Learning Unfaithful K-separable Gaussian Graphical Models
De Wen Soh, Sekhar Tatikonda.
Year: 2019, Volume: 20, Issue: 109, Pages: 1−30
Abstract
The global Markov property for Gaussian graphical models ensures graph separation implies conditional independence. Specifically if a node set S graph separates nodes u and v then Xu is conditionally independent of Xv given XS. The opposite direction need not be true, that is, Xu⊥Xv∣XS need not imply S is a node separator of u and v. When it does, the relation Xu⊥Xv∣XS is called faithful. In this paper we provide a characterization of faithful relations and then provide an algorithm to test faithfulness based only on knowledge of other conditional relations of the form Xi⊥Xj∣XS. We study two classes of separable Gaussian graphical models, namely, weakly K-separable and strongly K-separable Gaussian graphical models. Using the above test for faithfulness, we introduce algorithms to learn the topologies of weakly K-separable and strongly K-separable Gaussian graphical models with Ω(Klogp) sample complexity. For strongly K-separable Gaussian graphical models, we additionally provide a method with error bounds for learning the off-diagonal precision matrix entries.