Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: This paper studies a binary hypothesis testing problem that considers whether a given hypergraph has one or more than one community. Under a general class of degree-corrected mixed-membership model for hypergraphs, it identifies conditions under which it is impossible for any test to distinguish between the null and alternative hypothesis. The above results, which are first derived for uniform hypergraphs, are then extended to non-uniform hyper-graphs by viewing a non-uniform hypergraph as a collection of uniform hypergraphs. The paper also proposes a statistical test that successfully solves the above-mentioned hypothesis testing problem under conditions that can get logarithmically close to the impossibility regime. Experiments on simulated data validate some of the theoretical findings.
main_review:  1. This paper argues that it is the first to consider significantly more flexible models that support mixed-membership and degree-heterogeneity in hypergraphs. The key idea is degree matching, which allows construction of a difficult-to-distinguish alternative hypothesis. It would be better to present an intuitive explanation for the technical difficulties that arise due to the use of a richer model. What techniques have been borrowed from the existing literature and why are existing techniques not applicable in the current setting?

2. Why is $\pi_{i_1}$ still present while computing the expected degree of node i_1 under the alternative hypothesis? Under the alternative hypothesis, $\pi_{i_1}$ is a random quantity.

3. Degree matching aims at matching the expected degrees of nodes under the null and alternative model. Thus, it appears reasonable to argue that a degree-based test would fail in this case. However, to argue that "any" test would fail, the paper shows that $\chi^2$-divergence between the null and alternative distribution goes to zero asymptotically. An intuitive explanation for how one goes from arguing that expected degree matches to arguing that $\chi^2$-divergence is zero would be very helpful in making the paper more accessible.

4. Sections 2.4 and 3.1 are difficult to understand. Consider providing additional details and more intuition.

limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: This paper considers the community detection problem in the hypergraph setting: determine whether there is a single community (null hypothesis) or K > 1 communities (alternate hypothesis). The main contribution is the development of lower bounds via bounding the \Chi^2-divergence, which is a standard method, although quite technically demanding in this setting due to the many parameters involved. Overall, this is a clear contribution to the theory literature on stochastic block models and community detection. It is a bit harder to judge its appropriateness for NeurIPS.
main_review: On the technical side, the main contribution of this paper is pushing through the challenging technical analysis for the \Chi^2-divergence to demonstrate a lower bound that is tight up to logarithmic factors. I believe this is a valuable theoretical contribution, that extends the community detection work from the random graph to the random hypergraph setting. The paper is a dense read, due to the need to capture all of the notation and technical details within the page limit. I did not check the proofs carefully, but the results seems correct.

It does not devote much space or effort to justifying where this form of hypergraph model might arise and where the obtained theoretical understanding might lead to some useful algorithms. This would have significantly strengthened the paper with respect to NeurIPS, and might give the broader audience an appreciation for why such these results might be needed as part of a larger body of work. As the paper currently stands, it is an interesting contribution to a seemingly narrow set of technical questions arising from the stochastic block model community, and might be a better fit in a venue that is more targeted towards that community. To be clear, I do not see a clear reason to reject this paper from NeurIPS but I do not see a compelling reason to include it either. The paper would have been much stronger with a sample application and a real dataset, to justify the complexity of the proposed hypergraph models. I completely agree that this is a challenging technical problem, but I would prefer to see how and why this level of complexity might be needed some day in a data-driven setting.
limitations_and_societal_impact: I did not have any concerns on this front.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper introduces and studies a hypergraph community detection model called RMM-DCMM. In this model, each vertex may have a different degree (degree-corrected) and may also belong to many different communities (mixed-membership).

A main takeaway from the paper is that possibility/impossibility of testing whether this complicated model has K = 1 or K > 1 communities boils down to the quantity ||\theta||^2 ||\theta||_1 \mu_2^2. 

The main results are:
1) Region of impossibility result for RMM-DCBM (a subset of RMM-DCMM). This shows that given any:
	(a) degree-correction factors \theta for a 1-community model
	(b) tensor P representing connection strengths between subsets of the K communities,
	(c) distribution F over mixed membership vectors, supported on {e_1,...,e_K},
	if ||\theta||^2 ||\theta||_1 \mu_2^2 --> 0 (where \mu_2 is the second eigenvalue of the matricization of P), then there is a choice of degree-correction factors \theta^* such that the K-community model given  by (P, \theta^*, F) is information-theoretically indistinguishable from the 1-community model given by \theta

