Research map / Federated learning and privacy / Personalized and heterogeneous FL
GRAIN: Exact Graph Reconstruction from Gradients
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Presents GRAIN, the first exact gradient inversion attack on graph neural networks (GCN/GAT) that recovers both graph structure and node features from FedSGD gradients by span-check filtering and DFS graph building.
Problem
Gradient inversion attacks have not been studied for graph-structured client data in federated learning; recovering both discrete node features and adjacency structure from shared GNN gradients is hard for optimization-based methods.
Approach
Generalizes the DAGER span-check theory from linear layers to GNN layers, using the low-rank structure of GNN gradients to filter k-hop building blocks of the client graph, then reassembles the full graph via DFS guided by gradient matching, with a uniqueness heuristic for social/citation networks.
Key results
- GRAIN reconstructs up to 80% of graphs exactly (GCN/GAT on Tox21 FULL 68.0% GCN, 75.0% GAT), while the best baseline achieves 2.0% or less FULL on Tox21.
- On CiteSeer GAT, GRAIN achieves 61.0% FULL reconstruction versus 0% for DLG and TabLeak baselines.
- GRAIN scales to graphs up to n=60 nodes on Pokec using the node uniqueness heuristic, reconstructing 79.0% of Pokec graphs exactly for GAT.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use GRAIN instead of DLG with the input adjacency matrix | GCN gradient inversion · Tox21 | FULL: 1.0\pm0.2 -> 68.0\pm1.7 | Helped |
| Use GRAIN instead of DLG with the input adjacency matrix | GAT gradient inversion · Tox21 | FULL: 2.0 \pm 0.3 -> 75.0 \pm 1.8 | Helped |
| Use GRAIN instead of DLG | GCN gradient inversion · CiteSeer | FULL: 0.0\pm{0.0} -> 20.0\pm{0.8} | Helped |
| Use GRAIN instead of DLG | GAT gradient inversion · CiteSeer | FULL: 0.0\pm{0.0} -> 61.0\pm{1.6} | Helped |
| Use GRAIN instead of DLG with the input adjacency matrix | GCN gradient inversion · Pokec | FULL: 0.0\pm{0.0} -> 15.0\pm{0.8} | Helped |
| Use GRAIN instead of DLG with the input adjacency matrix | GAT gradient inversion · Pokec | FULL: 0.0\pm{0.0} -> 79.0\pm{1.8} | Helped |
| Add node degree to the feature set (ablation) | GRAIN · CiteSeer | FULL: 32.0\pm1.1 -> 61.0\pm1.6 | Helped |
| Add the node uniqueness heuristic (ablation) | GRAIN · CiteSeer | FULL: 44.0\pm 1.3 -> 61.0\pm1.6 | Helped |
| Replace ReLU with GELU (ablation) | GRAIN on GCN · Tox21 | FULL: 68.0\pm1.7 -> 61.0\pm1.6 | Hurt |
| Use a pre-trained model (ablation) | GRAIN on GCN · Tox21 | FULL: 68.0\pm1.7 -> 49.0\pm1.4 | Hurt |
| Use node classification with known labels (ablation) | GRAIN on GCN · Tox21 | FULL: 68.0\pm1.7 -> 66.0\pm 1.6 | Hurt |
Surprising findings
- Gradient matrix for GCN is often rank-deficient on small graphs, so exact recovery is harder for GCN than GAT; GAT results are consistently higher.
- GRAIN still reconstructs around 50% of molecules exactly on pre-trained models, where gradient inversion is expected to be harder.
Limitations
- Relies on assumptions: number of nodes smaller than embedding dimension, and all input node features discrete.
- Graph building times out (15 minutes) on large chemical graphs, reducing performance for graphs with 26+ nodes (5.1% FULL for GCN).
- Honest-but-curious FedSGD threat model with known architecture and feature semantics; GSM metric relies on approximate node matching.
Experimental setup
Datasets: Tox21 BBBP ClinTox CiteSeer Pokec
Benchmarks: Tox21 CiteSeer Pokec
Metrics: GSM-0 GSM-1 GSM-2 FULL exact reconstruction rate runtime
Baselines: DLG DLG +A TabLeak TabLeak +A
Builds on: DAGER DLG TabLeak
Closest papers by meaning
- Federated Graph Condensation with Information Bottleneck Principles (AAAI 2025 · similarity 0.88)
- SPEAR: Exact Gradient Inversion of Batches in Federated Learning (NeurIPS 2024 · similarity 0.88)
- GRAIN: Multi-Granular and Implicit Information Aggregation Graph Neural Network for Heterophilous Graphs (AAAI 2025 · similarity 0.88)
- DAGER: Exact Gradient Inversion for Large Language Models (NeurIPS 2024 · similarity 0.87)
- EAGLES: Towards Effective, Efficient, and Economical Federated Graph Learning via Unified Sparsification (ICML 2025 · similarity 0.87)
- Decoupled Subgraph Federated Learning (ICLR 2025 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.