GNNDelete: A General Strategy for Unlearning in Graph Neural Networks
Authors: Jiali Cheng
George Dasoulas
Huan He
Chirag Agarwal
Marinka Zitnik
Venue: ICLR 2023 poster (2023)
Keywords: Graph Unlearning
Graph Neural Networks
Knowledge Graphs
Graph Representation Learning
Data Deletion

Abstract: Graph unlearning, which involves deleting graph elements such as nodes, node labels, and relationships from a trained graph neural network (GNN) model, is crucial for real-world applications where data elements may become irrelevant, inaccurate, or privacy-sensitive. However, existing methods for graph unlearning either deteriorate model weights shared across all nodes or fail to effectively delete edges due to their strong dependence on local graph neighborhoods. To address these limitations, we introduce GNNDelete, a novel model-agnostic layer-wise operator that optimizes two critical properties, namely, Deleted Edge Consistency and Neighborhood Influence, for graph unlearning. Deleted Edge Consistency ensures that the influence of deleted elements is removed from both model weights and neighboring representations, while Neighborhood Influence guarantees that the remaining model knowledge is preserved after deletion. GNNDelete updates representations to delete nodes and edges from the model while retaining the rest of the learned knowledge. We conduct experiments on seven real-world graphs, showing that GNNDelete outperforms existing approaches by up to 38.8% (AUC) on edge, node, and node feature deletion tasks, and 32.2% on distinguishing deleted edges from non-deleted ones. Additionally, GNNDelete is efficient, taking 12.3x less time and 9.3x less space than retraining GNN from scratch on WordNet18.

Published as a conference paper at ICLR 2023
GNNDELETE: A GENERAL STRATEGY FOR UNLEARNING IN GRAPH NEURAL NETWORKS
Jiali Cheng' George Dasoulas" ?
Huan He"
Chirag Agarwal Marinka Zitnik?
University of Massachusetts Lowell
Harvard University *Adobe
uml. edu chiragagarwa eag.ggaaawwaa111mmaml..........a com
[georgios dasoulass huan hen marinka @hms har harvard. indicates co- co-second authors
ABSTRACT
Graph unlearning, which involves deleting graph elements such nodes, node labels, and relationships from a trained graph neural network (GNN) model, is crucial for real- world applications where data elements may become irrelevant, inaccurate, or privacy-sensitee either deteriorate model weights shared across all nodes or fail to effectively delete edges due to their strong dependence on local graph neighborhoods, To address these limitations, we introduce GNNDELETE, novel model-agnostic layer-wise operator that optimizes two critical properties, namely, Deleted Edge Consistency and Neighborhood Influence, for graph unlearning. Deleted Edge Consistency ensures that the influence of deleted elements is removed from both model weights and neighboring representations, while Neighborhood Influence guarantees that the remaining model knowledge is preserved after deletion. GNNDELETR updates representations to delete nodes and edges from the model while retaining the rest of the learned knowledge. We conduct experiments showing that GNNDELETE outperforms existing approaches by up to 38.8% (AUC) edge, node, and node feature deletion tasks, and 32.2% on distinguishing deleted edges from non-deleted ones. Additionally, GNNDELETE is efficient, taking 12.3x less time and 9.3x less space than retraining GNN from scratch 8
However, existing methods for graph unlearning
seven real-world graphs,
INTRODUCTION
Graph neural networks (GNNs) are being increasingly used in variety of real-world applications (Li al. [022a] Ying et al.) 2019 Xu al.) 2022 2019: Huang et al.] [202T] Morselli Gysi et al.) [022]]
Hu et al.] 2020), with the underlying graphs often evolving over time. Machine learning approaches typically involve offline training of a model on a complete training dataset, which then used for
inference without further updates. In contrast, online training methods allow for the model to be
updated using new data points as they become available (Orabona 2019; Nagabandi et al. 2019). However, neither offline online learning approaches address the problem of data deletion (Cao Yang. 20156] Ginart et al., 2019), which involves removing the influence of data point from trained model without sacrificing model performance. When data needs be deleted from model, the model must be updated accordingly (Fu et al. (2022). In the face of evolving datasets and growing demands for privacy, GNNs must therefore not only generalize to new tasks and graphs but also be capable of effectively handling information deletion for graph elements from a trained model.
Despite the development of methods for machine unlearning, none of these approaches are applicable to GNNs due to fundamental differences arising from the dependencies between nodes connected by edges (which we show in this paper). Existing machine unlearning methods are unsuitable for data with underlying geometric and relational structure, graph elements can exert strong influence on other elements their immediate vicinity. Furthermore, since the effectiveness GNN models is based on the exchange of information across local graph neighborhoods, agent can easily infer the presence of a data point from its neighbors the impact of the data point its local neighborhood is not limited. Given the wide range of GNN applications and the lack of graph unlearning methods, there is a pressing need to develop algorithms that enable GNN models to unlearn previously learned information. This would ensure that inaccurate, outdated, or
adversarial

---

Published as a conference paper at ICLR 2023
Deleted Edge Consistancy
Overview of GNINDELETE
Deleted
edge Kare
Node
DMN Intee
Edge
Edge la delate
Uncannected
OCAL AG) @CRg =
Represeriatio before deleton
Represeriation selesin
Neighborrooo Influence
Vector operasion
Message passing
Aggregetion
U Updete
Activation
Deletion
Defore doletion:
Freezed paramelers
After deletion:
PP
Learneble celetion operator
Wo ang Wia ALoce (1 A)Lmn
Figure I: Illustration of Deleted Edge Consistency: suggests that the predicted probability of deleted edges after unlearning should be random, such that it looks like the deleted data was not used for training before. b. Illustration of Neighborhood Influence: It implies that an appropriate unlearning should not change the representations of the local neighhorhood (nodes in the subgraph, not nodes themselves to maintain the original causality. c. Overview of GNNDELETE: Given trained GNN model and edge deletion request, GNNDELETE outputs unlcarned representations efficiently by only learning a small deletion operator WD. It also ensures representation quality by minimizing a loss function that satislies the two key properties proposed above.
privacy-concemee graph elements are no longer used by the model, thereby preventing security concerns and performance degradation. In this paper, we take step towards building an efficient and general-purpose graph unlearning method for GNNs.
Designing graph unlearning methods is challenging task. Merely removing data is insufficient to comply with recent demands for increased data privacy because models trained on the original data may still contain information about removed features. A naive approach is to delete the data and retrain a model from scratch, but this can be prohibitively expensive. especially in large datasets. Recently, efforts have been made to achieve efficient unlearning based on exact unlearning (Brophy & Lowd. [222] Sekhari et al. 2021 Hase et al. 2021 Ullah et al.] 2021). The core idea is to retrain several independent models by dividing dataset into separate shards and then aggregating their predictions during inference. Such methods guarantee the removal of all information associated with the deleted data. However, in the context of GNNs, dividing graphs destroys the structure of the input graph, leading to poor performance on node-, edge- and graph-level tasks. To address this issue, Chen et al. (2022b) uses a graph partitioning method to preserve graph structural information and aggregates predictions across individually retrained shards to produce predictions. However, this approach is still less efficient as the cost increases as the number of shards grows. In addition, choosing the optimal number of shards is still unresolved and may require extra hyperparameter tuning. Several approximation- based approaches (Guo et al.) 2020 Ullah et al. 2021 He et al.) [02T]] Shibata et al. 202I) avoid retraining model from scratch on data subsets. While these approaches have shown promise, Mitchell et al. (2022) demonstrated that these unlearning methods change the underlying predictive model in way that can harm model performance.
Present Work. We introduce GNNDELETE] a general approach for graph unlearning that can delete nodes, node labels, and relationships from any trained GNN model. We formalize essential properties that GNN deletion methods should satisfy: 1) Deleted Edge Consistency: predicted probabilities for deleted edges in the unlearned model should be similar to those for nonexistent edges. This property enforces GNNDELETE to unlearn information such that deleted edges appear as unconnected nodes. 2) Neighborhood Influence: we establish a connection between graph unlearning and Granger causality (Granger) 1969) to ensure that predictions in the local vicinity of the deletion maintain their original performance and are not affected by the deletion. However, existing graph unlearning methods do not consider this essential property, meaning they do not consider the influence of local connectivity, which can lead to sub-optimal deletion. To achieve both efficiency and scalability, GNNDELETE uses layer-wise deletion operator to revise trained GNN model. When receiving deletion requests, GNNDELETE freezes the model weights and Icarns additional small weight matrices that shared across nodes in the graph. Unlike methods that attempt to
"oode and datasets for GNNDELETE can be found http:///gttao.oommmmmm-naa/aaane
2

---

