acceptodds
Desk rejected at ICLR 2027

Mind Your Marginals: What Governs Fidelity in Linearized Hierarchical Optimal Transport?

Desk rejected at ICLR 2027, so left out of the paper lists and the map.

55 views

Abstract

Linearized optimal transport (LOT) replaces the n(n-1)/2 transport solves needed to compare n measures with n offline embeddings into a tangent space at a fixed reference. We study LOT for hierarchical transport, where the ground metric between support atoms is itself a Wasserstein distance over a learned, coarsened support, and instantiate this construction (HiLOT) in text, graphs and images from one shared implementation. Our central finding is that fidelity is governed less by modality than by four construction-level choices, the first of which has been overlooked. (i) Orientation: a transport plan between measures on a shared atom set admits two barycentric projections, indexed by the measure or by the reference, and only the latter lies in a tangent space shared across objects. Across 24 arms in two modalities the benefit of correcting the orientation is proportional to the linearization gap it repairs (Spearman ρ = -0.946, p = 3×10^-12; ρ = -0.947 and -0.806 within graphs and images), reducing test error by up to 0.235 on a single benchmark. (ii) Plan density: an exact plan is a polytope vertex with at most n+m-1 nonzeros, so the embedding degenerates into a quantizer; entropic regularization removes this with a provably interior optimum. Orientation and regularization together close the gap to exact hierarchical transport on curated retrieval (0.1123 against 0.1121 NDCG@10, t = -0.04) at  100 queries/s against 1.5. (iii) Coarsening acts as capacity control, with a truncation sweep isolating coarsening rather than support truncation as the mechanism behind its one clear failure case. (iv) The component model is exchangeable and matters about as much as coarsening, an order of magnitude less than orientation. Across six text benchmarks the linearization preserves accuracy relative to exact hierarchical transport at 12 to 182 times its throughput.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
Optimal Transport, Hierarchical Optimal Transport, Linear Optimal Transport, Wasserstein Distance, Barycentric Projection, Entropic Regularization, Sinkhorn Algorithm, Topic Models, Graph Kernels, Weisfeiler-Leman, Document Retrieval, Nearest Neighbor Search, Efficient Similarity Search

Reviews

Among:
Shape:
1234this paper, Bottom 1%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.00 over 4 reviews, above 0% of the others.
Reviewer_om8GOpenReview ↗
Rating
1
Confidence
2
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

This paper studies hierarchical optimal transport by proposing HiLOT. Its main contribution is largely an empirical study of how different choices in HiLOT affect OT performance.

Critical strengths

S1. Hierarchical LOT is an interesting setting. S2. Hierarchical LOT outperforms HOTT in some tasks evaluated in the experimental study.

Critical weaknesses
  1. The motivation of hierarchical LOT is weak. Table 3 shows that BM25 and sentence encoder are apparently the better choice of the retieval, so why bothering optimizing hierarchical OT with LOT? There can be tasks that hierarchical OT suits best and thus HiLOT is the optimized choice but this should be elaborated more.

  2. The baselines are weak. It only compares HiLOT's own variants and HOTT. Fast OT approximations should also be compared and see if it can have similar quality and performance trade-off compared to HOTT.

  3. The observation regarding the orientation is largely an empirical finding, rather than ``an orientation law''.

  4. The presentation needs improvement. For instance, the setup of Section 3 is brief with unnecessarily heavy use of notations without proper explanations. Section 6 is too dense with numbers and reporting without proper explanations of the results.

  5. The evaluation does not tell whether HiLOT's accuracy comes from transport or whether the embedding is faithful to HOTT.

  6. The evaluation does not tell whether HiLOT's accuracy comes from transport or whether the embedding is faithful to HOTT.

Questions for authors

n/a

Reviewer_C8rcOpenReview ↗
Rating
1
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper applies linearized optimal transport to hierarchical transport, where the cost between components is itself a Wasserstein distance over atoms, and tests the resulting method (HILOT) on text, graphs, and images. It argues that linearization quality depends mainly on four design choices: which marginal indexes the barycentric projection, entropic regularization of the plan, coarsening of the support, and the component model.

Critical strengths
  1. Paper is well written and easy to follow

  2. Thorough, controlled ablations with paired comparisons on identical splits.

  3. Honest reporting of negative and inconclusive results.

Critical weaknesses
  1. The orientation contribution needs clearer positioning. Reference indexed projection is the standard LOT convention, as Section 4.1 acknowledges through Wang et al. (2013). The results mainly demonstrate the cost of departing from that convention. This is useful, but framing it as an overlooked choice overstates its novelty. Although Tables 4 and 21 include reference indexed results on two text datasets, the full classification comparison in Table 1 still uses source indexing. Please evaluate the standard construction consistently across all tasks.

  2. The orientation law is affected by mathematical coupling. With G=eSRC−eexactG=e_{\mathrm{SRC}}-e_{\mathrm{exact}} and Δ=eREF−eSRC\Delta=e_{\mathrm{REF}}-e_{\mathrm{SRC}}, we have Δ=−G+(eREF−eexact)\Delta=-G+(e_{\mathrm{REF}}-e_{\mathrm{exact}}). A strong negative association therefore follows when reference indexed error stays close to exact transport error. Moreover, the 24 arms are not independent; MNIST contributes six. Please report reference indexed residuals and paired orientation effects directly, with uncertainty accounting for dependence within datasets.

  3. The theoretical claims need qualification. Proposition 2 applies to an optimal basic feasible solution, but the entropic limit in Proposition 3 need not be a vertex when exact optima are nonunique. Its sparsity conclusion therefore requires additional assumptions. Likewise, positivity of the entropic plan and the limiting formulas do not prove an interior optimum of downstream accuracy in ε\varepsilon. Prior work on entropic barycentric projections, including Pooladian and Niles-Weed, should also be discussed.

  4. The performance claims are too broad. The corrected entropic method in Table 3 achieves approximately 63 and 84 times the throughput of exact HOTT, rather than three to four orders of magnitude. Table 1 also does not uniformly support preserved accuracy: LOTT 10 increases error from 0.036 to 0.070 on BBCSPORT and from 0.062 to 0.093 on REUTERS. The retrieval gap to BM25 and the sentence encoder further limits practical competitiveness, although the authors acknowledge this.

