Community Detection with Graph Neural Network using Markov Stability
Shunjie Yuan, Chao Wang, Qi Jiang, Jianfeng Ma
Abstract
Community detection is a fundamental task in network analysis. With the recent development of deep learning, some community detection methods related to deep learning have been proposed. However, these methods still face limitations with respect to accuracy and runtime. In this paper, we propose a graph neural network (GNN) based overlapping community detection method CDMG from the perspective of optimizing Markov Stability, which is a statistical property of the Markov process quantifying the quality of a community partition. Specifically, we train a graph neural network to generate the node embedding defined as the community affiliation weight matrix that denotes the strength of nodes’ membership in communities while maximizing the Markov Stability. Then the community affiliation weight matrix is converted to a community affiliation matrix representing the community partition. Experiments on several real-world networks demonstrate the superiority of CDMG compared to other representative community detection algorithms. Additionally, since Markov Stability relies on a time parameter Markov Time, we observe that there exists a Markov Time threshold for a network. When using the Markov Time near the threshold, CDMG can produce a better community partition with much higher accuracy.