Published as a conference paper at ICLR 2023
retrain several small models from scratch directly update model weights, which can be inefficient and suboptimal, GNNDELETE learns small matrices for inference without changing GNN model weights. To optimize GNNDELETE, specify novel objective function that satisfies Deleted Edge Consistency and Neighborhood Influence and achieves strong deletion performance.
Our Contributions. We present our contributions follows: ! We formalize the problem of graph unlearning and define two key properties, Deleted Edge Consistency and Neighborhood Influence, for effective unlearning on graph data. 2 We propose GNNDELETE, GNN data deletion approach that achieves more efficient unlearning than existing methods without sacrificing predictive performance. GNNDELETE madel-agmostic and can be applied to various GNN architectures and training methodologies. 3 The difference between node representations returned the baseline GNN model and those revised by GNNDELETE theoretically bounded, ensuring the strong performance of GNNDELETR. 4 We demonstrate the flexibility of GNNDELETE through empirical evaluations on both link and node deletion tasks. Results show that GNNDELETE achieves effective unlearning with 12.3x less time and 9.3x less computation than retraining from scratch.
2 RELATED WORK
Machine Unlearning. We organize machine unlearning research into four categories: 1) Retraining: Retraining models from scratch unlearn is a simple yet often inefficient approach, despite recent
efforts to develop efficient data partitioning and retraining methods (Bourtoule et al. [2021 Wu et al. 2020: Liu et al., 2022b; Cao & Yang, 2015a Golatkar et al. 2020; Izzo et al.j (201). However, partitioning graphs can be challenging because the graph structure and learned node representations of the partitioned graphs may be significantly different from the original graph. Furthermore, such methods may not scale well to large datasets. 2) Output modification: Methods such as UNSIR (Tarun et al., 202I) directly modify model outputs to reduce computational overhead. UNSIR first learns error matrix that destroys the output and then trains the destroyed model for two epochs with clean data to repair the outputs. However, for graphs, the error destroys outputs for all edges, and the training after that falls back to retraining the whole model. 3) Logit manipulation: Other methods achieve unlearning by manipulating the model logits (Izzo et al., 2021] Baumhauer et al. 2022), but these methods only apply to linear or logit-based models. 4) Weight modification: Unlearning via weight modification is achieved by running an optimization algorithm. For example, Ullah et al. (2021) proposed an unlearning method based on noisy stochastic gradient descent, while Guo et al. (2020) achieves certified removal based on Newton updates. Other optimization methods that modify weights include Thuud et | (2022a) and Neel et al. (02T). Recent unlearning methods perturb gradients (Ma et al., (022) or model weights (Chen et al.] (021a). However, weight modification approaches lack unique features for graphs and incur computation overheads, such as calculating the
inverse Hessian. In Appendix A we provide details on unlearning methods for other models.
Graph Unlearning. We present an overview of the current state of the art in graph unlearning research. GraphEraser (Chen et al. (022b) attempts to address the graph unlearning problem by utilizing graph partitioning and efficient retraining. They use a clustering algorithm to divide a graph into shards based both node features and structural information. A learnable aggregator is optimized to combine the predictions from sharded models. However, the limitations of GraphEraser (Chen) ctt al., (2022b) are that it supports only node deletion. GraphEditor (Cong & Mahdavi 2023) provides a closed-form solution for linear GNNs to guarantee information deletion, including node deletion, edge deletion, and node feature update. Additional fine-tuning can improve predictive performance. However, GraphEditor is only applicable to linear structures, which is the case for most unlearning algorithms, not only those designed for graph-structured data. As a result, it is not possible to use existing non-linear GNNs or knowledge graphs with GraphEditor, and it struggles to process larger deletion requests. Recently, [Chien et al. (2022) proposed the first framework for certified graph unlearning of GNNs. Their approach provides theoretical guarantees for approximate graph unlearning. However, the framework is currently limited to certain GNN architectures and requires further development to become more practical solution for the broader range of GNNs. For more details on related work, we refer the reader to Appendix AA]
Connection with Adversarial Attacks and Defense for GNNs. To determine whether a data point has been used to train a model, the success of a membership inference (MI) attack can be a suitable measure for the quality of unlearning (Yeom al. 2019 (Sablayrolles et al. 2019). Defending
3

---

Published as a conference paper at ICLR 2023
against MI attacks is also challenge that care about when building unlearning models. Thudi et al. (2022c) proposed using a novel privacy amplification scheme based on a new tighter bound and subsampling strategy. Olltunji et al. (021) showed that all GNN models are vulnerable to MI attacks and proposed two defense mechanisms based on output perturbation and query neighborhood perturbation. [Liu al., (2022a) treated the data be unlearned backdoored data. While defense strategies against MI attacks can provide valuable insights for evaluating unlearning, it is important to note that they serve a different purpose than unlearning itself.
PRELIMINARIES
= x) be attributed graph with n | nodes, set of edges E, and n -iddimmnnio node features X = {.o..... Fn,I where æ; E RR We use to denote the adjacency matrix of G and degg : V + N to denote the degree distribution of graph G. Further, use S (V& aus wu
X ue) to represent a k-hop enclosing subgraph around nodes and v.
Graph Neural Networks (GNNs). GNN layer 9 can be expressed as a series of transformation func- tions: g(G) (UPD (G) that takes G as input and produces d-dimensional node repre- sentations h, for u E V (Figure[) D. Within layer I, MSG specifies neural messages that are exchanged between nodes and following edges in Aur by calculating p. MsG(h' .h'_! Auo). The AGG defines how every node u combines neural messages from its neighbors N₂ and computes the aggregated message P AGG((P
NN.)). Finally, UPD defines how the aggregated messages Pa and hidden node states from the previous layer are combined to produce h2 i.e., final outputs of 1-th layer hy UPD( Pt. h1-1). The output of the last GNN layer is the final node representation, Zu = h4 where L is the number of GNN layers in the model.
Unlearning for GNNs, Let & S denote the set of edges to be deleted and & EE be the remaining edges after the deletion of & from G. We use G, = (Vr, E,, to represent the resulting graph after deleting edge Eg. Here, V, fu E V| degg (u) 0} denotes the set of nodes that are still connected to nodes in G,, and X, denotes the corresponding node attributes. Although the above notations are specific to edge deletion, GNNDELETE can also be applied to node deletion by removing all edges incident to the node that needs to be deleted from the model.
To unlearn an edge Cav, the model must erase all the information and influence associated with eue as if it was never seen during the training while minimizing the change in downstream performance. To this end, we need to modify both the predicted probability of eve and remove its information from its local neighborhood. Therefore, post- pest-procsssng and logit manipulation are ineffective for deleting edges from a GNN model because these strategies do not affect the rest of the graph. We denote a classification layer f that takes node representations h and h! as input and outputs the prediction probability for edge Cuv. Given L layers and f, GNN model : G + R can be expressed as mGG) = (ʃ o g² ... .') (G), where g¹ is the 5th GNN layer. The unlearned model mn' G - RIE.1 can be written as m/ mn. (ʃ o g²z ............ (G.), which are L stacked unlearned GNN layers g" operating on the graph Gy..
4 GNNDELETE: A GENERAL STRATEGY FOR GRAPH UNLEARNING
To ensure effective edge deletion from graphs, the GNN model should ignore edges in Eg and not be able to recognize whether a deleted edge Cuv E & is part of the graph. Furthermore, the model should ignore any influence that a deleted edge has in its neighborhood. To this end, we introduce two properties for effective graph unlearning and a layer-wise deletion operator that implements the properties and can be used with any GNN to process deletions in E.--
Problem Formulation (Graph Unlearning). Given a graph G (V,E, X) and a fully trained GNN model m(G),, we aim to unlearn every edge ewv Ea from mGG), where Ea is set of edges to be deleted. The goal is to obtain an unlearned model m' (G) that is close to the model output that would have been obtained had the edges in Ea been omitted from training. To achieve this, we require that the following properties hold:
Deleted Edge Consistency: euv Ed, then m' (G) should output a prediction that is independent of the existence of the edge Cuo, i.e. the deletion of ewo should not have any influence on the predicted output.
4

---

Published as a conference paper at ICLR 2023
Neighborhood Influence: If euv & Ed, then m' (G) should output a prediction that is close mmG), i.e., the deletion of edges in E should not have any significant impact on predictions in the rest of the graph.
4.1 REQUIRED PROPERTIES FOR SUCCESSFUL DELETION ON GRAPIIS
Deleting information from a graph is not a trivial task because the representations of nodes and edges dependent on the combined neighborhood representations. The following two properties show intuitive assumptions over the deletion operator for effective unlearning in GNNs:
Deleted Edge Consistency. The predicted probability from the unlearned model m' for an edge euv should be such that it is hard to determine whether it is a true edge or not. The unlearned GNN layer g" should not be aware of the edge existence. Formally, we define the following property:
Definition (Deleted Edge Consistency). Let euv denote an edge to be deleted, g be the 1-th layer in a GNN with output node representation vectors by and the unlearned GNN layer g with h The unlearned layer g" satisfies the Deleted Edge Consistency property if it minimizes the difference between mode-pair representations @(h'u h',), and @hpp hgg) tfo two randomly chosen nodes p.g 9 E V.:
E
[6 k.)) - p(h h₂ =6
(1)
p.gEnY
where @ is readout function (e-g.. dot product, concatenation) that combines node representations h" and h" ER denotes random choice from V, and 5 is an infinitesimal constant.
2) Neighborhood Influence. While the notion of causality has been used in explainable machine learning, to the best of our knowledge, we propose the first effort of modifying a knowledge graph using a causal perspective. Formally, removing edge euv from the graph requires unlearning the influence of Cuv from the subgraphs of both nodes and v. In this work, we propose the Neighborhood Influence property which leverages the notion of Granger causality (Granger 1969 Bressler & Seth, 2011) and declares causal relationship eb ((h,,,lu |u Suv)) variables 4 u E Sue}) and Cuv we are better able to predict edge Cuv using all available node representations S.e than if the information apart from 4 (h.,/u E S) had been used. Here, (-)- is an operator that combines the node representations in subgraph Suv- In the context of graph unlearning. if the absence of node representations decreases the prediction confidence of euv, then there is causal relationship between the node representation and the eav prediction.
Cuv between
Here, we characterize the notion of deletion by extending Granger causality to local subgraph causality, i.c., an edge dependent on the subgraphs associated with both nodes and v. In particular, removing Cur should not affect the predictions of Suv yielding the following property:
Definition 2 (Neighborhood Influence). Let Ewv E E denote an edge in G to be deleted. g' be the 1-th layer in GNN with ourpur node representation vectors ht and the unlearned GNN layer g" with h The unlearned layer g" satisfies the Neighborhood Influence property if it minimizes the difference of all node-subset representations db( ((hh,,lu E &See) comprising Cav with their corresponding node-subset representations (tth
Wule ww E Swv/eew)) }) where ewv is deleted, i.e.,
(h(hi w E Swv - (bh"") w E Sunjean })] =1=
(2)
where şi is an operator that combines the elements of Suv (e.g., concatenation, summation), Sun//ue represent the subgraph excluding the information from eij, and 8 is an infinitesimal constant.
4.2 LAYER-WIT WISE DELETION OPERATOR
To achieve effective deletion of edge Cue from a graph G, is important eliminate signals with minor contributions to predicting the edges and develop mechanisms that can tune or perturb any source of node or edge information that aids in the prediction of cap- Perturbing weights or other hyperparameters of the GNN model can affect decisions for multiple nodes and edges in G due to information propagation through the local neighborhood of each node. In order to allow for the deletion of specific nodes and edges, introduce model-agnostic deletion operator DEL that can be applied to any GNN layer.
Deletion Operator. Following the notations of Section for the 1-th GNN layer g' (G) with output dimension d' we define extended GNN layer with unlearning capability (DEI.' g' (G) with
5

---

Published as a conference paper at ICLR 2023
the same output dimension d' Given an edge Cuv that is to be removed, DEL is applied to the node representations and is defined as:
DEL's = { if w E St..
(3)
(1 otherwise
where L is the identity function, and Ø Raxd' + Ruxd can be any diffcrentiable function that takes as input the output node representations of g. In this work, e considered as an ML.P with weight parameters W Similarly to other GNN operators, the weights W of our DEL operator are shared across all nodes to achieve efficiency and scalability.
Local Update. Defining an operator that acts only in the local neighborhood S.e enables targeted unlearning, keeping the previously learned knowledge intact as much as possible. If node u within the local neighborhood of Cuvs DEL is activated. For other nodes, DEL remains deactivated and does not affect the hidden states the nodes. This ensures that the model will not forget the knowledge has gained before during training and the predictive performance E ESSu will not drop.
By applying the deletion operator DEL to every GNN layer, we expect the final representations to reflect the unlearned information in the downstream task. Next, we show theoretical observation over the unlearned node representations that indicates a stable behavior of the deletion operator:
Theorem 1. (Bounding edge prediction using initial model m and unlearned model m') Let Guo be an edge to be removed, W be the weight matrix of the deletion operator DEL", and normalized Lipschitz activation function (-)). Then, the norm difference between the dot product of the final node representations from the initial model Zu; 2v and from the unlearned one z zly is bounded by:
1
(Zu: 2n) (2 2/)
2 2011
where W denotes the weight matrix of the deletion operator for the I-th GNN layer.
The proof is in Appendix B By Theorem (z' ztt), and consequently the prediction probability for edge eup from the unlearned model cannot be dissimilar from the baseline. Nevertheless, DEL ' is a layer-wise operator, which provides stable node embeddings compared to the initial ones.
4.3 MODEL UNLEARNING
Moving from a layer-wise operator to the whole GNN model, our method GNNDELETE applies DEL every GNN layer, leading to a total number of trainable parameters Σ, (d')². As the number of trainable parameters in GNNDELETE is independent of the size of the graph, it is compact and scalable to larger graphs and the number of deletion requests. Considering the properties defined in Section 4.1 we design two loss functions and compute them in layer-wise manner. Specifically, for the 1-th GNN layer we first compute the Deleted Edge Consistency loss:
D = C((hh;; le E Ea), (hi's h h.llu, En V)),
(5)
and the Neighborhood Influence loss:
Chu L(w (h"lww E Suv/euv llw (h'y ww S.
(6)
where [h h]] denotes the concatenation of two vectors, and denotes the concatenation of multiple vectors. Note that according to Equations [ndd] we choose the functions d, v to be the concatenation operators. During the backward pass, the deletion operator the l-th GNN layer is only optimized based on the weighted total loss at the I-th layer, i.c.
5 = arg min C' = arg min XC + (1 - -1) W
W
where À [0, 1] is regularization coefficient that balances the trade-off between the two properties, L refers to the distance function. We use Mean Squared Error (MSE) throughout the experiments.
Broad Applicability of GNNDELETE. GNNDELETE treats node representations in model- agnostic manner, allowing us to consider graph unlearning in models beyond GNNs. Graph trans- formers (Ying al. 2021 Rampášek et al. 2022) have been proposed recently extension

---

Published as a conference paper at ICLR 2023
of the Transformer architecture Vaswani al., 2017) for learning representations graphs. The DEL operator can also be applied after the computation of the node representations in such models. For example, the MPNN: X E', A) layer in GraphGPS (Rampákek et al. 2022 Equation 2) can be replaced with the unlearned version (DEL MPNN".. Similarly, in the Graphormer layer, DEL operator can be applied after the multi-head attention MHA layer (Rampášek et al. 2022 Equation 8).
5 EXPERIMENTS
We proceed with the empirical evaluation of GNNDELETE. We examine the following questions: Q1) How does GNNDELETE perform compared to existing state-of-the-an unlearning methods? Q2) Can GNNDELETE support various unlearning tasks including node, node label, and edge deletion? Q3) How does the interplay between Deleted Edge Consistency and Neighborhood Influence property affect deletion performance? Appendix C.I provides a detailed definition of performance metrics.
5.1 EXPERIMENTAL SETUP
Datasets. We evaluate GNNDELETE on several widely-used graphs various scales. We use 5 homogeneous graphs: Cora (Bojchevski & Günnemann 2018). PubMed (Bojchevski & Günnemann 2018), DBLP (Bojchevski & Günnemann 2018), CS (Bojchevski & Günnemann 2018).
Hu et al. 2020). and 2 heterogencous graphs: OGB-BioKG (Hu et al. 2020)) and WordNet1 Dettmers et al. 2018). Table includes details on graph datasets.
GNNs and Baselines. We test with four GNN architectures and two graph types to show the flexibility of our GNNDELETE operator. In particular, we test on GCN (Kipf & Welling 2017). GAT (Veličkovid
2018), and GIN (Xu et al. (2019) for homogeneous graphs, and R-GCN (Schlichtkrull et al. 2018 and R-GAT (Chen al. [b02Tb) for heterogeneous graphs. We consider four baseline methods: 1) GRAPHEDITOR (Cong & Mahdavi 2023), method that finetunes on a closed-fone solution of linear GNN models; ii) CERTUNLEARN (Chien et al. 2022). a certified unlearning approach based on linear GNNs; iii) GrAPHHRASER (Chen et al. 2022b), a re-training-based machine unlearning method for graphs; iv) GRADASCENT, which performs gradient ascent on & with cross-entropy loss, and v) DESCENT-TO-DEEETE (Neel et al. 2021). a general machine unlearning method.
ct al.
Tasks and Downstream Tasks. Requests for graph unlearning can be broadly classified into three categories: 1) edge deletion, which involves removing a set of edges En from the training graph, 2) node deletion, which involves removing a set nodes Na from the training graph, and 3) node feature unlearning, which involves removing the node feature Xa from the nodes Na. Deletion of information can have a significant impact on several downstream tasks. Therefore, we evaluate the effects of graph unlearning on three different downstream tasks, namely, link prediction, node classification, and graph classification.
Unlearning
Setup. We evaluate the effectiveness of GNNDELETE edge deletion tasks and also demonstrate its ability to handle node deletion and node feature unlearning tasks. We perform experiments on two settings: i) an easier setting where we delete information far away from test set & in the graph, and ii) harder setting where we delete information proximal to test set & in the graph. To perform edge deletion tasks, we delete a varying proportion of edges in Eg between [0.5% 5.00%) of the total edges. with step size of 0.5%. For larger datasets such as OGB (Hu et al. 2020). we limit the maximum deletion ratio to 2.5%. We report the average and standard error of the unlearning performance across five independent runs. We use AUROC to evaluate the performance of GNNDELETE for link prediction tasks, as well as Membership Inference (MI) (Thudi et al., 2022a) for node deletion. Performance metrics are described in Appendix C.I Additionally, we consider two sampling strategies for Ed (Appendix C.2
5.2
Q1: RESULTS COMPARISON TO EXISTING UNLEARNING STRATEGIES
We compare GNNDELETE to the baseline unlearning techniques and present the results in Tables I Across four GNN architectures, we find that GNNDELETE achieves the best performance the test edge set ε,, outperforming GRAPHEDITOR, CERTUNLEARN and GRAPHERASER by 13.9%, 19.7% and 38.8%. Further, we observe that GNNDELETE achieves the highest AUROC on Ea.
7

---

Published as a conference paper at ICLR 2023
Table 1: Unlearning task: 2.5% edge deletion. Evaluation: link prediction. Dataset: DBLP and Word- Net18. Reported is AUROC (t) performance with the best marked in bold and the second best underlined. GNNDELETE retains the predictive power of GNNs on & while improving performance on Eg. GRAPHEDITOR and CERTUNLEARN support unlcarning for linear GNNs on homogeneous graphs (i.c., N/A). Table shows results on other downstream tasks and Tables 15
show results other datasets and ratios of deleted edges.
GCN
GAT
R-GCN
R-GAT
Model
&
E
&
E,
&
E2
E+
Ed
RETRAIN
0.964 00000
0.506
+0.013
0,956
+00000
0.525
+:0012
0.800
+.0005
0,580
+00006
0.891
#:0.005
0.783
+00009
GRADASCENT
0.555 =0.066
0.594
+0.063
0.501
+0.020
0.592
10.077
0,490
+0.001
0.502
+0.002
0.490
1:0000
0.492 20.003
D2D
0.500 =0,000 0,500
10,000
0,500
1:0000
0,500
1:0000
0.500
+:0000
0,500
+00000
0,500
1:0.000
0.500
10,000
GRAPHÉRASER
0.527 20.002
0.500
1:0000
0,538
1.0013
0.500
1.0.000
0.512 1:0.003
0,500
110.000
0.545
::0.015
0.500
1:0000
GRAPHEDITOR
0.776 =0.025 0.432
+0.009
N/A
N/A
NIA
N/A
CERTUNLEARN 0.718 =0.032
0.475
+00011
N/A
N/A
NIA
N/A
GNNDELFTE 0.934 0.002 0.748 1.0000
0.914 100000 0.774
10.015
0.751
1000006
0.845
1.0007
0.893 1000002
0.786
0.004
Table 2: Unlearning task: 2.5% edge delction. Evaluation: MI attack. Dataset: DBLP and WordNet18. Reported is the MI attack ratio (1), with the best performance marked in bold and the second best underlined. GRAPHEDITOR and CERTUNLEARN support unlearning for linear GNNs on homogeneous graphs (i.c., N/A).
DBLP GAT
WordNet18
Model
GCN
GIN
R-GCN
R-GAT
RETRAIN
1,255 1.0207
1.223
10.151
1.200
10.177
1,250
10.091
1.215
10.125
GRADASCENT
1.180 +00061
1.112 =0.109
1.123
10.103
1.169
#0.066
1.112
10.106
D2D
1.264 +:0000
1.264
=0.000
1.264
10,000
1.268
00.000
1.268
40.000
GRAPHERASER
1.101
1.00032
1.182
10.104
1.071
10.113
10.048 1.199
T.173 10.104
GRAPHEDITOR
1.189
+-0.193
1.189
=0.193
1.189
10.193
N/A
N/A
CERTUNLEEARN
1.103
1:0.087
1.103
-0.087
1.103
10.087
N/A
N/A
GNNDELETE
1.266 1:0.106
1.338
0.122
1.254
10.159
1.264
10.143
1.280
:0.144
outperforming GRAPHEDITOR, CERTUNLEARN and GRAPHERASER by 32.2%. 27.9% and 25.4%. GNNDELETE even outperforms RETRAIN-FROM- SERRTCS by 21.7% under this setting, proving its capability of effectively unlearming the deleted edges. Interestingly, none of the existing baseline methods have comparable performance to GNNDELETE on these performance metrics, including GRAPHERASER,, which ignores the global connectivity pattern and overfit to specific shards, as well as GRAPHEDITOR and CERTUNLEARN, whose choice of linear architecture strongly limits the power of the GNN unlearning. Our results demonstrate that baselines like DESCENT- COENN---T--EEETEE DELETE and GRADASCENT lose almost their predictive prowess in making meaningful predictions and distinguishing deleted edges because the weight updates are independent of the unlearning task and affect all the nodes, including nodes associated with & In addition, CERTUNLEARN and GRAPHEDITOR are not applicable due to their linear architectures. Please refer to the Appendix for results on Cora (Tables 14). PubMed (Tables 15 16). DBLP (Tables 18)) OGB-Collab using a deletion ratio of 0.5%, 2.5% and 5%.
(Tables 19 20 and WordNet18 (Tables 21 22
Results in Table 2 show the Membership Inference (MI) performance of baselines and GNNDELETE for the DBLP and Wordnet18 using deletion ratio 2.5%. It shows that GNNDELETE outperforms baselines for most GNN models, highlighting its effectiveness in hiding deleted data. Across five GNN architectures, we find that GNNDELETE improves on the MI ratio score of all baselines: GRAPHEDITOR (+0.083), CERTUNLEARN (+0.169) GRAPHERASER (+0,154), RETRAIN-FROM- SCRATCH (+0.047), GRADASCENT (+0.134), and DESCENT-TO-DELETTE (+0.086).
5.3 Q2: RESULTS- - OTHER UNLEARNING TASKS AND GNNDELETE'S EFFCIENCY
Node Deletion. We examine the flexibility of GNNDELETE to handle node deletion. We delete 100 nodes and their associated edges from the training data and evaluate the performance of the unlearning method on node classification and Membership Inference attacks. Results in Table 8 show that GNNDELETE outperforms baselines on node classification while deleting nodes. GNNDELETE outperforms GRAPHEDITOR and CERTUNLEARN by 4.7% and 4.0% in accuracy, respectively. It is also 0.139 and 0.267 better than GRAPHEDITOR and CERT UNLEANN in terms of membership inference attacks. Tables 9 and 10 show results for node feature unlearning and sequential unlearning.
8

---

Published as a conference paper at ICLR 2023
Time and Space Efficiency. We demonstrate that GNNDELETE is time-efficient compared to most unlearning baselines. For all methods, we use a 2-layer GCN/R- architecture with a trainable entity and relation embeddings with 128, 64, and 32 hidden dimensions trained three datasets (PubMed, CS, and OGB-Collab). We present the results of wall-clock time vs. graph size in Figure 2 and observe that GNNDELFTT consistently takes less time than existing graph CROAAIN-FRO-SSHHE on WordNet. For smaller graphs like DBLP, GNNDELETE takes 185 seconds less (18.5% faster) than the pre-training stage of GRAPHEDITOR, Despite taking lower time, the predictive performances of DESCENT-TO-DELETE and GRADASCENT are poor compared GNNDELETE because they are not tailored to incorporate the graph structure for unlearning. Regarding the space efficiency, we measure the number of training parameters and show that GNNDELETE has the smallest model size. In addition, the number of training parameters does not scale with respect to the graph size, proving the efficiency and scalability of GNNDELETE. For instance, GNNDELETE takes 9.3 x less computation than GRAPHERASER. We further demonstrate that GNNDELETE can be more efficient by only inserting a deletion operator after the last layer without losing much performance. Additional results and details are in Tables
unlearning methods. In particular, GNNDELETE is 12.3x x faster than
5.4
Q3: RESULTS DELETED EDGE CONSISTENCY Vs. NEIGHBORHOOD INFLUENCE
We conducted ablations on two key properties of GNNDELETE, namely Deleted Edge Consistency and Neighborhood Influence, by varying the regularization parameter À in Equation 7 The results presented in Table demonstrate that both properties are necessary for achieving high AUROC on both and Ea. We observed that as À decreases, GNNDELETE focuses more on Neighborhood Influence, which explains why the model's 's performance on & is close to the original, while it cannot distinguish En from the remaining edges. Conversely, for higher values of X, GNNDELETE focuses more on optimizing the Deleted Edge Consistency property and can better distinguish between & and E,. In summary, we observed 5.56% improvement in the average AUROC for X = 0.5.
Cerike Dramh Uikardng
Drsceel Dolite Gradiess-eoort:
Table 3: Ablation study on the interplay of Deleted Edge Consistency and Neighborhood Influence prop- erty. Unlearning task: 2.5% edge deletion. Eval- uation: link prediction. Dataset: DBLP. The gap is calculated as: (AUROC(E:) AUROC(Ea)I- Best overall deletion performance is achieved for À = 0.5, indicating that both properties necessary suc- cessfully delete information from the GNN model while minimizing negative effects on overall model performance.
10
Time [min]
10a-
10a
0.0
0.5
1.0
3.5
2.0
Graph size
X
AUROC on &
AUROC on Ed
Avg. AUROC (Gap)
Figure 2: Comparison of efficiency on three datasets (PubMed, CS, and OGB-Collab). We plot the retrain- ing approach in solid lines, general unlearning meth- ods in dotted lines, and graph unlearning methods in dash-dotted lines. Results show that GNNDELETE scales better than existing graph unlearning methods. its execution time is consistently lower than other methods, especially for larger graphs.
0.0
0.964 1000
0.492 10012
0.728 (0.473)
0.2
0.961
100m
0.593
0.777 (0.368)
0.4
0.950
2000
0.691
#0000
0.821 (0.259)
0.5
0.934
#000
0.748
0,841 (0.185)
0.6
0.927
10000
0.739 10.00
0.834 (0.188)
0.8
0.893
1000
10.0
0.823 (0.134)
1.0
0.858
10000
0.757
10.004
0.808 (0.101)
CONCLUSION
We introduce GNNDELETE, a novel deletion operator that is both flexible and casy-to-use, and can be applied to any type of graph neural network (GNN) model. We also introduce two properties, denoted as Deleted Edge Consistency and Neighborhood Influence, which can contribute to more effective graph unlearning. By combining the deletion operator with these two properties, we define a novel loss function for graph unlearning. We evaluate GNNDELETE across wide range of deletion tasks including edge deletion, node deletion, and node feature unlearning, and demonstrate that outperforms existing graph unlearning models. Our experiments show that GNNDELETE performs consistently well across a variety of tasks and easy to use. Results demonstrate the potential of GNNDELETE general strategy for graph unlearning.

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGEMENTS
We gratefully acknowledge the support of the Under Secretary of Defense for Research and Engi- neering under Air Force Contract No. FA8702-15-D-0001 and awards from Harvard Data Science Initiative, Amazon Research Award, Bayer Early Excellence in Science Award, AstraZeneca Research, and Roche Alliance with Distinguished Scientists Award. G.D. is supported by the Harvard Data Science Initiative Postdoctoral Fellowship. Any opinions, findings, conclusions or recommendations expressed this material are those the authors and do not necessarily reflect the views of the funders. The authors declare that there are conflict of interests.
REFERENCES
Nasser Aldaghri, Hessam Mahdavifar, and Ahmad Beirami. Coded machine unlearning. IEKE Access, 2021.
Thomas Baumhauer, Pascal Schöttle, and Matthias Zeppelzauer. Machine unlearning: Linear filtration for logit-based classifiers. Machine Learning, 2022.
Aleksandar Bojchevski and Stephan Günnemann. Deep gaussian embedding of graphs: Unsupervised inductive learning via ranking. International Conference on Learning Representations, 2018.
Lucas Bourtoule, Varun Chandrasekaran, Christopher A Choquette- Choo, Hengrui Jia, Adelin Travers, Baiwu Zhang, David Lie, and Nicolas Papernot. Machine unlearning. In IEEE Symposium on Security and Privacy (SP), 2021.
Steven L Bressler and Anil K Seth. Wiener-granger causality: well established methodology. Neuroimage, 2011.
Jonathan Brophy and Daniel Lowd. Machine unlearning for random forests. In Proceedings of the International Conference on Machine Learning, 2021.
Yinzhi Cao and Junfeng Yang. Towards making systems forget with machine unlearning. In IEEE Symposium on Security and Privucy, 2015a.
Yinzhi Cao and Junfeng Yang. Towards making systems forget with machine unlearning. In Proceedings of the IEEE Symposium on Security and Privacy, 2015b.
Chong Chen, Fei Sun, Min Zhang, and Bolin Ding. Recommendation unlearning. In Proceedings of the ACM Web Conference 2022, 2022a.
Kongyang Chen, Yiwen Wang, and Yao Huang. Lightweight machine unlearning in neural network. arXiv, 2021a.
Meiqi Chen, Yuan Zhang, Xiaoyu Kou, Yuntao Li, and Yan Zhang. r-gat: Relational graph attention network for multi-relational graphs. arXiv, 2021b.
Min Chen, Zhikun Zhang, Tianhao Wang, Michael Backes, Mathias Humbert, and Yang Zhang. When machine unlearning jeopardizes privacy. In Proceedings of the ACM SIGSAC Conference on Computer and Communications Security, 2021c.
Min Chen, Zhikun Zhang, Tianhao Wang, Michael Backes, Mathias Humbert, and Yang Zhang. Graph unlearning. In Proceedings of the ACM SIGSAC Conference Computer and Communications Security, 2022b.
Eli Chien, Chao Pan, and Olgica Milenkovic. Certified graph unlearning. In NeurIPS 2022 Workshop: New Frontiers in Graph Learning. 2022.
Vikram S Chundawat, Ayush K Tarun, Murari Mandal, and Mohan Kankanhalli. Zero-shot machine unlearning. arXiv. 2022.
Weilin Cong and Mehrdad Mahdavi. Grapheditor: An efficient graph representation learning and unlearning approach. 2023.
10

---

Published as a conference paper at ICLR 2023
Tim Dettmers, Pasquale Minervini, Pontus Stenetorp, and Sebastian Riedel. Convolutional 2d knowledge graph embeddings. In Proceedings of the AAAI Conference on Artificial Intelligence, 2018.
Shaopeng Fu, Fengxiang He, and Dacheng Tao. Knowledge removal in sampling-based bayesian inference. In International Conference on Learning Representations, 2022.
Antonio Ginart, Melody Guan, Gregory Valiant, and James Y Zou. Making ai forget you: Data deletion in machine learning. Advances in Neural Information Processing Systems, 2019.
Shashwat Goel, Ameya Prabhu, Amartya Sanyal, Ser-Nam Lim, Philip Torr, and Ponnurangam Kumaraguru. Towards adversarial evaluations for inexact machine unlearning. arXiv, 2022.
Aditya Golatkar, Alessandro Achille, and Stefano Soatto. Eternal sunshine of the spotless net: Selective forgetting in deep networks. 2020.
Aditya Golatkar, Alessandro Achille, Avinash Ravichandran, Marzia Polito, and Stefano Soatto. Mixed-privacy forgetting in deep networks. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, 2021.
Clive WJ Granger. Investigating causal relations by econometric models and cross-spectral methods. Econometrica: journal of the Econometric Society, 1969.
Chuan Guo, Tom Goldstein, Awni Hannun, and Laurens Van Der Maaten. Certified data removal from machine learning models. Proceedings of the International Conference on Machine Learning, 2020.
Varun Gupta, Christopher Jung, Seth Neel, Aaron Roth, Saeed Sharifi-Malvajerdi, and Chris Waites. Adaptive machine unlearning. In Advances in Neural Information Processing Systems, 2021.
Peter Hase, Mona Diab, Asli Celikyilmaz, Xian Li, Zornitsa Kozareva, Veselin Stoyanov, Mohit Bansal, and Srinivasan Iyer. Do language models have beliefs? methods for detecting, updating, and visualizing model beliefs. arXiv,, 2021.
Yingzhe He, Guozhu Meng, Kai Chen, Jinwen He, and Xingbo Hu. Deepobliviate: A powerful charm for erasing data residual memory in deep neural networks. arXiv, 2021.
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning graphs. 2020.
Kexin Huang, Tianfan Fu, Wenhao Gao, Yue Zhao, Yusuf Roohani, Jure Leskovec, Connor W. Coley, Cao Xiao, Jimeng Sun, and Marinka Zitnik. Therapeutics data commons: Machine learning datasets and tasks for drug discovery and development. Advances in Neural Information Processing Systems Datasets and Benchmarks, 2021.
Zachary Izzo, Mary Anne Smart, Kamalika Chaudhuri, and James Zou. Approximate data deletion from machine learning models. In Proceedings of The International Conference on Artificial Intelligence and Statistics, 2021.
Rahif Kassab and Osvaldo Simeone. Federated generalized bayesian learning via distributed stein variational gradient descent. IEEE Transactions on Signal Processing, 2022.
Ronald Kemker, Marc McClure, Angelina Abitino, Tyler Hayes, and Christopher Kanan. Measuring catastrophic forgetting in neural networks. 2018.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations, 2017.
Jakub Konečný, Brendan McMahan, Felix Yu, Peter Richtarik, Ananda Theertha Suresh, and Dave Bacon. Federated learning: Strategies for improving communication efficiency. In NeurlPS Workshop on Private Multi-Party Machine Learning, 2016.
Michelle M Li, Kexin Huang, and Marinka Zitnik. Graph representation learning in biomedicine and healthcare. Nature Biomedical Engineering, 2022a.

---

Published as a conference paper at ICLR 2023
Yuyuan Li, Xiaolin Zheng, Chaochao Chen, and Junlin Liu. Making recommender systems forget: Learning and unlearning for erasable recommendation, 2022b.
Gaoyang Liu, Xiaoqiang Ma, Yang Yang, Chen Wang, and Jiangchuan Liu. Federaser: Enabling efficient client-level data removal from federated learning models. In Proceedings of the IEEE/ACM International Symposium Quality of Service, 2021.
Yang Liu, Mingyuan Fan, Cen Chen, Ximeng Liu, Zhuo Ma, Li Wang, and Jianfeng Ma. Backdoor defense with machine unlearning. In IEEE Conference on Computer Communications, 2022a.
Yi Liu, Lei Xu, Xingliang Yuan, Cong Wang, and Bo Li. The right to be forgotten in federated learning: An efficient realization with rapid retraining. In IEEE Conference on Computer Communications, 2022b.
Zhuo Ma, Yang Liu, Ximeng Liu, Jian Liu, Jianfeng Ma, and Kui Ren. Learn to forget: Machine unlearning via neuron masking. IEEE Transactions on Dependable and Secure Computing, 2022.
Ananth Mahadevan and Michael Mathioudakis. Certifiable machine unlearning for linear models. arXiv, 2021.
Eric Mitchell, Charles Lin, Antoine Bosselut, Chelsea Finn, and Christopher D Manning. Fast model editing at scale. In International Conference on Learning Representations, 2022.
Deisy Morselli Gysi, ftalo Do Valle, Marinka Zitnik, Asher Ameli, Xiao Gan, Onur Varol, Susan Dina Ghiassian, JJ Patten, Robert A Davey, Joseph Loscalzo, et al. Network medicine framework for identifying drug-repurposing opportunities for covid-19. Proceedings of the National Academy of Sciences, 2021.
Anusha Nagabandi, Chelsea Finn, and Sergey Levine. Deep online learning via meta-learning Con- tinual adaptation for model- based RL. In International Conference on Learning Representations, 2019.
Seth Neel, Aaron Roth, and Saeed Sharifi- Malaai-iMa..jjrdi.. Descent-to-delete: Gradient- methods for machine unlearning. In Proceedings of the International Conference on Algorithmic Learning Theory, 2021.
Giang Hoang Nguyen, John Boaz Lee, Ryan A. Rossi, Nesreen K. Ahmed, Eunyce Koh, and Sungchul Kim. Continuous-time dynamic network embeddings. In Companion Proceedings of the The Web Conference, 2018
Quoe Phong Nguyen, Bryan Kian Hsiang Low, and Patrick Jaillet. Variational bayesian unlearning. In Advances in Neural Information Processing Systems, 2020.
Iyiola E Olatunji. Wolfgang Nejdl, and Megha Khosla. Membership inference attack on graph neural networks. In Proceedings of the IEEE International Conference on Trust, Privacy and Security in Intelligent Systems and Applications, 2021.
Francesco Orabona. modern introduction to online learning. 2019.
Nishchal Parne, Kyathi Puppaala, Nithish Bhupathi, and Ripon Patgiri. Machine unlearning: Learning, polluting, and unlearning for spam email. arXiv, 2021.
Ladislav Rampášek, Mikhail Galkin, Vijay Prakash Dwivedi, Anh Tuan Luu, Guy Wolf, and Do- minique Beaini. Recipe for general, powerful, scalable graph transformer. In Advancses in Neural Information Processing Systems, 2022.
Alexandre Sablayrolles, Matthijs Douze, Yann Ollivier, Cordelia Schmid, and Hervé Jégou. White- box vs black-box: Bayes optimal strategies for membership inference. In Proceedings of the International Conference on Machine Learning. 2019.
Sebastian Schelter. Stefan Grafberger, and Ted Dunning, Hedgecut: Maintaining randomised trees for latenyy machine unlearning. In Proceedings of the International Conference on Management of Data, 2021.
12

---

Published as a conference paper at ICLR 2023
Michael Schlichtkrull, Thomas N Kipf, Peter Bloem, Rianne den Berg, Ivan Titov, and Max Welling. Modeling relational data with graph convolutional networks. In European Semantic Web Conference, 2018.
Ayush Sekhari, Jayadev Acharya, Gautam Kamath, and Ananda Theertha Suresh. Remember what you want to forget: Algorithms for machine unlearning. In Advances in Neural Information Processing Systems, 2021.
Takashi Shibata, Go Irie, Daiki Ikami, and Yu Mitsuzumi. Learning with selective forgetting. In Proceedings of the International Joint Conference on Artificial Intelligence, 2021.
David M. Sommer, Liwei SOng, Sameer Wagh, and Prateek Mittal. Athena: Probabilistic verification of machine unlearning. 2022.
Ayush K Tarun, Vikram S Chundawat, Murari Mandal, and Mohan Kankanhalli. Fast yet effective machine unlearning. arXiv, 2021.
Anvith Thudi, Gabriel Deza, Varun Chandrasekaran, and Nicolas Papernot. Unrolling sgd: Under- standing factors influencing machine unlearning. In Proceedings of the IEEE European Symposium on Security and Privacy, 2022a.
Anvith Thudi, Hengrui Jia, Ilia Shumailov, and Nicolas Papernot. On the necessity of auditable algorithmic definitions for machine unlearning. 2022b.
Anvith Thudi, Ilia Shumailov, Franziska Boenisch, and Nicolas Papernot. Bounding membership inference. arXiv, 2022c.
Enayat Ullah, Tung Mai, Anup Rao, Ryan A Rossi, and Raman Arora. Machine unlearning via algorithmic stability. In Proceedings of the Annual Conference on Learning Theory, 2021.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, L ukasz Kaiser, and Illia Polosukhin. Attention is all you need. Advances in Neural Information Processing Systems, 2017.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Representations. 2018.
Junxiao Wang. Song Guo, Xin Xie, and Heng Qi. Federated unlearning via class-discriminative pruning. In Proceedings of the ACM Web Conference 2022, 2022.
Alexander Warnecke, Lukas Pirch, Christian Wressnegger, and Konrad Rieck. Machine unlearning of features and labels. Network and Distributed System Security Symposium, 2023.
Yinjun Wu, Edgar Dobriban, and Susan Davidson. DeltaGrad: Rapid retraining of machine learning models. In Proceedings of the International Conference on Machine Learning, 2020.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In International Conference Learning Representations, 2019.
Minkai Xu, Lantao Yu, Yang Song, Chence Shi, Stefano Ermon, and Jian Tang. Geodiff: A geometric diffusion model for molecular conformation generation. International Conference on Learning Representations, 2022.
Samuel Yeom, Irene Giacomelli, Matt Fredrikson. and Somesh Jha. Privacy risk in machine learning: Analyzing the connection to overfitting. ACM SIGSAC Conference on Computer and Communi- cations Security, 2019.
Chengxuan Ying. Tianle Cai, Shengjie Luo, Shuxin Zheng, Guolin Ke, Di He, Yanming Shen, and Tie- Yan Liu. Do transformers really perform badly for graph representation? In Advances in Neural Information Processing Systems, 2021.
Rex Ying, Dylan Bourgeois, Jiaxuan You, Marinka Zitnik, and Jure Leskovec. Gnnexplainer: Generating explanations for graph neural networks. In Advances in Neural Information Processing Systems, 2019.
13

---

Published as a conference paper at ICLR 2023
A FURTHER DETAILS ON RELATED WORK
Connection with Catastrophic Forgetting and Dynamic Network Embeddings. Despite the fact of forgetting knowledge, we argue that catastrophic forgetting (Kemker et al. 2018) not good fit for the machine unlearning setting. Specifically, catastrophic forgetting is 1) not targeted at particular set of data, 2) not guaranteed forget, i.e. adversarial agents may still find out the presence of what is forgotten in the training set; 3) not capable of handling an arbitrary amount of deletion requests. Dynamic network embedding (Nguyen et al. 2018) learns network representations by incorporating time information and can deal with data deletion. However, these methods are designed to process graphs that are inherently changing over time. On the other hand, machine unlearning aims at deleting a specific set of training data, while keeping the majority of the underlying graph fixed. It aims at targeted data removal requests and is thus orthogonal to the above two approaches.
Connection with Techniques for Achieving Privacy in ML Models. Privcc--reeeevinn is another related preeeeringn learning scheme, such as federated learning (FL) (Konečný et al. (016) To let FL models unlearn data in a similar privacy-preserve first federated unlearning framework by leveraging historical parameter updates. Chen et (2021c)
way, [iu et al. (2021) proposed the
proposed new attack and metries improve privacy protection, which provides insights on practical implementations of machine unlearning. Golatkar et al. (2021) proposed machine unlearning in a from
mixed-privacy setting by splitting the weights into a set of core and forgettable user weights. Different
algorithms that aim at protecting data privacy during training and inference, the goal of machine unlearning, most of the time, is to retrieve privacy, which has no conflict.
Machine Unlearning for Other Tasks. Given the increasing necessity of machine unlearning. researches have studied machine unlearning algorithms tailored for other tasks. For example, Chen et al. (2022a) and Li et al. (2022b) propose machine unlearning frameworks for recommendation systems by considering the collaborative information. In addition, recent unlearning methods use Bayesian and latent models (Nguyen et al.) 2020; Kassab & Simeone 2022 Sekhari et al. 1021).
Machine unlearning (MU) has also been applied for other tasks, including verification of MU
(Sommer et al., 2022), re-definition of MU (Thudi et al., 2022b), test of MU (Goel et al.) 2022).
zero-shot MU (Chundawat et al. 2022). tree-based MU (Schelter et al. (021), coded MU (Aldaghri
al. 2021), y pruning based federated MU (Wang et al. 2022), adaptive sequence deletion MU (Gupta
et al. 2021), ), MU for k-means (Ginart et al.] 2019). MU for features and labels (Warnecke et al.
2023). ). MU for spam email detection (Parne al. 2021). MU for linear models (Mahadevan & Mathioudakis/ 2021). While the above mentioned methods have shown new directions for machine unlcarning, they are not comparable to our work as we focus on general graph unlearning instead of specific ML task.
B PROOF OF THEOREM
For the L-th GNN layer, we assume for sake of simplicity that the final node representation z, for node u is computed as:
Z,, - -
W WW hi
Σ Wah!-!).
(8)
vEN.
where a is the sigmoid function, and, and W1, W2 are the weight parameters for the GNN layer. Similarly, for the unlearned L-th layer we have:
=
where Wh's 's are the weight parameters for the DEL operator. For given edge euo E Ea that is be deleted, we expect for the dot product (Zu, 2.) to be maximized, as is an existent edge in the initial graph, while (z/,- =0) to be fixed, so that the edge probability is close to 0.5. following the Deleted Edge Consistency property. Specifically, the difference of the two terms can be bounded as:
1 [1] 122 + || 1|z- 1)) (1 + || + || 2/. 21,113)
(Zus zu)
(2/45 2/11)
2
(Zu, zu) - (2//0 2/1 Normalization
1 1|2u z 112 1-2-
2 011211 2111
(10)
14

---

Published as a conference paper at ICLR 2023
Then, simplifying Equations
8 Jaddl 9 we have:
< 2''ll
(W o (Wb)z))
Lipechitz
W Wh
Cauch--Schwarte
|| zu!l
and applying that to Equation 10
1 | zul1 1 [| =0
(Zur ze) (Z z,0
(11)
1 (1 +
(Zus Zud (z'==²²)
W
|1l)) z012
2
C EXPERIMENTS
In this section, we give further details on the experimental setup. We firstly present the used evaluation metries for the edge and node deletion, then we describe the sampling strategies for &,, and Ea, dataset statistics, and finally we present the full results for the model efficiency and the prediction performance of the models.
C.I EVALUATION METRICS
We choose the following performance metrics to measure the effectiveness of the deletion operation on the set of the deleted edges & and the test set & that contains a subset of the remaining edges: For the edge deletion case, we have:
AUROC and AUPRC on the test set & these metrics measure the prediction perfomance of each graph graph learning model over the existent edges of the test set &,. High values of AUROC and AUPRC on & show that the unlearned model's performance on the original test set is not affected by the deletion of edge subset.
AUROC and AUPRC the set of deleted edges Ex: these metrics quantify the ability of the unlearned models to distinguish deleted edges (contained in Ex) from the remaining edges (contained in E, For the computation of the area under the curve, take into account the total of the deleted edges in & and we sample an equal amount of remaining edges from & Then, we the labels of the deleted edges equal to 0 (since they do not exist after deletion), and the labels of the remaining edges to 1. Higher values of the AUC on Ed show that the model is more capable of distinguishing edges in E from edges in E,-
For the node deletion case, capitalize the evaluation for privacy leakage with Membership Inference (MI) (Thudi et al. 2022a) attacks. An unlearned model f' effectively forgets & if an MI attacker returns that Eg is not present in the training set, i.e., the probability of predicting the presence of Eạ decreases.
MI Ratio: this metric quantifies the success rate of a Membership Inference (MI) attack, by calculating the ratio of presence probability of & before and after the deletion operator. We adapt the implementation from Olatunji et al. (2021) in our experiments. If the ratio is higher than means that the model contains less information about &g. If the ratio is less than 1, it means the model contains more information about Egg.
C.2 SAMPLING OF EDGES IN & AND E
We sample 5% of the total edges as the test set (E₂) to evaluate the model's performance on link prediction and sample another 5% validation set for selecting the best model. We propose two sampling strategies for sampling & for edge deletion tasks: i) Êa,ouT refers to randomly sampling edges outside the 2-hop enclosing subgraph &,, i.e., Ê,,OuT = {ele & S and ii) & refers to randomly sampling edges from the 2-hop enclosing subgraph of &,, i.c., E,,N = fele e $2 We note that deleting Ex iN is more difficult than deleting Ed,our the deletion operation will have
15

---

Published as a conference paper at ICLR 2023
an impact on the local neighborhood of Ed, where & is located. For comparison of these two sampling strategies, please refer to the Appendix (Tables 13 14) fore results on Cora, Tables 16
for results on PubMed, Tables 17 18 on DBLP, Tables 19 20 OGB-Collab, and Tables 21 WordNet18.
C.3 EVALUATED DATASETS
Table presents the size of the graphs and the maximum number of deleted edges in the experiments, ranging from small to large scales.
Table 4: Statistics of evaluated datasets and a maximum number of deleted edges.
Graph
Nodes
# Edges
Unique edge types
Max # deleted edges
Cora
19,793
126,842
6,342
PubMed
19,717
88,648
4,432
DBLP
17,716
105,734
5,286
CS
18,333
163,788
8,189
OGB-Collab
235,868
2,358,104 104
117,905
WordNet18
40,943
151,442
18
7,072
OGB-BioKG
93,773
5,088,434
51
127,210
C.4 MODEL EFFICIENCY
Space efficiency. Space efficiency reflected by the number of trainable parameters a model has. We report number of parameters for all methods in Table We can observe that GNNDELETE has the smallest model size, which does not scale with respect to the size of the graph. This proves the efficiency and scalability of GNNDELETE. where we usually have to divide the original graph into 10 or 20 shards, each requiring a separate GNN model.
also significantly smaller than GRAPHERASER,
Table 5: Space efficiency of unlearning models. All models are trained on OGB-Collab and OGB-BioKG to delete 5.0% of edges, using 2-layer GCN/R-GCN architecture with 128, 64, 32 hidden dimensions, with the number of shards in GRAPHERASER as 10. Shown is number trainable parameters in deletion model.
Model
OGB-Collab
OGB-BioKG
RETRAIN
5,216
12,009,792
GRADASCENT
5,216
12,009,792
D2D
5,216
12,009,792
GRAPHERASER
52,160
220,097,920
GRAPHEDITOR
5,216
N/A
CERTUNLEANE
5,216
N/A
GNNDELFTE
5,120
5,120
Layer-wise unlearning vs. Last layer-only unlearning. Even though GNNDELETE achieves good efficiency, it may still be expensive when deleting large number of nodes/edges. GNNDELETEE can function under such extreme conditions and alleviate the computation cost by adopting a Last layer-only strategy, where single deletion operator is inserted after the last layer. As shown in Table 6 last layer-only GNNDELETE does not lead to significant performance degradation, with only 0.7% % and 0.9% drop on link prediction performance on &, and &,, respectively. While existing unlearning models don't 't have such flexibility to run in an lightweight fashion.
C.5 EVALUATIONS ON OTHER DOWNSTREAM TASKS
We recognize that the deleted information has influence many downstream tasks. For example, removing edges impacts node classification performance as well. We evaluate unlearning methods on three canonical downstream tasks: node classification, link prediction, and 3) graph classification.
16

---

Published as a conference paper at ICLR 2023
Table 6: Comparison between layer-wise and last layer-only GNNDELETE. Unlearning task: 2.5% edge
deletion DBLP. Evaluated on: link prediction. Performance AUROC (t).
Model
&
Ed
RETRAIN
0.964 00003
0,506
#0.013
GNNDELETE layer-wise
0.934
-0002
0.748
GNNDELETE last layer-only
0.927 10.005
0.739 100005
In addition to link prediction evaluation in Table we summarize the performance on other two downstream tasks in Table
Table 7: Unlearning task: 2.5% edge deletion. Evaluated on: node classification on DBLP (Aceuracy (f)) and graph classification on ogbg-molhiv (AUROC (1)), The best performance is marked in bold and the second best in nderline.
Model
Node classification
Graph classification
RETRAIN
0.810 =0.021
0,758 #0.068
GRADASCENT
0.614 =0.042
0,601 #0.063
D2D
0.250 1.00000
0.572 10.013
GRAPHÉRASER
0.682 10.04
0.596 10.032
GRAPHEDITOR
0.711 1.0.39
0.613 10.03
CERTUNLEARN
0.739 +0.024
0.607 #0.028
GNNDELETE
0.782 +0,027
0.710 +0,04
C.6 NODE DELETION
GNNDELETE can be applied unlearn nodes in graph by optimizing the same loss function in Eq.77 7 Table g presents the results of randomly deleting 100 nodes on DBLP dataset. In addition to the standard node classification evaluation, we also present the performance on link prediction and graph classification.
Table 8: Unlearning task: 100 node deletion. Evaluated on: node classification, link prediction (AUROC (1)). Dataset: DBLP. The best performance is marked in bold and the second best in underline.
Model
Accuracy
F1
MI ratio
Link prediction
RETRAIN
0.845 +0.008
0.841
10.004
1,515
=0.034
0.973 +0.002
GRADASCENT
0.392 +0.026
0.341
40.035
1.021
20.113
0.571 +0.032
D2D
0.250 10.000
0.250
10.000
1.755
-0.065
0.507 +0.002
GRAPHERASER
0.718 10.014
0.716
0.975
-0.083
0.513 40.004
GRAPHEDITOR
0.765 +0.012
0.749
10.006
1.260
00.88
0.697 40.031
CERTUNLEARN
0.743 10.027
0.738 10.022
1.134
0.000
0.713 +0,025
GNNDELETE
0.793 100016
0.768 110.009
1,401
00082
0.938 1:0.004
C.7 NODE FEATURE DELETION
GNNDELETE can be applied to update node features by optimizing the same loss function in Eq, For node and edge level evaluation, randomly select 100 nodes and update Xa = 0. For graph classification evaluation, we randomly choose 100 graphs and update X,
C.8 SEQUENTIAL UNLEARNING
Problem Formulation (Sequential Graph Unlearning). Given a graph = EV,E, X), a fully
trained GNN model mG)), and sequence of edges Eseq.d {Ea.0, Ed. Ed.s), (aa.st,lEeegie 1Eseg,al S, where each deletion request Ea,; E &seq.d is a standard graph unlearning problem (as defined in Sec. 4). Then, sequential graph unlearning aims to unlearn every batch of edges E,, Exeg,d from the GNN model mG)) in a sequential manner meaning that a request E given to the unlearned model after E,,; has been successfully unleared.
17

