Local Predicted Positional Encoding for Zero-Shot Link Prediction

Zero-shot link prediction requires a model to recognize transferable graph structure without fitting to a new graph, yet positional and structural encodings (PSEs) can be costly to compute on large graphs. We introduce Local Predicted Positional Encoding (LPPE), a two-stage, structure-only approach that learns node representations from bounded neighborhoods and uses them in a scalable graph transformer for link prediction. By computing structural supervision on local subgraphs during training, LPPE avoids whole-graph PSE calculations; at inference, the frozen model produces an encoding from a new graph without directly computing PSEs or requiring node features. With neighborhood size, PPR sampling, and encoder configuration fixed, producing LPPE encoding for all nodes at inference scales linearly with the numbers of nodes and edges, compared with the cubic scaling of dense full-graph spectral metric calculations. LPPE exceeds the performance of explicitly computed local structural encodings. On 18 held-out datasets, jointly training on 1 up to 15 training datasets increases zero-shot average precision from 0.676 to 0.758, closing 45.3% of the gap to a separately trained in-domain reference. These results suggest that local structural learning can make structural pretraining more scalable, while joint training on more datasets improves zero-shot link prediction on unseen graphs.