Rank-r Discrete Matrix Factorization for Anchor Graph Clustering

Considering many graph clustering methods are with quadratic or cubic time complexity and need post-processing to obtain the discrete solution. Combining with the anchor graph, we study a novel graph clustering model called Rank-$r$ Discrete Matrix Factorization (DMF-RR), which is linear time complexity, and motivated by nonnegative matrix factorization (NMF). Instead of constraining the factor matrices of NMF to be nonnegative as many existed methods, we constrain them to indicator matrices. Thus, DMF-RR can obtain the discrete solution by directly solving the original problem without post-processing. Furthermore, considering the greater similarity between samples of the same category, an anchor graph is constructed as an input to capture essential clustering structure by utilizing the duality information between samples and anchors. Subsequently, an efficient and simple algorithm is proposed due to the nature of indicator matrices. Extensive experiments performed on synthetic and real-world datasets demonstrate the superiority of DMF-RR.

1 Introduction

The goal of clustering is to cluster data into different groups, where the data points in the same group have higher similarity, data points in different groups have lower similarity, which is a fundamental topic in unsupervised machine learning. Clustering methods have been successfully applied to various kinds of fields, such as image segmentation [1], [2], bioinformatics [3], [4]. Their various applications make a lot of researchers devote to study them. NMF [5], [6], spectral clustering [7], [8], subspace clustering [9] and multi-view clustering [10], [11] are branches of clustering methods [12], [13]. Among them, NMF has attracted increasing attention in recent years because of its mathematical elegance and encouraging empirical results.