Abstract
Sampling of signals defined over the nodes of a graph is one of the crucial problems in graph signal processing. While in classical signal processing sampling is a well defined operation, when we consider a graph signal many new challenges arise and defining an efficient sampling strategy is not straightforward. Recently, several works have addressed this problem. The most common techniques select a subset of nodes to reconstruct the entire signal. However, such methods often require the knowledge of the signal support and the computation of the sparsity basis before sampling. Instead, in this paper we propose a new approach to this issue. We introduce a novel technique that combines localized sampling with compressed sensing. We first choose a subset of nodes and then, for each node of the subset, we compute random linear combinations of signal coefficients localized at the node itself and its neighborhood. The proposed method provides theoretical guarantees in terms of reconstruction and stability to noise for any graph and any orthonormal basis, even when the support is not known.
Introduction
In Graph Signal Processing (GSP), sampling signals—such as sensor network data or social media trends—presents unique challenges compared to traditional time-series analysis. Most existing sampling methods rely on selecting a specific subset of nodes. However, these "selection-based" methods typically require a priori knowledge of the signal's spectral support, necessitating the computation of graph eigenvectors before measurements are taken.
While Compressed Sensing (CS) offers a framework for "blind" recovery (without knowing the support), standard CS relies on dense random projections. In large-scale graphs, global projections are often physically impossible due to communication constraints; nodes can typically only interact with their immediate neighbors. This research addresses the need for a sampling scheme that is strictly local yet retains the robust recovery guarantees of Compressed Sensing.
Proposed Methodology: Randomized Local Aggregations
The authors introduce Randomized Local Aggregations, a three-step framework designed to bridge the gap between locality and universality:
- Node Selection: A sampling set of nodes is chosen. This set must be a "dominating set" (or a superset), ensuring every node in the graph is either in the set or adjacent to a node within it.
- Local Aggregation: At each selected node, a measurement is taken by computing a random linear combination of signal values from that node and its immediate neighbors.
- Signal Recovery: The original signal is reconstructed using standard CS techniques, such as $\ell_1$-norm minimization for unknown support or least-squares when the support is known.
The core innovation lies in the sampling matrix $\Phi$. Unlike dense CS matrices, $\Phi$ is sparse and respects the graph's topology. The authors prove that this localized matrix satisfies the Restricted Isometry Property (RIP), ensuring stable and accurate reconstruction.
Experimental Evaluation
The method was evaluated using several standard graph benchmarks, including the Minnesota road network, random geometric sensor graphs, and Erdős-Rényi random graphs. The latter was used primarily to test the numerical stability of the sampling matrix.
Numerical Stability and Performance
A critical advantage of the proposed method is its numerical stability. Previous "aggregation" methods often utilized powers of the adjacency matrix, leading to Vandermonde-like structures that are notoriously ill-conditioned. By using randomized weights, the proposed method avoids this stability crisis.
As shown in Table I, the proposed method maintains a low condition number (typically between 1.5 and 3.0 for larger measurement sets) regardless of the graph's edge probability. In contrast, previous state-of-the-art methods [20] exhibit condition numbers that explode to $10^{28}$, rendering them practically unusable in noisy environments.
Key Insights
- Locality vs. Universality: Local "mixing" via neighborhoods provides sufficient randomness to capture the signal's structure without global information.
- The Power of the Dominating Set: Ensuring the sampling set is a dominating set prevents "blind spots" in the graph representation, ensuring every node's information is represented.
- Minimum Node Multiplicity ($g_{min}$): The stability of the reconstruction is tied to $g_{min}$—the minimum number of times any node appears in the measurements. The proposed strategy specifically aims to maximize this value.
Conclusion
Randomized local aggregations provide a robust framework for sampling graph signals under physical locality constraints. The method demonstrates superior numerical stability and reconstruction accuracy in scenarios where signal support is unknown. Future work will address challenges in highly fragmented graphs and optimize hardware implementations for real-world sensor networks.
Summary updated