Relaxing Graph Transformers for Adversarial Attacks
This work addresses the vulnerability of Graph Transformers to adversarial attacks, which is crucial for ensuring reliable AI in graph-based applications like node classification and fake-news detection.
The paper tackled the problem of adversarial robustness in Graph Transformers, which was previously unexplored, by developing the first adaptive attacks targeting three architectures with different positional encodings, revealing that these models can be catastrophically fragile.
Existing studies have shown that Graph Neural Networks (GNNs) are vulnerable to adversarial attacks. Even though Graph Transformers (GTs) surpassed Message-Passing GNNs on several benchmarks, their adversarial robustness properties are unexplored. However, attacking GTs is challenging due to their Positional Encodings (PEs) and special attention mechanisms which can be difficult to differentiate. We overcome these challenges by targeting three representative architectures based on (1) random-walk PEs, (2) pair-wise-shortest-path PEs, and (3) spectral PEs - and propose the first adaptive attacks for GTs. We leverage our attacks to evaluate robustness to (a) structure perturbations on node classification; and (b) node injection attacks for (fake-news) graph classification. Our evaluation reveals that they can be catastrophically fragile and underlines our work's importance and the necessity for adaptive attacks.