In order to efficiently build a hypergraph structure, we usually extract the features of 3D objects and then build implicit hypergraphs. 3D objects can be described by multiple modalities, including point clouds, views, grids, and voxels. We can extract the descriptors of their respective modalities through the corresponding deep neural networks, such as dynamic graph CNN (DGCNN) [17] and PointNet (PointNet) [18] for point cloud data, multi-view convolutional neural networks (MVCNN) [19], and group-view convolutional neural networks (GVCNN) [20] for the multi-view data. When multi-modal features have been obtained, we can build a hypergraph structure for each kind of features.

Here, each 3D object can be represented by a vertex in the hypergraph. Each time, one object is selected as the centroid in a feature space, and its nearest neighbors can be connected by a corresponding hyperedge. This process is repeated until all objects have been selected as the centroid once in this feature space. Every feature and possible feature combination can be used in this process. In this way, we can achieve multiple hypergraphs, represented by incidence matrices **H**1*,* **H**2*,...,* **H***m* to formulate their correlations under different modalities. The pipeline is demonstrated in Fig. 4.11. We can further concatenate these incidence matrices along the axes of hyperedges to integrate these hypergraphs and obtain the complete hypergraph structure, as shown in Fig. 4.12.

#### *4.4.2 Recommender System*

In a recommender system, the relationship between users and items can be represented by a bipartite graph, that is, if an item is in a user's recommendation list, then we connect the user vertex with the item vertex. This bipartite graph can

**Fig. 4.11** An example of hypergraph modeling for multi-modal 3D objects

**Fig. 4.12** An illustration of multi-hypergraph combination. This figure is from [5]

**Fig. 4.13** An example of hypergraph modeling for a recommender system

be simply transformed into a hypergraph, where vertices on one side remain and vertices on the other side become hyperedges, as shown in Fig. 4.13. In this way, each user can be represented as a vertex in the hypergraph, and the users shared the same items can be connected by a corresponding hyperedge here. If the item is regarded as a vertex, then the hyperedges are generated using shared users. This hypergraph generation procedure follows the attribute-based strategy.

Mathematically, the ranking matrix of the recommender system equals to the incidence matrix of the corresponding hypergraph. With this transformation, we can solve the problem in recommender systems via hypergraph learning methods. In fact, undirected bipartite graph modeling and hypergraph modeling are interchangeable in some cases. If the edges in bipartite graph are weighted, we can use the hyperedge-dependent vertex weights accordingly.

#### *4.4.3 Computer-Aided Diagnosis*

In computer-aided diagnosis, the main objective is to measure whether a coming patient has some specific disease or not, or how serious the disease it is. For diagnosis, the experience and knowledge are from previous medical records. Casebased diagnosis has shown importance in practice. For AI-based computer-aided diagnosis, it is important to explore the existing labeled training data, which could be very few in some cases. These medical records may contain different examine files, MR images, CT images, and other types of data.

A conventional pipeline for computer-aided diagnosis is first extracting features from clinical text or medical imaging data and then applying computer programs to automatically categorize healthy people and patients. The commonly used techniques involve natural language processing, medical imaging analysis, machine learning, etc. It is worth noting that the existing methods mostly focus on individual subject classification. Under such circumstances, how to model the correlation among these subjects, including the training data and the coming patient (the testing data), is an important but difficult task.

**Fig. 4.14** An example of hypergraph modeling for computer-aided diagnosis

Here, a hypergraph at the subject level, i.e., each vertex stands for a subject, can be generated, where the hyperedges can be created using the distance-based method or attribute-based method. Given the MR images or other medical data, the features can be used to measure the distance between each two subjects. Then, the *k*-NN scheme can be used to select nearest neighbors for a centroid vertex and then generate a corresponding hyperedge, as shown in Fig. 4.14.

Another type of applications is to model the inter-correlation in one medical image, such as gigapixel whole-slide histopathological images (WSIs). Survival prediction is an important task in medical image analysis, which targets on modeling the life duration of a patient using WSIs. Different from traditional images, WSIs are with very large size and rich details. Therefore, traditional image representation methods do not work well in this task. To formulate the inter-correlation inside a WSI, a hypergraph can be generated, which the patch correlations are generated. A group of patches can be sampled from the original WSI, such as 2000 or 8000 patches. Then, these patches are represented as vertices in the corresponding hypergraph. The hyperedges can be generated based on either the visual feature of these patches or the spatial information, or both of them, using the distance-based hypergraph generation methods.

#### *4.4.4 Brain Network*

Recently, the development of neuroimaging techniques has provided a way to understand the brain network on a large scale. Studies have shown that the interaction relationships in the brain, from neuronal information flow to wholebrain functional networks, are the basis of its functionality. Therefore, formulating

**Fig. 4.15** An example of hypergraph modeling for brain network

the brain as a complex network and decoding its signals may further deepen our understanding of the human cognitive processes. The conventional functional network is usually modeled and represented based on pairwise correlations between two brain regions. However, neurologically, a brain region predominantly interacts with one or more other brain regions.

When using hypergraphs to model a single brain network, the vertices denote brain regions, and the hyperedges represent the interactions among multiple regions. Each element in the incidence matrix corresponds to the contribution of the brain region to the specific function, as shown in Fig. 4.15. In this process, each region can be selected as the centroid, and its nearest neighbor regions in the feature space can be selected and connected by a corresponding hyperedge.

#### **4.5 Hypergraph Modeling in Next Stage**

In this part, we discuss future research topics of hypergraphs modeling to render them more accurate and flexible, including adaptive hypergraph modeling, generative hypergraph modeling, and knowledge hypergraph generation.

#### *4.5.1 Adaptive Hypergraph Modeling*

Having initialized the hypergraph structure, the structure is fixed during the learning process. However, the initial hypergraph structure constructed by existing hypergraph modeling methods contains many noisy connections that may be destructive for the learning process. Therefore, the original structure needs to be optimized according to the data and downstream tasks to cut down on structure noise. Although there are some existing work on hypergraph structure optimization, these efforts are still far from reaching the goal of accurately modeling of complex data correlations.

At this stage, the selection of hypergraph generation methods still depends on experience, rather than a theoretical strategy. A possible route to conduct automate hypergraph generation is to create various hypergraphs via different approaches and then group them together to obtain a more complex but relatively complete hypergraph. The grouping weights can be learned in the training stage. Another way is to update the incidence matrix of hypergraph structure, which can be either directly optimized as learnable parameters or indirectly optimized via metric learning.

#### *4.5.2 Generative Hypergraph Modeling*

The generative models are a set of models that learn the distribution from the observed data and generate new data instances based on probability. They have been widely used in different tasks such as generation, synthesis, translation, reconstruction, prediction, etc. In recent years, with the development of deep graph representation learning, deep graph generative models have attracted much attention. Given a series of training graph data (assumed to be taken from the same distribution), the neural network is trained as a graph generation model. Inspired by these generative models, building a hypergraph by estimating the distribution of latent structures from observed data may be a viable way. Given a set of training hypergraphs or sampling signals from every vertex, the distribution can be implicitly or explicitly derived by combining hypergraph embeddings and generative models.

However, there is still a long way to go for hypergraph generative models to become practical. Unlike simple graphs whose distributions are the joint distributions of all pairwise correlations between data, the distribution of a hypergraph structure is the joint distribution of all high-order correlations among data. Therefore, the joint distribution is high dimension, and the variables are dependent on each other. Estimating the density function is intractable with considerable complexity. Furthermore, due to the high-dimensional issue, a large amount of observed data is required to make the density estimate closer to the true distribution, which is difficult to obtain in practical applications. Despite the above obstacles, generative hypergraph modeling is an area worth exploring in the future and will become useful in many areas, such as simulations of complex physical systems, trajectory tracking system identification, and community detection.

#### *4.5.3 Knowledge Hypergraph Generation*

Knowledge hypergraph has attracted much attention in recent years since it can store facts using high-arity relations. In a knowledge hypergraph H = *(*V *,* E *)*, the vertices represent the set of entities, and hyperedges demonstrate the high-arity relations. The basic unit is a fact based on a high-arity relation. Unlike knowledge graph that only uses binary relations, the relations in knowledge hypergraph are defined on any number of entities.

Although there have been several pieces of work targeting at knowledge hypergraph embedding and completion, such as Multi-fold TransH (m-TransH) [21], Hyper-relational Knowledge Graph Embedding (HINGE) [22], N-ary Link Prediction (NaLP) [23], they are mostly based on the assumption that there exists an initial knowledge hypergraph or some hyper-relational links. Few efforts have been made on the initial knowledge hypergraph generation. Actually, manually mining the hyper-relations among entities requires much time and effort. Therefore, it is of great significance to study the knowledge hypergraph generation methods for efficient and comprehensive knowledge inference.

#### **4.6 Summary**

In this section, we introduce the hypergraph modeling methods, which are categorized as the implicit type and the explicit type. The implicit hyperedges can be used in tasks in which we can represent each subject and develop metrics to evaluate sample similarity. By using the sparse representation, representation-based approaches might mitigate the impact of the noise vertices in comparison with distance-based ones. Explicit hyperedges are more appropriate when input data may already have certain structural details. In general, choosing a suitable hyperedge generation method is important for a specific task. Finally, adaptive and generative hypergraph modeling are worth further exploring to adjust hypergraph structures based on the data and the on-going tasks.

#### **References**

**Open Access** This chapter is licensed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license and indicate if changes were made.

The images or other third party material in this chapter are included in the chapter's Creative Commons license, unless indicated otherwise in a credit line to the material. If material is not included in the chapter's Creative Commons license and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder.

## **Chapter 5 Typical Hypergraph Computation Tasks**

**Abstract** After hypergraph structure generation for the data, the next step is how to conduct data analysis on the hypergraph. In this chapter, we introduce four typical hypergraph computation tasks, including label propagation, data clustering, imbalance learning, and link prediction. The first typical task is label propagation, which is to predict the labels for the vertices, i.e., assigning a label to each unlabeled vertex in the hypergraph, based on the labeled information. In general cases, label propagation is to propagate the label information from labeled vertices to unlabeled vertices through structural information of the hyperedges. In this part, we discuss the hypergraph cut on hypergraphs and random walk interpretation of label propagation on hypergraphs. The second typical task is data clustering, which is formulated as dividing the vertices into several parts in a hypergraph. In this part, we introduce a hypergraph Laplacian smoothing filter and an embedded model for hypergraph clustering tasks. The third typical task is cost-sensitive learning, which targets on learning with different mis-classification costs. The fourth typical task is link prediction, which aims to discover missing relations or predict new coming hyperedges based on the observed hypergraph.

#### **5.1 Introduction**

In previous chapters, we have introduced how to generate the hypergraph structure given observed data. After the hypergraph generation step, how to use this hypergraph for different applications becomes the key task. Hypergraph has the potential to be used in different areas, such as social medial analysis, medical and biological applications, and computer vision. We notice most of the applications can be categorized into several typical tasks and follow similar application patterns. In this chapter, we introduce several typical hypergraph computational tasks, which can be used for different applications.

More specifically, four typical tasks, including label propagation, data clustering, cost-sensitive learning, and link prediction, are introduced in this chapter. The first typical task is label propagation, which is also one of the most widely used methods in machine learning. The objective of label propagation is to assign a label to each unlabeled data. In general cases, label propagation on hypergraph is to propagate the label information from labeled vertices to unlabeled vertices through structural information of the hyperedges. Random walk is a basic processing for information propagation, which also plays a fundamental role in this process. We then review the hypergraph cut on hypergraphs and random-walk-based label propagation on hypergraphs. We introduce the label propagation process on single hypergraph and multi-hypergraphs [1, 2], respectively, in this part.

The second typical task is data clustering, targeting on grouping data into different clusters. We introduce how to conduct data clustering using hypergraph computation. The hypergraph structure can be used as guidance to the clustering criteria. Two types of hypergraph clustering methods are introduced, including structural hypergraph clustering and attribute hypergraph clustering, due to the different data information in the hypergraph. In structural hypergraph, the clustering tasks only use structural information, while in attribute hypergraph, each vertex is usually accompanied by attribute information from the real world. We introduce a hypergraph Laplacian smoothing filter and an embedded model specifically for hypergraph clustering tasks that named adaptive hypergraph auto-encoder (AHGAE) [3].

The third typical task is cost-sensitive learning, which is to solve the learning task under the scenario with different mis-classification costs, such as confronting the imbalanced data distribution issue. Here, we introduce two hypergraph computation methods, i.e., cost-sensitive hypergraph computation [4] and cost interval optimization for hypergraph computation [5]. First, we introduce a cost-sensitive hypergraph modeling method, in which the cost for different objectives is fixed in advanced. As the exact cost value may be not easy to be determined, we then introduce a cost interval optimization method, which can utilize the cost chosen inside the interval while generating data with high-order relations.

The fourth typical task is link prediction, which is to predict data relationship and can be used for recommender system and other applications. Here, the hypergraph link prediction is to mine the missing hyperedges or predict new coming hyperedges based on the observed hypergraph. We introduce a variational autoencoder for heterogeneous hypergraph link prediction [6]. It aims to learn the low-dimensional heterogeneous hypergraph embedding based on the Bayesian deep generative strategy. The heterogeneous encoder generates the vertex embedding and hyperedge embedding, and the hypergraph embedding is the combination of them. The hypergraph decoder reconstructs the incidence matrix based on the vertex embedding and the hyperedge embedding, and the heterogeneous hypergraph is generated based on the reconstructed incidence matrix.

Part of the work introduced in this chapter has been published in [1–6].

#### **5.2 Label Propagation on Hypergraph**

This section mainly introduces the label propagation task on hypergraph. We first introduce the basic assumptions of the label propagation process. Given a set of vertices on a hypergraph, a part of vertices is labeled, while other vertices are unlabeled. The task is to predict the label information of these unlabeled data given the label information and the hypergraph structure. Figure 5.1 shows that the label propagation process is to propagate the label information from these labeled vertices to the unlabeled vertices.

When propagating label information, vertices within the same hyperedge are more likely to have the same label because they characterize themselves with similar attributes in some aspects, and therefore, they have a higher probability of sharing the same label. Under this assumption, the label propagation task can be transformed into a hypergraph cut. In a hypergraph cut, the goal is to make the cut edges as sparse as possible, with each vertex set after the cut as dense as possible. After cutting the hypergraph, different sets of vertices have different labels. This approach satisfies the goal based on the above assumption. The form of the hypergraph cut can be described below.

Suppose a vertex set *S* ∈ V and its compliment *S*. There is a cut that splits the V into *S* and *S*. A hyperedge *e* is cut if it is incident with the vertices in both *S* and *S*. Define the hyperedge boundary *∂S* as the cut hyperedges, i.e., *∂S* = {*e* ∈ E |*e*∩*S* = ∅*, e* ∩ *S* = ∅}, and the volume of *S*, *vol(S)*, be the sum of the degrees of vertices in *S*, i.e., *vol(S)* = - *v*∈*S* **D***v(v)*. It can be shown as

$$vol(\partial S) = \sum\_{e \in \partial S} w(e) \frac{|e \cap S| |e \cap S|}{\mathbf{D}\_\ell(e)}.\tag{5.1}$$

The derivation is shown as follows, and the details can be found in [7]. Suppose that hyperedge *e* is a clique, i.e., a fully connected graph. To avoid confusion, the edges in the clique are called subedges. Then, the weight *w(e)* **D***e(e)* is assigned to each subedge. When the hyperedge *e* is cut, |*e*∩*S*|×|*e*∩*S*| subedges are cut. The volume of the cut is the sum of the weights over these subedges. Recall that our goal is to make the cut edges as sparse as possible, with each vertex set after the cut as dense

**Fig. 5.2** An illustration of the hypergraph label propagation based on random walks

as possible. Based on the goal, the objective partition formula is written as

$$\arg\min\_{S\subset \mathcal{Y}} c(S) = vol(\partial S) \left( \frac{1}{vol(S)} + \frac{1}{vol(\overline{S})} \right). \tag{5.2}$$

