ParaFormer: A Generalized PageRank Graph Transformer for Graph Representation Learning
ParaFormer integrates PageRank-enhanced attention to mitigate over-smoothing in deep graph transformers, achieving superior results on large-scale datasets.
Key Findings
Methodology
This paper introduces ParaFormer, which incorporates PageRank principles into the Transformer attention mechanism, creating a Generalized PageRank Attention (GPA) module. Theoretically, GPA acts as an adaptive filter balancing low- and high-frequency signals, mitigating over-smoothing. An efficient linear approximation algorithm is proposed to handle large graphs. Extensive experiments on 11 node classification and 2 graph classification datasets demonstrate that ParaFormer outperforms state-of-the-art models, especially in deep architectures, by effectively capturing global dependencies while preserving node distinctions.
Key Results
- On datasets like Cora and PubMed, ParaFormer improves accuracy by 2-3% over baselines, especially in deeper layers where over-smoothing is prominent. In large-scale graphs with millions of nodes, it maintains high node discriminability and stability, outperforming GAT and vanilla Transformers.
- In heterophilic graphs such as Recommendation systems, the model captures long-range dependencies better, leading to significant performance gains.
- Ablation studies confirm the importance of GPR attention in alleviating over-smoothing, and the linear approximation maintains performance with reduced computational cost.
Significance
This work addresses a fundamental challenge in deep graph learning: how to leverage deep architectures without succumbing to over-smoothing. By integrating PageRank into attention, it offers a theoretically grounded, scalable solution that enhances the capacity of graph transformers to model complex, large-scale graphs. The approach bridges the gap between global information capture and local feature preservation, with broad implications for social networks, recommendation systems, and knowledge graphs, pushing the frontier of scalable, deep graph representation learning.
Technical Contribution
The paper introduces a novel PageRank-based attention mechanism that functions as an adaptive, frequency-aware filter. Theoretical analysis proves its ability to control over-smoothing and model high-frequency signals. A linear complexity approximation makes the method scalable to large graphs. The fusion of local GNN features with global PageRank signals enhances expressiveness. These contributions collectively extend the theoretical understanding of graph transformers and open new avenues for deep, scalable graph models.
Novelty
This is the first work to embed PageRank principles directly into Transformer attention for graphs, creating a Generalized PageRank Attention that adaptively balances low- and high-frequency information. The linear approximation algorithm significantly improves scalability, enabling application to graphs with millions of nodes. Theoretical analysis confirms the model's ability to act as an adaptive filter, setting it apart from existing low-pass or high-pass graph filters.
Limitations
- The model relies on hyperparameters like PageRank damping factor and weights, which may require careful tuning for different graph types.
- Performance in highly dynamic or extremely sparse graphs remains to be validated.
- Training deep models still incurs high computational costs, especially for very large graphs.
Future Work
Future research will explore adaptive, data-driven tuning of PageRank parameters, extend the framework to dynamic and heterogeneous graphs, and develop more efficient approximation algorithms. Combining this approach with pretraining and transfer learning could further enhance its applicability in real-world scenarios, such as real-time recommendation or large-scale knowledge graph reasoning.
AI Executive Summary
Graph neural networks have revolutionized the way we model complex relationships in data, yet deep architectures often suffer from over-smoothing, where node representations become indistinguishable, undermining their effectiveness. Transformer models, with their all-pair attention, promise a solution by capturing global information, but they inherently act as low-pass filters, exacerbating the over-smoothing problem when stacked deeply. This challenge limits the potential of deep graph transformers, especially on large-scale and heterophilic graphs.
In response, this paper presents ParaFormer, a novel graph transformer architecture that integrates PageRank principles into the attention mechanism. The core innovation, Generalized PageRank Attention (GPA), adaptively balances low- and high-frequency signals, functioning as an intelligent filter that preserves node distinctions while capturing long-range dependencies. The model also employs a scalable linear approximation algorithm, making it feasible for graphs with millions of nodes.
Theoretical analysis confirms that ParaFormer acts as an adaptive-pass filter, effectively mitigating over-smoothing and maintaining high-frequency information crucial for heterophilic graphs. Extensive experiments across diverse datasets, including citation networks, Wikipedia graphs, and large recommendation graphs, demonstrate consistent performance improvements over existing GNNs and graph transformers. Notably, on large-scale datasets, ParaFormer achieves accuracy gains of 2-3%, validating its scalability and robustness.
This work significantly advances the understanding of frequency properties in graph transformers, offering a scalable, theoretically grounded solution to the over-smoothing dilemma. Its broad applicability promises to impact various domains, from social network analysis to industrial recommendation systems. Future directions include dynamic parameter tuning, extension to heterogeneous and evolving graphs, and integration with pretraining techniques, aiming to push the boundaries of deep, scalable graph representation learning.
Deep Dive
Limitations & Outlook
What gaps remain?
Abstract
Graph Transformers (GTs) have emerged as a promising graph learning tool, leveraging their all-pair connected property to effectively capture global information. To address the over-smoothing problem in deep GNNs, global attention was initially introduced, eliminating the necessity for using deep GNNs. However, through empirical and theoretical analysis, we verify that the introduced global attention exhibits severe over-smoothing, causing node representations to become indistinguishable due to its inherent low-pass filtering. This effect is even stronger than that observed in GNNs. To mitigate this, we propose PageRank Transformer (ParaFormer), which features a PageRank-enhanced attention module designed to mimic the behavior of deep Transformers. We theoretically and empirically demonstrate that ParaFormer mitigates over-smoothing by functioning as an adaptive-pass filter. Experiments show that ParaFormer achieves consistent performance improvements across both node classification and graph classification tasks on 11 datasets ranging from thousands to millions of nodes, validating its efficacy. The supplementary material, including code and appendix, can be found in https://github.com/chaohaoyuan/ParaFormer.