acceptodds
Under review as a conference paper at ICLR 2027

Reusable Graph Representations for Path Prediction

Abstract

Graph–path learning predicts properties of ordered paths in shared graphs, with applications in network routing and comparative biology. In this article, we advocate for caching graph representations: sharing their encoding cost across many path queries is crucial for large-scale applications. We make three contributions. First, we introduce the Edge–Vertex Transformer (EVT), which couples vertex states with direction-aware pair attention, and an aligned graph-to-path construction that separates reusable graph encoding from path processing. Second, we characterize the expressivity of this model by a path-indexed two-dimensional folklore Weisfeiler–Leman (2-FWL) profile. Every compatible continuous prediction can be uniformly approximated on compact domains using one parameter set shared across jointly bounded graph and path sizes. We also establish a strict hierarchy between selection, joint cache reading, and path-marked encoding. Third, we build a coherent benchmarking suite combining controlled synthetic tasks, temporal routing measurements from RIPE Atlas, and ThorAxe-Combo, a curated biological benchmark of splicing tasks. The experiments distinguish information access from finite-resource learning: the most elaborate reusable pipeline benefits synthetic composition tasks and Atlas prediction, while simpler pair processors lead on ThorAxe-Combo. Our benchmarks also assess the computational gains enabled by graph-cache reuse. Together, these contributions identify when relational path processing justifies its computational cost.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
graph transformers, path prediction, Weisfeiler-Leman, triangular attention, reusable graph representations, protein language models

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_X5JYOpenReview ↗
Rating
3
Confidence
2
Informativeness
3
Presentation
3
Soundness
2
Read review
Paper summary

The paper proposes reusable graph representations for answering multiple ordered-path queries without re-encoding the graph each time. It introduces the Edge–Vertex Transformer and characterizes the expressive power of different cache-reading strategies. Experiments on synthetic tasks, Internet routing, and biological splicing demonstrate computational savings and task-dependent benefits of relational path processing.

Critical strengths

The paper separates quite well what a cached representation can express from what a finite model learns in practice. Also, the expressivity hierarchy provides a useful account of the trade-offs between selection, joint cache reading, and query-specific encoding. Finally experiments span controlled synthetic tasks and two real applications. The same-weight timing comparisons convincingly demonstrate the benefits of cache reuse.

Critical weaknesses

In practice the scalability verification remains quite limited. Graph encoding has cubic computational cost and the cache requires quadratic storage from what I see. Synthetic scaling measurements reach only 112 vertices, while Atlas graphs are capped at 256. Reuse reduces repeated computation, but these experiments do not establish whether the approach remains practical on substantially larger graphs.

The Atlas comparison does not isolate the benefit of the proposed architecture. TT uses approximately 779k parameters, compared with 449k for PP-MLP and 101k for PathTransformer, with different search costs. Its MAE improvement is around 0.26–0.28 ms. Since simpler processors outperform TT on ThorAxe-Combo, a budget-matched Atlas comparison is important to establish when the additional architectural complexity is worthwhile.

Questions for authors
  • How do encoding time, peak memory, and the number of queries needed to amortize encoding scale beyond the evaluated graph sizes?

  • Does TT retain its Atlas advantage when parameter counts and tuning budgets are matched?

  • Can you identify task characteristics that predict when triangular path processing helps, given its gains on synthetic composition and Atlas but weaker performance on ThorAxe-Combo?

8 comments

Update after reading the other reviews. I am inclined to lower my score to 2. I had asked whether TT keeps its Atlas advantage under matched budgets. As Reviewer HxAF notes, Table E.5 already suggests an answer: a selection reader on frozen PP-MLP caches reaches 10.956 ms, close to TT’s 10.940 ms, although the training protocols differ. TT’s gain on its only winning real-data benchmark may therefore come from tuning rather than from triangular path processing, and it costs about 3× more per path (1.896 vs 0.647 ms). Together with the ThorAxe results and my scalability concerns, the evidence does not yet show that the architecture justifies its cost. I still value the expressivity analysis and would reconsider if the authors provide a budget-matched comparison.

AuthorsOpenReview ↗

Q1 — Encoding time, memory and cache amortization

