TL;DR
Federated learning on graph data struggles when clients have highly heterogeneous (non-IID) graph structures and features. This paper introduces GCFL and GCFL+, novel clustered federated learning frameworks that dynamically group clients based on the sequence of their Graph Neural Network (GNN) gradients. By clustering clients with similar gradient behaviors, the frameworks significantly improve collaborative graph classification across diverse datasets and domains without sharing raw data.
What Problem Does This Paper Address?
Federated Learning (FL) allows multiple clients to collaboratively train a model without sharing their private data. However, standard FL algorithms like FedAvg assume that data across clients is somewhat similar (Independent and Identically Distributed, or IID). When data is highly heterogeneous, standard FL can fail, causing models to converge slowly or even perform worse than if clients just trained on their own data.
This problem is especially severe for graph data (e.g., molecular structures, social networks). Graph heterogeneity is two-fold: clients can differ in graph structure (how nodes are connected) and node features (the attributes of the nodes). The authors tackle the challenge of performing effective federated graph classification when clients hold highly non-IID graphs, even spanning entirely different domains.
Methods
The authors propose a Graph Clustered Federated Learning (GCFL) framework. Instead of forcing one global model on everyone, the server dynamically groups clients into clusters and trains a specialized model for each cluster.
- GCFL: The server clusters clients based on the gradients they send during training. The authors provide mathematical proofs showing that the gradients of a GNN inherently encode the structural and feature differences of the underlying graphs. Therefore, clients with similar gradients likely have similar graph data.
- GCFL+ (The Improved Version): The authors observed that gradient norms fluctuate wildly from round to round, meaning a single snapshot of gradients is noisy and can lead to poor clustering. To fix this, GCFL+ tracks a time-series of gradient norms for each client over multiple communication rounds. It then uses Dynamic Time Warping (DTW) to measure the similarity between these gradient sequences. This captures the long-term learning behavior of clients, resulting in much more robust and accurate clustering.
Datasets
The authors evaluated their frameworks on 13 standard graph classification benchmark datasets spanning three distinct domains:
- Molecules: MUTAG, BZR, COX2, DHFR, PTC_MR, AIDS, NCI1
- Proteins: ENZYMES, DD, PROTEINS
- Social Networks: COLLAB, IMDB-BINARY, IMDB-MULTI
They tested two main settings: distributing a single dataset across multiple clients, and distributing multiple different datasets (sometimes from mixed domains) across clients.
Key Insights and Ideas
- Real-world graphs share universal traits: Despite coming from vastly different domains (e.g., proteins vs. social networks), real-world graphs share macro-properties (like long-tail degree distributions) that differ significantly from random graphs. This shared underlying structure is what makes cross-domain federated learning possible in the first place.
- Gradients are excellent structural proxies: You don't need to see a client's raw graph data to know it's different from yours; the GNN gradient tells you. The theoretical proof that GNN gradients are bounded by structure/feature differences is a clever justification for gradient-based clustering.
- Time-series clustering beats point-in-time: Because FL gradients fluctuate as models update, taking a snapshot at one communication round is easily misled by noise. Treating gradient norms as a sequence and using DTW is a highly effective way to find truly compatible clients.
- Cross-domain synergy is real: Surprisingly, the clustering algorithm sometimes grouped datasets from entirely different domains together (e.g., social networks with proteins), and these clients were actually able to mutually benefit each other's performance.
Key Results
- Single-Dataset Setting: On the NCI1 dataset distributed across 30 clients, GCFL+ achieved a 14.75% average performance gain over clients training locally (
self-train). Furthermore, GCFL+ improved performance for 28 out of 30 clients, whereas standardFedAvgactually hurt performance for more than half of them. - Multi-Dataset Setting: In a highly heterogeneous setup where 7 clients each held a completely different molecular dataset, GCFL+ improved the performance of 100% of the clients. In contrast,
FedAvgfailed to improve ~60% of the clients due to the severe non-IIDness. - Heterogeneity Reduction: Post-clustering analysis confirmed that GCFL+ successfully grouped clients into clusters with significantly lower structural and feature heterogeneity compared to the global pool.
Limitations and Future Work
- Privacy and Security: While FL inherently keeps raw data on local devices, the paper does not deeply explore formal privacy guarantees (like differential privacy or secure aggregation) to prevent gradient-leakage attacks. It also does not explicitly test against adversarial/malicious clients.
- Future Work: The authors suggest extending this framework to cross-task graph-level federated learning, where clients might not just have different data, but are trying to predict entirely different types of labels. They also note that integrating encryption mechanisms is a logical next step for real-world deployment.
Summary updated