Hypergraph Partitioning using Tensor Eigenvalue Decomposition

Deepak Maurya, Balaraman Ravindran

Computer Science and Engineering,

Robert Bosch Centre for Data Science and AI,

Indian Institute of Technology Madras, Chennai, India

*corresponding author<EMAIL_ADDRESS>
## Abstract

Hypergraphs have gained increasing attention in the machine learning community
lately due to their superiority over graphs in capturing super-dyadic
interactions among entities. In this work, we propose a novel approach for the
partitioning of $k$-uniform hypergraphs. Most of the existing methods work by
reducing the hypergraph to a graph followed by applying standard graph
partitioning algorithms. The reduction step restricts the algorithms to
capturing only some weighted pairwise interactions and hence loses essential
information about the original hypergraph.

We overcome this issue by utilizing the tensor-based representation of
hypergraphs, which enables us to capture actual super-dyadic interactions. We
prove that the hypergraph to graph reduction is a special case of tensor
contraction. We extend the notion of minimum ratio-cut and normalized-cut from
graphs to hypergraphs and show the relaxed optimization problem is equivalent
to tensor eigenvalue decomposition. This novel formulation also enables us to
capture different ways of cutting a hyperedge, unlike the existing reduction
approaches. We propose a hypergraph partitioning algorithm inspired from
spectral graph theory that can accommodate this notion of hyperedge cuts. We
also derive a tighter upper bound on the minimum positive eigenvalue of even-
order hypergraph Laplacian tensor in terms of its conductance, which is
utilized in the partitioning algorithm to approximate the normalized cut. The
efficacy of the proposed method is demonstrated numerically on simple
hypergraphs. We also show improvement for the min-cut solution on 2-uniform
hypergraphs (graphs) over the standard spectral partitioning algorithm.

##  1 Introduction

In machine learning, interacting systems are often modeled as graphs. In graph
modeling, an interacting object is represented as a node, and an edge captures
the interaction between a pair of objects. A conventional approach is to
quantify the extent of interaction by associating a positive _weight_ to the
corresponding edge. This graph formulation is further utilized for various
standard machine learning applications like clustering [1] and semi-supervised
learning [2]. While a graph representation is limited to capturing only
_pairwise_ interaction, many real-world systems may involve interactions that
may be more complex than the simple pairwise formulation [3]. For instance, a
collaboration network may involve agents interacting at a group level (also
called super-dyadic interactions), which can not be captured by modeling the
system as a graph.

Recently, hypergraphs have been used to represent and analyze such complex
super-dyadic relationships. Hypergraphs are generalizations of graphs where an
edge could potentially connect multiple nodes. These edges are commonly
referred to as hyperedges. A $k$-uniform hypergraph refers to the case when
all hyperedges are constrained to contain exactly $k$ nodes. Hypergraph
partitioning has been used in a variety of applications in several domains,
such as VLSI placement [4], object segmentation in videos [5], and citation
networks [6].

Existing hypergraph modeling frameworks can be classified into two paradigms,
based on whether they reduce the hypergraph to a graph explicitly [7] or
implicitly. These reduction based approaches are quite popular in the machine
learning community due to the scalability to large datasets [8, 9], and
provable performance guarantees of graph-based algorithms [10]. Thus most of
the existing approaches make use of hypergraph reduction to utilize standard
graph-based algorithms, which defeats the motivation behind using hypergraphs.
As graphs are limited to capture only dyadic interactions, the reduction-based
approaches fail to model the desired super-dyadic relationships.

An exciting aspect of hypergraph partitioning is that a hyperedge can be cut
in multiple ways, unlike the case of an edge in graphs. The nodes in a
hyperedge can be split in different ways. Most of the existing reduction based
partitioning methods do not differentiate these multiple configurations and
penalize them equally, which, ideally, should not be the case. In fact, Ihler
et al. [11] show that the reduction-based approaches can not model a
hypergraph cut, i.e., the complete removal of a hyperedge from a given
hypergraph.

On the other hand, tensors have gained increasing attention for modeling
hypergraphs, primarily in the mathematics community. For instance, Hu et al.
[12] extended the fundamental and well-known theorem in spectral graph theory
relating cardinality of zero eigenvalue of the Laplacian of a graph to the
number of connected components to the uniform hypergraphs. Specifically, they
proved that the algebraic multiplicity of zero eigenvalue of a symmetric
Laplacian tensor is equal to the sum of the number of even-bipartite connected
components and the number of connected components excluding the number of
singletons in the given hypergraph. Such insights can not be revealed from the
clique reduction methods and its variants [7]. In the machine learning
community, tensor representation of hypergraphs has not gained much attention,
except for a few works [13, 14]. In this work, we utilize the tensor
representation of hypergraphs for detecting densely connected components.

###  1.1 Our Contributions & Outline

The preliminaries of hypergraph reduction to graphs and tensor representation
are covered in Section 2. We make the following contributions in this work:

  * •

In Section 2.3, we utilize the tensor representation of hypergraphs and prove
that hypergraph reduction is a special case of tensor contraction. We propose
the ratio-cut and normalized cut objective functions in Section 3.2, which are
capable of distinguishing the multiple ways of cutting a hyperedge.

  * •

In Section 3.3, we prove that the solution to the minimization of relaxed
ratio-cut problem can be obtained from the eigenvector corresponding to the
minimum positive eigenvalue of the Laplacian tensor. We also derive an upper
bound on the minimum positive eigenvalue in terms of the conductance of the
hypergraph, which is a significant improvement over the existing bounds.

  * •

In Section 3.4, we exploit the structure of the Laplacian tensor to reduce the
objective function computation time from $O(n^{k})$ to $O(m)$, where $n,m,k$
are the number of nodes, hyperedges, and cardinality of hyperedges,
respectively. In Section 4, we demonstrate the efficacy of the proposed
algorithm on synthetic hypergraphs generated by stochastic block model. We
also report $n/8$ times improvement of ratio-cut over the conventional
spectral partitioning for cockroach graph.

The proofs of all theoretical claims and numerical details of examples are
given in Appendix.

##  2 Preliminaries

In this section, we briefly discuss the prevalent approach of representing
hypergraphs and their partitioning. A hypergraph $G$ is defined as a pair of
$G=(V,E)$, where $V=\\{v_{1},v_{2},\ldots,v_{n}\\}$ is the set of entities
called vertices or nodes and $E=\\{e_{1},e_{2},\ldots,e_{m}\\}$ is a set of
non-empty subsets of $V$ referred to as hyperedges. The strength of
interaction among nodes in the same hyperedge is quantified by the positive
weight represented by $w_{e}=\\{w_{e_{1}},w_{e_{2}},\ldots,w_{e_{m}}\\}$.

The vertex-edge incidence matrix is denoted by $\mathbf{H}$ and has the
dimension $|V|\times|E|$. The entry $h(i,j)$ is defined to be $1$ if $v_{i}\in
e_{j}$ and $0$ otherwise. The degree of node $v_{i}$ is defined by
$d(v_{i})=\sum_{e_{j}\in E}w_{e_{j}}h(i,j)$. We can also define two diagonal
matrices, $\mathbf{W}$, $\mathbf{D}$, with the dimension of $m\times m$,
$n\times n$, containing the hyperedge weights and node degrees respectively.
Note that there is no loss of information in this form of representation of
hypergraphs until this point. This implies that a unique hypergraph can be
constructed for a given incidence matrix.

###  2.1 Reducing a Hypergraph to a Graph

Now, we discuss the widely-accepted approach for hypergraph reduction in the
machine learning community. The fundamental idea is to reduce a hypergraph to
graph and subsequently apply standard graph-based algorithms. In this
subsection, we briefly discuss the merits and demerits of these approaches and
articulate the reasons for choosing the tensor based representation of
hypergraphs.

######  Definition 1.

The clique expansion for hypergraph $G(V,E)$ builds a graph
$G_{x}(V,E_{x}\subseteq V^{2})$ by replacing each hyperedge with the
corresponding clique, $E_{x}=\\{(v_{i},v_{j}):v_{i},v_{j}\in e_{l},e_{l}\in
E\\}$ [7]. The edge weight $w_{x}(u,v)$ is given by $w_{x}(u,v)=\sum_{u,v\in
e_{l},e_{l}\in E}w(e_{l})$.

The same could be stated in matrix form as

$\displaystyle\mathbf{A}=\mathbf{HW}\mathbf{H}^{T}-\mathbf{D}$ (1)

where $\mathbf{A}$ represents the adjacency matrix for reduced hypergraph.
Another traditional hypergraph reduction approach is star expansion [15]. Most
of the other reduction approaches are build on these. Please see [7] and the
references therein, for more details.

This reduction step is very convenient as we can now employ any graph learning
algorithms that scale well and come with theoretical guarantees. A natural
question arises on the need for these different reduction based approaches. We
believe that each of these reduction approaches preserves a few but not all
hypergraph properties in the reduction step. The preserved hypergraph property
may be useful for the end task of learning on hypergraphs. For example, [16]
demonstrates the improvement in clustering by proposing a reduction approach
which preserves the node degrees.

More often, the reduction step loses vital information about hypergraphs as
two different hypergraphs can reduce to the same graph. This can be seen
directly from Eq. (1) as two distinct hypergraphs having different
$\mathbf{H}$ and $\mathbf{W}$ can reduce to the same adjacency matrix
$\mathbf{A}$. An illustrative example of the same is presented in Appendix
B.1.

We discuss the demerits of reduction-based approaches in the context of
hypergraph partitioning in the later sections. In Section 2.3, we use the
tensor representation of hypergraphs, and show that reduction is just a
special case of tensor contraction.

