An Introduction

Hypergraph is a **generalization** of the graph, wherein an edge can join **any** number of
vertices. In contrast, in an ordinary graph, an edge connects exactly two vertices. It is
often desirable to study hypergraphs where all hyperedges have the same cardinality;
a $k$-uniform hypergraph is a hypergraph where all its hyperedges have size $k$. **Hypergraph learning**
is a technique
conducting learning on a hypergraph structure.
Here, we provide an general introduction to **Hypergraph Learning**.

We will introduce the **basic concepts** of hypergraphs in the first place, then we will discuss several
classic methods of
**hypergraph generation**, and finally we will demonstrate four representative hypergraph learning
**examples** from the shallower to the deeper.

A hypergraph is a generalization of a graph in which an edge can join any number of
vertices. In contrast, in an ordinary graph, an edge connects exactly two vertices. It is
often desirable to study hypergraphs where all hyperedges have the **same cardinality**. For instance,
a $k$-uniform hypergraph is a hypergraph such that all
its hyperedges have **the same** size $k$. Noting that the size $k$ of a hyperedges means how many
vertices are conneected by the hyperedge. Let's take the following example to understand it:

- Vertex. Typically denoted by $V$, which represents the
**vertex set**of the hypergraph. - Hyperedge. Typically denoted by $E$, which means the
**hyperedge set**of the hypergraph. - Weight. Typically denoted by $W$, which represents the
**weight**of the**hyperedge**. - Degree. The degree of a
**vertex**represents how many**hyperedges**the vertex belongs to, and the degree of a**hyperedge**represents how many**vertices**whichthe hyperedge is connected to. - Incidence Matrix. $H_{i,j} = 1$ represents that vertex $i$ is in hyperedge $j$, $H_{i,j} = 0$ represents that vertex $i$ is not in hyperedge $j$. Noting that $H_{i,j}$ can also represent the importance of a vertex $i$ for a hyperedge $j$ when $0\le H_{i,j} \le 1$.

We take the demo of Hypergraph as an example to explain those components via illustrating them in the following table.

$e_1$ | $e_2$ | $e_3$ | |
---|---|---|---|

$v_1$ | 1 | 1 | 0 |

$v_2$ | 1 | 0 | 0 |

$v_3$ | 0 | 1 | 1 |

$v_4$ | 1 | 0 | 1 |

$v_5$ | 0 | 1 | 1 |

vertex | $v_1$ | $v_2$ | $v_3$ | $v_4$ | $v_5$ | hyperedge | $e_1$ | $e_2$ | $e_3$ |
---|---|---|---|---|---|---|---|---|---|

degree | 2 | 1 | 2 | 2 | 2 | degree | 3 | 3 | 3 |

Compared with graphs, hypergraphs have a stronger **expressive ability** and unique advantages for
modeling more **complex data**. Hypergraphs are useful in modeling such things as **satisfiability
problems**, **databases**, **machine learning**, and **Steiner tree problems**. They have
been extensively used in machine learning tasks as the **data model** and **classifier
regularization**. The applications include Recommendation System, image retrieval, and bioinformatics.
Representative hypergraph learning techniques include hypergraph spectral clustering that extends the
spectral graph theory with hypergraph Laplacian and hypergraph semi-supervised learning that
introduces extra hypergraph structural cost to restrict the learning results. For large-scale hypergraphs, a
distributed framework built upon Apache Spark is
also available.

To capture the **data correlation** with a hypergraph, the first step is to **construct** a
hypergraph from the data. The quality of the generated hypergraph structure directly
affects the **effectiveness** of the data correlation modeling. The problem of *how to
construct an effective hypergraph* is not trivial and thereby has been extensively
investigated. Hypergraph generation can generally be divided into two categories:
**implicit** and **explicit**.

The implicit hyperedges are defined as the hyperedges that are **not able** to be directly obtained from
raw data and need to be **reconstructed** by establishing representations and measurements. Implicit
methods can be further divided into **distance-based** and **representation-based** hypergraph
generation methods. These methods can be applied to the tasks where we can create the representation of each
subject and metrics to describe the similarity between samples.

Representation-based hypergraph generation methods formulate the relations among
vertices through **feature reconstruction**.

Distance-based hypergraph generation approaches
to exploit the relations among vertices using **the distance** in the **feature space**. The main
objective is to find **neighboring vertices** in the feature space and construct a hyperedge to connect
them. Specifically, there are two ways to construct this hyperedge: **nearest-neighbor searching** and
**clustering**. In nearest-neighbor-based methods, hyperedge construction needs to find the **nearest
neighbors** for each vertex. Different from nearest neighbor-based methods, the clustering-based
methods aim to directly **group** all vertices into clusters by a clustering algorithm such as k-means
and connect all vertices in **the same cluster** by a hyperedge. Noting that different **scales** of
clustering results can be used to generate **multiple hyperedges.**

Let's take an exmaple of Distance-based Hypergraph Generation in the following to help understand hypergraph
generation. We considered the examples where the feature space is a **two-dimensional space** and the
distance is
Euclidean distance, then several vertices
closest to a center point form a hyperedge.

Explicit hyperedges can be established straightforwardly because the input data may inherently contain some
**structural information**. Explicit methods can be further divided into attribute-based and network-based hypergraph
generation methods.

Network data are available in many applications, such as social networks, reaction networks, cellular networks, and brain networks. For these data, the network data can be used to generate subject correlations.

Attribute-based hypergraph generation methods are those methods that employ the
**attribute information** to construct a hyperedge. For example, the vertices sharing the
same attributes are linked by a hyperedge. Hyperedge in an attribute-based
hypergraph is regarded as a **clique**, and then the mean of the heat kernel weights of
pairwise edges in this clique can be used as the **hyperedge weight**.