---

Published as a conference paper at ICLR 2023
Table 9: Unlearning task: 100 node feature update. Evaluated node classification DBLP (Acc. (f)),
link prediction on DBLP (AUROC (t)), and graph classification on ogbg-molhiv (AUROC (t)). Bold: best performance. Underline: second best performance.
Model
Node classification
Link prediction
Graph classification
RETRAIN (reference only)
0.810 #0.011
0.897 =00025
0.753 =0.042
GRADASCENT
0.614 40,02
0.655 100030
0.623 10.046
D2D
0,525 100009
0.504 1:0.00
0.586 1:0.017
GRAPHERASE
0.682 10.44
0.579 1:0.021
0.592 1.0002
GRAPHEDITOR
0,711 40:039
0.683 +00031
0.630 +0.026
CERTUNLEARN
0.739 +0.024
0.667 10.019
0.687 +00030
GNNDELETE
0.782 10.027
0.850 1.0.027
0.724 1.0027
GNNDelete is designed to handle a sequence of deletion requests. In stark contrast to existing deletion techniques (GraphEraser (Chen et al. (0022)). GraphEditor (Cong & Mahdavi [2023). Lescent-to-Delees (Neel et al. 2021)), GNNDelete does not require retraining from scratch for additional incoming deletion requests. It achieves sequential unlearning by continuing training the same deletion operator. As Ed,; o Ed,i+1, we can maintain a binary mask to easily turn on and off the deletion operator for specific nodes following the definition in Eq. 3 This is specified by the binary mask containing information about what node representations are to be updated in the DEL operator.
Table 10: Unlearning task: 2.5% sequential edge deletion, with a batch size of 0.5%. Evaluated on: link prediction. Dataset: DBLP. Performance is shown in AUROC (1) on GCN architecture.
Ratio (%)
Ed
0.5
0.951
0.829
1.0
0.949
0.808
1.5
0.943
0.791
2.0
0.938
0.776
0.934
0.748
C.9 COMPARISON WITH DYNAMIC NETWORK EMBEDDING (DNE)
Graph unlearning can be formulated as a special case of dynamic network. Despite that, we argue that they are fundamentally different. Graph unlearning usually refers to deleting a small part of the graph, while the majority of the graph remains stable. We want a graph unlearning algorithm to selectively forget something has captured during training. On the contrary, dynamic networks are intrinsically changing over time. The goal of DNE methods is to learn such evolution.
As shown in Table II DNE methods are not applicable to graph unlearning task out of the box, emphasizing the need for algorithms designed for graph unlearning.
Table 11: Comparison of Graph Unlearning and Dynamic Network Embedding (DNE). Unlcarning task: 2.5% % edge deletion. Evaluated on: link prediction. Dataset: DBLP. Performance is in AUROC (t).
Model
Ea
RETRAIN (reference only)
0.964 10.003
0.506
10.013
JODIE (DNE)
0.801 +0.422
0.613
=0.026
GNNDELETE (Unlearning)
0.934 10.002
0.748 10.006
C.10 EVALUATE NODE EMBEDDINGS ON OUTLIER DETECTION
D ADDITIONAL DETAILS ON RESULTS
We detail all the results from different graphs, GNN architectures, models, and deletion ratios.
18

---

Published as a conference paper at ICLR 2023
Table 12: Unlearning task: 2.5% edge deletion on DBLP. Evaluated on: outlier detection. We compute the percentage (f) of edges that are classified as regular edges, i.e., non-outliers on GCN architecture.
Model
Percentage
RETRAIN (reference only)
0.746
GRADASCENT
0.503
D2D
0.517
GRAPHERASER
0,563
GRAPHEDITOR
0,642
CERTUNLEARN
0.625
GNNDELETE
0.710
Table 13: Unlearning task: edge deletion when & = Edr our Evaluation: link prediction. Dataset: Cora.
Reported is AUROC (1) performance with the best marked in bold and the second best underlined.
Ratio
GCN
GAT
GIN
Model
(%)
3
Ed
&
Ed
RETRAIN
0.965 =0.002
0.783
10.018
0.961
+0.00
0.756
#0.013
0.961
#0.002
0.815
+00015
GRADASCENT
0,536 20.010
0.618
#0.014
0.517
+0.077
0.558
#0.034
0.751
#0.049
0.778
+00043
0.5
D2D
0,500 10.000
0.500
1..000
0.500
1.0000
0.500
10.000
0,500
10.000
0.500
10.000
GRAPHERASER
0.563 #0.002
0,500
#0.000
0.553
+0.013
0,500
=0.000
0.554
+0.009
0.500
+0,000
GRAPHEDITOR
0.805 20.077
0.614
10.054
CERTUNLEARN
0.814
10.065
0.603
1:0039
GNNDELETE
0.958
=0.002
0.977
=0.001
0.953
+0.002
0.979
=0.001
0.956
+0.003
0.953 0.0000
RETRAIN
0.966 =0.001
0.790
#0.009
0.961
+0.002
0.758
#0.011
0.961
#0.003
0.833
+00010
GRADASCENT
0.504 20.002
0.494
10.004
0.510
+0.019
0.522
#0.023
0.603
+0.039
0.605
+00030
2.5
D2D
0,500 10.000
0,500
10.000
0.500
10.000
0.500
10.000
0,500
10.000
0.500
100000
GRAPHERASER
0.542 #0.002
0,500
#0.000
0.519
+0.013
0,500
=0.000
0.563
+0.009
0,500 +0,000
GRAPHEDITOR
0.754
10.023
0.583
10.056
CERTUNLEARN
0.795
+0.037
0.578
#0.015
GNNDELETE
0.953
=0.002
0.912
#0.004
0.949
10.003
0.914
00.004
0.953
+0.002
0.922 0.000
RETRAIN
0,966 #0.002
0,812
#0.006
0.961
+0.001
0.778
#0.00
0.960
#0.003
0.852
+0000
GRADASCENT
0.557 10.122
0.513
1:0 106
0.520
+0.042
0.517
20.036
0,580
+0.027
0.572
+.0018
5.0
D2D
0,500 10.000
0.500
10.000
0.500
+0.000
0.500
#0.000
0,500
+0.000
0.500
100000
GRAPHERASER
0.514
#0.002
0,500
#0.000
0.523
+0.013
0,500
=0.000
0.533
+0.009
0,500 +0,000
GRAPHEDITOR
0.721
10.048
0.545 100056
CERTUNLEARN
0.745
+0.033
0.513
#0.012
GNNDELETE
0.953 10.003
0.882 10.005
0.951 1.0.002
0.872
10.004
0.950
10.003
0.914 0.0004
Table 14: Unlearning task: edge deletion when & = Ea Evaluation: link prediction. Dataset: Cora.
Reported is AUROC (f) performance with the best marked in bold and the second best underlined.
Ratio (%)
Model
GCN
GAT
GIN
&
Ea
Ed
&
Ea
RETRAIN
0.965 20.002
0.511
10.024
0.961
+0.001
0.513
10.024
0.960
10.003
0.571
+00028
GRADASCENT
0.528 10.008
0.588
10.014
0.502
10.002
0.543
10.058
0.792
10.046
0.705
10.113
0.5
D2D
0.500
=0.000
0.500
#0.000
0,500
+0.000
0,500
=0.000
0,500
+0.000
0.500
+0.000
GRAPHERASER
0.528
10.002
0.500
10.000
0.523
100033
0.500
10.000
0.542
10.009
0.500
10.000
GRAPHEDITOR
0.704
=0.057
0.488
+0.024
CERTUNLEARN
0.811
+0.035
0.497
10.013
GNNDELETE
0.944
10.003
0.843
0.937
10.004
0.880
10.011
0.942
10.005
0.824
100021
RETRAIN
0.966 10.002
0.520
10.008
0.961
1.00001
0.520
10.012
0.958
10.002
0.583
10.007
GRADASCENT
0.509 10.006
0.509
10.007
0.490
1:0007
0.551
20.014
0.639
+00077
0.614
10.016
2.5
D2D
0.500 =0.000
0.500
+0.000
0,500
+0.000
0.500
20.000
0,500
+0.000
0,500
+0.000
GRAPHERASER
0.517 10.002
0.500
110.000
0.556
10.013
0.500
10.000
0.547
10.009
0.500 10.000
GRAPHEDITOR
0.673 +0.091
0.493
#0.027
CERTUNLEARN
0.781
+0.042
0.492
10.015
GNNDELETE
0.925 1.000
0.716
:10.003
0.928
100007
0.738
1.000
0.919
1..004
0.745
10000
RETRAIN
0.964 10.002
0.525
10.008
0.960
10.001
0.525
10.007
0.958
10.002
0.591
10.006
GRADASCENT
0.509 10.005
0.487
10.003
0.489
10.015
0.537
20.007
0,592
+0.031
0.583
+0.013
5.0
D2D 0.500 +0.000
0.500
+0.000
0,500
+0.000
0.500
20.000
0,500
00.000
0.500
+0,000
GRAPHERASER
0.528
10.002
0.500
10.000
0.517
10001
0.500
10.000
0.530
10.009
0.500 10.000
GRAPHEDITOR
0,587
10.014
0.475
+0.015
CERTUNLEAAN
0.664
+0.023
0.457 +0.021
GNNDELETE
0,916 0.007
0.680 1:0.006
0.920 1.0.00
0.700
0.000
0.900
1.000
0.717 0.000
19

---

Published as a conference paper at ICLR 2023
Table 15: Unlearning task: edge deletion when &, our. Evaluation: link prediction. Dataset: PubMed. Reported AUROC (1) performance with the best marked bold and second best underlined.
Ratio
GCN
GAT
GIN
Model
(%)
&
E,
Ed
&
Ed
RETRAIN
0.968 +0.001
0.687
10.02
0.931
1:0000
0.723
=0.026
0.941
10.004
0.865
10012
GRADASCENT
0,458 10.139
0.539
10.091
0.450
100017
0.541
10.049
0.518
10.122
0.528
100021
D2D
0.500 10.000
0.500
1.0000
0.500
10.000
0.500
10.000
0,500
1..000
0.500
10.000
0.5
GRAPHERASER
0.529 =0,013
0,500
+0.000
0.542
+0.004
0,500
#0.000
0.535
+0.003
0.500
+0,000
GRAPHEDITOR
0.732
#0.043
0,603
+0.015
CERTUNLEARN
0.724
100012
0.597
1.00029
GNNDELETE
0.961 =0.004
0.973
+0.005
0.926
+:0006
0.976
=0.005
0.940
+0.00
0.963 0.0010
RETRAIN
0.967 10.001
0.696
0.930
1:0.00
0.736
10.011
0.942
10.005
0.875
10.008
GRADASCENT
0.446 10.130
0.500
#0.067
0.582
+0.006
0.758
+0.033
0,406
10.054
0.454
#00337
D2D
0.500 10.000
0.500
1.0000
0.500
1..000
0.500
1.0000
0.500
10.000
0.500
1.0000
2.5
GRAPHERASER
0,505
#0.024
0,500
#0,000
0.538
+0.009
0,500
=0.000
0.544
#0.014
0.500 +00000
GRAPHEDITOR
0.689
20.015
0,570
10.011
CERTUNLEARN
0.697
10.012
0.582
100032
GNNDELETE
0.954
#0.003
0,909
20.004
0.920
+:0004
0.916
00.00
0.943
+0.00
0.938
+.0009
RETRAIN
0.966 10.001
0.707
10.0004
0.929
1.0000
0.744
10.008
0.942
100004
0.885
1.0010
GRADASCENT
0.446 12.126
0.492
10.064
0.581
10.010
0.704
10.022
0.388
10.056
0.455
#0,028
D2D
0.500 10.000
0.500
1:00000
0.500
1.0000
0.500
1.0000
0.500
10.000
0.500
1:0000
GRAPHERASER
0,532 #0.001
0,500
#0.000
0.527
+0.022
0,500
=0.000
0.524
#0.015
0.500
+0,000
GRAPHEDITOR
0.598 20.023
0.530
10.006
CERTUNLEARN
0.643
10.031
0.534 10.020
GNNDELETE
0.950 00.003
0.859
10,05
0.921
+0.005
0.863 0.000
0.941 +0.002
0.930 +.0009
Table 16: Unlearning task: edge deletion when Ea Ed. Evaluation: link prediction. Dataset: PubMed.
Reported is AUROC (1) performance with the best marked bold and the second best underlined.
Ratio (%)
GCN
GAT
GIN
Model
E,
Ea
E,
Ed
E,
E.
RETRAIN
0.968 #0.001
0.493
+0.040
0.931
+0.003
0.533
=0.037
0.940
000002
0.626
+0.01
GRADASCENT
0.469 10.095
0.496
10.058
0.436
+0.028
0.553
10.029
0.687
10.060
0.556
+0.02
D2D
0.500 10.000
0.500
10.000
0.500
+0.000
0.500
10.000
0.500
10.000
0.500
10.000
GRAPHERASER
0.547
#0.004
0,500
#0.000
0.536
+0.000
0.500
=0.000
0.524
+0.002
0.500
+0.000
GRAPHEDITOR
0.669
10.005
0.469
10.021
CERTUNLEARN
0.657
10.055
0.515
+0.027
GNNDELETE
0.951
=0.005
0.838
10.014
0.909
1:0.003
0.888
10.016
0.929
10.006
0.835
+.0006
RETRAIN
0.968 10.001
0.499
10.019
0.931
10.002
0.541
10.013
0.937
10.004
0.614
10.015
GRADASCENT
0.470 10.087
0.474
10.039
0.522
1..066
0.704
10.086
0.631
10.050
0.499
10018
D2D
0.500 =0.000
0.500
+00000
0.500
+00000
0.500
10.000
0.500
+0.000
0.500
+0.000
GRAPHERASER
0.538
=0.003
0,500
+0.000
0.521
+0.003
0.500
=0.000
0.533
+0.010
0,500
+0,000
GRAPHEDITOR
0.657
1.0006
0.467
1.0.066
CERTUNLEARN
0.622
#0.009
0.468
1:0022
GNNDELETE
0.920
10.014
0.739
1100000
0.891
100.00
0.759
10.012
0.909
10.005
0.782
1.0.13
RETRAIN
0.967 10.001
0.503
1:0000
0.929
10.003
0.545
10.005
0.936
10.005
0.621
10.003
GRADASCENT
0.473
#0.090
0.473
#0.038
0.525
+0.069
0.686
+0.09
0.635
+0.073
0.493
+00088
5.0
D2D
0.500 10.000
0.500
10.000
0.500
10.000
0.500)
10.000
0.500
10.000
0.500
+0,000
GRAPHERASER
0.551
10.004
0.500
10.000
0.524
+0.020
0.500
10.000
0.531
+0.000
0.500
+0,000
GRAPHEDITOR
0,556
+0.007
0.468
+0.002
CERTUNLEARN
0.572
10.013
0.477 1.0028
GNNDELETE
0.916
0.000
0.691 100012
0.887
1:0.009
0,713 0.000
0.895
10.004
0.761 +.0.00
20

