Introducing Hypergraph Signal Processing: Theoretical Foundation and Practical Applications

Abstract

Signal processing over graphs has recently attracted significant attentions for dealing with structured data. Normal graphs, however, only model pairwise relationships between nodes and are not effective in representing and capturing some high-order relationships of data samples, which are common in many applications such as Internet of Things (IoT). In this work, we propose a new framework of hypergraph signal processing (HGSP) based on tensor representation to generalize the traditional graph signal processing (GSP) to tackle high-order interactions. We introduce the core concepts of HGSP and define the hypergraph Fourier space. We then study the spectrum properties of hypergraph Fourier transform and explain its connection to mainstream digital signal processing. We derive the novel hypergraph sampling theory and present the fundamentals of hypergraph filter design based on the tensor framework. We present HGSP-based methods for several signal processing and data analysis applications. Our experimental results demonstrate significant performance improvement using our HGSP framework over some traditional signal processing solutions.

References in corpus (12)

• Discrete Signal Processing on Graphs
• Tensor Decompositions for Signal Processing Applications From Two-way to Multiway Component Analysis
• Mathematical Formulation of Multi-Layer Networks
• Discrete Signal Processing on Graphs: Sampling Theory
• Random hypergraphs and their applications
• The Number of Eigenvalues of a Tensor
• Alignment and integration of complex networks by hypergraph-based spectral clustering
• Hypergraph topological quantities for tagged social networks
• Hypergraph model of social tagging networks
• Spectra of general hypergraphs
• Hypergraph Spectral Clustering in the Weighted Stochastic Block Model
• Context-Aware Hypergraph Construction for Robust Spectral Clustering

Cited by in corpus (10)

• What are higher-order networks?
• Signal Processing on Higher-Order Networks: Livin' on the Edge ... and Beyond
• Hypergraph Spectral Analysis and Processing in 3D Point Cloud
• Finite Impulse Response Filters for Simplicial Complexes
• Causal Fourier Analysis on Directed Acyclic Graphs and Posets
• Towards Multi-agent Reinforcement Learning based Traffic Signal Control through Spatio-temporal Hypergraphs
• An Efficient Hypergraph Approach to Robust Point Cloud Resampling
• Discrete Signal Processing on Meet/Join Lattices
• Point Cloud Resampling Through Hypergraph Signal Processing
• Point Cloud Segmentation based on Hypergraph Spectral Clustering