Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: The authors of the paper claim that Transformers can be as expressive as graph-invariant networks by applying them directly to a graph and treating all nodes and edges in the graph as tokens. Using appropriate node and type identifiers, self-attention can approximate any permutation equivariant linear operator in the graph. Orthogonal random features and Laplacian feature vectors for node identifiers are proposed. The final proposed model, Soft Graph Transformer (SGT), achieves performance improvements over the GNN baseline on the PCQM4Mv2 dataset.
strengths_and_weaknesses: Strengths: 
1. It is novel to treat nodes and edges as input tokens to Transformers and add node and type identifiers.
2. It is shown that SGT is as expressive as 2-IGN with equivariant linear layers.

Weakness: 
1. Evaluate on only one graph dataset.
questions: 1. Are node and type identifiers learned?
limitations: 1. Evaluate on only one graph dataset.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper proposes a variant of graph transformers, the Soft Graph Transformer (SGT). In particular, all nodes and edges are simply treated as independent tokens, and then they are augmented with token embedding. The authors prove this approach is theoretically at least as expressive as an invariant graph network, which is already more expressive than all message-passing graph neural networks. SGT performs significantly better than all GNNs and is competitive with Transformer variants with strong graph-specific architectural components.
strengths_and_weaknesses: Strengths:
The motivation is clear. This paper proposes an approach of applying a standard Transformer directly for graphs. Although the algorithm is simple, it is shown that this simple approach yields a powerful graph learner in terms of both theory and experiment. The theoretical analysis is comprehensive and proves the effectiveness of the proposed method.

Weaknesses:
The experiments are not very convincing. Only one graph dataset, PCQM4Mv2, is considered in the paper. If one to two new datasets are added, that would be great. It will be better to conduct more experimental ablation studies, such as the effects of type embedding. The results seem not strong enough, and more experiments can make this paper stronger.
questions: I have no questions.
limitations: The authors have addressed the limitations.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The paper proposes a new way to encode nodes and edges on the graph so that one can directly transform the input graph into a sequence and directly use the sequence transformers. With carefully designed position, type encodings, the paper proves that it is theoretically as expressive as a second-order invariant graph network. The authors validate several of their claims through a synthetic experiment and an experiment on real-world dataset PCQM4M. It achieves comparable performance with prior models and has the potential to scale to large graphs since the proposed method can just do a drop-in replacement of the transformer with all efficient transformer architectures.
strengths_and_weaknesses: The paper aims to serialize graphs so that we can leverage the benefits of all those expressive transformer architectures which have been investigated for the past few years. Although I’m not entirely sure that the prior graph transformers cannot leverage different attention/transformer architecture. I think the challenge of applying transformers to graphs is always how to differentiate nodes (i.e., designing different position encodings) while preserving the permutation invariance and equivariance. I like the second part of the paper where the model with the proposed position encodings is proved to be as expressive as a 2-IGN, and I also enjoy the first experiment which validates the theoretical claim.

One weakness/question in mind is on scalability and how to adapt to graphs with various sizes. The node identifier matrix $\mathbf{P} \in \mathbb{R}^{n \times d_p}$, where $d_p$ should be at least $n$. How can this scale to large graphs? Also the position encoding dimensions (node + type identifiers) may be much larger than the original node/edge features ($\mathbf{X}_v$).
Laplacian eigenvectors as node identifiers are still different from sinusoidal positional embeddings in NLP since the sinusoidal position embeddings can be of arbitrary dimension, but for the Laplacian eigenvectors, the dimension is fixed (which is the number of nodes on the graph).

Besides, from a practitioner point of view, the experimental results are not sufficient. The authors only evaluate their model on one real world dataset PCQM4M. There are multiple graph classification/regression dataset on Open Graph Benchmark and Benchmarking GNNs. Even on the PCQM4M dataset, it seems that all variants of the proposed methods are worse than prior graph transformers. Even with the claim that the proposed method can leverage efficient transformer implementations, it does not really address my concern. 1. you never show that the model actually works in a setting where we really need an efficient implementation, i.e., other quadratic implementations do not run or oom. 2. why can’t the prior works use the same efficient transformer implementations?

