Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper proposes a new sparse attention mechanism for graph-structured data to address the quadratic complexity issue of graph transformers. Inspired by the idea of the sparse attention module BigBird for sequences, the proposed method, named Exphormer, also constructs an interaction graph based on three types of edges for attention. These edges include a random expander graph (random attention), the original graph (local neighborhood attention), and edges between any node and a virtual node (global attention). Thanks to the fruitful mathematical properties of expander graphs, the authors prove mixing properties and a universal approximation property of Exphormer. The authors show the first time that BigBird-like models, namely Exphormer, achieve very good performance on five graph benchmark datasets.
strength_and_weaknesses: ##### Strengths
1. The idea of using expander graphs (specifically d-regular expanders for fixed d) as a sparse approximation of complete graphs is elegant and original to my best knowledge.
2. The proposed method seems to be simple to implement and to incorporate into existing framework combining transformers and GNNs, which only requires a sampler for generating random regular expander.
3. The empirical comparison is fair and solid.
4. The paper is well-written and easy to follow.

##### Weaknesses
1. (Positioning) This work is motivated by the fact that most existing graph transformers are limited to small graphs due to the quadratic complexity of full dot-product attention. However, the conducted experiments are somewhat misleading as most of the results are only shown on datasets of small-scale graphs. Given marginal improvements over the previous SOTA transformer GraphGPS that used either full or linear attention (e.g. Performer), the impact of this method is not very clear. On the other hand, for the more interesting tasks with large-scale graphs like ogbn-arxiv, the paper only shows very preliminary results, far behind the SOTA results. I expect a thorough evaluation of Exphormer on more datasets with large-scale graphs, such as other node classification datasets of OGB.
2. (Limited task types) Exphormer is only evaluated on classification tasks. It would be more convincing to demonstrate the effectiveness of Exphormer on graph regression tasks.
3. (Missing experiments) Some important studies of hyperparameters are missing, including the effect of expander graph degrees, the effect of the number of virtual nodes. It would also be useful to show the memory usage of the vanilla transformer, BigBird, Performer, and Exphormer.

clarity,_quality,_novelty_and_reproducibility: __Clarity__:
1. What is the difference between the BigBird model used in GraphGPS and Exphormer? Do they only differ in the choice of the random expander graphs?
2. Exphormer seems to work well mostly on synthetic and image datasets. On molecular graph datasets (ogbg-molpcba), there is a clear performance gap between Exphormer and GraphGPS, could the authors elaborate more on why Exphormer does not work well for molecular graphs? Also, why there is no standard deviation available in Table 5 for Exphormer?
3. What are the search grids for different hyperparameters?
4. Is Exphormer permutation-invariant? At inference time, does Exphormer still use a random expander graph? If so, how to ensure generating the same output for the same graph with different permutations of nodes.

__Quality__:
1. The work addresses an important and challenging problem for graph transformers, showing promising empirical results.
2. The implementation descriptions are detailed, and the experimental setup is fair and sound.

__Novelty__:
- The use of d-regular expanders is original. However, it would be important to clarify the difference between the BigBird and Exphormer in experiments.

__Reproducibility__:
- All hyperparameters are provided, but the code was not provided.
summary_of_the_review: This work successfully extends BigBird to graph-structured data and demonstrates the first time that BigBird-like sparse attention achieves SOTA performance on several graph classification datasets. I have some concerns about its insufficient experimental results on large-scale graphs, limited task types considered, and some missing experiments relative to hyperparameters and memory usage.

Overall, I think the strong points overweight the weak points and I recommend a weak accept. I would further increase my score if all my concerns and questions are answered.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper presents a new and scalable graph Transformer, named Exphormer. The motivation of this work is that existing graph Transformers can not efficiently scale to large graphs. Exphormer designs a sparse attention mechanism that consists of three main components: expander graph attention, local neighborhood attention and global attention. As the main building block, expander graph attention utilizes the edges of a regular expander graph with a constant degree in the interaction graph, thus allowing it have a linear computational cost. The authors further provide theoretical analysis of expander graphs and the implication with Exphormer. Extensive experimental results demonstrate the effectiveness of the proposed Exphormer.  
strength_and_weaknesses: Strengths: 
-	Comparing with full-attention graph Transformers, Exphomer can perform sparse attention mechanism on larger graphs and efficiently reduce the computational cost.
-	 The paper provides plenty of theoretical analysis to support their claims, although I have some concerns.
Weaknesses:
-	For two graphs with the same number of nodes, using the same degree constant may generate the same regular graphs, thus preserving the same edges.  How does this help in learning the features of the two graphs? In fact, the paper doesn’t distinctly illustrate the function of expander graph attention for learning node representations.
-	The degree of regular graphs, d, is an important hyperparameter and graphs of different sizes may need different d, especially on large graphs. However, the parameter studies of d on different graphs are missing.
-	Lacking of ablation studies to verify the effectiveness of the three main components of Exphormer. I’m curious about how much performance gain can expander graph attention bring.
-	More experiments need to be conducted on large graph benchmarks (Citeseer, Pubmed, Computer, ogbn-proteins, etc.) to validate the effectiveness and scalability (especially the comparison of time and memory cost) of the proposed method on large graphs. In addition, existing sparse attention methods (GT[1]) and sampling-based methods (NAGphormer[2], Gophormer[3]) shall be chosen as baselines on large graphs.
-	The paper is not very easy to follow and some notations are confusing. And the formulas are not numbered. Specifically, the format of Table 1 is totally a chaos and need to be reorganized.

[1] Dwivedi V P, Bresson X. A generalization of transformer networks to graphs[J]. arXiv preprint arXiv:2012.09699, 2020.
[2] Chen J, Gao K, Li G, et al. NAGphormer: Neighborhood Aggregation Graph Transformer for Node Classification in Large Graphs[J]. arXiv preprint arXiv:2206.04910, 2022.
[3] Zhao J, Li C, Wen Q, et al. Gophormer: Ego-Graph Transformer for Node Classification[J]. arXiv preprint arXiv:2110.13094, 2021.

clarity,_quality,_novelty_and_reproducibility: Clarity: The writing is not very clear and not friendly for readers.
Quality: The related theoretical analysis maybe reasonable, but the experimental results cannot validate the efficacy of the proposed method.
Novelty: A transferable work from BigBird, and the effectiveness remains uncertain.
Reproducibility: Not Applicable. 

summary_of_the_review: The method and theoretical analysis look good, but the experimental analysis, comparisons and writings need to be improved.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This work proposes Exphormer, a framework to improve the performance and scalability of graph transformers. Exphormer consists of three components, including expander graph attention, local neighborhood attention and global attention. The key innovation of this work is that Exphormer introduces expander graphs on graph transformers as a graph data augmentation method, which has rich theoretical properties. Meanwhile, Exphormer uses a sparse attention technology similar to BigBird, which reduces the quadratic time complexity of self-attention, making it possible to use it on larger-scale data. The authors demonstrate the abality and efficiency of Exphormer from two aspects of theoretical and experimental analysis, and achieves sota results on three datasets.
strength_and_weaknesses: Strengths:
1. Nice English writing and clear sentences.
2. The figure provides a good overview of the method.
3. The theoretical analysis of expander graphs is solid and complete.
4. Compared to other graph transformers, Exphormer has significant advantages in computational time complexity.

Weaknesses:
1. Insufficient motivation of using graph transformers as encoders. In the formula of the generalized (dot-product) attention mechanism at the bottom of page 3, each node only calculates attention scoers with its own 1-hop neighbor nodes. Such an attention process is not much different from the graph attention network (GAT), and destroys the properties of the global receptive field of graph transformers, which is a key advantage of graph transformers towards GNNs. There seems no problem if the graph transformer here is replaced with GAT, so the motivation of using graph transformers as encoders is not sufficient.
2. The authors discuss in section 4.2.2 that if a certain number of transformer layers are stacked, the global receptive field of the Exphormer can be recovered. However, this method is common in GNN. Besides, the authors mention in the introduction that the stacking can lead to problems such as oversmoothing and oversquashing. It is mentioned above that the graph transformer in Exphormer is not very different from GAT, so will Exphormer also face the problems of oversmoothing and over squashing if stacking multiple layers?
3. The authors mention in the introduction that most of the experiments done by GraphGPS focused on small graphs, but this work only conducts experiments on one large dataset, ogbn-arxiv. A key advantage of Exphormer is scalability, so it needs to be supplemented with more node classification experiments on other large-scale graph datasets.
4. Theorem 4.1 analyzes the  approximation properties of expander graphs to complete graphs, but complete graphs are only a kind of special structures, which cannot represent the approximation propertities for general graph structures, and it seems there is no proof for this theorem. Besides, $S$ in equation 1 has no annotation, $\pi^{(t+1)}=D_{G}^{-1}A_{G}\pi^{(i)}$ in section 4.2.2 should be replaced with $\pi^{(t+1)}=D_{G}^{-1}A_{G}\pi^{(t)}$.
5. In Appendix D, the authors analyze the universal approximation properties of Exphormer. However, the authors only uses the global attention module. It seems that expander graph attention and local neighborhood attention modules do not contribute to the theoretical performance of the model.

clarity,_quality,_novelty_and_reproducibility: Clarity: This work is well-organized, well-written, and the figures and the diagrams are helpful to understand the model architecture.

Quality: The theoretical analysis of expander graphs is solid and complete. However, the motivation of using graph transformers and expander graphs is insufficient, and the lack of large-scale dataset experiments is not convincing.

Novelty: This work combines graph transformers and expander graphs, which is innovative.