---

Published as a conference paper at ICLR 2023
Table 17: Unlearning task: edge deletion when &a Ed,our. Evaluation: link prediction. Dataset: DBLP.
Reported AUROC (1) performance with the best marked bold and second best underlined.
Ratio
GCN
GAT
GIN
Model
(%)
&
En
Ed
Ed
RETRAIN
0.965 +0.002
0.783
10018
0.956
100000
0.744
=0.021
0.934
10.003
0.861
100019
GRADASCENT
0.567 10.008
0.696
100017
0.501
10.000
0.667
10.052
0.753
10.055
0.789
100091
0.5
D2D
0.500 =0.000
0.500
#0.000
0.500
+0.000
0.500
=0.000
0.500
+0.000
0.500
+0,000
GRAPHERASER
0.518 10.002
0.500
100000
0.523
10.013
0.500
10.000
0.517
10.009
0.500
10,000
GRAPHEDITOR
0.790
=0.032
0,624
#0.017
CERTUNLEARN
0.763
1:0025
0.604
1..022
GNNDELETE
0.959
=0.002
0.964
10.005
0.950
=0.002
0.980
=0.003
0.924
0.000
0.894 +.0000
RETRAIN
0.965 10.002
0.777
1:0.009
0.955
1.0000
0.739
10.005
0.934
10.003
0.858
1.0002
GRADASCENT
0.528 #0.015
0.583
100016
0.501
10.026
0.576
10.017
0.717
10.022
0.766
+00019
2.5
D2D
0,500 =0.000
0.500
#0.000
0.500
+0.000
0.500
=0.000
0.500
+0.000
0.500
+0,000
GRAPHERASER
0.515
100002
0.500
1.0.000
0.563
10.013
0.500
10.000
0.552
10.009
0.500
10,000
GRAPHEDITOR
0.769
20.040
0.607
10.017
CERTUNLEARN
0.747
20.033
0,616
1:00199
GNNDELETE
0.957 =0.003
0,892
#0.004
0.949
+0.003
0.905
=0.002
0.926
+0,007
0.898
000017
RETRAIN
0.964
0.788
0.955
1.0000
0.748
10.008
0.936
1.0.044
0.868
10.005
GRADASCENT
0.555
0.591 1:0065
0.501
+0.023
0.559
10.024
0.672
10.032
0.728
+0.022
5.0
D2D
0.500 =0.000
0.500 #0.000
0.500
+0.000
0.500
10.000
0.500
+0.000
0.500
#0,000
GRAPHERASER
0.541 10.002
0.500
1.00000
0.523
10.013
0.500
10.000
0.522
10.009
0.500
10.000
GRAPHEDITOR
0.735 +0.037
0.611 +0.018
EERTUNLEEAN
0.721 20.033
0,602
10.013
GNNDELETE
0.956 00.004
0.859 =0.002
0.949 +0.003
0.859 20.00
0.924 -0.007
0.898 1..019
Table 18: Unlearning task: edge deletion when & = Ed Evaluation: link prediction. Dataset: DBLP.
Reported AUROC (f) performance with the best marked bold and the second best underlined.
Ratio (%)
GCN
GAT
GIN
Model
E,
Ea
E,
Ed
E,
Ed
RETRAIN
0.965 10.003
0.496
0.957
10.002
0.513
10.021
0.934
10.005
0.571
10.035
GRADASCENT
0.556 =0.018
0.657
+0.008
0.511
+0.023
0.612
10.107
0.678
10.084
0.573
+0,05
0.5
D2D
0.500 10.000
0.500
10.000
0.500
+0.000
0.500
10.000
0.500
10.000
0.500
+0,000
GRAPHERASER
0.515 10.001
0.500
1.00000
0.523
10.000
0.500
10.000
0.507
10.003
0.500
10.000
GRAPHEDITOR
0.781
+0.026
0.479
#0.017
CERTUNLEAARY
0.742
20.021
0.482
10.013
GNNDELETE
0.951
=0.002
0.829
1:0006
0.928
1:0004
0.889
10.011
0.906
10.009
0.736
+-0012
RETRAIN
0.964 10.003
0.506
10.013
0.956
0.525
10.012
0.931
10.005
0.581
10.014
GRADASCENT
0.555 #0.066
0.594
+0.063
0.501
+0.020
0.592
10.017
0.700
#0.025
0.524
#00017
2.5
D2D
0.500 10.000
0.500
10.000
0.500
10.000
0.500
10.000
0.500
10.000
0.500
+0,000
GRAPHERASER
0.527 10.002
0.500
1:00000
0.538
10.013
0.500
10.000
0.517
10.009
0.500 10.000
GRAPHEDITOR
0.776
=0.025
0.432
+0.009
CERTUNLEARN
0.718
20.032
10.011 0.475
GNNDELETE
0.934
10.002
0.748
100006
0.914
10.007
0.774
10.015
0.897
10.006
0.740
1.0.15
RETRAIN
0.963 10.003
0.504
1:0.006
0.955
10.002
0.528
10.007
0.931
1.00006
0.578
10.009
GRADASCENT
0.555 #0.060
0.581
+00073
0.490
+0.022
0.55
=0.030
0.723
+0.032
0.516
+0.02
D2D
0.500 10.000
0.500
10.000
0.500
10.000
0.500)
10.000
0.500
100000
0.500
10,000
GRAPHERASER
0.509 10.011
0.500
+:0000
0.511
+00006
0.500
10.000
0.503
+00000
0.500 +0,000
GRAPHEDITOR
0.736
+0.023
0.430
+0.011
CERTUNLEARN
0.694
1.0026
0.441
10.0008
GNNDRLETE
0.917
00.00
0.713
10.007
0.912 1.00007
0.733 10.018
0.864 10.005
0.732 1-0.008
21

