GRAIN: Exact Graph Reconstruction from Gradients
Maria Drencheva, Ivo Petrov, Maximilian Baader, Dimitar I. Dimitrov, Martin Vechev, {maria.drencheva, ivo.petrov, dimitar.iliev.dimitrov}@insait.ai, {mbaader,martin.vechev}@inf.ethz.ch · 2025
Read GRAIN: Exact Graph Reconstruction from Gradients by Maria Drencheva, Ivo Petrov, Maximilian Baader, Dimitar I. Dimitrov, Martin Vechev, {maria.drencheva, ivo.petrov, dimitar.iliev.dimitrov}@insait.ai, {mbaader,martin.vechev}@inf.ethz.ch (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-01838.txt.
Introduction
Drencheva and co-authors break federated learning's privacy promise for graph data in a 2025 paper. Clients in federated setups share gradient updates instead of raw data, trusting the math to hide the source. Earlier attacks rebuilt text and images from those updates, but graphs were untested.
Their attack, GRAIN, rebuilds the client's graph exactly, structure and node features alike, in the honest-but-curious setting. It exploits the low-rank shape of graph network gradients to recover pieces of the graph, filters them, and stitches them whole. On molecular, citation, and social data it recovered up to 80 percent of graphs perfectly, far beyond the baseline.
Catalog record
| CREATOR | Maria Drencheva, Ivo Petrov, Maximilian Baader, Dimitar I. Dimitrov, Martin Vechev, {maria.drencheva, ivo.petrov, dimitar.iliev.dimitrov}@insait.ai, {mbaader,martin.vechev}@inf.ethz.ch |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 92 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2503-01838
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
GRAIN: Exact Graph Reconstruction from Gradients Maria Drencheva, Ivo Petrov, Maximilian Baader, Dimitar I. Dimitrov, Martin Vechev, {maria.drencheva, ivo.petrov, dimitar.iliev.dimitrov}@insait.ai, {mbaader,martin.vechev}@inf.ethz.ch 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 % 80\% of all graphs exactly, significantly outperforming the baseline, which achieves up to 20% correctly positioned nodes. 1 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., 2021 ; 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 et al., 2023 ) , text ( Petrov et al., 2024 ) , and tabular data ( Vero et al., 2023 ) was recently severely violated by the introduction of gradient inversion attacks in the honest-but-curious 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, no prior work investigated the vulnerability of GNNs to such attacks. This work: Gradient inversion attack on graphs In this work, we introduce the first gradient inversion attack on graphs called G raph R econstruction A lgorithm for In version of Gradients ( GRAIN ), specifically designed to attack GNNs by recovering both the graph structure and the node features. At the core of GRAIN is an efficient filtering mechanism to correctly identify likely subgraphs, which are then combined to reconstruct the entire graph. In particular, we leverage span checks to 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 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 reconstruction accuracies of up to 75% (exact) and 85% (partial) on chemical graph classification, 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. 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 . 1 1 1 https://github.com/insait-institute/GRAIN • A generalization of the theory presented by Petrov et al. (2024) facilitating an effective mechanism to recover individual feature vectors and thus enabling the use on 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 in realistic applications, as GRAIN often recovers clients’ graph data exactly. We believe this work is an important step to further quantify the risks of using private data in FL. 2 Related Work Gradient inversion attacks ( Zhu et al., 2019 ) , are attacks to Federated Learning that aim to infer the client’s private data from the FL 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 on the attack model, gradient inversion attacks are either malicious ( Boenisch et al., 2021 ; Fowl et al., 2022b ; Fowl et al., 2022a ; Chu et al., 2023 ; Wen et al., 2022 ) if the attacker can additionally manipulate the model weights sent to the clients, or honest-but-curious ( Zhu et al., 2019 ; Phong et al., 2018 ; Zhao et al., 2020 ; Geiping et al., 2020 ; Geng et al., 2021 ; Zhang et al., 2023 ; Li et al., 2022 ; Deng et al., 2021 ; Balunovic et al., 2022 ; Dimitrov et al., 2024 ; Petrov et al., 2024 ; 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 honest-but-curious attacks formulate gradient inversion as an optimization problem ( Zhao et al., 2020 ; Geiping et al., 2020 ; Yin et al., 2021 ; Geng et al., 2021 ; Zhang et al., 2023 ; Li et al., 2022 ; Deng et 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 in many domains like images ( Geiping et al., 2020 ; Yin et al., 2021 ; Geng et al., 2021 ; Zhang et al., 2023 ; Li et al., 2022 ) where the client data is continuous, it has been shown that the associated optimization 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 et 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., 2024 ) and discrete inputs ( Petrov et al., 2024 ) in certain neural architectures. Notably, DAGER ( Petrov et al., 2024 ) showed that when