PAN: Expressiveness of GNNs with Paths

Motivated by the lack of theoretical investigation into the discriminative power of paths, we characterize classes of graphs where paths are sufficient to identify every graph. We formally justify the use of paths based on finite-variable counting logic and prove the effectiveness of paths to recognize graph structural features related to cycles and connectivity. We show that paths are able to identify graphs for which higher-order models fail. Building on this, we propose PAN, a novel graph neural network that replaces topological neighborhoods with paths in the aggregation step of the message-passing procedure. This modification leads to an algorithm that is strictly more expressive than the Weisfeiler-Leman graph isomorphism test, at the cost of a polynomial-time preprocessing step for every fixed path length. We support our theoretical findings by empirically evaluating PAN on synthetic datasets.