SGFormer: Simplifying and Scaling Graph Transformers with Single-Layer Attention and Approximation-Free Linear...

Area of Science:

• Graph Representation Learning
• Machine Learning on Large-Scale Data
• Transformer Architectures

Background:

• Learning representations on large graphs is challenging due to complex interdependencies.
• Existing Transformer models, while effective on small graphs, face scalability issues on larger datasets due to deep attention layers and partitioning difficulties.
• The necessity of deep attention in graph Transformers requires theoretical reassessment.

Purpose of the Study:

• To theoretically investigate the necessity of deep attention layers in graph Transformers.
• To propose a simplified, scalable Transformer architecture for large-graph learning.
• To achieve efficient and accurate representation learning on web-scale graphs.

Main Methods:

• Theoretical analysis of hybrid propagation layers combining global attention and graph-based propagation.
• Development of the Simplified Single-Layer Graph Transformer (SGFormer) architecture.
• Empirical evaluation on medium-sized graphs and the web-scale ogbn-papers100M dataset.

Main Results:

• Demonstrated that multi-layer graph Transformers can be reduced to single-layer counterparts without loss of representation capacity.
• SGFormer achieves approximation-free linear complexity, scaling linearly with graph size.
• Achieved orders-of-magnitude inference acceleration and smooth scaling to web-scale graphs on a single GPU.

Conclusions:

• Principled simplification is a viable strategy for developing powerful, scalable foundation models for large-graph learning.
• SGFormer provides an efficient and effective solution for Transformer-based large-graph representation learning.
• The findings challenge the conventional deep-layer design for Transformers in graph learning contexts.