PaperlayerView exact revision on arXiv

Source-linked AI summary

Bracketing Uncertainty in Clustering Under the Manifold Hypothesis

Savik Kinger, Luciano Dyballa, Steven W. Zucker

arXiv:2609.17892v1stat.MLcs.LGq-bio.QM

TL;DR

Clustering under the manifold hypothesis asks whether data come from one connected component or several, but sample gaps can leave that decision unresolved. MBC uses mutual-kNN threshold bounds to return a bracket of plausible cluster counts; the paper reports that many real datasets fall in the uncertainty zone rather than admitting one clear answer.

  • Problem

    Under the manifold hypothesis, deciding whether sampled data have distinct manifold components is difficult when component separation must be judged against gaps in sample coverage.

    Source: §1 · pp. 1–2

  • Method

    MBC combines manifold geometry and sample fill distance to bound cross-component edges in mutual-kNN graphs, then brackets counts across scales left unresolved by those bounds.

    Source: §1 · p. 3, §3.1 · p. 4

  • Results

    Many real datasets lie in the geometric uncertainty zone; on 38 synthetic datasets, MBC has median bracket width 0 and 68% coverage of K⋆.

    Source: §5.1 · p. 8, §6 · p. 10

  • Takeaways & Limitations

    The bracket quantifies when a single clustering choice is justified by the data rather than forcing one when multiple resolutions remain supported.

    Source: §6 · p. 10

    The threshold constants depend on intrinsic dimension, so when ambient distance fails to reflect intrinsic geometry, the bracket can narrow and miss the relevant cluster structure.

    Source: §6 · p. 10

Abstract

from arXiv · show

The manifold hypothesis suggests a natural criterion for clustering: partition data according to the manifold component from which each point is drawn. Whether two components are separable depends on a geometric tradeoff: the ambient separation between components versus the largest gap in sampling. In practice, this tradeoff is rarely assessed explicitly, leading standard methods to over-commit to a single clustering assignment even when the data do not support a unique answer. We formalize this tradeoff by combining intrinsic manifold geometry (volume growth and reach) with sample-level quantities (fill distance and density), yielding a threshold phenomenon for mutual-$k$-nearest-neighbor graphs: when the offset-to-fill ratio exceeds a conservative upper threshold, component separation is preserved; below a lower threshold, components fuse. The gap between these thresholds defines a geometric uncertainty zone in which the number of clusters is not identifiable from the data. Nevertheless, conventional approaches still seek one: sweeping parameters (an engineering approach) or fitting a generative mixture model (a model-based approach). Rather than forcing a single estimate of the number of clusters, we propose Manifold-Based Clustering (MBC), which returns an explicit bracket interval to quantify the underlying data uncertainty. This bracket acts as an empirically calibrated diagnostic: it narrows when a single resolution is supported, widens when multiple resolutions coexist, and collapses to one when no separated structure is detectable. Empirically, we find that many real datasets lie within the uncertainty zone rather than admitting one clear answer. Our results suggest that ambiguity in cluster number is often intrinsic, and should be quantified rather than resolved.

1 Introduction

The paper frames clustering as deciding whether sampled manifold support is connected or has distinct components, but that decision can remain uncertain. It develops a geometric threshold for mutual-kNN graphs and turns the unresolved threshold range into a cluster-count bracket.

1 Introduction

  • The manifold hypothesis makes a cluster a connected component of the data’s underlying manifold, recasting clustering as a connectedness decision.The support is modeled as a single connected manifold or a finite union of disjoint components.Source: §1 · p. 2
  • The mutual-kNN threshold depends on the offset between components relative to sample fill distance, with intrinsic volume growth and reach determining its constants.A large offset-to-fill ratio favors separated components; a small one can link them.Source: §1 · pp. 2–3
  • MBC uses a locally regularized mutual-kNN graph filtration and tracks connected components across scales as candidate clusters.Its scale range is informed by the geometric theory.Source: §1 · p. 3
  • MBC brackets the cluster count across a geometric uncertainty zone instead of forcing one estimate when the data do not support a unique answer.The paper evaluates this diagnostic across synthetic, real-world, and neural datasets.Source: §1 · pp. 2–3
  • The paper proves an upper no-bridge bound and a lower bridge bound, then uses the gap between them to construct a finite-sample bracket estimator.The bounds apply to mutual-kNN graphs on separated manifold components.Source: §1 · p. 3

