Gradient Inversion Attack on Graph Neural Networks
Authors: Divya Anand Sinha
Yezi Liu
Ruijie Du
Athina Markopoulou
Yanning Shen
Venue: Accepted by TMLR ()

Abstract: Graph federated learning is of essential importance for training over large graph datasets while protecting data privacy, where each client stores a subset of local graph data, while the server collects the local gradients and broadcasts only the aggregated gradients. Recent studies reveal that a malicious attacker can steal private image data from the gradient exchange of neural networks during federated learning. However, the vulnerability of graph data and graph neural networks under such attacks, i.e., reconstructing both node features and graph structure from gradients, remains largely underexplored. To answer this question, this paper studies the problem of whether private data can be reconstructed from leaked gradients in both node classification and graph classification tasks and proposes a novel attack named Graph Leakage from Gradients (GLG). Two widely used GNN frameworks are analyzed, namely GCN and GraphSAGE. The effects of different model settings on reconstruction are extensively discussed. Theoretical analysis and empirical validation demonstrate that, by leveraging the unique properties of graph data and GNNs, GLG achieves more accurate reconstruction of both nodal features and graph structure from gradients.

Published in Transactions on Machine Learning Research (06/2025)
Gradient Inversion Attack on Graph Neural Networks
Divya Anand Sinha University of Colifornia, Irvine
dasinha@ucii.om edu
Ruijie Du
ruijied@uci edu
University of California, Irvine
Yezi Liu
yezil edu
University of California, Irvine
Athina Markopolou University of California, Irvine
athina@uci..cm edu
Yanning Shen
yarninngs@uci.com edu
University of Colifornia, Irvine
Reviewed on OpenReview: https: /tttp:://ppnnyaeee opw.r/vie...eeee.e net/ forum? ammirgkliy
Abstract
Graph federated learning is of essential importance for training over large graph datasets while protecting data privacy, where each client stores a subset of local graph data, while the server collects the local gradients and broadcasts only the aggregated gradients. Recent studies reveal that malicious attacker can stcal private image data from the gradient exchange of neural networks during federated learning. However, the vulnerability of graph data and graph neural networks under such attacks, i.., reconstructing both node features and graph structure from gradients, remains largely underexplored. To answer this question, this paper studies the problem of whether private data can be reconstructed from leaked gradients in both node classification and graph classification tasks and proposes a novel allack named Graph Leakage from Gradients (GLG). Two widely used GNN frameworks are analyzed, namely GCN and GraphSAGE. The effects of different model settings on reconstruction are extensively discussed. Theoretical analysis and empirical validation demonstrale that, by leveraging the unique properties of graph data and GNNs, GLG achieves more accurate reconstruction of both nodal features and graph structure from gradients.
1 Introduction
Federated Learning McMahan et al. 2016b) is distributed learning paradigm that has gained increasing attention. Gradient averaging is a widely used mechanism in federated learning, where clients send the gradients of the models instead of the actual private data to a central server. The server then updates the model by taking the average gradient over all the clients. The computation executed independently on each client and synchronized via exchanging gradients between the server (Li et al. 2014 landola al., 2016) and the clients (Patarasuk & Yuan 2009). Various organizations and mobile devices in healthcare rely federated learning to train models while also keeping user data private. For example, multiple hospitals train model jointly without sharing their paticnts' medical records (Jochems et al. 2017 McMahan et al. 2016a
Recently, several efforts have demonstrated that gradients, accessible to an honest-but-curious (HBC) server,
can be exploited via gradient inversion attacks to reconstruct the original input data. By leveraging the
gradients, Jeon al. (2021): Zhu et al. (2019): Geiping (2000): Zhao al. (2020b) Yin al. (2021)
*Corresponding Author.

---

