Estimation of Number of Communities in Assortative Sparse Networks
Authors: Neil Hwang
Jiarui Xu
Shirshendu Chatterjee
Sharmodeep Bhattacharyya
Venue:  (2021)
Keywords: networks
number of communities
Bethe-Hessian
sparse networks
stochastic block model

Abstract: Most community detection algorithms assume the number of communities, $K$, to be known \textit{a priori}. Among various approaches that have been proposed to estimate $K$, the non-parametric methods based on the spectral properties of the Bethe Hessian matrices have garnered much popularity for their simplicity, computational efficiency, and robust performance irrespective of the sparsity of the input data. Recently, one such method has been shown to estimate $K$ consistently if the input network is generated from the (semi-dense) stochastic block model, when the average of the expected degrees ($\tilde{d}$) of all the nodes in the network satisfies $\tilde{d} \gg \log(N)$  ($N$ being the number of nodes in the network). In this paper, we prove some finite sample results that hold for $\tilde{d} = o(\log(N))$, which in turn show that the estimation of $K$ based on the spectra of the Bethe Hessian matrices is consistent not only for the semi-dense regime, but also for the sub-logarithmic sparse regime when $1 \ll \tilde{d} \ll \log(N)$. Thus, our estimation procedure is a robust method for a wide range of problem settings, regardless of the sparsity of the network input.

