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

###### Abstract

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

## 1 Introduction

Graph neural networks (GNNs) are being increasingly used in a variety of real-world applications (Li et al., 2022; Ying et al., 2019; Xu et al., 2022, 2019; Huang et al., 2021; Morselli Gysi et al., 2021; Hu et al., 2020), with the underlying graphs often evolving over time. Machine learning approaches typically involve offline training of a model on a complete training dataset, which is then used for inference without further updates. In contrast, online training methods allow for the model to be updated using new data points as they become available (Orabona, 2019; Nagabandi et al., 2019). However, neither offline nor online learning approaches can address the problem of data deletion (Cao and Yang, 2015; Ginart et al., 2019), which involves removing the influence of a data point from a trained model without sacrificing model performance. When data needs to be deleted from a model, the model must be updated accordingly (Fu et al., 2022). In the face of evolving datasets and growing demands for privacy, GNNs must therefore not only generalize to new tasks and graphs but also be capable of effectively handling information deletion for graph elements from a trained model.

Despite the development of methods for machine unlearning, none of these approaches are applicable to GNNs due to fundamental differences arising from the dependencies between nodes connected by edges (which we show in this paper). Existing machine unlearning methods are unsuitable for data with underlying geometric and relational structure, as graph elements can exert a strong influence on other elements in their immediate vicinity. Furthermore, since the effectiveness of GNN models is based on the exchange of information across local graph neighborhoods, an adversarial agent can easily infer the presence of a data point from its neighbors if the impact of the data point on its local neighborhood is not limited. Given the wide range of GNN applications and the lack of graph unlearning methods, there is a pressing need to develop algorithms that enable GNN models to unlearn previously learned information. This would ensure that inaccurate, outdated, or
privacy-concerned graph elements are no longer used by the model, thereby preventing security concerns and performance degradation. In this paper, we take a step towards building an efficient and general-purpose graph unlearning method for GNNs.

Designing graph unlearning methods is a challenging task. Merely removing data is insufficient to comply with recent demands for increased data privacy because models trained on the original data may still contain information about removed features. A naive approach is to delete the data and retrain a model from scratch, but this can be prohibitively expensive, especially in large datasets. Recently, efforts have been made to achieve efficient unlearning based on exact unlearning (Brophy & Lowd, 2021; Sekhari et al., 2021; Hase et al., 2021; Ullah et al., 2021). The core idea is to retrain several independent models by dividing a dataset into separate shards and then aggregating their predictions during inference. Such methods guarantee the removal of all information associated with the deleted data. However, in the context of GNNs, dividing graphs destroys the structure of the input graph, leading to poor performance on node-, edge- and graph-level tasks. To address this issue, Chen et al. (2022b) uses a graph partitioning method to preserve graph structural information and aggregates predictions across individually retrained shards to produce predictions. However, this approach is still less efficient as the cost increases as the number of shards grows. In addition, choosing the optimal number of shards is still unresolved and may require extra hyperparameter tuning. Several approximation-based approaches (Guo et al., 2020; Ullah et al., 2021; He et al., 2021; Shibata et al., 2021) avoid retraining a model from scratch on data subsets. While these approaches have shown promise, Mitchell et al. (2022) demonstrated that these unlearning methods change the underlying predictive model in a way that can harm model performance.

**Present Work.** We introduce GNNDelete1, a general approach for graph unlearning that can delete nodes, node labels, and relationships from any trained GNN model. We formalize two essential properties that GNN deletion methods should satisfy: 1) _Deleted Edge Consistency:_ predicted probabilities for deleted edges in the unlearned model should be similar to those for nonexistent edges. This property enforces GNNDelete to unlearn information such that deleted edges appear as unconnected nodes. 2) _Neighborhood Influence:_ we establish a connection between graph unlearning and Granger causality (Granger, 1969) to ensure that predictions in the local vicinity of the deletion maintain their original performance and are not affected by the deletion. However, existing graph unlearning methods do not consider this essential property, meaning they do not consider the influence of local connectivity, which can lead to sub-optimal deletion. To achieve both efficiency and scalability, GNNDelete uses a layer-wise deletion operator to revise a trained GNN model. When receiving deletion requests, GNNDelete frezes the model weights and learns additional small weight matrices that are shared across nodes in the graph. Unlike methods that attempt to

Figure 1: **a.** Illustration of Deleted Edge Consistency: It suggests that the predicted probability of deleted edges after unlearning should be random, such that it looks like the deleted data was not used for training before. **b.** Illustration of Neighborhood Influence: It implies that an appropriate unlearning should not change the representations of the local neighborhood (nodes in the subgraph, not nodes themselves ) to maintain the original causality. **c.** Overview of GNNDelete: Given a trained GNN model and edge deletion request, GNNDelete outputs unlearned representations efficiently by only learning a small deletion operator \(W_{D}\). It also ensures representation quality by minimizing a loss function that satisfies the two key properties proposed above.
retrain several small models from scratch or directly update model weights, which can be inefficient and suboptimal, GNNDelete learns small matrices for inference without changing GNN model weights. To optimize GNNDelete, we specify a novel objective function that satisfies Deleted Edge Consistency and Neighborhood Influence and achieves strong deletion performance.

