- 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
- 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.
- 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.
- 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
- 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.
- 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.
- 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.
-
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.
-
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.
-
Can the authors provide an end-to-end comparison of runtime, communication cost, and GPU memory against the strongest recent FGL baselines?
9 comments
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:
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 (%)
| Dataset | Anchor-DNA | Client-Recon | Full CoCo | Gain |
|---|---|---|---|---|
| CiteSeer | 76.92 | 77.58 | 79.87 | +2.29 |
| PubMed | 86.34 | 86.18 | 88.10 | +1.76 |
| Amazon-Photo | 83.47 | 83.33 | 92.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 , 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 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).
| Method | Cora | CiteSeer | PubMed | CS | Tolokers | Squirrel |
|---|---|---|---|---|---|---|
| CoCo | 1.5 | 1.2 | 1.2 | 1.6 | 1.3 | 1.0 |
| FedPub | 24.0 | 4.0 | 4.2 | 5.4 | 4.3 | 4.6 |
| FedGTA | 4.1 | 4.8 | 3.7 | 2.3 | 2.6 | 2.4 |
| FedDC | 1.8 | 1.9 | 1.8 | 1.6 | 1.3 | 1.4 |
| FedTGP | 6.0 | 5.2 | 4.0 | 4.3 | 2.3 | 2.7 |
| MOON | 2.7 | 2.8 | 3.2 | 2.4 | 1.9 | 1.8 |
| SCAFFOLD | 1.5 | 1.6 | 2.1 | 1.6 | 1.3 | 1.1 |
| FedTAD | 23.4 | 22.3 | 15.0 | 21.5 | 10.9 | 12.7 |
| FedSAGE+ | 14.2 | 12.9 | 35.3 | 490.4 | 543.5 | 356.8 |
| FedAux | 2589 | 2583 | 2999 | 3018 | 2949 | 2988 |
| FedSPA | 5.9 | 6.0 | 5.9 | 6.2 | 6.1 | 6.0 |
| FedSSA | 60.0 | 95.9 | 193.3 | 2519 | 258.7 | 214.4 |
| FedStruct | 4.9 | 4.9 | 7.9 | 11.1 | 16.9 | 12.0 |
| FedLAP | 18.6 | 20.1 | 61.6 | 65.5 | 60.4 | 33.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...
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.
| Dataset | Time (s) | GPU memory (MB) |
|---|---|---|
| Cora | 3.72 | 37.55 |
| CiteSeer | 4.96 | 86.65 |
| PubMed | 3.07 | 19.55 |
| Amazon-Photo | 4.32 | 24.66 |
| Coauthor-Physics | 9.41 | 186.97 |
| ogbn-arxiv | 2.41 | 12.02 |
| Chameleon | 3.39 | 44.27 |
| Squirrel | 2.86 | 32.75 |
| Coauthor-CS | 5.76 | 83.21 |
| Tolokers | 2.62 | 12.07 |
| Amazon-Ratings | 4.96 | 20.89 |
| Questions | 5.75 | 42.93 |
| 3.75 | 32.21 | |
| ogbn-products | 31.36 | 325.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: where 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.
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.
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.
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...