Graph transformers need strong inductive biases to derive meaningful
attention scores. Yet, current proposals rarely address methods capturing
longer ranges, hierarchical structures, or community structures, as they appear
in various graphs such as molecules, social networks, and citation networks. In
this paper, we propose a hierarchy-distance structural encoding (HDSE), which
models a hierarchical distance between the nodes in a graph focusing on its
multi-level, hierarchical nature. In particular, this yields a framework which
can be flexibly integrated with existing graph transformers, allowing for
simultaneous application with other positional representations. Through
extensive experiments on 12 real-world datasets, we demonstrate that our HDSE
method successfully enhances various types of baseline transformers, achieving
state-of-the-art empirical performances on 10 benchmark datasets.

本文提出了一种层次距离结构编码（HDSE）方法，用于加强现有图变换器，同时应用于其他位置表示，通过在图中的节点之间建模层次距离来捕捉图的多层次、分层结构，通过在 12 个真实世界数据集上的实验证明，我们的 HDSE 方法成功地提升了各种类型的基准变换器，在 10 个基准数据集上获得了最先进的实证性能。