GSP-KalmanNet: Tracking Graph Signals via Neural-Aided Kalman Filtering

Itay Buchnik, Guy Sagi, Nimrod Leinwand, Yuval Loya, Nir Shlezinger, Tirza Routtenberg

TL;DR

This paper introduces GSP-KalmanNet, a novel hybrid approach that combines graph signal processing (GSP) with deep learning to track dynamic graph signals more efficiently and robustly. It tackles the challenges of high dimensionality, model mismatches, and unknown noise statistics in real-world applications like power grids.

What Problem Does This Paper Address?

Tracking dynamic systems represented by graph signals is crucial in many fields, such as social networks, power grids, and transportation systems. These systems are often modeled using state-space (SS) models, and the Kalman Filter (KF) is a standard tool for tracking. However, applying KF to graph signals presents significant challenges:

  • High Dimensionality: Graph signals can have a very large number of nodes (N), making traditional KF computationally expensive and slow.
  • Model Mismatches: Real-world systems rarely perfectly match their mathematical models. Inaccuracies in the system dynamics, measurement functions, or even the graph topology itself can severely degrade KF performance.
  • Unknown Noise Statistics: The distributions of noise in the system are often unknown or non-Gaussian, which is a requirement for standard KF variants.

Existing solutions either struggle with scalability due to high dimensionality or lack robustness when models are imperfect. This paper aims to bridge this gap by developing a method that is both scalable and robust to model uncertainties.

Methods

The core contribution is the GSP-KalmanNet, a hybrid model-based/data-driven algorithm. It builds upon two key ideas:

  1. Graph Signal Processing (GSP) for Scalability: GSP provides tools to exploit the inherent structure of graph signals. The paper leverages GSP to transform the tracking problem into the graph frequency domain. This allows for filtering operations to be performed more efficiently, reducing the computational complexity from O(N³) to O(N²) or even O(N) for certain operations, thus addressing the high dimensionality challenge. This is achieved by developing the GSP-Extended Kalman Filter (GSP-EKF), which restricts the Kalman Gain (KG) to be a graph filter.
  2. Neural-Aided Kalman Filtering for Robustness: To handle model mismatches and unknown noise statistics (Challenges C.2-C.4), the GSP-EKF is augmented with a deep learning component, inspired by the KalmanNet framework. Instead of explicitly computing the KG based on potentially inaccurate model parameters, a Recurrent Neural Network (RNN) is trained to learn the KG. This RNN takes features indicative of the state and measurement noise statistics as input and outputs the coefficients of a graph filter for the KG. This data-driven approach allows the system to learn a "surrogate" KG that is effective even when the underlying SS model is imperfect.

The GSP-KalmanNet essentially uses the GSP-EKF as a framework and replaces the KG computation with a learned RNN module.

Datasets

The paper uses synthetic datasets generated according to the described models for training and evaluation. They also evaluate their method on a real-world application: Power System State Estimation (PSSE), using data from the IEEE 14-bus system. No new datasets are introduced; rather, existing benchmarks are used for comparison.

Key Insights and Ideas

  • Graph Frequency Domain is Key for Scalability: Transforming the problem to the graph frequency domain is crucial for making KF-based tracking computationally feasible for large-scale graph signals.
  • Learned Kalman Gain for Robustness: By learning the Kalman Gain (KG) using an RNN, the system can effectively adapt to model mismatches and unknown noise statistics, a significant limitation of traditional KF.
  • Hybrid Approach Offers Best of Both Worlds: GSP-KalmanNet successfully combines the interpretability and structure-awareness of model-based methods (GSP-EKF) with the adaptability and robustness of data-driven methods (RNN).
  • Parameter Efficiency Matters: The paper highlights that GSP-KalmanNet's RNN architecture is more parameter-efficient than other data-driven methods like GNN+RNN, leading to faster training and better stability.

Key Results

  • Improved Accuracy: GSP-KalmanNet consistently outperforms traditional EKF, GSP-EKF, and data-driven methods like KalmanNet and GNN+RNN in terms of Mean Squared Error (MSE) across various scenarios, including full and partial information settings. For instance, in one scenario, it achieved a 15dB gap over data-driven methods and over 20dB over model-based methods.
  • Reduced Computational Complexity: The paper demonstrates significant computational savings. While EKF has O(N³) complexity, GSP-EKF achieves O(N²), and GSP-KalmanNet's KG computation is O(N²).
  • Faster Inference: GSP-KalmanNet exhibits faster inference times compared to EKF, GSP-EKF, and KalmanNet, especially for larger graphs, due to its efficient architecture and the parallelization capabilities of deep learning frameworks.
  • Robustness to Model Misspecification: The method shows remarkable resilience to inaccuracies in the graph structure, state evolution, and measurement functions, often achieving performance comparable to the full information case.

Limitations and Future Work

  • Graph Structure Assumption: The current formulation assumes a stationary graph with a known number of nodes.
  • Future Work: The authors suggest extending GSP-KalmanNet to handle graphs with varying numbers of nodes and structures, potentially by exploring alternative architectures like Graph Neural Networks (GNNs) for KG computation. They also mention the possibility of using the learned KG to infer state error covariance for uncertainty measures and enabling unsupervised learning.

Summary updated

Abstract

Dynamic systems of graph signals are encountered in various applications, including social networks, power grids, and transportation. While such systems can often be described as state space (SS) models, tracking graph signals via conventional tools based on the Kalman filter (KF) and its variants is typically challenging. This is due to the nonlinearity, high dimensionality, irregularity of the domain, and complex modeling associated with real-world dynamic systems of graph signals. In this work, we study the tracking of graph signals using a hybrid model-based/data-driven approach. We develop the GSP-KalmanNet, which tracks the hidden graphical states from the graphical measurements by jointly leveraging graph signal processing (GSP) tools and deep learning (DL) techniques. The derivations of the GSP-KalmanNet are based on extending the KF to exploit the inherent graph structure via graph frequency domain filtering, which considerably simplifies the computational complexity entailed in processing high-dimensional signals and increases the robustness to small topology changes. Then, we use data to learn the Kalman gain following the recently proposed KalmanNet framework, which copes with partial and approximated modeling, without forcing a specific model over the noise statistics. Our empirical results demonstrate that the proposed GSP-KalmanNet achieves enhanced accuracy and run time performance as well as improved robustness to model misspecifications compared with both model-based and data-driven benchmarks.
BibTeX
@article{buchnik2024gsp,
  author = {Itay Buchnik and Guy Sagi and Nimrod Leinwand and Yuval Loya and Nir Shlezinger and Tirza Routtenberg},
  title = {{GSP-KalmanNet: Tracking Graph Signals via Neural-Aided Kalman Filtering}},
  journal = {IEEE TSP},
  year = {2024},
  doi = {10.1109/tsp.2024.3435935},
}
Figure