Processing math: 100%

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, XuXvXS need not imply S is a node separator of u and v. When it does, the relation XuXvXS 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 XiXjXS. 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.

PDF BibTeX