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

Thank you for the feedback! We are glad that you found the problem novel and interesting, and the proposed method effective. We highlight how we have updated the paper to address the weaknesses (W), and hope this improves the overall rating of our work. We also noticed a lower score in the presentation, please let us know if you have any suggestions for improvement.

W1: The experiments in the paper are seriously insufficient

We tested our method with 2 adversarial evaluations across 3 datasets, and 5 varying fractions of manipulated data, with several ablations of our method. Overall, we perform over 3000 runs per unlearning method to try our different hyperparameters and converge on the best performances for each setting. As also agreed by reviewers LxzZ and A7wi, we believe this makes our experiments comprehensive for the graph ML domain.

Taking your feedback into account, to increase the breadth of our experiments, we have now added results on the binary label flip attack across three large benchmark datasets used in prior graph unlearning literature (Amazon-Computers [4], Physics [4], DBLP [5]) where we test our method and the best-performing baselines. Details about these datasets are provided in Table 8. From Figure 10, we can observe that Cognac still outperforms the baselines in most of the settings and matches Oracle’s performance in the new datasets.

W2: Authors may need to provide a clearer comparison with these related works.

Thank you for the reference, and for allowing us to further clarify the scope of our work. Like most of the previous works in the domain of graph unlearning, such as GNNDelete [1], MEGU [2] and GIF [3], our work is intended for homophilic graphs and consequently caters to architectures like GCN and GAT. These are also the baselines we evaluate against in our work, and thus for a fair comparison, we primarily evaluate on datasets used in these works. We have now acknowledged focusing on homophilic graphs in the Limitations section L524-525 along with the cited reference, and agree that heterophilic graph unlearning would indeed be an intriguing avenue for follow-up works.

[1] Jiali Cheng, George Dasoulas, Huan He, Chirag Agarwal, & Marinka Zitnik (2023). GNNDelete: A General Strategy for Unlearning in Graph Neural Networks. In The Eleventh International Conference on Learning Representations .

[2] Li, X., Zhao, Y., Wu, Z., Zhang, W., Li, R. H., & Wang, G. (2024, March). Towards Effective and General Graph Unlearning via Mutual Evolution. In Proceedings of the AAAI Conference on Artificial Intelligence (Vol. 38, No. 12, pp. 13682-13690)

[3] Wu, J., Yang, Y., Qian, Y., Sui, Y., Wang, X., & He, X. (2023). GIF: A General Graph Unlearning Strategy via Influence Function. In Proceedings of the ACM Web Conference 2023 (pp. 651–661). ACM.

[4] Shchur, O., Mumme, M., Bojchevski, A., & Günnemann, S. (2018). Pitfalls of graph neural network evaluation. arXiv preprint arXiv:1811.05868

[5] Tang, J., Zhang, J., Yao, L., Li, J., Zhang, L., & Su, Z. (2008). Arnetminer: extraction and mining of academic social networks. In Proceedings of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining (pp. 990–998)

Thank you for your responses, I will raise my score!

Thank you for the constructive feedback! We’re glad you found our experiments comprehensive, and recognized our innovation in uniquely handling challenges of graph unlearning to achieve strong performance. We highlight how we updated the paper to address the weaknesses (W), hoping this improves the contribution and overall rating of our work.

W1: The evaluation metrics (ACC_aff and ACC_rem) mentioned in Lines 175–184, Page 4 differ from traditional accuracy metrics

The metrics are not novel, and we borrow them directly from the recent work which introduced corrective unlearning [1]. To further clarify, we do compute the accuracy over the original test (unseen) datapoints, but we just split it into two parts - one calculated over test data points from the manipulated distribution and one over test data points from the remaining data distribution. For example, in case of the label flip attack, $Acc_{aff}$ measures the accuracy over the two classes that were chosen to have flipped labels and $\mathrm{Acc_{rem}}$ measures the accuracy the remaining $n-2$ classes, where $n$ denotes the number of classes. We have added the following lines to Section 3 (L180-192) to clarify the same,

“The metrics $Acc_{aff}$ and $Acc_{rem}$ were termed ”Corrected Accuracy” $(Acc_{corr})$ and “Retain Accuracy” $({Acc}_{retain})$ respectively by [1]. We chose alternative names to explicitly state which data distribution accuracy is measured on. In Section 5.1, we further specify what the "affected distribution” and “remaining entities” are for the different evaluation types we study.”

[1] Shashwat Goel, Ameya Prabhu, Philip Torr, Ponnurangam Kumaraguru, & Amartya Sanyal (2024). Corrective Machine Unlearning. Transactions on Machine Learning Research.

W2: The paper could benefit from a more detailed discussion on why malicious node additions degrade GNN performance.

We have now added further context on graph robustness to include literature on node injections and robust pretraining as suggested, including citations mentioned in the review in Section 2 (L110-115). Thank you for pointing out these relevant papers!

W3: Correct the typo “th” to “the” in Line 432, Page 9.

