TL;DR
This paper introduces GRAIN, the first method capable of exactly reconstructing graph-structured data (like molecules or social networks) from gradients shared in federated learning. This is a significant privacy concern, as it demonstrates that even with gradient-only updates, sensitive graph data is not secure.
What Problem Does This Paper Address?
Federated learning (FL) aims to train machine learning models collaboratively across multiple clients without sharing their raw data. Instead, clients send model updates (gradients) to a central server. While this protects raw data, recent "gradient inversion attacks" have shown that it's sometimes possible to reconstruct the original client data from these gradients, especially for images and text. However, the privacy risks for graph-structured data, which is increasingly important in fields like drug discovery and social network analysis, remained largely unexplored. This paper addresses this gap by developing the first attack that can reconstruct both the structure and node features of graphs used in Graph Neural Networks (GNNs) within an FL setting.
Methods
GRAIN tackles the problem by leveraging the inherent structure of GNNs and their gradients. The core idea is to treat graph reconstruction as an inverse problem.
- Subgraph Recovery: GRAIN first identifies potential "building blocks" – small, k-hop neighborhoods within the graph. This is achieved by using a "span check" mechanism, which exploits the low-rank properties of GNN layer gradients. This allows the attacker to efficiently filter out impossible subgraphs from a large set of proposals.
- Graph Assembly: Once these building blocks are filtered and validated layer by layer, GRAIN uses a Depth-First Search (DFS) approach to stitch them together. This process involves intelligently "gluing" these building blocks, considering node features and degrees, to reconstruct the complete graph.
- Heuristics: The method incorporates heuristics, such as using node degrees and a uniqueness assumption for node features in certain network types, to significantly prune the search space and improve efficiency.
Datasets
The authors evaluated GRAIN on several real-world datasets:
- Chemical Datasets: Tox21, Clintox, and BBBP (representing molecules).
- Citation Networks: CiteSeer.
- Social Networks: Pokec.
Key Insights and Ideas
- GNNs are Not Privacy-Preserving for Graphs: The most critical insight is that even with gradient-only updates, GNNs do not inherently protect the privacy of graph-structured client data.
- Low-Rank Structure is Key: The attack heavily relies on the low-rank properties of GNN gradients, which allows for efficient filtering of potential subgraphs.
- Subgraph Assembly is Feasible: GRAIN demonstrates that by breaking down the problem into recovering and then assembling smaller graph components (building blocks), exact graph reconstruction is achievable.
- Node Features and Degrees are Crucial: The attack leverages information like node degrees and feature values, which are often implicitly or explicitly available to the FL server, to guide the reconstruction process.
Key Results
GRAIN achieves impressive reconstruction accuracy:
- Exact Reconstruction: Up to 80% of graphs can be reconstructed exactly on graph classification tasks.
- Partial Reconstruction: GRAIN significantly outperforms existing baselines in partial reconstruction, achieving up to 96% accuracy.
- Versatility: The method is shown to be robust across different GNN architectures (GCN, GAT), various datasets (chemical, citation, social), and different graph sizes.
- Efficiency: While computationally intensive, GRAIN is shown to be more efficient than some baselines, especially when using heuristics.
Limitations and Future Work
- Assumptions: GRAIN relies on specific assumptions:
- Node degree is available as a feature.
- The GNN architecture satisfies Assumption A.1 (local dependency of node embeddings).
- The number of nodes is less than the embedding dimension ($n < d'$).
- The adjacency matrix is high-rank (especially for GCNs, where this is not always true).
- Future Work: The authors suggest several directions:
- Relaxing the assumption of node degree availability.
- Improving computational efficiency to scale to larger graphs and higher node degrees.
- Adapting GRAIN to other GNN types and federated learning protocols (like Federated Averaging).
- Investigating potential defense mechanisms against such attacks.
Summary updated