acceptodds
Under review as a conference paper at ICLR 2027

Robust Geodesic Learning via Hierarchical Connectivity

Abstract

Geodesic rank is a fundamental signal for manifold learning, but it is difficult to recover when low-dimensional structure is embedded in a high-dimensional noisy ambient space. Irrelevant ambient coordinates can dominate nearest-neighbor relations, making graph-based methods unstable. We study robust geodesic learning as the problem of recovering both geodesic rank and topological structure under such noise. We propose AGD-SS, a dissimilarity measure built from random agglomerative hierarchical clustering forests. For each subsample, AGD-SS projects query points onto the sampled dendrogram and aggregates merge heights in the subtree rooted at their lowest common ancestor, using hierarchical connectivity rather than raw ambient neighborhoods. This construction connects geodesic learning with minimum spanning trees and 0-dimensional persistent homology, and supports a stability analysis of the estimator under perturbation. Experiments on synthetic manifolds, non-Euclidean settings, the Drosophila connectome, and single-cell datasets show that AGD-SS preserves local and global geodesic rank while recovering topological structure under ambient noise. These results suggest that hierarchical connectivity provides a simple inductive bias for robust representation learning that preserves both geometry and topology.

Primary area:
unsupervised, self-supervised, semi-supervised, and supervised representation learning
Keywords:
Robust geodesic learning, Manifold learning, Hierarchical connectivity, Persistent homology, Geometry and topology

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 3 reviews, above 0% of the others.
Reviewer_Z4r7OpenReview ↗
Rating
1
Confidence
3
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

The paper proposes to use Agglomerative Hierarchical Clustering (AHC) applied to random subsamples, followed by the respective subtree summation (SS). The resulting method AGD-SS is then a SS dissimilarity from random AHC forests. The paper aims to make the connection of AGD-SS with persistent homology (PH), discusses some theoretical stability results and evaluates it on real and synthetic data. I'd say the main strength of AGD-SS is its simplicity and tractability. While there's a potential, the paper in its current form seems to be quite far in terms of conveying novelty and clearly delineating the AGD-SS contributions from the already existing tools.

Critical strengths

The AGD-SS method is simple and tractable.

Critical weaknesses

While the paper overall reads well, it seems to be half-baked in its current form both in terms of methods and experiments.

The paper is vague mathematically. For example, the authors state "Manifold Topology Preservation: The method must correctly identify the topology (Persistent Homology (Chazal & Michel, 2021; Hausmann et al., 1995)) of the dataset." How is topology of the data defined and what is the relation to PH? One option is to formalize it through nerves and the Nerve theorem but it is not done.

Nothing is said on the dimension of topological features. Is it H_0 or H_1? So what is preserved then?

What is the selected scale ν\nu in the PH pipeline? How sensitive the validation results to the choice of ν\nu and the simplicial complex?

The paper does not present a proper comparison with the baselines, and overall, the list of competitors is very limited. For example, how do the kernel based methods perform here?

There is no ablation and sensitivity analysis.

Most importantly, the presented experiments do not convey sufficiently strongly why we need geodesic distances, that is, the epsilon that the existing methods cannot provide but AGD-SS brings. Examples from functional data analysis may be a potential source to highlight geodesic learning.

Questions for authors

See weaknesses above.

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

This paper introduces a new method for inferring geodesic rank (not distance) in high-dimensional noisy data. This is useful for recovering the ground-truth k nearest neighbors of a query point, which is a common starting point for many algorithms. They validate their methodology on synthetic data sets as well as several real-world data sets (a connectome network and transcriptomics data).

Critical strengths

The paper is well written and easy to follow. The authors included rigorous experiments and they were transparent about AGD-SS performance in comparison to other common methods. It is definitely an improvement compared to geodesic forests (GF), which you can especially see in Figure 5.

