PaperlayerView exact revision on arXiv

Source-linked AI summary

Curvature-Aware Radius Shrinkage for Adaptive Nearest Neighbor Classification

Alexandre L. M. Levada

arXiv:2608.27634v1cs.LGcs.AIcs.CVstat.ML

TL;DR

Conventional k-NN uses one global neighborhood cardinality even when local geometry varies, motivating a more flexible definition of locality. CARSANN estimates intrinsic geometry and uses curvature to shrink or preserve neighborhood radius, achieving stronger benchmark performance while retaining a complementary spatial-support perspective.

  • Problem

    Globally fixed k can impose inappropriate locality across heterogeneous regions with differing density, structure, and geometric complexity.

  • Method

    CARSANN estimates intrinsic dimension with TwoNN, constructs a PCA representation, estimates local mean curvature, and uses it to adapt neighborhood radius.

  • Results

    CARSANN achieved higher balanced accuracy on 40 of 45 datasets, increasing mean balanced accuracy from 0.6506 for standard k-NN to 0.7528 for CARSANN.

  • Takeaways & Limitations

    Local manifold curvature can serve as a geometric control variable for neighborhood support, complementing methods that adapt neighbor cardinality or local metrics.

  • Takeaways & Limitations

    The current framework uses mean curvature as a scalar descriptor, leaving richer curvature signals and learned curvature-to-radius mappings for future work.

Abstract

from arXiv · show

Nearest neighbor classification relies fundamentally on how locality is defined, yet conventional $k$-NN imposes the same neighborhood cardinality throughout the feature space. This assumption can be inadequate for data whose local geometry varies substantially across the underlying manifold. We introduce Curvature-Aware Radius Shrinkage for Adaptive Nearest Neighbor Classification (CARSANN), a geometry-driven framework that adapts the spatial support of each neighborhood according to local geometric complexity. CARSANN first estimates intrinsic dimensionality using TwoNN and constructs an intrinsic representation through principal component analysis. Local mean curvature is then estimated using a shape-operator-based formulation and controls neighborhood scale: highly curved regions receive stronger radius shrinkage, whereas approximately flat regions retain broader spatial support. Unlike methods that modify only the number of neighbors or the local metric, CARSANN explicitly adapts the spatial extent of local evidence. Experiments on more than 70 real-world OpenML datasets show that CARSANN consistently improves upon standard $k$-NN and is competitive with adaptive nearest-neighbor methods. In a controlled comparison using the same base neighborhood size, CARSANN achieves higher balanced accuracy on 40 of 45 datasets, increasing mean balanced accuracy from 0.6506 to 0.7528. The advantage also persists against $k$-NN with fixed $k=5$. Friedman and Nemenyi tests confirm that the improvements are statistically significant. These results indicate that local manifold curvature can serve as an effective geometric control variable for adapting neighborhood support, providing a complementary paradigm to cardinality-based nearest-neighbor adaptation.

1 Introduction

CARSANN addresses the limitations of globally fixed k by adapting neighborhood radius to local curvature, using intrinsic-dimensional geometry to define local support. It complements cardinality- and metric-based adaptation with explicit spatial-scale control.

  • Motivation: A globally fixed k imposes one notion of locality despite heterogeneous density, nonlinear structure, class imbalance, and varying geometric complexity.Small k can increase variance and sensitivity to noise, while large k can increase bias and oversmooth class boundaries.
  • Method: CARSANN estimates intrinsic dimensionality with TwoNN and uses PCA to construct the representation for local geometric estimation.The intrinsic representation defines the geometric space in which curvature is computed.
  • Method: Local mean curvature controls radius shrinkage: highly curved observations receive smaller effective neighborhoods, while low-curvature observations retain broader support.The reference radius comes from a baseline neighborhood with k0 = log2(n), followed by a monotone nonincreasing shrinkage function.
  • Novelty: Existing adaptive methods vary neighborhood cardinality or modify local metrics, whereas CARSANN adapts the neighborhood radius from local curvature.This distinguishes spatial extent from the number of retained observations.
  • Contribution: The framework introduces a complementary geometric degree of freedom by controlling the spatial scale over which local classification evidence is aggregated.The distinction is that changing k controls how many observations are retained, whereas changing radius controls how far evidence may influence classification.

