Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper is about testing properties of stochastic block models. In particular, the framework presented in the paper is applicable to symmetric properties. A property is defined to be a set of assignments of the $n$ nodes into $K$ communities and it can be described by a subset of $[K]^n$. A symmetric property is a property that contains all of the assignments that partition a specific subset $\mathcal{N}\subseteq [n]$ of the nodes in a specific way (the labels can be permuted though). The alternative hypothesis for the tests considered in the paper, need to be a union of symmetric properties for the same subset $\mathcal{N}$.

The authors define a notion of distance that depends both on combinatorial properties of the partitions and the probabilities of the models in different instances. In particular, the proposed distance is a product of the 2 distances, which implies a trade-off: the null hypothesis can be rejected if either the edge probabilities are close and the instances are very different combinatorially, or vice versa. Using a likelihood ratio statistic, it is shown that the test accepts the null hypothesis with constant probability when the minimum distance does not exceed a certain threshold and rejects it with probability that approaches 1 when the distance does go above a different threshold. The authors complement these results with information theoretic lower bounds, which show that the aforementioned trade-off is indeed necessary. 
strength_and_weaknesses: Strengths:
- The paper addresses a very important problem and proposes the use of a novel distance metric to quantify the quality of the propose statistical test. 
- The results are complemented with lower bounds showing that the new distance metric is indeed inherent to the problem.

Weaknesses:
- It seems that the examples on which the test is applied in the paper, do not capture the full generality of the framework. So, it would be nice to see a characterization (or at least a discussion) of what type of problems could be solved using this test. 
- To that end, it might also be useful to discuss about how restrictive Assumption 3.1 is in terms of the type of problems that satisfy it.

Minor comments:

- Last line of section 2.1: "$[K]^m$" should be "$[K]^{m+m^\prime}$"

- Section 2.4, lines 9-10: "supreme"->"supremum"

- Page 5, 2nd line from the bottom: "there existing"->"there exists" 
 
clarity,_quality,_novelty_and_reproducibility: The writing of the paper is clear and the ideas a novel. 


summary_of_the_review: The main contribution of this paper is showing that the right metric (justified by upper and lower bounds) for a testing symmetric properties of stochastic block models is a product of a combinatorial and a probabilistic distance metric. I consider this to be a solid contribution and recommend acceptance.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper studies a very general hypothesis testing problem about the community assignement on stochastic block model. Given two disjoint community properties, the difficulty of distinguishing between the properties depends on distance between properties and probability distance between communities in the stochastic block model. The authors propose a method to define p-value, which can be applied to define the rejection rule of the test. The author also derive the information-theoretic lower bound. 
strength_and_weaknesses: Strength

1. I believe this paper studies a very important and very general problem about stochastic block model. 
2. The authors provide examples for definitions, which help the reader understand the paper better. 
3. Overall, this paper is well-written. The statements in definitions, assumptions and theorems are clear. 
4. The theoretical results are novel and interesting. 

Weakness

There is a critical limitation in the theoretical result, which has been stated after Theorem 3.2. This main theorem assumes $1/\rho_n=o(n^c)$ for $c\in(0,1)$. In the existing result, if $n\rho_n/\log n\to\infty$, then then the assignments can be exactly recover with high probability. The assumption in Theorem 3.2 is even stronger than $n\rho_n/\log n\to\infty$. The case when exact recovery is not possible is still very interesting. 

I also have some comments and questions about the clarity in the next part. 
clarity,_quality,_novelty_and_reproducibility: 1. The signal strength $\rho_n$ is not defined when it appears in Section 2.3. I understand the definition of $\rho_n$ when it appears again in Section 3 before Theorem 3.2. I think the authors should move the definition of $\rho_n$ to Section 2. 

2. I am very confused about the definition of likelihood ratio statistic in equation (2.3). In classical hypothesis testing, the likelihood ratio statistic should be defined as
$$\frac{sup_{\theta\in\Theta_0}f(X;\theta)}{sup_{\theta\in\Theta_0\cup\Theta_1}f(X;\theta)},$$
and we reject the $H_0$ if this statistic is small. In the definition in the paper, the roles of $\Theta_0$ and $\Theta_1$ are exchanged. I think the author should justify why they use a different definition for likelhood ratio statistic. 
Let us consider a special case of hypothesis test: $\mathcal C_0$ contains a single assignment $z_0$ and $\mathcal C_1$ is the set of all other assignments, and suppose $z_0$ is not the MLE, then LRT=0. In this case, LRT only tells us if $z_0$ is the MLE. Is the LRT still useful in this test? 