Q1: Scaling to larger graphs requires using a tiling mechanism to lift the O(n3)O(n^3) memory bottleneck, potentially at the price of a higher computational cost. This principle was already described in Appendix J.3 of the submission (Proposition J.2), but was not tested in the submitted experiments. Our bilinear triangular operator uses its own row/channel tiling, rather than a drop-in FlashAttention kernel. Activation checkpointing recomputes intermediate activations during the backward pass instead of retaining them. Neither technique removes the dense operator's cubic arithmetic cost. To evaluate more precisely the practical memory-time tradeoff, we have conducted two new evaluation experiments detailed below and in the revised version. These measurements establish computational feasibility up to 1,024 vertices without changing the submitted architecture. The profiles use one synthetic graph per size and do not establish predictive accuracy on larger real graphs.

Both experiments use the submitted Atlas TT architecture ( 778,897 parameters, width 64, two graph and two path EVT layers), an A100-SXM4-40GB, PyTorch 2.9.1/CUDA 12.9 and FP32 without TF32. Width, depth and precision remain unchanged.

Peak memory and execution time: forward + backward. This experiment uses initialized weights, one graph and 16 paths of length 16 processed together. It includes graph encoding, all predictions, a synthetic MSE loss and backward through both stages, without an optimizer step. Architecture, weights and inputs are identical across execution policies. Plain uses native execution; light and aggressive use progressively smaller triangular/cross-attention tiles and checkpointing, with additional whole-layer checkpointing in aggressive mode. Small-graph output, loss and parameter-gradient parity checks pass before profiling.

Each cell gives peak allocated memory in GiB (mean forward+backward time in ms) over ten timed repetitions after two warmups. Memory is the maximum allocated peak across repetitions, including resident weights and inputs. Initialization, transfers and gradient clearing are excluded.

Graph size nnPlainLightAggressive
25617.95 (726.03)1.62 (571.94)0.70 (1695.45)
512OOM6.29 (4839.51)2.59 (9019.97)
1,024OOM24.92 (38442.36)10.16 (71448.49)

OOM denotes failure under the common 35 GiB allocation cap. These are full forward/backward peaks and times, not cache sizes or isolated inference-encoding costs. Both optimized policies complete forward and backward at 1,024 vertices. At this size, aggressive execution reduces peak memory by 2.45×, at 1.86× the total time of light execution.

Encoding time and amortization: inference. Separately, we use a fixed trained checkpoint, aggressive graph-stage tiling and the unchanged path decoder; checkpointing is inactive. Distinct, unpadded paths of length k=8k=8 (Atlas median) are processed individually. Encoding time EE and decoding time per path DD are measured separately; decoding includes selection, projections and the prediction head. Timings exclude initialization and transfers. We average ten encodings and 320 decodes after warmups.

For QQ queries, with EE and DD expressed in the same units, total time is modeled as T=E+QDT = E + QD. The estimated count \widehat{Q}_{10\\%} = \lceil 9E/D \rceil makes initial encoding contribute at most 10% of this total.

Graph size nnEncoding EE (s)Decoding DD (ms/path)Estimated queries (10%)
2560.32217.508166
5122.17517.7061,106
1,02417.35417.4588,946

Counts use unrounded means. This is an amortization threshold, not the minimum query count that benefits from reuse. Re-encoding the same graph for every query would cost approximately Q(E+D)Q(E+D); under this model, reuse saves computation as soon as Q>1Q>1. At 1,024 vertices, encoding costs about 994 single-path decodes: approximately 994 queries make its share 50%, whereas 8,946 make it at most 10%.

Direct checks at Q=1Q=1, Q=4Q=4 and the estimated 50% threshold differed from E+QDE+QD by at most 5.52%. The 10% thresholds were not directly timed. Paths of length k=32k=32 gave similar decoding costs in this setup; this does not imply path-length-independent complexity.

We are sorry for our slow response, which is due to the extensive new numerical experiments we have been conducting to address questions precisely. First, we believe our new experiments now put the comparison between the different architectures on a fair basis. Second, it is indeed true that TT is not always the best-performing model, and its computational cost may lead one to consider lighter architectures. But it is important to recall that our contribution does not aim to demonstrate TT’s superiority, but to propose, theoretically analyze, and extensively benchmark a new family of modular two-stage architectures, which we now call StrikeTwice. This framework allows the graph encoder and path processor to be chosen independently. We denote these choices as ST[GraphEncoder, PathProcessor]: TT and PP-MLP correspond to ST[EVT, EVT] and ST[EVT, MLP], respectively, two configurations with different computational costs. Our new matched-capacity comparisons (Q2), frozen-cache ablations (Q3) and scaling measurements (Q1) directly address these concerns, while also documenting the remaining accuracy–cost trade-offs. We therefore hope you will consider these new results alongside our broader contribution of bringing together methods, theory and benchmarking around a well-defined learning problem. We are happy to elaborate further if the new numerical experiments do not adequately address your concerns.

