# Graph Transformers Dream of Electric Flow

arXiv: https://arxiv.org/abs/2410.16699 · HTML: https://mlsanity.com/paper/2410.16699/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 24 of its 47 references that are in the map.
- First posted on arXiv 22 Oct 2024.

## Builds on (most cited first, 24 of 24)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Transformers learn in-context by gradient descent](https://mlsanity.com/paper/2212.07677/) (2022)
- [Recipe for a General, Powerful, Scalable Graph Transformer](https://mlsanity.com/paper/2205.12454/) (2022)
- [Benchmarking Graph Neural Networks](https://mlsanity.com/paper/2003.00982/) (2020)
- [A Generalization of Transformer Networks to Graphs](https://mlsanity.com/paper/2012.09699/) (2020)
- [Graph Transformer Networks](https://mlsanity.com/paper/1911.06455/) (2019)
- [Linear Transformers Are Secretly Fast Weight Programmers](https://mlsanity.com/paper/2102.11174/) (2021)
- [Rethinking Graph Transformers with Spectral Attention](https://mlsanity.com/paper/2106.03893/) (2021)
- [Graph Neural Networks with Learnable Structural and Positional Representations](https://mlsanity.com/paper/2110.07875/) (2021)
- [Pure Transformers are Powerful Graph Learners](https://mlsanity.com/paper/2207.02505/) (2022)
- [Sign and Basis Invariant Networks for Spectral Graph Representation Learning](https://mlsanity.com/paper/2202.13013/) (2022)
- [Graph Inductive Biases in Transformers without Message Passing](https://mlsanity.com/paper/2305.17589/) (2023)
- [GraphiT: Encoding Graph Structure in Transformers](https://mlsanity.com/paper/2106.05667/) (2021)
- [Rethinking the Expressive Power of GNNs via Graph Biconnectivity](https://mlsanity.com/paper/2301.09505/) (2023)
- [Attending to Graph Transformers](https://mlsanity.com/paper/2302.04181/) (2023)
- [GRPE: Relative Positional Encoding for Graph Transformer](https://mlsanity.com/paper/2201.12787/) (2022)
- [Linear algebra with transformers](https://mlsanity.com/paper/2112.01898/) (2021)
- [Graph Convolutional Networks using Heat Kernel for Semi-supervised Learning](https://mlsanity.com/paper/2007.16002/) (2020)
- [From block-Toeplitz matrices to differential equations on graphs: towards a general theory for scalable masked Transformers](https://mlsanity.com/paper/2107.07999/) (2021)
- [Transformers Generalize DeepSets and Can be Extended to Graphs and Hypergraphs](https://mlsanity.com/paper/2110.14416/) (2021)
- [Graph Positional Encoding via Random Feature Propagation](https://mlsanity.com/paper/2303.02918/) (2023)
- [Comparing Graph Transformers via Positional Encodings](https://mlsanity.com/paper/2402.14202/) (2024)
- [Affinity-Aware Graph Networks](https://mlsanity.com/paper/2206.11941/) (2022)
- [An Efficient Parallel Solver for SDD Linear Systems](https://mlsanity.com/paper/1311.3286/) (2013)

## Built on by (most cited first, 2 of 2)

- [Generalizable Insights for Graph Transformers in Theory and Practice](https://mlsanity.com/paper/2511.08028/) (2025)
- [In-Context Semi-Supervised Learning](https://mlsanity.com/paper/2512.15934/) (2025)

## Abstract (arXiv)

We show theoretically and empirically that the linear Transformer, when applied to graph data, can implement algorithms that solve canonical problems such as electric flow and eigenvector decomposition. The Transformer has access to information on the input graph only via the graph's incidence matrix. We present explicit weight configurations for implementing each algorithm, and we bound the constructed Transformers' errors by the errors of the underlying algorithms. Our theoretical findings are corroborated by experiments on synthetic data. Additionally, on a real-world molecular regression task, we observe that the linear Transformer is capable of learning a more effective positional encoding than the default one based on Laplacian eigenvectors. Our work is an initial step towards elucidating the inner-workings of the Transformer for graph data. Code is available at https://github.com/chengxiang/LinearGraphTransformer