Hypergraph Analysis Based on a Compatible Tensor Product Structure

The same as graphs, a hypergraph $\mathcal{G}=(V,\mathcal{E})$ consists of two parts: the set of vertices $V$ and the set of hyperedges $\mathcal{E}$. A hyperedge $E_{i}\subseteq V$ consists of several vertices. A hypergraph is $m$-uniform if all its hyperedges contain the same number of vertices, i.e., $|E_{i}|=m$ for all $E_{i}\in\mathcal{E}$. Specially, a graph can be regarded as a $2$-uniform hypergraph. For an undirected hypergraph, each hyperedge is an unordered set. For a directed hypergraph, its hyperedge $E_{i}=(T_{i},H_{i})$ is further divided into two parts: the head $H_{i}$ and the tail $T_{i}$ [5, 20, 44]. We follow the definition in [4, 52] that assumes $|H|=1$, or the definition of the forward arc in [5, 20, 11]. A directed hyperedge is an ordered pair $E=(T,h)$, where the unordered set $T\subset V$ is the tail and $h\in V\backslash T$ is the head. In the following part, we will use the hypergraph to refer to an undirected hypergraph, and will use the directed hypergraph to clarify the directed property.

A path in graph theory can be generalized to the hypergraph as a hyperpath [30]. We use $[n]$ as an abbreviation for the set $\{1,2,\dots,n\}$. For the undirected hypergraph, a hyperpath of length $l$ is a sequence of hyperedges and vertices $<E_{1},v_{1},E_{2},v_{2},\dots,v_{l-1},E_{l}>$ such that

$$v_{i}\in E_{i}\cap E_{i+1},\ \forall i\in[l-1],$$

and $v_{i}\neq v_{i+1}$ for all $i\in[l-2]$. For the directed hypergraph, a hyperpath $<E_{1},v_{1},E_{2},\dots,v_{l-1},E_{l}>$ of length $l$ satisfies

$$v_{i}=h_{i}{\ \rm and\ }v_{i}\in T_{i+1},\ \forall i\in[l-1].$$

As hyperedges forbid duplicate vertices, the property $v_{i}\neq v_{i+1}$ still holds for the directed hypergraph as $v_{i}=h_{i}\in T_{i+1}$ and $v_{i+1}=h_{i+1}\notin T_{i+1}$.

Based on this we can define the product of two $(m+1)$-uniform hypergraphs. In graph theory, the matrix product of two graphs is defined based on their adjacency matrices [39, Definition 17.3]. Suppose $G_{1}=(V,E_{1})$ and $G_{2}=(V,E_{2})$ are defined on the same vertex set $V$ and have their adjacency matrices $A_{1}$ and $A_{2}$. Then the product matrix $A_{3}=A_{1}A_{2}$ also corresponds to a graph $G_{3}=(V,E_{3})$ that allows multiple edges and self-loops. $G_{3}$ is exactly the matrix product of $G_{1}$ and $G_{2}$, and every edge $e=(v_{i},v_{j})$ in $E_{3}$ corresponds to a path $[(v_{i},v_{k}),(v_{k},v_{j})]$ of length $2$. In the path, the first edge $(v_{i},v_{k})$ comes from $G_{1}$ and the second $(v_{k},v_{j})$ comes from $G_{2}$. Or saying, $(v_{i},v_{k})\in E_{1}$ and $(v_{k},v_{j})\in E_{2}$. Specially, if $G_{1}=G_{2}$, then we have a conclusion [22, Lemma 8.1.2].

The product of two $(m+1)$-uniform hypergraphs is similar. The product of $\mathcal{G}_{1}=(V_{1},\mathcal{E}_{1})$ and $\mathcal{G}_{2}=(V_{2},\mathcal{E}_{2})$ is an $(m+1)$-uniform hypergraph $\mathcal{G}=(V,\mathcal{E})$. For a directed hypergraph, $E=(T,h)\in\mathcal{E}$ if and only if there exists a hyperpath of length two $<E_{1}=(T,h_{1}),h_{1},E_{2}=(T_{2},h)>$ such that $E_{i}\in\mathcal{E}_{i}$ for $i=1,2$. For an undirected hypergraph, we only need to split every hyperedge $E=\{v_{i_{1}},\dots,v_{i_{m+1}}\}$ into $(m+1)$ directed hyperedges $\{(E\backslash\{v_{i_{j}}\},v_{i_{j}})\}_{j=1}^{m+1}$, and the other part is the same.

