Local Hyper-Flow Diffusion
Authors: Kimon Fountoulakis
Pan Li
Shenghao Yang
Venue: NeurIPS 2021 Poster (2021)
Keywords: Hypergraph
diffusion algorithm
local graph clustering

Abstract: Recently, hypergraphs have attracted a lot of attention due to their ability to capture complex relations among entities. The insurgence of hypergraphs has resulted in data of increasing size and complexity that exhibit interesting small-scale and local structure, e.g., small-scale communities and localized node-ranking around a given set of seed nodes. Popular and principled ways to capture the local structure are the local hypergraph clustering problem and the related seed set expansion problem. In this work, we propose the first local diffusion method that achieves edge-size-independent Cheeger-type guarantee for the problem of local hypergraph clustering while applying to a rich class of higher-order relations that covers a number of previously studied special cases. Our method is based on a primal-dual optimization formulation where the primal problem has a natural network flow interpretation, and the dual problem has a cut-based interpretation using the $\ell_2$-norm penalty on associated cut-costs. We demonstrate the new technique is significantly better than state-of-the-art methods on both synthetic and real-world data.


Local Hyper-Flow Diffusion
Kimon Fountoulakis
Pan Li
School Computer Science
Department Computer Science
University of Waterloo
Purdue University West Lafayette, IN, United States panli@purdue edu
Waterloo, ON, Canada
kimon wwt.:ttooo....tssssaeeee........
Shenghao Yang
School of Computer Science
University of Waterloo Waterloo, ON, Canada
Abstract
Recently, hypergraphs have attracted a lot of attention due to their ability to capture complex relations among entities. The insurgence of hypergraphs has resulted in data of increasing size and complexity that exhibit interesting small-scale and local structure, e.g., small-scale communities and localized node-ranking around given set of seed nodes. Popular and principled ways to capture the local structure are the local hypergraph clustering problem and the related seed set expansion problem. In this work, we propose the first local diffusion method that achieves edge-size- independent Cheeger-type guarantee for the problem local hypergraph clustering while applying to a rich class of higher-order relations that covers number of previously studied special cases. Our method is based on a primal-dual optimization formulation where the primal problem has natural network flow interpretation, and the dual problem has a cut-based interpretation using the fn-m penalty on associated cut-costs. We demonstrate the new technique is significantly better than state-of-te the-ah art methods on both synthetic and wallworld data.
Introduction
Hypergraphs generalize graphs by allowing hyperedge consist of multiple nodes that capture higher-order relationships in complex systems and datasets (2). Hypergraphs have been used for music recommendation Last.fm data [3), news recommendation [4), sets of product reviews on Amazon [5), and sets of co-purchased products at Walmart [6]. Beyond the internet, hypergraphs are
used for analyzing higher-order structure in neuronal, air-traffic and food networks (78).
In order to explore and understand higher-order relationships in hypergraphs, recent work has made of cut-cost functions that are defined by associating each hyperedge with specifie set function. These functions assign specific penalties of separating the nodes within individual hyperedges. They generalize the notion of hypergraph cuts and are crucial for determining small-scale community structure The most popular cut-cost functions with increasing capability to model complex multiway relatiosshps
the unit cut-cost 12). cardinality-basee cut-cost [13 14 and general
submodular cut-cost 16). An illustration of a hyperedge and the associated cut-cost function is given in Figure In the simplest setting, all cut-cost functions take value either I (e.g., the case when = setting, the cut-costs are determined solely by the number of nodes in either side of the hyperedge (e.g., the case when = 1/2 and 72 = in Figure Ib], we obtain a cardinality-basse hypergraph.
1 in Figure lb). we obtain a unit cut-cost hypergraph. In a slightly more general
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

