- 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 versus . 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 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 rescaling, not from the ridge-regularized magnitude correction. A control with raw magnitude and 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 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 time and memory, which makes the method hard to apply to large graphs.
Questions for authors
Check weakness section.
3 comments
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.
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 t-test p=0.0318). The hybrid wins on seven seeds, with exact sign-test p=0.3438 (Tables 13–14). At width 64, the gain also appears in all five paired runs (Table 12).
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−2 factor to the raw ridge weighting. This completes the forest-reference × onset-normalization comparison (Table 4).
Rescaling the raw weighting slightly worsens mean test MAE. Rescaling the forest-centered residual improves it by 0.0034. At fixed q−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 P, whose support determines adjacency and thus the shortest-path distances used by MagResPE. At h=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 p-values exceed 0.05 (Tables 16–17).
We extended RRWP from h=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=23.
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=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) time and O(n2) working memory.