2 Related Work

Related work progressively adapts nearest-neighbor locality through sample-dependent cardinality, discriminative metrics, and curvature-based neighbor selection. CARSANN extends this progression by adapting spatial extent rather than neighborhood cardinality.

  • Cardinality adaptation: Adaptive nearest-neighbor methods replace globally fixed k with neighborhood cardinality that varies across observations.This line of work includes sample-dependent, heuristic, and optimization-based strategies.
  • Curvature-based adaptation: kK-NN uses shape-operator-based local curvature to determine neighborhood cardinality, favoring larger neighborhoods in flatter regions and more localized ones in curved regions.Its geometric signal is similar in spirit to CARSANN but operates on the number of neighbors.
  • Scalability: Scalability methods reduce the computational cost of neighborhood construction but primarily address efficiency rather than the geometric definition of locality.Approaches include early termination, indexing, pruning, partitioning, and distributed implementations.
  • Positioning: CARSANN asks how far a neighborhood should extend, providing a complementary radius-based alternative to methods that primarily ask how many neighbors to include.This distinction is especially relevant when equal neighbor counts occupy different spatial volumes under heterogeneous density.

3 Differential Geometry Concepts

The differential-geometric formulation treats data as locally lower-dimensional manifolds embedded in higher-dimensional spaces. Tangent spaces provide local first-order approximations, whose validity decreases as curvature increases.

  • Manifolds and local coordinates: A smooth d-dimensional manifold embedded in R^m has local degrees of freedom described by d coordinates, potentially with d much smaller than m.This formalizes the manifold hypothesis used to motivate intrinsic geometric analysis.
  • Manifolds and local coordinates: A local parametrization maps an open subset U of R^d into the embedded manifold M in R^m.The map provides local coordinates for representing points on the manifold.
  • Manifold motivation: Intrinsic-dimensional geometric computation can reveal local data structure that is obscured by the ambient representation.The framework uses this distinction because curvature estimation becomes more difficult as ambient dimension increases.
  • Tangent space: The tangent space T_xM is the d-dimensional linear space containing tangent vectors to curves on M through x.It supplies the local first-order approximation of the manifold.
  • Tangent-space approximation: Tangent-space approximation becomes increasingly inaccurate as neighborhoods extend into regions of stronger curvature.This motivates using local curvature to determine the spatial scale for neighborhood aggregation.

3.3 Metric Tensor and the First Fundamental Form

The metric tensor, or first fundamental form, defines intrinsic lengths and angles on an embedded manifold. It provides the intrinsic geometric structure that precedes descriptions of extrinsic bending.

  • Metric tensor: For an embedded manifold, the metric is induced by the standard inner product of the ambient Euclidean space.It measures lengths and angles between tangent vectors.
  • First fundamental form: In local coordinates, the metric tensor is represented by the first fundamental form.This coordinate representation determines intrinsic geometric measurements.
  • Intrinsic geometry: The local metric tensor determines the intrinsic notion of length and angle on the manifold.It also determines the squared norm of tangent vectors.
  • Intrinsic versus extrinsic geometry: The first fundamental form characterizes intrinsic geometry, whereas the second fundamental form describes how the manifold bends within ambient space.The distinction separates intrinsic metric structure from extrinsic curvature.

3.4 Normal Space and the Second Fundamental Form

The normal space complements the tangent space, while the second fundamental form measures how the manifold bends away from its tangent approximation.

  • The normal space N_xM is the orthogonal complement of the tangent space in the ambient space.
  • For a hypersurface, the normal space is one-dimensional and can be represented by a unit normal vector n(x).
  • The second fundamental form measures variation of the normal direction along tangent directions and characterizes extrinsic curvature.
  • In local coordinates, the second fundamental form is represented through its coefficients.
  • Unlike the first fundamental form, which describes local metric structure, the second fundamental form captures local bending of the embedded manifold.