There are many methods to propagate label information on a hypergraph, and the propagation based on random walks is the most widely used. The following describes the label propagation by random walk, and the illustration is shown as Fig. 5.2. Suppose that the current position is *u* ∈ V , and at first, we walk to a hyperedge *e* over all hyperedges incident with *u* with probability *w(e)*, and then we sample a vertex *v* ∈ *e* uniformly. By generalizing from typical random walks on graphs, we use **P** as the transition probability matrix of the random walk on a hypergraph, and the element *p(u, v)* is defined as follows:

$$p(\boldsymbol{\mu}, \boldsymbol{v}) = \sum\_{e \in \mathcal{E}} w(e) \frac{\mathbf{H}(\boldsymbol{\mu}, e)}{\mathbf{D}\_{\boldsymbol{v}}(\boldsymbol{\mu})} \frac{\mathbf{H}(\boldsymbol{v}, e)}{\mathbf{D}\_{\boldsymbol{\epsilon}}(e)}. \tag{5.3}$$

The formula can be organized into a matrix form as **P** = **D**−1 *v* **HWD**−1 *e* **H**. The stationary distribution *π* of the random walk is defined as

$$
\pi(\upsilon) = \frac{d(\upsilon)}{vol(\mathcal{V})},\tag{5.4}
$$

where **D***v(v)* is denoted by *d(v)* for short and *vol(.)* is the volume of the vertices in set *S*, defined as *vol(S)* = - *v*∈*S d(v)*. The formula can be derived from

$$\sum\_{u \in \mathcal{V}} \pi(u) \, p(u, v) = \sum\_{u \in \mathcal{V}} \frac{d(u)}{vol(\mathcal{V})} \sum\_{e \in \mathcal{E}} w(e) \frac{\mathbf{H}(u, e)}{\mathbf{D}\_v(u)} \frac{\mathbf{H}(v, e)}{\mathbf{D}\_e(e)}$$

$$= \frac{1}{vol(\mathcal{V})} \sum\_{e \in \mathcal{E}} w(e) \sum\_{u \in \mathcal{V}} \mathbf{H}(u, e) \frac{\mathbf{H}(u, e)}{\mathbf{D}\_e(e)} \tag{5.5}$$

$$= \frac{1}{vol(\mathcal{V})} \sum\_{e \in \mathcal{E}} w(e) \mathbf{H}(v, e) = \frac{d(v)}{vol(\mathcal{V})}.$$

The objective function Eq. (5.2) can be written as

$$c(S) = \frac{vol(\partial S)}{vol(\mathcal{V})} \left( \frac{1}{vol(S)/vol(\mathcal{V})} + \frac{1}{vol(\overline{S})/vol(\mathcal{V})} \right),\tag{5.6}$$

and then we arrive at

$$\frac{vol(S)}{vol(\mathcal{Y})} = \sum\_{v \in \mathcal{S}} \frac{d(v)}{vol(\mathcal{Y})} = \sum\_{v \in \mathcal{Y}} \pi(v),\tag{5.7}$$

where *vol(S) vol(*V *)* is the probability of random walks to vertex in *S*. It can then be shown as

$$\begin{split} \frac{vol(\partial S)}{vol(\mathcal{V})} &= \sum\_{e \in \partial S} \frac{w(e)}{vol(\mathcal{V})} \frac{|e \cap S| |e \cap \overline{S}|}{\delta(e)} \\ &= \sum\_{e \in \partial S} \sum\_{u \in e \cap S} \sum\_{v \in e \cap \overline{S}} \frac{w(e)}{vol(\mathcal{V})} \frac{\mathbf{H}(u, e)\mathbf{H}(v, e)}{\delta(e)} \\ &= \sum\_{e \in \partial S} \sum\_{u \in e \cap \overline{S}} \sum\_{v \in e \cap \overline{S}} w(e) \frac{d(u)}{vol(\mathcal{V})} \frac{\mathbf{H}(u, e)}{d(u)} \frac{\mathbf{H}(v, e)}{\delta(e)} \\ &= \sum\_{u \in \epsilon \cap \overline{\mathcal{V}}} \sum\_{v \in \partial \overline{\mathcal{S}}} \frac{d(u)}{vol(\mathcal{V})} \sum\_{e \in \partial \overline{\mathcal{S}}} w(e) \frac{\mathbf{H}(u, e)}{d(u)} \frac{\mathbf{H}(v, e)}{\delta(e)} \\ &= \sum\_{u \in \mathcal{S}} \sum\_{v \in \overline{\mathcal{S}}} \pi(u) \operatorname{p}(u, v), \end{split} \tag{5.8}$$

where the ratio *vol(∂S) vol(*V *)* is the probability with the random walk from a vertex in *S* to *S* under the stationary distribution. It can be seen that the hypergraph normalized cut criterion is to search a cut such that the probability with which the random walk crosses different clusters is as small as possible, while the probability with which the random walk stays in the same cluster is as large as possible.

Let us review the objective function Eq. (5.2). Note that it is NP complete, while it can be relaxed into the following optimization problem as

$$\begin{aligned} \arg\min\_{\mathbf{f}\in\mathbb{R}^{|V|}}\mathcal{Q}(\mathbf{f}) &= \frac{1}{2} \sum\_{e\in\mathcal{E}} \sum\_{\{u,v\}\in e} \frac{w(e)}{\delta(e)} \left( \frac{\mathbf{f}(u)}{\sqrt{d(u)}} - \frac{\mathbf{f}(v)}{\sqrt{d(v)}} \right)^2, \\\ s.t. &\quad \sum\_{v\in\mathcal{V}} \mathbf{f}^2(v) = 1, \sum\_{v\in\mathcal{V}} \mathbf{f}(v)\sqrt{d(v)} = 0,\end{aligned} \tag{5.9}$$

where **f** is the to-be-learned score vector. Since the goal is label propagation, it can be arrived at for some labeled data. The optimization problem becomes the

#### 78 5 Typical Hypergraph Computation Tasks

transductive inference problem as

$$\arg\min\_{\mathbf{f}\in\mathbb{R}^{|\mathcal{V}|}} \{\mathcal{Q}(\mathbf{f}) + \lambda R\_{emp}(\mathbf{f})\},\tag{5.10}$$

where the regularizer term is *Ω(***f***)*, the empirical loss term is *Remp(***f***)* = *f* −*y* - 2 = *v*∈V *(***f***(v)* − **y***(v))*2, **y** ∈ R|V | is the label vector, and *λ* is the balance parameter. Let us assume that the *i*-th vertex is labeled, and the elements of **y** are all 0 except the *i*-th value that is 1. The regularizer *Ω(***f***)* can be turned into

$$\begin{split} \mathcal{Q}(\mathbf{f}) &= \frac{1}{2} \sum\_{e \in \mathcal{E}} \sum\_{\{u,v\} \in e} \frac{w(e)}{\delta(e)} \left( \frac{\mathbf{f}(u)}{\sqrt{d(u)}} - \frac{\mathbf{f}(v)}{\sqrt{d(v)}} \right)^2 \\ &= \sum\_{e \in \mathcal{E}} \sum\_{\{u,v\} \in \mathcal{V}} \frac{w(e)\mathbf{H}(u,e)\mathbf{H}(v,e)}{\delta(e)} \left( \frac{\mathbf{f}^2(u)}{d(u)} - \frac{\mathbf{f}(u)\mathbf{f}(v)}{\sqrt{d(u)d(v)}} \right) \\ &= \sum\_{u \in \mathcal{V}} \mathbf{f}^2(u) \sum\_{e \in \mathcal{E}} \frac{w(e)\mathbf{H}(u,e)}{d(u)} \sum\_{v \in \mathcal{V}} \frac{\mathbf{H}(v,e)}{\delta(e)} \\ &\quad - \sum\_{e \in \mathcal{E}} \sum\_{u,v \in \mathcal{V}} \frac{\mathbf{f}(u)\mathbf{H}(u,e)w(e)\mathbf{H}(v,e)\mathbf{f}(v)}{\sqrt{d(u)d(v)}\delta(e)} \\ &= \mathbf{f}^\top(\mathbf{I} - \Theta)\mathbf{f}, \end{split} \tag{5.11}$$

where *Θ* = **D**− 1 2 *v* **HWD**−1 *e* **HD**− 1 2 *v* . The hypergraph Laplacian is denoted by *Λ* = **I** − *Θ*. Therefore, the objective function can be rewritten as

$$
\mathcal{Q}(\mathbf{f}) = \mathbf{f}^\top A \mathbf{f}.\tag{5.12}
$$

The optimization function can be turned into

$$\arg\min\_{\mathbf{f}\in\mathbb{R}^{|\mathcal{V}|}} \{\mathbf{f}^{\top}A\mathbf{f} + \lambda\|\mathbf{f} - \mathbf{y}\|^2\}. \tag{5.13}$$

There are two ways to solve the above problem. The first one is differentiating the objective function in Eq. (5.13) with respect to *f* , and it can be obtained as

$$\mathbf{f} = \left(\mathbf{I} + \frac{1}{\lambda}\boldsymbol{A}\right)^{-1}\mathbf{y}.\tag{5.14}$$

The second one is an iterative method. Similar to the iterative approach in [8], Eq. (5.13) can be efficiently solved by an iterative process. The process is illustrated in Fig. 5.3. The **f** *t*+1 can be obtained from the last iterative **f** *t* and **y**, and the procedure is repeated until convergence.

**Fig. 5.3** The iterative solution of Eq. (5.13). This figure is from [1]

This process will converge to the solution Eq. (5.14). To prove it, we first prove that the eigenvalues of *Θ* are in [−1*,* 1]. Since *Θ* = **D**−1*/*2 *v* **HWD**−1 *e* **HD**−1*/*2 *v* , we find that its eigenvalues are in [−1*,* 1]. Therefore, (**I**±*Θ*) are positive semi-definite.

The convergence of the iterative process is proved in [1]. Without loss of generality, we assume **f** *(*0*)* = *y*. From the iterative process, it can be obtained that

$$\begin{split} \mathbf{f}^{(t)} &= \left(\frac{\lambda}{1+\lambda}\right) \sum\_{l=0}^{t-1} \left(\frac{1}{1+\lambda} \Theta\right)^{l} \mathbf{y} + \left(\frac{1}{1+\lambda} \Theta\right)^{l} \mathbf{y} \\ &= (1-\xi) \sum\_{l=0}^{t-1} (\xi \Theta)^{l} \mathbf{y} + (\xi \Theta)^{l} \mathbf{y}, \end{split} \tag{5.15}$$

where *ζ* = 1 1+*λ* . Since 0 *<ζ<* 1, and the eigenvalues of *Θ* are in [−1*,* 1], it can be derived that

$$\lim\_{t \to \infty} \left( \zeta \Theta \right)^{t} = 0 \tag{5.16}$$

and

$$\lim\_{t \to \infty} \sum\_{l=0}^{t-1} (\zeta \Theta)^l = (\mathbf{I} - \zeta \Theta)^{-1}. \tag{5.17}$$

Then, it turns out

$$\mathbf{f} = \lim\_{t \to \infty} \mathbf{f}^{(t)} = (1 - \boldsymbol{\zeta})(\mathbf{I} - \boldsymbol{\zeta}\boldsymbol{\Theta})^{-1}\mathbf{y} = \left(\mathbf{I} + \frac{1}{\lambda}\boldsymbol{\Delta}\right)^{-1}\mathbf{y}.\tag{5.18}$$

Therefore, the convergence of **f** is proved to be equal to the closed-form solution Eq. (5.14).

The random-walk-based method is the most commonly used approach in label propagation on hypergraphs. It has the advantages of being simple to implement and theoretically verifiable.

In many cases, different hypergraphs may be generated based on different criteria. Under such circumstances, we need to conduct label propagation on multi-hypergraph. Here, we briefly introduce the cross diffusion method on multihypergraph [2]. We assume that there are *T* hypergraphs, and the *t*-th hypergraph is denoted as G *t* = *(*V *t ,* E *t ,***W***t )*, where V *t* is the vertex set, E *t* is the hyperedge set, and **W***t* is a diagonal matrix, representing the weights of hyperedges.

The transition matrix is first generated for each hypergraph. The label propagation process on hypergraph is based on the assumption that the local similarities could approximate the long-range similarities, and therefore, the local similarities are more important than far-away vertices. The similarity matrix among vertices of the *t*-th hypergraph is shown as follows:

$$\boldsymbol{A}^{l}(\boldsymbol{\mu},\boldsymbol{v}) = \sum\_{e \in \mathcal{E}^{l}} \frac{\mathbf{W}^{l}(e)\mathbf{H}^{l}(\boldsymbol{\mu},e)\mathbf{H}^{l}(\boldsymbol{v},e)}{\delta(e)},\tag{5.19}$$

or in the matrix form:

$$\boldsymbol{A}^{\boldsymbol{t}} = \mathbf{H}^{\boldsymbol{t}} \mathbf{W}^{\boldsymbol{t}} \mathbf{D}\_{\boldsymbol{\varepsilon}}^{\boldsymbol{t}-1} \mathbf{H}^{\boldsymbol{t}} \,. \tag{5.20}$$

The transition matrix **P***t* is the normalized similarity matrix:

$$\mathbf{P}^{l}(i,j) = \frac{A\_{l}(i,j)}{\sum\_{w \in \mathcal{Y}^{l}} A\_{l}(i,w)}\tag{5.21}$$

and

$$\mathbf{P}^{t} = \mathbf{D}^{t-1} \boldsymbol{\Lambda}^{t},\tag{5.22}$$

where **D***t* is a diagonal matrix with the *i*-th diagonal element **D***t (i, i)* = -|V *t* | *j*=1 *Λt (i, j )*.

The element of the transition matrix **P***t (i, j )* represents the probability of transition from the vertex *i* to the vertex *j* , and **P***t* could be regarded as the Parzen window estimators on hypergraph structure. After the generation of the transition matrix, the cross label propagation process is applied to the multi-hypergraph structure.

Denote **Y**0 as the initial label matrix. For labeled vertices, the *i*-th row of **Y**0 is the one-hot label of the *i*-th vertex, while for the unlabeled vertices, all elements of the *i*-th row are 0*.*5, indicating that there is no prior knowledge of the label. We denote the labeled part of the initial label matrix as **Y***L* 0 .

For simplicity, we assume the number of hypergraphs *T* is 2. The label propagation process for multi-hypergraph uses the output of one hypergraph as the input of the other hypergraph, which repeats until the output converges. The process could be formulated as

$$\mathbf{Y}\_{d+1}^{1} \leftarrow \mathbf{P}^{1} \mathbf{Y}\_{d}^{2},\tag{5.23}$$

$$\mathbf{Y}\_{d+1}^{\mathrm{IL}} \leftarrow \mathbf{Y}\_0^{\mathrm{L}} \tag{5.24}$$

**Fig. 5.4** An illustration of the diffusion process on multi-hypergraph. This figure is from [2]

and

$$\mathbf{Y}\_{d+1}^{2} \leftarrow \mathbf{P}^{2} \mathbf{Y}\_{d}^{1},\tag{5.25}$$

$$\mathbf{Y}\_{d+1}^{2L} \leftarrow \mathbf{Y}\_0^L,\tag{5.26}$$

where **Y***k d* denotes the label matrix of the *k*-th hypergraph after *d* times of label propagation. This process is shown in Fig. 5.4.

The overall matrix could be calculated according to the label matrix of each hypergraph after convergence:

$$\mathbf{Y}\_{final} = \frac{1}{T} \sum\_{l=1}^{T} \mathbf{Y}\_{d}^{l}. \tag{5.27}$$

For more complicated scenarios, where more than two hypergraphs are available, the label propagation process can repeat that, and the output of one hypergraph can be used as the input of other hypergraphs.

This diffusion process can also be used for a single hypergraph, and the framework can be described in Fig. 5.5.

**Fig. 5.5** An illustration of the diffusion process on a single hypergraph

