acceptodds
Under review as a conference paper at ICLR 2027

MagResPE: Forest-Normalized Magnitude Residual Positional Encoding for Graph Transformers

Abstract

Graph Transformers rely on positional encodings (PEs) to expose graph structure to attention, yet practical positional encodings provide only a finite structural interface. We introduce MagResPE, a deterministic multi-scale node PE derived from graph magnitude by measuring the ridge-regularized residual from an exact forest reference. This forest normalization gives every forest an explicit zero baseline while retaining non-forest structure across metric scales. We derive an all-orders BFS-shell expansion of the forest-prediction defect, whose coefficients are determined by same-shell edges and redundant shortest-path parents. Its second-order coefficient captures triangles and redundant two-hop geodesics, and the expansion yields a girth-controlled first nonzero order for the positive-ridge residual. We further prove a regular-subdivision separation: for arbitrarily prescribed finite horizons, connected graphs can share identical RRWP rooted row-profile multisets while exhibiting distinct small-q MagResPE onset orders. An exact cycle folding law further gives the sharp RRWP separation horizon. Empirically, on ZINC-12K, augmenting RRWP with MagResPE reduces test MAE from 0.0638 ± 0.0036 to 0.0600 ± 0.0021. Matched formulation controls and a SignNet spectral-node control do not reproduce this gain, indicating that it is not explained by raw magnitude or by the tested spectral-node augmentation. Using the same fixed MagResPE configuration, the hybrid also improves mean RRWP performance on Peptides-struct and PascalVOC-SP. Standalone replacement is not consistently competitive, supporting MagResPE as a complementary rather than universal PE. Together, these results suggest that forest-normalized graph magnitude is a promising basis for complementary positional encoding in Graph Transformers.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
graph transformers, positional encoding, structural encoding, graph magnitude, graph representation learning, shortest-path distance, graph theory

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_j79pOpenReview ↗
Rating
3
Confidence
3
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

MAGRESPE proposes a multi-scale node positional encoding for Graph Transformers derived from graph magnitude. The central idea is to use an exact forest reference as a structural baseline and encode the residual deviation of a graph from this baseline. Since forests map exactly to zero, the resulting representation is intended to capture non-forest structural information, such as cycles and redundant shortest paths, across multiple metric scales.

Critical strengths

Strengths.

S1. The paper proposes a new node positional encoding for graph transformers based on graph magnitude. On a forest, the magnitude weighting has an exact closed form. MagResPE uses it as a reference and encodes, for each node, how much the actual graph deviates from it across several scales. Every forest maps to zero, so the encoding focuses on non-tree structure. To my knowledge, this is the first use of graph magnitude as a node positional encoding.

S2. The theory explains what this residual encodes. The paper derives an all-order BFS-shell expansion of the forest-prediction defect. Its second-order coefficient captures triangles and redundant two-hop geodesics, and the girth controls the first nonzero order. The paper also proves that MagResPE can separate graph families that finite-horizon RRWP summaries cannot, and the cycle folding law gives the exact RRWP horizon for C2mC_{2m} versus 2Cm2C_m. I checked the main results and found no errors.

S3. Empirically, adding MagResPE to RRWP in GRIT lowers the mean test MAE on ZINC from 0.0638 to 0.0600, with smaller mean gains on Peptides-struct and PascalVOC-SP. On two synthetic tasks, the hybrid reaches 100% and 99.17% accuracy, while RRWP alone stays at chance.

S4. The experimental design is careful. Ablations separate the effects of the forest reference, the onset normalization and the ridge correction. A Zero-info control checks the effect of the extra encoder branch, and parameter budgets are roughly matched. Preprocessing time and conditioning are also reported.

Critical weaknesses

W1. The empirical gains are small. With five seeds, none of the paper's sign tests is significant. Table 1 also leaves out published results with the same GRIT host that match or beat the hybrid, such as GRIT (Ma et al., 2023), GRIT-SPSE (Airale et al., 2025) and GRIT+MoSE (Bao et al., 2025). With these results included, the claims in Sec. 6.2 that the hybrid gives the lowest MAE do not hold. In addition, standalone MagResPE is worse than RRWP on all three benchmarks, so it only helps as an add-on to RRWP.

W2. It is unclear which part of the method drives the gain. In the ZINC ablation (Table 4), the hybrid without the q−2q^{-2} factor is no better than RRWP alone. DirectDefect, which skips the ridge solve, already gives about 74% of the gain. So most of the gain seems to come from the fixed q−2q^{-2} rescaling, not from the ridge-regularized magnitude correction. A control with raw magnitude and q−2q^{-2} is also missing.

W3. The theory does not explain the gains on real data. The paper states that its separation result holds only for a summary of RRWP (rooted row profiles), while GRIT uses the complete RRWP pair representation. On ZINC, the horizon h=20h = 20 also covers the diameter of almost all graphs, so MagResPE can be computed from the RRWP features GRIT already uses. Even so, the contributions state that MagResPE "provides complementary information to finite-horizon RRWP".