###  2.2 Tensor representation of Hypergraphs

In this subsection, we briefly review the tensor-based representation of
hypergraphs [17, 18]. A natural representation of hypergraphs is a $k$-order
$n$-dimensional tensor $\mathcal{A}$, which consists of $n^{k}$ entries and is
defined by:

$\displaystyle a_{i_{1}i_{2}\ldots
i_{k}}=\begin{cases}\frac{w_{e_{j}}}{(k-1)!}&\text{if}\quad\\{i_{1},i_{2},\ldots,i_{k}\\}\in
E,\quad 1\leq i_{1},\ldots,i_{k}\leq n\\\ 0&\text{otherwise}\end{cases}$ (2)

It should be noted that $\mathcal{A}$ is a “ _super-symmetric_ " tensor, i.e,
$a_{i_{1}i_{2}\ldots i_{k}}=a_{\sigma\left(i_{1}i_{2}\ldots i_{k}\right)}$,
where $\sigma\left(i_{1},i_{2},\ldots i_{k}\right)$ denotes any permutation of
the elements in the set $\\{i_{1},i_{2},\ldots,i_{k}\\}$. The order or mode of
the tensor refers to the hyperedge cardinality, which is $k$ for
$\mathcal{A}$. The degree of all the vertices can be represented by $k$-order
$n$-dimensional diagonal tensor $\mathcal{D}$. The Laplacian tensor
$\mathcal{L}$ is defined as follows:

$\displaystyle\mathcal{L}=\mathcal{D}-\mathcal{A}$ (3)

An example demonstrating the tensor representation of a 4-uniform hypergraph
is presented in Appendix B.2. The normalized Laplacian tensor, denoted by
$\mathscr{L}$ can also be defined in a similar manner:

$\displaystyle\ell_{i_{1}i_{2}\ldots
i_{k}}=\begin{cases}-\frac{w_{e_{j}}}{(k-1)!}\prod_{i_{j}=1}^{k}\frac{1}{\sqrt[k]{d_{i_{j}}}}&\text{if}\quad\\{i_{1},i_{2},\ldots,i_{k}\\}\in
E\\\ 1&\text{if $i_{1}=i_{2}\ldots=i_{k}=i$},\qquad i=\\{1,2,\ldots,n\\}\\\
0&\text{otherwise}\end{cases}$ (4)

For the sake of completeness, we define the tensor eigenvalue decomposition
as:

$\displaystyle\mathcal{L}\mathbf{x}^{k-1}=\lambda\mathbf{x},\qquad\text{such
that}\quad\mathbf{x}^{T}\mathbf{x}=1$ (5)

where
$(\lambda,\mathbf{x})\in(\mathbb{R},\mathbb{R}^{n}\backslash\\{0\\}^{n})$ is
called the Z-eigenpair and $\mathcal{L}\mathbf{x}^{k-1}\in\mathbb{R}^{n}$,
whose $i^{th}$ component is:

$\displaystyle\left[\mathcal{L}\mathbf{x}^{k-1}\right]_{i}=\sum_{i_{k}=1}^{n}\ldots\sum_{i_{3}=1}^{n}\sum_{i_{2}=1}^{n}l_{ii_{2}i_{3}\ldots
i_{k}}x_{i_{2}}x_{i_{3}}\ldots x_{i_{k}}$ (6)

In the next section, we discuss the merits of choosing tensor representation
of hypergraphs over using reductions to graphs.

###  2.3 Hypergraph Reduction using Tensor Contraction

Agarwal et al. [7] proposes to unify various hypergraph reduction methods like
star expansion [15] , Bolla’s Laplacian [19], Rodriguez’s Laplacian [20],
Zhou’s Normalized Laplacian [3] using clique expansion idea. In this section,
we show clique expansion, and hence the other existing hypergraph reduction
methods, are just a special case of tensor contraction. We define a
contraction as an operation on the tensor, which reduces its mode or order.
The following lemma is crucial for the proof.

######  Lemma 2.

One of the Z-eigenpair of $\mathcal{L}$ is $(0,\mathbf{v})$, where
$\mathbf{v}=\left(\frac{1}{\sqrt{n}},\frac{1}{\sqrt{n}},\ldots,\frac{1}{\sqrt{n}}\right)\in\mathbb{R}^{n}$.

######  Theorem 3.

Let $\mathbf{L_{T}}$ be the graph Laplacian corresponding to the clique
expansion of a k-uniform hypergraph such that the node degrees are preserved
[16]. $\mathbf{L_{T}}$ can be obtained from the hypergraph tensor Laplacian
using $\mathbf{L_{T}}=\mathcal{L}\mathbf{1}_{n}^{k-2}$, where $\mathbf{1}_{n}$
is a column vector of dimension $n$ with all entries as unity and
$\mathcal{L}\mathbf{1}_{n}^{k-2}\in\mathbb{R}^{n\times n}$ with its elements
defined by

$\displaystyle\left[\mathcal{L}\mathbf{1}^{k-2}\right]_{ij}=\sum_{i_{k}=1}^{n}\ldots\sum_{i_{4}=1}^{n}\sum_{i_{3}=1}^{n}l_{iji_{3}\ldots
i_{k}}$ (7)

######  Corollary 4.

The Laplacian corresponding to clique expansion of a k-uniform hypergraph,
denoted by $\mathbf{L_{c}}$ can be derived from the hypergraph tensor
Laplacian using
$\mathbf{L_{c}}=(k-1)\mathcal{L}\mathbf{1}_{n}^{k-2}=(k-1)\mathbf{L}_{T}$.

This can also be interpreted as $(k-2)^{th}$ order contraction of original
$k$-order tensor. In this section, the generalized nature of tensor Laplacian
was demonstrated. This was done by deriving the mapping for $(k-2)$ order
contraction of original hypergraph tensor Laplacian of order $k$. This
operation reduces a $k^{th}$ order tensor to a matrix, which can be viewed as
a $2^{nd}$ order tensor.

Having established the generality of thee tensor representation, we revisit
the original problem of hypergraph partitioning in the next section.

##  3 Partitioning of Hypergraphs

We start this section with brief review of spectral graph theory for
partitioning of graphs [21] and further propose these ideas for hypergraphs.

###  3.1 Partitioning of Graphs

Let the $p$ partitions of vertex set $V$ be denoted by sets
$C_{1},C_{2},\ldots,C_{p}$ such that

$\displaystyle C_{i}\neq\emptyset,\quad C_{i}\subset
V,\quad\cup_{i=1}^{p}C_{i}=V,\quad C_{i}\cap C_{j}=\emptyset,\quad\forall
i,j\in[p],\quad\text{and}\quad i\neq j$ (8)

The two most commonly used objectives of graph partitioning are Ratio cut [22]
and Normalized cut [23]:

$\displaystyle\text{Ratio Cut}(C_{1},C_{2},\ldots,C_{p})=$
$\displaystyle\sum_{i=1}^{p}\frac{\text{cut}(C_{i},\bar{C_{i}})}{2|C_{i}|},\quad\text{where}\quad\text{cut}(C_{i},\bar{C_{i}})=\sum_{r\in
C_{i},s\in\bar{C_{i}}}w_{rs}$ (9) $\displaystyle\text{Normalized
Cut}(C_{1},C_{2},\ldots,C_{p})$
$\displaystyle=\sum_{i=1}^{p}\frac{\text{cut}(C_{i},\bar{C_{i}})}{2\text{vol}(C_{i})},\quad\text{where}\quad\text{vol}(C_{i})=\sum_{r\in
C_{i}}d_{r}$ (10)

where $w_{rs}$ denotes the weight of edge between nodes $r$ and $s$, and
$d_{r}$ denotes the degree of $r^{th}$ node. It is well known that the
solution to the relaxed version of minimizing the ratio cut and normalized cut
can be obtained from the Fiedler vector of unnormalized and normalized
Laplacians, respectively. The approximation made in the relaxation step is
theoretically analyzed by [24]. Several extension of this work can be seen in
[25, 26].

###  3.2 Ratio-Cut and Normalized-Cut for Hypergraphs

We start the discussion with a formal description of the problem. Let
$C_{1},C_{2},\ldots,C_{p}$ be the $p$ partitions as defined in Eq. (8). For a
given hypergraph $G(V,E,W_{e})$, we intend to remove a subset of hyperedges
$\partial E\subseteq E$, such that $G\setminus\partial E$ produces at least
$p$ disjoint partitions [27, 28]. The hyperedge boundary $\partial E$ can be
defined as:

$\displaystyle\partial E=\\{e_{j}\in E:e_{j}\cap
C_{i}\neq\varnothing,e_{j}\cap\bar{C_{i}}\neq\varnothing\\}$ (11)

The next step is to define the objective function to be minimized for
obtaining optimal partitions. The measures described in Eq. (9) and Eq. (10)
for graphs are not well-suited for hypergraphs. We propose the generalization
of ratio-cut and normalized-cut for hypergraphs.

######  Definition 5.

The cut cost for the partition $C_{i}$ denoted by $w_{h}(C_{i})$ and the total
cut cost denoted by $w_{h,t}(V)$ for all the partitions is defined as:

$\displaystyle w_{h}(C_{i})=\sum_{e_{j}\in\partial E}|C_{i}\cap
e_{j}|w_{e_{j}},\qquad w_{h,t}(V)=\frac{1}{k}\sum_{i=1}^{p}w_{h}(C_{i})$ (12)

The cut cost for a partition and total cut cost defined in Eq. (12) reduces to
numerator term in Eq. (9) and Eq. (10) for $k=2$ because the term $|C_{i}\cap
e_{j}|$ reduces to unity $\forall e_{j}\in\partial E$ in graphs. We further
demonstrate the merits of this cut cost by the following example.