#### **5.3 Data Clustering on Hypergraph**

Data clustering is a typical machine learning task that aims to group data into clusters. In this section, we introduce hypergraph-based data clustering methods, which can utilize the hypergraph structure for better finding correlations behind the data. For hypergraph clustering, two types of information can be used, including structural hypergraph clustering and attribute hypergraph clustering according to the data information in the hypergraph. In structural hypergraph, the clustering tasks only use structural information. For example, the hypergraph spectral clustering method[7] is extended on the basis of graph, which uses the hypergraph Laplacian to learn complex relations between nodes in the hypergraph. And some auto-encoderbased techniques[9] are also applied to structural clustering. In attribute hypergraph, each vertex is usually accompanied by attribute information from the real world. There are two assumptions as follows:

How to balance graph structure information and node feature information is a study focus of attributed graph clustering [10]. In this way, hypergraphs can utilize the features, attributes, and structured information of vertices to conduct data clustering task.

In this section, we introduce a hypergraph Laplacian smoothing filter and an embedded model called adaptive hypergraph auto-encoder (AHGAE) that is designed specifically for hypergraph clustering tasks [3]. First, we describe the hypergraph Laplacian smoothing filter and derive its low-pass filtering properties in the frequency domain. Then, we analyze the influence of each vertex on the attributes of its connected hyperedges and the feature of neighbor vertices. Finally, we introduce the detailed procedure and framework of the adaptive hypergraph autoencoder.

The hypergraph Laplacian smoothing filter, as shown in Fig. 5.6, first merges the vertex features into hyperedge features, and the feature of hyperedge *ek* is defined as

$$\mathbf{E}\_{k}^{(t)} = \frac{1}{|N\left(e\_{k}\right)|} \sum\_{v\_{j} \in N(e\_{k})} \mathbf{X}\_{j}^{(t)} = \sum\_{v\_{j} \in \mathcal{Y}} \frac{h(j,k)}{d\_{\epsilon}(k)} \mathbf{X}\_{j}^{(t)},\tag{5.28}$$

where *ek* denotes the *k*-th hyperedge in the hyperedge set E , *vi* denotes the *i*-th vertex in the vertex set V , *t* represents the order, *N (ek)* is the vertex set in hyperedge *ek*, **E***k* describes the hyperedge *ek* feature, and **X***j* describes the feature of the vertex *vj* .

**Fig. 5.6** An illustration for hypergraph Laplacian smoothing filter. This figure is from [3]

After aggregating the vertex features to get the hyperedge features, we can further combine the vertex features according to the hyperedge weights:

$$\begin{split} \mathbf{X}\_{l}^{(t+1)} &= (1-\boldsymbol{\nu})\mathbf{X}\_{l}^{(t)} + \boldsymbol{\nu} \sum\_{e\in N(v)} \frac{h(\boldsymbol{i},k)w(\boldsymbol{k})}{d\_{v}(\boldsymbol{i})} \mathbf{E}\_{k}^{(t)} \\ &= (1-\boldsymbol{\nu})\mathbf{X}\_{l}^{(t)} + \boldsymbol{\nu} \sum\_{v\_{l}\in \mathcal{V}} \sum\_{e\in \mathcal{E}} \frac{h(\boldsymbol{i},k)w(\boldsymbol{k})h(\boldsymbol{j},k)}{d\_{v}(\boldsymbol{i})d\_{e}(\boldsymbol{k})} \mathbf{X}\_{j}^{(t)}, \\ \mathbf{X}^{(t+1)} &= (1-\boldsymbol{\nu})\mathbf{X}^{(t)} + \boldsymbol{\nu}\mathbf{D}\_{v}^{-1/2}\mathbf{H}\mathbf{W}\mathbf{D}\_{e}^{-1}\mathbf{H}^{\top}\mathbf{D}\_{v}^{-1/2}\mathbf{X}^{(t)}, \end{split} \tag{5.29}$$

where *N (v)* represents the hyperedge connected to vertex *v*, and *γ* ∈ [0*,* 1] is the weight coefficient of the filter. **D***v* denotes the diagonal matrix of the vertex degrees, **D***e* denotes the diagonal matrix of the hyperedge degrees, and **H** is the incidence matrix of the hypergraph. In order to make the spectral radius less than 1, we can replace **D**−1 v **HWD**−1 *e* **H** with symmetric normalized form:

$$\begin{split} \mathbf{X}^{(t+1)} &= (1 - \boldsymbol{\gamma})\mathbf{X}^{(t)} + \boldsymbol{\gamma}\mathbf{D}\_{v}^{-1/2}\mathbf{H}\mathbf{W}\mathbf{D}\_{e}^{-1}\mathbf{H}^{\top}\mathbf{D}\_{v}^{-1/2}\mathbf{X}^{(t)} \\ &= \mathbf{X}^{(t)} - \boldsymbol{\gamma}\left(\mathbf{I} - \mathbf{D}\_{v}^{-1/2}\mathbf{H}\mathbf{W}\mathbf{D}\_{e}^{-1}\mathbf{H}^{\top}\mathbf{D}\_{v}^{-1/2}\right)\mathbf{X}^{(t)}. \end{split} \tag{5.30}$$

Then, the multi-order hypergraph Laplacian smoothing filter can be written as

$$\mathbf{X}^{(t)} = (\mathbf{I} - \boldsymbol{\gamma}\mathbf{L})^{\dagger}\mathbf{X}.\tag{5.31}$$

After decomposing the eigenvalues of the hypergraph Laplacian operator **L** = **U***Λ***U**−1, the diagonal elements of the diagonal matrix *Λ* are eigenvalues of **L**. The

**Fig. 5.7** The framework of the adaptive hypergraph auto-encoder framework. This figure is from [3]

frequency response function is as

$$p(\mathbf{A}) = \text{diag}\left(p\left(\lambda\_1\right), \dots, p\left(\lambda\_{|\mathcal{V}|}\right)\right),\tag{5.32}$$

$$p(\lambda) = 1 - \gamma \lambda, \; \chi \in [0, 1]. \tag{5.33}$$

Due to the eigenvalue of the hypergraph Laplacian *λ* ∈ [0*,* 1], *p(Λ)* is a positive semi-definite matrix, and the value of *p(λ)* decreases as *λ* increases. Therefore, the hypergraph Laplacian smoothed filtered can effectively suppress high-frequency signals:

$$\mathbf{F} = \mathbf{U}p(\mathbf{A})\mathbf{U}^{-1} = \mathbf{U}(\mathbf{I} - \boldsymbol{\chi}\boldsymbol{\Lambda})\mathbf{U}^{-1} = \mathbf{I} - \boldsymbol{\chi}\mathbf{L}.\tag{5.34}$$

Figure 5.7 illustrates how to use the relational reconstruction auto-encoder after getting the smoothed feature matrix to conduct vertex representation learning in low-dimensional environments without losing information. First, the incidence matrix is used to generate the adjacency matrix:

$$\mathbf{A} = \varepsilon \left( \mathbf{H} \mathbf{H}^{\top} \right), \tag{5.35}$$

$$\varepsilon(x) = \begin{cases} 1, \ x > 0 \\ 0, \ x = 0 \end{cases} \tag{5.36}$$

A single fully connected layer is used to compress the filtered feature matrix:

$$\mathbf{Z} = \text{scale}\left(\mathbf{X}\_{\text{sm}}\boldsymbol{\Theta}\right),\tag{5.37}$$

$$\text{scale}(\mathbf{x}) = \frac{\mathbf{x} - \min(\mathbf{x})}{\max(\mathbf{x}) - \min(\mathbf{x})},\tag{5.38}$$

where **Z** represents the vertex embedding matrix, which includes both structural and feature information, and *Θ* is the learnable parameter that is used to extract features from the vertices. In order to rescale the range of vertex characteristics to [0*,* 1], scale *(*·*)* represents a normalization function. So the following is the similarity matrix for vertex features:

$$\mathbf{S} = \text{sigmoid}\left(\mathbf{Z}\mathbf{Z}^{\top}\right),\tag{5.39}$$

$$\text{sigmoid}(\mathbf{x}) = \frac{1}{1 + e^{-\mathbf{x}}}.\tag{5.40}$$

This is the inner product decoder used to reconstruct vertex and its neighbors. The objective is to minimize the error between the adjacency matrix **A** and the similarity matrix **S**. However, using Eq. (5.35) to construct an adjacency matrix leads to a problem: the number of edges is too large when the hyperedge degree increases. To solve this problem, the elements in matrix **A** are weighted as

$$\mathbf{W}\_{lj} = \begin{cases} \frac{|\mathcal{V}|^2 - \sum \sum \mathbf{A}\_{lj}|}{\sum \sum \mathbf{A}\_{lj}}, \mathbf{A}\_{lj} = 1\\ 1 \qquad , \mathbf{A}\_{lj} = 0 \end{cases},\tag{5.41}$$

The reconstruction loss can be calculated by using the weighted binary crossentropy function:

$$L\_{re} = \frac{1}{|\mathcal{V}|^2} \sum\_{i=1}^{|\mathcal{V}|} \sum\_{j=1}^{|\mathcal{V}|} - \mathbf{W}\_{ij} \left[ \mathbf{A}\_{ij} \log \mathbf{S}\_{ij} + \left( \mathbf{1} - \mathbf{A}\_{ij} \right) \log \left( \mathbf{1} - \mathbf{S}\_{ij} \right) \right]. \tag{5.42}$$

The relational reconstruction auto-encoder can be trained to produce the learned vertex embeddings, and the spectral clustering technique can be further used to obtain the final clustering results.

#### **5.4 Cost-Sensitive Learning on Hypergraph**

Most of the machine learning applications may suffer from cost-sensitive scenarios. It is noted that different types of faults in real-world jobs might result in losses with varying severity. In diagnostic work, for example, misdiagnosing a patient as a healthy person is significantly more erroneous than classifying a healthy individual as a patient, as shown in Fig. 5.8. Similar cases also happen in the application of software defect prediction. Misjudging the flaws of software modules as a good one may destroy the software system and have disastrous repercussions in software defect prediction. In these cases, cost-sensitive learning methods [11–13] have been developed to deal with these issues.

In many cases, the data from a group of categories may be enough, while the data from other categories may be very limited. These imbalanced data distributions lead to different costs for the classification performance of different categories. Under such circumstances, imbalanced learning [13, 14] attracts much attention, which aims to attain a predictive prediction using imbalanced sampling data. In traditional methods, sampling methods [15, 16] are used to over-sample the minority class and under-sample the majority class to solve the imbalanced sample problem. Another way is to conduct cost-sensitive learning that can focus more on the minority class.

To confront the cost-sensitive issue in hypergraph computation, in this section, we introduce cost-sensitive hypergraph computation framework [4] and cost interval optimization for hypergraph computation [5], respectively. First, we describe how to quantify cost in the hypergraph modeling procedure [4], in which a fixed cost value is provided for modeling, and thereafter, we illustrate how to use the costsensitive hypergraph computation approach to tackle imbalanced problems. As the cost value for mis-classification results may not be feasible in practice, we then introduce the hypergraph computation method with cost interval optimization [5], which can utilize the cost chosen inside the interval while generating data with high-order relations. Figure 5.9 shows the frameworks of hypergraph computation under cost-sensitive scenarios, from traditional hypergraph modeling, hypergraph modeling with cost matrix, to hypergraph modeling with cost matrix using cost interval.

**Fig. 5.8** A medical example of cost-sensitive classification scenario

**Fig. 5.9** The frameworks of hypergraph computation under cost-sensitive scenarios

#### *(1) Cost-Sensitive Hypergraph Computation*

In this part, we introduce a cost-sensitive hypergraph computation method [4], and Fig. 5.10 shows the framework of this method. This framework consists of two stages to handle the cost-sensitive issue: F-measure is used in the initial step to calculate candidate cost information for cost-sensitive learning, and then the hypergraph structure is utilized to model the high-order correlations among the data in the second stage.

First, we introduce the hypergraph modeling with cost matrix. In traditional hypergraph modeling, each vertex represents a subject, and the hyperedges connect related vertices. To introduce cost information in hypergraph modeling, a cost matrix is associated with each vertex, indicating different costs for misclassification, as shown in Fig. 5.11 for a binary classification task. The definition of cost matrix is as follows.

As shown in Fig. 5.11, the cost matrix is a 2×2 matrix, including the true positive cost *CT P* , the true negative cost *CT N* , the false positive cost *CFP* , and the false negative cost *CF N* , respectively. The true positive cost and the true negative cost are mostly 0 in the matrix since that denotes the correct prediction. The cost-sensitive hypergraph's propensity for each class is achieved by giving various values to the false positive cost and the false negative cost in the cost matrix. A special case is that, if the false positive cost and the false negative cost are equal, then the costsensitive hypergraph reduces to traditional hypergraph modeling.

We generate candidate cost information at first and then apply F-measure to reduce the expense for both binary and multi-class data. For a classifier *h*, we can define the error profile as

$$\Psi(h) = \begin{pmatrix} \text{FN}\_1(h), \text{FP}\_1(h), \dots, \text{FN}\_{N\_c}(h), \text{FP}\_{N\_c}(h) \end{pmatrix}, \tag{5.43}$$

where *Nc* represents the number of classes, and FN and FP represent the false negative and the false positive probabilities. For simplicity, we let *ψ*2*k*−1 represent the FN possibility of the *k*-th class and *ψ*2*k* represent the FP possibility of the *k*-th

class. The F-measure for binary classification can be defined as

$$F\_{\beta}(\Psi) = \frac{\left(1 + \beta^2\right) \left(P\_1 - \psi\_1\right)}{\left(1 + \beta^2\right) P\_1 - \psi\_1(h) + \psi\_2(h)},\tag{5.44}$$

where *Pk* represents the marginal probability of class *k*. Similarly, the micro-Fmeasure for multi-class classification can be defined as

$$mcF\_{\beta}(\Psi) = \frac{\left(1 + \beta^2\right)\left(1 - P\_1 - \sum\_{k=2}^{C} \psi\_{2k-1}\right)}{\left(1 + \beta^2\right)\left(1 - P\_1\right) - \sum\_{k=2}^{C} \psi\_{2k-1} + \psi\_1}.\tag{5.45}$$

We can further divide the F-measure values in the region [0*,* 1] into a collection of equally spaced values *F* = {*fi*} to calculate the cost of various mis-classifications. The cost function *Υ* is then used to construct the cost vector using every *fi*. For binary classification, we constrain the denominator of Eq. (5.44) to be positive and *Fβ(Ψ )* ≤ *fi* for a value *c* of the F-measure:

$$\left(1+\beta^2-f\right)\psi\_1+f\psi\_2+\left(1+\beta^2\right)P\_1(f-1)\geq 0.\tag{5.46}$$

Therefore, the cost of *ψ*1 and *ψ*2 can be allocated according to *f* and 1+*β*2 −*f* , and the cost function can be written as follows:

$$\mathcal{T}\_i^{F\_\beta} = \begin{cases} 1 + \beta^2 - f, \text{ if sample from class 1} \\ f, & \text{if sample from class 2} \\ 0, & \text{otherwise} \end{cases} \tag{5.47}$$

Similarly, the cost function of multi-class classification can be written as follows:

$$\mathcal{T}\_{l}^{mI F\_{\beta}} = \begin{cases} 1 + \beta^2 - f, \text{ if sample from odd class and not from class 1} \\ f, & \text{if sample from class 1} \\ 0, & \text{otherwise} \end{cases} \tag{5.48}$$

The cost of F-measure optimization is added to the optimization function to increase the efficacy of the hypergraph computation method in imbalanced data. We first regard each data to be a vertex of the hypergraph and then apply the k nearest neighbor algorithm to construct the hypergraph. The cost-sensitive hypergraph differs in that it includes the cost matrix information of each vertex in addition to the original hypergraph correlation structure. With training and testing samples represented by **O**, cost-sensitive hypergraph computation function can be expressed as

