Fitting Networks with a Cancellation Trick

Thanks for a great summary. We are very glad that the reviewer find our theoretical results are well presented and support the merit of our method. Below, we first provide clarifications on the weaknesses and then respond to the questions in detail.

Presentation style: Thanks, but we have explained the theoretical results on Page 3-4, with explicit rates for the Hamming errors (see Line 161). It is unconventional to present a theorem in the introduction, especially for short papers like this one.

Stopping criteria and computational complexity: The stopping criteria was mentioned in the first paragraph of Section 3 (Line 253-256). The computation cost is specified in the paragraph right above Remark 4.

Numerical experiment: Thanks and we have fixed this and revised the text. We have also added two new experiments comparing R-SCORE with the non-convex penalization MLE-type algorithm (npMLE) by Ma, Ma, and Yuan (2020), which we refer it to as the npMLE. See Section 4.

Response to question on numerical studies: Thanks for the question. Regardless of the data settings, R-SCORE always converges very quickly ($\leq 5$ steps). For example, in the experiment reported last time, R-SCORE converges in $1$ step. In the newly added experiment, R-SCORE converges in $3$ steps. The key idea of R-SCORE is to use a cancellation trick to estimate the nonlinear factors, and so to convert the logit-DCBM to a DCBM. By design, such an algorithm usually converges quickly, for the estimate for each parameter in the nonlinear factor quickly become flat when we iterate. This is different from penalization approaches (e.g., Ma, Ma, Yuan (2020), which is also an MLE approach), where we need hundreds of iteration. See Figure 3 (left) in the supplement for how fast two algorithms converge when we iterate.

Note that a quick convergence is really not a disadvantage. In the revision, we compare R-SCORE with the MLE approach by Ma, Ma, Yuan (2020). In many settings, R-SCORE is not only much faster, but also has a smaller error rate in many settings. See for example Figure 3 (right).

Thanks for the great summary and comments. We are happy to address the concerns.

The scope of the paper and relevance to ICLR community: Thanks for the comment. First, we wish to point out that "proposing logit-DCBM" is only one of our contributions. We also have several other ones, including a novel cancellation trick, a new algorithm R-SCORE, and new theoretical results. Especially, the cancellation trick is a new approach for removing nonlinearity in latent space models and can be generalized to other nonlinear links (please see our response to Reviewer 2iwW). An important message we convey in this paper is: MLE (which can only be solved by nonconvex optimization) is not the only option for attacking nonlinear problems. There exists a novel cancellation trick that removes nonlinearity and allows us to apply those power tools designed for linear settings (such as spectral approaches). We believe this is a significant contribution.

Even this particular motivation of "studying logit-DCBM" is important by itself. Network modeling is an important problem in the machine learning community, and what is the best model for real networks remains an open problem. The DCBM, LSM, and $\beta$-model are all popular models, and many works about these models have been published in machine learning conferences. Here are a few examples:

• Neural Latent Space Model for Dynamic Networks and Temporal Knowledge Graphs. By Tony Gracious et al., AAAI 2021
• Learning Guarantees for Graph Convolutional Networks in the Stochastic Block Model. By Wei Lu, ICLR 2022

Our logit-DCBM is a broader model that extends the above models. Therefore, our work is an important step forward in network modeling.

Second, our work is closely related to machine learning. In machine learning, we have many nonlinear latent variable models spreading in many areas, including cancer clustering, empirical finance, text analysis, and network analysis. 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.

Especially, we showcase this cancellation trick with a network community detection setting. The logit-DCBM is a nonlinear model, where how to do community detection is a challenging problem: existing approaches are both computationally inefficient or hard to analyze. We show that, by removing the nonlinear factor in a 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 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.

