Graph clustering by congruency approximation. Issue 6 (1st December 2015)

• Record Type: Journal Article
• Authors: Ren, Weiya; Li, Guohui; Tu, Dan
• Is Part Of: IET computer vision. Volume 9:Issue 6(2015)
• Page Start: 841
• Page End: 849
• Publication Date: 2015-12-01
• Subjects: graph theory -- pattern clustering -- computational complexity -- matrix decomposition; congruency approximation -- graph-based data structure -- solution vectors -- nonnegative discrete values -- NP-hard optimal solution -- spectral clustering -- nonnegative matrix factorisation -- congruent approximate graph clustering -- CAC -- ideal discrete solution -- real image benchmark datasets; Computer vision -- Periodicals; Pattern recognition systems -- Periodicals; 006.37
• DOI: 10.1049/iet-cvi.2014.0131
• Languages: English
• ISSNs: 1751-9632

Abstract

Abstract : 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.