  Undirected graphical models encode in a graph $G$ the dependency structure of
a random vector $Y$. In many applications, it is of interest to model $Y$ given
another random vector $X$ as input. We refer to the problem of estimating the
graph $G(x)$ of $Y$ conditioned on $X=x$ as ``graph-valued regression.'' In
this paper, we propose a semiparametric method for estimating $G(x)$ that
builds a tree on the $X$ space just as in CART (classification and regression
trees), but at each leaf of the tree estimates a graph. We call the method
``Graph-optimized CART,'' or Go-CART. We study the theoretical properties of
Go-CART using dyadic partitioning trees, establishing oracle inequalities on
risk minimization and tree partition consistency. We also demonstrate the
application of Go-CART to a meteorological dataset, showing how graph-valued
regression can provide a useful tool for analyzing complex data.
