Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper studies the limitations to deepen graph transformers and argue that substructure learning gets increasingly harder in the canonical formulation of the graph transformers. To address this limitation, the paper proposes a variant of graph transformers that explicitly models substructure attention and encoding. Empirical results suggest that the proposed DeepGraph approach is effective and competitive.
strength_and_weaknesses: Strengths:
1) The paper tries to provide both theoretical and empirical insights on the importance of substructure sensitivity to the capacity of graph transformers.
2) The writing is generally clear.
3) I think the problem in itself is interesting (i.e., how can we train deeper graph transformers).
4) Good empirical results and ablative studies.

Weaknesses/questions:
1) While it's nice that the paper provides theoretical analysis on the model capacity, it is unclear to me how meaningful they are. Specifically, for example:
    - Inequality (6) provides an upper bound. In practice, $C_1$ and $C_2$ also depends on $H_\ell$, so they are not independent. This makes the inequality (12) in the Appendix potentially vacuous. Moreover, while $\alpha_i$ is accumulated in inequality (6) across layers indeed, it is unclear how $W_\ell^{VO}$ (which is learnable) evolves across depth. Could it balance this decay process? As another example, Theorem 3 is merely comparing two upper bounds. Without any evidence on the looseness of these upper bounds, it's hard to evaluate the value of this theorem. It'd be great if the authors could elaborate on issues like these.
    - The theoretical results applies mainly to the input level. $G_1^S, \dots, G_m^S$ makes sense at the input layer where each node contains the information only about itself. But starting from layer 2, the hidden units already combines information from all lower-level nodes, making the substructure argument a bit vague.
2) Given the assumptions, the theoretical results should also largely apply to the original (non-graph) transformers, such as those used in NLP. And yet we are able to train very deep transformers there, even though substructures do exist in language. Could the authors discuss more what their results imply in non-graph applications?
3) Do techniques that allow very deep training of conventional transformers help deepen graph transformers (e.g., ReZero)? This would be an interesting ablative study that demonstrates why the substructure attention is a better alternative for graphs.
4) For PCQM4M-LSC and ZINC, the # of nodes in these tasks is usually very small (e.g., <60). I'm a bit surprised that substructure is still very useful in these cases as global attention is not operating on a huge graph anyway.
5) Could the authors provide the # of parameters for each model in Table 1?
clarity,_quality,_novelty_and_reproducibility: The paper is generally quite clear, and the empirical studies is relatively extensive. I did not check the math carefully but I did go through all of the proof. The paper provides a good insight to an important problem that exists in graph transformers, and the empirical results seem solid. However, structural encodings is not a completely new idea. The authors mentioned that the code will be provided.
summary_of_the_review: Overall, I find the paper interesting and it provides a good insight into how substructure modeling plays a role in the attention and expressivity of modern graph transformers. There is still an obvious gap between the theory section and the empirical section (e.g., the paper did not empirically verify any of the theoretical conclusions), but the empirical results are quite good. I'm inclined to acceptance on the condition that my questions can be answered satisfactorily.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The author studies the effect of number of layers in graph transformer model, and claims that the previously used graph transformer layer has decreasing attention capacity on attending substructures with increasing attention layers. Then the author improves graph transformer with adding sampled substructures as token along with nodes. Extensive experiments over large real-world datasets are conducted to show its improvement.
strength_and_weaknesses: **Strength**: 
1. Substructure based GNNs are widely explored last year and also influences the graph transformer area. It's interesting to see that adding substructure directly helps improving current graph transformers.
2. The author proposes a measure to define the attention capacity for substructures. This is an interesting angle. 
3. The improvement over real-world dataset is great, especially on PATTERN dataset. 

