# On the Impact of Downstream Tasks on Sampling and Reconstructing Noisy Graph Signals

arXiv: https://arxiv.org/abs/2509.10874 · HTML: https://mlsanity.com/paper/2509.10874/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 27 of its 43 references that are in the map.
- First posted on arXiv 13 Sep 2025.

## Builds on (most cited first, 27 of 27)

- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering](https://mlsanity.com/paper/1606.09375/) (2016)
- [Simplifying Graph Convolutional Networks](https://mlsanity.com/paper/1902.07153/) (2019)
- [Graph Signal Processing: Overview, Challenges and Applications](https://mlsanity.com/paper/1712.00468/) (2017)
- [BernNet: Learning Arbitrary Graph Spectral Filters via Bernstein Approximation](https://mlsanity.com/paper/2106.10994/) (2021)
- [Handling Missing Data with Graph Representation Learning](https://mlsanity.com/paper/2010.16418/) (2020)
- [Classic GNNs are Strong Baselines: Reassessing GNNs for Node Classification](https://mlsanity.com/paper/2406.08993/) (2024)
- [On the Unreasonable Effectiveness of Feature propagation in Learning on Graphs with Missing Node Features](https://mlsanity.com/paper/2111.12128/) (2021)
- [Missing Data Imputation with Adversarially-trained Graph Convolutional Networks](https://mlsanity.com/paper/1905.01907/) (2019)
- [Graph Convolutional Networks for Graphs Containing Missing Features](https://mlsanity.com/paper/2007.04583/) (2020)
- [Learning on Attribute-Missing Graphs](https://mlsanity.com/paper/2011.01623/) (2020)
- [Graph Neural Networks with Learnable and Optimal Polynomial Bases](https://mlsanity.com/paper/2302.12432/) (2023)
- [Discrete Signal Processing on Graphs: Sampling Theory](https://mlsanity.com/paper/1503.05432/) (2015)
- [Matrix Completion on Graphs](https://mlsanity.com/paper/1408.1717/) (2014)
- [Gaussian Processes on Graphs via Spectral Kernel Learning](https://mlsanity.com/paper/2006.07361/) (2020)
- [Incomplete Graph Representation and Learning via Partial Graph Neural Networks](https://mlsanity.com/paper/2003.10130/) (2020)
- [Random sampling of bandlimited signals on graphs](https://mlsanity.com/paper/1511.05118/) (2015)
- [Greedy Sampling of Graph Signals](https://mlsanity.com/paper/1704.01223/) (2017)
- [On Manipulating Signals of User-Item Graph: A Jacobi Polynomial-based Graph Collaborative Filtering](https://mlsanity.com/paper/2306.03624/) (2023)
- [Fast Graph Sampling Set Selection Using Gershgorin Disc Alignment](https://mlsanity.com/paper/1907.06179/) (2019)
- [Practical graph signal sampling with log-linear size scaling](https://mlsanity.com/paper/2102.10506/) (2021)
- [Graph sampling with determinantal processes](https://mlsanity.com/paper/1703.01594/) (2017)
- [Low-complexity Graph Sampling with Noise and Signal Reconstruction via Neumann Series](https://mlsanity.com/paper/1812.02109/) (2018)
- [A-Optimal Sampling and Robust Reconstruction for Graph Signals via Truncated Neumann Series](https://mlsanity.com/paper/1803.03353/) (2018)
- [Towards joint graph learning and sampling set selection from data](https://mlsanity.com/paper/2412.09753/) (2024)
- [On the Impact of Sample Size in Reconstructing Noisy Graph Signals: A Theoretical Characterisation](https://mlsanity.com/paper/2406.16816/) (2024)
- [Graph-Based Signal Sampling with Adaptive Subspace Reconstruction for Spatially-Irregular Sensor Data](https://mlsanity.com/paper/2409.09526/) (2024)

## Abstract (arXiv)

We investigate graph signal reconstruction and sample selection for classification tasks. We present general theoretical characterisations of classification error applicable to multiple commonly used reconstruction methods, and compare that to the classical reconstruction error. We demonstrate the applicability of our results by using them to derive new optimal sampling methods for linearized graph convolutional networks, and show improvement over other graph signal processing based methods.