The connectivity of the hypergraph can be defined via the hyperpath. For the undirected graph, two vertices $v_{0},v_{l}$ is connected if there exists a hyperpath $<E_{1},v_{1},\dots,v_{l-1},E_{l}>,$ such that $v_{0}\in E_{1}$ and $v_{l}\in E_{l}$. Whether $v_{0}=v_{1}$ is not essential. If $v_{0}=v_{1}$, we can remove $E_{1}$ and $v_{1}$ from the hyperpath. This also works on $v_{l-1}=v_{l}$. Therefore without loss of generality we may assume $v_{0}\neq v_{1}$ and $v_{l-1}\neq v_{l}$ to be compatible with the definition of the hyperpath. Further we say an undirected hypergraph to be connected if every two vertices are connected. For the directed hypergraph, a vertex $v_{0}$ has access to a vertex $v_{l}$ if there exists a hyperpath $<E_{1},v_{1},\dots,v_{l-1},E_{l}>,$ such that $v_{0}\in T_{1}$ and $v_{l}=h_{l}$. We use $v_{i}\to v_{j}$ to represent this. The connectivity can be further distinguished. A directed hypergraph is said to be

• •

  strongly connected, if every vertex $v_{i}$ has access to every vertex $v_{j}$;

• •

  one-way connected, if for every two vertices $v_{i}$ and $v_{j}$, $v_{i}\to v_{j}$ or $v_{j}\to v_{i}$;

• •

  weak connected, if the base hypergraph (switching every directed hyperedge $E=(T,h)$ into an undirected hyperedge $T\cup\{h\}$) is connected.

For a connected hypergraph, the connectivity can be further measured by the vertex connectivity and the edge connectivity. A cutset $\widehat{V}\subseteq V$ of an undirected hypergraph $\mathcal{G}$ is a subset of $V$ such that if we remove the vertices in $\widehat{V}$ and all their incident hyperedges from $\mathcal{G}$, it will not be connected. The vertex connectivity $v(\mathcal{G})$ is the minimum size of the cutset. Let $\mathcal{G}(V\backslash\widehat{V})$ be the hypergraph induced by $V\backslash\widehat{V}$, or saying, removing the vertices in $\widehat{V}$ and all their incident hyperedges from $\mathcal{G}$. Then the vertex connectivity can be represent as

$$v(\mathcal{G})=\min_{\widehat{V}\subset V}\{|\widehat{V}|:\ \mathcal{G}(V\backslash\widehat{V}){\rm\ is\ not\ connected}\}.$$

For the directed hypergraph, removing a cutset will break the weak connectivity.

The hyperedge connectivity $e(\mathcal{G})$ is similar. $e(\mathcal{G})$ is the minimum number of hyperedges we need to remove to break the (weak) connectivity of a (directed) hypergraph.

$$e(\mathcal{G})=\min_{\widehat{\mathcal{E}}\subset\mathcal{E}}\{|\widehat{\mathcal{E}}|:\ \widehat{\mathcal{G}}=(V,\mathcal{E}\backslash\widehat{\mathcal{E}}){\rm\ is\ not\ connected}\}.$$

The vertex connectivity and the edge connectivity have some variations. The min-cut problem asks to split a graph (hypergraph) into two parts while minimizing the cost of edges (hyperedges) between these two parts, which is a variation of the edge connectivity. In the robust analysis of a complex network, the attacks on a vertex (hyperedge) will disable it, therefore leads to the vertex (hyperedge) connectivity.

Tensor is a high order generalization of the matrix, and a matrix is called a second order tensor. A tensor [12, 36, 49] is a multidimensional array. The order is the number of its indices. A tensor is denoted by calligraphic letters $\mathcal{A},\mathcal{B}$ and so on. The set of all the $m$th order $n$-dimensional real tensors is denoted as $T_{m,n}$.

There are different structures for tensor analysis. Based on the high order homogeneous polynomial, a tensor-vector product between $\mathcal{A}\in T_{m+1,n}$ and $x\in\mathbb{R}^{n}$ can be defined [36] as

$$\mathcal{A}x^{m}=(\sum_{i_{1},\dots,i_{m}=1}^{n}a_{i_{1},\dots,i_{m},j}x_{i_{1}}\cdots x_{i_{m}})_{j=1}^{m}\in\mathbb{R}^{n}.$$

Based on this the Z-eigenvalue and the Z-eigenvector $(\lambda,x)$ is defined [36] as

