Subgraph Federated Learning via Spectral Methods

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.

Our Contribution. We tackle the challenge of SFL for node classification, where a large graph is partitioned into disjoint subgraphs held by different clients. We adopt the common setting considered in [13,10], where clients know how their subgraphs connect to others, but neither the central server nor any client can access the internal features or edges of other subgraphs. This scenario naturally 39th Conference on Neural Information Processing Systems (NeurIPS 2025).

arises in real-world settings-for example in banking, where a bank records a transaction to a customer at another bank and thus knows the recipient's identifier (e.g., IBAN). In anti-money laundering applications, the assumption of known interconnections is standard [14]. Our contributions push the Pareto frontier of the accuracy-privacy-communication trilemma by enhancing privacy and reducing communication, without compromising predictive performance. Specifically: • We propose FEDLAP, a SFL framework that leverages global graph structure information via Laplacian smoothing in the spectral domain to effectively capture inter-node dependencies across subgraphs. The framework comprises two phases: an offline phase, executed once, in which global graph structure information is exchanged and does not involve any model training, and an online (training) phase that reduces to standard FL, offering higher flexibility than existing methods. FEDLAP achieves utility close to a centralized approach while preserving privacy.

• We propose a decentralized version of the Arnoldi iteration for spectral decomposition that substantially reduces the computational cost of FEDLAP, improving efficiency over prior frameworks and enabling scalability to large, sparse graphs. Crucially, information is exchanged only once before training, and thereafter only model parameters are shared with the server, as in standard FL.

• We provide a rigorous privacy analysis of FEDLAP, demonstrating strong privacy of local subgraph data. FEDLAP is the first SFL framework with formally-supported privacy guarantees-unlike existing methods, which lack such guarantees.

• Through extensive experiments for semi-supervised classification, we show that FEDLAP achieves performance on par with or surpassing existing SFL methods, with reduced communication overhead, better scalability, and enhanced privacy. The code is available at this link.

2 Related Work Subgraph federated learning. Relevant works include FEDSAGE+ [5], FEDNI [6] , FEDDEP [15], FEDPUB [11], FEDGCN [10], FEDCOG [9], and FEDSTRUCT [13]. FEDSAGE+, FEDNI, and FEDDEP address missing inter-client information by employing inpainting techniques to infer features or embeddings. However, these methods face a critical trade-off: accurate inpainting exposes sensitive information and undermines privacy, while poor inpainting fails to improve node classification. FEDPUB avoids inpainting through personalized aggregation strategies, mitigating privacy risks but sacrificing performance due to limited access to global structural information. FEDGCN and FEDCOG incorporate GNNs via secure aggregation methods to exploit structural information. Yet, FEDGCN reveals aggregated node features to neighboring clients and FEDCOG intermediate embeddings, violating privacy (see [13] and [16]

). FEDSTRUCT stands out as the most privacy-preserving method, while achieving similar or superior performance to FEDGCN and FEDCOG. However, it lacks a formal privacy analysis, and is communication-intensive, limiting its scalability to very large graphs.

Incorporating structural information into GNNs significantly enhances their representation power [17,18].

[17] introduces structure-aware aggregation functions that improve expressivity beyond traditional GNNs, while FEDSTAR [18] shares explicit structural information in a FL setup to boost local model accuracy. FEDSTRUCT [13] is the first work to leverage explicit st