2 Background

The background connects neighborhood-graph clustering to sampling-scale theory and distinguishes the paper’s geometric separation criterion from reach-based and density-threshold approaches.

2 Background

  • Random geometric graph theory places connectivity near k ≍ log n, while mutual-kNN graphs inherit the logarithmic threshold up to a constant.Under two-sided volume growth, fill distance and kNN radii are tightly coupled; comparing offset ∆ with hmax then tests component separation.Source: §2 · p. 3
  • Reach controls the local regularity scale of a manifold, including curvature and narrow bottlenecks, whereas ∆/h compares component separation with sample resolution.The paper’s ratio does not estimate or relax reach.Source: §2 · p. 3
  • Density- and mutual-reachability-threshold methods rely on user-specified parameters, while this method follows components across nested mutual-kNN graphs.The graph filtration is interpreted through the zeroth homology group of a persistence diagram.Source: §2 · p. 3

3 Geometric Cluster-Separation Criterion

The section defines geometric separation in terms of component offset and sample fill distance, then establishes upper and lower thresholds for cross-component edges in a mutual-kNN graph. Their gap identifies a regime where separation cannot be resolved by the threshold guarantees.

3 Geometric Cluster-Separation Criterion

  • The offset ∆ is the minimum distance between manifold components, while fill distance h measures the largest gap in sample coverage; their ratio compares separation with sampling dispersion.Smaller fill distance means denser, more uniform coverage.Source: §3 · p. 4

3.1 Manifold separation criterion

  • The threshold theorem assumes disjoint, compact, connected C2 manifolds with positive reach and locally bounded sampling mass.Its dimension is intrinsic dimension d, which may be smaller than ambient dimension D.Source: §3.1 · p. 4
  • Above the upper offset-to-fill threshold, the mutual-kNN graph has no cross-component edge; below the lower threshold, it contains one with high probability.The threshold statement also gives failure-probability bounds for the two directions.Source: §3.1 · pp. 4–5
  • For the upper-threshold direction, bounding every kNN radius below the component offset rules out cross-component neighbor relations and hence mutual edges.The proof first places fill distance and kNN radii on the same sampling scale.Source: §3.1 · p. 5
  • For the lower-threshold direction, occupied neighborhoods around a closest component pair provide a short cross-component pair whose endpoints become mutual neighbors when same-component competitors are controlled.The proof uses cap occupancy, a bound on same-component crowding, and reciprocity of the closest observed pair.Source: §3.1 · p. 5
  • With balanced sampling and bounded geometry, both threshold bounds scale as Θ(A^(1/d)), with constants depending only on intrinsic dimension d.The stated scaling assumes fixed ε and a and a volume-growth constant ratio c/c = Θ(1).Source: §3.1 · p. 6

4 From thresholds to a bracket estimator

The estimator reverses the fixed-scale threshold result to select graph scales whose bridge transition is unresolved by the practical bounds. It reports the component-count range across that sweep as an empirical bracket of plausible cluster counts.