As a small additional point, which was not requested in your questions, we adapted and evaluated RouteNet (Rusek et al., 2020): under a 24,000-update cap, RouteNet-SELU’s mean MAE is 10.886 ms, compared with 10.396 for TT and 10.460 for widened PP-MLP (see our response to Reviewer Q2t7, Q7 for more details).

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

This paper addresses graph-conditioned prediction for ordered path queries in settings where many paths share the same underlying graph. The authors argue that repeatedly encoding a path-marked graph is unnecessarily expensive and propose a reusable graph-first interface. The paper proposes caching a graph’s encoding to answer many path queries cheaply. It introduces the EVT/TT architecture, proves exactly what information such cached models can access, and tests them on synthetic, Internet, and biology benchmarks.

Critical strengths
  1. The distinction between query-dependent graph encoding and query-independent caching is both practical and conceptually clean.
  2. Multiple empirical perspectives
  3. The paper provides paired-seed studies, resampled synthetic graphs, factorial operator controls, longer optimization budgets, frozen-cache reader comparisons, and explicit descriptions of data splits.
  4. Rigorous theory.
Critical weaknesses
  1. The central architectural benefit is not consistent across tasks (see Q5).
  2. Empirical gains are modest or mixed: about 2% on Atlas, a loss on biology, and a small local MLP close behind on Task 1.
  3. The near-zero R² of Edge Transformers on Task 2, the lack of individual model tuning, and the absence of established baselines like RouteNet raise concerns about the fairness and reliability of the comparisons.
Questions for authors
  1. Why do the Edge Transformer baselines collapse on Task 2?
  2. Can you run MarkedEVTPat on Atlas and ThorAxe?
  3. How would this scale beyond a few hundred vertices?
  4. Why does the proposed TT architecture outperform simpler models on the synthetic benchmarks and RIPE Atlas, but underperform PP-MLP on ThorAxe-Combo?
  5. How sensitive are the reported improvements to hyperparameter selection, model initialization, and training duration?
  6. The Edge Transformer baselines achieve near-zero or negative R² on synthetic Task 2. Can the authors explain this substantial performance gap?
  7. Can you run RouteNet on Atlas?
11 comments
AuthorsOpenReview ↗

W1 & W3 — Modular architecture and comparison protocols

We thank the reviewer for the constructive feedback, which has helped us clarify our contributions and strengthen the experimental comparisons.

W1: We agree that using EVT at both stages does not consistently improve prediction. Nevertheless, we propose 2 architectural contributions. EVT allows us to configure vertex and pair attention separately. Our two-stage architecture, StrikeTwice, further allows us to vary the graph encoder and path processor independently. To make this clearer, we now write these choices as ST[GraphEncoder, PathProcessor], such that TT and PP-MLP architectures correspond to ST[EVT, EVT] and ST[EVT, MLP], respectively. Our benchmarks explore the choice of graph encoder and path processor across tasks, rather than focusing on demonstrating the superiority of TT = ST[EVT, EVT].

W3: We address each concern below. In Q1 and Q6, we investigate ET’s near-zero R2R^2 on Task 2 by testing its sensitivity to nuisance input features. In Q5, we address your concern about the lack of individual model tuning. We bring together the submitted experiments and additional experiments with model-specific tuning to assess sensitivity to hyperparameter selection, model initialization, and training duration. In Q7, we compare against two RouteNet adaptations on the same held-out Atlas paths.

AuthorsOpenReview ↗

W2 — Empirical gains and Atlas comparisons at 24,000 updates

