Bridging Graph Position Encodings for Transformers with Weighted Graph-Walking Automata
Not on the map. Why?
Abstract (arXiv)
A current goal in the graph neural network literature is to enable transformers to operate on graph-structured data, given their success on language and vision tasks. Since the transformer's original sinusoidal positional encodings (PEs) are not applicable to graphs, recent work has focused on developing graph PEs, rooted in spectral graph theory or various spatial features of a graph. In this work, we introduce a new graph PE, Graph Automaton PE (GAPE), based on weighted graph-walking automata (a novel extension of graph-walking automata). We compare the performance of GAPE with other PE schemes on both machine translation and graph-structured tasks, and we show that it generalizes several other PEs. An additional contribution of this study is a theoretical and controlled experimental comparison of many recent PEs in graph transformers, independent of the use of edge features.
Key facts. Cited by 1 paper in the map (data through 14 Oct 2026). Builds on 23 of its 44 references that are in the map. First posted on arXiv 13 Dec 2022.
Builds on
23 of 44 references.
References · 23
- 2017Attention Is All You Needcited by 60,361
- 2014Adam: A Method for Stochastic Optimizationcited by 37,240
- 2019PyTorch: An Imperative Style, High-Performance Deep Learning Librarycited by 20,305
- 2018How Powerful are Graph Neural Networks?cited by 4,393
- 2021Geometric Deep Learning: Grids, Groups, Graphs, Geodesics, and Gaugescited by 1,167
- 2018Self-Attention with Relative Position Representationscited by 1,120
- 2013Exact solutions to the nonlinear dynamics of learning in deep linear neural networkscited by 763
- 2020Benchmarking Graph Neural Networkscited by 680
- 2020A Generalization of Transformer Networks to Graphscited by 661
- 2021Rethinking Graph Transformers with Spectral Attentioncited by 473
- 2021Graph Neural Networks with Learnable Structural and Positional Representationscited by 333
- 2021OGB-LSC: A Large-Scale Challenge for Machine Learning on Graphscited by 329
11 more
- 2021Do Transformers Really Perform Bad for Graph Representation?cited by 320
- 2017Community Detection and Stochastic Block Modelscited by 319
- 2018Music Transformercited by 211
- 2019What graph neural networks cannot learn: depth vs widthcited by 201
- 2019On the equivalence between graph isomorphism testing and function approximation with GNNscited by 172
- 2019Relational Pooling for Graph Representationscited by 150
- 2021GraphiT: Encoding Graph Structure in Transformerscited by 147
- 2021MagNet: A Neural Network for Directed Graphscited by 107
- 2021Convergent Graph Solverscited by 12
- 2016Approximate Personalized PageRank on Dynamic Graphscited by 11
- 2020Learning Graph Structure With A Finite-State Automaton Layercited by 10
Built on by
Citing papers per year: 2026: 1.
1 paper.