  Behemoth graphs are often fragmented and separately stored by multiple data
owners as distributed subgraphs in many realistic applications. Without harming
data privacy, it is natural to consider the subgraph federated learning
(subgraph FL) scenario, where each local client holds a subgraph of the entire
global graph, to obtain globally generalized graph mining models. To overcome
the unique challenge of incomplete information propagation on local subgraphs
due to missing cross-subgraph neighbors, previous works resort to the
augmentation of local neighborhoods through the joint FL of missing neighbor
generators and GNNs. Yet their technical designs have profound limitations
regarding the utility, efficiency, and privacy goals of FL. In this work, we
propose FedDEP to comprehensively tackle these challenges in subgraph FL.
FedDEP consists of a series of novel technical designs: (1) Deep neighbor
generation through leveraging the GNN embeddings of potential missing
neighbors; (2) Efficient pseudo-FL for neighbor generation through embedding
prototyping; and (3) Privacy protection through noise-less
edge-local-differential-privacy. We analyze the correctness and efficiency of
FedDEP, and provide theoretical guarantees on its privacy. Empirical results on
four real-world datasets justify the clear benefits of proposed techniques.
