Signal Processing on Higher-Order Networks: Livin' on the Edge ... and Beyond

Abstract

In this tutorial, we provide a didactic treatment of the emerging topic of signal processing on higher-order networks. Drawing analogies from discrete and graph signal processing, we introduce the building blocks for processing data on simplicial complexes and hypergraphs, two common higher-order network abstractions that can incorporate polyadic relationships. We provide brief introductions to simplicial complexes and hypergraphs, with a special emphasis on the concepts needed for the processing of signals supported on these structures. Specifically, we discuss Fourier analysis, signal denoising, signal interpolation, node embeddings, and nonlinear processing through neural networks, using these two higher-order network models. In the context of simplicial complexes, we specifically focus on signal processing using the Hodge Laplacian matrix, a multi-relational operator that leverages the special structure of simplicial complexes and generalizes desirable properties of the Laplacian matrix in graph signal processing. For hypergraphs, we present both matrix and tensor representations, and discuss the trade-offs in adopting one or the other. We also highlight limitations and potential research avenues, both to inform practitioners and to motivate the contribution of new researchers to the area.

arXiv comment41 pages; 8 figures

References in corpus (51)

• The Emerging Field of Signal Processing on Graphs: Extending High-Dimensional Data Analysis to Networks and Other Irregular Domains
• Inductive Representation Learning on Large Graphs
• Geometric deep learning: going beyond Euclidean data
• Tensor Decomposition for Signal Processing and Machine Learning
• Discrete Signal Processing on Graphs
• Tensor Decompositions for Signal Processing Applications From Two-way to Multiway Component Analysis
• Variational Graph Auto-Encoders
• Discrete Signal Processing on Graphs: Sampling Theory
• Simplicial Closure and higher-order link prediction
• Connecting the Dots: Identifying Network Structure via Graph Signal Processing
• Efficient Sampling Set Selection for Bandlimited Graph Signals Using Graph Spectral Proxies
• Convolutional Neural Network Architectures for Signals Supported on Graphs
• Sampling of graph signals with successive local aggregations
• Autoregressive Moving Average Graph Filtering
• Topological Signal Processing over Simplicial Complexes
• Random Walks on Simplicial Complexes and the normalized Hodge 1-Laplacian
• Stability Properties of Graph Neural Networks
• HyperGCN: A New Method of Training Graph Convolutional Networks on Hypergraphs
• Multi-body Interactions and Non-Linear Consensus Dynamics on Networked Systems
• Alignment and integration of complex networks by hypergraph-based spectral clustering
• Tensor Spectral Clustering for Partitioning Higher-order Network Structures
• Reconstruction of Graph Signals through Percolation from Seeding Nodes
• Kernel-Based Structural Equation Models for Topology Identification of Directed Networks
• Spectra of general hypergraphs
• Efficient Minimization of Decomposable Submodular Functions
• Blind Identification of Graph Filters
• Inhomogeneous Hypergraph Clustering with Applications
• Introducing Hypergraph Signal Processing: Theoretical Foundation and Practical Applications
• Structural Deep Embedding for Hyper-Networks
• The Total Variation on Hypergraphs - Learning on Hypergraphs Revisited
• Graph-based Semi-Supervised & Active Learning for Edge Flows
• Numerical Optimization for Symmetric Tensor Decomposition
• Submodular Hypergraphs: p-Laplacians, Cheeger Inequalities and Spectral Clustering
• Simplicial Neural Networks
• Flow Smoothing and Denoising: Graph Signal Processing in the Edge-Space
• Weisfeiler and Lehman Go Topological: Message Passing Simplicial Networks
• Finite Impulse Response Filters for Simplicial Complexes
• Uniform Hypergraph Partitioning: Provable Tensor Methods and Sampling Techniques
• Random Walks on Hypergraphs with Edge-Dependent Vertex Weights
• Line Hypergraph Convolution Network: Applying Graph Convolution for Hypergraphs
• Decomposable Submodular Function Minimization: Discrete and Continuous
• Adjacency and Tensor Representation in General Hypergraphs Part 1: e-adjacency Tensor Uniformisation Using Homogeneous Polynomials
• Random Coordinate Descent Methods for Minimizing Decomposable Submodular Functions
• A Notion of Harmonic Clustering in Simplicial Complexes
• Opinion Dynamics with Multi-Body Interactions
• Polynomial-Time Algorithms for Submodular Laplacian Systems
• HyperSAGE: Generalizing Inductive Representation Learning on Hypergraphs
• Revisiting Decomposable Submodular Function Minimization with Incidence Relations
• Powerset Convolutional Neural Networks
• Hypergraph Random Walks, Laplacians, and Clustering
• Co-clustering Vertices and Hyperedges via Spectral Hypergraph Partitioning

Cited by in corpus (38)

• What are higher-order networks?
• Graph Signal Processing: History, Development, Impact, and Outlook
• Weighted simplicial complexes and their representation power of higher-order network data and topology
• Global topological synchronization on simplicial and cell complexes
• Simplicial Convolutional Filters
• Finite Impulse Response Filters for Simplicial Complexes
• Dirac signal processing of higher-order topological signals
• Signal Processing on Cell Complexes
• Dirac synchronization is rhythmic and explosive
• Turing patterns on discrete topologies: from networks to higher-order structures
• Diffusion-driven instability of topological signals coupled by the Dirac operator
• Local Dirac Synchronization on Networks
• Topology and dynamics of higher-order multiplex networks
• Higher-Order Networks Representation and Learning: A Survey
• Global topological synchronization of weighted simplicial complexes
• Hodgelets: Localized Spectral Representations of Flows on Simplicial Complexes
• Higher-order Connection Laplacians for Directed Simplicial Complexes
• Zoo Guide to Network Embedding
• Higher-order signal processing with the Dirac operator
• Geometric Scattering on Measure Spaces
• Outlier Detection for Trajectories via Flow-embeddings
• Measuring dynamical systems on directed hyper-graphs
• Signal Processing on Product Spaces
• Global Topological Dirac Synchronization
• Disentangling the Spectral Properties of the Hodge Laplacian: Not All Small Eigenvalues Are Equal
• Dirac-Equation Signal Processing: Physics Boosts Topological Machine Learning
• Topological Signal Processing on Quantum Computers for Higher-Order Network Analysis
• Combinatorial Complexes: Bridging the Gap Between Cell Complexes and Hypergraphs
• Topological Neural Networks over the Air
• Data-Centric AI Requires Rethinking Data Notion
• From Nodes to Edges: Edge-Based Laplacians for Brain Signal Processing
• Time delay embeddings to characterize the timbre of musical instruments using Topological Data Analysis: a study on synthetic and real data
• Designing topological cluster synchronization patterns with the Dirac operator
• Faster Inference of Cell Complexes from Flows via Matrix Factorization
• Untrained Graph Neural Networks for Denoising
• Quantum HodgeRank: Topology-Based Rank Aggregation on Quantum Computers
• Topological Trajectory Classification and Landmark Inference on Simplicial Complexes
• Multiscale methods for signal selection in single-cell data