Graph Learning via Logic-Based Weisfeiler-Leman Variants and Tabularization
This provides a more efficient alternative for graph classification tasks across various domains, though it appears incremental as it builds on existing Weisfeiler-Leman methods.
The paper tackles graph classification by tabularizing graph data using logic-based Weisfeiler-Leman variants, achieving accuracy matching state-of-the-art graph neural networks and kernels with improved time or memory efficiency on twelve benchmark datasets.
We present a novel approach for graph classification based on tabularizing graph data via variants of the Weisfeiler-Leman algorithm and then applying methods for tabular data. We investigate a comprehensive class of Weisfeiler-Leman variants obtained by modifying the underlying logical framework and establish a precise theoretical characterization of their expressive power. We then test two selected variants on twelve benchmark datasets that span a range of different domains. The experiments demonstrate that our approach matches the accuracy of state-of-the-art graph neural networks and graph kernels while being more time or memory efficient, depending on the dataset. We also briefly discuss directly extracting interpretable modal logic formulas from graph datasets.