# Natural Graph Networks

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

## Key facts

- Cited by 35 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Jul 2020.

## Built on by (most cited first, 30 of 35)

- [Weisfeiler and Lehman Go Cellular: CW Networks](https://mlsanity.com/paper/2106.12575/) (2021)
- [Neural Sheaf Diffusion: A Topological Perspective on Heterophily and Oversmoothing in GNNs](https://mlsanity.com/paper/2202.04579/) (2022)
- [Rethinking the Expressive Power of GNNs via Graph Biconnectivity](https://mlsanity.com/paper/2301.09505/) (2023)
- [Understanding and Extending Subgraph GNNs by Rethinking Their Symmetries](https://mlsanity.com/paper/2206.11140/) (2022)
- [Graph Filters for Signal Processing and Machine Learning on Graphs](https://mlsanity.com/paper/2211.08854/) (2022)
- [Learning Physical Dynamics with Subequivariant Graph Neural Networks](https://mlsanity.com/paper/2210.06876/) (2022)
- [Position: Categorical Deep Learning is an Algebraic Theory of All Architectures](https://mlsanity.com/paper/2402.15332/) (2024)
- [The Expressive Power of Graph Neural Networks: A Survey](https://mlsanity.com/paper/2308.08235/) (2023)
- [Probabilistically Rewired Message-Passing Neural Networks](https://mlsanity.com/paper/2310.02156/) (2023)
- [Scalable algorithms for physics-informed neural and graph networks](https://mlsanity.com/paper/2205.08332/) (2022)
- [Deep Generative Models for Detector Signature Simulation: A Taxonomic Review](https://mlsanity.com/paper/2312.09597/) (2023)
- [Zero-shot Node Classification with Decomposed Graph Prototype Network](https://mlsanity.com/paper/2106.08022/) (2021)
- [Higher-order Graph Convolutional Network with Flower-Petals Laplacians on Simplicial Complexes](https://mlsanity.com/paper/2309.12971/) (2023)
- [Probabilistic Graph Rewiring via Virtual Nodes](https://mlsanity.com/paper/2405.17311/) (2024)
- [CIN++: Enhancing Topological Message Passing](https://mlsanity.com/paper/2306.03561/) (2023)
- [Weisfeiler and Lehman Go Paths: Learning Topological Features via Path Complexes](https://mlsanity.com/paper/2308.06838/) (2023)
- [Towards a Grounded Theory of Causation for Embodied AI](https://mlsanity.com/paper/2206.13973/) (2022)
- [Improving the Expressiveness of K-hop Message-Passing GNNs by Injecting Contextualized Substructure Information](https://mlsanity.com/paper/2406.19244/) (2024)
- [Physics and Chemistry from Parsimonious Representations: Image Analysis via Invariant Variational Autoencoders](https://mlsanity.com/paper/2303.18236/) (2023)
- [K"ahler Geometry of Quiver Varieties and Machine Learning](https://mlsanity.com/paper/2101.11487/) (2021)
- [A Category-theoretical Meta-analysis of Definitions of Disentanglement](https://mlsanity.com/paper/2305.06886/) (2023)
- [Equivariant Matrix Function Neural Networks](https://mlsanity.com/paper/2310.10434/) (2023)
- [Subgraph Permutation Equivariant Networks](https://mlsanity.com/paper/2111.11840/) (2021)
- [Enriching Disentanglement: From Logical Definitions to Quantitative Metrics](https://mlsanity.com/paper/2305.11512/) (2023)
- [P-Tensors: a General Formalism for Constructing Higher Order Message Passing Networks](https://mlsanity.com/paper/2306.10767/) (2023)
- [The Role of Fibration Symmetries in Geometric Deep Learning](https://mlsanity.com/paper/2408.15894/) (2024)
- [Current Symmetry Group Equivariant Convolution Frameworks for Representation Learning](https://mlsanity.com/paper/2409.07327/) (2024)
- [CanonNet: Canonical Ordering and Curvature Learning for Point Cloud Analysis](https://mlsanity.com/paper/2504.02763/) (2025)
- [The Topos of Transformer Networks](https://mlsanity.com/paper/2403.18415/) (2024)
- [Multi-Scale Harmonic Encoding for Feature-Wise Graph Message Passing](https://mlsanity.com/paper/2505.15015/) (2025)

## Abstract (arXiv)

A key requirement for graph neural networks is that they must process a graph in a way that does not depend on how the graph is described. Traditionally this has been taken to mean that a graph network must be equivariant to node permutations. Here we show that instead of equivariance, the more general concept of naturality is sufficient for a graph network to be well-defined, opening up a larger class of graph networks. We define global and local natural graph networks, the latter of which are as scalable as conventional message passing graph neural networks while being more flexible. We give one practical instantiation of a natural network on graphs which uses an equivariant message network parameterization, yielding good performance on several benchmarks.