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}$.

通过基于高斯分布的傅里叶分析属性，我们提出了一个新的估计器，可从在网络上重复测量的高斯自由场图中估计加权网络的结构（等价地，其拉普拉斯矩阵），并展示了具体的恢复保证和所需样本复杂度的界限。

从高斯图模型和高斯自由场学习网络

Learning Networks from Gaussian Graphical Models and Gaussian Free  Fields

We introduce the graphlet decomposition of a weighted network, which encodes
a notion of social information based on social structure. We develop a scalable
inference algorithm, which combines EM with Bron-Kerbosch in a novel fashion,
for estimating the parameters of the model underlying graphlets using one
network sample. We explore some theoretical properties of the graphlet
decomposition, including computational complexity, redundancy and expected
accuracy. We demonstrate graphlets on synthetic and real data. We analyze
messaging patterns on Facebook and criminal associations in the 19th century.

本文介绍了使用图结构对加权网络进行图元分解的方法，并使用具有可扩展性的 EM-Bron-Kerbosch 算法对其进行参数估计，探究了图元分解的计算复杂性、冗余性和预期精度等理论性质，并在 Facebook 的消息模式和 19 世纪的犯罪组织等实际数据上进行了应用和分析。