Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper considers community detection in the Hypergraph Stochastic Block Model (HSBM), an extension of the popular SBM for graphs. The paper is concerned with the detection problem; namely, when is it possible to distinguish the HSBM from its Erdos-Renyi counterpart? Prior work by Pal et al. proves a result in the positive direction; when the model parameters satisfy a certain inequality, then detection is possible. The paper gives an alternate proof of the same result by relating the community detection problem to the problem of broadcasting on hypertrees (in a similar vein to the work of Mossel et al. in the SBM). This paper also gives consistent estimates of the model parameters whenever detection is possible. Finally, the paper proves a negative result, completing the conjecture of Angelini et al. (2015).
strengths_and_weaknesses: •	The proof of the positive result seems to be much simpler than the existing result of Pal et al. Even though the result is not novel, this is a valuable contribution. Moreover, the consistent estimation results are novel. 

•	The negative result is significant because it confirms a conjecture, identifying the detection threshold.

•	The positive result follows by analyzing the number of “loose cycles” in the HSBM and its Erdos-Renyi counterpart, showing that the loose cycle distributions differ.

•	The negative result applies an existing result to prove contiguity of the two hypergraph distributions; the main effort is in verifying its conditions.

•	There are pervasive writing issues; please proofread carefully! The writing issues are my main concern.

•	Lemma 3.4 is hard to parse.

questions: •	Please comment on whether your hypertree analysis techniques apply to any broadcasting/percolation problems outside the scope of your paper.

•	It would be valuable to include a description of the technical challenges and how you overcame them.


limitations: Yes
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: In this paper, the authors look at the problem of when it is possible to detect latent communities in a hypergraph stochastic block model. Previously the answer was known for SBM in graphs and a similar sharp threshold was conjectured for hypergraphs as well. The authors answer both the positive part and the negative part of the conjecture. The first part is answered by showing that the distribution of the number of loose cycles approach the Poisson distribution; in that case the detection problem can be resolved if certain conditions are met. On the other hand, if the conditions are not met, then by using a Galton-Watson style argument (similar to SBM), the prove the negative  part of the conjecture.
strengths_and_weaknesses: The paper is well-written and the results are very strong theoretically. The techniques are also quite interesting and I learned a lot from the paper.
questions: 1) In L75, approximate recovery is discussed. However, the problem that is solved is that of detection and not of recovery (even approximately). Here, I am a bit confused. Can you please explain?

2) Is it not possible to show the proof of Theorem 1.1 in the finite samples regime as well? 

3) I believe that the writing in Section 3 can be improved significantly. It is not clear to me at all why the difficulty in solving the hypertree problem (spin of the root) translates to difficulty in solving the detection problem in hypergraph SBM? Can you please point me to the formal proof that rigorizes this argument? For now, I think the paper simply says that the neighborhood looks similar for a particular node but this is very hand-wavy.


limitations: Yes
review_title: null

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: This paper studies the problem of community detection in hypergraph stochastic block models. The paper gives a proof of the detection threshold proposed by Angelini et al. [2].

The positive direction has previously been shown by Pal and Zhu [26], and this paper gives a new proof of the same result based on counting loose cycles in the hypergraph.

The negative direction was not previously known, and this paper generalises the proof of Mossel et al. [23] from graphs to hypergraphs.
strengths_and_weaknesses: ## Strengths
* This paper studies an interesting problem which is of interest to the community.
* The presented result is new, and the proof appears to be sound.

## Weaknesses
* This paper is quite difficult to follow. It is very mathematically dense and would benefit from some additional explanation and discussion. There are also some careless errors - for example the caption of Figure 1 (see the detailed comments).
* The proof follows the proof for the graph case (Mossel et al. [23]) very closely. It is not clear how the proof differs. It would be helpful to include more discussion of the key ideas which are needed to generalise the proof to hypergraphs. This would help to determine the significance of the result.
questions: ## Questions
My key question, to help judge the significance of this paper is: what are the key differences between the proof in this paper, and the one in [23]? What are the challenges in generalizing the result to hypergraphs, and how does this paper solve them?

## Minor Comments
* Line 13 - the first sentence is not grammatically correct. It could be "Community detection, or clustering, *aims* ... population. *It* is a *fundamentally* important ..."
* Lines 14 + 26 - I think there should not be colons here. I suggest just starting a new sentence.
* Line 28 typo: 'spectral' -> 'spectrum'
* Line 30 typo: 'known as *the* planted...'
* Line 37 typo: 'called *the* hypergraph...'
* Line 43: the number of vertices in a hyperedge is usually called the 'rank' of the hyperedge, and 'degree' always refers to a vertex. For example, Line 77 is ambiguous, because this paper overloads the term 'degree'.
* Lines 54-55: this is a little vague. Which computations on an adjacency tensor are NP-hard?
* Line 72 typo: "up a sign" -> "up to a sign"
* Line 97 - "see Theorem 1.1" should be in parentheses
* Figure 1 - I believe the caption is the wrong way round. Detection is impossible **above** the dashed curves, and possible **below** the dashed curves.
* Line 186 - it is not immediately clear what the 'children' of a hyperedge are. Does this refer to the vertices in the hyperedge?
* Line 189, and throughout the paper. It is quite difficult to follow inline math with many fractions and subscripts. I would recommend re-formatting to avoid inline fractions (like this $\frac{1}{2}$ ), either by rewritting as $1/2$ or using a full equation environment for more complex expressions.
* Line 209 typo: *and* also equivalent to
* Line 210 typo: 'variation' -> 'variance'
* Line 211-215: this is quite difficult to follow
* Line 216: what does it mean that "$V_2$ separates $V_1$ and $V_3$"?
* Line 222: there is a large gap after "a.a.s." - you can fix this by using "a.a.s.\ " in Latex.
* Line 231: brackets are not large enough to surround their contents. You can use "\left(" and "\right)" in latex. Though also see my earlier comment on inline math.
* Between lines 231 and 232 - the notation on this line is a bit confusing.

limitations: The authors have addressed the limitations of their work.
review_title: null

Meta-review: metareview: This paper confirm the positive part of the conjecture of Angelini et al (2015) about the existence of a sharp threshold on the model parameters for community detection for sparse hyper-graphs. Here the author’s contribution is a simpler proof than the existing one and consistent estimation of the model parameters. The authors also prove the negative part of the conjecture. One of the main negative comments of the reviewers is that the presentation can be improved by a careful proofreading and editing. The authors should incorporate the changes suggested by the reviewers for making the paper more accessible to the general audience and point out what the new contributions are in their proof, which seems to closely follow the proof in the graph setting by Mossel et al[23].

confidence: Certain
Decision: Accept