Adaptive Graph Unlearning

1 Introduction

Machine unlearning (MU) [Sekhari et al., 2021] has emerged as a pivotal step towards responsible AI, enabling the efficient removal of irrelevant, inaccurate, or privacy-sensitive data from trained models. While most MU methods focus on image or text data in Euclidean space, real-world data often appear in the form of graphs, prompting growing interest in unlearning for graph-based models, particularly graph neural networks (GNNs). For instance, fraudulent accounts in financial networks and outdated relations in knowledge graphs should be removed from their corresponding trained GNNs to prevent erroneous predictions. A naive approach is to retrain a new GNN on the updated graph, but this is costly and impractical for frequent unlearning requests. To address this issue, graph unlearning (GU) [Fan et al., 2025] has been proposed to efficiently eliminate the influence of specific graph elements (e.g., nodes and edges) from trained GNNs. Because the effectiveness of GNNs relies on message propagation across local neighborhoods, effective GU requires not only forgetting information related to the unlearning elements (e.g., deleted nodes or edges in Fig. 1), but also minimizing their impact on neighboring nodes, referred to as affected neighbors (e.g., ego nodes, 1- and 2-hop neighbors in Fig. 1).

∗Corresponding author

Recently, a wide range of GU studies [Wu et al., 2023a; Tan et al., 2024] focus on developing general frameworks that can address various GU tasks (e.g., node and edge unlearning) while supporting different backbone GNN architectures (e.g., GCN [Kipf and Welling, 2016] and GAT [Velickovic et al., 2017]). However, these studies either overlook the distinct objectives of different GU tasks, or neglect the unique message-passing mechanisms of various GNN architectures, leading to two critical limitations as follows.

Limitation 1: Ineffective Forgetting of Unlearning Elements. To remove information about deleted elements from a trained GNN, a series of GU methods [Li et al., 2024b; Kolipaka et al., 2024] adopt a common MU strategy that penalizes the trained GNN for correctly predicting labels associated with deleted elements. However, this strategy is not universally effective across all GU tasks and often results in incomplete or over unlearning: (1) Incomplete nodeunlearning: These methods input the remaining graph and deleted nodes into the trained GNN to generate labels for unlearning. However, since deleted nodes become isolated after removal, unlearning them in isolation only forgets their intrinsic attributes (e.g., node features), while ignoring the need to forget their original connections (e.g., related edges in Fig. 1(a)). (2) Over edge-unlearning: These methods transform edge-level GU tasks into node unlearning scenarios. Specifically, nodes connected to deleted edges (referred to as ego nodes, as shown in Fig. 1(b)) are treated as unlearning elements, while the topology of the remaining (undeleted) edges is preserved. However, this transformation inadvertently leads to the unlearning of these ego nodes' features, which should instead be retained in the remaining graph.

Limitation 2: Inaccurate Identification of Affected Neighbors. Existing GU methods have demonstrated that unlearning performance is heavily influenced by the identification of affected neighbors [Wu et al., 2023b; Dong et al., 2024]. However, these methods uniformly set the same affected range for all backbone GNNs. This setting overlooks the fact that different GNN architectures (e.g., GCN and GAT) employ distinct message-passing mechanisms, resulting in different degrees of influence on neighbors in node and edge unlearning. Table 1 compares the affected ranges used in existing methods with those identified in our study.

Figs. 1(c) and 1(d) illustrate why the affected ranges differ across various backbone GNNs. Consider the messagepassing process of node v3 in a two-layer GNN, where v3 aggregates messages from its neighbors within two hops (e.g., node features of v1 and v2). If node v0 or edge (v0, v1) is deleted, the degree of v1 decreases. Since GCN normalizes neighbor features based on node degrees, this degree change affects the message aggregated by v3, i.e., ∆msg(v3)̸=0. In contrast, GAT aggregates neighbor information without degree-based normalization, leaving the message aggregated at v3 unaffected, i.e., ∆msg(v3)=0. Consequently, the affected range in GAT is one hop smaller than that in GCN. Although some GU methods [Li et al., 2024b] propose strategies to select important affected neighbors, they overlook the different impact of degree changes on various GNNs, limiting their ability to accurately identify truly affected neighbors.

