acceptodds
Under review as a conference paper at ICLR 2027

Links Are Tokens as Nodes Are: Incidence-Graph Transformers with Editable Walk Encodings for Link Prediction

Abstract

Two gaps have kept the random-walk positional encoding (RWPE), now a standard input to graph transformers (GTs) on other tasks, out of the ones built for link prediction (LP). First, RWPE is defined at a vertex, and the object to be scored, an edge, has not been given one. Second, the walk probabilities around a pair of vertices depend on whether the pair has an edge in the graph, so a model either reads that edge's presence off its encodings, which fails to generalize, or recomputes them for every query, which fails to scale. We close both gaps with incidence RWPE and editable RWPE. We prove that on the incidence graph, whose vertices are the vertices and the edges of the original graph, the walk with each edge given its two orientations takes one step of the original walk every two steps, so every vertex and every edge around a query carries an RWPE of its own class, computed from powers of the original graph's operator alone: incidence RWPE. We also prove that the common-neighbor heuristics are closed-form functions of these encodings. Links are then tokens as nodes are, the query edge among them, scored by a transformer with no message passing, no topological attention mask, and no node identifiers. Editable RWPE, a rank-two correction, reads every encoding on the graph the query is scored under from encodings computed once per graph, at a cost per token quadratic in the walk length and independent of the graph's size. With fewer than five million parameters, Vephormer, our Vertex-Edge Graph Transformer, exceeds every published result on ogbl-ppa and matches or exceeds every GT on all six benchmarks. Ablations find the context tokens worth nearly a quarter of the model's score on ogbl-ppa, and a message-passing after every block largely redundant.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
graph representation learning, link prediction, graph transformers, positional encodings, random-walk positional encodings, structural encodings, incidence graph, edge tokens, low-rank updates, data leakage

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_dgDwOpenReview ↗
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
  1. The math is clear and can be verified.

  2. The design is simple, and the observations are useful.

Critical weaknesses
  1. 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.

  2. 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
  1. 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.

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

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

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}\{0,\ldots,4\}, on ogbl-ppa {0,1}\{0, 1\}:

GCNcora MRRciteseer MRRpubmed MRRogbl-collab Hits@50ogbl-ppa Hits@100
no walk encoding17.17 ± 0.6021.54 ± 0.527.15 ± 0.4753.09 ± 1.3826.83 ± 2.48
editable RWPE16.67 ± 0.1921.30 ± 0.3312.62 ± 0.9054.20 ± 0.6638.64 ± 7.64

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.

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-ppatransformerseconds to score the test settest Hits@100
SEAL (NeurIPS 2018)no4,56848.80
GraphGPT (ICML 2025)yes65,68176.55
PENCIL (ICML 2026)yes3,34579.54
Vephormeryes1,12084.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-ppaoperations to score one pair
GAE3.1×10103.1 \times 10^{10}
NCN3.1×10103.1 \times 10^{10}
GCN2.3×10112.3 \times 10^{11}
SAGE3.6×10113.6 \times 10^{11}
Optimized GAE6.9×10116.9 \times 10^{11}
Vephormer1.3×1091.3 \times 10^{9}

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

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

This paper introduces Vephormer, a Transformer-based model for link prediction that uses both node and edge information, along with random-walk positional encodings, to capture graph structure. The authors show how these features can represent several common link-prediction heuristics and capture structural differences that traditional methods may miss. They also introduce an efficient rank-two update that adjusts the random-walk features when a candidate edge is added, helping prevent data leakage without requiring expensive computations for every query.

Critical strengths
  1. Coherent problem formulation: lack of an edge positional encoding and query-edge-state leakage.
  2. Strong large-graph results
  3. Useful correction mechanism.
  4. Transparent qualifications: the manuscript distinguishes representability from trainability, notes the missing depth experiment, discloses limited seeds and admits that parameter count does not equal compute cost.
Critical weaknesses
  1. Insufficient isolation of the proposed components (see Q1 and 2).
  2. Limited experimental validation of higher-order walk encodings (see Q3).
  3. Limited evaluation of generalization beyond the studied benchmarks (see Q4 and 5).
