Fitting Networks with a Cancellation Trick
Authors: Jiashun Jin
Jingming Wang
Venue: ICLR 2025 Poster (2025)
Keywords: Network analysis
DCBM
logit-DCBM
community detection
SCORE
Primary area: learning on graphs and other geometries & topologies

Abstract: The degree-corrected block model (DCBM), latent space model (LSM), and $\beta$-model are all popular network models. We combine their modeling ideas and propose the logit-DCBM as a new model. Similar as the $\beta$-model and LSM, the logit-DCBM contains nonlinear factors, where fitting the parameters is a challenging open problem. We resolve this problem by introducing a cancellation trick. We also propose R-SCORE as a recursive community detection algorithm, where in each iteration, we first use the idea above to update our parameter estimation, and then use the results to remove the nonlinear factors in the logit-DCBM so the renormalized model approximately satisfies a low-rank model, just like the DCBM. Our numerical study suggests that R-SCORE significantly improves over existing spectral approaches in many cases. Also, theoretically, we show that  the Hamming error rate of R-SCORE is faster than that of SCORE in a specific sparse region, and is at least as fast outside this region.

Published as a conference paper at ICLR 2025
FITTING NETWORKS WITH A CANCELLATION TRICK
Jiashun Jin
Jingming Wang
Department of Statistics Carnegie Mellon University Pitisburgh, PA 15213, USA binshwn@andrew cmu. edu
Department of Statistics University of Virginia Virginia, VA 22903, USA
pdw9qvévirginia.c
ABSTRACT
The degree-corrected block model (DCBM), latent space model (LSM), and 3- model are all popular network models. We combine their modeling ideas and propose the logit-DCBM as a new model. Similar as the 3-model and LSM, the logit-DCBM contains nonlinear factors, where fitting the parameters is chal- lenging open problem. We resolve this problem by introducing a cancellation trick. We also propose R-SCORE as a recursive community detection algorithm, where in each iteration, we first use the idea above update our parameter estima- tion, and then use the results to remove the nonlinear factors in the logit-DCBM so the renormalized model approximately satisfies a low-rank model, just like the DCBM. Our numerical study suggests that R-SCORE significantly improves over existing spectral approaches in many cases, Also, theoretically, we show that the Hamming error rate of R-SCORE is faster than that of SCORE in specific sparse region, and at least as fast outside this region.
INTRODUCTION
Community detection is problem of major interest in network analysis (e.g., see (Goldenberg eet al. 2010)), a survey paper). Consider an undirected network with n nodes and K communities Ci, C2...., CK (a community is a group of nodes with similar behaviors). Let E IR be the adjacency matrix, where Aij = 1 if and only if there is an edge between node i and j. 1 S i i n. Conventionally, do count self edges,
A, 0 if j. As in many works on community detection (e.g.. Chen et al. (2018); Zhao et al. (2012): Yuan et al. (2022a)), we assume that each node belongs exactly one the K communities. For each S 2 S n. we encode the community label of node by K K-dimensional vector æ; (which is unknown to us) such that
n3 Ek if and only if node E Cs
(eg: k-th standard Euclidean basis vector of RR
(1)
The goal of community detection is to use (A, K) to cluster all n nodes into K communitiis//roups.
The degree-corrected block model (DCBM) Karrer & Newman 2011) is a popular network model. Suppose we a free parameter 0 to model the degree heterogeneity of node i, 1 S S n. For a non-negative matrix P E R.K.K DCBM assumes that the upper triangular entries of A are independent Bernoulli variables satisfying
P(A.; =) 0,0,m,
log(P(Ar.) = 1)) log(0.) + log(0,) + x(Qm,,
(2)
where Q is a K matrix such that Q = logg( entry-wise. When all 0; are equal, DCBM reduces to the well- Stochastic Block Model (SBM) (Holland al. 1983). Note that as 0 < P(A 1) < 1, so implicitly, DCBM has imposed a set constrants on its parameters:
log(0.) + log(0,) + R,QT < O, 15 n.
(3)
These constraints make an already complicated setting even more complicated, so we desire to remove them if possible. Also, if the matrix Q is positive definite, then Q = U'U for a matrix U E KK, In this special case, we can rewrite 2 as
log(P(AAg) 1)) log(O.) log (0g(0) + 2/23,
where 2; Um, í S

---

Published as a conference paper at ICLR 2025
The latent space model (LSM) (Hoff 2005) and the 3-model (Chatterjee al. 201 are also pop-
ular network models. Denote the logit function by logit(æ) log x/ |
d) 0.0- < x
< 1. In
representative form, for so-called latent positions 21..... . Zn E R the LSM assumes
logit(P(A,, = 1)) = log(O.) + log(0,) z/zz.
(5)
Compared (5) with ( the only difference the log-link is replaced by the logit-link, so at least in the special case where Q is positive definite, two models are similar. Also, if we drop the 2/2; term on the RHS, then (5) reduces to the 3 model (where we only have one community, i.e., = 1).
However, despite the similarity, to many statisticians, (5) is highly preferred. The main reason is that, for binary data, the model recommended by textbooks is the logistic regression model (e.g., (Hastie et al., [209] Section 4.4) and Dobson & Barneti (2018)). where the logit-link function was argued to be the most natural. Additionally, some popular Python packages, such as scikit-leam, frequently use the logit-link function. In fact, in the LSM case, since IPgit = 1)) can take any values in (-o0, oc), we do not have the constraints (see (3) as the DCBM case.
To combine the modeling ideas of all three models, we propose the DCgit where we assume
logit(P(A.,) = 1)) (o, + (0,) + T(QTH, with Q = log(P) entrywise as above. (6)
as in the DCBM case. Also, we can view (6) as an extension of (2). Moreover, since we do not require Q to be positive definite
Since we use the logit-link function, we do not need the constraints
in so also extends 5 to broader setting. Last. reduces to the 3-model if we let Q
In summary, we propose the logit-DCBM as a nonlinear variant of DCBM so hopefully it is more broadly acceptable, especially for researchers with a strong preferences in nonlinear network models (such as the LSM) and in using logistic regression type model for binary data.
We now rewrite the logit-DCBM in the matrix form. Note that under the model, P(Asg = 1) 11 is nonlinear term. Let N (N₂)). ). θ (n) E RT." and II = [T]..... nTpl For any matrix Q E R".." let diag( E R be the diagonal matrix where the k-th diagonal entry is Ωkk- Let W IR.. be the matrix where W; = A. B[A,y] if i o j and Wij = O otherwise. Let denote the Hadamard (or entry-wise) product (Horn& & Johnson 1985). Under the logit-DCBM model
Ni 0,0,TTPPT where No. = [1 + P,T
diag( (f..... ......,..
(6
A = Ω - diag(() + W, with Ω = N á and ② = OTPPI'..
(7)
Note that rank K, but due to the matrix of nonlincar factors N, rank(!?) may be much larger than K. For this reason, (7) is not a low-rank model in general.
Remark 1. Since Núj R when 0 PT; R O one may think that the DCBM and logit-DCBM are close to each other. This is not true. First, 0.0ym(PT, are not necessarily small for all í, Second, even if J2 and N o l2 are close in each entry, their spectra and norms can be very different.
Literature review and our contribution. The logit-DCBM (and all other models mentioned above) are so-called latent variable models, where II is the matrix of latent variables. For latent variable models, the EM algorithm (e.g.. Dempster et al. (1977) a well-known approach. However, EM algorithm is computationally expensive, lacks of theoretical guarantee for high dimensional setting as we have here, and does not perform well when the networks are sparse. For network data, pe- nalization approach is popular, and in the DCBM setting, there are many interesting works (e.g., Chen et al. (2018); Zhao et al. (2012)) However, since the DCBM is a latent variable model with many unknown parameters, these methods usually involve non-convex optimization, where good initialization is crucial. Also, penalization approaches are usually computationally relatively slow and hard analyze. We can extend these approaches LSM (Ma & Yuan 2020) and logit-DCBM, but due to the nonlinearity in LSM and logit-DCBM, these issues persist.
For these reasons, spectral approaches for network data are especially appealing. Compared with EM algorithm and penalization approaches, spectral approaches are conceptually simpler, computa- tional faster, and also easier (at least for the DCBM) to analyze. In the classical spectral approach,
we cluster by applying k- k-means to the n rows of the matrix é = .f....., Ek]. where Eμ is the k-th eigenvector of A. However, due to frequently observed phenomenon of severe degree heterogeneity in network data, such an approach frequently performs poorly. To fix the problem, (Jin) 2015) pro- posed SCORE new spectral approach. In the DCBM setting, SCORE was shown to have fast
.is.....xk
2

---

Published as a conference paper at ICLR 2025
convergence rates (e.g., Jin ) Jin al. (2021b)) Also, in survey paper (Ke & Jin 2023 SCORE was compared with many algorithms on many real networks, where it was shown to be competitive in real data performances.
Motivated by these, we wish to extend SCORE to our setting. The challenge is, the success of SCORE eritically depends the fact that the DCBM is low-rank model, but unfortunately, the logit-DCBM is not a low-rank model (see above).
We adapt SCORE to setting by proposing the Recursive-SCORE (R-SCORE): we initialize by possibly crude estimate for II (denoted for Îi), and then use A and II to estimate N (denoted by N). We then update A by A Ø N (Ø denotes the entry-wise division) and repeat the above process for a number times. The main idea here that, if Ñ R N, then A 2 N ~ A @ N Ω - ( + W @ N, where the RHS is low-rank model (recall that rank (St) K).
The challenge is, how estimate N is a difficult problem, even if II is known. In fact, when II is known, we can restrict the network to each of the K communities, where within each community, the logit-DCBM reduces the 3-model (which a symmetrical version of the p1 model (Holland & Leinhardt 1981)). How to estimate N in the 3-model is a well-known open problem, as explained the survey paper (Goldenberg et al.] 2010) (see also Rinaldo et al. (2010): "A major problem with the pı and related models, recognized by Holland and Leinhardt, is the lack of standard asymptotics, we have no consistency in results for the maximum likelihood estimates".
We tackle this with a cancellation trick. Construct two types of cycles. For each type, the expected cycle count is a big sum of many terms, where due to the matrix of nonlinear factors N, we can not derive simple expression. Fortunately, in the ratio of the two big sums, the nonlinear factors in one big sum cancel with those in the other, and the ratio has a simple and closed-form expression.
Therefore, if Il is known, then the idea gives rises to simple and convenient way to estimate N. Note that this also solves the open problem for the 3-model aforementioned. In our case, II is unknown, but we can first obtain a possibly crude estimate 11, and then use II and the idea above to obtain an estimate N for N. We can then repeat the two steps as in the R R-SCORE.
As many recent procedures rely on low-rank network model, the above idea is not only useful for adapting SCORE to our setting, but is also helpful in adapting other ideas (e.g., those on global testing (iin al. 2021a) and on estimating K (Jin et al.) 2023)) to our setting.
Remark
It remains to analyze SCORE and R-SCORE for the DCBM model. Note that while the Ham- ming clustering error of SCORE was analyzed before (e.g.. Jin (2055); Jin et al. (2021b)), but the focus were on the simpler DCBM model, where the analysis critically depends
that the DCBM is a low-rank model. Unfortunately, the logit-DCBi is not a low-rank model, so it is unclear how to extend the results in Jin (215)); Jin et al. (2021b) our setting. Note also that R-SCORE is new algorithm, and has never been analyzed before.
For any community detection procedures, we measure the performance by the Hamming clustering error. In the logit-DCBM model, we can always write
A ì + (N - ,,, - ă dia + W,
where π is a low-rank matrix,
and (N - 1,11) o ŋ can be viewed as a non-linear perturbation of Ω. We show that the Hamming error rate of SCORE is upper bounded by
()) + I[(N - 1,,1,) & (Ω))
This is the first time we derive a bound for the Hamming clustering error of SCORE for nonlin- ear network model. Compared with existing works on DCBM (e.g., Jin et al. (202aa) la 2023) ) the analysis is quite different.
The Hamming error of R-SCORE is much harder to analyze, for many reasons. First, R-SCORE is recursive algorithm, where the next step depends the pervious one. Second, Ñ (the estimate for N) is a complicated nonlinear function of A, which depends not only on the clustering errors in the previous step, but also the cycle count step aforementioned (where the analysis is non-standard).
Fortunately, we manage to derive an upper bound for the Hamming error rate of R-SCORE. To save space, consider special case here, leaving more general cases Section 3.1 Consider the
3

---

Published as a conference paper at ICLR 2025
special case where for all 1 < i i cun cun < 0 I cin where 3 E (0, 1/2) and 01 > co 0 are constants. In this case, the Hamming error rates of SCORE are R-SCORE are upper bounded by On (n) and n -a (9), respectively, where
ao (3 = min (1 - 2,3), a1 (3)
min 28), 63), and a (8) > (3 when 3 < 1/6.
Therefore, when 0 < < < 1/6, the rate of R-SCORE is faster than that of SCORE, and two rates are the same when 1/6 < 8 < 1/2 (the interesting range of 33 is 0 < 3 < 1/2; when 3 > 1/2, the signal-noise ratio so low that no procedure could succeed).
We have the following contributions: (a) propose the logit-DCBM 3-model, and DCBM, and as a more appealing network model, (b) introduce a cancellation trick and use it to solve open problem for the 3-model, as well as for open problem for the logit- DCBM in the idealized case where is known, and (c) propose R-SCORE as recursive approach to community detection with the logit-DCBM, (d) for the first time, we derive upper bounds for the Hamming error rates of SCORE and R-SOCRE for the legit-DCBM (which is a nonlinear network model), and (e) show that the rate of R-SCORE is faster than that of SCORE in specific sparse region, and is at least as fast outside the region.
extension of the LSM,
In summary, we propose the logit-DCBM as a nonlinear variant of DCBM, will be more broadly accepted. The nonlinear factors make the logit-DCBM harder to fit, but with a cancellation trick, we can successfully convert the model back DCBM approximately, so we can continue to enjoy all nice properties the DCBM has. We also propose R R-SCORE as fast spectral approach where the error rate is faster than that of applying SCORE directly to the logit-DCBM.
Content and notation. Section 2 introduces the cancellation trick. Section 3 introduces the R- SCORE algorithm and theoretical analysis. Section | contains some numerical study. Section discusses connections to other problems. In this paper, and @ denote the entry-wise product and division, respectively. For 1 S S K, we use eg to denote the k-th standard basis vector of I For any > 2, In denotes the For any two sequence of non-negative numbers {a,} } and {b,.), we write a, > b, if b,/aa, = o(1) (similar for a, < b,,), and write an x b,, if cub, I an S c1b, for some constants C₁ co > 0. We use C to stand for a generic constant, which may vary from one occasion to another.
identity matrix and 1,, E In" denotes the vector of all ones.
2 AN IDEA FOR CANCELLING NONLINEAR TERMS IN BIG SUMS
We introduce the cancellation trick by considering two seemingly new problems. Although it seems digression from our original purposes, the two problems are interesting in their own right, and provide the foundation for the refitting step of R-SCORE below. Consider the first problem. Suppose have matrix A R21 with independent Bernoulli entries, where 2i P(A., 1)
No.N,,0:0 xo > 0, 0, > O, with Ni; [1 + xg0:0,1 Here, O; are known but zo is not, and the interest is to estimate 2g. We may estimate zo by the maximum likelihood estimate (MLE), but does not have closed form and may be computationally slow,
desire new approach.
Lemma 2.1 We have (7) = (IT), where (T) === Eis
i Pig and (IT) = Ens 0,0, -ta))
Proof. As (T) xo En, N,,0,0, and (TT) = =E., Ne50:0, the claim follows. D
The key is, due to the non-linear terms Noz. it is hard to derive a closed-form formula for (7) or (II), but by our careful design, the ratio of (I)/(I) has a very simple form. Now, to estimate Tp, let (1) Em Eイ Aij and wi??)
0,0 A.y). By Lemma 2.1 zo =
Bly 11/P1/EE w1 so convenient estimate for 2y is (note: the computational cost is ((nn2)))
ig = - ////////)))
(10,(1A4))
(8)
i=1 :=1==
1=1
Consider the second problem. Suppose we have a network adjacency matrix A E RP satisfying the 3-model. That is, the upper triangle of A are independent Bernoulli satisfying 24j P(A. 1) N,,0,0, where N1, [1 + 0 1-,]]____ 1 i # S n1. The parameters 0, > 0 are unknown and the interest is to estimate them. Due to the nonlinear terms Nıj. the problem remains a difficult open problem in the literature, where classical approaches such as the MLE face grand challenges (e.g..
4

---

Published as a conference paper at ICLR 2025
Goldenberg et al. (2010); Karwa & Slavković (2016): Rinaldo et al. (2010)). We propose new approach, motivated by the following lemma. For any S n2. let
n2 11,
{i}.
Lemma 2.2 Fix an odd number m 3. We have (dist below stands for distinct)
Eig...imes (dist) ii - Rigiz) I. 24m (1 S2n 18 ) 1i
= 0., (9)
Σ Lig (dist) (1 Sigze )Rigis ... (1 S2 1-m-2im-1 )S2 j52mm-m 1 18m (1 Q2 {immis)
Proof. Note that
Disia (1 - ligis).... ... Iem 2 11m-22m-110 - Sm Mimi = Ni Nigis Nem. 02, 0ig Osm
(1- (Rini))iigig ... (1 Aim--im-1 10:-2immm)m0 100 )0mm
Pimin) = Ni,i ... Nim. 0i 6i...
Comparing the RHS, the only difference is the term 02. Since on both the numerator and denomina- tor of (9) the sum only over 22, .3,..., im with i being fixed, the claim follows. D
Similarly, due to the non-linear terms Naj. it is hard to derive a closed-form formula for both the numerator and denominator of (9). but by our design, the ratio in (9) has very simple form. Let
on (41 -iier..hm ES,, (dist) Asj (1 - -igig) Aim-zim- - Aim-mmm) 18m Aimis and @n.m (i1)
Cam.tmmeuu.. (dise) (1 Ai,is Aigis ... (1 Aim-2im- ) Aim-iiin km (1 A ). By Lemma 2.2
E Blomm(h) (f1)
Exgiittess ES,, 84 12 Dizia) ... m2m- (1 Q - im P
87,
(2) Blo (f1)
Enginnde ES,, (1 Peets ... 1mm 1m bm (1 Demis)
Therefore, a reasonable estimator for 0g is 0r. = v on (f (b)) This solves the open problem aforementioned (see also Section 3). Especially, we may take m = 3 and estimate 0 by
EyMess.ir
A A₁x)
0. = = 2o 00/00/000000 V Ee A55 Aka)
(10)
Alternatively, we may a larger m, but the numerical performance is similar, while the analysis is much longer. For each fixed m, the computational cost is ((?dd) (c.g., Jin et al. (2021a)), where d is the maximum node degree.
Remark 3. Lemma 2.2 is readily extendable. For example, if there are positive functions g and such that gf22,)) 8,6, n. (Sa)( for all j, then similarly
E ES,, (diat) Lig Es. (diet) h h(2,, (R4 h(94mmmmmmmm)
(1 .... .....g((...... 900mmm2m0mmmmmmmm 1h0 (a(2 )g (9(
0
In summary, the two problems above (especially the second one) are difficult. In these problems, the quantities of interest are hidden in some big sums. Due to the nonlinear factor Ni. it is hard to derive closed-form formula for such big sums. However, if we can carefully construct two big sums, then we can cancel the nonlinear terms N;j by considering the ratio of the two big sums, and derive a closed-form formula for the quantity of interest. Such a cancellation trick gives rises to a convenient approach solving the two problems above, and is readily extendable to many other settings (e.g., analysis of the pl model for directed networks Holland & Leinhardt (1981), analysis Yuan et al. 2022b)).
of tensor and
Below in Section 3 we introduce R-SCORE as a recursive algorithm, where the ideas above play key role in the refitting steps of R-SCORE. For space reasons, we defer the analysis of the above idea (i.e.. st and 0,) the supplement: see Sections C.2-C.3 of the supplement for details.
COMMUNITY DETECTION BY R-SCORE FOR THE LOGIT-DCBM
We propose Recursive-SCORE (R-SCORE) for community detection, where the key is to the ideas above in the refitting step; see Algorithm ( The number of iteration is not critical, so we set M 10 (R-SCORE typically converges in very few iterations). In each iteration, R-SCORE
5

---

Published as a conference paper at ICLR 2025
consists community detection step by SCORE (the SCORE step) and refitting step. We choose SCORE for it is fast, competitive in real data analysis, and with fast error rates (e.g.. Din (2013): ): Jin et al. (2021b)), but we can also view our algorithm a generic algorithm, where SCORE by any other community detection approaches that are provably effective for DCBM.
replace the
We now discuss the SCORE step and refitting step of Algorithm [ in detail. Consider the SCORE step JJin 2015) first. In this step, for an imput matrix or A Ø N, let f...... mK be the first K eigenvectors, and let R [E2/E1,.... /k/Li,, where E/n denotes the vector of entry-wise ratios. We cluster by applying the k-means to the n rows of R, and let n; be the estimated community label of node i. Let IT [#1...., #n/. Note that क takes values in 61, C2,..... CK (ex: k-th standard basis vector of k)
Algorithm The Recursive SCORE (R-SCORE)
Input: A and K. Initialize with an estimate II by SCORE. For m = 1,,,..,,M
Refitting. Update Ñ using A, Πi in the most recent step, and the refitting step below. SCOOE.. Update Il by applying SCORE A Ø N with the most recent N.
Output: [1= :
Consider the refitting step. Let II . #n] be the estimated 11 in the current iteration. Recall that even in the idealized case of fī II, refitting (i.e., how to estimate N) is difficult and open problem. We tackle this with the idea in Section 2 In detail, let C = {1 < < n क. = ex} be the k-th estimated community, S l < K, and let Sk. = Cx \ {i). By Lemma 2.2 and especially 10 we propose to estimate 0g by
0.
Σ S
A15(1 AR))
(1- (1)))) Aa))),
if E C
(11)
S
This corresponds to the case of m of our idea in Section 2 but we can also use a larger m. Also, inspired by Lemma 2.1 we can estimate the matrix P by
Prr I Aus/
ΣEO 00,0,(1 - As))),
IskesK.
(12)
iEc JEC
To appreciate the idea, consider the sub-matrix of A by restricting the rows and columns to C2 and C₁. In the idcalized case where 0: = 0, and CN = Cs. 1 < < n, 1 < k < K. the mean of the sub-matrix satisfies the condition of Lemma 2.1 2.1oof of Section This gives rises to the estimates above. Finally, we update our estimate of by letting N., = (1 + 0,0, Pke) if C₂ and E C..
Note that by the discussion in Section 2 the computational cost of the refitting step is no more than O(n2d), where d the maximum node degree. As a result, the computational cost of R-SCORE is no more than (n)d))
Remark 4. One may want to replace the refitting step by a simpler step, but how to do so remains unclear. Recall that when II is known, how estimate (o, P) is challenging problem (e.g., Goldenberg et al. 2010); Karwa & Slavković (2016); Rinaldo et al. (2010)).
3.1 THEORETICAL RESULTS
For any community detection procedure, let îî be the resultant estimate for II, where each row of fi takes values in {el, "2,....,,k, We measure the performance by the Hamming error rate:
Yn (i) min Σ 1(f = Pmr),
where P is any permutation in (1.2....,AA) K}.
n
Let score and scoore be the îl for applying SCORE and R-SCORE to the adjacency matrix A.
Note that under the logit-DCBM model,
A Ω (i-aiag)))+ W, where Ω No Ω. ñ OTPPII and P has unit diagonal entries. (13)

