GraphEditor: An Efficient Graph Representation Learning and Unlearning Approach
Authors: Weilin Cong
Mehrdad Mahdavi
Venue: Submitted to ICLR 2023 (2023)
Keywords: graph representation learning
graph unlearning
machine unlearning
linear-GNNs

Abstract:  As graph representation learning has received much attention due to its widespread applications, removing the effect of a specific node from the pre-trained graph representation learning model due to privacy concerns has become equally important.
However, due to the dependency between nodes in the graph, graph representation unlearning is notoriously challenging and still remains less well explored. To fill in this gap, we propose \textsc{GraphEditor}, an efficient graph representation \textit{learning} and \textit{unlearning} approach that supports node/edge deletion, node/edge addition, and node feature update. Compared to existing unlearning approaches, \textsc{GraphEditor} requires neither retraining from scratch nor of all data presented during unlearning, which is beneficial for the settings that not all the training data are available to retrain. Besides, since \textsc{GraphEditor} is exact unlearning, the removal of all the information associated with the deleted nodes/edges can be guaranteed. Empirical results on real-world datasets illustrate the effectiveness of \textsc{GraphEditor} for both node and edge unlearning tasks.

Under review as a conference paper at ICLR 2023
GRAPHEDITOR: AN EFFICIENT GRAPH REPRESENTA- TION LEARNING AND UNLEARNING APPROACH
Anonymous authors Paper under double-blind review
ABSTRACT
As graph representation learning has received much attention due its widespread applications. removing the effect of a specific node from the pre-trained graph rep- resentation learning model due to privacy concerns has become equally important. However, due to the dependency between nodes in the graph, graph representation unlearning is notoriously challenging and still remains less well explored. To fill this gap, we propose GRAPHEDITOR, an efficient graph representation learning and unlearning approach that supports node/edge deletion, node/edge addition, and node feature update for linear-GNN GNN. Compared to existing unlearning approaches. GRAPHEDITOR requires neither retraining from scratch nor of all data presented during unlearning, which is beneficial for the settings that not all the training data are available to retrain. Besides, since GRAPUEDTTOR is exact unlearning, the removal of all the information associated with the deleted nodes/edges can be guaranteed. Empirical results on real-world datasets illustrate the effectiveness of GRAPHEDITOR for both node and edge unlearning tasks. The code can be found in supplementary.
INTRODUCTION
In recent years, graph representation learning has been recognized as a fundamental learning problem and has received much attention due to its widespread use in various domains, including social network analysis Kipf& & Welling (2017); Hamilton et al. (2017), traffic prediction Cui et al. (2019); Rahimi et al. (2018), knowledge graphs Wang et al. (2019a;b), and recommender systems Berg et al. (2017); Ying et al. (2018). However, due to the increasing concerns on data privacy, removing the effect of a specific data point from the pre-trained model has become equally important. Recently, "Right to be forgotten" Wikipedia contributors (2021) empowers the users the right to request the organizations or companies to have their personal data be deleted a rigorous manner. For example, when Facebook users deregister their account, users not only can request the company to permanently delete the account's 's profiles from the social network, but also require the company to eliminate the impact of the deleted data any machine learning model trained based on the deleted data, which is known as machine unlearning Bourtoule et al. (2021).
One of the most straightforward unlearning approaches is retrain the model from scratch using the remaining data, which could be computationally prohibitive when the dataset size is large or infeasible if not all the data are available to retrain. Recently, many efforts have been made achieve efficient unlearning, which can be roughly classified into exact unlearning and approximate unlearning, each of which has its own limitations. Exact unlearning: Bourtoule al. (2021) proposes to randomly split the original dataset into multiple disjoint shards and train each shard model independently. Upon receiving a data deletion request, the model provider only needs to retrain the corresponding shard model. Chen et al. (2021) extends Bourtoule et al. (2021) by taking the graph into consideration for data partition. However, splitting too many shards could hurt the model performance due to the data heterogeneity and lack of training data for each shard model Ramezani et al. (2021). On the other hand, too few shards result in retraining on massive data, which is computationally prohibitive; Approximate unlearning: Guo et al. (2020); Chien et al. (2022) proposes to approximate the unlearned model using first-order Taylor-expansion Golatkar et al. (2020) proposes to fine-tune tune with Newton's 's method on the remaining data, and Wu et al. (2020a) proposes to transfer the gradient computed at one weight to another and retrain the model from scratch with lower computational cost. Since approximate unlearning lacks guarantee whether all information associated with the deleted data are eliminated,

---

Under review as a conference paper at ICLR 2023
these methods require injecting random noise, which can significantly hurt the model performance. Employing graph representation unlearning is even more challenging due to the dependency between nodes that are connected by edges. We not only need to remove the information related to the deleted nodes, but also need to update its impact on neighboring remaining nodes of multi-hops. Since most of the existing unlearning methods only support data deletion, extending their application to graphs is non-trivial Motivated by the importance and challenges of graph representation unlearning, we aim at answering the following two questions:
Q1: Can approximate unlearning methods remove all information related to the deleted data? To verify this, we introduce "deleted data replay test" validate the effectiveness of unlearning in Section 5, Specifically, we add an extra-label category and change all deleted nodes to this extra-label category. To better distinguish deleted nodes from others, an extra binary feature is appended to all nodes and set the extra binary feature as "1" for the deleted nodes and as "0" for other nodes. We first pre-train the model on the dataset with extra label and feature, then we evaluate the effectiveness of unlearning method by comparing the number of the deleted nodes that are predicted the extra- label category before and after the unlearning process. Intuitively, an effective unlearning method should unlearn all the knowledge related to the additional category and binary feature, model after unlearning should never predict a node as the additional category. However, according to our observation, approximate unlearning fails to remove all information related the deleted data, which motivates us to design an efficient exact graph representation unlearning method.
Q2: If not, can design an efficient exact graph representation unlearning method? We propose an exact graph learning and unlearning algorithm GRAPUEDITOR which can efficiently update the parameters with provable low time complexity. GRAPHEDITOR not only supports node/edge deletion, but also node/edge addition and node feature update. The key idea of GRAPHEDITOR is to reformulate the ordinary GNN training problem as an alternative problem with the closed-form solution. Upon receiving a deletion request, GRAPHEDITOR takes the closed-form solution as input and quickly updates the model parameters only based on small fraction of nodes in the neighborhood of the deleted node/edge. Comparing to retraining from the scratch, GR GRAPHEDITOR only requires less data with a single step of computation, which is more suitable for the online setting that requires the model provider to immediately get the unlearned model or not all the training data available to retrain. Comparing to existing exact unlearning methods GRAPHER ERAEER Chen et al. (2021), I), GRAPHEDITOR enjoys better performance since the unlearned model does not suffer from data heterogeneity and lack of training data on each shard model. Comparing to approximate unlearning method INFLUENCE Guo al. (2020) and FISHER Golatkar et al. (2020), GRAPHEDITOR guarantees removing all information related to deleted nodes/edges and does not require integrating differential privacy noise to prevent information leakage after unlearning.
Contributions. We summarize our contributions as follows: I We introduce "deleted data reply test" to validate the effectiveness of unlearning methods and illustrate the insufficiency of approximate unlearning methods for removing all information related to the deleted nodes/edges.
2 We introduce a graph representation learning and unlearning approach GRAPHEDITOR on supports node/edge deletion, node/edge addition, and node feature update. 3 To improve the scalability and expressiveness, we introduce subgraph sampling and the non-linearity extension of GRAPHEDITOR. ④ Empirical studies on real-world datasets that illustrates its effectivvness.
which
2 RELATED WORKS
Exact machine unlearning. Exact unlearning aims to produce the performance of the model trained without the deleted data. The most straightforward way is to retrain the model from scratch, which is in general computationally demanding, except for some model-specific or deterministic problems such as SVM Cauwenherghs & Poggio (2001), K-means Ginart et al. (2019), and decision tree Brophy & Lowd (2021). Recently, efforts have been made to reduce the computation cost for general gradient-based training problems. For example, Bourtoule et al. (2021) proposes to split the dataset into multiple shards and train an independent model on each data shard, then aggregate their prediction during inference. The data partition schema allows for an efficient retrain of models smaller fragment of data. However, the model performance suffers because each model has fewer data to be trained on and data heterogeneity can also deteriorate the performance. Besides, GRAPHERASER Chen al. (2021) extends Bourtoule et al. (2021) to graph-structured
2

---

Under review as a conference paper at ICLR 2023
data by proposing graph partition method that can preserve the structural information much as possible and weighted prediction aggregation for inference. Ullah et al. (2021) proposes to train the model using mini-batch SGD and save the model parameters at each iteration. When receiving the deletion requests, retraining only starts at the iteration that deleted data first time appears. Neel et al. (2020); Ullah et al. (2021); Sekhari et al. (2021) study the unlearning from the generalization theory perspective, which is not the main focus of this paper.
Approximate machine unlearning. INFLUENCE Guo al. (2020) proposes to unlearn by removing the influence of the deleted data on the model parameters. Formally, let Da C 'D denote the deleted subset of training data, D,- D \ Du denote the remaining data, [(w) is the objective function, and w is the model parameters before unlearning. Then, INFLUENCE unlearn by w" = w + H, H,'ga. which is derived from the first-order Taylor approximation on gradient, where w is the parameters after unlearning, H V ((,, (D) is the Hessian computed on the remaining data, and gd = VL(w, Da) is the gradient computed on the deleted data. To mitigate the potential information leakage, INFLUENCE utilizes a perturbed objective function L(w) b w. where b is the random noise. Guo et al. (2020) requires the objective function be i.i.d., extending its application on graph is non-trivial because nodes in graph are non-i.i.d due to node dependency (details in Appendix E). Chien et al. (2022) extends the analysis of Guo et al. (2020) to graph. A similar idea is explored in Wu al. (2022). FISHER Golatkar al. (2020) performs Fisher forgetting by taking a single step of Newton's method on the remaining training data, then performing noise injection to model parameters to mitigate the potential information leaking. The model parameters after unlearning is given by w = w - H, g. H, 1/A,, where H, = L'L(W, D,) is Hessian and g. = VL(w, D,) is gradient computed on the remaining data D,, and b is the random noise. Golatkar al. (2021) generalizes the idea to deep neural networks by assuming a subset of training samples are never forgotten, which can be used to pre-train neural network as feature extractor, and only unlearn the last layer. Wu et al. (2020a) proposes to save all the intermediate weight parameters w. and gradients VL(W,, D) during training. Then, these information will be used to efficiently estimate the optimization path of strongly convex and smooth objective function after unlearning, which results in very limited applications. Khan & Swaroop (2021) proposes knowledge- adde-adappattinn priors to reduce the cost of retraining by enabling adaptation for wide variety of tasks and models. Similar ideas are explored in Ginart et al. (2019) for K-means and Wu et al. (2020b) for logistic regression. Wang et al. (2021a) observes that different channels have a varying contribution to different categories in image classification. Inspired by this observation, Wang et al. (2021a) proposes to quantize the class discrimination of channels and prune the most relevant channel of the target category to unlearn its contribution to the model. Izzo et al. (2021) propose approximate data deletion method, which has a time complexity that is linear in the dimension of the deleted data and is independent of the size of the dataset. Fu et al. (2022); Nguyen et al. (2022) study Bayesian inference unlearning, which is different from the neural network unlearning that we focused on.
3 PRELIMINARIES ON GRAPH REPRESENTATION UNLEARNING
Problem setup. Given a graph G(V,E) with N = |V] nodes as input, let us suppose each node V E V is associated with node feature vector h, (0) Let A, D NxN denote the adjacency matrix and its degree matrix, and the normalized propagation matrix is defined as P D 1122 AD For case of exposition, we take semi-supervised node classification as a rumning example, where a subset of nodes Virain V are labeled, our goal is predict the label for the rest nodes V } Viain using the information of the labeled nodes. Please notice that GR GRAPHEDITOR can also be applied to link prediction task for edge unlearning, which will be discussed in details in the appendix.
Graph neural network. The feed-forward rule in graph neural network (GNN) is defined as H - a (PH((II) where a()) is non-linear activation function, H() denotes the hidden representation at the ε-th layer. Then, a linear classifier is applied to the final layer node representation (L) for prediction. Although GNNs have become the de-facto tool for graph representation learning, employing unlearning strategies the ordinary GNNs is non-trivial. This is because how to rigorously verify data removal guarantee in non-linear models is an open problem and non-trivial to verify empirically, Recently, linear-GNNy are proposed to remove non-linearisies and only use a single-weight matrix in the neural architecture. For example, SGC Wu et al. (2019) proposes to compute the node representation by ( = ''H(). By linearizing the GNNs, these methods not only enjoy faster training speed but also allow us rigorously theoretically and empirically
3

---

Under review as a conference paper at ICLR 2023
verify whether the information has been perfectly unleamed. Although lack of non-linearity, recent studies Wei et al. (2022); Wang & Zhang (2022) shows that AinerrGNNN are almost as expressive as its non-linear counterparts (details in Appendix F). Motivated by the advantages of we will first illustrating our idea on linear-GNNs in Section 4.1 and then introduce its non-linearity extension in Section 4.4. We will rigorously test whether the information is perfectly unlearned on Linear-GNNN and also demonstrate the possibility to use GRAPHEDITOR with non-linear GNNs.
Challenges in graph unlearning. Graph representation unlearning is challenging for the following three main reasons: ① High computation cost. Existing unlearning methods suffer from high computation cost. To see this, let us suppose we are training logistic regression via gradient descent, ie.. f(w) = - 9t log #4 + (1 y4) log(1 - p4), where μa = a w x,) is the prediction and Yi E [0, is the ground truth label. If unlearn by re-training from scratch, it takes O(dN F) time complexity to unlearn a single data point, where N is the number of data points, d is feature dimension, and E is the number of epochs during training, which is infeasible if the deletion request needs to be completed immediately. Although approximate unlearning methods can alleviate the computation burden to some extent, the computation cost is still linear with respect to the number nodes N. For example, INFLUENCE and FISHER require O(Nd) to compute gradient f((w) = X (H - y) and ((Nef)) to compute Hessian V f()( = X diag(ı (1- the large-scale datasets. 2 Non-triviality of extension to graph domain. Most existing unlearning
(1-1)) p))X, which could scale poorly on
methods only support data deletion, however, graph representation unlearning also requires updating the effect of the deleted nodes its neighborhood due to the convolution operation on graph.
For example, as shown in Figure 1, let us suppose our goal is unlearn the effect of node 11 on pre-trained 1-layer GCN. After removing node U1, the node representation of node (V2, U3, ) are also affected due to the change of edge weight aij and the deletion of node V1's 's feature. There- fore, a proper graph representation un- learning algorithm not only need to remove the effect of node i1 (which can be achieved by using INFLUENCE and FISHER), but also require to be capable of updating the effect of node (V2, U3, va} on model parameters (which is not supported by most unlearning methods). ② Lack of data removal guarantee. Although approximate unlearning methods are more efficient than retraining from scratch, the removal of all information related to the deleted data is not guaranteed, in which we validate this by "deleted data replay test" in Section 5. Intuitively, the above observation makes sense because the output of approximate unlearning is not necessarily equivalent to the result of exact unlearning. Furthermore, most approximate unlcarning algorithms seek to prove the approximately unlearned model is close to exactly retrained model Wu et al. (2020a); Aldaghri et al. (2021); Izzo et al. (2021). However, it has been pointed out by Thudi et al. (2021); Guo et al. (2020) that we cannot infer "whether the data have been deleted" solely from "the closeness of the approximately unlearned and exactly retrained model in the parameter space". In fact, Thudi et al. (2021) shows that one can even unlearn the data without modifying the parameters. Therefore, it is important to show from the algorithm itself that the sensitive information can be perfectly removed, which is lacking in most approximate unlearning methods due to the approximation process. To overcome the above challenges, we propose GRAPHEDITOR that enjoys a low computation cost with data removal guarantees.
Deleted mode
Σ SENUL
Affected modes
v /degfes) deg
Not aflected modes
Delete mode
Before unlearning
After unlearning
Figure 1:
An illustration of how output of a L-Layer GCN is affected after deleting the node f1-
4 GRAPHEDITOR
In this section, we first introduce the graph representation learning and unlearning under the notation of linear-GNN in Section 4.1 and Section 4.2, respectively. Then, we introduce the subgraph sampling-stratee strrtegy to lower the computation cost in Section 4.3 and introduce application of using GRAPHEDITOR with multi-layer GNNs in Section 4.4. We consider both the node unlearning (discussed in main text) and edge unlearning (deferred to appendix). We summarize the full unlearning process of GRAPHEDITOR in Algorithm 1, which consists of three main functions: find WQ. remove data(), and add data().
4

