mlsanityData to 7 Oct 2026

Some Might Say All You Need Is Sum

arXiv 2302.11603 ↗First posted 22 Feb 2023cs.LGcited by 21

Not on the map. Why?

Abstract (arXiv)

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 other GNNs, while certain practical works have observed a clear advantage to using Mean and Max. An examination of the theoretical guarantee identifies two caveats. First, it is size-restricted, that is, the power of every specific GNN is limited to graphs of a specific size. Successfully processing larger graphs may require an other GNN, and so on. Second, it concerns the power to distinguish non-isomorphic graphs, not the power to approximate general functions on graphs, and the former does not necessarily imply the latter. It is desired that a GNN's usability will not be limited to graphs of any specific size. Therefore, we explore the realm of unrestricted-size expressivity. We prove that basic functions, which can be computed exactly by Mean or Max GNNs, are inapproximable by any Sum GNN. We prove that under certain restrictions, every Mean or Max GNN can be approximated by a Sum GNN, but even there, a combination of (Sum, [Mean/Max]) is more expressive than Sum alone. Lastly, we prove further expressivity limitations for GNNs with a broad class of aggregations.

Key facts. Cited by 21 papers in the map (data through 7 Oct 2026). Builds on 19 of its 37 references that are in the map. First posted on arXiv 22 Feb 2023.

Builds on

19 of 37 references.

References · 19

  1. 2014Adam: A Method for Stochastic Optimizationcited by 36,960
  2. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,282
  3. 2017Inductive Representation Learning on Large Graphscited by 6,284
  4. 2016SGDR: Stochastic Gradient Descent with Warm Restartscited by 4,993
  5. 2018How Powerful are Graph Neural Networks?cited by 4,355
  6. 2017Neural Message Passing for Quantum Chemistrycited by 3,460
  7. 2019A Comprehensive Survey on Graph Neural Networkscited by 2,906
  8. 2019Fast Graph Representation Learning with PyTorch Geometriccited by 2,414
  9. 2018Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networkscited by 878
  10. 2020Principal Neighbourhood Aggregation for Graph Netscited by 477
  11. 2019Provably Powerful Graph Networkscited by 385
  12. 2021Combinatorial optimization and reasoning with graph neural networkscited by 267
7 more
  1. 2020The Surprising Power of Graph Neural Networks with Random Node Initializationcited by 190
  2. 2020Random Features Strengthen Graph Neural Networkscited by 184
  3. 2019On the equivalence between graph isomorphism testing and function approximation with GNNscited by 172
  4. 2021The Logic of Graph Neural Networkscited by 84
  5. 2022Expressiveness and Approximation Properties of Graph Neural Networkscited by 63
  6. 2021Graph Neural Networks with Local Graph Parameterscited by 51
  7. 2022One Model, Any CSP: Graph Neural Networks as Fast Global Search Heuristics for Constraint Satisfactioncited by 27

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 4; 2024: 8; 2025: 5; 2026: 4.

21 papers.

Sort:

  1. 2023The Descriptive Complexity of Graph Neural Networkscited by 26
  2. 2023Fine-grained Expressivity of Graph Neural Networkscited by 25
  3. 2024Distinguished In Uniform: Self Attention Vs. Virtual Nodescited by 19
  4. 2023Rank Collapse Causes Over-Smoothing and Over-Correlation in Graph Neural Networkscited by 18
  5. 2024Weisfeiler-Leman at the margin: When more expressivity matterscited by 13
  6. 2024Bundle Neural Networks for message diffusion on graphscited by 13
  7. 2024Attention as a Hypernetworkcited by 12
  8. 2024Almost Surely Asymptotically Constant Graph Neural Networkscited by 7
  9. 2025Logical Characterizations of GNNs with Mean Aggregationcited by 6
  10. 2025Exact Verification of Graph Neural Networks with Incremental Constraint Solvingcited by 4
  11. 2024Graph Neural Networks and Arithmetic Circuitscited by 3
  12. 2025Verifying Quantized Graph Neural Networks is PSPACE-completecited by 2
9 more
  1. 2025Repetition Makes Perfect: Recurrent Graph Neural Networks Match Message-Passing Limitcited by 2
  2. 2024Are Targeted Messages More Effective?cited by 1
  3. 2024MEGA: Message Passing Neural Networks for Multigraphs with EdGe Attributescited by 1
  4. 2025Sound Logical Explanations for Mean Aggregation Graph Neural Networkscited by 1
  5. 2023The logic of rational graph neural networkscited by 0
  6. 2026Investigating GNN Convergence on Large Randomly Generated Graphs with Realistic Node Feature Correlationscited by 0
  7. 2026Lost in Aggregation: On a Fundamental Expressivity Limit of Message-Passing Graph Neural Networkscited by 0
  8. 2026The Polynomial Counting Capabilities of Message Passing Neural Networkscited by 0
  9. 2026Warm-starting PDE solvers with any-dimensional machine learningcited by 0