**Our Contributions.** We present our contributions as follows: 1 We formalize the problem of graph unlearning and define two key properties, _Deleted Edge Consistency_ and _Neighborhood Influence_, for effective unlearning on graph data. 2 We propose GNNDelete, a GNN data deletion approach that achieves more efficient unlearning than existing methods without sacrificing predictive performance. GNNDelete is model-agnostic and can be applied to various GNN architectures and training methodologies. 3 The difference between node representations returned the baseline GNN model and those revised by GNNDelete is theoretically bounded, ensuring the strong performance of GNNDelete. 4 We demonstrate the flexibility of GNNDelete through empirical evaluations on both link and node deletion tasks. Results show that GNNDelete achieves effective unlearning with 12.3x less time and 9.3x less computation than retraining from scratch.

## 2 Related Work

**Machine Unlearning.** We organize machine unlearning research into four categories: 1) _Retraining:_ Retraining models from scratch to unlearn is a simple yet often inefficient approach, despite recent efforts to develop efficient data partitioning and retraining methods (Bourtoule et al., 2021; Wu et al., 2020; Liu et al., 2022; Cao and Yang, 2015; Golatkar et al., 2020; Izzo et al., 2021). However, partitioning graphs can be challenging because the graph structure and learned node representations of the partitioned graphs may be significantly different from the original graph. Furthermore, such methods may not scale well to large datasets. _2) Output modification:_ Methods such as UNSIR (Tarun et al., 2021) directly modify model outputs to reduce computational overhead. UNSIR first learns an error matrix that destroys the output and then trains the destroyed model for two epochs with clean data to repair the outputs. However, for graphs, the error destroys outputs for all edges, and the training after that falls back to retraining the whole model. _3) Logit manipulation:_ Other methods achieve unlearning by manipulating the model logits (Izzo et al., 2021; Baumhauer et al., 2022), but these methods only apply to linear or logit-based models. _4) Weight modification:_ Unlearning via weight modification is achieved by running an optimization algorithm. For example, Ullah et al. (2021) proposed an unlearning method based on noisy stochastic gradient descent, while Guo et al. (2020) achieves certified removal based on Newton updates. Other optimization methods that modify weights include Thudi et al. (2022) and Neel et al. (2021). Recent unlearning methods perturb gradients (Ma et al., 2022) or model weights (Chen et al., 2021a). However, weight modification approaches lack unique features for graphs and incur computation overheads, such as calculating the inverse Hessian. In Appendix A, we provide details on unlearning methods for other models.

**Graph Unlearning.** We present an overview of the current state of the art in graph unlearning research. GraphEraser (Chen et al., 2022b) attempts to address the graph unlearning problem by utilizing graph partitioning and efficient retraining. They use a clustering algorithm to divide a graph into shards based on both node features and structural information. A learnable aggregator is optimized to combine the predictions from sharded models. However, the limitations of GraphEraser (Chen et al., 2022b) are that it supports only node deletion. GraphEditor (Cong and Mahdavi, 2023) provides a closed-form solution for linear GNNs to guarantee information deletion, including node deletion, edge deletion, and node feature update. Additional fine-tuning can improve predictive performance. However, GraphEditor is only applicable to linear structures, which is the case for most unlearning algorithms, not only those designed for graph-structured data. As a result, it is not possible to use existing non-linear GNNs or knowledge graphs with GraphEditor, and it struggles to process larger deletion requests. Recently, Chien et al. (2022) proposed the first framework for certified graph unlearning of GNNs. Their approach provides theoretical guarantees for approximate graph unlearning. However, the framework is currently limited to certain GNN architectures and requires further development to become a more practical solution for the broader range of GNNs. For more details on related work, we refer the reader to Appendix A.

**Connection with Adversarial Attacks and Defense for GNNs.** To determine whether a data point has been used to train a model, the success of a membership inference (MI) attack can be a suitable measure for the quality of unlearning (Yeom et al., 2019; Sablayrolles et al., 2019). Defending
against MI attacks is also a challenge that we care about when building unlearning models. Thudi et al. (2022c) proposed using a novel privacy amplification scheme based on a new tighter bound and subsampling strategy. Olatunji et al. (2021) showed that all GNN models are vulnerable to MI attacks and proposed two defense mechanisms based on output perturbation and query neighborhood perturbation. Liu et al. (2022a) treated the data to be unlearned as backdoored data. While defense strategies against MI attacks can provide valuable insights for evaluating unlearning, it is important to note that they serve a different purpose than unlearning itself.

## 3 Preliminaries

