{"id":"0d900024-46f8-43e2-883d-697e42d410ae","arxiv_id":"2505.12614","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"AGU is an adaptive graph unlearning framework that combines task-specific edge and feature forgetting with GNN-specific affected-neighbor selection, and it reports state-of-the-art F1 and runtime on seven real-world graphs.","lead":"Graphs store relationships, and graph unlearning tries to make an already-trained graph neural network forget specific nodes or edges without full retraining. This paper proposes AGU, a framework that adapts the forgetting procedure to different unlearning tasks and to different GNN architectures, reporting better accuracy and speed than prior methods on seven graph datasets.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The one-hop-smaller affected range claimed for GAT/GIN/SAGE (Table 1, Figs. 1c-d) is not a consequence of omitting degree normalization; removing a neighbor renormalizes attention/aggregation and changes the intermediate representation, so two-hop messages usually change.","rationale":"The reader's conditional verdict identifies the right spot. My read makes the concern more definite: it is not merely that the appendix is missing; the stated reason for the GAT blast radius is incorrect. In a standard GAT, h_v1^{(1)} is a weighted sum over N(v1); deleting v0 changes both the set and the softmax renormalization, so h_v1^{(1)} changes, and since v3 aggregates h_v1^{(1)} at layer 2, Δmsg(v3)≠0. The paper's claim would require h_v1^{(1)} to be unchanged, which only happens in the degenerate case α_{v1,v0}=0 or if attention weights are artificially frozen rather than recomputed. For SAGE, mean pooling uses |N(v)| explicitly, so categorizing it as degree-free is internally inconsistent. Eq. (6) proposes a random-initialized GNN to determine affected neighbors, but a random GAT's attention is not the trained model's attention; removing randomness (e.g., uniform attention) defines a different architecture. Thus Table 1 and the marginal-neighbor filtering rely on an unvalidated and likely false premise. This does not automatically destroy the empirical contribution: the F1/runtime gains could survive from task-adaptive element forgetting. But the advertised 'accurate affected-neighbor identification' is not established. I would keep the paper under CONDITIONAL, with the concrete test above as a condition; if the test shows GAT reaches the same hop as GCN, the authors would need to either revise the theoretical framing or provide evidence that omitted neighbors matter negligibly.","tokens_in":17143,"tokens_out":6387,"duration_ms":66338,"concrete_test":"Train a 2-layer GAT on Cora; fix weights; for each of 100 randomly chosen nodes v0, delete v0 (or one incident edge) and recompute the output representation of a node v3 that is exactly two hops from v0 along a path v0-v1-v3. Compute the mean L2 distance ||h_v3 - h'_v3|| and the fraction of cases exceeding a small tolerance (e.g., 1e-6). Repeat with a random-initialized GAT and compare with a GCN. If the distance is nonzero in a non-negligible fraction, Δmsg(v3)≠0 and the Fig. 1(d)/Table 1 distinction collapses.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"AGU's core distinction between degree-based and degree-free GNNs is the claim that deleting a node (or edge) leaves the two-hop message Δmsg(v3)=0 in GAT because GAT has no degree normalization. This is unsound. In a K-layer GAT, v3's layer-2 output aggregates h_v1^{(1)} with an attention weight α_{v3,v1}. Deleting v0 removes v0 from v1's neighborhood, so the softmax over v1's incoming attention is renormalized and h_v1^{(1)} changes; hence the message from v1 to v3 changes. The same holds for GIN (sum aggregation over a changed neighbor set) and for SAGE (mean aggregation divides by the changed degree). The premise in Fig. 1(d) would only hold if v1's representation were invariant to deleting v0, which is not true for any nontrivial attention/aggregation weights. Eq. (6)'s proposed check using a randomly initialized frand with 'randomness removed' does not escape this: a real GAT's affected range depends on trained attention, not merely on whether degree normalization is present. The external appendix [Ding et al., 2025] is the only validation offered and is not part of the preprint. If the premise is false, AGU's GNN-adaptive neighbor selection omits genuinely affected neighbors for degree-free GNNs, and the accuracy claim in Table 1 is wrong even though the empirical F1 gains may still come from the task-adaptive losses.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":17462,"tokens_out":6489,"duration_ms":70090,"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":[{"comment":"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.","section":"§4.3, Fig. 1, Table 1"},{"comment":"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.","section":"§4.3, Eq. (6)"},{"comment":"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.","section":"§5.2, Fig. 3"}],"minor_comments":[{"comment":"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.","section":"Table 2"},{"comment":"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.","section":"§4.2, Eq. (1)"},{"comment":"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.","section":"§4.3, Eq. (8)"},{"comment":"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).","section":"§5.5"},{"comment":"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.","section":"References"}],"recommendation":"reject","confidential_remarks":"The experimental work is substantial and the ablations are well executed, but the core architectural claim about degree-free GNNs is analytically questionable and the only validation is an external appendix. I would be willing to reconsider a substantially revised version that either proves the affected-range claim under explicit assumptions or replaces it with an empirical, trained-model-based neighbor identification procedure, but as written the central contribution is not reliable."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nThis paper is worth your time, but read it with one eye on a specific, load-bearing claim that I think is wrong. The empirical story is genuinely solid — seven datasets, five GNNs, seven baselines, consistent wins, and ablations that show each module contributes. The framework's task-adaptive combination of edge and feature unlearning for node deletion is a reasonable piece of engineering, and the homophily-aware edge loss and representation-difference neighbor selection are sensible ideas.\n\nThe problem is the theoretical foundation for the 'GNN-adaptive' part. The paper claims that degree-free GNNs (GAT, GIN, SAGE) have a one-hop-smaller affected range than degree-based GNNs, because without degree normalization, deleting a node or edge leaves a two-hop node's message unchanged (Fig. 1d). That is not correct. In any attention-based or aggregation-based GNN, deleting a neighbor of an intermediate node renormalizes the attention weights (or changes the sum/mean), so the intermediate node's representation changes, and that change propagates to the next layer. The two-hop message does not stay fixed. The stress-test note is right about this.\n\nThere is also an internal contradiction: the text says v3, a 2-hop neighbor, is unaffected in GAT, while Table 1 says GAT node unlearning affects K hops (which, for K=2, includes v3). The paper defers validation to an external appendix, which is not in the preprint. That's not acceptable for a claim this central.\n\nThe empirical results are still meaningful. The F1 improvements over the best baseline are modest (1–2% on average) but consistent, and the runtime gains are real. The ablation study shows the neighbor selection and filtering modules help, and the strategy generalizes to existing baselines (Table 6). So the method may be useful even if the rationale is off. What needs fixing is the narrative: either prove (or empirically demonstrate over many graphs) that the ranges in Table 1 are accurate, or present Eq. (6) as the primary identification method and treat the theoretical ranges as heuristics.\n\nI would send this to peer review — the work is serious and the flaw is fixable — but I would not cite it in its current form, because the blast-radius claim could mislead. A careful referee should ask for a corrected theory, a direct measure of forgetting beyond F1 (e.g., membership inference or distance to a retrained model), and the appendix moved into the main text or clearly available. As it stands, it's a conditional reject or major revision, not a desk reject.","headline":"A serious empirical unlearning method whose headline claim about GNN blast radii doesn't survive attention renormalization; major revision needed.","tokens_in":18004,"tokens_out":8698,"would_cite":false,"duration_ms":82358,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"Adaptive graph unlearning beats seven baselines on seven graphs","keywords":["graph unlearning","graph neural networks","node unlearning","edge unlearning","feature unlearning","affected neighbor selection","degree normalization","machine unlearning"],"falsifier":"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.","tokens_in":16884,"feed_emoji":"🕸️","tokens_out":10463,"duration_ms":87377,"temperature":0.7,"pith_summary":"This paper argues that graph unlearning fails when it treats all deletion requests and all graph neural networks the same. The authors propose AGU, which matches the forgetting strategy to the type of deleted element (node, edge, or feature) and matches the set of affected neighbors to whether the backbone GNN normalizes messages by node degree. The central claim is that degree-based GNNs such as GCN and SGC propagate the influence of node deletion one hop farther than degree-free GNNs such as GAT, GIN, and SAGE, and that correcting this difference improves unlearning. On seven real-world graphs, AGU reports higher node-classification F1, faster unlearning, and stronger recovery from noisy-edge attacks than seven baselines. The paper's contribution is a concrete correction of neighbor identification that many existing graph unlearning methods get wrong.","feed_headline":"Adaptive graph unlearning beats seven baselines on seven graphs","feed_subtitle":"Deleted graph elements leave different footprints in GCN than in GAT; AGU matches the forgetting range to the architecture.","key_machinery":"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}$.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Carries the empirical validation deferred from Section 4.3 that degree-free GNNs affect one hop fewer than degree-based GNNs, plus dataset statistics.","marker":"[Ding et al., 2025]"},{"why":"GCN is the canonical degree-based backbone whose normalized propagation sets the K+1/K affected ranges.","marker":"[Kipf and Welling, 2016]"},{"why":"GAT is the canonical degree-free backbone whose attention renormalization motivates the K/K−1 affected ranges.","marker":"[Velickovicet al., 2017]"},{"why":"SGC is the degree-based backbone used in the marginal-neighbor degree-change analysis.","marker":"[Wu et al., 2019]"},{"why":"GIN is a degree-free backbone used as a testbed for the reduced affected range.","marker":"[Xu et al., 2018]"},{"why":"SAGE is another degree-free backbone used in the experiments.","marker":"[Hamilton et al., 2017]"},{"why":"Supplies the deleted-edge consistency loss and the uniform affected-range baseline that AGU refines.","marker":"[Cheng et al., 2023]"},{"why":"GIF provides the influence-function baseline and the earlier uniform K+1-hop convention.","marker":"[Wu et al., 2023a]"},{"why":"IDEA is a layer-based affected-neighbor baseline and certified unlearning comparison.","marker":"[Dong et al., 2024]"},{"why":"MEGU contributes highly-affected-neighbor selection and the self-supervised preservation-loss pattern AGU adopts.","marker":"[Li et al., 2024b]"}],"fun_headline_variants":["AGU adapts unlearning to task and GNN architecture","Architecture-aware graph unlearning beats seven baselines","Node unlearning means forgetting connections too—AGU","Different GNNs need different forgetting ranges: AGU"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["AGU adapts unlearning to task and GNN architecture","Architecture-aware graph unlearning beats seven baselines","Node unlearning means forgetting connections too—AGU","Different GNNs need different forgetting ranges: AGU"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000239,"raw_usage":{"total_tokens":1515,"prompt_tokens":950,"completion_tokens":565,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":566,"completion_tokens_details":{"reasoning_tokens":499}},"tokens_in":566,"tokens_out":565,"duration_ms":5862,"temperature":1.0,"reasoning_tokens":499,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T20:30:31.730277+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"AGU Appendix","cited_arxiv_id":null,"evidence_quote":"Carries the empirical validation deferred from Section 4.3 that degree-free GNNs affect one hop fewer than degree-based GNNs, plus dataset statistics."},{"cited_title":"Graph attention networks","cited_arxiv_id":null,"evidence_quote":"GAT is the canonical degree-free backbone whose attention renormalization motivates the K/K−1 affected ranges."},{"cited_title":"Inductive representation learning on large graphs","cited_arxiv_id":null,"evidence_quote":"SAGE is another degree-free backbone used in the experiments."},{"cited_title":"GNNDelete: A general strategy for unlearning in graph neural networks","cited_arxiv_id":null,"evidence_quote":"Supplies the deleted-edge consistency loss and the uniform affected-range baseline that AGU refines."},{"cited_title":"Idea: A flexible framework of certified unlearning for graph neural networks","cited_arxiv_id":null,"evidence_quote":"IDEA is a layer-based affected-neighbor baseline and certified unlearning comparison."}],"review_version":1}