Research map / Graph learning / Graph algorithms and clustering
DiffIM: Differentiable Influence Minimization with Surrogate Modeling and Continuous Relaxation
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes DiffIM, a differentiable influence minimization method that uses a GNN surrogate for IC influence, continuous relaxation of edge removal, and gradient-driven edge selection to remove edges far faster than discrete baselines.
Problem
Influence minimization under the independent cascade model: choose b edges to remove to reduce expected influence of seed nodes, which is NP-hard, #P-hard to evaluate, and discrete, hindering gradient-based methods.
Approach
Train a GCN surrogate to predict per-node influenced probabilities, relax edge-removal decisions into keep-probabilities optimized by gradient descent, and add a gradient-driven selection rule that removes the edge with largest gradient without test-time optimization.
Key results
- DiffIM variants are Pareto-optimal and up to 15,160x faster than the most effective baseline while being more effective.
- Trained GNN surrogates reach Pearson's r of 0.999 or higher against Monte Carlo ground truth on validation seed sets.
- Inductive (cross-dataset) effectiveness drops by at most 5.4% relative to transductive for b=5.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use DiffIM instead of the strongest baseline | Influence minimization · WannaCry (WC), transductive, b=5 | reduced ratio of influence: 0.3160 -> 0.4311 | Helped |
| use DiffIM instead of the strongest baseline | Influence minimization · Celebrity (CL), transductive, b=5 | reduced ratio of influence: 0.5591 -> 0.6547 | Helped |
| use DiffIM instead of the strongest baseline | Influence minimization · Extended (ET), transductive, b=5 | reduced ratio of influence: 0.5284 -> 0.5613 | Helped |
| add the budget loss (ablation) | DiffIM+ · WannaCry (WC), b=5 | reduced ratio of influence: 0.0052 -> 0.3914 | Helped |
| add the budget loss (ablation) | DiffIM+ · Celebrity (CL), b=5 | reduced ratio of influence: 0.0112 -> 0.6614 | Helped |
| add the budget loss (ablation) | DiffIM+ · Extended (ET), b=5 | reduced ratio of influence: 0.0170 -> 0.5332 | Helped |
| add the certainty loss (ablation) | DiffIM+ · WannaCry (WC), b=5 | reduced ratio of influence: 0.3891 -> 0.3914 | Helped |
| add the certainty loss (ablation) | DiffIM+ · Celebrity (CL), b=5 | reduced ratio of influence: 0.6479 -> 0.6614 | Helped |
| add the certainty loss (ablation) | DiffIM+ · Extended (ET), b=5 | reduced ratio of influence: 0.5282 -> 0.5332 | Helped |
| select the bottom-b edges together rather than one by one (ablation) | DiffIM+ · WannaCry, Celebrity, and Extended; budgets b in [10] | reduced ratio of influence | No clear effect |
| select the top-b edges together rather than one by one (ablation) | DiffIM++ · WannaCry and Extended; budgets b in [10] | reduced ratio of influence | Hurt |
| select the top-b edges together rather than one by one (ablation) | DiffIM++ · Celebrity; budgets b in [10] | reduced ratio of influence | No clear effect |
Surprising findings
- Choosing edges all at once in DiffIM++ gives noticeably lower effectiveness than selecting them one by one, except on CL.
Limitations
- Surrogate GNN training takes hours (about 6,800 to 17,200 seconds per dataset) and relies on MC-generated labels.
- Effectiveness drops slightly when moving from transductive to inductive settings and the speed-accuracy trade-off varies across schemes.
- Evaluated only with edge removal; the paper notes extension to influence maximization is future work.
Experimental setup
Datasets: WannaCry Celebrity Extended cit-HepTh email-EuAll twitter
Benchmarks: WannaCry Celebrity Extended cit-HepTh email-EuAll twitter
Metrics: reduced ratio of influence running time Pearson correlation
Baselines: Random OdC BC PR KED MDS BPM MBPM Greedy RIS
Builds on: independent cascade model graph convolutional networks Monte Carlo influence estimation
Closest papers by meaning
- Graph Bayesian Optimization for Multiplex Influence Maximization (AAAI 2024 · similarity 0.88)
- REM: A Scalable Reinforced Multi-Expert Framework for Multiplex Influence Maximization (AAAI 2025 · similarity 0.87)
- DeepSN: A Sheaf Neural Framework for Influence Maximization (AAAI 2025 · similarity 0.87)
- Influence Functions for Edge Edits in Non-Convex Graph Neural Networks (NeurIPS 2025 · similarity 0.86)
- Hyperparametric Robust and Dynamic Influence Maximization (AAAI 2025 · similarity 0.86)
- DAG-Aware Variational Autoencoder for Social Propagation Graph Generation (AAAI 2024 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.