Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper studies phase transition for detecting communities under the degree-corrected block model (DCBM). The motivation is that chi-square test is not good for DCBM because of artifacts, so they use the the Signed-Quadrilateral (SgnQ) instead. The authors provide the SgnQ efficient regime, the computationally infeasible regime, as well as the statistically impossible regime for the model. Some simulations and experiments are included.
strength_and_weaknesses: - I don't know how technically novel this paper is. A lot of analysis are similar to those in [Arias-Castro & Verzelen], [Ji et al.], except considering on an arguably more general model DCBM. The authors highlight in the introduction, that their problem is more challenging because they need to consider the computational gap. That is not entirely new because it is well-studied for the SBM (e.g. [1]). Could the authors highlight their technical novelties? What can other researchers learn from this paper if they want to work on similar models?

- Section 2.5: Why we only consider the case of SBM instead of more general cases here? Is it because of any difficulty in analysis?

- Figure 2: How should I interpret the white region (\beta > 0.5)? Is it because of any difficulty or limitation in analysis?

- Figure 2: I note that Theorem 2.4 (statistical lower bound, orange region) and Theorem 2.2 (SgnQ upper bound, blue region) all talk about the general DCBM case, while Theorem 2.6 (computational lower bound, green region) talks about the specific SBM case. The paper claims to establish the phase transitions for DCBM. How does that connect to the SBM assumption (the computational lower bound for SBM is already known [1])? Is that sufficient for the claim? This could be a writing issue but I don't know if there is any hidden assumption here, and if yes it should be pointed out in the figure. 

- Does the real-world dataset follow the DCBM? Why DCBM is a reasonable ground assumption in this case?


References:
[1] Chen, Yudong, and Jiaming Xu. "Statistical-computational phase transitions in planted models: The high-dimensional setting." International conference on machine learning. PMLR, 2014.
clarity,_quality,_novelty_and_reproducibility: - This paper suffers from mathiness, especially in the introduction. To me, for one example, this paragraph right on page 2 "To see why the signal captured ..." is not readable. Few will have an idea of what is going on behind the wall of notations at this point. Ironically, this paragraph serves as an important motivating example for the whole paper. I would suggest the authors to consider rephrase that part in their own words instead of throwing math notations. 

- The organization of the paper is another issue. Is it really necessary to introduce every definition, model, example, statistic in the introduction? On the other hand, why not put Figure 2 (which should be the most important message in the paper) to an earlier part?
summary_of_the_review: The technical novelty of this paper is unclear. The writing can be hard to follow, especially in the introduction.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper considers community detection with unbalanced communities. Specifically, they consider the hypothesis testing problem on the degree-corrected block model, which is to distinguish whether a graph is generated from a null model with one community or an alternative model with unbalanced communities. 

They show phase transitions of this testing problem. When the size of the small community is larger than $\sqrt{n}$, they show that the SgnQ test (Jin et al. 2021) is optimal. They show the matching computational lower bound in this case. When the size of the small community is smaller than $\sqrt{n}$, they show the parameter regime where the SgnQ test works.
strength_and_weaknesses: Strengths:
1. The small community detection problem is well-motivated. They show the naive degree-based $\chi^2$ test is powerless for some scenarios. 
2. They provide the phase transitions for this testing problem. The unbalanced community detection is harder than the balanced version. They show SgnQ test still works for unbalanced community detection in some regimes.

Weaknesses:
1. Does the identifiable issue only happen for the degree-corrected block model? I think it would also hold for the stochastic block model.   
2. I think some explanations like general settings with more than two communities and normalization in section 2.1 are not helpful. It makes the setting too complicated to follow. 
3. Although it is mentioned it is not easy to analyze the SgnQ test in the unbalanced setting, I think it would be very helpful to see a more intuitive explanation of how the analysis works.
clarity,_quality,_novelty_and_reproducibility: This paper is not very easy to follow due to the writing and arrangement. This paper analyzes this existing SgnQ test in a new small community detection problem.  
summary_of_the_review: Overall, this paper is very interesting. However, the main techniques to make the SgnQ test work for the unbalanced community detection is unclear to me since it is not well explained in the main paper.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper studies the task of detecting a planted community structure with small clusters (e.g. a planted clique) inside a graph with heterogeneous degrees. More precisely, the authors consider a random graph model such that
$$ P(i \sim j) = \theta_i \theta_j P_{\pi(i), \pi(j)}  $$
where $\theta$ models the degree heterogeneity between vertices, and $\pi$ is an assignment of vertices into $K$ different communities. The goal is to find a test that discriminates between the null hypothesis $K = 1$ and its alternative, even in the presence of very small communities. In particular, the alternative model considered consists in taking $K=2$, and two communities of size $n$ and $N \ll n$, with the matrix $P$ given as 
$$ P = \\begin{bmatrix} a & b 
\\\\ b & c \\end{bmatrix} $$

The paper's contributions are threefold:
- **Existence of a polynomial test:** consider the *signed quadrilateral* statistic
$$ \psi_n = \sum_{i_1, \dots, i_4} \hat A_{i_1 i_2} \hat A_{i_2 i_3} \hat A_{i_3 i_4} \hat A_{i_4 i_1},  $$
where $\hat A$ is a centered version of $A$. The authors show that there exists a certain threshold $\tau$ depending on the eigenvalues of $\mathbb E[A]$ (and related matrices), such that if $\tau\to\infty$ there exists a test based on the value of $\psi_n$ that discriminated between $K = 1$ and $K > 1$ whp. In the two-community case above, this corresponds to 
$$ \tau = N(a-c)/\sqrt{cn}. $$

