Federated Graph Classification over Non-IID Graphs

Han Xie, Jing Ma, Li Xiong, Carl Yang

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 standard FedAvg actually 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, FedAvg failed 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

Abstract

Federated learning has emerged as an important paradigm for training machine learning models in different domains. For graph-level tasks such as graph classification, graphs can also be regarded as a special type of data samples, which can be collected and stored in separate local systems. Similar to other domains, multiple local systems, each holding a small set of graphs, may benefit from collaboratively training a powerful graph mining model, such as the popular graph neural networks (GNNs). To provide more motivation towards such endeavors, we analyze real-world graphs from different domains to confirm that they indeed share certain graph properties that are statistically significant compared with random graphs. However, we also find that different sets of graphs, even from the same domain or same dataset, are non-IID regarding both graph structures and node features. To handle this, we propose a graph clustered federated learning (GCFL) framework that dynamically finds clusters of local systems based on the gradients of GNNs, and theoretically justify that such clusters can reduce the structure and feature heterogeneity among graphs owned by the local systems. Moreover, we observe the gradients of GNNs to be rather fluctuating in GCFL which impedes high-quality clustering, and design a gradient sequence-based clustering mechanism based on dynamic time warping (GCFL+). Extensive experimental results and in-depth analysis demonstrate the effectiveness of our proposed frameworks.
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},
}

Loading related content...

Figure