No PAIN no Gain: More Expressive 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 instance. Our analysis motivates the integration of paths into the learning procedure of graph neural networks in order to enhance their expressiveness. 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 PAth Isomorphism Network (PAIN), a novel graph neural network that replaces the topological neighborhood 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 step for every iteration and fixed path length. We support our theoretical findings by empirically evaluating PAIN on synthetic datasets.