Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: The paper proposed a simple Transformer-based neural network architecture for graph data, called GraphFormer. Inspired by the positional encoding in NLP, GraphFormer encodes the structural information of the graph into the Transformer architecture via 1) centrality encoding, which incorporates degree information in computing the node embeddings, 2) spatial and edge encoding, which utilizes the shortest path between nodes to determine the edge biases in self-attention. In addition, the author added a set of virtual nodes to GraphFormer that connects to all nodes via "virtual" edges. The author compared GraphFormer with other models in several molecule/chemistry graph classification tasks and show that GraphFormer significantly outperforms the other methods, including several SOTA Message-Passing Graph Neural Network (MPGNN) models.

main_review: 
- Originality
The architecture of the paper is similar to the Code Transformer model proposed in [ICLR2021, Language-Agnostic Representation Learning of Source Code from Structure and Context]. However, the author has not mentioned this paper in the related work. Other than that, the usage of virtual nodes and the way of generating the edge encodings via shortest path are novel and original.

- Technical Quality
The author performed extensive experimental evaluations of GraphFormer on benchmarks like OGB and ZINC and demonstrated that it achieves state-of-the-art performance. However, from Table 1,2,3, we can notice that GraphFormer has significantly more parameters than the baselines. This means that GraphFormer can be much more computationally expensive than the other models. Thus, it is not clear if the performance improvement of GraphFormer is attributed to its larger model size or architectural advances. In addition, one limitation of the encoding mechanism adopted by GraphFormer is that it may not be efficient for graphs with "hubs" (nodes with very large degrees). The author may need to mention this limitation in the paper.

- Clarity
The paper is well-written and easy to understand.

- Significance
Performance of GraphFormer is significantly better than the baselines according to Table 1,2,3. However, I need to see more evidence to understand if it is simply attributed to scaling up the model size or due to the usage of Transformer.


--- Post Rebuttal ---
The author has address my concerns and I will increase the score to accept.
limitations_and_societal_impact: I think the author needs to state that GraphFormer may not be suitable for large graphs due to the full-attention. In addition, the author needs to emphasize on the more extensive computational cost of the model.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: GraphFormer modifies the attention layer in a Transformer in a way to incorporate information about the structure of the graph. The modifications are intuitively motivated and show that GraphFormer is at least as powerful as GNNs. The experimental results are positive although they seem to come at the cost of many more parameters.
main_review: Originality: The idea appears to motivated by Graph Transformer and several other papers that add structural encodings to GNNs as mentioned in the Related Work section. Adding structural encodings to the attention mechanism indeed appears novel.

Quality: Simple proofs are provided to show that the model is at least as powerful as GNNs. Experiments are run on Open Graph Benchmark (OGB) which is standard for deep learning on graphs. Results are strong. Ablations are done to show the importance of each structural encoding ingredient.

Clarity: Background knowledge is clear and diagrams are good. Information is provided to reproduce experiments.

Significance: The method is easy to apply to any graph, and the experimental results are strong. Given the familiarity of Transformers, I expect many researchers and partitioners will reach for this model when presented with graph data. The main limitation appears to be the quadratic scaling with the size of the graph.
limitations_and_societal_impact: I don't see any potential negative societal impact.

The authors state that performance, especially on large graphs, will limit applicability of their system.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This work proposes a transformer architecture suited for graph representation. More precisely, the structure of the graph is encoded via three different mechanisms focused on the degrees, the distance of the shortest path between two nodes, and the edges. The resulting model outperforms different GNNs on four molecular graph tasks.
main_review: As GNNs are the current preferred architecture for graph representations, outperforming these make this work significant. The paper is also sound and clear. Some more experiments may be useful to better understand the capabilities of GraphFormer as well as some clarifications on the novelty of the encoding mechanisms.

Pros:
- The proposed architecture seems sound and simple.
- GraphFormer obtains excellent results on OGB.

Cons:
- The paper claims that the proposed Spatial Encoding is novel (l129). In my opinion, this may be exaggerated as this encoding seems rather be an instance of relative position encoding, where a parameter depending on the distance (of the shortest path) between two nodes are learned. 
- The paper does not propose experiments on smaller molecular data sets (a few hundreds/thousands graphs). This could be useful to understand how does GraphFormer do with respect to GNNs in different settings. To my understanding, these experiments could be conducted with and without pre-training.

