Aligning Transformers with Weisfeiler-Leman
Graph neural network architectures aligned with the $k$-dimensional Weisfeiler--Leman ($k$-WL) hierarchy offer theoretically well-understood expressive power. However, these architectures often fail to deliver state-of-the-art predictive performance on real-world graphs, limiting their practical utility. While recent works aligning graph transformer architectures with the $k$-WL hierarchy have shown promising empirical results, employing transformers for higher orders of $k$ remains challenging due to a prohibitive runtime and memory complexity of self-attention as well as impractical architectural assumptions, such as an infeasible number of attention heads. Here, we advance the alignment of transformers with the $k$-WL hierarchy, showing stronger expressivity results for each $k$, making them more feasible in practice. In addition, we develop a theoretical framework that allows the study of established positional encodings such as Laplacian PEs and SPE. We evaluate our transformers on the large-scale PCQM4Mv2 dataset, showing competitive predictive performance with the state-of-the-art and demonstrating strong downstream performance when fine-tuning them on small-scale molecular datasets. Our code is available at https://github.com/luis-mueller/wl-transformers.
Code (1)
Tasks
Graph Neural NetworkMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Weisfeiler and Leman Go Walking: Random Walk Kernels Revisited
Random walk kernels have been introduced in seminal work on graph learning and were later largely superseded by kernels based on the Weisfeiler-Leman test for graph isomorphism. We give a unified view on both classes of …
Graph LearningGraph Learning via Logic-Based Weisfeiler-Leman Variants and Tabularization
We present a novel approach for graph classification based on tabularizing graph data via new variants of the Weisfeiler-Leman algorithm and then applying methods for tabular data. The variants are obtained by modifying …
Graph ClassificationGraph LearningWalking Out of the Weisfeiler Leman Hierarchy: Graph Learning Beyond Message Passing
We propose CRaWl, a novel neural network architecture for graph learning. Like graph neural networks, CRaWl layers update node features on a graph and thus can freely be combined or interleaved with GNN layers. Yet CRaWl…
Graph ClassificationGraph LearningGraph RegressionregressionWeisfeiler and Leman Go Relational
Knowledge graphs, modeling multi-relational data, improve numerous applications such as question answering or graph logical reasoning. Many graph neural networks for such data emerged recently, often outperforming shallo…
Knowledge GraphsLogical ReasoningQuestion AnsweringThe Power of the Weisfeiler-Leman Algorithm for Machine Learning with Graphs
In recent years, algorithms and neural architectures based on the Weisfeiler-Leman algorithm, a well-known heuristic for the graph isomorphism problem, emerged as a powerful tool for (supervised) machine learning with gr…
BIG-bench Machine LearningNode Classification