Geometric Representations of Random Hypergraphs

ABSTRACT

We introduce a novel parameterization of distributions on hypergraphs based on the geometry of points in ${\mathbb{R}}^d$. The idea is to induce distributions on hypergraphs by placing priors on point configurations via spatial processes. This specification is then used to infer conditional independence models, or Markov structure, for multivariate distributions. This approach results in a broader class of conditional independence models beyond standard graphical models. Factorizations that cannot be retrieved via a graph are possible. Inference of nondecomposable graphical models is possible without requiring decomposability, or the need of Gaussian assumptions. This approach leads to new Metropolis-Hastings Markov chain Monte Carlo algorithms with both local and global moves in graph space, generally offers greater control on the distribution of graph features than currently possible, and naturally extends to hypergraphs. We provide a comparative performance evaluation against state-of-the-art approaches, and illustrate the utility of this approach on simulated and real data.

KEYWORDS:

• Computational topology
• Copulas
• Factor models
• Graphical models
• Random geometric graphs
• Simplicial complex

Acknowledgments

We are grateful to Herbert Edelsbrunner, John Harer, Henry Wynn, and Sofia Olhede for helpful conversations. We are also grateful to two reviewers, the associate editor, and the editor for offering suggestions that improved the article.

Funding

This work was partially supported by the National Science Foundation Under grants DMS-0635449, DMS-0732260, DMS-0757549, CAREER IIS-1149662, and IIS-1409177, by National Institute of Health grants NIH R01 CA123175, R01 GM096193, and NIH P50-GM081883, by the Army Research Office grant MURI W911NF-11-1-0036, and by the Office of Naval Research Under grant YIP N00014-14-1-0485. Edoardo M. Airoldi is an Alfred P. Sloan Research Fellow, and a Shutzer Fellow at the Radcliffe Institute for Advanced Studies.

Notes

1 The parameter k in this case is actually the number of prime components, but this quantity is typically in the same order of magnitude as the number of cliques.