Our Work. In this paper, we propose an Adaptive Graph Unlearning framework (AGU) that flexibly adapts to various GU tasks and backbone GNNs. To address Limitation 1, we propose the task-adaptive element forgetting, which contains two basic unlearning modules that can be combined to effectively handle GU tasks at the node, edge, and feature levels. To address Limitation 2, we propose a GNN-adaptive neighbor selection strategy, which accurately identifies affected neighbors for each backbone GNN, and prioritizes highly affected neighbors across different GU tasks.

Contributions. (1) Affected neighbor correction. We iden-

tify and rectify inaccuracies in affected neighbor identification, a longstanding issue in the GU literature. (2) Adaptive GU framework. We propose a novel framework that flexibly adapts to various GU tasks and backbone GNNs. (3) Universal selection strategy. We propose a novel neighbor selection strategy that can be integrated into existing GU methods, improving both effectiveness and efficiency. (4) SOTA performance. Extensive experiments on seven real-world graphs show that AGU outperforms state-of-the-art methods in terms of effectiveness, efficiency, and unlearning capability.

2 Preliminaries

2.1 Notations and Background

Consider a graph G={V, E, X} with |V| nodes and |E| edges. Each node vi ∈ V is associated with a feature vector xi ∈ X. In this paper, we focus on the node classification task. The training set D0 contains N samples {z1, z2, . . . , zN}, each annotated with a label y ∈ Y. The objective is to train a GNN model f to predict the label of a given node v ∈ V.

2.2 Graph Unlearning

In this part, we provide an overview of recent advances in GU. Early studies primarily focus on specific unlearning tasks and backbone GNN architectures. For instance, GraphEraser [Chen et al., 2022] and GUIDE [Wang et al., 2023] partition the graph into multiple shards and process the affected ones, but they only support node unlearning tasks. GraphEditor [Cong and Mahdavi, 2022], SGCunlearn [Chien et al., 2023], and ScaleGUN [Yi and Wei, 2025] offer closedform solutions with theoretical guarantees but are limited to linear GNNs. Recent advancements [Li et al., 2024a; Yang et al., 2025] extend GU to a wider range of tasks and backbone GNNs. For example, Delete [Cheng et al., 2023] proposes general operators to remove deleted elements, while GIF [Wu et al., 2023a] and IDEA [Dong et al., 2024] estimate parameter changes for various GU tasks. MEGU [Li et al., 2024b] improves performance by identifying highly affected neighbors. However, these methods either overlook the distinct objectives of different GU tasks or inaccurately identify affected neighbors, leading to suboptimal performance.

2.3 Graph Unlearning Formalization

Given a GNN model fG trained on a graph G, and an unlearning request ∆G={∆V,∆E,∆X}, the goal of GU is to derive a newGNNmodel ˆ f that closely approximates fG\∆G, which represents the model retrained from scratch on the remaining graph G\∆G. GU tasks can be classified into three types: Node Unlearning: ∆G={∆V, ∅, ∅}, where ∆V is the set of nodes to be unlearned. Edge Unlearning: ∆G={∅,∆E, ∅}, where ∆E is the set of edges to be unlearned. Feature Unlearning: ∆G={∅, ∅, ∆X}, where ∆X denotes the set of features to be unlearned, which will be replaced with zeros.

3 Methodology

3.1 Framework Overview

The overall framework of AGU is illustrated in Fig. 2. To address incomplete or over unlearning across different GU tasks Node Unlearning (ℒ𝑁𝑁𝑁𝑁= 𝛼𝛼ℒ𝐸𝐸𝐸𝐸+ ℒ𝐹𝐹𝐹𝐹)

Affected neighbor loss ℒ𝐴𝐴𝐴𝐴

