  Graph Transformer, due to its global attention mechanism, has emerged as a
new tool in dealing with graph-structured data. It is well recognized that the
global attention mechanism considers a wider receptive field in a fully
connected graph, leading many to believe that useful information can be
extracted from all the nodes. In this paper, we challenge this belief: does the
globalizing property always benefit Graph Transformers? We reveal the
over-globalizing problem in Graph Transformer by presenting both empirical
evidence and theoretical analysis, i.e., the current attention mechanism overly
focuses on those distant nodes, while the near nodes, which actually contain
most of the useful information, are relatively weakened. Then we propose a
novel Bi-Level Global Graph Transformer with Collaborative Training
(CoBFormer), including the inter-cluster and intra-cluster Transformers, to
prevent the over-globalizing problem while keeping the ability to extract
valuable information from distant nodes. Moreover, the collaborative training
is proposed to improve the model's generalization ability with a theoretical
guarantee. Extensive experiments on various graphs well validate the
effectiveness of our proposed CoBFormer.
