Optimal construction of k-nearest neighbor graphs for identifying noisy clusters

Abstract

We study clustering algorithms based on neighborhood graphs on a random sample of data points. The question we ask is how such a graph should be constructed in order to obtain optimal clustering results. Which type of neighborhood graph should one choose, mutual k-nearest neighbor or symmetric k-nearest neighbor? What is the optimal parameter k? In our setting, clusters are defined as connected components of the t-level set of the underlying probability distribution. Clusters are said to be identified in the neighborhood graph if connected components in the graph correspond to the true underlying clusters. Using techniques from random geometric graph theory, we prove bounds on the probability that clusters are identified successfully, both in a noise-free and in a noisy setting. Those bounds lead to several conclusions. First, k has to be chosen surprisingly high (rather of the order n than of the order log n) to maximize the probability of cluster identification. Secondly, the major difference between the mutual and the symmetric k-nearest neighbor graph occurs when one attempts to detect the most significant cluster only.

31 pages, 2 figures

Cited by in corpus (23)

• Spectral Clustering Based on Local PCA
• Spectral clustering based on local linear approximations
• Fully adaptive density-based clustering
• Fast $k$-NNG construction with GPU-based quick multi-select
• Pruning nearest neighbor cluster trees
• Improved spectral convergence rates for graph Laplacians on epsilon-graphs and k-NN graphs
• Recursive nearest agglomeration (ReNA): fast clustering for approximation of structured signals
• Density Level Set Estimation on Manifolds with DBSCAN
• DeBaCl: A Python Package for Interactive DEnsity-BAsed CLustering
• Parallel Strong Connectivity Based on Faster Reachability
• Color graph based wavelet transform with perceptual information
• How the result of graph clustering methods depends on the construction of the graph
• Modal-set estimation with an application to clustering
• Mapping Topographic Structure in White Matter Pathways with Level Set Trees
• Adaptive Clustering Using Kernel Density Estimators
• Local Two-Sample Testing over Graphs and Point-Clouds by Random-Walk Distributions
• Clustering with UMAP: Why and How Connectivity Matters
• Consistent procedures for cluster tree estimation and pruning
• Behavior of Graph Laplacians on Manifolds with Boundary
• Clustering of Big Data with Mixed Features
• Motion planning using shortest path
• Streaming Graph Partitioning in the Planted Partition Model
• Density-based Clustering with Best-scored Random Forest