Figure 2: The overall architecture of our proposed AGU framework.

and accurately identify affected neighbors, AGU includes two key components: (1) Task-adaptive element forgetting, which contains two basic unlearning modules that can be combined to comprehensively forget information at the node, edge, and feature levels, respectively. (2) GNN-adaptive neighbor selection, which determines the accurate affected range for different GNNs and identifies highly affected neighbors. These components empower AGU to perform specific strategies for different GU tasks while effectively mitigating the influence on affected neighbors across various GNN architectures.

3.2 Task-adaptive Element Forgetting

GU tasks at the node, edge, and feature levels typically require distinct unlearning strategies, making it complex to address tasks across different levels. However, GU tasks at different levels share commonalities that can help reduce redundant unlearning processes and enable flexible adaptation to complex scenarios. In this section, we design two basic unlearning modules: edge connection unlearning and individual feature unlearning, which effectively address edge and feature unlearning, respectively. Moreover, their combination provides a comprehensive solution for node unlearning.

Edge Connection Unlearning. Given a GNN fG trained on a graph G and an edge unlearning task ∆G={∅,∆E, ∅}, we aim to adjust fG to obtain an unlearned model ˆ f. Ideally, ˆ f should be unable to recognize whether a deleted edge euv∈∆E was originally part of G. A common approach is to use the deleted edge consistency loss (LDEC) [Cheng et al., 2023], which minimizes the difference between the representations of deleted edges and those of randomly selected node pairs:

where ˆh and h represent the node embeddings output by ˆ f and fG, respectively. φ(·) aggregates the embeddings of two nodes (e.g., via concatenation). dis(·) is a function positively correlated with the difference. ∈R indicates random selection.

However, enforcing the end nodes of edges in ∆E to approximate random node pairs may not accurately reflect the actual post-deletion homophily, where connected nodes in a graph typically share similar attributes or belong to the same class [Zhu et al., 2020]. Therefore, even after the removal of edges in ∆E, their end nodes are expected to retain homophily and should not be treated as randomly paired nodes.

To preserve the underlying homophily between nodes (u, v) ∈ ∆E, we refine Eq. (1) by proposing a new candidate set V k uv for selecting comparable node pairs. Specifically, V k uv consists of common neighbors within the k-hop range of u and v, i.e., V k uv = V k u ∩V k v , where V k v denotes the set of nodes within k hops of v. We replace V in Eq. (1) with V k uv to define our edge unlearning loss, denoted as LEU. If |V k u ∩ V k v | < 2, we set V k uv as the union of the two sets, i.e., V k u ∪V k v .

Individual Feature Unlearning. Since fG is trained using node labels as supervision signals, feature unlearning (∆G={∅, ∅,∆X}) requires the unlearned GNN ˆ f to dissociate the node features in ∆X from their corresponding labels predicted by fG. Existing methods [Li et al., 2024b; Kolipaka et al., 2024] typically achieve this through gradient ascent, which penalizes ˆ f for predicting the same labels as fG for nodes associated with ∆X .

However, since GNNs aggregate neighbor information to generate representations for prediction, directly applying gradient ascent can lead to the loss of valuable neighbor information, potentially degrading the performance of the unlearned GNN ˆ f. For example, if fG employs a weighted aggregation strategy that assigns lower weights to the target node v but higher weights to its neighbors, v's own features contribute less to its prediction. In this case, applying gradient ascent to v does not entirely cut the relationship between its features and the corresponding label. Instead, it may inadvertently degrade the prediction performance of other nodes that share similar neighbor information with v.

To address this issue, we propose a novel feature unlearning strategy that adaptively forgets deleted features while preserving valuable neighbor information. Specifically, we freeze the trained GNN fG and input individual nodes without edge connections (i.e., G\E) into fG to obtain their independent label distributions y′ as self-supervised signals. Then, we enforce the unlearned GNN ˆ f to output a distinct label distribution ˆy on the remaining graph G\∆G:

where V∆X denotes the set of nodes whose features are to be unlearned. LKL(·) is the Kullback-Leibler divergence. The rationale behind Eq. (2) is: (1) If fG relies more on u's features for prediction, y′u should approximate yu. Thus, enforcing a distributional difference between y′u and ˆyu encourages ˆ f to forget the correlation between u's features and the prediction made by fG. (2) If fG relies more on u's neighbor information for prediction, y′u should differ from yu. Thus, enforcing a distributional difference between y′u and ˆyu can forget u's own features while preserving valuable neighbor information. Node Unlearning. A simple yet common strategy to forget deleted nodes ∆V in a trained node classification model fG is to apply a reverse cross-entropy loss: - ∑u∈∆V LCE(y u , ˆy u ), where y u is the prediction of fG on G, and ˆy u is the prediction of ˆ f on the remaining graph G\∆V. However, since the nodes in ∆V become isolated after deletion, ˆy u depends only on u's own features and is no longer influenced by its original neighbors. Thus, applying this loss function cannot ensure ˆ f fully forgets the original connections between u and its neighbors.

For comprehensive node unlearning, we adopt a new perspective by transforming the task from {∆V, ∅, ∅} to {∅, ∆E, ∆X}, where ∆E represents the edges connected to nodes in ∆V, and ∆X denotes node features of ∆V. This transformation allows us to combine our proposed edge and feature unlearning modules to derive the node unlearning loss LNU:

where α is a loss coefficient hyper-parameter.

3.3 GNN-adaptive Neighbor Selection

Existing studies [Wu et al., 2023b; Li et al., 2024b] show that unlearning performance heavily depends on the identification of affected neighbors. Moreover, selecting highly affected neighbors can improve both the effectiveness and efficiency of unlearning. In this section, we address inaccuracies in existing methods for identifying affected neighbors and propose a novel GNN-adaptive selection strategy.

Accurate Affected Neighbor Identification. Given a k-layer trained GNN fG on graph G and an unlearning request ∆G, existing GU methods identify the affected neighbors Naff either directly based on the number of layers (i.e., k) [Dong et al., 2024; Li et al., 2024b] or through k-step normalized propagation [Wu et al., 2023a; Chen et al., 2023] as follows:

where A and ˆA are the adjacency matrices of G and G\∆G, respectively, with D and ˆD as their corresponding degree matrices. ∆H( ˆA,A) quantifies the propagation change before and after deleting unlearning elements. Nodes outside ∆G that satisfy ∆H( ˆA, A)̸=0 are considered affected neighbors.

However, this identification method is limited to backbone GNNs that incorporate node degrees in message passing (e.g., GCN, SGC [Wu et al., 2019]), which we refer to as degreebased GNNs. In contrast, degree-free GNNs (e.g., GAT, GIN [Xu et al., 2018]) aggregate neighbor information without relying on node degrees, leading to a different set of affected neighbors. As discussed in Section 1, degree-free GNNs typically influence fewer nodes than their degree-based counterparts. We validate this difference through experiments (see Appendix [Ding et al., 2025] for details). This influence discrepancy suggests that existing methods incorrectly set the same range of affected neighbors for all backbone GNNs. To address this issue, we summarize the correct affected range for popular GNNs in Table 1, and propose a simple yet general strategy to accurately identify affected neighbors without analyzing the architecture of the trained GNN fG:

where frand denotes a randomly initialized GNN with same architecture as fG. Note that in practice, it is crucial to remove randomness from frand's message-passing process to ensure accurate identification of affected neighbors.

Marginal Neighbor Filtering. For node and edge unlearning, degree-based GNNs affect an additional hop of neighbors compared to degree-free GNNs (as shown in Table 1). We refer to these extra affected neighbors as marginal neighbors. Note that for feature unlearning, since the graph structure remains unchanged after unlearning, the affected range is the same for all backbone GNNs.

