# Inferring Graphs from Cascades: A Sparse Recovery Framework

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 May 2015.

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

- [Network Inference and Influence Maximization from Samples](https://mlsanity.com/paper/2106.03403/) (2021)
- [A Graph Dynamics Prior for Relational Inference](https://mlsanity.com/paper/2306.06041/) (2023)
- [Learning of networked spreading models from noisy and incomplete data](https://mlsanity.com/paper/2401.00011/) (2023)
- [Cascade-based Randomization for Inferring Causal Effects under Diffusion Interference](https://mlsanity.com/paper/2405.12340/) (2024)
- [Online Influence Maximization under the Independent Cascade Model with Node-Level Feedback](https://mlsanity.com/paper/2109.06077/) (2021)
- [Learning the Topology and Behavior of Discrete Dynamical Systems](https://mlsanity.com/paper/2402.11686/) (2024)
- [Learning hidden cascades via classification](https://mlsanity.com/paper/2505.11228/) (2025)
- [Latent Network Embedding via Adversarial Auto-encoders](https://mlsanity.com/paper/2109.15257/) (2021)
- [Efficient PAC Learnability of Dynamical Systems Over Multilayer Networks](https://mlsanity.com/paper/2405.06884/) (2024)
- [Gated Graph Neural Networks for Learning Hidden Independent Cascade Dynamics](https://mlsanity.com/paper/2610.04033/) (2026)

## Abstract (arXiv)

In the Network Inference problem, one seeks to recover the edges of an unknown graph from the observations of cascades propagating over this graph. In this paper, we approach this problem from the sparse recovery perspective. We introduce a general model of cascades, including the voter model and the independent cascade model, for which we provide the first algorithm which recovers the graph's edges with high probability and O(slog m) measurements where s is the maximum degree of the graph and m is the number of nodes. Furthermore, we show that our algorithm also recovers the edge weights (the parameters of the diffusion process) and is robust in the context of approximate sparsity. Finally we prove an almost matching lower bound of Omega(slogfracms) and validate our approach empirically on synthetic graphs.