acceptodds
Withdrawn from ICLR 2027

Size-Transferability of Graph Transformers with Convolutional Positional Encodings

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

Attention-based architectures have achieved remarkable success across data modalities, motivating the rise of Graph Transformers (GTs). GTs typically encode structural information via positional encodings (PEs), which may be either embedding vectors added to the input or modifications to the attention kernel. Given the challenges of learning from large graphs, a crucial question is whether GTs are _size-transferable_, that is, whether they can generalize to larger graphs than those seen during training. In this work, we study GTs through the lens of manifold limit models and establish that GTs can _inherit_ the transferability properties of their PEs. In particular, if the PEs are transferable, the GT is also transferable. We derive bounds showing that GTs with Graph Neural Network (GNN)-based PEs are transferable. Furthermore, our results show that their transferability is more stable than that of eigenvector-based GTs. We complement our theory with extensive experiments on standard graph benchmarks, where we confirm that GTs with GNN-based PEs exhibit superior transferability compared to those eigenvector-based PEs. We showcase a real-world application of a computationally efficient GT in a shortest-path distance estimation task over terrain manifolds. Our results provide new insights into GTs and suggest practical directions for efficient training in large-scale settings.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
Graph Transformers, Transferability, Graph Positional Encodings, Graph Neural Networks

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_zDb1OpenReview ↗
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?

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

The paper studies size transferability of Graph Transformers through a continuum model, the Manifold Transformer. Its main result decomposes the approximation error into PE error and graph discretization error, showing that GTs inherit convergence from their PEs. Experiments compare eigenvector and GNN-based PEs in dense and sparse GTs, with additional runtime and terrain shortest-path evaluations.

Critical strengths

The paper addresses a practical problem: whether GTs trained on small subgraphs remain useful on much larger graphs. The finding that k-hop sparse GTs with RPEARL remain competitive at substantially lower cost is valuable. The modular error decomposition also provides a clear way to connect PE convergence results to attention.

Critical weaknesses

The claimed eigengap independence is not established. The proof of Theorem 4 uses Proposition 5, an eigenvalue convergence result, to justify per-eigenvector convergence in (150)–(151). This requires additional justification, including eigengap dependence and eigenvector alignment. Moreover, the constants appear to retain gap dependence through Ω1\Omega_1 and θ−1\theta^{-1}. An eigengap-free result for smooth spectral filters may be possible, but the current proof does not establish it. This directly affects the paper’s central theoretical argument for preferring GNN-based PEs.

The theoretical novelty needs clearer positioning. Theorem 1 largely combines attention stability with a discretization argument, while Theorems 3–4 adapt existing results. Continuum attention and its approximation are already studied by Calvello et al.; Alokhina and Li also derive a closely related dependence on PE stability. I would not penalize the omission of a recent preprint, but the “first theoretical guarantees” claim should be qualified and the new technical contribution identified.

The theory does not cover the main experimental configurations. RPEARL’s random Gaussian inputs do not satisfy the assumed Lipschitz signal model, and no corresponding limit object is provided. The k-hop sparse GT, which supplies the strongest practical results, is also outside the stated theorem. The analysis is single-layer, and extending it requires controlling regularity and constants across layers. Finally, induced subgraphs of the benchmark networks differ substantially from the assumed manifold kernel graphs.

The experiments do not directly test the theoretical claim. Retraining at each graph size measures sensitivity to training size, whereas Corollary 2 bounds output differences for fixed parameters. No experiment measures this discrepancy or its convergence rate. The PE comparison is also confounded by different hyperparameters and, on some datasets, feature inputs. Stable eigenvector-based baselines such as SPE or SignNet are missing.

Questions for authors
  1. Requested clarifications and experiments. The priority is to establish whether Theorem 4’s constants are independent of eigengaps, including repeated eigenvalues, and clarify which experimental models the theory covers. A fixed-parameter transfer experiment on synthetic manifold graphs would directly test the result. Matched PE comparisons, including SPE or SignNet, would strengthen the empirical conclusions.
  2. Several reporting issues also need correction: inconsistent graph sizes, missing appendices and terrain results, the placeholder Figure 5 caption, and the factor omitted from the statement of Theorem 4.
Reviewer_fp1zOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This manuscript investigates the size-transferability of Graph Transformers (GTs) to see whether a model trained on a smaller graph can be used on a larger graph. It studies GTs through the lens of manifold limit models and provides theoretical evidence of the transferability. Experiments are conducted on node and graph classification datasets for evaluation.

Critical strengths
  1. An interesting and important topic of studying model transferability across graphs of different sizes.
  2. Theoretical evidence for the size-transferability of Graph Transformers.
Critical weaknesses

Insufficient comparison and discussion with prior work, in both the related work and experiment parts.

Questions for authors
  1. The paper cites graph-based transferability (Ruiz et al., 2020, 2023; Maskey et al., 2025), growing-graph training (Cervino et al., 2023), the size-generalization framework of Levin et al. (2025), and continuum attention (Calvello et al., 2025), but does not compare against any of them in detail.
  2. A clearer discussion of the theoretical novelty should be made against those methods of graph-based transferability, such as Levin et al. (2025).

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

Related papers

Discussion (0)

Sign in to comment.