We’ve now fixed this typo, and have gone through the manuscript to check for other typos too. Thank you for pointing this out.

We are glad the reviewer found our experiments comprehensive and message coherent. We thank them for the questions and ideas for ablating the affected node identification part of our method. We address the weaknesses (W) below, and highlighted how we updated our paper to incorporate your suggestions. We hope this improves the soundness, contribution and overall rating of our work.

W1: What is the inverse features?

Thank you for pointing out this omission. We have now made the definition of ‘inverse’ features clearer in the paper (Section 4.1 L219-222). We define ‘inverse’ features as: $\vec{1} - X_v$, where $X_v$ is a one-hot encoding feature vector of all $v \in S_m$.

How will the chosen nodes influence the results? I suggest the authors provide empirical analysis of the $k$%.

We investigate the impact of selecting top $k$% nodes in our experiment, as detailed in Figure 13 (left), Appendix I. While varying $k$ % did not significantly change results, completely removing the step ($k=0$) degraded the performance. This suggests that performing contrastive unlearning on even a small percentage of nodes has a significant impact. Moreover, maintaining a low $k$% ($k \in [2,30]$) ensures computational efficiency without compromising performance, as shown in Figure 13 (right), which is particularly important for unlearning methods.

W2: When calculating the logits change, should the GNN be trained well? I suggest the authors provide more analysis of how the GNN's performance influence on the logits change.

Thank you for the suggestion. We have added another experiment to clarify this, with results presented in Figure 12, Appendix I. We used the top $k$% (fixed at $4$%) most affected nodes from previous checkpoints as anchors on the fully trained GNN, and observe that the GNN's training stage did not significantly influence the $Acc_{aff}$. However, if we select $4$% nodes randomly, we find a drop in performance. This points to the robustness of using logits change (computed at any model checkpoint) as a measure to identify potentially influenced nodes, as it leads to good downstream unlearning performance.

W3: How about the convergence of the algorithm? How to set the parameters of the optimizer?

As per your suggestion, we have added Figure 11 under Appendix H, where we plot the loss after the last epoch of each step, where step is as defined in Algorithm 1 in Appendix B. The ascent loss on $S_f$ (Figure 11 middle) continually increases which is an expected and intended behaviour with gradient ascent. On the other hand, the descent loss on $S \setminus S_f$ (Figure 11 right) and the contrastive loss (Figure 11 left) converge.

We supply the Adam optimizer for each unlearning component (contrastive, ascent, descent separately) with the following hyperparameters:

• Learning rate: Varies across settings based on hyperparameter search.
• Weight decay: Part of the hyperparameter search, but we see the optimal value is always found to be $10^{-6}$,
• Adam specific parameters: \beta_1$$\beta_2, $\epsilon$. Used the default values $0.9$, $0.999$, $1e-08$ respectively.

Apart from this, all tunable hyperparameters for our method are explained in the README.md in the code (which will be made public upon acceptance) provided in the supplementary, along with the exact hyperparameters for reproducibility.

W4: I suggest the authors theoretically analyze why selecting the top K% nodes with the largest logit change and using the contrastive unlearning objective work.

We agree that a lack of theoretical guarantees is a weakness of our work, and have now added a line to mention this in the Limitations, L534-535.

We use the largest logit changes to identify affected nodes, though more sophisticated techniques like influence functions [1] could improve performance. As a sanity check, we note that it still achieves higher $Acc_{aff}$ than selecting random $k$% nodes in the n-hop neighbourhood (Figure 12).

We incorporated contrastive unlearning for its unsupervised nature, which makes our method usable without labels and counteracts the effect of fine-tuning on incorrect labels when the manipulated data is only partially discovered. Leveraging contrastive learning's well-established theoretical framework [2], we adapt the technique to push manipulated samples away from clean neighbours in the representation space (Figure 3).

[1] Zizhang Chen, Peizhao Li, Hongfu Liu, & Pengyu Hong (2023). Characterizing the Influence of Graph Elements. In The Eleventh International Conference on Learning Representations.

[2] Arora, S., Khandeparkar, H., Khodak, M., Plevrakis, O., & Saunshi, N. (2019). A Theoretical Analysis of Contrastive Unsupervised Representation Learning. CoRR, abs/1902.09229. Retrieved from http://arxiv.org/abs/1902.09229

We are glad that the reviewer found the paper well-written and the problem interesting. We thank the reviewer for recognizing that existing methods fall short, and that our proposed method is effective. Below we respond to the weaknesses (W). We hope the updates we made to our paper improve the contribution and overall rating of our work.

W1: Suppose we have a two-layer GNN; in that case, a node will only impact its $2$-hop neighbors through message passing. This makes it confusing why, in Sec 4.1, the authors propose using output logits change as an indicator to find the most affected node.

