Normalized Likelihood Criteria for Model Selection in the Stochastic Block Model

Andressa Cerqueira; Felipe Baptist\~ao

arxiv: 2604.10205 · v1 · submitted 2026-04-11 · 🧮 math.ST · stat.TH

Normalized Likelihood Criteria for Model Selection in the Stochastic Block Model

Andressa Cerqueira , Felipe Baptist\~ao This is my paper

Pith reviewed 2026-05-10 15:43 UTC · model grok-4.3

classification 🧮 math.ST stat.TH

keywords stochastic block modelcommunity detectionmodel selectionnormalized maximum likelihoodconsistencysparse networkspenalized estimators

0 comments

The pith

Normalized maximum complete likelihood and decomposed normalized maximum likelihood estimators are strongly consistent for selecting the number of communities in sparse stochastic block models when average node degree diverges.

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

The paper examines penalized estimators based on normalized likelihood criteria to determine the number of communities in networks generated by the stochastic block model. It establishes that the normalized maximum likelihood approach is consistent with a logarithmic penalty but computationally intractable. To provide a practical alternative, the authors introduce the normalized maximum complete likelihood and the decomposed normalized maximum likelihood criteria. The latter has an explicit form that can be computed in cubic time relative to the number of nodes. They prove strong consistency of both the NMCL and DNML estimators specifically for sparse networks in which the average degree grows unbounded as the network enlarges.

Core claim

A penalized estimator derived from the Normalized Maximum Likelihood is strongly consistent with a logarithmic penalty term, although its computation is intractable. The Normalized Maximum Complete Likelihood and the Decomposed Normalized Maximum Likelihood admit explicit formulations, with the DNML having cubic computational complexity in the number of nodes. The NMCL- and DNML-based estimators are strongly consistent for sparse networks in which the average node degree diverges with the network size.

What carries the argument

The Normalized Maximum Complete Likelihood (NMCL) and Decomposed Normalized Maximum Likelihood (DNML) criteria, which serve as penalized likelihood functions for selecting the number of communities under the stochastic block model.

If this is right

The DNML estimator provides a computationally feasible method with cubic complexity that recovers the true number of communities under the stated sparsity condition.
Both estimators perform competitively with existing methods, especially when community sizes are unbalanced.
Strong consistency guarantees apply in the asymptotic regime of growing network size and diverging average degree.
These criteria extend the use of normalized likelihood penalties to the stochastic block model setting for model selection.

Where Pith is reading between the lines

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

The cubic complexity of DNML may limit application to extremely large networks, suggesting room for faster approximations that preserve consistency.
Real-world networks often violate the exact SBM assumption or the degree-divergence condition, so empirical performance may degrade outside the theoretical regime.
Similar normalized-likelihood penalties could be adapted to other latent-block or community models if their likelihood structures allow analogous decomposition.

Load-bearing premise

The observed network is generated exactly according to a stochastic block model in which the average node degree diverges to infinity with the number of nodes.

What would settle it

Simulate networks from a stochastic block model with fixed average degree that does not grow and verify whether the NMCL or DNML estimator selects an incorrect number of communities with probability bounded away from zero as the network size tends to infinity.

Figures

Figures reproduced from arXiv: 2604.10205 by Andressa Cerqueira, Felipe Baptist\~ao.

**Figure 2.** Figure 2: Average estimated number of communities for each method as the number of vertices [PITH_FULL_IMAGE:figures/full_fig_p013_2.png] view at source ↗

**Figure 3.** Figure 3: Mean estimated k by the methods varying the probability b of the network fixing n = 200, k0 = 5, a = 0.8 for balanced and a = 0.9 unbalanced networks. In order to study the impact of sparsity on the performance of the algorithm, we consider a network with k0 = 5, n = 300, a = 5, and b = 1 [PITH_FULL_IMAGE:figures/full_fig_p013_3.png] view at source ↗

**Figure 4.** Figure 4: Mean estimated k by the methods varying ρn fixing a = 5, b = 1 and k0 = 5. Finally, we compare the performance of the different versions of the DNML estimator under distinct conditions. Specifically, we consider: (i) the DNML defined in (3.4) without the penalty term; (ii) the penalized DNML defined in (3.6), with the penalty term given in (3.7); and (iii) a modified version of the penalized DNML that excl… view at source ↗

