Subgraph Federated Learning via Spectral Methods
Authors: Javad Aliakbari
Johan Östman
Ashkan Panahi
Alexandre Graell i Amat
Venue: NeurIPS 2025 poster ()
Keywords: Subgraph Federated Learning
Graph neural networks
Federated Learning
Interconnected Graphs
Laplacian Smoothing
Primary area: social_and_economic_aspects_of_machine_learning

Abstract: We consider the problem of federated learning (FL) with graph-structured data distributed across multiple clients. In particular, we address the common 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 the proposed method achieves competitive or superior utility compared to existing techniques.

Subgraph Federated Learning via Spectral Methods
Javad Aliakbari'
Johan Östman?
Ashkan Panahi'
Alexandre Graell Amat!
Chalmers University of Technology
AI Sweden
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 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 inder-node dependencies while ensuring privacy and scalability. We provide a formal analysis of the privacy of FEDLAP, demonstrating that it preserves privacy. Notably, FEDLAP 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.
risks, or relying on computationally-inennss
1 Introduction
Graph-structured data naturally arise in a wide variety of real-world scenarios, with nodes representing distinct entities and edges reflecting relationships among them. Illustrative examples include anti- money laundering, social networks, and supply chains.
For graph-structured data, graph neural networks (GNNs) 1:3 have demonstrated remarkable effectiveness in tasks such as drug discovery, social network analysis, and traffic prediction, by capturing both node and structural information. However, many real-world scenarios, as in the examples above, graph data is distributed across multiple parties, hindering direct data sharing due to regulatory, privacy, or proprietary considerations. This has led to the emergence of federated learning (FL) 4 as promising paradigm to harness globally distributed graph data while preserving local data privacy. particularly common setting for graph-structured data Subgraph Federated Learning (SFL)
[. where each client holds a disjoint subgraph of a globally connected graph.
Several SFL methods have been proposed 11 but most except 111 involve sharing node features or learned embeddings, raising critical privacy concerns. Furthermore, attaining robust predictive accuracy under limited information exchange remains challenging. This reflects the well-known trilemma [12), where improving one aspect often comes at the expense of the others. More recently, [33] proposed FEDSTRUCT, an SFL method that avoids sharing sensitive features by leveraging global graph structure. Although FEDSTRUCT offers stronger privacy than earlier methods (as clients share significantly less information), it still involves sharing partial adjacency matrix information and node structure features, which can potentially leak information. In addition, lacks a formal privacy analysis and demands considerable communication overhead.
Our Contribution. We tackle the challenge SFL for node classification, where a large graph is partitioned into disjoint subgraphs held by different clients. We adopt the common setting considered [13] 1O), 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 (NcurIPS 2025).

---