$$\mathcal{A}x^{m}=\lambda x,\ \|x\|_{\rm 2}=1.$$

The H-eigenvalue and the H-eigenvector $(\lambda,x)$ is introduced [36] as

$$\mathcal{A}x^{m}=\lambda x^{m}=\lambda(x_{1}^{m},\dots,x_{n}^{m})^{\top}.$$

The same as the quadratic form of matrices, a homogeneous polynomial is defined as

$$\mathcal{A}x^{m+1}=x^{\top}(\mathcal{A}x^{m})=\sum_{i_{1},\dots,i_{m+1}=1}^{n}a_{i_{1},\dots,i_{m},i_{m+1}}x_{i_{1}}\cdots x_{i_{m+1}}.$$

Only when $(m+1)$ is even, it can be positive or negative definite, as a polynomial of odd degree can never be positive or negative definite.

For the $2m$th order $n$-dimensional tensors, there is another structure, called the Einstein product. It is first proposed by Nobel laureate Einstein in [2] and there are some studies based on this structure [10, 33]. The Einstein product of tensors $\mathcal{A}\in\mathbb{R}^{n_{1}\times\cdots\times n_{k}\times p_{1}\times\cdots\times p_{m}}$ and $\mathcal{B}\in\mathbb{R}^{p_{1}\times\cdots\times p_{m}\times q_{1}\times\cdots\times q_{l}}$ is a tensor in $\mathbb{R}^{n_{1}\times\cdots\times n_{k}\times q_{1}\times\cdots\times q_{l}}$ such that

$$(\mathcal{A}*_{m}\mathcal{B})_{i_{1},\dots,i_{k},j_{1},\dots,j_{l}}=\sum_{t_{1},t_{2},\dots,t_{m}}a_{i_{1},\dots,i_{k},t_{1},\dots,t_{m}}b_{t_{1},\dots,t_{m},j_{1},\dots,j_{l}}.$$

The ring $(T_{2m,n},+,*_{m})$ is isomorphism to the matrix ring $(\mathbb{R}^{n^{m}\times n^{m}},+,\cdot)$ [10]. The identity tensor $\mathcal{I}$ satisfies $\mathcal{I}_{i_{1},\dots,i_{m},i_{1},\dots,i_{m}}=1$ for $1\leq i_{1},\dots,i_{m}\leq n$ and all the other elements are $0$. The generalized eigenvalue and the eigentensor [46] $(\lambda,\mathcal{X})$ is defined as

$$\mathcal{A}*_{m}\mathcal{X}=\lambda\mathcal{B}*_{m}\mathcal{X},$$

where $\mathcal{X}\in T_{m,n}$. When $\mathcal{B}=\mathcal{I}$, the generalized eigenvalue problem is just the classic eigenvalue problem.

In graph theory, for a graph $G=(V,E)$ with $n$ vertices, its adjacency matrix is $A\in\mathbb{R}^{n\times n}$, such that $a_{ij}=1$ if $(i,j)\in E$ and $a_{ij}=0$ otherwise. If we allow multiple edges, then $a_{ij}$ is the number of edges $(i,j)$ in $E$. Its degree diagonal matrix is $D={\rm diag}(\{d_{i}\}_{i=1}^{n})$. $d_{i}$ is the degree of the vertex $v_{i}$, satisfying $(d_{1},\dots,d_{n})^{\top}=A{\bf 1}$, where $\bf 1$ is the all-one column vector. For a directed graph, $d_{i}$ is the outdegree. The Laplacian matrix is defined as $L=D-A$ for both the directed and undirected graph.

The Laplacian matrix processes many interesting properties. The Laplacian matrix is diagonally dominant and all its diagonal elements are non-negative. For an undirected graph $G$, its Laplacian matrix is symmetric, therefore positive semi-definite. By its definition we have $L{\bf 1}=0$, therefore $\bf 1$ is an eigenvector corresponding to the smallest eigenvalue $0$. The second smallest eigenvalue $a(G)$ of $L$ is the algebraic connectivity of $G$, which is proposed by Fiedler in [19]. It can also be expressed by the Courant–Fischer theorem [6, 19]. Let ${\bf E}={\rm span}\{\bf 1\}$. We have [20, 50]

$$a(G)=\min_{\|x\|_{2}=1,\atop x\in{\bf E}^{\perp}}x^{\top}Lx.$$

(1)

For a directed graph, its algebraic connectivity is defined as (1) in [50]. However, as $L$ is not symmetric, $a(G)$ may be negative, as illustrated by the disconnected graph in [50]. For a real symmetric matrix $A$ of order $n$, let the eigenvalues of $A$ be arranged as: $\lambda_{1}(A)\leq\lambda_{2}(A)\leq\cdots\leq\lambda_{n}(A)$. It is well known that [50, Lemma 3]

$$\lambda_{1}\left(\frac{1}{2}\left(L+L^{\top}\right)\right)\leq a(G)\leq\lambda_{2}\left(\frac{1}{2}\left(L+L^{\top}\right)\right).$$

The algebraic connectivity is widely used as a measure of the robustness of complex networks [21, 23, 27, 41, 47, 16, 32]. When adding an edge, the algebraic connectivity helps to measure the increment of the robustness of the network. In the consensus problem of the graph, the convergence speed of a linear system

$$\dot{x}(t)=-Lx(t)$$

(2)

can be measured by the algebraic connectivity, the second smallest eigenvalue of $L$ [38].

The same as the graph, a tensor can be derived from a (directed) uniform hypergraph, called the adjacency tensor. For an undirected $(m+1)$-uniform hypergraph $\mathcal{G}=(V,\mathcal{E})$ with $|V|=n$, its adjacency tensor [17] is an $(m+1)$th order $n$-dimensional tensor $\mathcal{A}=\left(a_{i_{1},\dots,i_{m},i_{m+1}}\right)$, satisfying.

