Local Hyper-Flow Diffusion
Year: 2021

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-sizeindependent 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 `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.

heading: 1 Introduction
text: Hypergraphs [1] generalize graphs by allowing a hyperedge to consist of multiple nodes that capture higher-order relationships in complex systems and datasets [2]. Hypergraphs have been used for music recommendation on 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 [7, 8].
In order to explore and understand higher-order relationships in hypergraphs, recent work has made use of cut-cost functions that are defined by associating each hyperedge with a specific 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 [8, 9]. The most popular cut-cost functions with increasing capability to model complex multiway relationships are the unit cut-cost [10–12], cardinality-based cut-cost [13, 14] and general submodular cut-cost [15, 16]. An illustration of a hyperedge and the associated cut-cost function is given in Figure 1. In the simplest setting, all cut-cost functions take value either 0 or 1 (e.g., the case when γ1 = γ2 = 1 in Figure 1b), we obtain a unit cut-cost hypergraph. In a slightly more general setting, the cut-costs are determined solely by the number of nodes in either side of the hyperedge cut (e.g., the case when γ1 = 1/2 and γ2 = 1 in Figure 1b), we obtain a cardinality-based hypergraph.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
We refer to hypergraphs associated with arbitrary submodular cut-cost functions (e.g., the case when γ1 = 1/2 and 0 ≤ γ2 ≤ 1 in Figure 1b) as general submodular hypergraphs. Hypergraphs that arise from data science applications consist of interesting small-scale local structure such as local communities [9, 17]. Exploiting this structure is central to the above mentioned applications on hypergraphs and related applications in machine learning and applied mathematics [18]. We consider local hypergraph clustering as the task of finding a community-like 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 a 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 [19–21]. Google uses diffusion methods to perform clustering query refinements [22]. Let us not forget PageRank [23, 24], Google’s model for their search engine.
Empirical and theoretical performance of local diffusion methods is often measured on the problem of local hypergraph clustering [9, 25, 26]. Existing local diffusion methods only directly apply to hypergraphs with the unit cut-cost [17,27]. For the slightly more general cardinality-based cut-cost, they rely on graph reduction techniques which result in a rather pessimistic edge-size-dependent approximation error [9, 13, 27, 28]. Moreover, none of the existing methods is capable of processing general submodular 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 simultaneously accomplishes these goals.
In what follows we describe our main contributions and previous work. In Section 2 we provide preliminaries and notations. In Section 3 we introduce our diffusion model from a combinatorial flow perspective. In Section 4 we discuss the local hypergraph clustering problem and Cheeger-type quadratic ap-
proximation error. In Section 6 we perform experiments using both synthetic and real datasets.

heading: 1.1 Our main contributions
text: In this work we propose a generic local diffusion model that applies to hypergraphs characterized by a rich class of cut-cost functions that covers many previously studied special cases, e.g., unit, cardinality-based and submodular cut-costs. We provide the first edge-size-independent Cheeger-type 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 Φ(C), and assume that we are given a set of seed nodes that reasonably overlaps with C, then the proposed diffusion model can be used to find a cluster Ĉ with conductance at most O( √ Φ(C)) (in the appendix we show that an `p-norm version of the proposed model can achieve O(Φ(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 it 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-based and general submodular cut-costs for local clustering.

heading: 1.2 Previous work
text: 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-based (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 is 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 [7,8,15–17,29–38]. Local diffusion-based methods are more relevant to our work [9, 13,27]. 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 a 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 a target cluster using only one seed node. However, combinatorial methods have a 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 a 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-independent approximation error bound for even simple cardinality-based hypergraphs. Moreover, existing local approaches do not work for general submodular hypergraphs.

heading: 2 Preliminaries and Notations
text: Submodular function. Given a set S, we denote 2S the power set of S and |S| the cardinality of S. A submodular function F : 2S → R is a set function such that F (A)+F (B) ≥ F (A∪B)+F (A∩B) for any A,B ⊆ S. Submodular hypergaph. A hypergraph H = (V,E) is defined by a set of nodes V and a set of hyperedgesE ⊆ 2V , i.e., each hyperedge e ∈ E is a subset of V . A hypergraph is termed submodular if every e ∈ E is associated with a submodular function we : 2e → R≥0 [15]. The weight we(S) indicates the cut-cost of splitting the hyperedge e into two subsets, S and e \ S. This general form allows us to describe the potentially complex higher-order relation among multiple nodes (Figure 1). A proper hyperedge weight we should satisfy that we(∅) = we(e) = 0. To ease notation we extend the domain of we to 2V by setting we(S) := we(S ∩ e) for any S ⊆ V . We assume without loss of generality that we is normalized by ϑe := maxS⊆e we(S), so that we(S) ∈ [0, 1] for any S ⊆ V . For the sake of simplicity in presentation, we assume that ϑe = 1 for all e.1 A submodular hypergraph is written as H = (V,E,W) whereW := {we, ϑe}e∈E . Note that when we(S) = 1 for any S ∈ 2e\{∅, e}, the definition reduces to unit cut-cost hypergraphs. When we(S) only depends on |S|, it reduces to cardinality-based cut-cost hypergraphs. Vector/Function on V or E. For a set of nodes S ⊆ V , we denote 1S the indicator vector of S, i.e., [1S ]v = 1 if v ∈ S and 0 otherwise. For a vector x ∈ R|V |, we write x(S) := ∑ v∈S xv , where xv in the entry in x that corresponds to v ∈ V . We define the support of x as supp(x) := {v ∈ V |xv 6= 0}. The support of a vector in R|E| is defined analogously. We refer to a function over nodes x : V → R and its explicit representation as a |V |-dimensional vector interchangeably. Volume, cut, conductance. Given a submodular hypergraph H = (V,E,W), the degree of a node v is defined as dv := |{e ∈ E : v ∈ 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 ⊂ V , or a partition (C, C̄) where C̄ := V \ C. The cut-set of C is defined as ∂C := {e ∈ E|e ∩ C 6= ∅, e∩ C̄ 6= ∅}; the cut-size of C is defined as vol(∂C) := ∑ e∈∂C ϑewe(C) = ∑ e∈E ϑewe(C). The conductance of a cut C in H is Φ(C) := vol(∂C)min{vol(C),vol(V \C)} .
Flow. A flow routing over a hyperedge e is a function re : e→ R where re(v) specifies the amount of mass that flows from {v} to e \ {v} over e. To ease notation we extend the domain of re to V by identifying re(v) = 0 for v 6∈ e, so re is treated as a function re : V → R or equivalently a |V |-dimensional vector. The net (out)flow at a node v is given by ∑ e∈E re(v). Given a routing
1This is without loss of generality. In the appendix we show that our method works with arbitrary ϑe > 0.
function re and a set of nodes S ⊆ V , a directional routing on e with direction S → e \ S is represented by re(S), which specifies the net amount of mass that flows from S to e \ S. A routing re is called proper if it obeys flow conservation, i.e., rTe 1e = 0. Our flow definition generalizes the notion of network flows to hypergraphs. We provide concrete illustrations in Figure 2.

heading: 3 Diffusion as an Optimization Problem
text: 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 a hypergraph H = (V,E,W), we assign each node a sink capacity specified by a sink function T , i.e., node v is allowed to hold at most T (v) amount of mass. In this work we focus on the setting where T (v) = dv, so that a high-degree node that is part of many hyperedges can hold more mass than a low-degree node that is part of few hyperedges. Moreover, we assign each node some initial mass specified by a source function ∆, i.e., node v holds ∆(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 to 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 re for e ∈ E, recall that ∑ e∈E re(v) specifies the amount of
net (out)flow at node v. Therefore, the vector m = ∆− ∑ e∈E re gives the amount of net mass at each node after routing. The excess mass at a node v is ex(v) := max{mv − dv, 0}. In order to force the diffusion of initial mass we could simply require that ex(v) = 0 for all v ∈ V , or equivalently, ∆− ∑ e∈E re ≤ d. But to provide additional flexibility in the diffusion dynamics, we introduce a
hyper-parameter σ ≥ 0 and we impose a softer constraint ∆− ∑ e∈E re ≤ d+σDz, where z ∈ R|V | is an optimization variable that controls how much excess mass is allowed on each node. In the context of numerical optimization, we show in Section 5 that σ 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 a hyperedge would affect the flow routings over it. Apparently, simply requiring that the re’s obey flow conservation (i.e., rTe 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 = φeρe for some φe ∈ R+ and ρe ∈ Be, where
Be := {ρe ∈ R|V | | ρe(S) ≤ we(S),∀S ⊆ V, and ρe(V ) = we(V )} is the base polytope [40] for the submodular cut-cost we associated with hyperedge e. It is straightforward to see that re(v) = 0 for every v 6∈ e and rTe 1e = 0, so re defines a proper flow routing over e. Moreover, for any e ⊆ V , recall that re(S) represents the net amount of mass that moves from S to e \ S over hyperedge e. Therefore, the constraints ρe(S) ≤ we(S) for S ⊆ e mean that the directional flows re(S) are upper bounded by a submodular function φewe(S). Intuitively, one may think of φe and ρe as the scale and the shape of re, respectively.
The goal of our diffusion problem is to find low cost routings re ∈ φeBe for e ∈ E such that the capacity constraint ∆− ∑ e∈E re ≤ d+ σDz is satisfied. We consider the (weighted) `2-norm of φ and z as the cost of diffusion. In the appendix we show that one readily extends the `2-norm to `p-norm for any p ≥ 2. Formally, we arrive at the following convex optimization formulation (input: the source function ∆, the hypergraph H = (V,E,W), and a hyper-parameter σ):
min φ∈R|E|+ ,z∈R |V | +
1
2 ∑ e∈E φ2e + σ 2 ∑ v∈V dvz 2 v , s.t. ∆− ∑ e∈E re ≤ d+ σDz, re ∈ φeBe,∀e ∈ E. (1)
We name problem (1) Hyper-Flow Diffusion (HFD) for its combinatorial flow interpretation we discussed above. The dual problem of (1) is:
max x∈R|V |+
(∆− d)Tx− 1 2 ∑ e∈E fe(x) 2 − σ 2 ∑ v∈V dvx 2 v, (2)
where fe in (2) is the support function of the base polytope Be given by fe(x) := maxρe∈Be ρ T e x. fe is also known as the Lovász extension of the submodular function we.
We provide a combinatorial interpretation for (2) and leave algebraic derivations to the appendix. For the dual problem, one can view the solution x 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 function encourages raising x higher on the seed nodes and setting it lower on others. The cost fe(x) 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.

heading: 4 Local Hypergraph Clustering
text: In this section we discuss the performance of the primal-dual pair (1)-(2), respectively, in the context of local hypergraph clustering. We consider a generic hypergraph H = (V,E,W) with submodular hyperedge weightsW = {we, ϑe}e∈E . Given a set of seed nodes S ⊂ V , the goal of local hypergraph clustering is to identify a target cluster 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 are 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 Φ(C). We prove that applying sweepcut to an optimal solution x̂ of (2) returns a cluster Ĉ whose conductance is at most quadratically worse than Φ(C). 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 (1) is penalized by the `p-norm for any p ≥ 2. In order to start a diffusion process we need to provide the source mass ∆. Similar to the p-norm flow diffusion in the graph setting [26], we let
∆(v) = { δdv if v ∈ S, 0 otherwise, (3)
where S is a set of seed nodes and δ ≥ 1. Below, we make the assumptions that the seed set S and the target cluster C have some overlap, there is a constant factor of vol(C) amount of mass trapped in C initially, and the hyper-parameter σ 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 a good choice. Assumption 3 is very weak as it allows σ to reside in an interval containing 0. Assumption 1. vol(S ∩ C) ≥ αvol(C) and vol(S ∩ C) ≥ βvol(S) for some α, β ∈ (0, 1]. Assumption 2. The source mass ∆ as specified in (3) satisfies δ = 3/α, so ∆(C) ≥ 3vol(C). Assumption 3. σ satisfies 0 ≤ σ ≤ βΦ(C)/3.
Let x̂ be an optimal solution for the dual problem (2). For h > 0 define the sweep sets Sh := {v ∈ V |x̂v ≥ h}. We state the approximation property in Theorem 1.
Theorem 1. Under Assumptions 1, 2, 3, there exists h > 0 such that Φ(Sh) ≤ O( √ Φ(C)/αβ).
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,17]. 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 a neighbor of any node not belonging to the target cluster. Even in the classical graph setting, establishing a local clustering guarantee based on diffusing mass from a single node requires assuming that a good seed node has been selected from a 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 α 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 6 show that our method has superior performance in practice even when only one seed node is used.
One of the challenges we face in establishing the result in Theorem 1 is making sure that our diffusion model enjoys not only good clustering guarantees but also practical algorithmic advantages. This is achieved by introducing the hyper-parameter σ to our diffusion problem. We will demonstrate how σ helps with algorithmic development in Section 5, but from a clustering perspective, the additional flexibility given by σ > 0 complicates the underlying diffusion dynamics, making it more difficult to analyze. Another challenge is connecting the Lovász extension fe(x) in (2) with the conductance of a cluster. We resolve all these problems by combining a generalized Rayleigh quotient result for submodular hypergraphs [15], primal-dual convex conjugate relations between (1) and (2), and a classical property of the Choquet integral/Lovász extension.
Let (φ̂, r̂, ẑ) be an optimal solution for the primal problem (1). We state the following lemma on the locality (i.e., sparsity) of the optimal solutions, which justifies why HFD is a local diffusion method.
Lemma 2. |supp(φ̂)| ≤ vol(supp(x̂)) ≤ ‖∆‖1; moreover, vol(supp(ẑ)) = vol(supp(x̂)) if σ > 0.

heading: 5 Optimization algorithm for HFD
text: We use a simple Alternating Minimization (AM) [43] method that efficiently solves the primal diffusion problem (1). For e ∈ E, we define a diagonal matrix Ae ∈ R|V |×|V | such that [Ae]v,v = 1 if v ∈ e and 0 otherwise. Denote C := {(φ, r) : re ∈ φeBe, ∀e ∈ E}. The following Lemma 3 allows us to cast problem (1) to an equivalent separable formulation amenable to the AM method.
Lemma 3. The following problem is equivalent to (1) for any σ > 0, in the sense that (φ̂, r̂, ẑ) is optimal in (1) for some ẑ ∈ R|V | if and only if (φ̂, r̂, ŝ) is optimal in (4) for some ŝ ∈ ⊗ e∈E R|V |.
min φ,r,s
1
2 ∑ e∈E ( φ2e + 1 σ ‖se − re‖22 ) , s.t. (φ, r) ∈ C, ∆− ∑ e∈E se ≤ d, se,v = 0,∀v 6∈ e. (4)
Algorithm 1 Alternating Minimization for (4) Initialization:
φ(0) := 0, r(0) := 0, s(0)e := D −1Ae [∆− d]+ , ∀e ∈ E.
For k = 0, 1, 2, . . . do:
(φ(k+1), r(k+1)) := argmin (φ,r)∈C ∑ e∈E (φ2e + 1 σ ‖s(k)e − re‖22)
s(k+1) := argmin s ∑ e∈E ‖se − r(k+1)e ‖22
s.t. ∆− ∑ e∈E se ≤ d, se,v = 0,∀v 6∈ e. The AM method for problem (4) is given in Algorithm 1. The first sub-problem corresponds 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 Be. If the hyperedge weight we is unit cut-cost, Be holds special structures and projection can be computed with O(|e| log |e|) [36]. For general Be, a conic Fujishige-Wolfe minimum norm algorithm can be adopted to obtain the projection [36]. The second sub-problem in Algorithm 1 can be easily computed in closed-form. We provide more information about Algorithm 1 and its convergence properties in the appendix.
We remark that the reformulation (4) for σ > 0 is crucial from an algorithmic point of view. If σ = 0, then the primal problem (1) 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 a nonsmooth objective function, which prohibits applicability of optimization 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 ‖∆‖1. In Figure 3 we plot the number of nodes having positive excess (which equals the number of nonzeros in the dual solution x̂) at every iteration of Algorithm 1. Figure 3 indicates that Algorithm 1 is strongly local, meaning that it works only on a small fraction of nodes (and their incident hyperedges) as opposed to producing dense iterates. This key empirical observation has enabled our algorithm to scale to 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 is an open problem, which we leave for future work.

heading: 6 Empirical Results
text: 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-based cut-cost setting, we show that the edge-size-independent 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 state-ofthe-art diffusion methods for both unit and cardinality-based cut-costs. Moreover, we provide a compelling example where specialized submodular cut-cost is necessary for obtaining good results. Code that reproduces all results is available at https://github.com/s-h-yang/HFD.

heading: 6.1 Synthetic experiments using hypergraph stochastic block model (HSBM)
text: 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, . . . , n} be a set of nodes and let k ≥ 2 be the required constant hyperedge size. We consider kHSBM with parameters k, n, p, qj , j = 1, 2, . . . , bk/2c. The model samples a k-uniform hypergraph according to the following rules: (i) The community label σi ∈ {0, 1} is chosen uniformly at random for i ∈ V ;2 (ii) Each size k subset e = {v1, v2, . . . , vk} of V appears independently as a hyperedge with probability
P(e ∈ E) = { p if σv1 = σv2 = · · · = σvk , qj if min{k − ∑k i=1 σvi , ∑k i=1 σvi} = j.
If k = 3 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 qj’s are different, then we obtain a cardinality-based kHSBM.
2We consider two blocks for simplicity. In general the model applies to any number of blocks.
In particular, when q1 ≥ q2 ≥ · · · ≥ qbk/2c, 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 q1 qj , j ≥ 2, to evaluate HFD for cardinality-based cut-cost. There are other random hypergraph models, for example the Poisson degree-corrected HSBM [45] that deals with degree heterogeneity and edge 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.
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 a 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 (LH) [9], which can be seen as a hypergraph analogue of Approximate Personalized PageRank (APPR); (ii) ACL [42], which is used to compute APPR vectors on a standard graph obtained from reducing a hypergraph through star expansion [46].3
Cut-costs and parameters. We consider both unit cut-cost, i.e., we(S) = 1 if S ∩ e 6= ∅ and e \ S 6= ∅, and cardinality cut-cost we(S) = min{|S ∩ e|, |e \ S|}/b|e|/2c. 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 ‖∆‖1 is a constant factor times the volume of the target cluster. We set σ = 0.01. We highly tune LH by performing binary search over its parameters κ and δ and pick the output cluster having the lowest conductance. For ACL 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 4 shows local clustering results when we fix k = 3 but vary the conductance 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 it requires much weaker conditions for the theoretical conductance guarantee to hold. On the contrary, LH assumes an 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 to 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.
Cardinality cut-cost results. Figure 5 shows the median (markers) and 25-75 percentiles (lower-upper bars) of conductance ratios (i.e., the ratio between output conductance and ground-truth conductance, lower is better) and F1 scores for different methods for k ∈ {3, 4, 5, 6}. The target cluster for each k
3There are other heuristic methods which first reduce a hypergraph to a graph by clique expansion [7] and then apply diffusion methods for standard graphs. We did not compare with this approach because clique expansion often results in a dense graph and consequently makes the computation slow. Moreover, it has been shown in [9] that clique expansion did not offer significant performance improvement over star expansion.
has conductance around 0.3.4 For k = 3, unit and cardinality cut-costs are equivalent, therefore all methods have similar performances. As k increases, cardinality cut-cost provides better performance than unit cut-cost in both conductance and F1. However, since the theoretical approximation guarantee of C-LH depends on hyperedge size [9], there is 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 1.

heading: 6.2 Experiments using real-world data
text: 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, we show that general submodular cut-cost (recall that HFD is the only method that applies to this setting) can be necessary for capturing complex high-order relations in the data, improving F1 scores by up to 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 F1 scores by 8% on average for 13 different target clusters.
Datasets. We provide basic information about the datasets used in our experiments. Complete descriptions are provided in the appendix. Amazon-reviews (|V | = 2,268,264, |E| = 4,285,363) [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 use product category labels as ground truth cluster identities. We consider all clusters of less than 10,000 nodes. Trivago-clicks (|V | = 172,738, |E| = 233,202) [45]. The nodes in this hypergraph are accommodations/hotels. A set of nodes are connected by a 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 we filter them using cluster size and conductance. Florida Bay food network (|V | = 128, |E| = 141,233) [8]. Nodes in this hypergraph correspond to different species or organisms that live in the Bay, and hyperedges correspond to transformed motifs (Figure 1) of the original dataset. Each species is labelled according its role in the food chain: producers, low-level consumers, high-level consumers.
Methods and parameters. We compare HFD with LH and ACL.5 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 set σ = 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-reviews and Trivago-clicks, we run the methods multiple times, each time we use a different node as the singe seed node.6 We report the median F1 scores of the output clusters in Table 1 and Table 2. For
4See 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 in terms of the target conductance and illustrate the performance of algorithms for different levels of noise.
5We also tried a flow-improve method for hypergraphs [13], but the method was very slow in our experiments, so we only used it for small datasets. See appendix for results. The flow-improve method did not improve the performance of existing methods, therefore, we omitted it from comparisons on larger datasets.
6We show additional results using seed sets of more than one node in the appendix.
Amazon-reviews, we only compare the unit cut-cost because it is both shown in [9] and verified by our experiments that unit cut-cost is more suitable for this dataset. Observe that U-HFD obtains the highest F1 scores for nearly all clusters. In particular, U-HFD 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 F1 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 F1 than its unit cut-cost counterpart.
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 1. We compare HFD using unit (U-HFD, γ1 = γ2 = 1), cardinality-based (C-HFD, γ1 = 1/2 and γ2 = 1) and submodular (S-HFD, γ1 = 1/2 and γ2 = 0) cut-costs. Our goal is to search the most similar species of a queried species based on the food-network structure. Table 3 shows that S-HFD provides the only meaningful node ranking results. Intuitively, when γ2 = 0, separating the preys v1, v2 from the predators v3, v4 incurs 0 cost. This encourages S-HFD to diffuse mass among preys or predators only and not to cross from a predator to a prey or vice versa. As a result, similar species receive similar amount of mass and thus are ranked similarly. In the local clustering setting, Table 3 compares HFD using different cut-costs. By exploiting specialized higher-order relations, S-HFD further improves F1 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.
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-04067, DGECR- 2019-00147]. P.L. is partially supported by the 2021 JP Morgan Faculty Award and the National Science Foundation (NSF) award HDR-2117997. S.Y. is partially supported by the Borealis AI 2021 Fellowship.

Review summaries:
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. 

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).

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.