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

Graph Neural Networks (GNNs) are a powerful solution in many settings where the data is naturally graph-structured; they enable us to learn not only from individual features of objects, but also from the connections between them [15, 20]. They make the graph topology a key part of the learning process, enabling more accurate results in a range of scenarios [19, 21]. However, graph learning is computationally expensive, and training GNNs is usually much slower than training for state of the art methods on tabular data [11, 5]. In this paper, we aim to achieve graph learning with simpler, more efficient methods for tabular data, after enriching graph nodes with information about the graph topology. Our stepping stone is the Weisfeiler-Leman algorithm (WL), a well-known technique for approximating graph isomorphism [18]. In addition to its many applications in graph theory and other areas of computer science, WL has been very influential in graph learning. It has been used in graph kernels, enabling algorithms such as support vector machines to operate directly on graphs [16, 11]. Crucially, it has been used to characterize the expressive power of several types of GNNs [8, 20, 1], suggesting WL as a suitable tool to distill the topological information that GNNs can learn from.