EVINGCA: Adaptive Graph Clustering with Evolving Neighborhood Statistics

Abstract--Clustering algorithms often rely on restrictive assumptions: K-Means and Gaussian Mixtures presuppose convex, Gaussian-like clusters, while DBSCAN and HDBSCAN capture non-convexity but can be highly sensitive. I introduce EVINGCA (Evolving V ariance-Informed Nonparametric Graph Construction Algorithm), a density-variance based clustering algorithm that treats cluster formation as an adaptive, evolving process on a nearest-neighbor graph. EVINGCA expands rooted graphs via breadth-first search, guided by continuously updated local distance and shape statistics, replacing fixed density thresholds with local statistical feedback. With spatial indexing, EVINGCA features log-linear complexity in the average case and exhibits competitive performance against baselines across a variety of synthetic, real-world, low-d, and high-d datasets. Clustering is central to unsupervised learning, yet classical algorithms face significant structural and scalability limits. Centroid-based methods such as K-Means [19] assume convex, linearly separable clusters, while density-based approaches like DBSCAN [8] or HDBSCAN [4], [21] often struggle under heterogeneous densities and are highly sensitive in higher dimensionality. Graph-based and deep clustering methods offer stronger performance but often demand heavy tuning or incur prohibitive computational cost. I propose EVINGCA (Evolving V ariance-Informed Nonparametric Graph Construction Algorithm), an alternative clustering paradigm that models cluster formation as an adaptive, evolving process on a nearest-neighbor graph.