Hard to follow with many acronyms: Thanks, but we believe our way for presenting the acronym is conventional: we present the full name when the acronym appears the first time, with references. For example, the full name of DCBM is presented in the first line of the abstract, and again in Line 36 of the introduction with a reference. The full name of LSM is explained in Line 51 with a reference. The logit-DCBM is the direct combination of logit and DCBM, so the is no need to present the full name. For your comments on EM algorithm: in most published works, people only cite it as the "EM algorithm", without explaining what EM stands for. The EM algorithm is a textbook algorithm (first proposed by Dempster et al (1977)) for estimating latent variable models.

Response to Question on $|\lambda_{\min}(P)|$: In the area of network community detection, it is conventional to assume $\mathrm{rank}(\Omega) = K$ (in the DCBM case) or $\mathrm{rank}(\widetilde{\Omega}) = K$ (the logit-DCBM or LSM case). Since $\mathrm{rank}(\widetilde{\Omega}) = K$ in our case, we must have $\mathrm{rank}(P) = K$ by basic algebra. Since $P$ is $K \times K$, $P$ is non-singular, and so $|\lambda_{min}(P)| > 0$.

Response to Question on $C$: In this paper, $C$ stands for a generic constant which may vary from one occasion to another (such a use of notation is conventional in the literature). We have clarified this in the end of Section 1 (Content and notation).

Response to Question on simulations: Thanks and this is a great comment. It seems that the most appropriate MLE algorithm we can compare is the non-convex penalized MLE-based approach (npMLE) by Ma, Ma and Yuan 2020. The paper deals with the latent space model (LSM) and is probably the closest related work to our paper. We have added new two experiments (Experiment 2-3) in Section 4. The experiments suggest

• The R-SCORE runs much faster than the npMLE.
• In many settings, R-SCORE has a lower error rates than the npMLE.

We thank the reviewer for a great summary and we are very glad that the reviewer thinks our study depicts an optimistic view of the problems. Below we provide some clarifications on the weaknesses and address the question.

Accessibility: We thank you for a great comment. Community detection is probably the most studied problem in network analysis, and we have revised the paper to make it more accessible to such readers.

Table of notations: We do have a subsection called "Content and notation" in the end of Section 1. The table covers all notations we think that worthy of a clarification.

Response to Question: Thanks for raising this great question, we mention two points. First, in the simpler SBM case, all $\theta_i$ are the same, so the logit-SBM model and the SBM are equivalent. This is because the nonlinear matrix $N$ satisfies

Therefore, in this special case, the logit-DCBM reduces to an SBM (which is a special DCBM). Second, for DCBM, many algorithms have exponential error rates. However, for general logit-DCBM, due to the nonlinear factors, the optimal rates remain unknown, but it is likely that we only have polynomial rate. For example, suppose all $\theta_i$ are at the same order. Then the error rate of SCORE is

which is exponential (e.g., Jin, Ke, Luo (2021)). For the logit-DCBM, we only be able to show that that the error rate of a procedure is

which is polynomial.

Response to Question 3: Sorry but we do not have a Lemma 3 in our paper, but based on your description, we suppose you are referring to Lemma 2.2, which is about using cancellation trick to estimate $\theta_i$.

What we present in Section 2 is the so-called oracle approach in the literature, a frequently used idea for constructing new estimates. The main idea of the oracle approach is, we first find a way to reconstruct the parameters of interest in the idealized noiseless case, we then mimic the idea in the noiseless case and propose an approach for the real case. The oracle approach has been proven to be very successful in the literature, many important modern ideas, including classical PCA and the lasso (see "Uncertainty Principles and Signal Recovery" by Donoho (1989)), originated from the oracle approach.

In our setting, the parameters of interest are $\theta_1, \theta_2, \ldots, \theta_n$, and the model is

where $W$ is the noise matrix, and $\mathrm{diag}(\Omega)$ only has a secondary effect. Therefore, to apply the oracle approach to our setting,

• we first use $\Omega$ to construct $\theta_1, \ldots, \theta_n$ (this is the idealized noiseless case).
  This is done in Lemma 2.2, where we show that for each odd number $m \geq 3$,

• we then mimic the idea and replace $\Omega$ by $A$ everywhere in the construction above (this gives rise to an estimate for the real case). This is equation (10), where we set $m = 3$. For general $m$, the idea is similar, and for every $i_1$, we estimate $\theta_i$ by

