Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The authors propose a new transformer-like architecture for processing graphs. The main component is a special sparse attention module that considers only the neighbor nodes based on certain metrics. These metrics can be either structure or feature-based. For sampling from the neighborhood, it uses learned offsets. The authors also propose a novel position encoding method for the nodes in the graph.

strength_and_weaknesses: Strengths:
 - better performance on various datasets
 - the topology-based sorting ideas are interesting and novel to the best of my knowledge

 Weaknesses:
  - some parts (for example, the preprocessing) are not specified in the paper
  - the paper is difficult to read
  - some design choices need more justification
  - very complex
  - claiming that this method is the best among the transformer-based ones is somewhat unfair. The main difference between the transformer-based methods and the GAT-style GNNs is the unrestricted attention, but here the preprocessing step introduces very similar restrictions. 

The main weakness of the method:
- From Table 3, picking nodes at random is not much worse than choosing the nodes in the smart way proposed by the paper. This is surprising and questions what deformable attention does and its importance.

clarity,_quality,_novelty_and_reproducibility: - Clarity: I found the paper extremely hard to read. There are many ambiguities, the notation is unnecessarily complex, and many parts need to be specified more clearly.
- Novelty: The idea of ordering and subsampling the nodes is novel and interesting.
- Reproducibility: Because the preprocessing is unspecified, I would probably not be able to reproduce the paper.
- Quality: The quality of the paper is not enough to recommend acceptance.


summary_of_the_review: 
To recommend acceptance, I would like to see the following:
- Clarity has to be improved
- Specification of the preprocessing step in a clear way, including in the complexity calculation
- I would like to see an analysis of what the KatzPE does
- Some analysis on why the DGA's performance is very close to random


Questions to clarify:
- How do the sorting criteria work? What are they exactly? What is their input? Do they have learnable parameters?
- The paper claims that it is more efficient than the transformer-based methods. However, it does not consider the preprocessing step, which can be very slow (although it has to be done only once). Also,  "feature similarity", as far as the name suggests, is just ordinary attention, so it should be the same speed.
- "Although restricting the attention scope to local neighbors is a simple remedy to reduce the computational complexity, it leads to a failure in capturing local-range dependency, which is crucial for large-scale or heterophilic graphs." -> do you have any reference for this? According to Table 3, even using random nodes is almost as good as the best model. Isn't BFS doing just that?
- You mention that "DGT-light" uses a single sorting criterion. Which one?
- All of Eq. (4) is position based, but the positions are defined by the most relevant features (by S). The attention matrix only depends on the query node's feature and not the key's (it is just a fixed function for a given key index, k). This can act as a regularizer because the network can hardly choose individual, well-defined nodes to attend to. This can by itself improve performance.
- What is p? It can be inferred that it's probably an offset vector, but it would be nice if that is written in the paper.
- It would be nice to visualize p for some learned tasks. It would be informative about how far the model attends.
- What value of \gamma is used in eq (5)?
- "A major issue with positional encoding on graphs is the absence of absolute positions of nodes, unlike other domains." - what does it mean to have absolute positional encodings in a graph? What defines the ordering of the nodes?
- I don't see why KatzPE makes sense. It would be nice if the authors could add some more explanation. For me, it seems more like some kind of structure descriptor added to the nodes than it has anything to do with positions.
- A_k in Eq. (6) is of a fixed size. Does this mean that, unlike the transformer-based methods, KatzPE depends on the graph size? (for big graphs, this limitation is not present since there are only N' anchor nodes)
- It would be worth writing down that the so-called sampling is not actually an active sampling operation but just taking the features from the learned offsets. It can be confusing on the first read.
- Could you provide more details on how O(NC^2T + NKC^2T + WNKCT) becomes O(NC^2T + WNKCT) in Appendix A? Why does swapping the interpolation help with this?
- In 4.4, Figure 2, a should be Figure 2a
- In Appendix C.2, the list of parameters should be a table
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper proposes deformable graph transformer (DGT) to efficiently perform attention on graphs. The deformable graph transformer mainly consists of two components: deformable graph attention and Katz positional encoding. Experiments on eight datasets show better performance.
strength_and_weaknesses: Strengths 
1. The research problem is a fundamental and crucial one.
2. The experimental results show superior accuracies and efficiency (FLOPs).

Weaknesses
1. The novelty and technical contribution are limited.
2. It is unclear for the deformable graph attention module.
3. It is unclear why the proposed method has lower computational complexity.

Detailed comments:
1. What is the motivation to choose personalized pagerank score, bfs, and feature similarity as sorting criteria?
2. For NodeSort, 1) how to choose the base node, or is every node a base node? 
2)“NodeSort differentially sorts nodes depending on the base node.” Does this mean that the base node affects the ordering,  affects the key nodes for attention, and further affects the model performance?
3)After getting the sorted node sequence, how to sample the key nodes for each node? And how many key nodes are sampled？is the number of key nodes a hyper-parameter? 4)What are the Value nodes used in Transformer in this paper? 5)How to fuse node representations generated by attention for different ranking criteria.
3. Intuitively, the design of deformable graph attention is complicated, and the Katz positional encoding involves the exponentiation of adjacency matrix, so Is the computational complexity really reduced? Where can the reduction in complexity be explained from the proposed method compared to baselines? or just from the sparse implementation? 
clarity,_quality,_novelty_and_reproducibility: For clarity, some details are missing about deformable graph attention module.
For quality, the writing is easy to follow.
For novelty, the novelty and technical contribution are limited.
For reproducibility, the code is attached.


summary_of_the_review: The deformable graph attention module should be presented in a clear way. The reduction of complexity should be explained further.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper propose a new graph sampling mechanism for reducing the computational complexity in full attention of graph transformer. The sampling mechanism takes structural and semantic similarity into consideration. Experimental results show the effectiveness of the proposed method. Additionally proposed positioanl encoding enhances the performance of the model. 
strength_and_weaknesses: Pros:
The motivation makes sense. The paper is easy to follow. 

Cons:
1. The proposed method seems to be a graph sampling mechism + full attention on the sampled node subset. Therefore the claim of "sparse attention" should be clarified.
2. It's strange to run a Transformer-based graph model on full graph for node representation tasks without any graph sampling methods (e.g., random walk). Therefore, the comparision seems unfair to me from both the performance and the computation cost perspectives. More detailed benchmarking experiments with graph sampling methods will make the paper more solid.
3. The proposed Katz PE seems to be an important component contributing to the final performance, but the motivation of the Katz PE is less relevant to the main motivation of this paper. Therefore, it makes the solidness of the main contribution of this work (the graph samping mechnism) weak.
clarity,_quality,_novelty_and_reproducibility: quality, clarity and originality are good.
summary_of_the_review: See Weaknesses. I'm willing to raise my score if my concerns are well addressed.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: Graph transformers have drawn growing attention in representation learning on graph-structured data. However, their success is limited to small graphs due to the quadratic complexity of the dot-product attention module in transformers. This paper proposes the Deformable Graph Transformer (DGT) to address this issue, by using a deformable graph attention (DGA) module with a linear complexity in the number of nodes. The proposed DGA, inspired by recent work in computer vision, only attend to a small set of key sampling nodes around a reference node. The set of key sampling nodes is learned by learning their positions in a sorted list pre-defined by each reference node based on some similarity criteria with respect to the reference node, such as personalized Pagerank score (PPR), BFS, or node feature similarity. The paper also proposes a positional encoding to use with the proposed DGT. The authors validate the proposed method on several node classification tasks.
strength_and_weaknesses: ##### Strengths
1. Development of efficient transformers is a challenging and important task. To my best knowledge, this is the first work on linear transformer specifically developed for graphs.
2. The proposed method seems to scale well to large datasets with up to 232k nodes.
##### Weaknesses
1. (Presentation of the method) The paper does not do a great job of presenting the proposed method and highlighting the technical novelty. Section 3.2 is not very accessible for readers not familiar with previous work on deformable transformers, and is hard to identify the technical contribution from the previous work. It seems that many new concepts introduced here such as sampling offsets or using interpolation to find the representation at fractional location have already been introduced in [1]. I recommend a separate background section including section 3.1 and more preliminaries of deformable transformers to make the paper self-contained.
2. (Clarity of the method) The main contribution of the work should be to use a NodeSort module to enable offset sampling and thus key node sampling. However, the presentation of this module is very short and there is even no detailed description about each sorting criteria, neither a reference provided. Besides, I am not sure some of them have a proper definition of ordering. For instance, if I understand correctly that BFS denotes the breadth-first search (the paper uses this abbreviation without giving the full name), then its order cannot be unique and could be exponential in the worst case. I expect more a more detailed presentation of all these sorting criteria. In addition to this, I also found some other missing details. For instance, how the offsets are computed is only described in the caption of Figure 1, which largely reduces the readability of the paper.
3. (Missing baselines) There are a few recent graph transformers leveraging better the structural information about the graph such as [2, 3]. In particular, [3] explore different linear/sparse attention methods from NLP, such as Performer or BigBird, to make graph transformers more scalable. I expect an empirical comparison with these methods to justify the practical impact of DGT.
4. (Weak results on ogbn-arxiv) A quick check on the leaderboard of [ogbn-arxiv](https://ogb.stanford.edu/docs/leader_nodeprop/#ogbn-arxiv) suggests that the SOTA performance is around 76% while the best performing methods in Table 1 of this work only achieves 71%, which is far behind the real SOTA. I am skeptical about the so-called SOTA performance on other datasets and the claim in the abstract that DGT achieves SOTA performance on 7 datasets.
5. (Novelty of positional encoding) The proposed Katz positional encoding is very similar to the random walk positional encoding introduced in [4, 5], which have already been widely used in many graph transformers. I recommend the authors to check and correct the claims on this contribution.
6. (Missing hyperparameter studies) Comparison of using different sorting criteria is shown in Table 3. However, the results are incomplete and results for only using PPR or Feat are not given. In addition, a study on the effect of different values of $\gamma$ would also be useful as its search space seems to be much larger than other hyperparameters.

##### Minor comments
1. The way of measuring FLOPs could be variable and ambiguous. Could the authors elaborate more on how they measured the FLOPs for different methods? Could the authors also report the runtime per epoch?
2. In section 3.3, "path" should be replaced with "walk" that allows repeated nodes.

##### References
[1] Zhu, Xizhou, et al. "Deformable DETR: Deformable Transformers for End-to-End Object Detection." ICLR 2020.

[2] Chen, Dexiong, et al. "Structure-aware transformer for graph representation learning." ICML 2022.

[3] Rampášek, Ladislav, et al. "Recipe for a General, Powerful, Scalable Graph Transformer." NeurIPS 2022.

[4] Dwivedi, Vijay Prakash, et al. "Graph Neural Networks with Learnable Structural and Positional Representations." ICLR 2021.

[5] Li, Pan, et al. "Distance encoding: Design provably more powerful neural networks for graph representation learning." NeurIPS 2020.
clarity,_quality,_novelty_and_reproducibility: The presentation of method is unclear and hard to follow. More details about this can be found in point 1, 2 of __weaknesses__.
I also have some concerns with the quality of experiments (3, 4 in __weaknesses__), technical novelty (5 in __weaknesses__), and reproducibility (6 in __weaknesses__).

summary_of_the_review: Despite the efforts made by this work to solve a challenging and important for graph transformers, I recommend weak reject because 1) the presentation of method is imprecise and lacking a lot of details; 2) there are important missing baselines and the reported results seem to be far behind SOTA results; 3) the contribution to positional encoding is over-claimed due to incomplete related work; 4) some hyperparameter studies are missing.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This work propose DGT, a transformer architecture for dealing with graphs with a large number of nodes.
DGT combines an adaptation of the deformable attention scheme to graphs and a new learnable position encoding for nodes.