W4. Some controls are missing, and the method does not scale well. There is no simple global-distance control, such as decay centrality or a distance histogram, passed through the same encoder. RRWP with a longer horizon is not tested on Peptides-struct and PascalVOC-SP, whose average diameters exceed the horizon used. Finally, the solve stage costs O(Kn3)O(Kn^3) time and O(n2)O(n^2) memory, which makes the method hard to apply to large graphs.

Questions for authors

Check weakness section.

3 comments
AuthorsOpenReview ↗

Response to Reviewer j79p

Thank you for identifying the missing controls and for clarifying the distinction between the synthetic separation results and the claims on real data. We added the raw-magnitude rescaling control, same-encoder global-distance baselines, longer RRWP horizons, and ten paired ZINC seeds.

W1. Effect size, published results, and standalone performance

Across ten paired ZINC seeds, adding MagResPE to the same GRIT+RRWP configuration reduces mean test MAE from 0.0625 to 0.0596. The paired mean reduction is 0.0029 (95% bootstrap CI [0.0009, 0.0052], paired tt-test p=0.0318p=0.0318). The hybrid wins on seven seeds, with exact sign-test p=0.3438p=0.3438 (Tables 13–14). At width 64, the gain also appears in all five paired runs (Table 12).

Molecular benchmark referenceZINC-12K MAE ↓Peptides-struct MAE ↓
Published GRIT+RRWP0.059 ± 0.0020.2460 ± 0.0012
Published GRIT+SPSE0.059 ± 0.0010.2449 ± 0.0018
Published GRIT+MoSE0.056 ± 0.001—
Our five-seed RRWP+MagResPE0.060 ± 0.0020.2457 ± 0.0022

Table 1 now includes these published results, and §6.2 confines the lowest-MAE claim to our matched runs. Standalone MagResPE trails RRWP on all three benchmarks. Our main empirical result is the effect of supplying MagResPE alongside the existing RRWP input.

W2. What drives the gain

The new RawNormalized arm applies the same q−2q^{-2} factor to the raw ridge weighting. This completes the forest-reference × onset-normalization comparison (Table 4).

ZINC-12K input added to RRWPWithout q−2q^{-2}With q−2q^{-2}
Raw ridge weighting0.06480.0652
Forest-centered ridge residual0.06340.0600

Rescaling the raw weighting slightly worsens mean test MAE. Rescaling the forest-centered residual improves it by 0.0034. At fixed q−2q^{-2}, introducing the forest reference improves mean test MAE by 0.0052, with improvement on all five pairs. These results support the combination of forest centering and onset normalization.

DirectDefect retains both choices and recovers most of the gain. Across ten paired seeds, the ridge solve provides an additional mean test reduction of 0.0012 (7/10 wins, CI [−0.0010, 0.0035]) and validation reduction of 0.0065 (CI [0.0043, 0.0086]). The interval for the test comparison leaves the solve’s incremental predictive benefit uncertain (Table 14).

W3. What the theorem establishes and what the real-data experiment measures

Theorem 2 concerns rooted RRWP row-profile multisets. The full pairwise RRWP tensor includes the one-step matrix PP, whose support determines adjacency and thus the shortest-path distances used by MagResPE. At h=20h=20, the stored walk powers already cover the diameter of 99.90% of ZINC graphs (Appendix C.6). We revised the contribution statement to describe the empirical benefit of providing a structural bias through the node encoder. The real-data experiments measure that benefit in the matched model.

W4. Global-distance controls, longer horizons, and scalability

We used the same RRWP-equipped GRIT, auxiliary encoder, and five aligned seeds for the new ZINC controls. SPHist counts nodes at each shortest-path distance, and DegreeHist also includes the sum of their degrees at each distance. They address the missing global-distance control on ZINC. MagResPE beats both controls on all five seeds. Both paired bootstrap CIs favor MagResPE, while both Holm-adjusted pp-values exceed 0.05 (Tables 16–17).

ZINC-12K configurationTest MAE ↓
RRWP0.0638
RRWP + SPHist0.0676
RRWP + DegreeHist0.0706
RRWP + MagResPE0.0600

We extended RRWP from h=23h=23 for both models over five paired seeds on Peptides-struct and PascalVOC-SP (Table 15). Both mean gains are positive, with CIs including zero. On Peptides-struct, the longer horizon increases coverage and raises mean MAE for both models relative to h=23h=23.

DatasetLonger hhMean node-pair coverageRRWP → hybridGain [95% paired bootstrap CI]
Peptides-struct6366.73% → 96.81%0.2545 → 0.2516 MAE0.0029 [−0.0102, 0.0139]
PascalVOC-SP3199.34% → 99.99%0.4029 → 0.4111 macro-F10.0082 [−0.0051, 0.0247]

