The Logic of Graph Neural Networks
This work provides foundational insights into GNN expressiveness, benefiting researchers in graph machine learning, but it is incremental as it explains existing characterizations rather than introducing new ones.
The paper tackles the problem of characterizing the expressiveness of graph neural networks (GNNs) by explaining their correspondence with combinatorial Weisfeiler-Leman algorithms and finite variable counting logics, which has led to the development of new, higher-order GNNs.
Graph neural networks (GNNs) are deep learning architectures for machine learning problems on graphs. It has recently been shown that the expressiveness of GNNs can be characterised precisely by the combinatorial Weisfeiler-Leman algorithms and by finite variable counting logics. The correspondence has even led to new, higher-order GNNs corresponding to the WL algorithm in higher dimensions. The purpose of this paper is to explain these descriptive characterisations of GNNs.