4 From thresholds to a bracket estimator

  • MBC inverts the two threshold bounds at an empirical offset-to-fill estimate to find graph scales where the bridge transition remains unresolved.The resulting component counts define a range of plausible clustering assignments.Source: §4 · p. 6
  • A pilot graph at k⋆ = ⌈log(4n/δ)⌉ supplies neighborhood radii and a baseline partition for estimating the empirical ratio.The theorem’s scale family is k(A) = ⌈A log(4n/δ)⌉; the practical pilot uses A0 = 1.Source: §4 · p. 6
  • The pilot removes observations with overly large radii and adjusts local degrees for sampling-density variation before forming its mutual-neighbor graph.Large pilot radii are treated as plausible sources of spurious bridges; denser regions receive larger neighbor lists.Source: §4 · p. 6
  • When the empirical ratio falls between practical threshold curves, MBC solves for the scale-range endpoints; outside that regime, it chooses a sweep according to the same geometric criterion.A connected pilot graph or a ratio below the lower curve leads the sweep toward smaller degrees.Source: §4 · p. 7
  • Across the selected integer grid, MBC rebuilds mutual-neighbor graphs and reads candidate clusters from their connected components as increasing k carries partitions from finer to coarser.The primary bracket records the range of counts across this filtration.Source: §4 · p. 7
  • The primary size-filtered bracket is accompanied by raw-count and mass-bounded brackets; a narrow primary range indicates stable counts, while a wide one indicates multiple supported resolutions.A small lower endpoint indicates the representation does not support persistent separation at the sampled scale.Source: §4 · pp. 7–8

5 Experiments

Across synthetic, perturbed, real-world, and biological datasets, the experiments assess how MBC brackets reflect separability and representation limits. Comparisons use parameter-grid baselines and evaluate coverage, width, and informativeness.

5 Experiments

  • The evaluation covers 38 synthetic datasets, 11 real-world benchmarks, and three neural datasets, comparing MBC with DBSCAN and HDBSCAN parameter-grid brackets.MBC parameters are fixed across datasets; informativeness combines coverage of K⋆ with median bracket width.Source: §5 · p. 8

5.1 Bracket calibration

  • 0 median bracket width and 68% K⋆ coverage on 38 synthetic datasets; informativeness was 0.68 for MBC, 0.20 for HDBSCAN-grid, and 0.12 for DBSCAN-grid.MBC was strongest on most synthetic families, while HDBSCAN-grid led on high-dimensional blobs.Source: §5.1 · pp. 8–9, Figure 2 · p. 9

5.2 Bracket response to perturbations

  • Contamination is the hardest axis: pruning is mixed when background noise lies near manifolds, while sampling density and intrinsic dimension behave as predicted.Tightly wound spirals and Swiss rolls remain difficult when local reach is small relative to graph scale; alternative metrics can widen brackets.Source: §5 · p. 8, §5.2 · p. 9

5.3 Representation sensitivity on real-world data

  • All eleven real-world datasets place bρ near the transitional boundary; tabular brackets sometimes cover K⋆, while image and text datasets sit near representation failure.On ImageNet-Dogs, MBC returns [14, 19] around K⋆=15; on ImageNet-100 in the tested representation, it under-resolves.Source: §5.3 · p. 9

5.4 Biological results

  • The full retinal bracket [1, 8] contains the independent physiological estimate K⋆≈8, while the V1 bracket [1, 1] indicates no manifold-separable structure in its embedding.The labeled retinal subset returns [1, 7], containing K⋆=7.Source: §5.4 · p. 10

6 Discussion

The discussion identifies conditions that constrain MBC’s guarantees and reporting, while the appendices document implementation details and additional experiments.

6 Discussion

  • High contamination or weak separation can collapse the bracket to one, while nearly overlapping components fall outside the threshold guarantees.Components smaller than smin are omitted from the primary bracket; the mass-bounded companion bracket retains them, and the primary method misses a true Wine cluster.Source: §6 · p. 10
  • When ambient distance fails to reflect intrinsic geometry, the offset and fill scales can converge and narrow the bracket; geodesic-aware embeddings can expose structure, as in the retinal analysis.The retinal bracket contains the physiological estimate.Source: §6 · p. 10
  • Across synthetic, real-world, and neural data, the bracket trades raw coverage for width and is more informative than parameter-swept baselines; most real datasets fall in the geometric uncertainty zone.The paper concludes that cluster-count ambiguity is often intrinsic and should be quantified rather than resolved by forcing one clustering.Source: §6 · p. 10

Appendix overview.

  • The appendices provide the theorem and observed-sample-offset lemma, implementation and algorithm details, baseline grids, stability and sensitivity analyses, and additional experiments.These include perturbation and sampling-size sweeps, a synthetic-suite catalog, mass-coverage sensitivity, and a neuroscience filtration figure.Source: Appendix overview · p. 13

