Latent Space Modelling of Hypergraph Data

Kathryn Turnbull, Simón Lunagómez, Christopher Nemeth, Edoardo M. Airoldi

Abstract: The increasing prevalence of relational data describing interactions among a target population has motivated a wide literature on statistical network analysis. In many applications, interactions may involve more than two members of the population and this data is more appropriately represented by a hypergraph. In this paper, we present a model for hypergraph data which extends the well established latent space approach for graphs and, by drawing a connection to constructs from computational topology, we develop a model whose likelihood is inexpensive to compute. A delayed-acceptance MCMC scheme is proposed to obtain posterior samples and we rely on Bookstein coordinates to remove the identifiability issues associated with the latent representation. We theoretically examine the degree distribution of hypergraphs generated under our framework and, through simulation, we investigate the flexibility of our model and consider estimation of predictive distributions. Finally, we explore the application of our model to two real-world datasets.

Introduction

Traditional network analysis focuses on pairwise connections, typically represented as graphs. However, many real-world interactions involve groups of three or more—such as multiple authors collaborating on a single paper or several items purchased in one transaction. These higher-order interactions are best represented as hypergraphs.

Different representations of hypergraph data: the hypergraph itself (left), its 1-skeleton graph (middle), and its bipartite representation (right).

While latent space models—where nodes are placed in a hidden geometric space and proximity dictates connection probability—are highly successful for standard graphs, extending them to hypergraphs is notoriously difficult. Strict geometric rules (e.g., a group interacts only if all their latent spheres overlap) lead to binary likelihoods that make standard Bayesian inference like MCMC impossible. Furthermore, existing models often restrict data to "simplicial complexes," which are too rigid for the messy reality of real-world interaction patterns.

Methodology

This paper introduces a novel generative model for hypergraphs that overcomes these hurdles using several key techniques:

  • Čech Complexes & $k$-skeletons: Borrowing from computational topology, the model places nodes in a latent Euclidean space. A hyperedge of size $k$ is formed if the spheres of radius $r_k$ around those $k$ nodes share a common intersection.
  • Non-Simplicial Flexibility: By allowing the radius $r_k$ to vary depending on the size of the group, the model can generate arbitrary, non-simplicial interaction patterns.
  • Noise Injection: To resolve the "binary likelihood" problem, the authors introduce a noise parameter. The model takes the deterministic geometric hypergraph and randomly flips the presence or absence of hyperedges with a small probability, softening the likelihood for MCMC exploration.
  • Bookstein Coordinates: To address non-identifiability issues (where the network remains unchanged under rotation or translation of the latent space), the authors adapt "Bookstein coordinates" from shape analysis to anchor the space.
  • Delayed-Acceptance MCMC: Calculating higher-order geometric intersections is computationally intensive. The authors employ a delayed-acceptance scheme that evaluates cheaper, lower-order connections first, rejecting poor proposals before performing complex higher-order calculations.

Experimental Setup

The model was evaluated using three primary data sources:

  1. Simulated Data: Used to test flexibility, scalability, and robustness against baseline models.
  2. Grocery Items: A real-world dataset subset ($N=40$ item categories, maximum hyperedge size $K=6$).
  3. Coauthorship for Statisticians: An academic collaboration dataset from DBLP ($N=99$ authors, maximum hyperedge size $K=4$).

Key Results and Insights

The integration of topological concepts like the Čech complex provides a mathematically rigorous way to define multi-way ties. A crucial insight is the "noise trick," which bridges the gap between rigid topological constructs and noisy statistical data.

Key findings include:

  • Superior Flexibility: Simulations showed the model captured complex motif counts and higher-order transitivity significantly better than baseline uniform or latent-class models.
  • Computational Efficiency: The Delayed-Acceptance MCMC scheme yielded notable speedups, with relative efficiency improving as the number of nodes ($N$) increased.
  • Strong Predictive Performance: On both the Grocery and Coauthorship datasets, the model accurately predicted degree distributions and motif counts for held-out nodes, showing near-zero discrepancy from ground truth.

Limitations and Future Work

Despite the improvements, computing the Čech complex remains expensive, limiting the model to relatively small networks. The Euclidean latent space also imposes structural limits on certain motifs, such as the number of leaves in a star pattern.

Future research directions include exploring likelihood approximations, variational inference, or more computationally friendly constructs like the Vietoris-Rips complex. The authors also suggest extending the model to non-Euclidean embeddings (e.g., hyperbolic), node-specific radii, and the integration of node covariates.

Summary updated

Abstract

The increasing prevalence of relational data describing interactions among a target population has motivated a wide literature on statistical network analysis. In many applications, interactions may involve more than two members of the population and this data is more appropriately represented by a hypergraph. In this paper, we present a model for hypergraph data which extends the well established latent space approach for graphs and, by drawing a connection to constructs from computational topology, we develop a model whose likelihood is inexpensive to compute. A delayed-acceptance MCMC scheme is proposed to obtain posterior samples and we rely on Bookstein coordinates to remove the identifiability issues associated with the latent representation. We theoretically examine the degree distribution of hypergraphs generated under our framework and, through simulation, we investigate the flexibility of our model and consider estimation of predictive distributions. Finally, we explore the application of our model to two real-world datasets.
BibTeX
@article{turnbull2023latent,
  author = {Kathryn Turnbull and Simón Lunagómez and Christopher Nemeth and Edoardo M. Airoldi},
  title = {{Latent Space Modelling of Hypergraph Data}},
  journal = {Journal of the American Statistical Association},
  year = {2023},
  doi = {10.1080/01621459.2023.2270750},
}
Figure