Efficient Model Updates for Approximate Unlearning of Graph-Structured Data
Authors: Eli Chien
Chao Pan
Olgica Milenkovic
Venue: ICLR 2023 poster (2023)
Keywords: machine unlearning
graph unlearning
privacy

Abstract: With the adoption of recent laws ensuring the ``right to be forgotten'', the problem of machine unlearning has become of significant importance. This is particularly the case for graph-structured data, and learning tools specialized for such data, including graph neural networks (GNNs). This work introduces the first known approach for \emph{approximate graph unlearning} with provable theoretical guarantees. The challenges in addressing the problem are two-fold. First, there exist multiple different types of unlearning requests that need to be considered, including node feature, edge and node unlearning. Second, to establish provable performance guarantees, one needs to carefully evaluate the process of feature mixing during propagation. We focus on analyzing Simple Graph Convolutions (SGC) and their generalized PageRank (GPR) extensions, thereby laying the theoretical foundations for unlearning GNNs. Empirical evaluations of six benchmark datasets demonstrate excellent performance/complexity/privacy trade-offs of our approach compared to complete retraining and general methods that do not leverage graph information. For example, unlearning $200$ out of $1208$ training nodes of the Cora dataset only leads to a $0.1\%$ loss in test accuracy, but offers a $4$-fold speed-up compared to complete retraining with a $(\epsilon,\delta)=(1,10^{-4})$ ``privacy cost''. We also exhibit a $12\%$ increase in test accuracy for the same dataset when compared to unlearning methods that do not leverage graph information, with comparable time complexity and the same privacy guarantee.

Published as a conference paper at ICLR 2023
EFFICIENT MODEL UPDATES FOR APPROXIMATE UN- LEARNING OF GRAPH-STRUCTURED DATA
Eli Chien"
Chao Pan" Olgica Milenkovic
Department of Electrical and Computer Engineering
University of Illinois, Kirbana-hhappal fichien3, chaopan2, mi lenkov www.leiis.iineee..
ABSTRACT
With the udoption of recent laws ensuring the "right to be forgotten", the problem of machine unlearning has become of significant importance. This is particularly the case for graph-structure data, and learning tools specialized for such data, including graph neural networks (GNNs). This work introduces the first known approach for approximate graph unlearning with provable theoretical guarantees. The challenges addressing the problem are two-fold. First, there exist multiple different types of unlearning requests that need be considered, including node feature, edge and node unlearning. Second, to establish provable performance guarantees, needs to carefully evaluate the process of feature mixing dur- ing propagation. We focus on analyzing Simple Graph Convolutions (SGC) and their generalized PageRank (GPR) extensions, thereby laying the theoretical foun- dations for unlearning GNNs. Empirical evaluations of six benchmark datasets demonstrate excellent perorrnaccecompleexty/pivaaaaa compared to complete retraining and general methods that do not leverage graph information. For example, unlearning 200 out of 1208 training nodes of the Cora dataset only leads to a 0.1% loss in test accuracy, but offers 4-fold speed-up compared to complete retraining with a (e, 5) = (1, 10-4) "privacy cost". We also exhibit 12% increase in test accuracy for the same dataset when compared to unlcarning methods that do not leverage graph information, with comparable time complexity and the same privacy guarantee. Our code is available online"]
trade-off's of our approach
INTRODUCTION
Machine learning algorithms are used in many application domains, including biology, computer vision and natural language processing. Relevant models are often trained either on third-party datasets, internal or customized subsets of publicly available user data. For example, many computer vision models are trained on images from Flickr users (Thomee et al.) 2016)) Guo et al., (020) while many natural language processing (e.g.. sentiment analysis) and recommender systems heavily rely on repositories such as IMDB (Maas et al.) 2011). Furthermore, numerous MI. classifiers in computational biology trained data from the UK Biobank (Sudlow et al. 2015). which represents a collection genetic and medical records of roughly half million participants (Ginart et al. 2019). With recent demands for increased data privacy, the above referenced and many other data repositories are facing increasing demands for data removal. Certain laws are already in place guaranteeing the rights of certified data removal, including the European Union's 's General Data Protection Regulation (GDPR), the California Consumer Privacy Act (CCPA) and the Canadian Consumer Privacy Protection Act (CPPA) (Sekhari et al. 2021).
Removing user data from a dataset is insufficient to guarantee the desired level of privacy, since models trained on the original data may still contain information about their patterns and features. This consideration gave rise to new research direction in machine learning, referred to as machine unlearning (Cao Yang 2015), in which the goal is to guarantee that the user data information is also removed from the trained model. Naively, one can retrain the model from scratch to meet
Equul contribution.

---