We refer to hypergraphs associated with arbitrary submodular cut-cost functions (e.g., the case when as general submodular hypergraphs.
7i 1/2 and 0 S 72 I 1 in Figure lb
Hypergraphs that arise from data science applications consist of interesting small-scale local structure Exploiting this structure is central to the above mentioned applica- tions on hypergraphs and related applications in machine learning and applied mathematics (18). We consider local hypergraph clustering as the task of finding a community-
such as local communities (9] [7]
cluster around a given set of seed nodes, where nodes in the cluster are densely connected to each other while relatively isolated to the rest of the graph. One of the most powerful primitives for the local hypergraph clustering task is the graph diffusion. Diffusion on graph is the process of spreading a given initial mass from some seed node(s) to neighbor nodes using the edges of the graph. Graph diffusions have been successfully employed in the industry. for example, both Pinterest and Twitter use diffusion methods for their recommendation systems [T]. Google uses diffusion methods to perform clustering query refinements (22). Let us not forget PageRank [3 24). Google's model for their search engine.
Empirical and theoretical performance of local dif- fusion methods is often measured on the problem
of local hypergraph clustering [9|25]] 26) Existing local diffusion methods only directly apply to hyper-
w.((vs)) =x (c(l),11))) =
graphs with the unit cut-cost [1727]. J For the slightly more general cardinality -based cut-cost, they rely on graph reduction techniques which result in a rather pessimistic lige-size-dependent approximation er- ror 13 27 28). Moreover, none of the existing methods capable of processing general submod- ular cut-costs. In this work, we are interested in designing a diffusion framework that (i) achieves stronger theoretical guarantees for the problem of local hypergraph clustering, (ii) is flexible enough to work with general submodular hypergraphs, and (iii) permits computationally efficient algorithms. We propose the first local diffusion method that simul- taneously accomplishes these goals.
welle, 1g))
(a) Network motif (b) Hyperedge and cut-cost we
Figure 1: A food network can be mapped into a hypergraph by taking each network pattern in (a) as hyperedge (8). This network pattern captures carbon flow from two preys (U1, U2)
to two predators (23, 24). (b) is a hyperedge associated with cut-cost we that models their relations: We is a set function defined over the node set e s.t. We (fv:t) = 21 for i = 1, 2, 4, wa(for, U23) )= = 72, wo ((U), 033)
wa wa([vi, (v((1,) = 1 and w.(S) = (e)()))) for S S e. We becomes the unit cut-cost when
In what follows we describe our main contributions and previous work. In Section 2 we provide prelim-
"1 = 72 = 1; We is cardinality based if "1 = 1/2 and 722 = 1; more generally, we is submodular if 71 1/2 and 0 I 72 S 1. The specific choices depend on the application.
inaries and notations. In Section 3 we introduce our diffusion model from a combinatorial flow perspec- tive. In Section 4 we discuss the local hypergraph clustering problem and Cheeger-type quadratic ap- proximation error. In Section we perform experiments using both synthetic and real datasets.
1.1 Our main contributions
In this work we propose a generic local diffusion model that applics to hypergraphs characterized by rich class of cut-cost functions that covers many previously studied special cases, e.g., unit, cardinality-baa based and submodular cut-costs. We provide the first lagge-izze-indpendeee approximation error for the problem of local hypergraph clustering using any of these cut-costs. In particular, assume that there exists a cluster C' with conductance & (CC), and assume that we are given set of seed nodes that reasonably overlaps with C, then the proposed diffusion model can be used to find a cluster Ć' with conductance at most O(v$(C) (CC) (in the appendix we show that an f--norm version of the proposed model can achieve (()(C)) asymptotically). Our hypergraph diffusion model is formulated as a convex optimization problem. It has a natural combinatorial flow interpretation that generalizes the notion of network flows over hyperedges. We show that the optimization problem can be solved efficiently by an alternating minimization method. In addition, we prove that the number of nonzero nodes in the optimal solution is independent of the size of the hypergraph, and only depends on the size of the initial mass. This key property ensures that our algorithm scales well in practice for large datasets. We evaluate our method using both synthetic and real-world data. We show that our method improves accuracy significantly for hypergraphs with unit, cardinarlity-bar based and general submodular cut-costs for local clustering.
Cheeger-type

---

1.2 Previous work
Recently, clustering methods on hypergraphs received renewed interest. Different methods require different assumptions about the hyperedge cut-cost, which can be roughly categorized into unit cut-cost, cardinality-
(and submodular) cut-cost and general submodular cut-cost. Moreover, existing methods can be either global, where the output is not localized around a given set of seed nodes, or local, where the output a tiny cluster around a set of seed nodes. Local algorithms are the only scalable ones for large hypergraphs, which is our main focus. Many works propose global methods and thus they are not scalable to large hypergraphs 878 17 29 38), Local diffusion- methods are more relevant to our work [9 23) In particular, iterative hypergraph min-cut methods for the local hypergraph clustering problem can be adopted 13 However, these methods require in
theory and in practice large seed set, i.e., they are not expansive and thus cannot work with one seed node. The expansive combinatorial diffusion (25) is generalized for hypergraphs [27]. which can detect target cluster using only one seed node. However, combinatorial methods have large bias towards low conductance clusters as opposed to finding the target cluster (39] The most relevant paper to our work is (9]. However, the proposed methods in [9] depend on reduction from hypergraphs to directed graphs. This results in an approximation error for clustering that is proportional to the size of hyperedges and induces performance degeneration when the hyperedges are large. In fact, none of the above approaches (including global and local ones) has an edge-size-indepent error bound for even simple cardinality-basel hypergraphs. Moreover, existing local approaches do not work for general submodular hypergraphs.
approximation
2 Preliminaries and Notations
Submodular function. Given set S, we denote 2 the power set of S and |S] the cardinality of S. A submodular function F: 2 IR is set function such that F(A) + F(B) 2 F)AUB)+F(AA) for any A, B C S.
Submodular hypergaph. A hypergraph H- = (V, F) is defined by a set of nodes V and set of hyperedges E C 22,iic., i.c., each hyperedge e E E' is subset of V. A hypergraph is termed submodular if every E E' is associated with submodular function we 2 - R20 [15). The weight w. (S) indicates the cut-cost of splitting the hyperedge e into two subsets, S and e S.S. This general form allows us describe the potentially complex higher-order relation among multiple nodes (Figure I]. A proper hyperedge weight we should satisfy that we (0) = we(e) = 0. To ease notation we extend the domain of we to 2 by setting (S) == we(S n e) for any S C V. We assume without loss of generality that we is normalized by Ur- = maxsçe (S). so that (S) E [0. 1] for any S V. For the sake of simplicity in presentation, we assume that 02 = 1 for all e submodular hypergraph is written as H = (V, E, W) where W == {we, Oe J.E Note that when we (S) 1 for any S E 2*) (0, e), the definition reduces to unit cut-cost hypergraphs. When (S) only depends on [S], it reduces cardinality-baae -hased cut-cost hypergraphs.
Vector/Function on V or E. For a set of nodes S C V, we denote 1s the indicator vector of S, i.e., [1s], = 1 if E S and O otherwise. For a vector E R we write zr(S) == Eves Tip where x. in the entry in that corresponds to U E V. We define the support of x as supp(æ)) == {u E V|z, # 0}. is defined analogously. We refer to function over nodes x : V + R and its explicit representation as |VI dilmdemenii vector interchangeabll.
The support of vector in IR A
Volume, cut, conductance. Given a submodular hypergraph H = (V. W). the degree of a node v defined as d, := He E E e)}. We reserve d for the vector of node degrees and D diag(d). We refer to vol(S) == d(S) as the volume of S V. A cut is treated as a proper subset C C V, or a partition (C, C)) where C V C. The cut-set of C. is defined as ac == {e Ele n C #
0, enc # 0): the cut-size of C is defined as vol(OC)= ;= Eesoc Dew. WCC) = = (C). The
conductance of a cut C in H (C) == min (vil(vol(C),..) voll V(O
voll (CC)
Flow. A flow routing over a hyperedge e is a function re e + R where (v) specifies the amount of mass that flows from {f} to \ {o} over e. To case notation V by identifying re(w)= = 0 for e g e, so ra is treated as a function r. V + R or equivalently V dimennsolll vector. The net (out)flow at a node is given by E (v). Given routing
extend the domain of r. to
'This is without loss of generality. In the appendix we show that our method works with arbitrary dz 0.
3

---

function re and a set of nodes S C V, a directional routing on e with direction S + e S is represented by rS), which specifies the net amount mass that flows from \ S. A routing te is called proper if it obeys flow conservation, i.e., r² le = O. Our flow definition generalizes the notion of network flows to hypergraphs. We provide concrete illustrations Figure 2
2
Y3
+10
13
2
(a) Flows graph
(b) Hyperedge routing
(c) Flows hypergraph
Figure 2: Illustration of proper flow routings. The numbers next to each node correspond to entries in the flow routing Тe over a (hyper)edge e. We assign the same color to a (hyper)edge and its associated flow values. Our flow definition is a natural generalization of graph edge flow where re(v) = +f if and only if v e, i.e., V is incident to e, where f and the sign determine the amplitude and direction of the flow over e. In Figure 2a the net (out)flow at node Uy is given by EeEg Te (0x) = 1 2 - 3 = -4. In Figure 2b the directional flow from {ui to {22, Va Va. Us} over this hyperedge equals - 1; similarly, the directional flow from (1), 02, v4 to (va, us} equals 3 + 2 = 4. In Figure 2c the net (out)flow at node Vi is given by LeEF (e(g)) = 3 3-2 1.
3 Diffusion as an Optimization Problem
In this section we provide details of the proposed local diffusion method. We consider diffusion process as the task of spreading mass from a small set of seed nodes to a larger set of nodes. More precisely, given hypergraph H = (V, E, W). we assign each node a sink capacity specified by a sink function T,, i.e., node is allowed to hold at most (v)) amount of mass. In this work we focus on the setting where [vv = de, so that a high-degree node that is part of many hyperedges can hold more mass than low-degree node that is part of few hyperedges. Moreover, we assign each node some initial mass specified by a source function A, i.e., node v holds A(v) amount of mass at the start of the diffusion. In order to encourage the spread of mass in the hypergraph, the initial mass on the seed nodes is larger than their capacity. This forces the seed nodes to diffuse mass to neighbor nodes remove their excess mass. In Section 4 we will discuss the choice of Á to obtain good theoretical guarantees for the problem of local hypergraph clustering. Details about the local hypergraph clustering problem are provided in Section 4
Given a set of proper flow routings Te for E E E, recall that EeER Te(u) (v) specifies the amount of net (out)flow node v. Therefore, the vector m A EeEE Pe gives the amount of net mass at each node after routing. The excess mass at node ex(u) == max (m, du, 0}. In order to force the diffusion of initial mass we could simply require that ex(u) = 0 for all E V, or equivalently, A E.EE Te S d. But provide additional flexibility in the diffusion dynamics, we introduce hyper-parameter a 2 0 and we impose a softer constraint
Eeegre Te S Ad+aDz where & E V is an optimization variable that controls how much excess mass allowed on each node. In the context of numerical optimization, we show in Section that a allows a reformulation which makes the optimization problem amenable to efficient alternating minimization schemes.
Note that so far we have not yet talked about how specific higher-order relations among nodes within hyperedge would affect the flow routings over it. Apparently, simply requiring that the re 's obey flow conservation (i.e., r 1e = 0) similar to the standard graph setting is not enough for hypergraphs. An important difference between hyperedge flows and graph edge flows is that additional constraints on re are in need. To this end, we consider re = dePe for some &e E R4 and Pe E Be, where
B. = {pe E RR/|
(c(S) S w.(S)), VS V, and (V) = (v()))
the base polytope [40] for the submodular cut-cost we associated with hyperedge e. is straight- forward to see that (v) = 0 for every & e and r. le = 0, so re defines a proper flow routing over e. Moreover, for any e C V, recall that (S) represents the net amount of mass that moves from S to e S over hyperedge e. Therefore, the constraints (S) < (S) for S C mean that the directional flows rS) are upper bounded by submodular function &.w. (S). Intuitively, one may think of de and Pe as the scale and the shape of Te, respectively.

---

The goal of our diffusion problem is to find low cost routings Te E B. for e E E such that the capacity constraint A - Te I d - oDz is satisfied. We consider the (weighted) 2n-nomm of @ and as the cost of diffusion. In the appendix we show that one readily extends the fg-norm to e--norm for any p 2 2. Formally, we arrive at the following convex optimization formulation (input: the source function A, the hypergraph H = (V, E, W). and a hypper-parameter d):
min dE !
3 .EE
2
Σ .EV
2 d
d
s.t. A
Σ eE
re d oD E Be, E. (1)
2
We name problem Hyper-Flow Diffusion (HFD) for its combinatorial flow interpretation we discussed above. The dual problem of [ is:
(T)
max ZERI IV
(A - -
Σ (x)) 2
0 Σ 2
(2)
CEE
DEY
where Se in (2) is the support function of the base polytope B. given by fe(z) = ma o fe is also known as the Lovász extension of the submodular function w..
We provide a combinatorial interpretation for (2) and leave algebraic derivations to the appendix. For the dual problem, one can view the solution as assigning heights to nodes, and the goal is to separate/cut the nodes with source mass from the rest of the hypergraph. Observe that the linear term in the dual objective funetion encourages raising x higher others. The cost (z) captures the discrepancy in node heights over a hyperedge e and encourages smooth height transition over adjacent nodes. The dual solution embeds nodes into the nonnegative real line, and this embedding is what we actually use for local clustering and node ranking.
the seed nodes and setting it lower on
4 Local Hypergraph Clustering
In this section we discuss the performance of the primal-dual pair T 2 respectively, in the context of local hypergraph clustering. We consider a generic hypergraph
(V, E, W) with submodular hyperedge weights W {We, )e)ee E. Given set of seed nodes S c V. the goal of local hypergraph clustering is to identify a target cluster C C V that contains or overlaps well with S. This generalizes the definition of local clustering over graphs (41). To the best of our knowledge, we the first one to consider this problem for general submodular hypergraphs. We consider a subset of nodes having low conductance as a good cluster, i.e., these nodes are well-connected internally and well-separated from the rest of the hypergraph. Following prior work on local hypergraph clustering, we assume the existence of an unknown target cluster C with conductance (CC'. We prove that applying sweep- cut to an optimal solution & of (2) returns a cluster Ö whose conductance is at most quadratically worse than (CC.. Note that this result resembles Cheeger-type approximation guarantees of spectral clustering in the graph setting (42), and it is the first result that is independent of hyperedge size for general hypergraphs. We keep the discussion at high level and defer details to the appendix, where we prove a more general, and stronger, i.e., constant approximation error result when the primal problem is penalized by the f--norm for any p 2.
In order start diffusion process we need to provide the source mass A. Similar to the p-norm flow diffusion in the graph setting (26). we let
dd, i otherwise,
A(v) 0
where S is a set of seed nodes and 8 1. Below, we make the assumptions that the seed set S and the target cluster C' have some overlap, there is constant factor of vol(C') amount of mass trapped in C' initially, and the hyper-parameter a is not too large. Note that Assumption 2 is without loss of generality: if the right value of ò is not known apriori, we can always employ binary search to find good choice. Assumption 3 is very weak as it allows a to reside in an interval containing 0. Assumption 1. vol(Snor C) avol(C) and vol(S C) 2 (vol(S) for some a, B (0, 1]. Assumption 2. The source mass A as specified in B satisfies 8 = 3/a, so ACC) 2 3yol(C).
Assumption 3. satisfies 0 S (B
Let be an optimal solution for the dual problem (2) For define the sweep sets S, == {u E V &. 2 h). We state the approximation property in Theorem
5

---

Theorem 1. Under Assumptions
2 3
there exists h >> O such that 4(S)) & O(V
Some previous works on local hypergraph clustering provide an approximation guarantee by focusing on a specific setting when the seed set S contains precisely one seed node, e.g., [9 177. However, they rely on different assumptions about the seed node which may not hold in general. For example, [17] assumes that the seed node is not neighbor of any node not belonging to the target cluster. Even in the classical graph setting, establishing local clustering guarantee based on diffusing mass from a single node requires assuming that a good seed node has been selected from proper subset of the target cluster (42) On the other hand, our theoretical framework is more natural in the sense that Theorem 1 applies to any set of seed node(s) as long as it has nonempty intersection with the target. We view the a in the denominator of the bound as the price we pay for being certain that the approximation guarantee holds for an arbitrary seed set. The empirical experiments in Section show that our method has superior performance practice even when only one seed node is used.
One of the challenges we face in establishing the result in Theorem]] is making sure that our diffusion model enjoys not only good clustering guarantees but also practical algorithmic advantages. This is achieved by introducing the aaper-parameter a to our diffusion problem. We will demonstrate how a helps with algorithmic development in Section 5, but from a clustering perspective, the additional flexibility given by a > () complicates the underlying diffusion dynamics, making it more difficult to analyze. Another challenge is connecting the Lovász extension fz(x) in ( with the conductance of a cluster. We resolve all these problems by combining generalized Rayleigh quotient result for submodular hypergraphs [13]. primal-dum dual convex conjugate relations between ( and 2 and a classical property of the Choquet integral/Lovás extension.
Let (d, f, 2) be an optimal solution for the primal problem (T). locality (i.e., sparsity) of the optimal solutions, which justifies why HFD is a local diffusion method.
We state the following lemma on the
Lemma 2. (supp()) S vol(supp($)) I ||]|i: moreover, vol(supp(2)) = vol(supp($)) if > O.
Optimization algorithm for HFD
We use a simple Alternating Minimization (AM) 45 method that efficiently solves the primal diffusion problem ( For E, we define diagonal matrix Ae E I x|VI such that [Ac]u.e if v E and 0 otherwise. Denote := {(0, r) re Be Ve E E}. The following Lemma allows us to cast problem ① to an equivalent separable formulation amenable to the AM method.
Lemma 3. The following problem is equivalent to ① for any > O, in the sense that (6) f, is optimal in for some & IR if and only if (δ, 8) is optimal in (4) for some 8 2eer R VI.
Σ 2
1
1 ||se -ell)) s.t. (0, CC A- Σ se S d, Se, = 0, & e.
min 00r,5
o² +
(
(4)
CEE
EEE
The AM method for problem Algorithm []] The first sub-problem corre- sponds to computing projections to a group of cones, where all the projections can be computed in parallel. The computation of each projection depends on the choice of base polytope B.. If the hyperedge weight we is unit cut-cost, B. holds special struc- tures and projection can be computed with O(le log (el) (36). For general Be. a conic Fujishige-Wood Wolfe minimum norm algorithm can be adopted to obtain the projection (36). The second sub- problem in Algorithm [ can be easily computed in closed-form. We pro-
given in
Algorithm 1 Alternating Minimization for 4
Initialization:
(0)) : 0, : 82
0, (0) = Dー A. AA d4 Ve E E.
For k = 1,1, do:
(G (((t))))))) = argnin ( + -1 - -re rrl13)
(0.r)EC EE
8 (l+1) argmin
>
||oc ((+11) 113
R
s.t. A
Σ
Se d, 80,0 = Vo
eEE
vide more information about Algorithm I and its convergence properties in the appendix.
We remark that the reformulation for a > 0 is crucial from an algorithmic point of view. a = 0. then the primal problem (I) has complicated coupling constraints that are hard to deal with. In this

---

case, one has to resort to the dual problem 2 However, problem (2) has nonsmooth objective function, which prohibits applicability of optimizatiin methods for smooth objective functions. Even though subgradient method may be applied, we have observed empirically that its convergence rate is extremely slow for our problem, and early stopping results in a bad quality output.
Lastly, as noted in Lemma 2 the number of nonzeros in the optimal solution is upper bounded by ||||| In Figure 3 we plot the number of nodes having positive excess (which equals the number of nonzeros in the dual solution œ) at every iteration of Algorithm[] [ Figure iindicates that Algorithm I strongly local, meaning that it works only on small fraction of nodes (and their incident hyperedges) as opposed to producing dense iterates. This key empirical observation has enabled our algorithm scale large datasets by simply keeping track of all active nodes and hyperedges. Proving that the worst-case running time of AM depends only on the number of nonzero nodes at optimality as opposed to size of the whole hypergraph an open problem, which we leave for future work.
FigureBindicates
3,000
30,000
2,000
20,00
# nonoeece: per itenatio
1,000
nonsenee per
10.00
# nonzeroo per
# nonerence optimality
nonsenve at optimality
# honzeros optimality
50
100
150
200
100
200
50
100
150
200
(a) Cluster 12 - Gift Cards
(b) Cluster 18- Magazine Subs.
(c) Cluster 24 Prime Pantry
Figure The blue solid line plots the number of nonzeros in the dual solution x over 200 iterations of Algorithm| [ when it is applied to solve HFD) on the Amazon-reviews hypergraph for local clustering. See Section 6.2 for details about the dataset. The error bars show standard deviation over trials. In each trial we pick a different seed node and set the same amount of initial mass. The black dashed line shows the average number of nonzeros at optimality. The algorithm touches only small fraction of nodes out the total 2,268, 264 nodes in the Amazon-reviews dataset.
6 Empirical Results
In this section we evaluate the performance of HFD for local clustering, First, we carry out experiments on synthetic hypergraphs with varying target cluster conductances and varying hyperedge sizes. For the unit cut-cost setting, we show that HFD is more robust and has better performance when the target cluster is noisy; for a cardinality-bant approximation guarantee is important for obtaining good recovery results. Second, we carry out experiments using real-world data, We show that HFD significantly outperforms existing ofate-of- the-art diffusion methods for both unit and cardinality- cut-costs. Moreover, we provide compelling example where specialized submodular cut-cost necessary for obtaining good results. Code that reproduces all results is available at htttt::://// tigtthhu.... com/ s- s-mn//sh-aa h--hh-yagg/ie
cut-cost setting, we show that the edge-size-independen
6.1 Synthetic experiments using hypergraph stochastic block model (HSBM)
The generative model. We generalize the standard k-uniform hypergraph stochastic block model (kHSBM) 44) to allow different types of inter-cluster hyperedges appear with possibly different probabilities according to the cardinality of hyperedge cut. Let V = (1.2..... ......,. be set of nodes and let & 2 2 be the required constant hyperedge size. We consider kHSBM with parameters k. n, p. 93- j 1,2,.... ... [k/2]. The model samples k-uniform hypergraph according to the following rules: (i) The community label o, {0, 1} is chosen uniformly random for e V ( Each size l subset (U1, 02,02... u2.... ..... mx) of V appears independently as hyperedge with probability
P(cE = p of = = = Gua:
min(k Σ ou, Ei o. }
If k or all qj's are the same, then we obtain the standard two-block kHSBM. We use this setting to evaluate HFD for unit cut-cost. If 's are different, then we obtain a cardinality-basee kHSBM.
We consider two blocks for simplicity. In general the model applies any number of blocks.

---

In particular, when 91 22 .... 2[//2j- it models the scenario where hyperedges containing similar numbers of nodes from each block are rare, while small noises (e.g.. hyperedges that have one or two nodes in one block and all the rest in the other block) are more frequent. We use >> (j- j 2 2, to evaluate HFD for cardinality-ban for example the Poisson degree-corren size heterogeneity. In our experiments we focus on KHSBM because it allows stronger control over hyperedge sizes. We provide details on data generation in the appendix.
cut-cost. There are other random hypergraph models, HSBM (45) that deals with degree heterogeneity and edge
Task and methods. We consider the local hypergraph clustering problem. We assume that we are given a single labelled node and the goal is to recover all nodes having the same label. Using single seed node the most common (and sought-after) practice for local graph clustering tasks. We test the performance of HFD with two other methods: (i) Localized Quadratic Hypergraph Diffusions (L.H) [9. which can be seen as hypergraph analogue of Approximate Personalized PageRank (APPR); (ii) ACI. (42), which is used to compute APPR vectors on standard graph obtained from reducing hypergraph through star expansion (46]
Cut-costs and parameters. We consider both unit cut-cost, i... w.(S) = Sff + 0 and S + 0, and cardinality cul-cost (8) = min nel, le SID/Lel//2.. HFD that uses unit and cardinality cut-costs are denoted by U-HFD and C-HFD, respectively. LH also works with both unit and cardinality cut-costs and we specify them by U-LH and C-LH, respectively. For HFD, we initialize the seed mass so that ||] is constant factor times the volume of the target cluster. We set = 0.01. We highly tune LH by performing binary search over its parameters K and 6 and pick the output cluster having the lowest conductance. For ACI we use the same parameter choices as in [9. Details on parameter setting are provided in the appendix.
Results. For each hypergraph, we randomly pick a block as the target cluster. We run the methods 50 times. Each time we choose a different node from the target cluster as the single seed node.
Unit cut-cost results, Figure shows local clustering results when we fix k but vary the con- ductance of the target cluster (i.e., constant p but varying q1). Observe that the performances of all methods become worse as the target cluster becomes more noisy, but U-HFD has significantly better performance than both U-LH and ACL when the conductance of the target cluster is between 0.2 and 0.4. The reason that U-HFD performs better is in part because requires much weaker conditions for the theoretical conductance guarantee to hold. On the contrary, LHH assumes upper bound on the conductance of the target cluster (9]. This upper bound is dataset-dependent and could become very small in many cases, leading poor practical performances. We provide more details in this perspective in the appendix. ACL with star expansion is a heuristic method that has no performance guarantee.
Output conductance
C-HPD
1.0
C-H
Output F1 score
0.9
0.4
ACL
0.8
0.3
0.7
0.2
0.6
U.HPD
U-TH
0.5
ACL
0.1
0.2
0.3
0.4
0.5
0.1
0.2
0.3
0.4
0.5
Ground-truth conductance
Ground-truth conductance
Figure 4: Output conductance and Fl against ground- truth conductance
Cardinality cut-cost results. Figure sshows the median (markers) and 25-75 percentiles (lower-uppe upper bars) of conductance ratios (i.e., the ratio between output conductance and ground-truth conductance, lower better) and scores for different methods for k E (3, 4, 5, 6). The target cluster for each
'There are other heuristic methods which first reduce a hypergraph a graph by clique expansion and then apply diffuuson methods for standard graphs. We did not compare with this approach because clique expansion often results in dense graph and consequently makes the computation slow. Moreover, it has been shown in that clique expansion did not offer significant performance improvement over star expansion.
8

---

has conductance around 0.3 For & = 3, unit and cardinality cut-costs are equivalent, therefore all methods have similar performances. As increases, cardinality cut-cost provides better performance than unit cut-cost in both conductance and F1. However, since the theoretical approximation guarantee of C-L.H depends on hyperedge size (9). there a noticeable performance degradation for C-LH when we increase k = 3 to k = 4. On the other hand, the performance of C-HFD appears to be independent from k, which aligns with our conductance bound in Theorem
18
U-HED
1.00
C-HFD
1.6
U-LH
F1 score
CAT
ACL
0.92
U-HPD
0.36
CHIFD
1.2
D-LII
0.84
C-LH
ACL
1:
0.50
3
k 5
Figure 5: Conductance ratio and Fl on k-uniform hypergraphs
6.2 Experiments using real-world data
We conduct extensive experiments using real-world data. First, we show that HFD has superior local clustering performances than existing methods for both unit and cardinality- based cut-costs. Then, show that general submodular cut-cost (recall that HFD is the only method that applies this setting) can be necessary for capturing complex high-order relations in the data, improving F1 scores by up 20% for local clustering and providing the only meaningful result for node ranking. Because of limited space, in the appendix we show additional local clustering experiments on two additional datasets, where our method improves Fl scores by 8% on average for 13 different target clusters.
Datasets. We provide basic information about the datasets used in our experiments. Complete descriptions provided in the appendix. Amazon-reviews (V) 2,262,222244 2,64, |E| = 4,285, (,633) [13 47 In this hypergraph each node represents a product. A set of products are connected by a hyperedge if they are reviewed by the same person. We product category labels as ground truth cluster identities. We consider all clusters less than 10,000 nodes. Trivago-clicks ([V 172,738, |E] accommodations/oottll.. A set of nodes are connected by hyperedge if a user performed "click-out" action during the same browsing session. We use geographical locations as ground truth cluster identities. There are 160 such clusters, and filter them using cluster size and conductance. Florida food network ([V) = 128, E = 141,233 1,233) (8] Nodes in this hypergraph correspond different species or organisms that live in the Bay, and hyperedges correspond to transformed motifs (Figure [ of the original dataset. Each species is labelled according its role in the food chain: producers, low-level consumers, high-level consumers.
233,202) (5 The nodes in this hypergraph
Methods and parameters. We compare HFD with LH and ACL There is a heuristic nonlinear variant of LH which is shown to outperform linear LH in some cases (9. Therefore we also compare with the same nonlinear variant considered in (9]. We denote the linear and nonlinear versions by LH-2.0 and LH-1.4, respectively. We
0.0001 for HFD and we set the parameters for LH-2.0, LH-1.4 and ACL as suggested by the authors (9). More details on parameter choices appear in the appendix. We prefix methods that use unit and cardinality-based cut-costs by U- and C-, respectively.
Experiments for unit and cardinality cut-costs. For each target cluster in Amazon-review and different node the singe seed node 6 We report the median Fl scores of the output clusters in Table and Table For
Trivago-clicks, we run the methods multiple times, each time
*See the appendix for similar results when we fix the target cluster conductances around 0.2 and 0.25, respectively. These cover a reasonably wide range of scenarios terms of target conductance and illustrate the performance of algorithms for different levels of noise.
We also tried flow- imwroveeeee method for hypergraphs [33. but the method very slow in experiments, so we only used it for small datasets. See appendix performance of existing methods, therefore, we omitted from comparisons on larger datasets.
results. The flow-improve method did not improve the
We show additional results using seed sets of more than node in the appendix.

---

Amazon-reviewwe we only compare the unit cut-cost because it is both shown in 19 and verified by our experiments that unit cut-cost more suitable for this dataset. Observe that U-HFD obtains the highest F1 scores for nearly all clusters. In particular, U-HFID significantly outperforms other methods for clusters 12, 18, 24, where we see an increase in F1 score by up to 52%. For Trivago-clicks. C-HFD has the best performance for all but one clusters. Among the rest of all other methods, U-HFD) has the second highest Fl scores for nearly all clusters. Moreover, observe that for each method (i.e.. HFD, LH-2.0, LH-1.4), cardinality cut-cost leads to higher Fl than its unit cut-cost counterpart.
Table 1: Fl results for Amazon-reviews network
Method
2
15
17
24
25
U-HFD
0.45
0.09
0.65 0.92
0.04
0.10
0.80
0.81
0.09
U-LH-2.0 0.23
0.07
0.23 0.29
0.05
0.06
0.21
0.28
0.05
U-LH-114 0.23
0.09
0.35 0,40
0.00
0.07
0.31
0.35 0.06
ACL
0.23
0.07
0.22
0.25
0.04
0.05
0.17
0.20
0.04
Table 2: Fl results for Trivago-clicks network
Method
KOR
ISL PRI
UA-43
VNM HKG MLT
GTM
UKR
EST
U-HFD
0.75 0.99 0.89
0.85
0.28
0.82
0.98
0.94
0.60
0.94
C-HFD
0.76
0.99 0.95
0.94
0.32
0.80
0.98
0.97
0.68
0.94
U-LH-2.0
0.70
0.86 0.79
0.70
0.24
0.92
0.88
0.82
0.50
0.90
C-LH-2.0
0.73 0,90 0.84
0.78
0.27
0.94
0,96
0.88
0.51
0.83
U-LIH-1.4
0.69 0.84 0.80
0.75
0.28
0.87
0.92
0.83
0.47
0.90
C-LH-1.4 0.71
0.88 0.84
0.78
0.27
0.88
0.93
0.85
0.50
0.85
ACL 0.65 0.84 0.75
0.68
0.23
0.90
0.83
0.69
0.50
0.88
Experiments for general submodular cut-cost. In order to understand the importance of specialized general submodular hypergraphs we study the node-ranking problem for the Florida Bay food network
using hypergraph modelling shown in Figure [ We compare HFD using unit (U-HFD, 71 = 722 1),
cardinality-basee (C-HFD, 71 = 1/2 and 7/2 1) and submodular (S-HFD, 7/2 = 1/2 and 72- = 0) cut-costs. Our goal is to search the most similar species of a queried species based on the food-network structure. Table shows that S- HFD provides the only meaningful node ranking results. Intuitively, when 72 = 0, separating the preys U1, U2 from the predators 03 Bg incurs 0 cost. This encourages S-HFD to diffuse mass among preys or predators only and not to cross from predator to prey or vice versa. As result, similar species receive similar amount of mass and thus are ranked similarly. In the local clustering setting. Table SableBcomey compares HFD using different cut-costs. By exploiting specialized higher-order relations, S-HFD further improves Fl scores by up to 20% over U-HFD and C-HFD. This is not surprising, given the poor node-ranking results of other cut-costs. In the appendix we show another application of submodular cut-cost for node-ranking in an international oil trade network.
Table 3: Node-ranking and local clustering in Florida Bay food network using different cut-costs
Top-2 mode-ranking results
Clustering Fl
Method
Query: Raptors
Query: Gray Snapper
Prod. Low High
U-HFD Epiphytic Gastropods, Detriti. Gastropods Meiofauna, Epiphytic Gastropods
0.69 0.47 0.64
C-HFD
Epiphytic Gastropods, Detriti. Gastropods Mciofauna, Epiphytic Gastropods
0.67
0.47 0.64
S-HFD
Gruiformes, Small Shorebirds
Snook, Mackerel
0.69 0.62 0.84
Acknowledgments and Disclosure of Funding
K.F. would like to acknowledge the support of the Natural Sciences and Engineering Research Council of Canada (NSERC). Cette recherche a été financée par le Conseil de recherches en sciences naturelles et en génie du Canada (CRSNG), [RGPIN-2019-04066 DGECR- 2019-00144 P.I. is partially supported by the 2021 JP Morgan Faculty Award and the National Science Foundation (NSF) award HDR-2 21 17997. S.Y. is partially supported by the Borcalis AI 2021 Fellowship.
10

---

References
[1] C. Berge, Hypergraphs: combinatorics finite sets, vol. 45. Elsevier, 1984.
[2] R. Milo, S. Shen-Orr, S. Itzkovitz, N. Kashtan, D. Chklovskii, and U. Alon, "Network motifs: simple building blocks of complex networks." Science, vol. 298, no. 5594, pp. 824 827, 2002.
[3] J. Bu, S. Tan, C. Chen, C. Wang. H. Wu, L. Zhang. and X. He. "Music recommendation by unified hypergraph: combining social media information and music content," in MM '10: Proceedings of the 18th ACM international conference on Mulrimedia, 2010.
[4] L. Li and T. Li, "News recommendation via hypergraph learning: encapsulation of user behavior and news content," in WSDM '13: Proceedings of the sixth ACM international conference on Web search and data mining, 2013.
[5] J. Ni, J. Li, and J. McAuley, "Justifying recommendations using distantly-abelled reviews and fine- fine-grained aspects," " in Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP), pp. 188- 197, 2019.
[6] I. Amburg, N. Veldt, and A. R. Benson, "Clustering in graphs and hypergraphs with categorical edge labels," in Proceedings of the Web Conference. 2020.
[7] A. R. Benson, D. F. Gleich, and J. Leskovec, "Higher-order organization of complex networks," Science, vol. 353, no. 6295, pp. 163-166, 2016.
[8] P. Li and O. Milenkovic, "Inhomogeneous hypergraph clustering with applications," in Advances in Neural Information Processing Syxtems, 2017.
[9] M. Liu, N. Veldt, H. Song, P. Li, and D. F. Gleich, "Strongly local hypergraph diffusions for clustering and semi-supervised learning," in The WebConf 2021, 2021.
[10] E. L. Lawler, "Cutsets and partitions of hypergraphs." Networks, vol. 3, no. 3, pp. 275-285, 1973.
[11] E. Thler, D. Wagner, and F. Wagner, "Modeling hypergraphs hy graphs with the same mincut properties." Information Processing Letters, vol. 45, no. 4. pp. 171-175, 1993.
[12] S. W. Hadley, "Approximation techniques for hypergraph partitioning problems." Discrete Appl. Math.. vol. 59. p. 115-127, May 1995.
[13] N. Veldt, A. R. Benson, and J. Kleinberg, "Minimizing localized ratio cut objectives in hypergraphs." in Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), 2020.
[14] N. Veldt, A. R. Benson, and J. Kleinberg, "Hypergraph cuts with general splitting functions," 2020.
[15] P. Li and O. Milenkovic, "Submodular hypergraphs: p-laplacians, cheeger inequalities and spectral clustering," in Proceedings of the 35th International Conference on Machine Learning, 2018.
[16] Y. Yoshida, "Cheeger inequalities for submodular transformations." " Proceedings of the Thirtieth Annual ACM- SEM-SIAM Symposium on Discrete Algorithms, pp. 208.255222666 SIAM, 2019.
[17] Y. Takai, A. Miyauchi, M. Ikeda, and Y. Yoshida, "Hypergraph clustering based on pagerank," Pro- ceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 1970-1978, 2020.
[18] A. Benson, D. Gleich, and D. Higham, "Higher-order network analysis takes off, fueled by classical ideas and new data," SIAM News (online), 2021.
[19] C. Eksombatchai, P. Jindal, J. Z. Liu, Y. Liu, R. Sharma, C. Sugnet, M. Ulrich, and Leskovec, "Pixie: A system for recommending 3+ billion items to 200+ million users in real "aalttime," WWW '18 Proceedings of the 2018 World Wide Web Conference, pp.
2018.
[20] C. Eksombatchai, J. Leskovec, R. Sharma, C. Sugnet, and M. Ulrich, "Node graph traversal methods." U.S. Patent 10 762 134 B1, Sep. 2020, 2020.
[21] P. Gupta, A. Goel. J. Lin, A. Sharma, D. Wang, and R. Zadeh, "WTF: the who to follow service at twitter," WWW 113 Proceedings of the 22nd international conference World Wide Web, pp. 505-514, 2013.
[22] E. Sadikov, J. Madhavan, L. Wang, and A. Halevy, "Clustering query refinements by user intent," wWW 10: Proceedings of the 19th international conference World wide web, pp. 841-850, 2010.
[23] S. Brin and L. Page, "The anatomy of a large-scale hypertextual web search engine," Computer Networks and ISDN Systems, vol. 30, no. 1-7, pp. 107-117, 1998.
[24] L. Page. S. Brin, R. Motwani, and T. Winograd, "The pagerank citation ranking: Bringing order to the web." tech. rep.. Stanford, 1999. Technical Report 1999-66, Stanford InfoLab.
11

---

[25] D. Wang, K. Fountoulakis, M. Henzinger, M. W. Mahoney, and S. Rao, "Capacity releasing diffusion for speed and locality." Proceedings of the 34th International Conference on Machine Learning, vol. 70, pp. 3607-2017, 2017.
[26] K. Fountoulakis, D. Wang, and S. Yang. "p-norm flow diffusion for local graph clustering," in Proceedings of the 37th International Conference Machine Learning, 2020.
[27] R. Ibrahim and D. F. Gleich, "Local hypergraph clustering using capacity relcasing diffusion," PLOS ONE, vol. 15, pp. 1-20, 12 2020.
[28] H. Yin, A. R. Benson, J. Leskovec, and D. Gleich, "Local higher-order graph clustering," in Proceedings of the 23rd ACM SIGKDD international conference on knowledge discovery and data mining, pp. 555-564, 2017.
[29] D. Zhou, J. Huang, and B. Schölkopf. "Learning with hypergraphs: Clustering, classification, and embed- ding." " Advances in neural information processing systems. vol. 19, pp. 1601-1608. 2006.
[30] S. Arora, S. Rao, and U. Vazirani, "Expander flows, geometric embeddings and graph partitioning," JACM, vol. 56, Apr. 2009.
[31] M. Hein, S. Setzer, L. Jost, and S. S. Rangapuram, "The total variation on hypergraphs-leamingg on hypergraphs revisited," in Proceedings of the 26th International Conference on Neural Information Processing Systems- Volume 2, pp. 2427-2435, 2013.
[32] A. Louis, "Hypergraph markov operators, eigenvalues and approximation algorithmss" STOC, (New York, NY, USA), p. 713-722, Association for Computing Machinery, 2015.
[33] C. Zhang. S. Hu, Z. G. Tang. and T. H. Chan, "Re-revisiting learning hypergraphs: confidence interval and subgradient method," in International Conference on Machine Learning, pp. 4026-40344 PMLR, 2017.
[34] T.-H. H. Chan, A. Louis, 7. G. Tang, and C. Zhang, "Spectral properties of hypergraph laplacian and approximation algorithms," JACM, vol. 65, Mar. 2018.
[35] E. Chien, P. Li, and O. Milenkovic, "Landing probabilities of random walks for seed-set expansion in hypergraphs," 2019.
[36] P. Li, N. He, and O. Milenkovic, "Quadratic decomposable submodular lar function minimization: Theory and practice," " Journal of Machine Learning Research, vol. 21, no. 106, pp. 1-49. 2020.
[37] U. Chitra and B. Raphael. "Random walks on hypergraphs with edge-dependent vertex weights." in Pro- ceedings of the 36th International Conference on Machine Learning (K. Chaudhuri and R. Salakhutdinov, eds.), vol. 97 of Proceedings of Machine Learning Research, pp. 1172-1181, PMLR, 09-15 Jun 2019.
[38] K. Hayashi, S. G. Aksoy, C. H. Park, and H. Park, "Hypergraph random walks, laplacians, and clustering," in Proceedings of the 29th ACM International Conference on Information & Knowledge Management, CIKM '20, (New York, NY, USAA), p. 495-504, Association for Computing Machinery, 2020.
[39] K. Fountoulakis, M. Liu, D. F. Gleich, and M. W. Mahoney. "Flow-based algorithms for improving clusters: A unifying framework, software, and performance." arXiv:2004.090 09608, 2020.
[40] F. Bach, "Learning with submodular functions: convex optimization perspective." Foundations and Trends in Machine Learning, vol. 6, no. 2-3, pp. 145 303.373,772 2013.
[41] K. Fountoulakis, F. Roosta- Khorasani. J. Shun, X. Cheng, and M. W. Mahoney, "Variational perspective on local graph clustcring," Mathematical Programming B, pp. 1-21, 2017.
[42] R. Andersen, F. Chung, and K. Lang. "Local graph partitioning using pagerank vectors," FOCS '06 Proceedings of the 47th Annuad IEEE Symposium on Foundations of Computer Science, pp. 475-486, 2006.
[43] A. Beck, "On the convergence of alternating minimization for convex programming with applications to iteratively reweighted least squares and decomposition schemes," SIAM Journal on Optimization, vol. 25,
no. 1. pp. 185-209,70 2015.
[44] D. Ghoshdastidar and A. Dukkipati, "Consistency of spectral partitioning of uniform hypergraphs un- der planted partition model," in Advances in Neural Information Processing Systems (Z. Ghahramani, M. Welling, C. Cortes, N. Lawrence, and K. Q. Weinberger, eds.), vol. 27, Curran Associates, Inc., 2014.
[45] P. S. Chodrow, N. Veldt, and A. R. Benson, "Generative hypergraph clustering: from blockmodels modularity," 2021.
[46] J. Y. Zien, M. D. F. Schlag, and P. K. Chan, "Multilevel spectral hypergraph partitioning with arbitrary vertex sizes," IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 18, no. 9. pp. 1389-1399, 1999.
[47] J. Ni, J. Li, and J. McAuley, "Justifying recommendations using Eestantly-labelee reviews and fine-grained aspects," in Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCN)) IJCNLP), pp. 188- 197, 2019.
12


Reviews:
[{"review_id": "if3bX5Zl-Dc", "reviewer": "Reviewer_FB6z", "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. ", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "There exists no obvious negative societal impact.", "review_text": "", "extra_scores": {"ethical_concerns": "No ethical concerns with this paper. ", "needs_ethics_review": "No", "ethics_review_area": ["I don’t know"], "time_spent_reviewing": "7"}, "extra_text": {}}, {"review_id": "d-u7EkXu6Vs", "reviewer": "Reviewer_o3fQ", "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.\n\nA 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.\n\nThe author(s) also give(s) theoretical guarantees on the quality of the solution, based on clearly stated assumptions (Section 4).", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is a solid blend of sound theory and convincing experiments.\n\nThe 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.\n\nThe 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.\n\nWhile 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. \n\nThe 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.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "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.\n\nThe 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_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "10"}, "extra_text": {}}, {"review_id": "Z2sbRqjPtO", "reviewer": "Reviewer_Qb7P", "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. ", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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.\n\nOn 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. \n\nAlso, 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]?\n\nThe authors should also experimentally compare their algorithm with the one presented in [17].", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Not applicable.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4 hours"}, "extra_text": {}}, {"review_id": "LYgJy1jhzHq", "reviewer": "Reviewer_xXJk", "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.\n\nThe 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.\n\nEmpirical 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.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Although the results are interesting, there are several reservations.\n- 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).\n- 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?\n- 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.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

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)