Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The central part of the paper is the design of a learned positional encoding (LPE) that can be used in graph transformers in a similar way the positional encoding is used in text transformers. The authors propose to use eigenvalues and eigenfunctions to encode node positions in a graph, and demonstrate how to incorporate them into a transformer model that achieves high expressivity. The architectural choices are based on the theoretical introduction in which some concepts are borrowed from physics, such as the analogy to electric potential between nodes. The LPE is designed to address five principles that were overlooked by different methods. The authors also implement a new model, Spectral Attention Network (SAN), that utilizes the LPE resulting from the theoretical findings. The experimental results confirm the efficacy of the method.
main_review: The authors propose a novel learnable positional encoding and a new architecture, spectral attention network. The goal is to combat the problems of over-smoothing and over-squashing in graph neural networks and to increase expressivity. However, these problems are present in message passing or graph convolutional networks, and the authors do not elaborate on other graph transformers in this context in the work motivation. The correspondence between eigenvectors and sine functions is sketched in Section 2.1.1 An elegant physical explanation for the algorithmic decisions is provided. It is based on the Green's function and sheds new light on spectral graph theory and graph transformer architectures. The SAN architecture is an extension of the graph transformer proposed by Dwivedi and Bresson who also used Laplacian eigenvectors to encode node positions. However, their approach was much simpler and did not consider five principles raised by the authors of this paper -- they used $k$ smallest non-trivial vectors for each node.

The quality of the presented results is high. The performance metrics are calculated along with their error intervals based on 10 reruns of the model. The limitations of different elements of the architecture are described. The authors argue that their architecture is stronger than the Weisfeiler-Lehman isomorphism test and reduced over-squashing. However, there are some claims throughout the text that are not backed by any literature or experiments. For example in line 219: “Edge representations are not updated as it adds complexity with little to no performance gain”, or in line 254 "SAN model, which uses the Laplace spectrum more effectively, can learn to mimic the physical interactions presented in section 2.1.2". Is it confirmed by experiments?

Overall, the paper is clearly written and easy to follow. However I have some questions about Equations 1 and 2 since this is the source of the method motivation. Should not the Green's function be symmetric? $G$ is defined as the pseudo-inverse of the graph Laplacian, which is symmetric (for an undirected graph). By the definition of the generalized inverse, the inverse of the Laplacian would be
\begin{equation}
G(j_1, j_2) = \sum_{i>0} \frac{\phi_{i,j_1} \phi_{i,j_2}}{\lambda_i},
\end{equation}
but the derivation of Equation 1 is not immediately obvious for me. In [8] we see a similar formula (Equation 13), but this corresponds to the Laplace operator $\Delta$ which can be asymmetric, and even there the elements of $\phi_i$ are not squared. Am I missing something that is maybe related to the electric potential that was mentioned earlier? My other comments about the equations:
- In line 91, it probably should be said that $\hat{\phi}_{i,j}$ is the $j$-th **element** of the vector.
- $d_i$ is not defined.
- Should not the sum be over $i>0$ instead of $k>0$ in Equation 2?

The work is valuable from the perspective of the spectral graph theory research in deep learning. It can help to improve current graph transformer models. On the downside, only one graph transformer is used in the experiments. It would be interesting to see how SAN compares to the transformers that do not use the Laplacian eigenvectors as positional encoding. Additionally, in the caption of Figure 7, MoNet is mentioned as one of the architectures in the comparison, but the corresponding row is missing in the table. Another weak point of the experimental section is a relatively small range of tasks used. Maybe a task related to quantum chemistry would resonate well with the physical basis of the method.

Based on my above comments, I am leaning towards the rejection, but I am willing to change my rating if all the questions are addressed during the discussion period.
limitations_and_societal_impact: The limitations and societal impacts are described in the paper.
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: This paper proposes a learned position encoding mechanism which can fully make use of the eigenvalues and eigenvectors information from the graph Laplacian. The learned position encoding is then concatenated with the embedded node feature. In addition, the edge feature is also served as an input feature in order to completely leverage the graph structural information. Also, by fully connecting the graph, it helps tackle the common over-squashing problem in many GNNs. The paper also proposes an alternative version of attention so that real edges and added edges are taken into account separately when computing the attention. Eventually, the paper empirically tests the performance of the proposed model on real graph datasets.
main_review: 1.	The innovative architecture can make use of the full spectral information, while many spectral GNNs only adopt the eigenvectors of the Laplacian. Section 2.1.2 mentions the intuitions behind using full spectral information, which come from Laplacian’s green function and node distance measures. I enjoy reading about this part.
2.	The paper also summarizes some classical problems encountered by methods based on eigenfunctions. The proposed method can tackle most of them, except for the sign invariance of eigenvectors. This issue can be further solved if the edge learned position encoding is used.

limitations_and_societal_impact: 1.	As mentioned by the paper itself, a critical problem is the computational time complexity of the architecture, which requires $\mathcal{O}(N^{3})$ in order to generate node-wise embedding, or even $\mathcal{O}(N^{4})$ if the edge-wise embedding is leveraged. 
2.	Even though the results achieved by the proposed model is impressive, I encourage the authors to also test more on other well-known graph benchmark datasets, for example the OGB dataset, which exploits a more challenging splitting procedure and is similar to real-life application, or some datasets mentioned in [1].

[1] Errica, Federico, et al. "A fair comparison of graph neural networks for graph classification." arXiv preprint arXiv:1912.09893 (2019).
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper presents an interesting idea on designing a novel graph transformer with learning positional encoding by a spectral attention network (SAN) using the full Laplacian spectrum. Three theoretical limitations from previous efforts are overcome by this spectral attention, namely WL test and universality, over-squashing and physical interactions. Experimental results on four standard datasets demonstrate the effectiveness of the proposed SAN.
main_review: Strengths:

S1: It is important to properly define the positions of Transformers on graph structured data.
S2: The proposed method on using the full spectrum of Laplacian as positional encoding is simple yet effective, and the complementary theoretical analysis on the better properties brought by using spectrum is interesting and rooted in spectral graph theory.
S3: The paper is easy to follow with a clear motivation and closely related to the NeurIPS community with comprehensive experimental analysis.

Weaknesses:

W1: The novel is rather limited. The idea that using the spectrum of Laplacian as positional encoding is already proposed in the GT model as the authors stated, and certain properties of SAN, such as WL test and universality and reduced over-squashing, seem like that can also be achieved by the GT model with slight change on the design of structure.

W2: One important design is that SAN considers the variable # of eigenvectors by using a hyperparameter $m$. However, the choice of $m$ that splits the spectrum into two parts based on a hyper parameter seems not well-supported. In my view, the definition of low/high frequency components should at least have something to do with the actual distribution of eigenvalues, and not simply be based on a hard threshold on the eigenvalue index. This should be carefully discussed in the paper. 

W3: The reviews of previous works seem missing from both main paper and the Appendix. Some of the related works upon using the attention on the spectrum of Laplacian for both Transformer architecture [GTN and GT] and sparse message-passing models [1,2] should be discussed in details to demonstrate the novelty of proposed methods.

W4: For experiments, why there are so many missing results for baselines on MOLHIV dataset? This makes the role of this dataset a little meaningless. By the way, the statistics of datasets are missed. I noticed that the benchmarks used for evaluation are relatively small graphs, I would be curious about how the performance is on large graphs such as social networks.
[1] Dong, Y., Ding, K., Jalaian, B., Ji, S., & Li, J. (2021). Graph Neural Networks with Adaptive Frequency Response Filter. arXiv preprint arXiv:2104.12840.
[2] Chang, H., Rong, Y., Xu, T., Huang, W., Sojoudi, S., Huang, J., & Zhu, W. (2020). Spectral graph attention network. arXiv preprint arXiv:2003.07450.

limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This work proposes a transformer designed for graph structured data. As opposed to GNNs, the transformer allows non-neighboring nodes to communicate. To avoid loosing information on the structure of the graph, the transformer needs some form of structure encoding of the nodes, a non trivial problem for graphs. A common PE scheme consists in using the spectrum of the graphs Laplacian but, as detailed by the authors, this raises some issues. The authors propose an improved positional encoding circumventing these problems and demonstrate that a fully connected transformer is competitive with GNNs on four datasets.
main_review: This work is one of the first suggesting that transformers equipped with structure encoding can rival with GNNs, which are the de facto architecture for graph-structured data. The paper seems sounds although some points could be clarified (see below).

Pros:
- The authors carefully detail the issues related to using the spectrum of the Laplacian as node positional encoding in a transformer, making interesting observations and proposing a solution.
- SAN performs experimentally well.

Cons:
- It is claimed in the main paper (l254) that the model is able to capture long-distance interactions, but as far as I understand there are no experiments supporting this.
- Do eigenvectors of different Laplacians (i.e of different graphs) belong to a similar space, hence can they really be "compared" as done in your method? What is your view on this?
- One or two more datasets would be welcomed to better understand how does SAN compare to GNNs, for example a small scale such as NCI1 and larger scale such as OGBG-MolPCBA.
- As mentioned by the authors, the sign flip is not avoided by the proposed method unless paying a price of $O(N^4)$ ($N$ being the number of nodes in the graph).

Questions and remarks:
- Wouldn't have been also possible to simply pad eigenvectors of the Laplacian and project the position encodings to a new space to respectively solve the "Variable number of eigenvectors problem" and "Multiplicities" problems? 
- How is $m$ selected in practice? 
- l155: minor typo but I am not sure we can talk about the "eigenfunction of a node".
limitations_and_societal_impact: Both are adressed by the authors.
review_title: null

Meta-review: In this paper, a learned positional encoding (LPE) based on  eigenvalues and eigenvectors information from the graph Laplacian is designed to make Transformer work better on graph data. Experimental results show that the proposed method is effective on several important tasks. Most reviewers see the technical value of the paper, and agree that using graph Laplacian in the learning of positional encoding is a good idea. On the other hand, some concerns have been raised, mainly regarding the computational complexity and the completeness of the experimental results. The authors did a good job in providing their rebuttals, and after several rounds of discussions, the reviewers came to a consensus on the positive side. As a result, my recommendation is ACCEPT as a poster.
Decision: Accept (Poster)