Skip to yearly menu bar Skip to main content


Poster

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

Matthias Lanzinger · Pablo Barcelo

Halle B #99

Abstract: Seminal research in the field of graph neural networks (GNNs) has revealed a direct correspondence between the expressive capabilities of GNNs and the kk-dimensional Weisfeiler-Leman (kkWL) test, a widely-recognized method for verifying graph isomorphism. This connection has reignited interest in comprehending the specific graph properties effectively distinguishable by the kkWL test.A central focus of research in this field revolves around determining the least dimensionality kk, for which kkWL can discern graphs with different number of occurrences of a pattern graph pp. We refer to such a least kk as the WL-dimension of this pattern counting problem. This inquiry traditionally delves into two distinct counting problems related to patterns: subgraph counting and induced subgraph counting. Intriguingly, despite their initial appearance as separate challenges with seemingly divergent approaches, both of these problems are interconnected components of a more comprehensive problem: "graph motif parameters". In this paper, we provide a precise characterization of the WL-dimension of labeled graph motif parameters. As specific instances of this result, we obtain characterizations of the WL-dimension of the subgraph counting and induced subgraph counting problem for every labeled pattern pp. Particularly noteworthy is our resolution of a problem left open in previous work concerning induced copies.We additionally demonstrate that in cases where the kkWL test distinguishes between graphs with varying occurrences of a pattern pp, the exact number of occurrences of pp can be computed uniformly using only local information of the last layer of a corresponding GNN.We finally delve into the challenge of recognizing the WL-dimension of various graph parameters. We give a polynomial time algorithm for determining the WL-dimension of the subgraph counting problem for given pattern pp, answering an open question from previous work.We additionally show how to utilize deep results from the field of graph motif parameters, together with our characterization, to determine the WL-dimension of induced subgraph counting and counting kk-graphlets.

Chat is not available.