Practical graph signal sampling with log-linear size scaling
Graph signal sampling is the problem of selecting a subset of representative graph vertices whose values can be used to interpolate missing values on the remaining graph vertices. Optimizing the choice of sampling set using concepts from experiment design can help minimize the effect of noise in the input signal. While many existing sampling set selection methods are computationally intensive because they require an eigendecomposition, existing eigendecompostion-free methods are still much slower than random sampling algorithms for large graphs. In this paper, through optimizing sampling sets towards the D-optimal objective from experiment design, we propose a sampling algorithm that has complexity comparable to random sampling algorithms, while reaching accuracy similar to existing eigendecomposition-free methods for a broad range of graph types.
Code (1)
Tasks
Missing ValuesSimilar Papers 제목 키워드 기반
Scalable Graph Coreset Selection via Greedy Sampling
Sampling representative nodes from large graphs is fundamental to graph signal processing and network analysis, yet existing methods require access to the full graph Laplacian, making them impractical at scale. We propos…
On Random Sampling of Diffused Graph Signals with Sparse Inputs on Vertex Domain
The sampling of graph signals has recently drawn much attention due to the wide applications of graph signal processing. While a lot of efficient methods and interesting results have been reported to the sampling of band…
Nonlinear Sheaf Diffusion in Graph Neural Networks
This work focuses on exploring the potential benefits of introducing a nonlinear Laplacian in Sheaf Neural Networks for graph-related tasks. The primary aim is to understand the impact of such nonlinearity on diffusion d…
Design of Sampling Set for Bandlimited Graph Signal Estimation
It is of particular interest to reconstruct or estimate bandlimited graph signals, which are smoothly varying signals defined over graphs, from partial noisy measurements. However, choosing an optimal subset of nodes to …
Experimental DesignQuantizationregressionA Poincaré Inequality and Consistency Results for Signal Sampling on Large Graphs
Large-scale graph machine learning is challenging as the complexity of learning models scales with the graph size. Subsampling the graph is a viable alternative, but sampling on graphs is nontrivial as graphs are non-Euc…
Graph Sampling