acceptodds
Under review as a conference paper at ICLR 2027

Geometry-Aware Robust Denoising via Hierarchical Manifold Traversal

Abstract

Existing manifold traversal algorithms denoise by navigating a graph via gradient-guided steps and zero-order shortcuts. Because they operate at a single resolution, single-layer traversal is susceptible to local minima traps and requires fixed initialization to succeed, making it impractical. We introduce *Hierarchical Manifold Traversal Networks (HMTNs)*, which approximate a -dimensional manifold with a stack of traversal graphs at geometrically increasing resolutions. A cross-layer map provides a strong initialization for each finer layer from the converged coarse layer. Importantly, in HMTN the hierarchy depth grows only logarithmically in the number of training samples and depends on the intrinsic dimension rather than the ambient dimension . Our empirical results on time-series gravitational-wave manifolds show that, in the random-initialization regime, HMTN achieves a improvement in MSE relative to single-layer traversal at only the multiplication cost. On patch denoising, gains range from on MNIST, which has the lowest scale separation, to – on CIFAR-10 and CelebA, whose scale separation is substantially larger. HMTN also offers a favorable accuracy–compute trade-off against classical search-based and learning-based alternatives: it requires a median of fewer multiplications than exhaustive nearest-neighbor search, and nonlinear autoencoders need more multiplications to match its accuracy. Training HMTN is a one-time CPU cost of 9-32 minutes on our gravitational-wave benchmarks.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
manifold learning, hierarchical graph traversal, denoising, robust initialization

Reviews

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

This paper proposes Hierarchical Manifold Traversal Networks (HMTNs), a coarse-to-fine framework for manifold denoising that extends single-layer manifold traversal by constructing multiple graph approximations at different resolutions. The proposed approach introduces cross-layer mappings to transfer traversal results from coarse to fine layers, aiming to improve robustness to initialization and mitigate the local minima encountered by conventional single-layer traversal.

The paper also develops a geometry-motivated strategy for determining the number of hierarchical layers based on the intrinsic dimension and geometric properties of the underlying manifold. Experiments on gravitational-wave signals and image patches from MNIST, CIFAR-10, and CelebA demonstrate improvements in denoising accuracy, particularly under random initialization. The authors additionally compare their approach with several search-based and learning-based methods.

The problem is well motivated, and the empirical results are potentially interesting. However, I have several concerns regarding the correctness of the theoretical analysis, the fairness of the experimental comparisons, and the consistency and reproducibility of the reported numerical results.

Critical strengths
  1. The paper addresses a genuine limitation of single-layer manifold traversal. The coarse-to-fine construction is well motivated by the initialization sensitivity and local-minimum behavior of the underlying traversal method. In the gravitational-wave experiments, the hierarchy substantially improves random-start performance.

  2. The random-restart experiment is a useful control. Multiple random restarts of the single-layer method eventually approach or exceed the hierarchical method, but require substantially greater computation. This supports the claim that the hierarchy can provide a useful structured initialization mechanism rather than merely benefiting from one additional random start.

Critical weaknesses
  1. Issues in the theoretical analysis and its connection to the implementation. The proof of Proposition 1 appears flawed. Algorithm 1 only guarantees coverage of the finite training set X, not the entire manifold M, as assumed in Eq. (17). Moreover, the packing argument in Eq. (19) provides an upper bound on the number of separated landmarks, which does not imply the covering-number lower bound claimed in Eq. (20). These gaps undermine the theoretical justification for the hierarchy depth. Additionally, the practical radii are selected using empirical distance statistics, without showing that they satisfy the theoretical assumptions, particularly the manifold-reach constraint on the coarsest radius.

  2. Limited novelty and insufficiently controlled experimental comparisons. The hierarchical construction closely resembles existing multiscale methods, such as Navigating Nets (2004), Cover Trees (2006), and GMRA (2012/2019), which already employ multiscale coverings, cross-scale navigation, or local affine manifold approximations. The paper should better clarify its technical novelty beyond combining these ideas with existing single-layer traversal.

