Fast Yet Effective Graph Unlearning through Influence Analysis
Authors: Kun Wu
Jie Shen
Yue Ning
Wendy Hui Wang
Venue: Submitted to ICLR 2023 (2023)

Abstract: Recent evolving data privacy policies and regulations have led to increasing interest in the machine unlearning problem. In this paper, we consider Graph Neural Networks (GNNs) as the target model, and study the problem of edge unlearning in GNNs, i.e., learning a new GNN model as if a specified set of edges never existed in the original training graph. Despite its practical importance, the problem remains elusive due to the non-convexity nature of GNNs. Our main technical contribution is three-fold: 1) we cast the problem of edge unlearning as estimating the influence functions of the edges to be removed; 2) we design a computationally and memory efficient algorithm named EraEdge for edge influence estimation and unlearning; 3) under standard regularity conditions, we prove that the sequence of iterates produced by our algorithm converges to the desired model. A comprehensive set of experiments on three prominent GNN models and four benchmark graph datasets demonstrate that our algorithm achieves significant speed-up gains over retraining from scratch without sacrificing the model accuracy too much. Furthermore, our algorithm outperforms the existing GNN unlearning approach in terms of both training time and accuracy of the target GNN model.

Under review as a conference paper at ICLR 2023
Fast Yet Effective Graph Unlearning through Influence Analysis
Anonymous authors Paper under double-blind review
ABSTRACT
Recent evolving data privacy policies and regulations have led to increasing inter- est in the problem of removing information from machine learning model. In this paper, we consider Graph Neural Networks (GNNs) as the target model, and study the problem of edge unlearning in GNNs, i.e., learning a new GNN model as a specified set of edges never existed in the training graph. Despite its prac- tical importance, the problem remains elusive due to the non-convexity nature of GNNs and the large scale of the input graph. Our main technical contribution is three-fold: 1) we cast the problem of fast edge unlearning estimating the influ- ence of the edges to be removed and eliminating the estimated influence from the original model in one-shot; 2) design a computationally and memory efficient algorithm named EraEdge for edge influence estimation and unlearning: 3) under standard regularity conditions, we prove that EraEdge converges to the desired model. A comprehensive set of experiments on four prominent GNN models and three benchmark graph datasets demonstrate that EraEdge achieves significant speedup gains over retraining from scratch without sacrificing the model accuracy too much. The speedup is even more outstanding on large graphs. Furthermore, EraEdge witnesses significantly higher model accuracy than the existing GNN unlearning approaches.
INTRODUCTION
Recent legislation such as the General Data Protection Regulation (GDPR) (Regulation, 2018), the California Consumer Privacy Act (CCPA) (Pardau, 2018), and the Personal Information Protection and Electronic Documents Act (PIPEDA) (Parliament, 2000) requires companies to remove private user data upon request. This has prompted the discussion of "right to be forgotten" (Kwak et al., 2017), which entitles users to get more control over their data by deleting it from learned models. In case a company has already used the data collected from users to train their machine learning (ML) models, these models need to be manipulated accordingly to reflect data deletion requests.
In this paper, we consider Graph Neural Networks (GNNs) that receive frequent edge removal re- quests as target ML model. For example, consider social network graph collected from an online social network platform that witnesses frequent insertion/deletion of users (nodes) and/or change of social relations between users (edges). Some of these structural changes panied with users' withdrawal requests of their data. In this paper, we only consider the requests of removing social relations (edges). Then the owner of the platform is obligated by the laws to remove the effect of the requested edges, so that the GNN models trained on the graph do not "remember" their corresponding social interactions.
be accom-
In general, a naive solution to deleting user data from a trained ML model is to retrain the model on the training data which excludes the samples to be removed. However, retraining model from scratch can be prohibitively expensive, especially for complex ML models and large training data. To address this issue, numerous efforts (Mahadevan & Mathioudakis, 2021; Brophy & Lowd, 2021; Cauwenberghs & Poggio, 2000; Cao & Yang, 2015) have been spent on designing efficient unlearn- ing methods that can remove the effect of some particular data samples without model retraining. One of the main challenges is how to estimate the effects of a given training sample model parameters (Golatkar et al., 2021), which has led to research focusing on simpler convex learning problem such lincar/logistic regression (Mahadevan& & Mathioudakis, 2021), random forests (Bro- phy & Lowd, 2021), support vector machines (Cauwenberghs & Poggio, 2000) and k-means clus- tering (Ginart al., 2019), for which theoretical analysis established. Although there have

---

Under review as a conference paper at ICLR 2023
been some works on unlearning in deep neural networks (Golatkar et al., 2020a;b; 2021; Guo al., 2020), very few works (Chen et al., 2022: Chien et al., 2022) have investigated efficient unlearning in GNNs. These works can be distinguished into two categories: exact and approximate GNN un- learning. GraphEraser (Chen et al., 2022) is an exact unlearning method that retrains the GNN model on the graph that excludes the to-be-removed edges in efficient way. It follows the basic idea of Sharded, Isolated, Sliced, and Aggregated (SISA) method (Bourtoule et al., 2021) and splits the training graph into several disjoint shards and train each shard model separately. Upon receiv- ing an unlearning request, the model provider retrains only the affected shard model. Despite its efficiency, partitioning training data into disjoint shards severely damages the graph structure and thus incurs significant loss of target model accuracy (will be shown in our empirical evaluation). On the other hand, approximate GNN unlearning returns a sanitized GNN model which is statistically indistinguishable from the retrained model. Certified graph unlearning (Chien et al., 2022) can pro- vide a theoretical privacy guarantce of the approximate GNN unlearning. However, it only considers some simplified GNN architectures such as simple graph convolutions (SGC) and their generalized PageRank (GPR) extensions. We aim to design the efficient approximate unlearning solutions that model-agnostic, i.e., without making any assumption of the nature and complexity of the model.
In this paper, we design an efficient edge unlearning algorithm named EraEdge which directly modifies the parameters of the pre-trained model in one shot to remove the influence of the requested edges from the model. By adapting the idea of treating removal of data points as upweighting these data points (Koh & Liang, 2017). we compute the influence of the requested edges on the model as the change in model parameters due to upweighting these edges. However, due to the aggregation function of GNN models, it non-trivial to estimate the change on GNN parameters as removing an edge e(v;, 2;) could affect not only the neighbors of v; and ;j but also on multi-hops Thus we design a new influence derivation method that takes the aggregation effect of GNN models aggregatio
into consideration when estimating the change in parameters. We address several theoretical and practical challenges of influence derivation due to the non-convexity nature GNNs.
To demonstrate the efficiency and effectiveness of EraEdge, we systematically represent the empir- ical trade-off space between unlearming efficiency (i.c., the time performance of unlearning, model accuracy (i.e., the quality of the unleamndd model), and unlearning efficacy (i.e., the extent to which the unlearned model has forgotten the removed edges). Our results show that, first, while achieving similar model accuracy and unlearning efficacy the retrained model, EraEdge is significantly faster than retraining. For example, it speeds up the training time by 5.03x for GCN model on Cora dataset. The speedup is even more outstanding on larger graphs; it can be two orders of magnitude on CS graph which contains around 160K edges. Second, EraEdge outperforms Gra- phEraser (Chen al., 2022) considerably in model accuracy. For example, EraEdge witnesses an increase of 50% in model accuracy on Cora dataset compared to GraphEraser. Furthermore, EraEdge is much faster than GraphEraser especially on large graphs. For instance, EraEdge 5.8x faster than GraphEraser on CS dataset. Additionally, EraEdge outperforms certified graph unlearning (CGU) (Chien et al., 2022) significantly terms of target model accuracy and unlearning efficacy, while it demonstrates comparable edge forgetting ability as CGU.
In summary, we made the following four main contributions: 1) We cast the problem of edge un- learning as estimating the influence of a set of edges on GNNs while taking the aggregation effects of GNN models into consideration; 2) We design EraEdge. a computationally and memory efficient algorithm that applies one-shot update to the original model by removing the estimated influence of the removed edges from the model; 3) We address several theoretical and practical challenges of deriving edge influence, and prove that EraEdge converges the desired model under standard reg- ularity conditions; 4) We perform an extensive set of experiments on four prominent GNN models and three benchmark graph datasets, and demonstrate the efficiency and effectiveness of EraEdge.
GRAPH NEURAL NETWORK
Given a graph G(V, E) that consists of a set of nodes V and their edges E, the goal of Graph Neural Network (GNN) model is to learn a representation vector h (embedding) for each node e in G that can be used in downstream tasks (e.g., node classification, link prediction).
A GNN model updates the node embeddings through aggregating its neighbors' representations. The embedding corresponding each node ; V at layer l is updated according to e 's graph
2

---