Published in Transactions on Machine Learning Research (06/2025)
Vyy
DITATRAK
Recovered Private
Vy
Client
Client
Client
Client
Client
Private Graph Data
Figure 1: Gradient inversion attack in Federated Graph Learning
Zhu Blaschko g Jin (2011) successfully reconstruct the users' private image data and Boenisch et al. (2021]; | Fowl et al. (2022a) reconstruct users' text data. Gradient inversion attacks have demonstrated the privacy vulnerabilities of standard federated learning.
Meanwhile, Graph Neural Networks (GNNs) have demonstrated state-of-the-ard results when applied to structured data. From learning meaningful node representations over large social networks (Hamilton et al., 2017), to predicting molecular property (Gómez -oanez--ommbaelli et al. 2018 Yang ct al. 2019), GNNs have been widely adopted across various paradigmns. The coulluence of Federated Learning and graphs has led to the
emergence of Federated Graph Learning (FGL) (He et al. 2021 Scardapane al. 2020 Zhang al. 2021
However, the privacy concerns regarding gradient leakage in FGL remain crucial and underexplored. Prior work has explored gradient-based allacks and privacy lechniques in federated graph learning (Geisler el al. 2021 Ge et al.] 2024), which aims to mislead training. Meanwhile, gradient inversion attacks have shown notable success in general deep neural networks (Zhu et al. 2019 Zhao et al. 2020a). Nevertheless, graph- specific gradient-inversion attacks, i..., reconstructing both node features and graph structure from gradients, remain largely underexplored. Hence, the present work aims to answer the following underexplored research question:
How can the unique properties of graph data and GNNs be leveraged to effectively reconstruct graph structure and node features from gradients of GNNs?
A major challenge in reconstructing graph data is the intertwined nature of the nodal features and the irregular graph structures, making it difficult to separate the information from nodal features and the graph structure. In other words, representations are correlated, and the underlying graph structure influences the correlation. In this work, we provide theoretical analysis of the feasibility of reconstructing graph data based on gradients. Motivated by this observation, we propose gradient inversion attack called GLG (Graph Leakage From Gradients). We investigate two commonly used GNN frameworks, í.c., Graph Convolutional Networks (GCN) (Kipf & Welling 2016), and GraphSAGE. (Hamilton et al., 2017). and examine their vulnerabilitics to gradient inversion attacks for both node and graph classification tasks. An illustration of the attack scenario is presented in Figure [ showcasing the process in which a curious central parameter server attempts to reconstruct the graph data utilizing the gradients of the model obtained from client. To our best knowledge, this is among the first works to study maadient-inversion attacks for graph data. Our main contributions are summarized as follows:
Theoretical analysis revealing the vulnerabilities of GNNs towards gradient inversion attack.
Developing novel gradient inversion attack mechanisms reconstruct graph data for both node and graph classification tasks.
Experiments conducted in variety of settings with different amounts of prior knowledge.
2

---

Published in Transactions on Machine Learning Research (06/2025)
The structure of the rest of the paper is as follows. Section 2 reviews related work. Section 3 introduces the problem formulation and the federated graph learning frarnwwork. Section || presents the proposed gradient inversion attack algorithms, GLG, and Section 5 provides the corresponding theoretical analysis. Section 6 presents the experimental results. Section conchudes the paper and discusscs future work.
2 Related Work
Gradient inversion attacks in FL. In terms of privacy leakage, communicating gradients throughout the training process in FL can reveal sensitive information about the participants. Deep leakage from gradients (DI.))ZZuu et al. 2019 demonstrated that sharing the gradients can leak private training data, including images and text. Specifically, Zhao et al. (2020a) proposes that the ground truth labels can be directly inferred from the gradients. Consequently, ensuing works improve the attack techniques on large batches of user data (Yin et al.] 2021 Fowl et al.
2022b). A few recent works study reconstructing text data in
federated learning. To facilitate the text reconstruction, Boenisch et al. [202]]; Fowl et al. 2022a) reconstruct text data using a strong threat model in which the server is malicious and able to manipulate the training model's weights. In contrast, [uupta et al. (2022) studies the feasibility of reconstructing text from large batch sizes by leveraging the memorization capability of Language Models during federated learning. Recent work Petrov et al. (0024) introduces DAGER, the first exact gradient inversion allack for transformers by leveraging the low-rankness of self-attention layer gradients. The majority of the works are based on either image or text data.
Gradient inversion attacks in FGL. Reconstructing the data, including nodal features and graph structure, in FGL remains underexplored compared the gradient inversion attacks image or text domains. Since the input of GNN includes nodal features and graph structure, directly applying DLG or its enhanced methods in the graph domain is cither infeasible or leads to significant performance degradation. Particularly in GCN, DLG consistently struggles to reconstruct the graph structure, which is essential for graph data. The only concurrent work, Drencheva et al. 2025), proposes GRAIN that introduces gradient inversion attack tailored to GCN (Kipf& & Welling] 2016) and GAT (Veličković et al.) 2018). GRAIN employs a depth-first search strategy to identify subgraphs within gradients, iteratively filtering out unlikely candidates through a span check. By leveraging degree information in the features, GRAIN generates its final prediction. However, nodal degree information is not inherently accessible attackers during GNN training. In the absence of degree information, neither theoretical nor experimental guarantees of GRAIN can keep reliable. Given the limited exploration of gradient inversion attacks in FGL, propose method, GLG, that reconstructs both nodal features and graph structure with fewer constraints. GLG does not rely on explicit degree information, making it more generalizable. To facilitate comparison, we summarize the key differences between DLG, GRAIN, and our method in Table T The detailed comparison is provided in Appendix H
Table 1: Comparison of DLG, GRAIN and GLG. / and X indicate whether the method can reconstruct the corresponding graph data. Prior knowledge refers to any other information required besides the gradients.
Method Nodal feature
Graph structure
Prior knowledge
DLG
X
None
GRAIN
Node degree
GLG
None
3 Preliminaries
Given a graph := = (V,E), where V {0i, u2,... ... uNn] represents the node set and E C x N denotes the edge set. Matrices X NDD and A (0, 10 1 represent the node feature and adjacency matrix respectively, where Aij 1 if and only if {vi, matrix derived from A. a GCN framework A D D- +ID+IDD- where D E NNN is the diagonal degree matrix with i-th diagonal entry d, denoting the degree of node 222 While for GraphSAGE with mean aggregation, À D-A. Let L = D- A-AAD- denote the symmetric normalized laplacian matrix. In
E. Á NNN denoles the normalized adjacency
3

---

Published in Transactions on Machine Learning Research (06/2025)
node classification task, the node be classified is called the target node, denoted as Un, with Xe, and Ne. representing its feature vector and neighboring index set, respectively. Node representations at the I-th layer are denoted by H' E R where the i-th row of H' i.e. h E RIXP denotes the representation for the node D,. Throughout the paper we use the operator (-), to denote the i-th row of any matrix or the i-th clement of any vector, for example, (X); denotes the i-th row of the node feature matrix X.
3.1
GNN Frameworks
We first introduce GraphSAGE and Graph Convolutional Network (GCN) frameworks for both node and graph classification tasks below.
3.1.1 Node Classification:
Consider a GraphSAGE layer with weights Wi E RFXD, W2 E RFXD, and bias b E RIxE Let h and h denote the hidden and aggregated representation of the node Un at layer and is a non-lineat activation function. Then the GraphSAGE layer can be expressed as
h = ohh W h W + bb),
(1)
with bg. x and ha xass denoting the feature vector and aggregated representation of node un respectively. For a GraphSAGE layer with mean aggregation the aggregated representation of a node h can be obtained as
1-1 agg
= meanjeN., (h(
(2)
Similarly, for GON layer with weights W E FxD and bias b E BIxF, the representation of a target node Un can be obtained via.
h'_ oh W b).
(3)
Here h--1 is obtained by aggregating the neighboring nodal feature vectors as
1-1
1-1
Σ
(4)
agg
JEN U(n) Vdnd,
For a node classification task using an L layer GraphSAGE or GCN framework let K denote the number of classes. Also, let h E R x denote the output of the final layer and p = h The final Cross- of node en can be written as
Cross-Entropy Entropy loss
eP
Lv., -llog
(5)
k _==1
eP
where & is the corresponding ground-truth label and py denotes the jth element of the vector p.
3.1.2 Graph Classification:
Consider an N-node graph with X and Å as the node feature matrix and the normalized adjacency matrix respectively, let H' E NFF denote the hidden representations of the nodes at layer The output of a GraphSAGE layer can be written as
W. + +H' WT + Tb).
(6)
with H = X. Here I denotes a column vector of all ones. Similarly, the output of a GCN layer can be written as
H' -'H + Tb).
(7)
4

---

A typical FL. framework consists of server and C' clients. In the node-level FGT., each client samples a mini-batch of B target nodes {x from the graph which is used to compute the gradients of the loss function in equation []] with respect to the model parameters. In the graph-level FGL, at each step t, Published in Transactions on Machine Learning Research (06/2025)
Following the final GNN layer, an MLP layer is applied For an MLP with weights W RRXN the final readout from the MLP layer can be written as
HMLP = by W +
(8)
where hy E RRINN is the flattened representation of H R which is the hidden representations obtained at the Lth layer. Let p hMLP IR IxR be the final readout, the Gross-Entrope Loss L can be computed using equation
3.2 Federated Graph Learning (FGL)
each client has a set multiple graphs. Similar to the node-level FGL the t client samples a minibatch of B graphs ' gen which are then used to compute the gradients and train the model. The gradicnts from N clients then broadcast to the server for updating the weights
V 1
V Vw Legis
(9)
B.C
W W V
(10)
where Lo denotes the gradient of the loss at the e-th client for the i-th data sample.
4 Gradient Inversion Attack for GNNs
We consider the scenario where there is honest-but-curious server, i.e., the server has access the model gradient with respect to the client's 's private graph data. Different attack scenarios are next discussed, where the server may also have access to different amounts of information.
4.1 Threat Model
The attacker is an donest-but-curion server that aims to reconstruct the uscr's graph data given the gradients of a GNN model. In addition to possessing knowledge of the gradients, the attacker may also have access to varying amounts of information about the user's private graph data. Hence we categorize the attacks based on the task as follows:
Node Attacker has access to the gradients of node classification model for the target node and reconstructs the nodal features of the target. node and its neighbors.
Node Attacker has access the gradients of a node classification model for all the nodes in an egonet or subgraph. Specifically, the gradients are obtained for the loss function L, E RIx with respect to the neural networks weights, where each element Lu; denotes the loss for node u; Unlike traditional classification tasks, the adjacency information is also significant for graph data. In this setting, the graph structure could be unknown. The honest-but-curious server would also try to reconstruct the nodal features and/or the graph structure. Based on the input, we categorize the attacker furhter as follows
Node Attacker 2-G: has access to the gradients of all the nodes in an egonet or subgraph along with the nodal features and reconstructs the underlying graph strueture.
Node Attacker 2-N: has access to the gradients of all the nodes in an egonet subgraph along with the graph structure and reconstructs the nodal features.
Node Attacker 2-GN: has access only to the gradients of all nodes in an egonet or subgraph and reconstructs the graph structure as well as the nodal features.
Graph Attacker: has access to the gradients of the graph for a graph classification model. Similar Node Attacker 2, in this setting the cenest-but-curieen server would try reconstruct the nodal features and/or the graph structure. Hence, we categorize the attack in more detail follows
5

---

Published in Transactions on Machine Learning Research (06/2025)
Graph :ttacker-G: has access to the gradients along with the nodal features and reconstructs the underlying graph structure.
Graph Attacker-N: has access to the gradients along with the graph structure and reconstructs the nodal features.
Graph Attacker-GN: has access to the gradients and reconstructs both the nodal features and the graph structure.
Table 2: Overview of Threat Models: distinct attackers across seven settings. (X) Itarget refers to nodal
features of the target node and its neighbors. Vw denotes the gradients of nodes, X represents features of
all nodes in the subgraph, and A corresponds to the underlying graph structure.
Attacker
setting
Training task
Accessible information
Reconstructed data
Node Attacker 1
Node classification
Vw of the target node
(X) target
Node Attacker 2
G
Node classification
Vw and X
A
Node Attacker 2
N
Node classification
V and A
X
Node Attacker 2
GN
Node classification
Vw
X and A
Graph Attacker
G
Graph classification
Vw and X
A
Graph Attacker
Graph classification
Vw and A
Graph Attacker
GN
Graph classification
Vw
X and A
4.2 Attack Mechanisms
In this section, GLG is introduced to attack a GNN framework and steal private user data using the gradients in a federated graph learning setting. Specifically, given the gradients of the model from a client for the i-th data sample Ww the goal is to reconstruct the input graph data sample that was fed to the model. For simplicity, we denote Vw as VwL for the graph classification task, and VwC, for the node classification task. In ZZhu et al. (2019), the imput data to a model is reconstructed by matching the dummy gradients with the gradients. The dummy gradients are obtained by feeding dummy input data to the model. Given the gradients at a certain time step as WwC, the input data is reconstructed by minimizing the following ovjective function
D WWWWWWWWWll Vw2ll2
(11)
Here V is the gradient of the loss obtained from the dummy input data. Tn Geiping et al. (2020) the cosine loss optimization function is used instead of the &2 loss in equation []] Specifically, the objective is to minimize the cosine loss between the actual gradicnts shared by a client and the gradients obtained from dummy input data
VW V
D =11
(12)
[V
In this work, it is assumed that the input label is known since in classification task with cross-entropy loss, the labels can be readily inferred from the gradients (Zhao et al. 2020a For further details regarding this please refer to Appendix B
Feature Smoothness. As shown in equations 2 and 4 Graph Neural Networks (GNNs) typically employ feature aggregation mechanism wherein node representations are constructed by integrating features from neighboring nodes prior to weight multiplication at cach network layer. However, the objective function proposed in equation 12 may be insufficient for simultaneously reconstructing both nodal features and graph structure. To address this limitation, we leverage intrinsic properties characteristic of real-world graphs that can enhance graph data reconstruction. Many real-world graph structures, such as social networks, exhibit a fundamental property of feature smoothness, wherein connected nodes tend to possess similar characteristics. To formally enforce and quantify this feature smoothness in the reconstrueted graph data, we propose the

---

Published in Transactions on Machine Learning Research (06/2025)
following loss function, which is adapted from the approach introduced by Zhang al. (2022)
Ls = tr(XLX))
Xx. = EijEE
X
(13)
Vd.
Vdz
The loss function caplures the similarity between adjacent nodes by minimizing the normalized feature differences across connected nodes.
In addition, the Frobenius norm regularizer is also introduced such that the norm of A is bounded. Overall, the final objective can be writlen as
t= + DaC.+ + B1
(14)
where D is defined in equation 12 and 3 are hyperparameters. The iterative algorithms for reconstructing
the private data from the gradients in a node classification task and a graph classification task are summarized in algorithms and] [ in Appendix A respectively. Specifically, Node Attacker 1 utilizes algorithm [ for reconstructing the nodal features of the target node and its neighbors. Node Attackers 2 (G, N and GN) 2 for reconstructing the nodal features and graph structure given the gradients of the loss function for each node in the egonet /sobgr//ubgrahh By default, algorithm 2 assumes that both nodal features and graph structure are unknown and tries to reconstruct both. However, only the unknown paramcter will be optimized when either of the two is known. For instance, Node Attacker 2-G only optimizes for A in Line 9 of algorithm
utilizes algorithu
2 while skipping Line 8 since the nodal features X is known. The same holds for Node Attacker 2-N. However, unlike the other two Node Attacker 2-GN optimizes for both. Similar logic holds for Graph Attacker (a. b and c) which utilizes algorithm 3 Note that algorithms 2 and 3 might seem similar since they are reconstructing the same variables. However, a key difference wetween the two that algorithm 2 is attacking node classification model while algorithm 3 the gradients of the loss function are computed individually for each node. This because each node within the subgraph has an associated label. In contrast, algorithm calculates gradients for the entire graph, the graph has a single label.
attacks a graph classification model. In algorithm 2
Reconstructing the Adjacency Matrix: In all the scenarios where the atlacker is trying to reconstruct the adjacency matrix, projected gradient descent applied. Specifically, the gradient descent step in Line 9 of algorithms and entails a projection step, where each entry (i, of the adjacency matrix is updated through the entry-wise projection operator defined
1,
A 21
Å.j = projjo.1(AA (A.))
=
0,
Aij 5
(15)
Aij:
otherwise
Finally, to reconstruct the binary adjacency matrix, we consider each entry Aij as the probability of any edge between nodes e, and vy and the reconstructed binary adjacency matrix is obtained by sampling from a Bernoulli distribution with the corresponding probability at the last iteration, see also Line 11 of algorithm 2 and algorithm
Since the reconstructed adjacency matrix Å is obtained via sampling through Bernoulli distribution, the Frobenius regularizer has the effect of reducing the magnitude of entries of Å. Consequently, this regularizer also contributes to the promotion of sparsity in the ultimately reconstructed adjacency matrix. This sparsity property is particularly relevant since real-world social networks are sparse.
5 Theoretical Justification
While prior work GGeiping et al. 2020) has shown that the input to a fully- fully-connected layer can be reconstructed from the layer's gradients, the analysis of GNNs is largely under-explored. Below we will extensively study whether similar conclusions apply to GraphSAGE and GCN and what parts of the graph input can be reconstructed from the gradients.
7

---

Published in Transactions on Machine Learning Research (06/2025)
5.1 Node Attacker
Consider node classification setling, where the inputs to a GNN layer are the larget nodal feat ures and the neighboring nodal features denoted as and {xe, IEN. Through theoretical analysis we will show that parts of the input to a GCN or GraphSAGE layer can be reconstructed from the gradients analytically without solving an iterative optimization problem.
Proposition 1. For GraphSAGE defined in equation 1 or GCN layer defined in equation B Node Attacker 1 can reconstruct the aggregated representations of target node denoted as x (see equation 1 with h agg = xx ) given the gradients of the first layer as x Vow Coy,,,/V for GCN and as
x Lo (b) for GraphSAGE provided that (b)).o #0.
Proof. We show the proof for a GCN layer. For a GCN layer, the aggregated input at the target node can be reconstructed from the gradients with respect to the weights of the first layer by writing the following equations
h, = o(h.),
(16)
h, W + b,
(17)
V(w), V(h.), Cv V(w), (ha):.
(18)
V Cw), = V(b),Lo.x." x
(19)
where (W); denotes the ith row of W, (b); and (hr); denotes the ith element of vectors and h, respectively.
It can be concluded from equation 30 that x can be reconstructed as (ow))Co/V(b).4 long V V(b), C. + O.
It can be observed from the above proof that the analytic reconstruction is independent of the loss function or the non-linearity used after the layer and only depends on the gradients of the loss function with respect to the weights of the model.
Proposition 2. For GraphSAGE layer defined in equation 1 Node Attacker can reconstruct the target node features given the gradients of the first layer as Xx Lo (b),Co fo as long as V(b), # 0.
Proof. See Appendix D
In the following, we focus theoretically analyzing the attack setting of Node Attacker 2, specifically targeting the reconstruction of nodal features and/or the graph structure. To reiterate, this setting involves leveraging the gradients of the loss function of GNNs associated with each node in the egonet or subgraph.
Proposition 3. For GCN layer defined in equations equation 3 and equation Node Attacker 2-G con reconstruct A given the gradients of the first layer as long as X is full row-rank.
Proof. From Proposition I we know that given the gradients for node we can reconstruct the aggregated representations of that node. Since we know the gradients for each node representation for each node. Let Xage E NxD denote the aggregated node representation matrix where each row denotes the aggregated node representation of node Us equation g in the matrix form can be written as the following for 1-1
reconstruct the aggregated
X = AX.
(20)
Since a and X are known, the adjacency matrix can be then reconstructed as À Xagsy X
Proposition 4. For GCN layer defined in equations equation and equation Node Allacker 2-N con reconstruct X given the gradients of the first layer if A is full column-rank.
Proof. Similar Proposition g once we have X X can be obtained as X X Ät
8

---

Published in Transactions on Machine Learning Research (06/2025)
Table Target node feature reconstruction X (RNMSE) for Node Attacker 1.
Syuthetic
FB
GitHub
OGBNN-rxivv
GLG (Ours)
Mean 2.8+2.5
2.6
2.8+1.4 0.9
4.4
GraphSAGE (x10-9)
Min 0.75
0.6
1.53
Mean
0.54+:0.35
0.81=0.61
1.27=t0.79
4.28:10.99
GCN
Min
0.23
0.22
0.18
3.25
DLG
Mean
0.113=0.07
0.03=00.06
0.001#0.0012
4.57=0.37
GraphSAGE
Min
0.04
0.001
0.0009
3.92
Mean
3.21+2.56
1.34+1.66
7.01++5.49
4.98
GCN
Min
1.22
0.14
1.51
3.64
Proposition 5. For a GraphSAGE layer defined in equalion 7 and A given only the gradients of the first layer for each node.
Node Allacker 2-GN can reconstruct both X
Proof. Proposition 2 states that for a GraphSAGE layer, the target node features can be reconstructed given the gradients of the first layer for that node. Similarly, we have access to the gradients for each node in the graph we can reconstruct all the nodal features. Let X denote this matrix. From Propositions that for GraphSAGE layer, the aggregated node representations 8 be reconstructed. With both X and "88 in hand, the adjacency matrix can be reconstructed as À Xi similar to Proposition
is known
The aforementioned proposition has significant privacy implications. Even without any prior knowledge of the graph data, the attacker successfully reconstruct both the nodal features X and the underlying graph structure A. This result is particularly important as one would anticipate that the intertwined nature of graph data makes it impossible to independently reconstruct X and A, which is however shown not to be truc.
5.2 Graph Attacker
The present subsection provides theoretical analysis for a Graph Attacker-G in a scenario where prior information may be available for the graph data to be attacked. can be shown that for GraphSAGE, prior knowledge the nodal feature matrix X can help reconstruct the graph structure A, making the framework more vulnerable to the gradient-inversion attacks.
Proposition 6. For GraphSAGE framework defined in equation 0 with H X, Graph Attacker-Gi con reconstruct A from the gradients of the first layer Å X(V L) if the nodal feature matrir X is full-row rank and known.
Proof. See Appendix
Therefore if the attacker knows the nodal feature matrix X along with the gradients, it can reconstruct the normalized adjacency matrix À analytically. Even though is not possible to analytically demonstrate the reconstruction for Graph Attacker-N and Graph Attacker-GN. we do conduct experiments for all the threat models for both GraphSAGE and GCN.
6 Data & Experiments
The effectiveness of the proposed algorithms is evaluated on real-world social network datasots, paper citation network datasets, molecular datascts, and synthetic datasets. The detailed results for molecular datasets are provided separately in Appendix G

---

Published in Transactions on Machine Learning Research (06/2025)
Evaluation Metrics. Error metrics for reconstructing the nodal features and the graph structure are evaluated, along with their standard deviation.
Nodal Features: To evaluate the performance of the reconstructed node features, the Root Normalised Mean Squared Error(RNMSE) used
RNMSE(X, &,) 1|x, &
(21)
In order to evaluate the performance of reconstructing X in a graph classification setting, we report the mean RNMSE over all the nodal features in X.
Graph Structure: To evaluate the reconstruction performance of the binary adjacency matrix, we use the following metrics
Accuracy: defined as Σ,, (A,-AA) N+N
AUC (Area Under Curve): The area under the Reciever Operator Characteristic Curve. TP
AP (Average Procision): defined TP+FP where TP stands for number of True Positives and FP stands for False Positives. True Positives are the correctly identified edges in the actual graph by the attacker and False Positives are the non-edges incorrectly classified edges by the attacker.
Experimental Settings. Algorithms gradient descent. The gradient descent step can be replaced with off-the-shelf optimizers such as Adam or L-BFGS. In all the experiments, Adam is used as the optimizer. In an attack setting, allowing multiple restarts to the optimizer (especially L-BFGS) from different starting points can significantly increase the quality of reconstruction. For fair comparison, multiple restarts not used, and all results presented are oblained with single run of the optimizer. However, in actual allack setting, allacker may be able to greatly improve the reconstruction quality by allowing multiple restarts.
2 and B in Appendix A solve an optimization problem using
In the experiments, a 2-layer GNN model with hidden dimension 100 and a sigmoid activation function is employed. The weights of the model are randomly initialized. For all the experiments, the dummy nodal features are initialized randomly, with each entry sampled from the standard normal distribution i..., (o 1). The dummy adjacency matrix is initialized by randomly sctting its entries to 0 or 1. The hyperparamoters values for the feature smoothness and the sparsity regularizers are set to 10 and / 10-7, These are the values selected by grid search for the choice that leads to the best performance.
Node Attacker uses the cosine loss objective given in equation 12 without regularization.
Node Attacker uses the objective function is defined in equation 14
Graph Attacker uses the objective function as defined in equation
We adopt the DLG atlack as our baseline and evaluate across all three settings. comprehensive comparison with GRAIN is provided in Appendix H We also extend the experiments involving Node Attacker 1 and Graph Attacker-N to the minibatch setting; these results are detailed in Appendix F.2 As the attack involves numerous hyperparameters, we further analyze subset of these hyperparameters under various settings, with results presented in Appendix F.3 All reported results represent averages taken over 20 independent. runs each attack.
Datasets.
We consider the following three datascts:
GitHub [Rozemberzzki et al. 2021): Nodes represent developers on GitHub and edges are mutual follower relationships. The nodal features are extracted based on the location, repositories starred, employer and e-mail address. Binary labels indicate the user's job title, either web developer or machine learning developer. The details regarding the number of nodes and edges in this dataset are presented in Table T0
10

---

Published in Transactions on Machine Learning Research (06/2025)
FacebookPagePagge (FB) (Rozemberczki al.) 2019) : A page-page graph of verified Facebook
sites. Nodes correspond to official Facebook pages, links represent mutual likes between sites. Node features are extracted from the site descriptions. The labels denote the categories of the sites. The details regarding the number of nodes and edges in this datasct are presented in Table I0
OGBN-Arxiv (Hu et al., 2020): large-scale citation network dataset from the Open Graph Benchmark (OGB), representing academic papers from the arXiv repository. Each node corresponds to a paper, and directed edges represent citation links between them. Node features are based on the paper's title and abstract. The task is node classification: predicting the primary subject area of each paper. As the setting of OGBN-Arxiv aligns with the Node Attacker 1, we evaluate only Node Attacker 1 on this dataset.
Synthetic: A synthelic datasel containing undirected random graphs with an average degree of 4 and average number of nodes set to 50. The node features are generated by sampling from the standard normal distribution i.c. No 1). Node labels are generated by uniformly sampling an integer between zero and the number of classes specified. Edges are generated by uniformly sampling its two endpoints from the node set. The total number of edges are set to dan 2
Note that since Node Attacker 2 and Graph Attacker aim at attacking the subgraphs. We randomly sample node and its 3-hop neighborhood as the subgraph to be attacked. This setting is also consistent with the Federated Graph Learning setting where each client tends to store a subgraph instead of the whole graph.
6.1 Node Attacker 1
In this section, we evaluated the performance of feature reconstruction of Node Attacker 1 for the node classification task.
Target node feature reconstruction. In this experiment, the attacker has no prior knowledge of the graph dataset. Consequently, a 2-layer tree is generated as a dummy graph, with the target node as the root node and each node having degree dtree- 10. Table 3 reports the RNMSE for reconstructing the target node features, where the attack is performed on 20 randomly selected nodes from each dataset. It can be observed that, for GraphSAGE, the attacker achieves high accuracy in reconstructing the nodal features, whereas for GCN, the attacker struggles to reconstruct the target node features reliably. These observations align with the theoretical insights presented in Propositions 1 and 2 Furthermore, Table 3 also shows the minimum RNMSE achieved among the 20 nodes. While the mean RNMSE for GCN may be large, the presence of smaller minimum RNMSE values indicates that leakage of the nodal features can still occur in practice.
A closer examination of our proposed method, GL.G, reveals that it generally attains low RNMSE values for GraphSAGE across the Synthetic, FB, OGBN--rxiv, and GitHub datasets. For example, on Synthetic and FB, GLG reports mean RNMSE values on the order of 10-3, indicating a near-exact reconstruction of the target node features. Although the mean RNMSE for GitHub is slightly higher, GLG remains highly effective at recovering node features when GraphSAGE is used. Under the GCN framework, while GLG yields larger RNMSE values overall, its minimum RNMSE can still be as low as 0.18 on GitHub. This finding underscores that, even in scenarios where GCN poses a more challenging reconstruction problem, GLG can still reveal critical information about certain nodes.
In comparing GLG and DLG, the results highlight the superiority of GLG in most cases. Under the GraphSAGE framework, GLG exhibits significantly lower mean RNMSE on both Synthetic and FB, thereby demonstrating more accurate feature reconstruction. Although DLG achieves a marginally better result on GitHub, this exception does not overshadow the broader trend of GLG's robust performanco. Morcover, under the GCN framework, GLG consistently outperforms DLG on all tested datasets.
Detailed results evaluating the performance of node attacker I in reconstructing the nodal features of one-hop neighbors are presented in Appendix F.1
6.2 Node Attacker
In this section, we evaluate the performance of Node Attacker which has access to the gradient of node classification model for all nodes in subgraph.
11

