# Graph Learning via Logic-Based Weisfeiler-Leman Variants and Tabularization

arXiv: https://arxiv.org/abs/2508.10651 · HTML: https://mlsanity.com/paper/2508.10651/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 19 of its 40 references that are in the map.
- First posted on arXiv 14 Aug 2025.

## Builds on (most cited first, 19 of 19)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [A Comprehensive Survey on Graph Neural Networks](https://mlsanity.com/paper/1901.00596/) (2019)
- [Optuna: A Next-generation Hyperparameter Optimization Framework](https://mlsanity.com/paper/1907.10902/) (2019)
- [Fast Graph Representation Learning with PyTorch Geometric](https://mlsanity.com/paper/1903.02428/) (2019)
- [Open Graph Benchmark: Datasets for Machine Learning on Graphs](https://mlsanity.com/paper/2005.00687/) (2020)
- [TUDataset: A collection of benchmark datasets for learning with graphs](https://mlsanity.com/paper/2007.08663/) (2020)
- [Recipe for a General, Powerful, Scalable Graph Transformer](https://mlsanity.com/paper/2205.12454/) (2022)
- [Benchmarking Graph Neural Networks](https://mlsanity.com/paper/2003.00982/) (2020)
- [Long Range Graph Benchmark](https://mlsanity.com/paper/2206.08164/) (2022)
- [A Fair Comparison of Graph Neural Networks for Graph Classification](https://mlsanity.com/paper/1912.09893/) (2019)
- [Exphormer: Sparse Transformers for Graphs](https://mlsanity.com/paper/2303.06147/) (2023)
- [A Survey on Graph Kernels](https://mlsanity.com/paper/1903.11835/) (2019)
- [The Logic of Graph Neural Networks](https://mlsanity.com/paper/2104.14624/) (2021)
- [Where Did the Gap Go? Reassessing the Long-Range Graph Benchmark](https://mlsanity.com/paper/2309.00367/) (2023)
- [GraKeL: A Graph Kernel Library in Python](https://mlsanity.com/paper/1806.02193/) (2018)
- [Can Classic GNNs Be Strong Baselines for Graph-level Tasks? Simple Architectures Meet Excellence](https://mlsanity.com/paper/2502.09263/) (2025)
- [Graded modal logic and counting bisimulation](https://mlsanity.com/paper/1910.00039/) (2019)
- [Short Boolean Formulas as Explanations in Practice](https://mlsanity.com/paper/2307.06971/) (2023)

## Abstract (arXiv)

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 the underlying logical framework, and we establish a precise theoretical characterization of their expressive power using a novel generalization of the bisimulation game for generalized quantifiers. We then test our method on 14 datasets that span a range of application domains. The experiments demonstrate that on datasets with up to 40 000 samples, our approach generally matches the predictive performance of graph neural networks and graph transformers, without requiring a GPU or extensive hyperparameter tuning. Even when our method's tuning time is included and the baselines' is not, our method is 5-20 times faster. When tuning time is included for all methods, the gap is significantly greater in favour of our method.