Finding Bipartite Components in Hypergraphs
Authors: Peter Macgregor
He Sun
Venue: NeurIPS 2021 Poster (2021)
Keywords: hypergraph clustering
spectral methods

Abstract: Hypergraphs are important objects to model ternary or higher-order relations of objects, and have a number of applications in analysing many complex datasets occurring in practice.  In this work we study a new heat diffusion process in hypergraphs, and employ this process to design a polynomial-time algorithm that approximately finds bipartite components in a hypergraph.  We theoretically prove the performance of our proposed algorithm, and compare it against the previous state-of-the-art through extensive experimental analysis on both synthetic and real-world datasets. We find that our new algorithm consistently and significantly outperforms the previous state-of-the-art across a wide range of hypergraphs.

Finding Bipartite Components in Hypergraphs
Peter Macgregor School of Informatics University of Edinburgh
He Sun School of Informatics University of Edinburgh h. sun@ed ac. uk
peter peter. www.gmgoooedd.dccom
Abstract
Hypergraphs are important objects to model ternary or higher-order relations objects, and have number of applications in analysing many complex datasets occurring in practice. In this work we study a new heat diffusion process hypergraphs, and employ this process to design polynomial-time algorithm that approximately finds bipartite components in a hypergraph. We theoretically prove the performance of our proposed algorithm, and compare it against the previous state-of-the-art through extensive experimental analysis on both synthetic and real-world datasets. We find that our algorithm consistently and significantly outperforms the previous state-of-the-art across wide range of hypergraphs.
Introduction
Spectral methods study the efficient matrix representation of graphs and datasets, and apply the algebraic properties of these matrices to design efficient algorithms. Over the last three decades, spectral methods have become one of the most powerful techniques machine learning, and have had comprehensive applications in wide range of domains, including clustering (24 31 image and video segmentation (26). and network analysis (25). among many others. While the success this line of research is based our rich understanding of Laplacian operators of graphs, there has been sequence of very recent work studying non-linear Laplacian operators for more complex objects (i.c., hypergraphs) and employing these non-linear operators to design hypergraph algorithms with better
performance.
1.1 Our contribution
In this work, study the non-linear Laplacian-type operators for hypergraphs, and employ such an operator to design a polynomial-time algorithm for finding bipartite components in hypergraphs. The main contribution our work is follows:
First all, we introduce and study a non-linear Laplacian-type operator Jи for any hypergraph H. While we'll formally define the operator JH in Section 3 one can informally think about Ju variant of the standard non-line non-linear hypergraph Laplacian LH studied in [3] 20 27), and this variation is needed to study the other end of the spectrum of Lи- We present polynomial-time algorithm that finds some eigenvalue and its associated eigenvector of JH. and our algorithm is based on the following heat diffusion process: starting from arbitrary vector fo R that describes the initial heat distribution among the vertices, we use fo to construct some 2-grapt Go. and use the diffusion process in Go represent the one in the original hypergraph H and update f.; this process continues until the time at which Go cannot be used to appropriately simulate the diffusion process in Hl any more. At this point, we use the currently maintained to construct another 2-graph G,
Throughout the paper, we refer to non-hyper graphs as 2-graphs. Similarly, we always use L to refer to the non-linear hypergraph Laplacian operator, and use LG as the standard 2-graph Laplacian.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

0.5 0.5
0.5 0.5
0.14
0014
0.62
0.
0.02
0.02
0.02
0.35
0.38
115
ft
ft
U.5
0.5
0.5
0.5
0.11
0.00
0.03
-0.09
00.71
0.03
-0.09
1.0
1.0
0.03
0.04
0.03
0.03
0.03
0.03
0.04
8:25
0.29
0.03
0.5
0.5
0.03
f
ft
== 23
Figure I: Illustration of our proposed diffusion process. In cach time step, we construct a 2- 2-graph G based on the current vector fe, and update fe with the JG operator. Notice that the graph G changes throughout the execution of the algorithm, and that the final ft vector can be used to partition the vertices of H into two well-connected (all the edges adjacent both sets). splitting according positive and negative entries. This specific example with fi values generated by publicly available implementation our algorithm.
simulate the diffusion process in H, and update fi. This process continues until the vector fo converges; see Figure [ for illustration. We theoretically prove that this heat diffusion process is unique, well-defined, and our maintained vector fo converges some eigenvector of J While this result is quite interesting on its own and forms the basis of our second result, our analysis shows that, for certain hypergraphs H, both the operator JH and I. could have (11) eigenvectors. This result answers an open question in 55. which asks whether I. could have more than 2 eigenvector
Secondly, we present a polynomial-tmme algorithm that, given a hypergraph // (VH, EH, w) as input, finds disjoint subsets L, R C Vи that are highly connected with each other. The key to our algorithm Cheeger-type inequality for hypergraphs that relates the spectrum of JH and the bipartiteness ratio of H, an analog of 3G studied in (28) for 2-graphs. Both the design and analysis of our algorithm is inspired by [28]. however our analysis is much more involved because of the non-linear operator JH and hyperedges of different ranks. Our second result alone answers an open question posed by (33], which asks whether there is hypergraph operator which satisfies
Cheeger-type inequality for bipartiteness.
The significance of our work is further demonstrated by extensive experimental studies of algorithms on both synthetic and real-world datasets. In particular, on the well-known Penn Treebank corpus that contains 49, 208 sentences and over I million words, our purely unsupervised algorithm is able to identify a significant fraction of verbs from non-verbs in its two output clusters. Hence, we believe that our work could potentially have many applications in unsupervised learning for hypergraphs. Using the publicly available code of our implementation, we welcome the reader to explore further applications of work in even more diverse datasets.
1.2
Related work
The spectral theory of hypergraphs using non-linear operators is introduced in (5) and generalised in 33
The operator they describe is applied for hypergraph clustering applications in 20 27).
There are many approaches for finding clusters hypergraphs by constructing 2 2-graph which
approximates the hypergraph and using a 2-graph clustering algorithm directly 7 19 35
Another
We underline that, while the operator La of a 2-graph has n eigenvalues, the number of eigenvalues of La is unknown because of its non linearity. As answering this open question isn' 't the main point of our work. we refer the reader to Appendix C for detailed discussion.

---

approach for hypergraph clustering is based on tensor spectral decomposition [1]] 18
23
36
consider the problem of finding densely connected clusters in 2-graphs. Heat diffusion processes are used for clustering 2-g 2-graphs in 10 17 [4] studies a different, flow-based diffusion process for finding clusters in 2-graphs, and 13 generalises this hypergraphs. We note that all of these methods solve a different problem to ours, and cannot be compared directly. Our algorithm is related to the hypergraph max cut problem, and the state-of- -hrt approximation algorithm is given by [34). (28] introduces graph bipartiteness and gives approximation algorithm for the 2-graph max cut problem. To the best our knowledge, we are the first to generalise this notion of bipartiteness to hypergraphs. Finally,
note that there have been recent improvements in the time complexity for solving linear programs [1 29 although we do not take these into account in our analysis since the goal of this paper is not to obtain the fastest algorithm possible.
2 Notation
2-graphs. Throughout the paper, we call a non-hyper graph a 2-graph G= (Vg, Eg, w) to express a 2-graph, in which every edge e Eg consists of two vertices in Vo and we let and for any S C V the volume of S is defined by vola(5) - Eues da(u). Following 28 the hiparfiteness ratio of any disjoint sets I., R C Va is defined by
4 8
We always use
VVl-- The degree of any vertex E VG is defined by dc(u) & Eveva w(u, v).
2w( (,, L) + 2w R - W(LUR,LUR
BL R)
rolo(LUR)
where wA, B) = ((x.))AXB wuu, v), and we further define Bg A minsev Ba V (AV) (S). Notice that low va-val means that there is dense cut between L and R, and there is sparse cut between L R and V (L R). In particular, 9G = 0 implies that (L, R) forms a bipartite component G. We De denote the Moreover, we use Ag to denote the n x n adjacency matrix whose entries are (Ac) = w(u, v), for all u, E V. The Laplacian matrix is defined by LG - De Ag- In addition, we define 1/2 Je DoDa For any real and symmetric matrix A, the eigenvalues of A are denoted by (A) < ... < An (A), and the eigenvector associated with (;(4) is denoted by (AA for <isn.
diagonal matrix whose entries are (De) dc(u), for all V.
JG A DG Ag, and To A D
Hypergraphs. Let H = (VH: EH, w) be a hypergraph with n = |VHl vertices and weight function w : Eμ Rt. For any vertex v E VH, the degree of u is defined by (u) 2 Eee w(e) [[e E e). where I[X] = if event X holds and [[X] = 0 otherwise. The rank of edge e E Eµ the total number of vertices in For any A, B Vn, the value between A and B defined by
w ((A,B)
Σ w(e) I[ A AennE #
EBg
Sometimes, we are required to analyse the weights of edges that intersect some vertex sets and not others. To this end, we define for any A, B,C C VH that
w (A, B C A Σ
w(e) I[ A B
CEEN
and we sometimes write w(A C*) A w(A,A| C) for simplicity. Generalising the notion of the bipartiteness ratio of 2-graph, the bipartiteness ratio of sets L,, R in hypergraph H is defined by
(L, R2) 2w(L + 2w (R + w(L, L.R,URRR R(R) + w w(R, LURL)
vol(T. R)
and we define 3H A minsev Bn(SS S). For any hypergraph H and f E R", we define the discrepancy of edge Eн with respect
A
(e)
A max f(u) + min (wv) DEe
wEe
For any non-linear operator J + R we say that () is an eigen-pair if and only Jʃ Aʃ
and note that in general, non-linear operator can have any number of cigenvalues and cigenvectors.
3

---

It is important to remember that throughout the paper, we always use the letter H to represent hypergraph, and G represent a 2-graph.
Clique reduction. The clique reduction of a hypergraph H is a 2-graph G such that Vi = VH and for every edge ΣH, G contains clique on the vertices in with edge weights 1/(re - 1) where re is the rank of the edge e. The clique reduction is common tool for designing hypergraph algorithms M (3), and for this reason we use it as a baseline algorithm in this paper. We note that hypergraph algorithms based on the clique reduction often perform less well when there are edges with large rank the hypergraph. Specifically, in Appendix C use two r-uniform hypergraphs as examples to show that no matter how we weight the edges in the clique reduction, some cuts cannot be approximated better than a factor of (r)). This one of the main reasons to develop spectral theory for hypergraphs through heat diffusion processes S 27 33
3 Diffusion process and the algorithm
In this section, we propose a new diffusion process in hypergraphs and use it to design a polynomial- time algorithm for finding bipartite components in hypergraphs. We first study 2-graphs to give some intuition, and then generalise hypergraphs and describe our algorithm. Finally, we sketch some of the detailed analysis which proves that the diffusion process is well defined.
3.1 The diffusion process in 2-graphs
To discuss the intuition behind our designed diffusion process, let look at the case of 2-graphs. Let G = (V, E, w) be a 2-graph, and we have for any x E R" that
xT JJ x
xT(1 + DG 1/2 Dc 1/2
xtx
By setting x D'd2 y. we have that
IT JT n Ded JaD y7 (T + Ac)v EjuoyeEa w(u, (y(u) + y(v))²
xrr
Dyy
DTDGY
Evevo do(u) y(u)²
It is easy to see that (JG) if G is bipartite, and it is known that A (JTc) and its corresponding eigenvector Ji (Ja) are closely related two densely connected components of G [28] Moreover, similar to the heat equation for graph Laplacians L.G, suppose DaJi E R is some measure on the vertices of G, then a diffusion process defined by the differential equation
df dt
will converge to the minimum eigenvalue of D D= and can be employed to find two densely connected components of the underlying 2- 2-graph
3.2 The hypergraph diffusion and our algorithm
Now we study whether one can construct a new hypergraph operator Jh which generalises the diffusion in 2-graphs to hypergraphs. First of all, we focus on fixed time t with measure vector Duft E R.a and ask whether we can follow ( and define the rate of change
df dt D
so that the diffusion can proceed for an infinitesimal time step. Our intuition that the rate change due to some edge e Eh should involve only the vertices in e with the maximum minimum value in the normalised measure ft. To formalise this, for any edge e E En, we define
Sy(e) A {u E fe(e) max fe(u)} and (e Ee::: Se(u) = min fr(u)). wEe
wEe
'For the reader familiar with the heat diffusion process of 2-graphs (e.g.. 9 17)). we remark that the above-defined process essentially employs the operation Jc to replace the Laplacian La when defining the heat diffusion: through JG. the heat diffusion be used to find two densely connected components of G.

---

That is, for any edge and normalised measure ft. Sy S consists of the vertices adjacent to whose (u) values are maximum and (e) S e consists of the vertices v adjacent whose fi f(()) values are minimum. See Figure 2 for an example. Then, applying the Jnr operator to a vector ft should be equivalent to applying the operator Jg for some 2-graph G which we construct by splitting the weight of each hyperedge E EH between the edges in Sy(e) x [e))). Similar to the case for 2- 2-graphs and (T) for any x = D ft this will give us the quadratic form
DH 1/2
1/2 JnDH DH
fl Duft = EiunteEd wa(u,, v) (f((u) + fi(u))²
Jat.
xxx
Σneva du (u) ff(u)²
LeEEn wH(e)(maxuee fi(u) + minege Sc(v))²
Eveva du(u)= ft(u)²
where (t v) is the weight of the edge {u, F} in G. and (H)e) is the weight of the edge in H. We will show in the proof of Theorem that J/ has an eigenvalue of the hypergraph is 2-colourable" and that the spectrum of JH is closely related to the hypergraph bipartiteness.
For this reason, we would expect that the diffusion process based on the operator JH can be used to find sets with small hypergraph bipartiteness. However, one needs to be very cau- tious here as, by the nature of the diffusion process, the values fe( of all the vertices e change over time and, as a result, the sets Sy(e) and (e) that consist of the vertices with the maxi- mum and minimum fi-value might change after an infinitesimal time step: this will prevent the process from continuing. We will discuss this issue in detail through the so-called Diffusion Contimuity Condition in Section 3 In essence, the diffusion continuity condition ensures that one can always construct a 2- g-graph G by allocating the weight of each hyperedge to the edges in Sy(e) x (e) such that the sets Sy and [e) will not change in infinitesimal time although fa changes according to (d.ft/ (df) = - Dr= Jaft. We will also present an efficient procedure Section 3.3 to compute the weights of edges in Sy(e) x Lf().. All of these guarantee that (i) every 2- g-graph that corresponds to the hypergraph diffusion process at any time step can be efficiently constructed; (ii) with this sequence of constructed 2-graphs, the diffusion process defined by JH is able to continue until the heat distribution converges. With this, we summarise the main idea of our presented algorithm as follows:
[
Sy(e)
3
Hyperedge e
Figure 2: Illustration of Sy(e) and [e(c). Vertices are labelled with their value in ft.
First of all, we introduce some arbitrary fo E R. as the initial diffusion vector, and step size parameter 6 >> O to discretise the diffusion process. At each step, the algorithm constructs the 2-graph G guaranteed by the diffusion continuity condition, and updates ft E E according to the rate of change (dft)/ddt) converged, i.e., the ratio between the current Rayleigh quotient the one in the previous time step is bounded by some predefined constant.
-D Jeft- The algorithm terminates when fo has
fi) and
Secondly, similar to many previous spectral graph clustering algorithms (e.g. 27 28) the algorithm constructs the sweep sets defined by fe and returns the two sets with minimum -n-uul among all the constructed sweep sets. Specifically, for every < i < n, the algorithm constructs Ly {o; (f(())) > [((r,) A f(())) < 0} and Rg {r, fi(e))) > [f,( A (v,) > 0}. Then, between the n pairs (Lj, Ry). the algorithm returns the one with the minimum -vavul
See Algorithm for the formal description, and its performance is summarised in Theorem Theorem 1 (Main Result), Given a hypergraph H = (VH, En, w) and parameter > 0, the following holds:
1. There is an algorithm that finds an eigen-pair (X, f) of the operator JH such that X S X1 (JG),, where G is the clique reduction of H and the inequality is strict if mineee Ey Te >> where Te is the rank of e. The algorithm runs in poly([VHl, Vl, ER ; 1/e) time.
'Hypergraph H is 2- 2-colourable if there disjoint sets L, R C. Vn such that every edge intersects L and R.
5

---

2. Given an eigen-pair f) of the operator Ju, there is an algorithm that constructs the two-sided sweep sets defined on f. and finds sets L and R such that 3h (L, R) v2X. The algorithm runs in poly (VHH), EH]) time.
Algorithm 1: FINDBIPARTITECOMPONET
Input :Hypergraph H, starting vector fo E I2, step size > 0
Output: :Sets and R
:==0
while fi has not converged do
Use St to construct 2-graph G satisfying the diffusion continuity condition
fite == ft - - Jaf
t :
end
Set j arg minigig Bn R.) return (Lz. Rg)
Remark 1. We make the important remark that there is no polynomial -imme algorithm which guaran- tees any multiplicative approximation of the minimum hypergraph bipartiteness value 3H, unless P = NP. We prove this in Appendix C by reduction from the NP-complete HYPERGRAPE 2- COLOURABILITY problem. This means that the problem we consider in this work is fundamentally more difficult than the equivalent problem for 2-graphs, as well the problem of finding a sparse in a hypergraph. For this reason, the analysis of the non- non-linear hypergraph Laplacian operator [5] 27
cannot be applied in our case.
3.3 Dealing with the diffusion continuity condition
It remains for us discuss the diffusion continuity condition, which guarantees that Sy(e) and (e) will not change in infinitesimal time and the diffusion process will eventually converge to some stable distribution. Formally, let fo be the normalised measure on the vertices of H, and let
dft
-
D JH
dt
be the derivative of Jt, which deseribes the rate of change for every vertex the current time I. We write r(v) for any E VH as r(v)= E. ("), where r. rv)v) is the contribution of edge towards the rate of change of v. Now we discuss three rules that we expect the diffusion process to satisfy, and later prove that these three rules uniquely define the rate of change
we expect that only the vertices in Sy(e) Iy(e) will participate in the diffusion process, i.e., [u) O unless u E Sy(e) UI(e). Moreover, any vertex
First of all, as we mentioned in Section 3.2
participating the diffusion process must satisfy the following:
Rule (Oa): if (w)) > and Sy(e), then r(u) = m
Rule (Ob): if [r=(u)] > and u E [y(), then r(u) = min,er,())((u)))
To explain Rule (0), notice that for an infinitesimal time, fe(u) will be increased according to (dft/dt) (w) r(u). Hence, by Rule (0) we know that, if u E (e) (resp. E (e)) participates in the diffusion process in edge e, then in an infinitesimal time f(u) will remain the maximum (resp. minimum) among the vertices in Such rule is necessary to ensure that the vertices involved in the diffusion in edge e do not change infinitesimal time, and the diffusion process is able to continue.
Our next rule states that the total rate of change of the measure due to edge is equal to - -w(e) (())::
Rule (1): Eves, d())ra(v) Ever,tes d(u)ra(u) w(e) Ay(e) for all Er.
This rule is generalisation from the operator JG in 2-graphs. In particular, since D Jaf((u) E(uw)eeF wo (w f((d()) (u), the rate of change of fu(u) due to the edge {u, E EG -w ()(((u)) + fe(w))/da(u Rule (1) states that in the hypergraph case the rate of change of the vertices in Sy( and (e) together behave like the rate of change of and in the 2-graph case.

---

One might have expected that these two rules together will define a unique process. Unfortunately, this isn't t the case and we present counterexample in Appendix A. To overcome this, we introduce the following stronger rule to replace Rule (0):
Rule (2a): Assume that [re(u)] and Sy(e).
If (e) O, then r(u) my {r(v)]:
If ()) < O, then r(u) r(v) for all E Sy(e).
Rule (2b): Assume that [r][ 0 and [y(e):
If ( 0, then r(u) (e) fr(u)):
If Af > O, then r(u) r(v) for all E If(e).
Notice that the first conditions of Rules (2a) and (2b) correspond to Rules (0a) and (0b) respectively; the second conditions are introduced for purely technical reasons: they state that, if the discrepancy of is negative (resp. positive), then all the vertices E Sy(e) (resp. Ie(e) will have the same value of r(u). Theorem 2 shows that there is a unique E R" that satisfies Rules (1) and (2), and r can be computed in polynomial time. Therefore, our two rules uniquely define diffusion process, and we can use the computed r to simulate the continuous diffusion process with discretised version
Theorem 2. For any given Jt E IR" there is unique r = =ddf//d and associated (ra(u))cEF.a)) FV that satisfy Rule (1) and (2), and r can computed polynomial time by linear programming.
Remark 2. The rules define and the proof of Theorem are more involved than those used in (3] to define the hypergraph Laplacian operator. In particular, in contrast to (5), in our case the discrepancy Ay(e) within a hyperedge can be either positive or negative. This results in the four different cases in Rule (2) which must be carefully considered throughout the proof of Theorem 2
4 Experiments
In this section, we evaluate the performance of our new algorithm on synthetic and real-world datasets. All algorithms are implemented in Python 3.6, using the scipy library for sparse matrix rep- resentations and linear programs. The experiments are performed using an Intel(R) Core(TM) i5-8500 CPU @ 3.00GHz processor, with 16 GB RAM. Our code can be downloaded from components
Since ours is the first proposed algorithm for approximating hypergraph bipartiteness, we will compare it to a simple and natural baseline algorithm, which call CLIQUECUT (CC). In this algorithm, we construct the clique reduction of the hypergraph and use the two-sided sweep-set algorithm described in 28 to find with low bipartiteness in the clique reduction
Additionally, we will compare two versions of our proposed algorithm. FINDBIPARTIEECMPPO NENTS (FBC) is our new algorithm described in Algorithm | and FBCAPPROX (FBCA) is an approximate version in which we do not solve the linear programs in Theorem 2 to compute the graph G. Instead, at each step of the algorithm, we construct G by splitting the weight of each hyperedge evenly between the edges in S(e) x I(e).
We always set the parameter 1 for FBC and FBCA, and we set the starting vector So E R for the diffusion to the eigenvector corresponding to the minimum eigenvalue of Ja. where the clique reduction of the hypergraph H.
4.1 Synthetic datasets
We first evaluate the algorithms using random hypergraph model. Given the parameters n,, r, p. and q. we generate an n n-vertex r-uniform hypergraph in the following way: the vertex set V is divided
'Note that the graph G used for the diffusion at time I can be easily computed from the (r)(w)} values, although in practice this not actually needed since the r(u) values can be used to update the diffusion directly. "We choose to use the algorithm in (28) here since, as far we know, this is the only non- non-SDP based algorithm for solving the MAX-CUT problem for 2-graphs. Notice that, although SDP based algorithms achieve better approximation ratio for the MAX-CUT problem, they are not practical even for hypergraphs of medium sizes.
7

---

into two clusters L and R of size n/2. For every set S C V with =, or C R we add the hyperedge S with probability p and otherwise we add the hyperedge with probability 9. We remark that this is special case of the hypergraph stochastic block model (e.g.. (6). We limit the number of free parameters for simplicity while maintaining enough flexibility to generate random hypergraphs with wide range of optimal 33
We will compare the algorithms' performance using four metries: the hypergraph bipartiteness ratio 3H (L, Rt). the clique graph bipartiteness ratio Ba(L, R). the Fi-score (30) of the returned clustering, and the runtime of the algorithm. Throughout this subsection, we always report the average result on 10 hypergraphs randomly generated with each parameter configuration.
Comparison of FBC and FBCA. We first fix the values n = 200, r = 3, and p = 10 and vary the ratio of q/p from which produces hypergraphs with 250 650 edges. The performance of each algorithm on these hypergraphs is shown in Figure 3 from which we can make the following observations:
From Figure (a) we observe that FBC and FBCA find sets with very similar bipartiteness
and they perform better than the CLIQUECUT baseline.
From Figure 3 (b) can that proposed algorithms produce output with lower
3g-value than the output of the CLIQUECUT algorithm. This is surprising result given that CLIQUECUT operates directly on the clique graph.
Figure 3 (c) shows that the FBCA algorithm is much faster than FBC.
From these observations, we conclude that in practice it is sufficient to use the much faster FBCA algorithm in place of the FBC algorithm.
0.40
0:35
8:30
0.09
0.37
20
FBC
15
0.00
0:36
FBCA
0:35
0.01
0:34
u/p
4/P
(a) 0y value
(b) Salvalue
(c) Runtime
Figure 3: The average performance and standard error of each algorithm when 200, 3 and
p = 10-
Experiments on larger graphs. We now compare only the FBCA and CLiQUECUT algo- rithms, which allows us to run on hypergraphs with higher rank and number of vertices. We fix the parameters n 2000, r = 5. and p = 10-11, producing hypergraphs with be- tween 5000 and 75000 edge and show the re- sults in Figure 4 Our algorithm consistently and significantly outperforms the baseline on every metric and across wide variety of input hypergraphs.
Table 1: The runtime in seconds of the FBCA and CC algorithms.
Avg. Runtime
P
Avg. |E
FBCA
CC
10-9
1239
1.15
0.12
4
10-8
12479
10.14
0.86
10-7
124717
89.92
9.08
10-11
5177
3.99
0.62
To compare the algorithms' runtime, we fix the parameter n = 2000 and the ratio q = 2p and report the runtime of the FBCA and CC algo- rithms on a variety of hypergraphs in Table Our proposed algorithm takes more time than
5
10 10
51385
44.10
6.50
10-9
514375
368.48
69.25
In our model, very small value of and is needed since in an n-vertex, r-uniform hypergraph there are possible edges which can be very large number. In this case, (2000) 2.6 x 10

---

the baseline CC algorithm but both appear to scale linearly in the size of the input hypergraph which suggests that our algorithm's runtime is roughly constant factor multiple of the baseline.
0a1d
0478
0463
0030
6490
6455
0450
07
PBCA
6435
20 22
24
20
30
16
18
20
22
24
25
20
30
12
9/P
(a) Ba-value
(b) Va-value
(c) Fi-score
Figure 4: The average performance of each algorithm when 2000, 5, and p = 10-11 11, We omit the error bars because they are too small to read.
4.2 Real-world datasets
Next, we demonstrate the broad utility of our algorithm on complex real-world datasets with higher- order relationships which are most naturally represented by hypergraphs. Moreover, the hypergraphs are inhomogeneous, meaning that they contain vertices of different types, although this information not available to the algorithm and an algorithm has to treat every vertex identically. We demonstrate that our algorithm is able to find clusters which correspond to the vertices different types. Table 2 shows the Fi -core of the clustering produced by our algorithm each dataset and demonstrates that it consistently outperforms the CLIQUECUT algorithm.
Penn Treebank. The Penn Treebank dataset is an English-language corpus with examples of written American English from several sources, including fiction and journalism [22]. The dataset contains 49, 208 sentences and over million words, which are labelled with their part the
Table 2: The performance of the FBCA and CC algorithms on real world datasets.
Fi-Score
Dataset
Cluster
FBCA
CC
of speech. We construct hypergraph following way: the vertex set consists of all the verbs, adverbs, and adjectives which occur at least 10 times in the corpus, and for every 4-gram (a sequence edge containing the co-occurring words. This results in a hypergraph with 4, 686 vertices and 176, 286 edges. The clustering returned by algorithm correctly distinguishes between verbs and non-verbs with an accuracy of 67%. This experiment demonstrates that our unsupervised general purpose algorithm is capable of recovering non-trivial structure in dataset which would ordinarily be clustered using significant domain knowledge, or a complex pre-trained model 2 16
Penn
Verbs
0.73
0.69
Treebank
Non- Verbs
0.59
0.56
Conferences
1.00
0.25
words) we add a hyper-
DBLP
Authors
1.00
0.98
We construct hypergraph from a subset of the DBLP network consisting of 14, 376 papers published in artificial intelligence and machine learning conferences [2] (32. For each paper, include hyperedge linking the authors of the paper with the conference in which it was published, giving a hypergraph with 14, 495 vertices and 14, 376 edges. The clusters returned by our algorithm successfully separate the authors from the conferences with an accuracy of 100%.
DBLP.
Concluding remarks
In this paper, we introduce a new hypergraph Laplacian-type operator and apply this operator to design an algorithm that finds almost bipartite components in hypergraphs. Our experimental results
Although is fixed, the CLIQUECUT algorithm's runtime is not constant since the time to compute an eigenvalue of the sparse adjacency matrix scales with the number and rank of the hyperedges.

---

demonstrate the potentially wide applications of spectral hypergraph theory, and so we believe that designing faster spectral hypergraph algorithms is an important future research direction in algorithms and machine learning. This will allow spectral hypergraph techniques to be applied more effectively to analyse the complex datasets which occur with increasing frequency in the real world.
Acknowledgements
Peter Macgregor is supported by the Langmuir PhD Scholarship, and He Sun is supported by an EPSRC Early Career Fellowship (FP/T00729X/1).
References
[1] Sameer Agarwal, Jongwoo Lim, Lihi Zelnik-Manor, Pietro Perona, David Kriegman, and Serge Belongie. Beyond pairwise clustering. In Annual Conference on Computer Vision and Pattern Recognition (CVPR 005), volume 2. pages 838-845, 2005.
[2] Alan Akbik, Duncan Blythe, and Roland Vollgraf. Contextual string embeddings for sequence labeling. In 27th International Conference on Computational Linguisties (COLING 18), pages 1638-1649, 2018.
[3] Reid Andersen, Fan Chung, and Kevin Lang. Local graph partitioning using Pagerank vectors. In 2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06 pages 475-486, 2006.
[4] Anirban Banerjee. On the spectrum of hypergraphs. Linear Algebra and its Applications, 614:82-110, 2021.
[5] T.-H. Hubert Chan, Anand Louis, Zhihao Gavin Tang, and Chenzi Zhang. Spectral properties of hypergraph Laplacian and approximation algorithms. Journal of the ACM, 65(3):1 2018.
[6] I. Chien, Chung-Y: Yi Lin, and I.-Hsiang Wang. Community detection in hypergraphs: Opti- mal statistical limit and efficient algorithms. In 21st International Conference on Artificial Intelligence and Statisties (AISTATS' 18), pages 871-879, 2018
[7] Uthsav Chitra and Benjamin J Raphael. Random walks hypergraphs with edge-dependent vertex weights. In 36th International Conference on Machine Learning (ICML' pages 2002-2011, 2019.
2019.
[8] Fan Chung. The Laplacian of hypergraph. Expanding graphs (DIMACS series), pages 21-36. 1993.
[9] Fan Chung. The heat kernel as the Pagerank of a graph. Proceedings of the National Academy of Sciences, 10455)) 2007.
[10] Fan Chung. A local graph partitioning algorithm using heat kernel Pagerank. Internet Mathe- matics, 6(3):315-344 2009.
[11] Michael B. Cohen, Yin Tat Lee, and Zhao Song. Solving linear programs in the current matrix multiplication time. Journal of the ACM, 68(1):1-39, 2021.
[12] DBLP computer science bibliography. https://dblp... uni ceanttiir.dde de/ 2021.
Accessed: May
[13] Kimon Fountoulakis, Pan Li, and Shenghao Yang. 2rX1v:2102.07945. March 2021.
Local hyper-flow diffusion.
[14] Kimon Fountoulakis, Di Wang, and Shenghao Yang. p-Norm flow diffusion for local graph clustering. In 37th International Conference on Machine Learning (ICML'20), pages 3222- 3232, 2020.
[15] Debarghya Ghoshdastidar and Ambedkar Dukkipati. Consistency of spectral partitioning of uniform hypergraphs under planted partition model. 28th Advances in Neural Information Processing Systems (NeurIPS' 144), volume 27, pages 397-405, 2014.
10

---

[16] Sharon Goldwater and Tom Griffiths. A fully Bayesian approach to unsupervised part-of-speech tagging. In 45th Annual Meeting of the Association of Computational Linguisties (ACL (7)), pages 744-751, 2007.
[17] Kyle Kloster and David F. Gleich. Heat kernel based community detection. In 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD'14) 14), pages 1336-1399) 2014.
[18] Marius Leordeanu and Cristian Sminchisescu. Efficient hypergraph clustering. In 15th Inter- national Conference on Artificial Intelligence and Statistics (AISTATS' 12), pages 676-684, 2012.
[19] Pan Li and Olgica Milenkovic. Inhomogeneous hypergraph clustering with applications. In 31 Advances in Neural Information Processing Systems (NeurIPS pages 2308-2318, 2017.
[20] Pan Li and Olgica Milenkovic. Submodular hypergraphs: p-Laplacians, Cheeger inequalities and spectral clustering. In 35th International Conference on Machine Learning (ICML' 18), pages 4690-4719, 2018.
[21] Peter Macgregor and He Sun. Local algorithms for finding densely connected clusters. In 38th International Conference on Machine Learning (ICML'21), pages
2021.
[22] Mitchell P. Marcus, Mary Ann Marcinkiewicz, and Beatrice Santorini. Building a large annotated corpus of English: the penn treebank. Computational Linguistics, 19(2):11-330, 1993.
[23] Cristopher Moore, Xiaoran Yan, Yaojia Zhu, Bean-Baptiste Rouquier, and Terran Lane. Active learning for node classification in assortative and disassortative networks. In 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD'1I) pages 841-849, 2011.
[24] Andrew Y. Ng. Michael I. Jordan, and Yair Weiss. On spectral clustering: Analysis and an algorithm. 15th Advances in Neural Information Processing Systems (NeurIPS pages 849-856 2001.
[25] Andrew Seary and William D Richards. Spectral methods for analyzing and visualizing networks: an introduction. In Dynamic Social Network Modeling and Analysis: Workshop Summary and Papers. Citeseer, 2003.
[26] Jianbo Shi and Jitendra Malik.
Normalized cuts and image segmentation. In Annual Conference on Computer Vision and Pattern Recognition (CVPR'97) pages 731-737, 1997.
[27] Yuuki Takai, Atsushi Miyauchi, Masahiro Ikeda, and Yuichi Yoshida. Hypergraph clustering based on Pagerank. In 26th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD 20), pages 1970-1978, 2020.
[28] Luca Trevisan. Max cut and the smallest eigenvalue. SIAM Journal on Computing, 41(66)1769- 1786, 2012.
[29] Jan van den Brand. A deterministic linear program solver in current matrix multiplication time. In 31st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '20), pages 259-278, 2020.
[30] Cornelis Joost Van Rijshergen. The geometry of information retrieval. Cambridge University Press, 2004.
[31] Ulrike von Luxburg. A tutorial on spectral clustering. Statisties and Computing, 174tttinn..771111)))11 17(4):395-416. 2007.
[32] Xiao Wang, Houye Ji, Chuan Shi, Bai Wang. Yanfang Ye, Peng Cui, and Philip S. Yu. Het- erogeneous graph attention network. In The World Wide Web Conference, pages 2022-2032, 2019.
[33] Yuichi Yoshida. Cheeger inequalities for submodular transformations. In 30th Annual ACM- SIAM Symposiun Discrete Algorithms (SODA' 19),, pages 2582-2601, 2019.
11

---

[34] Jiawei Zhang, Yinyu Ye, and Qiaoming Han. Improved approximations for max set splitting and max NAE SAT. Discrete Applied Mathematics, 142(1-3):133-144) 1493,114,490 2004.
[35] Dengyong Zhou, Jiayuan Huang, and Berhhard Schölkopf. Learning with hypergraphs: Cluster- ing, classification, and embedding. In 20th Advances in Neural Information Processing Systems (NeurlPS 06), pages 1601-1608, 2006.
[36] Jiong Zhu, Yujun Yan, Lingxiao Zhao, Mark Heimann, Leman Akoglu, and Danai Koutra. Beyond homophily in graph neural networks: Current limitations and effective designs. In 33rd Advances in Neural Information Processing Systems (NeurIPS 20), pages 7793-7804, 2020.
12


Reviews:
[{"review_id": "cddq43kLEf0", "reviewer": "Reviewer_PH5A", "summary": "This paper proposes a polynomial-time algorithm that finds densely connected bipartite components in a hypergraph. The algorithm is based on a heat diffusion process generalized from graphs to hypergraphs. Cheeger-type approximation guarantee is established. Empirical results show that the new method has superior performance for both synthetic and real hypergraphs.", "questions": "", "limitations": "", "rating": 7, "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": "Hypergraphs and related nonlinear Laplacian operators received renewed interests recently in both machine learning and applied mathematics communities. The heat diffusion process studied in this paper is a nice addition, in particular it applies to find bipartite components in hypergraphs, which is a different application from most previous works. At the same time, the nonlinear operator considered in this work is simple and intuitive.\n\nTechnical analyses is this paper appear to be clear and solid. Overall I think the paper is well written and it solves an interesting problem. Empirical results are promising and further support the usefulness of the proposed method. \n\nI have a few minor comments:\n\n- line 129-131: Why is it intuitive that the rate of change should involve only the maximum and minimum values? Apparently this is the simplest case, but in more complex settings (e.g. when one models more complex higher-order relations as in [22]) can it depend on other node values as well? The formulation considered in this paper seems to correspond to hypergraphs modelled by all-or-nothing cut (or equivalently the unit cut-cost in [13]). Can the heat diffusion process be generalized to more complex higher-order relations among nodes within a hypergraph? More explanations are needed.\n\n- Baseline: Following footnote 4, another baseline could be $f_1(\\mathcal{J}_G)$. Although the authors explained in the supplementary material that the worst-case performance guarantee using $f_1(\\mathcal{J}_G)$ is scaled by a factor of $r$ the rank of hyperedge, it would provide additional information to the reader about the practical importance of the new method.\n\n- Synthetic experiments: Since you have the ground-truth information can you also show the F1 scores?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I cannot think of any potential negative societal impact based on this work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "JOfBnNBsBF0", "reviewer": "Reviewer_SWke", "summary": "The paper discusses how to find bipartite components in a hyper graph.  A bipartite component consists of two subsets of vertices L and R.  Bipartite implies  there is minimal connection within L as well as within R.  Component implies that there is minimal connection between vertices in L union R and vertices outside.  \n\nThe algorithm is based on diffusion process to find sets with small hyper graph bipartiteness.  The paper provides a couple of theorems for the existence of a polynomial algorithm.  Experiments are conducted on both synthetic as well as real-world datasets, including Penn Treebank and DBLP.", "questions": "", "limitations": "", "rating": 6, "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": "On the plus side, the paper gives a formal treatment of the problem.  It is written rigorously, if rather densely, but the key ideas come across.  It is also good that the experiments explore both synthetic datasets (to look at the runtime with increasing size) as well as real-world datasets (to explore potential applications).\n\nOne weakness of the paper is that it is light on applications.  It is not clear to me whether there will be many occasions in which we'd be looking for bipartite components in a hyper graph.  While the paper gives an example on Peen Treebank, claiming that it is achieving good performance given that it is an unsupervised general purpose algorithm, this seems to still be a contrived example.  The discussion on DBLP is similarly vague, saying that the algorithm can separate authors from conferences, but I imagine that task wouldn't really be an actual application.\n\nAnother point is the computational complexity relative to the baseline clique cut algorithm, which is much faster (by an order of magnitude or thereabout).  While the proposed method produces \"some\" improvement, some discussion on whether the difference justifies the large increase in computational cost.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The paper itself does not contain an ethics statement, though the authors acknowledged that they have read the ethics guidelines.\n\nAs suggestions for improvements, the paper would be a lot stronger if it could be motivated by real applications that someone actually wants to solve.  As of now the evaluations are rather contrived.\n\nThere should also be some discussions on the large increase of computational time relative to CC, and what could be done about it or why the increase is justified.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1"}, "extra_text": {}}, {"review_id": "5Iw9ggJ7z4V", "reviewer": "Reviewer_Xs5P", "summary": "This paper proposes a diffusion-based algorithm for finding bipartite components in hypergraphs. The work rigorously analyzes the algorithm and provides theoretical guarantees. ", "questions": "", "limitations": "", "rating": 6, "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": "This paper uses a diffusion-based algorithm that requires multiple iterations for convergence.  Therefore, it comes with high computational complexity. The complexity analysis of algorithm is missing. Further, the empirical time complexity (Table 1) shows that the algorithm is not scalable to large-scale networks with millions of nodes where the problem is much more relevant. More experimental results and computation complexity justification is required to assess the practical significance of the work. The work extends the theoretical understanding of the diffusion process, especially for hyper-graphs which is a major strength of this work. \n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"ethical_concerns": "None", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}]

Author rebuttal:

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