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.
Introduction
In multivariate statistics, understanding the conditional independence structure of variables is fundamental to modeling complex systems. Traditionally, this is achieved through graphical models where nodes represent variables and edges represent dependencies. However, standard graphical models face significant limitations: the combinatorial explosion of the search space as the number of variables $p$ increases, the restriction to pairwise interactions, and a frequent reliance on "decomposability" (the absence of chordless cycles of length $\ge 4$) for computational efficiency.
This paper proposes a paradigm shift: representing the dependency structure of a hypergraph through the geometry of points in $d$-dimensional Euclidean space. By transforming a discrete combinatorial problem into a continuous spatial modeling problem, we provide a flexible framework for Bayesian structural inference that naturally captures higher-order interactions and non-decomposable structures.
The Geometric Nerve Construction
The core of this approach is the mapping of $p$ variables to $p$ points in $\mathbb{R}^d$. The dependency structure is induced by the geometry of these points using the concept of a nerve from computational topology.
By placing a ball of radius $r$ around each point, the intersections of these balls define the hypergraph:
- Edges: Formed when the balls of two points intersect.
- Higher-order Simplices (Hyperedges): Formed when three or more balls intersect simultaneously.
The authors utilize different nerve constructions, such as the Čech complex, which is based strictly on ball intersections, and the Alpha complex, which intersects these balls with Voronoi cells to provide more refined control over clique sizes. This geometric mapping ensures that the number of parameters scales linearly ($O(p \times d)$) rather than quadratically ($O(p^2)$), offering a significant advantage in high-dimensional settings.
Bayesian Inference and Spatial Priors
To perform structural inference, the framework places a prior distribution on the positions of the points in $\mathbb{R}^d$. By choosing specific spatial processes, researchers can exert intuitive control over the resulting graph features:
- Uniform Priors: Points are drawn uniformly, providing a baseline distribution.
- Repulsive Processes: Using models like the Matern III or Strauss process, one can penalize the proximity of points, effectively encouraging sparsity or penalizing the formation of large cliques.
Posterior sampling is conducted via a specialized Metropolis-Hastings Markov chain Monte Carlo (MCMC) algorithm. This algorithm employs local moves (small diffusion-like perturbations of point positions) to refine the structure and global moves (jumping a point to a new random location) to ensure the sampler can escape local optima and explore the graph space effectively.
Experimental Results
The methodology was evaluated against state-of-the-art benchmarks, including FINCS (Feature Inclusion Stochastic Search) and adaptive LASSO, across several datasets:
Simulated Data
Using Clayton copula models and Gaussian graphical models, the geometric approach (labeled "Bayes") consistently outperformed benchmarks in recovering known structures. Specifically, it incurred lower normalized errors when counting complex subgraphs like triangles and 4-cycles, demonstrating superior structural fidelity.
Real-World Applications
- Fisher’s Iris Data: The method successfully captured the known relationships between sepal and petal dimensions in this classic four-variable dataset.
- Daily Exchange Rates: Analyzing eight major currencies relative to the US Dollar (2011–2014), the model identified non-decomposable structures. Traditional junction-tree methods often fail here, either missing these dependencies or forcing them into decomposable approximations that do not reflect the true underlying data generating process.
Discussion and Scalability
The geometric representation offers a bridge between continuous spatial statistics and discrete graph theory. While the method demonstrates strong performance, it faces challenges regarding the calculation of normalizing constants for non-decomposable graphs, which requires computationally intensive Monte Carlo importance sampling. Additionally, the choice of dimension $d$ and radius $r$ constrains the reachable graph space; while $d=2$ or $d=3$ is often sufficient, highly complex graphs may require higher dimensions.
In terms of scalability, the approach successfully handled up to 400 variables. While the computational time increases with $p$ (from minutes to several days), the linear parameter growth provides a more sustainable path for high-dimensional inference than traditional adjacency-matrix-based methods. Future work aims to extend this framework to Directed Acyclic Graphs (DAGs) and non-parametric vertex priors.
Summary updated