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:
- Satisfy Quasimetric Constraints: Strictly obey the triangle inequality ($d(x,z) \leq d(x,y) + d(y,z)$) and identity ($d(x,x)=0$).
- Universal Approximation: Be able to represent any valid quasimetric structure.
- Low Parameter Count: Keep the distance "head" simple so the encoder learns a rich latent space.
- 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})]$.
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.
Datasets
The authors evaluated IQE across three distinct domains:
- Large-Scale Social Graph: The Berkeley-Stanford Web Graph (685k nodes, 7.6M directed edges).
- Random Graphs: Three synthetic benchmarks—Dense, Sparse, and Sparse with Block Structure—designed to test generalization (Figure 6).
- 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
maxoperation encourages "conservative" distance estimates that prevent the agent from overestimating its ability to reach a goal.
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