3.5 Shape Operator

The shape operator, or Weingarten map, connects the first and second fundamental forms and spectrally characterizes local manifold curvature through principal curvatures.

  • The shape operator, also called the Weingarten map, expresses the relationship between the first and second fundamental forms.
  • Because the shape operator is self-adjoint under the induced metric, it has an orthonormal eigenbasis.
  • Its eigenvalues are the principal curvatures, with corresponding eigenvectors defining the principal directions.
  • Large magnitudes of principal curvatures indicate strong bending directions, whereas small values indicate closer agreement with the tangent approximation.
  • Moving along a tangent direction, the shape operator measures directional variation of the unit normal vector as a quantitative description of local bending.

3.6 Mean Curvature

Mean curvature summarizes the principal curvatures through the normalized trace of the shape operator and provides a scalar measure of local manifold bending relevant to neighborhood scale.

  • Mean curvature is defined as the normalized trace of the shape operator.
  • It can equivalently be expressed using the first and second fundamental forms.
  • Small |H(x)| indicates an approximately flat or minimal configuration, whereas larger |H(x)| indicates stronger average bending.
  • Low-curvature neighborhoods can generally extend farther while remaining compatible with the tangent approximation.
  • High curvature causes the tangent approximation to deteriorate more rapidly as neighborhood radius increases, motivating curvature-based scale control.

3.7 Geometric Interpretation for Neighborhood Adaptation

CARSANN uses intrinsic geometric quantities, especially local curvature, to adapt neighborhood radius: complex regions receive smaller support, while approximately flat regions retain broader support.

  • The tangent space provides a first-order local approximation, while the metric tensor defines distances and angles within that representation.
  • The second fundamental form and shape operator characterize departure from the tangent space, with shape-operator eigenvalues giving principal curvatures.
  • CARSANN uses local curvature to shrink a reference neighborhood in geometrically complex regions and preserve broader support in approximately flat regions.
  • Higher-curvature regions depart faster from the tangent-space approximation and therefore receive a smaller effective neighborhood radius.

3.8 Intrinsic Dimension and the TwoNN Algorithm

CARSANN estimates the unknown intrinsic dimension with TwoNN before applying its geometric pipeline. TwoNN uses first- and second-nearest-neighbor distance ratios, whose distribution depends on intrinsic dimension under local density homogeneity, followed by regression and PCA-based intrinsic representation.

  • TwoNN estimator: TwoNN estimates intrinsic dimension from each point’s distances to its first and second nearest neighbors, avoiding an additional neighborhood-size hyperparameter.The estimator is intended to reduce sensitivity to density inhomogeneity and curvature compared with estimators using larger fixed neighborhoods.
  • Distributional basis: Under local density homogeneity, the ratio µ = r2/r1 follows F(µ) = 1 − µ^-d, so its distribution identifies intrinsic dimension d independently of local density.The result assumes observations arise from a locally homogeneous Poisson process on a d-dimensional manifold.
  • Regression estimation: TwoNN estimates d by fitting an empirical log-log relation whose slope is d, with CARSANN using an unconstrained affine regression and recovering d̂ = −a.The upper tail of the ratio distribution is discarded before fitting to reduce violations of local density homogeneity.
  • Pipeline role: The intrinsic-dimension estimate determines the representation used for curvature estimation and the neighborhood sizes used by CARSANN.CARSANN rounds the estimate to the nearest integer, enforces a minimum of two dimensions, and applies PCA when d < m.

4 Local Mean Curvature Estimation

