Graph Transformers Dream of Electric Flow
Transformer;Graph Neural Network
Yes
No ethics review needed.
Please address the points raised in the previous section.
**Originality**: This paper introduces a novel use of a linear Transformer, to perform core graph algorithms like electric flow and eigenvector decomposition without explicit positional encodings. 

**Quality**: The paper offers rigorous theoretical analysis with explicit weight constructions and error bounds for each algorithm.

**Clarity**: The paper is well-organized, clearly written, and enjoyable to read.
The paper investigates the capabilities of the linear Transformer when applied to graph data, particularly its ability to implement algorithms for core graph tasks without explicit positional encodings. The authors demonstrate that the linear Transformer, which uses the graph incidence matrix as input, can solve canonical problems like electric flow computation and eigenvector decomposition. Key contributions include explicit configurations for weight matrices, error bounds for each task, and empirical results validating theoretical findings on synthetic data.
1. Since the paper’s contribution is primarily theoretical, providing a proof sketch under the main results would be highly beneficial. Additionally, a more detailed description of the weight matrices would enhance clarity.

2. The theoretical results are not particularly surprising given the use of a linear Transformer. Could these results also apply to GNNs?

3. The practical impact of the proposed approach is unclear, as the empirical results are limited compared to numerous existing works. For instance, the performance on the ZINC dataset is significantly lower than the state-of-the-art, with an error approximately twice as large.
Yes
No ethics review needed.
- How would the analysis be impacted if nonlinearity in self-attention was re-introduced? In order to "understand, at a mechanistic level, how the Transformer processes graph-structured data" (lines 32-33), we are expected to remove only non-essential elements of Transformer architecture (and nonlinearity seems to be a critical one). The linearity in the Transformer, means that if its operations are expanded for a number of layers we'll reduce to a simple matrix operator.
- The idea is novel and appealing: using a transformer to compute the solution to a graph problem as part of the latent vectors in its node output representations adds another level of applicability of transformers well beyond language understanding or generation.

- Lemmas are well organized, follow similar themes and the narrative is smooth and clear.
The authors introduce a simplified (linear) Transformer architecture (no softmax activation in self-attention layers) and use it to show (theoretically and empirically) that it can implement graph algorithms. In particular they present a series of lemmas providing bounds in approximating the solution to problems like flow and heat kernel computation, finding resistive embeddings and performing eigenvalue decomposition (assuming specific weight matrices). Their input encodings include the incidence matrix representation of the graph and then the approximate solution will land in a subset of columns in the output encodings' matrix,  after passing through a a number L of transformer layers (where L is decided by the target approximation error). A parameter efficient variant is also presented. The linear transformer is tested on a series of small graph instances of the problems (e.g. of the order of 10 nodes and 20 edges) and for learning a positional encoding (PE) for a molecular regression task.
- Removing the nonlinear softmax terms from standard transformer architecture, facilitates analysis but severely impacts the power of the model.

- Complexity of the approach is prohibitive: it can be O(n^4) and this explains their experimentation with very small synthetic graphs. Parameter efficient implementation is promising, but still the original idea is far from being scalable and thus practically testable beyond a couple of tens' of graph nodes.
Yes
No ethics review needed.
Q1. Can you elaborate on the practical implications of your findings (see W1)?

Q2. I think the eigenvectors you converge to have sign/basis ambiguities derived from the choice of $\Phi_0$. How do you deal with these ambiguities? Do you perform sign flipping at every forward pass?

Q3. I think denoting by $d$ the number of edges (Line 128) is a bit confusing, because $d$ is usually the embedding dimension. Also, in Equation 1, since $j= 1, \ldots, d$ is the first index of $B$, I think $B \in \mathbb{R}^{d \times n }$, but you wrote $B \in \mathbb{R}^{n \times d }$ (Line 132). Please clarify.
The results are interesting. I particularly appreciated the structure of the paper, in which experimental results are shown after their corresponding theoretical claims instead of having them all the end, which highlights the connection between the presented theory and the experimental results.
The paper shows that Linear Transformers (and their variant) using the incidence matrix can implement canonical problems, such as electric flow and subspace iteration. While the contribution is mainly theoretical, the authors also empirically validate their findings, and further show that on existing molecular datasets the linear transformer is capable of learning better performing positional encodings than standard laplacian eigenvectors.
W1. Generally speaking, I think the impact of the paper tends to be a bit limited. This is especially true because the considered architecture (linear Transformers), and in particular its variant which includes an L2 normalization, is not widely used. The main implication I can see is to use the variant of the linear transformer in place of existing predefined positional encodings, and therefore as an additional component of a bigger architecture.


