Benefits of Hypergraphs for Density-Based Clustering

Many of clustering algorithms are based on density estimates in <tex>${\mathbb{R}^{d}}$</tex>. Building geometric graphs on the dataset <tex>$\mathcal{X}$</tex> is an elegant way of doing this. In fact, the connected components of a geometric graph match exactly with the high-density clusters of the 1-Nearest Neighbor density estimator. In this paper, We show that the natural way to generalize geometric graphs is to use hypergraphs with a more restrictive notion of connected component called <tex>$K$</tex>-Polyhedron. Herein, we prove that <tex>$K$</tex>-polyhedra correspond to high-density clusters of K-Nearest Neighbors density estimator. Furthermore, the percolation phenomenon is omnipresent behind the family of clustering algorithms we look at in this paper.