# Path Neural Networks: Expressive and Accurate Graph Neural Networks

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

## Key facts

- Cited by 32 papers in the map (data through 14 Oct 2026).
- Builds on 51 of its 71 references that are in the map.
- First posted on arXiv 9 Jun 2023.

## Builds on (most cited first, 30 of 51)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shift](https://mlsanity.com/paper/1502.03167/) (2015)
- [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)
- [A Comprehensive Survey on Graph Neural Networks](https://mlsanity.com/paper/1901.00596/) (2019)
- [Open Graph Benchmark: Datasets for Machine Learning on Graphs](https://mlsanity.com/paper/2005.00687/) (2020)
- [Graph Neural Networks: A Review of Methods and Applications](https://mlsanity.com/paper/1812.08434/) (2018)
- [MoleculeNet: A Benchmark for Molecular Machine Learning](https://mlsanity.com/paper/1703.00564/) (2017)
- [Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks](https://mlsanity.com/paper/1810.02244/) (2018)
- [Hierarchical Graph Representation Learning with Differentiable Pooling](https://mlsanity.com/paper/1806.08804/) (2018)
- [TUDataset: A collection of benchmark datasets for learning with graphs](https://mlsanity.com/paper/2007.08663/) (2020)
- [Benchmarking Graph Neural Networks](https://mlsanity.com/paper/2003.00982/) (2020)
- [Principal Neighbourhood Aggregation for Graph Nets](https://mlsanity.com/paper/2004.05718/) (2020)
- [Geometric deep learning on graphs and manifolds using mixture model CNNs](https://mlsanity.com/paper/1611.08402/) (2016)
- [Provably Powerful Graph Networks](https://mlsanity.com/paper/1905.11136/) (2019)
- [Residual Gated Graph ConvNets](https://mlsanity.com/paper/1711.07553/) (2017)
- [Invariant and Equivariant Graph Networks](https://mlsanity.com/paper/1812.09902/) (2018)
- [Do Transformers Really Perform Bad for Graph Representation?](https://mlsanity.com/paper/2106.05234/) (2021)
- [Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting](https://mlsanity.com/paper/2006.09252/) (2020)
- [Dynamic Edge-Conditioned Filters in Convolutional Neural Networks on Graphs](https://mlsanity.com/paper/1704.02901/) (2017)
- [Long Range Graph Benchmark](https://mlsanity.com/paper/2206.08164/) (2022)
- [A Fair Comparison of Graph Neural Networks for Graph Classification](https://mlsanity.com/paper/1912.09893/) (2019)
- [Weisfeiler and Lehman Go Topological: Message Passing Simplicial Networks](https://mlsanity.com/paper/2103.03212/) (2021)
- [Position-aware Graph Neural Networks](https://mlsanity.com/paper/1906.04817/) (2019)
- [The Surprising Power of Graph Neural Networks with Random Node Initialization](https://mlsanity.com/paper/2010.01179/) (2020)
- [Identity-aware Graph Neural Networks](https://mlsanity.com/paper/2101.10320/) (2021)
- [Random Features Strengthen Graph Neural Networks](https://mlsanity.com/paper/2002.03155/) (2020)
- [On the equivalence between graph isomorphism testing and function approximation with GNNs](https://mlsanity.com/paper/1905.12560/) (2019)

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

- [Beyond Weisfeiler-Lehman: A Quantitative Framework for GNN Expressiveness](https://mlsanity.com/paper/2401.08514/) (2024)
- [Learning Long Range Dependencies on Graphs via Random Walks](https://mlsanity.com/paper/2406.03386/) (2024)
- [Spatio-Spectral Graph Neural Networks](https://mlsanity.com/paper/2405.19121/) (2024)
- [Beyond Message Passing: Neural Graph Pattern Machine](https://mlsanity.com/paper/2501.18739/) (2025)
- [No Metric to Rule Them All: Toward Principled Evaluations of Graph-Learning Datasets](https://mlsanity.com/paper/2502.02379/) (2025)
- [Return of ChebNet: Understanding and Improving an Overlooked GNN on Long Range Tasks](https://mlsanity.com/paper/2506.07624/) (2025)
- [Recurrent Distance Filtering for Graph Representation Learning](https://mlsanity.com/paper/2312.01538/) (2023)
- [Generative Graph Pattern Machine](https://mlsanity.com/paper/2505.16130/) (2025)
- [Can You Hear Me Now? A Benchmark for Long-Range Graph Propagation](https://mlsanity.com/paper/2512.17762/) (2025)
- [USBD: Universal Structural Basis Distillation for Source-Free Graph Domain Adaptation](https://mlsanity.com/paper/2602.08431/) (2026)
- [Non-backtracking Graph Neural Networks](https://mlsanity.com/paper/2310.07430/) (2023)
- [Distributed-Order Fractional Graph Operating Network](https://mlsanity.com/paper/2411.05274/) (2024)
- [NeuroPath: A Neural Pathway Transformer for Joining the Dots of Human Connectomes](https://mlsanity.com/paper/2409.17510/) (2024)
- [Graph Representational Learning: When Does More Expressivity Hurt Generalization?](https://mlsanity.com/paper/2505.11298/) (2025)
- [On the Two Sides of Redundancy in Graph Neural Networks](https://mlsanity.com/paper/2310.04190/) (2023)
- [Improving Subgraph-GNNs via Edge-Level Ego-Network Encodings](https://mlsanity.com/paper/2312.05905/) (2023)
- [DisRFM: Polar Riemannian Flow Matching for Structure-Preserving Graph Domain Adaptation](https://mlsanity.com/paper/2602.00656/) (2026)
- [A Condensed Transition Graph Framework for Zero-shot Link Prediction with Large Language Models](https://mlsanity.com/paper/2402.10779/) (2024)
- [Weisfeiler and Leman Go Loopy: A New Hierarchy for Graph Representational Learning](https://mlsanity.com/paper/2403.13749/) (2024)
- [Scalable Graph Compressed Convolutions](https://mlsanity.com/paper/2407.18480/) (2024)
- [Dual-branch Graph Domain Adaptation for Cross-scenario Multi-modal Emotion Recognition](https://mlsanity.com/paper/2603.26840/) (2026)
- [Simple Path Structural Encoding for Graph Transformers](https://mlsanity.com/paper/2502.09365/) (2025)
- [Graph Self-Supervised Learning with Learnable Structural and Positional Encodings](https://mlsanity.com/paper/2502.16233/) (2025)
- [NeuroTree: Hierarchical Functional Brain Pathway Decoding for Mental Health Disorders](https://mlsanity.com/paper/2502.18786/) (2025)
- [Message Detouring: A Simple Yet Effective Cycle Representation for Expressive Graph Learning](https://mlsanity.com/paper/2402.08085/) (2024)
- [T- Hop: A framework for studying the importance path information in molecular graphs for chemical property prediction](https://mlsanity.com/paper/2407.14270/) (2024)
- [Finding path and cycle counting formulae in graphs with Deep Reinforcement Learning](https://mlsanity.com/paper/2410.01661/) (2024)
- [Chordless Structure: A Pathway to Simple and Expressive GNNs](https://mlsanity.com/paper/2505.19188/) (2025)
- [Caterpillar GNN: Replacing Message Passing with Efficient Aggregation](https://mlsanity.com/paper/2506.06784/) (2025)
- [Weisfeiler Lehman Test on Combinatorial Complexes: Generalized Expressive Power of Topological Neural Networks](https://mlsanity.com/paper/2605.00725/) (2026)

## Abstract (arXiv)

Graph neural networks (GNNs) have recently become the standard approach for learning with graph-structured data. Prior work has shed light into their potential, but also their limitations. Unfortunately, it was shown that standard GNNs are limited in their expressive power. These models are no more powerful than the 1-dimensional Weisfeiler-Leman (1-WL) algorithm in terms of distinguishing non-isomorphic graphs. In this paper, we propose Path Neural Networks (PathNNs), a model that updates node representations by aggregating paths emanating from nodes. We derive three different variants of the PathNN model that aggregate single shortest paths, all shortest paths and all simple paths of length up to K. We prove that two of these variants are strictly more powerful than the 1-WL algorithm, and we experimentally validate our theoretical results. We find that PathNNs can distinguish pairs of non-isomorphic graphs that are indistinguishable by 1-WL, while our most expressive PathNN variant can even distinguish between 3-WL indistinguishable graphs. The different PathNN variants are also evaluated on graph classification and graph regression datasets, where in most cases, they outperform the baseline methods.