---

Published as a conference paper at ICLR 2025
The last item is well-known identifiability condition (Jin et al. K' is relatively small, so we suppose that K is fixed (this is only for technical simplicity and can be relaxed). Let ni be the number of nodes in the k-th community, < l S K. We assume
2023). Since in most real networks,
min(n+} Com, for some constant 0 < co 1/K.
(14)
This is a frequently used and mild balance condition among the K communities (e.g.. Jin (2015); Jin et al. (2021a)). Also, we assume that there exists constants 2 0 such that
0+0,
and c, S 0, S c20 for all 1 S i S nt,
where 0 = - 0z/n.
(15)
This condition is also only for technical reasons, and can be largely relaxed. Furthermore, we assume there exists an constant C3 > 0, such that
vno Amin (P) 2 eg log(n),
Amin (P): smallest eigenvalue of P in magnitude.
(16)
In the special case where satisfies a DCBM, S S2 and SCORE was analyzed before (e.g.. Jin 22015); Jin et al. (2021b), where it is known that the signal-noise ratio (SNR) is given by
[A /A) (92 (AA ($2) and ( represent the signal and noise level respectively). In order for the Hamming еπто rate of SCORE tends to O, it is necessary that the SNR - OC. Condition
(6) is necessary for otherwise the SNR may tend to Also, here Amin (P) measures community dissimilarity. In the special case of P = bl 1K + (1 bb 0 < b < 1, Amin
b
Therefore, if Amin (P) + O, then + 1, and all communities are very similar. Condition (66) defines class of weak signal settings where the problem of community detection is challenging. Lastly, consider III Let be the first right eigenvector of PII' we assume that 17 is a positive vector and
(PPI''01))) (A(('I)))))) (IT'''I)))
max (i)/ i mi) Sc (17)
This condition is necessary to guarantee that the first eigenvector is well-separated from the others and the SCORE normalization by the first eigenvector is well-defined, since the reciprocal of each entry of the first eigenvector cannot blow up. It is mild condition by Perron's 's theorem on non- negative matrices. Similar condition can be found in Jin et al. (2023).
Note that while SCORE was analyzed before for the DCBM, it was not analyzed for the logit- DCBM, where the analysis is expected to be much harder. In the logit-DCBM, we have Ω (N--111)) f2. To avoid that the nonlinearity completely ruins the low-rank structure, need
II(N - 1,)1, o [))1l/Ax (f2) + 0;
(18)
Recall that SNR = |Ax (1)) The following theorem is proved in the supplement.
Theorem 3.1 Let Necove be the resultant estimate for II when we apply SCORE directly to A and
suppose 14 17 and (18 hold. With probability 1 o(n-3)
Tn scooe)) S <C[II(N- 1,,1,) 01 (1)0)
In the special case where A satisfies the DCBM, N = 1,,1, and rn (fi I (X)
Next, consider R-SCORE. Since R-SCORE is recursive algorithm, it is useful to present result that is applicable in general cases. Consider an estimate for π the form of 2 By our construction, No 1/(1 + D.y). Suppose that with probability 1 o(n-3),
éúPi'..
| mlamax max < min (1, AAiin (P)
||î III[(V (Pm) 0,
(19)
and
O - 1,,1 o U1| of Ax ()),
(20)
The following lemma is proved in the supplement.
Lemma 3.1
Suppose 14 (4)-17) hold. Let î be the result of applying SCORE to A 1 Ñ where 19 20 and 0g C0 hold. With probability o3n-3),
CII(NN 1,1, o 2112 + T 21
where TA (ni0'\ -P max + | II].
(9)
7

---

Published as a conference paper at ICLR 2025
We show that (19 20 hold in many settings. Our numerical study shows that R-SCORE typically converges in just one iteration, so for convenience in analysis, we consider R-SCORE with one iteration from now in this section. Write for short 6n max(]I(N 1,11,) @11 (1)) (ft). Theorem 3.2 is proved in the supplement.
Theorem 3.2 Suppose 14/-17 17 hold and 6n/ min 0l>min (P),, Amia (P))2 0. Ler
cirscore be the estimate for 11 by applying R-SCORE to A, and let (θ, P. N) be the correspond- ing estimates for (O, P. 92, N) in the refitting step of R-SCORE. We have that 19 (20) hold and that with probability
o(n "),
I' ( S
C
(Ai( + n0 log(n) + 0200 + n200
X (S2)
Corollary 3.1 Suppose 14 17) hold, 1imin 2 C for constant C O, and n0* +
Let [Iscore and IIrscore be the estimates for 11 by applying SCORE and R-SCORE the adjacency matrix A, respectively. With probability 1 on
I' (ffccor)) SC
1 + + n22
Tn (IIrec
S CC
1 0 log(n) n2f2
n
With more careful analysis, we conjecture that the condition of not can be removed, and the rate of R-SCORE is at least as fast as that of SCORE in the whole range of interest (note that the proof of Theorem 3.2 and Corollary 3.1 is already hard and relatively long). If we calibrate 0 = n - for constant 3 > O, then in order for the SNR
(e.g., see (18), we must have 0 < B < 1/2. In this
range, n, (11) < Cn ao( and Fr (11 I O'n (3)) where
48, - 28, 1/6 < 3 1/2, (o( {
0 0<B51/0
63,
0< < 1/8, 1/8 < 3 < 1/6, 1/6 3 < 1/2.
(1
(1-23)
(1- (1-28),
Figure 1 Therefore, when 0 < 8 1/6, the Hamming rate of R-SCORE is faster than that of SCORE. When B > 1/6 1/6, such conclusion may also be true, as the current bound may complicated data dependent matrix Ñ, and the error bound can hopefully be improved with more careful analysis.
be conservative: the Hamming error rate for R-SCORE depends
Remark 5. The proof of Theorem 3.2 and Corollary 3.1 is hard, for N has complicated form: recall that No = 1/(1 + 24y) and l = θПPП'S, where Îl is the SCORE estimate for 11, and (θ, P) are constructed using ÎT, A, and a cancellation trick. Note that even when IT is known, how estimate (o, P) is a nontrivial problem and we resolve it with a cancellation trick.
afp)
(,(
3/4
2/3
ag(fi)
1/8 1/6
1/4
1/2
Figure 1: Comparison of error rates (z-axis: B. y-axis: (B) (blue) and a₁ (3) (red))
4 SIMULATION RESULTS
We compare R-SCORE with SCORE and a non non-convex penalization Mas-based approach by MMa
al. 2020), which refer to npMLE. We compare with npMLE for (Ma al. 2020) deals with
8

---

Published as a conference paper at ICLR 2025
the LSM and is probably the closest related work to our paper. Our study contains 3 experiments. In Experiment 1, we compare R-SCORE with SCORE (which is viewed as a benchmark). In Exper- iment 2, we study how the error rates of R-SCORE and npMLE change across different iterations (both algorithms are recursive). In Experiment 3, we compare the errors of R-SCORE and npML..
Experiment 1. R-SCORE vs. SCORE. The networks are simulated as follows: fixing (n, K), we first simulate an n. x n matrix Q as in the logit-DCBM model as follows. Let P = 31 k + (1 B)Tx where n. e for no n/K different (recall that e& is the k-th Euclidean basis vector of IR ). Moreover, fixing a parameter 6, > O, we generate 0 as follows. We first draw 8f. 82. ....... 6% i..d. from fixed distribution F(-). and then renormalize 6, to get 0. = b, 0 for 1 S i S n. Finally, we let Ω = @11P11' and 22 = 22 + Psy), 1 1 1, n. Once we have such matrix ft use it to generate binary adjacency matrix A.
and II [T], ........ ................................ nn.
In such settings, approximately, the Signal-to-Noise Noise ratio (SNR) is b,,(1 - B) (e.g., see J et al. (021a)). It is desirable to choose settings that the SNR is neither too large too small. Con- sider four settings (A); (B), (C) and (D). In Setting (A), we fix (n, K) = (2400, 3) and F = Uniform(0.01,22 2). We choose bn 60 and 3 23/30 (and this way, SNR 14). In Setting
(B), we fix (n, K) = (2500, 5) and F == Uniform (0.1. 0.8). We choose bn 70 and 8 = 0.65 (and so SNR 24.5). In Setting (C), we fix (n, (n)
(2400, 3) and F = Pareto(10, 1). To avoid ex- tremely severe degree heterogeneity, we truncate each 67 at 200. We choose b,, 70 and B = 0.55 (and this way, SNR = 31.5). In Setting (D), we fix (n, K) (2500. 5) and F Parcto 1) with truncation at 100. We choose b,, = 50 and 3 = 0.55 (and so SNR = 22.5).
The results are in Figure [] where the z-axis is the # of iterations m, and the y-axis is the corre- sponding error rate by R-SCORE (green dashed line: error rate for R-SCORE with m = O, same as that of applying SCORE directly to the adjacency matrix A). In all settings above, the performance of directly applying SCORE (m 0) is unsatisfactory. The improvements achieved by R-SCORE are significant, with substantially reduced error rates. This suggests that (a) the R-SCORE is suc- cessful expect, and (b) the iteration algorithm typically converges in very few iterations. Based on the numerical results, we believe that the refitting procedure steps in R-SCORE are effective: by re-normalization, they reduce the logit-DCBM model approximately
low-rank model.
Experiment 2. Error rates of R-SCORE and npMLEE E in different iterations. Fix (n, K) = (5400, 6). Let TT be generated similarly to Experiment except that n; 6 for nik different Let P P1
P2
where P1 0.533 12/2 + (1 0.53)) k/2 and P. = 0.5(31 + (2) k2222/ Pi
P2
We generate 0, in the same manner as in Experiment and similarly construct Q and 12 to gen- erate a binary adjacency matrix A. In this experiment, we choose (n,, (2,, .gx) = 200 (5, 1.5, 6, 3. 7.5, 4), F Uniform(0.01. 2). b, = 80, and (8,, 82) (0.9, 0.6). Under this set- 1,2..... ... 1000, we apply R-SCORE
ting, the SNR is given by bn./ [P)] = 28. For each and npMLE with m iterations (SCORE is also included for comparison, which is the same as R- SCORE with m 0). The result is in Figure (left). We observed that (a) R-SCORE converges much more rapidly than the npMLE, and (b) the error rates of R-SCORE is significantly lower than that of SCORE, and is slightly lower than that of npMLE.
(0)
[BI
022
0.00
9-50006
276
085 0:0
13-
Steration
Deration
Figure 2: The error rates of R-SCORE for different m (# of iterations). See Experiment for setting details. SCORE is also included for comparision as a benchmark, which corresponding to R-SCORE with m = 0 (r-axis: m; axiiis: error rate).

---

Published as a conference paper at ICLR 2025
Experiment 3. R-SCORE vs. npMLE. Consider the same setting in Experiment 2, but we let Ba vary: we set b, = 30 and let 32 range from 0.58 to 0.7 with a step size 0.02 (other parameters remain the same). The SNR of the simulated network hinges on the smallest eigenvalue of P. which in turn hinges on $2. The results (based on 20 repetitions) are in Figure 3 (right), which suggest that R- SCORE steadily outperforms npMLE for 32 in the entire range. Also, R-SCORE is much faster than npMLE. In each repetition, it takes R-SCORE only 6 seconds, whereas it takes the npMLE more than 300 seconds (more than 50 times longer). This shows that R-SCORE not only significantly faster than npMLE, but may also outperform the npMLE in many network settings.
R-SOOF
GALLE
Enoi
140
Hanatorottgg (2)
Figure 3: Left panel: The error rates by R-SCORE and npMLE for different m (# of iterations). See Experiment 2 (x-axis: logio (m). y-axis: error rates). SCORE is also included for comparison, which corresponds to R-SCORE with 0. Right panel: The error rates by R-SCORE and npMLE for different B2. See Experiment for setting details (z-axis: 32: y-axis: error rate).
DISCUSSION
In this paper, we have made three-fold contribution to the area of network community detection. First, we propose the logit-DCBM as a new network model. We argue that the logit-DCBM is more reasonable than the popular DCBM, but also poses challenge. Second, to overcome the challenge, we propose a trick that can effectively cancel the effect of the nonlinear factors of the logit-DCBM model in some statisties (especially the ratio of two cycle-counts). Last, we propose R-SCORE as a new algorithm for community detection, and show that it can significantly improve over existing spectral approaches including the SCORE. Our idea generalizable to many other settings. For example, the p1 model by Holland and Leinhardt Holland & Leinhardt [198]) is one of the most popular models for directed networks with community. Following the idea here we can generalize it to model with multiple communities, and extend R-SCORE for community detection with the new model. Also for example, the cancellation trick can be extended to many other settings (e.g., analysis of the pı model for directed networks Holland & Leinhardi (1981), text analysis Ke et al.) 2023), tensor analysis Yuan al. (2022b)) where the data matrix A satisfies E[A] N Q for simple low-rank matrix and matrix N consisting nonlinear factors. Given that nonlinear models become increasingly more important in statistics and machine learning, the trick (and its extended form) may find increasingly more uses in many applications in the near future.
The cancellation trick is especially useful. In machine learning, we have many nonlinear latent variable models spreading many areas (e.g., cancer clustering (Jin & Wang 2016), text analysis (Ke & Wang 2024), and empirical finance). Due to the nonlinearity, how to analyze such models is a challenging problem. In this paper, we propose an interesting cancellation trick using which we can effectively remove the nonlinear factor in some latent variable models. For space reasons, only showcase this trick with a network setting, but the idea is extendable to other nonlinear latent space models. For this reason, our work may spark new research in many different directions in machine learning.
REFERENCES
Sourav Chatterjee, Persi Diaconis, and Allan Sly. Random graphs with a given degree sequence. Ann. Appl. Probab., pp. 1400-1435, 2011.
10

---

Published as a conference paper at ICLR 2025
Yudong Chen, Xiaodong Li, and Jiaming Xu. Convexified modularity maximization for degree-
corrected stochastic block models. The Annals of Statistics, 46(4):1573 - 1602, 2018.
Arthur Dempster, Nan Laird, and Donald Rubin. Maximum likelihood from incomplete data via the em algorithm. J. Roy. Statist. Soc. 39(1):1-2,, 1977.
Annette J Dobson and Adrian G Barnett. An introduction to generalized linear models. Chapman and Hall/CRC, 2018.
Anna Goldenberg, Alice Zheng, Stephen Fienberg, and Edoardo Airoldi. A survey of statistical network models. Foundations and Trends Machine Learning, 2(2):129-255 2010.
Trevor Hastie, Robert Tibshirani, and Jerome Friedman. The elements of statistical learning. Springer, 2nd edition, 2009.
Peter Hoff. Bilinear mixed-effects models for dyadic data. J. Amer. Statist. Assoc. 100(469):286 295, 2005.
Paul W. Holland and Samuel Leinhardt. An exponential family of probability distributions for
directed graphs. J. Amer. Statist. Assoc, 76(373)333-00, 1981. doi: 10. 10.108001162459.11981 10477598. URL
1981. 10477598
Paul W Holland, Kathryn Blackmond Laskey, and Samuel Leinhardt. Stochastic blockmodels: First steps. Social networks, 5(2):199-137 1983.
Roger Horn and Charles Johnson. Malrix Analysis. Cambridge University Press, 1985.
Jiashun Jin. Fast community detection by score. Ann. Statist., 43(1):57--8, 2015.
Jiashun Jin and Wanjie Wang. Influential features pea for high dimensional clustering, Ann. Statist., 44(6)) 23599 2016.
Jiashun Jin, Zheng Tracy Ke, and Shengming Luo. Optimal adaptivity of sigmed-polygon statistics for network testing. Ann. Statist, 49(6):3408-3433, 2021a. doi: 10. 10.1214/11-A052089 URI.
ht.tps: :/ds:///o1 www.orrgg.... 21 4/21 -052088
Jiashun Jin, Zheng Tracy Ke, and Shengming Luo. Improvements on score, especially for weak signals. Sankhya A, pp. 1-36, 2021b.
Jiashun Jin, Zheng Tracy Ke, Shengming Luo, and Minzhe Wang. Optimal estimation of the num- ber of network communities.
J. Amer. Statist. Assoc 118(543):2101-211 -116 2023. doi: 10. URL
119000622459.22222205533
2035736
Brian Karrer and Mark Newman. Stochastic blockmodels and community structure in networks. Phys. Rev. E, 83(1):016107, 2011.
V. Karwa and A. Slavković. Inference using noisy degrees--iifferentially private beta model and synthetic graphs. The Annals of Statistics, 44:87-112, 2016.
Zheng Tracy Ke and Jiashun Jin. Special invited paper: The SCORE normalization, especially for heterogeneous network and text data. Stat., 12(1)),545, 2023.
Zheng Tracy Ke and Minzhe Wang. Using svd for topic modeling. Journal of American Statistics Association, 119(55)):434 449, 2024.
Zheng Tracy Ke, Jiashun Jin, Pengsheng Ji, and Wanshan Li. Recent advances in text analysis. Annual review of statistics and its application, 11, 2023.
Zhuang Ma and Zongming Ma Hongsong Yuan. Universal latent space model fitting for large net- works with edge covariates. Mach. Res., 21:1-67, 2020.
Zhuang Ma, Zongming Ma, and Hongsong Yuan. Universal latent space model fitting for large networks with edge covariates. Journal of Machine Learning Research, 21(4):1667, 2020.

---

Published as a conference paper at ICLR 2025
A. Rinaldo, Sonja Petrovic, and S. Fienberg. On the existence of the mle for directed random graph network model with reciprocation., 2010.
Mingao Yuan, Yang Feng, and Zuofeng Shang. A likelihood-ratio type test for stochastic block models with bounded degrees, Journal Statistical Planning and Inference, 219:98-119, 2022a.
Mingao Yuan, Ruiqi Liu, Yang Feng, and Zuofeng Shang. Testing community structure for hyper- graphs. Ann. Statist., 50(1):147-169, 2022b.
Yunpeng Zhao, Elizaveta Levina, and Ji Zhu. Consistency of community detection in networks under cegree-corrected stochastic block models. Ann. Statist, 40:2266-22922 2012.
12


Reviews:
[{"review_id": "0PFwOfAz4D", "reviewer": "Reviewer_wiFe", "summary": "The authors first propose the logit-DCBM model as a nonlinear variant of the degree-corrected block model (DCBM), which essentially replaces the log link function with the logit link function. Replacing the link from log brings some nice properties to the model, such as removing some constraints on latent parameters. However, at the cost of introducing non-linearity and the parameter estimation becomes difficult.\n\nThe main technique is the cancellation trick, used to estimate nonlinear terms in the logit-DCBM, which simplifies parameter estimation and the authors claim that this addresses an open problem in the $\\beta$-model parameter estimation (another one community variant which is the special case of their logit-DCBM). Additionally, the paper introduces R-SCORE for community detection, a recursive adaptation of the SCORE algorithm for the logit-DCBM. Finally, they derive upper bounds on the classification error rates for SCORE and R-SCORE for their proposed model logit-DCBM.", "questions": "1. I could not exactly make sense of the open question in the references given e.g. (Goldenberg et al., 2010). What is the open problem precisely? To analyze MLE? Or just to come up with an estimate? Or to come up with an estimate that satisfies certain properties? What is the precise technical open question?\n2. What properties does your estimate have? As far as I can think, it is not unbiased, or is it? Is it consistent? What can you say further? For me, right now, it is just some estimate.\n3. Ultimately, I really want to get a better understanding of Lemma 3 and how good this estimate is. I understood the statement and algebra used therein. But is there something more interesting? What is the effect of $m$ on the quality of the estimate? Does it not change anything in terms of quality? Or even if it does, we are looking at the statistics for $m=3$ for computational efficiency? Also, is there an intuitive way of thinking about what that statistics is capturing in (10) and its equivalent for higher $m$? And why I can expect it to be a reasonable estimate? Essentially, trying to get intuition on why cancellation happens. \n4. Does the cancellation trick also apply to other link functions beyond logit? In either yes or no, could you please walk me through why for some standard link functions (e.g. probit or other relevant ones)? \n\nTypos:\n-In Lemma 2.1 Proof, is there an extra summation over $i$ again in $(I)$?\n-In Line (222): \",the sum is over..\",the index $i_2$ is repeated twice.", "limitations": "", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "See summary.", "weaknesses": "Overall, I am not too sure why the logit-DCBM model is worth studying. The authors mention some motivation in lines 58-60 and lines 69-71, but I did not find it compelling enough. I found the motivation argued hand-heavily without any concrete and interesting reasons.\nLine 58, \",to many statisticians, (5) is preferred.\":  Which statisticians? References?\nLine 59-60: I don't think the logistic regression is the only \"recommended\" model by text bool for binary data. Also, what does \"recommending\" even mean? Where does Hastie et al. 2009 recommend it?\n\nSee also questions. Questions 1 and 2 in particular, where I further raised my concern.\n\nIt is perhaps interesting to study logit-DCBM, but it is not clear to me right now based on what is written on the paper, and that's why I am currently leaning towards a borderline reject.", "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": "", "extra_scores": {}}, {"review_id": "DkTt6ObNiT", "reviewer": "Reviewer_2iwW", "summary": "This paper proposes R-SCORE (Recursive-SCORE), a generalization of the SCORE spectral algorithm to estimate the parameters and communities in a newly introduced \"nonlinear\" extension of the DCBM model [3] where a logit function is added to the probability. The R-SCORE algorithm alternatingly optimizes the estimates of the core matrix $\\Pi$ and the offset terms $\\theta$ with the SCORE algorithm and a custom refitting step respectively.  Theoretical results are shown both for the application of the original SCORE algorithm to the proposed extension logit-DCBM and to the application of the newly proposed R-DCBM algorithm\n\n\n\n\n\n***References***\n\n[1] Jin J. 2015 Annals of Stats.  \"Fast community detection by SCORE\"\n[2] Jiashun Jin, Zheng Tracy Ke, Shengming Luo, and Minzhe Wang. \"Optimal estimation of the number of network communities\". Journal of the American Statistical association, 2023. \n\n[3] Karrer, B. and Newman, M. E. J. (2011). Stochastic blockmodels and community structure in networks", "questions": "Could you compare your rates with the classic rates for the simpler SBM model of Abbe et al. when the thetas are equal?", "limitations": "", "rating": 8, "confidence": 2, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "1. Well-written\n2. Appears rigorous and professional\n3. A generalization of the DCBM model to the logit case is an interesting direction", "weaknesses": "Accessibility to readers less familiar with the literature on community detection\n\nNo table of notations", "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": "", "extra_scores": {}}, {"review_id": "Qlk0TIU3ua", "reviewer": "Reviewer_urJ2", "summary": "The paper introduces the logit-DCBM as an extension of popular network models DCBM, LSM, and $\\beta$-model. The authors propose a \"cancellation trick\" to tackle the nonlinearity challenges of the logit-DCBM, which allows the model to retain a form of low-rank approximation similar to DCBM. They also present an algorithm, R-SCORE, for community detection in networks based on the logit-DCBM. R-SCORE iteratively updates the model's parameter estimates, removing nonlinear factors and approximating a low-rank model for clustering. The paper shows that R-SCORE achieves a faster Hamming error rate in certain sparse regions than standard SCORE.", "questions": "In eq (16), how can you guarantee |\\lambda_{min}|>0?\n\nIn Thm 3.1, Lemma 3.1, Thm 3.2, Corollary 3.1: What is C? Are the C used the same across the three results?\n\nIn the simulations, can't you compare with additional baselines based on e.g. a MLE?", "limitations": "", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 1, "strengths": "The logit-DCMB model provides a nice combination of the DCMB, LSM, and $\\beta$ models. \n\nThe \"cancellation trick\" allows disregarding of nonlinear terms by means of a ratio of two large sums used as estimators. This is an interesting idea that can be applied to various other settings.", "weaknesses": "The scope of the paper is [quote] \"to propose a nonlinear version of DCMB so that it will hopefully be more acceptable\" and extend SCORE to it. I find this goal somewhat incremental and only marginally related to the ICLR community. \n\nThe paper is hard to follow, with many acronyms that are not spelt out and sentences that are ambiguous. An example: line 085, \"The logit-DCBM (and all other models mentioned above) are so-called latent variable models, where Π is the matrix of latent variables. For latent variable models, the EM algorithm (e.g., Dempster et al. (1977)) is a well-known approach.\" What is EM? \"approach\" to do what?", "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": "", "extra_scores": {}}, {"review_id": "2g5GD5n9Ye", "reviewer": "Reviewer_CDCt", "summary": "The paper proposes logit-DCBM (Degree Corrected Block Model) for community detection in graphs. Authors propose a method to overcome the presence of non-linear terms in the estimation problem. Authors refer to their method as the \"cancelation trick\". They propose an iterative method dubbed R-score (R for Recursive) which recursively applies the cancellation trick to the estimate. Authors provide theoretical results that guarantee the estimate is close to the true value.", "questions": "Numerical experiments do not show any benefit in iterating: after a single iteration the method seems to have converged. Can you explain this? was the test data too easy? did you try running your model on more challenging problems?", "limitations": "", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 1, "contribution": 2, "strengths": "Literature is well reviewed and contributions are well positioned with respect to existing art. Authors introduce their contributions with thorough explanations that are explained in easy-to-read language, despite the large amount of notation and math involved. Theoretical results are well presented and seem to indicate the merit of the method.", "weaknesses": "Presentation of this rather theoretical paper could benefit from a more formal statement of results with a Theorem which goes earlier in the paper and the body of the paper being devoted to explaining the intuition and implications of the result. \n\nI do not find a clear indication of stopping criteria in the paper, neither did I find any discussion on computational complexity and scalability of the method. \n\nNumerical experiments are not well presented. At the very least figures could have x and y labels.", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)