Learning by Unsupervised Nonlinear Diffusion

Abstract

This paper proposes and analyzes a novel clustering algorithm that combines graph-based diffusion geometry with techniques based on density and mode estimation. The proposed method is suitable for data generated from mixtures of distributions with densities that are both multimodal and have nonlinear shapes. A crucial aspect of this algorithm is the use of time of a data-adapted diffusion process as a scale parameter that is different from the local spatial scale parameter used in many clustering algorithms. We prove estimates for the behavior of diffusion distances with respect to this time parameter under a flexible nonparametric data model, identifying a range of times in which the mesoscopic equilibria of the underlying process are revealed, corresponding to a gap between within-cluster and between-cluster diffusion distances. These structures can be missed by the top eigenvectors of the graph Laplacian, commonly used in spectral clustering. This analysis is leveraged to prove sufficient conditions guaranteeing the accuracy of the proposed \emph{learning by unsupervised nonlinear diffusion (LUND)} procedure. We implement LUND and confirm its theoretical properties on illustrative datasets, demonstrating the theoretical and empirical advantages over both spectral clustering and density-based clustering techniques.

arXiv comment40 Pages, 17 Figures

References in corpus (10)

• Consistency of spectral clustering
• Statistical inference on random dot product graphs: a survey
• Spectral Clustering Based on Local PCA
• Spectral clustering based on local linear approximations
• Data spectroscopy: Eigenspaces of convolution operators and clustering
• The geometry of kernelized spectral clustering
• Path-Based Spectral Clustering: Guarantees, Robustness to Outliers, and Fast Algorithms
• Clusters and water flows: a novel approach to modal clustering through Morse theory
• Computational Feasibility of Clustering under Clusterability Assumptions
• The exact constant for the ${\ell }_1-{\ell }_2$ norm inequality

Cited by in corpus (4)

• Spectral-Spatial Diffusion Geometry for Hyperspectral Image Clustering
• Unsupervised Diffusion and Volume Maximization-Based Clustering of Hyperspectral Images
• DISCERN: Diversity-based Selection of Centroids for k-Estimation and Rapid Non-stochastic Clustering
• Diffusion State Distances: Multitemporal Analysis, Fast Algorithms, and Applications to Biological Networks