@inproceedings{
li2023what,
title={What Improves the Generalization of Graph Transformer? A Theoretical Dive into Self-attention and Positional Encoding},
author={Hongkang Li and Meng Wang and Tengfei Ma and Sijia Liu and ZAIXI ZHANG and Pin-Yu Chen},
booktitle={NeurIPS 2023 Workshop: New Frontiers in Graph Learning},
year={2023},
url={https://openreview.net/forum?id=BaxFC3z9R6}
}
Graph Transformers, which incorporate self-attention and positional encoding, have recently emerged as a powerful architecture for various graph learning tasks. Despite their impressive performance, the complex non-convex interactions across layers and the recursive graph structure have made it challenging to establish a theoretical foundation for learning and generalization. This study introduces the first theoretical investigation of a shallow Graph Transformer for semi-supervised node classification, comprising a self-attention layer with relative positional encoding and a two-layer perception. Focusing on a graph data model with discriminative nodes that determine node labels and non-discriminative nodes that are class-irrelevant, we characterize the sample complexity required to achieve a zero generalization error by training with stochastic gradient descent (SGD). This paper provides the quantitative characterization of the sample complexity and number of iterations for convergence dependent on the fraction of discriminative nodes, the dominant patterns, the fraction of erroneous labels, and the initial model errors. Furthermore, we demonstrate that self-attention and positional encoding enhance generalization by making the attention map sparse and promoting the core neighborhood during training, which explains the superior feature representation of Graph Transformers. Our theoretical results are supported by empirical experiments on synthetic and real-world benchmarks.
What Improves the Generalization of Graph Transformer? A Theoretical Dive into Self-attention and Positional Encoding
Hongkang Li Meng Wang Tengfei Ma Sijia Liu ZAIXI ZHANG Pin-Yu Chen