Gaussian Graphical Models (GGMs) or Gauss Markov random fields are widely
used in many applications, and the trade-off between the modeling capacity and
the efficiency of learning and inference has been an important research
problem. In this paper, we study the family of GGMs with small feedback vertex
sets (FVSs), where an FVS is a set of nodes whose removal breaks all the
cycles. Exact inference such as computing the marginal distributions and the
partition function has complexity $O(k^{2}n)$ using message-passing algorithms,
where k is the size of the FVS, and n is the total number of nodes. We propose
efficient structure learning algorithms for two cases: 1) All nodes are
observed, which is useful in modeling social or flight networks where the FVS
nodes often correspond to a small number of high-degree nodes, or hubs, while
the rest of the networks is modeled by a tree. Regardless of the maximum
degree, without knowing the full graph structure, we can exactly compute the
maximum likelihood estimate in $O(kn^2+n^2\log n)$ if the FVS is known or in
polynomial time if the FVS is unknown but has bounded size. 2) The FVS nodes
are latent variables, where structure learning is equivalent to decomposing a
inverse covariance matrix (exactly or approximately) into the sum of a
tree-structured matrix and a low-rank matrix. By incorporating efficient
inference into the learning steps, we can obtain a learning algorithm using
alternating low-rank correction with complexity $O(kn^{2}+n^{2}\log n)$ per
iteration. We also perform experiments using both synthetic data as well as
real data of flight delays to demonstrate the modeling capacity with FVSs of
various sizes.

本文研究带有小反馈顶点集的高斯图模型，提出了有效的结构学习算法，特别是针对隐藏变量的情况，能够通过交替低秩校正等方式成功地学习模型参数，并用合成数据和真实数据进行了验证。