acceptodds
Under review as a conference paper at ICLR 2027

Fast Local Mean Curvature Estimation for High-Dimensional Data Manifolds

Abstract

Local mean curvature is a powerful geometric descriptor of data manifolds. Nonetheless, its computational cost has largely prevented its adoption in modern machine learning methods. In the present work, it is introduced a scalable curvature estimation framework for high-dimensional data (MeCuCo). The new method combines an exact algebraic reformulation of a classical curvature estimator with a low-rank approximation that exploits the structure of local neighborhoods. This innovative combination yields a reduced computational complexity – from quartic to nearly linear in the ambient dimension for typical settings, while preserving the quality of the estimated curvature values. Theoretical analysis of the proposed formulation and approximation are provided, resulting in outstanding speed-up improvements between 50 and 300 times on real-world datasets. Importantly, through rendering curvature estimation computationally tractable at scale, MeCuCo facilitates the integration of curvature-aware representations and geometric inductive biases into manifold learning, representation learning, and related machine learning paradigms.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
Mean curvature estimation, Manifold learning, High-dimensional geometry, Low-rank approximation, Geometric representation learning

Reviews

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

This paper proposes MeCuCo, a scalable framework for local mean-curvature estimation on high-dimensional data manifolds, aiming to address the prohibitive computational cost of existing curvature estimators in high-dimensional settings. The method first derives an exact algebraic reformulation that reduces the dominant complexity of the original estimator from O(D4)\mathcal{O}(D^4) to O(D3)\mathcal{O}(D^3) without introducing approximation error. It then further exploits the inherent low-rank structure of local covariance matrices when k≪Dk\ll D, replacing full eigendecomposition with truncated SVD and analytically approximating the covariance null-space contribution, thereby reducing the practical complexity to O(k2D+kDp2)\mathcal{O}(k^2D+kDp^2). Experiments on more than 40 publicly available OpenML datasets show that MeCuCo substantially improves computational efficiency while largely preserving the numerical values and ranking structure of the original curvature estimates, and remains feasible in very high-dimensional regimes where the original method becomes impractical. Overall, the main contribution of the work is to turn high-dimensional local curvature estimation from a computationally expensive procedure into a more scalable geometric primitive, potentially facilitating its use in geometry-aware machine learning applications.

Critical strengths

The paper presents a mathematically motivated and non-trivial computational reformulation.Rather than relying on implementation-level acceleration, the proposed method first derives an exact algebraic reformulation of the existing local mean-curvature estimator, reducing the dominant computational complexity from O(D4)\mathcal{O}(D^4) to O(D3)\mathcal{O}(D^3) without introducing approximation error. It further exploits the low-rank structure of local covariance matrices and introduces an analytical treatment of the null-space contribution, which provides a principled way to improve scalability in high-dimensional settings.

The proposed method achieves substantial computational gains while preserving the curvature estimates with high fidelity. The experimental results show that MeCuCo can significantly reduce the computational cost of curvature estimation while maintaining very strong agreement with the original estimator. In particular, the reported rank correlations and normalized errors suggest that the relative geometric structure of the curvature scores is largely preserved. This provides encouraging empirical evidence that the proposed acceleration does not substantially compromise the information captured by the original formulation.

The experimental evaluation covers a relatively broad range of high-dimensional datasets and provides useful evidence of scalability. The paper evaluates the proposed method on more than 40 publicly available OpenML datasets with diverse sample sizes, feature dimensions, and geometric characteristics, and further considers datasets with ambient dimensionalities ranging up to tens of thousands. This relatively broad evaluation helps demonstrate the practical scalability of the method, particularly in regimes where the computational cost of the original estimator becomes prohibitive.

Critical weaknesses

The experimental comparison is mainly conducted against the original MCBP estimator, which is sufficient to demonstrate the computational benefits of MeCuCo over its direct predecessor. However, this comparison does not fully establish the position of MeCuCo within the broader literature on scalable curvature estimation and local geometric analysis.

The paper evaluates MeCuCo on a relatively large collection of datasets, which is a strength in terms of empirical coverage. However, most experiments focus on two aspects: computational runtime and agreement with the original curvature estimator. As a result, the evaluation provides limited insight into when and why the approximation may succeed or fail.

