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.
Core Components
- Neural Controller ($f_\theta$): A small neural network designed to learn the optimal adjustments for node features based on the current prediction state.
- 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.
- 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.
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