---

Published in Transactions on Machine Learning Research (06/2025)
Table 4: Reconstruction of A for Node Attacker G.
Facebook
GitHub
Framework
ACC
AUC
AP
ACC
AUC
AP
GLG (Ours)
GraphSAGE
1.00++0.00
1.00=+0.00
1.00++0.00
1.00=+0.00
1.00=:0.00
1.00
GCN
0.97+00.08
0.97+00.2
0.85++0.04
0.97+00.02
0.98++0001
0.87+0.02
DLG
GraphSAGE
0.85++0.14
0.90 0.09
0.65++0.28
0.83++0.16 0.67:10228
0.87=+0.16
0.60++0277
GCN
0.74
0.74
0.54+0.20
0.71
0.47=10.27
Table 5: Reconstruction of X for Node Attacker 2-N.
Framework
Facebook
GitHub
GLG (Ours)
GraphSAGE (x10-*)
0.7:+0.6
0.9
GCN
0.07+00001
0.09110.02
DLG
GraphSAGFF(x10-)
0.1++0.0
0.06+0.03
GCN
0.31
0.29++021
Node Attacker 2-G. The reconstruction performance of the adjacency matrix for this setting is listed in Table 4 Note that the attacker perfectly reconstructs the graph structure for the GraphSAGE model. For GCN, even though Proposition 3 states that we can exactly reconstruct the adjacency matrix, we do observe some error in the reconstruction. This can be potentially attributed to either the limited number of iterations employed in the attack, hindering its convergence, or the optimization procedure encountering local minimum. Nonetheless, even though not a perfect reconstruction, the attacker can reconstruct the graph structure with high accuracy and precision for GCN. GLG consistently outperforms DLG for both GraphSAGE and GCN, demonstrating its overall superiority in reconstructing the adjacency matrix.
Node Attacker 2-N. Table T shows the results for Node Attacker 2-N. The attacker is capable of obtaining almost. perfect reconstruction of nodal features for the GraphSAGE model. Similarly, for the GCN model, the RNMSE values, although slightly higher, remain sufficiently low, which indicates data leakage. Note that the small error can again be attributed to the potential algorithmic issues such as local optimal as discussed before. Compared to DLG, GLG consistently performs better in reconstructing nodal features for GCN. While DLG achieves slightly better results on the GitHub dataset with GraphSAGE, like Node Attacker 1, this isolated exception does not detract from the overall trend of GLG's reliable performance across settings.
Node Attacker 2-GN. In this experimental setting, the attacker possesses no prior information regarding the graph data and endeavors to reconstruct both the nodal features and the graph structure. Table B summarizes the corresponding results. For the GraphSAGE model, is evident that the adversary can reconstruct both the features and the adjacency matrix with high accuracy on both the Facebook and GitHub datasets. These outcomes are consistent with our theoretical findings presented in Proposition Notably, for the GCN framework, the adversary is still able to reconstruct A with high AUC and AP scores, despite the absence of a theoretical guarantee for node attacker 2-GN in the GCN context (as noted in Section 5 This empirical observation may be attributed to the integration of the feature smoothness and sparsity regularizers defined in Equation equation 14
To further evaluate the impact of the regularizers, we assessed the performance of the attack without their inclusion. The corresponding results, also presented in Table 0 indicate marked decline in the reconstruction performance of the adjacency matrix, particularly in terms of Average Precision (AP), when the regularizers
12

---

Published in Transactions on Machine Learning Research (06/2025)
Table 6: Reconstruction of X (RNMSE) and A (AUC and AP) with Node Attacker 2-GN, comparing GLG and DLG.
Facebook
GitHub
Framework
X (RNMSE)
AUC1
AP1
X (RNMSE)
AUC
AP1
GLG (Ours)
GraphSAGE
0.002410.003
0.9910.01
0.99
0.0024+0.003
0.9910.01
0.99
GCN
1.39
0.97=0.03
0.75=0.10
0.58
0.99#0.04
0.83#0.04
GCN (w/o reg.)
1.19+1108
0.95++0.01
0.65+0.12
0.81+1.41
0.94++0.09
0.72+0.20
DLG
GraphSAGE
0.003+00.0
0.99 0.68+0.33
0.99 0.32
0.0026:10.03
0.98
0.99
GCN
1.01
0.88
0.87=0.05
0.5820.18
Table 7: Reconstruction of A with Graph Attacker-G.
Facebook
GitHub
Framework
ACC
AUC
AP
ACC
AUC
AP
GLG (Ours)
GraphSAGE
1.00-10.00
1.00++0.00
1.00++0.00
1.00++0.00
1.00++0.00
1.00++0.00
GCN
0.97+0.03
0.93+00.05
0.97+0.02
0.97-10.02
0.95+0.04
0.97+0.02
DLG
GraphSAGE
0.50++001
0.50++0.03 0.51+0.022
0.135 0.17+00007
0.50++0.04
0.51+00.02 0.53+0.02
0.15++0.04 0.15
GCN
0.51
0.53+0.01
are omitted. This suggests that the inclusion of these regularizers effectively enhances the performance of the attack.
Furthermore, compare the performance of DLG with our proposed method, GL.G. Our empirical results demonstrate that DLG is capable of reconstructing both the nodal fcatures and the graph structure only within the GraphSAGE framework, in accordance with Proposition 5 In contrast, for the GCN model on both the Facebook and GitHub datasets, GLG consistently outperforms DLG, particularly with respect the reconstruction of the adjacency matrix as indicated by the AUC and AP metrics. These findings underscore the broader applicability and superior performance of GLG, which effective even in scenarios lacking formal theoretical guarantees.
6.3 Graph Attacker
In this subsection, the performance of different graph attackers is evaluated for attacking nodal features as well as the adjacency matrix of the private subgraph.
Graph Attacker-G. Table lists the reconstruction performance of the graph structure. It can be observed that the attacker can perfectly recover the adjacency matrix from the gradients of GraphSAGE model in both datasets. Such results also consistent with the results of Proposition 6 On the other hand, in the case of GCN, despite the absence of theoretical guarantees, the attacker demonstrates high accuracy, precision, and AUC values in identifying the edges. Such results can again be attributed to the fcature smoothness and sparsity regularizer which help leverage usual properties for social nelworks. Unlike the Node allacker setling, DLG performs poorly in reconstructing the graph structure under the graph attacker setting, highlighting limitations in directly handling graph-structured data. To assess the impact of the regularizer, we again conduct the attack with and without the regularizer as shown equations equation 12 and equation 14 The resulting recovered adjacency matrices visualized through heatmaps depicted in Figures 2b and 2c
13

---

Published in Transactions on Machine Learning Research (06/2025)
Table Reconstruction of X (RNMSE) with Graph Attacker-N.
Framework
Facebook
GitHub
GLG (Ours)
GraphSAGE
0.18+0.08 0.61+0.08
0.15+0.08
GCN
0.59+0.08
DLG
GraphSAGE
0.77=00.55
0.20#
GCN
1.32+0.22
0.77+0.00
Figure 2a illustrates the true graph structure of the private data under attack for comparison. The difference in reconstruction quality between the two scenarios is evident. When the regularizer is not used, the attack accurately identifies substantial number of edges. However, this also leads to the erroncous identification of many non-edges as edges, resulting in lower AP score as also shown in the Figure 2
(a)
(b)
Figure 2: The heatmaps of the reconstructed adjacency matrix with Graph Attacker-G from the gradient of GCN models. (a) actual graph. (b) reconstructed graph structure with regularizers (AUC=0.981, AP=1.0). (c) reconstructed graph structure without regularizers (AUC-0.977, AP-0.86).
Graph Attacker-N. this setting, the attacker tries to reconstruct the nodal feature matrix given the gradients and the underlying graph structure. The results are listed in Table [ It can be observed that while the attacker is unable reconstruct nodal features from a GCN model, it can recover nodal features from GraphSAGE. model with small errors. The results also corroborate that this attacker is different from Node Attacker 2-N where the gradients of the loss for each node are leveraged to the attacker. Unlike this scenario, Node Attacker 2-N can successfully reconstruct the nodal features. While GLG performs better on GraphSAGE than on GCN, still consistently outperforms DI. on both architectures, suggesting that DLG struggles to directly handle graph-structured data well due to interdopendencies between nodal features and graph topology.
Graph Attacker-GN. Table 9 reports the performance the Graph Attacker- in reconstructing the graph structure and nodal features. An analysis of the results for our proposed method, GLG, reveals that the reconstructed adjacency matrix obtained with high accuracy for the GraphSAGE. framework. Interestingly, in this experimental setting, the attack on the GCN framework yields even better performance in recovering the graph structure, compared to GraphSAGE. It is worth noting, however, that in both frameworks the reconstruction of the nodal features remains unsatisfactory, highlighting an intrinsic difficulty in recovering node attibuues under this attack paradigm.
A detailed comparison between GLG and the baseline method, DLG, further underscores the superiority of GLG. In the GraphSAGE sctting, while DLG able to some success reconstruction of the graph structure (for Github), its performance is still far inferior that of GLG in terms of key metrics such as RNMSE, AUC, and AP. Moreover, even under the GCN framework, GL.G exceeds the performance of DL.G, despite
14

---

Published in Transactions on Machine Learning Research (06/2025)
Table 9: Reconstruction X (RNMSE) and A (AUC and AP) with Graph Attacker-GN for two different methodologics on Facebook and GitHub datasets.
Facebook
GitHub
Framework
X +
AUC f
AP
X +
AUC f
AP 1
Ours
GraphSAGE
0.58
0.89-1006
0.98
0.62:10.09
0.92
0.98+t0.02
GCN
0.60=0.09
0.92=0.03
0.97
0.61#0.03
0.93#0.01
0.98+0.009
DLG
GraphSAGE
1.39:10.01
0.50
0.20+10.88
0.85
0.71
0.48 0.46
GCN
1.31=0005
0.58
0.2440.14
0.78+0.06
0.88=0.05
0.70#0.08
the absence of theoretical guarantees for nodal feature reconstruction. These empirical findings demonstrate that GTG is more robust and effective in adversarial graph reconstruction, providing enhanced accuracy in reconstructing the adjacency matrix even in challenging scenarios.
Overall, the results clearly establish that GLG is a more reliable and superior approach compared to DLG, as it consistently achieves higher reconstruction accuracy across different graph models and datasets.
7 Conclusion & Future Work
In this work, study the gradient inversion atlack for Graph Neural Networks (GNNs) in federated graph learning setting and explore what information can be leaked about the graph data from the gradient. We studied both the node classification and the graph classification tasks, along with two widely used GNN structures, GraphSAGE and GCN. Through both theoretical and empirical results, we highlighted and analyzed the vulnerabilities of different GNN frameworks across a wide variety of gradient inversion attack settings. Our proposed method, GLG, attains superior accuracy in roconstructing both nodal features and graph structure from gradients.
Future work. In the future, it would be interesting to study the extension of the attack mechanisms to other GNN frameworks, such as GIN (Graph Isomorphism Networks) (Xu et al. 2019) and GAT (Graph Attention Networks) (Veličković et. al. 2018). Experiments and theoretical analysis regarding the vulnerability of other GNN frameworks hence is a promising direction. For example, are certain GNN frameworks more robust to gradient inversion attacks than others? Also, are there any other special properties that can be utilized for graph datasets other than social networks? For instance, it is worth exploiting the fact that the degrees of nodes in molecular datasets exhibit an upper limit. Finally, recent studies such as Wang et al. (2023) have provided theoretical bounds on the reconstruction quality of minibatch data. Hence, an intriguing question would be whether similar guarantees can be established for graph data.
Furthermore, it crucial to have appropriate defense mechanisms place to prevent data leakage. It is commonly believed that employing larger batch sizes could be an effective defense against the gradient inversion attack, but experiments show that even in batches of size 50, the private data be reconstructed with high accuracy. Therefore, solely relying on larger batch sizes is insufficient as defense strategy against gradient inversion attacks. Recent studies such as Wen et al. (2022): Wang et al. (2023) have provided provable guarantees regarding the quality of reconstructed private data from training batches. Based on the various defense strategies introduced in Gupta et al. (2022), some potential defense mechanisms can remain effective in graph sctting: c.g., noisy gradients (Abadi et al.] (0166), gradient pruning (Zhu et al., 2019); encoding inputs (Huang al. (020). However, more specific defensive mechanisms from graph perspectives remain undeveloped.
15

---

Published in Transactions on Machine Learning Research (06/2025)
Acknowledgments
Work in the paper is supported by NSF ECCS 2412484, ECCS 2207457, NSF GEO CI 2425748, and NSF
SaTC Frontiers FG229200.
References
Martin Abadi, Andy Chu, lan Goodfellow, H. Brendan McMahan, llya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, CCS '16, pp. 308 318, New York, NY, USA, 2016. Association for Computing Machinery. ISBN 9781450341394.
Franziska Boenisch, Adam Dziedzic, Roei Schuster, Ali Shahin Shamsabadi, Ili Shumailov, and Nicolas Paper- not. When the curious abandon honesty: Federated learning is not private. arXiv preprint arxiv:21 22.02010021 2021.
Asim Kumar Debnath, Rosa L Lopez de Compadre, Gargi Debnath, Alan Shusterman, and Corwin Hansch. Structure-activity relationship of mutagenic aromatic and heteroaromatic nitro compounds. correlation with molecular orbital energies and hydrophobicity. Journal of medicinal chemistry, 34(2):786-77) 797, 1991.
Maria Drencheva, Ivo Petrov, Maximilian Baader, Dimitar Lliev Dimitrov, and Martin Vechev, GRAIN: Exact graph reconstruction from gradicnts. In The Thirteenth International Conference on Learning Representations, 2025.
Liam Fowl, Jonas Geiping, Steven Reich, Yuxin Wen, Wojtek Czaja, Micah Goldblum, and Tom Goldstein. Decepticons: Corrupted transformers breach privacy in federated learning for language models. arXiv preprint ar Xrx::2201.11077 2022a.
Liam H Fowl, Jonas Geiping, Wojeiech Czaja, Micah Goldblum, and Tom Goldstein. Robbing the fed: Directly obtaining privale data in federated learning with modified models. In International Conference on Learning Representations, 2022b.
Lina Ge, YanKun Li, Haiao Li, Lei Tian, and Zhe Wang. A review of privacy-preservnng research on federated graph neural networks. Neurocomputing, pp. 128166, 2024.
Jonas Geiping, Hartmut Bauermeister, Hannah Dröge, and Michael Moeller, Inverting gradients how easy is it to break privacy in federated learning? In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 16937-16947. Curran Associates, Inc., 2020.
Simon Geisler, Tobias Schmidt, Hakan Sirin, Daniel Zügner, Aleksandar Bojchevski, and Stephan Günnemann. Robustness of graph neural networks at scale. Advances in Neurol Information Processing Systems, 34: (637-7649, 2021.
Rafael BombarlBi,,,llli, Jennifer N Wei, David Duvenaud, José Miguel HernándezzLLoato, Benjamín Sánchez- Lengelin,, Dennis Sheberla, Jorge Aguilera-Iparragiieee Iparraguirre, Timothy D Hirzel, Ryan P Adams, and Alán Aspuru-Guzik. Automatic chemical design using a data-driven continuous representation of molecules. ACS central science, 4(2):268 276, 2018.
Samyak Gupta, Yangsibo Huang, Zexuan Zhong, Tianyu Gao, Kai Li, and Danqi Chen. Recovering private text in federated learning of language models. arXiv preprint XrXo:2200..0 085544, 2022.
William T.. Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning on large graphs. CoRR, abs/1706.02216, 2017.
Chaoyang He, Keshav Balasubramanian, Emir Ceyani, Yu Rong. Peilin Zhao, Junzhou Huang, Murali Annavaram, and Salman Avestimehr. Fedgraphmn: federated learning system and benchmark for graph neural networks. CoRR, abs/2104.07145, 2021.
16

---

Published in Transactions on Machine Learning Research (06/2025)
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. Advances in newral information processing systems, 33:22118 22133, 2020.
Yangsibo Huang, Zhao Song, Kai Li, and Sanjeev Arora. InstaHide: Instance-hiding schemes for private distributed learning. In Hal Daumé III and Aarti Singh (eds.), Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pp. 4507-4518. PMLR, 13-18 Jul 2020.
Forrest N landola, Matthew W Moskewicz, Khalid Ashraf, and Kurt Keutzer. Firecaffe: near-linear acceleration of deep neural network training on compute clusters. In Proceedings of the IEEE Conference on Computer Vision and Pottern Recognition, pp. 2592 2600, 2016.
Jinwoo Jeon, Kangwook Lee, Sewoong Oh, Jungseul Ok, et al. Gradient inversion with generative image prior. Advances in Neural Information Processing Systems, 34:29898 29908, 2021.
Xiao Jin, Pin-Yu Chen, Chia-Yi Yi Hsu, Chia-Mu Yu, and Tianyi Chen. Cafe: Catastrophic data leakage vertical lederated learning. Advances in Newral Information Processing Systems, 34:994 1006, 2021.
Arthur Jochems, Timo M Doist, Issam El Naqa, Marc Kessler, Chuck Mayo, Jackson Reeves, Shruti Jolly, Martha Matuszak, Randall Ten Haken, Johan van Soest, et al. Developing and validating a survival prediction model for uscle patients through distributed learning across 3 countries. International Journal of Rodiation Oncology* Biology* * Physics, 99(2):344 352, 2017.
Jeroen Kazius, Ross McGuire, and Roberta Bursi. Derivation and validation of toxicophores for mutagenicity prediction. Journal of medicinal chemistry, 48(1):312 320, 2005.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. CoRR, abs/1600.02900 2016.
Harold W. Kuhn. The hungarian method for the assignment problem. Naval Research Logistics (NRL), 52, 2010.
Mu Li, David G. Andersen, Jun Woo Park, Alexander J. Smola, Amr Ahmed, Vanja Josifovski, James Long, Eugene J. Shekita, and Bor- Yiing Su. Scaling distributed machine learning with the parameter server. In 11th USENIX Symposium on Operating Systems Design and Implementation (OSDI 14), pp. 583 583-598, Broomfield, CO, 2014. USENIX Association. ISBN 978-1-931971-16
H Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, et al. Communication--ffiiieen learning of deep networks from decentralized data. arXiv preprint 1602 05629, 2016a.
H. Brendan McMahan, Eider Moore, Daniel Ramage, and Blaise Agūera y Arcas. Federated learning of deep networks using model averaging. CoRR, abs/ abs/1602.05629, 2016b.
Christopher Morris, Nils M. Kriege, Franka Bause, Kristian Kersting, Petra Mutzel, and Marion Neumann. Tudataset: collection of benchmark datasets for learning with graphs, 2020.
Pitch Patarasuk and Xin Yuan. Bandwidth optimal all-reduce algorithms for clusters of workstations. Journal of Parallel and Distributed Computing, 69(2):117-12) 2009.
Ivo Petrov, Dimitar Iliev Dimitrov, Maximilian Baader, Mark Niklas Mueller, and Martin Vechev. DAGER: Exact gradient inversion for large language models. In The eightt Annual Conference on Newral Information Processing Systems, 2024.
Kaspar Riesen and Horst Bunke. lam graph database repository for graph based pattern recognition and
machine learning. In Joint IAPR International Workshops Statistical Techniques in Pattern Recognition (SPR) and Structural and Syntactic Pallern Recognilion (SSPR), pp. Springer, 2008.
Benedek Rozemberezki, Carl Allen, and Rik Sarkar. Multi-scale attributed node embedding. CoRR, abs/1909.13022 2019.
17

---

Published in Transactions on Machine Learning Research (06/2025)
Benedek Rozemberczki, Carl Allen, and Rik Sarkar. Multi-Scale Attributed Node Embedding. Journal of Complex Networks, 9(2), 2021.
Simone Scardapane, Indro Spinelli, and Paolo Di Lorenzo. Distributed training of graph convolutional networks. IEFE Transactions Signal and Information Processing over Networks, 7:87-100, 2020.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liö, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Representations, 2018.
Zihan Wang, Jason Lee, and Qi Lei. Reconstructing training data from model gradient, provably. In International Conference on Artificial Intelligence and Statistics, 6595 6612. PMLR, 2023.
Yuxin Wen, Jonas Geiping, Liam Fowl, Micah Goldblum, and Tom Goldstein. Fishing for user data in large-batch federated learning via gradient magnification. arXiv:2202.00880 fes], February 2022.
Zhenqin Wu, Bharath Ramsundar, Evan N Feinberg, Joseph Gomes, Caleb Geniesse, Aneesh S Pappu, Karl Leswing, and Vijay Pande. Moleculenet: a benchmark for molecular machine learning. Chemical science, 9 (2):513 530, 2018.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? Tn International Conference on Learning Representations, 2019.
Kevin Yang, Kyle Swanson, Wengong Jin, Connor Coley, Philipp Eiden, Hua Gao, Angel Cuzzan-Perez, Timothy Hopper, Brian Kelley, Miriam Mathca, et al. Analyzing learned molecular representations for property prediction. Journal of chemical information and modeling, 59(8):3370 3388, 2019.
Hongxu Yin, Arun Mallya, Arash Vahdat, Jose M Alvarcz, Jan Kautz, and Pavlo Molchanov. See through gradients: Image batch recovery via gradinversion. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition, pp. 16337-16346, 2021.
Huanding Zhang, Tao Shen, Fei Wu, Mingyang Yin, Hongxia Yang, and Chao Wu. Federated graph learning a position paper. Xrxiv preprint arXiv:2105. 11099, 2021.
Zaixi Zhang, Qi Liu, Zhenya Huang, Hao Wang, Choo-Kong Lee, and Enhong Chen. Model inversion attacks against graph neural networks. IEEE Transactions on Knowledge and Data Engineering, pp. 13, 2022. doi: 20009/TKD220222
Bo Zhao, Konda Reddy Mopuri, and Hakan Bilen. idlg: Improved deep leakage from gradients. CoRR, abs/2001.020 .02610, 2020a.
Bo Zhao, Konda Reddy Mopuri, and Hakan Bilen. idlg: Improved deep leakage from gradients. arXiv preprint arXiv:2001.0220 002610, 2020b.
Junyi Zhu and Matthew Blaschko. R-gap: Recursive gradient attack on privacy. arXiv preprinl XXi:22010.07733, 2020.
Ligeng Zhu, Zhijian Liu, and Song Han. Deep leakage from gradients. In H. Wallach, H. Larochelle, Beygelzimer, F. d' d'Alché-Buc, E. Fox, and R. Garnett (eds.), Advances Newral Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
18

---

Published in Transactions on Machine Learning Research (06/2025)
A
Attack Algorithms
Algorithm GLG (Node Attacker).
1: Input:
2-layer GNN model F(x,, (Xey HeN, W)
2: VwL,; gradients calculated by training data, Yui True label
Output: private data X₂
//Tnitialize dummy target and neighboring node features by creating two level tree with degree as dirce and the label:
5: Initialize &. and (8o,HEN.
6: for - to P do
7:
//Compute dummy gradients:
VwL, = {&g Jea, W).
Compute DDP as equation 12
10:
&p+1 x 1/
V
11: for j N₂ do
12:
2p+1 ,, V x DP
13: end for
14: end for
15: return & x PP41
Algorithm GLG (Node Attacker 2)
1: Input: GNN model F(X, A, W), W: parameter weights; VwC gradients calculated by private training data for each node in the graph, y: True label
Output: private training data X,
Initialize dummy features and labels X1, A
for p - 1 to P do
5: //Compute dummy gradients:
6: Vw = @CF AP, W),y)/OW
7: Compute TDP as given in equation 14
8: Xp+1 X -, xx....
Art1 = proj (AP n/ A.D)
10: end for
11: return X P+1 Å (Ar(A
Algorithm Graph Attacker
1: Input: GNN model F(X, W), W: parameter weights; WwL: gradients calculated by private training data, y: True label
Output: private training data X. A
Initialize dummy features and labels X1 A
for p + 1 to P do
//Compute dummy gradients: 6: Vw = OC(F(X* (XP,A) AP, W).y)/0W
7: Compute DD as given in equation 12
Xp+1 = V/ D Dr,
Ap+1 = p-11=poojo.u (AP v/V A= ID),
10: end for
11: return X X+1++1
p+1
(A+1))))
19

