Learning Networks from Gaussian Graphical Models and Gaussian Free
  Fields
Subhro Ghosh Soumendu Sundar Mukherjee Hoang-Son Tran Ujan Gangopadhyay
We investigate the problem of estimating the structure of a weighted network
from repeated measurements of a Gaussian Graphical Model (GGM) on the network.
In this vein, we consider GGMs whose covariance structures align with the
geometry of the weighted network on which they are based. Such GGMs have been
of longstanding interest in statistical physics, and are referred to as the
Gaussian Free Field (GFF). In recent years, they have attracted considerable
interest in the machine learning and theoretical computer science. In this
work, we propose a novel estimator for the weighted network (equivalently, its
Laplacian) from repeated measurements of a GFF on the network, based on the
Fourier analytic properties of the Gaussian distribution. In this pursuit, our
approach exploits complex-valued statistics constructed from observed data,
that are of interest on their own right. We demonstrate the effectiveness of
our estimator with concrete recovery guarantees and bounds on the required
sample complexity. In particular, we show that the proposed statistic achieves
the parametric rate of estimation for fixed network size. In the setting of
networks growing with sample size, our results show that for Erdos-Renyi random
graphs $G(d,p)$ above the connectivity threshold, we demonstrate that network
recovery takes place with high probability as soon as the sample size $n$
satisfies $n \gg d^4 \log d \cdot p^{-2}$.