TL;DR
This paper introduces LGI-GT, a novel graph transformer architecture that interleaves local graph neural network (GNN) operations with global Transformer layers. This approach effectively addresses the over-smoothing and over-squashing issues common in GNNs while leveraging the strengths of Transformers for graph representation learning, achieving state-of-the-art results across various benchmarks.
What Problem Does This Paper Address?
Graph Neural Networks (GNNs) have shown great success in learning representations from graph-structured data. However, they suffer from critical limitations like over-smoothing (node representations becoming indistinguishable in deep networks), over-squashing (information from large receptive fields being compressed), and limited expressiveness. While Transformers have emerged as powerful models, adapting them to graphs (Graph Transformers or GTs) is challenging. Existing GTs often fall into two categories: Type I, which integrates graph structure into standard Transformers, and Type II, which combines GNNs and Transformers. The paper argues that existing Type II approaches, such as stacking GNNs and Transformers sequentially (GNN+Transformer) or running them in parallel, fail to fully utilize local and global information. This paper aims to bridge this gap by proposing an interleaved architecture that better fuses local and global graph information.
Methods
The core innovation is the LGI-GT (Local and Global Operators Interleaving Graph Transformer) architecture. It's built upon an LGI-Block, which alternates between local operators (GNN layers, referred to as GConvs) and global operators (Transformer layers, referred to as TLayers). This interleaving allows for a more effective fusion of information from local neighborhoods and global graph structures.
Key novelties include:
- Interleaving Architecture: Instead of stacking GNNs then Transformers, or running them in parallel, LGI-GT alternates them within each block. This is hypothesized to mitigate over-smoothing by allowing TLayers to refine node embeddings that are already locally processed by GConvs.
- [CLS] Token Propagation: A new method for propagating the special
[CLS]token embedding is introduced. This token skips GConv layers and only participates in TLayer updates, allowing it to act as a global graph representation without being affected by local GNN operations. - EELA (Edge Enhanced Local Attention): A novel message-passing module designed as a local operator. EELA enhances local attention by incorporating edge features into the attention mechanism, making LGI-GT a "full-attention" model where both local and global operations are attention-based.
Datasets
The paper evaluates LGI-GT on a variety of datasets for both node-level and graph-level tasks:
- Graph Regression: ZINC
- Node Classification: PATTERN, CLUSTER
- Multi-task Binary Graph Classification: ogbg-molpcba
- Code Summarization (Graph-level): ogbg-code2
- Additional smaller datasets for specific comparisons: NCI1, NCI109, ogbg-molbbbp, ogbg-moltox21
Key Insights and Ideas
- Interleaving is Key: The paper strongly suggests that the effectiveness of GTs lies not just in combining GNNs and Transformers, but in how they are combined. The interleaved approach of LGI-GT appears to be more robust to model depth and better at capturing discriminative node features compared to sequential or parallel combinations.
- [CLS] Token as a Global Summarizer: The dedicated propagation strategy for the
[CLS]token allows it to effectively capture global graph properties without being diluted by local GNN operations. - Full Attention Matters: The introduction of EELA, which integrates edge features into local attention, contributes to LGI-GT's performance by enabling a more comprehensive local information aggregation.
- Addressing GNN Limitations: The proposed architecture directly tackles the over-smoothing and over-squashing problems by allowing for deeper models and better information flow.
Key Results
- State-of-the-Art Performance: LGI-GT consistently outperforms existing state-of-the-art GNNs and GTs across 5 benchmark datasets (ZINC, PATTERN, CLUSTER, ogbg-molpcba, ogbg-code2) on various tasks.
- Robustness to Depth: Unlike GNN+Transformer and parallel GT schemes, LGI-GT's performance remains stable or improves as model depth increases, indicating its resilience to over-smoothing.
- Effectiveness of EELA: Ablation studies show that EELA contributes significantly to the performance of LGI-GT, outperforming other attention-based local modules like GATConv and TransformerConv.
- Model Interpretation: Visualizations of attention weights show that LGI-GT's
[CLS]token focuses on important atoms and connections, highlighting its ability to capture relevant structural information.
Limitations and Future Work
- Computational Cost: While not explicitly detailed as a limitation, the use of Transformer layers inherently increases computational complexity compared to pure GNNs.
- Dataset Specificity: The paper focuses on specific types of graph tasks and datasets. Further validation on a wider range of graph structures and tasks would be beneficial.
- Future Work: The authors suggest that their LGI scheme is flexible and can be extended by incorporating other GNN modules or PE/SE methods. The potential for further exploration of different interleaving strategies and attention mechanisms is implied.
Summary updated