# Estimating Diffusion Network Structures: Recovery Conditions, Sample Complexity & Soft-thresholding Algorithm

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

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 May 2014.

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

- [Network Inference and Influence Maximization from Samples](https://mlsanity.com/paper/2106.03403/) (2021)
- [On the Correctness and Sample Complexity of Inverse Reinforcement Learning](https://mlsanity.com/paper/1906.00422/) (2019)
- [Fair Sparse Regression with Clustering: An Invex Relaxation for a Combinatorial Problem](https://mlsanity.com/paper/2102.09704/) (2021)
- [Learning Graph Structure from Convolutional Mixtures](https://mlsanity.com/paper/2205.09575/) (2022)
- [Sparse Mixed Linear Regression with Guarantees: Taming an Intractable Problem with Invex Relaxation](https://mlsanity.com/paper/2206.01167/) (2022)
- [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)
- [A Theoretical Study of The Effects of Adversarial Attacks on Sparse Regression](https://mlsanity.com/paper/2212.11209/) (2022)
- [Outlier-robust Estimation of a Sparse Linear Model Using Invexity](https://mlsanity.com/paper/2306.12678/) (2023)
- [Survival Analysis of the Compressor Station Based on Hawkes Process with Weibull Base Intensity](https://mlsanity.com/paper/2112.13581/) (2021)
- [pyGSL: A Graph Structure Learning Toolkit](https://mlsanity.com/paper/2211.03583/) (2022)
- [Distributionally Robust Skeleton Learning of Discrete Bayesian Networks](https://mlsanity.com/paper/2311.06117/) (2023)
- [Efficient PAC Learnability of Dynamical Systems Over Multilayer Networks](https://mlsanity.com/paper/2405.06884/) (2024)
- [Causal Structure Learning in Hawkes Processes with Complex Latent Confounder Networks](https://mlsanity.com/paper/2508.11727/) (2025)
- [Gated Graph Neural Networks for Learning Hidden Independent Cascade Dynamics](https://mlsanity.com/paper/2610.04033/) (2026)

## Abstract (arXiv)

Information spreads across social and technological networks, but often the network structures are hidden from us and we only observe the traces left by the diffusion processes, called cascades. Can we recover the hidden network structures from these observed cascades? What kind of cascades and how many cascades do we need? Are there some network structures which are more difficult than others to recover? Can we design efficient inference algorithms with provable guarantees? Despite the increasing availability of cascade data and methods for inferring networks from these data, a thorough theoretical understanding of the above questions remains largely unexplored in the literature. In this paper, we investigate the network structure inference problem for a general family of continuous-time diffusion models using an l1-regularized likelihood maximization framework. We show that, as long as the cascade sampling process satisfies a natural incoherence condition, our framework can recover the correct network structure with high probability if we observe O(d3 log N) cascades, where d is the maximum number of parents of a node and N is the total number of nodes. Moreover, we develop a simple and efficient soft-thresholding inference algorithm, which we use to illustrate the consequences of our theoretical results, and show that our framework outperforms other alternatives in practice.