CARSANN estimates local mean curvature from covariance-derived principal directions and a closed-form quadratic feature map. The resulting orientation-invariant curvature magnitude measures local bending and supplies the geometric signal for neighborhood-scale adaptation.

  • Role in classification: Mean curvature controls the scale of locality rather than the class label, while labels within the resulting neighborhood determine the prediction.Approximately flat regions can retain broader support, whereas highly curved regions call for more localized evidence.
  • Local geometric representation: CARSANN represents local geometry through covariance matrices computed from k-nearest-neighbor patches in an intrinsic-dimensional representation.Dominant covariance eigenvectors provide a first-order approximation of the local tangent space, while inverse covariance supplies a local anisotropic metric.
  • Quadratic feature map: The covariance eigendecomposition yields principal directions, whose squared components and pairwise Hadamard products form the local quadratic feature map.This map contains d(d+1)/2 quadratic features and replaces explicit per-neighbor regression with a deterministic function of the local eigenbasis.
  • Shape-operator estimation: CARSANN uses a closed-form, regression-free shape-operator estimator that reuses the covariance eigendecomposition to approximate the second fundamental form and shape operator.The construction adapts the estimator introduced for kK-NN to the intrinsic-dimensional representation.
  • Curvature measure: The eigenvalues of the shape operator provide principal curvatures, from which CARSANN derives mean curvature and its magnitude as the scalar complexity measure.Taking curvature magnitude removes dependence on the chosen normal orientation and captures average bending regardless of principal direction.

5 CARSANN: Curvature-Aware Radius Shrinkage Adaptive Nearest Neighbors

CARSANN separates curvature estimation from classification by using a larger curvature patch and a smaller reference voting neighborhood, then contracts voting support according to local mean curvature. The contraction is implemented by truncating a sorted candidate list, which is equivalent to reducing the voting radius and keeps geometric computation in the intrinsic dimension.

  • Dual-scale neighborhoods: CARSANN uses separate curvature-patch and reference-voting sizes, enforcing kbase ≤ kcurv so voting neighbors remain within the region used for curvature estimation.The dual-scale design supports stable second-order curvature estimation while preserving a small, local classification neighborhood.
  • Curvature patch: The curvature patch size is chosen from intrinsic dimension and dataset size, with a factor-of-two support margin and Kmax = 50 limiting computational cost.The lower support requirement reflects the number of independent components in the local quadratic model.
  • Reference voting size: The reference voting size kbase is selected once during training by stratified cross-validation to maximize balanced accuracy over an admissible range.The selected size is reused for every test query rather than optimized separately at prediction time.
  • Curvature normalization: CARSANN computes local curvature with the closed-form shape-operator estimator in the intrinsic representation and fixes log-curvature normalization using the training set.The same training-derived normalization is reused for all test queries, making the curvature scale independent of test-batch composition.
  • Curvature-to-support mapping: The shrinkage factor decreases with curvature, so highly curved points retain fewer active neighbors while flatter points retain more of the kbase candidates.Voting uses the k(x) closest points among the kbase-nearest-neighbor set.
  • Radius-shrinkage equivalence: Restricting voting to the k(x) closest candidates is equivalent to using a metric ball of radius r(x) no larger than the reference radius r(0)(x).Equality holds when k(x) = kbase, while distance ties are the only qualification to exact set equality.
  • Computational realization: Because curvature-dependent truncation reuses the existing sorted candidate list, CARSANN avoids explicit radius queries and makes effective radius monotone nonincreasing in local curvature.This implementation preserves the radius-shrinkage rule without rebuilding neighborhood structures at prediction time.
  • Computational complexity: Performing geometric analysis in intrinsic dimension replaces ambient-dimensional dependence with dependence on the typically smaller d.The complexity discussion identifies this reduction as the central computational benefit of the representation.

6 Computational Experiments and Results

