Название: Hypergraph Computation
Автор: Qionghai Dai, Yue Gao
Издательство: Springer
Серия: Artificial Intelligence: Foundations, Theory, and Algorithms
Год: 2023
Страниц: 251
Язык: английский
Формат: pdf (true)
Размер: 10.2 MB

Artificial Intelligence (AI) is now everywhere and fuels both industry and daily life all over the world. We are in the era of “Big Data,” and huge sums of information can be obtained which are too cumbersome for people to process themselves. These Big Data are even with much complex correlations behind them in various areas, such as computer vision and social media. For example, the complex correlations among pixels in an image reveal its semantic information, and different types of correlations among social posts infer the users’ emotions. Therefore, developing effective AI methods to exploit such complex data correlations has become an urgent but challenging task.

Graph has been widely used to formulate data correlations. A graph is a non-linear data structure which is composed of groups of vertices and edges, representing the pairwise correlations among vertices. Graph learning and graph neural networks have attracted much attention in both research and industrial fields and become very hot topics in these years. It is noted that the world is far more complex than just pairwise connections, and thus graph-based methods still have limitations on high-order correlation modeling.

Hypergraph, as a generation of graph, is able to formulate such high-order correlations among the data and has been investigated in last decades. Recent years have witnessed a great popularity of research on hypergraph-related AI methods, which have been used in computer vision, social media analysis, and etc. We noticed that there still has not been a theoretical book to systematically introduce the recent achievements in this field and then started preparation of this book. We summarize these attempts as a new computing paradigm, called hypergraph computation, which is to formulate the high-order correlations underneath the data using hypergraph, and then conduct semantic computing on the hypergraph for different applications.
In this book, we introduce recent progress in hypergraph computation, from hypergraph modeling to hypergraph neural networks. The applications of hypergraph computation are also discussed. We also summarize the recent achievements and useful tools in hypergraph computation. This book can be regarded as both a theoretical book and a manual on how to use hypergraph computation in practice.

In this century, hypergraph has been used in Machine Learning. Transductive hypergraph learning is introduced to give the basic mathematical formulation of the objective function for predicting labels of vertices on a hypergraph. Since the performance of hypergraph learning is related to the modeling quality of the hypergraph, there are some efforts to further assign weights to the components in the hypergraph, including hyperedges, vertices, and hyperedge-dependent vertex weights. To accelerate the label propagation process on hypergraph, the cross diffusion on multiple hypergraphs is further introduced to model the high-order correlations among multi-modal data and conduct multi-modal information fusion.

Research on high-order representations of hypergraph structures has also been inspired by Deep Learning’s powerful learning and modeling abilities. Generally speaking, most Deep Learning methods on hypergraph can be divided into spectral-based methods and spatial-based methods. As for the spectral-based methods, Feng et al. proposed Hypergraph Neural Networks (HGNNs) to model non-pairwise relations based on the hypergraph Laplacian. Multi-modal data can be naturally modeled using the proposed methods. It is also possible to classify images using hypergraph neural networks[54]. Using tools from the spectral theory of hypergraphs, Yadati et al. proposed HyperGCN to train a GCN for semi-supervised learning on hypergraphs using graph convolutional networks (GCNs).

The Chapter 12 introduces the DeepHypergraph library, a hypergraph computation library based on Python, which bridges the hypergraph theory and hypergraph applications. This library provides the generation of multiple low-order structures (such as graph and directed graph), high-order structures (such as hypergraph and directed hypergraph), datasets, operations, learning methods, visualizations, etc. We first introduce the design motivation and the overall architecture of the library. Then, we introduce the “correlation structure” and “function library” of the Deephypergraph library, respectively.

We have designed DeepHypergraph (DHG), a Deep Learning library built upon PyTorch for hypergraph computation. It is a general framework that supports both low-order and high-order message passing such as from vertex to vertex, from vertex in one domain to vertex in another domain, from vertex to hyperedge, from hyperedge to vertex, and from vertex set to vertex set. It supports the generation of a wide variety of structures such as low-order structures (graph, directed graph, bipartite graph, etc.) and high-order structures (hypergraph, etc.).

Prerequisites
This book is designed for advanced undergraduate and graduate students, postdoctoral researchers, lecturers, researchers, and industrial engineers, as well as anyone interested in AI, especially hypergraph computation. The readers are expected to have basic knowledge in probability, linear algebra, and Machine Learning. Graph theory could be a good prior before reading this book, but not mandatory.

Contents: