pith. sign in

arxiv: 2601.06262 · v2 · submitted 2026-01-09 · 💻 cs.SI · math.OC· stat.ML

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

Alexandra Dache , Arnaud Vandaele , Nicolas Gillis This is my paper

Pith reviewed 2026-05-16 15:47 UTC · model grok-4.3

classification 💻 cs.SI math.OCstat.ML
keywords community detectiondegree-corrected block modelnonnegative matrix factorizationgraph clusteringnetwork inferencescalable algorithms
0
0 comments X

The pith

DCBM inference for community detection reduces to a constrained nonnegative matrix factorization problem.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper shows that maximum-likelihood inference under the degree-corrected block model is equivalent to solving a constrained nonnegative matrix factorization problem. This reformulation yields a scalable community detection method that works for arbitrary network structures representable by the DCBM, unlike spectral or modularity approaches limited to assortative cases. The authors also derive a theoretically grounded initialization from the matrix factorization view that improves convergence and quality for standard inference algorithms. Experiments indicate the approach matches full DCBM inference quality on synthetic and real networks while running much faster on large graphs.

Core claim

Inference under the degree-corrected block model can be reformulated as a constrained nonnegative matrix factorization problem. This equivalence produces a new community detection algorithm and an initialization strategy that supplies a strong starting estimate of communities, reducing iterations and improving solution quality across tested inference methods.

What carries the argument

The constrained nonnegative matrix factorization problem whose solution encodes the degree-corrected block model log-likelihood maximization.

If this is right

  • The method detects communities in networks with any structure representable by a DCBM, including disassortative and other non-assortative cases.
  • It scales to graphs with 100,000 nodes and 1,000,000 edges in roughly four minutes.
  • The initialization strategy reduces the number of iterations required by existing DCBM inference algorithms while raising final solution quality.
  • The approach remains agnostic to specific community structures as long as they fit the degree-corrected block model.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Techniques developed for nonnegative matrix factorization in other domains could be imported to further accelerate or regularize community detection under this model.
  • The matrix factorization perspective might naturally extend to overlapping or soft community assignments by relaxing the constraints.
  • Because the reformulation is parameter-light, it could serve as a fast baseline for comparing new inference methods on large real-world networks.

Load-bearing premise

The communities recovered by solving the constrained nonnegative matrix factorization are exactly the same as those from maximum-likelihood inference under the degree-corrected block model.

What would settle it

Generate a synthetic network from a known degree-corrected block model with planted communities, run both the proposed matrix factorization method and a standard DCBM inference algorithm, and check whether the recovered node assignments match with high accuracy.

Figures

Figures reproduced from arXiv: 2601.06262 by Alexandra Dache, Arnaud Vandaele, Nicolas Gillis.