Critical weaknesses
  1. Missing comparisons with modern geodesic-distance estimation algorithms in the literature. For example: Budninskiy et al (2019), Sober et al (2020), Arvanitidis et al (2019), Li and Dunson (2019), Fefferman et al (2025). I'd especially look at Budninskiy et al (parallel transport unfolding) because I think it does pretty well with noisy high-dimensional data. One step of PTU involves projecting to the local tangent space, which is one way of dealing with ambient noise, if you can get a decent tangent space approximation.

  2. AGD-SS performance seems comparable to Isomap and other established algorithms, based on the experiments that are presented in the paper. My experience is that Isomap really doesn't handle noise very well at all compared to some of the methods listed above. The authors claim that the main contribution of AGD-SS is that it's designed to handle high-dimensional noise, so it should do a lot better than Isomap.

  3. My understanding is that the output of the algorithm is only geodesic rank (relative ordering of geodesic distances), not the geodesic distances themselves.

Questions for authors

Major: For the connectome data set, I am confused by what you mean by "neurons within the same class are treated as manifold neighbors". Are you saying that you defined the neighborhood of each point to be every other point in its class? My experience working with connectome data (not this particular data set) is that the networks are usually weighted by synaptic strength, so you could define a node's neighborhood as neighboring nodes with highest weight. Or you could simply use the 1-hop neighborhood or k-hop neighborhood for some small k. Any of those options would be more principled than using the entire class, if that's what you're doing.

Minor:

  1. In Figure 2, is noise sigma = 20 correct? That seems high.
  2. What am I looking at in Figure 4 (left)? What are the coordinates of the points?
  3. For the additional scRNA-seq data sets, do we know if there's supposed to be an underlying loop or not? Is a high score good or bad?
Reviewer_YXvzOpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
2
Soundness
1
Read review
Paper summary

Given a set of points in R^n that are assumed to come from a low-dimensional manifold (with noise), this paper considers the problem of estimating the geodesic distances between all pairs of points. Two methods are defined in the paper: AGD and AGD-SS, both are defined as averages over tree distances based on hierarchical clustering of subsamples.

First a subsample S is drawn, then the points assigned representatives in S by mapping them to their nearest neighbor in the subsample: x -> \phi_S(x) and y -> \phi_S(y). The AGD distance between the points x,y is defined as a sum of h(w) for all nodes w in the shortest path (in the hierarchical tree) between \phi_S(x) and \phi_S(y). AGD-SS sums h(w) for all nodes in the minimal subtree that contains both \phi_S(x) and \phi_S(y). Both AGD and AGD-SS are averaged over subsamples. If I understand correctly, h(w) is the height of the node from the leaf. The paper doesn't really make it clear and just calls it "node heights (linkage values) h(·).".

The methods AGD/AGD-SS are compared to diffusion distances, geodesic forests and a few other methods that vary between datasets (e.g. t-SNE, UMAP).

Critical strengths

The problem of inferring pairwise distance from a noisy sample on a manifold is important and I am happy that the authors have decided to focus on it.

Critical weaknesses
  1. I find the clarity of writing to be lacking. The manuscript uses the term "Geodesic rank" multiple times (3 times just in the abstract) but never bothers to define it. I can infer that the term rank refers to position in a list of points sorted by their distance to a source point. However, this should really be defined in the paper since it is not standard. A web search found a math paper with a definition of geodesic rank that defines it to be something entirely different [1]. Even the writing of the abstract is sloppy. Some examples:
  • "We study robust geodesic learning [...] under such noise." but nothing was said about the noise prior to this.
  • "in a high-dimensional noisy ambient space" - it is not the ambient space that is noisy.
  1. The authors never explain why AGD/AGD-SS sums over node heights h(w) instead of just counting the length of the path or size of the subtree. I've asked Claude Opus 5.5 to run a quick simulation to compare AGD-SS with a variant that simply counts the subtree size. Here is Claude's summary of its simulation results: "Using the subtree size instead of the summed heights never hurts AGD-SS. It wins in every one of 360 paired configurations, but only by +0.004 on average at ψ=32 (+0.007 at ψ=128). So the height weighting isn’t contributing anything you can measure.

    Setup (matches the paper as closely as I could work it out)

    Data: sklearn S-curve and Swiss roll, N=1000, with c ∈ {0,2,…,10} added Gaussian noise dimensions at σ=20, then z-scored. Tree settings: single linkage, ψ=32 (the paper’s default) and ψ=128, t=100, no random projection. Ground truth: shortest paths on a 10-NN graph of the clean 3-D data. Replication: 3 repetitions. All variants share the same random subsets, so each comparison is paired. Check against the authors’ code: my tree statistics for AGD and AGD-SS match theirs to machine precision on a test tree. "

