Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: In this work the authors provide a local diffusion framework to a general class of hypergraphs, whose cut cost functions covers numerous important special cases. The extension of the flow to this set of hypergraphs is well-thought out, and enables an optimization framework that can scale to large graphs in practice. The authors provide experiments, both on synthetic and real-world datasets. 
main_review: In recent years, due to the importance of motif-based analysis of real-world networks, community detection in hyper-graphs has received a lot of attention. Furthermore, extensions of standard cut functions have been considered, including general sub-modular cut function costs. The local community detection problem has not received a lot of attention, compared to the more general hyper-graph partitioning problem. The authors propose an interesting local diffusion framework on hypergraphs, The seed nodes receive excess mass that is spread in an optimized way to produce low cost routings. This results in an interpretable primal-dual formulation that is solved using an alternating minimization method. Under mild conditions, the authors prove a Cheeger-type result for the resulting partition. The interesting part is the dependence of the parameters alpha,beta as the dependence on the conductance is as expected.  The authors perform a set of convincing experiments to illustrate the power of their framework both on synthetic and real data. Furthermore, they show on a motif-aware partitioning problem that the submodular cost function can yield significant practical improvements, e.g., in node ranking. While there could exist more baselines in the experimental section, [9] is a competitive state-of-the-art method that lies close to the proposed method. 
limitations_and_societal_impact: There exists no obvious negative societal impact.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: The paper studies the local hyper-flow diffusion problem, and presents a local hyper graph clustering algorithm that achieves a Cheeger-type approximation guarantee. 
main_review: The paper studies local algorithms for finding a sparse cut in a hypergraph. Both of the studied problem and the presented algorithm are interesting. The paper further presents extensive experimental studies, and the overall presentation of the paper is nice.

On the downsides, my first concern is the significance of submodular hypergraphs, and the motivation of studying such graphs isn't very clear to me. My second and major concern on this paper is on its theoretical result, i.e., Theorem 1. It is known that, in the non-hypergraph setting, a single vertex as seed is sufficient for a local algorithm to achieve a Cheeger-type guarantee, and this is also achievable for hypergraphs [17]. Unfortunately, the main result of the current submission would assume that there is a large overlap between the seed set S and the target cluster, which assumption looks very unrealistic for me.  Specifically, in order to achieve a Cheeger-type guarantee, one needs to assume that the seed set already gives a constant-factor approximation of the target set! On the other side, when the size of target cluster is large and one uses a single vertex to form the seed set S, the approximation guarantee of Theorem 1 becomes almost trivial. The paper should also clearly state the runtime of the presented algorithm. 

Also, could the authors clarify their statement on Lines 204-205 that "it is the first result that is independent of hypergraph size for general hyper graphs", given the result of [17]?

The authors should also experimentally compare their algorithm with the one presented in [17].
limitations_and_societal_impact: Not applicable.
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: The paper introduces a novel local hypergraph partitioning framework. This utilizes a new notion of diffusion defined through an optimization problem (Section 3), and allows to partition hypergraphs using several different types of cut-cost functions on the hyperedges. Of particular interest is the case of general submodular cut-cost functions, which did not appear in prior work.

A numerical algorithm to solve the optimization problem and partition the hypergraph is provided (Section 5). The algorithm is not proved to be local, however experiments are given, illustrating the performance of the algorithm and how it compares to existing approaches to the same problem (Section 6). These show that the algorithm recovers high quality solutions on both synthetic and real-world data, and does so in a seemingly local fashion, which allows for amenable runtimes. The author(s) also motivate(s) their interest in general submodular cut-cost functions by giving concrete experimental evidence that, in specific situations (with real-world data), these lead to better quality outputs.

The author(s) also give(s) theoretical guarantees on the quality of the solution, based on clearly stated assumptions (Section 4).
main_review: The paper is a solid blend of sound theory and convincing experiments.

The author(s) take(s) a principled approach to local hypergraph partitioning. Their framework is clearly explained and motivated, and they show how theoretical considerations lead to a specific choice of optimization problem. The theoretical guarantees are compelling, and their proofs are clear and sound.

The experiments are also clearly outlined, and the results therein are promising and indeed suggest that the algorithm works well in practice against relatively natural benchmarks.

While the general approach of utilizing diffusion to locally partition graph and hypergraphs certainly predates this work, the author's specific formulation and choice of algorithm is, to the best of my knowledge, new. 

The author(s) do(es) not mention limitations of their work, besides the lack of theoretical guarantees on the convergence time of the given numerical algorithm.  The absence of this kind of guarantee could be of concern, given that locality is a key feature of the work as it is presented. However, in light of the promising experiments, this does not seem to completely undermine the value of the results in the paper.
limitations_and_societal_impact: Not much is said about the limitations of the work, besides the lack of theoretical guarantees on the convergence time of the numerical algorithm given. In particular the author(s) do(es) not mathematically prove that the algorithm is local, but rather just provide(s) experimental evidence for this fact.

The author(s) do(es) not mention nor address any specific concern about possible negative effects of their work. In their defense, hypergraph partitioning methods have existed prior to this paper, and it seems unlikely that this specific line of inquiry will engender any kind of predictable negative societal impact.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: Submodular hypergraph is a generalization of hypergraph, where each hyperedge e is associated with a submodular function w_e such that w_e(0) = w_e(e) = 0. We can naturally define the notion of conductance for submodular hypergraphs by generalizing that for graphs. The main contribution of this work is a local clustering algorithm for submodular hypergraphs, where the goal is to find a vertex set with a small conductance that exists near a seed set just by looking around it.

The algorithm is based on a flow problem that transfers some amount of mass from the seed vertices to other vertices, with some regularizer that makes the problem amenable to continuous optimization. Let C be the target cluster. Then, the algorithm outputs a set of conductance O(sqrt(C)) if vol(S \cap C) / vol(C) = \Omega(1) and vol(S \cap C) / vol(S) = \Omega(1) (vol(S) is the volume of S) and some other conditions are satisfied. It is also shown that the support of the optimal solution has a small l1 norm. The authors proposed an alternating-minimization algorithm to solve the flow problem so that the number of vertices considered (= vertices with non-zero potentials) in the intermediate steps are small.

Empirical results are encouraging. The number of vertices with non-zero potentials is just a few thousands for a hypergraph with >2 million vertices. Also, the proposed algorithm outputs a set of a smaller conductance than previous methods on synthetic graphs and real-world hypergraphs when the submodular functions associated with the hyperedges are chosen properly.
main_review: Although the results are interesting, there are several reservations.
- A local clustering algorithm based on a flow problem for graphs has been already studied in [26]. The proposed algorithm is its natural (if not simple) generalization and not quite novel (maybe this is not crucial).
- The assumption vol(S \cap C) / vol(C) = \Omega(1) and vol(S \cap C) / vol(S) = \Omega(1) look quite restrictive. Can't we start with a seed vertex (rather than a seed set that non-trivially overlaps C) to output a set of a reasonably small conductance?
- The proposed algorithm must be empirically compared with recent works [17] and [27]. I guess the proposed algorithm runs much faster but I wonder which performs better in terms of the quality (conductance) of the output.

limitations_and_societal_impact: N/A
review_title: null

Meta-review: The paper extends the local flow diffusion framework of [26] to the submodular hypergraph setting,. The reviewers and AC agree that this is a solid theoretical contribution, even though it does not significantly depart from the graph analysis. More importantly, the reviewers and AC agree that the authors provide extensive and convincing experimental results.  These constitute the main strength of this submission.
Decision: Accept (Poster)