acceptodds
Under review as a conference paper at ICLR 2027

Latent Distance Denoising in Metric Measure Spaces

Abstract

Pairwise observations often encode a noisy monotone transform of an unobserved distance. We study how to denoise all latent pairwise distances when the underlying points are sampled from a metric measure space governed only by lower volume-growth bounds, without assuming coordinates, curvature, or a fixed dimension. Our observable neighborhood construction converts internal similarity into controlled-radius clusters and then denoises distances by independent cluster-to-cluster averaging. At any fixed target accuracy, the resulting algorithm produces uniform latent-distance estimates in near-linear time up to polylogarithmic factors. With 1,200 sampled points, controlled simulations reduce normalized mean absolute error from 0.107 to 0.022 on an interval and from 0.112 to 0.047 on a branching metric tree. We also give an exhaustive procedure that reaches finer resolution, together with an indistinguishability lower bound showing that lower volume growth alone cannot guarantee arbitrarily accurate denoising. The results expose a statistical-computational tension: fixed-accuracy denoising is efficient in general metric measure spaces, while the finer resolutions certified by our assumptions require substantially more computation.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
Latent Metric Recovery, Metric Measure Spaces, Noisy Pairwise Observations, Distance Denoising

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_4VEvOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper studies recovery of the full latent pairwise distance matrix from noisy and possibly missing pairwise observations. The latent points are sampled from a metric probability space, and the conditional mean of each pairwise observation is given by a monotone function of the corresponding latent distance. It doesn't assume coordinates, dimension, or a manifold representation; the paper constructs neighborhood proxies using only pairwise measurements.

Under a lower-mass condition and regularity assumptions on the link function, the method recovers latent distances at a target scale rr. When the link is known and globally bi-Lipschitz, it achieves uniform additive O(r)O(r) error over all pairs under the condition snϕ(r)r2≳log⁡2nsn\phi(r)r^2 \gtrsim \log^2 n. At fixed target accuracy, the proposed construction has near-linear time. The paper also considers locally informative and unknown link functions, and provides computational hardness and information-theoretic lower-bound results describing some limitations of the framework.

Critical strengths
  • The paper identifies an interesting abstraction under which latent pairwise distances can be recovered without relying on many of the geometric assumptions commonly used in latent-space reconstruction, such as fixed dimension, curvature, tangent approximations, or an ambient Euclidean representation. It is interesting that a relatively weak lower-mass condition is sufficient for a nontrivial uniform recovery guarantee.

  • The algorithmic development is motivated by a relatively intuitive observation: a sufficiently large local proxy provides enough pairwise observations for concentration, while a sufficiently small latent radius controls the geometric bias introduced by averaging.

Critical weaknesses
  • While the theoretical problem itself is interesting, I found the practical motivation insufficiently developed. The paper discusses several model classes covered by the framework but these are primarily examples of compatible statistical models. It remains unclear in what real-world setting recovering the entire latent distance matrix under this particular observation model would directly solve a practically relevant problem. The problem formulation currently feels somewhat specialized and theoretically motivated.

  • The guarantees rely on several quantities that may be difficult to know in practice, including the lower-mass profile ϕ\phi and local regularity parameters of the link function. The observation model also assumes an exact monotone link between latent distance and the conditional mean of each pairwise observation. It is unclear how robust the method is to misspecification of these assumptions.

Questions for authors
  • What concrete downstream applications motivate recovery of the entire latent distance matrix? The paper explains that the framework contains several existing statistical model classes, such as latent-space networks and random geometric graphs, but it is less clear what real-world task directly benefits from the proposed form of metric recovery.

  • The manuscript states uniform recovery of all pairwise distances while also claiming near-linear runtime at fixed accuracy. Since explicitly materializing an n×nn\times n distance matrix requires Ω(n2)\Omega(n^2) output time, could the authors clarify the output model underlying the runtime claim?

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

The paper studies how to recover hidden distances from noisy and possibly missing pairwise observations. It constructs groups of nearby vertices without knowing their locations, then averages observations between these groups to estimate distances. It provides accuracy and runtime guarantees, together with a lower bound. Experiments on an interval and a branching tree show reduced error although they use simplified versions of the theoretical algorithm.

