acceptodds
Under review as a conference paper at ICLR 2027

CoCo: COllaborate via COarsening for Personalized Federated Graph Learning

Abstract

Federated graph learning (FGL) enables collaborative training of graph neural networks without sharing raw data, but suffers from missing global structure and significant data heterogeneity. While personalized methods mitigate heterogeneity, existing approaches rely on noisy, training-dependent similarity signals and lack principled mechanisms to determine who should collaborate with whom. We propose CoCo, a personalized FGL framework that infers a client collaboration graph via privacy-preserving global structure reconstruction. By decoupling collaboration from training, CoCo enables a stable, one-shot estimation of collaboration patterns, avoiding the instability and communication overhead of iterative similarity learning. We provide theoretical guarantees on the stability of the inferred global structure under reconstruction error, the propagation of this stability to the induced collaboration graph, and a graph-smoothing property of the personalized collaboration step. From a privacy perspective, CoCo combines geometric non-identifiability with differential privacy to limit information leakage. Experiments on diverse benchmarks demonstrate consistent improvements over strong federated and personalized baselines, along with robustness to heterogeneity, noise, and privacy-utility trade-offs.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
Graph Federated Learning, Distributed Learning, Structure Aware Learning, Graph Neural Networks, Graph Learning

Reviews

Among:
Shape:
1234this paper, Top 32%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.50 over 4 reviews, above 68% of the others.
Reviewer_tSqgOpenReview ↗
Rating
3
Confidence
4
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes CoCo, a personalized federated graph learning framework that constructs client collaboration from the underlying graph structure rather than from training-dependent model similarity. CoCo first uses anchor-based distance representations to reconstruct a global graph structure without directly sharing raw node features, then projects the reconstructed node-level graph to a client-level collaboration graph through graph coarsening, and finally performs graph-guided personalized model aggregation. The paper further provides stability analyses for both global-structure reconstruction and client-level coarsening, together with privacy analysis based on geometric non-identifiability and local differential privacy.

Critical strengths
  1. The motivation is clear and targets a meaningful weakness of personalized FGL. Instead of estimating client similarity from model parameters, gradients, or intermediate representations during training, CoCo derives collaboration from the underlying data geometry. This gives the paper a relatively clean distinction from training-dependent personalized aggregation methods.
  2. The theoretical analysis follows the actual method pipeline. The paper does not only provide a generic convergence result. It separately analyzes the stability of the reconstructed global structure, how this error propagates through client-level coarsening, and the graph-smoothing property of the subsequent personalized aggregation. This makes the theory relatively well aligned with the proposed framework.
  3. The privacy discussion is more complete than in many FGL papers. The authors explicitly distinguish geometric non-identifiability from formal privacy guarantees and complement the former with node-level local differential privacy on the released anchor-distance vectors. I appreciate that the paper does not treat non-invertibility alone as a sufficient privacy argument.
Critical weaknesses
  1. The baseline set is somewhat outdated for an ICLR 2027 submission. Although the paper includes a reasonably large number of baselines, the recent FGL comparison is mainly represented by methods such as FedGTA and FedIIH. Given the pace of progress in federated graph learning, I would expect substantially stronger 2025–2026 baselines before accepting the claim that CoCo represents the current state of the art.
  2. Recent federated graph compression/condensation methods are missing. This omission is particularly important because graph coarsening and compact structural representations are central to CoCo. Recent methods such as FedC4 (CIKM’25), FedGVD (CIKM’25), and DANCE (ICML’26) are closely related competitors from the graph compression/condensation perspective. Even if their objectives are not identical, they should be included, or at least carefully discussed and adapted under the same backbone and data partition protocol.
  3. The practical cost of reconstructing the global structure remains a concern. CoCo first reconstructs private embeddings from anchor distances and then learns a global graph before client-level coarsening. Although the paper introduces an additional coarsening step for scalability, this pipeline is still considerably more involved than directly estimating client similarity. In particular, the paper would benefit from a clearer end-to-end comparison of runtime, communication, and memory against recent personalized or condensation-based FGL methods.
Questions for authors

If the rebuttal provides convincing comparisons, I would be open to maintain my score.

  1. Can the authors compare CoCo with FedC4, FedGVD, and DANCE under the same datasets, client partitions, and GNN backbones? I view this as a fixable concern rather than a fundamental flaw.

  2. How much of the gain comes specifically from the proposed client-level coarsening formulation, rather than simply having a reconstructed global graph? A baseline using the same reconstructed graph but a simpler client-similarity construction would be useful.

  3. Can the authors provide an end-to-end comparison of runtime, communication cost, and GPU memory against the strongest recent FGL baselines?

9 comments
AuthorsOpenReview ↗

W1; W2 and Q1; Q2 and W3-part1: Divided in parts due to space constraints

We sincerely thank the reviewer for the careful and detailed assessment of our work.

W1

We have extended our evaluation to include four recent methods: FedStruct (ICLR 2025), FedLAP (NeurIPS 2025), FedSPA (CVPR 2025), and FedSSA (ICML 2026), across six common node-classification benchmarks.

FedStruct and FedLAP exploit known cross-client graph connectivity through structural representations and spectral Laplacian methods, respectively. FedSPA addresses inter-client homophily heterogeneity through adaptive aggregation, while FedSSA aligns semantic and structural information across heterogeneous clients. In contrast, CoCo infers previously unknown inter-client relationships and uses the resulting collaboration graph for personalized model aggregation.

To address this concern within the rebuttal period, we evaluated all four recent baselines on six representative datasets from Table 1, covering both homophilic and heterophilic graphs. We remain open to extending these comparisons to the remaining benchmarks if needed.

Additional experimental results.

DataFedStructFedLAPFedSPAFedSSACoCo
Cora69.1368.7789.1085.3092.04
Cite67.5166.7875.6072.3079.87
Pub84.6781.0787.6088.0088.10
CS78.7179.0891.3089.9092.47
Tolokers80.4679.1079.2872.7079.39
Squi25.5731.1228.3037.8049.80

These additional comparisons strengthen the empirical evaluation against recent FGL methods while highlighting CoCo's distinct contribution of structure-informed personalized collaboration.


W2 and Q1: Comparison with Recent Federated Graph Condensation Methods

We thank the reviewer for highlighting FedC4 (CIKM 2025), FedGVD (CIKM 2025), and DANCE (ICML 2026). We agree that these are relevant methods from the graph compression and condensation perspective, and have added a discussion and new experimental comparisons in Appendix G.

FedC4 employs graph condensation for compact client-to-client knowledge exchange; FedGVD combines condensed representations with virtual-node-based knowledge distillation; and DANCE performs dynamic condensation for federated text-attributed graphs. In contrast, CoCo focuses on inferring unknown inter-client structural relationships and using the resulting collaboration graph for personalized model aggregation. Coarsening in CoCo serves primarily as a scalability mechanism rather than a learned representation for exchanging knowledge.

We evaluated these methods using matched datasets, client partitions, GNN backbones, and training protocols, and over five seeds.

