# Learnable Commutative Monoids for Graph Neural Networks

arXiv: https://arxiv.org/abs/2212.08541 · HTML: https://mlsanity.com/paper/2212.08541/

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- Builds on 27 of its 38 references that are in the map.
- First posted on arXiv 16 Dec 2022.

## Builds on (most cited first, 27 of 27)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [Open Graph Benchmark: Datasets for Machine Learning on Graphs](https://mlsanity.com/paper/2005.00687/) (2020)
- [Deep Sets](https://mlsanity.com/paper/1703.06114/) (2017)
- [On the Properties of Neural Machine Translation: Encoder-Decoder Approaches](https://mlsanity.com/paper/1409.1259/) (2014)
- [Geometric Deep Learning: Grids, Groups, Graphs, Geodesics, and Gauges](https://mlsanity.com/paper/2104.13478/) (2021)
- [Learning to Simulate Complex Physics with Graph Networks](https://mlsanity.com/paper/2002.09405/) (2020)
- [Representation Learning on Graphs with Jumping Knowledge Networks](https://mlsanity.com/paper/1806.03536/) (2018)
- [Benchmarking Graph Neural Networks](https://mlsanity.com/paper/2003.00982/) (2020)
- [Principal Neighbourhood Aggregation for Graph Nets](https://mlsanity.com/paper/2004.05718/) (2020)
- [DeeperGCN: All You Need to Train Deeper GCNs](https://mlsanity.com/paper/2006.07739/) (2020)
- [How Neural Networks Extrapolate: From Feedforward to Graph Neural Networks](https://mlsanity.com/paper/2009.11848/) (2020)
- [What Can Neural Networks Reason About?](https://mlsanity.com/paper/1905.13211/) (2019)
- [Neural Execution of Graph Algorithms](https://mlsanity.com/paper/1910.10593/) (2019)
- [Janossy Pooling: Learning Deep Permutation-Invariant Functions for Variable-Size Inputs](https://mlsanity.com/paper/1811.01900/) (2018)
- [On the Limitations of Representing Functions on Sets](https://mlsanity.com/paper/1901.09006/) (2019)
- [Can recurrent neural networks warp time?](https://mlsanity.com/paper/1804.11188/) (2018)
- [Graph Neural Networks are Dynamic Programmers](https://mlsanity.com/paper/2203.15544/) (2022)
- [Neural Execution Engines: Learning to Execute Subroutines](https://mlsanity.com/paper/2006.08084/) (2020)
- [Normalized Attention Without Probability Cage](https://mlsanity.com/paper/2005.09561/) (2020)
- [Regularizing Towards Permutation Invariance in Recurrent Models](https://mlsanity.com/paper/2010.13055/) (2020)
- [Learning Aggregation Functions](https://mlsanity.com/paper/2012.08482/) (2020)
- [Abelian Neural Networks](https://mlsanity.com/paper/2102.12232/) (2021)

## Built on by (most cited first, 13 of 13)

- [How does over-squashing affect the power of GNNs?](https://mlsanity.com/paper/2306.03589/) (2023)
- [Softmax is not Enough (for Sharp Size Generalisation)](https://mlsanity.com/paper/2410.01104/) (2024)
- [Asynchronous Algorithmic Alignment with Cocycles](https://mlsanity.com/paper/2306.15632/) (2023)
- [Categorical Foundations of Explainable AI: A Unifying Theory](https://mlsanity.com/paper/2304.14094/) (2023)
- [Recurrent Aggregators in Neural Algorithmic Reasoning](https://mlsanity.com/paper/2409.07154/) (2024)
- [What makes a good feedforward computational graph?](https://mlsanity.com/paper/2502.06751/) (2025)
- [Sequential Signal Mixing Aggregation for Message Passing Graph Neural Networks](https://mlsanity.com/paper/2409.19414/) (2024)
- [Probabilistic Invariant Learning with Randomized Linear Classifiers](https://mlsanity.com/paper/2308.04412/) (2023)
- [Revisiting Neighborhood Aggregation in Graph Neural Networks for Node Classification using Statistical Signal Processing](https://mlsanity.com/paper/2407.15284/) (2024)
- [Reforge: Low-Latency Distributed GNN Serving with Selective Embedding Recomputation](https://mlsanity.com/paper/2501.08547/) (2025)
- [Length Generalization with Log-Depth Recurrent Units](https://mlsanity.com/paper/2605.26035/) (2026)
- [Improving Set Function Approximation with Quasi-Arithmetic Neural Networks](https://mlsanity.com/paper/2602.04941/) (2026)
- [HiFi-LLP: High-Fidelity, Low-Cost Latency Predictors with Confidence for Robust HW-NAS](https://mlsanity.com/paper/2607.11746/) (2026)

## Abstract (arXiv)

Graph neural networks (GNNs) have been shown to be highly sensitive to the choice of aggregation function. While summing over a node's neighbours can approximate any permutation-invariant function over discrete inputs, Cohen-Karlik et al. [2020] proved there are set-aggregation problems for which summing cannot generalise to unbounded inputs, proposing recurrent neural networks regularised towards permutation-invariance as a more expressive aggregator. We show that these results carry over to the graph domain: GNNs equipped with recurrent aggregators are competitive with state-of-the-art permutation-invariant aggregators, on both synthetic benchmarks and real-world problems. However, despite the benefits of recurrent aggregators, their O(V) depth makes them both difficult to parallelise and harder to train on large graphs. Inspired by the observation that a well-behaved aggregator for a GNN is a commutative monoid over its latent space, we propose a framework for constructing learnable, commutative, associative binary operators. And with this, we construct an aggregator of O(log V) depth, yielding exponential improvements for both parallelism and dependency length while achieving performance competitive with recurrent aggregators. Based on our empirical observations, our proposed learnable commutative monoid (LCM) aggregator represents a favourable tradeoff between efficient and expressive aggregators.