questions: - How do you set the dimension of node identifiers? Is the dimension the number of nodes in the graph? How do you deal with a batch of graphs with different sizes?
- Is there any difference between modeling directed and undirected edges? If one edge (u,v) is undirected, I think the modeling of (u,v) and (v,u) should be identical. However, it seems that the edge embedding will be $[\mathbf{X}_{(u,v)}, \mathbf{P}_u, \mathbf{P}_v]$ for (u,v) and $[\mathbf{X}_{(u,v)}, mathbf{P}_v, \mathbf{P}_u]$ for (v,u). 
- Also wonder how does the above issue about directedness and undirectedness generalize to higher-order hypergraphs?
- It’s interesting that using Laplacian eigenvectors as node identifiers and not using type id leads to comparable performance with using type identifiers on sparse inputs (the 7th row vs the final three rows in Table 1). Any insights?
- Have you submitted your final results to get the numbers on the test set of PCQM4M? The authors do not seem to include a discussion on how they tune the hyperparameters on PCQM4M especially since you only have the validation set. The validation performance alone is not convincing enough, let alone the proposed method achieves higher MAE than prior transformer-based methods such as Graphormer. 
- The model achieves higher MAE than all the three graph transformer baselines in Table 2. I did not find sufficient discussion on this result. There is basically a one-liner, which still emphasizes that the proposed method can be optimized computationally while not discussing the reasons for not matching the same empirical performance. State-of-the-art results are not necessary for publication but detailed discussion and analysis on why not is necessary.
- Can the proposed method be applied to other node-level or edge-level tasks like link prediction?
- The authors mentioned in the checklist that they included the code and data. However, their supplementary is only a PDF, I do not see the code to reproduce the concrete numbers listed in the experiment section.

limitations: The only limitation in my mind is that the proposed method may not necessarily generalize to large graphs as well as message passing networks. Although the paper mentioned that they can use all the efficient transformer architectures, yet there are no experiments, no evidence showing this. The full transformer architecture with quadratic complexity still runs. Besides, it would be nice to add more discussion on how the proposed method may be applied to other node and edge level tasks (as raised in the above section).
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The authors show that we can use the vanilla Transformers for languages and Vit without any graph-specific modifications can lead to promising results in graph learning. The interesting view is that the proposed model Soft Graph Transformer (SGT) uses edge features as tokens compared to other graph learners who only use node features as input tokens. And identifiers are designed to encode the graph's local information. Therefore, they can use the techniques for Transformers without any other modifications. Furthermore, they also theoretically proved their equivalence to the k-IGN models and the k-WL algorithms. However, I think their empirical evaluations are not enough and the advantages of their proposed SGT are not clear compared with other Graph Transformers.
strengths_and_weaknesses: Strengths:
1. Proposed a new view on the tokens instead of only using node features.
2. They also give a theoretical analysis of SGT's representative ability as powerful as k-WL and more expressive than GCN. Their analysis also gives us a direct reason why the node identifiers are orthogonal.

Weaknesses:
1. It is still not clear to me why Transformers for graph need to be the same as other transformers. I think it is natural that Graph Transformers need to have something special for graph tasks. According to "No free lunch" theorem, there can not be an algorithm that works the best for all tasks. Therefore, considering task-specific models are necessary. For example, Swin-Transformers takes the inductive bias for vision tasks into Transformers for vision tasks.

2. The empirical results also show no advantages compared with other Transformers for Graphs with larger resources cost. As for SGT+Performer, I'm not sure whether such a comparison is fair since other Transformers for Graphs may also use the linearized acceleration by modifying their models like Linformer's attention?


Typo:
line 286 Figure 1 -> Figure 2
questions: Questions:

1. I'd like to know whether other baselines like GraphFormers use the Laplacian positional embedding or not. Since the Laplacian positional embeddings are useful tricks and have been used in GraphFormers, SAN and other works.

2. I'd like to know why SGT performs worse than other GraphFormers. Do you have any possible causes?
limitations: I think they should clearly tell the readers that they are not the first who uses the Laplacian's eigenvectors in Graph Transformers since this trick is a simple but effective one.
review_title: null

Meta-review: metareview: The paper applies transformers directly to a graph by treating all nodes and edges in the graph as tokens. The author prove this approach is theoretically at least as expressive as an invariant graph network, which is already more expressive than all message-passing graph neural networks. The approach is simple and interesting. Reviewers had concerns on the empirical studies as only one dataset was used. In the response, the authors have partially addressed the concerns by offering more results. More discussion/analysis of the empirical results is expected. Considering that the paper is mainly on the theoretical side and the paper does provides interesting new insights, I'd recommend acceptance.
confidence: Certain
Decision: Accept