{"id":"f3440a26-6bd3-4e71-8951-317338faf743","arxiv_id":"2502.01031","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":6,"one_line_summary":"DiffIM makes influence minimization differentiable by using a graph neural network surrogate and a continuous relaxation of edge removal, yielding large speedups.","lead":"This paper introduces DiffIM, a machine-learning method that slows the spread of influence in social networks by learning to estimate spread with a graph neural network and then selecting edges to remove. It reports speedups of up to 15,160 times over existing methods while matching or improving their effectiveness.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"GPU-vs-CPU hardware imbalance confounds the speed comparison, so the Pareto-optimality and up-to-15,160× claims are not established on equal hardware.","rationale":"I considered the reader's emphasis on surrogate accuracy under edge removal, but the end-to-end effectiveness numbers are measured by Monte Carlo on the final graph, so that concern affects generalization rather than the reported results. The speed comparison, however, directly determines the central Pareto-optimality claim, and the Appendix F hardware split means the reported speedups are not attributable to the algorithm alone. This is a concrete, testable flaw in the evaluation design. It does not imply the method is ineffective; it means the evidence for the headline claim is weaker than stated. The reader's verdict of CONDITIONAL remains appropriate, so no verdict change is recommended.","tokens_in":26860,"tokens_out":6327,"duration_ms":65570,"concrete_test":"Run the full experiment suite on a single machine class: (a) all methods on CPU-only using the same implementation framework, or (b) give the strongest baselines (GREEDY, MBPM, RIS) GPU-accelerated implementations; then recompute the Pareto frontier. If DIFFIM is no longer Pareto-optimal or the speedup fails to reach an order of magnitude, the headline claim should be re-framed as hardware- and implementation-dependent.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Appendix F discloses that all DIFFIM versions ran on a machine with 2.10GHz Intel Xeon Silver 4210R CPUs and an RTX2080Ti GPU, while all baselines ran on a machine with more powerful 3.70GHz Intel Core i9-10900KF CPUs and did not use GPUs. The headline speedups (30×–15,160×) are wall-clock comparisons that conflate algorithmic acceleration with hardware acceleration. The central Pareto-optimality claim ('no baseline is faster and more effective') is an empirical statement about these specific runs, not about the methods on equal footing. A GPU-accelerated Monte Carlo baseline or a CPU-only run of DIFFIM could plausibly shift the Pareto frontier; the paper provides neither. Therefore the 'orders of magnitude faster' claim is not supported as a property of the method.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes DiffIM, a learning-based method for influence minimization (IMIN) via edge removal under the independent cascade (IC) model. It trains a GNN surrogate on Monte Carlo influence estimates and then selects edges to remove using three variants: DIFFIM (greedy selection with GNN-estimated influence), DIFFIM+ (continuous relaxation of edge-removal decisions optimized by gradient descent with a loss combining influence reduction, budget, and certainty terms), and DIFFIM++ (one-shot selection of edges with largest gradients). Experiments on real-world graphs WC, CL, ET, on LT and G-SIR models, and on large-scale graphs report that all versions are Pareto-optimal against ten baselines, with speedups up to 15,160x. The paper also includes an NP-hardness proof, complexity analysis, ablation studies, and inductive experiments.","tokens_in":27103,"tokens_out":10081,"duration_ms":98365,"significance":"If the empirical claims survive scrutiny, this is a valuable contribution: it is, to my knowledge, the first differentiable-learning treatment of IMIN, it offers a practical way to avoid expensive Monte Carlo simulation at test time, and the three schemes form a clean speed-effectiveness spectrum. The paper ships code and datasets, which aids reproducibility. The central limitation is that the headline speed and Pareto-optimality claims depend on an uneven hardware comparison and on unvalidated surrogate behavior on modified graphs; these need to be addressed before the claims can be accepted as stated.","major_comments":[{"comment":"The speed comparison is confounded by hardware: all DIFFIM variants ran on a machine with 2.10GHz Intel Xeon Silver 4210R processors and an RTX2080Ti GPU, while all baselines ran on a machine with a faster 3.70GHz Intel Core i9-10900KF CPU and no GPU. Since the claimed speedups and the Pareto-optimality statement are wall-clock comparisons, they do not establish that the method is faster as an algorithm; they only compare a GPU implementation against CPU implementations. Please provide either CPU-only runs of DIFFIM variants, GPU-accelerated MC baselines (e.g., GREEDY or MBPM batched on GPU), or a hardware-normalized analysis, and restate the Pareto claim based on that comparison.","section":"Appendix F; Fig. 1; abstract"},{"comment":"The surrogate is trained only on intact graphs with varied seed sets, but at test time DIFFIM, DIFFIM+, and DIFFIM++ evaluate the surrogate on graphs from which edges have already been removed, and DIFFIM+ also feeds rescaled edge probabilities into the GNN. Fig. 3 validates the surrogate only by correlating total influence estimates with MC on unmodified validation graphs. Please add validation in the operating regime: for example, compare GNN-estimated total influence and per-edge marginal reductions with MC on graphs with 1 to b randomly removed edges and on probability-rescaled graphs. This is needed to support the claim that the selection driven by GNN gradients or greedy scores is reliable.","section":"Sec. 5.2, Alg. 1, Fig. 3"},{"comment":"The displayed L_certainty is not the Shannon entropy and is not minimized at binary r̃. For r̃=0.5 the expression is 0, and for r̃=0.1 (natural log) it is approximately -0.135, so it can be negative and its minimizer on [0,1] is interior. This contradicts the text stating it is inspired by Shannon entropy and is smaller when each r̃(e) is closer to 0 or 1, and Lemma 2's discreteness conclusion does not follow from this formula. If the code implements the intended entropy, please correct the formula and the missing parenthesis in 'logr(e)'; if not, the DIFFIM+ loss and the ablation in Table 6 need to be re-evaluated. Given Table 6 shows L_certainty has only a small effect, the corrected loss is unlikely to change the main empirical conclusions, but the inconsistency must be fixed.","section":"Sec. 5.3, Eq. (1), Lemma 2"},{"comment":"The budget handling in DIFFIM+ is not fully specified. EdgeSelection+ optimizes L_budget = (|E| - Σ_e r̃(e) - b)^2, but after each removal the graph shrinks while Algorithm 1 line 7 keeps b fixed; the initialization r̃(e)=1-b/|E| makes L_budget zero only on the initial graph. Please clarify whether r̃ is reinitialized in each round, whether b is decremented to reflect the remaining budget, and how the budget term behaves after the first removal. This is necessary for reproducibility of DIFFIM+.","section":"Sec. 5.3, Alg. 1, Sec. 6.1"}],"minor_comments":[{"comment":"The caption says the running time of the best baseline is compared with 'one of our methods with the most similar reduced ratio'; this wording is ambiguous. Please specify exactly which baseline and which DIFFIM version are used for each reported speed-up, and give the underlying numbers in the appendix or table.","section":"Fig. 1 caption"},{"comment":"There are formatting typos in the WC column: '0.1641 (2315)' and '0.3545 (2243)' should presumably read '0.1641 (0.2315)' and '0.3545 (0.2243)'.","section":"Table 7"},{"comment":"The text says the together variant of DIFFIM++ has lower effectiveness than 'the original DIFFIM+'; this should presumably say 'the original DIFFIM++'.","section":"Appendix G.3, Fig. 7 caption"},{"comment":"The reduction would be easier to verify if the budget were stated explicitly as b = m - k and the seed set as S = {v_init}; currently the construction is described only in prose.","section":"Appendix A.1, proof of Theorem 1"}],"recommendation":"major_revision","confidential_remarks":"The hardware imbalance is the most serious issue: the headline 'Pareto-optimal' and '15,160x' claims are not supported on equal hardware. I would ask for a revised comparison before publication. The surrogate-validation gap and the L_certainty formula inconsistency are also load-bearing and should be addressed in the revision; the rest of the issues are local and fixable."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"DiffIM is a genuinely new way to attack influence minimization—treating edge removal as a differentiable learning problem rather than discrete search—but the headline speed and Pareto-optimality claims are not established as stated because the comparison runs on different hardware.\n\nWhat's new: the three-scheme pipeline (GNN surrogate, continuous relaxation, gradient-driven selection) is, as far as I can tell, the first differentiable formulation of IMIN. The GNN surrogate is adapted from MONSTOR, but the combination is novel. The experiments are thorough: three real datasets, three diffusion models, budgets 3–10, plus large-scale graphs, and the code is public. Lemma 2 gives a reasonable guarantee for the relaxed loss when the surrogate is accurate and the loss weights are large.\n\nSoft spots, in order of importance. First, Appendix F discloses that all DiffIM versions ran on a Xeon Silver with an RTX2080Ti, while every baseline ran on a faster i9-10900KF CPU with no GPU. That means the 30×–15,160× speedups are wall-clock comparisons that bundle together algorithmic gains and hardware gains. The Pareto-optimality claim—'no baseline is faster and more effective'—is therefore not supported as a property of the method; it's a property of these particular runs. A GPU-accelerated MC baseline, or a CPU-only DiffIM, could plausibly change the frontier.\n\nSecond, the surrogate is trained only on the intact graph and validated on unmodified validation graphs (Fig. 3, r≥0.999). But DIFFIM+ and DIFFIM++ operate on graphs that have already been modified—edges removed, probabilities rescaled. The paper never checks whether the surrogate's per-node estimates or gradient rankings remain reliable in that regime. That's exactly the regime where the method lives.\n\nThird, a small but real typo: L_certainty in Eq. (1) is written with 'log r(e)' where it should presumably be 'log r̃(e)'. The intended entropy-like loss is clear, but the printed expression is garbled.\n\nFourth, the gradient-driven selection (DIFFIM++) is a heuristic—the paper doesn't demonstrate that gradient magnitude actually tracks marginal reduction in influence. Its good empirical performance is encouraging, but the reason it works is not fully pinned down.\n\nNone of this is fatal. The effectiveness numbers are strong and consistent across datasets and budgets, and the differentiable formulation is worth serious attention. The paper just overreaches in its headline speed claim, and the surrogate-under-removal question deserves a direct experiment before the method is fully trusted.\n\nWho should read it: anyone working on influence minimization, graph neural network surrogates, or learned combinatorial optimization. It deserves a serious referee; a good reviewer should push for equal-hardware baselines and an edge-removal validation study.","headline":"A genuinely novel differentiable IMIN pipeline, but the speed and Pareto-optimality claims rest on an unequal hardware comparison and an unvalidated surrogate under edge removal.","tokens_in":27536,"tokens_out":3467,"would_cite":false,"duration_ms":33357,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68T07","68R10","68Q25"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper claims that influence minimization—choosing which edges to delete so that a seed set's expected spread drops the most—can be solved far faster with differentiable learning than with discrete combinatorial search, and…","keywords":["influence minimization","independent cascade model","graph neural network surrogate","continuous relaxation","gradient-driven edge selection","rumor blocking","differentiable optimization"],"falsifier":"A reader could test the key assumption by taking a held-out graph, computing the surrogate's per-edge gradient ranking, and comparing it against the true marginal influence reduction from Monte Carlo after each edge removal in sequence; if the ranking correlation degrades sharply after the first few deletions, the gradient-driven and relaxed-optimization variants lose their grounding.","tokens_in":26691,"feed_emoji":"⚡","tokens_out":5486,"duration_ms":50060,"temperature":0.7,"pith_summary":"This paper claims that influence minimization—choosing a small set of edges to delete so that a seed set's expected spread drops the most—can be solved far faster with differentiable learning than with discrete combinatorial search. It proposes DiffIM, which trains a graph neural network to act as a surrogate for Monte Carlo influence estimation, relaxes edge-deletion decisions from binary to continuous, and then uses gradients to pick which edges to remove. On three real-world graphs and several diffusion models, the method is reported to be Pareto-optimal against existing baselines and orders of magnitude faster (up to 15,160×) while matching or improving effectiveness. If the claim holds, time-critical applications like rumor or epidemic blocking gain a practical tool where delays previously made exact or greedy approaches infeasible.","feed_headline":"Gradients choose edges to block influence up to 15,000x faster","feed_subtitle":"DiffIM replaces slow Monte Carlo simulations with a trained graph network and gradient-based edge removal decisions.","key_machinery":"The load-bearing object is the trained GNN surrogate $\\mathrm{GNN}_\\theta(v; G, p, S)$, which maps a graph with edge weights $p$ and a one-hot seed indicator to an estimate of each node's influenced probability. Because edge-removal decisions enter through modified weights $\\tilde p_{\\tilde r}(u,v) = p(u,v)\\,\\tilde r(u,v)$, the network's output is differentiable with respect to the keep-probabilities $\\tilde r$, which is what makes continuous relaxation and gradient-based selection possible. The loss $\\mathcal{L}_O = \\mathcal{L}_{\\mathrm{obj}} + \\alpha \\mathcal{L}_{\\mathrm{budget}} + \\beta \\mathcal{L}_{\\mathrm{certainty}}$ ties the relaxed decisions to the original objective under a budget while pushing them toward binary values.","core_discovery":"The central discovery is that the NP-hard, non-submodular edge-removal problem under the independent cascade model can be approached as a differentiable optimization, contrary to the field's discrete-combinatorial default. DiffIM trains a GNN to predict per-node influenced probabilities given a graph, activation probabilities, and a seed set; replaces each binary keep/remove decision with a continuous keep-probability; and defines a loss whose objective is the estimated influence-reduction ratio, whose budget term enforces exactly b removals, and whose certainty term pushes decisions toward 0/1. A third variant, DiffIM++, skips iterative optimization entirely and removes the edge whose gradient is largest. The authors show empirically that all three schemes accelerate the greedy selection loop, with the full pipeline remaining effective when trained and tested on different graphs.","pith_inferences":["A natural, untested extension is to use the same surrogate plus continuous relaxation for influence maximization (choosing seed sets), which the authors list as future work but do not evaluate.","The approach implicitly assumes that the gradient ranking on the original graph approximates the true marginal benefit of edge deletion on the progressively sparser graph; if that assumption fails on networks with highly heterogeneous local structure, the speed advantage would come at a larger effectiveness cost.","A quantitative test of gradient quality—comparing surrogate-predicted edge sensitivities with Monte-Carlo marginal reductions after sequential removals—would sharpen the paper's validation and could also serve as a training-time diagnostic."],"forward_implications":["If the results hold, influence minimization becomes practical for time-critical settings: the reported speed-ups place decision times well within minutes on graphs where Monte-Carlo-based greedy methods take hours or time out.","The surrogate's once-per-graph training cost is amortized over many seed sets and even across different graphs, since the method retains most of its effectiveness when trained and tested on separate networks.","The same differentiable pipeline transfers to other diffusion models such as linear threshold and G-SIR, so the approach is not tied to independent cascade.","Gradient-driven selection (DIFFIM++) offers near-instant edge recommendations, which could be used for adaptive blocking as an outbreak evolves."],"supporting_citations":[{"why":"Establishes that GNNs can learn to estimate influence under the IC model, the foundation for the surrogate-modeling scheme.","marker":"Ko et al. (2020)"},{"why":"Defines the independent cascade model and the Monte Carlo evaluation protocol used for ground-truth influence.","marker":"Kempe, Kleinberg, and Tardos (2003)"},{"why":"Formulates the same edge-removal IMIN problem and proves its non-submodularity; supplies the MDS heuristic that DiffIM is compared against.","marker":"Yan et al. (2019)"},{"why":"Introduces the bond-percolation estimation method and the BPM baseline for link blocking.","marker":"Kimura, Saito, and Motoda (2009)"},{"why":"Provides reverse-influence-sampling edge-deletion algorithms for epidemic models, giving the RIS baseline and the G-SIR extension.","marker":"Yi et al. (2022)"},{"why":"Supplies the GCN architecture used as the surrogate influence estimator.","marker":"Kipf and Welling (2017)"}],"fun_headline_variants":["DiffIM: Differentiable edge removal, 15,160x faster influence blocking","Surrogate GNN + gradients: 15,160x faster rumor blocking","Pareto-optimal IMIN: Gradient-chosen edges, up to 15,160x speedup","Monte Carlo-free: DiffIM blocks influence 15,160x faster","Continuous relaxation speeds influence minimization 15,160x"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The entire pipeline rests on the surrogate GNN, trained only on intact graphs, giving trustworthy influence estimates—and more importantly trustworthy gradient rankings—on graphs whose edges have already been deleted or whose probabilities have been rescaled.","fun_headline_variants_meta":{"raw":{"variants":["DiffIM: Differentiable edge removal, 15,160x faster influence blocking","Surrogate GNN + gradients: 15,160x faster rumor blocking","Pareto-optimal IMIN: Gradient-chosen edges, up to 15,160x speedup","Monte Carlo-free: DiffIM blocks influence 15,160x faster","Continuous relaxation speeds influence minimization 15,160x"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000241,"raw_usage":{"total_tokens":1531,"prompt_tokens":963,"completion_tokens":568,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":579,"completion_tokens_details":{"reasoning_tokens":464}},"tokens_in":579,"tokens_out":568,"duration_ms":5638,"temperature":1.0,"reasoning_tokens":464,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-09T16:49:59.930261+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"A reader could test the key assumption by taking a held-out graph, computing the surrogate's per-edge gradient ranking, and comparing it against the true marginal influence reduction from Monte Carlo after each edge removal in sequence; if the ranking correlation degrades sharply after the first few deletions, the gradient-driven and relaxed-optimization variants lose their grounding.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines the independent cascade model and the Monte Carlo evaluation protocol used for ground-truth influence."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Introduces the bond-percolation estimation method and the BPM baseline for link blocking."},{"cited_title":"N.; and Welling, M","cited_arxiv_id":null,"evidence_quote":"Supplies the GCN architecture used as the surrogate influence estimator."}],"review_version":1}