Federated Graph Classification over Non-IID Graphs

Han Xie, Jing Ma, Li Xiong, Carl Yang

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.

Gradient norm fluctuations in GCFL and GCFL+ across different datasets.

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.

Average structural and feature heterogeneity across different dataset combinations.

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

BibTeX
@inproceedings{xie2021federated,
  author = {Han Xie and Jing Ma and Li Xiong and Carl Yang},
  title = {{Federated Graph Classification over Non-IID Graphs}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2021},
  url = {https://openreview.net/forum?id=vvTU7SuPfC},
}
Figure