W2. I find a bit confusing that the authors claim that the input to the Transformer is only the graph incidence matrix, without any other positional encoding (Lines 11-13), while for instance for the subspace iteration $\Phi_0$ is required to be some arbitrary column-orthogonal matrix. I think -- depending on the graph -- $\Phi_0$ might need to be a positional encoding to ensure all columns are orthogonal (note that if $\Phi_0$ is a random matrix then it is a positional encoding [Srinivasan and Ribeiro, 2020]). I think the authors need to clarify this point and adjust accordingly in the entire paper.


Srinivasan and Ribeiro, 2020. On the Equivalence between Positional Node Embeddings and Structural Graph Representations.
Yes
No ethics review needed.
* While the paper concerns two graph problems: electric flow and Laplacian eigenvector decomposition, why the title mentions only the first one?
* The organisation of the paper is clear, it's easy to understand the main contribution of the paper. And mathematically, it's generally well-written.
* The idea of solving the traditional graph problem with a Transformer is novel. 
* For the proposed lemmas, the paper provides the relevant experiments which are quite nice.
The papers show theoretically and empirically that the linear transformer can approximate the hypothesis function space of several graph problem (electric flow and Laplacian eigenvector decomposition). The authors also conduct a real-world experiment on molecular regression, in which positional encoding outputs by transformers are adopted.
* My main concern is that since the neural network is a universe approximator, it's not surprising that it (in this paper, even it concerns linear Transformer, which is more like in a polynomial function) can solve approximate the hypothesis function space of several graph problems. I wonder how the lemmas shown in the paper can provide us with more useful information.
* The paper lacks a conclusion section.
* The real-world experiment concerns only the Laplacian eigenvector decomposition, it would be nice to have another for the electric flow.
* See the questions.
we provide simple constructions showing how linear Transformers can learn to solve a number of canonical graph problems, with practical implications for learning positional encodings.
@inproceedings{
anonymous2024graph,
title={Graph Transformers Dream of Electric Flow},
author={Anonymous},
booktitle={Submitted to The Thirteenth International Conference on Learning Representations},
year={2024},
url={https://openreview.net/forum?id=rWQDzq3O5c},
note={under review}
}
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 input to the Transformer is simply the graph incidence matrix; no other explicit positional encoding information is provided. We present explicit weight configurations for implementing each algorithm, and we bound the constructed Transformers' errors by the errors of the underlying algorithms. We verify our theoretical findings experimentally on synthetic data. Additionally, on a real-world molecular regression task, we observe that the linear Transformer is capable of learning a better 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.
I certify that there is no URL (e.g., github page) that could be used to find authors’ identity.
I acknowledge that I and all co-authors of this work have read and commit to adhering to the ICLR Code of Ethics.
Transformer Graph Neural Network
I certify that there is no acknowledgement section in this submission for double blind review.
/pdf/88ff8f06efbbda23ed873e23daed9d0cda53b993.pdf
learning on graphs and other geometries & topologies
I understand the reciprocal reviewing requirement as described on https://iclr.cc/Conferences/2025/CallForPapers. If none of the authors are registered as a reviewer, it may result in a desk rejection at the discretion of the program chairs. To request an exception, please complete this form at https://forms.gle/Huojr6VjkFxiQsUp6.
I certify that this submission complies with the submission instructions as described on https://iclr.cc/Conferences/2025/AuthorGuide.
Graph Transformers Dream of Electric Flow
ICLR 2025 Conference Submission
ICLR.cc/2025/Conference/Submission