Critical strengths
  1. The main idea is understandable, but important assumptions and proof details require careful reading of the appendix (which I couldn't do).

  2. Constructing reliable neighborhoods directly from noisy observations offers a useful approach to distance estimation in general metric spaces (up to some acceptable assumptions).

  3. The main strength is the construction of nearby groups without coordinates or smoothness assumptions. Combining these groups with independent measurements provides a useful way to control both noise and geometric error.

Critical weaknesses
  1. It is not clear how well the full method would work in real applications. The algorithm may be slow and the experiments test simpler methods on artificial data. However this is not a major concern by itself since the paper mainly focuses on theory.

  2. The near-linear runtime (Corollary 3.3) holds only when the resolution, observation rate, and local mass are all fixed constants. When the resolution shrinks with nn, the runtime bound grows exponentially through the factor in Theorem 3.1. The paper does not discuss how quickly this cost grows.

Questions for authors
  1. When pp is unknown, are any additional assumptions needed for recovery up to global factor?
  2. How can the method return all pairwise distances in near-linear time?
Reviewer_ihxBOpenReview ↗
Rating
1
Confidence
2
Informativeness
2
Presentation
1
Soundness
1
Read review
Paper summary

The paper studies the problem of recovering latent distances in metric measure spaces when given access to potentially missing noisy observations of the distances. Here "observation" is not directly the metric itself but a monotone function of the metric. The paper provides an algorithm to reconstruct these distances which works via several steps. The algorithm essentially constructs a cluster of neighbors for every point and then the average measurements between the clusters are eventually used to recover the latent distances. The paper also has some assumptions (some of which seem to be standard in this literature) that are necessary for the algorithmic guarantees. They also provide some experimental results on the interval [0,1] and an eight-arm metric tree.

Critical strengths

None

Critical weaknesses

Corollary 3.2(3) is false under the stated assumptions. Consider three uniformly weighted points with distances (ab,bc,ac)(ab,bc,ac) equal to (1,1,2)(1,1,2) in one model and (1,1,3/2)(1,1,3/2) in another. Define, for t∈[0,2]t\in[0,2],

p_1(t)= \begin{cases} 0.8-0.2t,&0\le t\le1,\\\\ 1-0.4t,&1<t\le2, \end{cases}$$ and extend both constantly beyond $2$. Both models satisfy the same parameters $r_p=r_\mu=2$, $\ell_p=0.2$, $L_p=0.4$, and lower-mass profile $\phi(r)=1/3$. Set $s=1$ and use conditionally independent Bernoulli observations with means $p_j(d_j(X_u,X_v))$. These means are identical in both models: $0.8$ for equal locations, $0.6$ for $ab,bc$, and $0.4$ for $ac$. Thus the complete observation laws are identical for every sample size, but the metrics are not proportional: their long-to-short distance ratios are $2$ and $3/2$. Therefore, no estimator can distinguish them up to global dilation. Which stated assumption excludes this example? **The reproducibility statement (lines 491–497) does not correspond to the experiments in this paper**: it describes instruction backbones, public benchmarks, and counterfactual intervention traces, none of which appear in this paper's experiments. It also states that anonymized code and supplementary materials are provided but I could not find the promised supplementary material on the submission page.
Questions for authors

Clarification questions:

The abstract states "Controlled simulations reduce average error by 86% on an interval and 77% on a branching metric tree". Compared to what?

The writing assumes uneven background knowledge: it expands “NP” on line 246 but uses notation like ≲,≳,≍\lesssim,\gtrsim,\asymp without definition.

Experimental details of the paper are underspecified: Please specify the sampling measure and procedure used to generate the latent points on the [0,1][0,1] interval and the eight-arm metric tree, including the tree’s arm lengths, probabilities of selecting each arm, and distribution of positions along an arm. Were points sampled iid or placed deterministically, and were distances normalized using the underlying space’s diameter or the realized sample diameter?

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.