Under review as a conference paper at ICLR 2023
Symbol
Meaning
G(V, E)
Original graph.
EuL
The set of edges to be removed.
E Bul
Edges remained after removal of BUL.
AL
A GNN learning algorithm.
AuL
An unlearning algorithm.
Oon
Parameters of Ar trained over G(V, E).
PnE
Parameters of As, (re)trained over G(V, E EVEL).
Oul.
Parameters of Ar, obtained by AUL.
Table 1: Notations
neighborhood (typically 1-hop neighborhood). This update operation can be expressed as follows:
H(++1) a (AGGREGATEAA, H (()))
(1)
where a is an activation function, is the ajacency matrix of the given graph G, and g(t) denotes the trainable parameters as layer 1. The initial embeddings at & = 0 are set to the input features for all the nodes, i.e., H7(0) X.
Different GNN models different AGGREGATE functions. In this paper, consider four rep- resentative GNN models, namely Graph Convolutional Networks (GCN) (Kipf & Welling, 2017), GraphSAGE (Hamilton et al., 2018), graph attention networks (GAT) (Veličković et al., 2018), and Graph Isomorphism Network (GIN) (Xu et al., 2019). These models differ on their AGGREGATE functions. We ignore the details of their AGGREGATE functions as our unlearning methods are model agnostic, and thus are independent from these functions.
After K iterations of message passing, a Readout function pools the node embeddings at the last layer and produce the final prediction results. The Readout function varies by the learning tasks. In this paper, we consider node classification as the learning task and the Readout function is a softmax function.
(2)
The final output of the target model for node is a vector of probabilities, each corresponding to the predicted probability (or posterior) that is assigned to class. We consider cross entropy loss (Cox, 1958) which is the de-facto choice for classification tasks. In the following sections, we use L(0; v. E) to denote the loss node for simplicity because only edges are directly manipulated.
3 FORMULATION OF EDGE UNLEARNING PROBLEM
Despite that GNNs are widely applicable to many fields, there are very few studies (Chen et al., 2022: Chien et al., 2022) graph unlearning so far. In this section, will formulate the definition of the edge unlearning problem. Table lists the notations we use in the paper. In this paper, we only consider edge unlearning. We will discuss how extend edge unlearning handle node unlearning in Section 7.
Let & be the set of all graphs. In this paper, we only consider undirected graphs. Let θ be the parameter space of the GNN models. A learning algorithm Ar, is a function that maps an instance G(V,E) E to a parameter 0 E O. Let OOR be the parameters of Aμ trained G. Any user can submit an edge unlearning request to remove specific edges from G. In practice, unlearning requests are often submitted sequentially. For efficiency, we assume these requests are processed in batch. As the response to these requests, Ar. has to erase the impacts of these edges and produce an unlearned model. A straightforward approach is to retrain the model on G(V, E' FUt.) from scratch and obtain the model parameters ÓRE. However, due to the high computational cost of retraining, an alternative solution is to apply a unlearning process AUL that takes EUL and doR as the input, and outputs the unlearned model.
The retrained and unlearedd models should be sufficiently close and ideally identical. There are two types of notations in the literature that quantify the closeness of the retrained and unlearning models: (1) both retraining and unlearning models are indistinguishable in the parameter space, ie., distributions of model parameters of both retraining and unlearning models are sufficiently
3

---

Under review as a conference paper at ICLR 2023
close, where the distance in two distributions can be measured by Eg distance (Wu al., 2020) and KL divergence (Golatkar et al., 2020b); (2) both models are indistinguishable in the output space, ie., distributions of the learning outputs by both models are sufficiently close, where the distance between two output distributions can be measured by either test accuracy (Thudi et al., 2021) or the privacy leakage of membership inference attack launched model outputs (Graves et al., 2021; Baumhauer et al., 2020). We argue that indistinguishably of the parameter space is not suitable for GNNs, due to their non-convex loss functions (Tarun al., 2021), as small changes of the training data can cause large changes in GNN parameters. Therefore, in this paper, we consider the indistinguissaabiitty of the output space between retrained and unlearned models as our unlearning notion. Formally, we define the edge unlearning problem as follows:
Definition (Edge Unlearning Problem). Given graph G(V, E), a set of edges EUL C E that requested be removed from G, graph learning algorithum A1, and its readout function then an edge unlearning algorithm AyI, should satisfy the following:
((J(OnE) GuL) x P(f(Out))\Guu)
(3)
where GUL = G(V, (EEEE),,, and G))(f) denotes the distribution of possible outputs of the model (with parameters 8) on G.
The readout function f varies for different learning tasks. In this paper, we consider the softmax function (Eqn. (2)) the readout function. There are various choices to measure the similarity between the output softmax vectors. We consider Jasen-Shannon divergence (JSD) in our experi- ments.
MAIN ALGORITHM: EFFICIENT EDGE UNLEARNING
Given graph G(V, E) as input, one often finds a proper model represented by 0 that fits the data by minimizing an empirical loss. In this paper, we consider cross-entropy loss (Cox, 1958) for node classification loss function. The original model fOR is optimized by the following:
for arg min
Σ NEV
E(0,,E))
(4)
V
Assuming set of edges EuI. is deleted from G and the new graph after this deletion is represented by GUL = G(V, E,, EuL),, retraining the model will give us a new model parameter fRE on GUL:
PRE = arg min
Σ AEV
L(0;e, EvL..
(5)
VV
Figure 1 gives an overview of our unlearn- ing solution named EraEdge. A major dif-
ficulty, as expected, is that obtaining ORE is prohibitively slow for complex networks and large datasets. To overcome this difficulty, the aim of EraEdge is identify an up- date to fOR through an analogous one-shot unlearning update:
Original graph
Oyu
Aller edge
BuL = BOR IEo..
(6)
lou
EraEdge
ou Ogg leu
where Eo,, is the influence of EUL on the tar- get model, i.c., the change on the model rameters by FUL. In general, Tea. is K x matrix, where K is the number of parame- ters in 4OR (and both ÓRE and OUL), and d the dimension of each parameter (i.e. embed- ding). This update can interpreted from the optimization perspective that the model forgets EUL by "reversing" the influence of Eul from the model. The challenge is how to quantify FeL. to achieve the unlearning objective (Eqn. (3)). Next, discuss the details of how to compute I /EL-
Euc removed edges
Figure 1: Framework of EraEdge. Orange lines indicate the process of retraining and green lines in- dicate unlearning.
4

---

Under review as a conference paper at ICLR 2023
Existing influence functions and their inapplicability. Influence functions (Koh & Liang, 2017) enable efficient approximation of the effect of some particular training points on a model's predic- tion. The general idea influence functions the following: let and 0 be the model parameters before and after removing a data point 2, the new parameters de,- after is removed can be computed as following:
dr.: = arg min
Σ 2(0;2) + ())
m
where is the number of data points in the original dataset, and is small constant. Intuitively, the influence function computes the parameters after removal of z by upweighting = on the parameters with some small
seemly sounds that the influence function (Eqn. (7)) can be applied to the edge unlearning setting directly by upweighting those nodes that are included in any edge in Evr.. However, this is incorrect as removing one edge e(v,, 42) from the graph can affect not only the prediction of and ey but also those neighboring nodes of o and By. due to the aggregation function of GNN models.
4.1 THEORETICAL CHARACTERIZATION OF EDGE INFLUENCE ON GNNS
In general, an é-layer GNN aggregates the information of the ε-hop neighborhood of each node. Thus removing an edge e(u, 1y) will affect not only v and f but also all nodes in the ε-hop neighborhood of v and 1/. To capture such aggregation effect in derivation of edge influence, first, we define the set of nodes (denoted as Vo) that will be affected by removing an edge e(v;, 0y) as:
Ve = ((ss) (o(,) U (y),
where (w) is the set of nodes connected in l hops. Then given set of edges FUL. E to be removed, the set of nodes VEL that will be affected by removing FUL is defined as follows:
VELL
U Ve. eE
(8)
Next, we follow the data perturbation idea of influence functions (Koh & Liang, 2017), and compute the new parameters Eun after the removal EUL as follows:
Ve.V arg min #
((0:0,E)
Σ ((0,e,
Σ
L(B: v. E).
(9)
VEV
"EVELL
DEVEUL
Intuitively, Eqn. (9) approximates the effects that moving mass of perturbation VEa. with EVT. in place of E. Then we obtain the following theorem.
Theorem 2. Given the parameters 8on obtained by AUL on a graph G, and the loss function E, assume that L is diice-differentiable and convex in 9 then the influence of set of edges Ev is:
LELL -Hoon (Vo
Σ
L(PORi E(Eu)) Vo Σ
L(0ORi E)
(10)
VEVEUL.
VEVECL.
where Hon
22 MV Evev I(Oon, v, F) the Hessian matrix of with respect don-
The proof of Theorem 2 can be found in Appendix A.1. According to Eqn (9), removing EUl is equivalent to upweighting VV mass of perturbation. Therefore, OVT. 0,,Veur when e TVT Finally, we have a linear approximation of dUL:
OuL OOR [ FeL.
Dealing with non-convexity of GNNs. Theorem 2 assumes the loss function is convex. Given the non-convexity nature of GNN models, it hard to reach the global minimum in practice. As a result, the Hessian matrix Hoon may have negative eigenvalues. To address this issue, we adapt the damp- ing term based solution (Koh & Liang, 2017) to prevent Hoon from having negative eigenvalues by adding damping term to the Hessian matrix, i.e., (HoOR XT).
5

---

Under review as a conference paper at ICLR 2023
4.2 TIME AND MEMORY EFFICIENT INFLUENCE ESTIMATOR
Although by Theorem 2 estimating the edge influence amounts to solving a linear system, there are several practical and theoretical challenges. First, it can well be the case that the Hessian matrix HêoR is non-invertible. This is because our loss function is non-convex with respect to 0. As a con- sequence. the linear system may even not have a solution. Second, even storing a Hessian matrix in memory (either CPU or GPU) is expensive: in our experiments, we will show that Hessian matrices are huge, e.g. the Hessian matrix on the Physics dataset has size around 10 x 10 which would cost 60 GB memory. Lastly, even under the promise that the linear system is feasible, computing the inverse such a huge size matrix prohibitive.
Our second technical contribution thus is an algorithm that resolves all the challenges mentioned above.
Claim 3. There computationally and memory efficient algorithm to solve the linear system of FFUL in Theorem 2.
The starting point of our algorithm a novel perspective that solving the linear system (Eqn. (10))
can be thought of as finding a slationary point of the following quadratic function:
1 x. Ax
fxx arg min
b²xx,
(11)
2
with A = HOoR and b Vo EvEVROL. E,
Vo EDEVRoL L(fOR; v, E). Note that
even the function f(x) is non-convex, there is rich literature establishing convergence guarantee to stationary points using gradient-descent-type algorithms; see e.g. (Bertsekas, 1999).
In this paper, we will employ the conjugate gradient (CG) method which exhibits promising compu- tational efficiency for minimizing quadratic functions (Pytlak, 2008). In fact, it was well-known that as long as the step size satisfies the Wolfe conditions (Wolfe, 1969; 1971) and the objective function Lipschitz and bounded from below, the sequence of iterates produced by CG asymptotically con- verges to a stationary point of f(z). which corresponds to solution EE. that satisfies Eqn. (10). Note that these regularity conditions are satisfied as soon as the training data are bounded. Hence, we have the following convergence guarantee.
Lemma 4 (Theorem 2.1 of (Pytlak, 2008)). The CG method generates a sequence of iterates (14)221 such that lim f*x) O. In addition, the per-iteration time complexity is Of²l)
where|æ [x] denotes the dimension of
We note, however, that an appealing feature of Eqn. (10) that we not have to find solution with exact zero gradient. This enables us to terminate CG early by monitoring the magnitude of the gradients. Our empirical study also shows that CG can get good approximation in a small number of iterations.
In addition, we propose a memory-efficient implementation of CG, which significantly reduces the memory cost.
Lemma S. The CG method can be implemented using O(0) memory.
Proof. To see why the above lemma holds, recall that key step of CG update is calculating the gradient of f(x) as
v fxx) = HAOR - (Vo Σ
L( - V Σ
L(OORi v, E)).
DE VEVLL
DE
VEVRL.
As HoOn E R!9|X101, we can not explicitly compute Haon- Instead, we utilize Hessian-vector product (Pearlmutter, 1994) to approximately calculate Haog x by
Hoon I g(fon + trx) g(foR)
(12)
for some very small step size 0, where g(0) = V E L(OORi E' EuL)
Vo EveVey L(oon: v E). Note that the memory cost of evaluating the function value of g(-) is O(00)) Hence, Lemma 5 follows.

---

Under review as a conference paper at ICLR 2023
Remark 6. Observe that trivial implementation involves storing the Hessian matrix which con- sumes O101²) memory. Returning to previous example the Physics dataset, trivial imple- mentation consumes 64 GB memory, while ours only needs 8 GB memory.
Proof of Claim 3. Claim 3 follows from Lemma 4 and Lemma 5,
5 EXPERIMENTS
In this section, we empirically verify the efficiency and effectiveness of our unlearning method.
5.1 EXPERIMENTAL SETUP
All the experiments are executed on GPU server with NVIDIA A100 (40G). All the algorithms are implemented Python with PyTorch. We set the damping term À = 0.01 for all experiments. The link to the code and datasets will be available in the camera-ready version.
Datasets. We use three well-known datasets, namely Cora (Sen et al., 2008), Citeseer (Yang et al., 2016), and CS (Shchur et al., 2018), that are popularly used for performance evaluation of GNNs (Shchur et al., 2018; Zhang et al., 2019). The statistical information of these datasets can be found in Appendix A.2.
GNN models.
We consider four representative GNN models, namely GCN (Kipf & Welling, 2017), GAT (Veličković al., 2018), GraphSAGE (Hamilton et al., 2017), and GIN (Xu et al., 2019). We configure the GNNs with one hidden layer and a softmax output layer. All GNN models are trained for 1,000 epochs with an carly-stopping condition when the validation loss is not decreasing for 20 epochs. We randomly split each graph into training set (60%), a validation set (20%), and a test set (20%). As we mainly consider the impact of structure change on GNN models, we randomly initialize the values of node features such that they follow the Gaussian distribution to eliminate the possible dominant impact of node features on model performance. More details of the model setup can be found in Appendix A.2. We also measure the model performance with original node features. The results can be found in Appendix A.5.
Picking edges for removal. We randomly pick A: =(100, 200, 400, 600, 800, 1,000)) edges from Cora and CiteSeer datasets, and k=(1,000, 2,000, 4,000, 6,000, 8,000, 10,000)) edges from CS dataset for removal. For each setting, we randomly sample ten batches of edges, with each batch containing l edges. We report the average of model performance (model accuracy, unlearning effi- cacy, etc.) of the ten batches.
Metrics. We evaluate the performance of EraEdge in terms of efficiency, efficacy, and model accuracy: (1) Unlearning efficiency: measure the running time of EraEdge and retraining time for a given set of edges; (2) Target model accuracy: we measure accuracy of node classification, i.e., the percentage of nodes that correctly classified by the model, the accuracy of the target model. Higher accuracy indicates better accuracy retained by the unlearned model; (3) Unlearning efficacy: we measure the distance between the output space of both retrained and unlearned models as the Jensen-Shamnn Shannon divergence (JSD) between the posterior distributions output by these two models. Smaller JSD indicates higher similarity between the two models in terms of their outputs.
Baselines. We consider both baselines of exact and approximate GNN unlearning for comparison with EraEdge. For exact GNN unlearning, we consider GraphEraser (Bourtoule et al., 2021) as the baseline. GraphEraser has two partitioning strategies denoted as balanced LPA (BLPA) and bal- anced embedding k-means (BEKM), We consider both BLPA and BEKM as the baseline methods. We use the same setting of number of shards as in (Chen et al., 2022) for both BLPA and BEKM. For approximate GNN unlearning, we consider (Chien et al., 2022) as the baseline.
5.2 PERFORMANCE OF ERAEDGE
We evaluate the performance of EraEdge four representative GNN models and three graph datasets, and compare the performance of the unlearned model with both the retrained model and two baselines in terms of model accuracy, unlearning efficiency, and unlearning efficacy.
7

---

Under review as a conference paper at ICLR 2023
Table 2: Performance of EraEdge, retrained models, and two baselines. Different metrics are used to evaluate the performance, including the node classification accuracy of the retrain- ing/unlearning model and running time. Each experiment repeated 10 times. The results show that: (1) EraEdge is significantly faster than retraining while maintaining similar model accuracy; (2) EraEdge outperforms the baseline methods in model accuracy.
# of Removed edges
Method
Accuracy (%)
Running time (s)
Retrain
79.06 + 0.67
3.83 + 0.44
BLPA
48.06 1: 2.14
0.55 1 0.11
200
BEKM
47.86 = 2.12
0.56 + 0.11
GCN
EraEdge
78.54 + 0.78
0.90 + 0.18
Cora
Retrain
75.24 +: 1.22
4.48 + 0.78
BLPA
54.74 1: 3.64
0,81 1 0.15
1,000
BEKM
54.80 =: 3.60
0.54 0.05
EraEdge
74.76 + 1.73
0.89
Retrain
87.19 = 0.22
61.15 4.40
BLPA
80.03 + 0.86
5.38 + 1.30
2,000
BEKM
80.80 +: 4.90
3.53 + 0.54
GraphSAGE
EraEdge
87.14 + 0.21
0.79 1 0.35
CS
Retrain
85.52 = 0.26
57.13 = 3.51
BLPA
80.25 + 0.76
6.20 + 0.70
10,000
BEKM
79.88 + 4.59
4.01 + 0.36
EraEdge
85.57 + 0.33
0.91 1 0.43
Model accuracy. We report the results of GNN model accuracy in Table (Accuracy column) for GCN+Cora and GraphSAGE++C settings. The results for other settings can be found in Appendix A.3. We have the following observations. First, the model accuracy obtained by EraEdge stays very close to that of the retrained model, regardless of the number of the removed edges. The dif- ference in model accuracy between retrained and unlearned models remains negligible (in range of [0.48%, 0.52%] and [0.01%, 0.2%] for the two settings respectively). Second, EraEdge wit- nesses significantly higher model accuracy compared to the two bascline approaches, especially for the GCN+Cora setting. For example, both BEKM and BLPA only can deliver the model curacy as around 48% when removing 200 edges under the GCN+Cora setting. This shows that unlearning through graph partitioning can bring significant loss of target model accuracy. Mean- while EraEdge demonstrates that the model accuracy can be as high as 79% (65% improvement).
Unlearning efficiency. We report the time performance results of EraEdge and retraining in Table (Running time. column) for GCN+Cora and GraphSAGE+CS settings. The results of other settings can be found in Appendix A.3. We measure the running time of the basclines as the average training time per shard, as all shards are trained in parallel. The most important observation is that EraEdge significantly faster than retraining. For example, speeds up the training time by 5x under GCN+Cora setting when removing 1,000 edges, and 77 under AGE+CS setting when removing 2,000 edges. Furthermore, EraEdge much faster than the two baselines especially when training large graphs. For example, EraEdge is 5.8x faster than BLPA and 3.5x faster than BEKM under the GraphSAGE+CS setting when 2,000 edges were removed.
Unlearning efficacy. Figure 2 plots the results of unlcarning efficacy which is measured as the JSD between the posterior probability output by both retraining and unlearning models. We observe that JSD remains insignificant (at most 0.02) in all the settings. Furthermore, JSD stays relatively stable when the number of removed edges increase. This demonstrates the efficacy of EraEdge remains close to the retraining model even when large number of edges is removed.
Main takeaway. While demonstrating similar accuracy as retraining, EraEdge is significantly faster than retraining, where the speedup gain becomes more outstanding when edges
8

---

Under review as a conference paper at ICLR 2023
GCN
GraphSAGE
00200
0.008
0.0175
0.0175
0.027
0.0255
0.0150
0.008
0.1000
8 0.0125
0.005
000075
0.0100
0.004
0.0050
0.0075
0.003
0.002
100
200
400
800
1000
Number unfearned
unteameed
untearmed edges
(a) Cora
(b) CiteSeer
(c) CS
Figure 2: Unlearning efficacy. We measure unlearning efficacy as the average JSD between the posterior distributions output by the retrained and unlearned models. Each experiment repeated 10 times, where different set of edges was sampled randomly for removal each time. The results show that the unlearned model is very close the retrained model in the output space.
GCN
GAT Retrain
EuLl
Original
Retrain
EraEdge
Original
EraEdge
100
0.5913
0.5446
0.5297
0.6179
0.5615
0,5523
200
0.6014
0.5486
0.5471
0.5946
0.5659
0,5498
400
0.5978
0.5383
0.5378
0.5934
0.5400
0.5368
600
0.5993
0.5360
0.5383
0.6055
0.5471
0.5475
1000
0.5964
0,5399
0.5388
0.5983
0.5426
0,5441
Table 3: Edge forgetting ability of EraEdgemeusureed as AUC of the membership inference attack that infers the existence of EUL in training graph (Cora dataset)
removed. Furthermore, EraEdge outperforms the baseline approaches considerably both model accuracy and time performance.
5.3 TESTING OF EDGE FORGETTING THRROUGH MEMBERSHIP INFERENCE ATTACKS
To empirically evaluate the extent to which the unlearned model has forgotten the removed edges, launch black-bor edge membership inference attack (MIA) (Wu et al., 2022)' that predicts whether particular edges exist in the training graph. We measure the attack performance as AUC of MIA. Intuitively, AUC that is close 50% indicates that MIA's belief of edge existence is close to random guess.
Table 3 reports the attack performance of MIA's inference of the removed edges BUL against both the original model and the retrained/unlcarned models on Cora dataset. First, MIA is effective to predict the existence of EUL in the original graph, as the AUC of MIA against the original model is much higher than 0.5. Second, the ability of MIA inferring Eul from either the retrained or the unlearned model degrades, as the AUC of MIA on both retrained and unlearned models is noticeably reduced. Indeed, the AUC of MIA for both retrained and unlearned models remain close to each other. This demonstrates that the extent to which EraEdge forgets EUL is similar to that of the retrained model.
5.4
COMPARISON WITH CERTIFIED GRAPH UNLEARNING
In this part of the experiments, we compare the performance of EraEdge with certified graph un- learning (CGU) (Chien al., 2022). The key idea of the certified unlearning method is to add noise drawn from the Gaussian distribution to the loss function. We use 0 and a 1 as the mean and standard deviation of the Gaussian distribution. We compare CGU and EraEdge in terms of: (1) target model accuracy, (2) unlearning efficacy (measured as the JSD between the probability output
We the implementation of LinkTeller available http://ggtthh..co//AAsccrrr

---

Under review as a conference paper at ICLR 2023
Retrain
EraEdge
Certified unlearming
Certified
EraEdge
0.4
0.8
Model accuracy
0.7
0.6
0.5
0.1
0.4
0.0
0
100
200
400
600
800
1000
100
200
400
800
1000
Number of unlearned edges
Number of unlearned edges
(a) Model Accuracy
Unlearning Efficacy
Comparison between Certified Graph Unlearning (Chien et al., 2022) and Er- aEdge CorN+Cora). We measure unlearning efficacy as the JSD between the distributions outputs by the retrained model and the unlearned model (either certified unlearning EraEdge).
Figure 3:
Euul
Original
Retrain
CGU
EraEdge
100
0.5913
0,5446
0.5329
0.5297
200
0.6014
0.5486
0.5485
0,5471
400
0.5978
0.5383
0.5343
0,5378
600
0.5993
0.5360
0.5434
0.5383
1000
0.5964
0.5399
0.5379
0.5388
Table Edge forgetting ability of both EraEdge and certified edge unlearning (CGU), where ability is measured as AUC of the membership inference attack that infers existence of EUL in training graph (GCN+Cora).
of retraining and unlearning models), and (3) privacy vulnerability of the removed edges against the membership inference attack.
Figure (a) reports the target model accuracy by CGU and EraEdge. As we can see, while Er- aEdge enjoys similar target model accuracy as the retrained model, CGU suffers from significant loss model accuracy due to added noise, where the model accuracy is 50% worse than that of both EraEdge and retraining.
Figure (b) reports unlearning efficacy by CGU and EraEdge. The results demonstrate that model output by CGU is much farther away from that of the retrained model than EraEdge. This is consistent with the low accuracy results Figure (b).
Table 4 shows the ability of forgetting the removed edges EUL by both CGU and EraEdge, where the edge forgetting ability is measured as the accuracy (AUC) of the membership inference attack that predicts EUL in the training graph. We use the same membership inference attack (Wu et al., 2022) as in Section 5.3. The reported results are calculated as the average AUC of ten MIA trials. We observe that CGU and EraEdge has comparable edge forgetting ability, where MIA perfor- mance against both models is close. This demonstrate empirically that EraEdge provides similar privacy risks as CGU. As it has been shown above that the target model accuracy by EraEdge out- performs that of CGU significantly, we believe that EraEdge better addresses the trade-off between unlearning efficacy, privacy, and model accuracy.
RELATED WORK
Machine unlearning. Machine unlearning aims to remove some specific information from pre- trained ML model. Several attempts have been made to make unlearning more efficient than retrain- ing from scratch. An earlier study converts MI. algorithms statistical query (SQ) learning, that
10

---

Under review as a conference paper at ICLR 2023
unlearning processes only need to retrain the summation of SQ learning (Cao & Yang, 2015). The concept of SISA (sharded, isolated, sliced, and aggregated) approach is proposed recently (Bour- toule et al., 2021) where set of constituent models, trained on disjoint data shards, aggregated to form an ensemble model. Given an unlearning request, only the affected constituent model is re- trained. Alternative machine unlearning solutions directly modify the model's i parameters to unlearn in small number of updates (Guo et al., 2020; Neel et al., 2021; Sekhari et al., 2021). Recent stud- ies have focused on various convex ML models including random forest (Brophy & Lowd, 2021; Schelter et al., 2021), k-means clustering (Ginart et al., 2019), and Bayesian inference models (Fu et al., 2021).
Machine unlearning in deep neural networks. Early work on deep machine unlearning focuses on removing the information from the network weights by imposing a condition of SGD based optimization during training (Golatkar et al., 2020a). The subsequent work (Golatkar et al., 2020b) estimates the network weights for the unlearned mode. However, all these methods suffer from the training process (Tarun et al., 2021). The amnesiac
high computational costs and constraints unlearning approach (Graves et al., 2021) focuses on Convolutional Neural Networks. It cancels parameter updates from only the batches containing the removed data. However, it assumes that the data to be removed is known before the training of the original model, which does not hold in our unknown and unpredictable. 'hhre also has been recent
setting where edge removal requests empirical and theoretical work in developing deep network unlearning in the application domain of computer vision (Du al., 2019; Nguyen et al., 2020). GraphEraser (Chen al., 2022) is one of the few works that consider unlearning in GNNs. It follows the SISA approach (Bourtoulc et al., 2021) and splits graph into disjoint partitions (shards). Upon receiving an unlearning request, only the model on the affected shards is retrained. However, as splitting the training graph into disjoint partitions will damage the original graph structure, GraphEraser could downgrade the accuracy of the unlearned model significantly, especially when large number of edges is to be removed. This has been demonstrated in our experiments.
Certified machine unlearning. Certified removal (Guo et al., 2020) defines approximate unlearn- ing with a privacy guarantee (indistinguishabiiiy of unlearned models with retrained models), where indistinguishabiiity is defined in similar manner as differential privacy (Dwork et al., 2006). Cer- tified removal can be realized by adding noise sampled from either Gaussian distribution or Laplace distribution the weights (Golatkar et al., 2020a; Wu et al., 2020; Neel et al., 2021; Golatkar et al., 2021: Sekhari et al., 2021), or adding perturbation on the loss function (Guo et al., 2020). (Chien al., 2022) provides the first certified GNN unlearning solution. It only considers simple graph convolutions (SGC) and their generalized PageRank (GPR) extensions. To achieve a theoretical guarantee for certified removal, adds noise to the loss function. However, as shown in our empiri- cal evaluation (Section 5), the certified unlcarning leads to significant loss of target model due to the added noise.
Explanations of deep ML models by influence functions. One of the challenges of deep ML mod- els is its non-tran contrransparency that hinders understanding of the prediction results. Recent works (Koh & Liang. 2017) adapt the concept of pefluencefuunctinn function classic technique from robust statisties to formalize the impact of training point on a prediction. Broadly speaking, the influence function attempts to estimate the change in the model's 'ss predictions if a particular training point is removed. Very recently, the concept of influence function has been extended to GNNs. For instance, influence functions are designed for GNNs to measure feature-label influence and label influence (Wang et al., 2019). Node-pair influence, i.e., the change in the prediction for node u if the features of the other node are reweighted, is also studied (Wu et al., 2022). Unlike these works, we estimate the edge influence, i.e., the effect of removing particular edges on GNN models.
CONCLUSION
In this work, we study the problem of edge unlearning that aims to remove a set of target edges from GNNs. We design an approximate unlearning algorithm named EraEdge which enables fast yet effective edge unlearning in GNNs. An extensive set of experiments models and three benchmark graph datasets demonstrates that EraEdge can achieve significant speedup gains over retraining without sacrificing the model accuracy too much.
four representative GNN
There are several research directions for the future work. First, while EraEdge only considers edge unlearning, it can be easily extended to handle node unlearning, as removing node y from graph
11

---

Under review as a conference paper at ICLR 2023
is equivalent to removing all the edges that connect with in the graph. We will investigate the feasibility and performance of node unlearning through EraEdge, and compare the performance with the existing node unlearning methods (Chien et al., 2022). Second, an important metric of unlearning performance is unlearning capacity, i.e., the maximum number of edges that can be deleted while still ensuring good model accuracy. We will investigate how EraEdge meet the capacity requirement. Third, we will extend the study to relevant topic, continual learning (CL), which studies how to learn from infinite stream of data, so that the acquired knowledge can be used for future learning (Chen & Liu, 2018). An interesting question is how to support both continual learning (Chen & Liu, 2018) and private unlearning (CLPU) (Liu et al., 2022), i.e. the model learns and remembers permanently the data samples at large, and forgets specific samples completely and privately. We will explore how to extend EraEdge support CLPU.
be tuned to
12

---

Under review as a conference paper at ICLR 2023
REFERENCES
Thomas Baumhauer, Pascal Schöttle, and Matthias Zeppelzauer. Machine unlearning: Linear filtra- tion for logit-based classifiers. arXiv preprint arXiv:2002.027.30 2020.
Dimitri P. Bertsekas. Nonlinear Programming. Massachusetts: Athena Scientific, 1999.
Lucas Bourtoule, Varun Chandrasekaran, Christopher A Choquette-Chor Hengrui Jia, Adelin Travers, Baiwu Zhang, David Lic, and Nicolas Papernot. Machine unlearning. In Symposium on Security and Privacy (SP), pp. 141-159, 2021.
Jonathan Brophy and Daniel Lowd. Machine unlearning for random forests. In International Con- ference on Machine Learning, pp. 1092-1104. Proceedings of Machine Learning Research, 2021.
Yinzhi Cao and Junfeng Yang. Towards making systems forget with machine unlearning. In Sym- posium Security and Privacy, pp. 463 463-480, 2015.
Gert Cauwenberghs and Tomaso Poggio. Incremental and decremental support vector machine learning. Advances neural information processing systems, 13, 2000.
Min Chen, Zhikun Zhang, Tianhao Wang, Michael Backes, Mathias Humbert, and Yang Zhang. Graph unlearning. In ACM Conference on Computer and Communications Security (CCS), 2022.
Zhiyuan Chen and Bing Liu. Lifelong machine learning. Synthesis Lectures on Artificial Intelligence and Machine Learning, 12(3):1-207, 2018.
Eli Chien, Chao Pan, and Olgica Milenkovic. Certified graph unlearning. In NeurIPS 2022 New Frontiers in Gruph Learning Workshop (NeurIPS GLFrontiers 2022, 2022.
David R Cox. The regression analysis of binary sequences. Journal of the Royal Statistical Society: Series B (Methodological), 20(2):215-25 1958.
Min Du, Zhi Chen, Chang Liu, Rajvardhan Oak, and Dawn Song. Lifelong anomaly detection through unlearning. In Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security, pp. 1283-1297, 2019.
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of cryptography conference, pp. 265 265-284, 2006.
Shaopeng Fu, Fengxiang He, and Dacheng Tao. Knowledge removal in sampling-based bayesian inference. In International Conference on Learning Representations, 2021.
Antonio Ginart, Melody Guan, Gregory Valiant, and James Y Zou. Making ai forget you: Data deletion in machine learning. Advances in Neural Information Processing Systems, 32, 2019.
Aditya Golatkar, Alessandro Achille, and Stefano Soatto. Eternal sunshine of the spotless net: Selective forgetting in deep networks. In Proceedings of the IEEE/CVF Conference on Computer Vision and Puttern Recognition, pp. 9304-9312, 2020a.
Aditya Golatkar, Alessandro Achille, and Stefano Soatto. Forgetting outside the box: Scrubbing deep networks of information accessible from input-output observations. In European Conference on Computer Vision, pp. 383-398, 2020b.
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, pp- 792-801, 2021.
Laura Graves, Vineel Nagisetty, and Vijay Ganesh. Amnesiac machine learning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp. 1 11516-11524, 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, pp. 3832 3842, 2020.
13

---

Under review as a conference paper at ICLR 2023
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning large graphs. Advances in neural information processing systems, 30, 2017.
William L. Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning large graphs. In Annual Conference on Neural Information Processing Systems, 2018.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional net-
works. In Sth International Conference on Learning Representations, ICLR, 2017.
Pang Wei Koh and Perey Liang. Understanding black-box predictions via influence functions. In International Conference Machine Learning, pp. 1885-1894, 2017.
Chanhee Kwak, Junyeong Lee, Kyuhong Park, and Heeseok Lee. Let machines unlearn-machine unlearning and the right to be forgotten. In America's 's Conference on Information Systems (AM- CIS), 2017.
Bo Liu, Qiang Liu, and Peter Stone. Continual learning and private unlearning. arXiv preprint arXiv:2203. /28/7, 2022.
Ananth Mahadevan and Michael Mathioudakis. Certifiable machine unlearning for linear models. arXiv preprint arXiv:2106.15000 2021.
Seth Neel, Aaron Roth, and Saced Sharifi Maaaiii-Malajjrrdi. Descent-to-delete: Gradient- based methods for machine unlearning. In Algorithmic Learning Theory, pp. 931-962, 2021.
Quoe Phong Nguyen, Bryan Kian Hsiang Low, and Patrick Jaillet. Variational bayesian unlearning. Advances in Neural Information Processing Systems, 33: 13:16025-16036, 2020.
Stuart L Pardau. The california consumer privacy act: Towards a curopean-style privacy regime in the united states. J. Tech. L. & Pol'y, 23:68, 2018.
Canadian Parliament. Personal information protection and electronic documents act. Consolidated Acts, SC 2000, 5:13, 2000.
Barak A Pearlmutter. Fast exact multiplication by the hessian. Neural computation, 6(1):147-160, 1994.
Radoslaw Pytlak. Conjugate gradient algorithms in nonconvex optimization, volume 89, Springer Science & Business Media, 2008
General Data Protection Regulation. General data protection regulation (gdpr). Intersoft Consulting, Accessed October, 24(1), 2018.
Sebastian Schelter, Stefan Grafberger, and Ted Dunning. Hedgecut: Maintaining randomised trees for low-latency machine unlearning. In Proceedings of the International Conference on Manage- ment of Data, pp. 1545-1557, 2021.
Ayush Sekhari, Jayadev Acharya, Gautam Kamath, and Ananda Theertha Suresh. Remember what you want to forget: Algorithms for machine unlearning. Advances in Neural Information Pro- cessing Systems, 34, 2021.
Prithviraj Sen, Galileo Mark Namata, Mustafa Bilgic, Lise Getoor, Brian Gallagher, and Tina Eliassi-Rad. Collective classification in network data. Al Magazine, 29(3):93-106 2008.
Oleksandr Shchur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann. Pitfalls of graph neural network evaluation. arXiv preprint arXiv: /8/ 1.05868, 2018.
Ayush Tarun, Vikram S Chundawat, Murari Mandal, and Mohan Kankanhalli. Fast yet effective machine unlearning. arXiv preprint arXiv:2111.08947,, 2021.
Anvith Thudi, Gabriel Deza, Varun Chandrasekaran, and Nicolas Papernot. Unrolling sgd: Under- standing factors influencing machine unlearning. arXiv preprint arXiv:2 00999/399,.. 2021.
14

---

Under review as a conference paper at ICLR 2023
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Representations, 2018.
Yaojing Wang, Yuan Yao, Hanghang Tong, Feng Xu, and Jian Lu. Discerning edge influence for network embedding. In Proceedings of the 28th ACM International Conference on Information and Knowledge Management, pp. 429-438, 2019.
Philip Wolfe. Convergence conditions for ascent methods. SIAM review, 11(2):226-22 235, 1969.
Philip Wolfe. Convergence conditions for ascent methods. ii: Some corrections. SIAM review, 13 (2):185-188, 1971.
Fan Wu, Yunhui Long, Ce Zhang, and Bo Li. Linkteller: Recovering private edges from graph neural networks via influence analysis. In Symposium on Security and Privacy (SP), 2022.
Yinjun Wu, Edgar Dobriban, and Susan Davidson. Deltagrad: Rapid retraining of machine learning models. In International Conference on Machine Learning, pp. 10355-10366, 2020.
Keyulu Xu, Weihua Hu, Jure Leskovee, and Stefanic Jegelka. How powerful are graph neural networks? In International Conference Learning Representations, 2019.
Zhilin Yang, William Cohen, and Ruslan Salakhudinov. Revisiting semi-supervised learning with graph embeddings. In International conference on machine learming, pp. 40-48, 2016.
Chuxu Zhang. Dongjin Song, Chao Huang, Ananthram Swami, and Nitesh V Chawla. Heteroge- neous graph neural network. Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 793-803, 2019.
15

---

Under review as a conference paper at ICLR 2023
Dataset
#. Features
Nodes
#. Edges
#. Classes
Min Degree
Max Degree
Avg. Degree
Cora
1,433
2,708
5,429
7
198
21.82
CiteSeer
3,703
3,327
4,552
126
13.83
CS
6,805
18,333
163,788
15
262
36.43
Table 5: Description of datasets
A APPENDIX
A.1
PROOF OF THEOREM 2
Proof. For simplicity, first define
R,O,V,
Σ VEV
v(0,v,
(13)
Then, formulate GNN learning process
fn arg min
R(0, V. E). VV
(14)
Since removing edges can be considered as perturbing the input, we introduce Eqn 9,
0, = arg min 0
L(0;e, E) +E Σ
E(Et)-- Σ
L(O
DEV
BEVROL
vEVRUL
arg min
R V. E) + ER((, V EvE)) cR(0, VELL, E).
(15)
IV
We note necessary condition is that the gradient of Eqn 15 at O, is zero. Then, we have
Voli(O,, V, E) + eVoR(0er VEL E EvL) - eVoRl(0e VEOL. E).
(16)
Next, we apply Taylor series at fOR and we get
0 1 +
V VOROO V, VoR(OO VELL EvE,1. VnR(OOR, VFu., E)
V
R(OOR V. E) + c ViROOO VEALS E Eun.) - V3 VEL. F7) (0. 0OR),
(17)
where we have dropped offOR 0.) for approximation. Then Eqn (17) is a linear system of Fut. the influence of EUL. Since fOR the minimum of Eqn (14), have M VR(OOR, V, E) As
e is a small value, we drop the two o(e) terms and have the following:
[V] R(HOR. V, (..
(on) te (0. R(RORR, VEn, E\EuL) VooR)o VEa. E)) = 0. (18)
Suppose Eqn (14) is convex, then
V2R(OOR, V,E) (VoR(OOR, V.E)) VELL. ExE.n.) V VoR(OOR, VELL E)) (19)
0, - FOR ~
Denote
d(0. 0OR)
TFUL
-- (VoR(OOn, VELL E EVE.). VoR(OOR, VELL E)) (20)
de
r=0
DOR
where HOR = 22 Vl EvEy L(Hon,v. v. E).
16