DataFedC4FedGVDDANCECoCo
Cora76.95 ± 1.6781.55 ± 0.3887.46 ± 0.9392.04 ± 0.35
CiteSeer68.11 ± 1.8870.28 ± 0.6973.61 ± 0.6479.87 ± 0.19
PubMed80.33 ± 1.1284.81 ± 0.3786.36 ± 0.2388.10 ± 0.07
Photo82.15 ± 2.0487.91 ± 0.4490.51 ± 0.1492.71 ± 0.68
CSOOMOOM88.67 ± 0.2292.47 ± 0.10
Physics92.77 ± 0.2694.48 ± 0.3695.30 ± 0.7295.95 ± 0.05
Chameleon46.11 ± 1.8252.80 ± 0.5851.54 ± 1.0661.25 ± 1.46
Squirrel39.28 ± 3.3145.92 ± 0.3743.22 ± 0.5049.80 ± 0.49
Tolokers76.86 ± 1.4678.74 ± 0.3377.92 ± 0.4879.39 ± 0.04
AR43.31 ± 0.8147.15 ± 0.2348.57 ± 0.5952.21 ± 0.22

CoCo achieves higher mean accuracy than all successfully evaluated alternatives across the ten datasets, supporting its effectiveness relative to recent condensation-based FGL approaches.

Computational considerations and future direction. While condensation methods may involve additional optimization of compact graph representations, CoCo uses lightweight UGC coarsening and one-time structure inference in the static setting. Integrating learned graph condensation as an alternative local compression strategy is a promising future extension.

We have included these methodological distinctions in Appendix G.


Q2 and W3-part1 Contribution of client-level coarsening

We clarify why CoCo uses graph coarsening and provide an additional controlled ablation.

CoCo uses coarsening for two distinct purposes: (i) client-level collaboration (Section 3.2), where the reconstructed global graph is projected into a smaller client collaboration graph; and (ii) scalability (Section 3.4, Appendix G), where each client first compresses its local graph into supernodes to reduce the cost of global reconstruction.

Why client-level coarsening? The main principle of graph coarsening is to reduce graph size while preserving useful structural information. Loukas [1] establishes spectral and cut-preservation guarantees under suitable conditions, while UGC [2, 3] demonstrates efficient graph reduction while retaining useful graph information.

Continuing in the next...

AuthorsOpenReview ↗

Q2 and W3-part1; W3-part2 and Q3: Divided in parts due to space constraints

Motivated by this principle, CoCo first learns fine-grained node relationships and then constructs the client collaboration graph through the size-normalized projection:

LC=PLGP⊤,P=(S⊤S)−1S⊤.L_C=PL_GP^\top,\qquad P=(S^\top S)^{-1}S^\top.

This projection is simple, requires no additional optimization, and accounts for different client sizes. Unlike methods that directly compare aggregated client features, it uses node-level structural relationships before forming client affinities. This can be particularly useful when clients contain heterogeneous groups of nodes.

To examine the benefit of this design, we compare full CoCo with two direct client-similarity approaches:

  • Anchor-DNA: Constructs client affinities directly from aggregated anchor-distance profiles.
  • Client-Recon: Constructs client affinities from aggregated reconstructed embeddings, without learning the global node-level graph.

All methods use consistent data splits and evaluation protocols, with the personalized aggregation mechanism unchanged.

Table: Node-classification accuracy (%)

DatasetAnchor-DNAClient-ReconFull CoCoGain
CiteSeer76.9277.5879.87+2.29
PubMed86.3486.1888.10+1.76
Amazon-Photo83.4783.3392.71+9.24

Full CoCo outperforms both direct alternatives by 2.29, 1.76, and 9.24 percentage points, respectively. These results support the benefit of learning global node-level relationships before constructing client affinities, rather than relying only on aggregated client representations.

Thus, client-level coarsening provides a simple way to summarize learned global structure into meaningful collaboration weights without additional optimization. The ablation demonstrates the benefit of the combined reconstruction-and-coarsening pipeline, although it does not independently isolate the projection when the reconstructed global graph is held fixed.

References [1] Loukas (2019). Graph Reduction with Spectral and Cut Guarantees. JMLR. [2] Kataria et al. (2024). UGC: Universal Graph Coarsening. NeurIPS. [3] Kataria et al. (2026). Fast and Scalable Hashing-Based Universal Graph Coarsening. IEEE TPAMI.


W3-part2 and Q3 (Runtime, communication cost, and scalability)

We have extended Table 8 with additional recent FGL methods and datasets, and clarify the one-time preprocessing cost and memory requirements using Table 9.

1. Why is the additional computation manageable?

CoCo separates structure inference from federated training. The global graph is reconstructed once, and the client collaboration graph is then obtained through the simple projection LC=PLGP⊤L_C=PL_GP^\top, which requires no iterative optimization.

For large datasets, CoCo additionally uses local UGC coarsening (Section 3.4, Appendix G) to compress each client's graph into supernodes before global reconstruction. Thus, the expensive reconstruction step operates on N′≪NN'\ll N supernodes rather than all original nodes.

2. Extended runtime and communication comparison.

We have expanded Table 8 to include 14 methods across six datasets, including recent methods such as FedStruct, FedLAP, FedSPA, FedSSA, and FedAux.

Table 8 (Extended): Wall-clock communication time (seconds per round; lower is better).

MethodCoraCiteSeerPubMedCSTolokersSquirrel
CoCo1.51.21.21.61.31.0
FedPub24.04.04.25.44.34.6
FedGTA4.14.83.72.32.62.4
FedDC1.81.91.81.61.31.4
FedTGP6.05.24.04.32.32.7
MOON2.72.83.22.41.91.8
SCAFFOLD1.51.62.11.61.31.1
FedTAD23.422.315.021.510.912.7
FedSAGE+14.212.935.3490.4543.5356.8
FedAux258925832999301829492988
FedSPA5.96.05.96.26.16.0
FedSSA60.095.9193.32519258.7214.4
FedStruct4.94.97.911.116.912.0
FedLAP18.620.161.665.560.433.3

CoCo achieves the lowest or joint-lowest reported per-round communication time across all six datasets. In particular, it is faster than FedStruct, FedLAP, FedGTA, and FedTAD on every evaluated dataset. This efficiency comes from learning the collaboration structure once instead of repeatedly estimating client relationships during training.

Continuing in the next...

AuthorsOpenReview ↗

W3-part2 and Q3

3. One-time preprocessing time and GPU memory.

Table 9 already reports the one-time PP-GSI cost across all 14 datasets.

CoCo PP-GSI preprocessing time and peak GPU memory.

DatasetTime (s)GPU memory (MB)
Cora3.7237.55
CiteSeer4.9686.65
PubMed3.0719.55
Amazon-Photo4.3224.66
Coauthor-Physics9.41186.97
ogbn-arxiv2.4112.02
Chameleon3.3944.27
Squirrel2.8632.75
Coauthor-CS5.7683.21
Tolokers2.6212.07
Amazon-Ratings4.9620.89
Questions5.7542.93
Reddit3.7532.21
ogbn-products31.36325.63

PP-GSI takes only a few seconds on most datasets, and even on ogbn-products (approximately 2.45 million nodes), preprocessing takes 31.36 seconds with 325.63 MB reported peak GPU memory.

