Scalable and Certifiable Graph Unlearning: Overcoming the Approximation Error Barrier
Authors: Lu Yi
Zhewei Wei
Venue: ICLR 2025 Spotlight (2025)
Keywords: Machine Unlearning
Graph Neural Networks
Scalability
Primary area: learning on graphs and other geometries & topologies
TL;DR: We propose a certifiable graph unlearning model that scales to billion-edge graphs by non-trivial theoretical analysis.

Abstract: Graph unlearning has emerged as a pivotal research area for ensuring privacy protection, given the widespread adoption of Graph Neural Networks (GNNs) in applications involving sensitive user data. Among existing studies, certified graph unlearning is distinguished by providing robust privacy guarantees. However, current certified graph unlearning methods are impractical for large-scale graphs because they necessitate the costly re-computation of graph propagation for each unlearning request. Although numerous scalable techniques have been developed to accelerate graph propagation for GNNs, their integration into certified graph unlearning remains uncertain as these scalable approaches introduce approximation errors into node embeddings. In contrast, certified graph unlearning demands bounded model error on exact node embeddings to maintain its certified guarantee.

  To address this challenge, we present ScaleGUN, the first approach to scale certified graph unlearning to billion-edge graphs. ScaleGUN integrates the approximate graph propagation technique into certified graph unlearning, offering certified guarantees for three unlearning scenarios: node feature, edge and node unlearning. 
  Extensive experiments on real-world datasets demonstrate the efficiency and unlearning efficacy of ScaleGUN. Remarkably, ScaleGUN accomplishes $(\epsilon,\delta)=(1,10^{-4})$ certified unlearning on the billion-edge graph ogbn-papers100M in 20 seconds for a 5,000 random edge removal request -- of which only 5 seconds are required for updating the node embeddings -- compared to 1.91 hours for retraining and 1.89 hours for re-propagation. Our code is available at https://github.com/luyi256/ScaleGUN.

