3 papers
cs.LG2026
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…
cs.LG2025
Repetition Makes Perfect: Recurrent Graph Neural Networks Match Message-Passing Limit
Eran Rosenbluth, Martin Grohe
We precisely characterize the expressivity of computable Recurrent Graph Neural Networks (recurrent GNNs). We prove that recurrent GNNs with finite-precision parameters, sum aggreg…
cs.LG2024
Distinguished In Uniform: Self Attention Vs. Virtual Nodes
Eran Rosenbluth, Jan Tönshoff, Martin Ritzert +2
Graph Transformers (GTs) such as SAN and GPS are graph processing models that combine Message-Passing GNNs (MPGNNs) with global Self-Attention. They were shown to be universal func…