Estimating High Dimensional Faithful Gaussian Graphical Models by Low-Order Conditioning

D. Malouche (Tunisia) and S. Sevestre-Ghalila (France)


Graphical Models, PartialCorrelation, Markov Properties, Multivariate Normal Distribution.


The aim of this paper is to devise a new PC-algorithm (par tial correlation), uPC-algorithm, for estimating a high di mensional undirected graph associated to a faithful Gaus sian Graphical Model. First, we define the separability or der of a graph as the maximum cardinality among all its minimal separators. We construct a sequence of graphs by increasing the number of the conditioning variables. We prove that these graphs are nested and at a limited stage, equal to the separability order, this sequence is constant and equal to the true graph. Thus, the uPC-algorithm devised in this paper, is a step-down procedure based on a recursive estimation of these nested graphs. We show on simulated data its ac curacy and consistency and we compare it with the 0 − 1 covariance graph estimation recently proposed by [11].

Important Links:

Go Back