Matrix Factorization Framework for Community Detection under the Degree-Corrected Block Model

원문 초록

Community detection is a fundamental task in data analysis, and block models provide an approach for identifying diverse community structures. The degree-corrected block model (DCBM) is an established model that captures node degree heterogeneity. However, inference methods are computationally costly and sensitive to initialization, while cheaper alternatives, such as spectral or modularity-based approaches, may be less effective at recovering certain non-assortative structures. In this work, we show that DCBM inference can be reformulated as a constrained nonnegative matrix trifactorization problem. Leveraging this insight, we propose a scalable community detection method with a theoretically grounded initialization providing an initial partition for inference algorithms. Our approach is agnostic to network structure and applies to any graph representable by a DCBM. Experiments on synthetic and real-world benchmark networks show that our method achieves community recovery comparable to, and sometimes better than, that achieved by the DCBM inference methods, while being faster: it processes a graph with 100,000 nodes and 500,000 edges in about 30 seconds. Moreover, the initialization significantly improves solution quality. Overall, this work provides a scalable and robust framework for community detection and highlights the benefits of a matrix-factorization perspective for the DCBM.