Invariant Graph Transformer
Authors: name: Zhe Xu, name: Menghai Pan, name: Yuzhong Chen, name: Huiyuan Chen, name: Yuchen Yan, name: Mahashweta Das, name: Hanghang Tong

Rationale discovery is defined as finding a subset of the input data that
maximally supports the prediction of downstream tasks. In graph machine
learning context, graph rationale is defined to locate the critical subgraph in
the given graph topology, which fundamentally determines the prediction
results. In contrast to the rationale subgraph, the remaining subgraph is named
the environment subgraph. Graph rationalization can enhance the model
performance as the mapping between the graph rationale and prediction label is
viewed as invariant, by assumption. To ensure the discriminative power of the
extracted rationale subgraphs, a key technique named "intervention" is applied.
The core idea of intervention is that given any changing environment subgraphs,
the semantics from the rationale subgraph is invariant, which guarantees the
correct prediction result. However, most, if not all, of the existing
rationalization works on graph data develop their intervention strategies on
the graph level, which is coarse-grained. In this paper, we propose
well-tailored intervention strategies on graph data. Our idea is driven by the
development of Transformer models, whose self-attention module provides rich
interactions between input nodes. Based on the self-attention module, our
proposed invariant graph Transformer (IGT) can achieve fine-grained, more
specifically, node-level and virtual node-level intervention. Our comprehensive
experiments involve 7 real-world datasets, and the proposed IGT shows
significant performance advantages compared to 13 baseline methods.