Learning Gaussian Graphical Models with Observed or Latent FVSs
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 highly influential 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 with complexity 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 an 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 corrections with complexity O(kn 2 + n 2 log n) per iteration. We perform experiments using both synthetic data as well as real data of flight delays to demonstrate the modeling capacity with FVSs of various sizes.
'Learning Gaussian Graphical Models with Observed or 
      Latent FVSs' addresses the problem of learning (i.e. discovery of the 
      graph structure) a GGM which can be decomposed into a small feedback 
      vertex set and a tree. The motivation is that exact inference under these 
      models can be done quickly, and so in the case where one needs near-linear 
      inference (which is prohibited in general for sparse GGMs) it is desirable 
      to have this form. The results address three cases: (4.1.1) all nodes are 
      observed with known FVS, (4.1.2) all nodes are observed with unknown FVS, 
      (4.2) and the FVS is latent. In (4.1.1) they provide a simple extension of 
      the Chow-Liu algorithm, which applies CL to the empirical Schur 
      complement. In (4.1.2) they make the observation that one can exhaustively 
      run the previous algorithm for all k-sets selecting the one that maximizes 
      the likelihood and then provide a greedy algorithm. In (4.2) they provide 
      an EM-type algorithm that uses the conditional distribution from the 
      previous iteration to find an empirical joint distribution then finding 
      the best structure from this with CL. There is a nice interpretation using 
      low rank adjustments in each step. They show that each iteration decreases 
      the KL. There is a very nice experimental section, which applies this to 
      flight traffic data. The paper is high quality, as it motivates 
      the problem well, describes the landscape of learning GGMs, and 
      comprehensively provides an algorithm for each situation. The paper is 
      clear as it is well written and well organized. The paper seems original, 
      as it is a unique extension of the Chow-Liu algorithm. The significance of 
      this paper is somewhat suspect (although I admit that I am not an expert 
      in this field). While it is the case that exact inference is more 
      difficult for non-tree graphs, it is a bit difficult to imagine real-world 
      GGMs that can be decomposed into the FVS and a tree. And if we don't 
      believe that we are providing an accurate graph and only a convenient 
      approximation, then approximate inference should be as good as we can hope 
      for. If this is the case, then we can employ loopy BP, or even linear 
      solvers. Prop 1 is really just the fact that CL works on the Schur 
      complement too, and Prop 2 doesn't tell us that much. Again, I may have 
      overlooked some fundamental insight into how important this extension is, 
      so please argue with me on this point. With that said, I think that the 
      insights into using CL with the FVS merits publication, as there is 
      precedent for doing inference with the FVS. typos: 141: proved 
      in the 265: the sentence 'We have no search of sets...' is awkward 
      306: overlaping lines 313: 
      D_KL(N(0,...