# Contingency-Aware Influence Maximization: A Reinforcement Learning Approach

arXiv: https://arxiv.org/abs/2106.07039 · HTML: https://mlsanity.com/paper/2106.07039/

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 48 references that are in the map.
- First posted on arXiv 13 Jun 2021.

## Builds on (most cited first, 22 of 22)

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Playing Atari with Deep Reinforcement Learning](https://mlsanity.com/paper/1312.5602/) (2013)
- [Pointer Networks](https://mlsanity.com/paper/1506.03134/) (2015)
- [Attention, Learn to Solve Routing Problems!](https://mlsanity.com/paper/1803.08475/) (2018)
- [Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizon](https://mlsanity.com/paper/1811.06128/) (2018)
- [Neural Combinatorial Optimization with Reinforcement Learning](https://mlsanity.com/paper/1611.09940/) (2016)
- [Learning Combinatorial Optimization Algorithms over Graphs](https://mlsanity.com/paper/1704.01665/) (2017)
- [Reinforcement Learning for Solving the Vehicle Routing Problem](https://mlsanity.com/paper/1802.04240/) (2018)
- [An Efficient Graph Convolutional Network Technique for the Travelling Salesman Problem](https://mlsanity.com/paper/1906.01227/) (2019)
- [Combinatorial Optimization with Graph Convolutional Networks and Guided Tree Search](https://mlsanity.com/paper/1810.10659/) (2018)
- [Learning Scheduling Algorithms for Data Processing Clusters](https://mlsanity.com/paper/1810.01963/) (2018)
- [Discriminative Embeddings of Latent Variable Models for Structured Data](https://mlsanity.com/paper/1603.05629/) (2016)
- [Influence maximization in unknown social networks: Learning Policies for Effective Graph Sampling](https://mlsanity.com/paper/1907.11625/) (2019)
- [DISCO: Influence Maximization Meets Network Embedding and Deep Learning](https://mlsanity.com/paper/1906.07378/) (2019)
- [Clinical trial of an AI-augmented intervention for HIV prevention in youth experiencing homelessness](https://mlsanity.com/paper/2009.09559/) (2020)
- [Using Social Networks to Aid Homeless Shelters: Dynamic Influence Maximization under Uncertainty - An Extended Version](https://mlsanity.com/paper/1602.00165/) (2016)
- [Active Screening for Recurrent Diseases: A Reinforcement Learning Approach](https://mlsanity.com/paper/2101.02766/) (2021)
- [Efficient Approximation Algorithms for Adaptive Influence Maximization](https://mlsanity.com/paper/2004.06469/) (2020)
- [Learning Explainable Interventions to Mitigate HIV Transmission in Sex Workers Across Five States in India](https://mlsanity.com/paper/2012.01930/) (2020)
- [Artificial Intelligence for the Public Sector: Opportunities and challenges of cross-sector collaboration](https://mlsanity.com/paper/1809.04399/) (2018)
- [MONSTOR: An Inductive Approach for Estimating and Maximizing Influence over Unseen Networks](https://mlsanity.com/paper/2001.08853/) (2020)

## Built on by (most cited first, 13 of 13)

- [Challenges and Opportunities in Deep Reinforcement Learning with Graph Neural Networks: A Comprehensive review of Algorithms and Applications](https://mlsanity.com/paper/2206.07922/) (2022)
- [Graph Reinforcement Learning for Combinatorial Optimization: A Survey and Unifying Perspective](https://mlsanity.com/paper/2404.06492/) (2024)
- [A Survey on Influence Maximization: From an ML-Based Combinatorial Optimization](https://mlsanity.com/paper/2211.03074/) (2022)
- [ToupleGDD: A Fine-Designed Solution of Influence Maximization by Deep Reinforcement Learning](https://mlsanity.com/paper/2210.07500/) (2022)
- [Maximizing Influence with Graph Neural Networks](https://mlsanity.com/paper/2108.04623/) (2021)
- [Graph Representation Learning for Popularity Prediction Problem: A Survey](https://mlsanity.com/paper/2203.07632/) (2022)
- [Dyadic Reinforcement Learning](https://mlsanity.com/paper/2308.07843/) (2023)
- [Never Explore Repeatedly in Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2308.09909/) (2023)
- [DQ4FairIM: Fairness-aware Influence Maximization using Deep Reinforcement Learning](https://mlsanity.com/paper/2512.00545/) (2025)
- [HyCO: A Hybrid Neural Solver for Combinatorial Optimization](https://mlsanity.com/paper/2609.07990/) (2026)
- [A Benchmark Study of Deep-RL Methods for Maximum Coverage Problems over Graphs](https://mlsanity.com/paper/2406.14697/) (2024)
- [SP-GCRL: Influence Maximization on Incomplete Social Graphs](https://mlsanity.com/paper/2605.12513/) (2026)
- [Learning Multi-Timescale Abstractions for Hierarchical Combinatorial Planning](https://mlsanity.com/paper/2605.17058/) (2026)

## Abstract (arXiv)

The influence maximization (IM) problem aims at finding a subset of seed nodes in a social network that maximize the spread of influence. In this study, we focus on a sub-class of IM problems, where whether the nodes are willing to be the seeds when being invited is uncertain, called contingency-aware IM. Such contingency aware IM is critical for applications for non-profit organizations in low resource communities (e.g., spreading awareness of disease prevention). Despite the initial success, a major practical obstacle in promoting the solutions to more communities is the tremendous runtime of the greedy algorithms and the lack of high performance computing (HPC) for the non-profits in the field -- whenever there is a new social network, the non-profits usually do not have the HPCs to recalculate the solutions. Motivated by this and inspired by the line of works that use reinforcement learning (RL) to address combinatorial optimization on graphs, we formalize the problem as a Markov Decision Process (MDP), and use RL to learn an IM policy over historically seen networks, and generalize to unseen networks with negligible runtime at test phase. To fully exploit the properties of our targeted problem, we propose two technical innovations that improve the existing methods, including state-abstraction and theoretically grounded reward shaping. Empirical results show that our method achieves influence as high as the state-of-the-art methods for contingency-aware IM, while having negligible runtime at test phase.