Furthermore, the baseline comparisons are not fully fair: HMT uses tangent-plane correction, while kNN and HNSW do not receive the same denoising refinement. Thus, the reported accuracy gains cannot be attributed solely to hierarchical search. Comparisons with kNN and HNSW using identical tangent-plane corrections are needed. Finally, some CIFAR-10 settings require over 100× more multiplications for approximately 8× MSE improvement, raising questions about the claimed computational efficiency.

Questions for authors

Q1. Can the authors provide a rigorous justification for Equation (17) in Appendix B.2? How does coverage of the finite training set imply coverage of the entire manifold? Additionally, could the authors clarify the transition from Equation (19) to Equation (20) and provide a corrected proof if necessary?

Q2. How does HMTN compare against HNSW and exhaustive nearest-landmark search when all methods apply exactly the same tangent-plane denoising correction? How much of the reported improvement is attributable to better landmark selection rather than the local denoising estimator?

Q3. Why do HMT, HMT-epsilon, and eHMT-epsilon-k report identical MSE improvement ranges and medians under both initialization regimes in Table 2? Do these methods actually produce identical predictions for most test samples, or is the agreement caused by rounding? Please clarify the variant naming and provide unrounded results for individual configurations.

Q4. Why do several values of R_L/R_1 in Table 8 increase as rho increases, despite the stated radius-selection formula? Were different training subsets or preprocessing results used for different configurations? How do the authors ensure that the hyperparameter comparisons remain controlled?

Q5. Could the authors clarify whether the train/test splits in the image experiments are disjoint at the original-image level rather than only at the patch level? Furthermore, what operating regimes should practitioners target to achieve favorable accuracy–computation trade-offs, given the substantial overhead observed in some image experiments?

4 comments
AuthorsOpenReview ↗

PART 1/4 – Summary and theory (W1, Q1)

PART 1/4 -- Summary and theory (W1, Q1)

We sincerely thank the reviewer for the careful and detailed review. The reviewer's concerns about the proof of Proposition 1 are justified, and we address them below. In summary, we (i) correct the theory and state precisely what its assumptions are, (ii) will add baselines that use an identical denoiser, (iii) clarify novelty relative to the cited multiscale literature, and (iv) address the Table 2, Table 8 and train/test split questions. All additional experiments will be included in the final version of the paper.

Coverage of XX vs. M\mathcal{M} (Eq. 17). We agree with the reviewer. Algorithm 1 guarantees only that every training point lies within RℓR_\ell of a landmark, so QℓQ_\ell is an RℓR_\ell-net of the finite set XX, not of M\mathcal{M}, and N(M,R1)≤∣Q∣\mathcal{N}(\mathcal{M}, R_1) \le |Q| does not follow from the algorithm. The base method makes the same assumption: Theorem 7.1 of Wang et al. (2025) assumes the landmarks form a δ\delta-net of M\mathcal{M} and leaves a guarantee for the online construction as future work. We will state this explicitly as an assumption, applied per layer:

(A0) Each QℓQ_\ell is a cRℓcR_\ell-net of M\mathcal{M} for a constant c≥1c \ge 1 (c=1c = 1 is the "ideal graph" assumption of Wang et al., 2025).

We do not claim (A0) for Algorithm 1 in general. For i.i.d. samples from the uniform measure on M\mathcal{M} it holds with c=3/2c = 3/2 and probability at least 1−δ1-\delta, once N>β1(log⁡β2+log⁡(1/δ))N > \beta_1\left(\log\beta_2 + \log(1/\delta)\right) with ε=min⁡(Rℓ,0.49τM)\varepsilon = \min(R_\ell, 0.49 \tau_{\mathcal{M}}) (Niyogi–Smale–Weinberger, 2008, Prop. 3.2): the sample is then ε/2\varepsilon/2-dense in M\mathcal{M}, so an RℓR_\ell-net of XX is a 32Rℓ\tfrac{3}{2}R_\ell-net of M\mathcal{M}. At the finest layer this condition reads N≳vol(M) R1−dN \gtrsim \mathrm{vol}(\mathcal{M})\,R_1^{-d} up to dd-dependent constants and logarithmic factors, consistent with the resolution scale in Prop. 1 below. Our data are not uniform on M\mathcal{M}, so for the experiments (A0) remains an assumption.

