GTCert: Certified Robustness for Graph Transformers via Attention-Mask Randomized Smoothing

Graph Transformers (GTs) achieve strong performance on graph learning tasks, but their global O(n²) self-attention invalidates every existing certified robustness guarantee, all of which rely on a local influence assumption that fails under full attention. We present GTCert, a robustness analysis framework designed for Graph Transformers. The core mechanism is attention-mask randomized smoothing: Bernoulli masks independently ablate attention entries with probability q, converting the GT into a random ensemble of sparse models. We make four contributions: (i) a corrected Davis–Kahan bound on LapPE perturbation under edge flips; (ii) a proof that spectral-norm Lipschitz certificates are always vacuous (r_theory = 0) for sparse-graph GTs, plus an empirically grounded radius r_emp based on directly measured vote-probability sensitivity δ_p,max; (iii) an adaptive adversary construction that breaks all MPNN-based certificates on LapPE-augmented GTs; (iv) a consistency regularization objective that provably reduces δ_p,max. Experiments on Cora and CiteSeer confirm r*_theory = 0 and demonstrate CA_emp@1 = 0.780 on Cora, where all MPNN baselines yield 0.000.