Source-linked AI summary
Federated Learning on Non-IID Graphs via Structural Knowledge Sharing
Yue Tan, Yixin Liu, Guodong Long, Jing Jiang, Qinghua Lu, Chengqi Zhang
TL;DR
Non-IID graph data make it difficult for FGL methods to share knowledge across heterogeneous domains while learning generalized encoders. FedStar explicitly separates structural and feature information, shares the structure encoder across clients, and learns feature encoders locally. Experiments report consistent superiority over state-of-the-art methods across varied non-IID FGL scenarios.
Problem
Heterogeneous graph domains complicate shared knowledge capture because conventional FGL encodes structure together with features, while structural properties may be shared across domains.
Method
FedStar uses structure embeddings and a feature-structure decoupled GNN, sharing the structure encoder across clients while learning feature-based representations locally.
Results
FedStar consistently outperforms state-of-the-art methods across various cross-dataset and cross-domain non-IID FGL scenarios.
Takeaways & Limitations
FedStar enables clients from different domains to learn domain-agnostic structural knowledge globally while keeping feature-based node representation learning personalized.
Takeaways & Limitations
FedStar is agnostic to the construction of structure embeddings; exploring additional types such as Laplacian eigenvectors and distance-based embeddings is left for future work.
Abstract
from arXiv · showhide
Graph neural networks (GNNs) have shown their superiority in modeling graph data. Owing to the advantages of federated learning, federated graph learning (FGL) enables clients to train strong GNN models in a distributed manner without sharing their private data. A core challenge in federated systems is the non-IID problem, which also widely exists in real-world graph data. For example, local data of clients may come from diverse datasets or even domains, e.g., social networks and molecules, increasing the difficulty for FGL methods to capture commonly shared knowledge and learn a generalized encoder. From real-world graph datasets, we observe that some structural properties are shared by various domains, presenting great potential for sharing structural knowledge in FGL. Inspired by this, we propose FedStar, an FGL framework that extracts and shares the common underlying structure information for inter-graph federated learning tasks. To explicitly extract the structure information rather than encoding them along with the node features, we define structure embeddings and encode them with an independent structure encoder. Then, the structure encoder is shared across clients while the feature-based knowledge is learned in a personalized way, making FedStar capable of capturing more structure-based domain-invariant information and avoiding feature misalignment issues. We perform extensive experiments over both cross-dataset and cross-domain non-IID FGL settings, demonstrating the superiority of FedStar.
Introduction
Federated graph learning applies privacy-preserving collaborative training to decentralized graph data, but heterogeneous non-IID graphs make shared representation learning difficult. FedStar addresses this by sharing structural knowledge globally while learning feature-based knowledge locally.
- Graph neural networks model graph-structured data in applications including recommender systems, drug discovery, and traffic.
- Federated learning lets clients collaboratively train shared or personalized models without sharing local data.
- Non-IID graph data span diverse feature spaces and connection rules, complicating collaboration across domains such as social networks and molecules.
- Existing FGL methods implicitly encode structure with features, making feature heterogeneity hinder structural knowledge capture and communication.
- FedStar explicitly represents shared structure, decouples structure and feature encoders, and shares domain-agnostic structural information while learning personalized feature representations.
- FedStar studies structural knowledge sharing and consistently outperforms baselines across four cross-dataset/domain non-IID settings.
Related Work
Related work covers GNN message passing, federated learning under heterogeneous client data, and federated graph learning across inter-graph, intra-graph, and graph-structured settings.
- Graph Neural Network: GNNs learn node representations by aggregating and transforming embeddings from each node and its neighbors.
- Federated Learning: Federated learning performs decentralized collaborative training, with FedAvg periodically averaging client model parameters at a central server.
- Federated Learning: Non-IID federated learning addresses diverse client label or feature distributions using approaches including clustering and meta-learning.
- Federated Graph Learning: FGL studies are categorized as inter-graph, intra-graph, and graph-structured federated graph learning.
Preliminaries
The preliminaries describe GNN message passing, graph-level readout, and federated optimization. Standard parameter sharing can perform poorly under client distribution differences, motivating personalization in FGL.
- Graph Neural Networks: GNN layers iteratively update each node representation by aggregating representations from its neighbors.
- Graph Neural Networks: Graph-level representations are formed by applying readout functions such as summation or mean pooling to node representations.
- Federated Learning: In federated learning, each client owns a private dataset and contributes to a global objective weighted by its number of instances.
- Federated Learning: FedAvg periodically averages client parameters and returns the averaged model, whereas personalization allows client models to better fit local data.
- Federated Graph Learning: In FGL, client models and datasets correspond to GNN parameters and graph datasets, with classification commonly optimized using cross-entropy loss.
Methodology
FedStar separates structural and feature-based knowledge in a two-channel GNN, then shares only the structure encoder across clients. It represents local and global graph patterns explicitly so structural knowledge can generalize across heterogeneous domains while feature learning remains personalized.
- Structure Embedding Initialization: FedStar introduces structure embeddings to represent universal graph properties independently from heterogeneous node features.The embeddings serve as features during message aggregation, allowing structure information to be learned separately.
- Structure Embedding Initialization: Degree-based structure embeddings encode local structure using one-hot vertex degrees and provide a computationally friendly initialization.Degree is available across graph domains, and degree distributions share structural regularities such as power-law behavior.
- Structure Embedding Initialization: Random-walk structure embeddings capture global node roles and neighborhood distributions across multiple hops.RWSE complements degree-based embeddings by modeling global structural properties through random-walk diffusion.
- Structure Embedding Initialization: FedStar concatenates degree-based and random-walk embeddings, while remaining compatible with other structure-related embedding constructions.The paper identifies Laplacian eigenvectors and distance-based embeddings as possible future alternatives.
- Feature-Structure Decoupled GNN: The feature-structure decoupled GNN uses parallel channels: one learns from raw features, while the other propagates explicitly initialized structural information.The channels are connected so shared structural knowledge can provide additional information for feature learning.
- Structural Knowledge Sharing: FedStar decouples each client model into personalized feature parameters and structure parameters that are aggregated across clients.The server aggregates structure encoders, returns the global encoder to clients, and clients continue local training with personalized feature encoders.
Experiments
Experiments evaluate FedStar across cross-dataset and cross-domain non-IID settings, comparing it with six baselines and testing convergence, component sharing, structure embeddings, local epochs, and client scale. FedStar consistently achieves the strongest reported performance and benefits from sharing structural knowledge while personalizing feature-based learning.
- Experimental Setup: Experiments use 16 graph-classification datasets from four domains to construct one cross-dataset and three cross-domain non-IID settings.The settings include CHEM, BIO-CHEM, BIO-CHEM-SN, and BIO-SN-CV.
- Performance Comparison: FedStar outperforms Local, FedAvg, FedProx, FedPer, FedSage, and GCFL by a notable margin across the four non-IID settings.FedAvg and FedProx can underperform Local, while FedPer, FedSage, and GCFL improve performance in many cases.
- Convergence Analysis: Across all four non-IID settings, FedStar dominates average test accuracy and converges faster than the compared methods.The curves report mean accuracy and standard deviation over five random runs.
- Effects of Decoupling and Sharing Mechanisms: Feature-structure decoupling improves performance by 0.5%-2.4%, while sharing only the structure encoder achieves the best result.Sharing all parameters or the feature encoder can degrade performance relative to pure local training.
- Effects of Different Structure Embeddings: Concatenating degree-based and random-walk-based structure embeddings achieves the best performance in all three evaluated non-IID settings.Degree-based structure embedding contributes more than random-walk-based embedding when used alone, although the latter remains beneficial.
- Scalability and Communication Efficiency: FedStar benefits more from increasing local epochs and outperforms FedAvg and GCFL as the CHEM client count grows from 7 to 84.With more clients, performance first drops from greater divergence and later improves as each local task becomes easier.
Conclusion
FedStar addresses non-IID federated graph learning through structural knowledge sharing. It explicitly represents structure with embeddings and a decoupled encoder, shares structural knowledge globally, personalizes feature learning, and consistently outperforms state-of-the-art methods.
- Conclusion: FedStar uses structure embeddings and a feature-structure decoupled GNN to capture structural knowledge without feature-based interference.The structure encoder is shared across clients, while feature-based node representation learning remains personalized.
- Conclusion: FedStar enables clients from different domains to learn domain-agnostic structural knowledge globally while keeping feature learning personalized.This design targets non-IID federated graph learning scenarios.
- Conclusion: Experimental results show that FedStar consistently outperforms state-of-the-art methods across various non-IID FGL scenarios.
A Experimental Details
The appendix describes hyperparameter selection through a small validation-set grid search, with selected insensitive hyperparameters fixed for the experiments.
- Experimental Details: Important hyperparameters are selected through a small grid search on the validation dataset.
- Experimental Details: Remaining insensitive hyperparameters are kept fixed after selection.
- Experimental Details: The search varies k1, k2, learning rate, and weight decay across five candidate values each.The searched dimensions are degree-based and random-walk-based structure embeddings, learning rate, and weight decay.
A.2 Details of the Baseline Methods
FedStar is compared with six baselines spanning local training, standard federated averaging, heterogeneity-aware FL, personalized FL, and two FGL methods.
- Details of the Baseline Methods: Local trains independently on each client without communication, whereas FedAvg exchanges all learnable parameters for server aggregation.
- Details of the Baseline Methods: FedProx extends FedAvg with a regularization term weighted by µ, set to 0.01 in the experiments.
- Details of the Baseline Methods: FedPer shares only part of the learnable parameters, while FedSage and GCFL are specialized FGL baselines.
A.3 Data Splitting Details
The experiments use four non-IID graph-classification settings: one cross-dataset setting and three cross-domain settings. Detailed dataset statistics are provided for CHEM, BIO, SN, and CV.
- Four non-IID settings are considered: CHEM, BIO-CHEM, BIO-CHEM-SN, and BIO-SN-CV.CHEM is cross-dataset, while the other three are cross-domain settings.
- CHEM, BIO-CHEM, and BIO-CHEM-SN follow empirical studies, whereas BIO-SN-CV is proposed in this work.
- All datasets are publicly available graph-classification datasets.
- Detailed statistics are reported separately for CHEM, BIO, SN, and CV across the non-IID settings.These statistics are listed in Tables 5–8.
A.4 Model Architecture
FedStar uses separate structure and feature encoders at each client. The structure encoder is a three-layer GCN, while the feature encoder is a three-layer GIN.
- The structure encoder is implemented as a three-layer GCN, and the feature encoder as a three-layer GIN.
- The client model architecture contains eight layers in total.
- Table 9 identifies the components shared across clients and defines FC as a fully connected layer.It also specifies n_feat as the node-feature dimension and n_class as the number of graph classes at a client.
B Addition Experimental Results
Additional experiments evaluate FedStar across GNN backbones and describe its federated optimization procedure. The results report stable, considerable performance across different encoder choices, supporting backbone universality.
- Additional experimental results: FedStar maintains stable and considerable performance with various GNNs used as feature and structure encoders.This experiment is conducted on the CHEM setting.
- Additional experimental results: Using different GNN backbones for feature and structure encoders verifies FedStar’s universality across GNN architectures.
- FedStar algorithm: The server communicates the initial structure encoder to all clients before local training rounds begin.
- FedStar algorithm: During each round, clients perform local updates in parallel and the server updates the structure encoder by aggregating client encoders.
- FedStar algorithm: Each client initializes its local structure encoder from the server encoder and returns its locally updated structure parameters.