Reproducibility：The authors did not provide supplementary material, so it cannot be reproduced.


summary_of_the_review: This work combines graph transformers and expander graphs together, and uses sparse attention mechanism to reduce quadratic time complexity. However, the motivation of using graph transformers and expander graphs is insufficient, and the lack of large-scale dataset experiments is not convincing.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This work proposes a new attention mechanism for graph transformers aiming at handling graphs with large number of nodes.

More precisely, the attention mechanism is three-fold:
- Local attention, applied to 1-hop neighbors of a given node.
- Global attention via virtual nodes.
- Sparse attention based on an expander graph, which is the main contribution of the paper.
The main model is used within GraphGPS framework, which combines an attention scheme with message passing and positional/structural encodings.

The authors motivate the use of an expander graph based attention by the theoretical properties of expander graphs: 
- The expander graph is a good approximation of the complete graph.
- Random walks on the expander graph mix well, meaning that provided there are log(nb_nodes) expander graph attention layers, each node is able to communicate with any other node.

The author then proceed to experimentally demonstrate the benefits of the proposed attention mechanism over various GNNs and Graph Transformers, both in terms of accuracy and number of parameters/scalability. Finally, some ablations are conducted i) by combining other attention schemes than Exphormer with MPNN and ii) by comparing Exphormer without message passing to models that do not necessarily use message passing.
strength_and_weaknesses: Strengths:
- Scaling competitive graph transformers to large graph is an important problem for which this work offers a potential solution.
- This work proposes interesting motivations for the use of expander graphs.
- The proposed mechanism scales to larger graphs (order of magnitude of 100k nodes).
- Some ablations demonstrate the usefulness of Exphormer compared to other graph transformers. More generally, the experimental protocol is thorough (error bars, various baselines and tasks).

Weaknesses:
- Although the use of expander graph is motivated, it is not clear whether these motivations are responsible for the performance of Exphormer: there is to my understanding no ablation on the role of each of the three attention mechanisms (local, global, expander), and the attention pattern could be studied to check whether expander attention indeed uses communication between distant neighbors.
- Experiments on ogbn may be more convincing: experiments on arxiv are behind GAT, and behind GraphGPS for molpcba and code2. Moreover, it would be useful to display the results of Exphormer only on molpcba and code2.


clarity,_quality,_novelty_and_reproducibility: Clarity:
The paper is globally well-written with a few caveats:
- It is not clear how the three attention mechanisms are combined.
- Is the model sensitive to the choice of number of virtual nodes and expander degree?

Quality:
- The paper offers interesting mathematical motivations for the use of the expander attention scheme but I don't think the experiments illustrate the benefits of this scheme, which makes the paper somehow imbalanced. It would be more convincing to either study the expander attention pattern and show it leverages the properties detailed in Section 4, or reduce Section 4 to further experimentally study the proposed attention mechanism (sensitivity to hyper-parameters or ablation of local/global/expander attention).

Novelty:
- The use of expander graphs has been recently proposed [1] in the context of GNNs: it would be worth discussing it in the related work to better delineate this contribution. Apart from this, the proposed scheme (combination of local-global-expander attention) seems new.

[1] SPARSIFYING THE UPDATE STEP IN GRAPH NEURAL NETWORKS, Johannes F. Lutzeyer, Changmin Wu, Michalis Vazirgiannis (2021)

Reproducibility: no code is not provided but the appendix seems to contain enough experimental details.
summary_of_the_review: This work offers a sensible solution, a sparse attention scheme relying on expander graphs, to an important problem, scaling graph transformers to large graphs. Expander attention has theoretically suitable properties and the experiments demonstrate that its combination to other attention mechanisms within GraphGPS framework scales to large graphs with reasonable performance in terms of accuracy.

However, it seems to me that the paper stresses on the mathematical motivation of expander attention without studying whether these properties are indeed useful in practice, and the results on ogbn seem to be behind other baselines.

Therefore, I do not recommend acceptance for now. I am willing to increase my score if my concerns (clarification of usefulness of expander attention, discrepancy with GNNs on ogbn-arxiv and with GraphGPS on ogbn-molpcba and ogg-code2) are answered.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The paper proposes a new transformer-type GNN architecture based on expander graphs. This is an interesting and novel idea (expander graphs have made an appearance in several recent GNN works, but overall are rather new in this community), which was also appreciated by the reviewers. However, the reviewers raised concerns about non-convincing results on ogbn-datasets, limited task types, and missing theoretical understanding of the proposed method (although the use of expander graphs is motivated, it is not clear whether these motivations are responsible for the performance of Exphormer). This opinion also prevailed after the rebuttal. 
Our recommendation is rejection. 
justification_for_why_not_higher_score: I think this is a nice paper, but the theoretical motivation is lacking and the reviewers were overall quite lukeworm
Decision: Reject