Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper studies machine unlearning on graph neural networks (GNNs) by analyzing influence function. The authors identify that simply applying influence function on GNNs for edge removal is problematic due to node dependency. As such, the authors propose to estimate the influence function by upweighting the set of all affected nodes. Then the influence is obtained as the reverse of Hessian matrix multiplied by the gradient vector. And conjugate gradient is applied to reduce the computational cost. Experimental results demonstrate the effectiveness of the proposed EraEdge in terms of the indistinguishability betweem model parameters and the efficiency of the proposed EraEdge in terms of running time.
strength_and_weaknesses: Strengths:
- Unlearning on GNNs is less studied, and there is no existing works on influence function-based GNN unlearning.
- The paper is overall easy to follow.
- The experimental results demonstrate that EraEdge can efficiently unlearn a set of edges via the indistinguishability between the retrained model parameters and the unlearned model parameters.

Concerns/Questions:
- Many existing influence function-based approximate unlearning techniques (see references below) add Gaussian noises to preserve data privacy. I am wondering why such noise is not needed in EraEdge for data privacy?
[1] https://arxiv.org/abs/1911.04933
[2] https://arxiv.org/abs/1911.03030
[3] https://arxiv.org/abs/2106.04378 
[4] https://arxiv.org/abs/2006.14755
[5] https://arxiv.org/abs/2007.02923
[6] https://arxiv.org/abs/2012.13431
[7] https://arxiv.org/abs/2110.11891
[8] https://arxiv.org/abs/2103.03279
- Existing works often solve Eq. (10)-like equation with Hessian-vector product (HVP). What is the key limitation of using HVP to solve Eq. (10)? If HVP can be used as well, what is the benefit of conjugate gradient over HVP?
- I doubt that the indistinguishability in the GNN output necessarily mean the data is removed. Similar concern also appear in (Guo et al. 2020) even for linear and convex classifier like logistic regression, not to mention the nonconvexity of GNNs. It is better to study the privacy of this data removal mechanism like how they are studied in differential privacy (e.g., through membership inference attack).
- How would EraEdge perform when we sequantially delete multiple batches of edges? In many real-world scenarios, it is uncommon that the model will be only unlearned once.
clarity,_quality,_novelty_and_reproducibility: The paper is overall novel and easy to follow.
summary_of_the_review: While the paper is novel in terms of its technical aspect, I have a few concerns on the technical details on the privacy of this unlearning approach. In terms of writing, the paper is clear and easy to follow.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: An unlearning algorithm for graph neural networks is proposed in the paper. The paper tries to find the difference between the upweighted model and the original model by utilizing a hessian-based approximation, which can be solved by investigating the corresponding linear system with conjugate gradient methods. The found difference is then added to the original model to obtain the retrained parameters.
strength_and_weaknesses: Strength

1. The proposed method has a good applicability and can work with most existing variants of GNNs.

2. The paper is a computationally and memory efficient algorithm.

3. The algorithm is evaluated on a number of three real datasets to demonstrate the effectiveness of the proposed approach for graph unlearning.

Weakness

1. Upweighting using the influence function merely approximates the retrained parameters and provides no theoretical error bound on non-convex loss functions. This work then constructs another approximation of this already fuzzy target to obtain the unlearnt model. One can hardly be convinced that such a method will result in a set of parameters that resemble the retrained model. The proposed scheme also provides no means of generating a verification of data removal, which is utterly vital for a data provider.

2. Adding a scaled identity matrix to the hessian to make it positive definite only accounts for the non-invertible problem. It still destroys the basis of Theorem 2, which requires the loss function to be globally convex. This assumption is too strong to make any meaningful sense in real-world scenarios. Also, Theorem 2 seems to be only an adaptation in notations of eq.(3) in [1].

3. In scenarios where the graph is relatively dense and the GCN is deep (e.g., as described in [2]), the affected set of nodes, as defined in the paper, can easily become the whole graph, which sort of destroys the purpose of the paper, which is fast unlearning.

4. Unlearning efficacy is only evaluated for the proposed model without comparison with other baselines, unlike classification accuracy. Also, experiments like the behavior difference between the unlearning model and the retrained model on the unlearned part of the dataset should be added to demonstrate the algorithm's efficacy further.