W2: We agree that predictive gains are modest or mixed across tasks. However, comparisons among StrikeTwice configurations should be distinguished from comparisons with the other baselines.

  • Task 1: the small local MLP is not a generic graph–path competitor but a control baseline. We introduced it to ask how well the target can be learned when its local structure is supplied directly. This network bypasses both graph encoding and path processing. Even with this task-specific advantage, its mean test R2R^2 is lower than TT’s on both resampled datasets (0.892 versus 0.954 and 0.865 versus 0.912, respectively).
  • Task2: In the submitted results, TT=ST[EVT,EVT] and PP-MLP=ST[EVT,MLP] outperform ET-MLP = ST[ET,MLP] under a common initial learning rate, across five training seeds. New experiments give all ten submitted architectures the same model-specific learning-rate search (details in Q5). The mean test R2R^2 remains higher for TT and PP-MLP: 0.5893 and 0.5254, respectively, versus −0.0095 for ST[ET,MLP]. Q1 investigates the ET baselines’ sensitivity to irrelevant node features.
  • ThorAxe-Combo: In the submitted results, PP-MLP = ST[EVT, MLP] achieves higher mean AUROC than ST[ET,MLP] (0.702 versus 0.690).
  • Atlas RIPE: In a new experiment (details below), with matched training and tuning budgets and approximately matched parameter counts, TT = ST[EVT, EVT] retains a modest advantage over widened PathTransformer at 8,000 updates under the common learning-rate selection protocol, while widened PP-MLP= ST[EVT, MLP] slightly outperforms TT. We also report a separate duration control, keeping each model’s learning rate fixed between 8,000 and 24,000 updates. For TT, this control uses its historical rate of 3×10−43\times10^{-4}, which yielded lower August validation error than the screen-selected rate on all five seeds at 8,000 updates. Widened PP-MLP and PathTransformer retain their screen-selected rates. In this control, TT achieves lower mean error than both at 24,000 updates. Thus, the TT–PP-MLP ranking depends on the training budget and learning rate. In addition, we have performed the comparison requested in Q7 against the adapted RouteNet baselines and with matched tuning budgets and approximately matched parameter counts, Both StrikeTwice models (widened PP-MLP and TT) also outperform the adapted RouteNet baselines, as detailed in Q7.

Details of the new experiment in Atlas. Widened PP-MLP and TT each have 778,897 parameters; widened PathTransformer has 793,729, approximately 1.9% more. Each model received the same learning-rate screen over {10−410^{-4},3×10−43\times10^{-4},10−310^{-3}}, with 2,000 updates per rate at seed 0, followed by five evaluation seeds trained for 8,000 updates. Learning rates and checkpoints were selected on the same 4,096-query August cohort.

September MAE in milliseconds (lower is better), mean ± sample SD over five evaluation seeds.

ModelParametersSelected learning rateSeptember MAE (ms)
Widened original PP-MLP — ST[EVT, MLP]778,8973×10−43\times10^{-4}11.004 ± 0.106
TT — ST[EVT, EVT]778,89710−410^{-4}11.089 ± 0.093
Widened PathTransformer — no learned graph encoder793,72910−410^{-4}11.159 ± 0.077

Separately, an additional five-seed TT control at 3×10−43\times10^{-4} achieved 11.011 ± 0.145 ms. It lowered September MAE relative to 10−410^{-4} on four of five paired seeds and outperformed widened PP-MLP on three of five paired seeds.

Extended training. For this separate duration control, we evaluated the three models up to 24,000 updates on the same five seeds, without additional learning-rate tuning. TT uses its historical constant learning rate of 3 × 10⁻⁴; widened PP-MLP and PathTransformer retain their selected rates of 3 × 10⁻⁴ and 10⁻⁴, respectively. Checkpoints are selected on August within each training budget. September MAE (ms), mean ± sample SD:

Model8,000 updates24,000 updates
TT — historical LR 3 × 10⁻⁴11.011 ± 0.14510.396 ± 0.052
Widened original PP-MLP11.004 ± 0.10610.460 ± 0.068
Widened PathTransformer11.159 ± 0.07710.947 ± 0.073
All three models improve on every seed. At 24,000 updates, TT and widened PP-MLP outperform PathTransformer on all five paired seeds, and TT outperforms PP-MLP on four of five. These comparisons match update budgets, not wall-clock computation, and do not establish convergence.
AuthorsOpenReview ↗

Q1 & Q6 — Edge Transformers and nuisance node features

