1 citations · 1 across the 6 of their papers we have counts for
7 papers
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…
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…
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…
Are Targeted Messages More Effective?
Martin Grohe, Eran Rosenbluth
Graph neural networks (GNN) are deep learning architectures for graphs. Essentially, a GNN is a distributed message passing algorithm, which is controlled by parameters learned fro…
Where Did the Gap Go? Reassessing the Long-Range Graph Benchmark
Jan Tönshoff, Martin Ritzert, Eran Rosenbluth +1
The recent Long-Range Graph Benchmark (LRGB, Dwivedi et al. 2022) introduced a set of graph learning tasks strongly dependent on long-range interaction between vertices. Empirical…
The Solidarity Cover Problem
Eran Rosenbluth
Various real-world problems consist of partitioning a set of locations into disjoint subsets, each subset spread in a way that it covers the whole set with a certain radius. Given…
Some Might Say All You Need Is Sum
Eran Rosenbluth, Jan Toenshoff, Martin Grohe
The expressivity of Graph Neural Networks (GNNs) is dependent on the aggregation functions they employ. Theoretical works have pointed towards Sum aggregation GNNs subsuming every…