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.

41 pages; 8 figures

References in corpus (15)

• Discrete Signal Processing on Graphs
• Variational Graph Auto-Encoders
• Alignment and integration of complex networks by hypergraph-based spectral clustering
• Inhomogeneous Hypergraph Clustering with Applications
• Structural Deep Embedding for Hyper-Networks
• Graph-based Semi-Supervised & Active Learning for Edge Flows
• Simplicial Neural Networks
• Weisfeiler and Lehman Go Topological: Message Passing Simplicial Networks
• Finite Impulse Response Filters for Simplicial Complexes
• 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
• Random Coordinate Descent Methods for Minimizing Decomposable Submodular Functions
• HyperSAGE: Generalizing Inductive Representation Learning on Hypergraphs
• 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