A Proof of Theorem 2

The proof establishes fill-normalized conditions for mutual-kNN clustering by relating neighborhood radii and fill distances to the manifold offset, deriving conditions for preserving separation or forcing a cross-component edge. It also uses crowding to control the lower-threshold event and extends the argument to observed offsets and bounded perturbations.

A.1 Notation and assumptions

  • The argument assumes compact, connected, disjoint manifolds with positive reach and local mass comparable to r^d; curvature enters only through the local-mass constants.The samples on the two components are independent, and balance is additionally required for the mutual-cross-edge direction.Source: §A.1 · p. 14

We assume

  • Theorem 8 gives a fill-normalized threshold result for the mutual-kNN graph under Assumptions 4–7, with cases stated without balance condition (9) and under conditions (9) and (21).Source: We assume · p. 15

A.2 The neighborhood scale

  • Fill distance is controlled above and below at the canonical sampling scale, with the upper bound requiring both components and the lower bound requiring only the least-sampled component.A uniform kNN-radius bound also places every sample point’s k neighbors within a common radius with probability at least 1 − δ/4.Source: §A.2 · pp. 16, 18

A.3 No cross-component edges

  • On an event whose complement has probability at most 3δ/8, no mutual cross edge exists when the manifold offset exceeds Mhigh times the maximum fill distance.The radius bound excludes cross-component neighbor listings, which precludes a mutual edge.Source: §A.3 · p. 19

A.4 Existence of a mutual cross-component edge

  • For the lower-threshold argument, samples in caps near a closest manifold pair yield a short observed cross pair, while a crowding condition keeps same-component competitors below k.The proof’s crowding event requires Q(z; t) ≤ k − 1 for every sample point.Source: §A.4 · p. 20, Then the event · p. 20

Then the event

  • On the cap and crowding events, the graph contains a mutual cross edge; a label-based choice among closest pairs resolves ties so both endpoint listings hold.The tie-breaking choice first fixes the smallest-labeled S1 endpoint among minimizing pairs, then its smallest-labeled minimizing S2 partner.Source: Then the event · p. 21
  • Under Ecover, a low offset-to-fill ratio forces crowding at radius BΔ, and a deterministic crowding dichotomy yields the lower-threshold event bound (28).The calculation gives the k/4 crowding threshold; the balance assumption is used only to bound (n_i − 1)/m by 2.Source: Then the event · pp. 21–22

A.5 Consequences and extensions

  • The observed sample offset lies between the manifold offset Δ and Δ + 2hmax.The lower bound follows because observed cross-pairs belong to the manifold-pair set; approximating a minimizing manifold pair by samples gives the upper bound.Source: §A.5 · p. 22
  • With perturbations bounded by σ, cross-distances decrease by at most 2σ and clean k-neighbor radii increase by at most 2σ, supporting the no-edge direction on Esep.The corollary gives a sufficient condition for no perturbed mutual cross edge; Proposition 12 then applies.Source: §A.5 · p. 22

B Implementation details

The implementation describes preprocessing, pilot-graph construction, sweep endpoints, component-count brackets, and label selection. The full procedure and mechanism ablations supplement these practical details.