Q1 and Q6: We believe this behavior is due to instability of ET in the presence of noisy confounding features. Indeed, Task 2 predicts alternative-route counts from graph and path structure and does not require node information. The dataset, constructed for both Task 1 and Task 2, includes purely noisy node features to test robustness, as with the nuisance features added for Task 1. To investigate this, we ran an additional experiment (see below). We evaluated the ET baselines with all node features set to zero. Under this intervention, they achieve excellent predictions – even better than EVT when evaluated under the same intervention. This demonstrates a strong sensitivity to task-irrelevant node features in the ET baselines control under this protocol. The result shows that EVT is then more robust to the irrelevant node features than ET in this experiment. One possible explanation is that EVT processes node states through self-attention, in parallel with triangular attention on pair states, before mixing the two streams whereas ET incorporates node features into pair states without a separate node-processing stream.

We additionally tested whether the poor ET results could be resolved by model-specific learning-rate selection. In the common three-rate, three-tuning-seed search reported in Q5, all four ET variants remained near zero on the original inputs. Thus, the particular learning rate used in the main comparison does not explain their poor performance within the tested grid.

We have added these experiments and discussion in the revised version.

Details of the new experiment: Pair features, graph topology, paths, labels and target normalization remained unchanged. Within each model, the two conditions used paired initializations and minibatches.

All models received 2,000 updates with the same initial learning rate of 3 × 10⁻⁴, followed by the same warm-up and cosine-decay schedule. Checkpoints were selected by validation MSE and evaluated on 256 held-out graphs.

Task 2 test R², mean ± sample SD over five paired seeds:

Submitted modelOriginal node featuresNode features set to zero
ET-chain−0.0142 ± 0.01130.8996 ± 0.0127
ET-mix−0.0101 ± 0.00810.8790 ± 0.0123
EVT-Transformer0.5272 ± 0.09760.8524 ± 0.0341
TT = ST[EVT, EVT]0.5893 ± 0.10180.8377 ± 0.1030
PP-MLP= ST[EVT, MLP]0.5254 ± 0.09100.9215 ± 0.0370
ET-MLP= ST[ET, MLP]−0.0065 ± 0.00690.9458 ± 0.0583

ET-chain and ET-mix retain their submitted Transformer path processors. PP-MLP and ET-MLP retain their submitted pair-MLP, row-mean and concatenating vertex-MLP readers. Zeroing the node features improves test R² on all five seeds for every model except TT, which improves on four of five.

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

This paper studies prediction on ordered paths within a graph, where the graph representation can be computed once and reused across queries. It proposes the Edge Vertex Transformer (EVT), characterizes what information remains available after selecting cached path representations, and compares selection, joint cache reading, and encoding with the path marked beforehand. Experiments use synthetic graphs, Internet routing measurements, and a biological benchmark of splicing combinations, with different path processors performing best across tasks.

Critical strengths
  • The distinction between the three ways of accessing graph information is useful. In particular, the result that selection and joint reading have equal expressivity for paths of length at most two, but differ at length three, explains a specific limitation of selecting cached states.
  • The synthetic experiments include several useful controls, such as changing the graph and path operators separately, increasing training duration, and comparing against a small local MLP. The paper also reports the biological results where the simpler models outperform TT.
  • The caching experiments compare the same trained weights with and without reuse, include cache construction, and check that predictions agree. This makes the reported inference savings convincing under the tested settings.
Critical weaknesses
  • The architectural novelty seems limited relative to the theoretical contribution. Edge Transformers already use triangular composition and have 2-FWL expressivity (Müller et al., 2024), while approximation from distinguishability builds on Azizian and Lelarge (2021). These connections are discussed, but SUREL and SUREL+ (2023), which reuse sampled graph structure across queries, are missing. Their setup differs, but the paper should explain what is new about reuse here. The ordered selection theorem and access hierarchy appear to be the main advances.
  • Tables 4 and E.1: TT improves over PathTransformer by 0.261 ms, but uses 778.9k parameters against 101.2k. Also, the selection reader trained on frozen PP-MLP representations reaches 10.956 ms, close to TT’s 10.940 ms, although their training protocols differ. This leaves unclear how much improvement comes from triangular processing itself. These readers should be compared with the same training and selection budget. Cached TT also takes 1.896 ms/path against PP-MLP’s 0.647, so the accuracy improvement comes with a substantial inference cost.
  • Remark 3 shows that triangular path attention is unnecessary for the limiting expressivity result. However, PP-MLP changes several components, and TD replaces triangular attention with dense attention. A more direct experiment would disable only triangular path attention while keeping the other components, and compare performance across widths and training budgets using the same frozen graph representations.
  • The synthetic tasks should be interpreted narrowly. Task 1 explicitly asks for products of consecutive edge weights, which suits the proposed operator. Task 2 uses small generated graphs and exact path-counting labels. These are useful controlled tests, but Atlas carries most of the evidence for practical benefit. The certified experiment also repeats the same two label-specific joint histograms across its test graphs.
