Efficient local updates for undirected graphical models

We present a new Bayesian approach for undirected Gaussian graphical model determination. We provide some graph theory results for local updates that facilitate a fast exploration of the graph space. Specifically, we show how to locally update, after either edge deletion or inclusion, the perfect sequence of cliques and the perfect elimination order of the nodes associated to an oriented, directed acyclic version of a decomposable graph. Building upon the decomposable graphical models framework, we propose a more flexible methodology that extends to the class of nondecomposable graphs. Posterior probabilities of edge inclusion are interpreted as a natural measure of edge selection uncertainty. When applied to a protein expression data set, the model leads to fast estimation of the protein interaction network.