$$a_{i_{1},\dots,i_{m},i_{m+1}}=\left\{\begin{array}[]{cc}\frac{1}{m!}&{\rm If\ }\{i_{1},\dots,i_{m+1}\}\in\mathcal{E}\\ 0&{\rm otherwise.}\end{array}\right.$$

(3)

The Laplacian tensor can be defined as $\mathcal{L}=\mathcal{D}-\mathcal{A}$, where $\mathcal{D}$ is an $(m+1)$th order $n$-dimensional diagonal tensor of which diagonal elements are the degrees of vertices. In different structures, the coefficients $\frac{1}{m!}$ in (3) may differ. The definition of the degree may also differ. Hu and Qi defined the algebraic connectivity for the hypergraph using the $H$-eigenvalue and $Z$-eigenvalue [24] of its Laplacian tensor. There are also studies about spectrum [37, 52] under the same structure.

The Laplacian eigenmap [8, 7] is widely used in dimensionality reduction in data science. Given a dataset $(x_{1},\dots,x_{n})\in\mathbb{R}^{p\times n}$, a dimensionality reduction algorithm aims to project the dataset onto a space with lower dimension $q<p$, while keeping the distance between data to some extent. For each $x_{i}$, the Laplacian eigenmap algorithm connects a vertex $v_{i}$ with its neighbors, for example, $k$ nearest neighbors or neighbors of which distance is less than a given threshold $\epsilon$. Then a weighed graph is generated. The Laplacian eigenmap projects the dataset onto the subspace spanned by the eigenvectors corresponding to the $q$ smallest non-zero eigenvalues of the normalized Laplacian matrix. There are also some matrix-based hypergraph Laplacian eigenmap surveys.

Graph reduction techniques [42, 29, 1] reduce a hypergraph into a related graph, and therefore classic graph methods that allow multiple edges can be applied. Clique reduction [42, 29] splits a hyperedge $E=\{v_{i_{1}},\dots,v_{i_{m+1}}\}$ into a clique $r(E)=\{\{v_{i_{j}},v_{i_{k}}\}:\ 1\leq j<k\leq m+1\}$. For a directed hypergraph, the reduction of $(T=\{v_{i_{1}},\dots,v_{i_{m}}\},v_{i_{m+1}})$ is $r(E)=\{(v_{i_{j}},v_{i_{m+1}}):\ j\in[m]\}$. For a hypergraph $\mathcal{G}=(V,\mathcal{E})$, its reduced graph $r(\mathcal{G})=(V,r(\mathcal{E}))$ satisfies

$$r(\mathcal{E})=\bigsqcup_{E\in\mathcal{E}}r(E),$$

where $\bigsqcup$ is the disjoint union as we allows multiple edges in $r(\mathcal{G})$.

Graph reduction can help solving many problems. For example, a hypergraph cut $V=S\cup S^{\rm c}$ with penalty function

$$f(S)=\sum_{E\in\mathcal{E}}|E\cap S||E\cap S^{\rm c}|g(S,S^{\rm c})$$

(4)

can be naturally transformed into the graph cut problem of $r(\mathcal{G})$ by the clique reduction. $g(S,S^{\rm c})$ is a normalized function, such as $\frac{1}{|S|}+\frac{1}{|S^{\rm c}|}$ and $\frac{1}{{\rm vol}(S)}+\frac{1}{{\rm vol}(S^{\rm c})}$ where ${\rm vol}(S)=\sum_{v\in S}d_{v}$. We can also consider the isoperimetric number of a hypergraph $\mathcal{G}$ [31]

$$i(\mathcal{G})=\min_{S\subset V}\left\{\frac{|\{E\in\mathcal{E}:E\cap S\neq\emptyset,\ E\cap S^{\rm c}\neq\emptyset\}|}{\min\{|S|,|S^{\rm c}|\}}\right\},$$

which corresponds to the all-or-nothing cut function in [43]. It can be modeled by the circle reduction, which reduce a hyperedge $\{v_{i_{1}},\dots,v_{i_{m+1}}\}$ into

$$\{\{v_{i_{j}},\ v_{i_{j+1}}\}:\ j=1,\dots,m+1\},$$

where $v_{i_{m+2}}=v_{i_{1}}$. After the reduction, we have

$$i(r(\mathcal{G}))=2i(\mathcal{G}).$$

To fit the structure of the hypergraph better, we propose a new product between two tensors $\mathcal{A}\in T_{m+1,n}$ and $\mathcal{B}\in T_{k+1,n}$.

This product shows great compatibility with the matrix product. When $m=k=1$, the product is just the same as the standard matrix product. When $m=0$, it leads to a vector-tensor product $x^{\top}\mathcal{B}$ and if $k=1$ this time, it is the same as the standard vector-matrix product.

The associative law holds for this product. For $\mathcal{A},\mathcal{B}$ and $\mathcal{C}$ we can assert $(\mathcal{A}*\mathcal{B})*\mathcal{C}=\mathcal{A}*(\mathcal{B}*\mathcal{C})$. This product is not communicative.

We then focus the product between tensors in $T_{m+1,n}$, i.e., $k=m$. We define the diagonal tensor $\mathcal{D}={\rm diag}\left((a_{i})_{i=1}^{n}\right)$ as $d_{i,\dots,i}=a_{i}$ for $i\in[n]$ and $d_{i_{1},\dots,i_{m+1}}=0$ otherwise. The right identity $\mathcal{I}\in T_{m+1,n}$ is $\mathcal{I}={\rm diag}\left((1)_{i=1}^{n}\right)$, satisfying

$$\mathcal{A}*\mathcal{I}=\mathcal{A},\ \forall\mathcal{A}\in T_{m+1,n}.$$

We move on to the vector-tensor product, denoting it as $x^{\top}\mathcal{A}$ for $x\in\mathbb{R}^{n}$ and $\mathcal{A}\in T_{m+1,n}$. By the Definition 3.1 $x^{\top}\mathcal{A}\in\mathbb{R}^{1\times n}$ and

$$(x^{\top}\mathcal{A})_{j}=\sum_{i_{1},\dots,i_{m},i}x_{i}a_{i_{1},\dots,i_{m},j}\delta(i\in\{i_{1},\dots,i_{m}\})=\sum_{i_{1},\dots,i_{m}}a_{i_{1},\dots,i_{m},j}(x_{i_{1}}+\cdots+x_{i_{m}}).$$

Based on this we can define the eigenvalue and eigenvector under this product. The eigenvalue and eigenvector $(\lambda,x)$ satisfies

$$x^{\top}\mathcal{A}=\lambda x^{\top},$$

and can be solved by a linear equation

$$x^{\top}(\mathcal{A}-\lambda\mathcal{I})={\bf 0}.$$

The quadratic form $(x^{\top}\mathcal{A})x\in\mathbb{R}$ is

	$\displaystyle(x^{\top}\mathcal{A})x$	$\displaystyle=\sum_{i_{1},\dots,i_{m},i_{m+1},t}x_{t}a_{i_{1},\dots,i_{m},i_{m+1}}\delta(t\in\{i_{1},\dots,i_{m}\})x_{i_{m+1}}$
		$\displaystyle=\sum_{i_{1},\dots,i_{m},i_{m+1}}a_{i_{1},\dots,i_{m},i_{m+1}}x_{i_{m+1}}(x_{i_{1}}+\cdots+x_{i_{m}}).$

For $x^{\top}\in\mathbb{R}^{1\times n}$, $x^{\top}\mathcal{A}$ is a linear transform on the row vector space $\mathbb{R}^{1\times n}$. Therefore it can be represented by a matrix $A\in\mathbb{R}^{n\times n}$, denoting as $A=\phi(\mathcal{A})$. $A$ can be identified by directly computing $e_{k}^{\top}\mathcal{A}$, which leads to the $k$-th column of $A$.

	$\displaystyle(e_{k}^{\top}\mathcal{A})_{i}$	$\displaystyle=(0,\dots,0,1,0,\dots,0)\mathcal{A}=\sum_{j_{1},\dots,j_{m},t}e_{kt}a_{j_{1},\dots,j_{m},i}\delta(t\in\{j_{1},\dots,j_{m}\})$		(5)
		$\displaystyle=\sum_{j_{1},\dots,j_{m}}a_{j_{1},\dots,j_{m},i}\delta(k\in\{j_{1},\dots,j_{m}\}).$

As a result, the eigenvalue problem and the extremum of the quadratic form can be solved.

Subtensor under this product is not a cube as usual. Consider a linear equation $x^{\top}\mathcal{A}=b$. If we focus on the reaction of $\{x_{i}\}_{i\in I}$ and $\{b_{j}\}_{j\in J}$ where $I$ and $J$ are index sets, this will lead to an irregular subset of $\mathcal{A}$

$$\mathcal{A}[I,J]=\{l_{i_{1},\dots,i_{m},j}\}|\{i_{1},\dots,i_{m}\}\cap I\neq\emptyset,j\in J\}.$$

