Deep Efficient Private Neighbor Generation for Subgraph Federated Learning

Ke Zhang, Lichao Sun, Bolin Ding, Siu Ming Yiu, Carl Yang

Introduction

Graph Neural Networks (GNNs) have become a cornerstone for analyzing relational data. However, in many practical applications like fraud detection or drug discovery, graph data is fragmented across multiple organizations or "silos." This scenario, known as subgraph federated learning, presents a significant challenge: incomplete neighborhoods. Since GNNs rely on aggregating information from adjacent nodes, the absence of cross-silo connections—where a node's neighbor resides in a different client's database—severely degrades model performance.

Previous state-of-the-art methods like FedSage attempted to address this by generating missing neighbors. However, these approaches often struggled with high communication overhead, limited structural utility (focusing only on 1-hop neighbors), and a lack of formal privacy guarantees.

The FedDEP Framework

To overcome these limitations, we present FedDEP (Deep Efficient Private Neighbor Generation). FedDEP is designed to reconstruct missing cross-silo structural information efficiently while maintaining strict privacy standards.

Overview of the FedDEP framework, illustrating the transition from unobservable global graphs to mended local subgraphs via deep neighbor generation and embedding prototyping.

The framework consists of three primary innovations:

1. Deep Neighbor Generation (DGen)

Unlike prior methods that predict raw features of immediate neighbors, FedDEP’s DGen component generates embeddings that encapsulate multi-hop neighborhood contexts. This allows local GNNs to incorporate the influence of distant nodes in the global graph, effectively "mending" the fragmented subgraphs with high-fidelity structural information.

2. Efficient Pseudo-FL (Proto)

Traditional federated learning requires frequent, high-bandwidth data exchanges. FedDEP introduces a Pseudo-FL strategy using embedding prototyping. Clients cluster their local node embeddings into representative "prototypes" and share them once at the beginning of training. During the generation phase, clients perform local searches against these shared prototypes, reducing inter-client communication during generator training to nearly zero.

3. Noise-free Differential Privacy (NFDP)

Privacy is paramount in federated settings. While standard Differential Privacy (DP) often sacrifices accuracy by injecting noise, FedDEP utilizes Noise-free Differential Privacy (NFDP). By leveraging the inherent stochasticity of mini-batch neighborhood sampling and Bernoulli-based selection, FedDEP provides formal edge-local-differential-privacy (edge-LDP) without degrading model utility.

Experimental Evaluation

FedDEP was evaluated on four benchmark datasets: Cora, CiteSeer, PubMed, and MSAcademic. These graphs were partitioned into 3, 5, and 10 subgraphs using the Louvain algorithm to simulate realistic data silos.

Key Results

The experimental results demonstrate that FedDEP consistently outperforms existing baselines in both accuracy and efficiency.

Performance comparison of FedDEP against baselines, showing accuracy curves, loss convergence, and training time efficiency.
  • Superior Accuracy: FedDEP achieved up to a 3.84% improvement in node classification accuracy over FedSage. In certain instances, such as on the CiteSeer dataset, the generated neighbors acted as a form of robust data augmentation, allowing FedDEP to even surpass centralized models.
  • Communication Efficiency: The "Proto" strategy significantly slashes overhead. While FedSage's costs scale with feature dimensions and the number of missing neighbors, FedDEP’s communication is dominated by a one-time exchange of compact prototype sets.
  • Privacy-Utility Balance: NFDP allows FedDEP to maintain high accuracy while offering robust protection against edge-inference attacks, outperforming traditional noise-based DP methods.

Conclusion

FedDEP offers a scalable and private solution for training GNNs on fragmented graph data. By shifting from feature generation to deep embedding generation and utilizing efficient prototyping, it resolves the "blind spot" of local subgraphs without the prohibitive costs or privacy risks of previous methods. Future work will explore extending this framework to dynamic graphs and overlapping node sets.

Summary updated

BibTeX
@inproceedings{zhang2024deep,
  author = {Ke Zhang and Lichao Sun and Bolin Ding and Siu Ming Yiu and Carl Yang},
  title = {{Deep Efficient Private Neighbor Generation for Subgraph Federated Learning}},
  booktitle = {SDM},
  year = {2024},
  doi = {10.1137/1.9781611978032.92},
}
Figure