B Implementation details

  • Preprocessing can standardize coordinates and retain the smallest PCA subspace explaining 90% of variance, capped at 64 dimensions; effective dimension uses the same variance rule.When preprocessing is disabled, effective dimension is estimated directly on the supplied representation.Source: B Implementation details · p. 23
  • The pilot graph uses a density-discontinuity gate only for isolated-node fallback edges; fallback and gate are disabled during the persistence sweep.The gated pilot graph supplies the partition used to estimate the offset-to-radius proxy, not the final bracket graphs.Source: B Implementation details · p. 23
  • The practical sweep endpoints invert theory-informed threshold curves, and the resulting interval is clipped to [0.15A0, 4A0] and enlarged if needed to contain A0.The endpoint map retains dependence on A1 and effective dimension while absorbing unknown geometric factors into the curves.Source: B Implementation details · p. 23
  • The mass-bounded bracket tracks the smallest number of largest components covering at least 95% of retained observations across sampled scales; a run-length variant keeps counts repeated at consecutive scales.The ordinary mass bracket is reported by default because run-length filtering can remove the reference count.Source: B Implementation details · p. 24
  • When the strict estimate is 1 but the bracket spans multiple counts, bKprac selects the most frequent non-trivial sweep count, breaking ties toward larger counts.If no non-trivial count occurs, it returns 1.Source: B Implementation details · p. 24
  • The DBSCAN and HDBSCAN parameter grids define swept-count brackets, while single-K baselines run at K = K⋆ when ground truth is known.Spectral is skipped for n > 3,000 because of memory constraints.Source: B Implementation details · p. 24

C Full pseudocode

  • The full algorithm preprocesses and prunes observations, builds a gated pilot graph to set the sweep range, then records raw, size-filtered, and mass-bounded counts across sampled mutual-neighbor graphs.It returns brackets, point estimates, representative labels, and diagnostics; eligible density-pruned observations may receive labels afterward.Source: C Full pseudocode · p. 25

D Mechanism ablations: A-sweep, reciprocity, and pruning

  • The mechanism ablations vary the logarithmic coefficient, mutual reciprocity, and density pruning across three seeds and five n = 2000 datasets spanning five structural settings.The settings include clean low- and high-dimensional separation, background contamination, non-separable moons, and hierarchical structure.Source: D Mechanism ablations: A-sweep,… · p. 25

D.1 A-sweep on representative datasets

The A-sweep shows how the bracket changes with scale, mutual kNN preserves a wider bracket on bridge-sensitive moons, and pruning has limits when contaminants are not distinguishable by pilot radii.

D.1 A-sweep on representative datasets

  • Near A = 1, the clean separable blobs-2D-clean bracket is [K⋆, K⋆], while increasing A moves well-separated datasets toward [1, Khigh].By Acert = 12, every non-noisy dataset has Klow = 1; the contamination case collapses at A = 1 and never recovers.Source: §D.1 · pp. 25–26, Table 2 · p. 25

D.2 Mutual versus union kNN at the primary scale

  • On bridge-sensitive two-moons, the mutual graph returns [1, 3], whereas the union graph collapses to [1, 1]; separated cases have identical brackets.Table 3 compares the two graph types at A = 1 with other parameters fixed.Source: §D.2 · p. 26, Table 3 · p. 26

D.3 Density pruning on the contamination case

  • Pruning removes only ≈1% of background contaminants when they lie near blob components, and its effects across seeds are mixed.The rule is most useful when off-manifold points have noticeably larger pilot radii; it is not a general remedy for overlapping or near-manifold noise.Source: §D.3 · p. 26, Table 4 · p. 26

E Sensitivity to δ and α

The sensitivity and perturbation studies show that MBC’s bracket responds differently across regimes and perturbations. Results also assess stability, sampling size, and alternative interval constructions.

E Sensitivity to δ and α

  • The easy 50D blobs remain at [6, 6] across the δ and α grid, while retina and noisy moons vary near the transitional regime.Table 5 reports endpointwise min, median, and max across the grid rather than literal brackets for each seed.Source: E Sensitivity to δ and α · p. 27, Table 5 · p. 27

F Multi-seed stability

  • Mean within-dataset ARI standard deviation is 0.098 on 38 synthetic datasets and 0.005 on 11 real-world datasets; variability concentrates in hierarchical and contaminated datasets.The corresponding Khigh standard deviations are 1.86 and 0.27.Source: F Multi-seed stability · p. 27

G Perturbation walk

  • Increasing spread or decreasing centroid distance shifts the bracket toward smaller counts, while contamination is less monotone because noise often lies near blobs.The perturbation walk uses a clean four-blob base configuration in R2 with n = 1500 and varies one axis at a time.Source: G Perturbation walk · p. 27, Table 6 · p. 27