3. In equation (2.9), we obtained the MLE of $p$ and $q$ for $z\in\mathcal C_0 \cup\mathcal C_1$. Why can we also use these MLE for $z\in\mathcal C_0$ in equation (2.10). 
summary_of_the_review: I believe this is a good paper if the author can clarify my concerns.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper presents a framework to test whether a certain [symmetric] community property of the stochastic block model (SBM) is satisfied and calculate p-values the quantify the uncertainty. The paper introduces a shadowing bootstrap method to deal with the combinatorial challenges of the test. The framework relies a combinatorial distance (a.k.a community property distance in Def. 2.4) between communities and uses it together with a probabilistic distance (difference of community parameters/probabilities) to ensure the test remains “honest”. The model works applying a likelihood ratio test for the SBM, where the limiting distribution of the likelihood ratio is driven by the two edge sets of misaligned edges (assigned to the same community by one assignment in a community property and to different communities by another assignment in the other property). The paper also presents an analysis of the limiting distribution of the leading term of the LRT statistic and a Shadowing Bootstrap for the test. The theoretical component of the paper concludes with both: a validity analysis of the proposed test for general symmetric community properties, and an alternative (information theoretical) lower bound result relaxing the scaling conditions of the test. The experiments show numerical evaluations (Type I and II errors) of the shadowing bootstrap to test the community hypothesis with $\alpha=0.5$ for various sizes of networks $n$ and varying difference between $p$ and $q$ (i.e., $\Delta$).
strength_and_weaknesses: With respect to its strengths, the paper is well organized, the problem is relevant to the ML community, particularly to hypothesis testing SBM modeling and could be applicable to clustering and other domains. The paper states a clear goals although it is at times obscure in its notation. Another strength is the thorough analysis of permutation impacting computation of likelihood in the SBM which highlights the practical difficulties of LRT for probabilistic models due to isomorphisms. The Shadowing Bootstrap to estimate the p-value of the LRT is also interesting but it seems that it may present scaling challenges.
There are some areas where the paper could be improved. For instance, the evaluations are interesting on the impact of $\Delta$ (distinguishing an SBM from an Erdös-Rényi model) but not fully developed. The computational costs and runtimes (e.g. as K and n grows) could be interesting to identifyfy applicability of the technique and possible future work to ensure scalability. Another weakness is that no evaluation is provided with respect to the choice of other parameters. In general the contribution is more theoretical. 
clarity,_quality,_novelty_and_reproducibility: The paper is relatively clear in terms of the model and intuition, although there are some areas that need polishing and better understanding of the performance (most notably, conditions that make the framework desirable to be used over other alternatives) require further evaluation. The quality of the ideas are interesting and the model is intriguing. The novelty is more with respect to a possible implementation of the LRT for SBM models though a more thorough evaluation could be beneficial.
summary_of_the_review: The paper has its pros, such as the relevance, the clear stated goals and the analysis of the effect of $\Delta$ over Type I and II errors. However, there are several reservations with respect to the applicability of the framework because a hypothesis testing technique is as important as its application. The advantage seems to be more due to the some of the insights but more evaluations are highly recommended. I detailed my comments on what could be improved in the Strength and Weaknesses section.

%%%Post Rebuttal Comment%%%

Thank you for the answer to my questions. This clarifies most of my doubts and I raise my score.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper studies the problem of hypothesis testing in community detection: instead of asking to recover the exact community assignments, the goal is to perform hypothesis testing on them (e.g. asking whether two given nodes belong to the same community or not).

The authors introduce a framework for measuring distances between community assignments, that depends on the number of mismatched edges between the two assignments. Using this notion, they propose a test based on Gaussian approximation to discriminate between hypothesis classes $\mathcal C_0$ and $\mathcal C_1$. They show that this test has the prescribed asymptotic power, i.e. that the p-values are asymptotically the same for the original hypothesis test and its Gaussian approximation. Finally, they show an information-theoretic lower bound involving the SBM parameters and the classes themselves, under which no test can discriminate between the two.


strength_and_weaknesses: This is overall a very enjoyable to read paper; it departs from the classical point of view on the SBM, and introduces several new tools to handle hypothesis testing in this setting. It is overall quite clear: all technical definitions are accompanied with figures, and the authors included several extended examples throughout the paper to illustrate the main results. The more technical setting is relegated to the appendix,

My main reservation about the paper is about its practical usefulness. The fact that $\rho_n \gg n^{\epsilon - 1}$ is glossed upon a bit too fast: it is a scaling where the actual assignment $z^*$ can be recovered with absurdly overwhelming probability, and hence the p-values for any (rejected) test should be extremely small. It also does not seem to be a technical assumption, since a non-negligible level of signal is certainly needed for a Gaussian approximation to hold. Can you explain why your framework is more powerful/useful than simply computing $z^*$ and then testing whichever hypotheses we want ?

clarity,_quality,_novelty_and_reproducibility: Minor remarks:
- $\rho_n$ should be defined earlier, since it is used as early as section 2.3
- you make a lot of reference to diverse assumptions/examples, the paper would be slightly easier to follow if they were hyperlinked
- In the definition of LRT (2.3), why is the sup in the denominator over $\mathcal C_0 \cup \mathcal C_1$ ? This is especially weird since the remainder of the paper seems to assume that this sup always belongs to $\mathcal C_0$.
- I had some trouble understanding the notion of packing that you introduce in Definition 4.1, especially when $\epsilon = 0$; could you expand on it a bit more ?
- in the numerical results section, could you specify the value of the threshold $I(p, q)d(\mathcal C_0, \mathcal C_1)$ so that we can see how it matches with the predictions ?
summary_of_the_review: See above
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: This paper considers the important problem of testing properties of stochastic block models, e.g., whether two nodes belong to the same community. A novel distance metric is introduced and the achievability results are complemented by information-theoretic lower bounds. All reviewers agreed that the contributions are significant. 
justification_for_why_not_higher_score: I believe the paper is suitable for a spotlight presentation but not an oral one because there might be others papers that are more deserving of an oral presentation. I don't have the full information, and hence, I can't tell, so I'll be conservative. 
justification_for_why_not_lower_score: Clearly, this paper should not be rejected.
Decision: Accept: notable-top-25%