- 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 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 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?
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.