Federated Graph Classification over Non-IID Graphs

Han Xie; Jing Ma; Li Xiong; Carl Yang

Source-linked AI summary

Federated Graph Classification over Non-IID Graphs

Han Xie, Jing Ma, Li Xiong, Carl Yang

arXiv:2106.13423v5Jun 25, 2021cs.LGcs.AIcs.DCstat.ML

TL;DR

Graph federated learning must exploit shared graph properties while handling non-IID structures and node features across local systems. The paper introduces GCFL, which clusters clients using GNN gradients, and GCFL+, which uses dynamic time warping over gradient sequences; experiments show GCFL+ consistently outperforms straightforward baselines.

Problem
Graph datasets share useful properties but remain heterogeneous in graph structures and node features, creating a challenge for collaborative graph classification across clients.
Method
GCFL dynamically clusters clients using GNN gradients, while GCFL+ improves clustering by comparing gradient sequences with dynamic time warping.
Results
GCFL+ effectively and consistently outperforms straightforward baselines across cross-dataset and cross-domain graph-classification settings.
Takeaways & Limitations
Clustered federated learning can reduce structure and feature heterogeneity among graph clients while supporting collaborative model training.
Takeaways & Limitations
The experiments omit a global-model baseline because datasets come from various domains with divergent tasks.

Abstract

from arXiv · show

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.

1 Introduction

Real-world graphs share statistically significant properties, yet remain non-IID in structures and node features across clients. The paper proposes clustered federated learning frameworks that dynamically address this heterogeneity and reports consistently improved performance.

Graph classification applies graph kernels and GNNs to predict graph-level labels in domains including molecules, proteins, social communities, and geographic networks.
Real-world graphs across four domains share properties statistically significant compared with Erdős–Rényi random graphs, motivating federated graph classification across datasets and domains.
Structure and node-feature distributions can diverge among graphs, making cross-dataset clients non-IID and potentially causing naïve FedAvg to fail or backfire.
GCFL dynamically clusters clients using GNN gradients without prior knowledge, theoretically targeting clusters with reduced structure and feature heterogeneity.
GCFL+ uses gradient sequences and dynamic time warping because gradients fluctuate across communication rounds and last-round clustering can ignore client behavior.
Extensive experiments show GCFL+ can effectively and consistently outperform straightforward baselines in cross-dataset and cross-domain graph classification.

2 Related works

Prior work established federated learning for decentralized data and explored graph-based federated settings, but graph federated learning remains comparatively limited.

Federated learning coordinates collaborative model training across remote devices holding distributed data, with FedAvg as a foundational aggregation approach.
Research on federated learning for graphs includes graph-structured client modeling, cross-domain heterogeneity, and GNN-based modeling of relationships among clients.

3 Preliminaries

GNNs learn graph representations through message propagation, neighborhood aggregation, and graph-level readout. FedAvg provides the baseline federated procedure by averaging client updates weighted by local data sizes.

GNNs use graph structure and node features to learn node or graph embeddings through message propagation and neighborhood aggregation.
Graph-level readout aggregates node embeddings into a single vector for graph classification or regression.
FedAvg aggregates updated client parameters and redistributes the averaged model for another round of local training.
The FedAvg aggregation weights each client update by its local sample count relative to the total number of samples.

4 The GCFL framework

GCFL addresses non-IID graph structures and features by dynamically clustering clients and training cluster-specific graph models. Its gradient-based clustering is supported theoretically because GNN gradients reflect graph structure, features, and task information.

4.1 Non-IID structures and features across clients: Graph structures and features exhibit heterogeneity within datasets, domains, and across domains, making naïve federated learning potentially ineffective.Structure heterogeneity complicates learning universally important patterns, while feature heterogeneity complicates learning universally appropriate message propagation functions.
4.2 Problem formulation: GCFL jointly clusters clients with similar graph structures and features, then applies FedAvg among clients within each cluster.The server dynamically maintains cluster-wise models and assignments during federated training.
4.3 Technical design: GNN parameters and gradients can reflect graph structure and feature information, enabling gradient-based client clustering without additional prior knowledge.Theoretical analysis uses SGC propositions and Bourgain embeddings to bound weight differences by structure or feature differences; gradients are also analyzed for task heterogeneity.
4.3 Technical design: GCFL dynamically stops general federated training and splits heterogeneous clusters using gradient norms, cosine similarities, and graph minimum cuts.The top-down bi-partitioning mechanism uses criteria based on mean and maximum transmitted-gradient norms, then applies Stoer–Wagner minimum cut.

