FedSage+ (Subgraph Federated Learning with Missing Neighbor Generation)

In FedSage+, each data owner D_i holds out h% of its local nodes V_i^h subset V_i and incident links E_i^h to construct an impaired subgraph G_bar_i = {V_bar_i, E_bar_i, X_bar_i} and trains a Missing Neighbor Generator NeighGen_i comprising a K-layer GraphSage encoder H_i^e(theta^e) producing node embeddings z_v in R^{d_z}, a linear degree generator dGen(theta^d) predicting missing neighbor counts n_tilde_v = sigma((theta^d)^T . n_v) under smooth L1 loss L^d = (1/|V_bar_i|) sum_{v in V_bar_i} L_1^S(n_tilde_v - n_v), and a Gaussian-noise variational feature generator fGen(theta^f) generating n_tilde_v neighbor feature vectors x_tilde_v = R(sigma((theta^f)^T . (z_v + N(0,1))), n_tilde_v) (Equations 3-4).

Because directly averaging NeighGen weights across clients via FedAvg degrades neighbor diversity (Table 4), FedSage+ maintains a local specialized NeighGen_i per owner D_i and optimizes the cross-subgraph feature reconstruction loss L_i^f = (1/|V_bar_i|) sum_{v in V_bar_i} sum_{p in [n_tilde_v]} (min_{u in N_{G_i}(v) cap V_i^h} ||x_tilde_v^p - x_u||_2^2 + alpha sum_{j in [M] \ {i}} min_{u in V_j} ||H_i^g(z_v)^p - x_u||_2^2) (Equation 6), where each peer owner D_j locally computes the closest-node distance gradient nabla L_{i,j}^f and returns it via the server without sharing raw node features X_j (Algorithm 1).

In the overparameterized Graph Neural Tangent Kernel (GNTK) regime with kernel matrix Theta in R^{n x n} satisfying tr(Theta) <= 2n (Lemma C.4) and sqrt(y^T Theta^{-1} y) = o(n) (Lemma C.3), the node classification generalization error is bounded by L_{D(F)} = O(sqrt(y^T Theta^{-1} y . tr(Theta)) / n + sqrt(log(1/sigma) / n)) <= O(1/n^c) (Theorem 6.2 and Theorem C.1), and empirically FedSage+ outperforms Local GraphSage (LocSage) by an average of 23.18% across Cora, CiteSeer, PubMed, and MSAcademic while reducing the accuracy gap to centralized GlobSage from 2.11% (FedSage) to 1.28%.

FedSage+ requires tuning the graph impairing ratio h% to match the true missing cross-subgraph edge fraction (since too-small h=1% provides insufficient training supervision for NeighGen and too-large h=30% over-sparsifies local subgraphs), and Phase 1 NeighGen training transmits node embeddings z_v and generator models H_i^g across owners, incurring additional communication and potential embedding-level privacy leakage without formal differential privacy.