Published as a conference paper at ICLR 2025
SCALABLE AND CERTIFIABLE GRAPH UNLEARNING: OVERCOMING THE APPROXIMATION ERROR BARRIER
Lu Yi & Zhewei Wei" Renmin University of China {yilu, zhewei lereeei@rrc.edu.co
ABSTRACT
Graph unlearning has emerged as pivotal research area for ensuring privacy protection, given the widespread adoption of Graph Neural Networks (GNNs) in applications involving sensitive user data. Among existing studies, certified graph unlearning is distinguished by providing robust privacy guarantees. However, current certified graph unlearning methods are impractical for large-scale graphs because they necessitate the costly re-computation of graph propagation for each unlearning request. Although numerous scalable techniques have been developed to accelerate graph propagation for GNNs, their integration into certified graph unlearning remains uncertain as these scalable approaches introduce approximation errors into node embeddings. In contrast, certified graph unlearning demands bounded model eπror on exact node embeddings to maintain its certified guarantee.
To address this challenge, we present ScaleGUN, the first approach to scale cer- tified graph unlearning to billion-edge graphs. ScaleGUN integrates the approx- imate graph propagation technique into certified graph unlearning, offering cer- tified guarantees for three unlearning scenarios: node feature, edge, and node unlearming. Extensive experiments on real-world datasets demonstrate the effi- ciency and unlearning efficacy of ScaleGUN. Remarkably, ScaleGUN accom- plishes (c, = (1, 10-1) certified unlearning on the billion-edge graph ogbn- papers100M in 20 seconds for a 5,000 random edge removal request- of which only 5 seconds are required for updating the node embeddings compared to 1.91 hours for retraining and 1.89 hours for re- pe-propagttion. Our code is available at https::/github.
INTRODUCTION
Graph Neural Networks (GNNs) have been widely adopted in various applications that involve sensitive user data, such as recommender systems (He et al. (020), online social networks QQiu jt al. 2018), and financial networks (Weber et al. 2019). With the increasing demands for privacy protection, recent regulations have been established ensure "the right to be forgotten" of users (Dang 2021). Advances in privacy protection have led to the emergence of graph unlearning (Said et al.
2023), which aims remove certain user data from trained GNNs. A straightforward approach is to retrain the model from scratch without the data to remove. However, retraining incurs substantial computation costs, rendering impractical for frequent removal requests. Consequently, various graph unlcarning methods attempt to enhance efficiency while maintaining performance and privacy protection comparable retraining. Among them, certified graph unlearning (Chien et al. 2022a) has garnered increasing attention due to its solid theoretical guarantees for privacy protection.
To achieve certified graph unlearning, an unlearning mechanism must be proved to ensure that the unlearned model is approximately equivalent to the retrained model with respect to their probability distributions. Specifically, certified unlearning guaranteed if the gradient residual norm of the loss function, || [(w D') is bounded for the unlearned model w and the updated dataset D' post- unlearning (Guo et al. 2019). This can be accomplished by introducing noise perturbation into the loss function, thereby rendering the unlearned and retrained models approximately indistinguishable in their probability distributions. Intuitively, the gradient residual norm measures the model error
"Zhewei Wei is the corresponding author.

---

Published as a conference paper at ICLR 2025
of the unlearned model, representing the discrepancy between the unlearned and retrained model. When the model error is limited in a certain bound relative to the noise level, the noise can effectively mask the error, thereby ensuring certified guarantees. Thus, previous studies attempt to achieve certified graph unlearning by perturbing the loss and subsequently deriving the gradient residual norm bound by non-trivial theoretical analysis. CGU (Chien et al.) 2022a) takes the first step achieve certified graph unlearning on the SGC (Wu et al. (2019) model and CEU Wu et al. (2023b) further extends this work batch edge unlearning. To satisfy the requirements of certified unlearning, the aforementioned studies typically re-compute graph propagation, such as (D~ AD + 2 in 2-hop SGC, and subsequently perform single Newton update step on the model parameters. This approach demonstrates substantial efficiency gains compared to retraining on small graphs.
Motivations. However, we observe that the existing certified graph unlearning methods struggle to scale to large graphs by conducting evaluations ogbn-papers 100M dataset (Hu et al. 2020). which comprises 11 1M nodes and 1.6B edges. Figure (a) shows the costs of existing un unlearning methods when removing 5,000 random edges with a (e (I, 100 certified guarantee. Re-computing graph propagation for a 2-hop SGC model requires over 6,000 seconds while retraining the SGC model after graph propagation takes less than 80 seconds. Furthermore, by excluding the propagation cost, unlearning can be finished in under 20 seconds via single update step of model parameters.
Since existing methods require re- re-propagation for each unlearning request, addressing one such request demands requires about 6,000 seconds, whose cost is expensive and almost comparable to retraining. The high cost of existing solutions contradicts the objective of unlearning, implying that reducing propagation costs is imperative to scale certified graph unlearning to large graphs.
Existing Unlearning Mathods
ScaleGUN
100
100
Time
Propepatoon
Uriceriing
wonupetin
Inlesring
(a)
(b)
Intuitively, scalable techniques developed for graph learning (Chiang al. 2019 Zeng et al., 2019) can be utilized to accelerate the propaga- tion process in certified graph unlearning. How- ever, the existing scalable approaches introduce
Figure 1: Time costs per 5,000-random--dee edge batch removal for existing unlearning methods v.s. Scale- GUN on ogbn-papen, I 100M (2-hop SGC model).
approximation error into the node embeddings, i.e., leverage an approximate dataset D' rather than the exact D'. Conversely, deriving a certified guarantee for unlearning requires bounding the model error, the gradient residual norm of the loss function ( || on the exact DD. This discrepancy leaves the impact of approximation error on the model error of unlearning unclear. making it uncertain whether existing scalable approaches can be directly integrated into certified graph unlearning.
Contributions. In this study, we address the research question: How can we integrate existing scalable techniques into certified graph unlearning to improve scalability while maintaining certified guarantees? We verify the feasibility of this integration and propose ScaleGUN, the first approach for Scalable and certifiable Graph UNlearning, ensuring both efficiency and privacy guarantees for billion-edge graphs. Our main contributions are as follows.
Uncovering the impact of approximation error on certified guarantees. We integrate the approxi- mate propagation technique from decoupled models (Zhang et 2016 Zheng et al.) 2022) into certified graph unlearning and derive theoretical guarantees for three graph unlearning scenarios: node feature, edge, and node unlearning. By non-trivial theoretical analysis, we reveal that the approximation error only marginally increases the model error of unlearning, while still ensuring that the total model error remains bounded. Therefore, the total model error can also be masked by noise perturbation, ensuring the certified unlearning guarantee.
Lazy local propagation framework for Generalized PageRank. Existing approximate propagation techniques for dynamic Personalized PageRank cannot be applied to commonly used models in certified graph unlearning, such as SGC. To address the gap, extend these techniques to Generalized PageRank, facilitating efficient propagation for layered propagation schemes.
Empirical studies. Extensive experiments demonstrate that ScaleGUN achieves superior perfor- mance, efficiency, and privacy protection trade-offs on large graphs. Specifically, ScaleGUN takes only 5 seconds to update embeddings and 20 seconds in total to execute the aforementioned
2

---

Published as a conference paper at ICLR 2025
unleamiig request ogbn-punn eebnnpapers papers100M, as shown in Figure Additionally, study the impact of approximation error on certified unlearning by analyzing the approximate propagation parameter T maax- The results reveal that the approximation error can be controlled by T'ax to simultancously achieve impressive model performance and unlearning efficiency.
2
PRELIMINARIES
Notation. We consider undirected graph 9 = (V)E) with node set V of size and edge set & of size m. We denote the size of the training set as nh, Each node is associated with an F-dimensional feature vector x, and the feature matrix is denoted by X RTxF A and D are the adjacency matrix and the diagonal degree matrix of G with self-loops, respectively. .Nu) represents the neighbors of node u. Let A be (randomized) learning algorithm that trains on graph-structured data D = (X, Y, A) E X, where Y are the labels of the training nodes and X' represents the space of possible datasets.
outputs a model E H. where H is the hypothesis set, that is, A [D] + H. Suppose that DD' is the new graph dataset resulting from a desired removal. An unlearning method M applied to A(D) will output a new model E H according to the unlearning request, that is ((A(D), D') + H. We add a hat to a variable to denote the approximate version of it, e.g., 2 is the approximation of the embedding matrix Z. For simplicity, we denote the data as D to indicate that Z takes the place of Z during the learning and unlearning process. We add a prime to variable denote the variable after the removal, e.g., D' is the new dataset post-unlearning.
Certified removal. Guo et al. (2019) define certified removal for unstructured data as follows. Given c, 8 O, the original dataset D, removal request resulting in D', a removal mechanism M guarantees (c, o--erttif removal for a learning algorithm A if VT C H, C XX
P(M(A(D). D, D') T) S <(P((()) E T) + 6. and
P(A(D') T) S (TP(M((())) D, D') E T) +
This definition states the likelihood ratio between the retrained model on DD' and the unlearned model via M is approximately equivalent in terms of their probability distributions. [uoo et al. (2019) also introduced certified unlearning mechanism for linear models trained on unstructured data. Consider AA trained on D = {(x1. ([x1.80 ...181,,, ...,.... (Xx: }n)} aiming to minimize the empirical risk C(w; D) = Σm= / (w" everywhere. Let w* A(D) the unique optimum such that V VL(w", D) Guo al. propose the Newton udpate removal mechanism: w w= + H A, where A Aw" + vi((w*) x, v) when (x, y) is removed, and Hw- is the Hessian matrix of C(,,D") at w* Furthermore, to mask the direction of the gradient residual VL(w DD), they introduce a perturbation in the empirical risk: (w, D) L(w, D) + b w, where b RR. is a random vector sampled from specific distribution. Then, one can secure a certified guarantee by using the following theorem:
T X4, 91) + An
2 |w where is a convex loss function that is differentiable
Theorem 2.1 (Theorem 3 in (Guo et al. 2019)). Let A be the learning algorithm that returns the unique optimum of the loss [b(w; D). Suppose that a removal mechanism M returns w with |VV (w= :D)ll2 Se' for some computable bound e' > 0. Ifb ~ N (0, ce' /e) with e >> 0, then M guarantees (c, 8) -certifie removal for A with 8 1.5 1/
Certified graph unlearning. CGU (Chien et al. 2022a) generalizes the certified removal mechanism to graph-structured data SGC and the Generalized PageRank extensions. The empirical risk is Y is
modified to L( w: D)- Σm 7 (e. Zw, e, Y) + Ane w 12. where c, Z e, DDD'AA'X., the embedding vector and the label of node i, respectively, and ny denotes the number of training nodes. Removing a node alters its neighbors' embeddings, consequently affecting their loss values. Therefore, CGU generalizes the mechanism in (Guo et al. 2019) by revising A as V[w=" D) V V((w,, ("). If no graph structure is present, implying Z is independent of the graph structure, CGU aligns with that of (Guo et al. 2019). Based on the modifications. CGU derives the certified unlcarning guarantee for three types of removal requests: node feature, edge, and node unlearning.
Approximate dynamic PPR propagation techniques via Forward Push. Forward Push (Andersen et al. 2006 Yang et al. 2024 is canonical technique designed to accelerate graph propagation computations for decoupled models (Wang et al.] [02T]] Chen et al.) (020). The technique is a localized version of cumulative power iteration, performing one push operation for single node
3

---

Published as a conference paper at ICLR 2025
at time. Take Forward Push for = P'x and P AD-1 as an example, where x is the graph signal vector and & is the number of propagation steps. Forward Push maintains a reserve vector q(0) and a residue vector p(t) for each level For any node u E V. (v()) represents the current estimation of (P'x)(u), and (u) holds the residual mass to be distributed to subsequent levels. When r(0(()) exceeds a predefined threshold Tmax, it added to (0) and distributed to the residues of u's neighbors in the next level, i.e., r((+1)(v) is increased by r (()( ( ) for v E &u().. After that, (1)( is set 0. Ignoring small residues that contribute little to the estimate, Forward Push achieve a balance between estimation error and efficiency. Several dynamic PPR algorithms have been proposed to solve PPR-based propagation in evolving graphs (Zhang et al. 2016 Guo eet al.] (021). We focus on InstantGNN (Zheng et al., (022) the lazy local propagation framework in our ScaleGUN draws inspiration from it. Specifically, InstantGNN observed that the invariant property Å + or ox + (1 P holds during the propagation process for the propagation scheme π = = Lt= a - 'P'x. Upon an edge arrival or removal, this invariant is disrupted due to the revised P or x. InstantGNN updates the residue vector for affected nodes to maintain the invariant, then applies Forward Push to meet the error requirement. Since only a few nodes are affected by one edge change, the updates are local and efficient.
LAZY LOCAL PROPAGATION
This section introduces our lazy local propagation framework that generates approximate embeddings with a bounded L2-error To effectively capture the propagation scheme prevalent in current GNN models and align with the existing graph unlearning methods, we adopt the Generalized PageRank
(GPR) approach (Li et al. 2019) as the propagation scheme, Z = ELto we (D ID- ? X,
where we is the weight of the ε-th order propagation matrix and >/ E--0 |we| S 1. Note that this propagation scheme differs from that of CGU (Chien et al., 2022a). which uses an asymmetric normalized matrix P = D- "A and fixes we = 1/Z. We introduce the initial propagation method for signal vector x and the corresponding update method. The approximate embedding matrix 2 can be obtained by parallel adopting the method for each signal vector and putting the results together. Details and pseudo-codes of our propagation framework are provided in Appendix D
Remark. The lazy local propagation framework draws inspiration from the dynamic PPR method of InstantGNN (Zheng et al. 2022) and extends it to the GPR propagation scheme. To the best of our knowledge, our framework the first to achieve efficient embeddings update for the layered propagation scheme in evolving graphs, making it readily applicable to various models, such as SGC, GBP (Chen et al., 2020). and GDC (Gasteiger et al., 2019). Utilizing the GPR scheme also enhances the generalizability of ScaleGUN, allowing one to replace our propagation framework with dynamic PPR methods to achieve certified unlearning for PPR-based GNNs. Note that InstanIGNN cannot be directly applied to certified unlearning because the impact of approximation on the certified unlearning guarantees has not been well studied. This paper's 's main contribution is addressing this gap. We establish certified guarantee for GNNs that use approximate embeddings, detailed in Section 4 The differences between our propagation framework and existing propagation methods are further detailed in Appendix D.
For the initial propagation, adopt Forward Push with P = AD-1 drawing from the observation
that (D 1/2 AD- t) = D D' Initially, we normalize x to ensure D x < 1, and
set the residue vector r (0) = D x. Applying Forward Push, we derive = Σt we W.D D-- ( as
the approximation of z = El we iD-iAD= x. Any non-zero r(() holds the weight mass not yet passed on to subsequent levels, leading to the approximation error between à and z. During the propagation process, holds that
z
Σ t=
W.
q
(
Σ (AD AAD-11---p10 t=
By examining El Wi D (AD 1)6- we establish the error bound of as follows.
Lemma 3.1. Given graph G with n nodes and the threshold Tmax the approximate embedding 2 for signal vector x satisfies that ||2 2|2 S /
4

---

Published as a conference paper at ICLR 2025
Inspired by the update method for the PPR-based propagation methods on dynamic graphs (Zengg et al. 2022). we identify the invariant property for the GPR scheme as follows.
Lemma 3.2. For each signal vector x, the reserve vectors {q()} and the residue vectors {rl0)
satisfy the following invariant property for all u E V during the propagation process:
q (u) (1)) = -D(u)xx())
{= 0
q
(u) 1 = E (EN(u)
OCEAL
d(t)
Upon a removal request, we adjust [r(() locally for the affected nodes to maintain the invariant property. Consider edge removal scenario, for example, where edge (u, is targeted for removal. Only node u, node u, and their neighbors fail to meet Equation (2) due to the altered degrees of u and v. Take the modification for node u as an example. For level O, we update (0()) (u) reflecting changes in D x. For subsequent levels, r r(0) (2) is updated to reflect that the right side of u's equations exclude (u) For u's neighbors, their residues are updated accordingly, since one term on the ((t-)((a),
d(e)
(t)))) shifts to d(u)=1 Post-adjustment, the invariant property is preserved across all nodes. Then we invoke Forward Push to secure the error bound and acquire the updated 2. Removing node be treated multiple edge removals by eliminating all edges connected the node, Moreover, feature removal for node can be efficiently executed by setting p (u) -qi") (u). The following theorem illustrates the average cost for each removal request.
right, d(u)
Theorem 3.3 (Average Cost). For sequence of m removal requests that remove all edges of the graph, the amortized cost per edge removal O (T.2d). For a sequence of K random edge removals, the expected cost per edge removal is O (L?d).
Note that the propagation step L and the average degree d are both typically a small constant in practice. is commonly set to GCN (Kipf & Welling 2016), SGC, GAT (Velickovic et al.) 2017). Many real-world networks are reported to be scale-free, free, characterized by small average degree (Barabási 2013). For instance, the citation network ogbn-arxiv and ogbn ogbn-papers supers100M 100M exhibit average degrees of and 14, respectively. Consequently, this setup generally allows for constant time complexity for each removal request.
SCALABLE AND CERTIFIABLE UNLEARNING MECHANISM
This section presents the certified graph unlearning mechanism of ScaleGUN based on the approxi- mate embeddings derived from our lazy local propagation framework. Following existing works, we first study linear models with strongly convex loss function and focus on binary node classifica- tion problems. We define the empirical risk as L(w, D) -iee(n)]
[[(e) 2w, e, Y) + llwl)),
where is convex loss that is differentiable everywhere, e. and c, Y represents the approximate embedding vector and the label of node i, respectively. Without loss of generality, we assume that the training set contains the first n, nodes. Suppose that w the unique optimum of the original graph and unlearning request results in a new graph D'. Our unlearning approach produces model w as follows: w w H.l A, where A VL(=*, D) VL(w* D') and H. is the Hessian matrix of L(,)D') at w" We also introduce a perturbation in the loss function following (Guo et al. 2019) to hide information: Lb (w, D) = L(w, D) + bT where b E R is noise vector sampled from a specific distribution.
Compared to the unlearning mechanism, w = + (VL(w" D) VL(w" D')). proposed by Chien et al.) (2022a), our primary distinction lies in the approximation of embeddings. This also poses the main theoretical challenges in proving certified guarantee. According to Theorem 1 an unlearning mechanism can ensure (e, -)-ceriffied graph unlearning || D is bounded. Bounding V L(w , is the main challenge develop certified unlearning mechanism. One of the leading contributions of (Guo et al. 2019 Chien et al. 20226) is to establish the bounds for their proposed mechanisms. In the following,
elaborate on the bounds of || LVW( "DD) of ScaleGUN
under three graph unlearning scenarios: node feature, edge, and node unlearning. Before that, we make the following assumptions.
5

---

Published as a conference paper at ICLR 2025
Assumption 4.1. For any dataset D E X E [n] and E RP: (1) Vi(ee Zw, e Y) S (2) cl-bounded; (3) l' is 71-Lipschitz; (4) 1" is -i-Lisschi;:; (5) e X 1
Note that these assumptions are also needed for (Chien et al. 2022a) Assumptions (1)(3)(5) can be
avoided when working with the data-dependent bound in Theorem 4.5 We first focus on a single
instance unlearning and extend to multiple unlearning requests in Section 4.3
4.1 NODE FEATURE UNLEARNING
We follow the definitions of all three graph unlearning scenarios in CChien et al.) 2022a). In the node feature unlearning case, the feature and label of a node are removed, resulting in D = (X', Y' A). where X' and Y' is identical to X and Y except the row of the removed node is zero. Without loss of generality, we assume that the removed node is node in the training set. Our conclusion remains valid even when the removed node is not included in the training set.
Theorem 4.2 (Worst-case bound of node feature unlearning). Suppose that Assumption 4.1 holds
and the feature of node u is to be unlearned. If E [F], Zez Ze,| S we have
|[ D'Il S (T +av/F(u- (a1+ 8m F
1(m-1) vd(u)
The feature dimension F affects the outcome as the analysis is conducted on one dimension of the embedding Zj rather than on e, Z. In real-world datasets, F is typically a small constant. Note that 61 is exactly VuLrmax according to Lemma 3.1 To ensure that the norm will not escalate with the training set size nh, we typically set = 0 ( which implies that T Tmax
0(1/ (.n).. The bound can be viewed as comprising two components: the component resulting from approximation, ( + CIV (mmm-11) 61, and the component resulting from unlearning,
8 vd(u). In the second component, the norm increases the (FF+tv/(mm X(RL-1)
unlearned node possesses high degree, as removing a large-degree node's feature impacts the embeddings of many other nodes. This component is not affected by L, the propagation step, due to the facts that (D AD ff = = D (AD ((AD-I'D' ' and that AD is left stochastic.
Analytical challenges. It is observed that VL(w D'Il originates from the exact embeddings of D', whereas w is derived from approximate embeddings in ScaleGUN. Thus, the first challenge is to establish the connection between D' and D' in [[V[(W, ,''Ill To address this issue, we employ
the Minkowski inequality to adjust the norm: /V((W D')ll < | DD) - VL(w |')|
VL(W- . The first norm depicts the difference between the gradient of w on the exact and approximate embeddings, which is manageable through the approximation error. The second norm, VL(w-, D') signifies the error of w- as the minimizer of L(., D'), given
VL(W DD) (w,, Hw. H A/l
where Hw, is the Hessian of C(,, D¹) at W,, w + A for some 1) E [0. This introduces the second challenge: bounding | Bounding || is intricate, especially for graph unlearning scenarios. Here, A represents the difference between the gradient of w" on pre- and post-removal datasets, i.e., 2 and Ž'. Therefore, establishing the mathematical relationship between Z and Z' is the crucial point. Although prior studies have explored the bound of |e (Z Z')l| their interest primarily lies in P D 'A (Chien al. 2022a) or 1-hop feature propagation (Wu et al., (023b). which cannot be generalized to our GPR propagation scheme with D- AD 5. We address this challenge innovatively by taking advantage of our lazy local propagation framework as follows.
bounding A via the propagation framework. Assuming node is the 14-th node in the training set, for the case of feature unlearning, we have
A = Aw + Vl(2, w m4) + Σ (V((2.w',) -iu2 w', w'),))
kE(m.-1]

---

Published as a conference paper at ICLR 2025
where ((2, w ..) is short for l(e Zw" e Y). Creatively, we bound IZe Z'e, for all j E [F] via the lazy local propagation framework. Let z = Ze, and z' = Z'e, for brevity. In our propagation framework, right after adjusting the residues upon a removal, (g( remains unchanged. Moreover, Equation I holds during the propagation process. Thus, we have
D (AD (p(0
z
We
To derive p(t) y((t) notice that Equation is applicable across all Tmax configurations. Setting Tmax = 0 to eliminate error results r((() becoming zero vector. Thus, for the feature unlearning scenario, (0) r'(0) is precisely ( as only node u's residue is modified. For p((t) p(() are all zero vectors since these residues are not updated. This solves the second challenge.
The bounds for edge and node unlearning scenarios can be similarly derived via the lazy local framework, significantly streamlining the proof process compared direct analysis of Zej Z'oj.
4.2 EDGE UNLEARNING AND NODE UNLEARNING
In the edge unlearning case, we remove an edge (u, v). resulting in D' (X, where A' is identical A except that the entries for (u, 8) and (v, u) are set to zero. The node feature and labels remain unchanged. The conclusion remains valid regardless of whether u, are in the training set. Theorem 4.3 (Worst-case bound of edge unlearning). Suppose that Assumption 4.1 holds, and the edge (u, v) is to be unlearned. Vf [F],
[Ze -Ze,
S c1, we can bound V VL(w ,D'Il by
Acn F An4
FaF++V/Fn Fri)
(1+ 271 (201 + An
4
4
vd(m)
Vd(u)
We observe that the worst-case bound diminishes when the two terminal nodes of the removed edge have a large degree. This reduction occurs because the impact of removing single edge from a node with many edges is relatively minor.
In the node unlearning case, removing node results in D (X', Y', A'), where the entries regarding the removed node in all three matrices are set to zero. The bound can be directly inferred from Theorem 443 since unlearning node equates eliminating all edges connected node This upper bound indicates that the norm is related to the degree of node u and that of its neighbors.
Theorem 4.4 (Worst-case bound of node unlearning). Suppose that Assumption 4.1 holds and node is removed. If E [F],
Ze, Ze,
I E1, can bound [[VL(W", (D') by
Ac7 F
( OfF+aVV(me 1)) -l)
[1+
271 F X(ni 1)
(2e1 + +4vd(u)+ E
4
A(n -11 1)
Vd(ww)
wEN(u)
4.3 UNLEARNING ALGORITHM
In this subsection, we introduce the unlearning procedure of ScaleGUN, More practical considerations are deferred to Appendix B.I including feasible loss functions and batch unlearning.
Data-dependent bound. The worst-case bounds may be loose in practice. Following the existing certified unlcarning studies (Guo et al. 2019; Chien et al. (2022a). we examined the data-dependent norm as follows. Similar to the worst-case bounds, the data-dependent bound can also be understood as two components: the first term 2c, || R incurred by the approximation error and the second
2'H incurred by unlearning. The second term is similar to that of the existing works, except that it is derived from the approximate embeddings.
term 72
12/
H ! A
Theorem 4.5 (Data-dependent bound). Let R(t) g denote the residue matrix at level t, where the j-th column R( represents the residue at level t for the j-th signal vector. Let R be defined as the sum E R(t). We can establish the following data-dependent bound:
VL(WT, ,D')ll 22c ||1 T R|| + + | |
2'A A
7

---

Published as a conference paper at ICLR 2025
Cora Node feature unlearning
Cora - Edge unlearning
Cora Node unlearming
10:0
Gradeent resiuull norm
Gredlent resiuvl norm
10'
30"
Worsisone rean bota-dependert Ligrr
10f
Wersk sase rarm Data dependent tom
10f
Mipoi-cuss nom Data-cepa stent nom Irus rorm
10f
The nore
10c
10F
10'
10%
Gradieess
10F
100
10-3
10
10
30
10
2007 450 Number of removals
2007 ATD Number of removals
Number of removals
Figure 2: Comparison of the bounds of the gradient residual: Worst-case bound (Theorem 4.2
4.3
4.4 for node feature, edge, node unlearning, respectively), data-dependent bound (Theorem 4.5) and the true value Cora dataset.
Sequential unlearning algorithm. Multiple unlearning requests can be executed sequentially. The unlearning process is similar to the existing works (Chien et al. [022a Wu et al.) 2023b), except that we employ the lazy local propagation framework for the initial training and each removal. Specifically, we select the noise standard deviation and privacy parameter e, 6, and compute the "privacy budget". Once the accumulated data-dependent norm exceeds the budget, we retrain the model and reset the accumulated norm. Notably, only the component attributable unlearning, i.e., the second term in Theorem 4.5) needs to be accumulated. This is because the first term represents the error caused by the current approximation error and does not depend on the previous results. We provide the pseudo-code and illustrate more details in Appendix B.2
5 EXPERIMENTS
In this section, we evaluate the performance of ScaleGUN real-world datasets, including three small graph datasets: Cora (Sen et al. 2008), Citeseer (Yang et al.) (0066), and Photo (McAuley et al., 2015); as well as three large graph datasets: ogbn-arxiv, ogbn-products, and agbn-papers 100M (Hu jet al. 2020). Consistent with prior certified unlearning research, we employ LBFGS as the optimizer for linear models. The public splittings are used for all datasets. Unless otherwise stated, we set L = 2, c = for all experiments, averaging results across 5 trials with random seeds. By default, we set #edges for edge unlearning and #uodes for node/feature unlearning in the linear model utility experiments to meet the typical privacy requirements (Chien et al.) 2024 Sajadmanesh et al.! 2023). Following (Chien et al. 2022a)). wy is set to for = 2 and 0 for other values. The propagation matrix is set to P = D AD across all the methods for fair comparison. Our benchmarks include CGU (Chien et al.) 2022a), CEU (Chen et al. (022). and the standard retrained method. The experimental results under this setting, additional experiments and detailed configurations are available in Appendix C
Evaluations. We evaluate the performance of ScaleGUN in terms of efficiency, model utility (performance), and unlearning efficacy. The efficiency is measured by the average total cost per removal and the average propagation cost per removal. The model utility is evaluated by the accuracy of node classification. Given the lack of standardized methods for evaluating unlearning efficacy in graphs, we utilize two attack methods to assess this efficacy. For edge unlearning, we apply the task of forgetting adversarial data as described by (Wu al. 2023a). For node unlearning, we employ the Deleted Data Replay Test (DDRT) as outlined in (Cong & Mahdavi).
Bounds the gradient residual norm. Figure 2 validates the bounds the gradient residual norm: the worst-case bounds, the data-dependent bounds, and the true value for all three unlearning scenarios the Cora dataset. For simplicity, the standard deviation is set 0 for the noise b. The results demonstrate that both the worst-case bounds and the data-dependent bounds validly upper bound the true value, and the worst-case bounds are looser than the data-dependent bounds.
Efficiency and model utility on linear models. We examine the unlearning performance of ScaleGUN on large graph datasets here and provide the results small graphs in Appendix C For large datasets, randomly selecting edges to remove is insufficient to affect model accuracy significantly. We propose novel approach to select a set of vulterable edges for removal. In- spired by Theorem 4433 we find that edges linked to nodes with small degrees are more likely to yield larger gradient residual norms, thus severely impacting performance. Consequently,
8

---

Published as a conference paper at ICLR 2025
Table Test accuracy (%), total unlearning cost (s) and propagation cost (s) per batch edge removal for linear models (large graphs).
ogbu-arxiv
ogha-prodacts
oghi-paperss00M
N
Retrain
CGU
CEU
ScaleGUN
N(xI0")
Retrain
OGU
CEU
ScaleGUN
N(x10*)
Retrain
SealeGUN
56.17
56.17
25
$7.83
$7.84
57.84
57.84
1
56.23
56.16
56.16
56.03
2
59.71
59.71
57.82
$1.83
57.83
57.83
56.22
56.15
56.15
56.02
4
59.55
57.82
57.82
57.82
57.82
56.21
56.15
56.15
56.15
6
59.89
59,32
100
51.81
57.81
57.81
57.81
4
56.20
56.14
56.14
56.24
8
59,46
59.59
57.81
57.81
57.81
57.81
56.13
56.13
56.17
10
Total
2,66
3.36
3.42
1,08
Total Prop
101.90
87.79
88.90
11.69
Total
6764,31
54.79
Prop
1.73
2,91
86.81
87.95
Prop
Corn
oghn-arsiv
0.50
ogbn-produrts
ogbnnpagerss 100M
Retrain
0.500
Retrain
Retrain
Retran
eCU.N
0.500
ScateGUN
2
0.57
SosleGUM
CBU
2
0.500
ScaleGUM
0510
0.500
0.500
0.55
0.000
0.50
0.79
0.695
107
200 100
2003
10100
7000 200 200 1000
Tox
1001 1006
adversorial
edges
Figure 3: Comparison of unlearning efficacy for linear models: Model accuracy v.s. the number of removed adversarial edges.
set of low-degree nodes from the test set and then select edges that con- nect these nodes to other low-degree nodes bearing identical labels. Table presents the test accuracy, average total unlearning cost, and average propagation cost for batch edge unlearn- ing in linear models applied to large graph datasets. The results highlight ScaleGUN's impres- sive performance, with its advantages becoming more pronounced as the graph size increases. Furthermore, Table[]shows the node and feature unlearning results on oghn-papers 100M, where 2000 nodes removed time. The results demonstrate that ScaleGUN achieves competi- tive accuracy compared the retrained model while significantly reducing the total unlearning and propagation costs under the node feature and node unlearning scenarios. Notably, on the ogbn-papers 100M dataset, ScaleGUN demon- strates a speed advantage of 1000 over retrain- ing in terms propagation cost under both edge and feature unlearning scenarios.
randomly choose
Table 2: Test accuracy (%), total unlearning cost (s) and propagation cost (s) per node feature/node removal for linear models on ogbn-papers 100M.
Festure Unlenming
Node Unlearaing
N(x1P))
Retrain
ScaleGUN N''10'')
Retrain
ScaleGUN
0
59.99
59.72
0)
$9.99
19.22
59,99
59.15
59.99
59.47
5
59.99
59,80
8
59.99
59.54 54
8
59.99
59.56
10
59.99
59.45
10
60.00
59.63
Total
5400.45
45.29
Total
5201
60.18
Prop
Efficiency and model utility deep models. ScaleGUN can also achieve superior unlearning performance on deep models, such as decoupled models and spectral GNNs (Chien et al. [2200] He al. 2022). despite lacking certified guarantees. Table 3 presents ScaleGUN's performance on decoupled models, utilizing a structure where two-hop propagations are followed by a two-layer
Multi-Layer Perceptron (MLP). The formulation is expressed as Y = LogSoftmax (a (Pa (W))) We introduce perturbation BW W to each learnable parameter W, utilizing Adam as the optimizer.
The propagation cost is excluded as its pattern consistent with that in Table | This suggests that ScaleGUN can be employed in shallow net- works to achieve higher model accuracy when certified guarantee
Table 3: Test accuracy (%), total unlearning cost (s) per batch edge removal for decoupled models.
oghn-products
aghn-paperssIIIM
not required. Further- more, spectral GNNs are a significant subset of GNNs rooted in spectral graph theory, known for their superior expressive power. We also ap- ply ScaleGUN on the spectral GNN model to demonstrate its versatility in Appendix
N(x10*)
Retrain
ScaleGU
N(xx10))
Retrain
ScaleGUNN
76.16
74.25
63.39
63.13
74.15
74:25
63.05
74,16
74.24
63.13
62.97
74.12
74.24
63.05
62.89
74.18
74:23
62.80
74.10
74.22
62.85
62.72
Total
174.23
14.19
Total
7958.83
10.49
Edge unlearning efficacy. We adopt the task of forgetting adversarial data to evaluate ScaleGUN's edge unlearning efficacy. First, we introduce the measurement for edge unlearning efficacy. Specifi- cally, introduce adversarial edges into the graph, ensuring the terminal nodes bear different labels.

---

Published as a conference paper at ICLR 2025
Table 4: Deleted Data Replay Test:
The ratio of incorrectly labeled nodes, rd, Fas after unlearning.
ru
HeEMa18 [Va]
(%, D)
[1EV M
(%. 4)
Model
Cora
ogbn-arxiv
ogbn-products
Cora
ogbn-arxiv
ogbn-products
Origin
100
90.72
100
52.13
1.01
45.59
Retrain
0
0
0
0
CGU
0
0
0
0.09
0
ScaleGUN
0
0
0
0,08
These adversarial edges are used to deceive the model into making incorrect predictions, diminishing its performance. The objective of unlearning is to delete these adversarial edges and recuperate the model's 's performance. With the removal of more adversarial edges, the accuracy of unlearning methods is expected to rise, following the trend of retraining. For Cora, we randomly selected 500 edges connecting two distinct labeled terminal nodes to serve as adversarial edges. However, this straightforward method proves inadequate in affecting model accuracy for large graphs. Consequently, we adopt a more refined approach tailored for large graphs, which is detailed in Appendix C illustrates how the model accuracy varies as the number of removed adversarial edges increases. The results affirm that CGU, CEU, and ScaleGUN exhibit effectiveness in edge unlearning.
Figure 3
Node unlearning efficacy. To measure the node unlearning efficacy, we conduct Deleted Data Replay Test on Cora, ogbn-arxiv, arxiv, and ogbn- products for linear models in Table 4 First, we choose a set of nodes Va to be unlearned from the training and add 100-dimensional binary features to the original node features. For nodes in Vd these additional features are set to I; for other nodes, they are set to O. The labels of nodes in V.J are assigned to new class An effective unlearning method is expected not to predict the unlearned nodes as class after unlearning Va, meaning that Jt o C for i E Va. We report the ratio of incorrectly labeled nodes ra [(iEVal0: in the original model (which does [Val
not unlearn any nodes) and target models after unlearning. We set [Va = 100, 125, 50000 for Cora, ogbn-arxiv, and ogbn-products, respectively. We also report ra HoEV|e=e| to assess whether the impact of the unlearned nodes is completely removed from the graph. The results show that ScaleGUN successfully removes the impact of the unlearned nodes, with only a slight discrepancy compared to retraining. Moreover, Attack (MIA), however, as argued in (Chien et al. 2022a), MIA is not suitable to evaluate graph unlearning efficacy. We defer the MIA results Appendix
[V]
also evaluate unlearning efficacy by Membership Inference
Effects of Tmax. ScaleGUN introduces the parameter Fmax to manage the approximation er- ror. To investigate the impact of Tmax, we conduct experiments on the ogbn-arxiv dataset, re- moving 100 random edges, one at a time. Table 5 displays the initial model accuracy before any removal, total unlcarning cost, propagation cost per edge removal, and average number of retraining throughout the unlcarning process. Decreasing Tmax improves model accuracy and reduces the approximation error, leading to fewer retraining times and lower unlearning costs. Beyond a certain threshold, the model accuracy stabilizes, and the unlearning cost is minimized. Further reduction in Tmax is unnecessary as it would increase the initial computational cost. Notably, the propagation cost remains stable, consistent with Theorem 3.3] which indicates that the average propagation cost is indepen- dent of Tmax. Table
Table 5: Initial test accuracy, total unlearning cost and propagation cost per edge removal by varying Tmax on ogbn-arxiv with linear model.
Finxx
le:5
lc-7
1c-9
Se-10
1e- 10
le-15 15
Acc (9)
55.23
57.84
57.84
57.84
57.84
57.84
Total (s)
3.30
3.60
3.31
1.81
0.92
0.93
that selecting an appropriate r "max can achieve both high model utility and efficient unlearning.
Prop (6)
0.72
0.76
0.75
0.71
0.77
0.77
#Retrain
100
100
85.33
56.67
0
CONCLUSION
This paper introduces ScaleGUN, the first certified graph unlearning mechanism that scales to billion-edge graphs. We introduce the approximate propagation technique from decoupled models into certified unlearning and reveal the impact of approximation error on the certified unlearning guarantees by non-trivial theoretical analysis. Certified guarantees established for all three graph unlearning scenarios: node feature, edge, and node unlearning. Empirical studies of ScaleGUN on real-world datasets showease its efficiency, model utility, and unlearning efficacy in graph unlearning.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGEMENTS
The work was partially done at Gaoling School of Artificial Intelligence, Beijing Key Laboratory of Big Data Management and Analysis Methods, MOE Key Lab of Data Engineering and Knowledge Engineering, and Pazhou Laboratory (Huangpu), Guangzhou, Guangdong 510555, China. This research was supported in part by National Science and Technology Major Project (2022ZD01 14802), by National Natural Science Foundation of China (No. 92470128, No. U2241212), by Beijing Out- standing Young Scientist Program No. N...BJWWYJHH12011 1019000020098, by Huawei -eneein University joint program on Information Retrieval. We also wish to acknowledge the support provided by the fund for building world-class universities (disciplines) of Renmin University of China, by Engi- neering Research Center of Next-Generation Intelligent Search and Recommendation, Ministry of Education, by Intelligent Social Governance Interdisciplinary Platform, Major Innovation & Planning Interdisciplinary Platform for the "Double-Firs" Class" Initiative, Public Policy and Decision-making Research Lab, and Public Computing Cloud, Renmin University China.
REFERENCES
Martin Abadi, Andy Chu, Ian 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.
Reid Andersen, Fan Chung, and Kevin Lang. Local graph partitioning using pagerank vectors. In 2006 47th Annual IEEE Symposium on Foundations of Computer Science (F)) pp- 475-484- 486. IEEE, 2006.
Albert-Lásztó Barabási. Network science. Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences, 37 (71(1)8))20120335, 2013.
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. In Proceedings of the 2022 ACM SIGSAC Conference Computer and Communications Security, pp. 199--113, 2022.
Ming Chen, Zhewei Wei, Bolin Ding, Yaliang Li, Ye Yuan, Xiaoyong Du, and Ji-Rong Wen. Scalable graph neural networks via bidirectional propagation. Advances in neural information processing systems, 13:4466614 2020.
Jiali Cheng, George Dasoulas, Huan He, Chirag Agarwal, and Marinka Zitnik. Gnndelete: A general strategy for unlearning in graph neural networks. arXiv preprint arXiv:2302. 13406, 2023.
Wei-Lin Chiang, Xuanqing Liu, Si Si, Yang Li, Samy Bengio, and Cho-Jui Hsieh. Cluster-gen: An efficient algorithm for training deep and large graph convolutional networks. In Proceedings of the 25th ACM SIGKDD international conference on knowledge discovery & data mining, pp. 257-266. 2019.
Eli Chien, Jianhao Peng, Pan Li, and Olgica Milenkovic. Adaptive universal generalized pagerank graph neural network. arXiv preprint arXiv:2006.07988. 2020.
Eli Chien, Chao Pan, and Olgica Milenkovic. Certified graph unlearning. arXiv preprint S1ti::2206.91444 2022a.
Eli Chien, Chao Pan, and Olgica Milenkovic. Efficient model updates for approximate unlearning of graphestructured data. In The Eleventh International Conference on Learning Representations, 2022b.
11

---

Published as a conference paper at ICLR 2025
Eli Chien, Wei-Ning Chen, Chao Pan, Pan Li, Ayfer Ozgur, and Olgica Milenkovic. Differentially private decoupled graph convolutions for multigranular topology protection. Advances in Neural Information Processing Systems, 36, 2024.
Weilin Cong and Mehrdad Mahdavi. Grapheditor: An efficient graph representation learning and unlearning approach.
Weilin Cong and Mehrdad Mahdavi. Efficiently forgetting what you have learned in graph represen- tation learning via projection. In International Conference on Artificial Intelligence and Statistics, pp. 6703. PMLR, 2023.
Quang- Vinh Dang. Right to be forgotten in the age of machine learning. In Advances in Digital Science: ICADS 2021, pp. 403-411. Springer, 2021.
Buang-Vinh
Johannes Gasteiger, Stefan WeiBenberger, and Stephan Günnemann. Diffusion improves graph learning. Advances in neural information processing systems, 32, 2019.
Antonio Ginart, Melody Guan, Gregory Valiant, and James Y Zou. Making ai forget you: Data deletion in machine learning. Advances in neural information processing systems, 32, 2019.
Aditya Golatkar, Alessandro Achille, and Stefano Soatto. Eternal sunshine of the spotless net: Selective forgetting in deep networks. In Proceedings of the IEEE/CVF Conference on Computer Vision and Puttern Recognition, pp. 9304-9312, 2020.
Chuan Guo, Tom Goldstein, Awni Hannun, and Laurens Van Der Maaten. Certified data removal from machine learning models. arXiv preprint arXiv:1911.0303: 2019.
Xingzhi Guo, Baojian Zhou, and Steven Skiena. Subset node representation learning over large dynamic graphs. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, pp. 516-526, 2021.
Mingguo He, Zhewei Wei, and Ji-Rong Wen. Convolutional neural networks on graphs with chebyshev approximation, revisited. Advances in neural information processing systems, 35: 7264-7276, 2022.
Xiangnan He, Kuan Deng, Xiang Wang. Yan Li, Yongdong Zhang, and Meng Wang. Lightenn: Simplifying and powering graph convolution network for recommendation. Proceedings of the 43rd International ACM SIGIR conference research and development in Information Retrieval, pp. 639-648, 2020.
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovee. Open graph benchmark: Datasets for machine learning on graphs. Advances in neural information processing systems, 13:22118-22 13:22118-22133, 2020.
Masayuki Karasuyama and Ichiro Takeuchi. Multiple incremental decremental learning of support vector machines. IEEE Transactions on Neural Networks, 1048 1059, 2010.
Thomas N Kipf and Max Welling. Semi-super classification with graph convolutional networks. arXiv preprint arXiv: 02907, 2016.
Pang Wei Koh and Percy Liang. Understanding black-box predictions via influence functions. In International conference on machine learning, pp. 1885-1894. PMLR, 2017.
Pan Li, Chien, and Olgica Milenkovic. Optimizing generalized pagerank methods for seed-expansion community detection. Advances Neural Information Processing Systems, 32, 2019.
Xunkai Li, Yulin Zhao, Zhengyu Wu, Wentao Zhang, Rong-Hua Li, and Guoren Wang. Towards effective and general graph unlearning via mutual evolution. arXiv preprint 1766 2024.
Julian McAuley, Christopher Targett, Qinfeng Shi, and Anton Van Den Hengel. Image- based recommendations on styles and substitutes. In Proceedings of the 38th international ACM SIGIR conference on research and development in information retrieval, pp. 43-52, 2015.
12

---

Published as a conference paper at ICLR 2025
Iyiola E Olatunji, Wolfgang Nejdl, and Megha Khosla. Membership inference attack graph neural networks. 2021 Third IEEE International Conference on Trust, Privacy and Security in Intelligent Systems and Applications (TPS-ISA), pp. 11-20. IEEE, 2021.
Chao Pan, Eli Chien, and Olgica Milenkovie. Unlearning graph classifiers with limited data resources. In Proceedings of the ACM Web Conference 2023, pp. 716-726, 2023.
Jiezhong Qiu, Jian Tang, Hao Ma, Yuxiao Dong, Kuansan Wang, and Jie Tang. Deepinf: Social influence prediction with deep learning. In Proceedings of the 24th ACM SIGKDD international conference on knowledge discovery & data mining, pp. 21 2110-2119, 2018.
Anwar Said, Tyler Derr, Mudassir Shabbir, Waseem Abbas, and Xenofon Koutsoukos, A survey of graph unlearning. arXiv preprint arXiv:2310.02164, 2023.
Sina Sajadmanesh, Ali Shahin Shamsabadi, Aurélien Bellet, and Daniel Gatica-Perez. (GAP): Differentially private graph neural networks with aggregation perturbation. In 32nd USENIX Security Symposium (USENIX Security 23), pp. 3223-32224220 2023.
Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rad Collective classification in network data. Al magazine, 29(3):93-93, 2008
Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. arXiv preprint arXiv: 10903, 2017.
Cheng-Long Wang, Mengdi Huai, and Di Wang. Inductive graph unlearning. arXiv preprint arXiv:2304.030093, 2023.
Hanzhi Wang, Mingguo He, Zhewei Wei, Sibo Wang, Ye Yuan, Xiaoyong Du, and Ji-Rong Wen. Approximate graph propagation. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, pp. 1686-1696, 2021.
Yifei Wang and Mert Pilanci. Polynomial- -ime solutions for relu network training: A complexity classification via max-cut and zonotopes. CoRR, abs/2311. 10972, 2023. doi: 10.48550/ARXIV. 2311.10972. URL httpt::t:///ett org.10..01...0 48550/ wtt.555/aXX..2111111
Mark Weber, Giacomo Domeniconi, Jie Chen, Daniel Karl Weidele, Claudio Bellei, Tom Robin- son, and Charles E Leiserson. Anti-money laundering in bitcoin: Experimenting with graph convolutional networks for financial forensics. arXiv preprint Xrvi (tti:/990..000 /908.0259, 2019.
Felix Wu, Amauri H. Souza Jr., Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Q Weinberger. Simplifying graph convolutional networks. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference Machine Learning. ICML 2019, 9- 15 June 2019, Long Beach, California, USA, volume 97 of Proceedings of Machine Learning Research, pp. 6861-6871. PMLR, 2019.
Jiancan Wu, Yi Yang, Yuchun Qian, Yongduo Sui, Xiang Wang, and Xiangnan He. Gif: A general graph unlearning strategy via influence function. In Proceedings of the ACM Web Conference 2023, pp. 651-661, 2023a.
Kun Wu, Jie Shen, Yue Ning, Ting Wang, and Wendy Hui Wang. Certified edge unlearning for graph neural networks. In Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 2606-2617, 2023b.
Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka. Representation learning on graphs with jumping knowledge networks. In International conference on machine learning, pp. 5453-5462. PMLR, 2018.
Mingji Yang, Hanzhi Wang, Zhewei Wei, Sibo Wang. and Ji-Rong Wen. Efficient algorithms for personalized pagerank computation: A survey, IEEE Transactions on Knowledge and Data Engineering, 2024.
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.
13

---

Published as a conference paper at ICLR 2025
Hanqing Zeng, Hongkuan Zhou, Ajitesh Srivastava, Rajgopal Kannan, and Viktor Prasanna. Graph- saint: Graph sampling based inductive learning method. arXiv preprint arXiv:1907.04991 2019.
Hongyang Zhang, Peter Lofgren, and Ashish Goel. Approximate personalized pagerank on dynamic graphs. In Proceedings of the 22nd ACM SIGKDD international conference on knowledge discovery and data mining. pp. 5315-1324, 2016.
Yanping Zheng, Hanzhi Wang. Zhewei Wei, Jiajun Liu, and Sibo Wang. Instant graph neural networks for dynamic graphs. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 2605-2615, 2022.
A OTHER RELATED WORKS
Machine unlearning, first introduced by Cao & Yang (0015), aims to eliminate the impact of selected training data from trained models enhance privacy protection.
Exact unlearning. Exact unlearning seeks to generate a model that mirrors the performance of a model retrained from scratch. The straightforward method is to retrain the model upon data removal request, which is often deemed impractical due to high computational and temporal costs. To bypass the burdensome retraining process, several innovative solutions have been proposed. Ginart et al. (2019) focused on k-means clustering unlearning, while MhilleKarasuyama & Takeuchi (2010) addressed the unlearning problem for support vector machines. [Bourtoule al. (2021) proposed the SISA (sharded, isolated, sliced, and aggregated) method, which partitions the training data into shards and trains on each shard separately. Upon a removal request, only the affected shards need to be retrained, thus enhancing the performance significantly. GraphEraser (Chen et al. 2022) extended the SISA approach to
data. Projector and GraphEditor (Cong & Mahdavi 2023) address exact unlearning for linear GNNs with Ridge regression as their objective.
Approximate unlearning. Approximate unlearning, on the other hand, introduces probabilistic or heuristic methods to reduce unlearning costs further. Within this realm, certified unlearning, the primary subject of this study, stands subclass of approximate methods distinguished by its probabilistic assurances. Besides the certified unlearning works previously mentioned, Pan et al. (2023) extended the certified unlearning to graph scattering transform. GIF (Wu et al.) 2023a) de- veloped graph influence function based on influence function for unstructured data (Koh & Liang 2017). Golatkar al. (2020) proposed heuristic-based selective forgetting in deep networks. GN- NDelete (Cheng et al. 2023) introduced novel layer-wise operator for optimizing deleted edge consistency and neighborhood influence in graph unlearning. Concurrently, [Li et al.) (2024) achieved effective and general graph unlearning through mutual evolution design, and [Wang et al. (2023) proposed the first general framework for addressing the inductive graph unlearning problem.
Differentially Privacy v.s. Certified unlearning. Differentially Privacy (DP) aims to ensure that an adversary cannot infer whether the model was trained on the original dataset or the dataset with any single data sample removed, based on the model's 's output. Certified unlearning aims to remove the impact of the specifie data sample(s) so that the model behaves as if the sample was never included. Thus, a DP model inherently provides certified unlearning for any single data sample. However, most DP models suffer from performance degradation even for loose privacy constraints (Abadi et al. 2016, Chaudhuri et al., (01T). Certified unlearning can balance model utility and computational cost, presenting an alternative to retraining and DP (Chien et al., 2022b). This also explains the growing interest in certified unlearning privacy protection demands rise. Additionally, there some nuances between DP and certified unlearning. For example, DP does not obscure the total dataset size and the number of deletions any given model instance has processed, but this should not be leaked in certified unlearning (Ginart et al. 2019).
B DETAILS OF CERTIFIABLE UNLEARNING MECHANISM
B. PRACTICAL ASPECTS
Least-squares and logistic regression on graphs. Similar to (Chien et al., 2022a), our un- learning mechanism achieve certifiable unlearning with least-squares and binary logistic
14

---

Published as a conference paper at ICLR 2025
regression. ScaleGUUN performs exact unlearning for least-squares since the Hessian of loss function is independent of w. For binary logistic regression, we define the empirical risk as I(e] Zw, e Y,) = - (o ee Zw)). where a denotes the sigmoid function. As shown in (Guo al., 2019 Chien et al. 2022a), Assumption holds with c 1, 71 = 22 1/4, c1 1 for logistic regression. Following (Chien et al., 2022a). ScaleGUN can adapt the "one-versus-all other classes" strategy for multiclass logistic regression.
Batch unlearning. In the batch unlearning scenario, multiple instances may be removed at a time. In the worst-case bounds of the gradient residual norm, the component attributable to approximation error remains unchanged across three kinds of unlearning requests and for any number of unlearning instances. This stability is due tion eπror 61 does not vary with the number of removed instances. Regarding the component related to unlearning, which is mainly determined by |ie, Z'ezll, we can establish the corresponding bounds by aggregating the bounds for each unlearning instance, utilizing the Minkowski inequality. The data-dependent bound remains unchanged and can be computed directly.
lazy local propagation framework, which ensures the approxima-
Limitations of existing certified unlearning mechanisms. The existing certified unlearning studies, including ScaleGUN, are limited to linear models with strongly convex loss function. Achieving certified graph unlcarning in nonlinear models is a significant yet challenging objective. Existing approximate unlearning methods deep models are heuristics without theoretical guarantees (Go latkar et al.) 2020, McAuley et al., 2015). On the one hand, the theoretical foundation of existing certified un unlearning mechanisms is the Newton update. However, the thorough examination of the Newton update in deep networks remains an unresolved issue (Xu et al.) 2018). Koh & Liang (0177) demonstrates that the Newton update performs well in non-convex shallow CNN networks. However, performance may decline in deeper architectures as the convexity of the loss function is significantly compromised (Wu et al., 2023a). On the other hand, note that a certified unlearning model is ap- proximately equivalent to retraining in terms of their probability distributions. This indicates that the unlearning model must be able to approximate the new optimal point of empirical risk within a certain margin of error after data removal. However, existing studies (Wang & Pilanci] 2023) have proven that even approximating the optimal value of a 2-layer ReLU neural network is NP-hard in the worst cases. Therefore, the path to certified unlearning in nonlinear models remains elusive, even for unstructured data. While ScaleGUN cannot achieve certified unlearning for deep models, our empirical results demonstrate that ScaleGUN can achieve competitive model utility using deep models as backbones when certified guarantees are not required, as shown in Table 3 and Table [3] In summary, ScaleGUN can perform certified unlearning for linear GNNs and serves an effective heuristic unlearning method for deep models.
Potential improvements and future directions. As suggested in (Guo et al., 2019 Chien et al. 2022a), pretraining nonlinear feature extractor on public datasets can significantly improve overall model performance. If no public datasets are available, feature extractor with differential privacy (DP) guarantees can be designed. DP-based methods provide privacy guarantees for nonlinear models, indicating the potential to leverage DP concepts facilitate certified unlearning in deep models. We also observe that ScaleGUN is capable of data removal from deep models to a certain extent (see Figure 7 in Appendix C. even without theoretical guarantees. This observation suggests the possibility of formulating more flexible certification criteria to assess the efficacy of current heuristic approaches.
B.2 DETAILS SEQUENTIAL UNLEARNING ALGORITHM
According to the privacy requirement and Theorem 2.1 we select the noise standard deviation a,
privacy parameters e, ō and compute the "privacy budget" / 22log(1.)))) Initially, compute the approximate embeddings by the lazy local propagation framework and train the model from scratch. For each unlearning request, update the embeddings and then employ our unlearning mechanism. Specifically, compute the first component of the data-dependent bound, i.c., 2c, || R
in Theorem 4.5 and accumulate the second component 72 | H. / A| for each unlearning request. Once the budget is exhausted, retrain the model from scratch. Note that do not need to re- co-prpaagat even when retraining the model. Algorithm| T provides the pseudo-code of ScaleGUN, where the removal request R2 can be instance batch of instances.
15

---

Published as a conference paper at ICLR 2025
Algorithm 1: ScaleGUN
Input: Graph data = (X, Y, Y.A), A), sequence removal requests = {Ri, ... RE loss
function parameters I., [wee) Tmax: a, 22,6,
Compute the embedding matrix 2 by Algorithm 2 with initialized ()) and {r(0}
w f- the model trained on the training set of 'D with the approximate embeddings Z; Accumulated unlearning error / 0:
for R; E R do
Z', R the embedding matrix updated by the lazy local propagation framework and the corresponding residue matrix according to the removal request R;;
D' +- the updated dataset according to R;;
A VL(W, D L(w, D');
Hw + V2C(w, D));
8 +- 72
Z'H Z'H 1
3 + 2e || R ae/ (l0((/))/ then
10
w the model retrained on the training set of D':
11
8+ 0;
13
else
w + H A:
14
Table 6: Statistics of datasets.
Datasct
n
m
[C]
train/val/test
Cora
2708
5278
1433
1208/500/1000
Citeseer
3327
4552
3703
1827/500/ 1000//000/0000
Photo
7650
119081
745
6150/500/ 1000
ogbn-arxiv
169,343
1,166,243
40
128
20941/29799/48603
ogbn-products
2,449.029
61,859,140
47
128
1966115/39823222113391
ogbn-papers100k
111,059,956
1,615,685,872
172
128
C DETAILS OF EXPERIMENTS AND ADDITIONAL EXPERIMENTS
C.I EXPERIMENTS SETTINGS
We use cumulative power iteration to compute exact embeddings for the retrain method, CGU, and CEU. Each dimension of the embedding matrix is computed in parallel with total of 40 threads. We adopt the "one-versus-all strategy to perform multi-class node classification following (Chien et al. (002a)). We conduct experiments on a machine with an Intel(R) Xeon(R) Silver 4114 CPU @ 2.20GHz CPU, 1007GB memory, and Quadro RTX 8000 GPU in Linux OS. The statistics of the datasets are summarized Table 6 Table 7 and Table g summarize the parameters used the linear and deep experiments, respectively. The parameters consistently utilized across all methods.
Ad Adversarial edges selection. In Figure we show the model accuracy as the number of removed adversarial edges increases. We add 500 adversarial edges to Cora, with 5 random edges being removed in each removal request. For ogbn-arxiv, cebbn-podducs, and ogbn-papers papers100Ms 100M, we add 10 adversarial edges, with batch-unlearning size 100, 200, and 2000, respectively. The details of selecting adversarial edges are as follows. For the Cora dataset, we randomly select edges connecting two distinct labeled terminal nodes and report the accuracy on the whole test set. For large datasets, randomly selecting adversarial edges proves insufficient to impact model accuracy. Hence, we initially identify small set of nodes from the test set, then add adversarial edges by linking these nodes to other nodes with different labels. Specifically, we first randomly select 2000 nodes from the original test set create new test set V,. We then repeat the following procedure until collect enough
16

---

Published as a conference paper at ICLR 2025
Table 7: Parameters used in the linear model experiments.
Dataset
Tmax
Cora
1e-7
le-2
0.1
Citeseer
le-8
le-2
0.1
Photo
1e-8
le-4
ogbn-arxiv
Ic-8
lc-4
0.1
ggbn-proddctt
Ic-8
lc-4
0.1
1oon-paperss00M.,
Ic-9
1c-8
15.0
Table 8: Parameters used in the deep model experiments.
Dataset
À
a
learning rate
hidden size
batch size
ogbn-arxiv
5c-4
0.1
lc-3
1024
1024
lc-4
0.01
lc-4
1024
512
agbn-papers100M
le-8
5.0
le-4
256
8192
edges: randomly select node from Vs, randomly select node from the entire node set V, and if u and have different labels, we add the adversarial edge (u, u) to the original graph.
Vulnerable edges selection. In Table D we show the unlearning results in large graph datasets. For these datasets, we selected vulnerable edges connected low-degree nodes order observe changes in test accuracy after unlearning. The details of selecting vulnerable edges are as follows. We first determine all nodes with a degree below specified threshold in the test set. Specifically, the threshold is set to 10 for the ogbn-arxiv and ogbn-products datasets, and 6 for the ogbn-papers 100M dataset. We then shuffle the set of these low-degree nodes and iterate over each node v: For each node v, if any of its neighbors share the same label as the corresponding edge is included in the unlearned edge set. The iteration ends until we collect enough edges.
C.2 ADDITIONAL EXPERIMENTS ON NODE FEATURE, EDGE AND NODE UNLEARNING.
Node feature and node unlearning experiments. We conduct experiments node feature and node unlearning for linear models and choose Cora, ogbn-arixv. and ogbn- bebbn-paperslne 100M as the representative datasets. Following the setting in (Chien et al. 2022b), set ó le 4. Table 9 shows the model accuracy, average total cost, and average propagation cost per removal on Cora and ogbn-arxiv. For Cora, remove the feature of one node time for node feature unlearning tasks. While for ogbn-arxiv, we remove the feature of 25 nodes. The node unlearning task is set in the same way. The results demonstrate that ScaleGUN achieves comparable model utility with retraining while significantly reduce the unlearning costs in node feature and node unlearning tasks.
100errs00MM
Edge unlcarning results on small graphs. Table presents test accuracy, average total unlearning cost, and average propagation cost for edge unlearning linear models applied to small graph datasets. For each dataset, 2000 edges removed, with edge removed time. The table reports the initial and intermediate accuracy after every 500-edge removal. this experiment, we also set 1e following the setting in (Chien al. 2022b). ScaleGUN is observed maintain competitive accuracy when compared to CGU and CEU while notably reducing both the total and propagation costs. It is important to note that the difference in unlearning cost (Total- among the three methods is relatively minor. However, CGU and CEU incur the same propagation cost as retraining, which is 10x 30x higher than that of ScaleGUN.
Model utility when removing more than 50% training nodes. To validate the model utility when the unlearning ratio reaches 50%. we remove x 1 and 10s training nodes/features from ogbn-arxiv and
in Figure 4 The batch-unlearning sizes are set to 25 and 10 nodes/features. respectively. We set 8 = le 4 in the experiment, following the setting in (Chien et al., 2022b). The results show that ScaleGUN closely matches the retrained model's utility even when half of the training nodes/features removed.
17

---

Published as a conference paper at ICLR 2025
Table 9: Test accuracy (%), total unlearning cost (s) and propagation cost (s) per node feature/feature removal for linear models on Cora and ogbn-arxiv.
Fenture Unlcaming
Node Unkearing
Cora
ogbo- SEATV
Cura
oghn-araiv
N
Retrain
CGU
StaleGUN
N
Retrain
OGU
ScaleGUN
NV
Retrain
CGU
ScalGGUN
.V
Retrain
CGU
ScaleGUNN
$4.9
54.9
84.9
57.84
57.84
57.84
84.9
84.9
54.9
0
57.84
57.84
57.84
57.85
200
63.5
07.88
67.83
4000
82.43
81.58
81.53
50
07.83
07.83
67.88
600
83.03
81.73
61.73
57.84
07.84
67.84
600
81.57
50.7
50.7
75
07.84
67.84
800
81.9
77.83
77.83
100
57.83
07.85
67.84
800
80.1
76.7
76.7
100
07.83
07.64
67.84
2:
0.46
0.20
0.30
T:
2.59
2.33
1.49
2:
0.54
0.20
0:11
2:
2.86
2.04
1.38
0.10
0.01
1.55
1.56
0.77
75
0.10
0.10
0.01
75
1.06
1.43
0.81
Table 10: Test accuracy (%), total unlearning cost (s), and propagation cost (s) per one-edge removal for linear models (small graphs).
Cora
Caasser
Photo
N10600)
Retrain
CGG
CFE
ScoleGUNN
N(x600)
Retrain
CGU
CFE1
ScaleGUUN
N 500)
Retroin
CGG
CFEUU
StaleGUN
0
85.30
84.10
84,10
$4.10
79.30
78.30
78.30
78.90
91.67
89.93
$9.93
89.93
1
85:30
83.30
83.30
83.50
78.60
78.37
78.37
78.37
91.60
89:90
89.90
89 20
2
84.10
82.30
82.30
82.30
78.30
75.00
78.00
78.00
91.60
69.90
89.50
82.40
81.40
81.40
81.40
77,60
77.10
77.10
77.10
91.63
89.67
59.67
Total
0.74
0.28
0.32
0.12
Total
0.99
0.81
0.76
0.55
Total
3.08
0.35
0.40
0.07
Prop
0.15
0.15
0.17
0.01
Prop
0.34
0.29
0.27
0.03
Prop
0.31
0.25
0.29
0.01
C.3 PARAMETER STUDIES.
Trade-off between privacy, model utility, and unlearning efficiency. According to Theorem 2.1 and our sequential unlearning algorithm, there is trade-off amongst privacy. model utility, and unlearning efficiency. Specifically, e and controls the privacy requirement. To achieve (e, --eertife unlearning, we can adjust the standard deviation of the noise b. An overly large introduces too much noise and may degrade the model utility. However, a smaller a may lead to frequent retraining and increase the unlearning cost due to the privacy budget constraint. We empirically analyze the trade-off between privacy and model utility, by removing 800 nodes from Cora, one at a time. To control the frequency of retraining, we fix or = 0.1 and vary the standard derivation a of the noise b. The results are shown in Figure 5 Here, we set = 1/ #nodes and Tmax = 10 We observe that the model accuracy decreases as a increases (i.e., c decreases), which agrees with our intuition.
Cora Node unlearning
0.8
0.7
0.6
0.5
8-05
0.4
Varying batch-unlearning size. To validate the model efficiency and model utility under vary- ing batch-unlearinng sizes, we vary the batch- unlearning size in (1x 10 3x xx 10 5x 10 10x 109) for ogbn-products and {2 x 10 10 x 103 50x 10²} for ogbn-papers Pompers100Ma 100M in Table Following the setting in (Chien et al. 20226).
0.1
200 300 400 500
Number of removals
Figure 5: Varying a (ae 0.1 fixed): Test accu- racy v.s. the number of removed nodes on Cora.
4. The average total cost and propagation cost for five batches and the accuracy after unlearning five batches are reported. For comparison, the corresponding retraining results are provided, where x 1 and 2 x 10s nodes removed per batch for prondutoducts and ogbn-papers 100M, respectively. ScaleGUN maintains superior efficiency over retraining, even when the batch-unlearning size becomes 4%-5% of the training set in large graphs (e.g., 50 10 nodes in batch out of 1.2 x 10 total training nodes of ogbn-papers pap--spppeo)) 100M). The test accuracy demonstrates that ScaleGUN preserves model utility under varying
we set
sizes.
18

---

Published as a conference paper at ICLR 2025
orbnneraiv
oybn-arsly
oybn-producct
ogbe-products
Rotiah Sc3lGUN
Rotroin
Rotiinn ScalSOUN
50
ScoloGUN
Sca
Accuracy 166
Aec Accuracy 1901
10
3
50
1=30
20 a
2n20" a removed nades
removed features
removed nodes
removed features
Figure 4: Unlearning more than 50% of training nodes/features: Test accuracy on ogbn-arxiv and ogbn-products.
ScaleGuN Worst case nome
COL: Morst-cast room
CEU: WAr norm
ScaleGuN: Dara degendent norm
CGL: Qata-dependent nomm
CEU: Daca dependeer norm
ScaleGUN: The norm
COL Thue norm
CRU: Thue worm
102
107
10"
30'
109
10a
207
10a
207
10a
10"
200
4.00
600
800
100
300
400
500
200
400
600
800
Node feature unlearning
Edge unleariing
Node unlearming
Figure 6: Comparison of the bounds of the gradient residual: Worst-case bound, data-dependent bound and the true value on Cora dataset for ScaleGUN, CGU and CEU.
C.4 CGU, CEU AND SCALEGUN'S BOUNDS OF THE GRADIENT RESIDUAL.
Figure 6 shows the worst-case bound, data-dependent bound, and the true value of the gradient residual for ScaleGUN, CGU, and CEU on the Cora dataset. For ScaleGUN, CGU and CEU, the worst-case bounds and the data-dependent bounds validly upper bound the true value, and the worst- case bounds are looser than the data-dependent bounds. This confirms the correctness of the bounds for all methods. The worst-case bound of ScaleGUN is larger than that of CGU and slightly larger than that of CEU. This difference arises because ScaleGUN introduces approximation error, which is not present in CGU and CEU. However, note that this large worst-case bound does not impact the update efficiency ScaleGUN, as decisions on retraining during sequential unlearning rely on data-dependent bounds rather than worst-case bounds. In edge and node unlearning scenarios, the data-dependent bound of ScaleGUN is slightly larger than that of CGU in the early stages of sequential unlearning. This occurs because the approximation error introduced by ScaleGUN dominates the model error when only a small amount of data has been unlearned. As the number of unlearning requests increases, the unlearning error accumulates, eventually dominating the model error, while the approximation error does not accumulate since we meet the approximation error bound in each unlearning step. Consequently, the data-dependent bound of ScaleGUN becomes comparable that of CGU over time. In the edge unlearning scenario, the data-dependent bound of CEU is larger than that of both ScaleGUN and CGU, primarily due CEU employing different unlearning mechanism. The true norm of ScaleGUN is slightly larger than that of CGU in edge and node unlearning scenarios, again due to the introduction of approximation error by ScaleGUN.
C.5 ADDITIONAL VALIDATION OF UNLEARNING EFFICACY.
Unlearning efficacy deep models. We also evaluate the unlearning efficacy for deep models. Figure 7 illustrates how the model accuracy changes as the number of removed adversarial edges increases. The adversarial edges are the same as those used for linear models, selected according to the method detailed in Appendix C.I The deep models employed are consistent with those in Table 3 defined as Y = LogSoftmax ( (P²x W). The results indicate that ScaleGUN's performance improves with the removal of more adversarial edges, behaving similarly retraining, This highlights ScaleGUN's s ability to effectively unlearn adversarial edges, even in shallow non-linear networks.
Membership Inference Attack (MIA). As noted in (Chien al., 2022b), MIA has distinct design goals from unlearning. Even after unlearning a training node, the attack model may still recognize the unlearned node in the training set if there are other similar training nodes.
19

---

Published as a conference paper at ICLR 2025
Table 11: Varying batch-unles seich-unlearning size: Test accuracy (%), average total cost (s), and average propagation cost (s) per batch node removal.
ogba-products
ogbn-papers 100p 10M
Metric
ScaleGUN
Retrain
ScaleGUN
Retrain
1 10
10
x 10
10
10
x 10
10 10*
10
10*
Acc
56.25
56.25
56.07
56.14
56.24
39.49
59.71
58.76
59.45
Total
24.00
39.07
45.58
56, 14
92.44
54,85
352.35
657.99
5201. 08
Prop
21.97
37.25
43.91
54.72
91.54
15.49
313.11
621.62
5139.09
ogbn-arxiv
oghn-products
Sygbn-appess0000
0.60
Retrain ScaleGUN
0.76
Retrain
Retrain
ScoleGUN
ScaleGUN
0.58
Accuracy (%)
Accuracy (%)
0.74
Acturacy
0.558
0.62
0.73
0.54
0.72
0.61
0.71
0.60
0.70
0.59
2000 4000 5000 8000 10000 removed adversarial edges
2000 4000 6000 8000 10000
1000
2000 3000 4000 5000
# removed adversarial edges
removed adversarial edges
Figure 7: Comparison of unlearning efficacy for deep model: Model accuracy v.s. the number of removed adversarial edges.
Nonetheless, we follow (Chien et al.] 2022b; Cheng et al. 2023) to conduct MIA (Oltunji ctt al.] 202I) on Cora and ogbn-arxiv in Table 12 The core idea is that if the target model effectively unlearns training node, the MI attacker will determine that the node is not probability of the unlearned nodes decreases.
present in the training set, i.e., the presence We remove 100 training nodes from Cora and 125 from ogbn-arxiv. We then report the ratio of the presence probability of these unlearned nodes between the original model (which does not unlearn any nodes) and target models after unlearning. A reported ratio greater than 1.0 indicates that the target model successfully removed some information about the unlearned nodes, with higher values indicating better per- formance. Table 12] indicates that ScaleGUN offers preaecciree performance compara- ble to retraining in the context of MIA.
Table 12: MIA: The ratio of the presence proba- bility of the unlearned nodes between the original model and target models after unlearning.
Target model
Cora (f)
ogbn-arxiv (f)
Retrain CGU
1.698:10.21
1,232:10.388
1.526:10.100
1.231
ScaleGUN
1.5244:.130
1.232
C.6 APPLY SCALEGUN TO SPECTRAL GNNS.
Besides decoupled GNNs that incorporate MLPs, ScaleGUN can also be applied to spec- tral GNNs (Chien et al. 2020 He et al. 2022), which are significant subset of ex- isting GNN models and have shown superior performance in many popular benchmarks. For example, ChebNetll (He et al. 2022)
Table 13: Test accuracy (%), total unlearning cost (s), and propagation cost (s) per batch edge re- moval using ChebNetHl the backbone on ogbn- arxiv.
can be expressed as V
Io(2),
Exmo (L)X when applied large graphs, where T3 are the Chebyshev polynomials, fo is MLP and wg are learnable parameters. We can maintain Ti (T.) using the lazy local frame- work and perform unlearning fo and w'k, sim- ilar to that of Table 3 Table 13 demonstrated the unlearning results using ChebNeill as the backbone on agbn-arxiv, mirroring the unlearn- ing settings with Table [ This suggests that ScaleGUN can achieve competitive performance when certified guarantees are required.
Retrain
ScaleGUNN
71.99
71.99
72.08
71.98
72.01
71.98
75
71.8
71.96
72.3
71,94
125
71.79
71.93
Prop
14.96
3.13
Total
58.51
5.84
20

---

Published as a conference paper at ICLR 2025
Licenses of the datasets. Ogbn-arxiv and Seon-paperss000 are both under the ODC-BY license. Cora, Citeseer, Photo, and gebnnproddcts are under the CCO 1.0 license. Creative Commons license, Open Data Commons Attribution License, and Amazon license, respectively.
D DETAILS OF LAZY LOCAL PROPAGATION FRAMEWORK
D.1 DIFFERENCES BETWEEN SCALEGUN AND EXISTING DYNAMIC PROPAGATION METHODS
Existing dynamic propagation methods focus on the PPR-based propagation scheme, while ScaleGUN adopts the GPR- based one. Note that these dynamic propagation methods based on PPR cannot be straightforwardly transformed to accommodate GPR. Specifically, PPR-based methods can simply maintain a reserve vector q and a residue vector In contrast, GPR-based propagation requires (()) and y()) for each level f. This difference also impacts the theoretical analysis of correctness and time complexity. Therefore, we have developed tailored algorithms and conducted comprehensive theoretical analysis of the GPR-based scheme.
Choosing GPR enhances the generalizability of our framework. Specifically, our framework computes F-oo wyP'X, wherein PPR, the weights wy are defined as a(1 a:) with
the embedding Z = Σi being the decay factor and L tending towards infinity. Such a formulation allows the theoretical underpinnings of ScaleGUN to be directly applicable to PPR-based models, illustrating the broader applicability of our approach. One could replace the propagation part in ScaleGUN with the existing dynamic PPR approaches and obtain certifiable unlearning method for PPR-based models. Conversely, confining our analysis to PPR would notably limit the expansiveness of our results.
Limitations of InstantGNN to achieve certified unlearning. InstantGNN (Zheng et al., 2022) provides an incremental computation method for the graph embeddings of dynamic graphs, accom- modating insertions/deletions of nodes/edges and modifications of node features. However, simply applying InstantGNN for unlearning does not lead certified unlearning. as this requires thorough analysis of the impact of approximation ing mandates that the gradient residual norm on exact embeddings, i.c., [|VL(W" ,')I,, remains within the privacy limit, detailed in Theorem 2.1 InstantGNN, which relies approximate beddings for training, lacks a theoretical analysis of [|VL(w,, D'II Whether InstantGNN retrains the model for each removal employs adaptive training strategy for better performance, it lacks solid theoretical backing. Thus, InstantGNN is considered a heuristic method without theoretical support.
on the certified unlcarning guarantee. Certified unlearn-
D.2 ALGORIHTMSS OF LAZY LOCAL PROPAGATION FRAMEWORK
Initial propagation. Algorithm illustrates the pseudo-code of Forward Push graph with P = AD- and L propagation steps. Initially, we normalize x to ensure | < 1, and let (0) = (() 0 for < l < L, except for (0) = D when = After employing Algorithm we obtain Et w. D D- (t( as the approximation of z.
Algorithm 2: BasicProp
Input: Graph G, level L, threshold Tmax, and initialized (000), Output: New estimated vectors (f) (f))
for & from 0 to L do
for u E with (w)) > Tmax do
for each v EN(u) do (+)+ (a),
d(n))
(1)+ = 10 and r (f) +
&q (L)) < (L) + (4) and (4) - nxxF
return (0) r(0) 0 S L
21

---

Published as a conference paper at ICLR 2025
Algorithm 3: Uppeaaeemmbadddiigaaixxdeeeeeorr
Input: Graph G, level L, edge (u, to be removed, threshold Ymux. {we) and {g(t) p(()),
0 <. i < L Output: Z E R
G' f delete (u, v) from 9;
(l0) r (00) (u) (d(u)= 1))
(0)) - r (v) + (d(r)² (d(v) + 1)))x((1)
for L from 1 to do
(1) (1)
(())())
d(v)+I
for w E (u) do
L (w) p0 (w) +()(d(()+)i*
(e)
(v) + - (v) (w).
dutt
for E (w) do
p(0
(0) (w)
(w)
d[v]d(v]++1)
u (q(9) ((() + Basic L, maxx, ((()))(())) ,(()));
12 return El= DeD ((())
Efficient Removal. ( the update process for edge removal. Upon removal request, we first adjust {r(()} } locally for the affected nodes to maintain the invariant property. Post-adjustment, the invariant property is preserved across all nodes. Then, Algorithm|] 2 is invoked to reduce the error further and returns the updated 2. Note that the degree of node and node revised in Line [
Batch update. Inspired by (Zheng et al. (022), we introduce a parallel removal algorithm upon receiving a batch of removal requests. Specifically. we initially update the graph structure to reflect all removal requests and then compute the final adjustments for each affected node. Notably, the computation is conducted only once, thus significantly enhancing efficiency. We extend Algorithm 3 to accommodate batch-edge removal, simultaneously enabling parallel processing for multiple edges. The core concept involves adjusting both the reserves and residues for nodes impacted by the removal, deviating from Algorithm 3 where only the residues are modified. The benefit of altering the reserves is that only the reserves and residues for nodes and need updates when removing the edge (u, v). Consequently, this allows the removal operations for all edges to be executed in parallel. Algorithm details the batch update process for edge removal. Batch-node removal and batch-feature removal can be similarly implemented.
D.3 THEORETICAL ANALYSIS OF LAZY LOCAL PROPAGATION FRAMEWORK
Denote (Ar()) as the adjustments residues before invoking Forward Push (Algorithm 2 for (o)
further reducing the error. For instance, we have (r (u)
d(e)+1 for l > 0. Let d be the
average degree of the graph. We introduce the following theorems regarding the time complexity of our lazy local propagation framework.
Theorem D.1 (Initialization Cost, Update Cost, and Total Cost). Let 2o be the initial embedding vector generated from scratch. 2, and {r:²) represents the approximate embedding vector and the residues after the i-th removal, respectively. Each embedding vector 2, satisfies Lemma 3.1 Given the d
threshold max. the cost of generating in from scratch O -t ((
E) |
Tiaax
The cost for updating 2,1 and (r(2,) generate 2, is
o 0 d
L-1 [ (01-)
+ Ar A
T Tiax
1=0
22

---

Published as a conference paper at ICLR 2025
Algorithm 4: BatchuppaateEEdeeeenoooo
Input: Graph G, level I,, edges to unlearned {e,, , weight coefficients wig
threshold mmax. (g(*) r (()), 0 < L
Output: E I
Update according to S, and let A be the number of removed neighbors of node u; Va f {u the degree of node has changed];
parallel for E Va do
(1) + [()+A(() (00 (u))
d(u))
(0) - x(u)xx(u) q (u)
for & from 1 to L do
parallel for Va do
(1) + [ q (1) (w);
d(u)
(1) t (1) + d(u) a (u):
A(w)
for each {removed neighbors of node u) do
(u) t (1(((u) z¹ (m))
d(v)
(g(0) m()) BasicProp(('' I., maxx (we), (0, r(0));
is return El=o D (9)
where ( (0) represent the adjustments of residues for the i-th removal. For a sequence of K removal requests, the total cost of initialization and K removals is
( Tal
K L-1
Ld
+ K.d
Σ
Ar
(f)
r mmax
1 Fmax
E PROOFS OF THEORETICAL RESULTS
Notations for proofs. For the sake of readability, we use (ZZ, w, denote I(e, Zw, e Y). Z; represents the embedding column vector of node i. When referring to the embedding row vector of Z, we use e, Z. Zij denotes the term at the i-th row and the j-th column of Z. |v| represents the vector with the absolute value of each element in vector
E.
PROOF EQUATION AND LEMMA 3.2
Equation ①1) is presented as follows:
W
(
Σ (AD 1 (0(0))
Lemma. For each feature vector x, the reserve vectors (0) and the residue vectors (r(0) satisfy the following invariant property during the propagation process:
9 (0) (1) (w) = D(u))
f= 0
(
10 (u) (0))) = Σ
0 D<E5L
d(t)
(EN())
For simplicity, we reformulate the invariant into the vector form:
( (0) (0) = Dix
t=
(3)
(v)+ ADD (T-
0 0<E5L
23

---

Published as a conference paper at ICLR 2025
We prove that Equation [ and Lemma 3.2 hold during the propagation process by induction. At
the beginning of the propagation,
initialize g (0) 0 for all e, ( D and r(() 0 for all
f > Therefore, Equation (3) and Equation ① hold at the initial state. Consider the situation of
level Since we set (())
(u)
0 and q(d)))))))))) (u) = r (V) once we push the residue (() (u). The sum
of (r(0)) (u) and (1) for any node u remains unchanged during the propagation. Thus, Equation 3
holds for level 0. Consider the situation of level & 0. Assuming that Equation (3) and Equation
holds after a specific push operation. Consider push operation on node u from level k: to level k
< L. Let (kk)) (u), e, is the one-hot vector with only 1 at the node u and elsewhere.
According to Line to 5 in Algorithm the push operation can be described as follows:
*k+1) = (k+11] + AD yee
g(a)) ((k) + yeu
(4)
(() (k)) you
Therefore, we have
q (((+1)) ((++)) -9 1k++)) + +r (k++1) + AD-1 yeu
AD (((()) AD (k) + ye.)
Note that q (>-1) (k+1) AD (R) is satistied before this push operation. Thus, q ((++)) (k++)) AD AD- and thus Equation (3) holds after this push operation. For Equation I the
right side of the equation is updated to:
Σ W. D
d 100
Σ (AD-1)---
Plugging the updated q (k), (k), (*++1) into the equation, we derive that Equation holds after this push operation. This completes the proof of Equation ( and Lemma 3.2
E.2 PROOF OF LEMMA 31
Lemma. Given the threshold Tmax, the L2-error between and is bounded by
2 2112 S Vnl.mmax
(5)
Proof. As stated in Equation
we have
- 2
Wp
Σ t=0
(AD-1)---700
(AD
8=
Since the largest eigenvalue of AD is no greater than 1, we have (AD-1) 2 < 1 for Ł 2 0. D
a diagonal matrix, and d(u) 1 is no greater than for all u. Thus, D } have
1. Therefore,
2| z|| =
W
D
(AD
1)--
ビ=1
t=0
D (AD 10--
W
(AD-1)-- |-:00/
Iwel
0=
The norm of (+) can be derived as Vnrmax since each item of (t) is greater than Tmaxx Given that Ete [wzl < conclude that z S Vn.rmax.
24

---

Published as a conference paper at ICLR 2025
E.3 PROOF OF THEOREM D.1
Proof. First, consider the initialization cost for generating 2,. Recall that we have ( = D before we invoke Algorithm2 2 In Algorithm 2, we push the residue r( (u) node v to its neighbors whenever p(() (u) > Tmax. Each node is pushed at most once at each level. Thus, for level 0, there
00) /mmxx nodes with residues greater than Tmaxx where To is the residues D ro
are at most
of level after the generation. The average cost for one push operation is O(d), the average degree of the graph. Therefore, it costs most T()) D r00l d/rmax time finish the push operations for level 0. In Algorithm 2 a total of (w) will be added to the residues at the next level once we perform push on node u. Therefore, after the push operations for level 0, ||^(()]],
||,
is no
greater than D r0 ||. Thus, the cost of the push operations at level 1 satisfies that
T - [| To (0)
-
d
Tmax
=7(0) - |
Tiaa
Similarly, the cost of the push operations at level é is bounded by T(t) = T(e-1) (6) d Therefore, the total cost of generating (1--Et (1 (e) 11)
Tiax
Timxx
Second, consider the update cost for single removal. For ease of analysis, design the following update procedure: First, we update the residues of the nodes whose degrees have changed at all levels,
corresponding to Algorithm 3 Line
11 We denote the residues as (r(()) after the first step. Then,
push the non-negative residues for all levels. We denote the residues {r-2) J after pushing the non-negative residues. Finally, we push the negative residues at all levels, resulting in the approximate
embedding vector 2; and its residues {r] (f) ). The cost of the first step is (d((u) + d(v)) = O(d).
Denote the cost of the push operations at level as T(1), which contains the cost of pushing non- negative residues _ and the cost of pushing negative residues (()))
Consider the cost of pushing non-negative residues. For level 0, we have d Tmax
(0) = - -
< (1 - -1
Tmax
Note that the residues at level will be modified since the non-negative residues at level 0 are pushed. Specifically, let the modification be f(1), that is, the residues of level 1 of this time is r + f(1) Thus, the cost pushing non-negative residues at level is
(1)
T (1) = r (1-2)) + )())
Tmax
d
+
Tmax
Tmax
Note that ||(00] is exactly the sum of the pushed residues from level O, which is no greater than
(0) Thus, we have
TTe < r
-11-1
d Tmax
+ (
Similarly, we have
T <
(0)
- -11-)
+ T-(e-1
Tmax
Therefore, we derive that
I
1-1
(L- (1:22) - -11-29 II)
T
<
(6)
E=1
E=:
T
Tmax
25

---

Published as a conference paper at ICLR 2025
The cost of pushing negative residues is similar. We have
= r
10)
(1r-1 - -11::01))
Tmax
Tmax
Thus T- be derived
1-1
( -1 -1-0)-1111))))
T- -
T
Timax
Summing up Equation
66) and Equation
7. the i-th update costs can be derived
L-1
- - E) (11-11, - 111111))) Tmax
T s 2d +
(L
1=
Recall that 11 can be derived from r r--1 by the first step. Let ri = (0) + Art (9) We can conclude that
a+ d L-1
T:50
+| | 11
Tmax
Finally, consider the total cost for K removals. The total cost the sum of the initial and update costs for K updates.
T =T mitt
+
T
i=1
1
D
- 6) 11000
L-1
d
Tmax
K
K
1-1
(1. - 2) (11-2 + +|| - -11)))))
+
d
+
Tmax
1=1
f=1
t=
d
<7
D x
Kd
1
mmax
d
Σ (I.
1-1
E)
|r
1-1 Σ
(I. - 2) 11.0011
Tmax
t=
t=
(0)
L
D
d
+ Kd +
Σ
K
L
L-1
Ar!
Tmax
Tmax
1=1
8=0
where we omit the (L
(L-
in (a). This completes the proof.
E.4 PROOF OF THEOREM 3.3
Theorem. For sequence of removal requests that remove all edges of the graph, the amortized cost per edge removal is O (I²d). For a sequence of K random edge removals, the expected cost per edge removal is O (T.2d).
With the help of Theorem D.I we derive the proof of Theorem 3.3 as follows.
Proof. Consider the amortized cost for m removal requests. First, we observe that Σm ||
Ar
1 | where we denote the degree matrix of the initial graph as Do. To explain, ||
((d(u) + 1) - ( + ((d(v) + 1) - d(v)+t +) [x(U) if we remove edge (u, v), where d(u) the new degree of node u. All nodes have edges at the end of the removals. Thus,
26

---

Published as a conference paper at ICLR 2025
the sum of A 1n |, for the m removals is D x And we observe that
| || for
(w))
2/4 d(v)+1 Note
O (||An(0))))
11,) for each removal. First, we have || |||
d()++
that Σ (u) S 1 and [x(u)] S since x is normalized such that
D
S 1. Thus,
Ar
2 d(t)+T
On the other hand, since (d(u) + 1) - d(u)= <
we have
d(u)+I
2 d()(
S
due [x(x]] S for any node u. Therefore, ||r(()) (8)
|1 - 4 Ar 00) |||
2 d((())
2(((e)
for any removal and any & >> 0. Thus, the sum Σezo
|r(*)), O (7. A (0)
||,) Plugging the
result into the total cost in Theorem D.I the total cost for m removals
d + md +
b-1
T= L D
Σ
Tmax
Tmax
1=1
t=0
<7
D
d
+ md +0
Ar
(0)
d
Tmax
Tmax
1=1
d + md + O
<T.
D
1??
D
Tmux
Tmax
We set Tmax = 1/ /rr by the certified unlearning requirement, where n, represents the size of the training set. Thus, Tmax 2 1/n. The amortized cost per edge removal is
T
O
1 - m
L
D
dn
m
Since have m 2 and D
I conclude that the amortized cost is O(L2d).
Consider the expected cost for K random edge removals. Each node has the same probability of being the endpoint of removed edge. When removing e (u, v). the part induced by node u in E1-1 ||) can be expressed as
Su = -(d(u)) + 1) - d(w)+) [x(u)]
(w))
(x))
Σ
1=1 d(u) +1
wEN(u) d(u)(d(u) + +))
The first term (dd(u) 1) (|)=))+1== d(u)+) x(u)) is less than [x(x)] and the second term equals 20 (w) d(w)+
Therefore, the expected value of S, is
(w) d(u) +1
E[S.] = T
Σ S.
-
Σ
x(w)
+ 71
Σ
n1
wEV
WEV
WEV
1=1
The first term is O and Evev (- (u)) in second term is less than 1 for all level both due to
n. The expected value of S,, is ((2). Therefore, for one edge removal, the expected value of E/=1 |r)) is O(2). Note that we set Fmax = O(1/ /n// 2 1/n. Plugging the result into the total cost in Theorem D.1 the expected
the fact that | < 1. Thus, the second term is less than 2L
cost per edge removal is O (L?d).
E.5 PROOF OF THEOREM 4.2
Theorem. Suppose that Assumption 4.1 holds and the feature of node u is to be unlearned. Vj E [F], Ze, Ze, I 61 we have "L((w=D')) is less than
cn
+
(a
X(n, - 1) v vdlu)) vd(u))
F
27

---

Published as a conference paper at ICLR 2025
For the sake of simplicity, the upper bound of IZe Z'e,ll for all j E [F] is denoted eg in the following analysis. At the end of the proof, we will plug the bound in Lemma E.I into the result. We also assume that node is the n,-th node in the training. We state the following lemmas support the proof.
Lemma E.1. Suppose that the feature of node u is to be removed. Then, we have [ee, Z'eyl s
vd(u) for all j E [F].
Lemma E.2. Vj E [FT, suppose that Zee Ze,
S E1. We have [Eee|me (Z. (Zi-Zi) Z,) s
VF(n, -1---
Lemma F.3. Vj E [F], suppose that [Zee - Ze,l S 62 We have |)
(Z) 12 z,) s
VF(m+ 11m--16c 1)22-
Lemma E.4. For the embedding vector z Et we (D (D-+AD- x, where ||||| S and
El wy S 1, we have ||z|| 1.
Proof. We note that V[W[( D'Il can be written as
, - V-WW ,D>/I VL(W DD) + VL(W ,
which is less than VL(W (')) VL(W .D' ||||| + V Dol
due to the Minkowski inequal-
ity.
We start with the term
V VL(w .
Observe that
VL(WT, VL(W :D'l
Σ (VI(Z', w .1) vi(2', w w.))) NE(m--1]
Σ
(''z', ,0)z,, -1 "., ,2)2:)
1]
Σ
(f(Z', . ",), - -1)22-(('') .1)z)) ||
(8)
1E|m,-1]
Σ
(1(Z, ,0%; (2',,, w .0)::)) ().
(9)
1E|m--1]
where the inequality (c) is due to the Minkowski inequality. Consider Term 8 we have
Σ (1'Z', w (1))',",i 12z',, ",,
.1)z:) ,,,)zz)
iE(n--1]
Σ
(i'z',w-, 1 1'((') w
,,, .0) z'
iE(n-11]
2
Σ ve(xe-11
(1(Z', w- (1) V(' w .8)) Z/d
FE
Σ
(' - 1() w- ;))
Σ ztz
(10)
SE[F] [1
xE(m.-1]
28

---

Published as a conference paper at ICLR 2025
where (a) is due to the Cauchy-Schwarz inequality. Recalling that 1' is -i-pschhitzz stated in the
Assumption 4.1 we derive that
Σ
(I' w .1) - -'' .
(c(m=-1]
/ Z'w - - =e,2'w 2'w ||
Σ
ic(m; [1]
T z' 0. 2 / || 1|²
Σ
[1]
||
w
Σ
गे è z' e: =/-1²
iE(ne-1
(2) Fe w w-
(11)
For inequality (a), note that
Σ
e T z' e. eT21
Z'e, - 2'e, 2 S FFe..
5
iE
FE
which follows from the assumption that Z'oz 2'c, S 61 for all j. Since w = w + HW!s A,
we have
w |w' H. P S || || + H |
(12)
Note that V Zw, e Y) S c holds as stated in the Assumption 4.1 Thus,
||w*|| Eve(ma))
Ve(e, 2w
.c. e,TY
(13)
An4
X
Also, following from Lemma E.4. we have Σje(F Eie(n --1 1]
z3 S F. Plugging Inequality
Inequality [2] and Inequality [3 into Inequality (10), we have
Σ
((
w z) ((22 w .12z))
SMFa (i |
kE|m--11
Next, considering Term
we have
Σ - w :1)z)) ..))
1E(n--1]
1(2', w, .8) [z) 2:)
[E[n=11]
(a)
Σ Z -2:) KE(x--1]
Se / F(m+ - 1)E1,
where Inequality (a) is due to the assumption that El s c1 and (b) follows from Lemma E.2 by substituting D with D', Therefore, we have
VV(W ,D') VD(W ,DD
STEiF (f+1A=!A|)) + ci / P(m 1)er.
(14)
29

---

Published as a conference paper at ICLR 2025
Next, our focus shifts to analyzing VC(W D While our approach draws partial inspiration from the proof of Theorem in (Chien al. 2022a), it significantly diverges due the approximation involved in the embedding matrix. This necessitates distinct analytical framework. Let G(w)
V D'). Note that G Rd - Rd is vector-valued function. By Taylor's Theorem, there exists
some 7/ E [o, 1] such that:
G (w = G (w''= + Hw = ((w")(()))))))) + VG (w' + +n HE!A
=G(w") + H w. H H A
G(w") + A Hw, H
A
(4) Hw, H A
(Hw,, Hw ) w A.
(15)
Here, we denote Hw., V& (w' + nH A) with W,, = w + +n/Hw! A. Equality (a) is due to A = VL(W", D) - VL(w", DD) and w' is the unique minimizer of L(,, D). This gives:
| (w (w)) | |= ((ww, H H s | Hw |
(Aw., Hw-)|| i|| Let 2 consist of the first n4 1 rows of ğ', D2 diag(?"(2) wy. 1).... 1"( Wn, n4 - 1)) and D = diag(?" w", ..,... 1' (2' w .n 1)).
First, we consider the term
By the definition, we have
H Hw-
V ((w,, D') - V2 VWW""" Di)
ž - - D'
2 ||IDI DD -D2ll /
Note that
|
|||||z
|||
Ż T ž
and the trace of Ž T Z has the following upper bound:
tr(Z
2)
Σ
Ze,
S
Σ [|Ze,|| + [že, zez|]² {1
JE(F)
JE[F
Thus, we have Ż 2
< F(1 + 22 Since D2 D2 is diagonal matrix, its norm equals the
maximum absolute value of its diagonal elements. Due to the assumption that l' is 7 -L-Lschchi,, we have 1' ("(Z, w, < ?1 for any Z, w, Thus, [[D, D2ll is upper bounded by %1 Therefore, we have
Hw., Aw. S (1(1++1)
(16)
Since C(., ((,,D)) is A(n,- - -ttstrrn convex, we have Hw 2 A(n - 1). hence
|
< X(x 1j
Next, we focus on bounding A V.(w*, D) v((w*, D'). In the feature unlearning scenario, we have
A = Aw" + vi(2 m)) + Σ 12((2."',0 -V(, w', w')))
vE(m:-1]
30

---

Published as a conference paper at ICLR 2025
By assumption that |/ w) < and the fact that /|w*| vi(2, w mm)
$
2. we have
Aw
s 2c. For the last term, we derive that
Σ
E vI(22, w", 1)
KE(M+ [E(m-11 11
sE(me-1]
(1(2, ,", .1)2))
1E(m-111
Σ w0) ,"", 22)..)
w,
(17)
|E(m--1]
+
Σ
(1): -'''', w .)22) ww)
(18)
xE(me-1)
For Term 17 it can be bounded by
Σ
-''2',
w .1)::)
sE
Σ
w 11) 2.
<
-E(m--1]
+
Σ
(C'Z, w 1) - I'','' ww,i)) 2,
iE|me-1]
Σ
(r(Z', w 1) - 11 12''''""n,) .)) 2,
+
iE(m.-1 I]
For the first term, similar to Term
(8) we have
Σ
((2, i) - 1' w wrii)) 2.
iE/m--1]
Σ
(1(2, w - - IZ, wr,
Σ
23
JELFI sE|m:-1]
iE[n--1]
and
Σ
('(2, (12,w", (),,,)-30 1 ll( w ,i))
1E(n.-1]
e Zw' e Zw" * 2
$ Σ
(E/mc-1]
Σ
222
e TT 2 e.z zz) 2
X2
kE/m 1]
2 1
FeE.
2
x2
To derive the Frobenius norm of 2, V
EyE(m Eie(m--1] 2z.0 note that
Σ
/0,
|| S
2
<1Z0e]1
|
|20z zezll) 2 = (1 +.)22
1E|n:-1]
31

---

Published as a conference paper at ICLR 2025
which implies that ESE(F] -ie(ne-1) 2 S v1()+e1). Thus, we have the first term bounded as
(Z w' .i) 2g Σ ((Z kEfn.-1]
S mn FG X
The third term is the same as the first term, except that the embedding matrix is replaced by the updated one. Thus, we have
(I) Σ (1'Z,, w) 1''', w w) 2. S cn Fa + HE [[]
X
The second term can be derived similarly,
Σ
(L'Z, w .8) - -l'(z', w i))
KE (
x Σ
2²22
e _ e z
X2
xE(mg-11
According to Lemma
E.3
we derive that
e2 Fez.
Σ
('(Z.w', 1' l'zz, w ,))² -
12
iE (x 1]
Therefore, the second term can be bounded as
Σ
(' i) - (Z', w 1)) 2,
c Feg(1 +1).
|E(m:-1]
Plugging the above results into Term 17 have
vI(2, w", ()
Σ vE(ne-11
VI(2', w", i)
1E|B 11
F(1 + (2 +22.
For Term (18. we have
Σ ( ((e, e, 2)2,)
kE(m:-1]
(e T w² c, Y). (2()))-))) -2:)
-1|n:-1]
(0)
Σ
(2. - 21)
-1]
<q
Σ
(2: -zi)
iE(R-11 1]
Σ (Z, - Z²)
Σ (z) -2:)
+
+ci
(E(m:-1)
iE(m:-1] 1]
where (a) is due to the assumption that ll < Plugging the results of Lemma B.2 and Lemma E.3
into the above inequality, we have [ (8' (e. 2'w",,, Y)2, l'ee," 2'w' e, Y) S
c / F(n 1) + +22.
32

---

Published as a conference paper at ICLR 2025
Now are ready to bound A for feature unlearning scenarios follows:
| = 2c+ cVi F(1 + (1) + + + c1 F(n, - 1)(2c1 + 62).
Consequently, combining the results in Inequality 14 and Inequality 16 we have
V/[(W ,D)
(
v F(n 1)ei + +1 + +e))FF( H
SheeP
27 Fcj + c1 1.c F(m, 1)q + + X(ne A
(a) cm Fei + +a ta /(m 1)e1 + 2 F M(n 1) A.
Here, we omit the small term (1 11) for simplicity. Then (a) follows from ye F S n.F. Similarly, can derived as
< 2c ( F +avVF(m - 11) (2e1 + t2).
Thus, we have
VL(W D')l
271 FEI + e / F(n+ - 1)61 + 4cn F
A(n= - 1)
27F
ce F + F
F(n- ( (261 (2)
M(m- -1] 1)
x
Fcn (
(a
2 A(n - 1)
(26 (2))
X(m-1 1)
Plugging Lemma E.5 into the above inequality, we have
VL D'Il
F
c71 F + ci (mmm (e1
X(na 1] (2e1 + vd(w)))
2nF
< X(n 1)
+
ta
Note that C1 /F(14 -1) /d(u) is much larger than 2c, and thus 40r is much smaller than X1,,1] 2-1 /d(u), which is include in the second term. Therefore, omit 4em F X(x=11)
C1 /F/F(m 1). ((++1))
For for simplicity. Similarly, omit the 2epsilon term and and adjust by enlarging x(n=-1) to A(n--1j
F
enlarge /d(u) to 2 2 Finally, we have the upper bound of || WWW, ,D)]l
( F F X
(e1+
871 F Am4-1)
/Vdu)
E.6 PROOF OF THEOREM 43
Theorem. Suppose that Assumption 4. holds, and the edge (u,u) is to be unlearned. If E [F].
Žee Ze;
I E1, we can bound v [ ,D')ll by
40y F + + F
47 (c1 +
4
4
(1
+
An4
An;
Vd(u)
vd(u)
In the proof of Theorem 4.3 we also denote the upper bound of IZe Z'e; for all j E [F] as E2 before the conclusion is derived.
Lemma E.5. Suppose that edge (u, v) is to be removed. Then, have Zee Z'e 5 for all j E [F].
4(4)
vd(z)
33

---

Published as a conference paper at ICLR 2025
Proof. We can derive that E(e(m.]
22
- (2-2))
/ Fn and Ene( (Z) Z.)
- VFnie
by substituting n2 by n, in the proofs of Lemma E.2 and Lemma E.3 Thus, by plugging the above results into the proof of Theorem 4.2 we derive that VVL(w D'Ill
is less than
ree [A
+ + Criverrer + 71 + +1)
1 A
In the edge unlearning scenario, we have
A Σ (vI(Z, (ir,,i)--('''vw wi)))
iE|m|]
Similar to the analysis of the third term of A in the proof of Theorem 4.2 we have
|
< oi
X F(1+ e)) E2)
Fm (2E1 + +2).
Plugging Lemma E.5
we derive the upper bound of |VVL(W ,D')l
(
4c%F F
(
(' F -
FM)FMM)) c1
F (2e) +
4
An
An
Vd(u)
Vd(v))
E.7 PROOF OF THEOREM 4.4
Theorem. Suppose that Assumption 4.1 holds and the feature of node u is to be unlearned. If
E (F), [e, Ze,|
I E1, we can bound || VL(Ww DD'] by
Fo X(n-1) (a
27F X(n, 1] (2e1 + dVV + E
+
vdlww)
wEN((u)
Lemma E.6. Suppose that node u is to be removed. Then, for all j E [F', it holds that:
IZee Z'e, S <4)d(u)+
Σ Vd(w)
wEN(a)
Proof. The node unlearning scenario is identical to the node feature unlearning scenario except for Iee Zlc, According the proof of Theorem 4.2
we have
4cn
(7) ( F -)) (a (a F A(m: - 1) (2e) + +&2))
VVCW D')l| - A(1, 1)
+
Plugging Lemma bounded by
E.6 into the above inequality, we derive the conclusion that Zee Z' Z'e, is
F(m (at FnF
F
+ ( F AFFtaVFF F
X(n, - 1) (2e1 + 44/((u)
Σ
4
X(n: (n,-1) 1)
vd(w)
wEN(w)
E.8 PROOF OF LEMMA
E.1
Lemma. Suppose that feature of node u is to be removed. Then, we have [Ze Z'e, S vd(u) for all j E [F).
Proof. Let and z' be the j-th column of Z and Z', respectively. Correspondingly, let (r(O), J.
0 T are the residues of And (r((0) denotes the residues after the update operation for
34

---

Published as a conference paper at ICLR 2025
residues but before invoking Algorithm reduce the error further. Thus, and z' shares the same (q ). First, we consider the difference between z and z'. We have
z z
WE
(AD (AD-1 (100)
Let Ar is the difference between r and r', that is, Ar = p(()) ((), Note that the node feature unlearning scenario does not revise the graph structure. Thus, the residues the neighbors of u and their neighbors are not updated. Since only r()(()) is updated, we have
|| 1
D (AD-!)²
(u) eu.
Since AD-1 is a left stochastic matrix and D
will not increase the result, we derive that
L
5
Ar
(0) (u)
eu.
8=
Due to the fact that Et wy S 1, it can be further bounded by | (u)l- As illustrated in Section (0) is modified to (m)).... Note that Eguation (1) holds for all settings of Tmax. When
Timax 0, (0) is zero vector. Combining Lemma 3.2 have q (w) ((u))x(u). Therefore,
Ar(() d(u)a xx()) d(u)a due to the fact that is normalized such that | S 1.
Consequently, we have ||z - 2'11, I d(u) 2. Thus, the L2-norm, which is always less than L1-norm, bounded by d(u)3, too. This holds for all [F], which completes the proof.
E.9 PROOF OF LEMMA E.5
Lemma. Suppose that edge e = (u, v) is to be removed. Then, we have [Zee Z'e, S Vd(u)
for all j [F].
Proof. Similar to the proof of Lemma E.
we have
Wy
D
q
(AD 1)(-))(1))
t=0
D
(
(A'''-1
where A' and D' are the adjacency matrix and the degree matrix of the graph after the edge removal, respectively. Let Ar the difference between r and r', that is, (r()) (() r()) Then, we have
2
(AD-
D' (A + An(C)))
WF
1=0
1
+
w D
wy D' (())
8=
Note that the above equation holds under all settings of Tmax- Thus, simply set Tmax 0 and then (T(()) are a zero vector for 0 < < L. Therefore, it can be simplified as
z'
W
D
(A'D'-1)e-'An
1
+
wi
1 (
Σ
wy D'
1=0
0=
35

---

Published as a conference paper at ICLR 2025
Consider the L1-norm of --2 z'. Note that the L1-norm of the first term is upper bounded by
S =
we
Σ Σ e D' Ar(t)
F=o
where |Ar(0) represents the vector with the absolute value of each element in Ar(!) Since A A'D'-1 a left stochastic matrix and D'-2 will not increase the result, we derive that
S
Ar(C))
8=0
t=0
Due to the fact that Ei |we] I 1, it can be further bounded by Ei Eigln e | that is, the sum of the absolute value of r(t) for & f & L. According to Algorithm 3 only the residues of node u, node u, and their neighbors will be updated. The sum induced by node be written
Su (Id(u) + 1)
d(())) [x(u)]
g (w)
9 (w)
Σ
d(()(d(u) +1)
wEN(u)
where the first term is the decreasement of (0) (u), the second term is the decreasement of the residues
of v. and the third term is the increase of the residues of the neighbors u. Note that S, S _x(w)]
2 /(((()
d(u)+T Ei=1l (t((t))(x) (u) due to the fact that (dd(u) + 1) d(u)²) Va(u)+ Vdlu++ ddd(
and the new degree of u is d(u)). Note that Σle (u)
S and [x(x) S since x is
normalized such that | S 1. Thus, we have S, S
2v d(u) + *बामhT" S Va(a)"
Similarly, the
sum induced by node can be bounded by 2v/(e)) a())+I
2
Va(e)*
Consider the second term. Only the degree of node u and node v modified. Thus, we have
Σ W (0)
Σ
W (0(0
[e (d(u) - (d(ux) + 1) 1) 19
(d(u)-2-(d(0)
t=
weel (d(u)= (d(v) + (((u)+1)-9 (v)
t=
The term (d(u)- (d(u) + 1)- is less than 1/d(u). Thus, the second term is upper bounded -_ Thus, the L2-norm,
by ब.j + म... Sum up the two terms, we have ||z z' Vd(u) + Vd(c)" which is always less than L1-norm, is bounded by 4 + Vd(oj" too. The lemma follows.
Vd(u)
E. PROOF OF LEMMA E.6
Lemma. Suppose that node is be removed. Then, for all j [F), it holds that:
IZe Z'o,₁1 s <4/((u) + Σ
wEN(a) V Vdww)
Proof. Removing a node is equivalent to removing all edges connected to the node. Thus, [Ze, Z'c, can be bounded by the sum of the bounds of removing all edges from node u. Drawing the result from Lemma E.5 the bound induced by removing one single edge can be bounded
by Vd(u) + Vd(w)) Thus, the total sum is less than 4 4dd() EmeN(u) Va(w) by the triangle inequality. The lemma follows.
36

---

Published as a conference paper at ICLR 2025
E.11 PROOF OF THEOREM 4.5
Theorem. Let ( E R denote the residue matrix at level t, where the j-th column R R
represents the residue at level for the j-th feature vector. Let R be defined as the sum Et R Consequently, we can establish the following data-dependerd bound:
VV , 22c ||1
R|
+
72
[2:)
| || 2
Proof. As demonstrated in the proof of Theorem 4.2 established that
VV(WW D'Il = VL(W D') - VL(w .D') + VL(W D')|
Initially, the data-dependent bound of the second term VL(WW -2' can be inferred directly from
Corollary 1 in Guo al.
2019). by substituting D'' with D' This leads to the conclusion that
VL(WW, 72
H
A
Z'H
Focusing now on the first term.
VL(W ,D) - VL(w .D'1
Σ
('(Z', w :)2; - 12'2', w .1)2:) ,i)))
||-
Since 1' is bounded by cJ, have
Σ
(''Z', w .iZ! 1'(2', w .)2z) ,)))
iE|mv
$201
Σ
Z 2: ||
tERm
-201
Σ
Zi 21
(19)
SE[F]
iE|nd]
Let Z'e, and 2 B'. According Equation II. we have
z'- 2'
Wt
(AD 1)6-1)))))))))
t=
Given that AD-1 forms a left stochastic matrix, the sum of the entries in (() equivalent the sum of entries in (AD-1)) (1)) And D- will not increase the result. Thus, we have
Σ imine]
2 2
(1))
2=
t=0
0
due the fact that ΣL_ completes the proof.
|wrl
< Therefore, Term 19)
be bounded by 2c, ||RR] R||. This
E.12 PROOF OF LEMMA E.2 AND LEMMA E.
We prove these two lemmas directly by the Schwarz inequality. The followings show the proof of Lemma R.2 and the other can be derived similarly.
37

---

Published as a conference paper at ICLR 2025
Proof. Note that
21)
2
Σ iE|n--1]
(2 (21-21)
Σ
Σ
(Z - Zzs)
SE[F]
jEinn-1]
With the Cauchy-Schwarz inequality, we derive that
2
Σ SELFi
Σ
(Ze -Zis)
21n)
S
Σ
(mg
1)
Σ
(2.5 2iz)
(E(
SELF]
iE(n.-11
Given that Ze, Zo,
S 61, we have
22 2:)
Σ
SVF(nn F(ne 1)G1
11
38


Reviews:
[{"review_id": "j0cRQFlTSK", "reviewer": "Reviewer_ABLM", "summary": "This paper studies the certified graph unlearning problem with controlled propagation approximation to accelerate the unlearning speed over large-scale datasets. The main contribution of this paper comes from combining the ideas from forward push and graph unlearning with theoretical guarantees. Specifically, the forward push is designed to control the impact when we try to remove an edge or node feature from the graph dataset. Overall the idea of this paper is intuitive and the presentation is easy to follow. The empirical evaluations also show significant improvement in the unlearning efficiency compared to previous graph unlearning baselines when the model performance is comparable.", "questions": "In Lemma 3.2 Eq (2), the authors claim that \"Consider an edge removal scenario, for example, where edge (u, v) is targeted for removal. Only node u, node v, and their neighbors fail to meet Eq (2) due to the altered degrees of u and v.\" But I think besides the one-hop neighbors, more nodes could be affected thus violating the Eq (2). This is mainly because both $q^{l-1}(t)$ and $d(t)$ can change in this process, not just $d(t)$. For example, suppose there is a line connection between $a-b-c$, and we remove one edge incident to $a$. In this case, $a$ and $b$ would definitely violate Eq (2). But for $c$, since $q^{l-1}(b)$ would change, $q^{l}(c)$ and $r^{l}(c)$ would also need to adjust. I am wondering if the authors can explain the details here in a more rigorous way and maybe discuss how it will affect the following analysis.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1. This paper aims to resolve one of the major bottlenecks of current certified graph unlearning methods, which is the high complexity of repropagating the features over the new graph topology. Approximate updates, adapted from dynamic PPR propagation techniques, are used to accelerate this repropagation process. To align with the certified (graph) unlearning analysis, the authors also provide theoretical analysis to bound the extra approximation error, validating that the privacy requirement is satisfied.\n\n2. The empirical performance on large-scale datasets show promising gains in the unlearning efficiency while the model performance is comparable.", "weaknesses": "1. The linear model assumption is still needed with the new analysis. Also, most of the analysis (i.e., forward push part and graph unlearning part) seems similar to previous methods.\n\n2. One of the key points, why updating the embeddings of a small local neighborhood is enough, is not rigorously explained in the main text. I am not sure the statement \"Consider an edge removal scenario, for example, where edge (u, v) is targeted for removal. Only node u, node v, and their neighbors fail to meet Equation (2) due to the altered degrees of u and v.\" is enough here. Please see the Questions Section for more details.", "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": "", "extra_scores": {}}, {"review_id": "vvuLLMJPgv", "reviewer": "Reviewer_qZtw", "summary": "This paper proposes ScaleGUN, a scalable certified unlearning framework for PPR-based GNNs. In particular, the authors propose a lazy local propagation mechanism to improve the efficiency of the forward pass. In a theoretical perspective, this paper proposes theoretical guarantees on the unlearning efficacy of the proposed lazy local propagation framework. Experimental results show that ScaleGUN largely reduces the latency for unlearning.", "questions": "Please see the Weaknesses", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The proposed ScaleGUN achieves an impressive speedup on some of the largest graph datasets while ensuring a theoretical guarantee.\n- In the theoretical perspective, ScaleGUN extends previous certified unlearning for linear GNNs to PPR-based GNNs which includes a forward approximation error.\n- The paper is overall well-organized. Technical details are introduced. Open-source codes are provided.", "weaknesses": "- The scope of ScaleGUN is still limited to linear GNNs. However, existing studies [1,2,3] have already extended certified graph unlearning to general GNN architectures. This limitation can reduce the significance of the proposed ScaleGUN.\n- For the unlearning technique, ScaleGUN simply follows previous designs (based on influence function). The technical novelty is limited.\n- Several latest certified graph unlearning baselines [1,3] are missing in the experiments.\n- The noise variance is determined by some hyperparameters, e.g., $c_1$ and $\\gamma_2$. How to determine the value of them in the practical scenarios?\n- Some typos need to be fixed, such as the reference to CEU is incorrect.\n\n[1] Wu, Jiancan, et al. \"Gif: A general graph unlearning strategy via influence function.\" Proceedings of the ACM Web Conference 2023. 2023.\n\n[2] Wu, Kun, et al. \"Certified edge unlearning for graph neural networks.\" Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. 2023.\n\n[3] Dong, Yushun, et al. \"Idea: A flexible framework of certified unlearning for graph neural networks.\" Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. 2024.", "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": "", "extra_scores": {}}, {"review_id": "L3MEK74xjP", "reviewer": "Reviewer_skqz", "summary": "The authors study the important problem of certified graph unlearning, where they focus on developing scalable graph unlearning algorithms that can work on extremely large graphs such as ogbn-papers100M. They identify the scalability issue of prior works that require recomputing the graph propagation, and alleviate such issue with an efficient push-forward algorithm that is commonly utilized in efficient PageRank computation. The certified unlearning guarantees are established and extensive experiments are done for large graph datasets, which demonstrates the superiority of the proposed method compared to prior works.", "questions": "1.\tWhat is the definition of $\\hat{D}$ and other quantities with \\hat?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "- Identify the scalability issue of the prior graph unlearning works.\n- Combining error analysis of push-forward operation and certified graph unlearning framework in a clever way.\n- Extensive experiment, especially conducted on graphs with at most 100M nodes.", "weaknesses": "I personally do not find major weaknesses in the paper. Yet some minor points can be addressed to improve the manuscript further.\n\n- The notations can be hard to digest for readers who are not familiar with prior works.\n- The difference in analysis compared to prior works should be further emphasized and elaborated.\n- I feel the main experiments should be based on the setting $\\delta=1/n$ or $\\delta=1/|E|$ instead (currently deferred to Appendix), which provides a more meaningful privacy implication. \n\n## Detail comments\n\nOverall it is a joyful read. The authors study the important certified graph unlearning problem, where they identify the scalability issue in prior works and resolve it by introducing approaches from efficient PageRank computation methods. In theory, while both the error analysis of updating push-forward operation and certified graph unlearning are known, it is still not trivial to combine them correctly. I feel the authors made a great contribution here. On the practice side, the authors test with large graphs such as ogbn-papers100M, which is the largest graph to be tested in the context of certified graph unlearning to the best of my knowledge. The proposed algorithm makes an important step toward the practical certified graph unlearning approach, which I find it as another great contribution of the paper. \n\nThere are still some minor comments that can further improve the clarity and quality of the papers. First, I feel the notations can be further improved. Some notations are not even clearly defined, albeit I roughly understand the meaning since I am familiar with the field. For instance, what exactly is the definition of $\\hat{D}$ and the other quantities with \\hat? I guess it implies the quantities related to approximate propagation regarding equation (2) but it would be great to further elaborate the details. Also, it would be weird to say we have some “approximate dataset $\\hat{D}$”. If I understand correctly, we only have $D,D^\\prime$ in practice, and the “approximate quantity” is only regrading to $Z, Z^\\prime$. I encourage the authors to think more carefully about the choice of the notation here.\n\nAnother comment is that I feel the difference in analysis compared to prior works is not emphasized enough and clearly explained. For instance, I cannot fully understand why the authors can deal with propagation matrix $P = D^{-1/2}A D^{-1/2}$ and the prior works only can do $P=D^{-1}A$. What exactly is the issue and what techniques that the authors use to resolve such issue? Now I only roughly know that it is handled by examining the approximation error of equation (2), but I feel the explanation can be clearer.\n\nFinally, I personally think the authors should focus on the privacy setting of $\\delta = 1/n$ or $1/|E|$ instead of a fix $\\delta = 10^{-4}$, especially the number of edges and nodes are larger than 100M in the largest graph. As also pointed out by the authors, this is the common standard in the privacy graph learning literature. While the claim would not change and is fair (since all tested approaches follow the same privacy constraint), it is still preferable to make the setting as meaningful as possible in terms of privacy.", "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": "", "extra_scores": {}}, {"review_id": "nZVSTsqXfi", "reviewer": "Reviewer_N1R8", "summary": "This paper examines and highlights the efficiency issue of existing certified graph unlearning approaches. The authors show that the culprit is the costly re-computation of graph propagation. To address this challenge, the authors propose ScaleGUN, an efficient certified graph unlearning method that integrates the approximate graph propagation technique to speed up the process. Despite being introduced with additional approximation errors, ScaleGUN's model error is bounded with theoretical guarantees.", "questions": "1. Would the efficiency issue still be a problem when CGU/CEU uses other GNNs as the backbone model (e.g., multi-layer GCN)? Is ScaleGUN compatible with other GNN models? Would the model error of ScaleGUN be still bounded when using other GNNs as the backbone model?\n2. What is the main difference between the approximate propagation module in ScaleGUN and that in InstantGNN?\n3. It would be better if the authors can also plot the bounds of other baseline methods (CGU and CEU) in Figure 2, so as to show that ScaleGUN is on par with them.\n4. To avoid ambiguity and improve readability, the authors are advised to explain or formally define $\\nabla\\mathcal{L}(\\mathbf{w}^\\star,\\mathcal{D})-\\nabla\\mathcal{L}(\\mathbf{w}^\\star,\\mathcal{D^\\prime})$. The reader may incorrectly interpret that $\\mathcal{L}(\\cdot)$ here is the loss function of all training samples, whereas it is actually the loss function of those removed.\n5. There are a few typos or grammatical errors, such as\n    1. Page 1 Line 049 & Page 2 Line 83: the gradient residual norm is missing the vector differential operator $\\nabla$.\n    2. Page 4 Line 188: \"parallel\" should be corrected as \"parallelly\"", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. Certified graph unlearning is an important research topic with potentially broach impact in both academia and industry.\n2. The theoretical analyses and proofs in this paper are mostly rigorous.", "weaknesses": "1. The assumption, analysis, and proposed methodology seem to be limited to SGC-like models (GNNs with pre-computed graph propagation). The efficiency issue may also not be evident when the backbone model is not SGC (e.g., multi-layer GCN).\n2. The main contribution of this paper mainly lies in theory, while the methodology part seems to be just a simple combination of InstantGNN and CGU.\n3. The clarity and presentation of this paper can be further improved. For example, it feels quite strange when the authors suddenly bring up PageRank in Line 100 without any bedding or motivation.", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Spotlight)