Abstract
This paper builds theoretical foundations for the recovery of a newly proposed class of smooth graph signals, approximately bandlimited graph signals, under three sampling strategies: uniform sampling, experimentally designed sampling and active sampling. We then state minimax lower bounds on the maximum risk for the approximately bandlimited class under these three sampling strategies and show that active sampling cannot fundamentally outperform experimentally designed sampling. We propose a recovery strategy to compare uniform sampling with experimentally designed sampling. As the proposed recovery strategy lends itself well to statistical analysis, we derive the exact mean square error for each sampling strategy. To study convergence rates, we introduce two types of graphs and find that (1) the proposed recovery strategy achieves the optimal rates; and (2) the experimentally designed sampling fundamentally outperforms uniform sampling for Type-2 class of graphs. To validate our proposed recovery strategy, we test it on five specific graphs: a ring graph with $k$ nearest neighbors, an Erd\H{o}s-R'enyi graph, a random geometric graph, a small-world graph and a power-law graph and find that experimental results match the proposed theory well. This work also presents a comprehensive explanation for when and why sampling for semi-supervised learning with graphs works.
Introduction
In Graph Signal Processing (GSP), a central challenge is the reconstruction of a full signal—such as temperatures across a sensor network or labels in a social network—from a limited set of samples. Traditional GSP theory has largely relied on the assumption that signals are strictly bandlimited, meaning they possess zero energy beyond a certain frequency threshold in the graph Fourier domain. However, real-world data often exhibits a "tail" of high-frequency components due to noise or fine-grained local variations. This paper addresses this gap by introducing a more realistic "approximately bandlimited" (ABL) framework and establishing the fundamental limits of signal recovery under various sampling strategies.
Modeling Real-World Signals
The authors define the Approximately Bandlimited (ABL) class as signals where high-frequency components decay according to a power law. This model is validated using real-world datasets, such as temperature readings across the United States and wind speeds in Minnesota. As shown in the frequency analysis of temperature data, while most energy is concentrated in low frequencies, a non-zero tail persists, necessitating the ABL model.
Theoretical Framework and Notation
To analyze recovery performance, the paper employs a rigorous mathematical framework involving graph shifts, Fourier bases, and sampling operators. The notation used to define these components and their dimensions is summarized below:
Sampling Strategies and Minimax Limits
The research compares three primary sampling strategies:
- Uniform Sampling: Nodes are selected at random with equal probability.
- Experimentally Designed Sampling: Nodes are selected based on a pre-determined distribution, specifically proportional to "leverage scores" (the squared norms of the rows of the graph Fourier basis).
- Active Sampling: Samples are chosen sequentially, using feedback from previous observations.
A key theoretical contribution is the derivation of minimax lower bounds on recovery risk. Surprisingly, the authors prove that for ABL signals, active sampling does not fundamentally improve the convergence rate over a well-designed experimental sampling strategy. This suggests that the primary benefit of sophisticated sampling comes from understanding the graph's static topology rather than dynamic feedback.
The Impact of Graph Topology
The paper categorizes graphs into two types to show how topology dictates sampling efficiency:
- Type-1 (Homogeneous): Regular graphs like rings or grids where nodes have similar influence. On these graphs, uniform sampling performs nearly as well as experimental design.
- Type-2 (Heterogeneous): Irregular networks like power-law or small-world graphs. Here, uniform sampling is highly inefficient. Optimal recovery requires sampling "influential" nodes identified by leverage scores.
Proposed Recovery Strategy
The authors propose a Sampled Projection algorithm that reweights samples based on their sampling scores and projects them onto a low-frequency subspace. This method is shown to be an unbiased estimator for low-frequency components and achieves the minimax optimal convergence rate of $m^{-2\beta/(2\beta+1)}$, where $m$ is the number of samples and $\beta$ is the signal decay parameter.
Conclusion
By moving to an approximately bandlimited model, this work provides a more robust theoretical foundation for GSP. The findings highlight that while active sampling may offer practical conveniences, the fundamental limits of recovery are dictated by the alignment between the sampling distribution and the graph's spectral structure. This provides a clear theoretical explanation for the success of structure-aware sampling in fields like semi-supervised learning.
Summary updated