  Despite that going deep has proven successful in many neural architectures,
the existing graph transformers are relatively shallow. In this work, we
explore whether more layers are beneficial to graph transformers, and find that
current graph transformers suffer from the bottleneck of improving performance
by increasing depth. Our further analysis reveals the reason is that deep graph
transformers are limited by the vanishing capacity of global attention,
restricting the graph transformer from focusing on the critical substructure
and obtaining expressive features. To this end, we propose a novel graph
transformer model named DeepGraph that explicitly employs substructure tokens
in the encoded representation, and applies local attention on related nodes to
obtain substructure based attention encoding. Our model enhances the ability of
the global attention to focus on substructures and promotes the expressiveness
of the representations, addressing the limitation of self-attention as the
graph transformer deepens. Experiments show that our method unblocks the depth
limitation of graph transformers and results in state-of-the-art performance
across various graph benchmarks with deeper models.
