Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper studies the problem of graph neural network unlearning. Unlike the partitioning-based unlearning strategies, the proposed solution works on two defined loss functions that reflect the target of edge deletion kind of unlearning request. One loss function measures the Deleted Edge Consistency: the predictiveness of deleted edges comparing to the nonexistent edges. The other loss function computes the Neighborhood Influence: the influence of edge deletion on local subgraphs. The unlearning process is to optimize these two loss functions over each layer, to reach the aim of unlearning about the edge deletion request. 
strength_and_weaknesses: The strengths:
1) comparing to the partitioning based models, the proposed solution doesn't need to specify partitioning parameters that may have impact on the unlearning performance.
2) the proposed method was shown to have better performance than baselines in evaluation 

The weaknesses
1) The layer-wise unlearning can be expensive. Although the number of trainable parameters to update in the unlearning process is independent of the size of the graph, the computational cost depends on the number of layers in graph neural networks.  The time complexity evaluation shows only on the 2-layer graph neural networks (GNNs). When the networks get deeper and have a larger number of parameters, the proposed model will become expensive.
2) The evaluation results were not well discussed. For example, \mathcal{E}_d is the set of edges to delete. what is  \mathcal{E}_t in Table 1 and 2?  If the target of GNNDELETE is to delete \mathcal{E}_d,  why improving the performance of GNNs on predicting the links in \mathcal{E}_d?
3) The unlearning impact should be also evaluated on other tasks. For example, if the request is to delete edges in \mathcal{E}_d, node classification performance should also be evaluated in the whole remaining graph, to see if the classification performance is retained for unaffected nodes. 
4) when the unlearning task is about nodes (deleting nodes), how the  loss functions are defined?  the evaluation in Table 3 shows the performance of MI. What about the influence on link prediction?  if a set of nodes were deleted, how the link prediction is affected? 
5) the evaluation mentioned node feature update unlearning tasks. However, there is no experiments about such tasks. 
clarity,_quality,_novelty_and_reproducibility: As given in the list of weaknesses, theses questions should be addressed. 
summary_of_the_review: The paper presents an interesting idea. However, there are several issues about evaluation results to address.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper proposes an efficient graph unlearning method based on novel formalization of two unlearning properties, namely deleted edge consistency and neighborhood influence. A model-agnostic layer-wise deletion operator is optimized via an objective based on these two properties. Empirically results on link prediction and deleted edge prediction tasks demonstrates the unlearning effect.

strength_and_weaknesses: **Strength** 
- The paper provides a clear formulation of required unlearning properties, which motivates the design of the optimization objective
- The proposed layer-wise deletion operator is efficient, flexible and provides theoretically bound for deleted edge prediction
- Extensive evaluation is conducted to showcase the performance of the proposed method  

**Weaknesses**
- Performance on node deletion task seems to be less impressive

**Questions**
- The condition of $u\in S^l_{uv}$ in Eq. (3) is a bit hard to understand under the context. Can the authors provide more explanations about when this condition will be true and what part of the extended GNN layer will take $\phi$?

- What is the difference between $\mathcal{E}_t$ (which seems to be undefined and I guess it is the test set) and $\mathcal{E}_d$? 

clarity,_quality,_novelty_and_reproducibility: This paper is well-written with providing clear formulation of unlearning properties and well motivated designs. 

The method is technically sound, and some novel ideas are proposed through problem formulation, unlearning operator design and evaluation.

Codes are provided for reproducibility.

summary_of_the_review: This work introduces some new insights to the graph unlearning problem, and the presentation is easy to follow. I believe the community should find this work interesting, thus I lean to acceptance.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This work solves the problem of graph unlearning, where a sequence of requests arrive to delete graph elements (nodes, edges) from trained graph neural networks (GNN). To unlearn information from a trained GNN, its influence on model weights must be deleted from the model. This work formalizes required properties for graph unlearning in the form of Deleted Edge Consistency and Neighborhood Influence. Then, it proposes GNNDelete, a model-agnostic layer-wise operator that optimizes both properties for unlearning tasks.
strength_and_weaknesses: Strengths
1. The two desired properties for graph unlearning effectively work as the goals of the problem.
2. The proposed DEL operator can be generally used for various types of graph models.
3. The performance of the proposed approach is significantly better than those of existing approaches.