$e_{1}$$e_{2}$$e_{3}$$v_{1}$$v_{2}$$v_{3}$$v_{4}$$v_{5}$ Fig 1: Hypergraph :
$H_{1}$
$1$$2$$3$$4$$5$$6$$7$$8$$9$${10}$${11}$${12}$${\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\footnotesize{1}}$${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\footnotesize{1}}$${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}2}$${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}2}$${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}2}$${\color[rgb]{1,.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,.5,0}3}$${\color[rgb]{1,.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,.5,0}2}$${\color[rgb]{1,.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,.5,0}2}$${\color[rgb]{1,.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,.5,0}2}$
Fig 2: Hypergraph : $H_{2}$

######  Example 1.

Consider the 3-uniform hypergraph shown in Figure 1. Consider the partitions
obtained after removing hyperedges $e_{2}$ and $e_{3}$. Let
$C_{1}=\\{v_{1},v_{2},v_{3}\\},C_{2}=\\{4\\},C_{3}=\\{5\\}$. The partition
cost is given by

$\displaystyle w_{h}(C_{1})=2w_{e_{2}}+w_{e_{3}},\quad
w_{h}(C_{2})=w_{e_{2}}+w_{e_{3}},\quad w_{h}(C_{3})=w_{e_{3}},\quad
w_{h,t}(V)=w_{e_{2}}+w_{e_{3}}$

It should be noted that $w_{e_{1}}$ is not reflected in the above cut costs
because hyperedge $e_{1}$ is not cut. It could be easily verified that this
cut cost is not equivalent to clique reduction approach. The cut costs derived
for the reduced hypergraph are as follows:

$\displaystyle w_{g}(C_{1})=2(w_{e_{2}}+w_{e_{3}}),\quad
w_{g}(C_{2})=2(w_{e_{2}}+w_{e_{3}}),\quad w_{g}(C_{3})=2w_{e_{3}},\quad
w_{h,t}(V)=2w_{e_{2}}+3w_{e_{3}}$

Note that the cut costs derived from both approaches are different. On further
inspection, we infer $w_{g}(C_{i})=2w_{h}(C_{i})$ for $i=\\{2,3\\}$, which
means the cut cost for partitions $C_{2}$ and $C_{3}$ in the reduced
hypergraph are just a scaled version of costs involved in original hypergraph.
The same relation does not hold for partition $C_{1}$ due to the presence of
the term $|C_{i}\cap e_{j}|$ in Eq. (12). Please refer Appendix B.3 for the
computation of these cut costs.

From this illustrative example, it can be inferred that the proposed cut cost
for hypergraphs defined in Eq. (12) comprises of more information about the
cut as compared to reduced hypergraphs. The term $|C_{i}\cap e_{j}|$ in Eq.
(12) will lead to a greater penalty for cutting hyperedges with more elements
from $C_{i}$. A hyperedge with higher $|C_{i}\cap e_{j}|$ is likely to have
more association with partition $C_{i}$, so the corresponding cut should be
penalized more.

Minimizing the total cut cost defined in Eq. 12 directly may lead to
“unbalanced” partitions with minimum cost. To bypass such trivial and
undesirable partitions, we propose the normalization.

######  Definition 6.

The Ratio-cut and Normalized-cut for $p$ partitions are defined as:

$\displaystyle\text{Ratio-
Cut}(C_{1},C_{2},\ldots,C_{p})=\sum_{i=1}^{p}\frac{w_{h}(C_{i})}{k|C_{i}|^{k/2}},\quad\text{N-Cut}(C_{1},C_{2},\ldots,C_{p})=\sum_{i=1}^{p}\frac{w_{h}(C_{i})}{k(\text{vol}(C_{i}))^{k/2}}$
(13)

where $w_{h}(C_{i})$ is defined in Eq.(12). The above term for ratio-cut and
normalized-cut simplifies to Eq.(9) and Eq.(10) respectively for $k=2$. We
prefer normalization of exponential factor in the denominator to bypass the
partitions with singletons or less number of nodes. [10, 29] define normalized
associativity of a hypergraph in a similar manner but utilize the approach of
hypergraph reduction for modelling purposes.

###  3.3 Hypergraph Partitioning Algorithm

The partitions $C_{1},C_{2},\ldots,C_{p}$ can be derived by minimizing the
ratio-cut or normalized cut. For further discussion, we focus on the
minimization of ratio-cut, and the same approach can be extended for
normalized-cut, as shown later. The optimal partitions can be obtained by
solving:

$\displaystyle{(C_{1},C_{2},\ldots,C_{p})}=\operatorname*{argmin}_{(C_{1},C_{2},\ldots,C_{p})}\frac{1}{k}\sum_{i=1}^{p}\frac{w_{h}(C_{i})}{|C_{i}|^{k/2}}$
(14)

Unfortunately, the above problem is NP-hard. Inspired from spectral graph
theory, we propose to solve a relaxed version of the optimization problem
mentioned above.

######  Theorem 7.

The minimization of ratio-cut in Eq. (13) can be equivalently expressed as

$\displaystyle\min\left(\sum_{i=1}^{p}\mathcal{L}\mathbf{f}_{i}^{k}\right)=\min\left(\sum_{i=1}^{p}|C_{i}\cap
e_{j}|\frac{w_{e_{j}}}{|C_{i}|^{k/2}}\right),\qquad
f_{i,j}=\begin{cases}\frac{1}{\sqrt{|C_{j}|}}&\quad v_{i}\in C_{j}\\\
0&\text{otherwise}\end{cases}$ (15)

where we define $p$ indicator vectors $\mathbf{f}_{i}$ and its $j^{th}$
element, denoted by $f_{i,j}$ indicates if the vertex $v_{i}$ belongs to
cluster $C_{j}$. The solution to the above problem after relaxing
$\mathbf{f}_{i}\in\mathbb{R}^{n}$ rather than an indicator vector can be
derived from the eigenvector corresponding to the minimum positive eigenvalue
stated in Eq. (5).

Hence, we focus on the computation of objective function
$\mathcal{L}\mathbf{x}^{k}$ for any vector $\mathbf{x}\in\mathbb{R}^{n}$.

######  Theorem 8.

The objective for the tensor Laplacian of a hypergraph can be simplified using

$\displaystyle\mathcal{L}\mathbf{x}^{k}$
$\displaystyle=\sum_{i_{1},i_{2},\ldots,i_{k}=1}^{n}l_{i_{1}i_{2}\ldots
i_{k}}x_{i_{1}}x_{i_{2}}\ldots x_{i_{k}}$ $\displaystyle=\sum_{e_{j}\in
E}w_{e_{j}}\left(\sum_{i_{t}\in e_{j}}x^{k}_{i_{t}}-k\prod_{i_{t}\in
e_{j}}x_{i_{t}}\right)=\sum_{e_{j}\in E}w_{e_{j}}k\left(\underset{i_{t}\in
e_{j}}{\text{A.M}\left(x^{k}_{i_{t}}\right)}-\underset{i_{t}\in
e_{j}}{\text{G.M}\left(|x_{i_{t}}|^{k}\right)}(-1)^{n_{s}}\right)$ (16)

where $n_{s}=|\\{i_{j}:x_{i_{j}}<0\\}|$, A.M and G.M stand for arithmetic and
geometric means respectively.

The above objective function can be viewed as generalization of the graph, as
for any edge $\\{a,b\\}$, the objective function
$(x_{a}-x_{b})^{2}=x_{a}^{2}+x_{b}^{2}-2x_{a}x_{b}$. We continue the
discussion on partitioning with the following example.

######  Example 2.

Consider the 3-uniform hypergraph shown in Figure 2. The colored number
indicates the hyperedge weight. It is clear that the optimal partitions are
$A_{1}=\\{2,3,4,5,6,7\\}$ and $\bar{A}_{1}$. The Fiedler eigenvector for this
hypergraph is

$\displaystyle\mathbf{f^{\star}}=[0.33\quad 0.16\quad 0.17\quad
0.13\quad-0.05\quad 0.05\quad 0.12\quad 0.39\quad 0.38\quad 0.43\quad
0.39\quad 0.38]$

A standard approach in spectral graph theory is to use the sign of the
elements in the Fiedler vector for partitioning [21]. For example,
$C_{1}=\\{i|\mathbf{f}^{\star}(i)<0,i\in[n]\\}$. Hence, the partitions are
$C_{1}=\\{5\\}$ and $C_{2}=V\setminus C_{1}$, which is clearly not the
optimal.

From the above example, it is clear that the traditional approach of
partitioning does not yield desired partitions for hypergraphs. This is
primarily because the eigenvectors of the Laplacian tensor of a hypergraph can
not be interpreted in the same way as the eigenvectors of the Laplacian matrix
of a graph.

To understand the implication of minimum ratio-cut associated with minimum
positive $\lambda^{\star}$, we analyze the computation of Laplacian objective
function using the Fiedler vector:

$\displaystyle l_{e_{j}}(\mathbf{f^{\star}})=w_{e_{j}}\left(\sum_{i_{k}\in
e_{j}}f^{k}_{i_{k}}-k\prod_{i_{k}\in
e_{j}}f_{i_{k}}\right),\qquad\lambda^{\star}=\sum_{e_{j}\in
E}l_{e_{j}}(\mathbf{f^{\star}})$ (17)

where $l_{e_{j}}(\mathbf{f^{\star}})$ denotes the “score" for hyperedge
$e_{j}$ computed for the eigenvector $\mathbf{f^{\star}}$. With a slight abuse
of terminology, we argue that a higher value of this score indicates the
corresponding hyperedges are “close" to separator boundary $\partial E$. The
measure of closeness between two nodes is quantified by the minimum number of
hyperedges to be traversed for reaching one node to another.