Questions for authors
  1. Could the authors provide more detailed ablation experiments to quantify the individual contributions of the proposed components, particularly edge tokens and editable RWPE, to predictive performance and computational efficiency?
  2. How would Vephormer perform compared with a node-only Transformer equipped with the same relative RWPE features, a symmetric pair-level prediction head, and a matched computational budget?
  3. How does Vephormer's performance change with different random-walk depths?
  4. Could the authors provide additional experiments demonstrating whether the proposed incidence RWPE and editable RWPE framework generalizes to other graph-learning settings, such as dynamic link prediction or graphs with edge attributes? 5.Could the authors apply the method over heterophilic datasets?
2 comments

Thank you for the review and the precise questions. We have incorporated your suggestions into the revision, all but dynamic link prediction, which we leave to future work. 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.

Q2, a node-only transformer

The variant "− edge tokens" of Table 2 in the revised PDF (also in the general comment "Ablations" above) is the node-only transformer you describe. It reads the same relative walk encodings, holds at most as many tokens per query as Vephormer, and scores the pair with a symmetric head over the two endpoint embeddings, using the sum and the Hadamard product of their states. It scores below Vephormer on every graph, by 8.4 points on citeseer, 3.4 on cora, 3.5 on ogbl-collab, and about 1 on pubmed and ogbl-ppa.

Q3, the walk depth

Figure 5 of the revision plots the scores of the reported configuration against the walk depth, from 0 to 9, on the three Planetoid graphs, ogbl-collab, and ogbl-ppa, and the general comment "Walk depth" above tabulates it. Without walk encodings every score falls, and past depth 2 the depth matters little except on ogbl-ppa, where each step up to depth 3 gains.

Q1, the components

Q2 above gives the contribution of the edge tokens, so here we turn to editable RWPE. Its accuracy is measured by two contrasts, and its efficiency follows them.

Editable RWPE against local RWPE

Editable RWPE reads the walks on the whole graph, exact on each query's graph, whereas local RWPE recomputes them on each query's subgraph and sees only that subgraph. Replacing editable RWPE with local RWPE ("→ subgraph walks" in Table 2) lowers every score, by 35.1 points on ogbl-ppa and 4.3 on ogbl-collab (the general comment "Ablations" above).

Editable RWPE against no walk encoding and against uncorrected walks

Without the correction, walks read on the given graph GG reveal whether the query edge is present, and Vephormer can learn that shortcut (Table 4 of the revised PDF, in Appendix E, reproduced here).

Test MRR in percent, mean ± std over seeds {0,…,4}\{0,\ldots,4\}, beside the training loss at the last epoch:

Vephormercora testcora lossciteseer testciteseer losspubmed testpubmed loss
no walk encoding15.19 ± 0.720.01024.84 ± 0.640.0068.50 ± 0.370.009
walks read on GG, uncorrected15.35 ± 0.370.000114.43 ± 0.320.00014.55 ± 0.260.0000
editable RWPE17.08 ± 0.290.01125.24 ± 0.710.00712.01 ± 0.230.018

Without the correction, Vephormer's training loss falls a hundredfold, to nearly zero, and its test score falls below editable RWPE's on every graph, by 10.81 points on citeseer. A GCN shows the same (Table 5 of the revised PDF, in Appendix F, reproduced here). Test results in percent, mean ± std over seeds {0,…,4}\{0,\ldots,4\}, on ogbl-ppa {0,1}\{0, 1\}:

GCNcora MRRciteseer MRRpubmed MRRogbl-collab Hits@50ogbl-ppa Hits@100
no walk encoding17.17 ± 0.6021.54 ± 0.527.15 ± 0.4753.09 ± 1.3826.83 ± 2.48
walks read on GG, uncorrected5.87 ± 0.566.32 ± 0.614.22 ± 0.3549.58 ± 0.391.19 ± 1.56
editable RWPE16.67 ± 0.1921.30 ± 0.3312.62 ± 0.9054.20 ± 0.6638.64 ± 7.64

Without the correction, the GCN falls below editable RWPE on every graph, to 1.19 Hits@100 on ogbl-ppa.

