Fitting Networks with a Cancellation Trick

Authors: Jiashun Jin, Jingming Wang
Primary area: learning on graphs and other geometries & topologies
Keywords: Network analysis, DCBM, logit-DCBM, community detection, SCORE

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.

Decision: accept (poster)
Reviewer scores: 5, 8, 5, 5

Reviews and discussion:
<thread>
creation date:
1730497423407

thread_type:
official_review

<thread_object>
creator: reviewer_cdct

<content>
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.

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. 

I 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. 

Numerical experiments are not well presented. At the very least figures could have x and y labels.

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?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730631992444

thread_type:
official_review

<thread_object>
creator: reviewer_urj2

<content>
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.

strengths:
The logit-DCMB model provides a nice combination of the DCMB, LSM, and $\beta$ models. 

The "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. 

The 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?

questions:
In eq (16), how can you guarantee |\lambda_{min}|>0?

In 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?

In the simulations, can't you compare with additional baselines based on e.g. a MLE?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730721577596

thread_type:
official_review

<thread_object>
creator: reviewer_2iww

<content>
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





***References***

[1] Jin J. 2015 Annals of Stats.  "Fast community detection by SCORE"
[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. 

[3] Karrer, B. and Newman, M. E. J. (2011). Stochastic blockmodels and community structure in networks

strengths:
1. Well-written
2. Appears rigorous and professional
3. 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

No table of notations

questions:
Could you compare your rates with the classic rates for the simpler SBM model of Abbe et al. when the thetas are equal?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730798115733

thread_type:
official_review

<thread_object>
creator: reviewer_wife

<content>
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.

The 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.

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.
Line 58, ",to many statisticians, (5) is preferred.":  Which statisticians? References?
Line 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?

See also questions. Questions 1 and 2 in particular, where I further raised my concern.

It 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.

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?
2. 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.
3. 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. 
4. 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)? 

Typos:
-In Lemma 2.1 Proof, is there an extra summation over $i$ again in $(I)$?
-In Line (222): ",the sum is over..",the index $i_2$ is repeated twice.
</content>
</thread_object>

</thread>
<thread>
creation date:
1732774070031

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Comments to All

comment:
We thank all reviewers  for their valuable time and thoughtful comments. The reviewers have two main points or recommendations: (1) to clarify the relevance to machine learning, and (2) to add a numerical comparison with the MLE approach. 

***
**For the first main point**: (a)  Our paper introduces a cancellation trick by which we can conveniently reduce a nonlinear latent variable setting to a linear latent variable setting, (b) network analysis is an important area in machine learning, with increasingly more interest,  and how to model and analyze social networks remains a largely open problem. 

For (a): Compared with classical multivariate statistical analysis approaches, a major advantage of  machine learning approaches lies in modern ideas for tackling nonlinearity. However, for unsupervised learning  (e.g., clustering and fitting latent variable models), 
how to tackle nonlinearity is a very challenging problems. Most existing machine learning approaches use non-convex optimization, with substantial efforts devoted to speed up algorithms, but still, many of non-convex optimization approaches remain slow computationally.   

In this paper, we discover a simple cancellation trick that is able to remove nonlinearity effectively and so allows the users to take advantage of existing powerful methods for linear problems (e.g.,  PCA) and thus significantly reduce computational costs. This points out a new possible solution for tackling nonlinearity.   

Since nonlinear latent variable models exist in many machine learning problems and have broad applications (e.g., in cancer clustering,  empirical finance, text analysis, and network analysis), we believe our paper is very relevant to the machine learning community.  

Especially, the logit-DCBM is a nonlinear latent variable model, where how to do community detection is a challenging 
problem:  existing approaches are either computationally inefficient, or hard to analyze, or both. We show that, by removing the nonlinear factor in the logit-DCBM (a nonlinear network model), we can convert it approximately to a DCBM. We can then effectively apply (say) SCORE (a recent spectral approach) for community detection. For networks with a few thousand nodes, this can speed up the computation by 50 times compared to using MLE. 


For space reasons,  we 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.  In the revised paper, we have added a paragraph in the end of Section 5, reflecting the points above. See details therein.

For (b):  Network analysis  is an important area  in machine learning. Many papers on network modeling and analysis haven been accepted at top machine learning conferences. For instance, 

1) Effects of Graph Convolutions in Multi-layer Networks. By Aseem Baranwal et al.,  ICLR 2023

2) Semi-supervised Community Detection via Structural Similarity Metrics. By Yicong Jiang and Tracy Ke,  ICLR 2023

3) Random Sparse Lifts: Construction, Analysis and Convergence of finite sparse networks. By David Robin et al., ICLR 2024

Thus, we believe that the network setting presented in this paper is of interest to the machine learning community.
 
***
**For the second main point**, we have added two numerical experiments  (Experiment 2 and 3 in Section 4) where we compare 
R-SCORE with the approach by Ma, Ma, and Yuan (2020). The latter is essentially a non-convex penalized MLE (npMLE) approach for fitting latent space model, which is the work that is most closely related to our work. We compare the error rates of R-SCORE with npMLE under different settings, and find that (a) R-SCORE is computationally much faster, and (b) in many settings, the error rate of 
R-SCORE is lower than that of npMLE.
</content>
</thread_object>

</thread>


Metareview:
metareview:
This paper introduces the logit-DCBM model for random graphs which extends several previous models. The paper then designs R-SCORE to estimate the parameters of the model, which addresses nonlinearities in the model by a cancellation trick, detailed in Lemma 2.2. Empirically R-SCORE seems to outperform existing spectral clustering approaches. Overall the reviewers find the results to be interesting, however there are some concerns about presentation (which was partly addressed in author response) and the significance of the work especially for the ICLR community.