Questions for authors

The paper writing is at many places too dense and difficult to follow because it introduces several technical terms before explaining what they mean for the problem. For instance, the abstract mentions an “aligned graph-to-path construction,” a “path-indexed 2-FWL profile,” and “compatible continuous prediction” without giving the reader enough context. It then introduces selection, joint cache reading, and path-marked encoding, but the difference between these is central to understanding the contribution. The paper would benefit from having a non AI writing that explains the story in a better pedagogical flow.

5 comments
AuthorsOpenReview ↗

W1 & Q1 — Architectural contributions and clearer exposition

W1: We thank the reviewer for this feedback. We would like to clarify that our architectural contributions are substantial, work hand in hand with the theoretical one, and have been extensively benchmarked. The EVT component provides configurable interactions between vertex and pair states and our two-stage framework is modular. This architecture makes an exact characterization of expressivity and approximation possible. Below, we detail what is new relative to Edge Transformers, to the approximation framework of Azizian and Lelarge (2021), and to reuse in SUREL and SUREL+. For clarity, we now call our two-stage framework StrikeTwice and denote it as ST[GraphEncoder, PathProcessor], making explicit that both stages can be chosen independently.

Edge Transformers already use triangular composition and have 2-FWL expressivity (Müller et al., 2024),

While we agree that Edge Transformers already use triangular composition and have 2-FWL distinguishing power (Müller et al., 2024), EVT differs architecturally in two ways: it adds explicit vertex states that exchange information with pair states, and it applies triangular attention in all four orientations rather than one. Extending the 2-FWL result to EVT is therefore nontrivial, since the proof must account for these vertex–pair exchanges. Moreover, Müller et al.’s result characterizes distinguishability at a fixed graph size, whereas we additionally characterize which continuous targets EVT and ST[EVT, EVT] can uniformly approximate on compact domains, with a single parameter set for all graph sizes n≤Nn\leq N and, for StrikeTwice, all path lengths k≤Kk\leq K, for any fixed bounds NN and KK.

while approximation from distinguishability builds on Azizian and Lelarge (2021).

We agree that our approximation argument builds on the framework of Azizian and Lelarge (2021). Applying it to EVT and StrikeTwice, however, requires an architecture-specific proof of closure under concatenation: we show that a single wider network can reproduce the outputs of several networks side by side. In the revision, we further prove that this construction can be uniformly approximated on compact sets by networks with pre-LayerNorm and GELU, and hence, the guarantee holds for the architecture as implemented (Appendix H.10).

These connections are discussed, but SUREL and SUREL+ (2023), which reuse sampled graph structure across queries, are missing.

Their setup differs, but the paper should explain what is new about reuse here. The ordered selection theorem and access hierarchy appear to be the main advances. SUREL and SUREL+ provide precedents for reusing graph information across queries, and we have added them to the related work, together with a discussion of what is new about reuse here. Their setting differs in two ways. First, these methods do not address the same prediction tasks as ours, since their queries are vertex pairs or sets, whereas ours are ordered paths with repeated visits. Second, they reuse sampled graph structure, whereas StrikeTwice reuses learned vertex and pair states computed by a full-graph encoder, selected in path order. Neither SUREL nor SUREL+ provides an expressivity or uniform-approximation theorem for its reuse interface, whereas we establish both for our ordered-selection interface. We agree with the reviewer that the ordered-selection theorem and the hierarchy between marking, combination, and ordered selection are central contributions, and the revision states this explicitly.

Q1 : The paper writing is at many places too dense and difficult to follow [...] The paper would benefit from having a non AI writing that explains the story in a better pedagogical flow.