$$\begin{aligned} \arg\min\_{\boldsymbol{\omega}, \mathbf{W}} & \left[ \mu \mathcal{Q}(\boldsymbol{\omega}) + \mathcal{R}\_{emp}(\boldsymbol{\omega}) + \lambda \Phi(\mathbf{W}) \right], \\ & \text{s.t. } \sum\_{j=1}^{N} \mathbf{W}\_{j,j} = 1, \forall \, \mathbf{W}\_{j,j} \ge 0, \end{aligned} \tag{5.49}$$

where *Ω(ω)* = *(***O***ω)Δ(***O***ω)* represents the hypergraph Laplacian regularized with hypergraph Laplacian *Δ*, R*emp(ω)* = *Υ (***O***ω* − **y***)*2 2 = -*N i*=1 *Υi,i (***o***iω* − **y***i)* 2 is the empirical loss using cost information with diagonal matrix *Υ* that *Υi,i* represents the cost of the *i*-th data, *Φ(***W***)* = *λ***W**2 F stands for the hypergraph regularization, *ω* represents the mapping vector to be learnt, **W** is a diagonal matrix representing hyperedge weights, and *μ* and *λ* are the trade-off hyperparameter. We first fix **W** to optimize *ω*, and then the optimization equation can be expressed as

$$\arg\min\_{\boldsymbol{\omega}} \left\{ \|\boldsymbol{\mathcal{T}}(\mathbf{O}\boldsymbol{\omega}) - \mathbf{y}\|\_{2}^{2} + \mu(\mathbf{O}\boldsymbol{\omega})^{\top}\boldsymbol{\Delta}(\mathbf{O}\boldsymbol{\omega}) \right\}.\tag{5.50}$$

The optimal *ω* can be obtained as

$$
\omega = \left(\mathbf{O}^{\top}\mathcal{I}^2\mathbf{O} + \mu\mathbf{O}^{\top}\Delta\mathbf{O}\right)^{-1}\left(\mathbf{O}^{\top}\mathcal{I}\mathbf{y}\right).
\tag{5.51}
$$

Following that, we fix *ω* to enhance **W**:

$$\begin{aligned} \arg\min\_{\mathbf{W}} & \left\{ \mu (\mathbf{O}\omega)^{\top} \Delta (\mathbf{O}\omega) + \lambda \|\mathbf{W}\|\_{F}^{2} \right\}. \\ \text{s.t. } & \sum\_{j=1}^{N} \mathbf{W}\_{j,j} = 1, \forall \; \mathbf{W}\_{j,j} \ge 0. \end{aligned} \tag{5.52}$$

We can have **W** as

$$\mathbf{W} = \frac{\mu A^{\top} A \left(\mathbf{D}\_{\ell}\right)^{-1} - \eta \mathbf{I}}{2\lambda},\tag{5.53}$$