Editable RWPE, for efficiency

Editable RWPE computes the walks once on the whole graph and only corrects them for each query pair. On ogbl-ppa, the encodings of all 68 million query pairs of a training run thus take 641 seconds, about half the time of one training epoch (Appendix Q.3). Recomputing them for each query pair instead, at the rate PENCIL reports for its per-subgraph encodings, would take about 11 days for a single epoch. The general comment "Computational cost on ogbl-ppa" above gives the details.

Q4, edge attributes and dynamic graphs

Yes, one of our benchmarks already has edge attributes, and Vephormer uses them. On ogbl-collab each edge records a pair's collaborations, and since an edge token carries its edge's attributes by construction, we give every edge token its pair's history, its count of collaborations, their summed weight, and the years since the last one. These are the only attributes Vephormer reads there, and removing them ("− attributes" in Table 2, in the general comment "Ablations" above) lowers its Hits@50 from 71.14 to 67.67 on validation and from 70.96 to 67.69 on test. Table 20 of the revised PDF (Appendix O.3) also separates the query edge's own count from the history on every edge token, reproduced here:

Hits@50 (%), seeds {0,…,4}\{0,\ldots,4\}validtest
no edge data ("− attributes" in Table 2)67.67 ± 0.2167.69 ± 0.46
the pair's count on the query-edge token only68.53 ± 0.2868.71 ± 0.28
and every edge token's history71.07 ± 0.0970.48 ± 0.31
every edge token's history alone (Table 1)71.14 ± 0.2370.96 ± 0.43

Beyond the query edge's count, the history on every edge token adds 2.5 points on validation and 1.8 on test, on every seed, and vertex tokens alone have no token for a context edge's history. Dynamic link prediction we have not run, and we agree it is a natural next setting. There the rank-two correction would update the encodings cheaply as edges arrive, rather than recomputing the walks, and the conclusion of the revision names it as a setting editable RWPE suits.

Q5, heterophily

Appendix N adds the heterophilic Wikipedia graphs Chameleon and Squirrel, with every baseline run on one split under one protocol (Table 16 of the revised PDF, reproduced here in part).

MRR (%), seeds {0,…,4}\{0,\ldots,4\}Chameleon validChameleon testSquirrel validSquirrel test
Vephormer91.51 ± 1.5088.27 ± 3.2087.55 ± 3.2559.35 ± 10.37
PENCIL94.55 ± 1.0885.13 ± 16.20––
Optimized GAE82.80 ± 1.6262.62 ± 8.4679.22 ± 0.9639.48 ± 6.09
NCN72.76 ± 4.0333.59 ± 10.5270.25 ± 2.1540.97 ± 7.78
LPFormer84.37 ± 2.9246.62 ± 14.7871.72 ± 9.0030.30 ± 6.23
Link-MoE83.86 ± 5.0139.82 ± 15.4584.24 ± 2.6920.68 ± 4.64

Vephormer has the highest test MRR on both graphs. On Chameleon its test lead over PENCIL lies within PENCIL's spread, and PENCIL leads on validation.

We hope these answers and the revision address your concerns, and we would be glad to answer any further question.

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

The article proposes a transformer model for link prediction that treats vertices and edges as tokens using random-walk encodings. The main idea is to transform the original graph G into an incidence graph G' which additionally has edges of G as nodes, while ensuring that the random walks on G and G' are the same. In order to avoid leakage, encodings are computed on the graph plus the query edge. Here the authors show that this can be done efficiently. The set of vertices and edges around the query edge (with their encodings) is then fed to a transformer to score it. In an experimental section, the authors show that their model is competitive on most datasets and outperforms all others on pubmed and ogbl-ppa.

Critical strengths

The approach is well motivated. The idea of representing edges via the incidence graph to treat them as tokens is simple and clean. The method seems to be quite efficient due to the closed-form correction.

I appreciated Proposition 3 on the capability of the encodings to recover the common-neighbour heuristics. This is a neat expressivity result showing that their approach captures rich information, though the result itself is somewhat straightforward.