**Weakness**:
1. Notation and writing is not clear and is too hard to follow. I suggest the author to revise the paper extensively to make the notation easier to follow. For example, the author use $G^S$ for general notation of subgraph, which is really confusing as I was originally thinking that $G^S = G[S]$ representing the set S induced subgraph on G.  For general subgraph pattern, I suggest the author remove the G notation, just use something like $S$ directly, as there is no relation to G. The section 4 needs to be greatly improved. For example, even the first paragraph inside 4.1 is hard to follow. All notations of graph, subgraph, pattern, and support are too hard to follow. Also $supp(e) \subseteq  N^S$ instead of $supp(e) \in  N^S$. There are so many confusing notations and I cannot read and evaluate the section 4. Another example is the $\triangle$ notation...it represents easy stuff in principle but the notation makes the easy stuff hard to interpret. Again, like $Attn_{A}$,  the underscript is never mentioned before using. 
2. Definition 1 of measuring attention capacity is questionable. There are learnable W inside and it's not possible to analyze the F norm directly, as W can have any scale to enlarge the F norm. Also, there is no relationship between small F norm and substructure indistinguishability. (a-b small doesn't imply a=b for graph separation case) I suggest the author at least give some empirical example to link the small F norm and the bad ability of identifying substructure. 
3. Theorem 1 and Theorem 2 I cannot read yet, after the author revise the section 4 I would like to check the theorem correctness. 
4. Section 5 substructure sampling is very similar to the one designed in [Zhao et al. ICLR 22]. The author should mention with reference. 
5. The designed method is a special case of [Kim et al. NeurIPS 22], and it doesn't provide much new contribution to model design. 
6. The ZINC experiment may need 500K parameter restriction in comparison. 

[Kim et al. NeurIPS 22] Pure transformer are powerful graph learners. 
[Zhao et al. ICLR 22] From stars to subgraphs 


clarity,_quality,_novelty_and_reproducibility: Clarity can be improved. Quality is limited by novelty in model design. However if the theoretical analysis is correct, the novelty can be improved. Please see the comments about Definition 1 and Theorem 1,2. 
summary_of_the_review: The author added substructure tokens to current graph transformer and show empirically improvement. In the meantime, the author try to answer why increasing depth doesn't benefit the performance for previous graph transformers, with a measure of attention capacity. However the relationship between the defined attention capacity and the empirical performance drop of increasing depth is not clear.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper shows the theoretical bottleneck on attention capacity for transformer depth scaling and proposed a new graph transformer model called DeepGraph to address it. The proposed architecture relies on substructure-based attention mechanism, where there are extra substructure tokens that correspond to sampled substructures. Specifically, each substructure token only attends to tokens within it. The model is shown to increase performance on several datasets as depth increases.
strength_and_weaknesses: Strength
- Depth limitation of gnns and graph transformers has been a key issue in graph ML. The theoretical analysis reveals insights for solving this. 
- The proposed method is conceptually simple and motivated by theoretical results.
- The proposed method is tested over a diverse set of datasets and tasks and demonstrates empirical gains.

Weaknesses
- The performance improvements with depth seem pretty small relative to the variances on most datasets.
- The method seems not completely correspond to the theoretical motivation: in theorem 3 substructure based local attention is defined as  "where each node only attends nodes that belong to the same substructures". If I understand correctly, in DeepGraph each node can still attend to all other nodes, but only that the substructure token only attends to and by the nodes in the substructure. Can this be further justified?
clarity,_quality,_novelty_and_reproducibility: The work is novel to the best of my knowledge and seems of high quality. The paper is clearly written mostly, with small confusing bits potentially due to typos. Specifically, in the definition of M_{ij} under equation 10, should it be i \in {...} instead of i+n \in {...}? Or is there some special relation between node i and substructure i + n? 

