Size Transferability of Graph Transformers with Convolutional Positional Encodings Javier Porras-Valenzuela, Zhiyang Wang, Xiaotao Shang, Alejandro Ribeiro Abstract Transformers have achieved remarkable success across domains, motivating the rise of Graph Transformers (GTs) as attention-based architectures for graph-structured data. A key design choice in GTs is the use of Graph Neural Network (GNN)-based positional encodings to incorporate structural information. In this work, we study GTs through the lens of manifold limit models for graph sequences and establish a theoretical connection between GTs with GNN positional encodings and Manifold Neural Networks (MNNs). Building on transferability results for GNNs under manifold convergence, we show that GTs inherit transferability guarantees from their positional encodings. In particular, GTs trained on small graphs provably generalize to larger graphs under mild assumptions. We complement our theory with extensive experiments on standard graph benchmarks, demonstrating that GTs exhibit scalable behavior on par with GNNs. To further show the efficiency in a real-world scenario, we implement GTs for shortest path distance estimation over terrains to better illustrate the efficiency of the transferable GTs. Our results provide new insights into the understanding of GTs and suggest practical directions for efficient training of GTs in large-scale settings. 1 Introduction Transformers have recently been adapted to graph‑structured data by injecting graph information through positional or structural encodings while retaining global self‑attention—yielding Graph Transformers. Graph transformers have delivered state‑of‑the‑art or highly competitive results in several domains, including but not limited to large‑scale molecular property prediction ( 51 ) , biomedical knowledge graphs ( 18 ) , and long-range data benchmark ( 13 ) . Figure 1 : Diagram of Graph Transformer (GT) with RPEARL Positional Encodings. The graph {\mathbf{G}} is sampled from manifold {\mathcal{M}} . The graph structure is processed by RPEARL using a graph neural network. The positional encodings are added to the node features and passed to the graph transformer, which outputs node features {\mathbf{Y}} . Graph transformers perform attention on sets of nodes not strictly limited by their local neighborhoods, and incorporate structural information via positional encodings. Early examples compute dense, pairwise attention over all nodes of the graph, such as ( 12 ) which uses the top -k eigenvectors of the graph Laplacian as positional encodings, and SAN, which learns spectral encodings drawn from the Laplacian spectrum ( 24 ) . Other graph transformers use relative (pairwise) positional encodings, such as GraphiT (diffusion‑kernels) ( 34 ) , the Graphormer family (shortest‑path and centrality biases in dense self‑attention) ( 51 ) , random walk approaches ( 30 ; 14 ) , or GKAT (heat kernel-based) ( 9 ) . Mask-based relative encodings replace quadratic attention with structured sparsity to trade off globality and scalability, for example Exphormer (local neighborhood + expander graphs) ( 40 ) , and UnifiedGT ( k -hop neighborhood) ( 29 ) . We refer to ( 4 ) for an in-depth analysis on the properties of absolute and relative positional encodings on graph transformers. A central insight across this literature is that structure must be encoded explicitly for attention to be effective on graphs. The outstanding performance of full pairwise attention is restricted by its inherent computational complexity, impeding scalability to graphs beyond hundreds of thousands of nodes. Moreover, data collection costs for training with large graphs can be prohibitively expensive. Therefore, it is paramount to develop a graph transformer that can be transferable across different graph sizes under theoretical guarantees. Theory from spectral graph signal processing establishes that graph convolutional filters—under continuity conditions—are stable to perturbations and transferable across graphs sampled from the same limit model ( 46 ; 47 ; 37 ; 38 ; 23 ) . Furthermore, by analyzing graphs through limits, one obtains that graph filters and GNNs converge as graph size grows; hence, models trained on small graphs can be deployed on larger graphs from the same limit model without retraining. Building on this theory ( 20 ) has proposed RPEARL, which uses GNNs with random features as positional encodings. They show that an architecture consisting of RPEARL and a GNN backbone is provably more expressive than a message-passing GNN. RPEARL encodings are permutation equivariant and retain the same stability and transferability of GNNs. We show that when these stable and transferable encodings are fed to a transformer whose attention is controlled to be Lipschitz—e.g., by normalization schemes for self‑attention or by alternative Lipschitz attention maps—the composed model inherits stability and size‑transferability. Practically, this yields an efficient recipe: train on small graphs using graph convolutional positional encodings, then transfer to larger graphs while keeping attention regularized, achieving sub‑linear performance difference and substantial computational savings. The main contributions are as follows: • We argue that GNNs are a principled choice of positional encodings to ensure the stability, equivariance, generalization, and transferability of the transformer inputs. • We provide theoretical guarantees that graph transformers inherit the transferability properties of their GNN positional encodings, enabling competitive performance across different scales of graphs sampled from an underlying manifold without retraining. • We propose a transferable, practical sparse graph transformer with attention masking and RPEARL PEs, which is also covered by our transferability results. • We carry out experiments where we verify the transferability of various graph transformer architectures on different domains (ArXiv-year, Reddit, snap-patents, MAG). We show that the performance and transferability of sparse GT can match or outperform GNNs and dense graph transformers. To the best of our knowledge, our experiments provide the first results where full batch performance of graph transformers (dense and sparse) is analyzed on graphs larger than 1M nodes. • We validate our Sparse Graph Transformer over real-world terrain datasets and solve the shortest path distance estimation problem. 1.1 Related work Transferability and Generalization via Limit Models. The convergence of GNNs to manifold neural networks (MNNs) has been leveraged extensively as an analytical tool to establish the transferability, stability, and statistical generalization of graph neural networks ( 46 ; 47 ; 45 ) . Transferability has also been explored with graphons as a limit model for graphs ( 38 ; 31 ; 32 ) . More recently, ( 26 ) studied a general framework for transferability by relating small graph instances to limit objects. ( 27 ) presented the generalization analysis for general transformers without considering graph structural information. Efficent training on large graphs. The seminal work on efficient graph training is GraphSage ( 17 ) scales GNNs to large-scale graphs by training on minibatches of neighborhood subgraphs. ( 29 ) leverages GraphSage-style sampling. Based on graphon convergence results, ( 7 ) proposes training on growing graphs. Length Generalization in Transformers. Length generalization in large language models has been studied both empirically ( 53 ; 1 ) and theoretically ( 19 ) . It has been argued that positional encodings play an important role in achieving robust length generalization ( 22 ; 35 ) Yet, the characterization and necessary conditions for length generalization remain an open area of research. GNN-Transformer Hybrids. Several works have proposed similar hybrid “local‑global” models by combining message-passing GNNs with global attention. For instance, GraphGPS ( 36 ) , SGFormer ( 48 ) , GraphTrans ( 49 ) , and UnifiedGT ( 29 ) . The theoretical results on the transferability of graph transformers also covers these hybrid architectures. 2 Graph Transformer With RPEARL Positional Encodings Set up. An undirected graph {\mathbf{G}}=({\mathcal{V}},{\mathcal{E}},{\mathcal{W}}) contains a node set {\mathcal{V}} with N nodes and an edge set {\mathcal{E}}\subseteq{\mathcal{V}}\times{\mathcal{V}} . The weight function {\mathcal{W}}:{\mathcal{E}}\rightarrow{\mathbb{R}} assigns values to the edges. We define the graph Laplacian {\mathbf{L}}=\text{diag}({\mathbf{A}}\textbf{1})-{\mathbf{A}} where {\mathbf{A}}\in{\mathbb{R}}^{N\times N} is the weighted adjacency matrix. Graph signals are functions mapping nodes to feature vectors, which we denote by {\mathbf{x}}_{i}\in{\mathbb{R}}^{D} and collect in a matrix of column vectors {\mathbf{X}}=[{\mathbf{x}}_{1},\dots,{\mathbf{x}}_{N}] . 2.1 Graph Transformer A graph transformer is a layered architecture that processes graph signals {\mathbf{X}} and outputs a graph signal matrix {\mathbf{Y}}\in{\mathbb{R}}^{D\times N} by using an attention ( 42 ) operation, where each layer computes \displaystyle{\mathbf{Y}} \displaystyle=\bm{\Phi}_{\mathbf{G}}({\mathcal{T}},{\mathbf{X}})={\mathbf{V}}{\mathbf{X}}\ \text{softmax}\left[({\mathbf{Q}}{\mathbf{X}})^{\top}({\mathbf{K}}{\mathbf{X}})\right]. (1) The graph transformer \bm{\Phi}_{\mathbf{G}} is parameterized by the query, key and value linear maps {\mathbf{Q}} , {\mathbf{K}}, {\mathbf{V}}\in{\mathbb{R}}^{D\times D} , collected in {\mathcal{T}}=\{{\mathbf{Q}},{\mathbf{K}},{\mathbf{V}}\} . The operation ({\mathbf{Q}}{\mathbf{X}})^{\top}({\mathbf{K}}{\mathbf{X}}) computes inner products between pairs of projected node features \langle{\mathbf{Q}}{\mathbf{x}}_{i},{\mathbf{K}}{\mathbf{x}}_{j}\rangle , for all i,j\in[1,N] . Then, the softmax operation normalizes the pairwise inner products so that the rows sum to one. Finally, the output node features are computed as a linear combination of the projected values weighted by the attention coefficients. 1 1 1 For simplicity of presentation, we omit the transformer’s feedforward layer, softmax normalization constant, and low-rank projections. While we present our theory on a single-layer, single-head transformer, its extension to these settings graph transformers is straightforward. The input to the graph transformer is {\mathbf{X}}+\bm{\Psi}_{\mathbf{G}}({\mathcal{H}},{\mathbf{L}},{\mathbf{Z}}) , where \bm{\Psi}_{\mathbf{G}}:{\mathbb{R}}^{N\times D}\rightarrow{\mathbb{R}}^{N\times D} is called the graph positional encoder . The operator \bm{\Psi}_{\mathbf{G}} maps each node into a positional encoding vector utilizing the structural information of {\mathbf{L}} . Therefore, an effective choice of \bm{\Psi}_{\mathbf{G}} must satisfy key properties for graph signal processing, such as permutation equivariance, expressivity, and transferability. 2.2 Positional encodings with Graph Neural Networks Consider using a graph neural network (GNN) as a learnable positional encoder \bm{\Psi}_{\mathbf{G}} . A GNN is a layered architecture composed of graph convolutional filters followed by pointwise nonlinearities. One layer of a GNN is written as \displaystyle{\mathbf{P}}=\sigma\bigg[\sum_{k=0}^{K-1}{\mathbf{H}}_{k}{\mathbf{Z}}{\mathbf{L}}^{k}\bigg] (2) where {\mathbf{Z}}\in{\mathbb{R}}^{D\times N} are the input signals, and {\mathcal{H}}=\{{\mathbf{H}}_{1},\dots,{\mathbf{H}}_{K}\} collects the filter coefficients. Equation ( 2 ) performs a graph convolution of order K on the graph signals by the graph Laplacian {\mathbf{L}} , followed by the pointwise nonlinearity \sigma . The input signal {\mathbf{Z}} can be the graph signals, i.e. {\mathbf{Z}}={\mathbf{X}} . In the absence of data, it is also possible to leverage random features. Draw m\in[1,M] realizations {\mathbf{z}}^{(m)} of an N -dimensional random variable from an isotropic Gaussian distribution {\mathbf{z}}\sim{\mathcal{N}}({\mathbf{0}},{\mathbf{I}}_{N}) , and pass each realization in parallel to the GNN: \displaystyle{\mathbf{P}}^{(m)}=\sigma\bigg[\sum_{k=0}^{K-1}{\mathbf{H}}_{k}{\mathbf{z}}^{(m)\top}{\mathbf{L}}^{k}\bigg], (3) where each {\mathbf{H}}_{k}\in{\mathbb{R}}^{D\times 1} . This results in M independent output matrices {\mathbf{P}}^{(m)}\in{\mathbb{R}}^{N\times D} . The realizations {\mathbf{z}}^{(m)} play the role of random node IDs, which are known to improve the expressiveness of the GNN by breaking structural symmetries ( 52 ) . However, the resulting outputs {\mathbf{P}}^{(m)}\in{\mathbb{R}}^{N\times D} lose permutation equivariace. Noting that the distribution of {\mathbf{z}} and its statistics are themselves permutation equivariant, we can recover this property by taking their empirical average: \displaystyle\bm{\Psi}_{\mathbf{G}}({\mathcal{H}},{\mathbf{L}},{\mathbf{Z}}) \displaystyle=\hat{\mathbb{E}}\big[{\mathbf{P}}^{(1)},\dots,{\mathbf{P}}^{(M)}\big]=\frac{1}{M}\sum_{m=1}^{M}{\mathbf{P}}^{(m)}. (4) The output is the positional encoding \bm{\Psi}_{\mathbf{G}}({\mathcal{H}},{\mathbf{L}},{\mathbf{Z}}) with dimensions {N\times D} . This positional encoder, named RPEARL, is shown by ( 20 ) to provably enhance the expressive power of GNNs beyond the WL-test while preserving key GNN properties (stability, scalability, and transferability) ( 39 ) . 3 Transferability Analysis of Graph Transformers via a Manifold Perspective A central bottleneck of graph transformers lies in their efficient deployment on large-scale graphs. The quadratic complexity of attention relative to graph size makes naive scaling impractical, often requiring costly retraining. Transferability offers a principled way to overcome this limitation by enabling models to capture structural regularities that persist across graph sizes and instances. In particular, if a sequence of graphs admits a well-defined limit object, then a model trained on small-scale graphs can, in principle, be transferred to larger-scale graphs without retraining, while preserving its functional behavior. In this section, we show that the transferability of graph transformers is inherited from the transferability of their positional encodings. That is, once positional encodings are size-transferable functions over the graph limit, the induced graph transformer naturally generalizes across graph scales. Building on this insight, we present the first transferability analysis of graph transformers from a manifold-based perspective, establishing a theoretical foundation for size-generalizable and scalable graph transformers. 3.1 Discrete graphs and operator limits We study transferability by relating graph-based computations to their continuum counterparts on a manifold. Let {\mathcal{M}} be a d -dimensional compact, smooth and differentiable Riemannian submanifold embedded in a \mathsf{M} -dimensional space {\mathbb{R}}^{\mathsf{M}} with finite volume. This induces a measure \mu which has a non-vanishing Lipschitz continuous density \rho with respect to the Riemannian volume over the manifold with \rho:{\mathcal{M}}\rightarrow(0,\infty) , assumed to be bounded as 0<\rho_{min}\leq\rho(x)\leq\rho_{max}<\infty for all x\in{\mathcal{M}} . The manifold data supported on each point x\in{\mathcal{M}} is defined by vector-valued functions f:{\mathcal{M}}\rightarrow{\mathbb{R}}^{p} ( 47 ) . We use L^{2}(\mu;{\mathbb{R}}^{p}) to denote square-integrable {\mathbb{R}}^{p} -valued functions over {\mathcal{M}} with respect to measure \mu . Given a set of N i.i.d. samples X_{N}=\{x_{i}\}_{i=1}^{N} drawn from \mu over {\mathcal{M}} , we construct a graph {\mathbf{G}}({\mathcal{V}},{\mathcal{E}},{\mathcal{W}}) on these N sampled points X_{N} , where each point x_{i} is a vertex of graph {\mathbf{G}} , i.e. {\mathcal{V}}=X_{N} . Each pair of vertices (x_{i},x_{j}) is connected with an edge while the weight attached to the edge {\mathcal{W}}(x_{i},x_{j}) is determined by a kernel function K_{\epsilon} . The kernel function is decided by the Euclidean distance \|x_{i}-x_{j}\| between these two points. The graph Laplacian denoted as {\mathbf{L}} can be calculated based on the weight function ( 33 ) . The constructed graph Laplacian with an appropriate kernel function has been proved to approximate the Laplace operator {\mathcal{L}} of {\mathcal{M}} ( 6 ; 3 ; 11 ) . In this paper, we implement the normalized Gaussian kernel definition in ( 11 ) . To compare discrete and continuous computations over the sampled graphs and ove the manifold, we introduce two linear mappings that connect data from sampled graph {\mathbf{G}}_{N} and manifold {\mathcal{M}} and back, i.e. sampling operator as {\mathbf{S}}_{N}:L^{2}(\mu;{\mathbb{R}}^{p})\rightarrow{\mathbb{R}}^{N\times p} and interpolation operator as {\mathbf{I}}_{N}:{\mathbb{R}}^{N\times p}\rightarrow L^{2}(\mu;{\mathbb{R}}^{p}) . We assume that these operators are bounded and consistent ( 46 ; 25 ) , i.e. \lim_{N\to\infty}\|{\mathbf{I}}_{N}{\mathbf{S}}_{N}f-f\|_{L^{2}(\mu)}=0,\text{for all}\;f\in L^{2}(\mu;\mathbb{R}^{p}). (5) With these mapping operators, the convergence of graph Laplacians {\mathbf{L}}_{N} over constructed graphs {\mathbf{G}}_{N} to the continuous operator {\mathcal{L}} can be written as \lim_{N\to\infty}\|{\mathbf{I}}_{N}{\mathbf{L}}_{N}{\mathbf{S}}_{N}f-{\mathcal{L}}f\|_{L^{2}(\mu)}=0, (6) for all f\in L^{2}(\mu;{\mathbb{R}}^{p}) . 3.2 Transferable Functions over Manifolds We now formalize transferability as a property of functions defined through graph operators that remain well defined in the continuum limit. Let \bm{\Psi} be a map defined on any Hilbert space with a bounded linear operator. We write this dependence explicitly as \bm{\Psi}_{\mathbf{G}}({\mathbf{L}}_{N},{\mathbf{X}})\in{\mathbb{R}}^{N\times q} with {\mathbf{X}}\in{\mathbb{R}}^{N\times p} as a graph-level realization and \bm{\Psi}_{\mathcal{M}}({\mathcal{L}},f)\in L^{2}(\mu;{\mathbb{R}}^{q}) with f\in L^{2}(\mu;{\mathbb{R}}^{p}) as a manifold-level realization. The same functional form \bm{\Psi} is thus instantiated on discrete graphs and on the continuum, with dependence on the underlying domain entering solely through the operator {\mathbf{L}}_{N} or {\mathcal{L}} . Definition 1 (Transferable functions over Manifolds) . Assume that \bm{\Psi} is permutation equivariant and uniformly Lipschitz in its inputs. \bm{\Psi} is said to be size-generalizable with respect to the operator convergence {\mathbf{L}}_{N}\to\mathcal{L} if for every admissible input function f\in L^{2}(\mu;\mathbb{R}^{p}) , \lim_{N\to\infty}\big\|{\mathbf{I}}_{N}\bm{\Psi}_{\mathbf{G}}({\mathbf{L}}_{N},{\mathbf{S}}_{N}f)-\bm{\Psi}_{\mathcal{M}}(\mathcal{L},f)\big\|_{L^{2}(\mu)}=0. (7) Definition 1 formalizes the notion of transferability as a function whose output converges to the limit as operating on the manifold. As a consequence, a transferable function \bm{\Psi} can be trained or defined on finite graphs of one size and deployed on other graph instances—possibly of different sizes or resolutions—as long as the associated operators converge to the same manifold limit {\mathcal{L}} . This operator-centric perspective underlies our analysis of graph transformers in the sequel, where we show that their transferability is inherited from the transferability of the positional encodings that define their operator dependence. 3.3 Transferable Graph Transformers To study the properties of graph transformers, we first define the counterpart of transformers over the manifold as the limit object. Definition 2 (Manifold Transformer (MT)) . A manifold transformer layer is defined as \displaystyle\bm{\Phi}_{\mathcal{M}}({\mathbf{T}},f)(x) \displaystyle=\frac{\int_{\mathcal{M}}e^{\langle{\mathbf{Q}}f(x),{\mathbf{K}}f(y)\rangle}{\mathbf{V}}f(y)d\mu(y)}{\int_{\mathcal{M}}e^{\langle{\mathbf{Q}}f(x),{\mathbf{K}}f(y)\rangle}d\mu(y)}, (8) for all x\in{\mathcal{M}} with the input function f defined as a positional encoding of a manifold signal g\in L^{2}({\mathcal{M}}) \displaystyle f(x) \displaystyle=\bm{\Psi}_{\mathcal{M}}({\mathcal{H}},{\mathcal{L}},g)(x). (9) Here, f and g are vector-valued functions over {\mathcal{M}} . The manifold transformer is a map \bm{\Phi}_{\mathcal{M}}:L^{2}(\mu;{\mathbb{R}}^{q})\rightarrow L^{2}(\mu;{\mathbb{R}}^{D}) resulting of the composition of f (the positional encoding) with the manifold attention operation. Equation ( 9 ) corresponds to the evaluation of the limit object of the positional encodings over the input manifold signal g . Equation ( 8 ) specifies manifold attention, an integral over a weighted sum of the projected inputs, with each weight corresponding to the exponential of inner products of the manifold attention. Equation ( 8 ) can be interpreted as a continuous analogue of the softmax attention in Equation ( 1 ) where attention coefficients are computed across infinitely many points across the manifold. We now introduce a set of assumptions required to ensure the convergence of GTs to MTs. Assumption 1 (Normalized Lipschitz signals) . The input manifold signals g are normalized Lipschitz for all points a,b\in{\mathcal{M}} , \|g(b)-g(a)\|\leq\|b-a\| . Assumption 2 (Bounded linear operators) . {\mathbf{Q}} , {\mathbf{K}} , and {\mathbf{V}} are bounded linear operators with constants C_{Q},C_{K},C_{V}>0 , i.e., \|{\mathbf{Q}}{\mathbf{x}}\|\leq C_{Q}\|{\mathbf{x}}\| , \|{\mathbf{K}}{\mathbf{x}}\|\leq C_{K}\|{\mathbf{x}}\| , \|{\mathbf{V}}{\mathbf{x}}\|\leq C_{V}\|{\mathbf{x}}\| , \text{for all}\,{\mathbf{x}}\in{\mathbb{R}}^{D} . Assumption 3 (Transferable positional encoding) . The positional encoding function \bm{\Psi}_{\mathbf{G}}({\mathcal{H}},{\mathbf{X}}) is transferable and converges to a limit object \bm{\Psi}_{\mathcal{M}}({\mathcal{H}},f):{\mathcal{M}}\rightarrow{\mathbb{R}}^{q} . The output difference between a transferable positional encoding and its limit object,for a point x\in{\mathcal{M}} , is denoted by \|\bm{\Psi}_{\mathbf{G}}(\cdot)(x)-\bm{\Psi}_{\mathcal{M}}(\cdot)(x)\|\leq\Delta_{\mathrm{PE}} Assumption 1 is a mild assumption on the underlying manifold. Assumption 2 can be seen as regularization of transformer operators. These can be realized in practice via penalty terms during training process. Assumption 3 is readily satisfied in the case where \bm{\Psi}_{\mathbf{G}} is a GNN, which follows from established convergence results of GNNs to MNNs, shown via manifold convergence analysis in previous works ( 46 ) . Building on this foundation, in Appendix 6.2 we present a convergence theorem from the literature, tailored to our setting. We can now present our main theorem on the convergence of GT to MT, which we will use to show the transferability of GT. Theorem 1 . (Point-wise Convergence of GT to MT) For any x\in{\mathcal{M}} , under assumptions 1 — 3 , the pointwise output difference between a graph transformer and manifold transformer, with probability at least 1-\delta , is bounded by \displaystyle\|\bm{\Phi}_{\mathbf{G}}({\mathbf{T}},{\mathbf{X}})(x)-\bm{\Phi}_{\mathcal{M}}({\mathbf{T}},f)(x)\|_{2}\leq\Delta_{\bm{\Phi}({\mathbf{X}})} \displaystyle=\big[C_{V}+4e^{2M}C_{QKV}\big]\Delta_{\mathrm{PE}} \displaystyle+\ \big[e^{M}C_{V}+2e^{2M}C_{QKV}\big]A\left(\frac{\log N}{N}\right)^{1/d}, (10) where A is a constant related to the geometry of {\mathcal{M}} , d\geq 3 is the intrinsic dimension of the manifold, C_{QKV}=C_{Q}C_{K}C_{V} and C_{V} are the linear operator bound constants of {\mathbf{Q}} , {\mathbf{K}} , and {\mathbf{V}} , and M:=\sup_{u,v\in{\mathcal{M}}}\ \langle{\mathbf{Q}}f(u),{\mathbf{K}}f(v)\rangle . Figure 2 : Transferability plots. For each dataset, the x axis represents the train graph sizes as a proportion of the largest graph (\alpha) , and the y axis is the test accuracy at the full-sized graph. The titles show dataset name and largest graph size. The proof of Theorem 1 is available in Appendix 6.6 . This result proves that as the number of nodes sampled in graph {\mathbf{G}} increases, the output of GT tends to converge to the underlying MT with a rate {\mathcal{O}}\left(\left({\log N/N}\right)^{(1/d)}\right) . The dependence of this result on the linear operator bounds C_{CKV} and C_{V} , as well as the bound on the positional encoding \Delta_{PE} , suggests that smoother linear operators {\mathbf{Q}},{\mathbf{K}},{\mathbf{V}},{\mathbf{H}} can improve the convergence rate. This provides the insight that regularized operators in GT and its positional encoding helps to achieve a better convergence result, hence a better transferability performance. Theorem 1 indicates that the pointwise output difference of GT and MT decays as the size of the sampled graph N grows. This implies that we can train a GT on a small graph {\mathbf{G}}_{1} with N_{1} nodes, and transfer it to a larger graph {\mathbf{G}}_{2} , with N_{2}>N_{1} , with guarantees that the approximation gap to the manifold transformer’s output is bounded. This implication is meaningful in practice given the {\mathcal{O}}(N^{2}) computational cost of GT – we can train on a relatively smaller graph and ensure good performance on larger graphs. We state this below in the following corollary: Corollary 2 . (Transferability of Graph Transformers) Let graphs {\mathbf{G}}_{1} and {\mathbf{G}}_{2} constructed by points sampled from {\mathcal{M}} , with N_{1} , N_{2} nodes respectively, and graph signals {\mathbf{X}}_{1} and {\mathbf{X}}_{2} . Then, it holds, with probability 1-\delta , \displaystyle\frac{1}{\mu({\mathcal{M}})} \displaystyle||{\mathbf{I}}_{N_{1}}\bm{\Phi}_{{\mathbf{G}}_{1}}({\mathbf{T}},{\mathbf{X}}_{1})-{\mathbf{I}}_{N_{2}}\bm{\Phi}_{{\mathbf{G}}_{2}}({\mathbf{T}},{\mathbf{X}}_{2})||_{L^{1,2}({\mathcal{M}})} \displaystyle\leq\Delta_{\bm{\Phi}({\mathbf{X}}_{1})}+\Delta_{\bm{\Phi}({\mathbf{X}}_{2})} \displaystyle\quad+4e^{2M}C_{QKV}A\left(\frac{\log N}{N}\right)^{1/d} (11) Further, as we propose the architecture in Section 2 , RPEARL as positional encodings also possess the transferability property as studied in ( 20 ) . We state the transferability of graph transformers proposed in Section 2 as Corollary 3 . Our proposed graph transformer architecture with RPEARL positional encoding is size tranferable with probability 1-\delta \displaystyle\|\bm{\Phi}_{\mathbf{G}}({\mathbf{T}},{\mathbf{X}})(x)-\bm{\Phi}_{\mathcal{M}}({\mathbf{T}},f)(x)\|_{2} \displaystyle\leq\big[C_{V}+4e^{2M}C_{QKV}\big]\Bigg(C_{\mathcal{M}}\left(\frac{\log(C/\delta)}{N}\right)^{\frac{1}{d+4}} \displaystyle+\sqrt{\frac{\log(1/\delta)}{N}}\Bigg)+\ \big[e^{M}C_{V}+2e^{2M}C_{QKV}\big]A\left(\frac{\log N}{N}\right)^{1/d}. (12) 3.4 Sparse Graph Transformer (Sparse GT). One common computational tradeoff in graph transformers is to mask coefficients to attend to a neighborhood of nodes reachable in k -hops instead of computing all pairwise node attentions. Restricting the attention operation to the k -hop neighborhood results in the Sparse Graph Transformer (Sparse GT) given by \displaystyle{\mathbf{x}}_{i}=\frac{\sum_{j\in{\mathcal{N}}^{\leq k}(i)}\exp\{\langle{\mathbf{Q}}{\mathbf{x}}_{i},{\mathbf{K}}{\mathbf{x}}_{j}\rangle\}{\mathbf{V}}{\mathbf{x}}_{j}}{\sum_{j\in{\mathcal{N}}^{\leq k}(i)}\exp\{\langle{\mathbf{Q}}{\mathbf{x}}_{i},{\mathbf{K}}{\mathbf{x}}_{j}\rangle\}}. (13) where we denote the k -hop neighborhood of node i as {\mathcal{N}}^{\leq k}(i)=\bigcup_{k^{\prime}=1}^{k}{\mathcal{N}}^{k}(i) , with {\mathcal{N}}^{k}(i)=\{j:j^{\prime}\in{\mathcal{N}}(j),j^{\prime}\in{\mathcal{N}}^{k-1}(i)\} . We denote the Sparse GT operator by \dot{\bm{\Phi}}_{\mathbf{G}}({\mathcal{T}},{\mathbf{X}}):X_{N}\rightarrow{\mathbb{R}}^{D} . Sparse GT reduces computational complexity from quadratic in the N to quadratic in the worst-case k -hop neighborhood cardinality. Additionally, the transferability results of Theorem 1 and Corollary 2 can be shown to hold equivalently for ( 13 ), by showing it converges to a restricted manifold transformer: \displaystyle\dot{\bm{\Phi}}_{\mathcal{M}}({\mathcal{T}},f)(x)=\frac{\int_{{\mathcal{M}}}\dot{\gamma}_{xy}{\mathbf{V}}f(y)d\mu(y)}{\int_{{\mathcal{M}}}\dot{\gamma}_{xy}d\mu(y)}, (14) where \dot{\gamma}_{xy}=\mathbbm{1}_{B_{r}(x)}\exp\{\langle{\mathbf{Q}}f(x),{\mathbf{K}}f(y)\rangle\} , and B_{r}(x) denotes an Euclidean ball of radius r centered around x . Analogous to the k- hop neighborhood, this modified kernel function restricts manifold attention contributions to a region around each point. Corollary 4 . Let X_{N}=\{x_{i}\}_{i=1}^{N} a set of points sampled from manifold {\mathcal{M}} . Let \bm{\Phi}_{{\mathcal{M}}_{i}}({\mathcal{T}},f,{\mathcal{L}}) denote a manifold transformer operating on manifolds {\mathcal{M}}_{i}=\{y\in{\mathcal{M}}:\|x_{i}-y\|0 , if n is sufficiently large so that \epsilon=\epsilon(n)\geq\left(\frac{\log n}{n}\right)^{\frac{1}{2d+12}} , then with probability greater than 1-n^{-2} , for all 0\leq i0 , there exists some M_{0} , such that for all M>M_{0} it holds that A_{4}(M)\leq\delta/2 . There also exists n_{0} , such that for all N>n_{0} , it holds that A_{1}(N)+A_{2}(M_{0},N)+A_{3}(N)\leq\delta/2 . We can conclude that the summations converge as N goes to infinity. We see M large enough to have M^{-1}\leq\delta^{\prime} , which makes the eigengap \theta_{M} also bounded by \epsilon . We combine the first two terms as \displaystyle\|[{\mathbf{h}}({\mathbf{L}}_{N}){\mathbf{S}}_{N}f]_{j}-{\mathbf{h}}({\mathcal{L}}_{\rho})f(x_{j})\|\leq(C_{1}C_{L}+C_{2}){\epsilon}^{2}+\frac{\pi^{2}}{6}\sqrt{\frac{\log(1/\delta)}{N}}, (51) with C_{1}=\Omega_{1}\frac{\pi^{2}}{6}\|f\|_{\mathcal{M}} and C_{2}=\Omega_{2}\frac{\pi^{2}}{6}\theta^{-1}_{\delta^{\prime-1}} . To bound the output difference of MNNs, we need to write in the form of features of the final layer \displaystyle\|[\bm{\Psi}_{\mathbf{G}}({\mathbf{H}},{\mathbf{L}}_{N},{\mathbf{S}}_{N}f)]_{j}-\bm{\Psi}({\mathbf{H}},{\mathcal{L}}_{\rho},f)(x_{j})\| \displaystyle=\left\|\sum_{q=1}^{F}[{\mathbf{x}}_{n,L}^{q}]_{j}-\sum_{q=1}^{F}f_{L}^{q}(x_{j})\right\| (52) \displaystyle\leq\sum_{q=1}^{F}\left\|[{\mathbf{x}}_{n,L}^{q}]_{j}-f_{L}^{q}(x_{j})\right\|. (53) By inserting the definitions, we have \displaystyle\left\|[{\mathbf{x}}_{n,l}^{p}]_{j}-f_{l}^{p}(x_{j})\right\|=\left\|\sigma\left(\left[\sum_{q=1}^{F}{\mathbf{h}}_{l}^{pq}({\mathbf{L}}_{N}){\mathbf{x}}_{n,l-1}^{q}\right]_{j}\right)-\sigma\left(\sum_{q=1}^{F}{\mathbf{h}}_{l}^{pq}({\mathcal{L}}_{\rho})f_{l-1}^{q}(x_{j})\right)\right\| (54) with {\mathbf{x}}_{n,0}={\mathbf{S}}_{N}f as the input of the first layer. With a normalized point-wise Lipschitz nonlinearity, we have \displaystyle\|[{\mathbf{x}}_{n,l}^{p}]_{j}-f_{l}^{p}(x_{j}) \displaystyle\|\leq\left\|\sum_{q=1}^{F}\left[{\mathbf{h}}_{l}^{pq}({\mathbf{L}}_{N}){\mathbf{x}}_{n,l-1}^{q}\right]_{j}-\sum_{q=1}^{F}{\mathbf{h}}_{l}^{pq}({\mathcal{L}}_{\rho})f_{l-1}^{q}(x_{j})\right\| (55) \displaystyle\leq\sum_{q=1}^{F}\left\|[{\mathbf{h}}_{l}^{pq}({\mathbf{L}}_{N}){\mathbf{x}}_{n,l-1}^{q}]_{j}-{\mathbf{h}}_{l}^{pq}({\mathcal{L}}_{\rho})f_{l-1}^{q}(x_{j})\right\| (56) The difference can be further decomposed as \displaystyle\|[{\mathbf{h}}_{l}^{pq}({\mathbf{L}}_{N}){\mathbf{x}}_{n,l-1}^{q}]_{j}-{\mathbf{h}}_{l}^{pq}({\mathcal{L}}_{\rho})f_{l-1}^{q}(x_{j})\| \displaystyle\leq\|[{\mathbf{h}}_{l}^{pq}({\mathbf{L}}_{N}){\mathbf{x}}_{n,l-1}^{q}]_{j}-[{\mathbf{h}}_{l}^{pq}({\mathbf{L}}_{N}){\mathbf{S}}_{N}f_{l-1}^{q}]_{j}+[{\mathbf{h}}_{l}^{pq}({\mathbf{L}}_{N}){\mathbf{S}}_{N}f_{l-1}^{q}]_{j}-{\mathbf{h}}_{l}^{pq}({\mathcal{L}}_{\rho})f_{l-1}^{q}(x_{j})\| (57) \displaystyle\leq\left\|[{\mathbf{h}}_{l}^{pq}({\mathbf{L}}_{N}){\mathbf{x}}_{n,l-1}^{q}]_{j}-[{\mathbf{h}}_{l}^{pq}({\mathbf{L}}_{N}){\mathbf{S}}_{N}f_{l-1}^{q}]_{j}\right\|+\left\|[{\mathbf{h}}_{l}^{pq}({\mathbf{L}}_{N}){\mathbf{S}}_{N}f_{l-1}^{q}]_{j}-{\mathbf{h}}_{l}^{pq}({\mathcal{L}}_{\rho})f_{l-1}^{q}(x_{j})\right\| (58) The second term can be bounded with ( 50 ) and we denote the bound as \Delta_{N} for simplicity. The first term can be decomposed by Cauchy-Schwartz inequality and non-amplifying of the filter functions as \displaystyle\left\|[{\mathbf{x}}_{n,l}^{p}]_{j}-f_{l}^{p}(x_{j})\right\|\leq\sum_{q=1}^{F}\Delta_{N}\|{\mathbf{x}}_{n,l-1}^{q}\|+\sum_{q=1}^{F}\|[{\mathbf{x}}_{l-1}^{q}]_{j}-f_{l-1}^{q}(x_{j})\|. (59) To solve this recursion, we need to compute the bound for \|{\mathbf{x}}_{l}^{p}\| . By normalized Lipschitz continuity of \sigma and the fact that \sigma(0)=0 , we can get \displaystyle\|{\mathbf{x}}_{l}^{p}\|\leq\left\|\sum_{q=1}^{F}{\mathbf{h}}_{l}^{pq}({\mathbf{L}}_{N}){\mathbf{x}}_{l-1}^{q}\right\|\leq\sum_{q=1}^{F}\left\|{\mathbf{h}}_{l}^{pq}({\mathbf{L}}_{N})\right\|\|{\mathbf{x}}_{l-1}^{q}\|\leq\sum_{q=1}^{F}\|{\mathbf{x}}_{l-1}^{q}\|\leq F^{l-1}\|{\mathbf{x}}\|. (60) Insert this conclusion back to solve the recursion, we can get \displaystyle\left\|[{\mathbf{x}}_{n,l}^{p}]_{j}-f_{l}^{p}(x_{j})\right\|\leq lF^{l-1}\Delta_{N}\|{\mathbf{x}}\|. (61) Replace l with L we can obtain \displaystyle\|[\bm{\Psi}_{\mathbf{G}}({\mathbf{H}},{\mathbf{L}}_{N},{\mathbf{S}}_{N}f)]_{j}-\bm{\Psi}({\mathbf{H}},{\mathcal{L}}_{\rho},f)(x_{j})\|\leq LF^{L-1}\Delta_{N}, (62) when the input graph signal is normalized. By replacing f={\mathbf{I}}_{N}{\mathbf{x}} , we can conclude the proof. 6.3 Local Lipschitz continuity of MNNs We utilize Proposition 3 in ( 45 ) , which shows that the outputs of MNN defined in ( 18 ) are locally Lipschitz continuous within a certain area, which is stated explicitly as follows. Proposition 2 . (Local Lipschitz continuity of MNNs ( 45 ) [Proposition 3]) Assume that the assumptions in Theorem 1 hold. Let MNN be L layers with F features in each layer, suppose the manifold filters are nonamplifying with |\hat{h}(\lambda)|\leq 1 and the nonlinearities normalized Lipschitz continuous, then there exists a constant C^{\prime} such that |\bm{\Phi}({\mathbf{H}},{\mathcal{L}}_{\rho},f)(x)-\bm{\Phi}({\mathbf{H}},{\mathcal{L}}_{\rho},f)(y)|\leq F^{L}C^{\prime}\text{dist}(x-y),\quad\text{for all }x,y\in B_{r}({\mathcal{M}}), (63) where B_{r}({\mathcal{M}}) is a ball with radius r over {\mathcal{M}} with respect to the geodesic distance. 6.4 Manifold decomposition and induced manifold signal The graph {\mathbf{G}} contains points X_{N}=\{x_{i}\}_{i=1}^{N} sampled from the manifold {\mathcal{M}} . The graph signal {\mathbf{X}}\in{\mathbb{R}}^{N\times D} can be viewed as a discretization of the continuous manifold signal f evaluated at points X_{N} , that is \displaystyle{\mathbf{S}}_{N}f={\mathbf{X}}, (64) where {\mathbf{S}}_{N}:L^{2}(\mu)\rightarrow L_{2}(X_{N}) is called the sampling operator. The sample X_{N} induces a decomposition of the manifold ( 41 ) , \{V_{i}\}_{i=1}^{N} with respect to X_{N} , with V_{i}\subset B_{r}(x_{i}) a ball of radius r centered at x_{i} , with respect to the Euclidean distance in Euclidean ambient space. Let \mu_{N}=\frac{1}{N}\sum_{i=1}^{N}\delta x_{i} the empirical measure of the random sample. The decomposition is defined by the \infty -optimal transport map T:{\mathcal{M}}\rightarrow X_{N} , defined by the \infty -optimal Transport Distance between \mu and \mu_{N} , \displaystyle d_{\infty}(\mu,\mu_{N})L=\min_{T:T\#\mu=\mu_{N}}\text{ess sup}_{x\in{\mathcal{M}}}\delta(x,t(x)). (65) Here, T\#\mu denotes that \mu(T^{-1}(V))=\mu_{N}(V) holds for every V_{i} of the decomposition of {\mathcal{M}} . The radius of the balls where the partitions are contained can be bounded as r\leq A(\frac{\log N}{N})^{1/d} when d\geq 3 and as r\leq A(\log N)^{3/4}/N^{1/2} when d=2 , with A being a constant related to the geometry of the manifold. The manifold function induced by the signals of the sampled graph is a piecewise constant function defined by \displaystyle({\mathbf{I}}_{N}{\mathbf{X}})(x)=\sum_{i=1}^{N}[{\mathbf{X}}]_{i}\mathbbm{1}_{x\in V_{i}}, (66) where {\mathbf{I}}_{N}:L_{2}(X_{N})\rightarrow L^{2}(\mu) denotes the interpolation operator. 6.5 Lemmas and Propositions In this section we state a series of lemmas that will be useful for the proof of Theorem 1 . Lemma 5 . Let x\in{\mathcal{M}} a point in the manifold, and y\in V_{j} , a point in partition V_{j}\subset B_{r}(x_{j}) . Then it holds that \displaystyle\left|\langle{\mathbf{Q}}f(x),{\mathbf{K}}f(x_{j})\rangle-\langle{\mathbf{Q}}f(x),{\mathbf{K}}f(y)\rangle\right|\leq B_{f}C_{Q}C_{K}\ r (67) Proof. \displaystyle\left|\langle{\mathbf{Q}}f(x),{\mathbf{K}}f(x_{j})\rangle-\langle{\mathbf{Q}}f(x),{\mathbf{K}}f(y)\rangle\right| \displaystyle=\left|\langle{\mathbf{Q}}f(x),{\mathbf{K}}\left(f(x_{j})-f(y)\right)\rangle\right| (68) \displaystyle\leq C_{Q}\|f(x)\|-C_{K}\|f(x_{j})-f(y)\| (69) \displaystyle\leq B_{f}C_{Q}C_{K}\|f(x_{j})-f(y)\| (70) \displaystyle\leq B_{f}C_{Q}C_{K}|x_{j}-y| (71) \displaystyle\leq B_{f}C_{Q}C_{K}\ r (72) Where in ( 69 ) we apply the bound on the linear operators {\mathbf{Q}} and {\mathbf{K}} , in ( 70 ) we apply the bound on the manifold signal \|f(x)\|\leq B_{f} , in ( 71 ) we apply the assumption on normalized Lipschitz MNN, \|f(x)-f(y)\|\leq|x-y| , and in ( 72 ) we use the fact that y\in V_{j} , therefore |y-x_{j}|\leq r . ∎ For notational brevity, onwards we will denote the GT attention coefficients as \gamma_{ij}=\exp[\langle{\mathbf{Q}}{\mathbf{x}}_{i},{\mathbf{K}}{\mathbf{x}}_{j}\rangle] , the MT attention coefficients as \tilde{\gamma}_{iy}=\exp[\langle{\mathbf{Q}}f(x_{i}){\mathbf{K}}f(y)\rangle] , and the induced manifold signal coefficients as \tilde{\gamma}_{ij}=\exp[\langle{\mathbf{Q}}f(x_{i}),{\mathbf{K}}f(x_{j})\rangle] . Lemma 6 . Let X_{N}=\{x_{i}\}_{i=1}^{N} be a se t of points sampled from the manifold {\mathcal{M}} , with its corresponding induced partitioning \{V_{i}\}_{i=1}^{N} . For each x_{j}\in X_{N} , and for any y\in V_{j} , it holds that \displaystyle|\tilde{\gamma}_{ij}-\tilde{\gamma}_{iy}| \displaystyle\leq e^{M}B_{f}C_{Q}C_{K}\ r (73) Proof. \displaystyle|\tilde{\gamma}_{ij}-\tilde{\gamma}_{iy}| \displaystyle=|\exp{\langle{\mathbf{Q}}f(x_{i}),{\mathbf{K}}f(x_{j})\rangle}-\exp{\langle{\mathbf{Q}}f(x_{i}),{\mathbf{K}}f(y)\rangle}| (74) \displaystyle\leq e^{M}\left|\langle{\mathbf{Q}}f(x_{i}),{\mathbf{K}}f(x_{j})\rangle-\langle{\mathbf{Q}}f(x_{i}),{\mathbf{K}}f(y)\rangle\right| (75) \displaystyle\leq e^{M}B_{f}C_{Q}C_{K}\ r (76) where M:=\sup_{u,v\in{\mathcal{M}}}\ \langle{\mathbf{Q}}f(u),{\mathbf{K}}f(v)\rangle . Note that M\leq C_{QK}B_{f}^{2} using the bounds on the MNN signal and linear operators. In the first inequality we use the mean value theorem, |e^{a}-e^{b}|\leq e^{\max\{a,b\}}|a-b| . In the second we apply the bound from Lemma 5 . ∎ Lemma 7 . For each x_{i},x_{j}\in X_{N} it holds that \displaystyle|\gamma_{ij}-\tilde{\gamma}_{ij}|\leq 2e^{M}C_{QK}\Delta_{\mathrm{PE}}. (77) Proof. \displaystyle|\gamma_{ij}-\tilde{\gamma}_{ij}| \displaystyle=\Bigl|\exp\!\big(\langle{\mathbf{Q}}{\mathbf{x}}_{i},{\mathbf{K}}{\mathbf{x}}_{j}\rangle\big)-\exp\!\big(\langle{\mathbf{Q}}f(x_{i}),{\mathbf{K}}f(x_{j})\rangle\big)\Bigr| (78) \displaystyle\leq e^{M}\Bigl|\langle{\mathbf{Q}}{\mathbf{x}}_{i},{\mathbf{K}}{\mathbf{x}}_{j}\rangle-\langle{\mathbf{Q}}f(x_{i}),{\mathbf{K}}f(x_{j})\rangle\Bigr| (79) \displaystyle\leq e^{M}\Bigl(\big|\langle{\mathbf{Q}}({\mathbf{x}}_{i}-f(x_{i})),{\mathbf{K}}{\mathbf{x}}_{j}\rangle\big|+\big|\langle{\mathbf{Q}}f(x_{i}),{\mathbf{K}}({\mathbf{x}}_{j}-f(x_{j}))\rangle\big|\Bigr) (80) \displaystyle\leq e^{M}\Bigl(\|{\mathbf{Q}}\|\,\|{\mathbf{K}}\|\,\|{\mathbf{x}}_{i}-f(x_{i})\|\,\|{\mathbf{x}}_{j}\|+\|{\mathbf{Q}}\|\,\|{\mathbf{K}}\|\,\|f(x_{i})\|\,\|{\mathbf{x}}_{j}-f(x_{j})\|\Bigr) (81) \displaystyle\leq 2e^{M}C_{QK}B_{f}\,\Delta_{\mathrm{PE}}\;\leq\;2e^{M}C_{QK}\Delta_{\mathrm{PE}}. (82) In ( 79 ) we apply the mean value theorem |e^{a}-e^{b}|\leq e^{\max\{a,b\}}|a-b| and upper-bound \max\{a,b\}\leq M . In ( 80 ) we add and subtract \langle{\mathbf{Q}}f(x_{i}),{\mathbf{K}}{\mathbf{x}}_{j}\rangle and use bilinearity and the triangle inequality. In ( 81 ) we apply Cauchy–Schwarz and boundedness of the linear operators. In ( 82 ) we use Assumption 3 and B_{f}=1 . ∎ Lemma 8 . Let x,y\in{\mathcal{M}} , with |x-x_{i}|\leq r . Then, it holds that \displaystyle|\tilde{\gamma}_{iy}-\tilde{\gamma}_{xy}|\leq e^{M}C_{QK}B_{f}r (83) Proof. \displaystyle|\tilde{\gamma}_{iy}-\tilde{\gamma}_{xy}|\ \displaystyle=|\exp\langle{\mathbf{Q}}f(x_{i}),{\mathbf{K}}f(y)\rangle-\exp\langle{\mathbf{Q}}f(x),{\mathbf{K}}f(y)\rangle| (84) \displaystyle\quad\leq e^{M}\left|\langle{\mathbf{Q}}f(x_{i}),{\mathbf{K}}f(y)\rangle-\exp\langle{\mathbf{Q}}f(x),{\mathbf{K}}f(y)\rangle\right| (85) \displaystyle\quad=e^{M}|\langle{\mathbf{Q}}\left[f(x_{i})-f(x)\right],{\mathbf{K}}f(y)\rangle| (86) \displaystyle\quad\leq e^{M}C_{QK}B_{f}r. (87) where in ( 85 ) we use |e^{a}-e^{b}|\leq e^{\max\{a,b\}}|a-b| and upper-bound \max\{a,b\}\leq M , in ( 86 ) we rearrange the terms, and in ( 87 ) we use the bounds on linear operators, bounded manifold signal, normalized Lipschitz of f , and |x-x_{i}|\leq r . ∎ 6.6 Proof of Theorem 1 Theorem 1 bounds the convergence of a Graph Transformer with GNN-based PEs to a Manifold Transformer with MNN-based PEs. Proof. The graph transformer’s output for the i -th node can be written in vector form as \displaystyle{\mathbf{x}}_{i}=\frac{\sum_{j=1}^{n}\exp[\langle{\mathbf{Q}}{\mathbf{x}}_{i},{\mathbf{K}}{\mathbf{x}}_{j}\rangle]{\mathbf{V}}{\mathbf{x}}_{j}}{\sum_{j=1}^{n}\exp[\langle{\mathbf{Q}}{\mathbf{x}}_{i},{\mathbf{K}}{\mathbf{x}}_{j}\rangle]} (88) For notational brevity, we will denote the GT attention coefficients as \gamma_{ij}=\exp[\langle{\mathbf{Q}}{\mathbf{x}}_{i},{\mathbf{K}}{\mathbf{x}}_{j}\rangle] , the MT attention coefficients as \tilde{\gamma}_{iy}=\exp[\langle{\mathbf{Q}}f(x_{i}){\mathbf{K}}f(y)\rangle] , and the induced manifold signal coefficients as \tilde{\gamma}_{ij}=\exp[\langle{\mathbf{Q}}f(x_{i}),{\mathbf{K}}f(x_{j})\rangle] . Furthermore, when necessary we will abbreviate the denominator terms as D_{\mathbf{G}}=\sum_{j=1}^{N}\gamma_{ij} , D_{\mathcal{M}}=\int_{{\mathcal{M}}}\tilde{\gamma}_{iy}d\mu(y) , and \bar{D}_{\mathcal{M}}=\sum_{j=1}^{n}\tilde{\gamma}_{ij} . Thus we have \displaystyle\bm{\Phi}_{\mathbf{G}}({\mathbf{X}};{\mathbf{T}})(x_{i}) \displaystyle=\frac{1}{D_{\mathbf{G}}}\sum_{j=1}^{n}\gamma_{ij}{\mathbf{V}}{\mathbf{x}}_{j} (89) \displaystyle\bm{\Phi}_{\mathcal{M}}(f;{\mathbf{T}})(x_{i}) \displaystyle=\frac{1}{D_{\mathcal{M}}}\int_{\mathcal{M}}\tilde{\gamma}_{iy}{\mathbf{V}}f(y)d\mu(y) (90) We will introduce an auxiliary term derived from the induced manifold signal, denoted by \displaystyle\bar{\Phi}_{\mathcal{M}}(f;{\mathbf{T}})(x_{i})= \displaystyle=\frac{\sum_{j=1}^{n}\int_{V_{j}}\tilde{\gamma}_{ij}{\mathbf{V}}{\mathbf{x}}_{j}d\mu(y)}{\sum_{j=1}^{n}\int_{V_{j}}\tilde{\gamma}_{ij}d\mu(y)}. (91) Notice that since the integrand does not depend on y , we can simplify \bar{\Phi}_{\mathcal{M}}(f;{\mathbf{T}})(x_{i}) to: \displaystyle\bar{\Phi}_{\mathcal{M}}(f;{\mathbf{T}})(x_{i}) \displaystyle=\frac{\sum_{j=1}^{n}\int_{V_{j}}\tilde{\gamma}_{ij}{\mathbf{V}}{\mathbf{x}}_{j}d\mu(y)}{\sum_{j=1}^{n}\int_{V_{j}}\tilde{\gamma}_{ij}d\mu(y)} (92) \displaystyle=\frac{\sum_{j=1}^{n}\tilde{\gamma}_{ij}{\mathbf{V}}{\mathbf{x}}_{j}\cdot\mu(V_{j})}{\sum_{j=1}^{n}\tilde{\gamma}_{ij}\cdot\mu(V_{j})} (93) \displaystyle=\frac{\frac{1}{N}\sum_{j=1}^{n}\tilde{\gamma}_{ij}{\mathbf{V}}{\mathbf{x}}_{j}}{\frac{1}{N}\sum_{j=1}^{n}\tilde{\gamma}_{ij}} (94) \displaystyle=\frac{1}{\bar{D}_{\mathcal{M}}}\sum_{j=1}^{n}\tilde{\gamma}_{ij}{\mathbf{V}}{\mathbf{x}}_{j}, (95) The output difference for node i can be decomposed as \displaystyle\|\bm{\Phi}_{G}({\mathbf{X}};{\mathbf{T}})(x_{i})-\bm{\Phi}_{\mathcal{M}}(f;{\mathbf{T}})(x_{i})\| \displaystyle=\|\bm{\Phi}_{\mathbf{G}}({\mathbf{X}};{\mathbf{T}})(x_{i})-\bar{\bm{\Phi}}_{\mathcal{M}}(f;{\mathbf{T}})(x_{i})+\bar{\bm{\Phi}}_{\mathcal{M}}(f;{\mathbf{T}})(x_{i})-\bm{\Phi}_{\mathcal{M}}(f;{\mathbf{T}})(x_{i})\| (96) \displaystyle\leq\|\bm{\Phi}_{\mathbf{G}}({\mathbf{X}};{\mathbf{T}})(x_{i})-\bar{\bm{\Phi}}_{\mathcal{M}}({\mathbf{X}};{\mathbf{T}})(x_{i})\|+\|\bar{\bm{\Phi}}_{\mathcal{M}}({\mathbf{X}};{\mathbf{T}})(x_{i})-\bm{\Phi}_{\mathcal{M}}(f,{\mathcal{L}};{\mathbf{T}})(x_{i})\| (97) To Equation ( 96 ) we add and subtract the induced manifold signal term, and in ( 96 ) to ( 97 ) we use the triangle inequality. We will now bound the first term of ( 97 ), \displaystyle\left|\bm{\Phi}_{\mathbf{G}}({\mathbf{X}};{\mathbf{T}})(x_{i})-\bar{\bm{\Phi}}_{\mathcal{M}}({\mathbf{X}};{\mathbf{T}})(x_{i})\right|=\left|\frac{1}{D_{\mathbf{G}}}\sum_{j=1}^{n}\gamma_{ij}{\mathbf{V}}{\mathbf{x}}_{j}-\frac{1}{\bar{D}_{\mathcal{M}}}\sum_{j=1}^{n}\tilde{\gamma}_{ij}{\mathbf{V}}f(x_{j})\right|. (98) Distribute the denominators, add and subtract D_{\mathcal{M}}\gamma_{ij}{\mathbf{V}}f(x_{j}) , then apply triangle inequality: \displaystyle\left\|\frac{1}{D_{\mathbf{G}}\bar{D}_{\mathcal{M}}}\sum_{j=1}^{N}\bar{D}_{\mathcal{M}}\gamma_{ij}{\mathbf{V}}{\mathbf{x}}_{j}-D_{\mathbf{G}}\tilde{\gamma}_{ij}{\mathbf{V}}f(x_{j})\right\| \displaystyle=\Bigg\|\frac{1}{D_{\mathbf{G}}\bar{D}_{\mathcal{M}}}\sum_{j=1}^{N}\bar{D}_{\mathcal{M}}\gamma_{ij}{\mathbf{V}}{\mathbf{x}}_{j}-\bar{D}_{\mathcal{M}}\gamma_{ij}{\mathbf{V}}f(x_{j})+\bar{D}_{\mathcal{M}}\gamma_{ij}{\mathbf{V}}f(x_{j})-D_{\mathbf{G}}\tilde{\gamma}_{ij}{\mathbf{V}}f(x_{j})\ \Bigg\| (99) \displaystyle\leq\left\|\frac{1}{D_{\mathbf{G}}\bar{D}_{\mathcal{M}}}\sum_{j=1}^{N}\bar{D}_{\mathcal{M}}\gamma_{ij}{\mathbf{V}}{\mathbf{x}}_{j}-\bar{D}_{\mathcal{M}}\gamma_{ij}{\mathbf{V}}f(x_{j})\right\|+\left\|\frac{1}{D_{\mathbf{G}}\bar{D}_{\mathcal{M}}}\sum_{j=1}^{N}\bar{D}_{\mathcal{M}}\gamma_{ij}{\mathbf{V}}f(x_{j})-D_{\mathbf{G}}\tilde{\gamma}_{ij}{\mathbf{V}}f(x_{j})\right\| (100) \displaystyle=\left\|\frac{1}{D_{\mathbf{G}}}\sum_{j=1}^{N}\gamma_{ij}{\mathbf{V}}({\mathbf{x}}_{j}-f(x_{j}))\right\|+\left\|\frac{1}{D_{\mathbf{G}}\bar{D}_{\mathcal{M}}}\sum_{j=1}^{N}(\bar{D}_{\mathcal{M}}\gamma_{ij}-D_{\mathbf{G}}\tilde{\gamma}_{ij}){\mathbf{V}}f(x_{j})\right\|. (101) Note that {\mathbf{x}}_{j}-f(x_{j}) represents the output difference between a GNN and an MNN evaluated at node x_{j} . By Assumption 3 , this difference is bounded by \Delta_{\mathrm{PE}} . Using this bound, we can control the first term of ( 101 ) as follows: \displaystyle\frac{1}{D_{\mathbf{G}}} \displaystyle\left\|\sum_{j=1}^{N}\gamma_{ij}{\mathbf{V}}({\mathbf{x}}_{j}-f(x_{j}))\right\|\leq\frac{1}{D_{\mathbf{G}}}\sum_{j=1}^{N}\gamma_{ij}\|{\mathbf{V}}\|\cdot\|{\mathbf{x}}_{j}-f(x_{j})\|\leq\frac{C_{V}\Delta_{\mathrm{PE}}}{D_{\mathbf{G}}}\sum_{j=1}^{N}\gamma_{ij}=C_{V}\Delta_{\mathrm{PE}}, (102) where we first apply the triangle inequality, along with the definition of the operator norm. Finally ( 102 ) uses the bound on the operator norm of {\mathbf{V}} and \|{\mathbf{x}}_{j}-f(x_{j})\|\leq\Delta_{\mathrm{PE}} from Assumption 3 , followed by the identity \sum_{j=1}^{N}\gamma_{ij}=D_{\mathbf{G}} . Now we bound the second term in ( 101 ). We add and subtract another comparative term \bar{D}_{\mathcal{M}}\tilde{\gamma}_{ij} , \displaystyle\left\|\frac{1}{D_{\mathbf{G}}\bar{D}_{\mathcal{M}}}\sum_{j=1}^{N}(\bar{D}_{\mathcal{M}}\gamma_{ij}-D_{\mathbf{G}}\tilde{\gamma}_{ij}){\mathbf{V}}f(x_{j})\right\| \displaystyle=\Bigg\|\frac{1}{D_{\mathbf{G}}\bar{D}_{\mathcal{M}}}\sum_{j=1}^{N}\Bigl[(\bar{D}_{\mathcal{M}}\gamma_{ij}-\bar{D}_{\mathcal{M}}\tilde{\gamma}_{ij})+(\bar{D}_{\mathcal{M}}\tilde{\gamma}_{ij}-D_{\mathbf{G}}\tilde{\gamma}_{ij})\Bigr]{\mathbf{V}}f(x_{j})\Bigg\| (103) \displaystyle=\Bigg\|\frac{1}{D_{\mathbf{G}}\bar{D}_{\mathcal{M}}}\sum_{j=1}^{N}\Big[\bar{D}_{\mathcal{M}}(\gamma_{ij}-\tilde{\gamma}_{ij})(\bar{D}_{\mathcal{M}}-D_{\mathbf{G}})\tilde{\gamma}_{ij}\Big]{\mathbf{V}}f(x_{j})\Bigg\| (104) \displaystyle\leq\sum_{j=1}^{N}\left\|\frac{\bar{D}_{\mathcal{M}}}{D_{\mathbf{G}}\bar{D}_{\mathcal{M}}}\left[(\gamma_{ij}-\tilde{\gamma}_{ij})\right]{\mathbf{V}}f(x_{j})\right\|+\left\|\frac{\tilde{\gamma}_{ij}(\bar{D}_{\mathcal{M}}-D_{\mathbf{G}})}{D_{\mathbf{G}}\bar{D}_{\mathcal{M}}}{\mathbf{V}}f(x_{j})\right\| (105) \displaystyle\leq\sum_{j=1}^{N}\|{\mathbf{V}}\|\|f(x_{j})\|\biggl[\frac{1}{D_{\mathbf{G}}}|\gamma_{ij}-\tilde{\gamma}_{ij}|+\frac{\tilde{\gamma}_{ij}}{D_{\mathbf{G}}\bar{D}_{\mathcal{M}}}|\bar{D}_{\mathcal{M}}-D_{\mathbf{G}}|\biggr] (106) \displaystyle\leq C_{V}B_{f}\sum_{j=1}^{N}\left[\frac{1}{D_{\mathbf{G}}}|\gamma_{ij}-\tilde{\gamma}_{ij}|+\frac{\tilde{\gamma}_{ij}}{D_{\mathbf{G}}\bar{D}_{\mathcal{M}}}|\bar{D}_{\mathcal{M}}-D_{\mathbf{G}}|\right] (107) \displaystyle\leq C_{V}B_{f}\left[\frac{N\cdot 2e^{M}C_{QK}\Delta_{\mathrm{PE}}}{D_{\mathbf{G}}}+\frac{|\bar{D}_{\mathcal{M}}-D_{\mathbf{G}}|}{D_{\mathbf{G}}\bar{D}_{\mathcal{M}}}\sum_{j=1}^{N}\tilde{\gamma}_{ij}\right] (108) \displaystyle\leq C_{V}B_{f}\left[2e^{2M}C_{QK}\Delta_{\mathrm{PE}}+\frac{|\bar{D}_{\mathcal{M}}-D_{\mathbf{G}}|}{D_{\mathbf{G}}}\right] (109) On ( 104 ) we rearrange the terms, on ( 105 ) we apply the triangle inequality, on ( 106 ) we use the operator norm inequality, and on ( 107 ) we apply the bounds from Assumptions 2 and 1 . On ( 108 ) we apply the bound from Lemma 7 . Finally, ( 109 ) uses \sum_{j=1}^{N}\tilde{\gamma}_{ij}=\bar{D}_{\mathcal{M}} for the second term, and for the first term we note that the worst case denominator is D_{\mathbf{G}}\geq N\cdot e^{-M} , which we can rearrange to bound N/D_{\mathbf{G}}\leq e^{M} . We can bound the remaining term using Lemma 7 : \displaystyle\frac{|\bar{D}_{\mathcal{M}}-D_{\mathbf{G}}|}{D_{\mathbf{G}}} \displaystyle=\frac{1}{D_{\mathbf{G}}}\left|\sum_{j=1}^{N}\tilde{\gamma}_{ij}-\sum_{j=1}^{N}\gamma_{ij}\right| (110) \displaystyle\leq\frac{1}{D_{\mathbf{G}}}\sum_{j=1}^{N}|\tilde{\gamma}_{ij}-\gamma_{ij}| (111) \displaystyle\leq\frac{N}{D_{\mathbf{G}}}\cdot 2e^{M}C_{QK}\Delta_{\mathrm{PE}} (112) \displaystyle\leq 2e^{2M}C_{QK}\Delta_{\mathrm{PE}}, (113) where in ( 111 ) we apply the triangle inequality, in ( 112 ) we apply Lemma 7 , and in ( 113 ) we again use N/D_{\mathbf{G}}\leq e^{M} . Substituting ( 113 ) into ( 109 ), the second term of ( 101 ) is bounded by \displaystyle\left\|\frac{1}{D_{\mathbf{G}}\bar{D}_{\mathcal{M}}}\sum_{j=1}^{N}(\bar{D}_{\mathcal{M}}\gamma_{ij}-D_{\mathbf{G}}\tilde{\gamma}_{ij}){\mathbf{V}}f(x_{j})\right\| \displaystyle\leq C_{V}B_{f}\left[2e^{2M}C_{QK}\Delta_{\mathrm{PE}}+2e^{2M}C_{QK}\Delta_{\mathrm{PE}}\right] (114) \displaystyle=4B_{f}e^{2M}C_{QKV}\Delta_{\mathrm{PE}}, (115) where we absorb the linear operator constants into C_{QKV}=C_{QK}C_{V} . Combining ( 102 ) and ( 115 ), we conclude the bound for the first term of ( 97 ) is \displaystyle\left|\bm{\Phi}_{\mathbf{G}}({\mathbf{X}};{\mathbf{T}})(x)-\bar{\bm{\Phi}}_{\mathcal{M}}({\mathbf{X}};{\mathbf{T}})(x)\right| \displaystyle\leq C_{V}\Delta_{\mathrm{PE}}+4B_{f}e^{2M}C_{QKV}\Delta_{\mathrm{PE}}. (116) We now bound the second term of ( 97 ). Let \tilde{D}_{\mathcal{M}}=\sum_{j=1}^{n}\int_{V_{j}}\tilde{\gamma}_{ij}d\mu(y) denote the discrete approximation of D_{\mathcal{M}} in integral form, \displaystyle\|\bar{\bm{\Phi}}_{\mathcal{M}}({\mathbf{X}};{\mathbf{T}})(x_{i})-\bm{\Phi}_{\mathcal{M}}(f,{\mathcal{L}};{\mathbf{T}})(x_{i})\| (117) \displaystyle=\Bigg\|\frac{1}{\tilde{D}_{\mathcal{M}}}\sum_{j=1}^{n}\int_{V_{j}}\tilde{\gamma}_{ij}{\mathbf{V}}f(x_{j})d\mu(y)-\frac{1}{D_{\mathcal{M}}}\int_{\mathcal{M}}\tilde{\gamma}_{iy}{\mathbf{V}}f(y)d\mu(y)\Bigg\| (118) \displaystyle=\Bigg\|\frac{1}{\tilde{D}_{\mathcal{M}}D_{\mathcal{M}}}\bigg(D_{\mathcal{M}}\sum_{j=1}^{n}\int_{V_{j}}\tilde{\gamma}_{ij}{\mathbf{V}}f(x_{j})d\mu(y)-\tilde{D}_{\mathcal{M}}\int_{\mathcal{M}}\tilde{\gamma}_{iy}{\mathbf{V}}f(y)d\mu(y)\bigg)\Bigg\| (119) \displaystyle=\Bigg\|\frac{1}{\tilde{D}_{\mathcal{M}}D_{\mathcal{M}}}\bigg(D_{\mathcal{M}}\sum_{j=1}^{n}\int_{V_{j}}\tilde{\gamma}_{ij}{\mathbf{V}}f(x_{j})d\mu(y)-\tilde{D}_{\mathcal{M}}\sum_{j=1}^{n}\int_{V_{j}}\tilde{\gamma}_{iy}{\mathbf{V}}f(y)d\mu(y)\bigg)\Bigg\| (120) \displaystyle=\Bigg\|\frac{1}{\tilde{D}_{\mathcal{M}}D_{\mathcal{M}}}\bigg(D_{\mathcal{M}}\sum_{j=1}^{n}\int_{V_{j}}\tilde{\gamma}_{ij}{\mathbf{V}}f(x_{j})d\mu(y)-\tilde{D}_{\mathcal{M}}\tilde{\gamma}_{iy}{\mathbf{V}}f(y)d\mu(y)\bigg)\Bigg\| (121) \displaystyle\leq\frac{1}{\tilde{D}_{\mathcal{M}}D_{\mathcal{M}}}\sum_{j=1}^{n}\int_{V_{j}}\Big\|D_{\mathcal{M}}\tilde{\gamma}_{ij}{\mathbf{V}}f(x_{j})-\tilde{D}_{\mathcal{M}}\tilde{\gamma}_{iy}{\mathbf{V}}f(y)\Big\|d\mu(y) (122) In ( 119 ) we distribute the denominators, in ( 120 ) we partition the integral, in ( 121 ) we rearrange terms, and in ( 122 ) we apply the triangle inequality. To bound the integrand of ( 122 ), we add and subtract D_{\mathcal{M}}\tilde{\gamma}_{ij}{\mathbf{V}}f(y) and apply the triangle inequality: \displaystyle\left\|D_{\mathcal{M}}\tilde{\gamma}_{ij}{\mathbf{V}}f(x_{j})-\tilde{D}_{\mathcal{M}}\tilde{\gamma}_{iy}{\mathbf{V}}f(y)\right\| (123) \displaystyle\leq\left\|D_{\mathcal{M}}\tilde{\gamma}_{ij}{\mathbf{V}}f(x_{j})-D_{\mathcal{M}}\tilde{\gamma}_{ij}{\mathbf{V}}f(y)\right\|+\left\|D_{\mathcal{M}}\tilde{\gamma}_{ij}{\mathbf{V}}f(y)-\tilde{D}_{\mathcal{M}}\tilde{\gamma}_{iy}{\mathbf{V}}f(y)\right\| (124) \displaystyle\leq D_{\mathcal{M}}\left\|{\mathbf{V}}(f(x_{j})-f(y))\right\|+\left\|(D_{\mathcal{M}}\tilde{\gamma}_{ij}-\tilde{D}_{\mathcal{M}}\tilde{\gamma}_{iy}){\mathbf{V}}f(y)\right\|. (125) The first term of ( 125 ) is bounded by \displaystyle D_{\mathcal{M}}\left\|{\mathbf{V}}(f(x_{j})-f(y))\right\| \displaystyle\leq D_{\mathcal{M}}\|{\mathbf{V}}\|\|f(x_{j})-f(y)\| (126) \displaystyle\leq D_{\mathcal{M}}C_{V}\|f(x_{j})-f(y)\| (127) \displaystyle\leq D_{\mathcal{M}}C_{V}r. (128) ( 126 ) linear operator bound, ( 127 ) Assumption 2 ( 128 ) using the fact that \|f(x_{j})-f(y)\|\leq r for all y\in V_{j} , and Assumption 1 ( f is normalized Lipschitz continuous). The second term of ( 125 ) is bounded by \displaystyle\left\|(D_{\mathcal{M}}\tilde{\gamma}_{ij}-\tilde{D}_{\mathcal{M}}\tilde{\gamma}_{iy}){\mathbf{V}}f(y)\right\| \displaystyle\leq\left|D_{\mathcal{M}}\tilde{\gamma}_{ij}-\tilde{D}_{\mathcal{M}}\tilde{\gamma}_{iy}\right|\|{\mathbf{V}}\|\|f(y)\| (129) \displaystyle\leq C_{V}B_{f}\left|D_{\mathcal{M}}\tilde{\gamma}_{ij}-\tilde{D}_{\mathcal{M}}\tilde{\gamma}_{iy}\right| (130) \displaystyle=C_{V}B_{f}\left|D_{\mathcal{M}}\tilde{\gamma}_{ij}-D_{\mathcal{M}}\tilde{\gamma}_{iy}+D_{\mathcal{M}}\tilde{\gamma}_{iy}-\tilde{D}_{\mathcal{M}}\tilde{\gamma}_{iy}\right| (131) \displaystyle\leq C_{V}B_{f}\left(D_{\mathcal{M}}\left|\tilde{\gamma}_{ij}-\tilde{\gamma}_{iy}\right|+\left|D_{\mathcal{M}}-\tilde{D}_{\mathcal{M}}\right|\tilde{\gamma}_{iy}\right) (132) In ( 129 ) we apply the linear operator bound, in ( 130 ) we use Assumption 2 ( \|{\mathbf{V}}\|\leq C_{V} ) and \|f(y)\|\leq B_{f} , in ( 131 ) we add and subtract D_{\mathcal{M}}\tilde{\gamma}_{iy} , and in ( 132 ) we apply the triangle inequality and factor. To bound the difference between denominator terms: \displaystyle\left|D_{\mathcal{M}}-\tilde{D}_{\mathcal{M}}\right| \displaystyle=\left|\int_{\mathcal{M}}\tilde{\gamma}_{iy}d\mu(y)-\sum_{j=1}^{n}\int_{V_{j}}\tilde{\gamma}_{ij}d\mu(y)\right| (133) \displaystyle=\left|\sum_{j=1}^{n}\int_{V_{j}}(\tilde{\gamma}_{iy}-\tilde{\gamma}_{ij})d\mu(y)\right| (134) \displaystyle\leq\sum_{j=1}^{n}\int_{V_{j}}\left|\tilde{\gamma}_{iy}-\tilde{\gamma}_{ij}\right|d\mu(y) (135) \displaystyle\leq\sum_{j=1}^{n}\int_{V_{j}}e^{M}B_{f}C_{QK}r\ d\mu(y) (136) \displaystyle=e^{M}B_{f}C_{QK}r, (137) where in ( 134 ) we partition the integral, in ( 135 ) we apply the triangle inequality, and in ( 136 ) we apply Lemma 6 and the fact that \mu({\mathcal{M}})=1 . Now, applying ( 137 ) and Lemma ( 6 ) to ( 132 ) we have that the second term of ( 125 ) is bounded by \displaystyle\left\|(D_{\mathcal{M}}\tilde{\gamma}_{ij}-\tilde{D}_{\mathcal{M}}\tilde{\gamma}_{iy}){\mathbf{V}}f(y)\right\| \displaystyle\leq C_{V}B_{f}\big(D_{\mathcal{M}}e^{M}B_{f}C_{Q}C_{K}\ r+e^{M}B_{f}C_{QK}r\tilde{\gamma}_{iy}\big) (138) \displaystyle\leq D_{\mathcal{M}}e^{M}B_{f}^{2}C_{QKV}r+e^{M}B_{f}^{2}C_{QKV}r\tilde{\gamma}_{iy} (139) Now, we return to bound the integral of ( 122 ), \displaystyle\|\bar{\bm{\Phi}}_{\mathcal{M}}({\mathbf{X}};{\mathbf{T}})(x_{i})-\bm{\Phi}_{\mathcal{M}}(f,{\mathcal{L}};{\mathbf{T}})(x_{i})\| (140) \displaystyle\leq\frac{1}{\tilde{D}_{\mathcal{M}}D_{\mathcal{M}}}\sum_{j=1}^{n}\int_{V_{j}}\Big\|D_{\mathcal{M}}\tilde{\gamma}_{ij}{\mathbf{V}}f(x_{j})-\tilde{D}_{\mathcal{M}}\tilde{\gamma}_{iy}{\mathbf{V}}f(y)\Big\|d\mu(y) (141) \displaystyle\leq\frac{1}{\tilde{D}_{\mathcal{M}}D_{\mathcal{M}}}\sum_{j=1}^{n}\int_{V_{j}}\Big[D_{\mathcal{M}}C_{V}r+D_{\mathcal{M}}e^{M}B_{f}^{2}C_{QKV}r+e^{M}B_{f}^{2}C_{QKV}r\tilde{\gamma}_{iy}\Big]d\mu(y) (142) \displaystyle\leq\frac{1}{\tilde{D}_{\mathcal{M}}D_{\mathcal{M}}}\Big[D_{\mathcal{M}}C_{V}r\mu({\mathcal{M}})+D_{\mathcal{M}}e^{M}B_{f}^{2}C_{QKV}r\mu({\mathcal{M}})+e^{M}B_{f}^{2}C_{QKV}r\sum_{j=1}^{n}\int_{V_{j}}\tilde{\gamma}_{iy}d\mu(y)\Big] (143) \displaystyle=\frac{C_{V}r\mu({\mathcal{M}})}{\tilde{D}_{\mathcal{M}}}+\frac{e^{M}B_{f}^{2}C_{QKV}r\mu({\mathcal{M}})}{\tilde{D}_{\mathcal{M}}}+\frac{e^{M}B_{f}^{2}C_{QKV}r\mu({\mathcal{M}})}{D_{\mathcal{M}}} (144) \displaystyle\leq\frac{C_{V}r\mu({\mathcal{M}})}{e^{-M}\mu({\mathcal{M}})}+\frac{e^{M}B_{f}^{2}C_{QKV}r\mu({\mathcal{M}})}{e^{-M}\mu({\mathcal{M}})}+\frac{e^{M}B_{f}^{2}C_{QKV}r\mu({\mathcal{M}})}{e^{-M}\mu({\mathcal{M}})} (145) \displaystyle\leq e^{M}C_{V}r+2e^{2M}B_{f}^{2}C_{QKV}r (146) where in ( 142 ) we use the bounds of ( 128 ) and ( 139 ), in ( 143 ) we evaluate the integrals of the first to terms, in ( 145 ) we distribute the denominators and use the fact that both denominators are positive quantities greater than e^{-M}\mu({\mathcal{M}}) . We conclude that the second term of ( 97 ) is bounded by \displaystyle\|\bar{\bm{\Phi}}_{\mathcal{M}}({\mathbf{X}};{\mathbf{T}})(x_{i})-\bm{\Phi}_{\mathcal{M}}(f,{\mathcal{L}};{\mathbf{T}})(x_{i})\|\leq e^{M}C_{V}r+2e^{2M}B_{f}^{2}C_{QKV}r (147) Finally, we can bound ( 97 ) using ( 116 ) and ( 147 ), which by gathering terms and setting B_{f}=1 . With this we conclude that the output difference of GT and MT is bounded by \displaystyle\|\bm{\Phi}_{G}({\mathbf{X}};{\mathbf{T}})(x_{i})-\bm{\Phi}_{\mathcal{M}}(f;{\mathbf{T}})(x_{i})\| \displaystyle\leq C_{V}\Delta_{\mathrm{PE}}+4e^{2M}B_{f}C_{QKV}\Delta_{\mathrm{PE}}+e^{M}C_{V}r+2e^{2M}B_{f}^{2}C_{QKV}r (148) \displaystyle\leq\big[C_{V}+4e^{2M}C_{QKV}\big]\Delta_{\mathrm{PE}}+\ \big[e^{M}C_{V}+2e^{2M}C_{QKV}\big]r. (149) which gives us the statement of Theorem 1 . ∎ 7 Proof of Corollary 2 Corollary 2 bounds the output difference between two GT’s trained with differently sized graphs by applying Theorem 1 . Proof. The output difference can be bounded as \displaystyle\frac{1}{\mu({\mathcal{M}})}\|{\mathbf{I}}_{N_{1}}\bm{\Phi}_{{\mathbf{G}}_{1}}({\mathbf{X}}_{1};{\mathbf{T}})-{\mathbf{I}}_{N_{2}}\bm{\Phi}_{{\mathbf{G}}_{2}}({\mathbf{X}}_{2};{\mathbf{T}})\|_{L^{1,2}({\mathcal{M}})} \displaystyle=\frac{1}{\mu({\mathcal{M}})}\|{\mathbf{I}}_{N_{1}}\bm{\Phi}_{{\mathbf{G}}_{1}}({\mathbf{X}}_{1};{\mathbf{T}})-\bm{\Phi}_{\mathcal{M}}(f;{\mathbf{T}})+\bm{\Phi}_{\mathcal{M}}(f;{\mathbf{T}})-{\mathbf{I}}_{N_{2}}\bm{\Phi}_{{\mathbf{G}}_{2}}({\mathbf{X}}_{2};{\mathbf{T}})\|_{L^{1,2}({\mathcal{M}})} (150) \displaystyle\leq\frac{1}{\mu({\mathcal{M}})}\|{\mathbf{I}}_{N_{1}}\bm{\Phi}_{{\mathbf{G}}_{1}}({\mathbf{X}}_{1};{\mathbf{T}})-\bm{\Phi}_{\mathcal{M}}(f;{\mathbf{T}})\|_{L^{1,2}({\mathcal{M}})}+\frac{1}{\mu({\mathcal{M}})}\|\bm{\Phi}_{\mathcal{M}}(f;{\mathbf{T}})-{\mathbf{I}}_{N_{2}}\bm{\Phi}_{{\mathbf{G}}_{2}}({\mathbf{X}}_{2};{\mathbf{T}})\|_{L^{1,2}({\mathcal{M}})} (151) \displaystyle\leq\frac{1}{\mu({\mathcal{M}})}\int_{\mathcal{M}}\|{\mathbf{I}}_{N_{1}}\bm{\Phi}_{{\mathbf{G}}_{1}}({\mathbf{X}}_{1};{\mathbf{T}})(x)-\bm{\Phi}_{\mathcal{M}}(f;{\mathbf{T}})(x)\|_{2}\ d\mu(x) (152) \displaystyle\quad+\frac{1}{\mu({\mathcal{M}})}\int_{\mathcal{M}}\|\bm{\Phi}_{\mathcal{M}}(f;{\mathbf{T}})(x)-{\mathbf{I}}_{N_{2}}\bm{\Phi}_{{\mathbf{G}}_{2}}({\mathbf{X}}_{2};{\mathbf{T}})(x)\|_{2}\ d\mu(x) (153) where in ( 150 ) we add and subtract \bm{\Phi}_{\mathcal{M}}(f;,{\mathbf{T}}) , in ( 151 ) we apply the triangle inequality, and ( 152 ) use the definition of L^{1,2}({\mathcal{M}}) . The two terms in ( 153 ) correspond to the pointwise difference between the induced manifold signal of GT and the output signal of the MT, for x\in{\mathcal{M}} . Consider bounding the first term, that compares \bm{\Phi}_{{\mathbf{G}}_{1}} with \bm{\Phi}_{\mathcal{M}} , \displaystyle\frac{1}{\mu({\mathcal{M}})}\int_{\mathcal{M}}\|{\mathbf{I}}_{N_{1}}\bm{\Phi}_{{\mathbf{G}}_{1}}({\mathbf{X}}_{1};{\mathbf{T}})(x)-\bm{\Phi}_{\mathcal{M}}(f;{\mathbf{T}})(x)\|_{2}\ d\mu(x) \displaystyle=\frac{1}{\mu({\mathcal{M}})}\sum_{i=1}^{N}\int_{V_{i}}\|\bm{\Phi}_{{\mathbf{G}}_{1}}({\mathbf{X}}_{1};{\mathbf{T}})(x_{i})-\bm{\Phi}_{\mathcal{M}}(f;{\mathbf{T}})(x)\|_{2}\ d\mu(x) (154) \displaystyle=\frac{1}{\mu({\mathcal{M}})}\sum_{i=1}^{N}\int_{V_{i}}\|\bm{\Phi}_{{\mathbf{G}}_{1}}({\mathbf{X}}_{1};{\mathbf{T}})(x_{i})-\bm{\Phi}_{\mathcal{M}}(f;{\mathbf{T}})(x_{i})+\bm{\Phi}_{\mathcal{M}}(f;{\mathbf{T}})(x_{i})-\bm{\Phi}_{\mathcal{M}}(f;{\mathbf{T}})(x)\|_{2}\ d\mu(x) (155) \displaystyle\leq\frac{1}{\mu({\mathcal{M}})}\sum_{i=1}^{N}\int_{V_{i}}\|\bm{\Phi}_{{\mathbf{G}}_{1}}({\mathbf{X}}_{1};{\mathbf{T}})(x_{i})-\bm{\Phi}_{\mathcal{M}}(f;{\mathbf{T}})(x_{i})\|+\|\bm{\Phi}_{\mathcal{M}}(f;{\mathbf{T}})(x_{i})-\bm{\Phi}_{\mathcal{M}}(f;{\mathbf{T}})(x)\|_{2}\ d\mu(x) (156) In ( 154 ) we apply the interpolator operator on \bm{\Phi}_{{\mathbf{G}}_{1}} , then in ( 156 ) we add and subtract the MT output at point x_{i} , and apply triangular inequality. The first term of ( 156 ) is the statement of Theorem 1 . The second term is the output difference of MT between a point within a partition x\in V_{i} and the center of the ball containing the partition x_{i} , therefore it holds that \|x_{i}-x\|\leq r . Denote the softmax denominators over x and x_{i} as D_{\mathcal{M}}(x) and D_{\mathcal{M}}(x_{i}) respectively. We can decompose this as \displaystyle\|\bm{\Phi}_{\mathcal{M}}(f;{\mathbf{T}})(x_{i})-\bm{\Phi}_{\mathcal{M}}(f;{\mathbf{T}})(x)\|_{2} \displaystyle\leq\Bigg\|\frac{\int_{\mathcal{M}}\tilde{\gamma}_{iy}{\mathbf{V}}f(y)d\mu(y)}{\int_{\mathcal{M}}\tilde{\gamma}_{iy}d\mu(y)}-\frac{\int_{\mathcal{M}}\tilde{\gamma}_{xy}{\mathbf{V}}f(y)d\mu(y)}{\int_{\mathcal{M}}\tilde{\gamma}_{xy}d\mu(y)}\Bigg\| (157) \displaystyle\leq\Bigg\|\frac{1}{D_{\mathcal{M}}(x)D_{\mathcal{M}}(x_{i})}\int_{\mathcal{M}}\Big(D_{\mathcal{M}}(x)\tilde{\gamma}_{iy}{\mathbf{V}}f(y)-D_{\mathcal{M}}(x_{i})\tilde{\gamma}_{xy}{\mathbf{V}}f(y)\Big)d\mu(y)\Bigg\| (158) \displaystyle\leq\frac{1}{D_{\mathcal{M}}(x)D_{\mathcal{M}}(x_{i})}\int_{\mathcal{M}}\Big\|D_{\mathcal{M}}(x)\tilde{\gamma}_{iy}{\mathbf{V}}f(y)-D_{\mathcal{M}}(x_{i})\tilde{\gamma}_{xy}{\mathbf{V}}f(y)\Big\|\ d\mu(y) (159) Which we obtain by distributing the denominators, applying the triangle inequality, and grouping terms. The integrand in ( 159 ) is bounded as \displaystyle\left\|D_{\mathcal{M}}(x)\tilde{\gamma}_{iy}{\mathbf{V}}f(y)-D_{\mathcal{M}}(x_{i})\tilde{\gamma}_{xy}{\mathbf{V}}f(y)\right\| \displaystyle\leq\|D_{\mathcal{M}}(x)\tilde{\gamma}_{iy}\left[{\mathbf{V}}f(x)-{\mathbf{V}}f(y)\right]-\left[D_{\mathcal{M}}(x)\tilde{\gamma}_{iy}-D_{\mathcal{M}}(x_{i})\tilde{\gamma}_{xy}\right]{\mathbf{V}}f(y)\| (160) \displaystyle\leq D_{\mathcal{M}}(x)C_{V}\tilde{\gamma}_{iy}\|f(x)-f(y)\|-C_{V}B_{f}\big|D_{\mathcal{M}}(x)\tilde{\gamma}_{iy}-D_{\mathcal{M}}(x_{i})\tilde{\gamma}_{xy}\big| (161) where in ( 160 ) add and subtract subtract D_{\mathcal{M}}(x)\tilde{\gamma}_{iy}{\mathbf{V}}f(x) We now focus on the second term of ( 161 ), \displaystyle\|D_{\mathcal{M}}(x)\tilde{\gamma}_{iy}-D_{\mathcal{M}}(x_{i})\tilde{\gamma}_{xy}\|\leq D_{\mathcal{M}}(x)|\tilde{\gamma}_{iy}-\tilde{\gamma}_{xy}|+\|\left[D_{\mathcal{M}}(x)-D_{\mathcal{M}}(x_{i})\right]\tilde{\gamma}_{xy}\| (162) The second term of ( 162 ) is \displaystyle\tilde{\gamma}_{xy}\|D_{\mathcal{M}}(x)-D_{\mathcal{M}}(x_{i})\| \displaystyle=\left\|\int_{\mathcal{M}}\tilde{\gamma}_{xy}\tilde{\gamma}_{xy}-\tilde{\gamma}_{iy}d\mu(y)\right\| (163) \displaystyle\leq\int_{\mathcal{M}}\tilde{\gamma}_{xy}\left\|\tilde{\gamma}_{xy}-\tilde{\gamma}_{iy}\right\|d\mu(y) (164) \displaystyle\leq D_{\mathcal{M}}(x_{i})e^{M}C_{QK}B_{f}r (165) where we use Lemma 8 to bound the remaining integral by D_{\mathcal{M}}(x_{i}) . Returning to the integral ( 159 ), we have \displaystyle\frac{C_{V}B_{f}}{D_{\mathcal{M}}(x)D_{\mathcal{M}}(x_{i})}\int_{\mathcal{M}}\Big\|D_{\mathcal{M}}(x)\tilde{\gamma}_{iy}{\mathbf{V}}f(y)-D_{\mathcal{M}}(x_{i})\tilde{\gamma}_{xy}{\mathbf{V}}f(y)\Big\|\ d\mu(y) (166) \displaystyle\qquad\leq\frac{C_{V}B_{f}}{D_{\mathcal{M}}(x)D_{\mathcal{M}}(x_{i})}\int_{\mathcal{M}}\Big\|D_{\mathcal{M}}(x)e^{M}C_{QK}B_{f}r+\tilde{\gamma}_{xy}\mu({\mathcal{M}})e^{M}C_{QK}B_{f}r\Big\|\ d\mu(y) (167) \displaystyle\qquad=\frac{C_{V}B_{f}}{D_{\mathcal{M}}(x)D_{\mathcal{M}}(x_{i})}D_{\mathcal{M}}(x)\mu({\mathcal{M}})e^{M}C_{QK}B_{f}r+\tilde{\gamma}_{xy}D_{\mathcal{M}}(x)\mu({\mathcal{M}})e^{M}C_{QK}B_{f}r (168) \displaystyle\qquad=\frac{1}{D_{\mathcal{M}}(x_{i})}2\mu({\mathcal{M}})e^{M}C_{QKV}B_{f}^{2}r (169) \displaystyle\qquad\leq 2e^{2M}C_{QKV}B_{f}^{2}r (170) by applying the bounds of ( 165 ) and Lemma 8 , then evaluating the integral, and finally using the fact that the denominator is D_{\mathcal{M}}(x_{i})\geq e^{M}/\mu({\mathcal{M}}) . We conclude that \displaystyle\|\bm{\Phi}_{\mathcal{M}}(f;{\mathbf{T}})(x_{i})-\bm{\Phi}_{\mathcal{M}}(f;{\mathbf{T}})(x)\|_{2}\leq 2e^{2M}C_{QKV}B_{f}^{2}r (171) We can now bound ( 152 ) by applying this bound and the bound of Theorem 1 , \displaystyle\frac{1}{\mu({\mathcal{M}})}\int_{\mathcal{M}}\|{\mathbf{I}}_{N_{1}}\bm{\Phi}_{{\mathbf{G}}_{1}}({\mathbf{X}}_{1};{\mathbf{T}})(x)-\bm{\Phi}_{\mathcal{M}}(f;{\mathbf{T}})(x)\|_{2}\ d\mu(x)\leq\Delta_{\bm{\Phi}({\mathbf{X}}_{1})}+2e^{2M}C_{QKV}B_{f}^{2}r, (172) where \Delta_{\bm{\Phi}({\mathbf{X}}_{1})} denotes the bound of Theorem 1 for G_{1} . Applying this bound in ( 153 ) for \bm{\Phi}({\mathbf{X}}_{1}) and \bm{\Phi}({\mathbf{X}}_{2}) gives us the statement of Corollary 2 . ∎ 7.1 Proof of Corollary 4 Proof. The proof of Theorem 1 can be adapted to account for Sparse GT. Notice that with the definition of the k -hop neighborhood, the only terms contributing to the softmax are |{\mathcal{N}}^{\leq k}(x_{i})| . Similarly for the restricted MT, the only nonzero terms contributing to t he integral are those contained in partitions y\in V_{i}\subset B_{r}(x_{i}) , i.e. D_{\mathcal{M}}=\int_{V_{i}}\tilde{\gamma}_{iy}Vf(y)d\mu(y) . With those modifications, the same proof applies and we arrive at the same bound. ∎ 8 Experiment Implementation Details Datasets. SNAP-Patents is a network for patents granted between 1963 to 1999 in the US. Each node is a patent, and a directed edge connects a patent to another patent that it cited. The prediction task is to classify each patent into one of five time intervals. ArXiv-year is a paper citation network on the arXiv papers. Each node represents a paper, and a directed edge connects a paper to another paper that it cited. The task is to predict the posting time of each paper, which is classified into one of five time intervals between 2013 and 2020. Both SNAP-Patents and arXiv-year are heterophilic graph datasets. OGBN-MAG is a heterogeneous network composed of a subset of the Microsoft Academic Graph (MAG), capturing the relationships among papers, authors, institutions and topics. The node classification task is to predict the venue of each paper. Reddit-Binary consists of 2000 graphs, each representing a subreddit community. The graph-level binary classification task is to identify each community as either a Q&A community or discussion-based community using graph structures. Table 2 : Datasets used for transferability experiments Dataset Nodes Edges Max Train/Test Nodes Classes Graphs Feature Dim SNAP-Patents 2,923,922 13,975,788 1,315,764 5 1 269 ArXiv-year 169,343 1,166,243 76,203 5 1 128 OGBN-MAG 736,389 5,416,271 2,923,922 349 1 128 Reddit-Binary avg. 429.61 avg. 497.75 / 2 2000 0 Dataset preparation. Each dataset is split into train/val/test fractions of 45%-10%-45% respectively. For datasets that have pre-established train/test masks, we discard the masks in favor of our partition proportions. The training and testing partitions are the sources for the graph subsampling procedure explained in Section 4 . Training procedure and transferability evaluation. For each model architecture, we train multiple models with graphs of increasing sizes and evaluate each model on testing graphs of different sizes. For single-graph datasets, the training graphs and testing graphs are constructed by subsampling a fraction of nodes from the training split and the testing split respectively. For multi-graph datasets, we construct the training graphs and testing graphs by subsampling the nodes in each training graph and each testing graph respectively by a specific fraction. We do not create graph batches, but rather train with the full subsampled graph. Hyperparameters. For each dataset, we tuned hyperparameters by training each model on the full training graph. Then, we held the selected hyperparameters fixed across all smaller training graph sizes. In general, We tuned learning rate over the interval [1\times 10^{-5},1\times 10^{-2}] , dropout and attention dropout over [0,0.5] , the feedforward hidden dimension in \{128,256,512\} , the number of transformer heads in \{4,8\} , the number of GNN/Transformer layers in \{3,4,5,6,7\} , the number of GNN/Sparse GT hops in \{2,3,4\} , and the Expander degree for Exphormer in \{3,4\} . The full set of hyperparameters used for each model and dataset is available in Table 3 . Table 3 : Hyperparameters for different model architectures across datasets Model/Hyperparameters snap-patents arXiv-year OGBN-MAG REDDIT-BINARY General Max epochs 300 300 700 350 GNN Learning rate 1\times 10^{-3} 1\times 10^{-2} 1\times 10^{-2} 3\times 10^{-3} Dropout 0.25 0.5 0.25 0 Hidden channels 256 256 128 512 Number of hop 3 3 3 3 Number of layers 7 3 7 2 Sparse GT + RPEARL Learning rate 5\times 10^{-4} 5\times 10^{-4} 5\times 10^{-4} 1\times 10^{-5} Dropout 0.01 0.01 0.5 0.01 Attention dropout 0.01 0.01 0.05 0.01 Dim model 256 256 128 128 Heads 8 8 4 8 Number of hops 2 2 2 3 Number of layers 8 3 3 3 Dense GT Learning rate 5\times 10^{-4} 5\times 10^{-4} 3\times 10^{-4} 5\times 10^{-4} Dropout 0.05 0.05 0.05 0.1 Attention dropout 0.15 0.15 0.15 0.1 Transformer Heads 4 4 4 8 Transformer dim feedforward 128 128 128 512 Transformer dim model 256 256 128 128 Transformer number of layers 3 3 3 3 Features Data Random Data Random PE hidden channels 128 128 128 512 PE number of layers 8 8 8 4 Exphormer Learning rate 1\times 10^{-3} 1\times 10^{-3} 1\times 10^{-3} 5\times 10^{-4} Dropout 0.5 0.5 0.5 0.01 Dim model 256 128 256 512 Dim feedforward 512 512 512 512 Expander algorithm Random-d Random-d Random-d Random-d Expander degree 3 3 3 4 Heads 8 8 8 4 Number of layers 2 2 2 5 MLP Learning rate 1\times 10^{-3} 1\times 10^{-3} 1\times 10^{-3} 5\times 10^{-4} Dropout 0.5 0.5 0.5 0 Hidden Dim 256 256 128 512 Number of layers 3 3 5 3 8.1 Extended Results In this section, we provide additional results, including transferability analysis for other reference architectures, as well as the full heatmaps for every model-dataset combination. Models. In addition to DGT and Sparse GT, we consider MLP and GNN ( 10 ) baselines, and Exphormer ( 40 ) , a sparse variant of graph transformer that computes attention coefficients for (i) one-hop neighbors, (ii) random edges from an expander graph, (iii) N additional attention coefficients between each node and a virtual global node. Crucially, Exphormer has no positional encodings beyond its masking. Transferability and comparison between models. Figure 5 contains transferability plots for all architectures. We observe transferability patterns for Dense GT, Sparse GT and GNN in most datasets. Exphormer shows transferable behavior in MAG and SNAP. In all datasets, GT is either comparable (MAG,Reddit) or significantly superior (SNAP, Arxiv-year) to GNN. This performance gap is consistent with previous work’s observations of the success of global attention in heterophilic datasets ( 12 ) . The trend of Exphormer in ArXiV-year also shows a more pronounced monotonic increase, possibly due to the random sampling procedure being more beneficial on larger graphs. In MAG and Reddit, GNN and GTs show comparable performance and transferability patterns. As the training fraction increases, the total number of nodes decreases. In the cases of SNAP-patents and MAG, Exphormers presents a monotonically increasing performance as training graph size increases. Figure 5 : Transferability plots for all datasets and architectures. For each dataset, the x axis represents the train graph sizes as a proportion of the largest graph (\alpha) , and the y axis is the test accuracy at the full-sized graph. The titles show dataset name and largest graph size. Figure 6 : Transferability plots for all datasets and architectures, zoomed into pre-peak-performance training fractions. For each dataset, the x axis represents the train graph sizes as a proportion of the largest graph (\alpha) , and the y axis is the test accuracy at the full-sized graph. The titles show dataset name and largest graph size. ((a)) Dense GT ((b)) Sparse GT ((c)) GNN ((d)) Exphormer Figure 7 : Test Accuracy Heatmaps on arXiv-Year across models. ((a)) Dense GT ((b)) Sparse GT ((c)) GNN ((d)) Exphormer Figure 8 : Test Accuracy Heatmaps on OGBN-MAG across models. ((a)) Dense GT ((b)) Sparse GT ((c)) GNN ((d)) Exphormer Figure 9 : Test Accuracy Heatmaps on SNAP-Patents across models. 8.2 Runtime analysis Our transferability results imply that it is possible to train with small graphs and attain competitive test performance on larger graphs, resulting in shorter training times. In addition to this, Sparse GT reduces the computational complexity from quadratic in the number of nodes to quadratic in the k -hop neighborhood cardinality. Table 4 shows the training times of Dense and Sparse GT for multiple fractions. We observe that Sparse GT is one or two orders of magnitude faster than Dense GT in all settings. It is worth highlighting that Sparse GT is both faster and achieves superior performance than Dense GT in ArXiv-year, and SNAP-Patents. Table 4 : Runtimes in minutes for three subsample sizes of Sparse and Dense GT Dataset Model 6.10% 56.84% 100.00% ArXiv-Year Dense GT 51.6 10.0 19.8 ArXiv-Year Sparse GT 8.8 1.4 2.0 OGBN-MAG Dense GT 41.8 103.3 366.6 OGBN-MAG Sparse GT 22.4 7.4 15.0 SNAP-Patents Dense GT 223.3 945.7 2763.6 SNAP-Patents Sparse GT 28.3 13.5 23.2 8.3 Terrain graphs In Section 4.3 we presented a practical implication of our theoretical results using terrain graphs, which are approximations of terrain manifolds. Sparse GT provides an efficient, scalable, and expressive architecture that can be applied to the metric learning problem in terrain graphs. Furthermore, the transferability guarantees of Corollary 3 imply that we need not train with the highest possible resolution of terrain graph in order to achieve competitive performance. Here we provide implementation details and an additional result on a second terrain graph dataset. Metric learning. The setup of ( 8 ) is to use imitation learning to learn a latent space that resembles true shortest-path distance between points. For two points x_{i},x_{j} in the terrain graph, we train to minimize \|L_{1}(\phi(x_{i})-\phi(x_{j}))-SPD(x_{i},x_{j})\|_{2} , where \phi is an embedding function, in our case either GNN or SGT. On ( 8 ) , a subsequent stage consists of freezing the embedding function’s parameters and finetuning an additional MLP on a larger set of sample points. In our experiments, we omit this second stage. Datasets. The terrain graphs we use are Digital Elevation Model (DEM) datasets. The results of Section 4.3 used a DEM of the Troms region of Norway ( 21 ) . The Norway dataset is available in a 2000\times 2000 (4M nodes) resolution. For our experiments we downsample so that the largest grid graph is 250\times 250 . Graph and train/test data constructions. To test transferability, we generate graphs of evenly spaced points based on the high resolution graph. The downsampling parameter r controls the space between generated points, i.e. r=1 is the full resolution, r=2 takes every second point (resulting in a 1000\times 1000 graph, etc. The edges of the graph are taken to be the 8 nearest neighbors. For training datasets, we subsample 500 sources and 100 targets per source, for a total of 50,000 pairs. For testing, a total of 10,000 source points are selected based on maximum height, and the SPD is computed between these points and every other point in the graph.