Critical weaknesses

I found the article very hard to follow. Multiple parts of the paper were a struggle to read and parse. In particular:

  • The article contains lots of overly long sentences chained together with colons and semicolons.
  • Already abstract and introduction are hard to understand due to terminology that the reader does not know about yet (e.g., “two orientations”, “depth-three return”). It reads a little like a summary for people that already know the content.
  • Grammatical errors further hurt readability (e.g. line 135-136).

Overall, I find the method to be interesting and the results promising. However, in my eyes, the language in the paper makes the paper too hard to follow. Addressing this would require a substantial overhaul, which is beyond what can or should be done during the rebuttal. As of now, I believe the article is not ready for publication, preventing me from recommending acceptance. Relatedly, I may have missed or misunderstood some of the contents, and I have chosen my confidence accordingly.

Questions for authors
  • Have the authors considered alternative walk-based encodings?
3 comments

Thank you for the review and the points on readability. We have incorporated all of your suggestions 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 above that answer each point.

Readability

We rewrote the paper. We shortened its sentences and no longer join clauses by a colon or a semicolon alone. The tables compare the main text of the previous submission and of the revision.

number of sentencesprevious submissionrevision
all170278
longer than 35 words5417
with a colon or a semicolon641
length in wordsprevious submissionrevision
median2820.5
75th percentile3826
90th percentile5532
longest8855
  • Every term and symbol is defined at its first use.
  • We rewrote the abstract and the introduction to explain the ideas with fewer specialized terms, and leave the technical details to later sections.
  • We have corrected all grammatical mistakes.

Alternative walk encodings

In this work we focus on RWPE because it is a widely used walk encoding for graph transformers. For this revision we also tried three other encodings built from the same walk, Chebyshev polynomials, personalized PageRank, and the random-walk heat kernel, each cut at the same depth, which our correction handles too (Appendix H of the revised PDF). The general comment "Alternative walk encodings" above gives the results, in which the four encodings score within 1.8 points of one another on the Planetoid graphs.

Thank you for the response. As I stated before, I believe that a complete re-write of the paper goes beyond what a rebuttal is meant for and therefore I have not reviewed the paper again. I remain my score.

We appreciate your review and your response, and we understand your view.

Just to clarify, the rewrite in the revision mainly consisted of rephrasings, alongside the added experiments. The structure of the main text (every section, and most subsections), the method, the theory, and the main results remain intact. We welcome you to look at the abstract and the introduction, where the rephrasing for readability was focused.

Comments on the paper

5 comments
AuthorsOpenReview ↗

Alternative walk encodings

In response to FwuY's review, we tested Vephormer with three other walk encodings of the same depth in place of the walk powers PkP^{k} (Appendix H). In this work we focus on RWPE because it is a widely used walk encoding for graph transformers. However, the rank-two correction behind editable RWPE applies to any encoding that is a weighted sum of the powers P0,…,PKP^{0}, \ldots, P^{K} of the random-walk matrix PP. These include Chebyshev polynomials of the walk, a truncated personalized PageRank, and a truncated random-walk heat kernel, the three we tried. RWPE and the Chebyshev polynomials give each power its own coordinate, whereas PageRank and the heat kernel sum the powers into one coordinate with fixed weights.

Table 6 of the revised PDF (Appendix H), reproduced here in part. Test MRR in percent, mean ± std over seeds {0,…,4}\{0,\ldots,4\}:

walk encodingcoraciteseerpubmed
RWPE (Vephormer)17.65 ± 1.1527.09 ± 0.6111.38 ± 0.63
Chebyshev basis17.27 ± 0.6825.81 ± 1.3911.76 ± 0.37
personalized PageRank, α=0.15\alpha = 0.1518.00 ± 0.6226.31 ± 1.0511.58 ± 0.40
heat kernel, t=1t = 117.46 ± 0.7625.66 ± 1.5211.70 ± 0.48

On the Planetoid graphs the four encodings score within 1.8 points of one another on validation and test, mostly within the spread over seeds.

AuthorsOpenReview ↗

Computational cost on ogbl-ppa

