Weisfeiler and Leman Go Measurement Modeling: Probing the Validity of the WL Test

arXiv:2307.05775v3 Announce Type: replace
Abstract: The expressive power of graph neural networks is usually measured by comparing how many pairs of graphs or nodes an architecture can possibly distinguish as non-isomorphic to those distinguishable by the $k$-dimensional Weisfeiler-Leman ($k$-WL) test. In this paper, we uncover misalignments between graph machine learning practitioners' conceptualizations of expressive power and $k$-WL through a systematic analysis of the reliability and validity of $k$-WL. We conduct a survey ($n = 18$) of practitioners to surface their …

abstract architecture arxiv cs.lg cs.si graph graph neural networks graphs measurement modeling networks neural networks nodes paper power test type