- Rating
- 2
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper studies the size-transferability of Graph Transformers (GTs) from a manifold perspective. The authors establish an equivalence between discrete GTs on sampled graphs and a continuous Manifold Transformer (MT) limit, and show that if the positional encoding (PE) is transferable, then the induced GT inherits transferability. They provide pointwise convergence bounds for GT-to-MT and for two different PE families: truncated Laplacian eigenvectors and GNN-based convolutional PEs (RPEARL). The theoretical analysis predicts that eigenvector PEs suffer from instability due to the spectral gap and sign ambiguity, whereas GNN PEs yield more stable transferability without dependence on the eigengap. Experiments on node classification over several large graphs, as well as a terrain-graph shortest-path-distance application, support the theory: GTs with RPEARL PEs transfer more stably across graph sizes than those with Laplacian PEs, and sparse GTs retain transferability at substantially lower computational cost. Overall, the paper provides a timely theoretical and empirical treatment of an important practical question: whether GTs trained on smaller graphs can be reliably deployed on larger graphs.
Critical strengths
The comparison between eigenvector PEs and GNN PEs is insightful. The paper explains why Laplacian eigenvector PEs can be unstable due to the eigengap and sign ambiguity, while GNN PEs avoid the eigengap dependence.
The empirical study covers several large and heterophilic datasets, compares dense and sparse GTs, and includes additional architectures (GraphGPS, Exphormer) and PE variants. The ablation on SNAP-Patents is informative.
Critical weaknesses
The theoretical framework relies on strong assumptions: graphs are i.i.d. samples from a low-dimensional compact Riemannian manifold, with smooth density, appropriate kernel bandwidth, bounded linear attention operators, and normalized Lipschitz PEs. These assumptions may not hold for real-world graphs.
Sparse GTs are a central empirical contribution, but the theoretical analysis is developed for dense softmax GTs. Appendix E.4 and conjectures that the k-hop mask supplies useful local structure, but does not provide a transferability analysis for sparse attention.
Questions for authors
How sensitive are the transferability results to the hyperparameters selected on the full graph? Would per-size tuning change the conclusions?
In the terrain-graph experiment, how does omitting the second-stage MLP fine-tuning affect the comparison with Chen et al. (2025)? Would including it change the relative gains?