The influence of $J$ is the same as the common case of submatrix. However, the shape influenced by $I$ is irregular. When $\mathcal{A}$ is $3$rd-order, the location of elements in the slice is like a union of several crosses. We will still use the expression $x_{I}^{\top}L[I,J]$.

We retain the definition of the adjacency tensor in (3). For the directed hypergraph, the condition $\{i_{1},\dots,i_{m+1}\}\in\mathcal{E}$ will be $(\{i_{1},\dots,i_{m}\},i_{m+1})\in\mathcal{E}$. We can easily identify that the adjacency tensor is permutation invariant. For an undirected hypergraph and a permutation

$$\sigma:[m+1]\to[m+1],$$

we have $a_{i_{\sigma(1)},\dots,i_{\sigma(m+1)}}=a_{i_{1},\dots,i_{m+1}}$ because they correspond to the same hyperedge. For a directed hypergraph and a permutation $\sigma:\ [m]\to[m]$, we have $a_{i_{\sigma(1)},\dots,i_{\sigma(m)},i_{m+1}}=a_{i_{1},\dots,i_{m+1}}$.

Our product is compatible with the structure of the hypergraph. Suppose $\mathcal{A}_{i}$ is the adjacency tensor of $\mathcal{G}_{i}$ for $i=1,2$. Then $\mathcal{A}=\mathcal{A}_{1}*\mathcal{A}_{2}$ also corresponds to a hypergraph. Its hyperedge corresponds to a hyperpath of length $2$, the first hyperedge comes from $\mathcal{G}_{1}$ and the second comes from $\mathcal{G}_{2}$. Moreover, if $i_{1}\neq i_{m+1}$ holds for all $a_{i_{1},\dots,i_{m+1}}\neq 0$, then $\mathcal{A}$ is exactly an adjacency tensor and $a_{i_{1},\dots,i_{m+1}}=\frac{k}{m!}$ means there are exactly $k$ such hyperpaths. $i_{1}=i_{m+1}$ corresponds to the self-loop situation in graph theory.

The degree of vertices $(d_{i})_{i=1}^{n}$ can be defined as

$$(d_{i})_{i=1}^{n}={\bf 1}^{\top}\mathcal{A}=\left(m\sum_{i_{1},\dots,i_{m}}^{n}a_{i_{1},\dots,i_{m},i}\right)_{i=1}^{n}.$$

(6)

As the definition of the Laplacian tensor is $\mathcal{L}={\rm diag}(\{d_{i}\}_{i=1}^{n})-\mathcal{A}$, we have ${\bf 1}^{\top}\mathcal{L}={\bf 0}$. For a directed hypergraph, $(d_{i})_{i=1}^{n}$ is the indegree of vertices.

