TL;DR
Path Neural Networks (PathNNs) overcome the expressivity limits of standard message-passing GNNs by aggregating path-based information rather than just immediate node neighborhoods. By encoding and aggregating shortest or simple paths up to length $K$, PathNNs achieve provably higher expressive power than the standard 1-WL isomorphism test, leading to state-of-the-art performance on both synthetic and real-world graph benchmarks.
What Problem Does This Paper Address?
Standard Graph Neural Networks (GNNs) rely on message passing, where a node recursively aggregates features from its immediate neighbors. While intuitive, this neighborhood aggregation scheme is fundamentally limited: it is at most as powerful as the 1-dimensional Weisfeiler-Leman (1-WL) graph isomorphism test. Consequently, standard GNNs fail to distinguish structurally distinct graphs that share identical neighborhood statistics (such as certain regular graphs or connected vs. disconnected structures).
To break this expressivity barrier, researchers have turned to higher-order or subgraph-based methods, but these can be computationally heavy and complex to implement. This paper addresses this gap by exploring paths as a more expressive yet tractable alternative to standard neighborhood aggregation.
Methods
The authors introduce Path Neural Networks (PathNNs). Instead of aggregating immediate neighbors, PathNNs aggregate entire paths emanating from a node. They propose three variants based on different path collections up to a maximum length $K$:
- Single Shortest Paths ($SP$): Considers a single shortest path between node pairs.
- All Shortest Paths ($SP^+$): Considers all possible shortest paths between node pairs.
- All Simple Paths ($AP$): Considers all simple paths (paths with no repeated nodes) up to length $K$.
Path Encoding & Aggregation
Because paths are ordered sequences of nodes, PathNNs employ a Long Short-Term Memory (LSTM) network operating on reversed paths to encode these sequences into vectors. At each layer $k$, paths of length $k$ are embedded and aggregated into the node's representation using an injective aggregation function (sum/MLP) combined with Batch Normalization to maintain numerical stability.
Distance Encoding
For the most complex variant ($AP$), the authors introduce a distance-aware LSTM cell. This cell explicitly injects the geodesic distance from the path's nodes back to the root node, helping the model distinguish paths with similar sequence structures but different structural roles within the graph.
Datasets
The model was evaluated across a diverse suite of benchmarks:
- Synthetic Expressivity Benchmarks: Circular Skip Link (CSL), EXP (EXP-Class and EXP-Iso), and Strongly Regular (SR) graph datasets, used specifically to test graph isomorphism limits.
- TUDataset Collection: DD, PROTEINS, NCI1, ENZYMES, IMDB-B, and IMDB-M for standard graph classification.
- Open Graph Benchmark (OGB):
ogbg-molhivfor molecular property prediction. - Long-Range/Regression Benchmarks: ZINC 12K (graph regression), Peptides-functional (multi-label classification), and Peptides-structural (3D property regression).
Key Insights and Ideas
- Path-Trees vs. WL-Trees: Standard 1-WL effectively explores walks (which allow repeated nodes and edges), creating redundant loops that "pollute" the structural representation of regular graphs. PathNNs look at paths (no repeated nodes), removing this redundancy and allowing the model to see the true underlying skeleton of the graph.
- Breaking the 1-WL and 3-WL Barriers: The authors prove theoretically that the $SP^+$ and $AP$ variants are strictly more powerful than the 1-WL test. Remarkably, the $AP$ variant with distance encoding can even distinguish strongly regular graphs that are indistinguishable by the much stronger 3-WL test.
- Capturing Long-Range Dependencies: Because paths explicitly trace long-range connections across the graph up to length $K$, PathNNs naturally excel at tasks requiring long-range interaction reasoning without needing deep, over-smoothed message-passing stacks.
Key Results
- Expressivity: On the CSL and EXP datasets, PathNN-$SP^+$ and PathNN-$AP$ achieved 100% accuracy, perfectly distinguishing non-isomorphic graphs where standard models like GIN fail (achieving only 10% and 50% respectively). On the challenging SR dataset, PathNN-$AP$ successfully distinguished over 80% of 3-WL-indistinguishable graphs in most instances.
- Real-World Performance: PathNNs outperformed standard baselines on 5 out of 6 TUDatasets.
- Long-Range Benchmarks: On the Peptides-Functional dataset, PathNNs achieved an absolute improvement of 8.86% in Average Precision over standard GCNs. On Peptides-Structural, they improved Mean Absolute Error by 8.80% over GatedGCN, showcasing their superior ability to capture long-range molecular properties.
Limitations and Future Work
- Computational Complexity: Enumerating all simple paths ($AP$) is NP-hard in general. While bounding the path length to $K$ makes it tractable for small or sparse graphs (like molecules), it scales as $O(nb^K)$ where $b$ is the branching factor. For large, dense graphs, this leads to high preprocessing times and out-of-memory (OOM) errors (e.g., PathNN-$AP$ faced OOM on the dense DD dataset at $K=3$).
- Future Directions: Developing smarter path sampling strategies (instead of full enumeration) to scale the highly expressive $AP$ variant to larger, denser networks remains an open area for future work.
Summary updated