The complexity analysis mainly focuses on the per-point curvature estimation stage, where FAST mode reduces the cost to O(k2D+kDp2)\mathcal{O}(k^2D+kDp^2). However, the complete pipeline also requires nearest-neighbor search, local neighborhood construction, repeated SVD computations, and tensor contractions over all samples. In large-scale and high-dimensional datasets, these additional operations may become non-negligible and could affect the practical scalability of the overall framework.

The paper positions MeCuCo as a scalable geometric primitive that could benefit representation learning, clustering, anomaly detection, active learning, graph learning, and related geometry-aware ML tasks. However, the current experiments focus almost entirely on computational efficiency and agreement with the original curvature estimator, without demonstrating whether the estimated curvature actually improves any downstream learning task. Therefore, the broader claim regarding the practical utility of MeCuCo for machine learning remains insufficiently supported by the current experimental evidence.

Questions for authors

Could the authors clarify how MeCuCo compares with other efficient curvature estimators, local-PCA-based geometric descriptors, or Weingarten-map-based approaches in terms of both computational efficiency and estimation quality? Such a comparison would help assess whether MeCuCo offers advantages beyond accelerating its direct predecessor, MCBP.

Could the authors provide more insight into the conditions under which the FAST approximation remains reliable or begins to degrade? In particular, how sensitive is the method to neighborhood size, noise level, local anisotropy, effective rank, or high-curvature regions?

Could the authors clarify the end-to-end computational and memory costs when nearest-neighbor search, neighborhood construction, repeated SVD computations, and tensor operations are all included? This would help determine whether the claimed scalability still holds at the level of the complete pipeline.

Could the authors provide evidence that the curvature estimated by MeCuCo leads to measurable improvements in at least one representative downstream task? The answer to this question would materially affect my assessment of the broader machine-learning impact of the work.

1 comment

Thank you for your thorough review and for the time and effort you put into your comments and questions. We appreciate your acknowledgment of the mathematical motivation behind the exact reformulation, the fidelity of the curvature estimates, and the breadth of the empirical evaluation. We are working on the paper and will implement any pertinent improvements in the revision.

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

In this paper, the authors propose an algorithm for estimating the local mean curvature of a low-dimensional manifold embedded in a high-dimensional ambient space from sampled data. Existing curvature estimators incur high computational costs, limiting their applicability to a wide range of machine learning problems. The authors therefore focus on developing a computationally efficient estimator. The proposed algorithm combines an exact algebraic reformulation of an existing curvature estimator, reducing its computational complexity, with an efficient approximation based on the low-rank structure of local covariance matrices, which further reduces the computational cost at the expense of introducing an approximation. Specifically, the authors use truncated SVD and replace the contribution of the null-space eigenvectors with its analytically computed expectation. Experiments are conducted on a diverse set of benchmark datasets to evaluate computational efficiency and agreement with the original estimator.

Critical strengths
  • The proposed algebraic reformulation of the curvature estimator appears mathematically sound and interesting.
  • Given the local neighborhood structure in high-dimensional ambient spaces, exploiting the low-rank structure of the covariance matrices is sensible.
  • Within the considered settings, the experiments across a diverse range of datasets demonstrate substantial computational improvements. In particular, the runtime improvements on USPS and mfeat-factors are significant.
Critical weaknesses
  • The experiments focus on computational efficiency and agreement with the original estimator. It is unclear how the computationally improved estimates would support downstream learning tasks. Furthermore, the evaluation is limited to relatively established benchmark datasets. It remains to be seen how the proposed method would perform in more challenging and larger-scale real-world settings, such as ImageNet-scale classification or other comparably complex domains. While demonstrating the effectiveness of mean curvature estimation in downstream applications is not the primary goal of this work, additional evidence of practical utility would help understand the practical significance.

  • The proposed method assumes that the observations, represented as points in a high-dimensional ambient space, are sampled from an underlying low-dimensional manifold. The usefulness of the resulting curvature estimates therefore depends on whether this assumption is appropriate for the data under consideration. However, the experiments do not directly investigate this aspect. It remains unclear whether the estimated curvature provides useful geometric information in the considered real-world datasets.

  • In Step 1, the authors assume that the nearest neighbors provide a discrete approximation of a local coordinate chart. However, the reliability of this approximation appears to depend on the neighborhood size k, which may itself depend on the intrinsic manifold dimensionality, sampling density, and local curvature. Since these quantities are generally unknown, the authors should clarify how an appropriate value of k can be determined in practice.

  • In Step 2, the authors associate the inverse local covariance matrix with the Riemannian metric tensor. However, the covariance matrix depends on the sampling distribution on the manifold, while the Riemannian metric induced by the embedding is a geometric quantity. This association appears to require additional assumptions. The authors should clarify under what conditions the inverse covariance provides an appropriate approximation of the local metric and how this affects the interpretation of the resulting curvature estimates.

  • In Step 3, the leading d eigenvectors of the local covariance matrix are interpreted as a basis for the tangent space. However, the intrinsic dimensionality d is generally unknown. Furthermore, even when the observations are sampled without noise from a d-dimensional manifold, the remaining D-d covariance eigenvalues are not necessarily zero. The authors should clarify the distinction between the intrinsic manifold dimensionality and the algebraic rank of the local covariance matrix.

