A Cognac Shot To Forget Bad Memories: Corrective Unlearning for Graph Neural Networks
Authors: Varshita Kolipaka
Akshit Sinha
Debangan Mishra
Sumit Kumar
Arvindh Arun
Shashwat Goel
Ponnurangam Kumaraguru
Venue: ICML 2025 poster (2025)
Keywords: Machine Unlearning
Graphs
Graph Neural Networks
GNN
Attacks
Manipulations
Removal
Primary area: deep_learning->graph_neural_networks
TL;DR: We propose Cognac, a method for unlearning adverse effects of manipulated data from GNNs. It achieves near Oracle performance with just 5% of the manipulated set is identified for deletion, beating retraining while being 8x efficient.

Abstract: Graph Neural Networks (GNNs) are increasingly being used for a variety of ML applications on graph data. Because graph data does not follow the independently and identically distributed *i.i.d.* assumption, adversarial manipulations or incorrect data can propagate to other data points through message passing, which deteriorates 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, and is $8$x more efficient while also scaling to large datasets. We hope our work assists GNN developers in mitigating harmful effects caused by issues in real-world data, post-training.

Graph Neural Networks (GNNs) are seeing widespread adoption across diverse domains, from recommender sys- tems to drug discovery (Wu et al., 2022; Zhang et al., 2022). Recently, GNNs have been scaled to large training sets for A Cognac Shot To Forget Bad Memories: Corrective Unlearning for Graph Neural Networks
Varshita Kolipaka" 1 Akshit Sinha"
Debangan Mishra Sumit Kumar'
Arvindh Arun 112 Shashwat Goel 134 Ponnurangam Kumaragura'
cogmac-gan-inlleaminngg.g..u.i.
pocrective-imleemmng--forrr
Abstract
various graph foundation models (Mao et al., 2024; Arun et al., 2025). However, in these large-scale settings, it is prohibitively expensive to verify the integrity of every sam- ple in the training data that can potentially affect desiderata like fairness (Konstantinov Lampert, 2022), robustness (Paleka & Sanyal, 2023: Günnemann, 2022), and accuracy (Sanyal al., 2021).
Graph Neural Networks (GNNs) are increasingly being used for a variety of ML. applications on graph data. Because graph data does not fol- low the independently and identically distributed (i.i.d)) assumption, adversarial manipulations or incorrect data can propagate to other data points through message passing, which deteriorates the model's 's performance. To allow model developers to remove the adverse effects of manipulated enti- ties from a trained GNN, we study the recently for- mulated 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 intro- duce a new graph unlearning method, Cognac, which can unlearn the effect of the manipulation set even when only 5% of it is identified. re- covers most of the performance of a strong oracle with fully corrected training data, even beating retraining from scratch without the deletion set, and is 8x more efficient while also scaling large datasets. We hope our work assists GNN develop- ers in mitigating harmful effects caused by issues in worldworld data, post-training.
Making the training process robust to minority populations (Günnemann, 2022; Jin et al., 2020) is challenging and can adversely affect fairness and accuracy (Sanyal et al., 2022). Consequently, model developers may want post-hoe ways to remove the adverse impact of manipulated training data if they observe problematic model behavior on specific dis- tributions of test-time inputs. Such approach follows the recent trend of using post-training interventions to ensure models behave in intended ways (Ouyang et al., 2022). Re- cently, Goel et al. (2024) formulated corrective unlearning as the challenge of removing adverse effects of manipulated data with access to only a representative subset for unlearn- ing while being agnostic to the type of manipulations. We study this problem in the context of GNNs, which face unique challenges due to the graph structure. The traditional assumption of independent and identically distributed (i.i..) samples does not hold for GNNs, as they use a message- passing mechanism that aggregates information from neigh- bors. This process makes GNNs vulnerable to adversarial perturbations, where modifying even few nodes can prop- agate changes across large portions of the graph and result in widespread changes in model predictions (Bojchevski & Günnemann, 2019b; Zügner et al., 2018) 8). Consequently, for GNNs to effectively unlcarn, they must remove the influence of manipulated entities on their neighbors.
1. Introduction
Corrective Unlearning is an emerging paradigm that focuses on removing the influence of arbitrary training data manip- ulations on trained model, using only representative subset of the manipulated data (Goel et al., 2024). In this work, we focus on the use of GNNs in node classification tasks, studying unlearning for targeted binary class confu- sion attacks (Lingam et al., 2024) on both edges and nodes. For edge unlearning, we evaluate the unlearning of spurious
'Equal contribution 'Equal advising. 'IIT Hyderabad Institute for AI, University of Stuttgart 'ELLIS Institute Tübingen 'Max Planck Institute for Intelligent Systems. Correspondence to: Varshita Kolipaka Evarshitak@rrscarrt @ersearch.iiit.ec <akshit, @ wttuents.iit..ac.i..
Akshit Sinha
Proceedings of the 4nnd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

