GRASP: Graph-Routed Adaptive Spectral Partitioning

The fundamental difficulty in clustering is that the optimal algorithm depends on geometric and statistical properties of the dataset that are precisely unknown in the unsupervised setting. In practice, practitioners execute several algorithms in succession, selecting among them via visual inspection or labelled validation data — neither of which is available in genuinely unsupervised analysis.

Clustering — sorting items into groups where similar things end up together — has one big catch. The best algorithm depends on the shape and spread of your data, but you cannot see either without labels. So people just run a few algorithms back to back and pick the answer that looks right, or compare it against labelled data. Neither option exists when your data is truly unlabelled.

GRASP's three design principles separate it from existing methods. First, topology-prior partitioning constructs a topology map before committing to any partitioning strategy, at cost O(nm) independent of k. Second, geometry-adaptive routing selects the specialist on the basis of diagnostics extracted from the topology map — not heuristics external to the pipeline. Third, selective spectral deployment applies full spectral computation only when topological evidence indicates Euclidean methods are insufficient, keeping the typical cost at O(nm).

Three design choices set GRASP apart. First, map first, decide later: it builds a shape map of the data before picking how to split it — the cost is O(nm), which doesn't grow with the number of groups k. Second, let the map pick the tool: the algorithm is chosen using signals read from the map, not outside rules of thumb. Third, save the expensive math for when you need it: heavy spectral computation runs only when straightforward methods clearly won't work. The typical cost stays at O(nm).

Full spectral clustering incurs O(n²) memory for the kernel matrix and O(n³) for eigendecomposition — prohibitive at n ≥ 10,000. GRASP's Nyström extension with GNG landmarks reduces this to O(nmk) with data-proportional coverage, enabling spectral-quality clustering at linear cost.

Standard spectral clustering chokes on big datasets. It needs O(n²) memory and O(n³) time, so once you hit n ≥ 10,000 points it becomes impractical. GRASP sidesteps this with a Nyström approximation built on GNG landmarks — a smart way to learn from a representative slice instead of every point. Cost drops to O(nmk) and the landmarks cover the data evenly, so quality stays high.

GRASP was evaluated on 26 benchmark datasets in six categories: non-convex shapes (moons, circles, spirals, interlocking rings, swiss_roll_2d, anisotropic, varied_density; n = 150–1000), SIPU S-sets s1–s4, A-sets a1–a3, UCI real-world (Iris, Wine, Breast Cancer, Digits), and scalability datasets at n = 50,000.

We threw 26 datasets at GRASP, grouped into six families. Tricky shapes: moons, circles, spirals, interlocking rings, swiss_roll_2d, anisotropic, varied_density (n = 150–1000). Standard academic benchmarks: SIPU S-sets s1–s4 and A-sets a1–a3. Real-world data from UCI: Iris, Wine, Breast Cancer, Digits. And a speed test at n = 50,000.

Non-convex benchmarks show the clearest advantage: GNG correctly captures the ring and spiral topology, the Laplacian eigengap identifies k = 2 or k = 3, and the oracle routes to TopoSOM which recovers the true partition via spectral embedding. KMeans++ achieves mean ARI 0.188 on these datasets; GRASP achieves 0.376.

Weird shapes are where GRASP shines brightest. The GNG mesh captures the rings and spirals correctly. The eigengap correctly says there are 2 or 3 groups. The oracle picks TopoSOM, and TopoSOM uses its spectral embedding to find the right answer. Across these datasets, KMeans++ averages ARI 0.188; GRASP averages 0.376 — roughly twice as accurate.

A-sets and S-sets (overlapping Gaussian clusters): The convex-bypass probe correctly activates on S4 (tight clusters, silhouette > 0.55) and routes to KMeans on A1 (ρ = 0.862). On A3 (heavily overlapping, k = 50), GRASP routes to KMeans++ and achieves ARI 0.216 vs KMeans++ at 0.188.

A-sets and S-sets are made of overlapping blob-shaped groups. GRASP correctly takes the shortcut on S4 (tight clusters, silhouette > 0.55) and hands A1 to KMeans (ρ = 0.862). On A3, which is messy with k = 50 heavily overlapping groups, GRASP still routes to KMeans++ and scores ARI 0.216, slightly better than running KMeans++ alone at 0.188.

Scalability: GNG, Laplacian, and eigendecomposition stages collectively incur O(m³) operations, entirely independent of n. The sole n-dependent step is the Nyström extension O(nmk); at n = 50,000 this completes in ~140ms. Standard SC requires O(n²d) at n = 10,000 this is 10¹² operations — GRASP's O(nm) is a 500× reduction at comparable quality.