Weaknesses
1. This work studies only link prediction, while there are other tasks such as node classification or graph classification for which GNNs are widely used. I think the proposed approach can also be applied to such tasks, since the node representations can still be used to compose an edge probability even though the model is trained for a different task. 
2. I’m not sure whether adding a new weight matrix to an existing model fits the purpose of “unlearning,” since the learned knowledge in the initial model does not change. If one can recover the knowledge of the original model by removing the added weights, isn’t it problematic in terms of privacy?
3. Eq. (1) forces the probability of a deleted edge to be close to the mean probability of all edges. However, even though e_{u, v} is perfectly deleted, i.e., if we re-train a GNN without e_{u, v}, the probability for e_{u, v} still have a variance and can be different from the average of all probabilities. I think this condition is too strong, and it will make more sense if we consider the probabilities collectively such as by comparing the mean of all deleted edges and that of all other edges. Can you support Eq. (1) empirically or theoretically?

Questions
1. What happens if we need to remove multiple edges? Should we run the algorithm multiple times? How long does it take?
2. In Theorem 2, why is it beneficial to bound the difference of the norm difference? I think the purpose of deletion is to change the edge prediction probability for e_{u, v}, not preserving it, especially when the readout function \phi is the dot product.

Minor comments
1. I think “Problem Formulation” in Section 4 should be clearer, since it is the formulation, not a description. For example, I suggest to replace the expressions like “the information of all edges” or “fails to predict”, which are not formally defined.

clarity,_quality,_novelty_and_reproducibility: - Clarify: This paper is written well and easy to understand.
- Quality: The quality is good. The desired properties for graph unlearning work effectively as the goals of the proposed approach.
- Novelty: I'm not very aware of previous works on graph unlearning, but I think the proposed approach has novelty.
- Reproducibility: The authors provide the code for reproducibility.


summary_of_the_review: This paper solves the graph unlearning problem by presenting two desired properties and designing a novel approach that satisfies the two properties. I think this paper proposes a reasonable approach for the problem with strong empirical performance, but I have a few concerns  on the generalizability and the motivations of the proposed approach. Please see the weaknesses.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: The paper proposed an unlearning method for GNN. In order to remove an edge, a patch network is attached to each layer of the original network, which are MLPs that only affects nodes in the neighborhood of the target edges. These networks are trained so that the neighborhood representations remain the same while that of the two nodes of the target edge is tuned to be similar to random pairs of vertices sampled from the graph.
strength_and_weaknesses: Strength

1. The proposed method does not require extra information from the training process, which is required in many unlearning schemes.

2. The proposed method can also be used for deleting nodes by removing all their associated edges.

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

Weakness

1. It is hard to perceive the paper's motivation of minimizing the change in the neighborhoods of deleted edges. If one expects the information of an edge to be removed entirely from the trained model, its neighborhood's intermediate representation must be changed to reflect the removal. Otherwise, its influence will most probably remain in the network.

2. The predicted probability of a deleted edge should not be random, as enforced in the paper. Instead, it should match the posterior distribution of the edge existing, given the corresponding node information. Otherwise, these deleted edges can be potentially caught by abnormal/outlier detectors and thus be recovered from deletion.

3. The proposed removal process seems to be data independently reversible, which is the last thing to hope for from a data provider’s aspect. Suppose the original untouched network can be recovered by removing the patching network described in the paper. How would you be able to provide convincing evidence to the data providers that their data’s influence has been eliminated once and for good?

4. Theorem 1 only shows that the predicted probability for the target edge of deletion will change for at least a certain amount but tells nothing about its influence being eliminated. There is also seemingly no effort that can be found in the paper to regularize the behavior of the unlearned model and a clean, trained-from-scratch model with target edges removed from its training dataset.
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 contributions.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper:  Graph unlearning refers to the task where a graph neural network (GNN) is required to remove the knowledge about a specific node or edge. This paper presents a method, GNNDelete, for performing the task of graph unlearning. The main motivation of this paper is that existing unlearning methods use divide-and-retrain, which leads to performance loss on graph datasets. Further, existing graph unlearning methods suffer from limited scope (e.g. limited model, limited task). 

This paper proposes two standards that a graph unlearning method should satisfy, Deleted Edge Consistency and Neighborhood Influence. This paper then proposes a layer-wise, model-agnostic operator, GNNDelete to implement the two standards. Extensive experiments on link prediction show the effectiveness of GNNDelete in handling edge deletion and maintaining link prediction performance. Further, the efficiency of GNNDelete is good. 
strength_and_weaknesses: Strengths: 
- This paper studies an important topic. Graph unlearning is related to privacy-preservation on graphs and machine learning. 
- This paper clearly states the motivation and its difference with related works. The main difference between graph data and image/text data is that deleting a node/edge directly influences other nodes and edges. Thus, dividing the input data leads to performance compromise. 
- The proposed standards and techniques are sound. The design of GNNDelete as an add-on module is interesting as it is more efficient than retraining the whole model. 
- Overall, the paper is largely organized clearly and easy to follow. 

