UN-CCDs Push Parameter-Free Clustering Past 20 Dimensions 18x Faster
A new graph-based clustering method swaps Ripley's K function for nearest-neighbor distances, keeping cluster catch digraphs usable up to 20 dimensions.
Takeaways
- UN-CCDs extend cluster catch digraphs to moderate dimensions by swapping Ripley's K for a nearest-neighbor-distance Monte Carlo test.
- Previous CCD variants degraded sharply above 5 dimensions; UN-CCDs remain competitive up to about d=20.
- At n=500, d=5, UN-CCDs finish in 4.38 minutes versus 78.6 for RK-CCDs and 986 for KS-CCDs.
- Robust to 3% to 20% uniform background noise with no separate outlier-removal step required.
- Complexity is O(n³); not suitable for large-scale, streaming, or very high-dimensional data.
- Code and benchmarks are open source on GitHub.
Cluster catch digraphs (CCDs) are a family of graph-based clustering methods that build a covering ball around each point, then keep only a small set of balls that dominate the data. They handle irregular cluster shapes and are almost parameter-free, but they share a stubborn ceiling: existing variants break down once dimensions exceed 5. A new arXiv paper, Clustering with Uniformity- and Neighbor-Based Random Geometric Graphs, introduces UN-CCDs, which replace the fragile piece of the pipeline with a nearest-neighbor-distance test and push the working range up to roughly 20 dimensions.
Where the old method cracked
The previous state of the art was RK-CCDs, which set each covering ball's radius using a Monte Carlo test based on Ripley's K function, a spatial statistic that measures whether points are clustered, dispersed, or randomly scattered. Two problems bite as dimensions grow. The initial points in the Monte Carlo test are always ball centers rather than random samples, biasing the test. And the confidence band for K(t) is built on fixed distance values, which becomes inappropriate as pairwise distances stretch out in high-dimensional space. The authors' earlier outlier-detection work already showed that RK-CCDs produce covering balls that are too small in moderate dimensions, leading to high false-positive rates above d=10.