${C}_{k+2}$ of size $n^{\prime}$. For $u,v\in{C}_{k+i}$ for $i\in\\{1,2\\}$,
there is an edge between $u$ and $v$ with probability $p$ and for
$u\in{C}_{k+1}$ and $v\in{C}_{k+2}$, there is an edge with probability
$q^{\prime}_{1}$; the edge directions are chosen uniformly at random. For
$u\in{C}_{k+1}\cup{C}_{k+2}$ and $v\in{C}_{1}$, there is an edge with
probability $q^{\prime}_{2}$. If $u\in{C}_{k+1}$, the orientation is from $v$
to $u$ with probability $\eta^{\prime}$ and from $u$ to $v$ with probability
$1-\eta^{\prime}$ and if $u\in{C}_{k+2}$, the orientation is from $u$ to $v$
with probability $\eta^{\prime}$ and from $v$ to $u$ with probability
$1-\eta^{\prime}$. We always fix $q^{\prime}_{1}=0.5$, $q^{\prime}_{2}=0.005$,
and $\eta^{\prime}=1$. Notice that the clusters ${C}_{k+1}$ and ${C}_{k+2}$
form a ‘local’ cycle with the cluster ${C}_{1}$.

Table 6.2 reports the average performance over 10 runs with a variety of
parameters. We can see that CLSZ uncovers the global structure in the CBM more
accurately than ECD. On the other hand, CLSZ fails to identify the local cycle
in the CBM+ model, while ECD succeeds.

Table 6.2: Comparison of ECD with CLSZ on synthetic data.  |  |  |  | Time | ARI
---|---|---|---|---|---
Model | $n^{\prime}$ | $n$ | $k$ | ECD | CLSZ | ECD | CLSZ
CBM | - | $10^{3}$ | $5$ | $\mathbf{1.59}$ | $3.99$ | $0.92$ | $\mathbf{1.00}$
CBM | - | $10^{3}$ | $50$ | $\mathbf{3.81}$ | $156.24$ | $0.99$ | $0.99$
CBM+ | $10^{2}$ | $10^{3}$ | $3$ | $\mathbf{0.24}$ | $6.12$ | $\mathbf{0.98}$ | $0.35$
CBM+ | $10^{2}$ | $10^{4}$ | $3$ | $\mathbf{0.32}$ | $45.17$ | $\mathbf{0.99}$ | $0.01$

###### Real-world dataset.

Now we evaluate the algorithms’ performance on the US Migration Dataset [CB].
For fair comparison, we follow Cucuringu et al. [CLSZ20] and construct the
directed graph as follows: every county in the mainland USA is represented by
a vertex; for any vertices $j,\ell$, the edge weight of $(j,\ell)$ is given by

$\left|\frac{{\mathbf{M}}_{j,\ell}-{\mathbf{M}}_{\ell,j}}{{\mathbf{M}}_{j,\ell}+{\mathbf{M}}_{\ell,j}}\right|,$

where ${\mathbf{M}}_{j,\ell}$ is the number of people who migrated from county
$j$ to county $\ell$ between 1995 and 2000; in addition, the direction of
$(j,\ell)$ is set to be from $j$ to $\ell$ if
${\mathbf{M}}_{j,\ell}>{\mathbf{M}}_{\ell,j}$, otherwise the direction is set
to be the opposite.

For CLSZ, we follow their suggestion on the same dataset and set $k=10$. Both
algorithms’ performance is evaluated with respect to the flow ratio, as well
as the cut imbalance ratio used in their work. For any vertex sets ${L}$ and
${R}$, the cut imbalance ratio is defined by

$\mathrm{CI}({L},{R})=\frac{1}{2}\cdot\left|\frac{{w}({L},{R})-{w}({R},{L})}{{w}({L},{R})+{w}({R},{L})}\right|,$

and a higher $\mathrm{CI}({L},{R})$ value indicates the connection between
${L}$ and ${R}$ is more significant. Using counties in Ohio, New York,
California, and Florida as the starting vertices, the outputs of
EvoCutDirected are visualised in Figures 6.2, and in Table 6.3 we compare them
to the top $4$ pairs returned by CLSZ, which are shown in Figure 6.8. The new
algorithm produces better outputs with respect to the two metrics.

(a) CLSZ, Pair 1

(b) CLSZ, Pair 2

(c) CLSZ, Pair 3

(d) CLSZ, Pair 4

Figure 6.8:  The top $4$ pairs of clusters found by CLSZ on the US Migration
dataset.  Table 6.3: Comparison of EvoCutDirected with CLSZ on the US
migration dataset.
Figure | Algorithm | Cluster | Cut Imbalance | Flow Ratio
---|---|---|---|---
6.8(a) | CLSZ | Pair 1 | $0.41$ | $0.80$
6.8(b) | CLSZ | Pair 2 | $0.35$ | $0.83$
6.8(c) | CLSZ | Pair 3 | $0.32$ | $0.84$
6.8(d) | CLSZ | Pair 4 | $0.29$ | $0.84$
6.2(a) | EvoCutDirected | Ohio Seed | $0.50$ | $0.56$
6.2(b) | EvoCutDirected | New York Seed | $0.49$ | $0.58$
6.2(c) | EvoCutDirected | California Seed | $0.49$ | $0.67$
6.2(d) | EvoCutDirected | Florida Seed | $0.42$ | $0.79$

These experiments suggest that local algorithms are not only more efficient,
but can also be much more effective than global algorithms when learning
certain structures in graphs. In particular, some localised structure might be
hidden when applying the objective function over the entire graph.

###  6.4 Future Work

This chapter presents a novel graph reduction technique, and applies this to
design two local algorithms for learning a certain structure of clusters in
both undirected and directed graphs. Our experimental results further
demonstrate their potential wide applications in learning meaningful
structures of real-world datasets. Our work leaves several open questions for
future work.

Firstly, there is a gap between the approximation guarantee of the algorithm
for directed graphs when compared with undirected graphs, and it looks very
challenging to close this gap with the techniques presented in this chapter.
To understand this, it is insightful to discuss why Algorithm 1 cannot be
applied for directed graphs, although the input graph is translated into an
_undirected_ graph by the semi-double cover reduction. This is because, when
translating a directed graph into a bipartite undirected graph, the third
property of the $\sigma$-operator in Lemma 6.2 no longer holds, since the
existence of the edge $\\{u_{1},v_{2}\\}\in{E}_{H}$ does not necessarily imply
that $\\{u_{2},v_{1}\\}\in{E}_{H}$. Indeed, Figure 6.9 gives a counterexample
in which
$\left(\sigma\circ({\mathbf{W}}{\bm{p}})\right)(u)\not\leq\left({\mathbf{W}}(\sigma\circ{\bm{p}})\right)(u)$.

$\xrightarrow{}$$\begin{bmatrix}{\mathbf{B}}_{1}&{\mathbf{0}}&{\mathbf{0}}\\\
{\mathbf{0}}&{\mathbf{B}}_{2}&{\mathbf{0}}\\\
{\mathbf{0}}&{\mathbf{0}}&{\mathbf{B}}_{3}\end{bmatrix}$$\xrightarrow{}$Graph
${G}$Normalised Laplacian ${\mathbf{N}}$Spectral
Embedding$\xrightarrow{}$$\begin{bmatrix}{\mathbf{B}}_{1}&{\mathbf{C}}_{12}&{\mathbf{C}}_{13}\\\
{\mathbf{C}}_{12}^{\intercal}&{\mathbf{B}}_{2}&{\mathbf{C}}_{23}\\\
{\mathbf{C}}_{13}^{\intercal}&{\mathbf{C}}_{23}^{\intercal}&{\mathbf{B}}_{3}\end{bmatrix}$$\xrightarrow{}$Graph
${G}$Normalised Laplacian ${\mathbf{N}}$Spectral
Embedding$\rightarrow$$v_{1}$$v_{3}$$v_{5}$$v_{4}$$v_{2}$$\rightarrow$$x_{1}=v_{1}$$x_{2}=v_{4}$$x_{3}=v_{5}$${\bm{p}}^{(i)}$${\bm{p}}^{(j)}$$\frac{{\bm{p}}^{(i)}}{\left\|{\bm{p}}^{(i)}\right\|}$$\frac{{\bm{p}}^{(j)}}{\left\|{\bm{p}}^{(j)}\right\|}$${\bm{a}}_{i}$${\bm{a}}_{j}$$\frac{\left\|{\bm{a}}_{i}\right\|}{\left\|{\bm{a}}_{j}\right\|}{\bm{a}}_{j}$$a_{1}$$a_{2}$$a$$b$$c$$d$$\Longrightarrow$$b_{1}$$b_{2}$$c_{1}$$c_{2}$$d_{1}$$d_{2}$$\cdots$$a_{1}$$S$$b_{1}$$c_{1}$$d_{1}$$e_{1}$$f_{1}$$\cdots$$\cdots$$a_{2}$$b_{2}$$c_{2}$$d_{2}$$e_{2}$$f_{2}$$\cdots$$a_{1}$$a_{2}$$a$$b$$c$$d$$\Longrightarrow$$b_{1}$$b_{2}$$c_{1}$$c_{2}$$d_{1}$$d_{2}$$a_{1}$$b_{1}$$a_{2}$$b_{2}$ab$\Longrightarrow$
Figure 6.9: Consider the directed graph and its semi-double cover above.
Suppose ${\bm{p}}(a_{1})={\bm{p}}(a_{2})=0.5$ and
${\bm{p}}(b_{1})={\bm{p}}(b_{2})=0$. It is straightforward to check that
$(\sigma\circ({\mathbf{W}}{\bm{p}}))(b_{2})=0.25$ and
$({\mathbf{W}}(\sigma\circ{\bm{p}}))(b_{2})=0$.

This means that the typical analysis of a Pagerank vector with the Lovász-
Simonovitz curve cannot be applied anymore. In addition, it is interesting to
note that one cannot apply the tighter analysis of the ESP process given by
Andersen et al. [AOGPT16] to the new algorithm in this chapter. The key to
their analysis is an improved bound on the probability that a random walk
escapes from the target cluster. This bound given a better guarantee for the
conductance of the output set at the cost of a relaxed guarantee on the
overlap between the output set and the target set. Since the analysis for
directed graphs in this chapter relies on a very tight guarantee on the
overlap of the output set with the target set, we cannot use their improvement
in this setting. These difficulties leave the following important open
question.

######  Open Question 5.

Suppose we are given a directed graph ${G}=({V},{E})$ containing clusters
${L},{R}\subset{V}$ with $F({L},{R})=\phi$. Is there a local algorithm which
is guaranteed to return ${L}^{\prime},{R}^{\prime}\subset{V}$ with
$F({L}^{\prime},{R}^{\prime})=\widetilde{O}(\sqrt{\phi})$?

Secondly, although this chapter shows that two densely connected clusters can
be approximately recovered with local algorithms, it would be very interesting
to know whether our presented technique can be generalised to find clusters
whose structure is defined by some meta-graph as described in Chapter 5.

######  Open Question 6.

Suppose we are given a graph ${G}=({V},{E})$, and
${S}_{1},\ldots,{S}_{k}\subset{V}$ are clusters defined with respect to some
meta-graph. Is there a local algorithm that approximately recovers these
${S}_{1},\ldots,{S}_{k}$?

## Chapter 7Finding Bipartite Components in Hypergraphs

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 chapter 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 study the performance of the proposed algorithm, and compare it
against the previous state-of-the-art through extensive experimental analysis
on both synthetic and real-world datasets. We see that the new algorithm
consistently and significantly outperforms the previous state-of-the-art
across a wide range of hypergraphs. The problem studied in this chapter can be
seen as a generalisation of the problem studied in the previous chapter,
although we study algorithms in the global setting rather than the local one.

A unifying theme of this thesis is the design of efficient algorithms based on
spectral methods, which study the graph Laplacian matrix in particular. The
results of the present chapter form part of a sequence of work to generalise
many of the results of spectral graph theory to hypergraphs. We introduce and
study the non-linear Laplacian-type operator ${\mathbf{J}}_{H}$ for any
hypergraph ${H}$. While we formally define the operator ${\mathbf{J}}_{H}$ in
Section 7.3, one can informally think about ${\mathbf{J}}_{H}$ as a variant of
the non-linear hypergraph Laplacian ${\mathbf{L}}_{H}$ studied in [CLTZ18,
LM18, TMIY20] which generalises the _signless Laplacian operator_ of graphs.
We develop a polynomial-time algorithm that finds an eigenvalue $\lambda$ and
its associated eigenvector of ${\mathbf{J}}_{H}$.

######  Main Result 6 (See Theorem 7.2 for the formal statement).

Given a hypergraph ${H}$, there is a non-linear operator ${\mathbf{J}}_{H}$
which generalises the signless graph Laplacian operator for hypergraphs.
Moreover, there is a polynomial-time algorithm that finds an eigenvalue of
${\mathbf{J}}_{H}$ along with its associated eigenvector.

The algorithm is based on the following heat diffusion process: starting from
an arbitrary vector ${\bm{f}}_{0}\in\mathbb{R}^{n}$ that describes the initial
heat distribution among the vertices, we use ${\bm{f}}_{0}$ to construct some
graph111Note that the word ‘graph’ always refers to a non-hyper graph.
Similarly, we always use ${\mathbf{L}}_{H}$ to refer to the _non-linear_
hypergraph Laplacian operator, and use ${\mathbf{L}}_{G}$ as the standard
graph Laplacian. ${G}_{0}$, and use the diffusion process in ${G}_{0}$ to
represent the one in the original hypergraph ${H}$ and update ${\bm{f}}_{t}$;
this process continues until the time at which ${G}_{0}$ cannot be used to
appropriately simulate the diffusion process in ${H}$ any more. At this point,
we use the currently maintained ${\bm{f}}_{t}$ to construct another graph
${G}_{t}$ to simulate the diffusion process in ${H}$, and update
${\bm{f}}_{t}$. This process continues until the vector ${\bm{f}}_{t}$
converges; see Figure 7.1 for illustration. We prove that this heat diffusion
process is unique, well-defined, and the maintained vector ${\bm{f}}_{t}$
converges to an eigenvector of ${\mathbf{J}}_{H}$.

$\xrightarrow{}$$\begin{bmatrix}{\mathbf{B}}_{1}&{\mathbf{0}}&{\mathbf{0}}\\\
{\mathbf{0}}&{\mathbf{B}}_{2}&{\mathbf{0}}\\\
{\mathbf{0}}&{\mathbf{0}}&{\mathbf{B}}_{3}\end{bmatrix}$$\xrightarrow{}$Graph
${G}$Normalised Laplacian ${\mathbf{N}}$Spectral
Embedding$\xrightarrow{}$$\begin{bmatrix}{\mathbf{B}}_{1}&{\mathbf{C}}_{12}&{\mathbf{C}}_{13}\\\
{\mathbf{C}}_{12}^{\intercal}&{\mathbf{B}}_{2}&{\mathbf{C}}_{23}\\\
{\mathbf{C}}_{13}^{\intercal}&{\mathbf{C}}_{23}^{\intercal}&{\mathbf{B}}_{3}\end{bmatrix}$$\xrightarrow{}$Graph
${G}$Normalised Laplacian ${\mathbf{N}}$Spectral
Embedding$\rightarrow$$v_{1}$$v_{3}$$v_{5}$$v_{4}$$v_{2}$$\rightarrow$$x_{1}=v_{1}$$x_{2}=v_{4}$$x_{3}=v_{5}$${\bm{p}}^{(i)}$${\bm{p}}^{(j)}$$\frac{{\bm{p}}^{(i)}}{\left\|{\bm{p}}^{(i)}\right\|}$$\frac{{\bm{p}}^{(j)}}{\left\|{\bm{p}}^{(j)}\right\|}$${\bm{a}}_{i}$${\bm{a}}_{j}$$\frac{\left\|{\bm{a}}_{i}\right\|}{\left\|{\bm{a}}_{j}\right\|}{\bm{a}}_{j}$$a_{1}$$a_{2}$$a$$b$$c$$d$$\Longrightarrow$$b_{1}$$b_{2}$$c_{1}$$c_{2}$$d_{1}$$d_{2}$$\cdots$$a_{1}$$S$$b_{1}$$c_{1}$$d_{1}$$e_{1}$$f_{1}$$\cdots$$\cdots$$a_{2}$$b_{2}$$c_{2}$$d_{2}$$e_{2}$$f_{2}$$\cdots$$a_{1}$$a_{2}$$a$$b$$c$$d$$\Longrightarrow$$b_{1}$$b_{2}$$c_{1}$$c_{2}$$d_{1}$$d_{2}$$a_{1}$$b_{1}$$a_{2}$$b_{2}$ab$\Longrightarrow$$0.5$$0.5$$0.5$$0.5$$0.5$$0.5$$0.5$$0.5$$0.62$$0.38$$1.0$$0.38$$0.62$$1.0$$1.0$$0.5$$0.25$$0.25$$1.0$$1.0$$0.5$$0.5$$\begin{bmatrix}1\\\
0\\\ 0\\\ 0\\\ 0\\\
0\end{bmatrix}$$\rightarrow$$\rightarrow$$t=0$$t=1$$\begin{bmatrix}0.29\\\
-0.14\\\ -0.14\\\ 0.02\\\ 0.02\\\
0.02\end{bmatrix}$$\rightarrow$$\rightarrow$$t=3$$\begin{bmatrix}0.11\\\
-0.09\\\ -0.09\\\ 0.04\\\ 0.04\\\
0.04\end{bmatrix}$$\rightarrow$$\rightarrow$$t=4$$\begin{bmatrix}0.09\\\
-0.71\\\ -0.71\\\ 0.03\\\ 0.03\\\
0.03\end{bmatrix}$$\rightarrow$$\rightarrow$$t=23$$\begin{bmatrix}0.03\\\
-0.03\\\ -0.03\\\ 0.03\\\ -0.03\\\
-0.03\end{bmatrix}$$v_{1}$$v_{2}$$v_{3}$$v_{5}$$v_{4}$${\bm{f}}_{t}$${\bm{f}}_{t}$${\bm{f}}_{t}$${\bm{f}}_{t}$${\bm{f}}_{t}$$v_{6}$

Figure 7.1: Illustration of the proposed diffusion process. In each time step,
we construct a graph ${G}$ based on the current vector ${\bm{f}}_{t}$, and
update ${\bm{f}}_{t}$ with the ${\mathbf{J}}_{G}$ operator. Notice that the
graph ${G}$ changes throughout the execution of the algorithm, and that the
final ${\bm{f}}_{t}$ vector can be used to partition the vertices of ${H}$
into two well-connected sets (all the edges are adjacent to both sets), by
splitting according to positive and negative entries.

The second result of this chapter is a polynomial-time algorithm that, given a
hypergraph ${H}=({V}_{H},{E}_{H},{w})$ as input, finds disjoint subsets
${L},{R}\subset{V}_{H}$ that are highly connected with each other.

######  Main Result 7 (See Theorem 7.1 for the formal statement).

Suppose we are given a hypergraph ${H}=({V}_{H},{E}_{H},{w})$, and an
eigenvalue $\lambda$ of the operator ${\mathbf{J}}_{H}$ with its corresponding
eigenvector. There is an algorithm that finds two clusters
${L},{R}\subset{V}_{H}$ such that ${\beta}_{H}({L},{R})\leq\sqrt{2\lambda}$,
where ${\beta}_{H}$ is the _hypergraph bipartiteness_.

The key to this algorithm is a Cheeger-type inequality for hypergraphs that
relates the spectrum of ${\mathbf{J}}_{H}$ and the _hypergraph bipartiteness_
of ${H}$, an analogue of the graph bipartiteness studied in Chapter 6. Both
the design and analysis of the algorithm is inspired by Trevisan [Tre12],
however the analysis is much more involved because of the non-linear operator
${\mathbf{J}}_{H}$ and hyperedges of different ranks. This result alone
answers an open question posed by Yoshida [Yos19], who asks whether there is a
hypergraph operator which satisfies a Cheeger-type inequality for
bipartiteness.

The significance of our algorithmic result is demonstrated by extensive
experimental studies of the algorithm on both synthetic and real-world
datasets. In particular, on the well-known Penn Treebank corpus that contains
49,208 sentences and over 1 million words, our _purely unsupervised_ algorithm
is able to identify a significant fraction of verbs from non-verbs in its two
output clusters. Hence, this work could potentially have many applications in
unsupervised learning for hypergraphs.

Finally, we study the spectrum of the non-linear Laplacian-type operators for
hypergraphs, and show that, for any $n\in\mathbb{Z}_{\geq 0}$, there is a
hypergraph on $n$ vertices such that ${\mathbf{L}}_{H}$ and ${\mathbf{J}}_{H}$
have more than $n$ eigenvectors. This answers an open question posed by Chan
et al. [CLTZ18], who ask whether ${\mathbf{L}}_{H}$ could have more than $2$
eigenvectors222Notice that, while the operator ${\mathbf{L}}_{G}$ of a graph
${G}$ has $n$ eigenvalues, the number of eigenvalues of ${\mathbf{L}}_{H}$ is
unknown because of its non-linearity..

###  7.1 Additional Notation

In order to study densely connected clusters in hypergraphs, we need some new
notation and definitions. Suppose, we have a hypergraph ${H}=({V},{E},{w})$,
then for any ${A},{B}\subset{V}$ we can overload the weight function to define
the cut value between ${A}$ and ${B}$ by

${w}({A},{B})\triangleq\sum_{e\in{E}}{w}(e)\cdot\boldsymbol{\left[\vphantom{e\cap{A}\neq\emptyset\land
e\cap{B}\neq\emptyset}\right.}e\cap{A}\neq\emptyset\land
e\cap{B}\neq\emptyset\boldsymbol{\left.\vphantom{e\cap{A}\neq\emptyset\land
e\cap{B}\neq\emptyset}\right]}.$

Sometimes, we would like to analyse the weights of edges that intersect some
vertex sets and not others. To this end, for any ${A},{B},{C}\subseteq{V}$,
let

${w}({A},{B}~{}|~{}{C})\triangleq\sum_{e\in{E}}{w}(e)\cdot\boldsymbol{\left[\vphantom{e\cap{A}\neq\emptyset\land
e\cap{B}\neq\emptyset\land e\cap
C=\emptyset}\right.}e\cap{A}\neq\emptyset\land e\cap{B}\neq\emptyset\land
e\cap C=\emptyset\boldsymbol{\left.\vphantom{e\cap{A}\neq\emptyset\land
e\cap{B}\neq\emptyset\land e\cap C=\emptyset}\right]},$

and we can also define ${w}({A}~{}|~{}{C})\triangleq{w}({A},{A}~{}|~{}{C})$
for simplicity. Generalising the notion of the bipartiteness of a graph, the
hypergraph bipartiteness of sets ${L},{R}\subset{V}$ is defined by

${\beta}_{H}({L},{R})\triangleq\frac{2{w}({L}|\overline{{L}})+2{w}({R}|\overline{{R}})+{w}({L},\overline{{L}}|{R})+w({R},\overline{{R}}|{L})}{\mathrm{vol}({L}\cup{R})},$

and we define

${\beta}_{H}\triangleq\min_{{S}\subset{V}_{H}}{\beta}_{H}({S},{V}_{H}\setminus{S}).$

This definition generalises the graph bipartiteness (Definition 3.3) in that,
if every edge in ${H}$ contains $2$ vertices, then ${H}$ is a (non-hyper)
graph and ${\beta}_{H}({L},{R})$ is equivalent to the graph bipartiteness.
Informally, a low value of ${\beta}_{H}({L},{R})$ indicates that most of the
edges which intersect either ${L}$ or ${R}$ connect ${L}$ and ${R}$ together.
The goal of this chapter is to develop an algorithm to find such sets ${L}$
and ${R}$ in a hypergraph.

For any hypergraph $H$ and ${\bm{f}}\in\mathbb{R}^{n}$, we define the
discrepancy of an edge $e\in{E}_{H}$ with respect to ${\bm{f}}$ as

${\Delta}_{{\bm{f}}}(e)\triangleq\max_{u\in e}{\bm{f}}(u)+\min_{v\in
e}{\bm{f}}(v).$

Moreover, the weighted discrepancy of $e\in{E}_{H}$ is