Let \(G=(\mathcal{V},\mathcal{E},\mathbf{X})\) be an attributed graph with \(n=|\mathcal{V}|\) nodes, set of edges \(\mathcal{E}\), and \(n_{f}\)-dimensional node features \(\mathbf{X}=\{\mathbf{x}_{0},\dots,\mathbf{x}_{n-1}\}\) where \(\mathbf{x}_{i}\in\mathbb{R}^{n_{f}}\). We use \(\mathbf{A}\) to denote the adjacency matrix of \(G\) and \(\text{deg}_{G}:\mathcal{V}\rightarrow\mathbb{N}\) to denote the degree distribution of graph \(G\). Further, we use \(\mathcal{S}_{uv}^{k}=(\mathcal{V}_{uv}^{k},\mathcal{E}_{uv}^{k},\mathbf{X}_{uv}^{k})\) to represent a \(k\)-hop enclosing subgraph around nodes \(u\) and \(v\).

**Graph Neural Networks (GNNs).** A GNN layer \(g\) can be expressed as a series of transformation functions: \(g(G)=(\text{Upd}\circ\text{Agg}\circ\text{Msg})(G)\) that takes \(G\) as input and produces \(n\)\(d\)-dimensional node representations \(\mathbf{h}_{u}\) for \(u\in\mathcal{V}\) (Figure 1). Within layer \(l\), \(\text{Msg}\) specifies neural messages that are exchanged between nodes \(u\) and \(v\) following edges in \(\mathbf{A}_{uv}\) by calculating \(\mathbf{p}_{uv}^{l}=\text{Msg}(\mathbf{h}_{u}^{l-1},\mathbf{h}_{v}^{l-1},\mathbf{A}_{uv})\). The \(\text{Agg}\) defines how every node \(u\) combines neural messages from its neighbors \(\mathcal{N}_{u}\) and computes the aggregated message \(\mathbf{P}_{u}^{l}=\text{Agg}((\mathbf{p}_{uv}^{l}|v\in\mathcal{N}_{u}))\). Finally, \(\text{Upd}\) defines how the aggregated messages \(\mathbf{P}_{u}^{l}\) and hidden node states from the previous layer are combined to produce \(\mathbf{h}_{u}^{l}\), i.e., final outputs of \(l\)-th layer \(\mathbf{h}_{u}^{l}=\text{Upd}(\mathbf{P}_{u}^{l},\mathbf{h}_{u}^{l-1})\). The output of the last GNN layer is the final node representation, \(\mathbf{z}_{u}=\mathbf{h}_{u}^{L}\), where \(L\) is the number of GNN layers in the model.

**Unlearning for GNNs.** Let \(\mathcal{E}_{d}\subseteq\mathcal{E}\) denote the set of edges to be deleted and \(\mathcal{E}_{r}=\mathcal{E}\backslash\mathcal{E}_{d}\) be the remaining edges after the deletion of \(\mathcal{E}_{d}\) from \(G\). We use \(G_{r}=(\mathcal{V}_{r},\mathcal{E}_{r},\mathbf{X}_{r})\) to represent the resulting graph after deleting edge \(\mathcal{E}_{d}\). Here, \(\mathcal{V}_{r}=\{u\in V|\deg_{G_{r}}(u)>0\}\) denotes the set of nodes that are still connected to nodes in \(G_{r}\), and \(\mathbf{X}_{r}\) denotes the corresponding node attributes. Although the above notations are specific to edge deletion, GNNDelete can also be applied to node deletion by removing all edges incident to the node that needs to be deleted from the model.

To unlearn an edge \(e_{uv}\), the model must erase all the information and influence associated with \(e_{uv}\) as if it was never seen during the training while minimizing the change in downstream performance. To this end, we need to modify both the predicted probability of \(e_{uv}\) and remove its information from its local neighborhood. Therefore, post-processing and logit manipulation are ineffective for deleting edges from a GNN model because these strategies do not affect the rest of the graph. We denote a classification layer \(f\) that takes node representations \(\mathbf{h}_{u}^{L}\) and \(\mathbf{h}_{v}^{L}\) as input and outputs the prediction probability for edge \(e_{uv}\). Given \(L\) layers and \(f\), a GNN model \(m:G\rightarrow\mathbb{R}^{|\mathcal{E}|}\) can be expressed as \(m(G)=(f\circ g^{L}\cdots\circ g^{1})(G)\), where \(g^{i}\) is the \(i^{th}\) GNN layer. The unlearned model \(m^{\prime}:G\rightarrow\mathbb{R}^{|\mathcal{E}_{r}|}\) can be written as \(m^{\prime}(G_{r})=(f\circ g^{\prime L}\cdots\circ g^{\prime 1})(G_{r})\), which are \(L\) stacked unlearned GNN layers \(g^{\prime i}\) operating on the graph \(G_{r}\).

## 4 GNNDelete: A General Strategy for Graph Unlearning

To ensure effective edge deletion from graphs, the GNN model should ignore edges in \(\mathcal{E}_{d}\) and not be able to recognize whether a deleted edge \(e_{uv}\in\mathcal{E}_{d}\) is part of the graph. Furthermore, the model should ignore any influence that a deleted edge has in its neighborhood. To this end, we introduce two properties for effective graph unlearning and a layer-wise deletion operator that implements the properties and can be used with any GNN to process deletions in \(\mathcal{E}_{d}\).

