PaperlayerView exact revision on arXiv

Source-linked AI summary

Subgraph Federated Learning with Missing Neighbor Generation

Ke Zhang, Carl Yang, Xiaoxiao Li, Lichao Sun, Siu Ming Yiu

arXiv:2106.13430v6cs.LGcs.SI

TL;DR

The paper addresses how to train a globally applicable node classifier from biased, distributed subgraphs without sharing raw graph data, especially when cross-subgraph links are missing. It proposes FedSage, which combines GraphSage with FedAvg, and FedSage+, which adds missing-neighbor generation; both outperform local classifiers across four real-world datasets.

  • Problem

    Distributed subgraphs may be small, biased, heterogeneous, and missing cross-subgraph links, creating challenges for learning a globally applicable graph model without raw-data sharing.

  • Method

    FedSage trains GraphSage with FedAvg across local subgraphs, while FedSage+ jointly trains a missing neighbor generator to mend incomplete neighborhoods.

  • Results

    Both models outperform locally trained classifiers in all tested scenarios across four real-world datasets, with FedSage+ further improving over FedSage.

  • Takeaways & Limitations

    Federated training can produce a global graph classifier, and missing-neighbor generation further addresses information loss from absent cross-subgraph links.

  • Takeaways & Limitations

    FedSage incurs additional communication costs and potential privacy concerns, motivating future work on communication reduction and rigorous privacy protection.

Abstract

from arXiv · show

Graphs have been widely used in data mining and machine learning due to their unique representation of real-world objects and their interactions. As graphs are getting bigger and bigger nowadays, it is common to see their subgraphs separately collected and stored in multiple local systems. Therefore, it is natural to consider the subgraph federated learning setting, where each local system holds a small subgraph that may be biased from the distribution of the whole graph. Hence, the subgraph federated learning aims to collaboratively train a powerful and generalizable graph mining model without directly sharing their graph data. In this work, towards the novel yet realistic setting of subgraph federated learning, we propose two major techniques: (1) FedSage, which trains a GraphSage model based on FedAvg to integrate node features, link structures, and task labels on multiple local subgraphs; (2) FedSage+, which trains a missing neighbor generator along FedSage to deal with missing links across local subgraphs. Empirical results on four real-world graph datasets with synthesized subgraph federated learning settings demonstrate the effectiveness and efficiency of our proposed techniques. At the same time, consistent theoretical implications are made towards their generalization ability on the global graphs.

1 Introduction

The paper introduces subgraph federated learning for training globally applicable graph mining models from distributed, biased subgraphs without sharing raw graph data. FedSage combines GraphSage with FedAvg, while FedSage+ generates missing neighbors across subgraphs; experiments show both outperform local classifiers.

  • Distributed subgraphs can have heterogeneous feature and structure distributions, making locally trained models potentially overfit and miss the global distribution.
  • FedSage trains an inductive, scalable GraphSage model with FedAvg across multiple local subgraphs.
  • Cross-subgraph links contain neighborhood information but are not directly captured by data owners.
  • FedSage+ adds a missing neighbor generator, mends each local subgraph with generated neighbors, and then applies FedSage.
  • Both proposed models outperform locally trained classifiers across experiments on four real-world datasets with different numbers of data owners.

2 Related works

Prior federated learning methods address collaborative learning without raw-data sharing, but existing graph FL methods do not fully match the distributed subgraph setting. This work targets globally applicable node classification with missing cross-subgraph edges.

  • Federated learning: Federated learning collaboratively trains models on siloed data through local updating and global aggregation without sharing raw data.
  • Federated learning: Meta-learning seeks models that adapt to local tasks, whereas this work seeks a generalizable model for a global task across diverse data owners.
  • Federated graph learning: Existing graph-level federated learning schemes are inapplicable to the distributed subgraph system considered here.
  • Federated graph learning: The paper considers distributed subgraphs with missing cross-subgraph edges and learns a globally applicable node classifier through federated learning.