$c_{{\bm{f}}}(e)\triangleq{w}(e)\left\lvert{\Delta}_{{\bm{f}}}(e)\right\rvert,$

and for any set ${S}\subseteq{E}_{H}$ we have

$c_{{\bm{f}}}({S})\triangleq\sum_{e\in{S}}c_{{\bm{f}}}(e).$

The discrepancy of ${H}$ with respect to ${\bm{f}}$ is defined by

$D({\bm{f}})\triangleq\frac{\sum_{e\in{E}_{H}}{w}(e)\cdot{\Delta}_{{\bm{f}}}(e)^{2}}{\sum_{v\in{V}_{H}}{d}_{H}(v)\cdot{\bm{f}}(v)^{2}}.$

For any ${\bm{f}},{\bm{g}}\in\mathbb{R}^{n}$, the weighted inner product
between ${\bm{f}}$ and ${\bm{g}}$ is defined by

$\left\langle{\bm{f}},{\bm{g}}\right\rangle_{w}\triangleq{\bm{f}}^{\intercal}{\mathbf{D}}_{H}{\bm{g}},$

where ${\mathbf{D}}_{H}\in\mathbb{R}^{n\times n}$ is the diagonal matrix
consisting of the degrees of all the vertices of ${H}$. The weighted norm of
${\bm{f}}$ is defined by
$\left\|{\bm{f}}\right\|_{w}^{2}\triangleq\left\langle{\bm{f}},{\bm{f}}\right\rangle_{w}$.

For any non-linear operator
${\mathbf{J}}:\mathbb{R}^{n}\mapsto\mathbb{R}^{n}$, we say that
$(\lambda,{\bm{f}})$ is an eigen-pair if and only if
${\mathbf{J}}{\bm{f}}=\lambda{\bm{f}}$. Note that in contrast with linear
operators, a non-linear operator does not necessarily have $n$ eigenvalues.
Additionally, we define the weighted Rayleigh quotient of the operator
${\mathbf{J}}$ and vector ${\bm{f}}$ to be

$R_{\mathbf{J}}({\bm{f}})\triangleq\frac{{\bm{f}}^{\intercal}{\mathbf{J}}{\bm{f}}}{\left\|{\bm{f}}\right\|_{w}^{2}}.$

It is important to remember that throughout this chapter the letter ${H}$ is
always used to represent a hypergraph, and ${G}$ to represent a graph.

###  7.2 Baseline Algorithms

Before we present the new algorithm, let us first consider the baseline
algorithms for finding bipartite components in hypergraphs. One natural idea
is to construct a graph ${G}$ from the original hypergraph ${H}$ and apply a
graph algorithm on ${G}$ to find a good approximation of the cut structure of
${H}$ [CR19, LM17, ZHS06]. However, most graph reductions would introduce a
factor of $r$, which relates to the rank of hyperedges in ${H}$, into the
approximation guarantee. To see this, consider the following two natural graph
reductions:

  1. 1.

Random Reduction: From ${H}=({V},{E}_{H})$, we construct ${G}=({V},{E}_{G})$
in which every hyperedge $e\in{E}_{H}$ is replaced by an edge connecting two
randomly chosen vertices in $e$;

  2. 2.

Clique Reduction: From ${H}=({V},{E}_{H})$, we construct ${G}=({V},{E}_{G})$
in which every hyperedge $e\in{E}_{H}$ is replaced by a clique of
$\mathrm{rank}(e)$ vertices in ${G}$.

To discuss the drawback of both reductions, we study the following two
$r$-uniform hypergraphs ${H}_{1}$ and ${H}_{2}$, in each of which the vertex
set is ${L}\cup{R}$ and the edge set is defined as follows:

  1. 1.

in ${H}_{1}$, every edge contains exactly one vertex from ${L}$, and $r-1$
vertices from ${R}$;

  2. 2.

in ${H}_{2}$, every edge contains exactly $r/2$ vertices from ${L}$ and $r/2$
vertices from ${R}$.

As such, we have that
${w}_{{H}_{1}}({L},{R})=\left\lvert{E}_{{H}_{1}}\right\rvert$, and
${w}_{{H}_{2}}({L},{R})=\left\lvert{E}_{{H}_{2}}\right\rvert$. See Figure 7.2
for illustration.

$\xrightarrow{}$$\begin{bmatrix}{\mathbf{B}}_{1}&{\mathbf{0}}&{\mathbf{0}}\\\
{\mathbf{0}}&{\mathbf{B}}_{2}&{\mathbf{0}}\\\
{\mathbf{0}}&{\mathbf{0}}&{\mathbf{B}}_{3}\end{bmatrix}$$\xrightarrow{}$Graph
${G}$Normalised Laplacian ${\mathbf{N}}$Spectral
Embedding$\xrightarrow{}$$\begin{bmatrix}{\mathbf{B}}_{1}&{\mathbf{C}}_{12}&{\mathbf{C}}_{13}\\\
{\mathbf{C}}_{12}^{\intercal}&{\mathbf{B}}_{2}&{\mathbf{C}}_{23}\\\
{\mathbf{C}}_{13}^{\intercal}&{\mathbf{C}}_{23}^{\intercal}&{\mathbf{B}}_{3}\end{bmatrix}$$\xrightarrow{}$Graph
${G}$Normalised Laplacian ${\mathbf{N}}$Spectral
Embedding$\rightarrow$$v_{1}$$v_{3}$$v_{5}$$v_{4}$$v_{2}$$\rightarrow$$x_{1}=v_{1}$$x_{2}=v_{4}$$x_{3}=v_{5}$${\bm{p}}^{(i)}$${\bm{p}}^{(j)}$$\frac{{\bm{p}}^{(i)}}{\left\|{\bm{p}}^{(i)}\right\|}$$\frac{{\bm{p}}^{(j)}}{\left\|{\bm{p}}^{(j)}\right\|}$${\bm{a}}_{i}$${\bm{a}}_{j}$$\frac{\left\|{\bm{a}}_{i}\right\|}{\left\|{\bm{a}}_{j}\right\|}{\bm{a}}_{j}$$a_{1}$$a_{2}$$a$$b$$c$$d$$\Longrightarrow$$b_{1}$$b_{2}$$c_{1}$$c_{2}$$d_{1}$$d_{2}$$\cdots$$a_{1}$$S$$b_{1}$$c_{1}$$d_{1}$$e_{1}$$f_{1}$$\cdots$$\cdots$$a_{2}$$b_{2}$$c_{2}$$d_{2}$$e_{2}$$f_{2}$$\cdots$$a_{1}$$a_{2}$$a$$b$$c$$d$$\Longrightarrow$$b_{1}$$b_{2}$$c_{1}$$c_{2}$$d_{1}$$d_{2}$$a_{1}$$b_{1}$$a_{2}$$b_{2}$ab$\Longrightarrow$$0.5$$0.5$$0.5$$0.5$$0.5$$0.5$$0.5$$0.5$$0.62$$0.38$$1.0$$0.38$$0.62$$1.0$$1.0$$0.5$$0.25$$0.25$$1.0$$1.0$$0.5$$0.5$$\begin{bmatrix}1\\\
0\\\ 0\\\ 0\\\ 0\\\
0\end{bmatrix}$$\rightarrow$$\rightarrow$$t=0$$t=1$$\begin{bmatrix}0.29\\\
-0.14\\\ -0.14\\\ 0.02\\\ 0.02\\\
0.02\end{bmatrix}$$\rightarrow$$\rightarrow$$t=3$$\begin{bmatrix}0.11\\\
-0.09\\\ -0.09\\\ 0.04\\\ 0.04\\\
0.04\end{bmatrix}$$\rightarrow$$\rightarrow$$t=4$$\begin{bmatrix}0.09\\\
-0.71\\\ -0.71\\\ 0.03\\\ 0.03\\\
0.03\end{bmatrix}$$\rightarrow$$\rightarrow$$t=23$$\begin{bmatrix}0.03\\\
-0.03\\\ -0.03\\\ 0.03\\\ -0.03\\\
-0.03\end{bmatrix}$$v_{1}$$v_{2}$$v_{3}$$v_{5}$$v_{4}$${\bm{f}}_{t}$${\bm{f}}_{t}$${\bm{f}}_{t}$${\bm{f}}_{t}$${\bm{f}}_{t}$$v_{6}$${L}$${R}$Hypergraph
${H}_{1}$${L}$${R}$Hypergraph
${H}_{2}$$\vdots$$\vdots$$\vdots$$\vdots$$\vdots$$\vdots$$\vdots$$\vdots$$\vdots$
Figure 7.2: Hypergraphs illustrating the downside of simple reductions

Now we analyse the size of the cut $({L},{R})$ in the reduced graphs.

  * •

Let ${w}_{{G}}({L},{R})$ be the cut value of $({L},{R})$ in the _random_ graph
${G}$ constructed from ${H}$ by the random reduction. We have for ${H}_{1}$
that $\mathbb{E}[{w}_{{G}}({L},{R})]=\Theta(1/r)\cdot{w}_{{H}_{1}}({L},{R})$
and for ${H}_{2}$ that
$\mathbb{E}[{w}_{{G}}({L},{R})]=\Theta(1)\cdot{w}_{{H}_{2}}({L},{R})$.

  * •

Similarly, by setting ${w}_{{G}}({L},{R})$ to be the cut value of $({L},{R})$
in the reduced graph ${G}$ constructed from ${H}$ by the clique reduction, we
have for ${H}_{1}$ that
${w}_{{G}}({L},{R})=\Theta(r)\cdot{w}_{{H}_{1}}({L},{R})$ and for ${H}_{2}$
that ${w}_{{G}}({L},{R})=\Theta(r^{2})\cdot{w}_{{H}_{2}}({L},{R})$.

Notice that these two approximation ratios differ by a factor of $r$ in the
two reductions. This suggests that reducing an $r$-uniform hypergraph ${H}$ to
a graph with some simple reduction would always introduce a factor of $r$ into
the approximation guarantee. This is one of the main reasons to develop
spectral theory for hypergraphs through heat diffusion processes [CLTZ18,
TMIY20, Yos19].

###  7.3 Diffusion Process and Algorithm

In this section, we introduce a new diffusion process in hypergraphs, and use
it to design a polynomial-time algorithm for finding bipartite components in
hypergraphs. We first study the heat diffusion process in graphs to give some
intuition. Then, we generalise it to hypergraphs and describe the new
algorithm. Finally, we sketch some of the analysis which proves that the
diffusion process is well defined. The full analysis is given in Sections 7.4
and 7.5.

####  7.3.1 Diffusion Process in Graphs

To discuss the intuition behind our designed diffusion process, let us look at
the case of graphs. Let ${G}=({V},{E},{w})$ be a graph, and we have for any
${\bm{x}}\in\mathbb{R}^{n}$ that

$\frac{{\bm{x}}^{\intercal}{\mathbf{Z}}_{G}{\bm{x}}}{{\bm{x}}^{\intercal}{\bm{x}}}=\frac{{\bm{x}}^{\intercal}({\mathbf{I}}+{\mathbf{D}}^{-\frac{1}{2}}_{G}{\mathbf{A}}_{G}{\mathbf{D}}^{-\frac{1}{2}}_{G}){\bm{x}}}{{\bm{x}}^{\intercal}{\bm{x}}}.$

By setting ${\bm{x}}={\mathbf{D}}^{\frac{1}{2}}_{G}{\bm{y}}$, we have that

$\displaystyle\frac{{\bm{x}}^{\intercal}{\mathbf{Z}}_{G}{\bm{x}}}{{\bm{x}}^{\intercal}{\bm{x}}}$
$\displaystyle=\frac{{\bm{y}}^{\intercal}{\mathbf{D}}^{\frac{1}{2}}_{G}{\mathbf{Z}}_{G}{\mathbf{D}}^{\frac{1}{2}}_{G}{\bm{y}}}{{\bm{y}}^{\intercal}{\mathbf{D}}_{G}{\bm{y}}}$
$\displaystyle=\frac{{\bm{y}}^{\intercal}({\mathbf{D}}_{G}+{\mathbf{A}}_{G}){\bm{y}}}{{\bm{y}}^{\intercal}{\mathbf{D}}_{G}{\bm{y}}}$
$\displaystyle=\frac{\sum_{\\{u,v\\}\in{E}_{G}}{w}(u,v)\cdot({\bm{y}}(u)+{\bm{y}}(v))^{2}}{\sum_{u\in{V}_{G}}{d}_{G}(u)\cdot{\bm{y}}(u)^{2}}.$
(7.1)

It is easy to see that $\lambda_{1}({\mathbf{Z}}_{G})=0$ if ${G}$ is
bipartite, and it is known that $\lambda_{1}({\mathbf{Z}}_{G})$ and its
corresponding eigenvector ${\bm{f}}_{1}({\mathbf{Z}}_{G})$ are closely related
to two densely connected components of ${G}$ [Tre12]. Moreover, similar to the
heat equation for graph Laplacian ${\mathbf{L}}_{G}$, suppose
${\mathbf{D}}_{G}{\bm{f}}_{t}\in\mathbb{R}^{n}$ is some measure on the
vertices of ${G}$, then a diffusion process defined by the differential
equation

$\frac{\mathrm{d}{\bm{f}}_{t}}{\mathrm{d}t}=-{\mathbf{D}}_{G}^{-1}{\mathbf{J}}_{G}{\bm{f}}_{t}\
$ (7.2)

converges to the eigenvector of ${\mathbf{D}}_{G}^{-1}{\mathbf{J}}_{G}$ with
minimum eigenvalue and can be employed to find two densely connected
components of the underlying graph.333For the reader familiar with the heat
diffusion process of graphs (e.g., [Chu07, KG14]), notice that the above-
defined process essentially employs the operator ${\mathbf{J}}_{G}$ to replace
the Laplacian ${\mathbf{L}}_{G}$ when defining the heat diffusion: through
${\mathbf{J}}_{G}$, the heat diffusion can be used to find two densely
connected components of ${G}$.

####  7.3.2 Hypergraph Diffusion and our Algorithm

Now we study whether one can construct a new hypergraph operator
${\mathbf{J}}_{H}$ that generalises the diffusion in graphs to hypergraphs.
First of all, we focus on a fixed time $t$ with measure vector
${\mathbf{D}}_{H}{\bm{f}}_{t}\in\mathbb{R}^{n}$. We follow (7.2) and define
the rate of change

$\frac{\mathrm{d}{\bm{f}}_{t}}{\mathrm{d}t}=-{\mathbf{D}}_{H}^{-1}{\mathbf{J}}_{H}{\bm{f}}_{t}$

so that the diffusion can proceed for an infinitesimal time step. Our
intuition is that the rate of change due to some edge $e\in{E}_{H}$ should
involve only the vertices in $e$ with the maximum or minimum value in the
normalised measure ${\bm{f}}_{t}$. To formalise this, for any edge
$e\in{E}_{H}$ we define

${S}_{{\bm{f}}}(e)\triangleq\\{v\in e:{\bm{f}}_{t}(v)=\max_{u\in
e}{\bm{f}}_{t}(u)\\}\mbox{\ \ \ and\ \ \ }{I}_{{\bm{f}}}(e)\triangleq\\{v\in
e:{\bm{f}}_{t}(v)=\min_{u\in e}{\bm{f}}_{t}(u)\\}.$

That is, for any edge $e$ and normalised measure ${\bm{f}}_{t}$,
${S}_{{\bm{f}}}(e)\subseteq e$ consists of the vertices $v$ adjacent to $e$
whose ${\bm{f}}_{t}(v)$ values are maximum, and ${I}_{{\bm{f}}}(e)\subseteq e$
consists of the vertices $v$ adjacent to $e$ whose ${\bm{f}}_{t}(v)$ values
are minimum. See Figure 7.3 for an example. Then, applying the
${\mathbf{J}}_{H}$ operator to a vector ${\bm{f}}_{t}$ should be equivalent to
applying the operator ${\mathbf{J}}_{G}$ for some graph ${G}$ which we
construct by splitting the weight of each hyperedge $e\in{E}_{H}$ between the
edges in ${S}_{{\bm{f}}}(e)\times{I}_{{\bm{f}}}(e)$. Similar to the case for
graphs and (7.3.1), for any
${\bm{x}}={\mathbf{D}}^{\frac{1}{2}}_{H}{\bm{f}}_{t}$ this gives us the
quadratic form

$\displaystyle\frac{{\bm{x}}^{\intercal}{\mathbf{D}}^{-\frac{1}{2}}_{H}{\mathbf{J}}_{H}{\mathbf{D}}^{-\frac{1}{2}}_{H}{\bm{x}}}{{\bm{x}}^{\intercal}{\bm{x}}}=\frac{{\bm{f}}_{t}^{\intercal}{\mathbf{J}}_{G}{\bm{f}}_{t}}{{\bm{f}}_{t}^{\intercal}{\mathbf{D}}_{H}{\bm{f}}_{t}}$
$\displaystyle=\frac{\sum_{\\{u,v\\}\in{E}_{G}}{w}_{G}(u,v)\cdot({\bm{f}}_{t}(u)+{\bm{f}}_{t}(v))^{2}}{\sum_{u\in{V}_{G}}{d}_{H}(u)\cdot{\bm{f}}_{t}(u)^{2}}$
$\displaystyle=\frac{\sum_{e\in{E}_{H}}{w}_{H}(e)(\max_{u\in
e}{\bm{f}}_{t}(u)+\min_{v\in
e}{\bm{f}}_{t}(v))^{2}}{\sum_{u\in{V}_{H}}{d}_{H}(u)\cdot{\bm{f}}_{t}(u)^{2}},$

where ${w}_{G}(u,v)$ is the weight of the edge $\\{u,v\\}$ in ${G}$, and
${w}_{H}(e)$ is the weight of the edge $e$ in ${H}$. We see later in this
chapter that ${\mathbf{J}}_{H}$ has an eigenvalue of $0$ if the hypergraph is
$2$-colourable444Hypergraph ${H}$ is $2$-colourable if there are disjoint sets
${L},{R}\subset{V}_{H}$ such that every edge intersects ${L}$ and ${R}$., and
the spectrum of ${\mathbf{J}}_{H}$ is closely related to the hypergraph
bipartiteness.

$\xrightarrow{}$$\begin{bmatrix}{\mathbf{B}}_{1}&{\mathbf{0}}&{\mathbf{0}}\\\
{\mathbf{0}}&{\mathbf{B}}_{2}&{\mathbf{0}}\\\
{\mathbf{0}}&{\mathbf{0}}&{\mathbf{B}}_{3}\end{bmatrix}$$\xrightarrow{}$Graph
${G}$Normalised Laplacian ${\mathbf{N}}$Spectral
Embedding$\xrightarrow{}$$\begin{bmatrix}{\mathbf{B}}_{1}&{\mathbf{C}}_{12}&{\mathbf{C}}_{13}\\\
{\mathbf{C}}_{12}^{\intercal}&{\mathbf{B}}_{2}&{\mathbf{C}}_{23}\\\
{\mathbf{C}}_{13}^{\intercal}&{\mathbf{C}}_{23}^{\intercal}&{\mathbf{B}}_{3}\end{bmatrix}$$\xrightarrow{}$Graph
${G}$Normalised Laplacian ${\mathbf{N}}$Spectral
Embedding$\rightarrow$$v_{1}$$v_{3}$$v_{5}$$v_{4}$$v_{2}$$\rightarrow$$x_{1}=v_{1}$$x_{2}=v_{4}$$x_{3}=v_{5}$${\bm{p}}^{(i)}$${\bm{p}}^{(j)}$$\frac{{\bm{p}}^{(i)}}{\left\|{\bm{p}}^{(i)}\right\|}$$\frac{{\bm{p}}^{(j)}}{\left\|{\bm{p}}^{(j)}\right\|}$${\bm{a}}_{i}$${\bm{a}}_{j}$$\frac{\left\|{\bm{a}}_{i}\right\|}{\left\|{\bm{a}}_{j}\right\|}{\bm{a}}_{j}$$a_{1}$$a_{2}$$a$$b$$c$$d$$\Longrightarrow$$b_{1}$$b_{2}$$c_{1}$$c_{2}$$d_{1}$$d_{2}$$\cdots$$a_{1}$$S$$b_{1}$$c_{1}$$d_{1}$$e_{1}$$f_{1}$$\cdots$$\cdots$$a_{2}$$b_{2}$$c_{2}$$d_{2}$$e_{2}$$f_{2}$$\cdots$$a_{1}$$a_{2}$$a$$b$$c$$d$$\Longrightarrow$$b_{1}$$b_{2}$$c_{1}$$c_{2}$$d_{1}$$d_{2}$$a_{1}$$b_{1}$$a_{2}$$b_{2}$ab$\Longrightarrow$$0.5$$0.5$$0.5$$0.5$$0.5$$0.5$$0.5$$0.5$$0.62$$0.38$$1.0$$0.38$$0.62$$1.0$$1.0$$0.5$$0.25$$0.25$$1.0$$1.0$$0.5$$0.5$$\begin{bmatrix}1\\\
0\\\ 0\\\ 0\\\ 0\\\
0\end{bmatrix}$$\rightarrow$$\rightarrow$$t=0$$t=1$$\begin{bmatrix}0.29\\\
-0.14\\\ -0.14\\\ 0.02\\\ 0.02\\\
0.02\end{bmatrix}$$\rightarrow$$\rightarrow$$t=3$$\begin{bmatrix}0.11\\\
-0.09\\\ -0.09\\\ 0.04\\\ 0.04\\\
0.04\end{bmatrix}$$\rightarrow$$\rightarrow$$t=4$$\begin{bmatrix}0.09\\\
-0.71\\\ -0.71\\\ 0.03\\\ 0.03\\\
0.03\end{bmatrix}$$\rightarrow$$\rightarrow$$t=23$$\begin{bmatrix}0.03\\\
-0.03\\\ -0.03\\\ 0.03\\\ -0.03\\\
-0.03\end{bmatrix}$$v_{1}$$v_{2}$$v_{3}$$v_{5}$$v_{4}$${\bm{f}}_{t}$${\bm{f}}_{t}$${\bm{f}}_{t}$${\bm{f}}_{t}$${\bm{f}}_{t}$$v_{6}$${L}$${R}$Hypergraph
${H}_{1}$${L}$${R}$Hypergraph
${H}_{2}$$\vdots$$\vdots$$\vdots$$\vdots$$\vdots$$\vdots$$\vdots$$\vdots$$\vdots$$-2$$-2$$0$$1$$3$$1$Hyperedge
$e$${I}_{{\bm{f}}}(e)$${S}_{{\bm{f}}}(e)$ Figure 7.3: Illustration of
${S}_{{\bm{f}}}(e)$ and ${I}_{{\bm{f}}}(e)$. Vertices are labelled with their
value in ${\bm{f}}_{t}$.

For this reason, we would expect that the diffusion process based on the
operator ${\mathbf{J}}_{H}$ can be used to find sets with small hypergraph
bipartiteness. However, one needs to be very cautious here as, by the nature
of the diffusion process, the values ${\bm{f}}_{t}(v)$ of all the vertices $v$
change over time and, as a result, the sets ${S}_{{\bm{f}}}(e)$ and
${I}_{{\bm{f}}}(e)$ that consist of the vertices with the maximum and minimum
${\bm{f}}_{t}$-value might change after an _infinitesimal_ time step; this
prevents the process from continuing. We discuss this issue in detail through
the so-called diffusion continuity condition in Section 7.3.3. In essence, the
diffusion continuity condition ensures that one can always construct a graph
${G}$ by allocating the weight of each hyperedge $e$ to the edges in
${S}_{{\bm{f}}}(e)\times{I}_{{\bm{f}}}(e)$ such that the sets
${S}_{{\bm{f}}}(e)$ and ${I}_{{\bm{f}}}(e)$ don’t change in infinitesimal time
although ${\bm{f}}_{t}$ changes according to
$(\mathrm{d}{\bm{f}}_{t})/(\mathrm{d}t)=-{\mathbf{D}}_{H}^{-1}{\mathbf{J}}_{G}{\bm{f}}_{t}$.
We also develop an efficient procedure in Section 7.3.3 to compute the weights
of edges in ${S}_{{\bm{f}}}(e)\times{I}_{{\bm{f}}}(e)$. All of these guarantee
that (i) every graph that corresponds to the hypergraph diffusion process at
any time step can be efficiently constructed; (ii) with this sequence of
constructed graphs, the diffusion process defined by ${\mathbf{J}}_{H}$ is
able to continue until the heat distribution converges. With this, we can
summarise the main idea of the new algorithm as follows:

  * •