The fact that a simpler variant beats AGD-SS on simple benchmarks really makes me question the depth of thinking and experimentation that went into this work.

  1. Empirically the methods do not seem to fair any better than existing methods such as diffusion distances. Overall, I do not see why a practitioner would choose these methods over others. See for example Figure 4, Figure 8, and Section E.5 in the supplementary.

  2. Both AGD and AGD-SS involve multiple rounds of hierarchical clusterings on random subset. It appears it would be very slow to run the methods on large data sets with large subsamples (as the authors acknowledge in C.1), However, no complexity analysis is included and no runtime benchmarks to compare it against other more established methods.

  3. There are multiple issues with the main Theorem 4.5. First, the upper bound becomes worse as the size of the subsample increases, which is at odds with what one would expect. Second, it makes an assumption that "with probability at least 1−\alpha over S, the query leaves attach to corresponding nearest representatives in S and S' when constructing AHC from points S \cup {x,y} / S'\cup {x', y'}". This is an odd choice for an assumption of a mathematical theorem. It is not clear why it should hold in general and the authors only demonstrate it empirically on some artificial datasets in Section B.2.1 of the supplementary. Essentially, the authors are assuming stability (of the tree structure) in order to prove stability (of AGD-SS). Third, it appears there may be a serious bug in the proof. Claude claims that the claim in line 744 does not follow from the condition \epsilon_S and found a counter-example. I cannot see why it would follow but admit I only did a shallow reading and did not invest a lot of time digging into this issue since I believe the paper will be rejected in any case, based on the other issues that I mentioned above. Here is Claude Opus's report on this issue for the benefit of the authors:

"The proof of Theorem 4.5 breaks at its only nontrivial step (App. B.2, l. 744). That step claims that, on the event E_S, the LCA-subtree sums before and after perturbation differ by at most 2(ψ+1)δ. It rests on the parenthetical at ll. 726-727, which says E_S implies a 2δ-matching between the merge heights in the two LCA subtrees. It does not. E_S only says that the queries attach to corresponding representatives. It says nothing about which other sample points lie under their LCA. That set of points is a single-linkage cluster, and cluster membership is discontinuous. A δ-perturbation moves every merge height by up to 2δ, so any point whose merge level is within 4δ of the LCA height can enter or leave the subtree. When that happens, whole merge heights are added to or removed from the sum. Bottleneck stability does not help. It matches all death times of S with all death times of S’, not the ones inside one subtree with the ones inside the other. Counterexample: take ψ = N = 3 and X = {x=(0,0), y=(1,0), c=(2+ε,0)}. Then S = X, and E_S holds with α = 0. Move y by +δ and c by -δ, with ε < 3δ. Now y’ and c’ merge first, so the LCA subtree of (x’,y’) becomes the whole tree and the distance jumps from 1 to 2+ε-δ. With δ = 0.01 and ε = 0.02 the difference is 1.01, against a bound of 2(ψ+3)δ = 0.12. With ε = 2δ → 0, the difference stays ≈ 1 while the bound goes to 0."

  1. The attached code does not contain a full reproduction of the results of the paper as I expect modern papers in ML to include.

[1] Cao, Jianguo, Huijun Fan, and François Ledrappier. "Martin points on open manifolds of non-positive curvature." Transactions of the American Mathematical Society 359, no. 12 (2007): 5697-5724.

Questions for authors

If the authors insist that the proof of Theorem 4.5 is correct or fixable, they are welcome to explain why Claude's counterexample is incorrect (or irrelevant to the setting) and give a detailed formal proof of the inequality in lines 734,735. It may be the case that another assumption needs to be added to the theorem statement to correct it.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.