5 GCFL+: improved GCFL based on observation sequences of gradients

GCFL+ improves clustering by using sequences of fluctuating gradient norms rather than only the latest gradients. Dynamic time warping compares these sequences to capture longer-range client behavior and produce more homogeneous clusters.

5.1 Fluctuation of gradient norms: Gradient norms fluctuate across communication rounds and differ in scale across clients, indicating diverse updating directions and distances.These observations reflect structure and feature heterogeneity in the federated graph-classification setting.
5.2 Technical design: GCFL+ clusters clients using tracked sequences of gradient norms and dynamic time warping instead of relying only on the last transmitted gradients.The server maintains a multi-variant time-series matrix, updates it each round, and computes pairwise sequence distances when clustering criteria are met.
5.2 Technical design: At round 118, GCFL+ clusters using a gradient sequence of length 10, capturing longer-range client behavior and producing more homogeneous clusters.The sequence-based distance matrix supports bi-partitioning of clusters that satisfy the clustering criteria.

6 Experiments

Experiments across single- and multi-dataset federated graph-classification settings evaluate GCFL and GCFL+ against standard baselines. The frameworks improve client performance, reduce within-cluster heterogeneity, and achieve convergence comparable to FedProx.

Experimental setup: Experiments use 13 graph-classification datasets spanning molecule, protein, and social-network domains, with single- and multi-dataset client partitions.The multi-dataset setting includes single-domain MOLECULES and cross-domain BIOCHEM and MIX groups.
Single-dataset results: 13.27% and 14.75% are GCFL and GCFL+ average performance gains over self-train on NCI1 across 30 clients.Both frameworks help 10–14 more clients than FedAvg and FedProx in this setting.
Single-dataset results: 7.29% and 7.81% are GCFL and GCFL+ average performance gains over self-train on PROTEINS across 10 clients.On IMDB-BINARY, both GCFL variants improve all 10 clients, whereas FedAvg and FedProx fail to help 5/10 and 4/10 clients.
Multi-dataset results: 1.7%–2.7% are the improvements of GCFL and GCFL+ over self-train across multi-dataset groups.GCFL+ improves twice as many clients as FedAvg in all three groups and improves all MOLECULES clients.
Hyper-parameters: Smaller ε2 makes clustering more likely, while ε1 checks proximity to a stationary point; feasible-range variation has little performance effect.Setting ε2 too small can create many small clusters or single-client clusters.
Cluster analysis: GCFL and GCFL+ significantly reduce structure and feature heterogeneity within clusters, especially for multiple-dataset settings.Feature heterogeneity decreases only slightly in one-dataset settings because clients’ features already occupy the same space.
Convergence analysis: GCFL, GCFL+, and FedProx converge at similar rates, and all reach lower testing loss than FedAvg.Training curves report averages with standard deviations across clients.

7 Conclusion

The paper introduces cross-dataset and cross-domain federated graph classification for structure- and feature-non-IID graphs. GCFL and GCFL+ enable collaborative GNN training without direct data sharing, while privacy and adversarial issues remain future work.

Conclusion: GCFL and GCFL+ support collaborative graph-classification neural-network training among data owners holding structure- and feature-non-IID graphs.The frameworks avoid direct data sharing.
Conclusion: Data privacy and adversarial scenarios are not carefully studied, though encryption and malicious-client clustering are identified as possible future directions.The authors present the work as a first trial in this setting.

A More Motivating Examples and Analysis