summary_of_the_review: Overall, the paper is addressing an important issue. The theoretical results and proposed methods seem sound and well tested. The concern is about the significance of the experimental results on depth improvement.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: In this paper, the authors first theoretically present the bottleneck of graph transformers’ performance with depth. The authors then propose a simple but effective substructure token based local attention mechanism in graph transformer, promoting focus on local substructure features of deeper graph transformer. Empirical results show that the proposed achieves state-of-the-art results on standard graph benchmarks with deeper models.
strength_and_weaknesses: Strengths:
- The theory proposed looks interesting, and the corresponding transformer structure introduced also look very novel.
- The authors conducted experiments on various benchmarks and the results look very competitive.
- The paper is clearly written and the motivation is easy to follow.

Weaknesses:
- Why there's such a negative correlation for Graph Transformer, while for Transformer in NLP the case is the larger, the better? Does the theoretical analysis also apply to Transformer in NLP?
- The proposed method has so many different designs so that it's hard to tell whether the proposed theory can justify what actually happened. Specifically, the authors proposed to tokenizing substructures subsampled from the graph. This is very different from the previous Graph Transformers as there's no sampling before.
- The authors didn't discuss the runtime overhead of the proposed method. Is it feasible to scale the proposed method on larger graphs?
- There isn't much ablation study in the paper. Specifically, the authors should study the size of substructure and how it affects the performance degradation with increased depth.
clarity,_quality,_novelty_and_reproducibility: The paper is clearly written and easy to follow.
The novelty of the proposed method looks significant.
There isn't much implementation detail provided so I feel it's nontrivial to reproduce the exact model.

summary_of_the_review: This paper provides interesting theoretical results and novel Graph Transformer design. The empirical results look good but not enough ablation studies. There's a nontrivial gap between the theory and the actual method proposed.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The paper proposes the "DeepGraph" approach which aims to alleviate the limitations in deepening graph transformers. They argue that capturing substructure information becomes increasingly harder as the depth of the model increases, and hence proposes a variant of graph transformers which incorporates substructure tokens and attention into the transformer model.

In general, reviewers appreciated the conceptually simple idea, and agreed that the approach is well-motivated by a clear goal of deepening graph transformers, including theoretical analysis on attention capacity, and the empirical gains are overall convincing. At the same time, some issues were also raised, particularly regarding the meaningfulness of the theoretical results, and some clarity issues. 

During the rebuttal stage, the author response made a range of improvements to the paper, which helped to address some of the reviewer concerns and improve the paper, such as adding improvements to the clarity, and adding various empirical studies regarding time complexity, ablations, empirical study of theoretical results, etc. I thank the authors for their efforts in addressing the reviewer concerns and making comprehensive improvements to the paper, which has significantly improved its quality.

Since this was a borderline paper, a virtual meeting was conducted. Reviewers generally agreed that many of the initial concerns had been successfully addressed. There were some questions regarding the relationship of the method to related work, such as TokenGT, but we feel that these were well-addressed by the authors. Overall, reviewers agreed that while the model has similarity to some approaches such as subgraph GNNs, such subgraph approaches are less well explored for Transforrmer models, so there is still sufficient innovation compared to existing approaches. With regard to writing quality, reviewers felt that the paper has been improved significantly and is of satisfactory quality, though some typos / editing may still be required. 

There were still some remaining questions, particularly regarding the meaningfulness of the theoretical results; however, on the whole we feel that the paper still presents an intriguing angle on the issue of depth in graph transformers, as well as empirical findings which can spur follow-up investigations on this question, by providing a clear analysis on the depth limitation issue, showing that their model successfully alleviates this issue, and presenting theoretical analysis on the attention capacity issue. 

In the end, reviewers and AC find that the paper is well-motivated, and provides a novel and interesting angle on the depth limitation of graph transformers, as well as theoretical analysis and convincing performance gains. Hence, I recommend acceptance. 
justification_for_why_not_higher_score: There are still some issues, particularly on the meaningfulness of the theoretical results, as well as writing quality and clarity.
justification_for_why_not_lower_score: The paper presents an interesting and well-motivated analysis on the issue of depth in graph transformers, as well as interesting empirical and theoretical findings that can spur further analysis and investigation.
Decision: Accept: poster