Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: 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.
main_review: I am impressed by the long proof of the failure case construction in the appendix. But the statement of the Theorem 4.5 and the base case construction (Figure 3) is confusing. It seems that the orthogonal transformation is not essential in this result. Only thing that matters is that the action is at least nontrivial. Then we can identify different points y ~ y', w ~ w' and do the same trick. 

Once we identify those points, the result becomes obvious: We have a quasimetric in one space, but we cannot define the pushforward of the quasimetric directly to a quotient space. It can fail to be a quasimetric. d(x, y) = d(y, w) = d(w, z) = 1 and d(w, z) = c for c large are just two contradictory statements. You can even get a simpler counterexample by considering d(x, y) = 1 and d(x, y') = c. (If the construction in Figure 3 is allowed, I don't see why this easier one is not allowed.) In other words, if we train an equivariant model on a space where there is actually no equivariance, the model will fail. The author can explain more clearly what Theorem 4.5 means and what are the intended implications.
summary_of_the_review: The paper is organized nicely and I have no difficulty following the proof. I think the paper provides a valuable contribution for the learning of quasimetrics and would be useful for many real world applications.

I consider this paper to be marginally above the acceptance threshold.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper is concerned with learning asymmetric distance functions (that is, quasimetrics) from a sample. The authors prove that a certain class of algorithms fails to properly learn these spaces, and instead propose the "Poisson quasimetric embedding" as a tool to learn these functions.
main_review: Firstly, the topic under consideration is important and timely. Less structured spaces are frequently encountered, and learning algorithms tend to be developed with very restrictive settings in mind.

One highlight of the paper is Lemma 4.4, which rules out some common approaches to distance learning for this problem. The proof seems to me to be relatively straightforward. 

My most significant reservation comes from Theorem 5.2, which is the theoretical justification behind the Poisson embedding: There we find a guarantee of distortion O(t log^2 n) for the embedding, and this is exceptionally high. Even the hopeless task of embedding metric space into Euclidean space gives smaller distortion O(logn) by Bourgain's theorem. The authors point to a result of Memoli, but the goal of that paper is quite different than the current one: That paper embeds into an ultrametric - a very restrictive space - and this allows them to  approximate a difficult computational task. So the distortion translates to approximation, which is more reasonable, but even then the dependence on the treewidth is problematic. The task of the current paper is to estimate a distance, and I find that the large distortion undermines this approach.

Some more minor concerns: 
- I'm confused by the statement of Theorem 4.5: What's undesirable about S containing only few pairs? And why should a 50% probability be objectionable? Based on this bound alone, the random embedding could be repeated multiple times until finding one that is a good match for the sample.
- Why would use test your method against a metric embedding into Euclidean space? That embedding doesn't seem remotely appropriate for the problem under consideration.
summary_of_the_review: The paper has some nice positive contributions, but I have concerns about the overall theoretical foundation of the work.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: 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.
main_review: The problem of learning Quasi-metrics is an interesting problem with many applications. The proof of the fact that algorithms invariant to orthogonal transforms can not learn quasimetric functions is quite neat. The formulation of the PQEs is also quite nice. The paper is quite well written as well with toy examples which help pedgogically. 

One complaint I have is that the empirical results are over just 5 trials. 
summary_of_the_review: The paper examines an interesting problem. They propose an interesting program to solve the problem, with some analysis to show a class of algorithms can not be used to learn quasimetrics. It is also well written. Hence I recommend acceptance.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: 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.
main_review: Strength:

- The paper is well written for most of time. The problem of learning quasimetrics is interesting, and the motivation is clear.

- The large scale experiments in Table 2 and Table 3 look promising. It is interesting to see that in directed networks, the proposed method works fairly well compared to the baselines. 

Comments:

- It is mentioned in Section 3: "These objectives also indirectly capture generalization because a predictor with bad approximation or that ignores quasimetric constraints must have large error on some possible pairs." Could the authors elaborate on that? 

- In particular, is there any relationship between quasimetric violation (Definition 4.2) and the generalization bound?

- If my understanding is correct, the regular (symmetric) metric is no more than a special case of the quasimetric. I wonder if there is any possible explanation for the undirected case (Table 3), in which the proposed method performs worse than some symmetric methods. Is this because of some overfitting on the training network? 

- It seems that the acronym NTK is never defined.

- I did not check the proofs.
summary_of_the_review: Overall an interesting paper with solid theoretic and experimental results. I am not an expert in this area though, hence I cannot say how novel the approach is.
review_title: null

Meta-review: The reviewers agree that the paper is addressing an interesting problem, and provides a valuable contribution for the learning of quasimetrics and would be useful for many real world applications.
Decision: Accept (Poster)