Eq. (19) → (20). We agree with the reviewer: a packing argument bounds ∣Q∣|Q| from above, so the rearrangement to Eq. (20) went in the wrong direction. We replace Eqs. (18)–(20) with two bounds that are rigorous under (A0), with extrinsic curvature bounded by κ\kappa and cRℓ≤τMcR_\ell \le \tau_{\mathcal{M}} (so τM≤1/κ\tau_{\mathcal{M}} \le 1/\kappa, as in Wang et al.):

  • Upper bound. Euclidean separation implies intrinsic separation, so the log-map/Toponogov argument of Wang et al. (Lemma A.2) gives ∣Qℓ∣≤(1+42diam(M)eκdiam(M)Rℓ)d.|Q_\ell| \le \left(1 + \frac{4\sqrt{2} \mathrm{diam}(\mathcal{M}) e^{\kappa \mathrm{diam}(\mathcal{M})}}{R_\ell}\right)^{d}. This also removes the "≳\gtrsim" in Eq. (18).
  • Lower bound. Bishop–Gromov (Ric≥−(d−1)κ2\mathrm{Ric} \ge -(d-1)\kappa^2) gives volBM(q,r)≤ωd rd(sinh⁡(κr)κr)d−1.\mathrm{vol} B_{\mathcal{M}}(q, r) \le \omega_d\ r^d \left(\frac{\sinh(\kappa r)}{\kappa r}\right)^{d-1}. A Euclidean RR-ball intersected with M\mathcal{M} lies in BM(q,2R)B_{\mathcal{M}}(q, 2R) for R≤τMR \le \tau_{\mathcal{M}} (Wang et al., Lemma B.5). Under (A0), ∣Qℓ∣≥vol(M)Cd(cRℓ)dCd=ωd 2d(sinh⁡22)d−1.|Q_\ell| \ge \frac{\mathrm{vol}(\mathcal{M})}{C_d (cR_\ell)^d} \qquad C_d = \omega_d\ 2^d \left(\tfrac{\sinh 2}{2}\right)^{d-1}.

Proposition 1 (corrected). Under (A0) and cR1≤τMcR_1 \le \tau_{\mathcal{M}}, the lower bound with ∣Q1∣≤N|Q_1| \le N gives R1≥(vol(M)/(CdcdN))1/dR_1 \ge \left(\mathrm{vol}(\mathcal{M}) / (C_d c^d N)\right)^{1/d}, which is the conclusion of the original Prop. 1, now with an explicit constant and a valid proof. Without (A0) the conclusion fails: as R1→0R_1 \to 0 every training point becomes its own landmark, but Q=XQ = X is then not an R1R_1-net of M\mathcal{M}. Substituting into the real-valued depth of Eq. (9), L=1+dln⁡(RL/R1)L = 1 + d \ln(R_L/R_1), gives L≤1+ln⁡(CdcdNRLdvol(M)),L \leq 1 + \ln \left(\frac{C_d c^d N R_L^d}{\mathrm{vol}(\mathcal{M})}\right), which has the same form as Eq. (3), up to the constant CdcdC_d c^d, and is independent of DD. Since the number of layers must be an integer, Eq. (4) rounds this up to ⌈dln⁡(RL/R1)⌉+1\lceil d \ln(R_L/R_1) \rceil + 1.

AuthorsOpenReview ↗

PART 2/4 — Practical radii vs. theory (W1, continued)

PART 2/4 — Practical radii vs. theory (W1, continued)