You are correct in mentioning that a node’s impact is limited to its $n$-hop neighbourhood for a n-layer GNN. What we find is that using the most affected subset of the nodes in the n-hop neighbourhood for contrastive unlearning is sufficient, and greatly improves efficiency. We have clarified that the motivation is efficiency in L217 of Section 4. We have now added analysis on the effect of varying the fraction of the $n$-hop neighbourhood used for contrastive unlearning in Figure 13, Appendix Section I shows that using a larger fraction of $n$-hop neighbourhood (apart from the top-$k$% chosen by our method) for contrastive unlearning does not lead to better unlearning performance while adding computational cost.

W2: I believe gradient ascent on would significantly reduce model utility.

As suggested, we have added an additional experiment to verify this, with results presented in Table 7 under Appendix F. We set the fraction of nodes to be unlearnt as $25$% (more than $2$x the previous size) of all training nodes on the Amazon dataset and perform unlearning. Cognac performs well even at a large deletion size, and is not adversely affected by it. This could be attributed to a tunable learning rate of the gradient ascent component of our algorithm: i.e. if the performance of the method is adversely affected due the destabilisation by the ascent, the learning rate is reduced automatically during the hyperparameter search.

W3: The experiments are not comprehensive, as they only focus on small graph datasets.

We test our method against $6$ baselines with $2$ adversarial evaluations across $3$ datasets, and $5$ varying fractions of manipulated data, with several ablations of our method. Overall, we perform over $3000$ runs per unlearning method to try our different hyperparameters and converge on the best performances for each setting. We have chosen three large, and relatively balanced datasets for our experiments: Cora Full, an extended version of the Cora dataset consisting of $18,800$ nodes and $125,370$ edges (the commonly referenced Cora consists of $2708$ nodes, and $5429$ edges with $7$ classes); the CS dataset with $18,333$ nodes and $163,788$ edges; and Amazon-Photos with $7,487$ nodes and $238,086$ edges. As also mentioned by Reviewer LxzZ and A7wi, we believe this makes our experiments comprehensive for the Graph ML domain.

Nevertheless, we have now added results on the binary label flip attack across three benchmark datasets used in prior graph unlearning literature, (Amazon-Computers [1], Physics [1], DBLP [2]) where we test our method and the best-performing baselines. Note that Physics has almost $500$k edges, $2$x more than our previous biggest dataset. Details about these datasets are provided in Table 8. From Figure 10, we can observe that Cognac still outperforms the baselines in most of the settings and matches the Oracle’s performance in the new datasets.

[1] Shchur, O., Mumme, M., Bojchevski, A., & Günnemann, S. (2018). Pitfalls of graph neural network evaluation. arXiv preprint arXiv:1811.05868

[2] Tang, J., Zhang, J., Yao, L., Li, J., Zhang, L., & Su, Z. (2008). Arnetminer: extraction and mining of academic social networks. In Proceedings of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining (pp. 990–998)

W3: There are many larger datasets, such as OGB-arXiv.

We appreciate your suggestion of the OGB-arXiv [1] dataset. We did not have the compute resources to run this earlier, but given the reviewer thinks this point is crucial, procured external compute to expand our experiments to this larger dataset. As shown in Table 9, Appendix G, Cognac consistently outperforms all baselines and Retrain from Scratch. For ease, we also include the table below in this response. Moreover, to confirm that our GCN model is well-trained, we checked that the Oracle GCN reaches a micro accuracy of $71.15$% on the OGB-arXiv test set, matching the performance reported by [2]. Note that, due to limitations in time and compute, we were only able to run a subset of the settings on this larger dataset. In the camera ready, we will add results across all settings studied.

We hope this resolves all your concerns and is sufficient to recommend acceptance!

Table: Node Unlearning results on the OGB-arXiv dataset for $S_f/S_m \mathbf{= 0.25, 1.00}$. We observe that the Cognac method outperforms all baseline approaches, including Retrain, in both correcting the $Acc_{aff}$ metric and maintaining the $Acc_{rem}$ metric.

[1] Wang, K., Shen, Z., Huang, C., Wu, C. H., Dong, Y., & Kanakia, A. (2020). Microsoft academic graph: When experts are not enough. Quantitative Science Studies, 1(1), 396-413

[2] Kipf, T. N., & Welling, M. (2016). Semi-supervised classification with graph convolutional networks. arXiv preprint arXiv:1609.02907

We thank the reviewers for engaging in discussions. Consequently, we have added more details in a revised version, summarised below:

Table 9 (Appendix G, Page 19): Added experiment of Node Unlearning on OGB-arXiv dataset as requested. We note that OGB-arXiv is a much larger dataset than benchmarks used in our work earlier, with $169,343$ nodes and $1,166,243$ edges. On this dataset as well, Cognac outperforms all baselines including Retrain from Scratch by a significant margin.

Section 3 (L180-192): Clarified that evaluation metrics are borrowed from [1].

Table 8 (Appendix G, Page 19): We have added details of additional datasets used in the experiments performed during the rebuttal.

[1] Shashwat Goel, Ameya Prabhu, Philip Torr, Ponnurangam Kumaraguru, & Amartya Sanyal (2024). Corrective Machine Unlearning. Transactions on Machine Learning Research.