Published as a conference paper at ICLR 2023
Original graph
Node feature unlearning
Edge unlearning
Node unlearming
Unstructured unlearning
Figure 1: Illustaation of three different types of approximate graph unlearning problems and com- parison with the case of unlearning without graph information (Guo et al. 2020). The colors of the nodes capture properties of node features, and the red frame indicates node embeddings affected by 1-hop propagation. When graph information is used, the node embeddings are uncorrelated. However, for the case of graph unlearning problems, removing one node or edge can affect the node embeddings of the entire graph for large enough number of propagation steps.
the privacy demand, yet retraining comes at high computation cost and is thus not practical when accommodating frequent removal requests. To avoid complete retraining, various methods for ma- chine unlearning have been proposed, including exact approaches (Ginart et al. 2019; Bourtoule cct al. 202I) as well as approximate methods (Guo et al., 2020 Sckhari et al. 2021).
At the same time, graph-centered machine learning has received significant interest from the learning community due to the ubiquity of graph hepph-strutture data. Usually, the data contains two sources of information: Node features and graph topology. Graph Neural Networks (GNN) leverage both types of information simultaneously and achieve sate--of-the-al performance in numerous real-world ap- plications, including Google Maps (Derrow- Pinion al. [2021) various recommender system (Ying) et al. 2018). self-driving cars (Gao et al. (2020) and bioinformatics (Zhang et al., 2021b). Clearly, user data is involved in training the underlying GNNs and may therefore be subject to removal. However, it is still unclear how to perform unlearning of GNNs.
We take the first step towards solving the approximate unlearning problem by performing nontrivial theoretical analysis of some simplified GNN architectures. Inspired by the unstructured data certified removal procedure (Guo al., 2020), we propose the first known approach for approximate graph unlearning. Our main contributions are as follows. First, we introduce three types of data removal requests for graph unlearning: Node feature unlearning, edge unlearning and node unlearning (see Figure []]. Second, derive theoretical guarantees for approximate graph unlearning mechanisms for all three removal cases on SGC (Wu et al., 2019) and their GPR gencralizations. In particular, analyze L--regularized graph models trained with differentiable convex loss functions. The analysis is challenging since propagation on graphs "mixes" node features. Our analysis reveals that the degree of the unlearned node plays important role in the unlearning process, while the number of propagation steps may or may not be important for different unlearning scenarios. To the best of our knowledge, the theoretical guarantees established in this work the first provable approximate unlearning studies for graphs. Furthermore, the proposed analysis also encompasses node classification and node regression problems. Third, our empirical investigation on frequently used datasets for GNN learning shows that our method offers an excellent performance-comples privacy trade-off. For example, when unlearning 200 out of 1208 training nodes of the Cora dataset, our method offers comparable test accuracy complete retraining, but offers 4-fold speed-up with a (e, = (1, 10-4) "privacy cost", We also test our model on datasets for which removal requests are most likely to arise, including Amazon co-purchase networks.
Due to space limitations, all proofs and some detailed discussions are relegated to the Appendix.
2 RELATED WORKS
Machine unlearning and certified data removal. Cao & Yang 2015) machine unlearning and proposed distributed learners for exact unlearning, Bourtoule et al. (2021) introduced sharding-based methods for unlearning, while Ginart et al. (2019) described unlearning approaches for k-means clustering. These works focused on exact unlearning: The unlearned model is required to perform identically to completely retrained model. As an alternative, Guo et al. (2020) introduced a probabilistic definition of unlearning motivated by differential privacy (Dwork) 20111. Sekhari al. (022) studied the generalization performance of machine unlearning methods.
introduced the concept of
2

---

Published as a conference paper at ICLR 2023
Golatkar et al. (2020) proposed heuristic-based selective forgetting in deep networks. These prob- abilistic approaches naturally allow for "approximate" unlearning. None of these works addressed the machine unlearning problem graphs. To the best of our knowledge, the only work in this direction is GraphEraser (Chen et al. 2021). However, the strategy proposed therein uses sharding, which only works for exact unlearning and is hence completely different from our approximate ap- proach. Also, the approach in Chen et al. (202I) relies on partitioning the graph using community detection methods. It therefore implicitly makes the assumption that the graph is homophilic which is not warranted in practice (Chien et al., 2021b Lim et al. (02T). In contrast, our method works for arbitrary graphs and allows for approximate unlearning while ensuring excellent trade-offs among performance, privacy and complexity.
Differential privacy (DP) and DP-GNNs. Machine unlearning, especially the approximation ver- sion described in Guo et al. (2020), is closely related to differential privacy (Dwork) (011). In fact, differential privacy is a sufficient condition for machine unlearning. If a model is differentially private, then the adversary cannot distinguish whether the model is trained on the original dataset or on a dataset which one data point is removed. Hence, even without model updating, a DP model will automatically unlearn the removed data point (see also the explanation in (Ginart al., 2019 Sekkhari et al., (202T) and Figure 4. Although DP is a sufficient condition for unlearning, it not necessary condition. Also, most of the DP models suffer from significant degradation in performance even when the privacy constraint is loose (Chaudhuri et al. 2011 Abadi et al.] (0166). Machine unlearning can therefore be viewed means to trade-off between performance and com- putational cost, with complete retraining and DP on two different ends of the spectrum (Guo et al.,
2020). Several recent works proposed DP-GNNs (Daigavane al. 202T; Olatunji et al.) [202 la Wu et al. 20211 (ajaadmanesh et al. 2022) however, even for unlearning one single node or edge, these methods require a high "privacy cost" (c 2 5) to learn with sufficient accuracy.
Graph neural networks. While GNNs are successfully used for many graph-related problems, accompanying theoretical analyses are usually difficult due to the combination of nonlinear feature transformation and graph propagation. Recently, several simplified GNN models were proposed that can further the theoretical understanding of their performance and scalability. SGCs (Wu et al.) 2019) simplify Graph Convolutional Networks (GCNs) (Kipf & Welling, 2017) via lincarization (i.e., through the removal of all nonlinearities): although SGC in general underperforms compared to otate-of-the-art GNNs, they still offer competitive performance on many datasets. The analy- sis of SGCs elucidated the relationship between low-pass graph filtering and GCNs which reveals both advantages and potential limitations of GNNs. The GPR generalization of SGC is closely related to many important models that resolve different issues inherent to GNNs. For example, GPRGNN (Chien et al., 202 addresses the problem of universal learning on homophilic and het- erophilic graph datasets and the issue of over-smoothing. SIGN (Frasca et al. 2020) based graph models and S2GC (Zhu & Koniusz 2020) allow for arbitrary sized mini- bini-batch training, which im- proves the scalability and leads to further performance improvements of methods (Sun et al. 2021 Zhang et al. 2202 la] Chien et al. (2022a) on the Open Graph Benchmark leaderboard Hu et al. (020)) Hence, developing approximate graph unlearning approaches for SGC and generalizations thereof not only of theoretical interest, but also of practical importance.
PRELIMINARIES
Notation. We reserve bold-font capital letters such as S for matrices and bold-font lowercase letters such for vectors. We use to denote the 7th standard basis, so that e. S and Se, represent the 7th row and column vector of S, respectively. The absolute value | is applied component-wist on both matrices and vectors. We also use the symbols for the all-one vector and I for the identity matrix. Furthermore, we let G = (V,E) stand for an undirected graph with node set V [r]] of size n and edge set ε. The symbols A and D are used to denote the corresponding adjacency and node degree matrix, respectively. The feature matrix is denoted by X E RaxF and the features have dimension F; For binary classification, the label are summarized in Y E {-1, while the nonbinary case is discussed in Section 5 The relevant norms are || II. the la norm, and || l|.. the Frobenius norm. Note that we use || [T for both row and column vectors to simplify the notation. The matrices A and D should not be confused with the symbols for algorithm A and dataset D.
3

---

Published as a conference paper at ICLR 2023
Certified removal. Let A be (randomized) learning algorithm that trains D, the set of data points before removal, and outputs a model h E H. where H. represents a chosen space of models. The removal of subset of points from D results in D'. For instance, let D = (X. Y). Suppose want to remove a data point, (ef X. Y) from DD resulting in D' = (X', Y'). Here, X', Y' are equal X, Y, respectively, except that the row corresponding to the removed data point is deleted. Given e > 0, an unicarming algorithm M applied to A(D) is said to guarantee an (c, d--ertiffee and X denotes the space of possible datasets, if
removal for A, where e,
VT H. & E [m]] : P (A((E)) D, D \ D') E T) S exp(e) (A(D') E (T)+
PP (A((D) E T) S (M D, D D' +
(I)
This definition is related to (e, 6)-DP Dwork 2011) except that we are allowed to update the model
based on the removed point (see Figure 4. An (e, 6) ceettifie removal method guarantees that the updated model M (A(D). D, D D') is approximately" the same as the model A(D") obtained by
retraining from scratch. Thus, any information about the removed data D \ D'' is "approximately" eliminated from the model. Ideally, we would like to design M such that it satisfies equation |I and has a complexity that is significantly smaller than that of complete retraining.
APPROXIMATE GRAPH UNLEARNING WITH THEORETICAL GUARANTEES
Unlike standard machine unlearning, approximate graph unlearning uses datasets that contain not only node features X but also the graph topology A, and therefore require different data removal pro- cedures. We focus on node classification, for which the training dataset equals D (X, Y A). Here, Yr. is identical to Y on rows indexed by points of the training set T, while the remaining rows all zeros. Without loss of generality, we assume that the training set comprises the first m nodes (i.e. T. = [m]) where m S n. An unlearning method M achieves (c, 8) -approoximaee graph unlearning with algorithm A if equation [ is satisfied for D (X, YT,: A) and D', which differ based on the type of requests: Node feature unlearning, edge unlearning, and node unlearning.
4.1 UNLEARNING SGC AND COMPARISON WITH UNSTRUCTURED UNLEARNING
SGC is a simplification of GCN obtained by removing all nonlinearities from the latter model. This leads to the following update rule: p XW A ZW, where W denotes the matrix of learnable weights. K 2 0 equals the number of propagation steps and P denotes the one-step propagation matrix. The standard choice of the propagation matrix is the symmetric normalized adjacency matrix with self- P 11/ AD-1/2, where À A+I and D equals the degree matrix with respect A. We will work with the asymmetric normalized version P. D A. This choice made purely for analytical purposes and our empirical results confirm that this normalization ensures the competitive performance of our unlearning methods.
The resulting node embedding is used for node classification by choosing appropriate loss (i.e., logistic loss) and minimizing the Le-regularized empirical risk. For binary classification, W can be replaced by vector w; the loss equals L(w, D) EieTy,, (f(e?" Zw, e Yr.) >/llll))) where f(e Zw, e: Yr,) is convex loss function that is differentiable everywhere. We also write w* = A(D)= arg min L(w, D), where the optimizer unique whenever À > 0.
We start with a high-level description of the approximate unstructured unlearning approach intro- duced in Guo et al. (2020). Note that "certified removal" in the context of the former work refers to approximate unlearning that provably satisfies (I). Let us denote the Hessian of L(: D') at w by Hw V2 VZL(w":D" DD). The authors of Guo et al. (0200) propose the following mecha- nism for unlearning the mh training point: w =M (M(w" (w" D,D DD) = w* + H A Auo- where Aguo Aw* + Vi(ee" Xw* e Y.,). When VL(W , D') = then w is the unique optimizer of L(::D),, If VL(ww, D') & O, then information about the removed data point remains present in the model. One can show that the gradient residual norm [V _D)] determines the error of w- when used to approximate the true minimizer of L(:; D') (Guo et al. 2020). Hence, upper bounds on [[V[(w [I can be used establish approximate unlearning guarantees. More pre- cisely, assume that have [V((w D'Ill I é' for some e' O. Furthermore, consider training with the noisy loss Lo(w, D) Exe. Yr, fo (c(e) Xw, drawn randomly according some distribution. Then one leverage the following result.
e YT,) 3 [|l])²) + b" w, where b is
4

---

Published as a conference paper at ICLR 2023
Theorem 4.1 (Theorem 3 from Guo et al. (2200)) Let A be the learning algorithm that returns the unique optimum of the loss Lb w. D). Suppose that L (w ,D')l < é for some computable bound e' > 0 independent b and achieved by M. If (0, (coe' yd) with Cn > 0, then M satisfies with parameters (c, 8) for algorithm A applied to D', where 5 1.5e 1.5e- -
Hence, if we can prove that VL(wT, ,D)ll is appropriately bounded for the graph setting well, then the unlearning mechanism M will ensure (e, -appproximmt graph unlearning. One of the main contributions of Guo al. (2020) is bound the gradient residual norm (V((W, of the proposed unlearning mechanism with Aguo Xw* + "ew"e",,","" e Yr.).
Motivated by the unlearning approach from Guo al. (2020) pertaining to unstructured data, we design an unlearning mechanism for graphs. We generalize their unlearning mechanism by replacing A Ayuo with A VL(w", D) VL(W", DD). As an demonstrative example, for node unlearning we consequently have
A Aw + TW e Yr.) + Σ
Ve(e of YT,) Vi(ee Z'w", .e Yr.)] (2)
E=1
Note that our generalized unlearning mechanism matches that ot Guo et al. (020)) when no graph information is present. This can be seen by setting K 0, which leads to X and c. Z
e? Z' Vi [m--11 1]. Hence, the third term in equation (2) is zero and thus A Aguo- Note that when graph information is present, the third term in equation (2) is, in general, bounded away from zero. This term captures the impact of unlearning node m on remaining training nodes [m - 1), and including effects pertaining to edge and feature removal. This not only highlights the necessity of investigating generalized unlearning mechanisms, but also the main difficulty of extending the analysis of Guo et al.) (2020) to graphs. A more detailed discussion regarding the intuition behind our approach can be found Appendix [A.3 The main technical contribution of our work to establish bounds of the gradient residual norm for all three types of graph unlearning scenarios. For this analysis, we need the loss function é to satisfy the following properties.
Assumption 4.2. For any D, i E [n] and E FRF: (I) [[V (eee(c/Zww,wc Y. S (i.e. the norm of V is c-bounded); (2) 8" is Ly-Liipshit:: (3) leef X|| S 1; (4) ll is 7 Lipschitz; (5) ll is ei ei-bounded.
Assumptions (1)-(3) are also needed for unstructured unlearning of linear classifiers (Guo et al., 2020). To account for graph-structured data, we require additional assumptions (4)-(5) to establish worst-case bounds. The additional assumptions may be avoided when working with data-dependent bounds (Section 55) In all subsequent derivations, we assume that the unlearned data point cor- responds to the mh node for node feature and node unlearning; for edge unlearning, we wish to unlearn the edge (1, m). Generalizations for multiple unlearning requests are discussed in Section
4.2 NODE FEATURE UNLEARNING FOR SGCS
We start with the simplest type of unlearning node feature unlearning for SGCs. In this case, we remove the node feature and label of one node from D, resulting in D = (X', T A). The matrices X', Y/,, are identical to X, YT,, respectively, except for the mh row of the former being set to zero Note that in this case, the graph structure remains unchanged.
Theorem 4.3. Suppose that Assumption 4.2 holds. For the node feature unlearning scenario and = pKy and --1 A, we have
VV(( D')l "')) = [[ H H < 72(2c) + (cn + +Ac1 )
(3)
(4
where Hw,, denotes the Hessian of L(: at = A for some 7) E [0. 1]. A similar conclusion holds for the case when we wish to unlearn node features of node that is not in T,. In this case we just replace D Dmm by the degree of the corresponding node. This result shows that the norm bound is large the unlearned node has a large degree, since large-degres node will affect the values of many rows in Z. Our result also demonstrates that the norm bound is independent of K, due to the fact that P is right stochastic. We provide next a sketch of the proof to illustrate the analytical challenges of graph unlearning compared to those of unstructured data unlearning.
5

---

Published as a conference paper at ICLR 2023
Although for node feature unlearning the graph topology does not change, all rows of Z = P X may potentially change due to graph information propagation. Thus, the original analysis from (Guo et al. 2020), which corresponds to the special case Z X, cannot be applied directly. There are two particular challenges. The first is to ensure that the norm of each row of Z is bounded by 1. We provide Lemma A.1 to guarantee this. It is critical to choose P = D-1A A since all other choices of degree normalization lead to worse bounds (see Appendix A.I.I. The second and more difficult challenge is to bound ||| When Z = X, the third term in equation (2) is exactly zero, in accordance with Guo al. (2020). Due graph propagation, we have further bound the norm of the third term, which is highly nontrivial since the upper bound is not allowed to grow with m or n. We first focus on one of the m -1 terms in the sum. Using Assumption 4.2 one can bound this term by ||e/ (Z Z (we suppressed the dependency on X, C and m for simplicity). The key analytical novelty is to explore the sparsity of Z - Z' = (x--XXX
Note that X X' is an all zero matrix except for its m row being equal c X. Thus, we have lle? (Z-Z')| = lle P (X-X))| ||e Pe Cm em e,,ee X < e."p" em: where the last bound follows from the wise) nonnegative matrix. Thus, summing over E [m 1] leads to the upper bound 1 em
inequality, (3) in Assumption 4.2 and the fact that pK is (component-
K
since m S n. Next, observe that 1 1Pk Cm = 1TPKD 'Dem 1s (D-IA) D D-'c,,, D Dmm=
1 D -1 (AD-1)= K em D mm- Since AD-1 is a left stochastic matrix, AD is a probability
vector whenever is a probability vector. Clearly, em is probability vector. Hence, (AD 1Dbol1KK K)eem is also probability vector. Since all diagonal entries of D-1 are nonnegative and upper bounded 'p
by given the self-loops for all nodes, DnD ' < 1 1mp p
for any probability vector p. Hence, D,mm and does not increase with m
the term above is bounded by D Dmm The bound depends or K. Although node feature unlearning is the simplest case of graph unlearning, our sketch of the proof illustrates the difficulties associated with bounding the third term in A. Similar, but more complicated approaches are needed for the analysis of edge unlearning and node unlearning.
4.3 EDGR AND NODE UNLFARNING FOR SGCS AND GPRS EXTENSIONS
Edge unlearning for SGC. We describe next the bounds for edge unlearning and highlight the technical issues arising in the analysis of this setting. Here, we remove one edge (1, from D, resulting in D' (X, YT, The matrix A' is identical to A except for Aím A 0. Furthermore, D' is the degree matrix corresponding to A'. Note that the node features and labels remain unchanged.
Theorem 4.4. Suppose that Assumption 4.2 holds. Under the edge unlearning scenario, and for
P P= P-D-1A Å and Z = PKX, we have
16 (en caa)
[ = (HW,, H. H.
(4)
X4m
Similar to what holds for the node feature unlearning case, Theorem 4.4 still holds when neither of the two end nodes of the removed edge belongs to T,,.
Node unlearning for SGC. We now discuss the most difficult case, node unlearning. In this case, one node entirely removed from D. including node features, labels and edges. This results in D' = (X', YY,,, A'). The matrices X', YY,, are defined similarly to those described for node feature unlearning. The matrix A' is obtained by replacing the mhth row and column in A by all- zeros (similar changes introduced in A, with Amm 0). For simplicity, we let D mm 1 as this assumption does not affect the propagation results.
Theorem 4.5. Suppose that Assumption 4.2 holds. For the node unlearning scenario and Z Pk X and P D-1 have
72 (2cx + (c>) + +c 2D mm - 1))
VVL(W D') = ([Hw,, Hw- ) H
(5)
X4 1)
The main challenge arises in the proof of Theorem 4.4 and 4.5 is bounding |||| appropriately. Unlike for the node feature unlearning case, now both graph structure and node features can change

---

Published as a conference paper at ICLR 2023
due to the unlearning request. We establish series of lemmas to characterize the difference between Z and Z', which play important roles in our proofs (see Appendix (a.rndixAAAAlaaa 8.8 and A.9 for complete proofs).
Approximate graph unlearning in GPR-baseds model. Our analysis can be extended to General- ized PageRank (GPR)-based models (Li al., 2019). The definition of GPR is -k=o Og Pk where
S denotes a node feature or node embedding. The learnable weights 0g are called GPR weights and
different choices for the weights lead different propagation rules (Jeh & Widom 2003 Chung 2007]. GPR-type propagations include SGC and APPNP rules as special cases (Chien et al.
2021b
If we use linearly transformed features = XW, for some weight matrix W, the GPR rule can
be rewritten as ZW = K+I [X, P2X, P W. This constitutes a concatenation of
the steps from O up to K. The learnable weight matrix W E (K+FFX combines 02 and W. These represent linearizations of GPR-GNNs (Chien et al., (02 and SIGNs (Frasca et al. 22220), simple yet useful models for learning on graphs. For simplicity, we only describe the results for node feature unlearning and delegate the analysis of edge and node unlearning Appendix Aopendix[A.10
Theorem 4.6. Suppose that Assumption 4.2 holds and considers the node feature unlearning case. For Z
K- X,PX, P2X, PK X and P = - we huve
72(2cc + (cn + Aci )D mmm)) IVI(W D')l = [H H W All
(6)
X4m -
Note that the resulting bound is the same as the bound in Theorem 4.3 This is due to the fact that we used the normalization factor K+T in Z. Hence, given the same noise level, the GPR-based models are more sensitive when we trained on the noisy loss Lts Whether the general high-level performance of GPR can overcompensate this drawback depends on the actual datasets considered.
EMPIRICAL ASPECTS OF APPROXIMATE GRAPH UNLEARNING
Logistic and least-squares regression on graphs. For binary logistic regression, the loss equals E(e? Zw,,e, e Yr,) = log( e Yr, ef Zw)), where (zx) = 1/(1 + exp(-x)) denotes the sig- moid function. As shown in Guo al. (020)). the assumptions (1)-(3) in Assumption 4.2 are satisfied with e = 11 and 72 1/4. By standard analysis, we show that our loss satisfies (4) and (5) in Assumption 4.2 with ?1 = 1/4 and c = For multi-elass logistic regression, one can adapt the Cone-versus, -all other-classes" strategy which leads to the same result. For least-square regression, since the hessian is independent of w our approach offers (0, apprroxxieetee graph unlearning even without loss perturbations. See Appendix A.5 for the complete discussion and derivation.
Sequential unlearning. practice, multiple users may request unlearning. Hence, it is desirable to have a model that supports sequential unlearning of all types of data points. One can leverage the same proof as in Guo et al. (2020) (induction coupled with the triangle inequality) to show that the resulting gradient residual norm bound equals T' at the th unlearning request, where e' is the bound for a single instance of approximate graph unlearning.
Data-dependent bounds. The gradient residual norm bounds derived for different types of approx- imate graph unlcarning contain a constant factor 1/A+, and may be loose in practice. Following Guo al. 2020), we also examined data dependent bounds.
Corollary 5.1 (Application of Corollary in Guo et al.
2020 Z'H
For all three graph unlearning All
scenarios, we have [[V ,D'Il < 72 [Z'll [|op
A
Hence, there are two ways to accomplish approximate graph unlearning. If we do not allow any retraining, we have to leverage the worst case bound in Section 4 based on the expected number of unlearning requests. Importantly, we will also need to constrain the node degree of nodes to be unlearned (i.e., do not allow for unlearning hub nodes), for both node feature and node unlearning. Otherwise, we can select the noise standard deviation a, e and d and compute the corresponding "pri- vacy budget" ac/ / log (1.5/8). Once the accumulated gradient residual norm exceeds this budget, retrain the model from scratch. Note that this still greatly reduces the time complexity compare to retraining the model for every unlcarning request (see Section 6). We also relegate the pseudo-code of our method leveraging data-dependent bounds for sequential unlearning in Appendix A.6
7

---

Published as a conference paper at ICLR 2023
10P
Grasient res hotm
104
10
301
Comolay
107
Buy
Tru Hore Node Festure Uniarriin
Thue horm Zage Uninurring
Narm for Mode Unsaninng
The Hore Unszuztared Unturning
Theorame
Narm for Unstruau Unteaming
Thwover
Towere 4.5.
00
221
10
10"
94.0
00
Test 80D0PFR (16
8500
02.
SGC Nace Famare Ueieuming
SGC Node Unisumiig
Lecrucuued lnneerring
Undeucuee Limber
60
S30 Rebbinng
No Crudlt Hicuunng
BLC
S6C Eutpp-UsAAATT
5C0 reduueaanngg
80
No Grupe iocrarig
Soc Rersading
100
20C
300
400
500
500
700
800
250
500
750
1000
2250
1200
1750
2000
100
230
300
400
200
800
105
200
Lecmucuuee lnneorningg
Nace Fenaar Lebouring
3000
S6C Reerenng ng
Cdpe Unteariing
(ineestoned Linker
Node Unioumiig
Accumbattes vemovva uime
No Druch Hirueing
S0C Ruttunngg
NJ Gruph rocouring
SCC fichuas
100
Number of removals
Number remavals
Numberr remavals
Figure 2: Comparison of proposed SGC node feature unlearning (left column), edge unlearning (middle column) and node unlearning (right column) with baseline methods. The shaded regions the second row represent the standard deviation test accuracy. In the third row, we show the accumulated unlearning time function of the number of unlearned points. The time needed for each unlearning procedure is given in Appendix A.19
EXPERIMENT
Settings. We test our methods on benchmark datasets for graph learning, including Cora, Citseer, Pubmed (Sen et al. 2008 Yang et al.] 2016 Fey & Lenssen 2019) and large-scale dataset ogbn- arxiv (Hu et al. (2020) and Amazon co-purchase networks Computers and Photo (McAuley et al.) 2013 Shehur et al. 2018). We either use the public splitting or random splitting based on similar rules public splitting and focus node classification. Following Guo al. (2020), we LBFGS as the optimizer for all methods due to its high efficiency on strongly convex problems. Unless specified otherwise, and average the results over 5 independent trails with random initializations. Our baseline methods include complete retraining with graph information after each unlcarning request (SGC Retraining), complete retraining without graph information after each unlearning request (No Graph Retraining). and Unstructured Unlearning (Guo al. 2020 Additional details can be found in Appendix (A.
fix K 2, 10-1, X 10-2,e 1, 0.1 for all experiments,
Bounds on the gradient residual norm. The first row of Figure 2 compares the values of both worst-case bounds computed in Section and data-dependent bounds computed from Corollary [5.1 with the true value of the gradient residual norm (True Norm). For simplicity, we set 0 during training. The observation that the worst-case bounds are looser than the data-dependent bounds, and both bounds indeed valid upper bounds for the actual gradient residual norm.
Dependency on node degrees. While an upper bound does not necessarily capture the dependency of each term correctly, show in Figure 3 (a) and (b) that our Theorem 4.5 and 4.6 indeed do Here, each point corresponds to unlearning one node. We test for all nodes in the training set T, and fix À 10 a O. Our results show that unlearning large-degree node is more expensive in terms of the privacy budget (i.c., induces larger gradient residual norm). For other datasets, refer to Appendix A.19
8

---

Published as a conference paper at ICLR 2023
Congutes
Cuepp Arey
1000
Degres xt colsraation
(0
Digine cluserred 1od0
00
Number (emmnn
M
Oogaur buaid
5003
2010 20:0
1900 1310 3108
(0
Figure 3: (a), (b) Simulation verification of the result in Theorem and 4.6 pertaining to node degrees. (d), (f) Accumulated unlearning time as function of the number of removed nodes. The unlearning time of Unstructured Unlearning is often higher than that of our proposed approximate graph unlearning algorithms, because the number of retraining steps needed may be larger. (c), (e) Performance of approximate graph unlcarning methods on different datasets. We set a = 10, = 10 for Computers and À 10 for ogbn-arxiv. The number of repeated trials is 3 due to the large amount of removed data. (g) Tradeoff between privacy e and performance. To achieve similar numbers of retraining, we set = 0.1. (h) The number of data points predicted by the memhership inference attack model to lie in the training set.
Performance of approximate graph unlearning methods. The time complexity of unlearning and test accuracy of our proposed approximate graph unlcarning methods after unlcarning is shown in Figures 2 and B It shows that: (1) Leveraging graph information is necessary when design- ing unlearning methods for node classification tasks. (2) Our method supports unlearning a large proportion of data points with a small loss in test accuracy. (3) Our method is around 4x faster than completely retraining the model after each unlearning request. (4) Our methods have robust performance regardless of the scale of the datasets. For more results see Appendix
Trade-off amongst privacy, performance and time complexity. As indicated in Theorem 4.1 there is a trade-off amongst privacy, performance and time complexity. Comparing to exact un- learning (i.e. SGC retraining), allowing approximate unlearning gives 4x speedup in time with competitive performance. We further examine this trade-off by fixing and 6, then the trade-off is controlled by and a. The results are shown in Figure (g) for Cora, where we set ac = 0.1. The test accuracy increases when we relax our constraints on c, which agrees with our intuition. Remarkably, we can still obtain competitive performance with SGC Retraining when we require to be as small as 1. In contrast, one needs at least e 5 to unlearn even one node or edge by leveraging state-of the-arr DP-GNN (Sajadmanesh et al. [2022] Daigavane et al. 202I) for reason- able performance, albeit our tested datasets are different. This shows the benefit of our approximate graph unlearning method as opposed to both retraining from scratch and DP-GNNs. Unfortunately, the codes of these DP-GNNs are not publicly available, which prevents us from testing them on our datasets in unified treatment.
Membership inference attacks on unlearned models. We performed experiments pertaining to the node unlearning task and applied the membership inference (MT) attack for GNNs reported in Olatunji et al.] (2021b) on our updated model. The experimental details are discussed in Ap- pendix 19 As shown Figure 3 (h), even for full SGC retraining the attack can still identify parts of the removed nodes in the training set (for relevant explanations, see Appendix A.2). and the result of SGC node unlearning is slightly worse (w.rtt privacy) than retraining since our algorithm performs approximate unlearning. Note that the performance of the MI attack on the original model is consistent with the results in Olatunji et al. (021b) and significantly worse than both our unlearn- ing and complete retraining method. The results also highlight the fact that the privacy definition considered in MI attacks and approximate unlearning are different (see Appendix A.2 Neverthe- less, experiments show that method offers similar sevaccypreserving performance (in terms of MI) as complete retraining, and better performance compared to just using the original model without unlearning features.

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGMENTS
This work was funded by NSF grants 1816913 and 1956384. The authors thank Wei-Ning Chen and Pan Li for the helpful discussion.
REFERENCES
Martin Abadi, Andy Chu, lan Goodfellow, Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC conference on computer and communications security, pp. 308-318, 2016.
Lucas Bourtoule, Varun Chandrasekaran, Christopher A Choquette-Choo, Hengrui Jia, Adelin Travers, Baiwu Zhang, David Lie, and Nicolas Papernot. Machine unlearning. In 2021 IEEE Symposium on Security and Privacy (SP), pp. 141-159. IEEE, 2021.
Yinzhi Cao and Junfeng Yang. Towards making systems forget with machine unlearning. In 2015
IEEE Symposium on Security and Privacy, pp. 463-480. IEEE, 2015.
Kamalika Chaudhuri, Claire Monteleoni, and Anand D Sarwate. Differentially private empirical risk minimization. Journal of Machine Learning Research, 12(3). 2011.
Min Chen, Zhikun Zhang, Tianhao Wang, Michael Backes, Mathias Humbert, and Yang Zhang. Graph unlearning. arXiv preprint arXiv:2103. 14991, 2021.
Eli Chien, Pan Li, and Olgica Milenkovic. Landing probabilities of random walks for seed-set expansion in hypergraphs. In 2021 IEEE Information Theory Workshop (ITW), pp. 1-6. IEEE, 2021a.
Eli Chien, Jianhao Peng, Pan Li. and Olgica Milenkovie. Adaptive universal generalized pagerank graph neural network. In International Conference on Learning Representations, 2021b. URL
/tttps::/openreviiee net/ wtwp://wwwww.eeeeeeooommm///oooo wtt:://mmmmnnnnnlm..
Eli Chien, Wei-Cheng Chang, Cho-Jui Hsieh, Hsiang- Fu Yu, Jiong Zhang, Olgica Milenkovic, and Inderjit S Dhillon. Node feature extraction by self-supervised multi-scale neighborhood prediction, In International Conference on Learning Representations, 2022a. URL https:
//openrevien ew. www.//ooouaee ftt////ommmmmmdkggggg dJJggg1 Hbs8
Eli Chien, Chao Pan, Jianhao Peng, and Olgica Milenkovic. You are allset: A multiset function framework for hypergraph neural networks. In International Conference on Learning Represen-
tations, 2022b. URL http::/ss///peee.veeeeeeeee wwwpeeiwwwwwwweeeeeeeeeeeeeeeeee wwwpee/errr..eepeeeeeeaeeee
Fan Chung. The heat kernel as the pagerank of graph. Proceedings of the National Academy of Sciences, 197355199735-19740 2007.
Ameya Daigavane, Gagan Madan, Aditya Sinha, Abhradeep Guha Thakurta, Gaurav Aggarwal, and Prateck Jain. Node-level differentially private graph neural networks. arXiv preprint arXiv2211..1521, 2021.
Austin Derrow-Pinioon Jennifer She, David Wong, Oliver Lange, Todd Hester, Luis Perez, Marc Nunkesser, Seongjae Lee, Xueying Guo, Brett Wiltshire, al. Eta prediction with graph neural networks in google maps. In Proceedings of the 30th ACM International Conference on Informa- fion & Knowledge Management, pp. 3767-3776, 2021.
Cynthia Dwork. Differential privacy. encyclopedia of cryptography and security, 2011.
Matthias Fey and Jan Eric Lenssen. Fast graph representation learning with pytorch geometric. arXiv preprint 1903.02903 2019.
Fabrizio Frasca, Emanuele Rossi, Davide Eynard, Ben Chamberlain, Michael Bronstein, and Fed- erico Monti. Sign: Scalable inception graph neural networks. arXiv preprint arXiv:2004. 1988 2020.
Fernando Gama, Alejandro Ribeiro, and Joan Bruna. Stability of graph scattering transforms. Ad- vances in Neural Information Processing Systems, 32, 2019.
10

---

Published as a conference paper at ICLR 2023
Jiyang Gao, Chen Sun, Hang Zhao, Yi Shen, Dragomir Anguelov, Congcong Li, and Cordelia Schmid. Vectomet:: Encoding hd maps and agent dynamics from vectorized representation. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp-
11525- 1533, 2020.
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 Pattern Recognition, pp.
2020.
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. PMLR, 2020.
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. Advances in neural information processing systems, 33:22118 18-22133, 2020.
Glen Jeh and Jennifer Widom. Scaling personalized web search. In Proceedings of the 12th inter- national conference World Wide Web, pp. 271-279, 2003.
Junteng Jia and Austion Benson. Residual correlation in graph neural network regression. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 588-598, 2020.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. In International Conference on Learning Representations (ICLR), 2017.
Pan Li, Chien, and Olgica Milenkovic. Optimizing generalized pagerank methods for seed- expansion community detection. Advances in Neural Information Processing Systems, 32, 2019.
Derek Lim, Xiuyu Li, Felix Hohne, and Ser-Nam Lim. New benchmarks for learning on non- homophilous graphs. arXiv preprint arXiv: 104.0 11..00404444.401 2021.
Jiaqi Ma, Bo Chang, Xuefei Zhang, and Qiaozhu Mei. Copulagnn: Towards integrating representa- tional and correlational roles of graphs in graph neural networks. In International Conference on Learning Representations, 2020.
Andrew L. Maas, Raymond E. Daly, Peter Pham, Dan Huang, Andrew Ng, and Christopher Potts. Learning word vectors for sentiment analysis. In Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies, pp. 142-150, Portland, Oregon, USA, June 2011. Association for Computational Linguistics. URL http:
7/ 7/www www..accwwe.... org. http://ww.............oooooaaaa.
Julian McAuley, Christopher Targett, Qinfeng Shi, and Anton Van Den Hengel. Image-based rec-
ommendations on styles and substitutes. In Proceedings of the 38th international ACM SIGIR conference on research and development in information retrieval, pp. 43 43-52, 2015.
Iyiola E Olatunji, Thorben Funke, and Megha Khosla. Releasing graph neural networks with differ- ential privacy guarantees, arXiv preprint arXiv:2109.08800 202
Iyiola E Olatunji, Wolfgang Nejdl, and Megha Khosla. Membership inference attack on graph neural networks. 2021 Third IEEE International Conference on Trust, Privacy and Security in Intelligent Systems and Applications (TPS-ISA), pp. 11-20. IEEE, 2021b.
Chao Pan, Siheng Chen, and Antonio Ortega. Spatio-temporal graph scattering transform. In In- ternational Conference on Learning Representations, 2021. URL htttps:/
net. www.ooummmdFFFFF.oo. ZI
Chao Pan, Eli Chien, and Olgica Milenkovic, Unlcarning nonlinear graph classifiers in the limited training data regime. arXiv preprint 2rXiv:2211.032/6 2022.

---

Published as a conference paper at ICLR 2023
Sina Sajadmanesh, Ali Shahin Shamsabadi, Aurélien Bellet, and Daniel Gatica-Peree Gap: Differentially private graph neural networks with aggregation perturbation. arXiv preprint arXiv:2203.00999, 2022.
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 Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rad.
Collective classification in network data. Al magazine, 29(3):93 93999399333333 2008.
Oleksandr Shchur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günneeaann Pitfalls of graph neural network evaluation. Relational Representation Learning Workshop, NeurIPS 2018, 2018.
Reza Shokri, Marco Stronati, Congzheng Song, and Vitaly Shmatikov. Membership inference at- tacks against machine learning models. In 2017 IEEE symposium security and privacy (SP), pp. 3-18. IEEE, 2017.
Cathie Sudlow, John Gallacher, Naomi Allen, Valerie Beral, Paul Burton, John Danesh, Paul Downey, Paul Elliott, Jane Green, Martin Landray, et al. Uk biobank: an open access resource for identifying the causes of wide range of complex diseases of middle and old age. PLoS medicine, 12(3) 1001)790 2015.
Chuxiong Sun, Hongming Gu, and Jie Hu. Scalable and adaptive graph neural networks with self- label-enhanced training. arXiv preprint arXiv:2104.09376, 2021.
Bart Thomee, David Shamma, Gerald Friedland, Benjamin Elizalde, Karl Ni, Douglas Poland, Damian Borth, and Li-Jia L.. Yfee100m: 100m: The new data in multimedia research. Communications of the ACM, 59(2):4473, 2016.
Fan Wu, Yunhui Long. Ce Zhang. and Bo Li. Linkteller: Recovering private edges from graph neural networks via influence analysis. arXiv preprint arXiv:2108. 06504, 2021.
Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinherger. Sim- plifying graph convolutional networks. In International conference machine learning, pp- 6861-6871. PMLR, 2019.
Zhilin Yang. William Cohen, and Ruslan Salakhudinov. Revisiting semi-supervised learning with graph embeddings. In International conference on machine learning. pp. 40-48. PMLR, 2016.
Rex Ying, Ruining Hc, Kaifeng Chen, Pong Eksombatchai, William L Hamilton, and Jure Leskovec. Graph convolutional neural networks for web-scale recommender systems. In Proceedings the 24th ACM SIGKDD international conference on knowledge discovery & data mining, pp. 974 983, 2018.
Wentao Zhang, Ziqi Yin. Zeang Sheng, Wen Ouyang, Xiaosen Li, Yangyu Tao, Zhi Yang, and Bin Cui. Graph attention multi-layer perceptron. arXiv preprint arXiv:2 208. 10097, 2021
Xiao-Meng Zhang, Li Liang, Lin Liu, and Ming-Jing Tang. Graph neural networks and their current applications in bioinformatics. Frontiers in Genetics, 12, 2021b.
Hao Zhu and Piotr Koniusz. Simple spectral graph convolution. In International Conference on Learning Representations, 2020.
A APPENDIX
A.1 CONCLUSION
We introduced the first known framework for approximate graph unlearning. In this setting, new analytical unlearning challenges had to be addressed due to the presence of complex graph feature and topology data. Our analytical contributions pertain novel proof techniques for approximate graph unlearning, while our empirical studies on six benchmark datasets established fundamental performance-compleeity trade-offs between unlearning and complete retraining.
12

---

Published as a conference paper at ICLR 2023
A.2 FUTURE RESEARCH DIRECTIONS AND LIMITATIONS
Batch unlearning. In practice, it is likely that we not only require sequential unlearning, but also batch unlearning: A number of users may request their data to be unlearned within a certain (short) time frame. The approach in Guo et al. (2020) can ensure certified removal even in this scenario. The generalization of our approach for batch unlearning is also possible, but will be discussed elsewhere.
Nonlinear models and hypergraph extension. Also akin to what was described in Guo et al. 2020), we can leverage pre-trained (nonlinear) feature extractors or special graph feature trans- forms to further improve the performance of the overall model. For example, Chien et al. (2022a) proposed a node feature extraction method termed GIANT-XRT that greatly improves the perfor- mance of simple network models such as MLP and SGC. If public dataset is never subjected to unlearning, one can pre-train GIANT-XRT on that dataset and use it for subsequent approximate graph unlearning. If such public dataset is unavailable, we have to make the node feature extractor DP. In this case, we can either design a DP version of GIANT-XRT or leverage the DP-GNN model described in Section 2 By applying Theorem 5 Gf et al. (200)) the overall model can be shown to guarantee approximate graph unlearning, where the parameters c and 8 now also depend on the DP guarantees of the node feature extractor. There also another line of work on Graph Scattering Transforms (GSTs) (Gama et al. [019 Pan et al. (202T) for use as feature extractors for graph in- formation. Since GST predefined mathematical transform and hence does not require training. it can be casily combined with our approach (Pan et al.) 2022). Finally, generalizing approximate graph unlearning to hypergraphs can also be an interesting direction. Although the current SOTA hypergraph neural networks heavily rely on nonlinear modules such as AllSet (Chien et al. 2022b), we believe extension to classical hypergraph learning algorithms CChin et al. 2021a) is possible.
Empirical metries and MI. There is currently no empirical metric that be used to evaluate how well approximate machine unlearning methods preserve privacy. Although the definition of approximate graph unlearning automatically and theoretically ensures that one cannot infer infor- mation about the unlearned data point from the updated model (if one chooses to set e, to 0), it remains an open problem whether we can design an empirical metric that can accurately quantify this privacy- crivacypreservvng performance. Note that privacy-based attacks like the membership infer- ence attack (Shokri et al., 2017; Olatunji et al., 202Tb) have completely different design goals and may not work well in unlearning practice. For example, assume that there are two nodes that share similar features and neighborhood structures, come from the same class in the graph and are both included in the training set. This scenario frequently arises in practice, especially for graphs with strong homophily properties. In this case, even if we unlearn one of the nodes, the attack model will still have high probability of recognizing the unlearned node in the training set due to the presence of the "similar" node. Thus, the viability of using the results returned by the attack models to assess the performance of unlearner is not clear. This is also verified by some preliminary experiments on node unlearning tasks described in Section A. and the main text.
Societal impacts. The authors believe that for medical and biological sciences research, the right to be forgotten may significantly set back potentially life-saving discoveries due to the need to have access to many diverse data samples. But current trends seem favor privacy over discovery rates and timings. Hence, a compromise between data availability and the right to be forgotten has to be established in the near future.
One current limitation of our work is that the newly proposed proof techniques do not apply to general graph neural networks where nonlinear activation functions are used. Nevertheless, our work is the first step towards developing approximate graph unlearning approaches for general GNNs.
A.3 INTUITION BEHIND THE MODEL UPDATE RULE
Our unlearning mechanism proposed in Section iis
W = w' + [V2 D') (VL(W",D) - VL(w", D')]
and the intuition is stated as follows. Our goal for the updated model VL(W D') 0. By Taylor series we have that
V[(w- ,D')= VL(W", DD) + V2I(w", ('w V'I("'''')
w²) =0
13

---

Published as a conference paper at ICLR 2023
Therefore, have
10 10- VI((w", D')] W W' = [ D')]
w V2L(W" D -1 [V((W" (FL(W",D) -) VL(w", D')]
The last equality holds due to the fact that w should be the unique optimizer for the strongly convex loss L(w, D) over the entire dataset D.
A.4
ADDITIONAL ILLUSTRATIONS
W
Learning algorithm A()
+
W Pal:
Unlearning algorithm M (W. D. D/D/")
Learning algorithm A()
~ D)
DP requirement: Pa(:D) Pa(:2)
PA(:D')
Unlearning requirement: Pu W. D.DD") Px(:D')
W : D.D/D')
(a) approach
Machine unlearning approach
Figure 4: Difference between machine unlearning (as defined in Guo et al. (2020) and Differential
Privacy (DP).
A.5 ADDITIONAL DISCUSSIONS
Assumptions (2), (4) and (5) in our model and that of Guo et al. (2020) require Lipschitz conditions with respect to the first argument of t, but not the second. We also implicitly assume that the second argument (corresponding labels) does not effect the norm of gradients or Hessians. One example that meets these constraints the logistic loss: E ((w" x,y) then all required assumptions hold.
Details on Assumption 4.2
f(yw" x)
Least-squares and logistic regression on graphs. Paralleling once again the results of Guo et al. 2020), it is clear that our approximate graph unlearning mechanism can be used in conjunction with least-squares and logistic regressions. For example, node classification can be performed using logistic loss. The node regression problem described in Ma et al. (2020); Jia & Benson 2020) is related to least-squares regression. In particular, least-squares regression uses the loss (e Zw, e Yr,) Ze:'Zw Zw YY"Y,,"
),) )². Note that Hessian is of the form (c Z Te Z. which does not depend on w. Thus, based on the same arguments presented in Guo et al. (2200). our proposed unlearning method M offers (0, apprrxixiee graph unlearning even without loss per- turbations.
For binary logistic regression, the loss equals f(e Zw, Yf log[aee Y e. Zw)). where (xx) = 11(11 exp(=x) denotes the sigmoid function. As shown in Guo et al. (020)), the assump- tions (3)-(3) in 4.2 are satisfied with с = 1 and 72 = 1/4. We only need to show that (4) and (5) of 4.2 hold as well. Observe that (z YY Y,,)
(a Y x) 1). Since the sigmoid function ( restricted to lie in [0, 1]. 16") bounded by 1, which means that our loss satisfies (5) in 4.2 with
1. Based on the Mean Value Theorem, one can show that (xx) is max (z) LLisschiz
Using some simple algebra, one can also prove that (x) = a (z) axx)) = max (x()) 1/4. Thus our loss satisfies assumption (4) in 4.2 as well, with ?1 = 1/4. For multi-class logistic regression, one can adapt the "one-versus--le other-classes" strategy which leads to the same result.
A.6 ALGORITHMIC DETAILS
The pseudo-codes for training removal-enabled models and the removal procedure for the case of binary classification are presented below. Note that this procedure is the same for all three types of removal requests (node feature unlearning, edge unlearning and node unlearning). During training, add random linear term to the training loss by sampling a Gaussian noise vector b. The choice of standard deviation determines the "privacy budget" or/ //llog 1.5/5) as shown in Section
14

---

Published as a conference paper at ICLR 2023
Algorithm Training procedure
input: Training data Rxxdd training labels Y Rm, loss parameters a, x 0.
2: Sample the noise vector ~ a²),
3: w = arg minlwedd
Ei=1 (f(z, w. v.) + / 12) + b
4: return w'.
Algorithm Unlearning procedure
input: Feature matrix X Raxd labels Y E R", one-step propagation matrix P, loss train- ing set indices T, fi,,82,...5 sequence of removal requests Rm. Ui, parameters K,e, 6, 72, a,
0.
2: Compute node embedding after propagation Z = X
3: Training set D = {z,, y: VeT..
4: Compute using Algorithm (D) &, a, A).
5: Accumulated gradient residual norm B = O.
6: for j Rm, do
7: Update the feature matrix X' and propagation matrix P' based on the removal.
8: Compute new node embedding after propagation Z' = p x'.
9:
j Tr then
10:
Remove from the training indices T, T, \ (i). end if
11:
12:
Update the training set D' {z/, Va her..
13:
Compute A VL (w, D) L (w, D').
14:
Compute H 2 L (w; D').
15:
Update accumulated gradient residual norm B 3 + 72 Z' |lpp
Z
16:
if 3 > ac/ /2 log(1.5/0) then
17:
Recompute w using Algorithm 18: else
I (D,,,, a, A), 0.
19: w - w H
20: end if
21:
end for
22: return
15

---

Published as a conference paper at ICLR 2023
A.7 PROOF OF THEOREM 4.3
Theorem.
Under the node feature unlearning scenario, D = (X, Yr,, A) and D = (X', Y,,, A).
Suppose Assumption 4.2 holds. For Z = PK and P D-11--1 A, have
LV D')ll = (lHw,, Hw H S 7/2 + (on + Ae (01)Dmmm))
A4m
We need ensure that the norm of each row of Z is bounded by 1. We state the following lemma in support of this claim.
Lemma A.1. Assume that ||eTS|| S 1, Vi [n]. Then, Vi E [n], K 2 0, || |e s where P D-D-AA
Proof. Our proof is nontrivial generalization and extension of the proof in Guo et al. (2020). For completeness, we outline every step of the proof. We also emphasize novel approaches used to accommodate out approximate graph unlearning scenario.
Let G(() = VI(w, D'). By the Taylor theorem, Byy [0, such that G(w = G(w" + + = G(w*) + VG(w + t/H H
@ G(w") Hw, H A
G(w") + A Hw, A A
( 0+ Hw, H A A
.Hw,, H A Hw. H !
-HH,, Hww)) H H A.
In (a), we wrote Hw., & VG(w" + A), corresponding to the Hessian at w 2 w* + H Equality (b) due our choice of
w" VL(w", , D) VL(w", D') and the fact that w the minimizer of L(., D). We would like to point out that our choice of A is more general then that Guo al. 2020): Since unlearning one node may affect the entire node embedding Z, generalization recovers A from Guo ct al. 2020) as a special case of our model. In the latter part the proof, we will see how the graph setting makes the analysis more intricate and complex.
of A crucial. When K 0 (i.c., when graph topology is included),
By the
inequality, we have
[[G(w")) )I S [H,,, H || All
Below we bound both norms on the right hand side separately. We start with the term [Hw, -w- Note that
(v'((e Y (.) v' ef Y2;)!l
(c TT w c Y (c, Z w. of Y (c.
| T z' w, T Z'w 2 < 72/1
/2//|w, w ? >
(10) 2 H
Here, (a) follows from the Cauchy-Schwartz inequality and the Lipschitz condition on E" in As- sumption 4.2] Unlike the analysis in Guo et al. (2020), we are faced with the problem of bounding the term le I' In Guo al. (000 (where Z X), simple bound equals 1, which may be ontained via (3) in Assumption 4.2 However, in our case, due to graph propagation this norm needs more careful examination and simple application of the Cauchy- Sanchy-Schwart. inequality does not suf- fice, as would lead to term
| |||o where llop denotes the operator norm. The simple worst case (i.e., when all rows of X are identical) leads meaningless bound O(n).
By leveraging Lemma A. we can further upper bound equation 10 according to
| ((e w,, of Y V2e(ee w., e, YY: )ll S 72 H Allee
72 H H
(11)
16

---

Published as a conference paper at ICLR 2023
where (a) follows from Lemma A.1
As a result, we arrive at a bound for Hw, Hw
|| of the form
Hw, Hw 11 S 78-1
- V E(e
$ 7m - 1) | w A|.
(12)
Next, we bound |. Since L(, D') is A(m 1) J-strongly convex, have H For the norm || we have
All
X(m-1)
A = VL(w", D) - VL(W",D')
Aw" "e I Yr.) + Σ
Vi(ee Zw" of YT,) Ve(e of Yr,)) (13)
1=1
The third term does not appear in Guo et al. (2020), since when K 0, Z X and Z' X' are identical except for the m row. In the approximate graph unlearning scenario, even removing one node feature can make the entire node embedding matrix Z change in e row, which creates new analytical challenges. For example, consider the case X [x1, x.)" where we have graph with three nodes, each with a 1-dimensional feature. Consider the fully connected graph (i.e., all entries in P set to 1/3). Then, unlearning node 1 results in Z' [0, 22, æa]" for unstructured unlearning. However,
[(x2 + 233/3, (I2 + x33/33 (I2 + x3)/3/" for the case of L = 1, which completely different from Z [(21 + T2 /3, (21 22 + zz)/3, (I1 + +22 + 233/3]" Hence, the analysis in Guo et al. (2020) cannot be directly applied to graphs, as Z' changes in more than just row compared to Z while unlearning node feature.
By Minkowski's s triangle inequality, we only need to bound the norm of the three individual terms in order bound the norm of A. For [|w*]l, since w is the global optimum of L(:; D), we have
0 VL [ D)
Vl(ce Zw", ,o, ,o,Y,,, Yr.) + Amww
(14)
By (1) in Assumption 4.2 we have
[w||| E Tl(e.TZw .e. Yr.)l
(15)
Am
X
Once again, by (1) in Assumption 4.2 have
Vi(e,,,z'' e YY, )ll cc
(16)
bound for the last term is established in the last step, as described below.
Vile.'Z"' .e.T.. ve(ee e, Yr.))
Vllle.Zz' o YT.) - Z'w,, c Yr.)ll
m-
[ of YT.)(eZZ)) (e z'v (ef
(17)
Observe that
. Y (e.
$ [ C Z' Yr.) Yz.
+ (1e( [e w ,Y (c f - Z'w'
Yn.
(18)
17

---

Published as a conference paper at ICLR 2023
The first term can be bounded as
(e Zw e YT, - ee Yr, (e)))
< (e Zw e YT.) - ((e e Yr,) ) [ z)
2 nlll Zw - e Z''''' (e 1
Wn m |1(e z c ''' w*ll
||(ee - o 1|
(19)
Here, (a) is due to (4) in Assumption 4.2 while (b) follows from Lemma A.1 and the Cauchy- Schwartz inequality. Inequality (c) is a consequence of the bound for ||w]] that we previously de- rived.
The second term can bounded as [e'eTT of (n z) ('
- - c YYYr, (e, $ (c Z'w' of Y,:) [ (c.
_ <al(TT)) (e I
(20)
For the inequality in (a), we used (5) from Assumption 4.2 Put together, we have
1
Vi(e Zw" of Yr.)
Ve(c Z'w', Yr.)
+ c
| Z)² - (e =
- + +a1 Σ c (Z
-z']l
m-1
c
+
I( p (X X|III|
(e k p D -Dix - x
+
C71
(ee D De m X||
CCY
+4
1e''p" D D De e x
ce
c p D DDeml
X +a
c
+c
|1e7 k - -e
D mm
X
c
+c
Σ
em D Dmm e
P D
1=1
(c2)
1'p'D -1 em D mm
+
ITD "D mm
+cl
cc
+ +ei)
D Dmm
(21)
18

---

Published as a conference paper at ICLR 2023
Inequality (a) follows from the fact that X' is identical to X except for the last and column, which are set to all-zeros. Thus, X -X is matrix with rows equal to zero-vectors, except for the m which equals the m row of X. Inequality (b) follows from the Cauchy- Secwwa-S inequal- ity. Inequality (c) is a result of (3) in Assumption 4.2 while (d) is a consequence the fact that c e""PDDlee is the value in the jth row and m column the matrix P D-D Also, it is obvious that this matrix is entry-wise nonnegative. Inequality (c) is due to the fact that p D is entry-wise nonnegative. In (f), p stands for a probability vector and (f) holds since
K PKD-I= (D- D = D===D-'(AD-))
(22)
and AD- is a left stochastic matrix. Inequality (g) is a consequence of the observation that the maximum entry D at most and that the latter is a diagonal matrix. Hence, D D'D-''p p S 1"p. Also, 1 by the definition of the probability vector.
Combining the bounds, we obtain
2cA (cn + dc D
| < c
+ ci
D mm
(23)
Including the bound on Hw!!| || and equation 12
we then obtain
2n 222+ + D
[|G(w 7m 1) 2
72(m -1) 1)
X X(m -
72(2cd + (ey + Aey ( mmmm)
(24)
11(m- -
This completes the proof.
A.8 PROOF OF THEOREM 4.4
Theorem. For the edge unlearning case, we have (X, Yr., P) and D' =X, YT., P'). If P P À and Z = Pky X, then we have
[[V((W D'II (H,,, H H..HH 16 (cn c2)2
(25)
Amm
Similar to what holds for the node feature unlearning case, Theorem 4.4 still holds when neither of the two end nodes of the removed edge belongs Ty. Since P' is right stochastic matrix, Lemma A. still applies. Thus, we only need to describe how to bound | Following an ap- proach similar to the previously described one, we have |||| < ( + 21) Σ 1 (P
p'k K Je, We also need the following technical lemmas.
Lemma A.2. For both edge and node unlearning, we have le [p - -P'')*
ΣK e (P') P pk-kee vi,j [n], K 1 Lemma A.3. For edge unlearning, we have 1 1 PPP'Pk- < 4, Yk E K]
Combining the two lemmas and after some algebraic manipulation, we arrive at the desired result. is not hard to see that [P P' has only two nonzero rows, which correspond to the unlearned edge.
One can again construct a left stochastic matrix Á'D and a right stochastic matrix which lead to the result of Lemma A.3
Proof. The theorem can be proved as follows. From previous proof we have
||||
[[[w Ill < [Hw, Hw- H ||| < 72 X²m
(26)
Since the first term H H only involved the updated dataset, the upper bound for this term proved for node feature unlearning still holds. The term | can again be bounded using the fact
19

---

Published as a conference paper at ICLR 2023
that L(, is Am-strongly convex. The main difference between node feature and edge unlearning lies in the bound for A. By definition,
A VL(w", D) VI(W", D
Vi(ee Zw" . Yr,) Z'le, e,,YY,Y))) Yr.)]. and
Vl(ee"Z"'
cy |||| S
+ CI
11 - Z') eill
1=1
m
ch
+ 0I
Σ
|(p p x) Teil
i=1
m
-
c
+
Σ
-P'X)X) |
c7
|le T (Pk -prk) Σ e X
+
X
m
| T (P& -p ee X
+a
m
ch
Σ
|ee (P* -p
ee ||l]
m
n
C7
Σ Σ
|e (p
-prk jej]
(27)
j=l
By Lemma
A.2 we have
m n
C71 +
0 I (P -p' e,,ll )o,l
1=1 j=1
K
cen
t Lp P- -P
+a
k=1
K Σ
cn (
+
+a)
1'p
P 1
(28)
k=1
Using Lemma A.3 we arrive at ||||| S completes the proof.
(
+ +c) 4K. Plugging this expression into equation 26
A.9 PROOF OF THEOREM 4.5
Theorem. Under the node unlearning scenario, we have D = (X, Yr., P) and D = (X', Yr,, P'). Suppose also that Assumption 4.2 holds. For Z = pk x and P = D-1 A, we
have
2D mm - -1))² 2
12 2cx + K (on + ad)
[VL(W: ,'')l = ([,,, H H <
(29)
>+mm- 11m-11 1)
Again, the main challenge is to bound A. First we observe that (P') x'
(P')*X X.
This holds because node m removed from the graph in D', and thus its correspond- ing node features do not affect Z'. Similarly to the proof Lemma A.2 we first derive the bound >K K IT (P'') PP- P' For each term, 1 (P')k P P' p'ppk-k
ΣE 1T (T(pP'=-ee e P P' 11 To proceed, need the following two lemmas.
20

---

Published as a conference paper at ICLR 2023
Lemma A.4. For node unlearning and vk [K] and 1A [n], 1" (P' h-
( (D') ei S 1.
Lemma A.S. For node unlearning and vk [K] Ei of D' P P' PKP 1 2D mm 1.
These two lemmas give rise to the term K22 mm 1) in the bound of Theorem 4.5 and the rest of the analysis is similar to that of the previous cases. Lemma A.5 rather technical, and relies on the following proposition that exploits the structure of P P
Proposition A.6. For node unlearning and Vi, # m, e. OP-P'ley c PP)-)) Fori m or m, e.¹ P e, e Pej.
Proof. The proof is similar to the proof of Theorem 4.3 although several parts need modifications.
First, the result of Lemma A.1 needs to be replaced by the following claim.
Lemma A.7. Assume that lle S S $,, Vi and that e = O Then Vi [ni, K 2 have ||e] (PP)*S) S|| S 1, where P D-1 and P' -D')-
Next we have to modify the proof regarding the bound of ||]]. Following proof similar to that of Theorem 4.3
we have
m-1
||ه|
< 2c
C71 X
+ ci
- I eill.
(30)
Plugging in the expressions for and Z' leads
[(Z Z') c:1l Σ
(P'))x'''
[P x - x e: Σ
[[[pk -PP))1 x)
12 | ppk_ (
Σ
c, x||
1=1
le [px
-P'') je
10 pp - (P e, 1llllo
p (P') ei
(31)
The equality (a) is due to the fact that (P*) = x as the mh row and column of (P') K all-zeros. Thus, changing the last row of X' makes difference of (Pr) X'. Equation (b) is a consequence of the fact that I = Σn e/e" Inequality (c) follows from Minkowski's inequal- ity, while (d) follows from the Assumption 4.2
Schwartz inequality. Inequality (c) holds based on (3) in
21

---

Published as a conference paper at ICLR 2023
By Lemma A.2
can proceed with analysis as follows:
1 - T ezll
[p - (P')
K
(P') P PP
k=1
K
1 P
P-
(32)
where (a) due Lemma A.2 and the fact that of Pey a scalar, equal the jth row jth column of the matrix P.
Next, we bound each term 12 (P PPP''KK 1 separately, For E [K], we have
P-P 11
-1"(P))-1('))) (D') D' P P P PK-1
-1(("")~1 Σ - P
Σ (
61) (o D' P --P--P P')
(33)
Note that for each index 1, the corresponding term in the sum is just a product of two scalars. Let
first analyze 1d (D') This term can be bounded as
(PPP' b- P- P' Pk--1
1 ('
(4) Σ
n
P PPPPPPP-Ky
(34)
where (a) follows from Lemma A.4
We now turn our attention to the term e D' P - P' p which can be bounded according to Lemma A.5 as follows
(T'P') k- P- 1
D' P p
1=1
2D mm
1.
(35)
22

---

Published as a conference paper at ICLR 2023
Using these two bounds in equation 32 gives
[Z Z eill
i=1
c pp (P'))
eyll
(P k-1 P PPPPk
k=
(2D mm
+ 1) (2D mm 1).
(36)
Using this bound in the expression for ||||
we obtain
m-1
||||| S 2c
c71
Σ II Zz)Teil Till
071 + +() K 2D mm 1)
2c
+ +[G([ III I Hw., Hw
|||
w All
72 1)] A
2
12c ( + ci)
2D mm
< 11 -1)
D(m 11
7/2 22c) + K Ken + A1 2D mm - 1))
(37)
>+(m- -
This completes the proof.
A.10 PROOF OF THEOREM 4.6
Theorem. In the node feature unlearning scenario, we are given = (X. Yr,.
A) and D =
(X', Yr,,, A). Suppose that Assumption 4.2 holds. For Z K+I X PX p2x. Pk x and
P= D=D-1A we have
IVI(W D')lI HH, H H. 72(2c) + (on + Ae D mmm)²
(38)
X+mm 1)
Proof. The proof is almost identical to the proof of Theorem 4.3 We only need to bound the norms of the terms in Z. We start by modifying Lemma A. for the GPR case.
Lemma A.8. Assume that lee S
< 1, Vi E [n]. Then Vi E [n],
K 2 0, we have
VK+1 of [S, ... p S
< 1, where P 1-
Another part of the proof that needs to be changed is to establish a bound on
Vl(e . Yr.)
ve(eT''v ee. Yr.)).
(39)
23

---

Published as a conference paper at ICLR 2023
Following proof similar to that of Theorem 4.3 have
Vilo Zw' - Yr,))
Ve(c
m-1
c/i A
+ a) -
cm + 4
(z Z')Te,l
1 X X(X-P(X-X)) ",),..,,(((x,, (xXx')))
+ 9
K +1
MIMMIL
071 +
Om Com X, Peme X. X.
emem x) ooil
K +1
10
+ 6
[ em 2 X, e Peme X,
X.... ... pfp eme x
Y
K +
T Tm c Cm, T Pem, K ++1
em
Y
(ef em, e T Pem.
e pk Ppkmml |11
K
c +
e em
p*
m +4
Σ
K
1T em
+ 61
K Σ
1"''D-1
- DDem A
en + K
Σ
1'''D-'- e D Pm
K +1
K +1
K +1
1=1
1=1
k=
20 X
+ C1
Σ
D pp D
K+1
mm
km1
K
X +
Σ
1sT (
+
x KD
K +1
K+1
k=1
071
+ eI) EI)D Dmm:
(40)
where (a) is due to the fact that the & norm is upper bound for the & norm. Also note that
e. em 0, Vi # m. In (b), Ak E [K], p ((8) are probability vectors. This completes the proof.
Remark. Note that the GPR extension for the edge and node unlearning cases be derived through a similar analysis. One can also see that the key step is inequality (a), which still holds for the edge and node unlearning cases. The results are similar to Theorem 4.4 and Theorem 4.5 except that the definition of Z is replaced by one corresponding to the GPR case, as in Theorem 4.6
A.11 PROOF LEMMA A.I
Lemma. Assume that lee S|| < 1, Vi E [n). Then Vi E [n), K 2 0, we have ||e/ PKS] 1, where P D A
Proof. We prove this lemma by induction. Let (k) P For the base case = is true by assumption that |ee S|| < 1 Vi [n]. Assume next that the claim is true for the case k K 1.
24

---

Published as a conference paper at ICLR 2023
Then we have
e P
= |le pz (11) (
Σ
oz
Σ
||05
1
=
Dit A:A:=
Di
AA,,=
1 - x
(41)
Du j:A,==
D
where (a) based on the induction hypothesis for = K 1.
Remark: Note that if choose another propagation matrix P compared the one used in the SGC analysis, the above expression for K = becomes
es
S
l
S
l PS
Σ
Σ
Da =A Dj
D
D3
s
(42)
DD =:A,==1
D
One way approach the problem is simply the fact that the degree of node is at least and thusbe further upper bounded by D... This leads to the bound
We cannot easily simplify the sum Ejidn== VD,;"
le PSI S VD...
(43)
Obviously, this bound worse than the one Lemma A.Ienven when K 1. For general K, there will be an additional exponent K/2 for the maximal degree, which is undesirable. Nevertheless, our bound tight since for the worst case
star graph with center at node i, so that Djj for all j * i. The same argument applies for other degree normalizations. Thus it is critical to choose
P = D 1-1 Á to obtained the desired bound in Lemma A.1
A.12 PROOF OF LEMMA A.2
Lemma. For either the edge or node unlearning case, and Vi,j E [n], K 2 1, we have
lef [pK (P*) e, = Σ ef (P')-L 1=1
(44)
Proof. The proof consist of two parts. We first show that
- -PP
Then we proceed to analyze the absolute values of all terms in the sum.
The proof the first part follows from a telescoping property for the sum,
K
P (P P') - Σ (P') l - <P'
k+1
OP')OK 1P' + (P') 'pK (P')2p-22 ....+ Kp
= P K
(45)
Next, note that both P' and P are nonnegative matrices, and the same true of their k powers, A > 2. Thus,
k (P-P''K-tto pk-ke
| p (P)*
e Σ e (P))
K
< of (P') 1 P- P
(46)
k=1
This completes the proof.
25

---

Published as a conference paper at ICLR 2023
A.13 PROOF OF LEMMA A.3
Lemma, For the edge unlearning scenario, and vk. E [K], we have
1 P $ S
(47)
Proof. Let us start by analyzing the matrix P -'I-=-D''A-" A except for the 1st and thth row. The first row of the matrix equals
Note that all its rows
ej
P
P
1
A
À 1(m-1);
A A(m+t))...
A1......
d1 -
d1
d1 -
dl
di
di -
di
1
1
1
Atl
À A1mm-1) 1)1
Al(m+1)s...
di(di -1)
di(di -1)
di
di((i 1)
A A
À A1mm-1); (d1 - 1}
À A(m++))....
(d1 - -1)
d1 - 1)
(d1 -
d1 2
eT
e
D
D À
d1 2
1) m
(48)
d (d1
(d
where the last equality holds since Aim = 1. Similar arguments apply for the m row, for which we have
dm T. dm - 1)
T P'
cm D D
(49)
For fixed & E [K].
1 P- 1 p
e TT D - ApK-k
T p di 2
C1 Ci0 PKK-
d1 1)
+ p eme
D AApK-
1 1''p' dm 2
em e #1
(50)
dm 1)
We analyze these four terms separately. For the first term, have
1 l'p' h- e D' D-
1''p' kh "D'
c D ÄPK-K
1Tp'k- " ppeppk-k11
(51)
By the same argument as used in the proof for node feature unlearning, 17ppk-1 D D' e = D -1
p < 1, for some probability vector p. Also, e eTp < 1, which holds due the fact that P is right-stochastic matrix. We have hence shown that the first term in equation 51 is bounded by 1. For the second term, note that dj(d-
d,-2 & [d. Hence,
1'p di
e _ p
(d 1)
1 p n
I p kk m
d1
1 D
e T k <
(52)
where the final inequality follows the same argument as the one used for bounding the first term. For the third and fourth term, the analysis is similar to these two cases and both terms can be shown to be bounded by 1. Hence, we have
1 1 P D - - 14
(53)
This completes the proof.
n
26

---

Published as a conference paper at ICLR 2023
A.14 PROOF OF LEMMA A.4
Lemma, For all l & [K] and l E [n]].
(D') (De 1.
(54)
Proof. For k = 1, the claim is obviously true for all 1 E [xx], as the largest entry in D is upper
bounded by For & 2 2 and o have
1 ( (A (D'
- @ "
(55)
In (a), p stands for probability vector and the result follows since A'D is left-stochastic matrix if one ignores the node m. For m, easy that A'D'e, by the fact that the mh row and column of A' are all-zeros. This completes the proof.
A.15 PROOF LEMMA A.5
Lemma. For node unlearning, and Ak: E [K], Σi= D - 1 2D mm 1.
Proof. First, note that
a
n
-
P
Σ
o D'P P'
Σ e ΣΣ
o D' P' (56)
Then for i,j + m, by Proposition
A.6
we have
ef D'
P
P' P
(a)
c
D' (P' -P)c,c
of A -DDDD-D-- A C
D/u Air A/r
C
Du
D
(b)
Air
Air
eT
(57)
Di.
We used Proposition A.6 (a) since e/'D -D/oTT The equality (b) is due to the fact that for i # m, Ai. Air. Recall that A' and A only differ in the m row and column.
We consider next the only two possible scenarios, (1) is neighbor of m; (2) | is not a neighbor of m. For (1), we know that D' = Da 1 2 1. This leads to
D'J Air Air 1
1/1
(1 (1- Du -
Air
Å D
Air
(58)
D
D
D2
For (2), we know that D = Dyy Thus, Aur
D' Air = D.:
Next, we consider the case 1 + m,r = m. Again, by Proposition A.6 we have
D'
e D e' e = D' eT
Arm T
(59)
Du
Now, for case (J), we have Åim 1 and D', DDi 12 This leads to
D/
Du T
e/ e P P'
em eT
Atm e
e
(60)
Du
Dn
27

---

Published as a conference paper at ICLR 2023
For case (2), clearly have D/ [P P' e 0 as AAm 0.
Hence, for each j + and under the setting in case (1), D' P P' equals the vector
Ån A22 Du Du
A((m-)
A(m+1)
... 0. Du
,0,
0, .......
(61)
Du
DT
Dn
where the th entry of the first vector equals 0 and the second row vector is all-zeros except for the thth entry. Note that the first row vector times Di, Dn > a probability vector. Hence, by the
property p being a right-stochaste matrix, we have
An
A12
A 1)
A((m+1)
0,
pk-*1 1.
(62)
Du
Du
Du
Du
Since 1y-1 D2
1, we also have
Dij
0,
00
0,
pk-+1sh 1
(63)
D
Together, this shows that for each j + m and for the case (I), one has
- 2
(64)
For case (2), note that D JP- P' is an all-zero row vector. Note also that, excluding self-loops, there most D Drmm- neighbors of m (case (1)). Thus,
Ee' P P' P #1 1 2D
e
2.
(65)
To conclude the proof, we analyze the term = m. For any i E [m]. by Proposition A.6 we have
DD P'
e
D D'm Amr
(a) Amr
e D'Peee
e
e, eT D Ae,,, = e Pe,ee
(66)
D
mm
D mm
where (a) holds by definition, and since D mm
1. Thus,
Kk- ppk-11=p
(67)
for some probability vector p. We have hence shown that for any k E [K].
Σ D' D'
Pkp 1 2D mm 2 1 = 2D mm 1.
P
(68)
This completes the proof.
A.16 PROOF OF LEMMA A.7
Lemma. Assume that |le!'s] Vi + m and that eT, = OT. Then Vi E [n], K we have IleT (P") < where P D- and P' (D')- A'
Proof. The proof is similar to the proof of Lemma A.I and based on induction. The base case k 0 obviously true by assumption. Now, assume that the claim is true for k K and let
28

---

Published as a conference paper at ICLR 2023
((K-1) (P')(K-1)S. Then, vi m,
|e (P')
Σ
e
(
D j:A,==1
Σ
eej (K-)
Di A:A =1
Σ 1
D j:A =1
Σ
Da
(69)
D AAA
Dii
Here, (a) is due to our hypothesis for k = K - 1. For = m, note that Ams - 0, Vi E [n]. Thus,
[eT (P = 0 < 1. This completes the proof.
A.17 PROOF OF LEMMA A.8
Lemma. Assume that ||e S
S 1, Vi E [n]. Then, Vi
E [n], K 2 0, we have
|K4I of [s, P.S. ... P S I, where P D-IA.
Proof. By Lemma A.l we have leT"*ss < 1. vk [K]. Thus,
1 of [s, JSP P's....... pk
Σ 1sfs
$
(70)
VK+
+1
K +1
which complete the proof.
Remark. Using the normalization к+I also leads norm bounded by Hence, the norm of each row of bounded by 1. We need the normalization K+1 instead of KK+ to accommodate another claim in the proof.
A.18 PROOF OF PROPOSITION A.6
Proposition. We have of P - P' = (P'-P)ej, Vi,j # m For i = m or j = m,
cf PP e, o Pej.
Proof. For the first case when Vi,j + m,
A A D
e (P- (P-P')
(71)
D's
Recall that by definition, in this case we have Asj i is a neighbor of m; (2) is not neighbor of m. For (1), we know that D' D 2 1. As result,
Aly. Now, there are two cases to consider: (1)
A D
A
A
A D -
0.
(72)
D
D
This directly implies e! |P P' e, of (P'- (P'-P)ej- For (2), know that D D2 and thus c. |P C, 0 c. (P' P)c, These claims complete the proof for the first part. For the case that or m, note that since both the mh row and column all-zeros for P', simply have e." P e, = e. Pe,. Note that in establishing the claim we also used the fact that P is nonnegative. This completes the proof.
29

---

Published as a conference paper at ICLR 2023
Table 1: Properties of benchmarking datasets.
Name
#nodes
#edges
#features
#classes
train/val/test
Cora
2,708
10,556
1,433
1,208/500/1,00
Citeseer
3,327
9,104
3,703
6
1,827/500/1,00
PubMed
19,717
88,648
500
18.217/500/1,000
Computers
13,752
491,722
767
10
12.252/500/1.000
Photo 7,650
238,162
745
6,150/500/1,
ogbn-arxiv 169,343
1,166,243
128
40
90,941/29,799948.663
A.19 ADDITIONAL EXPERIMENTAL DETAILS
All our experiments were executed on a Linux machine with 48 cores, 376GB of system memory. and two NVIDIA Tesla P100 GPUs with 12GB of GPU memory each. Information about all datasets can found in Table [ The data split is public and obtained from PyTorch Geometric Fey & Lenssen 2019) We used the "full" split option for Cora, Citeseer and Pubmed. Since there is no public split for Computers and Photo, we adopted a similar setting as for the citation networks via random splits (i.e., 500 nodes in the validation set and 1, 000 nodes in the test set). The data split for ogbn-arxiv is the public split provided by the Open Graph Benchmark Hu et al. 2020).
Dependency the node degree. We verified Theorem 4.5 and Theorem 4.6 for node degree dependencies on Photo, Cora, Citeseer and Pubmed. The results are presented in Figure 5
Ciedoon Nom
4010 a0 10 1009
Citedoon Dositnal Nomm
20 106
Coadert Roamne Nom
30*
Theoee 4p
torm
zup
tni
101
20
T0P
20"
10-2
10
10"4
0014
10a
1t2
30P
30P
101
102
301
10
10P
10a
Degra Uniaamed Moda
Degion of Unbhaarad hode
Degris Uniksama Nodia
Dag of Undearred Node
Putomed
20a
Grastlnt Resithal Narm
104
107
10"
nerm
104
2z4
Gradtrrd Resraial
30"
10"
Grastene Desehha
10P
203
"""""
10P
3013
30
Z0n4
20r3
2014
[111
107
10!
122
10?
10P
101
10P
10P
301
107
107
101
107
Unleneeed made dingron
Degres Eivisamed
Degran Unleermdd Nextn
Degren Lininamed
Figure 5: Additional examination of the degree dependency result from Theorem 4.5
(top) and
Theorem 4.6 (bottom).
Nonaccumulative time for each of the unlearning procedures. Figure 6 6/owwsssssows shows the average time complexity for each unlearning step the Cora dataset. The spikes for approximate graph un- learning methods and Unstructured Unlearning (Guo et al. 2020) corresponds to retraining after a removal.
Membership inference attacks for unlearned models. We performed experiments for node un- learning tasks and applied the membership inference attack for GNNs reported in Olatunji et al. (202Tb) to our obtained updated models. For simplicity, we used the Cora dataset and removed up 100 nodes. After each removal, we applied an MI attack on the updated model. We compare the results of our SGC node unlearning approach with that of the original SGC model without updates, which is the model trained on the full dataset, and with SGC retraining, which corresponds to the model obtained after retraining upon each removal request. We repeated the experiments with 10 different trails and random splits and averaged the results. As shown in Figure 7 even for full SGC retraining the attack model can still identify parts of the removed nodes in the training set, and the result of SGC node unlearning is slightly worse (w.r.t privacy) than retraining since our method is concerned with approximate unlearning. Note that the performance of the MI attack the original model is consistent with the results from Olatunji et al. (2021b) and significantly worse than both our unlearning well the complete retraining method. This, from the experimental side, shows that
30

---

models. None of the retraining methods involves Published as a conference paper at ICLR 2023
Cora plwarning
Cora
Cora
Edge Unteering
Lnteeaninng
5.2
Removal Time
200
000
250
500
200
3300
1200
1500
1750
2000
100
300
800
Number of Removals
Number of Removals
Number of Removals
Figure 6: Nonaccumulative time for each removal step on the Cora dataset. The setting is the same as in Figure 2
method offers similar privacy-preserve performance full retraining, and better performance when compared to the original model without unlearning. Nevertheless, the results also motivate the search for alternatives to MI attacks for unlearning schemes.
Cora, 10 Repeated Trails
Predicted Number of Data Points in Training
SGC Node Unlearning
Original SGC Model without Update
80
SGC Retraining
60
40
20
0
20
40
60
80
100
Number Removed Nodes
The number of data points predicted by the attack model to lie in the training set. The setting is the same as Figure
Figure 7:
Additional experiments. The performance of our proposed approximate graph unlearning methods on three datasets, including Citeseer, Pubmed and Amazon Photo. is shown in Figure g It is worth pointing out that our bound on the gradient residual norm in Section 4 does not guarantee the gen- eralization ability of the updated model. Therefore, could happen that the test accuracy increases as we remove information from the training set, as shown in the second row of Figure g or that the performance not very stable, as seen in the third row of Figure g
We also performed additional experiments The first row shows the average performance over 10 repeated trails with random splitting, and conclusion is the same the one stated in Section The second row shows the performance GPRR-ased models. Note that when the number removal requests becomes large, the performance of GPR-basedd models degrades much faster than that of SGC-based models. This observation is consistent with our discussion of noise.
the Cora dataset, with results shown in Figure 9
31

---

Published as a conference paper at ICLR 2023
Citeseer
Citeseer
SGC Node Feature Unlearning
SGC Node Unlcarning
Test Test Accuracy (9))
Removal Time (s)
Alg. 2
600
400
72
SGC Node Feature Unlearning
SGC Node Unlearning
Alg. 2 in
200
400
600
800
1000
200
400
000
1000
Number of Removals Pubmed
Number of Removals
Pubmed
75.0
SGC Node Feature Unlearning
1000
SGC Node Feature Unlearning
SGC Node Unlearning
SGC Node Unlearning
Test Accuracy (96)
74.0
Alg. in [2]
800
Alg, 2 in
74.6
Removal Time
600
74.4
74.2
400
74.0
73.8
2000
4000
6000
8000
10000
Number Removals Photo
Number of Removals
Photo
Node
SGC Node Feature Unlearning
7000
SGC Node Unlearning
Test Accuracy (96)
6000
Alg. 2 in
Removal Time
60
4000
50
2000
2000
40
1000
1000
1750
250
750
1000
1250
1500
1750
2000
Number of Removals
Number of Removals
Figure 8: Performance of approximate graph unlearning methods on different datasets. First Row: We removed to 55% of the training data in Citeseer. Second Row: We removed up to 50% of training data Pubmed. Third Row: We set 10, = 10 10-4, and removed up to 30% of the training data in Amazon Photo.
32

---

Published as a conference paper at ICLR 2023
53.
02.5
50C Node Festure Undoaring
SGC Node Unbnering
In]]
81.5
Alc 2
Anc Ressiia
Frlgn Undrenaing Rozeiing
8n0 meeuarin
Gruph Rezsiing
BLC
Graph Demsinnng
66
60
GPR Lidnarning
82
80C-0 G/T1 Mode Uiioarirg Alp 3n
21
dage
700
Narber Remondts
Nurdar Farmovall
Figure 9: Performance of approximate graph unlearning methods on Cora. First Row: The reported statistics are based on averaging over 10 repeated trails with random splitting. Second Row: GPR- based models are used obtain node embedding. All other settings are the same in Figure 2
33


Reviews:
[{"review_id": "UFAIE-asUDY", "reviewer": "Reviewer_dA7m", "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 deals with unlearning methods for graphs. It introduces a new algorithm for approximate graph unlearning from different requests (feature, node, and edge unlearning) for Simple Graph Convolution and Generalized PageRank models, and provide theoretical guarantees of unlearning.", "summary_of_the_review": "I enjoyed reading this paper despite a number of presentation flaws. The approach and results are clearly worthwhile, but the presentation of the paper really needs to be improved to allow for publication.", "strength_and_weaknesses": "This article is an extension of a paper by Guo et al. published in ICML 2020, which investigates approximate unlearning for unstructured data. The present paper extends the methodology and the results to graph data for 2 learning models: Simple Graph Convolution and Generalized PageRank, which is clearly of great interest and certainly non-trivial.\n\nOn the substance, I think that this paper suffers from 2 main limitations.\n- First, it does not apply to Graph Neural Networks and can therefore appear as quite specific. On this point, it would be interesting for the authors to explain precisely the conceptual limitations of their approach and why it does not apply to more complex models (GCNs for example). However, I understand that this paper is a first step towards approximate unlearning for graphs and can not handle all models at once.\n- Second, it does not investigate from a theoretical perspective the time-complexity of their removal procedure, while the main objective is to save computation time compared to retraining. It would be interesting to know the theoretical gain in each of the cases considered, also in the case of successive requests.\n\nOn the form, my comments are given in the following box.\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": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "9u7YpCbQS5", "reviewer": "Reviewer_XzFP", "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 graph unlearning algorithm with provable theoretical guarantees. The graph unlearning is divided into three sub-unlearning tasks: node feature unlearning, edge unlearning, and node unlearning. A tailored analysis is provided for each subtask. The experiments with six benchmarks show the effectiveness of the proposed method as well as the inherent trade-off between privacy and accuracy.", "summary_of_the_review": "Although there are some limitations to the proposed approach, it is worth emphasizing that this work lays the foundation of the theoretical analysis of graph unlearning. Some parts of the presentation could be improved further to improved the readability of the manuscript.", "strength_and_weaknesses": "Strength\n- The paper provides a detailed theoretical analysis of the graph unlearning algorithm.\n- Graph unlearning is broken down into three subtasks: node feature/edge/node unlearning.\n\nWeaknesses\n- The analysis is performed on the simplified convolutional graphs and cannot be generalized to the standard GNN architectures. Although SCG shows competitive performance on some datasets, it is not the most preferable model selection in general. So, it would be good to have some additional experiments with more GNN architectures to show how the proposed approach can be generalized to the other models.\n- Following the previous weakness, the assumptions such as the unique optimum of the loss is quite strong are quite strong and cannot meet in general.\n- Although it is important to keep similar performance with retraining methods, it is also important to analyze what can be unlearned or not from the unlearning perspective. The current analysis only shows the performance of the membership inference attack and lacks a detailed analysis.\n- The proposed method only works when the full dataset is accessible. In many unlearning scenarios, it is not guaranteed to access the full dataset.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and 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": "2N9Rus8T74", "reviewer": "Reviewer_VMQZ", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper investigates the problem of machine unlearning for graph-structured data. The authors provide an efficient algorithm to approximate graph unlearning in node classification tasks. The algorithm is proved to hold good theoretical properties for specific GNNs (SGC and GPRGNN). The authors also conduct an empirical study to demonstrate that the proposed algorithm outperforms the baselines.", "summary_of_the_review": "A solid and interesting work that generalizes unlearning algorithms from unstructured data to graph domain with theoretical guarantees. The analysis is comprehensive and well supported by experimental results. ", "strength_and_weaknesses": "Strength:\n\n1.\tThe introduced proposed algorithm and analysis are novel and promising. The process of generalizing unstructured data unlearning analysis to the graph domain is nontrivial. Node embeddings are propagated on graphs during training, and therefore the removal of data is more complex. The theoretical analysis is deep and sound.\n\n2.\tThe proposed bounds of error are well supported by the experiments. The experimental results support the claim that the unlearning algorithm is faster than retraining. The improvement of accuracy against unstructured algorithm is significant, and the correlation between the accuracy and the degree of removed node makes the bounds more reasonable.\n\n3.\tThe paper is well-written. Limitation of the work, reasonableness of assumptions and main techniques used in the proof are all well illustrated.\n\nWeakness:\n\n1.\tMany of the main techniques in analysis and the algorithm are generalized from Guo’s work, which makes the work less revolutionary.\n\n2.\tMost of the analysis is constrained to the binary classification task and linear GNN models, which is not practical. Current GNNs, such as the original GRPGNN, include non-linearity modules. As a result, the applicability of this method in real-world unlearning scenarios could be limited.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster