  Large graphs abound in machine learning, data mining, and several related
areas. A useful step towards analyzing such graphs is that of obtaining certain
summary statistics - e.g., or the expected length of a shortest path between
two nodes, or the expected weight of a minimum spanning tree of the graph, etc.
These statistics provide insight into the structure of a graph, and they can
help predict global properties of a graph. Motivated thus, we propose to study
statistical properties of structured subgraphs (of a given graph), in
particular, to estimate the expected objective function value of a
combinatorial optimization problem over these subgraphs. The general task is
very difficult, if not unsolvable; so for concreteness we describe a more
specific statistical estimation problem based on spanning trees. We hope that
our position paper encourages others to also study other types of graphical
structures for which one can prove nontrivial statistical estimates.
