Research map / Learning theory and algorithms / Submodular and game algorithms
Hyperparametric Robust and Dynamic Influence Maximization
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 RIME, a method for robust influence maximization over dynamic (insertion/removal) diffusion networks under a hyperparametric IC model, combining multiplicative weight updates with a greedy algorithm and giving approximation guarantees.
Problem
Influence maximization in dynamic diffusion networks where edge probabilities are uncertain, governed by a global hyperparameter; the seed set must maximize worst-case spread at every time step as the network changes.
Approach
Combines the MWU-based robust IM method HIRO with a greedy max-coverage algorithm over reverse-reachable sets sampled per hyperparameter value, with incremental RR-set updates on node/edge insertions and removals and restarts when the graph size doubles or halves, yielding bi-criteria approximation guarantees for both incremental and fully dynamic settings.
Key results
- RIME is several orders of magnitude faster than baselines (HIRO, BASE, LUGreedy) in total running time over network updates, while achieving comparable solution quality.
- Incremental setting RIME is 2-3 orders of magnitude faster than its fully dynamic setting.
- Empirical gap between the guarantee and 1-1/e-epsilon was about 4.7e-14 (incremental) and 0.124 (fully dynamic) max across 5 networks.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use RIME instead of recomputing influence maximization from scratch after every update | Dynamic influence maximization · Synthetic and real-world networks | total running time: several orders of magnitude faster | Helped |
| Use RIME instead of HIRO | Robust dynamic influence maximization · Networks where HIRO completes | minimum influence spread | No clear effect |
| Use RIME instead of BASE | Robust dynamic influence maximization · Synthetic and real-world networks | minimum influence spread | Helped |
| Use RIME instead of LUGreedy | Robust dynamic influence maximization · Networks where LUGreedy completes | minimum influence spread | Helped |
| Use the incremental setting rather than the fully dynamic setting | RIME · Synthetic and real-world networks | total running time: 2-3 orders of magnitude faster | Helped |
| Increase the hyperparameter-space radius B (ablation) | RIME · Networks evaluated with varying B | minimum influence spread | Hurt |
| Increase the sample count l or MWU iteration count T (ablation) | RIME · Networks evaluated with varying l and T | solution quality | No clear effect |
| Vary the seed budget k (ablation) | RIME · Weibo | minimum influence spread | No clear effect |
Surprising findings
- Solution quality converges at very small numbers of hyperparameter samples l and T, far below theoretical requirements.
Limitations
- HIRO and LUGreedy do not scale beyond about 10^3 to 10^4 nodes; RIME scales only to around 10^5 nodes.
- Fully dynamic setting is 2-3 orders of magnitude slower than incremental setting.
- Theoretical guarantees require large l and T values that are impractical; practical values much smaller.
Experimental setup
Datasets: Weibo repost network LiveJournal synthetic random networks
Benchmarks: Weibo LiveJournal synthetic random networks
Metrics: total running time minimum approximate influence spread across sampled hyperpar
Baselines: HIRO BASE LUGreedy
Builds on: HIRO Independent Cascade model dynamic influence maximization incremental algorithm LUGreedy reverse influence sampling
Closest papers by meaning
- Correlation Robust Influence Maximization (NeurIPS 2020 · similarity 0.91)
- Robust Influence Maximization for Hyperparametric Models (ICML 2019 · similarity 0.91)
- REM: A Scalable Reinforced Multi-Expert Framework for Multiplex Influence Maximization (AAAI 2025 · similarity 0.87)
- DiffIM: Differentiable Influence Minimization with Surrogate Modeling and Continuous Relaxation (AAAI 2025 · similarity 0.86)
- DeepSN: A Sheaf Neural Framework for Influence Maximization (AAAI 2025 · similarity 0.86)
- Graph Bayesian Optimization for Multiplex Influence Maximization (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.