Scalable network reconstruction in subquadratic time

Network reconstruction consists in determining the unobserved pairwise couplings between <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>N</mml:mi> </mml:math> 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 <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>Ω</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:msup> <mml:mi>N</mml:mi> <mml:mn>2</mml:mn> </mml:msup> <mml:mo stretchy="false">)</mml:mo> </mml:math> , 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 <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>O</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mi>N</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:math> . 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 <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>O</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:msup> <mml:mi>N</mml:mi> <mml:mrow> <mml:mn>3</mml:mn> <mml:mrow> <mml:mo>/</mml:mo> </mml:mrow> <mml:mn>2</mml:mn> </mml:mrow> </mml:msup> <mml:mi>log</mml:mi> <mml:mo>⁡</mml:mo> <mml:mi>N</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:math> , but with a more typical log-linear complexity of <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>O</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mi>N</mml:mi> <mml:msup> <mml:mi>log</mml:mi> <mml:mn>2</mml:mn> </mml:msup> <mml:mo>⁡</mml:mo> <mml:mi>N</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:math> . 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.