3 FedSage

FedSage uses FedAvg to collaboratively train a shared GraphSage node classifier on isolated local subgraphs without raw graph-data sharing. The resulting classifier is intended to avoid being limited or biased toward any single owner, although incomplete neighborhoods constrain global-query coverage.

  • 3.1 Subgraphs Distributed in Local Systems: The system partitions a global graph among a server and M data owners, with each owner holding a distributed subgraph Gi.
  • 3.1 Subgraphs Distributed in Local Systems: Cross-owner edges may exist in the global graph but are absent from both endpoint owners’ stored edge sets.
  • 3.2 Collaborative Learning on Isolated Subgraphs: FedSage fixes GraphSage as the node classifier and trains it with the efficient FedAvg framework.
  • 3.2 Collaborative Learning on Isolated Subgraphs: Each owner performs local updates, the server averages the latest parameters, and the averaged model is broadcast for another training round.
  • 3.2 Collaborative Learning on Isolated Subgraphs: After ec epochs, the system obtains a global classifier not limited or biased toward queries from any specific data owner.
  • 3.2 Collaborative Learning on Isolated Subgraphs: Incomplete queried ego-graphs restrict FedSage from capturing the global query distribution when cross-subgraph links are missing.

4 FedSage+

FedSage+ augments FedSage with NeighGen, which learns to reconstruct missing neighbors and their features from impaired local graphs. Federated training exposes the generator to diverse neighborhood information while preserving the no-raw-data-sharing setting.

  • FedSage+ jointly trains a missing neighbor generator and GraphSage for subgraph federated learning with missing links.
  • 4.1 Missing Neighbor Generator (NeighGen): NeighGen encodes nodes with GraphSage, predicts missing-neighbor counts, and generates feature vectors for those neighbors.
  • 4.2 Training NeighGen: Local training randomly holds out nodes and related links, trains NeighGen on the impaired graph, and mends the graph with generated neighbors.
  • 4.2 Training NeighGen: Local graph mending acts as data augmentation, while federated NeighGen training targets missing neighbors across distributed subgraphs.
  • 4.3 Federated Training of NeighGen: Directly averaging NeighGen weights can reduce its ability to generate diverse neighbors from different subgraphs.
  • 4.3 Federated Training of NeighGen: The federated procedure transmits embeddings and locally computed gradients rather than raw graph data, while preserving local encoder components.

5 Experiments

Experiments evaluate FedSage and FedSage+ on four real-world datasets partitioned into distributed subgraphs, using global node-classification accuracy and comparisons with centralized and local baselines. FedSage+ improves over local training and reduces the accuracy gap to the centralized upper bound, while studies examine hyperparameters, label distributions, convergence, and runtime.

  • Datasets and experimental settings: Four real-world datasets are partitioned into similarly sized subgraphs using Louvain clusters with 3, 5, or 10 data owners.The datasets are Cora, Citeseer, PubMed, and MSAcademic.
  • Datasets and experimental settings: Node classification accuracy is measured on global-graph testing queries; global-model scores average five repetitions, while local-model scores also average across local models.
  • Overall performance: Federated classifiers outperform locally trained classifiers, and FedSage+ provides further gains over FedSage, especially when graphs are relatively sparse.The results associate the additional gains with addressing missing cross-subgraph neighbors through NeighGen.
  • Hyper-parameter studies: The best hyperparameter settings are generally around α=1 and moderate hiding portions; h values that are too small or too large degrade learning.The tested missing-edge range is [3.4%, 27.8%], helping explain why h=15% often boosts FedSage+ performance.
  • Training curves and runtime: On Cora with five data owners, FedSage and FedSage+ converge with rapidly improving testing accuracy, add no observable runtime over each other, and take slightly longer than GlobSage.The comparison tracks testing accuracy, loss convergence, and runtime over 100 epochs.

6 Implications on Generalization Bound

