Towards Principled Graph Transformers

Summary

This paper introduces a novel architecture called Edge Transformer (ET) for graph learning tasks. The ET leverages global attention on node pairs instead of individual nodes and demonstrates strong empirical performance without relying on positional or structural encodings. The authors show that ET has the expressive power of 3-WL and achieves competitive results on algorithmic reasoning and molecular regression tasks.

Strengths

1、ET bridges the gap between theoretical expressivity and practical performance. 2、The paper provides comprehensive empirical evidence demonstrating that the Edge Transformer outperforms existing theoretically motivated models and competes well with state-of-the-art models in various graph learning tasks.

Weaknesses

1、The total number of parameters for the model is not provided in the parameter table. 2、While ET is more efficient than some other high-order transformers, it is still significantly inferior to most graph transformers with O(n^2). This limits the applicability of ET. 3、The author's contribution is confined to applying the ET model to the graph, without proposing their own method.

Questions

1、Can you provide possible ways to reduce the complexity of ET? 2、Can you provide the total number of parameters for ET on each dataset? See Weaknesses 1. 3、Why has the performance changed so much compared to the submitted version of ICML in 2024? Especially on the Searching dataset. 4、What do Average and All algorithms represent respectively?

Rating

1

Confidence

5

Soundness

2

Presentation

2

Contribution

2

Limitations

See Weaknesses.

Summary

In this paper, the authors show that Edge Transformer, a global attention model operating on node pairs, has 3-WL expressive power when provided with the right tokenization. Experiments results also show that the Edge Transformer has competitive performance on molecular regression tasks and algorithmic reasoning.

Strengths

1. This paper proposes a concrete implementation of the Edge Transformer, and proves that it has an expressive power of 3-WL. 2. The proposed ET has superior empirical performance on molecular regression and neural algorithmic reasoning tasks.

Weaknesses

1. My major concern is the real usefulness of ET, since the high runtime and memory complexity may offset the importance of ET, though the authors discuss it in Limitations. Also, it is not clear what is the parameter count, which raises the question that the better performance of ET may be mainly from large number of parameters. 2. It seems that the ET in this paper is mainly from existing work, and the difference needs to be explained.

Questions

1. The ET in this paper is a variant of existing ones, due to the specific tokenization. But it is not quite clear to me what are the main differences of the tokenization compared with existing ones, and why this tokenization can help the 3-WL. It would be good if the authors provide more details. 2. In Table 1, ET with RRWP has a little bit lower performance on QW9. Can the authors elaborate on this? Since generally, transformers with positional encodings will lead to improved performance. 3. The authors emphasize that the designed ET can achieve superior performance even without positional encodings. But maybe as an open question, if incorporated with PEs, will the theoretical results change? [1] Comparing Graph Transformers via Positional Encodings, ICML 2024

Rating

6

Confidence

4

Soundness

3

Presentation

3

Contribution

2

Limitations

Scalability limitations are discussed.

Summary

This paper applies Edge Transformer (ET) to the field of graph learning. It is proved that ET has 3-WL expressivity with cubic complexity, which is more efficient than existing 3-WL models. Experiments on BREC benchmark clearly demonstrate its expressive power. Results on the other three molecular datasets and CLRS benchmark are also provided.

Strengths

- It proves ET has 3-WL expressive power and demonstrates excellent results on BREC benchmark. Even though it has $O(n^3)$ complexity, it is still more efficient than other 3-WL models. - It shows good performance on real-world graph learning tasks. - The paper is well-written and easy to follow.

Weaknesses

- My major concern is about empirical evaluation. - While I appreciate ET's excellent theoretical expressive power, I find it is needed to include more benchmark datasets in graph learning (e.g., OGB, moleculeNet, GNN benchmark, Long Rang Graph Benchmark, Zinc-full, etc) to comprehensively demonstrate its practical predictive power compared with state-of-the-art (SOTA) methods, e.g., those graph transformers Grit, Exphormer, GraphGPS, etc. - Besides datasets from algorithmic reasoning, currently, in my opinion, ET is only evaluated on two widely-used graph benchmark datasets with performance reported from very recent SOTA methods, i.e., Zinc-12k and Alchemy-12k, making it hard to assess ET's practical performance. Although QM9 is also a popular dataset, the adopted setting is less common. Meanwhile, Zinc-12k is just a small subset of Zinc-full, and it has recently been shown that being good at Zinc-12k does not necessarily lead to the best performance on Zinc-full [1]. - It would be interesting to see its long-range modeling capability on the LRGB benchmark as it's a transformer. - In terms of the evaluation of expressive power, it would be better to include SOTA methods such as those subgraph-GNNs, potentially also discussing their complexity compared to ET. [1] Wang, X., Li, P., & Zhang, M. (2024). Graph as Point Set. ICML 2024.

Questions

- How does the setting of QM9 used in this paper differ from the setting that is commonly used in equivariant GNNs (e.g., EGNN, DimeNet, etc)? It would be better if this description could be put in the paper, making it self-contained. - Are there any particular benefits to having an expressive model without using PE or SE? I consider the major benefit would be on the computation side as computing PE can be $O(n^2)$, but ET has already had $O(n^3)$ complexity. So, for the claim in the paper, is it just because it would be more challenging to analyze expressive power with PE/SE, therefore it would be easier to understand a model's expressive power without using them? - I feel like depending on how PE is used, it is still possible to analyze the expressive power, e.g., via graph substructure counting. Can the authors discuss the works such as graph as point set and those subgraph-GNNs? Because they may also use PE, while proving their expressive power via graph substructure counting.

Rating

5

Confidence

4

Soundness

2

Presentation

4

Contribution

2

Limitations

See above.

Summary

This work proposes an Edge Transformer (ET), a global attention model operating on node pairs instead of nodes. Authors theoretically demonstrate that ET has 3-WL expressive power with the proper tokenization. Experimental results demonstrate that the proposed model outperforms other theoretically aligned models in terms of predictive performance. Additionally, ET competes with state-of-the-art models in algorithmic reasoning and molecular regression tasks without relying on positional or structural encodings.

Strengths

1. The paper is well-written. All technical steps are easy to follow. 2. The proposed triangular attention is interesting and novel. 3. ET achieves impressive results for both molecular regression and algorithmic reasoning tasks.

Weaknesses

1. Previous work [1] has demonstrated that graph transformers (GTs) with proper positional encodings (PEs) can be more powerful than any WL test. Therefore, it is unclear why the authors aim to develop a model with 3-WL expressive power, which cannot be more expressive than prior GTs (e.g., [1]). Notably, given the cubic complexity of the proposed ET, computing PEs is no longer a scalability bottleneck. Consequently, if ET empirically outperforms GT+PE, it essentially implies that the WL hierarchy is not a meaningful metric in practice, undermining the purpose of building a 3-WL expressive model. 2. While the authors mention how to apply ET for node-level tasks, they provide no corresponding results. Given the cubic complexity of ET, it is likely not scalable to most graphs for node-level tasks. 3. Some relevant GT models haven't been discussed or compared (e.g., [1-3]). [1] Kreuzer et al., "Rethinking Graph Transformers with Spectral Attention", NeurIPS'21. \ [2] Zhu et al., "On Structural Expressive Power of Graph Transformers", KDD'23. \ [3] Deng et al., "Polynormer: Polynomial-Expressive Graph Transformer in Linear Time", ICLR'24.

Questions

N/A

Rating

7

Confidence

4

Soundness

3

Presentation

3

Contribution

3

Limitations

Please refer to the Weaknesses section for details.