REVIEW 3 major objections 5 minor 26 references
Adaptive Graph Unlearning
T0 review · 3 major / 5 minor · reviewed 2026-08-15 · deepseek-v4-flash
Pith's one-line read Adaptive graph unlearning beats seven baselines on seven graphs
desk verdict A serious empirical unlearning method whose headline claim about GNN blast radii doesn't survive attention renormalization; major revision needed. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The load-bearing machinery is the contrast between degree-normalized and degree-free message passing. In a GCN or SGC, deleting a node or edge lowers the degree of a neighboring node, and the symmetric degree normalization $D^{-1/2}AD^{-1/2}$ changes the message that a two-hop node aggregates; in a GAT, attention weights are renormalized over remaining neighbors, so the paper assumes a two-hop message is unchanged. AGU operationalizes this through three mechanisms: a random-initialized GNN comparison of the original and remaining graph to fix the affected-neighbor set, a marginal-neighbor filter that keeps a degree-affected hop only when the degree change exceeds random-edge deletion, and an affected-neighbor selection that freezes the trained model and selects nodes whose representations shift most, then preserves their predictions. Task adaptivity is carried by two base losses, an edge unlearning loss $L_{EU}$ and a feature unlearning loss $L_{FU}$, whose weighted sum forms the node unlearning loss $L_{NU} = \alpha L_{EU} + L_{FU}$.
What would settle it
Train a two-layer GAT on Cora, delete a node $v_0$, and compute the representation change of a two-hop neighbor $v_3$: $\lVert h^{(2)}_{v_3}(G) - h^{(2)}_{v_3}(G\setminus\{v_0\})\rVert$. If this norm is nonzero above floating-point noise for any $v_0$, then the message at $v_3$ changes and the claimed equal affected range for GAT is false. The same test on edge deletion settles whether the K−1 edge range is right.
Extended reading notes
Core claim
AGU's central discovery is that effective graph unlearning is both task-adaptive and architecture-adaptive. For the task dimension, node unlearning should be decomposed into edge-connection unlearning plus individual-feature unlearning, because a deleted node becomes isolated and its original connections must be forgotten along with its features; edge unlearning should compare deleted edges against common k-hop neighbors rather than random node pairs, preserving homophily; feature unlearning should use the frozen model's own node-only predictions as a self-supervised signal and drive a KL-divergence between those and the unlearned model's predictions. For the architecture dimension, the paper identifies affected neighbors by running a randomly initialized GNN (with randomness removed) on the graph before and after deletion, and reports that degree-based GNNs need ranges of K+1 hops for node deletion and K hops for edge deletion, while degree-free GNNs need K and K−1 hops respectively. The extra hop, called marginal neighbors, is filtered by a threshold on degree-change influence, and the remaining affected neighbors are ranked by representation difference to pick the top-k for a preservation loss. The paper claims that this combination ensures complete forgetting of deleted elements while keeping the remaining graph's predictions close to a retrained model.
Load-bearing premise
The framework's architecture-specific claim rests on the assumption that in degree-free GNNs, removing a node or edge leaves the message a two-hop node receives exactly unchanged, because attention weights are renormalized over the remaining neighbors; if real attention layers leak any change to that second hop, the K-hop ranges for GAT, GIN, and SAGE would be off by one, and the paper's validation of this point is deferred to an external appendix.
Editorial extensions
If this is right
- Correcting the affected-neighbor range alone should cut both over-unlearning and under-unlearning: degree-free GNNs currently waste effort on a hop that does not change, while degree-based GNNs miss an extra hop that does.
- Treating node unlearning as combined edge plus feature unlearning gives a direct recipe for forgetting a deleted node's original connections, not just its isolated features.
- Because the neighbor-selection modules are plug-in, existing methods such as Delete, MEGU, and ETR should gain accuracy and efficiency simply by adopting MNF and ANS, with reported time reductions of 11–36% on degree-based GNNs and 25–48% on GAT.
- AGU's edge unlearning predicts that forcing deleted-edge endpoints to resemble random pairs harms the remaining graph; comparing them to common neighbors instead should preserve homophily and improve resilience to noisy-edge attacks.
Reading between the lines
- The architecture taxonomy implies a testable generalization: GNNs that explicitly divide by degree should land in the K+1/K column, while aggregators like GatedGCN, PNA, or graph transformers need their own hop audit rather than inheriting GAT's K/K−1 range.
- If the random-initialized GNN comparison reliably identifies affected neighbors, it could serve as a practical audit tool: a deployer can verify unlearning completeness by checking whether any retained node's representation still shifts after deletion, without retraining.
- The homophily-preserving candidate set for edge unlearning is tailored to assortative graphs; on heterophilous networks where connected nodes often carry different labels, the assumption that deleted endpoints stay similar would break, and AGU would need an alternative candidate distribution.
- The marginal-neighbor analysis suggests that in degree-based GNNs, small degree changes only matter when they cross a noise threshold; this invites a theoretical bound relating the threshold to the graph's degree distribution and the number of layers.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper proposes AGU, an adaptive graph unlearning framework that combines task-adaptive element forgetting with GNN-adaptive neighbor selection. The element-forgetting component introduces an edge connection unlearning loss (LEU), an individual feature unlearning loss (LFU), and a node unlearning loss (LNU = αLEU + LFU). The neighbor-selection component classifies GNNs into degree-based (GCN, SGC) and degree-free (GAT, GIN, SAGE) families, assigns affected ranges of K+1/K hops for node/edge unlearning to degree-based GNNs and K/K-1 hops to degree-free GNNs, and adds marginal neighbor filtering plus affected neighbor selection. Experiments on seven real-world graphs, five backbone GNNs, and seven baselines report consistent F1 improvements, competitive or faster runtimes, and better recovery from noisy-edge attacks. Ablations and integration of the proposed selection modules into existing methods are also presented.
Significance. If the architecture-dependent affected-range claim were correct, AGU would be a practical and general contribution to graph unlearning: the experimental coverage is extensive, the ablations indicate that each module contributes, and the proposed neighbor-selection strategies are shown to transfer to existing baselines. However, the central theoretical premise of the paper -- that degree-free GNNs propagate deletion influence to strictly fewer hops than degree-based GNNs -- is not established and is contradicted by standard message-passing renormalization. Because this premise drives Table 1, the marginal neighbor filtering (Eq. 8), and the claim of accurately identifying affected neighbors, the headline contribution is not reliable even though the empirical F1 gains may partially stem from the task-adaptive losses.
major comments (3)
- [§4.3, Fig. 1, Table 1] The claimed one-hop-smaller affected range for GAT, GIN, and SAGE is not a consequence of omitting degree normalization, and the paper's own message-passing analysis does not support it. In a two-layer GAT, deleting node v0 removes v0 from v1's neighborhood, which renormalizes the softmax attention coefficients of v1 and changes the layer-1 representation h_v1^(1); since v3 aggregates h_v1^(1) at layer 2, the change in the message received by v3 is generally nonzero. The same argument applies to GIN, whose sum aggregation changes when the neighbor set changes, and to SAGE, whose mean aggregation divides by a changed neighbor count. The paper defers the only validation of this distinction to the external appendix [Ding et al., 2025], which is not part of the preprint. Since this premise is load-bearing for Table 1 and for Eq. (8)'s marginal-neighbor filtering, the claim of accurate affected-neighbor identification is not established.
- [§4.3, Eq. (6)] Eq. (6) proposes to identify affected neighbors by comparing outputs of a randomly initialized frand on G and G\Delta G, with the remark that 'randomness must be removed' from the message-passing process. A randomly initialized network cannot certify the influence range of the trained model fG: for GAT, the set of affected nodes depends on the learned attention weights, not merely on the presence or absence of degree normalization. The phrase 'remove randomness' is undefined (fixed seed, zeroed attention, or something else), and the equation as written does not validate Table 1. A concrete test would be to measure the actual representation difference of a trained GAT after deleting a node or edge and compare it with the predicted affected range; the paper does not provide such evidence in the main text.
- [§5.2, Fig. 3] The abstract and Section 1 state that AGU 'ensures the complete forgetting of deleted elements,' but the reported experiments measure only downstream node-classification F1 and recovery from noisy-edge attacks. There is no direct evaluation of forgetting, such as membership-inference tests, deletion-influence metrics, or queries on the deleted elements themselves. The completeness claim in the abstract is therefore not supported by the evidence provided.
minor comments (5)
- [Table 2] The column header 'Bone' should read 'Backbone'; Table 6 also contains formatting inconsistencies such as '85.8+.3' and '85.1±.4' in adjacent rows.
- [§4.2, Eq. (1)] The notation 'p, q ∈ R V' is garbled and should be written as 'p, q randomly sampled from V.' In addition, φ(·) and dis(·) are not formally defined in the main text; the reader has to wait until Section 5.1 to learn that φ is concatenation and dis is mean-squared error or cosine similarity.
- [§4.3, Eq. (8)] The construction of A′, obtained by 'randomly deleting an edge within the k-hop neighborhood of each node in ΔG,' is not fully specified: the distribution over deleted edges, the choice of k, and the relationship to the threshold θ should be stated precisely.
- [§5.5] The sensitivity analysis covers only θ and k_ans; the node-unlearning coefficient α is fixed at 0.1 without a reported sweep, despite α directly controlling the balance between LEU and LFU in Eq. (3).
- [References] The appendix is referenced as a GitHub URL [Ding et al., 2025]. Since the architecture-dependent affected-range claim is central and the main text provides no verification, the supporting material should be included with the submission rather than only linked externally.
Circularity Check
No circular derivation: AGU's losses and neighbor selection are constructive design choices, and the affected-range claim is an architectural inference rather than an input reused as output.
full rationale
I walked the derivation chain: task-adaptive forgetting (LEU, LFU, LNU) is defined from unlearning objectives and combined loss terms; none of these losses is fitted to the F1 numbers they later predict. The neighbor-selection modules (Nac via frand, Nfmn via Eq. 8, Nhan via Eq. 9) are operational heuristics: they identify nodes by representation change or degree-change thresholds, and LAN then preserves fG's predictions on selected neighbors as self-supervision. This is a design choice, not a hidden fit, because the target of unlearning is precisely closeness to fG on retained nodes. Table 1's range difference (degree-based K+1/K vs degree-free K/K-1) is derived by an architectural argument about degree normalization, not by substituting Table 1 into the loss. The one caveat is that the paper defers empirical validation of this range difference to a self-authored appendix [Ding et al., 2025]; that is an unverified support gap in the preprint, but it is not a circular reduction: no equation in the paper is equivalent by construction to the claimed result, and the experimental claims are benchmarked against external retraining and seven baselines. Therefore no specific circular step meets the quoting-plus-reduction bar.
Assumptions & free parameters
free parameters (3)
- theta (marginal neighbor filtering threshold) =
~5e-5 to 5e-4
- k_ans (proportion of affected neighbors selected as highly affected) =
~40%
- alpha (node unlearning loss coefficient) =
0.1
assumptions (3)
- ad hoc to paper Degree-free GNNs (GAT/GIN/SAGE) propagate deletion influence to fewer hops than degree-based GNNs; specifically GAT's affected range is one hop smaller than GCN's.
- domain assumption A randomly initialized GNN with the same architecture can identify the set of affected neighbors for the trained GNN (Eq. 6).
- domain assumption Connected nodes in graphs are typically homophilous, so deleted edges' endpoints should be pushed toward common-neighbor pairs rather than random pairs.
Cite this review
Pith. "Pith review of Adaptive Graph Unlearning." pith.science (2026). https://pith.science/paper/PNAD7F5M
@misc{pith2026250512614,
author = {Pith},
title = {Pith review of: Adaptive Graph Unlearning},
year = {2026},
howpublished = {\url{https://pith.science/paper/PNAD7F5M}},
note = {Machine review of arXiv:2505.12614}
}
read the original abstract
Graph unlearning, which deletes graph elements such as nodes and edges from trained graph neural networks (GNNs), is crucial for real-world applications where graph data may contain outdated, inaccurate, or privacy-sensitive information. However, existing methods often suffer from (1) incomplete or over unlearning due to neglecting the distinct objectives of different unlearning tasks, and (2) inaccurate identification of neighbors affected by deleted elements across various GNN architectures. To address these limitations, we propose AGU, a novel Adaptive Graph Unlearning framework that flexibly adapts to diverse unlearning tasks and GNN architectures. AGU ensures the complete forgetting of deleted elements while preserving the integrity of the remaining graph. It also accurately identifies affected neighbors for each GNN architecture and prioritizes important ones to enhance unlearning performance. Extensive experiments on seven real-world graphs demonstrate that AGU outperforms existing methods in terms of effectiveness, efficiency, and unlearning capability.
Figures
Figures from the paper (1 more)
Reference graph
Works this paper leans on
-
[1]
[Chen et al., 2022] Min Chen, Zhikun Zhang, Tianhao Wang, Michael Backes, Mathias Humbert, and Yang Zhang. Graph unlearning. In ACM CCS, pages 499–513,
work page 2022
-
[4]
Efficient model updates for approximate un- learning of graph-structured data
[Chien et al., 2023] Eli Chien, Chao Pan, and Olgica Milenkovic. Efficient model updates for approximate un- learning of graph-structured data. In ICLR,
work page 2023
-
[5]
Grapheditor: An efficient graph representation learn- ing and unlearning approach
[Cong and Mahdavi, 2022] Weilin Cong and Mehrdad Mah- davi. Grapheditor: An efficient graph representation learn- ing and unlearning approach
work page 2022
-
[6]
[Corso et al., 2024] Gabriele Corso, Hannes Stark, Stefanie Jegelka, Tommi Jaakkola, and Regina Barzilay. Graph neural networks. Nature Reviews Methods Primers , 4(1):17,
work page 2024
-
[9]
OpenGU: A Comprehensive Benchmark for Graph Unlearning
[Fan et al., 2025] Bowen Fan, Yuming Ai, Xunkai Li, Zhilin Guo, Rong-Hua Li, and Guoren Wang. OpenGU: A comprehensive benchmark for graph unlearning. arXiv preprint arXiv:2501.02728,
work page Pith review arXiv 2025
-
[10]
Inductive representation learning on large graphs
[Hamilton et al., 2017] Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. NeurIPS, 30,
work page 2017
-
[12]
Semi-supervised classification with graph convolutional networks
[Kipf and Welling, 2016] Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. arXiv preprint arXiv:1609.02907,
arXiv 2016
-
[14]
TCGU: Data-centric graph unlearning based on transferable con- densation
[Li et al., 2024a] Fan Li, Xiaoyang Wang, Dawei Cheng, Wenjie Zhang, Ying Zhang, and Xuemin Lin. TCGU: Data-centric graph unlearning based on transferable con- densation. arXiv preprint arXiv:2410.06480,
Show all 26 references
-
[15]
Remem- ber what you want to forget: Algorithms for machine un- learning
[Sekhari et al., 2021] Ayush Sekhari, Jayadev Acharya, Gautam Kamath, and Ananda Theertha Suresh. Remem- ber what you want to forget: Algorithms for machine un- learning. NeurIPS, 34:18075–18086,
2021
-
[18]
Graph attention networks
[Velickovicet al., 2017] Petar Velickovic, Guillem Cucu- rull, Arantxa Casanova, Adriana Romero, Pietro Lio, Yoshua Bengio, et al. Graph attention networks. stat, 1050(20):10–48550,
2017
-
[19]
Inductive graph unlearning
[Wang et al., 2023] Cheng-Long Wang, Mengdi Huai, and Di Wang. Inductive graph unlearning. In USENIX Se- curity, pages 3205–3222,
2023
-
[20]
Sim- plifying graph convolutional networks
[Wu et al., 2019] Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. Sim- plifying graph convolutional networks. In ICML, pages 6861–6871,
2019
-
[21]
How powerful are graph neural net- works? arXiv preprint arXiv:1810.00826,
[Xu et al., 2018] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural net- works? arXiv preprint arXiv:1810.00826,
2018 arXiv
-
[22]
Revisiting semi-supervised learning with graph embeddings
[Yang et al., 2016] Zhilin Yang, William Cohen, and Ruslan Salakhudinov. Revisiting semi-supervised learning with graph embeddings. In ICLR, pages 40–48,
2016
-
[23]
Erase then rectify: A training- free parameter editing approach for cost-effective graph unlearning
[Yang et al., 2025] Zhe-Rui Yang, Jindong Han, Chang- Dong Wang, and Hao Liu. Erase then rectify: A training- free parameter editing approach for cost-effective graph unlearning. In AAAI, pages 13044–13051,
2025
-
[24]
Scalable and cer- tifiable graph unlearning: Overcoming the approximation error barrier
[Yi and Wei, 2025] Lu Yi and Zhewei Wei. Scalable and cer- tifiable graph unlearning: Overcoming the approximation error barrier. In ICLR,
2025
-
[25]
Graph- saint: Graph sampling based inductive learning method
[Zeng et al., 2019] Hanqing Zeng, Hongkuan Zhou, Ajitesh Srivastava, Rajgopal Kannan, and Viktor Prasanna. Graph- saint: Graph sampling based inductive learning method. In ICLR,
2019
-
[2016]
A cognac shot to forget bad memories: Corrective unlearning in gnns.arXiv preprint arXiv:2412.00789,
[Kolipaka et al., 2024] Varshita Kolipaka, Akshit Sinha, De- bangan Mishra, Sumit Kumar, Arvindh Arun, Shashwat Goel, and Ponnurangam Kumaraguru. A cognac shot to forget bad memories: Corrective unlearning in gnns.arXiv preprint arXiv:2412.00789,
2024 arXiv
-
[2017]
A review of graph neural networks: concepts, architectures, techniques, challenges, datasets, applications, and future directions.Journal of Big Data, 11(1):18,
[Khemani et al., 2024] Bharti Khemani, Shruti Patil, Ketan Kotecha, and Sudeep Tanwar. A review of graph neural networks: concepts, architectures, techniques, challenges, datasets, applications, and future directions.Journal of Big Data, 11(1):18,
2024
-
[2018]
Unlink to unlearn: Simplifying edge unlearning in gnns
[Tan et al., 2024] Jiajun Tan, Fei Sun, Ruichen Qiu, Du Su, and Huawei Shen. Unlink to unlearn: Simplifying edge unlearning in gnns. In TheWebConf, pages 489–492,
2024
-
[2019]
Be- yond homophily in graph neural networks: Current lim- itations and effective designs
[Zhu et al., 2020] Jiong Zhu, Yujun Yan, Lingxiao Zhao, Mark Heimann, Leman Akoglu, and Danai Koutra. Be- yond homophily in graph neural networks: Current lim- itations and effective designs. NeurIPS, 33:7793–7804, 2020
2020
-
[2021]
Pitfalls of graph neural network evaluation
[Shchur et al., 2018] Oleksandr Shchur, Maximil- ian Mumme, Aleksandar Bojchevski, and Stephan G¨unnemann. Pitfalls of graph neural network evaluation. NeurIPS Workshop,
2018
-
[2022]
Characterizing the influence of graph elements
[Chen et al., 2023] Zizhang Chen, Peizhao Li, Hongfu Liu, and Pengyu Hong. Characterizing the influence of graph elements. In ICLR,
2023
-
[2023]
GNNDelete: A general strategy for unlearning in graph neural networks
[Cheng et al., 2023] Jiali Cheng, George Dasoulas, Huan He, Chirag Agarwal, and Marinka Zitnik. GNNDelete: A general strategy for unlearning in graph neural networks. ICLR,
2023
-
[2024]
AGU Appendix
[Ding et al., 2025] Pengfei Ding, Yan Wang, Guanfeng Liu, and Jiajie Zhu. AGU Appendix. https://github.com/ Aliezzz/AGU,
2025
-
[2025]
Idea: A flexible framework of certified unlearning for graph neural networks
[Dong et al., 2024] Yushun Dong, Binchi Zhang, Zhenyu Lei, Na Zou, and Jundong Li. Idea: A flexible framework of certified unlearning for graph neural networks. InKDD, pages 621–630,
2024
Reviewed August 15, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.