Estimating high dimensional faithful Gaussian graphical models by low-order conditioning. (English) Zbl 1157.68407

Gammerman, A. (ed.), Artificial intelligence and applications. Machine learning. As part of the 26th IASTED international multi-conference on applied informatics. Calgary: International Association of Science and Technology for Development (IASTED); Anaheim, CA: Acta Press (ISBN 978-0-88986-710-9/CD-ROM). 1-6 (2008).
Summary: The aim of this paper is to devise a new PC-algorithm (partial correlation), uPC-algorithm, for estimating a high dimensional undirected graph associated to a faithful Gaussian Graphical Model. First, we define the separability order 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 accuracy and consistency and we compare it with the 0 - 1 covariance graph estimation recently proposed by A. Wille and P. Bühlman [Stat. Appl. Genet. Mol. Biol. 5, No. 1, Article 1, electronic only (2006; Zbl 1166.62374)].
For the entire collection see [Zbl 1154.68012].


68R10 Graph theory (including graph drawing) in computer science
68W05 Nonnumerical algorithms


Zbl 1166.62374