Control the GNN: Utilizing Neural Controller with Lyapunov Stability for Test-Time Feature Reconstruction

Jielong Yang, Rui Ding, Feng Ji, Hongbin Wang, Linbo XiearXiv 2024 · DOI · arXiv

Abstract

Graph Neural Networks (GNNs) are susceptible to performance degradation when encountering distribution shifts at test time. While test-time feature reconstruction offers a flexible alternative to retraining, existing heuristic methods lack theoretical guarantees of stability. This paper introduces a control-theoretic framework that treats node feature reconstruction as a dynamical control problem. By employing a Neural Lyapunov Controller ($f_\theta$) alongside a learned Lyapunov function ($V_\phi$), we provide a theoretically grounded method to adjust input features such that GNN predictions converge toward ground-truth states. Our approach utilizes an SMT (Satisfiability Modulo Theories) solver for counterexample-guided training, ensuring the controller remains stable across the state space. Empirical evaluations on five benchmark datasets demonstrate that our method consistently improves accuracy and produces superior feature clustering compared to state-of-the-art baselines.

Introduction

Graph Neural Networks (GNNs) have demonstrated remarkable success in various domains, yet they remain brittle under distribution shift—scenarios where the test data distribution deviates significantly from the training data. Traditional remedies like data augmentation or regularization often necessitate costly model retraining.

A more flexible alternative is "test-time feature reconstruction," which involves adjusting input node features to align with the model's learned parameters. However, current reconstruction methods are largely heuristic and lack theoretical assurances that such adjustments will not lead to prediction instability or divergence. This work addresses these shortcomings by framing feature reconstruction as a control problem with formal stability guarantees.

Methodology: GNNs as Dynamical Systems

The proposed framework reinterprets a GNN's prediction process as a dynamical control system where predictions are "system states" and node features are "control variables." The objective is to "control" these features so that the system converges to a stable equilibrium point representing the ground truth.

The overall framework of the Neural Lyapunov Controller, illustrating the interaction between the Neural Controller, Lyapunov Function, GNN, and the SMT solver for counterexample-guided training.

Core Components

  1. Neural Controller ($f_\theta$): A small neural network designed to learn the optimal adjustments for node features based on the current prediction state.
  2. Neural Lyapunov Function ($V_\phi$): Based on control theory, this function acts as an "energy" metric that must strictly decrease as the system approaches the target equilibrium, providing a mathematical proof of stability.
  3. Counterexample-Guided Training: To ensure robustness, the authors employ an SMT solver to search the state space for "counterexamples"—specific instances where Lyapunov stability conditions are violated. These cases are iteratively added to the training set to refine the controller.

Experimental Results

The method was evaluated on five standard node classification benchmarks: Cora, Citeseer, Pubmed, Amazon Photo, and Amazon Computers. To simulate distribution shift, a Scalable Biased Sampler was used to create training sets that do not fully represent the test diversity.

Performance Gains

The proposed method, Ours$_{NC}$, consistently outperformed base GNN models (such as SGC) and existing reconstruction methods like FRGNN. For instance, on the Cora dataset, the method improved accuracy to 67.22%, up from the base model's 64.36%.

Feature Representation and Efficiency

Beyond raw accuracy, the neural controller produces more distinct feature representations. t-SNE visualizations confirm that reconstructed features result in tighter, more separable clusters for different node classes. Furthermore, because the control system is stabilized during training, it typically requires only a single adjustment step at test time, offering significant efficiency over iterative optimization heuristics.

t-SNE visualizations of node embeddings across different classes, demonstrating that the proposed method achieves tighter and more distinct clustering.

Discussion and Future Work

While the integration of control theory and SMT solvers provides rigorous stability, it introduces computational challenges. The SMT solver is currently a bottleneck, requiring node feature downsampling (via PCA) and the use of simplified base models like SGC to remain tractable. Additionally, the current implementation focuses on single-class reconstruction; extending this to multi-class equilibrium points simultaneously remains a complex theoretical and computational hurdle.

Future research will focus on developing more efficient stability verification methods and exploring alternative solvers to scale the Lyapunov-based control framework to larger, more complex graph architectures.

Summary updated

Abstract

The performance of graph neural networks (GNNs) is susceptible to discrepancies between training and testing sample distributions. Prior studies have attempted to mitigating the impact of distribution shift by reconstructing node features during the testing phase without modifying the model parameters. However, these approaches lack theoretical analysis of the proximity between predictions and ground truth at test time. In this paper, we propose a novel node feature reconstruction method grounded in Lyapunov stability theory. Specifically, we model the GNN as a control system during the testing phase, considering node features as control variables. A neural controller that adheres to the Lyapunov stability criterion is then employed to reconstruct these node features, ensuring that the predictions progressively approach the ground truth at test time. We validate the effectiveness of our approach through extensive experiments across multiple datasets, demonstrating significant performance improvements.
BibTeX
@misc{yang2024control,
  author = {Jielong Yang and Rui Ding and Feng Ji and Hongbin Wang and Linbo Xie},
  title = {{Control the GNN: Utilizing Neural Controller with Lyapunov Stability for Test-Time Feature Reconstruction}},
  year = {2024},
  eprint = {2410.09708},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2410.09708},
}
Figure