In classical signal processing, we often deal with data sampled at regular intervals, like the pixels in an image or the pressure waves of a sound file. But much of the world’s data is irregular. Brain activity is measured at specific electrode sites; social opinions spread through arbitrary friendship networks; sensor data is collected from scattered weather stations.
When these irregular datasets have missing values—a common "headache" in fields like Brain-Computer Interface (BCI) research—we cannot use standard linear interpolation. Instead, we must turn to Graph Signal Processing (GSP). By treating data points as signals residing on the nodes of a graph, we can use the underlying topology to "fill in the blanks" with remarkable precision.
Smoothness as a Reconstruction Engine
The core intuition behind graph interpolation is smoothness. If two nodes are connected by a strong edge in a graph, we expect their signal values to be similar.
Lucas Drumetz, Yassine El Ouahidi, and their colleagues demonstrate this in Spatial Graph Signal Interpolation with an Application for Merging BCI Datasets with Various Dimensionalities. When merging EEG datasets with different electrode layouts, they treat the sensor array as a graph. Missing sensor values are estimated by minimizing a "smoothness functional"—essentially a mathematical penalty for sharp differences between connected nodes.
This is often achieved using the Graph Laplacian, a matrix that captures the graph's connectivity. As David I Shuman and Mohammad Javad Faraji explain in A Framework for Multiscale Transforms on Graphs, we can use the Green’s functions of a regularized Laplacian to perform variational spline interpolation. This ensures the reconstructed signal remains consistent with the intrinsic topology of the data, rather than just its Euclidean coordinates.
The Spectral View of Sampling
Just as a radio signal can be decomposed into frequencies, a graph signal can be decomposed into graph frequencies via the Graph Fourier Transform (GFT). This spectral perspective allows us to define "bandlimited" signals—signals that only contain low-frequency components (i.e., they change slowly across the graph).
In Graph Signal Processing - Part II: Processing and Analyzing Signals on Graphs, Ljubiša Stanković and co-authors show that if a signal is sparse in the graph frequency domain, it can be perfectly reconstructed from only a small subset of nodes. This is the graph equivalent of the Nyquist-Shannon sampling theorem.
Santiago Segarra and Alejandro Ribeiro take this further in Reconstruction of Graph Signals Through Percolation from Seeding Nodes. They describe a process where sparse "seeding" values are injected into the network and allowed to "percolate" through a graph filter. By choosing the right seeds and filter coefficients, one can induce a specific global state across the entire network.
Bayesian and Algebraic Recovery
When data is not just missing but also noisy, we need more robust frameworks. Sam Leone and Smita Krishnaswamy propose Bayesian Formulations for Graph Spectral Denoising, which combines a smoothness prior with models for specific noise types (like dropout in gene expression data). By using L1-norm regularization, they frame missing data recovery as a sparse regression task, allowing the system to selectively trust observed data while reconstructing the rest.
For specific graph structures, even more efficient methods exist. Madeleine S. Kotzagiannidis and Pier Luigi Dragotti introduced Graph-FRI, which applies Finite Rate of Innovation theory to circulant graphs. They prove that sparse signals can be recovered using algebraic solvers like Prony’s method, requiring a minimal number of spectral samples.
Why Graph Neural Networks Excel
While classical GSP provides closed-form solutions, modern Graph Neural Networks (GNNs) offer a powerful implementation of these theories. A. Martina Neuman and Rongrong Wang provide theoretical guarantees showing that GNNs are fundamentally more efficient than standard neural networks at generalizing smooth functions.
They argue that GNN layers act as physical realizations of sampling formulas. By leveraging the graph structure as a reconstruction kernel, GNNs can achieve lower error rates with fewer weights and training samples, effectively "learning" the interpolation rules that GSP researchers derive mathematically.