The paper analyzes GNTK generalization error as a function of training nodes and uses the result to motivate federated training across subgraphs. Under its stated assumptions, more training samples reduce the bound and align with FedSage and FedSage+ experimental behavior.

  • Theoretical setting: The analysis applies GNTK theory to relate node-classification generalization error to the number of distributed training samples.The setting uses a generalized GNN with layerwise aggregation and ReLU fully connected layers, including GraphSage as a special case.
  • Generalization bound: Theorem 6.2 gives a high-probability upper bound for GNTK node-classification generalization error under Lipschitz bounded loss assumptions.The bound is stated for n i.i.d. training nodes and probability at least 1 −σ.
  • Generalization bound: The kernel-method analysis shows that the bound depends on y⊤Θ(−1)y and tr(Θ), where y is the label vector and Θ is the GNTK matrix.These quantities determine the upper bound for the GNTK formation error in the presented analysis.
  • Implications: More training samples bring down the GNTK generalization-error bound under the assumptions of Definition 6.1.The authors interpret this as theoretical support for collaborative training that includes more nodes across subgraphs.
  • Implications: FedSage and FedSage+ experimentally learn classifiers that better follow global-graph label distributions when they involve more training nodes across subgraphs.The paper states that this experimental finding is consistent with the theoretical implication.

7 Conclusion

The conclusion presents FedSage and FedSage+ as solutions for generalized node classification over distributed subgraphs without direct data sharing, including missing cross-subgraph links. It also outlines FedSage+’s two-phase training process and identifies communication cost and privacy as future concerns.

  • Conclusion: The work targets generalized node classification over distributed subgraphs without direct graph-data sharing.It addresses the setting by combining federated learning with a missing-neighbor generation process.
  • Conclusion: FedSage+ adds NeighGen to address missing cross-subgraph links and trains the resulting local and federated components.The conclusion identifies NeighGen as the missing-neighbor generator used in the corresponding training processes.
  • Conclusion: The paper reports performance improvements for FedSage and FedSage+ consistent with its theoretical implications.The conclusion describes these improvements without supplying a numerical metric in the cited passage.
  • Limitations and future work: FedSage incurs additional communication cost and raises potential privacy concerns, motivating future work on communication reduction and privacy guarantees.The authors identify both issues as promising future directions for distributed subgraph federated learning.
  • FedSage+ training: FedSage+ first jointly trains NeighGen through gradient sharing, then mends local graphs with synthetic neighbors before running FedSage.This two-phase sequence is summarized in Algorithm 1.
  • FedSage+ training: FedSage+ executes federated GraphSage training on the mended subgraphs after the NeighGen phase.The server collects local GraphSage updates and broadcasts the averaged model during the second phase.
  • Theoretical formulation: The theoretical setting defines graph aggregation through repeated neighborhood aggregation and ReLU transformations, with GraphSage corresponding to graph convolutional layers.The GNTK formulation uses covariance and intermediate kernel quantities for node pairs.

C Missing Proofs for Theorem 6.2

The appendix supplies the proof machinery for Theorem 6.2’s GNTK generalization bound, including assumptions on labels and bounds on kernel quantities. Combining these results yields the stated theorem.

  • Proof structure: The appendix provides the detailed proof of Theorem 6.2’s GNTK generalization bound.The proof uses intermediate lemmas and assumptions introduced for the theorem’s full version.
  • Assumptions: The full theorem assumes n i.i.d. training samples, a loss in [0, 1] that is 1-Lipschitz in its first argument, and l(y, y) = 0.Under these conditions, the bound holds with probability at least 1 −σ and constant c ∈(0, 1).
  • Assumptions: The proof introduces an explicit assumption on the training labels before deriving the kernel-dependent bounds.The label vectors are represented through coefficients α and feature vectors β in the appendix development.
  • Kernel analysis: The proof considers a simple GNN with K = 1 and R = 1 to define the kernel matrix on computational graphs.It uses degree-specific feature maps Φ2k to represent kernel terms as inner products.
  • Kernel bounds: The trace term satisfies tr(Θ) ≤2n for n training samples.This result is stated as Lemma C.4 and is used in the final bound derivation.
  • Proof structure: Combining Theorem C.1, Lemma C.3, and Lemma C.4 yields the full generalization bound for a constant c ∈(0, 1).The appendix explicitly identifies these results as the ingredients of the theorem.