---

Published as a conference paper at ICLR 2023
Table 19: Unlearning task: edge deletion when = = Edr Evaluation: link prediction. Dataset: OGB-
Collab. Reported is AUROC (t) performance with the best marked in bold and the second best underlined.
Ratio
GCN
GAT
GIN
Model
(%)
Ea
&
&
Ed
RETRAIN
0.986 =0.001
0.553
+0.004
0.983
+0.001
0.541
=0.002
0.859
10.011
0.523
+0,003
GRADASCENT
0,606 =0.012
0.509
+0.002
0.674
+0.016
0.535
=0.020
0.665
#0.097
0.511
+0,009
0.5
D2D
0,500 10.000
0,500
100000
0.500
+0.000
0.500
#0.000
0,500
+0.000
0.500
+0,000
GRAPHERASER
0.544 10.000
0,500
1:0000
0.551
10.004
0.500
10.000
0,513
+0.009
0.500
10,000
GRAPHEDITOR
0.857
=0.010
0.497
#0.004
CERTÜNLEARN
0.841
10.005
0.478
1:0.066
GNNDELETE
0.985
=0.002
0.723
+:0002
0.983
1:0000
0.728
00.007
0.977
1.0004
0.715 0.0.05
RETRAIN
0.986 =0.001
0.553
100001
0.983
+00001
0.541
=0.002
0.858
+00006
0.525
+0,00
GRADASCENT
0,531 =0.047
0,552
+0.006
0.562
+0.032
0.543
#0.003
0,645
+0.094
0,513
+00008
2.5
D2D
0.500 10.000
0,500
1:0000
0.500
1.00000
0.500
10,000
0,500
+0.000
0.500
10,000
GRAPHERASER
0.517
#0.000
0,500
100000
0.524
+0.009
0.500
+0.000
0.542
+0.001
0.500
+0.000
GRAPHEDITOR
0.839
+0.002
0,465
#0.002
CERTUNLEARN
0.822
10.002
0.473 100010
GNNDELETE
0,983 +0.002
0.642 =0.002
0.983 +00000
0.639 0.003
0.963 +0000
0.647 0.000
Table 20: Unlearning task: edge deletion when E Ed, ms- Evaluation: link prediction. Dataset: OGB- Collab. Reported is AUROC (t) performance with the best marked in bold and the second best underlined.
Ratio
GCN
GAT
GIN
Model
(%)
E,
E3
Eg
&
Ed
RETRAIN
0.986 10.001
0.521
10.002
0.983
1.0000
0.644
10.002
0.855
10.007
0.599
10.003
GRADASCENT
0.552 =0.093
0.505
10.003
0.559
10.154
0.569
#0.034
0.658
+0.088
0.524
40.014
0.5
D2D
0.500 =0.000
0.500
+0.000
0.500
+0.000
0.500
=0.000
0,500
+0.000
0.500
+0.000
GRAPHERASER
0.554 10.002
0.500
1:00000
0.512
10.00
0.500
10.000
0.532
10.002
0.500
10.000
GRAPHEDITOR
0.840 #0.002
0.571
#0.003
CERTÜNLEARN
0.825
20.004
0.583
1:0005
GNNDELETE
0.976
1.0002
0.715
110.002
0.974
1.0001
0.814
10.011
0.935
10.005
0.663
1.0114
RETRAIN
0.986 10.001
0.532
10.0002
0.982
10.001
0.650
10.004
0.845
10.010
0.612
10.003
GRADASCENT
0.577 =0.005
0.534
100006
0.697
+0.000
0.541
10.018
0,568
+0.097
0.585
+0.04
2.5
D2D
0.500 +0.000
0.500
+0.000
0.500
100000
0.500
10.000
0.500
+0.000
0.500
+0.000
GRAPHERASER
0.539
0.500
110.000
0.542
10.01
0.500
10.000
0.528
10.009
0.500
10.000
GRAPHEDITOR
0.811
=0.002
0.575
+0.001
CERTÜNLEARN
0.803
10.005
0.547
:0.002
GNNDELETE
0.972 0.003
0.665 ::00002
0.966 1:0.00
0.772 10.015
0.974 ::0.003
0.675 0.010
Table 21: Unlearning task: edge deletion when E, = Ed,our. Evaluation: link prediction. Dataset:
WordNet18. Reported is AUROC (1) performance with the best marked in bold and the second best underlined.
Ratio (%)
R-GCN
R-GAT
Model
&
&
Eg
RETRAIN
0.801 -0.007
0.601
100014
0.898
+0.003
0.808
=0.015
GRADASCENT
0.499
=0.002
0.501
40.003
0.495
+0.001
0.411
=0.012
0.5
D2D
0.500
10.000
0.500
10.000
0.500
1..000
0.500
1:0.000
GRAPHERASER
0.517
10.001
0.511
10.003
0.533
10.004
0.508
100001
GNNDELETE
0.757
0.005
0,901
1.0000
0.899
+0.002
0.828
10.010
RETRAIN
0.804 +0.005
0.639
10.004
0.897
10.004
0.831
+0.005
GRADASCENT
0.493
100002
0.489
10.005
0.491
110.001
0.424
10.015
2.5
D2D
0.500
=0.000
0,500
#0.000
0.500
+0.000
0.500
=0.000
GRAPHERASER
0.515
+0.004
0.508
+.0005
0.533
+00003
0.505
+00004
GNNDELETE
0.758
0.005
0,902
10.000
0,898
1:0.002
0,836
1.0.05
RETRAIN
0.801
10.004
0.661
10.011
0.896
10.001
0.861
GRADASCENT
0.493
=0.001
0.485
#0.002
0.491
10.001
0.425
10.025
5.0
D2D
0.500
+0.00
0.500
+0.000
0.500
10.000
0.500 10.000
GRAPHERASER
0.525
0.000
0.504
1000001
0.531
1.0.004
0.502 1.0.00
GNNDELETE
0.756
20.044
0,910
1-0.0%
0.897 +0.002
0.852 20.04
22

