On the Learning and Learnability of Quasimetrics

Tongzhou Wang, Phillip Isola

Introduction

Our world is full of asymmetries. Gravity and wind can make reaching a place easier than coming back. Social artifacts such as genealogy charts and citation graphs are inherently directed. In reinforcement learning and control, optimal goal-reaching strategies are rarely reversible. Distance functions supported on these asymmetrical structures are called quasimetrics. Despite their common appearance, standard machine learning models struggle to learn them. This paper introduces Poisson Quasimetric Embedding (PQE), a novel, theoretically grounded framework for learning asymmetric distances that significantly improves performance in graph learning and reinforcement learning.

The Challenge of Asymmetric Distances

In the real world, distance is rarely symmetric. It’s easier to walk downhill than uphill; you might follow a celebrity on social media, but they likely don't follow you back. While standard "metric learning" (which assumes symmetry) is well-studied, learning quasimetrics is much harder.

Examples of quasimetrics versus standard metrics, highlighting the asymmetry in real-world scenarios like gravity and directed graphs.

A major gap exists: common machine learning models, like standard Multi-Layer Perceptrons (MLPs), often fail to respect the fundamental constraints of a quasimetric—specifically the triangle inequality ($d(x, z) \leq d(x, y) + d(y, z)$). Because these models treat a pair of points $(x, y)$ as a generic concatenated vector, they lack the structural prior needed to understand how distances should "chain" together. This leads to poor generalization and "illegal" distance predictions.

Poisson Quasimetric Embedding (PQE)

The core contribution of the paper is the Poisson Quasimetric Embedding (PQE). Instead of directly predicting a scalar distance, PQE maps data points into a latent space where distances are defined through the lens of Poisson processes.

  • The "Race" Intuition: Imagine two independent Poisson processes (randomly occurring events). The distance between two points is derived from the probability that one process "wins a race" against the other.
  • Differentiability: While counting events is discrete, the probability of one count being less than another is a smooth, differentiable function. This allows PQE to be trained using standard gradient descent.
  • Universality: The authors prove that PQE is a "universal approximator" for quasimetrics. Given a powerful enough encoder (like a deep neural network), it can represent any valid quasimetric.
  • Two Flavors: They propose PQE-LH (using simple Lebesgue measures on half-lines) and PQE-GG (a more robust version using Gaussian-based measures and shapes) to handle different data complexities.

Key Insights: The Failure of Unconstrained Networks

The authors provide a rigorous proof that a wide class of algorithms (including standard MLPs) will inevitably fail on certain quasimetric tasks. Because these models are equivariant to certain transformations, they cannot distinguish between different valid constraint ranges for a missing edge, often predicting values that violate the triangle inequality.

A simple directed graph demonstrating how unconstrained models can fail to respect the triangle inequality when predicting unseen edges.

By forcing the model to embed data into a space that must be a quasimetric by construction, the model gains a powerful inductive bias. It doesn't have to "learn" the triangle inequality; it's baked into the math. Furthermore, unlike Gaussian processes, which break differentiability when you try to use them for "less-than" comparisons at the same point, Poisson processes maintain smoothness. This makes them uniquely suited for building differentiable quasimetric spaces.

Experimental Validation

The authors evaluated their method across three distinct domains, demonstrating superior generalization and efficiency:

  1. Synthetic Random Directed Graphs: Tested on 300-node graphs with different structures to see how well models recover shortest-path distances. PQE significantly outperformed MLPs and other baselines. In sparse graphs, where MLPs often failed completely to generalize to unseen pairs, PQE maintained low error rates.
  2. Large-Scale Social Graphs: Using the Berkeley-Stanford Web Graph (685k nodes, 7.6M edges), PQE-LH achieved the best performance in predicting discounted distances, accurately identifying unreachable pairs (infinite distance) where other models struggled.
  3. Gridworld with One-Way Doors: A custom reinforcement learning environment where certain paths are irreversible. Using PQE as the structural backbone for a Q-function allowed the agent to reach near-perfect success rates with significantly less data than standard unconstrained Q-learning.

Limitations and Future Work

While the theoretical failure of MLPs is a "worst-case" proof, MLPs sometimes work "well enough" in practice. The authors suggest that an average-case analysis could help explain this discrepancy. Additionally, while more robust, the Gaussian-based PQE-GG involves more complex math and implementation details compared to the simpler PQE-LH. Looking forward, the authors suggest that this framework could be extended to other fields like causal discovery (where relationships are inherently directed) and more complex hierarchical representation learning.

Summary updated

Abstract

Our world is full of asymmetries. Gravity and wind can make reaching a place easier than coming back. Social artifacts such as genealogy charts and citation graphs are inherently directed. In reinforcement learning and control, optimal goal-reaching strategies are rarely reversible (symmetrical). Distance functions supported on these asymmetrical structures are called quasimetrics. Despite their common appearance, little research has been done on the learning of quasimetrics. Our theoretical analysis reveals that a common class of learning algorithms, including unconstrained multilayer perceptrons (MLPs), provably fails to learn a quasimetric consistent with training data. In contrast, our proposed Poisson Quasimetric Embedding (PQE) is the first quasimetric learning formulation that both is learnable with gradient-based optimization and enjoys strong performance guarantees. Experiments on random graphs, social graphs, and offline Q-learning demonstrate its effectiveness over many common baselines.
BibTeX
@inproceedings{wang2022learning,
  author = {Tongzhou Wang and Phillip Isola},
  title = {{On the Learning and Learnability of Quasimetrics}},
  booktitle = {International Conference on Learning Representations},
  year = {2022},
  url = {https://openreview.net/forum?id=z-L3_lhZe9i},
}
Figure