Scalable network reconstruction in subquadratic time
Open Access
- 29 October 2025
- journal article
- Published by The Royal Society in Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences
- Vol. 481 (2324)
Abstract
Network reconstruction consists in determining the unobserved pairwise couplings between N nodes given only observational data on the resulting behaviour 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 Ω ( N 2 ) , 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 are 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-neighbour search that produces the best edge candidates with high probability, thus bypassing an exhaustive quadratic search. If we rely on the conjecture that the second-neighbour search finishes in log-linear time, we demonstrate theoretically that our algorithm finishes in subquadratic time, with a data-dependent complexity loosely upper bounded by O ( N 3 / 2 log N ) , but with a more typical log-linear complexity of O ( N log 2 N ) . 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.Keywords
All Related Versions
Funding Information
- Vienna Science and Technology Fund (10.47379/ESS22032)
This publication has 38 references indexed in Scilit:
- From diversity to complexity: Microbial networks in soilsSoil Biology and Biochemistry, 2022
- A communal catalogue reveals Earth’s multiscale microbial diversityNature, 2017
- Coordinate descent algorithmsMathematical Programming, 2015
- Structure, function and diversity of the healthy human microbiomeNature, 2012
- Cyclic Seesaw Process for Optimization and IdentificationJournal of Optimization Theory and Applications, 2012
- Identification of direct residue contacts in protein–protein interaction by message passingProceedings of the National Academy of Sciences, 2009
- Synchronization in complex networksPhysics Reports, 2008
- Reconstruction of Markov Random Fields from Samples: Some Observations and Algorithms2008
- Convergence of a Block Coordinate Descent Method for Nondifferentiable MinimizationJournal of Optimization Theory and Applications, 2001
- Closest-Point Problems in Computational Geometry2000