---

Published in Transactions on Machine Learning Research (06/2025)
B Extracting ground-truth labels
In a classification task, it possible to extract the ground-truth labels from the gradients as shown Zhao et al. [2020a). Similary, it possible to extract the ground-truth labels in a graph/ node classification task. We demonstrate how to extract the ground-truth labels when cross-entropy loss is used defined in equation 5 The gradients of the loss with respect to is given by
ac
-1+
E
cPc
if K
9i 0p,
(22)
cPc cPj
else.
Since (5,-² spi Σ sb.
(0, 1) therefore 9i E (-1,0) when i i= and 9i (0, otherwise. Now consider the node
classification task for a GCN layer as defined in equation 3 For the final layer of the model with output as h = p we can write the gradients of the loss as follows
DC OC 0p:
Vww,
(23)
O(W); Òp. a(W);
① (a (hass (W), - b.))
Di
(24)
O(W);
9: A h
(25)
As hass independent of the logit. index i, and A because of the sigmoid non-linearity, the ground-truth label k can be identified by just checking the signs of V(w),C C for all i. Formally, the ground-truth label k is the one for which the following condition holds
istt. V(w). 50,
(26)
C Proof of Proposition I for GraphSAGE
For GraphSAGE layer defined in equation the gradient equations for the first layer can be written as follows
h, = a(ho),
(27)
h, W + W +b,
(28)
(W.), C, V(hi): Lo V(w.). (hr).. V V(W.), = ((b). x
(29)
(30)
D Proof of Proposition 2
For a GraphSAGE layer as shown in equation the target nodal features can be recovered as the following
h. o (h.).
(31)
h, = W + x, W.J +b,
(32)
V (W.), C. = V(h.).fo fo V(w.). (hw)..
(33)
V V(wa), C. Vob),fo. Xx-
(34)
The target nodal features henceforth be reconstructed x, ((W.).or V Lo as long V(b). L, + 0.
20

---

Published in Transactions on Machine Learning Research (06/2025)
E Proof of Proposition 6
Proof. For GraphSAGE framework shown in equation 6 let H be the hidden node representation matrix before applying the non-linearity as shown below
H = (H))
(35)
H Äx + +WW + Пb.
(36)
The derivatives of the loss function with respect to the weights w, 22, and bias b the first convolutional layer can be written
dc
OC
HH
OC (AX)k)
Σ
(37)
I(Wi);
HH
6
1W1);
HH
0C
N
OL
(X)sr
(38)
((W)).
ÖH
OC
OC
(39)
0(b),
HH
where ① denotes the partial derivative operator. Equations equation 37 lequatiin 39 can be written in matrix form as the following
( V Vw,C",
(40)
x VHC = Vw,C"
(41)
VaC i = VbC..
(42)
It be observed from equation 40::::00000-uuuuuu equation 41 that there two unknowns À and VaC. However A and V V be computed directly from the above equations. Given equation 41 and the fact that X is full-row rank, VgC can be obtained as follows
(43)
Plugging the value of C in equation 40 À can be calculated as
Á X(Vw, (Vw,
(44)
0
F
Supplementary Experimental Results and Analysis
Table 10: Dataset statistics for Node Classification task.
Dataset
# #Nodes
Edges
#Labels
GitHub 37,300
578,006
2
Facebook
22,170
342,004
F.1 Node Attacker 1: One-hop Neighborhood Nodal Feature Reconstruction
To evaluate the performance the node attacker in reconstructing the nodal features of one-hop neighbors, a target node is selected randomly from the graph. A dummy graph initialized as a depth-2 tree with deree set the actual number of one-hop neighbors of the target node. Since there's permutation ambiguity the reconstructed nodal features, the Hungarian Algorithm used to find the best match with the original
21

---

Published in Transactions on Machine Learning Research (06/2025)
Table 11: Target node feature reconstruction X (RNMSE x10- for Node Attacker in a batched setting.
Dataset
B=5
B=20
B=50
Mean
0.07
0.8:00.3
3.9:1144
Synth.
Min
0.0
0.13
0.4
Mean
0.9:0044
12:64
17:955
FB
Min
0.8
28
65
Mean
28:11
126-178
1324:83
Github
Min
0.3
111
107
Table 12: dataset.
Reconstruction performance of X (RNMSE x10-²) for Graph Attacker-N for batched graph
d
B=5
B=20
B=50
Mean
23 31
82 27
11911
4
Min
0.04
86
Mean
25:33
84+34
121#99
8
Min
0.04
87
Mean 224330
89436
12119
12
Min
0.04
87
neighboring node features KKuhn 2010). Figure 3 shows the one-hop neighbor reconstruction error (RNMSF) using GraphSAGE. The results are averaged over 10 randomly selected nodes. For some nodes, the nodal features of neighbors were reconstructed accurately. For example, nodes 0 and 8 in Figure 3a for Facebook. Further, although the mean RNMSE of the reconstructed neighbors is high, the minimum RNMSE of the best-reconstructed neighbors can be low (node 9 in Figure 3ab. indicating private data leakage.
1.50
1.25
0.25
1.25
1.00
0.20
1.00
0.75
0.15
0.75
0.50
0.00
Node
Node
(a) Facebook
(b) Synthetic
(c) Github
Figure 3: One-hop neighbor reconstruction (RNMSE) for Node Attacker- with GraphSAGE.
F.2
Attacking batched data
We also extended the experiments for node and graph attackers to the minibatch setting. Specifically, we only evaluate GraphSAGE for both tasks since provides the best reconstruction in the stochastic (single data sample) setting shown in the previous experiments. Although effective attack techniques (Wen et al. 2022 have been proposed to reconstruct image data from large batches, here tested the performance of the attackers by simply optimizing with respect to the dummy input batch. Hence, the performance may improve if attack techniques for batch data are also incorporated. Due to possible permutation ambiguily in a batch setting, the Hungarian algorithm is used to find the best match with the actual input data. The evaluation metric for the algorithm is the RNMSE between all pairs of the dummy batch and the actual batch. These results are averaged over 10 independent runs for each batch size. Experiments are conducted for Node Attacker 1 and Graph Attacker-N.
22

---

Published in Transactions on Machine Learning Research (06/2025)
Node Attacker 1. Table 11 shows the performance of reconstructing the target node features for batches of size B 5, 20, and 50. It can be observed that the best results are obtained for the Synthetie Dataset with accurate reconstruction across all batch sizes. When the batch size is B = 5, the attack provides accurate roconstruction across all the datasets.
Graph Attacker-N. In this scenario, the attack attempts to reconstruct X for the whole batch with A being known. To simplify the matching after rumning the attack we only consider graphs with the same number of nodes. This is done by generating Erdos-Reng Renyi (ER) graphs with the number of nodes n = 50. For FR graph with nodes and edge probability p, the average degree of node = (n - 1)p. We conduct. experiments by varying with different batch sizes. The nodal features are generated by sampling from the standard normal distribution i.c. (0, 1). Table 12 lists the performance of reconstructing X with varying batch sizes and degrees. As expected, the quality of reconstruction declines with increasing batch size, with the best results being achieved at B 5. Also, the performance remains roughly the same across all degrees.
F.3 Sensitivity Analysis for Hyperparameters
In our attack, numerous hyperparameters come into play, including but not limited to the rogularization parameters and 3, the graph size, and the network width. In our analysis, we examined subset of these hyperparameters in different settings and subsequently present the corresponding outcomes below.
2.5
2.0
RNMSE
1.5
1.0
0.5
250 500 750 1000 1250 1500 17502000
Number of Hidden Channels
Figure 4: Variation in RNMSE of the reconstructed target features vs. the number of hidden channels for a GCN framework on the Github dataset.
Network Width. All previous experiments conducted with the number of hidden channels set to 100. In the setting of Node Attacker 1, the attack could successfully reconstruct the target nodal features for a GraphSAGE framework with high accuracy. However, for a GCN framework, the attack only managed to reconstruct the aggregated nodal features. Consequently, in this section, we explore the impact of varying the number of hidden channels in the 2-layer GCN framework on the quality of reconstruction. Figure illustrates the results of target node feature reconstruction for the Github Dataset. Notably, as the number of hidden channels increases, there is clear decrease in the RNMSE values, suggesting that wider networks are more susceptible to the attack.
Regularization Hyperparameters. To investigate the influence of and 3 in equation 14 we examine the effects the reconstruction performance of Graph Attacker-G for the GCN framework. More specifically, maintain one hyperparameter at fixed value while altering the other, and depict the AUC and AP values. Figure 5a illustrates the AUC and AP values for different a values in log scale with base 10. The values on the x-axis are also in the log scale with base 10. In Figure 5a a is varied while keeping 3 = 10-7 Similarly, in Figure 5b] where 3 is varied, is fixed at 10 It is evident from the figures that higher values of hyperparameters severely degrade the performance of the attack whereas extremely low values give suboptimal results. This clearly demonstrates the effectiveness of the feature smoothness and sparsity regularizers.
23

---

Published in Transactions on Machine Learning Research (06/2025)
AUC
1.0
AVC
0.9
0.8
0.7
0.2
0.6
0.0
-13
-12
-11
-10
-8
-7
-6
4
-13
-10
-9
5
B
(a)
(b)
Figure 5: Variation of AUC and AP vs. a and 3 for Graph Attacker-C.
G Additional Graph Classification results on TUDatasets
All attack settings considered in previous experiments in Section 0 are defined within the context of social networks. In order to assess the efficacy of the attack on alternative datasets, such as molecular datasets which are commonly employed in graph classification tasks, we extend our analysis the TUDatasct (Morris et al. 2020
For the graph classification task, conduct the attack on the following three datasets from the TUDataset repository (Morris et al. 2020).
MUTAG (Debnath al. 1991 It consists of 188 chemical compounds from two classes. The vertices represent atoms and edges represent chemical bonds. Node features denote the atom type represented by one-hot encoding. Labels represent their mutagenic effect on specific gram-negative bacterium.
COIL-RAG (Riesen & Bunke 2008
Datasct in computer vision where images of objects represented region adjacency graphs Each node in the graph is specific part in the original image, Graph labels denote the object type.
FRANKENSTEIN Kazius et al. 2005 It contains graphs representing chemical molecules, where the vertices are chemical atoms and edges represent the bonding, Node features denote the atom type. Binary labels represent mutagenecity.
The average number of nodes in the graphs of these datasets is significantly smaller than social networks (sce Table 13 However, unlike social networks, these graphs might not necessarily exhibit properties like feature hnoothness and sparsity. Hence, for all the attacks we use the objective function as defined in equation 12 The results in all attack settings are again consistent with the theoretical analysis.
The results are obtained by randomly selecting 20 graphs from the datasets. The selected graphs are fixed for different parameter selections for fair comparison. this case since the graphs are small we can directly use the Mean Absolute Error (MAE) of the reconstructed adjacency matrix measure the performance of reconstructing the underlying graph structure. Specifically, the MAE is given follows
2 |trioower (A) tritower (ritower(AA)
MAF A, A)
(45)
N(N + +
Also, instead of directly sampling edges from the probabilistic adjacency matrix as given in Section 4.2 the MAE also evaluated with and without thresholding the reconstructed adjacency matrix. We apply min-max normalization the resulting Å before thresholding. After applying the threshold, A, == th, is obtained, where (Z, entry-wise operator that returns 0 if zij т, and returns otherwise.
24

---

Published in Transactions on Machine Learning Research (06/2025)
Table 13: Dataset statistics (Graph Classification). Edge density is calculated based on (#Avg.Edges Edges in the fully connected graph).
Dataset
#Avg. Nodes
#Avg. Edge
#Edge Density
#Labels
MUTAG
17.93
19.79
0.1304
2
COIL-RAG
3.01
3.02
0.9983
100
FRANK.
16.90
17.88
0.1331
2
Table 14: Reconstruction of A (MAE) for Graph Attacker-G
(a) GraphSAGE
(b) GCN
MUTAG
COIL-RAG
TRANN.(x10-1
MUTAG
COIL-RAG FRANK, (x10-2)
N/A
0.2540.10
0.02+:0.4
0.08
N/A
0.20#0.04
0.22+0.11
4.58+2.99
0.2
0.2740.11
0.03+0007
0.0++0.0
0.2
0.27=0.07
0.16=0.09
4.74
0.4
0.24+0.11
0.03
0.0++0.0
0.4
0.19+0.06
0.16+0.09
4.20+2.15
0.6
0.23:0.11
0.02 + 0.04
0.0
0.6
0.1520.04
0.16
1.08=11.96
0.8
0,23+0.10
0.003:10.13
0.0:00.0
0.8
0,14#0.01
0.26
4.22+2.04
Graph Attacker-G. Table 14 shows the MAE of reconstructing A with thresholding (for different values of r) and without (N/A in the table). The attack achieves the best results on the FRANKENSTEIN dataset while using GraphSAGE. Each node in the FRANKENSTEIN dataset has D 780 features, whereas MUTAG and COIL-RAG have only = 7 and D = 64 features respectively. Moreover, the average mumber of nodes (N) per graph in FRANKENSTEIN, MUTAG and COIL-RAG are 16.9, 17.9 and 3.01 respectively. This implies that X E RND is full-row rank with high probability in COIL-RAG and FRANKENSTEIN. Meanwhile, the node features in the MUTAG dataset consist of only binary values. It can be observed from the experimental results that the best and worst results are obtained on FRANKENSTEIN and MUTAG respectively. This is also consistent with Proposition G which requires X to be full row-rank for successfully reconstructing A. The reconstruction performance improves for COIL-RAG with GraphSAGE at r 0.8. The FRANKENSTEIN dataset is reconstructed accurately even with the GCN framework.
Graph Attacker-N. Table 15 lists the RNMSE of reconstructing X. can be observed that the allack is able to reconstruct X with high accuracy for GraphSAGE across all three datasets. For the GCN framework, it can be observed that the algorithm fails to reconstruct X.
Graph Attacker-GN, In this scenario, since the attacker has no knowledge of the graph data, try different settings and observe their effects on the reconstruction. To improve the attack for Graph Attacker-GN where we have no prior knowledge of the graph, we utilize various initialization and thresholding strategies. Specifically, since the optimization process given in the algorithms can be greatly improved by utilizing different starting points, we initialize the dummy node feature and adjacency matrices with different values. In the case of thresholding, instead of sampling the edges given the probabilistic adjacency matrix Á P+1 we various threshold values to sample edges.
The effect of initialization: Previous studies have established that the quality of reconstruction heavily depends on the initialization (Gupta et al. 2022 Geiping et al., 2020). The closer the initialization is to the original data, the better the reconstruction. An initialization value of 0.1 implies that all the entries of X and are initialized to 0.1 and similarly A 1) implies that all entries are initialized from the standard
Table 15: Reconstruction of X (RNMSE) for Graph Attacker-N.
MUTAG COIL-RAG FRANK.
GraphSAGE(x110
6.9117.1 1.51 8.80+1127
0.07+0.06
21.95+16.05
GCN
2.68-40.0
25

---

Published in Transactions on Machine Learning Research (06/2025)
0.175
0.20
0.30
0.150
0.8
0.15
0.25
2 0.075
9.300
1.0
0.10
0.050
0.10
0.05
0.000
0.00
15 17
Number
Number
(a) Eutries of X² and A set to 1 (b) Entries of X and A set to
(c) Entries of X² and A sampled from N 1)
Figure 6: Reconstruction of different graph structures (MAE) for Graph Attacker-GN using GraphSAGE.
Table 16: Reconstruction of A (MAE) in for Graph Attacker-Gi GN with different thresholds.
(a) GraphSAGE
(b) GCN
MUTAG COIL-RAG FRANK.
MUTAG COIL-RAG FRANK.
N/A
0.37+0.10
0.18++011
0.41=0.17
N/A
0.48+00.5
0.20+0.12
0.41+00008
0.2
0.47 +0.13
0.20+0.11
0.64-0.25
0.2
0.68 =000
0.15+0.08
0.64+0.08
0.4
0.13
0.15
0.50
0.4
0.55 =0.07
0.14
0.46:10.12
0.5
0.39
0.14
0.38=0.20
0.3
0.47
=0.07
0.14+0.08
0.38
0.6
0.32
0.1110.188
0.29=0.15
0.6
0.40
0.14
0.32+00110
0.8
0.26
0.19+0018
0.19=0.10
0.8
0.30+00005
0.32+0.34
0.19+00.08
normal distribution. Since the values of X and A lie in the range [0. 1] for all three datasets, we tested the effect of different initialization points in the same range. Specifically, we tested the initialization values as {0, 02..0,,..3 0.5, 1, 1)}. The results of the attack with different initialization strategies is shown in Table 18 The leftmost column gives the initialization values of the dummy adjacency and node feature matrices. For the adjacency matrix, the results are listed with and without thresholding, Similar Scenario 2, we apply min-max normalization (before thresholding) and threshold value of 0.5 is chosen. A more compact version of the results showing the best performance over all initialization strategies is shown in Table 17 It can be observed that for GraphSAGE, the attack can accurately reconstruct both X and A in the MUTAG and FRANKENSTEIN datasets. While using GCN, even though X cannot be recovered, A can be reconstructed accurately.
For GraphSAGE in Table 18a attack can accurately reconstruct both X and A just by utilising a good initialization strategy. For example, in Table 18a for the FRANKENSTEIN dataset, the attack gives a high error for both A and X while using (N0, 1) as the initialization. However, the MAF drops by orders of magnitude when we initialize X and A to value of 0.2. Even for the GCN framework in Table I8b] while the data cannot be reconstructed in most of the cases, it can be observed that a good initialization point can leak A in COIL-RAG and PRANKENSTEIN datasets.
can be observed that even without any knowledge of the graph data, the
The effect of threshold: To explore the effect of thresholding on the adjacency matrix, we examined the MAE across all three datasets using different threshold values. Table 16 lists the MAE of reconstructing A at. different thresholds. It can be observed that unlike Scenario 2, the performance of the algorithm stays roughly the same for both GraphSAGE and GCN. Also, the FRANKENSTEIN dataset is no longer vulnerable to the attack unlike Scenario 2. Few of the threshold values reduce the MAE by considerable amount. For example, == 0.8 works well for MUTAG and PRANKENSTEIN in the case of GraphSAGE, and for MUTAG in the case of GCN.
Vulnerable graph structures: In order to identify vulnerable graph structures, we tested the performance of the attack in attacking graphs with varying numbers of nodes and edges for the GraphSAGE framework.
26

---

Published in Transactions on Machine Learning Research (06/2025)
Table 17: Reconstruction of X (RNMSE) and A (MAE) for Graph Attacker-GN.
GraphSAGE
GCN
Dataset
X
A..5
x
A
A0.5
MUTAG 0.0027=0.007S
0.22=0009
0.21
1.07=0.20
0.2440.02
0.14=0.04
COIL-RAG 0.005 + 0.0015
0.01=0.03
0.001 0.00+10.00
0.74+00113
0.05+0.10
0.03=0.10
FRANK.
0.01+000006
0.004 + 0.002
0.63
0.07
0.007+10.01
Table 18: Reconstruction of X (RNMSE) and A (MAE) for Graph Attacker-GN.
(a) GraphSAGE
MUTAG
COIL-RAG (x10-3)
FRANK. (x10-
énit
8 2x
A
Âu.5
X
Au.5
8
Åo.5
0.0
4+1
0.37+0.10
0.47+0.13
3148
1+9
4+8
29+14
27+15
21+15
0.1
0.9+0.9
0.23+0.08
0.26 + 0.14
2241
9+8
3+7
4+5
1+2
0.6+1
0.2
0.8+2
0.22+0.09
0.21+0.11
9+-
5+44
0.5+2
140.6
0.4+0.2
0.0+0.0
0.5
0.310.4
0.2310.10
0.22+:012
0.611
143
0.120.6
110.9
0.410.3
0.010.0
1.0
0.240.7
0.23+0.10
0.2210.11
0.511
143
0.1
1:4
0.4
+0.8
0.0610.2
N(0,1) 1)
6
0.37 + 0.10
0.39 0.13
26
12
18
+:
14
66
13
17
38 20
(b) GCN
MUTAG
COIL-RAG
FRANK.
*
Á
Åo.s
Á
Ao.5
X
Åo.5
0.0
1.38+0.31
0.25+0.05
0.21+0007
1.964-2.2
0.05+0.10
0.03+0.10
1.11+0.27
0.11+0.03
0.03+0.04
0.1
1.06 + 0.15
0.24+0.02
0.14+0.04
1.54
0.43+0044
0.42+0.47
0.66+0.15
0.07+0.02
0.007+0.01
0.2
1.07+0.20
0.25 0.02
0.14+0004
1.12:0.71
0.50+0.40
0.47+0.43
0.63+00118
0.007+0.01 0.08+0.02
1.47+00.3
0.33+00066
0.23+0.09
0.75+0.14
0.17+0.33
0.17+0..3
0.72+0.25
0.14+0.05
0.05+00.77
1.0
1.15+0.33
0.3440.04
0.26=0006
0.74+0.113
0.76+0.31
0.78+0.32
0.81+0.23
0.19+0.05
13400.00
N00, 1)
3.26+6033
0.48 + 0.05 0.47 + 0.07
7.98 + 1.50 0.20 + 0.12
0.14 + 0.08
4.54 + 0.44 0.41 + 0.08
0.388 + 0.11
Specifically, the performance was tested on Erdos- Erdos-Renyi graphs (with varying edge probabilities). Figure shows the MAE of reconstructing A for different graphs. The number of features for all graphs is set to 10, and their values are sampled from the standard normal distribution. Each subfigure represents different initialization strategies for X and Å. For each graph with specifie number of nodes, the MAE is averaged over 20 runs of the attack. As the number of nodes in graph increases, the quality of reconstruction decrcases. More importantly, it is evident that the vulnerability to the attack increases with decreasing sparsity. Fully connected graphs (ER graphs with edge probability 1.0) are the least vulnerable to the attack.
Table 19: Reconstruction performance (GSM-0, GSM-1, GSM-2, and Full) Tox21 results using GCN.
GSM-0
GSM-1
GSM-2
FULL
GLG (Ours)
80.86
96.51
+11
97.02+0.8
98.71 +1.0
333
-2.8
GRAIN
86.9142 5.7
83.9*52
552
6.9
82.6
7.4
5.7
68.0 1.7
DLG
31.8+4. 4.3
20.3+5.5
22.8
6.6
0.2
0.2
5.6
DLG + A
54.7 -12
60.1 5.2
76.7
1.0
TabLeak
25.1
12.4+5.5
10.8
1.0
3.9
TabLeak +
55.6
57.7141
73.8
1.0 0.2
27

---

Published in Transactions on Machine Learning Research (06/2025)
Table 20:
Reconstruction of X (RNMSE U) and (AUC f and AP f) with Graph Attacker- GN on Tox21 dataset using GCN.
Framework
X
AUC
AP 1
GLG (Ours)
0.93 0.76=0.13 1.35+0.03
0.9410.04 0.91
GRAIN
0.6510.11
H Comparison with Other Methods
In this section, we compare our proposed gradient inversion attack, GLG, against several existing methods, including the only other graph-specific gradient inversion approach, GRAIN (Drencheva al. 2025 well as two widely used baselines originally designed for image or tabular data, DLG and TabLeak. We evaluate our approach on the Tox21 dataset, well-known chemical dataset from the MoleculeNet benchmark (Wu et al. 2018). The task is to reconstruct. both the node features X and the adjacency matrix from gradients alone.
Our evaluation utilizes the GSM-k metric as introduced in Drencheva al. 2025 where for each k we aggregate the k-hop neighborhood for each node. This is done by randomly initializing a GCN model with 2 k layers. We also include evaluation metrics the Tox21 dataset to provide more detailed comparison.
H.1 Detailed Analysis
We evaluate method under the Graph attacker-GN threat model, which attempts to reconstruct both the node feature matrix X and the adjacency matrix A given the gradients. Table 19 shows that while reconstruction of X remains challenging, as indicated by a relatively lower GSM-0 score, reconstruction of the graph structure (reflected in the GSM-1, GSM-2 and FULL scores) is significantly improved compared to other methods, Table 20 presents the RNMSE, AUC, and AP results for a more detailed comparison between GLG and GRAIN.
Observations.
Node Feature Reconstruction (GSM-0): The GSM-O score measures the fidelity of the node feature reconstruction. Our experiments indicate that reconstructing X from gradients is challenging due to the lack of direct node-level supervision during backpropagation through graph convolutional layers.
Subgraph and Full Graph Reconstruction (GSM-1, GSM-2, FULL): In contrast, the higher GSM-k scores for k: 2 1 demonstrate that the graph structure reconstructed with high accuracy. This suggests that even if individual node features are not perfectly reconstructed, the aggregation of multi-hop neighborhood information helps approximate the overall topology of the graph.
Comparison with GRAIN: Although GRAIN is tailored for graph gradient inversion attacks, our method achieves higher scores in capturing global structure as indicated by improved GSM-1, GSM-2, and FULL metrics. Table 20 shows a similar trend: GLG more effectively reconstructs the graph structure, as indicated by higher AUC and AP, while also slightly improving nodal fcature reconstruction, as reflected by the lower RNMSE.
Baseline Methods (DLG and TabLeak): These methods, originally developed for images and tabular data, undcrperform in the graph domain. Even when augmented with the adjacency matrix information ("+A"), their performance across all GSM metrics remains inferior, highlighting the unique challenges of gradient inversion attacks graph data.
Interpretation. The lower GSM-0 score suggests that reconstructing node features X purely from gradient information is non-trivial. However, the significant improvements observed in GSM-1, GSM-2, and FULL indicate that the model highly effective capturing the graph structure. This is critical, as many practical applications depend on the accurate reconstruction of the graph topology rather than on precise node-level details.
28

---

Published in Transactions on Machine Learning Research (06/2025)
Conclusion. Overall, our experimental results demonstrate that our method outperforms existing gradient inversion attacks on the Tox21 dataset, particularly in reconstructing the global graph structure. Although node feature reconstruction remains an open challenge, leveraging multi-hop neighborhood information through the GSM-k metric allows for robust approximation of the overall graph, thereby opening new avenues for research graph-based based gradient inversion attacks.
29


Reviews:
[{"review_id": "oSV5xFjWek", "reviewer": "Reviewer_f6ne", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths  \n1.\tThe paper studies gradient inversion attacks for graph federated learning, which is valuable for the privacy of graph machine learning.   \n2.\tThe paper is generally clearly written and easy to follow.  \n3.\tThe authors have provided theoretical support for their proposed method.   \n\nWeaknesses  \n1.\tThe authors state in the third paragraph of the introduction, \"To our best knowledge, this is the first work that studies gradient-based attacks for graph data.\" However, they should clarify that while this may be the first study focusing on the federated learning scenario, numerous papers have already addressed gradient-based attacks in other contexts, such as PRBCD [1].  \n2.\tThe authors claim that few studies have investigated the issue of information leakage for graph data in the federated domain. However, based on my understanding, there is already a substantial body of existing research on privacy protection in the field of federated graph learning, e.g., see a comprehensive survey [2]. The authors should clearly compare with the literature to truly demonstrate the novelty of their contribution.  \n3.\tFor the technical part, my major concern is that the proposed method (Section 3) essentially adapts existing general-purpose gradient inversion attack methods into GNN scenarios with limited novelty. It would make the paper stronger if the authors could provide tailored model designs for federated graph learning. For example, the authors mention that graphs have structure and features, making them more difficult to extract. However, the proposed method seems not to delve deep into further analyzing and dealing with this challenge, but rather extracting features and structure separately.  \n4.\tIn experiments, the authors only verify the validity of the proposed method, but do not compare it with any baseline, which makes it hard to truly assess the effectiveness of the proposed method. Besides, the adopted datasets are not well-adopted benchmarks in graph machine learning (e.g., the Open Graph Benchmark). The authors may want to provide clarifications for the experimental designs.   \n \n[1] Robustness of graph neural networks at scale, NeurIPS’21  \n[2] A review of privacy-preserving research on federated graph neural networks, NeuroComputing’21", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper investigates the vulnerability of Graph Neural Networks (GNNs) against gradient inversion attacks within the context of federated learning, where the goal is to train over large graph datasets while preserving data privacy. The motivation stems from the increasing use of GNNs in various applications and the potential risk of private data leakage through gradient exchanges, which has not been extensively studied for graph data. The authors propose a novel attack named Graph Leakage from Gradients and analyze its effectiveness on two widely-used GNN frameworks: GCN and GraphSAGE. The method involves both theoretical analysis and empirical validation to demonstrate that parts of the graph data can indeed be leaked from the gradients. The experiments are conducted over real-world social network datasets as well as synthetic datasets, using various evaluation metrics such as Root Normalised Mean Squared Error for nodal features and accuracy, AUC, and AP for graph structure recovery. The results show that attackers can recover significant information about the graph structure and nodal features.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Overall, I think the paper needs further clarifications on comparisons with the liteature, novelty in model, and experimental designs (see Weaknesses for details).", "broader_impact_concerns": "NA", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "yTn1CSGeS5", "reviewer": "Reviewer_CLWN", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: \n\n- I like the clarity of the writing\n- the propositions add theoretical insights\n- the performance seems to be good\n- an effect of the regularisation is examiend\n\nWeaknesses:\n\n- There exists work that studies attacking GNN federated learning [GRAIN: Exact Graph Reconstruction from Gradients (https://arxiv.org/abs/2503.01838) but on openreview since ICLR 2025 submission] So the claim that this is the first work is not true. Since the other work is open since September it is debatable whether it is concurrent\n- There is no baseline in the empiric eval", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors propose to do gradient inversion attacks to reconstruct graph data (features, structure or both) in a federated learning scenario. They provide theoretic results for GCN and GraphSage and demonstrate seemingly good empirical performance for node classification and graph classification.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- discuss the mentioned baseline in great detail\n- add baselines (as GRAIN does; straightforward application of related work)\n- compare to GRAIN empirically", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "jupzJYU49O", "reviewer": "Reviewer_mTSV", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. Understanding the privacy leakage in graph federated learning is important.\n2. The proposed approach achieved some reasonable effectiveness in inducing privacy leakage. \n\n Weaknesses:\n1. The research challenge is not clearly defined. There are many gradient inversion attacks in other euclidean domains such as images. Therefore, a very natural question is, whether those methods can be effectively applied with minimal modifications. If the modifications are not straightforward and requires significant research effort, this can be claimed as a new contribution. This part is basically lacking from the paper. \n2. The threat model is never mentioned in the paper. Such threat modeling is a standard practice in cybersecurity related problems and the authors should clearly define what is the attacker capability as well as the attacker knowledge.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies the gradient inversion attacks in federated graph learning to recover sensitive attributes such as node features as well as graph structures, depending on the specific classification tasks. This is the first work contributing to understand the privacy leakage in the vanilla graph federated learning. Empirical results show that the proposed approach indeed can leak significant information in different settings.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. Clearly define the research challenges. And in response to this, the authors should show the results of the existing baselines in the Euclidean domain and show how (well/poorly) these methods would perform when applied with minimal or somewhat trivial modifications. I would expect the Eq. (13) would be a key deciding factor and without this term, the attack performance may be low on graph data. However, using such a term also makes the distinction with Zhang et al. (2022) unclear and the authors need to clearly position themselves well in the literature. \n2. For the threat model, the authors should consider levels of threat models to understand the effectiveness of the attacks. It is fine to start from the complete white-box settings where the attacker knows the all possible information about the target victim. Then, start to relax some of the assumptions such as only having access to partial gradient information, or the adversarial clients are not always selected during the model training process. Instead of exhaustively listing all possible changes, the general guideline here is to consider what assumptions are likely too strong in practical applications and then gradually relax them to achieve a holistic view of the attack performance.", "broader_impact_concerns": "Broader impact is not considered and the authors should discuss the implications of the proposed attacks to the society.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper investigates the vulnerability of Graph Neural Networks (GNNs) to gradient inversion attacks in federated learning, with the goal of training on large graph datasets while preserving data privacy. The motivation is strong, and the authors propose a novel attack method, Graph Leakage from Gradients, to analyze GCN and GraphSAGE. The paper provides both empirical evaluations and theoretical analyses, and the writing is clear and well-organized. There are a few suggestions for improvement: it would be beneficial to include baseline results, clarify some claims and statements, and better illustrate the challenges and rationale behind the method design. Overall, this is a good work that could be accepted after revision.
Decision: Accept (poster)