SURF: Expressive Structural Adaptation for Billion-Scale Link Prediction with Graph Foundation Models

Large-scale link prediction with Graph Foundation Models (GFMs) seeks to share knowledge across relationships, tasks, and graph domains while efficiently serving predictions over massive candidate link populations. Realizing this vision requires reconciling structural expressivity to capture diverse linking patterns with indexed retrieval for low-latency candidate search. We identified three bottlenecks in retrieval-compatible GFMs: neighborhood sampling can discard predictive structural evidence, standard similarity readouts restrict how this evidence can be used, and shared structural mechanisms can suffer negative transfer across relationships. To address these limitations, we introduce SURF, which augments a pretrained graph-transformer backbone (HGT by default) with precomputed full-neighborhood node signatures, lightweight relation-conditioned structural operators, and score fusion. By confining relation-dependent computation to the query side, SURF preserves reusable candidate representations and indexed retrieval without online graph traversal or query–candidate-specific neural computation. Our analysis shows how suitable signature channels and lightweight query-side operators can express neighborhood-overlap and finite random-walk heuristics. Each domain–relationship task adapts and combines structural evidence without updating the shared backbone. Across 16 datasets, SURF improves MRR over its HGT backbone on 14 under sampled large-candidate retrieval, including all six held-out domains after adaptation. On a sampled production subgraph, SURF achieves 73.4–183.7% relative MRR gains across three backbones, each evaluated on over one billion query–candidate pairs. These results demonstrate that structural expressivity and large-scale indexed retrieval need not be competing objectives for GFMs.