The Expressive Power of Path-Based Graph Neural Networks
Caterina Graziani, Tamara Drucks, Fabian Jogl, Monica Bianchini, franco scarselli, Thomas Gärtner
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.
BibTeX
@inproceedings{
graziani2024the,
title={The Expressive Power of Path-Based Graph Neural Networks},
author={Caterina Graziani and Tamara Drucks and Fabian Jogl and Monica Bianchini and franco scarselli and Thomas G{\"a}rtner},
booktitle={Forty-first International Conference on Machine Learning},
year={2024},
url={https://openreview.net/forum?id=io1XSRtcO8}
}