**Figure 5.** Figure 5: Comparison of the different DNML-based estimators, varying the number of nodes [PITH_FULL_IMAGE:figures/full_fig_p015_5.png] view at source ↗

read the original abstract

Estimating the number of communities is a fundamental problem in network analysis under the stochastic block model (SBM). In this paper, we study penalized estimators for this task based on normalized likelihood criteria. We show that a penalized estimator derived from the Normalized Maximum Likelihood (NML) is strongly consistent with a logarithmic penalty term, although its computation is intractable. To overcome this limitation, we consider the Normalized Maximum Complete Likelihood (NMCL) and the Decomposed Normalized Maximum Likelihood (DNML). The DNML admits an explicit formulation with cubic computational complexity in the number of nodes. We prove that the NMCL- and DNML- based estimators are strongly consistent for sparse networks in which the average node degree diverges with the network size. Empirical results show that the DNML estimator performs competitively with existing methods, particularly in unbalanced networks.

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.

Desk Editor's Note private letter to a colleague

The paper proves strong consistency for NMCL and DNML estimators of community number in sparse SBMs with diverging average degree and supplies an explicit cubic-time DNML formula.

read the letter

The one thing to know is that this paper proves strong consistency for estimators based on normalized maximum complete likelihood and decomposed normalized maximum likelihood when selecting the number of communities in stochastic block models. The key regime is sparse networks where average node degree diverges with network size. They also derive an explicit DNML expression that runs in cubic time in the number of nodes, sidestepping the intractability of plain NML while keeping the asymptotic guarantee. This is new compared with earlier normalized likelihood work, which either stayed intractable or lacked the consistency result in this exact sparse diverging-degree setting. The paper does well by focusing on unbalanced community sizes in the simulations, where the DNML version holds up competitively against existing methods. That practical angle matters because many real networks have uneven blocks. The proofs appear to follow standard information-theoretic arguments for penalized likelihood, and the stress-test found no internal gaps in the stated claims. The main soft spot is the exact-SBM assumption plus the diverging-degree condition. Those are required for the theorems but rule out many bounded-degree or misspecified networks that show up in applications. That is a standard limitation rather than a flaw in the logic, and the paper states the regime clearly. Empirical details would need referee scrutiny to confirm the simulation protocols and baseline choices, but nothing in the abstract suggests overclaiming. This work is for network statisticians and community-detection researchers who need consistent, computable criteria for model selection in sparse graphs. A reader already working on penalized likelihood or SBM asymptotics would get direct value from the consistency theorems and the explicit DNML form. I would send it to peer review. The results are focused, the contribution is clear, and the claims are precise enough to benefit from expert checking.

Referee Report

0 major / 4 minor

Summary. The paper develops penalized estimators for the number of communities under the stochastic block model using normalized likelihood criteria. It establishes that an NML-based estimator is strongly consistent with a logarithmic penalty (though intractable to compute), then introduces the NMCL and DNML criteria. The DNML admits an explicit closed-form expression with cubic complexity in the number of nodes. The central theoretical result is a proof that both the NMCL- and DNML-based estimators are strongly consistent for sparse SBM networks in which the average node degree diverges to infinity with network size. Numerical experiments indicate that the DNML estimator performs competitively with existing methods, with particular strength in unbalanced community-size regimes.

Significance. If the consistency proofs are correct, the work supplies rigorous asymptotic justification for normalized-likelihood penalties in a sparsity regime that is both theoretically interesting and practically relevant. The explicit, O(n^3) DNML formula is a concrete algorithmic contribution that removes the intractability barrier of full NML while preserving the consistency property. Credit is due for the precise statement of the divergence condition on average degree and for the empirical focus on unbalanced networks, where many competing criteria degrade.

minor comments (4)

