Graph 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. We investigate a comprehensive class of versions of the Weisfeiler-Leman algorithm obtained by modifying the underlying logical framework and establish a precise theoretical characterization of their expressive power. We then test selected versions on 14 benchmark datasets that span a range of application domains. The experiments demonstrate that our approach generally achieves better predictive performance than graph neural networks and matches that of graph transformers, while being 40-60x faster and requiring neither a GPU nor extensive hyperparameter tuning.