Experiments show that CARSANN’s curvature-aware radius adaptation improves classification over standard k-NN in controlled comparisons and is competitive with adaptive alternatives, while not uniformly dominating every method or dataset.

  • Experiment 1: CARSANN’s curvature-aware radius is not equivalent to curvature-based neighbor-count adaptation: CARSANN performs better on some datasets, while Kk-NN remains preferable on others.The comparison indicates that translating curvature into spatial support versus neighborhood cardinality affects classification performance differently.
  • Experiment 1: DANN outperforms CARSANN on some datasets, including confidence, where DANN reaches balanced accuracy 0.8333 and F1-score 0.9398.The paper therefore treats geometric complexity and discriminative structure as complementary sources of local adaptation.
  • Experiment 1: CARSANN significantly outperformed standard k-NN, DANN, and Kk-NN in balanced accuracy according to post-hoc Nemenyi tests.The reported p-values were 2.55 × 10−11, 2.43 × 10−4, and 0.0077, respectively, at α = 0.05.
  • Experiment 2: 40 of 45 datasets achieved higher balanced accuracy with CARSANN than standard k-NN when both used k = kbase.This controlled comparison isolates curvature-aware radius adaptation from the initial neighborhood cardinality.
  • Experiment 2: 0.1022 absolute balanced-accuracy improvement raised the mean from 0.6506 for standard k-NN to 0.7528 for CARSANN at k = kbase.Mean F1-score also increased from 0.7053 to 0.7933.
  • Experiment 2: 40 of 45 datasets also favored CARSANN in balanced accuracy against standard k-NN with fixed k = 5, with mean balanced accuracy increasing from 0.6547 to 0.7568.The corresponding mean F1-score increased from 0.7118 to 0.7966, and performance remained stable across the two configurations.
  • Experiment 2: CARSANN does not outperform standard k-NN on every dataset; under k = kbase, standard k-NN performs better on five named datasets.The largest reported degradation is on micro-mass (v1), where balanced accuracy falls from 0.7772 to 0.6606.

7 Conclusions and Final Remarks

CARSANN adapts neighborhood spatial support using local curvature rather than relying solely on neighborhood cardinality. Experiments support this geometry-driven approach, while remaining limitations concern curvature representation and the curvature-to-radius mapping.

  • Method: CARSANN uses local mean curvature to shrink neighborhood radii in highly curved regions and preserve broader support in flatter regions.The method estimates curvature after intrinsic-dimensionality estimation and PCA-based representation.
  • Novelty: CARSANN controls spatial neighborhood extent, complementing methods that adapt neighbor count or local metrics.This extends adaptive nearest-neighbor classification from cardinality adaptation to geometry-driven support adaptation.
  • Results: CARSANN significantly outperformed standard k-NN, DANN, and Kk-NN in balanced-accuracy post-hoc Nemenyi comparisons across the evaluated datasets.The first experiment also reported substantial balanced-accuracy and F1-score improvements on many datasets.
  • Results: 40 of 45 datasets favored CARSANN in balanced accuracy under equal base neighborhood cardinality.Mean balanced accuracy increased from 0.6506 for standard k-NN to 0.7528 for CARSANN.
  • Results: CARSANN’s advantage persisted against standard k-NN with fixed k = 5, supporting radius adaptation beyond choosing a more favorable neighbor count.The controlled comparison attributes the distinction to adapting spatial support according to local curvature.
  • Limitations and future work: The framework adds preprocessing overhead and has computational scaling O(nd log n) + O(nd4), with curvature estimates computed once for training data.Geometric computations are performed in the intrinsic representation and separated from online classification.
  • Limitations and future work: Current limitations include using scalar mean curvature and a fixed curvature-to-radius mapping, motivating richer geometric signals and learned transformations.Future work also considers robust estimators, approximate search, noisy manifolds, and supervised or semi-supervised variants.

Statements and declarations

The paper acknowledges financial support and provides reproducibility resources. The experiments use publicly available OpenML datasets.

  • Funding: The study received support from CNPq through grant #301432/2025-2 and partial funding from CAPES Finance Code 001.
  • Reproducibility: Python scripts for reproducing the reported results are available in the authors’ CARSANN GitHub repository.The implementation is described as a first version of the CARSANN classifier.
  • Data availability: All datasets used in the experiments are publicly available through OpenML.
Loading 2608.27634v1…