---

Under review as a conference paper at ICLR 2023
Sequential unlearning
Single-batch unlearning
B1
B2
B3
B1
Retrain
0.7795
0.7758
0.7811 1
0.7797
0.7793
EraEdge
0.7791
0.7786
0.7790
0.7793
0.7792
Table 6: Target model accuracy under single-batch and sequential unlearning (GCN+Cora).
A.2 ADDITIONAL DETAILS OF EXPERIMENTAL SETUP
Description of datasets. Table 5 summarizes the statistical information of the three graph datasets (Cora, Citeseer, and CS) we used in the experiments. Cora and Citeseer datasets are citation graphs, while CS dataset is co-author graph.
Additional details of model setup. To ensure fair comparison between the retrained and unlearned models,
the same model size (i.e., same number of layers and number of neurons) for both retraining and unlearned models. All GNN models are trained with a learning rate of 0.001. We train the models by 1,000 epochs, with the carly-stopping condition as that the validation loss does not decrease for 20 epochs.
A.3 ADDITIONAL PERFORMANCE RESULTS
Model efficiency. Figure 4 presents the model efficiency results on the three datasets. We observe that EraEdge significantly faster than retraining. For example, EraEdge outperforms by 9.95x, x, 5.41 69.36x, and 3.12x CS dataset respectively over retraining (Figure (c), (f), (i), and (I)).
Model accuracy. Figure presents the results of model accuracy for all settings. First, the accuracy of the target model by EraEdge is very close to that by the retrained model. In particular, the average difference in model accuracy between retrained and unlearned models are in the range of [0.11%, 0.68%], [0.02%, 0.74%), [0.06% 0.65%] and [0.07%, 1.00%] for GCN, GAT, GraphSAGE, and GIN on Cora, [0.01 %. 0.71% 771%), J. (0.05%, 0.44%, [0.05%, 0.65%], and [0.02%, 1 1.25%] on CiteSeer, and [0.02%, 0.22%] [0.01 %, 0.20%. [0.05%, 0.23%), and [0.01 %. 0.22%] Furthermore, the model accuracy of the unlearned model stays close to that of the retrained model, regardless of the number of removed edges. This demonstrates that EraEdge can handle the removal of large number of edges.
CS, respectively.
A.4 SEQUENTIAL UNLEARNING (NEW)
So far we only considered deleting of one batch of edges. In practice, there can be multiple batch deletion requests to forget the edges in a sequential fashion. Next, we focus on the scenario where multiple edge batches removed sequentially. Specifically, we divide the to-be-removed EvL into h > disjoint batches {B,) with each batch consisting of the same number of edges. For each batch B, (1 < < k 1), consider the target model obtained from retraining/unleamiing of the previous batch B as the original model fOR, and update foR by removing B, (either by retraining unlearning). We evaluate the target model accuracy under sequential unlearning and compare it with that under one-batch unlearning.
We consider l: = 4, and reports the target model accuracy for deleting FUl in one batch and deleting EUL in k 4 batches in Table 6. We also report the target model accuracy of the retrained and unlearned models at each batch. We observe that, first, the accuracy of the unlearned model remains close to the retrained model at each batch during sequential removals. Second, the performance of the unlearned model after removing & batches stays close to that of the model after mongle-batch, unlearning. These results demonstrate that EraEdge can handle sequential deletion of multiple batches of edges.
A.5 UNLEARNING WITH NODE FEATURES (NEW)
In Section we mainly considered the node features that are randomly initialized to eliminate the possible dominant impact of node features model performance. Next, we evaluate the perfor-
17

---

Under review as a conference paper at ICLR 2023
Retrain
EraEdge
GCN
unggning ling (OCO01T1
Number sturkcamed
415
Member urleetted enipes
Namber of unsames edgea
(a) Cora
(b) CiteSecr
(C) CS
GAT
Lior lie beordg
VWlee 190 tee sponng
900
800
1000
1000
2030
4002
6000
6000
30000
Sturdeamed edgne
sturleamed edgee
edgss
Cora
(e) CiteSeer
(f) CS
SAGE
Uncomrg One Sac0tre)
Unkommine tire teceeds)
12
Number
100
200
438
800
600
1000
2000 4002
Number entamed
(g) Cora
(h) CiteSeer
(i) CS
GIN
Urlearang Lnd Dicuree
L.0
1 jue (acores
3.6
ospes
esges
Number ofunleamed edges
Cora
(k) CiteSeer
(I) CS
Figure 4: Unlearning efficiency. The results show that EraEdge speeds up the training time sig- nificantly compared with retraining.
18

---

Under review as a conference paper at ICLR 2023
Retrain
EraEdge
GCN
3.00
3.58
25.80
0.320
3.57
3.55
3.54
1006
2006
6990
6930
3000
1990
Numberot of unfcamed odges
Namberr uiiesmed edges
(a) Cora
(b) CiteSeer
(c) CS
GAT
0.300
3.4
2.58
4768
2.45
0.56
1030
20
203
623
630
300
Z00
C231
193)
1990
Numberra uidesmeed Edges
(d) Cora
(e) CiteSeer
(f) CS
GraphSAGE
3.64
6.370
11.60
24.820
0.78
2.59
2.08
6.3500
0.56
0.55
1006
2006
6093
1990
Numberof of unfcammd odgea
Nurrbe of undecamed odgaa
(g) Cora
(h) CiteSeer
(i) CS
GIN
6.8755
0.19
0.18
3..00
9919
2.50
0.3000
3.56
6.666
150
AU2
200
1000
110
215
400
603
10.0
Kunbeer LElONTEE
(i) Cora
(k) CiteSeer
(I) CS
Figure 5: Accuracy of the target GNN model after retraining/unlearning. The results show that
EraEdge still maintains a competitive model accuracy which is close to that of the retraining model.
19

---

Under review as a conference paper at ICLR 2023
Retrain
EraEdge
Retrain+NF
EraEdge+
0.88
Model accuracy
0.86
0.86
0.84
0.84
Model
0.82
0.82
200
Number of unlearned edges
Number of unlearned edges
(a) GCN
(b) GAT
Figure 6: Comparison of target model accuracy for unlearning with and without the original node features (Cora). "XX+NF" indicates the model that considers the original node features.
mance of EraEdge that uses the original node features. Figure 6 reports the target model accuracy of the unlearned model that is trained with or without the node features. We have the following main observations. First, the target model accuracy improves significantly by considering the origi- nal node features. This shows that the node features have dominant importance on the target model performance in this setting. However, the target model accuracy of the unlearned model still stays close to that of the retrained model. In other words, EraEdge still can make GNNs forget the edges effectively even when node features have dominant importance the graph structure model performance.
20


Reviews:
[{"review_id": "iAjBXAQ30p", "reviewer": "Reviewer_UL7T", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "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 authors study the machine unlearning problem on graphs, where they focus on the edge unlearning problem. The proposed method, EraEdge, is based on subtracting the *influence* of the unlearned edges in a heuristic manner. The experiments demonstrate the efficiency and accuracy of the proposed method. They also show that the output of the unlearned model is close to the one retraining from scratch.", "summary_of_the_review": "My major concern focuses on how private the proposed unlearning method is. I also think the authors should specify the difference between exact and approximate unlearning, otherwise the result can be misleading. For example, EraEdge is an approximate unlearning method while retraining from scratch is an exact unlearning method. Once we specify this difference, one can naturally ask how EraEdge *trade-off* privacy for time complexity and test accuracy. I also find the experiment setting a bit weird, where the authors replace the default node features with random Gaussian vectors. This is an artificial setting, and I wonder how the result looks like if the authors use default node features. In summary, I feel the paper needs a major revision before publishing.", "strength_and_weaknesses": "### Strengths\n\n- EraEdge can be applied to non-linear models such as GNNs.\n\n- The methods seem to be efficient in terms of time complexity.\n\n- The problem of machine unlearning on graphs is an important problem.\n\n### Weaknesses\n\n- The proposed unlearning definition is not rigorous and heuristic-based. Also, having approximately close model output does not guarantee privacy.\n\n- The proposed method is an ***approximate unlearning*** method ***without theoretical guarantee*** (i.e. heuristic based). \n\n- The related works about machine unlearning on graphs are not extensive enough. Also, differential privacy based GNNs should also be discussed.\n\n- In the experiment, the authors use random Gaussian vectors as node features instead of the default features. How does the result look like if we use the default features?\n\n- (Minor) The paper focuses on the edge unlearning problem, while the really important problem is the node unlearning problem.\n\n### Detail comments\n\nWhile the problem of machine unlearning on graphs is very important, one should be extremely careful when they claim a method can achieve unlearning. Machine unlearning can be roughly characterized into two categories, exact and approximate unlearning. For exact unlearning methods, we require the unlearned models to be ***identical*** (in distribution) to the one retraining from scratch, examples include sharding-based method as mentioned by the authors. Approximate unlearning requires the unlearned model to be *indistinguishable* from the one retraining from scratch. Note that one should be extremely careful when defining the *indistinguishability*, as an inappropriate definition could lead to zero privacy in some cases (see [1] for a simple example). Apparently, the proposed definition of unlearning belongs to approximate unlearning and the authors should clearly specify it. Otherwise, the paper can be misleading to the readers.\n\nOne rigorous definition of approximate unlearning is via differential privacy type of definition in the parameter space, which was proposed in [1]. The proposed approximate unlearning method therein comes with a differential privacy type of theoretical guarantee. The other line of work such as [2] proposed a heuristic-based measure, which is more similar to the one proposed in this paper. However, the proposed method in [2] involves ***privacy noise*** to *blur out* the potentially leaked information. In contrast, EraEdge does not add any privacy noise to protect the privacy. Most importantly, the authors of [2] conduct extensive experiments and multiple metrics to examine the effectiveness of unlearning their method. On the other hand, the authors of this paper merely examine the closeness of the model output which can be problematic following the same rationale in the counterexample provided in [1] (i.e. the paragraph in the title *Insufficiency of parametric indistinguishability*). Hence, I doubt how private it is for EraEdge on the unlearned data. I would suggest the authors conduct similar extensive experiments to [2], or examine the ability of the proposed method against some membership inference attack methods.\n\nRegarding the related works, the authors miss several recent papers about machine unlearning on graphs. Please check the survey paper [3] for a collection of papers about machine unlearning on graphs, where the node unlearning problem is also studied. It is also worth mentioning the recent development of differential private GNNs, as differential private models automatically achieve (approximate) unlearning *without* any update [1].\n\nIn summary, my main concern about the paper is the privacy of the proposed method. Since EraEdge is not an exact unlearning approach, one has to be extremely careful about the choice of *indistinguishability*. Also, most of the existing approximate machine unlearning methods require adding privacy noise to burr out the information from the approximation error. However, EraEdge does not leverage any privacy noise and thus any approximate error can potentially lead to severe privacy issues (i.e. adversarial attacks). In the empirical evaluation, the authors do not conduct enough experiments to demonstrate the privacy of their EraEdge. This should be done for heuristic-based methods such as those in [2]. Hence, I feel the paper needs a major revision before publishing.\n\n### References\n\n[1] Certified data removal from machine learning models, Guo et al., ICML 2020.\n\n[2] Eternal Sunshine of the Spotless Net: Selective Forgetting in Deep Networks, Golatkar et al., CVPR 2020.\n\n[3] A Survey of Machine Unlearning, Nguyen et al., 2022.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "1: The main claims of the paper are incorrect or not at all supported by theory or empirical results.", "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": "cSPjEvwlO8X", "reviewer": "Reviewer_wUNT", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This work studies a notion of unlearning for graph neural networks. Basically, given a set of edges removed from the graph, it tries to address how to fast adjust the model parameters to make the model behave like the model retrained on the graph with edge removal while without retraining. The technical idea is to analyze the influence of the edge removal on the model parameters given the convex and differentiable assumption of the objective. Experiments show some superiority of the proposed method. ", "summary_of_the_review": "The studied problem is interesting. The adopted technique is reasonable. However, the novelty and true technical contributions are not sufficient given previous works.", "strength_and_weaknesses": "Strengthes:\n1. Graph unlearning is a relatively novel concept. The problem studies here is interesting. Also, the analysis and argument sound reasonable and solid. \n\n2. The paper is written very well. I appreciate the logic flow. The motivation and the exposition of the approach is clear. \n\nWeaknesses:\n1. Here is my biggest concern. Although I overall think the technique in this paper is reasonable and the studied problem is interesting. Unfortunately, recently, I have read a relevant paper on graph unlearning published four months ago [1], which I think has studies a far more extensive setting on graph unlearning than this work. Although that work is just an arxiv paper, I cannot view it as a concurrent work because the content studied in [1], in my opinion, is broader and provides more insights than the setting studied in this work. I know it is tough for the authors but I cannot ignore this. Therefore, this work's statement saying this is the only work that considers unlearning in GNN, which is an over-claiming. \n\nMoreover, [1] studies both node and edge unlearning, while this work only studies edge unlearning. In my opinion, node unlearning is more crucial because a user (typically corresponding to a node), if not wanting to disclose her data, will ask to remove this node from the graph. Moreover, I think [1] also tells more data insights due to their analytic bounds such as the dependence of unlearning performance on node degrees, etc. \n\nI can see some adopted detailed techniques are different, such as [1] using SGC (linear model) while this paper using convex assumptions. My feeling is that if this work may discuss both edge/node unlearning and also provides further insights on how graph structure affects the unlearning performance, I would appreciate the technical difference in this paper and may support an acceptance. However, the current setting of this paper is still kind of narrow compared to [1].\n\n2. This work writes well and is easy to follow. However, I feel there is a little bit misleading in the introduction. For example, after reading the introduction, I thought the paper would like to touch non-convex settings in theory (the fourth paragraph of intro). However, the later analysis is based on convex assumption. Moreover, in intro, the authors say \"empirical studies on tradeoff between unlearning efficiency, accuracy, unlearning efficacy\". However, in the experiments, I can only see the list of these results without tradeoff. My understanding of the tradeoff would be about, e.g., high accuracy/efficacy  requires less efficiency, and the proposed method has a work to balance these aspects. Unfortunately, I do not think the proposed approach has such flexibility. \n\n3. Moreover, I am not clear how the averaged JSD is computed. I can think of there are multiple ways to define averaged JSD. Do you mean averaging over testing samples? or averaging over classes? I think a math equation is needed to show this. \n\n4. Fig.4 the first row has wrong subtitles I think. \n\n5. Regarding experiments, how do you remove edges, randomly and how many times, or? Also, I do not see how to tune the model and how to make sure the comparison between model retraining and the proposed method fair, e.g., same model size? how about learning rate?\n\n6. Since efficiency is one topic of interest in this work, the used graphs are in general too small.  \n\n\n\n[1] Certified Graph Unlearning, Chien et al., 2022. ", "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": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "5g17Ys3Icu", "reviewer": "Reviewer_TMqC", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies machine unlearning on graph neural networks (GNNs) by analyzing influence function. The authors identify that simply applying influence function on GNNs for edge removal is problematic due to node dependency. As such, the authors propose to estimate the influence function by upweighting the set of all affected nodes. Then the influence is obtained as the reverse of Hessian matrix multiplied by the gradient vector. And conjugate gradient is applied to reduce the computational cost. Experimental results demonstrate the effectiveness of the proposed EraEdge in terms of the indistinguishability betweem model parameters and the efficiency of the proposed EraEdge in terms of running time.", "summary_of_the_review": "While the paper is novel in terms of its technical aspect, I have a few concerns on the technical details on the privacy of this unlearning approach. In terms of writing, the paper is clear and easy to follow. ", "strength_and_weaknesses": "Strengths:\n- Unlearning on GNNs is less studied, and there is no existing works on influence function-based GNN unlearning.\n- The paper is overall easy to follow.\n- The experimental results demonstrate that EraEdge can efficiently unlearn a set of edges via the indistinguishability between the retrained model parameters and the unlearned model parameters.\n\nConcerns/Questions:\n- Many existing influence function-based approximate unlearning techniques (see references below) add Gaussian noises to preserve data privacy. I am wondering why such noise is not needed in EraEdge for data privacy?\n[1] https://arxiv.org/abs/1911.04933\n[2] https://arxiv.org/abs/1911.03030\n[3] https://arxiv.org/abs/2106.04378 \n[4] https://arxiv.org/abs/2006.14755\n[5] https://arxiv.org/abs/2007.02923\n[6] https://arxiv.org/abs/2012.13431\n[7] https://arxiv.org/abs/2110.11891\n[8] https://arxiv.org/abs/2103.03279\n- Existing works often solve Eq. (10)-like equation with Hessian-vector product (HVP). What is the key limitation of using HVP to solve Eq. (10)? If HVP can be used as well, what is the benefit of conjugate gradient over HVP?\n- I doubt that the indistinguishability in the GNN output necessarily mean the data is removed. Similar concern also appear in (Guo et al. 2020) even for linear and convex classifier like logistic regression, not to mention the nonconvexity of GNNs. It is better to study the privacy of this data removal mechanism like how they are studied in differential privacy (e.g., through membership inference attack).\n- How would EraEdge perform when we sequantially delete multiple batches of edges? In many real-world scenarios, it is uncommon that the model will be only unlearned once.", "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": "2mbgWwbHnV", "reviewer": "Reviewer_yNN2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "An unlearning algorithm for graph neural networks is proposed in the paper. The paper tries to find the difference between the upweighted model and the original model by utilizing a hessian-based approximation, which can be solved by investigating the corresponding linear system with conjugate gradient methods. The found difference is then added to the original model to obtain the retrained parameters.", "summary_of_the_review": "In general, the studied problem is interesting and important. In addition, the methodology is principled with three major merits as discussed above. However, the work still has some unaddressed concerns to well justify its technical and empirical contributions.", "strength_and_weaknesses": "Strength\n\n1. The proposed method has a good applicability and can work with most existing variants of GNNs.\n\n2. The paper is a computationally and memory efficient algorithm.\n\n3. The algorithm is evaluated on a number of three real datasets to demonstrate the effectiveness of the proposed approach for graph unlearning.\n\nWeakness\n\n1. Upweighting using the influence function merely approximates the retrained parameters and provides no theoretical error bound on non-convex loss functions. This work then constructs another approximation of this already fuzzy target to obtain the unlearnt model. One can hardly be convinced that such a method will result in a set of parameters that resemble the retrained model. The proposed scheme also provides no means of generating a verification of data removal, which is utterly vital for a data provider.\n\n2. Adding a scaled identity matrix to the hessian to make it positive definite only accounts for the non-invertible problem. It still destroys the basis of Theorem 2, which requires the loss function to be globally convex. This assumption is too strong to make any meaningful sense in real-world scenarios. Also, Theorem 2 seems to be only an adaptation in notations of eq.(3) in [1].\n\n3. In scenarios where the graph is relatively dense and the GCN is deep (e.g., as described in [2]), the affected set of nodes, as defined in the paper, can easily become the whole graph, which sort of destroys the purpose of the paper, which is fast unlearning.\n\n4. Unlearning efficacy is only evaluated for the proposed model without comparison with other baselines, unlike classification accuracy. Also, experiments like the behavior difference between the unlearning model and the retrained model on the unlearned part of the dataset should be added to demonstrate the algorithm's efficacy further.\n\n[1] Pang Wei Koh and Percy Liang. “Understanding Black-box Predictions via Influence Functions.” In: Proceedings of the 34th International Conference on Machine Learning, ICML 2017, Sydney, NSW, Australia, 6-11 August 2017. Ed. by Doina Precup and Yee Whye Teh. Vol. 70. Proceedings of Machine Learning Research. PMLR, 2017, pp. 1885–1894.\n\n[2] Guohao Li et al. “DeepGCNs: Can GCNs Go As Deep As CNNs?” In: 2019 IEEE/CVF International Conference on Computer Vision, ICCV 2019, Seoul, Korea (South), October 27 - November 2, 2019. IEEE, 2019, pp. 9266–9275.", "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": {}}]

Author rebuttal:

Decision: Reject