Low-rank Sparse Decomposition of Graph Adjacency Matrices for Extracting Clean Clusters

In this paper, we propose a refining method of graphs having clusters. Clean graphs, i.e., those represent relationships between data clearly, are important for various applications. There have been many graph construction or learning methods, however, graphs obtained from the conventional approaches are not specifically designed to yield clean graphs that have dense connections within clusters whereas sparse ones between them. In this paper, we focus on making dense edges denser and sparse edges sparser for refining graphs. In order to make it possible, we propose a low-rank sparse decomposition of an adjacency matrix. We apply the methodology of robust PCA to the adjacency matrix for the decomposition. To obtain a valid adjacency matrix, we further formulate it in a form applicable to ADMM with proper constraints. In the experiments using synthetic data, we validate that the proposed method effectively refines graphs.