A Cognac Shot To Forget Bad Memories: Corrective Unlcarning for Graph Neural Networks
Method:
Cognac
Training
After Unlearning
Alliciad Maie tani Boadon
Controstve Unieeming
Grape No geaouuooood
AC / DC
Dobiian Sei
heesinng Date
Loss Lots
Mfecldd Disibuttoo
Medzed Didtibution
800
Chenn iiriuttion
Clean Eudiibation
Accent
Dessent
Loss
Hodes
Abocied haudes.
UrBoaring
Nogal nodts
Aacest Stap
Model
Parsuring
erti Lnasariin
Pullng) in
Coovert Exp
Figure 1. Illustration of our method Cognac. Initially (Left), the model is trained on manipulated data (Devils), out of which only a subset is identified for deletion "Dark-red-devlly Our method alternates between two steps. (1) Identifying neighbors by the deletion set, which can include both nodes from the remaining data (light red) and unidentified manipulated nodes (Purple), and pushes their representation away from the delction set and toward other nodes in the ncighborhood. (2) We then perform ascent the deletion set labels and descent on the remaining data with separate optimizer instances. This cleanly separates the embeddings the affected classes (Right), recovering the accuracy on the affected distribution, and maintaining the remaining distribution.
edges that change the graph topology in a way that violates the homophily assumption that most GNNs rely on. For node unlearming, we utilize a label flip attack (Lingam et al., 2024) which is used as a classical graph adversarial attack, similar to the Interclass Confusion attack (Goel et al., 2022).
2. Corrective Unlearning for Graph Neural Networks
We now formulate the Corrective Unlearning problem for graph-structured, non-i.i.d data. We consider a graph G (V,E), where and & represent the constituent set of nodes and edges respectively. For each node V, V. there is corresponding feature vector X; and label V, with V (X, )). Consistent with prior work in unlearning on graphs (Wu et al., 2023a; Li et al., 2024c), we focus on semi-supervisee node classification using GNNs. GNNs use the message- paasagg-passingggg mechanism, where each node aggre- gates features from its immediate neighbors. The effect of this aggregation process propagates through multiple suc- cessive layers, effectively expanding the receptive field of each node with network depth. This architecture inherently exploits the principle of homophily, common property in many real-work graphs where nodes with similar features or labels are more likely to be connected than not.
First, we evaluate whether existing GNN unlearning meth- ods are effective in removing the impact of manipulated entities. Our findings reveal that these methods consistently fail, even when provided with a complete set of manipulated entities. We then propose our method, Cognac, which un- learns by alternating between two components, as illustrated in Figure 1. The first component Contrastive unlearning on Graph Neighborhoods (CoGN), finds affected neigh- bors of the known deletion set, updating the GNN weights using contrastive loss that pushes representations of the affected neighbors away from the deletion entities while staying close to other neighbors. The second component, AsCent DesCent de coupled (CC applies the classic i.i.d. unlearning method of gradient ascent on the deletion set and gradient descent on the retain set.
While assuming homophily is extremely useful for learning representations from graph data, annotation mistakes or ad- versarial manipulations that create dissimilar neighborhoods connect otherwise dissimilar nodes easily harm the learned representations (Zügner& & Günnemann, 2019). This motivates our study of post-hoc correction strategies like unlearning for GNNs. Following Goel et al. (2024), we adopt an adversarial formulation that subsumes correcting more benign mistakes.
Our proposed method shows promise for corrective unlearn- ing: we not only outperform retraining from scratch, the previously assumed gold standard for this task. but also re- cover most of the performance of an oracle (a model trained on the complete and correct data) while discovering as few as 5% the manipulated entities.
2

---

A Cognac Shot To Forget Bad Memories: Corrective Unlcarning for Graph Neural Networks
Adversary's Perspective. The adversary aims to reduce model accuracy on target distribution by manipulating parts of the clean training data G. This can be done in the following ways: (1) adding spurious edges E, result- ing in E" = & U E; or (2) manipulating node information, V = (V), where fm manipulates a subset of nodes by changing their features or labels. We define Sm as the set of manipulated entities. which can be either the manipulated subset of nodes or the added spurious edges E. The final manipulated graph is denoted as G EV"
to explicitly state which data distribution accuracy is mea- sured. In Section 4, we further specify what the "affected distribution" and "remaining entities" are for the different evaluation types we study.
Goal, An ideal corrective unlearning method should have high Accaff even when a small fraction of manipulated set (Sm) is identified for deletion (5y) without big drops in Accrem. all while being computationally efficient.
3. Our Method: Cognac
Unlearner's Perspective. After training, model develop- ers may observe that desired properties like fairness and robustness are compromised in the trained model M. which can be modeled as lower accuracy on some data distribu- tions. The objective, then, is to remove the influence of the manipulated training data Sm on the affected distribution while maintaining performance on the remaining entities. By utilizing data monitoring strategies on subset of the training data or using incorrect data detection techniques like (Northcutt et al., 2021), it may be possible to identify a part of the manipulated entities S S Sm- For unlearn- ing to be feasible, S must be a representative subset of S.. We only assume the type of affected entity (edges or nodes) is known to the model developer, but do not assume any knowledge about the nature of manipulation. An un- learning method UMM,S, G') is then used to mitigate the adverse effects of S,.. ideally by improving the accuracy on unseen samples from the affected distribution. An effec- tive unlearning method should remove the impact of certain training data samples without degrading performance on the rest of the data or incurring the cost of retraining from scratch. Moreover, while Retrain was previously considered a gold standard in privacy-oriente unlearning and graph unlearning, Goel et al. (2024) showed that when the whole manipulated set is not known, retraining on the remaining data can reinforce the manipulation, implying it's not a gold standard for corrective unlearning.
Our proposed unlearning method, Cognac, requires access to the underlying graph g', the known set of entities to be deleted Sy, and the original model M. We define Vy as the set of nodes whose influence is to be removed. For node unlearning, V/- Sy; for edge unlearning, Vy is the set of vertices connected to the edge set to be deleted. Manipulated data has two main adverse effects on the trained GNN: 1) Message passing can propagate the influence of the manipulated entities S,,, on their neighborhood, and 2) The layers learn transformations to fit potentially wrong labels in Sm.. Mitigating the effects of attacks first requires analysis of the impact of such attacks. The most general form of attack is Interclass Confusion (Goel et al., 2022), which we show entangles the representations of two classes, below.
Theorem 3.1. Let G = (V,E,X be a graph with node set V. edge set E, and features X. Let C2, C2 C V be two distinct classes with ground-truth labels yi E (C1, C2). Suppose an Interclass Confusion (IC) attack is applied.
Let (M ΦMd (C2) E Rd denote the mean embeddings of C1 and C2. and Di (Ct), Φs ( (C2)) be the Wasserstein-2 distance between their embedding distributions.
Then, there exists a degradation term A >> 0 such that:
E E(D((M((1)) S ST [DiD( (Ci) (M (Mi) (C2)) A
Metrics. To evaluate the performance of unlearning meth- ods, we use the metrics proposed by Goel et al. (2024):
Complete list of assumptions and attack details in Appendix A.3. We tackle these two problems using separate compo- nents CoGN and AC₁ DC.
1. Accaft: It measures the clean-label accuracy of test set samples from the affected distribution. This metric cap- tures the method's ability to correct the influence of the manipulated entities on unseen data through unlearning. As the affected distribution differs for each manipulation, we specify it when describing each evaluation.
3.1. Removing Effects on Neighbors with CoGN
The first question we address is: How can we remove the in- fluence of manipulated entities on their neighboring nodes? First, this requires us identify the nodes affected by the manipulations (Var) and then mitigate the influence their representations. Identifying affected nodes is challenging, as the impact of message passing from manipulated entities Sm depends on the interference from messages of other neighboring nodes. Therefore, we use an empirical estima- tion to identify the affected nodes from each entity in the
2. ACCrem: It is defined as the accuracy of the remain- ing entities. This metric measures whether the unlearning maintains model performance on clean entities.
The metrics Accai and Accrem were termed "Corrected Accuracy" (Acccorr) and "Retain Accuracy" (Accretain) re- spectively by Goel et al. (2024). We chose alternative names
3

---

A Cognac Shot To Forget Bad Memories: Corrective Unlcarning for Graph Neural Networks
deletion set. On these nodes, we then perform contrastive unlearning, simultaneously pushing the representations of the affected nodes away from nodes in V while keeping them close to other nodes in their neighborhood. We call this component Contrastive unlearning on Graph Neighbor- hoods (CoGN), formalized below.
Peatere lavenike
Forward GNN
Raekinng and Spleetion
3. 1. AFFECTED NODE IDENTIFICATION
To first identify the affected samples, Vatf, we first observe that any manipulated node V can only affect the repre- sentation of any other node E VVV, Vy in G' only if is part of the receptive field of v, widely known result for GNNS. Formally.
Figure 2. A toy example detailing Affected Node Identification.
(1) We first invert the features of the known manipulated node, (2)
We perform two forward passes through the GNN, one with the original feature vector and one with the inverted feature vector. (3) We compute the difference in output logits from both cases and take the top 2 nodes with the largest logit change, which in this case are nodes and B.
Lemma 3.2. Let G = E) be an undirected graph, and let (w) denote the I-hop neighborhood of node v. For a node E V. let (s) denote the n-hop neighborhood of defined recursively
{s} (*) (OE N())
in= 0,
3.1.2. CONTRASTIVE UNLEARNING
in > 0.
To remove the influence of the deletion set V, the af- fected nodes Vai identified in the previous step, we must ensure that our model maps the hidden representations of nodes in Vatr far away from that of nodes in V/ (Goel et al., 2024). However, satisfying this property alone will lead to unrestricted separation and damage the quality of learned representations. To achieve this balance and restore ho- mophily (Ma et al., 2022), we constrain Vatf to stay close to its unaffected neighbors Niv. \V/ Ypos, ensuring align- ment with the local structure while distancing from Vy. Formally, can state this as the following optimization problem over the parameters of GNN, which is necessary for corrective unlearning.
In an n-layer GNN, the representation in of node can affect the representations 2, of nodes only i E (s). For any v & (N"(s), by is independent of message passing effects of Zz.
The proof is provided in Appendix A.I. The main takeaway is that manipulations only propagate within n-hop neigh- borhood of poisoned nodes. This locality drastically reduces the search space for identifying affected nodes.
The second observation is that not all nodes in the n-hop neighborhood of the manipulated nodes may be affected enough by the attack, as some nodes are more robust to the perturbations than others (Gosch et al., 2023; Arun al., 2023). To find the most affected nodes, we employ a cheap and simple heuristic. We invert the features of e E Vy and select neighboring nodes where final output logits are changed the most. Formally, the inversion is performed by the transformation I - X, V v E Vy, leading to a new feature matrix X', where X, represents a -nneodigg vector. We then compute the difference in the original out- put logits M(x), and those obtained by on the new feature matrix, M(x') given by: 4x= = IMMx'') - -M())- The top k% nodes with the most change. 4x. are selected as the af- fected set of entities Van- A conceptual example illustrating the workings of Affected Node Identification is presented in Figure 2. Appendix E.2 varies our design choices, confirm- ing that we retain the same performance as using the entire n-hop neighborhood while being more efficient (Figure 9). Our method works robustly even if the original GNN was under-trained (Figure 8). Further, in Table 7 we also ablate the heuristic for identifying affected nodes against Cognac using MEGU's s sampling technique. We observe that our heuristic delivers over 25% higher and is 8x faster.
max "
(EVEVaEE PEVpon [2. 2n] - BUEVatt NEV, (Zo Zn
= =max (BoePariDEVoo.mey) 2o Zp Zu Zn
Equation I offers a direct way to enforce separation between positive and negative pairs, but it has notable shortcomings. In particular, it does not sufficiently penalize small margins, as only considers the raw similarity difference without emphasizing cases where 2/. Zp and = zn are nearly equal. This can lead to weak separation and reduced robustness, es- pecially when positive and negative embeddings are closely aligned. Additionally, the lack of non-linear scaling creates an uneven optimization landscape, increasing the risk of convergence issues. To overcome these limitations, we use log-based loss function that applies non-lineat sigmoid terms, providing stronger penalization for small margins and a probabilistic similarity interpretation (Hamilton et al., 2017). This enhances the separation between positive and negative pairs while ensuring smoother gradients for more stable optimization (Lee et al., 2024). Formally.
Lo.p.n = log(a (2.xz) xp)) - (-2f 2n))
(2)
4

---

A Cognac Shot To Forget Bad Memories: Corrective Unlcarning for Graph Neural Networks
Under assumptions of differentiability, convexity, and bounded gradients, can guarantee that optimizing this function achieves a better separation between the positive and negative dot products equivalent to Equation 1.
6000
4000
Value
Theorem 3.3. Ler O E Rd parameterize a GNN generat- ing embeddings Teo Zp.2z. 2n E I2* for triplets (v, p, nt). Let [()) = -E log (2, zp) + log ( 2n)] and S() = E [ 2p - 2 mm)
2000
0
22000
0
2
6
7
9
Then under the assumptions stated above, gradient descent on (()) with step size S I (where L is the Lipschitz constant of VoL) guarantees:
Epoch
Foatrve Dot Product
Difference
Negative Dot Producs
Contrastive Loes
S(0++1) S(()) V2
Figure 3. Empirical convergence of CoGN. The average positive and negative dot products across samples increase and decrease, respectively, over epochs, resulting in overall convergence.
and at convergence, S(0*) > S(0)).
The proof is presented in Appendix A.2. We also empirically validate this theorem for non-linear GNNs, with Figure 3 showing on the Cora dataset that the separation between the positive dot product and negative dot product monotonically increases as the loss converges.
leads better results. Thus, we call this component Ascent Descent dep coupled. Convergence of this formulation has been shown in previous works (Kurmanji et al., 2023). We show the empirical convergence of AC DC in Figure 7 present in Appendix E.
For our final method Cognac, we alternate steps of CoGN, which fixes representations of affected neighborhood nodes, and AC DC, which unlearns potentially wrong labels in- troduced by Sm. We also perform ablations in Section 5 (Table 3), showing that the individual components CoGN and AC; DC alone perform notably worse than our final method, suggesting the necessity of both components.
3.2. Unlearning Old Labels with DC
Next, we ask: Can we undo the effect of the task loss Lrask explicitly learning to fit the node representations of Sm to potentially wrong labels? We do this by performing gradi- ent ascent on Sy, which non-directionally maximizes the training loss with respect to the old labels. Ascent alone ag- gressively leads to arbitrary forgetting of useful information, so we counterbalance it by alternating with steps that min- imize the task loss on the remaining data. More precisely, we perform gradient ascent on V, and gradient descent on vr, iteratively on the original GNN M.
4. Experimental Setup
4.1. Benchmarking Details
We now describe design choices made for benchmarking. first specifying the datasets and architectures, and then out- lining how to ensure a fair comparison between methods.
La = -Lask (Vy), La = Craste (V,)
(3)
While variants of ascent on S and descent on remaining data have been studied for image classification (Kurmanji et al., 2023) and language models (Yao al., 2024), we find specific optimization strategy useful to achieve corrective unlearning on graphs. The challenge arises when Sy C Sm. as the remaining data could still contain manipulated entities, which we aim to avoid reinforcing. However, in realistic scenarios, the manipulated entities Sm typically are a small fraction of the training data, allowing us to mitigate their impact through ascent on the representative subset Sy.
Models and Datasets. We report results using the Graph Convolutional Network (GCN) (Kipf & Welling, 2017) architecture and evaluate the methods on ten benchmark datasets used in prior literature: Cora, PubMed, DBLP, Coauthor CS, Coauthor Physics, Amazon Photos (Pho- tos), Amazon Computers (Computers), CiteSeer (Cheng et al., 2023; Li et al., 2024c), and additionally CoraFull (Bo- jchevski & Günnemann, 2018) and OGB-arXiv (Wang et al., 2020). In Appendix D.1, we provide additional results on Graph Attention Network (GAT) (Veličković et al., 2018), 8). For each dataset, we extract the largest connected subgraph for our experiments. Dataset details, including the num- ber of classes, nodes, edges, and entities manipulated, are provided in Table 1 and Appendix B.
This requires a careful balance between ascent and descent, which can achieve by using two different optimizers and starting learning rates for these steps. This insight is similar to prior work in Generative Adversarial Networks (GANs) (Heusel et al., 2017). The starting learning rates for both ascent and descent are hyperparameters to be tuned, and usually, we find that a lower learning rate for ascent
Hyperparameter Tuning, Ensuring a fair comparison of unlearning methods can be tricky, as there are multiple desiderata: unlearning, maintaining utility, and computa-
5

---

A Cognac Shot To Forget Bad Memories: Corrective Unlcarning for Graph Neural Networks
ping labels between two targeted classes entangle their representations. Once again, the unlearning goal is to im- prove Accaff on the two targeted classes, while preserving performance, Accrem on the remaining classes.
Table Dataset statistics. our evaluations, we include citation networks, co-author networks, and co- co-purchase networks. The number of nodes and edges reported here refers to the entire dataset. From this, we use 60/20/20 split for train/validatiinn/ess.. The manipulation statistics are presented Table
4.3. Basclines
DATASET
CLASSES
NODES
EDGES
We evaluate four popular graph unlearning methods and adapt one popular i..d. unlearning method for graphs. For reference, we also report results for the Original model, Retrain, which trains new model without Sy, and Finetune, which continues training the poisoned model on data without Sy for additional epochs. Following Goel et al. (2024), we find that retraining from scratch is not the gold standard in corrective unlearning. Thus, we introduce Oracle, trained on the whole training set without manipulations, indicating an upper bound on what can be achieved. The Oracle has correct labels for the unlearning entities, information that the unlearning methods cannot access.
CORAFULL
70
18, 800
170,370
CORA
2,485
10, 138
CITESEER
6
2, 120
7,358
DBLP
4
16, 191
103, 826
PURMED
3
19, 717
88, 648
OGB-ARXIV
40
169, 343
1, 166, 243
CS
15
18, 333
163, 788
PHYSICS
34, 493
495, 924
PHOTOS
7, 487
238, 086
COMPUTERS
13, 381
191,556
tional efficiency, and hyperparameter tuning of the methods can particularly affect results on GNNs. We describe our efforts towards this in Appendix sections F. and F.2.
We choose five methods as baselines where unlearning incorrect data explicitly mo- tivates the technique. (1) GNNDelete (Cheng et al., 2023) adds deletion operator after each GNN layer and trains them using a loss function to randomize the prediction prob- abilities of deleted edges while preserving their local neigh- borhood representation, keeping the original GNN weights unchanged. (2) GIF (Wu al., 2023a) draws from closed- form solution for linear GNNs to measure the structural influence of deleted entities on their neighbors. Then, they provide estimated GNN parameter changes for unlearning using the inverse Hessian of the loss function. (3) MEGU (Li et al., 2024c) finds the highly influenced neighborhood (HIN) of the unlcarning entities and removes their influence over the HIN while maintaining predictive performance and forgetting the deletion set using combination of losses. (4) UrU (Tan et al., 2024) proposes zero-cost edge-unlearning by removing the edges to be deleted during inference for blocking message propagation from nodes linked to these edges. Finally, we include a popular unlearning method studied in i.i.d. classification settings. (5) SCRUB (Kur- manji et al., 2023) employs teacher-student framework with alternate steps of distillation away from the forget set and towards the retain set. For edge unlearning, we use SCRUB by taking the nodes connected to spuriously added edges as the forget set and the rest as the retain set.
Existing Unlearning Methods.
4.2. Evaluations
Given a fixed budget of samples to manipulate, ideal cor- rective unlearning evaluations should maximize the deteri- oration of model performance on the affected distribution, creating wide gap between clean and poisoned model per- formance to measure the progress of the unlearning method. We thus evaluate unlearning in the context of attacks that are not constrained by stealthiness. Lingam et al. (2024) show that binary label flip manipulation attacks, where a fraction of labels are swapped between two chosen classes, stronger than multi-class manipulations, theoretically and empirically, on GNNs. Building on this, we use two targeted attacks to evaluate corrective unlearning on graph data. Additionally, for completeness we also present results on a Feature Poisoning Attack, analogous to patch-based based backdoor attacks in image poisoning (Gu et al., 2017), in Appendix D.3.
Spurious Edge Addition. Prior GNN unlearning works (Wu al., 2023a; Li et al., 2024c) have evaluated adversarial edge attacks, but in an untargeted setting, making their evaluations weak. We, instead, simulate targeted adversarial edge insertions between nodes of two classes, violating homophily assumptions and entangling their representations. This models attacks like fake social connections (Bojehevski & Günnemann, 2019at knowledge graph manipulations (Xi et al., 2023; Zhang et al., 2019; Zhao et al., 2024). Unlearning aims to recover accuracy on the targeted classes Accoff while preserving performance on others Accrem-
5. Results & Discussion
We now report our main results comparing our method to existing methods across the manipulation types and datasets. Detailed method ablations and analyses of what can be achieved in this setting are reported in Appendix E.4. We also present consistent results on the GAT architecture in Appendix D.I. We show the robustness of Cognac to large
Label Manipulation. We implement the Interclass Confu- sion (IC) Test (Goel et al., 2022), by systematically swap-
6

---

A Cognac Shot To Forget Bad Memories: Corrective Unlcarning for Graph Neural Networks
Edge Unlearning
Node Unlearning
Plyedos
Utteleer
Phadoo
Uhaleer
0.5
Legend
0.0
0.
0.0
0.1
0.0
Cognae
0.1
1535"
8.00"
9ett
330
1075
1150
0.00
255
Cora
Retrain
38
0.5
0.0
Oradle
Accoff
36
Origiaal
0.1
0.6
0.0
1138
11.00
1.00
0030
0.23
12.5
110
0:37
1025
113
00000
1.70
1200
6:37
0337
10.3
0.00
1135
1330
015
GIF
Computers
Com
CS
Compuners
Clea
0.5
AC DC
0.5
SCRUD
0.7
0.7
GNNDellte
0.
0.0
MEGU
0.4
11.0
0.5
040
2.70
0.30
1000
0.70
1.00
0.00
3.55
3.00
100
0.00
0.50
0.00
1.00
0.00
1300
1,00
8.0
100
0.00
100
1200
1220
0.90
0.59
1.
S1 Sm
Fraction Identified For Deletion
Figure 4. Corrective Unlearning Results. We report the accuracy the affected classes Accart across different fractions of the manipulation set known for deletion (Sy/Sm), Baseline methods perform poorly, except for GNNDelete, which achieves reasonable unlearning performance in some settings. AC₁ DC and Finetune, despite not being graph-specific, perform much better. Cognac, which adds graph awareness to AC₁ DC, archives SOTA across datasets and corrective fractions, unlearning the effect of the manipulation with just 5% of the manipulation set known.
S sizes, showing strong performance even with 38.96% of total training nodes in Sy for the PubMed dataset.
ure 4, we can see across manipulation types and datasets that existing methods fail to improve Accuft even when the whole manipulation set is known. UtU fails to unlearn the effects of either of the attacks, as simply unlinking on the forward pass does not sufficiently counteract the influence neighbors and weights. Both SCRUB and MEGU use KL Divergence Loss term keep predictions on the re- maining data close to the original model, which could be detrimental when done unidentified manipulation set en- tities and other affected neighbors. Even though MEGU and GIF were evaluated on removing adversarial edges and GNNDelete also mentioned incorrect data as one of its key applications, they failed to recover performance when pre- sented with targeted data manipulation. Interestingly, de- spite extensive hyperparameter searches, they are beaten by methods with no special graph components: the best baselines are AC; DC and naive finetuning (Finetune) on the retain set: both achieve a performance similar to retraining in some of the evaluations.
Table Accuracy averaged across S5/Sm on remaining distri- bution relative to the Original model. We find prior methods, especially GNNDelete, lead to large drops in Accrem, while our methods Cognac and ACO DC minimize the loss Accrem-
METHOD
CS
CORA
EDGE
LABEL
EDGE
LABEL
ORIGINAL
90.6
89.6
61.2
61.4
ORACLE
+0.5
-0.7
RETRAIN
-1.4
-0.1
-2.4
-5.7
Cognac
-1.4
-0.4
-4.5
AC/DC DC
-0.7
-0.8
-2.2
0.8
GNNDELETE
-6.0
-1.9
-0.9
-8.4
GIF
-1.6
-0.9
-4.2
-0.6
MEGU
-0.5
-2.8
+0.0
6.5
UTU
+0.00
+0.0
+0.0
+0.0
SCRUB
-0.9
0.7
+0000
2. Corrective unlearning methods must perform better than Retrain. While both AC; DC and Finetune match Retrain, all of them still fall far behind the Oracle model's performance in most evaluations, and are not consistent enough. This scope for improvement motivates the design of our method which performs well across attacks, datasets, and fractions identified for deletion.
Figure 4 shows unlearning performance the test set for manipulated classes (Acc.t) upon varying the fraction of the manipulation set known for unlearning (Sy/Sm). Ta- ble 2 accompanies this, showing side-effects on utility.
Existing unlearning methods perform poorly even when |Syl |.m| Observing the rightmost points in Fig-

---

A Cognac Shot To Forget Bad Memories: Corrective Unlcarning for Graph Neural Networks
3. Cognac beats Retrain, and can sometimes match the Oracle's performance. We observe that Cognac con- sistently achieves state-of-the-art performance across all datasets and manipulations, convincingly and consistently beating existing graph methods, and often exceeds Retrain. Notably, Cognac occasionally even surpasses Oracle, our introduced gold standard, on multiple datasets and iden- tified fractions despite having access to less data (and unknown manipulated samples) than Oracle. In Table 3, we show how both components of Cognac complement each other. CoGN alone does not improve Accaft over the origi- nal model, showing that while it effectively moves affected nodes, it lacks signals from labels. Conversely, AC; DC alone achieves better performance than CoGN, but is still far from matching the Oracle. AC; DC weakens incorrect learning signals and preserves task-relevant representations, while CoGN steers affected nodes away from manipulated ones. This highlights the effectiveness of our contrastive approach in achieving robust unlearning.
OGB-Arxiv (Accar)
Poisoned
MEGU
0.7
0.6
0.5
0.4
0.00
0.25
0.50
0.75
1.00
Cognac
Orsele
Figure (a)
Figure (b)
Figure 5. (a) Results on a larger dataset, OGB-Arxiv, and (b) Visualization of hidden layer embeddings after unlearning on CS dataset for node unlearning. (a) On the OGB-Ars datasct, Cognac outperforms retraining from scratch by more than 10%, while most baselines fail to achieve any performance gains beyond the Original model. (b) The affected distribution embeddings (highlighted by red and blue) are fully entangled in the original trained model, while after unlearning with Cognac the embeddings are well separated and clustered, matching Oracle.
4. Cognac performs strongly even with only 5% of Sm known. Cognac effectively recovers most of the accuracy on the affected distribution even when only 5% of the ma- nipulated set is known. Notably, it outperforms Retrain in realistic scenarios where Sm is only partially known. We attribute this to Affected Neighborhood Identification, which leverages graph structure to infer manipulated nodes and edges beyond those explicitly identified. Additionally, CoGN plays a crucial role by pushing influenced neighbors away from the deletion set and aligning them with their un- affected neighbors, thereby correcting representations even for unknown manipulated samples.
fail to improve Accaff over the original model. Even as dataset size grows, Cognac effectively retains its advantage. demonstrating its scalability and robustness.
Overall, our work makes progress on the problem of correc- tive unlearning in graph neural networks with remarkably minimal training signal: the knowledge of as little as (5%) of the manipulation set Sm The visualization of the hidden GNN layer embeddings after unlearning (Figure 5 (b)) shows that Cognac. like the Oracle model, achieves clear clustering of the manipulated class data points, validating our theoretical results shown in Section 3.1.
achieve strong unlearning with
5. Cognac scales well to significantly larger datasets. We evaluate Cognac on OGB-Arxiv, a significantly larger dataset than our other benchmarks with 170, 000 nodes and over 1M edges, and observe that it continues to achieve strong performance. Despite the increased scale, Cognac maintains a substantial lead over Retrain across different fractions of S., (Figure 5 (a)), while the baseline methods
6. Related Work
Graph-based attacks, such as Sybil (Douceur, 2002) and link spam farms (Wu & Davison, 2005), have long affected the integrity of social networks and search engines. Recent works reveal that even tfateoof-the-ar GNN architectures are vulnerable to simple attacks on the trained models, which either manipulate existing edges and nodes inject new adversarial nodes (Sun et al., 2019; Dai et al., 2018; Zügner & Günnemann, 2019; Geisler et al., 2024), Parallelly, works have characterized the influence of specific nodes and edges that can guide such attacks (Chen et al., 2023). One strategy to mitigate the influence of such attacks is robust pretraining, such as using adversarial training (Yuan et al., 2024; Zhang et al., 2023). Post-hoc interventions like unlearning act as complementary layer of defense, helping model developers when attacks slip through and affect a trained model.
Table 3. Ablating both components of Cognac across datasets. CoGN alone does not improve Acesæt over the original model. Conversely, AC; DC alone achieves better performance than CoGN, but still far from matching the Oracle. These results show how both components are integral to Cognac's success.
METHOD
CS
CORA
Accaft
ACCrem
Accatt
AcCrem
ORIGINAL
41.3
89.8
51.4
60.6
ORACLE
90.1
90.0
71.1
60.7
CoGN
47.2
89.8
12.1
60.5
Removing the impact of manipulated entities begins with their identification (Brodley & Friedl, 1999), for which multiple strategies exist like data attribution (Ilyas et al.,
DC
67.2
86.6
59.9
61.3
Cognac
79.3
82.3
75.5
56.6
8

---

A Cognac Shot To Forget Bad Memories: Corrective Unlcarning for Graph Neural Networks
2022), adversarial detection, and automated or human-in- the-loop anomaly detection (Northcutt et al., 2021). While approaches like model debiasing and concept erasure (Fan et al., 2024; Belrose et al., 2023) can remove effects of iden- tified manipulations post-training, they require knowledge of the manipulation. In contrast, unlearning methods are par- ticularly valuable in adversarial settings where corruption effects may be deliberately obfuscated and impact multiple model behaviors simultaneously (Paleka & Sanyal, 2023).
fusion manipulations with access to little as 5% of the manipulated data. We hope this sparks interesting future work on developing stronger evaluations and theoretical understanding for graph corrective unlearning in the GNN Robustness and Machine Unlearning community.
A Acknowledgements
Varshita Kolipaka is grateful to be funded by IHUB-Data. Data. Arvindh Arun was funded by the CHIPS Joint Undertaking (JU) under grant agreement No. 101 140087 (SMARTY), and by the German Federal Ministry of Education and Re- search (BMBF) under the sub-project with the funding num- ber 16MEE0444, and acknowledges support from the Inter- national Max Planck Research School for Intelligent Sys- tems (IMPRS-IS) and the European Laboratory for Learning and Intelligent Systems (ELLIS) PhD programs.
Recently, machine unlearning has received newfound atten- tion beyond privacy applications (Pawelezyk et al., 2024; Schoepf et al., 2024; Li et al., 2024a;b). Goel et al. (2024) demonstrated the distinction between the Corrective and Privacy-oriented unlearning settings for i.i.d. classification tasks, emphasizing challenges when not all manipulated data is identified for unlearning.
Exact Unlearning arose in privacy applications, offering guaranteed removal of data influence through selective re- training (Chen et al., 2022b;a; Bourtoule et al., 2021). While perfect guarantees are valuable for privacy, the exponential cost of sequential deletions (Warnecke et al., 2023) becomes impractical as unlearning expands broader challenges like model correction and debiasing (Pawelezyk et al., 2024; Schoepf et al., 2024; Li et al., 2024a). This has driven the development of Inxxact Unlearning methods that balance ef- fectiveness with scalability, using either theoretical bounds for simple models (Chien et al., 2022; Wu et al., 2023b) or empirical validation for deep networks (Wu et al., 2023a; Cheng et al., 2023; Li et al.. 2024c). The recent formaliza- tion of Corrective Unlearning (Goel et al., 2024) opened crucial new direction: removing corruption effects with only partial identification of manipulated data. We tackle this challenge in graphs, where the non-i.i.d. nature of data (Said et al., 2023) results in the graph elements exerting a strong influence on other elements in their neighborhood.
The authors extend their appreciation to the members of the Precog research group, Shashwat Singh, Karuna Chandra, Pratyaksh Gautam, Prashant Kodali, and Makarand Tapaswi for helpful discussions and feedback.
Impact Statement
The increasing adoption of Graph Neural Networks (GNNs) in real-world applications raises concerns about fairness and safety, particularly in settings where biased data propagates through message passing or incorrect information influences high-stakes decisions. From a fairesss perspective, Cognac can be potentially used to mitigate the impact of biased social connections in recommender systems and hiring net- works, where unfair edges or annotations may reinforce discriminatory patterns. From a safety standpoint, GNNs are increasingly used in drug discovery and biomedical ap- plications, where incorrect relationships between molecular compounds or erroneous biological interactions could lead to misleading predictions. Corrective unlearning can help remove the influence of faulty training data adversari- ally inserted edges, improving the reliability of GNN-based scientific models without compromising efficiency.
7. Limitations and Conclusion
Our work addresses corrective unlearning for GNNs, focus- ing on removing the effects of manipulated training data when only a fraction is identified. As our method relies on the homophily assumption and is evaluated primarily on ho- mophilic datasets like previous works (Li et al., 2024c), it is left for future works expand this heterophilic datasets. While method does not guarantee successful unlearn- ing against arbitrary real-world attacks, our experiments suffice to show that existing unlearning methods struggle even with complete knowledge of manipulations, which is an unrealistic scenario.
References
Akiba, T., Sano, S., Yanase, T., Ohta, T., and Koyama, M. Optuna: A next-generation hyperparameter optimization framework. In Proceedings of the 25th ACM SIGKDD international conference on knowledge discovery & data mining, pp. 2223-2631, 2019.
Arun, A., Aanegola, A., Agrawal, A., Narayanam, R., and Kumaraguru, P. CAFIN: Centrality Aware Fairness in- ducing IN IN-processing for unsupervised representation learning on graphs. In Proceedings of the 26th Euro- pean Conference on Artificial Intelligence, 2023. doi:
Cognae pushes the frontiers of unlearning by consistently beating retraining-from- from---ratcct-cc scratch, and nearly matching the performance of a strong oracle on unlearning class con-

---

A Cognac Shot To Forget Bad Memories: Corrective Unlcarning for Graph Neural Networks
10.3233Mfia2300559, URL http::/dx, dww. 10. 0...33///AAA2005599
Chien, E., Pan, C., and Milenkovic, O. Efficient model up- dates for approximate unlearning of graph-structured data. In The Eleventh International Conference on Learning Representations, 2022.
Arun, A., Kumar, S., Nayyeri, M., Xiong, B., Kumaraguru, P., Vergari, A., and Staab, S. Semma: A semantic aware knowledge graph foundation model, 2025. URL https: //arxiv. org/ abs/2b05.
Dai, H., Li, H., Tian, T., Huang, X., Wang, L., Zhu, J., and Song, L.. Adversarial attack on graph structured data. In Dy, J. and Krause, A. (eds.), Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 1115-1122 PMLR, 10-15 Jul 2018.
Belrose, N., Schneider-Jospph, D., Ravfogel, S., Cotterell, R., Raff, E., and Biderman, S. LEACE: Perfect lin- concept erasure in closed form. In Thirty-seventh seventh Conference on Neural Information Processing Systems, www./eeett/ooo forum?
2023. URL
Douceur, J. R. The sybil attack. In International workshop on peer-to-peer systems, pp. 251-260. Springer, 2002.
id=awIpKpwIwF.
Bojchevski, A. and Günnemann, S. Deep gaussian em- bedding graphs: Unsupervised inductive learning via ranking. In International Conference Learning Repre- sentations, 2018.
Fan, S., Wang, X., Mo. Y., Shi, C., and Tang. J. Debiasing graph neural networks via learning disentangled causal substructure. In Proceedings of the 36th International Conference on Neural Information Processing Systems, NIPS '22, Red Hook, NY, USA, 2024. Curran Associates Inc. ISBN 9781713871088
Bojchevski, A. and Günnemann, S. Adversarial attacks on node embeddings via graph poisoning. In International Conference on Machine Learning, pp. 695-704, PMLR, 2019a.
Geisler, S., Schmidt, T., Şirin, H., Zügner, D., Bojchevski, A., and Günnemann, S. Robustness of graph neural net- works at scale. In Proceedings of the 35th International Conference on Neural Information Processing Systems, NIPS '21, Red Hook, NY, USA, 2024. Curran Associates Inc. ISBN 9781713845393.
Bojchevski, A. and Günnemann, S. Certifiable robustness to graph perturbations. Advances in Neural Information Processing Systems, 32, 2019b.
Bourtoule, L., Chandrasekaran, V., Choquette-Choo. C. A., Jia, H., Travers, A., Zhang, B., Lie, D., and Papernot, N. Machine unlearning. In IEEE S&P, 2021.
Goel, S., Prabhu, A., Sanyal, A., Lim, S.-N., Tom, P., and Ku- maraguru, P. Towards adversarial evaluations for inexact machine unlearning. arXiv preprint Sidi:2201.066444 2022.
Brodley, C. E. and Friedl, M. A. Identifying mislabeled training data. Journal of artificial intelligence research, 11:131-167, 1999.
Goel, S., Prabhu, A., Torr, P., Kumaraguru, P., and Sanyal, A. Corrective machine unlearning. Transac- tions on Machine Learning Research, 2024. ISSN 2835- 8856. URL https: /ttprr/eie/peereiieeeeee net forum? i 1d=8een44 9B.
Chen, C.. Sun, F., Zhang, M., and Ding, B. Recommenda- tion unlearning. In Proceedings of the ACM Web Confer- ence 2022, pp. 2768-2777, 2022a.
Gosch, I.,, Sturm, D., Geisler, S., and Günnemann, S. Re- visiting robustness in graph machine learning. In The Eleventh International Conference on Learning Represen- lations, 2023. URL https: / opwnreview.e..ee////p net/ forum?id-h1o7Rye
Chen, M., Zhang, Z., Wang. T., Backes, M., Humbert, M., and Zhang, Y. Graph unlearning. In Proceedings of the 2022 ACM SIGSAC conference computer and commu- nications security, pp. 493, 2022b.
Chen, Z., Li, P., Liu, H., and Hong, P. Characterizing the influence of graph elements. In The Eleventh In- ternational Conference on Learning Representations, 2023, URL https: httpt:ps///ppprvee.... id 1d=51GXyzOKOp.
Gu, T., Dolan-Gavitt, B., and Garg, S. Badnets: Identify- ing vulnerabilities in the machine learning model supply 2017.
chain. arXiv preprint
Günnemann, S. Graph neural networks: Adversarial robust- ness. Graph neural networks: foundations, frontiers, and applications, pp. 149-176, 2022.
Cheng. J., Dasoulas, G., He, H., Agarwal, C., and Zit- nik, M. GNNDelete: A general unlearning strategy for graph neural networks. In International Confer- ence on Learning Representations, 2023. URL https: ott.
Hamilton, W., Ying, Z., and Leskovec, J. Inductive repre-
sentation learning on large graphs. Advances in neural information processing systems, 30, 2017.
//openreview net/ fore/fformm2 dd-0mm
10

---

A Cognac Shot To Forget Bad Memories: Corrective Unlcarning for Graph Neural Networks
Heusel, M., Ramsauer, H., Unterthiner, T., Nessler, B., and Hochreiter, S. Gans trained by two time-scale update rule converge to local nash equilibrium, Advances in neural information processing systems, 30, 2017.
Lingam, V., Akhondzadeh, M. S., and Bojchevski, A. Re- thinking label poisoning for GNNs: Pitfalls and attacks. In The Twelfth International Conference Learning Representationss 2024. URL https: /tttp::://peezevie.. net / htt./formm?ico
d= dtt.rrmmmmmmiddi Je fgDPw.
Iyas, A., Park. S. M., Engstrom, L., Leclere, G., and Madry, A. Datamodels: Understanding predictions with data and data with predictions. In Chaudhuri, K., Jegelka, S., Song, L.,, Szepesvari, C., Niu, G., and Sabato, S. (eds.), Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pp. 9525 3585-9987. PMIR, 17- 23 Jul 2022. URL https: http:///pocee//eeeeeeee mmlr. press/vl 62 62/ wetpe///llleaaaaa html.
Ma, Y., Liu, X., Shah, N., and Tang. Is homophily a neces- sity for graph neural networks? In International Confer- ence Learning Representations, 2022. URL https: //oppnrevvew.cee wttp://eooomm.ddddceceeeeeeeeeee
Maini, P., Feng, Z., Schwarzschild, A., Lipton, Z. C., and Kolter, J. Z. TOFU; A task of fictitious unlearning for LLMs. In First Conference on Language Modeling, 2024. URL https:/ /owpnreveeeewweeeeee net/ forum??
Jin, W., Ma, Y., Liu, X., Tang, X., Wang, S., and Tang. J. Graph structure learning for robust graph neural networks. In Proceedings of the 26th ACM SIGKDD international conference on knowledge discovery & data mining. pp. 66-74, 2020.
Mao, H., Chen, Z., Tang, W., Zhao, J., Ma, Y., Zhao, T., Shah, N., Galkin, M., and Tang, J. Position: Graph foundation models are already here. In Forty-first Inter- national Conference on Machine Learning, 2024.
Kipf, T. N. and Welling, M. Semi-supervised classification with graph convolutional networks, 2017.
Northcutt, C. G., Athalye, A., and Mueller, J. Pervasive la- bel errors in test sets destabilize machine learning bench- marks. In NeurIPS, 2021.
Konstantinov, N. H. and Lampert, C. Fairness-awe aware pac learning from corrupted data. JMLR, 2022.
Ouyang, L., Wu, J., Jiang, X., Almeida, D., Wainwright, C., Mishkin, P., Zhang, C., Agarwal, S., Slama, K., Ray, A., et al. Training language models to follow instructions with human feedback. Advances neural information processing systems, 35:27730-27744 2022.
Kurmanji, M., Triantafillou, P., and Triantafillou, E. To- wards unbounded machine unlearning. NeurlPS, 2023.
Lec, C., Chang, J., and Sohn, J.yy. Analysis of using sigmoid loss for contrastive learning. In Dasgupta, S., Mandt, S., and Li, Y. (eds.), Proceedings of The 27th International Conference on Artificial Intelligence and Statistics, volume 238 of Proceedings of Machine Learning Research, pp. 1747-1755. PMLR, 02-04 May 2024. URI. htt.hhtttss///tt pwwcceedceeeeooooooooooooooccc.c ngs. ml .press/// v238/1ee24a.hte html.
Paleka, D. and Sanyal, A. A law of adversarial risk, interpo- lation, and label noise. In /CLR, 2023.
Pawelezyk, M., Di, J. Z., Lu, Y., Kamath, G., Sekhari, A., and Neel, S. Machine unlearing fails to remove data poisoning attacks. arXiv preprint 1xX1::2406.17266. 2024.
Said, A., Derr, T., Shabbir, M., Abbas, W., and Kout- soukos, X. A survey of graph unlearning. arXiv preprint arXiv:2310.02164, 2023.
Li, N., Pan, A., Gopal, A., Yue, S., Berrios, D., Gatti, A., Li, J. D., Dombrowski, A.-K., Goel, S., Mukobi, G., et al. The wmdp benchmark: Measuring and reducing mali- cious use with unlearning. In International Conference on Machine Learning, pp. 28525-28550 PMLR, 2024a.
Sanyal, A., Dokania, P. K., Kanade, V., and Torr, P. How benign is benign overlitting? ICLR, 2021.
Sanyal, A., Hu, Y., and Yang, F. How unfair is private learning? In Uncertainty in Artificial Intelligence, 2022.
Li, W., Li, J., de Witt, C. S., Prabhu, A., and Sanyal, A. Delta-influence: Unlearning poisons via influence functions, 2024b. URL hittps://arxiv/ /rb//s/// /bs/ 2411.13731.
Schoepf, S., Foster, J., and Brintrup, A. Potion: Towards poi- son unlearning. Journal of Data-centric Machine Learn ing Research, 2024. URL https:: http:://///eeeieww./ net/ / forum? wwwiiii44iiiii....
Li, X., Zhao, Y., Wu, 7., Zhang, W., Li, R.-H., and Wang, G. Towards effective and general graph unlearning via mutual evolution. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pp. 13682-13690, 2024c.
Sun, Y., Wang, S., Tang, X., Hsieh, T.-Y., and Honavar, V. Node injection attacks on graphs via reinforcement learning. arXiv preprint arXiv: (et.e999900554 2019.

---

A Cognac Shot To Forget Bad Memories: Corrective Unlcarning for Graph Neural Networks
Tan, J., Sun, F., Qiu, R., Su, D., and Shen, H. Unlink to unlearn: Simplifying edge unlearning in gnns. In Companion Proceedings of the ACM on Web Conference 2024, pp. 489-492,22 2024.
graph learning. In The Twelfth International Confer- ence Learning Representations, 2024. URL https: / //openreview.nete wwwp://wteee.tt///t//ee/// wtt.://mnnoooooooooaaaaaa--a
Zhang, C., Tian, Y., Ju, M., Liu, Z., Ye, Y., Chawla, N., and Zhang, C. Chasing all-round graph representation robust- ness: Model, training, and optimization. In The Eleventh International Conference Learning Representations, 2023. URL https: wwwppreeppeeeeeeeeeeeeeeeeeeeeee net forum? id= jkg
Veličković, P., Cucurull, G., Casanova, A., Romero, A., Liò, P., and Bengio, Y. Graph attention networks. In International Conference on Learning Representations, 2018.
Wang, K., Shen, Z., Huang, C., Wu, C.-H., Dong, Y., and Kanakia, A. Microsoft academic graph: When experts are not enough. Quantitative Science Studies, 1(1):396-413, 2020.
Zhang, H.. Zheng, T., Gao, J., Miao, C., Su, L., Li, Y.. and Ren, K. Data poisoning attack against knowl- edge graph embedding. In Proceedings of the Twenty- Eighth International Joint Conference on Artificial In- telligence, IJCAI-19, pp. 4853-4859, International Joint Conferences on Artificial Intelligence Organization, 7 2019. doi: 10.24963/ijcai 2019//77 URL https: //doi org 1..0..249630 jcai 2019/674.
Warnecke, A., Pirch, L., Wressnegger, C., and Rieck, K. Machine unlearning of features and labels. In Proc. of the 30th Network and Distributed System Security (NDSS), 2023.
Wu, B. and Davison, B. D. Identifying link farm spam pages. In Special Interest Tracks and Posters of the 14th International Conference World Wide Web, WWW '05, pp. 820-829, New York, NY, USA, 2005, Association for Computing Machinery. ISBN 1595930515. doi: 10. 1145/106274510067760 URL https: /ttp://ooo////////// 10627762..
Zhang, Z., Chen, L.,, Zhong, F., Wang, D., Jiang, J., Zhang, S., Jiang, H.,, Zheng, M., and Li, X. Graph neural network approaches for drug-target interactions. Current Opinion in Structural Biology 73:102327, 2022. ISSN 0959- 440X. doi: http:://oo.ag////00000.........0 URL
com/
Wu, J., Yang, Y., Qian, Y., Sui, Y., Wang. X., and He, X. Gif: general graph unlearning strategy via influence function. In Proceedings of the ACM Web Conference 2023, pp. 651-661 2023a.
Zhao, T., Chen, J., Ru, Y., Lin, Q.. Geng, Y., and Liu, J. Untargeted adversarial attack on knowledge graph embeddings. In Proceedings of the 47th International ACM SIGIR Conference on Research and Development in Information Retrieval, pp. 1701-1711, 2024.
Wu, K., Shen, J., Ning, Y., Wang, T., and Wang, W. H. Certified edge unlearning for graph neural networks. Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 2606-2617, 2023b.
Zügner, D. and Günnemann, S. Adversarial attacks on graph neural networks via meta learning. In International Conference on Learning Representations (ICLR), 2019.
Zügner, D., Akbarnejad, A., and Günnemann, S. Adversarial attacks neural networks for graph data. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, KDD '18, pp- 2847-2856, New York, NY, USA, 2018. Association for Computing Machinery. ISBN 978 9781450355520. doi: 10. 1145/2219819.3220077 URL https: /doiiorrr 10. 00.1145/3219911 3220078.
Wu, S., Sun, F., Zhang, W., Xie, X., and Cui, B. Graph neu- ral networks in recommender systems: A survey. ACM Comput. Surv, 55(5), December 2022. ISSN 0360-0300. doi: 10.1145/3535101. URL htths:::: / org/10. 1145/353510
Xi, 7., Du, T., Li, C., Pang, R., Ji, S., Luo, X., Xiao, X., Ma, F., and Wang, T. On the security risks of knowledge graph reasoning. In Proceedings of the 32nd USENIX Conference on Security Symposium, SEC '23, USA, 2023. USENIX Association. ISBN 978-1-9331133-37-3
Yao, Y., Xu, X., and Liu, Y. Large language model unlearn- ing, Advances in Neural Information Processing Systems, 37:105425-105477 2024.
Yuan, X., Zhang, C., Tian, Y., Ye, Y., and Zhang, C. Mit- igating emergent robustness degradation while scaling
12

---

A Cognac Shot To Forget Bad Memories: Corrective Unlcarning for Graph Neural Networks
Appendix
A. Proof of Theoretical Results
A.1. Proof of Receptive Field Theorem
14
A.2. Proof of Convergence Theorem
14
A.3. Proof of IC Attack Theorem
16
B. Data Manipulation Statistics
17
C. Formal Description of Cognac...
19
D. Results Showing The Breadth Applicability
D.1. Results GAT
18
D.2. Performance on large S
20
D.3. Results on trigger poisoning attack
20
E. Convergence and Ablations
E.1. Convergence Analysis... ................................
20
E.2. Analysis of Affected Neighbors Method...
21
E.3. Comparing sampling method MEGU's
21
E.4. Analysis of Accaff Reduction.......
22
F. Detailed Experimental Setup
F.1. Hyperparameter Tuning
23
F.2 Unlearning Times
24
13

---

A Cognac Shot To Forget Bad Memories: Corrective Unlcarning for Graph Neural Networks
A. Proof of Theoretical Results
A.I. Proof of Lemma 3.2
Lemma. Let G (V, E)) be an undirected graph, and let (() denote the 1-hop neighborhood of node v. For a node E let (s) denote the n-hop neighborhood of s, defined recursively as:
(s) (
in = 0, 1s
{s}
inn>0 >
In an n-layer GNN, the representation 2n of node s can affect the representations 2, nodes v only if u E N (N (s). For any E (s), Zu independent of 2s.
Proof. We prove the claim by induction the number of layers in the GNN.
Base Case (1 0):
(0) is initialized based only on the node's features. Thus, 2, h12 can only affect ( itself, and no other node * is affected.
At layer 1 0, the representation of node v,
Inductive Hypothesis:
Assume that at layer 1, the representation 2, 10 affects only the representations 1 of nodes v E (s),,, the l-hop neighborhood s.
Inductive Step:
At layer + 1, the representation A. (1+1) of a node v is computed as:
h(+1)) (nL),, (nn u ((E()))))
By the inductive hypothesis, ( depends only on nodes in N (u). Therefore, 15 ((+1) depends on nodes in:
(n)
wEN((e
Since (v) = (n) (u), h
(1+1) depends only on nodes in AV)1(vv).
For to be influenced by 2,, there must exist a path of length at most + 1 from to v, i.., v E (s).
Conclusion:
By induction, after layers, 2, only affect nodes in (*))). For any & (s)ss,, the representation 2, is independent of Zz.
A.2. Proof of Theorem 3.3
Theorem. Let I parameterize a GNN generating embeddings 2u; Zps Fn. E R* for triplets (u.p, Let L(O) -E [log (z, zp) + logo(-2] 2n)] and S(O) = E [z__ Zpp 2 2n).
Then under the assumptions stated below, gradient descent on L(0) with step size n S (where L is the Lipschitz constant of V o)) guarantees:
S(0++1) 2 S(0,) Vt 2 0,
and convergence, S(0') > S(Ou).
Assumption A.1 (Differentiabilltyy) zy Ep and = on are differentiable in 0.
Assumption A.2 (Convexity). L(0) is convex in 6.
Assumption A.3 (Bounded Gradients). [VV =p)]l s G and [[Vo zn)ll S G for some G > 0.
Proof. Let a = 2. 2p and b = 2, Zn. Then:
(()) - (a) + log (-b))
14

---

A Cognac Shot To Forget Bad Memories: Corrective Unlcarning for Graph Neural Networks
Under Assumption and using & (logo(x)) 1 (xx) and az (logo(-x)) -a we compute:
VgL -E
(1-o(a)) Vea o(b) Vab
Positive
Positive
The gradient of S()) is:
voS= = E Vab
The gradient of C can be rewritten as:
VoL = -BL--aoo(aaVood obb)
Both a--a) and (b) are positive for all finite a. Thus, VoL is negatively weighted combination of Vaa and Vab, while VaS is their unweighted difference.
Next, we show the monotonic improvement of S()). Consider gradient descent update:
O2+1 02 Vo
The change in S(0) is:
AS ((0+-)) - S(0,)
To simplify the analysis, we'll use first-order approximation. Specifically, for small updates, we approximate:
S(0++)) R 5(0,) + Vo5,0.+1 - 0z),
where (+-)) denotes the inner product. Substituting 0.+1 = 0g - v(,,),,,) we get:
AS - VoL)
Substituting S and VoL:
V voL) ( Vob) (a-
AS = Bio vaa 0 (b) 2 - -d Voa Vab) Vob
But since the dot product is commutative for real-valued column vectors, i.e., Vob Voa Voa
Vob. AS nBlo(-a)]\Vaa] (a((a obb) Vab)]
This expression contains both positive and negative terms. However, we now use the fact that the sigmoid function (xx) satisfies 0 (x: < for all real values of x, which means:
(1-o(a)) a--a) 0) for (a IR) and (a(b) 0) for (b R)
Thus, both terms a--a)l Veal2 and o vbbl2 are positive. On the other hand, the cross-product terms Vea T Tyb might be negative, but their magnitude is bounded by the gradients Voal and ||Vbbll which constrained by the assumption of bounded gradients (Assumption
3). Under this assumption, the gradients Vaa| and //bl are bounded by G. i.e.,
||Voa]| < G and V|abl G. Therefore, the cross-product terms are also bounded:
ja Vobl < G²
Now we can write the change S(0) as:
15