**Problem Formulation (Graph Unlearning).**_Given a graph \(G=(\mathcal{V},\mathcal{E},\mathbf{X})\) and a fully trained GNN model \(m(G)\), we aim to unlearn every edge \(e_{uv}\in\mathcal{\bar{E}}_{d}\) from \(m(G)\), where \(\mathcal{\bar{E}}_{d}\) is a set of edges to be deleted. The goal is to obtain an unlearned model \(m^{\prime}(G)\) that is close to the model output that would have been obtained had the edges in \(\mathcal{E}_{d}\) been omitted from training. To achieve this, we require that the following properties hold:_
* [leftmargin=*]
* _Deleted Edge Consistency: If_ \(e_{uv}\in\mathcal{E}_{d}\)_, then_ \(m^{\prime}(G)\) _should output a prediction that is independent of the existence of the edge_ \(e_{uv}\)_, i.e., the deletion of_ \(e_{uv}\) _should not have any influence on the predicted output._
* _Neighborhood Influence: If_ \(e_{uv}\notin\mathcal{E}_{d}\)_, then_ \(m^{\prime}(G)\) _should output a prediction that is close to_ \(m(G)\)_, i.e., the deletion of edges in_ \(\mathcal{E}_{d}\) _should not have any significant impact on predictions in the rest of the graph._

### Required Properties for Successful Deletion on Graphs

Deleting information from a graph is not a trivial task because the representations of nodes and edges are dependent on the combined neighborhood representations. The following two properties show intuitive assumptions over the deletion operator for effective unlearning in GNNs:

**1) Deleted Edge Consistency.** The predicted probability from the unlearned model \(m^{\prime}\) for an edge \(e_{uv}\) should be such that it is hard to determine whether it is a true edge or not. The unlearned GNN layer \(g^{tl}\) should not be aware of the edge existence. Formally, we define the following property:

**Definition 1** (Deleted Edge Consistency).: _Let \(e_{uv}\) denote an edge to be deleted, \(g^{l}\) be the 1-th layer in a GNN with output node representation vectors \(\mathbf{h}^{l}_{u}\), and the unlearned GNN layer \(g^{tl}\) with \(\mathbf{h}^{tl}_{u}\). The unlearned layer \(g^{tl}\) satisfies the Deleted Edge Consistency property if it minimizes the difference between node-pair representations \(\phi(\mathbf{h}^{l}_{u},\mathbf{h}^{l}_{v})\), and \(\phi(\mathbf{h}_{p},\mathbf{h}_{q})\) of two randomly chosen nodes \(p,q\in\mathcal{V}\):_

\[\underset{p,q\in_{R}}{\mathbb{E}}[\phi(\mathbf{h}^{tl}_{u},\mathbf{h}^{tl}_{v})-\phi (\mathbf{h}_{p},\mathbf{h}_{q})]=\delta, \tag{1}\]

where \(\phi\) is a readout function (e.g., dot product, concatenation) that combines node representations \(\mathbf{h}^{tl}_{u}\) and \(\mathbf{h}^{tl}_{v}\), \(\in_{R}\) denotes a random choice from \(\mathcal{V}\), and \(\delta\) is an infinitesimal constant.

**2) Neighborhood Influence.** While the notion of causality has been used in explainable machine learning, to the best of our knowledge, we propose the first effort of modifying a knowledge graph using a causal perspective. Formally, removing edge \(e_{uv}\) from the graph requires unlearning the influence of \(e_{uv}\) from the subgraphs of both nodes \(u\) and \(v\). In this work, we propose the _Neighborhood Influence_ property which leverages the notion of Granger causality (Granger, 1969; Bressler & Seth, 2011) and declares a causal relationship \(\psi(\{\mathbf{h}_{u}|u\in\mathcal{S}_{uv}\})\to e_{uv}\) between variables \(\psi(\{\mathbf{h}_{u}|u\in\mathcal{S}_{uv}\})\) and \(e_{uv}\) if we are better able to predict edge \(e_{uv}\) using all available node representations in \(\mathcal{S}_{uv}\) than if the information apart from \(\psi(\{\mathbf{h}_{u}|u\in\mathcal{S}_{uv}\})\) had been used. Here, \(\psi(\cdot)\) is an operator that combines the node representations in subgraph \(\mathcal{S}_{uv}\). In the context of graph unlearning, if the absence of node representations decreases the prediction confidence of \(e_{uv}\), then there is a causal relationship between the node representation and the \(e_{uv}\) prediction.

Here, we characterize the notion of deletion by extending Granger causality to local subgraph causality, i.e., an edge \(e_{uv}\) dependent on the subgraphs associated with both nodes \(u\) and \(v\). In particular, removing \(e_{uv}\) should not affect the predictions of \(\mathcal{S}_{uv}\) yielding the following property:

