Discrete Signal Processing on Graphs: Sampling Theory

By Siheng Chen, Rohan Varma, Aliaksei Sandryhaila, Jelena Kovacevic. IEEE Transactions on Signal Processing, 2015

673 citations recorded by the source corpus.

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 Erdös-Ré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 of online blogs and digit images, where we achieve similar or better performance with fewer labeled samples compared to previous work.

Subfields: Artificial Intelligence, Statistical and Nonlinear Physics

View Paper: https://www.semanticscholar.org/paper/fd6432fa2b032dd5f246d26460bf3353c43c257a

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Statistical and Nonlinear Physics

Citations in the corpus

Graph Signal Processing: Overview, Challenges, and Applications (2017, methodology): “An alternative approach proposed in [104], [85] can be applied to circulant graphs, for which the GFT corresponds to the DFT. Recent work [105], [106] has shown that similar filterbank designs can be developed for directed graphs, where these designs are only possible for M -block cyclic graphs, whi”
Compressive Spectral Clustering (2016, background): “There has been recently a surge of interest around adapting classical sampling theorems to such bandlimited graph signals (Anis et al., 2015; Chen et al., 2015; Marques et al., 2015; Tsitsvero et al., 2015).”
Evaluating Large Language Models in Class-Level Code Generation (2024, methodology): “…where five solution code samples are randomly generated for each task with a temperature of 0.2 [21] and default top_p, and (ii) greedy sampling [22], where only one single solution code sample is generated for each task using greedy decoding, i.e., setting the “do_sample” hyper-parameter to…”
Explainability Methods for Graph Convolutional Neural Networks (2019, background): “…meth-ods for CNNs. Graph Convolutional Neural Networks: The mathematical foundation of GCNNs is deeply rooted in the ﬁeld of graph signal processing [3, 4] and spectral graph theory in which signal operations like Fourier transform and convolutions are extended to signals living on graphs.”
Signals on Graphs: Uncertainty Principle and Sampling (2015, background): “Alternative deﬁnitions of GFT have been proposed, see, e.g., [1]–[7], looking at the problem from different perspectives: [1], [5], [6] apply to undirected graphs and build on the spectral clustering properties of the Laplacian eigenvectors and the minimization of the 2 -norm graph total variation;…”
A Comprehensive Survey on Graph Neural Networks (2019, methodology): “Background Spectral-based methods have a solid mathematical foundation in graph signal processing [82], [83], [84].”
Convolutional Neural Network Architectures for Signals Supported on Graphs (2018, background): “Apart from the challenge of selecting sampling matrices for graphs – see (16) and [7], [28]–[30] –, this does not require any further modification to (5).”
Efficient Sampling Set Selection for Bandlimited Graph Signals Using Graph Spectral Proxies (2015, methodology): “Using this condition, we also propose a direct sampling set selection method that finds a set approximately maximizing this bound so that a larger space of graph signals can be uniquely reconstructed.”
Network Topology Inference from Spectral Templates (2016, neutral): “, V is found as the eigenbasis ofCx where x is bandlimited in the graph Fourier domain [43].”
Graph Learning: A Survey (2021, background): “An optimal operator with a guarantee for perfect recovery was proposed in [35], and it is robust to noise for general graphs.”