where *η* can be calculated as *η* = *μΛ(***D***e)* −1*Λ*−2*λ N* , and *Λ* can be calculated as *Λ* = *(***O***ω) (***D***v)* −1*/*2 **H**. The optimized mapping vector *ω* allows sample *ζi* in the test set to obtain the classification result *γ* = *ζiω*.

Each piece of potential cost information *ci* generates a cost matrix *Υ* , which is then used to build a cost-sensitive hypergraph structure G*i*. The model then employs an efficient collection to choose the cost-sensitive hypergraph with the greatest Fmeasure as the best choice.

#### *(2) Cost Interval Optimization for Hypergraph Computation*

As the cost value for cost-sensitive hypergraph modeling is not easy to be determined in practice, in this part, we introduce a cost interval optimization method for hypergraph computation [5], in which the fixed cost value is replaced by a cost interval, which is much easier to be provided than a fixed cost value.

Given a hypergraph G = *(*V *,* E *,***W***)*, the regularization foundation of the costsensitive hypergraph can be divided into three components, i.e., empirical loss using cost information, the hypergraph Laplacian regularizer, and the hypergraph regularization, in order to optimize the overall cost by adding the mis-classification costs of various categories to the hypergraph framework.

The empirical loss using cost information can be formulated as

$$\left\|\mathcal{R}\_{emp}(\omega) = \left\|\Phi(\mathbf{S}\omega - \mathbf{y})\right\|\_{2}^{2} = \sum\_{l=1}^{N\_{v}} \left(\Phi\_{l,i}\left(\mathbf{s}\_{l}\omega - \mathbf{y}\_{l}\right)\right)^{2},\tag{5.54}$$

where *ω* represents the mapping vector, and *Φ* is a diagonal matrix representing misclassification cost weights. The hypergraph Laplacian regularizer can be written as

$$\begin{split} \mathcal{Q}(\omega) &= \frac{1}{2} \sum\_{e \in \mathcal{S}} \sum\_{v\_i, v\_j \in \mathcal{V}} \frac{\mathbf{W}(e) \mathbf{H}\left(v\_i, e\right) \mathbf{H}\left(v\_j, e\right)}{\delta(e)} \left( \frac{\omega \mathbf{s}\_l}{\sqrt{d\left(v\_l\right)}} - \frac{\omega \mathbf{s}\_f}{\sqrt{d\left(v\_j\right)}} \right)^2 \\ &= (\mathbf{S}\omega)^\top \Delta(\mathbf{S}\omega). \end{split} \tag{5.55}$$

To adjust the hyperedges weights and hence the hypergraph classification ability, the hypergraph regularization is written as *Ψ (***W***)* = **W**2 *F* . It is noted that this part can be removed in different applications, if not required.

Combining the above three, the whole optimization task for cost-sensitive hypergraph computation can be written as

$$\begin{aligned} \arg\min\_{\boldsymbol{\omega}, \mathbf{W}} & \left\| \| \boldsymbol{\Phi} (\mathbf{S} \boldsymbol{\omega} - \mathbf{y}) \|\|\_{2}^{2} + \mu (\mathbf{S} \boldsymbol{\omega})^{\top} \boldsymbol{\Delta} (\mathbf{S} \boldsymbol{\omega}) + \boldsymbol{\lambda} \|\mathbf{W} \|\_{\rm F}^{2} \right\|, \\ \text{s.t. } & \sum\_{j=1}^{N\_{\varepsilon}} \mathbf{W}\_{j,j} = 1, \forall \; \mathbf{W}\_{j,j} \ge 0, \end{aligned} \tag{5.56}$$

where *μ* and *λ* are the trade-off hyperparameters.

The precise cost of each category is required for cost-sensitive hypergraph computation, but the cost is frequently impossible to be obtained, and it can only be known that the cost is within a cost interval [*Cmax, Cmin*]. Therefore, a simple idea is to attempt all values inside the cost interval and minimize the overall cost. However, this is inefficient given the possibly huge cost interval. As the actual cost is difficult to establish, we need to find a surrogate cost *c*∗ to guide the optimization procedure, and the surrogate classifier *h*∗ is supposed to be as successful as the true cost classifier *ht* . In this way, the problem can be formulated as

$$\begin{aligned} \min\_{h, c^\*} L(h, c^\*),\\ \text{s.t. } p(L(h, c) < \theta) &> 1 - \varphi, \forall c \in [\mathcal{C}\_{\text{min}}, \mathcal{C}\_{\text{max}}], \mathcal{C}\_{\text{min}} \le c^\* \le \mathcal{C}\_{\text{max}}, \end{aligned} \tag{5.57}$$

where *L(h, c)* is the empirical risk. *L(h, c)* is formulated as *L(h, c)* = -*Nv i*=1 *cI (ρi* = *y* ∧ *y* = +*)* + *I (ρi* = *y* ∧ *y* = −*)*, where *ρi* = *siω* is the *i*-th data labeling in the test set, and + and − represent the label of the important class and the unimportant class, respectively.

The worst-case risk is considered first to guarantee that all limitations can be fulfilled. The worst-case classifier *h*∗ can be written as

$$h^\* = \arg\min\_h \sup\_c L(h, c) \tag{5.58}$$

and

$$p\left(\sup\_{c} L\left(h\_{\*},c\right) < \theta\right) > 1 - \varphi. \tag{5.59}$$

We have *p (L(h*∗*, c) < θ) >* 1 − *ϕ* for any *c*. The worst-case risk is attained when the surrogate cost *c*∗ equals *Cmax* . However, only a solution that meets the requirements can be acquired in this manner, and the cost cannot be guaranteed to be close to the true cost. As the average cost is the smallest maximum distortion of the genuine risk, it is another good choice, which can be calculated as *Cmean* = 0*.*5*(Cmax* + *Cmin)*.

With the use of alternative costs *Cmax* and *Cmean*, we can conduct cost interval optimization. First, *Cmax* is used as a surrogate cost, and a collection of costsensitive hypergraph structures with varying parameter values is learned in the first stage. Then, *Cmean* is used as a surrogate cost to determine the lowest overall cost on the valid dataset, and then we choose the hypergraph structure as the final solution.

In this section, we describe cost-sensitive hypergraph computation methods. Imbalanced data issue is very common in many applications. The cost-sensitive hypergraph computation methods introduce cost matrix in hypergraph modeling, and both fixed cost value and cost interval can be used in the learning process.

#### **5.5 Link Prediction on Hypergraph**

Link prediction is a fundamental task in network analysis. The objective of link prediction is to predict whether two vertices in a network may have a link. Link prediction has wide applications in different domains, such as social relation exploration [17, 18], protein interaction prediction [19, 20], and recommender system [21, 22], which has attracted much attention in the past decades.

Link prediction on hypergraph aims to discover missing relations or predict new coming hyperedges based on the observed hypergraph, where hypergraph computation can be used to deeply exploit the underneath high-order correlations among these data. Unlike the link prediction task on the graph structure [23, 24], the hypergraph models the high-order correlation among the data, which is heterogeneous in many applications, as the vertices are in different types. For example, in a bibliographic network, the vertex can represent a paper, an author, or a venue, while the hyperedge represents the relation where the paper is written by multiple authors and published in a venue. These different types of vertices do not necessarily share the same representation space. The heterogeneous hypergraph consists of two kinds of vertex in the view of the hypergraph event, i.e., identifier vertex and slave vertex. Identifier vertex is the vertex that determines a hyperedge uniquely, while slave vertex is the other vertex except for the identifier vertex. In this section, we introduce the Heterogeneous Hypergraph Variational Auto-encoder (HeteHG-VAE) method [6] for heterogeneous hypergraph link prediction task.

The overview of HeteHG-VAE can be found in Fig. 5.12. HeteHG-VAE aims to learn the low-dimensional heterogeneous hypergraph embedding based on the Bayesian deep generative strategy. The input hypergraph is represented by the incidence matrix **H**, whose sub-hypergraph represents the hypergraph generated by different types of slave vertices. The heterogeneous encoder can project the vertices and the hyperedges to the vertex embedding and hyperedge embedding, respectively. The hypergraph embedding is the combination of the vertex embedding and the hyperedge embedding, which can be used for reconstructing the incidence matrix by the hypergraph decoder.

In the following part of this section, we first introduce the variational evidence lower bound with the task specific derivation. Then, the inference model, including the heterogeneous vertex encoder and the heterogeneous hyperedge encoder, is presented. At last, the generative model and the link prediction method are introduced.

Denote {*xk*}*K k*=1 as the observed data with the total number *K*, **Z***V k* as the latent vertex embedding, and *ZE* as the latent hyperedge embedding. HeteHG-VAE assumes that **Z***V k* and **Z***E* are drawn *i.i.d.* from a Gaussian prior, i.e., **Z***V k* ∼ *p*0*(***Z***V k )* and **Z***E* ∼ *p*0*(***Z***E)*, and *xk* are drawn from the conditional distribution, *xk* ∼ *p(xk*|**Z***V k , ZE*; *λk)*, where *λk* is the parameter of the distribution. The objective of HeteHG-VAE is to maximize the log-likelihood of the observed data by optimizing

**Fig. 5.12** An illustration of the HeteHG-VAE method. This figure is from [6]

*λk* as follows:

$$\begin{split} & \log p(\mathbf{x}\_1, \dots, \mathbf{x}\_K; \boldsymbol{\lambda}) \\ &= \log \int\_{\mathbf{Z}\_1^V} \cdots \int\_{\mathbf{Z}\_K^V} \int\_{\mathbf{Z}^E} p(\mathbf{x}\_1, \dots, \mathbf{x}\_K, \mathbf{Z}\_1^V, \dots, \mathbf{Z}\_K^V, \mathbf{Z}^E; \boldsymbol{\lambda}) d\mathbf{Z}\_1^V \cdots d\mathbf{Z}\_K^V d\mathbf{Z}^E \\ & \ge \mathbb{E}\_q \left( \log \frac{p(\mathbf{x}\_1, \dots, \mathbf{x}\_K, \mathbf{Z}\_1^V, \dots, \mathbf{Z}\_K^V, \mathbf{Z}^E; \boldsymbol{\lambda})}{q(\mathbf{Z}\_1^V, \dots, \mathbf{Z}\_K^V, \mathbf{Z}^E | \mathbf{x}\_1, \dots, \mathbf{x}\_K; \boldsymbol{\theta})} \right) \\ & \coloneqq \mathcal{L}^p(\mathbf{x}\_1, \dots, \mathbf{x}\_K; \boldsymbol{\theta}, \boldsymbol{\lambda}), \end{split} \tag{5.60}$$

where *q(*·*)* is the variational posterior for the estimation of the true posterior *p(***Z***V* 1 *,...,***Z***V K,***Z***E*|*x*1*,...,xK)*, which is inaccessible, and *θ* is the parameter to be estimated. Then, L *(x*1*,...,xK*; *θ , λ)* is the evidence lower bound of the log marginal likelihood. Based on the evidence lower bound, an inference encoder is presented to parameterize *q*, and a generative decoder is used to parameterize *p*.

The inference encoder of HeteHG-VAE consists of two main parts, i.e., the heterogeneous vertex encoder and the heterogeneous hyperedge encoder. Heterogeneous vertex encoder first maps the observed data *xk* to a latent space **Z**˜ *V k* , which can be written as

$$\tilde{\mathbf{Z}}\_k^V = f^V(\mathbf{x}\_k \mathbf{W}\_k^V + b\_k^V),\tag{5.61}$$

where **W***V k* and *bV k* are the to-be-learned weights of the model, and *f V* is a nonlinear activation function. Two separated linear layers map the latent representation of the means *μV k* and variances *σ V k* of *q*:

$$
\mu\_k^V = \tilde{\mathbf{Z}}\_k^V \mathbf{W}\_k^{V\mu} + b\_k^{V\mu},\tag{5.62}
$$

$$
\sigma\_k^V = \tilde{\mathbf{Z}}\_k^V \mathbf{W}\_k^{V\sigma} + b\_k^{V\sigma}, \tag{5.63}
$$

where **W***V μ k* , *bV μ k* , **W***V σ k* , and *bV σ k* are learnable parameters. The vertex embedding is the sample from the Gaussian distribution N *(μV k , σ V k )*.

Heterogeneous hyperedge encoder first maps the observed data *xk* to a latent space **Z**˜ *E k* , which can be written as

$$\tilde{\mathbf{Z}}\_k^E = f^E(\mathbf{x}\_k^\top \mathbf{W}\_k^E + b\_k^E),\tag{5.64}$$

where **W***E k* and *bE k* are the to-be-learned weights of the model, and *f E* is a nonlinear activation function. Then, the importance of different types of vertices is learned by the hyperedge attention mechanism, which can be written as

$$
\tilde{\alpha}\_k = \text{Tan}h(\tilde{\mathbf{Z}}\_k^E \mathbf{W}\_k^{E\alpha} + b\_k^{E\alpha})\mathbf{P},\tag{5.65}
$$

where **W***Eα k* , *bEα k* , and **P** are learnable parameters. The attention score *αk* is obtained by normalizing *α*˜ *k*, and the hyperedge embedding can be written as

$$
\tilde{\mathbf{Z}}^E = \sum\_{k=1}^K \alpha\_k \tilde{\mathbf{Z}}\_k^E \,. \tag{5.66}
$$

Similarly, two separated linear layers map the latent representation of the means *μE* and variances *σ E* of the distribution *q*:

$$
\mu^E = \tilde{\mathbf{Z}}^E \mathbf{W}^{E\mu} + b^{E\mu},\tag{5.67}
$$

$$
\sigma^E = \tilde{\mathbf{Z}}^E \mathbf{W}^{E\sigma} + b^{E\sigma},\tag{5.68}
$$

where **W***Eμ*, *bEμ*, **W***Eσ* , and *bEσ* are learnable parameters. The vertex embedding is the sample from the Gaussian distribution N *(μE, σ E)*.

The incidence matrix is sampled from a Bernoulli distribution parameterized by H*k*:

$$p(\mathbf{H}\_{lj}|\mathbf{Z}\_{k,i}^{V}, \mathbf{Z}\_{k,j}^{E}; \lambda\_k) = Ber(\mathcal{H}\_{lj}),\tag{5.69}$$

where H*ij* is the dot product of the vertex embedding and the hyperedge embedding:

$$\mathcal{H}\_{lj}^{\ell} = \text{Sigmoid}(\mathbf{Z}\_{k,l}^{V}(\mathbf{Z}\_{j}^{E})^{\top}).\tag{5.70}$$

The likelihood of the connection among vertices could be obtained based on the vertex embedding and hyperedge embedding as follows:

$$p\_{conn}(\mathbf{Z}\_l^V, \mathbf{Z}\_j^E) = ||\mathbf{Z}\_l^V, \mathbf{Z}\_j^E||\_2. \tag{5.71}$$

In this section, we have introduced the Heterogeneous Hypergraph Variational Auto-encoder method [6] for the task of link prediction on hypergraph, which captures the high-order correlations among the data while preserving the origin loworder topology. Link prediction on hypergraph has shown superior performance in different experiments and can be further used in other applications.

#### **5.6 Summary**

In this chapter, we introduce four typical hypergraph computation tasks, including label propagation, data clustering, imbalance learning, and link prediction. Label propagation on hypergraph is to predict the labels for the vertices on a hypergraph, i.e., assigning a label to each unlabeled vertex in the hypergraph, based on the labeled information. Data clustering on hypergraph divides the vertices in a hypergraph into several groups. Imbalanced learning on hypergraph considers the imbalanced data distributions and introduces cost-sensitive hypergraph computation methods. Link prediction on hypergraph discovers missing relations or predicts new coming hyperedges based on the observed hypergraph. We note that these four tasks are typical ways to use hypergraph computation in practice. Other tasks can also be deployed under the hypergraph computation framework, such as data regression, data completion, and data generation. Following these typical hypergraph computation tasks, we can use them in different applications, such as social media analysis and computation vision.

#### **References**

**Open Access** This chapter is licensed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license and indicate if changes were made.

The images or other third party material in this chapter are included in the chapter's Creative Commons license, unless indicated otherwise in a credit line to the material. If material is not included in the chapter's Creative Commons license and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder.

## **Chapter 6 Hypergraph Structure Evolution**

**Abstract** In practice, noise exists in the process of data collection and hypergraph construction. Therefore, missing, abundant, and noisy connections may be introduced into the generated hypergraph structure, which may lead to inaccurate inference on hypergraph. Another issue comes from the increasing data stream, which is also very common in many applications. It is important to consider the structure evolution methods on the hypergraph, which optimize the hypergraph structure accordingly. Early hypergraph computation methods mainly rely on static hypergraph structure, which may suffer from the limitation of the static mechanism when confronting random and increasing data scenarios. In this chapter, we introduce dynamic hypergraph structure evolution methods, including both hypergraph component optimization and hypergraph structure optimization. Finally, we briefly introduce the incremental learning method on growing data.

#### **6.1 Introduction**

The hypergraph structure models the high-order and complex correlations among data, and thus the quality of topology structure plays an important role in learning tasks on hypergraph. As shown in the previous chapter, there have been implicit and explicit methods of hypergraph generation from observed data. However, the generated hypergraph may contain abundant, missing, and noisy connections due to the disturbances in the process of data collection and hypergraph construction. In other words, there may exist biases between the generated hypergraph and the ground truth structure. Under such circumstances, it is essential to optimize the hypergraph structure to make it fit the ground truth high-order correlation more accurately. The quality of a hypergraph can be directly qualified by comparing with the ground truth structure if available, or indirectly evaluated by the performance of downstream applications. Most existing hypergraph computation methods rely on static hypergraph structure, such as k-nn-based method [1], cluster-based method [2], and spare representation-based method [3]. These methods may suffer from the inaccurate hypergraph structure that exists in practice. In this chapter, we introduce hypergraph structure evolution methods under the dynamic hypergraph structure learning mechanism. Hypergraph structure evolution can be divided into two main categories, i.e., hypergraph component optimization and hypergraph structure optimization. The problem of hypergraph structure evolution is usually integrated with the learning process and formulated as a bi-level optimization problem. Part of the work introduced in this chapter has been published in [4–7].

#### **6.2 Hypergraph Component Optimization**

Besides the main structure of a hypergraph, i.e., the incidence matrix, a hypergraph is also composed of a group of components such as the weights for hyperedges, vertices, and even sub-hypergraphs, which play an important role on the hypergraph structure. Hypergraph component optimization aims to explore the optimal components of the hypergraphs, i.e., hyperedge weights, vertices weights, and sub-hypergraph weights. The hyperedge weights represent the strength of each highorder correlation among data, while the vertex weights represent the importance of different samples on the structure. In many cases, we may construct multiple hypergraphs using multi-modal data or different criteria, which can be regarded as sub-hypergraphs. The sub-hypergraph weights are used to measure the importance of different sub-hypergraphs on the overall structure. The optimization procedure adjusts the hyperedge weights, the vertex weights, and sub-hypergraph weights during the training process in order to improve the performances on the downstream applications.

#### *6.2.1 Hyperedge Weight Optimization*

The hyperedge is a basic component of the hypergraph, representing the high-order complex correlation among data. The initial hypergraph usually assigns an identical weight to all hyperedges. However, hyperedges actually have different effects for a given task. The hyperedge weights indicate the importance of different hyperedges contributing to the whole structure. In this section, we introduce the hyperedge weight learning methods [4], in which the weights of hyperedges are adaptively adjusted during the training process, and thus the importance of different hyperedges can be automatically modulated.

#### 6.2 Hypergraph Component Optimization 103

We assume that there are *m* hyperedges in the hypergraph, denoted by {*e*1*, e*2*,...,en*}. The weights of the hyperedges are defined by the *n* × 1 vectors *w* = [*w*1*, w*2*,...,wn*] -. There is usually a constraint on the hypergraph weights that their sum is equal to one, i.e., *n i*=1 *ωi* = 1. We use **F** to denote the output of hypergraph learning. The problem of learning hyperedge weights can be formulated in a dual-optimization form mathematically

$$\arg\min\_{\mathbf{F}, w} \Psi(\mathbf{F}) := \left\{ \mathcal{Q}(\mathbf{F}) + \lambda R\_{\text{emp}}(\mathbf{F}) + \mu \Phi(w) \right\},$$

$$\text{s.t. } \sum\_{e \in \mathcal{E}} \mathbf{W}(e) = 1. \tag{6.1}$$

Here, *Ω(***F***)* and *R*emp*(***F***)* are the regularizer and empirical loss of **F**, respectively. *Φ(w)* is the regularizer on *w*. *λ* and *μ* are the scalars controlling the relative importance of these three items.

The general formulation can be implemented by specifying the functions *Ω(*·*)*, *R*emp*(*·*)* and *Φ(*·*)*. As said before, **F** is the to-be-learned labels in the node classification task. The regularizer *Ω(***F***)* can be defined as **F**-*Δ***F**, where *Δ* is the Laplacian matrix. The empirical loss *R*emp*(***F***)* in the general form can be instantiated by the difference between the learned **F** and observed labels of training data **Y**, which are called the least residuals. The regularizer on *w* is a 2-norm. The general formulation can be written as

$$\begin{aligned} \arg\min\_{\mathbf{F}, w} \Psi(\mathbf{F}) &:= \left\{ \mathbf{F}^\top \Delta \mathbf{F} + \lambda \|\mathbf{F} - \mathbf{Y}\|^2 + \mu \sum\_{l=1}^n w\_l^2 \right\}, \\ &\text{s.t. } \sum\_{l=1}^n w\_l^2 = 1. \end{aligned} \tag{6.2}$$

The aim of the learning process is to search the optimal solution of **F** and *w* to minimize the cost function in Eq. (6.2).

There are two variables to be optimized in Eq. (6.2), which can be solved by the alternating optimization algorithm. For each instant in time, one variable is optimized, while the other is kept constant for the to-be-learned two variables **F** and *w*. The details of the alternating optimization strategy are introduced as follows.

Given the initial hyperedge weights, the first step is fixing *w* and optimizing *Ω(***F***)*. The sub-problem is written as

$$\arg\min\_{\mathbf{F}} \Psi(\mathbf{F}) = \arg\min\_{\mathbf{F}} \left\{ \mathbf{F}^{\top} \Delta \mathbf{F} + \lambda \left\| \mathbf{F} - \mathbf{Y} \right\|^{2} \right\}. \tag{6.3}$$

A closed-form solution of Eq. (6.3) has already been achieved from the traditional hypergraph learning. The solution is written as

$$\mathbf{F} = \left(I + \frac{1}{\lambda}\Delta\right)^{-1}\mathbf{Y}$$

$$= \left(\mathbf{I} + \frac{1}{\lambda}(\mathbf{I} - \Theta)\right)^{-1}\mathbf{Y}$$

$$= \frac{\lambda + 1}{\lambda} \left(\mathbf{I} - \frac{1}{\lambda + 1}\Theta\right)^{-1}\mathbf{Y}.\tag{6.4}$$

Let *ζ* = 1 *λ*+1 , and Eq. (6.4) can be rewritten as

$$\mathbf{F} = \frac{1}{1 - \xi} (\mathbf{I} - \xi \Theta)^{-1} \mathbf{Y}. \tag{6.5}$$

With the updated **F**, the next step is fixing **F** while optimizing *w*, and the subproblem about *w* is

$$\begin{aligned} \arg\min\_{w} \Psi(\mathbf{F}) &= \arg\min\_{\mathbf{F}} \left\{ \mathbf{F}^{\top} \Delta \mathbf{F} + \mu \sum\_{l=1}^{n} w\_{l}^{2} \right\}, \\ &\text{s.t. } \sum\_{l=1}^{n} w\_{l} = 1, \mu > 0. \end{aligned} \tag{6.6}$$

The Lagrangian multipliers method is employed here, and the sub-problem is replaced with

$$\begin{aligned} &\arg\min\_{w,\eta} \mathbf{F}^\top \Delta \mathbf{F} + \mu \sum\_{l=1}^n w\_l^2 + \eta \left(\sum\_{l=1}^n w\_l - 1\right) \\ &= \quad \arg\min\_{w,\eta} \mathbf{F}^\top \left(\mathbf{I} - \mathbf{D}\_v^{-\frac{1}{2}} \mathbf{H} \mathbf{W} \mathbf{D}\_e^{-1} \mathbf{H}^\top \mathbf{D}\_v^{-\frac{1}{2}}\right) \mathbf{F} + \mu \sum\_{l=1}^n w\_l^2 + \eta \left(\sum\_{l=1}^n w\_l - 1\right) . \end{aligned} \tag{6.7}$$

Let *Γ* = **D**− 1 2 0 **H**, and it can be shown that

$$\eta = \frac{\mathbf{F}^\top \Gamma \mathbf{F} - 2\mu}{n} \tag{6.8}$$

#### 6.2 Hypergraph Component Optimization 105

and

$$w\_{l} = \frac{1}{n} - \frac{\mathbf{F}^{\top} \boldsymbol{I} \boldsymbol{\Gamma} \mathbf{D}\_{e}^{-1} \boldsymbol{\Gamma}^{\top} \mathbf{F}}{2n\mu} + \frac{\mathbf{F}^{\top} \boldsymbol{I} \boldsymbol{\Gamma} \mathbf{D}\_{e}^{-1} (i, i) \boldsymbol{\Gamma}\_{l}^{\top} \mathbf{F}}{2\mu}. \tag{6.9}$$

Here, *Γi* defines the *i*-th column of *Γ* .

In this way, **F** and *w* are alternatively updated until convergence. Finally, the optimal values of **F** and *w* are obtained. We note that the above method is a typical way to optimize the hyperedge weights using the *l*2-norm. Other methods can also be used to learn the hyperedge weights using different constraints.

#### *6.2.2 Vertex Weight Optimization*

Early hypergraph computation methods may not take the importance of vertices into account and mainly focus on the weights of hyperedges. However, the vertex set in the hypergraph may have heterogeneous, unbalanced, and outlier problems, resulting in performance degeneration of learning process. Therefore, it is highly required to consider the weights of vertices to define the impact of different subjects during the learning process. For example, vertices belonging to the minority class may require larger weights and vice versa for imbalanced data. In this part, we introduce the vertex-weighted hypergraph learning method [5], which can update the vertex weights during the learning process.

The aim of vertex-weighted hypergraph learning algorithm is to emphasize the vertices with distinguishable information and disregard the redundant vertices that bring in bias and noise instead of useful information. On the basis of learning hyperedge weights, vertex-weighted learning algorithm further considers the vertex weights. Here let {*v*1*, v*2*,...,vn*} denote all *n* vertices in the hypergraph. The corresponding weight for vertex *vi* is represented by *ui*. Let **U** denote the diagonal matrix of vertex weights. The overall cost function is similar to learning hyperedge weights, but with the impact of **U** simultaneously taken into consideration. The general formulation is written as

$$\begin{aligned} \arg\min\_{\mathbf{F}, w} \Psi\_{\mathbf{U}}(\mathbf{F}) &:= \left\{ \Omega\_{\mathbf{U}}(\mathbf{F}) + \lambda R\_{\text{emp}}(\mathbf{F}) + \mu \Phi(w) \right\}, \\\\ \text{s.t. } \mathbf{W}(e) &\le 0, \sum\_{e \in \mathcal{E}} \mathbf{H}(v, e) \mathbf{W}(e) = \mathbf{D}\_{v}(v). \end{aligned} \tag{6.10}$$

The key point of vertex weight optimization is to design a reasonable vertex weighting scheme that scores the importance of each subject during the learning process. First, the pairwise distances between vertices are calculated based on the features. Let *dij* denote the distances between vertices *vi* and *vj* , and *d*ˆ *i* declares the mean distance between *vi* and all other training vertices with the same label. The vertex weight is then defined as

$$
\mu\_l = \frac{\vec{d}\_l}{\sum\_{j=1}^{n\_{train}} \hat{d}\_j},
\tag{6.11}
$$

where *ntrain* denotes the number of training samples. It is noted that only the training data are labeled and further weighted. The unlabeled vertices are initialized with an identical weight. Normalization is then applied to the vertex weights. This weighting scheme can assign higher weights to vertices that are far from other intraclass vertices and vice versa. Therefore, the importance of repeated/close samples is relatively smaller than the outliers during the hypergraph learning process.

Since the hypergraph structure is updated with vertex weights, the hypergraph structure regularizer is different from the initial one. As stated already, the hypergraph regularizer is defined based on the cut cost. Here, the cut cost is related to not only just the hyperedge weights but to the vertex weights. In general, the higher the weight of two vertices, the higher the cut cost. Therefore, the regularizer of the hypergraph structure *Ψ***U***(***F***)* is rewritten as

*Ω(***F***)* = *C k*=1 *e*∈E *u,v*∈V **W***(e)***U***(u)***H***(u, e)***U***(v)***H***(v, e)* 2*δ(e)* **F***(u, k)* √*d(u)* − **F***(v, k)* √*d(v)* 2 = *C k*=1 *e*∈E *u,v*∈V **W***(e)***U***(u)***H***(u, e)***U***(v)***H***(v, e) δ(e)* × **F***(u, k)*2 *d(u)* − **F***(u, k)***F***(v, k)* √*d(u)d(v)* = *C k*=1 *u*∈V **U***(u)***F***(u, k)*2 *e*∈E **W***(e)***H***(u, e) d(u) v*∈V **H***(v, e)***U***(v) δ(e)* − *e*∈E *u,v*∈V **F***(u, k)***U***(u)***H***(u, e)***W***(e)***H***(v, e)***U***(v)***F***(v, k)* √*d(u)d(v)δ(e)* ⎫ ⎬ ⎭ = *C k*=1 **F***(*:*, k)*-*Δ***UF***(*:*, k)* = **F**-*Δ***UF***.* (6.12)

Here, **F***(*:*, k)* is the k-th column of **F** and *C* is the number of data categories. *Δ***U** is the vertex-weighted hypergraph Laplacian, which can be defined as

$$\mathbf{A}\_{\mathbf{U}} = \mathbf{U} - \boldsymbol{\Theta} = \mathbf{U} - \mathbf{D}\_{v}^{-1/2} \mathbf{U} \mathbf{H} \mathbf{W} \mathbf{D}\_{e}^{-1} \mathbf{H}^{\top} \mathbf{U} \mathbf{D}\_{v}^{-1/2}. \tag{6.13}$$

Compared with the traditional hypergraph Laplacian *Δ* = **I** − **D**− 1 2 *v* **HWD***e* −1**H**- **D***v* − 1 2 , the hypergraph Laplacian with weighted vertices takes different weights of vertices into consideration during the evaluation of the cost on the hypergraph structure. Therefore, the learning task can be further defined as

$$\begin{aligned} \arg\min\_{\mathbf{F}, \mathbf{W}} \Psi(\mathbf{F}) &:= \left\{ \mathbf{F}^\top \mathbf{A}\_\mathbf{U} \mathbf{F} + \lambda \|\mathbf{F} - \mathbf{Y}\|^2 + \mu \sum\_{e \in \mathcal{E}} \mathbf{W}(e)^2 \right\}, \\\\ \text{s.t. } \mathbf{W}(e) &\ge 0, \sum\_{e \in \mathcal{E}} \mathbf{H}(v, e) \mathbf{W}(e) = \mathbf{D}\_v(v). \end{aligned} \tag{6.14}$$

The above optimization problem can be solved by the alternative optimization algorithm. The sub-problem about **F** has the closed-form solution as in traditional hypergraph learning. The sub-problem about **W** is written as

$$\begin{aligned} \arg\min\_{\mathbf{F},\mathbf{W}} \Psi(\mathbf{F}) &:= \left\{ \mathbf{F}^\top \mathbf{A}\_\mathbf{U} \mathbf{F} + \mu \sum\_{e \in \mathcal{E}} \mathbf{W}(e)^2 \right\}, \\\text{s.t. } \mathbf{W}(e) &\ge 0, \sum\_{e \in \mathcal{E}} \mathbf{H}(v, e) \mathbf{W}(e) = \mathbf{D}\_v(v). \end{aligned} \tag{6.15}$$

The above optimization task can be solved via quadratic programming, since it is convex on **W**. Through vertex weight optimization, the vertex-weighted hypergraph structure takes the contribution of each vertex to the whole hypergraph structure into consideration, and thus it can model the high-order relevance among objects more accurately. During the learning process, the impact of low-quality training samples on the structure and subsequent classification tasks decreases continuously, while high-quality training data, which account for a minority, can be given greater importance. On the other hand, the minority of training data can have greater importance. The additional vertex weights lead to an optimal Laplacian matrix of hypergraph that measures data correlation better than the traditional one and consequently lead to improvement of the classification performance.

#### *6.2.3 Sub-hypergraph Weight Optimization*

Given multiple sub-hypergraphs that are used to jointly formulate the correlation among data, it is important to measure how these sub-hypergraphs work in the main task. Sub-hypergraph weight optimization adjusts the importance of the subhypergraphs, which models the complex correlation among the multi-model data. In this part, we introduce the inductive multi-hypergraph learning (iMHL) [7] to learn the weights of the model and adjust the weights of the sub-hypergraphs during the training process simultaneously, which models the high-order correlation of

**Fig. 6.1** The framework of inductive multi-hypergraph learning method. This figure is from [7]

the multi-model data with the multi-hypergraph, diffuses the sub-hypergraphs as the modality weight, and learns the map from the data to the labels under the supervised setting. Given testing data, the learning projection can be used to predict corresponding labels. The framework of iMHL is illustrated in Fig. 6.1, where the offline training and online training are both supported by the inductive learning process, which can easily handle new coming data efficiently.

Here, we denote *m* as the total number of all sub-hypergraphs and G*i* = *(*V*i,* E*i,***W***i)* as the *i*-th hypergraph for the *i*-th modality. The projection matrices **M***i* are combined as per the sub-hypergraph weights and are used to map the data to the label for prediction. The combination weights *ω* = [*ω*1*,* ··· *, ωm*] are another object to be optimized, which represents the weight of the corresponding modality, subject to *m i*=1 *ωi* = 1 and *ω* ≥ 0.

The loss function *Ψ*¯ for learning all **M***i* can be formulated as

$$\bar{\Psi} = \sum\_{l=1}^{m} \omega\_l \{ \mathcal{Q}(\mathbf{M}\_l) + \lambda R\_{emp}(\mathbf{M}\_l) + \mu \Phi(\mathbf{M}\_l) \} + \eta \Gamma(\omega), \tag{6.16}$$

which consists of two main parts, i.e., the summation of the cost of each subhypergraph and the regularization on the sub-hypergraph weights *ω*. *Φ(***M***)* is the regularizer on the projection matrix. We assume that the vertices with similar labels are connected strongly, and *Ω(***M***)* can then be written as

$$\begin{split} \mathcal{Q}(\mathbf{M}) &= \frac{1}{2} \sum\_{k=1}^{c} \sum\_{e \in \mathcal{E}} \sum\_{u,v \in \mathcal{V}} \frac{\mathbf{W}(e)\mathbf{H}(u,e)\mathbf{H}(v,e)}{\delta(e)} \left( \frac{\mathbf{X}^{\top}\mathbf{M}(u,k)}{\sqrt{d(u)}} - \frac{\mathbf{X}^{\top}\mathbf{M}(v,k)}{\sqrt{d(v)}} \right)^{2} \\ &= \text{tr}(\mathbf{M}^{\top}\mathbf{X}\boldsymbol{\Delta}\mathbf{X}^{\top}\mathbf{M}), \end{split} \tag{6.17}$$

where *Δ* denotes the normalized hypergraph Laplacian,

$$
\Delta = \mathbf{I} - \mathbf{D}\_v^{-1/2} \mathbf{H} \mathbf{W} \mathbf{D}\_e^{-1} \mathbf{H}^\top \mathbf{D}\_v^{-1/2}. \tag{6.18}
$$

The empirical loss term *Remp(***M***)* can be written as

$$R\_{emp}(\mathbf{M}) = ||\mathbf{X}^\top \mathbf{M} - \mathbf{Y}||^2. \tag{6.19}$$

*Φ(***M***)* can be formulated as the 2*,*1-norm of **M**,

$$\Phi(\mathbf{M}) = ||\mathbf{M}||\_{2,1},\tag{6.20}$$

which produces row sparsity for more informative features. *Γ (ω)* is the 2-norm of the sub-hypergraph weights

$$\left|\Gamma(\omega)\right| = \left||\omega||^2,\tag{6.21}$$

which aims to learn the optimal weights for each sub-hypergraph.

The inductive multi-hypergraph learning task can be formulated as

$$\begin{aligned} \arg\min\_{\mathbf{M}\_l,\omega\geq0} &\sum\_{l=1}^m \alpha\_l \left(\varOmega(\mathbf{M}\_l) + \lambda R\_{emp}(\mathbf{M}\_l) + \mu \varPhi(\mathbf{M}\_l)\right) + \eta \varGamma(\omega), \\ &\text{s.t. } \sum\_{l=1}^m \omega\_l = 1. \end{aligned} \tag{6.22}$$

It is observed that Eq. (6.22) could be split into *m*+1 independent sub-problems, each **M***i* is optimized individually, and the combination weights *ω* are optimized to fuse all multi-hypergraphs.

The optimization of **M***i* shown below can be solved by iterative algorithm.

$$\arg\min\_{\mathbf{M}\_l} \mathcal{Q}(\mathbf{M}\_l) + \lambda R\_{emp}(\mathbf{M}\_l) + \mu \Phi(\mathbf{M}\_l). \tag{6.23}$$

The optimization problem of *ω* can then be written as

$$\begin{aligned} \arg\min\_{\boldsymbol{\omega}\geq 0} & \sum\_{l=1}^{m} \alpha\_{l} \left( \mathcal{Q}(\mathbf{M}\_{l}) + \lambda R\_{emp}(\mathbf{M}\_{l}) + \mu \Phi(\mathbf{M}\_{l}) \right) + \eta ||\boldsymbol{\omega}||^{2}, \\ & \text{s.t. } \sum\_{l=1}^{m} \alpha\_{l} = 1. \end{aligned} \tag{6.24}$$

We denote *Υi* = *Ω(***M***i)* + *λRemp(***M***i)* + *μΦ(***M***i)*, and Eq. (6.24) can be simplified to

$$\begin{aligned} \arg\min\_{\boldsymbol{\omega}\geq 0} & \sum\_{l=1}^{m} \boldsymbol{\omega}\_{l} \boldsymbol{\Upsilon}\_{l} + \eta ||\boldsymbol{\omega}||^{2}, \\ & \text{s.t. } \sum\_{l=1}^{m} \boldsymbol{\omega}\_{l} = 1. \end{aligned} \tag{6.25}$$

The Lagrangian algorithm can be applied to solve Eq. (6.25), which can be formulated as

$$\arg\min\_{\boldsymbol{\omega},\boldsymbol{\xi}} \sum\_{l=1}^{m} \boldsymbol{\omega}\_{l} \boldsymbol{\Upsilon}\_{l} + \eta ||\boldsymbol{\omega}||^{2} + \xi \left(\sum\_{l=1}^{m} \boldsymbol{\omega}\_{l} - 1\right). \tag{6.26}$$

Then, we can have

$$\xi = \frac{-\sum\_{l=1}^{m} \Upsilon\_l - 2\eta}{m} \tag{6.27}$$

and

$$
\omega\_l = \frac{1}{m} + \frac{\sum\_{l=1}^{m} \Upsilon\_l}{2m\eta} - \frac{\Upsilon\_l}{2\eta}.\tag{6.28}
$$

Given the testing sample *xt* = {*xt* 1*,* ··· *, xt m*} features for each modality, the prediction of the corresponding label can be achieved by

$$C(\mathbf{x}^{l}) = \arg\max\_{k} \sum\_{l=1}^{m} \alpha\_{l} \mathbf{x}\_{l}^{l} \prescript{\mathsf{T}}{}{\mathbf{M}}\_{l}. \tag{6.29}$$

The overall algorithm is shown in Fig. 6.2. The optimization of sub-hypergraph weights is effective as the incorporation of the multi-modal data via multiple subhypergraphs can make it flexible to investigate the contributions of different data or information on the learning process.

#### **6.3 Hypergraph Structure Optimization**

Although the above component optimization methods can modify the weights of hyperedges, vertices, or sub-hypergraphs, it is not easy to precisely adjust the inappropriate or wrong connections since the intersections between vertices and hyperedges cannot be changed, i.e., the incidence matrix of the hypergraph is

fixed. To solve this challenge and further optimize the hypergraph structure, it is imperative to investigate how to finely optimize the hypergraph structure and dynamically learn the high-order relationship. It can be regarded as finding the optimal hypergraph structure in a hypergraph space, as shown in Fig. 6.3.

In this part, we introduce the dynamic hypergraph structure learning method [6], and Fig. 6.4 shows the framework of this method. Different from the above methods, structure optimization on incidence matrix aims to optimize the incidence matrix **H**.

**Fig. 6.3** An illustration of hypergraph structure evolution

The output **F** and the incidence matrix **H** are jointly optimized by the dualoptimization method. The objective function of the joint learning can be formulated as

$$\arg\min\_{\mathbf{F},0\preceq\mathbf{H}\preceq1}\Psi(\mathbf{F}) := \left\{\Omega(\mathbf{F},\mathbf{H}) + \lambda\mathcal{A}\_{\text{emp}}^{\vee}(\mathbf{F}) + \mu\Phi(\mathbf{H})\right\}.\tag{6.30}$$

There are three terms in the objective function, explained as follows:

• First, *Ω(***F***,* **H***)* is the regularizer related to **F** and **H**. The output **F** is the tobe-learned label vectors of vertices. Therefore, smoothness is expected to be conducted on the hypergraph structure, where the commonly used regularizer of hypergraph smoothness can be written as

$$\mathcal{Q}(\mathbf{F}, \mathbf{H}) = \text{tr}\left(\mathbf{F}^{\top} \left(\mathbf{I} - \mathbf{D}\_v^{-1/2} \mathbf{H} \mathbf{W} \mathbf{D}\_e^{-1} \mathbf{H}^{\top} \mathbf{D}\_v^{-1/2}\right) \mathbf{F}\right). \tag{6.31}$$

However, the regularizer in the previous methods is a function only of **F**, while **H** is a stable parameter. Here, the regularizer is a function of both **F** and **H**.

$$\boldsymbol{\Phi}(\mathbf{F}) = \text{tr}\left(\mathbf{X}^{\top} \left(\mathbf{I} - \mathbf{D}\_{v}^{-1/2} \mathbf{H} \mathbf{W} \mathbf{D}\_{e}^{-1} \mathbf{H}^{\top} \mathbf{D}\_{v}^{-1/2}\right) \mathbf{X}\right). \tag{6.32}$$

To summarize, the general objective function in Eq. (6.30) for dynamic hypergraph structure learning is instantiated as

$$\arg\min\_{\mathbf{F},0\preceq\mathbf{H}\preceq\mathbf{I}}\Psi(\mathbf{F}) := \text{tr}\left(\left(\mathbf{I} - \mathbf{D}\_v^{-1/2}\mathbf{H}\mathbf{W}\mathbf{D}\_e^{-1}\mathbf{H}^\top\mathbf{D}\_v^{-1/2}\right)\left(\mathbf{F}\mathbf{F}^\top + \mu\mathbf{X}\mathbf{X}^\top\right)\right)$$

$$+\lambda\|\mathbf{F} - \mathbf{Y}\|^2. \tag{6.33}$$

Similar to the previous methods, the alternative optimization algorithm is applied to solve the dual-optimization problem. The sub-problem about **F** has the same closed-form solution as traditional hypergraph learning [8].

The most important point that is different from the previous one is the subproblem about **H**, which is written as

$$\begin{split} \arg\min\_{0 \le \mathbf{H} \le 1} \mathcal{Q}(\mathbf{H}) &= \mathcal{Q}(\mathbf{H}) + \mu \Phi(\mathbf{H}) \\ &= \text{tr}\left( \left( \mathbf{I} - \mathbf{D}\_v^{-1/2} \mathbf{H} \mathbf{W} \mathbf{D}\_e^{-1} \mathbf{H}^\top \mathbf{D}\_v^{-1/2} \right) \mathbf{K} \right), \end{split} \tag{6.34}$$

where **K** = **FF**- +*μ***XX**-. The projected gradient method is employed here because Eq. (6.34) is a complex function of **H** with a bound constraint. The gradient is derived as

$$\begin{split} \nabla \mathcal{Q}(\mathbf{H}) &= \mathbf{J} \left( \mathbf{I} \otimes \mathbf{H}^{\top} \mathbf{D}\_{v}^{-1/2} \mathbf{K} \mathbf{D}\_{v}^{-1/2} \mathbf{H} \right) \mathbf{W} \mathbf{D}\_{e}^{-2} \\ &+ \mathbf{D}\_{v}^{-3/2} \mathbf{H} \mathbf{W} \mathbf{D}\_{e}^{-1} \mathbf{H}^{\top} \mathbf{D}\_{v}^{-1/2} \mathbf{K} \mathbf{J} \mathbf{W} - 2 \mathbf{D}\_{v}^{-1/2} \mathbf{K} \mathbf{D}\_{v}^{-1/2} \mathbf{H} \mathbf{W} \mathbf{D}\_{e}^{-1}, \end{split} \tag{6.35}$$

where **J** = **11**-. The detailed derivation process can be found in [6]. The step size of learning **H** is set as *α*. Since **H** is required to be in the range of [0*,* 1], the projection *P* on the feasible set is conducted after each update. Therefore, **H** is updated by

$$\mathbf{H}\_{k+1} = \mathbf{P} \left[ \mathbf{H}\_k - a \nabla \mathcal{Q} \left( \mathbf{H}\_k \right) \right],\tag{6.36}$$

where

$$\mathcal{P}\left[h\_{ij}\right] = \begin{cases} h\_{ij} & \text{if } 0 \le h\_{ij} \le 1 \\ 0 & \text{if } h\_{ij} < 0 \\ 1 & \text{if } h\_{ij} > 1 \end{cases} \tag{6.37}$$

In this way, we can alternately optimize **F** and **H** until the objective function converges.

The dynamic hypergraph structure learning method can outperform the traditional hypergraph learning consistently. This is due to the fact that the dynamic hypergraph structure can fit the data better and formulate the high-order correlation more effectively. Furthermore, both the feature and the label information are applied for the hypergraph structure optimization. Therefore, the learned hypergraph structure is smooth on the feature space and the label space. In other words, the vertices with the same labels have stronger high-order connections, which benefit the downstream task. We also note that the above dynamic hypergraph structure optimization method is with relatively high computational complexity, as it optimizes the whole incidence matrix **H**.

#### **6.4 Incremental Learning on Growing Data**

Most of the existing methods consider the static structures with fixed sets of vertices and edges, while the data are generally dynamic in real-world applications. Under such circumstances, the vertices and connections can be added or removed, and the vertex attributes and connects weights change during the dynamic procedure. Generally, there are two typical ways of dynamic structure learning, i.e., using recurrent architectures [9, 10] and capturing temporal patterns [11, 12]. However, the efficient learning of temporally growing structure has not been explored yet, where the vertex and edge sets are expanding over time. Taking the citation network into consideration, new publications and citation links are continuously added into the network.

The incremental subgraph is the subgraph with the newly appeared vertices and related new edges in the given growing graph at each time step. The edges connecting the vertices from the same incremental subgraph are denoted as intraedges, while the edges connecting the vertices from different incremental subgraphs are denoted as inter-edges. The incremental learning method aims to update the model based on the incremental subgraphs at each time step and perform on the entire graph consistently. The challenge of the incremental graph learning method is how to design the efficient strategy to update the model with incremental data and maintain the performance on the whole dataset.

The main differences between incremental graph learning and existing incremental learning methods are as follows:

There are two straightforward solutions of incremental graph learning. First, the static graph learning methods can directly be applied on the whole graph at each time step, which suffers from a high computation cost. Second, only learn from the incremental subgraph, which leads to bias to the newly coming subgraphs and loses the information of the inter-edges.

In this section, we introduce incremental learning for graphs on the growing data. During training, a graph G *L t* with a smaller number of vertices and edge sets from the growing graph {G*t*} is generated for updating current model, which can be implemented by existing GNN methods for specified graph learning task and can perform on the entire observed graph at any time. Vertices and edges within restricted numbers from the old graph are selected and combined with new subgraph into G *L t* . Therefore, G *L t* is unbiased to the entire graph and enough inter-edges are preserved. The overview of the IGL is shown in Fig. 6.5.

To address these issues of subgraph bias and inter-edges missing, the following conditions should be considered for generating learning.

*Unbiased Estimation of Neighboring Aggregation* To alleviate the bias of subgraph, the aggregation results of vertices in G *L t* should be unbiased estimations of them in the entire graph, i.e., ∀**v** ∈ V*t* ,

$$\mathbb{E}\left(\text{agg}\left(\mathbf{v}, \mathcal{N}\_t(\mathbf{v}) \cap \mathcal{V}\_t^L\right) \mid \mathbf{v} \in \mathcal{V}\_t^L\right) = \text{agg}\left(\mathbf{v}, \mathcal{N}\_t(\mathbf{v})\right),\tag{6.38}$$

where *agg(***v***,* N *)* is the aggregator function of GNN to aggregate vertex embeddings from N to **v**, and N*t(***v***)* = {**u** ∈ V*t* | *(***u***,* **v***)* ∈ E*t*} is the neighborhood set of vertex **v**. Thus, N*t(***v***)* ∩ V *L t* represents the sampled neighboring vertices in G *L t* .

*Preservation of Inter-edges* Since the missing of inter-edges may seriously affect training, we aim at preserving more edges of E *inter t* in *Δ*E *L t* , which can be formulated as

$$\begin{array}{ll}\max\_{\Delta \mathcal{E}\_l^L} |\Delta \mathcal{E}\_l^L \cap \mathcal{E}\_l^{inner}|.\\\\ \text{s.t.} \quad |\Delta \mathcal{E}\_l^L| \le E\_{\max}.\end{array} \tag{6.39}$$

The edge preservation can be required as a definite optimization problem in Eq. (6.39) or sampling problem with priority to vertices with higher degrees so that *P (***u** ∈ V *L t )* ∝ |{*(***u***,* **v***)* ∈ E *inter t* | **v** ∈ V *new t* }|.

IGL is based on the unbiased and edge-preserved conditions. In the presentation of method, we follow the memory constraint *Vmax* and set *Emax* = *(*|V *new t* | + *Vmax )*2 − |E *intra t* | by default. The generated edges can be uniformly sampled if a smaller *Emax* is required. The sample-based strategy is presented to select a subgraph from the previous graph for learning. The following cluster-based strategy is presented to construct a cluster graph that satisfies both the unbiased and edgepreserved conditions in midway. The presented strategies are illustrated in Fig. 6.6.

#### **(1) Sample-Based Strategy**

The strategy of sampling a representative subgraph from previous data based on the required conditions is studied first. We assume that a subset *Δ*V *L t* from V*t*−1 in size of *Vmax* is sampled, and all the related edges are preserved, i.e.,

$$\begin{aligned} \Delta \mathcal{V}\_l^L &= \text{Sample}\ (\mathcal{Y}\_{l-1}, V\_{\text{max}}),\\ \Delta \mathcal{E}\_l^L &= \{ (\mathbf{u}, \mathbf{v}) \in \mathcal{E}\_l^{inter} \mid \mathbf{u} \in \Delta \mathcal{V}\_l^L, \mathbf{v} \in \mathcal{V}\_l^{new} \}, \end{aligned} \tag{6.40}$$

**Fig. 6.6** An illustration of the sample-based and cluster-based strategies

where *Sample()* denotes the sampling function. Considering the required conditions, we explore the following pragmatic methods for appropriate sampling:

The above methods take into consideration only part of required conditions. It can be proved that, ignoring the ideal case when all the vertices in V*t*−1 connect with the same number of vertices in V *new t* , sampling in Eq. (6.40) satisfies the two required conditions when all the vertices have been sampled, i.e., joint training.

#### **(2) Cluster-Based Strategy**

The sample-based strategy selects a subgraph from the previous graph for learning. However, in such a process, G*t*−1 is not completely covered, and some important vertices might be dropped. Then, the selected subgraph cannot perform full communication with the new subgraph. The assumption of sampling that G *L t* must be a subgraph of G*t* is relaxed, and a cluster graph is constructed. Technically, we first arrange vertices in V*t*−1 into *K* cluster sets {C *t*−1 *i* }*K i*=1 with centers {**c***t*−1 *i* }*K i*=1 in average values of clusters. We set the number of clusters *K* = *Vmax* . The cluster graph is therefore defined as

$$\begin{split} \Delta \mathcal{V}\_{t}^{\ell^{L}} &= \{ \mathbf{c}\_{1}^{t-1}, \dots, \mathbf{c}\_{K}^{t-1} \}, \\ \Delta \mathcal{E}\_{t}^{\ell^{L}} &= \{ (\mathbf{c}\_{l}^{t-1}, \mathbf{v}) \mid \mathbf{v} \in \mathcal{V}\_{l}^{new}, \exists \ \mathbf{u} \in \mathcal{C}\_{l}^{t-F1}, (\mathbf{u}, \mathbf{v}) \in \mathcal{E}\_{l}^{inter} \} \cup \\ & \{ (\mathbf{c}\_{l}^{t-1}, \mathbf{c}\_{j}^{t-1}) \mid \exists \ \mathbf{u}\_{1} \in \mathcal{C}\_{l}^{t-1}, \mathbf{u}\_{2} \in \mathcal{C}\_{j}^{t-1}, (\mathbf{u}\_{1}, \mathbf{u}\_{2}) \in \mathcal{E}\_{l-1} \}, \end{split} \tag{6.41}$$

which suggests that the cluster centers be added as new cluster vertices, and the edges connecting to any vertex in V*t*−1 be directly transferred to the corresponding cluster vertex. It is noted that the additional edge sets in Eq. (6.41) represent E *inter t* and E*t*−1, respectively.

Due to the continued growth of the graph, direct clustering on the entire graph is time-consuming. For an approximate but efficient clustering with a balanced size, we first conduct clustering on the new vertices V *new t* into cluster sets {*Δ*C *t i* }*K i*=1 with centers {**c**ˆ*t i*}*K i*=1. The bipartite matching algorithm is applied to optimize a bijective matching function *M(*·*)* : {1*, ..., K*}→{1*, ..., K*} for the objective: min*m(*·*) ΣK k*=1**c***t*−1 *k* − **c**ˆ*t m(k)*2 2, which assigns new clusters to be closer with old clusters. Then, we merge the clusters as C *t k* = C *t*−1 *k* ∪ *Δ*C *t m(k)* and update the value of centers **c***t k*.

In a word, incremental graph learning (IGL) is a general framework for efficient learning on growing graphs in an incremental manner, which has the following advantages. First, IGL is more suitable in real-world applications, since the dynamic graphs are commonly appeared. Second, the sample-based and cluster-based strategies significantly improve the efficiency when the large scale graph grows. However, only the incremental of the nodes and edges are considered, while the deletion are ignored, which limits the application of the method. The general dynamic patterns are worth studying in the future works.

#### **6.5 Summary**

In this chapter, we introduce hypergraph structure evolution methods, i.e., hyperedge weight optimization, vertex weight optimization, sub-hypergraph weight optimization, dynamic hypergraph learning, and the techniques for incremental learning on growing graphs. The hyperedge weight optimization adjusts weights of each hyperedge for different contributions, while the vertex weight optimization considers the different importance of vertices on hypergraph. The sub-hypergraph weight optimization method further combines multiple hypergraphs for multi-modal data with learned weights. Dynamic hypergraph learning optimizes the hypergraph structure by modifying the inappropriate connections, which can partially solve the missing and incorrect connection issue. Finally, we introduce the incremental learning method on growing graphs, which can update the data structure under the incremental scenario.

It is noted that the optimization of hypergraph, either component or the structure, will bring in extra computational cost and lead to potentially high computation complexity in practice. How to effectively and efficiently adjust the hypergraph structure is still a challenging problem, which requires further investigation in future.

#### **References**

**Open Access** This chapter is licensed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license and indicate if changes were made.

The images or other third party material in this chapter are included in the chapter's Creative Commons license, unless indicated otherwise in a credit line to the material. If material is not included in the chapter's Creative Commons license and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder.

## **Chapter 7 Neural Networks on Hypergraph**

**Abstract** With the development of deep learning on high-order correlations, hypergraph neural networks have received much attention in recent years. Generally, the neural networks on hypergraph can be divided into two categories, including the spectral-based methods and the spatial-based methods. For the spectral-based methods, the convolution operation is formulated in the spectral domain of graph, and we introduce the typical spectral-based methods, including hypergraph neural networks (HGNN), hypergraph convolution with attention (Hyper-Atten), and hyperbolic hypergraph neural network (HHGNN), which extend hypergraph computation to hyperbolic spaces beyond the Euclidean space. For the spatial-based methods, the convolution operation is defined in groups of spatially close vertices. We then present spatial-based hypergraph neural networks of the general hypergraph neural networks (HGNN+) and the dynamic hypergraph neural networks (DHGNN). Additionally, there are several convolution methods that attempt to reduce the hypergraph structure to the graph structure, so that the existing graph convolution methods can be directly deployed. Lastly, we analyze the association and comparison between hypergraph and graph in the two areas described above (spectral-based, spatial-based), further demonstrating the ability and advantages of hypergraph on constructing and computing higher-order correlations in the data.

#### **7.1 Introduction**

Hypergraph has demonstrated its ability to model and learn complex correlations in recent years. Zhou et al. [1] introduced the hypergraph learning, which conducts transductive learning and propagates information on the hypergraph structure. Transductive inference on the hypergraph aims to minimize the label difference between vertices with stronger connections. There has been extensive development and application of hypergraph learning in several fields over the past few years.

In addition, hypergraph has been investigated in deep learning applications. Based on the hypergraph Laplacian and the Chebyshev formula, Feng et al. [2] first introduced hypergraph neural networks (HGNN). The hypergraph Laplacian is synthesized using predictions in Yadati et al. [3], while Bai et al. [4] defined two neural hypergraph operators based on [5, 6]. However, they do not implement highorder learning algorithms by introducing only vertex functions, even though they construct a simple weighted graph and apply mature graph learning algorithms. A lack of powerful tools for expressing hyperstructure and a wealth of graph literature motivated the work of [7]. Additionally, recent successes with graph representation learning have been achieved by using neural operators (convolution, attention, spectral, etc.). Generally, the neural networks on hypergraph can be divided into two categories, including the spectral-based methods and the spatial-based methods.

For the spectral-based methods, Feng et al. [2] introduced the hypergraph neural networks (HGNN) for modeling and learning beyond pairwise complex correlations. Different from the traditional graph neural networks (GNN), HGNN learns its data representation by iteratively propagating the vertex–hyperedge– vertex information pattern. Additionally, the hypergraph Laplacian is first approximated and introduced into the deep hypergraph learning method to speed up the learning process. Following [2], Bai et al. [4] developed an attention module based on hypergraph convolution patterns (Hyper-Atten). Hyper-Atten introduced a hyperedge–vertex attention learning module that adaptively identifies the importance of different vertices in a hyperedge, thus revealing the intrinsic correlations between vertices.

Using the spatial methods, Atwood et al. [8] made use of transition matrices to determine where vertices are located. The generalization of convolution in the spatial domain is achieved using Gaussian mixture models based on local path operators. A graph-based attention-based architecture was built in work [9] for analyzing vertices on graph using attention mechanism. A dynamic change in hypergraph structure was taken into considerations in [6]. The framework introduced in [6], which is more versatile than HGNN [2]. A unified hypergraph is then constructed by merging the correlations from different modalities/types using an adaptive hyperedge grouping strategy. To learn a general data representation for various tasks, a hypergraph convolution scheme [6] was performed in the spatial domain.

Hypergraph spectral graph theory [10] has been explored far less in other methods. The concept of hypergraph learning was first introduced by Zhou et al. [1], where it was presented as a propagation process. The Laplacian matrix, however, is equivalent to pairwise operations according to [11]. There have been several studies addressing non-pairwise relationships since then, including developing nonlinear Laplacian operators [12, 13], learning the optimal parameters of hyperedges [13, 14], as well as utilizing random walking techniques [10]. Hyperedges can be regarded as connectors in these algorithms, which explicitly break the bipartite property of hypergraph by focusing on vertices.

In this chapter, we systematically introduce the above three types of neural networks on hypergraph and show the comparison between graph neural networks and hypergraph neural networks from both spectral and spatial aspects. Part of the work introduced in this chapter has been published in [2, 15, 16].

#### **7.2 Spectral-Based Neural Networks on Hypergraph**

The spectral neural networks methods have attracted much attention since Bruna et al. [17] and Kipf et al. [18] simplified them in a graph convolutional network pattern. The data are transformed from the common domain to the spectral domain to be processed with according to map theory and the convolution theorem, and it then gets transformed back to the common domain. In other words, first we convert the signal from the common domain to the frequency domain (Fourier transform implementation) and then multiply it by the phase. Then, we convert the result of the phase multiplication back to the common domain again (Fourier inverse transform implementation). We will present spectral-based hypergraph neural networks methods, including hypergraph neural networks (HGNN) [2], hypergraph convolution with attention (Hyper-Atten) [3], and hyperbolic hypergraph neural networks (HHGNN) [19]. In particular, HHGNN extends hypergraph learning to the hyperbolic spaces beyond the Euclidean space.

#### *7.2.1 Hypergraph Neural Networks*

Given a hypergraph G = *(*V *,* E *, Δ)* with *N* vertices, the hypergraph Laplacian *Δ* is an *N* × *N* positive semi-definite matrix. The orthonormal eigen vectors *Φ* = diag*(φ*1*,...,φN )* and a diagonal matrix *Λ* = diag*(λ*1*,...,λN )*, which contains the corresponding non-negative eigenvalues, are obtained by employing the eigendecomposition *Δ* = *ΦΛΦ*-. *x*ˆ = *Φx* defines the Fourier transform for a signal *x* = *(x*1*,...,xN )* in the hypergraph. It is assumed that the eigenvectors represent the Fourier bases and the eigenvalues represent the frequencies. The spectral convolution of signal *x* and filter *g* can be denoted as

$$\mathbf{g}\star\mathbf{x} = \Phi((\boldsymbol{\Phi}^{\top}\boldsymbol{g})\odot(\boldsymbol{\Phi}^{\top}\boldsymbol{x})) = \boldsymbol{\Phi}\mathbf{g}(\boldsymbol{\Lambda})\boldsymbol{\Phi}^{\top}\mathbf{x},\tag{7.1}$$

where denotes the element-wise Hadamard product and *g(Λ)* = diag*(g(λ*1*), . . . , g(λn))* indicates a function of the Fourier coefficients. However, in the forward and inverse Fourier transforms, the computational cost is *O(n*2*)*, which is high. To solve this problem, Defferrard et al. [20] parameterize *g(Λ)* with *K*-order polynomials, and one such polynomial is the truncated the Chebyshev expansion. Chebyshev polynomials *Tk(x)* are computed by the formula of *Tk(x)* = 2*xTk*−1*(x)* − *Tk*−2*(x)*, with *T*0*(x)* = 1 and *T*1*(x)* = *x*. After that, the *g(Λ)* can be computed by

$$\log \star x \approx \sum\_{k=0}^{K} \theta\_k T\_k(\tilde{\Delta}) x,\tag{7.2}$$

where *Tk(Δ)*˜ denotes the Chebyshev polynomial of order *k* with scaled Laplacian *Δ*˜ = 2 *λmax Δ*−*I* . In Eq. (7.2), matrix powers, additions, and multiplications are combined instead of expansive computation of Laplacian Eigen vectors, thus improving computation complexity even further. Since that the Laplacian in hypergraph can already represent the high-order correlations among nodes, it can further limit the order of convolution operation to *K* = 1. It is suggested by Kipf et al. [18] that *λmax* ≈ 2 for the scale adaptability of neural networks. After that, the convolution operation can be simplified to

$$\mathbf{g} \star \mathbf{x} \approx \theta\_0 \mathbf{x} - \theta\_1 \mathbf{D}\_v^{-1/2} \mathbf{H} \mathbf{W} \mathbf{D}\_e^{-1} \mathbf{H}^\top \mathbf{D}\_v^{-1/2} \mathbf{x},\tag{7.3}$$

where *θ*0 and *θ*1 represent the parameters of all node filters. In addition, a single parameter *θ* is used to avoid the overfitting problem, which is defined as

$$\begin{cases} \theta\_{\mathbb{I}} = -\frac{1}{2}\theta\\ \theta\_{0} = \frac{1}{2}\theta \mathbf{D}\_{v}^{-1/2} \mathbf{H} \mathbf{D}\_{e}^{-1} \mathbf{H}^{\top} \mathbf{D}\_{v}^{-1/2} . \end{cases} \tag{7.4}$$

Thereafter, the convolution process can be simplified to the following function:

$$\begin{split} \mathbf{g} \star \mathbf{x} &\approx \frac{1}{2} \theta \mathbf{D}\_{v}^{-1/2} \mathbf{H} (\mathbf{W} + \mathbf{I}) \mathbf{D}\_{e}^{-1} \mathbf{H}^{\top} \mathbf{D}\_{v}^{-1/2} \mathbf{x} \\ &\approx \theta \mathbf{D}\_{v}^{-1/2} \mathbf{H} \mathbf{W} \mathbf{D}\_{e}^{-1} \mathbf{H}^{\top} \mathbf{D}\_{v}^{-1/2} \mathbf{x}, \end{split} \tag{7.5}$$

where *(***W**+ **I***)* can be regarded as the weight of the hyperedges. In the initialization of **W**, the hyperedges can be all assigned with equal weights as an identity matrix.

When having a hypergraph signal **X***t* for the *t*-th layer, the hyperedge convolution layer **HGNNConv** can be formulated by

$$\mathbf{X}^{t+1} = \sigma(\mathbf{D}\_v^{-1/2}\mathbf{H}\mathbf{W}\mathbf{D}\_e^{-1}\mathbf{H}^\top\mathbf{D}\_v^{-1/2}\mathbf{X}^t\Theta),\tag{7.6}$$

where *Θ* is the parameter to be learned during the training process. To extract features from a hypergraph, the filter *Θ* is applied to the vertices. After convolution, **X***t*+1, which can be used for further processing.

The framework of the abovementioned HGNN model is shown in Fig. 7.1. HGNN is able to address the challenges of learning representations for complex data by incorporating such data structures into hypergraph, which are more flexible and effectively confronting practical data.

The HGNN calculation stages are shown in Fig. 7.2, and the three processes are directly projected to the functions. We can observe that there are vertex feature transform, hyperedge feature gathering, and vertex feature aggregating steps in this framework.

#### *7.2.2 Hypergraph Convolution and Hypergraph Attention*

Based on the study of hypergraph neural networks [2], Bai et al. [4] introduced hypergraph convolution and hypergraph attention (Hyper-Atten) by introducing attention mechanism in the framework.

In this method, an explicit magnitude of importance is assigned to the afferent and efferent information flow for non-binary values of the transition probability between vertices for a given vertex. However, such an attention mechanism must work after the graph structure (the incidence matrix **H**) is given, instead of learning a dynamic incidence matrix. It is easier to reveal the intrinsic relationship between vertices using a dynamic transition matrix than by using a fixed incidence matrix. An attention learning module could be imposed on **H**, which does not treat each vertex as being connected by a hyperedge or which does not assign non-binary and real values when measuring the degree of connectivity. Following [6] when the vertex set and the edge set are comparable, the attention score between a given vertex *xi* and its associated hyperedge *xj* can be written as

$$\mathbf{H}\_{lj} = \frac{\exp\left(\sigma\left(\text{sim}\left(x\_l \mathbf{P}, x\_j \mathbf{P}\right)\right)\right)}{\sum\_{k \in N\_l} \exp\left(\sigma\left(\text{sim}\left(x\_l \mathbf{P}, x\_k \mathbf{P}\right)\right)\right)},\tag{7.7}$$

where *σ (*·*)* is a nonlinear activation function. The weight matrix between the *(l)*-th and *(l* + 1*)*-th layers is denoted as **P** ∈ R*F(l)*×*F(l*+1*)* . *Ni* is the neighborhood set of *xi*. The pairwise similarity of two vertices is computed with this similarity function sim*(*·*)*:

$$\text{sinc}\left(\mathbf{x}\_{l}, \mathbf{x}\_{f}\right) = \mathbf{a}^{\top} \left[\mathbf{x}\_{l} \| \mathbf{x}\_{f}\right]. \tag{7.8}$$

Operation [*, ,*] indicates concatenation, and notation **a** is a weight vector for outputting a scalar similarity value.

When following Eq. (7.6) to learn the intermediate embedding of vertices layer by layer, hypergraph attention also propagates gradients to **H** in addition to **X***(l)* and *Θ*. Therefore, Eq. (7.7) means the share of hyperedge *xj* in the neighbors of the vertex *xi*, which indicates the relative importance *xj* of *xi*. More categorical embeddings can be learned by the probabilistic model, and the relationship between vertices can be described more accurately.

In order to further enhance the capability of representation learning, the method uses hypergraph attention mechanisms based on the basic formulation of performing convolutions.

#### *7.2.3 Hyperbolic Hypergraph Neural Networks*

The hyperbolic space is a manifold with constant Gaussian negative curvature everywhere, which has several models. Similar to [21, 22], the work is based on the Poincaré ball model for its well-suited for gradient-based optimization. The Poincaré ball model with constant negative curvature −1*/k(k >* 0*)* corresponds to the Riemannian manifold P*n,k, g*P **x** . P*n,k* = {**x** ∈ R*n* : **x** *<* 1} is an open *n*-dimensional unit ball, where *.* denotes the Euclidean norm. Its metric tensor is *g*P **x** = *λ*2 **x***g*E, where *λ***x** = 2 1−*k***x**2 is the conformal factor and *g*E = **I***n* is the Euclidean metric tensor. Then, we define the Möbius addition of two points **x***,* **y** ∈ P*n,k* as follows:

