Improved Representation of Asymmetrical Distances with Interval Quasimetric Embeddings

Tongzhou Wang, Phillip Isola

Introduction

In machine learning, distance is typically treated as a symmetric metric: if point A is five units from point B, the reverse is also true. However, many real-world scenarios—from navigating one-way streets and uphill paths to social media influence and game state transitions—are inherently asymmetrical. These structures are known as quasimetrics. While they satisfy the triangle inequality, they discard the requirement of symmetry.

Tongzhou Wang and Phillip Isola from MIT CSAIL introduce Interval Quasimetric Embeddings (IQE), a novel framework that embeds this asymmetry directly into neural representations while satisfying critical mathematical properties that previous models lacked.

The Challenge of Asymmetry

Existing "latent quasimetric" models often struggle with one or more of four essential criteria:

  1. Quasimetric Constraints: Strict adherence to the triangle inequality.
  2. Universal Approximation: The ability to represent any possible quasimetric.
  3. Parameter Efficiency: Keeping the "distance head" simple to avoid obscuring the latent space.
  4. Latent Positive Homogeneity: Ensuring that scaling latent vectors by a factor $\alpha$ scales the predicted distance by the same factor.

Previous methods like Poisson Quasimetric Embedding (PQE) suffer from "diminishing gradients" as distances increase, while models like Deep Norm require massive predictor heads, making them computationally expensive and less interpretable.

Interval Quasimetric Embeddings (IQE)

IQE represents distance as the Lebesgue measure (size) of a union of intervals on the real line. For any two points $u$ and $v$ mapped to sets of intervals, the distance from $u$ to $v$ is determined by how much $u$'s intervals must "stretch" to cover $v$'s.

Specifically, an IQE component is defined as: $$d_i(u, v) = \left| \bigcup_{j=1}^l [u_{ij}, \max(u_{ij}, v_{ij})] \right|$$

The authors propose two variants: IQE-sum for graph data and IQE-maxmean, which provides a universal approximation guarantee.

Comparison of quasimetric models showing IQE's positive homogeneity and parameter efficiency.

Key Insights and Results

A core advantage of IQE is its positive homogeneity. As shown in the comparison above, IQE avoids the vanishing gradient problems of PQE by maintaining a linear relationship between latent scale and distance. Furthermore, IQE shifts the model's "intelligence" into the encoder. Since the distance head has zero or near-zero trainable parameters, the resulting latent space is highly interpretable.

The authors evaluated IQE across several domains:

  • Web Graph Modeling: On the Berkeley-Stanford Web Graph, IQE-sum outperformed PQE by 61% in Mean Squared Error (MSE) and showed a 16% improvement in $\ell_1$ error.
  • Reinforcement Learning: In grid-world tasks with one-way constraints, IQE-maxmean demonstrated superior sample efficiency, reaching high success rates with fewer training trajectories than unconstrained baselines.
  • Efficiency: IQE models achieved state-of-the-art results while using significantly fewer parameters—over 12,000 fewer in the distance head compared to baselines like Deep Norm.

Conclusion

Interval Quasimetric Embeddings provide a mathematically robust and efficient way to model asymmetrical relationships. By satisfying universal approximation and positive homogeneity with minimal parameters, IQE offers a powerful tool for tasks ranging from large-scale graph analysis to offline reinforcement learning. Future applications may include discovering hierarchical structures in natural language or navigating complex, high-dimensional environments.

Summary updated

Abstract

Asymmetrical distance structures (quasimetrics) are ubiquitous in our lives and are gaining more attention in machine learning applications. Imposing such quasimetric structures in model representations has been shown to improve many tasks, including reinforcement learning (RL) and causal relation learning. In this work, we present four desirable properties in such quasimetric models, and show how prior works fail at them. We propose Interval Quasimetric Embedding (IQE), which is designed to satisfy all four criteria. On three quasimetric learning experiments, IQEs show strong approximation and generalization abilities, leading to better performance and improved efficiency over prior methods. Project Page: https://www.tongzhouwang.info/interval_quasimetric_embedding Quasimetric Learning Code Package: https://www.github.com/quasimetric-learning/torch-quasimetric
BibTeX
@inproceedings{wang2022improved,
  author = {Tongzhou Wang and Phillip Isola},
  title = {{Improved Representation of Asymmetrical Distances with Interval Quasimetric Embeddings}},
  booktitle = {NeurReps @ NeurIPS},
  year = {2022},
  url = {https://openreview.net/forum?id=KRiST_rzkGl},
}
Figure