[1] Pang Wei Koh and Percy Liang. “Understanding Black-box Predictions via Influence Functions.” In: Proceedings of the 34th International Conference on Machine Learning, ICML 2017, Sydney, NSW, Australia, 6-11 August 2017. Ed. by Doina Precup and Yee Whye Teh. Vol. 70. Proceedings of Machine Learning Research. PMLR, 2017, pp. 1885–1894.

[2] Guohao Li et al. “DeepGCNs: Can GCNs Go As Deep As CNNs?” In: 2019 IEEE/CVF International Conference on Computer Vision, ICCV 2019, Seoul, Korea (South), October 27 - November 2, 2019. IEEE, 2019, pp. 9266–9275.
clarity,_quality,_novelty_and_reproducibility: It is understandable to a large extent, but parts of the paper need more work.
summary_of_the_review: In general, the studied problem is interesting and important. In addition, the methodology is principled with three major merits as discussed above. However, the work still has some unaddressed concerns to well justify its technical and empirical contributions.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This work studies a notion of unlearning for graph neural networks. Basically, given a set of edges removed from the graph, it tries to address how to fast adjust the model parameters to make the model behave like the model retrained on the graph with edge removal while without retraining. The technical idea is to analyze the influence of the edge removal on the model parameters given the convex and differentiable assumption of the objective. Experiments show some superiority of the proposed method. 
strength_and_weaknesses: Strengthes:
1. Graph unlearning is a relatively novel concept. The problem studies here is interesting. Also, the analysis and argument sound reasonable and solid. 

2. The paper is written very well. I appreciate the logic flow. The motivation and the exposition of the approach is clear. 

Weaknesses:
1. Here is my biggest concern. Although I overall think the technique in this paper is reasonable and the studied problem is interesting. Unfortunately, recently, I have read a relevant paper on graph unlearning published four months ago [1], which I think has studies a far more extensive setting on graph unlearning than this work. Although that work is just an arxiv paper, I cannot view it as a concurrent work because the content studied in [1], in my opinion, is broader and provides more insights than the setting studied in this work. I know it is tough for the authors but I cannot ignore this. Therefore, this work's statement saying this is the only work that considers unlearning in GNN, which is an over-claiming. 

Moreover, [1] studies both node and edge unlearning, while this work only studies edge unlearning. In my opinion, node unlearning is more crucial because a user (typically corresponding to a node), if not wanting to disclose her data, will ask to remove this node from the graph. Moreover, I think [1] also tells more data insights due to their analytic bounds such as the dependence of unlearning performance on node degrees, etc. 

I can see some adopted detailed techniques are different, such as [1] using SGC (linear model) while this paper using convex assumptions. My feeling is that if this work may discuss both edge/node unlearning and also provides further insights on how graph structure affects the unlearning performance, I would appreciate the technical difference in this paper and may support an acceptance. However, the current setting of this paper is still kind of narrow compared to [1].

2. This work writes well and is easy to follow. However, I feel there is a little bit misleading in the introduction. For example, after reading the introduction, I thought the paper would like to touch non-convex settings in theory (the fourth paragraph of intro). However, the later analysis is based on convex assumption. Moreover, in intro, the authors say "empirical studies on tradeoff between unlearning efficiency, accuracy, unlearning efficacy". However, in the experiments, I can only see the list of these results without tradeoff. My understanding of the tradeoff would be about, e.g., high accuracy/efficacy  requires less efficiency, and the proposed method has a work to balance these aspects. Unfortunately, I do not think the proposed approach has such flexibility. 

3. Moreover, I am not clear how the averaged JSD is computed. I can think of there are multiple ways to define averaged JSD. Do you mean averaging over testing samples? or averaging over classes? I think a math equation is needed to show this. 

4. Fig.4 the first row has wrong subtitles I think. 

5. Regarding experiments, how do you remove edges, randomly and how many times, or? Also, I do not see how to tune the model and how to make sure the comparison between model retraining and the proposed method fair, e.g., same model size? how about learning rate?

6. Since efficiency is one topic of interest in this work, the used graphs are in general too small.  



[1] Certified Graph Unlearning, Chien et al., 2022. 
clarity,_quality,_novelty_and_reproducibility: I think I have made these points clear in the above response. 