The deformable attention mechanisms consists in sorting all the nodes in the graph w.r.t. some criterion viewed from all nodes (e.g., BFS). This is a pre-processing step. Then, for a given query node and each combination of (sorting criterion, head), for each k of the K first nodes, a deformable attention is computed. More precisely, the deformable attention interpolates the values of all the nodes w.r.t. node k in the sorting using the RBF kernel.

On the other hand, the new Katz position encoding counts all paths between a given node and all the others with decaying weight for longer paths. A subsequent processing by a MLP makes it learnable.

Then, the authors demonstrate the superiority of their approach on several homophilic and heterophilic node-classification datasets in terms of accuracy and FLOPs. Some ablations study are performed to demonstrate the usefulness of their relative multi-criteria search and position encoding separately. Finally, the work study the nodes that are selected by their attention mechanism compared to Graphormer.

strength_and_weaknesses: Strengths:
- This work address an important problem, namely how to make graph transformers work when the number of nodes is large.
- The strategy proposed by the authors seems very effective on all datasets both in terms of accuracy and FLOPs.
- The authors provide ablations to study the effectiveness of their two contributions (DGA and Katz PE).

Weakness:
- Although the paper is mostly well-written, I had a hard time understanding how DGA works. In particular, the idea of sampling offsets could be made more clear both in the text and in the figure (I do not understand what do the arrows do in the blue boxes in the center) so that the work is more self-contained.
- The claim that other architectures query irrelevant nodes could be backed more rigorously (see below).
- I am not sure the comparison are fair or at least clear in terms of model size (see below). 
- It would be even more convincing to demonstrate that DGT is also good at graph classification/regression tasks
clarity,_quality,_novelty_and_reproducibility: Clarity:
- Are the K values the first from the sorting? If so, it could be interesting to space these values since you already interpolate between neighbors. 
- If I understand correctly, DGA interpolate on all the nodes of a given sorting for K=4 references. Wouldn't it be worth trading the interpolation for increased K?
- It could be useful to give the size of the models. It seems that the number of parameters in DGT scales linearly with the number of sorting criteria?
- I am not super convinced by the idea proposed in Figure 2: why querying nodes with similar labels necessarily makes an attention mechanism better? Why would only similar nodes be relevant and not dissimilar nodes? In light of this, I think the claim that other methods aggregate information from irrelevant node exaggerated.

