Graph neural networks keep trusted predictions while adapting safely
Reference-Tail Trust:Certified Probability Floors for Learned Updates Inside a Deployed Network
Machine LearningArtificial Intelligence
Summary
Graph neural networks sometimes need to update their predictions using new information without losing trust in what they previously predicted. The authors present Reference-Tail Trust (RTT), a method that lets parts of the network learn updates while guaranteeing those updates won’t make predictions worse beyond a certified limit. RTT uses mathematical checks to ensure the updated results stay close to trusted ones, and if not, it falls back to old predictions to stay safe. Tests show RTT improves predictions modestly while keeping error rates very low across various graph types and tasks.
What this means in practice
- •For network engineers: Enhance graph-based network monitoring systems with reliable real-time updates that do not degrade trusted detections.
- •For molecular data scientists: Improve molecular property prediction pipelines by safely adapting graph models to evolving datasets with certified accuracy guarantees.
Authors
Abdolvahab Khalili Sadaghiani, Jose Nunez-Yanez
Abstract
Graph neural networks (GNNs) need to exploit improved message passing without surrendering control over predictions already trusted in deployment. We introduce Reference-Tail Trust (RTT), a framework that admits learned updates inside a frozen GNN and certifies the prediction actually served. RTT couples graph-based proposal states with a constrained internal optimizer: each displacement is charged for its worst-case terminal cross-entropy increase through the incumbent's remaining message-passing layers. A trajectory-validated tube and an independent checker enforce per-node probability floors, $p^{\mathrm{s}}_{ic} \ge e^{-H_{\mathrm{row}}} p^{\mathrm{r}}_{ic}$, and a call-level budget, $\sum_i w_i D_\infty(p^{\mathrm{r}}_i \| p^{\mathrm{s}}_i) \le H^+$, uniformly over labels. Calls whose adapted outputs pass certification require no separate full incumbent rollout; failed certificates trigger whole-call fallback. We derive the exact probability-floor frontier by water-filling, characterize architecture-constrained efficiency, and establish conditions under which internal propagation exploits evidence unavailable to restricted output correctors. In the reported ogbn-arxiv audit, RTT achieves $6.5\times 10^{-3}$ nats of mean gain per call, with a one-sided 95% regression-rate upper bound of 0.95% and a 95% negative-flip upper bound of 0.51% on the uninspected part of the reserved node population. Its mean gain is 61% of a cross-fitted posterior-based frontier estimate and exceeds the strongest matched one-pass corrector by $+0.9\times 10^{-3}$ nats. Reported experiments span eight proposals, six graph-incumbent families, structural and temporal graph shifts, and molecular prediction, with additional image and tabular evaluations. RTT makes GNN adaptation a budgeted, certifiable inference decision rather than an unconditional model replacement.