H Sampling sweep

  • For moons, the bracket narrows from a wide low-n range to [2, 2] at n = 5,000; the high-dimensional primary bracket is already tight.The practical label count briefly differs at intermediate sample sizes.Source: H Sampling sweep · p. 27, Table 7 · p. 28

I.1 Alternative interval constructions

  • HDBSCAN has the highest coverage but a substantially wider interval; the variational mixture is slightly narrower than MBC on average but has lower coverage and nonzero median width.MBC derives endpoints from selected graph scales, unlike the parameter sweep or subsampling variability used for the alternatives.Source: §I.1 · p. 28, Table 8 · p. 28

I.2 Geometric robustness

The robustness analyses examine curvature and distance metrics, while the image benchmarks and downstream tests assess MBC’s outputs on large-scale data.

I.2 Geometric robustness

  • Across quadratic patches with center curvatures −2, −0.5, 0, 1, and 2, bracket widths are 0.3, 1.3, 1.3, 1.0, and 0.3, and every bracket contains the true count.Mean ARIs range from 0.990 to 0.992, with no monotone degradation as curvature changes.Source: §I.2 · p. 28
  • Euclidean distance gives the narrowest or tied-narrowest bracket on every row; cosine fragments two-moons, while Manhattan widens the high-dimensional blob bracket.The theory’s extension to these alternatives requires corresponding metric-ball bounds in place of the Euclidean local-mass condition.Source: §I.2 · pp. 28–29, Table 9 · p. 29

I.3 Large-scale image benchmarks and downstream use

  • On ImageNet-100, MBC returns [16, 60], while on ImageNet-Dogs it returns [14, 19] around K⋆ = 15; only HDBSCAN’s broad ImageNet-100 interval contains all 100 recorded classes.On ImageNet-Dogs, values drawn from the MBC interval yield the highest mean downstream ARI for both KMeans and spectral clustering; silhouette-selected KMeans is the exception, where DBSCAN slightly exceeds MBC.Source: §I.3 · p. 29

J Synthetic suite: catalog and per-dataset results

The synthetic catalog shows how bracket behavior changes with sampling conditions and geometric ambiguity, while mass-bounded variants expose a coverage–width tradeoff as γ increases.

J Synthetic suite: catalog and per-dataset results

  • The synthetic suite contains 38 datasets across eight families, generated at approximately 2,000 samples with K⋆ fixed by the generator.The families stress classic shapes, noise, contamination, scale, dimension, hierarchy, imbalance, and near-boundary geometry.Source: J Synthetic suite: catalog and… · p. 29
  • Clean shapes have tight brackets, while added noise or contamination widens brackets or lowers their lower endpoint as separation becomes less defensible.Hierarchical and adversarial cases can yield wide or collapsed brackets, reflecting multiple defensible resolutions or no separated resolution at the sampled scale.Source: J Synthetic suite: catalog and… · pp. 29–30
  • In high-dimensional data, the primary bracket can retain the intended count while the mass companion exposes many small fragments in Euclidean space.The two brackets therefore serve different diagnostic purposes.Source: J Synthetic suite: catalog and… · pp. 29–30

K Mass-bounded bracket sensitivity

  • On synthetic data, the primary bracket has the highest informativeness; on labeled real data, increasing γ raises coverage but rapidly widens intervals.All mass-bounded variants cover both neuroscience targets, with width increasing in γ.Source: K Mass-bounded bracket sensitivity · p. 30
  • γ = 0.90 often drops true minorities comprising 5%–10% of the sample, whereas γ = 0.98 admits long fragmentation tails and greatly widens real-data intervals.The authors use γ = 0.95 as an intermediate coverage diagnostic; the run-length variant is not recommended by default because it performs poorly on short real and neuroscience sweeps.Source: K Mass-bounded bracket sensitivity · p. 31

L Neuroscience filtration: per-dataset results

The figure presents retinal ganglion cell and V1 data in diffusion-map space alongside their filtration behavior across the uncertainty zone.

L Neuroscience filtration: per-dataset results

Loading 2609.17892v1…