# Kernel-based Reconstruction of Graph Signals

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

## Key facts

- Cited by 20 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 May 2016.

## Built on by (most cited first, 20 of 20)

- [Graph Learning: A Survey](https://mlsanity.com/paper/2105.00696/) (2021)
- [Graph Filters for Signal Processing and Machine Learning on Graphs](https://mlsanity.com/paper/2211.08854/) (2022)
- [Gegenbauer Graph Neural Networks for Time-varying Signal Reconstruction](https://mlsanity.com/paper/2403.19800/) (2024)
- [Non-separable Spatio-temporal Graph Kernels via SPDEs](https://mlsanity.com/paper/2111.08524/) (2021)
- [Fairness-Aware Graph Filter Design](https://mlsanity.com/paper/2303.11459/) (2023)
- [Reconstructing nodal pressures in water distribution systems with graph neural networks](https://mlsanity.com/paper/2104.13619/) (2021)
- [Recovering Missing Node Features with Local Structure-based Embeddings](https://mlsanity.com/paper/2309.09068/) (2023)
- [Time-varying Signals Recovery via Graph Neural Networks](https://mlsanity.com/paper/2302.11313/) (2023)
- [Multiple Kernel Representation Learning on Networks](https://mlsanity.com/paper/2106.05057/) (2021)
- [Distributed Optimization of Graph Convolutional Network using Subgraph Variance](https://mlsanity.com/paper/2110.02987/) (2021)
- [Graph Signal Reconstruction Techniques for IoT Air Pollution Monitoring Platforms](https://mlsanity.com/paper/2201.00378/) (2022)
- [Fairness-aware Optimal Graph Filter Design](https://mlsanity.com/paper/2310.14432/) (2023)
- [Graph Signal Sampling for Inductive One-Bit Matrix Completion: a Closed-form Solution](https://mlsanity.com/paper/2302.03933/) (2023)
- [Inhomogeneous graph trend filtering via a l2,0 cardinality penalty](https://mlsanity.com/paper/2304.05223/) (2023)
- [Online Graph Filtering Over Expanding Graphs](https://mlsanity.com/paper/2409.07204/) (2024)
- [Regularized Recovery by Multi-order Partial Hypergraph Total Variation](https://mlsanity.com/paper/2102.09771/) (2021)
- [Gaussian Kernel Variance For an Adaptive Learning Method on Signals Over Graphs](https://mlsanity.com/paper/2204.12629/) (2022)
- [Graph Filter Transfer via Probability Density Ratio Weighting](https://mlsanity.com/paper/2210.14633/) (2022)
- [A Review of Graph-Powered Data Quality Applications for IoT Monitoring Sensor Networks](https://mlsanity.com/paper/2410.21006/) (2024)
- [Reconstruction of Graph Signals on Complex Manifolds with Kernel Methods](https://mlsanity.com/paper/2505.15202/) (2025)

## Abstract (arXiv)

A number of applications in engineering, social sciences, physics, and biology involve inference over networks. In this context, graph signals are widely encountered as descriptors of vertex attributes or features in graph-structured data. Estimating such signals in all vertices given noisy observations of their values on a subset of vertices has been extensively analyzed in the literature of signal processing on graphs (SPoG). This paper advocates kernel regression as a framework generalizing popular SPoG modeling and reconstruction and expanding their capabilities. Formulating signal reconstruction as a regression task on reproducing kernel Hilbert spaces of graph signals permeates benefits from statistical learning, offers fresh insights, and allows for estimators to leverage richer forms of prior information than existing alternatives. A number of SPoG notions such as bandlimitedness, graph filters, and the graph Fourier transform are naturally accommodated in the kernel framework. Additionally, this paper capitalizes on the so-called representer theorem to devise simpler versions of existing Thikhonov regularized estimators, and offers a novel probabilistic interpretation of kernel methods on graphs based on graphical models. Motivated by the challenges of selecting the bandwidth parameter in SPoG estimators or the kernel map in kernel-based methods, the present paper further proposes two multi-kernel approaches with complementary strengths. Whereas the first enables estimation of the unknown bandwidth of bandlimited signals, the second allows for efficient graph filter selection. Numerical tests with synthetic as well as real data demonstrate the merits of the proposed methods relative to state-of-the-art alternatives.