$$\mathbf{x} \oplus\_{k} \mathbf{y} = \frac{\left(1 + 2k \langle \mathbf{x}, \mathbf{y} \rangle + k \|\mathbf{y}\|^2\right) \mathbf{x} + \left(1 - k \|\mathbf{x}\|^2\right) \mathbf{y}}{1 + 2k \langle \mathbf{x}, \mathbf{y} \rangle + k^2 \|\mathbf{x}\|^2 \|\mathbf{y}\|^2}. \tag{7.9}$$

The distance between two points **x***,* **y** ∈ P*n,k* is calculated by integration of the metric tensor, which is given as

$$d\_{\mathbb{P}}^{k}(\mathbf{x}, \mathbf{y}) = (2/\sqrt{k}) \tanh^{-1} \left(\sqrt{k} \| -\mathbf{x} \oplus\_{k} \mathbf{y} \| \right). \tag{7.10}$$

Here we can denote point **z** ∈ TxP*n,k* as the tangent (Euclidean) space centered at any point **x** in the hyperbolic space. For the tangent vector **z** = **0** and the point **y** = **0**, the exponential map exp**x** : T**x**P*n,k* → P*n,k* and the logarithmic map log**x** : P*n,k* → T**x**P*n,k* are given for **y** = **x** by

$$\exp\_\mathbf{x}^k(\mathbf{z}) = \mathbf{x} \oplus\_k \left( \tanh\left(\sqrt{k} \frac{\lambda\_\mathbf{x}^k \|\mathbf{z}\|}{2}\right) \frac{\mathbf{z}}{\sqrt{k} \|\mathbf{z}\|} \right) \tag{7.11}$$