Clarity: Generally easy to follow while some explanations on experiment settings are missed

Quality: Okay, but not extensive enough given previous works

Novelty: Topic is interesting while there are a few contributions being over-claimed. 

Reproducibility: Good while I did not see how to tune hyperparameters and some detailed experiment settings are missed. 
summary_of_the_review: The studied problem is interesting. The adopted technique is reasonable. However, the novelty and true technical contributions are not sufficient given previous works.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: The authors study the machine unlearning problem on graphs, where they focus on the edge unlearning problem. The proposed method, EraEdge, is based on subtracting the *influence* of the unlearned edges in a heuristic manner. The experiments demonstrate the efficiency and accuracy of the proposed method. They also show that the output of the unlearned model is close to the one retraining from scratch.
strength_and_weaknesses: ### Strengths

- EraEdge can be applied to non-linear models such as GNNs.

- The methods seem to be efficient in terms of time complexity.

- The problem of machine unlearning on graphs is an important problem.

### Weaknesses

- The proposed unlearning definition is not rigorous and heuristic-based. Also, having approximately close model output does not guarantee privacy.

- The proposed method is an ***approximate unlearning*** method ***without theoretical guarantee*** (i.e. heuristic based). 

- The related works about machine unlearning on graphs are not extensive enough. Also, differential privacy based GNNs should also be discussed.

- In the experiment, the authors use random Gaussian vectors as node features instead of the default features. How does the result look like if we use the default features?

- (Minor) The paper focuses on the edge unlearning problem, while the really important problem is the node unlearning problem.

### Detail comments

While the problem of machine unlearning on graphs is very important, one should be extremely careful when they claim a method can achieve unlearning. Machine unlearning can be roughly characterized into two categories, exact and approximate unlearning. For exact unlearning methods, we require the unlearned models to be ***identical*** (in distribution) to the one retraining from scratch, examples include sharding-based method as mentioned by the authors. Approximate unlearning requires the unlearned model to be *indistinguishable* from the one retraining from scratch. Note that one should be extremely careful when defining the *indistinguishability*, as an inappropriate definition could lead to zero privacy in some cases (see [1] for a simple example). Apparently, the proposed definition of unlearning belongs to approximate unlearning and the authors should clearly specify it. Otherwise, the paper can be misleading to the readers.

One rigorous definition of approximate unlearning is via differential privacy type of definition in the parameter space, which was proposed in [1]. The proposed approximate unlearning method therein comes with a differential privacy type of theoretical guarantee. The other line of work such as [2] proposed a heuristic-based measure, which is more similar to the one proposed in this paper. However, the proposed method in [2] involves ***privacy noise*** to *blur out* the potentially leaked information. In contrast, EraEdge does not add any privacy noise to protect the privacy. Most importantly, the authors of [2] conduct extensive experiments and multiple metrics to examine the effectiveness of unlearning their method. On the other hand, the authors of this paper merely examine the closeness of the model output which can be problematic following the same rationale in the counterexample provided in [1] (i.e. the paragraph in the title *Insufficiency of parametric indistinguishability*). Hence, I doubt how private it is for EraEdge on the unlearned data. I would suggest the authors conduct similar extensive experiments to [2], or examine the ability of the proposed method against some membership inference attack methods.

Regarding the related works, the authors miss several recent papers about machine unlearning on graphs. Please check the survey paper [3] for a collection of papers about machine unlearning on graphs, where the node unlearning problem is also studied. It is also worth mentioning the recent development of differential private GNNs, as differential private models automatically achieve (approximate) unlearning *without* any update [1].

In summary, my main concern about the paper is the privacy of the proposed method. Since EraEdge is not an exact unlearning approach, one has to be extremely careful about the choice of *indistinguishability*. Also, most of the existing approximate machine unlearning methods require adding privacy noise to burr out the information from the approximation error. However, EraEdge does not leverage any privacy noise and thus any approximate error can potentially lead to severe privacy issues (i.e. adversarial attacks). In the empirical evaluation, the authors do not conduct enough experiments to demonstrate the privacy of their EraEdge. This should be done for heuristic-based methods such as those in [2]. Hence, I feel the paper needs a major revision before publishing.

### References

[1] Certified data removal from machine learning models, Guo et al., ICML 2020.