Practical radii vs. theory. The reviewer is also right that the experimental radii are set from empirical statistics (R1R_1: pp-th percentile of pairwise distances; RL=(1−ρ)r^min⁡R_L = (1-\rho) \hat r_{\min} from the minimum eccentricity), and that we did not verify RL≤τMR_L \le \tau_{\mathcal{M}}. However, in practice the reach of a manifold, including the GW manifold, is unknown, and RLR_L on unit-norm signals is of the order of the diameter. The role of RLR_L is to guide the traversal coarsely, and it serves this purpose in practice. We regard the theory and the practical radii as complementary: the former states when the guarantees hold rigorously, and the latter is a design choice that we validate empirically. We will (i) present Eq. (4) with measured radii as a design rule rather than as an implementation of Eq. (3), changing "determined by" to "guided by" in the abstract and introduction (as also committed in our response to Reviewer 88H3), and (ii) clarify that the coarsest layer is not claimed to be a faithful local linear model at a fine scale. Empirically, the coarse layers act as global localizers: at d=2d = 2, performance degrades when RLR_L is decreased (larger ρ\rho, Figs. 6–7), which does not indicate that a reach constraint on RLR_L limits performance. Finally, all empirical results are independent of Proposition 1: LL is computed from the measured RL/R1R_L/R_1, and Fig. 3 reports accuracy as a function of depth directly.

AuthorsOpenReview ↗

PART 3/4 — Novelty, matched-denoiser baselines, compute (W2, Q2)

PART 3/4 — Novelty, matched-denoiser baselines, compute (W2, Q2)

Novelty. We thank the reviewer for the pointers to Navigating Nets (Krauthgamer & Lee, 2004), Cover Trees (Beygelzimer et al., 2006), and GMRA (Allard et al., 2012; Liao & Maggioni, 2019), which we will cite and discuss. We agree that multiscale coverings and coarse-to-fine navigation are classical, and we do not present the idea of hierarchical structure per se as novel (we already cite HNSW and small-world navigation in this role). Our contribution is what this device does for manifold-traversal denoising:

  1. Layers are traversal graphs with first-order tangent edges and zero-order tunnels (Wang et al., 2025). Within a layer, search takes Riemannian gradient steps in dd-dimensional tangent coordinates (O(Dd)O(Dd) per step), rather than evaluating DD-dimensional distances to all candidate children as in net/cover-tree descent. App. G analyzes the cost (diam2(M)\mathrm{diam}^2(\mathcal{M}) is replaced by Rl2R_l^2 at each layer).
  2. Cross-layer pointers act as warm starts for a local optimizer, which removes the initialization failure of single-layer traversal.
  3. Single-pass online construction with incremental local SVD, and a data-computable scale ratio RL/R1R_L/R_1 that predicts the gain over single-layer traversal (Sec. 5).

We agree that a direct comparison would strengthen the paper: in the final version we will add a cover-tree baseline with the same tangent-plane correction (below), and a related-work discussion of GMRA. GMRA builds a multiscale partition with local PCA bases offline from the full dataset, whereas HMTN uses learned landmarks and tangent bases with traversal at query time.

Fairness of kNN/HNSW comparisons (Q2). We thank the reviewer for this point. Indeed, kNN and HNSW (App. D.1–D.2) return the landmark without the tangent-plane (TP) correction used by SMT/HMT. This was intended to isolate the final denoising-step contribution. We will revise as follows:

  • The core claims (robustness to initialization, layer ablation, random-restart control) compare SMT and HMT are unaffected.
  • Matched denoiser. In the final version we will apply the identical TP step x^=qj+UjUj⊤(y−qj)\hat{x} = q_j + U_j U_j^\top (y - q_j) to the landmark returned by exact nearest-landmark search, HNSW (ef∈{1,…,128}\mathrm{ef} \in \{1, \dots, 128\}) and a cover tree, on all configurations, and will report MSE–multiplication curves. We will also report landmark-selection accuracy: the fraction of queries for which each method returns the exact nearest landmark, and the MSE excess relative to exact search. This separates search quality from the local estimator, as requested.
  • Full-data pipeline. In the final version we will also add HNSW over all NN training points followed by a local PCA/TP fit on the kk retrieved neighbours (locally linear denoising, Gong et al., 2010), with the PCA cost counted in multiplications. This is the standard practitioner pipeline and tests whether learned landmarks with precomputed tangent bases outperform raw-data retrieval.
  • We will present the efficiency claim in terms of the cost at matched denoising performance for ease of readability. In HMTN the tangent bases are precomputed, so TP costs about O(Dd)O(Dd) per query, whereas applying TP to raw data requires a query-time local PCA.

