A new method to build the adaptive k-nearest neighbors similarity graph matrix for spectral clustering

In spectral clustering (SC), the clustering result highly depends on the similarity graph matrix. The knearest neighbors graph is a popular method to build the similarity graph matrix with a sparse structure for better graph cutting. However, many current methods require that the parameter k is specified by the user, and specifying an appropriate k for an unknown data set is often a difficult task. In this paper, we propose a new method for building the adaptive k-nearest neighbors similarity graph (AKNNG). The AKNNG specifies different k values for different data points to obtain a better graph structure. Specifically, it sets a maximum number of the nearest neighbors kmaxand assigns a different k value (k 6 kmax) for each data point. The k value is adjusted automatically by cutting some weak connections from each data point according to the m powers transform of the similarity graph. The experimental results on Spiral, Multi-clusters, Yale and Coil20 datasets have shown that when setting kmax = 20, the new method has improved the clustering accuracies of these four datasets over 4%, 6%, 4%, 5%, respectively, in comparison with those by the existing methods. The new method can also reduce the sensitiveness of the number of nearest neighbors, and build the similarity graph with less time. (c) 2022 Elsevier B.V. All rights reserved.

Automated summary

This paper proposes a new method called adaptive k-nearest neighbors similarity graph (AKNNG) for constructing a better graph structure. By assigning different k values to different data points and automatically adjusting the k value based on the similarity graph, the AKNNG method improves clustering accuracies and reduces construction time.