**Definition 2** (Neighborhood Influence).: _Let \(e_{uv}\in\mathcal{E}_{d}\) denote an edge in \(G\) to be deleted, \(g^{l}\) be the 1-th layer in a GNN with output node representation vectors \(\mathbf{h}^{l}_{u}\), and the unlearned GNN layer \(g^{tl}\) with \(\mathbf{h}^{tl}_{u}\). The unlearned layer \(g^{tl}\) satisfies the Neighborhood Influence property if it minimizes the difference of all node-subset representations \(\psi(\{\mathbf{h}^{l}_{w}|w\in\mathcal{S}_{uv}\})\) comprising \(e_{uv}\) with their corresponding node-subset representations \(\psi(\{\mathbf{h}^{l}_{w}|w\in\mathcal{S}_{uv/e_{uv}}\})\) where \(e_{uv}\) is deleted, i.e.,_

\[\psi(\{\mathbf{h}^{l}_{w}|w\in\mathcal{S}_{uv}\})-\psi(\{\mathbf{h}^{tl}_{w}|w\in \mathcal{S}_{uv/e_{uv}}\})]=\delta, \tag{2}\]

where \(\psi\) is an operator that combines the elements of \(S_{uv}\) (e.g., concatenation, summation), \(\mathcal{S}_{uv/e_{uv}}\) represent the subgraph excluding the information from \(e_{ij}\), and \(\delta\) is an infinitesimal constant.

### Layer-Wise Deletion Operator

To achieve effective deletion of an edge \(e_{uv}\) from a graph \(G\), it is important to eliminate signals with minor contributions to predicting the edges and develop mechanisms that can tune or perturb any source of node or edge information that aids in the prediction of \(e_{uv}\). Perturbing weights or other hyperparameters of the GNN model can affect decisions for multiple nodes and edges in \(G\) due to information propagation through the local neighborhood of each node. In order to allow for the
deletion of specific nodes and edges, we introduce a model-agnostic deletion operator Del that can be applied to any GNN layer.

**Deletion Operator.** Following the notations of Section 3, for the \(l\)-th GNN layer \(g^{l}(G)\) with output dimension \(d^{l}\), we define an extended GNN layer with unlearning capability as \((\textsc{Del}^{l}\circ g^{l})(G)\) with the same output dimension \(d^{l}\). Given an edge \(e_{uv}\) that is to be removed, Del is applied to the node representations and is defined as:

\[\textsc{Del}^{l}=\begin{cases}\phi&\text{if }w\in S^{l}_{uv}\\ \mathbbm{1}&\text{otherwise}\end{cases}, \tag{3}\]

where \(\mathbbm{1}\) is the identity function, and \(\phi:\mathbb{R}^{n\times d^{l}}\rightarrow\mathbb{R}^{n\times d^{l}}\) can be any differentiable function that takes as input the output node representations of \(g\). In this work, \(\phi\) is considered as an MLP with weight parameters \(\mathbf{W}^{l}_{D}\). Similarly to other GNN operators, the weights \(\mathbf{W}^{l}_{D}\) of our Del operator are shared across all nodes to achieve efficiency and scalability.

**Local Update.** Defining an operator that acts only in the local neighborhood \(\mathcal{S}_{uv}\) enables targeted unlearning, keeping the previously learned knowledge intact as much as possible. If node \(u\) is within the local neighborhood of \(e_{uv}\), Del is activated. For other nodes, Del remains deactivated and does not affect the hidden states of the nodes. This ensures that the model will not forget the knowledge it has gained before during training and the predictive performance on \(\mathcal{E}\backslash S_{uv}\) will not drop.

By applying the deletion operator Del to every GNN layer, we expect the final representations to reflect the unlearned information in the downstream task. Next, we show a theoretical observation over the unlearned node representations that indicates a stable behavior of the deletion operator:

**Theorem 1**.: _(Bounding edge prediction using initial model \(m\) and unlearned model \(m^{\prime}\)) Let \(e_{uv}\) be an edge to be removed, \(\mathbf{W}^{L}_{D}\) be the weight matrix of the deletion operator \(\textsc{Del}^{L}\), and normalized Lipschitz activation function \(\sigma(\cdot)\). Then, the norm difference between the dot product of the final node representations from the initial model \(\mathbf{z}_{u},\mathbf{z}_{v}\) and from the unlearned one \(\mathbf{z}^{\prime}_{u},\mathbf{z}^{\prime}_{v}\) is bounded by:_

\[\langle\mathbf{z}_{u},\mathbf{z}_{v}\rangle-\langle\mathbf{z}^{\prime}_{u},\mathbf{z}^{\prime }_{v}\rangle\geq-\frac{1+\|\mathbf{W}^{L}_{D}\|^{2}}{2}\|\mathbf{z}_{u}-\mathbf{z}_{v}\|^ {2}, \tag{4}\]

_where \(\mathbf{W}^{L}_{D}\) denotes the weight matrix of the deletion operator for the \(l\)-th GNN layer._

The proof is in Appendix B. By Theorem 1, \(\langle\mathbf{z}^{\prime}_{u},\mathbf{z}^{\prime}_{v}\rangle\), and consequently the prediction probability for edge \(e_{uv}\) from the unlearned model cannot be dissimilar from the baseline. Nevertheless, Del is a layer-wise operator, which provides stable node embeddings as compared to the initial ones.

