- 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
-
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.
-
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
-
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.
-
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
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 (: -th percentile of pairwise distances; from the minimum eccentricity), and that we did not verify . However, in practice the reach of a manifold, including the GW manifold, is unknown, and on unit-norm signals is of the order of the diameter. The role of 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 , performance degrades when is decreased (larger , Figs. 6–7), which does not indicate that a reach constraint on limits performance. Finally, all empirical results are independent of Proposition 1: is computed from the measured , and Fig. 3 reports accuracy as a function of depth directly.
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:
- 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 -dimensional tangent coordinates ( per step), rather than evaluating -dimensional distances to all candidate children as in net/cover-tree descent. App. G analyzes the cost ( is replaced by at each layer).
- Cross-layer pointers act as warm starts for a local optimizer, which removes the initialization failure of single-layer traversal.
- Single-pass online construction with incremental local SVD, and a data-computable scale ratio 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 to the landmark returned by exact nearest-landmark search, HNSW () 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 training points followed by a local PCA/TP fit on the 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 per query, whereas applying TP to raw data requires a query-time local PCA.
Compute on CIFAR-10. Agreed. At 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 (), and we will state this scope clearly in the final abstract and body of the paper.
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--" in Table 2 should read "HMT--", 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 ; exhaustive scan of layers with at most 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, 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 and . Preprocessing was identical across all runs. The implied is stable across runs (0.95–1.10, mean 1.00). The non-monotonicity comes mainly from sampling variability in ( at ), which exceeds the 5–11% change in between adjacent 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 is the only variable, and report and .
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) is small ( at ) and follows Eq. (4); and (iv) , 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 with . In the image-patch settings, gain and overhead both grow with . 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!
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 X vs. M (Eq. 17). We agree with the reviewer. Algorithm 1 guarantees only that every training point lies within Rℓ of a landmark, so Qℓ is an Rℓ-net of the finite set X, not of M, and N(M,R1)≤∣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 δ-net of M and leaves a guarantee for the online construction as future work. We will state this explicitly as an assumption, applied per layer:
We do not claim (A0) for Algorithm 1 in general. For i.i.d. samples from the uniform measure on M it holds with c=3/2 and probability at least 1−δ, once N>β1(logβ2+log(1/δ)) with ε=min(Rℓ,0.49τM) (Niyogi–Smale–Weinberger, 2008, Prop. 3.2): the sample is then ε/2-dense in M, so an Rℓ-net of X is a 23Rℓ-net of M. At the finest layer this condition reads N≳vol(M)R1−d up to d-dependent constants and logarithmic factors, consistent with the resolution scale in Prop. 1 below. Our data are not uniform on M, so for the experiments (A0) remains an assumption.
Eq. (19) → (20). We agree with the reviewer: a packing argument bounds ∣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 κ and cRℓ≤τM (so τM≤1/κ, as in Wang et al.):
Proposition 1 (corrected). Under (A0) and cR1≤τM, the lower bound with ∣Q1∣≤N gives R1≥(vol(M)/(CdcdN))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→0 every training point becomes its own landmark, but Q=X is then not an R1-net of M. Substituting into the real-valued depth of Eq. (9), L=1+dln(RL/R1), gives L≤1+ln(vol(M)CdcdNRLd), which has the same form as Eq. (3), up to the constant Cdcd, and is independent of D. Since the number of layers must be an integer, Eq. (4) rounds this up to ⌈dln(RL/R1)⌉+1.