Hybrid Focal and Full-Range Attention Based Graph Transformers

Abstract

The paradigm of Transformers using the self-attention mechanism has manifested its advantage in learning graph-structured data. Yet, Graph Transformers are capable of modeling full range dependencies but are often deficient in extracting information from locality. A common practice is to utilize Message Passing Neural Networks (MPNNs) as an auxiliary to capture local information, which however are still inadequate for comprehending substructures. In this paper, we present a purely attention-based architecture, namely Focal and Full-Range Graph Transformer (FFGT), which can mitigate the loss of local information in learning global correlations. The core component of FFGT is a new mechanism of compound attention, which combines the conventional full-range attention with K-hop focal attention on ego-nets to aggregate both global and local information. Beyond the scope of canonical Transformers, the FFGT has the merit of being more substructure-aware. Our approach enhances the performance of existing Graph Transformers on various open datasets, while achieves compatible SOTA performance on several Long-Range Graph Benchmark (LRGB) datasets even with a vanilla transformer. We further examine influential factors on the optimal focal length of attention via introducing a novel synthetic dataset based on SBM-PATTERN.

References in corpus (22)

• An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale
• Self-Supervised Graph Transformer on Large-Scale Molecular Data
• A Generalization of Transformer Networks to Graphs
• Residual Gated Graph ConvNets
• Recipe for a General, Powerful, Scalable Graph Transformer
• Graph-Bert: Only Attention is Needed for Learning Graph Representations
• Representing Long-Range Context for Graph Neural Networks with Global Attention
• Global Self-Attention as a Replacement for Graph Convolution
• Transformer for Graphs: An Overview from Architecture Perspective
• Pure Transformers are Powerful Graph Learners
• Subgraph Neural Networks
• How Powerful are K-hop Message Passing Graph Neural Networks
• Attending to Graph Transformers
• Long Range Graph Benchmark
• Gophormer: Ego-Graph Transformer for Node Classification
• Understanding and Extending Subgraph GNNs by Rethinking Their Symmetries
• Graph Inductive Biases in Transformers without Message Passing
• Multiresolution Graph Transformers and Wavelet Positional Encoding for Learning Hierarchical Structures
• Your Transformer May Not be as Powerful as You Expect
• Improving the Expressiveness of $K$-hop Message-Passing GNNs by Injecting Contextualized Substructure Information
• Exphormer: Sparse Transformers for Graphs
• Self-Attention in Colors: Another Take on Encoding Graph Structure in Transformers