Importantly, these costs are incurred only once before federated training, while the learned client collaboration graph is reused across communication rounds.

4. Complexity and scalability.

Appendix A.8 provides the one-time PP-GSI complexity for the scalable setting: O(K2d+N′Kd+TMDSN′Kd+CGL(N′,d)),O(K^2d+N'Kd+T_{\mathrm{MDS}}N'Kd+C_{\mathrm{GL}}(N',d)), where N′≪NN'\ll N denotes the number of supernodes after local coarsening. Furthermore, Table 11 shows that CoCo retains useful accuracy under substantial graph reduction. For example, on Cora, retaining only 10% of nodes achieves 91.05% accuracy, compared with 92.04% without coarsening.

Thus, CoCo controls the initial reconstruction cost through local graph reduction and avoids repeatedly learning collaboration weights during training.

Reviewer_reUEOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies personalized federated graph learning, abbreviated FGL, where clients hold disjoint subgraphs that cannot be centralized. The authors identify four problems: P1, missing global cross-client structure; P2, data heterogeneity; P3, noisy training-dependent client-similarity signals; and P4, uncharacterized leakage from the signals used to infer collaboration. They propose CoCo, a three-stage pipeline. First, PP-GSI: each client releases Euclidean distances from its private nodes to K shared public anchors, and the server reconstructs embeddings via anchored SMACOF and learns a global node-level graph with a Kalofolias-style smoothness objective in Eq. 3. Second, the recovered global Laplacian is coarsened to the client level through the size-normalized projection P = [S^T S]^{-1} S^T, yielding an M x M operator whose off-diagonal entries are mean inter-client affinities. Third, personalized aggregation mixes each client's locally trained parameters with those of structurally related clients using a symmetric normalized collaboration matrix W. The main claims are: one-shot, training-independent collaboration inference; stability of the recovered structure and of its client-level coarsening, shown in Theorems 1 and 2; a graph-smoothing property of the aggregation step, Theorem 3; privacy through geometric non-identifiability when K < d plus node-level approximate local differential privacy, Theorem 4 and Lemma 2; and strong empirical results on 14 benchmarks, scaling to ogbn-products with about 2.45M nodes via UGC-based local coarsening.

Critical strengths
  1. Motivation: The problem is well motivated and clearly positioned. Asking which clients should collaborate, and to what extent, is a central open question in personalized FL, and the paper articulates why training-dependent similarity estimation, as in Fed-PUB, pFedGraph, and FedGTA, is unstable and communication-heavy. Decoupling collaboration inference from optimization and reusing the missing-structure problem specific to subgraph FGL, namely P1, to answer it is a clean and significant reframing, and the P1 to P4 problem statements make the paper easy to situate against prior work.

  2. Method design: The idea of defining client collaboration as a coarsened projection of a reconstructed global geometry is novel, simple, and modular. Each stage is a standard, well-understood component, namely anchored MDS, graph learning from smooth signals, and normalized adjacency aggregation, which makes the pipeline interpretable and analyzable. Theorem 3 is a nice touch: the implemented aggregation step is exactly one gradient step on the collaboration energy with step size 1 - alpha, so the smoothing claim covers the actual algorithm rather than an idealized variant. Theorem 2's explicit 1/n_min propagation is also practically meaningful for size-imbalanced federations.

  3. Experiments: The empirical study is broad. It covers 14 datasets across five categories, 11 baselines including the recent FGL methods Fed-PUB, FedGTA, FedTAD, FedTGP, FedSage+, AdaFGL, and FedIIH, mean and standard deviation over five runs in Table 10, scalability to ogbn-products, ablations on alpha, anchor generation, coarsening ratio, client count, and partition schemes, a dynamic non-stationary study, node-level LDP and model-level DP evaluations, five inference-attack suites, and measured communication and preprocessing costs in Tables 8 and 9. The anonymized code release further supports reproducibility.

Critical weaknesses
  1. Several Table 1 improvements are small or within noise. PubMed improves by +0.17 over FedSage+, 88.10 vs 87.93 with std 0.18, Questions by +0.04 in a regime where every method scores about 97.01, suggesting a near-degenerate split, OG-P by +0.16, and Tolokers by +0.16, and CoCo loses on Amazon-Photo and Reddit. The abstract claim of "consistent improvements over strong baselines" should be tempered, and an average-rank or significance analysis would make the evidence more convincing.

  2. The link-prediction study in Table 2 is thin: only four datasets and the four generic baselines FedDC, FedAvg, FedProx, and SCAFFOLD, with none of the personalized FGL baselines from Table 1. The dynamic study in Table 3 uses only three datasets, and M_re on Photo, 84.27, exceeding the pre-shift M_orig of 82.01 under identical training rounds is unexplained.

Questions for authors

Please refer to the weaknesses.

6 comments
AuthorsOpenReview ↗

Rebuttal: W1 and W2

We sincerely thank the reviewer for the careful and detailed assessment of our work.

W1.

We thank the reviewer for this important observation. We have revised the abstract to temper the performance claims.

Changed abstract

from

Experiments on diverse benchmarks demonstrate consistent improvements over strong federated and personalized baselines, along with robustness to heterogeneity, noise, and privacy-utility trade-offs.

to

Experiments across diverse benchmarks demonstrate competitive performance against strong federated and personalized baselines, achieving the highest mean accuracy on 12 of 14 node-classification datasets along with robustness to heterogeneity, noise, and privacy-utility trade-offs.


W2

We have expanded both evaluations with additional datasets and baselines and clarify the dynamic results below.

To address the limited coverage of Table 2, we evaluated CoCo on 11 datasets against 12 baselines, including personalized FGL methods such as FedPub, FedGTA, FedTGP, FedSAGE+, AdaFGL, FedTAD, and FedIIH.

Table: Link prediction performance (%). Best results are highlighted in bold. OOM denotes out of memory.

DatasetCoCoF-PubF-AvgF-GTAF-DCF-TGPMOONSCAF.F-Sage+AdaFGLF-ProxF-TADF-IIH
Cora73.8652.1371.4172.4567.4572.3272.8565.3453.2370.7371.0971.7970.24
CiteSeer72.7353.7071.6470.7170.5170.4271.7769.3171.5270.3470.7671.8571.15
PubMed68.6950.3867.9867.8956.1567.8954.4251.2667.7367.7368.5368.1768.50
Squirrel74.3456.2670.7270.7968.6072.7669.3056.6373.3170.6671.0070.5173.75
Tolokers69.5455.9669.4869.5067.3265.5069.4960.4065.1168.8468.2069.1968.90
Amazon-Ratings72.9654.1372.3972.4966.2371.4670.0051.6750.0369.4372.6672.2572.30
Questions61.5850.4257.1957.0459.5252.9056.6451.1750.0455.1257.4657.9860.95
Coauthor-CS75.2950.7271.3473.4067.3574.2069.4662.0971.1770.8770.2371.4872.88
Coauthor-Physics76.1158.8072.5373.7968.4473.0963.9859.0172.5672.3372.3172.1473.24
Chameleon75.5455.4974.0971.6267.8168.7667.4862.0671.0570.3574.2968.7974.53
ogbn-arxiv74.5650.0168.0471.4159.3473.5967.1750.2067.8866.5168.2267.18OOM

These results provide a broader comparison with strong personalized FGL methods and further support CoCo's effectiveness for link prediction.

Extended dynamic evaluation and Photo clarification

We also expanded the dynamic study on more datasets.

Table: Accuracy (%) under distribution shifts.

DatasetMorigM_{\mathrm{orig}}McorrM_{\mathrm{corr}}MreM_{\mathrm{re}}Gain
Cora91.2689.0589.90+0.85
PubMed85.8182.0484.62+2.58
Amazon-Photo82.0180.7284.27+3.55
Coauthor-CS85.2483.3484.33+0.99
Squirrel41.4225.7426.46+0.72
Coauthor-Physics92.8490.9291.14+0.22
Amazon-Ratings42.2238.0138.56+0.55
CiteSeer79.7276.7676.80+0.04

Re-learning the collaboration graph improves accuracy over retaining the outdated graph on all eight datasets.

Clarification of Amazon-Photo (84.27 vs. 82.01):

As described in Section 5.2, MorigM_{\mathrm{orig}} is the pre-shift checkpoint, while McorrM_{\mathrm{corr}} and MreM_{\mathrm{re}} continue training from this same checkpoint on shifted data for identical additional rounds. The only difference between these two settings is whether the collaboration graph is updated.

Thus, the controlled comparison is MreM_{\mathrm{re}} vs. McorrM_{\mathrm{corr}}, where updating the graph improves photo accuracy from 80.72% to 84.27% (+3.55 points). The higher accuracy relative to MorigM_{\mathrm{orig}} can result from continued training and the changed data; it does not imply that distribution shift itself improves accuracy.

We have revised the manuscript to include the extended link-prediction and dynamic-setting results, along with an updated abstract. All changes are highlighted in blue for ease of reference.

AuthorsOpenReview ↗

Appeal to the Reviewer

Dear Reviewer reUE,

Thank you again for your detailed and thoughtful feedback on our submission. We have provided a point-by-point rebuttal in order to address the raised concerns.

As the rebuttal period is ending in a few days, we would be very grateful if you could kindly let us know whether any key concerns remain or if our clarifications address your main objections. If the rebuttal alleviates some of your worries, we would also appreciate it if you could consider updating your score accordingly.

Thank you for your time and consideration.

Sincerely,

Authors.

AuthorsOpenReview ↗

Appeal to the Reviewer

Dear Reviewer reUE,

We would like to thank you for your positive recognition of our work. Based on your concerns in rebuttal we have now incorporated your suggestions in the manuscript.

As the author-reviewer discussion phase is nearing its conclusion in a few hours, we would like to politely inquire if you have any outstanding concerns regarding our work. We’d be more than happy to elaborate on any aspect that might need further explanation.

And if you feel that your concerns have been adequately addressed, we would be sincerely grateful if you would consider updating your rating to reflect your current assessment of the work. Your feedback is indeed important for determining the ultimate fate of our work.

Sincerely,

Authors

Reviewer_tHFTOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
3
Soundness
1
Read review
Paper summary

This paper proposes CoCo, a personalized federated graph learning framework that infers a global graph Laplacian using anchor-based distances. The Laplacian is then coarsened to obtain a client collaboration graph for personalized model aggregation. The authors provide theoretical results on reconstruction stability, graph smoothing, and privacy, and evaluate the method on several graph datasets.

Critical strengths

The paper proposes an interesting approach for determining client collaboration based on graph structure. The experimental evaluation is extensive and shows promising results across different datasets.

Critical weaknesses
  1. Theorem 1 assumes a small embedding reconstruction error but does not establish that the proposed anchor-based reconstruction can achieve such an error. In particular, when K<dK < d, anchor distances do not uniquely determine the original features, and it is unclear whether they are sufficient to recover the cross-client relationships needed to construct the collaboration graph.

Moreover, Theorem 2 only bounds the error of the coarsened Laplacian, not the final normalized collaboration matrix (WW) used for aggregation. Similarly, Theorem 3 guarantees graph smoothing but does not establish improvements in prediction accuracy or convergence.

  1. The default experiments rely on real data points as public anchors. However, representative and non-sensitive anchors may not be available in practical federated settings. If anchors are obtained from client data, their release may introduce additional privacy risks. Although synthetic anchors are considered, their effectiveness under realistic distribution mismatch is not sufficiently evaluated.

CoCo also reconstructs the full node-level Laplacian, which contains detailed information about private node relationships, although only the client-level Laplacian is needed for aggregation. The necessity of this intermediate reconstruction is unclear, and it may introduce unnecessary privacy exposure and computational costs.

Although the authors use local coarsening for scalability, the computational cost of global graph learning remains unspecified. Furthermore, the privacy analysis combines different guarantees without clearly establishing their scope across the complete pipeline, particularly when supernode representations are used.

Finally, the experiments do not clearly isolate the benefit of full global Laplacian reconstruction compared with directly estimating client-level affinities.

Questions for authors
  1. When K<dK < d, different node configurations can produce identical anchor distances but different pairwise relationships. Under what assumptions can CoCo reliably reconstruct the global graph? Can the authors provide a reconstruction guarantee based on the observed anchor distances rather than assuming a small embedding error?

  2. Can the authors extend Theorem 2 to bound the reconstruction error of the final collaboration matrix (W)? Also, how does the graph-smoothing guarantee in Theorem 3 relate to the convergence or prediction performance of personalized models?

  3. How can representative anchors be obtained when public in-distribution data are unavailable? If anchors are generated from client data, how is their privacy protected?

  4. Why is reconstructing the full node-level Laplacian necessary when only client-level affinities are ultimately required? Could the coarsened Laplacian be estimated directly? Also, can the authors provide the computational complexity of the global graph-learning step and an ablation showing the benefit of full reconstruction?

  5. Can the authors clarify how anchor selection, Laplacian reconstruction, and graph coarsening affect privacy leakage? In particular, does the node-level LDP guarantee extend to the scalable implementation that uses feature-dependent supernodes?

  6. The paper does not discuss the recent works FedStruct (ICLR 2025) and FedLAP (NeurIPS 2025), which also use global graph structure in federated learning. Although their assumptions differ from CoCo, their relationship to this work should be discussed, and comparisons should be given where applicable.

J. Aliakbari, J. Östman, A. Graell i Amat, "Decoupled Subgraph Federated Learning," ICLR, 2025

J. Aliakbari, J. Östman, A. Panahi, A. Graell i Amat, "Subgraph Federated Learning via Spectral Methods," NeurIPS, 2025.

12 comments
AuthorsOpenReview ↗

Q1 and Q2 (and W1 part1-2): We have divided the responses in parts due to space constraints.

We sincerely thank the reviewer for the careful and detailed assessment of our work.

Q1 and W1-part 1 (Theorem 1 assumes a small....the collaboration graph.)

We clarify that Theorem 1 establishes a conditional stability guarantee: given bounded embedding reconstruction error ϵX\epsilon_X, the resulting global graph Laplacian error is bounded by cGϵXc_G\epsilon_X. The theorem does not independently establish an upper bound on the reconstruction error achieved by anchored-SMACOF. We therefore complement this theoretical result with empirical evidence of reconstruction fidelity and structural preservation.

Classical localization literature [1] establishes that d+1d+1 suitably positioned anchors are sufficient for exact reconstruction in d-dimensional space. Conversely, when K<d, exact feature recovery is generally non-unique, as also established by our Lemma 1 and Theorem 5. Consequently, a universal exact reconstruction guarantee cannot be obtained from these observations alone without additional assumptions.

However, CoCo's objective is not exact feature reconstruction but recovering the structural relationships needed for client collaboration. Landmark-based MDS studies [2, 3] establish that limited landmark observations can recover useful geometric information and that increasing the number of landmarks can improve reconstruction accuracy. More directly, PPDA [4] demonstrates neighborhood preservation with K<d.

To empirically assess the reconstruction fidelity achieved by CoCo, Figure 4(a–b) reports normalized Frobenius reconstruction error (XfrobX_{frob}) and neighborhood-preservation F-score across varying anchor counts.

Cora d=1433d=1433

KXfrobX_{frob}
3601.00
5400.72
7200.52
9000.36
12000.20
14000.08
K>=1433K>=1433≈0.0

PubMed d=500d=500

KXfrobX_{frob}
3001.00
3500.72
4000.48
4500.22
4700.14
4900.04
K>=500K>=500≈0.0

These results show that small reconstruction errors are achievable even before reaching the ambient feature dimension. The accompanying F-score results demonstrate that useful neighborhood relationships are preserved in this regime. These findings motivate selecting anchors within a practical operating window, d−T≤K<d,d-T\le K<d, where T>0 controls the distance from the feature dimension. Within this range, we can empirically identify anchor counts offering good reconstruction fidelity while retaining the geometric non-identifiability established by Theorem 5. We recognize that geometric non-identifiability does not prevent all forms of approximate inference. Therefore, CoCo additionally provides node-level LDP (Section 4) to protect released anchor-distance representations when the mechanism is enabled, including when K approaches or exceeds d.

Thus, while Theorem 1 provides conditional theoretical stability, our experiments substantiate the practical reconstruction fidelity and structural preservation achieved by CoCo under the evaluated settings. We will make this distinction explicit in the revised manuscript.

References [1] Khan et al. (2009). Distributed Sensor Localization. IEEE TSP, 57(5):2000–2016. [2] de Silva & Tenenbaum (2004). Sparse Multidimensional Scaling Using Landmark Points. Stanford TR. [3] Platt (2005). FastMap, MetricMap, and Landmark MDS are all Nyström Algorithms. AISTATS, 261–268. [4] Malik et al. (2024). PPDA: Privacy-Preserving Distributed Graph Learning. ICONIP, 308–331.


Q2 and W1-part 2: Extension of Theorem 2 to the Final Collaboration Matrix

To address this concern, we have extended the theoretical analysis to establish a stability bound for the final collaboration matrix.

Corollary 1. Let ACA_C and AC⋆A_C^\star denote the client affinity matrices obtained from the reconstructed and oracle client-level Laplacians L^C\widehat L_C and LC⋆L_C^\star, respectively, using the same affinity construction and entrywise positive-part operation defined in Section 3.3.

Let

D_C^\star=\operatorname{Diag}(A_C^\star\mathbf{1}),$$ and define $$W=D_C^{-1/2}A_CD_C^{-1/2},\qquad W^\star=(D_C^\star)^{-1/2}A_C^\star(D_C^\star)^{-1/2}.$$ Let $d_m=(A_C\mathbf{1})_m$ and $d_m^\star=(A_C^\star\mathbf{1})_m$ denote the degrees of client $m$ in the reconstructed and oracle collaboration graphs, respectively. Assume all client degrees have a common positive lower bound $d_0>0$, such that $d_m,d_m^\star\geq d_0$ for every client $m$. Let $d_{\max}^\star=\max_m d_m^\star$. Then, extending Theorem 2, we obtain $$\lVert W-W^{\star}\rVert_F \leq \left( \frac{1}{d_0} + \frac{\sqrt{M}\\,d_{\max}^{\star}}{d_0^2} \right) \frac{c_G}{n_{\min}}\varepsilon_X.$$ For proof see next...
AuthorsOpenReview ↗

Proof (Corollary1), Q2 (W1 part3), Q3 (W2)

Proof. For a symmetric matrix QQ, affinity extraction sets. For m ≠ ℓ, define 𝒜(Q)[m,ℓ] = max(0, −Q[m,ℓ]), with zero diagonal. Since the positive-part operation is nonexpansive,

\leq \\|\widehat L_C-L_C^\star\\|_F.$$ Let $E=A_C-A_C^\star$, $H=D_C^{-1/2}$, and $H^\star=(D_C^\star)^{-1/2}$. Since $d-d^\star=E\mathbf{1}$, the matrix-vector norm inequality gives $$\begin{aligned} \\|d-d^\star\\|_2 &=\\|E\mathbf{1}\\|_2 \\\\ &\leq \\|E\\|_F\\|\mathbf{1}\\|_2 \\\\ &=\sqrt{M}\\|E\\|_F. \end{aligned}$$ Since $d_m,d_m^\star\geq d_0>0$, the mean-value theorem applied to $f(x)=x^{-1/2}$, with $|f'(x)|\leq 1/(2d_0^{3/2})$, implies $$\begin{aligned} \\|H-H^\star\\|_F &\leq \frac{1}{2d_0^{3/2}}\\|d-d^\star\\|_2 \\\\ &\leq \frac{\sqrt{M}}{2d_0^{3/2}}\\|E\\|_F. \end{aligned}$$ Furthermore, $$\\|H\\|_2,\\|H^\star\\|_2\leq d_0^{-1/2},$$ and since $A_C^\star$ is symmetric and nonnegative, $$\lVert A_C^{\ast} \rVert_2 \leq d_{\max}^{\ast}.$$ Expanding the difference between the normalized collaboration matrices gives $$\begin{aligned} W-W^\star ={}&HEH \\\\ &+(H-H^\star)A_C^\star H \\\\ &+H^\star A_C^\star(H-H^\star). \end{aligned}$$ Applying the triangle inequality and standard matrix-norm inequalities, $$\lVert W-W^{\star}\rVert_F \leq \lVert HEH\rVert_F + \lVert (H-H^{\star})A_C^{\star}H\rVert_F + \lVert H^{\star}A_C^{\star}(H-H^{\star})\rVert_F.$$ $$\lVert W-W^{\star}\rVert_F \leq \frac{\lVert E\rVert_F}{d_0} + \frac{2d_{\max}^{\star}}{\sqrt{d_0}} \lVert H-H^{\star}\rVert_F \leq \left( \frac{1}{d_0} + \frac{\sqrt{M}\\,d_{\max}^{\star}}{d_0^2} \right) \lVert E\rVert_F.$$ Finally, by Theorem 2, ‖E‖_F ≤ ‖L̂_C − L*_C‖_F ≤ c_G ε_X / n_min. we establish $$\lVert W-W^{\star}\rVert_F \leq \left( \frac{1}{d_0} + \frac{\sqrt{M}\\,d_{\max}^{\star}}{d_0^2} \right) \frac{c_G}{n_{\min}}\varepsilon_X.$$ **The result establishes that, under the positive-degree condition & the reconstruction assumptions of Theorem 1, stability propagates from the global Laplacian through client-level coarsening & normalization to the final collaboration matrix W used for personalized aggregation.** We have incorporated this result as **Corollary 1**, extending Theorem 2, with its complete proof in Appendix D.2 and a corresponding reference in Section 3.3 of the revised manuscript. ---- ## Q2 and W1-part 3 (how does the graph-smoothing guarantee in Theorem 3 .. personalized models?): We would like to clarify that the primary motivation behind Theorem 3 is to provide a principled characterization of structure-guided personalized collaboration, rather than to claim unconditional convergence or improved prediction accuracy. This motivation is consistent with prior personalized federated learning research, particularly pFedGraph (Ye et al., ICML 2023), which emphasizes that clients with similar data distributions should benefit from stronger collaboration and encourages model similarity through its optimization objective. Building on this principle, CoCo derives client relationships from the reconstructed global graph rather than training-dependent model similarities. The graph energy in Theorem 3 measures the degree-normalized variation of client parameters over these inferred relationships. The theorem establishes that the implemented aggregation step is exactly a gradient step on this energy and cannot increase it. We further clarify that for a fixed collaboration graph and $0< \alpha <1$, the aggregation operator contracts all positive-eigenvalue components of the normalized collaboration Laplacian. Consequently, repeated aggregation-only steps converge geometrically toward its kernel. This does not imply convergence of the complete nonconvex federated GNN training process, which includes intervening local optimization steps. Graph smoothing provides a structural regularization mechanism: it encourages compatible models among related clients, potentially improving knowledge sharing while the personalization coefficient $\alpha$ controls the degree of collaboration. Its effectiveness depends on how well the inferred structural relationships align with the clients' prediction tasks. The corresponding predictive benefits are supported empirically by our existing personalization ablations (Figure 4(c,d)) and accuracy-versus-communication-round evaluations (Fig. 3 & 8), rather than being asserted as a direct consequence of the smoothing theorem. ---- ## Q3 & W2 As discussed in Appendix A.2, CoCo supports 3 ways of obtaining anchors: (i) publicly available, non-sensitive reference data, (ii) consented or governance-approved reference samples, and (iii) independently generated synthetic anchors. Our default experiments use held-out reference samples excluded from all private client partitions. Thus, **CoCo does not require releasing private client samples as anchors**. Continued in the next...
AuthorsOpenReview ↗

Q3 (W2), Q4 (W2)

continuing Q3 and W2....

Effectiveness under distribution mismatch.

We have already evaluated two synthetic-anchor strategies in Appendix B.6, Table 12: Gaussian anchors sampled independently from N(0,Id)\mathcal N(0,I_d) and orthogonalized Gaussian anchors. Unlike in-distribution anchors, these synthetic anchors are not sampled from the underlying dataset, allowing us to evaluate performance under a mismatch between anchor and data distributions.

Table: Node-classification acc (%) with different anchor distributions.

DataSynthetic GaussianSynthetic Ortho-GausIn-Distribution K<d
Cora92.0192.0492.04
Pub86.3187.9088.10
Photo90.0491.0592.71

The results show that CoCo maintains competitive performance even with distribution-mismatched synthetic anchors. This demonstrates that representative real-data anchors are not essential for obtaining useful collaboration structures in these evaluated settings.

Future Direction. An interesting direction is to explore more representative synthetic anchors through federated Maximum Mean Discrepancy (MMD), as studied by [1]. This could help CoCo's synthetic anchor generation process match the underlying client data distributions without sharing raw data. We also plan to investigate differentially private anchor generation to further protect client information while maintaining reconstruction quality under distribution shifts.

Regarding privacy, independently generated synthetic anchors require no private client samples. If anchors are instead learned from private client data, their generation must be separately privacy-protected and accounted for; CoCo's existing node-level LDP guarantee applies to released anchor-distance representations, not automatically to anchor generation.

References: [1] Qiao, Ma, and Fan, Fed t-SNE & UMAP for Distributed Data Visualization, AAAI 2025


(Q4 and W2) Necessity and computational cost of global structure reconstruction

We address it through the motivation for global structure reconstruction, a new controlled ablation, and the existing complexity analysis.

Why reconstruct global structure? CoCo first learns fine-grained relationships between nodes and then uses the normalized projection LC=PLGP⊤L_C = P L_G P^{\top} to obtain client-level affinities. This differs from directly representing each client using a single aggregated feature vector or distance profile. When clients contain heterogeneous groups of nodes, aggregation before structure learning can discard relationships that are informative for selecting collaboration partners. CoCo therefore learns these relationships before forming the client collaboration graph.

Additional controlled ablation. To directly evaluate whether this intermediate step is necessary, we compare full CoCo with two alternatives that estimate client affinities without reconstructing the global node-level graph:

  • Anchor-DNA: Affinities constructed directly from aggregated anchor-distance profiles.
  • Client-Recon: Affinities constructed from aggregated reconstructed node embeddings.

All methods use consistent data splits and evaluation protocols, with the personalized aggregation mechanism unchanged.

Table: Node-classification accuracy (%)

DatasetAnchor-DNAClient-ReconFull CoCoGain over best direct
CiteSeer76.9277.5879.87+2.29
PubMed86.3486.1888.10+1.76
Amazon-Photo83.4783.3392.71+9.24

Full CoCo consistently outperforms both direct client-level alternatives, with improvements of 2.29, 1.76, and 9.24 percentage points. This directly supports the value of learning fine-grained global relationships before constructing the client collaboration graph.

Computational cost. Appendix A.8 provides the one-time inference complexity:

O(K2d+N′Kd+TMDSN′Kd+CGL(N′,d))O(K^2d + N'Kd + T_{\mathrm{MDS}}N'Kd + C_{\mathrm{GL}}(N',d))

where N' is the number of nodes after optional local coarsening. For dense pairwise graph learning, CGLC_{\mathrm{GL}} depends on the solver and can scale quadratically with N'. Importantly, CoCo does not require reconstructing the full original-node graph on large datasets. Section 3.4 and Appendix G describe local UGC coarsening, which reduces the effective graph size before global structure inference. Moreover, this preprocessing is performed only once, and the resulting collaboration graph is reused throughout training. Existing Table 11 further shows that substantial coarsening retains competitive accuracy, while Tables 8–9 quantify preprocessing and communication costs.

Together, the direct ablation establishes the practical benefit of global structure reconstruction, while the one-time computation and local coarsening address its scalability.

We would be happy to include the additional ablation results in the revised appendix.

Reviewer_cQWeOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper proposes CoCo, a personalized federated graph learning framework that constructs client collaboration independently of model training. Clients share anchor-distance representations, from which the server estimates a global graph and coarsens it into a client-level collaboration graph. This graph guides personalized model aggregation. The authors provide theoretical bounds connecting embedding reconstruction error to global- and client-level structural perturbations, together with a graph-smoothing guarantee for the aggregation step. Privacy analysis combines geometric non-identifiability under specified conditions with node-level approximate local differential privacy for the released distance vectors.

Validation includes node classification on 14 graph benchmarks, link prediction on four datasets, and experiments examining distribution shifts, noisy clients, graph coarsening, anchor construction, and privacy–utility trade-offs. CoCo reports the highest mean node classification accuracy on 12 of 14 datasets and the best link prediction results among the evaluated baselines.

Critical strengths
  1. A coherent mechanism for constructing collaboration independently of model training. CoCo uses anchor-distance geometry to infer a global affinity structure and projects it into client-level relationships for personalized aggregation. This directly addresses how to select collaboration partners without relying on evolving model similarities. The accompanying stability and smoothing results clarify properties of the construction and aggregation, making this a substantive methodological contribution.

  2. Broad empirical validation with measurable gains over strong baselines. The evaluation covers 14 node-classification datasets, four link-prediction datasets, multiple GNN backbones, and additional tests of anchor construction, distribution shifts, coarsening, and privacy perturbations. CoCo achieves the highest mean node-classification accuracy on 12 of 14 datasets. Its improvements on Cora, CiteSeer, and Amazon-Ratings are particularly encouraging relative to the reported run-to-run variation. This breadth supports the practical relevance of the proposed collaboration mechanism.

Critical weaknesses
  1. The stability analysis does not establish an end-to-end guarantee for the aggregation weights. Theorem 1 assumes a bound on embedding reconstruction error without bounding the error produced by the proposed reconstruction procedure. Theorem 2 controls perturbations in the coarsened operator but does not extend this guarantee to the final degree-normalized aggregation matrix WW. The sensitivity of WW to small client degrees, and the effect of the degree regularization used in implementation, remain unquantified. These gaps limit the theoretical support for the stability of the implemented collaboration mechanism.

  2. The experiments do not sufficiently isolate the contribution of the inferred client relationships. The paper lacks a controlled comparison against uniform affinities or a client-permuted version of the inferred affinity matrix, using the same aggregation rule, backbone, local training, and personalization weight. The α\alpha sweep changes the amount of collaboration while retaining the inferred relationships. Consequently, the experiments do not establish how much of the improvement in the static setting depends on correctly matching clients through the proposed structure-inference procedure. This leaves the contribution of the paper’s central mechanism insufficiently isolated.

Questions for authors
  1. Clarification of the stability claim. Theorem 1 assumes a bound on embedding reconstruction error, while Theorem 2 controls the coarsened operator. What supports the stability of the final aggregation matrix WW, particularly when some client degrees are small? Does the analysis require additional reconstruction or minimum-degree assumptions? This would affect how strongly I interpret the claimed stability of the collaboration mechanism.

  2. Request for evidence isolating the collaboration mechanism. Have you compared the inferred client affinities against uniform affinities or randomly permuted affinities, with the same backbone, local training, and personalization weight? Such a controlled comparison would help determine whether the gains specifically depend on recovering meaningful client relationships. This concerns validation of the current contribution, rather than an extension to a new setting.

7 comments
AuthorsOpenReview ↗

Q1 (and W1 part1-2): Divided into parts due to space constraints.

We sincerely thank the reviewer for the careful and detailed assessment of our work.

Q1 and W1-part 1 (Theorem 1 assumes a small....the collaboration graph.)

We clarify that Theorem 1 establishes a conditional stability guarantee: given bounded embedding reconstruction error ϵX\epsilon_X, the resulting global graph Laplacian error is bounded by cGϵXc_G\epsilon_X. The theorem does not independently establish an upper bound on the reconstruction error achieved by anchored-SMACOF. We therefore complement this theoretical result with empirical evidence of reconstruction fidelity and structural preservation.

Classical localization literature [1] establishes that d+1d+1 suitably positioned anchors are sufficient for exact reconstruction in d-dimensional space. Conversely, when K<d, exact feature recovery is generally non-unique, as also established by our Lemma 1 and Theorem 5. Consequently, a universal exact reconstruction guarantee cannot be obtained from these observations alone without additional assumptions.

However, CoCo's objective is not exact feature reconstruction but recovering the structural relationships needed for client collaboration. Landmark-based MDS studies [2, 3] establish that limited landmark observations can recover useful geometric information and that increasing the number of landmarks can improve reconstruction accuracy. More directly, PPDA [4] demonstrates neighborhood preservation with K<d.

To empirically assess the reconstruction fidelity achieved by CoCo, Figure 4(a–b) reports normalized Frobenius reconstruction error (XfrobX_{frob}) and neighborhood-preservation F-score across varying anchor counts.

Cora d=1433d=1433

KXfrobX_{frob}
3601.00
5400.72
7200.52
9000.36
12000.20
14000.08
K>=1433K>=1433≈0.0

PubMed d=500d=500

KXfrobX_{frob}
3001.00
3500.72
4000.48
4500.22
4700.14
4900.04
K>=500K>=500≈0.0

These results show that small reconstruction errors are achievable even before reaching the ambient feature dimension. The accompanying F-score results demonstrate that useful neighborhood relationships are preserved in this regime. These findings motivate selecting anchors within a practical operating window, d−T≤K<d,d-T\le K<d, where T>0 controls the distance from the feature dimension. Within this range, we can empirically identify anchor counts offering good reconstruction fidelity while retaining the geometric non-identifiability established by Theorem 5. We recognize that geometric non-identifiability does not prevent all forms of approximate inference. Therefore, CoCo additionally provides node-level LDP (Section 4) to protect released anchor-distance representations when the mechanism is enabled, including when K approaches or exceeds d.

Thus, while Theorem 1 provides conditional theoretical stability, our experiments substantiate the practical reconstruction fidelity and structural preservation achieved by CoCo under the evaluated settings. We will make this distinction explicit in the revised manuscript.

References [1] Khan et al. (2009). Distributed Sensor Localization. IEEE TSP, 57(5):2000–2016. [2] de Silva & Tenenbaum (2004). Sparse Multidimensional Scaling Using Landmark Points. Stanford TR. [3] Platt (2005). FastMap, MetricMap, and Landmark MDS are all Nyström Algorithms. AISTATS, 261–268. [4] Malik et al. (2024). PPDA: Privacy-Preserving Distributed Graph Learning. ICONIP, 308–331.


Q1 and W1-part 2: Extension of Theorem 2 to the Final Collaboration Matrix

To address this concern, we have extended the theoretical analysis to establish a stability bound for the final collaboration matrix.

Corollary 1. Let ACA_C and AC⋆A_C^\star denote the client affinity matrices obtained from the reconstructed and oracle client-level Laplacians L^C\widehat L_C and LC⋆L_C^\star, respectively, using the same affinity construction and entrywise positive-part operation defined in Section 3.3.

Let

D_C^\star=\operatorname{Diag}(A_C^\star\mathbf{1}),$$ and define $$W=D_C^{-1/2}A_CD_C^{-1/2},\qquad W^\star=(D_C^\star)^{-1/2}A_C^\star(D_C^\star)^{-1/2}.$$ Let $d_m=(A_C\mathbf{1})_m$ and $d_m^\star=(A_C^\star\mathbf{1})_m$ denote the degrees of client $m$ in the reconstructed and oracle collaboration graphs, respectively. Assume all client degrees have a common positive lower bound $d_0>0$, such that $d_m,d_m^\star\geq d_0$ for every client $m$. Let $d_{\max}^\star=\max_m d_m^\star$. Then, extending Theorem 2, we obtain $$\lVert W-W^{\star}\rVert_F \leq \left( \frac{1}{d_0} + \frac{\sqrt{M}\\,d_{\max}^{\star}}{d_0^2} \right) \frac{c_G}{n_{\min}}\varepsilon_X.$$ For proof see next...
AuthorsOpenReview ↗

Proof (Corollary1), Q1 (W1 part3) and Q2 (W2)

Proof. For a symmetric matrix QQ, affinity extraction sets. For m ≠ ℓ, define 𝒜(Q)[m,ℓ] = max(0, −Q[m,ℓ]), with zero diagonal. Since the positive-part operation is nonexpansive,

\leq \\|\widehat L_C-L_C^\star\\|_F.$$ Let $E=A_C-A_C^\star$, $H=D_C^{-1/2}$, and $H^\star=(D_C^\star)^{-1/2}$. Since $d-d^\star=E\mathbf{1}$, the matrix-vector norm inequality gives $$\begin{aligned} \\|d-d^\star\\|_2 &=\\|E\mathbf{1}\\|_2 \\\\ &\leq \\|E\\|_F\\|\mathbf{1}\\|_2 \\\\ &=\sqrt{M}\\|E\\|_F. \end{aligned}$$ Since $d_m,d_m^\star\geq d_0>0$, the mean-value theorem applied to $f(x)=x^{-1/2}$, with $|f'(x)|\leq 1/(2d_0^{3/2})$, implies $$\begin{aligned} \\|H-H^\star\\|_F &\leq \frac{1}{2d_0^{3/2}}\\|d-d^\star\\|_2 \\\\ &\leq \frac{\sqrt{M}}{2d_0^{3/2}}\\|E\\|_F. \end{aligned}$$ Furthermore, $$\\|H\\|_2,\\|H^\star\\|_2\leq d_0^{-1/2},$$ and since $A_C^\star$ is symmetric and nonnegative, $$\lVert A_C^{\ast} \rVert_2 \leq d_{\max}^{\ast}.$$ Expanding the difference between the normalized collaboration matrices gives $$\begin{aligned} W-W^\star ={}&HEH \\\\ &+(H-H^\star)A_C^\star H \\\\ &+H^\star A_C^\star(H-H^\star). \end{aligned}$$ Applying the triangle inequality and standard matrix-norm inequalities, $$\lVert W-W^{\star}\rVert_F \leq \lVert HEH\rVert_F + \lVert (H-H^{\star})A_C^{\star}H\rVert_F + \lVert H^{\star}A_C^{\star}(H-H^{\star})\rVert_F.$$ $$\lVert W-W^{\star}\rVert_F \leq \frac{\lVert E\rVert_F}{d_0} + \frac{2d_{\max}^{\star}}{\sqrt{d_0}} \lVert H-H^{\star}\rVert_F \leq \left( \frac{1}{d_0} + \frac{\sqrt{M}\\,d_{\max}^{\star}}{d_0^2} \right) \lVert E\rVert_F.$$ Finally, by Theorem 2, ‖E‖_F ≤ ‖L̂_C − L*_C‖_F ≤ c_G ε_X / n_min. we establish $$\lVert W-W^{\star}\rVert_F \leq \left( \frac{1}{d_0} + \frac{\sqrt{M}\\,d_{\max}^{\star}}{d_0^2} \right) \frac{c_G}{n_{\min}}\varepsilon_X.$$ The result establishes that, under the positive-degree condition & the reconstruction assumptions of Theorem 1, stability propagates from the global Laplacian through client-level coarsening & normalization to the final collaboration matrix W used for personalized aggregation. We added *Corollary 1* (extending Theorem 2), its proof in Appendix D.2, and a reference in Section 3.3. ---- ## Q1 and W1-part 3 We have extended our stability corollary to account for degree regularization using a fixed stabilizer $\gamma>0$. The resulting bound ensures finite perturbation sensitivity even for vanishing client degrees, with explicit dependence on $\gamma$. To account for small or zero client degrees, consider a fixed positive stabilizer $\gamma>0$ and define $$D_{C,\gamma}=D_C+\gamma I_M,\qquad D_{C,\gamma}^\star=D_C^\star+\gamma I_M.$$ The corresponding regularized collaboration matrices are $$W_\gamma=D_{C,\gamma}^{-1/2} A_CD_{C,\gamma}^{-1/2}, \qquad W_\gamma^\star=(D_{C,\gamma}^\star)^{-1/2} A_C^\star(D_{C,\gamma}^\star)^{-1/2}.$$ Then, without requiring strictly positive unregularized client degrees, we obtain $$\lVert W_{\gamma}-W_{\gamma}^{\star}\rVert_F \leq \left( \frac{1}{\gamma} + \frac{\sqrt{M}\\,d_{\max}^{\star}}{\gamma^2} \right) \frac{c_G\varepsilon_X}{n_{\min}}$$ Thus, the positive stabilizer ensures a finite stability bound even when some client degrees approach zero. --- ## Q2 and W2 To isolate the contribution of the *inferred client collaboration graph*, we conducted an additional controlled ablation on 5 data. We compared CoCo against *uniform affinities*, *randomly permuted affinities*, & *local-only training*. The backbone & local training were kept unchanged with the same personalization weight $\alpha$ used for the 3 collaboration-based variants. Table: Node classification acc (%) under different collaboration strategies. The CoCo acc are different here as they are run for single seed and different setting here. |Data| Local-only|Uniform |Permuted|CoCo| |-|-|-|-|-| |Cora| 68.70 | 75.60 | 74.90 | **79.00** | |Pub| 72.00 | 74.80 | 73.40 | **77.80** | |Squi| 31.76 | 37.37 | 36.45 | **38.31** | |Chame| 46.52 | 46.49 | 51.83 | **54.43** | |CS| 89.95 | 91.95 | 91.88 | **92.10** | These results highlight two important observations: 1. *Collaboration itself is beneficial*, as the collaboration-based variants generally outperform local-only training. 2. *The learned client relationships matter*, as CoCo consistently outperforms uniform & randomly permuted affinities under the same training setup. Thus, the improvements are not explained solely by exchanging model parameters or applying a generic collaboration mechanism. *The inferred client affinities provide useful information for selecting and weighting collaboration between clients*, directly supporting CoCo's central contribution. We will include this controlled ablation in the revised manuscript to make the contribution of the learned collaboration graph more explicit.
AuthorsOpenReview ↗

Appeal to the Reviewer

Dear Reviewer cQWe,

Thank you again for your detailed and thoughtful feedback on our submission. We have provided a point-by-point rebuttal in order to address the raised concerns.

As the rebuttal period is ending in a few days, we would be very grateful if you could kindly let us know whether any key concerns remain or if our clarifications address your main objections. If the rebuttal alleviates some of your worries, we would also appreciate it if you could consider updating your score accordingly.

Thank you for your time and consideration.

Sincerely,

Authors.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.