Compute on CIFAR-10. Agreed. At p=1%p = 1\% under random start, Table 7 reports 7.9–8.9× MSE improvement at 101–121× overhead relative to SMT. The reported overheads are ratios relative to SMT, which is a cheap baseline; in the final version we will report absolute multiplication counts and compare against exhaustive landmark search in absolute terms to make it easier for practitioners to understand and relate to the computational costs. On image patches, the benefit of HMTN is in accuracy under random initialization (up to about 9× lower MSE than SMT), at the compute overheads reported above. Its efficiency advantage over exhaustive and approximate search is demonstrated on the high-dimensional GW data (D=2048D = 2048), and we will state this scope clearly in the final abstract and body of the paper.

AuthorsOpenReview ↗

PART 4/4 – Q3, Q4, Q5

PART 4/4 — Q3, Q4, Q5

Q3 (Table 2). We thank the reviewer for their careful check of our work.

(a) Naming: the row "eHMT-ϵ\epsilon-kk" in Table 2 should read "HMT-ϵ\epsilon-kk", as in Tables 3–5, Fig. 2 and App. D; we will correct it in the final version.

(b) Identical values: HMT, HMT-ε and HMT-ε-k differ only in how they traverse coarse layers (full convergence; early exit at ϵl=Rl2\epsilon_l = R_l^2; exhaustive scan of layers with at most kk landmarks), whereas the denoised output depends only on the finest-layer landmark. When two variants reach the same finest-layer landmark, their MSE is identical to floating-point precision while their cost differs (7.2×, 3.9×, 4.0× under random start). We confirmed from the raw logs that the final landmark agrees across these variants, and in the final version we will report unrounded MSE and the agreement rate in the appendix.

Q4 (Table 8). We thank the reviewer for pointing this out. Within each run, RL/R1R_L/R_1 follows the stated formula exactly. However, the CIFAR-10 sweep was run without a fixed seed. Each configuration therefore drew its own 50k training subset and test split, and recomputed R1R_1 and r^min⁡\hat r_{\min}. Preprocessing was identical across all runs. The implied r^min⁡=RL/(1−ρ)\hat r_{\min} = R_L/(1-\rho) is stable across runs (0.95–1.10, mean 1.00). The non-monotonicity comes mainly from sampling variability in R1R_1 (±14%\pm 14\% at p=1%p = 1\%), which exceeds the 5–11% change in (1−ρ)(1-\rho) between adjacent ρ\rho values. Fixed- and random-start runs were also trained independently, which is why their ratios differ. We agree that a controlled comparison would be more fit for this purpose. In the final version we will fix the seed, and hence the train/test split and both radius estimates. We will then rerun the sweep so that ρ\rho is the only variable, and report R1R_1 and r^min⁡\hat r_{\min}.

Q5(a) Train/test splits. We thank the reviewer for this astute observation. Training and test patches were extracted from the training and test images of the original datasets, respectively, so the source images of the two sets are disjoint. We will make this explicit in the final version of the paper.

Q5(b) Operating regimes. From the results in the paper, HMTN is favorable when (i) initialization is uncontrolled and single-layer traversal fails; (ii) the ambient dimension is high, so distance-based search is expensive; (iii) ρ\rho is small (ρ≤0.05\rho \le 0.05 at d=2d = 2) and LL follows Eq. (4); and (iv) RL/R1R_L/R_1, computable before building the graph, is large. It is not favorable when a good initialization is available and the scale separation is small (e.g., MNIST), or at d=2d = 2 with ρ≥0.1\rho \ge 0.1. In the image-patch settings, gain and overhead both grow with RL/R1R_L/R_1. In the final version we will add a practical-guidance table and a limitations paragraph with these regimes.

We hope these revisions address the reviewer's concerns. Thank you again for the constructive and rigorous review, we really appreciate your time and feedback!

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

