Subgraph Federated Learning via Spectral Methods

AI summary

Overview

Research area: Federated learning (FL) on graph-structured data, specifically Subgraph Federated Learning (SFL) for node classification, with a focus on the accuracy–privacy–communication trilemma.

Technical level: Advanced. The paper relies on spectral graph theory (graph Laplacian eigendecomposition), Krylov subspace methods (Arnoldi iteration), homomorphic encryption, and Neyman–Pearson hypothesis testing for its privacy analysis.

Scope: The paper proposes FedLap and FedLap+, two variants of a subgraph federated learning framework that use Laplacian smoothing — in the vertex domain and the spectral domain respectively — to exploit global graph structure while avoiding the exchange of sensitive node features or embeddings, and provides a formal privacy analysis.

What This Paper Is About

In subgraph federated learning, a large graph is split across multiple clients, each holding one subgraph, and the goal is to train a model jointly for node classification without sharing local data. Connections between subgraphs (interconnections) carry important information, but the existing methods that exploit them either share sensitive node features or embeddings, or require costly computation that does not scale. The authors aim to capture these cross-subgraph dependencies using global graph structure information — specifically through Laplacian smoothing — while reducing communication, improving scalability, and provably protecting private subgraph structure.

Key Contributions

1. FedLap: A subgraph FL framework that captures inter-node dependencies across subgraphs by adding a Laplacian smoothing regularizer to the federated loss. The regularizer is expressed using the Rayleigh Quotient to prevent trivial minimization of the term by shrinking the norm of the structure matrix. FedLap avoids explicitly computing the global combined-neighborhood adjacency matrix A̅ ∈ ℝ^(n×n) used in FedStruct, reducing communication overhead and privacy risk.

2. FedLap+: A spectral-domain variant that decomposes the structure feature matrix S into a fixed spectral matrix U ∈ ℝ^(n×r) and a smaller learnable matrix W ∈ ℝ^(r×d_s). By retaining only the first r ≪ n spectral components (those with the smallest Laplacian eigenvalues), FedLap+ reduces dimensionality and communication. It separates the process into a one-time offline phase (structure information exchange, no model training) and an online training phase that reduces to standard FL.

3. A decentralized Arnoldi iteration for spectral decomposition, which substantially reduces computational cost and only requires matrix–vector products. Its complexity is reported as O(nr²) — linear in the number of nodes n — under typical sparsity assumptions, compared with O(n³) for a full eigendecomposition.

4. A rigorous privacy analysis of FedLap+, framing structural leakage as an edge membership-inference attack and using a log-likelihood ratio test. The authors state that FedLap is the first subgraph FL scheme with formally-supported privacy guarantees.

5. Extensive experiments for semi-supervised classification, which the authors report show performance on par with or surpassing existing SFL methods, with reduced communication overhead, better scalability, and enhanced privacy. Code is provided at a link referenced in the paper.

Main Findings

• Laplacian regularization acts as a low-pass filter: Minimizing the spectral-form regularization term in Equation (8) naturally reduces the coefficients of high-frequency eigenvectors u_j (those with larger eigenvalues λ_j), encouraging embeddings to align with smooth, low-frequency eigenvectors. This motivates truncating W to its first r rows.

• Decentralized computation of the regularization term: Equation (4) shows the Laplacian regularizer can be computed with each client i needing only the structure features of its internal nodes and external neighbors, i.e., {s_v for all v ∈ V_i ∪ V_i*}, rather than the full matrix S or a local partition of A̅. This improves privacy and cuts communication relative to FedStruct.

• Truncation preserves global structure: The authors apply spectral truncation to the Cora dataset (2708 nodes) with r = 100 and compare the reconstructed adjacency matrix with the original, reporting that the global structure is preserved as a smoother, low-pass version of the graph. Figure 2 also shows an Arnoldi-truncated matrix for the same r = 100.

• Privacy guarantee under a strong attacker model: Theorem 1 considers a two-client worst case (client 1 target, client 2 attacker) where the attacker holds an estimate Q̆ of the true spectral basis with error bounded by σ (‖Q̆ − Q_{V₁,:}‖ ≤ σ). For large n, the log-likelihood ratio LLR_{u,v} for whether an edge A_uv exists is Gaussian, with H₁: LLR_{u,v} ~ N(½ α_v, α_v) and H₀: LLR_{u,v} ~ N(−½ α_v, α_v) (the H₀ expression appears truncated in the provided text). The paper states this shows clients cannot infer other clients' internal or cross-client connections.

• Online phase leakage matches standard FL: Because the online phase only federates model parameters θ = (θ_f, θ_s, W) via an arbitrary FL scheme such as FedAvg, FedLap+ adds no leakage beyond standard FL and is compatible with differential privacy, homomorphic encryption, and secure aggregation. Any FedLap+-specific privacy considerations are confined to the offline phase, where no features or labels are shared and only structural information is exchanged.

• Privacy-preserving Arnoldi exchange: Each client j computes its local product A_{V_i,V_j} q_{V_j} and sends an additively homomorphically encrypted ciphertext to the server; the server sums the ciphertexts over all j ∈ [K] and returns only the encrypted aggregate to client i, who decrypts it. The server never sees plaintext contributions and client i learns only the required sum.

• FedLap+ inherits FedAvg convergence guarantees, as noted in the paper (with details deferred to Appendix D).

• Comparison against prior work: The paper reviews FedSage+, FedNI, FedDep (inpainting-based), FedPub (personalized aggregation), FedGCN and FedCog (secure-aggregation GNNs that are described as revealing aggregated node features or intermediate embeddings), and FedStruct (the most privacy-preserving prior method, but lacking formal privacy analysis and communication-intensive). FedLap is positioned as pushing the Pareto frontier of the accuracy–privacy–communication trilemma.

• FedStar is cited as prior work sharing explicit structural information in FL for local accuracy, and the Laplacian-smoothing background draws on foundational semi-supervised learning work and on the observation that GCNs approximate spectral Laplacian smoothing through message passing.

Methodology in Plain English

The authors start from a setting in which a global graph is partitioned into K disjoint subgraphs, one per client. Each client knows its own nodes, its own edges, and how its subgraph connects to nodes owned by other clients (external nodes), but not the features or internal edges of other subgraphs. This mirrors real settings such as banking, where one bank records a transaction to a customer at another bank and therefore knows the recipient's identifier (for example, an IBAN).

Their first design, FedLap, keeps the standard federated training loop but adds a term to the loss that penalizes neighboring nodes for having dissimilar structural embeddings. Because this penalty is written as a normalized Rayleigh quotient over the Laplacian, it can be evaluated locally: each client only needs the structure features of its own nodes and its external neighbors. The authors motivate this by pointing out that direct message passing in SFL risks exposing node and adjacency information, while GCNs are known to approximate Laplacian smoothing anyway.

Their second design, FedLap+, moves the same idea into the spectral domain. The graph Laplacian is symmetric and positive semi-definite, so it decomposes as L_G = U Λ Uᵀ. Because the regularization term weights each spectral coefficient by its eigenvalue, it acts as a low-pass filter, so the authors keep only the r smallest eigenvalues and their eigenvectors. The large learnable structure matrix S is replaced by a fixed spectral matrix U and a much smaller learnable W, and only the rows of U that a client needs are distributed to it.

To get the top eigenvectors without an expensive full eigendecomposition, they use the Arnoldi iteration, which builds an orthonormal basis for a Krylov subspace using only matrix–vector products with L_G. Each client can compute its own block of the product L_G q, but the cross-client parts require coordination. The authors solve this with additive homomorphic encryption: clients send encrypted local products to the server, which sums them and returns the encrypted total, so no party sees individual contributions in plaintext. This one-time computation forms the offline phase; afterwards, training is ordinary federated learning.

For privacy, they analyze the offline phase only, since the online phase is standard FL. They model the attack as deciding whether a particular edge exists inside a target client's subgraph, using the optimal log-likelihood ratio test (justified by the Neyman–Pearson lemma), and derive the distribution of that ratio for large graphs under a deliberately conservative, unrealistically strong attacker.

