What Expressivity Theory Misses: Message Passing Complexity for GNNs

TL;DR

Expressivity theory, characterizing which graphs a GNN can distinguish, has become the predominant framework for analyzing GNNs, with new models striving for higher expressivity…

Opening excerpt from the authors’ abstract. source