Although in the undirected hypergraph the definition of the degree of a vertex (6) leads to

$${\rm deg}(v_{i})=m|\{E\in\mathcal{E}:v_{i}\in E\}|,$$

we retain the coefficient $m$ so that in a directed hypergraph the total outdegree can match the total indegree. In a directed hypergraph, the definition (6) leads to the indegree of a vertex:

$${\rm deg}_{\rm in}(v_{i})=m|\{E=(T,h)\in\mathcal{E}:v_{i}=h\}|.$$

As the tail of a hyperedge contains $m$ vertices and the head contains only one, we have

	$\displaystyle\sum_{i}{\rm deg}_{\rm in}(v_{i})$	$\displaystyle=\sum_{i}m|\{E=(T,h)\in\mathcal{E}:v_{i}=h\}|$
		$\displaystyle=\sum_{i}|\{E=(T,h)\in\mathcal{E}:v_{i}\in T\}|=\sum_{i}{\rm deg}_{\rm out}(v_{i}),$

where the outdegree of vertex $v_{j}$ can be counted by

$${\rm deg}_{\rm out}(v_{i})=|\{E=(T,h)\in\mathcal{E}:v_{i}\in T\}|=\sum_{i_{1},\dots,i_{m},i_{m+1}}a_{i_{1},\dots,i_{m},i_{m+1}}\delta(i\in\{i_{1},\dots,i_{m}\}).$$

For the undirected graph, its adjacency matrix and Laplacian matrix is symmetric. There is also a similar result for the undirected hypergraph.

In the following parts, we will use $\widehat{i}$ as an abbreviation for the ordered indices $(i_{1},\dots,i_{m+1})$ or $(i_{1},\dots,i_{m})$ if the dimension of $\widehat{i}$ is not confusing.

There are different methods to analyze the properties of the hypergraph. The tensor analysis based on the Einstein product is not compatible with the hypergraph structure. When taking the Einstein product, we need the hypergraph to be even order uniform. Suppose we consider a $2m$-uniform hypergraph with $n$ vertices in the view of Einstein product. Two adjacent hyperedge in a hyperpath need to have exactly $m$ same vertices. If we consider the consensus problem (2), then $\mathcal{X}(t)\in T_{m,n}$ and $\mathcal{X}_{\widehat{i}}(t)$ does not correspond to a vertex $v_{i}$, but to an ordered set of $m$ vertices $(v_{i})_{i\in\widehat{i}}$. Meanwhile, the degree is defined for the $m$-vertices set rather than the vertex itself. This is not common in graph theory and complex network. Moreover, if we consider the splitting or clustering tasks, splitting the $m$-vertices set is meaningless and we only concern the clustering of these vertices themselves. The H-eigenvalue and the Z-eigenvalue structure partially resolve these problems. For (2) we have $x(t)\in\mathbb{R}^{n}$ and each $x_{i}(t)$ corresponds to a vertex $v_{i}$. However, there are still some problems. The positive semi-definite property still asks the order to be even. Also, both the H-eigenvalue and the Z-eigenvalue are high order polynomials. Computing them is much more difficult. Our tensor product structure fixes these problems. We can summarize its advantages as below. Compared with the Einstein product, our product has the following advantages.

1. 1.

   The Einstein product is only for the even order uniform hypergraph. Our product has no such limit.

2. 2.

   In a hyperpath, two adjacent hyperedges only need to have at least one common vertex under our product structure, rather than exactly $m$ common vertices for an $2m$-uniform hyperedge under the Einstein product.

3. 3.

   In the models like (2), each vertex is equipped with a state, rather than each $m$-vertices set. This is more natural and explicable in network theory. The clustering and partition can be done on the vertices, rather than on the $m$-vertices set.

4. 4.

   Much less computational cost.

Compared with other tensor products, our product has the following advantages.

1. 1.

   The positive semi-definite property of the Laplacian tensor needs the hypergraph to be even order uniform. Our product does not have such limit.

2. 2.

   Much less computational cost.

In some cases, our structure is consistent with the clique reduction. For $\mathcal{G}$ and its adjacency tensor $\mathcal{A}$, the adjacency matrix of its reduced graph $r(\mathcal{G})$ in the clique reduction is exactly $\phi(\mathcal{A})$, the matrix representation of the linear mapping of $\mathcal{A}$. This also happens on the Laplacian tensor and will be shown in the following section. This consistency makes our structure the same as a matrix-based analysis of the reduced graph in some cases. For example, consider the min-cut problem [42] with penalty function (4). As

