# Clustering with Uniformity- and Neighbor-Based Random Geometric Graphs

arXiv: https://arxiv.org/abs/2501.06268 · HTML: https://mlsanity.com/paper/2501.06268/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 9 of its 73 references that are in the map.
- First posted on arXiv 9 Jan 2025.

## Builds on (most cited first, 9 of 9)

- [From Louvain to Leiden: guaranteeing well-connected communities](https://mlsanity.com/paper/1810.08473/) (2018)
- [Structural Deep Clustering Network](https://mlsanity.com/paper/2002.01633/) (2020)
- [A Robust Spectral Clustering Algorithm for Sub-Gaussian Mixture Models with Outliers](https://mlsanity.com/paper/1912.07546/) (2019)
- [A Rapid Review of Clustering Algorithms](https://mlsanity.com/paper/2401.07389/) (2024)
- [Classification of Imbalanced Data with a Geometric Digraph Family](https://mlsanity.com/paper/1904.04564/) (2019)
- [Bayesian community detection for networks with covariates](https://mlsanity.com/paper/2203.02090/) (2022)
- [Parameter Free Clustering with Cluster Catch Digraphs (Technical Report)](https://mlsanity.com/paper/1912.11926/) (2019)
- [Network-Adjusted Covariates for Community Detection](https://mlsanity.com/paper/2306.15616/) (2023)
- [Outlier Detection with Cluster Catch Digraphs](https://mlsanity.com/paper/2409.11596/) (2024)

## Abstract (arXiv)

We propose a graph-based clustering method based on Cluster Catch Digraphs (CCDs) that extends their applicability to moderate-dimensional data settings. Existing CCD variants, such as RK-CCDs, rely on spatial randomness tests based on Ripley's K function, which exhibit performance degradation as dimensionality increases. To address this limitation, we introduce a nearest-neighbor-distance (NND) based Monte Carlo spatial randomness test (MC-SRT) for determining covering radii, resulting in the proposed Uniformity- and Neighbor-based CCDs (UN-CCDs). The proposed method is designed for datasets of moderate size and dimension, particularly in settings with complex cluster geometry and uniformly distributed background noise. Through Monte Carlo simulations and experiments on benchmark datasets, we show that UN-CCDs provide stable and competitive performance relative to several established clustering methods within the evaluated regimes, while remaining largely parameter-free. We also discuss computational trade-offs and identify the practical regimes in which the method is most effective. -- Keywords: Graph-based clustering; Cluster catch digraphs; Moderate-dimensional data; the nearest neighbor distance; Spatial randomness test.