### Model Unlearning

Moving from a layer-wise operator to the whole GNN model, our method GNNDelete applies Del to every GNN layer, leading to a total number of trainable parameters \(\sum_{l}(d^{l})^{2}\). As the number of trainable parameters in GNNDelete is independent of the size of the graph, it is compact and scalable to larger graphs and the number of deletion requests. Considering the properties defined in Section 4.1, we design two loss functions and compute them in a layer-wise manner. Specifically, for the \(l\)-th GNN layer we first compute the _Deleted Edge Consistency_ loss:

\[\mathcal{L}^{l}_{\text{DEC}}=\mathcal{L}(\{[\mathbf{h}^{l}_{u};\mathbf{h}^{l}_{v}]|e_{ uv}\in\mathcal{E}_{d}\},\{[\mathbf{h}^{l}_{u};\mathbf{h}^{l}_{v}]|u,v\in_{R}\mathcal{V}\}), \tag{5}\]

and the _Neighborhood Influence_ loss:

\[\mathcal{L}^{l}_{\text{NI}}=\mathcal{L}(\|_{w}\ \{\mathbf{h}^{l}_{w}|w\in\mathcal{S}^{l }_{uv}/e_{uv}\},\|_{w}\ \{\mathbf{h}^{l}_{w}|w\in\mathcal{S}^{l}_{uv}\}), \tag{6}\]

where \([\mathbf{h}^{l}_{u};\ \mathbf{h}^{l}_{v}]\) denotes the concatenation of two vectors, and \(\|\) denotes the concatenation of multiple vectors. Note that according to Equations 1 and 2, we choose the functions \(\phi,\psi\) to be the concatenation operators. During the backward pass, the deletion operator at the \(l\)-th GNN layer is only optimized based on the weighted total loss at the \(l\)-th layer, i.e.

\[\mathbf{W}^{l^{*}}_{D}=\arg\min_{\mathbf{W}^{L}_{D}}\mathcal{L}^{l}=\arg\min_{\mathbf{W}^{ L}_{D}}\lambda\mathcal{L}^{l}_{\text{DEC}}+(1-\lambda)\mathcal{L}^{l}_{\text{NI}}, \tag{7}\]

where \(\lambda\in[0,1]\) is a regularization coefficient that balances the trade-off between the two properties, \(\mathcal{L}\) refers to the distance function. We use Mean Squared Error (MSE) throughout the experiments.
**Broad Applicability of GNNDelete.** GNNDelete treats node representations in a model-agnostic manner, allowing us to consider graph unlearning in models beyond GNNs. Graph transformers (Ying et al., 2021; Rampasek et al., 2022) have been proposed recently as an extension of the Transformer architecture (Vaswani et al., 2017) for learning representations on graphs. The Del operator can also be applied after the computation of the node representations in such models. For example, the MPNN\({}_{e}^{l}(\mathbf{X}^{l},\mathbf{E}^{l},\mathbf{A})\) layer in GraphGPS (Rampasek et al., 2022, Equation 2) can be replaced with the unlearned version \((\textsc{Del}\circ\textsc{MPNN}_{e}^{l})\). Similarly, in the Graphormer layer, Del operator can be applied after the multi-head attention MHA layer (Rampasek et al., 2022, Equation 8).

## 5 Experiments

We proceed with the empirical evaluation of GNNDelete. We examine the following questions: **Q1**) How does GNNDelete perform compared to existing state-of-the-art unlearning methods? **Q2**) Can GNNDelete support various unlearning tasks including node, node label, and edge deletion? **Q3**) How does the interplay between Deleted Edge Consistency and Neighborhood Influence property affect deletion performance? Appendix C.1 provides a detailed definition of performance metrics.

### Experimental setup

**Datasets.** We evaluate GNNDelete on several widely-used graphs at various scales. We use 5 homogeneous graphs: Cora (Bojchevski & Gunnemann, 2018), PubMed (Bojchevski & Gunnemann, 2018), DBLP (Bojchevski & Gunnemann, 2018), CS (Bojchevski & Gunnemann, 2018), OGB-Collab (Hu et al., 2020), and 2 heterogeneous graphs: OGB-BioKG (Hu et al., 2020), and WordNet18RR (Dettmers et al., 2018). Table 4 includes details on graph datasets.

**GNNs and Baselines.** We test with four GNN architectures and two graph types to show the flexibility of our GNNDelete operator. In particular, we test on GCN (Kipf & Welling, 2017), GAT (Velickovic et al., 2018), and GIN (Xu et al., 2019) for homogeneous graphs, and R-GCN (Schlichtkrull et al., 2018) and R-GAT (Chen et al., 2021b) for heterogeneous graphs. We consider four baseline methods: i) GraphFlotor (Cong & Mahdavi, 2023), a method that finetunes on a closed-form solution of linear GNN models; ii) CerUnlear(Chien et al., 2022), a certified unlearning approach based on linear GNNs; iii) GraphEraser (Chen et al., 2022b), a re-training-based machine unlearning method for graphs; iv) GradAscent, which performs gradient ascent on \(\mathcal{E}_{d}\) with cross-entropy loss, and v) Descent-to-Delete (Neel et al., 2021), a general machine unlearning method.