Questions and remarks:
- l18: what do you mean by "powerful"?
- Experiments: GAT, which also applies attention (although on neighboring nodes only) could be an interesting baseline for this work, why not comparing to it?
limitations_and_societal_impact: The authors identify sensible limitations in their work. Negative societal impact are not mentioned, although they remain limited.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper considers adapting a standard Transformer to work on general graphs, and applying it to a few recent graph representation learning benchmarks. They propose three ways of augmenting a standard Transformer architecture by adding new node features and additive attention biases, and show that their approach (GraphFormer) yields state-of-the-art performance on the considered benchmarks. They also prove some theoretical results stating that GraphFormer is more expressive than many standard graph neural network architectures, and conduct an ablation of the modifications they make to a standard Transformer, showing that each of them leads to better performance.

As the authors note, there has been a lot of work in adapting attention and other parts of transformers to a graph domain. In particular, there has been a lot of work on using attention mechanisms in graphs, and also more specifically in using edges to bias attention between nodes or using features based on shortest paths between nodes. Taken on their own, the modifications proposed in GraphFormer seem fairly incremental.

Nevertheless, most of the prior work I'm aware of focuses on individual modifications for specific tasks instead of a unified set of changes for standardized benchmark datasets, and often deviate from a standard Transformer backbone in a large number of ways. It does seem useful to demonstrate that the Transformer architecture can be applied to graph understanding tasks in a straightforward and general way, and that doing so leads to strong performance both theoretically and empirically. Transformers have shown strong results in many domains, and I think this paper could be a good starting point for future developments on using transformers for graph representation learning.
main_review: ## Proposed approach
The authors propose three ways of adapting a standard Transformer architecture to work on graphs.

- First, they propose adding in-degree and out-degree embeddings to the embedding of each node, before computing the query and key attention vectors. This gives the network an ability to condition on those degrees in addition to the local features of the node itself.
- Second, they propose computing the distance between each pair of nodes, and then using this to choose from a set of learnable biases for the attention logit between that pair of nodes. In particular, by assigning different biases, the network can learn to focus attention only on nodes in the neighborhood, or to nodes far away, with different weights assigned to each. This adjustment happens "outside" the key-value dot product, so it is based on distance alone and not based on the query and key embeddings.
- Third, for graphs with edge features, they propose adding an adjustment based on the ordered sequence of edges along the shortest path between those nodes. In particular, for each possible index $n$ in the shortest path, they learn an edge weight vector ${{w^E}\_{n}}$, then take the dot product between ${{w^E}\_{n}}$ and the $n$-th edge feature ${{x}\_{e\_n}}$ along the shortest path. This is also added to the attention logits directly, allowing each attention head to learn to attend to a different type of path between nodes.

In addition to these modifications, they adapt some well-known tricks from transformers and graph neural networks:
- They apply layer normalization before attention, which has been shown to work well for transformers in other domains,
- They introduce a "special" node [VNODE] that tracks full-graph information, similar to the use of similar nodes in MPNNs and the use of the [CLS] token in BERT. However, they emphasize that this node is "virtual" and doesn't participate in the shortest-path embeddings (it instead gets its own, separate attention bias).

One question I had about the edge feature path embedding: what do you do when there are multiple paths of the same length? Should all of them be averaged together, or do you just pick one? (Does it matter?)

## Theoretical and empirical results
Theoretically, the authors argue that GraphFormer is able to represent the same operations as a standard GNN: in particular, that it can mask attention to the nearest neighbors, use the known degree to compute sums over neighbors, and use the FFN in the attention layer to combine node and neighbor features. Their proof defers to the universal approximation theorem of fully-connected networks, and although it is a fairly informal argument I think it's essentially correct. (I think it would be a bit more precise to say that GraphFormer can approximate any other GNN arbitrarily well with enough parameters, since that's all the universal approximation theorem allows?)