Although Steps 1-3 in Section 2 do not constitute the main contribution of this paper, their implications for the proposed estimator deserve further discussion.

  • The original curvature estimator appears to depend on the choice of basis within the null space. The proposed approximation replaces the corresponding contribution with its analytically computed expectation, removing the dependence on the particular choice of null-space basis. However, it remains unclear whether the resulting estimates accurately capture the underlying geometric mean curvature. This does not necessarily undermine the proposed computational approach, but the authors should clarify the scope and limitations of their empirical evaluation.

  • The ambient dimensionality m should be defined before the complexity O(m4)O(m^4) is first mentioned (line 55).

  • Similarly, k should be defined when it is first used (line 66).

Questions for authors

Please see weakness section.

1 comment

Thank you for your careful reading of our paper and for the thoughtful feedback. We appreciate your positive remarks on the algebraic reformulation, on the use of the low-rank structure of the local covariance matrices, and on the computational gains observed across the datasets. Your comments are helpful, and we are working on the manuscript to implement any pertinent improvements.

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

This work proposes MeCuCo, a faster implementation of the MCBP local mean-curvature estimator introduced in [1]. The authors first provide an exact algebraic reformulation and then further reduce computational complexity by exploiting the lowrankness of the covariance matrix. Both these accelerations are combined in MeCuCo. Validation compares runtime and agreement between MeCuCo and the original estimator MCBP on a variety of realworld datasets.

Reference:

[1] Levada. A mean curvature approach to boundary detection: Geometric insights for unsupervised learning. 2026. arXiv.2605.04274.

Critical strengths
  • The paper proposes an algorithm that reduces time complexity compared to MCBP [1], which is the main contribution of the paper.
  • The proposed algorithm is tested against a large number of datasets.
Critical weaknesses
  • The paper doesn't discuss related works in curvature estimation [2, 3, 4] and compare them in the experiment.
  • The paper doesn't provide any indicator to show if the baseline and their improvements could actually capture the true curvature of data.
  • The notations are not consistent throughout the paper. For example, the dimension of ambient space is notated as mm in the first and third sections, while being DD in the second section.
  • Minor:
    • The roadmap at the end of section 1 doesn't match the paper structure.
    • Typo at line 242 ("resukting")

Reference:

[2] Hickok and Blumberg. An Intrinsic Approach to Scalar-Curvature Estimation for Point Clouds. 2023. arXiv.2308.02615.

[3] Wang et al. Curvature Estimation on Data Manifolds via Diffusion-augmented Sampling. NeurIPS 2025 Workshops on Symmetry and Geometry in Neural Representations.

[4] Álvarez-Vizoso et al. Manifold curvature from covariance analysis. IEEE SSP 2018.

Questions for authors
  • Could the authors provide results on synthetic data sampled from manifolds embedded in higher dimension space, for example, sphere, hyperboloid, cylinder, torus, plane, or Cartesian products of them? This is needed to evaluate the reliability of both the proposed methods and the baselines.
  • The experimental result of 'wine' in Table 1 seems impossible to me. The difference between the normalized results of MeCuCo and the original method is 0, but the averages suggest differently: the average normalized curvature from the original is 0.1640, while the average result from MeCuCo is 0.1579. Could the authors clarify this mismatch?
  • The normalized MAE metric might not be a good measurement of divergence between 2 sets of curvature, as 2 sets of numbers different only in scale could result in 0 difference. Could the authors provide results in terms of relative difference on the unnormalized curvatures, as it could be a better alternative?
1 comment

Thank you for taking the time to review our submission and for your detailed comments and questions. We appreciate your recognition of the reduced time complexity and of the breadth of datasets used in the evaluation. We are currently working on the paper and will incorporate any pertinent improvements in the revised version.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.