  The recent works proposing transformer-based models for graphs have proven
the inadequacy of Vanilla Transformer for graph representation learning. To
understand this inadequacy, there is a need to investigate if spectral analysis
of the transformer will reveal insights into its expressive power. Similar
studies already established that spectral analysis of Graph neural networks
(GNNs) provides extra perspectives on their expressiveness. In this work, we
systematically study and establish the link between the spatial and spectral
domain in the realm of the transformer. We further provide a theoretical
analysis and prove that the spatial attention mechanism in the transformer
cannot effectively capture the desired frequency response, thus, inherently
limiting its expressiveness in spectral space. Therefore, we propose FeTA, a
framework that aims to perform attention over the entire graph spectrum (i.e.,
actual frequency components of the graphs) analogous to the attention in
spatial space. Empirical results suggest that FeTA provides homogeneous
performance gain against vanilla transformer across all tasks on standard
benchmarks and can easily be extended to GNN-based models with low-pass
characteristics (e.g., GAT).