In the single-thread CPU profile, MagResPE alone takes 47% less preprocessing time on ZINC (4.1 vs. 7.7 ms) and 37% less on Peptides-struct (10.4 vs. 16.5 ms) than RRWP at h=20h=20. At a median of 2,973 nodes, it uses 80% less incremental peak CPU memory (481 vs. 2,413 MB) and takes about 10% longer (8.85 vs. 8.03 s). The histogram controls take 1.16–1.21 s and use 206 MB (Tables 22–23). The hybrid computes both encodings and adds about 2% to cached ZINC epoch time, with comparable GPU memory (Table 20). On PascalVOC-SP, 16 workers reduce reusable cache build-and-load time from 18.1 to 3.4 minutes (Table 25). The exact solve still requires O(Kn3)O(Kn^3) time and O(n2)O(n^2) working memory.

Reviewer_j79pOpenReview ↗

Maintain my positive score

Thank you for the detailed responses, which have addressed my concerns. I will maintain my positive rating.

Thank you for taking the time to review our responses. We’re glad the revision addressed your concerns, and we appreciate your suggestions for improving the paper.

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

The paper proposes MagResPE, a node positional encoding for graph transformers built from graph magnitude. The authors select scales q \in (0,1), and form the kernel q raised to the shortest-path distance between node pairs. The method further evaluate a closed-form magnitude weighting that is exact on forests and depends only on node degree. They measure how far this forest weighting departs from solving the magnitude equations on the given graph and compute a ridge-regularized correction for each node. The corrections are rescaled by q squared, passed through a signed logarithm and concatenated over eight scales to form the node encoding, which is added to GRIT alongside its existing random-walk encoding (RRWP). Empirically, adding MagResPE to RRWP lowers ZINC-12K test MAE from 0.0638 to 0.0600 relative to the authors' retrained baseline and gives small mean gains on Peptides-struct and PascalVOC-SP. On synthetic tasks built around their separation results, the hybrid reaches near-perfect accuracy and truncated RRWP stays at chance.

Critical strengths
  1. The authors study an important aspect of position encodings for graph transformers
  2. The results on benchmarks are competitive and the authors position MagResPE as a complement to existing PEs like RRWP
Critical weaknesses

W1. Limited novelty and overlap with distance-based encodings: Lemma 8 shows the forest defect at node v is a generating polynomial of BFS-shell statistics. It depends only on the multiset of pairs (distance from v, degree), so it is a degree-weighted shortest-path distance histogram. Distance encodings (Li et al., 2020) and the generalized distance WL framework with Graphormer-GD (Zhang et al., 2023) already cover features of this kind, and neither is cited. The only part specific to magnitude is the ridge solve. Its value is not supported by the paper's own ablation: DirectDefect skips the solve and reaches 0.0610 MAE on ZINC against 0.0600 for the full method, with a bootstrap interval of [−0.0024, 0.0044] that contains zero.

W2. Prior work on magnitude is not credited: Magnitude weighting vectors have been used as per-point features before (Bunch et al., 2021). Magnitude has also been applied to diversity of graph embeddings (Limbeck et al., 2024) and to generalization in neural networks (Andreeva et al., 2023). Bunch et al. also note that the weighting vector may fail to exist for shortest-path metrics on graphs, which is the issue the ridge term addresses here. Proposition 4 (the forest inverse and weighting) appears closely related to Leinster's (2019) results on the magnitude of trees and forests, and the paper should state what in it is new.

W3. The separation from RRWP comes from truncation: Theorem 2 and the cycle-family results compare a global encoding against RRWP cut off at a horizon h chosen below half the girth. Any encoding that depends only on radius-h neighbourhoods fails on such graphs, since these neighbourhoods are identical trees when the girth exceeds 2h. The result therefore says little about random walks compared with magnitude. The following examples illustrate this.

