A shot of Cognac to forget bad memories: Corrective Unlearning in GNNs

Authors: Varshita Kolipaka, Akshit Sinha, Debangan Mishra, Sumit Kumar, Arvindh Arun, Shashwat Goel, Ponnurangam Kumaraguru
Primary area: learning on graphs and other geometries & topologies
Keywords: Unlearning, Graphs, Graph Neural Networks, GNN, Attacks, Manipulations, Removal

Abstract:
Graph Neural Networks (GNNs) are increasingly being used for a variety of ML applications on graph data.  As graph data does not follow the independently and identically distributed (i.i.d) assumption, adversarial manipulations or incorrect data can propagate to other datapoints through message passing, deteriorating the model's performance. To allow model developers to remove the adverse effects of manipulated entities from a trained GNN, we study the recently formulated problem of _Corrective Unlearning_. We find that current graph unlearning methods fail to unlearn the effect of manipulations even when the whole manipulated set is known. We introduce a new graph unlearning method, ***Cognac***, which can unlearn the effect of the manipulation set even when only $5$\% of it is identified. It recovers most of the performance of a strong oracle with fully corrected training data, even beating retraining from scratch without the deletion set while being 8x more efficient. We hope our work guides GNN developers in fixing harmful effects due to issues in real-world data post-training.

Decision: reject
Reviewer scores: 5, 5, 5, 6

Reviews and discussion:
<thread>
creation date:
1729705484111

thread_type:
official_review

<thread_object>
creator: reviewer_bduh

<content>
summary:
This paper propose **Cognac** model to tackle corrective unlearning in Graph Neural Networks, efficiently removing the impact of adversarial manipulations, even when only 5% of the manipulation set is identified. It recovers most of the performance of an oracle trained with fully corrected data and is 8x more efficient than retraining from scratch. This makes **Cognac** effective in real-world scenarios with limited knowledge of corrupted data, enhancing GNN robustness post-training.

strengths:
(1) The proposed graph contrastive unlearning is a novel and interesting concept.

(2) The method presented in this paper is simple and effective, without introducing additional discriminative components.

weaknesses:
(1) The experiments in the paper are seriously insufficient. In the graph domain, there are numerous heterophilic and homophilic graphs, such as Wisconsin, Cornell, and Citeseer. The authors only demonstrate results on three graph datasets, which is clearly inadequate.

(2) There are some conceptually similar works [1], and the authors may need to provide a clearer comparison with these related works.

[1] The Heterophilic Snowflake Hypothesis: Training and Empowering GNNs for Heterophilic Graphs

questions:
please refer weakness
</content>
</thread_object>

</thread>
<thread>
creation date:
1730234498574

thread_type:
official_review

<thread_object>
creator: reviewer_a7wi

<content>
summary:
This paper introduces *Cognac*, a corrective unlearning framework designed for Graph Neural Networks (GNNs) to mitigate the adverse effects of manipulated data, even when only a small subset of compromised nodes or edges is identified. Cognac combines two key components: (1) *Contrastive Unlearning on Graph Neighborhoods* (CoGN), which minimizes the influence of manipulated nodes on neighboring nodes via contrastive learning, and (2) *Ascent-Descent Decoupled* (AC DC) gradient optimization, which unlearns harmful labels by alternating between ascent and descent steps. This method effectively reduces adversarial impact while maintaining efficiency and scalability.

strengths:
1. Cognac’s integration of CoGN and AC DC components offers an innovative approach to corrective unlearning in GNNs, utilizing contrastive learning and decoupled optimization to handle the unique challenges posed by graph-structured data.
2. The framework demonstrates strong performance, achieving effective unlearning even when only 5% of manipulated data is identified, thus substantially lowering the typical data requirement for effective unlearning.
3. The experiments are comprehensive, covering various manipulation types, model types, and datasets. The paper’s ablation studies and visualizations provide clear insights into Cognac’s efficacy and the mechanisms behind it.

