Discrete Signal Processing on Graphs

Abstract

In social settings, individuals interact through webs of relationships. Each individual is a node in a complex network (or graph) of interdependencies and generates data, lots of data. We label the data by its source, or formally stated, we index the data by the nodes of the graph. The resulting signals (data indexed by the nodes) are far removed from time or image signals indexed by well ordered time samples or pixels. DSP, discrete signal processing, provides a comprehensive, elegant, and efficient methodology to describe, represent, transform, analyze, process, or synthesize these well ordered time or image signals. This paper extends to signals on graphs DSP and its basic tenets, including filters, convolution, z-transform, impulse response, spectral representation, Fourier transform, frequency response, and illustrates DSP on graphs by classifying blogs, linear predicting and compressing data from irregularly located weather stations, or predicting behavior of customers of a mobile service provider.

References in corpus (5)

• Perfect Reconstruction Two-Channel Wavelet Filter-Banks for Graph Structured Data
• A Spectral Graph Uncertainty Principle
• Empirical graph Laplacian approximation of Laplace--Beltrami operators: Large sample results
• Algebraic Signal Processing Theory: Cooley-Tukey Type Algorithms for DCTs and DSTs
• Finding Non-overlapping Clusters for Generalized Inference Over Graphical Models

Cited by in corpus (281)