We first analyze the impact of unlearning on marginal neighbors compared to other affected neighbors. Consider the message-passing process in a simple and classic degreebased GNN, SGC. The output for node i at the l-th layer is:

where N l i denotes the set of i's neighbors at the l-th hop. di is the degree of node i. The term ∏lt=1 √djt-1 djt represents the degree normalization over l layers.

In node unlearning, if i is a marginal neighbor, the deletion of unlearning nodes causes only a minor degree change, ∆d, for some of i's neighbors l hops away (i.e., djl ), while leaving N l i unchanged. In contrast, for other affected neighbors, message passing is often obstructed due to a reduction in N l i , leading to a more significant change in ∆h. Therefore, marginal neighbors tend to be less influenced than other affected nodes. To filter out marginal neighbors with minimal impact from degree changes, we propose the following filtering strategy: A marginal neighbor should be considered only if the degree change in its neighbors exceeds the effect of randomly removing one of its neighbors:

where A′ is the adjacency matrix obtained after randomly deleting an edge within the k-hop neighborhood of each node in ∆G. θ represents the difference threshold parameter.

Affected Neighbor Selection. In this part, we propose a general strategy to select important affected neighbors. Existing GU methods typically employ inverse feature propagation on the original graph G to identify highly affected neighbors. Specifically, they perform feature propagation (e.g., AkX) using the original feature matrix X and its inverse counterpart X′=1-X. By comparing propagation results for the same node, they identify highly affected neighbors as those with significant differences. However, this approach overlooks variations across different GU tasks and GNN architectures.

To address this limitation, we propose a task- and GNNadaptive neighbor selection module. The idea is to utilize the trained GNN to directly identify important affected neighbors. Specifically, we freeze the trained model fG and input G and G\∆G into fG. We then compare the differences in the node representations output by fG for these two graphs:

where fG(·)v denotes the representation of node v output by fG. dis(·) is a function that positively correlates with the difference. Intuitively, nodes with higher diff(·) values are more significantly affected by the unlearning elements. Thus, we select the top-kans nodes with the highest diff(·) values as important affected neighbors, denoted as Nhan. For degreebased GNNs, we first apply marginal neighbor filtering, then use the remaining affected neighbors for further selection.

Optimization Objective. Unlike the labels of unlearning elements in ∆G, which are intended to be forgotten in the unlearned GNN ˆ f, the predictive accuracy for the highly affected neighbors Nhan should be preserved in ˆ f. To this end, we follow [Li et al., 2024b] and treat the predictions of the original model (fG) as self-supervised signals for Nhan. Specifically, we freeze the parameters of fG and define a cross-entropy loss LAN=∑u∈Nhan LCE(y u , ˆy u ), where y u is the prediction of fG on G, and ˆy u is the prediction of ˆ f on G\∆G.

Finally, by combining LAN with the loss on the unlearning elements ∆G, the overall loss is formulated as:

where LEF is selected from {LNU,LEU,LFU} based on the specific GU task.

4 Experiments

We conduct extensive experiments to answer the following research questions: RQ1: How does AGU perform compared to state-of-the-art methods? RQ2: How does each proposed module in AGU contribute to the overall performance? RQ3: Can our proposed neighbor selection strategies enhance the performance of existing methods? RQ4: How do different parameter settings influence AGU's performance?

4.1 Experimental Setup

Datasets. We select seven widely used datasets: Cora, Citeseer, PubMed [Yang et al., 2016], Amazon-Photo, AmazonComputers, Coauthor-CS [Shchur et al., 2018], and Flickr [Zeng et al., 2019]. The datasets are split following the guidelines of recent GU studies [Cheng et al., 2023; Li et al., 2024b], with 80% of the nodes used for training and 20% for testing. Detailed statistics and descriptions of these datasets are provided in the Appendix [Ding et al., 2025].

