{"id":"72d67b61-2502-4917-a828-44f124fb7b77","arxiv_id":"2501.11823","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":4,"one_line_summary":"The paper's NIM+SGU pipeline improves forgetting and preserves accuracy in graph unlearning by selecting high-influence nodes via propagation-based influence scores and fine-tuning on entity-specific losses.","lead":"A graph-unlearning method selects which unaffected nodes to retrain by borrowing language from viral-marketing 'influence' models, then fine-tunes the model so that deleted nodes are forgotten without hurting predictions. The paper reports gains over existing methods on graphs up to 111 million nodes.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The central premise—that Eqs. (5)-(6) capture UE-to-node training influence—is asserted without derivation. If false, NIM's HIE set is a heuristic, and the claimed forgetting gains are not attributable to influence-targeted removal.","rationale":"The reader's weakest assumption is exactly the premise I would stress-test: the assertion that Jacobians of propagated features and predictions (Eqs. (5)-(6)) faithfully represent the gradient-driven entanglement produced during GNN training. The paper gives intuition but no derivation, and the quantities used omit the loss, labels, and Hessian that govern true training influence. Because NIM is the plug-and-play contribution and the HIE set directly determines which nodes receive the forgetting losses, this is the single most load-bearing point in the paper. The evidence in the paper is substantial: 14 datasets, multiple backbones, large-scale results on ogbn-papers100M, and consistent MIA improvements. Those results are compatible with the possibility that NIM is a useful heuristic even if its influence interpretation is not exact. They do not, however, establish the stronger causal claim that the forgetting gains come from identifying the nodes actually influenced by UE. The concrete experiment I propose would settle this by comparing NIM's ranking against ground-truth retraining-based influence on a small SGC setting, where exact influence is computable. I therefore keep the reader's CONDITIONAL verdict: the empirical case is strong enough to warrant conditional acceptance, but the central mechanism should be validated before the influence-selection claim is taken as established. No code release further limits verification, but that is secondary to the conceptual gap.","tokens_in":27344,"tokens_out":4444,"duration_ms":53285,"concrete_test":"On a small transductive dataset with SGC backbone, generate N random UE sets. For each set, (i) retrain from scratch without the UE to obtain the ground-truth removal model; (ii) compute per-node true influence as the L2 change in held-out predictions or last-layer embeddings between the original and retrained models; (iii) compute NIM's score ~I(v, UE, k) from the original model using Eqs. (5)-(7). Then compute rank correlation and top-k overlap/NDCG between true influence and NIM's ordering at k = B = 3|UE|, compared against L-hop neighborhood and random selection. If NIM is not significantly better, the Sec. 3.1.1 premise is unsupported. As a complementary check, run SGU with NIM-selected HIE replaced by same-size random HIE at fixed lambda; if MIA AUC and F1 are statistically indistinguishable, the claimed forgetting improvement is not attributable to reliable HIE selection.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The load-bearing premise is that the influence of an unlearning entity u on another node v during training is faithfully quantified by the L1 norms in Eqs. (5)-(6), i.e., by Jacobians of propagated features and predictions of the already-trained model. The paper asserts this in Sec. 3.1.1 without derivation. For a decoupled linear GNN, the actual sensitivity of the trained weights to deleting u is mediated by the training loss at u and by the Hessian of the empirical risk; it cannot be read off from dX_v/dX_u and dY_v/dY_u alone. Those quantities are essentially random-walk reachability plus a classifier Jacobian; they do not involve the labels of u, the loss gradient, or the optimization trajectory. If the measure is only a heuristic proxy, then the selected HIE are not necessarily the nodes whose trained knowledge came from the UE, so the fine-tuning losses in Eqs. (9)-(12) target the wrong entities, and the reported forgetting and reasoning gains could come from extra entity-specific fine-tuning rather than from targeted knowledge removal. This is particularly consequential because the paper's SOTA claim depends on NIM selecting reliable HIE. The implementation also muddies the criterion: Algorithm 1 lines 11-17 select B nodes by argmax over the influence score, whereas Definition 3 (Eq. 8) activates nodes by a threshold theta; these two selection rules are not equivalent, making it unclear which criterion the experiments actually use. Even if the influence measure fails, SGU's fine-tuning may retain value; the NIM-specific claim would not be supported.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a graph-unlearning framework built on a new high-influence entity (HIE) selection module called Node Influence Maximization (NIM). NIM treats unlearning entities as seeds in an influence-propagation model and scores each non-UE node by the L1 norm of Jacobians of propagated features and predictions (Eqs. (5)-(6)). SGU then fine-tunes the trained GNN with entity-specific losses: random-label cross-entropy, prototype perturbation, contrastive learning, and a memory-based KL term (Eqs. (9)-(12)). The authors claim that NIM is plug-and-play and improves the forgetting capability of existing graph-unlearning methods, and that SGU achieves state-of-the-art forgetting/reasoning while scaling to ogbn-papers100M. The experiments cover 14 datasets, multiple backbones, and transductive, inductive, and link-level settings.","tokens_in":27580,"tokens_out":10279,"duration_ms":98410,"significance":"If the central premise of NIM were established, the paper would make a useful conceptual and practical contribution: it draws a concrete connection between graph unlearning and influence maximization, and the plug-and-play HIE selector is simple enough to retrofit into existing GU pipelines. The experimental breadth is a genuine strength: 14 datasets, transductive/inductive/link settings, and several decoupled and sampling backbones. The paper also reports consistent gains of NIM across multiple HIE-based GU methods (Table 1), which is the most direct evidence for the plug-and-play claim. The main caveat is that the influence measure itself is asserted rather than derived, and the forgetting losses directly target the MIA signal, so the current experiments do not fully separate the effect of NIM from the effect of the fine-tuning objective. With a derivation or validation study and more careful reporting, the contribution would be solid.","major_comments":[{"comment":"The influence measures in Eqs. (5)-(6) are asserted rather than derived. For a decoupled linear GNN of the form in Eq. (2), the effect of removing UE u on the trained weights is mediated by the loss term at u and by the curvature of the training objective; it is not determined by the L1 norm of dX_v/dX_u or dY_v/dY_u alone, because those Jacobians are evaluated at the already-trained model and do not involve the labels of u, the loss gradient at u, or the optimization trajectory. Since NIM's selected HIE are the input to all SGU losses (Eqs. (9)-(12)), this is a load-bearing assumption. Please either provide a derivation linking Eqs. (5)-(6) to leave-one-out influence for a linear GNN, or add a validation experiment on small graphs (e.g., compare NIM-selected HIE against actual retraining-based influence). Without this, the claim that NIM identifies nodes that carry UE knowledge is not established.","section":"Sec. 3.1.1, Eqs. (5)-(6)"},{"comment":"Definition 3 (Eq. (8)) defines HIE as the set of nodes whose maximum influence from the UE seed set exceeds threshold theta. Algorithm 1, however, repeatedly selects the single node with the largest influence score until B nodes are collected (lines 11-17) and never uses theta. Thresholding and top-B selection are not equivalent rules, and App. A.7 reports searching theta in [0.5,1] while the algorithm uses B=3|DeltaV|. The reader cannot tell which criterion produced Tables 1-5 and Fig. 5. Please reconcile the formal definition with the implementation, and specify how theta and B interact (e.g., threshold then cap, or top-B with theta used only for sensitivity analysis).","section":"Sec. 3.1.2 (Def. 3) and Algorithm 1"},{"comment":"The forgetting losses directly remove the signals measured by the MIA: L1_f randomly shuffles UE labels, L2_f pushes UE embeddings away from class prototypes, and L3_f uses UE as negative samples. Low MIA AUC is therefore partially a consequence of the loss design, not necessarily of NIM's HIE selection. The paper should add a control experiment in which the SGU fine-tuning losses are held fixed and only the HIE source is changed (NIM vs L-hop neighborhood vs random nodes), and should report an additional membership-evaluation metric or a held-out UE set. This would separate the contribution of NIM from the contribution of the objective itself.","section":"Sec. 3.2.1, Tables 1 and 5"},{"comment":"MIA results in Tables 1, 5, and 9 are reported without standard deviations, even though App. A.7 states that each experiment is repeated 10 times. The differences are small (e.g., Table 1 improvements of 4-5% on AUC values around 0.53-0.61), so without variance or significance testing the improvements may be within noise. In addition, App. A.7 says hyperparameters (B, theta, lambda, k) are searched per dataset/backbone to report the best performance; this selection protocol should be applied identically to baselines, and the chosen values should be reported in the main text or appendix. Please add error bars or per-seed values and a fixed validation-based hyperparameter protocol.","section":"Tables 1, 5 and App. A.7"},{"comment":"Table 3 contains many OOM, OOT, or missing entries for baselines on arxiv, products, papers100M, Flickr, and Reddit. As a result, the comprehensive SOTA and scalability claim on large graphs rests on a small number of completed comparisons (notably SGU vs ScaleGUN, GNNDelete, and MEGU on papers100M). Please report runtime and peak memory for all completed cells, state the resource limits that caused OOM/OOT, and clarify whether the missing entries mean the baselines could not run at all under the reported environment.","section":"Table 3"}],"minor_comments":[{"comment":"The product notation in the random-walk expression lacks explicit limits and appears inconsistent with the definition of P_{v->u}^k; please rewrite with i=1..k.","section":"Eq. (7)"},{"comment":"The phrase 'expected Jacobin matrix' should be 'Jacobian', and the expectation and the exact L1 matrix norm should be specified.","section":"Definitions 1 and 2"},{"comment":"The notation overloads X_tilde for both the aggregated propagated features and per-layer quantities, and Y_tilde^{(k)} in Eq. (6) is never defined; please align the notation.","section":"Eq. (4)"},{"comment":"Line 3 names S the 'seed set (HIE)', although HIE is the activated set; line 16 also uses u without a definition. Please rename and clarify.","section":"Algorithm 1"},{"comment":"The table uses '!' and '%' symbols without a legend; please define them in the caption.","section":"Table 6"},{"comment":"The table lists 'GCU [9]', but reference [9] is CGU; please correct the citation.","section":"App. A.6 / Table 6"},{"comment":"No code or data link is provided; please include a reproducibility artifact.","section":"Reproducibility"}],"recommendation":"major_revision","confidential_remarks":"Editors: The manuscript is within scope for a graph-mining/machine-learning venue, and the empirical contribution is substantial. My main concerns are verification of the influence measure and consistency between the formal definition and the implementation; these are fixable. I would not recommend rejection, but the missing error bars and per-dataset tuning should be addressed before publication."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nHere's my read of the SGU/NIM paper. It deserves a serious referee, but it needs revision before acceptance. The core idea—selecting high-influence entities by a propagation-based score instead of the L-hop neighborhood—is a useful plug-and-play contribution, and the 14-dataset evaluation is substantial.\n\nWhat is actually new: NIM combines topology influence (gradient of propagated features) with feature influence (gradient of predictions) into a single HIE criterion. That combination is not in the cited literature, and the paper shows it improves forgetting across several existing GU baselines. The SGU fine-tuning losses (label randomization, prototype separation, contrastive learning) are also well-designed for entity-specific updates. Running on ogbn-papers100M is a real strength; many baselines OOM or OOT.\n\nNow the soft spots. The load-bearing premise is that Eqs. (5)-(6) quantify UE-to-node training influence. The paper asserts this in Sec. 3.1.1 without derivation. Reading the equations, they are essentially random-walk reachability plus a classifier Jacobian; they do not involve the labels of the unlearning entity, the loss gradient, or the optimization trajectory. As a heuristic proxy, fine; as a faithful measure of training influence, it is unsupported. The stress-test is right on this. The paper should either derive it under a decoupled linear GNN or explicitly call it a heuristic and justify it empirically.\n\nSecond, there is a genuine inconsistency: Definition 3 selects HIE by threshold theta (Eq. 8), while Algorithm 1 selects B nodes by argmax. The experiments tune both B and theta (Fig. 5), so the reader cannot tell which criterion drives the results. That is a fixable but important clarity issue.\n\nThird, MIA numbers in Tables 1 and 5 come without error bars, and hyperparameters are tuned per dataset to report the best performance (App. A.7). That is a selection-bias risk. The large-scale comparisons have many OOM/OOT gaps, so \"comprehensive SOTA\" is stronger than what the data show.\n\nOne more thing: some forgetting is by construction—the losses directly randomize UE labels and separate UE embeddings, so MIA gains over baselines are partly baked in. That is standard in this literature, but \"complete knowledge removal\" should be tempered; MIA AUC remains above 0.5.\n\nWho is this for: the graph unlearning community and anyone building scalable unlearning pipelines. It is a solid empirical paper with a valuable plug-and-play component. I would accept it for peer review, with a strong expectation of major revision. A serious referee should push on the influence measure's justification, the algorithm/definition mismatch, and error bars.","headline":"A useful plug-and-play HIE selector for graph unlearning with a heuristic core; solid experiments, but the influence measure is asserted and the algorithm/definition mismatch needs fixing.","tokens_in":28199,"tokens_out":3545,"would_cite":true,"duration_ms":35619,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"Graph unlearning works better when the nodes to scrub are chosen by influence scores from the trained model's own propagation, rather than by local neighborhood.","keywords":["graph unlearning","node influence maximization","high-influence entity selection","decoupled graph neural networks","influence function","entity-specific fine-tuning","forgetting and reasoning trade-off","scalable graph learning"],"falsifier":"Train a GNN on a graph, pick an unlearning set, and fully retrain from scratch without those entities; define ground-truth high-influence entities as the nodes whose predictions change most between the original and retrained models. If NIM's selected set overlaps with this ground truth no better than the $L$-hop neighborhood does, the measure fails its core purpose; the paper currently reports membership-inference improvements, not this direct overlap check against retraining.","tokens_in":2003,"feed_emoji":"🕸️","tokens_out":3209,"duration_ms":74706,"temperature":0.7,"pith_summary":"The paper claims that the nodes a graph-unlearning request must scrub are rarely just the deleted entity's local neighborhood; gradient-driven training entangles many other nodes, often same-class nodes far away. It proposes Node Influence Maximization (NIM), a plug-and-play method that measures how strongly each remaining node was influenced by the unlearning entities during training, treating those entities as seeds in an influence-propagation model. NIM's influence scores come from the already-trained model's propagated features and predictions, so it runs offline before unlearning and can be attached to most existing graph unlearning methods. On top of that, the paper introduces Scalable Graph Unlearning (SGU), which fine-tunes the model only on the deleted entities and the selected high-influence entities with custom forgetting and reasoning losses. On 14 datasets, including the 111-million-node ogbn-papers100M, the claimed result is that NIM improves forgetting for most baseline methods while SGU matches or beats state-of-the-art unlearning quality at scale.","feed_headline":"Influence scores pick which nodes to scrub in graph unlearning","feed_subtitle":"Plug into most unlearning methods to forget more, and fine-tune only the entities that matter—tested to 111M nodes.","key_machinery":"The carrier is a decoupled influence propagation model (Eq. 4) that treats the GNN's weight-free propagation operator $P$ (SGC-style $k$-step propagation, GBP weighting, GAMLP attention, and similar formulas) as a social-influence diffusion process, with the unlearning entities as the seed set $S$. Topology influence $I_t$ is the $\\ell^1$-norm of the expected Jacobian of propagated features, $\\partial \\tilde{X}^{(k)}_v / \\partial \\tilde{X}^{(0)}_u$; feature influence $I_f$ is the $\\ell^1$-norm of the expected Jacobian of predictions, $\\partial \\tilde{Y}^{(k)}_v / \\partial \\tilde{Y}^{(0)}_u$. The two are normalized into a random-walk interpretation (Eq. 7) and summed, and nodes whose maximum influence from $S$ exceeds a threshold $\\theta$ are activated as high-influence entities (Eq. 8), with budget $B$ controlling how many are selected. The second mechanism is entity-specific fine-tuning: label-shuffled cross-entropy on unlearning entities, prototype-based embedding forgetting on unlearning entities, contrastive loss on high-influence entities against same-label positives and unlearning-entity negatives, plus an L2/KL memory-based reasoning loss; the scalar $\\lambda$ balances forgetting against reasoning.","core_discovery":"The paper's central discovery is that high-influence entity selection is the bottleneck in learning-based graph unlearning: existing methods take the $L$-hop neighborhood of the unlearning entity, which misses same-label nodes reached by similar gradients and includes nearby nodes that carry little signal. The paper claims that a node's influence can be quantified directly from the decoupled propagation operator of the trained GNN: the $\\ell^1$-norm of the Jacobian of propagated features (topology influence) plus the $\\ell^1$-norm of the Jacobian of model predictions (feature influence). Summing these gives a fine-grained influence score, and nodes whose maximum influence from the unlearning set exceeds a threshold $\\theta$ form the high-influence entities. Replacing neighborhood selection with this influence measure lowers membership-inference AUC toward 0.5 for five high-influence-based graph unlearning baselines, and the fine-tuning framework built on it reaches state-of-the-art prediction on non-unlearning entities while remaining efficient on billion-scale graphs.","pith_inferences":["(Editorial inference) If the Jacobian-based influence scores are good proxies for training entanglement, the same scores could serve as a data-attribution tool beyond unlearning, ranking which training nodes most shaped a given prediction.","(Editorial inference) The paper's motivating claims that same-label nodes are more influenced and different-label nodes less so (Sec. 1) are directly testable by inspecting NIM's selected sets; on highly heterophilic graphs, where same-label nodes are structurally distant, NIM's advantage over $L$-hop selection should shrink.","(Editorial inference) Because NIM is computed from the trained model's propagated features and predictions, it inherits the backbone's quality; for sampling-based GNN backbones the added weight-free propagation is an approximation, so the benefit may degrade when that propagation diverges from the actual training distribution.","(Editorial inference) The framework suggests a practical recipe for deletion requests in web-scale graphs: separate the expensive influence computation as a one-time pre-processing step, then let each new deletion request reuse it for fast entity-specific fine-tuning."],"forward_implications":["Any high-influence-based graph unlearning method (the paper lists CGU, GIF, D2DGN, GNNDelete, and MEGU) can drop in NIM as a pre-processing step and lower membership-inference leakage, with reported improvements up to about 5.7 percentage points.","Unlearning can scale to graphs with over 100 million nodes because NIM runs offline on precomputed propagated features, and fine-tuning touches only the unlearning entities plus the selected high-influence entities.","The trade-off between forgetting and reasoning is controllable through the budget $B$, threshold $\\theta$, and loss weight $\\lambda$, so practitioners can steer toward complete removal or preserved prediction.","Same-class influence that extends beyond the $L$-hop neighborhood is explicitly addressed by the influence measure, which is the paper's explanation for why neighborhood-based high-influence selection underperforms.","SGU preserves the reasoning capability of the unlearned model through memory-based supervision, so frequent deletion requests need not degrade predictions on remaining nodes."],"supporting_citations":[{"why":"Defines the social influence maximization seed-set and activated-node model that NIM adapts to graph unlearning.","marker":"[24]"},{"why":"Provides the decoupled propagation paradigm (SGC) used to precompute propagated features for NIM.","marker":"[52]"},{"why":"GNNDelete is a learning-based graph unlearning baseline whose high-influence selection NIM improves and which SGU is compared against.","marker":"[7]"},{"why":"GIF is an influence-function-based graph unlearning baseline that relies on high-influence entities and is improved by NIM.","marker":"[53]"},{"why":"MEGU is a learning-based graph unlearning baseline that NIM improves and that serves as a state-of-the-art comparison for SGU.","marker":"[29]"},{"why":"Grain connects influence maximization with graph learning, providing prior evidence that activated-node selection can improve training efficiency.","marker":"[68]"},{"why":"Supports the claim that GNNs derive most of their benefit from weight-free graph propagation rather than the learnable module, motivating the decoupled influence model.","marker":"[65]"},{"why":"ScaleGUN is the scalable certified graph unlearning baseline that SGU is contrasted against for scalability and inference protection.","marker":"[59]"}],"fun_headline_variants":["Influence-based selection boosts graph unlearning at scale","Node influence scores pick high-impact entities for graph unlearning","Scalable graph unlearning via node influence maximization","Fine-grained influence trims graph unlearning to 111M nodes","Unlearn better by picking high-influence nodes, not neighborhoods"],"cache_read_input_tokens":30208,"weakest_assumption_plain":"The load-bearing premise is that the already-trained model's propagation and predictions can be read like an influence map, specifically that the sensitivity of each node's propagated features and predictions to those of the deleted entity reveals which nodes were actually entangled with that entity during gradient-driven training.","fun_headline_variants_meta":{"raw":{"variants":["Influence-based selection boosts graph unlearning at scale","Node influence scores pick high-impact entities for graph unlearning","Scalable graph unlearning via node influence maximization","Fine-grained influence trims graph unlearning to 111M nodes","Unlearn better by picking high-influence nodes, not neighborhoods"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000604,"raw_usage":{"total_tokens":2855,"prompt_tokens":1020,"completion_tokens":1835,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":636,"completion_tokens_details":{"reasoning_tokens":1753}},"tokens_in":636,"tokens_out":1835,"duration_ms":12609,"temperature":1.0,"reasoning_tokens":1753,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T17:49:30.784745+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Train a GNN on a graph, pick an unlearning set, and fully retrain from scratch without those entities; define ground-truth high-influence entities as the nodes whose predictions change most between the original and retrained models. If NIM's selected set overlaps with this ground truth no better than the $L$-hop neighborhood does, the measure fails its core purpose; the paper currently reports membership-inference improvements, not this direct overlap check against retraining.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines the social influence maximization seed-set and activated-node model that NIM adapts to graph unlearning."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the decoupled propagation paradigm (SGC) used to precompute propagated features for NIM."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"GIF is an influence-function-based graph unlearning baseline that relies on high-influence entities and is improved by NIM."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"MEGU is a learning-based graph unlearning baseline that NIM improves and that serves as a state-of-the-art comparison for SGU."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Grain connects influence maximization with graph learning, providing prior evidence that activated-node selection can improve training efficiency."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supports the claim that GNNs derive most of their benefit from weight-free graph propagation rather than the learnable module, motivating the decoupled influence model."}],"review_version":1}