---

Published as a conference paper at ICLR 2023
Table 22: Unlearning task: edge deletion when & = Ed.Iu- Evaluation: link prediction. Dataset:
WordNet18. Reported is AUROC (1) performance with the best marked in bold and the second best underlined.
Ratio (%)
Model
R-GCN &
R-GAT
E.
RETRAIN
0.802 #0.007
0.584
10.005
0.898
10.002
0.771
10.011
GRADASCENT
0.496
+0.002
0,486
=0.005
0.493
#0.001
0.487
=0.08
0.5
D2D
0.500
10.000
0.500
10.000
0.500
10.000
0.500
1.0.000
GRAPHERASER
0.505
+0,002
0.510
=0.001
0.502
10.000
0.502
+0.000
GNNDELETE
0.756
10.00
0.850
20.005
0.897
1:0002
0.819
10.014
RETRAIN
0.800 +0.005
0.580
=0.006
0.891
=00005
0.783
#0.009
GRADASCENT
0.490 10.001
0.477
10.006
0.490
100001
0.492 10.003
2.5
D2D
0.500
=0.000
0.500
100000
0.500
10,000
0.500
10.000
GRAPHERASER
0.512
+0,003
0.509
+0.004
0,545
+0.015
0.509 +0.00
GNNDELETE
0.751
1.0006
0.845
10.007
0.893
1.0002
0.786
10.04
RETRAIN
0.797 10.003
0.588
0.883
0.786
GRADASCENT
0.491 10.001
0,480
10.004
0.490
0.494
10.002
5.0
D2D
0.500
+0.000
0.500
=0.000
0.500
=0.000
0.500 +0.000
GRAPHERASER
0.507
10.003
0.511 100.005
0.518
1.0002
0.504 10.004
GNNDELETE
0.749 3:0005
0,850
0:0008
0,889
1000002
0.779 =00007
23