This paper studies manifold traversal problem. The authors claimed that previous methods chose single-layer traversal, which easily stop at local-minima traps. Therefore, they proposed hierarchical manifold traversal networks via layer-by-layer exploration.

Critical strengths

None.

Critical weaknesses
  1. Paper organization. The paper writing style is hard to follow. For example, alogrithm is used to show the process with rigorous and concise math formulas, but algorithms in this paper include too many textual descriptions. Also, the method section has the same issue, too many words with only one formula Eq. (2), and this equation is very similar to Eq. (1). In section 5, experimental results, there are no tables and figures in this section. I know that the authors showed them in other sections, but it could be better to pair results with illustrations together.

  2. Motivations. The main motivation is the former methods using single-layer traversal are prone to trap in local minima. However, I cannot get why the proposed hierarchical traversal can solve it. It's natural to say hierarchy can improve efficiency. Since we cannot know what the real shape of the manifold beforehand, it is very likely that the true global minima is around the landmarks that are not the best during the selection in the top coarse layer. HTMN also utilizes zero-order edges, same to the single-layer methods. The paper does not clearly establish that hierarchy itself is the mechanism responsible for escaping local minima.

Questions for authors

No.

1 comment

We thank the reviewer for the careful reading and for pointing out where the writing style and the motivation can be made clearer. Below, we address both concerns that the reviewer has raised.

1. Paper organization

Algorithms and method section. We agree that Algorithms 1-2 mix procedure and prose. We included textual descriptions in the algorithm boxes in an attempt to make it easier for the reader to absorb the meaning of each line, but evidently it has had the opposite effect. In the revision, we will rewrite both algorithms in compact mathematical notation. The line-by-line explanations will move to the appendix, where Algorithms 4-5 already hold them. We will decrease the amount of text in the methods section, and move tables and figures from the appendix into in section 5, as suggested. We agree that the paper would significantly benefit from these changes.

We would like to address the point about Eq. (1) vs. Eq. (2). These are different objects that happen to share a squared-distance form. Eq. (1) is the denoising objective, the distance from a noisy query yy to a point on the manifold. Eq. (2) is the cross-layer pointer map, the distance between a landmark at layer ll and landmarks at layer l−1l-1 within radius R⊗R_\otimes. We will state this explicitly and use distinct notation for the two.

Section 5. We agree that results should sit next to their discussion. Fig. 2, Fig. 3 and Table 2 (currently in Appendix) will be moved into Section 5, together with a compact summary table for the image benchmarks.

2. Motivation

Why does hierarchy help escape local minima?

We thank the reviewer for this point. We do not claim that the coarse layer returns the global minimizer, or even a point that has to be close to the optimum. The claim is that the coarser layers help us zoom in onto the correct region of the global minimizer, and finer layers help with a more detailed search.

Zero-order edges are most useful when they provide good coverage of the graph. Edges are created only when training traversal gets stuck (Alg. 1), so they certify coverage only if enough training points visit each landmark. Single-layer traversal needs this at the finest scale across the entire manifold, where there are many landmarks and few samples per landmark. The number of landmarks drops by a factor of ee per layer, so coarse layers have far more samples per landmark and a small, densely tunneled graph. Global search there is cheap. Finer layers then only need local refinement within roughly the radius RlR_l. The traversal path in Fig. 2(b-c) shows that SMT stops quickly at a minimum far from the query (φ=2.15\varphi = 2.15), while HMT reaches to a landmark closest to the query (φ=0.21\varphi = 0.21).

Evidence that the hierarchy is the responsible mechanism. Four existing experiments point out that the hierarchy is the mechanism responsible for escaping local minima, resulting in better performance.

  1. Layer ablation (Fig. 3). The graph construction process and edge types are identical across sub-networks, but MSE decreases as the number of layers are increased.

  2. HMT-ϵ\epsilon-3L. The paper proposes a recipe for choosing the hierarchy depth LL. When we don't follow this recipe and artificially remove the middle layers, the gains drops from 134×134\times to 5.3×5.3\times (Table 2). This shows the importance of the graph depth, and that each layer of the hierarchy plays a role.

  3. HMT-ϵ\epsilon-kk. This variant scans exhaustively at coarse layers. It matches the accuracy of HMT (134×134\times, Table 2), consistent with "global coarse search, then local refinement". This shows that the coarse layers provide the function of narrowing down onto the right region, as opposed to denoising or finding the correct point.

  4. Random restarts (App. D.4). SMT needs 16-32 restarts to match HMT, at 4.74.7-5.4×5.4\times its compute, meaning that SMT gets stuck often and needs numerous restarts to eventually match HMTN's performance, while HMTN's hierarchical mechanism helps us find the global optimum quickly.

