Discrete Signal Processing on Graphs: Sampling Theory
arXiv:1503.05432 · doi:10.1109/TSP.2015.2469645
Abstract
We propose a sampling theory for signals that are supported on either directed or undirected graphs. The theory follows the same paradigm as classical sampling theory. We show that perfect recovery is possible for graph signals bandlimited under the graph Fourier transform. The sampled signal coefficients form a new graph signal, whose corresponding graph structure preserves the first-order difference of the original graph signal. For general graphs, an optimal sampling operator based on experimentally designed sampling is proposed to guarantee perfect recovery and robustness to noise; for graphs whose graph Fourier transforms are frames with maximal robustness to erasures as well as for Erdős-Rényi graphs, random sampling leads to perfect recovery with high probability. We further establish the connection to the sampling theory of finite discrete-time signal processing and previous work on signal recovery on graphs. To handle full-band graph signals, we propose a graph filter bank based on sampling theory on graphs. Finally, we apply the proposed sampling theory to semi-supervised classification on online blogs and digit images, where we achieve similar or better performance with fewer labeled samples compared to previous work.
To appear in IEEE T-SP
References in corpus (4)
Cited by in corpus (143)
- A Comprehensive Survey on Graph Neural Networks
- Graph Learning: A Survey
- Kernel Mean Embedding of Distributions: A Review and Beyond
- Learning Decentralized Controllers for Robot Swarms with Graph Neural Networks
- Efficient Sampling Set Selection for Bandlimited Graph Signals Using Graph Spectral Proxies
- Signals on Graphs: Uncertainty Principle and Sampling
- Convolutional Neural Network Architectures for Signals Supported on Graphs
- Sampling of graph signals with successive local aggregations
- Kernel-based Reconstruction of Graph Signals
- Fast Resampling of 3D Point Clouds via Graphs
- Graph Signal Processing: History, Development, Impact, and Outlook
- Signal Processing on Higher-Order Networks: Livin' on the Edge ... and Beyond
- Sampling Signals on Graphs: From Theory to Applications
- Greedy Sampling of Graph Signals
- On the Graph Fourier Transform for Directed Graphs
- Adaptive Least Mean Squares Estimation of Graph Signals
- Adaptive Graph Signal Processing: Algorithms and Optimal Sampling Strategies
- Eigendecomposition-Free Sampling Set Selection for Graph Signals
- Reconstruction of Graph Signals through Percolation from Seeding Nodes
- Subgraph-based filterbanks for graph signals
- Graph Unrolling Networks: Interpretable Neural Networks for Graph Signal Denoising
- Spectral Domain Sampling of Graph Signals
- Introducing Hypergraph Signal Processing: Theoretical Foundation and Practical Applications
- Deep Unsupervised Learning of 3D Point Clouds via Graph Topology Inference and Filtering
- Distributed Adaptive Learning of Graph Signals
- Spectral Projector-Based Graph Fourier Transforms
- Two-Channel Critically-Sampled Graph Filter Banks With Spectral Domain Sampling
- A User Guide to Low-Pass Graph Signal Processing and its Applications
- Reconstruction of Time-varying Graph Signals via Sobolev Smoothness
- A Directed Graph Fourier Transform with Spread Frequency Components
- Fast Graph Sampling Set Selection Using Gershgorin Disc Alignment
- Compressive Spectral Clustering
- Revisiting Over-smoothing in Deep GCNs
- Flow Smoothing and Denoising: Graph Signal Processing in the Edge-Space
- Generalized Sampling on Graphs With Subspace and Smoothness Priors
- Localized Spectral Graph Filter Frames: A Unifying Framework, Survey of Design Considerations, and Numerical Comparison (Extended Cut)
- Graph Fourier Transform: A Stable Approximation
- Low-complexity Graph Sampling with Noise and Signal Reconstruction via Neumann Series
- Graphon Signal Processing
- A Sampling Theory Perspective of Graph-based Semi-supervised Learning
- Vector-Valued Graph Trend Filtering with Non-Convex Penalties
- Finite Impulse Response Filters for Simplicial Complexes
- Bayesian Estimation of Graph Signals
- Graph CNN for Moving Object Detection in Complex Environments from Unseen Videos
- A-Optimal Sampling and Robust Reconstruction for Graph Signals via Truncated Neumann Series
- Signal Representations on Graphs: Tools and Applications
- Graph Signal Sampling Under Stochastic Priors
- Sampling and Reconstruction of Sparse Signals on Circulant Graphs - An Introduction to Graph-FRI
- When Slepian Meets Fiedler: Putting a Focus on the Graph Spectrum
- Controllability of Bandlimited Graph Processes Over Random Time Varying Graphs
- Iterative reconstruction of signals on graph
- Gegenbauer Graph Neural Networks for Time-varying Signal Reconstruction
- Sampling of graph signals via randomized local aggregations
- Graph Signal Processing: Dualizing GSP Sampling in the Vertex and Spectral Domains
- Graph Signal Restoration Using Nested Deep Algorithm Unrolling
- Graph Fourier Transform Based on Norm Variation Minimization
- Graph-signal Reconstruction and Blind Deconvolution for Structured Inputs
- Bias-Variance Tradeoff of Graph Laplacian Regularizer
- Convolutional Learning on Multigraphs
- Distributed Linear Network Operators using Graph Filters
- Shift-enabled graphs: Graphs where shift-invariant filters are representable as polynomials of shift operations
- Graph Sampling for Matrix Completion Using Recurrent Gershgorin Disc Shift
- Graph Signal Processing: Vertex Multiplication
- Two Channel Filter Banks on Arbitrary Graphs with Positive Semi Definite Variation Operators
- Non-Bayesian Estimation Framework for Signal Recovery on Graphs
- Graph Based Imaging for Synthetic Aperture Radar
- Discrete Signal Processing with Set Functions
- Joint Time-Vertex Fractional Fourier Transform
- Localized Fourier Analysis for Graph Signal Processing
- Observing and Tracking Bandlimited Graph Processes
- Graph Signal Processing: Modulation, Convolution, and Sampling
- Graph Vertex Sampling with Arbitrary Graph Signal Hilbert Spaces
- Towards Interpretable Sparse Graph Representation Learning with Laplacian Pooling
- Graph Generative Models for Fast Detector Simulations in High Energy Physics
- Graph Signal Processing -- Part II: Processing and Analyzing Signals on Graphs
- Designing Asymmetric Shift Operators for Decentralized Subspace Projection
- Multiresolution Representations for Piecewise-Smooth Signals on Graphs
- An Underparametrized Deep Decoder Architecture for Graph Signals
- Coding Method for Parallel Iterative Linear Solver
- Sampling Theory of Jointly Bandlimited Time-vertex Graph Signals
- Recovery of Missing Sensor Data by Reconstructing Time-varying Graph Signals
- A Graph Signal Processing View on Functional Brain Imaging
- Detecting Localized Categorical Attributes on Graphs
- Sampling and Inference of Networked Dynamics using Log-Koopman Nonlinear Graph Fourier Transform
- Signal Recovery on Graphs: Fundamental Limits of Sampling Strategies
- Localization, Decomposition, and Dictionary Learning of Piecewise-Constant Signals on Graphs
- Random sampling of bandlimited signals on graphs
- Hilbert Transform, Analytic Signal, and Modulation Analysis for Graph Signal Processing
- Graph Signal Processing: Overview, Challenges and Applications
- Graph Fourier Transform based on Directed Laplacian
- A Markov Variation Approach to Smooth Graph Signal Interpolation
- Task-Based Graph Signal Compression
- Sampling and Recovery of Graph Signals based on Graph Neural Networks
- Modelling Graph Errors: Towards Robust Graph Signal Processing
- Optimal Sampling of Water Distribution Network Dynamics using Graph Fourier Transform
- Graph Cross Networks with Vertex Infomax Pooling
- Fast Path Localization on Graphs via Multiscale Viterbi Decoding
- Signal Processing on Directed Graphs
- A Graph Downsampling Technique Based On Graph Fourier Transform
- An Example-Driven Introduction to Data Analytics on Graphs
- Vertex-Frequency Graph Signal Processing: A review
- Steering Macro-Scale Network Community Structure by Micro-Scale Features
- Folded Graph Signals: Sensing with Unlimited Dynamic Range
- Subset Selection for Matrices with Fixed Blocks
- Blind Community Detection from Low-rank Excitations of a Graph Filter
- State Estimation in Unobservable Power Systems via Graph Signal Processing Tools
- Proactive Doppler Shift Compensation in Vehicular Cyber-Physical Systems
- From Spectrum Wavelet to Vertex Propagation: Graph Convolutional Networks Based on Taylor Approximation
- Guided Signal Reconstruction Theory
- Robust recovery of bandlimited graph signals via randomized dynamical sampling
- Scalable -Channel Critically Sampled Filter Banks for Graph Signals
- Optimal Sampling for Dynamic Complex Networks with Graph-Bandlimited Initialization
- Some adjacency-invariant spaces on products of short cycles
- Active Sampling for Approximately Bandlimited Graph Signals
- Graph Signal Processing over a Probability Space of Shift Operators
- Blind Demixing of Diffused Graph Signals
- On Critical Sampling of Time-Vertex Graph Signals
- Tracking Infection Diffusion in Social Networks: Filtering Algorithms and Threshold Bounds
- Online Distributed Learning over Graphs with Multitask Graph-Filter Models
- Constrained Sampling: Optimum Reconstruction in Subspace with Minimax Regret Constraint
- Bayesian Design of Sampling Set for Bandlimited Graph Signals
- Extreme Learning Machine for Graph Signal Processing
- Neural Network Approximation of Graph Fourier Transforms for Sparse Sampling of Networked Flow Dynamics
- Average Consensus by Graph Filtering: New Approach, Explicit Convergence Rate and Optimal Design
- A Novel Scheme for Support Identification and Iterative Sampling of Bandlimited Graph Signals
- Fast Decentralized Linear Functions Over Edge Fluctuating Graphs
- Pooling in Graph Convolutional Neural Networks
- Sensor selection on graphs via data-driven node sub-sampling in network time series
- Joint Forecasting and Interpolation of Graph Signals Using Deep Learning
- Enhancing Geometric Deep Learning via Graph Filter Deconvolution
- Reconstruction-Cognizant Graph Sampling using Gershgorin Disc Alignment
- Fast sensor placement by enlarging principle submatrix for large-scale linear inverse problems
- Estimating Network Processes via Blind Identification of Multiple Graph Filters
- Distributed interference cancellation in multi-agent scenarios
- Multi-dimensional graph fractional Fourier transform and its application
- Robust Semi-Supervised Graph Classifier Learning with Negative Edge Weights
- Weighted sampling and weighted interpolation on combinatorial graphs
- Polynomial control on stability, inversion and powers of matrices on simple graphs
- Sampling Policy Design for Tracking Time-Varying Graph Signals with Adaptive Budget Allocation
- Untrained Graph Neural Networks for Denoising
- Subgraph Signal Processing
- A low discrepancy sequence on graphs
- Sampling Theory of Bandlimited Continuous-Time Graph Signals