Testing Unfaithful Gaussian Graphical Models

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 X_u is conditionally independent of X_v given X_S . The opposite direction need not be true, that is, X_u \perp X_v \mid X_S need not imply S is a node separator of u and v . 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 X_i \perp X_j \mid X_S .