We agree with the reviewer that a poor selection of landmarks in a coarse layer can mislead the descent. However, another strength of the hierarchical approach is that even if one of the layers provides a somewhat misleading direction, the rest of the hierarchy will be able to fix this due to gradient-guided steps and convergence in each layer.

We thank the reviewer once again, and hope that these explanations have addressed you concerns. We are extremely grateful for your time and feedback, will make sure that the final version of this work addresses all your points.

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

This paper proposes Hierarchical Manifold Traversal Networks (HMTNs), which extend single-resolution manifold traversal to a coarse-to-fine hierarchy for denoising. Each layer approximates the data manifold at a different resolution, with cross-layer mappings providing warm starts for progressively finer traversal. The method is evaluated on simulated gravitational-wave signals and image patches, with comparisons to single-layer traversal, nearest-neighbor search, HNSW, and autoencoders.

Critical strengths
  1. The coarse-to-fine traversal idea is intuitive and well motivated. It directly addresses the initialization sensitivity of single-layer manifold traversal by using coarse layers to localize the query before fine-scale refinement.

  2. The experiments show a clear accuracy–compute benefit in the gravitational-wave setting. The paper also includes comparisons with HNSW, nearest-neighbor search, autoencoders, multiple SMT restarts, and layer-depth ablations.

Critical weaknesses
  1. The hierarchy is less fully determined by the theory than the presentation suggests. In practice, the depth depends on the intrinsic dimension �0��0� and radii �1��1�, while �2��2� and �3��3� are set through percentile and margin choices and �4��4� is manually specified for the image-patch experiments. This makes the practical hierarchy partly heuristic rather than purely geometry-determined.

  2. The image evaluation is limited and its split protocol is unclear. The experiments operate on small patches rather than full images, and the paper describes randomly holding out patches after extraction; it is not clear whether train and test patches are separated at the source-image level. With overlapping patches, this distinction could materially affect the reported denoising performance.

  3. The paper is mostly readable, but the presentation could use a careful formatting pass; in particular, pages contain large amount of unused s space at the bottom of the page.

Questions for authors

1.How is the intrinsic dimension �0��0� selected in practice for datasets where it is not known a priori? More generally, how sensitive is HMTN to misspecification of �1��1�, �2��2�, and �3��3�?

  1. For MNIST, CIFAR-10, and CelebA, are the training and test patches extracted from disjoint source images, or are patches randomly split after extraction? This seems particularly important for overlapping CIFAR-10 patches.

  2. How should the image results be interpreted with respect to full-image denoising, given that the current evaluation is performed only on small grayscale patches?

2 comments

We greatly appreciate the reviewer's assessment and are immensely grateful for their time and helpful feedback. Below we address the reviewer's questions and concerns.

Weakness 1. Theory vs. heuristic-guided hierarhcy. We thank the reviewer for this helpful comment. It is indeed correct that the hierarchy depth depends on the intrinsic dimension dd and radii R1R_1 and RLR_L in practice. Given the desin choice of λ\lambda, the hierarchy depth depends on geometric quantities such as manifold diameter, reach, volume, and intrinsic dimension. We clarify which parts are determined by theory and which are estimated.

The practical depth is fully determined by R1,RLR_1, R_L, and dd. The theory ties these to geometric quantities: $R_L \le \min ( \text{diam}(\mathcal{M}), \tau ) $ (Section B.3) and R1≳(vol(M)/N)1/dR_1 \gtrsim \left( \text{vol}(\mathcal{M})/N\right)^{1/d} (Proposition 1), which is independent of the ambient dimension DD.

