Parallel Graph Signal Processing: Sampling and Reconstruction

Daniela Dapena, Daniel L. Lau, Gonzalo R. Arce

Research output: Contribution to journalArticlepeer-review

3 Scopus citations


Graph signal processing (GSP) extends classical signal processing methods to analyzing signals supported over irregular grids represented by graphs. Within the scope of GSP, sampling and reconstruction represent fundamental tools that have received considerable attention. For very large graphs, however, many of the current methods struggle with the computational and memory requirements. Vertex domain and randomized sampling strategies somewhat ameliorate the computational requirements, but these algorithms perform poorly at preserving signal fidelity for graphs with hundreds of thousands of vertices. To address these shortcomings, this article introduces a new and scalable approach that can be easily parallelized. This new approach uses existing graph partitioning algorithms in concert with vertex-domain blue-noise sampling and reconstruction, performed independently across partitions. In the reconstruction, some degree of overlapping is added to the partitions to induce trans-partition smoothness in the recovered signal. We also propose two sampling schemes based on the spatial characteristic of the graph that minimizes the recovery error. The first combines graph partitioning with the Void-and-Cluster algorithm, while the second approach uses Error Diffusion. We conclude this article with experiments on synthetic and real data that show the effectiveness of these new approaches on very large graphs.

Original languageEnglish
Pages (from-to)190-206
Number of pages17
JournalIEEE Transactions on Signal and Information Processing over Networks
StatePublished - 2023

Bibliographical note

Funding Information:
This work was supported in part by National Science Foundation under Grants 1815992 and 1816003

Publisher Copyright:
© 2015 IEEE.


  • Graph signal reconstruction
  • blue-noise
  • graph signal processing
  • graph signal sampling

ASJC Scopus subject areas

  • Signal Processing
  • Information Systems
  • Computer Networks and Communications


Dive into the research topics of 'Parallel Graph Signal Processing: Sampling and Reconstruction'. Together they form a unique fingerprint.

Cite this