Improved Representation of Asymmetrical Distances with Interval Quasimetric Embeddings

Tongzhou Wang, Phillip Isola

TL;DR

This paper introduces Interval Quasimetric Embeddings (IQE), a novel framework for learning asymmetrical distances (quasimetrics) that strictly obey the triangle inequality. By representing distances as the size of unions of intervals on the real line, IQE achieves universal approximation with minimal parameters and superior optimization stability, significantly outperforming prior methods in graph modeling and reinforcement learning.

What Problem Does This Paper Address?

In the real world, the "distance" from point A to B is rarely the same as B to A. Think of navigating one-way streets, hiking up a steep hill versus down, or the irreversible flow of time and entropy. In machine learning, these asymmetrical structures are called quasimetrics. They are essential for tasks like reinforcement learning (where the "cost-to-go" between states is rarely symmetric) and causal inference.

While several models exist to learn these structures, the authors identify a "four-way" struggle. A perfect quasimetric model should:

  1. Satisfy Quasimetric Constraints: Strictly obey the triangle inequality ($d(x,z) \leq d(x,y) + d(y,z)$) and identity ($d(x,x)=0$).
  2. Universal Approximation: Be able to represent any valid quasimetric structure.
  3. Low Parameter Count: Keep the distance "head" simple so the encoder learns a rich latent space.
  4. Latent Positive Homogeneity: Ensure that scaling the latent vectors scales the distance linearly ($d(\alpha z_x, \alpha z_y) = \alpha d(z_x, z_y)$), which prevents vanishing gradients during training.

Prior works like Poisson Quasimetric Embeddings (PQE) or Deep Norm fail on at least one of these counts—often suffering from optimization issues or requiring massive, complex distance heads that obscure the latent representation.

Methods

The authors propose Interval Quasimetric Embedding (IQE). The core idea is elegant: represent the distance between two latent vectors $u$ and $v$ as the total length (Lebesgue measure) of a union of intervals.

Specifically, for latent vectors reshaped into matrices, an IQE component $d_i(u, v)$ is defined as the size of the set formed by the union of intervals $[u_{ij}, \max(u_{ij}, v_{ij})]$.

Visualizing how IQE computes distances from latent intervals.

This construction naturally satisfies the triangle inequality. The authors propose two versions:

  • IQE-sum: A simple summation of components.
  • IQE-maxmean: A weighted combination of the maximum and the mean of components, which provides a more "conservative" distance estimate useful in offline reinforcement learning.

Crucially, IQE is positively homogeneous. Unlike PQE, which uses sigmoid-like saturating functions, IQE scales linearly. This prevents the "diminishing gradient" problem shown in Figure 1, where IQE maintains a steady slope while other methods flatten out.

Comparison of latent quasimetrics. IQE (d) shows linear scaling and zero parameters in the head compared to the saturating or parameter-heavy baselines (a-c).

Datasets

The authors evaluated IQE across three distinct domains:

  1. Large-Scale Social Graph: The Berkeley-Stanford Web Graph (685k nodes, 7.6M directed edges).
  2. Random Graphs: Three synthetic benchmarks—Dense, Sparse, and Sparse with Block Structure—designed to test generalization (Figure 6).
  3. Offline Q-Learning: A grid-world environment with one-way doors, where the model must learn the "cost-to-go" to reach goals from limited trajectory data.

Key Insights and Ideas

  • The Power of Homogeneity: The authors argue that positive homogeneity is a "hidden" requirement for successful deep learning of distances. It relates latent magnitudes directly to distances, making the optimization landscape much friendlier for standard optimizers like Adam.
  • Head vs. Encoder: By using a distance head with zero (IQE-sum) or one (IQE-maxmean) trainable parameter, IQE forces the neural encoder to do all the heavy lifting. This results in a latent space that is more informative and easier for downstream tasks to utilize.
  • Theoretical Breakthrough: The paper provides the first proof that Deep Norm and Wide Norm are universal approximators, while also proving that IQE-maxmean can exactly represent any finite quasimetric.

Key Results

IQE demonstrated significant gains in both accuracy and efficiency:

  • Graph Modeling: On the massive Berkeley-Stanford graph, IQE-sum achieved a 61% improvement in Mean Squared Error (MSE) and a 16% improvement in $\ell_1$ error over the previous state-of-the-art.
  • Sample Efficiency in RL: In offline Q-learning, IQE-maxmean reached high success rates with far fewer training trajectories than unconstrained networks. It proved more robust than other quasimetric baselines, likely because the max operation encourages "conservative" distance estimates that prevent the agent from overestimating its ability to reach a goal.
Offline Q-learning results. IQE-maxmean (solid red) achieves higher success rates with fewer trajectories than baselines.

Limitations and Future Work

While IQE is highly effective, the authors note that the choice of hyperparameters $k$ (number of components) and $l$ (size of each component) affects performance. As seen in Figure 3, there is a trade-off: larger component sizes generally improve generalization, but the optimal balance depends on the specific graph structure.

Future work could involve automatically tuning these dimensions or applying IQE to more complex, high-dimensional control tasks and causal discovery where asymmetry is a fundamental feature of the data.

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