The Expressive Power of Path-Based Graph Neural Networks - Abstract

Aug 4, 2026

Upload by Miles

We systematically investigate the expressive power of path-based graph neural networks and address the gap behind their strong empirical performance. The work introduces PATH-WL, a general color refinement framework grounded in paths and shortest-path distance information. Results show PATH-WL is incomparable to many expressive GNNs, can count cycles, and performs well on strongly regular graphs. The theory establishes PATH-WL as a new hierarchy of highly expressive graph neural networks.

LanguageEnglish

CategoryResearch & Report

FormatPDF

Pages24

Reading Time1 h 0 min

AccessFree to download

Introduction

Expressive power of paths in GNNs

Related work on path-based GNNs

Main contributions

Preliminaries

Graph theory definitions

The Expressive Power of Path-Based Graph Neural Networks Caterina Graziani * 1 Tamara Drucks * 2 Fabian Jogl 2 3 Monica Bianchini 1 Franco Scarselli 1 Thomas Grtner 2 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. 1. Introduction We investigate the discriminative power of paths to increase the expressivity of graph neural networks (GNNs) . The expressive power of a GNN commonly refers to its ability to compute different embeddings for non-isomorphic graphs. The most common GNN, the message-passing graph neural network, has been shown to be at most as expressive as the Weisfeiler-Leman (1-WL) color refinement algorithm (Xu et al., 2019 ; Morris et al., 2019) . 1-WL is a polynomial-time heuristic for testing graph isomorphism that identifies almost all graphs (Babai et al., 1980) but systematically fails for some graph instances (see Figure 1 for an example) . This shortcoming can be partially explained by the limitation of 1-WL to recognize and count only simple substructures such as star graphs (Arvind et al., 2020) . The higher-order extension of 1-WL is k-WL (Babai, 1979 ; Immerman & *Equal contribution 1Department of Information Engineering and Mathematics, University of Siena, Siena, Italy 2RUML, TU Wien, Vienna, Austria 3 CAIML, TU Wien, Vienna, Austria. Correspondence to: Caterina Graziani <[caterina.graziani@student.unisi.it](caterina.graziani@student.unisi.it) >, Tamara Drucks <[tamara.drucks@tuwien.ac.at](tamara.drucks@tuwien.ac.at) > . Proceedings of the 41 st International Conference on Machine Learning, Vienna, Austria. PMLR 235, 2024 . Copyright 2024 by the author(s) . Lander, 1990), which operates on k-tuples of nodes and is more powerful due to its ability to count additional substructures. However, k-WL is impractical due to its prohibitive complexity and lack of locality (Morris et al., 2019) . To address these well-studied limitations, several novel GNNs that leverage graph substructures to improve expressivity have been recently proposed (Geerts, 2020 ; Thiede et al., 2021 ; Zhang & Li, 2021 ; Bodnar et al., 2021a ;b ; Bevilacqua et al., 2022 ; Bouritsas et al., 2022) . Please refer to Papp & Wattenhofer (2022) for an extensive comparison of the expressive power of many such GNN extensions. Related work. Paths are arguably one of the simplest graph substructures. Despite this, paths have only recently received attention in the context of GNNs. They can be broadly categorized into GNNs which incorporate shortest path information (Abboud et al., 2022 ; Kong et al., 2022 ; Li et al., 2020 ; Ding et al., 2023 ; Ying et al., 2021 ; Nikolentzos et al., 2020 ; Feng et al., 2022 ; Zhang et al., 2023) and GNNs which aggregate or sample from the set of all paths (Sun et al., 2022 ; Truong & Chin, 2023 ; Michel et al., 2023) . Please find a more comprehensive related work discussion in Appendix A. While Michel et al. (2023) proved that aggregating shortest paths alone is less expressive than 1-WL, they achieve strong empirical results with the incorporation of shortest path distance information. However, a precise characterization of the expressive power of pathbased GNNs with distance information is lacking. In this paper, we fill the existing gap in the literature and show that path-based GNNs with shortest path distances form a novel class of

FAQs

What is the main goal of the paper on path-based graph neural networks?

The paper systematically studies how expressive path-based GNNs are, focusing on their ability to distinguish graphs via path and shortest-path distance information.

What is PATH-WL?

PATH-WL is a general class of color refinement algorithms that iteratively performs message passing on all paths up to a chosen length, using paths and shortest-path distance information.

How do the theoretical results position PATH-WL relative to 1-WL and k-WL?

PATH-WL is strictly more expressive than 1-WL and is incomparable to k-WL, while also characterizing graph classes it can distinguish and showing it can count cycles of arbitrary length.

Aug 4, 2026

Upload by Miles