Flow Smoothing and Denoising: Graph Signal Processing in the Edge-Space
arXiv:1808.02111 · doi:10.1109/GlobalSIP.2018.8646701
Abstract
This paper focuses on devising graph signal processing tools for the treatment of data defined on the edges of a graph. We first show that conventional tools from graph signal processing may not be suitable for the analysis of such signals. More specifically, we discuss how the underlying notion of a `smooth signal' inherited from (the typically considered variants of) the graph Laplacian are not suitable when dealing with edge signals that encode a notion of flow. To overcome this limitation we introduce a class of filters based on the Edge-Laplacian, a special case of the Hodge-Laplacian for simplicial complexes of order one. We demonstrate how this Edge-Laplacian leads to low-pass filters that enforce (approximate) flow-conservation in the processed signals. Moreover, we show how these new filters can be combined with more classical Laplacian-based processing methods on the line-graph. Finally, we illustrate the developed tools by denoising synthetic traffic flows on the London street network.
arXiv comment5 pages, 2 figure
References in corpus (17)
- The Emerging Field of Signal Processing on Graphs: Extending High-Dimensional Data Analysis to Networks and Other Irregular Domains
- Link communities reveal multiscale complexity in networks
- Discrete Signal Processing on Graphs
- Discrete Signal Processing on Graphs: Sampling Theory
- Line Graphs, Link Partitions and Overlapping Communities
- Simplicial Closure and higher-order link prediction
- Signals on Graphs: Uncertainty Principle and Sampling
- Sampling of graph signals with successive local aggregations
- The Price of Anarchy in Transportation Networks: Efficiency and Optimality Control
- Autoregressive Moving Average Graph Filtering
- Kernel-based Reconstruction of Graph Signals
- Prediction of allosteric sites and mediating interactions through bond-to-bond propensities
- Reconstruction of Graph Signals through Percolation from Seeding Nodes
- A Distributed Tracking Algorithm for Reconstruction of Graph Signals
- Flow-based network analysis of the Caenorhabditis elegans connectome
- Structure of complex networks: Quantifying edge-to-edge relations by failure-induced flow redistribution
- Hodge Laplacians on graphs
Cited by in corpus (21)
- The physics of higher-order interactions in complex systems
- What are higher-order networks?
- Higher-order interactions shape collective dynamics differently in hypergraphs and simplicial complexes
- Topological Signal Processing over Simplicial Complexes
- Signal Processing on Higher-Order Networks: Livin' on the Edge ... and Beyond
- Synchronization induced by directed higher-order interactions
- A User Guide to Low-Pass Graph Signal Processing and its Applications
- Simplicial Convolutional Filters
- Dirac signal processing of higher-order topological signals
- Finite Impulse Response Filters for Simplicial Complexes
- Signal Processing on Cell Complexes
- Turing patterns on discrete topologies: from networks to higher-order structures
- Beyond Low-Pass Filters: Adaptive Feature Propagation on Graphs
- Hodgelets: Localized Spectral Representations of Flows on Simplicial Complexes
- Principled Simplicial Neural Networks for Trajectory Prediction
- Higher-order signal processing with the Dirac operator
- Outlier Detection for Trajectories via Flow-embeddings
- Signal Processing on Product Spaces
- FTF-ER: Feature-Topology Fusion-Based Experience Replay Method for Continual Graph Learning
- Graphs for deep learning representations
- Faster Inference of Cell Complexes from Flows via Matrix Factorization