Bayesian Hyperbolic Multidimensional Scaling

Bolun Liu, Shane Lubold, Adrian E. Raftery, Tyler H. McCormick

TL;DR

This paper introduces Bayesian Hyperbolic Multidimensional Scaling (BHMDS), a novel framework for embedding high-dimensional, hierarchical data into low-dimensional hyperbolic space. By combining non-Euclidean geometry with a Bayesian approach, the authors provide a method that not only captures tree-like structures more accurately than standard Euclidean models but also quantifies the uncertainty and measurement noise inherent in real-world datasets.

What Problem Does This Paper Address?

Multidimensional Scaling (MDS) is a staple of data science used to visualize high-dimensional "dissimilarities" (like distances or correlations) in a simple 2D or 3D map. However, standard MDS faces two major hurdles:

  1. The Geometry Gap: Most MDS methods use Euclidean space. But many datasets—like social networks, linguistic hierarchies, or genetic lineages—are "tree-like." Euclidean space doesn't have enough "room" to represent the exponential growth of branches in a tree without massive distortion.
  2. The Uncertainty Gap: Real-world data is noisy. Traditional frequentist MDS methods provide a single "best" map but offer no way to tell if a specific point’s position is a rock-solid fact or a lucky guess based on noisy input.

The authors tackle these by moving the map to hyperbolic space (which naturally fits trees) and using a Bayesian framework to provide rigorous error bars (uncertainty quantification).

Methods

The authors represent data using the Lorentz (Hyperboloid) model of hyperbolic geometry. Their approach includes several technical innovations:

  • Hyperbolic Wrapped Normal Prior: To make the math tractable, they use a "wrapped" normal distribution. This allows them to sample in a standard flat space ($\mathbb{R}^p$) and then project those samples onto the curved hyperbolic manifold. This reparameterization makes their Markov Chain Monte Carlo (MCMC) sampler much more efficient.
  • Truncated Normal Likelihood: Since observed distances must be positive, they model the noise using a truncated normal distribution, ensuring the statistical model respects physical reality.
  • Case-Control Likelihood Approximation: This is the "speed boost" of the paper. Standard Bayesian MDS is computationally expensive ($O(n^2)$), making it slow for large datasets. The authors borrow a trick from epidemiology: they treat similar items as "cases" (calculated exactly) and dissimilar items as "controls" (randomly sampled). This reduces the computational complexity to $O(n)$, allowing the model to scale to thousands of observations.

Datasets

The researchers evaluated BHMDS against a mix of synthetic simulations and classic real-world benchmarks:

  • Social Networks: Zachary’s Karate Club and an Indian village financial borrowing network.
  • Biology: A phylogenetic tree of mosses and a massive global human gene expression map (5,372 samples).
  • Linguistics/NLP: The WordNet mammals subtree (a hierarchy of "is-a" relationships).
  • Academic Networks: A CS Ph.D. advisor-advisee network.

Key Insights and Ideas

  • Hyperbolic "Pseudotime": In the gene expression study, the authors found that the distance from a cell's position to the hyperbolic origin correlates with its level of differentiation. Less specialized cells (like stem cells) sit near the center, while highly specialized cells move toward the edges. This provides a geometric way to measure "evolutionary pseudotime."
  • Don't Over-interpret the Map: In the Indian village network, BHMDS showed that while some households appear more "central" than others, their confidence intervals (credible intervals) often overlap. This is a crucial "aha moment": it warns researchers not to claim one person is more influential than another if the data's noise makes them statistically indistinguishable.
  • The Power of $O(n)$: The case-control approximation allowed the authors to process the WordNet dataset (1,141 nodes) in half the time of the full model with almost no loss in accuracy.

Key Results

  • Superior Fit: BHMDS consistently matched or outperformed state-of-the-art frequentist methods (like hydraPlus) and Euclidean methods in terms of "stress" (how well the map preserves original distances) and "distortion."
  • Robustness: In simulations, the Bayesian model proved much more resilient to high levels of measurement noise compared to frequentist alternatives.
  • Uncertainty Quantification: Unlike previous hyperbolic MDS tools, BHMDS provides a full posterior distribution, allowing users to see "fuzzy" regions on the map where data is less certain.

Limitations and Future Work

  • Dimensionality Selection: The authors primarily used 2D or 5D embeddings for visualization. They suggest that future work could develop an automated "information criterion" to help users choose the optimal number of dimensions.
  • Non-Metric MDS: The current model assumes a linear relationship between true distances and observed noise. The authors noted that extending this to "non-metric" MDS (which only cares about the rank of distances) would be a valuable next step.
  • Constant Curvature: The model assumes the hyperbolic space has a constant negative curvature ($\kappa$). Exploring manifolds with varying curvature might allow for even more flexible embeddings of complex data.

Summary updated

Abstract

Multidimensional scaling (MDS) is a widely used approach to representing high-dimensional, dependent data. MDS works by assigning each observation a location on a low-dimensional geometric manifold, with distance on the manifold representing similarity. We propose a Bayesian approach to multidimensional scaling when the low-dimensional manifold is hyperbolic. Using hyperbolic space facilitates representing tree-like structures common in many settings (e.g. text or genetic data with hierarchical structure). A Bayesian approach provides regularization that minimizes the impact of measurement error in the observed data and assesses uncertainty. We also propose a case-control likelihood approximation that allows for efficient sampling from the posterior distribution in larger data settings, reducing computational complexity from approximately $O(n^2)$ to $O(n)$. We evaluate the proposed method against state-of-the-art alternatives using simulations, canonical reference datasets, Indian village network data, and human gene expression data.
BibTeX
@article{liu2022bayesian,
  author = {Bolun Liu and Shane Lubold and Adrian E. Raftery and Tyler H. McCormick},
  title = {{Bayesian Hyperbolic Multidimensional Scaling}},
  journal = {Journal of Computational and Graphical Statistics},
  year = {2022},
}
Figure