D Detailed ablation studies of NeighGen

The NeighGen ablation studies examine how missing-link and missing-neighbor-feature generation contributes to FedSage+, whether local specialization is needed, and how robust federated hyperparameters are.

  • NeighGen components: The ablation decomposes NeighGen into missing cross-subgraph link generation by dGen and missing neighbor-feature generation by fGen.The study first examines these intermediate generation results separately.
  • Local specialization: The experiments test the necessity of training locally specialized NeighGen models.This evaluates whether specialization by local data owner is needed for missing-neighbor generation.
  • Federated robustness: The study varies batch size and local epoch in federated NeighGen training to assess FedSage+ robustness.These hyperparameter experiments are intended to emphasize the robustness of the federated procedure.

D.1 Intermediate results of dGen and fGen.

This section examines dGen and fGen as NeighGen’s components for reconstructing missing-neighbor numbers and features. The results indicate that dGen recovers missing-neighbor counts and fGen recovers missing-neighbor features.

  • NeighGen contains dGen and fGen, which separately reconstruct missing-neighbor numbers and features.Both generators are fully connected neural networks; fGen additionally uses Gaussian noise.
  • dGen predicts missing-neighbor counts from node representations and rounds its float output to obtain integer counts for reconstruction.The rounding step converts the regression output into a usable number of generated neighbors.
  • On MSAcademic with M=3, dGen clearly recovers the true number of missing neighbors.Figure 6 reports the break-down performance for this prediction task.
  • fGen generates missing-neighbor features based on the neighbor count predicted by dGen, thereby completing incomplete neighborhoods.The evaluation compares locally drawn neighborhoods with global-graph neighbors, where smaller values indicate greater similarity.
  • Table 3 shows that fGen effectively recovers the true features of missing neighbors.This evaluates feature reconstruction as part of the missing-neighbor generation process.

D.2 Usage of local specialized NeighGens

This section compares a globally shared NeighGen with locally specialized NeighGens in downstream node classification. The ablation results support using specialized generators rather than directly averaging NeighGen weights across the system.

  • The ablation compares FedSage with a globally shared NeighGen against FedSage+ with locally specialized NeighGens.Experiments were conducted on four datasets with M=3 using downstream node classification accuracy.
  • The results assert that directly averaging NeighGen weights across the system degenerates performance.

D.3 Experiments on Local Epoch and Batch Size

This section evaluates how batch size and local epoch number affect FedSage and FedSage+. FedSage+ consistently improves robustness, further elevates FedSage’s global node-classification performance, and can exceed GlobSage under small batch sizes.

  • FedSage+ consistently further elevates FedSage in the global node classification task across the reported batch-size and local-epoch experiments.Tables 5 and 6 provide the corresponding comparisons on PubMed with M=5.
  • FedSage+ exceeds centralized GlobSage when batch sizes are 16 and 1.This result is attributed in the passage to employing NeighGen.
  • Batch size 16 suits FedSage and FedSage+, while GlobSage suits batch size 64 better than 1 or 16.The passage relates this difference to centralized training on the whole graph versus local sampling from limited subgraphs.
  • With batch size 1, FedSage is prone to overfitting local biased distributions, whereas FedSage+ resists this overfitting.
  • More local epochs degenerate FedSage through increasingly biased aggregated local weights, while FedSage+ maintains relatively more stable downstream performance.The experiments use batch size 64, and GlobSage is trained with 50 epochs.
  • The missing-neighbor generator provides further generalization and robustness against rapid accuracy loss from higher local epoch numbers.
Loading 2106.13430v6…