Reviews:
[{"review_id": "ZAqc3kxDcD_", "reviewer": "Reviewer_ctZT", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "main_review": "", "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). \n\nThis 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. ", "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.  ", "strength_and_weaknesses": "Strengths: \n- This paper studies an important topic. Graph unlearning is related to privacy-preservation on graphs and machine learning. \n- 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. \n- 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. \n- Overall, the paper is largely organized clearly and easy to follow. \n\nWeaknesses and questions. \n- 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. \n- 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). \n- 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. \n- 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. \n- 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. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "XZ28x3QxIWC", "reviewer": "Reviewer_Wk6L", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "main_review": "", "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.", "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.", "strength_and_weaknesses": "Strength\n\n1. The proposed method does not require extra information from the training process, which is required in many unlearning schemes.\n\n2. The proposed method can also be used for deleting nodes by removing all their associated edges.\n\n3. The algorithm is evaluated on a number o freal graph  datasets to demonstrate the effectiveness of the proposed approach for machine unlearning.\n\nWeakness\n\n1. 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.\n\n2. 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.\n\n3. 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?\n\n4. 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.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "XJJbRvONgd", "reviewer": "Reviewer_kuQk", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "main_review": "", "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.", "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.\n", "strength_and_weaknesses": "Strengths\n1. The two desired properties for graph unlearning effectively work as the goals of the problem.\n2. The proposed DEL operator can be generally used for various types of graph models.\n3. The performance of the proposed approach is significantly better than those of existing approaches.\n\nWeaknesses\n1. 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. \n2. 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?\n3. 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?\n\nQuestions\n1. What happens if we need to remove multiple edges? Should we run the algorithm multiple times? How long does it take?\n2. 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.\n\nMinor comments\n1. 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.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "EAInYMWA5dw", "reviewer": "Reviewer_PAk1", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "main_review": "", "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. ", "summary_of_the_review": "The paper presents an interesting idea. However, there are several issues about evaluation results to address. ", "strength_and_weaknesses": "The strengths:\n1) comparing to the partitioning based models, the proposed solution doesn't need to specify partitioning parameters that may have impact on the unlearning performance.\n2) the proposed method was shown to have better performance than baselines in evaluation \n\nThe weaknesses\n1) 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.\n2) 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?\n3) 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. \n4) 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? \n5) the evaluation mentioned node feature update unlearning tasks. However, there is no experiments about such tasks. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "1sWnxUi1Gs", "reviewer": "Reviewer_mYMM", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "main_review": "", "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.\n", "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.\n", "strength_and_weaknesses": "**Strength** \n- The paper provides a clear formulation of required unlearning properties, which motivates the design of the optimization objective\n- The proposed layer-wise deletion operator is efficient, flexible and provides theoretically bound for deleted edge prediction\n- Extensive evaluation is conducted to showcase the performance of the proposed method  \n\n**Weaknesses**\n- Performance on node deletion task seems to be less impressive\n\n**Questions**\n- 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$?\n\n- 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$? \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster