Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper proposes a graph unlearning approach for linear graph neural networks, with ridge regression as the objective. The authors derive closed form solution for deleting nodes in the graph. For experiments, the authors propose to insert extra binary feature indicating whether the node is to be removed in node features to validate if the unlearned model has prediction power of the extra binary feature. The authors also compare the model closeness of unlearned model re-trained model. Other extensive experiment results are also shown to show the effectiveness and efficiency of the proposed approach. The approach can be extended to non-linear GNN case by pre-training the feature extraction part with non-deletable data and only train a linear classifier.
strength_and_weaknesses: Strength
1. The proposed approach is simple and efficient, which does not scale with the dataset size
2. The idea of inserting extra binary feature to check the unlearning quality is novel and useful
3. Experiment results are promising

Weaknesses
1. The closed form solution in derived with Sherman–Morrison–Woodbury formula, and the authors only show the derivation for only one row deleted. Maybe I miss something but I do not think it can be directly extend to matrix case (multiple rows) with the same formula.
2. The approach is only for linear GNN, which is very limited. Although the authors argue that other graph unlearning algorithms also requires that for theoretical guarantee, I think in general the other approaches should work for non-linear case without theoretical guarantee. But the proposed work does not work for non-linear case
3. The proposed connection to non-linear GNN makes sense but not practical. In industry use case no users' data should be forbidden to delete, and using public dataset to train the feature extractor could deteriorate the model performance. For section 5.3 the authors still use the same training dataset to train the feature extractor, the statement could be validated better if the authors could find some other dataset to train the feature extractor.
clarity,_quality,_novelty_and_reproducibility: Clarity

The paper is clearly written and easy to understand.

Quality

I am worried on the closed form solution derived with Sherman–Morrison–Woodbury formula for multi-row update. I expect the authors to clarify on that. Experiments are with high quality.

Novelty 

The idea of inserting extra binary feature to check the unlearning quality is novel and useful

Reproducibility

For replicating the results reported in this submission, it is not for now
summary_of_the_review: The paper shows novelty on evaluating the quality of unlearning. However, there are still many limitations of the approach as it only works for linear GNN, I do not recommend to accept it now.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper proposes a computationally efficient exact unlearning approach called GraphEditor on graph neural networks. The main challenge of unlearning on graph data is the interconnection between neighboring nodes makes elimination of influence from a given deleted node nontrivial. This paper considers a linearized GNN, in which the influence of a given node on the model weight could be explicitly written out and computed. GraphEditor is thus guaranteed to remove all information related to deleted nodes. The author also introduce a "deleted data replay test" to validate whether information is actually forgotten.
strength_and_weaknesses: Strengths:

- GraphEditor enables the influence of deleted node to have closed form and can be explicitly computed, which theoretically guarantees the exact unlearning.

- The proposed approach flexibly supports various scenarios including node/edge updating and also introduces subgraph sampling to address scalability issues.

Weaknesses:

- The linearity assumption limits the technical contribution. the authors do provide some discussions on why linear GNN may be expressive enough and existing literature also uses linearity. To better understand the technical contribution of this paper, please clarify more on the essential barrier when transferring proposed approach and its theoretical guarantee to nonlinearity, i.e. why it is nontrivial in its current form and how potentially we could make progress. without such discussion, there is a significant logic gap from Sec 4.2 to Sec 4.4.

- in Section 4.1, the paper proposes to use ridge regression to initialize and fine-tune using a different task-related loss term (e.g. cross-entropy loss) with a small number of iterations. 

     - Is there potential issue that the unlearning is specific to a certain loss structure (ridge loss) while is insufficient for another. 
     - Please discuss whether the given guarantee is generalizable to cross entropy loss, where the experiments are mainly about.

- does the competing baseline also uses some trick like fine-tuning to boost performance in experiments, to ensure a fair comparison? 

- is there a guarantee that fine-tuning from such initialization is faster than retrain to get comparable performance?

clarity,_quality,_novelty_and_reproducibility: The presentation is in general clear. Please address some of the points raised in weaknesses for better clarity.
 
The paper ensembles a lot of materials to solve a very important but relatively under-explored problem. Though some strong assumption (e.g. linearity) limits its technical challenge and novelty, its empirical evaluation is convincing, and it is a good complement to the existing literature.

Though I do not check the proof and codes in great detail, I believe it is technically sound.
summary_of_the_review: This paper is technically solid and provides a good contribution to graph unlearning problem. Though the theoretical contribution is restricted by the linearity constraint, it serves as a good starting point. I enjoy reading the paper and vote for acceptance.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper studies graph unlearning, a problem on how to quickly adapt the GNN after removing/adding a subgraph like nodes and edges. This work proposes GraphEditor, an efficient learning algorithm that does not need GNN retraining, with motivation on the linear GNN.

strength_and_weaknesses: Strengths:
- Graph unlearning is an interesting problem, especially in the large-scale graph setting.
- I’m not an expert on graph unlearning, but the experiments seem to prove the effectiveness of GraphEditor algorithm. I’m open to hear comments from other reviewers on this.


Weakness:
- The new metric, “deleted data reply test”, is interesting, but the logic is not clear. A better logic is that, what this measure is about, and how existing methods fail on this method. Then it can be more reasonable to introduce the GraphEditor algorithm. The current logic is that, in Sec 3, the authors propose a metric for data removal guarantee, then without further explanation, goes directly to introducing the algorithm Sec 4. This logic is not clear to the readers.

- In Sec 4, The three main functions can be renamed, e.g., find-W is actually the GNN learning. Similarly for remove_data() and add_data(), where the namings are confusing.

- For Lemma 1, there are some places I want to confirm with the authors.
  - Where is L defined in Lemma 1? I can only find it implied in Sec 3, if it’s the number of GNN layers. Can authors confirm this?
  - If so, then Lemma 1 is straightforward for linear GNN. It is essentially saying that for L-layer linear GNN, the effect of unlearning is restricted in the 2L-hop neighborhood.
  - Now the authors are considering a simplieid case without activation function. What if the non-linear activation functions are considered? I didn’t find this explicitly discussed in Sec 4.4. Sec 4.2 makes sense because the parameters can be learned in a closed-form, which is not the case for Sec 4.4, and authors say just replacing the linear GNN with non-linear GNN is not convincing.


- Another question on the backbone modeling. So this work is focusing on the GNN. But actually the most recent works [1,2] find that MLP can achieve similar performance as GNN. Then the unlearning can much simpler in that case. Does author have any comment on this?

clarity,_quality,_novelty_and_reproducibility: The writing of this paper can be further improved. Here are some aditional minor points:
- Briefly introduce unlearning in the abstract, to make it more clear.
- A pipeline figure is better than algorithm (pseudocode) for illustration.

summary_of_the_review: My biggest concern is on the generalization of Lemma 1 to non-linear GNN. If it's still an open challenge, as mentioned by the authors, then maybe Lemma 1 can be skipped, and authors can consider telling the story from another direction.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper studies the problem of machine unlearning on graphs. The authors claim an exact unlearning method (GraphEditor) that supports node/edge deletion/addition and node feature update. The experiments demonstrate the efficiency, high performance, and ability of unlearning of the method.
strength_and_weaknesses: ### Strengths

- GraphEditor demonstrates great empirical results in terms of efficiency and test accuracy.

- The related works are extensive.

### Weaknesses

- The proposed approach is only proved to be an exact unlearning method for the ridge regression problem on graphs. Yet the authors claim to study the node classification problem, which usually uses either logistic regression or cross-entropy loss.

- The overall writing of the paper is quite misleading, assuming the first weakness is valid.

- The GraphEditor ***cannot*** extend to non-linear models such as general GNNs. The authors only use pretrained GNNs (on private datasets) as a ***fixed*** feature extractor. The learning and unlearning processes apply only to linear classifiers on public datasets.

- The setting of testing the unlearning ability of approximate unlearning methods is unclear. Do the authors use ridge regression or cross-entropy loss?

### Detail comments

Graph unlearning is a very important problem that is just recently been aware by the community. I was very excited at the beginning when I see the claims and fascinating experimental results. Unfortunately, I found some critical issues regarding the method itself which I discussed below. I am more than happy to change my mind if the authors can correct me.

The major and most critical issue is that the paper overclaims its contribution and ignores the important assumption of GraphEditor when conducting the experiments. Note that all analyses pertaining to GraphEditor rely on the structure of the ***ridge regression problem*** (on graphs), see Section 4.1. For example, the key part of the method is to show that the resulting unlearned weights $W_{upd}$ is ***identical*** to the one retraining from scratch $W^{u}_\star$ (when the training algorithm is guaranteed to converge to the unique optimum). The authors rely on the closed-form solution and the quadradic nature of the problem to establish their deletion and update steps (Section 4.2). However, the real task that we aim to learn is the classification problem, which usually adopts logistic loss or cross-entropy loss. Note that the authors also claim to study the classification problem and conduct experiments on node classification tasks. Unfortunately, the analysis and guarantee established in Section 4.2 cannot generalize to even logistic loss. Hence, the proposed GraphEditor unlearning approach is ***not*** an exact unlearning method in general graph representation learning and I feel the authors overclaim their contributions.

