GRAIN: Exact Graph Reconstruction from Gradients
Authors: Maria Drencheva
Ivo Petrov
Maximilian Baader
Dimitar Iliev Dimitrov
Martin Vechev
Venue: ICLR 2025 Poster (2025)
Keywords: gradient leakage
gradient inversion
graph neural networks
federated learning
graph convolutional networks
gnn
gcn
attack
privacy
reconstruction
Primary area: alignment, fairness, safety, privacy, and societal considerations
TL;DR: We present GRAIN, the first gradient leakage attack designed specifically for graph neural networks, and show we achieve a high fraction of exact reconstructions, and outperform existing attacks on partial reconstruction.

Abstract: Federated learning claims to enable collaborative model training among multiple clients with data privacy by transmitting gradient updates instead of the actual client data. However, recent studies have shown the client privacy is still at risk due to the, so called, gradient inversion attacks which can precisely reconstruct clients' text and image data from the shared gradient updates. While these attacks demonstrate severe privacy risks for certain domains and architectures, the vulnerability of other commonly-used data types, such as graph-structured data, remain under-explored. To bridge this gap, we present GRAIN, the first exact gradient inversion attack on graph data in the honest-but-curious setting that recovers both the structure of the graph and the associated node features. Concretely, we focus on Graph Convolutional Networks (GCN) and Graph Attention Networks (GAT) -- two of the most widely used frameworks for learning on graphs. Our method first utilizes the low-rank structure of GNN gradients to efficiently reconstruct and filter the client subgraphs which are then joined to complete the input graph. We evaluate our approach on molecular, citation, and social network datasets using our novel metric. 
We show that GRAIN reconstructs up to 80\% of all graphs exactly, significantly outperforming the baseline, which achieves up to 20\% correctly positioned nodes.