The motivating analysis connects graph properties to classification signals and examines when cross-dataset collaboration helps or harms. It also illustrates possible social-network and multi-app deployment scenarios.

Motivating examples: High clustering coefficients in social networks indicate triangle patterns that may provide signals for graph classification.The passage contrasts these patterns with random graphs whose prominent patterns may instead be subtrees or long edges.
Additional analysis: Federated learning on another graph dataset initially benefits PROTEINS more as structure heterogeneity increases, but performance degenerates when heterogeneity becomes too large.The analysis uses one-hot degree features to isolate structure heterogeneity.
Example scenarios: Separate-country social-network branches and departments operating healthcare and social-media apps are presented as scenarios where data cannot be directly shared.The latter scenario assumes common ownership can facilitate federated collaboration.

B.1 Proof of Proposition 4.1

The proof bounds how changes in graph structure affect learned weights in the simplified graph-convolution setting. The resulting bound depends on the fixed node features and graph structure.

Proof strategy: The proof represents graph-structure variation as a perturbation and bounds its effect on the learned weights through Laplacian and embedding differences.Intermediate steps invoke bounds on the graph embedding and matrix inverses.
Proof conclusion: With trained SGC, fixed feature matrix X and graph structure L bound the weight difference between the original and perturbed graphs.This is the proof’s stated final dependence.

B.2 Proof of Proposition 4.2

The proof bounds how perturbations in graph features, structures, embeddings, and tasks affect trained weights. For fixed feature and graph-structure matrices, the resulting SGC weight difference is bounded.

Proof of Proposition 4.2: Feature perturbations are represented as bounded differences between X and X′, with the corresponding inverse-matrix difference bounded through ||XEX||².The proof introduces EX and δX to control the effect of changing graph features.
Proof of Proposition 4.2: Bourgain’s theorem is used to bound the difference between graph embeddings Y and Y′ under structural changes.The embedding perturbation is then incorporated into the weight-difference bound.
Proof of Proposition 4.2: With SGC fixing X and L, the proof concludes that the weight difference is bounded.This conclusion applies after the feature and graph-structure inputs are fixed.
Proof of Proposition 4.2: A separate expression represents weight differences arising from training on different tasks.The proof also gives a transformed-embedding bound using Bourgain’s theorem.

C Dataset Details

The appendix points to a dataset-statistics table and identifies Table 5 as the source of dataset details.

Dataset Details: Dataset details are provided in Table 5.The passage explicitly directs readers to the table for dataset information.
Dataset Details: The dataset appendix therefore serves as a reference for the datasets used in the study.This follows directly from the appendix statement linking the dataset details to Table 5.
Dataset Details: Table 5 is labeled as reporting the statistics of the datasets.The supplied table caption does not enumerate the individual statistics.

D More Detailed Experiment Results

Additional experiments examine client overlap, node-feature choices, and gradient-sequence standardization. The results show improvements across several settings, while standardization and non-standardization yield similar average gains.

Overlapping versus non-overlapping: Overlapping data partitions still allow GCFL and GCFL+ to improve performance for clients.Figure 6 compares performance-gain distributions under overlapped and non-overlapped partitions.
Original node features versus one-hot degree features: GCFL and GCFL+ consistently improve performance when one-hot degree features replace original node features.The gains decrease in the multi-dataset setting when only one-hot node degrees are used, possibly because feature heterogeneity decreases.
Original node features versus one-hot degree features: Feature gains decrease in the multi-dataset setting with one-hot node degrees, possibly because this representation reduces feature heterogeneity.The passage identifies Figure 7c as the setting where the decrease occurs.
Standardized versus non-standardized multi-variant time-series matrix: GCFL+ standardizes each gradient-sequence row before calculating the distance matrix, removing scale while retaining fluctuation trends.The standardization uses Q′(i, :) = Q(i, :)/std(Q(i, :)).
Standardized versus non-standardized multi-variant time-series matrix: Average performance gains are similar with standardized and non-standardized gradient-sequence matrices.Figure 8 reports the comparison for GCFL+ across the oneDS and multiDS settings.