[2] Eternal Sunshine of the Spotless Net: Selective Forgetting in Deep Networks, Golatkar et al., CVPR 2020.

[3] A Survey of Machine Unlearning, Nguyen et al., 2022.

clarity,_quality,_novelty_and_reproducibility: - Clarity: The authors should specify the difference between exact and approximate unlearning. Note that their main baseline methods such as Retrain and GraphEraser are exact unlearning methods while the proposed method is an approximate unlearning method without theoretical guarantees. Hence, merely comparing the test accuracy and time complexity is not satisfied.

- Quality: I have concerns about the privacy of EraEdge method.

- Novelty: Most of the analysis and techniques are from the existing literature. The main novelty comes from applying them to graphs, yet the novelty of this extension used in the papers seems limited. 

- Reproducibility: The authors do not provide their experimental code. Details about hyperparameters are also missing.

summary_of_the_review: My major concern focuses on how private the proposed unlearning method is. I also think the authors should specify the difference between exact and approximate unlearning, otherwise the result can be misleading. For example, EraEdge is an approximate unlearning method while retraining from scratch is an exact unlearning method. Once we specify this difference, one can naturally ask how EraEdge *trade-off* privacy for time complexity and test accuracy. I also find the experiment setting a bit weird, where the authors replace the default node features with random Gaussian vectors. This is an artificial setting, and I wonder how the result looks like if the authors use default node features. In summary, I feel the paper needs a major revision before publishing.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: Based on the collected information from all of reviewers and my personal judgment, I can make the recommendation on this paper, **rejection**. Here are the comments that I summarized, which include my opinion and evidence.

**Research Problem**

The authors consider the graph unlearning problem, which can be regarded as a novel but less explored problem.

**Presentation**

This paper is easy to read, but difficult to follow. I read this paper more than three times and found this paper is less coherent. I have the same feeling with Reviewer wUNT. In the abstract, the authors mentioned the challenges in non-convexity nature of GNNs and large scale of input graph. Unfortunately, this paper does not tackle the above two points. 

**Challenge Analysis or Motivation**

The challenge analysis is missing. I did not find anything about it in the original version. In the updated version, the authors mention they aim to design the efficient approximate unlearning solutions that are model-agnostic. I believe the proposed technique struggles to handle generalized PageRank. 

**Philosophy**

Without a clear challenge analysis, it is unclear the philosophy to deal with the challenges. 

**Technical Contribution**

(1) The authors extend Koh & Liang’s work from the tabular data to graph data without rigorous support, especially in the non-convex scenarios. When dealing with non-convexity of GNNs, it is necessary to verify such approximations are accurate enough. Lambda is a key parameter to guarantee the existence of the Hessian matrix and determine the final result; however, I do not see parameter analysis on lambda or how to set it. Moreover, removing a set of edges would bring extra group effect as well [1]. The authors need to address this issue in this scenario as well. From Figure 2, we can see the large JSD value with the increased unlearned edges.  

(2) Another technical contribution claimed by the authors is that they resolve the computational challenge on calculating the inverse of a large Hessian matrix. Unfortunately, the techniques on Page 6 are well-known, at least known to me. The authors also cited the original papers as well. Therefore, I do not regard this as a contribution point. 

(3) Two reviewers raise their concerns on privacy and provide a list of key references as well. However, privacy is not covered in the main body, but indeed it is a crucial topic in the unlearning area. Later, the authors added one more experiment on this point. I suggest the authors to add more discussions on why the proposed method can address this problem. 

**Experiments**

(1) The parameter analysis on lambda is missing. 

(2) Figure 2 does not include the results from BLPA and BEKM.

(3) I believe Reviewer wUNT would like to see some large graphs, such as Ogbn-Arixv that contains nearly 170 thousand nodes and over 2 million edges. 

No objection was raised from the reviewers on the rejection recommendation. 

[1] Koh, P. W. W., Ang, K. S., Teo, H., & Liang, P. S. (2019). On the accuracy of influence functions for measuring group effects. Advances in neural information processing systems, 32.
justification_for_why_not_higher_score: This paper does not reach the bar of ICLR, which lacks clear motivations and suffers from some technical flaws. More details can be found in my meta review.
Decision: Reject