mlsanityData to 14 Oct 2026

Logical Characterizations of GNNs with Mean Aggregation

arXiv 2507.18145 ↗First posted 24 Jul 2025cs.AI cs.LOcited by 6

Not on the map. Why?

Abstract (arXiv)

We study the expressive power of graph neural networks (GNNs) with mean as the aggregation function, with the following results. In the non-uniform setting, such GNNs have exactly the same expressive power as ratio modal logic, which has modal operators expressing that at least a certain ratio of the successors of a vertex satisfies a specified property. In the uniform setting, the expressive power relative to MSO is exactly that of modal logic, and thus identical to the (absolute) expressive power of GNNs with max aggregation. The proof, however, depends on constructions that are not satisfactory from a practical perspective. This leads us to making the natural assumptions that combination functions are continuous and classification functions are thresholds. The resulting class of GNNs with mean aggregation turns out to be much less expressive: relative to MSO and in the uniform setting, it has the same expressive power as alternation-free modal logic. This is in contrast to the expressive power of GNNs with max and sum aggregation, which is not affected by these assumptions.

Key facts. Cited by 6 papers in the map (data through 14 Oct 2026). Builds on 14 of its 40 references that are in the map. First posted on arXiv 24 Jul 2025.

Builds on

14 of 40 references.

References · 14

  1. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,361
  2. 2017Inductive Representation Learning on Large Graphscited by 6,320
  3. 2018How Powerful are Graph Neural Networks?cited by 4,393
  4. 2019A Comprehensive Survey on Graph Neural Networkscited by 2,919
  5. 2018Graph Neural Networks: A Review of Methods and Applicationscited by 1,576
  6. 2018Graph Convolutional Neural Networks for Web-Scale Recommender Systemscited by 1,138
  7. 2020Graph Neural Networks in Recommender Systems: A Surveycited by 494
  8. 2021Graph Neural Network-Based Anomaly Detection in Multivariate Time Seriescited by 301
  9. 2021Graph Neural Network for Traffic Forecasting: A Surveycited by 261
  10. 2020Molecular graph generation with Graph Neural Networkscited by 80
  11. 2023Some Might Say All You Need Is Sumcited by 21
  12. 2019Graded modal logic and counting bisimulationcited by 13
2 more
  1. 2024Logical Characterizations of Recurrent Graph Neural Networks with Reals and Floatscited by 13
  2. 2023On the Correspondence Between Monotonic Max-Sum GNNs and Datalogcited by 12

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2025: 2; 2026: 4.

6 papers.

  1. 2025Exact Verification of Graph Neural Networks with Incremental Constraint Solvingcited by 4
  2. 2025Sound Logical Explanations for Mean Aggregation Graph Neural Networkscited by 2
  3. 2026How Expressive Are Graph Neural Networks in the Presence of Node Identifiers?cited by 1
  4. 2026Towards Understanding the Expressive Power of GNNs with Global Readoutcited by 0
  5. 2026The Polynomial Counting Capabilities of Message Passing Neural Networkscited by 0
  6. 2026Recurrent Graph Neural Networks with Set-Based Aggregationcited by 0