Poster
The Expressive Power of Path-Based Graph Neural Networks
Caterina Graziani · Tamara Drucks · Fabian Jogl · Monica Bianchini · franco scarselli · Thomas Gärtner
Hall C 4-9 #500
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.
Live content is unavailable. Log in and register to view live content