How fast does it scale? The heavy math (GNG, Laplacian, eigendecomposition) costs O(m³) and doesn't grow with the dataset size n. Only one step actually touches every data point, and it costs O(nmk). At n = 50,000 the whole thing finishes in roughly 140ms. Standard spectral clustering would need O(n²d), which at just n = 10,000 is already 10¹² operations. GRASP's O(nm) is about 500× less work for similar quality.

GRASP's three main theoretical results establish conditions under which each component achieves its design goal.

Three theorems pin down exactly when each part of GRASP is guaranteed to do its job correctly.

Theorem 3 (Nyström error): For rank-m Nyström approximation K̃ with GNG landmarks, ‖K−K̃‖_F ≤ λ_m+1(K) √(n−m). The eigenvector error for the leading k components is O(λ_k+1/(λ_k−λ_k+1)), which diminishes as the spectral gap increases — exactly the regime where GRASP routes to TopSOM.

Theorem 3 (how close the shortcut gets to the real answer): With GNG landmarks, the Nyström approximation K̃ differs from the true kernel by at most ‖K−K̃‖_F ≤ λ_m+1(K) √(n−m). The error in the leading k directions is O(λ_k+1/(λ_k−λ_k+1)). The bigger the spectral gap, the smaller the error — and the big-gap case is exactly when GRASP routes to TopSOM.

Theorem 4 (Delaunay subgraph, Frötzke 2009): The GNG edge set is a subgraph of the Delaunay triangulation of the neuron positions. Hence any topologically separable cluster boundary present in the data's Delaunay structure is also represented in the GNG graph, bounding the Nyström approximation quality from below.

Theorem 4 (Delaunay subgraph, Frötzke 2009): The GNG mesh's edges are always part of the data's natural Delaunay structure — the canonical way to connect nearby points. So any boundary between groups that the Delaunay structure can see, the GNG mesh sees too. This sets a guaranteed floor on how good the Nyström approximation can be.

Proposition 5 (Oracle consistency): As n → ∞ with fixed cluster counts, the routing oracle selects the Bayes-optimal specialist with probability approaching 1. The oracle uses ARI estimate ρ, silhouette coefficients, and spectral advantage Δ — all of which converge by law of large numbers, and eigenvector stability of symmetric operators stabilises at a fixed label corresponding to the asymptotically optimal specialist.

Proposition 5 (the oracle picks right in the long run): As the dataset grows large (n → ∞) with a fixed number of groups, the oracle picks the truly best specialist with probability approaching 1. The signals it relies on — ρ, the silhouette scores, the spectral advantage Δ — all settle into stable values by the law of large numbers, and the eigenvectors lock onto the right specialist.

GRASP demonstrates that autonomous, parameter-free clustering is achievable through principled geometric diagnosis rather than heuristic ensemble voting. The three-principle architecture — topology prior, geometry-adaptive routing, selective spectral deployment — produces a system that is simultaneously faster than full spectral methods, more robust than density methods on complex topology, and more accurate than KMeans++ on non-convex structure.

GRASP shows you can build a clustering system that picks its own algorithm and tunes itself, by reading the geometry of the data rather than blindly stacking methods together. The three-part design — map first, route by shape, use heavy math only when needed — gives you something that is faster than full spectral methods, steadier than density methods on tangled shapes, and more accurate than KMeans++ on anything that isn't a clean blob.

The fast convex-bypass terminates 16 of 26 benchmarks in under 22ms. For the remaining 10, the full pipeline achieves state-of-the-art accuracy while processing 50,000 points within 140ms — scaling as O(nm) in n, independent of the O(m³) topology computation which depends only on the GNG size m.

The shortcut path finishes 16 of 26 benchmarks in under 22ms. For the other 10, the full pipeline reaches top-tier accuracy and still handles 50,000 points in 140ms. The cost grows as O(nm) with the dataset, and the heavier O(m³) topology step doesn't grow with n at all — only with the mesh size m.

Future directions include extending GRASP's routing oracle with learned diagnostic features via a small neural classifier trained on the topology signals, integrating SOM-TSK's multi-start seeding as a replacement for KMeans++ in the KMeans specialist, and evaluating GRASP on single-cell RNA-seq datasets where cluster topology is biologically meaningful and ground truth is available via cell-type markers.

Next steps: train a small neural classifier to read the topology signals and make the oracle even sharper, swap KMeans++ for SOM-TSK's multi-start seeding inside the KMeans specialist, and try GRASP on single-cell RNA-seq data — where the shape of the cluster carries real biological meaning and the answers can be checked against known cell-type markers.