Fine-Grained Expressive Power of Weisfeiler-Leman: A Homomorphism Counting Perspective

Junru Zhou, Muhan Zhang

The ability of graph neural networks (GNNs) to count homomorphisms has recently been proposed as a practical and fine-grained measure of their expressive power. Although several ex…