A Relaxed Symmetric Non-Negative Matrix Factorization Approach for Community Discovery (Extended Abstract)

Abstract

Community discovery is a prominent issue in com-plex network analysis. Symmetric non-negative matrix factorization (SNMF) is frequently adopted to tackle this issue. The use of a single feature matrix can depict network symmetry, but it limits its ability to learn node representations. To break this limitation, we present a novel Relaxed Symmetric NMF (RSN) approach to boost an SNMF-based community detector. It works by 1) expanding the representational space and its degrees of freedom with multiple feature factors; 2) integrating the well-designed equality-constraints to make the model well-aware of the network’s intrinsic symmetry; 3) employing graph regularization to pre-serve the local geometric invariance of the network structure; and 4) separating constraints from decision variables for efficient optimization via the principle of alternating-direction-method of multi-pliers. RSN’s effectiveness is verified through empirical studies on six real social networks, show-casing superior precision in community discovery over existing models and baselines.