- **Statistical exact threshold:** in the two-community case, this paper show the existence of a statistical threshold at 
$$\tau' = \sqrt{N}(a-c)/\sqrt{c} $$ such that if $\tau' \to 0$, no test can distinguish between $K=1$ and $K>1$. Conversely, if $\tau' \to \infty$, then there exists a (non-polynomial) test that discriminates between the two hypotheses.

- **Computational lower bound:** finally, if $\tau \to 0$, the authors provide a computational lower-bound based on the low-degree framework, showing that there is no succesfull test based on a low-degree polynomial in $A$. This is a proxy for polynomial hardness. Since $\tau$ and $\tau'$ differ significantly only when $N \ll \sqrt{n}$, this implies that the signed quadrilateral test is optimal above $\sqrt{n}$.
strength_and_weaknesses: The setting considered by the paper is both natural and interesting; it is closer to a real-world setting than the vanilla planted clique problem, and therefore the failure of $\chi^2$ and the need for other methods are meaningful. The authors obtain a near complete phase diagram, with only a small gap in the $N \gg \sqrt{n}$ regime.

However, the main weakness of the paper is the overall clarity and presentation of the results; precise feedback is given in the next section. In particular, it is nearly impossible to check the proof without constantly referring to Jin et al. for every single definition.

It is also my opinion that this paper would be more suited for a more theoretical CS conference/paper, although I do not consider it grounds for rejection.
clarity,_quality,_novelty_and_reproducibility: See above for quality/novelty of results. The difference of power between the $\chi^2$ and SgnQ tests are nicely illustrated, with figures showing the distinction between a symmetric and non-symmetric SBM.

Here is the more precise feedback on the paper clarity:

**Presentation**: 
- the relevant model definitions are split between the very beginning of the introduction and section 2.1, which makes it hard to refer to. In general, the introduction is a bit rushed; the Sinkhorn-type argument is introduced before the $\chi^2$ test is properly defined. I think the paper would benefit from a more formal model introduction, which defines all the useful quantities used in the theorems.
- the paper is overall very technical, and provides almost no rationale behind all the definitions and algorithms. Some questions/remarks:
  - $\tilde \Omega, \tilde P, \hat A$ (among others) are defined in matrix form, and it is hard to understand what they correspond to (you basically zero out the image of a specific vector, but why this one?). More minorly, for consistency $\hat A$ should maybe be renamed to $\tilde A$.
  - accordingly, the intuition behind the SgnQ algorithm based on $\hat A$ is never given.
  - the vector $h$ is defined twice, in slightly different ways: in the introduction, it is given as $\mathbb E[\pi]$, while in section 2.1 it is the empirical vector $\Pi \mathbf 1$ (this matrix characterization should probably also be given, since it is useful to understand some of the results afterwards)
  - I tend to agree that $d$ and $g$ are quite natural vectors, but their significance should be expanded upon; for example, the fact that $d = h$ in the SBM case is quite crucial, since it means that $\tilde \lambda_1 = \lambda_2$.
  - the notion of "power" of the tests should be explicitly defined.
  - for (2.3) and after, why are the community labels swapped (i.e. why does $\mathcal C_1$ correspond to the first community and $\mathcal C_0$ to the second ?).
  - Lemma 2.2 does not give much insight into the problem, and should probably be relegated in the appendix. Alternatively, it would be more meaningful to expand on why this means that $\tilde \lambda_1 \simeq N(a-c)$
  - when writing $Ph \propto \mathbf 1_K$, I think it would be interesting to make the proportionality constant explicit (for notation consistency, let's call it $\alpha$) and mention that $n\alpha$ is the average degree of the graph, just like in the null model. This would give people used to the SBM a better grasp of the degree conditions such as the ones in (2.5) and (2.7).
  - the notation $'$ for matrix transpose is not very standard, so it should be made explicit somewhere.

**Proof**: the proofs of appendix E rely too much on Jin et al. for key quantities. Of course, lifting bounds is perfectly normal, but the quantities of interest ($X_i, Y_i, Z_i$) should be defined in a self-contained way. Even more important, no definition for the *ideal*, *proxy* and *real* versions of $Q$ are given, so the structure of the proof cannot be followed. Otherwise, the proof is very computational, so I didn't every inch of it; but Lemma E.13 is a welcome formalism.



**Minor remarks/typos**:

- in (2.4), I found interesting that $b = c + O(\epsilon)$, this may be worth to mention, in relation with the classical planted clique setting
- above (2.6), the matrix $G$ is never used
- I assumed that $(dist)$ means that the summation terms need to be distinct; if so this should be made explicit
- in E.4.1, the definition of T should have $i_m$ and not $i_M$; is it the same $m$ as in the definition of the DCBM model ?
- below Theorem F.1, the conditions (i)-(iv) should be (1.)-(4.)
- the checking of conditions from Appendix C and Lemma E1 can probably be merged, since it is the same change of parametrization
- the use of $\Omega$ in appendix I is very confusing
summary_of_the_review: This paper presents very interesting results on testing a generalized version of the planted clique setting, which is closer to real-world applications. However, the presentation must be significantly improved, and the proof made self-contained, hence I do not recommend acceptance.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The reviewers agree that the results of the paper are an interesting contribution to the statistics literature on community detection and its algorithmic hardness. The paper is of theoretical nature focusing on testing whether a small community is present of not the in degree-corrected SBM. This poses some mathematical challenges that are resolved in the paper. We were not sure ICRL is the best venue for this paper as the paper does not really deal with learning. But putting this aside it is a paper that should be accepted for publication. 
justification_for_why_not_higher_score: The paper is nice, but I did not identify any specific reason to highlight it. 
justification_for_why_not_lower_score: It could be rejected if the senior chair or the program committee considers it out of scope. It would indeed be more suitable for TCS or statistics venues.
Decision: Accept: poster