Backbone GNNs and Baselines. We evaluate the adaptability of AGU using two degree-based GNNs: GCN [Kipf and Welling, 2016] and SGC [Wu et al., 2019], and three degreefree GNNs: GAT [Velickovic et al., 2017], SAGE [Hamilton et al., 2017], and GIN [Xu et al., 2018]. We compare AGU against seven state-of-the-art baselines: Delete [Cheng et al., 2023], GIF [Wu et al., 2023a], IDEA [Dong et al., 2024], MEGU [Li et al., 2024b], UTU [Tan et al., 2024], ETR [Yang et al., 2025], and Cognac [Kolipaka et al., 2024]. Detailed descriptions of these GNNs and baselines are provided in the Appendix. For all methods, we set the embedding dimension to 64, and fix the number of GNN layers at 2. Baseline parameters are initialized using the values reported in the original papers and further fine-tuned for optimal performance. In AGU, the edge unlearning loss LEU uses concatenation for φ(·) and mean-squared error for dis(·), while Eq. (9) uses cosine similarity for dis(·). The loss coefficient parameter α is set to 0.1. To ensure a fair comparison, each experiment is repeated 10 times and we report the average performance.

Unlearning Tasks. In our experiments, GU tasks are designed as follows: (1) Node-level: We randomly delete 5% of nodes from the training graph and remove their associated edges. (2) Edge-level: We randomly delete 5% of edges from the training graph. (3) Feature-level: We randomly select 5% of nodes from the training graph and mask their full-dimensional features. Results for other unlearn ratios are provided in the Appendix. All methods are evaluated using the Micro-F1 score for node classification. To further evaluate the unlearning capability of GU methods, we adopt the widely used Edge Attack approach [Wu et al., 2023a; Li et al., 2024b]. Specifically, we add noisy edges into the training graph to mislead representation learning. Each added edge connects two nodes from different classes to maximize its adversarial effect. These noisy edges are then treated as unlearning elements. The unlearning capability of GU methods is evaluated by their ability to mitigate the negative impact of these noisy edges on predictive performance.

4.2 Performance Comparison (RQ1)

We compare the performance of all methods from three perspectives: effectiveness, efficiency, and unlearning capability. Effectiveness. Tables 2 and 3 compare the node classification performance across various GU tasks and backbone GNNs. Notably, AGU consistently outperforms all baselines in F1score across all settings. On average, AGU achieves a 1.37% improvement over the best-performing baseline in node unlearning (ranging from 0.35% to 4.93%), 1.21% in edge unlearning (0.31% to 2.28%), and 1.26% in feature unlearning (0.47% to 3.31%). These results demonstrate AGU's robustness across diverse GU tasks and backbone GNNs, highlighting the effectiveness of its task-adaptive element forgetting and GNN-adaptive neighbor selection. In contrast, existing methods adopt uniform unlearning strategies, leading to inferior overall performance. For instance, Delete, which adopts an edge-based unlearning strategy, performs well in edgelevel GU tasks but struggles in other GU tasks. These findings further validate the necessity of designing task-specific unlearning strategies for different GU tasks.

Efficiency. We report the average unlearning time in Table 4. The results show that AGU outperforms other training-based methods (Delete, MEGU, and Cognac), achieving a speedup from 1.36× to 29×. Compared to training-free methods (GIF, IDEA, ETR), which directly adjust model parameters without training, AGU remains competitive, ranking second only to ETR in some cases. However, ETR requires additional time to extract subgraphs based on specific unlearning requests before initiating the unlearning process. Moreover, our experiments reveal that these training-free methods require careful parameter tuning to avoid model invalidation on the testing graph. In contrast, AGU ensures robust performance with minimal training epochs (20-30).

Unlearning Capability. Fig. 3 presents the node classification performance under different edge attack ratios. To provide a clear baseline for comparison, we introduce vanilla train, which retrains a new GNN directly on the noisy graph. The results demonstrate that AGU consistently outperforms other baselines and remains stable across varying attack ratios, particularly when using GAT as the backbone GNN. Notably, unlike Delete, which adopts a random node-pair strategy for contrastive edge unlearning, AGU leverages homophily consistency between connected nodes to more effectively distinguish noisy edges from real ones, thereby mitigating the impact of edge attacks.