For experiments, we replace these with standard computable counterparts [West, 2001]. R1R_1 is the 1st percentile of pairwise distances, a robust proxy for the typical inter-sample distance. RL=(1−ρ)rmin⁡R_L = (1-\rho) r_{\min}, where rmin⁡r_{\min}, the minimum eccentricity, satisfying rmin⁡≤diam(M)r_{\min} \le \text{diam}(\mathcal{M}). To conclude, we agree that practical hierarchy is therefore geometry-informed rather than purely geometry-determined. We will change “determined by” to “guided by” in the abstract and introduction to state this explicitly.

Question 1. Choice of intrinsic dimension dd in practice. This is a great question, and the community has been trying to find answers to it for a long time. Pope et al., 2021, show that one dataset can have different potential values of dd.

As you can see, there is no one definite value for intrinsic dimension dd in practice. We chose the patch size to be 4×44 \times 4 across datasets as it is common practice in the literature (Wu, 2025). The choice of dd is better supported by prior topological analyses of small natural-image patches. The high-density core of high-contrast patches concentrates near a 2-dimensional manifold (Carlsson, 2008, for 3×33 \times 3 patches; Xia, 2016, for 3×33 \times 3 through 7×77 \times 7 patches, including 4×44 \times 4). Therefore, we chose d=2d = 2 as an effective practical dimension. We will make this clarification in the final version of the paper. Thank you for pointing this out!

We also showed varying values of dd on MNIST patches. Table 6(c) already varies dd on the same MNIST patches (d=5,7,11,12,13d = 5, 7, 11, 12, 13, with RL/R1≈1.9R_L/R_1 \approx 1.9 throughout). LL grows from 5 to 10 as expected from Eq. (4). The random-start MSE gain declines gradually (1.62→1.40→1.34→1.30→1.281.62 \to 1.40 \to 1.34 \to 1.30 \to 1.28) and stays above 1, while overhead grows from 1.55×1.55\times to 2.63×2.63\times. In this setting, over-specifying dd decreases accuracy and increases compute cost, but does not cause failure.

In the final version of the paper, we will provide:

  1. Values of dd computed by dimension estimation methods on the patch datasets, including MLE and TwoNN.
  2. A sweep over a dense grid of values for dd, ranging from 2 to 20, for all image patch datasets, to demonstrate what happens when dd is misspecified.

Sensitivity to misspecification. Different intrinsic dimension estimators provide different answers for the coveted value of dd. Therefore, it is difficult to clarify what misspecificaion means in this setting, as there is no clear correct or incorrect answer. However, our experiments on MNIST provide a hint. Table 6 (c) shows that varying dd from 5 to 13 changes LL from 5 to 10. Increasing the value of dd decreases accuracy and increases compute cost, but does not cause failure.

Because gravitational wave data provides physics-backed ground-truth values for dd, we will run a misspecification sweep with $\hat{d} \in { d/2, d, 2d, 5d, 10d \big $ and report MSE and multiplications.

Sensitivity to R1R_1 and RLR_L. i) If the coarsest radius is too small (e.g., for ρ≥0.1\rho \geq 0.1), performance degrades as the hierarchy depth suffers (Figures 4–7). If the finest radius R1R_1 is too large, it shrinks RL/R1R_L/R_1 and degrades the method gradually toward single-layer traversal. The depth ablation shows the same behavior (Figures 3, 8-10)

Question 2. We thank the reviewer for this astute observation. The source images of test and train set were kept separate. We will make this distinction explicit in the final version of the paper.

Question 3. We propose dividing a full-sized image into patches, denoising these patches via HMTN, stitching them back together, and using classical algorithms to avoid edge-artifacts, if needed. We will add a full-sized image experiment in the final version.

Formatting. We will remove the unused space at the bottom of the pages in the revision by repositioning floats and tables.

We hope these revisions address the reviewer's concerns. Thank you again for the helpful review!

Thanks for the clarification. The response resolves my concern. So I keep my initial rating.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.