We agree that the abstract introduced technical terminology too early. We have rewritten it to begin with the prediction problem and cache reuse, then describe StrikeTwice through its two stages and ordered selection of vertex and pair states. We have removed the expressions “aligned graph-to-path construction”, “path-indexed 2-FWL profile”, and “compatible continuous prediction”. We also describe the access choices through concrete operations: selecting cached states, jointly reading graph-to-path relations, and marking path positions before encoding. We have also rewritten or added certain sentences in the paper to make it more pedagogic.

AuthorsOpenReview ↗

W2 — Atlas: matched budgets, extended training and computational cost

W2: We have performed the suggested comparison with matched training and tuning budgets and approximately matched parameter counts (details below). At 8,000 updates, TT = ST[EVT, EVT] keeps a modest advantage over widened PathTransformer, which has no learned graph encoder, while the widened PP-MLP = ST[EVT, MLP] is slightly better than TT. We also report a separate duration control, keeping each model’s learning rate fixed between 8,000 and 24,000 updates. For TT, this control uses its historical rate of 3×10−43\times10^{-4}, which yielded lower August validation error than the screen-selected rate on all five seeds at 8,000 updates. Widened PP-MLP and PathTransformer retain their screen-selected rates. In this control, TT achieves lower mean error than both at 24,000 updates. In this end-to-end setting, TT and PP-MLP each train their own graph encoder, so the comparison does not isolate the path processor: a jointly trained encoder may compensate for a simpler path processor. The controlled ablation in W3, shows that triangular path attention does improve the path processor at finite widths and training budgets.

The submitted measurements show that original PP-MLP is faster than TT (0.647 versus 1.896 ms/path), but also smaller (448,653 versus 778,897 parameters). In our new parameter-matched inference comparison, widened PP-MLP remains faster: 6.047 versus 8.015 ms/path, corresponding to approximately 25% less inference time, including initial cache construction.

More experiment details: Widened PP-MLP and TT each have 778,897 parameters; widened PathTransformer has 793,729, approximately 1.9% more. Each model received the same learning-rate screen over 10−4,3×10−4,10−3\\{10^{-4},3\times10^{-4},10^{-3}\\}, with 2,000 updates per rate at seed 0, followed by five evaluation seeds trained for 8,000 updates. Learning rates and checkpoints were selected on the same 4,096-query August cohort.

September MAE in milliseconds (lower is better), mean ± sample SD over five evaluation seeds.

ModelParametersSelected learning rateSeptember MAE (ms)
Widened original PP-MLP — ST[EVT, MLP]778,8973×10−43\times10^{-4}11.004 ± 0.106
TT — ST[EVT, EVT]778,89710−410^{-4}11.089 ± 0.093
Widened PathTransformer — no learned graph encoder793,72910−410^{-4}11.159 ± 0.077

Separately, an additional five-seed TT control at 3×10−43\times10^{-4} achieved 11.011 ± 0.145 ms. At 8,000 updates, TT’s historical rate also yielded lower August validation error than the screen-selected rate on all five seeds. It lowered September MAE relative to 10−410^{-4} on four of five paired seeds and outperformed widened PP-MLP on three of five paired seeds.

Extended training. We also evaluated the three models up to 24,000 updates on the same five seeds. TT uses its historical constant learning rate of 3×10−43\times10^{-4}; widened PP-MLP and PathTransformer retain their selected rates of 3×10−43\times10^{-4} and 10−410^{-4}, respectively. Checkpoints are selected on August within each training budget.

September MAE (ms), mean ± sample SD:

Model8,000 updates24,000 updates
TT — historical LR 3×10−43\times10^{-4}11.011 ± 0.14510.396 ± 0.052
Widened original PP-MLP11.004 ± 0.10610.460 ± 0.068
Widened PathTransformer11.159 ± 0.07710.947 ± 0.073

All three models improve on every seed. At 24,000 updates, TT and widened PP-MLP outperform PathTransformer on all five paired seeds, and TT outperforms PP-MLP on four of five. These comparisons match update budgets.

Inference cost. The widened PP-MLP and TT have 778,897 parameters and use the same A100 protocol, with 32 paths per graph and physical batches of eight. These are medians across nine graphs, with seven synchronized repetitions and one frozen checkpoint per model. The submitted approximately 3× ratio used a smaller PP-MLP on TPU hardware, whereas the new 1.33× ratio is measured on A100. TT therefore retains an additional inference cost.

