acceptodds
Withdrawn from ICLR 2027

Local Predicted Positional Encoding for Zero-Shot Link Prediction

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

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.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
graph foundation models, zero-shot link prediction, learned positional encodings

Reviews

Among:
Shape:
1234this paper, Bottom 25%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.75 over 4 reviews, above 25% of the others.
Reviewer_7qr1OpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes Local Predicted Positional Encoding (LPPE) for structure-only zero-shot link prediction. LPPE first constructs bounded Personalized PageRank neighborhoods around sampled nodes in the training graphs and computes several local structural targets, including spectral and cycle-based descriptors. A GPS encoder is trained with multi-task supervision to predict these targets, after which the prediction heads are discarded and the frozen root representation is used as a positional encoding. A second-stage SGFormer link predictor is jointly trained on multiple graphs using the frozen LPPE representations. On an unseen graph, LPPE only constructs local PPR neighborhoods and applies the frozen encoder and link predictor, without graph-specific fine-tuning or explicit structural-target computation. Experiments on 15 training datasets and 18 held-out datasets report improved zero-shot average precision over random features and explicitly computed local positional encodings.

Critical strengths

The paper addresses a relevant scalability problem. Predicting structural representations instead of explicitly recomputing spectral encodings on every unseen graph is a sensible direction for transferable graph learning.

The separation between structural supervision and inference is conceptually clean. Expensive structural targets are required only during pretraining, while the learned representation can be reused without computing those targets at deployment.

The zero-shot protocol is reasonably strict. Both the LPPE encoder and link predictor are frozen on held-out graphs, and the structure-only setting avoids relying on transferable node features or identifiers.

Critical weaknesses

The main efficiency claim lacks sufficient empirical validation. The paper provides asymptotic complexity analysis but does not report comprehensive wall-clock time, preprocessing cost, throughput, or memory usage. Constructing and encoding a PPR neighborhood for every node may still be expensive because these neighborhoods overlap substantially.

The claimed O(N+M)O(N+M) inference complexity depends on strong fixed-budget assumptions. It assumes bounded neighborhood size, bounded random walks, and fixed encoder depth. The practical cost may depend heavily on PPR construction, graph density, and repeated processing of the same nodes across overlapping neighborhoods.

The experimental setting isolates structure but limits practical generality. Removing all node features is useful for evaluating structural transfer, but many real zero-shot link-prediction problems contain informative text, node types, or attributes. It remains unclear whether LPPE provides complementary gains when such features are available.

The contribution of individual structural targets is unclear. The model predicts several local spectral and cycle-based descriptors, but the main results do not clearly show which targets are necessary or whether multi-target supervision is better than a simpler structural pretraining objective.

Questions for authors

Can the authors report end-to-end preprocessing time, inference time, throughput, and peak memory for LPPE across graphs of different sizes, including the cost of constructing and encoding all PPR neighborhoods?

Does the claimed O(N+M)O(N+M) complexity include the practical cost of repeated PPR sampling and overlapping neighborhoods? How does runtime change with graph density, neighborhood size, and random-walk budget?

How does LPPE perform when combined with available node features, text embeddings, or node types? Does it provide complementary gains beyond these attributes?

Can the authors provide ablations for the individual structural targets and their combinations? In particular, does multi-target supervision outperform using only spectral descriptors, cycle-based descriptors, or a simpler link-reconstruction objective?

1 comment

Thank you for the review and your constructive feedback.

Although some of the requested evidence is already available, completing all of the measurements and ablations in a controlled and scientifically meaningful way will require significant work and compute time and we will be working on that.

W1 and Q1. End-to-end computational efficiency. We agree that asymptotic analysis alone does not establish practical efficiency. We retained some training and inference runtimes, but some experiments used different machines, making those records unsuitable for direct comparison. We will rerun the efficiency experiments under consistent hardware and software conditions and measure both runtime and memory consumption. The reporting will distinguish preprocessing, PPR neighborhood construction, encoding generation, and downstream inference, and include throughput and peak memory across graphs of different sizes. These measurements will cover constructing and encoding every node’s neighborhood, including repeated work caused by overlap.

W2 and Q2. Complexity assumptions and sensitivity to graph structure. Our analysis takes into account neighborhood construction, random-walk sampling for every root, and repeated processing of nodes and edges across overlapping neighborhoods. It does not assume that shared nodes are encoded only once. The linear scaling claim holds with fixed neighborhood size, sampling budgets, and encoder configuration, although the practical costs can still be substantial. We will clarify these assumptions and explore the effect of graph density on runtime.

W3 and Q3. Complementarity with node attributes. In this work, we chose to focus on graph structure to isolate the contribution of structural transfer. In parallel, our lab is working on methods for incorporating feature information. We will explore an ablation comparing node features alone with features augmented by LPPE and other PSEs to assess how our proposed positional and structural encoder can enrich node representations and provide complementary gains under zero-shot evaluation.

W4 and Q4. Contributions of the structural supervision targets. The six targets were adopted from the cited GPSE work, but their usefulness in our local setting needs to be established experimentally. We will ablate them individually and in combinations, including comparisons between spectral targets, cycle-based targets, and the full supervision set.

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

The paper modifies graph positional and structural encodings (GPSE) by computing structural targets on local PPR subgraphs instead of full graphs. It uses the resulting learned encodings for structure-only zero-shot link prediction, and it shows gains over explicit local encodings and with more training datasets.

Critical strengths
  1. Full-graph PSEs really are a bottleneck for large graphs, and localizing the targets is a sensible fix.
  2. Comprehensive evaluation across diverse graphs, the method uses 33 datasets. This is a useful finding for graph foundation models.
  3. Detailed implementation and reproducibility information
Critical weaknesses
  1. There are no classic heuristics like Common Neighbors or Adamic-Adar, these are crucial baselines
  2. There is no comparison to other zero-shot link predictors the paper itself cites (AnyGraph, UniLP, TFMLinker).
  3. The efficiency story is asserted, not measured.
  4. Missing ablation studies (see Q6)
Questions for authors
  1. How do Common Neighbors or Adamic-Adar score under this protocol?
  2. How do AnyGraph, UniLP or TFMLinker score under this protocol?
  3. What happens in the scaling experiment if the link predictor is fixed and only the LPPE encoder’s training datasets vary, or the reverse?
  4. Why does LPPE outperform the explicit local PSEs it was trained to predict?
  5. Could the authors report empirical runtimes to better demonstrate the computational efficiency of the proposed method?
  6. How do AP and runtime change with fewer walks, a different restart probability, and larger/smaller neighborhood caps?
1 comment

Thank you for reviewing our work and for the constructive feedback. We appreciate both your recognition of the motivation for local structural supervision and your suggestions for making the empirical evaluation more informative.

Some relevant results are already in hand, but the remaining comparisons and controlled experiments will require considerable work and compute time and we are working on them right now.

W1, W2, Q1, and Q2. Classical heuristics and additional baselines. We agree that classical heuristics and established zero-shot predictors are important reference points. We will expand the evaluation to include Common Neighbors, Adamic–Adar, AnyGraph, UniLP, TFMLinker, PEARL, CondPSE, GPSE, and Global PSE, adding further relevant baselines as the experiments progress. The heuristics and zero-shot predictors will use the same Link2 datasets, permitted observed graph structure, and evaluation pairs. Structural encoding methods will be compared under matched downstream conditions, with a separate comparison on smaller graphs where GPSE and Global PSE can complete.

W3 and Q5. Empirical efficiency. We agree that the complexity analysis should be accompanied by measured computational costs. Some training and inference runtimes were retained, but the experiments were partly conducted on different machines, preventing a consistent comparison. We will rerun the efficiency evaluation using a common hardware and software setup and report both wall-clock runtime and memory consumption.

W4, Q3, and Q6. Training-stage and PPR parameter ablations. The current dataset-scaling experiment expands the training datasets for both the LPPE encoder and the link predictor, so it does not isolate their respective contributions. We will vary the encoder’s training datasets while holding the link-predictor training data and procedure constant, retraining the predictor for each encoder, and conduct complementary experiments that fix the encoder while varying the link-predictor training datasets. We will also vary the number of random walks, restart probability, and neighborhood cap, reporting changes in AP and runtime. Together, these experiments will help identify the sources of the scaling gains and clarify the tradeoffs between predictive performance and computational cost.

Q4. Why learned encodings can outperform explicit local PSEs. The downstream input is the encoder’s hidden root representation, rather than its predicted PSE values. Consequently, LPPE is not restricted to reproducing the explicit target vector as its final representation. Training across neighborhoods may allow it to retain additional transferable structural information. We will study this phenomenon further by also reporting results of the model when using the predicted metrics instead of the latent representation.

Reviewer_jds5OpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes Local Predicted Positional Encoding (LPPE), a two-stage, structure-only pipeline for zero-shot link prediction. The first stage extracts a personalized PageRank (PPR) neighborhood of at most 50 nodes around each root, computes the six positional and structural targets of GPSE within each induced subgraph, and trains a GPS encoder on random Gaussian node inputs to predict these targets. The second stage freezes the encoder, uses the root representations as node features for an SGFormer link predictor, and scores candidate pairs with a pairwise MLP decoder. Both stages remain frozen on unseen graphs. The authors argue that this design reduces the cost of producing encodings for all nodes from O(N³) to O(N + M). The experiments use the 15 Link1 training datasets and 18 Link2 held-out datasets of the AnyGraph collection. LPPE achieves a zero-shot mean average precision of 0.758 on Link2 after training on all 15 Link1 datasets, against 0.705 for explicitly computed local encodings and 0.667 for random features. Increasing the number of training datasets from 1 to 15 raises the mean AP from 0.676 to 0.758.

Critical strengths
  1. The paper addresses a relevant problem. The cost of computing positional and structural encodings limits the use of graph transformers on large graphs, and a learned local encoder offers a plausible route to reduce this cost.

  2. The evaluation protocol prevents leakage carefully. The authors exclude test edges from message passing, PPR construction, target computation, and checkpoint selection, and they document the splits, seeds, and dataset orderings in detail.

Critical weaknesses
  1. The paper omits all established zero-shot link prediction baselines. The experiments use the exact AnyGraph Link1/Link2 split, yet the paper does not compare against AnyGraph itself, the model for which this benchmark was constructed.

  2. The comparison with the closest methods did not complete. Table 2 reports no results for Global PSE or GPSE because encoding computation timed out on large graphs. The paper presents GPSE as its closest methodological predecessor, so the absence of this comparison removes the central empirical test of the contribution.

  3. The efficiency claims lack any empirical support. The paper positions computational efficiency as a primary contribution, yet it reports no wall-clock time, memory consumption, or throughput measurement for any method. Table 1 assigns qualitative ratings such as “Best” and “Very slow” without measurement.

  4. LPPE applies the GPSE training procedure, with the same targets, the same random-input design, and the same multitask regression objective, to PPR-induced subgraphs instead of full graphs. The use of local subgraphs for link prediction is well established through SEAL, ELPH, and BUDDY.

Questions for authors
  1. The authors should report the zero-shot performance of AnyGraph, UniLP, and classical heuristics on the same Link2 datasets under the same protocol.

  2. The authors should report measured wall-clock inference time and memory for LPPE, explicit local encodings, GPSE, and sparse global encodings across graphs of increasing size.

  3. The authors should report ablations over the neighborhood size, the number of walks, and the subset of structural targets.

1 comment
AuthorsOpenReview ↗

Zero-shot baselines, GPSE comparisons, and measured efficiency

We appreciate your assessment and the time you invested in providing constructive suggestions. Thank you also for recognizing the attention given to leakage prevention and reproducibility.

While we already have some of the requested results, completing the remaining baseline comparisons, controlled measurements, and ablations will involve substantial experimental work and computational resources.

W1 and Q1. Established zero-shot baselines. Following your feedback we are planning to add multiple new baselines. Our planned comparison set includes AnyGraph, UniLP, TFMLinker, Common Neighbors, Adamic–Adar, PEARL, and CondPSE, together with completed GPSE and Global PSE comparisons. We may extend this set with other important baselines as the evaluation develops. The zero-shot methods and classical heuristics will be evaluated on the same Link2 datasets under the same protocol.

W2. Incomplete GPSE and Global PSE comparisons. A key limitation identified in our paper is the difficulty of scaling full-graph structural target computation to large graphs. Under our computational budget, this prevented GPSE and Global PSE from completing evaluation in our setting, which includes several such graphs. We agree, however, that these timeouts leave their predictive performance relative to LPPE unresolved. To address this, we will add a separate comparison on smaller graphs where all methods can complete, allowing their predictive performance to be assessed under matched conditions.

W3 and Q2. Measured efficiency. The theoretical analysis in the paper is insufficient to support practical efficiency claims on its own, and the qualitative ratings in Table 1 need empirical grounding. Although we recorded some training and inference times, runs conducted on different machines are not directly comparable. We will repeat the efficiency measurements in a standardized environment and report wall-clock runtime, memory consumption, and throughput. This evaluation will include LPPE, explicit local encodings, GPSE, and global encodings, including sparse implementations, across graphs of increasing size. We will revise the qualitative claims to reflect the measured evidence.

W4. Relationship to previous methods. We acknowledge the substantial methodological inheritance from GPSE and the established use of local subgraphs in link prediction, including SEAL, ELPH, and BUDDY. We will sharpen the distinction between these foundations and our specific contribution: learning reusable node representations from locally computed structural targets for transfer to unseen graphs without target computation or graph-specific fitting.

Q3. Neighborhood, sampling, and target ablations. Following your feedback we will run more ablation on the hyper parameters chosen. The six supervision targets were selected based on the cited GPSE framework; we agree that this precedent does not replace validation in our local setting. We will test individual targets and combinations to determine which contribute to performance and whether the full set is needed. We also intend to explore additional structural metrics as part of this investigation.

Reviewer_S6nYOpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
2
Soundness
1
Read review
Paper summary

This paper studies the problem of scalable zero-shot link prediction. The authors propose LPPE, a two-stage framework that learns transferable node representations by predicting structural encodings computed on PPR-sampled local subgraphs. The learned representations are then used by a graph transformer for link prediction without graph-specific fine-tuning.

Critical strengths

S1. The problem of scalable zero-shot link prediction across diverse graphs is important and practically relevant.

S2. The use of local structural supervision provides a practical approach to reducing the computational cost of structural encoding.

Critical weaknesses

W1. The proposed LPPE largely follows the GPSE framework, with the main modification being the replacement of full-graph PSE supervision with PSE targets computed on PPR-sampled local subgraphs. The remaining components primarily build on existing methods, making the methodological novelty limited.

W2. Although the paper evaluates 33 datasets, it primarily reports aggregated results without providing per-dataset performance. I suggest reporting detailed results on the 18 held-out Link2 datasets to better assess the consistency of zero-shot generalization across different graphs.

W3. The evaluation lacks comparisons with representative zero-shot link prediction methods, such as AnyGraph and UniLP, as well as recent learnable structural encoding methods, such as PEARL and CondPSE.

W4. Although computational efficiency is a central motivation, the paper provides only theoretical complexity analysis without systematic runtime and memory comparisons.

Questions for authors

Q1. The paper lacks ablation studies on the six PSE supervision targets. Could the authors evaluate their individual contributions and compare against a local structural encoder without PSE supervision to justify their necessity?

Q2. LPPE improves AP and ROC-AUC but achieves worse BCE than the random-feature baseline. Could the authors explain this discrepancy and discuss its implications for zero-shot link probability estimation?

1 comment
AuthorsOpenReview ↗

LPPE’s contribution, per-dataset results, and evaluation

Thank you for the time you devoted to reviewing our paper and for your constructive feedback. Your comments identify important opportunities to strengthen both the evaluation and the presentation of LPPE’s contribution.

Some of the requested results are already available, while others require additional experiments. Completing the comparisons and ablations under consistent conditions will require substantial work and compute time. We want to develop a more complete and rigorously validated study, with empirical evidence that adequately supports its conclusions. Below, we address your concerns in the order raised.

W1. Methodological contribution. We acknowledge that LPPE builds on GPSE’s structural supervision framework and uses established architectural components. Our contribution is to show how localizing structural target generation to bounded, root-centered neighborhoods enables this approach to scale to large graphs while learning representations that transfer to unseen graphs. These results suggest that local structural supervision can provide a promising basis for graph foundation models. We will clarify this contribution and strengthen the empirical evaluation of its scalability and benefits relative to existing approaches.

W2. Per-dataset performance. We agree that aggregate results do not adequately reveal how consistently LPPE generalizes across graphs. In the revision, we will report results separately for each of the 33 training and held-out Link2 datasets, alongside the aggregate statistics.

W3. Missing comparisons. We plan to expand the evaluation to include AnyGraph, UniLP, TFMLinker, Common Neighbors, Adamic–Adar, PEARL, and CondPSE, and to complete the comparisons with GPSE and Global PSE. We will consider additional relevant baselines as the experiments progress.

W4. Computational efficiency. The submission includes a theoretical complexity analysis, but we agree that measured runtime and memory consumption are important to substantiate the efficiency claims. We retained some training and inference runtimes; however, some runs were performed on different machines, so those measurements do not provide a fair comparison. We will rerun the efficiency experiments under a consistent hardware and software setup, measuring both runtime and memory consumption.

Q1. Structural supervision ablations. Our choice of six PSE targets followed the cited GPSE work. This provided a starting point, but it does not establish that all six targets are necessary or equally useful for local structural learning. Following your feedback, we will evaluate the targets individually and in combinations. We will also investigate additional candidate structural metrics.

Q2. Higher AP and ROC-AUC but worse BCE. AP and ROC-AUC measure ranking quality, whereas BCE evaluates the predicted probabilities and strongly penalizes confident incorrect predictions. Better ranking can therefore coexist with worse BCE. Our results indicate that LPPE improves the ranking of candidate links, but its probability estimates perform worse under BCE than those of the random-feature baseline.

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

Related papers

Discussion (0)

Sign in to comment.