Hypergraph Computation

Description

This open access book discusses the theory and methods of hypergraph computation. Many underlying relationships among data can be represented using graphs, for example in the areas including computer vision, molecular chemistry, molecular biology, etc. In the last decade, methods like graph-based learning and neural network methods have been developed to process such data, they are particularly suitable for handling relational learning tasks. In many real-world problems, however, relationships among the objects of our interest are more complex than pair-wise. Naively squeezing the complex relationships into pairwise ones will inevitably lead to loss of information which can be expected valuable for learning tasks.  Hypergraph, as a generation of graph, has shown superior performance on modelling complex correlations compared with graph. Recent years have witnessed a great popularity of researches on hypergraph-related AI methods, which have been used in computer vision, social media analysis, etc. 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. The content of this book consists of hypergraph computation paradigms, hypergraph modelling, hypergraph structure evolution, hypergraph neural networks, and applications of hypergraph computation in different fields. We further summarize recent achievements and future directions on hypergraph computation in this book. Preface Book Organization Prerequisites Contact Information Acknowledgments Contents Acronyms 1 Introduction 1.1 Background 1.2 The Definition of Hypergraph 1.3 Applications of Hypergraph 1.4 The History of Studies on Hypergraph 1.4.1 Topology and Coloring on Hypergraph 1.4.2 Hypergraph Partitioning, Clustering, and Machine Learning 1.4.3 Deep Learning on Hypergraph 1.5 Hypergraph Computation: Challenges and Objectives 1.6 Structure of This Book 1.7 Summary References 2 Mathematical Foundations of Hypergraph 2.1 Introduction 2.2 Preliminary Knowledge of Hypergraph 2.2.1 Undirected Hypergraph 2.2.2 Directed Hypergraph 2.2.3 Probabilistic Hypergraph 2.2.4 K-Uniform Hypergraph 2.2.5 Hypergraph and Bipartite Graph 2.2.6 The Weights on Hypergraph 2.3 Comparison Between Graph and Hypergraph 2.3.1 Low-Order Versus High-Order Correlations 2.3.2 Adjacency Matrix Versus Incidence Matrix 2.3.3 Structure Transformation from Hypergraph to Graph 2.3.4 Random Walks on Graph and Hypergraph 2.4 Summary References 3 Hypergraph Computation Paradigms 3.1 Introduction 3.2 Intra-hypergraph Computation 3.3 Inter-hypergraph Computation 3.4 Hypergraph Structure Computation 3.5 Summary References 4 Hypergraph Modeling 4.1 Introduction 4.2 Implicit Hypergraph Modeling 4.2.1 Distance-Based Hypergraph Generation 4.2.2 Representation-Based Hypergraph Generation 4.3 Explicit Hypergraph Modeling 4.3.1 Attribute-Based Hypergraph Generation 4.3.2 Network-Based Hypergraph Generation 4.4 Typical Examples of Hypergraph Modeling 4.4.1 Computer Vision 4.4.2 Recommender System 4.4.3 Computer-Aided Diagnosis 4.4.4 Brain Network 4.5 Hypergraph Modeling in Next Stage 4.5.1 Adaptive Hypergraph Modeling 4.5.2 Generative Hypergraph Modeling 4.5.3 Knowledge Hypergraph Generation 4.6 Summary References 5 Typical Hypergraph Computation Tasks 5.1 Introduction 5.2 Label Propagation on Hypergraph 5.3 Data Clustering on Hypergraph 5.4 Cost-Sensitive Learning on Hypergraph (1) Cost-Sensitive Hypergraph Computation (2) Cost Interval Optimization for Hypergraph Computation 5.5 Link Prediction on Hypergraph 5.6 Summary References 6 Hypergraph Structure Evolution 6.1 Introduction 6.2 Hypergraph Component Optimization 6.2.1 Hyperedge Weight Optimization 6.2.2 Vertex Weight Optimization 6.2.3 Sub-hypergraph Weight Optimization 6.3 Hypergraph Structure Optimization 6.4 Incremental Learning on Growing Data 6.5 Summary References 7 Neural Networks on Hypergraph 7.1 Introduction 7.2 Spectral-Based Neural Networks on Hypergraph 7.2.1 Hypergraph Neural Networks 7.2.2 Hypergraph Convolution and Hypergraph Attention 7.2.3 Hyperbolic Hypergraph Neural Networks 7.3 Spatial-Based Neural Networks on Hypergraph 7.3.1 General Hypergraph Neural Networks 7.3.2 Dynamic Hypergraph Neural Networks 7.4 Comparison Between Graph and Hypergraph Neural Networks 7.4.1 Spectral Perspective 7.4.2 Spatial Perspective 7.5 Summary References 8 Large Scale Hypergraph Computation 8.1 Introduction 8.2 Factorization-Based Big-Hypergraph Modeling 8.3 Hierarchical Hypergraph Modeling 8.4 Summary References 9 Hypergraph Computation for Social Media Analysis 9.1 Introduction 9.2 Recommender System 9.2.1 Collaborative Filtering 9.2.2 Attribute Inference 9.3 Sentiment Analysis 9.3.1 Sentiment Prediction 9.3.2 Social Event Detection 9.4 Emotion Recognition 9.5 Summary References 10 Hypergraph Computation for Medical and Biological Applications 10.1 Introduction 10.2 Computer-Aided Diagnosis 10.2.1 MCI Identification Using MRI 10.2.2 Medical Image Retrieval 10.2.3 COVID-19 Identification Using CT Imaging 10.2.4 ASD Identification Using Brain Functional Networks 10.3 Survival Prediction with Histopathological Image 10.3.1 Ranking-Based Survival Prediction 10.3.2 Phenotypic and Topological Hypergraph Modeling 10.4 Drug Discovery 10.5 Medical Image Segmentation 10.6 Summary References 11 Hypergraph Computation for Computer Vision 11.1 Introduction 11.2 Visual Classification 11.3 3D Object Retrieval 11.4 Tag-Based Social Image Retrieval 11.5 Summary References 12 The DeepHypergraph Library 12.1 Introduction 12.2 The Correlation Structures in DHG 12.3 The Function Library in DHG 12.4 Summary References 13 Conclusions and Future Work 13.1 Summary of This Book 13.2 Future Work