AuthorsOpenReview ↗

W3 — Triangular-attention ablations on frozen graph encodings

W3: We ran the requested ablations on Task 1 and Atlas to test whether triangular attention helps the path processor learn at finite widths and training budgets. We compare three path processors on the same frozen graph encoder: the full EVT, EVT without triangular attention (EVT-), and EVT- with wider feed-forward layers to approximately match the parameter count. All three receive identical graph representations, paired minibatches, and the same learning-rate search budget.

On Task 1, the full EVT outperformed both controls in every setting and on every paired seed, for both widths and training budgets, and for frozen encoders taken from both TT = ST[EVT, EVT] and PP-MLP = ST[EVT, MLP]. For example, with the frozen TT encoder, a width-64 path processor and 3,200 updates, test R2 was 0.981 versus 0.872 without triangular attention and 0.863 with wider feed-forward layers. On Atlas-RIPE, with one frozen TT encoder, the full EVT achieved lower mean MAE in all four settings, with the clearest margins at 8,000 updates; at 2,000 updates and width 32, the differences are within seed variability.

Thus, although triangular path attention is not needed for the limiting expressivity result, it improves what the path processor learns at finite width and training budget. We have added this ablation and its discussion to the revision.

More details for new Task1 experiment: Full EVT outperformed both controls on every paired seed at both widths and training budgets, including on the PP-MLP cache learned with an MLP path processor. At 3,200 updates, its mean gain over the FFN-compensated control was approximately 0.056 at both widths on the PP-MLP cache, and 0.104 and 0.118 at widths 32 and 64 on the TT cache. Task 1 test R² (higher is better), mean ± sample SD over three paired path-processor seeds. Checkpoints are selected by validation loss within each training budget.

Frozen encoder sourcePath-processor widthUpdatesFull EVTEVT-EVT- + wider FFNs
PP-MLP328000.8935 ± 0.00580.8425 ± 0.01150.8374 ± 0.0128
PP-MLP323,2000.9065 ± 0.00910.8493 ± 0.00220.8507 ± 0.0011
PP-MLP648000.8945 ± 0.01200.8417 ± 0.01270.8404 ± 0.0111
PP-MLP643,2000.9018 ± 0.00670.8556 ± 0.00320.8459 ± 0.0043
TT328000.9683 ± 0.01270.8781 ± 0.00910.8605 ± 0.0244
TT323,2000.9775 ± 0.00830.8659 ± 0.00430.8732 ± 0.0120
TT648000.9705 ± 0.00570.8646 ± 0.00320.8557 ± 0.0093
TT643,2000.9805 ± 0.00210.8718 ± 0.00270.8629 ± 0.0022
Each source uses one refitted, frozen graph encoder. The three seeds measure path-processor variability conditional on that encoder.

More details for new Atlas experiment: On Atlas, we froze one TT-trained graph encoder and trained fresh path processors on identical cached representations, comparing full EVT, removal of triangular path attention (EVT-), and EVT- with wider FFNs to approximately match the full processor’s output-connected parameter count. Full EVT achieved better results at both tested widths and both evaluated training horizons. At 8,000 updates, its MAE (lower is better) was 10.678 versus 10.886 ms without triangular attention at width 32, and 10.610 versus 10.684 ms at width 64. The advantage remained against the FFN-compensated controls, which achieved 10.750 and 10.728 ms, respectively. These are means over three path-processor seeds, conditional on one frozen encoder.

Atlas September MAE (ms; lower is better), mean ± sample SD over three paired path-processor seeds. All processors receive identical representations from one frozen TT-trained graph encoder. Checkpoints are selected on August.

Path-processor widthUpdatesFull EVTEVT-EVT- + wider FFNs
322,00011.233 ± 0.05211.258 ± 0.03911.249 ± 0.025
328,00010.678 ± 0.08210.886 ± 0.04710.750 ± 0.063
642,00011.187 ± 0.01111.237 ± 0.02611.235 ± 0.012
648,00010.610 ± 0.07010.684 ± 0.07110.728 ± 0.027

Wider FFNs approximately match the full processor’s output-connected parameter count. The 2,000-update results use learning rates selected by the 8,000-update screen. These comparisons are conditional on one pretrained encoder.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.