First of all, we introduce some arbitrary ${\bm{f}}_{0}\in\mathbb{R}^{n}$ as
the initial diffusion vector, and a step size parameter $\epsilon>0$ to
discretise the diffusion process. At each step, the algorithm constructs the
graph ${G}$ guaranteed by the diffusion continuity condition, and updates
${\bm{f}}_{t}\in\mathbb{R}^{n}$ according to the rate of change
$(\mathrm{d}{\bm{f}}_{t})/(\mathrm{d}t)=-{\mathbf{D}}_{H}^{-1}{\mathbf{J}}_{G}{\bm{f}}_{t}$.
The algorithm terminates when ${\bm{f}}_{t}$ has converged, i.e., the ratio
between the current Rayleigh quotient
$({\bm{f}}_{t}^{\intercal}{\mathbf{J}}_{G}{\bm{f}}_{t})/({\bm{f}}_{t}^{\intercal}{\mathbf{D}}_{H}{\bm{f}}_{t})$
and the one in the previous time step is bounded by some predefined constant.

  * •

Secondly, similar to many previous spectral graph clustering algorithms (e.g.
[ACL06, TMIY20, Tre12]), the algorithm constructs the sweep sets defined by
${\bm{f}}_{t}$ and returns the two sets with minimum ${\beta}_{H}$-value among
all the constructed sweep sets. Specifically, for every $i\in[n]$, the
algorithm constructs
${L}_{j}=\\{v_{i}:\left\lvert{\bm{f}}_{t}(v_{i})\right\rvert\geq\left\lvert{\bm{f}}_{t}(v_{j})\right\rvert\land{\bm{f}}_{t}(v_{i})<0\\}$
and
${R}_{j}=\\{v_{i}:\left\lvert{\bm{f}}_{t}(v_{i})\right\rvert\geq\left\lvert{\bm{f}}_{t}(v_{j})\right\rvert\land{\bm{f}}_{t}(v_{i})\geq
0\\}$. Then, among the $n$ pairs $({L}_{j},{R}_{j})$, the algorithm returns
the one with the minimum ${\beta}_{H}$-value.

See Algorithm 1 for the formal description, and its performance is summarised
in Theorem 7.1. We prove the theorem in Section 7.5.

######  Theorem 7.1.

Given a hypergraph ${H}=({V}_{H},{E}_{H},{w})$ and parameter $\epsilon>0$, the
following holds:

  1. 1.

There is an algorithm that finds an eigen-pair ($\lambda,{\bm{f}}$) of the
operator ${\mathbf{J}}_{H}$ such that
$\lambda\leq\lambda_{1}({\mathbf{J}}_{G})$, where ${G}$ is the clique
reduction of ${H}$ and the inequality is strict if
$\min_{e\in{E}_{H}}\mathrm{rank}(e)>2$. The algorithm has running time
$\mathrm{poly}(\left\lvert{V}_{H}\right\rvert,\left\lvert{E}_{H}\right\rvert,1/\epsilon)$.

  2. 2.

Given an eigen-pair $(\lambda,{\bm{f}})$ of the operator ${\mathbf{J}}_{H}$,
there is an algorithm that constructs the two-sided sweep sets defined on
${\bm{f}}$, and finds sets ${L}$ and ${R}$ such that
${\beta}_{H}({L},{R})\leq\sqrt{2\lambda}$. The algorithm has running time
$\mathrm{poly}(\left\lvert{V}_{H}\right\rvert,\left\lvert{E}_{H}\right\rvert)$.

Input : Hypergraph ${H}$, starting vector ${\bm{f}}_{0}\in\mathbb{R}^{n}$,
step size $\epsilon>0$

Output : Sets ${L}$ and ${R}$

1 $t:=0$

2 while  _${\bm{f}}_{t}$ has not converged_ do

3 Use ${\bm{f}}_{t}$ to construct graph ${G}$ satisfying the diffusion
continuity condition

4
${\bm{f}}_{t+\epsilon}:={\bm{f}}_{t}-\epsilon{\mathbf{D}}_{H}^{-1}{\mathbf{J}}_{G}{\bm{f}}_{t}$

5 $t:=t+\epsilon$

6 end while

7Set $j:=\operatorname*{arg\,min}_{1\leq i\leq n}{\beta}_{H}({L}_{i},{R}_{i})$

return $({L}_{j},{R}_{j})$

Algorithm 1 FindBipartiteComponents$(H,{\bm{f}}_{0},\epsilon)$

####  7.3.3 Dealing with the Diffusion Continuity Condition

It remains for us to discuss the diffusion continuity condition, which
guarantees that ${S}_{{\bm{f}}}(e)$ and ${I}_{{\bm{f}}}(e)$ don’t change in
infinitesimal time and the diffusion process eventually converges to some
stable distribution. Formally, let ${\bm{f}}_{t}$ be the normalised measure on
the vertices of ${H}$, and

${\bm{r}}\triangleq\frac{\mathrm{d}{\bm{f}}_{t}}{\mathrm{d}t}=-{\mathbf{D}}_{H}^{-1}{\mathbf{J}}_{H}{\bm{f}}_{t}$

be the derivative of ${\bm{f}}_{t}$, which describes the rate of change for
every vertex at the current time $t$. We write ${\bm{r}}(v)$ for any
$v\in{V}_{H}$ as ${\bm{r}}(v)=\sum_{e\in{E}_{H}}{\bm{r}}_{e}(v)$, where
${\bm{r}}_{e}(v)$ is the contribution of edge $e$ towards the rate of change
of ${\bm{f}}_{t}(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 ${\bm{r}}$.

First of all, as we mentioned in Section 7.3.2, we expect that only the
vertices in ${S}_{{\bm{f}}}(e)\cup{I}_{{\bm{f}}}(e)$ participate in the
diffusion process, i.e., ${\bm{r}}_{e}(u)=0$ unless
$u\in{S}_{{\bm{f}}}(e)\cup{I}_{{\bm{f}}}(e)$. Moreover, any vertex $u$
participating in the diffusion process must satisfy the following:

  * •

Rule (0a): if $\left\lvert{\bm{r}}_{e}(u)\right\rvert>0$ and
$u\in{S}_{{\bm{f}}}(e)$, then
${\bm{r}}(u)=\max_{v\in{S}_{{\bm{f}}}(e)}\\{{\bm{r}}(v)\\}$.

  * •

Rule (0b): if $\left\lvert{\bm{r}}_{e}(u)\right\rvert>0$ and
$u\in{I}_{{\bm{f}}}(e)$, then
${\bm{r}}(u)=\min_{v\in{I}_{{\bm{f}}}(e)}\\{{\bm{r}}(v)\\}$.

To explain Rule (0), notice that for an infinitesimal time, ${\bm{f}}_{t}(u)$
is increased according to
$\left(\mathrm{d}{\bm{f}}_{t}/\mathrm{d}t\right)(u)={\bm{r}}(u)$. Hence, by
Rule (0) we know that, if $u\in{S}_{{\bm{f}}}(e)$ (resp.
$u\in{I}_{{\bm{f}}}(e)$) participates in the diffusion process in edge $e$,
then in an infinitesimal time ${\bm{f}}(u)$ remains the maximum (resp.
minimum) among the vertices in $e$. Such a rule is necessary to ensure that
the vertices involved in the diffusion in edge $e$ do not change in
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
$e$ is equal to $-{w}(e)\cdot{\Delta}_{{\bm{f}}}(e)$:

  * •

Rule (1):
$\sum_{v\in{S}_{{\bm{f}}}(e)}{d}(v){\bm{r}}_{e}(v)=\sum_{v\in{I}_{{\bm{f}}}(e)}{d}(v){\bm{r}}_{e}(v)=-{w}(e)\cdot{\Delta}_{{\bm{f}}}(e)$
for all $e\in{E}_{H}$.

This rule is a generalisation from the operator ${\mathbf{J}}_{G}$ in graphs.
In particular, since

${\mathbf{D}}_{G}^{-1}{\mathbf{J}}_{G}{\bm{f}}_{t}(u)=\sum_{\\{u,v\\}\in{E}_{G}}{w}_{G}(u,v)({\bm{f}}_{t}(u)+{\bm{f}}_{t}(v))/{d}_{G}(u),$

the rate of change of ${\bm{f}}_{t}(u)$ due to the edge $\\{u,v\\}\in{E}_{G}$
is $-{w}_{G}(u,v)({\bm{f}}_{t}(u)+{\bm{f}}_{t}(v))/{d}_{G}(u)$. Rule (1)
states that in the hypergraph case the rate of change of the vertices in
${S}_{{\bm{f}}}(e)$ and ${I}_{{\bm{f}}}(e)$ together behave like the rate of
change of $u$ and $v$ in the graph case.

One might have expected that Rules (0) and (1) together would define a unique
process. Unfortunately, this isn’t the case. For example, let us define an
unweighted hypergraph ${H}=({V}_{H},{E}_{H})$, where ${V}_{H}=\\{u,v,w\\}$ and
${E}_{H}=\\{\\{u,v,w\\}\\}$. By setting the measure to be
${\bm{f}}_{t}=(1,1,-2)^{\intercal}$ and $e=\\{u,v,w\\}$, we have
${\Delta}_{{\bm{f}}_{t}}(e)=-1$, and ${\bm{r}}(u)+{\bm{r}}(v)={\bm{r}}(w)=1$
by Rule (1). In such a scenario, either $\\{u,w\\}$ or $\\{v,w\\}$ can
participate in the diffusion and satisfy Rule (0), which makes the process not
uniquely defined. To overcome this, we introduce the following stronger rule
to replace Rule (0):

  * •

Rule (2a): Assume that $\left\lvert{\bm{r}}_{e}(u)\right\rvert>0$ and
$u\in{S}_{{\bm{f}}}(e)$:

    * –

if ${\Delta}_{{\bm{f}}}(e)>0$, then
${\bm{r}}(u)=\max_{v\in{S}_{{\bm{f}}}(e))}\\{{\bm{r}}(v)\\}$;

    * –

if ${\Delta}_{{\bm{f}}}(e)<0$, then ${\bm{r}}(u)={\bm{r}}(v)$ for all
$v\in{S}_{{\bm{f}}}(e)$.

  * •

Rule (2b): Assume that $\left\lvert{\bm{r}}_{e}(u)\right\rvert>0$ and
$u\in{I}_{{\bm{f}}}(e)$:

    * –

if ${\Delta}_{{\bm{f}}}(e)<0$, then
${\bm{r}}(u)=\min_{v\in{I}_{{\bm{f}}}(e))}\\{{\bm{r}}(v)\\}$;

    * –

if ${\Delta}_{{\bm{f}}}(e)>0$, then ${\bm{r}}(u)={\bm{r}}(v)$ for all
$v\in{I}_{{\bm{f}}}(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 $e$ is negative
(resp. positive), then all the vertices $u\in{S}_{{\bm{f}}}(e)$ (resp.
$u\in{I}_{{\bm{f}}}(e)$) have the same value of ${\bm{r}}(u)$. Lemma 7.1 shows
that there is a unique ${\bm{r}}\in\mathbb{R}^{n}$ that satisfies Rules (1)
and (2), and ${\bm{r}}$ can be computed in polynomial time. Therefore, our two
rules uniquely define a diffusion process, and we can use the computed
${\bm{r}}$ to simulate the continuous diffusion process with a discretised
version.555Note that the graph ${G}$ used for the diffusion at time $t$ can be
easily computed from the $\\{{\bm{r}}_{e}(v)\\}$ values, although in practice
this is not actually needed since the ${\bm{r}}(u)$ values can be used to
update the diffusion directly.

######  Lemma 7.1 (Existence of diffusion process).

For any given ${\bm{f}}_{t}\in\mathbb{R}^{n}$, there is a unique
${\bm{r}}=\mathrm{d}{\bm{f}}_{t}/\mathrm{d}t$ and associated
$\\{{\bm{r}}_{e}(v)\\}_{e\in{E},v\in{V}}$ that satisfy Rule (1) and (2), and
${\bm{r}}$ can be computed in polynomial time by linear programming.

It is worth emphasising that our defined rules and the proof of Lemma 7.1 are
more involved than those used in [CLTZ18] to define the hypergraph Laplacian
operator. In particular, in contrast to [CLTZ18], in our case the discrepancy
${\Delta}_{{\bm{f}}}(e)$ within a hyperedge $e$ can be either positive or
negative. This results in the four different cases in Rule (2) which have to
be carefully considered throughout the proof of Lemma 7.1.

###  7.4 Existence of Diffusion Process

In this section we prove Lemma 7.1 which shows that the diffusion process
introduced in Section 7.3 is well-defined. The proof consists of two parts.
First, we construct a linear program which can compute the rate of change
${\bm{r}}$ satisfying the rules of the diffusion process. Then we analyse the
new linear program which establishes Lemma 7.1.

####  7.4.1 Computing ${\bm{r}}$ by a Linear Program

Now we present an algorithm that computes the vector
${\bm{r}}=\mathrm{d}{\bm{f}}_{t}/\mathrm{d}t$ for any
${\bm{f}}_{t}\in\mathbb{R}^{n}$. Without loss of generality, let us fix
${\bm{f}}_{t}\in\mathbb{R}^{n}$, and define a set of equivalence classes
$\mathcal{U}$ on ${V}$ such that vertices $u,v\in{V}_{H}$ are in the same
equivalence class if ${\bm{f}}_{t}(u)={\bm{f}}_{t}(v)$. Next we study every
equivalence class ${U}\in\mathcal{U}$ in turn, and set the ${\bm{r}}$-value of
the vertices in ${U}$ recursively. In each iteration, we fix the
${\bm{r}}$-value of some subset ${P}\subseteq{U}$ and recurse on
${U}\setminus{P}$. As we prove later, it’s important to highlight that the
recursive procedure ensures that the ${\bm{r}}$-values assigned to the
vertices always _decrease_ after each recursion. Notice that it suffices to
consider the edges $e$ in which
$({S}_{{\bm{f}}_{t}}(e)\cup{I}_{{\bm{f}}_{t}}(e))\cap{U}\neq\emptyset$, since
the diffusion process induced by other edges $e$ has no impact on
${\bm{r}}(u)$ for any $u\in{U}$. Hence, we introduce the sets

$\displaystyle\mathcal{S}_{{U}}$
$\displaystyle\triangleq\\{e\in{E}_{U}:{S}_{{\bm{f}}_{t}}(e)\cap{U}\neq\emptyset\\}$
$\displaystyle\mathcal{I}_{{U}}$
$\displaystyle\triangleq\\{e\in{E}_{U}:{I}_{{\bm{f}}_{t}}(e)\cap{U}\neq\emptyset\\},$

where ${E}_{U}$ consists of the edges adjacent to some vertex in ${U}$. To
work with the four cases listed in Rule (2a) and (2b), we define

$\displaystyle\mathcal{S}_{{U}}^{+}$
$\displaystyle\triangleq\\{e\in\mathcal{S}_{U}:{\Delta}_{{\bm{f}}_{t}}(e)<0\\},$
$\displaystyle\mathcal{S}_{{U}}^{-}$
$\displaystyle\triangleq\\{e\in\mathcal{S}_{U}:{\Delta}_{{\bm{f}}_{t}}(e)>0\\},$
$\displaystyle\mathcal{I}_{U}^{+}$
$\displaystyle\triangleq\\{e\in\mathcal{I}_{U}:{\Delta}_{{\bm{f}}_{t}}(e)<0\\},$
$\displaystyle\mathcal{I}_{U}^{-}$
$\displaystyle\triangleq\\{e\in\mathcal{I}_{U}:{\Delta}_{{\bm{f}}_{t}}(e)>0\\}.$

Our objective is to find some ${P}\subseteq{U}$ and assign the same
${\bm{r}}$-value to every vertex in ${P}$. To this end, for any
${P}\subseteq{U}$ we define

$\displaystyle\mathcal{S}_{{U},{P}}^{+}$
$\displaystyle\triangleq\left\\{e\in\mathcal{S}_{{U}}^{+}:{S}_{{\bm{f}}_{t}}(e)\subseteq{P}\right\\},$
$\displaystyle\mathcal{I}_{{U},{P}}^{+}$
$\displaystyle\triangleq\left\\{e\in\mathcal{I}_{{U}}^{+}:{I}_{{\bm{f}}_{t}}(e)\subseteq{P}\right\\},$
$\displaystyle\mathcal{S}_{{U},{P}}^{-}$
$\displaystyle\triangleq\left\\{e\in\mathcal{S}_{{U}}^{-}:{S}_{{\bm{f}}_{t}}(e)\cap{P}\neq\emptyset\right\\},$
$\displaystyle\mathcal{I}_{{U},{P}}^{-}$
$\displaystyle\triangleq\\{e\in\mathcal{I}_{{U}}^{-}:{I}_{{\bm{f}}_{t}}(e)\subseteq{P}\\}.$

These are the edges contributing to the rate of change of the vertices in
${P}$. Before continuing the analysis, we briefly explain the intuition behind
these four definitions:

  1. 1.

For $\mathcal{S}_{{U},{P}}^{+}$, since every $e\in\mathcal{S}_{{U}}^{+}$
satisfies ${\Delta}_{{\bm{f}}_{t}}(e)<0$ and all the vertices in
${S}_{{\bm{f}}_{t}}(e)$ must have the same value by Rule (2a), all such
$e\in\mathcal{S}_{{U},{P}}^{+}$ must satisfy that
${S}_{{\bm{f}}_{t}}(e)\subseteq{P}$, since the unassigned vertices would
receive lower values of ${\bm{r}}$ in the remaining part of the recursion
process.

  2. 2.

For $\mathcal{I}_{{U},{P}}^{+}$, since every $e\in\mathcal{I}_{{U}}^{+}$
satisfies ${\Delta}_{{\bm{f}}_{t}}(e)<0$, Rule (2b) implies that if
${\bm{r}}_{e}(u)\neq 0$ then ${\bm{r}}(u)\leq{\bm{r}}(v)$ for all
$v\in{I}_{{\bm{f}}_{t}}(e)$. Since unassigned vertices would receive lower
values of ${\bm{r}}$ later, such $e\in\mathcal{I}_{{U},{P}}^{+}$ must satisfy
${I}_{{\bm{f}}_{t}}(e)\subseteq{P}$.

  3. 3.

For $\mathcal{S}_{{U},{P}}^{-}$, since every $e\in\mathcal{S}_{{U}}^{-}$
satisfies ${\Delta}_{{\bm{f}}_{t}}(e)>0$, by Rule (2a) it suffices that some
vertex in ${S}_{{\bm{f}}_{t}}(e)$ receives the assignment in the current
iteration, i.e., every such $e$ must satisfy
${S}_{{\bm{f}}_{t}}(e)\cap{P}\neq\emptyset$.

  4. 4.

The case for $\mathcal{I}_{{U},{P}}^{-}$ is the same as
$\mathcal{S}_{{U},{P}}^{+}$.

As we expect all the vertices $u\in{S}_{{\bm{f}}_{t}}(e)$ to have the same
${\bm{r}}$-value for every $e$ as long as ${\Delta}_{{\bm{f}}_{t}}(e)<0$ by
Rule (2a) and at the moment we are only considering the assignment of the
vertices in ${P}$, we expect that

$\left\\{e\in\mathcal{S}_{{U}}^{+}\setminus\mathcal{S}_{{U},{P}}^{+}:{S}_{{\bm{f}}_{t}}(e)\cap{P}\neq\emptyset\right\\}=\emptyset,$
(7.3)

and this ensures that, as long as ${\Delta}_{{\bm{f}}_{t}}(e)<0$ and some
$u\in{S}_{{\bm{f}}_{t}}(e)$ gets its ${\bm{r}}$-value, all the other vertices
in ${S}_{{\bm{f}}_{t}}(e)$ would be assigned the same value as $u$. Similarly,
by Rule (2b), we expect all the vertices $u\in{I}_{{\bm{f}}_{t}}(e)$ to have
the same ${\bm{r}}$-value for every $e$ as long as
${\Delta}_{{\bm{f}}_{t}}(e)>0$, and so we expect that

$\left\\{e\in\mathcal{I}_{{U}}^{-}\setminus\mathcal{I}_{{U},{P}}^{-}:{I}_{{\bm{f}}_{t}}(e)\cap{P}\neq\emptyset\right\\}=\emptyset.$
(7.4)

We set the ${\bm{r}}$-value by dividing the total discrepancy of the edges in
$\mathcal{I}_{{U},{P}}^{+}\cup\mathcal{S}_{{U},{P}}^{+}\cup\mathcal{I}_{{U},{P}}^{-}\cup\mathcal{S}_{{U},{P}}^{-}$
between the vertices in ${P}$. As such, we would like to find some
${P}\subseteq{U}$ that maximises the value of

$\frac{1}{\mathrm{vol}({P})}\cdot\left(\sum_{e\in\mathcal{S}_{{U},{P}}^{+}\cup\mathcal{I}_{{U},{P}}^{+}}c_{{\bm{f}}_{t}}(e)-\sum_{e\in\mathcal{S}_{{U},{P}}^{-}\cup\mathcal{I}_{{U},{P}}^{-}}c_{{\bm{f}}_{t}}(e)\right).$

Taking all of these requirements into account, we show that, for any
equivalence class ${U}$, we can find the desired set ${P}$ by solving the
following linear program:

maximise $\displaystyle
c({\bm{x}})=\sum_{e\in\mathcal{S}_{{U}}^{+}\cup\mathcal{I}_{{U}}^{+}}c_{{\bm{f}}_{t}}(e)\cdot
x_{e}-\sum_{e\in\mathcal{S}_{{U}}^{-}\cup\mathcal{I}_{{U}}^{-}}c_{{\bm{f}}_{t}}(e)\cdot
x_{e}$ (7.5) subject to $\displaystyle\sum_{v\in{U}}\begin{aligned}
{d}(v)y_{v}&=1\\\\[12.91663pt] x_{e}&=y_{u}&\quad
e&\in\mathcal{S}_{{U}}^{+},u\in{S}_{{\bm{f}}_{t}}(e),\\\ x_{e}&\leq
y_{u}&\quad e&\in\mathcal{I}_{{U}}^{+},u\in{I}_{{\bm{f}}_{t}}(e),\\\
x_{e}&\geq y_{u}&\quad
e&\in\mathcal{S}_{{U}}^{-},u\in{S}_{{\bm{f}}_{t}}(e),\\\ x_{e}&=y_{u}&\quad
e&\in\mathcal{I}_{{U}}^{-},u\in{I}_{{\bm{f}}_{t}}(e),\\\ x_{e},y_{v}&\geq
0&&\forall v\in{U},e\in{E}_{{U}}.\end{aligned}$

Since the linear program only gives partial assignment to the vertices’
${\bm{r}}$-values, we solve the same linear program on the reduced instance
given by the set ${U}\setminus{P}$. The formal description of our algorithm is
given in Algorithm 2.

Input : vertex set ${U}\subseteq{V}$, and edge set ${E}_{{U}}$

Output : Values of $\\{{\bm{r}}(v)\\}_{v\in{U}}$

1 Construct sets $\mathcal{S}_{{U}}^{+}$, $\mathcal{S}_{{U}}^{-}$,
$\mathcal{I}_{{U}}^{+}$, and $\mathcal{I}_{{U}}^{-}$

2 Solve the linear program defined by (7.5), and define
${P}:=\\{v\in{U}:y(v)>0\\}$

3 Construct sets $\mathcal{S}_{{U},{P}}^{+}$, $\mathcal{S}_{{U},{P}}^{-}$,
$\mathcal{I}_{{U},{P}}^{+}$, and $\mathcal{I}_{{U},{P}}^{-}$

4 Set
$C({P}):=c_{{\bm{f}}_{t}}\left(\mathcal{S}_{{U},{P}}^{+}\right)+c_{{\bm{f}}_{t}}\left(\mathcal{I}_{{U},{P}}^{+}\right)-c_{{\bm{f}}_{t}}\left(\mathcal{S}_{{U},{P}}^{-}\right)-c_{{\bm{f}}_{t}}\left(\mathcal{I}_{{U},{P}}^{-}\right)$

5 Set $\delta({P}):=C({P})/\mathrm{vol}({P})$

6 Set ${\bm{r}}(u):=\delta({P})$ for every $u\in{P}$

ComputeChangeRate$\left({U}\setminus{P},{E}_{U}\setminus\left(\mathcal{S}_{{U},{P}}^{+}\cup\mathcal{I}_{{U},{P}}^{+}\cup\mathcal{S}_{{U},{P}}^{-}\cup\mathcal{I}_{{U},{P}}^{-}\right)\right)$

Algorithm 2 ComputeChangeRate$({U},{E}_{U})$

####  7.4.2 Analysis of the Linear Program

Now we analyse Algorithm 2, and the properties of the ${\bm{r}}$-values it
computes. Specifically, we show the following facts which together allow us to
establish Lemma 7.1.

  1. 1.

Algorithm 2 always produces a unique vector ${\bm{r}}$, no matter which
optimal result is returned when computing the linear program (7.5).

  2. 2.

If there is any vector ${\bm{r}}$ which is consistent with Rules (1) and (2),
then it must be equal to the output of Algorithm 2.

  3. 3.

The vector ${\bm{r}}$ produced by Algorithm 2 is consistent with Rules (1) and
(2).

##### Output of Algorithm 2 is Unique

First of all, for any ${P}\subseteq{U}$ that satisfies (7.3) and (7.4), we
define vectors ${\bm{x}}_{P}$ and ${\bm{y}}_{P}$ by

${\bm{x}}_{P}(e)=\left\\{\begin{array}[]{ll}\frac{1}{\mathrm{vol}({P})}&\mbox{if
}e\in\mathcal{S}_{{U},{P}}^{+}\cup\mathcal{I}_{{U},{P}}^{+}\cup\mathcal{S}_{{U},{P}}^{-}\cup\mathcal{I}_{{U},{P}}^{-}\\\
0&\mbox{otherwise}\end{array}\right.,$
${\bm{y}}_{P}(v)=\left\\{\begin{array}[]{ll}\frac{1}{\mathrm{vol}({P})}&\mbox{if
}v\in{P}\\\ 0&\mbox{otherwise}\end{array}\right.,$

and $z_{P}=\left({\bm{x}}_{P},{\bm{y}}_{P}\right)$. It is easy to verify that
$\left({\bm{x}}_{P},{\bm{y}}_{P}\right)$ is a feasible solution to (7.5) with
the objective value $c\left({\bm{x}}_{P}\right)=\delta({P})$. We prove that
ComputeChangeRate (Algorithm 2) computes a unique vector ${\bm{r}}$ regardless
of how ties are broken when computing the subsets ${P}$.

For any feasible solution $z=({\bm{x}},{\bm{y}})$, we say that a non-empty set
${Q}$ is a _level set_ of $z$ if there is some $t>0$ such that
${Q}=\left\\{u\in{U}:y_{u}\geq t\right\\}$. We first show that any non-empty
level set of an optimal solution $z$ also corresponds to an optimal solution.

######  Lemma 7.2.

Suppose that $z^{\star}=\left({\bm{x}}^{\star},{\bm{y}}^{\star}\right)$ is an
optimal solution of the linear program (7.5). Then, any non-empty level set
${Q}$ of $z^{\star}$ corresponds to an optimal solution of (7.5) as well.

###### Proof.

Let ${P}=\\{v\in{V}_{H}:{\bm{y}}^{\star}(v)>0\\}$. The proof is by case
distinction. We first look at the case in which all the vertices in ${P}$ have
the same value of ${\bm{y}}^{\star}(v)$ for any $v\in{P}$. Then, it must be
that $z^{\star}=z_{P}$ and every non-empty level set ${Q}$ of $z^{\star}$ is
equal to ${P}$; as such, the statement holds trivially.

Secondly, we assume that the vertices in ${P}$ have at least two different
${\bm{y}}^{\star}$-values. We define
$\alpha=\min\left\\{y_{v}^{\star}:v\in{P}\right\\}$, and have

$\alpha\cdot\mathrm{vol}({P})<\sum_{u\in{U}}{d}(u)\cdot y_{u}^{\star}=1.$

We introduce $\widehat{z}=\left(\widehat{{\bm{x}}},\widehat{{\bm{y}}}\right)$
defined by

$\displaystyle\widehat{{\bm{x}}}(e)$
$\displaystyle=\left\\{\begin{array}[]{ll}\frac{{\bm{x}}^{\star}(e)-\alpha}{1-\alpha\mathrm{vol}({P})}&\mbox{if
}{\bm{x}}^{\star}(e)\geq 0\\\ 0&\mbox{otherwise}\end{array}\right.,$

and

$\displaystyle\widehat{{\bm{y}}}(v)$
$\displaystyle=\left\\{\begin{array}[]{ll}\frac{{\bm{y}}^{\star}(v)-\alpha}{1-\alpha\mathrm{vol}({P})}&\mbox{if
}v\in{P}\\\ 0&\mbox{otherwise}\end{array}\right..$

This implies that

${\bm{x}}^{\star}=\left(1-\alpha\mathrm{vol}({P})\right)\widehat{{\bm{x}}}+\alpha\cdot{\bm{1}}_{P}=\left(1-\alpha\mathrm{vol}({P})\right)\widehat{{\bm{x}}}+\alpha\cdot\mathrm{vol}({P})\cdot{\bm{x}}_{P},$
(7.6)

and

${\bm{y}}^{\star}=\left(1-\alpha\mathrm{vol}({P})\right)\widehat{{\bm{y}}}+\alpha\cdot{\bm{1}}_{P}=\left(1-\alpha\mathrm{vol}({P})\right)\widehat{{\bm{y}}}+\alpha\cdot\mathrm{vol}({P})\cdot{\bm{y}}_{P},$
(7.7)

where ${\bm{1}}_{P}$ is the indicator vector of the set ${P}$. Notice that
$\widehat{z}$ preserves the relative ordering of the vertices and edges with
respect to ${\bm{x}}^{\star}$ and ${\bm{y}}^{\star}$, and all the constraints
in (7.5) hold for $\widehat{z}$. These imply that $\widehat{z}$ is a feasible
solution to (7.5) as well. Moreover, it’s not difficult to see that
$\widehat{z}$ is an optimal solution of (7.5), since otherwise by the
linearity of (7.6) and (7.7) $z_{P}$ would have a higher objective value than
$z^{\star}$, contradicting the fact that $z^{\star}$ is an optimal solution.
Hence, the non-empty level set defined by $\widehat{z}$ corresponds to an
optimal solution. Finally, by applying the second case inductively, we prove
the claimed statement of the lemma. ∎

By applying the lemma above and the linearity of the objective function of
(7.5), we obtain the following corollary.

######  Corollary 7.1.

The following statements hold:

  * •

Suppose that ${P}_{1}$ and ${P}_{2}$ are optimal subsets of ${U}$. Then,
${P}_{1}\cup{P}_{2}$, as well as ${P}_{1}\cap{P}_{2}$ satisfying
${P}_{1}\cap{P}_{2}\neq\emptyset$, is an optimal subset of ${U}$.

  * •

The optimal set of maximum size is unique, and contains all optimal subsets.

Now we are ready to show that the procedure ComputeChangeRate (Algorithm 2)
and the linear program (7.5) together always give us the same set of
${\bm{r}}$-values regardless of which optimal solution of (7.5) is used for
the recursive construction of the entire vector ${\bm{r}}$.

######  Lemma 7.3.

Let $({U},{E}_{U})$ be the input to ComputeChangeRate, and ${P}\subset{U}$ be
the set returned by (7.5). Moreover, let
$\left({U}^{\prime}={U}\setminus{P},{E}_{{U}^{\prime}}\right)$ be the input to
the recursive call ComputeChangeRate$({U}^{\prime},{E}_{{U}^{\prime}})$. Then,
it holds for any ${P}^{\prime}\subseteq{U}^{\prime}$ that
$\delta({P}^{\prime})\leq\delta({P})$, where the equality holds if and only if
$\delta({P}\cup{P}^{\prime})=\delta({P})$.

###### Proof.

By the definition of the function $c$ and sets
$\mathcal{S}^{+},\mathcal{S}^{-},\mathcal{I}^{+},\mathcal{I}^{-}$, it holds
that

$c\left(\mathcal{S}_{{U^{\prime}},{P^{\prime}}}^{+}\right)=c\left(\mathcal{S}_{{U},{P\cup
P^{\prime}}}^{+}\right)-c\left(\mathcal{S}_{{U},{P}}^{+}\right),$

and the same equality holds for sets $\mathcal{S}^{-},\mathcal{I}^{+}$ and
$\mathcal{I}^{-}$. We have that

$\displaystyle\delta({P}^{\prime})$
$\displaystyle=\frac{c\left(\mathcal{S}_{{U^{\prime}},{P^{\prime}}}^{+}\right)+c\left(\mathcal{I}_{{U^{\prime}},{P^{\prime}}}^{+}\right)-c\left(\mathcal{S}_{{U^{\prime}},{P^{\prime}}}^{-}\right)-c\left(\mathcal{I}_{{U^{\prime}},{P^{\prime}}}^{-}\right)}{\mathrm{vol}({P}^{\prime})}$
$\displaystyle=\frac{\delta\left({P}\cup{P}^{\prime}\right)\cdot\mathrm{vol}({P}\cup{P}^{\prime})-\delta({P})\cdot\mathrm{vol}({P})}{\mathrm{vol}({P}\cup{P}^{\prime})-\mathrm{vol}({P})}.$

Therefore, it holds for any operator $\bowtie\ \in\\{<,=,>\\}$ that

$\displaystyle\delta({P}^{\prime})$ $\displaystyle\bowtie\delta({P})$
$\displaystyle\iff$
$\displaystyle\frac{\delta({P}\cup{P}^{\prime})\cdot\mathrm{vol}({P}\cup{P}^{\prime})-\delta({P})\cdot\mathrm{vol}({P})}{\mathrm{vol}({P}\cup{P}^{\prime})-\mathrm{vol}({P})}$
$\displaystyle\bowtie\delta({P})$ $\displaystyle\iff$
$\displaystyle\delta({P}\cup{P}^{\prime})$ $\displaystyle\bowtie\delta({P}),$

which implies that $\delta({P}^{\prime})\leq\delta({P})$ if and only if
$\delta({P}\cup{P}^{\prime})\leq\delta({P})$ with equality if and only if
$\delta({P}\cup{P}^{\prime})=\delta({P})$. Since ${P}$ is optimal, it cannot
be the case that $\delta\left({P}\cup{P}^{\prime}\right)>\delta({P})$, and
therefore the lemma follows. ∎

Combining everything together, we have that for any input instance
$({U},{E}_{U})$, Algorithm 2 always returns the same output
${\bm{r}}\in\mathbb{R}^{\left\lvert{U}\right\rvert}$ no matter which optimal
sets are returned by solving the linear program (7.5). In particular,
Algorithm 2 always finds the unique optimal set ${P}\subseteq{U}$ of maximum
size, and assigns ${\bm{r}}(u)=\delta({P})$ to every $u\in{P}$. After removing
the computed ${P}\subset{U}$, the computed ${\bm{r}}(v)=\delta({P}^{\prime})$
for some ${P}^{\prime}\subseteq{U}\setminus{P}$ and any $v\in{P}^{\prime}$ is
always strictly less than ${\bm{r}}(u)=\delta({P})$ for any $u\in{P}$.

##### Any ${\bm{r}}$ Satisfying Rules (1) and (2) is Computed by Algorithm 2

Next we show that if there is any vector ${\bm{r}}$ satisfying Rules (1) and
(2), it must be equal to the output of Algorithm 2.

######  Lemma 7.4.

For any hypergraph ${H}=({V}_{H},{E}_{H},{w})$ and
${\bm{f}}_{t}\in\mathbb{R}^{n}$, if there is a vector
${\bm{r}}=\mathrm{d}{\bm{f}}_{t}/\mathrm{d}t$ with an associated
$\\{{\bm{r}}_{e}(v)\\}_{e\in{E}_{H},v\in{V}_{H}}$ satisfying Rules (1) and
(2), then ${\bm{r}}$ is equal to the output of Algorithm 2.

###### Proof.

We focus our attention on a single equivalence class ${U}\subset{V}$ where for
any $u,v\in{U}$, ${\bm{f}}(u)={\bm{f}}(v)$. Recall that for each
$e\in{E}_{U}$,
$c_{{\bm{f}}_{t}}(e)={w}(e)\left\lvert{\Delta}_{{\bm{f}}_{t}}(e)\right\rvert$,
which is the rate of flow due to $e$ into ${U}$ (if
$e\in\mathcal{S}_{{U}}^{+}\cup\mathcal{I}_{{U}}^{+}$) or out of ${U}$ (if
$e\in\mathcal{S}_{{U}}^{-}\cup\mathcal{I}_{{U}}^{-}$). Let
${\bm{r}}\in\mathbb{R}^{n}$ be the vector supposed to satisfy Rules (1) and
(2). We assume that ${U}\subseteq{V}$ is an arbitrary equivalence class, and
define

${T}\triangleq\left\\{u\in{U}:{\bm{r}}(u)=\max_{v\in{U}}{\bm{r}}(v)\right\\}.$

Let us study which properties ${\bm{r}}$ must satisfy according to Rules (1)
and (2).

  * •

Assume that $e\in\mathcal{S}_{U}^{-}$, i.e., it holds that
${S}_{{\bm{f}}_{t}}(e)\cap U\neq\emptyset$ and ${\Delta}_{{\bm{f}}_{t}}(e)>0$.
To satisfy Rule (2a), it suffices to have that

$c_{{\bm{f}}_{t}}(e)={w}(e)\cdot{\Delta}_{{\bm{f}}_{t}}(e)=-\sum_{v\in{S}_{{\bm{f}}}(e)}{d}(v){\bm{r}}_{e}(v)=-\sum_{v\in{T}}{d}(v){\bm{r}}_{e}(v)$

if ${S}_{{\bm{f}}_{t}}(e)\cap{T}\neq\emptyset$, and ${\bm{r}}_{e}(v)=0$ for
all $v\in{T}$ otherwise.

  * •

Assume that $e\in\mathcal{S}_{U}^{+}$, i.e., it holds that
${S}_{{\bm{f}}_{t}}(e)\cap{U}\neq\emptyset$ and
${\Delta}_{{\bm{f}}_{t}}(e)<0$. To satisfy Rule (2a), it suffices to have
${S}_{{\bm{f}}_{t}}(e)\subseteq{T}$, or
${S}_{{\bm{f}}_{t}}(e)\cap{T}=\emptyset$.

  * •

Assume that $e\in\mathcal{I}_{U}^{+}$, i.e., it holds that
${I}_{{\bm{f}}}(e)\cap{U}\neq\emptyset$ and ${\Delta}_{{\bm{f}}_{t}}(e)<0$. To
satisfy Rule (2b), it suffices to have that

$c_{{\bm{f}}_{t}}(e)=\sum_{v\in{I}_{{\bm{f}}}(e)}{d}(v){\bm{r}}_{e}(v)=\sum_{v\in{T}}{d}(v){\bm{r}}_{e}(v)$

if ${I}_{{\bm{f}}}(e)\subseteq{T}$, and ${\bm{r}}_{e}(v)=0$ for all $v\in{T}$
otherwise.

  * •

Assume that $e\in\mathcal{I}_{U}^{-}$, i.e., it holds that
${I}_{{\bm{f}}}(e)\cap{U}\neq\emptyset$ and ${\Delta}_{{\bm{f}}_{t}}(e)>0$. To
satisfy Rule (2b), it suffices to have ${I}_{{\bm{f}}}(e)\subseteq{T}$, or
${I}_{{\bm{f}}}(e)\cap{T}=\emptyset$.

Notice that the four conditions above needed to satisfy Rule (2) naturally
reflect our definitions of the sets
$\mathcal{S}_{{U},{P}}^{+},\mathcal{I}_{{U},{P}}^{+},\mathcal{S}_{{U},{P}}^{-}$,
and $\mathcal{I}_{{U},{P}}^{-}$ and for all $u\in{T}$, it must be that
${\bm{r}}(u)=\delta({T})$.

Now we show that the output set ${P}$ returned by solving the linear program
(7.5) is the set ${T}$. To prove this, notice that on one hand, by Corollary
7.1, the linear program gives us the unique maximal optimal subset
${P}\subseteq{U}$, and every $v\in{P}$ satisfies that
${\bm{r}}(v)=\delta({P})\leq{\bm{r}}(u)=\delta({T})$ for any $u\in{T}$ as
every vertex in ${T}$ has the maximum ${\bm{r}}$-value. On the other side, we
have that $\delta({T})\leq\delta({P})$ since ${P}$ is the set returned by the
linear program, and therefore ${T}={P}$. We can apply this argument
recursively, and this proves that Algorithm 2 must return the vector
${\bm{r}}$. ∎

##### Output of Algorithm 2 Satisfies Rules (1) and (2)

Now we show that the output of Algorithm 2 does indeed satisfy Rules (1) and
(2) which, together with Lemma 7.4, implies that there is exactly one such
vector satisfying the rules.

######  Lemma 7.5.

For any hypergraph ${H}=({V}_{H},{E}_{H},{w})$ and vector
${\bm{f}}_{t}\in\mathbb{R}^{n}$, the vector ${\bm{r}}$ constructed by
Algorithm 2 has corresponding
$\\{{\bm{r}}_{e}(v)\\}_{e\in{E}_{H},v\in{V}_{H}}$ which satisfies Rules (1)
and (2). Moreover, the $\\{{\bm{r}}_{e}(v)\\}_{e\in{E}_{H},v\in{V}_{H}}$
values can be computed in polynomial time using the vector ${\bm{r}}$.

###### Proof.

We focus on a single iteration of the algorithm, in which $r(v)$ is assigned
for the vertices in some set ${T}\subset{V}_{H}$. We use the notation

$\mathcal{E}_{{T}}^{+}=\mathcal{I}_{{U},{T}}^{+}\cup\mathcal{S}_{{U},{T}}^{+},\qquad\mathcal{E}_{{T}}^{-}=\mathcal{I}_{{U},{T}}^{-}\cup\mathcal{S}_{{U},{T}}^{-}$

and show that the values of ${\bm{r}}_{e}(v)$ for
$e\in\mathcal{E}_{{T}}^{+}\cup\mathcal{E}_{{T}}^{-}$ can be computed and
satisfy Rules (1) and (2). Therefore, by applying this argument to each
recursive call of the algorithm, we establish the lemma. Given the set ${T}$,
construct the following undirected flow graph, which is illustrated in Figure
7.4.

  * •

The vertex set is
$\mathcal{E}_{{T}}^{+}\cup\mathcal{E}_{{T}}^{-}\cup{T}\cup\\{s,t\\}$.

  * •

For all $e\in\mathcal{E}_{{T}}^{+}$, there is an edge $(s,e)$ with capacity
$c_{{\bm{f}}_{t}}(e)$.

  * •

For all $e\in\mathcal{E}_{{T}}^{-}$, there is an edge $(e,t)$ with capacity
$c_{{\bm{f}}_{t}}(e)$.

  * •

For all $v\in{T}$, if $\delta({T})\geq 0$, there is an edge $(v,t)$ with
capacity ${d}(v)\delta({T})$. Otherwise, there is an edge $(s,v)$ with
capacity ${d}(v)\left\lvert\delta({T})\right\rvert$.

  * •

For each $e\in\mathcal{E}_{{T}}^{+}\cup\mathcal{E}_{{T}}^{-}$, and each
$v\in{T}\cap\left({S}_{{\bm{f}}_{t}}(e)\cup{I}_{{\bm{f}}_{t}}(e)\right)$,
there is an edge $(e,v)$ with capacity $\infty$.

$\xrightarrow{}$$\begin{bmatrix}{\mathbf{B}}_{1}&{\mathbf{0}}&{\mathbf{0}}\\\
{\mathbf{0}}&{\mathbf{B}}_{2}&{\mathbf{0}}\\\
{\mathbf{0}}&{\mathbf{0}}&{\mathbf{B}}_{3}\end{bmatrix}$$\xrightarrow{}$Graph
${G}$Normalised Laplacian ${\mathbf{N}}$Spectral
Embedding$\xrightarrow{}$$\begin{bmatrix}{\mathbf{B}}_{1}&{\mathbf{C}}_{12}&{\mathbf{C}}_{13}\\\
{\mathbf{C}}_{12}^{\intercal}&{\mathbf{B}}_{2}&{\mathbf{C}}_{23}\\\
{\mathbf{C}}_{13}^{\intercal}&{\mathbf{C}}_{23}^{\intercal}&{\mathbf{B}}_{3}\end{bmatrix}$$\xrightarrow{}$Graph
${G}$Normalised Laplacian ${\mathbf{N}}$Spectral
Embedding$\rightarrow$$v_{1}$$v_{3}$$v_{5}$$v_{4}$$v_{2}$$\rightarrow$$x_{1}=v_{1}$$x_{2}=v_{4}$$x_{3}=v_{5}$${\bm{p}}^{(i)}$${\bm{p}}^{(j)}$$\frac{{\bm{p}}^{(i)}}{\left\|{\bm{p}}^{(i)}\right\|}$$\frac{{\bm{p}}^{(j)}}{\left\|{\bm{p}}^{(j)}\right\|}$${\bm{a}}_{i}$${\bm{a}}_{j}$$\frac{\left\|{\bm{a}}_{i}\right\|}{\left\|{\bm{a}}_{j}\right\|}{\bm{a}}_{j}$$a_{1}$$a_{2}$$a$$b$$c$$d$$\Longrightarrow$$b_{1}$$b_{2}$$c_{1}$$c_{2}$$d_{1}$$d_{2}$$\cdots$$a_{1}$$S$$b_{1}$$c_{1}$$d_{1}$$e_{1}$$f_{1}$$\cdots$$\cdots$$a_{2}$$b_{2}$$c_{2}$$d_{2}$$e_{2}$$f_{2}$$\cdots$$a_{1}$$a_{2}$$a$$b$$c$$d$$\Longrightarrow$$b_{1}$$b_{2}$$c_{1}$$c_{2}$$d_{1}$$d_{2}$$a_{1}$$b_{1}$$a_{2}$$b_{2}$ab$\Longrightarrow$$0.5$$0.5$$0.5$$0.5$$0.5$$0.5$$0.5$$0.5$$0.62$$0.38$$1.0$$0.38$$0.62$$1.0$$1.0$$0.5$$0.25$$0.25$$1.0$$1.0$$0.5$$0.5$$\begin{bmatrix}1\\\
0\\\ 0\\\ 0\\\ 0\\\
0\end{bmatrix}$$\rightarrow$$\rightarrow$$t=0$$t=1$$\begin{bmatrix}0.29\\\
-0.14\\\ -0.14\\\ 0.02\\\ 0.02\\\
0.02\end{bmatrix}$$\rightarrow$$\rightarrow$$t=3$$\begin{bmatrix}0.11\\\
-0.09\\\ -0.09\\\ 0.04\\\ 0.04\\\
0.04\end{bmatrix}$$\rightarrow$$\rightarrow$$t=4$$\begin{bmatrix}0.09\\\
-0.71\\\ -0.71\\\ 0.03\\\ 0.03\\\
0.03\end{bmatrix}$$\rightarrow$$\rightarrow$$t=23$$\begin{bmatrix}0.03\\\
-0.03\\\ -0.03\\\ 0.03\\\ -0.03\\\
-0.03\end{bmatrix}$$v_{1}$$v_{2}$$v_{3}$$v_{5}$$v_{4}$${\bm{f}}_{t}$${\bm{f}}_{t}$${\bm{f}}_{t}$${\bm{f}}_{t}$${\bm{f}}_{t}$$v_{6}$${L}$${R}$Hypergraph
${H}_{1}$${L}$${R}$Hypergraph
${H}_{2}$$\vdots$$\vdots$$\vdots$$\vdots$$\vdots$$\vdots$$\vdots$$\vdots$$\vdots$$-2$$-2$$0$$1$$3$$1$Hyperedge
$e$${I}_{{\bm{f}}}(e)$${S}_{{\bm{f}}}(e)$s$T$t$\mathcal{E}_{T}^{+}$$\mathcal{E}_{T}^{-}$$\vdots$$c(e)$$c(e)$$d(v)\delta(T)$$\infty$
(a)

$\xrightarrow{}$$\begin{bmatrix}{\mathbf{B}}_{1}&{\mathbf{0}}&{\mathbf{0}}\\\
{\mathbf{0}}&{\mathbf{B}}_{2}&{\mathbf{0}}\\\
{\mathbf{0}}&{\mathbf{0}}&{\mathbf{B}}_{3}\end{bmatrix}$$\xrightarrow{}$Graph
${G}$Normalised Laplacian ${\mathbf{N}}$Spectral
Embedding$\xrightarrow{}$$\begin{bmatrix}{\mathbf{B}}_{1}&{\mathbf{C}}_{12}&{\mathbf{C}}_{13}\\\
{\mathbf{C}}_{12}^{\intercal}&{\mathbf{B}}_{2}&{\mathbf{C}}_{23}\\\
{\mathbf{C}}_{13}^{\intercal}&{\mathbf{C}}_{23}^{\intercal}&{\mathbf{B}}_{3}\end{bmatrix}$$\xrightarrow{}$Graph
${G}$Normalised Laplacian ${\mathbf{N}}$Spectral
Embedding$\rightarrow$$v_{1}$$v_{3}$$v_{5}$$v_{4}$$v_{2}$$\rightarrow$$x_{1}=v_{1}$$x_{2}=v_{4}$$x_{3}=v_{5}$${\bm{p}}^{(i)}$${\bm{p}}^{(j)}$$\frac{{\bm{p}}^{(i)}}{\left\|{\bm{p}}^{(i)}\right\|}$$\frac{{\bm{p}}^{(j)}}{\left\|{\bm{p}}^{(j)}\right\|}$${\bm{a}}_{i}$${\bm{a}}_{j}$$\frac{\left\|{\bm{a}}_{i}\right\|}{\left\|{\bm{a}}_{j}\right\|}{\bm{a}}_{j}$$a_{1}$$a_{2}$$a$$b$$c$$d$$\Longrightarrow$$b_{1}$$b_{2}$$c_{1}$$c_{2}$$d_{1}$$d_{2}$$\cdots$$a_{1}$$S$$b_{1}$$c_{1}$$d_{1}$$e_{1}$$f_{1}$$\cdots$$\cdots$$a_{2}$$b_{2}$$c_{2}$$d_{2}$$e_{2}$$f_{2}$$\cdots$$a_{1}$$a_{2}$$a$$b$$c$$d$$\Longrightarrow$$b_{1}$$b_{2}$$c_{1}$$c_{2}$$d_{1}$$d_{2}$$a_{1}$$b_{1}$$a_{2}$$b_{2}$ab$\Longrightarrow$$0.5$$0.5$$0.5$$0.5$$0.5$$0.5$$0.5$$0.5$$0.62$$0.38$$1.0$$0.38$$0.62$$1.0$$1.0$$0.5$$0.25$$0.25$$1.0$$1.0$$0.5$$0.5$$\begin{bmatrix}1\\\
0\\\ 0\\\ 0\\\ 0\\\
0\end{bmatrix}$$\rightarrow$$\rightarrow$$t=0$$t=1$$\begin{bmatrix}0.29\\\
-0.14\\\ -0.14\\\ 0.02\\\ 0.02\\\
0.02\end{bmatrix}$$\rightarrow$$\rightarrow$$t=3$$\begin{bmatrix}0.11\\\
-0.09\\\ -0.09\\\ 0.04\\\ 0.04\\\
0.04\end{bmatrix}$$\rightarrow$$\rightarrow$$t=4$$\begin{bmatrix}0.09\\\
-0.71\\\ -0.71\\\ 0.03\\\ 0.03\\\
0.03\end{bmatrix}$$\rightarrow$$\rightarrow$$t=23$$\begin{bmatrix}0.03\\\
-0.03\\\ -0.03\\\ 0.03\\\ -0.03\\\
-0.03\end{bmatrix}$$v_{1}$$v_{2}$$v_{3}$$v_{5}$$v_{4}$${\bm{f}}_{t}$${\bm{f}}_{t}$${\bm{f}}_{t}$${\bm{f}}_{t}$${\bm{f}}_{t}$$v_{6}$${L}$${R}$Hypergraph
${H}_{1}$${L}$${R}$Hypergraph
${H}_{2}$$\vdots$$\vdots$$\vdots$$\vdots$$\vdots$$\vdots$$\vdots$$\vdots$$\vdots$$-2$$-2$$0$$1$$3$$1$Hyperedge
$e$${I}_{{\bm{f}}}(e)$${S}_{{\bm{f}}}(e)$s$T$t$\mathcal{E}_{T}^{+}$$\mathcal{E}_{T}^{-}$$\vdots$$c(e)$$c(e)$$d(v)\delta(T)$$\infty$s$T^{\prime}$t$\mathcal{E}_{T^{\prime}}^{+}$$\mathcal{E}_{T^{\prime}}^{-}$$\vdots$$c(e)$$c(e)$$d(v)\delta(T)$$\infty$
(b)

Figure 7.4:  (a) An illustration of the constructed max-flow graph, when
$\delta({T})\geq 0$. The minimum cut is given by $\\{s\\}$. (b) A cut induced
by ${T}^{\prime}\subset{T}$. We can assume that every
$e\in\mathcal{E}_{{T}}^{+}\cup\mathcal{E}_{{T}}^{-}$ connected to
${T}^{\prime}$ is on the same side of the cut as ${T}^{\prime}$. Otherwise,
there would be an edge with infinite capacity crossing the cut.

We use $\mathrm{cut}({A})$ to denote the weight of the cut defined by the set
${A}$ in this constructed graph, and note that
$\mathrm{cut}(\\{s\\})=\mathrm{cut}(\\{t\\})$ since

$\displaystyle\mathrm{cut}(\\{s\\})-\mathrm{cut}(\\{t\\})=\sum_{e\in\mathcal{E}_{{T}}^{+}}c_{{\bm{f}}}(e)-\sum_{e\in\mathcal{E}_{{T}}^{-}}c_{{\bm{f}}}(e)-\mathrm{vol}({T})\delta({T})=0$

by the definition of $\delta({T})$.

Now, suppose that the maximum flow value on this graph is
$\mathrm{cut}(\\{s\\})$, and let the corresponding flow from $u$ to $v$ be
given by $\Theta(u,v)=-\Theta(v,u)$. Then, set
${d}(v){\bm{r}}_{e}(v)=\Theta(e,v)$ for any
$e\in\mathcal{E}_{{T}}^{+}\cup\mathcal{E}_{{T}}^{-}$ and $v\in{T}\cap e$. This
configuration of the values ${\bm{r}}_{e}(v)$ would be compatible with the
vector ${\bm{r}}$ computed by Algorithm 2, and would satisfy the rules of the
diffusion process for the following reasons:

  * •

For all $v\in{T}$, the edge $(v,t)$ or $(s,v)$ is saturated and so

$\sum_{e\in{E}}{d}(v){\bm{r}}_{e}(v)={d}(v)\delta({T})={d}(v){\bm{r}}(v)$

.

  * •

For any $e\in\mathcal{E}_{{T}}^{+}\cup\mathcal{E}_{{T}}^{-}$, the edge $(s,e)$
or $(e,t)$ is saturated and so we have

$\sum_{v\in{T}\cap e}{d}(v){\bm{r}}_{v}(e)=-{w}(e){\Delta}(e).$

Since $\mathcal{E}_{{T}}^{+}\cup\mathcal{E}_{{T}}^{-}$ is removed in the
recursive step of the algorithm, ${\bm{r}}_{e}(v)=0$ for all
$v\in{U}\setminus{T}$ and so $\sum_{v\in{U}\cap
e}{d}(v){\bm{r}}_{e}(v)=-{w}(e){\Delta}(e)$. This establishes Rule (1) since
${U}\cap e$ is equal to either ${S}_{{\bm{f}}}(e)$ or ${I}_{{\bm{f}}}(e)$.

  * •

For edges in $\mathcal{S}_{{U},{T}}^{+}$ (resp. $\mathcal{I}_{{U},{T}}^{+}$,
$\mathcal{I}_{{U},{T}}^{-}$), since ${S}_{{\bm{f}}_{t}}(e)$ (resp.
${I}_{{\bm{f}}_{t}}(e)$, ${I}_{{\bm{f}}_{t}}(e)$) is a subset of ${T}$ and
every $v\in{T}$ has the same value of ${\bm{r}}(v)$, Rule (2) is satisfied.
For edges in $\mathcal{S}_{{U},{T}}^{-}$, for any $v\not\in{T}$, we have
${\bm{r}}_{e}(v)=0$ and ${\bm{r}}(v)<\delta({T})$ which satisfies Rule (2).

We now show that every cut separating $s$ and $t$ has weight at least
$\mathrm{cut}(\\{s\\})$ which would establish that the maximum flow on this
graph is $\mathrm{cut}(\\{s\\})$ by the max-flow min-cut theorem.

Consider some arbitrary cut given by
${X}=\\{s\\}\cup{T}^{\prime}\cup\mathcal{E}_{{T}^{\prime}}^{+}\cup\mathcal{E}_{{T}^{\prime}}^{-}$
where ${T}^{\prime}$ (resp. $\mathcal{E}_{{T}^{\prime}}^{+}$,
$\mathcal{E}_{{T}^{\prime}}^{-}$) is a subset of ${T}$ (resp.
$\mathcal{E}_{{T}}^{+}$, $\mathcal{E}_{{T}}^{-}$). Figure 7.4 illustrates this
cut. Since all of the edges not connected to $s$ or $t$ have infinite
capacity, we can assume that no such edge crosses the cut which implies that

  * •

for all $e\in\mathcal{E}_{{T}^{\prime}}^{+}$,
$e\cap({T}\setminus{T}^{\prime})=\emptyset$;

  * •

for all $e\in\mathcal{E}_{{T}^{\prime}}^{-}$,
$e\cap({T}\setminus{T}^{\prime})=\emptyset$;

  * •

for all $e\in(\mathcal{E}_{{T}}^{+}\setminus\mathcal{E}_{{T}^{\prime}}^{+})$,
$e\cap{T}^{\prime}=\emptyset$;

  * •

for all $e\in(\mathcal{E}_{T}^{-}\setminus\mathcal{E}_{{T}^{\prime}}^{-})$,
$e\cap{T}^{\prime}=\emptyset$.

These conditions, along with the definition of $\mathcal{E}_{{T}}^{+}$ and
$\mathcal{E}_{{T}}^{-}$, allow us to assume that
$\mathcal{E}_{{T}^{\prime}}^{+}=\mathcal{I}_{{U},{T^{\prime}}}^{+}\cup\mathcal{S}_{{U},{T^{\prime}}}^{+}$
and
$\mathcal{E}_{{T}^{\prime}}^{-}=\mathcal{I}_{{U},{T^{\prime}}}^{-}\cup\mathcal{S}_{{U},{T^{\prime}}}^{-}$.
The size of this arbitrary cut is

$\mathrm{cut}({X})=\mathrm{cut}(\\{s\\})-\sum_{e\in\mathcal{E}_{{T}^{\prime}}^{+}}c(e)+\sum_{e\in\mathcal{E}_{{T}^{\prime}}^{-}}c(e)+\sum_{v\in{T}^{\prime}}{d}(v)\delta({T}).$

Since ${T}$ maximises the objective function $\delta$, we have

$\sum_{e\in\mathcal{E}_{{T}^{\prime}}^{+}}c(e)-\sum_{e\in\mathcal{E}_{{T}^{\prime}}^{-}}c(e)=\mathrm{vol}({T}^{\prime})\delta({T}^{\prime})\leq\mathrm{vol}({T}^{\prime})\delta({T})=\sum_{v\in{T}^{\prime}}{d}(v)\delta({T})$

and can conclude that $\mathrm{cut}({X})\geq\mathrm{cut}(\\{s\\})$. This
completes the proof. ∎

We can now combine the results in Lemmas 7.4 and 7.5 to prove Lemma 7.1.

###### Proof of Lemma 7.1..

Lemma 7.4 and Lemma 7.5 together imply that there is a unique vector
${\bm{r}}$ and corresponding $\\{{\bm{r}}_{e}(v)\\}_{e\in{E}_{H},v\in{V}_{H}}$
which satisfies Rules (1) and (2). Lemma 7.4 further shows that Algorithm 2
computes this vector ${\bm{r}}$, and the proof of Lemma 7.5 gives a
polynomial-time algorithm for computing the $\\{{\bm{r}}_{e}(v)\\}$ values by
solving a sequence of max-flow problems. ∎

###  7.5 Analysis of Algorithm 1

In this section we analyse the FindBipartiteComponents algorithm and prove
Theorem 7.1. This section consists of two parts corresponding to the two
statements in Theorem 7.1. First, we show that the diffusion process converges
to an eigenvector of ${\mathbf{J}}_{H}$. We then show that this allows us to
find sets ${L},{R}\subset{V}_{H}$ with low hypergraph bipartiteness.

####  7.5.1 Convergence of the Diffusion Process

We now show that the diffusion process determined by the operator
${\mathbf{J}}_{H}$ converges in polynomial time to an eigenvector of
${\mathbf{J}}_{H}$.

######  Theorem 7.2.

For any $\epsilon>0$, there is some $t=O\\!\left(1/\epsilon^{3}\right)$ such
that for any starting vector ${\bm{f}}_{0}$, there is an interval
$[c,c+2\epsilon]$ such that

$\frac{1}{\left\|{\bm{f}}_{t}\right\|_{w}}\sum_{{\bm{u}}_{i}:\lambda_{i}\in[c,c+2\epsilon]}\left\langle{\bm{f}}_{t},{\bm{u}}_{i}\right\rangle_{w}\geq
1-\epsilon,$

where $({\bm{u}}_{i},\lambda_{i})$ are the eigen-pairs of
${\mathbf{D}}_{H}^{-1}{\mathbf{J}}_{t}={\mathbf{D}}_{H}^{-1}({\mathbf{D}}_{{G}_{t}}+{\mathbf{A}}_{{G}_{t}})$
and ${G}_{t}$ is the graph constructed to represent the diffusion operator
${\mathbf{J}}_{H}$ at time $t$.

By taking $\epsilon$ to be some small constant, this shows that the vector
${\bm{f}}_{t}$ converges to an eigenvector of the hypergraph operator in
polynomial time.

###### Proof.

We show that the Rayleigh quotient $R_{{\mathbf{J}}_{H}}({\bm{f}}_{t})$ is
always decreasing at a rate of at least $\epsilon^{3}$ whenever the conclusion
of Theorem 7.2 does not hold. Since $R_{{\mathbf{J}}_{H}}({\bm{f}}_{t})$ can
only decrease by a constant amount, the theorem follows.

First, we derive an expression for the rate of change of the Rayleigh quotient
$R_{{\mathbf{J}}_{H}}({\bm{f}}_{t})$. Let
${\bm{x}}_{t}\triangleq{\mathbf{D}}^{\frac{1}{2}}_{H}{\bm{f}}_{t}$, and

${\mathbf{Z}}_{t}={\mathbf{D}}^{-\frac{1}{2}}_{H}({\mathbf{D}}_{{G}_{t}}+{\mathbf{A}}_{{G}_{t}}){\mathbf{D}}^{-\frac{1}{2}}_{H}.$

Then, we have

$R_{{\mathbf{J}}_{H}}({\bm{f}}_{t})=\frac{{\bm{f}}_{t}^{\intercal}({\mathbf{D}}_{{G}_{t}}+{\mathbf{A}}_{{G}_{t}}){\bm{f}}_{t}}{{\bm{f}}_{t}^{\intercal}{\mathbf{D}}_{H}{\bm{f}}_{t}}=\frac{{\bm{x}}_{t}^{\intercal}{\mathbf{Z}}_{t}{\bm{x}}_{t}}{{\bm{x}}_{t}^{\intercal}{\bm{x}}_{t}}.$

For every eigenvector ${\bm{u}}_{j}$ of
${\mathbf{D}}_{H}^{-1}{\mathbf{J}}_{H}$, the vector
${\bm{v}}_{j}={\mathbf{D}}^{\frac{1}{2}}_{H}{\bm{u}}_{j}$ is an eigenvector of
${\mathbf{Z}}$ with the same eigenvalue $\lambda_{i}$. Since ${\mathbf{Z}}$ is
symmetric, the vectors ${\bm{v}}_{1},\ldots,{\bm{v}}_{n}$ are orthogonal.
Additionally, notice that

$\left\langle{\bm{x}}_{t},{\bm{v}}_{j}\right\rangle={\bm{f}}^{\intercal}_{t}{\mathbf{D}}_{H}{\bm{u}}_{j}=\left\langle{\bm{f}}_{t},{\bm{u}}_{j}\right\rangle_{w}$

and we define
$\alpha_{j}=\left\langle{\bm{f}}_{t},{\bm{u}}_{j}\right\rangle_{w}$ so we can
write ${\bm{x}}_{t}=\sum_{j=1}^{n}\alpha_{j}{\bm{v}}_{j}$ and

${\bm{f}}_{t}={\mathbf{D}}^{-\frac{1}{2}}_{H}{\bm{x}}_{t}=\sum_{j=1}^{n}\alpha_{j}{\bm{u}}_{j}.$

Now, we have that

$\displaystyle\frac{\mathrm{d}}{\mathrm{d}t}\left\langle{\bm{x}}_{t},{\mathbf{Z}}_{t}{\bm{x}}_{t}\right\rangle$
$\displaystyle=\left\langle\frac{\mathrm{d}}{\mathrm{d}t}{\bm{x}}_{t},{\mathbf{Z}}_{t}{\bm{x}}_{t}\right\rangle+\left\langle{\bm{x}}_{t},\frac{\mathrm{d}}{\mathrm{d}t}{\mathbf{Z}}_{t}{\bm{x}}_{t}\right\rangle$
$\displaystyle=-{\bm{x}}_{t}^{\intercal}{\mathbf{Z}}_{t}^{2}{\bm{x}}_{t}-{\bm{x}}_{t}^{\intercal}{\mathbf{Z}}_{t}^{2}{\bm{x}}_{t}$
$\displaystyle=-2\sum_{j=1}^{n}\alpha_{j}^{2}\lambda_{j}^{2}.$

Additionally, we have

$\frac{\mathrm{d}}{\mathrm{d}t}{\bm{x}}_{t}^{\intercal}{\bm{x}}_{t}=-{\bm{x}}_{t}^{\intercal}{\mathbf{Z}}_{t}{\bm{x}}_{t}-{\bm{x}}_{t}^{\intercal}{\mathbf{Z}}_{t}{\bm{x}}_{t}=-2{\bm{x}}_{t}^{\intercal}{\mathbf{Z}}_{t}{\bm{x}}_{t}.$

Recalling that
${\bm{x}}_{t}^{\intercal}{\bm{x}}_{t}=\sum_{j=1}^{n}\alpha_{j}^{2}$, this
gives

$\displaystyle\frac{\mathrm{d}}{\mathrm{d}t}R({\bm{f}}_{t})$
$\displaystyle=\frac{1}{({\bm{x}}_{t}^{\intercal}{\bm{x}}_{t})^{2}}\left(\left(\frac{\mathrm{d}}{\mathrm{d}t}({\bm{x}}_{t}^{\intercal}{\mathbf{Z}}_{t}{\bm{x}}_{t})\right)({\bm{x}}_{t}^{\intercal}{\bm{x}}_{t})-\left(\frac{\mathrm{d}}{\mathrm{d}t}({\bm{x}}_{t}^{\intercal}{\bm{x}}_{t})\right)({\bm{x}}_{t}^{\intercal}{\mathbf{Z}}_{t}{\bm{x}}_{t})\right)$
$\displaystyle=\frac{1}{{\bm{x}}_{t}^{\intercal}{\bm{x}}_{t}}\left(\frac{\mathrm{d}}{\mathrm{d}t}({\bm{x}}_{t}^{\intercal}{\mathbf{Z}}_{t}{\bm{x}}_{t})\right)+2R({\bm{f}}_{t})^{2}$
$\displaystyle=2\left(R({\bm{f}}_{t})^{2}-\frac{1}{\sum_{j=1}^{n}\alpha_{j}^{2}}\sum_{j=1}^{n}\alpha_{j}^{2}\lambda_{j}^{2}\right)$
(7.8)

We now show that at any time $t$, if the conclusion of the theorem does not
hold, then

$\frac{\mathrm{d}}{\mathrm{d}t}R({\bm{f}}_{t})\leq-\epsilon^{3}.$ (7.9)

Assuming that this holds and using the fact that $R({\bm{f}}_{0})\leq 2$, when
$t=2/\epsilon^{3}$, either $R({\bm{f}}_{t})=0$ or there is some $t^{\prime}<t$
when $(\mathrm{d}/\mathrm{d}t^{\prime})R({\bm{f}}_{t^{\prime}})>-\epsilon^{3}$
and the conclusion of the theorem holds.

Now, to show (7.9), consider the partial derivative

$\displaystyle\frac{\partial}{\partial\lambda_{i}}2\left(R({\bm{f}}_{t})^{2}-\frac{1}{\sum_{j=1}^{n}\alpha_{j}^{2}}\sum_{j=1}^{n}\alpha_{j}^{2}\lambda_{j}^{2}\right)$
$\displaystyle=2\left(\frac{2\alpha_{i}^{2}}{\sum_{j=1}^{n}\alpha_{j}^{2}}R({\bm{f}}_{t})-\frac{2\alpha_{i}^{2}}{\sum_{j=1}^{n}\alpha_{j}^{2}}\lambda_{i}\right)$
$\displaystyle=\frac{4\alpha_{i}^{2}}{\sum_{j=1}^{n}\alpha_{j}^{2}}(R({\bm{f}}_{t})-\lambda_{i}),$
(7.10)

where we use the fact that
$R({\bm{f}}_{t})=(\sum_{j=1}^{n}\alpha_{j}^{2}\lambda_{j})/(\sum_{j=1}^{n}\alpha_{j}^{2})$.
Notice that the derivative in (7.10) is greater than $0$ if
$\lambda_{i}<R({\bm{f}}_{t})$, and the derivative is less than $0$ if
$\lambda_{i}>R({\bm{f}}_{t})$. This means that, in order to establish an
upper-bound of $(\mathrm{d}/\mathrm{d}t)R({\bm{f}}_{t})$, we can assume that
the eigenvalues $\lambda_{j}$ are as close to the value of $R({\bm{f}}_{t})$
as possible.

Now, we assume that at time $t$ the conclusion of the theorem does not hold.
Then, one of the following cases must hold:

  1. 1.

$(\sum_{j:\lambda_{j}>R({\bm{f}}_{t})+\epsilon}\alpha_{j}^{2})/(\sum_{j=1}^{n}\alpha_{j}^{2})>\epsilon/2$;

  2. 2.

$(\sum_{j:\lambda_{j}<R({\bm{f}}_{t})-\epsilon}\alpha_{j}^{2})/(\sum_{j=1}^{n}\alpha_{j}^{2})>\epsilon/2$.

Suppose the first case holds. By the conclusions we draw from (7.10), we can
assume that there is an eigenvalue $\lambda_{i}=R({\bm{f}}_{t})+\epsilon$ such
that $\alpha_{i}^{2}/(\sum_{j=1}^{n}\alpha_{j}^{2})=\epsilon/2$ and that

$\left(\sum_{j:\lambda_{j}<R({\bm{f}}_{t})}\alpha_{j}^{2}\right)\Bigg{/}\left(\sum_{j=1}^{n}\alpha_{j}^{2}\right)=1-\epsilon/2.$

Then, since

$R({\bm{f}}_{t})=\left(\sum_{j=1}^{n}\alpha_{j}^{2}\lambda_{j}\right)\Bigg{/}\left(\sum_{j=1}^{n}\alpha_{j}^{2}\right),$

we have

$\displaystyle\frac{1}{\sum_{j=1}^{n}\alpha_{j}^{2}}\sum_{j:\lambda_{j}<R({\bm{f}}_{t})}\alpha_{j}^{2}\lambda_{j}=R({\bm{f}}_{t})-\frac{\epsilon}{2}(R({\bm{f}}_{t})+\epsilon),$

which is equivalent to

$\frac{1}{\sum_{j=1}^{n}\alpha_{j}^{2}}\sum_{j:\lambda_{j}<R({\bm{f}}_{t})}\alpha_{j}^{2}(\lambda_{j}-R({\bm{f}}_{t}))=\frac{\epsilon}{2}\cdot
R({\bm{f}}_{t})-\frac{\epsilon}{2}\cdot(R({\bm{f}}_{t})+\epsilon)=-\frac{\epsilon^{2}}{2}.$
(7.11)

Now, notice that for any $\lambda_{j}<R({\bm{f}}_{t})$ we have

$\displaystyle(\lambda_{j}^{2}-R({\bm{f}}_{t})^{2})$
$\displaystyle=(\lambda_{j}+R({\bm{f}}_{t}))(\lambda_{j}-R({\bm{f}}_{t}))$
$\displaystyle\geq 2R({\bm{f}}_{t})(\lambda_{j}-R({\bm{f}}_{t})),$

since $\lambda_{j}-R({\bm{f}}_{t})<0$. As such, we have

$\displaystyle\frac{\mathrm{d}}{\mathrm{d}t}R({\bm{f}}_{t})$
$\displaystyle=2\left(R({\bm{f}}_{t})^{2}-\frac{1}{\sum_{j=1}^{n}\alpha_{j}^{2}}\sum_{j=1}^{n}\alpha_{j}^{2}\lambda_{j}^{2}\right)$
$\displaystyle=-\frac{2}{\sum_{j=1}^{n}\alpha_{j}^{2}}\sum_{j=1}^{n}\alpha_{j}^{2}(\lambda_{j}^{2}-R({\bm{f}}_{t})^{2})$
$\displaystyle=-\epsilon\left((R({\bm{f}}_{t})+\epsilon)^{2}-R({\bm{f}}_{t})^{2}\right)-\frac{2}{\sum_{j=1}^{n}\alpha_{j}^{2}}\sum_{j:\lambda_{j}<R({\bm{f}}_{t})}\alpha_{j}^{2}(\lambda_{j}^{2}-R({\bm{f}}_{t})^{2})$
$\displaystyle\leq-\epsilon\left(2\epsilon
R({\bm{f}}_{t})+\epsilon^{2}\right)-\frac{2}{\sum_{j=1}^{n}\alpha_{j}^{2}}\sum_{j:\lambda_{j}<R({\bm{f}}_{t})}2\alpha_{j}^{2}R({\bm{f}}_{t})(\lambda_{j}-R({\bm{f}}_{t}))$
$\displaystyle=-2\epsilon^{2}R({\bm{f}}_{t})-\epsilon^{3}+2\epsilon^{2}R({\bm{f}}_{t})$
$\displaystyle=-\epsilon^{3},$

where the second last equality follows by (7.11). We now consider the second
case. We assume that there is an eigenvalue
$\lambda_{i}=R({\bm{f}}_{t})-\epsilon$ such that
$\alpha_{i}^{2}/(\sum_{j=1}^{n}\alpha_{j}^{2})=\epsilon/2$, and that
$(\sum_{j:\lambda_{j}>R({\bm{f}}_{t})}\alpha_{j}^{2})/(\sum_{j=1}^{n}\alpha_{j}^{2})=1-\epsilon/2$.
Then, we have

$\displaystyle\frac{1}{\sum_{j=1}^{n}\alpha_{j}^{2}}\sum_{j:\lambda_{j}>R({\bm{f}}_{t})}\alpha_{j}^{2}\lambda_{j}=R({\bm{f}}_{t})-\frac{\epsilon}{2}\left(R({\bm{f}}_{t})-\epsilon\right),$

which is equivalent to

$\frac{1}{\sum_{j=1}^{n}\alpha_{j}^{2}}\sum_{j:\lambda_{j}>R({\bm{f}}_{t})}\alpha_{j}^{2}(\lambda_{j}-R({\bm{f}}_{t}))=\frac{\epsilon}{2}R({\bm{f}}_{t})-\frac{\epsilon}{2}(R({\bm{f}}_{t})-\epsilon)=\frac{\epsilon^{2}}{2}.$
(7.12)

Now, notice that for any $\lambda_{j}>R({\bm{f}}_{t})$ we have

$\displaystyle\lambda_{j}^{2}-R({\bm{f}}_{t})^{2}$
$\displaystyle=(\lambda_{j}+R({\bm{f}}_{t}))(\lambda_{j}-R({\bm{f}}_{t}))$
$\displaystyle\geq 2R({\bm{f}}_{t})\cdot(\lambda_{j}-R({\bm{f}}_{t})).$

As such, we have

$\displaystyle\frac{\mathrm{d}}{\mathrm{d}t}R({\bm{f}}_{t})$
$\displaystyle=-\frac{2}{\sum_{j=1}^{n}\alpha_{j}^{2}}\sum_{j=1}^{n}\alpha_{j}^{2}(\lambda_{j}^{2}-R({\bm{f}}_{t})^{2})$
$\displaystyle=-\epsilon\left((R({\bm{f}}_{t})-\epsilon)^{2}-R({\bm{f}}_{t})^{2}\right)-\frac{2}{\sum_{j=1}^{n}\alpha_{j}^{2}}\sum_{j:\lambda_{j}>R({\bm{f}}_{t})}\alpha_{j}^{2}(\lambda_{j}^{2}-R({\bm{f}}_{t})^{2})$
$\displaystyle\leq-\epsilon\left(\epsilon^{2}-2\epsilon
R({\bm{f}}_{t})\right)-\frac{2}{\sum_{j=1}^{n}\alpha_{j}^{2}}\sum_{j:\lambda_{j}<R({\bm{f}}_{t})}2\alpha_{j}^{2}R({\bm{f}}_{t})(\lambda_{j}-R({\bm{f}}_{t}))$
$\displaystyle=2\epsilon^{2}g(t)-\epsilon^{3}-2\epsilon^{2}R({\bm{f}}_{t})$
$\displaystyle=-\epsilon^{3}$

where the second last equality follows by (7.12). These two cases establish
(7.9) and complete the proof of the theorem. ∎

##### Relationship of the Eigenvalue to the Clique Graph

We now show that the eigenvalue corresponding to the eigenvector to which the
algorithm converges is at most the minimum eigenvalue of ${\mathbf{J}}_{G}$
where ${G}$ is the clique reduction of ${H}$. We start by showing the
following technical lemma.

######  Lemma 7.6.

For any hypergraph ${H}=({V}_{H},{E}_{H},{w})$, vector
${\bm{f}}\in\mathbb{R}^{n}$, and edge $e\in{E}_{H}$, it holds that

$\left(\max_{u\in e}{\bm{f}}(u)+\min_{v\in
e}{\bm{f}}(v)\right)^{2}\leq\sum_{u,v\in
e}\frac{1}{\mathrm{rank}(e)-1}({\bm{f}}(u)+{\bm{f}}(v))^{2}.$

The equality holds if and only if there is exactly one vertex $v\in e$ with
${\bm{f}}(v)\neq 0$ or $\mathrm{rank}(e)=2$.

###### Proof.

We consider some ordering of the vertices in $e$,

$u_{1},u_{2},\ldots,u_{\mathrm{rank}(e)},$

such that $u_{1}=\operatorname*{arg\,max}_{u\in e}{\bm{f}}(u)$ and
$u_{2}=\operatorname*{arg\,min}_{u\in e}{\bm{f}}(u)$ and the remaining
vertices are ordered arbitrarily. Then, for any $2\leq k\leq\mathrm{rank}(e)$,
we define

$C_{k}=\sum_{u,v\in\\{u_{1},\ldots,u_{k}\\}}\frac{1}{k-1}({\bm{f}}(u)+{\bm{f}}(v))^{2}.$

We show by induction on $k$ that

$C_{k}\geq\left(\max_{u\in e}{\bm{f}}(u)+\min_{v\in e}{\bm{f}}(v)\right)^{2}$
(7.13)

for all $2\leq k\leq\mathrm{rank}(e)$, with equality if and only if $k=2$ or
there is exactly one vertex $u_{i}\in e$ with ${\bm{f}}(v)\neq 0$. The lemma
follows by setting $k=\mathrm{rank}(e)$.

The base case of $k=2$ follows trivially by the definitions and the choice of
$u_{1}$ and $u_{2}$.

For the inductive step, we assume that (7.13) holds for some $k$, and show
that it holds for $k+1$. We have that

$C_{k+1}=\sum_{u,v\in\\{u_{1},\ldots,u_{k+1}\\}}\frac{1}{k}\cdot({\bm{f}}(u)+{\bm{f}}(v))^{2},$

which is equivalent to

$\displaystyle C_{k+1}$
$\displaystyle=\frac{1}{k}\sum_{i=1}^{k}({\bm{f}}(u_{i})+{\bm{f}}(u_{k+1}))^{2}+\frac{1}{k}\sum_{u,v\in\\{u_{1},\ldots,u_{k}\\}}({\bm{f}}(u)+{\bm{f}}(v))^{2}$
$\displaystyle=\frac{1}{k}\sum_{i=1}^{k}({\bm{f}}(u_{i})+{\bm{f}}(u_{k+1}))^{2}+\frac{k-1}{k}C_{k}$
$\displaystyle\geq\left(1-\frac{1}{k}\right)\left(\max_{u\in
e}{\bm{f}}(u)+\min_{v\in
e}{\bm{f}}(v)\right)^{2}+\frac{1}{k}\sum_{i=1}^{k}({\bm{f}}(u_{1})+{\bm{f}}(u_{k+1}))^{2}$

where the final inequality holds by the induction hypothesis. Therefore, it is
sufficient to show that

$\sum_{i=1}^{k}\left({\bm{f}}(u_{i})+{\bm{f}}(u_{k+1})\right)^{2}\geq\left(\max_{u\in
e}{\bm{f}}(u)+\min_{v\in e}{\bm{f}}(v)\right)^{2}.$

We instead show the stronger fact that

$\left(\max_{v\in e}{\bm{f}}(v)+{\bm{f}}(u_{k+1})\right)^{2}+\left(\min_{v\in
e}{\bm{f}}(v)+{\bm{f}}(u_{k+1})\right)^{2}\geq\left(\max_{u\in
e}{\bm{f}}(u)+\min_{v\in e}{\bm{f}}(v)\right)^{2}.$ (7.14)

The proof is by case distinction. The first case is when

$\mathrm{sign}(\max_{u\in e}{\bm{f}}(v))=\mathrm{sign}(\min_{u\in
e}{\bm{f}}(u)).$

Assume without loss of generality that the sign is positive. Then, since
${\bm{f}}(u_{k+1})\geq\min_{v\in e}{\bm{f}}(v)$, we have

$\left(\max_{v\in
e}{\bm{f}}(v)+{\bm{f}}(u_{k+1})\right)^{2}\geq\left(\max_{v\in
e}{\bm{f}}(v)+\min_{u\in e}{\bm{f}}(v)\right)^{2}$

and (7.14) holds. Moreover, the inequality is strict if $\left\lvert\min_{u\in
e}{\bm{f}}(u)\right\rvert>0$ or $\left\lvert{\bm{f}}(u_{k+1})\right\rvert>0$.

The second case is when

$\mathrm{sign}(\min_{u\in e}{\bm{f}}(u))\neq\mathrm{sign}(\max_{v\in
e}{\bm{f}}(v)).$

Expanding (7.14), we would like to show

$\left(\max_{u\in e}{\bm{f}}(u)\right)^{2}+\left(\min_{v\in
e}{\bm{f}}(v)\right)^{2}+2{\bm{f}}(u_{k+1})\left(\max_{u\in
e}{\bm{f}}(u)\right)+2{\bm{f}}(u_{k+1})\left(\min_{v\in
e}{\bm{f}}(v)\right)\\\ +2{\bm{f}}(u_{k+1})^{2}\geq\left(\max_{u\in
e}{\bm{f}}(u)\right)^{2}+\left(\min_{u\in
e}{\bm{f}}(u)\right)^{2}-2\left(\max_{u\in
e}{\bm{f}}(u)\right)\left\lvert\min_{u\in e}{\bm{f}}(u)\right\rvert,$

which is equivalent to

$2{\bm{f}}(u_{k+1})^{2}+2{\bm{f}}(u_{k+1})\left(\max_{u\in
e}{\bm{f}}(u)\right)+2{\bm{f}}(u_{k+1})\left(\min_{v\in
e}{\bm{f}}(v)\right)\geq-2\left(\max_{u\in
e}{\bm{f}}(u)\right)\left\lvert\min_{v\in e}{\bm{f}}(v)\right\rvert.$

Notice that exactly one of the terms on the left hand side is negative.
Recalling that $\min_{u\in e}{\bm{f}}(u)\leq{\bm{f}}(u_{k+1})\leq\max_{v\in
e}{\bm{f}}(v)$, it is clear that

  * •

if ${\bm{f}}(u_{k+1})<0$, then

$-2\left(\max_{u\in e}{\bm{f}}(u)\right)\left\lvert\min_{v\in
e}{\bm{f}}(v)\right\rvert\leq 2{\bm{f}}(u_{k+1})\left(\max_{v\in
e}{\bm{f}}(v)\right)\leq 0$

and the inequality holds.

  * •

if ${\bm{f}}(u_{k+1})\geq 0$, then

$-2\left(\max_{u\in e}{\bm{f}}(u)\right)\left\lvert\min_{v\in
e}{\bm{f}}(v)\right\rvert\leq 2{\bm{f}}(u_{k+1})\left(\min_{u\in
e}{\bm{f}}(u)\right)\leq 0,$

and the inequality holds.

Moreover, in both cases the inequality is strict if $-2\left(\max_{v\in
e}{\bm{f}}(v)\right)\left\lvert\min_{u\in e}{\bm{f}}(u)\right\rvert<0$ or
$\left\lvert{\bm{f}}(u_{k_{1}})\right\rvert>0$. ∎

Now, we show that one always finds an eigenvector whose corresponding
eigenvalue is at most the minimum eigenvalue of the clique reduction.

######  Lemma 7.7.

For any hypergraph ${H}=({V}_{H},{E}_{H},{w})$ with clique reduction ${G}$, if
${\bm{f}}$ is the eigenvector corresponding to
$\lambda_{1}({\mathbf{D}}_{G}^{-1}{\mathbf{J}}_{G})$, then

$\frac{{\bm{f}}^{\intercal}{\mathbf{J}}_{H}{\bm{f}}}{{\bm{f}}^{\intercal}{\mathbf{D}}_{H}{\bm{f}}}\leq\lambda_{1}({\mathbf{D}}_{G}^{-1}{\mathbf{J}}_{G})$

and the inequality is strict if $\min_{e\in{E}_{H}}\mathrm{rank}(e)>2$.

###### Proof.

Since
$\lambda_{1}({\mathbf{D}}_{G}^{-1}{\mathbf{J}}_{G})=({\bm{f}}^{\intercal}{\mathbf{J}}_{G}{\bm{f}})/({\bm{f}}^{\intercal}{\mathbf{D}}_{G}{\bm{f}})$
and
$({\bm{f}}^{\intercal}{\mathbf{D}}_{G}{\bm{f}})=({\bm{f}}^{\intercal}{\mathbf{D}}_{H}{\bm{f}})$
by the construction of the clique graph, it suffices to show that

${\bm{f}}^{\intercal}{\mathbf{J}}_{H}{\bm{f}}\leq{\bm{f}}^{\intercal}{\mathbf{J}}_{G}{\bm{f}}.$

This is equivalent to

$\displaystyle\sum_{e\in{E}_{H}}{w}(e)\left(\max_{v\in
e}{\bm{f}}(v)+\min_{u\in e}{\bm{f}}(u)\right)^{2}$
$\displaystyle\leq\sum_{(u,v)\in{E}_{G}}{w}_{G}(u,v)({\bm{f}}(u)+{\bm{f}}(v))^{2}$
$\displaystyle=\sum_{e\in{E}_{H}}{w}(e)\sum_{u,v\in
e}\frac{1}{\mathrm{rank}(e)-1}({\bm{f}}(u)+{\bm{f}}(v))^{2}$

which holds by Lemma 7.6.

Furthermore, if $\min_{e\in{E}_{H}}\mathrm{rank}(e)>2$, then by Lemma 7.6 the
inequality is strict unless every edge $e\in{E}_{H}$ contains at most one
$v\in e$ with ${\bm{f}}(v)\neq 0$. Suppose the inequality is not strict, then
it must be that

$\displaystyle\lambda_{1}({\mathbf{D}}_{G}^{-1}{\mathbf{J}}_{G})$
$\displaystyle=\frac{\sum_{(u,v)\in{E}_{G}}{w}_{G}(u,v)({\bm{f}}(v)+{\bm{f}}(u))^{2}}{\sum_{v\in{V}_{G}}{d}_{G}(v){\bm{f}}(v)^{2}}$
$\displaystyle=\frac{\sum_{v\in{V}_{G}}{d}_{G}(v){\bm{f}}(v)^{2}}{\sum_{v\in{V}_{G}}{d}_{G}(v){\bm{f}}(v)^{2}}$
$\displaystyle=1,$

since for every edge $(u,v)\in{E}_{G}$, at most one of ${\bm{f}}(u)$ or
${\bm{f}}(v)$ is not equal to $0$. This cannot be the case, since it is well-
known that the maximum eigenvalue
$\lambda_{n}({\mathbf{D}}_{G}^{-1}{\mathbf{J}}_{G})=2$ and so
$\sum_{i=1}^{n}\lambda_{i}({\mathbf{D}}_{G}^{-1}{\mathbf{J}}_{G})\geq(n-1)+2=n+1$
which contradicts the fact that the trace
$\mathrm{tr}({\mathbf{D}}_{G}^{-1}{\mathbf{J}}_{G})$ is equal to $n$. This
proves the final statement of the lemma. ∎

####  7.5.2 Cheeger-type Inequality for Hypergraph Bipartiteness

We now prove some intermediate facts about the new hypergraph operator
${\mathbf{J}}_{H}$. These allow us to show that the operator
${\mathbf{J}}_{H}$ has a well-defined minimum eigenvector, and the
corresponding eigenvalue satisfies a Cheeger-type inequality for hypergraph
bipartiteness. Given a hypergraph ${H}=({V}_{H},{E}_{H},{w})$, any edge
$e\in{E}_{H}$ and weighted measure vector ${\bm{f}}_{t}$, let
$r_{e}^{{S}}\triangleq\max_{v\in{S}_{{\bm{f}}_{t}}(e)}\\{{\bm{r}}(v)\\}$ and
$r_{e}^{{I}}\triangleq\min_{v\in{I}_{{\bm{f}}_{t}}(e)}\\{{\bm{r}}(v)\\}$;
recall that
$c_{{\bm{f}}_{t}}(e)={w}(e)\left\lvert{\Delta}_{{\bm{f}}_{t}}(e)\right\rvert$.

######  Lemma 7.8.

Given a hypergraph ${H}=({V}_{H},{E}_{H},{w})$ and normalised measure vector
${\bm{f}}_{t}$, let

${\bm{r}}=\frac{\mathrm{d}{\bm{f}}_{t}}{\mathrm{d}t}=-{\mathbf{D}}_{H}^{-1}{\mathbf{J}}_{H}{\bm{f}}_{t}.$

Then, it holds that

$\left\|{\bm{r}}\right\|_{w}^{2}=-\sum_{e\in{E}}{w}(e){\Delta}_{{\bm{f}}_{t}}(e)\left(r_{e}^{{S}}+r_{e}^{{I}}\right).$

###### Proof.

Let ${P}\subset{V}$ be one of the densest vertex sets defined with respect to
the solution of the linear program (7.5). By the description of Algorithm 2,
we have ${\bm{r}}(u)=\delta({P})$ for every $u\in{P}$, and therefore

$\displaystyle\sum_{u\in{P}}{d}(u){\bm{r}}(u)^{2}$
$\displaystyle=\mathrm{vol}({P})\cdot\delta({P})^{2}$
$\displaystyle=\left(c_{{\bm{f}}_{t}}\left(\mathcal{S}_{{U},{P}}^{+}\right)+c_{{\bm{f}}_{t}}\left(\mathcal{I}_{{U},{P}}^{+}\right)-c_{{\bm{f}}_{t}}\left(\mathcal{S}_{{U},{P}}^{-}\right)-c_{{\bm{f}}_{t}}\left(\mathcal{I}_{{U},{P}}^{-}\right)\right)\cdot\delta({P})$
$\displaystyle=\left(\sum_{e\in\mathcal{S}_{{U},{P}}^{+}}c_{{\bm{f}}_{t}}(e)+\sum_{e\in\mathcal{I}_{{U},{P}}^{+}}c_{{\bm{f}}_{t}}(e)-\sum_{e\in\mathcal{S}_{{U},{P}}^{-}}c_{{\bm{f}}_{t}}(e)-\sum_{e\in\mathcal{I}_{{U},{P}}^{-}}c_{{\bm{f}}_{t}}(e)\right)\cdot\delta({P})$
$\displaystyle=\sum_{e\in\mathcal{S}_{{U},{P}}^{+}}c_{{\bm{f}}_{t}}(e)\cdot
r_{e}^{{S}}+\sum_{e\in\mathcal{I}_{{U},{P}}^{+}}c_{{\bm{f}}_{t}}(e)\cdot
r_{e}^{{I}}-\sum_{e\in\mathcal{S}_{{U},{P}}^{-}}c_{{\bm{f}}_{t}}(e)\cdot
r_{e}^{{S}}-\sum_{e\in\mathcal{I}_{{U},{P}}^{-}}c_{{\bm{f}}_{t}}(e)\cdot
r_{e}^{{I}}.$

Since each vertex is included in exactly one set ${P}$ and each edge appears
either in one each of $\mathcal{S}_{{U},{P}}^{+}$ and
$\mathcal{I}_{{U},{P}}^{+}$ or in one each of $\mathcal{S}_{{U},{P}}^{-}$ and
$\mathcal{I}_{{U},{P}}^{-}$, it holds that

$\displaystyle\|{\bm{r}}\|^{2}_{w}$
$\displaystyle=\sum_{v\in{V}}{d}(v){\bm{r}}(v)^{2}$
$\displaystyle=\sum_{{P}}\sum_{v\in{P}}{d}(v){\bm{r}}(v)^{2}$
$\displaystyle=\sum_{{P}}\left(\sum_{e\in\mathcal{S}_{{U},{P}}^{+}}c_{{\bm{f}}_{t}}(e)\cdot
r_{e}^{S}+\sum_{e\in\mathcal{I}_{{U},{P}}^{+}}c_{{\bm{f}}_{t}}(e)\cdot
r_{e}^{{I}}-\sum_{e\in\mathcal{S}_{{U},{P}}^{-}}c_{{\bm{f}}_{t}}(e)\cdot
r_{e}^{S}-\sum_{e\in\mathcal{I}_{{U},{P}}^{-}}c_{{\bm{f}}_{t}}(e)\cdot
r_{e}^{{I}}\right)$
$\displaystyle=-\sum_{e\in{E}}{w}(e){\Delta}_{{\bm{f}}_{t}}(e)\left(r_{e}^{S}+r_{e}^{{I}}\right),$

which proves the lemma. ∎

Next, we define $\gamma_{1}=\min_{\bm{f}}D({\bm{f}})$ and show that any vector
${\bm{f}}$ that satisfies $\gamma_{1}=D({\bm{f}})$ is an eigenvector of
${\mathbf{J}}_{H}$ with eigenvalue $\gamma_{1}$. We start by showing that the
Raleigh quotient of the new operator is equivalent to the discrepancy ratio of
the hypergraph.

######  Lemma 7.9.

For any hypergraph ${H}$ and vector ${\bm{f}}_{t}\in\mathbb{R}^{n}$, it holds
that $D({\bm{f}}_{t})=R_{{\mathbf{J}}_{H}}({\bm{f}}_{t})$.

###### Proof.

Since
${\bm{f}}_{t}^{\intercal}{\mathbf{D}}_{H}{\bm{f}}_{t}=\sum_{v\in{V}}{d}(v){\bm{f}}_{t}(v)^{2}$,
it is sufficient to show that

${\bm{f}}_{t}^{\intercal}{\mathbf{J}}_{H}{\bm{f}}_{t}=\sum_{e\in{E}_{H}}{w}(e)\left(\max_{u\in
e}{\bm{f}}_{t}(u)+\min_{v\in e}{\bm{f}}_{t}(v)\right)^{2}.$

Recall that for some graph ${G}_{t}$,
${\mathbf{J}}_{H}={\mathbf{D}}_{{G}_{t}}+{\mathbf{A}}_{{G}_{t}}$. Then, we
have that

$\displaystyle{\bm{f}}_{t}^{\intercal}{\mathbf{J}}_{H}{\bm{f}}_{t}$
$\displaystyle={\bm{f}}_{t}^{\intercal}({\mathbf{D}}_{{G}_{t}}+{\mathbf{A}}_{{G}_{t}}){\bm{f}}_{t}$
$\displaystyle=\sum_{(u,v)\in{E}_{G}}{w}_{G}(u,v)({\bm{f}}_{t}(u)+{\bm{f}}_{t}(v))^{2}$
$\displaystyle=\sum_{e\in{E}_{H}}\left(\sum_{(u,v)\in{S}_{{\bm{f}}_{t}}(e)\times{I}_{{\bm{f}}_{t}}(e)}{w}_{{G}_{t}}(u,v)({\bm{f}}_{t}(u)+{\bm{f}}_{t}(v))^{2}\right)$
$\displaystyle=\sum_{e\in{E}_{H}}{w}(e)\left(\max_{u\in
e}{\bm{f}}_{t}(u)+\min_{v\in e}{\bm{f}}_{t}(v)\right)^{2},$

which follows since the graph ${G}_{t}$ is constructed by splitting the weight
of each hyperedge $e\in{E}_{H}$ between the edges
${S}_{{\bm{f}}_{t}}(e)\times{I}_{{\bm{f}}_{t}}(e)$. ∎

######  Lemma 7.10.

For a hypergraph ${H}$, operator ${\mathbf{J}}_{H}$, and vector
${\bm{f}}_{t}$, the following statements hold:

  1. 1.

$\frac{\mathrm{d}}{\mathrm{d}t}\left\|{\bm{f}}_{t}\right\|_{w}^{2}=-2{\bm{f}}_{t}^{\intercal}{\mathbf{J}}_{H}{\bm{f}}_{t}$;

  2. 2.

$\frac{\mathrm{d}}{\mathrm{d}t}({\bm{f}}_{t}^{\intercal}{\mathbf{J}}_{H}{\bm{f}}_{t})=-2\left\|{\mathbf{D}}_{H}^{-1}{\mathbf{J}}_{H}{\bm{f}}_{t}\right\|_{w}^{2}$;

  3. 3.

$\frac{\mathrm{d}}{\mathrm{d}t}R({\bm{f}}_{t})\leq 0$ with equality if and
only if
${\mathbf{D}}_{H}^{-1}{\mathbf{J}}_{H}{\bm{f}}_{t}\in\mathrm{span}({\bm{f}}_{t})$.

###### Proof.

By definition, we have that

$\displaystyle\frac{\mathrm{d}\left\|{\bm{f}}_{t}\right\|_{w}^{2}}{\mathrm{d}t}$
$\displaystyle=\frac{\mathrm{d}}{\mathrm{d}t}\sum_{v\in{V}}{d}(v){\bm{f}}_{t}(v)^{2}$
$\displaystyle=\sum_{v\in{V}}{d}(v)\cdot\frac{\mathrm{d}{\bm{f}}_{t}(v)^{2}}{\mathrm{d}t}$
$\displaystyle=\sum_{v\in{V}}{d}(v)\cdot\frac{\mathrm{d}{\bm{f}}_{t}(v)^{2}}{\mathrm{d}{\bm{f}}_{t}(v)}\frac{\mathrm{d}{\bm{f}}_{t}(v)}{\mathrm{d}t}$
$\displaystyle=2\sum_{v\in{V}}{d}(v){\bm{f}}_{t}(v)\cdot\frac{\mathrm{d}{\bm{f}}_{t}(v)}{\mathrm{d}t}$
$\displaystyle=2\left\langle{\bm{f}}_{t},\frac{\mathrm{d}{\bm{f}}_{t}}{\mathrm{d}t}\right\rangle_{w}=-2\left\langle{\bm{f}}_{t},{\mathbf{D}}_{H}^{-1}{\mathbf{J}}_{H}{\bm{f}}_{t}\right\rangle_{w},$

which proves the first statement.

For the second statement, by Lemma 7.9 we have

${\bm{f}}_{t}^{\intercal}{\mathbf{J}}_{H}{\bm{f}}_{t}=\sum_{e\in{E}}{w}(e)\left(\max_{u\in
e}{\bm{f}}_{t}(u)+\min_{v\in e}{\bm{f}}_{t}(v)\right)^{2},$

and therefore

$\displaystyle\frac{\mathrm{d}}{\mathrm{d}t}{\bm{f}}_{t}^{\intercal}{\mathbf{J}}_{H}{\bm{f}}_{t}$
$\displaystyle=\frac{\mathrm{d}}{\mathrm{d}t}\sum_{e\in{E}}{w}(e)\left(\max_{u\in
e}{\bm{f}}_{t}(u)+\min_{v\in e}{\bm{f}}_{t}(v)\right)^{2}$
$\displaystyle=2\sum_{e\in{E}}{w}(e){\Delta}_{{\bm{f}}_{t}}(e)\cdot\frac{\mathrm{d}}{\mathrm{d}t}\left(\max_{u\in
e}{\bm{f}}_{t}(u)+\min_{v\in e}{\bm{f}}_{t}(v)\right)$
$\displaystyle=2\sum_{e\in{E}}{w}(e){\Delta}_{{\bm{f}}_{t}}(e)\cdot\left(r_{e}^{{S}}+r_{e}^{{I}}\right),$
(7.15)

where the last equality holds by the way that all the vertices receive their
${\bm{r}}$-values by the algorithm and the definitions of $r_{e}^{{S}}$ and
$r_{e}^{{I}}$. On the other side, by definition
${\bm{r}}=-{\mathbf{D}}_{H}^{-1}{\mathbf{J}}_{H}{\bm{f}}_{t}$ and so by Lemma
7.8,

$\left\|{\mathbf{D}}_{H}^{-1}{\mathbf{J}}_{H}{\bm{f}}_{t}\right\|_{w}^{2}=\left\|{\bm{r}}\right\|_{w}^{2}=-\sum_{e\in{E}}{w}(e){\Delta}_{{\bm{f}}_{t}}(e)\left(r_{e}^{{S}}+r_{e}^{{I}}\right).$
(7.16)

By combining (7.15) with (7.16), we have the second statement.

For the third statement, notice that we can write
${\bm{f}}_{t}^{\intercal}{\mathbf{J}}_{H}{\bm{f}}_{t}$ as
$\left\langle{\bm{f}}_{t},{\mathbf{D}}_{H}^{-1}{\mathbf{J}}_{H}{\bm{f}}_{t}\right\rangle_{w}$.
Then, we have that

$\displaystyle\frac{\mathrm{d}}{\mathrm{d}t}\frac{\langle{\bm{f}}_{t},{\mathbf{D}}_{H}^{-1}{\mathbf{J}}_{H}{\bm{f}}_{t}\rangle_{w}}{\left\|{\bm{f}}_{t}\right\|_{w}^{2}}$
$\displaystyle=\frac{1}{\left\|{\bm{f}}_{t}\right\|_{w}^{2}}\cdot\frac{\mathrm{d}~{}\langle{\bm{f}}_{t},{\mathbf{D}}_{H}^{-1}{\mathbf{J}}_{H}{\bm{f}}_{t}\rangle_{w}}{\mathrm{d}t}-\langle{\bm{f}}_{t},{\mathbf{D}}_{H}^{-1}{\mathbf{J}}_{H}{\bm{f}}_{t}\rangle_{w}\cdot\frac{1}{\left\|{\bm{f}}_{t}\right\|_{w}^{4}}\frac{\mathrm{d}~{}\left\|{\bm{f}}_{t}\right\|^{2}_{w}}{\mathrm{d}t}$
$\displaystyle=-\frac{1}{\left\|{\bm{f}}_{t}\right\|_{w}^{4}}\cdot\left(2\cdot\left\|{\bm{f}}_{t}\right\|_{w}^{2}\cdot\left\|{\mathbf{D}}_{H}^{-1}{\mathbf{J}}_{H}{\bm{f}}_{t}\right\|_{w}^{2}+\left\langle{\bm{f}}_{t},{\mathbf{D}}_{H}^{-1}{\mathbf{J}}_{H}{\bm{f}}_{t}\right\rangle_{w}\cdot\frac{\mathrm{d}~{}\left\|{\bm{f}}_{t}\right\|^{2}_{w}}{\mathrm{d}t}\right)$
$\displaystyle=-\frac{2}{\left\|{\bm{f}}_{t}\right\|_{w}^{4}}\cdot\left(\left\|{\bm{f}}_{t}\right\|_{w}^{2}\cdot\left\|{\mathbf{D}}_{H}^{-1}{\mathbf{J}}_{H}{\bm{f}}_{t}\right\|_{w}^{2}-\left\langle{\bm{f}}_{t},{\mathbf{D}}_{H}^{-1}{\mathbf{J}}_{H}{\bm{f}}_{t}\right\rangle_{w}^{2}\right)$
$\displaystyle\leq 0,$

where the last inequality holds by the Cauchy-Schwarz inequality on the inner
product $\left\langle\cdot,\cdot\right\rangle_{w}$ with the equality if and
only if
${\mathbf{D}}_{H}^{-1}{\mathbf{J}}_{H}{\bm{f}}_{t}\in\mathrm{span}({\bm{f}}_{t})$.
∎

This allows us to establish the following key lemma.

######  Lemma 7.11.

For any hypergraph ${H}$, $\gamma_{1}=\min_{{\bm{f}}}D({\bm{f}})$ is an
eigenvalue of ${\mathbf{J}}_{H}$ and any minimiser ${\bm{f}}$ is its
corresponding eigenvector.

###### Proof.

By Lemma 7.9, it holds that $R({\bm{f}})=D({\bm{f}})$ for any
${\bm{f}}\in\mathbb{R}^{n}$. When ${\bm{f}}$ is a minimiser of $D({\bm{f}})$,
it holds that

$\frac{\mathrm{d}R({\bm{f}})}{\mathrm{d}t}=0,$

which implies by Lemma 7.10 that
${\mathbf{D}}_{H}^{-1}{\mathbf{J}}_{H}{\bm{f}}\in\mathrm{span}({\bm{f}})$ and
proves that ${\bm{f}}$ is an eigenvector. ∎

We are now ready to prove a Cheeger-type inequality for our operator and the
hypergraph bipartiteness. We first show that the minimum eigenvalue of
${\mathbf{J}}_{H}$ is at most twice the hypergraph bipartiteness.

######  Lemma 7.12.

Given a hypergraph ${H}=({V}_{H},{E}_{H})$ with sets ${L},{R}\subset{V}_{H}$
such that ${\beta}({L},{R})={\beta}$, it holds that

$\gamma_{1}\leq 2{\beta}$

where $\gamma_{1}$ is the smallest eigenvalue of ${\mathbf{J}}_{H}$.

###### Proof.

Let ${\bm{\chi}}_{{L},{R}}\in\\{-1,0,1\\}^{n}$ be the indicator vector of the
cut ${L},{R}$ such that

${\bm{\chi}}_{{L},{R}}(u)=\left\\{\begin{array}[]{lll}1&\mbox{if }u\in{L}\\\
-1&\mbox{if }u\in{R}\\\ 0&\mbox{otherwise}\end{array}\right..$

Then, by Lemma 7.9, the Rayleigh quotient is given by

$\displaystyle R_{{\mathbf{J}}_{H}}\left({\bm{\chi}}_{{L},{R}}\right)$
$\displaystyle=\frac{\sum_{e\in{E}}{w}(e)\left(\max_{u\in
e}{\bm{\chi}}_{{L},{R}}(u)+\min_{v\in
e}{\bm{\chi}}_{{L},{R}}(v)\right)^{2}}{\sum_{v\in{V}}{d}(v){\bm{\chi}}_{{L},{R}}(v)^{2}}$
$\displaystyle=\frac{4{w}({L}|\overline{{L}})+4{w}({R}|\overline{{R}})+{w}({L},\overline{{L}\cup{R}}|{R})+{w}({R},\overline{{L}\cup{R}}|{L})}{\mathrm{vol}({L}\cup{R})}$
$\displaystyle\leq 2{\beta}({L},{R}),$

which completes the proof since
$\gamma_{1}=\min_{{\bm{f}}}R_{{\mathbf{J}}_{H}}({\bm{f}})$ by Lemma 7.11. ∎

The proof of the other direction of the Cheeger-type inequality is more
involved, and forms the basis of the second claim in Theorem 7.1.

######  Lemma 7.13.

For any hypergraph ${H}=({V},{E},{w})$, let ${\mathbf{J}}_{H}$ be the operator
defined with respect to ${H}$, and
$\gamma_{1}=\min_{{\bm{f}}}D({\bm{f}})=\min_{{\bm{f}}}R({\bm{f}})$ be the
minimum eigenvalue of ${\mathbf{D}}_{H}^{-1}{\mathbf{J}}_{H}$. Then, there are
disjoint sets ${L},{R}\subset{V}$ such that

${\beta}({L},{R})\leq\sqrt{2\gamma_{1}}.$

###### Proof.

Let ${\bm{f}}\in\mathbb{R}^{n}$ be the vector such that
$D({\bm{f}})=\gamma_{1}$. For any threshold $t\in[0,\max_{u}{\bm{f}}(u)^{2}]$,
define ${\bm{x}}_{t}$ such that

${\bm{x}}_{t}(u)=\left\\{\begin{array}[]{lll}1&\mbox{if
}{\bm{f}}(u)\geq\sqrt{t}\\\ -1&\mbox{if }{\bm{f}}(u)\leq-\sqrt{t}\\\
0&\mbox{otherwise}\end{array}\right..$

We show that choosing $t\in\left[0,\max_{u}{\bm{f}}(u)^{2}\right]$ uniformly
at random gives

$\mathbb{E}\left[\sum_{e\in{E}_{H}}{w}(e)\left\lvert\max_{u\in
e}{\bm{x}}_{t}(u)+\min_{v\in
e}{\bm{x}}_{t}(v)\right\rvert\right]\leq\sqrt{2\gamma_{1}}\cdot\mathbb{E}\left[\sum_{v\in{V}_{H}}{d}(v)\left\lvert{\bm{x}}_{t}(v)\right\rvert\right].$
(7.17)

Notice that every such ${\bm{x}}_{t}$ defines disjoints vertex sets ${L}$ and
${R}$ that satisfy

${\beta}({L},{R})=\frac{\sum_{e\in{E}_{H}}{w}(e)\left\lvert\max_{u\in
e}{\bm{x}}_{t}(u)+\min_{v\in
e}{\bm{x}}_{t}(v)\right\rvert}{\sum_{v\in{V}_{H}}{d}(v)\left\lvert{\bm{x}}_{t}(v)\right\rvert}.$

Hence, (7.17) would imply that there is some ${\bm{x}}_{t}$ such that the
disjoint ${L},{R}$ defined by ${\bm{x}}_{t}$ would satisfy

$\sum_{e\in{E}_{H}}{w}(e)\left\lvert\max_{u\in e}{\bm{x}}_{t}(u)+\min_{v\in
e}{\bm{x}}_{t}(v)\right\rvert\leq\sqrt{2\gamma_{1}}\cdot\sum_{v\in{V}_{H}}{d}(v)\left\lvert{\bm{x}}_{t}(v)\right\rvert,$

which implies that

${\beta}({L},{R})\leq\sqrt{2\gamma_{1}}.$

Hence, it suffices to prove (7.17). We assume without loss of generality that
$\max_{u}\left\\{{\bm{f}}(u)^{2}\right\\}=1$, so $t$ is chosen uniformly from
$[0,1]$. First of all, we have that

$\displaystyle\mathbb{E}\left[\sum_{v\in{V}_{H}}{d}(v)\left\lvert{\bm{x}}_{t}(v)\right\rvert\right]=\sum_{v\in{V}_{H}}{d}(v)\mathbb{E}\left[\left\lvert{\bm{x}}_{t}(v)\right\rvert\right]=\sum_{v\in{V}_{H}}{d}(v){\bm{f}}(v)^{2}.$

To analyse the left-hand side of (7.17), we focus on a particular edge
$e\in{E}_{H}$. Let $a_{e}=\max_{u\in e}{\bm{f}}(u)$ and $b_{e}=\min_{v\in
e}{\bm{f}}(v)$. We drop the subscript $e$ when it is clear from context. We
show that

$\mathbb{E}\left[\left\lvert\max_{u\in e}{\bm{x}}_{t}(u)+\min_{v\in
e}{\bm{x}}_{t}(v)\right\rvert\right]\leq\left\lvert
a_{e}+b_{e}\right\rvert(\left\lvert a_{e}\right\rvert+\left\lvert
b_{e}\right\rvert).$ (7.18)

  1. 1.

Suppose $\mathrm{sign}(a_{e})=\mathrm{sign}(b_{e})$. Our analysis is by case
distinction:

     * •

$\left\lvert\max_{u\in e}{\bm{x}}_{t}(u)+\min_{v\in
e}{\bm{x}}_{t}(v)\right\rvert=2$ with probability $\min(a_{e}^{2},b_{e}^{2})$;

     * •

$\left\lvert\max_{u\in e}{\bm{x}}_{t}(u)+\min_{v\in
e}{\bm{x}}_{t}(v)\right\rvert=1$ with probability $\left\lvert
a_{e}^{2}-b_{e}^{2}\right\rvert$;

     * •

$\left\lvert\max_{u\in e}{\bm{x}}_{t}(u)+\min_{v\in
e}{\bm{x}}_{t}(v)\right\rvert=0$ with probability
$1-\max(a_{e}^{2},b_{e}^{2})$.

Assume without loss of generality that
$a_{e}^{2}=\min\left(a_{e}^{2},b_{e}^{2}\right)$. Then, it holds hat

$\mathbb{E}\left[\left\lvert\max_{u\in e}{\bm{x}}(u)+\min_{v\in
e}{\bm{x}}(v)\right\rvert\right]=2a_{e}^{2}+\left\lvert
a_{e}^{2}-b_{e}^{2}\right\rvert=a_{e}^{2}+b_{e}^{2}\leq\left\lvert
a_{e}+b_{e}\right\rvert(\left\lvert a_{e}\right\rvert+\left\lvert
b_{e}\right\rvert).$

  2. 2.

Suppose $\mathrm{sign}(a_{e})\neq\mathrm{sign}(b_{e})$. Our analysis is by
case distinction:

     * •

$\left\lvert\max_{u\in e}{\bm{x}}_{t}(u)+\min_{v\in
e}{\bm{x}}_{t}(v)\right\rvert=2$ with probability $0$;

     * •

$\left\lvert\max_{u\in e}{\bm{x}}_{t}(u)+\min_{v\in
e}{\bm{x}}_{t}(v)\right\rvert=1$ with probability $\left\lvert
a_{e}^{2}-b_{e}^{2}\right\rvert$;

     * •

$\left\lvert\max_{u\in e}{\bm{x}}_{t}(u)+\min_{v\in
e}{\bm{x}}_{t}(v)\right\rvert=0$ with probability $\min(a_{e}^{2},b_{e}^{2})$.

Assume without loss of generality that
$a_{e}^{2}=\min\left(a_{e}^{2},b_{e}^{2}\right)$. Then, it holds that

$\displaystyle\mathbb{E}\left[\left\lvert\max_{u\in
e}{\bm{x}}_{t}(u)+\min_{v\in e}{\bm{x}}_{t}(v)\right\rvert\right]$
$\displaystyle=\left\lvert a_{e}^{2}-b_{e}^{2}\right\rvert$
$\displaystyle=(\left\lvert a_{e}\right\rvert-\left\lvert
b_{e}\right\rvert)(\left\lvert a_{e}\right\rvert+\left\lvert
b_{e}\right\rvert)$ $\displaystyle=\left\lvert
a_{e}+b_{e}\right\rvert(\left\lvert a_{e}\right\rvert+\left\lvert
b_{e}\right\rvert),$

where the final equality follows because $a_{e}$ and $b_{e}$ have different
signs.

These two cases establish (7.18). Now, we have that

$\displaystyle\mathbb{E}\left[\sum_{e\in{E}_{H}}{w}(e)\left\lvert\max_{u\in
e}{\bm{x}}_{t}(u)+\min_{v\in e}{\bm{x}}_{t}(v)\right\rvert\right]$
$\displaystyle\leq\sum_{e\in{E}_{H}}{w}(e)\left\lvert
a_{e}+b_{e}\right\rvert(\left\lvert a_{e}\right\rvert+\left\lvert
b_{e}\right\rvert)$
$\displaystyle\leq\sqrt{\sum_{e\in{E}_{H}}{w}(e)\left\lvert
a_{e}+b_{e}\right\rvert^{2}}\sqrt{\sum_{e\in{E}_{H}}{w}(e)(\left\lvert
a_{e}\right\rvert+\left\lvert b_{e}\right\rvert)^{2}}$
$\displaystyle=\sqrt{\sum_{e\in{E}_{H}}{w}(e)\left(\max_{u\in
e}{\bm{f}}(u)+\min_{v\in
e}{\bm{f}}(v)\right)^{2}}\sqrt{\sum_{e\in{E}_{H}}{w}(e)(\left\lvert
a_{e}\right\rvert+\left\lvert b_{e}\right\rvert)^{2}}.$

By our assumption that ${\bm{f}}$ is the eigenvector corresponding to the
eigenvalue $\gamma_{1}$, it holds that

$\sum_{e\in{E}_{H}}{w}(e)\left(\max_{u\in e}{\bm{f}}(u)+\min_{v\in
e}{\bm{f}}(v)\right)^{2}\leq\gamma_{1}\sum_{v\in{V}_{H}}{d}(v){\bm{f}}(v)^{2}.$

On the other side, we have that

$\sum_{e\in{E}_{H}}{w}(e)(\left\lvert a_{e}\right\rvert+\left\lvert
b_{e}\right\rvert)^{2}\leq 2\sum_{e\in{E}_{H}}{w}(e)(\left\lvert
a_{e}\right\rvert^{2}+\left\lvert b_{e}\right\rvert^{2})\leq
2\sum_{v\in{V}_{H}}{d}(v){\bm{f}}(v)^{2}.$

This gives us that

$\displaystyle\mathbb{E}\left[\sum_{e\in{E}_{H}}{w}(e)\left\lvert\max_{u\in
e}{\bm{x}}(u)+\min_{v\in e}{\bm{x}}(v)\right\rvert\right]$
$\displaystyle\leq\sqrt{2\gamma_{1}}\sum_{v\in{V}_{H}}{d}(v){\bm{f}}(v)^{2}$
$\displaystyle=\sqrt{2\gamma_{1}}\cdot\mathbb{E}\left[\sum_{v\in{V}_{H}}{d}(v)\left\lvert{\bm{x}}(v)\right\rvert\right],$

which proves the statement. ∎

Now, we are able to combine these results to prove Theorem 7.1.

###### Proof of Theorem 7.1..

The first statement of the theorem follows by setting the starting vector
${\bm{f}}_{0}$ of the diffusion to be the minimum eigenvector of the clique
graph ${G}$. By Lemma 7.7, we have that
$R_{{\mathbf{J}}_{H}}({\bm{f}}_{0})\leq\lambda_{1}({\mathbf{D}}_{G}^{-1}{\mathbf{J}}_{G})$
and the inequality is strict if $\min_{e\in{E}_{H}}\mathrm{rank}(e)>2$. Then,
Theorem 7.2 shows that the diffusion process converges to an eigenvector and
the Rayleigh quotient only decreases during convergence, and so the inequality
holds. The algorithm runs in polynomial time, since by Theorem 7.2 the
diffusion process converges in polynomial time and each step of Algorithm 1
can be computed in polynomial time using a standard algorithm for solving
linear programs.

The second statement is a restatement of Lemma 7.13. The sweep set algorithm
runs in polynomial time, since there are $n$ different sweep sets and
computing the hypergraph bipartiteness for each one also takes polynomial
time. ∎

###  7.6 Further Study of the Hypergraph Laplacian Spectrum

In this section, we further study the spectrum of the operators
${\mathbf{L}}_{H}$ and ${\mathbf{J}}_{H}$. We first demonstrate that there
exist infinite families of hypergraphs $\\{H\\}$ for which the number of
eigenvectors of ${\mathbf{L}}_{H}$ and ${\mathbf{J}}_{H}$ exceeds the number
of vertices. We then show that finding the eigenvector of ${\mathbf{J}}_{H}$
corresponding to its smallest eigenvalue is $\mathsf{NP}$-hard.

####  7.6.1 Discussion on the Number of Eigenvectors of ${\mathbf{J}}_{H}$ and
${\mathbf{L}}_{H}$

We now investigate the spectrum of the non-linear hypergraph Laplacian
operator and our new operator ${\mathbf{J}}_{H}$ by considering some example
hypergraphs. In particular, we show that the hypergraph Laplacian
${\mathbf{L}}_{H}$ can have more than $2$ eigenvalues, which answers the
following open question posed by Chan et al. [CLTZ18].

> … apart from ${\bm{f}}_{1}$, the Laplacian has another eigenvector
> ${\bm{f}}_{2}$ … it is not clear if ${\mathbf{L}}$ has any other
> eigenvalues. We leave as an open problem the task of investigating if other
> eigenvalues exist.  (Chan et al. [CLTZ18])

Furthermore, we show that the number of eigenvectors of the new operator
${\mathbf{J}}_{H}$ can be exponential in the number of vertices.

#####  ${\mathbf{L}}_{H}$ Can Have More Than $2$ Eigenvalues

Similar to our new operator ${\mathbf{J}}_{H}$, for some vector ${\bm{f}}$,
the operator ${\mathbf{L}}_{H}$ behaves like the graph Laplacian
${\mathbf{L}}_{G}={\mathbf{D}}_{G}-{\mathbf{A}}_{G}$ for some graph ${G}$
constructed by splitting the weight of each hyperedge $e$ between the edges in
${S}_{{\bm{f}}}(e)\times{I}_{{\bm{f}}}(e)$. We refer the reader to [CLTZ18]
for the full details of this construction.

$\xrightarrow{}$$\begin{bmatrix}{\mathbf{B}}_{1}&{\mathbf{0}}&{\mathbf{0}}\\\
{\mathbf{0}}&{\mathbf{B}}_{2}&{\mathbf{0}}\\\
{\mathbf{0}}&{\mathbf{0}}&{\mathbf{B}}_{3}\end{bmatrix}$$\xrightarrow{}$Graph
${G}$Normalised Laplacian ${\mathbf{N}}$Spectral
Embedding$\xrightarrow{}$$\begin{bmatrix}{\mathbf{B}}_{1}&{\mathbf{C}}_{12}&{\mathbf{C}}_{13}\\\
{\mathbf{C}}_{12}^{\intercal}&{\mathbf{B}}_{2}&{\mathbf{C}}_{23}\\\
{\mathbf{C}}_{13}^{\intercal}&{\mathbf{C}}_{23}^{\intercal}&{\mathbf{B}}_{3}\end{bmatrix}$$\xrightarrow{}$Graph
${G}$Normalised Laplacian ${\mathbf{N}}$Spectral
Embedding$\rightarrow$$v_{1}$$v_{3}$$v_{5}$$v_{4}$$v_{2}$$\rightarrow$$x_{1}=v_{1}$$x_{2}=v_{4}$$x_{3}=v_{5}$${\bm{p}}^{(i)}$${\bm{p}}^{(j)}$$\frac{{\bm{p}}^{(i)}}{\left\|{\bm{p}}^{(i)}\right\|}$$\frac{{\bm{p}}^{(j)}}{\left\|{\bm{p}}^{(j)}\right\|}$${\bm{a}}_{i}$${\bm{a}}_{j}$$\frac{\left\|{\bm{a}}_{i}\right\|}{\left\|{\bm{a}}_{j}\right\|}{\bm{a}}_{j}$$a_{1}$$a_{2}$$a$$b$$c$$d$$\Longrightarrow$$b_{1}$$b_{2}$$c_{1}$$c_{2}$$d_{1}$$d_{2}$$\cdots$$a_{1}$$S$$b_{1}$$c_{1}$$d_{1}$$e_{1}$$f_{1}$$\cdots$$\cdots$$a_{2}$$b_{2}$$c_{2}$$d_{2}$$e_{2}$$f_{2}$$\cdots$$a_{1}$$a_{2}$$a$$b$$c$$d$$\Longrightarrow$$b_{1}$$b_{2}$$c_{1}$$c_{2}$$d_{1}$$d_{2}$$a_{1}$$b_{1}$$a_{2}$$b_{2}$ab$\Longrightarrow$$0.5$$0.5$$0.5$$0.5$$0.5$$0.5$$0.5$$0.5$$0.62$$0.38$$1.0$$0.38$$0.62$$1.0$$1.0$$0.5$$0.25$$0.25$$1.0$$1.0$$0.5$$0.5$$\begin{bmatrix}1\\\
0\\\ 0\\\ 0\\\ 0\\\
0\end{bmatrix}$$\rightarrow$$\rightarrow$$t=0$$t=1$$\begin{bmatrix}0.29\\\
-0.14\\\ -0.14\\\ 0.02\\\ 0.02\\\
0.02\end{bmatrix}$$\rightarrow$$\rightarrow$$t=3$$\begin{bmatrix}0.11\\\
-0.09\\\ -0.09\\\ 0.04\\\ 0.04\\\
0.04\end{bmatrix}$$\rightarrow$$\rightarrow$$t=4$$\begin{bmatrix}0.09\\\
-0.71\\\ -0.71\\\ 0.03\\\ 0.03\\\
0.03\end{bmatrix}$$\rightarrow$$\rightarrow$$t=23$$\begin{bmatrix}0.03\\\
-0.03\\\ -0.03\\\ 0.03\\\ -0.03\\\
-0.03\end{bmatrix}$$v_{1}$$v_{2}$$v_{3}$$v_{5}$$v_{4}$${\bm{f}}_{t}$${\bm{f}}_{t}$${\bm{f}}_{t}$${\bm{f}}_{t}$${\bm{f}}_{t}$$v_{6}$${L}$${R}$Hypergraph
${H}_{1}$${L}$${R}$Hypergraph
${H}_{2}$$\vdots$$\vdots$$\vdots$$\vdots$$\vdots$$\vdots$$\vdots$$\vdots$$\vdots$$-2$$-2$$0$$1$$3$$1$Hyperedge
$e$${I}_{{\bm{f}}}(e)$${S}_{{\bm{f}}}(e)$s$T$t$\mathcal{E}_{T}^{+}$$\mathcal{E}_{T}^{-}$$\vdots$$c(e)$$c(e)$$d(v)\delta(T)$$\infty$s$T^{\prime}$t$\mathcal{E}_{T^{\prime}}^{+}$$\mathcal{E}_{T^{\prime}}^{-}$$\vdots$$c(e)$$c(e)$$d(v)\delta(T)$$\infty$$v_{1}$$v_{2}$$v_{3}$$H$$v_{1}$$v_{2}$$v_{3}$$G_{1}$$v_{1}$$v_{2}$$v_{3}$$G_{2}$$v_{1}$$v_{2}$$v_{3}$$G_{3}$$\frac{1}{3}$$\frac{1}{3}$$\frac{1}{3}$$\frac{1}{2}$$\frac{1}{2}$$1$

Figure 7.5: Given the hypergraph ${H}$, there are three graphs ${G}_{1}$,
${G}_{2}$, and ${G}_{3}$ which correspond to eigenvalues of the hypergraph
Laplacian ${\mathbf{L}}_{H}$.

Now, with reference to Figure 7.5, we consider the simple hypergraph ${H}$
where ${V}_{H}=\\{v_{1},v_{2},v_{3}\\}$ and
${E}_{H}=\\{\\{v_{1},v_{2},v_{3}\\}\\}$. Letting
${\bm{f}}_{1}=[1,1,1]^{\intercal}$, notice that the graph ${G}_{1}$ in Figure
7.5 is the graph for which ${\mathbf{L}}_{H}{\bm{f}}_{1}$ is equivalent to
${\mathbf{L}}_{{G}_{1}}{\bm{f}}_{1}$. In this case,

${\mathbf{L}}_{{G}_{1}}=\begin{bmatrix}\frac{2}{3}&-\frac{1}{3}&-\frac{1}{3}\\\
-\frac{1}{3}&\frac{2}{3}&-\frac{1}{3}\\\
-\frac{1}{3}&-\frac{1}{3}&\frac{2}{3}\end{bmatrix}$

and we have

${\mathbf{L}}_{H}{\bm{f}}_{1}={\mathbf{L}}_{{G}_{1}}{\bm{f}}_{1}=[0,0,0]^{\intercal},$

which shows that ${\bm{f}}_{1}$ is the trivial eigenvector of
${\mathbf{L}}_{H}$ with eigenvalue $0$.

Now, consider ${\bm{f}}_{2}=[1,-2,1]^{\intercal}$. In this case, ${G}_{2}$
shown in Figure 7.5 is the graph for which ${\mathbf{L}}_{H}{\bm{f}}_{2}$ is
equivalent to ${\mathbf{L}}_{{G}_{2}}{\bm{f}}_{2}$. Then, we have

${\mathbf{L}}_{{G}_{2}}=\begin{bmatrix}\frac{1}{2}&-\frac{1}{2}&0\\\
-\frac{1}{2}&1&-\frac{1}{2}\\\ 0&-\frac{1}{2}&\frac{1}{2}\end{bmatrix}$

and

${\mathbf{L}}_{H}{\bm{f}}_{2}={\mathbf{L}}_{{G}_{2}}{\bm{f}}_{2}=\left[\frac{3}{2},-3,\frac{3}{2}\right]^{\intercal}$

which shows that ${\bm{f}}_{2}$ is an eigenvector of ${\mathbf{L}}_{H}$ with
eigenvalue $3/2$.

Finally, we consider ${\bm{f}}_{3}=[1,-1,0]$ and notice that ${G}_{3}$ is the
graph such that ${\mathbf{L}}_{H}{\bm{f}}_{3}={\mathbf{L}}_{G}{\bm{f}}_{3}$.
Then,

${\mathbf{L}}_{{G}_{3}}=\begin{bmatrix}\frac{1}{2}&-\frac{1}{2}&0\\\
-\frac{1}{2}&\frac{1}{2}&0\\\ 0&0&0\end{bmatrix}$

and

${\mathbf{L}}_{H}{\bm{f}}_{3}={\mathbf{L}}_{{G}_{3}}{\bm{f}}_{3}=\left[2,-2,0\right]^{\intercal}$

which shows that ${\bm{f}}_{3}$ is an eigenvector of ${\mathbf{L}}_{H}$ with
eigenvalue $2$.

Through an exhaustive search of the other possible constructed graphs on
$\\{v_{1},v_{2},v_{3}\\}$, we find that these are the only eigenvalues of
${\mathbf{L}}_{H}$. By the symmetries of ${\bm{f}}_{2}$ and ${\bm{f}}_{3}$,
this means that the operator ${\mathbf{L}}_{H}$ has a total of $7$ different
eigenvectors and $3$ distinct eigenvalues. It is useful to point out that,
since the ${\mathbf{L}}_{H}$ operator is non-linear, a linear combination of
eigenvectors with the same eigenvalue is _not_ , in general, an eigenvector.
Additionally, notice that the constructions of ${\bm{f}}_{1}$ and
${\bm{f}}_{2}$ can be generalised to hypergraphs with more than $3$ vertices,
demonstrating that the number of eigenvectors of ${\mathbf{L}}_{H}$ can grow
faster than the number of vertices.

#####  ${\mathbf{J}}_{H}$ Can Have an Exponential Number of Eigenvectors

$\xrightarrow{}$$\begin{bmatrix}{\mathbf{B}}_{1}&{\mathbf{0}}&{\mathbf{0}}\\\
{\mathbf{0}}&{\mathbf{B}}_{2}&{\mathbf{0}}\\\
{\mathbf{0}}&{\mathbf{0}}&{\mathbf{B}}_{3}\end{bmatrix}$$\xrightarrow{}$Graph
${G}$Normalised Laplacian ${\mathbf{N}}$Spectral
Embedding$\xrightarrow{}$$\begin{bmatrix}{\mathbf{B}}_{1}&{\mathbf{C}}_{12}&{\mathbf{C}}_{13}\\\
{\mathbf{C}}_{12}^{\intercal}&{\mathbf{B}}_{2}&{\mathbf{C}}_{23}\\\
{\mathbf{C}}_{13}^{\intercal}&{\mathbf{C}}_{23}^{\intercal}&{\mathbf{B}}_{3}\end{bmatrix}$$\xrightarrow{}$Graph
${G}$Normalised Laplacian ${\mathbf{N}}$Spectral
Embedding$\rightarrow$$v_{1}$$v_{3}$$v_{5}$$v_{4}$$v_{2}$$\rightarrow$$x_{1}=v_{1}$$x_{2}=v_{4}$$x_{3}=v_{5}$${\bm{p}}^{(i)}$${\bm{p}}^{(j)}$$\frac{{\bm{p}}^{(i)}}{\left\|{\bm{p}}^{(i)}\right\|}$$\frac{{\bm{p}}^{(j)}}{\left\|{\bm{p}}^{(j)}\right\|}$${\bm{a}}_{i}$${\bm{a}}_{j}$$\frac{\left\|{\bm{a}}_{i}\right\|}{\left\|{\bm{a}}_{j}\right\|}{\bm{a}}_{j}$$a_{1}$$a_{2}$$a$$b$$c$$d$$\Longrightarrow$$b_{1}$$b_{2}$$c_{1}$$c_{2}$$d_{1}$$d_{2}$$\cdots$$a_{1}$$S$$b_{1}$$c_{1}$$d_{1}$$e_{1}$$f_{1}$$\cdots$$\cdots$$a_{2}$$b_{2}$$c_{2}$$d_{2}$$e_{2}$$f_{2}$$\cdots$$a_{1}$$a_{2}$$a$$b$$c$$d$$\Longrightarrow$$b_{1}$$b_{2}$$c_{1}$$c_{2}$$d_{1}$$d_{2}$$a_{1}$$b_{1}$$a_{2}$$b_{2}$ab$\Longrightarrow$$0.5$$0.5$$0.5$$0.5$$0.5$$0.5$$0.5$$0.5$$0.62$$0.38$$1.0$$0.38$$0.62$$1.0$$1.0$$0.5$$0.25$$0.25$$1.0$$1.0$$0.5$$0.5$$\begin{bmatrix}1\\\
0\\\ 0\\\ 0\\\ 0\\\
0\end{bmatrix}$$\rightarrow$$\rightarrow$$t=0$$t=1$$\begin{bmatrix}0.29\\\
-0.14\\\ -0.14\\\ 0.02\\\ 0.02\\\
0.02\end{bmatrix}$$\rightarrow$$\rightarrow$$t=3$$\begin{bmatrix}0.11\\\
-0.09\\\ -0.09\\\ 0.04\\\ 0.04\\\
0.04\end{bmatrix}$$\rightarrow$$\rightarrow$$t=4$$\begin{bmatrix}0.09\\\
-0.71\\\ -0.71\\\ 0.03\\\ 0.03\\\
0.03\end{bmatrix}$$\rightarrow$$\rightarrow$$t=23$$\begin{bmatrix}0.03\\\
-0.03\\\ -0.03\\\ 0.03\\\ -0.03\\\
-0.03\end{bmatrix}$$v_{1}$$v_{2}$$v_{3}$$v_{5}$$v_{4}$${\bm{f}}_{t}$${\bm{f}}_{t}$${\bm{f}}_{t}$${\bm{f}}_{t}$${\bm{f}}_{t}$$v_{6}$${L}$${R}$Hypergraph
${H}_{1}$${L}$${R}$Hypergraph
${H}_{2}$$\vdots$$\vdots$$\vdots$$\vdots$$\vdots$$\vdots$$\vdots$$\vdots$$\vdots$$-2$$-2$$0$$1$$3$$1$Hyperedge
$e$${I}_{{\bm{f}}}(e)$${S}_{{\bm{f}}}(e)$s$T$t$\mathcal{E}_{T}^{+}$$\mathcal{E}_{T}^{-}$$\vdots$$c(e)$$c(e)$$d(v)\delta(T)$$\infty$s$T^{\prime}$t$\mathcal{E}_{T^{\prime}}^{+}$$\mathcal{E}_{T^{\prime}}^{-}$$\vdots$$c(e)$$c(e)$$d(v)\delta(T)$$\infty$$v_{1}$$v_{2}$$v_{3}$$H$$v_{1}$$v_{2}$$v_{3}$$G_{1}$$v_{1}$$v_{2}$$v_{3}$$G_{2}$$v_{1}$$v_{2}$$v_{3}$$G_{3}$$\frac{1}{3}$$\frac{1}{3}$$\frac{1}{3}$$\frac{1}{2}$$\frac{1}{2}$$1$$K_{\frac{n}{2}}$$K_{\frac{n}{2}}$$H$$\vdots$$K_{\frac{n}{2}}$$K_{\frac{n}{2}}$$G$$\vdots$$\rightarrow$$\vdots$$\vdots$$\vdots$$\vdots$

Figure 7.6: Given the hypergraph ${H}$, there are $2^{n/3}$ possible graphs
${G}$, each of which corresponds to a different eigenvector of the hypergraph
operator ${\mathbf{J}}_{H}$.

To study the spectrum of our new operator ${\mathbf{J}}_{H}$, we construct a
hypergraph ${H}$ in the following way:

  * •

There are $n$ vertices split into two clusters ${L}$ and ${R}$ of size $n/2$.
There is a clique on each cluster.

  * •

The cliques are joined by $n/3$ edges of rank $3$, such that every vertex is a
member of exactly one such edge.

Now, we can construct a vector ${\bm{f}}$ as follows: for each edge $e$ of
rank $3$ in the hypergraph, let $u\in e$ be the vertex alone in one of the
cliques, and $v,w\in e$ be the two vertices in the other clique. Then, we set
${\bm{f}}(u)=1$ and one of ${\bm{f}}(v)$ or ${\bm{f}}(w)$ to be $-1$ and the
other to be $0$. Notice that there are $2^{n/3}$ such vectors. Each one
corresponds to a different graph ${G}$, as illustrated in Figure 7.6, which is
the graph constructed such that ${\mathbf{J}}_{H}$ is equivalent to
${\mathbf{J}}_{G}$ when applied to the vector ${\bm{f}}$.

Notice that, by the construction of the graph ${H}$, half of the edges of rank
$3$ must have one vertex in ${L}$ and two vertices in ${R}$, and half of the
rank-$3$ edges must have two vertices in ${L}$ and one vertex in ${R}$. This
means that, within each cluster ${L}$ or ${R}$, one third of the vertices have
${\bm{f}}$-value $1$, one third have ${\bm{f}}$-value $-1$, and one third have
${\bm{f}}$-value $0$.

Now, we have that

$\displaystyle\left({\mathbf{D}}_{H}^{-1}{\mathbf{J}}_{H}{\bm{f}}\right)(u)=\left({\mathbf{D}}_{H}^{-1}{\mathbf{J}}_{G}{\bm{f}}\right)(u)=\frac{2}{n}\sum_{\\{u,v\\}\in{E}_{G}}({\bm{f}}(u)+{\bm{f}}(v)).$

Suppose that ${\bm{f}}(u)=0$, meaning that it does not have an adjacent edge
in ${G}$ from its adjacent rank-$3$ edge in ${H}$. In this case,

$\displaystyle\left({\mathbf{D}}_{H}^{-1}{\mathbf{J}}_{H}{\bm{f}}\right)(u)$
$\displaystyle=\frac{2}{n}\sum_{u\sim_{G}v}{\bm{f}}(v)$
$\displaystyle=\frac{2}{n}\left[\frac{n}{3\cdot 2}\cdot 1+\frac{n}{3\cdot
2}\cdot(-1)\right]$ $\displaystyle=0.$

Now, suppose that ${\bm{f}}(u)=1$, and so it has an adjacent edge in ${G}$
from its adjacent rank-$3$ edge in ${H}$. Then,

$\displaystyle\left({\mathbf{D}}_{H}^{-1}{\mathbf{J}}_{H}{\bm{f}}\right)(u)$
$\displaystyle=\frac{2}{n}\sum_{u\sim_{G}v}(1+{\bm{f}}(v))$
$\displaystyle=\frac{2}{n}\left[\frac{n}{2}+\frac{n}{3\cdot
2}\cdot(-1)+\left(\frac{n}{3\cdot 2}-1\right)\cdot 1-1\right]$
$\displaystyle=1-\frac{4}{n}.$

Similarly, if ${\bm{f}}(u)=-1$, then we find that

$\left({\mathbf{D}}_{H}^{-1}{\mathbf{J}}_{H}{\bm{f}}\right)(u)=\frac{4}{n}-1,$

and so we can conclude that ${\bm{f}}$ is an eigenvector of the operator
${\mathbf{J}}_{H}$ with eigenvalue $(n-4)/n$. Since there are $2^{n/3}$
possible such vectors ${\bm{f}}$, there are an exponential number of
eigenvectors with this eigenvalue. Once again, we highlight that due to the
non-linearity of ${\mathbf{J}}_{H}$, a linear combination of these
eigenvectors is in general not an eigenvector of the operator.

####  7.6.2 Hardness of Finding the Minimum Eigenvalue of ${\mathbf{J}}_{H}$

The second statement of Theorem 7.1 answers an open question posed by Yoshida
[Yos19] by showing that our constructed hypergraph operator satisfies a
Cheeger-type inequality for hypergraph bipartiteness. However, the following
theorem shows that there is no polynomial-time algorithm to compute the
eigenvector corresponding to the minimum eigenvalue of _any such operator_
unless $\mathsf{P}=\mathsf{NP}$. This means that the problem we consider in
this work is fundamentally more difficult than the equivalent problem for
graphs, as well as the problem of finding a sparse cut in a hypergraph.

######  Theorem 7.3.

Given any operator that satisfies a Cheeger-type inequality for hypergraph
bipartiteness, there is no polynomial-time algorithm that computes a
multiplicative-factor approximation of the minimum eigenvalue or eigenvector
unless $\mathsf{P}=\mathsf{NP}$.

###### Proof.

The proof is based on considering the following Max Set Splitting problem: For
any given hypergraph, the problem looks for a partition ${L},{R}$ with
${L}\cup{R}={V}_{H}$ and ${L}\cap{R}=\emptyset$, such that it holds for any
$e\in{E}_{H}$ that $e\cap{L}\neq\emptyset$ and $e\cap{R}\neq\emptyset$. This
problem is known to be $\mathsf{NP}$-complete [GJ79]. This is also referred to
as Hypergraph 2-Colourability and we can consider the problem of colouring
every vertex in the hypergraph either red or blue such that every edge
contains at least one vertex of each colour.

We assume that there is some operator ${\mathbf{J}}$ which satisfies the
Cheeger-type inequality

$\frac{\lambda_{1}({\mathbf{J}})}{2}\leq{\beta}_{H}\leq\sqrt{2\lambda_{1}({\mathbf{J}})}$
(7.19)

and that there is an algorithm which can compute the minimum eigen-pair of the
operator in polynomial time. We show that this would allow us to solve the Max
Set Splitting problem in polynomial time.

Given a 2-colourable hypergraph ${H}$ with colouring $({L},{R})$, we use the
eigenvector of the operator ${\mathbf{J}}_{H}$ to find a valid colouring. By
definition, we have that ${\beta}({L},{R})=0$ and $\gamma_{1}=0$ by (7.19).