Abstract: the phrase 'cubic computational complexity in the number of nodes' should be clarified to indicate whether the cubic term is strictly O(n^3) or also depends on the maximum number of communities K_max under consideration.
Section 4 (simulation protocol): the description of the unbalanced-network experiments should report the number of Monte Carlo replications and include standard errors or box-plots for the estimated number of communities, so that variability can be assessed.
Section 2 (related work): the literature review on penalized likelihood criteria for SBM would benefit from explicit comparison of the logarithmic penalty derived here with the penalties appearing in the BIC-type criteria of Wang & Bickel (2017) and the ICL criterion of Daudin et al. (2008).
Notation: the distinction between the normalized maximum complete likelihood (NMCL) and the decomposed normalized maximum likelihood (DNML) is introduced without a compact display equation showing how the DNML decomposition differs from the NMCL; adding such an equation would improve readability.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their careful reading of the manuscript and for the positive assessment, including recognition of the consistency results in the sparse regime where average degree diverges and the computational tractability of the DNML criterion. We appreciate the recommendation for minor revision.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper's core contribution consists of asymptotic consistency proofs for NMCL- and DNML-based estimators under the stochastic block model when average node degree diverges to infinity. These are mathematical derivations establishing strong consistency in a specified regime, not data-driven fits, parameter estimations renamed as predictions, or self-referential definitions. The abstract and described claims contain no load-bearing steps that reduce by construction to the paper's own inputs or unverified self-citations; the results are conditional on explicit SBM assumptions and are presented as independent theoretical results.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claims rest on the stochastic block model generative assumptions and standard asymptotic analysis for sparse regimes; no free parameters or invented entities are described in the abstract.

axioms (2)

domain assumption Data generated exactly from a stochastic block model
Consistency statements are derived under the SBM generative process.
domain assumption Average node degree diverges with network size
The sparse-network consistency result explicitly requires this divergence condition.

pith-pipeline@v0.9.0 · 5435 in / 1276 out tokens · 38816 ms · 2026-05-10T15:43:56.211091+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

4 extracted references · 4 canonical work pages

[1]

(2024) once again to obtain that kY a=1 na n na Γ(na + 1

Using the fact thatn 1 +n 2 +· · ·+n k =n, we apply Lemma 5.1 in Cerqueira et al. (2024) once again to obtain that kY a=1 na n na Γ(na + 1

work page 2024
[2]

≤ 1 Γ( 1 2)k−1Γ(n+ 1

work page
[3]

Thus, we conclude that supπ∈Πk Pπ(zn) Qk(zn) ≤ Γ( 1 2)Γ(n+ k 2 ) Γ( k 2 )Γ(n+ 1

work page
[4]

(A.12) By (A.7), we obtain that log Γ( 1 2)Γ(n+ k 2 ) Γ( k 2 )Γ(n+ 1 2) ! ≤ k−1 2 logn+c ′′ k,(A.13) wherec ′′ k is a constant depending only onk. Combining (A.12) and (A.13) we have, for all zn ∈[k] n, that log supπ∈Πk Pπ(zn) Qk(zn) ≤ k−1 2 logn+c ′′ k (A.14) Using the fact that Q k(zn) is a distribution overz n ∈[k] n, we have that Cz DNML(n, k) = X en ...

work page 2020

[1] [1]

(2024) once again to obtain that kY a=1 na n na Γ(na + 1

Using the fact thatn 1 +n 2 +· · ·+n k =n, we apply Lemma 5.1 in Cerqueira et al. (2024) once again to obtain that kY a=1 na n na Γ(na + 1

work page 2024

[2] [2]

≤ 1 Γ( 1 2)k−1Γ(n+ 1

work page

[3] [3]

Thus, we conclude that supπ∈Πk Pπ(zn) Qk(zn) ≤ Γ( 1 2)Γ(n+ k 2 ) Γ( k 2 )Γ(n+ 1

work page

[4] [4]

(A.12) By (A.7), we obtain that log Γ( 1 2)Γ(n+ k 2 ) Γ( k 2 )Γ(n+ 1 2) ! ≤ k−1 2 logn+c ′′ k,(A.13) wherec ′′ k is a constant depending only onk. Combining (A.12) and (A.13) we have, for all zn ∈[k] n, that log supπ∈Πk Pπ(zn) Qk(zn) ≤ k−1 2 logn+c ′′ k (A.14) Using the fact that Q k(zn) is a distribution overz n ∈[k] n, we have that Cz DNML(n, k) = X en ...

work page 2020