Note that in the experiments, the authors also seem to leverage cross-entropy loss (softmax) as stated in Section 5.2. Thus, the GraphEditor is not guaranteed as an exact unlearning method in theory throughout the experiments in Section 5. Note that the proposed deleted data replay test is not sufficient to validate whether the model is exactly unlearned or not. The only criterion to validate whether GraphEditor is an exact unlearning method is to check if its resulting weights after unlearning $W_{upd}$ is ***identical*** to the one retraining from scratch $W^u_\star$ in distribution. Unfortunately, it is unlikely to verify whether $W_{upd}$ and $W^u_\star$ are identical in distribution in practice. This is why theoretical guarantees are very important and critical in the context of machine unlearning, especially when one claims a method to be an exact unlearning method.

Interestingly, if we consider the special case where all nodes in the graph are isolated (i.e. the propagation matrix is merely an identity matrix), the situation falls back to the standard machine unlearning problem. Consider again the case of the classification task, which is the problem studied by [1] under the approximate unlearning criteria. Apparently, GraphEditor is also claimed to be an exact unlearning method in this scenario. Due to the superior time complexity demonstrated by the authors, why does one even need approximate unlearning approaches such as the one proposed in [1]? Notably, Guo et al. [1] already mentioned that when the problem is ridge regression (i.e. least-squared loss with $\ell_2$ regularization), then the approach therein is an exact unlearning method (Section 3.2). This also emphasizes the fact that ridge regression is less interesting for machine unlearning.

The other major issue is the claim of GraphEditor being able to generalize to non-linear graph models such as GNNs. Note that the authors only adopt the approach proposed in [1] and [2], which simply pretrain non-linear models on private datasets as ***fixed*** feature extractors. The learning and unlearning processes apply only to linear classifiers on public datasets. I think the statements in the abstract and the introduction on GraphEditor can be generalized to non-linear models such as GNNs are overclaimed and misleading.

I would suggest the authors emphasize that GraphEditor only works with ridge regression problems, albeit this greatly diminishes the contribution of the paper. Also, I would suggest the authors to tone down the claim on the generalization ability of GraphEditor to non-linear models.

### References

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

[2] Mixed-privacy forgetting in deep networks, Golatkar et al., CVPR 2021.

clarity,_quality,_novelty_and_reproducibility: - Clarity: The paper does not emphasize the key assumption that GraphEditor only applies to ridge regression. Also, please clearly specify whether ridge regression or cross-entropy loss is used in the experiment. Overall, I feel the paper is misleading.

- Quality: For ridge regression, the results and proofs are correct. However, the main task considered in the paper is the classification problem, where logistic loss or cross-entropy loss should be considered.

- Novelty: The novelty of the paper is limited. The analysis on ridge regression is quite standard.

- Reproducibility: The experiment code is attached. However, the readme file is empty and does not specify the environment and package dependency to run the code.

summary_of_the_review: The authors proposed GraphEditor and claim it to be an exact unlearning method for general graph representation learning, especially node classification problems. However, the unlearning guarantee relies on the problem being the ridge regression problem and does not generalize to the other popular classification loss such as logistic loss and cross-entropy loss. The experiments seem to leverage cross-entropy loss which makes the result meaningless. I feel the contribution is overclaimed and the assumption on ridge regression needs to be emphasized. Otherwise, the paper is misleading in its current form. I might misunderstand the paper and I am more than happy to change my mind if the authors can correct me.

================post rebuttal===========================

I thank the authors for their effort in addressing my major concern. Now I agree that GraphEditor is indeed an exact unlearning method. Thus I increase my rating accordingly. However, some new concerns arise (see my follow-up comments below). Overall, I still think the manuscript should be further improved before publication, especially in its clarity.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The paper presents GraphEditor, a new efficient method for graph representation learning and unlearning. Graph unlearning is an important task with many privacy applications, in this task one is interested in removing the effect of a node from the pre-trained graph representation learning of a graph efficiently.

The presented method is interesting and it presents nice theoretical and experimental results for linear GNN.

The main drawback of the paper is that almost all the GNN used are non linear and so the current result has limited applicability. In addition, it is also hard to imagine that the current approach could be generalized to more complex network structure because it heavily relies on the linear structure of the problem.

In addition, the theoretical result is not particularly novel or surprising in the linear setting.

Overall, the paper contains some interesting ideas but the paper does not meet the ICLR acceptance bar.
justification_for_why_not_higher_score: The presentation is a bit misleading and limitation of the current approach are not clearly presented. Paper may be interesting but it needs major rewriting.
Decision: Reject