Title: Graphical Models: An Extension to Random Graphs, Trees, and Other Objects,
Abstract: In this work, we consider an extension of graphical models to random graphs,
trees, and other objects. To do this, many fundamental concepts for
multivariate random variables (e.g., marginal variables, Gibbs distribution,
Markov properties) must be extended to other mathematical objects; it turns out
that this extension is possible, as we will discuss, if we have a consistent,
complete system of projections on a given object. Each projection defines a
marginal random variable, allowing one to specify independence assumptions
between them. Furthermore, these independencies can be specified in terms of a
small subset of these marginal variables (which we call the atomic variables),
allowing the compact representation of independencies by a directed graph.
Projections also define factors, functions on the projected object space, and
hence a projection family defines a set of possible factorizations for a
distribution; these can be compactly represented by an undirected graph.
The invariances used in graphical models are essential for learning
distributions, not just on multivariate random variables, but also on other
objects. When they are applied to random graphs and random trees, the result is
a general class of models that is applicable to a broad range of problems,
including those in which the graphs and trees have complicated edge structures.
These models need not be conditioned on a fixed number of vertices, as is often
the case in the literature for random graphs, and can be used for problems in
which attributes are associated with vertices and edges. For graphs,
applications include the modeling of molecules, neural networks, and relational
real-world scenes; for trees, applications include the modeling of infectious
diseases, cell fusion, the structure of language, and the structure of objects
in visual scenes. Many classic models are particular instances of this
framework.