acceptodds
Under review as a conference paper at ICLR 2027

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

Abstract

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.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
graph transformers, certified robustness, randomized smoothing, graph neural networks, adversarial robustness, positional encoding, spectral graph theory

Reviews

Among:
Shape:
1234this paper, Bottom 2%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.33 over 3 reviews, above 2% of the others.
Reviewer_zM5xOpenReview ↗
Rating
1
Confidence
4
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

Not necessary, paper clearly violates page limit (10 instead of 9 pages) and should be desk rejected.

Critical strengths

Not necessary, paper clearly violates page limit (10 instead of 9 pages) and should be desk rejected.

Critical weaknesses

Paper clearly violates page limit (10 instead of 9 pages) and should be desk rejected.

Questions for authors

Not necessary, paper clearly violates page limit (10 instead of 9 pages) and should be desk rejected.

Reviewer_CNEhOpenReview ↗
Rating
1
Confidence
4
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper may have scientific merit. However, the main text contains 10 pages, exceeding the 9-page limit specified in the ICLR 2027 Author Guidelines for initial submissions. According to the guidelines, papers violating this requirement are subject to desk rejection. Therefore, I recommend that the Area Chair consider this submission for desk rejection due to the formatting violation.

Critical strengths

The paper may have scientific merit. However, the main text contains 10 pages, exceeding the 9-page limit specified in the ICLR 2027 Author Guidelines for initial submissions. According to the guidelines, papers violating this requirement are subject to desk rejection. Therefore, I recommend that the Area Chair consider this submission for desk rejection due to the formatting violation.

Critical weaknesses

The paper may have scientific merit. However, the main text contains 10 pages, exceeding the 9-page limit specified in the ICLR 2027 Author Guidelines for initial submissions. According to the guidelines, papers violating this requirement are subject to desk rejection. Therefore, I recommend that the Area Chair consider this submission for desk rejection due to the formatting violation.

Questions for authors

The paper may have scientific merit. However, the main text contains 10 pages, exceeding the 9-page limit specified in the ICLR 2027 Author Guidelines for initial submissions. According to the guidelines, papers violating this requirement are subject to desk rejection. Therefore, I recommend that the Area Chair consider this submission for desk rejection due to the formatting violation.

Reviewer_vUWLOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
1
Soundness
1
Read review
Paper summary

GTCert studies certified robustness of Graph Transformers (GTs) against adversarial edge perturbations, arguing that GTs' global O(n2) attention over Laplacian-PE-augmented embeddings breaks the locality assumption underlying all existing graph certificates. The contributions include impossibility results. The paper introduces (a) a corrected three-term Davis–Kahan bound under edge flips; (b) a proof that spectral-norm Lipschitz certificates are vacuous for sparse-graph GTs, and (c) a proof that MPNN certificates (RIMS, SmoothGNN) are vacuous on LapPE-augmented GTs and that an adaptive adversary can break them with one closed-form edge deletion. It then proposes the attention-mask Bernoulli smoothing method that converts the GT into a random ensemble of sparse-attention models, yielding an empirical robustness radius derived from a directly measured vote-sensitivity rather than the intractable spectral-norm product, together with a consistency regularizer. The approach is validated on Cora and CiteSeer with a 4-layer GPS Graph Transformer.

Critical strengths
  1. The impossibility results are valuable.
  2. The perturbation analysis is detailed.
Critical weaknesses
  1. The paper is does not read well and is hard to follow which reduces the readability.
  2. The paper is as "certified robustness" but delivers no sound certificate, and its empirical radius appears weak against the stated adaptive adversary.
  3. The empirical evidence is limited.
Questions for authors
  1. Your sensitivity is measured on random edge changes, but the threat model is a worst-case attacker, and Proposition 4 shows one can always find a damaging edge. How is a radius built from random edges sound against that attacker, and what does the sensitivity become under your own Corollary 5 attack?
  2. On CiteSeer, the measured sensitivity is so small it falls below your Monte-Carlo noise level, which makes the radius infinite. Does this reflect real robustness, or just that your estimate is too noisy to detect any change? How do you rule out the latter?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.