arXiv:2611.25603v1 Announce Type: new
Abstract: Stability bounds for graph neural networks limit how much node representations can drift when the graph changes, but they are rarely compared with the simplest alternative: a bound on the distance between any two outputs, whatever the graph. We derive structural stability bounds for Graph Isomorphism Networks (GINs) and single-head GATv1 networks under deterministic edge perturbations that need not be small, and compare each with such a perturbation-independent diameter bound. For GINs, we characterize exactly when the stability bound is tighter, through a condition linking perturbation size, depth and maximum degree; it holds with a wide margin on Cora, but fails beyond a few layers on the low-degree MUTAG graphs. For GATv1, the bound is never tighter, which calls for analyses based on attention masses.
Trending
- On the Informativeness of Structural Stability Bounds for GNNs: GINs versus GATs
- Text-Aware, Vision-Blind: How Multimodal Image Editing Systems Handle Unsafe Inputs
- Decision-Focused Reinforcement Learning for LLM Post-Training
- [2611.26476] Anticipating Future Build Results with BuildPredictor
- Bradley-Terry Training Can Distort Outcome Probabilities of Initially Accurate Language World Models
- Exact Bayesian layers via characteristic functions
- Few-Shot Cross-City Traffic Prediction with Conditional Diffusion
- Simulation-pretrained autoencoders versus PCA for compressing multimode fibre transmission matrices