Let's take an example of Attribute-based Hypergraph Generation in the following to help understand hypergraph
generation. We considered the examples where the **basic information** of several **classmates** is
given, and each classmate acts as a **vertex**, then classmates with the same information can form a
**hyperedge**.

student | Chinese | Math | English | Physics | Chemistry |
---|---|---|---|---|---|

1 | 1 | 1 | 1 | 1 | |

2 | 1 | 1 | 1 | ||

3 | 1 | 1 | 1 | ||

4 | 1 | 1 | |||

5 | 1 | 1 | 1 |

After a hypergraph is **constructed**, learning tasks, such as label prediction of unlabeled
vertices, dynamic structure update, and multi-modal learning
on this hypergraph, can
be performed. In the following, we briefly introduce several representative hypergraph learning
methods.

To apply hypergraph learning to a specific clustering task, there are three steps to do (Take the face recognition task as an example):

**Modeling the problem with the hypergraph structure.**A hypergraph can be built on the face image dataset where each face photo is associated with a vertex in the hypergraph.**Constructing the hypergraph based on the features, attributes, or prior correlations of the objects.**After extracting the features of all face images, distance-based or representation-based hyperedges can be generated and a hypergraph can be constructed accordingly.**Conducting learning on this hypergraph with an appropriate hypergraph learning method.**The eigenvectors associated with the $k$ smallest eigenvalues of the Laplacian matrix can be calculated to obtain a $k$-way partition. And a clustering algorithm like k-means can be run on these vectors to divide them into $k$ clusters.

The figures above describes the process of how the hypergraph learning methods handle the clustering task.

MNIST is a **picture dataset** of handwritten digits for **Classification**. Here we'll use the MNIST
dataset which consists of greyscale handwritten digits. Each image is 28x28 pixels, you can see a sample
below.

Our goal is to build a hypergraph that can take one of these images and predict the digit in the image. Let's get straight into it. Below is the full hypergraph we built, which contains all nodes in the test and training sets.

For better analysis, we extract the test set separately and show its **corresponding hyperedge**.

Experiments show that the hypergraph model can well represent the **correlation information ** between
various pictures and extract **similar** (common) features. Below are several representative hyperedges
and the nodes they contain.

t-DHL **leverage** a **tensor representation** to characterize the **dynamic hypergraph** structure
more flexibly. Unlike the incidence matrix, not only weights but **the number and order** of hyperedges
can also be changed when optimizing the tensor representation. It is that the tensor representation can
describe the hyperedges of all orders, which is a complete representation of hypergraph structure. The
tensor-based dynamic hypergraph learning is formulated as a **biconvex model** to ensure that the model
can converge to the optimal solution **efficiently**. T-DHL has the potential of applying to large-scale
data due to its high effectiveness and **low computational cost**.

**Microblog sentiment prediction** is one of the common applications of hypergraph with
wide application prospects. With the increasing proportion of multimodal tweets
consisting of **images**, **texts**, and **emoticons**, new challenges have been raised to the
existing sentiment prediction schemes. More crucially, it remains an open problem to
model the **dependency** among multiple modalities, where one or more modalities may
be **missing**. Therefore, a novel **Bi-layer Multimodal Hypergraph learning** (Bi-MHG) is
put forward toward robust sentiment prediction of multimodal tweets to tackle the
above challenges. In particular, Bi-MHG has a two-layer structure: The first layer, that
is, a tweet-level hypergraph, learns the **tweet-feature correlation** and the **tweet
relevance** to predict the sentiments of unlabeled tweets. The second layer, that is, a
featurelevel hypergraph learns the **relevance** among different feature modalities
(including the midlevel visual features in Sentibank) by leveraging **prior multimodal
sentiment dictionaries**. These two layers are connected by sharing the relevance of
multimodal features in a unified bilayer learning scheme. In such a way, Bi-MHG
explicitly models the modality relevance **rather than** implicitly weighting multimodal
features adopted in the existing Multimodal Hypergraph learning. Finally, a nested
alternating optimization is further proposed for Bi-MHG parameter learning.

**MHGNN** is a **multi-scale** representation learning method on hypergraph for **3D shape
retrieval** and **recognition**. **Effective** 3D shape retrieval and recognition are
challenging
but important tasks in computer vision research field, which have attracted much
attention in recent decades. Although recent progress has shown significant
improvement of deep learning methods on 3D shape retrieval and recognition
performance, it is still under investigated of *how to jointly learn an optimal
representation of 3D shapes considering their relationships*. In this method, the
**correlation** among 3D shapes is formulated in a hypergraph and a **hypergraph
convolution process** is conducted to learn the representations. Here, multiple
representations can be obtained through different convolution layers, leading to multi-scale representations
of 3D shapes. A

fusion module is then introduced to combine
these representations for 3D shape retrieval and recognition. MHGNN can investigat
the high-order correlation among 3D shapes, and the **joint multi-scale representation**
can be more robust for comparison.

**Hypergraph Neural Network** (HGNN) is currently the **de-facto** method for hypergraph
representation learning. However, HGNN aims at single hypergraph learning and uses
a **pre-concatenation approach** when confronting multi-modal datasets, which leads to
*sub-optimal exploitation of the inter-correlations of multi-modal hypergraphs*. HGNN
also suffers the *over-smoothing issue*, that is, its performance drops significantly when
layers are stacked up. To resolve these issues, **Residual enhanced Multi-Hypergraph
Neural Network** is put forward, which can not only fuse multi-modal information from
each hypergraph effectively, but also **circumvent **the over-smoothing issue associated
with HGNN.