## A Junction Tree Framework for Undirected Graphical Model Selection

*Divyanshu Vats, Robert D. Nowak*; 15(Jan):147−191, 2014.

### Abstract

An undirected graphical model is a joint probability
distribution defined on an undirected graph $G^*$, where the
vertices in the graph index a collection of random variables and
the edges encode conditional independence relationships among
random variables. The undirected graphical model selection
(UGMS) problem is to estimate the graph $G^*$ given observations
drawn from the undirected graphical model. This paper proposes a
framework for decomposing the UGMS problem into multiple
subproblems over clusters and subsets of the separators in a
junction tree. The junction tree is constructed using a graph
that contains a superset of the edges in $G^*$. We highlight
three main properties of using junction trees for UGMS. First,
different regularization parameters or different UGMS algorithms
can be used to learn different parts of the graph. This is
possible since the subproblems we identify can be solved
independently of each other. Second, under certain conditions, a
junction tree based UGMS algorithm can produce consistent
results with fewer observations than the usual requirements of
existing algorithms. Third, both our theoretical and
experimental results show that the junction tree framework does
a significantly better job at finding the weakest edges in a
graph than existing methods. This property is a consequence of
both the first and second properties. Finally, we note that our
framework is independent of the choice of the UGMS algorithm and
can be used as a wrapper around standard UGMS algorithms for
more accurate graph estimation.

[abs][pdf][bib]