Reusable Graph Representations for Path Prediction

Graph–path learning predicts properties of ordered paths in shared graphs, with applications in network routing and comparative biology. In this article, we advocate for caching graph representations: sharing their encoding cost across many path queries is crucial for large-scale applications. We make three contributions. First, we introduce the Edge–Vertex Transformer (EVT), which couples vertex states with direction-aware pair attention, and an aligned graph-to-path construction that separates reusable graph encoding from path processing. Second, we characterize the expressivity of this model by a path-indexed two-dimensional folklore Weisfeiler–Leman (2-FWL) profile. Every compatible continuous prediction can be uniformly approximated on compact domains using one parameter set shared across jointly bounded graph and path sizes. We also establish a strict hierarchy between selection, joint cache reading, and path-marked encoding. Third, we build a coherent benchmarking suite combining controlled synthetic tasks, temporal routing measurements from RIPE Atlas, and ThorAxe-Combo, a curated biological benchmark of splicing tasks. The experiments distinguish information access from finite-resource learning: the most elaborate reusable pipeline benefits synthetic composition tasks and Atlas prediction, while simpler pair processors lead on ThorAxe-Combo. Our benchmarks also assess the computational gains enabled by graph-cache reuse. Together, these contributions identify when relational path processing justifies its computational cost.