Introduction
Federated Learning (FL) has emerged as a powerful paradigm for collaborative model training without the need for raw data sharing. However, its application to graph-structured data—such as molecular structures, social networks, and protein interactions—is complicated by significant data heterogeneity. Standard FL algorithms, like FedAvg, often struggle when client data is non-Independent and Identically Distributed (non-IID), leading to slow convergence or degraded performance compared to local training. This paper introduces Graph Clustered Federated Learning (GCFL) and its enhanced version, GCFL+, to address these challenges by dynamically grouping clients based on their learning behaviors.
The Challenge of Graph Heterogeneity
Graph data presents unique challenges due to two-fold heterogeneity: structural differences (how nodes are connected) and feature differences (node attributes). In a federated setting, clients may hold graphs from entirely different domains. Despite these differences, real-world graphs often share macro-properties, such as long-tail degree distributions, which distinguish them from random graphs. This shared underlying structure suggests that cross-domain collaboration is possible if clients with compatible learning dynamics can be identified.
Methodology: GCFL and GCFL+
The core innovation of this work is the use of Graph Neural Network (GNN) gradients as proxies for data similarity. The authors provide theoretical evidence that GNN gradients encode structural and feature information.
Graph Clustered Federated Learning (GCFL)
GCFL dynamically clusters clients based on the similarity of their gradients. Instead of a single global model, the server maintains specialized models for each cluster. However, as shown in Figure 3, gradient norms can fluctuate significantly between communication rounds, making point-in-time snapshots noisy.
GCFL+: Time-Series Clustering
To mitigate the noise in individual gradient updates, GCFL+ tracks the sequence of gradient norms over multiple rounds. By applying Dynamic Time Warping (DTW) to these time-series, GCFL+ captures long-term learning patterns, resulting in more robust clustering that better reflects the underlying data compatibility between clients.
Experimental Results
The frameworks were evaluated on 13 benchmark datasets across molecular, protein, and social network domains.
Performance Gains
In a single-dataset setting (NCI1), GCFL+ achieved a 14.75% average performance gain over local training, benefiting 28 out of 30 clients. In contrast, standard FedAvg negatively impacted more than half of the clients. In multi-dataset scenarios with extreme heterogeneity, GCFL+ improved performance for 100% of the clients, whereas FedAvg failed for approximately 60% of them.
Heterogeneity Reduction
Post-clustering analysis, summarized in Figure 5, confirms that the proposed frameworks effectively reduce structural and feature heterogeneity within each cluster compared to the global population.
Conclusion
GCFL and GCFL+ offer a robust solution for federated graph classification by leveraging GNN gradients to navigate non-IID data. By clustering clients with similar learning trajectories, these frameworks enable effective collaboration even across diverse domains. Future work includes exploring formal privacy guarantees and extending the framework to cross-task learning scenarios.
Summary updated