---

Under review as a conference paper at ICLR 2023
Algorithm 1 GRAPHEDDTTR (Numpy-like pseudo-code)
Input: X as the output of GNNs, Y as the label matrix (Refare un unlearn' ng) Compote the a closed-form solution >>> S, W = find_M(X, Y) def #ind_M (X, Y, reg-0):
XtX X.T8X reganumpy. eye shape [0]), , numpy, www.lllilllliii.. (XtX), W Sex.
returt S, W
(GraphEditor) step 1: Delete information
>>> S, W remove data (X U Vipal, (V Vopal, S, W) def remove_data (X, Y, 8, W):
I numpy eye sbspe
A - sex.I, B muumpy.1izag..ue. returr (GraphEditor) Step 2: Update information. X computed on updated graph. >>> S, W add data (X (Vosal (opdl,, S, W) def add_data (x, Y, 8, W):
x)5ex. C x x0n, D x2s
ABBaD,
ABB3C
I numpy. (x.spepe A T, B - numpy. hompp..lnalg.hii. (I xesex. ,), C -- Y X0N, D. -28
returr S ABBaD, W + ABB3C
(Opticral) Fine-ture W using cross-entzopy loss
4.1 GRAPH REPRESENTATIO LEARNING ON LINEAR-GNN
Instead of training ordinary GNNs by optimizing the cross-entropy loss, we propose to first formulate the ordinary GNN training as a linear GNN training with Ridge regression as the objective, which can be efficiently solved by the closed-form solution. More specifically, we first solve the following Ridge regression problem CRidge( (W; (R; X, Y) = XW - I + X/Wl I|2. where Y E NNxd, is the zero-one label matrix and X E R RNxxa is the node representation matrix for linear-GNN (e.g.. for SGC we have X (²H(")) The closed-form solution for the above objective function is W, arg minw CRidge (W; X, Y) correlation matrix. After training, we cache both S. E xd and W. gd for efficient unlearning. Please refer to find_W () for details. To boost model performance, we can take the closed-form solution as initialization and fine-tune using cross-entropy loss with small number of iterations. The time complexity of computing an exact unlearning solution with closed-fone solution is ONN,, + NN,,d, + de, dyy) which makes retraining on large-scale dataset computationally prohibitive due to linear dependency with respect to the graph size N. In the next section, we show that GRAPHEDITOR achieves efficient graph unlearning with computation cost independent of graph size, which makes it suitable for unlearning on large graphs.
S.X Y, where S. = (X X AI)- is the inversed
4.2 GRAPH REPRESENTATION UNLEARNING ON LINEAR LINEAR-GNN
Let us suppose node v; is to be deleted. In node unlcarning, we not only need to unlearn node U, features but also need to unlearn its connection with other nodes. Formally, let goode modde gnodey denote the graph with node i; and all its associated edges are removed, where V = V {1;} and goode 3 {(,, vy) My (N())) The model after node unlearning is expected to produce the Ey
same performance the model trained Gr The key idea of GRAPHEDITOR is to leverage the obtained closed-for ffomm solution to first efficiently "remove" the effect of the deleted nodes on weight parameters by remove data (), then "update" the effect of the neighboring nodes of the deleted nodes on weight parameters by add_data () Before delving into the details of algorithm, let us first take a closer look at the key factors that affect the weight parameters after node deletion.
Lemma 1 (Key factors that affect weight parameters). The optimal weight parameters W after removing node v; is affected by two factors: D "node representation removal" caused by removing node set V.m {wy) ); ② "node representation update" " due to the inner dependency between nodes in the graph, where the affected node set are all nodes that has shortest path distance (SPD) smaller than 2L to nodes in V.n. i.e., Vupd = {uş SSDD(v,, Uz)= < 2L, Vuj V, Yo; V.m).
The above lemma shows that node-set V. and Vupd are the key factors that affect the weight parameters. Therefore, we propose GRAPHEDITOR to first remove the effect of all node in V.m U Vood on the optimal weight parameters W., ., then update the effect of Vapa to derive the optimal weight W More specifically, our first step is to remove the effect of Vm U Vapd by remove data (). Let Xm X(V. U Vapal, Ym Y(v. U Vupa] denote the subset of matrix X, Y with row
5

---

Under review as a conference paper at ICLR 2023
indexed by V.n U Vapd. Then, given the initial solution S. and W., we first update the inversed correlation matrix as S = =. +.X I- S.X ! and update the optimal solution by Wm = W. -S - mm (Ym Xm W.). Then, our next step is to update the effect of Vupu on the weight parameters by add_data (). To achieve this, we first compute the updated node representation X on the graph without the deleted nodes. Let Xupd = Vapal, Y upd = [Ppaal denote the subset of matrix X, Y with row indexed by Vapa- Then, we update the inversed correlation
matrix by Spp = Sm Sm X (ppl + XnpdS X
T upd -- "SppsS/m and update the optimal solution by
upd
W Wapd = W m + Sm X [I + X Xmp updl 1-1(Y upd Xupa W.) Notice that GRAPHEDITOR'S output is equivalent to the optimal solution W = arg minw Cridee (W; X, Y). Besides, since are using the closed-form solution, we do not have to worry about the information of the deleted nodes in Vm might be potentially remained in the weight parameters. The time complexity for graph unlcarning is (M + Mc + M dy,y), where M = V U Vupal- According to time complexity, we know GRAPHEDITOR enjoys lower computation cost than retraining from scratch if M < dg. When M is large, we could split the removed nodes into multiple small shards and unlearn them one after another, which alleviates the cubic computation dependency on M. Since we are using the closed-fon form solution, the results after unlearning nodes are identical regardless of how many shards we split to unlearn. Besides, since efficient matrix inverse algorithms (e.g.. BLAS and LAPACK) have been implemented in Numpy, the practical computation time of GRAPHEDITOR is significantly smaller than re- training or other unlearning methods according to our observations. Details on the correctiveness of GRAPHEDITOR and the time complexity please refer to Appendix C.
Remark 1 (Node/Edge addition). The process of nodeledge addition is identical to nodeledge deletion. For example, we can add nodes by first unlearn the set of all "affected nodes" using the remove data(), then perform information updote on the "affected nodes" and the "added nodes" use the add data (). Here, the "affected nodes" " are nodes that have SPD smaller than 2I, to the "added nodes", which is similar to the node deletion operation. The same applies to edge addition.
4.3 SUBGRAPH SAMPLING FOR BETTER SCALABILITY
Recall from Lemma that the number of nodes in Vapd grows twice exponentially with respect to the Sieea-GGN depth, i.e., by letting D as the maximum node degree we have MYpull S [mmll x D When the linear GNN is deep, GRAPHEDITOR becomes computational prohibitive even when the deleted node set Vm is small, since GRAPHEDITOR'' 's overall computation cost is cubic with respect to |Vupa U V. To overcome the aforementioned issue, we propose to decouple the receptive field of each node with the GNN depth by extracting the rooted-subgraph for each node in the graph using shaDow-subee -ubboww-uubgaph sampler Zeng et al. (2021), and apply the linear GNN compute the feature representation of the root node on the extracted subgraph. In practice, we can either use the K K-hop sampling to uniformly sampling the K-hop neighbors of root node or we can sample a fixed number of nodes according to the PPR score with respect to the root node.
Lemma 2 (Affected nodes after sampling). Let us denote V as the set of nodes returned by shalow- subgraph sampler for root node vj. If using shaDow-suby suboowssubgrahh sampler, the affected node set of "node representation update" in Lemma are reduced to Vug {tş v, E 1,9, Voj E V,, Vu; E Vmm)
As shown in Lemma 2, we can reduce the size of update node set D which is independent of GNN depth. In practice, we find K- K-hop sampling works well on all datasets. When using K K-hhop sampling, the update node set size is reduced to updl
/ S [Vmml x D and we only need to update the representation of a node if its K- K-hop rooted subgraph contains the deleted nodes.
4.4 USING GRAPHEDITOR WITH NON-LINEAR MULTI-LAYER GNNS
One of the biggest concern readers might have is the linear-GNN requirement.' Extending the existing unlearning methods to non-lineat models requires first pre-training multi-layer GNNs as a feature extractor the public datasets (assume nodes in the public set will never need to be unlearned in the future), then we use the pre-trained multi-layer GNNs to extract the node representation for
Please notice that the linearity is not only required by GRAPHEDITOR but also required by most approximate unlearning methods (e.g., Guo et al. (2020); Golatkar et al. (2020); Wu et al. (2020a): Golatkar et al. (2021)) to theoretically show the data removal guarantee. Unless re-training from scratch, how to rigorously show data
removal guarantee in non-linear models is still an open problem and is non-trivial verify empirically.

---

Under review as a conference paper at ICLR 2023
linear classifier'. During unlearning, we only unlearn the linear classifier without updating the feature extractor because it does not carry any information on the deleted data. Formally, let us define V Publiic V privane as the nodes in the public and private dataset, V. n Vushtic 0 and V. C V privatee define fw o Go as a multi-layer GNN model with fee as the final linear classifier and go as all previous layers. Let us suppose
could pre-train go on the public dataset nodes Viublic. then we use the go as a feature extractor to extract the node representation X on private graph node private. By doing so, we can apply find_W) on X learn the linear classifier for by GRAPHEDITOR. To unlearn node Vim. we can first apply lemove-datale with ( U V upal to unlearn the information of Vim U U.V upd on fw, then compute the node representation X on the update graph using ge, and finally apply add data() with [[V to update the information of 2 on f Please notice that using GRAPHEDITOR with non-linear GNNs is similar to using GRAPHEDITOR with Kinear-GNNG except the original X, X are computed using linear-GNNs but here we use non-linear GNNs instead.
EXPERIMENTS
Datasets and baselines. We select OGB-Arxiv, OGB-Products, Flickr, and Reddit datasets for node unlearning evaluation, and OGB-Collab dataset for edge unlearning evaluation. We compare with approximate unlearning methods INFLUENCE and FISHER on linear-GNNs (by extending their application from the non-structured data to the structured data) and exact unlearning method ASER on both linear and non-linear GNNs. Besides, we compare with retraining GCN Kipf & Welling (2017), GraphSAGE Hamilton et al. (2017), GAT Veličković et al. (2017) from scratch.
GrAPHÉR ASER
Representation computation. For node unlearning, the node representation is extracted from the sampled rooted subgraph of each node and label reuse trick Wang al. (2021b) is used for linear-GNNs node classification. For edge unlearning, we first extract the subgraph of the two nodes connected by that edge, then the edge representation is extracted from the intersection of the two subgraphs, common neighbor score Liben-Nowell & Kleinberg (2007) is used for AinerrGNNN,
Overview on experiments. We measure the success of an unlearning method by two criteria: whether the information is unlearned and whether the unlearming algorithm could deteriorate the model performance. Please notice that the second criteria as important as the first criteria. For example, in an extreme case, one can just unlearn by randomly initializing the model but it might significantly hurt the model performance. To validate the above two criteria, we conduct the following experiments: In section 5.1, we conduct deleted data replay test on linear-GNN to test whether an unlearning method could perfectly unlearn the features- correlation from the deleted nodes, and whether the unlearning method hurt the model's prediction accuracy. In section 5.2, we compare the similarity between the unlearned model to the re-training from the scratch model on linear-GNN. The two models are expected to be similar prevent information leakage on the deleted nodes. In section 5.3, we evaluate the efficiency and effectiveness of using GR APA with non-linear GNNs. We compare the accuracy with re-training non-linear GNNs from scratch. Intuitively, strong unlearning method should unlearn in a short time and produce a similar model performance to re- re-training. Furthermore, we conduct edge unlearning test in Appendix A. ablation study the effect of subgraph sampling size on GRAPHEDITOR for node unlearning in Appendix A.2 and for edge unlearning Appendix A.3, conduct node addition test in Appendix A.4, compare the prediction confidence on the unlearned node in Appendix A.5, compare the running time in Appendix A.6, and compare linear-GNN with shallow sampler and different multi-layer GNNs in Appendix A.7. Details on datasets, baselines, experiment details are summarized in Appendix B.
5.1 DELETED DATA REPLAY TEST
In this experiment, randomly select 100 nodes from the training set as the deleted nodes and modify their label categories to an extra-label category. An extra binary feature is injected to the node features help linear-GNNs memorize the correlation between deleted nodes to the extra-label category. To simulate real-world deletion unlearning requests that come one after another, we first uniformly split all deleted nodes into S {10, 50, 100) shards, then we randomly select one shard without replacement to unlearn at each unlearning iteration and repeat this S times. We measure the success of unlearning by checking whether the information on the deleted nodes is unlearned and
"iiiilar assumption are made in Golatkar et al. (2021) for convolutional neural network unlcarning.
7

---

Under review as a conference paper at ICLR 2023
Table I: Comparison on the accuracy (before parentheses), number of deleted nodes that are predicted as the extra-label category before and after unlearning (inside parentheses), and wall-clock time.
OGB-Arxiv
OGB-Products
Method
S=10
S=50
S=100
S=10
S=50
S=100
Before
71.77% (70)
71.77% (70)
71.77% (70)
77.63% (83)
77 77.63% (83)
77.63% (83)
GRAPHEDITOR
After
71.78% (0)
71.78% (0)
71.78% (0)
77.63% (0)
77.63% (0)
77.63% (0)
Time
10.8
11.9
46.6
76.9
1
Before
73.87% (88)
73.87% (88)
73.87% (88)
79.26% (71)
79.26% (71)
79.26% (71)
GRAPHEDITOR
Afer
73.86% (0)
73.86% (0)
73.86% (0)
79.26% (0)
79.25% (0)
79.25% (0)
+ Finc-tune
Time
1
14.8
5
85.0
1
Belore
69.91% (28)
69.91% (25)
09.91% (28)
63.27% (32)
03.27% (32)
63.27% (32)
GRAPHERASER
After
69.90% (0)
69.90% (0)
69.8 89% (0)
63.27% (0)
03.28% (0)
63.25% (0)
Time
615.9
1888 s
2, 237.8
15. 191.4
39.61
46, 491.4
Before
72.99%
(93)
72.99% (93)
72. .9% (93)
78.05% (63)
78. 78.05% (63)
78.05% (63)
INFLUENCE
After
72.89% (53)
72.89% (53)
72.89% (53)
78.05% (19)
78.03% (19)
78.04% (19)
Time
62.1
284.7
554.8 S
151.7 S
614.2 s
1. 185877
Before
72.94% (94)
T2.94% (94)
72.94% (94)
78.05% (63)
78.05% (63)
78.05% (63)
FISHER
Afler 72.73% (56)
72.70% (55)
72.69% (54)
77.87% (57)
77.86% (57)
77.76% (54)
Time
77.1s
364.4s
7
185.3
791.8
1, 1,8.8.6
whether the unlearning algorithm could deteriorate the model performance: ! To measure the first criteria, we compare the number of the deleted nodes that is computed as the extra-label category. The prediction of deleted nodes is computed on the graph structure before node deletion, therefore namely "deleted data replay test". Intuitively, a successful unlearning should never predict a node as the extra-label category after the unlearning process. As shown in Table I, exact unlearning methods GRAPHEDITOR and GRAPUERASER can unlearn all the information because none the deleted nodes predicted the extra-label category. However, this is not the case for approximate unlearning methods INFLUENCE and FISHER. ② To measure the second criteria, we report the "accuracy" before and after unlearning. A strong unlearning method should not hurt the model performance, therefore they should produce high accuracy both before and after unlearning." From Table 1, we know that GRAPHERASER, INFIUENCE, and FISHER need sacrifice their performance achieve efficient unlearming, therefore they have a lower performance both before and after unlearning. GRAPHERASER has lower performance because of data heterogeneity (data distribution on each shard is different from each other) and lack of training data for each shard model (caused by graph partition). INFLUENCE and FISHER have lower performance because a large regularization term is required to stabilize the Hessian inverse computation and also due to random noises. 3 Moreover, we also compare the running time in Table 1. As the number of shards S increeses, the times required by ARAPPHIN GRAPHEDITOR increases less than baselines. This is because increasing S could also decreases the number of nodes to unlearn at each iteration and the time complexity of GRAPHEDITOR is independent of the dataset size (refer to in Section 4.2). Please notice that this is not the case for baselines because their complexity is always proportional to the dataset size (refer to part three of Section 3). Therefore, GRAPHEDITOR is more efficient than other baseline methods.
5.2 COMPARISON TO RETRAINED MODEL
To assess the similarity between the unlearned model and the retrained model, a natural way is to measure the distance between the final activations obtained by the unlearned W and the retrained W" models on the deleted nodes and testing set nodes. More specifically, for B E { (em:: Visa we compare the distance of final activations E [|softmax(xx W") softmax(x, W The deleted nodes are randomly selected 100 samples from the training set and are unlearned through 10 sequential forgetting requests, each request of size 10. Intuitively, a powerful unlearning algorithm should generate similar final activations to the retrained model on nodes from both the deleted nodes and testing set nodes. Besides, we measure the Euclidean distance between the parameters returned by the unlearning algorithms and the parameters obtained via retraining from scratch. For linear GNN, small Euclidean distance in the parameter space means the model is likely to have the same predictions. We have the following observations according to Figure 2: ① We observe that GR PRHEDDTTO''s 's (both with and without fine-tune) final activation difference and parameter difference is consistently low compared to baselines during the 10 unlearning requests. However, this
We are not comparing the difference between the accuracy before and after unlearning hecause it is not necessarily related to whether the unlcarning success hut mainly related the number of data to unleam.
8

---

Under review as a conference paper at ICLR 2023
Ualearzing rounds
Unllersiing rounds
Unbearunng rounds
Urausadoc Alselum
kanrd
Uebressing touands
Uodearsiny coundss
Figure 2: Comparison on the difference of final activation prediction on deleted nodes (Ist column) and testing nodes (2nd column) and difference of weight parameters (3rd column).
is not the case for approximate unlearning methods INFLUENCE and FISHER. ② We observe that the final activation differences of approximate unlearning methods on the deleted nodes are consistently larger than the values on the test nodes. Therefore, a malicious third party could potentially identify the deleted nodes from other nodes by comparing its final activation difference.
5.3 GRAPHEDITOR WITH NON-LINEAR GNN
In this section, we demonstrate the potential extension of using GRAPHEDITOR with non-linear GNNs. This experiment is conducted under the assumption that a subset of training samples are never forgotten (i.e.. public dataset), which can be used to pretrain neural network as feature extractor, and only unlearn the final linear classifier. To test under this scenario, we randomly split the training set into 90% and 10% for public dataset and private dataset. For GRAPHEDITOR, the feature extractor is pre-trained on the 90% training set nodes, then it is used to extract node representation for all nodes. The extracted representation will be used to train the linear classifier. GRAPHEDITOR is only applied to the linear classifier since the pre-trained feature extractor do not have any information about the deleted nodes. For both re- re-training and GRAPHERASER, the multi-layer GNNs are trained on all nodes. We select 100 nodes from the 10% private training set with the largest node degree to unlearn. We use 3-layer GAT, GCN, and SAGE with hidden dimension 256, attention head size 8 the backbone model. We are using the official implementation of GRAPHERASER (detailed setup in Appendix B.3). From Table 2, we observe that: ① GRAPHEDITOR could attain similar accuracy as re-training from scratch but with shorter time, 2 GRAPHEDITOR has slightly lower precision than re- ve-training because it has less data to training the feature extractor, 3 the performance of GRAPHERASER
relatively lower than GRAPHEDITOR and re- re-training due to lack of training data on each shard model, data heterogeneity caused by graph partitioning, and is prone to over-file wer-fitting during shard model training phase.
Table 2: Comparison on the accuracy after unlearning and running time on non-linear GNNs.
Retrain
GRAPHEDITOR
GRAPHERASER
SAGE
72.58 1 0.17
211 sec)
71.13 0.19 (19 sec)
56.32 1 0.23 [224 sec)
OGB-Arxiv
GAT
72.23 0.18
(1. 425 sec)
71.01 - 0.19 (21 sec)
57.16 - 0.56 (301 sec)
GCN
71.49
1: 0.27 (1, 080 sec)
70.89 1 0.30 (18 see)
55.90 1 0.51 (277 sec)
SAGE
80.67
0.37
(3, 156 szc)
79.00 (56 sec)
56.53 + 0.50 (11, 648 sce)
OGB-Products
GAT
81.42
0.31 (3, 235 sec)
79.41 0.37 (59 sec)
62.47 + 0.62 (15, 496 see)
GCN
7.41
(3,071
78.11 +.11 (55 sec)
56.41 + 0.49 (11, 298 scc)
SAGE
53.95
1 0.13 (311 sec)
52.87 1.15 (11
43.15 1 0.54 (194 sec)
Flickr
GAT
53.64
1 0.26 (328 see)
52.42 4 0.27 (13 sec)
43.14 1 0.54 (243 sec]
GCN
52.86 + 0.13 (305 soc)
52,50 - 0.16
(12 sec)
44.01 + 0.53 (190 sec)
SAGE
97.03 + 0.03
(3, 300 sec)
96.11 + 0.03 (60 sec)
88.91 - 0.03 (728 sec)
Reddit
GAT
97.10
+ 0.04 (3, 598 szc)
96.21 + 0.04
(61 soc)
87.78 + 0.04 (993 scc)
GCN
96.24 + 0.02
(3, 238 sec)
95.96
0.03
(60 sec)
87.54 0.03 (730 sec)
6 CONCLUSION
We study the problem of graph representation unlearning and propose an exact unlearning algorithm GRAPHEDITOO, which supports node/edge deletion, node/edge addition, and node feature update. GRAPHEDITOR requires neither retraining from scratch nor all data presented during unlearning, and enjoys guarantee on the removal of all the information associated with the deleted nodes/edges. Extensive experiments on real-world datasets indicate its effectiveness and efficiency.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Nasser Aldaghri, Hessam Mahdavifar, and Ahmad Beirami. Coded machine unlcarning. IEEE Access, 2021.
Rianne van den Berg, Thomas N Kipf, and Max Welling. Graph convolutional matrix completion. In International Conference Knowledge Discovery & Data Mining, 2017.
Christopher M Bishop et al. Neural networks for pattern recognition. Oxford university press, 1995.
Lucas Bourtoule, Varun Chandrasekaran, Christopher A Srnquuctte-Choo Hengrui Jia, Adelin Travers, Baiwu Zhang, David Lie, and Nicolas Papernot. Machine unlearning. In 202/ IEEE Symposium on Security and Privacy (SP), 2021.
Jonathan Brophy and Daniel Lowd. Machine unlearning for random forests. In International
Conference on Machine Learning, 2021.
Gert Cauwenberghs and Tomaso Poggio. Incremental and decremental support vector machine learning. Advances neural information processing systems, 2001.
Min Chen, Zhikun Zhang, Tianhao Wang, Michael Backes, Mathias Humbert, and Yang Zhang Graph unlearning. 2021.
Eli Chien, Chao Pan, and Olgica Milenkovic. Certified graph unlearning. arXiv preprint arXiv:2206.09 09200009944, 2022.
Weilin Cong, Morteza Ramezani, and Mehrdad Mahdavi. On provable benefits of depth in training graph convolutional networks. Advances in Neural Information Processing Systems, 2021.
Zhiyong Cui, Kristian Henrickson, Ruimin Ke, and Yinhai Wang. Traffic graph convolutional recurrent neural network: A deep learning framework for network-scale traffic learning and forecasting. IEEE Transactions on Intelligent Transportation Systems, 2019.
Shaopeng Fu, Fengxiang He, and Dacheng Tao. Knowledge removal in sampling- bayesian inference. arXiv preprini arXiv:2203. 12964, 2022.
Antonio Ginart, Melody Y Guan, Gregory Valiant, and James Zou. Making ai forget you: Data deletion in machine learning. ax0iv:1907.050/0 2019.
Aditya Golatkar, Alessandro Achille, and Stefano Soatto. Eternal sunshine of the spotless net: Selective forgetting deep networks. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, 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.
Chuan Guo, Tom Goldstein, Awni Hannun, and Laurens Van Der Maaten. Certified data removal from machine learning models. In International Conference on Machine Learning, 2020.
William L. Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Advances in Neural Information Processing Systems, 2017.
Zachary Izzo, Mary Anne Smart, Kamalika Chaudhuri, and James Zou. Approximate data deletion from machine learning models. In International Conference on Artificial intelligence and Statistics, 2021.
Mohammad Emtiyaz Khan and Siddharth Swaroop. snowledge-adaptatiee priors. arXiv preprint arXiv:2106.08769, 2021.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations, 2017.
Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper insights into graph convolutional networks for semi-supervised learning. In Thirfy-Second AAAI conference artificial intelligence, 2018.
10

---

Under review as a conference paper at ICLR 2023
David Liben-Nowell and Jon Kleinberg. The link link-prediction problem for social networks. Journal of the American society for information science and technology. 5807::009-1031, 2007.
Seth Neel, Aaron Roth, and Saeed Sharifi-Malvaeeddi. Descent-to-delcte: Gradient-based methods for machine unlearning. arXiv preprint arXiv:2007.029: 2020.
Quoc Phong Nguyen, Ryutaro Oikawa, Dinil Mon Divakaran, Mun Choon Chan, and Bryan Kian Hsiang Low. Markov chain monte carlo-based machine unlearning: Unlearning what needs to be forgotten. arXiv preprint arXiv:2202. 13585, 2022.
Kaare Brandt Petersen, Michael Syskind Pedersen, et al. The matrix cookbook. Technical University of Denmark, 7(15):510, 2008.
Afshin Rahimi, Trevor Cohn, and Timothy Baldwin. Semi-supervised user geolocation via graph convolutional networks, In Proceedings of the Association for Computational Linguistics, 2018.
Morteza Ramezani, Weilin Cong, Mehrdad Mahdavi, Mahmut T Kandemir, and Anand Sivasubrama- niam. Learn locally, correct globally: A distributed algorithm for training graph neural networks. arXiv preprint arXiv:2111.002000 08.0202, 2021.
Ayush Sekhari, Jayadev Acharya, Gautam Kamath, and Ananda Theertha Suresh. Remember what you want forget: Algorithms for machine unlearning. 2021.
Jack Sherman and Winifred Morrison. Adjustment of inverse matrix corresponding to change in one element of given matrix. The Annals of Mathematical Statistics, 1950.
Anvith Thudi, Hengrui Jia, Ilia Shumailov, and Nicolas Papernot. On the necessity of auditable algorithmic definitions for machine unlearning. arXiv preprint 1rXiv:2110.1189) 2021.
Enayat Ullah, Tung Mai, Anup Rao, Ryan Rossi, and Raman Arora. Machine unlearning via
algorithmic stability. 2021.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. arXiv preprint arXiv:1710.1090. 2017.
Hongwei Wang, Fuzheng Zhang, Mengdi Zhang, Jure Leskovec, Miao Zhao, Wenjie Li, and Zhongyuan Wang. Knowledge-aware graph neural networks with label smoothness regular- ization for recommender systems. In International Conference on Knowledge Discovery & Data Mining, 2019a.
Junxiao Wang, Song Guo, Xin Xie, and Heng Qi. Federated unlearning via class-discriminative pruning. arXiv preprint arXiv:2110.11794 2021a.
Xiang Wang, Xiangnan He, Yixin Cao, Meng Liu, and Tat-Seng Chua. KGAT: knowledge graph attention network for recommendation. In International Conference Knowledge Discovery & Data Mining, 2019b.
Xiyuan Wang and Muhan Zhang. How powerful are spectral graph neural networks. arXiv preprint arXiv:220S.1 11172 2022.
Yangkun Wang, Jiarui Jin, Weinan Zhang, Yong Yu, Zheng Zhang, and David Wipf. Bag of tricks for node classification with graph neural networks. arXiv preprint 1333v:2103.13355 2021b.
Rongzhe Wei, Haoteng Yin, Junteng Jia, Austin R Benson, and Pan Li. Understanding non- con-linearity in graph neural networks from the bayesian-inferent perspective. arXiv preprint arXiv:2207.11311 2022.
Wikipedia contributors. Right to be forgotten - Wikipeddia, the free encyclopedia, 2021.
Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinherger. Simplify- ing graph convolutional networks. In International conference on machine learning, 2019.
Ga WU, Masoud Hashemi, and Christopher Srinivasa. Puma: Performance unchanged model augmentation for training data removal. arXiv preprinl arXiv:2203.0008: 2022.
11

---

Under review as a conference paper at ICLR 2023
Yinjun Wu, Edgar Dobriban, and Susan Davidson. Deltagrad: Rapid retraining of machine learning models. In International Conference on Machine Learning, 2020a.
Yinjun Wu, Val Tannen, and Susan B Davidson. Priu: A provenance-based approach for incrementally updating regression models. In Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data, 2020b.
Rex Ying, Ruining He, Kaifeng Chen, Pong Eksombatchai, William L. Hamilton, and Jure Leskovec. Graph convolutional neural networks for web-scale recommender systems. International Conference Knowledge Discovery & Data Mining, 2018.
Hanqing Zeng, Muhan Zhang, Yinglong Xia, Ajitesh Srivastava, Andrey Malevich, Rajgopal Kannan, Viktor Prasanna, Long Jin, and Ren Chen. Decoupling the depth and scope of graph neural networks. In A. Beygelzimer, Y. Dauphin, P. Liang, and J. Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, 2021. URL https: / /ttp///ppeeeeweeeeeeeeee net forum? 1d=dOMttWYONN..
12

---

Under review as a conference paper at ICLR 2023
GRAPHEDITOR: AN EFFICIENT GRAPH REPRESENTATION LEARNING AND UNLEARNING APPROACH
Introduction
Related works
3
Preliminaries graph representation unlearning
4
GRAPHEDITOR
4.1
Graph representation learning on linear-GNN
4.2
Graph representation unlearning on linear-GNN
4.3
Subgraph sampling for better scalability
4.4
Using GRAPHEDITOR with non-linear multi layer GNNs
5
Experiments
5.1
Deleted data replay test
5.2
Comparison retrained model
5.3
GRAPHEDITOR with non-linear GNN
Conclusion
More experiment results
15
A.1
Edge unlearning
15
A.2
Effectiveness of GRAPHEDITOR for node unlearning
16
A.3
Effectiveness for edge unlearning.
17
A.4
Node addition test
17
A.5 Comparison the confidence of delete nodes
18
A.6 Computation cost of each phase.
18
A.7
Comparison linear-GNN with shallow sampler with deep multi-layer GNNs
19
B
Experiment setup
19
B.1
Hardware specification and environment
19
B.2
Dataset
19
B.3 Details on baseline methods
19
B.4
Baseline hyper- parametrss setup
20
B.5 Details for node deletion replay test
20
C GRAPHEDITOR: details, correctiveness, and time complexity
C.1 Before unlearning: closed-form solution by find_W (x,
21
C.2 Graph unlearning: delete information by remove data (X, Y, S, W)
C.3 Graph unlearning: update information by add data (X, 5, W)
22
13

---

Under review as a conference paper at ICLR 2023
C,4 Connection second-order unlearning.
23
On the affected nodes size with/without subgraph sampling
24
D.1 Proof of Lemma
24
D.2 Proof of Lemma
24
Dependency issue of applying existing unlearning approaches
24
F
Linear-GNN is almost as powerful non-linear counterparts
26
E1 From Bayesian inference perspective..
27
F2 From spectral neural network perspective
28
14

---

Under review as a conference paper at ICLR 2023
Organization. In Section A, we provide additional experiment results on both node/edge unlearning and comparison of linear GNNs to ordinary multi-layer non-linear GNNs. More specifically, we conduct edge unlearning test in Appendix A. ablation study the effect of subgraph sampling size on GR AHHTTOOR for node unlearning in Appendix A.2 and for edge unlearning in Appendix A.3, conduct node addition test in Appendix A.4, compare the prediction confidence on the unlearned node in Appendix A.5, compare the running time in Appendix A.6, and compare linear-GNN with shallow sampler and different multi-layer GNNs in Appendix A.7. In Section B, we provide details on experiment setup. In Section C, we provide detailed analysis on the computation complexity and correctness of GRAPHEDITOR. In Section D. we provided proof for Lemma and Lemma 2. In Section E we highlight the dependency issue of applying existing unlearning approach to graph structured data. In Section F, we summarize recent theoretical analysis showing that linear-GNNy GNN could be almost expressive as non-linear GNNs. [Code] to reproduce the experiment results can be find from the anonymous repository.
A MORE EXPERIMENT RESULTS
A.1 EDGE UNLEARNING
In this section, we introduce our edge unlearning problem formulation and demonstrate our results. Suppose edge (vi, nyy) is to be deleted, our goal is to unlearn the connectivity. Let galee (V, Ealee) denotes the graph with edge (vi, Uý) removed, where gulge = \ {(vs, vj)} The model after unlearn- gedge
ing is expected to produce the same performance as the model trained on Ph As shown in Table 3, we compare the model performance (measured by Hits 50 for edge unlearning), wall-clock time (measured by seconds), and the number of deleted nodes that are predicted as the extra-label category before and after unlearning (reported in the parenthesis), and have the following observations: ! We can observe that different from node-level tasks, the performance of GR GRAHHDTO to baselines are very close. This potentially due to the nature of OGB-Collab dataset and the feature extraction strategy used linear GNN. In fact, we found that the feature extracting strategy plays more important role in the OGB-Collab dataset, please refer to the next section for more detailed discus- sions and ablation study results in Table 5. ② Besides, methods GRAPHEDITOR and GRAPHERASER can always unlearn all the information related to the deleted nodes, however, this is not the case for approximate unlearning methods INFLUENCE and FISHER. 3 GRAPHEDITOR is significantly more efficient than other baseline methods, mainly due to its unlearning complexity is independent of the dataset size, which requires less wall-clock time throughout the unlearning process.
observe that the exact unlearning
Table 3: Comparison on the accuracy (in front of the parentheses), the number of the deleted nodes that are predicted the extra-label category before and after unlearning (inside the parentheses). and wall-clock time.
Method
S=10
S=50
S=100
Before
63.45% (97)
63.45% (97)
63.45% (97)
GRAPHEDITOR
After
62.69% (0)
57. 57.42% (0)
56.34% (0)
Time
6.9
13.0
19.4
OGB-Collabh (Hits@
Before
64.00% (59)
64.00% (59)
64.00% (59)
GRAPHEDITOR
After
63.76% (0)
63.67% (0)
63.39% (0)
+ Fine-tune
Time
8.1
14.2
20.5 s
Before
63.82% (21)
63.82% (21)
63.82% (21)
GRAPHERASER
After
63.82% (0)
63.82% (0)
63.82% (0)
Time
8, 3,990.7 s
21. 586.8 s
29, 891.41145 s
Before
63.76% (76)
63.76% (76)
63.76% (76)
INFLUENCE
After
63.57% (55)
63.19% (42)
63.54% (61)
Time
20.8
83.1
159.2
Before
64.33% (31)
64.33% (31)
64.33% (31)
FISHER
After
63.93% (1)
63.95% (1)
63.91% (1)
Time
27.1s
111.8 s
230.8 s
15

---

Under review as a conference paper at ICLR 2023
A.2 EFFECTIVENESS OF GRAPHEDITOR FOR NODE UNLEARNING
We study the effectiveness of GRAPHEDITOR by comparing it with ordinary GNNs (including GCN and GraphSAGE) and provide an ablation study on the effect of the number of layers per- hop on performance and efficiency. Besides, we also provide experimental results by applying GRAPHERASER onto ordinary GNNs by splitting the original graph into subgraphs and using mean-aggregation during inference, where the time is reported by the maximum time trained on a single subgraph. We repeat experiment times, each time 100 nodes are randomly selected as deleted nodes from the training set, for node unlearning we randomly split the deleted nodes into 10 sequential forgetting requests of equal size. The results are reported Table 4, where we denote full-neighbor subgraph as "Full", denote subgraph with K neighbors per hop "SG (K)", and denote model with fine-tuning as "+ FT We have the following observation from Table 4: ! adding neighbors per hop not necessarily results in better model performance on the linear GNN used in GRAPHEDITOR, which can be explained by the over-smoothing hypothesis in Cong et al. (2021) I): Li al. (2018). ② fine-tuning can bring around 3% of performance-boostnn datasets, which indicates the importance of finetuning. 3 linear GNN can achieve compatible results (even outperform) the ordinary multi-layer non-linear GNN with significantly less computation time, which motivates us to explore better feature engineering tricks for linear GNN as future direction. ④ GRAPHERASER suffers performance degradation issue due to the data heterogeneity and lack of training data on each subgraph, which is aligned with our observation on using GRAPHERASER with linear GNNs as reported in Table I. Interesting, we found that the performance degradation issue using ordinary GNN is more severe than the linear GNN and the results reported in their original paper Chen et al. (2021). This potentially due to ordinary non-linear GNNs requires more data for training than linear GNN because of its higher model complexity.
node classification
Table 4: Comparison the effect of subgraph sampling and fine-tuning of GRAPHEDITOR GNNNs Besides, we also compare with re-training multi-layer GNNs from scratch and using GRAPHERASER for multi-layer GNNs (marked with t).
Method
Accuracy (Belore)
Accuracy (After)
T Time
Full
69.78 = 0.02
69.78
3968,45
Full FT
74.04 1: 0.06
74.02 0.00
3971.6
SG (10)
71.49 + 0.02
71.42
6.6
SG (20)
71.99 +: 0.02
71.98 +.08
20.8
OGB-ArXiv
SG (50)
71.51 1: 0.03
71.52 0.002
126.7
SG (10) + FT
73.75 0.07
73,51
10.45
SG (20) FT
74.07 + 0.07
7.007
24.3
SG (50) FT
74.29 1 0.06
74.26 0.006
130.0
TCCN
0.27
71.67
961.45
+GraphSAGE
71.49 +: 0.27
71.41 + 0.30
0.30
686.6
(GCN + GRAPHERASER
66.52 1 0.31
66.51 1 0.32
137.8
+GraphSAGE + GRAPHERASER
65.96 1 0.26
65.96 0.31
107.6
SG (I0)
76.63 1. 0.02
76.63 0.02
47.6
SG (15)
77.06 1: 0.03
77.06 + 0.02
259.3
SG (20)
77.11 1: 0.02
77.12 1 0.00
610.8
OGB-Products
SG (10) FT
79.26 1 0.0T
79.25 0.007
54.2
SG (15) FT
79.32 1 0.06
79.32
265.5 5
SG (20) FT
79.51 1: 0.07
79.52 0.07
617.1
TGaphhAAG
78.70 1. 0.36
78.68 1.300
12539.5
-GraphSAINT
79.08 1: 0.24
79.07 1.225
7061.1
CChusterCNN
78.99 -:: 0.36
79.00 + 0.37
11459.8
GrEphSAGE GRAPHERASER
58.99 1 0.40
38.87 1.441
3707.2
+GraphSAINT GRAPHERASER
59.54 1: 0.41
39.39 0.39
2271.3
:ClusterGCN+ GRAPHENASHR
59.10 + 0.57
39.01 + 0.60
3351.7
*Here, we are using our implementation of GRAPHERASER by directly applying GCN, GraphSAGE, GraphSAINT, and ClusterGCN onto the graph partitioned by METIS and using mean-average pooling for aggregation. We do this to make sure only the unlearning method is different and other parts are consistent among different unlearning methods (e.g., neural architecture, pyper-parameterss. We believe our implementation general enough and has already captured the leading spirit of GRAPHERASER, i.c., split data into multiple shards and train a different model on each graph partition. METIS allows us to split the original graph into
multiple subgraphs while preserving the original graph structure as much as possible. We would like to point out that the experimental results using official implementations (Table 2) are consistent with our implementation 's results and meet our expectations.
16

---

Under review as a conference paper at ICLR 2023
A.3 EFFECTIVENESS FOR EDGE UNLEARNING.
We conduct similar experiment to Appendix A.2 for edge unlearning. We repeat experiment times, each time 100 edges are randomly selected deleted edges from the training set, for edge unlearning we unlearn through 100 forgetting requests The results are reported in Table 5, where we denote full-neighbor subgraph as "Full", denote subgraph with K neighbors per hop as "SG (K)", and denote model with fine-tuning as "+ FT". We have the following observation from Table 5. ① Addinhg neighbors per hop not necessarily results in a better model performance on the linear GNN used in GRAPHEDITOR, which can be explained by the over-smoothing hypothesis in Cong et al. (2021); I); Li et al. (2018). @ Fine-tuning can bring very less improvements to link prediction datasets, which is potential because node features are less important in the OGB-Collab dataset, details please refer to here. 3 Linear GNN can achieve compatible results (even outperform) the ordinary multi- non-linear GNN with significantly less computation time, which motivates explore better feature engineering tricks for linear GNN as a future direction.
Table 5: Comparison on the effect of subgraph sampling and tine-tuning with ordinary GNNs for edge unlearning.
Method
Hit 50 (Before)
50 (After)
Time
Full
63.98 0.02
03.36 0.02
9
Full + FT
64.68 + 0.06
64.68
0.02
92.1
(G()
63.45 + 0.02
63.30 = 0.02
19.7
OGB-Collab
SG (100)
63.12 + 0.03
63.22 + 0.02
2
SG (200)
63.15 + 0.02
63,25 + 0.02
4
SG (50) FT
63.63 0.07
63.62 0.07
20.3 s
SG (100) FT
65.52 0.06
64.45 0.06
28.9 s
SG (200) FT
64.60 0.07
64559 039:000 0.07
49.4
GCN
47.14 1.45
46.99 1.56
167.767.7
GraphSAGE
54.63 + 1.12
54.49 + 1.14
522, 571.2s
A.4 NODE ADDITION TEST
In this experiment, we first randomly select 100 nodes from the training set as the node set Vasd to add, then remove them from the graph, including all edges that are connected to Vuai- Similar to the "deleted node reply test", extra-label category and binary feature are added to all nodes, where edit the label of nodes in Vasi to this additional label category. and set the extra feature as "1" for all node in Vadd. and as "0" for all other nodes in V Vadd. Then, we pre-train our model on the modified dataset. We randomly split the 100 added nodes into S E {10, 50, 100) shards. At each node addition iteration, we randomly select one shard without replacement and ask the model to learn the information about the new nodes. To evaluate the effectiveness of node addition operation, we compare the number of nodes that are predicted as the (C+ + 1)-th category. Notice that "node addition test" can be thought of as a reverse operation of the "deleted data replay test" for node unlearning. As shown in Table 6, GRAPHEDITOR can efficiently learn the correlation between the extra node features and extra-label category.
Table 6: Comparison on the accuracy (in front of the parentheses), the number of the deleted nodes that are predicted as the extra-label category before and after node addition (inside the parentheses), and wall-clock time.
Method
S=10
S=50
S=100
Belore
71.8%% (0)
71.78% (0)
71.78% (0)
OGBI-Arávv
GRAPHÉDITOR
After
71.77% (70)
71.77% (70)
71.77% (70)
Time
11.7
11.9
12.1s
Before
73.86% (0)
73. 73.86% (0)
73.86% (0)
GRAPHEDITOR
After
73.87% (88)
73.87% (88)
73.87% (88)
Fine-tune
Time
15.1
1
15.4
Before
77.62% (0)
77. 77.6%% [0]
77. 77.62% (0)
OGB-Produets
GRAPHEDITOR
After
77.62% (83)
77.62% (86)
77. 77.62% (86)
Time
4
79.1
110.4 s
Betore
79.26%
(0)
79.20% (0)
79.26% (0)
GRAPHEDITOR
Aller
79.26% (71)
79.26% (71)
79.26% (71)
Fine-tune
Time
36.4s
87.1s
119.8
17

---

Under review as a conference paper at ICLR 2023
A.5 COMPARISON ON THE CONFIDENCE OF DELETE NODES
In this experiment, we measure the difference between the prediction probability of the target category obtained by the unlearned W and the retrained W models on the deleted nodes as Ev,ev.. [softmax(x,, x; W
[softmax (x W The deleted nodes are randomly selected 100 samples from the training set and are unlearned through 10 sequential forgetting requests, each request of size 10. Intuitively, if a model Iearned the node during training. it is expected to have higher confidence on the target category. powerful unlearning algorithm should generate similar prediction probability of the target category to the retrained model on nodes from both the deleted note-set. We repeat the experiment 5 times with different random seeds. We retrain INFLUENCE and FISHER with the same initialization and number of epochs to eliminate the performance difference caused by other factors. We observe that prediction probability of the target category of GRAPHEDITOR (both with and without fine-tune) is consistently low compared to baselines during the 10 unlearning requests. However, this is not the case for approximate unlcarning methods INFLUENCE and FISHER. Therefore, malicious third party could potentially identify the deleted nodes from other nodes by comparing its final activation difference.
OGB-Arxiv (Fme): Predict difference/ Rounds
ACB-Praducts (Pmn): Predict difference Rounds
0.012
Inftuence beaeece--eeed
0,030
cattsence-basedd
Prodiet difference
0.010
GraphEddtor
Fisher based
Predict difference
0.025
GraphEdrtor
Pisher based
0.008
GraphEdtto--nnetuce
0.020
Graph
0.000
6.005
6.020
0.002
0.005
0.200
0.000
Unlearning rounds
Unlearning rounds
Figure 3: Comparison on the difference of the prediction probability of the target category obtained by the unlearned n and the retrained W" models on deleted nodes
A.6 COMPUTATION COST OF EACH PHASE.
We report the wall-clock time of unlearning 10 nodes with a single unlearning request on in Table 7 on OGB-Arxiv and
We use 2-hop neighbor sampling with 15 neighbors for OGB-Arxiv and 10 neighbors for -Go-rrrdscts. In practice, the overall unlearning process of GRAPHEDI- TOR could be split into the data preparation time on CPU and the computation time on GPU, For example on OGB-Arxiv, GRAPHEDITOR takes around 1 190.2 + 0.325 seconds to learn model using the closed-form solution. The unlearning process takes around 1.21 + 0.092 + 0.0028 + 0.087 seconds, which is relatively small compared to re-training. The computation time on OGB-Arxiv is because the dimension of the augmented feature in OGB-Arxiv is larger
larger than and the computation cost is proportional to the feature dimension. Besides, we would like to point out that one of another biggest advantages of GraphEditor is that it does not require all data presented during unlearning, which is beneficial for the settings where not all the training data are available to retrain.
Table 7: The time of unlearning 10 nodes with single unlearning request using linear-GNN,
Compute X
wind_W)
Prepare delete
remove remove_data()
Prepare update
add_ add_data()
On CPU
On GPU
On CPU
On GPU
On CPU
On GPU
OGB-Arxiv
190.2s
0.325s
1.21s
0.092s
0.0028 0.0003
0.087s
OGB- -S--Prrducts
417.6s
0.028
7.03s
0.003s
0.002s
18

---

Under review as a conference paper at ICLR 2023
A.7 COMPARISON LINEAR- -NAN WITH SHALLOW SAMPLER WITH DEEP MULTI-LAYER GNNS
Reader might wondering whether shallow sampling could cause performance degradation. Before answering this question, we would like to point out that has been shown in existing works Zeng et al. (2021) that 2-hop shallow sampler usually achieves good performance when compared to the deeper GNN with larger receptive fields. Then, to answer this question, we compare the performance of the "2-hop sampler with linear-GNN" and "multi-layer GNNs" on more datasets in Table 8. We could observe that the performance of "2-hop linear GNN" very close to "multi-layer GNNs". Combining the results of the 2-hop linear GNN in Table 4 and Table 5, we believe using shallow depth is not significant limitation. Meanwhile, please notice that the computation cost GRAPHEDITOR is only related to the number of nodes in the sampled subgraph. Therefore, strategies to obtain a deeper receptive field subgraph but with fewer neighbors per node. However, please notice that this is not the focus of our unlearning paper.
could still use other sampling
Table 8: Comparison linear-GNV with shallow sampler with deep multi-layer GNNs.
Models
Number of layers
Flickr
Reddit
3-layers
51.59 + 0.17
95.32 + 0.03
GCN
5-layers
52.17 + 0.16
94.95 + 0.12
3 3-layers
50.70 = 0.32
out of memory
GAT
5 5-layers
51.64 = 0.33
out of memory
Linear- GNN
2-hop sampling
51.81 = 0.08
95.64 + 0.02
B EXPERIMENT SETUP
B.1 HARDWARE SPECIHICATION AND ENVIRONMENT
We conduct experiments on a single machine with Intel i9 CPU, Nvidia RTX 3090 GPU, and 64GB RAM memory. The code is written in Python 3.7 and we use PyTorch 1.4 on CUDA 10.1 for model training.
B.2 DATASET
We select OGB-Arxiv, NGB-Products, Flickr, and Reddit datasets for node unlearning evaluation, and OGB-Collab dataset for edge unlearning evaluation. The detailed dataset statistics are summarized in Table 9.
Table 9: Statistics of the datasets used in our experiments.
OGB-Arxiv
DGB-Produee
Flickr
Reddit
OGB-Collab
Nodes
169, 343
2, 449, 029
89, 250
232, 965
235, 868
Edges
1, 166, 243
61, 859, 140
809, 756
11, 606, 919
1, 285, 463
Task (Metric) Node (Accuracy)
Node (Accuracy) Node (Accuracy) Node (Accuracy)
Edge (Hits @ 50)
B.3 DETAILS ON BASELINE METHODS
In this paper, consider graph unlearning method GRAPHERASER Chen et al. (2021), general machine unlearning method INFLUENCE" Guo et al. (2020) and FISHER Golatkar et al. (2020) as baseline methods.
Details on GRAPHERASER, GRAPHERASER is an exact unlearning method. GRAPHERASER proposes to split the original graph into multiple shards (i.e., subgraphs) and train an independent model on each data shard. During inference, GRAPHERASER averages the prediction of each
19

---

Under review as a conference paper at ICLR 2023
shard model the final prediction. Upon receiving unlearning requests, GRAPHERASER only needs to re-train the specific shard model where the deleted data belongs to. For GRAPHERASER, we use the default official implementation for non-linear GNNs and we also provide implementation for linear-GNNs to achieve a fair comparison with other linear-GiN methods. For the official implementation, we follow their official implementation by using "balanced k-means graph partitioning" to split the original graph into 10 shards, using "importance score aggregate" for model inference aggregation, and using mini-batch size 512 for shard model training. Although the official implementation also provides "balanced label propagation" for graph partitioning, this graph partitioning method does not work well with large-scale graphs due to its high memory cost. For example, it takes 173GB for Arxiv dataset, which is infeasible on our machine. For our implementation, we split all nodes into 8 shards using graph partition algorithm METIS S and use mean average for model aggregation. Each shard model is trained with enough epochs and we return the epoch model with the highest validation score. We believe our implementation is general enough and has already captured the main spirit of GRAPHERASER a shard model on each shard. METIS allows us to split the original graph into multiple subgraphs while preserving the original graph structure as much as possible.
i.., split data into multiple shards and train
Details on INFLUENCE. INFLUENCE is approximate unlearning method. INFLUENCE proposes to unlearn by removing the influence of the deleted data on the model parameters. Formally, let Da C DD denote the deleted subset of training data, D, = 'D \ Da denote the remaining data, C(w) is the objective function, and w is the model parameters before unlearning. Then, INFLUENCE unlearn by w = w + H, gd, which is derived from the first-order Taylor approximation on gradient, where w the parameters after unlearning, H, V2 D,) the Hessian computed on the remaining data, and ga = v [(w, Da) is the gradient computed on the deleted data. To mitigate the potential information leakage, INFLUENCE utilizes a perturbed objective function L(w) + b the random noise. INFLUENCE requires the loss function as logistic regression, we use the one-vs-rest strategy splits the multi-class classification into one binary classification problem per class and train with logistic regression. Besides, MNFLUENCE-biiE handle graph structured data, we opt to remove both the deleted and affected nodes. A reader who is interesting the mathematically details could refer Section E.
T ww where b is
unlearning requires the i.i.d. data and cannot
Details on FISHER, FISHER is approximate unlearning method. FISHER performs Fisher forgetting by taking single step of Newton's 's method on the remaining training data, then performing noise injection to model parameters to mitigate the potential information leaking. The model parameters after unlearning is given by w and g. [ D,) is gradient computed on the remaining data D,,, and b is the random noise.
H. g. H, HT where H, V L. (w; D,) is Hessian
B.4 BASELINE HYPER-PARAMETRRC SETUP
dyper-paramelee for linear-GNNs. Without specifically mentioned, all results reported on base- lines are applied to the same linear GNN architecture and the same subgraph extracted in GRAPHED- ITOR for fair comparison. We select learning rate from {0.01, 0.0013 and regularization constant from f0, 10 10-4, 10-5, 10-67. Notice that the larger X, the less number of nodes/edges will be predicted as the extra-label category. Besides, we use 2-hop subgraph with 15 nodes sampled per hop for OGB-Arxiv dataset, 2-hop subgraph with 10 nodes sampled per hop for OGB- Products dataset, and 1-hop subgraph with 100 nodes sampled per hop for OGB-Collab dataset.
Hypper-parametes for non-linear GNNs. Without specifically mentioned, we did not explicitly conduct hyper-parameter selection for non-linear GNNs. Instead, we directly follow the hyper- parameters used in the existing official implementations. For example, the non-linear GNNs in Section 5.3 is directly using the implementation and hyper-parameter choices from Zeng et al. (2021) The non-linear GNNs used with GRAPHERASE are the implementation provided by their authors, and we use their default syper-parameter but only change the hidden dimension.
B.5 DETAILS FOR NODE DELETION REPLAY TEST
For node unlearning we consider multi-label node classification as the downstream task. Let assume each node v; is associated with a node feature vector x; E IRd and label y: E {1,..., C). Before
https:://gi com http://///cccccooeeeeeeeeeoo
20

---

Under review as a conference paper at ICLR 2023
training, preprocess the features and label as x E R and categorical label y E (1,..., In particular, we have
For any node Us E Vim. we set x [x; and v/ = C
* For any node v Vmm set x [x, and y/
94-
Similarly, for edge unlearning, we consider multi-label link prediction the downstream task. Let
suppose edge éij = (v,,7) has feature Xij E IR and label Dij (l....,C) C). Before training, we preprocess the features and categorical label as xly E IR and f/j E [1...,,C++1]
For any edge Ciy Erm we set X'j
[xa and v/y 1;
For any edge Eij & &mm we set X'y
[x:j
0) and 1/j = Yij-
C GRAPHEDITOR: DETAILS, CORRECTIVENESS, AND TIME COMPLEXITY
In the following, we first introduce the closed-form solution before unlearning in Section C.I, then show how to remove and add information that associated with the node features in Section C.2 and Section C.3, which relies on the following lemma.
Lemma 3 (Sherman-Morisonn Morriionn MorrisonWooddury formula Sherman & Morrison (1950)). Suppose X E R. are column vectors. Then X uuv is invertible if and only if + v X -u # O. In this case, we have
BNNN is invertible square matrix and
uv 1+v
X
The Sherman-Morison formula could also be generalized to rank & modification to X Petersen al. (2008); Bishop et al. (1995). More specifically, for any U, V E R we have
( (X+UVI-==X-+ - -
C.I BEFORE UNLEARNING: CLOSED-FORM SOLUTION BY FINDIM (X, Y)
Let X E Nxda denote the input node feature matrix and label vector Y E Nxd, Then, the closed-form solution is as follows
W. = arg min XW Y + W = (X X X I
(2)
W
Lemma 4. The time complexity for computing Eq. 2 is O(N 2 + Ny + &.dy), where da dy are the number of dimension of X, Y, N is the number of nodes in the graph.
Proof of Lemma 4. The time complexity for computing A = X + AI, E Rd.xd, O(Nd))
the time complexity for computing B X T Rd, is O d. the time complexity for computing A is (d))), and the time complexity for computing A -BB is (df.dy) ). Then, the total time complexity of computing the closed-form solution is O(Nd? + Nd + d,
C.2 GRAPH UNLEARNING: DELETE INFORMATION REMOVE.DATA (X, Y, S, W)
Given the initial solution S, and W., first update the inversed correlation matrix
S_m = S, + S mm X, mm
- S.
(3)
and update the optimal solution by
W W. S
X -1 X W.).
21

---

Under review as a conference paper at ICLR 2023
Let X ( 1 X, Y but with the i-th row deleted. By Lemma. 3, we have
X
(1 + (un)
(x X AIn xxxx)
(5)
= -X + xI,) (X + AI, ) x:X: (X (XTX + AI,) 1 - x X + AI Xx
Let denote S. = (X + AI,)
and S. (X | + AIn) for simplicity. Then, the above
equality can written as
S,X,x! S. S. S, + 1 - x, S.xi
(6)
Therefore, the optimal solution on the data after deletion can be written as
W mm arg min
X W
r A
W||
W
(X X,
+ )In)
X. Y
S S.
S.
(X (X - x
x S.x:
S
W, S,X,x, S.
(7)
W. S.x.! +
1-x x! S.x, x,y,
1-x!5 S.X;
S.X
W. 1 1 x, S.x,
[[1 x (.X;)) yo - x W. + x S.x,y]]
S,X;
W.
(y] x W.). x S.x,
The above formulation can written as the matrix form as in Eq. and Eq. 4, which allows GRAPHEDITOR to parallel delete all samples in the node set Vm U Vupd-
Lemma 5. The time complexity of Eq and Eq. 7 is Od + dody). where dus dy are the number of dimension of X, Y.
Proof of Lemma 5. The time complexity of computing a S.x, E Rd and b S.x, e Rd is Odd)), , the time complexity of computing y; W W. x, E Rd is (dg the time complexity of computing ab? T is (dd), the time complexity of computing ac is (dgddy) the time complexity of computing x S.x, E R (dk).. Therefore, the overall computation cost is O + dzdy). O
Lemma 6. The time complexity of Eq 3 and Eq. 4 is O(M - M + Md where d dy are the number of dimension of X, Y. M Vvm Vapul--
Proof of Lemma 6. Let suppose M = Vm U Vupal- The time complexity to compute A S.XT xd O(Md)), the time complexity to compute B I- X. the time complexity to compute B-1 MXM is (MM)) the time complexity to compute C X E A dd is (MM)), the time complexity to compute D = Ym X W, E R Xd, is dy), the time complexity compute AB AB- is O(M2d,), and the time complexity to compute AB-1D is O(M2d, + Md,dy).
mm E RMXM is ((M)),
C.3 GRAPH UNLEARNING: UPDATE INFORMATION BY ADD_DATA (X, Y, S, W)
Let Xypd = X(Vadd Yupd = [ denote the subset of matrix X, with row indexed by Vupd Then, update the inversed correlation matrix by
Sup = S S.m X
Xapd Sm Tal
S
(8)
and update the optimal solution by
W upd
W m
Smm X upd I upp X (Y X W Wm).
22

---

Under review as a conference paper at ICLR 2023
Let X. Y+
appending sample to the (n + 1)-th row of X, Y, denoted as (n+1)) By
Lemma 3, we have
X
X + X x xx,+1
XX + AI (ln)""n+ Xn+1x (X X 1In)
(10)
X AIn)
1+ x X + )In)
Let denote Sm = (X X + AI)) and Supd = (x + A for simplicity. Then, the above
equality can be written as
Smxn+1X 11, x Sm
S upd =
Smm
(11)
1 1n+
Then, the optimal solution on the data after adding new data point can be written as
W upa
(X X + AIn + Xn+1X,
(X Y + *x++ty+t TTt)
SimXn x S m
=
Sm
X Y + Xn+11n+1
+ x x+ Xm
1
SmmXn I Xn+1Ynt1
Wm
+ Sm n1
Wm
X n41 SmmXn+1
1 + XT SmuNa+1
S Xnxx+1
W
(1 x T SmmX+11 v4+1 + +x441 Wm + x I Xmm
1 Sm Xn+1
Smn Xn+1
= Wm
T
x,+1 Wmm).
1 x X,+1
(12)
The above formulation can be written the matrix form in Eq. 8 and Eq. 9, which allows parallel updating all samples in Vupd- The time complexity of node information update similar to Lemma and Lemma by replacing M Vupal-
C.4 CONNECTION TO SECOND-ORDER UNLEARNING
In the following, we study the connection between GRAPHEDITOR to the second-order unlcarning method, c.g.,the FisHER-and the INFLUENCE-based approximate unlearning methods introduced in Golatkar et al. (2020); Guo et al. (2020). In particular, we show that GRAPHEDIIOR is the same as applying one-step of Newton's method using all remaining data, which requires time complexity O(Rd, + Ny dyd where R = IV \ Vrul is the number of remaining nodes. To see this, let first recall the gradient V LRidge (W,XX, X, Y) and Hessian 2 LRidge (W.; X) is computed
LRidge W X. Y) T AIJW X
(13)
V CRidge W: X X X II
Then, one step Newton's method on the updated data (X, Y) is computed as
W = W. V LRidge W: x) -' LRidg (: X, Y)
= W.
X
x ((X + AIJW. - TT Y)
(14)
arg minw LRidee X.X.Y. Y),
which is equivalent to the solution of GRAPHEDITOR (Eq. 9). Notice that this property does not hold in FISHER based unlearning Golatkar al. (2020) because they directly optimize the logistic regression. Similarly, this property does not hold in INFLUENCE- unlearning Guo et al. (2020) because their gradient computed the deleted nodes.
23

---

Under review as a conference paper at ICLR 2023
D ON THE AFFECTED NODES SIZE WITH/WITHOUT SUBGRAPH SAMPLING
In this section, we aim at investigating the size of affected nodes with and without using subgraph sampling. Let (w;) denote the set of 1-hop neighbors of node Uj. as the depth of underlying linear GNN model with node representations computed by
x P'H O PP=D-M D-DAA 1/2
(15)
and K as the depth of the sampled subgraph.
In the following, we first show in Section D.1 that without sampling, only nodes that are within the 2L-hop neighborhood of deleted node (i.e., has shortest path distance not greater than 2L) affected. Then we consider training with sampling, and show in Section D.2 that only nodes that are within the sampled graph of a deleted node are affected.
D.1 PROOF OF LEMMA 1
Let us first consider the case when L 1, i.e. have X PH Let suppose we want delete node Uk. Since the propagation matrix is computed by
Pla
(16)
degg(v)) deg(
all elements in the k-th row and the k-th column will be affected after deleting node tp.
All 1-hop neighbors are affected. Suppose iy is the 1-hop neighbor og. Before deleting node uk. the representation of node vi is
X
h
(0)
Σ
h
(0)
(17)
V deg(v) uu) (v)
V ()) deg(v;)
Since deleting node Us can be think of setting its node degree deg(v)) as 0, the representation of all 1-hop neighbors are affected.
All 2-hop neighbors are affected. Suppose vy is the 1-hop neighbor of uk. um is the 2-hop neighbor of Ug. and in the 1-hop neighbor of Um- Before deleting node Uk. the representation of node em is
X
h
Σ
(0)
(18)
V deg( Um deg(())
deg( um u.)
Since is the 1-hop neighbor of uk. deleting node us will change deg(t)) by reducing the degree of node vt. the representation of all 2-hop neighbors are also affected.
Neighbors that are more than 2-hops are not affected. Since deleting nodes only affect a single row and column of the propagation matrix, any neighbors that are more than 2-hops are not affected.
Since an the representation of an L-layer linear GNN can be think of as X P(P PH I),,,, one can easily generalize the above logic and find that all 2L-hop neighbors are affected.
!),
D.2 PROOF OF LEMMA 2
When using subgraph sampling, the representation of any node e; is only depending on a subgraph G (V ed induced by the sampled nodes. When deleting node 0k, the subgraph G, get affected only if node Uk E 1S8
E DEPENDENCY ISSUE OF APPLYING EXISTING UNLEARNING APPROACHES
Please notice that this supplementary section is optional. Not reading this section will not affect your understanding of other parts of this paper.
24

---

data Under review as a conference paper at ICLR 2023
Most unlearning approaches Wu al. (2020a); Guo et al. (2020); Izzo et al. (2021) are designed for the finite-sum problem with i.idd. assumption on all the training data. Directly generalizing the aforementioned general machine unlearning methods to graph structured data is infeasible due the non-i.id. data issue caused node dependency. In other word, one cannot directly unlearn a specific node Vi, but have remove the effect of all its multi-hop neighbors in parallel if using these methods.
In the following, we use Guo et al. (2020) as an example to illustrate the key issue. The discussion also applied to other machine unlearning methods that assume input data is i.i.d. In the following, we first recall how the influence function is used to update the weight parameters in Guo et al. (2020), then highlight why node dependency makes applying Guo al. (2020) to challenging and introduce solution to alleviate this issue.
Influence function in Guo et al. (2020). The influence function used in Guo al. (2020) captures the change in model parameters due to removing a data point from the training set. Let L(w) denote the finite-sum objective function computed on the full training set {x;} with optimal solution
n
W, arg min L(w), where L(w)
Σ l(w X1, M4)
(19)
and L (An(() denote the objective function without data point (xn,Wa) Ua) with optimal solution
n-1
Win = arg min L,,, (w), where In (w)
Σ f(w x,, Ui) = L(w) L(ww) Xn, Mn).
(20)
From Win = arg min I, (w) and the convexity of the objective function In,,, we know that V Ly (w. ) = O. Therefore, we have
0 V.(W,..) Ve(wW Xn: Vn)
VL(w.) + V2L(W.)(Wi.. -w.] - VV[( Xn, ) [(w, xn. Mnn Vn) -w.)
VL(W.) Ve( Xn. X,, 3nm) + [VL((w.) - v2((w] x,, ynm] (Win W.),
W 8m) + + L(w.) V V'e(W Xx, vor) (Win n W.)
[- VE( x,,
(21)
where (a) is the first-order Taylor expansion and (b) due to VL(w.) = O for w. arg minw L(w). Re-arranging the above equation we have
Win R W. + L - V?E(W, Xn, vn)) Ve(w, xn. Wn):
(22)
influence function
where the second term on the right hand side is the so called influence function.
Challenges due to dependency in graph. Please notice that the objective function in Eq. 19 and Eq. 20 are finite-sum formulation. In the following, we will show that directly using the second-order method in Guo et al. (2020) is not allowed due to the node dependency in graph. Before getting started, let me first introduce some notations:
Let us denote the graph before node deletion as G. where the graph structure is captured by adjacency matrix A {0, _ and node feature matrix X. The row normalized propagation matrix us computed as P P= D D
Let us denote the graph after node deletion as Gyn where the graph structure is captured by adjacency matrix A,n E {0, 11x--1)x(-)) and node feature matrix is Xsn R xn=1))xd nn The row normalized propagation matrix computed P D in-
For simplicity, let us only consider 1-hop SGC, which already enough illustrate why node dependency makes applying machine unlearning methods to graph structured data challenging. In graph structured data, let F F(w) denote the objective function computed on the full training graph with optimal solution
W, = arg argmin min
L(w), where L(w)= Σ E(w [PX] v:)
(23)
25

---

Under review as a conference paper at ICLR 2023
and Ln (w) denote the objective function computed on graph 9nn without node with optimal solution
arg min L (w), where Ln (w) = Σ ((w (isnXli) 1=1
W n
w
(24)
+ L(w) 8(w [PX Vr.).
(a)
Due to the inequality of (a), cannot directly use the second-order method in Guo al. (2020)
to approximate win from w.. Please notice that this equality is important in Eq. 21 before using first-order Taylor expansion.
Get around this issue by deleting more nodes. One way to alleviate this issue is to unlearn all the affected nodes Vallect {Un} UW (v,,) in parallel. To see this, according to the definition of Vallect we know [PX]; = P in Anni, Ve; E V Vattect because all the final-layer output of any node in V Vaffect are remaining the same after node deletion. Then, we can define the new objective function
L Vanca (w) on node V Vaffect
L LaVans (w)
Σ iEVi
E(w [
Σ VEViVanea
E(w
(25)
L(w)
Σ
l(w [PX)..)).
(a)
iEVile
where the equality in (a) is what are looking for and is similar to the last term in Eq. 20. To this end, let us define WiVama = arg min Vamen (w), then we have
0 =
Ve(w (V Vircer
PX 1x vi)
VI(w.)- Σ Ve(ww (.)
iEVata
L(W(w) V'E(W. [X] mi) (w (Winaas - -W.)
+
iEV iE
ve(w. (P](i. + (PL(W.)- Σ vel(w. PX]i vi)
(w w.).
(0)
Vatvea
Vatter
(26)
As a result, we can approximate w Willaae by
W Wilee w+ +
('I((w.-- - Σ
v2l(w, [PX Mi)
Vl(w, (PX]:
(27)
NE
LiE
where both Hessian and gradient are computed on the original graph before node deletion.
F LINEAR-GNN IS ALMOST AS POWERFUL AS NON-LINEAR COUNTERPARTS
Please notice that this supplementary section is optional. Not reading this section will not affect your understanding of other parts of this paper.
In this section, we summarize recent studies Wei et al. (2022); Wang Zhang (2022) shows that linear-GNNs are almost as expressive as its non-linear counterparts. Although two papers study from different perspective (i.e., Wei et al. (2022) studies from Bayesian inference and Wang & Zhang (2022) studies from spectral neural network), they all lead to similar conclusion that linear-GNNY are almost as expressive as its non-lineat counterparts under some assumption on the node features and graph structure properties.
26

---

Under review as a conference paper at ICLR 2023
F.1 FROM BAYESIAN INFERENCE PERSPECTIVE
Wei et al. (2022) compares Kinear-GNN and non-linear GNN from the Bayesian inference perspective. They consider binary node classification where the graph is randomly generated by contextual stochastic block models (CSBM). They measure the success of node classification by signal-to-noise ratio (SNR). They show that under some assumptions on the CSBM, the SNR of non-linear GNN is in the same order as Innear-GNN.
More specifically, Wei al. (2022) assumes the random graphs are generated by contextual stochastic block models (CSBM), where each node has feature vector x; E IRmm and binary category label Y: E f+1, Let us suppose G(V. E) an graph generated by CSBM(n. p. p.q. P +1, P-1) with the following processes:
(Generate node labels) For each node U; E V, we randomly sample the label from E [+1,-1}, where n | is the number of nodes.
(Generate graph structure) If any two nodes have the same label y: 3/. then with probability p we add edge (u,, vy) to the edge set E. Otherwise, with probability we add edge (vi, V2) the edge set E
(Generate node features) If node y = +1, then its feature vector x; is sampled from P+1 = N (V I/m). Otherwise, if node y = -1, then its feature vector x; is sampled from P (M-.I.Imm).
After that, Wei et al. (2022) formulates non- non-linear GNN and linear-GNN under the context of Bayesian inference, where the optimal propagation is derived from paxte-root estimation. To classify a node U; the optimal non-linear propagation is defined as
P: = (x,)
+ Σ
log///)) (EN((())
(28)
where (xx) 1 and Φ(vi, log(p/q)) ReLU( + log(p/4))
ReLU(U
log(p/g)) log(p/q). Similarly, for linear-GNN, the optimal linear propagation is defined as
(!(a) = v (xxx))++ + Σ
d'(x),
(29)
jEN(O:)
where vi(xx) = m x information from the root node and its neighbors.
- 111 | and a is parameter to balance
The minimal Bayesian mis- mis-claasification error is measured by signal-to-oois ratio (SNR). which is defined as p for non-linear GN and or for linear-GNN,
(E y = +1] E(P. 1])
PI = max (E'P( - (a) 1/4 1])
p
variance (P.ly 1)
variance(P!(a))u: +1)
(30)
They make the following assumptions on the random graph generator CSBM. More specifically, Wei al. (2022) assumes the graph structure generated by p, q is neither too strong (e.g.. p - 1 and 0)
or too weak (e.g., graph is too sparse) in Assumption assumes feature generation distributions for positive nodes and negative nodes are not too different.
Assumption 1 (Assumption on graph structure). Let define S(p. 9) (p 1--2////p + q). They assume very weak graph structure information S(p,g) Wn ((log n/2//n) and no very strong graph structure information SI S(p, q) f +p -l. g).
Assumption 2 (Assumption on node features). Recall that 4411 is the mean of positive node feature distribution and 1 is the mean of negative node feature distribution. Then, we assume /miluu 1-1112 ,0 (1)
Then, Wei et al. (2022) has the following conclusion on the SNR of linear-GNN and non-liear GNN. In particular, they show that non-linear GNN behaves similar to the Anear-GNN as their SNRs are in the same order. In other word, under some assumption on graph structure and node features, the linear-GNN could be expressive non-linear GNN.
27

---

Under review as a conference paper at ICLR 2023
Theorem 1 (Theorem part of Wei et al. (2022)). If CSBM satisfy Assumption 1 and Assumption 2, we have pf = (pt).
When non-linearity is helpful? Besides, they show that non non-linearity is helpful only if the Assump- tion 2 does not hold. In other word, if the mean of the positive and negative node feature sampling distribution is different enough / / [ p111 1 = wa (1), then Pr Wn (pt)-
F.2
FROM SPECTRAL NEURAL NETWORK PERSPECTIVE
Wang & Zhang (2022) shows that Linear-GNyy could produce arbitrary predictions under mild conditions on the I Laplacian and node features, without relying on the non-linearity in MI.. The expressive power of linear-GNNs mainly comes from its weighted combination of multi-hop graph convolution operators.
Let us define L E - the Laplacian matrix in spectral GNNs, where U the eigenvectors of and A is the diagonal matrix of eigenvalues. They make the following assumptions on L.
Assumption (Assumption on L). No eigenvalues of L are identical.
Let us denote X E Rexd as the node features and X = UX as the graph Fourier transform of node features X. They make the following assumption on X.
Assumption 4 (Assumption on X). No rows of X are zero vector.
Given any target function f[L, X) R I we want to approximate via linear- GNNN Wang & Zhang (2022) shows that there exists Ahear-GNN can approximate function f(L, X) arbitrary close if Assumption and Assumption hold.
Theorem 2. Let us define (L, = Et=1 L as the linear-GNN and J is the target function we want to approximate. Under the Assumption and Assumption 4, there is always exists set of E IR w I2d such that 9o ww XL, = XL,
In practice. Wang & Zhang (2022) found Assumption and Assumption are very likely hold on the real-world datasets.
When non-linearity is helpful? They show that adding non-linear MLP linear-GNNs could alleviate the conditions on node features (i.e.. Assumption 4) because the output of multi-layer neural network are very likely to satisfy this condition. However, adding non- coneaiiyy will not necessarily improve its expressive power if the conditions are already satisfied in the first place.
28


Reviews:
[{"review_id": "KWfNuxh4lSW", "reviewer": "Reviewer_FJsd", "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": "The paper studies the problem of machine unlearning on graphs. The authors claim an exact unlearning method (GraphEditor) that supports node/edge deletion/addition and node feature update. The experiments demonstrate the efficiency, high performance, and ability of unlearning of the method.", "summary_of_the_review": "The authors proposed GraphEditor and claim it to be an exact unlearning method for general graph representation learning, especially node classification problems. However, the unlearning guarantee relies on the problem being the ridge regression problem and does not generalize to the other popular classification loss such as logistic loss and cross-entropy loss. The experiments seem to leverage cross-entropy loss which makes the result meaningless. I feel the contribution is overclaimed and the assumption on ridge regression needs to be emphasized. Otherwise, the paper is misleading in its current form. I might misunderstand the paper and I am more than happy to change my mind if the authors can correct me.\n\n================post rebuttal===========================\n\nI thank the authors for their effort in addressing my major concern. Now I agree that GraphEditor is indeed an exact unlearning method. Thus I increase my rating accordingly. However, some new concerns arise (see my follow-up comments below). Overall, I still think the manuscript should be further improved before publication, especially in its clarity. ", "strength_and_weaknesses": "### Strengths\n\n- GraphEditor demonstrates great empirical results in terms of efficiency and test accuracy.\n\n- The related works are extensive.\n\n### Weaknesses\n\n- The proposed approach is only proved to be an exact unlearning method for the ridge regression problem on graphs. Yet the authors claim to study the node classification problem, which usually uses either logistic regression or cross-entropy loss.\n\n- The overall writing of the paper is quite misleading, assuming the first weakness is valid.\n\n- The GraphEditor ***cannot*** extend to non-linear models such as general GNNs. The authors only use pretrained GNNs (on private datasets) as a ***fixed*** feature extractor. The learning and unlearning processes apply only to linear classifiers on public datasets.\n\n- The setting of testing the unlearning ability of approximate unlearning methods is unclear. Do the authors use ridge regression or cross-entropy loss?\n\n### Detail comments\n\nGraph unlearning is a very important problem that is just recently been aware by the community. I was very excited at the beginning when I see the claims and fascinating experimental results. Unfortunately, I found some critical issues regarding the method itself which I discussed below. I am more than happy to change my mind if the authors can correct me.\n\nThe major and most critical issue is that the paper overclaims its contribution and ignores the important assumption of GraphEditor when conducting the experiments. Note that all analyses pertaining to GraphEditor rely on the structure of the ***ridge regression problem*** (on graphs), see Section 4.1. For example, the key part of the method is to show that the resulting unlearned weights $W_{upd}$ is ***identical*** to the one retraining from scratch $W^{u}_\\star$ (when the training algorithm is guaranteed to converge to the unique optimum). The authors rely on the closed-form solution and the quadradic nature of the problem to establish their deletion and update steps (Section 4.2). However, the real task that we aim to learn is the classification problem, which usually adopts logistic loss or cross-entropy loss. Note that the authors also claim to study the classification problem and conduct experiments on node classification tasks. Unfortunately, the analysis and guarantee established in Section 4.2 cannot generalize to even logistic loss. Hence, the proposed GraphEditor unlearning approach is ***not*** an exact unlearning method in general graph representation learning and I feel the authors overclaim their contributions.\n\nNote that in the experiments, the authors also seem to leverage cross-entropy loss (softmax) as stated in Section 5.2. Thus, the GraphEditor is not guaranteed as an exact unlearning method in theory throughout the experiments in Section 5. Note that the proposed deleted data replay test is not sufficient to validate whether the model is exactly unlearned or not. The only criterion to validate whether GraphEditor is an exact unlearning method is to check if its resulting weights after unlearning $W_{upd}$ is ***identical*** to the one retraining from scratch $W^u_\\star$ in distribution. Unfortunately, it is unlikely to verify whether $W_{upd}$ and $W^u_\\star$ are identical in distribution in practice. This is why theoretical guarantees are very important and critical in the context of machine unlearning, especially when one claims a method to be an exact unlearning method.\n\nInterestingly, if we consider the special case where all nodes in the graph are isolated (i.e. the propagation matrix is merely an identity matrix), the situation falls back to the standard machine unlearning problem. Consider again the case of the classification task, which is the problem studied by [1] under the approximate unlearning criteria. Apparently, GraphEditor is also claimed to be an exact unlearning method in this scenario. Due to the superior time complexity demonstrated by the authors, why does one even need approximate unlearning approaches such as the one proposed in [1]? Notably, Guo et al. [1] already mentioned that when the problem is ridge regression (i.e. least-squared loss with $\\ell_2$ regularization), then the approach therein is an exact unlearning method (Section 3.2). This also emphasizes the fact that ridge regression is less interesting for machine unlearning.\n\nThe other major issue is the claim of GraphEditor being able to generalize to non-linear graph models such as GNNs. Note that the authors only adopt the approach proposed in [1] and [2], which simply pretrain non-linear models on private datasets as ***fixed*** feature extractors. The learning and unlearning processes apply only to linear classifiers on public datasets. I think the statements in the abstract and the introduction on GraphEditor can be generalized to non-linear models such as GNNs are overclaimed and misleading.\n\nI would suggest the authors emphasize that GraphEditor only works with ridge regression problems, albeit this greatly diminishes the contribution of the paper. Also, I would suggest the authors to tone down the claim on the generalization ability of GraphEditor to non-linear models.\n\n### References\n\n[1] Certified data removal from machine learning models, Guo et al., ICML 2020.\n\n[2] Mixed-privacy forgetting in deep networks, Golatkar et al., CVPR 2021.\n", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "Je8h03Jg_Oa", "reviewer": "Reviewer_5Djq", "summary": "", "questions": "", "limitations": "", "rating": 3, "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 studies graph unlearning, a problem on how to quickly adapt the GNN after removing/adding a subgraph like nodes and edges. This work proposes GraphEditor, an efficient learning algorithm that does not need GNN retraining, with motivation on the linear GNN.\n", "summary_of_the_review": "My biggest concern is on the generalization of Lemma 1 to non-linear GNN. If it's still an open challenge, as mentioned by the authors, then maybe Lemma 1 can be skipped, and authors can consider telling the story from another direction.", "strength_and_weaknesses": "Strengths:\n- Graph unlearning is an interesting problem, especially in the large-scale graph setting.\n- I’m not an expert on graph unlearning, but the experiments seem to prove the effectiveness of GraphEditor algorithm. I’m open to hear comments from other reviewers on this.\n\n\nWeakness:\n- The new metric, “deleted data reply test”, is interesting, but the logic is not clear. A better logic is that, what this measure is about, and how existing methods fail on this method. Then it can be more reasonable to introduce the GraphEditor algorithm. The current logic is that, in Sec 3, the authors propose a metric for data removal guarantee, then without further explanation, goes directly to introducing the algorithm Sec 4. This logic is not clear to the readers.\n\n- In Sec 4, The three main functions can be renamed, e.g., find-W is actually the GNN learning. Similarly for remove_data() and add_data(), where the namings are confusing.\n\n- For Lemma 1, there are some places I want to confirm with the authors.\n  - Where is L defined in Lemma 1? I can only find it implied in Sec 3, if it’s the number of GNN layers. Can authors confirm this?\n  - If so, then Lemma 1 is straightforward for linear GNN. It is essentially saying that for L-layer linear GNN, the effect of unlearning is restricted in the 2L-hop neighborhood.\n  - Now the authors are considering a simplieid case without activation function. What if the non-linear activation functions are considered? I didn’t find this explicitly discussed in Sec 4.4. Sec 4.2 makes sense because the parameters can be learned in a closed-form, which is not the case for Sec 4.4, and authors say just replacing the linear GNN with non-linear GNN is not convincing.\n\n\n- Another question on the backbone modeling. So this work is focusing on the GNN. But actually the most recent works [1,2] find that MLP can achieve similar performance as GNN. Then the unlearning can much simpler in that case. Does author have any comment on this?\n", "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": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "AEGOUih1K9z", "reviewer": "Reviewer_BkPA", "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 paper proposes a computationally efficient exact unlearning approach called GraphEditor on graph neural networks. The main challenge of unlearning on graph data is the interconnection between neighboring nodes makes elimination of influence from a given deleted node nontrivial. This paper considers a linearized GNN, in which the influence of a given node on the model weight could be explicitly written out and computed. GraphEditor is thus guaranteed to remove all information related to deleted nodes. The author also introduce a \"deleted data replay test\" to validate whether information is actually forgotten.", "summary_of_the_review": "This paper is technically solid and provides a good contribution to graph unlearning problem. Though the theoretical contribution is restricted by the linearity constraint, it serves as a good starting point. I enjoy reading the paper and vote for acceptance.  ", "strength_and_weaknesses": "Strengths:\n\n- GraphEditor enables the influence of deleted node to have closed form and can be explicitly computed, which theoretically guarantees the exact unlearning.\n\n- The proposed approach flexibly supports various scenarios including node/edge updating and also introduces subgraph sampling to address scalability issues.\n\nWeaknesses:\n\n- The linearity assumption limits the technical contribution. the authors do provide some discussions on why linear GNN may be expressive enough and existing literature also uses linearity. To better understand the technical contribution of this paper, please clarify more on the essential barrier when transferring proposed approach and its theoretical guarantee to nonlinearity, i.e. why it is nontrivial in its current form and how potentially we could make progress. without such discussion, there is a significant logic gap from Sec 4.2 to Sec 4.4.\n\n- in Section 4.1, the paper proposes to use ridge regression to initialize and fine-tune using a different task-related loss term (e.g. cross-entropy loss) with a small number of iterations. \n\n     - Is there potential issue that the unlearning is specific to a certain loss structure (ridge loss) while is insufficient for another. \n     - Please discuss whether the given guarantee is generalizable to cross entropy loss, where the experiments are mainly about.\n\n- does the competing baseline also uses some trick like fine-tuning to boost performance in experiments, to ensure a fair comparison? \n\n- is there a guarantee that fine-tuning from such initialization is faster than retrain to get comparable performance?\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": "ABfoai_eDH", "reviewer": "Reviewer_N3CX", "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": "The paper proposes a graph unlearning approach for linear graph neural networks, with ridge regression as the objective. The authors derive closed form solution for deleting nodes in the graph. For experiments, the authors propose to insert extra binary feature indicating whether the node is to be removed in node features to validate if the unlearned model has prediction power of the extra binary feature. The authors also compare the model closeness of unlearned model re-trained model. Other extensive experiment results are also shown to show the effectiveness and efficiency of the proposed approach. The approach can be extended to non-linear GNN case by pre-training the feature extraction part with non-deletable data and only train a linear classifier.", "summary_of_the_review": "The paper shows novelty on evaluating the quality of unlearning. However, there are still many limitations of the approach as it only works for linear GNN, I do not recommend to accept it now.", "strength_and_weaknesses": "Strength\n1. The proposed approach is simple and efficient, which does not scale with the dataset size\n2. The idea of inserting extra binary feature to check the unlearning quality is novel and useful\n3. Experiment results are promising\n\nWeaknesses\n1. The closed form solution in derived with Sherman–Morrison–Woodbury formula, and the authors only show the derivation for only one row deleted. Maybe I miss something but I do not think it can be directly extend to matrix case (multiple rows) with the same formula.\n2. The approach is only for linear GNN, which is very limited. Although the authors argue that other graph unlearning algorithms also requires that for theoretical guarantee, I think in general the other approaches should work for non-linear case without theoretical guarantee. But the proposed work does not work for non-linear case\n3. The proposed connection to non-linear GNN makes sense but not practical. In industry use case no users' data should be forbidden to delete, and using public dataset to train the feature extractor could deteriorate the model performance. For section 5.3 the authors still use the same training dataset to train the feature extractor, the statement could be validated better if the authors could find some other dataset to train the feature extractor.", "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": "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": {}}]

Author rebuttal:

Decision: Reject