weaknesses:
1. The evaluation metrics (ACC_aff and ACC_rem) mentioned in Lines 175–184, Page 4 differ from traditional accuracy metrics, which directly assess model performance on the original data. Does this mean that the model’s performance on the original data was not evaluated? Or does it imply that naive unlearning performance metrics were excluded? For clarity and comprehensive understanding, I suggest including results from standard unlearning metrics for comparison, even if they may not be favorable for the proposed method. Additionally, if ACC_aff and ACC_rem are novel metrics introduced by the paper, please clarify their originality, or otherwise include citations clearly defined in Lines 175–184.
2. The paper could benefit from a more detailed discussion on why malicious node additions degrade GNN performance. While related studies are referenced, incorporating recent studies would provide a more robust context [1, 2, 3, 4].
3. Correct the typo “th” to “the” in Line 432, Page 9.

**References for Additional Context**:
- [1] *Graph Robustness Benchmark: Benchmarking the Adversarial Robustness of Graph Machine Learning*, NeurIPS 2021, Datasets and Benchmarks Track.
- [2] *Mitigating Emergent Robustness Degradation on Graphs while Scaling Up*, ICLR 2024.
- [3] *Chasing All-Round Graph Representation Robustness: Model, Training, and Optimization*, ICLR 2023.
- [4] *Characterizing the Influence of Graph Elements*, ICLR 2023.

questions:
See Weaknesses Section.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730260340147

thread_type:
official_review

<thread_object>
creator: reviewer_lzxz

<content>
summary:
This work study the corrective unlearning problem for GNNs, where model developers try to remove the adverse effects of manipulated training data from a trained GNN, with realistically only a fraction of it identified for deletion. The authors introduce a new graph unlearning method, Cognac, which can unlearn the effect of the manipulation set even when only 5% of it is identified.

strengths:
1. The authors provide a coherent story.
2. Empirical studies on the benchmark dataset are comprehensive.

weaknesses:
1. When identifying the affected nodes, the inverse features need to be computed. What is the inverse features? The authors then choose the top K% nodes with the largest logit change. How will the chosen nodes influence the results? I suggest the authors provide empirical analysis of the K%. 
2. When calculating the logits change, should the GNN be trained well? I suggest the authors provide more analysis of how the GNN's performance influence on the logits change.
3. The algorithm has two optimization steps. How about the convergence of the algorithm? How to set the parameters of the optimizer?
4. The proposed method lacks justification. I suggest the authors theoretically analyze why selecting the top K% nodes with largest logit change and using the contrastive unlearning objective work.

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

</thread>
<thread>
creation date:
1730351397767

thread_type:
official_review

<thread_object>
creator: reviewer_47hj

<content>
summary:
This paper tackles Corrective Unlearning in Graph Neural Networks (GNNs) to counter the spread of manipulated data effects. Existing methods fall short, even with complete knowledge of manipulated data. The proposed method, Cognac, effectively reduces manipulation impacts with only partial information (5% of the manipulated set), restoring most of the ideal model’s performance and surpassing retraining efficiency by 8 times.

strengths:
1. The paper is well-written and easy to follow.
2. This paper studies an interesting problem in the graph domain.
3. The motivation to identify most affected nodes make sense.

weaknesses:
1. The experiments use GCN or GAT as backbones. Suppose we have a two-layer GNN; in that case, a node will only impact its 2-hop neighbors through message passing. This makes it confusing why, in Sec 4.1, the authors propose using output logits change as an indicator to find the most affected node.
2. I am concerned about updating the model with Eq. (2). If we have a large number of nodes to unlearn, I believe gradient ascent on $S_f$ would significantly reduce model utility. Could the authors add an experiment to verify this?
3. The experiments are not comprehensive, as they only focus on small graph datasets.

questions:
please refer to weakness
</content>
</thread_object>

</thread>
<thread>
creation date:
1732139636992

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Summary of Paper Revision

comment:
We thank all reviewers for their constructive feedback.  We have responded to each reviewer individually, and below, we also summarise the updates to our paper including additional results and recommended writing changes.

---

**Section 2 (L110-115, Page 2):** We have added further context on graph robustness to include literature (citing the relevant literature pointed out in a review) on node injections and robust pretraining.

**Section 4 (L219-222, Page 5):**  We have restated the definition of ‘*inverse*’ features for clarity.

**Section 4 (L216-217, Page 5):** We have clarified that the motivation for selecting top $k$% nodes is for efficiency.

**Limitations (L534-535, Page 10):** We acknowledge our work's lack of theoretical guarantees.

**Limitations (L524-525, Page 10):** We have acknowledged that we, like most of the existing graph unlearning literature, focus on homophilic graphs, and have cited the suggested reference for context on heterophilic GNN literature.

**Table 7 (Appendix F, Page 19):** We have added an experiment to show the performance of *Cognac* and the best-performing baselines when $25$% of the training data is manipulated, and observe that *Cognac* still outperforms all baselines.

**Figure 10 (Appendix G, Page 20):** We have added 3 more large datasets, and evaluated *Cognac* and best-performing baselines on the binary label flip attack, and we observe that *Cognac* still outperforms the baselines in most of the settings and matches Oracle’s performance in the new datasets. **Table 8:** provides details about these datasets. 

**Figure 11 (Appendix H, Page 20):** We plot and discuss the convergence of the different optimization steps in our algorithm.

**Figure 12 (Appendix I, Page 21):** We observe that the well-trained-ness of the GNN used for getting the top $k$% affected nodes does not influence the $Acc_{aff}$ with any clear trend. As a sanity check, we also show that selecting the top $k$% affected still achieves a higher $Acc_{aff}$ than while choosing random $k$% nodes in the n-hop neighbourhood.

**Figure 13 (Appendix I, Page 21):** We show that using a larger fraction of the $n$-hop neighbourhood (apart from the top $k$% chosen by our method) for contrastive unlearning does not lead to better unlearning performance while adding computational cost.
</content>
</thread_object>

</thread>
<thread>
creation date:
1733178772497

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Summary of Discussion Phase

comment:
Dear Reviewers and ACs,

Thank you for your thorough reviews. We would be happy to provide any further clarifications. We are delighted to note that reviewers find that:

**Contribution**

- The proposed method, *Cognac*, presents a novel and innovative approach to graph unlearning (Reviewers `bduh`, `A7wi`), which is an interesting, important, and well-motivated problem in the graph domain (Reviewer `47hj`).
- *Cognac* effectively reduces adversarial impact while maintaining efficiency and scalability (Reviewer `A7wi`) while being simple and effective (Reviewer `bduh`).
- *Cognac* restores most of the ideal model’s performance, surpassing retraining efficiency by 8 times (Reviewers `47hj`, `bduh`) even with only 5% identified manipulated data (Reviewers `A7wi`, `bduh`, `47hj`, `LzxZ`) across datasets and manipulation types.

**Soundness**

- The empirical studies are comprehensive, covering various manipulation types, model types, and benchmark datasets (Reviewers `LzxZ`, `A7wi`).
- The ablations and visualisations offers clear insights into *Cognac*'s efficacy and mechanisms (Reviewer `A7wi`).

**Presentation**

- The narrative is coherent (Reviewer `LzxZ`), the paper is well-written and easy to follow (Reviewer `47hj`).

---

The reviewers’ feedback has allowed us to improve our manuscript through added breadth in datasets, ablations, and writing changes. Here is how we resolved their initial concerns:

- **Experiments on 4 new datasets, including large scale** (Reviewers `47hj`, `bduh`), **and** **large deletion set sizes** (Reviewer `47hj`): We ran experiments on Computers, Physics, DBLP, and the much larger OGB-arXiv (1.1M edges). Our results demonstrate that *Cognac*'s advantages hold at scale **(Figure 10, Table 9)**, with robust unlearning even at higher fractions of manipulated samples **(Table 7)**.
- **Affected neighbour selection** (Reviewers `47hj`, `LzxZ`): We added ablations that confirm that our design choices for this, while simple and computationally cheaper, enjoy the same performance as using the entire $n$-hop neighbourhood **(Figure 13)** and robustly work even if the original GNN was under-trained **(Figure 12)**. We also improved the description of neighbourhood selection **(Section 4)**.
- **Positioning with respect to related work** (Reviewers `A7wi`, `bduh`): We clarified that we used established evaluation metrics for corrective unlearning as done in prior work (**Section 3)**. We incorporated studies on graph robustness **(Section 2)**, and acknowledged we focus on empirical performance on homophilic graph datasets **(Section 7)**.
- **Convergence analysis** (Reviewer `LzxZ`): We confirmed different components of our method converge as expected **(Figure 11)**.
</content>
</thread_object>

</thread>
<thread>
creation date:
1733271893062

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Clarifying Contributions

comment:
Dear ACs and Senior ACs,

At the end of the discussion phase, Reviewer `LzXz` wrote that *“this work primarily applies corrective unlearning from existing papers directly to graph setting, lacking deeper insights into the field”.* Before we had a chance to respond, Reviewer `47Hj` mentioned *“I agree with reviewer LzxZ”*, citing this as the reason the paper is *“below the acceptance bar”* of ICLR. We strongly disagree with this characterization due to the following reasons,

1. **There are no existing corrective unlearning methods we could directly apply:** The paper highlighting Corrective Unlearning as a problem was released as a pre-print in February 2024 [[Arxiv]](https://arxiv.org/abs/2402.14015), and was only published in October 2024 [[TMLR]](https://openreview.net/forum?id=v8enu4jP9B). We are unaware of any strong solutions to this problem, and are curious to know which existing papers Reviewer `LzxZ` thinks we directly apply to the graph setting. Our proposed method does not even have a direct analogue for image classification or LLMs where corrective unlearning methods [1, 2] have been proposed before, as it has a graph-specific component (Reviewer `A7wi` characterizes this well). Even for components like Ascent and Descent, which are used in many unlearning methods, we adapt them to our setting by making a modification, which leads to 20% unlearning improvements, as shown in Section 6.3.
2. **To even study corrective unlearning on graphs, we had to make important adaptations:** We could not trivially apply attacks from existing corrective unlearning works on images directly to graph data due to its fundamentally different nature (non-i.i.d structure and different features). So, we formulate two effective attacks tailored for both node and edge unlearning (a concept not applicable to images) inspired by the interclass confusion attack and observe that existing graph unlearning methods perform poorly on unlearning poisons, even when provided with complete knowledge about the manipulated data as shown in Section 6.1.
3. **We achieved unprecedented performance for corrective unlearning (surpassing retraining with 5% manipulated data):** No existing unlearning method (across domains) has been shown to be able to remove interclass confusion style attacks in the corrective setting. Our method, *Cognac*, was not only able to achieve that, but also beat retraining in some cases, which is generally considered a gold standard in unlearning (including graph unlearning) as shown in Section 6.1. *Cognac* is thus not only SOTA by huge margins, but also pushes the frontier of what was thought as possible.
4. **We extensively showed deeper insights for unlearning and dealing with manipulated graph data:** In Sections 6.1 and 6.2, we provide insights beyond establishing *Cognac* as SOTA in graph unlearning. We demonstrate that leveraging negative information about affected nodes can help outperform retraining from scratch, often considered the gold standard. Additionally, we analyze a counterintuitive phenomenon where unlearning performance declines as more manipulated samples are identified, showing in Table 3 that retaining node structure significantly improves unlearning. This highlights a key insight: unlike traditional graph unlearning, removing nodes is not always the optimal approach for addressing manipulations.

We are confident our work is a meaningful contribution to the field. We sincerely hope there is room in ICLR for papers that: a) Are the first to study an important problem of increasing interest (corrective unlearning), in an important domain (graph ML) b) Propose a method that is not only SOTA across datasets and evaluations (See Figures 2, 10, Table 9), but also sometimes beats what is considered the gold standard (retraining) while being 8x more efficient c) Have comprehensive ablations and justification for design choices (as highlighted by Reviewer `A7wi`, and further through incorporating all experiments suggested by Reviewers `LzxZ` and `47Hj`, which only reinforced our final design choices).

---

[1] Stefan Schoepf, Jack Foster, Alexandra Brintrup (2024). [Potion: Towards Poison Unlearning](https://openreview.net/forum?id=4eSiRnWWaF). *Journal of Data-Centric Machine Learning Research.*

[2] Li, N., et al. (2024). [The WMDP Benchmark: Measuring and Reducing Malicious Use with Unlearning](https://proceedings.mlr.press/v235/li24bc.html). *Proceedings of the 41st International Conference on Machine Learning*, in *Proceedings of Machine Learning Research*.
</content>
</thread_object>

</thread>


Metareview:
metareview:
**(a) Scientific Claims and Findings:**
The paper introduces Cognac, a novel method designed to mitigate the adverse effects of manipulated or incorrect data in Graph Neural Networks (GNNs). Given that graph data often violates the independently and identically distributed (i.i.d.) assumption, adversarial manipulations can propagate through message passing, degrading model performance. Cognac addresses this challenge by enabling corrective unlearning, effectively removing the influence of manipulated entities from a trained GNN. Notably, Cognac can unlearn the effects even when only 5% of the manipulated set is identified, achieving performance close to an oracle with fully corrected training data. It outperforms retraining from scratch without the deletion set while being eight times more efficient.

**(b) Strengths:**
* Innovative Unlearning Method: Cognac presents a novel approach to corrective unlearning in GNNs, addressing a critical need to mitigate the impact of adversarial manipulations or incorrect data. In comparison to related literature, it has to overcome additional challenges like the fact that samples (nodes) are not iid.
* Efficiency: The method demonstrates efficiency, being eight times faster than retraining from scratch, which can be advantageous in practical large-scale applications. 
* Partial Identification Capability: Cognac's ability to effectively unlearn with only 5% of the manipulated set identified showcases its robustness and practicality in real-world scenarios where full identification may not be feasible. In a few cases, Cognac also improves over retraining from scratch.

**(c) Weaknesses:**
* Limited Theoretical Analysis: The paper lacks a comprehensive theoretical foundation explaining why Cognac performs effectively, which could strengthen the understanding and acceptance of the method.
* Clarity on Innovation: What were the specific challenges in transferring unlearning ideas to GNNs? How is the fact that samples are non-iid actually addressed as an algorithmic innovation?
* Motivation: To which degree is computational efficiency a relevant concern for GNNs. For most of the studied datasets, retraining the model from scratch on the cleaned dataset is well feasible. The more interesting question is: How/why could cognac lead to improved generalization performance in comparison? (Yet, this is seldomly the case.)
* Scalability Concerns: While Cognac is more efficient than retraining, the paper does not provide a detailed analysis of its scalability to very large graphs, where this increased computational efficiency would actually be a relevant concern. (Only experiments on ogbn were added during the rebuttal.)
* Comparative Evaluation: The submission would benefit from a more extensive comparison with existing unlearning methods in GNNs to clearly highlight Cognac's advantages and potential limitations on a wider set of datasets. Even though four more datasets (Computers, Physics, DBLP, and the much larger OGB-arXiv) were added during the rebuttal, the experiments fall short in comparison with standard GNN evaluations. A comparison even on a conceptual level could provide an intuition of the main idea why Cognac should succeed/improve over competitors. 

**(d) Reasons for Rejection:**
After thorough evaluation, the decision to reject the paper is based on the following considerations:
1. Insufficient Justification: The absence of a detailed theoretical analysis undermines the understanding of Cognac's underlying mechanisms and its effectiveness in corrective unlearning. The algorithmic contribution that overcomes GNN specific challenges should be highlighted more. Furthermore, when does the computational speed-up justify the often inferior performance to retraining from scratch?
2. Scalability Uncertainty: The lack of discussion regarding the method's scalability to large-scale graphs and run-time assessments raises concerns about its applicability in practical, real-world settings.
3. Inadequate Comparative Analysis: The paper does not sufficiently compare Cognac with existing unlearning methods (on a conceptual and empirical level), making it challenging to assess its relative performance and contributions to the field. Experiments for heterophilic cases should be added as well. GATs can also work well in this setting and the authors designed Cognac for this architecture.
Addressing these issues would enhance the paper's contribution and its potential for future acceptance.