Graph clustering by congruency approximation

The authors consider the general problem of graph clustering. Graph clustering manipulates the graph-based data structure and the entries of the solution vectors are only allowed to take non-negative discrete values. Finding the optimal solution is NP-hard, so relaxations are usually considered. Spectral clustering retains the orthogonality rigorously but ignores the non-negativity and discreteness of the solution. Sym non-negative matrix factorisation can retain the non-negativity rigorously but it is hard to reach the orthogonality. In this study, they proposed a novel method named congruent approximate graph clustering (CAC), which can retain the non-negativity rigorously and can reach the orthogonality properly by congruency approximation. Furthermore, the solution obtained by CAC is sparse, which is approximate with the ideal discrete solution. Experimental results on several real image benchmark datasets indicate that CAC achieves encouraging results compared with state-of-the-art methods.