This can be validated easily by careful inspection of hyperedge score
$l_{e_{j}}(\mathbf{f})$, when the vector $\mathbf{f}$ is treated as the
cluster indicator variable shown in Eq. (15). The hyperedge score will be non-
zero only for the hyperedges on the separating boundary for such ideal choice
of $\mathbf{f}$. The same can be also interpreted as the score being zero
$\forall e_{j}\in\\{E\setminus\partial E\\}$. We carry forward the same
intuition and prefer to cut the hyperedges with a “higher" score.

The score may not be exactly zero for any hyperedge if the Fiedler vector is
used for the score computation as it is obtained for the relaxed minimization
of the ratio-cut (Theorem 7). Applying this approach on Example 2, we report a
maximum score of $0.017$ for the hyperedge $\\{1,2,3\\}$ and hence cut it to
obtain the optimal partitions. The proposed algorithm is summarized in Table
1.

Table 1: Hypergraph Partitioning Algorithm

  1. 1.

Construct the tensor Laplacian and derive the Fiedler eigenpair
$(\lambda^{\star},\mathbf{f}^{\star})$.

  2. 2.

Calculate the hyperedge score, $l_{e_{j}}(\mathbf{f}^{\star})$ by using Eq.
(17).

  3. 3.

Remove hyperedges with maximum cost until p-disjoint partitions are obtained.

The intuition behind using the hyperedge score for deriving $\partial E$ is
motivated from spectral graph theory. It is interesting to note that this
novel use of hyperedge scores helps to compute a better ratio-cut for the
cockroach graph presented in Section 4.

A similar analysis can be performed for the minimization of the normalized cut
of hypergraphs.

######  Corollary 9.

The solution to the relaxed optimization problem of minimizing normalized cut
mentioned in Proposition 6 can be derived using the eigenvector corresponding
to the minimum positive eigenvalue of the normalized Laplacian tensor defined
in Eq. (4).

We perform the theoretical analysis of the proposed algorithm and derive an
interesting bound on the approximation made in normalized cuts.

######  Theorem 10.

The upper bound on the minimum positive eigenvalue of an even order
$k$-uniform hypergraph is

$\displaystyle\lambda_{1}\leq k\phi(G),\qquad\phi(G)=\min_{C\subseteq
V}\frac{\sum_{e_{j}\in{\partial
E}}w_{e_{j}}}{\min\left\\{\text{vol}(C),\text{vol}(\bar{C})\right\\}},\qquad\text{vol}(C)=\sum_{i_{j}\in
C}d_{i_{j}}$ (18)

where $\lambda_{1}$ is the first positive eigenvalue satisfying Eq. (5) for
normalized tensor Laplacian $\mathscr{L}$ and $\phi(G)$ refers to the
conductance of hypergraph.

The above inequality helps to analyze the order of approximation involved in
relaxing the N-min cut problem by deriving the solution through tensor EVD.
The tightness of the bound indicates the goodness of the approximation.
Several other attempts have been made to derive such approximation bounds for
hypergraphs. For example, [30] utilizes a different Laplacian tensor and the
following hyperedge score to derive similar bound on $\lambda_{1}$ of a
different tensor:

$\displaystyle l_{e_{j}}(\mathbf{x})=\sum_{i_{k}\in
e_{j}}(x_{i_{k}}-\bar{x})^{k},\quad\bar{x}=\frac{1}{k}\sum_{i_{k}\in
e_{j}}x_{i_{k}},\qquad\lambda_{1}\leq 2^{k/2}\phi(G)$ (19)

This is a weaker bound of exponential nature where as we have proposed tighter
bound of linear nature in Theorem 10.

###  3.4 Computation of Tensor Eigenvectors

The computation of eigenvectors of real super-symmetric tensors is quite
challenging and not straightforward as in the case of real symmetric matrices.
This is primarily due to the non-orthogonality of tensor eigenvectors. There
are several other challenging aspects, for example, real symmetric tensors can
have complex eigenpairs, unlike the case of matrices. Also, a real symmetric
matrix of size $n\times n$ can have a maximum of $n$ eigenvalues, whereas a
tensor can have much larger number of eigenpairs [31]. Please refer to [17]
and references therein for more details.

Most of the existing works on computation of eigenpairs have been for tensors
with special structure [32] or the extreme eigenvalues such as maximum or
minimum eigenvalue [33, 34]. As discussed in the section 3.3, only the Fiedler
vector is required for partitioning a given hypergraph. As the Fiedler vector
is not one of the extreme eigenvectors, the above methods are not helpful for
our case.

Recently, [35] proposed an algorithm to compute all the eigenvalues of a
tensor using homotopy methods. They pose the problem as finding the roots of a
vector of high order polynomials generated from
$P(\mathbf{y})=\mathcal{L}\mathbf{x}^{k-1}-\lambda\mathbf{x}=\mathbf{0}$,
where $\mathbf{y}=[\mathbf{x}\quad\lambda]\in\mathbb{R}^{n+1}$. As it is tough
to compute the zeros of $P(\mathbf{y})$ directly, the core idea of linear
homotopy methods is to construct a vector function
$H(\mathbf{y},t)=(1-t)Q(\mathbf{y})+tP(\mathbf{y})$, where $t\in[0,1]$ and
$Q(\mathbf{y})$ is a suitable vector polynomial whose roots can be computed
easily. The next step is to slowly iterate from the solution of
$H(\mathbf{y},t=0)=Q(\mathbf{y})=\mathbf{0}$ to
$H(\mathbf{y},t=1)=P(\mathbf{y})=\mathbf{0}$. Despite the novel formulation,
this approach is forced to compute all the complex eigenpairs even if we are
interested in real eigenpairs only.

We prefer to use the approach by [36], which computes all the real eigenvalues
sequentially from maximum to minimum by using Jacobian semidefinite
relaxations in polynomial optimization. They formulate the following problem
to compute $\lambda_{i+1}$ assuming $\lambda_{i}$ is known:

$\displaystyle\max$ $\displaystyle\quad
f(\mathbf{x})=\mathcal{L}\mathbf{x}^{k}$ such that $\displaystyle\quad
f(\mathbf{x})\leq\lambda_{k}-\delta\quad\&\quad
h_{r}(\mathbf{x})=0,\quad(r=1,\ldots,2n-2)$ (20)

where $0<\delta<\lambda_{i}-\lambda_{i+1}$ and $h_{r}(\mathbf{x})$ is defined
as:

$\displaystyle h_{r}(\mathbf{x})=\sum_{i+j=r+2}\frac{\partial
f(\mathbf{x})}{\partial x_{i}}\frac{\partial g(\mathbf{x})}{\partial
x_{j}}-\frac{\partial f(\mathbf{x})}{\partial x_{j}}\frac{\partial
g(\mathbf{x})}{\partial x_{i}}$ (21)

where $g(\mathbf{x})=x_{1}^{2}+x_{2}^{2}+\ldots+x_{n}^{2}-1$ is a
normalization constraint. They further utilize Lasserre’s hierarchy of
semidefinite relaxations [37] to solve the above problem.

The computation of the objective function $f(\mathbf{x})$ and the constraints
$h_{r}(\mathbf{x})$ is expensive and takes $O(n^{k})$ for general tensors.
Using Theorem 8, the objective function can be computed in linear time $O(m)$
for Laplacian tensors. The constraint can also be simplified using:

$\displaystyle\frac{\partial f(\mathbf{x})}{\partial x_{i}}=\sum_{e_{p}\in
E_{i}}kw_{e_{p}}\left(x^{k-1}_{i}-k\prod_{t\in\\{e_{p}\setminus
i\\}}x_{t}\right)$ (22)

where $E_{i}=\\{e_{q}|i\cap e_{q}\neq\emptyset,e_{q}\in E\\}$. This approach
is very helpful as all the eigenvalues need not be computed for the Fiedler
eigenvalue. Hence, the Fiedler vector can be computed easily by using Theorem
8 and the above equation.

###  3.5 Related works

As stated earlier, most of the existing methods utilize hypergraph reductions
either implicitly [7, 6] or explicitly. For example, [38] utilize the tensor-
based representation of hypergraphs but construct a matrix by concatenating
the slices of the tensor. Further, they apply the standard spectral
partitioning algorithm on the covariance of that matrix. These variants of
hypergraph reduction differ in the method of expanding a hyperedge and produce
graphs with different edge weights. The Laplacian objective function (Eq.(16))
of any graph is second-order polynomial, which captures weighted interaction
among two nodes. A second-order polynomial is insufficient for capturing
super-dyadic interaction among multiple nodes ($\geq 3$) of a hyperedge. Also,
note that multiple hypergraphs may reduce to the same graph.

[39] discuss the incapability of reduction methods in preserving the hyperedge
cuts for general hypergraphs. We utilize the Laplacian tensor (Eq. (16)) to
penalize these multiple cuts differently. Few other recent works try to
capture these multiple ways of splitting nodes. For example, [40] proposes
non-uniform clique expansion and provides quadratic approximation under
submodularity constraints of the inhomogeneous cost function. [41] extends the
notion of p-Laplacian from graphs to hypergraphs by introducing the following
hyperedge score:

$\displaystyle l_{e_{j}}(\mathbf{x})=\max_{i_{k},i^{{}^{\prime}}_{k}\in
e_{j}}|x_{i_{k}}-x_{i^{{}^{\prime}}_{k}}|^{p}$ (23)

