Proximity Alert: Ipelets for Neighborhood Graphs and Clustering

Nearest neighborhood graphs are fundamental tools in data analysis on a point set $P$. A point $p\in P$ is connected to $q\in P$ when one is the nearest neighbor of the other. The $k$-nearest neighbor graph connects $p$ to $q$ when $q$ is among the $k$ nearest neighbors of $p$; the $k^{th}$-nearest neighbor graph connects $p$ to $q$ when $q$ is the $k^{th}$ nearest neighbor of $p$; mutual nearest neighbor graphs connect $p$ to $q$ when each is the other’s nearest neighbor; the $k$-mutual neighbor graph connects $p$ to $q$ when each is among the other’s $k$ nearest neighbors; the $k^{th}$-mutual neighbor graph connects $p$ to $q$ when each is exactly the other’s $k^{th}$ nearest neighbor; asymmetric nearest neighbor graphs connect $p$ to $q$ when exactly one is the other’s nearest neighbor; asymmetric $k$-nearest neighbor graphs connect $p$ to $q$ when exactly one has the other among their $k$ nearest neighbors; asymmetric $k^{th}$-nearest neighbor graphs connect $p$ to $q$ when exactly one has the other as their $k^{th}$ nearest neighbor; and furthest neighbor graphs connect $p$ to $q$ when $q$ is $p$’s furthest neighbor. See illustration in Figure 2.

A proximity graph is a graph in which points are connected when a region-based condition is satisfied, often in the context of network analysis. The Gabriel graph connects two points $p$ and $q$ when the disk defined by the diameter of $p$ and $q$ contains no other points [10]. A relative neighborhood graph connects two points $p$ and $q$ exactly when no point is closer to both $p$ and $q$ than they are to each other, or equivalently, no point is in the lune of $p$ and $q$ (intersection of the ball at $p$ with $q$ on its boundary and the ball at $q$ with $p$ on its boundary) [15]. A sphere of influence graph assigns to each point a disk with radius given as the distance to its nearest neighbor and connects points when their disks overlap [16]. An $\epsilon$-graph connects pairs of points if they lie within $\epsilon$ of each other. A Urquhart graph is the Delaunay triangulation with the longest edge of each triangle removed [17]. A Yao graph divides the plane into sectors by angle around points, and points are connected to their closest neighbor per sector [18]. See visuals in Figure 3.

Centroid-based clustering partitions a point set in space into clusters using a centroid-based method. The $k$-Means clustering partitions points into $k$ clusters, assigning points to its nearest centroid and recomputing the centroids iteratively until it is stable. The $k$-Means++ variant is similar, except it chooses initial centroids that are likely to be far apart to improve convergence. Unlike $k$-means, $k$-Medoids clustering uses preexisting points in the data as the centroids of the cluster [13]. Each iteration, a point replaces the medoid if it decreases the total intra-cluster distance. Illustrations of the methods can be seen in Figure 4.

Hierarchical clustering methods work by treating each point as a cluster and iteratively merging clusters until only a specified number remain. Single-linkage clustering defines the cluster distance between clusters as the minimum pairwise distance between their points, while complete-linkage clustering uses the maximum [7]. See Figure 5.

Density-based clustering partitions a point set into clusters based on how densely points are packed. DBSCAN groups points that are within a specified distance, $\epsilon$, of each other and have a minimum number of neighboring points (MinPts). Points meeting these criteria form clusters (distinguished by colors), while points that don’t are labeled as noise [6]. HDBSCAN, on the other hand, applies a hierarchical approach to density-based clustering [3]. It builds a mutual reachability graph and a minimum spanning tree to identify clusters at varying densities. Instead of relying on a fixed distance threshold like DBSCAN, HDBSCAN evaluates the stability of clusters across different scales. It then uses the Excess of Mass method to select stable clusters. Mean shift computes where each point would converge if moved towards the mean of its neighbors within the given bandwidth radius. Points whose trajectories converge on the same location form a cluster [5]. See Figure 6.