Why This Matters

Impact on research: The paper claims the first formally-supported privacy guarantee in subgraph federated learning, replacing the informal privacy arguments of prior work such as FedStruct, FedGCN, and FedCog. It also reframes structural exploitation in SFL as a spectral filtering problem, and contributes a decentralized Arnoldi procedure that other decentralized spectral methods could reuse. By separating a one-time structural preprocessing phase from ordinary FL training, it decouples graph-specific machinery from the training loop, which the authors present as offering greater flexibility than existing methods.

Real-world applications (as listed in the paper):

• Anti-money laundering, where the assumption of known interconnections between institutions is described as standard.
• Banking, where a bank knows it transacts with a customer at another bank (identified for example by IBAN) but not that customer's internal data.
• Social networks, where user relationships span platform boundaries or administrative domains.
• Supply chains, where relationships between organizations are only partially visible to each participant.
• Graph learning tasks more broadly cited as benefiting from GNNs, including drug discovery, social network analysis, and traffic prediction.

Industry relevance: Organizations that hold graph data but cannot share it due to regulatory, privacy, or proprietary constraints — financial institutions, healthcare and pharmaceutical researchers, telecommunications, and logistics operators — are the intended beneficiaries. The reduction in communication overhead, the linear-in-n scaling of the Arnoldi procedure, and the ability to use standard FL primitives (including differential privacy, homomorphic encryption, and secure aggregation) in the online phase make the approach more practical for large, sparse production graphs than methods that share embeddings or full adjacency information.

Future Directions

• Bounding the attacker's spectral estimation error: The privacy theorem assumes the attacker's estimate of the spectral basis is accurate to within σ and that equality in the attack equation holds only when σ = 0 and the Arnoldi residual h_{r+1,r} = 0. Understanding how the guarantee degrades for realistic values of σ and nonzero residual is a natural open question.

• Choosing the truncation rank r: The paper states r should be on the order of the number of communities in the graph and uses r = 100 in the Cora illustration. How to select r principledly across datasets, and how it trades off utility against privacy and communication, remains to be determined.

• Extending beyond node classification: The formulation is built around semi-supervised node classification with a cross-entropy loss and known inter-client connections. Whether the same spectral approach transfers to other tasks — link prediction, graph-level prediction, or settings where interconnections are unknown — is not addressed.

• Integrating formal privacy-enhancing mechanisms into the offline phase: The paper notes that the online phase is amenable to differential privacy, homomorphic encryption, and secure aggregation. Whether the offline phase can be composed with differential privacy to yield an end-to-end guarantee, rather than the described worst-case hypothesis-test analysis, is left open.

Target Audience

This paper is aimed at federated learning and graph machine learning researchers, particularly those working on subgraph federated learning, privacy-preserving graph learning, and spectral graph methods. It will also interest practitioners who need to train GNNs over graphs partitioned across organizations under regulatory or proprietary constraints, especially those concerned with communication budgets and scaling to large, sparse graphs. Readers should be comfortable with linear algebra, graph Laplacian notation, and basic federated learning concepts; the spectral and privacy sections are notably technical.

Authors’ abstract

We consider the problem of federated learning (FL) with graph-structured data distributed across multiple clients. In particular, we address the prevalent scenario of interconnected subgraphs, where interconnections between clients significantly influence the learning process. Existing approaches suffer from critical limitations, either requiring the exchange of sensitive node embeddings, thereby posing privacy risks, or relying on computationally-intensive steps, which hinders scalability. To tackle these challenges, we propose FedLap, a novel framework that leverages global structure information via Laplacian smoothing in the spectral domain to effectively capture inter-node dependencies while ensuring privacy and scalability. We provide a formal analysis of the privacy of FedLap, demonstrating that it preserves privacy. Notably, FedLap is the first subgraph FL scheme with strong privacy guarantees. Extensive experiments on benchmark datasets demonstrate that FedLap achieves competitive or superior utility compared to existing techniques.