Ideally, any definition of hyperedge score should capture the non-uniformity
among the nodes in a hyperedge, but the above equation fails to capture the
variation perfectly. For example, consider two hyperedges with cardinality 4
and node labels assigned as $\\{0,1,1,2\\}$ and $\\{0,1,2,2\\}$. Equation (23)
computes the maximum difference and hence will not differentiate among these
two hyperedges but the AM-GM difference (Eq. (17)) will capture the variance
among all the nodes of the hyperedge. [42, 43, 44] consider a similar
formulation of the hyperedge score function.

##  4 Experiments

The proposed algorithm is examined on well-known and synthetic hypergraphs.
The numerical details of Fiedler vector and hyperedge scores are presented in
Appendix B.

######  Example 3.

Consider the cockroach graph shown in Figure 3 and taken from [21].

$v_{1}$$v_{t}$$v_{t+1}$$v_{3t+1}$$v_{3t}$$v_{2t+1}$$v_{2t}$$v_{4t}$ Fig 3:
Cockroach Graph

The traditional spectral partitioning makes the red cut shown in the graph and
the partition is $A_{1}=\\{v_{1},\ldots,v_{2t}\\}$ and the ratio-
cut$(A_{1},\bar{A_{1}})=\frac{t}{2t}+\frac{t}{2t}=1$. We utilize the edge
scores as suggested in the proposed algorithm and report that the edges
$\\{v_{t},v_{t+1}\\}$ and $\\{v_{3t},v_{3t+1}\\}$ have maximum scores. On
cutting these edges, the obtained partition is
$B_{1}=\\{v_{1},v_{2},\ldots,v_{t},v_{2t+1},\ldots,v_{3t}\\}$ and hence the
ratio-cut$(B_{1},\bar{B_{1}})=\frac{2}{2t}+\frac{2}{2t}=\frac{2}{t}$.
Therefore, the solution obtained by proposed algorithm is $t/2$ times better
than the traditional approach. We made this observation for
$t=\\{3,4,\ldots,20\\}$.

######  Example 4.

In this example, we consider different types of synthetic graphs and compare
the ratio-cut values computed by the existing and proposed methods.

We begin with the study on random graphs generated from the Erdős-Rényi model
denoted by $G(n,p)$ where $n$ is the number of nodes and $p$ is the
probability of an edge between any two nodes. We compare the ratio-cut values
for $100$ different graphs for $n=100$ and for each value of
$p=\\{0.2,0.4,0.6\\}$. We observe that the ratio-cut value by our proposed
algorithm is always less than the ratio-cut obtained by sign-based Fiedler
vector partitioning. Hence we define the following metric, termed as
percentage improvement (PI) to showcase the proposed algorithm’s performance:

$\displaystyle\text{PI}=\frac{(R_{f}-R_{p})}{R_{f}}\times 100$ (24)

where $R_{f}$, $R_{p}$ denotes the ratio-cut value by sign based Fiedler
partitioning and proposed algorithm, respectively. A positive value of PI
indicates the proposed algorithm has produced a better ratio-cut value and the
magnitude of the value represents the extent of the improvement. Figure 4
shows the result as a histogram for different values of $p=\\{0.2,0.4,0.6\\}$.
It can be seen that the proposed algorithm performs better than the sign based
Fiedler partitioning in all the cases.

Fig 4: Histogram plot for percentage improvement by the proposed method for
graphs generated by the ER model for different values of $p$. It shows that
the proposed algorithm performs better for all the generated graphs.

We perform the similar analysis for another graph generation model, referred
to as the stochastic block model (SBM). This model provides us the freedom to
control the number of partitions, the number of nodes in each partition
(denoted by $n_{1},n_{2}$), the probability of an edge within a partition
(denoted by $p$), and across the partition ($q$). Note that $p=q$ yields ER
model with $n=n_{1}+n_{2}$ as discussed previously.

We consider the graphs for multiple combinations of probabilities $p$, $q$ and
$2$ partitions with $n_{1}=n_{2}=50$. It should be noted that we consider the
SBM with assortative community structure, which implies $p>q$. We generate 100
random graphs for each of these settings and compare the ratio-cut values. A
histogram plot summarizing the results is presented in Figure 5.

Fig 5: Histogram plot for percentage improvement by the proposed method for
graphs generated by the SBM for different values of intra-cluster probability
(p) and inter-cluster probability (q). It confirms that the proposed algorithm
performs better for most of the generated graphs as there are very few cases
of negative PI.

It is evident from Figure 5 that the proposed algorithm produces a lower
ratio-cut value for most of the graphs generated by SBM. We perform a similar
analysis on synthetic hypergraphs generated by SBM [38]. We generate $100$
random $4$-uniform hypergraphs with $2$ partitions, $60$ nodes, and relatively
small values of intra-cluster probability ($p$) and inter-cluster probability
($q$) as compared to the case of graphs. This is primarily because the number
of possible hyperedges for a $4-$uniform hypergraph is $\binom{n}{4}$, which
is much larger as compared to the case of graphs $\left(\binom{n}{2}\right)$.

The proposed algorithm is compared against the conventional sign-based
partitioning using the Fiedler vector computed from the Laplacian tensor of
the hypergraph. A histogram plot summarizing the results is shown in Figure 6.

Fig 6: Histogram plot for percentage improvement by the proposed method for
hypergraphs generated by the SBM for different values of $q$. It shows that
the proposed algorithm performs significantly better as compared to sign-based
partitioning for all generated hypergraphs.

It can be observed that the proposed algorithm has improved the ratio-cut
value (defined in Eq. (13)) significantly as compared to the traditional sign-
based partitioning. This is primarily because cutting a few hyperedges does
not necessarily produce only two components, unlike the case of graphs. For
example, if we cut a hyperedge having $3$ nodes in a hypergraph with one
hyperedge only, we get $3$ disconnected components, and there is no
possibility of obtaining two connected components. Hence, we may get $3$
connected components, even if we desired only $2$ connected components. This
is a unique property of hypergraphs.

Any partitioning algorithm producing many small connected components (like
singletons) will have a higher ratio-cut value. We observe that the
conventional sign-based partitioning approach using the Fiedler vector of the
Laplacian tensor is more prone to producing many small connected components as
compared to the results by proposed algorithms. Hence, the ratio-cut value by
sign-based partitioning is significantly higher.

In this section, we examined the performance of the algorithm on various
synthetic hypergraphs and observed that the proposed approach derives the
partitions with lower ratio-cut values.

##  5 Conclusions & Future Work

In this work, we propose a hypergraph partitioning algorithm using tensor
eigenvalue framework and establish its superiority over existing hypergraph
reduction methods. We extend the notion of ratio-cut and normalized cut from
graphs to hypergraph and show the equivalence of relaxed optimization problem
to a tensor eigenvalue problem. Further, we derive a tighter upper bound for
the approximation of Normalized-cut problem. We also reduce the computation
time drastically for Fiedler vector of Laplacian tensor of hypergraph. The
future directions of this work is along the lines of similar analysis for non-
uniform and directed hypergraphs.

## Supporting information

##  Appendix A Proofs

###  A.1 Proof of Lemma 2

###### Proof.

Please refer [18]: Theorem 3.13 (iv). ∎

###  A.2 Proof of Theorem 3

###### Proof.

Using (3) and Lemma 1, following may be stated :

$\displaystyle\mathcal{L}\mathbf{1}^{k-1}_{n}=\mathbf{0}$
$\displaystyle\Rightarrow\left(\mathcal{D-A}\right)\mathbf{1}_{n}^{k-1}=\mathbf{0}$
$\displaystyle=\left(\mathcal{D}\mathbf{1}_{n}^{k-2}-\mathcal{A}\mathbf{1}_{n}^{k-2}\right)\mathbf{1}_{n}=\mathbf{0}$

As $\mathcal{D}$ is a diagonal tensor of order $k$, the first term
$\mathcal{D}\mathbf{1}_{n}^{k-2}$ is a contracted diagonal tensor of order
$=k-(k-2)=2$. The diagonal elements in the resulting $2^{nd}$ order tensor (a
matrix) will be same as the diagonal of original $k$ mode tensor.

As $\mathcal{A}$ is a _super symmetrical_ tensor of order $k$, the second term
$\mathcal{A}\mathbf{1}_{n}^{k-2}$ will be a $2-$ dimensional _symmetric_
tensor. This is due to the fact that all $(k-2)$ modes of tensor are scaled
and contracted with same vector of ones. As all the diagonal terms for
$\mathcal{A}\mathbf{1}_{n}^{k-2}$ are zeros, the vertex degree can be seen to
be preserved from
$\mathbf{L}_{T}=\mathcal{D}\mathbf{1}_{n}^{k-2}-\mathcal{A}\mathbf{1}_{n}^{k-2}$.
The Laplacian of the corresponding reduced graph is described by

$\displaystyle\mathbf{L}_{T}=\mathcal{D}\mathbf{1}_{n}^{k-2}-\mathcal{A}\mathbf{1}_{n}^{k-2}=\mathcal{L}\mathbf{1}_{n}^{k-2}$

∎

###  A.3 Proof of Corollary 4

The Laplacian corresponding to clique expansion [7] of a k-uniform hypergraph,
denoted by $\mathbf{L_{c}}$ can be derived from the hypergraph tensor
Laplacian as follows:

$\displaystyle\mathbf{L_{c}}=(k-1)\mathcal{L}\mathbf{1}_{n}^{k-2}=(k-1)\mathbf{L}_{T}$
(25)

###### Proof.

This can be seen as a direct consequence of Lemma 1 which proposes an approach
to preserve node degree. In basic clique expansion algorithm, the vertex
degree is not preserved. Each node in a hyperedge of $k$ nodes will be paired
up with remaining $(k-1)$ nodes. So, the same scaling factor appears in Eq.
(25). The proof is trivial because the input is a $k$-_uniform_ hypergraph. ∎

