A High-Order Proximity-Incorporated Nonnegative Matrix Factorization-Based Community Detector
Zhigang Liu, Yugen Yi, Xin Luo
Abstract
Community describes the functional mechanism of an undirected network, making community detection a fundamental tool for graph representation learning-related applications like social circle discovery. To date, a Symmetric and Nonnegative Matrix Factorization (SNMF) model has been frequently adopted to address this issue owing to its high interpretability and scalability. However, most existing SNMF-based community detectors neglect the high-order proximity in an undirected network, thus suffering from accuracy loss caused by incomplete information. Motivated by this discovery, this paper proposes a <underline xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">H</u> igh- <underline xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">O</u> rder <underline xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">P</u> roximity-incorporated <underline xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">N</u> onnegative <underline xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">M</u> atrix <underline xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">F</u> actorization (HOP-NMF)-based community detector with the following three-fold ideas: a) adopting a weighted pointwise mutual information-based approach to measure the high-order proximity among nodes in a network; b) leveraging an iterative network enhancement scheme to encode the captured high-order proximity into the network to effectively enhance the its information; and c) implementing a capacity-enlarged and graph-regularized factorization algorithm for highly-accurate representation to the enhanced network. With the above design, an HOP-NMF model is able to achieve highly-accurate community detection results. Theoretical proof is rigorously conducted to validate its convergence ability. Extensively empirical studies on eight real networks from industrial applications demonstrate that an HOP-NMF-based community detector significantly outperforms sophisticated and state-of-the-art community detectors in detection accuracy.