Year: 2021

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. 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 embedding formulation learnable with gradient-based optimization, and enjoys strong performance guarantees. Experiments on random graphs, social graphs, and offline Q-learning demonstrate the effectiveness of our method over common baselines.

heading: 1 INTRODUCTION
text: Learned symmetrical metrics have been proven useful for innumerable tasks including dimensionality reduction (Tenenbaum et al., 2000), clustering (Xing et al., 2002), classification (Weinberger et al., 2006; Hoffer & Ailon, 2015), and information retrieval (Wang et al., 2014). However, the real world is largely asymmetrical, and symmetrical metrics can only capture a small fraction of it.
Generalizing metrics, quasimetrics (Defn. 2.1) allow for asymmetrical distances and can be found in a wide range of domains (see Fig. 1). Ubiquitous physical forces, such as gravity and wind, as well as human-defined rules, such as one-way roads, make the traveling time between places a quasimetric. Furthermore, many of our social artifacts are directed graphs— genealogy charts, follow-relation on Twitter (Leskovec & Krevl, 2014), citation graphs (Price, 2011), hyperlinks over the Internet, etc. Shortest paths on these graphs naturally induce quasimetric spaces. In fact, we can generalize to Markov Decision Processes (MDPs) and observe that optimal goal-reaching plan costs (i.e., universal value/Q-functions (Schaul et al., 2015; Sutton et al., 2011)) always form a quasimetric (Bertsekas & Tsitsiklis, 1991; Tian et al., 2020). Moving onto more abstract structures, quasimetrics can also be found as expected hitting times in Markov chains, and as conditional Shannon entropy H(· | ·) in information theory. (See the appendix for proofs and discussions of these quasimetrics.)
In this work, we study the task of quasimetric learning. Given a sampled training set of pairs and their quasimetric distances, we ask: how well can we learn a quasimetric that fits the training data? We define quasimetric learning in analogy to metric learning: whereas metric learning is the problem of learning a metric function, quasimetric learning is the problem of learning a quasimetric function. This may involve searching over a hypothesis space constrained to only include quasimetric functions (which is what our method does) or it could involve searching for approximately quasimetric functions (we compare to and analyze such approaches). Successful formulations have many potential applications, such as good structural priors in reinforcement learning (Schaul et al., 2015; Tian et al., 2020), graph learning (Rizi et al., 2018) and causal relation learning (Balashankar & Subramanian, 2021).
Towards this goal, our contributions are • We study the quasimetric learning task with two goals: (1) fitting training data well and (2)
respecting quasimetric constraints (Sec. 3); • We prove that a large family of algorithms, including unconstrained networks trained in the
Neural Tangent Kernel (NTK) regime (Jacot et al., 2018), fail at this task, while a learned embedding into a latent quasimetric space can potentially succeed (Sec. 4);
• We propose Poisson Quasimetric Embeddings (PQEs), the first quasimetric embedding formulation learnable with gradient-based optimization, with strong theoretical guarantees (Sec. 5);
• Our experiments complement the theory and demonstrate the benefits of PQEs on random graphs, social graphs and offline Q-learning (Sec. 6).