On the subdivision pair from Corollary 13 with L = 2 (girth-5 graph X14 against the Heawood graph, 35 nodes, diameters 8 and 6), the plain per-node shortest-path distance histograms already differ. RRWP row-profile multisets also differ at horizon h = 5 (powers up to P⁵, i.e. ksteps = 6 in the paper's convention), a horizon below the diameter of 8. For C₂ₘ against 2Cₘ, every node in 2Cₘ has m reachable nodes where C₂ₘ has 2m, so any shortest-path encoding separates the pair trivially. The synthetic benchmarks in Section 6.3 inherit this issue and include no baseline built on shortest-path or resistance distance.

W4. The encoding can be weaker than RRWP: The encoding is a function of the shortest-path distance matrix alone, and Proposition 18 concedes that regular graphs with identical per-node distance histograms receive identical encodings. A concrete case: on the Dodecahedron and Desargues graphs, we obtain identical MagResPE residuals at all eight scales of the paper's bank (differences at most 1e-11). These graphs have girths 5 and 6. RRWP separates them at horizon 5, and Ma et al. (2023) use this same pair to show RRWP is strictly more expressive than shortest-path distance under GD-WL. The paper also does not place MagResPE in the WL hierarchy.

W5. The theory does not explain the behavior in practice: Theorem 2 separates graphs only for sufficiently small q. On the regular-subdivision benchmark the leading orders are q²³ and q²⁷, and Table 12 shows 0 of 14,400 pairs resolved for q ≤ 0.21. The separation that is observed comes from q ≥ 0.34, which no theorem covers for the regular-subdivision family.

W6. Weak baselines and missing published results:

The retrained GRIT baseline is weaker than the published one. It reaches 0.0638 on ZINC, while Ma et al. (2023) report 0.059 ± 0.002 under a ~500K parameter budget. The configuration here uses 364K parameters and width 56.

On ZINC the hybrid (0.0600) does not improve on published GRIT (0.059 ± 0.002) or GRIT with SPSE (0.059 ± 0.001, Airale et al., 2025). On Peptides-struct it (0.2457) is within one standard deviation of published GRIT (0.2460 ± 0.0012) and behind GRIT with SPSE (0.2449 ± 0.0018, Airale et al., 2025).

PascalVOC-SP baselines are outdated. Table 2 uses the original LRGB numbers, which predate the hyperparameter and feature-normalization reassessment by Tönshoff et al. (2023). Published results from that point on, obtained under different tuning and normalization settings, are well above the hybrid's 0.4070: GraphGPS reaches 0.4538 (Grötschla et al., 2024), CRaWl 0.4588 (Tönshoff et al., 2023), and NeuralWalker 0.4912 (Chen et al., 2025).

Cycle-aware methods are absent. Methods aimed at the same structural signal are not compared: GSN (Bouritsas et al., 2023) and CycleNet (Yan et al., 2024).

W7. Cost and numerical stability: Preprocessing scales as O(Kn³) with dense O(n²) memory and takes about 18 minutes on PascalVOC-SP on a single CPU core. The recommended hybrid trains slightly slower than RRWP with similar memory (Table 13). The lighter footprint of standalone MagResPE comes from removing GRIT's pairwise tensor. Node-only encodings such as RWSE or LapPE would share that property, and neither is included as a standalone baseline. At q = 0.95 the condition number of the regularized normal matrix has median 3.2 × 10⁵ and maximum 6.4 × 10⁵ on ZINC graphs (Appendix E.4), and the paper gives no analysis of how the encoding behaves under perturbations of the graph.

References

Airale, L., Longa, A., Rigon, M., Passerini, A., and Passerone, R. Simple Path Structural Encoding for Graph Transformers. In Proceedings of the 42nd International Conference on Machine Learning (ICML), PMLR 267:857–873, 2025.

Andreeva, R., Limbeck, K., Rieck, B., and Sarkar, R. Metric Space Magnitude and Generalisation in Neural Networks. In Proceedings of the 2nd Annual Workshop on Topology, Algebra, and Geometry in Machine Learning (TAG-ML), PMLR 221:242–253, 2023.

Bouritsas, G., Frasca, F., Zafeiriou, S., and Bronstein, M. M. Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting. IEEE Transactions on Pattern Analysis and Machine Intelligence, 45, 2023.

Bunch, E., Kline, J., Dickinson, D., Bhat, S., and Fung, G. Weighting Vectors for Machine Learning: Numerical Harmonic Analysis Applied to Boundary Detection. arXiv:2106.00827, 2021.

Chen, D., Schulz, T. H., and Borgwardt, K. Learning Long Range Dependencies on Graphs via Random Walks. In International Conference on Learning Representations (ICLR), 2025.

Grötschla, F., Xie, J., and Wattenhofer, R. Benchmarking Positional Encodings for GNNs and Graph Transformers. arXiv:2411.12732, 2024.

Leinster, T. The Magnitude of a Graph. Mathematical Proceedings of the Cambridge Philosophical Society, 166:247–264, 2019.

Li, P., Wang, Y., Wang, H., and Leskovec, J. Distance Encoding: Design Provably More Powerful Neural Networks for Graph Representation Learning. In Advances in Neural Information Processing Systems (NeurIPS), 2020.

Limbeck, K., Andreeva, R., Sarkar, R., and Rieck, B. Metric Space Magnitude for Evaluating the Diversity of Latent Representations. In Advances in Neural Information Processing Systems 37 (NeurIPS), 2024.

Ma, L., Lin, C., Lim, D., Romero-Soriano, A., Dokania, P. K., Coates, M., Torr, P. H. S., and Lim, S.-N. Graph Inductive Biases in Transformers without Message Passing. In Proceedings of the 40th International Conference on Machine Learning (ICML), PMLR 202:23321–23337, 2023.

Tönshoff, J., Ritzert, M., Rosenbluth, E., and Grohe, M. Where Did the Gap Go? Reassessing the Long-Range Graph Benchmark. Transactions on Machine Learning Research (TMLR), 2023.

Yan, Z., Ma, T., Gao, L., Tang, Z., Chen, C., and Wang, Y. Cycle Invariant Positional Encoding for Graph Representation Learning. In Proceedings of the Second Learning on Graphs Conference (LoG), PMLR 231, 2024.

Zhang, B., Luo, S., Wang, L., and He, D. Rethinking the Expressive Power of GNNs via Graph Biconnectivity. In International Conference on Learning Representations (ICLR), 2023.

Questions for authors

Please refer weakness section above

4 comments
AuthorsOpenReview ↗

Response to Reviewer ZeJv - Part 1

Thank you for the concrete examples and baseline suggestions. We added same-encoder distance controls, an exact example separating the ridge residual from distance-shell signatures, an expressivity bound, and a finite-precision analysis at the scales used in training.

W1–W2. Relationship to distance encodings and prior magnitude work

We agree that the complete ordinary and degree-weighted BFS shells determine the forest defect and thus DirectDefect. Sections 2.1–2.2 now discuss Li et al.’s distance encodings and Zhang et al.’s generalized distance WL and Graphormer-GD. The shell statistics determine the forest defect but not necessarily the ridge-corrected residual. Proposition 15 and Appendix D.5 supply a seven-node counterexample to equality of unordered shell-signature multisets, while also showing that shortest-path GD-WL is strictly more discriminating than MagResPE signatures.

Matched ZINC-12K configurationFive-seed test MAE ↓
RRWP0.0638 ± 0.0036
RRWP + SPHist0.0676 ± 0.0041
RRWP + DegreeHist0.0706 ± 0.0084
RRWP + DirectDefect0.0610 ± 0.0035
RRWP + MagResPE0.0600 ± 0.0021

DegreeHist supplies the shell statistics that determine DirectDefect, yet achieves a higher MAE under the matched setup (Table 16). This supports explicitly computing the forest defect. We agree that DirectDefect recovers most of the hybrid gain. The extended ablation isolates the additional contribution of the solve (Tables 13–14).

Ten paired ZINC seedsRRWP + DirectDefectRRWP + MagResPEMAE reduction [95% paired bootstrap CI]
Test0.06080.05960.0012 [−0.0010, 0.0035]
Validation0.07420.06770.0065 [0.0043, 0.0086]

The solve has a clearer validation advantage, while its incremental held-out benefit remains uncertain. The exact seven-node witness establishes what the solve can distinguish independently of its predictive benefit.

Section 2.2 now credits Bunch et al. for prior use of pointwise magnitude weightings and for observing that graph shortest-path kernels need not admit a weighting. It also credits Andreeva et al. for work on neural-network generalization and Limbeck et al. for work on latent-representation diversity. Appendix A credits Leinster for classical forest magnitude and Bapat et al. for the tree inverse. Proposition 4 records its componentwise extension to forests and derives the row sums used as the reference. Our construction uses that forest-exact reference on general graphs and encodes the ridge-regularized correction to it.

W3–W4. Truncation, synthetic controls, and expressivity

Theorem 2 compares MagResPE with truncated rooted RRWP row-profile multisets. The full indexed RRWP tensor contains the one-step matrix and determines adjacency (§5.3, Appendix C.6). Appendix A.6 now includes your L=2L=2 example. The two 35-node subdivisions have diameters 8 and 6 and different shortest-path histogram multisets. Their RRWP row-profile multisets agree through h=4h=4 and first differ at h=5h=5, below both diameters. For C2mC_{2m} versus 2Cm2C_m, reachable component size alone separates the classes. The cycle theorem identifies the exact first horizon at which the RRWP row-profile multisets distinguish that pair.

Synthetic taskRRWP horizonRRWPRRWP + SPHistRRWP + MagResPE
Cycle pairs2050.0%97.5%100.0%
Cycle pairs3050.0%98.8%100.0%
Cycle pairs4050.0%100.0%100.0%
Regular subdivisions2050.0%98.3%99.2%

The matched SPHist results show that GRIT can exploit explicit global distance features in both tasks (Table 18), but shows limited gain on ZINC-12K (Tables 16–17). MagResPE provides this signal with eight fixed node channels, whereas the histogram width depends on the distance range and must be set from the data. Proposition 15 also places its deterministic signature multisets strictly below shortest-path GD-WL, which is strictly below complete RRWP-GD-WL. The Dodecahedron and Desargues graphs have identical MagResPE signatures, and RRWP distinguishes them at h=5h=5 (Appendix A.6).

W5. Exact separation and numerically usable scales

Corollary 13 extends exact separation to all but finitely many scales for each fixed subdivision pair. Table 19 measures whether that separation is numerically resolvable at the actual scales.

Tested scalesCross-class pairs resolved at each scale
0.05, 0.08, 0.13, 0.210 / 14,400
0.34, 0.52, 0.74, 0.9514,400 / 14,400

The leading residual orders are q23q^{23} and q27q^{27}, so both signals can be extremely small at low qq. The measured finite-scale margins identify which channels carry a resolvable signal on the subdivision benchmark (Appendix D.1).

AuthorsOpenReview ↗

Response to Reviewer ZeJv - Part 2

W6. Stronger published baselines and cycle-aware comparisons

Table 1 now includes the original published GRIT, GRIT+SPSE, GRIT+MoSE, GSN, and CWN+CycleNet. We agree that the original width-56 retrained GRIT baseline is weaker than published GRIT on ZINC. The revised table gives the published comparisons explicitly.

Molecular benchmark referenceZINC-12K MAE ↓Peptides-struct MAE ↓
Published GRIT+RRWP0.059 ± 0.0020.2460 ± 0.0012
Published GRIT+SPSE0.059 ± 0.0010.2449 ± 0.0018
Published GRIT+MoSE0.056 ± 0.001—
Published GSN (500K)0.101 ± 0.010—
Published CWN+CycleNet0.068—
Our RRWP+MagResPE0.0600 ± 0.00210.2457 ± 0.0022

We also reran the paired ZINC comparison at GRIT width 64. The mean MAE improves from 0.0626 to 0.0603, with wins on all five seeds (Table 12). The gain survives this width change, while the retrained baseline still does not reproduce the stronger published GRIT result (0.059 MAE, Table 1). Our cycle-based MoSE run achieves 0.0616 ± 0.0028 under our ZINC protocol. It removes the RRWP encoding and uses node encoding by homomorphism counts for the cycle-based patterns. GSN and CWN+CycleNet provide published benchmark context under their respective architectures.

For PascalVOC-SP, Appendix B.1 specifies that all our GRIT and GraphGPS variants use node and edge feature standardization based on the training split. Table 2 includes the stronger published results identified in the review.

PascalVOC-SP comparisonTest macro-F1 ↑
Published GraphGPS+ESLapPE0.4538 ± 0.0083
Published CRaWl0.4588 ± 0.0079
Published NeuralWalker0.4912 ± 0.0042
Our GRIT+RRWP → +MagResPE0.3968 → 0.4070
Our GraphGPS without a PE → +MagResPE0.4465 → 0.4535

The modern published PascalVOC results are included for context; our transfer test compares GraphGPS without PE against the same backbone with MagResPE. The paired comparisons estimate the benefit of adding MagResPE within a fixed backbone and training protocol. The published comparisons show where the resulting models sit relative to other methods. It is not a head-to-head comparison against GraphGPS+ESLapPE or NeuralWalker (Table 2).

W7. Preprocessing, node-only memory, and numerical stability

The revised cost profile distinguishes cached training from preprocessing. On ZINC, the cached hybrid takes 65.1 seconds per epoch versus 63.8 seconds for RRWP. Peak allocated GPU memory is 135.1 MB for standalone MagResPE, 137.3 MB for RWSE, and 135.1 MB for LapPE. This confirms that the lower footprint is shared by the node-only configurations (Table 20). The RWSE and LapPE comparison in that table measures runtime and memory.

Encoding on real graphs with median 2,973 nodesMedian preprocessing timeMedian incremental peak CPU memory
SPHist / DegreeHist1.16–1.21 s206 MB
DirectDefect2.07 s408 MB
LapPE5.59 s354 MB
RWSE7.24 s118 MB
RRWP8.03 s2,413 MB
MagResPE8.85 s481 MB

The exact solve costs O(Kn3)O(Kn^3) time and O(n2)O(n^2) working memory. The hybrid computes both encodings. On PascalVOC-SP, the full MagResPE cache takes 18.1 minutes serially and 3.4 minutes to build and load with 16 workers (Tables 22–25).

For fixed inputs, we compared the implemented float64 normal-equation solve with an independent augmented-SVD solve on 100 ZINC and 20 PascalVOC-SP graphs. At q=0.95q=0.95, the sampled PascalVOC-SP regularized systems reach a condition number of 9.60×1079.60\times10^7, and the maximum difference in stored float32 features is 1.2×10−71.2\times10^{-7} (Table 26). We separately measured feature drift over 990 ZINC and 200 PascalVOC-SP single-edge edits.

Dataset and editMagResPEDirectDefectSPHistDegreeHist
ZINC addition0.7830.8480.6940.698
ZINC deletion0.6910.9260.3920.388
PascalVOC-SP addition0.0900.1910.4770.476
PascalVOC-SP deletion0.0650.0440.0140.015

The entries are median-standardized feature drift (Table 27). MagResPE is less sensitive than DirectDefect in three of the four settings, while the comparison with histograms depends on the dataset and edit type. At a 10−610^{-6} feature-change threshold, the median fraction of nodes affected by each edge edit of MagResPE is 100% across the reported dataset/edit categories. The fixed-input solver agreement and the observed sensitivity to actual changes in topology address separate aspects of stability.

I appreciate the authors' response. I will review the contributions in light of the response in detail and for now I maintain my score.

Best

Thank you for taking the time to reassess the contribution in light of our response. In our rebuttal, we responded to each point raised in your review and added new experiments and clarifications to the manuscript. If any concern still weighs on your assessment, we would welcome the opportunity to clarify the relevant evidence or address any follow-up questions.

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

MagResPE forms a multiscale node signature from the mismatch between a shortest-path magnitude system and its exact forest reference. A learned encoder turns the signature into a node feature that is concatenated with the ordinary input embedding in GRIT; the model retains node-level and pairwise RRWP (Section 4.3, Eq. 9).

Critical strengths

The math is the strong part. Forests map to zero and the first nonzero order is tied to girth (Section 5.1); the second-order term counts triangles and redundant two-hop geodesics (Section 5.2). The synthetic experiments target those claims. Appendix C.5 also acknowledges that the RRWP horizon exceeds the diameter of 99.69% of ZINC graphs, so the separation theorem is not offered as the explanation for ZINC's improvement.

Critical weaknesses
  1. The separation theorem concerns truncated RRWP row-profile summaries, not full GRIT. Since MagResPE starts from all-pairs shortest-path information, a plain distance or cycle-count encoding in the same backbone seems like the obvious control. The encoding norm also tracks cycle rank (about 0.67–0.69 across ZINC splits; Appendix C.5).

  2. The gains are small. On ZINC, test MAE improves from 0.0638 to 0.0600 (Table 1). Paired bootstrap intervals favor the hybrid on ZINC and PascalVOC-SP, but not on Peptides-struct (Table 11). The exact sign tests don't reach 0.05, although with five pairs the smallest possible two-sided p-value is 0.0625. The SPSE comparison on ZINC is mixed too.

  3. Appendix C.2 shows forest subtraction helping on all five seeds, but the mean test-MAE difference is only about 0.0014. Validation MAE is 0.0725 with or without it, and scale normalization has a larger effect.

  4. Cached training overhead is small: roughly 63.8 vs. 65.1 seconds per ZINC epoch, with similar GPU memory (Table 13). Preprocessing is costlier, about 18 minutes for PascalVOC-SP on one CPU core (Table 14). Appendix E.3 benchmarks synthetic graphs up to 320 nodes, but does not establish costs on much larger real graphs. I would also like a preprocessing comparison with cheaper structural features. All downstream tests use GRIT.

Questions for authors
  1. Does MagResPE still help when GRIT receives matched shortest-path or cycle-count features?
  2. Do the results hold on another backbone or with more paired seeds? How does preprocessing compare with cheaper encodings on larger real graphs?
3 comments
AuthorsOpenReview ↗

Response to Reviewer NcDa

Thank you for the detailed review. We added matched shortest-path controls, extended the ZINC comparison to ten paired seeds, tested MagResPE in GraphGPS, and profiled preprocessing on larger real graphs. We also expanded the forest-subtraction ablation to test its interaction with onset normalization.

W1&Q1. Matched shortest-path controls and the scope of the theorem

We added SPHist, a plain shortest-path distance histogram, and DegreeHist, which combines ordinary and degree-weighted distance histograms. Each control uses the same RRWP-equipped GRIT, auxiliary node encoder, training protocol, and five aligned seeds as the MagResPE hybrid (Appendix C.5, Tables 16–17).

ZINC-12K configurationTest MAE ↓MagResPE wins against this configuration
RRWP0.0638 ± 0.00364/5
RRWP + SPHist0.0676 ± 0.00415/5
RRWP + DegreeHist0.0706 ± 0.00845/5
RRWP + MagResPE0.0600 ± 0.0021—

The hybrid’s mean paired reductions over SPHist and DegreeHist are 0.0075 and 0.0106 MAE. Both paired bootstrap intervals favor MagResPE, while the Holm-adjusted tests give p=0.108p=0.108 and p=0.270p=0.270. The results therefore provide consistent directional evidence against the two matched distance controls. Table 1 also reports a retrained cycle-based MoSE comparator at 0.0616 ± 0.0028.

We agree that Theorem 2 concerns truncated rooted RRWP row-profile multisets. The full pairwise tensor contains the one-step transition matrix, whose support determines the edges. Appendix C.6 now makes this explicit and reports that h=20h=20 covers the diameter of 99.90% of ZINC graphs. The ZINC experiment therefore tests the benefit of supplying MagResPE directly as a precomputed node feature alongside RRWP.

W2-W4&Q2. More paired seeds and a second backbone

Matched comparisonBaseline → with MagResPEMean paired gain [95% bootstrap CI]Wins
ZINC-12K, GRIT+RRWP, 10 seeds0.0625 → 0.0596 MAE0.0029 [0.0009, 0.0052]7/10
Peptides-struct, GRIT+RRWP, 5 seeds0.2479 → 0.2457 MAE0.0022 [−0.0009, 0.0061]3/5
PascalVOC-SP, GRIT+RRWP, 5 seeds0.3968 → 0.4070 macro-F10.0102 [0.0058, 0.0180]5/5
PascalVOC-SP, GraphGPS without a PE, 5 seeds0.4465 → 0.4535 macro-F10.0070 [0.0018, 0.0100]4/5

The ten-seed ZINC comparison provides evidence of a positive mean improvement (paired tt-test p=0.0318p=0.0318, exact sign-test p=0.3438p=0.3438). The comparison with retrained SPSE on ZINC remains mixed (3/5 wins, CI [−0.0017, 0.0036]). The GraphGPS result provides transfer evidence on one additional backbone and dataset, with a paired tt-test p=0.051p=0.051 (Tables 2 and 11–14).

W3. Forest subtraction with and without onset normalization

Without q−2q^{-2}, forest subtraction reduces test MAE by 0.0014, and both variants have 0.0725 validation MAE, as you observed. With q−2q^{-2} held fixed, the new RawNormalized control gives 0.0652 test MAE and the forest-centered variant gives 0.0600, with gains on all five seeds. Rescaling the raw weighting alone changes test MAE from 0.0648 to 0.0652. Against DirectDefect, the ridge solve reduces mean MAE across ten paired seeds by 0.0012 on test (7/10 wins, CI [−0.0010, 0.0035]) and 0.0065 on validation (CI [0.0043, 0.0086]). These comparisons support using forest subtraction and onset normalization together (§6.4, Appendix C.2).

W4&Q2. Preprocessing and cached runtime. We profiled seven encodings end to end from the edge list on 202 real graphs, using one CPU thread per measurement and h=20h=20 for RRWP (Tables 22–23).

Sample (median nodes)SPHist/DegreeHistMagResPERRWP
ZINC-12K (23)3.2–3.3ms4.1ms7.7ms
Peptides-struct (126)6.3–6.4ms10.4ms16.5ms
PascalVOC-SP( 481)55.9–57.3ms147.1ms105.2ms
REDDIT-BINARY (2,973)1.16–1.21s8.85s8.03s

MagResPE preprocesses in 47% less time than RRWP on ZINC and 37% less on Peptides-struct. On ZINC, it matches RWSE at 4.1 ms and is faster than LapPE (4.8 ms). In the largest bin, it takes 10% longer than RRWP but uses 80% less incremental peak CPU memory (481 vs. 2,413 MB). The histograms use 206 MB, and DirectDefect takes 2.07 s and uses 408 MB. On full PascalVOC-SP, 16 workers cut the reusable cache’s build-and-load time from 18.1 to 3.4 min (5.3×, Table 25). The dense solve remains costly on large graphs.

Cached GRIT on ZINC (Table 20)Seconds/epoch ↓Peak GPU MB ↓Validation graphs/s ↑
RRWP63.82696.11,174
SPSE64.22696.11,229
RWSE59.07137.31,367
LapPE60.09135.11,424
StandaloneMagResPE57.27135.11,562
RRWP+MagResPE65.12665.71,204

Standalone MagResPE trains faster and has higher mean validation throughput than RWSE and LapPE at comparable GPU memory. It trails RRWP in predictive performance. The hybrid adds about 2% to cached epoch time relative to RRWP, with comparable validation throughput and GPU memory.

Thank you for the detailed responses and additional experiments. The new results have addressed some of my concerns. I'll keep my positive score accordingly.

Thank you for reviewing the additional experiments and sharing your assessment. Your feedback helped us strengthen the evaluation and clarify the scope of our claims.

Comments on the paper

3 comments

Dear Reviewers,

The authors have submitted their responses to the questions and concerns raised in the reviews. Please review their responses and provide any further comments or clarifications, if applicable.

Thank you for your time and consideration.

AuthorsOpenReview ↗

Update Manuscript

We thank the reviewers for their detailed feedback. We have revised the manuscript and added experiments and analyses in response to the reviews. The main updates are listed below.

  1. Reviewer NcDa — Matched controls, additional seeds, and backbone transfer. We added shortest-path and degree-weighted histogram controls to the same RRWP-equipped GRIT. MagResPE outperforms both controls on all five paired ZINC-12K seeds (Appendix C.5, Tables 16–17). We extended the matched ZINC comparison to ten paired seeds, where adding MagResPE reduces mean test MAE from 0.0625 to 0.0596. We also tested MagResPE in GraphGPS on PascalVOC-SP and profiled seven encodings on 202 real graphs, including graphs with roughly 3,000 nodes (Table 2, Appendix C.4, and Appendix E.3).

  2. Reviewer ZeJv — Prior work, expressivity, and benchmark comparisons. We expanded the related work on distance encodings and magnitude weightings (§2). We added an exact graph pair that the ridge correction distinguishes despite identical distance-shell signature multisets, established an upper bound via shortest-path GD-WL, and included the reviewer’s L=2L=2 subdivision example (Appendices A.6 and D.5). We also added a matched shortest-path histogram control on both synthetic tasks, analyzed numerical resolution at the tested scales, and expanded the published and cycle-aware baseline comparisons (Tables 1–2 and 18–19). An independent SVD solver check and a single-edge perturbation study now quantify numerical agreement and sensitivity to graph edits (Appendices E.4–E.5).

  3. Reviewer j79p — Formulation ablations, longer RRWP horizons, and claim scope. We added a rescaled raw-magnitude control to isolate the effects of forest subtraction and onset normalization. The ten-seed DirectDefect comparison shows a clearer validation benefit from the ridge solve, while its incremental test benefit remains uncertain (Table 4 and Tables 13–14). We also evaluated both GRIT variants at longer RRWP horizons on Peptides-struct and PascalVOC-SP (Table 15). We revised the contribution statement to frame MagResPE as an additional structural feature in matched experiments and clarified that the separation theorem concerns rooted RRWP row-profile summaries (§5.3 and Appendix C.6).

The individual replies provide the full comparisons and uncertainty estimates.

AuthorsOpenReview ↗

Follow-up to Reviewer ZeJv

Thank you, Reviewer ZeJv, for taking another look at the revision. For easy reference, here are our responses to your review: Part 1 - theory and expressivity and Part 2 - baselines, cost, and stability. If any concern remains central to your assessment after reading the revision, we’d be happy to clarify it.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.