###  A.4 Proof of Theorem 7

###### Proof.

Given a partition of $p$ disjoint sets $\\{C_{1},C_{2},\ldots,C_{p}\\}$,
define the $p$ indicator variables
$f_{j}=(f_{1,j},f_{2,j},\ldots,f_{n,j})^{{}^{\prime}}$ defined as

$\displaystyle f_{i,j}=\begin{cases}\frac{1}{\sqrt{|C_{j}|}}&\quad v_{i}\in
C_{j}\\\ 0&\text{otherwise}\end{cases}$ (26)

where $i\in[n]$ and $j\in[p]$.

For any partition $C_{i}$, we compute $\mathcal{L}\mathbf{f}_{i}^{k}$

$\displaystyle\mathcal{L}\mathbf{f}_{i}^{k}=\sum_{i_{k}=1}^{n}\ldots\sum_{i_{2}=1}^{n}\sum_{i_{1}=1}^{n}l_{i_{1}i_{2}\ldots
i_{k}}x_{i_{1}}x_{i_{2}}\ldots x_{i_{k}}$ (27)

We use Theorem 8 to compute the above term

$\displaystyle\mathcal{L}\mathbf{f}_{i}^{k}$ $\displaystyle=\sum_{e_{j}\in
E}w_{e_{j}}\left(\sum_{i_{k}\in e_{j}}f^{k}_{i_{k}}-k\prod_{i_{k}\in
e_{j}}f_{i_{k}}\right)$ (28)

There can be three case for each hyperedge.

  1. 1.

All the nodes in a hyperedge $e_{j}$ are assigned as
$\frac{1}{|C_{j}|^{1/2}}$. Both the terms will be $k\frac{1}{|C_{i}|^{k/2}}$
and the overall term reduces to 0.

  2. 2.

All the nodes in hyperedge $e_{j}$ are assigned 0: Both the terms will be zero
and overall term will be zero.

  3. 3.

Some of the nodes are assigned $\frac{1}{\sqrt{|C_{j}|}}$. The second term
will be zero and the first term will reduce to $|C_{i}\cap
e_{j}|\frac{w_{e_{j}}}{|C|^{k/2}}$.

So the overall term reduce to

$\displaystyle\mathcal{L}\mathbf{f}_{i}^{k}=|C_{i}\cap
e_{j}|\frac{w_{e_{j}}}{|C_{i}|^{k/2}}$ (29)

Similarly adding other partitons, we arrive at

$\displaystyle\sum_{i=1}^{p}\mathcal{L}\mathbf{f}_{i}^{k}=\sum_{i=1}^{p}|C_{i}\cap
e_{j}|\frac{w_{e_{j}}}{|C_{i}|^{k/2}}$ (30)

The RHS term in the above equation is same as the defined ratio cut for
hypergraphs. It should be noted that $\mathbf{f_{i}}^{T}\mathbf{f_{i}}=1$. As
the objective function and constraint are same under relaxation, both the
problems are equivalent and the solution can be derived from tensor Eigenvalue
decompostion. ∎

###  A.5 Proof of Theorem 8

###### Proof.

$\displaystyle\mathcal{L}\mathbf{x}^{k}$
$\displaystyle=\sum_{i_{k}=1}^{n}\ldots\sum_{i_{2}=1}^{n}\sum_{i_{1}=1}^{n}(d_{i_{1}i_{2}\ldots
i_{k}}-a_{i_{1}i_{2}\ldots i_{k}})x_{i_{1}}x_{i_{2}}\ldots x_{i_{k}}$
$\displaystyle=\sum_{i=1}^{n}d(v_{i})x_{i}^{k}-\sum_{i_{k}=1}^{n}\ldots\sum_{i_{2}=1}^{n}\sum_{i_{1}=1}^{n}a_{i_{1}i_{2}\ldots
i_{k}}x_{i_{1}}x_{i_{2}}\ldots x_{i_{k}}$
$\displaystyle=\sum_{i=1}^{n}\sum_{i_{k}=1}^{n}\ldots\sum_{i_{3}=1}^{n}\sum_{i_{2}=1}^{n}a_{ii_{2}i_{3}\ldots
i_{k}}x_{i}^{k}-\sum_{i_{k}=1}^{n}\ldots\sum_{i_{2}=1}^{n}\sum_{i_{1}=1}^{n}a_{i_{1}i_{2}\ldots
i_{k}}x_{i_{1}}x_{i_{2}}\ldots x_{i_{k}}$
$\displaystyle=\sum_{i=1}^{n}\left(\sum_{(i_{2},i_{3},\ldots,i_{k})\in
e_{j}}\frac{w_{e_{j}}}{(k-1)!}x_{i}^{k}\right)-\left(\sum_{(i_{1},i_{2},\ldots,i_{k})\in
e_{j}}\frac{w_{e_{j}}}{(k-1)!}x_{i_{1}}x_{i_{2}}\ldots x_{i_{k}}\right)$ (31)

As there are $(k-1)!$ and $k!$ permutations of the first and second term
respectively :

$\displaystyle\mathcal{L}\mathbf{x}^{k}$ $\displaystyle=\sum_{e_{j}\in
E}w_{e_{j}}\left(\sum_{i_{t}\in
e_{j}}\frac{(k-1)!}{(k-1)!}x^{k}_{i_{t}}-\frac{k!}{(k-1)!}x_{i_{1}}x_{i_{2}}\ldots
x_{i_{k}}\right)$ $\displaystyle=\sum_{e_{j}\in
E}w_{e_{j}}\left(\sum_{i_{t}\in e_{j}}x^{k}_{i_{t}}-k\prod_{i_{t}\in
e_{j}}x_{i_{t}}\right)$ $\displaystyle=\sum_{e_{j}\in
E}w_{e_{j}}\left(k\frac{\sum_{i_{t}\in
e_{j}}x^{k}_{i_{t}}}{k}-k\left(\prod_{i_{t}\in
e_{j}}|x_{i_{t}}|^{k}\right)^{\frac{1}{k}}(-1)^{n_{s}}\right)$
$\displaystyle=\sum_{e_{j}\in E}w_{e_{j}}k\left(\underset{i_{t}\in
e_{j}}{AM\left(x^{k}_{i_{t}}\right)}-\underset{i_{t}\in
e_{j}}{GM\left(|x_{i_{t}}|^{k}\right)}(-1)^{n_{s}}\right)$ (32)

∎

###  A.6 Proof of Corollary 9

The proof of this corollary is very similar to the proof of Theorem 7. In this
case, we choose the indicator variable as

$\displaystyle f_{i,j}=\begin{cases}\frac{1}{\sqrt{\text{vol}(C_{j})}}&\quad
v_{i}\in C_{j}\\\ 0&\text{otherwise}\end{cases}$ (33)

The next step is to compute the $\mathscr{L}\mathbf{x}^{k}$, where the
normalized Laplacian tensor $\mathscr{L}$ is defined in Eq. 4. Rest of the
proof is very similar to the proof of Theorem 7.

###  A.7 Proof of Theorem 10

###### Proof.

Let $\mathbf{x}$ be $n\times 1$ vector with
$x_{i_{j}}\in\left\\{\frac{\sqrt[k]{d_{i_{j}}}}{\omega},\frac{-\sqrt[k]{d_{i_{j}}}}{\omega}\right\\}$,
where $\omega$ is defined as

$\displaystyle\omega=\left(\sum_{i_{j}=1}^{n}d_{i_{j}}^{\frac{2}{k}}\right)^{\frac{1}{2}}$

It can be easily verified that $\mathbf{x}^{T}\mathbf{x}=1$. Substituting
$\mathbf{x}$ in the expression for normalized hypergraph Laplacian defined in
Eq. (4). Please note that we do not use the signs of elements in the Fiedler
vector to compute partitions, as discussed in the main manuscript.

$\displaystyle\lambda_{1}\leq\mathscr{L}\mathbf{x}^{m}$
$\displaystyle=\sum_{e_{j}\in E}w_{e_{j}}\left(\sum_{i_{j}\in
e_{j}}\frac{x^{k}_{i_{j}}}{d_{i_{j}}}-k\prod_{i_{j}\in
e_{j}}\frac{x_{i_{j}}}{\sqrt[k]{d_{i_{j}}}}\right)$
$\displaystyle=\sum_{e_{j}\in
E}w_{e_{j}}\left(\frac{k-n_{s}}{\omega^{k}}+\frac{n_{s}(-1)^{k}}{\omega^{k}}-k(-1)^{n_{s}}\frac{1}{\omega^{k}}\right)$
(34)

where $n_{s}=|\\{i_{k}:x_{i_{k}}<0\\}|$. For even order hypergraphs, the above
can be reduced to

$\displaystyle\lambda_{1}$ $\displaystyle\leq\sum_{e_{j}\in
E}w_{e_{j}}\left(\frac{k}{\omega^{k}}-k(-1)^{n_{s}}\frac{1}{\omega^{k}}\right)$
(35) $\displaystyle\leq\sum_{e_{j}\in{\partial
S}}w_{e_{j}}\left(\frac{2k}{\omega^{k}}\right)=\sum_{e_{j}\in{\partial
S}}w_{e_{j}}\left(\frac{2k}{\left(\sum_{i=1}^{n}d_{i}^{\frac{2}{k}}\right)^{\frac{k}{2}}}\right)$
$\displaystyle\leq\sum_{e_{j}\in{\partial
S}}w_{e_{j}}\left(\frac{2k}{\left(\sum_{i=1}^{n}d_{i}\right)^{\frac{2}{k}\times\frac{k}{2}}}\right)$
$\displaystyle\leq\sum_{e_{j}\in{\partial
S}}w_{e_{j}}\frac{2k}{2\min(\text{vol}(C),\text{vol}(\bar{C}))}=k\phi(G)$ (36)

