Lost in Aggregation: On a Fundamental Expressivity Limit of Message-Passing Graph Neural Networks

Eran Rosenbluth

We define an information-complexity property for aggregation functions, capturing a vast range of practical aggregations, and prove that any Message-Passing Graph Neural Network (M…