Figure 1
Figure 1. Figure 1: FIG. 1: Examples of structures detectable by an SBM with 3 blocks, illustrated with the matrix [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: FIG. 2: Geometric illustration of the separability [PITH_FULL_IMAGE:figures/full_fig_p006_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: FIG. 3: Examples of LFR benchmark networks with 1 [PITH_FULL_IMAGE:figures/full_fig_p007_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: FIG. 4: Average AMI and average runtime over 10 LFR [PITH_FULL_IMAGE:figures/full_fig_p008_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: FIG. 5: Average AMI and runtime over 10 LFR graphs [PITH_FULL_IMAGE:figures/full_fig_p009_5.png] view at source ↗
Figure 7
Figure 7. Figure 7: FIG. 7: Partition of the political blog network found [PITH_FULL_IMAGE:figures/full_fig_p010_7.png] view at source ↗
Figure 9
Figure 9. Figure 9: FIG. 9: Heat-map of matrix [PITH_FULL_IMAGE:figures/full_fig_p011_9.png] view at source ↗
Figure 10
Figure 10. Figure 10: Table III reports the average NMI, the number [PITH_FULL_IMAGE:figures/full_fig_p012_10.png] view at source ↗
Figure 10
Figure 10. Figure 10: FIG. 10: The [PITH_FULL_IMAGE:figures/full_fig_p013_10.png] view at source ↗
read the original abstract

Community detection is a fundamental task in data analysis, and block models provide an approach for identifying a wide variety of community structures while offering high interpretability. The degree-corrected block model (DCBM) is an established model that accounts for the heterogeneity of node degrees. However, inference methods are computationally costly and highly sensitive to initialization, while cheaper alternatives, such as spectral or modularity-based approaches, are restricted to detecting specific structures, typically assortative. In this work, we show that DCBM inference can be reformulated as a constrained nonnegative matrix factorization problem. Leveraging this insight, we propose a novel method for community detection and a theoretically well-grounded initialization strategy that provides an initial estimate of communities for inference algorithms. Our approach is agnostic to any specific network structure and applies to graphs with any structure representable by a DCBM. Experiments on synthetic and real benchmark networks show that our method detects communities comparable to those found by DCBM inference while being faster; for instance, it processes a graph with 100,000 nodes and 1,000,000 edges in approximately 4 minutes. Moreover, the proposed initialization strategy significantly improves solution quality and reduces the number of iterations required by all tested inference algorithms. Overall, this work provides a scalable and robust framework for community detection and highlights the benefits of a matrix-factorization perspective for the DCBM.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper claims that inference under the degree-corrected block model (DCBM) can be exactly reformulated as a constrained nonnegative matrix factorization (NMF) problem. It proposes a novel community detection algorithm based on this reformulation together with a theoretically grounded initialization strategy. Experiments on synthetic and real networks (including a 100k-node graph) report that the method recovers communities comparable to standard DCBM maximum-likelihood inference while running substantially faster, and that the initialization improves convergence of existing DCBM algorithms.

Significance. If the claimed equivalence to DCBM MLE holds without relaxation or bias, the work supplies a scalable, structure-agnostic alternative to expensive likelihood-based inference and a broadly useful initialization heuristic. The matrix-factorization perspective could also open new theoretical connections between NMF and block-model estimation.

major comments (2)
  1. [Section 3 (reformulation)] The central reformulation (claimed in the abstract and derived in the main text) is presented as preserving the DCBM log-likelihood including degree-correction parameters, yet no explicit derivation or proof is given that the NMF objective and feasible set share identical global optima with the original MLE; without this, recovered partitions may differ even under correct model specification.
  2. [Section 5] Section 5 (experiments) reports comparable performance on benchmarks but supplies neither recovery-error bounds nor an analysis showing that the NMF relaxation introduces no systematic bias relative to exact DCBM MLE; the timing result for the 100k-node graph is given without variance or comparison to optimized likelihood baselines.
minor comments (2)
  1. [Section 2] Notation for the degree-correction parameters and the precise NMF constraints should be introduced earlier and used consistently to aid readability.
  2. [Section 4] The initialization strategy is described as 'theoretically well-grounded' but the supporting argument is only sketched; a short formal statement would strengthen the claim.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive feedback. We address the major comments below and have revised the manuscript to strengthen the presentation of the reformulation and the experimental analysis.

read point-by-point responses

  1. Referee: [Section 3 (reformulation)] The central reformulation (claimed in the abstract and derived in the main text) is presented as preserving the DCBM log-likelihood including degree-correction parameters, yet no explicit derivation or proof is given that the NMF objective and feasible set share identical global optima with the original MLE; without this, recovered partitions may differ even under correct model specification.

    Authors: Section 3 derives the equivalence by rewriting the DCBM log-likelihood (including degree-correction parameters) directly as the constrained NMF objective with the stated feasible set. To address the concern explicitly, we will add a formal proposition and its proof in the revised manuscript showing that the two problems share identical global optima under the DCBM assumptions, confirming that the reformulation introduces no relaxation. revision: yes

  2. Referee: [Section 5] Section 5 (experiments) reports comparable performance on benchmarks but supplies neither recovery-error bounds nor an analysis showing that the NMF relaxation introduces no systematic bias relative to exact DCBM MLE; the timing result for the 100k-node graph is given without variance or comparison to optimized likelihood baselines.

    Authors: Because the reformulation is exact (not a relaxation), no systematic bias relative to DCBM MLE is introduced by construction; we will add a short analysis subsection in the revised Section 5 that demonstrates this empirically on synthetic data. We will also report timing results with standard deviations over repeated runs and include direct comparisons against optimized likelihood baselines. revision: yes

Circularity Check

0 steps flagged

No circularity: DCBM-to-NMF reformulation derived from likelihood, not by construction or self-citation

full rationale

The paper derives the equivalence between DCBM maximum-likelihood inference and constrained nonnegative matrix factorization directly from the model definition, presenting the reformulation as a mathematical insight that enables a new algorithm and initialization. No equations reduce a prediction to a fitted input by construction, no load-bearing self-citations justify uniqueness or ansatzes, and the central claim does not rename a known result or smuggle assumptions via prior author work. The provided abstract and context show an independent derivation chain whose validity can be checked against the DCBM log-likelihood without tautology. This matches the expected non-finding for a reformulation paper whose core step is not self-referential.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on the assumption that the DCBM is an appropriate generative model for the networks of interest and that the constrained NMF exactly captures the inference objective.

axioms (1)
  • domain assumption The degree-corrected block model accurately describes the observed network structure
    Invoked as the basis for the reformulation and experiments

pith-pipeline@v0.9.0 · 5547 in / 1101 out tokens · 26257 ms · 2026-05-16T15:47:49.360763+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

43 extracted references · 43 canonical work pages · 1 internal anchor

  1. [1]

    The resulting networks have community sizes between 20 and 100, leading to 16 to 24 commu- nities per network

    For each value of the mixing parameterµbetween 0 and 0.6, we generate 10 test networks using the original code from [31]. The resulting networks have community sizes between 20 and 100, leading to 16 to 24 commu- nities per network. Fig. 3 illustrates three examples of networks generated with these parameters, for different values ofµ. Each method is run ...

    work page

  2. [2]

    We com- pare KN, KL-EM, and FROST with both random and SVCA initializations

    Scalability To further illustrate the scalability of the methods, we perform an additional experiment to examine how run- time and performance vary with graph size. We com- pare KN, KL-EM, and FROST with both random and SVCA initializations. MHA is not included in this com- parison, as it was significantly slower in the previous test. For each network siz...

    work page 2005

  3. [3]

    This dataset docu- ments the participation of women in social events held in a southern town in the United States

    Southern Women Dataset The Southern women dataset [36] is a widely used benchmark for evaluating community detection methods on bipartite networks [34, 35, 37]. This dataset docu- ments the participation of women in social events held in a southern town in the United States. The bipartite net- work is composed of 32 nodes, 18 for women and 14 for events. ...

    work page

  4. [4]

    This network captures the con- nections between 136 directors and 108 large companies

    Scotland Corporate Interlock We now consider the Scotland corporate interlock net- work [38], which is commonly used as a benchmark for bipartite graphs [37]. This network captures the con- nections between 136 directors and 108 large companies. Since the network is disconnected, we focus solely on its largest connected component, which consists of 131 di...

    work page

  5. [5]

    Malaria dataset We now consider a larger bipartite network. In the Malaria network, presented in [35], the nodes repre- sent the malaria parasite (P.falciparum)vargenes (297 nodes) and their constituent substrings (806 nodes), with edges connecting each substring to all genes in which it appears. For both OtrisymNMF and the DCBM, the best partition into t...

    work page

  6. [6]

    Holland, K

    P. Holland, K. B. Laskey, and S. Leinhardt, Stochastic blockmodels: First steps, Social Networks5, 109 (1983)

    work page 1983

  7. [7]

    Fortunato, Community detection in graphs, Physics reports486, 75 (2010)

    S. Fortunato, Community detection in graphs, Physics reports486, 75 (2010)

    work page 2010

  8. [8]

    Abbe, Community detection and stochastic block models: recent developments, J

    E. Abbe, Community detection and stochastic block models: recent developments, J. Mach. Learn. Res.18, 1 (2018)

    work page 2018

  9. [9]

    Decelle, F

    A. Decelle, F. Krzakala, C. Moore, and L. Zdeborov´ a, Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications, Phys- ical Review E—Statistical, Nonlinear, and Soft Matter Physics84, 066106 (2011)

    work page 2011

  10. [10]

    Karrer and M

    B. Karrer and M. E. J. Newman, Stochastic blockmodels and community structure in networks, Phys. Rev. E83, 016107 (2011)

    work page 2011

  11. [11]

    X. Yan, C. Shalizi, J. E. Jensen, F. Krzakala, C. Moore, L. Zdeborov´ a, P. Zhang, and Y. Zhu, Model selection for degree-corrected block models, J. Stat. Mech.: Theory Exp.2014(5), P05007

    work page 2014

  12. [12]

    Jin, Fast community detection by score, The Annals of Statistics43, 57 (2015)

    J. Jin, Fast community detection by score, The Annals of Statistics43, 57 (2015)

    work page 2015

  13. [13]

    C. Gao, Z. Ma, A. Y. Zhang, and H. H. Zhou, Community detection in degree-corrected block models, The Annals of Statistics46, 2153 (2018)

    work page 2018

  14. [14]

    Y. Chen, X. Li, and J. Xu, Convexified modularity max- imization for degree-corrected stochastic block models, The Annals of Statistics46, 1573 (2018)

    work page 2018

  15. [15]

    Gillis,Nonnegative Matrix Factorization(SIAM, Philadelphia, 2020)

    N. Gillis,Nonnegative Matrix Factorization(SIAM, Philadelphia, 2020). 14

    work page 2020

  16. [16]

    Zhang, Y

    Z.-Y. Zhang, Y. Gai, Y.-F. Wang, H.-M. Cheng, and X. Liu, On equivalence of likelihood maximization of stochastic block model and constrained nonnegative ma- trix factorization, Physica A: Statistical Mechanics and its Applications503, 687 (2018)

    work page 2018

  17. [17]

    C. Ding, T. Li, W. Peng, and H. Park, Orthogonal non- negative matrix t-factorizations for clustering, inProceed- ings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining(2006) pp. 126– 135

    work page 2006

  18. [18]

    Orthogonal symmetric non-negative matrix factorization under the stochastic block model

    S. Paul and Y. Chen, Orthogonal symmetric non- negative matrix factorization under the stochastic block model, arXiv preprint arXiv:1605.05349 (2016)

    work page internal anchor Pith review Pith/arXiv arXiv 2016

  19. [19]

    Dache, A

    A. Dache, A. Vandaele, and N. Gillis, Orthogonal sym- metric nonnegative matrix tri-factorization, inInterna- tional Workshop on MLSP(IEEE, 2024)

    work page 2024

  20. [20]

    D. D. Lee and H. S. Seung, Learning the parts of objects by non-negative matrix factorization, Nature401, 788 (1999)

    work page 1999

  21. [21]

    Arora, R

    S. Arora, R. Ge, R. Kannan, and A. Moitra, Comput- ing a nonnegative matrix factorization–provably, inACM Symposium on Theory of Computing(2012)

    work page 2012

  22. [22]

    Bhattacharyya and R

    C. Bhattacharyya and R. Kannan, Finding a latent k– simplex ino ∗(k·nnz(data)) time via subset smoothing, in Proceedings of the Fourteenth Annual ACM-SIAM Sym- posium on Discrete Algorithms(SIAM, 2020) pp. 122– 140

    work page 2020

  23. [23]

    Bhattacharyya, R

    C. Bhattacharyya, R. Kannan, and A. Kumar, Finding kin latentk−polytope, inInternational Conference on Machine Learning(2021) pp. 894–903

    work page 2021

  24. [24]

    Bakshi, C

    A. Bakshi, C. Bhattacharyya, R. Kannan, D. P. Woodruff, and S. Zhou, Learning a latent simplex in input sparsity time, inProceedings of the International Conference on Learning Representations (ICLR)(2021)

    work page 2021

  25. [25]

    Nadisic, N

    N. Nadisic, N. Gillis, and C. Kervazo, Smoothed separa- ble nonnegative matrix factorization, Linear Algebra and its Applications676, 174 (2023)

    work page 2023

  26. [26]

    J. M. Nascimento and J. M. Dias, Vertex component analysis: A fast algorithm to unmix hyperspectral data, IEEE transactions on Geoscience and Remote Sensing 43, 898 (2005)

    work page 2005

  27. [27]

    Pompili, N

    F. Pompili, N. Gillis, P. Absil, and F. Glineur, Two al- gorithms for orthogonal nonnegative matrix factorization with application to clustering, Neurocomputing141, 15 (2014)

    work page 2014

  28. [28]

    J. Jin, Z. T. Ke, and S. Luo, Mixed membership estima- tion for social networks, Journal of Econometrics239, 105369 (2024)

    work page 2024

  29. [29]

    Panov, K

    M. Panov, K. Slavnov, and R. Ushakov, Consistent es- timation of mixed memberships with successive projec- tions, inInternational Conference on Complex Networks and their Applications(Springer, 2017) pp. 53–64

    work page 2017

  30. [30]

    Qing, Discovering overlapping communities in multi- layer directed networks, Chaos, Solitons & Fractals194, 116175 (2025)

    H. Qing, Discovering overlapping communities in multi- layer directed networks, Chaos, Solitons & Fractals194, 116175 (2025)

    work page 2025

  31. [31]

    Arora, R

    S. Arora, R. Ge, Y. Halpern, D. Mimno, A. Moitra, D. Sontag, Y. Wu, and M. Zhu, A practical algorithm for topic modeling with provable guarantees, inInterna- tional conference on machine learning(PMLR, 2013) pp. 280–288

    work page 2013

  32. [32]

    N. X. Vinh, J. Epps, and J. Bailey, Information theoretic measures for clusterings comparison: Variants, proper- ties, normalization and correction for chance, Journal of Machine Learning Research11, 2837 (2010)

    work page 2010

  33. [33]

    B. W. Kernighan and S. Lin, An efficient heuristic proce- dure for partitioning graphs, The Bell System Technical Journal49, 291 (1970)

    work page 1970

  34. [34]

    Funke and T

    T. Funke and T. Becker, Stochastic block models: A com- parison of variants and inference methods, PLOS ONE 14, 1 (2019)

    work page 2019

  35. [35]

    T. P. Peixoto, Efficient monte carlo and greedy heuris- tic for the inference of stochastic block models, Physical Review E89, 012804 (2014)

    work page 2014

  36. [36]

    Lancichinetti, S

    A. Lancichinetti, S. Fortunato, and F. Radicchi, Bench- mark graphs for testing community detection algorithms, Physical Review E78, 046110 (2008)

    work page 2008

  37. [37]

    W. W. Zachary, An information flow model for conflict and fission in small groups, Journal of anthropological research33, 452 (1977)

    work page 1977

  38. [38]

    L. A. Adamic and N. Glance, The political blogosphere and the 2004 us election: divided they blog, inProceed- ings of the 3rd international workshop on Link discovery (2005) pp. 36–43

    work page 2004

  39. [39]

    Alzahrani and K

    T. Alzahrani and K. Horadam, Community detection in bipartite networks: Algorithms and case studies, Under- standing Complex Systems73, 25 (2016)

    work page 2016

  40. [40]

    D. B. Larremore, A. Clauset, and A. Z. Jacobs, Effi- ciently inferring community structure in bipartite net- works, Phys. Rev. E90, 012805 (2014)

    work page 2014

  41. [41]

    Davis, B

    A. Davis, B. B. Gardner, and M. R. Gardner,Deep South: A social anthropological study of caste and class(Univ of South Carolina Press, 2009)

    work page 2009

  42. [42]

    M. J. Barber, Modularity and community detection in bipartite networks, Physical Review E—Statistical, Non- linear, and Soft Matter Physics76, 066102 (2007)

    work page 2007

  43. [43]

    Scott and M

    J. Scott and M. Hughes,The anatomy of Scottish cap- ital: Scottish companies and Scottish capital, 1900-1979 (Routledge, 2021)

    work page 1900