**Unlearning Tasks and Downstream Tasks.** Requests for graph unlearning can be broadly classified into three categories: 1) edge deletion, which involves removing a set of edges \(\mathcal{E}_{d}\) from the training graph, 2) node deletion, which involves removing a set of nodes \(\mathcal{N}_{d}\) from the training graph, and 3) node feature unlearning, which involves removing the node feature \(X_{d}\) from the nodes \(\mathcal{N}_{d}\). Deletion of information can have a significant impact on several downstream tasks. Therefore, we evaluate the effects of graph unlearning on three different downstream tasks, namely, link prediction, node classification, and graph classification.

**Setup.** We evaluate the effectiveness of GNNDelete on edge deletion tasks and also demonstrate its ability to handle node deletion and node feature unlearning tasks. We perform experiments on two settings: i) an easier setting where we delete information far away from test set \(\mathcal{E}_{t}\) in the graph, and ii) a harder setting where we delete information proximal to test set \(\mathcal{E}_{t}\) in the graph. To perform edge deletion tasks, we delete a varying proportion of edges in \(\mathcal{E}_{d}\) between [0.5%-5.0%] of the total edges, with a step size of 0.5%. For larger datasets such as OGB (Hu et al., 2020), we limit the maximum deletion ratio to 2.5%. We report the average and standard error of the unlearning performance across five independent runs. We use AUROC to evaluate the performance of GNNDelete for link prediction tasks, as well as Membership Inference (MI) (Thudi et al., 2022a) for node deletion. Performance metrics are described in Appendix C.1. Additionally, we consider two sampling strategies for \(\mathcal{E}_{d}\) (Appendix C.2).
### **Q1**: Results - Comparison to Existing Unlearning Strategies

We compare GNNDelete to the baseline unlearning techniques and present the results in Tables 1. Across four GNN architectures, we find that GNNDelete achieves the best performance on the test edge set \(\mathcal{E}_{t}\), outperforming GraphEditor, CertUnLearn and GraphEraser by 13.9%, 19.7% and 38.8%. Further, we observe that GNNDelete achieves the highest AUROC on \(\mathcal{E}_{d}\), outperforming GraphEditor, CertUnLearn and GraphEraser by 32.2%, 27.9% and 25.4%. GNNDelete even outperforms Retrain-from-Scratch by 21.7% under this setting, proving its capability of effectively unlearning the deleted edges. Interestingly, none of the existing baseline methods have comparable performance to GNNDelete on these performance metrics, including GraphEraser, which ignores the global connectivity pattern and overfit to specific shards, as well as GraphEditor and CertUnLearn, whose choice of linear architecture strongly limits the power of the GNN unlearning. Our results demonstrate that baselines like Descent-to-Delete and GradAscent lose almost their predictive prowess in making meaningful predictions and distinguishing deleted edges because the weight updates are independent of the unlearning task and affect all the nodes, including nodes associated with \(\mathcal{E}_{t}\). In addition, CertUnLearn and GraphEditor are not applicable due to their linear architectures. Please refer to the Appendix for results on Cora (Tables 13-14), PubMed (Tables 15-16), DBLP (Tables 17-18), OGB-Collab (Tables 19-20), and WordNet18 (Tables 21-22) using a deletion ratio of 0.5%, 2.5%, and 5%.

Results in Table 2 show the Membership Inference (MI) performance of baselines and GNNDelete for the DBLP and Wordnet18 using a deletion ratio of \(2.5\%\). It shows that GNNDelete outperforms baselines for most GNN models, highlighting its effectiveness in hiding deleted data. Across five GNN architectures, we find that GNNDelete improves on the MI ratio score of all baselines: GraphEditor (+0.083), CertUnLearn (+0.169) GraphEraser (+0.154), Retrain-from-Scratch (+0.047), GradAscent (+0.134), and Descent-to-Delete (+0.086).
unlearning method on node classification and Membership Inference attacks. Results in Table 8 show that GNNDelete outperforms baselines on node classification while deleting nodes. GNNDelete outperforms GraphEditor and CertUnLearn by 4.7% and 4.0% in accuracy, respectively. It is also 0.139 and 0.267 better than GraphEditor and CertUnLearn in terms of membership inference attacks. Tables 9 and 10 show results for node feature unlearning and sequential unlearning.

