CoCo: COllaborate via COarsening for Personalized Federated Graph Learning

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.