GRAIN: Exact Graph Reconstruction from Gradients

Authors: Maria Drencheva, Ivo Petrov, Maximilian Baader, Dimitar Iliev Dimitrov, Martin Vechev
Primary area: alignment, fairness, safety, privacy, and societal considerations
Keywords: gradient leakage, gradient inversion, graph neural networks, federated learning, graph convolutional networks, gnn, gcn, attack, privacy, 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.

Decision: accept (poster)
Reviewer scores: 6, 5, 6, 6, 5

Reviews and discussion:
<thread>
creation date:
1729058190253

thread_type:
official_review

<thread_object>
creator: reviewer_t4xv

<content>
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.

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. 
2. 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. 

- The abstract contains a redundant sentence 'Federated learning allows multiple parties to train collaborative while'. 

- 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). 

- 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'. 

- 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. 

- It is not clear how to obtain $T_0$. 

2. This paper makes unrealistic assumptions about the problem and the data. 

- 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. 

- 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. 

- 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. 

- 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). 

3. 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.  

[1] Graph Structure Learning for Robust Graph Neural Networks. KDD 2020

[2] Learning social infectivity in sparse low-rank networks using multi-dimensional hawkes processes. AAAI 2013.

questions:
1. Please briefly explain the unclear parts stated in Weakness 1. 

2. Please briefly discuss how the assumptions in Weakness 2 hold in practice, and what will happen when they do not hold.   

3. 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?

4. 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}$ .
</content>
</thread_object>

</thread>
<thread>
creation date:
1729959183272

thread_type:
official_review

<thread_object>
creator: reviewer_5wij

<content>
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.

Overall, 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).

strengths:
1. Technical novelty.
2. Strong experimental results.
3. 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?

I 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.

Finally, 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.

For the experiments, the following should be addressed.

1.	It 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.

2.	For 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.

3.	As 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.

Minor comments:
1)	In the Abstract, there is redundancy in the first sentence (e.g. “Federated learning allows multiple parties to train collaboratively while only Federated learning…”).
2)	In the third line in 5.1, the symbol is a subset instead of an overlap.
3)	In 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.

questions:
See weaknesses.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730302925199

thread_type:
official_review

<thread_object>
creator: reviewer_hrgw

<content>
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.

In 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.

strengths:
1. As the authors mention, this paper addresses a crucial yet unexplored problem: gradient inversion attacks in graph federated learning.
2. 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.
3. This paper suggests future directions for gradient inversion attacks in the graph domain, as discussed in Section 7 (Limitations).
4. 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.  

2. 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.  

3. 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?

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).

2. As I mentioned in W1, I suggest that the authors provide additional evaluations on other categories of graph datasets.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730540975199

thread_type:
official_review

<thread_object>
creator: reviewer_d7q7

<content>
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.

strengths:
1. It is the first work that explores extracting the structure of a graph from gradients. 
2. 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.
2. 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.
3. 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.

[1] DAGER: Exact Gradient Inversion for Large Language Models.

questions:
see Weaknesses
</content>
</thread_object>

</thread>
<thread>
creation date:
1730609531139

thread_type:
official_review

<thread_object>
creator: reviewer_61n5

<content>
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.

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.
- A new metric is proposed to measure the similarity between graphs.
- 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.
- 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? 
- 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?
- 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?
- 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.


[1] Petrov, Ivo, et al. "DAGER: Exact Gradient Inversion for Large Language Models." arXiv preprint arXiv:2405.15586 (2024).

questions:
Please see Weaknesses.
</content>
</thread_object>

</thread>
<thread>
creation date:
1732286133544

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Main Response to ICLR 2025 Official Reviews

comment:
$\newcommand{\RO}{\textcolor{red}{61N5}}$$\newcommand{\Rt}{\textcolor{blue}{d7Q7}}$$\newcommand{\RTH}{\textcolor{green}{HRGw}}$$\newcommand{\RF}{\textcolor{purple}{5Wij}}$$\newcommand{\RFI}{\textcolor{orange}{t4xV}}$$\newcommand{\grad}[1]{{\tfrac{\partial\mathcal{L}}{\partial #1}}}$$\def\colspan{{\text{ColSpan}}}$We thank the reviewers for their valuable input, as we strongly believe that it has made our paper stronger. We are delighted to read that reviewers find gradient inversion attacks on graph neural networks an important ($\RTH$), unexplored($\RO, \Rt, \RTH$), and interesting($\RO$) topic, and that our results constitute a significant step toward understanding the privacy vulnerabilities of federated learning when applied to graph-structured data ($\RF$) and could inspire further research in the area ($\RO$). We are particularly pleased that the reviewers acknowledge the unique challenges posed by the gradient inversion problem in the context of graph-structured data, specifically recognising that recovering the graph structure is a fundamentally different task compared to traditional gradient inversion problems ($\Rt, \RTH$). Furthermore, we appreciate the reviewers' recognition of the importance of the graph reconstruction metric introduced ($\RO, \RFI$), facilitating future research in this area. Finally, we are happy to read that the reviewers found our experiments to be  'extensive' and 'rigorous' ($\RF$), noting that GRAIN ‘outperforms existing baseline attacks' ($\RO,\RF$) and demonstrates 'promising performance across different scenarios' ($\Rt$). In the response below, we provide answers to common and important questions. We plan to incorporate their answers in the next revision of this paper. Further, we would like communicate to the reviewers that we are currently crafting responses for their outstanding questions not addressed in the main response and will make them available shortly.
</content>
</thread_object>

</thread>
<thread>
creation date:
1733308227639

thread_type:
official_comment

<thread_object>
creator: authors

<content>
comment:
$\newcommand{\RO}{\textcolor{red}{61N5}}$$\newcommand{\Rt}{\textcolor{blue}{d7Q7}}$$\newcommand{\RTH}{\textcolor{green}{HRGw}}$$\newcommand{\RF}{\textcolor{purple}{5Wij}}$$\newcommand{\RFI}{\textcolor{orange}{t4xV}}$

We sincerely thank all five reviewers for their constructive comments and insightful questions, which have significantly helped us improve our work. We are particularly encouraged by the reviewers' recognition of our paper's strengths, as summarized below:

**Novelty**
- The problem is important ($\RTH$)
- The problem is unexplored ($\RO, \Rt, \RTH$)
- The problem is interesting and our paper can inspire further research in the area ($\RO$)
- Our paper is significant step toward understanding the privacy vulnerabilities of federated learning when applied to graph-structured data ($\RF$)
- GNN gradient inversion is fundamentally different task compared to traditional gradient inversion problems ($\Rt, \RTH$)
- The graph reconstruction metrics we introduced are important for future research in the area ($\RO, \RFI$)

**Extensive Experiments and Strong Results**
- The experiments are extensive and rigorous ($\RF$)
- GRAIN significantly outperform existing baseline attacks ($\RO,\RF$)
- GRAIN shows promising performance across different scenarios  ($\Rt$)

We acknowledge that our initial submission had areas for improvement. In response to the reviewers’ thorough reviews, we have provided the following additional information and experiments which we will incorporate in the next revision of the paper:

1. Better explanation of the contributions of our work, especially versus Petrov et al.

    - Clarified challenges specific to graph neural networks and how we solved them (**Q.1**)
    - Extended the theory introduced by Petrov et al. to handle GCN and GAT layers (**Q.1**)
    - Showed the role rank-deficiency of adjacency matrices plays in the reconstruction (**Q.5**)

2. Clarified the exact threat model assumed by GRAIN (**Q.3**), showing that in-degree features are not required for GRAIN to pose significant risks in practice (**Q.6**).
3. Provided an extended discussion regarding our novel graph reconstruction metrics (**Q.4**)

    - Added discussion on desired properties of the metrics
    - Added discussion on the motivation for our exact choice of metrics
    - Showed in a small user study that the metric results correlate well with human judgement

4. Showed that GRAIN is generic:

    - We showed that GRAIN is generic w.r.t. The GNN architectures it supports, showing that we can handle both GCNs (main paper) and GATs (**Q.5**)
    - We showed that GRAIN is generic w.r.t graph dataset types it supports, showing that it is applicable to chemical datasets (main paper), citation networks (**Q.5**), and social networks (**Q.8**)

5. Showed that GRAIN can scale:

    - In terms of number of input features (**Q.5**)
    - In terms of graph sizes (**Q.8**)
    - In terms of number of possible values per input feature (**Q1.7**)

6. Typos and paper clarifications:

    -  Provided a table summarizing all of our notations in the revised version of our paper (Table 5 in Appendix A).
    - Provided exhaustive clarifications to various technical questions the reviewers had, which we will incorporate in the next paper revision, alongside the reviewers’ other writing suggestions.

Once again, we deeply appreciate the valuable feedback and guidance provided by the reviewers.

Best regards,  
The authors
</content>
</thread_object>

</thread>


Metareview:
metareview:
This work introduces GRAIN, a gradient inversion attack tailored to Graph Convolutional Networks (GCNs) in federated learning settings. The primary contribution of this work lies in its tailoring these attacks to graph-structured data in federated learning, by devising a reconstruction attack capable of recovering both the graph structure and node features from shared gradient updates between clients and the server.

GRAIN employs a depth-first search strategy to identify subgraphs within gradients, iteratively filtering them by layer to reconstruct the full input graph. Notably, it leverages the low-rank structure of GCN layer updates and incorporates degree information in the features to generate the final prediction. Furthermore, the authors propose new evaluation metrics, such as GRAPH-N, to assess the similarity between reconstructed and original graphs in the context of graph gradient inversion attacks.

While the proposed method demonstrates promise, its effectiveness is limited when dealing with larger graphs, which is common for this type of attack. A more explicit connection to graph isomorphism would have strengthened the work, providing additional insights into the theoretical foundations of the task. Nevertheless, the reviewers' overall assessment was positive, and the paper has shown significant improvement following the rebuttal, which must make into the final version of the paper. Considering the borderline nature of this work, I recommend **acceptance if there is room**.

PS to authors: In one of the replies the authors said graph isomorphism is NP-complete. The paper also has a confusing statement: "Since exact matching of graphs is an NP-complete problem (Fortin, 1996)". The graph isomorphism problem belongs to NP but is not known to be either NP-complete or in P. In 2015, Babai found a quasipolynomial-time algorithm for graph isomorphism, running in exp((log n)^c) time for some constant c. If graph isomorphism were NP-complete, this would imply a collapse of the polynomial hierarchy. For the graph sizes considered in the paper, interactive color refinement works well and is reasonably fast.