2) Region of possibility result for RMM-DCBM. For any K-community model (P,\theta,F) with K > 2, such that ||\theta||^2 ||\theta||_1 \mu_2^2 / log(n)^{1.1} --> \infty, there is a test (based on estimating the degree-correction vector \theta assuming that the model is null) to distinguish it from any 1-community model.

These results extend to RMM-DCMM under some additional conditions.
main_review: The paper appears technically correct, and the connection to tensor scaling is especially nice. Furthermore, it is nice that the paper boils down the study of a complicated testing problem to whether a simple quantity ||\theta||^2 ||\theta||_1 \mu_2^2 tends to 0 or to infinity. Finally, the RMM-DCMM model introduced by the paper is a natural community detection model.
Overall, this paper is of interest to researchers specializing in community detection, so it seems on-topic for the conference.

Nevertheless, I am on the fence about acceptance, since I think that the result may only be of interest to a very small group of attendees.
From a practical point of view, the testing algorithm to distinguish H0 (1 community) from H1 (more than one community), seems to depend heavily on the null distribution being Erdos-Renyi, and my best guess is that it will not be effective on real-world data (I could be convinced otherwise if the paper had experiments on real-world data). Furthermore, the testing algorithm is computationally inefficient, as it involves an exponentially-large sum. Because of this, the experiments implemented by the paper use an entirely different algorithm -- a standard spectral algorithm based on the matricization of the adjacency tensor.

Thus, the significance of the paper appears to be mainly theoretical. The main theoretical insight that I gleaned was that if the expected degrees of the K > 2-community model and the K = 1 community model match, then their information-theoretic distinguishability depends on the quantity ||\theta||^2 ||\theta||_1 \mu_2^2, and whether it tends to 0 or to infinity sufficiently quickly.


Minor comments

* "hypergraph" in the title should be capitalized for consistency
* typos: indicies, hypergraphse, "can not" --> "cannot", "the simply quantity"

* Line 127, \theta^{(m)}, P^{(m)} \mu_2^{(m)} have not yet been defined. Please either define them or add a remark that they will be defined later and are analogues of the 3-hypergraph case.

* Line 233, write log(n)^{1.1} instead of log(n)^{1+delta}

* Line 286, "[M; b1, · · · , bK]" should be "[M; b1, · · · , bm]"

* Lines 320, 321: (3.16) and (3.15) are flipped
limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The current paper explore information-theoretic results for testing the existence of community underlying an observed hypergraph. The nodes of hypergraph are degree hetergeneous extending homogeneous results in literature. Both uniform and non-uniform hypergraphs are considered.


main_review: The results are new, original, solving a basic problem in graphical model. The results are important, and proving deeper theoretical insights on the nature of the testing problem.
limitations_and_societal_impact: There is a lack of comparison with existing results such as Yuan et al. (AoS, 2021) who explored testing limits under homogeneous setting, i.e., $\theta_1=\cdots=\theta_n$. Can the authors compare their results? For instance, setting all $\theta_i$'s to be equal, can they recover the results of   Yuan et al. (AoS, 2021) ?

Also, I am a bit confused by the definition of degree-corrected model which seems a bit different from literature. Can the authors explain why they consider such a different version?
review_title: null

Meta-review: The paper's main contribution is to provide a crisp theoretical characterization of the feasibility of detecting multiplicity of underlying communities in a degree-corrected mixed membership hypergraph model. 

It has been recognized by all reviews that this is a significant achievement that will be of interest to researchers working on stochastic block models and related inference questions. The reviewers did not give very high marks on the basis that the topic may be of interest to only a limited subset of the NeurIPS community, also pointing to the fact that the paper could be made more attractive if a compelling application was brought forward. 

The authors' reply to these comments is an argument that the problem they tackle is important in network science, an area which is relevant for NeurIPS, and a description of concrete applications to hypergraphs of co-authorships in scientific articles. The authors further point to the usefulness of their result to hierarchical clustering, and explain in greater detail how their non-polynomial time test informs the design of the polynomial test used in the experiments. 

I believe that these answers by the authors alleviate the concerns expressed by the reviewers, and suffice to justify acceptance of the paper to the conference. 






Decision: Accept (Poster)