Under review as a conference paper at ICLR 2021
ESTIMATION OF NUMBER OF COMMUNITIES IN As- SORTATIVE SPARSE NETWORKS
Anonymous authors Paper under double-blind review
ABSTRACT
Most community detection algorithms assume the number of communities, K, to be known priori. Among various approaches that have been proposed to esti- mate K. the non-parametric methods based on the spectral properties of the Bethe Hessian matrices have garnered much popularity for their simplicity, computa- tional efficiency, and robust performance irrespective of the sparsity of the input data. Recently, one such method has been shown to estimate K consistently if the input network is generated from the (semi-dense) stochastic block model, when the average of the expected degrees (d) of all the nodes in the network satisfies d >> log(N) (N being the number of nodes in the network). In this paper, we prove some finite sample results that hold for d = o(log(NV), which in turn show that the estimation of K based on the spectra of the Bethe Hessian matrices is consistent not only for the semi-dense regime, but also for the sub-logarithmic sparse regime when bust method for a wide range of problem settings, regardless of the sparsity of the network input.
d < log(N). Thus, our estimation procedure ro-
INTRODUCTION
Statistical analysis of network data has now become extensively studied field within statistics and machine learning (see (Goldenberg et al. 2010: Kolaczyk & Csárdi 2014: 4: Newman 2018) for reviews). Network datasets show up several disciplines. Examples include networks originating from biosciences such as gene regulation networks (Emmert-Streib et al. (2014)), protein- protein-protein interaction networks (De Las Rivas Fontanillo/ 2010)), structural (Rubinov & Sporns (2010) and functional networks (Friston (2011)) of brain and epidemiological networks (Reis et al. (2007)); networks originating from social media such as Facebook, Twitter and Linkedln (Faloutsos et al. 2010); ) citation and collaboration networks (Lehmann et al. (2003); information and technological networks such as internet-based networks (Adamic Glance (2005)), power networks (Pagani & Aiello (2013) and cell-tower networks (Isaacman al. (2011)). There several active areas of research in developing statistical methodologies for network data analysis and also deriving the theoretical properties of the statistical methods. In this paper, we focus on networks with community structure and finding the number of communities in networks with arbitrary sparsity level.
The last two decades saw resurgence of interest in problem popularly known "community detection". A common problem definition is to partition N nodes in a graph into K communities such that there are differences in edge densities between within and between communities, where K is assumed to be known a priori. Estimating number of communities (K) has recently become active in the literature. While the initial focus in the literature for estimating K has been devel- oping algorithms and drawing support from comain-speciffi intuition and empirical studies using the Stochastic Block Model (SBM), first proposed in Holland al. (1 (183),, (such as, [Saade et al. (2014)). Yan et al. (2018)). there has been recent progress attaining theoretical understanding of community numbers. [Bickel & Sarkar (2015) and Lei et al. (2016) proposed hypothesis testing approaches based on principal eigenvalues or singular values. Some likelihood-based methods us- ing the BIC criterion were proposed by Wang et al. (2017) and Hu et al. (0119). From a Bayesian perspective, Riolo al. (2017) discussed priors for number of communities under the SBM and designed an Markov Chain Monte Carlo algorithm, Kemp et al. (2006) presented a nonparametric Bayesian approach for detecting concept systems, [u et al. (006) introduced an infinite-state latent

---

Under review as a conference paper at ICLR 2021
variable as part of Dirichlet process mixture model, and Cerqueiraa & Leonardi (2020) proposed an estimator based on integrated likelihood for the SBM. Rosvall & Bergstrom (2007) introduced the concept of the minimum description length (MDL) to describe network modularities in partitioning networks, and Peixoto (2013) employed MDL to detect the number of communities. CChn & Lei (2018) and [i et al. (2020) proposed vross-validation based approaches with theoretical guarantees to estimate K. Yan et al. (2018) proposed semi-definite programming approach, and Ma et al. (2018) proposed an estimator based on the loss of binary segmentation using pseudo-likelihow ra- tio. All of these approaches had theoretical guarantees. However, all the theoretical results were obtained under the assumption that mean density of the networks is greater than log(N).
Methods based on the spectrum of a certain class of matrices have become increasingly popular in recent years as non-parane non-parametric alternatives that are more computationally efficient and applicable to wider range of settings. Most notably the non-backtracking matrices (e.g.. Krzakala et al. (2013), Saade et al. 20144)) Coste Zhu (0199, Bordenave et al. (2015), [aade et al. (2066) and the Bethe Hessian matrices (e.g.. Saade al. (2015b). Lelarge (2018), Dall' Amico et al. (2019), Saade et al. (2015a), Dall" Amico et al. (2020), Saade et al. (2014a). Le & Levina (2015) have received much attention due their non-parametric form and competitive performance in the presence of degree heterogeneity and sparsity. In particular, unlike the non- backkraackking operator, the Bethe Hessian is real symmetric operator and hence offers additional computational advantages. Through simula- tions, (Saade et al. (2014a) demonstrated that the Bethe Hessian outperformed the non-backtracking operator. belief propagation, and the adjacency matrices on clustering on both accuracy and effi- ciency. Le & Levina (015)) proved the consistency of the method based on the spectrum of the Bethe Hessian operator in semi-dense regimes, i.e., with the expected degree d >> log(N) and the scalar parameter chosen from the two values commonly used in the literature based on heuristics for assortative and disassortative networks. However, other than the two candidate values and their variations, there are no other known values for the scalar parameter to ensure the consistency result in any regime. Furthermore, real-world networks are generally much more sparse and there is no theoretical result in the literature that guarantees the effectiveness of the Bethe Hessian operator in more sparse regimes.
Our contribution. In this paper, we contribute to the theoretical understanding of the Bethe Hessian operator in estimating K for networks generated from the SBM in any regime regardless of the sparsity. We have three main contributions.
We show that the method of estimating K based on the spectral properties of the Bethe Hessian matrix ("spectral method") statistically consistent, even in regimes more sparse than those previously considered in the literature, with the expected degree < d log(N). The precise definition of d is given in 22.1
We provide the first-of-its-kind interval of values for the scalar parameter of the Bethe Hessian operator that serves as a sufficient condition for the spectral method to correctly estimate K asymptotically in network data.
Through extensive simulations, we demonstrate that for any value chosen from the interval for the scalar parameter, the spectral method correctly estimates K in networks regardless of sparsity. We also consider the heuristics- based values commonly used in the literature for the scalar parameter in the context of the interval.
The paper is arranged as follows. We present the definitions and a formal problem statement in We present our main theoretical result and sketch of the proof in $3 followed by empirical methods in $4 The simulation results and concluding remarks are given in and [ respectively.
2
2
PRELIMINARIES
2.1 NOTATION
An adjacency matrix, denoted by A, is a random matrix whose rows and columns are labeled by nodes i,j [N], where Aij 1 if there is an edge between nodes and j and otherwise, and [N] denotes the set (1,..., NJ. The mean observed degree is denoted by d == Y 1 AlN N and the
2

---

Under review as a conference paper at ICLR 2021
expected degree by d= EAAIN (A) denotes the f-th largest eigenvalue of A and (A) denotes the E-th smallest eigenvalue of A.
2.2 THE STOCHASTIC BLOCK MODEL
The stochastic block model (SBM) is simple generative model for network data that embeds community structure in an adjacency matrix X of the randomly generated network. SBM has three parameters: (1) the number of communities K; (2) the membership vector (21, ... 2N) that assigns a community label E [K] to each node E [N]; and (3) the connectivity probability matrix Bx x K where the element Bab represents the probability of an edge between nodes belonging to community a and 6, where a, b E [K].
Z E Z is defined as the community membership matrix such that Z: 1 if node be- longs to community j and otherwise. We denote the maximum expected degree by dmax == N max, Li=il(ZZZ" )s> Diag(ZBZ")u) and the maximum entry in matrix B by d/N, where = N maxx,be(K] Bab- À denotes the smallest eigenvalue of the normalized matrix, == & ()... A is the expectation of A and is computed A ZBZT Diag ZBZ"). D is diagonal matrix whose i-th diagonal entry is the sum of the i-th row of A. Let N be the vector of true community sizes and Nmin denotes the number of nodes in the community with the lowest number of nodes in it.
A network generated from the SBM with parameters K, B, Z is defined to be assortative if Boa Bob for all a, b E [K] with a + b, and if B has all positive eigenvalues (i.e., B has full-rank K). The existing works in the literature on the spectral method referenced above have considered assortative networks, and we also consider assortative networks in this paper.
2.3 THE BETHE HESSIAN MATRIX
The Bethe Hessian matrix associated with an adjacency matrix A is defined as
H = (C² 1)IN + D ÇA where Ç > 1 is real scalar parameter, D == Diag(A (A1n) is diagonal matrix whose i-th diagonal entry corresponds to the degree of the i-th node, and IN is an identity matrix of dimension N N.
(2.1)
As a real symmetric operator, H. is analytically tractable and computationally efficient, and has a number of useful properties. Saade et al.) (2014a) demonstrated that the community structure in A can be recovered by applying standard clustering algorithm (such as k-means clustering) to the eigenvectors of Hę corresponding to negative cigenvalues. In the spectral clustering literature, those eigenvalues whose eigenvectors encode the community structure are known the informative eigenvalues and have been observed to be well-separated from the bulk of the spectrum. In Saade et al. 20144), Ç was set to be the square-root of the mean observed degree as a heuristic to render informative (negative) eigenvalues of Hç-
Le & Levina (2015) showed that the number of informative eigenvalues of He directly estimate K in the semi-dense regime (d >> log( ()) when is set to be either I'm := (d2 + (dk +...+ d3) or := v(d, +... + dNN/N. Both I'm and ra are obtained based on heuristic arguments and are commonly used in the literature to estimate the radius of the bulk of the spectra. тa was considered in [Sadde et al. (2014a) and the choice of I' stems from the deep connection between the spectrum of Hę and that of another matrix which is known as the non-backtracking operator B. Denoting by m the number of edges in A. B is 2m x 2m matrix indexed by directed edges + and defined B. = (1 da), where å is the Kronecker delta and m is the number of edges.
As in HG, the informative eigenvalues of B are well-separated from the bulk its spectrum and are real, so it also has been used to develop many popular nan-parametric methods for clustering (see e.g.,/Saade /Saade et al. (2014b), Coste & Zhu (2019), Bordenave et al. (2015), Bruna & Li 2017 Gulikers et al. (2 This deep connection between He and 8 was noted in Krzakala et al. (2013) and can be summarized by the phenomenon that, given any eigenvalue v of B. the determinant of H vanishes. However, unlike HG, B is non-symmetric and its dimension (2m x 2m) can get quite large. These present analytical and computational challenges when using B, and in turn have popularized Hę tool for clustering. Le & Levina (0055) showed that in semi-dense regimes
3

---

Under review as a conference paper at ICLR 2021
with expected degree d > log(N), the number of negative eigenvalues of H directly estimate K for Ç E {Tm.rr ra where the methods were called BHm and BHa. In addition, it was noted that the number of negative eigenvalues of H tend to underestimate K when networks are unbalanced. Hence, corrections for BHm and BH, were proposed, namely BHmc and BHac, which heuristically estimate K = max 1pn-k+1 & Pn-2) where PI 3 ... > PN are sorted eigenvalues and & > 0 the hyperparameter. In light of this, we present the following problem we focus on in this paper:
Problem Definition: Suppose that we observe one network generated from the SBM, where the parameters K, B, B satisfy (i) assortativity, and (ii) the sparsity condition d = olog(N)), For the appropriate choices of C. are the negative eigenvalues of the Bethe Hessian matrix Hę still informative for estimating K'? If so, what are the appropriate choices for Ç? Can there be other heuristic choices for Ç? Are the popular heuristic choices of Ç, i.e. I'm and ra as defined above (hereinafter "heuristic choices"), appropriate in the above sense?
THEORETICAL RESULTS
Our main contribution is twofold. First, we show that even in a sparse regime when 1 < d << log(N), the number of informative eigenvalues of H: directly estimates K consistently. Second, we provide the first-of-its-knnd interval, which serves conveniently as sufficient condition, of ap- propriate values for Ç for which the number of informative eigenvalues of the associated matrix H. directly estimates K. Below, we formally state this twofold result and provide a sketch of the proof, where we build intuition and provide key intermediate results. Precise statements and full proofs for all of the intermediate results discussed below are presented in $1.2 in the Supplement, along with statements and proofs of other relevant results in the literature.
Theorem 3.1. (Main Result) Let B == dd(ANmin min 1)/N. For any ò E (0,3/2), Hę has exactly K negative eigenvalues for all & 1 3 + v 32 +4 4dmax) with probability at least 1 (xpl-(c/Va))/2-b))
Sketch of the Proof assessing the spectral properties of Hg. it is more convenient to instead work with the spectrum of the associated Laplacian matrix, since it would allow to some of the important known results on the concentration of certain regularized adjacency matrix A around its expectation. Indeed, we are allowed to do so due to Sylvester's law of inertia (Theorem 1,4 in Supplement $1.1), which gives us that Hç and the associated Laplacian have the same inertia. Note that the inertia of a real and symmetric matrix is vector consisting of the number of positive, negative, and zero eigenvalues of the matrix.
To be more precise, consider the Laplacian L Lc H D Dc- - A, where D. = ( 2) &
and Ç 1. Now take its symmetric normalized version L(Lç) == D' Then, by Sylvester's 's law of inertia, H& and ((Lç) have the same number of negative eigenvalues (see Lemma 1.5 in Supplement $1.2).
Next, to make the problem more tractable, we show that ((Lç) concentrates around its expec- tation C(Le) such that the problem can be stated in terms of the latter, which is deterministic matrix, rather than the former, the random counterpart. More concretely, denote the expectation of
the Laplacian L(I,)) == D- D=>/", where L = D. Á and D = (S - f)T + $D. Then, we decompose L(Lc) into two parts. The first part is the difference between A and A, reg- ularized by 1- The second part is the difference between Á regularized by D- and Á regularized by the expectation of 1- In a regime satisfying d o(log(N)), the first part is bounded by 5-1/c (Va+(3 114+(1221000 1)1/4), where C' is a constant, with probability at least -N -1)42))))) (see Theorem 1.3 in Supplement $1.1) due concentration result in Le et al. (2017) where is shown that regularized A concentrates around its expectation. The second part is also bounded by
Cr2
(1+ where C' is a constant, with probability at least 1 2r due the properties of the Orlicz norm and Markov- Benttov--eettei-ttypeee inequalities. Hence, for d = ollog N), the difference between the sample and its expected Laplacian, ||<(L,) L(Lc)]], is finite. Note
4

---

Under review as a conference paper at ICLR 2021
that this is finite-sample result. We can obtain asymptotic result from it by considering appro- priate relationships among d, Ç. and r, where r > determines the probability (1 e>)) for the foregoing result. A sufficient condition for ||]( [(Le)] to be o(1) with high probability is &< S Vi
(see Lemma 1.6 Supplement $1.2).
As the last step in this proof sketch, we apply Weyl's 's inequality Ag( (x and Ag+1 (-Lc), and readily see that only the K informative eigenvalues are negative, and hence the claimed result in the theorem (see Proof of Theorem 3.1 in Supplement $1.2).
Remark (Theorem 3.1). Note that Theorem 3.1 is a finite sample result. The sufficient condition vd < C implies a high probability asymptotic result showing consistent estimation of the num- ber of communities by the spectral method with chosen from the interval given in the theorem. Hereinafter, we refer to the interval for Ç stated in Theorem 3.1 as the "oracle interval".
A sufficient threshold for detecting K is presented below with proof appearing in the Supplement.
Corollary 3.2. In the setup of Theorem 3.1 with high probability, can be detected if the following threshold satisfied:
2N dmax
(3.1)
dNmin
Nmin
4 EMPIRICAL METHODS
4.1 ESTIMATION OF THE INTERVAL FOR BETHE HESSIAN SCALAR PARAMETER
One practical consideration that needs to be addressed when implementing Theorem 3.1 and Corol- lary i. finding estimators of the parameters that are not directly observable in the data, namely d. dmax. X, and Nmin. Below, we propose an algorithm to compute the estimators for these oracle values. We do so by first estimating community memberships Z using regularized spectral cluster- ing (Amini et al. (2013); [e et al. (2017) and using maximum likelihood estimates to estimate the rest of the parameters. Then, the desired estimators are computed in straightforward way.
Procedure 4.1 PARAMS-ESTIMANTI
Input: Adjacency matrix A; a candidate number of communities Kg Output: Nx,: estimator for N; BK, estimator for B; and 2: estimator for Z
1: Obtain 2 using regularized spectral clustering of A with Ko communities
> See Remark
4.1
2: NK. + 1"IN
3: Bx, (iag(NKo) ko) -1ZT S...AAAA (iDiag(NKo)+>
Remark In Step 1, we need an algorithm which can consistently recover communities from A. Other standard clustering algorithms can also be used in Step as long as it consistently recovers community labels. The consistency of the estimators proposed in Algorithm 4.1 have already been established in Le et al. (017). The time complexity of the procedure is O(N3) driven by the eigenvalue computation in Step 1. Hereinafter, we refer the interval computed with the estimators from this procedure as the "estimated interval" (recall that the interval in Theorem 3.1 is referred to as the "oracle interval").
Procedure 4.1 outputs Nk, and BR, with candidate number of communities Kú [1, K as an input, where Kmax is a tuning parameter. Then, the minimal community size is estimated with Nmin min min(Na). Nmin is an upper bound of Nmin with high probability and has shown in simulations to be good estimate of Nmia- Details on ad-hoc estimation of d, dmaxx and À using NK, and B and tuning parameter Ko given in the Supplement $1.3.
Figure shows the simulation results on the performance of the oracle and estimated intervals for Ç, and two popular heuristic choices 7'm and ra. Under the setting of large network (N) and the assortativity condition, the estimated intervals computed with Procedure [4. appear to match their oracle values well. It is shown that once the threshold in Corollary 3.2 is satisfied, T'm and r.
5

---

Under review as a conference paper at ICLR 2021
turn out to be sufficient, i.e., fall within the oracle interval. In S is shown that values from the interval other than Tm and Ta can improve the performance, especially when . large in the sparse regime. Further extensive simulation results based on other parameter settings are included in the Supplement $1.3.
2013 ... 2eta.est est
5000
15000
N. 25000
N: 35000
5
3
2-
Figure 4.1: The oracle interval for (Theorem 3.1 and its estimation (Procedure 4.1 are shown with two popular heuristic choices for (rm and ra) commonly used in literature. Network data was simulated from the SBM with the parameter settings shown in Table 5.1 with K = 3 and / each simulated with 20 repetitions. Intervals are shown zeros when the threshold not met.
4.2 ESTIMATION OF THE NUMBER OF COMMUNITIES WITH THE BETHE HESSIAN
With choice of ( from the interval computed with the estimators from Procedure 4.1 above, now propose an algorithm below that uses a spectral method to directly estimate K.
Procedure 4.2 K-ESTIMATION
Input: Adjacency matrix A; scalar parameter Ç
Output: K: estimator K
1: D < NA
2: H. (S² 1)JNN +D D--C -A
3: Obtain sorted eigenvalues Af,.., A/y of H,
4: + max(k: A1 < <0}
Just with Procedure 4.1 the time complexity of Procedure 4.2 is O(N3) driven by the cigenvalue computation in Step 3.
Remark (.2
Hereinafter, refer Procedures 4.1 and 4.2 as the "BHsparse" method.
EMPIRICAL STUDIES
We denote empirical accuracy rate (ACR) as the fraction of accurate estimates of K out of 20 repetitions per simulation. Recent literature (Le & Levina (205)), Yan et al. (2018), Cerqueira & Leonardi (2020)) showed that methods based on the spectrum of the Bethe Hessian operator with popular heuristic choices for Ç. i.e., (rm,ra), are competitive in performance and computational efficiency in the semi-dense regimes. However, the synthetic networks used in the above references were relatively small (in terms of N) and more dense (with > O(log(N)) compared to the real- world networks. Through extensive simulations, those based the heuristic choices for on large (N up to 35,000) and sparse (d o[log(N)) networks. It is shown that BHsparse outperforms those based on the heuristic choices, especially as N gets large and networks become more assortative.
compare the performance of BHsparse with

---

Under review as a conference paper at ICLR 2021
5.1 DATA GENERATION AND SIMULATION SETTINGS
We simulate network data from the SBM under two different settings. In Simulation Setting (I), define B pBn p(n 1)b(Ix - k p controls the expected degree by d = p(1 (ZB,z" Diag ZB, ))
7 is the in/out ratio based on B and determines the degree of assortativity. b is the baseline value B, which is set to 0.1. We first simulate the member- ship vector Z ~ Mult (1; (...... k) We set d E (3ylog(N] N), 0.165 (log( (log(N))) 0.788( N) ()/133) by varying p. assess the performance of the algorithms under different sparsity regimes. The stants in the rates of d are chosen in way that d is same N 1000 for all the rates. With fixed Z and B, and given model parameters K, N, d, and v), then generate A with 20 repetitions. Table 5.1 summarises the combinations of model parameter settings used in the simulations.
Table 5.1: Model Parameters for Simulation Setting (1)
K
N
3
(5000, 15000, 25000, 35000)
(V)), (.165(log(NN) 0.788)))))))
(3, 4, ..., 8)
4
(5000, 15000, 25000, 35000)
(oooog[). 0. (l)6)))) (1))))))))))))).077)))))))))))))
{3, ..., 8}
10
(5000, 15000, 25000, 35000)
[3 (log(o)gV))) (V)
17, (16,
25
(25000) (25000)
{3 [og (15((og((N)22,0..888())))))
421, 553
50
[3 log([)) 0. (.1666(0gg())) (.785)())))
(101, 102, 1101
In Simulation Setting (2), we
general probability connectivity matrix defined in equa- where E {2.5 + (m - 1)0.25 m .... 9}, and set other parameters as follows:
tion 5.1
3 (N); K = 3; and N (5000, 15000, 25000, 35000}.
(1+
0.5
0.3
B =
0.5
2 21
0.1
(5.1)
0.3
0.1
0.5 + m
5.2 SIMULATION RESULTS
Figure 5.1 below shows ACR of BHsparse versus with varying values for chosen from quantiles of the oracle interval in Theorem 3.1 It is clear that there is threshold value of r) below which detection of K fails and otherwise it succeeds. The top row (A) shows that this threshold decreases N increases from 5, 000 15, 000 while the bottom row (B) shows that the threshold increases with K. Note that the threshold for À in equation 3.1 which depends on 17, decreases as N increases.
Quantile (%) - 10 +A. 30
+ 70 +82 90
5000
N: 15000
25000
N: 35000
1.00
0.50
0.25
0.00
K:
K: 25
50
1.00
0.75
0.50
17.5
20.0
102.5
105
1100
Figure 5.1: ACR of BHsparse with set to quantiles (10%. 30%, 50%. 70%, 90%) of the oracle
interval in Theorem 3.1 Network data was generated from Simulation Setting (1) with fixed d
3 //log(N). (A) shows ACR versus 77 for varying levels of N with K 3. (B) shows ACR versus for varying levels of K with N = 25,0000 000.

---

Under review as a conference paper at ICLR 2021
Quantie (%)
70
90
K:3
KC
K-
K-3
IC
K:
5000
N: 15000
N: 25000
N: 35000
N: 25000
N: 25000
0.75
4 0.50
0.25
23.0
Figure 5.2: ACR of BHsparse versus 7l K and N vary, using estimated intervals with Ç set to quantiles (10%, 30%, 50%. 70%, 90%) the estimated intervals using Procedure [4T] based on networks satisfying the threshold (3.2) Network data was generated from Simulation Setting (1) with fixed d = /lo((N).
shows ACR of BHsparse with set different quantiles of the estimated intervals. Only those cases where either interval exists are shown in the plot. It can be observed that the performance becomes worse as ( gets close to end-points of the intervals. Generally 30% 50% quantiles within the intervals appear to work the best.
Figure 5.2
In Figure 5.3 (Figure 5.4 resp.), compare the performance of BHsparse using 30% and 50%
quantiles of oracle intervals (estiamted intervals resp.) with BHmc and BHac. Figure [53 and 5.4 show that when the threshold in Corollary 3.2 is satisfied, Ç (30%, 50% quantiles both the oracle and estimated intervals perform better than the two heuristic choices in Le & Levina (2015).
The plots corresponding to Figures 5.1 5.2 5.3 and 5.4 for the other two density regimes of (0.165(log(N) O. (88(33) are given in the Supplement $1.3.
We also compare performances of BHsparse of Ç equals 30%, 50%, and 70% quantiles of the timated intervals with BHme and BHac with a more general setting of the probability connectivity matrix Equation 5. Figure 5.5 shows the ACR performances of proposed method with choices of as 30% to 50% quantiles of the intervals over-perform the methods proposed in Le & Levina 20155.
Method
+ BHac
BHimc
BHeparse-Ora-305
BHaparse-Ore-50k
5000
N: 15000
25000
N: 35000
1.00
0.95
0
0 0.90
0.05
7.5
7.0
8.0
B
0.98
02
0.85
0.92
22
23
24
82
54
108
100
109
110
110
Figure 5.3: Row (A) shows ACR versus using oracle intervals, with different values N and K 3. Row (B) shows ACR versus n K varies with fixed N = 25, 000. Both plots only include cases where oracle thresholds in Corollary 3.2 are satisfied and are based on data generated from Simulation Setting (1) with fixed å i= 3 (N).
8

---

Under review as a conference paper at ICLR 2021
Method
BHac
BHmc
BrisparseEEat300
BrispareeEa--50%
K:3
K:3
K0
K:3
KC4
KC
N: 5000
N 15000
25000
35000
N: 25000
N: 25000
08
0.7
5
23.5
Figure 5.4: ACR versus K varies using estimated intervals, based on data from Simulation Set- ting (1) with fixed d = 3 (ogg(A))))) N) and only including cases where estimated thresholds in Corollary 3.2 are satisfied. For Ç. 30% and 50% quantiles the estimated intervals are considered.
Method
-
15000
1.0
0.8
3.50
Figure 5.5: ACR versus 77 N varies using estimated intervals, based on data from Simulation Setting (2) with K 3 and d 3 / [N), and only include cases where estimated thresholds in Corollary 3.2 are satisfied. For Ç, 30% and 50% quantiles of the estimated intervals are considered.
5.3 REAI-WORLLD NETWORK APPLICATION
We apply our proposed methods to benchmark real-world network data set, the Polbooks network, which also been used in previous works (Le & Levina (2015), Chen & Lei (2018). The Polbooks network (Rossi & Ahmed (2015)) represents books on politics published around the 2004 presiden- bundle from Amazon.com, The Polbooks network has two natural communities (liberal and conservative). 105 nodes, and the mean observed degree of 8.4. The estimated interval for ( using Procedure 4. [1.3, 7.3]. Using the 50th percentile of the interval, Procedure 4.1 correctly estimates the number of communities. K, K 2, while both BHac and BHmc estimate the number of communities, K, as K 4. This result demonstrates that Procedures 4.1 and 4.2 can correctly detect the number of communities in real-world networks too.
tial election that were purchased together
DISCUSSION
In this paper, we contribute theoretical results on the selection of Bethe Hessian scalar parameter, Ç, for consistent estimation of number of communities (K) in networks that are generated from the SBM with arbitrary degree of sparsity. To the best our knowledge, this is the first study to theoretically prove the consistency of the Bethe Hessian spectral method to estimate K in sparse regimes with d = o(log(NV)). We also rigorously derive the oracle interval and provide a convenient way to empirically estimate the intervals for selecting Ç to construct the Bethe Hessian operator to consistently estimate K. We support theoretical results with simulation studies and real-world network application too.
In this paper, only prove upper bound of the hypothesized threshold for estimation of number of communities. An important future work will be to prove the lower bound results such that the existence of the threshold can be properly established.

---

Under review as a conference paper at ICLR 2021
REFERENCES
Lada A Adamic and Natalie Glance. The political blogosphere and the 2004 us election: divided they blog. In Proceedings of the 3rd international workshop on Link discovery, pp. 36 43. ACM, 2005.
Arash A Amini, Aiyou Chen, Peter J Bickel, Elizaveta Levina, al. Pseudo-likelihood methods for community detection in large sparse networks. The Annals of Statistics, 41(4):2097-2122, 2013. 2013.
Peter J Bickel and Purnamrita Sarkar. Hypothesis testing for automated community detection in networks. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 1(78): 253-273, 2015.
Charles Bordenave, Marc Lelarge, and Laurent Massoulié. Non-backtracking spectrum of random graphs: community detection and non-regular ramanujan graphs. In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, pp. 1347-1357. IEEE, 2015.
Joan Bruna and Li. Community detection with graph neural networks. Stat, 1050:27, 2017.
Andressa Cerqueira and Florencia Leonardi. Estimation of the number of communities in the stochastic block model. IEEE Transactions on Information Theory, 2020.
Kehui Chen and Jing Lei. Network cross-validation for determining the number of communities in network data. Journal of the American Statistical Association, 113(521):241-551 2018.
Simon Coste and Yizhe Zhu, Eigenvalues of the non- non-backtracking operator detached from the bulk. arXiv preprint arXiv: /et0/9967300,0.. 2019.
Lorenzo Dall' Amico, Romain Couillet, and Nicolas Tremblay. Revisiting the bethe-hessian: im- proved community detection in sparse heterogencous graphs. In Advances in Neural Information Processing Systems, pp. 4037-4047, 2019.
Lorenzo Dall' Amico, Romain Couillet, and Nicolas Tremblay. Community detection in sparse time- evolving graphs with a dynamical bethe-hessian. arXiv preprint arXiv:2006.04510 2020.
Javier De Las Rivas and Celia Fontanillo. Protein-protein interactions essentials: key concepts to building and analyzing interactome networks. PLoS computational biology, 10000007, 2010.
Frank Emmert-Streib, Matthias Dehmer, and Benjamin Kains. Gene regulatory networks and their applications: understanding biological and medical problems in terms of networks. Frontiers in cell and developmental biology, 2:38, 2014.
Michalis Faloutsos, Thomas Karagiannis, and Sue Moon. Online social networks. IEEE network, 24(5):4-5, 2010.
Karl J Friston. Functional and effective connectivity: a review. Brain connectivity, 1(1):13-36, 2011.
Anna Goldenberg, Alice X Zheng, Stephen E Fienberg, and Edoardo M Airoldi, A survey of statis- tical network models. Now Publishers Inc, 2010.
Lennart Gulikers, Mare Lelarge, and Laurent Massoulié. Non-backtracking spectrum of degree- corrected stochastic block models. arXiv preprint 10xiv.1609.02487 2016.
Paul W Holland, Kathryn Blackmond Laskey, and Samuel Leinhardt. Stochastic blockmodels: First steps. Social networks, 109): 1983.
Jianwei Hu, Hong Qin, Ting Yan, and Yunpeng Zhao. Corrected bayesian information criterion for stochastic block models. Journal of the American Statistical Association, pp. 1-13, 2019.
Sibren Isaacman, Richard Becker, Ramón Cáceres, Stephen Kobourov, Margaret Martonosi, James Rowland, and Alexander Varshavsky. Identifying important places in people's ' lives from cellular network data. In International Conference on Pervasive Computing, pp. 133-151. Springer, Springer,, 201 1.
10

---

Under review as a conference paper at ICLR 2021
Charles Kemp, Joshua B Tenenbaum, Thomas L Griffiths, Takeshi Yamada, and Naonori Ueda. Learning systems concepts with an infinite relational model. In AAAI, volume 3, pp. 5, 2006.
Eric D Kolaczyk and Gábor Csárdi. Statistical analysis of network data with R, volume 65. Springer, 2014.
Florent Krzakala, Cristopher Moore, Elchanan Mossel, Joe Neeman, Allan Sly. Lenka Zdeborová, and Pan Zhang. Spectral redemption in clustering sparse networks. Proceedings of the National Academy of Sciences, 110652)20935522094) 2013.
Can M Le and Elizaveta Levina. Estimating the number of communities in networks by spectral methods. arXiv preprint arXiv:1507.0082) 2015.
Can M Le, Elizaveta Levina, and Roman Vershynin. Concentration and regularization of random graphs. Random Structures & Algorithms, 51(3):53--561, 2017. 2017.
Sune Lehmann, Benny Lautrup, and Andrew Jackson. Citation networks in high energy physics. Physical Review E, 68(2):0261 2003.
Jing Lei al. goodness-of-ft test for stochastic block models. The Annals of Statistics, 44(1): 401-424, 2016.
Marc Lelarge. Community detection with the triplet loss, 2018. URL /tRphttts///peeeeieiee
Tianxi Li, Elizaveta Levina, and Ji Zhu, Network cross-validation by edge sampling. Biometrika, 107(2):257-276, 2020.
Shujie Ma, Liangjun Su, and Yichong Zhang. Determining the number communities degree- 2018.
corrected stochastic block models. arXiv preprint
Mark Newman. Networks. Oxford university press, 2018.
Giuliano Andrea Pagani and Marco Aiello. The power grid as a complex network: a survey. Physica A: Statistical Mechanics and its Applications, 392(1 11:2688-22700 2700, 2013.
Tiago P Peixoto. Parsimonious module inference in large networks. Physical review letters, 110 (14):148701, 2013.
Ben Y Reis, Isaac S Kohane, and Kenneth D Mandl. An epidemiological network model for disease outbreak detection. PLOS medicine, 4(6):e110, 2007.
Maria A Riolo, George T Cantwell, Gesine Reinert, and Mark EJ Newman. Efficient method for estimating the number of communities a network. Physical review e, 96(3):333300, 2017.
Ryan A. Rossi and Nesreen K. Ahmed. The network data repository with interactive graph analytics and visualization. In AAAI, 2015. /RR/http.///eetorrepppottoro
Martin Rosvall and Carl Bergstrom. An information-thhorreti framework for resolving community structure in complex networks. Proceedings of the National Academy of Sciences, 104(18):7327- 7331, 2007.
Mikail Rubinov and Olaf Sporns. Complex network measures of brain connectivity: uses and inter- pretations. Neuroimage, 52(3):1059-166) 2010.
Alaa Saade, Florent Krzakala, and Lenka Zdeborová. Spectral clustering of graphs with the bethe hessian. In Advances in Neural Information Processing Systems, pp. 406-414, 2014a.
Alaa Saade. Florent Krzakala, and Lenka Zdeborová. Spectral density of the bon-backtracking operator on random graphs. EPL (Europhysics Letters), 107(5):50005, 2014b.
Alaa Saade, Florent Krzakala, and Lenka Zdeborová. Matrix completion from fewer entries: Spec- tral detectability and rank estimation. In Advances in Neural Information Processing Systems, pp. 1261-1269, 2015a.
11

---

Under review as a conference paper at ICLR 2021
Alaa Saade, Mare Lelarge, Florent Krzakala, and Lenka Zdeborová. Spectral detection in the sored block model. In 2015 IEEE International Symposium on Information Theory (ISIT), pp- 1184-1188. IEEE, 2015b.
Alaa Saade, Mare Lelarge, Florent Krzakala, and Lenka Zdeborová. Clustering from sparse pairwise measurements. In 2016 IEEE International Symposium on Information Theory (ISIT), pp. 780- 784. IEEE, 2016.
YX Rachel Wang, Peter Bickel, et al. Likelihood based model selection for stochastic block models. The Annals of Statistics, 45(2):500-528, 2017.
Zhao Xu, Volker Tresp, Kai Yu, and Hans-Peter Kriegel. Learning infinite hidden relational models. Uncertainity in Artificial Intelligence (UA12006), pp. 2, 2006.
Bowei Yan, Purnamrita Sarkar, and Xiuyuan Cheng. Provable estimation of the number of blocks in block models. In International Conference Artificial Intelligence and Statistics, pp. 1185- 1194, 2018
12


Reviews:
[{"review_id": "heM21lRzQCX", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Post Rebuttal:\n\nI think the paper is much improved, and I'm bumping up my score accordingly. \n\nSmall point - in corollary 3.2, to say 'with high probability' still requires that explicit conditions such as $|\\beta|/\\sqrt{d} \\to \\infty$ are stated. Thm 3.1 makes no claim of _high_ probability - it instead has an explicit bound, and does not impose conditions needed to make this bound 'high'. As a conseuqnce, the conditions of Thm 3.1 do not suffice for corollary 3.2. \n\n----\n\n\nSummary:\n\nThe paper studies the estimation of the number of communities in a graph drawn from a stochastic block model (SBM) using spectral properties of the Bethe Hessian of the observed graph. While this scheme has been proposed in the prior literature, the focus here is on sparse graphs, with average degrees bounded as $o(\\log N)$. The authors show a sufficient condition for consistency of this procedure in this regime, and provide simulations as evidence for the effectiveness of the resulting method. These simulations incorporate the challenges of having to estimate the various parameters of the generative model. \n\n---\n\nStrengths:\n\nThe problem is contexaulised well, and related work is adequately discussed and compared to. The theoretical analyses provided are crisp, and use existing results on concentration of random graphs in a nice way. I particularly appreciate that the simulations dealt with the fact that parameters of the models need to be estimated. The procedure to do so is well described, with the performance gains clearly demonstrated for small $K$.\n\nWeaknesses:\n\nFor me there are two main weaknesses:\n\na) Section 3 needs some polish. \n\nFirst, The section is begun by directly launching into a proof sketch for the relevant method. This comes out of nowhere, and would be helped by describing the precise main result before launching into a proof of it. This could be done, perhaps, by stating Thm 3.3 before the argument, and then launching into the proof sketch.\n\nSecond, I don't think corrolary 3.4 is entirely accurate. There's a minor issue of an additive $(d/N)$ term that's missed on the right hand side. More importantly, in order to show consistency in the usual setting of large graphs that is taken in SBMs, you need to be able to drive the probability of error to $0$, which requires that $\\zeta/\\sqrt{d} \\to \\infty$ as $N$ blows up. The necessary condition stated doesn't allow that _unless_ $d_{\\max}$ blows up with $N$. This is worth saying since the result of this corollary is ultimately compared to weak recovery of the $2$-SBM, where the claim made is not valid because the condition for weak recovery that is stated holds even when $d_{\\max}$ and $d$ are $O(1)$. \n\nSpeaking of, I want to point out that the condition on the top of page 4 is for _weak recovery_, that is, the problem of obtaining a partition which is _slightly_ better than random guessing. The phrasing of the paragraph suggests that the problem being compared to is that of exact recovery, for which the SNR threshold is very different (e.g. degrees need to blow up logarithmically). Also, it is worth noting here that even the distinguishability problem for the SBM (i.e., hypothesis testing between an SBM and an unstructured Erdos-Renyi graph of the same average degree) in the $2$-SBM requires $(a-b)^2 > 2(a+b)$. This is a weaker problem than recovering the number of communities, and so effectively serves as a lower bound. See, e.g. [1].\n\nMinor aside - it might be better to state Corollary 3.4 in terms of $\\lambda$ instead of $\\lambda_K^{\\downarrow}$. The reason for this is that as it stands, it looks like the left hand side grows linearly with $N$, while the right hand side grows sublogarithmically. This is, of course, not the case because $\\lambda_K^{\\downarrow}$ itself must behave at the scale $o(\\log N)/N$ in order for the degrees to be $o(\\log N)$. The normalised $\\lambda$ gets rid of this effect.\n\nb) In my opinion, the experiments need to be deepened. \n\nUltimately the result given can be seen as a thresholding of $\\frac{d\\lambda}{\\sqrt{d_{\\max} -1}} \\frac{N_{\\min}}{N},$ or, in the multinomial prior chosen, in terms of $\\frac{d\\lambda}{\\sqrt{d_\\max}-1} \\frac{1}{K}$ (with high probability, up to small corrections). The experiments vary the first term by altering $\\eta$, but the values of $K$ explored are very small - only $K = 3$ and $4$ are explored. This effectively means that the behaviour of the scheme with respect to the ground truth $K$ is left largely unexplored. (It is claimed that Fig 5.1 shows the behaviour with respect to $N_{\\min}$ but this is not the case - for instance, $N_{\\min}$ increases by a factor of $1.75$ when going for Fig 5.1 b) to c), but the threshold remains the same. I think what's actually being seen is the limiting effect in that the data aligns more strongly with the large graph limit as you increase $N$.)\n\nIn fact, the behaviour with respect to $K$ has twofold importance. First, it enters as a parameter of the threshold that is developed, and this needs to be empirically confirmed. Secondly, a critical issue in many community SBMs is the behaviour of the achievability thresholds as $K$ grows large relative to $N$ - for instance, for large $K$, the Kesten-Stigum theshold and the information theoretic thresholds separate, and a computational-statistical gap is conjectured for weak recovery. Thus exploring how the scheme empirically behaves as $K$ grows is of technical interest.\n\nMinor comment - in section 5.1, it might be worth explicitly mentioning that you set $\\tilde{d} = 3\\sqrt{\\log N}$ and vary $\\rho$ to make the average degree come out correct. Also, it would be valuable to explicitly show the threshold condition of Corollary 3.4 in terms of these new parameters.\n\n---\n\nOverall impressions:\n\nI quite like this paper. The problem is certainly relevant, and the analyses provided are the first, in my knowledge, to explore the sublogarithmic degree regime in the recovery of the number of communities in a graph with planted partitions with both theoretical and parameter-aware simulation studies. The method is interesting and well fleshed out.  I think the paper does have some flaws - most critically the empirical study with respect to $K$, and the issues I mentioned regarding Corollary 3.4 (which is a bit oversold as of now). These are the main bottlenecks in my current rating of marginally below acceptance. I can fully see myself bumping the rating to 7 if they are dealt with.\n\n---\n\nNitpicking:\n\n- Operators in mathmode should be escaped via ``````\\operatorname {XYZ}, which gives $\\operatorname{Diag}(A)$ instead of $Diag(A)$. Similarly \\min, \\max, \\log are available as mathmode commands, giving $N_{\\min}$ and not $N_{min}$.\n\n- I'm not sure that the line plots in section 5 are the best way to present this data, mainly because there are so few data points. I'm also not sure what should be used instead, so this is not totally constructive, but it may be worth exploring other ways (maybe just a table?). Also, i have no clue what CND.MTD.correct means.\n\n[1]: Banks, J., Moore, C., Neeman, J., & Netrapalli, P. (2016, June). Information-theoretic thresholds for community detection in sparse networks. In Conference on Learning Theory (pp. 383-416).", "extra_scores": {}, "extra_text": {}}, {"review_id": "KBRMIQVqPYq", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "I really like this paper. But there are a few questions that I have which are not clear to me. \n\n1)  What is the threshold for detecting if the number of communities K is 2 or more than 2? \n2) What does equation 3.3 mean? If the threshold is satisfied, then we can infer the number of communities? Should the threshold not depend on K?\n3) It is also unclear from previous literature if the work presented by the authors is incremental or not. I would like to see a paragraph explaining the main difficulties while proving these results given the previous work. \n\nHowever, this work has a number of pros\n\n1) The paper provides a very nice theoretical guarantee on when it will be possible to detect the number of clusters\n2) The algorithm and the theoretical lemmas are stated rigorously.\n\nCons\n\n1) I would have really liked to see a sketch of the proofs of the lemmas in the main draft. It would provide intuition on why the spectrum of the Bethe-Hessian matrix is used to determine the number of components.\n\n2) The authors have not discussed any lower bounds beyond which the number of communities cannot be detected\n\n3) Is it possible to detect the number of communities approximately? Surely, it would be possible to detect a single large community. Maybe the authors can discuss approximate detection of communities where failure to detect a community has a cost proportional to its size. \n\nBut I believe that the pros of this paper outweigh its cons and therefore I recommend acceptance.", "extra_scores": {}, "extra_text": {}}, {"review_id": "K6Bv__s0s65", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary\nThe authors propose a spectral framework using the Bethe Hessian matrix to infer the number of communities in sparse networks. The method relies on the eigendecomposition of the Bethe Hessian matrix for which negative eigenvalues are preserved and the number of such eigenvalues used to define the number of communities. In particular, theoretical guarantees for settings of the scalar of the Bethe Hessian matrix is derived including an associated spectral estimation procedure. \n\nPros: The procedure is very easy to implement and extends existing work to also operate in the sparse regime of d=o(log(N)) which is much more relevant and realistic from a practical perspective.\n\nThe manuscript includes nice theoretical contributions including proofs that the normalized Laplacian form of the Bethe Hessian preserves inertia, that the normalized Laplacian concentrates around its expectation, and bounds on the recovery of number of communities for suitable intervals of the scalar paramter of the Bethe Hessian matrix.\n\nCons: The k-means procedure is not guaranteed to identify the same clustering configuration each time and thus the robustness of the procedure hinges on the robustness of k-means (which is not particularly robust). That being said this is not specifically just an issue of this procedure but in general when using spectral approaches relying on a subsequent clustering step. It would be good to furher discuss robustness in regards to procedure 4.2.\n\nThere is a large body of literature on identifying the number of clusters for the SBM and several key references within Bayesian inference in this context is missing. This includes the non-parametric SBM called the infinite relation model considering sampling for inference\nKemp, Charles, et al. \"Learning systems of concepts with an infinite relational model.\" AAAI. Vol. 3. 2006.\nXu, Zhao, et al. \"Learning infinite hidden relational models.\" Uncertainty in Artificial Intelligence (UAI2006) (2006): 2.\nand variational inference.\nXu, Zhao, et al. \"Fast Inference in Infinite Hidden Relational Models.\" MLG. 2007.\nFurther work includes the use of minimum description length to quantify complexity:\nRosvall, Martin, and Carl T. Bergstrom. \"An information-theoretic framework for resolving community structure in complex networks.\" Proceedings of the National Academy of Sciences 104.18 (2007): 7327-7331.\nThe impact of the assumption that B in the stochastic block model is full rank and assortative is unclear. Typically in SBM there are no such restrictions and it would be good to argue for the validity of this assumption. Clearly, a very community structured network will be diagonal dominant and in general we can expect the rank to be full, but it would be good to clarify the impact of this assumption. The synthetic study is very simple including a within and between link density structure (two-parameters in the B matrix) – it would be good to elaborate on how the approach would work considering more complex structured B matrices.\nThe paper only includes synthetic analyses and it is unclear how practical useful the procedure is. It would strengthen the paper to also demonstrate the approach on real data and how community structures are inferred and differ from existing procedures in the real network regime.\n\nQuality\nThe paper is in general well written and clear. The mathematical derivation is non-trivial relying in particular on work by (Can M Le et al., 2017)  but the experimentation are somewhat lacking. The approach is solely contrasted existing procedures using the Bethe Hessian and not the large existing literature proposing various means to estimate the number of components within the SBM formulation including the literature also reviewed in the introduction. Furthermore, only a very simple synthetic dataset study is executed in which the SBM is restricted to a within community density and between community density for which the contrast $\\eta$ between within and between density is varied. It is therefore unclear what the merits of the present procedure is in contrast to existing methods for inferring the number of communities. It would strengthen the paper to consider also real networks for instance as in (Le & Levina, 2015) considering networks with “Ground Truth” (see also https://arxiv.org/pdf/1507.00827.pdf).\n\nClarity\nTo make the paper more self-contained it would be good to explain the structure of the Bethe matrix and how it is motivated as well as the role of the scalar parameter >1.\nMinor typos: \nexcellent excellent –> excellent\nI suspect line 3 in Procedure 4.2 should have Z 1_N -> Z^T 1_N.\n\nOriginality\nThe approach is based on results for the semi-sparse regime (i.e. average degree >> log(N)) but presently developed for the sparse regime, i.e. average degree = o(log(n)) with theoretical results for an interval of the scalar parameter used when specifying the Bethe Hessian matrix as well as a simple (spectral) algorithm to infer the communities and their number and a spectral procedure for defining an initial B0 matrix and community size vector N0 used to define plausible intervals for the scalar parameter of the Bethe Hessian matrix.\n\nSignificance\nThe paper extends the Bethe Hessian approach to the sparse domain and provides simple algorithmic procedures for inferring communities based on the spectral decomposition of the Bethe Hessian and a heuristic procedure setting the scalar for the Bethe Hessian according to an interval inferred through a procedure defining plausible estimates of the between community connectivity matrix B. The approach is only evaluated on very simple synthetic problems with very clear simple community structure not contrasting the procedure to any alternatives but approaches relying on the Bethe Hessian. As such, the significance and impact of the produced method is at this point very unclear and hard to assess. It is also unclear to what extend the results generalize beyond the synthetic experiments including an c_in and c_out link density to more general stochastic block modeling in which the B matrix has separate elements for each entry.\n\nIn summary, I consider the manuscript right around the acceptance threshold. The derivations are solid and sound, but the paper does not demonstrate the practical utility on real networks considering only very simple synthetic networks. This leaves me wondering if the approach would actually work in a practical setting and in particular, if the procedure for estimating the scalar interval based on procedure 4.2 can be used in practical applications. \n\n\n______________________________________ Updates in regards to the authors' response__________________________________________________________\n\nI appreciate the authors efforts to improve the manuscript and I think the manuscript has improved. I therefore raise my score to marginally above acceptance.\n\nIn the abstract computational efficiency is highlighted but from the response it seems the approach scales as O(N^3) this is not particularly efficient as many procedures such as conventional SBM can exploit network sparsity for computational scaling. I think stating the approach as efficient is somewhat misleading based on the response explicitly made to Reviewer #4. \n\nI appreciate the added synthetic analyses and that a real network analysis is included but I am somewhat disapointed that only one real network is considered as opposed to including a series of existing networks with ground truth community structure. I thus find that the experimental validation on actual networks could be further strengthened - but it is good to see a real result.\n\n\nMinor comments:\n\nWhen stating \"All of these approaches had theoretical guarantees.\" I believe this refers to some of the approaches discussed and not all. It would be good to clarify which approaches.\n\nestiamted -> estimated\n\nwhich also been used -> which has also been used\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "AhTU9STXRhQ", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "In this paper the authors consider the problem of computing the number of communities K in an arbitrarily sparse graph generated under the Stochastic Block Model (SMB). Previous studies that consider the problem of computing K show theoretical guarantees only in graphs with average degree $\\Omega(\\log n)$. One of the previous studies (namely, [1]) has shown that  the number of communities equals the number of negative eigenvalues of the Bethe Hessian matrix for graphs with expected average degree $\\Omega(\\log n)$ under SBM. In this paper the authors show that with an appropriate scalar parameter for the Bethe Hessian matrix of graphs with average degree $o(\\log n)$, the same property still holds, and thus obtain a method for computing K in graphs of sublogarithmic density. In particular, the authors give an interval for the choice of the $\\zeta$ scalar that depends on several parameters of the underlying SBM distribution.\n\nTo use this result in practice (i.e., to set the right $\\zeta$), one has to estimate the maximum expected degree of the underlying SBM distribution, the maximum probability of an edge, and the smallest eigenvalue of the normalized probability matrix B of the SBM. However, this is a non-trivial task, and the authors show that using estimates (with no guarantees) of B and the sizes of the communities they get reasonable estimates in practice and can thus choose a reasonable parameter $\\zeta$.\n\nFinaly, the authors compare their choice of $\\zeta$ with the one from [1] and show that on graphs with sparsity $3\\sqrt{\\log n}$ and sufficient assortativity the Bethe-Hessian-based method more frequently estimates the right number of communities. \n\n=================\nPROS \n+ The problem of computing the number of communities is important and relevant to the ML community, as most methods for computing the actual communities require prior knowledge of K.\n+ This is the first study to show theoretical guarantees in the sublogarithmic density regime in graphs generated by the SBM. As the authors stretch out this is an important practical scenario. \n\nCONS\n- The time complexity of the method and the estimation computation is not discussed.\n- Non-extensive experiments (K is set only to 3 and 4, and the average degree is set to a single value)\n- The right choice of the parameter $\\zeta$ is non-straightforward, and the authors suggest non-guaranteed estimations. That makes the theoretical guarantee of the overall method weaker, as one has no guaranteed way of tuning it.\nThe problem itself is well-motivated and the regime of sublogarithmic average degree is important, and typically real-world graphs fall under this category. \n\nThe presentation of the paper is acceptable, although I would like to see some further discussions:* Please add a formal definition of the problem and explain the connection of the number of the negative eigenvalues of the Bethe Hessian matrix and the number of communities. Unless I missed something, this is not discussed.* I think it would be beneficial to discuss the time complexity of the method. That would also support the claim about efficiency.\n\nThe choice of $\\zeta$ is non-straightforward. Recall that $\\zeta$ needs to be set right to enable the theoretical guarantees of the method. My understanding is that the authors rely on heuristics to estimate the right parameters and eventually choose the appropriate $\\zeta$. If there is no guaranteed way of computing the right $\\zeta$, then in practice one has no way to run the algorithm with guarantees. Please, do correct me if I'm wrong here.\n\nThe experimental section could also be improved. My main complaint is the very limited number of communities generated under the SBM. In particular, the authors only consider setting $K \\in {3,4}$, and this is not justified. Why not set K = 2, 5, 10, 50, 100 and show the performance (also compared to [1]) of the method as K changes? Also, it would be nice to consider different densities ranging from constant average degree to super-logarithmic. My understanding is that there is no upper bound on the densities supported by the method. \n\nOverall, I'm not enthusiastic about the paper because of the non-systematic way of choosing $\\zeta$, and because of the weak experimental evaluation. \n\nMinor things:\n* there are some hats flying around in Procedure 4.2, Line 4\n* \" expected expected degree\" in page 6\n\n[1] Can M Le and Elizaveta Levina. Estimating the number of communities in networks by spectral methods. arXiv preprint arXiv:1507.00827, 2015.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper describes a procedure for estimating the number of clusters in assortative sparse networks generated from a stochastic blockmodel, where the average degree scales sublogarithmically with the number of nodes. The approach proposed by the authors is based on the spectra of the Bethe Hessian matrix.

The article is well written. The reviewers raised a number of questions regarding the ad-hoc procedure for estimating the parameter $\zeta$ needed to estimate $K$, and the limited experiments. While the authors provided some additional experiments in the revised version, including on a real world dataset, the overall article stills appears to be too borderline for ICLR. Adding experiments on other real-world datasets would strengthen the paper. 

I recommend rejection.
Decision: Reject