• A Comprehensive Survey on Graph Neural Networks
• Discrete Signal Processing on Graphs: Sampling Theory
• Random walks and diffusion on networks
• Geometric Deep Learning: Grids, Groups, Graphs, Geodesics, and Gauges
• Graph Learning: A Survey
• Predicting Station-level Hourly Demands in a Large-scale Bike-sharing Network: A Graph Convolutional Neural Network Approach
• Learning graphs from data: A signal representation perspective
• Connecting the Dots: Identifying Network Structure via Graph Signal Processing
• Efficient Sampling Set Selection for Bandlimited Graph Signals Using Graph Spectral Proxies
• Signals on Graphs: Uncertainty Principle and Sampling
• A Comprehensive Survey on Deep Graph Representation Learning
• Fault Location in Power Distribution Systems via Deep Graph Convolutional Networks
• Convolutional Neural Network Architectures for Signals Supported on Graphs
• Signal Recovery on Graphs: Variation Minimization
• Sampling of graph signals with successive local aggregations
• Graph Laplacian Regularization for Image Denoising: Analysis in the Continuous Domain
• Autoregressive Moving Average Graph Filtering
• Dynamic stochastic blockmodels for time-evolving social networks
• Stationary signal processing on graphs
• Stationary Graph Processes and Spectral Estimation
• Topology Adaptive Graph Convolutional Networks
• Graph signal processing for machine learning: A review and new perspectives
• Data-Free Knowledge Distillation for Deep Neural Networks
• Stability Properties of Graph Neural Networks
• HyperGCN: A New Method of Training Graph Convolutional Networks on Hypergraphs
• Graph Frequency Analysis of Brain Signals
• Kernel-based Reconstruction of Graph Signals
• Gated Graph Recurrent Neural Networks
• Fast Resampling of 3D Point Clouds via Graphs
• Signal Processing on Graphs: Causal Modeling of Unstructured Data
• Missing Data Imputation with Adversarially-trained Graph Convolutional Networks
• Graph Signal Processing: History, Development, Impact, and Outlook
• Local-set-based Graph Signal Reconstruction
• Graph-based Spatial-temporal Feature Learning for Neuromorphic Vision Sensing
• Signal Processing on Higher-Order Networks: Livin' on the Edge ... and Beyond
• Sampling Signals on Graphs: From Theory to Applications
• Robust Spatial Filtering with Graph Convolutional Neural Networks
• Greedy Sampling of Graph Signals
• On the Graph Fourier Transform for Directed Graphs
• Forecasting Time Series with VARMA Recursions on Graphs
• Adaptive Least Mean Squares Estimation of Graph Signals
• Adaptive Graph Signal Processing: Algorithms and Optimal Sampling Strategies
• Advances in Distributed Graph Filtering
• Eigendecomposition-Free Sampling Set Selection for Graph Signals
• Reconstruction of Graph Signals through Percolation from Seeding Nodes
• Distributed Autoregressive Moving Average Graph Filters
• Filtering Random Graph Processes Over Random Time-Varying Graphs
• Subgraph-based filterbanks for graph signals
• Graph Unrolling Networks: Interpretable Neural Networks for Graph Signal Denoising
• Blind Identification of Graph Filters
• Grid-Graph Signal Processing (Grid-GSP): A Graph Signal Processing Framework for the Power Grid
• Irregularity-Aware Graph Fourier Transforms
• Spectral Domain Sampling of Graph Signals
• Introducing Hypergraph Signal Processing: Theoretical Foundation and Practical Applications
• Approximate fast graph Fourier transforms via multi-layer sparse approximations
• A Distributed Tracking Algorithm for Reconstruction of Graph Signals
• Distributed Adaptive Learning of Graph Signals
• Graph Signal Processing and Deep Learning: Convolution, Pooling, and Topology
• 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
• Graph Neural Ordinary Differential Equations
• Hierarchical Representation Learning in Graph Neural Networks with Node Decimation Pooling
• A Directed Graph Fourier Transform with Spread Frequency Components
• Invariance-Preserving Localized Activation Functions for Graph Neural Networks
• Compressive Spectral Clustering
• Revisiting Over-smoothing in Deep GCNs
• Flow Smoothing and Denoising: Graph Signal Processing in the Edge-Space
• Learning Graphs with Monotone Topology Properties and Multiple Connected Components
• A Spectral Framework for Anomalous Subgraph Detection
• Graph Fourier Transform: A Stable Approximation
• A Hilbert Space Theory of Generalized Graph Signal Processing
• Graphon Signal Processing
• Model Degradation Hinders Deep Graph Neural Networks
• Noisy multi-label semi-supervised dimensionality reduction
• Simplicial Convolutional Filters
• Fast Graph Fourier Transforms Based on Graph Symmetry and Bipartition
• Network Inference from Consensus Dynamics with Unknown Parameters
• Learning Laplacian Matrix in Smooth Graph Signal Representations
• Phase Transitions in Spectral Community Detection
• Vector-Valued Graph Trend Filtering with Non-Convex Penalties
• Stability of Graph Scattering Transforms
• Adaptive Diffusions for Scalable Learning over Graphs
• Multi-hop Attention Graph Neural Network
• A Novel Image Denoising Algorithm Using Concepts of Quantum Many-Body Theory
• Finite Impulse Response Filters for Simplicial Complexes
• The Complex Hierarchical Topology of EEG Functional Connectivity
• An Iterative Graph Spectral Subtraction Method for Speech Enhancement
• Graphon Filters: Graph Signal Processing in the Limit
• Stochastic Graph Neural Networks
• Generic Reversible Visible Watermarking Via Regularized Graph Fourier Transform Coding
• Causal Fourier Analysis on Directed Acyclic Graphs and Posets
• Graph Signal Processing Meets Blind Source Separation
• Signal Representations on Graphs: Tools and Applications
• Algebraic Neural Networks: Stability to Deformations
• Unifying Graph Convolution and Contrastive Learning in Collaborative Filtering
• When Slepian Meets Fiedler: Putting a Focus on the Graph Spectrum
• Controllability of Bandlimited Graph Processes Over Random Time Varying Graphs
• Digraph Signal Processing with Generalized Boundary Conditions
• The Generalized Fourier Transform: A Unified Framework for the Fourier, Laplace, Mellin and $Z$ Transforms
• Iterative reconstruction of signals on graph
• Joint Inference of Multiple Graphs from Matrix Polynomials
• Graph Signal Processing: Dualizing GSP Sampling in the Vertex and Spectral Domains
• Graph Signal Restoration Using Nested Deep Algorithm Unrolling
• Locating Temporal Functional Dynamics of Visual Short-Term Memory Binding using Graph Modular Dirichlet Energy
• Graph-signal Reconstruction and Blind Deconvolution for Structured Inputs
• Bias-Variance Tradeoff of Graph Laplacian Regularizer
• Graph Fourier Transform Based on ${\ell }_1$ Norm Variation Minimization
• Kernel-based Graph Learning from Smooth Signals: A Functional Viewpoint
• Label Efficient Semi-Supervised Learning via Graph Filtering
• Detecting Central Nodes from Low-rank Excited Graph Signals via Structured Factor Analysis
• Graph Filters and the Z-Laplacian
• Distributed Linear Network Operators using Graph Filters
• Shift-enabled graphs: Graphs where shift-invariant filters are representable as polynomials of shift operations
• SILVar: Single Index Latent Variable Models
• Two Channel Filter Banks on Arbitrary Graphs with Positive Semi Definite Variation Operators
• Robust Graph Filter Identification and Graph Denoising from Signal Observations
• Ergodicity in Stationary Graph Processes: A Weak Law of Large Numbers
• Structural-constrained Methods for the Identification of Unobservable False Data Injection Attacks in Power Systems
• Graph Signal Processing: Vertex Multiplication
• Smooth Adversarial Examples
• Discrete Signal Processing on Meet/Join Lattices
• Analysis of Signals via Non-Maximally Decimated Non-Uniform Filter Banks
• Joint Time-Vertex Fractional Fourier Transform
• Community-Aware Graph Signal Processing
• Graph-Variate Signal Analysis
• Non-Bayesian Estimation Framework for Signal Recovery on Graphs
• Discrete Signal Processing with Set Functions
• Graph Based Imaging for Synthetic Aperture Radar
• Joint Network Topology Inference in the Presence of Hidden Nodes
• 3DTI-Net: Learn Inner Transform Invariant 3D Geometry Features using Dynamic GCN
• Frequency Analysis of Temporal Graph Signals
• Graph Signal Processing: Modulation, Convolution, and Sampling
• Phase Transitions and a Model Order Selection Criterion for Spectral Graph Clustering
• Multi-dimensional Graph Fourier Transform
• Understanding Graph Neural Networks from Graph Signal Denoising Perspectives
• DCT and DST Filtering with Sparse Graph Operators
• Preconditioned Gradient Descent Algorithm for Inverse Filtering on Spatially Distributed Networks
• Graph Signal Processing -- Part II: Processing and Analyzing Signals on Graphs
• Eigendecomposition of Block Tridiagonal Matrices
• Joint Network Topology Inference via a Shared Graphon Model
• A noncommutative approach to the graphon Fourier transform
• Designing Asymmetric Shift Operators for Decentralized Subspace Projection
• Graph Signal Processing -- Part I: Graphs, Graph Spectra, and Spectral Clustering
• Tensor graph convolutional neural network
• Multiresolution Representations for Piecewise-Smooth Signals on Graphs
• Signal processing on graphs: Transforms and tomograms
• M-Channel Critically Sampled Spectral Graph Filter Banks With Symmetric Structure
• Graph Signal Processing for Geometric Data and Beyond: Theory and Applications
• A Review of Graph-Powered Data Quality Applications for IoT Monitoring Sensor Networks
• Sampling Theory of Jointly Bandlimited Time-vertex Graph Signals
• Localization bounds for the graph translation
• Graph-Based Object Classification for Neuromorphic Vision Sensing
• A Graph Signal Processing View on Functional Brain Imaging
• Wide-Sense Stationarity in Generalized Graph Signal Processing
• Input State Stability of Gated Graph Neural Networks
• Detecting Localized Categorical Attributes on Graphs
• Spatially Distributed Sampling and Reconstruction
• Functional Alignment with Anatomical Networks is Associated with Cognitive Flexibility
• Graph and graphon neural network stability
• Localization, Decomposition, and Dictionary Learning of Piecewise-Constant Signals on Graphs
• On the Shift Operator, Graph Frequency and Optimal Filtering in Graph Signal Processing
• Polynomial graph filter of multiple shifts and distributed implementation of inverse filtering
• Signal Recovery on Graphs: Fundamental Limits of Sampling Strategies
• Signal Processing on Product Spaces
• Signal processing on simplicial complexes
• Hilbert Transform, Analytic Signal, and Modulation Analysis for Graph Signal Processing
• Fast Spectral Ranking for Similarity Search
• A Markov Variation Approach to Smooth Graph Signal Interpolation
• Understanding Concepts in Graph Signal Processing for Neurophysiological Signal Analysis
• Learning Product Graphs Underlying Smooth Graph Signals
• Closed Form Solutions of Combinatorial Graph Laplacian Estimation under Acyclic Topology Constraints
• Graph Fourier Transform based on Directed Laplacian
• Infection Analysis on Irregular Networks through Graph Signal Processing
• Graph Signal Processing: Overview, Challenges and Applications
• Unitary Shift Operators on a Graph
• Sampling and Recovery of Graph Signals based on Graph Neural Networks
• Task-Based Graph Signal Compression
• Local Measurement and Reconstruction for Noisy Graph Signals
• Blind Identification of Invertible Graph Filters with Multiple Sparse Inputs
• Gaussian Kernel Variance For an Adaptive Learning Method on Signals Over Graphs
• Modeling Spread of Preferences in Social Networks for Sampling-based Preference Aggregation
• Graph Neural Lasso for Dynamic Network Regression
• Modelling Graph Errors: Towards Robust Graph Signal Processing
• Agile Inexact Methods for Spectral Projector-Based Graph Fourier Transforms
• GraphTER: Unsupervised Learning of Graph Transformation Equivariant Representations via Auto-Encoding Node-wise Transformations
• Hop-Hop Relation-aware Graph Neural Networks
• Structural transition in interdependent networks with regular interconnections
• Recovering the Graph Underlying Networked Dynamical Systems under Partial Observability: A Deep Learning Approach
• Graph Convolutional Neural Networks Sensitivity under Probabilistic Error Model
• Signal Processing on Directed Graphs
• VGAI: End-to-End Learning of Vision-Based Decentralized Controllers for Robot Swarms
• Perceptually inspired weighted MSE optimization using irregularity-aware graph Fourier transform
• Continuous-Depth Neural Models for Dynamic Graph Prediction
• Dynamic Polygon Clouds: Representation and Compression for VR/AR
• On the Supermodularity of Active Graph-based Semi-supervised Learning with Stieltjes Matrix Regularization
• Decentralized Eigendecomposition for Online Learning over Graphs with Applications
• Optimized Quantization in Distributed Graph Signal Filtering
• From Spectrum Wavelet to Vertex Propagation: Graph Convolutional Networks Based on Taylor Approximation
• Improving J-divergence of brain connectivity states by graph Laplacian denoising
• Vertex-Frequency Graph Signal Processing: A review
• State Estimation in Unobservable Power Systems via Graph Signal Processing Tools
• 3D Dynamic Point Cloud Inpainting via Temporal Consistency on Graphs
• Folded Graph Signals: Sensing with Unlimited Dynamic Range
• Online Inference for Mixture Model of Streaming Graph Signals with Non-White Excitation
• Blind Community Detection from Low-rank Excitations of a Graph Filter
• Topology and Prediction Focused Research on Graph Convolutional Neural Networks
• Topological Signal Processing on Quantum Computers for Higher-Order Network Analysis
• Polynomial Selection in Spectral Graph Neural Networks: An Error-Sum of Function Slices Approach
• Haar-Laplacian for directed graphs
• Scalable Perception-Action-Communication Loops with Convolutional and Graph Neural Networks
• A unified framework for manifold landmarking
• Stability of Graph Convolutional Neural Networks to Stochastic Perturbations
• A Time-Vertex Signal Processing Framework
• SoGCN: Second-Order Graph Convolutional Networks
• Graph Blind Deconvolution with Sparseness Constraint
• A Multiscale Graph Convolutional Network for Change Detection in Homogeneous and Heterogeneous Remote Sensing Images
• An Example-Driven Introduction to Data Analytics on Graphs
• What's in a frequency: new tools for graph Fourier Transform visualization
• Nonsubsampled Graph Filter Banks and Distributed Implementation
• A Graph Downsampling Technique Based On Graph Fourier Transform
• Graph Equivalence Classes for Spectral Projector-Based Graph Fourier Transforms
• GFCN: A New Graph Convolutional Network Based on Parallel Flows
• Graph Signal Processing over a Probability Space of Shift Operators
• Graph Neural Networks for Distributed Linear-Quadratic Control
• Inferring Graph Signal Translations as Invariant Transformations for Classification Tasks
• Guided Graph Spectral Embedding: Application to the C. elegans Connectome
• Learning Parametrised Graph Shift Operators
• Phase Transitions in Spectral Community Detection of Large Noisy Networks
• Some adjacency-invariant spaces on products of short cycles
• Online Distributed Learning over Graphs with Multitask Graph-Filter Models
• Blind Demixing of Diffused Graph Signals
• Design of Sampling Set for Bandlimited Graph Signal Estimation
• Detecting Anomalous Activity on Networks with the Graph Fourier Scan Statistic
• Distributed Network Privacy using Error Correcting Codes
• Extreme Learning Machine for Graph Signal Processing
• Space-Time Graph Neural Networks
• Tracking Time-Vertex Propagation using Dynamic Graph Wavelets
• Graph Signal Processing of Indefinite and Complex Graphs using Directed Variation
• Identifying First-order Lowpass Graph Signals using Perron Frobenius Theorem
• Diffusion and Superposition Distances for Signals Supported on Networks
• Orthogonal Transforms for Signals on Directed Graphs
• Topology Inference for Network Systems with Unknown Inputs
• From Nodes to Edges: Edge-Based Laplacians for Brain Signal Processing
• Wide and Deep Graph Neural Networks with Distributed Online Learning
• Polynomial control on stability, inversion and powers of matrices on simple graphs
• Graph-based Matched Field Localization for an Underwater Source
• Subgraph Signal Processing
• Accelerated Spectral Clustering Using Graph Filtering Of Random Signals
• Asymptotic Justification of Bandlimited Interpolation of Graph signals for Semi-Supervised Learning
• Partition-wise Graph Filtering: A Unified Perspective Through the Lens of Graph Coarsening
• Translation Operator in Graph Signal Processing: A Generalized Approach
• Learning Sparse Graphs for Prediction and Filtering of Multivariate Data Processes
• Signed Graph Learning with Hidden Nodes
• Learning flexible representations of stochastic processes on graphs
• Implementing distributed graph filters by elementary matrix decomposition
• Simple Graph Convolutional Networks
• How likely is a random graph shift-enabled?
• Single Index Latent Variable Models for Network Topology Inference
• Sampling Theory of Bandlimited Continuous-Time Graph Signals
• A Novel Scheme for Support Identification and Iterative Sampling of Bandlimited Graph Signals
• Average Consensus by Graph Filtering: New Approach, Explicit Convergence Rate and Optimal Design
• Signal processing with a distribution of graph operators
• EEG-based video identification using graph signal modeling and graph convolutional neural network
• Enhancing Geometric Deep Learning via Graph Filter Deconvolution
• Robust Semi-Supervised Graph Classifier Learning with Negative Edge Weights
• Constructing Frequency Domains on Graphs in Near-Linear Time
• Pooling in Graph Convolutional Neural Networks
• Predicting Station-Level Bike-Sharing Demands Using Graph Convolutional Neural Network
• FFT and orthogonal discrete transform on weight lattices of semi-simple Lie groups
• Joint Forecasting and Interpolation of Graph Signals Using Deep Learning
• Estimating Network Processes via Blind Identification of Multiple Graph Filters
• SStaGCN: Simplified stacking based graph convolutional networks
• Learning to Learn Graph Topologies
• Estimating Centrality Blindly from Low-pass Filtered Graph Signals
• Graph Wavelets via Sparse Cuts: Extended Version
• Untrained Graph Neural Networks for Denoising
• Stationarity of Time-Series on Graph via Bivariate Translation Invariance
• Offline detection of change-points in the mean for stationary graph signals
• Brain Maturation Study during Adolescence Using Graph Laplacian Learning Based Fourier Transform