Quality:
- The work successfully tackles an important problem and both contributions (DGA and Katz PE) could be reused in subsequent works
- The experiments use several baselines with thorough error bars and both homophilic and heterophilic graphs, with ablations hence are very convincing.

Novelty:
- I have a slight doubt on the novelty of Katz PE. Indeed, it is common in the graph kernel litterature to enumerate paths. Could you comment on this? See e.g. [1].

Reproducibility:
- The code and hyperparameter grid were provided.

[1] Shortest-path kernels on graphs (Borgwardt and Kriegel, 2005).

summary_of_the_review: This work combines two effective mechanisms to propose a graph transformer scaling to large number of nodes with very good performance in terms of accuracy and FLOPs. It also has some defaults such as lack of clarity for one of the two mechanisms (sampling offset in DGA), claims about novelty of Katz PE and about how classical architectures aggregate "irrelevant" nodes that could be better supported. I also think it would be interesting to demonstrate the usefulness of DGT for graph classification. 

Overall, I think the pros outweight the cons and I recommend acceptance. I would further raise my score if these concerns are answered.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: In this work, a deformable graph transformer is proposed, which is capable of sparsifying the attention mechanism to make Transformers more scalable. Additionally, a learnable Katz PE is proposed in order to improve the representational quality of the model. Reviewers have all agreed that the work has relevance for the community, and the proposed solution is interesting. However, serious concerns were raised by the motivation of the proposed combination of methods, their practical impact, the novelty of the various components, and certain non-solid claims made by the authors. After a thorough AC-Reviewer discussion (see details), a consensus was reached to reject this paper, which I agree with. I hope the authors can take all the reviewer comments into account, and continue this line of work -- it could be quite promising!
justification_for_why_not_higher_score: During the AC-Reviewer discussion, all Reviewers reached a consensus to recommend a rejection for this work.
Decision: Reject