The Expressive Power of Path-Based Graph Neural Networks
Abstract
We systematically investigate the expressive power of path-based graph neural networks. While it has been shown that path-based graph neural networks can achieve strong empirical results, an investigation into their expressive power is lacking. Therefore, we propose PATH-WL, a general class of color refinement algorithms based on paths and shortest path distance information. We show that PATH-WL is incomparable to a wide range of expressive graph neural networks, can count cycles, and achieves strong empirical results on the notoriously difficult family of strongly regular graphs. Our theoretical results indicate that PATH-WL forms a new hierarchy of highly expressive graph neural networks.
Cite
Text
Graziani et al. "The Expressive Power of Path-Based Graph Neural Networks." International Conference on Machine Learning, 2024.Markdown
[Graziani et al. "The Expressive Power of Path-Based Graph Neural Networks." International Conference on Machine Learning, 2024.](https://mlanthology.org/icml/2024/graziani2024icml-expressive/)BibTeX
@inproceedings{graziani2024icml-expressive,
title = {{The Expressive Power of Path-Based Graph Neural Networks}},
author = {Graziani, Caterina and Drucks, Tamara and Jogl, Fabian and Bianchini, Monica and Scarselli, Franco and Gärtner, Thomas},
booktitle = {International Conference on Machine Learning},
year = {2024},
pages = {16226-16249},
volume = {235},
url = {https://mlanthology.org/icml/2024/graziani2024icml-expressive/}
}