Recently, Transformers for graph representation learning have become
increasingly popular, achieving state-of-the-art performance on a wide-variety
of datasets, either alone or in combination with message-passing graph neural
networks (MP-GNNs). Infusing graph inductive-biases in the innately
structure-agnostic transformer architecture in the form of structural or
positional encodings (PEs) is key to achieving these impressive results.
However, designing such encodings is tricky and disparate attempts have been
made to engineer such encodings including Laplacian eigenvectors, relative
random-walk probabilities (RRWP), spatial encodings, centrality encodings, edge
encodings etc. In this work, we argue that such encodings may not be required
at all, provided the attention mechanism itself incorporates information about
the graph structure. We introduce Eigenformer, which uses a novel
spectrum-aware attention mechanism cognizant of the Laplacian spectrum of the
graph, and empirically show that it achieves performance comparable to SOTA
MP-GNN architectures and Graph Transformers on a number of standard GNN
benchmark datasets, even surpassing the SOTA on some datasets. We also find
that our architecture is much faster to train in terms of number of epochs,
presumably due to the innate graph inductive biases.

Eigenformer 通过一种新颖的对 Laplacian 谱意识的注意机制，在一些标准的图神经网络基准数据集上实现了与最先进的 MP-GNN 体系结构和 Graph Transformers 相当的性能，甚至在某些数据集上超越了最先进的方法。此外，我们发现我们的架构在训练速度方面要快得多，可能是由于内在的图归纳偏置。