Learning Networks From Wide-Sense Stationary Stochastic Processes

Complex networked systems driven by latent inputs are common in fields like neuroscience, finance, and engineering. A key inference problem here is to learn edge connectivity from node outputs (potentials). We focus on systems governed by steady-state linear conservation laws: <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow><mml:msub><mml:mi>X</mml:mi> <mml:mi>t</mml:mi></mml:msub> <mml:mo>=</mml:mo> <mml:mi>L</mml:mi> <mml:mo>*</mml:mo> <mml:msub><mml:mi>Y</mml:mi> <mml:mi>t</mml:mi></mml:msub> </mml:mrow> </mml:math> , where <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow><mml:msub><mml:mi>X</mml:mi> <mml:mi>t</mml:mi></mml:msub> <mml:mo>,</mml:mo> <mml:msub><mml:mi>Y</mml:mi> <mml:mi>t</mml:mi></mml:msub> <mml:mo>∈</mml:mo> <mml:msup><mml:mi>ℝ</mml:mi> <mml:mi>p</mml:mi></mml:msup> </mml:mrow> </mml:math> denote inputs and potentials, respectively, and the sparsity pattern of the <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>p</mml:mi> <mml:mo>×</mml:mo> <mml:mi>p</mml:mi></mml:mrow> </mml:math> Laplacian <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>L</mml:mi> <mml:mo>*</mml:mo></mml:mrow> </mml:math> encodes the edge structure. Assuming <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow><mml:msub><mml:mi>X</mml:mi> <mml:mi>t</mml:mi></mml:msub> </mml:mrow> </mml:math> to be a wide-sense stationary stochastic process with a known spectral density matrix, we learn the support of <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>L</mml:mi> <mml:mo>*</mml:mo></mml:mrow> </mml:math> from temporally correlated samples of <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow><mml:msub><mml:mi>Y</mml:mi> <mml:mi>t</mml:mi></mml:msub> </mml:mrow> </mml:math> via an <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow><mml:msub><mml:mi>ℓ</mml:mi> <mml:mn>1</mml:mn></mml:msub> </mml:mrow> </mml:math> -regularized Whittle's maximum likelihood estimator (MLE). The regularization is particularly useful for learning large-scale networks in the high-dimensional setting where the network size <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>p</mml:mi></mml:math> significantly exceeds the number of samples <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>n</mml:mi></mml:math> . We show that the MLE problem is strictly convex, admitting a unique solution. Under a novel mutual incoherence condition and certain sufficient conditions on <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mo>(</mml:mo> <mml:mi>n</mml:mi> <mml:mo>,</mml:mo> <mml:mi>p</mml:mi> <mml:mo>,</mml:mo> <mml:mi>d</mml:mi> <mml:mo>)</mml:mo></mml:mrow> </mml:math> , we show that the ML estimate recovers the sparsity pattern of <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>L</mml:mi> <mml:mo>*</mml:mo></mml:mrow> </mml:math> with high probability, where <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>d</mml:mi></mml:math> is the maximum degree of the graph underlying <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>L</mml:mi> <mml:mo>*</mml:mo></mml:mrow> </mml:math> . We provide recovery guarantees for <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>L</mml:mi> <mml:mo>*</mml:mo></mml:mrow> </mml:math> in element-wise maximum, Frobenius, and operator norms. Finally, we complement our theoretical results with several simulation studies on synthetic and benchmark datasets, including engineered systems (power and water networks), and real-world datasets from neural systems (such as the human brain).