and

$$\log\_{\mathbf{x}}^{k}(\mathbf{y}) = \frac{2}{\sqrt{k}\lambda\_{\mathbf{x}}^{k}} \tanh^{-1}\left(\sqrt{k}\parallel - \mathbf{x} \oplus\_{k} \mathbf{y} \parallel\right) \frac{-\mathbf{x} \oplus\_{k} \mathbf{y}}{\parallel - \mathbf{x} \oplus\_{k} \mathbf{y} \parallel}.\tag{7.12}$$

The transformation between the tangent space and the hyperbolic space is shown in Fig. 7.3. Leverage the operations of exp and log maps, so that we can use the tangent space T**x**P to perform transformations such as convolution and activation in Euclidean space. In the convolution, vertex information is first gathered to the hyperedge for storage, and then each vertex aggregates the information of the connected hyperedge.

It is noted that initial data are on the Euclidean space and need to be converted into embeddings on the hyperbolic space, so then first project the data on the previously obtained Euclidean space onto the hyperbolic manifold space in order to use the spectral-based hypergraph hyperbolic convolutional network to learn the information to update the node embeddings. Set *t* := {√*k,* 0*,* 0*,...,* 0} ∈ P*d,k*

**Fig. 7.3** The transformation between the tangent space and the hyperbolic space