4.3 Ablation Study (RQ2)

We conduct ablation studies by creating five AGU variants to evaluate the contributions of its key components: (1) w/o Homo: This variant replaces the homophily-based node-pair strategy with a random node-pair strategy for contrastive edge unlearning, allowing us to assess the effectiveness of the proposed edge unlearning module. (2) w/o EU and w/o FU: Since AGU combines the edge unlearning (EU) and feature unlearning (FU) modules to address node unlearning tasks, these two variants independently evaluate the contributions of EU and FU to the overall unlearning performance. (3) w/o MNF: This variant removes the marginal neighbor filtering (MNF) module to evaluate its impact, particularly on degree-based GNNs (e.g., GCN). (4) w/o ANS: This variant excludes the affected neighbor selection (ANS) module to assess its influence on the unlearning process. The results in Table 5 show that AGU consistently outperforms all variants across all cases. This not only validates the importance of combining EU and FU for effective node unlearning, but also highlights the critical roles of MNF and ANS in identifying highly affected nodes for efficient and effective unlearning.

4.4 Strategy Generalizability (RQ3)

We evaluate the generalizability of our proposed neighbor selection strategies, MNF and ANS, by integrating them into existing GU methods: Delete, MEGU, and ETR. While MEGU and ETR have their own neighbor selection strategies, we replace them with MNF and ANS for comparison. In addition, we provide the "+AAN" variant, which selects accurate affected neighbors for degree-free GNNs (e.g., GAT). To reflect real-world scenarios with frequent but small-scale unlearning requests, we set the unlearn ratio to 1%. Our statistics show that in a 2-layer GNN, removing just 1% of nodes affects over 70% of the remaining nodes in the Photo and Computer datasets. We also conduct experiments on other datasets with various backbone GNNs and unlearn ratios (see Appendix). Our results demonstrate that MNF and ANS can be effectively integrated into existing GU frameworks, improving both effectiveness and efficiency across different datasets, backbone GNNs, and unlearn ratios. Specifically, the results in Table 6 show that (1) For degree-based GNNs (e.g., GCN), applying MNF or ANS consistently reduces unlearning time while preserving prediction performance in most cases. Combining both strategies further improves prediction performance and reduces unlearning time by 11% to 36%. (2) For degree-free GNNs (e.g., GAT), using ANS enhances prediction performance in most cases while achieving a comparable reduction in unlearning time (25% to 48%).

4.5 Parameter Study (RQ4)

We investigate the sensitivity of two key parameters θ and kans in AGU. The parameter θ controls the filtering of marginal neighbors (Nfmn) when using degree-based GNNs as backbones, while kans determines the proportion of affected neighbors selected as highly affected neighbors (Nhan). As shown in Fig. 4, increasing θ generally improves unlearning performance. However, when θ becomes too large, the number of filtered marginal neighbors approaches zero, leading to a performance degradation. Thus, the optimal range for θ is between 5e - 5 and 5e - 4. For kans, a value around 40% can achieve a good trade-off between effectiveness and efficiency.

5 Conclusion

In this paper, we identify two significant limitations in existing GU studies: ineffective forgetting of unlearning elements and inaccurate identification of affected neighbors. These issues arise from the neglect of differences across various GU tasks and backbone GNNs. To address these issues, we propose AGU, an adaptive graph unlearning framework that unifies different GU tasks and develops general neighbor selection strategies adaptable to diverse backbone GNNs. Extensive experiments demonstrate the superior performance of AGU in terms of efficiency, effectiveness, and unlearning capability. In future work, we plan to extend our AGU framework to support various types of graph data, including heterogeneous graphs, knowledge graphs, and temporal graphs.

Acknowledgments

This work is supported by the Australian Research Council Discovery Project DP230100676.