∎

##  Appendix B Examples & Numerical Details of Experiments

###  B.1 Hypergraph reduction to same graph

Various hypergraph reduction methods have been summarized in [7]. One of the
prevalent approaches is

$\displaystyle\mathbf{A}_{r}=\mathbf{HW}\mathbf{H}^{T}-\mathbf{D}$ (37)

It should be noticed that these reduction methods are a non-unique mapping
from hypergraph to adjacency matrix. This implies that there could be multiple
different hypergraphs which reduce to same graph. For example, the clique
reduction approach reduces the four-uniform hypergraph and the three-uniform
hypergraph hypergraph shown in following figure to the same graph.

Represent G as Matrix$\frac{1}{2}$$\frac{1}{2}$$\frac{1}{2}$$\frac{1}{2}$ Fig
7: Two Hypergraphs reducing to same Graph

This non-uniqueness property of hypergraph reduction method plays a very
crucial role in the task of hypergraph partitioning. The reduced hypergraph
has lost the information about the original hypergraph structure. So there is
no assurance of any analysis on reduced hypergraph to deliver correct results
for the original hypergraph. To avoid the loss of information in the reduction
step, we utilize the tensor-based representation of hypergraphs as shown in
the next example.

###  B.2 Representation of Hypergraphs

Consider a $4-$uniform hypergraph $G(V,E)$ as shown below, where the set of
vertices and hyperedges are defined by

$\displaystyle V$ $\displaystyle=\\{1,2,3,4,5\\}$ $\displaystyle E$
$\displaystyle=\\{\\{1,2,3,4\\},\\{2,3,4,5\\},\\{1,2,3,5\\}\\}$

The adjacency tensor for the above hypergraph is denoted by $\mathcal{A}$ and
has dimensions $5\times 5\times 5\times 5$. It should be noted that the
cardinality ($k$) of all $3$ hyperedges is 4 . The elements of $\mathcal{A}$
are denoted by $a_{i_{1},i_{2},i_{3},i_{4}}$, where $1\leq i_{k}\leq 5$. It
should be noted that $\mathcal{A}$ contains $n^{k}=5^{4}$ elements but only
$m\times k!=3\times 4!=72$ elements have non-zero entries. The elements
corresponding to first hyperedge are described by

$\displaystyle a_{1234}=a_{1243}=a_{1324}=a_{1342}=a_{1423}=a_{1432}$
$\displaystyle=$ $\displaystyle
a_{2134}=a_{2143}=a_{2314}=a_{2341}=a_{2413}=a_{2431}$ $\displaystyle=$
$\displaystyle a_{3214}=a_{3241}=a_{3124}=a_{3142}=a_{3421}=a_{3412}$
$\displaystyle=$ $\displaystyle
a_{4231}=a_{4213}=a_{4321}=a_{4312}=a_{4123}=a_{4132}=c$

where $c=\frac{1}{(k-1)!}=\frac{1}{6}$. The vertex degrees can be stored in a
tensor of dimension $5\times 5\times 5\times 5$ with its diagonal elements
being $d(v)=\begin{bmatrix}2&3&3&2&2\end{bmatrix}$. The tensor Laplacian has
dimension of $5\times 5\times 5\times 5$ and its entries are given by:

$\displaystyle l_{i_{1}i_{2}i_{3}i_{4}}=\begin{cases}-\frac{1}{6}&\text{if
$(i_{1},i_{2},i_{3},i_{4})=\\{e_{j}\\},\quad j=\\{1,2,3\\}$}\\\
d(v_{i})&\text{if $i_{1}=i_{2}=i_{3}=i_{4}=i$}\\\
0&\text{otherwise}\end{cases}$ (38)

This example shows the procedure to construct the adjacency and Laplacian
tensor for any $k$-uniform hypergraph.

###  B.3 Partition Cost

First we show the cut cost derived from graphical. The hypergraph is shown in
Figure 1. The partitions are given to be $C_{1}=\\{1,2,3\\}$, $C_{2}=\\{4\\}$
and $C_{3}=\\{5\\}$. The hyperedges denoted by $e_{2}$ and $e_{3}$ have to be
removed for such partition, so $\partial E=\\{e_{2},e_{3}\\}$. The cost for
partitions can be derived as shown below :

$\displaystyle w_{h}(C_{1})$ $\displaystyle=\sum_{e_{j}\in\partial
E}|C_{1}\cap e_{j}|w_{e_{j}}$ $\displaystyle=|C_{1}\cap
e_{2}|w_{e_{2}}+|C_{1}\cap e_{3}|w_{e_{3}}$
$\displaystyle=2w_{e_{2}}+w_{e_{3}}$ (39)

The cost of other partitions can be derived in similar fashion and are
observed to be $w_{h}(C_{2})=w_{2}+w_{3}$ and $w_{h}(C_{3})=w_{3}$.

Further, we compute the cut cost for reduced hypergraph. The edges between
node $i$ and $j$ is named as $e_{ij}$ and the corresponding weight is denoted
by $w_{e_{ij}}$. The edges denoted by $e_{24},e_{34},e_{35},e_{45}$ have to be
removed for arriving at the desired partition, So $\partial
E_{g}=\\{e_{24},e_{34},e_{35},e_{45}\\}$ . The cut cost for such partitioning
is given by:

$\displaystyle w_{g}(C_{1})$ $\displaystyle=\sum_{e_{ij}\in\partial
E_{g}}|C_{1}\cap e_{ij}|w_{e_{ij}}$ $\displaystyle=|C_{1}\cap
e_{24}|w_{e_{24}}+|C_{1}\cap e_{34}|w_{e_{34}}+|C_{1}\cap
e_{35}|w_{e_{35}}+|C_{1}\cap e_{45}|w_{e_{45}}$
$\displaystyle=w_{e_{24}}+w_{e_{34}}+w_{e_{35}}+0$
$\displaystyle=w_{e_{2}}+(w_{e_{2}}+w_{e_{3}})+w_{e_{3}}=2(w_{e_{2}}+w_{e_{3}})$
(40)

The cut cost for other partitions can be calculated as
$w_{g}(C_{2})=2(w_{e_{2}}+w_{e_{3}})$ and $w_{g}(C_{3})=2w_{e_{3}}$.

It can be easily noticed that the cut cost for both the cases are not equal.
On further inspection, we infer $w_{g}(C_{i})=2w_{h}(C_{i})$ for
$i=\\{2,3\\}$, which means the cut cost for partitions $C_{2}$ and $C_{3}$ in
reduced hypergraph are just a scaled version of costs involved in original
hypergraph. The same relation doesn’t hold for partition $C_{1}$ due to the
presence of the term $|C_{i}\cap e_{j}|$.

###  B.4 Numerical details of Example 2

The Fiedler eigenvalue for this hypergraph is reported to be $0.0372$ and the
corresponding eigenvector is given by:

$\displaystyle\mathbf{f}=\setcounter{MaxMatrixCols}{12}\begin{bmatrix}0.34&0.21&0.18&0.11&-0.07&0.05&0.12&0.38&0.39&0.39&0.38&0.39\end{bmatrix}^{T}$
(41)

It is clear that the classical spectral approach does not produce the optimal
partitions and hence we compute the hyperedge scores as prescribed by the
proposed algorithm.

Hyperedge | Score
---|---
$\\{1,2,3\\}$ | 0.0170
$\\{4,5,6\\}$ | 0.0060
$\\{2,3,4\\}$ | 0.0041
$\\{3,4,7\\}$ | 0.0036
$\\{1,8,11\\}$ | 0.0033
$\\{4,6,7\\}$ | 0.0024
$\\{8,9,10\\}$ | 0.0005
$\\{10,11,12\\}$ | 0.0005
$\\{9,10,12\\}$ | 0
Table 2: Hyperedge-Score for Example 2

We observe the maximum score of $0.017$ for the hyperedge $\\{1,2,3\\}$ and
hence cut it to obtain the optimal partitions $A_{1}=\\{2,3,4,5,6,7\\}$ and
$\bar{A}_{1}$.

###  B.5  Numerical details of Example 3

Consider the cockroach graph shown in Figure 3 for $t=3$ and hence 12 nodes.
The Fiedler vector for this graph is given by:

$\displaystyle\mathbf{f}=\setcounter{MaxMatrixCols}{12}\begin{bmatrix}-0.49&-0.41&-0.26&-0.07&-0.02&-0.01&0.49&0.41&0.26&0.07&0.02&0.01\end{bmatrix}^{T}$
(42)

So the partitions defined based on the sign of elements in $\mathbf{v}$ are
$A_{1}=\\{v_{1},v_{2},v_{3},v_{4},v_{5},v_{6}\\}$ and $A_{2}=\bar{A_{1}}$. So,
RatioCut$(A_{1},\bar{A_{1}})=\frac{3}{6}+\frac{3}{6}=1$.

The next step is to apply the proposed algorithm. The edge score computed from
the proposed algorithm are:

Edge | Score
---|---
$\\{v_{3},v_{4}\\}$ | 0.0371
$\\{v_{9},v_{10}\\}$ | 0.0371
$\\{v_{4},v_{10}\\}$ | 0.0228
$\\{v_{2},v_{3}\\}$ | 0.0228
$\\{v_{8},v_{9}\\}$ | 0.0222
$\\{v_{1},v_{2}\\}$ | 0.0222
$\\{v_{7},v_{8}\\}$ | 0.0066
$\\{v_{4},v_{5}\\}$ | 0.0066
$\\{v_{10},v_{11}\\}$ | 0.0029
$\\{v_{5},v_{11}\\}$ | 0.0029
$\\{v_{6},v_{12}\\}$ | 0.0002
$\\{v_{11},v_{12}\\}$ | 0.0002
$\\{v_{5},v_{6}\\}$ | 0.0002
Table 3: Edge-Score for 2

