# Scalable network reconstruction in subquadratic time

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 47 references that are in the map.
- First posted on arXiv 2 Jan 2024.

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

- [UMAP: Uniform Manifold Approximation and Projection for Dimension Reduction](https://mlsanity.com/paper/1802.03426/) (2018)
- [Coordinate Descent Algorithms](https://mlsanity.com/paper/1502.04759/) (2015)
- [Structure Learning in Graphical Modeling](https://mlsanity.com/paper/1606.02359/) (2016)
- [Network Inference via the Time-Varying Graphical Lasso](https://mlsanity.com/paper/1703.01958/) (2017)
- [Efficiently learning Ising models on arbitrary graphs](https://mlsanity.com/paper/1411.6156/) (2014)
- [Inverse statistical problems: from the inverse Ising problem to data science](https://mlsanity.com/paper/1702.01522/) (2017)
- [Learning graphical models from the Glauber dynamics](https://mlsanity.com/paper/1410.7659/) (2014)
- [Network reconstruction and community detection from dynamics](https://mlsanity.com/paper/1903.10833/) (2019)
- [A convex pseudo-likelihood framework for high dimensional partial correlation estimation with convergence guarantees](https://mlsanity.com/paper/1307.5381/) (2013)
- [Network reconstruction from infection cascades](https://mlsanity.com/paper/1609.00432/) (2016)
- [Empirical complexity of comparator-based nearest neighbor descent](https://mlsanity.com/paper/2202.00517/) (2022)

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

- [Network reconstruction via the minimum description length principle](https://mlsanity.com/paper/2405.01015/) (2024)
- [Uncertainty quantification and posterior sampling for network reconstruction](https://mlsanity.com/paper/2503.07736/) (2025)

## Abstract (arXiv)

Network reconstruction consists in determining the unobserved pairwise couplings between N nodes given only observational data on the resulting behavior that is conditioned on those couplings -- typically a time-series or independent samples from a graphical model. A major obstacle to the scalability of algorithms proposed for this problem is a seemingly unavoidable quadratic complexity of Omega(N2), corresponding to the requirement of each possible pairwise coupling being contemplated at least once, despite the fact that most networks of interest are sparse, with a number of non-zero couplings that is only O(N). Here we present a general algorithm applicable to a broad range of reconstruction problems that significantly outperforms this quadratic baseline. Our algorithm relies on a stochastic second neighbor search (Dong et al., 2011) that produces the best edge candidates with high probability, thus bypassing an exhaustive quadratic search. If we rely on the conjecture that the second-neighbor search finishes in log-linear time (Baron & Darling, 2020; 2022), we demonstrate theoretically that our algorithm finishes in subquadratic time, with a data-dependent complexity loosely upper bounded by O(N3/2log N), but with a more typical log-linear complexity of O(Nlog2N). In practice, we show that our algorithm achieves a performance that is many orders of magnitude faster than the quadratic baseline -- in a manner consistent with our theoretical analysis -- allows for easy parallelization, and thus enables the reconstruction of networks with hundreds of thousands and even millions of nodes and edges.