@inproceedings{
graziani2023no,
title={No {PAIN} no Gain: More Expressive {GNN}s with Paths},
author={Caterina Graziani and Tamara Drucks and Monica Bianchini and franco scarselli and Thomas G{\"a}rtner},
booktitle={NeurIPS 2023 Workshop: New Frontiers in Graph Learning},
year={2023},
url={https://openreview.net/forum?id=q2xXh4M9Dx}
}
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.
No PAIN no Gain: More Expressive GNNs with Paths
Caterina Graziani Tamara Drucks Monica Bianchini franco scarselli Thomas Gärtner