# Network Inference and Influence Maximization from Samples

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 31 references that are in the map.
- First posted on arXiv 7 Jun 2021.

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

- [Combinatorial Multi-Armed Bandit and Its Extension to Probabilistically Triggered Arms](https://mlsanity.com/paper/1407.8339/) (2014)
- [Estimating Diffusion Network Structures: Recovery Conditions, Sample Complexity & Soft-thresholding Algorithm](https://mlsanity.com/paper/1405.2936/) (2014)
- [The Limitations of Optimization from Samples](https://mlsanity.com/paper/1512.06238/) (2015)
- [Inferring Graphs from Cascades: A Sparse Recovery Framework](https://mlsanity.com/paper/1505.05663/) (2015)
- [Trace Complexity of Network Inference](https://mlsanity.com/paper/1308.2954/) (2013)
- [Scalable Influence Estimation in Continuous-Time Diffusion Networks](https://mlsanity.com/paper/1311.3669/) (2013)
- [Learning Influence Functions from Incomplete Observations](https://mlsanity.com/paper/1611.02305/) (2016)
- [Optimization from Structured Samples for Coverage Functions](https://mlsanity.com/paper/2007.02738/) (2020)
- [Cumulative Activation in Social Networks](https://mlsanity.com/paper/1605.04635/) (2016)
- [The Importance of Communities for Learning to Influence](https://mlsanity.com/paper/1801.07355/) (2018)

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

- [Offline Learning for Combinatorial Multi-armed Bandits](https://mlsanity.com/paper/2501.19300/) (2025)
- [Geometric Algorithms for Neural Combinatorial Optimization with Constraints](https://mlsanity.com/paper/2510.24039/) (2025)
- [Inferring Dynamic Networks from Marginals with Iterative Proportional Fitting](https://mlsanity.com/paper/2402.18697/) (2024)
- [Online Influence Maximization under the Independent Cascade Model with Node-Level Feedback](https://mlsanity.com/paper/2109.06077/) (2021)
- [DSCom: A Data-Driven Self-Adaptive Community-Based Framework for Influence Maximization in Social Networks](https://mlsanity.com/paper/2311.11080/) (2023)
- [Learning the Topology and Behavior of Discrete Dynamical Systems](https://mlsanity.com/paper/2402.11686/) (2024)
- [Online Influence Maximization: Concept and Algorithm](https://mlsanity.com/paper/2312.00099/) (2023)
- [Efficient PAC Learnability of Dynamical Systems Over Multilayer Networks](https://mlsanity.com/paper/2405.06884/) (2024)
- [Learning Submodular Sequencing from Samples](https://mlsanity.com/paper/2409.05265/) (2024)

## Abstract (arXiv)

Influence maximization is the task of selecting a small number of seed nodes in a social network to maximize the influence spread from these seeds. It has been widely investigated in the past two decades. In the canonical setting, the social network and its diffusion parameters are given as input. In this paper, we consider the more realistic sampling setting where the network is unknown and we only have a set of passively observed cascades that record the sets of activated nodes at each diffusion step. We study the task of influence maximization from these cascade samples (IMS) and present constant approximation algorithms for it under mild conditions on the seed set distribution. To achieve the optimization goal, we also provide a novel solution to the network inference problem, that is, learning diffusion parameters and the network structure from the cascade data. Compared with prior solutions, our network inference algorithms require weaker assumptions and do not rely on maximum-likelihood estimation and convex programming. Our IMS algorithms enhance the learning-and-then-optimization approach by allowing a constant approximation ratio even when the diffusion parameters are hard to learn, and we do not need any assumption related to the network structure or diffusion parameters.