Abstract
Inference of space-time varying signals on graphs emerges naturally in a plethora of network science related applications. A frequently encountered challenge pertains to reconstructing such dynamic processes, given their values over a subset of vertices and time instants. The present paper develops a graph-aware kernel-based kriged Kalman filter that accounts for the spatio-temporal variations, and offers efficient online reconstruction, even for dynamically evolving network topologies. The kernel-based learning framework bypasses the need for statistical information by capitalizing on the smoothness that graph signals exhibit with respect to the underlying graph. To address the challenge of selecting the appropriate kernel, the proposed filter is combined with a multi-kernel selection module. Such a data-driven method selects a kernel attuned to the signal dynamics on-the-fly within the linear span of a pre-selected dictionary. The novel multi-kernel learning algorithm exploits the eigenstructure of Laplacian kernel matrices to reduce computational complexity. Numerical tests with synthetic and real data demonstrate the superior reconstruction performance of the novel approach relative to state-of-the-art alternatives.
Introduction
In many modern applications, data is naturally represented as signals on a graph—for example, temperatures recorded by weather stations, stock prices in a financial network, or traffic delays across internet routers. A recurring challenge is the reconstruction of these dynamic processes when only a small subset of nodes is observable at any given time. This task is particularly difficult when both the signal values and the underlying graph topology change over time.
Previous approaches often assume slow signal changes or require strict statistical knowledge, such as the exact covariance of the data. This paper introduces the Kernel Kriged Kalman Filter (KeKriKF), an online, computationally efficient estimator designed to track fast-changing signals over dynamic graphs with minimal prior information.
Methodology
Spatio-Temporal Decomposition (KeKriKF)
The proposed framework models the time-varying graph signal as a combination of two components: a structured, slow-varying "trend" and an instantaneous, fast-varying spatial fluctuation. The KeKriKF solves a Kernel Ridge Regression (KRR) problem online, utilizing a Kalman filter-like step to track the temporal trend and a Kriging step to interpolate spatial fluctuations. By framing the problem as a deterministic regression, the authors bypass the need for rigid probabilistic assumptions, making the model robust to non-stationary real-world data.
Online Multi-Kernel Learning (MKriKF)
Because kernel performance depends heavily on the choice of the kernel function, the authors introduce a Multi-Kernel (MKriKF) extension. This module adaptively learns the best linear combination of kernels from a predefined dictionary on the fly.
To make this computationally feasible for online operation, the authors exploit the fact that all Laplacian kernels associated with a specific graph share the same eigenvectors. This allows for a Projected Gradient Descent (PGD) algorithm that reduces the computational complexity of gradient calculations from $O(N^3M)$ to $O(NM)$, where $N$ is the number of nodes and $M$ is the number of kernels.
Experimental Evaluation
The algorithms were evaluated on synthetic data and three real-world datasets: US Temperature Data, Global GDP Data, and Internet2 Network Delays.
Key results include:
- Superior Accuracy: Both KeKriKF and MKriKF consistently achieved lower Normalized Mean-Square Error (NMSE) compared to state-of-the-art alternatives like Least Mean-Square (LMS) and Distributed Least-Squares Reconstruction (DLSR).
- Adaptability: In the GDP dataset, MKriKF successfully learned optimal kernel combinations on the fly, outperforming manually tuned models and accurately tracking unsampled data points (e.g., Greece's GDP).
- Robustness: Synthetic tests confirmed that the algorithm maintains low error rates even under abrupt, random changes in graph topology.
Conclusion
The KeKriKF and its multi-kernel extension provide a powerful framework for online signal reconstruction on dynamic graphs. By separating temporal trends from spatial fluctuations and exploiting the spectral properties of Laplacian kernels, the method achieves high accuracy with low computational overhead. Future work may involve data-driven learning of the state transition matrix and the development of fully distributed, consensus-based implementations for massive decentralized networks.
Summary updated