Deformable Graph Transformer.

Area of Science:

• Graph Neural Networks
• Machine Learning
• Artificial Intelligence

Background:

• Transformer models show promise for graph representation learning.
• Full attention mechanisms in transformers lead to quadratic complexity, limiting scalability to large graphs.
• Message aggregation from irrelevant nodes further hinders performance on complex graph structures.

Purpose of the Study:

• To propose a novel transformer-based model, Deformable Graph Transformer (DGT), for efficient and scalable graph representation learning.
• To overcome the computational limitations of existing transformer models on large-scale graphs.
• To enhance the performance of graph representation learning by focusing on relevant nodes.

Main Methods:

• Developed Deformable Graph Transformer (DGT) employing sparse attention.
• Constructed multiple node sequences considering structural and semantic proximity.
• Integrated learnable Katz Positional Encodings to enhance sparse attention mechanisms.
• Achieved linear complexity concerning the number of nodes for efficient computation.

Main Results:

• DGT demonstrated superior performance across 7 graph benchmark datasets.
• Achieved significant computational cost reduction, 2.5 to 449 times less than full attention transformer models.
• Successfully handled large-scale graphs efficiently through sparse attention.

Conclusions:

• Deformable Graph Transformer (DGT) offers an efficient and scalable solution for representation learning on large-scale graphs.
• The proposed sparse attention mechanism effectively reduces computational complexity while improving performance.
• DGT represents a significant advancement over existing transformer-based graph models.