# Graph signal interpolation with Positive Definite Graph Basis Functions

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Dec 2019.

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

- [Kernel-Based Models for Influence Maximization on Graphs based on Gaussian Process Variance Minimization](https://mlsanity.com/paper/2103.01575/) (2021)
- [Reconstruction of Graph Signals on Complex Manifolds with Kernel Methods](https://mlsanity.com/paper/2505.15202/) (2025)
- [Graph Neural Networks for Community Detection in Graph Signal Analysis](https://mlsanity.com/paper/2605.19733/) (2026)

## Abstract (arXiv)

For the interpolation of graph signals with generalized shifts of a graph basis function (GBF), we introduce the concept of positive definite functions on graphs. This concept merges kernel-based interpolation with spectral theory on graphs and can be regarded as a graph analog of radial basis function interpolation in euclidean spaces or spherical basis functions. We provide several descriptions of positive definite functions on graphs, the most relevant one is a Bochner-type characterization in terms of positive Fourier coefficients. These descriptions allow us to design GBF's and to study GBF interpolation in more detail: we are able to characterize the native spaces of the interpolants, we provide explicit estimates for the interpolation error and obtain bounds for the numerical stability. As a final application, we show how GBF interpolation can be used to get quadrature formulas on graphs.