They also argue that GraphFormer is not limited by the 1-WL test, by providing an example where distances between pairs of nodes can be used to distinguish two graphs that the 1-WL test cannot distinguish. Finally, they argue that even without a special [VNODE] node, GraphFormer can still learn to aggregate information across the graph using the "mean readout" function (essentially, by having all of the queries, keys, and spatial biases be identical so that every node attends to every other node).

Empirically, they demonstrate their approach on the OGB Large-Scale Challenge, OGB, and benchmarking-GNN benchmarks. For each, they compare to a variety of graph neural network approaches that have been previously applied to those benchmarks. They also compare to the Graph Transformer model of Dwivedi and Bresson [13], a different general-purpose adaptation of transformers to graphs. The GraphFormer model shows strong results across the different domains, outperforming all of the reported baselines.

The authors also include an ablation study on one of the datasets, showing that each of their proposed modifications improves performance over a vanilla Transformer, as well as over some alternative encoding strategies from prior work.

One thing that would strengthen the experimental results would be to compare the GraphFormer architecture to some of the other methods for encoding paths, distances, and edge features that the authors cite in their related work section. For instance, how does GraphFormer compare to the concatenated-path-attention strategy in [9] or the distance encoding of [30]?

## Originality and significance
As the authors note, the success of transformer-based models has led to a wide variety of work on combining parts of graph neural networks with parts of transformers. Thus, many of the ideas used in GraphFormer (in particular, using attention mechanisms locally and globally, and biasing attention using shortest paths, edge features, or distances between nodes) resemble things from prior work (and the authors do a good job of citing many of these earlier works).

Even so, one of the nice things about the proposed GraphFormer architecture is that the modifications to the standard transformer architecture are quite simple and general. The node degree information is simply added as part of the node features, and the distance and path features are added as attention biases. This suggests that improvements to transformers for NLP or other domains could easily transfer to improvements in GraphFormer, and vice versa.

Thus, despite the simplicity of the proposed changes, I think this paper could be quite impactful by showing that, both theoretically and empirically, the standard Transformer architecture can be successfully adapted to graph representation learning tasks. In fact, the simplicity might be a good thing, as it provides a signal that the Transformer backbone can do very well with just a few extra graph-based features. I wouldn't be surprised if this was a starting point for additional research on applying transformers to graphs, even if not all of those future directions incorporate exactly the same set of modifications.

One piece of related work that the authors may be unaware of is ["Global relational models of source code" (Hellendoorn et al. 2019)](https://openreview.net/forum?id=B1lnbRNtwr), which proposes adding edge-feature-based attention biases to a standard transformer, applied to a graph representation of a program. 

## Clarity
Overall I found the paper easy to read and well motivated. The authors provide an intuitive explanation for why each of their modifications is sensible, and give a nice proof sketch in the main text of how the GraphFormer architecture generalizes other GNN architectures.

Minor suggestions for clarification:
- Line 253: "transferable capability of the pre-trained GraphFormer on OGB-LSC": I initially interpreted this as transferring from something else to OGB-LSC. But I think you actually mean transferring from OGB-LSC to graph classification? Perhaps you could reword this to "transferable capability of a GraphFormer model pre-trained on OGB-LSC" or something similar?
- Line 262: Is PCQM4M-LSC the same dataset you pretrain GraphFormer on, or did you pretrain on a different dataset?

limitations_and_societal_impact: This work is a methodological contribution without any specific negative societal impacts that I'm aware of.

The authors discuss some limitations of their work, in particular the quadratic complexity of global self attention and the need for future work on graph subsampling strategies. They also mention that their approach may be more prone to overfitting, although regularization seems to fix this. (The checklist mentions section 5 containing limitations, but I think the authors may have meant section 6?)
review_title: null

Meta-review: This paper presents a set of simple modifications to the popular transformer architecture so that they can work well on graph structured data.  The paper is quite clear and well-written.  Extensive empirical results show that these architectures can outperform graph neural networks on a wide range of benchmarks.

All reviewers consistently recommend accepting this paper, and are optimistic about the adoption of the proposed techniques due to their simplicity and strong empirical results.

The authors should consider the reviewers’ suggestions to improve the paper, in particular the additional related works mentioned in the reviews that can better help put this work into context.
Decision: Accept (Poster)