Hypergraph neural networks: from signal processing to convolution, u-nets and beyond
Date
2024
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
University of Delaware
Abstract
Network data has gained significant attention in signal processing and machine learning communities. Existing research mainly centers on simple graphs, which depict only pairwise connections. This limitation becomes apparent in many real-world scenarios, such as social networks where interactions often involve multiple individuals, or in recommender systems where decisions are influenced by groups of interrelated purchase histories. In response to this limitation, we turn our focus to a more advanced and general data abstraction: the hypergraph. In a hypergraph, each hyperedge can simultaneously bind multiple nodes, offering a richer representation of relationships. Building on the foundational principles of hypergraph signal processing (HGSP), we develop a series of hypergraph neural networks (HyperGNNs) ranging from convolution to u-nets and beyond, which are applicable to node-level, hyperlink-level, and hypergraph-level tasks. ☐ The first study embraces recent advances in tensor-HGSP and proposes a tensor-spectral convolution (T-SpectralConv) hypergraph neural network. The t-spectral convolution is defined under the t-product algebra from the convolution and spectral filtering theorem. Observing the interplay between HGSP and HyperGNNs, we continue to study the connection between a classic hypergraph signal denoising (hyperGSD) problem and T-SpectralConv layers. Interestingly, we theoretically prove that constructing a hypergraph convolution layer is equivalent to performing a one-step gradient descent to solve the HyperGSD problem. Inspired by this intriguing discovery, we propose a multi-step gradient descent rule and further design a tensor-hypergraph iterative network (T-HGIN) based on the multi-step updating scheme. Compared to the original T-SpectralConv neural network, the T-HGIN efficiently propagates information to a larger neighborhood in just one layer, thus achieving better performance with fewer learnable parameters. ☐ To improve computational efficiency for T-SpectralConv operations, we localize the t-spectral convolution approach to formulate the t-spatial convolution and further devise a novel tensor-message-passing (T-MP) algorithm for practical implementation by facilitating compressed adjacency tensor representations. The proposed models leverage hypergraph tensor descriptors that preserve complete higher-order relationships without reducing the hypergraph structure, thus allowing for the full exploitation of hypergraph data. Furthermore, we introduce a cross-node interaction operation to capture polynomial interactions of node features, significantly enhancing the capacity to understand intrinsic higher-order relationships beyond traditional linear aggregation approaches. By leveraging tensor sparsity, the T-MP approach notably reduces both space and time complexities from polynomial to linear relative to the number of nodes. Designed from a node-centric perspective, our model demonstrates strong generalizability to unseen nodes during testing and enables inductive learning. ☐ While convolutions have been successfully developed in non-Euclidean higher-order domains, particularly in hypergraphs, the exploration of u-net architectures in hypergraph data remains sparse due to the lack of well-defined pooling and unpooling operations. The last work in this dissertation pioneers the study of u-net architectures for hypergraph data, addressing the critical challenge of designing effective pooling and unpooling operations that retain maximal structural information from the input hypergraph. Motivated by hierarchical clustering, we propose to construct the pooling and unpooling operators all at once by cutting the clustering dendrogram at different granularities, coined the Parallel Hierarchical Pooling (PH-Pool) and Unpooling (PH-Unpool) operators. Unlike existing pooling methods that risk local structural damage through a sequential learning procedure, our PH-Pool operators are designed in a global and parallel manner to ensure fidelity to the original hypergraph structure with efficient computation. The PH-Unpool operators are tailored to perform inverse operations of the PH-Pools for hypergraph reconstruction, leading to the development of hypergraph u-nets. We validate the proposed hypergraph u-net through hypergraph reconstruction simulation, hypergraph classification, and self-supervised anomaly detection, which demonstrate superior performance over state-of-the-art graph and hypergraph deep learning methods.
Description
Keywords
Network data, Hypergraph signal processing, Hypergraph neural networks, Unpooling operations