- Rating
- 2
- Confidence
- 4
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
The paper shows that 'incidence RWPE' and 'editable RWPE' can solve the difficulties of applying RWPE (which is commonly used in Graph Transformers) to link prediction. In particular, the authors claim that their model achieves the best performance on ogbl-ppa while using fewer parameters than previous models.
Critical strengths
-
The math is clear and can be verified.
-
The design is simple, and the observations are useful.
Critical weaknesses
-
If there is no reason why a Transformer(TF) must be used for link prediction, I think using TF is itself a limitation because TF has high computational costs. Fig1 makes it look as if Vephormer has a lower computational cost than others(ex. Optimized GAE), but Optimized GAE has many parameters mainly to store node embeddings. In actual computation, Optimized GAE only needs to compute on the whole graph once and all node pairs share the results. In contrast, TF-based models need to repeat computation for each pair even if they have fewer parameters.
-
The main experiment in this paper is on ogbl-ppa, but the authors report results using only two random seeds (and, in fact, the performance improvement on the other datasets is not very large). This raises some concerns about seed selection and the reliability of the reported results. I think the experiments should be run with seeds 0, 1, 2, 3, and 4 for a fairer evaluation, and the code used to run these experiments should also be released. (The Planetoid datasets are also small graphs, but the authors used only three seeds. Also, the supplementary code does not include the code or settings for Planetoid, which raises concerns about reproducibility...)
Questions for authors
-
Could you report the training and inference time of Vephormer compared to others (ex. Optimized GAE, MPLP+, GraphGPT, PENCIL, ... etc)? This would help clarify the computational cost of using a Transformer.
-
Could you provide ablation results on ogbl-ppa using only vertex tokens, without edge returns, and with local RWPE? (If this is too expensive on ogbl-ppa, smaller datasets such as Planetoid or a subset of ogbl-ppa would also be helpful). This would help clarify the contribution of each component.
-
Could you run ogbl-ppa with five seeds (0, 1, 2, 3, 4) using the same code (version + settings), including those for Planetoid? This would help address concerns about the reliability and reproducibility of the results.
4 comments
Seeds, the size of the gains, and reproducibility (W2, Q3)
We reran Vephormer over the 5 seeds {0,...,4} on the OGB graphs and the 10 seeds, {0,...,9}, on the Planetoid graphs, all consecutive from 0 and all seeds of a graph under one configuration (please see the general comment "Main results over consecutive seeds from 0" above or Table 1 in the revised PDF). On ogbl-ppa the five seeds give 84.27 ± 0.45 Hits@100, ranging from 83.51 to 84.73, and each of them exceeds every published result, the best of which is PENCIL's 79.54. On the other benchmarks Vephormer is first on pubmed and second on cora, citeseer, ogbl-collab, and ogbl-citation2, where it is 0.07 points behind GraphGPT with a thirtieth of its parameters. On pubmed it leads LPFormer by 1.47 points, or 15 percent of LPFormer's 9.99, and on the other four it lies 0.07 to 1.36 points behind the best other method. We agree that some of these differences are small, and on those four we claim only that Vephormer ranks second while reading neither heuristics nor vertex identifiers.
The updated supplement contains every script and configuration needed to reproduce each result of Tables 1 to 3 and Figure 5, on the Planetoid graphs and the OGB graphs alike.
Ablations (Q2)
The general comment "Ablations" above reproduces Table 2 of the revised PDF, which holds the requested variants on every Planetoid graph, ogbl-collab, and ogbl-ppa.
- We understand "without edge returns" as without edge encodings, and in our framework that is the same ablation as "only vertex tokens", the row "− edge tokens". An edge token is placed in the graph only by its encodings, so without them there can be no edge tokens either, and removing the edge tokens removes their encodings with them. This variant, "− edge tokens", keeps the vertex tokens' walk encodings, and, having no token for the query edge, it scores the pair by a symmetric head over the two endpoints' vertex tokens using the sum and Hadamard product of their states. Its vertex tokens fill the same token budget as Vephormer's vertex and edge tokens, so it sees more of the graph around the query than Vephormer does.
- Local RWPE is the row "→ subgraph walks", where every walk encoding is recomputed for each query on the small subgraph its tokens span, so its walks see only that subgraph. In this variant local RWPE replaces editable RWPE, whose walks run on the whole graph and are exact for each query.
Both fall below Vephormer on every graph, and local RWPE costs ogbl-ppa 35.1 points. If you had another variant in mind, we would welcome the suggestion.
We hope these answers and the revision address your concerns, and we would be glad to answer any further question.
Thank you for additional results. However, I'm still not convinced computational cost of Transformer is sufficiently justified by overall performance gains. Therefore, I'll maintain my score.
We appreciate your review and your response. We would like to add some context on the cost.
Subgraph transformers are a leading approach, and Vephormer is the most efficient of them
Link predictors fall into two families, the whole-graph approaches and the subgraph approaches. Whole-graph approaches embed the graph once and score every pair from the shared embeddings, whereas subgraph approaches read each pair's own neighborhood. So the cost you point to reflects the difference between the whole-graph and the subgraph approaches more than any choice of transformer. Within the subgraph approaches, the transformer is a leading architecture, as GraphGPT (ICML 2025) and PENCIL (ICML 2026), each with the best published result on one OGB benchmark, show.
Among subgraph approaches, Vephormer takes the least time and scores the highest on ogbl-ppa (Table 25 of the revised PDF):
| model, ogbl-ppa | transformer | seconds to score the test set | test Hits@100 |
|---|---|---|---|
| SEAL (NeurIPS 2018) | no | 4,568 | 48.80 |
| GraphGPT (ICML 2025) | yes | 65,681 | 76.55 |
| PENCIL (ICML 2026) | yes | 3,345 | 79.54 |
| Vephormer | yes | 1,120 | 84.27 |
Whole-graph approaches save cost only when many candidates are of interest simultaneously
Which family costs less depends on the task and on how it is evaluated. A whole-graph model pays for one pass over the graph and shares it across the pairs it scores, whereas a subgraph approach pays for each pair's neighborhood separately. So the whole-graph approaches are cheaper when many candidates are scored at once, as in the benchmark's evaluation.
But consider a task that asks about only a few given pairs, such as which of two candidate links is the more likely, or how likely each of a handful of candidates is. There a whole-graph model still pays its full pass, whereas a subgraph approach pays only for the neighborhoods of those pairs. Counting the network's floating-point operations to score one pair alone (Table 28 of the revised PDF, in Appendix Q.4), Vephormer costs less than the whole-graph models until about 24 to 540 candidates are scored together:
| model, ogbl-ppa | operations to score one pair |
|---|---|
| GAE | |
| NCN | |
| GCN | |
| SAGE | |
| Optimized GAE | |
| Vephormer |
When only a few candidates are asked about, the cost no longer favors the whole-graph approaches. A subgraph approach, such as Vephormer, can then be both cheaper and more accurate.
Editable RWPE is agnostic to the architecture, subgraph or whole-graph
Editable RWPE, the rank-two correction that is one of our two core contributions, can benefit subgraph and whole-graph approaches alike, with or without a transformer. It improves a GCN link predictor, a whole-graph model, on the three larger graphs, pubmed, ogbl-collab, and ogbl-ppa (Section 6.3 of the revised PDF, and our response above).
Thank you for the review and the concrete requests. We have incorporated all of them into the revision. We welcome you to look at the revised PDF, and below we point to the changes in it and to the general comments that answer each point.
Why a transformer (W1)
We agree that a model that embeds the whole graph once is cheaper, and the more so the larger the graph. However, whether a pair is linked often depends on the structure around that pair, and models that read each pair's own neighborhood, from SEAL to transformers over a pair's own tokens such as LPFormer and PENCIL, have often been more accurate than models that embed the graph once, at the cost of reading every pair separately. A transformer suits that reading, since it takes a variable set of tokens and lets every token attend to every other in the neighborhood, and graph transformers have proved effective on many graph tasks. What a model reading only the pair's neighborhood lacks is the structure beyond it, and editable RWPE supplies that structure, giving every token its walks on the whole graph, exact for each query. On ogbl-ppa, a large and dense graph, this combination leads every published result.
We do not claim that a transformer in its current form is the final architecture, for link prediction in particular or for graphs in general. We expect a better architecture to combine the structure of the whole graph with a rich reading of each pair's neighborhood, and our work is a step in that direction.
Furthermore, the encodings are not tied to a transformer. In Section 6.3 of the revision, we study feeding the query pair's walk encodings, corrected by editable RWPE, to HeaRT's GCN link predictor, which already propagates over the whole graph (Table 3 of the revised PDF, reproduced here). Test results in percent, mean ± std over seeds {0,…,4}, on ogbl-ppa {0,1}:
The encodings raise the GCN by 5.47 points on pubmed, 1.11 on ogbl-collab, and 11.81 on ogbl-ppa, whose two seeds lie 10.80 points apart, and leave it within one standard deviation on cora and citeseer. So the whole-graph walks can improve a link predictor that has no transformer.
Computational cost and Figure 1 (W1, Q1)
You are right that the previous Figure 1, by setting parameter counts side by side, may have given the impression that Vephormer has the lower computational cost. We agree that a model's parameter count does not measure its compute, and that a transformer scoring each pair costs more than a model that embeds the graph once. We removed that figure from the main text, and the revision measures the cost instead (Figure 4; Appendix Q). The general comment "Computational cost on ogbl-ppa" above gives the training and inference time of every model on ogbl-ppa. Vephormer scores the test set in 1,120 seconds, against 2.0 for Optimized GAE, 36.1 for MPLP+, 3,345 for PENCIL, and 65,681 for GraphGPT. Vephormer costs more than Optimized GAE, as you expected, and less than PENCIL and GraphGPT, the other transformers over a pair's own sequence, while it scores higher than all four.