Fuzzy graph clustering

Spectral clustering is a group of graph-based clustering methods in which the columns of the scaled cluster indicator matrix can be obtained by stacking the eigenvectors of the Laplacian matrix corresponding to the top c smallest eigenvalues (c is the number of clus-ters). This leads to the possible existence of negative values in the scaled indicator matrix and therefore a post-processing step such as K means clustering or spectral rotation is nec-essary to get the discrete cluster assignments. Moreover, such obtained results lack of the interpretability for data points in the boundary area of multiple clusters. To simultaneously address both limitations, we propose a two-stage clustering model, termed FGC (fuzzy graph clustering) in this paper. In FGC, we first construct a doubly stochastic graph affinity matrix which is then approximated by the scaled product of the fuzzy cluster indicator matrices. The newly designed fuzzy cluster indicator matrix has two desirable properties of non-negativity and row normalization, which can bring us two benefits. On one hand, we can directly get the cluster assignment of a certain data point by checking the largest value in the corresponding row of the fuzzy cluster indicator matrix; and on the other hand, we can obtain the membership of each data point to different clusters. An iterative method under the alternative optimization framework is proposed to solve the objective function of FGC. We conduct data clustering experiments on both synthetic and benchmark data sets and the results demonstrate the effectiveness of our proposed FGC model. (c) 2021 Elsevier Inc. All rights reserved.

Automated summary

A two-stage clustering model called FGC (fuzzy graph clustering) is proposed to address the limitations of spectral clustering, by constructing a doubly stochastic graph affinity matrix and approximating it with the scaled product of fuzzy cluster indicator matrices. The newly designed fuzzy cluster indicator matrix has non-negativity and row normalization properties, allowing for direct cluster assignment and obtaining membership to different clusters for each data point.