I suggest using standard LOT as the default baseline, separating orientation effects from the shared term correlation, qualifying the entropic claims, and reporting accuracy and speed for the same configurations.

Questions for authors

Please see the weakness section.

Reviewer_S97bOpenReview ↗
Rating
1
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper studies how to speed up hierarchical optimal transport, where objects are mixtures of components and the distance between components is itself computed by OT. Each object is transported to a shared reference and represented as a vector, allowing later comparisons without solving OT for every pair. The experiments cover text, graphs, and images. They examine how projection direction, entropy regularization and component choice affect speed and accuracy. On two text retrieval benchmarks, suitable settings achieve similar retrieval quality to exact hierarchical OT at higher speed.

Critical strengths
  1. The controlled comparisons across modalities, paired evaluations, and validation-based orientation selection are useful. Reference orientation lowers error in 17 of Table 19's 24 arms, including all ten image arms. The paper also reports negative results and distinguishes its protocol from published graph/image benchmarks.
  2. The curated retrieval experiments show a promising speed–quality tradeoff within the hierarchical-transport family, while clearly acknowledging stronger modern retrieval baselines.
Critical weaknesses
  1. The algorithmic novelty is limited. The method combines hierarchical OT, a shared-reference embedding, and standard component models. Its main added value is the theoretical and empirical explanation of this combination, but that explanation has important gaps.
  2. The need for the chosen hierarchy is not sufficiently justified. Topic models, clustering, and truncation change both the representation and the distance. The ablations show mixed benefits over flat OT, without a clear rule for when the hierarchy is worth its cost. The text results also fall below BM25 and the sentence-encoder baseline, leaving the practical use case unclear.
  3. The final embedding can lose information used by the nested OT cost. Components with different distributions can have the same mean, causing distinct objects to map to identical vectors even when their hierarchical OT distance is positive. The paper gives no applicable distortion guarantee for this discrete construction.
  4. Proposition 3 does not support the claimed “provably interior optimum.” The zero-entropy limit need not be a basic optimal plan [1], and the infinite-entropy statement fails for sparse supports under the stated zero-filling convention. Neither endpoint proves an interior optimum of retrieval quality.
  5. The orientation “law” is weakened by mathematical coupling: both axes contain SRC with opposite signs, so a strong negative correlation is partly built into their definitions. Reusing datasets across arms adds another source of dependence. The headline correlation and p-value therefore do not establish the claimed general relationship.
  6. The scalability analysis is incomplete. Reducing the number of OT solves does not make all-pairs comparison linear; vector search still has a quadratic term. Component fitting, nested cost construction, and embedding storage also need to be counted. Stage timings are provided, but there are no complete time and space bounds or peak-memory scaling results.

[1] Computational Optimal Transport.

Questions for authors
  1. When does the hierarchy improve on flat OT? What information is lost through clustering and truncation?
  2. What are the total time and memory costs, including construction and search?
  3. Can you revise Proposition 3 for nonunique optimal plans and sparse supports? What proves an interior optimum?
  4. Can you account for the shared SRC term in the orientation analysis? Does the embedding use σi\sqrt{\sigma_i} weights?
Reviewer_uwJ8OpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
1
Soundness
3
Read review
Paper summary

This paper explores a method to alleviate the computational burden of hierarchical optimal transport, which is doing optimal transport over optimal transport: equivalently, using the Wasserstein distances on a base space which is itself a space of probability measures endowed with the Wasserstein metric. The first step is the computation of the underlying Wasserstein distances on the base space which can be done once for all. Then, it linearizes the second step of optimal transport at a given reference measure. They construct a vector for each distribution by averaging their mean through the given plan: here there are two different choices of averaging: with respect to the source or the reference measure. The main finding is that reference-indexed most often outperforms source-indexed averaging. Alos, moderate entropic regularization can help. Their experiments demonstrate substantial speedups with sometimes comparable downstream performance to exact hierarchical transport.

Critical strengths

Explore a possible but not natural method and prove empirically that it does not work. Empirically show that entropic regularization can help.

Critical weaknesses

This finding (mind your marginal) is rather expected. The contrary or the opposite result (average with respect to source) would have been an important result. The most important weakness of the paper is the writing style, which feels like an LLM report and not pedagogical at all.

Questions for authors

Other feature maps could have been chosen for your averaging. Have you tested it? An ablation study on that point could be also interesting.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Discussion (0)

Sign in to comment.