as a reference point to perform tangent space operations. The above condition makes *(*0*,* **x**0*,*E*), t*= 0 hold, so *(*0*,* **x**0*,*E*)* can be regarded as the initial embedding representation of the hypergraph structure on the tangent plane of the hyperbolic manifold space T*t*P*d,k*. The initial hypergraph structure embedding is then mapped onto the hyperbolic manifold space P following [19]:

$$\begin{split} \mathbf{x}^{0,\mathbb{P}} &= \exp\_{l}^{k} \left( \left( 0, \mathbf{x}^{0,\mathbb{E}} \right) \right) \\ &= \left( \sqrt{k} \cosh \left( \frac{\|\mathbf{x}^{0,\mathbb{E}}\|\_{2}}{\sqrt{k}} \right), \sqrt{k} \sinh \left( \frac{\|\mathbf{x}^{0,\mathbb{E}}\|\_{2}}{\sqrt{k}} \right) \frac{\mathbf{x}^{0,\mathbb{E}}}{\|\mathbf{x}^{0,\mathbb{E}}\|\_{2}} \right). \end{split} \tag{7.13}$$

Unlike the previous study [23] that simply generates the hyperedge structure for common domain convolution, combined with the inspiration provided by HGNN [2], hypergraph computation from the perspective of spectral convolution can be conducted.

Given hyperbolic curvatures −1*/k*−1*,* −1*/k* at layers −1 and , respectively, then the hyperbolic hypergraph convolution of the hypergraph input signal *x*P with filter g can be defined as

$$\begin{split} \mathbf{x}^{\mathbb{P}} \ast \mathbf{g} &= \exp\_{\mathbf{x}}^{k\ell} \left( \Phi \left( \left( \Phi^{\top} \left( \log\_{\mathbf{x}}^{k\_{\ell-1}} \left( \mathbf{x}^{\mathbb{P}} \right) \right) \right) \odot \left( \Phi^{\top} \mathbf{g} \right) \right) \right) \\ &= \exp\_{\mathbf{x}}^{k\_{\ell}} \left( \Phi \mathbf{g}(\boldsymbol{A}) \Phi^{\top} \left( \log\_{\mathbf{x}}^{k\_{\ell-1}} \left( \mathbf{x}^{\mathbb{P}} \right) \right) \right), \end{split} \tag{7.14}$$

where is the element-wise product, *g(Λ)* = diag*(θ )*, and *θ* = [*θ*1*,* ··· *, θn*] is the parameters to be learned. Leverage the operations of exp and log maps, so that the tangent space T0P*d,k* can be used to perform Euclidean transformations. It operates in the tangent space of each center point *x*P because the Euclidean approximation is best [19].

Considering the high computational complexity of the Fourier transform and inverse Fourier transform, this convolution method is very expensive to calculate. Convolutions can be computed more efficiently by truncating Chebyshev polynomials as [2]. It can be simply expressed as

$$\mathbf{x}^{\mathbb{P}} \ast \; \mathbf{g} \approx \exp\_{\boldsymbol{\chi}}^{k\_{\ell}} \left( \theta \mathbf{D}\_{\boldsymbol{v}}^{-1/2} \mathbf{H} \mathbf{W} \mathbf{D}\_{\boldsymbol{e}}^{-1} \mathbf{H}^{\top} \mathbf{D}\_{\boldsymbol{v}}^{-1/2} \left( \log\_{\boldsymbol{\chi}}^{k\_{\ell-1}} \left( \mathbf{x}^{\mathbb{P}} \right) \right) \right), \tag{7.15}$$