In response to dgDw's and yqU5's reviews, we measured on ogbl-ppa the cost of every model, and the cost of Vephormer's walk encodings alone (Appendix Q).

The cost of every model

We timed every model's own release on one RTX 4090. In the revised paper, Figure 4 in the main text plots each model's score against the time to score the test set, and Figure 9 in Appendix Q adds three panels, the parameter count, the FLOPs of one training epoch, and its time. We agree that a model's parameter count does not measure its compute, and that a transformer scoring each pair costs more per pair than a model that embeds the graph once. Accordingly, we removed the parameter-count plot, the previous submission's Figure 1, from the main text and kept it in Appendix Q beside the time and FLOPs.

Table 25 of the revised PDF (Appendix Q.2), reproduced here in part. Seconds as mean ± std over two runs:

modeltest Hits@100seconds to score the test settraining seconds per epoch
Vephormer84.271,120 ± 167,646 ± 44
PENCIL79.543,345 ± 3728,432 ± 556
Optimized GAE78.412.0 ± 0.0194 ± 0
GraphGPT76.5565,681 ± 515not measured
MPLP+65.2436.1 ± 0.0519 ± 0
LPFormer63.3276.8 ± 0.3480 ± 0
NCNC61.42179 ± 01,549 ± 0
NCN61.199.1 ± 0.2329 ± 0
  • The test set has 6.0 million candidates. An epoch is the unit of training compared, since how many epochs a run takes is set by each release's schedule or early stop.
  • Vephormer costs more than the embedding and message-passing models and LPFormer, and less than PENCIL and GraphGPT, the other transformers over a pair's own sequence.

The cost of the walk encodings

Vephormer computes the walk encodings once on the whole graph and corrects them for each query. Table 27 of the revised PDF (Appendix Q.3) times them in one training run on ogbl-ppa, on the four RTX PRO 6000 GPUs that trained Vephormer, reproduced here in part:

one training run on ogbl-ppasecondsminutes
the walk encodings of its 68 M query pairs64110.7
one training epoch, the median over the run1,22120.4
  • The walk encodings are computed once for the whole run, for all its 68 million query pairs, in 641 seconds.
  • That is only about half the time of a single training epoch.
  • Recomputing them for each query instead, at the rate PENCIL reports for its per-subgraph encodings, would take about 11 days for the 42 million training queries of a single epoch, at the depth of 3 we use (Appendix Q.3).
AuthorsOpenReview ↗

Walk depth

In response to yqU5's review, we varied the walk depth of the reported configuration on the three Planetoid graphs, ogbl-collab, and ogbl-ppa (Figure 5). Figure 5 of the revised PDF, reproduced here as a table. Test results in percent, mean ± std over seeds {0,…,9}\{0,\ldots,9\} on the Planetoid graphs, {0,…,4}\{0,\ldots,4\} on ogbl-collab, and {0,1}\{0, 1\} on ogbl-ppa except depth 3's {0,…,4}\{0,\ldots,4\}:

depthcoraciteseerpubmedogbl-collabogbl-ppa
0, no walk encoding15.13 ± 0.5025.13 ± 1.378.02 ± 0.4049.03 ± 0.4941.26 ± 0.48
116.81 ± 0.9826.73 ± 0.7411.65 ± 0.3766.26 ± 0.6858.63 ± 1.25
216.83 ± 0.9426.46 ± 0.6511.74 ± 0.5171.23 ± 0.5481.18 ± 0.72
3, as in Table 117.48 ± 0.8527.29 ± 0.7011.46 ± 0.5770.96 ± 0.4384.27 ± 0.45
517.23 ± 0.9127.08 ± 0.9811.62 ± 0.4770.74 ± 0.60–
717.26 ± 0.6826.82 ± 0.7111.30 ± 0.38––
917.16 ± 1.0327.01 ± 0.9611.14 ± 0.55––
  • Without walk encodings every score falls, and ogbl-ppa loses 43 points.
  • Past depth 2 the depth matters little on ogbl-collab and the Planetoid graphs, whereas on ogbl-ppa each step up to depth 3 gains.

Appendix O gives more details.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.