Weaknesses and questions. 
- Discussion with respect to dynamic network embedding is not clear. From my perspective, graph unlearning can be seen as a special case of dynamic network embedding, where the dynamics are limited to edge deletion. Thus, a simple experiment of dynamic network embedding (e.g. treating edge deletions as graph dynamics) can be added to better justify the difference. 
- GNNDelete seems unable to deal with a sequence of delete requests. In the abstract, the authors state that graph unlearning is "a sequence of requests arrives to delete graph elements". However, from my understanding, it seems that GNNDelete can only handle one set of requests given at the same time. For example, suppose we are given a sequence of $T$ deletion requests, we should have $T$ separate del operators (Eqn. 3), one being responsible for each deletion request (as at earlier stages, one cannot know the requests that are yet to come). However, the authors state that "the weights $W_D^l$ are shared across all nodes" without mentioning that there can be multiple weights. Thus, I think the authors should clearly state whether and how GNNDelete handles a sequence of deletion requests (as stated in the abstract). 
- There are some contradictory descriptions on the two standards. In the introduction, the authors state that "the predicted probability for deleted edges of the unlearned model should be similar to those for **nonexistent** edges". However, in Section 4.1, the authors state that "the combination of the node representations that are present in the deleted edge should be **random**". These two descriptions seem contradictory, and some justifications are needed. 
- Some details and notations are not clear and can be revised. For example, in section 4.2, the Del operator (Eqn. 3), the condition $u\in S_{uv}^l$ is hard to understand as it includes two $u$.  Further, it is not described what the $\mathcal{L}$ is in Eqn. 5 and 6. Finally, I would suggest the authors clearly describe what the metrics (AUROC on $\mathcal{E}_t, \mathcal{E}_d$ and MI ratio reflect (e.g. AUROC on E_t tests ability to maintain model performance. MI-ratio and AUROC on E_d test ability of GNNDelete to delete knowledge). At the current stage, such information is not immediate without referring to the appendix. 
- It seems that GNNDelete cannot perform effectively on node classification. As shown in Table 6, GNNDelete is outperformed by GraphEditor in terms of accuracy, F1 and MI-ratio. Justifying the performance difference between node classification and link prediction can strengthen this paper. 
clarity,_quality,_novelty_and_reproducibility: Clarity: The paper is largely clear. I can easily understand the main motivation and overall design of the paper. However, some points are not clear. Please refer to "Strengths and Weaknesses". 

Quality: The paper is of good technical quality. The proposed method is largely sound, and there are extensive experiments, including ability to maintain performance, ability to forget knowledge, and efficiency. 

Novelty: The paper is of good novelty. The authors make a valid observation that the main difference between graph data and image/text data is that deleting a node/edge directly influences other nodes and edges. Thus, dividing the input data leads to performance compromise. The proposed method, which is designed based on the observations, seem simple and effective. 

Reproducibility: Code is anonymously provided. I am satisfied with it.  
summary_of_the_review: I recommend a weak accept at this stage. The studied problem is important and the proposed techniques and technically sound and make novel insights. However, the paper suffers from some unclear statements. If the authors can revise or clarify my questions, I am willing to further raise the score.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The authors propose the graph unlearning problem. When GNNs are used on networks, there might be reasons for removing some information such as individual nodes but also edges between nodes (e.g., connections in a social network). The problem is now how we can unlearn the parts of the GNN that were influenced by these deleted elements during training, without having to retrain from scratch. The problem is novel and the proposed approach to achieving the unlearning objective is effective. 

The reviewers provided helpful feedback, especially for the experimental evaluation. The authors responded to these suggestions and provided additional results. 

One of the reviewers was very negative and gave a score of 3. However, even after several attempts by the authors and the AC, there was no activity of said reviewer during the discussion phase. In addition, the AC believes that the criticism of said reviewer was vague and unspecific. Hence, this reviewer's score was not taken into account in the recommendation.
justification_for_why_not_higher_score: Some remaining minor weaknesses in clarity and experimental results. 
justification_for_why_not_lower_score: Novel problem, idea, approach.
Decision: Accept: poster