Deformable Graph Transformer
This addresses the problem of scaling transformer models to large graphs for researchers and practitioners in graph machine learning, representing a novel method rather than an incremental improvement.
The paper tackles the computational inefficiency of transformer models on large-scale graphs by proposing Deformable Graph Transformer (DGT), which uses sparse attention to achieve state-of-the-art performance on 7 benchmark datasets with 2.5 to 449 times less computational cost.
Transformer-based models have recently shown success in representation learning on graph-structured data beyond natural language processing and computer vision. However, the success is limited to small-scale graphs due to the drawbacks of full dot-product attention on graphs such as the quadratic complexity with respect to the number of nodes and message aggregation from enormous irrelevant nodes. To address these issues, we propose Deformable Graph Transformer (DGT) that performs sparse attention via dynamically sampled relevant nodes for efficiently handling large-scale graphs with a linear complexity in the number of nodes. Specifically, our framework first constructs multiple node sequences with various criteria to consider both structural and semantic proximity. Then, combining with our learnable Katz Positional Encodings, the sparse attention is applied to the node sequences for learning node representations with a significantly reduced computational cost. Extensive experiments demonstrate that our DGT achieves state-of-the-art performance on 7 graph benchmark datasets with 2.5 - 449 times less computational cost compared to transformer-based graph models with full attention.