Published as a conference paper at ICLR 2025
GRAIN: EXACT GRAPH RECONSTRUCTION FROM GRADIENTS
Maria Drencheva', ', Ivo Petrov', Maximilian Baader Dimitar 1. Dimitrov! Martin Vechey1.2 INSAIT, Sofia University "St. Kliment Ohridski" (maria. drenchev,,, ivo.petrow dimitar. www.:iiweeeieiieaae. dimitrov) @insait. [mbaader, martin, vechev) www.:iin...h.......m
"ETH Zurich
ABSTRACT
Federated learning claims enable collaborative model training among multiple clients with data privacy by transmitting gradient updates instead of the actual client data. However, recent studies have shown the client privacy is still at risk due to the, so called, gradient inversion attacks which can precisely reconstruct clients' text and image data from the shared gradient updates. While these attacks demonstrate severe privacy risks for certain domains and architectures, the vulner- ability of other commonly- under-explored. To bridge this gap, we present GRAIN, the first exact gradient inversion attack on graph data in the canest-but-curioun setting that recovers both the structure of the graph and the associated node features. Concretely, we focus on Graph Convolutional Networks (GCN) and Graph Attention Networks (GAT) two of the most widely used frameworks for learning on graphs. Our method first utilizes the low-rank structure of GNN gradients to efficiently reconstruct and filter the client subgraphs which are then joined to complete the input graph. We evaluate our approach on molecular, citation, and social network datasets using our novel metric. We show that GRAIN reconstructs up to 80% of all graphs exactly, significantly outperforming the baseline, which achieves up to 20% cor- rectly positioned nodes.
data types, such as graph-structured data, remain
INTRODUCTION
Graph Neural Networks (GNNs) (Scarselli et al., 2009) have shown a great promise in learning on graph-structured data like social networks, traffic flows, molecules, as well as healthcare and income data. Many of these applications, however, require large quantities of private data, which can be hard to collect due to privacy regulations and the reluctance of users to share their data due to fear of losing competitive advantage. This has naturally led to widespread use of GCNs and GATs
alongside Federated Learning (FL) which promises to protect the sensitive data of users (Xie et al.
2021 Zhang et al. 202T Zhu et al. 2022 Lee et al. 2022 Lou et al. 2021 Peng et al. 2022).
However, the privacy of client data in FL in different domains including images (Zhang al., 2023).
text (Petrov et al., 2024)), and tabular data (Vero et al., (203) was recently severely violated by the introduction of gradient inversion attacks in the conest-but-curionn setting. In these attacks, the FL server infers the client data based on passively observed client gradients and the models where they were computed. However, prior work investigated the vulnerability of GNNs such attacks.
This work: Gradient inversion attack on graphs In this work, we introduce the first gradi- ent inversion attack graphs called Graph Reconstruction Algorithm for Inversion of Gradients (GRAIN), specifically designed to attack GNNs by recovering both the graph structure and the node features. At the core of GRAIN is efficient filtering mechanism correctly identify likely sub- graphs, which are then combined to reconstruct the entire graph. In particular, we leverage span checks exploit the rank-deficiency of GNN layer updates and recover both the discrete set of per- layer node features and the subgraph adjacency matrices. We then reconstruct the client input using a depth-first first search (DFS) algorithm to piece together the full graph from the recovered subgraphs.
We evaluate our attack on real-world chemical, citation and social network datasets, achieving re- construction accuracies of up to 75% (exact) and 85% (partial) on chemical graph elassification, 61% in citation graph classification, and 66% in molecular node classification tasks with known node labels. Finally, we demonstrate that data-dependent traversal strategies allow GRAIN to scale to significantly larger graphs, recovering 85% of graphs with around 25 nodes.

---

Published as a conference paper at ICLR 2025
Main Contributions Our main contributions are:
The first gradient inversion attack on Graph Neural Networks, recovering both the graph structure and the node features. We provide an efficient implementation on GitHub
A generalization of the theory presented by Petroy et al. (2024) facilitating an effective mechanism to recover individual feature vectors and thus enabling the use GNN layers to recover the graph connectivity via efficient filtering.
A novel set of metrics for measuring the quality of the recovered client graph structure and node features, enabling the evaluation of graph gradient inversion attacks at scale.
A thorough evaluation of GRAIN showing FL with GNNs does not preserve the client data privacy realistic applications, as GRAIN often recovers clients' graph data exactly.
We believe this work is an important step further quantify the risks of using private data in FL.
RELATED WORK
Gradient inversion attacks (Zhu et al. 2019). are attacks to Federated Learning that aim infer the client's ' private data from the FI. updates clients share with the federated server. As such, they assume knowledge of the updates themselves, as well as the model weights on which the updates were computed. Depending
the attack model, gradient inversion attacks are either malicious (Boenisch)
ct al.
2021 Fowl et al. 2022b|a a Chu et al.) 2023 Wen et al.
2022) if the attacker can additionally (Zhu et al. 2019 Phong
manipulate the model weights sent to the clients, or coonest-uut-urrion
eet al.
2018 Zhao et al., 2020 Geiping et al. 2020 |020| Geng et al.
2021 Zhang et al. 2023 Li et al,
2022
Deng al. 2021 Balunovic et al. 2002 Dimitrov et al.
2024 Petrov et al. [204]] Vero et al.
2023
if the attack is executed passively by just observing model weights and updates.
In this work, we focus on the harder setting of honest-but-curious gradient inversion attacks. Most existing bonest-but-curious attacks formulate gradient inversion as an optimization problem (Zhao al. 2020: Geiping al.] [2020) Yin al. [202]] Geng et al. [021 Zhang et al. 2023 Li al. Deng el al.] 2021: Balunovic et al.] [2022) where the attacker tries to obtain the data which corresponds to a client update that matches the observed one best. While this approach is effective
2022
in many domains like images (Geiping et al.) [020 Yin et al. 2021 Geng et al., 2021; Zhang et al.) Li al. 2022) where the client data is continuous, it has been shown that the associated opti- mization problem is much harder to solve for domains where client inputs are discrete. Some prior works have attempted to alleviate this issue by relying on various continuous relaxation (Balunovic)
2023
ct al. 2022
Vero et al. 2023) to the discrete optimization problem with some success.
In contrast to such approaches, recent research has demonstrated that exact gradient inversion is possible for both continuous (Dimitrov et al. (024) and discrete inputs (Petrov et al. (024) in certain neural architectures. Notably, DAGER (Petrov et al. 2024) showed that when dealing with a large but countable number of options for the client input data, the low-rank structure of gradient updates in fully connected layers can be leveraged to efficiently test all possibilities and identify the true input data. GRAIN extends this theory GNN layers, exploiting the discrete nature of the unknown the attacker adjacency matrix A to simultancously recover the client input features and graph structure, under the assumption of discrete input features. This addresses critical challenge in graph-specific gradient inversion, where the interdependence between the recovery of the client feature matrix X and the adjacency matrix A renders traditional optimization- based attacks ineffective. Unlike DAGER, however, the structure of GNNs only allows for the recovery of the local graph structure using this approach. To overcome this, we further introduce a DFS-basee algorithm that combines local graph structures into single graph, enabling the recovery of the full client input data.
3 BACKGROUND AND NOTATION
Threat Model GRAIN is honest-but-curion gradient inversion attack executed by malicious FL server that aims to recover the clients' private data. As such, the server is assumed to know the weight updates sent to clients and the corresponding responses received from them. Following
most existing gradient inversion attacks (Deng et al. 2021| Balunovic et al. 2022 Vero et al. 2023
https://gituub.com/iiii htw.://wom/taaiiiiiiiiiiutAuAAA institute/GRAIN

---

Published as a conference paper at ICLR 2025
Geiping et al. 2020), we also assume knowledge of the client data structure, including the semantic meaning, value ranges, and normalization of individual input features. This is well-justified as the server needs enforce consistency in input representations across clients to ensure correct training.
As GRAIN represents the first gradient inversion attack on GNNs, it targets the most traditional fed- erated protocol, FedSGD (McMahan et al.) 2017). and the most commonly used GNN architectures GCN and GAT. Further, as GRAIN is based on our extension to Thm. 3.1 introduced by Petrov et al. (2024), it makes two additional assumptions: (i) the number of nodes in the client graphs is smaller than the embedding dimension of the client GNN layers; and (ii) all input node features in the client graphs are discrete. We denote by m the total number of features, by F, the set of possible
values for the i-th feature, and by J Fi x F2 x .... x Fm the set of all possible feature vectors. As we show in Sec. 6 these assumptions cover many realistic use cases of GNNs.
Graph Terminology Next, we introduce our graph notations. By V we denote the set of possible graph nodes, where each node v E V is associated with given feature vector. For an undirected graph 9 (V, E) with node set V C V of size of a node E V with (v) Further, for pair of vertices Us, te E V. the distance dist(u,, ve) denotes the number of edges in the shortest path connecting v, Ue. We introduce the notion of a k-hop neighborhood of a node v, defined by the subgraph (x) = (V E C g consisting of all nodes V {v' E V dist(e, v²) I k} in the graph at distance S k from and the edges between them that can be traversed from v in S k steps E { = (V1, 02) E E 11 E V(Ng (u)), 22 E V²} with (g( = {v). Finally, we will call a triplet (V.* E. u) associated with the h-hop neighborhood around in G the building block G with center v.
|V] and edge set E,, we denote the degree
Graph Neural Networks Graph Neural Networks (GNNs) extend traditional neural networks to handle graph-structured data by leveraging the edges between nodes through message passing. Each GNN layer captures complex relationships between nodes by combining information from their neighbors and the graph's 's structural properties. This allows the model to learn richer node embed- dings and gain insights into the graph's 's topology. In particular, the 1h GNN layer takes as an input a matrix X E x of d-dimensional node features for each node V and performs a combination of messages passing and non-linearity to produce the node features of the next layer X
x o azz) = (A'Y') = (A''''""
where A' E Ruxx is a weighted adjacency matrix, W E Raxdd is the weight matrix, Y' E R is the output to the linear layer, and a is an activation function. For GCNs, the adjacency weights calculated using the respective node degrees, while for GATss they are determined by the attention mechanism. We denote the input features matrix with X and abuse the notation X to denote the row of X corresponding to the node v E V. We consider I.-layer GNNs, where we denote with ft the function that maps the input graph the output of the 1th layer for 1 0,1,2..... 1.
Gradient Filtering in Linear Layers Recently, DAGER (Petrov et al. 2024) showed that one ac can leverage the gradients of the network loss L w.r.t. the weights W of the 1dh linear layer aw to search for the correct set of inputs x' to the layer among a discrete set of possibilities via filtering enabled by the low-ranknes, of the weight updates. We restate the theoretical findings below: ac is of full rank, then rowspan X = colspan ac Ow? )
Theorem 3.1. !f n < d and if the matrix Tyr
To verify whether an input vector z can be a part of the client input, DAGER performs spancheck by measuring the distance between z and the subspace spanned by the column vectors of 8c
SWT
d(zz
ac = || proj(z, colspan SW
ac Ow?
We say z can be part of the 1-th layer input if d(z, SC < r for chosen threshold 7. In our aw
work, will extend Thm. 3.1 to Eq. in particular applying it to the linear layer Y x W
4 OVERVIEW OF GRAIN
Next, we provide a high-level overview of GRAIN, visualized in Fig. GRAIN a gradient inversion attack designed to reconstruct graph- graph-structured client training data FL assuming an honest-but- curious adversary and is based on the key observation that due to the architecture of GNNs, the
3

---

Published as a conference paper at ICLR 2025
C
.2C.
In5po
Exteed
LuSpa
Fi
fo
Lona
Glue T
haSpa
CCue CCur-loodd bourd
fiteciar
F3
32
Tp
cp
Subgraph Filtering
Graph Building
Client
OW2
Server
Figure 1: Overview of GRAIN. GRAIN first recovers the input nodes To by filtering through the cross-product To of all possible feature values, c.g., all atom types Fi and all number of bonds F2. It then iteratively combines and filters them into set of larger building blocks Tī up to degree L. Finally, it reconstructs the input graph by combining building blocks from Tg in DFS manner.
input embedding of node v at layer I can be influenced only by the original input embeddings of the nodes in the l-hop neighborhood of v. Therefore, given any I-hop neighborhood. we can obtain the corresponding embedding of its center u and use our spancheck, inspired by Thm. 3.II and shown in Thm. 5.1 to check whether the neighborhood is a possible subgraph of the input graph G not.
Filtering We leverage this subgraph checking procedure to create the filtering stage of GRAIN. In particular, we first generate the node proposal set To consisting of all nodes the can obtained using the known to the attacker sets of possible feature values F, We then apply the span checks layer-by- layer starting from To. At each layer I, we "glue" the (1 -hhp building blocks recovered from the previous filtering iteration into the set of possible I-hop neighbourhoods, denoted Ti in Fig. D which are then filtered using Thm. 5. to produce the set of consistent (-hop building blocks T," Finally, at layer L final consistency check is performed obtain the final set of L-hop building blocks TT-
Graph Building In the second stage, we perform graph building where we combine the L-hop building blocks Th using DFS-based approach to obtain the final graph reconstruction. To do this, at each node of the DFS tree, we "glue" building block at graph node that does not yet have enough neighbors to match their degree. Here, we use that the degree of a node is a widely used node feature for training GNNs (Hamilton et al.) 2017: Xu et al. 2018 8 thus known by the attacker at this stage. When we cannot extend the graph further, we compute its gradient and compare it to the client gradient. If they do not match, we backtrack and try different path. Otherwise, we terminate the DFS successfully and return the reconstructed graph.
Cui et al. 2022). and is
5 GRAIN: EXACT GRAPH RECONSTRUCTION FROM GRAIDENTS
We now present the technical details of GRAIN. First, in Scc. we we explain the key operation of graph gluing. Then, in Sec. 5.2 we present Thm. 5.T that adapts Thm. 3.1
Algorithm 1 The GRAIN algorithm
1: function GRAIN(To. aw. T, f.f.C)
ac
2:
To -GENERATEBBSCTT ow: T, f)
ac
to GNN layers and Thm. 5.33 that enables
3:
TB --STRUCCTREFFLLEERTTT OW
GRAIN to locally recover graph structures. These theoretical developments allow for the efficient removal of proposal elements from Tr, which fail the span check and hence cannot sub- detail in Sec. [.3 Finally, in Sec. [5.4 we demonstrate our graph building,
4: return RECONSTRUCTGRAPPITT B. aw C)
ac
graph of the input, which recovers the entire graph from the filtered set of possible subgraphs T using DFS.
5.1 GRAPH GLUING
In this section we describe the process of gluing a l-hop building block = (VB F.B cB) to a graph G (V, F) at vertex e E V. The resulting set of graphs G contains all possible ways of attaching the non-overlapping parts of B to & at c, as shown in Fig [ To this end, we combine the graphs by correctly matching equivalent nodes between them based their features. In particular,

---

Published as a conference paper at ICLR 2025
Sysladic Grapla
Makondar Cogale
Ciaiko Nevado
10
0.-
0.00
0.5
0.55
rash: Hhai (OCN)
014
0.00
wank MIS (U00))
0.1
PAA
(x1
13
14l
75
103
Graph
(a) GCN vs GAT recon- structability (on Citeseer)
(b) Impact of low-rankness of the adjacency matrix on reconstructability for GCNs for synthetic data (left), molecules (middle), and citation networks (right)
Figure 3: Ablation studies on how the data and architecture affect reconstructability
we return the empty set if the center of the building block v' and the chosen node e from the graph have different features. The same holds if the (-hop neighborhood of the chosen node does not match a subgraph of the building block. In all other cases we return the set of all possible graphs resulting from the gluing G gl B3 v). We describe how to efficiently perform gluing in App. A.3
5.2 THEORETICAL FOUNDATIONS THE SPANCHECK FILTERING
g
B
gl
Span check for GNN layers We now state our main result extending Thm. 3.1 GNN layers. The proof is in App. A.2 Theorem 5.1. If n < d, X E colspan( ac aw:) if and only if ac rowspan( 0C ), where öc denotes the matrix OY? with its i-th row removed.
OC TY1
OY!
OY!
Center of
Figure 2: Glueing visualization
This important generalization of the theory presented in DAGER provides an exact condition for BC
Bc recovering individual input vectors X under any output gradient aY.. In particular, when öYT full-rank, the theorem recovers the statement of Thm. 3.1 Otherwise, intuitively, the theorem states that we lose recoverability for inputs X for which the corresponding row in SYT dependent of the rest of the rows in ac ayr- The empricial experiments, illustrated in Fig. 3a showcase Ac is almost certainly full-rank for GAT', enabling the span check to accurately filter the entire that oy: input, making Thm. 3.1 still applicable most of the time. However, in general zy? can exhibit low- rankness, which limits the recovery of the entire input. In particular, Fig. 33 shows that for GCNs for small graphs the full-rankness assumption is violated. To this end. we present the following corollary (proven in App.(A.2) which outlines the implications of Thm. [..gs..fiiiiicilllll for GCNs: ac Corollary 5.2. For "2" of full-rank, n < d, if the (possibly normalized) adjacency matrix at layer
&c is linearly
ac
1, A Baxn, X! E colspan( (WT) if and only if A? & colspan( (A:). Further, if A is full-rank, then X! E colspan owT) for all = 1, ...
ac
i.c. when A is full-rank, all feature vectors at layer are recoverable via the spancheck. If this isn't ' the case, according to the main theorem we still recover most, but not all. In Fig. 3b and App. C.3 we demonstrate that even when A is significantly rank-deficient, the majority of X can still be recovered under the GCN setting. Our experiments on real-world datasets show that even in these cases GRAIN is able to partially recover the graph. Next we explain how we propagate our proposed building blocks through the GNN layers in order to be able to apply Thm. 5.1 to filter them.
order to be able to apply Thm. 5.1 to filter a generated (-hop building block at the 1-th layer we need to reconstruct its corresponding input embedding vector X) to the 1-th layer. We now state our key result allowing us to recover this input vector.
Building block propagation
Theorem 5.3. For GNNs satisfying Asm, A.1 propagating a correctly reconstructed building block G. centred at v through the first 1 GNN layers recovers the original embedding of v at layer I:
fr-1( = =X!
where i is the index of v in the adjacency matrix of the original input graph G and j is the index of e in the adjacency matrix of g..
Intuitively, this shows that a correctly recovered I-hop neighborhood is sufficient to compute the embeddings of e at layer enabling the span check filter at this layer. The proof is available in App. A.2 alongside a proof that GCNs and GATs satisfy Asm. A.I
5

---

Published as a conference paper at ICLR 2025
5.3 SUBGRAPH FILTERING
Next, we begin our attack with the creation of the L--hop building blocks and reduce the search space via the span check mechanism. Even though GRAIN applicable to any type of discrete features, we describe our methodology for one-hot encoded ones for notational convenience.
Recovering the single node feature vectors in To We now describe how to recover the single node client feature vectors, that is the O-hop neighborhoods in To' We note that the direct enumera- tion approach by DAGER is often infeasible for graph data. To this end, instead of performing span checks on the entire input vectors, we do partial span checks on partial vectors, iteratively adding di- mensions in order to control the complexity. Specifically, we first take the dimensions corresponding to subset of features and filter those. To further constrain the search space, we then keep adding di- mensions corresponding other features, followed by another filtering. We note the soundness of this partial filtering is covered by Thm. as performing the spancheck on subspace is less restrictive compared to the full span check. Pseudocode and further explanations are provided App. A.4
Creating I-hop building blocks T We first define the extension ext(v) of a node to be the set of all 1 1-hop building blocks that can be constructed by at- taching exactly deg(v) nodes from To' to v. We note that we do not attach nodes w E To to e if the feature
Algorithm 2 Filtering using the spancheck ac aw:. T, fi-1)
1:
function FILTER
2:
T < 0
3:
for G in Ti do
degree of w is 0, that is deg(w) w) 0. The set of all possible I-hop building blocks Ti = UNET: ext(v) is
4:
V +- center(g)
5:
if d(f- aw! < r then
then defined as the set of all possible 1-hop neighbor- hoods that can be constructed by extending node from To. Thm. 5.3 then allows us exactly recover the first layer embedding for the center of each neighborhood. We are hence able to filter Ti by applying SWT to achieve the reduced set of 1-hop building blocks Ti", as shown in Alg. 2
6:
T +- Ti' U (9)
7: return TE
Thm. 5.1
02
Creating L-hop building blocks T For a building block B E T we de- fine the dangling nodes dBng((3) as the set of all nodes v E such that deg(v) (the ground-truth degree of the node) is greater than the number of its neighbors. We extend the (-hop building blocks B E Ti" by calculating all possible gluings of 1-hop building blocks E' T to all dangling nodes of B. This is shown in lines T6 of Alg- [ The resulting set is then called Ti+1, which is then fil- ac
Algorithm 3 Creating the degree-L building blocks
1: function GENERATEBBS (( Fih ac JW: T, f)
2:
To FILTERNODES ow. 7)
BC
T f
4:
for in To' do
5:
Ti 4 Ti Uext(u, To
6:
T FFLLERR OW, fo)
dc
7:
for / 1,...... L 1 do
Ti+1 + 0
9:
for G in T," do
10:
St (G)
tered by applying Thm. 5.1 on awl+: to achieve the reduced set of 1-hop build-
11:
for in dang(G) do
12:
S' + 0
ing blocks T- We repeat the process 13:
for G' G in do
explained above until reach the de-
14:
S' S'SSUGLLLEG ga, u,,uu, v,,)
sired L-hop neighborhoods, with the fi-
15:
S
nal spancheck performed on the first lin-
16:
T+ TH
ear layer of the commonly used readout classification head.
17:
OC T + FILTER((H+1, oW T, f(-1)
18:
return Ti
Additional structure-based filtering
To further restrict the proposal set of building blocks, we perform a consistency check to rule out blocks that cannot be part of the ground truth graph. Specifically, for every building block B E T and for every dangling node in it u E dang(B) we assert that there exists a building block in T that we can glue it at e to B. If this is not the case, we know that either B is the input graph (which
we check by computing the gradients produced by B), or it cannot be part of the ground truth graph and remove it from T7. We denote the resulting set T

---

Published as a conference paper at ICLR 2025
5.4 GRAPH BUILDING
Algorithm 4 DES reconstruction
Finally, we describe how we leverage depth-first search to combine the filtered set of building blocks TB into our final graph reconstruction.
1:
function DODFS
B Bw Jeurss C) if [dang ( = 0 then
dc
2:
3:
return a Geurr
4:
Specifically, each node of our DFS exploration tree
5:
GrOp; dToP + 0. 00
represents a partially reconstructed client graph Gaur. and at each branch we choose an arbitrary dangling
6: Bard t- Order(TB)
7:
v f- Sample( E dangg(Gau))) Gnew Branch ( Gaurs v)
node E Geur (Line[7jin Alg. [4 and generate all pos-
8:
sible graphs G = (guur B, v) that can be created
9:
for G in Gaow do d' G' DODFSDDF 5W ...9,C 9.C) if d' == 0 then return 0,g'
by gluing building block B TB
(Line 8 in
10:
8C
Alg. J. This is done by iterating over all the building 11:
blocks in Tg. checking for each one if it is possible
12:
to glue it to Geurr and if so, saving the extended graph
13:
else if drop > d' then dTOP, STOP + d',g'
as new branch. The pseudocode for the branching is provided in App. A During branching, we also take
14:
15: return dTOP, STOP
care of recovering possible cycles within the recon-
structions by overlapping nodes in Geur that might coincide. This is also elaborated on in App. A.6 If Geurr has no more dangling nodes, we calculate the distance between its and the client gradients:
Ag min cEC
||
@C(G.e) oW
0C SW
||F,
where C is the set of all possible labels and ||p is the standard Frobenius norm. If Ag.... the algorithm terminates early with correct graph (Line 12 in Alg. Otherwise, we return the best
possible reconstruction in gradient distance (Lines 9 14 in Alg.
Building block ordering A key factor in the performance of the algorithm the order in which visit nodes of the exploration tree. We use heuristic ordering based on score S(B) we define for every building block B E Tğ. We first define the score (B) to be equal to the lowest span ac check distance d(G, awt) of a building block B that can be glued to & at v. The score for the entire block is then calculated as the sum of the vertex scores S(B) = Σ. S.()). Intuitively, this score represents how compatible any building block from Tg is with the other building blocks that passed the spanchecks. Again, intuitively, the building blocks which are part of the input will be more compatible with the other building blocks from the input than potential false positives.
Uniqueness heuristic In some settings, such as social or citation networks we notice that the feature vectors of different nodes are almost surely unique. In these settings, we leverage heuristic which during reconstruction always overlaps any two nodes with the same features. Further, in these settings we never try glue the same building block twice, as L-hop neighborhoods are analogically unique. The heuristic drastically reduces the search space and the time for convergence of GRAIN.
6 EVALUATION
In this section we evaluate GRAIN's performance against prior gradient leakage methods.
We begin by detailing our experimental setup and the baseline attacks considered, along with intro- ducing a novel set of metrics, specifically designed to jointly assess the differences in node features and graph topology between the true client graphs and their reconstructions. The experimental results demonstrate GRAIN's substantial improvements over existing attacks, achieving superior re- construction accuracy and versatility. Namely, we demonstrate that GRAIN remains effective across a wide range of architectural changes, GNN model types, data modalities, and task scenarios.
6.1 EVALUATION METRIC
We found it necessary to design our own set of metrics, as prior graph-related similarity measure- ments were not suitable for evaluating gradient inversion attacks. A discussion on the desired quali- ties of the metrics, and the reasoning behind their design can be found in App. B
To this end, we introduce the Gruph Similarity Metries (GSM) a set of metrics designed to evaluate the similarity of pair of graphs G and & under the name GSM-N, the details of which we showcase
7

---

Published as a conference paper at ICLR 2025
in App. B A key highlight of GSM is that it assesses structures of varying globality, while ensuring the metric is invariant to graph isomorphism through rigorous node matching.
We utilise 3 separate instances of the metric namely for N 0, 2, where larger-hop neighbor- hoods are used to capture more structural information. It is important to note that all measurements
(ax((V are scaled by a factor of minIVV) to penalize reconstructions of incorrect size. We further report
the percentage of exactly reconstructed graphs, denoted by FULL in the result tables.
To measure the perceived reconstruction quality and compare it to our GSM set of metrics, as well as confirm that our metrics are fair with respect to the baseline attacks, we further conducted a human evaluation study. In Tab. [T we show that our metrics are highly correlated with human perception. Further details about how this study was conducted shown in App. C
Table 1: Comparison of GSM and human evaluation.
6.2 EXPERIMENTAL SETUP
GSM-0
GSM-1
GSM-2
Human
Next, we describe our experimental setup, including the architecture of the attacked models, the client datasets used, and the hardware required by the attacker.
GRAIN
72.6
67.8
66.9
70.6
DLG
24.2
10.5
12.0
6.5
Architecture details Unless otherwise specified, all of our attacks are applied on 2-layer GNNs (L = 2) with hidden embedding dimension d' = 300 and ReLU activation. For GAT experiments 2-headed attention was used (adapting GRAIN to GATs with more heads is analogous). All networks also feature a 2-layer feedforward network for performing the readout Kipf & Welling (016)) Given the depth restrictions, we recover building blocks up to layer 2, with the first readout layer being used for the relevant filtering of the largest blocks. In Tab. 10 that our attack is robust with respect to changes in these architectural parameters.
common depth for GNNs
we show
Evaluation datasets We evaluate on three different types of graph data chemical data, citation and social networks. For the chemical experiments, we evaluate on molecule property prediction data, where molecules are represented common convention to omit hydrogen atoms in the graphs. Each node is embedded by concatenating the one-hot encodings of 8 features (Xu et al.) 2018 Wu et al. 22020), namely the atom type, formal charge. number of bonds, chirality, number of bonded hydrogen atoms, atomic mass, aromaticity and hybridization (Rong al. 2020). We evaluate GRAIN on 3 well-known chemical datasets Tox21, Clintox, and BBBP, introduced by the MoleculeNet benchmark (Wu et al., 2018).
graphs and each node is a given atom. We follow the
For the citation networks experiments, we apply GRAIN the CiteSeerGGiles et al. 1998) dataset, which features single graph with 3312 nodes representing scientific publications classified into one of six classes. The edges between them represent citations, and the features of any node is 0/1-valued word vector of length 3703 indicating the absence/presence of a keyword in the abstract.
Finally, for the social network experiments we use the Pokee(Rossi & Ahmed 2015) dataset, con- taining 1.6 million nodes (users), where connections represent friendship between users. We chose discrete node features where every feature with frequency less that 1% was categorized "Other", as these entries usually contain irrelevant outliers. This resulted in 36 total discrete features.
To simulate federated learning environment, in the latter two settings we sample subgraphs of given size from the datasets for each of the FL clients and use cluster classification objective, where each subgraph is classified as the most common class among the comprising nodes. We chose the sampling distribution: 20 graphs with 1-10 nodes, 40 graphs with 10-20 nodes, 30 graphs with 20-30 nodes, and 10 graphs with 30-40 nodes, closely mirroring the distribution of the Tox21 dataset.
Computational requirements We provide an efficient GPU imlementation. where each experi- ment has been run on NVIDIA 1.4 Tensor Core GPU with less than 40GB of CPU memory.
6.3 BASELINE ATTACKS
We adapt the DLG attack (Zhu et al. 2019), a standard continuous attack, and Tabl leak, an attack purposefully designed for recovering discrete tabular data. As described in (Vero et al.) 2023), all input features are first passed through an initial sigmoid layer to ensure they are in the interval (0,
8

---

Published as a conference paper at ICLR 2025
Table 2: Results (in %) of experiments on the 3 dataset types Tox21 (chemical), CiteSeer (citation), Pokec (social), Here "+A" refers the baseline attack with the input adjacency matrix given.
GCN
GAT
GSM-0
GSM-1
GSM-2
FULL
Time
GSM-0
GSM-1
GSM-2
FULL
Time
GRAIN
66.9123
83.9-63
82:611
68.0
1.7
14.3
92.9223
90.7.71
89.9172
76.0 1.8
10.8
DLG
31.811
20.3
22.8 k
9.5
6.5"1
20.03
Tox21
DLG +
51.7553
60.1
76.7
10:022
3.1
96.5 0.34
09.7153
20:
4.5
TabL.ak
25.1
108
002
T3.7
7.2
10.0
10:022
TabLzak +.4
35.6
57.7
73.8
102
12.3
75.1
719
S12115
10:02
GRAIN
62.5
$1005 KU
31.6
20.0
0.8
2.5
79.3
69.1
09.6
61.0 1.16
2.1
DLG
65.7117
0.0
00
0.0
0.0::00
Cieeeer
DLG +
65.7
0.0
0.0.00
0.0 1.0
26.8
65.7
0.0
0.0
0.0 1.0000
28.2
65.2"1
0.3:84
172.7
06.0
0othe
177.4
Tabl.aak 4.4
65.31.7
0.0
0.0
0.0
172.9
66.1 66.1
0.0
0.0"h
0.0 + 0.0
171.5
GRAIN
58.3150
S0.7
35.8153
15.0 0.8
0.3
07.2 1
03.5143
96.313
78.0 1.8
DLG
38.1"12
0.0
7.9
0.0
0.6
36.8
000h0
0.1:8
1.0
Pokes
DLG +-4
37.4"1
0.2
26.375
0.0 000
0.5
37.7
0.1
16.9"11
0.0 0.0
1.0
37.1"13
29 15
0,0
1111T
Tabl.zak +.4
37.9113
0.5
20.1
0.0 00
5.7
37.7
0.3
23.411
0.0 0.0
11.4
Original
GRAIN
DLG
Tableak
HH
H,G
HH
Figure 4: Examples molecule reconstructions. Multivalent interactions are not recovered, they are not considered by the GNN.
1). Similarly, we ensure the adjacency matrix A is symmetric by optimizing over the upper triangle, and apply softmax operation over the dummy labels to convert them to probabilities. Finally, we generate a prediction graph by connecting all nodes U, fy corresponding to o (A)); 2 0.5. Additionally, we test both baselines when they are given the correct adjacency matrix A. In all cases provide the attack with the correct number of nodes to ensure that X and A have the correct shape. We demonstrate that, even when the baselines have a significant amount of prior knowledge, GRAIN significantly outperforms them (see Fig. and Tab.
6.4 EXPERIMENTAL RESULTS
Next, we evaluate the baselines and GRAIN and show that GRAIN outperforms the existing base- lines across all defined metrics. Further, GRAIN is applicable across variety of datasets and settings, including being depth- and width-agnostic, and far more scalable and robust. all mea- surements we quote the mean value of the metric, as well as the 95% confidence interval around it, measured by generating 10,000 random sample sets via bootstrapping.
Main experiments We first apply the algorithms DLG, TabLeak and GRAIN to the 3 types of dataset on both the GCN and GAT architectures. We observe in Tab. that GRAIN achieves a much higher partial reconstruction rate (up to 96%) compared to any baseline. This remains true when the baseline is informed about the input adjacency matrix A. Without A, baseline performance notably drops with neighborhood size, showing the baselines" inability recover the structure. Beyond partial reconstruction, GRAIN is further able to recover up to 80% of the dataset exactly, while the baselines achieve this only in the case of very small graphs. Further, GRAIN closely matches TabLeak's 's runtime and is much faster than all baselines with the node unigueness heuristic. For visual inspection, we also include a comparison of fully reconstructed molecule in Fig. with further examples in App.
As shown, GRAIN can also be effectively applied to both architectures, consistently achieving higher score the GAT architecture. This increase happens because we showed in Fig. 3a ØYr almost certainly full-rank, where Cor. 5.2 enables the direct recovery of all inputs.
dc
For the Tox21 baseline experiments we used a LBFGS optimizer for more stable and higher quality results. However, for CiteSeer and Pokec, where the client input space much larger, we instead ran SGD due to time constraints. In App. C.3 we show results with LBFGS on 10 times fewer samples.

---

Published as a conference paper at ICLR 2025
Table 3: Comparison of GRAIN and baselines on chemical datasets for GCNs on graphs of size n.
n S 15
16 S R 25
26 S
GSM-D
GSM-2
FULL
GSM-0
GSM-2
FULL
GSM-O
GSM-2
FULL
GRAIN
93.0254
91.6
81.9 1.7
81.7113
748183
3 16.
13.6 1.1
50.127:
39,2177
5.1 + 0.6
DL.G
27.451
13.3-16
1.2
25.5243
0.2
25.4213
118811
0.0 0.0
DLG +-A
52.1533
71.8534
1.2
58.7245
75.4237
0.9 0.2
53.0112
72.6114
0.0 1 0.0
TabLeak
30.3213
15.4725
1.9 1.910.3
15.7122
2.1211
0.0 0.0
13.0153
2.811
0.0 1 0.0
TabLeak +.4
53.9
72.9
1.9
0.3
57.12915
71.4556
0.0
56.1
74.4
0.0 1.0.100 0.0
Table 4:
Reconstruction results in % for GRAIN Table 5: Reconstruction results in % for GRAIN on Tox21 for GCNs in various settings
on Citeseer and GAT's for different ablations.
GSM.0
GSM
GSM-2
FULL
GSM-0
GSM-1
GSM-2
FULL
Default
86,911
83.9223
82.629]
68.0 1 1.7
Default
degree
79.3
59.7173
69.1
42.7
69.6
69.6
43.2
61.0 1 1.6
32.0
a GELU
Pre-trained
82.0
73.5
57
70.0
79.1
68.6
78.4
61.0 1 1.6
49.0 1.4
No heuristic 64.6
52.1
14.
52.4 5.2
1466
44.0 + 1.3
Node Class.
88.0 5.4
85.5
81.9288 6.8
66.0
Effect of graph size on reconstruction In Tab. and Tab. 12 we show how GRAIN performs
on graphs of different sizes under the same setting respectively). In the chemical setting (Tab. (3] molecules are divided into groups of n x 15, 16 < 26 nodes, aggregated across the 3 chemical datasets. We notice that GRAIN significantly outperforms the baselines for smaller graphs, but the performance decreases on the largest groups in both the chemical and the social networks setting due to timeouts (15 minutes) during graph building. That said, the social network setting (Tab. (2]. allows us to apply the node uniqueness heuristic, allowing us to scale to much larger graphs of size up to n = 60 nodes. Further, our work still manages to reconstruct a fraction of the large graphs exactly, which is impossible for the baseline models, even the more difficult chemical setting (discussed in App. D
main experiments (for GCNs and GATs
25 or
Ablation studies We analyze the impact of our design choices and heuristics GRAIN in Tab. 4
Removing the node in-degree from the feature set and enumerating all possibilities during filtering still enabled exact recovery of 30% of graphs but caused substantial degradation. A similar, though less severe, drop occurs without the node uniqueness heuristic (Sec. (544). highlighting the key role of data-specific heuristics in strengthening the attack. We also show that GRAIN's stability is unaf- fected by architecture parameters and thresholds. As demonstrated in App. C.3) network width and depth have minimal impact, provided the embedding dimension exceeds the number of graph nodes (d >> n). Additionally, the threshold remains robust, with values between 10 40 and 10 yielding nearly identical filtering performance.
Additional experiments We provide additional experiments showcasing GRAIN's performance in different miscellaneous settings in Tab. [5] First, we replace the ReLU activation function in the GCN by a GELU and report that GRAIN achieves similar results, showing our flexibility with respect to different activations. Furthermore, while prior work has shown that gradient inversion becomes significantly more diffieult on pre-trained models (Geiping al. 2020). GRAIN still man- ages to reconstruct around 50% of molecules exactly. Finally, we achieve consistently strong results in the node classification task, assuming ground-truth labels are known, which can be easily recov- ered using methods like Zhao et al. 2020
7 CONCLUSION
We introduced GRAIN, the first gradient inversion attack for Graph Neural Networks capable of accurately recovering graphs from shared gradients. By leveraging the rank-deficiency of the GNN layers, we developed an efficient framework for extracting and filtering subgraphs of the input graph, which are iteratively combined to reconstruct the original graph.
Our results showed GRAIN achieves an exact reconstruction rate of up to 80% for graph classifi- cation. We introduced new metries to evaluate partial graph reconstructions and demonstrated that GRAIN significantly outperforms prior work. Moreover, GRAIN maintains high reconstruction quality across different architectures, parameters, and settings, and can scale to much larger graphs.
In summary, our paper is the first to demonstrate that GNN training in federated learning setting poses data privacy risks. We believe that this is a promising initial step towards identifying these vulnerabilities and developing effective defense mechanisms.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENTS
INSAIT, Sofia University "St. Kliment Ohridski". Partially funded by the Ministry of Education and Science of Bulgaria's s support for INSAIT as part of the Bulgarian National Roadmap for Research Infrastructure.
This project was supported with computational resources provided by Google Cloud Platform (GCP).
This work has been done as part of the EU grant ELSA (European Lighthouse on Secure and Safe AI, grant agreement no. 101070617). Views and opinions expressed are however those of the authors only and do not necessarily reflect those of the European Union or European Commission. Neither the European Union nor the European Commission can be held responsible for them.
The work has received funding from the Swiss State Secretariat for Education, Research and Innova- tion (SERI).
REFERENCES
László Babai. Graph isomorphism in quasipolynomial time. In Proceedings of the forty-eighth annual ACM symposium Theory of Computing, pp. 684-697, 2016.
Mislav Balunovic, Dimitar Dimitrov, Nikola Jovanović, and Martin Vechev. Lamp: Extracting text from gradients with language model priors. Advances Neural Information Processing Systems, 35:7641-7654, 2022.
Franziska Boenisch, Adam Dziedzic, Roei Schuster, Ali Shahin Shamsabadi, Ilia Shumailov, and Nicolas Papernot. When the curious abandon honesty: Federated learning is not private. arXiv, 2021.
Hong-Min Chu, Jonas Geiping, Liam H Fowl, Micah Goldblum, and Tom Goldstein. Panning for gold in federated learning: Targeted extraction under arbitrarily large-scale aggregation. ICLR, 2023.
Hejie Cui, Zijie Lu, Pan Li, and Carl Yang. On positional and structural node features for graph neu- ral networks on non-attributed graphs. In Proceedings of the 31 ACM International Conference on Information & Knowledge Management, pp. 3898 39088,99022220 2022.
Jieren Deng. Yijue Wang, Li, Chao Shang. Hang Liu, Sanguthevar Rajasekaran, and Caiwen Ding. Tag: Gradient attack on transformer-based language models. arXiv preprint arXiv:2103.0688 066899 2021.
Dimitar Dimitrov, Maximilian Baader, Mark Niklas Müller, and Martin Vechev. Spear: Exact gradient inversion of batches in federated learning. arXiv preprint arXiv:2403.03945, 2024.
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. ICLR, 2022a.
Liam H. Fowl, Jonas Geiping, Wojeiech Czaja, Micah Goldblum, and Tom Goldstein. Robbing the fed: Directly obtaining private data in federated learning with modified models. In ICLR, 2022b.
András Frank. On kuhn's 's hungarian method a tribute from hungary. Naval Research Logistics (NRL), 52(1):2-5, 2005.
Jonas Geiping, Hartmut Bauermeister, Hannah Dröge, and Michael Moeller. Inverting gradients- how easy to break privacy in federated learning? Advances in neural information processing systems, 33:16937-16947 2020.
Jiahui Geng, Yongli Mou, Feifei Li, Qing Li. Oya Beyan, Stefan Decker, and Chunming Rong. Towards general deep leakage in federated learning. arXiv, 2021.
C. Lee Giles, Kurt D. Bollacker, and Steve Lawrence.
Citeseer: an automatic citation indexing system. In Proceedings of the Third ACM Conference on Digital Libraries, DI. '98, pp. 89-98, New York, NY, USA, 1998. Association for Computing Machinery. ISBN 0897919653. doi: 10.1145/276655227666

---

Published as a conference paper at ICLR 2025
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. Advances in neural information processing systems, 30, 2017.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. arXiv preprint arXiv: (109:06600009900000 2016.
Harlin Lee, Andrea L Bertozzi, Jelena Kovačević, and Yuejie Chi. Privacy-preserving federated multi-task linear regression: A one-shot linear mixing approach inspired by graph regularization. In ICASSP 2022-2022 IEEE International Conference on Acousties, Speech and Signal Process- ing (ICASSP), pp. 5947-5951. IEEE, 2022.
Zhuohang Li, Jiaxin Zhang, Luyang Liu, and Jian Liu. Auditing privacy defenses in federated learn- ing via generative gradient leakage. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 20132-10142, 2022.
Chin-Yew Lin. Rouge: A package for automatic evaluation of summaries. In Text summarization branches out, pp. 74-81, 2004.
Guannan Lou, Yuze Liu, Tichua Zhang, and Xi Zheng. Stfl: A temporal-spatial federated learning framework for graph neural networks. arXiv preprint arXiv:2111.06750 2021.
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Communication-efficcee learning of deep networks from decentralized data. In Artificial intelli- gence and statistics, pp. 1273-1282. PMLR, 2017.
Liang Peng, Nan Wang, Nicha Dvorek, Xiaofeng Zhu, and Xiaoxiao Li. Fedni: Federated graph learning with network inpainting for population-base based disease prediction. IEEE Transactions on Medical Imaging, 42(7):2032-22) 2023,003, 2022.
Ivo Petrov, Dimitar I. Dimitrov, Maximilian Baader, Mark Niklas Müller, and Martin T. Vechev. DAGER: exact gradient inversion for large language models. CoRR, abs/2405, 15586, 2024. doi: 1044855/ARXXVV24005.5555 155866 URL https://doi. org/10. 15586
2405.
Le Tricu Phong, Yoshinori Aono, Takuya Hayashi, Lihua Wang, and Shiho Moriai. Privacy- preserving deep learning via additively homomorphic encryption. IEEE Trans. Inf. Forensics Secur., (5), 2018.
Yu Rong, Yatao Bian, Tingyang Xu, Weiyang Xie, Ying Wei, Wenbing Huang. and Junzhou Huang. Self-supervised graph transformer on large-scale molecular data. Advances in neural information processing systems, 33: 12559-12571, 2020.
Ryan Rossi and Nesreen K. Ahmed. The network data repository with interactive graph analytics and visualization. In AAAI, 2015. httphtttpes//etttorrrrpoooss
com
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEÉE Transactions on Neural Networks, 20(1):61-80, 2009. doi:
2005665.
Mark Vero, Mislav Balunović, Dimitar Iliev Dimitrov, and Martin Vechev. Tableak: Tabular data leakage in federated learning. In Proceedings of the 40th International Conference on Machine Learning, volume 202, pp. 35051-35083 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. ICMI., 2022.
Zhenqin WU, Bharath Ramsundar, Evan N Feinberg, Joseph Gomes, Caleb Geniesse, Aneesh Pappu, Karl Leswing, and Vijay Pande. Moleculenet: benchmark for molecular machine learn- ing. Chemical science, 9(2):513-530 2018.
Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and Yu Philip. A comprehensive survey graph neural networks. 1EEE transactions neural networks and learning systems, 32(1):4-24, 2020.
Han Xie, Jing Ma, Li Xiong, and Carl Yang. Federated graph classification over non-iid graphs. Advances in neural information processing systems, 34: 14:18889-18852, 2021.
12

---

Published as a conference paper at ICLR 2025
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanic Jegelka. How powerful graph neural networks? arXiv preprint arXi::1810.00826, 2018.
Hongxu Yin, Arun Mallya, Arash Vahdat, Jose M. Alvarez, Jan Kautz, and Pavlo Molchanov. See through gradients: Image batch recovery via gradinversion. In CVPR, 2021.
Chenhan Zhang, Shuyu Zhang. JQ James, and Shui Yu. Fastgnn: A topological information pro- tected federated learning approach for traffic speed forecasting. IEEE Transactions Industrial Informatics, 17(12)88464 8474, 2021.
Chi Zhang, Zhang Xiaoman, Ekanut Sotthiwat, Yanyu Xu, Ping Liu, Liangli Zhen, and Yong Liu. Generative gradient inversion via over over-varamann parameterized networks in federated learning. Proceed- ings of the IEEE/CVF International Conference on Computer Vision, pp. 5126 5126-5135, 2023.
Bo Zhao, Konda Reddy Mopuri, and Hakan Bilen. idlg: Improved deep leakage from gradients. arXiv preprint urXiv:2001.0244 100610, 2020.
Ligeng Zhu, Zhijian Liu, and Song Han. Deep leakage from gradients. Advances in neural infor- mation processing systems, 32, 2019.
Wei Zhu, Jiebo Luo, and Andrew D White. Federated learning of molecular properties with graph neural networks in a heterogeneous setting. Patterns, 3(6), 2022.
13

---

Published as a conference paper at ICLR 2025
A
ADDITIONAL TECHNICAL DETAILS
A.1 TABLE OF NOTATIONS
For convenience, we add a table of notations containing brief definitons for all symbols used in our
work.
Table 6: Table of notations used in the technical description of GRAIN.
Symbol
Definition
Symbol
Definition
G (V, B)
Graph with nodes V and edges n Possibly weighted adjacency ma- trix at layer I
# nodes in the graph
A'
dist(va, vo)
# edges shortest path connecting nodes Pay Ve E V
(e)
k-hop neighhorhood in graph with center node v
C
Loss
degg(e)
Degree of node in graph
deg(v)
Degree of node given by its feature
X²
Input the ith GNN layer Weights of the i-th layer Number of GNN layers
x
i-th layer input feature of node Hidden dimension size Number of features Span check distance threshold
W
d'
L
m
fi
Function mapping the input graph to the output of the i-th layer
Fi x ... Fn set of all possible feature combinations
F.
Set of values for the i-th feature
T
Proposal set I-hop building blocks
T
Filtered set I-hop building blocks
TB
Final set filtered building blocks
Activation function
Ag
Distance between the gradients and observed gradients
dhest
Gradient distance of the re- constructed graph
GSM-NGG,
Similarity between N-hop neigh-
Gusst
The best reconstructed graph.
borhoods of G and
A.2
DEFERRED PROOFS
A.2.1 SPAN CHECK PROOF
Here show the proof Thm. 5.1 which restate here for convenience:
Theorem 5.1. If d, X E colspan( (ffr) if and only if OY. of rowspan dc { ac denotes the matrix BYT with its i-th row removed.
where dc OY!
Proof. For notational clarity, omit the layer index in our proof. We separate the proof in steps:
0c Step I: x?" E colspan( ac if and only if there is vector a, such that ow 6; is the i-th standard basis vector.
BY a; es where
Step 2:
0c There is a vector a, such that BY
if and only if null(
Øc 0Y
mull( ac E
Step 3: null(
8C TY
null( #c 0Y
#C is equivalent to bY. & rowspan
dc
Step 1 (XF E colspan(
8C OW
3ay By
ac a, e;):
(+) First, we begin by expressing (2024):
ac BW
using the following common result from Petrov et al.
8C DW
X
ac 0Y

---

implies that there exists an af E null( such Published as a conference paper at ICLR 2025
implying that X E colspan X ac = rowspan T OY X). This can be rewritten as T X X Assuming X Randd is full-rank, then there exists a right-inverse 30 BY
X R as rank X = n < d.
T ac T Xx 0 BY
X x
T 00 T aj BY =
ac BY
Ci
It is notable that X not being full-rank still allows for all nodes with feature vectors in X to pass the span check, however is possible that some hallucinated inputs might also pass the check.
(+)
0Y 0: Cj
T OC T
a E
T dc X X!
a
Thus X?" E roosspan OC colspan( ).)) ).
BY X) colspan
(X X 06 8Y
colspan 0C aw) Therefore x!
Step 2 (3a;, Oc B7 04 6₁ = null( dc
E mull( (G)) )): First, for both directions of the proof,
can separate 2y a; = e; into 2 different requirements:
0c
dc 8Y 0r;
(3)
84, a;
ac
(4)
(+) Assuming the existence of a with ac = Cs. we know that Eq. SY
3 and Eq. hold. It is
evident with 0; E null(
0C but as mull( of that null 0C OY
null( ac
OY
8c (+) First of all, we note that SY,
E Ixd has rank 1, as SY, contains non-zero entry under normal training conditions. Therefore,
ac has nullity (5 SY.
due to the rank- 8C OY
nullity theorem. null( Sx, g null(
0c OY 2c b9
that af & mull( ac) (since mullity
1 this set is non-empty). For that ag,
the following hold:
3Y. 0
dc
OY,
a' =c c
Therefore, if we take a4 L as would satisfy both (2) and (3), giving us a valid solution.
Step 3: (null( .Y
& null(
& rowspan
(5 First of all, the statement
NY
SY
equivalent to negating both sides, null( can be shown by the following steps:
dc OY
ac C null(
ac
rowspann Øc oY
), which
OY,
aY.
mull DY
C mull
0c OY
+ null(
0C .Y
c C mull dc )
rowspan
ac DY.
8C C rowspan
57
dc OY,
E rowspan AY
15

---

Published as a conference paper at ICLR 2025
Here we used that the complenetary subspace the null space of matrix is the rowspan of the matrix null( y (owspan(M)) The last step follows from that the fact that &c is a single common ØY, vector, and therefore all vectors in colspan( X4,) are of the form A 8Y, This concludes our proof.
We extend this by presenting the proof for Cor. 5.2g
Corollary 5.2. For ac az' full-rnk,, n < if the (possibly normalized) adjacency matrix layer Bc 1, A E Raxn, X E colspan( aw?) if and only if A? & colspan(A.) Further, if A is full-rank, then X E colspan( 0C for all 1, n..
OWT
Proof. For notational clarity, we omit the layer index in our proof.
From Z = =Y, by applying the following common result from Petrov et al. (0244) (replacing W with Y. and with Z), we obtain:
&c A
8c 82
Therefore,
0C 8Y:
AT
0c 8Z
We will now prove that if ac is full-rank, then AT & colspan 82
5C BC & rowspan( OY,
). This is equivalent to proving the converse, or A colspan (A.)
UY
8C OY,
rowspan
dc OY,
(=) AT E Ecolspan (A,) implies that there exist coefficients a 02." An, such that:
A =
Σ
a
Multiplying both sides by az gives:
dc
A ac OZ
Σ
Dc aj a
oz
OC 0Y:
=
Σ |= NY
ajoy,
ac
-
Oc OY:
E rowspann 52 BY,
NAO
(+= We can similarly rewrite
Bc RY,
E rowsspan
BC BY,
0c
E
OC BY
A
T oc az
Σ
aj
0c a2
OY:
(1.22.....
j= NAA0
As 8C is full-rank, then there exists a right-inverse
8C oz
R
Multiplying on both sides gives:
oZ
A 0C Oc oz
Σ
A T 0C ac az az
aj
NRG
A7"
Σ
Af + A E colspan A,)
j=(1.2.....
From here, we can now apply Thm. 5.1 which gives that X; E colspan ow) ) if and only if AT & colspan(A,)) If is full-rank, then AT & colspan(A,) for all 1.2,.... n, implying that X; E colspan( SW) for all This concludes the proof.
A.2.2 EMBEDDING RECOVERY PROOF
In this section, first we formally state Asm. A. on which Thm. 5.3 is based. Next, using it we provide a proof for Thm. 5.3 Finally, we prove that Asm. A. is satisfied for common GNN archi- tectures, such as GCNs and GATs.
For simplicity, in the rest of the section we will denote the node of corresponning to the the 2h row of the embedding matrices X! with v;.
16

---

Published as a conference paper at ICLR 2025
Assumption A.I. The output corresponding to the node vs of the 1-th layer of the GNN, X!+1 is independent X3 for Voz $ (v)
The assumption intuitively states that for most popular GNNs the embeddings of node only de- pends on the embeddings of its neighbourhood the previous layer. Using this, we now present the proof of Thm. 5.3, restating it for convinience:
Theorem 5.3. For GNNs satisfying Asm. A.7 propagating a correctly reconstructed building block G. centred at v through the first I GNN layers recovers the original embedding of v. at layer l:
fi = =
where is the index of u in the adjacency matrix of the original input graph G and is the index of o in the adjacency matrix of go..
Proof. First will show that the embedding X is independent of the embeddings of any nodes that do not belong in the I-hop neighborhood of v. For / = 1 this follows immediately from Asm. [A.] For 2, we know that X is only dependent on the embeddings X of the neighboring nodes Pe E <Ng(e) by applying Asm. A.1 However, the embeddings X themselves only depends on the embeddings of the nodes in the -hhop neighborhood of Ug. Therefore, the only nodes that can influence X? are v, its neighbors, and the neighbors of its neighbors, which exactly comprise the 2- 2-hop neighborhood of v. Similarly, we can show that X is independent of the embeddings of any nodes that are not part of the I-hop neighborhood of e by induction.
We now take the full graph G and remove all edges starting or ending at nodes not in Gh and set their feature values to O, obtaining G. As shown above, this implies the output of fi-1 for G at is the same the one for G. Note that applying the network on 9 is the same applying it to g except for few the additional embeddings produced for the disconnected nodes. By reindexing we arrive at our formula.
Finally, we prove our assumption Asm. A. holds for all GNN architectures considered in this paper: Theorem A.2. Asm. A.7 holds for GCNs
Proof. For GCN models, the formula for computing the hth embedding layer + 1, X!- can be expressed as:
x
Σ
A W' x
(..))
where A is the normalized strength of the connection between i; and ny at layer I given by:
Al.s
//de(vi)ddg(t
Assuming the degrees of the nodes uy E (e:) are known, x! is independent on X for ey & (V;)) We note that for correctly recovered (-hop neighbourhood around the degrees of all nodes in the (1 - hop neighbourhood around u can be recovered exactly, while for the remaining nodes one provide sound lower bound for their degree. Assuming sound guess the upper bound on the largest degree in the graph, this allows to recover the degrees of the remaining nodes via enumeration starting from these computed lower bounds. Further, if the input features X of contain information about the node degree of vs this information can be easily incorporated to reduce the computational overhead of the enumeration.
Theorem A.3. Asm. A.7 holds for GATs
Proof. For GAT models, the formula for computing the tt embedding at layer 1 1, x!+1, can similarly be expressed as:
x
Σ
Ale w'x
()EN)(()))
17

---

Published as a conference paper at ICLR 2025
where A is the attention coefficient between ty and by at layer given by:
exp (Leaky (aa)) w x)))
A Ee (Vg((N)))) exp (LeakyReLU ((a)) W x))
and a' is a vector of attention parameters.
As X 1++1 only depends on W Aly and X to be calculated for by E (eg)))),, and A itself also only depends on X and W we show that X!+1 is independent on X for u $ (N))))).
A.3 GLUING ALGORITHM
In order to establish the gluing operation, we need first define how we determine which nodes in G and G can potentially match, so that the building block is glued correctly. This can be achieved recursively, by ensuring that:
For every pair of matched nodes, their features must be exactly equal.
The center of g c matches the center of attaching
For a node E V of and its match uB BBB every one of its neighbors e' ((t,2') E) has to match a neighbor V'D UB ((UB, 2/)) E E²).
This recursive definition can be satisfied by exploring the possible matchings from the center outwards. In particular, we explore the i-hop neighborhoods one by one for i = 1,2, I. We try all possible matchings Up for the given node v, such that their features match, and the matches of its neighbors (in particular those which have already been traversed) are also connected to (Line 7
After all possible matchings are generated, with those in the building block, in order to obtain the set of all possible gluings (Lines) 13 16
easy substitute any nodes in the original graph
Algorithm 5 Gluing graph with building block
1: function GLUB(G, GB c,
2:
M < (((c,=))))
3:
for i i= 1.2,..... do
Generate all correct matchings
4:
for v E (oldist(c, w) i) do Mnew + {}
5:
6:
for M E M do Mnew Mnew x {(U, (B,, X A Meweeeetteesheeeeee E²)
7:
8:
M Mnow G 0
9:
for
M M do İ + VVNg(cc)UV,
Transform matchings into valid graphs
11:
12:
È ++H BB for (u, do
13:
14:
vg if (p, M else
15:
= v'g if (v' M else of
16:
E - ((v,)))
G G GU ((V,
18:
return
18

---

Published as a conference paper at ICLR 2025
A.4 FEATURE-BY-PEATURE FILTERING ALGORITHM
Algorithm Filtering nodes feature-by. bereeeby---ffrre
1: function (F: mm +8W6 7)
ac
2:
(1, dsum < (1, Fi
3:
for k E 11, m) do
4: To. - T - x Fk dsum + doum + [F
5:
6:
daum > rank oW. then
UC
This is a requirement for the filtering to work
7:
8C Ti ( awo
dsam] T, Xe.
8:
return Tu.m
Here we describe how we build and filter 0-hop neighborhoods, i.e. the single node client feature vectors. While DAGER directly enumerates and filters all possible text input feature vectors, for many graph data applications this procedure is impractical. To this end, we instead recover the node features one-by-one, as described next.
For the first feature, we generate all partial input vectors associated with the values in Fi and then filter them create the of consistent partial input vectors T0.1- To do so, we apply our span- ac check on the truncated input layer gradients aw.o [ [Fill corresponding to the input entries of the first feature. This is possible since, by Thm. 5.1 the truncated i-th row of X, X [i, [Fil], is similarly filter the of vectors responding to combinations between a partially recovered vector in To,-- and a value in Fi by applying Thm. 5.1 to obtain the set of consistent partial input vectors up feature i To Finally,
in colspan( oWe
ac [Fll))- For each subsequent feature,
we obtain T 0.m- A pseudocode for this approach is provided in Alg.
A.5 STRUCTURE-BASER FILTERING ALGORITHM
Algorithm Structure filtering algorithm
Oc 1: function STRUCTUREFILTER(T;; 7W
2: for E Tí do
3: if Ag = then return G
4:
5: CunGlue +- True
6: for E V do
7:
!3 E TTi g²,v) then CanGlue <- False break if CanGlue then Tn t Tn (g}
8:
9:
11:
return TB
A.6 DEPTH-FIRST SEARCH IMPLEMENTATION
We present the pseudocode for branching the DFS tree:
Cycles exploration After every step of gluing possible building blocks from T3 to Gour at node (line 5 in Alg. 8). we enumerate all sets S of pairs (V) E Geurs $ Geur) of vertices of any graph G E G such that the features U1 and U2 match (line 9 in Alg. gp. For every such set S, we additionally consider for exploration the graph ğ' = overlap(
created by overlapping each pair of vertices in S (line [0 in Alg. 8). Intuitively, this allows us to reconstruct any cycle of the input graph. All valid overlaps, including those with 0. where the graph remains unchanged, then added branches of the search space (line g in Alg
19

---

Published as a conference paper at ICLR 2025
Algorithm 8 Generate graphs for branch
1: function BRANCH(TB. Geurr+ u))
2: Gnew +
3:
4:
for B E TT do
5:
G glue(Geumr B) i + @ then
6:
7:
Gaow new L G for G' EG do for (V(g") V(geun) V(gaum) do
8:
9:
10:
Gnew +- Grow U (overlap(g',S))
12:
return Gnew
Node overlaping In this paragraph, deseribe how the overlaping function (used in line 10 in Alg. 8) works. Given graph g' and a set of pairs of nodes S, if some pair has two nodes with different node feature vectors, the function returns empty graph. Otherwise, for each pair (vi, 02) E S we modify the current graph by deleting 12 and connect add an edge between ii and any node that was previously neighbor of U2 but not U1. After doing these overlaps for every pair of nodes in S, the new graph is returned.
B THE GSM METRIC
We designed the GSM set of metrics so that they satisfy the following three qualities:
The metric should be efficiently computable in polynomial time
It should capture both structural and feature-wise information
Isomorphic graphs should be guaranteed achieve 100% score
( where for all Fk : g xd is a function that aggregates the feature vectors for each k-hop neighborhood. This allows to measure the similarites in features across increasingly larger subgraphs, which capture the structure around each node. In our case we utilise a randomly initialised 2 k-layer GCN to achieve such mapping.
To this end, we define GSM-Nr(G, 9) under set functions
We note that a precise evaluation of the metric requires for us to match the 2 graphs as accurately as possible. Since exact matching of graphs has known polynomial-time algorithm (Babail 2016), we match the graph nodes by applying the Hungarian matching algorithm (Frank (005) for mini- mizing a cost function C that captures the feature difference across (0-5)-hop neighborhoods:
d
C₁
(Fv(g) (x()))
k=
We can hence define:
FI-Score(Pxx()) Fv(()) (9) discrete
GSM-Nr(9.9)-
Fx(
if Fx (g) continuous
First of all, the NP-complete nature of the subgraph isomorphism problem makes difficult to do any subgraph or full-graph matching, which we tackle by utilising the hidden states of a GCN create an approximate matching between nodes. The method described above ensures that for isomorphic graphs, the correct k-hop neighborhoods will be matched and the GSM-k metric will achieve perfect score.
The second requirement is rarely satisfied by metrics defined in the literature (i.e. the edit distance), as comparison studies on coloured graphs are limited. Our solution these problems was inspired by the ROUGE set of metrics (Lin 2004), used for evaluation of textual similarity. Instead of
20

---

Published as a conference paper at ICLR 2025
comparing sequences such unigrams bigrams like ROUGE, we instead compute continuous properties of graphs on the scale of different k-hop neighbourhoods. This rationale allows us to compare both node-based and structural properties using a simple methodology.
C ADDITIONAL EXPERIMENTS
Here we present additional experiments that are not part of the main text.
C.I HUMAN EVALUATION FOR THE GSM SET OF METRICS
We performed a human evaluation, where 3 experts in Graph Theory and Chemistry were shown 120 sample reconstructions of molecules, as given by DLG and GRAIN. The samples were shuffled, and the participants were tasked to assign a score from 0 to 10, with the following instructions:
"Thank you for agreeing to participate in this study the quality of graph reconstructions! We have gathered a set of graphs, coupled with the best-effort reconstruction. Please give each pair a score of 0-10, where 0 is a complete lack of similarity, and 10 is perfect match. When assigning score, take into account the structure of the two graphs, as well as the alom type for matching atoms, and also be wary that 2 graphs might be isomorphic, but have different pictures. Please disregard the connections between atoms, as the methods we used do not recover any edge properties. Give your, as best as possible, score on how similar the graphs are with respect to these properties."
Reconstructed samples from both GRAIN and DLG were shuffled and anonymized before being presented to the participants. We report the average scores for each algorithm, multiplied by factor of 10 to match the order of magnitude of the GRAPH metrics, and present the results in Tab. [ We observe very good correlation between our metrics and the reported human scores, even though our metrics are slightly more lenient to completely wrong reconstructions, compared to the evaluators. This leniency provides slight advantage to the baseline attacks when measured using our metrics, the baselines fail catastrophically more often.
Based on these studies, we also show Tab. 7 that our partial reconstructions are deemed more significant than what the metric suggests, likely meaning that there examples which present significant information leakage. contrast, high-scoring examples from the DLG attacks have been rated as essentially uninformative.
Table 7: Score discrepancy examples between human evaluators and the GRAPH set of metrics. G-1 stands for the GRAPH-1 metric.
GT
GRAIN
G-1
Study
GT
DLG
G-1
Study
62.0
93.3
52.7
10.0
CHpip No Nc.
Hjp
41.3
63.3
61.0
23.3
33.5
56.7
41.0
0.0
Additional examples of molecule reconstructions comparing GRAIN, DLG, and TabLeak are shown Fig. 5 this set of examples, the first 3 columns show the exact reconstruction of the input. We also highlight that in cases where GRAIN does not managed to recover the entire graph, the attack can reconstruct subgraphs the input (4th column), and a more realistic approximation otherwise (5th column).
21

---

Published as a conference paper at ICLR 2025
Original
GRAIN
DLG
HH
TabLcak
Figure 5: Examples of molecule reconstructions compared between GRAIN, DLG, and TabLeak.
C.2 ADDITIONAL. CHEMICAL. DATASETS
Table 8: Results (in %) of main experiments on biochemical datasets Tox21, Clintox, BBBP.
Here "+A" refers to the baseline attack with the input adjacency matrix given.
GSM-0
GSM-1
GSM-2
FULL
Runtime[h]
GRAIN
86.9
83.
82.6 5.7
68.0 1.7
14.3
6.9
7.4
DLG
31.8+4.5 4.3
20.3 4.8
22.8+6.6
5.6
1.0
3.3
Tox21
DLG +A
54.7+3.9
60.1 +4.6
76.7
1.0
3.1
5.2
TabLeak
25.1 5.1
12.4
+5.5
10.8 +5.6
1.0 0.2
13.1
4.3
4.3
3.9
TabLeak +A
55.6
3.9
3.9
57.7
4.1
4.6
73.8 3.5
1.0
12.3
GRAIN
73.7+5.7
6.5
68.4
7.8
66.8
36.0 + 1.2
24.1
DLG
24.0 4.1
10.3
12.2
1.0 0.2
3.5
Clintox
DLG +A
52.5
52.6+11
72.3
1.0 + 0.2
3.2
TabLeak
17.6 17.6
6.0
5.4+42
1.0 0.2
15.2
Tableak +A
54.0 3.3
52.0 +338
62.8+333
4.2
1.0 + 0.2
14.5
GRAIN
71.7 +5.9
66.8
64.9+7.
38.0 1.2
23.7
6.8
7.7
8.0
DLG
22.6 3.6
8.8
10.0 3.7
0.0
3.9
3.3
BBBP
DLG +A
51.6 3.6
+31
50.1
70.6+31
0.0
3.1
TabLeak
17.6 +3.8
6.3
4.7 4.773.7
0.0
12.6
2.5
2.3
TabLeak +A
59.1 3.6
+31.1
59.4 43.6
71.9 4.0
2.9
0.0
12.5
4.3
In this section, we present our results on additional chemical datasets, namely Clintox and BBBP (Wuet al. 2018). We highlight in Tab. that GRAIN generalizes across all settings, retaining

---

Published as a conference paper at ICLR 2025
its increased performance over the baseline attacks. We reaffirm that we achieve these results despite running for time comparable to the one of Tableak.
C.3 ADDITIONAL ABLATION STUDIES
We perform additional ablation studies on various assumptions and parameters, demonstrating their effects GRAIN. In particular, we observe how architectural changes might affect our perfor- mance, or how properties of the data might influence reconstructability.
Table 9: Results (in %) of main experiments with the LBFGS optimizer. Here "+A" refers to the baseline attack with the imput adjacency matrix given.
GCN
GAT
GSM-0
GSM-1
GSM-2
FULL
Min/Rec
GSM-0
GSM-1
GSM-2
FULL
MinRee
62.5"22
31.0 5.0
618.1
79.3
11.1
69.6
69.61.8
1.6
DLG
67.7:52
0.0191
0.3:
0.0 0.0
67.7152
0.0
0.0
0.0
31.0
ChicSeer
DLG +-
67.7 67
0.0"
0.02.0
0.0 1.000.
29.9
67.77 67.7"
0.02pu
0.02mu
0.0 0.00
27.7
7:33
0.0"0a
0.05hb
158.8
0.0:20
0.0thu
TabLeak +
67.7
0.0
0.0280
0.0 0.00
202.0
67.71:67
0,0200
0,0
0,0.000
168.7
GRAIN
68 08.3:52
50.7
56.8
15.0 = 0.S
0.1
97.2118
53..5
96.3112
79.0 1.8
0.2
00.0753
11.31166
13.7 187
41.7153
2.2
0.0tha
0.0
26.3
Pokec
DLG +-4
48.7:15
39.12
518
=.2002
38.5
57. 07.4"55
09.5
58.6181
0.0
21.8
TabLeak
09.0
8.2
5.6
177.5
30.8
13.9 5
7.9129
0.0 0.0000
204.5
Tall
49.911
38.1533
1:24
58:251
216.0
62.6133
68.1256
82.7550
Effect of optimizer on baseline results In main experiments presented results for the CiteSeer and Pokec datasets with the baselines running an SGD optimizer. In Tab. 9 we present results with the more stable LBFGS optimizer averaged across 10 reconstructions due to time limits. We see that the baselines show better performance, however, GRAIN still outperforms them and is less resource-consumingg requiring up 100x less runtime.
Effeet of model parameters reconstruction quality First, in Tab. T0 and Tab. 11 strate the performance of GRAIN under modifying the model parameters. We observe that neither changing in the number of layers nor the hidden dimension size of the GCN substantially affects the performance of GRAIN, while reaffirming the significant improvement over the baselines, even when they are given the graph connections prior knowledge. We note that we only utilise the first 2 GCN layers even when > 2, showing the robustness of our method.
we demon-
Additionally, we note that GRAIN is not significantly impacted by the embedding dimension d', as long as n < d', consequently achieving similar scores, particularly for small graphs. We show the exact results in Tab. 11
Effect of span check threshold on filtering capabilities We now investigate the effect of the choice for the threshold, used for filtering inputs using the span check method. We measure the ra- tio between the number of nodes and I-hop building blocks that pass the filter, and the actual number
of these blocks. We explore different values of the range [10-6 6 1]. and evaluate this metric on 10 randomly chosen samples from the Tox21 I dataset. We show in Fig. 6 that any E [10-4, 10-2] results in essentially the same filtering results, and that thresholds in this interval perfectly recover the correct I-hop building blocks.
Adjacency matrix low-rankness effect on reconstructability Further, in Fig. 3b we looked into how the rank-deficiency of the adjacency matrix A affects how much of the input GRAIN might be able to recover. For different sizes of A, we measure what the Monte-Carlo probability of A being full-rank, and the fraction of nodes we can recover, computed per Thm. S.I This was done for synthetic graphs, where we sampled 100,000 symmetric binary matrices with varying probability of every 2 nodes being connected, as well as for all molecular graphs in the chemical datasets Clintox, Tox21 and BBBP. We show that Thm. 5.] is crucial for understanding why GRAIN is effective, despite the probability of A being full-rank being low. particular, we highlight in Fig. 3b that
GRAIN can recover an increasing fraction of nodes as A grows.
23

---

Published as a conference paper at ICLR 2025
Table Results (in %) GRAIN and the baselines in cases of different model parameters. Here
L is the number of GCN layers and d' is the model's width. L 2, d' 300 is the original setting.
GSM-0
GSM-1
GSM-2
FULL
GRAIN
86.9+1.2
83.9*52 2
82.6+5.
68.0 1.7
5.7
7.4
L = 2,
DLG
31.8*4.5 4.3
20.3 +5.5
22.8 +2.8+6.6
5.6
1.2
d' 300
DLG +A
54.7*32
60.1
76.7
1.0 0.2
5.2
4.8
(default)
TabLeak
25.1 4.3
12.4 12.4 +5.6
10.8 10.8
+5.6
1.2
4.3
3.9
TabLeak +A
55.6 3.9
57.7
73.8
1.0 0.2
GRAIN
82.517.7
80.7
80.4
63.0 + 1.6
DLG
20.3+
7.8+5.1
8.2
1.0 = 0.2
L
DLG +4
43.0 3.6
48.0
66.0 3.7
1.0 0.2
d' 300
TabLeak
16.5
8.8 1.4
3.1
8.0
1.0 0.2
TabLeak +4
47.5 4.2
48.1
62.9
1.0 0.2
GRAIN
83.9 5.5
82.8 5.9
5.9
82.8
64.0 + 1.6
7.4
7.7
L
DLG
DLG +A
39.1 +-3.7
14.1
2.8
37.0
4.0
55.6
4.8
1.0 0.2
1.0 0.2
d' 300
3.8
TabLeak
12.0
2.1
3.4 1.7
4.0
1.0 0.2
TabLeak +A
30.0 4.0
27.3
51.1 5.3
4.9
1.0 2 0.2
GRAIN
84.6
81.4 458
80.5 +5.9
62.0 + 1.6
6.4
6.9
7.2
DLG
30.8+15
18.9
22.2+6.7
1.0 + 0.2
L 2,
DLG +4
50.3+42
53.4+5.3
68.71
3.0
d' 200
5.9
TabLeak
22.1+1.
10.3+5.3
8.9
1.0 0.2
366
3.6
TabLeak +4
55.0 5.0
62.1 +..9
76.7
1.0 0.2
5.9
GRAIN
85.2 4.6
81.5
5.4
80.1+6.1
63.0 + 1.6
6.1
7.1
7.5
DLG
35.1 1.7
26.1 +6.4
25.0
1.0 0.2
L = 2,
DLG +A
57.6+3.9
61.714.7
72.5+4.3
2.0 0.3
d' = 400
TabLeak
28.5
17.1
12.9 12.9
1.0 0.2
4.0
TabLeak +A
61.7 3.7
+3.6
62.6 +3.6
76.3
+ 2.9
1.0 0.2
4.4
3.3
Table 11: Results (in %) of GRAIN with different embedding dimensions across range of graph sizes
S.S 15
16 S. n S 25
26 S m.
GSM-0
GSM-2
FULL
GSM-0
GSM-2
FULL
GSM-0
GSM-2
FULL
300
93.0+3-
91.6 0.
81.9
81.7:39
71.8
43.6
50.1:44
39.2133
5.1 0.6
128
92.1-11
92.3
79.3
81.4+10
75.1+17
43.6
19.3-72
36.8+57
5.1 = 0.6
92.2*
92.0
79.3 1.6
81.3*11
75.5*
43.6
48.677
37.9
6.1:0.6
32
92.2
91.7
3.0
79.3 1.6
81.7140
140
73.8 6.1
4..
15.3
13.3:25
0.0 0.0
D LIMITATIONS
GRAIN is the first algorithm advance the field of gradient inversion for graph data, and see significant potential for further development. However, our attack method currently assumes that the FL protocol includes node degree as node feature. While this assumption holds in many GNN settings, relaxing it leads to reduced performance. Improving performance under relaxed assumptions an important direction for future research.
Another key area for improvement is reducing the computational complexity of GRAIN, enabling scale to larger graphs and graphs with nodes of higher degree. We believe this to be promis- ing future direction, as there are many potential optimizations that could enhance the algorithm's

---

Published as a conference paper at ICLR 2025
Table 12: Results (in %) of GRAIN tested on the Pokec social network dataset (oosi & Ahmed
2013 20 subgraphs were sampled for each of the size ranges 25-30, 30-40, 40-50 and 50-60
71
GSM-0
GSM-1
GSM-2
FULL
Runtime[h]
25-30
98.3+00
95.1+0.5
96.8+0.4
17/20
0.17
30-40
83.1
61.6"3.0
79.4
5/20
0,46
3.6
40-50
69.3
3.8
38.0*4:3
4.3
59.2*47
4.0
2/20
0.64
50-60
32.7 3.9
23.3*3:3 3.5
41.2
14.6
3/20
0.43
4.1
Total
70.916.
55.6 1. 7.2
69.2
27/80
1.70
6.6
efficiency. Particularly promising is using data priors that have the potential to severely reduce the number of span checks that need be performed by efficiently filtering impossible subgraphs.
Additionally, GRAIN relies on the assumption that the GNN architecture satisfies Asm. A. While this assump- tion holds for widely used GNNs like GCN and GAT, adapting our algorithm to support other GNN types is left for future work.
Figure 6: Ablation study on the span check filtering threshold
Filtered BBs Ratio
102
Moreover, as discussed Sec. 5 GRAIN requires that < d' to maintain the low-rank nature of gradient up- dates. While this is limitation, we believe applies many real-world scenarios, meaning that practical FL. set- tings remain vulnerable to privacy risks.
10
108
Ground truth
10-1
Layer 0
Another assumption GRAIN depends on is that the weighted adjacency matrix A high-rank, with full re- construction possible only if A is full-rank. While this holds for GAT architectures, it is not always true for GCNs presented in Fig. 3b Relaxing the full-rankness assumption would be a crucial step toward better understanding privacy risks FL. for GNNs.
Layer
10 10-2 2
22
Threshold
Finally, leave the investigation of potential defenses against GRAIN as well more complex federated learning protocols such as Federated Averaging for future work.
25


Reviews:
[{"review_id": "TvxB5u8Z8R", "reviewer": "Reviewer_61N5", "summary": "This paper proposes GRAIN, a gradient inversion attack on GNNs. GRAIN identifies subgraphs within gradients and filters them iteratively by layer to construct the full input graph through a depth-first search approach. New evaluation metrics are introduced to measure similarity between reconstructed and original graphs for graph gradient inversion attacks. GRAIN has a desirable performance on the molecule benchmarks.", "questions": "Please see Weaknesses.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 1, "contribution": 2, "strengths": "- This paper proposes the first gradient inversion attack on GNNs. This topic is interesting and unexplored. This paper could inspire further investigation on this topic.\n- A new metric is proposed to measure the similarity between graphs.\n- The proposed GRAIN achieves a desirable performance compared with existing attacks.", "weaknesses": "- It is mentioned that $\\mathcal{T}_0$ is the cross-product of all possible feature values. It seems to be impractical for general attributed graphs and only possible for molecular graphs where the node features are in a small set with low dimensionality.\n- It would be helpful to include a Threat Model section to introduce the attack settings, such as the adversary's knowledge, capability, and objective. What is the function $f$ in Algorithm 2? Is it the exact target GNN model? \n- The introduction mentions federated learning as a practical scenario of gradient inversion attacks. However, the methodology part does not include any specific FL settings (such as local models and global models). Is FL a necessary requirement for implementing GRAIN?\n- The challenge of gradient inversion attacks on GNNs is understated. Why GRAIN is not a trivial adaptation of existing methods [1] to GNNs and what unique challenge does GRAIN overcome while other methods fail to?\n- The introduction of proposed algorithm is not clear enough. It would be better to introduce the detailed algorithm following a single direction (e.g., from input to output). And it would be helpful to add a notation table.\n\n\n[1] Petrov, Ivo, et al. \"DAGER: Exact Gradient Inversion for Large Language Models.\" arXiv preprint arXiv:2405.15586 (2024).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "extra_scores": {}}, {"review_id": "BNuH1jzQkw", "reviewer": "Reviewer_d7Q7", "summary": "This paper presents GRAIN, the first exact reconstruction attack specifically designed to target GCNs. By leveraging the low-rank structure of GCN layer updates, GRAIN can accurately reconstruct both the graph structure and the associated node features from the gradients shared under federated learning setting. This attack demonstrates a significant privacy vulnerability in GCN training within the federated learning framework.", "questions": "see Weaknesses", "limitations": "", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1. It is the first work that explores extracting the structure of a graph from gradients. \n2. The framework demonstrates promising performance across different scenario.", "weaknesses": "1. The article seems to be largely based on the theories presented in [1] and then adapted it for GCNs, particularly Theorem 3.1. However, for readers unfamiliar with this work, it may be quite challenging to comprehend. We hope the authors can provide more discussion on why the filtering mechanism can be effective.\n2. Following the previous question, what is the difficulties encountered when applying the methods from [1] to graph data? A detailed explanation of the challenges encountered during this adaptation, including any limitations or obstacles that were overcome, would help clarify the novelty of the work presented.\n3. The article uses the degree of a node as a node feature; however, this approach may limit the application scope. For instance, in the case of chemical molecules mentioned in the article, relevant features are more likely to include chemical properties. We suggest that the authors discuss this point and conduct further experiments.\n\n[1] DAGER: Exact Gradient Inversion for Large Language Models.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "extra_scores": {}}, {"review_id": "MLZYjk5HVY", "reviewer": "Reviewer_HRGw", "summary": "The main contribution of this paper is that it is the first to address gradient inversion attacks on graph data, highlighting privacy risks in graph federated learning. Based on the theorem from Petrov et al. (2024), the authors propose a method capable of reconstructing both the graph structure and node features. They reconstruct the graph step-by-step, from low-degree to high-degree levels, with each step involving the filtering of unlikely candidates through a span check. Finally, by leveraging degree information in the features, they generate the final prediction using a depth-first search (DFS) algorithm to combine the remaining candidates.\n\nIn experiments, the proposed method outperforms other baselines. The authors also conduct a hyperparameter analysis by adjusting L and d', representing the number of GNN layers and the hidden dimension, respectively. Additionally, they test varying numbers of nodes, identifying limitations as discussed in Section 7.", "questions": "1. In Table 3, $d' = [200, 300, 400]$ represents quite a large hidden dimension for training graphs with a small number of nodes (i.e., $\\leq 25$). I wonder if this method will still work when the hidden dimension is much smaller (e.g., 32, 64, 128).\n\n2. As I mentioned in W1, I suggest that the authors provide additional evaluations on other categories of graph datasets.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. As the authors mention, this paper addresses a crucial yet unexplored problem: gradient inversion attacks in graph federated learning.\n2. Constructing both the graph structure and features is a challenging task, but it is interesting to see experimental results that accurately reconstruct the input graph, even if restricted to chemistry graphs.\n3. This paper suggests future directions for gradient inversion attacks in the graph domain, as discussed in Section 7 (Limitations).\n4. The paper is well-written and easy to follow.", "weaknesses": "1. I agree on the importance of exploring gradient inversion attacks in the graph domain, and this could be a notable contribution of the paper as it is the first to address this issue. However, the scope is quite limited in terms of graph types. Specifically, the paper focuses only on chemistry datasets. To fully substantiate its contribution as a pioneering work in gradient inversion attacks on graph data, the authors should demonstrate that this method is applicable to other types of graph datasets, such as citation networks (e.g., Cora, PubMed) or transaction networks (e.g., Elliptic). This is especially important since molecular graphs may be relatively less privacy-sensitive than other graph types (e.g., transaction networks), and federated learning in molecular graphs may be less common. I suggest that the authors provide additional evaluations on other categories of graph datasets.  \n\n2. As shown in Table 2, the proposed method only works well when the input graph has a limited number of nodes (i.e., $\\leq 25$). I understand that, given the step-by-step approach of combining building blocks, this limitation leads to higher computational costs and a greater risk of error as the graph size increases.  \n\n3. The claim that using the degree as a feature is widely adopted in training GCNs is not entirely convincing. Using degree values as features is more common in graphs lacking attributes or in structural learning tasks. However, since this paper addresses gradient inversion attacks in federated learning, it should consider more practical settings where degree values may not be used as features. How might this method be adapted if degree information is not available as a feature?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "extra_scores": {}}, {"review_id": "blQrMf74ue", "reviewer": "Reviewer_5Wij", "summary": "This paper presents GRAIN, a novel gradient inversion attack designed for Graph Convolutional Networks (GCNs) in the federated learning (FL) setting. GRAIN leverages an efficient filtering mechanism to identify subgraphs of the input graphs, which are then pieced together using a depth-first traversal to recover the full original graph. This method enables the exact reconstruction of graph structures and node features from gradient updates clients share with the federated server. The main contribution is extending gradient inversion attacks to GCNs under harder FL settings, which is a significant step toward understanding the privacy vulnerabilities of federated learning when applied to graph-structured data. The introduction of new evaluation metrics for graph similarity (e.g., GRAPH-N) is also an excellent contribution, providing valuable insights into partial and exact graph reconstructions. Lastly, this paper presents extensive rigorous experiments on molecular data, demonstrating that GRAIN significantly outperforms existing baseline attacks regarding exact graph reconstruction accuracy in the chemical domain. The empirical performance convincingly highlights client privacy risks associated with FL for graph-structured data, making this work relevant to a broad audience.\n\nOverall, I am leaning toward acceptance of this paper. The novelty of GRAIN, its strong experimental results, and its contribution to the discussion on privacy risks in federated learning make it a valuable and impactful addition to the conference. However, there are some limitations and concerns that require further clarification and improvement (see weaknesses).", "questions": "See weaknesses.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. Technical novelty.\n2. Strong experimental results.\n3. Contribution to the discussion on privacy risks in federated learning.", "weaknesses": "One major limitation is that GRAIN struggles with larger graphs due to the high computational cost. As mentioned in the paper, the method times out for large molecules. Have you considered any strategies for reducing the computational complexity of GRAIN, such as parallelizing the depth-first search or using pruning techniques? Furthermore, more detailed comparisons of the convergence time of GRAIN versus the baseline methods might be beneficial, particularly for larger graphs. Could you provide more quantitative details on the computational overhead of GRAIN in comparison to other baselines?\n\nI noticed several similarities between the algorithms and figures in this paper and those in your reference DAGER. I would appreciate more clarification on how this paper differentiates itself and introduces novel contributions beyond the existing work. Highlighting the differences, extensions, and innovations more clearly and explaining your considerations on adaptions might strengthen the paper's contribution.\n\nFinally, in the experimental section, the paper notes that GRAIN cannot recover multivalent interactions, an edge property that GCNs not able to capture. However, given multivalent interactions are associated with features like \"valence structures\" in the MoleculeNet benchmark datasets, whether other node features such as valence structures be fully used in graph filter and node-feature recovery? This raises the question of whether GRAIN has limitations in effectively utilizing feature vectors of the input nodes. It would be helpful if the authors could clarify whether GRAIN could recover some other complex critical chemical characteristics with all feature vectors and the reasons behind them.\n\nFor the experiments, the following should be addressed.\n\n1.\tIt would be helpful to see more experiments that vary the value of chosen threshold tau in the span check mechanism to better understand its role in filtering performance.\n\n2.\tFor the scenario where exact reconstruction is not achieved, what proportion of nodes and edges are typically misplaced, and how? Additional discussion on this and how it affects real-world privacy concerns would provide a more comprehensive picture of the method's practical implications.\n\n3.\tAs the proposed graph similarity metric is novel and potentially valuable, I have some concerns regarding the fairness and comparability of the results. Specifically, how do you ensure that the comparison is fair, given that the baseline methods were not specifically designed for graph-structured data? Additionally, it would be helpful to include a more detailed explanation of why common, widely used metrics were not used for comparison in the meantime. This clarification would strengthen the validity of your results and provide a clearer understanding of how the proposed metric aligns with established evaluation standards.\n\nMinor comments:\n1)\tIn the Abstract, there is redundancy in the first sentence (e.g. “Federated learning allows multiple parties to train collaboratively while only Federated learning…”).\n2)\tIn the third line in 5.1, the symbol is a subset instead of an overlap.\n3)\tIn 5.1, the third sentence in Additional structure-based filtering and likelihood ordering, the grammar of “Specifically, we for every…” is wrong. The last sentence in the same subsection “lines 3–13 of Algorithm 1” should be 3-14.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "extra_scores": {}}, {"review_id": "Lz1Wo4pwQU", "reviewer": "Reviewer_t4xV", "summary": "This paper proposes a method for gradient inversion attack on graph neural networks. This problem differs from previous gradient inversion attacks in that not only the node features but also the graph structures. The proposed method involves a recursive construction process that continually glues small building blocks to build large graphs. The authors propose some new metrics for this new task of gradient inversion attack on graphs, and show that the proposed method achieves state-of-the-art performance compared to other existing gradient inversion attacks.", "questions": "1. Please briefly explain the unclear parts stated in Weakness 1. \n\n2. Please briefly discuss how the assumptions in Weakness 2 hold in practice, and what will happen when they do not hold.   \n\n3. In practice, graph data are often organized in a batch, and the gradients are an average of all samples in the batch. Does GRAIN assume batch_size=1? Will this change the effectiveness of GRAIN?\n\n4. In the case with more complex/adaptive node-wise relations, such as Graph Attention Networks, will GRAIN still work? From my understanding of Lemma 5.1, $\\tilde{A}$ plays an important role, and in GAT, the actual message passing topology is not $\\tilde{A}$ .", "limitations": "", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 1, "contribution": 2, "strengths": "1. This paper tackles a new problem of gradient inversion attack on graphs. More importantly, gradient inversion attack on graphs is different from GIA for other types of data, in that graphs not only have feature vectors, but also have graph structures. \n2. This paper proposes a new evaluation metric to evaluate GIA on graphs, which would help future efforts in this field. At present, this research field is blank without any existing evaluation protocols, so the first such protocol or metric is nice to have.", "weaknesses": "1. The presentation of this paper requires significant improvements. The technical methodology of this paper is very hard to understand. \n\n- The abstract contains a redundant sentence 'Federated learning allows multiple parties to train collaborative while'. \n\n- It is suggested that the authors should clearly state the attack setting. For example, who is the attacker (server or client), what does the attacker know (model parameters, gradients, anything else). \n\n- The authors should revise the use of the term 'degree'. It is used simultaneously to describe 'the number of edges connected to a node', as well as 'the number of hops of a subgraph'. This makes the paper very confusing to read. The second usage of degree can be replaced to something like 'hop'. \n\n- For Theorem 3.1, the authors should define the concept of 'rowspan' and 'colspan', and briefly state the implication of the theorem. The same holds for Lemma 5.1. \n\n- It is not clear how to obtain $T_0$. \n\n2. This paper makes unrealistic assumptions about the problem and the data. \n\n- In Lemma 5.1, the authors assume that $\\tilde{A}$ is full rank. However, this is an unrealistic assumption, in that in practice, the adjacency matrix of most graphs are low-rank [1,2]. Therefore, for this Lemma to work, the authors either need to show that real-world graphs are almost full rank, or discuss what happens when the adjacency matrix is low-rank. \n\n- In Page 4, Lines 183-190, the authors say that 'we leverage that the degree of a node is a widely used node feature', and subsequently assume that the degree is a known knowledge. However, this is not always true. When the node features are bag-of-word vectors, word embeddings, etc., the assumption may not hold. It is suggested that the authors should at least explicitly state the assumption. \n\n- In Section 6.2, the authors say that 'we provide the attack with the correct number of nodes'. However, in practice, this is often not the case --- how can the attacker know the number of nodes before attacking? The authors should either justify the assumption, or discuss what happens when the attacker does not know the information. \n\n- In Section 5.1 and Figure 2, the authors show that the gluing operation actually merges the same node $v$ in two building blocks, and merge edges similarly. However, I did not quite understand how the information of 'two nodes in two different building blocks correspond to the same node' is obtained. The authors should state how to obtain this information, as in practice, all reconstructed nodes are not given node indices and are only identified with features (which are inaccurate by themselves). \n\n3. The authors' claim that the proposed method is 'exact' should be an overclaim. In fact, the proposed GRAIN can reconstruct 30-70% of all molecules (Table 1), which, in my opinion, is not sufficient to claim 'exact'. The authors should revise the claim to better fit the actual effectiveness of GRAIN.  \n\n[1] Graph Structure Learning for Robust Graph Neural Networks. KDD 2020\n\n[2] Learning social infectivity in sparse low-rank networks using multi-dimensional hawkes processes. AAAI 2013.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)