TL;DR
GRAIN is the first exact gradient inversion attack designed for Graph Neural Networks (GNNs) in a federated learning setting. By exploiting the low-rank structure of GNN gradients, it successfully recovers both the discrete graph topology and node features, achieving up to 80% exact reconstruction. This work demonstrates that simply sharing gradients does not guarantee data privacy for graph-structured data.
What Problem Does This Paper Address?
Federated Learning (FL) is widely adopted for privacy-sensitive applications because it allows multiple clients to collaboratively train a model by sharing only gradient updates instead of raw data. However, recent "gradient inversion attacks" have shattered this privacy assumption by showing that private images, text, and tabular data can be precisely reconstructed from these shared gradients.
Until now, Graph Neural Networks (GNNs)—used for complex data like social networks, molecules, and citation webs—were thought to be relatively safe. Reconstructing graphs from gradients is uniquely challenging due to the tight interdependence between the discrete graph structure (the adjacency matrix $A$) and the node features (matrix $X$). Traditional optimization-based attacks fail here because they cannot easily handle discrete graph topologies. This paper introduces GRAIN to close this gap and evaluate the true privacy risks of GNNs in FL.
Methods
GRAIN operates under an "honest-but-curious" threat model where a malicious FL server passively observes gradients to steal client data. The algorithm breaks down the reconstruction into two main phases:
- Subgraph Filtering: GRAIN leverages the mathematical property that GNN layer updates are rank-deficient. It extends prior text-reconstruction theory to GNNs, using "span checks" to filter out impossible node feature combinations. It recovers 0-hop nodes feature-by-feature, then iteratively "glues" them into larger $l$-hop local neighborhoods (subgraphs) and filters them layer-by-layer using the model's gradients.
- Graph Building: Once a clean set of valid local subgraphs is filtered, GRAIN uses a Depth-First Search (DFS) algorithm to assemble them into the full, global graph. To make this combinatorial problem tractable, it employs smart heuristics, such as using node degrees (a common GNN feature) and a "node uniqueness" heuristic for domains like social networks where node features rarely duplicate.
Datasets
The authors evaluated GRAIN across three distinct domains:
- Chemical/Molecular Data: Tox21, Clintox, and BBBP from the MoleculeNet benchmark, where molecules are represented as graphs of atoms.
- Citation Networks: The CiteSeer dataset, representing scientific publications and their citation links.
- Social Networks: The Pokec dataset, containing 1.6 million users and their friendship connections.
While no new datasets were introduced, the authors proposed a new evaluation framework called Graph Similarity Metrics (GSM) to rigorously measure the quality of recovered graph structures across varying neighborhood sizes while remaining invariant to graph isomorphism.
Key Insights and Ideas
- GATs are more vulnerable than GCNs: Graph Attention Networks (GATs) compute intermediate gradients that are almost always full-rank. This makes the span check filtering incredibly precise, allowing GRAIN to easily isolate the true input data.
- Rank-deficiency is a double-edged sword: While Graph Convolutional Networks (GCNs) often have rank-deficient adjacency matrices (which theoretically limits full recovery), GRAIN can still recover the vast majority of node features because the mathematical conditions for span checks hold true for most nodes as the graph grows.
- Exploiting Domain Heuristics: In social or citation networks, node features are often unique. GRAIN leverages this "uniqueness heuristic" to automatically overlap nodes with identical features during the DFS phase, drastically reducing the search space and allowing the attack to scale to larger graphs (up to 60 nodes).
Key Results
- Exact Reconstruction: GRAIN successfully reconstructed up to 80% of all molecular graphs exactly (both structure and features), whereas baseline attacks like DLG and TabLeak achieved virtually 0% to 2% exact recovery.
- Partial Reconstruction: On the Pokec social network dataset, GRAIN achieved a partial reconstruction score (GSM-0) of up to 97.2% for GAT architectures.
- Robustness: The attack proved highly robust against architectural variations, maintaining high accuracy across different GNN depths (2 to 4 layers), hidden dimensions, and activation functions (ReLU vs. GELU).
Limitations and Future Work
- Node Degree Dependency: The current implementation of GRAIN assumes that node degrees are known or included as a node feature, which helps guide the DFS graph assembly. Relaxing this assumption is a key area for future work.
- Scalability Limits: Without data-specific heuristics (like node uniqueness), the DFS phase can hit timeouts (set to 15 minutes in the paper) on larger or highly dense graphs due to combinatorial explosion.
- Architectural Constraints: The attack requires the number of nodes ($n$) to be smaller than the hidden embedding dimension ($d'$) to exploit the low-rank nature of the gradients. It also currently only supports GCN and GAT architectures.
Summary updated