acceptodds
Under review as a conference paper at ICLR 2027

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

19 views

Abstract

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.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
Graph Foundation Models, Graph Neural Networks, Graph Representation Learning, Link Prediction, Heterogeneous Graphs, Information Retrieval, Scalable Machine Learning

Reviews

Among:
Shape:
1234this paper, Top 17%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.75 over 4 reviews, above 83% of the others.
Reviewer_f3joOpenReview ↗
Rating
2(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

SURF augments frozen graph-model embeddings with precomputed neighborhood signatures. Lightweight relationship-specific operators and calibrated score fusion combine structural and backbone information. All relationship-dependent computation remains on the query side, preserving an inner-product retrieval interface. Experiments evaluate academic datasets, production prediction tasks, and retrieval costs.

Critical strengths

Preserving reusable candidate representations while introducing relationship-specific structural scoring is an appealing design. The implementation requires very few task-specific parameters.

The evaluation spans multiple backbones and datasets. The paper also distinguishes exact score factorization from approximate index search and explicitly acknowledges storage and refresh costs.

Critical weaknesses

The comparisons do not establish how much benefit requires a pretrained GFM. Strong structural references—such as Bloom-signature predictors, MPLP, or calibrated heuristic fusion—are absent from the main evaluation. Table 3 also introduces calibration and learned fusion together at the stage producing the largest jump. A structural-only model and calibration-only controls are important for identifying SURF’s added value.

The balanced-negative protocol is unusual. Appendix E ranks each positive against scores from a shared pool of negative pairs, irrespective of their source node. This differs from ranking candidate destinations for a fixed query and can reward score calibration across queries. These results should be separated clearly from conventional query-wise retrieval metrics and checked using standard per-query evaluation.

The serving experiments provide limited evidence for the advertised scale. The production total exceeds one billion scored pairs, but each group contains 4,093 candidates. The latency test uses 100,000 candidates, and HNSW recall is unreported. The separate large-graph preprocessing experiment computes signatures for approximately 50,000 requested nodes. Together, these support useful components of the system, but leave full-population index memory, recall, and refresh costs unresolved.

Questions for authors

How does SURF compare with structural-only scoring and calibrated fusion of established structural predictors?

Do the balanced-negative conclusions hold under fixed-query candidate ranking?

Can you report index size and recall–latency curves on actual learned representations at larger candidate populations?

2 comments
AuthorsOpenReview ↗

Reply to Reviewer f3jo

We thank the reviewer for the constructive comments. We added component comparisons, retrieval results, and protocol clarifications in Appendix G, marked in purple.

Structural baselines. Common Neighbors (CN) and Adamic–Adar (AA) use the same RMS calibration and relation-conditioned fusion procedure as SURF, with train/validation supervision only. The additional comparisons cover ten train/test datasets, two seeds, and 4,096 filtered negatives per positive. MRR is reported as mean ±\pm sample SD across seeds: relation tasks are weighted by original edge counts within each dataset, then datasets are averaged equally.

Scoring modelGraphBFF MRRHGT MRR
Backbone only0.0973±0.00400.0973\pm0.00400.0636±0.00090.0636\pm0.0009
Backbone + CN0.1602±0.00070.1602\pm0.00070.1249±0.00070.1249\pm0.0007
Backbone + AA0.1839±0.00080.1839\pm0.00080.1568±0.00070.1568\pm0.0007
SURF: RMS-equal0.2553±0.00810.2553\pm0.00810.1983±0.00210.1983\pm0.0021
SURF: learned weights0.3129±0.0077\mathbf{0.3129\pm0.0077}0.3164±0.0001\mathbf{0.3164\pm0.0001}

CN/AA improve both backbones, while SURF achieves substantially higher reported macro MRR and preserves inner-product retrieval. Tables 13–14 provide all dataset results, including cases where AA is stronger. The heuristic rows use average ties; SURF uses the saved strict-greater ranks.

Calibration versus learned fusion. The two SURF rows hold features, kernels, RMS scales, evaluation pairs, and ranking protocol fixed. Learned weights improve MRR by 5.75±1.585.75\pm1.58 and 11.80±0.2211.80\pm0.22 percentage points for GraphBFF and HGT (paired seed differences). Thus, calibration alone does not explain the gains. Appendix G.2 and Table 12 report the complete controlled ablation, complementing the existing RMS-removal ablation.

Structural-only scoring. Removing pretrained embeddings yields 0.3641±0.00070.3641\pm0.0007 macro MRR, confirming that structure is the strongest signal in this aggregate. The backbone contributes differently across tasks: full SURF with HGT outperforms both branches on Fitness, Goodreads, and Rel-Stack. On Goodreads, HGT, structural-only scoring, and full SURF achieve 0.1329±0.00620.1329\pm0.0062, 0.8409±0.00180.8409\pm0.0018, and 0.8734±0.00890.8734\pm0.0089, respectively. Appendix G.4 and Tables 15–16 provide all dataset comparisons under the same ranking convention.

Retrieval evaluation. Table 1 already evaluates query-wise sampled retrieval using 10% of test positives and 10% of compatible candidates. SURF(HGT) improves MRR on 14 of 16 datasets, including all six held-out datasets. This conclusion therefore holds independently of the balanced-negative evaluation. Appendix G.5 explicitly distinguishes Table 1's candidate ranking from the shared negative-pair score pool used in the balanced-negative results.

Recall–latency curves and index footprint. Appendix G.6, Figure 7, and Table 17 add ANN measurements on learned GraphBFF + SURF representations for 100,000 candidates and all 676,084 Goodreads destinations. At structural width 256, semantic-first retrieval followed by SURF reranking gives:

CandidatesReranking depthRecall@100 (%)Latency (ms)
100,0001,00061.5±8.561.5\pm8.515.9±0.4\mathbf{15.9\pm0.4}
100,00010,00097.9±1.4\mathbf{97.9\pm1.4}35.8±0.635.8\pm0.6
676,0841,00045.3±6.145.3\pm6.124.0±0.8\mathbf{24.0\pm0.8}
676,08410,00085.5±3.9\mathbf{85.5\pm3.9}43.8±0.943.8\pm0.9

Values are mean ±\pm sample SD across two seeds after averaging five warm-query repetitions per seed. Latency combines semantic-search p95 with mean reranking time. The full-population fused index occupies 3.30 GB; the semantic index occupies 0.53 GB, plus candidate data for reranking. Figure 7 shows the recall, latency, and storage trade-offs across structural widths and both populations.

Production evaluation and scalability. We rank each positive against 4,092 sampled negatives, following the platform's internal protocol and using identical groups across models. Sampled-candidate ranking is widely used in recommender evaluation to reduce the cost of scoring the full candidate population [1]. This measures prediction quality under substantial class imbalance while making repeated production evaluation tractable. The sampled group size does not limit the population SURF can search.

SURF scores 1.105 billion pairs per backbone across three production tasks, demonstrating its ability to process a large production workload. Its MIPS formulation supports cached candidate vectors and retrieval without query-time graph traversal. In the paper's 100,000-candidate benchmark, exact SURF retrieval takes 68.5 ms; the evaluated ULTRA configuration requires an estimated 633.8 seconds. The production workload and learned-vector ANN results provide complementary evidence of scoring and retrieval scalability (Appendix G.7).

Given the additional evidence, we hope the reviewer reconsiders their recommendation.

[1] Zhao et al., [A Revisiting Study of Appropriate Offline Evaluation for Top-N Recommendation Algorithms]

Dear Reviewer,

Thank you again for your feedback. As the response deadline approaches, we wanted to briefly follow up on our rebuttal and the revised manuscript. Appendix G now includes the controlled calibration-versus-fusion ablation, calibrated CN/AA baselines, and structural-only comparisons (G.2–G.4). We also clarified Table 1’s query-wise retrieval protocol (G.5) and added recall–latency curves and index-size measurements on learned representations for up to 676,084 candidates (G.6, Figure 7).

We hope these additions help address the concerns you raised. Could you let us know whether any points remain unresolved or would benefit from further clarification? We would appreciate the opportunity to discuss them before the response period closes.

Thank you for your time and consideration.

Reviewer_HKxNOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper proposes SURF, a lightweight structural adaptation framework for graph foundation models on large-scale link prediction. It combines pretrained node embeddings with precomputed structural signatures, relation-specific structural operators, and calibrated score fusion. The resulting scoring function preserves an inner-product form, enabling efficient indexed retrieval with cached candidate embeddings. Experiments across 16 academic datasets and three production tasks demonstrate substantial performance improvements and low retrieval latency.

Critical strengths
  1. Simple, effective, and broadly applicable design. SURF introduces a lightweight structural adaptation mechanism without modifying the pretrained backbone. The approach is compatible with different node-embedding GFM architectures, and experiments demonstrate substantial improvements across multiple datasets and backbones.

  2. Practical consideration of large-scale retrieval efficiency. The method carefully preserves compatibility with indexed retrieval while incorporating structural information. The paper provides extensive experiments, including production-scale evaluations, retrieval latency measurements, and ablations on structural adaptation and scalability.

Critical weaknesses
  1. Insufficient justification for the use of pretrained GFMs. While SURF substantially improves pretrained GFM backbones, the experiments do not sufficiently establish the benefit of GFM pretraining over task-specific link prediction models. Since the method still requires target-task supervision, comparisons with efficient structural predictors such as NCN/NCNC would help clarify the advantages of the proposed GFM-based framework. Moreover, the independent contribution of pretrained node embeddings relative to the structural components is not systematically evaluated.
Questions for authors

Q1. How does SURF compare with efficient task-specific structural link predictors such as NCN/NCNC, particularly in terms of prediction quality and inference efficiency under comparable candidate-set sizes?

Q2. How much of SURF's performance depends on pretrained GFM embeddings? Could the authors provide a systematic structural-only comparison, without the semantic backbone branch, to better isolate the contribution of GFM pretraining?

3 comments
AuthorsOpenReview ↗

Reply to Reviewer HKxN

We thank the reviewer for highlighting SURF's applicability and retrieval efficiency, and for suggesting additional structural comparisons.

Neural plus structural baselines. Motivated by your request for comparisons with structural link predictors such as NCN/NCNC, we evaluated pretrained backbones augmented with Common Neighbors (CN) and Adamic–Adar (AA). These baselines use the same RMS calibration and relation-conditioned fusion procedure as SURF, allowing us to examine the choice of structural scoring while keeping the backbone fixed.

Scoring modelGraphBFF MRRHGT MRR
Backbone only0.0973±0.00400.0973 \pm 0.00400.0636±0.00090.0636 \pm 0.0009
Backbone + CN0.1602±0.00070.1602 \pm 0.00070.1249±0.00070.1249 \pm 0.0007
Backbone + AA0.1839±0.00080.1839 \pm 0.00080.1568±0.00070.1568 \pm 0.0007
Full SURF0.3129±0.0077\mathbf{0.3129 \pm 0.0077}0.3164±0.0001\mathbf{0.3164 \pm 0.0001}

Results are mean ±\pm sample standard deviation across two seeds of macro MRR over the ten train/test datasets, using 4,096 filtered negatives per positive. When applicable, relation tasks are weighted by their original edge counts within each dataset, and datasets are averaged equally within each seed.

Both conventional heuristics improve the backbones, while SURF achieves substantially higher reported mean MRR with both backbones. SURF also preserves cached candidate representations and inner-product retrieval, keeping graph traversal outside online scoring.

Structural-only comparison and backbone contribution. We distinguish three configurations: backbone only uses pretrained node embeddings; structural only uses the relation-conditioned structural kernel without node embeddings; and full SURF combines backbone and structural scores.

Under the same dataset aggregation, structural-only scoring achieves 0.3641±0.00070.3641 \pm 0.0007 macro MRR, compared with 0.3129±0.00770.3129 \pm 0.0077 and 0.3164±0.00010.3164 \pm 0.0001 for full SURF with GraphBFF and HGT. Structure is therefore the strongest signal in this aggregate. However, results in the dataset level show that combining the branches can improve over either branch alone:

DatasetHGT backbone onlyStructural onlyFull SURF (HGT)
Fitness0.1783±0.00780.1783 \pm 0.00780.7221±0.00320.7221 \pm 0.00320.7324±0.0023\mathbf{0.7324 \pm 0.0023}
Goodreads0.1329±0.00620.1329 \pm 0.00620.8409±0.00180.8409 \pm 0.00180.8734±0.0089\mathbf{0.8734 \pm 0.0089}
Rel-Stack0.0466±0.00260.0466 \pm 0.00260.1377±0.00050.1377 \pm 0.00050.1525±0.0070\mathbf{0.1525 \pm 0.0070}

These component comparisons use the same ranking convention and report mean ±\pm sample standard deviation across two seeds. They demonstrate a task-dependent contribution from the backbone and motivate SURF's ability to combine the two information sources.

Our contribution is a lightweight, retrieval-compatible mechanism for adapting pretrained GFMs with structural information. We will add the complete dataset-level component and heuristic comparisons to the revision, explicitly defining each configuration and discussing where the backbone provides complementary value.

Dear Reviewer,

Thank you again for your feedback. We wanted to briefly follow up on the additional comparisons in the revised manuscript: calibrated CN/AA baselines in Appendix G.3, Tables 13–14, and complete backbone-only, structural-only, and full-SURF results in Appendix G.4, Tables 15–16. These results clarify both the strength of structural information and the task-dependent contribution of the pretrained backbone.

As the response deadline approaches, we would welcome your thoughts on these additions and any remaining questions we can help clarify.

Thank you for your time and consideration.

Thank you for the additional experiments and clarifications. The new baseline comparisons and structural-only ablations help address my concerns and better clarify the contributions of the proposed framework. I will maintain my original score.

Reviewer_fUaDOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper introduces SURF, a lightweight structural adaptation framework for improving link prediction with pretrained Graph Foundation Models (GFMs). It combines precomputed structural signatures, relation-specific structural operators, and learned score fusion while preserving efficient large-scale retrieval.

Critical strengths
  1. The paper identifies a well-defined and practically relevant gap in existing GFMs, which are designed for general-purpose graph representation learning rather than specifically optimizing structural link prediction.

  2. The paper is well written, and the proposed methodology is intuitive and clearly explained.

  3. The evaluation covers 16 academic datasets and large-scale production experiments involving over a billion scored pairs. The experiments are relevant to the paper’s objectives and demonstrate substantial improvements across multiple backbones.

Critical weaknesses
  1. Although the paper provides several ablation studies, it does not adequately investigate whether improvements arise from the proposed structural adaptation methodology or simply from incorporating established structural heuristics. Compare pretrained GFMs augmented with Common Neighbors, Adamic–Adar, and Resource Allocation using the same learned fusion and calibration mechanism.
Questions for authors

Could you please provide the comparision mentioned in weaknesses?

2 comments
AuthorsOpenReview ↗

Reply to Reviewer fUaD

We thank the reviewer for the comments and for suggesting this comparison.

Comparison with calibrated structural heuristics. We evaluated Common Neighbors (CN) and Adamic–Adar (AA) using the same fusion procedure as SURF: RMS normalization of training score differences, relation-conditioned gates, and train/validation supervision only. Each heuristic model combines the backbone score with CN or AA, whereas SURF uses its learned structural kernel channels.

The table reports illustrative dataset results and the overall macro averages:

DatasetBackboneBackbone only+ CN+ AA+ SURF
FitnessGraphBFF0.4355±0.00140.4355 \pm 0.00140.6249±0.00620.6249 \pm 0.00620.6541±0.00300.6541 \pm 0.00300.7443±0.0178\mathbf{0.7443 \pm 0.0178}
GoodreadsGraphBFF0.2401±0.03600.2401 \pm 0.03600.3531±0.02070.3531 \pm 0.02070.3826±0.01880.3826 \pm 0.01880.8753±0.0616\mathbf{0.8753 \pm 0.0616}
BioKGGraphBFF0.0215±0.00280.0215 \pm 0.00280.3128±0.01040.3128 \pm 0.01040.3587±0.0059\mathbf{0.3587 \pm 0.0059}0.2566±0.00260.2566 \pm 0.0026
Ten-dataset macro averageGraphBFF0.0973±0.00400.0973 \pm 0.00400.1602±0.00070.1602 \pm 0.00070.1839±0.00080.1839 \pm 0.00080.3129±0.0077\mathbf{0.3129 \pm 0.0077}
Ten-dataset macro averageHGT0.0636±0.00090.0636 \pm 0.00090.1249±0.00070.1249 \pm 0.00070.1568±0.00070.1568 \pm 0.00070.3164±0.0001\mathbf{0.3164 \pm 0.0001}

Values are MRR, reported as mean ±\pm sample standard deviation across two seeds, with 4,096 filtered negatives per positive. When applicable, relation tasks are weighted by their original edge counts within each dataset, followed by an equal average over datasets within each seed.

CN and AA improve the backbones on average, confirming the value of structural information. Their effectiveness varies across datasets: AA is particularly strong on BioKG, while SURF provides substantially larger improvements on Fitness and Goodreads. Across all ten datasets, SURF achieves higher reported mean MRR with both backbones, while preserving reusable candidate representations and inner-product retrieval.

We will add the complete per-dataset comparisons for both backbones, including variability across seeds, to the revised paper and discuss these differences in the experimental analysis.

I thank the authors for their rebuttal, i am maintaining my positive score.

Reviewer_dVwaOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This papers presents a method called "SURF" that augments frozen graph foundation model (GFM) embeddings with 1 and 2 hop bloom signatures from a nodes full neighborhood. The motivation for this is that while traditional pretrained node embeddings from GFM can be cached for fast retrieval during link prediction, computing similarity of source - candidates may miss some domain specific pairwise structural evidence. Hence the authors propose to augment GFM with a learned linear operator that utilizes the neighborhood signatures adaptively. Since these features can be calculated and indexed, no online graph traversal is required making the proposed method scalable. The paper evaluates the proposed method on a variety of held out domains after pretraining the frozen GFM on ten graph domains. The proposed method's task specific linear operator is trained on each held out domain and evaluated. Baselines include popular / sota GFM with further domain adaptation finetuning. Experiments show avg gains across datasets of proposed method over baselines in terms of MRR and Hits @ 1.

Critical strengths
  1. This paper proposes a method that is sound and offers a practical connection between structural features and GFM node representations. The reusable candidate vectors, score fusion and the use of neighborhood signatures all together are innovative ideas in the context of GFM adaptation.

  2. From experiments, baselines are trained on the same setting, and results do show significant gains with the proposed method. on Goodreads, Fitness and Amazon-Text that's very significant compared to vanilla finetuned GFMs.

  3. Experiments are setup well, multiple GFM backbones are considered and the proposed method do show gains across GFMs, helping the claim the in the paper.

Critical weaknesses
  1. From the ablations in table 3, its not clear structural signatures actually add value, since the final row uses a learned fusion compared to an uncalibrated unit weight. How much does the calibration matter ? The jump in performance seems to come from careful calibration rather than features and relation readout, which IMHO hurts the central claim that they matter.
Questions for authors
  1. Please address the point the weakness section.

Comments on the paper

1 comment

We thank the reviewers for their constructive feedback. We have added controlled ablations, structural comparisons, and retrieval measurements, and clarified the evaluation protocols and production configuration. These additions appear in Appendix G and are marked in dark purple. All references below are to the revised manuscript.

  1. Calibration versus learned fusion. Appendix G.2 and Table 12 add a controlled comparison between equal weights on RMS-normalized channels and learned simplex weights. Structural features, fitted kernels, calibration scales, and evaluation pairs remain fixed. Learned fusion improves macro MRR by 5.75±1.585.75 \pm 1.58 and 11.80±0.2211.80 \pm 0.22 percentage points for GraphBFF and HGT, respectively, computed from paired seed differences. This comparison isolates the additional benefit of learned fusion after calibration.

  2. Calibrated structural baselines. Appendix G.3 and Tables 13–14 add GraphBFF and HGT augmented with Common Neighbors and Adamic–Adar, using the same RMS calibration and relation-conditioned fusion procedure as SURF. We report complete results across the ten train/test datasets. Both heuristics improve the backbones on average, while SURF achieves higher reported macro MRR with both backbones. The dataset results also identify where conventional heuristics remain competitive.

  3. Structural-only scoring and backbone contribution. Appendix G.4 and Tables 15–16 compare backbone-only scoring, structural-only scoring without pretrained embeddings, and full SURF. Structural-only scoring achieves 0.3641±0.00070.3641 \pm 0.0007 macro MRR and is the strongest configuration in this aggregate. However, full SURF with HGT outperforms both individual branches on Fitness, Goodreads, and Rel-Stack. These results establish the strength of structural information and clarify the task-dependent contribution of pretrained embeddings.

  4. Evaluation protocols and seed variability. Appendix G.1 documents the additional comparisons: ten datasets, two seeds, and 4,096 filtered negatives per positive, with explicit dataset aggregation and sample standard deviations. Appendix G.5 clarifies that Table 1 already evaluates query-wise sampled retrieval, separately from the shared negative-pair pool used in the balanced-negative evaluation. Under Table 1’s retrieval protocol, SURF(HGT) improves MRR on 14 of 16 datasets, including all six held-out datasets.

  5. Recall–latency curves and index footprint. Appendix G.6, Figure 7, and Table 17 add ANN results on learned GraphBFF + SURF representations for 100,000 candidates and the complete Goodreads population of 676,084 candidates. On the full population, reranking 10,000 candidates achieves (85.5±3.9)%(85.5 \pm 3.9)\% ANN Recall@100 at 43.8±0.943.8 \pm 0.9 ms. The reported latency combines semantic-search p95 with mean reranking time. The full-population fused and semantic indexes occupy 3.30 GB and 0.53 GB, respectively; the latter requires additional candidate data for reranking.

  6. Production configuration and scalability. Appendix G.7 clarifies that validation selected equal one-third mixing weights for the RMS-calibrated channels in the production results already reported in Table 2. The structural kernels and calibration scales were fitted, so these results demonstrate gains from structural augmentation without unequal mixing weights. We also distinguish prediction-quality evaluation with sampled candidate groups from the 1.105-billion-pair scoring workload and MIPS-based retrieval. The candidate-group size is an evaluation choice and does not limit the candidate population that SURF can search.

Detailed responses to the reviewers’ concerns are provided in the individual reviewer threads.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.