$$f(S)={\bf 1}^{\top}_{S}\mathcal{L}{\bf 1}_{S}={\bf 1}^{\top}_{S}L_{r(\mathcal{G})}{\bf 1}_{S}$$

holds for the indicator vector ${\bf 1}_{S}$, a tensor-based analysis in our structure is the same as the matrix-based analysis for the reduced graph $r(\mathcal{G})$ if the matrix analysis method allows multiple edges. For example, the consensus problem of the hypergraph under this product has form

$$\dot{x}(t)=-x(t)^{\top}\mathcal{L},$$

which also corresponds to the continuous-time homogeneous polynomial dynamical system [13, Eq. (6)]. It is the same as a graph consensus problem (2) after the clique reduction. Some results related to the adjacency matrix also have this consistency, such as the Hoffman theorem [6, Thm 3.23].

However, our tensor product structure and the tensor-based analysis still have some unique advantages. Some graph methods that do not support multiple edges can not be applied to the reduced graph. For example, if we allow multiple edges, the relationship between the algebraic connectivity and the vertex connectivity in [20, 50] no longer holds, and the new relationship will be established in the following section using our tensor-based analysis. The hypergraph and the adjacency tensor also carry more information than the reduced graph and its adjacency matrix. Moreover, the hypergraph is a unique structure. Suppose a hyperedge $\{v_{1},\dots,v_{m+1}\}$ is split into a clique $\{\{v_{i},v_{j}\}:1\leq i<j\leq m+1\}$ and now we remove the vertex $v_{1}$. In the original hypergraph, the whole hyperedge is removed. In its adjacency tensor, we remove the elements of which indices contain $1$, leading to an $(m+1)$th order $(n-1)$-dimensional tensor. In the reduced graph, only $\{\{v_{1},v_{i}\}:1<i\leq m+1\}$ is removed and $\{\{v_{i},v_{j}\}:2\leq i<j\leq m+1\}$ are retained. In the adjacency matrix, it is an $(n-1)\times(n-1)$ matrix containing $\{\{v_{i},v_{j}\}:2\leq i<j\leq m+1\}$. According to this analysis, we have such conclusion.

In this and the next subsection we focus on the undirected hypergraph. Based on Lemma 3.1 we can defined the algebraic connectivity of the hypergraph by the quadratic form.

We have a direct conclusion.

We actually prove $\mathcal{L}$ is positive semi-definite and the algebraic multiplicity of eigenvalue $0$ equals to the number of its connected components. In this proof, a hypergraph is equivalent to a graph generated by the clique reduction. However, the advantages of the hypergraph over the graph reduction will be seen in Lemma 4.2.

As the Laplacian tensor of an undirected hypergraph is positive semi-definite and ${\bf 1}^{\top}\mathcal{L}=0$, there is another representation of the algebraic connectivity of the undirected hypergraph.

The eigenvector corresponding to the algebraic connectivity is called the Fiedler vector.

We further move onto the relationship between the algebraic connectivity and the vertex connectivity.

As the algebraic connectivity of an unconnected hypergraph is $0$, we have

Sparsity is an important hypothesis for the hypergraph. There are much more possible hyperedges in a hypergraph. A simple graph with $n$ vertices can only have $\frac{1}{2}n(n-1)$ edges at most. However, an $(m+1)$-uniform hypergraph can contain at most $\binom{n}{m+1}$ hyperedges. When $m\ll n$, this is almost an exponential rate of $m$. Specially, in a graph, a vertex can be incident to at most $(n-1)$ edges; In an $(m+1)$-uniform hypergraph, a vertex can be incident to $\binom{n-1}{m}$ hyperedges. This will boost up the eigenvalues of $\mathcal{A}$ and $\mathcal{L}$. For example, in a complete $5$-uniform hypergraph with $10$ vertices, each vertex is incident to $126$ hyperedges and the smallest non-zero eigenvalue of the Laplacian tensor is $560$. Therefore a sparsity hypothesis is needed. The sparsity $s$ of a hypergraph is defined as

$$s=\max_{v_{i},v_{j}}|\{E\in\mathcal{E}:\ v_{i},\ v_{j}\in E\}|.$$

We further prove that when removing a vertex and all its incident hyperedges, the upper bound for the loss of the algebraic connectivity is related to $s$.