---

A Cognac Shot To Forget Bad Memories: Corrective Unlcarning for Graph Neural Networks
AS n ( Voa ab)) Vobll 2G
For sufficiently small the positive terms of [(-a)]| and [bbl will dominate the cross-product terms, ensuring that AS 2 0.
AS n [a( + V -GG
For sufficiently small 7, AS 2 O. Thus, ((0++1) 2 S().).
By convexity (Assumption 2), gradient descent converges to global minimum 0" where VoL(0*) = 0. AtO":
(o(aa)Veel E (bb
This equality holds only if a(-a) ++ and (b) - 0, which occurs when a + co and h - -00. Thus:
S(0") = Bi 2p - 2 zn| (0n)
Striet inequality S(A*) S(b) follows from the monotonic improvement at each step.
A.3. Proof of Theorem 3.1
Theorem. Let G = E, X) be a graph with node set V, edge set E, and features X. Let C1, C2 C CV be two distinct classes with ground-truth labels yı E {C1, C2}. Suppose an Interclass Confusion (IC) attack is applied as follows:
1. Select subsets S'C1 C1 and S'C² C2. each of size n forming S'GUU
2. Swap labels of a = fraction of S', creating a confused set S
3. Train GNN model M on (8) U
Let (C1), OM (C2) E Ed denote the mean embeddings of C1 and Cz and ((oar(Ci) (ar))) be the Wasserstein-2 distance between their embedding distributions. Assume:
Assumption A.1 (Homophily preserving GNNs). The GNN L-layers of homophily-pressrrvng message passing (e.g.. mean aggregation).
Assumption A.2 (Homophily). The graph exhibits 7-hooophhly, where intra-class edge density dominates inter-class. Assumption A.3 (Cross-Entropy Loss). The loss function L includes cross-entropy and graph smoothness regularization.
Then, there exists degradation term A 0 such that:
E ((x))())
(C1), &. (C2)) -A. A,
where x a - t).
Proof. Step 1: Embedding Process Formalization
The GNN computes node embeddings via L-layer message passing. For node v, the embedding ((0(v) layer / is:
1 (v) (W AGG ((olLI)(() MuollueNG (u)
where AGG is a mean aggregator, ( are learnable weights, and a is nonlinearity. The final embedding &M (v) (v)).
Step 2: Loss Function and Label Noise
The training loss L LeE Arrey where:
16

---

A Cognac Shot To Forget Bad Memories: Corrective Unlcarning for Graph Neural Networks
LE isT Eves the logge yo (cross-entropy)
Leg [ET E (uW)EE 1Øar (u) (u)(v)) (smoothness regularization)
For Sy, labels yr are swapped between C and C2- Let Enoise = {u E Sy yo is incorrect). The corrupted Cer forces conflicting gradients for v E Enose pulling (v) toward the wrong class centroid.
Step 3: Bias in Mean Embeddings
Let JA,, MC2 be the mean embeddings of C₁, C2 under Melen- After IC attack, for E Enoise
BløM (v)] axcc + (1 - a)je, (if E C1)
By linearity of expectation, the perturbed mean for C1 becomes:
Pee μC, alpec (C2a)
Similarly, I/c = pc2 + a(ıc, - pc,). Thus, the distance between means reduces by 2a|lMc. - -Maall-
Step 4: Message-Passing Amplification
Under 7-hooophhlly (where is the 'extent' of homophily), neighbors of u Emoise are likely in C1. The smoothness term freg propagates the corrupted embedding of to its neighbors, perturbing their embeddings. After L layers, the influence of Ensise spreads to ~ [V nodes. This amplifies the mean embedding shift by factor (1-111111 - +
Step 5: Wasserstein Distance Bound
The Wasserstein-2 distance between (C1) and (Cr( is dominated by the mean shift and covariance distortion. Using the Fréchet inequality:
D2 S lIre. -1'c,1' + Tr(Ec, + Ec, - 2(Ec, Ec,)
From Steps 3 and 4, 11,6, Pccs 2|2 (1 22m f)) MC221 Thus,
E[D(onr(Ci), OM (C2)) E[D( @Ma (C2)) - A,
where A - on (1 +) || - -c2 11
Conclusion
The IC attack reduces the separability of C₁ and C2 in the embedding space by biasing their mean embeddings toward each other and amplifying this bias via graph convolutions. The degradation A scales with a, and the depth L, confirming representation entanglement.
B. Data Manipulation Statistics
Table 4 presents the manipulation statistics for all datasets used in our study. We introduce significant variation in the degree of manipulation to achieve two key objectives: (1) in some datasets, a lower percentage of manipulated nodes or edges sufficient to induce noticeable performance degradation, while others require more extensive modifications, and (2) we aim to evaluate unlearning performance across a broad spectrum of manipulation scales. For instance, PubMed undergoes highest level manipulation, with nearly 39% of training nodes affected and 33.84% additional edges introduced, whereas datasets like CS and CoraFull experience minimal modifications. Additionally, for OGB-Arxiv, significantly larger dataset, only 3. 14% of training nodes are manipulated. This diverse manipulation strategy ensures rigorous and comprehensive evaluation of unlearning effectiveness across different graph structures.
C. Formal Description of Cognac
In this section, we outline the procedure of our proposed unlearning method, Cognac, designed to effectively remove the influence of manipulated data from GNNs. First, the algorithm identifies the nodes affected by the manipulation, as well as
17

---

A Cognac Shot To Forget Bad Memories: Corrective Unlcarning for Graph Neural Networks
Table Dataset manipulation statistics. Statistics of manipulations across datasets. percentage nodes and edges added are relative to the existing number of training nodes and the number of edges in the graph, respectively.
DATASET
TraiNING NODES
NODES MANIPULATED (%)
EDGES ADDED (%)
CORAFULL
28,
1.45
CORA
1,491
14.88
17.26
CITESEER
1, 1,22
14.78
20.38
DBLP
9, 714
10.50
5.78
PUBMED
11,830 830
38.96
33.84
OGB-ARXIV
90, 941
3.14
CS
10, 999
2.25
1.83
PHYSICS
20, 695
8.17
5.04
PHOTOS
492
11.40
5.04
COMPUTERS
8, 028
3.14
0.814
Cora
90-
Orsele
80-
Poisoned
60
Cognao FDC
50
40
30
GNNDelete
20
MEGU
SCRUB
10-
UIU
3
1001
Percmingge Identified for Deletion (Sy(mm)
Figure 6. Node Unlearning results for Cora with GAT backbone. Comparison of Accar for the unlearning methods on GAT trained on Cora for different values of (S.. We see that Cognac outperforms all baselines.
their corresponding positive and negative samples, and then alternates between applying CoGN and AC₁ DC unlearn their influence. The key steps include identifying the affected nodes, performing contrastive learning to re-optimize the embeddings, and minimizing classification loss on the unaffected nodes while maximizing it on the discovered manipulated set (Sy). The complete algorithm is detailed in Algorithm 1.
D. Results Showing The Breadth of Applicability of Cognac
D.1. Results GAT
To provide comprehensive comparison between Cognac and other methods, we provide results commonly used GNN backbone architectures GCN and GAT.
Graph Convolutional Network (GCN) is method for semi semi-supervised classification of graph-structured data. It employs an efficient layer-wise propagation rule derived from a first-order approximation of spectral convolutions on graphs.
Graph Attention Network (GAT) employs computationally efficient masked self-attention layers that assign varying importance neighborhood nodes without needing the complete graph structure upfront, thereby overcoming many theoretical limitations of earlier spectral-based methods.
Figure 6 shows that Cognac also performs competitively with a GAT backbone. When 5% of Sm is known, SCRUB performs similarly to Cognac, within the standard deviation. For higher fractions, we achieve greater Acc than the benchmark graph unlearning methods with large margins, often beating the performance of retraining the GNN from scratch. These results indicate that benchmark graph unlearning methods used for comparison cannot recover from the impact the label flip poison. In contrast, our method is much closer Oracle's performance.
18

---

A Cognac Shot To Forget Bad Memories: Corrective Unlcarning for Graph Neural Networks
Algorithm 1 COGNAC
Require: GNN M, Graph G = (V, F,, X), Deletion set Sy, Hyperparameters θ
Ensure: Unlearned GNN M
S LDBNTEEAFFEETDDNOOSSS,.KKKK. E,,
2: P SAMPLEPOSITIVES(S, F,, S))
3: N SAMPLENEGIATIVES((S...0
4: // Overall unlearning process
5: for outer epoch = to rotll spochs do
6: // Contrastive unlearning phase
7: for epoch = 1 to & contrast.epochs do
8:
+ M(X)
9:
L. EvES( log( (o Zp)) (x))))
10: . <- OP f.)
11:
end for
12:
// Gradient ascent on S,, and gradient descent on V Ss
13:
for epoch = I to ascent descent epochs do
14:
La f- (ROOSSENTROPY(M(()]ss Ys,)
M <- OPTIMIPTIMEM C.)
Ld (RROSEENROPP(MMX))))) Yvss,)
M OPTIMIZE(M, Ca)
18: end for
19: end for
20: return M
21:
22: function M,anllyyAfiiceedoodesMM,,,.,, E, θ)
X' INVERTFEATURESS(X, Sy,
24:
A -
-
25:
return TOPK(A.
26: end function
19

---

A Cognac Shot To Forget Bad Memories: Corrective Unlcarning for Graph Neural Networks
D.2. Additional Experiments Large ,
To stress-test Cognac's performance methods could potentially degrade the size of S grows we conduct an experiment where choose significant fraction of the training nodes of the Amazon, DBLP, and Physies datasets, to be attacked (by the binary label flip attack) and marked for deletion. The method performs competitively even at this large deletion size. Table 5 demonstrates these results.
Table Evaluation on larger sizes of Sy. Cognac performs well across datasets (Amazon, DBLP, Physics), even when a significant fraction of the total training nodes are present in Sy.
METHOD
AMAZON (25%)
DBLP (29.4%)
PHYSICS (14.8%)
Accrem
Acc,
Accrem
Accar
Accrem
Acc.d
ORACLE
92.9
95.6
72.9
86.0
95.2
95.1
ORIGINAL
92.5
49.0
74.9
57.9
58.9
95.4
Cognac
92.4
83.7
82.3
81.7
90.7
95.0
GNNDELETE
27.7
49.7
45.0
49.6
1.4
37.3
SCRUB
92.3
72.6
77.5
82.1
77.9
91.9
D.3. Results on trigger poisoning attack
We expand the analysis to a wider range of attack scenarios, now covering all major poisoning types (label, graph structure, and feature). Our feature attack injects trigger pattern into the feature vectors of select nodes, and assigning fixed spurious label, and reduces accuracy on the target distribution. Despite not being the strongest possible attack, our implementation provides sufficient signal for evaluation most unlearning methods struggle, while Cognac matches and even outperforms retraining performance. Complete results are provided Table 6.
The attacker selects subset of victim nodes Sp C V. For each node E Sp. its original feature vector x. is modified to zi, by setting specific trigger feature indices j E I, to (i.e., d'e, Vj E It, while other features Fr.j for j & Ia remain unchanged). Subsequently, all nodes v E Sp are assigned a fixed target label Starget- The choice of victim nodes here is random within the victim class, and the number is chosen to maintain stealth while maximising Attack Success Rate (the percentage of manipulated nodes in the test set that are successfully classified as the target class).
This use of a localized feature pattern as a trigger is analogous to patch-based backdoor attacks image poisoning, such as those introduced by BadNets (Gu al., 2017).
Table Results for unlearning the trigger-based feature manipulation. Cognac performs strongly across datasets, maintaining high Accast and Accrem. Retrain fails to recover accuracy on the victim class for the Cora dataset, while SCRUB fails to do so for both Cora and CS. GNNDelete and MEGU, the graph unlearning baselines, fail to remove the poison.
METHOD
PHOTOS
CORA
CS
AcCrem
Accaft
Accrem
Accafl
Accrem
Accaft
ORIGINAL
95.0 + 0.0
33.9 + 0.0
67.4 + 0.0
25.6 + 0.0
89.3 0.0
0.0
RETRAIN
94.1
92.0 1.7
68.3 0.4
46,9 + 6.8
93.0 0.2
92.8 2.3
GNNDELETE
0.0
0.0
0.2
00.8+9.11
68.0 0.0
0.0 0.0
MEGU
8.7
17.5 23.1
+.3
+.0
8.1
0.0
SCRUB
0.0
92.7
68.0
64.1
9.1
72.1
Cognac
0.0
0.0
6.0
9.0 7.0
0.6
E. Convergence and Ablations of Cognac
E.1. Convergence
We now discuss the convergence properties of Cognac. Plots in Figure describe the losses of each of the components of our method (contrastive, ascent, descent) after the last epoch of every step, the meaning of which should be clear from Algorithm 1: Line (which we denote as num steps). The loss plots are constructed over the best hyperparameters, and
20

---

A Cognac Shot To Forget Bad Memories: Corrective Unlcarning for Graph Neural Networks
Loss Convergence
Contrestive
Descent
330
0-2
1.3
0.33
S4p
Sup
24.
Figure 7. Convergence of the losses across unlearning steps. The ascent loss on S. continually increases expected, the descent loss on S Sm converges, and the contrastive loss exhibits low plateau after an initial overshoot, implying it may have learned discriminative features.
would likely not such convergence trends with sub-optimal hyperparameters, which may provide insights to improve performance when it's used in other settings well.
E.2. Analysis of method used to find affected neighbors
Our strategy to find affected neighbors is likely not perfect for finding the most affected nodes, and more sophisticated influence functions, such as the one presented in (Chen et al., 2023), could be used to potentially improve performance. Still, we note that it achieves a 5% higher Acc,s than while choosing random 1% nodes in the n-hopp neighborhood (where is the number of layers of message passing) while being cheap to compute: we only require a single forward pass over the model with the inverted features. Interestingly, Figure 8 also shows that even if the GNN is not well-trained, if we choose the top 6% affected nodes, the unlearning performance does not change much, while still being noticeably better than when we use random 4% of the neighbors.
noticeable changes in taking smaller larger 1%. However, removing this step entirely (k 0%) results in worse performance, suggesting that performing contrastive unlearning even small 6% is significant. Additionally, by keeping this percentage small, we ensure computational efficiency without diminishing performance (Figure 9 (right)), which is essential for unlearning methods.
Figure 9 (left) shows that there
E.3. Comparing our sampling method to MEGU's
Below, we compare the performance of Cognac while using our sampling method (described in Section 3.1.1) against its performance when using MEGU's sampling method.
Table 7. Evaluating Cognac with different strategy to identify affected nodes Cora. We find that strategy outperforms the MEGU's, while also being 8x faster. Both variants are hyperparameter-tumed for 100 runs.
METHOD
Accrem
Accur
SAMPLING TIME (3160 NODES)
ORIGINAL
61.4 + 0.00
40.0 0.00
ORACLE
58.4 0.00
69.2 0.00
Cognac (MEGU'S)
54.8 + 0.00
48.7 0.00
0.432
Cognac (OURS)
56.6 0.00
75.5 0.04
0.054 s
21

---

A Cognac Shot To Forget Bad Memories: Corrective Unlcarning for Graph Neural Networks
1.0
Top-k Accuracy
AcCaff using the top-k nodes identified
Random Accuracy
0.8
0.6
0.4
0.2
0.0
50 (acc=0.04)
80 (acc=0.09)
95 (acc=0.19)
110 (acc=00.27)
140 (acc=0.40)
180 (acc=0.49)
(acc=0.60)
360 (acc=0.63)
660 (acc=0.66)
860 (acc=0.66)
1060 (acc=0.66)
1150 (acc=0.66)
1207 (acc=0.66)
290
Epoch at which top-k nodes are identified
Figure 8. Effeet of how well-trained the GNN is top-&% affected neighbor identification. Here 4. The x-axis represents the epoch at which we used GNN representations to identify the most affected neighbors for Cognac. The y-axis reports the unlearning performance after contrastive unlearning these identified nodes using the final model. The red line contains performance after picking random subset from the n-hop neighborhood. Affected neighhorhood identification using top-&% logit change is more effective even with extremely undertrained GNN.
E.4. Why does Accah sometimes reduce as identified manipulated entities increase?
We find an interesting trend that sometimes, as more the manipulation set (Sm) is known and used as the deletion set (Sy) (going left right in Figure 4), Accui reduces. This can seem counterintuitive, as one would expect the accuracy of affected classes to improve manipulation reduces Accue due
samples used for unlearning. We hypothesize that unlearning larger fraction of the
factors that adversely affect the neighborhoods of the nodes removed, which typically have other nodes of the affected classes due to homophily. First, in the case of label manipulation, when we model it as node unlearning for consistency with prior work, we lose correct information about the graph structure. Second, when modifying the graph structure, i.e., removing some edges or nodes, changes the feature distribution of their neighboring nodes after the message passes, making out of distribution for the learned GNN layers. The same rationale is why the test nodes are kept the graph structure (without optimizing the task loss for them) during training (Kipf Welling, 2017). investigate this by adding an ablation where, the unlearning of the label manipulation, instead of unlcarning the whole node, we keep the structure, i.e., the node and connected edges, but unlearn the features and labels.
As observed in Table 8, retaining the node structure leads to large improvements in Accaи when the deletion set is larger (the full set of manipulated entities), while not benefiting much when the delction set is smaller. In the full manipulation set deletion setting, Cognac even slightly outperforms Oracle. This highlights how, unlike conventional node unlearning in graphs removing the nodes is not always the best way to unlearn manipulations. They can simply be moved from the train set to the test set to still partake in message passing, so the task loss not optimized over wrong labels.
22

---

A Cognac Shot To Forget Bad Memories: Corrective Unlcarning for Graph Neural Networks
1.0
Metrics
AcCan Actren
0.8
Accuracy Metrics
Time
0.2
0.0
70
80
90
100
30
40
50
60
100
(%)
(%)
Figure Efffect on unlearning (Accat)), utility (Acezem) and efficiency when identifying top-X% affected nodes contrastive unlearning. (Left) Cognac effectiveness sharply improves beyond à = 0%, suggesting that performing contrastive unlearning even a small percentage nodes (k) significantly enhances the algorithm's 's effectiveness. However, using higher values of lo yiclds similar performance with the added downside of increasing computational time (Right).
Table 8. Ablating node unlearning performance on label manipulation with and without unlinking. We report the accuracy the affected classes Accaf for unlearning label manipulation on Cora, both when the full and a subset (25%) of the manipulated set used for deletion. We find that not removing the structural information leads to significant improvement in Accafr especially when more entities are deleted. This illustrates that the unlcarning methods can achieve improved performance when precise information about the manipulated data is available.
Method
0.25
1.00
Linked
Unlinked
Linked
Unlinked
Oracle
73.0
73.0gn.o
73.0go.o
73.0
Original
42.0+0.0
42.0+n.o
42.0gn.o
42.0=n.0
Cognac
64.8
67. 8
77 77.2
69 1..
GNNDelete
35.2+2.5
50.2+1.9
21.924.5
30.226.3
MEGU
40.8+1.6
33.420.4
41.221.5
32.1
SCRUB
45.7+0.0
60.7
41.1+u.p
29.0=m.v
ACADC DC
61.7+v.0
58.8+0.0
63.7
54.3
F. Detailed report of the experimental setup
F.1. Hyperparameter Tuning
We perform extensive hyperparameter tuning for all unlearning methods using Optuna (Akiba et al., 2019) with a TPESampler (Trec-structured Parzen Estimator) Algorithm. We ensure the hyperparameter ranges searched include any values specified by the methods. The optimization target is an average of Accaft and Accrem, computed on the validation set. We report averaged results across five seeds. Method-specific hyperparameter ranges and scatter plots across hyperparameters for each method are provided in Appendix F.I.
We perform hyperparameter tuning for each combination of attack, dataset, unlearning method, and the identified fraction of deletion set (Sy). The optimization target is average of Accar and Accrem- computed the validation set. For each setting, we run 100 trials with hyperparameters selected using the TPESampler (Tree-struucture Parzen Estimator) algorithm. In Figures 10, 1I and 12, we report Accat and Accrem scores for each hyperparameter tuning trial. Across hyperparameter runs, existing gased unlearning methods, barring MEGU, vary drastically across different sets of hyperparameters. On the other hand, our proposed method Cognac and its ablations show consistently high scores across hyperparameters, showcasing Cognac's robustness to hyperparameter tuning.
23

---

A Cognac Shot To Forget Bad Memories: Corrective Unlcarning for Graph Neural Networks
SCRUB
DC
COGNAC
ACC
06
0.6
AcS.yt
62
02
02
02
0.1
0.4
0.0
0.5
0.6
0.8
ACCrum
ACGuum
ACCrum
MEGU
GNNDelete
GIF
08
0.8
0.2
0.2
00.
0.
02
04
24
04
100
0.0
02
04
0.0
0.8
10
0.0
02
0.6
0.6
0.5
1.
AcCrem
ACGrem
Figure 10. Hyperparameter runs for Sy = 1.0 on Amazon. Scores of various hyperparameter trial runs. The best hyperparameters are selected according the rum achieving the best value for the average of Accrem and Accaft
F22 Unlearning Times
To ensure the practicality of inexact unlearning methods, they must achieve greater efficiency than retraining from scratch. As illustrated in Figure 13, Cognac demonstrates competitive efficiency compared to alternative methods, offering substantial speedups over retraining from scratch.
Measuring Unlearning Time. To simplify comparisons to just two axes, Accaft and Accrem. fix maximum cutoff of time unlearning method can take, as motivated by Maini et al. (2024). We chose this cutoff as 25% of the original model training time. We pick the best model checkpoint during training for each method, which could be achieved earlier than this. Average run times for each method reported in Figure 13 under Appendix F.2 show that Cognac's efficiency is comparable to or better than baselines. All experiments were run on machine with Intel Xeon CPUs and two dedicated RTX 5000 GPUs.
24

---

A Cognac Shot To Forget Bad Memories: Corrective Unlcarning for Graph Neural Networks
SCRUB
DC
COGNAC
10
1.0
3.0
AcCiff
0.
0.6
AcCst
0.0
02
ACGrum GNNDelete
AcCrum
MEGU
GIF
ACGU
0.6
0.6
AcCgp
0.6
0.
02-
0.-
02
04
0.6
0.0
Figure 11. Hyperparameter runs for Sy 1.0 CS. Scores of various hyperparameter trial runs. The best hyperparameters selected according to the run achieving the best value for the average of Accrem and Accar.
SCRUB
AC
COGNAC
1.0
3.0
AcCuft
0.
0.6
AcCap
0.6
02
04
0.6
AcCrom
MEGU
GNNDelete
GIF
00
0.6
AcCett
02
0.
0.-
02
04
0.6
0.6
AcCrem
AcCuem
Figure 12. Hyperparameter runs for S, 1.0 Cora. Scores of various hyperparameter trial runs. The best hyperparameters selected according to the run achieving the best value for the average of Accrem and Accau.
25

---

A Cognac Shot To Forget Bad Memories: Corrective Unlcarning for Graph Neural Networks
Amazon
CS
Cora
Time Takeen (4)
5,188
3,095
3,020
2,257
1.809
1.979
2.043
1.214
220
0.005
0,00
007
Cognac
GFF
GNNDelete
MEGU
Patrain
SCRUB
utu
Cognac
GFF
GNNDelete
MEGU
Retrain
SCRUB
und
Cognac
GiF
GNNDelete
MEGU
Retrain
SCRUB
utd
Figure Time taken to unlearn. report the time taken by each unlcarning method datasets, setting where all manipulated samples are known for deletion. Cognac provides significant speedups over Retrain and has performance similar to other unlearning methods.
26


Reviews:
[{"review_id": "GKhxnn2wIV", "reviewer": "Reviewer_rWWk", "summary": "In this paper, the author proposes an unlearning algorithm, Cognac, to remove manipulated data from a well-trained GNN model. The approach first identifies sensitive neighbors that may be influenced by spurious entities and then mitigates these effects by aligning the embeddings of the selected neighbors with unaffected ones. Abundant experiments have been conducted to demonstrate the perrormance of the proposed method.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer’s recognition of our comprehensive experiments and the soundness of our claims. We're also pleased that the reviewer found the idea behind Cognac innovative. We hope our clarifications below address your concerns.\n\n---\n\n## Affected Nodes Sampling\n\n_Can solely targeting homophilic edges mislead the unlearning algorithm?_\n\nYour question raises an important point. While the attack exploits the homophily due to the GNN’s inductive bias, the unlearning algorithm is fully agnostic to the manipulation type. It simply requires knowledge of a representative subset of the unlearning entities and selects affected nodes based on prediction changes, not graph structure properties, and can hence be adapted for heterophilic settings. Moreover, in L418-421, we acknowledge that our current work has not explored applications in heterophilic datasets yet.\n\n_1-hop vs 2-hop node selection_\n\nThe heuristic selects nodes based on the magnitude of change in their output logits (∆χ) when features are inverted, and not just the hop distance. A high ∆χ indicates strong influence from manipulated nodes, even if the node is not a direct neighbor. By choosing the top k% based on the GNN forward pass, the method accounts implicitly for hop distance, ensuring that only nodes significantly affected are flagged for corrective unlearning.\n\n_Soundness of our heuristic selecting affected nodes_\n\nLemma 3.2 shows that a manipulated node’s influence is confined to its n-hop neighborhood. Using feature inversion, we measure how changes in these nodes’ features affect their neighborhood. Our ablation studies (Figure 8, Appendix E.2) reveal that selecting the top 10% of nodes by change in output logits performs similarly to using the full n-hop subgraph, yet is 2× faster. Moreover, compared to MEGU’s sampling method, our heuristic delivers over 25% higher $Acc_{aff}$ and is 8× faster. Additional details are in our discussion with reviewer igz9 and will be included in the revised version.\n\n_Working Example_\n\nWe will add an example of our affected nodes sampling to the updated version (link to figure: https://imgur.com/a/Kgzfl3E)\n\n---\n\n## Contrastive Loss and Information Preservation\n\nThank you for pointing this out! Left unchecked, contrastive learning could indeed degrade information. That's why we perform gradient descent on the retain set, which contains these affected nodes, ensuring their information is preserved. As part of new experiments, we add an ablation showing that contrastive unlearning alone (CoGN) performs notably worse notably worse (upto 48.2% on label flip on Photos). More details can be found in our discussion with reviewer igz9 and in the following table: https://imgur.com/a/mk6D9ly. We will include this discussion explicitly in the revised version in Appendix E.\n\n---\n\n## Data Manipulations - Breadth and Discovery\n\n_Discovering manipulated data_\n\nWe agree that addressing the difficulty in finding manipulated data is the motivation and main contribution of our work! [1] shows that prior works rely on the availability of all manipulated samples, which is unrealistic. Our method Cognac achieves better performance than theirs with as little as 5% of the manipulated set known. Note that unlearning is only defined for a non-zero number of unlearning entities. A small fraction of the manipulated data can be identified by manually investigating a small random subset of the data or using automated tools like [2]. We will address this in the revised version in Section 6.\n\n_Spurious edge addition_\n\nThanks for noting that this would be a valuable setting!  This attack is indeed covered in our experiments, with details in Section 4.2.\n\n---\n\n## Paper Revision\n\n1. **We’ll improve the writing of proof A.2** to make it more readable, and **expand the conclusion** with specific ideas for next steps.\n2. **Include missing reference:** Thank you for pointing out the paper. We’ll add it to our related work section. We note that while both use contrastive methods, they use it for different objectives. Cognac performs contrastive learning directly on hidden representations of affected nodes while GCU improves upon GNNDelete by contrasting between Deleted Edge Consistency and Neighbourhood Influence to provide a more granular, graded removal of edge information rather than the binary deletion used in GNNDelete.\n3. **Code is already present in the supplementary material:** All code and hyperparameters are in the supplementary materials zipfile; we'll include a deanonymized link in the final version.\n\n---\n\nThanks for your questions and suggestions. We hope our response increases your support for our work and are happy to discuss further!\n\n[1] Goel, Shashwat, et al. \"Corrective Machine Unlearning.\" *Transactions on Machine Learning Research*.\n\n[2] Thyagarajan, Aditya, et al. \"Identifying Incorrect Annotations in Multi-label Classification Data.\" *ICLR 2023 Workshop on Pitfalls of limited data and computation for Trustworthy ML*.", "claims_and_evidence": "The claims are sound and figure 1 explains it by showing a concrete example. However, I have two questions:\n1 In Section 2, the focus is on removing edges that compromise the homophily property of the graph. However, recent findings suggest that heterophilic GNNs can enhance performance, indicating that non-local neighbors can also contribute to node and edge classification tasks. Does this imply that solely targeting homophilic edges could mislead the unlearning algorithm?\n\n2 In Section 3.1.1, the method selects affected nodes using a heuristic that measures the influence of manipulated data. I suggest providing a concrete example to clarify this approach.\n\n3 In reality, we usually don't know the manipulated data set.", "methods_and_evaluation_criteria": "The problem is well defined and algorithm is plausible. However, I have several questions:\n1 In section 3.1.1, the method selects affected nodes influenced by the manipulated data. However, how can they ensure that these nodes exert a strong influence on other 'unaffected' data? For example, suppose node A is a 1-hop neighbor of the manipulated node N but has no other connections, while node B is a 2-hop neighbor of N but has multiple neighbors. Given k=1, does it make sense to select A over B?\n\n2 I suggest them to introduce the procedure of spurious edge addition in their experiments.\n3 They propose a contrastive loss in formula 2 by aliging the inner product of \"affected links\" with \"unaffected links\".  Could this potentially degrade the information preserved in the 'affected nodes'?", "theoretical_claims": "I suggest them to prove the soundess of the heuristic of selecting affected nodes in section 3.1.1.", "experimental_designs_or_analyses": "The experiments appear comprehensive, and their algorithm outperforms other approaches.", "relation_to_broader_scientific_literature": "NA", "essential_references_not_discussed": "Yang, Tzu-Hsuan, and Cheng-Te Li. \"When Contrastive Learning Meets Graph Unlearning: Graph Contrastive Unlearning for Link Prediction.\" In 2023 IEEE International Conference on Big Data (BigData), pp. 6025-6032. IEEE, 2023.", "other_strengths_and_weaknesses": "The idea is innovative. However, paper was a little hard to follow with too many avenues and experiments explored, it would have been more productive to reduce the scope of the paper. At the end the conclusion and future work needs to be a little more elaborate in terms of next steps. \n\nThe idea and approach is good, work is there just needs more organizing and scoping out.", "other_comments_or_suggestions": "NA", "questions_for_authors": "Could you provide the link of code?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {"ethics_expertise_needed": ["Responsible Research Practice (e.g., IRB, documentation, research ethics, participant consent)"], "ethical_review_concerns": "NA"}}, {"review_id": "vcFKFjKJye", "reviewer": "Reviewer_igz9", "summary": "The paper addresses the challenge of Corrective Unlearning in Graph Neural Networks (GNNs). While GNNs are widely used across various applications, their message-passing mechanism makes them vulnerable to adversarial manipulations and erroneous data, as errors can propagate throughout the graph. To mitigate this, the authors introduce Cognac, a novel method designed to unlearn the effects of manipulated data, even when only a small fraction (5%) of the manipulated set is identified. Cognac significantly outperforms existing approaches, restoring model performance to levels close to those achieved with fully corrected data. Moreover, it is 8× more efficient than retraining the model from scratch.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer’s recognition of our work, particularly noting our theoretical analysis of adversarial attacks on GNNs, the effective mitigation of data manipulation through Cognac, and its computational efficiency compared to retraining.\n\n---\n\n## Expanding the analysis to a wider range of attack scenarios\n\nThank you for the suggestion! We've added preliminary experiments on feature poisoning backdoor attacks across 3 representative datasets, now covering all major poisoning types (label, graph structure, and feature). The results can be found at https://imgur.com/a/nJnsqWN.\n\nOur feature attack injects trigger a pattern into the feature vectors of select nodes, and assigning a fixed spurious label, and reduces accuracy on the target distribution. Despite not being the strongest possible attack (also addressed in the limitations section, L422-426), our implementation provides sufficient signal for evaluation - most unlearning methods struggle, while Cognac matches and even outperforms retraining performance. Retrain fails to recover accuracy on the victim class for the *Cora* dataset, while SCRUB fails to do so for both *Cora* and *CS*. GNNDelete and MEGU, the graph unlearning baselines, fail to remove the poison.\n\n---\n\n## Affected Nodes Sampling: Validation against alternative approaches\n\nOur ablations (Figure 8, Appendix E.2) show the top 10% of affected nodes using our sampling performs comparably to using all nodes. As per your suggestion, we compare our sampling with MEGU’s.\n\nThe link to the table can be found at https://imgur.com/a/3HykVJ8. Our results on the Cora dataset indicate that our method outperforms MEGU’s approach. Our heuristic delivers over 25% higher $Acc_{aff}$ and is 8x faster (0.43s vs 0.05s for 3160 samples)\n\nKey difference: MEGU propagates features through adjacency matrices using cosine similarity to adaptively threshold selection, while we use actual model predictions with L1 norm. \n\nWe would be happy to include any additional sampling strategies/influence functions in the final version.\n\n---\n\n## Method Ablations\n\nWe appreciate your suggestion! \n\nWe've added ablation studies showing the individual contributions of both components (CoGN and AC/DC). While our paper already reports AC/DC performance separately (Figure 3), we've now added results for CoGN too, at this link (https://imgur.com/a/mk6D9ly):\n\nBoth components contribute significantly: **CoGN alone achieves only 34.7% forgetting on Amazon (compared to Cognac’s 82.9%) and 42.1% on Cora (vs. Cognac’s 75.5%)**, showing that it effectively moves affected nodes but lacks correction from labels. Conversely, **AC/DC achieves 76.2% forgetting on Amazon, far better than CoGN but still below Cognac**, confirming that the components are complementary. AC/DC weakens incorrect learning signals and preserves task-relevant representations, while CoGN steers affected nodes away from manipulated ones.\n\n---\n\n## Scalability to larger datasets\n\nWe thank the reviewer for the suggestion. However, we note that Cognac is designed so that its computational complexity primarily scales with the **size of the deletion set, not the entire graph**. In real-world unlearning applications, the deletion set is typically a small fraction of the overall data, making our approach inherently scalable. Moreover, our experiments (Appendix D.2) demonstrate that even when faced with a relatively large deletion fraction, Cognac consistently outperforms baseline methods. This empirical evidence further confirms that our method can effectively handle large graphs, showing promise against scalability concerns even for massive real-world networks.\n\n---\n\n## Does Cognac’s success depend on having some prior knowledge of the manipulations?\n\nThe unlearning algorithm is fully agnostic to the manipulation type (as we show in our experiments across label, graph structure, and the newly added feature attacks). The input to the algorithm is simply a representative subset of the manipulated data, without any knowledge about the manipulation itself. Furthermore, note that unlearning is only defined for a non-zero number of unlearning entities. Please see our discussion with reviewer rWWk for additional insights on this.\n\n---\n\nThanks! Your detailed feedback has helped us greatly improve the paper. We hope this increases your support for our work.", "claims_and_evidence": "Generalizability to Diverse Manipulations and Tasks: \nThe paper primarily examines targeted binary class confusion attacks on edges and nodes within node classification tasks. The evaluation to a broader range of attack types and graph-related tasks is missing to validate Cognac's overall effectiveness and applicability.", "methods_and_evaluation_criteria": "yes", "theoretical_claims": "Yes, \nTheorem 3.1 analyzes the impact of Interclass Confusion attacks on class representations.\n\nLemma 3.2 establishes the locality of manipulation propagation in GNNs.", "experimental_designs_or_analyses": "Evaluation Scope: The paper evaluates targeted binary class confusion attacks on both edges and nodes, covering key manipulation types. However, expanding the analysis to a wider range of attack scenarios could further strengthen the evaluation.\n\nIdentification of Affected Nodes: The paper employs a heuristic approach to identify affected nodes by inverting features and observing changes in output logits. While this method appears reasonable, a more rigorous validation against alternative approaches would enhance confidence in its effectiveness.\n\nThe paper does not explicitly include ablation studies to assess the contribution of individual components (CoGN and AC-DC). Incorporating such studies would strengthen the justification for the method’s design choices and provide deeper insights into their impact.", "relation_to_broader_scientific_literature": "The paper builds upon the recently introduced problem of Corrective Machine Unlearning (https://arxiv.org/abs/2402.14015), which aims to remove the adverse effects of manipulated data while being agnostic to the type of manipulations. This approach operates with access to only a representative subset of the manipulated data for unlearning, making it more practical for real-world applications where full knowledge of manipulations is often unavailable.", "essential_references_not_discussed": "no", "other_strengths_and_weaknesses": "Strengths:\n1. The paper provides a theoretical analysis of adversarial attacks on GNNs, specifically examining the effects of Interclass Confusion attacks on the Wasserstein-2 distance between class embedding distributions.\n2. Cognac effectively mitigates the impact of manipulated data, even when only 5% of the manipulated set is identified, outperforming existing GNN unlearning methods.\n3. The proposed method restores most of the performance of a strong oracle trained on fully corrected data, even surpassing retraining from scratch when the deletion set is excluded.\n4. Computational Efficiency: Cognac is 8× more efficient than retraining and scales effectively to large datasets.\n\n\nWeakness:\n1. Scalability to Extremely Large Graphs: While Cognac demonstrates strong scalability to large datasets, its performance on massive graphs with billions of nodes, which are common in real-world applications like social networks, remains largely untested.\n2. The study primarily focuses on node classification tasks and targeted binary class confusion attacks on edges and nodes, which may not fully capture all possible manipulation scenarios.\n3. Dependence on Identified Manipulations: Although Cognac remains effective even when only 5% of manipulated entities are identified, its success still depends on having some prior knowledge of the manipulations.", "other_comments_or_suggestions": "It would be great to have more experiment evaluation on the eally large-scale dataset.", "questions_for_authors": "no", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "5yImdIuK7z", "reviewer": "Reviewer_Lw8o", "summary": "The authors propose a methodology, named Cognac, aimed at enhancing the fairness, robustness, and accuracy of Graph Neural Networks (GNNs) through corrective unlearning techniques applied to specific nodes. Cognac consists of two primary components:\n\n1.\tContrastive Unlearning on Graph Neighborhoods (CoGN): This component identifies nodes influenced by entities that should be removed and strategically repositions them away from those entities, while concurrently moving them closer to normal nodes through contrastive learning.\n\n2.\tAsCent DesCend de-coupled (ACDC): This technique leverages gradient ascent and descent methods to induce effective unlearning for sets of nodes designated for removal.\n\nThe authors support their proposed components with sufficient mathematical justification and rigorous proofs, demonstrating the robustness and theoretical soundness of the proposed methodology. Extensive experiments conducted across diverse benchmark datasets and multiple GNN models illustrate the superiority of Cognac over existing approaches. Notably, the proposed methodology maintains strong performance even when the number of nodes designated for removal is extremely limited and consistently scales effectively to significantly larger datasets.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their thorough and positive assessment of our work! We are thrilled that you recognized the novelty, mathematical soundness, experimental rigor, and effectiveness of our proposed method. In response to the other reviewers, we have added more experiments: (1) a feature trigger poison (reviewer igz9), (2) ablations of CoGN and AC/DC separately (reviewers igz9, rWWk), and (3) ablations of the strategy for identifying affected nodes (reviewers igz9, rWWk). If you have any specific questions or concerns that could further strengthen your support for our work, we would be happy to address them.", "claims_and_evidence": "The authors provide clear and convincing evidence supporting the two core components of their proposed methodology (CoGN and ACDC). Specifically, they present rigorous mathematical justifications for identifying and adjusting nodes through the CoGN approach, including the derivation of the criteria used to select nodes for contrastive unlearning. Additionally, the authors offer comprehensive theoretical proofs regarding the ACDC technique, which effectively unlearns the influence of designated node sets. Beyond these theoretical validations, the authors also perform extensive experimental evaluations demonstrating that their proposed methods outperform existing state-of-the-art techniques in various experimental scenarios.", "methods_and_evaluation_criteria": "The authors evaluate their proposed method using a recently introduced metric from the literature (ICLR, 2024). They clearly indicate the sources of benchmark datasets widely adopted in prior research, ensuring transparency in their evaluations. Moreover, the authors acknowledge that, given the inherent characteristics of unlearning methods, guaranteeing a fair comparison can be challenging. To address this issue, they openly share multiple components essential for reproducibility, effectively demonstrating the robustness of their experimental setup. Finally, the soundness of the experimental approach is further strengthened by thoroughly comparing their methodology against five state-of-the-art benchmark models and four additional reference models.", "theoretical_claims": "The authors provide rigorous mathematical justification regarding their proposed method. First, they clearly formalize and prove how the Wasserstein-based interclass confusion attack affects class distributions by quantifying changes via mathematical analysis, thereby establishing a strong theoretical foundation. Additionally, the authors offer mathematical proofs to efficiently identify specific cases where the representation of an arbitrary node could be influenced, significantly optimizing the node-selection step in contrastive unlearning (CoGN). Finally, they define a loss function suitable for effective contrastive unlearning and rigorously prove important theoretical properties, including differentiability, convexity, and bounded gradients, thereby further solidifying the soundness and reliability of their approach.", "experimental_designs_or_analyses": "The authors demonstrate the validity of their proposed method by comparing it with four primary GNN unlearning techniques (original model, retrain, finetune, i.id.) and five state-of-the-art benchmark models. They emphasize that the widely adopted retrain baseline, as indicated by recent research, does not represent an optimal standard for corrective unlearning. In their evaluation, the authors convincingly show that their proposed method outperforms the retrain-based approach. Furthermore, the authors introduce an oracle baseline trained on the full, unmodified dataset to represent an upper-bound for corrective unlearning performance. The authors' method demonstrates strong performance relative to both the retrain and oracle baselines, further validating the effectiveness and rigor of their experimental evaluations.", "relation_to_broader_scientific_literature": "The paper extensively compares to prior graph unlearning methods. For instance, GNNDelete by Cheng et al. (2023) is taken as a baseline. By doing so, the authors clarify that they are tackling the corrective post-hoc unlearning scenario rather than the more studied privacy-driven exact unlearning scenario, which is an important distinction.\nFurthermore, the paper relates Cognac to general unlearning methods like SCRUB (Kurmanji et al., 2023). By including SCRUB, they acknowledge the broader machine unlearning literature. The fact that Cognac, with graph-specific insight, outperforms SCRUB in this domain highlights the contribution that graph structure awareness brings. In positioning relative to broader literature, the authors also mention robust training and concept erasure approaches in the introduction. \nThey cite works on robust pre-training for GNNs (adversarial training by Yuan et al., 2024; defense by Zhang et al., 2023) and concept erasure in vision (Belrose et al., 2023) to clarify that while those aim to remove unwanted influences, unlearning is distinct in that it’s post-hoc and does not assume knowledge of the specific concept or attack in advance. This helps readers see how their work is different from training a GNN to be robust to attacks from the start instead fix the model after the fact.", "essential_references_not_discussed": "NA", "other_strengths_and_weaknesses": "Strengths\n1.\tThe authors propose a novel approach, named Cognac, comprising two key components—Contrastive Unlearning on Graph Neighborhoods (CoGN) and Ascent Descent De-coupled (ACDC)—to address corrective unlearning in Graph Neural Networks (GNNs). The authors provide rigorous mathematical justifications and proofs supporting both components, demonstrating their theoretical soundness and validity clearly and convincingly.\n2.\tThrough extensive experimental evaluation on various benchmark datasets and models, the authors demonstrate the superiority of Cognac compared to existing baseline unlearning approaches. Notably, the experiments include a wide array of benchmark datasets and state-of-the-art models. The authors also highlight the scalability of their approach by showing its effectiveness on datasets up to eight times larger than standard benchmarks, further supporting the method's robustness.\n3.\tThe authors demonstrate that Cognac achieves superior performance even when compared against the oracle model, which represents the upper bound for corrective unlearning performance. Remarkably, Cognac maintains strong performance despite having access to only 5% of the manipulated data, clearly highlighting the method’s effectiveness and efficiency.", "other_comments_or_suggestions": "NA", "questions_for_authors": "NA", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper presents Cognac for corrective unlearning in Graph Neural Networks (GNNs). The approach seeks to remove the effects of manipulated data from a trained GNN model by identifying and mitigating the influence of spurious entities on sensitive neighbors. Cognac consists of two main components: one that repositions affected nodes away from manipulated entities and towards unaffected ones through contrastive learning, and another that uses gradient-based methods to induce unlearning for designated node sets. This requires the method to identify which nodes are manipulated, which may be difficult in practice (but assumed somewhat easy in the paper because of the clear influence they exert, which is OK). The authors provide some mathematical justification for the approach, as well as extensive experimental results across various benchmark datasets and GNN models. 

Overall, the work is a good contribution. The reviewers were positive. I am recommend acceptance.
Decision: Accept (poster)