Source-linked AI summary
Discrete Signal Processing on Graphs: Sampling Theory
Siheng Chen, Rohan Varma, Aliaksei Sandryhaila, Jelena Kovačević
TL;DR
Graph sampling on irregular directed or undirected graphs lacks a general recovery framework and an associated sampled-graph structure. The paper develops a classical-sampling-based theory with designed and random sampling operators, then applies it to classification. It establishes perfect recovery for bandlimited signals and reports competitive classification with fewer labeled samples.
Problem
Graph-sampling methods do not adequately address directed graphs or explain which graph structure supports sampled coefficients.
Method
The paper develops a DSPG sampling theory using graph Fourier bandlimiting, sampling-operator design, sampled-graph construction, and graph filter banks for full-band signals.
Results
Perfect recovery is possible for bandlimited graph signals, while applications to online blogs and digit images achieve similar or better performance with fewer labeled samples than previous work.
Takeaways & Limitations
The framework connects graph sampling with classical finite discrete-time sampling and supports semi-supervised classification on irregular graph-structured data.
Abstract
from arXiv · showhide
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.
I. INTRODUCTION
The paper develops a DSPG sampling theory for directed and undirected graph signals, addressing recovery and graph-structure questions on irregular domains. It connects graph sampling to classical sampling theory and applies the framework to semi-supervised classification.
- Graph signal processing extends classical signal processing to complex, irregular structures represented by graphs.
- DSPG uses a graph shift operator based on the adjacency matrix, supporting directed or undirected graphs with real or complex edge weights.
- Previous graph-sampling approaches are difficult to apply to directed graphs and do not specify the graph structure supporting sampled coefficients.
- The proposed framework samples signals on directed or undirected graphs and enables perfect recovery for graph signals bandlimited under the graph Fourier transform.
- Sampled coefficients form a new graph signal whose graph structure is constructed from the original structure while preserving first-order differences.
- The paper introduces linear-algebraic sampling tools and sampling-operator design, including experimentally designed sampling for graph signals.
III. SAMPLING ON GRAPHS
The paper defines graph sampling and interpolation through linear operators, with bandwidth determined by the number of nonzero graph-Fourier coefficients. Qualified sampling operators enable perfect recovery of bandlimited graph signals when enough linearly independent samples are selected.
- B. Sampling Theory for Graph Signals: Bandwidth is the number of nonzero graph-Fourier coefficients, rather than the numerical values of graph frequencies.This definition supports linear-algebraic sampling tools on complex, irregular graphs and differs from prior frequency-cutoff definitions.
- A. Sampling & Interpolation: Graph sampling maps x ∈ C^N to sampled coefficients x_M ∈ C^M, while interpolation maps x_M back to x′ ∈ C^N.Random sampling selects indices independently; experimentally designed sampling selects them beforehand, with random sampling as a subset of the latter.
- B. Sampling Theory for Graph Signals: A bandlimited graph signal has graph-Fourier coefficients bx_k = 0 for all k ≥ K, with K as its smallest such bandwidth.Bandlimited signals need not be low-pass or smooth because frequency ordering can be permuted.
- B. Sampling Theory for Graph Signals: Perfect recovery of every signal in BL_K(V^-1) requires at least K samples and an invertible sampling matrix ΨV(K).When M = K, the interpolation matrix is the inverse of ΨV(K); redundant samples can reduce noise influence.
C. Sampled Graph Signal
The sampled coefficients of a bandlimited graph signal form a new graph signal. Its graph shift is constructed from sampled eigenvectors and eigenvalues of the original graph, preserving corresponding Fourier-domain content.
- C. Sampled Graph Signal: For bandlimited x and qualified sampling Ψ, sampled coefficients x_M and the first K Fourier coefficients form a Fourier pair.The sampled coefficients reconstruct the retained spectrum through U^-1, while U recovers that spectrum from x_M.
- C. Sampled Graph Signal: The sampled graph shift A_M is constructed by sampling rows of the original eigenvector matrix and the first K eigenvalues.This construction preserves selected information in the original graph’s graph-Fourier domain.
- C. Sampled Graph Signal: The original and sampled signals have equivalent Fourier content after their corresponding graph Fourier transforms when x has bandwidth K.The first K coefficients are retained and the remaining N − K coefficients are zero.
D. Property of A Sampled Graph Signal
The sampled graph shift preserves the first-order difference of the original signal at sampled indices, even though sampling loses connectivity information. A numerical directed-graph example illustrates this preservation.
- D. Property of A Sampled Graph Signal: A_M preserves the first-order difference of x at sampled indices, despite losing connectivity between sampled and unsampled nodes.The graph total variation ||x − A x||_p measures signal smoothness, while Ψ(x − A x) measures the sampled first-order difference.
- D. Property of A Sampled Graph Signal: In the five-node directed-graph example, the sampled first-order difference is Ψ(x − A x) = [0.05, 0.07, −0.13]^T.The example uses a bandlimited signal and constructs its sampled graph shift from selected graph-Fourier quantities.
- D. Property of A Sampled Graph Signal: The sampled shift A_M can contain self-loops and negative weights while remaining related to A through sampled Fourier information.The example reports that A_M preserves part of A’s frequency content and validates the first-order-difference property.
- D. Property of A Sampled Graph Signal: The example verifies the theorem numerically by comparing the sampled graph shift’s first-order difference with the sampled original difference.The cited construction includes the sampled frequencies, sampled shift, signal, and corresponding difference calculation.
IV. SAMPLING WITH A QUALIFIED SAMPLING OPERATOR
Qualified sampling selects linearly independent rows of the graph-Fourier basis to guarantee recovery, while optimal experimental design minimizes noise amplification. Redundant samples improve robustness, and random sampling can succeed with high probability for specific graph classes.
- IV. Sampling with a Qualified Sampling Operator: A qualified sampling operator selects K linearly independent rows of V(K), enabling perfect recovery for bandlimited signals.Because V(K) has rank K, at least one such row set exists when the graph shift is known.
- IV. Sampling with a Qualified Sampling Operator: For general graphs, optimal sampling minimizes noise amplification by maximizing the smallest singular value of ΨV(K).The exact optimization is non-deterministic polynomial-time hard, so the paper uses a greedy algorithm.
- IV. Sampling with a Qualified Sampling Operator: Random sampling leads to perfect recovery with high probability for some specific graph classes.The paper contrasts this result with experimentally designed sampling for general graphs.
- IV. Sampling with a Qualified Sampling Operator: Increasing the number of samples grows the smallest singular value of ΨV(K), making redundant sampling more robust to noise.The noise model introduces sampling error before interpolation, and the design criterion bounds its amplification.
2) Simulations:
A 150-station weather-network signal with bandwidth 3 is recovered using two sampling operators, but only the optimally designed operator remains robust under noise.
- Setup: The experiment models 150 U.S. weather stations, connecting stations whose geodesic distance is below 500 miles.The graph shift assigns an edge when the interstation geodesic distance satisfies the threshold.
- Sampling operators: A graph signal with bandwidth 3 is tested using an arbitrary qualified operator and an optimal sampling operator.Both operators perfectly recover the signal from 3 samples without added noise.
- Recovery: 3 samples suffice for perfect recovery with both sampling operators before noise is added.Gaussian noise with mean zero and variance 0.01 is then added to each sample.
- Noise robustness: The arbitrary qualified operator fails under noise, whereas the optimal operator approximately recovers the original graph signal.The comparison is shown in Figure 4(f) and (h).
B. Random Sampling
Random sampling is guaranteed for graph Fourier transforms with maximal erasure robustness and succeeds with high probability for Erdős-Rényi graphs under stated conditions.
- Frames with maximal robustness to erasures: A maximally erasure-robust graph Fourier frame has every K × K submatrix invertible, so sampling at least K coefficients guarantees perfect recovery.The inverse graph Fourier transform must have this maximal robustness property.
- Frames with maximal robustness to erasures: For circulant graphs, any M ≥ K sampled coefficients perfectly recover a bandwidth-K graph signal.The graph Fourier transform is the discrete Fourier transform, a polynomial transform matrix that is maximally robust to erasures.
- Erdős-Rényi graphs: For Erdős-Rényi graphs, random sampling of a sufficient number of coefficients achieves perfect recovery with high probability.This follows because the sampled Fourier submatrix has full rank with high probability.
- Erdős-Rényi graphs: With probability 1−δ, the sampled Fourier submatrix is a frame with lower bound M/2 and upper bound 3M/2.The result applies under the Erdős-Rényi conditions specified in Lemma 1.
3) Simulations:
Simulations show that random sampling success on Erdős-Rényi graphs rises with connection probability and graph size, while the theory also recovers bandlimited discrete-time signals and constructs smaller graph shifts.
- Simulations: The success-rate experiment varies graph sizes from 50 to 500, connection probabilities from 0 to 0.5, and averages 100 random graphs per setting.Each graph signal has fixed bandwidth K = 10, and 10 rows are sampled from the first 10 Fourier columns.
- Simulations: Success rates increase with connection probability and graph size, approaching 100% when Erdős-Rényi graphs have sufficient connections.Figure 5 reports averages over 100 random tests for sizes 50 and 500.
- Relation to finite discrete-time sampling: For finite discrete-time signals, sampling at least the bandwidth, M ≥ K, guarantees perfect recovery of every bandlimited signal.This recovers the classical discrete-time sampling result within the graph-sampling framework.
- Relation to finite discrete-time sampling: An appropriate frequency ordering and sampling mechanism transforms a larger finite discrete-time graph into a smaller graph with the cyclic permutation shift.Different orderings or sampling operators can produce different, potentially non-intuitive graph shifts.
- Relation to finite discrete-time sampling: The construction yields an N/2 × N/2 cyclic permutation matrix and remains consistent with finite discrete-time signal sampling.The sampled graph Fourier transform is the discrete Fourier transform of size N/2.
B. Relation to Compressed Sensing
The paper distinguishes graph sampling from compressed sensing by whether the signal’s nonzero frequency locations are known.
- Compressed sensing: Compressed sensing recovers sparse signals from relatively few measurements using a sampling operator and an optimization problem.The standard formulation assumes M ≪ N.
- Compressed sensing: Because the l0 optimization is nonconvex and computationally hard, l1-based basis pursuit methods provide efficient approximate recovery.Basis pursuit with denoising is also described for noisy measurements.
- Compressed sensing: Dictionary-based compressed sensing can recover general signals when a dictionary makes their representation sparse.For graph signals, the appropriate graph Fourier transform makes limited-bandwidth signals sparse in frequency.
- Relation to the proposed sampling theory: The proposed sampling theory assumes known nonzero frequencies that can be reordered into a bandlimited signal, whereas compressed sensing handles unknown frequency locations.Unknown support makes compressed sensing a more general and harder problem.
C. Relation to Signal Recovery on Graphs
The paper distinguishes sampling theory on graphs from broader signal recovery and extends its framework to graph filter banks for full-band signals. Filter banks split signals into bandlimited channels, process each channel separately, and recombine them.
- Sampling theory targets exact recovery of bandlimited graph signals from incomplete samples, whereas signal recovery often targets smooth signals with noisy, missing, or corrupted observations.
- Graph Filter Banks: Full-band graph signals are decomposed into two bandlimited components, which are sampled and interpolated in separate channels before recombination.
- Graph Filter Banks: Graph filter banks can use channels of unequal sizes and generalize to multiple channels, enabling processing with smaller graphs focused on selected frequency bands.
- Graph Filter Banks: In the weather-station example, a high-frequency channel detects a weather change in one case but not in another.
- Graph Filter Banks: Fixed graph structures and decomposed channels allow sampling and interpolation operators to be designed in advance for inspecting sampled coefficients.
VI. APPLICATIONS
The applications evaluate random and optimal sampling for semi-supervised classification on online blogs. Optimal sampling is reported to outperform random sampling, while random sampling achieves high-probability recovery at lower bandwidths.
- Sampling Online Blogs: The online-blog experiment represents 1,224 political blogs as nodes in a directed hyperlink graph with conservative labels +1 and liberal labels −1.
- Sampling Online Blogs: Random sampling success exceeds 90% for bandwidths no greater than 20, but decreases as bandwidth increases.
- Sampling Online Blogs: The recovery procedure exactly recovers bandlimited labeling signals and approximates low-frequency content when the labeling signal is not bandlimited.
- Sampling Online Blogs: The optimal sampling operator significantly outperforms random sampling because random operators are not always qualified for the interpolation procedure.
- Graph Filter Banks: The graph filter-bank analysis uses low- and high-frequency channels to inspect temperature-signal patterns across weather stations.
- Sampling Online Blogs: 94.44% classification accuracy is achieved by sampling two blogs with the optimal sampling operator.
2) Classification for Handwritten Digits:
The digit-classification application builds directed nearest-neighbor graphs for MNIST and USPS images and queries a small set of optimally selected labels. The proposed method reaches about 90% accuracy with 0.5% of images and 91.69% on USPS with 100 samples.
- MNIST uses 10,000 selected images normalized to 784 pixels, while USPS uses all images normalized to 256 pixels.
- Each dataset is represented by a 12-nearest-neighbor graph based on Euclidean image similarity, yielding an asymmetric directed graph.
- The method queries labels through an optimal sampling operator, estimates low-frequency class content with logistic regression, and assigns each image its highest-confidence class.
- The optimal sampling operator selects representative images from clusters corresponding to the ten digit classes.
- Around 90% classification accuracy is achieved on both MNIST and USPS by querying only 0.5% of images.