**Time and Space Efficiency.** We demonstrate that GNNDelete is time-efficient as compared to most unlearning baselines. For all methods, we use a 2-layer GCN/R-GCN architecture with a trainable entity and relation embeddings with 128, 64, and 32 hidden dimensions trained on three datasets (PubMed, CS, and OGB-Collab). We present the results of wall-clock time vs. graph size in Figure 2 and observe that GNNDelete consistently takes less time than existing graph unlearning methods. In particular, GNNDelete is \(\mathbf{12.3\times}\) faster than Retrain-from-Scratch on WordNet. For smaller graphs like DBLP, GNNDelete takes 185 seconds less (18.5% faster) than the pre-training stage of GraphEditor. Despite taking lower time, the predictive performances of Descent-to-Delete and GradAscent are poor compared to GNNDelete because they are not tailored to incorporate the graph structure for unlearning. Regarding the space efficiency, we measure the number of training parameters and show that GNNDelete has the smallest model size. In addition, the number of training parameters does not scale with respect to the graph size, proving the efficiency and scalability of GNNDelete. For instance, GNNDelete takes \(\mathbf{9.3\times}\) less computation than GraphEraser. We further demonstrate that GNNDelete can be more efficient by only inserting a deletion operator after the last layer without losing much performance. Additional results and details are in Tables 5-6.

### Q3: Results - Deleted Edge Consistency vs. Neighborhood Influence

We conducted ablations on two key properties of GNNDelete, namely Deleted Edge Consistency and Neighborhood Influence, by varying the regularization parameter \(\lambda\) in Equation 7. The results presented in Table 3 demonstrate that both properties are necessary for achieving high AUROC on both \(\mathcal{E}_{t}\) and \(\mathcal{E}_{d}\). We observed that as \(\lambda\) decreases, GNNDelete focuses more on Neighborhood Influence, which explains why the model's performance on \(\mathcal{E}_{t}\) is close to the original, while it cannot distinguish \(\mathcal{E}_{d}\) from the remaining edges. Conversely, for higher values of \(\lambda\), GNNDelete focuses more on optimizing the Deleted Edge Consistency property and can better distinguish between \(\mathcal{E}_{d}\) and \(\mathcal{E}_{r}\). In summary, we observed a 5.56% improvement in the average AUROC for \(\lambda=0.5\).

## 6 Conclusion

We introduce GNNDelete, a novel deletion operator that is both flexible and easy-to-use, and can be applied to any type of graph neural network (GNN) model. We also introduce two properties, denoted as Deleted Edge Consistency and Neighborhood Influence, which can contribute to more

\begin{table}
\begin{tabular}{c|c c c} \hline \(\lambda\) & AUROC on \(\mathcal{E}_{t}\) & AUROC on \(\mathcal{E}_{d}\) & Avg. AUROC (Gap) \\ \hline
0.0 & 0.964 \(\pm\)0.003 & 0.492 \(\pm\)0.012 & 0.728 (0.473) \\
0.2 & 0.961 \(\pm\)0.003 & 0.593 \(\pm\)0.011 & 0.777 (0.368) \\
0.4 & 0.950 \(\pm\)0.005 & 0.691 \(\pm\)0.0010 & 0.821 (0.259) \\
0.5 & 0.934 \(\pm\)0.002 & 0.748 \(\pm\)0.005 & **0.841** (**0.185**) \\
0.6 & 0.927 \(\pm\)0.001 & 0.739 \(\pm\)0.006 & 0.834 (0.185) \\
0.8 & 0.893 \(\pm\)0.003 & 0.759 \(\pm\)0.008 & 0.823 (0.134) \\
1.0 & 0.858 \(\pm\)0.004 & 0.757 \(\pm\)0.004 & 0.808 (0.101) \\ \hline \end{tabular}
\end{table}
Table 3: Ablation study on the interplay of Deleted Edge Consistency and Neighborhood Influence property. **Unlearning task: 2.5% edge deletion. Evaluation: link prediction. Dataset: DBLP.** The gap is calculated as: \(|\text{AUROC}(\mathcal{E}_{t})-\text{AUROC}(\mathcal{E}_{d})|\). Best overall deletion performance is achieved for \(\lambda=0.5\), indicating that both properties are necessary to successfully delete information from the GNN model while minimizing negative effects on overall model performance.

Figure 2: Comparison of efficiency on three datasets (PubMed, CS, and OGB-Collab). We plot the retraining approach in solid lines, general unlearning methods in dotted lines, and graph unlearning methods in dash-dotted lines. Results show that GNNDelete scales better than existing graph unlearning methods, as its execution time is consistently lower than other methods, especially for larger graphs.
effective graph unlearning. By combining the deletion operator with these two properties, we define a novel loss function for graph unlearning. We evaluate GNNDelete across a wide range of deletion tasks including edge deletion, node deletion, and node feature unlearning, and demonstrate that it outperforms existing graph unlearning models. Our experiments show that GNNDelete performs consistently well across a variety of tasks and is easy to use. Results demonstrate the potential of GNNDelete as a general strategy for graph unlearning.
## Acknowledgements

We gratefully acknowledge the support of the Under Secretary of Defense for Research and Engineering under Air Force Contract No. FA8702-15-D-0001 and awards from Harvard Data Science Initiative, Amazon Research Award, Bayer Early Excellence in Science Award, AstraZeneca Research, and Roche Alliance with Distinguished Scientists Award. G.D. is supported by the Harvard Data Science Initiative Postdoctoral Fellowship. Any opinions, findings, conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the funders. The authors declare that there are no conflict of interests.
