Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper discusses how to find bipartite components in a hyper graph.  A bipartite component consists of two subsets of vertices L and R.  Bipartite implies  there is minimal connection within L as well as within R.  Component implies that there is minimal connection between vertices in L union R and vertices outside.  

The algorithm is based on diffusion process to find sets with small hyper graph bipartiteness.  The paper provides a couple of theorems for the existence of a polynomial algorithm.  Experiments are conducted on both synthetic as well as real-world datasets, including Penn Treebank and DBLP.
main_review: On the plus side, the paper gives a formal treatment of the problem.  It is written rigorously, if rather densely, but the key ideas come across.  It is also good that the experiments explore both synthetic datasets (to look at the runtime with increasing size) as well as real-world datasets (to explore potential applications).

One weakness of the paper is that it is light on applications.  It is not clear to me whether there will be many occasions in which we'd be looking for bipartite components in a hyper graph.  While the paper gives an example on Peen Treebank, claiming that it is achieving good performance given that it is an unsupervised general purpose algorithm, this seems to still be a contrived example.  The discussion on DBLP is similarly vague, saying that the algorithm can separate authors from conferences, but I imagine that task wouldn't really be an actual application.

Another point is the computational complexity relative to the baseline clique cut algorithm, which is much faster (by an order of magnitude or thereabout).  While the proposed method produces "some" improvement, some discussion on whether the difference justifies the large increase in computational cost.
limitations_and_societal_impact: The paper itself does not contain an ethics statement, though the authors acknowledged that they have read the ethics guidelines.

As suggestions for improvements, the paper would be a lot stronger if it could be motivated by real applications that someone actually wants to solve.  As of now the evaluations are rather contrived.

There should also be some discussions on the large increase of computational time relative to CC, and what could be done about it or why the increase is justified.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper proposes a diffusion-based algorithm for finding bipartite components in hypergraphs. The work rigorously analyzes the algorithm and provides theoretical guarantees. 
main_review: This paper uses a diffusion-based algorithm that requires multiple iterations for convergence.  Therefore, it comes with high computational complexity. The complexity analysis of algorithm is missing. Further, the empirical time complexity (Table 1) shows that the algorithm is not scalable to large-scale networks with millions of nodes where the problem is much more relevant. More experimental results and computation complexity justification is required to assess the practical significance of the work. The work extends the theoretical understanding of the diffusion process, especially for hyper-graphs which is a major strength of this work. 


limitations_and_societal_impact: N/A
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper proposes a polynomial-time algorithm that finds densely connected bipartite components in a hypergraph. The algorithm is based on a heat diffusion process generalized from graphs to hypergraphs. Cheeger-type approximation guarantee is established. Empirical results show that the new method has superior performance for both synthetic and real hypergraphs.
main_review: Hypergraphs and related nonlinear Laplacian operators received renewed interests recently in both machine learning and applied mathematics communities. The heat diffusion process studied in this paper is a nice addition, in particular it applies to find bipartite components in hypergraphs, which is a different application from most previous works. At the same time, the nonlinear operator considered in this work is simple and intuitive.

Technical analyses is this paper appear to be clear and solid. Overall I think the paper is well written and it solves an interesting problem. Empirical results are promising and further support the usefulness of the proposed method. 

I have a few minor comments:

- line 129-131: Why is it intuitive that the rate of change should involve only the maximum and minimum values? Apparently this is the simplest case, but in more complex settings (e.g. when one models more complex higher-order relations as in [22]) can it depend on other node values as well? The formulation considered in this paper seems to correspond to hypergraphs modelled by all-or-nothing cut (or equivalently the unit cut-cost in [13]). Can the heat diffusion process be generalized to more complex higher-order relations among nodes within a hypergraph? More explanations are needed.

- Baseline: Following footnote 4, another baseline could be $f_1(\mathcal{J}_G)$. Although the authors explained in the supplementary material that the worst-case performance guarantee using $f_1(\mathcal{J}_G)$ is scaled by a factor of $r$ the rank of hyperedge, it would provide additional information to the reader about the practical importance of the new method.

- Synthetic experiments: Since you have the ground-truth information can you also show the F1 scores?
limitations_and_societal_impact: I cannot think of any potential negative societal impact based on this work.
review_title: null

Meta-review: The paper provides a clean solution for a new problem, but the motivations and applications of the paper is not completely clear.  The results is not straightforward. The applications and motivating examples presented in the paper, on the other hand, are not  convincing.  Given the results are mathematically interesting and the area is of interest to the community, the paper could be accepted as a poster.
Decision: Accept (Poster)