This is nothing but replacing all $\Omega$ by $A$ in equation (9) of Lemma 2.2.

• we then justify the derived estimates $\hat{\theta}_{1}, \ldots, \hat{\theta}_n$ are consistent for $\theta_1, \ldots, \theta_n$ rigorously.
  For space reasons, we present this in Lemma C.1-C.2 of the supplement.
  The idea why this works is similar to that of central limit theorem, though the proof is much more complicated.

The above work for each fixed odd number $m \geq 3$. But since the algorithm with $m = 3$ is already first-order optimal, there is little reason to use a larger $m$ (for a larger $m$, we have similar numerical results, but the proof is much longer).

Response to Question 4: Yes, the cancellation trick is applicable to much broader settings. In our setting, Lemma 2.2 holds because for all $i, j$ in the same community,

We have a similar result if there is a positive function $g$ and $h$ such that for all $i, j$ in the same community,

In fact, by basic algebra, it is seen that for any odd number $m \geq 3$,

For revision, we have added a new remark, Remark 3, in Section 2. See details therein.

Response to Typos: Thank you and we have fixed them.

Thanks for the summary and great comments. We are happy to address the concerns.

Response to Weaknesses: We wish to re-iterate the motivation of our work, which is three-fold:

• We introduce a cancellation trick, which can be useful for many nonlinear latent-variable models in statistics and machine learning. For reasons of space, we only use the logit-DCBM to showcase the trick, but the trick may be useful in much broader settings. We have explained this in ``Comments to all" above; see details therein.

• If we use DCBM, then we must impose a large number of constraints as in equation (3). This is not desirable, especially if we want to fit the model using a penalization approach. If we use the logit-DCBM, then we do not need such constraints.

• The logit-DCBM is an extension of the DCBM, LSM, and $\beta$-model, each of which is popular in network analysis. Using the logit-DCBM allows us to have a unified model, and thus helps reduce repetitive and overlap research in this area (and so save research time and efforts in the research community of network analysis).

We believe we have explained the motivations carefully in the introduction, but we agree with you that more references could help. In this revision, we have added textbooks and popular packages there as reference, in all of which the logistic link is the default choice for handling binary data. We also pointed out which place of Hastie et al (2009) recommends using logistic regressions.

Response to Question 1: The open problem is all of these: "how to analyze MLE", "how to come up with an estimate" and "how to come up with an estimate that satisfies certain property" (e.g., consistency). In classical statistical settings, the MLE is usually consistent, and we can analyze the MLE with a standard approach (e.g., Lehmann and Casella, 2006, textbook).
For our setting, standard analysis for MLE does not work, and there is no consistency results for the MLE. It is therefore unclear (a) how to develop a new method, (b) what methods are consistent. We have explained these in Line 118-120 carefully: "How to estimate N in the $\beta$-model is a well-known open problem, as explained in the survey paper (Goldenberg et al., 2010) (see also Rinaldo et al. (2010)): "A major problem with the $p_1$ 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” (the $p_1$ model is a special case or ours).

Our major contribution here is that, using a cancellation trick we discover, we overcome the challenge by proposing an easy-to-use estimate and show that they are consistent, and lead to improved community detection results in the down-stream.

Response to Question 2: The estimates are consistent with rigorous proofs. In fact, under our settings, $\mathbb{P}(\widehat{\Pi} \neq \Pi) = o(1)$, and the estimates for $P$ and $\theta_1, \ldots, \theta_n$ are all consistent. Since that our ultimate goal is community detection (where we use such estimates in a middle step), so for reasons of space, we defer both the statements and proofs for consistency to the supplement: see Section C.2 and C.3 or Lemma C.1 and C.2 for details. Second, R-SCORE is the combination of SCORE and these estimates. Our main results in Section 3.1 shows that R-SCORE improves SCORE on the error rate of community detection. This implies that these estimates behave as expected.