Overall, the quantitative understanding of the complexity of simulating WL remains an open problem. Indeed, the survey [1]} states “The size of the GNNs and related parameters like depth and width, which directly affect the complexity of inference and learning, definitely require close attention.”
