Generalization of single-linkage with higher-order interactions

This article analyzes and generalizes the classical Single-Linkage clustering algorithm, which performs hierarchical clustering by iteratively merging the two closest clusters. Single-Linkage and its robust version are still widely used in modern clustering techniques like the state-of-the-art HDBSCAN. Single-Linkage can be understood from three perspectives: (i) it conducts persistent analysis on geometric graphs; (ii) it identifies high-density clusters using the 1-Nearest Neighbor density estimator; and (iii) it is implemented via the minimum spanning tree of the data. This paper extends Single-Linkage to higher-order interactions by replacing geometric graphs with hypergraphs and introducing a stricter notion of connected components, named K-polyhedra. Specifically, for $$K=2$$ , our method employs “triangle connectivity”. We prove that K-polyhedra correspond to high-density clusters of the K-Nearest Neighbors density estimator. In practice, this approach is implemented by identifying a minimum K-tree. The paper also introduces original geometric optimizations for efficiently computing the 2-generalization of Single-Linkage in low-dimensional Euclidean spaces. Experimental results demonstrate that even when $$K=2$$ is used, the proposed method already surpasses the state-of-the-art clustering methods on synthetic and real-world datasets.