heading: 2 PRELIMINARIES ON QUASIMETRICS AND POISSON PROCESSES
text: Quasimetric space is a generalization of metric space where all requirements of metrics are satisfied, except that the distances can be asymmetrical.
Definition 2.1 (Quasimetric Space). A quasimetric space is a pair (X , d), where X is a set of points and d : X × X → [0,∞] is the quasimetric, satisfying the following conditions:
∀x, y ∈ X , x = y ⇐⇒ d(x, y) = 0, (Identity of Indiscernibles) ∀x, y, z ∈ X , d(x, y) + d(y, z) ≥ d(x, z). (Triangle Inequality)
Being asymmetric, quasimetrics are often thought of as (shortest-path) distances of some (possibly infinite) weighted directed graph. A natural way to quantify the complexity of a quasimetric is to consider that of its underlying graph. Quasimetric treewidth is an instantiation of this idea.
Definition 2.2 (Treewidth of Quasimetric Spaces (Mémoli et al., 2018)). Consider a quasimetric space M as shortest-path distances on a positively-weighted directed graph. Treewidth of M is the minimum over all such graphs’ treewidths.
Poisson processes are commonly used to model events (or points) randomly occurring across a set A (Kingman, 2005) , e.g., raindrops hitting a windshield, photons captured by a camera. The number of such events within a subset of A is modeled as Poisson distribution, whose mean is given by a measure µ of A that determines how “frequently the events happen at each location”.
Definition 2.3 (Poisson Process). For nonatomic measure µ on set A, a Poisson process on A with mean measure µ is a random countable subset P ⊂ A (i.e., the random events / points) such that
• for any disjoint measurable subsets A1, . . . , An of A, the random variables N(A1), . . . , N(An) are independent, where N(B) , #{P ∩B} is the number of points of P in B, and
• N(B) has the Poisson distribution with mean µ(B), denoted as Pois(µ(B)).
Fact 2.4 (Differentiability of P [N(A1) ≤ N(A2)]). For two measurable subsets A1, A2, P [N(A1) ≤ N(A2)] = P [ Pois(µ(A1 \A2)) ≤ Pois(µ(A2 \A1))︸ ︷︷ ︸
two independent Poissons
] . (1)
Furthermore, for independent X ∼ Pois(µ1), Y ∼ Pois(µ2) is differentiable w.r.t. µ1 and µ2. In the special case where µ1 or µ2 is zero, we can simply compute
P [X ≤ Y ] = { P [0 ≤ Y ] = 1 if µ1 = 0 P [X ≤ 0] = P [X = 0] = e−µ1 if µ2 = 0
(Pois(0) is always 0) = exp ( −(µ1 − µ2)+ ) , (2)
where x+ , max(0, x). In general, this probability and its gradients can be obtained via a connection to noncentral χ2 distribution (Johnson, 1959), which we overview and derive formulas in the appendix.
Therefore, if A1 and A2 are parametrized by some θ such that µ(A1 \ A2) and µ(A2 \ A1) are differentiable w.r.t. θ, so is P [N(A1) ≤ N(A2)].
a b
c
: Train : Test
Triangle inequality =⇒ ? ≤ d(a, b) + d(b, c) = 31 ? ≥ d(a, b)− d(c, b) = 28
0
0
029
2
1
11?
0
20
40
60
80
100
Count
Unconstrained Network (Training MSE = 0.02 ± 0.06)
0 10 20 30
Valid Range
0
20
40
60
80
100
Euclidean Space Embedding (Training MSE = 58.83 ± 0.00)
0 10 20 30
0
20
40
60
80
100
Poisson Quasimetric Embedding (Training MSE = 0.02 ± 0.07)
0 10 20 30
Figure 2: Quasimetric learning on a 3-element space. Leftmost: Training set contains all pairs except for (a, c). Arrow labels show quasimetric distances (rather than edge weights). A quasimetric d̂ should predict d̂(a, c) ∈ [28, 30]. Right three: Different formulations are trained to fit training pairs distances, and then predict on the test pair. Plots show distribution of the prediction over 100 runs.

heading: 3 QUASIMETRIC LEARNING
text: Consider a quasimetric space (X , d). The quasimetric learning task aims to infer a quasimetric from observing a training set {(xi, yi, d(xi, yi))}i ⊂ X × X × [0,∞]. Naturally, our goals for a learned predictor d̂ : X × X → R are: respecting the quasimetric constraints and fitting training distances. Crucially, we are not simply aiming for the usual sense of generalization, i.e., low population error. Knowing that true distances have a quasimetric structure, we can better evaluate predictors and desire ones that fit the training data and are (approximately) quasimetrics. These objectives also indirectly capture generalization because a predictor failing either requirement must have large error on some pairs, whose true distances follow quasimetric constraints. We formalize this relation in Thm. 4.6.

heading: 3.1 LEARNING ALGORITHMS AND MODEL CLASSES
text: Ideally, the learning should scale well with data, potentially generalize to unseen samples, and support integration with other deep learning systems (e.g., via differentiation).
One option is to simply learn a generic function approximator that takes in (x, y) ∈ X × X (as a concatenated input) and outputs a scalar as the prediction of the pair’s distance, or some transformed version of it (e.g., log distance). This approach has been adopted by the community in learning graph distances (Rizi et al., 2018) and plan costs in MDPs (Tian et al., 2020). When the function approximator is a deep neural network, we refer to such formulations as unconstrained (deep neural) networks. While deep networks are known to fit training data well (Jacot et al., 2018), in this paper we also investigate whether they learn to be (approximately) quasimetrics.
Alternatively, we can encode each input to a latent space, where a bivariate function outputs the distance prediction. When the function is a latent metric, we obtain metric embeddings. Our proposed Poisson Quasimetric Embedding (PQE) (specified in Sec. 5) is also of this kind, where the function is a differentiable latent quasimetric that can approximate arbitrary quasimetrics in data space.

heading: 3.2 A TOY EXAMPLE
text: To build up intuition on how various models perform according to our two goals, we consider a toy quasimetric space with only 3 elements in Fig. 2. The space has a total of 9 pairs, from which we use 8 as the training set. Due to quasimetric requirements (esp. triangle inequality), knowing distances of these 8 pairs restricts valid values for the heldout pair to a particular range (which is [28, 31] in this case). If a model approximates 8 training pairs well and respects quasimetric constraints well, its prediction on that heldout pair should fall into this range.
We train three models w.r.t. mean squared error (MSE) over the training set using gradient descent: • Unconstrained deep network that predicts distance, • Metric embedding into a latent Euclidean space with a deep encoder, • Quasimetric embedding into a latent PQE space with a deep encoder (our method).
(Details of Poisson Quasimetric Embedding (PQE) are explained later in Sec. 5.) The three approaches exhibit interesting qualitative differences. Euclidean embedding, unable to model asymmetries in training data, fails to attain a low training error. While both other methods approximate training distances well, unconstrained networks greatly violate quasimetric constraints; only PQEs respect the constraints and consistently predicts within the valid range.
Here, the structural prior of embedding into a quasimetric latent space appears important to successful learning. Without any such prior, unconstrained networks fail badly. In the next section, we present a rigorous theoretical study of the quasimetric learning task, which confirms this intuition.

heading: 4 THEORETICAL ANALYSIS OF VARIOUS LEARNING ALGORITHMS
text: In this section, we define concrete metrics for the two quasimetric learning objectives stated above, and present positive and negative theoretical findings for various learning algorithms.
Overview. Our analysis focuses on data-agnostic bounds, which are often of great interests in machine learning (e.g., VC-dimension (Vapnik & Chervonenkis, 2015)). We prove a strong negative result for a general family of learning algorithms (including unconstrained MLPs trained in NTK regime, k-nearest neighbor, and min-norm linear regression): they can arbitrarily badly fail to fit training data or respect quasimetric constraints (Thm. 4.5). Our informative construction reveals the core reason of their failure. Quasimetric embeddings, however, enjoy nice properties as long as they can approximate arbitrary quasimetrics, which motivates searching for “universal quasimetrics”. The next section presents PQEs as such universal approximators and states their theoretical guarantees.
Assumptions. We consider quasimetric spaces (X , d) with X ⊂ Rd, finite size n = |X| <∞, and finite distances (i.e., d has range [0,∞)). It allows discussing deep networks which can’t handle infinities well. This mild assumption can be satisfied by simply capping max distances in quasimetrics. For training, m < n2 pairs are uniformly sampled as training pairs S ⊂ X × X without replacement. In the appendix, we provide all full proofs, further discussions of our assumptions and presented results, as well as additional results concerning specific learning algorithms and settings.

heading: 4.1 DISTORTION AND VIOLATION METRICS FOR QUASIMETRIC LEARNING
text: We use distortion as a measure of how well the distance is preserved, as is standard in embedding analyses (e.g., Bourgain (1985)). In this work, we especially consider distortion over a subset of pairs, to quantify how well a predictor d̂ approximates distances over the training subset S. Definition 4.1 (Distortion). Distortion of d̂ over a subset of pairs S ⊂ X × X is disS(d̂) ,(
max(x,y)∈S,x 6=y d̂(x,y) d(x,y) )( max(x,y)∈S,x 6=y d(x,y)
d̂(x,y)
) , and its overall distortion is dis(d̂) , disX×X (d̂).
For measuring consistency w.r.t. quasimetric constraints, we define the (quasimetric) violation metric. Violation focuses on triangle inequality, which can often be more complex (e.g., in Fig. 2), compared to the relatively simple non-negativity and Identity of Indiscernibles. Definition 4.2 (Quasimetric Violation). Quasimetric violation (violation for short) of d̂ is vio(d̂) , maxA1,A2,A3∈X d̂(A1,A3)
d̂(A1,A2)+d̂(A2,A3) , where we define 00 = 1 for notation simplicity.
Both distortion and violation are nicely agnostic to scaling. Furthermore, assuming non-negativity and Identity of Indiscernibles, vio(d̂) ≥ 1 always, with equality iff d̂ is a quasimetric. Distortion and violation also capture generalization. Because the true distance d has optimal training distortion (on S) and violation, a predictor d̂ that does badly on either must also be far from truth. Theorem 4.6 (Distortion and Violation Lower-Bound Generalization). For non-negative d̂, we have dis(d̂) ≥ max(disS(d̂), √ vio(d̂)), where dis(d̂) captures generalization over the entire X space.

heading: 4.2 LEARNING ALGORITHMS EQUIVARIANT TO ORTHOGONAL TRANSFORMS
text: For quasimetric space (X , d), X ⊂ Rd, we consider applying general learning algorithms by concatenating pairs to form inputs ∈ R2d (e.g., unconstrained networks). While straightforward, this approach means that the algorithms are generally unable to relate the same element appearing as 1st or 2nd input. As we will show, this is sufficient for a wide family of learning algorithms to fail badly– ones equivariant to orthogonal transforms.
Informally, for an algorithm of this family, training on orthogonally transformed data does not affect its prediction, as long as the test data is also identically transformed. In fact, many standard learning algorithms are equivariant to orthogonal transforms.
Definition 4.3 (Equivariant Learning Algorithms). Given training set D = {(zi, yi)}i ⊂ Z × Y , where zi are inputs and yi are targets, a learning algorithm Alg produces a function Alg(D) : Z → Y such that Alg(D)(z′) is the function’s prediction on sample z′. Consider T a set of transformations Z → Z . Alg is equivariant to T iff for all transform T ∈ T , training set D, Alg(D) = Alg(TD) ◦ T , where TD = {(Tz, y) : (z, y) ∈ D} is the training set with transformed inputs. Lemma 4.4 (Examples of Algorithms Equivariant to Orthogonal Transforms). Algorithms equivariant to orthogonal transforms include k-nearest-neighbor with Euclidean distance, MLP trained with squared loss in NTK regime, and min-norm least-squares linear regression.
Failure case construction. Because these algorithms are unable to relate the same element appearing as 1st or 2nd input and equivariant to transforms on the concatenated input, we can freely transform, say, only 2nd inputs without affecting 1st inputs. Consider the two training sets depicted in Fig. 3, sampled from two different quasimetrics over the same 6 elements: x, z, y, y′, w, w′. With one-hot features, we can apply an orthogonal transform that only exchanges on 2nd input y ↔ y′ and w ↔ w′, leaving the heldout test pair (y, z) unchanged, but transforms the training pairs from one scenario to the other. Given either training set, an orthogonal-transform-equivariant algorithm must attain same training set distortion and predict identically on (y, z). However, with appropriate c, this implies large distortion or violation on one of these cases. In the appendix, we empirically verify that unconstrained MLPs indeed do fail on this construction.
Extending to larger quasimetric spaces, we construct graphs containing many copies of both patterns in Fig. 3. With high probability, our sampled training set fails in the same way—the learning algorithm can not distinguish it from another training set with different quasimetric constraints. Theorem 4.5 (Failure of Algorithms Equivariant to Orthogonal Transforms). Let (fn)n be an arbitrary sequence of large values. There is an infinite sequence of quasimetric spaces ((Xn, dn))n with |Xn| = n, Xn ⊂ Rn such that, over the random training set S of size m, any learning algorithm equivariant to orthogonal transforms must output a predictor d̂ that satisfies
• d̂ fails non-negativity, or • max(disS(d̂), vio(d̂)) ≥ fn (i.e., d̂ approximates training S badly or is far from a quasimetric), with probability 1/2− o(1), as long as S does not contain almost all pairs 1−m/n2 = ω(n−1/3), and does not only include few pairs m/n2 = ω(n−1/2).
Furthermore, standard NTK results show that unconstrained MLPs trained in NTK regime converge to a function with zero training loss. By the above theorem, the limiting function is not a quasimetric with nontrivial probability. In the appendix, we formally state this result. Despite their empirical usages, these results suggest that unconstrained networks are likely not suited for quasimetric learning.
In the appendix, we also discuss potential generalizations of this result to other transforms.

heading: 4.3 QUASIMETRIC EMBEDDINGS
text: A quasimetric embedding consists of a mapping f from data space X to a latent quasimetric space (Z, dz), and predicts d̂(x, y) , dz(f(x), f(y)). Therefore, they always respect all quasimetric constraints and attain optimal violation of value 1, regardless of training data.
However, unlike deep networks, their distortion (approximation) properties depend on the specific latent quasimetrics. If the latent quasimetric can generally approximate any quasimetric (with flexible learned encoders such as deep networks), we have nice guarantees for both distortion and violation.
In the section below, we present Poisson Quasimetric Embedding (PQE) as such a latent quasimetric, along with its theoretical distortion and violation guarantees.

heading: 5 POISSON QUASIMETRIC EMBEDDINGS (PQES)
text: Motivated by above theoretical findings, we aim to find a latent quasimetric space (Rd, dz) with a deep network encoder f : X → Rd, and a quasimetric dz that is both universal and differentiable:
• for any data quasimetric (X , d), there exists an encoder f such that dz(f(x), f(y)) ≈ d(x, y); • dz is differentiable (for optimizing f and possible integration with other gradient-based systems).
Notation 5.1. We use x, y for elements of the data space X , u, v for elements of the latent space Rd, upper-case letters for random variables, and (·)z for indicating functions in latent space (e.g., dz).
An existing line of machine learning research learns quasipartitions, or partial orders, via Order Embeddings (Vendrov et al., 2015). Quasipartitions are in fact special cases of quasimetrics whose distances are restricted to be binary, denoted as π. An Order Embedding is a representation of a quasipartition, where πOE(x, y) = 0 (i.e., x is related to y) iff f(x) ≤ f(y) coordinate-wise:
πOE(x, y) , πOEz (f(x), f(y)) , 1− ∏ j 1f(x)j−f(y)j≤0. (3)
Order Embedding is universal and can model any quasipartition (see appendix and Hiraguchi (1951)).
Can we extend this discrete idea to general continuous quasimetrics? Quite naïvely, one may attempt a straightforward soft modification of Order Embedding:
πSoftOEz (u, v) , 1− ∏ j exp ( − (uj − vj)+ ) = 1− exp ( − ∑ j (uj − vj)+ ) , (4)
which equals 0 if u ≤ v coordinate-wise, and increases to 1 as some coordinates violate this condition more. However, it is unclear whether this gives a quasimetric.
A more principled way is to parametrize a (scaled) distribution of latent quasipartitions Πz , whose expectation naturally gives a continuous-valued quasimetric:
dz(u, v; Πz) , α · Eπz∼Πz [πz(u, v)] , α ≥ 0. (5)
Poisson Quasimetric Embedding (PQE) gives a general recipe for constructing such Πz distributions so that dz is universal and differentiable. Within this framework, we will see that πSoftOEz is actually a quasimetric based on such a distribution and is (almost) sufficient for our needs.

heading: 5.1 DISTRIBUTIONS OF LATENT QUASIPARTITIONS
text: A random latent quasipartition πz : Rd×Rd → {0, 1} is a difficult object to model, due to complicated quasipartition constraints. Fortunately, the Order Embedding representation (Eq. (3)) is without such constraints. If, instead of fixed latents u, v, we have random latents R(u), R(v), we can compute:
Eπz[πz(u, v)] = ER(u),R(v) [ πOEz (R(u), R(v)) ] = 1− P [R(u) ≤ R(v) coordinate-wise] . (6)
In this view, we represent a random πz via a joint distribution of random vectors1 {R(u)}u∈Rd , i.e., a stochastic process. To easily compute the probability of this coordinate-wise event, we assume that each dimension of random vectors is from an independent process, and obtain
Eπz [πz(u, v)] = 1− ∏ j P [Rj(u) ≤ Rj(v)] . (7)
1In general, these random vectors R(u) do not have to be of the same dimension as u ∈ Rd, although the dimensions do match in the PQE variants we experiment with.
The choice of stochastic process is flexible. Using Poisson processes (with Lebesgue mean measure; Defn. 2.3) that count random points on half-lines2 (−∞, a], we can have Rj(u) = Nj((∞, uj ]), the (random) count of events in (∞, uj ] from j-th Poisson process:
Eπz∼Πz [πz(u, v)] = 1− ∏ j P [ Nj((−∞, uj ]) ≤ Nj((−∞, vj ]) ] (8)
= 1− ∏ j exp ( − (uj − vj)+ ) (9)
= πSoftOEz (u, v), (10) where Eq. (9) follows that one half-line is either subset or superset of another, and Fact 2.4. Indeed, πSoftOEz is an expected quasipartition (and thus a quasimetric), and is differentiable.
Considering a mixture of such distributions for expressiveness, the full latent quasimetric formula is dPQE-LHz (u, v;α) , ∑ i αi · ( 1− exp ( − ∑ j (ui,j − vi,j)+ )) , (11) where we slightly abuse notation and consider latents u and v as (reshaped to) 2-dimensional. We will see that this is a special PQE case with Lebesgue measure and half-lines, and thus denoted PQE-LH.

heading: 5.2 GENERAL PQE FORMULATION
text: We can easily generalize the above idea to independent Poisson processes of general mean measures µj and (sub)set parametrizations u→ Aj(u), and obtain an expected quasipartition as: Eπz∼ΠPQEz (µ,A)[πz(u, v)],1− ∏ j P [Nj(Aj(u)) ≤ Nj(Aj(v))] (12)
=1− ∏ j P [ Pois(µj(Aj(u) \Aj(v))︸ ︷︷ ︸
Poisson rate of points landing only inAj(u)
) ≤ Pois(µj(Aj(v) \Aj(u))) ] , (13)
which is differentiable as long as the measures and set parametrizations are (after set differences). Similarly, considering a mixture gives us a latent quasimetric.
A general PQE latent quasimetric is defined with {(µi,j , Ai,j)}i,j and weights αi ≥ 0 as: dPQEz (u, v;µ,A, α) , ∑ i αi · Eπz∼ΠPQEz (µi,Ai) [πz(u, v)] (14)
= ∑ i αi ( 1− ∏ j P [ Pois(µi,j(Ai,j(u) \Ai,j(v))) ≤ Pois(µi,j(Ai,j(v) \Ai,j(u))) ]) ,
whose optimizable parameters include {αi}i, possible ones from {(µi,j , Ai,j)}i,j (and encoder f ). This general recipe can be instantiated in many ways. Setting Ai,j(u)→ (−∞, ui,j ] and Lebesgue µi,j , recovers PQE-LH. In the appendix, we consider a form with Gaussian-based measures and Gaussian-shapes, denoted as PQE-GG. Unlike PQE-LH, PQE-GG always gives nonzero gradients.
The appendix also includes several implementation techniques that empirically improve stability, including learning αi’s with deep linear networks, a formulation that outputs discounted distance, etc.

heading: 5.3 CONTINUOUS-VALUED STOCHASTIC PROCESSES
text: But why Poisson processes over more common choices such as Gaussian processes? It turns out that common continuous-value processes fail to give a differentiable formula.
Consider a non-degenerate process {R(u)}u, where (R(u), R(v)) has bounded density if u 6= v. Perturbing u → u+ δ leaves P [R(u) = R(u+ δ)] = 0. Then one of P [ R(u) ≤ R(u+ δ) ] and
P [ R(u+ δ) ≤ R(u) ] must be far away from 1 (as they sum to 1), breaking differentiability at P [R(u) ≤ R(u)] = 1. This argument is formalized in the appendix. However, discrete-valued stochastic processes, e.g., Poisson process, can leave most probability mass on R(u) = R(u+ δ) and thus remain differentiable.
2Half-lines has Lebesgue measure∞. More rigorously, consider using a small value as the lower bounds of these intervals, which leads to same result.

heading: 5.4 THEORETICAL GUARANTEES
text: Our PQEs bear similarity with the algorithmic quasimetric embedding construction in Mémoli et al. (2018). Extending their analysis to PQEs, we obtain the following distortion and violation guarantees. Theorem 5.2 (Distortion and violation of PQEs). Under the assumptions of Sec. 4, any quasimetric space with size n and treewidth t admits a PQE-LH and a PQE-GG with distortion O(t log2 n) and violation 1, with an expressive encoder (e.g., a ReLU network with ≥ 3 layers and polynomial width).
In fact, these guarantees apply to any PQE formulation that satisfies a mild condition. Informally, any PQE with h×k Poisson processes (i.e., h mixtures) enjoys the above guarantees if it can approximate the discrete counterpart: mixtures of h Order Embeddings, each specified with k dimensions. In the appendix, we make this condition precise and provide a full proof of the above theorem.

heading: 6 EXPERIMENTS
text: Our experiments are designed to (1) confirm our theoretical findings and (2) compare PQEs against a wider range of baselines, across different types of tasks. In all experiments, we optimize γ-discounted distances (with γ ∈ {0.9, 0.95}), and compare the following four families of methods:
• PQEs (2 formulations): PQE-LH and PQE-GG with techniques mentioned in Sec. 5.2. • Unconstrained networks (20 formulations): Predict raw distance (directly, with exp
transform, and with (·)2 transform) or γ-discounted distance (directly, and with a sigmoid-transform). Each variant is run with a possible triangle inequality regularizer Ex,y,z [ max(0, γd̂(x,y)+d̂(y,z) − γd̂(x,z))2 ] for each of 4 weights ∈ {0, 0.3, 1, 3}. • Asymmetrical dot products (20 formulations): On input pair (x, y), encode each into a feature vector with a different network, and take the dot product. Identical to unconstrained networks, the output is used in the same 5 ways, with the same 4 triangle inequality regularizer options. • Metric encoders (4 formulations): Embed into Euclidean space, `1 space, hypersphere with (scaled) spherical distance, or a mixture of all three.
We show average results from 5 runs. The appendix provides experimental details, full results (including standard deviations), additional experiments, and ablation studies.
Random directed graphs. We start with randomly generated directed graphs of 300 nodes, with 64-dimensional node features given by randomly initialized neural networks. After training with MSE on discounted distances, we test the models’ prediction error on the unseen pairs, measured also by MSE on discounted distances. On two graphs with distinct structures, PQEs significantly outperform baselines across almost all training set sizes (see Fig. 4).
Large-scale social graph. We choose the Berkeley-Stanford Web Graph (Leskovec & Krevl, 2014) as the real-wold social graph for evaluation. This graph consists of 685,230 pages as nodes, and 7,600,595 hyperlinks as directed edges. We use 128-dimensional node2vec features (Grover & Leskovec, 2016) and the landmark method (Rizi et al., 2018) to construct a training set of 2,500,000 pairs, and a test set of 150,000 pairs. PQEs generally perform better than other methods, accurately predicting finite distances, and predicting high values for infinite distances (see Table 1).
Offline Q-learning. Optimal goal-reaching plan costs in MDPs are quasimetrics (Bertsekas & Tsitsiklis, 1991; Tian et al., 2020) (see also the appendix). In practice, optimizing deep Q-functions often suffers from stability and sample efficiency issues (Henderson et al., 2018; Fujimoto et al., 2018). As a proof of concept, we use PQEs as goal-conditional Q-functions in offline Q-learning, on the grid-world environment with one-way doors built upon gym-minigrid (Chevalier-Boisvert
Triangle inequality regularizer MSE w.r.t. γ-discounted distances (×10−3) ↓ L1 Error when true d <∞ ↓ Prediction d̂ when true d =∞ ↑
PQE-LH 7 3.043 1.626 69.942 PQE-GG 7 3.909 1.895 101.824
Best Unconstrained Net. 7 3.086 2.115 59.524 3 2.813 2.211 61.371
Best Asym. Dot Product 7 48.106 2.520 ×10 11 2.679 ×1011
3 48.102 2.299 ×1011 2.500 ×1011
Best Metric Embedding 7 17.595 7.540 53.850
Table 1: Quasimetric learning on large-scale web graph. “Best” is selected by test MSE w.r.t. γ-discounted distances. 0 200 400 600 800 1000 Number of Training Trajectories
0.0
0.2
0.4
0.6
0.8
1.0
[s uc
ce ss
]
PQE Unconstrained Network Metric Embedding Asym. Dot Product
Figure 5: Offline Q-learning results.
et al., 2018) (see Fig. 1 right), following the algorithm and data sampling procedure described in (Tian et al., 2020). Adding strong quasimetric structures greatly improves sample efficiency and greedy planning success rates over popular existing approaches such as unconstrained networks used in (Tian et al., 2020) and asymmetrical dot products used in (Schaul et al., 2015) (see Fig. 5). As an interesting observation, some metric embedding formulations work comparably well.

heading: 7 RELATED WORK
text: Metric learning. Metric learning aims to approximate a target metric/similarity function, often via a learned embedding into a metric space. This idea has successful applications in dimensionality reduction (Tenenbaum et al., 2000), information retrieval (Wang et al., 2014), clustering (Xing et al., 2002), classification (Weinberger et al., 2006; Hoffer & Ailon, 2015), etc. While asymmetrical formulations have been explored, they either ignore quasimetric constraints (Oord et al., 2018; Logeswaran & Lee, 2018; Schaul et al., 2015), or are not general enough to approximate arbitrary quasimetric (Balashankar & Subramanian, 2021), which is the focus of the present paper.
Isometric embeddings. Isometric (distance-preserving) embeddings is a highly influential and well-studied topic in mathematics and statistics. Fundamental results, such as Bourgain’s random embedding theorem (Bourgain, 1985), laid important ground work in understanding and constructing (approximately) isometric embeddings. While most such researches concern metric spaces, Mémoli et al. (2018) study an algorithmic construction of a quasimetric embedding via basic blocks called quasipartitions. Their approach requires knowledge of quasimetric distances between all pairs and thus is not suitable for learning. Our formulation takes inspiration from the form of their embedding, but is fully learnable with gradient-based optimization over a training subset.
Quasimetrics and partial orders. Partial orders (quasipartitions) are special cases of quasimetrics (see Sec. 5). A line of machine learning research studies embedding partial order structures into latent spaces for tasks such as relation discovery and information retrieval (Vendrov et al., 2015; Suzuki et al., 2019; Hata et al., 2020; Ganea et al., 2018). Unfortunately, unlike PQEs, such formulations do not straightforwardly generalize to arbitrary quasimetrics, which are more than binary relations.

heading: 8 IMPLICATIONS
text: In this work, we study quasimetric learning via both theoretical analysis and empirical evaluations.
Theoretically, we show strong negative results for a common family of learning algorithms, and positive guarantees for our proposed Poisson Quasimetric Embedding (PQE). Our results introduce the novel concept of equivariant learning algorithms, which may potentially be used for other learnability analyses with algorithms such as deep neural networks. Additionally, a thorough average-case or data-dependent analysis would nicely complement our results, and may shed light on conditions where algorithms like deep networks can learn decent approximations to quasimetrics in practice.
PQEs are the first quasimetric embedding formulation that can be learned via gradient-based optimization. Empirically, PQEs show promising performance in various tasks. Furthermore, PQEs are fully differentiable, and (implicitly) enforce a quasimetric structure in any latent space. They are particularly suited for integration in large deep learning systems, as we explore in the Q-learning experiments. This can potentially open the gate to many practical applications such as better embedding for planning with MDPs, efficient shortest path via learned quasimetric heuristics, representation learning with quasimetric similarities, causal relation learning, etc.

heading: APPENDIX

heading: A Discussions for Sec. 2: Preliminaries on Quasimetrics and Poisson Processes 15
text: A.1 Quasimetric Spaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
A.2 Poisson Processes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

heading: B Proofs, Discussions and Additional Results for Sec. 4: Theoretical Analysis of Various Learning Algorithms 20
text: B.1 Thm. 4.6: Distortion and Violation Lower-Bound Generalization . . . . . . . . . . 20
B.2 Lemma 4.4: Examples of Algorithms Equivariant to Orthogonal Transforms . . . . 21
B.3 Thm. 4.5: Failure of Algorithms Equivariant to Orthogonal Transforms . . . . . . 22

heading: C Proofs and Discussions for Sec. 5: Poisson Quasimetric Embeddings (PQEs) 33
text: C.1 Non-differentiability of Continuous-Valued Stochastic Processes . . . . . . . . . . 33
C.2 PQE-GG: Gaussian-based Measure and Gaussian Shapes . . . . . . . . . . . . . . 34
C.3 Theoretical Guarantees for PQEs . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
C.4 Implementation of Poisson Quasimetric Embeddings (PQEs) . . . . . . . . . . . . 39

heading: D Experiment Settings and Additional Results 42
text: D.1 Experiments from Sec. 3.2: A Toy Example . . . . . . . . . . . . . . . . . . . . . 42
D.2 Experiments from Sec. 6: Experiments . . . . . . . . . . . . . . . . . . . . . . . . 43

heading: A DISCUSSIONS FOR SEC. 2: PRELIMINARIES ON QUASIMETRICS AND POISSON PROCESSES

heading: A.1 QUASIMETRIC SPACES
text: Definition 2.1 (Quasimetric Space). A quasimetric space is a pair (X , d), where X is a set of points and d : X × X → [0,∞] is the quasimetric, satisfying the following conditions:
∀x, y ∈ X , x = y ⇐⇒ d(x, y) = 0, (Identity of Indiscernibles) ∀x, y, z ∈ X , d(x, y) + d(y, z) ≥ d(x, z). (Triangle Inequality)
Definition A.1 (Quasipseudometric Space). As a further generalization, we say (X , d) is a quasipseudometric space if the Identity of Indiscernibles requirement is only satisfied in one direction:
∀x, y ∈ X , x = y =⇒ d(x, y) = 0, (Identity of Indiscernibles) ∀x, y, z ∈ X , d(x, y) + d(y, z) ≥ d(x, z). (Triangle Inequality)

heading: A.1.1 EXAMPLES OF QUASIMETRIC SPACES
text: Proposition A.2 (Expected Hitting Time of a Markov Chain). Let random variables (Xt)t be a Markov Chain with support X . Then (X , dhitting) is a quasimetric space, where
dhitting(s, t) , E [time to hit t | start from s] , (15) where we define the hitting time of s starting from s to be 0.
Proof of Proposition A.2. Obviously dhitting is non-negative. We then verify the following quasimetric space properties:
• Identity of Indiscernibles. By definition, we have, ∀x, y ∈ X , x 6= y, dhitting(x, x) = 0 (16) dhitting(x, y) ≥ 1. (17)
• Triangle Inequality. For any x, y, z ∈ X , we have dhitting(x, y) + dhitting(y, z) = E [time to hit y then hit z | start from x] (18)
≥ E [time to hit z | start from x] (19) = dhitting(x, z). (20)
Hence, (X , dhitting) is a quasimetric space.
Proposition A.3 (Conditional Shannon Entropy). Let X be the set of random variables (of some probability space). Then (X , dH) is a quasipseudometric space, where
dH(X,Y ) , H(Y | X). (21) If for all distinct (X,Y ) ∈ X × X , X can not be written as (almost surely) a deterministic function of Y , then (X , dH) is a quasimetric space.
Proof of Proposition A.3. Obviously dH is non-negative. We then verify the following quasipseudometric space properties:
• Identity of Indiscernibles. By definition, we have, ∀X,Y ∈ X , dH(X,X) = H(X | X) = 0 (22) dH(Y,X) = H(Y | X) ≥ 0, (23)
where ≤ is = iff Y is a (almost surely) deterministic function of X . • Triangle Inequality. For any X,Y, Z ∈ X , we have
dH(X,Y ) + dH(Y, Z) = H(Y | X) +H(Z | Y ) (24) ≥ H(Y | X) +H(Z | XY ) (25) = H(Y Z | X) (26) ≥ H(Z | X) (27) = dH(X,Z). (28)
Hence, (X , dH) is a quasipseudometric space, and a quasimetric space when the last condition is satisfied.
Conditional Kolmogorov Complexity From algorithmic information theory, the conditional Kolmogorov complexity K(y | x) also similarly measures “the bits needed to create y given x as input” (Kolmogorov, 1963). It is also almost a quasimetric, but the exact definition affects some constant/log terms that may make the quasimetric constraints non-exact. For instance, when defined with the prefix-free version, conditional Kolmogorov complexity is always strictly positive, even for K(x | x) > 0 (Li et al., 2008). One may remedy this with a definition using a universal Turing machine (UTM) that simply outputs the input on empty program. But to make triangle inequality work, one needs to reason about how the input and output parts work on the tape(s) of the UTM. Nonetheless, regardless of the definition details, conditional Kolmogorov complexity do satisfy a triangle inequality up to log terms (Grunwald & Vitányi, 2004). So intuitively, it behaves roughly like a quasimetric defined on the space of binary strings.
Optimal Goal-Reaching Plan Costs in Markov Decision Processes (MDPs) We define MDPs in the standard manner:M = (S,A,R,P, γ) (Puterman, 1994), where S is the state space, A is the action space,R : S ×A → R is the reward function, P : S ×A → ∆(S) is the transition function (where ∆(S) is the set of all distributions over S), and γ ∈ (0, 1) is the discount factor. We define Π as the collection of all stationary policies π : S → ∆(A) onM. For a particular policy π ∈ Π, it induces random trajectories:
• Trajectory starting from state s ∈ S is the random variable ξπ(s) = (s1, a1, r1, s2, a2, r2, . . . ), (29)
distributed as s1 = s (30) ai ∼ π(si), ∀i ≥ 1 (31)
si+1 ∼ P(si, ai), ∀i ≥ 1. (32) • Trajectory starting from state-action pair (s, a) ∈ S ×A is the random variable
ξπ(s, a) = (s1, a1, r1, s2, a2, r2, . . . ), (33) distributed as
s1 = s (34) a1 = a (35) ai ∼ π(si), ∀i ≥ 2 (36)
si+1 ∼ P(si, ai), ∀i ≥ 1. (37)
Proposition A.4 (Optimal Goal-Reaching Plan Costs in MDPs). Consider an MDP M = (S,A,R,P, γ). WLOG, assume that R : S × A → (−∞, 0] has only non-positive rewards (i.e., negated costs). Let X = S ∪ (S ×A). Then (X , dsum) and (X , dγ) are quasipseudometric spaces, where dsum(x, y) , min
π∈Π E [total costs from x to y under π] (38)
=  minπ∈Π E(s1,a1,r1,... )=ξπ(x) [ − ∑ t rt 1s′ /∈{si}i∈[t]︸ ︷︷ ︸ not reached s′ yet ] if y = s′ ∈ S︸ ︷︷ ︸ goal is a state , minπ∈Π E(s1,a1,r1,... )=ξπ(x) [ − ∑ t rt 1(s′,a′)/∈{(si,ai)}i∈[t−1]︸ ︷︷ ︸
not reached s′ and performed a′ yet
] if y = (s′, a′) ∈ S ×A︸ ︷︷ ︸
goal is a state-action pair
,
(39) and
dγ(x, y) , logγ max π∈Π
E [ γtotal costs from x to y under π ] (40)
is defined similarly.
If the reward function is always negative, (X , dsum) and (X , dγ) are quasimetric spaces.
Proof of Proposition A.4. Obviously both dsum and dγ are non-negative, and satisfy Identity of Indiscernibles (for quasipseudometric spaces). For triangle inequality, note that for each y, we can instead consider alternative MDPs:
• If y = s′ ∈ S, modify the original MDP to make s′ a sink state, where performing any action yields 0 reward (i.e., 0 cost);
• If y = (s′, a′) ∈ S × A, modify the original MDP such that performing action a′ in state s′ surely transitions to a new sink state, where performing any action yields 0 reward (i.e., 0 cost).
Obviously, both are Markovian. Furthermore, they are Stochastic Shortest Path problems with no negative costs (Guillot & Stauffer, 2020), implying that there are Markovian (i.e., stationary) optimal policies (respectively w.r.t. either minimizing expected total cost or maximizing expected γtotal cost). Thus optimizing over the set of stationary policies, Π, gives the optimal quantity over all possible policies, including concatenation of two stationary policies. Thus the triangle inequality is satisfied by both.
Hence, (X , dsum) and (X , dγ) are quasipseudometric spaces. Finally, if the reward function is always negative, x 6= y =⇒ dsum(x, y) > 0 and dγ(x, y) > 0, so (X , dsum) and (X , dγ) are quasimetric spaces.
Remark A.5. We make a couple remarks: • Any MDP with a bounded reward function can be modified to have only non-positive rewards by
subtracting the maximum reward (or larger);
• We have
dsum(s, (s, a)) = dγ(s, (s, a)) = −R(s, a). (41)
• When the dynamics is deterministic, dsum ≡ dγ , ∀γ ∈ (0, 1). • Unless y is reachable from x with probability 1 under some policy, dsum(x, y) =∞. • Unless y is unreachable from x with probability 1 under all policies, dsum(x, y) <∞. Therefore,
it is often favorable to consider dγ types.
• In certain MDP formulations, the reward is stochastic and/or dependent on the reached next state. The above definitions readily extend to those cases.
• γdγ((s,a),y) is very similar to Q-functions except that Q-function applies discount based on time, and γdγ((s,a),y) applies discount based on costs. We note that a Q-learning-like recurrence can also be found for γdγ((s,a),y).
If the cost is constant in the sense for some fixed c < 0, R(s, a) = c, ∀(s, a) ∈ S × A, then time and cost are equivalent up to a scale. Therefore, γdγ((s,a),y) coincides with the optimal Q-functions for the MDPs described in proof, and γdγ(s,y) coincides with the optimal value functions for the respective MDPs.

heading: A.1.2 QUASIMETRIC TREEWIDTH AND GRAPH TREEWIDTH
text: Definition 2.2 (Treewidth of Quasimetric Spaces (Mémoli et al., 2018)). Consider representations of a quasimetric space M as shortest-path distances on a positively-weighted directed graph. Treewidth of M is the minimum over all such graphs’ treewidths. (Recall that the treewidth of a graph (after replacing directed edges with undirected ones) is a measure of its complexity.)
Graph treewidth is a standard complexity measure of how “similar” a graph is to a tree (Robertson & Seymour, 1984). Informally speaking, if a graph has low treewidth, we can represent it as a tree, preserving all connected paths between vertices, except that in each tree node, we store a small number of vertices (from the original graph) rather than just 1.
Graph treewidth is widely used by the Theoretical Computer Science and Graph Theory communities, since many NP problems are solvable in polynomial time for graphs with bounded treewidth (Bertele & Brioschi, 1973).

heading: A.2 POISSON PROCESSES
text: Definition 2.3 (Poisson Process). For nonatomic measure µ on set A, a Poisson process on A with mean measure µ is a random countable subset P ⊂ A (i.e., the random events / points) such that
• for any disjoint measurable subsets A1, . . . , An of A, the random variables N(A1), . . . , N(An) are independent, where N(B) , #{P ∩B} is the number of points of P in B, and
• N(B) has the Poisson distribution with mean µ(B), denoted as Pois(µ(B)).
Poisson processes are usually used to model events that randomly happens “with no clear pattern”, e.g., visible stars in a patch of the sky, arrival times of Internet packages to a data center. These events may randomly happen all over the sky / time. To an extent, we can say that their characteristic feature is a property of statistical independence (Kingman, 2005).
To understand this, imagine raindrops hitting the windshield of a car. Suppose that we already know that the rain is heavy, knowing the exact pattern of the raindrops hitting on the left side of the windshield tells you little about the hitting pattern on the right side. Then, we may assume that, as long as we look at regions that are disjoint on the windshield, the number of raindrops in each region are independent.
This is the fundamental motivation of Poisson processes. In a sense, from this characterization, Poisson processes are inevitable (see Sec. 1.4 of (Kingman, 2005)).
A.2.1 POISSON RACE PROBABILITY P [Pois(µ1) ≤ Pois(µ2)] AND ITS GRADIENT FORMULAS
In Fact 2.4 we made several remarks on the Poisson race probability, i.e., for independent X ∼ Pois(µ1), Y ∼ Pois(µ2), the quantity P [X ≤ Y ]. In this section, we detailedly describe how we arrived at those conclusions, and provide the exact gradient formulas for differentiating P [X ≤ Y ] w.r.t. µ1 and µ2.
From Skellam distribution CDF to Non-Central χ2 distribution CDF. Distribution of the difference of two independent Poisson random variables is called the Skellam distribution (Skellam, 1946), with its parameter being the rate of the two Poissons. That is, X − Y ∼ Skellam(µ1, µ2). Therefore, P [X ≤ Y ] is essentially the cumulative distribution function (CDF) of this Skellam at 0. In Eq. (4) of (Johnson, 1959), a connection is made between the CDF of Skellam(µ1, µ2) distribution, and the CDF of a non-central χ2 distribution (which is a non-centered generalization of χ2 distribution) with two parameters k > 0 degree(s) of freedom and non-centrality parameter λ ≥ 0): for integer n > 0,
P [Skellam(µ1, µ2) ≥ n] = P [ NonCentralχ2( 2n︸︷︷︸
degree(s) of freedom , 2µ2︸︷︷︸ non-centrality parameter
) < 2µ1 ] , (42)
which can be evaluated using statistical computing packages such as SciPy (Virtanen et al., 2020) and CDFLIB (Burkardt, 2021; Brown et al., 1994).
Marcum-Q-Function and gradient formulas. To differentiate through Eq. (42), we consider representing the non-central χ2 CDF as a Marcum-Q-function (Marcum, 1950). One definition of the Marcum-Q-function QM : R× R→ R in statistics is
QM (a, b) , ∫ ∞ b x (x a )M−1 exp ( −x 2 + a2 2 ) IM−1(ax) dx, (43)
where IM−1 is the modified Bessel function of order M − 1. (When M is non-integer, we refer readers to (Brychkov, 2012; Marcum, 1950) for definitions, which are not relevant to the discussion below.) When used in CDF of non-central χ2, we have
P [ NonCentralχ2(k, λ) < x ] = 1−Q k
2 ( √ λ, √ x). (44)
Combining with Eq. (42), and using the symmetry Skellam(µ1, µ2) d = −Skellam(µ2, µ1), we have, for integer n, P [X ≤ Y + n] = P [Skellam(µ1, µ2) ≤ n] (45)
=
{ P [ NonCentralχ2(−2n, 2µ1) < 2µ2 ] if n < 0
1− P [ NonCentralχ2(2(n+ 1), 2µ2) < 2µ1 ] if n ≥ 0 (46)
=
{ 1−Q−n( √ 2µ1, √
2µ2) if n < 0 Qn+1( √ 2µ2, √ 2µ1) if n ≥ 0. (47)
Prior work (Brychkov, 2012) provides several derivative formula for the Marcum-Q-Function:
• For n < 0, we have ∂
∂µ1 P [X ≤ Y + n] = ∂ ∂µ1
( 1−Q−n( √ 2µ1, √ 2µ2) ) (48)
= Q−n( √ 2µ1, √ 2µ2)−Q−n+1( √ 2µ1, √
2µ2) (Eq. (16) of (Brychkov, 2012))
= − ( µ2 µ1 )−n2 e−(µ1+µ2)I−n(2 √ µ1µ2) (Eq. (2) of (Brychkov, 2012))
= − ( µ2 µ1 )−n2 e−( √ µ1− √ µ2) 2 I (e) −n(2 √ µ1µ2), (49)
where I(e)v (x) , e−|x|Iv(x) is the exponentially-scaled version of Iv that computing libraries often provide due to its superior numerical precision (e.g., SciPy (Virtanen et al., 2020)),
∂ ∂µ2 P [X ≤ Y + n] = ∂ ∂µ2
( 1−Q−n( √ 2µ1, √ 2µ2) ) (50)
= ( µ2 µ1 )−n+12 e−(µ1+µ2)I−n−1(2 √ µ1µ2)
(Eq. (19) of (Brychkov, 2012))
= ( µ2 µ1 )−n+12 e−( √ µ1− √ µ2) 2 I (e) −n−1(2 √ µ1µ2), (51)
• For n ≥ 0, we have ∂
∂µ1 P [X ≤ Y + n] = ∂ ∂µ1 Qn+1(
√ 2µ2, √ 2µ1) (52)
= − ( µ1 µ2 )n e−(µ1+µ2)In(2 √ µ1µ2) (Eq. (19) of (Brychkov, 2012))
= − ( µ1 µ2 )n e−( √ µ1− √ µ2) 2 I(e)n (2 √ µ1µ2), (53)
and, ∂
∂µ2 P [X ≤ Y + n] = ∂ ∂µ2 Qn+1(
√ 2µ2, √ 2µ1) (54)
= Qn+2( √ 2µ2, √ 2µ1)−Qn+1( √ 2µ2, √
2µ1) (Eq. (16) of (Brychkov, 2012))
= ( µ1 µ2 )n+1 2 e−(µ1+µ2)In+1(2 √ µ1µ2) (Eq. (2) of (Brychkov, 2012))
= ( µ1 µ2 )n+1 2 e−( √ µ1− √ µ2) 2 I (e) n+1(2 √ µ1µ2). (55)
Setting n = 0 gives the proper forward and backward formulas for P [X ≤ Y ].

heading: B PROOFS, DISCUSSIONS AND ADDITIONAL RESULTS FOR SEC. 4: THEORETICAL ANALYSIS OF VARIOUS LEARNING ALGORITHMS
text: Assumptions. Recall that we assumed a quasimetric space, which is stronger than a quasipseudometric space (Defn. A.1), with finite distances. These are rather mild assumptions, since any quasipseudometric with infinities can always be modified to obey these assumptions by (1) adding a small metric (e.g., d (x, y) , 1x 6=y with small > 0) and (2) capping the infinite distances to a large value higher than any finite distance.
Worst-case analysis. In this work we focus on the worst-case scenario, as is common in standard (quasi)metric embedding analyses (Bourgain, 1985; Johnson & Lindenstrauss, 1984; Indyk, 2001; Mémoli et al., 2018). Such results are important because embeddings are often used as heuristics in downstream tasks (e.g., planning) which are sensitive to any error. While our negative result readily extends to the average-case scenario (since the error (distortion or violation) is arbitrary), we leave a thorough average-case analyses as future work.
Data-independent bounds. We analyze possible data-independent bounds for various algorithms. In this sense, the positive result for PQEs (Thm. C.4) is really strong, showing good guarantees regardless data quasimetric. The negative result (Thm. 4.5) is also revealing, indicating that a family of algorithms should probably not be used, unless we know something more about data. Dataindependent bounds are often of great interest in machine learning (e.g., concepts of VC-dimension (Vapnik & Chervonenkis, 2015) and PAC learning (Valiant, 1984)). An important future work is to explore data-dependent results, possibly via defining a quasimetric complexity metric that is both friendly for machine learning analysis, and connects well with combinatorics measures such as quasimetric treewidth.
Violation and distortion metrics. The optimal violation has value 1. Specifically, it is 1 iff d̂ is a quasimetric on X (assuming non-negativity). Distortion (over training set) and violation together quantify how well d̂ learns a quasimetric consistent with the training data. A predictor can fit training data well (low distortion), but ignores basic quasimetric constraints on heldout data (high violation). Conversely, a predictor can perfectly obey the training data constraints (low violation), but doesn’t actually fit training data well (high distortion). Indeed, (assuming non-negativity and Identity of Indiscernibles), perfect distortion (value 1) and violation (value 1) imply that d̂ is a quasimetric consistent with training data.
Relation with classical in-distribution generalization studies. Classical generalization studies the prediction error over the underlying data distribution, and often involves complexity of the hypothesis class and/or training data (Vapnik & Chervonenkis, 2015; McAllester, 1999). Our focus on quasimetric constraints violation is, in fact, not an orthogonal problem, but potentially a core part of in-distribution generalization for this setting. Here, the underlying distribution is supported on all pairs of X × X . Indeed, if a learning algorithm has large distortion, it must attain large prediction error on S ⊂ X × X ; if it has large violation, it must violates the quasimetric constraints and necessarily admits bad prediction error on some pairs (whose true distances obey the quasimetric constraints). Thm. 4.6 (proved below) formalizes this idea, where we characterize generalization with the distortion over all possible pairs in X × X .

heading: B.1 THM. 4.6: DISTORTION AND VIOLATION LOWER-BOUND GENERALIZATION
text: Theorem 4.6 (Distortion and Violation Lower-Bound Generalization). For non-negative d̂, we have dis(d̂) ≥ max(disS(d̂), √ vio(d̂)), where dis(d̂) captures generalization over the entire X space.

heading: B.1.1 PROOF
text: Proof of Thm. 4.6. It is obvious that dis(d̂) ≥ disS(d̂). (56)
Therefore, it remains to show that dis(d̂) ≥ √ vio(d̂).
WLOG, say vio(d̂) > 1. Otherwise, the statement is trivially true.
By the definition of violation (see Defn. 4.2), we have, for some x, y, z ∈ X , with d̂(x, z) > 0, d̂(x, z)
d̂(x, y) + d̂(y, z) = vio(d̂). (57)
Since d̂ is non-negative, we can derive d̂(x, z) = vio(d̂) ( d̂(x, y) + d̂(y, z) ) (58)
≥ vio(d̂) dis(d̂)
( d(x, y) + d(y, z) ) (59)
≥ vio(d̂) dis(d̂) d(x, z). (60)
If d(x, z) = 0, then dis(d̂) =∞ and the statement is trivially true. If d(x, z) > 0, above Eq. (60) implies
dis(d̂) ≥ d̂(x, z) d(x, z) ≥ vio(d̂) dis(d̂)
=⇒ dis(d̂) ≥ √ vio(d̂). (61)
Combining Eqs. (56) and (61) gives the desired statement.

heading: B.2 LEMMA 4.4: EXAMPLES OF ALGORITHMS EQUIVARIANT TO ORTHOGONAL TRANSFORMS
text: Lemma 4.4 (Examples of Algorithms Equivariant to Orthogonal Transforms). Algorithms equivariant to orthogonal transforms include k-nearest-neighbor with Euclidean distance, MLP trained with squared loss in NTK regime, and min-norm least-squares linear regression.
Recall the definition of Equivariant Learning Transforms.
Definition 4.3 (Equivariant Learning Algorithms). Given training set D = {(zi, yi)}i ⊂ Z × Y , where zi are inputs and yi are targets, a learning algorithm Alg produces a function Alg(D) : Z → Y such that Alg(D)(z′) is the function’s prediction on sample z′. Consider T a set of transformations Z → Z . Alg is equivariant to T iff for all transform T ∈ T , training set D, Alg(D) = Alg(TD) ◦ T , where TD = {(Tz, y) : (z, y) ∈ D} is the training set with transformed inputs.

heading: B.2.1 PROOF
text: Proof of Lemma 4.4. We consider the three algorithms individually:
• k-nearest neighbor with Euclidean distance.
It is evident that if a learning algorithm only depend on pairwise dot products (or distances), it is equivariant to orthogonal transforms, which preserve dot products (and distances). k-nearestneighbor with Euclidean distance only depends on pairwise distances, which can be written in terms of dot products:
‖x− y‖22 = x Tx+ yTy − 2xTy. (62)
Therefore, it is equivariant to orthogonal transforms.
• Min-norm least-squares linear regression.
Recall that the solution to min-norm least-squares linear regression Ax = b is given by Moore–Penrose pseudo-inverse x = A+b. For any matrix A ∈ Rm×n with SVD UΣV ∗ = A, and T ∈ O(n) (where O(n) is the orthogonal group in dimension n), we have
(ATT)+ = (UΣV ∗TT)+ = TV Σ+U∗ = TA+, (63)
where we used T ∗ = TT for T ∈ O(n). The solution for the transformed data ATT and b is thus
(ATT)+b = TA+b. (64) Thus, for any new data point x̃ ∈ Rn and its transformed version T x̃ ∈ Rn,
(T x̃)T(ATT)+b︸ ︷︷ ︸ transformed problem prediction = x̃TTTTA+ = x̃A+︸︷︷︸ original problem prediction . (65)
Hence, min-norm least-squares linear regression is equivariant to orthogonal transforms.
• MLP trained with squared loss in NTK regime.
We first recall the NTK recursive formula from (Jacot et al., 2018).
Denote the NTK for a MLP with L layers with the scalar kernel Θ(L) : Rd × Rd → R. Let β > 0 be the (fixed) parameter for the bias strength in the network model, and σ be the activation function. Given x, z ∈ Rd, it can be recursively defined as following. For h ∈ [L],
Θ(h)(x, z) , Θ(h−1)(x, z)Σ̇(h)(x, z) + Σ(h)(x, z), (66) where
Σ(0)(x, z) = 1
d xTz + β2, (67)
Λ(h−1)(x, z) = ( Σ(h−1)(x, x) Σ(h−1)(x, z) Σ(h−1)(z, x) Σ(h−1)(z, z) ) , (68)
Σ(h)(x, z) = c · E(u,v)∼N (0,Λ(h−1)) [σ(u)σ(v)] + β2, (69)
Σ̇(h)(x, z) = c · E(u,v)∼N (0,Λ(h−1)) [σ̇(u)σ̇(v)] , (70) for some constant c.
It is evident from the recursive formula, that Θ(h)(x, z) only depends on xTx, zTz and xTz. Therefore, the NTK is invariant to orthogonal transforms.
Furthermore, training an MLP in NTK regime is the same as kernel regression with the NTK (Jacot et al., 2018), which has a unique solution only depending on the kernel matrix on training set, denoted as Ktrain ∈ Rn×n, where n is the training set size. Specifically, for training data {(xi, yi)}i∈[n], the solution f∗NTK : R→ R can be written as
f∗NTK(x) = ( Θ(L)(x, x1) Θ (L)(x, x2) · · · Θ(L)(x, xn) ) K−1trainy, (71)
where y = (y1 y2 . . . yn) is the vector of training labels.
Consider any orthogonal transform T ∈ O(d), and the NTK regression trained on the transformed data {(Txi, yi)}i∈[n]. Denote the solution as f∗NTK,T : R → R. As we have shown, K −1 train is invariant to such transforms, and remains the same. Therefore, f∗NTK,T (Tx) = ( Θ(L)(Tx, Tx1) Θ (L)(Tx, Tx2) · · · Θ(L)(Tx, Txn) ) K−1trainy (72)
= ( Θ(L)(x, x1) Θ (L)(x, x2) · · · Θ(L)(x, xn) ) K−1trainy (73) = f∗NTK(x). (74)
Hence, MLPs trained (with squared loss) in NTK regime is equivariant to orthogonal transforms.
Furthermore, we note that there are many variants of MLP NTK formulas depending on details such as the particular initialization scheme and bias settings. However, they usually only lead to slight changes that do not affect our results. For example, while the above recursive NTK formula are derived assuming that the bias terms are initialized with a normal distribution (Jacot et al., 2018), the formulas for initializing bias as zeros (Geifman et al., 2020) does not affect the dependency only on dot product, and thus our results still hold true.
These cases conclude the proof.

heading: B.3 THM. 4.5: FAILURE OF ALGORITHMS EQUIVARIANT TO ORTHOGONAL TRANSFORMS
text: We start with a more precise statement of Thm. 4.5 that takes into consideration divergent m/n2:
Theorem 4.5 (Failure of Algorithms Equivariant to Orthogonal Transforms). Let (fn)n be an arbitrary sequence of large values. There is an infinite sequence of quasimetric spaces ((Xn, dn))n with |Xn| = n, Xn ⊂ Rn such that, over the random training set S of size m, any learning algorithm equivariant to orthogonal transforms must output a predictor d̂ that satisfies
• d̂ fails non-negativity, or • max(disS(d̂), vio(d̂)) ≥ fn (i.e., d̂ approximates training S badly or is far from a quasimetric), with probability 1/2− o(1), as long as S does not contain almost all pairs 1−m/n2 = ω(n−1/3), and does not only include few pairs m/n2 = ω(n−1/2).
Recall that the little-Omega notation means f = ω(g) ⇐⇒ g = o(f).

heading: B.3.1 PROOF
text: Proof strategy. In our proof below, we will extend the construction discussed in Sec. 4.2 to large quasimetric spaces (reproduced here as Fig. 6). To do so, we
1. Construct large quasimetric spaces containing many copies of the (potentially failing) structure in Fig. 6, where we can consider training sets of certain properties such that
• we can pair up such training sets, • an algorithm equivariant to orthogonal transforms must fail on one of them, • for each pair, the two training sets has equal probability of being sampled;
Then, it remains to show that with probability 1− o(1) we end up with a training set of such properties.
2. Consider sampling training set as individually collecting each pair with a certain probability p, and carefully analyze the conditions to sample a training set with the special properties with high probability 1− o(1).
3. Extend to fixed-size training sets and show that, under similar conditions, we sample a training set with the special properties with high probability 1− o(1).
In the discussion below and the proof, we will freely speak of infinite distances between two elements of X , but really mean a very large value (possibly finite). This allows us to make the argument clearer and less verbose. Therefore, we are not restricting the applicable settings of Thm. 4.5 to quasimetrics with (or without) infinite distances.
In Sec. 4.2, we showed how orthogonal-transform-equivariant algorithms can not predict d̂(y, z) differently for the two particular quasimetric spaces and their training sets shown in Fig. 6.
But are these the only bad training sets? Before the proof, let us consider what kinds of training sets are bad for these two quasimetric spaces. Consider the quasimetrics dleft and dright over X , {x, y, y′, z, w,w′}, with distances as shown in the left and right parts of Fig. 6, where we assume that the unlabeled pairs have infinite distances except in the left pattern d(x,w′) ≤ 2, and in the both patterns d(y, z) has some appropriate value consistent with the respective triangle inequality.
Specifically, we ask:
• For what training sets Sleft ⊂ X × X can we interchange y ↔ y′ and w ↔ w′ on 2nd input to obtain a valid training set for dright, regardless of c? • For what training sets Sright ⊂ X × X can we interchange y ↔ y′ and w ↔ w′ on 2nd input to obtain a valid training set for dleft, regardless of c?
Note that if Sleft (or Sright) satisfies its condition, the predictor d̂ from an algorithm equivariant to orthogonal transforms must (1) predict d̂(y, z) identically and (2) attain the same training set distortion on it and its transformed training set. As we will see in the proof for Thm. 4.5, this implies large distortion or violation for appropriate c.
Intuitively, all we need is that the transformed data do not break quasimetric constraints. However, its conditions are actually nontrivial as we want to set c to arbitrary:
• We can’t have (x,w) ∈ Sright because it would be transformed into (x,w) which has dleft(x,w) ≤ 2. Then dright(x,w) ≤ 2 and then restricts the possible values of c due to triangle inequality with dright(w, z) = 1. For similar reasons, we can’t have (x,w′) ∈ Sleft. In fact, we can’t have a path of finite total distance from x to w (or w′) in Sright (or Sleft). • We can not have (y′, y′) ∈ S(·) (which has distance 0), which would get transformed into (y′, y) with distance 0, which (on the right pattern) would restrict the possible values of c due to triangle inequality, and break our assumption of d(·) not being a quasipseudometric. For similar reasons (w′, w′), and cycles containing y′ or w′ with finite total distance, should be avoided. We note that having (y, y) or (w,w) would also break the non-quasipseudometric assumptions, and thus should avoid them as well (although cycles are okay here since they do not restrict values of c). In fact, with metrics more friendly to zero distances (than distortion and violation, which are based on distance ratios), it might be possible to allow them and obtain better bounds in the second-moment argument below in the proof for Thm. 4.5. • Similarly, we can’t have (y, y′), (y′, y), (w,w′), or (w′, w) in S(·), as they will be mapped to (y, y),(y′, y′), (w,w), or (w′, w′).
With these understandings of the pattern shown in Fig. 6, we are ready to discuss the constructed quasimetric space and training sets.
Proof of Thm. 4.5. Our proof follows the outline listed above.
1. Construct large quasimetric spaces containing many copies of the (potentially failing) structure in Fig. 6.
For any n > 0, consider the following quasimetric space (Xn, dn) of size n, with one-hot features. WLOG, assume n = 12k is a multiple of 12. If it is not, set at most 11 elements to have infinite distance with every other node. This won’t affect the asymptotics. Let the n = 12k elements of the space be
Xn ={xleft1 , . . . , xleftk , x right 1 , . . . , x right k ,w left 1 , . . . , w left k , w right 1 , . . . , w right k ,
yleft1 , . . . , y left k , y right 1 , . . . , y right k ,w ′left 1 , . . . , w ′left k ,w ′right k+1 , . . . , w ′right 2k ,
y′left1 , . . . , y ′left k ,y ′right k+1 , . . . y ′right 2k ,z1, . . . , zk, zk+1, . . . , z2k}, (75)
with quasimetric distances, ∀i, j, dn(x left i , zj) = dn(x right i , zj) = c (76)
dn(w left i , zj) = dn(w right i , zj) = 1 (77)
dn(x left i , y left i ) = dn(x right i , y ′right i ) = 1 (78)
dn(y left i , w ′left i ) = dn(y right i , w right i ) = 1 (79)
dn(x left i , w ′left i ) = 2 (80)
dn(y left i , zj) = c (81)
dn(y right i , zj) = 2, (82)
where subscripts are colored to better show when they are the same (or different), unlisted distances are infinite (except that dn(u, u) = 0,∀u ∈ X ). Essentially, we equally divide the 12k nodes into 6 “types”, {x, y, w, z, w′, y′}, corresponding to the 6 nodes from Fig. 6, where each type has half of its nodes corresponding to the left pattern (of Fig. 6), and the other half corresponding to the right pattern, except for the z types.
Furthermore,
• Among the left-pattern nodes, each set with the same subscript are bundled together in the sense that xlefti only has finite distance to y left i which only has finite distance to w ′left i
(instead of other yleftj ’s or w ′left k ’s). However, since distance to/from y left i and w left i are infinite anyways, we can pair (xlefti , y left i , w ′left i , y ′left j , w left l , zh) (83)
for any i, j, l, h, to obtain a left pattern. • Among the right-pattern nodes, each set with the same subscript are bundled together
in the sense that xrighti only has finite distance to y ′right i , and y right j which only has finite distance to wrightj (instead of other y ′right j ’s or w right k ’s). However, since are distances are infinite anyways, we can pair (xrighti , y ′right i , y right j , w right j , w ′right l , zh) (84) for any i, j, l, h, to obtain a right pattern.
We can see that (X , d) indeed satisfies all quasimetric space requirements (Defn. 2.1), including triangle inequalities (e.g., by, for each (a, b) with finite distance dn(a, b) < ∞, enumerating finite-length paths from a to b).
Now consider the sampled training set S.
• We say S is bad on a left pattern specified by ileft, jleft, lleft, hleft, if S ⊃ {(xleftileft , zhleft), (x left ileft , yleftileft), (y left ileft , w′leftileft ), (w left lleft , zhleft)} (85)
∅ = S ∩ {(yleftileft , zhleft), (y left ileft , yleftileft), (w left lleft , wleftlleft), (y ′left jleft , y′leftjleft ), (w ′left ileft , w′leftileft ),
(xleftileft , w ′left ileft ), (yleftileft , y ′left jleft ), (wleftlleft , w ′left ileft ), (y′leftjleft , y left ileft ), (w′leftileft , w left lleft )} (86) • We say S is bad on a right pattern specified by iright, jright, lright, hright, if
S ⊃ {(xrightiright , zhright), (x right iright , y′rightiright ), (y ′right jright , wrightjright ), (w right jright , zhright)} (87)
∅ = S ∩ {(yrightjright , zhright), (y right jright , yrightjright ), (w right jright , wrightjright ), (y ′right iright , y′rightiright ), (w ′right lright , w′rightlright ),
(xrightiright , w ′right jright ), (yrightjright , y ′right iright ), (wrightjright , w ′right lright ), (y′rightiright , y right jright ), (w′rightlright , w right jright
)} (88)
Most importantly,
• If S is bad on a left pattern specified by ileft, jleft, lleft, hleft, consider the orthogonal transform that interchanges yleftileft ↔ y ′left jleft and wleftlleft ↔ w ′left ileft
on 2nd input. In S, the possible transformed pairs are d(xleftileft , y left ileft ) = 1 −→ d(xleftileft , y ′left jleft ) = 1, (known in S)
d(yleftileft , w ′left ileft ) = 1 −→ d(yleftileft , w left lleft ) = 1, (known in S)
d(u, yleftileft) =∞ −→ d(u, y ′left jleft ) =∞, (poissble in S for some u 6= xleftileft ) d(u, y′leftjleft ) =∞ −→ d(u, y left ileft
) =∞, (poissble in S for some u) d(u,w′leftileft ) =∞ −→ d(u,w left lleft
) =∞, (poissble in S for some u /∈ {xleftileft , y left ileft })
d(u,wleftlleft) =∞ −→ d(u,w ′left ileft ) =∞. (poissble in S for some u)
The crucial observation is that the transformed training set just look like one sampled from a quasimetric space where
– the quasimetric space has one less set of left-pattern elements, – the quasimetric space has one more set of right-pattern elements, and
– transformed training set is bad on that extra right pattern (given by the extra set of right-pattern elements),
which can be easily verified by comparing the transformed training set with the requirements in Eqs. (87) and (88).
• Similarly, if S is bad on a right pattern specified by iright, jright, lright, hright, consider the orthogonal transform that interchanges yrightjright ↔ y ′right iright and wrightjright ↔ w ′right lright
on 2nd input. In S the possible transformed pairs are
d(xrightiright , y ′right iright ) = 1 −→ d(xrightiright , y right jright ) = 1, (known in S)
d(yrightjright , w right jright ) = 1 −→ d(yrightjright , w ′right lright ) = 1, (known in S)
d(u, yrightjright ) =∞ −→ d(u, y ′right iright ) =∞, (poissble in S for some u)
d(u, y′rightiright ) =∞ −→ d(u, y right jright
) =∞, (poissble in S for some u 6= xrightiright )
d(u,w′rightlright ) =∞ −→ d(u,w right jright ) =∞, (poissble in S for some u)
d(u,wrightjright ) =∞ −→ d(u,w ′right lright
) =∞. (poissble in S for some u /∈ {xrightiright , y right jright })
Again, the crucial observation is that the transformed training set just look like one sampled from a quasimetric space where
– the quasimetric space has one less set of right-pattern elements, – the quasimetric space has one more set of left-pattern elements, and – transformed training set is bad on that extra left pattern (given by the extra set of
left-pattern elements), which can be easily verified by comparing the transformed training set with the requirements in Eqs. (85) and (86).
Therefore, when S is bad on both a left pattern and a right pattern (necessarily on disjoint sets of pairs), we consider the following orthogonal transform composed of:
(a) both transforms specified above (which only transforms 2nd inputs), (so that after this we obtain another possible training set of same size from the quasimetric space that is only different up to some permutation of X )
(b) a permutation of X (on both inputs) so that the bad left-pattern nodes and the bad right-pattern nodes exchange features,
This transforms gives another possible training set of same size from the same quasimetric space, also is bad on a left pattern and a right pattern. Moreover, with a particular way of select bad patterns (e.g., by the order of the subscripts), this process is reversible. Therefore, we have defined a way to pair up all such bad training sets.
Consider the predictors d̂before and d̂after trained on these two training sets (before and after transform) with an learning algorithm equivariant to orthogonal transforms. Assuming that they satisfy non-negativity and Identity of Indiscernibles, we have,
• The predictors have the same distortion over respective training sets.
Therefore we denote this distortion as disS(d̂) without specifying the predictor d̂ or training set S.
• the predictors must predict the same on heldout pairs in the sense that d̂before(y left ileft , zhleft) = d̂after(y right jright , zhright) (89)
d̂before(y right jright , zhright) = d̂after(y left ileft , zhleft). (90)
Focusing on the first, we denote d̂(y, z) , d̂before(y left ileft , zhleft) = d̂after(y right jright , zhright) (91)
without specifying the predictor d̂ or the specific y and z.
However, the quasimetric constraints on heldout pairs (yleftileft , zhleft) and (y right jright , zhright) are completely different (see the left vs. right part of Fig. 6). Therefore, as shown in Fig. 6, assuming non-negativity, one of the two predictors must have total violation at least
vio(d̂) ≥ max
( c
disS(d̂)(disS(d̂) + d̂(y, z)) ,
d̂(y, z)
2 · disS(d̂)
) . (92)
Fixing a large enough c, two terms in the max of Eq. (92) can equal for some d̂(y, z), and are respectively decreasing and increasing in d̂(y, z). In that case, we have
vio(d̂) ≥ δ 2 · disS(d̂) , (93)
for δ > 0 such that
c
disS(d̂)(disS(d̂) + δ) =
δ
2 · disS(d̂) . (94)
Solving the above quadratic equation gives
δ = −disS(d̂) +
√ disS(d̂)2 + 8c
2 , (95)
leading to
vio(d̂) ≥ −1 +
√ 1 + 8c/disS(d̂)2
4 . (96)
Therefore, choosing c ≥ f2n(4fn + 1)2 gives disS(d̂) ≤ fn (97)
=⇒ vio(d̂) ≥ −1 +
√ 1 + 8c/disS(d̂)2
4 (98)
≥ −1 +
√ 1 + 8f2n(4fn + 1)
2/f2n 4
(99)
= −1 +
√ 1 + 8(4fn + 1)2
4 (100)
≥ −1 + 4fn + 1 4
(101)
= fn. (102)
Hence, for training sets that are bad on both a left pattern and a right pattern, we have shown a way to pair them up such that
• each pair of training sets have the same size, and • the algorithm fail on one of each pair by producing a distance predictor that
– has either distortion over training set ≥ fn, or violation ≥ fn, and – has test MSE ≥ fn.
Remark B.1. Note that all training sets of size m has equal probability of being sampled. Therefore, to prove the theorem, it suffices to show that with probability 1− o(1), we can sample a training set of size m that is bad on both a left pattern and a right pattern.
2. Consider sampling training set as individually collecting each pair with a certain probability p, and carefully analyze the conditions to sample a training set with the special properties with high probability 1− o(1). In probabilistic methods, it is often much easier to work with independent random variables. Therefore, instead of considering uniform sampling a training set S of fixed size m, we consider including each pair in S with probability p, chosen independently. We will first show result based on this sampling procedure via a second moment argument, and later extend to the case with a fixed-size training set.
First, let’s define some notations that ignore constants: f ∼ g ⇐⇒ f = (1 + o(1))g (103) f g ⇐⇒ f = o(g). (104)
We start with stating a standard result from the second moment method (Alon & Spencer, 2004).
Corollary B.2 (Corollary 4.3.5 of (Alon & Spencer, 2004)). Consider random variable X = X1 +X2 + · · ·+Xn, where Xi is the indicator random variable for event Ai. Write i ∼ j if i 6= j and the pair of events (Ai, Aj) are not independent. Suppose the following quantity does not depend on i:
∆∗ , ∑ j∼i P [Aj | Ai] . (105)
If E [X]→∞ and ∆∗ E [X], then X ∼ E [X] with probability 1− o(1).
We will apply this corollary to obtain conditions on p such that S with probability 1− o(1) is bad on some left pattern, and conditions such that S with probability 1− o(1) is bad on some right pattern. A union bound would then give the desired result.
• S is bad on some left pattern.
Recall that a left pattern is specified by ileft, jleft, lleft, hleft all ∈ [k]: (xleftileft , y left ileft , w′leftileft , y ′left jleft , wleftlleft , zhleft) (106)
Therefore, we consider k4 = ( n12 ) 4 events of the form
Aileft,jleft,lleft,hleft , {S is bad on the left pattern at ileft, jleft, lleft, hleft}. (107)
Obviously, these events are symmetrical, and the ∆∗ in Eq. (105) does not depend on i.
By the quasimetric space construction and the requirement for S to be bad on a left pattern in Eqs. (85) and (86), we can see that (ileft, jleft, lleft, hleft) ∼ (i′left, j′left, l′left, h′left) only if ileft = i′left or jleft = j ′ left or lleft = l ′ left or hleft = h ′ left.
Therefore, we have E [X] ∼ n4p4(1− p)10 (include 4 pairs & exclude 10 pairs)
∆∗ n3p4(1− p)9 (share jleft) + n3p2(1− p)7 (share ileft) + n3p4(1− p)9 (share lleft) + n3p4(1− p)10 (share hleft) + n2p2(1− p)4 (share jleft, ileft) + n2p4(1− p)8 (share jleft, lleft) + n2p4(1− p)9 (share jleft, hleft) + n2p2(1− p)4 (share ileft, lleft) + n2p(1− p)6 (share ileft, hleft) + n2p3(1− p)9 (share lleft, hleft) + n(1− p)3 (share ileft, lleft, hleft) + np3(1− p)8 (share jleft, lleft, hleft) + np(1− p)3 (share jleft, ileft, hleft) + np2(1− p) (share jleft, ileft, lleft)
∼ n3p2(1− p)7 + n2(p2(1− p)4 + p(1− p)6) (108) + n((1− p)3 + p2(1− p)). (109)
Therefore, to apply Corollary B.2, we need to have n4p4(1− p)10 →∞ (110) n3p2(1− p)7 n4p4(1− p)10 (111)
n2(p2(1− p)4 + p(1− p)6) n4p4(1− p)10 (112) n((1− p)3 + p2(1− p)) n4p4(1− p)10, (113)
which gives p n−1/2 (114)
1− p n−1/3 (115) as a sufficient condition to for S to be bad on some left pattern with probability 1−o(1).
• S is bad on some right pattern. Recall that a right pattern is specified by iright, jright, lright, hright all ∈ [k]:
(xrightiright , y ′right iright , yrightjright , w right jright , w′rightlright , zhright) (116)
Similarly, we consider k4 = ( n12 ) 4 events of the form
Airight,jright,lright,hright , {S is bad on the left pattern at iright, jright, lright, hright}. (117) Again, these events are symmetrical, and ∆∗ in Eq. (105) does not depend on i. Similarly, we have
E [X] ∼ n4p4(1− p)10 (include 4 pairs & exclude 10 pairs) ∆∗ n3p3(1− p)9 (share iright)
+ n3p3(1− p)8 (share jright) + n3p4(1− p)10 (share hright) + n3p4(1− p)9 (share lright) + n2p2(1− p)4 (share iright, jright) + n2p2(1− p)9 (share iright, hright) + n2p3(1− p)8 (share iright, lright) + n2p2(1− p)7 (share jright, hright) + n2p3(1− p)5 (share jright, lright) + n2p4(1− p)9 (share hright, lright) + np2(1− p)4 (share jright, hright, lright) + np2(1− p)8 (share iright, hright, lright) + np2(1− p) (share iright, jright, lright) + n(1− p) (share iright, jright, hright)
∼ n3p3(1− p)8 + n2p2(1− p)4 (118) + n(1− p). (119)
Therefore, to apply Corollary B.2, we need to have n4p4(1− p)10 →∞ (120) n3p3(1− p)8 n4p4(1− p)10 (121) n2p2(1− p)4 n4p4(1− p)10 (122)
n(1− p) n4p4(1− p)10, (123) which gives
p n−3/4 (124) 1− p n−1/3 (125)
as a sufficient condition to for S to be bad on some right pattern with probability 1− o(1).
So, by union bound, as long as p n−1/2 (126)
1− p n−1/3, (127) S is bad on some left pattern and some right pattern with probability 1− o(1).
3. Extend to fixed-size training sets and show that, under similar conditions, we sample a training set with the special properties with high probability 1− o(1). To extend to fixed-size training sets, we consider the following alteration procedure:
(a) Sample training set S by independently include each pair with probability p , m+δn2 , for some δ > 0.
(b) Show that with high probability 1− o(1), we end up with [m,m+ 2δ] pairs in S. (c) Make sure that p satisfy Eq. (126) and Eq. (127) so that S is bad on some left pattern
and some right pattern with high probability 1− o(1). (d) Randomly discard the additional pairs, and show that with high probability 1− o(1)
this won’t affect that S is bad on some left pattern and some right pattern.
We now consider each step in details:
(a) Sample training set S by independently include each pair with probability p , m+δ n2 , for some δ > 0.
For p , m+δn2 , the number of pairs in the training set is distributed as
Binomial(n2, m+ δ
n2 ). (128)
(b) Show that with high probability 1− o(1), we end up with [m,m+ 2δ] pairs in S. Standard Binomial concentration tells us that,
δ n √ p(1− p) =⇒ P [ Binomial(n2, m+ δ
n2 ) /∈ [m,m+ 2δ]
] → 0, (129)
which can be satisfied if
δ n. (130) (c) Make sure that p satisfy Eq. (126) and Eq. (127) so that S is bad on some left
pattern and some right pattern with high probability 1− o(1). Therefore, we want
m+ δ
n2 n−1/2 (131)
1− m+ δ n2
n−1/3. (132)
(d) Randomly discard the additional pairs, and show that with high probability 1− o(1) this won’t affect that S is bad on some left pattern and some right pattern. We want to make make sure that we don’t break a bad left pattern and a right pattern in S. Since we only discard pairs, it suffices to only consider the pairs we want to preserve, which are a total of 8 pairs across two patterns. Each such pair is discarded the probability ≤ 2δm , since we remove at most 2δ pairs. By union bound,
P [all 8 pairs are preserved] ≥ 1− 16δ m . (133)
Hence, it suffices to make sure that δ m. (134)
Collecting all requirements, we have δ n (135)
m+ δ
n2 n−1/2 (136)
1− m+ δ n2
n−1/3 (137)
δ m. (138)
Assume that m
n2 n−1/2 (139) 1− m n2 n−1/3. (140)
It can be easily verified that using δ , n1.1 satisfies all conditions.
Hence, for a uniformly randomly sampled training set S with size m, S is bad on some left pattern and some right pattern with high probability 1− o(1), as long as
m n2 n−1/2 (141) 1− m n2 n−1/3. (142)
This is exactly the condition we need to prove the theorem (see Remark B.1).
This concludes the proof.

heading: B.3.2 DISCUSSIONS
text: Training set size dependency. Intuitively, when the training set has almost all pairs, violation can be lowered by simply fitting training set well; when it is small and sparse, the learning algorithm may have an easier job finding some consistent quasimetric. Thm. 4.5 shows that, outside these two cases, algorithms equivariant to orthogonal transforms can fail. Note that for the latter case, Thm. 4.5 requires the training fraction to decrease slower than n−1/2, which rules out training sizes that is linear in n. We leave improving this result as future work. Nonetheless, Thm. 4.5 still covers common scenarios such as a fixed fraction of all pairs, and highlights that a training-data-agnostic result (such as the ones for PQEs) is not possible for these algorithms.
Proof techniques. In embedding theory, it is quite standard to analyze quasimetrics as directed graphs due to their lack of nice metric structure. In the proof for Thm. 4.5, we used abundant techniques from the probabilistic method, which are commonly used for analyzing graph properties in the asymptotic case, including Corollary B.2 from the second moment technique, and the alteration technique to extend to fixed-size training sets. While such techniques may be new in learning theory, they are standard for characterizing asymptotic probabilities on graphs, which quasimetrics are often analyzed as (Charikar et al., 2006; Mémoli et al., 2018).
To provide more intuition on why these techniques are useful here, we note that the construction of a training set of pairs is essentially like constructing an Erdős-Rényi random graph on n2 vertices. Erdős-Rényi (undirected) random graphs come in two kinds:
• Uniformly sampling a fixed number of m edges; • Adding an edge between each pair with probability p, decided independently.
The latter, due to its independent decisions, is often much easy to analyze and preferred by many. The alteration technique (that we used in the proof) is also a standard way to transfer a result on a random graph of the latter type, to a random graph of the former type (Bollobás & Béla, 2001). Readers can refer to (Alon & Spencer, 2004; Bollobás & Béla, 2001; Erdős & Rényi, 1959) for more in-depth treatment of these topics.
Generalization to other transforms. The core of this construction only relies on the ability to swap (concatenated) inputs between (x, y)↔ (x, y′) and between (y, w)↔ (y, w′) via a transform.
For instance, here the orthogonal transforms satisfy this requirement on one-hot features. Therefore, the result can also be generalized to other transforms and features with the same property. Our stated theorem focuses on orthogonal transforms because they correspond to several common learning algorithms (see Lemma 4.4). If a learning algorithm is equivariant to some other transform family, it would be meaningful to generalize this result to that transform family, and obtain a similar negative result. We leave such extensions as future work.

heading: B.3.3 COROLLARY OF DISTORTION AND VIOLATION FOR UNCONSTRAINED MLPS
text: Corollary B.3 (Distortion and Violation of Unconstrained MLPs). Let (fn)n be an arbitrary sequence of desired violation values. There is an infinite collection of quasimetric spaces ((Xn, dn))n=1,2,... with |Xn| = n, Xn ⊂ Rn such that MLP trained with squared loss in NTK regime converges to a function d̂ that either
• fails non-negativity, or • vio(d̂) ≥ fn,
with probability 1/2− o(1) over the random training set S of size m, as long as S does not contain almost all pairs 1−m/n2 = ω(n−1/3), and does not only include few pairs m/n2 = ω(n−1/2).
Proof of Corollary B.3. This follows directly from Thm. 4.5 and standard NTK convergence results obtained from the kernel regression optimality and the positive-definiteness of the NTK. In particular, Proposition 2 of (Jacot et al., 2018) claims that the NTK is positive-definite when restricted to a hypersphere. Since the construction in proof of Thm. 4.5 uses one-hot features, the input (concatenation of two features) lie on the hypersphere with radius √ 2. Hence, the NTK is guaranteed positive definite.

heading: B.3.4 EMPIRICAL VERIFICATION OF THE FAILURE CONSTRUCTION
text: We train unconstrained MLPs on the toy failure construction discussed in Sec. 4.2 (reproduced as Fig. 6). The MLP uses 12-1024-1 architecture with ReLU activations, takes in the concatenated one-hot features, and directly outputs predicted distances. Varying c ∈ {1, 10, 100, 1000}, we train the above MLP 5 times on each of the two patterns in Fig. 6, by regressing towards the training distances via MSE loss.
In Fig. 7, we can see that all training runs conclude with small training error, and indeed the trained MLPs predict very similarly on the heldout pair, regardless whether it is trained on the left or right pattern of Fig. 6, which restricts the heldout pair distance differently.
This verifies our theory (Thm. 4.5 and Corollary B.3) that algorithms equivariant to orthogonal transforms (including MLPs in NTK regime) cannot distinguish these two cases and thus must fail on one of them.

heading: C PROOFS AND DISCUSSIONS FOR SEC. 5: POISSON QUASIMETRIC EMBEDDINGS (PQES)

heading: C.1 NON-DIFFERENTIABILITY OF CONTINUOUS-VALUED STOCHASTIC PROCESSES
text: In this section we formalize the argument presented in Sec. 5.3 to show why continuous-valued stochastic processes lead to non-differentiability. Fig. 8 also provides a graphical illustration of the general idea.
Proposition C.1 (Quasimetric Embeddings with Continuous-Valued Stochastic Processes are not Differentiable). Consider any Rk-valued stochastic process {R(u)}u∈Rd such that u 6= u′ =⇒ P [R(u) = R(u′)] < c for some universal constant c < 1. Then P [R(u) ≤ R(u′)] is not differentiable at any u = u′.
Proof of Proposition C.1. Assume that the quantity is differentiable. Then it must be continuous in u and v.
We will use the ( , δ)-definition of continuity.
At any u ∈ Rd, consider small ∈ (0, 1−c3 ). By continuity, since P [R(u) ≤ R(u)] = P [R(u+ δ) ≤ R(u+ δ)] = 1 (143)
we can find ∈ Rd such that P [R(u) ≤ R(u+ δ)] ≥ 1− (144) P [R(u+ δ) ≤ R(u)] ≥ 1− . (145)
However, by assumption, P [R(u) = R(u+ δ)] < c. Therefore, P [R(u) ≤ R(u+ δ)] ≥ 1− (146) P [R(u+ δ) < R(u)] ≥ 1− − c, (147)
which implies
1 = P [R(u) ≤ R(u+ δ)] + P [R(u+ δ) < R(u)] ≥ 2− 2 − c ≥ 5 3 − 2 3 c > 1. (148)
By contradiction, the quantity must not be differentiable at any u = u′.

heading: C.2 PQE-GG: GAUSSIAN-BASED MEASURE AND GAUSSIAN SHAPES
text: In Sec. 5.1, we presented the following PQE-LH formulation for Lebesgue measures and half-lines: dPQE-LHz (u, v) , ∑ i αi · ( 1− exp ( − ∑ j (ui,j − vi,j)+ )) . (11) Here, ui,j and vi,j receive zero gradient when ui,j ≤ vi,j .
Gaussian shapes parametrization. We therefore consider a set parametrization where no one set is entirely contained in a different set— the regions regions ⊂ R2 between an axis and a 1D Gaussian density function of fixed variance σ2shape = 1. That is, for each given u ∈ R, we consider sets
AN (µ) , {(a, b) : b ∈ [0, fN (a;µ, 1)]}, (149) where fN (b;µ, σ2) denotes the density of 1D Gaussian N (µ, σ2) with mean µ and variance σ2 evaluated at b. Since the Gaussian density function have unbounded support, these sets, which are translated versions of each other, never have one set fully contained in another. For latent u ∈ Rh×k reshaped as 2D, our set parametrizations are,
u→ Ai,j(u) , AN (ui,j), i ∈ [h], j ∈ [k]. (150)
A Gaussian-based measure. These subsets of R2 always have Lebesgue measure 1, which would make PQE symmetrical (if used with a (scaled) Lebesgue measure). Thus, we use an alternative R2 measure given by the product of a R Lebesgue measure on the b-dimension (i.e., dimension of the function value of the Gaussian density) and a R Gaussian measure on the a-dimension (i.e., dimension on the input of the Gaussian density) centered at 0 with learnable variances (σ2measure)i,j . To avoid being constrained by the bounded total measure of 1, we also optimize learnable positive scales ci,j > 0. Hence, the each Poisson process has a mean measure as the product of a R Lebesgue measure and a R Gaussian with learnable standard deviation, then scaled with a learnable scale.
Note that the Gaussian measure should not be confused with the Gaussian shape. Their parameters also are fully independent with one another.
Computing measures of Gaussian shapes and their intersections. The intersection of two such Gaussian shapes is formed by two Gaussian tail shapes, reflected around the middle point of the two Gaussian means (since they have the same standard deviation σshape = 1). Hence, it is sufficient to describe how to integrate a Gaussian density on a Gaussian measure over an interval. Applying this with different intervals would give the measure of the intersection, and the measures of the two Gaussian shapes. Omit indices i, j for clarity. Formally, we integrate the Gaussian density fN (a;u, σ 2 shape) over the centered Gaussian measure with variance σ 2 measure, which has density fN (a; 0, σ 2 measure): ∫
c · fN (a;u, σ2shape)fN (a; 0, σ2measure) da, (151)
which is also another Gaussian integral (e.g., considered as integrating the product measure along the a line of the form y = x+ u). After standard algebraic manipulations (omitted here), we obtain∫
c · fN (a;u, σ2shape)fN (a; 0, σ2measure) da (152)
= c · exp
( −u2/σ2total )√ 2πσ2total ∫ fN ( a;u σ2measure σ2total , σ2shapeσ 2 measure σ2total ) da, (153)
for
σ2total , σ 2 shape + σ 2 measure. (154)
This can be easily evaluated using statistical computing packages that supports computing the error function and/or Gaussian CDF. Moreover, this final form is also readily differentiable with standard gradient formulas. To summarize,
• each set A(u) has total measure c√
2πσ2total exp
( −u2/σ2total ) ; (155)
• the intersection of A(v) and A(u2), for v ≤ u2 has measure c · exp ( −u22/σ2total )√ 2πσ2total ∫ v+u2 2 −∞ fN ( a;u2 σ2measure σ2total , σ2shapeσ 2 measure σ2total ) da (156)
+ c · exp
( −v2/σ2total )√ 2πσ2total ∫ +∞ v+u2 2 fN ( a; v σ2measure σ2total , σ2shapeσ 2 measure σ2total ) da. (157)
Interpretation and representing any total order. Consider two Gaussian shapesA(v) andA(u2). Note that the Gaussian-based measure µGaussian is symmetric around and centered at 0. Therefore,
|v| < |u2| =⇒ µGaussian(A(v)) > µGaussian(A(u2)) (158) =⇒ µGaussian(A(v) \A(u2)) > µGaussian(A(u2) \A(v)). (159)
Moreover, scaling the rates of a Poisson makes it more concentrated (as a Poisson’s mean grows as the square of its standard deviation) so that limc→∞ P [Pois(cµ1) ≤ Pois(cµ2)] = 1µ1<µ2 for µ1 6= µ2. Then any total order can be represented as the limit of a Poisson process with Gaussian shapes, with the shapes’ having their means arranged according to the total order, as the scale on the Gaussian-based measure grows to infinity.

heading: C.3 THEORETICAL GUARANTEES FOR PQES
text: Theorem 5.2 (Distortion and violation of PQEs). Under the assumptions of Sec. 4, any quasimetric space with size n and treewidth t admits a PQE-LH and a PQE-GG with distortion O(t log2 n) and violation 1, with an expressive encoder (e.g., a ReLU network with ≥ 3 layers and polynomial width).
In Sec. 5.4, we presented the above theoretical distortion and violation guarantees for PQE-LH and PQE-GG. Furthermore, we commented that the same guarantees apply to more generally to PQEs satisfying a mild condition. Here, we first precisely describe this condition, show that PQE-LH and PQE-GG do satisfy it, state and prove the general result, and then show the above as a straightforward corollary.

heading: C.3.1 THE CONCENTRATION PROPERTY
text: Recall that PQEs are generally defined with measures µ and set parametrizations A as dPQEz (u, v;µ,A, α) , ∑ i αi · Eπz∼ΠPQEz (µi,Ai) [πz(u, v)] , (14) where Eπz∼ΠPQEz (µ,A)[πz(u, v)] , 1− ∏ j P [Nj(Aj(u)) ≤ Nj(Aj(v))] . (13)
Because the measures µ and set parametrizations A themselves may have parameters (e.g., as in PQE-GG), we consider them as classes of PQEs. E.g., PQE-GG is a class of PQEs such that the µ is the specific Gaussian-based form, and A is the specific Guassian-shape.
Definition C.2 (Concetration Property of PQEs). Consider a PQE class with h mixtures of quasipartition distributions, each from k Poisson processes. We say that it has concentration property if it satisfies the following. Consider any finite subset of X ′ ⊂ X , and arbitrary function g : X → Rh×k. There exists a sequence of ((f (n), µ(n), A(n))n such that
• f (n) : X ′ → Rd, • µ(n), A(n) are valid members of this PQE,
• Eπz∼ΠPQEz (µi,Ai) [ πz(f (n)(x′), f (n)(y′)) ] uniformly converges to 1− ∏ j 1g(x)i,j≤g(y)i,j , over
all mixtures i and pairs x, y ∈ X ′.
A sufficient condition. It suffices to make the probabilities (x, y, i, j)→ P [Nj(Aj(u)) ≤ Nj(Aj(v))] , (160) along some PQE sequence uniformly converge to the indicators (x, y, i, j)→ 1g(x′)i,j≤g(y′)i,j . (161)
This is sufficient since product of bounded functions is uniformly convergent, if each function is. Both statements below together form a sufficient condition for Eq. (160) to uniformly converge to Eq. (161):
1. For any g, there exists a specific PQE of this class satisfying • Measures (of set differences) are consistent with g with some margin > 0: ∀i ∈
[h], j ∈ [k], x ∈ X ′, y ∈ X ′, g(x)i,j < g(y)i,j ⇐⇒ µi,j(Ai,j(f(x)) \Ai,j(f(y))) + < µi,j(Ai,j(f(y)) \Ai,j(f(x))) g(x)i,j = g(y)i,j ⇐⇒ µi,j(Ai,j(f(x)) \Ai,j(f(y))) = µi,j(Ai,j(f(y)) \Ai,j(f(x))) = 0.
• Either of the following: – One side must be zero: ∀i ∈ [h], j ∈ [k], x ∈ X , y ∈ X ,
(µi,j(Ai,j(f(x)) \Ai,j(f(y)))) (µi,j(Ai,j(f(y)) \Ai,j(f(x)))) = 0, (162) – Max measure is bounded by some constant c > 0:
max x,y,i,j
µi,j(Ai,j(f(x)) \Ai,j(f(y))) ≤ c. (163)
2. For any given specific PQE of this class, for any positive scale d > 0, there is another PQE (with same formulation) whose measures (of set differences) equal exactly those of the given PQE scaled by d.
We now show that this is a sufficient condition. Note that a Poisson distribution has standard deviation equal to square root of its mean. This means that as we scale the rate of a Poisson, it becomes more concentrated. Applying to Poisson race probability, we have, for 0 ≤ µ1 + < µ2,
• one direction of Poisson race probability: P [Pois(d · µ1) ≤ Pois(d · µ2)] (164)
≥ P [|Pois(d · µ2)− Pois(d · µ1)− d(µ2 − µ1)| ≤ d(µ2 − µ1)] (165)
≥ 1− µ1 + µ2 d(µ2 − µ1)2
(166)
≥ {
1− 2d if µ1 = 0 1− 2cd 2 if µ2 < c;
(167)
• the other direction of Poisson race probability: P [Pois(d · µ2) ≤ Pois(d · µ1)] (168)
≤ P [|Pois(d · µ2)− Pois(d · µ1)− d(µ2 − µ1)| ≥ d(µ2 − µ1)] (169)
≤ µ1 + µ2 d(µ2 − µ1)2
(170)
≤ {
2 d if µ1 = 0 2c d 2 if µ2 < c.
(171)
Therefore, applying to scaled versions of the PQE from Item 1 above, we have thus obtained the desired sequence, where Eq. (160) uniformly converges to Eq. (161) with rate O(1/d). Lemma C.3. PQE-LH and PQE-GG has the concentration property.
Proof of Lemma C.3. We show that both classes satisfy the above sufficient condition.
• PQE-LH: Lebesgue measure λ and half-lines.
WLOG, since X is countable, we assume that g satisfies g(x)i,j 6= g(y)i,j =⇒ |g(x)i,j − g(y)i,j | > 1, ∀i ∈ [h], j ∈ [k], x ∈ X ′, y ∈ X ′. (172) The encoder in Item 1 above f : X → Rh×k can simply be g. We then have µi,j(Ai,j(f(y))\Ai,j(f(x))) = Leb((−∞, g(y)]\(−∞, g(x)]) = (g(y)i,j−g(x)i,j)+. (173) This ensures that one side is always zero. Furthermore, scaling can be done by simply scaling the encoder f . Hence, PQE-LH satisfies this constraint.
• PQE-GG: Gaussian-based measure and Gaussian shapes (see Appendix C.2).
Because X ′ is finit, we can have positive constant margin for the PQE requirements in Item 1. (Infinite X ′ does not work because the total measure is finite (for a specific PQE-GG with specific values of the scaling).) Concretely, we satisfy both requirements via
– in descending order of g(·)i,j we assign Gaussian shapes increasingly further from the origin;
– scaling comes from that we allow scaling the Gaussian-based measure. Hence, PQE-GG satisfies this constraint for finite X .

heading: C.3.2 A GENERAL STATEMENT
text: We now state the general theorem for PQEs with the above concentration property. Theorem C.4 (Distortion and violation of PQEs (General)). Consider any PQE class with the concentration property. Under the assumptions of Sec. 4, any quasimetric space with size n and treewidth t admits such a PQE with distortion O(t log2 n) and violation 1, with an expressive encoder (e.g., a ReLU network with ≥ 3 hidden layers,O(n) hidden width, andO(n2) quasipartition distributions, each with O(n) Poisson processes.).
Before proving this more general theorem, let us extend a result from Mémoli et al. (2018). Lemma C.5 (Quasimetric Embeddings with Low Distortion; Adapted from Corollary 2 in Mémoli et al. (2018)). Let M = (X, d) be a quasipseudometric space with treewidth t, and n = |X|. Then M admits an embedding into a convex combination (i.e., scaled mixture) of O(n2) quasipartitions with distortion O(t log2 n).
Proof of Lemma C.5. The distortion bound is proved in Corollary 2 in (Mémoli et al., 2018), which states that any quasipseudometric space with n elements and t treewidth admits an embedding into a convex combination of quasipartitions with distortion O(t log2 n). To see that n2 quasipartitions suffice, we scrutinize their construction of quasipartitions in Algorithm 2 of (Mémoli et al., 2018), reproduced below as Algorithm 1.
Algorithm 1 Random quasipartition of a bounded treewidth graph. Algorithm 2 of (Mémoli et al., 2018). Input: A digraph G of treewidth t, a hierarchical tree of separators of G (H, f) with width t, and r > 0. Output: A random r-bounded quasipartition R.
Initialization: Set G∗ = G, H∗ = H and R = E(G). Perform the following recursive algorithm on G∗ and H∗. Step 1. Pick z ∈ [0, r/2] uniformly at random. Step 2. If |V (G∗)| ≤ 1,terminate the current recursive call. Otherwise pick the set of vertices K = G∗.
Let H1, . . . , Hm be the sub-trees of H∗ below root(H∗) that are hierarchical trees of separators of C1, . . . , Cm respectively.
Step 3. For all (u, v) ∈ E(G∗) remove (u, v) from R if one of the following holds: (a) dG(u, x) > z and dG(v, x) ≤ z for some vertex x ∈ K. (b) dG(x, v) > z and dG(x, u) ≤ z for some vertex x ∈ K. Step 4. For all i ∈ {1, . . . ,m} perform a recursive call of Steps 2-4 setting G∗ = G∗[Ci] and H∗ = Hi. Step 5. Once all branches of the recursive terminate, enforce transitivity on R: For all u, v, w ∈ V (G) if
(u, v) ∈ R and (v, w) ∈ R, add (u,w) to R.
Many concepts used in Algorithm 1 are not relevant for our purpose (e.g., r-bounded quasipartition). Importantly, we observe that for a given quasimetric space, the produced quasipartition is entirely determined by the random choice of z in Step 1, which is only used to compare with distance values between node pairs. Note that there are n2 node pairs, whose minimum distance is exactly 0 (i.e., distance from a node to itself). Since z ≥ 0, there are at most n2 choices of z that lead to at most n2 different quasipartitions, for all possible values of r.
The construction used to prove Corollary 2 of (Mémoli et al., 2018) uses exactly quasipartitions given by this algorithm. Therefore, the lemma is proved.
Lemma C.5 essentially proves the first half of Thm. C.4. Before proving the full Thm. C.4, we restate the following result from (Hiraguchi, 1951), which gives us a bound on how many total orders are needed to represent a general partial order (i.e., quasipartition).
Theorem C.6 (Hiraguchi’s Theorem (Hiraguchi, 1951; Bogart, 1973)). Let (X,P ) be a partially ordered set such that |X| ≥ 4. Then there exists a mapping f : X → Rb|X|/2c such that
∀x, y ∈ X, xPy ⇐⇒ f(x) ≤ f(y) coordinate-wise . (174)
Proof of Thm. C.4. It immediately follows from Lemma C.5 and Thm. C.6 that any quasimetric space with n elements and treewidth t admits an embedding with distortionO(t log2 n) into a convex combination of n2 quasipartitions, each represented with an intersection of O(n) total orders. Because the PQE class has concentration property, for any finite quasimetric space, we can simply select a PQE that is close enough to the desired convex combination of n2 quasipartitions, to obtain distortion O(t log2 n). Since each Poisson process in PQE takes a constant number of latent dimensions, we can have such a PQE with O(n3)-dimensional latents and n2 quasipartition distributions.
It remains only to prove that we can compute such required latents using the described architecture.
Consider any x ∈ X ⊂ Rd. Since X is finite, we can always find direction ux ∈ Rd such that ∀y ∈ X \ {x}, yTux 6= xTux. That is, x has a unique projection onto ux. Therefore, we can have c, b+, b− ∈ R such that
c · uTxx+ b+ = 1 (175) −c · uTxx+ b− = 1, (176)
but for y ∈ X \ {x}, we have, for some a > 0, either c · uTxy + b+ = −a (177) −c · uTxy + b− = a+ 2, (178) or c · uTxy + b+ = a+ 2 (179) −c · uTxy + b− = −a. (180)
Then, consider computing two of the first layer features as, on input z, [ReLU(c · uTxz + b+) ReLU(−c · uTxz + b−)], (181) which, if z = x, is [1, 1]; if z 6= x, is either [0, 2 + a] or [2 + a, 0], for some a > 0. Then, one of the second layer features may sum these two features and threshold it properly would single out x, i.e., activate only when input is x.
After doing this for all x ∈ X , we obtain an n-dimensional second layer feature space that is just one-hot features.
The third layer can then just be a simple embedding look up, able to represent any embedding, including the one allowing a PQE to have distortion O(t log n), as described above. Because quasimetric embeddings naturally have violation 1, this concludes the proof.

heading: C.3.3 PROOF OF THM. 5.2: DISTORTION AND VIOLATION OF PQES
text: Proof of Thm. 5.2. Lemma C.3 and Thm. C.4 imply the result. To see that polynomial width is sufficient, note that the hidden width are polynomial by Thm. C.4, and that the embedding dimensions needed to represent each of the O(n3) Poisson processes is constant 1 in both PQE-LH and PQE-GG. Hence the latent space is also polynomial. This concludes the result.

heading: C.3.4 DISCUSSIONS
text: Dependency on log n. log n dependency frequently occurs in distortion results. Perhaps the most well-known ones are Bourgain’s Embedding Theorem (Bourgain, 1985) and the Johnson-
Lindenstrauss Lemma (Johnson & Lindenstrauss, 1984), which concern metric embeddings into Euclidean spaces.
Dependency on treewidth t. Treewidth t here works as a complexity measure of the quasimetric. We will use a simple example to illustrate why low-treewidth is easy. Consider the extreme case where the quasimetric is the shortest-path distance on a tree, whose each edge is converted into two opposing directed ones and assigned arbitrary non-negative weights. Such a quasimetric space has treewidth 1 (see Defn. 2.2). On a tree,
1. the shortest path between two points is fixed, regardless of the weights assigned, 2. for each internal node u and one of its child c, the followings are quasipartitions:
d′01(x, y) , 1shortest path from x to y passes (u, c) d′′01(x, y) , 1shortest path from x to y passes (c, u).
Hence it can be exactly represented as a convex combination of quasipartitions. However, both of observations becomes false when the graph structure becomes more complex (higher treewidth) and the shortest paths can are less well represented as tree paths of the tree composition.
Comparison with unconstrained MLPs. Thm. C.4 requires a poly-width encoder to achieve low distortion. This is comparable with deep unconstrained MLPs trained in NTK regime, which can reach 0 training error (distortion 1 on training set) in the limit but also requires polynomial width (Arora et al., 2019).
Quasipseudometrics and infinite distances. Thm. C.4 relies on our assumptions that (X , d) is not a quasipseudometric space and has all finite distances. In fact, if we allow a PQE to have infinite convex combination weights, it can readily represent quasipseudometric spaces with infinite distances. Additionally, PQE can still well approximate the quasimetric space with infinities replaced with any sufficiently large finite value (e.g., larger than the maximum finite distance). Thus, this limit is generally not important in practice (e.g., learning γ-discounted distances), where a large value and infinity are usually not treated much differently.
Optimizing quasimetric embeddings. From Thm. C.4, we know that optimizing PQEs over the training set S w.r.t. distortion achieves low distortion (and optimal violation by definition). While directly optimizing distortion (or error on log distance or distance ratios, equivalently) seems a valid choice, such objectives do not always train stably in practice, with possible infinities and zeros. Often more stable losses are used, such as MSE over raw distances or γ-discounted distances γd, for γ ∈ (0, 1). These objectives do not directly relate to distortion, except for some elementary loose bounds. To better theoretically characterize their behavior, an alternative approach with an average-case analysis might be necessary.
C.4 IMPLEMENTATION OF POISSON QUASIMETRIC EMBEDDINGS (PQES)
Sec. 5.2 mentioned a couple implementation techniques for PQEs. In this section, we present them in full details.
C.4.1 OUTPUTTING γ-DISCOUNTED DISTANCES
Recall the PQE quasimetric formulation in Eq. (14), for αi ≥ 0, and encoder f : X → Rd: d̂(x, y) , ∑ i αi ( 1− ∏ j P [Pois(µi,j(Ai,j(f(x)) \Ai,j(f(y)))) ≤ Pois(µi,j(Ai,j(f(y)) \Ai,j(f(x))))] ) .
(14)
With discount factor γ ∈ (0, 1), we can write the γ-discounted PQE distance as γd̂(x,y) = ∏ i ( γαi︸︷︷︸ a scalar that can take value in any (0, 1) )1− ∏ j P[Pois(µi,j(Ai,j(f(x))\Ai,j(f(y))))≤Pois(µi,j(Ai,j(f(y))\Ai,j(f(x))))]. (182)
Therefore, instead of learning αi ∈ [0,∞), we can learn bases βi ∈ (0, 1) such and define the γ-discounted PQE distance as
γd̂(x,y) , ∏ i β 1− ∏ j P[Pois(µi,j(Ai,j(f(x))\Ai,j(f(y))))≤Pois(µi,j(Ai,j(f(y))\Ai,j(f(x))))] i . (183)
These bases βi ∈ (0, 1) can be parametrized via a sigmoid transform. Consider quasimetric learning w.r.t. errors on γ-discounted distances (e.g., MSE). Unlike the parametrization with directly learning the convex combination weights αi’s, such a parametrization (that learns the bases βi’s) does not explicitly include γ and thus can potentially be more stable for a wider range of γ choices.
Initialization. Consider learning bases βi’s via a sigmoid transform: learning bi and defining βi , σ(bi). We must take care in initializing these bi’s so that σ(bi)’s are not too close to 0 or 1, since we take a product of powers with these bases. To be robust to different h numbers of quasipartition distributions, we initialize the each bi to be from the uniform distribution U [σ−1(0.52/h), σ−1(0.752/h)], (184) which means that, at initialization,∏
i∈[h] β0.5i = ∏ i∈[h] σ(bi) 0.5 ∈ [0.5, 0.75], (185)
providing a good range of initial outputs, assuming that the exponents (expected outputs of quasipartition distributions) are close to 0.5. Alternatively, bi’s maybe parametrized by a deep linear network, a similar initialization is employed. See Appendix C.4.2 below for details.

heading: C.4.2 LEARNING LINEAR/CONVEX COMBINATIONS WITH DEEP LINEAR NETWORKS
text: Deep linear networks have the same expressive power as regular linear models, but enjoy many empirical and theoretical benefits in optimization (Saxe et al., 2013; Pennington et al., 2018; Huh et al., 2021). Specifically, instead of directly learning a matrix ∈ Rm×n, a deep linear network (with bias) of l layers learns a sequence of matrices
M1 ∈ Rm1×n (186) M2 ∈ Rm2×m1 (187)
... ... (188)
Ml−1 ∈ Rml−1×ml−2 (189) Ml ∈ Rm×ml−1 (190) B ∈ Rm×n, (191)
where the linear matrix can be obtained with Ml Ml−1 . . .M2 M1 +B, (192) and we require min(m1,m2, . . . ,ml−1) ≥ min(m,n). (193)
In our case, the convex combination weights for the quasipartition distributions often need to be large, in order to represent large quasimetric distances; in Poisson process mean measures with learnable scales (e.g., the Gaussian-based measure described in Appendix C.2), the scales may also need to be large to approximate particular quasipartitions (see Appendix C.3.1).
Therefore, we choose to use deep linear networks to optimize these parameters. In particular,
• For the convex combination weights for h quasipartition distributions, – When learning the convex combination weights {αi}i∈[h], we use a deep linear network to
parametrize a matrix ∈ R1×h (i.e., a linear map from Rh to R), which is then viewed as a vector ∈ Rh and applied an element-wise square transform a→ a2 to obtain non-negative weights α ∈ [0,∞)h; – When learning the bases for discounted quasimetric distances βi’s (see Appendix C.4.1), we use a deep linear network to parametrize a matrix ∈ Rh×1, which is then viewed as a vector ∈ Rh and applied an element-wise sigmoid transform a → σ(a) to obtain bases β ∈ (0, 1)h.
Note that here we parametrize a matrix ∈ Rh×1 rather than R1×h as above for αi’s. The reason for this choice is entirely specific to the initialization scheme we use (i.e., (fullyconnected layer weight matrix initialization, as discussed below). Here the interpretation of a linear map is no longer true. If we use R1×h, the initialization method would lead to the entries distributed with variance roughly 1/n, which only makes sense if they are then added together. Therefore, we use Rh×1, which would lead to constant variance.
• For scales of the Poisson process mean measure, such as PQE-GG, we consider a slightly different strategy. Consider a PQE formulation with h× k independent Poisson processes, from which we form h quasipartition distributions, each from k total orders parametrized by k Poisson processes. The Poisson processes are defined on sets
{Ai,j}i∈[h],j∈[k], (194) use mean measures {µi,j}i∈[h],j∈[k], (195) and set parametrizations {u→ Ai,j(u)}i∈[h],j∈[k], (196) to compute quantities
µi,j(Ai,j(u) \Ai,j(v)) for u ∈ Rd, v ∈ Rd, i ∈ [h], j ∈ [k]. (197) Scaling each mean measure independently. Essentially, adding learnable scales (of mean measures) w ∈ [0,∞)h×k (or, equivalently, {wi,j ∈ [0,∞)}i,j) gives a scaled set of measures {wi,j · µi,j}i∈[h],j∈[k]. (198) This means that the quantities in Eq. (197) becomes respectively scaled as
wi,j · µi,j(Ai,j(u) \Ai,j(v)) for u ∈ Rd, v ∈ Rd, i ∈ [h], j ∈ [k]. (199) Convex combinations of all measures. However, we can be more flexible here, and allow not just scaling each measure independently, but also convex combinations of all measures. Instead of having w as a collection of h× k scalar numbers ∈ [0,∞), we have a collection of (h× k) vectors each having length (h× k) (or h× k-shape tensors)
{wi,j ∈ [0,∞)h×k}i∈[h],j∈[k], (200) and have the quantities in Eq. (197) becomes respectively scaled and combined as∑
i′,j′
wi,j,i′,j′ · µi′,j′(Ai′, j′(u) \Ai′,j′(v)) for u ∈ Rd, v ∈ Rd, i ∈ [h], j ∈ [k]. (201)
Note that these still are valid Poisson processes for a PQE. Specifically, the new Poisson processes are all defined over the product space (of original ones) with mean measuresA→∑
i′,j′
wi,j,i′,j′ · µi′,j′(Ai′,j′)  i∈[h],j∈[k] , for box A, (202)
and set parametrizations u→∏ i′,j′ Ai′,j′(u)  i∈[h],j∈[k] all boxes. (203)
Note that this generalize the case where each mean measure is scaled independently (as w can be diagonal). Therefore, we will apply this more general strategy using convex combinations of all measures. Similarly to learning the convex combination weights of quasipartition distributions, we collapse a deep linear network into a tensor ∈ Rh×k×h×k, and apply an element-wise square a → a2, result of which is used as the convex combination weights w to ensure non-negativity.
Initialization. For initializing the matrices (M1,M2, . . . ,Ml) of a deep linear network (Eq. (190)), we use the standard weight matrix initialization of fully-connected layers in PyTorch (Paszke et al., 2019). The bias matrix B (Eq. (191)) is initialized to all zeros.
When used for learning the bases for discounted quasimetric distances βi’s (as described in Appendix C.4.1), we have a deep linear network parametrizing a matrix ∈ Rh×1. We follow the same
initialization as above (including initializing B as all zeros). Consider the matrix up to be fore the last one:
M∗ ,Ml−1 ·M2 M1 ∈ Rml−1×1. (204) M∗ is essentially a projection to be applied on each row of the last matrix Ml ∈ Rh×ml−1 , to obtain bi (which is then used to obtain bases βi , σ(bi)). Therefore, we simply rescale the M∗ subspace for each row of Ml and keep the orthogonal space intact, such that the projections would be distributed according to the distribution specified in Eq. (184):
U [σ−1(0.52/h), σ−1(0.752/h)], , (184) which has good initial value properties, as shown in Appendix C.4.1.
C.4.3 CHOOSING h THE NUMBER OF QUASIPARTITION DISTRIBUTIONS AND k THE NUMBER OF POISSON PROCESSES FOR EACH QUASIPARTITION DISTRIBUTION
A PQE (class) is defined with h×k independent Poisson processes with means {µi,j}i∈[h],j∈[k] along with h× k set parametrizations {Ai,j}i∈[h],j∈[k]. For k pairs of means and set parametrizations, we obtain a random quasipartition. A mixture (convex combination) of the resulting h random quasipartitions gives the quasimetric. The choices of µ and A are flexible. In this work we explore PQE-LH and PQE-GG as two options, both using essentially the same measure and parametrization across all i, j (up to individual learnable scales). These two instantiations both perform well empirically. In this section we aim to provide some intuition on choosing these two hyperparameters h and k.
h the Number of Quasipartition Distributions Theoretical result Thm. C.4 suggest thats, for a quasimetric space with n elements, n2 quasipartition distributions suffice to learn a low distortion embedding. Since this is a worst-case result, the practical scenario may require much fewer quasipartitions. For instance, Appendix C.3.4 shows thatO(n) quasipartitions is sufficient for any quasimetric space with a tree structure. In our experiments, h ∈ [8, 128] quasipartition distributions are used.
k the Number of Poisson Processes for Each Quasipartition Distribution (Random Partial Order) It is well-known that such intersection of sufficiently many total orders can represent any partial order (Trotter, 1995; Hiraguchi, 1951). This idea is equivalent with the dominance drawing dimension of directed graphs (Ortali & Tollis, 2019), which concerns an order embedding of the vertices to preserve the poset specified by the reachability relation. In this graph theoretical view, several results are known. (Felsner et al., 2010) prove that planar graphs have at most 8 dimension. (Ortali & Tollis, 2019) show that the dimension of any graph with n vertices is at most min(wP , n2 ), where wP the maximum size of a set of incomparable vertices. A simpler and more fundamental result can be traced to Hiraguchi from 1951:
Theorem C.6 (Hiraguchi’s Theorem (Hiraguchi, 1951; Bogart, 1973)). Let (X,P ) be a partially ordered set such that |X| ≥ 4. Then there exists a mapping f : X → Rb|X|/2c such that
∀x, y ∈ X, xPy ⇐⇒ f(x) ≤ f(y) coordinate-wise . (174)
Thm. C.6 states that n2 dimensions generally suffice for any poset of size n ≥ 4. In our formulation, this means that using k = n2 Poisson processes (giving n 2 random total orders) will be maximally expressive. In practice, this is likely unnecessary and sometimes impractical. In our experiments, we choose a small fixed number k = 4.

heading: D EXPERIMENT SETTINGS AND ADDITIONAL RESULTS
text: Computation power. All our experiments run on a single GPU and finish within 3 hours. GPUs we used include NVIDIA 1080, NVIDIA 2080 Ti, NVIDIA 3080 Ti, NVIDIA Titan Xp, NVIDIA Titan RTX, and NVIDIA Titan V.

heading: D.1 EXPERIMENTS FROM SEC. 3.2: A TOY EXAMPLE
text: In Sec. 3.2 and Fig. 2, we show experiment results on a simple 3-element quasimetric space.
Quasimetric space. The quasimetric space has 3 elements with one-hot features ∈ R3. Thequasimetric and training pairs are shown in Fig. 9.
Unconstrained network. The unconstrained network has architecture 6-128-128-32-1, with ReLU activations.
Metric embedding. The embedding space is 32-dimensional, upon which corresponding metric is applied. The encoder network has architecture 6-128-128-32, with ReLU activations.
Asymmetric dot products. The embedding space is 32-dimensional. The two inputs are encoded with a different encoder of architecture 6-128-128-32, with ReLU activations. Then the dot product of the two 32-dimensional vector is taken, which parametrizes a distance estimate
Poisson Quasimetric Embeddings. The embedding space is 32-dimensional, which parametrizes 8 quasimetric distributions, each from 4 independent Poisson processes using (scaled) Lebesgue measure and half-lines. We use deep linear networks, as described in Appendix C.4.2. A deep linear network (without bias) of architecture 8-32-32-1 parametrizes the convex combination weights {αi}i∈[8]. Another deep linear network (without bias) of architecture 32-64-64-32 parametrizes convex combination weights of the mean measures d ∈ [0,∞)32×32. Note that these do not give many more effective parameters to PQEs as they are equivalent with simple linear transforms.
Optimization. All models are trained w.r.t. MSE on distances with the Adam optimizer (Kingma & Ba, 2014) with learning rate 0.0003 for 1000 iterations (without mini-batching since the training set has size 8).
Additional results. Results with additional formulations (together with the ones presented in Fig. 2) are shown in Fig. 10.

heading: D.2 EXPERIMENTS FROM SEC. 6: EXPERIMENTS
text: Triangle inequality regularizer. For methods that do not inherently respect triangle inequalities (e.g., unconstrained networks and asymmetrical dot products), we explore training with a regularizer that encourages following these inequalities. By sampling random triplets uniformly over the training set, the regularizer is formulated as,
Ex,y,z [ max(0, γd̂(x,y)+d̂(y,z) − γd̂(x,z))2 ] , (205)
where the γ-discounted terms and the squared form allows easier balancing with the training loss, which, across all experiments, are MSEs on some γ-discounted distances.
0
20
40
60
80
100
Count
Unconstrained Network (Output Distance)
(Training MSE = 0.02 ± 0.06)
0 10 20 30
Valid Range
(a) Unconstrained network that directly predicts distance.
0
20
40
60
80
100
Unconstrained Network (Output Square Root of Distance)
(Training MSE = 0.00 ± 0.02)
0 10 20 30
(b) Unconstrained network that predicts distance with a square a→ a2 transform.
0
20
40
60
80
100
Asym. Dot Product (Output Square Root of Distance)
(Training MSE = 0.00 ± 0.00)
0 10 20 30
(c) Asymmetrical dot product that predicts distance with a square a→ a2 transform.
0
20
40
60
80
100
Count
1 Space Embedding (Training MSE = 58.83 ± 0.00)
0 10 20 30
Valid Range
(d) Metric embedding into an `1 space.
0
20
40
60
80
100
Euclidean Space Embedding (Training MSE = 58.83 ± 0.00)
0 10 20 30
(e) Metric embedding into an Euclidean space.
0
20
40
60
80
100
Poisson Quasimetric Embedding (Training MSE = 0.02 ± 0.07)
0 10 20 30
(f) Poisson Quasimetric Embedding specified in Appendix D.1.
Figure 10: Training different formulations to fit training pairs distances via MSE, and using them to predict on the test pair. Plots show distribution of the prediction over 100 runs. Standard deviations of the training error are shown.
PQE settings. Across all experiments of this section, when given an encoder architecture mapping input to an Rd latent space, we construct PQEs according to the following general recipe, to obtain the two PQEs settings used across all experiments: PQE-LH (PQE with Lebesgue measure and half-lines) and PQE-GG (PQE with Gaussian-based measure and Gaussian shapes, see see Appendix C.2):
• (Assuming d is a multiple of 4,) We use h ,= d/4 quasipartition distributions, each given by k , 4 Poisson processes;
• A deep linear network (see Appendix C.4.2), is used for parametrizing the convex combination weights α ∈ Rd/4 or the bases β ∈ Rd/4 (see Appendix C.4.1), we follow the initialization and parametrization described in Appendix C.4.2, with hidden sizes [nhidden, nhidden, nhidden] (i.e., 4 matrices/layers), where nhidden , max(64, 21+dlog2(d/4)e). • For PQE-GG, – The learnable σ2measure ∈ (0,∞)d (one for each Poisson Process) is achieved by optimizing
the log variance, which is initialized as all zeros. – The Gaussian-based measures need learnable scales. We use a deep linear network to
parametrize the [0,∞)d×d weights for the convex combinations of measures, as described in Appendix C.4.2. Similarly, it has hidden sizes [nhidden, nhidden, nhidden] (i.e., 4 matrices/layers), where nhidden , max(64, 21+dlog2 de).
Note that the PQEs add only a few extra effective parameters on top of the encoder (d for PQE-HL, and d+ d2 for PQE-GG).
Mixed space metric embedding setting. Across all experiments of this section, when given an encoder architecture mapping input to an Rd latent space, we construct the metric embedding into mixed space as follows:
• (Assuming d is a multiple of 4,) We use (1) a (d/2)-dimensional Euclidean space (2) a (d/4)dimensional `1 space, and a (d/4)-dimensional spherical distance space (without scale). • Additionally, we optimize three scalar values representing the log weights of the convex combination to mix these spaces.
Error range. Results are gathered across 5 random seeds, showing both averages and population standard deviations.

heading: D.2.1 RANDOM DIRECTED GRAPHS QUASIMETRIC LEARNING
text: Graph generation. The random graph generation is controlled by three parameters d, ρun and ρdi. d is the dimension of the vertex features. ρun specifies the fraction of pairs that should have at least one (directed) edge between them. ρdi specifies the fraction of such pairs that should only have one (directed) edge between them. Therefore, if ρun = 1, ρdi = 0, we have a fully connected graph; if ρun = 0.5, ρdi = 1, we have a graph where half of the vertex pairs have exactly one (directed) edge between them, and the other half are not connected. For completeness, the exact generation procedure for a graph of n vertices is the following:
1. randomly add ρun · n2 undirected edges, each represented as two opposite directed edges; 2. optimize Rn×d vertex feature matrix using Adam (Kingma & Ba, 2014) w.r.t. Lalign(α =
2) + 0.3 · Luniform(t = 3) from (Wang & Isola, 2020), where each two node is considered a positive pair if they are connected;
3. randomly initialize a network f of architecture d-4096-4096-4096-4096-1 with tanh activations;
4. for each connected vertex pair (u, v), obtain du→v , f(feature(u)) − f(feature(v)) and dv→u = −du→v;
5. for each (u, v) such that du→v is among the top 1−ρdi/2 of such values (which is guaranteed to not include both directions of the same pair due to symmetry of du→v), make v → u the only directed edge between u and v.
We experiment with three graphs of 300 vertices and 64-dimensional vertex features:
• Fig. 11: A graph generated with ρun = 0.15, ρdi = 0.85;
• Fig. 12(not included in Sec. 6): A sparser graph generated with ρun = 0.05, ρdi = 0.85; • Fig. 13: A sparse graph with block structure by
1. generating 10 small dense graphs of 30 vertices and 32-dimensional vertex features, using ρun = 0.18, ρdi = 0.15,
2. generating a sparse 10-vertex “supergraph” with 32-dimensional vertex features, using ρun = 0.22, ρdi = 0.925,
3. for each supergraph vertex (a) associating it with a different small graph, (b) for all vertices of the small graph, concatenate the supergraph vertex’s feature to the
existing feature, forming 64-dimensional vertex features for the small graph vertices, (c) picking a random representative vertex from the small graph,
4. connecting all 10 representative vertices in the same way as their respective supergraph vertices are connected in the supergraph.
Architecture. All encoder based methods (PQEs, metric embeddings, dot products) use 64-128- 128-128-48 network with ReLU activations, mapping 64-dimensional inputs to a 48-dimensional latent space. Unconstrained networks use a similar 128-128-128-128-48-1 network, mapping concatenated the 128-dimensional input to a scalar output.
Data. For each graph, we solve the groundtruth distance matrix and obtain 3002 pairs, from which we randomly sample the training set, and use the rest as the test set. We run on 5 training fractions evenly spaced on the logarithm scale, from 0.01 to 0.7.
Training. We use 2048 batch size with the Adam optimizer (Kingma & Ba, 2014), with learning rate decaying according to the cosine schedule without restarting (Loshchilov & Hutter, 2016) starting from 10−4 to 0 over 3000 epochs. All models are optimized w.r.t. MSE on the γ-discounted distances, with γ = 0.9. When running with the triangle inequality regularizer, 683 ≈ 2048/3 triplets are uniformly sampled at each iteration.
Full results and ablation studies. Figs. 11 to 13 show full results of all methods running on all three graphs. In Fig. 14, we perform ablation studies on the implementation techniques for PQEs mentioned in Appendix C.4: outputting discounted distance and deep linear networks. On the simple directed graphs such as the dense graph, the basic PQE-LH without theses techniques works really well, even surpassing the results with both techniques. However, on graphs with more complex structures (e.g., the sparse graph and the sparse graph with block structure), basic versions of PQELH and PQE-GG starts to perform badly and show large variance, while the versions with both techniques stably trains to the best results. Therefore, for robustness, we use both techniques in other experiments.

heading: D.2.2 LARGE-SCALE SOCIAL GRAPHS QUASIMETRIC LEARNING
text: Data source. We choose the Berkeley-StanfordWebGraph (Leskovec & Krevl, 2014) as the largescale directed social graph, which consists of 685,230 pages as nodes, and 7,600,595 hyperlinks as directed edges. Additionally, we also use the Youtube social network (Leskovec & Krevl, 2014; Mislove et al., 2007) as a undirected social graph, which consists of 1,134,890 users as nodes, and 2,987,624 friendship relations as undirected edges. Both datasets are available from the SNAP website (Leskovec & Krevl, 2014) under the BSD license.
Data processing. For each graph, we use node2vec to obtain 128-dimensional node features (Grover & Leskovec, 2016). Since the graph is large, we use the landmark method (Rizi et al., 2018) to construct training and test sets. Specifically, we randomly choose 150 nodes, called landmarks, and compute the distances between these landmarks and all nodes. For directed graph, this means computing distances of both directions. From the obtained pairs and distances, we randomly sample 2,500,000 pairs to form the training set. Similarly, we form a test set of 150,000 from a disjoint set of 50 landmarks. For the undirected graph, we double the size of each set by reversing the pairs, since the distance is symmetrical.
Architecture. All encoder based methods (PQEs, metric embeddings, dot products) use 128- 2048-2048-2048-512 network with ReLU activations and Batch Normalization (Ioffe & Szegedy, 2015) after each activation, mapping 128-dimensional inputs to a 512-dimensional latent space. Unconstrained networks use a similar 256-2048-2048-2048-512-1 network, mapping concatenated the 256-dimensional input to a scalar output.
Training. We use 1024 batch size with the Adam optimizer (Kingma & Ba, 2014), with learning rate decaying according to the cosine schedule without restarting (Loshchilov & Hutter, 2016) starting from 10−4 to 0 over 80 epochs. All models are optimized w.r.t. MSE on the γ-discounted distances, with γ = 0.9. When running with the triangle inequality regularizer, 342 ≈ 1024/3 triplets are uniformly sampled at each iteration.
Full results. Tables 2 and 3 show full results of distance learning on these two graphs. On the directed Berkeley-StanfordWebGraph, PQE-LH performs the best (w.r.t. discounted distance MSE). While PQE-GG has larger discounted distance MSE than some other baselines, it accurately predicts finite distances and outputs large values for unreachable pairs. On the undirected Youtube graph, perhaps as expected, metric embedding methods have an upper hand, with the best performing method being an Euclidean space embedding.

heading: D.2.3 OFFLINE Q-LEARNING
text: As shown in Proposition A.4 and Remark A.5, we know that a quasimetric is formed with the optimal goal-reaching plan costs in a MDP M = (S,A,R,P, γ) where each action has unit cost (i.e., negated reward). The quasimetric is defined on X , S ∪ (S ×A). Similarly, Tian et al. (2020) also make this observation and propose to optimize a distance function by Q-learning on a collected set of trajectories. The optimized distance function (i.e., Q-function) is then used with standard planning algorithms such as the Cross Entropy Method (CEM) (De Boer et al., 2005). The specific model they used is an unconstrained network f : (s, a, s′)→ R, outputting discounted distances (Q-values).
Due to the existing quasimetric structure, we explore using PQEs as the distance function formulation. We mostly follow the algorithm in Tian et al. (2020) except for the following minor differences:
• Tian et al. (2020) propose to sample half of the goal from future steps of the same trajectory, and half of the goal from similar states across the entire dataset, defined by a nearest neighbor search. For simplicity, in the latter case, we instead sample a random state across the entire dataset.
• In Tian et al. (2020), target goals are defined as single states, and the Q-learning formulation only uses quantities distances from state-action pairs (s, a) ∈ S ×A to states s′: d̂((s, a), s′).
However, if we only train on d̂((s, a), s′), quasimetric embeddings might not learn much about the distance to state-action pairs, or from states, because it may simply only assign finite distances to d̂((s, a), s′), and set everything else to infinite. To prevent such issues, we choose to use state-action pairs as target goals, by adding a random action. Then, the embedding methods only need to embed state-action pairs.
In planning when the target is actually a single goal s′ ∈ S, we use the following distance/Qfunction
d̂((s, a), s′) , −1 + 1 |A| ∑ a′∈A d̂((s, a), (s′, a′)). (206)
Such a modification is used for all embedding methods (PQEs, metric embeddings, asymmetrical dot products). For unconstrained networks, we test both the original formulation (of using single state as goals) and this modification.
Environment. The environment is a grid-world with one-way doors, as shown in of Fig. 15, which is built upon gym-minigrid (Chevalier-Boisvert et al., 2018) (a project under Apache 2.0 License). The agent has 4 actions corresponding to moving towards 4 directions. When it moves toward a direction that is blocked by a wall or an one-way door, it does not move. States are represented as 18-dimensional vectors, containing the 2D location of the agent (normalized to be within [−1, 1]2). The other dimensions are always constant in our enviroment as they refer to information that can not be changed in this particular environment (e.g., the state of the doors). The agent always starts at a random location in the center room (e.g., the initial position of the red triangle in Fig. 15). The environment also defines a goal sampling distribution as a random location in one of the rooms on the left or right side. Note that this goal distribution is only used for data collection and evaluation. In training, we train goal-conditional policies using the goal sampling mechanism adapted from Tian et al. (2020), as described above.
Training trajectories. To collect the training trajectories, we use an -greedy planner with groundtruth distance toward the environment goal, with a large = 0.6. Each trajectory is capped to have at most 200 steps.
Architecture. All encoder based methods (PQEs, metric embeddings, dot products) use 18-2048- 2048-2048-1024 network with ReLU activations and Batch Normalization (Ioffe & Szegedy, 2015) after each activation, mapping a 18-dimensional state to four 256-dimensional latent vectors, corresponding to the embeddings for all four state-action pairs. Unconstrained networks use a similar architecture and take in concatenated 36-dimensional inputs. With the original formulation with states as goals, we use a 36-2048-2048-2048-256-4 network to obtain a R|A| output, representing the distance/Q-values from each state-action pair to the goal; with the modified formulation with state-action pairs as goals, we use a 36-2048-2048-2048-256-16 network to obtain a R|A|×|A| output.
Training. We use 1024 batch size with the Adam optimizer (Kingma & Ba, 2014), with learning rate decaying according to the cosine schedule without restarting (Loshchilov & Hutter, 2016) starting from 10−4 to 0 over 1000 epochs. Since we are running Q-learning, all models are optimized w.r.t. MSE on the γ-discounted distances, with γ = 0.95. When running with the triangle inequality regularizer, 341 ≈ 1024/3 triplets are uniformly sampled at each iteration.
Planning details. To use the learned distance/Q-function for planning towards a given goal, we perform greedy 1-step planning, where we always select the best action in A according to the learned model, without any lookahead. In each of 50 runs, the planner is asked to reach a goal given by the environment within 300 steps. The set of 50 initial location and goal states is entirely decided by the seed used, regardless of the model. We run each method 5 times using the same set of 5 seeds.
Full results. Average results across 5 runs are shown in Fig. 15, with full results (with standard deviations) shown in Fig. 16. Planning performance across the formulations vary a lot, with PQEs and the Euclidean metric embedding being the best and most data-efficient ones. Using either formulation (states vs. state-action pairs as goals) does not seem to affect the performance of unconstrained networks. We note that the the asymmetrical dot product formulation outputting discounted distance is similar to Universal Value Function Approximators (UVFA) formulation (Schaul et al., 2015); the unconstrained network outputting discounted distance with states as goals is the same formulation as the method from Tian et al. (2020).

Review summaries:
This paper studies the problem of learning of quasimetrics. It first proves that an orthogonal equivariant model cannot learn quasimetrics reliably, and then proposes the Poisson Quasimetric Embedding model which is both universal and differentiable. To be more precise, the Poisson process (or just a soft modification of Order Embedding) is differentiable and can be used to approximate quasipartitions, and quasipartitions can be used to approximate arbitrary quasimetrics.  The paper also conducts extensive experiments and indeed PQE has better performance for many tasks.

This paper considers the problem of learning Quasi-metrics. A quasi-metric is a non-negative function of two variables that satisfies the triangle inequality and that d(x,y) = 0 <=> x=y. Unlike metrics it does not satisfy triangle inequality.  In this paper, the authors define the quasi-metric learning problem. They then proceed to show that algorithms invariant to orthogonal transforms (in a sense they define - such that it includes unconstrained multi-layer perceptron) can not learn transforms satisfy the quasimetric constraints with probability at least 1/2 - o(1). They then define a program called Poisson Quasimetric Embeddings (PQEs) to learn quasimetrics - which come in two related flavours. They conclude with empirical evaluation of PQE and a variety of algorithms.

The paper proposes a Poisson Quasimetric Embedding (PQE) framework, that can be used to embed data to a quasimetric space. Quasimetrics are similar to distance metrics, except that symmetry property does not need to hold. The proposed PQE approach can be solved using gradient based methods.   In addition, the paper shows that many common learning algorithms provably fail to learn a quasimetric consistent with training data.