On the Power of the Weisfeiler-Leman Test for Graph Motif Parameters

arXiv:2309.17053v3 Announce Type: replace
Abstract: Seminal research in the field of graph neural networks (GNNs) has revealed a direct correspondence between the expressive capabilities of GNNs and the $k$-dimensional Weisfeiler-Leman ($k$WL) test, a widely-recognized method for verifying graph isomorphism. This connection has reignited interest in comprehending the specific graph properties effectively distinguishable by the $k$WL test. A central focus of research in this field revolves around determining the least dimensionality $k$, for which $k$WL can discern graphs with different number …

abstract arxiv capabilities cs.lg gnns graph graph neural networks motif networks neural networks parameters power research test type