arises in real-world settings for example in banking, where bank records a transaction to customer another bank and thus knows the recipient's identifier (e.g.. IBAN). In anti- anti-money laundering applications, the assumption of known interconnections is standard [14]. Our contributions push the Pareto frontier of the communication, without compromising predictive performance. Specifically:
trilemma by enhancing privacy and reducing
We propose FEDLAP, 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 centralized approach while preserving privacy.
We propose a decentralized version of the Arnoldi iteration for spectral decomposition that substan- tially 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 guaran- tees-unlike existing methods, which lack such guarantees.
Through extensive experiments for semi- sumei-suere 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 [5], FEDPUB [[]]. 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 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 exploit structural information. Yet, FEDGCN reveals aggregated node features to neighboring clients and FEDCOG intermediate embeddings, violating privacy (see [13] and (6)). 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 cotmmmnnicationinnnniiiii limiting its scalability to very large graphs
Structural information in GNNs. Incorporating structural information into GNNs significantly enhances their representation power 17 [8] 17 introduces structure-aware aggregation functions that improve expressivity beyond traditional GNNs, while FEDSTAR [8] shares explicit structural information in FL setup boost local model accuracy. FEDSTRUCT [3] is the first work to leverage explicit structural information in SFL to enhance performance while preserving privacy.
Laplacian smoothing. Foundational works [19 20 highlighted both the theoretical and practical advantages of integrating graph Laplacians into semi-supervised frameworks, emphasizing their role in preserving the underlying data relationships. Modern GNNs (1 22 draw inspiration from Laplacian smoothing by employing message- paagge-ppsinggggg mechanisms that aggregate information from neighboring nodes, effectively promoting local smoothness in the learned embeddings.
3 Preliminaries and Setup
General notation. For a matrix M E RaxT, we denote by Mij its (i, element. We represent a submatrix of M that is restricted rows by the set I by Mz: and a submatrix that is restricted in columns by the set J by M., Hence, M., and M., denote the i-th row and i-th column of M, respectively. A submatrix of M that restricted in rows by the set I and in columns by the set J by MI.y. We define [k] kk).
Graph notation. We consider undirected graph 9 = (V,E,, X, Y), where V (1, n is the set of nodes, & {(u, v)lu, e V) the set of edges, X e Raxd the node feature matrix,

---

and Y E RRex the label matrix. Let De E Rd be the feature vector of node v, y, E 13% its one-hot encoded label vector, and V S V the subset of nodes that possess labels. The adjacency matrix of graph G is denoted by A E Rux", where Aur = 1 if (u, v) E and 0 otherwise. We define the diagonal matrix of node degrees D E [R where Dun. E. Auv. Also, we denote
by A = A + I the self-loop adjacency matrix, by À D A the normalized self-loop adjacency matrix, where Dan = Evey-Aa Auv. and by A = Ei=1 3:AA the L-hop combined neighborhood adjacency matrix. The elements of A reflect the proximity of two nodes in the graph, with 3, Ets 31 = 1, determining the contribution of each hop. The graph Laplacian of G is Lg D A.
based regularization method that encourages similar representations for neighboring nodes via a Laplacian loss term. Specifically, the total loss can be expressed as = + + Creg where Le the supervised loss defined over the labeled part of the graph, Arg is a weighting factor, and Legg is the Laplacian regularization term defined as
Laplacian smoothing. Laplacian smoothing a
Lieg = Auellf((am)) - fo(m=))) Tr (f6(x)"LoffoX)) (
Here, fe(-) denotes a neural network- differentiable function. The regularization term Lieg ensures that connected nodes in the graph have similar feature representations, thereby leveraging the graph structure to propagate label information from labeled nodes to unlabeled nodes.
Setup. We consider scenario where data is structured according to global graph G (V, E, Y,),, which is distributed among K clients such that each client owns a smaller local subgraph. We denote by Gi = (V., Vi &,, E X i, Y): the subgraph of client i, where V: C V is the set of n., nodes that reside client i, referred to as internal nodes, for which client i knows their features. V is the set of nodes that do not reside in client but have at least
connection to nodes in V. We call these nodes external nodes. Importantly, client i does not have access to the features of nodes in V Furthermore, & represents the set of edges between nodes owned by client (intra-connections)) E the set of edges between nodes of client and nodes of other clients (interconnections). X, E R xd the node feature matrix, and Y, E RR xd the label matrix for the nodes within subgraph G, and we denote by D) the set of nodes that possess labels.
Federated learning, The FL problem can be formalized as learning the model parameters that minimize the aggregated loss across clients,
e* arg min (e(
1 M
Σ (,)
with (() = Σ CE(U,, U.).
(1)
0
DEV.
where CE is the cross-entropy loss function between the true label y, and the predicted label g..
The model 0 is trained iteratively over multiple epochs. At each epoch, the clients compute the local gradients VoL, (0) and send them to the central server. The server updates the model through
gradient descent, 0 0 AV)((O), VoL(O) 1 Σ VoL:(O), and is the learning rate.
K
4 FEDLAP
In this section, introduce the FEDLAP framework (illustrated in Fig. D. designed to exploit graph structure for enhancing SFL while rigorously addressing privacy and communication challenges.
FEDLAP builds upon the key insights from FEDSTRUCT [3] (discussed in Appendix A). explicitly addressing its main limitations: (i) the need to compute costly global matrix À E Ruxm significantly increasing communication cost and privacy risks; (ii) optimization of a large structure feature matrix S E R during training, which demands extensive communication and exposes the gradients of S to all clients, thereby increasing privacy leakage; and (iii) absence of formal privacy guarantees.
We resolve these challenges using two complementary strategies:
FEDLAP (Section 4.1) employs Laplacian smoothing as regularizer to implicitly enforce similar structural embeddings among neighboring nodes. This avoids explicitly calculating the costly matrix A, thus significantly reducing communication overhead and privacy risks.
3

---

deet
Partal Monneche
Vadult
S
Figure 1: FEDLAP+ with three clients. Left: the global graph and its partitioning across clients. Center: local refinementt of the global eigenvectors obtained via Arnoldi iterations; the corresponding adjucency matrix shown below. Right: federuted learning leveraging the estimated global eigenvectors.
FEDLAP+ (Section 4.2) addresses the challenge posed by the large structural matrix S. decomposes S into fixed spectral matrix U [R"Xr and smaller learnable matrix W e Rrxd., Instead of sharing the entire matrix U, FEDLAP+ distributes only the relevant rows to corresponding nodes. This efficient distribution is enabled by the spectral representation of the graph Laplacian, which allows truncation to retain only the smoothest eigenvectors. Consequently, this substantially reduces the dimensionality, accelerates convergence, and enhances privacy.
To efficiently compute the partial spectral decomposition in FEDLAP+, we propose a decentralized version of the Arnoldi iteration (Section 4.3) and Appendix B.2 This approach significantly re- duces the computational cost of FEDLAP+, making it more efficient than prior frameworks (Section
scaling to large, sparse graphs, while preserving privacy (Section 5
Below, we provide a detailed description and a formal analysis of these components.
4.1 FEDLAP: Exploiting Structural Information in SFL via Laplacian Smoothing
The core idea of FEDLAP is to leverage structural information through Laplacian smoothing, achieved by incorporating graph Laplacian regularization term into the loss function in (.. Specifically, each client i E [K] node prediction is performed for a node E Vi as
j. = softmax (Jo, ( (X;, E,, v) + go, (s.))
where the parameters of the model = (0r, 2z S) are optimized based on the loss function
Tr(S LG
( = (0) + Aveg
33)
Tr
with Lg being the Laplacian matrix of graph 9, and S is generated using HOP2VEC Appendix A).
B3
(see
In (3). the Laplacian regularizer is formulated using the Rayleigh Quotient, which normalizes the Laplacian term by the norm of S. This normalization prevents the undesirable trivial minimization of the regularization term by simply reducing the norm of S. Equation (3) can be rewritten as
( = (0) + Arog E(mN)E |/. -s
(4)
Ever ||
The regularization term non-negative and decreases when neighboring nodes have similar NSFs.
The regularization term 3 implicitly captures pairwise relationships between nodes without clients necessitating the knowledge of the whole NSF matrix and local partition of A, as opposed to FEDSTRUCT. Specifically, Equation (4) shows that the Laplacian regularizer can be computed in a decentralized manner, where each client only requires the NSFs of its internal nodes and external neighbors, i.c., {s., Vu E V, V.). This approach not only enhances privacy compared to FEDSTRUCT but also significantly reduces communication overhead.
Motivation. Our motivation for employing Laplacian smoothing in FEDLAP arises from two critical considerations: (i) direct message passing in traditional SFL inherently risks exposing sensitive node and adjacency information, leading to privacy concerns; and (ii) graph convolutional networks (GCNs), as shown by Kipf and Welling [21], approximate spectral Laplacian smoothing through message passing. Hence, adopting Laplacian smoothing enables FEDLAP to implicitly leverage structural information without explicitly exchanging sensitive data, thus preserving the benefits of message-passing methods while addressing their privacy vulnerabilities in FL contexts.

---

Sharing NSFs from external nodes Vi may still pose privacy risks, as these features are indirectly tied to the labels through 2 Moreover, the high dimensionality of makes its optimization computationally and communication-intensii requiring multiple rounds of training, which amplifies the risk of information leakage.
To address these challenges and further enhance privacy, in Section 4.2 we propose leveraging the Laplacian regularizer in the spectral domain, as detailed in the next subsection. This approach eliminates the need for explicitly sharing 8, E V.
4.2 FEDLAP+: Exploiting Structural Information in the Spectral Domain
FEDLAP+ a spectral-domate domain variant of FEDLAP, designed to reduce communication overhead and privacy leakage while maintaining competitive performance. It decomposes the SFL problem into two distinct phases:
An offline phase consisting of a one-time preprocessing step that precomputes the influence of the global graph structure for each node. This phase involves no model training and privately extracts useful graph-level structural information without revealing node features or labels.
An online (training) phase that does not involve any exchange of information among clients and effectively reduces standard FL.
The graph Laplacian Lg is symmetric and positive semi-definite and can be decomposed as
Lg UAU
where U E Rax* = [ui..... un] is the matrix of orthonormal eigenvectors of Lg and A is the An, Let W U Raxd, be the
diagonal matrix of eigenvalues, Aj >3J with A
spectral representation of matrix S. Substituting (5) into 2 and 3
yields
ú = softmax (fo, (X, &,, D) + (0 vV. W))
(6)
(()) (0) Argg Tr(W AW)
Tr(W W)
where Uo, is the w-th row of U and 0 = (Or, 0s, W).
Leveraging the Laplacian in the spectral domain provides principled way to truncate W and mitigate information exchange. particular, since A diagonal matrix, we can simplify as
EJ= > |10,11 Σ W
((0) = (0) + A
(8)
where wy is the j-th row of W.
Equation (8) reveals that the Laplacian regularization term acts as a low-pass filter by attenuating high-freuennc components while preserving low-frequency (smooth) components the graph signal. Specifically, minimizing (8) naturally reduces the coefficients ||wy|| associated with high-frequency eigenvectors uj, which correspond larger eigenvalues X, of the graph Laplacian. This encourages the learned embeddings to align with low-frequency eigenvectors, which capture smooth variations across the graph. These eigenvectors correspond to signals that vary gradually across connected nodes, reflecting regions of high connectivity and structural continuity. As result, the Laplacian regularization inherently promotes smoothness the learned embeddings. This observation motivates truncating W by removing rows corresponding large cigenvalues, these represent less smooth-as and consequently less informative anformative-sspects of the graph structure.
To focus on the most informative spectral components and reduce dimensionality, we retain only the first r & n rows of W, defined as
W [r
[wI ..... w T
E Rex4
(9)
Similarly, we truncate the corresponding columns of U and the diagonal elements of A:
U Ua(r]]
[r] = U1,, U2 U2,..., 2r
R
Apprl = diag(Ai....,..) E Rexr.
(10)
5

---

Adjacency matrix.
Spectral trunc. matrix.
(c) Amoldi matrix.
Figure 2: Comparison of different matrix representations in the graph. In (b) and (c), r 100 for dirnensionality reduction.
With this truncation, the graph Laplacian Lg (see can be approximated
Lg = U (() (r1
U
(11)
To obtain a good approximation of the Laplacian Lg. r should be chosen on the order of its rank, i.c. the number of communities in G, which is much smaller than In Fig. we apply spectral truncation to the Cora dataset (2708 nodes) and compare the reconstructed adjacency matrix (F) with the original (Fig. [[a)). As shown, the global structure is preserved, yielding smoother, low-pass version of the graph.
The truncation of spectral components not only drastically reduces communication overhead (thereby improving privacy), but also serves as an additional form of regularization, preventing the model from overfitting to noise or irrelevant details in the graph structure. This is particularly important in FL settings, where models must generalize well across different subgraphs from multiple clients.
Note that FEDLAP+ inherits the standard convergence guarantees of FEDAVG (see Appendix D
4.3 Decentralized Arnoldi Iteration: Privacy-Preserving Approximation of the Laplacian
FEDLAP+ requires the eigendecomposition of the Laplacian Lg. While full decomposition has a complexity of (n²) and prohibitively expensive in decentralized settings, as discussed in FEDLAP+ only requires the first eigenvectors associated with the smallest eigenval- ues. To compute these efficiently and privacy-preserving manner, we propose a decentralized version of the Arnoldi iteration
Section 4.2
(23) particularly well-suited for large, sparse graphs. As detailed in B.3 its complexity is O(nr)) ie., linear in under typical sparsity assumptions.
Appendix
The Arnoldi iteration is efficient iterative method for approximating eigenvalues and eigen- vectors of large, sparse matrices. Rather than performing a full (and potentially very costly) eigendecomposition, Arnlli constructs an orthonormal basis for the so-called Krylov subspace (M,, x) span(ær Mæ....,M Mmm-1z) x) where æ is some chosen starting vector. Specifically, it computes an orthonormal basis (41,-. .., am for the subspace KC, (M, æ)) iteratively and yields an approximate cigendecomposition of M as
M R T
(12)
where U = Qm V and U ~ I, with Qm, = [ 91..... 9m being the matrix of Arnoldi basis vectors, and and Σ the matrix of eigenvectors and eigenvalues, respectively, of an upper Hessenberg matrix H m Rm with entries hij q. MM For details, we refer the reader to Appendix B
We use the Arnoldi iteration to approximate the eigenvalues and eigenvectors of Lg- Crucially, the Arnoli iteration relies only on matrix-vecte multiplication. As shown in Section this enables a decentralized. privacy-presee preeeriie implementation that does not disclose clients' node structures. In particular, given the Krylov subspace K,m (Lg, v), the Amolli update becomes (see (22 in Appendix
Tt Lgg E hn,
hi, q. Loge:
(13)
|re]
More compactly, if we stack the first Arnoli vectors in Q, = [q collect the coefficients luj = q, Logg, we obtain the Arnoldi relation
q,l and let H,
R
LgQ, Q, H, + h, gr+1 e
(14)

---

where e, is the r-th standard basis vector. A small residual hy+1,r implies the rank-r approximation
Lg ~ Q, = Q.V, Qr
(15)
where V, E, V. is the eigendecomposition of H,. Defining UsIrl _ Q,V, and [rl.te] recovers the truncated Laplacian approximation in (IT).
Σr
Proposed decentralized Arnoldi iteration. We aim use Amoldi to estimate the smallest r eigenvalues of Lg and corresponding cigenvectors in a decentralized manner across clients while preserving privacy. For generic vector q. we define = Lgq. As each client i knows the rows and columns of the adjacency matrix indexed by V:, i.e., Av,, and A.v, (and thus also Dy and D., D.,,)), client i needs obtain its local block of b Lgg, namely by. This block can be written as
by. Dv.,A 94,
Σ Av.y, Sv, j=1
(16)
The first term is computable using only local information, whereas the second term requires collabora- tion across clients. To preserve privacy, so that no party learns any part of the global adjacency beyond its own, each client j computes the local product Av,, Tv, and sends an additively homomorphically encrypted ciphertext to the server. The server sums these ciphertexts over all j E [K] and returns
the encrypted aggregate client i, who decrypts it to obtain Σj=1 Av,,, 9y,- In this way, the server never accesses individual contributions in plaintext, and client learns only the required sum. Protocol details are in Appendix B.2 and the privacy analysis is given in Section and Appendix C
Privacy Analysis of FEDLAP+
In this section, we analyze the privacy of FEDLAP+. We show that, under strong attacker model, clients cannot infer other clients' internal connections or cross-client connections, i.e., FEDLAP+ provides strong privacy.
As mentioned earlier, FEDLAP+ is divided into an offline and an online phase. In the online phase, clients federate the model parameters 0 = (0,. 0s, W) via an arbitrary FL scheme, c.g., FEDAVG [4] Hence, the online phase of FEDLAP+ exhibits the same kind of vulnerabilities as FL and amenable to privacy enhancing techniques like differential privacy, homomorphic encryption, and secure aggregation (24). In the offtine phase, executed once before training, no node features or labels are shared; only information related to the graph structure is exchanged. The goal is to extract a compact structural summary while preserving privacy. As previously explained, we operate in the spectral domain and use a decentralized Arnoldi procedure to estimate small set of Laplacian eigenvectors, leveraging the empirical fact that most interconnection signals lie low-frequency components.
Under this decomposition, any additional privacy considerations specific to FEDLAP+ are confined to the offline phase, as the online phase introduces no leakage beyond standard FL. In the offline phase, since no fcatures or labels leave a client, the only potential leakage channel pertains to edges. We thus focus on structural privacy and cast the attack as a membership-inferenee attack on edges: given the offline messages, can an adversary determine whether specific connection Aue "participated" in the Arnoldi computations? This results in a binary hypothesis test based on log-likelihoon ratio (LLR). By the Beyyann-Pearoon lemma, the LLR test is the optimal decision rule for this setting.
Attacker observations and procedure. For the analysis, we consider a worst-case scenario in- volving two clients: client (target) and client 2 (attacker). The attacker aims to infer whether an edge exists between two nodes u, u E V1 (test Ho Age = 0 vs. H1 Age 1). From the decentralized Arnoldi updates (see (16) the attacker obtains, for the target client, the aggregated vector Tv- = Ays,,. 9r. and also knows the adjacency blocks Av.,, Since Tv, comprises n2 linear equations in the n 12 unknown spectral blocks gv, the attacker can only form an estimate .. S where Q is the estimate of Qv and o quantifies the attacker's uncertainty. Using the public H, and spectral estimate Q and invoking the Arnoldi relation (14). the attacker creates the equation
Ty, of the true spectral basis. We assume Q -
U AQ
(17)
where U A Dr. Q Av, Qy QH, and Ā Av,y, Equality in (17 holds only when 0 and h,t1, = O. The attacker must also know Dv, to calculate U. The attacker then
7

---

50
1.5
100
P+ n
R
150
200
R (r 100)
(r 100)
10
5
10
10
5
0
5
10
5
10
15
7
Figure 3: Effect of rank parameter r on the precision recall with varying " for the Chameleon (left), Amazon photo (center), and PubMed (right) datasets. The pairs (p, n) are (0.0139, 2277). (0.008, 7650), and (0.0005, 19717), 17),, respectively. The curves illustrate how the choice of impacts the trade-off between recall and precision as the decision threshold varies.
performs the following steps: (i) obtain U, (ii) evaluate the log-likelihood ratio LLR for the two hypotheses using U, and (iii) decide H1 whenever LLR 2 for some threshold E R.
We note that the following analysis adopts deliberately conservative perspective. In line with standard practice in privacy research (c.g., secure aggregation and spectral privacy frameworks), we assume an unrealistically strong attacker obtain worst-case privacy guarantee.
Theorem I. Consider two clients rumning the decentralized Arnoldi scheme outlined in Sec. 4.3 Let A be a random graph with denoting the probability of a connection between any pair (u, U) for u, E V1. Assume to be known by client 2. Let U = AQ. where À Av,, v. and Q = Q are client 2's observations (provided by client 1) about the sensitive low-rank matrix Á. Moreover let Q have delocalized entries and be known to client 2. For large n, the LLR
P(U) Awo =1)
LLR log
(18)
P(U 0)
random variable with the distribution
LLRu, ~ N (2arnar))
LLR ~ ~ (-Zacsau
H1:
Ho
(19)
where ag = Q uet and Σ = -p11-))''
Proof. See Appendix
Theorem [ provides insights into how different parameters influence the attack performance, as shown in Corollary
Corollary I. Consider the same setting as in Theorem If T Q = (r/n)I, it follows that
DKL (Pr(LLR..v)
H1) Pr(LLRu,v
Ho)) =
r
2np(1 p)
Proof. See Appendix C.4
C.4
The KL divergence in Corollary [ quantifies the discrepancy of the LLR distributions under the two hypotheses; a lower value makes it harder for the adversary to distinguish between them. This implies that a larger r, i.e., increased shared information between clients, and smaller p. i.e., sparser graphs, negatively impact privacy, whereas greater number of nodes in the graph, has a beneficial effect.
Using Theorem [ in Appendix C.5 we derive the true-positive rate (TPR) and the false-positive rate (FPR) for the attack and then use them to obtain expressions for the precision and recall of the attack function of p, r, n., and 7y Fig. we plot the sum of precision (P) and recall (R) for different values of r and varying Each figure corresponds to a distinct pair (p, n) drawn from three different datasets Chameleon, Amazon photo, and PubMed where p the estimated probability of connection and is the number of nodes. We observe that, for sufficiently small r, P + R < 1 (r 175 for Chameleon, r 350 for Amazon-Photo, and r = 80 for PubMed). In our privacy analysis, achieving P + R 1 indicates that the attacker gains no meaningful advantage over trivial assumptions- either all nodes connected (precision P z 0. recall R = 1) or all disconnected revealing useful information about individual connections.

---

Table 1: Communication cost.
Figure 4: Precision vs recall on PubMed.
Algorithm
Offine
Online
thooretical
FRDTAP
O K. [0] + E. K d.n)
0.8
PubMed
FEDLAP+ (Amoldá)
O(r K. n) O K- p-n) O(n Pin.d.om Cava)
O(E K [0])
0.6
FEDSTRUCT
O [0] + E.
d..)
FEUGCN-2HOP
O(E K [0])
FEDSAGE+
O(E K [0) + E K d-n)
0.2
FEDAVG
O(E 101)
0.2
0.4
In Fig. | we compare the theoretical attack performance, derived in A.p with an actual attack on the links in PubMed. The theoretical results are based on several assumptions (see Thm. that do not apply to the real attack. As shown in the figure, the actual attack is weaker than the theoretical predictions. Notably, these results assume exceptionally strong, albeit unrealistic, attacker with knowledge of Q and p.
Remark. No formal privacy analysis exists for FEDSTRUCT or FEDGCN, making FEDLAP especially appealing. Analyzing their privacy is challenging due to the iterative information exchange in the online phase. In Appendix C.6 we provide arguments supporting the stronger privacy of FEDLAP.
Communication Complexity
Table displays the communication complexity of FEDLAP+ alongside other SFL schemes. The communication complexity is divided into two parts: pre-training, a setup phase to acquire compo- nents necessary for training, and an online phase where the actual training takes place. In the table, E. K, and n represent the number of training rounds, clients, and nodes in the graph, respectively. Moreover, for simplicity, we assume all feature dimensions to be equal to d and [0] to be the model size. Lg and p are the number of layers and pruning parameter of FEDSTRUCT and, to incorporate FEDGCN, we consider the average number of clients that contain neighbors As seen in the table, the online complexity of FEDLAP+ is on par with FEDAVG and FEDGCN but is significantly lower than that of FEDS AGE+ and FEDSTRUCT. In the pre-training phase, FEDLAP+ scales with n, as does FEDSTRUCT and FEDGCN (which does not provide privacy). However, the other parameters are typically much smaller in FEDLAP+ than in its counterparts. Particularly, FEDGCN suffers for large Cavg and d, as can be seen in Appendix
given node, Cave-
7 Experimental Results
In this section, we evaluate the performance of FEDLAP on node classification for varying client counts, and limited number of training nodes (only 10% of the total nodes). We report results alongside the edge homophily ratio h E [0, 1]. which quantifies the proportion of edges connecting nodes with the same label (25). Experiments are conducted six datasets: Cora and Citeseer [26).
PubMed 227. Chameleon (28), Amazon Photo [29]. and Ogbn-Arxi [30]. Our experiments were conducted on machine with 2 NVIDIA Tesla V100 SXM2 GPUs, each with 32GB of RAM.
To assess robustness across different partitioning strategies, we provide results using Louvain and KMeans partitionings in Appendix E The centralized and local settings constitute upper and lower bounds on the performance and are included for reference. We also incorporate several benchmark methods including FEDSAGE+ (5), FEDPUB II., FEDGCN [10], and FEDSTRUCT B Each of these methods share sensitive information that may violate privacy of the node features or links. On
the contrary, both FEDLAP and FEDLAP+ significantly reduce the amount of shared information and does not leak information even under very severe attack threats as shown in Section
Analysis. In Table we report the average accuracy over 10 runs across six datasets with random partitioning. FEDLAP and FEDLAP+ outperform general FL baselines like FEDSGD, FEDSAGE+. and FEDPUB, and remain competitive with structure-aware methods such as FEDGCN and FEDSTRUCT- while providing stronger privacy guarantees. Notably, FEDGCN requires 2-hop aggregation sharing (see Appendix C4 in [B] for discussion), and FEDSTRUCT involves iterative sharing of structural features, both leading to potential privacy leakage.
Performance
FEDLAP excels on homophilic graphs (e.g., Pubmed, Cora) where Laplacian smoothing is effec- tive, but underperforms on heterophilic graphs like Chameleon, where neighboring nodes behave differently. FEDLAP+, by contrast, remains robust across all datasets by operating in the spectral

---

Table 2: Node classification accuracy with random partitioning. Nodes split into train-val-test as 10%-109-80% each
result, the mean and standard deviation are shown for 10 independent runs. Edge homophily ratio (h) is given in brackets.
CORA (h 0.81)
CITISIER 0.74)
PUBMED 0.80)
CENTRAL GNN
83.40: 0.63
70.99 0.32
85.602 D:26
CLIENTS
10 CLIENTS
20 CLIENTS
5 CLIENTS
CLLENTS
CLJENTS
CLIEETS
CLIENTS
PROSGD GNN
65,46 2.45
65.26:
1.37 64.384
1.38
66.84t:
66.53:
1.03 66.11 1:11
84,24
0.29
85,96t
0.19 83.56 0.27
FEDSAGE+
65.80:1 1,72
64.534
1.54 63.624
1,08
66.64:1
0.98
66.57:
0.67
66.24:1 0.89
$4,29
0.37
83,9611
0.23 83.551 0.27
PRnPUR
68 24.22.1:1 1,10
59.
19.17
1.34
47.91
1.98
64.
86:2 0.97
63.30=
1.82
56.00 2.22
$4.13
0.19
84.00::
0.21
83.45 0.22
PROGUN- BROGCN-2HGP
81.48 0.81
#2.224
0.79
82.82
0.73
71.36+
0.60
71.75
0.80
69.71 0.54
55,93
0.29
86.13+
0.34
85.90+ 0.28
PUOSTROUT-S (H2V)
79.02- 0.93
80.01:
1.00
80.09:
0.60
67.71: 0.96
67.51=
1.01
64.54
1.62
65.41:: 0:21
85.40
0.17
85.27 0.25
FEDLAP
80.85:1: 1.24
80.55.1
0.97
80.42:1:
0.69
67.24:
66.29::
63.96.1
1.66
96.27::
0:31
0.19
85.86.1
Funt (ARNOLDI)
79:574 1.00
79.311
1.03 79.42::
80:2
67.302
67.
65.572
1.65
65.02
0:33
85.294
85.052
LOCAL GNN
47 48 1.85 37.59.t 1.12 32.66:1 1.20 $1.93:1
0.64 49.94:2 1.66 40.33 1.20
33.23 0.7
76.77
0.25
72.59 0.41
CHAMELEON (h. 0.23)
AMAZON PHOTO (A- 0.52)
OGBN-ARXIV (A 0.65)
CENTRAL GNN
54.3811 1.60
94.07 0.41
68.041 0.09
SELINNSS
CLONNT
20 ELLINIS
SCLIINTS
CL
CLLUNTS
CCIINTTS
CDCLINTSS
CLIENTS
PROSGDGNN
40.972
35.93
1.62.
34.41 1.95
40:
0.41
89.93=
0,56 19.12 0.59
57.10 0.17
54.07
0.10
51.742 0.20
PROSAGE+
39.96+ 1.17
35.15
1.99
34.59
2.31
91.46+
0.52
89.97
0.58 89.15 0.56
?
TEDPUB
38.45:12.117
34.21:1
2.40
29.41:::
2.44
89.73:1
0.72
88.03
0.76
85.48:1 0.83
59.12:2
0.13
55.501
0.11
52.151
0.12
FUDGCN-2u0e
$1.51 1.46
50.
10.19:::1
1.34
52.044
1.13
93.61
0.28
93.
0.44
95.73d 0:40
66.77
0:13
66.934
0.14
66,89
0.08
PEDSTRUCT- (H2V)
55.65
1.22
55.814
1.09
55.78-
1.68
92.47:
0.35
92,00
0.51
92.51 0.27
65.17 0.16
64.95
0.06
64.94 0.22
PEDLAP
32,91 2.45
32.
2.63
32.85
1.88
92.24
0.44
92.08
92.26 0.36
66.00%
0.26
66.034
0.33
65.93
FEDLAP+ (ARNOLDI)
53,53:t: 1,33
54.31.1
1.59
51.15::
0.91
92.59
0.36
92.14:1
0,56
92.79.t 0.32
66.73:2
0.15 66.2211
0.26 66.061 0.26
LOCAL GNN
36. 06-t 1.53 36, 06.t 1.53 29.53
1.54 24.9 24.98
1.01 77. 27 1.84 60.97 1.52
55 46 0.16 50.43 D. 1. 45.34 0.2.0..1
" FFBGGCN lacks privacy
agareg node festures and 2-hop [6] Also, the official code oveslouks isolated externa neighbors removal. posentially enhancing prediction performance above its actual capubilities
sharre betwees clients, which constinutes privacy breach
shown
60
Upt splnec
OU
FEDLAPs pn0.1 FOLLAN up9)
40
PEOPUO REDGEN Dartreus
PaDGEN TemSraiTe -EDSGD
Peel (Phaa) Banl (Dia)
Panlaar m.D.1
PEDLAP-
POESTRUCT
PIDGCN (Nos Ptina)))
FEDLaP
3 PORPED
50
100
150
200
0.4
10
20
30
Lousain
Bandom
muscation number e
tailiing rato by
number of clienss
partiioning mechods
Figure 5: Left to right: (i) Accamcy vs for various training mitios (Ev)) on Coen (10 elients, madden portitionin); (61) Accuncy vs training ratio on Chameleon
(Kmeans partitioning) (ili) Accuracy num of elients on Cora (candom partitioning): (ir) Accuracy on UGiBN-Ariv (10 clients) on vizious partitioinng methods.
domain and applying truncation, which filters noisy signals and avoids the limitations of smoothing. Though truncation reduces information, it regularizes learning and simplifies optimization, which helps FEDLAP+ perform well in low-label or large-scale settings (e.g., ogbn-arxiv). In summary, FEDLAP+ is more robust on heterophilic and large graphs, while FEDLAP favors high privacy and communication justiiccy--stiiyyiigg slight utility trade-offs in some cases.
Fig. 5 demonstrates strong and consistent performance for FEDLAP and FEDLAP+. Small truncation numbers (r') already yield high accuracy (left), showing that only a few dominant spectral components are sufficient to capture the global structure. Accuracy remains robust across training ratios (mid-left) and scales smoothly with the number of clients (mid-right), confirming that FEDLAP+ maintains stability even under highly partitioned data. On OGBN-Arxiv (right), both methods outperform all alternatives across different partitioning strategies, with FEDLAP+ particularly excelling on larger and more heterogeneous graphs. Note that, in practice, moderate values of r (e.g.. 50-200) provide an excellent balance between accuracy and efficiency, as increasing r further offers only marginal gains. Additional experimental results are reported in Appendix E
Concluding remarks. FEDLAP achieves performance close the centralized setting and signif- icantly outperforms prior methods such as FEDSAGE+ and FEDPUB in challenging settings. It also matches the performance of FEDSTRUCT and even the non-private FEDGCN, while being the first SFL method to provide strong privacy guarantees. By doing so, FEDLAP advances the Pareto frontier in the accuracy-privacy-oo pit--riicccc-mmmmiaaiiiiiio space, demonstrating that strong privacy and low communication overhead can be attained without sacrificing accuracy. Although this paper focuses on node classification, the proposed framework is applicable to any local graph-based task, including edge prediction and link-level inference.
10

---

Acknowledgments
This work was partially supported by the Swedish Research Council (VR) under grants 2020-03687 and 2023-05065, by the Wallenberg AI, Autonomous Systems and Software Program (WASP) funded by the Knut and Alice Wallenberg Foundation, and by the Swedish innovation Agency (Vinnova) under grant 2022-03063.
The computations were enabled by resources provided by the National Academic Infrastructure for Supercomputing in Sweden (NAISS), partially funded by the Swedish Research Council through grant agreement no. 2022-06725.
References
[1] Jonathan M Stokes, Kevin Yang. Kyle Swanson, Wengong Jin, Andres Cubillos-Ruiz, Nina M Donghia, Craig R MacNair, Shawn French, Lindsey A Carfrae, Zohar Bloom-Ackermann, et al. deep learning approach antíbiotic discovery. Cell, 180(4), 2020.
[2] Wenqi Fan, Yao Ma, Qing Li, Yuan He, Eric Zhao, Jiliang Tang, and Dawei Yin. Graph neural networks for social recommendation. In The world wide web conference, 2019.
[3] Weiwei Jiang and Jiayun Luo. Graph neural network for traffic forecasting: A survey. Expert Systems with Applications, 207, 2022.
[4] Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Communication-effie -effcccient learning of deep networks from decentralized data. In Artificial intelligence and statistics, 2017.
[5] Ke Zhang, Carl Yang, Xiaoxiao Li, Lichao Sun, and Siu Ming Yiu. Subgraph federated learning with missing neighbor generation. Neurips, 34, 2021.
[6] Liang Peng. Nan Wang, Nicha Dvornek, Xiaofeng Zhu, and Xiaoxiao Li. Fedni: Federated graph learning with network inpainting for population-based disease prediction. IEEE Transactions on Medical Imaging. 2022.
[7] Fahao Chen, Peng Li, Toshiaki Miyazaki, and Celimuge Wu. Fedgraph: Federated graph learning with intelligent sampling. IEEE Transactions on Parallel and Distributed Systems, 33 (8):1775-1786, 2021.
[8] Bingqian Du and Chuan Wu. Federated graph learning with periodic neighbour sampling. In IEEE International Symposium on Quality of Service (IWQoS), 2022.
[9] Runze Lei, Pinghui Wang. Junzhou Zhao, Lin Lan, Jing Tao, Chao Deng, Junlan Feng, Xidian Wang, and Xiaohong Guan. Federated learning over coupled graphs. IEEE Transactions on Parallel and Distributed Systems, 34(4), 2023.
[10] Yuhang Yao, Weizhao Jin, Srivatsan Ravi, and Carlee Joe- fue-Wong. Fedgen: Convergence- communication tradeoffs in federated training of graph convolutional networks. Neurips, 36, 2024.
[11] Jinheon Back, Wonyong Jeong. Jiongdao Jin, Jachong Yoon, and Sung Ju Hwang. Personalized subgraph federated learning. /CML, 2023.
[12] Wei-Ning Chen, Peter Kairouz, and Ayfer Ozgur. Breaking the trilemma. Neurips, 33, 2020.
[13] Javad Aliakbari, Johan Östman, and Alexandre Graell Amat. Decoupled subgraph federated learning. In ICLR, 2025.
[14] Bank for International Settlements. Project aurora: The power of data, technology and collabo- ration to combat money laundering across institutions and borders. Technical report, Bank for International Settlements, 2023. URL httpp:://www bis oagii.orr/ppuui bttp.ooogg/.bb//opp....... pdf
[15] Ke Zhang, Lichao Sun, Bolin Ding, Siu Ming Yiu, and Carl Yang. Deep efficient private neighbor generation for subgraph federated learning. Proceedings of the 2024 SIAM International Conference Data Mining (SDM), pages 806-814 SIAM, 2024.
11

---

[16] Khac-Hoang Ngo. Johan Östman, Giuseppe Durisi, and Alexandre Graell i Amat. Secure aggregation is not private against membership inference attacks. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, 2024.
[17] Giorgos Bouritsas, Fabrizio Frasca, Stefanos Zafeiriou, and Michael M Bronstein. Improving graph neural network expressivity via subgraph isomorphism counting. IEEE Transactions on Pattem Analysis & Machine Intelligence, 45(1), 2023.
[18] Yue Tan, Yixin Liu, Guodong Long, Jing Jiang, Qinghua Lu, and Chengqi Zhang. Federated learning on non-iid graphs via structural knowledge sharing. In AAAI conference on artificial intelligence, volume 37, 2023.
[19] Dengyong Zhou, Olivier Bousquet, Thomas Lal, Jason Weston, and Bernhard Schölkopf. Learning with local and global consistency. Advances in neural information processing systems, 16, 2003.
[20] Mikhail Belkin, Partha Niyogi, and Vikas Sindhwani. Manifold regularization: A geometric framework for learning from labeled and unlabeled examples. Journal of machine learning research, 7(11), 2006.
[21] Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In ICLR, 2017.
[22] Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. Neurips, 30, 2017.
[23] Richard B Lehoucq and Danny C Sorensen. Deflation techniques for an implicitly restarted amolli iteration. SIAM Journal on Matrix Analysis and Applications, 17(4):789-822 821, 1996.
[24] Keith Bonawitz, Vladimir Ivanov, Ben Kreuter, Antonio Marcedone, H Brendan McMahan, Sarvar Patel, Daniel Ramage, Aaron Segal, and Karn Seth. Practical secure aggregation for privacy-preserving machine learning. In proceedings of the ACM SIGSAC Conference on Computer and Communications Security, 2017.
[25] Jiong Zhu, Yujun Yan, Lingxiao Zhao, Mark Heimann, Leman Akoglu, and Danai Koutra. Beyond homophily in graph neural networks: Current limitations and effective designs. Neurips, 33, 2020.
[26] Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi- Rad. Collective classification in network data. Al magazine, 29(3), 2008.
[27] Galileo Namata, Ben London, Lise Getoor, Bert Huang, and U Edu. Query-driven active surveying for collective classification. International workshop on mining and learning with graphs (MLG), volume 8, 2012.
[28] Hongbin Pei, Bingzhe Wei, Kevin Chen-Chuar Chang, Yu Lei, and Bo Yang. Geom-GCN Geometric graph convolutional networks. In ICLR, 2020.
[29] Oleksandr Shchur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann. Pitfalls of graph neural network evaluation. arXiv: 1.05868, 2018.
[30] Weihua Hu, Matthias Fey, Marinka Zitiik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. Advances neural information processing systems,
2020.
[31] Berkant Savas and Inderjit S Dhillon. Clustered low rank approximation of graphs information science applications. In Proceedings of the SIAM International Conference Data Mining, 2011.
[32] Karl O Friedrich. A besre- bound for functions of independent random variables. The Annals of Statistics, pages 170-183, 1989.
[33] Xiang Li, Kaixuan Huang, Wenhao Yang, Shusen Wang, and Zhihua Zhang. On the convergence of fedavg on non-iid data. In ICLR, 2020.
12

---

A Prediction model with FEDSTRUCT
The proposed SFL scheme in Section Jlligss with the philosophy of FEDSTRUCT 13 by utilizzing explicit global graph structure information to enhance performance. However, it overcomes the limitations of FEDSTRUCT through fundamentally different approach-integratinn integrating this information through the Laplacian. For clarity, we provide a concise overview of FEDSTRUCT below.
In FEDSTRUCT, the prediction for node
V is given by
g. = softmax (h, + ze)
(20)
where h is the node feature embedding (NFE) and 2u the node structure embedding, which encodes structural information of the node. The NFEs h, are computed locally each client by a GNN based on the local node features and local connections, h. = fe, [e,(x,, (X,, Ei, v), where 0, are the learnable parameters of the GNN.
The NSEs ze are generated based on node structure f (NSFs), which encode structural proper- ties of node, such as degree and neighborhood patters,, providing a task-specific representation of the graph topology. Let 8u E Rd. be the NSF node and S the matrix containing all NSFs as rows, [s] ........ _T Particularly, the NSEs are computed
Σ NEV
Aousto, (8u):
(21)
where go, is learnable function parameterized by O,.
The NSFs 8n can be generated using established methods such as GDV or VEC.2VEC. However, these approaches rely on knowledge of the global graph. To address this limitation, [I3] proposed HOP2VEC, which generates task-dependent NSFs, without access to the global graph, by treating them as learnable features optimized dynamically during training.
B Details of the Arnoldi Iteration Method
B.1 Standard Arnoldi Iteration
The Amoldi iteration is an efficient iterative method for approximating eigenvalues and eigen- vectors of large, sparse matrices. Rather than performing full (and potentially eigendecomposition, Arnoldi constructs an orthonormal basis for the so-called Krylov subspace K,n (M, æ) = span(x; Mæ...., M "n-1 x). where æ is some chosen starting vector.
very costly)
Given an orthonormal basis .q..... 4r} for the subspace Km (M, v), the Arnoldi method iteratively computes the next basis vector 4,+1 as
a++1
|rell
Tt Mq:
Σ h4 1=1
(22)
where - q. Mq:- The vectors are also referred to as Arnoldi vectors.
From this orthonormal basis, the method constructs approximate decomposition to estimate some of the eigenvalues and eigenvectors of M.
Note that
[m qm+1re
=qTn,
= -he+1.e
(23)
where the second equality follows since, by construction, g0+1 is orthogonal the previous Arnoldi vectors.
13

---

Using 23 in 22
we can write
Mq:- 9641 [ell +
ha
ha
(24)
Hence, after m iterations the Arnoldi iteration yields the relation
MQ.. m = Qm m. + hm+ Im+11m c
(25)
where Qm 19 ........ 9m the matrix of Amoldi basis vectors, H. E Rmxx is an upper Hessenberg matrix with entries ha - q Mg,, and em is the m-th standard basis vector. The Arnldi iteration is summarized in Algorithm
Equation of M.
25 known as the Arnoldi relation, shows that the eigenvalues of Hm approximate those
Algorithm The Arnoldi iteration for the computation of an orthonormal basis of Krylov space
1: Let M E Raxn This algorithm computes orthonormal basis for Kun (M,x). x)).
2: qi = 2/ 2/|=
3: for
1,..., do
4: r := Mq6
5: for : do
6: h4 = q, r 7: h:::
7: end for
8: he+1.e== = |r]]
9:
if he41, then
return (q1..... -e. H R(x))
11: end if
91+1 r -r/het1.
13: end for
return (q1...., 1m+1 H E Rm++1m)
Specifically, assuming 1,m small, using 25 M can be approximated
M Q H
(26)
Let H = VVVT the eigendecomposition of Hm Then, the eigenvalues of H. serve as an approximation of some of the eigenvalues of M, and the corresponding eigenvectors of M, denoted by u, can be obtained as u = Q v. Substituting this eigendecomposition into (26 yields the approximate eigendecomposition of M:
M U
(27)
where U = Q and U
B.2
Proposed Decentralized Arnoldi Iteration
For later use, we denote by VI [u,, Vi I] the entries of vector v indexed by the set I.
We aim to use Arnoldi iteration estimate the smallest eigenvalues of Lg and their corresponding eigenvectors in decentralized manner across clients while preserving privacy.
Each client knows only the incoming and outgoing connections to its local nodes and does not have other knowledge about the subgraphs of other clients. Formally, Client knows the rows and columns
'The assumption that interconnections between clients are known, ie.. a node in given client knows the existence of a node in another client and the edge connecting them, is both realistic and reflective of several
14

---

of the adjacency matrix A corresponding to its internal nodes E V4, i... Av,: and A.,, and subsequently the corresponding rows and columns of the degree matrix, Dv.; and D.,.
In the Arnoldi iteration, clients need to collaboratively compute
ri
4e+1
|rell
rg = LEqe
(28)
which follows from the Arnoldi update 22 with M Lg.
Carrying out (28 decentralized way requires each Client i compute its local portion rv, (for generic vector r). Effectively, this means performing the matrix-vecter multiplication b= Lgq (for generic vector q), where b, q R" are n-dimensional vectors, and computing the coefficients ha.t 9: Lege in privacy-preservin
way: Neither the clients nor the central server should be able reconstruct the global vectors or q. To achieve this, we decompose by, as follows:
by: (L =(D A)q)v
<Dqq Aq)ı
(Dq)v: (Aq)v.
Dv.u,v, - Av
K
Av,,,
(29)
where K is the number of clients.
We observe that the first term of (29). Dv, ny, can be computed by Client using its local knowledge. However, the second term requires collaboration among clients, as qv, for j * i is unknown to Client i.
Since client i only requires Σj=1 Av. clients can employ homomorphic encryption to securely compute this sum via the server Specifically, each Client j encrypts its local prod- uet Ay. gv, and sends ( HE(A,,v gv,) to the central server, where HE(-) homo- morphic encryption function. The server computes the encrypted sum hy; -Ø h and sends hy, to Client i. Finally, Client decrypts to obtain the required sum ΣØー Av,y, Iv as ΣØ= Av, HD(hy,), where HI((-) is the homomorphic decryption function.
Through this approach, neither the central server nor any Client can reconstruct the components Av, V. qp, for # Furthermore, as by: E IR" has dimension n4 and the remaining n n; entries {qv, vk & i} are unknown to Client i, it cannot reconstruct (dv, V * i) as long as n T4 2 n2, The proposed decentralized Arnoldi iteration is detailed in Algorithm
In Appendix C we formally demonstrate that the proposed decentralized Arnoldi iteration prevents clients from inferring the internal subgraph structure of other clients, thereby ensuring FEDLAP preserves privacy.
B.3 Computational Complexity of the Arnoldi Iteration
Computing the eigenvalues and eigenvectors of graph Laplacian matrix is generally considered computationally expensive. However, FEDLAP circumvents this limitation by leveraging the Arnoldi iteration, technique that particularly efficient for sparse and low-rank graphs, which common in real-world datasets.
real-world scenarios. This setting naturally arises in applications where edges originate locally but terminate in another client's 's subgraph, and the originating client must know the identifier of the destination node. For example, in banking, bank records transaction recipient's identifier (e.g., IBAN). In anti-money laundering applications, this assumption standard [14) Also, in supply chains, a company places an order with a supplier managed by another organization and must identify the recipient entity. Moreover, this setting has been explicitly adopted in prior work on subgraph federated learning, including FedStruct and FedGCN, which further supports its practical relevance.
customer another bank and therefore knows the
15

---

Algorithm 2 The Decentralized Arnoldi algorithm for the computation of an orthonormal basis of Krylov space
1: Let E R clients with client knowing Av,, and A.v, and œy,, for an input vector æ. This algorithm computes orthonormal basis for Km (Lg, æz).
2:
Q
x/ |
3: for ...., K do
4: Client sends HE zty: I2-) to the server
5: end for
6: Server computes Σ 1==1 HE( byy 12)) and sends it to clients
7: Clients calculate | HD E x HE([|æy, I1²))
8: Qy /|
9: for iteration 8 . do
10:
Lg Q
K do 12: for k = 1..., K do
for
Client l sends h end for
HE (Av.v Qun.e) to the server
14:
Server does hv. Ek= (/ and sends hy, to client
15:
Client calculates Σ Av..v. Qv,, (Dv,),)
K k=1 K
17:
TV: Dv,,, k=1 Av. Qve.e
18:
end for
19:
hu 1,.... do
Q
= he
20: for =
21:
for i 1,.... K do
22:
Client i sends HE Q V., V. Tv,) to the server
23: end for
24: Server computes Σ Li=1 HE T rv.) and sends it to clients
25: Clients calculate d1 HD Σ 1= HE(QV,
rv. : Tv, Qv,
27:
end for
28:
11+1, = ||||]:
29:
for = I,.... K do
30:
Client sends HE([|ry,ll I1²) to the server
31:
end for
32:
Server computes Σ K
HE (1,, and sends it to clients
33:
Clients do ||||]
HD
E H
K
34:
het1. |||]]
35:
if hye+1)e then
36:
&Found invariant subspace%
37:
for i = 1, I,..., K do
return (Q...: Rruxe E Rexe) end for 40: end if
38:
39:
41:
Qu1+1 =r/h(4ty) for i = 1, 1,..., do
42:
43:
Qv.((+1) rv: /ve//e
44: end for
45: end for
46: for = 1, 1,..., K do
47: return (Qv,: E p xm Q Qv).(++1 E R"; E Rm h 1)m)
48: end for
16

---

The computational complexity of the Arnoldi iteration for extracting the top r eigenvectors of a sparse matrix of size n x primarily determined by two operations:
1. Matrix-vector multiplication: Each iteration involves multiplying the sparse Laplacian matrix with a vector. This operation has a cost of O(n d), where d is the average degree of the graph.
2. Orthogonalization: The newly computed vector must be orthogonalized against all previous vectors, requiring On r²) operations over r' iterations.
Thus, the total computational complexity after Arnoldi iterations is:
O(r n d n-r
In practical scenarios with sparse graphs (i.e., d < r), the orthogonalization step dominates, resulting in an effective complexity of O(n -r)).
We illustrate this with two widely used benchmark datasets:
ogbn-arxiv (n = 169,343, = 13.7):
For r 100: 0(169,343 3433 x 100²) x 1.69 x 10 operations
For r = 200: 0(169,343 x 200²) x 6.77 x 10 operations
ogbn-products (n = 2,449,029) d 50.5):
-For 100: ((2,449. 4299 x 1002) 2.45
10 operations
For = 200: 0(2,449,02 ,029 x 2002) x 9.80 10 operations
These computations are feasible with standard hardware and can be further optimized using distributed implementations. Overall, the Arnoldi method offers scalable and coaimuunicatio--fffiiee strategy for spectral approximation in federated graph settings.
B.4 Learning in FEDLAP+ with the Arnoldi Iteration
After r iterations of the decentralized Arnoldi iteration introduced in Appendix B B.2 each Client i obtains matrices Qy E RR and H, |rxr (see also Algorithm 2. Since H, shared among all clients, each client can decompose it as
= =.=
(30)
where Σ Rexr is the diagonal matrix of eigenvalues of H, and V Rrxr the matrix of corresponding eigenvectors.
Each client can then compute
Uv Qv V.
(31)
With this, an approximate cigendecomposition of the graph Laplacian can be written as (see (27))
LG UEUT.
(32)
where U is formed by concatenating the matrices Uv.
FEDLAP+ uses this approximation of the Laplacian for learning. Specifically, for node in Client when using the decentralized Amoldi iteration to approximate the graph Laplacian, FEDLAP+ performs node prediction as
g. = softmax (So (X,, Jo, (U,, W)).
Tr(WT ΣW)
C(e, W) (e) + Aree Tr(WT
(33)
The model parameters W are updated
W W W AN Vw
(34)
17

---

C Privacy Analysis of FEDLAP+
In this appendix, provide detailed derivations supporting the privacy analysis presented in Section of the main paper.
Our focus is on the offline phase of FEDLAP+, where clients collaboratively estimate the eigenvectors of the graph Laplacian using the decentralized Arnoldi iteration (see Appendix [B2 and Algorithm 2). Unlike the online phase-whice involves standard model updates and can be protected using estab- lished eeaanccinnanninngg techniques such as differential privacy or secure aggregation thetttoon-hhe the offline phase involves sharing Ainear-algebrat components derived from local graph structure. This creates novel privacy challenges that warrant careful analysis.
In particular, we aim to quantify the ability of an attacker to infer local connections within another client. To this end, we consider a worst-case scenario in which the system consists only two clients: Client I is the target and Client 2 is the attacker. The attacker attempts to infer whether there an edge between two nodes u, v E Vl, the node set of Client This formulated as binary hypothesis test:
Hy: no edge exists between and v, i.e., Aur =
* H1i edge exists between and i.c., Aue L.
We study the distribution of the log-likelihood ratio (I.RR) associated with this test and analyze how well the attacker can distinguish between the two hypotheses.
Structure of this appendix.
The remainder of this section is organized follows:
Section
introduces the attack model.
Section
introduces the assumptions made for the analysis.
Section
provides the full proof of Theorem I which characterizes the distribution of the
LLRs under both hypotheses.
Section C.4 contains the proof of Corollary T which provides expression for the Kull- Leik-ee divergence between the two LLR distributions and analyzes its dependence on key parameters such as the truncation rank r. the number of nodes n, and the connection probability p.
Section C.3 derives the attacker's true positive rate (TPR) and false positive rate (FPR), and uses these compute the corresponding precision and recall. This analysis enables to quantify the privacy guarantees offered by FEDLAP+.
C.1 Attacker model
This appendix gives detailed account of what the attacker can observe in the decentralized Amoldii protocol.
What the attacker observes.
Recall the local block identity (Equation (16))
by. DV..V. dv Σ
Av.y, qv,
(35)
j=1
From the secure aggregation step, the attacker (client i) receives only the aggregated vector
K TV: Σ
Av. gv
j=1
The attacker also knows the adjacency blocks Av. that correspond its own outgoing/incoming inter-client edges. Thus the attacker has n, linear constraints:
A, q Tv.
A,-, [Av.
Ap, Ap. Av.
where q,4 19 bi is the stacked vector of unknown spectral blocks of other clients. Since n1 n, in typical settings, the system is underdetermined and infinitely many q-i satisfy the
18

---

observed equations. Consequently, the attacker can only produce an estimate 4i Collecting the estimates of Q Qii; pyliis as E Rn-R;xr, we can write
② Qu,ill s.
(36)
Using the Arnoldi relation (14) and the public matrix H,, an attacker with estimate Q, forms
U
D Q + A v. Qv. QH,
Hence, the attacker faces the reconstruction problem
AQ
(37)
where Ā A-i,-i is the unknown target adjacency block and Q Qma,: : is noisy (the attacker's estimate). Note that equality in (37) holds only when o = 0 and hy+1, = 0. The attacker must also know Di to calculate U. The attacker then performs the following steps: (i) obtain U = Q r., (ii) evaluate the log- likelihoood ratio LLR,,v for the two hypotheses using U, and (iii) decide H1 whenever , 2 y for some threshold E R.
C.2 Assumptions
C.2.1 Modeling assumptions
To enable tractable and rigorous analysis, assume that the graph connections follow Bernoulli distribution. This setup corresponds to a simplified instance of the Stochastic Block Model (SBM), common generative model for graphs with community structure. of an edge between two nodes depends on whether they belong to the same community (p) or different communities (g). Specifically, p the probability of an intra-community edge and q the probability of an inter-community edge. In our analysis we consider the case where the attacker assumes p = 9, meaning all node pairs are connected independently with equal probability. While this assumption may not perfectly reflect community-structure conservative and aggnssi-- baseline. realistic scenarios, adversaries are unlikely to know the exact community assignments. making the q setting a reasonable approximation for worst- case analysis. Moreover, both the SBM and Bernoulli model are widely adopted the graph learning literature analytical tools, allowing us derive privacy guarantees that remain meaningful under minimal structural assumptions.
the SBM, the probability
real-world graphs, it provides
C.2.2 Worst-case scenario with two clients
We assume a scenario with two clients, where Client 1 is the target and Client 2 is potentially malicious client attempting to infer private connections within Client 1. This models the worst-case setting where all other clients collude against a single target client.
C.2.3 Low-rank approximation of adjacency matrix
The attacker observes a low-rank approximation
U AQ
(38)
To simplify the analysis, in favor of the attacker assume the equation holds with equality and therefore o = and 1,r = However, the attacker cannot reconstruct the exact adjacency matrix Á from this observation, even with full knowledge of Q
Note that realistic adjacency matrices include clusters and are typically well-approximated by low rank matrix 31 Hence, even with full knowledge of Q À cannot be uniquely determined by observing U.
C.2.4 Delocalization and Orthogonality of Eigenvectors
To derive the analytical form of the privacy guarantees in Corollary assume that the columns of are approximately orthogonal, i.c., Q Q Ir, and that Q is delocalized, meaning its columns
19

---

are spread uniformly over the unit sphere. This implies Q.,,1 = r/n for all v V1, where r is the truncation rank and n is the number of nodes in Clientl.
These assumptions are grounded in empirical observations of spectral properties real-world graphs, particularly under stochastic models such the SBM and random regular graphs. However, stress that they are not necessary for our privacy guarantees to hold. They are used purely to simplify the derivations and enable closed-form analysis.
Assuming delocalization and orthogonality gives the attacker more power than in most realistic settings. For instance, since the actual number of nodes is n = R1 + R2 > f1, the true norm !!,,,.1?? often smaller than r/n, which decreases the attacker's ability to distinguish between hypotheses. As suggested by the KL divergence expression in Corollary (see also (55) below), smaller r /nn reduces statistical distinguishability, thereby enhancing privacy. Thus, our assumptions result in a conservative (i.e., worst-case) privacy analysis, further highlighting the robustness of our guarantees.
C.2.5 Central Limit Theorem applicability
Lemma C.1
shows that the multivariate Lindeberg Central Limit Theorem (CLT) holds for our setting.
To address finite-sample effects, we refine this analysis using the multivariate Berry-Esseen the- orem [32]. By Lemma C.2. the deviation of the empirical LLR distribution from the Gaussian limit scales ErrorcLT O(1 np)) ensuring the validity of the CLT approximation even for moderate-sized graphs.
This bound clearly shows that the CLT approximation improves rapidly with larger n or denser graphs (larger rep). Even for moderate-size real-world graphs, where p is small but n in the thousands, the approximation remains accurate.
Importantly, this assumption large used only to simplify the derivation of the LLR distribution; it does not weaken privacy guarantees for smaller graphs. In practice, the attacker's 's real-world infer- ence capability weaker than predicted by the asymptotic bound. As confirmed our experiments (see Fig. 4. the theoretical bound remains conservative, and FEDLAP+ continues to provide strong privacy even for finite, moderately sized graphs.
Lemma C.1. For i E nl, let c; E IR" where - O(1/n). and let B, Ber(p), [0. 1]. Define the random vector y = Σ B,C Then, for large ni, we have
~ C. c)
(39)
where C = [ei...... cal' e Raxr
Proof. Let μ; = E[B.c] = pe,, and define the centered random variable ú, = (Br - p)c, To invoke the multivariate Lindeberg CLT, we verify the Lindeberg condition:
E
l0 1 1100.1 evn)] 0 as n 00.
(40)
Since B, - E {-p, 1 - ph. we have | S max(p, 1 p)l|c,l O(1/vn). Hence, (40) is
upper-bounded as
U. 1 2 c/m) s 1 E e/n)] = 011/n) - 0 as 00.
(41)
Thus, the Lindeberg condition is satisfied. Since the total covariance is
Cov(ū,) = p(1 - = =
(42)
we conclude the proof by invoking the multivariate Lindeberg CLT.
20

---

Lemma C.2 (Berry-Essean bound for Bernuulii graph models). Let [Au)}]= be independent
Bernoullipp) random variables and define the normalized zero-mean vector
(Au.: ppppppp 'Q,
V Vnp(1 - p)
where Q RuxT is an orthonormal matrix satisfying Q²Q=1
Then E[a] and Cov(x) 1--
Let 2, denote the cumulative distribution function (CDF) of the r-dimensional standard normal distribution. Then, by the multivariate Berry- Fsseen theorem (32, the deviation of the distribution of x from the Gaussian limit satisfies
Auj p| (np(1 p))
Vrep[1 - (
o
sup DER"
- C
where C >> O is absolute constant independent of n. P, In the sparse-graph regime with small this simpliftes to
ErrorcLr = 0
(43)
Proof. Each coordinate of æ is a normalized sum of i.i.d. centered Bernoulli(p) variables with variance p(1 - p). The univariate Berry-Esseen bound implies convergence to normality at rate h///npp11-1 p)). Since Q is orthonormal, linear combinations of these coordinates preserve the same rate in the multivariate case [3]. For sparse graphs (p< 1), the factor (1 p) is absorbed into the constant, yielding (43).
C.3 Proof of Theorem
Following the assumptions in Appendix C.2.1 let the connections in Á {0, 1 be drawn independently from a Bernoulli distribution with parameter p. Based on the attack model (38), the attacker's goal is to estimate specific entries A to infer connections between nodes and within Client 1. Using Bayes, we write the posterior distribution Auo as
PPU Aw =1) P(Á = 1(U)= PP(UIÁme = + (1-)) =0)
(44)
From 38
we note that
U. = -=:=
Amn
(45)
Hence, each row U is given by of scaled independent Bernoulli random variables and ||@...1 (1/n). Therefore, Lemma C. applies and we can approximate the distribution U u,: as
U ui N E),
(46)
where Q and Σ = p(1 - Q) "Q row u in U, we find that
Q. By using 46 and by noting that Avo only influences
Un ANw = N(n, E) U Un. Amm =0 ~ N(p Q Σ)
(47)
(48)
which, after some algebraic manipulations, results in the LLR
PiU 1)
LLR (..(( log
(49)
P 0)
1
= =U,, a.:
l + Qu.) -'1 0.:
(50)
2
21

---

By using 47
48 and noting that (50) is linear transformation of a Gaussian vector under the two
hypotheses, we obtain
1
LLR(A.)))AL = =1~
2
(51)
2
1
LLR(A.)))Auu) - N~
-
(52)
where a == Q Σ 'Q. This concludes the proof.
C.4
Proof of Corollary
Based on the orthogonality assumption in C.2.4 the columns of Q are orthogonal. Therefore,
1
Σ
(53)
p(1 p)
Also, based on the delocalized assumption in C.2.4 Q has delocalized rows, and it follows || P
r/n. Therefore, approximate in Theorem as
(54)
p(1-p)
np(1 p)
Note that the approximation of a is independent of and v.
Next, we consider the KL divergence between the two LLR distributions. Noting that the LLR distributions in Theorem I follow Normal distributions with the same variance, we have that
(LLR(A.)) Age - =0) 2 2mp(1 -p) (55)
DKL Pr (LLR(Aw)) Awv = ||
where the last step follows from
54 This concludes the proof.
C.5 Attack Performance and Privacy Guarantees
In this appendix, we derive the TPR and FPR for the attacker and discuss the resulting privacy guarantees.
We consider the LLR distributions for a given node pair (u, v) under the two hypotheses. From Theorem we have
a 2.
H1 LLR N
(56)
HO LLRg N
2 2
(57)
Using this, for given threshold 7 E R, we can derive the true positive rate (TPR) and false positive rate (FPR) as
7
TPR P(LLR > 7 H1) +
(58)
Va
7 (7+ 2
FPR P(LLR >7 Ho))
(59)
Va
where (xx) is the cumulative distribution function of the standard normal Gaussian distribution.
Real world graphs typically sparse. Hence, there will be strong imbalance between the two hypotheses. For this reason, we assess the attacker performance via precision and recall. The precision (P) and recall (R) can be expressed as
pTPR P pTPR + F)FR
(60)
R = TPR.
(61)
22

---

Together, precision and recall measure the attacker's s ability to correctly infer which pairs of nodes are connected. Given the distributions of TPR and FPR under our worst-case attacker model, one can compute these values and generate the corresponding precision-recall curves. In Fig. 3 in the main paper, we show this relationship for varying values of the truncation rank r, number of nodes n, and connection probability
Importantly, for any fixed and p. our analysis shows that is possible to select value of such that
P R51.
This inequality is a key indicator of privacy in our setting. Intuitively, when the sum of precision and recall falls below one, the attacker performs worse than trivial guessing. For example:
If the attacker guesses all node pairs connected, they achieve Recall 1 and Precision x 0.
If the attacker guesses all node pairs are disconnected, they achieve Precision and Recall 0.
In both cases, P + R~ 1. Thus, R < 1, the attacker's best strategy reduces to guessing either everything connected nothing is-neither of which reveals any meaningful information about individual inter-client connections. This result underscores the strong privacy guarantees of FEDLAP+ under the analyzed threat model.
C.6 Privacy analysis of Subgraph Federated Learning methods
In this section, we provide a more detailed discussion of the privacy guarantees offered by FEDLAP and contrast them with those of existing SFL approaches, notably FEDSTRUCT and FEDGCN. We also discuss the challenges in conducting a formal privacy analysis for these baselines.
C.6.1 Two-Phase Privacy Perspective
To structure our privacy analysis, we divide FEDLAP into two conceptual phases:
This phase occurs once before training begins and is responsible for com- puting structural components using the Arnoldi iteration. It involves exchanging partial results of matrix-vector multiplications (i.e., Aq) but does not share raw adjacency or feature information.
Offline phase:
This corresponds to standard FL. training and introduces no additional privacy risks beyond those already known in FL. Any conventional commonly used in FL- differential privacy or secure aggregation- can be directly applied this phase.
Online phase:
mechanism
As result, the main privacy concern restricted to the offline phase, and in our paper, we provide a formal analysis of this phase under a worst-case scenario. Even assuming a strong attacker with access to all intermediate values (e.g., U = ÄQ and Q). we have demonstrated in Appendix C that inferring intra-client edges becomes infeasible under reasonable sparsity and rank conditions. This analysis establishes FEDLAP'S privacy guarantees on firm theoretical foundation.
C.6.2 Comparison with FEDGCN and FEDSTRUCT
No formal privacy analysis exists for FEDSTRUCT or FEDGCN, making FEDLAP especially appeal- ing. Furthermore, applying our privacy framework to these methods is not straightforwward due the nature of the information they exchange:
FEDGCN shares aggregated node features-ttpicall the sum of features of neighboring nodes. As shown in [16), even secure aggregation offers weak protection against membership inference attacks. Moreover, when node features are sparse and structured (e.g., binary encodings of names), reconstruction becomes alarmingly feasible.
Consider a toy example where node features encode ASCII binary representations of account names:
23

---

Alice:
[01000001, 00000000,111111000000000 01101001, 01100011, 01 01000001
Bob: [01000010, 01101111, 01100110 00000000, 00000000]
Sum: 000000001,00000011,,,0000000000, 10100000110000000000000000001000 101000 001100101]
An attacker with access to this aggregated sum precompute the sum of known character encodings and match the result, effectively inferring sensitive identities. When nodes partic- ipate in multiple aggregations, the adversary obtains overlapping constraints, compounding the privacy risk.
FEdSTruCE introduces a large learnable structure matrix S, which is iteratively updated and shared across clients during training. This makes the privacy analysis highly nontrivial. Although its offline setup phase may potentially be analyzed using our black-box approach. the online phase presents serious challenges. The continuous sharing of gradients with respect to S, and the exposure of global model updates, pose significant risks that are difficult to quantify formally. The authors of FEDSTRUCT acknowledge this by including an attack in their Appendix G.I, which demonstrates concrete leakage scenarios.
Despite these challenges, we provide the following intuitive arguments for why FEDLAP offers stronger privacy guarantees:
FedLap reduces the need for direct structural feature sharing, instead relying on local matrix-vector computations through Amoldi iteration.
The structural information shared is limited and one-time (offline), unlike FEDSTRUCT, which exposes evolving parameters over training.
The decomposition used in FEDLAP+ allows for distributing only local structural compo- nents (i.e., relevant rows of U), further minimizing exposure.
D Convergence guarantee of FEDLAP+
We analyze the smoothness of the spectral regularizer establish the convergence guarantee of FEDLAP+ under the standard FEDAVG framework. Our online loss is defined as
R(W) Tr(WT AW) Tr(W W)
L( (0) Azeg R(W),
(62)
where (f) the supervised loss (e.g., cross-entropy). is the diagonal matrix of Laplacian eigenvalues, and W contains the spectral coefficients. To ensure the convergence of FEDAVG, examine the smoothness of the regularizer R(W).
Since R(W) is scale-invariant (R(aWW) R(W) for any 0), we normalize W to have unit Frobenius norm [|| = 1) after each local update. On the unit sphere, the gradient of ((W) is given by
V R(W) 2(AW W TT AW)).
(63)
This gradient is Lipschitz-comtinuuus. For any W,, We with W f| = [22ll 2/1 = 1, and using ||A||2 Amax. we have
(R((W,) VR(W2) 2) < 8Amax W
W2ll.
(64)
Hence, R(W) is smooth with Lipschitz constant LR S 8Amax- Since (o) is also smooth with constant [ (sm) the overall loss L(0) is smooth with
I, (sm)
I, (sm)
+ Areg Amax-
(65)
Convergence of FEDLAP+. By the smoothness of L(0) and standard results on FEDAVG conver- gence [33, FEDLAP+ inherits the same convergence guarantees under typical assumptions, i.e.,
[|V
(66)
where T' is the total number of communication rounds.
24

---

E Additional Results
E.1
Performance under different partitioning methods
Table presents the node classification accuracy of FEDLAP and FEDLAP+ alongside various previous SFL methods across six benchmark datasets using three partitioning strategies: Louvain, Random, and KMeans. Each experiment involves 10 clients with a 10%-10%-800 train-validation- test split, and results averaged over 10 independent runs. The Central GNN baseline remains fixed across partitionings, as is trained on the full graph. Among the partitioning strategies, Louvain generates community-based clusters with fewer inter-client edges, while Random and KMeans typically lead to more fragmented structures and higher inter-client dependencies, making learning more challenging.
As expected, Local GNN suffers most under Random and KMeans partitioning due to missing neighborhood information, especially on datasets with strong structural dependencies like Cora and PubMed. This highlights the importance of collaboration in distributed graph learning.
FEDLAP+ consistently delivers the highest or near-highest accuracy across all datasets and parti- tioning settings, even under challenging conditions such as Random partitioning on Chameleon or OGBN-Arxiv. Its robustness and strong performance across both high- and low-homophily graphs demonstrate its ability to preserve essential graph information while respecting privacy constraints. This makes FEDLAP+ a practical and reliable solution for real-world SFL applications.
FEDSTRUCT also shows strong performance, particularly under more difficult partitionings, indicating that sharing structural information is effective for learning. However, it lacks privacy guarantees since it requires exchanging graph structure during training. The effectiveness of FEDSTRUCT supports the key idea behind FEDLAP+, which is designed to capture structural signals without directly sharing sensitive graph information.
In contrast, FEDGCN achieves competitive performance but compromises privacy by transmitting aggregated node features (see Appendix C.6.2). FEDSGD and FEDS AGE+ generally underper- form, especially under Random and KMeans partitions, highlighting their limitations in leveraging distributed graph structure.
Overall, FEDLAP+ demonstrates a clear advantage by achieving high accuracy across all settings while preserving privacy, establishing the most robust and effective method among the compared approaches.
E.2 Hyperparameters
In the following we provide the hyperparameters used in the experiments, obtained through grid search optimize performance. In particular, Table[coontai for the different datasets, the learning rate X, the weight decay in the L2 regularization, the number training iterations (epochs), the regularization parameter Arg. the dimensionality of the NSFs, dg the truncation number r, and the model architecture of the node fcature and node structure feature predictors, fo o, and 90,, respectively.
E.3 Truncation Number Effect
In this experiment, we evaluate the sensitivity of FEDLAP+ to the truncation number r, which determines how many eigenvectors of the graph Laplacian retained in the spectral representation. In Fig. 6 we plot the classification accuracy as a function r across three datasets, each exhibiting different levels of homophily and structural characteristies:
Chameleon (left): heterophilic graph where Laplacian smoothing typically less effective. We observe that increasing r significantly improves performance, particularly at low r, but the gains saturate around r = 100. Higher training ratios consistently lead to better accuracy.
CiteSeer (middle): A moderately homophilic dataset where performance remains relatively stable across wide range of values of r. This indicates that small number of eigenvectors is sufficient to capture the relevant structural information in this dataset.
25

---

Table 3: Node classification accuracy for different partitioning. The results are shown for clients with 10%-10% 80% train-val-lest split. For each result, the mean and standard deviation are shown for 10 independent runs, Edge homophily ratio (b) is given in brackets.
deviaii
COBA (h 0.81)
CITESEER 0.74)
PUBMED 0.80)
CENTRAL GNN
83.40:1 0.63
70.99:t 0.32
$5.60 0.26
LOUVAIN
RANDOM
KMPANS
LOUVAIN
RANNOM
KMRANS
LOUVAIN
RANDOM
KMRANS
FROSGD GNN
#1.41 1,24
65.26:
1.37
67.02
0.86
69.99:
66.53
1.03 67.05 0.67
55,05
0.32
85,96
0.19
84.32
FEDSAGE+
81,171 1,26
64.534
1.54
66.481
1.54
70.32:1
1.06
66.572
0.67 67.154 0.66
$5.07 0.32
83,974:
0.23
84.321 0.16
ProPun
78.59 1.31
59.17
1.34
61.21
1.85
68.55:
0.85
63.30=
1.82
63.794 0.87
$4.54 0.22
84.00:
0.21
83.83 0.56
FEDGCN-2HOP
80.82:2
1,20
82
02.22.1:0
0.79
81.31
1.07
71
71:28:
0.48
71.75
0.80
70.71:: 0.64
86.
10::
0.32
13:1
0.34
85.74
0.24
PROSTROUT- (HIVV
81.72+
0.84
80.01:
1,00
79.81
1.02
69.23cb
0.91
67.51
1.01
68.17
0.70
55.01
0.29
85.40
0.17
85.20
0.25
TEDLAP
81.60:1
80.55.1
0.97
80.79:1
1.22
66.2911
67.188:
1.16
$4.18:2
0.34
85,991
Funt (ARNOLDI)
82.01
79.311
1.03 79.88
70:07
67.30
67.882
0:83
65.16
0:52
85.294
85.182
0.31
LOCAL GNN
75.01 2.25 37.59L 1,12 44.951 3.28
59.50:: 1.34 40.33:2 1.20 50.27 6.17
81.71: 0:41
76.771
0:25
80.31 0.40
CHAMPLEON (A. 0.23)
AMAZON PHOTO (A 0.82)
OGEN-ARXIV (A. 0.65)
CENTRAL GNN
54.3811 1.60 RANDOM
94.07
68.041 0.09
LOUVAIN
KMBANS
LOUVAIN
RANIUM
KMBANS
LOUVAIN
RANDOM
KMEANS
PROSGD GNN
49. 02.2 1,50
35
97:t 1.62 38.33 1.25
93.60: 0.38
89.93
0,56
90.424 0:43
66,70 0.18
$4.07 0.10
56.322 D.
PEDSAGE+
48.60 1.84
35.15
1.99
38.324
1.24
93.52+
0.39
89.97
0.58
90.46- 0.34
?
TEDPUB
40.44: 1,86
34.24:1
2.40
34.70:1
2.10
68,
74: 1.70
88.03:2
0.76
87.
0.99
68.50
0.13
55.501
0.11
58.81
0.12
PUDGCN-2u0e
49.93 1.42
50.19:
1.34
49.974
1.74
93.19:t
0.39
93.
0.44
95.624: 0.43
65.18
0:33
66.934
0.14
66.20
0.20
PEDSTRUCT (31VV
55.72
1.82
55.81
1.09
55.20:1:
1.43
93.73
0.34
92.00
0.51
92.62::
0.39
65.62 0.17
64.95
0.06
65.07 0.23
PEDLAP
32.81 2.41
32,9884
2.63
33.34
2.37
93.28:t
92.08
92.50
0.45
66.73-
0.38
66.03+
0.33
05.98
FEDLAP+ (ARNOLDI)
54.24 1,80
54.34:t
1,59
53.954
1.94
93.70:1
0.30
14:14:2
0,56
92.53a
0.37
68.84
0.11
66.221
0.26 66.56
66.561 0.26
LOCAL GNN
47. 37.69-t22 2.20 29. .3.. 1.54 30.90:t
0.87 91.26
0.57 77.62 0.84 78.75
1.25 67.883
0:14 50.43 0.15 55.65 0.12
FFEGCCN lacks privacy
shared between clients, which constinutes privazy breach Also, the official code overlooks isolated external neighbors removal, potentially enhancing prediction performance above its actual capubilities
aggregared node features and 2-hop
shown
16
Table 4: Hyper-parammetrs of the datascts.
CoRA
CereSaue
PusMua
CHAMILEUN
AMAZON Pauroo
OUBN-ABXXY
0.003
0.002
0.001 0.0003
0.001
0
0.001
WEIGHT DECAY
0.0002
0.0005
0.0001
EPOCHS
100
100
150 1
100
150
1000
Asso
1
0.1
1
$12
1024
256
1024
512
128
100
100
75
OT LAYERS
[1433,32, 16, 256.71 (512,64.7]
(3703.128.64.64.6
1500.256.128.64.3)
12325.256.188.5
[745.256.8]
1128.128.64, 64,40]
O, LAYERS
1256,128,64.6]
[256, 64,3]
[1024.5)
[512.128.8]
[1024,40]
Amazon Photo (right): A strongly homophilic dataset where accuracy is consistently high, and increasing r yields marginal improvements beyond r = 50. The method is more robust the choice of r in this setting.
These results show that moderately sized (e.g.. r = 100) is sufficient for good performance across a range of datasets and label ratios. Moreover, they validate that spectral truncation effectively reduces model complexity while preserving predictive power, supporting our design of FEDLAP+ for communication-effiiene and privacy- privacy-preserviie preserving SFL.
E.4 Regularization Coefficient Effect
In Fig. 7 we analyze the sensitivity of FEDLAP and FEDLAP+ to the regularization strength Areg- which controls the influence of the Laplacian smoothing term in the optimization objective.
Across all three datasets, we observe that FEDLAP is sensitive to the choice of Areg very small (Areg 0) or very large (Areg 100) values degrade its performance. This behavior reflects under- and over-regularizzatio, respectively. Optimal performance is typically achieved for intermediate values such Arg 1 or 5. where structural information is effectively leveraged without overwhelming the learning signal.
In contrast, FEDLAP+ shows remarkable robustness to the choice of A Its performance remains relatively stable across a wide range of values. This robustness stems from its spectral truncation mechanism, which implicitly regularizes the model by discarding noisy feequerey eigenvectors.
26

---

D FEDLAP tr-0.1
PEDLAPS tn-02
PEDLAP m-0.3
PEOLAP tr-0.4
FEDLAP- tn-0.5
Chameloon
CiteSeer
74
94
top- accurccy
60
top-1 accoracy
top- aucuracyy
70
92
68
50
50
100
130
200
50
100
150
200
100
150
200
truncation number
truncation number y
truncation number T
Figure 6: Eftect of truncation number node classification accuracy for FEDLAP+ three datasets (Chameleon. CiteSeer, Amazon Photo) under varying training label ratios. Results demonstrate that increasing generally improves accuracy, with diminishing returns beyond a moderate value (c.g., r 100). Each curve corresponds to different training ratio tr E 0..1, 0.3, 0.3, 0.5..
FEDLAP
FEDLAP+
Cora
PuhMed
CiteSeer
87
68
top- accuracy
75
85
70
84
66
65
83
65
0.5
5
10
100
0.5
5
10
100
0.5
5
10
100
Regularization Coefficient Areg
Regularization Coefficient Areg
Regularization Coefficient Aveg
Figure Effect regularization coefficient Areg on node classification accuracy for FEDLAP FEDLAP+ three datusets (Cora, PubMed, and CiteSeer). Each represents accuracy given value Xue E [0, 1, 10, 100).
As result, FEDLAP+ benefits less from explicit tuning of Axe. making it more reliable option in practical scenarios where hyperparameter tuning may be limited or costly.
This robustness further illustrates key advantage of FEDLAP+: by incorporating structural priors in the spectral domain, inherently mitigates the need for aggressive regularization, simplifying training and improving stability across diverse datasets.
Communication Cost
Fig. g compares several SFL methods across three datasets terms accuracy, communication cost, and privacy. The baseline FEDSGD has the lowest communication cost but suffers from low accuracy. FEDGCN offers strong accuracy and low communication cost but lacks privacy, it directly shares aggregated node features. FEDSTRUCT achieves high accuracy but has poor communication efficiency and does not provide privacy guarantees. FEDS AGE performs poorly in all aspects, with high communication cost, low accuracy, and no privacy protection. In contrast, FEDLAP+ is the only method that performs well across all mnmeensions-acheviinn high accuracy, maintaining low communication cost, and preserving balanced choice for privacy-sensitive SFL settings.
it the most practical and
NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
27

---

PEDSCD
PEDSTRUCT
FEDSAGE
FEDGCN
FEDLAP+
Chamekon
PulMed
Ogha-Arsiv
86
65
50
Accuracy
85
60
40
84
55
10
10'
10
10'
102
10
10
102
Communication Cost
Communication Cost
Communication Cost
Figure & Comparison of accuracy versus communication cost for different SFL models on three dutasets: Charnleon,, PubMed. and OGBN-Arxiv The communication plotted logarithmic scale visualize the variation several orders magnitude.
Justification:
The abstract and introduction clearly describe the contributions and accurately reflect theoretical and empirical results presented throughout the paper.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: The paper explicitly discusses limitations related to computational complexity and assumptions in the privacy analysis (Sections and 6).
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors encouraged create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
28

---

If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't It acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed
penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: All theoretical results, assumptions, and complete proof' are provided clearly in Sections 4, 5, and detailed in the Appendix.
Guidelines:
The answer NA means that the paper does include theoretical results. the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the suppiemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: The experimental setup, hyperparameters, datasets, and training details neces- sary for reproducibility are fully documented in Sections 6 and the Appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, descríbing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm.
29

---

(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is new model (e.g.. a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d)
We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
The code is openly accessible, and link is provided at the end of the contributions section, including clear instructions for reproducing the experimental results.
Justification:
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips... cc/
public/guide httil///uuiide//ooeeuusmsssssss
for more details.
While we encourage the release of code and data, we understand that this might be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed run reproduce the results. See the NeurlPS code and data submission guidelines (https ctfps..cc/pubbll httppppwwpppppspppppppppppaaaaep http://uudddee/eeeubbbbssss.ee wwt.iiiissiiiiiiiiiiiiooiii for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: All training and testing details, including hyperparameters, data splits, and optimization procedures, are explicitly described in Section and the Appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can provided either with the code, appendix, or as supplemental material.
7. Experiment statistical significance
30

---

Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: Experimental results include confidence intervals, clearly reporting standard deviations and statistical significance across multiple runs (Tables Figures in Section 6).
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results accompanied by enror bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall
run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report I-sigma eтror bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [No]
The paper currently does not include explicit details about the computational resources required; this will be provided in the supplemental material upon acceptance. The paper introduces new framework and computational resource details are not crucial for understanding or replicating the main contributions and their impact.
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer: [Yes]
Justification: The paper complies fully with the NeurIPS Code of Ethics, involving no ethical concerns or misuse.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
31

---

If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. there a special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: The paper discusses positive societal impacts by enhancing privacy and communication efficiency federated learning setups. No negative societal impacts were identified.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative socictal impacts include potential malicious unintended uses (c.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper does not involve datasets models with high risks for misuse.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
32

---

Question: Are the creators or original owners of assets (e.g.. code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: All datasets and existing models used are clearly cited with references and licenses properly respected, as detailed in Section and the Appendix.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include a URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g.. website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperssi thcode. com datasets has curated licenses for some datasets. Their licensing guide can help determine the license dataset.
For existing datasets that are re- re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. If this information is available online, the authors are encouraged to reach out to the asset's 's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
The paper does not introduce any new datasets, models, code assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: The research presented in this paper does not involve crowdsourcing human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
33

---

15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: The research does not involve human subjects and thus does not require IRB approvals.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, or originality the research, declaration not required.
Answer: [NA]
Justification:
The research does not utilize large language models as part of its core method-
ology.
Guidelines:
The answer NA means that the method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy /tttps://neuriii www.erippsccccoooeeeeee / /LLM) for what should or should be described.
34


Reviews:
[{"review_id": "2vjf8itZQ3", "reviewer": "Reviewer_HaMS", "summary": "This paper proposes FEDLAP and its spectral variant FEDLAP+, novel frameworks for subgraph federated learning that leverage Laplacian smoothing in both spatial and spectral domains to capture global graph structure while preserving privacy. By avoiding the exchange of sensitive node features and using a decentralized Arnoldi iteration for efficient spectral decomposition, the approach reduces communication overhead and enhances scalability. The authors provide formal privacy guarantees and demonstrate through extensive experiments that FEDLAP achieves competitive or superior accuracy compared to existing SFL methods, especially on large or heterophilic graphs.", "questions": "1. The privacy guarantees rely on strong assumptions, such as attackers having access to certain spectral components. Could the authors elaborate on how realistic these assumptions are in practice? \n2. While FEDLAP+ improves performance on heterophilic graphs, the base FEDLAP model performs poorly in such settings. Could the authors provide more insight into this limitation?\n3. The spectral truncation parameter  𝑟 plays a key role in FEDLAP+.  Can the authors provide more guidance on how to choose it across different datasets?\n4. In real-world federated settings, the graph structure may evolve over time. How adaptable is FEDLAP/FEDLAP+ to dynamic graphs? Can the spectral components be incrementally updated, or must the entire process be rerun? \n5. On Chameleon, FEDSTRUCT outperforms FEDLAP. Could the authors explain the limitations of Laplacian smoothing in these cases, and whether hybrid approaches (combining spectral and feature-level smoothing) might help?", "limitations": "YES", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "1. This paper presents a novel, privacy-preserving approach to subgraph federated learning using Laplacian smoothing and spectral methods.  It offers strong theoretical grounding, including formal privacy guarantees, and demonstrates competitive or superior performance across multiple datasets.  The proposed method reduces communication overhead and scales well.\n2. The privacy analysis relies on idealized assumptions, and the method is mainly tested on node classification, limiting its generality. FEDLAP underperforms on heterophilic graphs, and the computational cost of spectral decomposition is not fully discussed.", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the thoughtful and detailed feedback, which has helped us improve the paper. We believe we have addressed all of your comments thoroughly and satisfactorily. If our responses resolve your concerns, we would be grateful if you would consider updating your score accordingly.\n\n## WEAKNESSES: ##\n\n**Note**: We address the idealized assumptions in the response to your Question 1 and the comment on heterophilic graphs in the response to your Question 2. \n\n**Generality beyond node classification.** FedLAP+ is designed as a general privacy-preserving framework that leverages structural information (such as connectivity patterns and degree statistics) across clients in a decentralized setting. It naturally decomposes the SFL problem into two phases:  \n- Offline Phase: Executed once before training, this phase privately extracts useful graph-level structure without sharing node features or labels.  \n- Online Phase: Identical to standard FL, this phase supports any local graph learning task, including node classification, edge prediction, or link-level inference.\n\nOur primary focus in this paper was to demonstrate that FedLAP+ achieves strong privacy guarantees while maintaining competitive utility. As the majority of existing SFL literature focuses on node classification, we adopt the same setting to enable fair and meaningful comparisons with prior work.\n\nThat said, FedLAP+ can be easily extended to other tasks, such as edge classification. We will include results for such tasks in the final version of the paper to further demonstrate the framework’s versatility.\n\n**Computational cost of spectral decomposition:**\nThe spectral decomposition in FedLAP+ is performed during the offline phase using the Arnoldi iteration, a well-known method for efficiently computing a few dominant eigenvectors of large sparse matrices.\n\nWe explicitly discuss the computational cost of the Arnoldi iteration at the beginning of Section 4.3 and provide a more detailed analysis in Appendix B.3. Importantly, the computational complexity of Arnoldi iteration scales linearly with the number of nodes in the graph, making it well suited for large and sparse graphs. This enables fast and scalable spectral decomposition, even for sizable real-world datasets.  \n\n## QUESTIONS: ##\n\n## Q1: ##\nWe thank the reviewer for the comment. In our privacy analysis of FEDLAP+, we deliberately consider a strong attacker model during the offline phase of the protocol. Specifically, we assume that the attacker (a malicious client) has access to:  \n(i) the spectral projection matrix $Q_{\\mathcal{V}_1,:}$, and  \n(ii) the connection probability $p$,  \nEven though these are not shared in practice.\n\nWe emphasize that this analysis is intentionally conservative. The goal is to establish a worst-case privacy guarantee, following the standard practice in the privacy literature (e.g., in secure aggregation or spectral privacy frameworks), where one assumes an unrealistically strong attacker. This approach is crucial for stress-testing the protocol and identifying fundamental vulnerabilities. If FEDLAP+ is private under this strong model, it is by design private under weaker, more realistic threat models.\n\nBy showing that even under this pessimistic scenario the attacker gains negligible advantage (e.g., precision + recall < 1), we provide strong assurance that the offline phase of FEDLAP+ preserves link privacy. In particular, this result implies that even if spectral components were somehow leaked, the attacker still cannot reliably infer internal connections of other clients.\n\nThis level of robustness is especially valuable in federated environments, where partial leakage or side-channel access may occur. Our analysis thus gives clients confidence that such leakage does not compromise their local subgraph structure.\n\nWe hope this clarifies the rationale behind our assumptions: they are not intended to reflect typical attacker capabilities, but rather to provide rigorous evidence that FEDLAP+ is fundamentally privacy-preserving.\n\n## Q2: ##\nWe appreciate the reviewer’s observation. In this paper, our primary contribution is FEDLAP+, a spectral-domain method designed to handle both homophilic and heterophilic graph structures. FEDLAP+ builds on a base variant we call FEDLAP, which applies Laplacian smoothing directly in the spatial domain.\n\nAs highlighted in line 323 of the main paper, the base FEDLAP model relies on the assumption that neighboring nodes tend to have similar features or labels, an assumption that aligns well with homophilic graphs. However, in heterophilic graphs, where connected nodes often belong to different classes or have dissimilar features, this assumption no longer holds. As a result, Laplacian smoothing can blur useful distinctions between nodes and degrade performance. This is a well-known limitation of smoothing-based methods and is expected in our setting as well.\n\nImportantly, FEDLAP was introduced primarily to motivate FEDLAP+, and FEDLAP's results are included to show that it performs well in the homophilic case, often on par with existing state-of-the-art methods. However, we do not position FEDLAP as a standalone solution for heterophilic graphs. Instead, FEDLAP+ addresses this limitation by operating in the spectral domain, where it can selectively retain global structure and filter out noisy or misleading local signals.  \n## Q3: ##  \nWe thank the reviewer for pointing out the importance of the spectral truncation parameter $r$ in FEDLAP+. This parameter controls how many eigenvectors of the graph Laplacian are retained during the spectral decomposition step.\n\nMore precisely, the global Laplacian matrix $L_G$ is approximated by the low-rank decomposition $L_G \\approx U_{[:, r]} \\Lambda_{[r, r]} U_{[:, r]}^\\top$, where $U_{[:, r]} \\in \\mathbb{R}^{n \\times r}$ contains the first $r$ eigenvectors (corresponding to the smallest eigenvalues), and $\\Lambda_{[r, r]}$ is the diagonal matrix of the corresponding eigenvalues. The matrix $W \\in \\mathbb{R}^{r \\times d_s}$ is then learned in the spectral domain. Truncating to the top-$r$ smooth eigenvectors serves three purposes:  \t\n- It reduces communication (only the top $r$ eigenvectors are shared),  \n- It improves privacy (smaller $r$ reduces potential leakage),  \n- It acts as a regularizer, filtering out high-frequency components (which often capture noise) that may harm generalization.  \n\nTo choose $r$ in practice:  \n- A rule of thumb is to set $r$ close to the intrinsic rank of the graph, which often corresponds to the number of clusters or communities. For many real-world datasets, this number is much smaller than the total number of nodes $n$.  \n- In our experiments (see Fig.5 and Fig.6 of the paper), we observed that moderate values of $r$ (e.g., 50–200) work well across all datasets. For example, in PubMed (with over 19K nodes), $r = 80$ already gives strong performance, and further increasing $r$ yields diminishing returns.  \n- We also show in Fig.5 (left panel) and Fig.6 that the performance of FEDLAP+ is robust across a wide range of $r$ values, \n\nWe will include this detailed explanation of the truncation parameter $r$ in the revised manuscript.\n\n## Q4: ## \nThank you for the insightful question. While FEDLAP+ is designed for static graphs, its use of decentralized Arnoldi iteration makes it amenable to handling dynamic graphs efficiently. In particular, when the graph structure evolves incrementally (e.g., through the addition or removal of a few nodes or edges), one can apply Krylov subspace recycling [1] to update the spectral components without recomputing them from scratch. This makes it possible to adapt to dynamic settings with minimal communication overhead.\n\nOur current framework, like all other existing SFL methods (e.g., FEDSTRUCT, FEDGCN), \nfocuses on fixed graphs. However, we are currently investigating the extension of FEDLAP+ to dynamic graphs as part of our ongoing research. We believe that developing privacy-preserving SFL methods for evolving graphs is a promising and largely unexplored direction for future work.  \n[1] Bolten et al., \"Krylov subspace recycling for evolving structures,\" Computer Methods in Applied Mechanics and Engineering, 2022.  \n## Q5:  ##\nIndeed, FEDSTRUCT achieves stronger performance than FEDLAP on Chameleon, and we appreciate the reviewer’s observation. Note that Chameleon is a heterophilic graph where neighbors often belong to different classes and have dissimilar features. In such settings, Laplacian-based smoothing, whether applied in the spatial domain (as in FEDLAP) or the spectral domain (as in FEDLAP+), can propagate misleading signals across class boundaries. Although Laplacian smoothing has known limitations on heterophilic graphs, FEDLAP+ overcomes this issue by truncating high-frequency spectral components that often carry noisy signals. As a result, it achieves competitive performance, often close to state-of-the-art models, despite its privacy-preserving design.\n\nWe reiterate that we do not position FEDLAP as a standalone solution for heterophilic graphs, but as a step toward FEDLAP+, which is the primary contribution of our work. FEDLAP+ achieves performance very close to FEDSTRUCT on Chameleon.\n\nHybrid approaches that combine spectral and feature-level smoothing could potentially improve performance further. However, they typically require additional cross-client information sharing, which increases the risk of privacy leakage. In contrast, FEDLAP and FEDLAP+ are explicitly designed to limit the information exchanged to minimize such leakage. It is also worth noting that FEDSTRUCT shares significantly more information across clients and does not offer formal privacy guarantees. Its slightly stronger performance on Chameleon with respect to FEDLAP+ likely results from this additional information exchange, which comes at the cost of increased privacy exposure."}, {"review_id": "CGbQz2JPf0", "reviewer": "Reviewer_3cQg", "summary": "This paper presents  framework, FEDLAP,  for subgraph federated learning that addresses the challenge of learning from graph-structured data distributed across multiple clients while preserving privacy. \n\nThe key contribution lies in leveraging Laplacian smoothing in the spectral domain to capture inter-node dependencies without requiring the exchange of sensitive node embeddings or computationally expensive structural information sharing that existing methods rely on. \n\nThe authors propose two variants: FEDLAP, which uses Laplacian regularization to implicitly enforce structural similarity among neighboring nodes, and FEDLAP+, which operates in the spectral domain using truncated eigendecomposition to reduce communication overhead and enhance privacy.", "questions": "No more questions, please check the weakness.", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths:** This paper makes several significant contributions to subgraph federated learning that address real limitations in existing work. The theoretical foundation is solid, with FEDLAP being the first SFL method to provide formal privacy guarantees through rigorous analysis of potential attacks using log-likelihood ratios and KL divergence bounds. \n\n**Weaknesses:** Despite its strengths, the paper has several limitations that could impact its practical adoption. The privacy analysis, while theoretically sound, relies on strong assumptions (known connection probabilities, access to spectral matrices) that may not hold in practice, and the actual attack performance shown in Figure 4 is weaker than theoretical predictions, suggesting the bounds may be loose. The method's performance is inconsistent across graph types—while FEDLAP excels on homophilic graphs, it significantly underperforms on heterophilic graphs like Chameleon, limiting its general applicability. \n\nThe decentralized Arnoldi iteration requires homomorphic encryption, which adds computational overhead and implementation complexity that isn't fully characterized in terms of practical costs. The communication analysis, while showing theoretical improvements, doesn't account for the encryption overhead or provide empirical measurements of actual network traffic. \n\nAdditionally, the truncation parameter r requires careful tuning and domain knowledge about graph structure (number of communities), which may not be readily available in practice. \n\nThe experimental setup is somewhat limited, focusing primarily on semi-supervised node classification with only 10% labeled nodes, and doesn't explore other important graph learning tasks or more challenging federated settings with severe data heterogeneity.", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the thoughtful and detailed feedback, which has helped us improve the paper. We believe we have addressed all of your comments thoroughly and satisfactorily. If our responses resolve your concerns, we would be grateful if you would consider updating your score accordingly.\n\n# WEAKNESSES: #\n\n## W1: ##\nWe thank the reviewer for the comment. In our privacy analysis of FEDLAP+, we deliberately consider a strong attacker model during the offline phase of the protocol. Specifically, we assume that the attacker (a malicious client) has access to:  \n1. the spectral projection matrix $Q_{\\mathcal{V}_1,:}$, and  \n2. the connection probability $p$,  \n\neven though these are not shared in practice.\n\nWe emphasize that this analysis is intentionally conservative. The goal is to establish a worst-case privacy guarantee, following the standard practice in the privacy literature (e.g., in secure aggregation or spectral privacy frameworks), where one assumes an unrealistically strong attacker. This approach is crucial for stress-testing the protocol and identifying fundamental vulnerabilities. If FEDLAP+ is private under this strong model, it is by design private under weaker, more realistic threat models.\n\nBy showing that even under this pessimistic scenario the attacker gains negligible advantage (e.g., precision + recall < 1), we provide strong assurance that the offline phase of FEDLAP+ preserves link privacy. In particular, this result implies that even if spectral components were somehow leaked, the attacker still cannot reliably infer internal connections of other clients.\n\nThis level of robustness is especially valuable in federated environments, where partial leakage or side-channel access may occur. Our analysis thus gives clients confidence that such leakage does not compromise their local subgraph structure.\n\nWe hope this clarifies the rationale behind our assumptions: they are not intended to reflect typical attacker capabilities, but rather to provide rigorous evidence that FEDLAP+ is fundamentally privacy-preserving.\n\nRegarding Fig. 4, the fact that the real attack performs worse than the theoretical bound is expected (at best, the real attack can perform as the bound). This gap further strengthens our privacy claims. It shows that our bound is conservative, reinforcing the privacy guarantees of FEDLAP+.\n\n## W2: ##\nWe appreciate the reviewer’s observation. In this paper, our primary contribution is FEDLAP+, a spectral-domain method designed to handle both homophilic and heterophilic graph structures. FEDLAP+ builds on a base variant we call FEDLAP, which applies Laplacian smoothing directly in the spatial domain.\n\nAs highlighted in line 323 of the main paper, the base FEDLAP model relies on the assumption that neighboring nodes tend to have similar features or labels, an assumption that aligns well with homophilic graphs. However, in heterophilic graphs such as Chameleon, where connected nodes often belong to different classes or have dissimilar features, this assumption no longer holds. As a result, Laplacian smoothing can blur useful distinctions between nodes and degrade performance. This is a well-known limitation of smoothing-based methods and is expected in our setting as well.\n\nImportantly, FEDLAP was introduced primarily to motivate FEDLAP+, and FEDLAP's results are included to show that it performs well in the homophilic case, often on par with existing state-of-the-art methods. However, we do not position FEDLAP as a standalone solution for heterophilic graphs. Instead, FEDLAP+ addresses this limitation by operating in the spectral domain, where it can selectively retain global structure and filter out noisy or misleading local signals. FEDLAP+ achieves excellent performance for heterophilic graphs such as Chameleon.\n\n## W3: ##\nWe thank the reviewer for highlighting this practical concern. To clarify, we use Homomorphic Encryption (HE) only once, during the offline decentralized Arnoldi iteration prior to training. Its purpose is to securely aggregate the spectral information (specifically the projection matrix $\\mathbf{Q})$ without revealing individual node features or adjacency details.\n\nWhile HE does introduce extra computational and communication overhead, this cost is fixed per iteration and does not scale unfavourably with the number of nodes or clients. As discussed in Section E.2 of the FedGCN paper [1], standard HE methods such as CKKS typically increase communication costs by roughly 15x compared to plaintext. However, by applying optimizations like Boolean packing, this overhead can be significantly reduced, down to roughly twice that of plaintext communication for large vectors. \n\nImportantly, our privacy analysis assumes a worst-case scenario where the entire spectral matrix $\\mathbf{Q}$ is directly revealed to the attacker. Therefore, even without relying on HE, our analysis already demonstrates strong privacy guarantees. The use of HE thus serves as an additional practical layer of security, but our privacy guarantees hold true regardless of its usage.\n\nWe will include the cost of the HE in the analysis of the communication in the revised version of the paper. However, we emphasize that HE is not a requirement for FEDLAP+ to ensure privacy.\n\n[1] Yao et al., \"FedGCN: Convergence-communication tradeoffs in federated training of graph convolutional networks,\" NeurIPS, 2023.\n\n## W4: ##\nWe thank the reviewer for pointing out the importance of the spectral truncation parameter $r$ in FEDLAP+. This parameter controls how many eigenvectors of the graph Laplacian are retained during the spectral decomposition step.\n\nMore precisely, the global Laplacian matrix $L_G$ is approximated by the low-rank decomposition $L_G \\approx U_{[:, r]} \\Lambda_{[r, r]} U_{[:, r]}^\\top$, where $U_{[:, r]} \\in \\mathbb{R}^{n \\times r}$ contains the first $r$ eigenvectors (corresponding to the smallest eigenvalues), and $\\Lambda_{[r, r]}$ is the diagonal matrix of the corresponding eigenvalues. The matrix $W \\in \\mathbb{R}^{r \\times d_s}$ is then learned in the spectral domain. Truncating to the top-$r$ smooth eigenvectors serves three purposes:  \n- It reduces communication (only the top $r$ eigenvectors are shared),  \n- it improves privacy (smaller $r$ reduces potential leakage),  \n- It acts as a regularizer, filtering out high-frequency components (which often capture noise) that may harm generalization.  \n\nTo choose $r$ in practice:  \n- A rule of thumb is to set $r$ close to the intrinsic rank of the graph, which often corresponds to the number of clusters or communities. For many real-world datasets, this number is much smaller than the total number of nodes $n$.  \n- In our experiments (see Fig.5 and Fig.6 of the paper), we observed that moderate values of $r$ (e.g., 50–200) work well across all datasets. For example, in PubMed (with over 19K nodes), $r = 80$ already gives strong performance, and further increasing $r$ yields diminishing returns.  \n- We also show in Fig.5 (left panel) and Fig.6 that the performance of FEDLAP+ is robust across a wide range of $r$ values, especially when the training data is limited, indicating that fine-tuning $r$ is not critical.\n\nWe will include this detailed explanation of the truncation parameter $r$ in the revised manuscript.\n\n## W5: ##\nWe would like to clarify that our primary objective in designing FEDLAP+ was to develop a privacy-preserving framework that incorporates the knowledge of interconnections in a decentralized setting, while keeping the setup as general and aligned with standard Federated Learning (FL) as possible. To this end, the online phase of FEDLAP is identical to standard FL, ensuring that any specific FL scenario can be readily integrated into our framework.\n\nRegarding our experiments, we intentionally evaluated FEDLAP+ across multiple representative federated setups to cover varying degrees of client heterogeneity and interconnections. Specifically, we adopted three distinct partitioning strategies (Random, K-means, and Louvain) each corresponding to a unique FL scenario, as detailed in Tables 2 and 3 of our paper:  \n1. Random partitioning: Nodes are randomly distributed across clients, resulting in a large number of interconnections and relatively homogeneous clients.  \n2. K-means partitioning: Nodes with similar features are clustered together, creating highly heterogeneous clients with fewer interconnections.  \n3. Louvain partitioning: Nodes within the same community are grouped into the same client, leading to high client heterogeneity and minimal interconnections.\n\nThese setups allow us to analyze FEDLAP+’s behavior under a range of realistic and challenging federated settings.\n\nAdditionally, in Fig. 5, we reported the performance of FEDLAP+ with varying numbers of clients (i.e., small and large node counts per client) and different training ratios, further enriching the diversity of experiments.\n\nAs for our focus on node classification, our primary focus in this paper was to demonstrate that FedLAP+ achieves strong privacy guarantees while maintaining competitive utility. As the majority of existing SFL literature focuses on node classification, we adopt the same setting to enable fair and meaningful comparisons with prior work.\n\nThat said, FedLAP+ can be easily extended to other tasks, such as edge classification. We will include result for such tasks in the final version of the paper to further demonstrate the framework’s versatility.\n\nWe would appreciate it if the reviewer could specify any particular FL scenario or experimental setup they believe would be valuable to investigate."}, {"review_id": "ihrxzgfGkH", "reviewer": "Reviewer_7gcZ", "summary": "The authors propose a method which is able to cater for graph-structured data in the federated learning domain. It claims that it improves on the state of the art on both communication and overall performance.", "questions": "Based on my prior comments I would like the authors to answer the following questions:\n\n- Can you please expand a bit more on the privacy? Normally, such methods require a form of statistical privacy (e.g. DP) to avoid data leaks and inference attacks. At the very least some sort of formal encryption or similar. As presented, I currently lack understanding on why the definition provided can be considered a form of \"strong\" or \"formal\" privacy definition.\n- Can you please elaborate a bit in terms of the hardware resources required? I feel it is quite important given the context of the paper.", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "The paper tackles an important and unsolved problem: how to efficiently train in the FL domain when using graph-structured data, which is an important use-case.\n\nThe paper strengths can be summarised as follows:\n\n- The performance is appealing and is compared against a number of competing methods\n- The code is provided for the reviewing process\n- The evaluation is extensive in terms of overall results regarding performance\n\nHowever the paper suffers from severe flaws which I am outlining below:\n\n- Claims of strong / formal privacy -- to me this is the biggest problem with this paper. Normally, privacy definitions are quite strict and the notion of \"not being able to infer the connections of nodes\" is not a form of _strong_ privacy or any formal definition of it. I would argue the method provides _no_ privacy at all apart from being unable to infer who your neighbors are.\n- Little light on the details regarding experimentation hardware used and potential scalability of the method (although results are extensive in terms of numbers).", "was_revised": true, "final_justification": "After reading the authors comments, I am willing to raise my score to borderline accept given the justification provided. The paper does not appear to have any technical flaws but I still I am highly concerned about the definition of privacy used (and the protections it entails).\n\nI would highly encourage the authors to substantially rephrase and improve that aspect within the paper so that the limitations are clear and explicit.", "rebuttal": "We believe we have addressed all of your comments thoroughly and satisfactorily. If our responses resolve your concerns, we would kindly ask you to consider updating your score accordingly.\n\n## Weakness 1. ## \n* Claims of strong/formal privacy -- to me, this is the biggest problem with this paper. Normally, privacy definitions are quite strict and the notion of \"not being able to infer the connections of nodes\" is not a form of strong privacy or any formal definition of it. I would argue the method provides no privacy at all, apart from being unable to infer who your neighbors are.\n\n## Question 1. ##\n\n* Can you please expand a bit more on the privacy? Normally, such methods require a form of statistical privacy (e.g. DP) to avoid data leaks and inference attacks. At the very least some sort of formal encryption or similar. As presented, I currently lack understanding on why the definition provided can be considered a form of \"strong\" or \"formal\" privacy definition. \n\n## Response. ##\nOur privacy measure naturally aligns with a membership inference formulation, widely adopted in privacy auditing [1,2]. Below, we justify our privacy analysis, why our results imply strong privacy guarantees, and explain why differential privacy is not well suited to our setting. \n\n**Privacy in FEDLAP+: What we protect and why it matters**  \nTo properly address the concerns raised regarding the privacy analysis, we first clarify how FedLAP+ approaches the Subgraph Federated Learning (SFL) problem. FedLAP+ is designed as a general privacy-preserving framework that leverage structural information (such as connectivity patterns and degree statistics) among clients in a decentralized setting. As explained in the paper, FedLAP+ separates the SFL problem into two distinct sub-problems (phases):\n\n1. Offline Phase:\n- This phase is executed once, prior to training.\n- No node features or sensitive node attributes are exchanged in this phase; only information related to the graph structure and interconnections is shared.\n- The primary question FedLAP+ addresses here is how to efficiently extract useful structural information from interconnections while preserving privacy. By working in the spectral domain, we demonstrate experimentally that most valuable information regarding interconnections resides in a small number of dominant eigenvectors of the graph Laplacian.\n\n\n2. Online Phase:\n- This phase is identical to standard federated learning (FL) training process.\n- No additional information beyond model parameters is exchanged between clients and the server. Thus, FedLAP+’s online phase inherits all privacy guarantees and protections inherent in standard FL.\n- Consequently, any privacy-enhancing methods used in standatd FL (e.g., differential privacy or secure aggregation)  can be applied directly to FedLAP+’s online phase.\n\nGiven this decomposition, ensuring the privacy of FedLAP+ reduces solely to analyzing the offline phase, since the online phase does not introduce additional privacy leakage beyond that of standard FL.\n\nIn the offline phase, the only possible privacy leakage relates to node connections,\nsince no sensitive node features are exchanged in this phase. Hence, our analysis explicitly addresses privacy concerning these structural connections.\n\n**Clarification on Privacy Analysis (Offline Phase)**\n\nTo clarify precisely how our privacy analysis works, we first explain the exact setup:\n\nWe assume a binary random adjacency matrix $\\mathbf{A}$ with probability of connection $p$. To rigorously assess privacy, we consider a worst-case scenario where the attacker possesses complete spectral knowledge, far beyond realistic capabilities. Given the relation $\\mathbf{U} = \\mathbf{A} \\mathbf{Q}$, where $\\mathbf{Q} \\in \\mathbb{R}^{n \\times r}$ is a known orthonormal matrix and $\\mathbf{U} \\in \\mathbb{R}^{n \\times r}$, the attacker observes both $\\mathbf{U}$ and $\\mathbf{Q}$ and attempts to infer $\\mathbf{A}$. It is crucial to note that this process is entirely deterministic. Crucially, the attacker cannot recover $\\mathbf{A}$ via simple inversion, $\\mathbf{A} = \\mathbf{U}\\mathbf{Q}^{-1}$,  since the problem is underdetermined due to the low-rank nature of the matrix $\\mathbf{A}$. There exist infinitely many adjacency matrices consistent with a given $\\mathbf{U}$ and $\\mathbf{Q}$.  Moreover, we also assume that the attacker knows $p$, hence that $\\boldsymbol{A}$ is sparse (i.e., most nodes are not connected).\n\n\nIn this setup, differential privacy (DP) is not a suitable privacy metric. DP measures the indistinguishability between two neighboring datasets differing in a single element under a randomized mechanism. However, since our scenario is deterministic, an attacker can trivially distinguish between two adjacency matrices $\\mathbf{A}$ and $\\mathbf{A}’$ that differ in a single edge by simply checking whether they satisfy $\\mathbf{U} = \\mathbf{A}\\mathbf{Q}$. \n\nInstead, we adopt a membership inference-based approach, which is widely used in empirical privacy auditing [1,2]. Specifically, we consider an attacker who attempts to determine whether a specific connection $A_{uv}$ was involved in computing $\\mathbf{U}$. This leads to a binary hypothesis testing problem, where the attacker computes the log-likelihood ratio (LLR) of observing $\\mathbf{U}$ under the two hypotheses (with and without the presence of $A_{uv}$). Following the Neyman–Pearson lemma, this LLR test is the optimal decision rule.\n\nOur analysis shows that even under this optimal attack, for practical values of parameters $r$, $n$, and $p$,  the attacker performs no better than random guessing (i.e., $\\text{Precision} (P) + \\text{Recall} (R) \\leq 1$). Practically, the attacker cannot extract any meaningful structural information from observing the spectral matrix $\\mathbf{U}$.\n\nAdditionally, we derive an explicit analytical formula for the KL divergence between the distributions under the null hypothesis (edge absent) and the alternative hypothesis (edge present) and show that, for small values of $r$, it is extremely small, indicating the two distributions are nearly indistinguishable. Practically, this implies that even an optimal attacker would have negligible advantage in accurately identifying specific edges. In other words, a membership inference attack cannot succeed.\n\nRegarding the reviewer’s claim that our privacy definition and guarantees provide \"no privacy at all apart from being unable to infer who your neighbors are,\" we respectfully point out that this is precisely the privacy risk of FEDLAP+ (as discussed above under the heading \"Privacy in FEDLAP+: What we protect and why it matters\"), and the one we rigorously address.\n\n\n[1] Carlini et al. \"Membership inference attacks from first principles.\" SP, 2022.\n\n[2] Zarifzadeh et al., \"Low-cost high-power membership inference attacks.\" ICML, 2024.\n\n## Weakness 2. ## \nLittle light on the details regarding experimentation hardware used and potential scalability of the method (although results are extensive in terms of numbers).\n\n## Question 2. ## \nCan you please elaborate a bit in terms of the hardware resources required? I feel it is quite important given the context of the paper.\n\n## Response.  ##\nOur experiments were conducted on a machine with 2 × NVIDIA Tesla V100 SXM2 GPUs, each with 32GB of RAM, connected via NVLink.\n\nAs discussed in the paper, the online phase of FedLAP is both computationally and communication-wise equivalent to standard federated learning (FL). Therefore, it inherits the same scalability and efficiency properties as classical FL frameworks.\n\nThe offline phase, which involves the decentralized Arnoldi iteration, is analyzed in detail in the paper (Appendix B.3). Its computation and communication complexity grows linearly with the number of nodes in the graph, making it practical even for large graphs. Moreover, because real-world graphs typically have sparse adjacency matrices, the memory footprint for graph-related computations is small, and the overall procedure can be executed efficiently.\n\nWe will include a more detailed description of the hardware setup in the revised manuscript.\n\n## Final comment ##\nWe respectfully note that a score of 2 is typically intended for papers with technical flaws, weak evaluation, inadequate reproducibility, or incompletely addressed ethical considerations. We appreciate the reviewer’s concern regarding the framing of our privacy claims and have addressed this point in our response. However, we believe this issue relates to only one aspect of the work. Our paper presents a broader framework with multiple contributions, and we feel that both the review and the overall score should reflect the work as a whole. We kindly ask that this be taken into consideration."}, {"review_id": "mEnOcJOX5s", "reviewer": "Reviewer_Ea2b", "summary": "This paper proposes two methods FEDLAP and FEDLAP+, for Subgraph Federated Learning (SFL) which has gained interest in recent years (some NeurIPS and ICLR papers on this in recent years, for example). In the setting considered in this paper, graph-structured data is partitioned across multiple clients, each with a disjoint subgraph. The central challenge addressed is how to capture global graph structure to improve learning performance without violating privacy or incurring excessive communication costs.\n\nSome key features of the method:\n- a graph Laplacian regularizer in the loss function to balance nodes with labels and without labels\n- use truncated eigenvectors of the Laplacian to reduce communication and enhance privacy.\n- as an offline part of the algorithm, a novel decentralized Arnoldi iteration to compute the spectral components in a privacy-preserving way. A formal privacy analysis is provided for this method.\n\nThere is a comprehensive experimental comparison across six benchmark datasets which shows that FEDLAP offers competitive or superior accuracy with better communication efficiency.", "questions": "- The privacy analysis assumes a random adjacency matrix, right? More specifically, an adjacency matrix where each element in Bernoulli(p) distributed. Could you extend the analysis to static non-random graphs?\n\n- What does the guarantee exactly tell: are the rest of the edges random and the result protect a specific fixed edge?\n\n- Can you say anything rigorous about the case of finite $n$? Does the privacy analysis require $n \\rightarrow \\infty $ ?", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "Strengths\n\n- A formal privacy analysis for the offline phase (Theorem 1 and Corollary 1), seems to be the first one for SFL methods (e.g. baselines FEDSTRUCT and FEDGCN lack rigorous privacy proofs).\n\n- significantly reduces communication overhead through the offline sharing of eigenvectors\n\n- The experimental results demonstrate competitive or superior accuracy compared to SOTA methods\n\nWeaknesses:\n\n- The privacy analysis is not entirely rigorous in my opinion: looking at the proofs in the appendix, the results assume randomness of the adjacency matrices. This then gives in the limit those normal distributions stated in Theorem 1. I see here two problems: a) the assumptions of the randomness of $A$ is not clearly stated in the main text and b) the results does not exactly hold for finite $n$. \n\n- It is also not clearly stated what does the privacy guarantee of Thm. 1 mean. It is kind of differential privacy guarantee (privacy loss random variable for edge-DP), however it is not clearly stated.\n\n- No convergence guarantees for the proposed method", "was_revised": true, "final_justification": "I find the paper interesting including the membership information based privacy analysis of Thm. 1. However, I have some reservations due to the fact that the current privacy analysis is for the infinite limit case (graph size goes to infinity) and has also some additional assumptions listed in Sec. C.1. Authors promise changes that would address the finite graph case, and I think their suggestions for modifications are convincing but I think that they would require non-trivial changes to the paper, not just cosmetic adjustments. In the current form, the results listed in the main paper are not correct I would say, although with small modifications they can be corrected.", "rebuttal": "## W1: ##\nOur privacy analysis assumes the adjacency matrix  is drawn from a random graph model, where each entry  independently follows a Bernoulli distribution with probability $p$. This assumption, clearly stated in Appendix C.1 and implied in Theorem 1, allows us to analytically derive a closed-form log-likelihood ratio (LLR) and apply the central limit theorem to approximate it with a Gaussian distribution. This approximation facilitates computing the KL divergence, quantifying the adversary's ability to infer edges.\n\nThe random graph modeling is standard practice in graph-based privacy analyses, providing controlled analytical insights and clear interpretability [1, 2]. \nImportantly, our analysis considers a worst-case attacker with complete spectral knowledge $\\mathbf{Q}$, greatly exceeding realistic capabilities, ensuring our theoretical bound remains conservative.\n\nRegarding finite graphs, while the Gaussian approximation is exact only asymptotically, our empirical results (Figure 4) confirm its accuracy for practical, moderately sized graphs. The actual attacker performance observed is consistently weaker than our theoretical bound, reinforcing our claim that the derived guarantees robustly hold even in finite settings.\n\nWe will revise the final version of the paper to clearly state the random graph assumption in the main text. Additionally, in our response to your final question, we derive a bound on the error between the true distribution and the Gaussian approximation for finite graphs, further supporting the practical validity of our analysis.\n\n[1] Ullman et al., \"Efficiently estimating Erdos-Renyi graphs with node differential privacy,\" NeurIPS, 2019.\n\n[2] Chen et al., \"Private edge density estimation for random graphs: Optimal, efficient and robust,\" NeurIPS, 2024.\n\n## W2: ##\nWe appreciate the reviewer’s question regarding the privacy guarantee in Theorem 1. We clarify that our privacy analysis is not based on differential privacy (DP), but instead follows a principled approach grounded in membership inference attacks [3].\n\nIn our setup, we consider an adversary who observes the spectral projection $\\mathbf{U} = \\mathbf{A}\\mathbf{Q}$, where $\\mathbf{Q}$ is a known orthonormal matrix and $\\mathbf{A}$ is a random adjacency matrix sampled from a Bernoulli graph model with connection probability $p$. The attacker aims to infer whether a specific edge $A_{uv}$ was present in the computation of $\\mathbf{U}$, framing this as a membership inference problem.\n\nTo do so, the attacker evaluates the log-likelihood ratio (LLR) between two hypotheses: edge present vs. edge absent. We show analytically that the distributions of the LLR under both hypotheses are nearly indistinguishable for small values of $r$, as measured by the KL divergence.\n\nThis analysis aligns with widely-used frameworks in privacy auditing that assess inference risk through optimal hypothesis testing [3]. Using the Neyman–Pearson lemma, we establish that this LLR-based attack is statistically optimal. Moreover, we prove that under practical values of $r, n,$ and $p$, the attacker’s precision and recall satisfy $P + R \\leq 1$, which implies that the attacker cannot outperform trivial guessing. Thus, no meaningful structural information can be inferred from $\\mathbf{U}$. In other words, a membership inference attack cannot succeed.\n\nWe will clarify these concepts in the revised manuscript.\n\n[3] Carlini et al. \"Membership inference attacks from first principles.\" IEEE S&P, 2022.\n\n## W3: ##\n**Smoothness of the spectral regularizer.**  \nOur online loss is defined as:\n\\begin{align}\nL(\\theta) = L_c(\\theta) + \\lambda_{\\text{reg}} \\cdot R(W), \\quad \\text{where} \\quad R(W) = \\frac{\\operatorname{Tr}(W^\\top \\Lambda W)}{\\operatorname{Tr}(W^\\top W)}.\n\\end{align}\nHere, $L_c(\\theta)$ is the supervised loss (e.g., cross-entropy), $\\Lambda$ is the diagonal matrix of Laplacian eigenvalues, and $W$ contains the spectral coefficients. To ensure that $L(\\theta)$ is smooth, which is needed for FedAvg convergence, we analyze the smoothness of $R(W)$.\n\nSince $R(W)$ is scale-invariant ($R(\\alpha W) = R(W$) for any $\\alpha > 0$), we normalize $W$ to unit Frobenius norm ($\\lVert W \\rVert_{\\mathrm{F}} = 1$) after each local update.\n\nOn the unit sphere, the gradient becomes:\n\\begin{align}\n\\nabla_W R(W) = 2(\\Lambda W - W \\cdot \\operatorname{Tr}(W^\\top \\Lambda W)).\n\\end{align}\nThis gradient is Lipschitz-continuous. For any $\\lVert W_1 \\rVert_{\\mathrm{F}} = \\lVert W_2 \\rVert_{\\mathrm{F}} = 1$, using $\\lVert \\Lambda \\rVert_2 = \\lambda_{\\max}$, we have:\n\\begin{align}\n\\lVert \\nabla R(W_1) - \\nabla R(W_2) \\rVert \\le 8 \\lambda_{\\max} \\lVert W_1 - W_2 \\rVert\n\\end{align}\nSo, $R(W)$ is smooth with Lipschitz constant $L_R \\le 8 \\lambda_{\\max}$. Since $L_c(\\theta)$ is also smooth, the full loss is smooth with constant:\n$L \\le L_c^{(\\text{sm})} + 8 \\lambda_{\\text{reg}} \\lambda_{\\max}$,\nwhere $L_c^{(\\text{sm})}$ is the Lipschitz constant of $\\nabla L_c$.\n\nThus, FedAvg applied to this loss inherits standard convergence guarantees (e.g., $O(1/\\sqrt{T})$ under typical assumptions) [4].\n\nWe will include this analysis in the final version of the paper.\n\n[4] Li et al., \"On the convergence of fedavg on non-iid data,\" ICLR, 2020.\n\n## Q1: ##\n\nYes, our privacy analysis assumes the adjacency matrix $\\mathbf{A}$ is drawn from a random graph model with independent Bernoulli($p$) edges. While real-world graphs are fixed, attackers typically lack structural knowledge, making this prior a natural choice to reflect uncertainty.\n\nThis probabilistic model enables a principled privacy analysis using Bayesian inference and privacy auditing. We assess the attacker’s ability to infer whether a specific edge $A_{uv}$ exists based on the spectral observation $\\mathbf{U} = \\mathbf{A} \\mathbf{Q}$, using the log-likelihood ratio and KL divergence to quantify their advantage.\n\nAnalyzing a fixed graph would require graph-specific assumptions and limit generality. The random model instead yields conservative, broadly applicable guarantees. Empirically, we observe that attacker performance is even weaker than predicted (Figure 4), confirming the robustness of our approach in static settings.\n\n## Q2: ##\nTo directly address your question, we restate our main result (Theorem 1) in a clear and intuitive way:\n\nTheorem 1 (restated):\nConsider a graph with n nodes, where each edge is included independently with probability $p$. For any pair of nodes u,v, we analyze two hypotheses:  \n1. $H_0$ : u and v are not connected.  \n2. $H_1$ : u and v are connected.\n\nUsing spectral methods, we derive an explicit formula for the log-likelihood ratio (LLR) between these hypotheses. The LLR depends on three parameters: the number of nodes n, edge probability p, and the number of shared eigenvectors r.\n\nWe then compute the KL divergence between the LLR distributions under $H_0$ and $H_1$, showing it remains small for small r. This implies that an attacker cannot reliably distinguish whether an edge exists based on the spectral representation.\n\nWe instantiate a membership inference attack using this LLR: if $\\text{LLR}_{uv} > \\gamma$, the attacker predicts an edge; otherwise, no edge. We analytically evaluate the attack’s Precision (P) and Recall (R), showing that $P + R \\leq 1$. This means the attacker performs worse than trivial baselines (e.g., guessing all edges exist or none do).\n\nTherefore, even an optimal attacker gains no meaningful advantage from observing the spectral matrix $\\mathbf{U}$, and individual edge privacy is effectively preserved.\n\n## Q3: ##\nThe privacy analysis presented in our paper utilizes a central limit theorem (CLT) to approximate the LLR as a Gaussian distribution.\nTo address the reviewer’s concern regarding finite-sample effects, we invoke the multivariate Berry–Esseen theorem [5], a standard tool for quantifying the convergence rate of the central limit theorem. Specifically, using Equation (38) from the paper, we construct a zero-mean random vector $\\mathbf{x}$ with normalized covariance, formed from the Bernoulli(p) adjacency entries $A_{ij}$ and the orthonormal spectral matrix $\\mathbf{Q}$:\n\n\\begin{align}\n\\\\mathbf{x} = \\\\frac{1}{\\\\sqrt{n p (1-p)}} (\\\\mathbf{A}_{u,:} - p\\\\mathbf{1})^\\\\top \\\\mathbf{Q}\n\\end{align}\n\nThis normalization ensures that $\\mathbf{x}$ has zero mean and identity covariance. The Berry–Essen bound then quantifies how closely the distribution of $\\mathbf{x}$ approximates a multivariate normal distribution, even for finite n.\nSince each entry in $ \\mathbf{A}_{u,:}$ is Bernoulli(p) (with typically small p), the Berry–Esseen bound states that the maximum deviation from Gaussian distribution in terms of cumulative distribution functions scales as $O\\left(\\frac{1}{\\sqrt{n p (1-p)}}\\right)$. When $p$ is small, this simplifies approximately to:\n\n\\begin{align}\n\\\\text{Error}_{\\\\text{CLT}} = O\\\\left(\\\\frac{1}{\\\\sqrt{n p}}\\\\right).\n\\\\end{align}\n\nThis result clearly indicates the number of samples $n$ needed for the CLT approximation to hold rigorously: specifically, the error decreases rapidly as $np$ grows. Therefore, even moderate-size graphs yield accurate approximations due to the typical sparsity of real-world graphs (small $p$) and reasonably large $n$.\n\nImportantly, we stress that the assumption of an infinite sample (or large n) is only used to simplify the analytical derivation of the LLR and ensure the CLT approximation’s validity. It does not inherently result in weaker privacy guarantees for smaller graphs. Indeed, as shown empirically in our experiments (see Fig. 4), even when the CLT approximation is not exact, the attacker’s real-world performance remains weaker than our theoretical analysis predicts. Thus, our theoretical bound remains conservative, and our privacy guarantees remain robust even for finite graphs.\n\n[5] Friedrich, \"A Berry-Esseen bound for functions of independent random variables,\" The Annals of Statistics, 1989."}]

Author rebuttal:

Meta-review: The reviewers unanimously recognized the novel methodological contribution of this paper, which introduces a spectral-domain framework for private, structure-aware subgraph federated learning.

While initial reviews raised concerns about performance in heterophilic settings (3cQg, HaMS) and the assumptions for the privacy proofs (Ea2B, 3cQg), the authors’ rebuttal successfully addressed most of these issues. The primary remaining point of contention was the rigor of the theoretical analysis, a point that Reviewers Ea2b and 7gcZ felt was not fully resolved. They noted that the proof for the online component was missing and that the theorem on privacy guarantees lacked clarity and formal precision.

Despite this weakness in the theoretical presentation, the paper’s core contribution is significant and it is free of critical flaws. Therefore, I recommend acceptance. I strongly encourage the authors to address the feedback on the theoretical proofs in the final version, either by strengthening them or by moderating their claims of rigor.
Decision: Accept (poster)