The edges $\\{v_{3},v_{4}\\}$ and $\\{v_{9},v_{10}\\}$ are removed as they are
of maximum edge score of $0.0371$. So the partitions are
$B_{1}=\\{v_{1},v_{2},v_{3},v_{7},v_{8},v_{9}\\},B_{2}=\bar{B_{1}}$.
Therefore, RatioCut$(B_{1},\bar{B_{1}})=\frac{2}{6}+\frac{2}{6}=0.66$. It can
be clearly observed that the partitions obtained from the proposed algorithm
have a lower RatioCut value compared to the existing method.

We observe the superior performance of the proposed algorithm for
$t=\\{3,4,\ldots,20\\}$.

## References

  * [1] Dhillon IS, Guan Y, Kulis B.  Kernel k-means: spectral clustering and normalized cuts.  In: Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining. ACM; 2004. p. 551–556.
  * [2] Wang M, Fu W, Hao S, Tao D, Wu X.  Scalable semi-supervised learning by efficient anchor graph regularization.  IEEE Transactions on Knowledge and Data Engineering. 2016;28(7):1864–1877.
  * [3] Zhou D, Huang J, Scholkopf B.  Beyond pairwise classification and clustering using hypergraphs.  In: Proceedings of the Neural Information Processing Systems; 2005.
  * [4] Karypis G, Aggarwal R, Kumar V, Shekhar S.  Multilevel hypergraph partitioning: applications in VLSI domain.  IEEE Transactions on Very Large Scale Integration (VLSI) Systems. 1999;7(1):69–79.
  * [5] Huang Y, Liu Q, Metaxas D.  Video object segmentation by hypergraph cut.  In: Computer Vision and Pattern Recognition, 2009. CVPR 2009. IEEE Conference on. IEEE; 2009. p. 1738–1745.
  * [6] Zhou D, Huang J, Schölkopf B.  Learning with hypergraphs: Clustering, classification, and embedding.  In: Advances in neural information processing systems; 2007. p. 1601–1608.
  * [7] Agarwal S, Branson K, Belongie S.  Higher order learning with graphs.  In: Proceedings of the 23rd International Conference on Machine learning. ACM; 2006. p. 17–24.
  * [8] Li L, Li T.  News recommendation via hypergraph learning: encapsulation of user behavior and news content.  In: Proceedings of the sixth ACM international conference on Web search and data mining; 2013. p. 305–314.
  * [9] Gao Y, Wang M, Tao D, Ji R, Dai Q.  3-D object retrieval and recognition with hypergraph analysis.  IEEE Transactions on Image Processing. 2012;21(9):4290–4303.
  * [10] Ghoshdastidar D, Dukkipati A.  A provable generalized tensor spectral method for uniform hypergraph partitioning.  In: International Conference on Machine Learning; 2015. p. 400–409.
  * [11] Ihler E, Wagner D, Wagner F.  Modeling hypergraphs by graphs with the same mincut properties.  Information Processing Letters. 1993;45(4):171–175.
  * [12] Hu S, Qi L.  The eigenvectors associated with the zero eigenvalues of the Laplacian and signless Laplacian tensors of a uniform hypergraph.  Discrete Applied Mathematics. 2014;169:140–151.
  * [13] Shashua A, Zass R, Hazan T.  Multi-way clustering using super-symmetric non-negative tensor factorization.  In: European conference on computer vision. Springer; 2006. p. 595–608.
  * [14] Benson AR.  Three hypergraph eigenvector centralities.  SIAM Journal on Mathematics of Data Science. 2019;1(2):293–312.
  * [15] Zien JY, Schlag MD, Chan PK.  Multilevel spectral hypergraph partitioning with arbitrary vertex sizes.  IEEE Transactions on computer-aided design of integrated circuits and systems. 1999;18(9):1389–1399.
  * [16] Kumar T, Vaidyanathan S, Ananthapadmanabhan H, Parthasarathy S, Ravindran B.  Hypergraph Clustering: A Modularity Maximization Approach.  arXiv preprint arXiv:181210869. 2018;.
  * [17] Qi L, Luo Z.  Tensor analysis: spectral theory and special tensors. vol. 151.  SIAM; 2017.
  * [18] Banerjee A, Char A, Mondal B.  Spectra of general hypergraphs.  Linear Algebra and its Applications. 2017;518:14–30.
  * [19] Bolla M.  Spectra, euclidean representations and clusterings of hypergraphs.  Discrete Mathematics. 1993;117(1-3):19–39.
  * [20] Rodriguez JA.  On the Laplacian spectrum and walk-regular hypergraphs.  Linear and Multilinear Algebra. 2003;51(3):285–297.
  * [21] Von Luxburg U.  A tutorial on spectral clustering.  Statistics and computing. 2007;17(4):395–416.
  * [22] Hagen L, Kahng AB.  New spectral methods for ratio cut partitioning and clustering.  IEEE transactions on computer-aided design of integrated circuits and systems. 1992;11(9):1074–1085.
  * [23] Shi J, Malik J.  Normalized cuts and image segmentation.  Departmental Papers (CIS). 2000; p. 107.
  * [24] Chung F.  Four proofs for the Cheeger inequality and graph partition algorithms.  Proceedings of ICCM. 2007;2:378.
  * [25] Bühler T, Hein M.  Spectral clustering based on the graph p-Laplacian.  In: Proceedings of the 26th Annual International Conference on Machine Learning; 2009. p. 81–88.
  * [26] Lee JR, Gharan SO, Trevisan L.  Multiway spectral partitioning and higher-order cheeger inequalities.  Journal of the ACM (JACM). 2014;61(6):1–30.
  * [27] Chandrasekaran K, Xu C, Yu X.  Hypergraph k-cut in randomized polynomial time.  In: Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics; 2018. p. 1426–1438.
  * [28] Chekuri C, Li S.  A note on the hardness of approximating the k-way Hypergraph Cut problem.  Manuscript, http://chekuri cs illinois edu/papers/hypergraph-kcut pdf. 2015;.
  * [29] Ghoshdastidar D, Dukkipati A.  Spectral Clustering Using Multilinear SVD: Analysis, Approximations and Applications.  In: AAAI; 2015. p. 2610–2616.
  * [30] Chen Y, Qi L, Zhang X.  The Fiedler Vector of a Laplacian Tensor for Hypergraph Partitioning.  SIAM Journal on Scientific Computing. 2017;39(6):A2508–A2537.
  * [31] Qi L.  Eigenvalues of a real supersymmetric tensor.  Journal of Symbolic Computation. 2005;40(6):1302–1324.
  * [32] Qi L, Wang F, Wang Y.  Z-eigenvalue methods for a global polynomial optimization problem.  Mathematical Programming. 2009;118(2):301–316.
  * [33] Kolda TG, Mayo JR.  Shifted power method for computing tensor eigenpairs.  SIAM Journal on Matrix Analysis and Applications. 2011;32(4):1095–1124.
  * [34] Hu S, Huang ZH, Qi L.  Finding the extreme Z-eigenvalues of tensors via a sequential semidefinite programming method.  Numerical Linear Algebra with Applications. 2013;20(6):972–984.
  * [35] Chen L, Han L, Zhou L.  Computing tensor eigenvalues via homotopy methods.  SIAM Journal on Matrix Analysis and Applications. 2016;37(1):290–319.
  * [36] Cui CF, Dai YH, Nie J.  All real eigenvalues of symmetric tensors.  SIAM Journal on Matrix Analysis and Applications. 2014;35(4):1582–1601.
  * [37] Lasserre JB.  Global optimization with polynomials and the problem of moments.  SIAM Journal on optimization. 2001;11(3):796–817.
  * [38] Ghoshdastidar D, Dukkipati A.  Consistency of spectral partitioning of uniform hypergraphs under planted partition model.  In: Advances in Neural Information Processing Systems; 2014. p. 397–405.
  * [39] Hein M, Setzer S, Jost L, Rangapuram SS.  The total variation on hypergraphs-learning on hypergraphs revisited.  In: Advances in Neural Information Processing Systems; 2013. p. 2427–2435.
  * [40] Li P, Milenkovic O.  Inhomogeneous hypergraph clustering with applications.  In: Advances in Neural Information Processing Systems; 2017. p. 2308–2318.
  * [41] Li P, Milenkovic O.  Submodular Hypergraphs: p-Laplacians, Cheeger Inequalities and Spectral Clustering.  In: Dy J, Krause A, editors. Proceedings of the 35th International Conference on Machine Learning. vol. 80 of Proceedings of Machine Learning Research. PMLR; 2018. p. 3014–3023.
  * [42] Zhang C, Hu S, Tang ZG, Chan T.  Re-revisiting learning on hypergraphs: confidence interval and subgradient method.  In: Proceedings of the 34th International Conference on Machine Learning-Volume 70. JMLR. org; 2017. p. 4026–4034.
  * [43] Chan THH, Louis A, Tang ZG, Zhang C.  Spectral properties of hypergraph laplacian and approximation algorithms.  Journal of the ACM (JACM). 2018;65(3):1–48.
  * [44] Chan THH, Liang Z.  Generalizing the hypergraph laplacian via a diffusion process with mediators.  Theoretical Computer Science. 2020;806:416–428.