From Theory to Practice: Rethinking Green and Martin Kernels for Unleashing Graph Transformers
Authors: Yoon Hyeok Lee
Jaemin Park
Taejin Paik
Doyun Kim
Bosun Hwang
Venue: ICML 2025 poster (2025)
Keywords: Graph Transformers
Graph Neural Networks
Structural Encodings
Green Kernel
Martin Kernel
Non-aperiodic substructures
DAGs
Primary area: deep_learning->graph_neural_networks
TL;DR: We proposed new structural encodings for graph transformers based on the Green and Martin kernels. Our approaches achieve SOTA performance on 7 out of 8 benchmark datasets, particularly excelling in molecular and circuit graphs.

Abstract: Graph Transformers (GTs) have emerged as a powerful alternative to message-passing neural networks, yet their performance heavily depends on effectively embedding structural inductive biases. In this work, we introduce novel structural encodings (SEs) grounded in a rigorous analysis of random walks (RWs), leveraging Green and Martin kernels that we have carefully redefined for AI applications while preserving their mathematical essence.These kernels capture the long-term behavior of RWs on graphs and allow for enhanced representation of complex topologies, including non-aperiodic and directed acyclic substructures.Empirical evaluations across eight benchmark datasets demonstrate strong performance across diverse tasks, notably in molecular and circuit domains.We attribute this performance boost to the improved ability of our kernel-based SEs to encode intricate structural information, thereby strengthening the global attention and inductive bias within GTs.This work highlights the effectiveness of theoretically grounded kernel methods in advancing Transformer-based models for graph learning.

From Theory to Practice: Rethinking Green and Martin Kernels for Unleashing Graph Transformers
Yoon Hyeok Lee" Jaemin Park I
Taejin Paik
Doyun Kim
Bosun Hwang?
Abstract
2019; Rusch et al., 2023], over-squashing [Alon & Yahav, 2020; Topping et al., 2021]. under-reaching [Sun et al., 2022; Barceló et al., 2020], and limited expressive power [Xu et al., 2018; Morris et al., 2019]. For GTs to perform effectively, it essential to incorporate inductive biases [Dosovitskiy et al., 2020] specific graph data. Additionally, global attention of GT's requires structural encodings (SEs) that enable precise differentiation of nodes within the graph and its substructures [Dwivedi & Bresson, 2020]. Recent model, GRIT [Ma et al.. 2023a], has shown state-of-the-at (SOTA) performance for various benchmarks by implicitly incorpo- rating the graph inductive bias from message-passingg and the global attention advantages of Transformer [Vaswani et al., 2017] by using Relative Random Walk Probabilities (RRWP) as the SE.
Graph Transformers (GTs) have emerged as a powerful alternative to message-passing neural networks, yet their performance heavily depends effectively embedding structural inductive bi- ases. In this work, we introduce novel structural encodings (SEs) grounded in a rigorous analy- sis of random walks (RWs), leveraging Green and Martin kernels that we have carefully rede- fined for AI applications while preserving their mathematical essence. These kernels capture the long-term behavior of RWs on graphs and allow for enhanced representation of complex topolo- gies, including non-aperiodic and directed acyclic substructures. Empirical evaluations across eight benchmark datasets demonstrate strong perfor- mance across diverse tasks, notably in molecu- lar and circuit domains. We attribute this perfor- mance boost to the improved ability of our kernel- based SEs to encode intricate structural informa- tion, thereby strengthening the global attention and inductive bias within GTss This work high- lights the effectiveness of theoretically grounded kernel methods in advancing Transformer-basee models for graph learning.
Random walks (RWs) have been extensively studied as a means of exploring the structure of graphs. Several re- sults [Lyons, 1994;
et al., 2019; Barlow, 2017] have demonstrated that the long-term behavior of a RW encapsulates the topological information of the graph. There are two mathematical quantities that capture this long- term behavior, providing valuable insights into the graph't 's characteristics. The Green kernel is classically defined as a "pseudo-inverse operator" used to find solutions to equa- tions [Evans, 2022]. Analogously, the Green kernel on a graph can be defined by the Moore-Penrose Inverse of the graph Laplacian matrix in [Chung Yau, 2000; Xu & Yau, 2013], in which the Green kernel is utilized for calculating various probabilistic quantities. In the context of RWs on graphs, it represents the expected number of visits to one node from another [Lyons & Peres, 2017]. The Martin ker- nel, on the other hand, is an important function in probability theory and potential theory, particularly within the frame- work of Martin boundary theory [Tsuji, 1959]. By utilizing Martin kernel, one can construct the harmonic potential function, which is essential tool for analyzing behavior of the Brownian motion [Paulin et al., 2012). The Martin kernel is defined on graphs analogously and used for con- structing the harmonic potential function [Broise-Alamichel et al., 2019]. Moreover, is equal to the probability that a RW starting from one node will reach another node within finite time [Barlow, 2017].
1. Introduction
Graph Transformers (GTs) [Ying et al., 2021; Hussain et al., 2022; Chen al., 2022a; Bo et al., 2023; Rampášek al., 2022; Ma et al., 2023a] have been proposed as superior alternative to conventional Message Passing Neural Net- works (MPNNs) [Gilmer et al., 2017], mitigating MPNNs' well-known issues such as over-smoothing [Oono & Suzuki,
'Equal contribution DDssign AI Lab, Al Center, Samsung Elec- tronics, Suwon, Republic of Korea "Normal Computing. New York, USA "Independent Researcher, Paju, Republic of Korea. Corre- spondence to: Yoon Hycok Lee syoonhuk10334 gmail.com>, Bosun Hwang <bshwang07 @ gmail.com>.
Proceedings of the nnnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Green and Martin Kernels for Graph Transformers
In this study, we introduce two extended concepts from the theory of RWs-the Green and Martin kernels [Barlow, 2017: Lyons& & Peres, 2017; Woess, 2000]-as new SEs. To the best of our knowledge, our paper is the first to introduce these concepts to design SEs. We apply these new SEs to the recently developed GRIT model [Ma et al., 2023a] and demonstrate that they outperform existing methods on various benchmark datasets, including the molecular and cir- cuit domains. Through this targeted innovation, we present new SEs that are not only specialized for non-aperiodic sub- structures and DAGs, but also enhanced performance across diverse benchmarks
to handle edge attributes more effectively. GraphGPS [Ram- pášek et al., 2022] applies relative SEs to facilitate interac- tion between local messagg--assing and global self-attention mechanism. In particular, the GRIT [Ma et al., 2023a] em- ploys a multimodal approach to incorporating both node and edge attributes into the self-attention mechanism. achieves high performance by utilizing RRWP, an SE based on RWs. effectively capturing the structural properties of graphs. For comprehensive insights into GT's readers can refer to detailed surveys that cover recent methodologies, challenges, and future research opportunities [Min et al., 2022; Müller et al., 2023].
In summary, our contributions are as follows. (i) We propose new SEs, Green Kernel Structural Encoding (GKSE) and Martin Kernel Structural Encoding (MKSE), based on the Green and Martin kernels, which extend the RWs. (ii) We in- tegrate GKSE and MKSE into the GRIT, demonstrating that GKSE and MKSE exhibit strong performance across vari- ous graph benchmarks, including those with small, medium, large, and long-range interactions. (iii) In molecular graphs containing numerous non-aperiodic substructures (e.g.. ben- zene rings), our methods demonstrate efficient learning and strong performance on ZINC (Dwivedi et al., 2023] and PCQM4Mv2 [Hu et al., 2021]. (iv) We demonstrate that GKSE and MKSE efficiently learn circuit domain data, which is represented as a DAG, and provide several baseline benchmark results on Open Circuit Benchmark (OCB), the first graph benchmark dataset in the circuit domain.
Structural Encodings for Graphs. GT's encounter notable challenges in encoding structural information, which are crucial for distinguishing non-isomorphic structures and uti- lizing graph symmetries. In this paper, consider and utilize SE as node and edge representations that are invari- ant to graph isomorphisms, in order to better capture the structural information of the graph [Lim et al., 2024; Li et al., 2020].
For SEs, the use of graph Laplacians in graph analysis has been widely explored. One study introduced globally con- sistent anisotropic kernels using Laplacian eigenvectors to incorporate directional information in GNNs [Beaini et al., 2021]. Additionally, other research has generalized graph Laplacians, demonstrating their effectiveness in capturing the geometric structure of graphs [Dwivedi & Bresson, 2020; Kreuzer et al., 2021]. Researchers have tackled the con- straints of spectral methods through the development of SignNet and BasisNet, which maintain invariance to sign flips and the basis symmetries of eigenvectors [Lim et al., 2023]. Additionally. another study leveraged the eigenvec- tors of the Magnetic Laplacian to integrate directional infor- mation into SEs [Geisler et al., 2023; Zhang et al., 2021]. Furthermore, an alternative approach utilized the Hodge I-Laplacian spectrum for creating edge-level SEs [Zhou et al., 2024]. On the other hand, the Random Walk-based Structural Encoding (RWSE) has been proposed (Dwivedi et al., 2022a], while direction- and structure-aware SEs for directed graphs based on directional RWs have been developed [Geisler et al., 2023]. In addition, the RRWPs were proposed using RW probabilities and learned relative SEs [Ma et al., 2023a]. This was extended by applying edge-level RWs on a simplicial complex for edge SEs in graphs [Zhou et al., 2024].
2. Related Work
Graph Transformers. Graph Neural Networks (GNNs) have advanced considerably, evolving from MPNNs [Gilmer et al., 2017] to sophisticated GT's. GTss capitalize on Transformers' flexibility and scalability, incorporating SEs to enhance learning from graph data. Notably, NAG- phormer [Chen et al., 2022b], AGT [Ma al., 2023b] and TokenGT [Kim et al., 2022] leverage Laplacian eigenvectors as SEs, demonstrating strong performance in node classi- fication tasks by effectively capturing the global structure of graphs. In addition, the magnetic Laplacian have been explored for SEs, emphasizing the importance of directed graphs [Geisler et al., 2023].
GT models have also evolved to incorporate edge attributes, improving their ability to capture the structural information present in graphs. The Graphormer [Ying et al., 2021] and EGT [Hussain et al., 2022] enhance the self-attention mech- anism by integrating edge attributes, which improve the interaction between node attributes during the learning pro- cess. Moreover, several models have introduced relative SEs
3. Mathematical Background
The Green and Martin kernels are mathematical tools that capture the long-term behavior of RWs on graphs. Specifi- cally, both kernels are functions of node pairs, and from this perspective, we utilize them as absolute relative SEs for GNNs or GTs. When used as SEs, these kernels leverage
'The code is publicly available at https: : //gittb.....//// com/ yoonhuk30 0/ ////E/KKMKKK
2

---

Green and Martin Kernels for Graph Transformers
the RW information that inherently reflects the topological properties of the graph, enabling the model to better capture structural patterns. We begin by describing RWs on grpahs as a stochastic process, focusing on the Green and Martin kernels.
3.2. Green Kernel and Martin Kernel Graphs
In this subsection, we introduce the Green kernel and Martin kernel, which are essential tools in understanding RWs on graphs. The Green kernel represents the expected number of visits from one node to another, while the Martin kernel describes the probability of reaching specific node from another within a finite number of steps. One can formulate both kernels as follows: for x, y E V.
3.1. Random Walk on Graphs as Stochastic Process
Let g = (V)E) be a graph, and let P: :.:V V V - R repre- sent the transition probability kernel of G. that is, p(r,y) denotes the probability that a RW starting at node x moves to node y in the next step. We define p(1) : V x V + I for E N, by performing the convolution of P with itself as follows: for y,y V,
(Green kernel)
G(x, v) = Be (w))] M(r P Puee(s) (w)) < oo], (4)
(3)
(Martin kernel)
where Ly (k) 1 + [0) is the counting function and To 52 + N (0) is the first hitting time map, which are defined follows: for E S
/ p (x,
p0 (x. v)
(1)
k
We note that if G is finite graph with n nodes, P can be represented as an x n matrix defined by = D A, where D is the diagonal matrix with the degrees of the nodes as its diagonal entries, and A is the adjacency matrix of the graph G. In this case, p(0) is the matrix Pt, which is obtained by multiplying P by itself times.
(w) = Σ 1l (x)())));;
(5)
==0 Tu(w) = minffi E NU Xi(w) = =x]
(6)
Both kernels are deeply connected to the underlying struc- ture of the graph, as they reflect important topological prop- erties of the graph [Barlow, 2017: Lyons & Peres, 2017: Broise-Alamichel et al., 2019]. However, it is important to note that the Green and Martin kernels are primarily meaningful in transient graphs where RWs do not return to the starting node infinitely often. In fact, for recurent graph, which is a non- non-transient graph, the value of Green kemnl is always +oo and the value of Martin kernel remains constantly 1.
We define the sequence spaces M(x) C (BL(0) for E V by the set of all sequence w = (Wo, (1o..W..... .) E (NU(0) with wo = I and ([+1 E & for all i E N U {0}, that is, the space of all forward trajectories derived from the RW on G starting from the node æ. We simply denote by Us))s(x)), which is the space of all forward trajectories.
We define the probability measure Pues(()) on ((z) such that, for w U4 E V.
PWER(()) (fw E 2(x)) Wi ui, Vi = 1, 1.......) 1t))
3.3. Adapting Green and Martin Kernels for Recurrent Graphs
k-1
(2)
:= P(a, ui)
II P(u 15+1);
Most graph data in practical applications tends to be recur- rent rather than transient, which makes the computation of the traditional Green and Martin kernels less meaningful. In finite graphs, RWs are recurrent unless there a sink region that terminates the walk (i.e., killed process). This issue arises because the traditional Green and Martin kernels cap- ture the long-term behavior of RWs over infinite time, where RWs repeatedly revisit nodes. To address this limitation, we developed new versions of the Green and Martin kernels by restricting the RW to a finite number of steps. This approach allows us to create new kernels for our proposed SEs, which reflect meaningful RW properties even in recurrent graphs by capturing the behavior over finite horizon.
which means the probability that a RW starting at node x passes through uI,..., Uk in that specific order.
Lastly, we define the set of random variables = : Ω + Veeeuoo by X²(w) w; for all NU and E Q. We intentionally omit further mathematical details, such as o-algebra and precise construction of measure, for the sake of simplicity. For a more detailed explanation, please refer to [Billingsley, 2017].
The triple (I2, (oee X) uniquely determines the RW on a graph. For example, for x, y E V and E N U [0), the probability that a RW starting from will visit y after i step is PwER(z) (X((w) = v)- We note that the transition probability matrix P also uniquely determines the RW. Ob- serve that the kernel (()) represents the probability moving from one node to another node in i steps. In other word, the value (++) (ar, y) is equal to IP (eee (X,(W) = v).
One further issue is that, for all E V, the value of the Martin kernel at (I, x) is always because the RW immedi- ately revisits itself at step O. As a result, even when using the finite-step Martin kernel, the absolute SE consists of constant 1s. To resolve this, we replace the first hitting time
3

---

Green and Martin Kernels for Graph Transformers
map Ty with the first return time map - 12 - N (U(0), (0),
For application GNN models, the GKSE and MKSE used as relative SEs in attention mechanisms message- passing operations. Furthermore, their diagonal components are used as absolute SEs by concatenating or summing them with node features. For more details, please refer to [Black et al., 2024].
which is defined
Te (w) == min MinfieN ENINN X((w) = x). You E S2
(7)
By modifying the definition of the Martin kernel to use the first return time map, the absolute SE reflects the topology of the graph. More specifically, it becomes the probabil- ity that a RW starting from a node returns to itself. This adjustment ensures that the SE reflects more meaningful information about the graph structure. Importantly, the rela- tive SE remains unaffected by this change.
4.2. Computation of finite-step Green and Martin Kernels
In this subsection, we introduce the practical method for calculating the finite-step Green and Martin kernels. While the theoretical definition of the Green and Martin kernels may seem complex, its actual computation can be efficiently performed using recursive approach. In fact, its computa- tion speed is comparable to that of RRWP, with the detailed computation times provided in Appendix B.6.
4. Methodology: Introducing GKSE and MKSE
In this section, we introduce our proposed Green Kernel Structural Encoding (GKSE) and Martin Kernel Structural Encoding (MKSE), which are designed to reflect the theoret- ical significance of the Green and Martin kernels discussed in the previous section. Moreover, these encodings incorpo- rate all the considerations discussed in section 3.3, leading to the development of new mathematical constructs that ef- fectively capture meaningful structural properties of graphs.
Finite-step Green Kernel. The finite-step Green kernel can be calculated using the following recurrence relation: for k E NUNNUU [O).
G = I ((++)) = G
(12)
4.1. Green and Martin Kernel Structural Encodings
where I(x, v) is 1 if = y and O otherwise. Here, x denotes convolution of kernels, which, in the case of finite graph, corresponds to matrix multiplication.
Applying observations in previous section 3.3, we now intro- duce our GKSE and MKSE. First, we define the finite-step Green kernel and finite-step Martin kernel to capture mean- ingful RW behavior within limited number of steps, whose meanings are as follows: for x, y E V and k E ENU(0) (0).
The following theorem shows that the theoretical definition of the finite-step Green kernel (eq. (8)) and its practical computation (eq. (12)) are consistent. The proof is provided in Appendix C.2.
(finite-step Green kernel)
E E 14 (1) (w)]: P. Pwestailyy IT (w)
(8)
Theorem 4.1. For k E [0) and x. y E V, lel G be the sinite-step Green kernel as computed by eq. (12). Then, the following equality holds:
(finite-step Martin kernel)
S k).
(9)
Mathematically, the finite-step Green kernel represents the expected number of visits from one node to another within A steps, while the finite-step Martin kernel approximates the probability of reaching specific node from another within k steps.
(I,)) = Ewen(H) [x)(())]
(13)
where Ewe((,) means the expectation taken with respect to the probability Pwes(e))
Based on these definitions, we construct the GKSE: : V x V + R and MKSE: V V + RK with the dimension
Finite-step Martin Kernel. Before introducing the finite- step Martin kernel, we first observe that the traditional Martin kernel M on graphs is defined by M(x, y) := G(r, v)/G(y y) for x. y. E V. Based on this definition, the finite-step Martin kernel (with the first hitting time map)
K of SE as follows: for y. E V.
GKSB (x. v) = (G (0) (x. v), G (( v)l;
(10)
MKSE (x., ( v), ..... (x, (11)
(() can be computed using the following formula: for x, y E V and i E N U (0).
where (A) and (R) are finite-step Green and Martin ker- nels (eq. (8), eq. (9)), respectively, whose actual formula- tions are described in the section 4.2. These new encodings provide significant structural information while overcoming the limitations of traditional kernels, making them applica- ble to recurrett graphs. It can be easily checked that these SEs are invariant under graph isomorphisms.
(x,
( v) (y,
(14)
To apply the first return time map in the finite-step Martin kernel ((), we use the following modification: for x. y e
4

---

Green and Martin Kernels for Graph Transformers
Vand k [0).
continuous function defined in the definition of constructibil-
ity.
(P M (L (1 (2,
if yi if + (15)
(x,
The following theorem compares the constructilibity of GKSE and MKSE with RRWP.
Theorem 4.3. The following two statements hold:
Although the finite-step Martin kernel computed using eq. (15) may not exactly match the eq. (9), provides a close approximation. The following theorem ensures that this approximation accurate. The proof is provided in Appendix C.4.
1. GKSE and RRWP are mutually constructible, meaning they are equivalent in terms of constructibility.
2. MKSE is not constructible over RRWP, that is, MKSE exhibits unique constructibility properties that are in- dependent of RRWP.
Theorem 4.2. For k E [0) and x, y E let ( be
the finite-step step Martin kernel as computed by eq. (15), Then, the following inequalities hold:
We prove the theorem in generalized RW setting, as stated in Appendix D.2. Furthermore, inspired by [Ma et al., 2023a], we also provides the following results.
1. 0 PEEn(a)lTY Iry (w) (k)))k)M''
(16)
H (r. (x,))
$ G (i(--(10 ((z,9) (v,8)*
(17)
Corollary 4.4. The following two statements hold:
( (I,
2. G(k- (y.9)
$ 1,
1. GKSE can construct the shortest path distance, heat kernel, and graph Laplacian:
P PWER(H) Tr (w) S
(18)
MKSE can construct the shortest path distance and graph Laplacian.
where H (x, BWESSt) (Ty (w); 7g (w) kj Bues(w)) [1 (og (W) T (w]] is the k-step hitting time, meaning the expectation of the first hitting time within k-
We present more general statements in Appendix D.3 with the corresponding proofs provided in Appendix D.4.
steps and 5 is the Dirac function given by 5(x, v) = if and otherwise 0.
4.3.2. EXPRESSIVENESS COMPARISON
In the above theorem, eq. (18) ensures the approximation when & is small, while eq. (17) guarantees the approxima- tion when & is large. In fact, as k becomes large, ( (y, y) increases sublincarly, and for finite graphs, ( (x,8) y) con- verges a specific constant. Consequently, the lower bound in eq. (18) is close 1 when & small, and the upper bound in eq. (17) converges O as l becomes large.
Next, we compare GKSE and MKSE with other SE when they combined with the Generalized Distance Weisfeiler- Lehman test (GD-WL), which is variant of Weisfeiler- Lehman test that uses a distance between nodes to update node colors as follows: for x E V.
X (x) = hash ([(d(z, v), x-)x--(())) : VH). (19)
4.3. Representational Power of GKSE and MKSE
The distance in GD-WL can be chosen from any graph kernel, such as the shortest path distance (SPD). By utilizing GKSE and MKSE as the distance, we obtain the following result. The proof is provided in Appendix D.4.
As we conclude this section, we focus on the representa- tional power of the newly proposed GKSE and MKSE in the theoretical view.
Theorem 4.5. GD-WL with GKSE or MKSE is strictly stronger than GD-WL with SPD.
1. CONSTRUCTIBILITY COMPARISON
We begin by clarifying the concept of constructiblity com- parison between two SEs. We say that SE, constructible over SE₂ if there exists continuous function that transforms SE, into SE2. This concept provides framework to ana- lyze the relationship between SEs in terms of their ability to represent one another.
5. Experimental Results
5.1. Benchmarking of GKSE and MKSE
We evaluate GKSE and MKSE comprehensive suite of graph-level task benchmarks, encompassing three datasets from the Benchmarking GNNs [Dwivedi et al., 2023] and two datasets from the Long-Range Graph Benchmark (LRGB) [Dwivedi et al., 2022b]. In addition to these, we conductee on the larger dataset PCQM4Mv2 from
From practical perspective, if SEs are passed through an MLP before being input into GT, the constructibility relationship between SEs directly reflects their relative rep- resentational power. This is because the MLP acts as the
5

---

Green and Martin Kernels for Graph Transformers
eter choices closely followed those used in the baseline tested in GRIT [Ma al., 2023a], with exceptions made for batch size and RW steps. Detailed hyperparameter con- figurations are provided in the Table 7. The results, pre- sented in the Table 2, indicate that on the Peptides-struct dataset, an 11-task regression benchmark, GRIT+GKSE model achieved the best performance, followed by MKSE and RRWP. On the Peptides-fung dataset, 10-label clas- sification task, GRIT+GKSE and GRIT+MKSE performed comparably to GRIT+RRWP. These findings demonstrate our SEs' proficiency in learning long-range interactions. Notably, the superior performance of GKSE and MKSE on the Peptides-stmn dataset, which uses the same graph struc- tures as Peptides-func, suggests that our SEs are particularly effective in multi-task regression scenarios, outperforming GRIT+RRWP despite its established efficacy in multi-label classification tasks.
Table 1. Test performance on thrce graph-task benchmarks from the Benchmarking GNNs [Dwivedi et al., 2023]. Shown is the
mean + s.d. of 4 runs with different random seeds. Highlighted are the top first, second, and third results.
ZINC
MNIST
CIFAR1O
Model
MAEI
Accuracyt
Accuracy?
GCN
0.367 +: 0.011
90.705 +: 0.218
55.710 +: 0.381
GAT
0,384 +: 0.007
95.535 + 0.205
64.223 1: 0.455
GIN
0,526 + 0.051
96.485 + 0.252
55,255 = 1.527
GraphSAGE
0.398 +: 0.002
97.312 + 0.097
65.767 + 0.308
GatedGCN
0,282 + 0.015
97.340
+ 0.143
67.312 + 0.311
PNA
0,188 +: 0.004
97.940
+: 0.120
70,350 + 0.630
CRaWI
0.085 + 0.004
97.944 + 0.050
69.013 + 0.259
EGT
0,108 +: 0.009
98.173 + 0.087
68.702 + 0.409
GPS
0.070 + 0.004
98.051 + 0.126
72.298 + 0.356
GRIT-RRWP
0.059 + 0.001
98.108 + 0.111
76,468 = 0.881
GRIT&GKSE (ours)
0.058 + 0.002
98.305
+ 0.125
76.718 + 0.919
GRIT+MKSE (ours)
0.056 0.021
98.235 : 0.155
77.365 + 0.640
the Open Graph Benchmark Large Scale Challenge (OGB- LSC) [Hu et al., 2021] to further validate the scalability and effectiveness of our approaches. Furthermore, we evaluate our methods on the Open Circuit Benchmark (OCB) [Dong et al., 2023], the first benchmark specifically designed for the circuit domain. Detailed descriptions of the experimen- tal setup and configurations can be found in Appendix A.
Table 2. Test performance on two benchmarks from the LRGB [Dwivedi et al., 2022b]. Shown is the mean + s.d. of runs with different random seeds. Highlighted are the top first, second, and third results.
Peptides-func
Peptides-struct
Model
APt
MAE/
GCN
0,5930 1: 0,0023
0.3496 : 0.0013
Benchmarking GNNs [Dwivedi al., 2023]. We ini- tially test our methods on three graph-level task bench- mark datasets from the BenchmarkingGNN [Dwivedi et al., 2023]: ZINC, MNIST, and CIFAR10. We primarily com- pare our methods against the SOTA GT model, GRIT [Ma et al., 2023a]. and various baselines described in Ap- pendix A.2. To ensure a fair comparison with prior studies, we adopted experimental settings similar to those in the GraphGPS [Rampášek al., 2022] and GRIT [Ma al., 2023a] papers, maintaining parameter limits of approxi- mately 500K for ZINC and approximately 100K for MNIST and CIFARIO. Detailed hyperparameter configurations are provided in the Table 6. The experimental results are sum- marized in Table 1. In our experiments, GRIT+GKSE achieved SOTA performances on MNIST, and the second- best performances on ZINC and CIFARIO when paired with GRIT+RRWP [Ma al., 2023a]. GRIT+MKSE achieved SOTA performances on ZINC and CIFARIO, and exhibited the second- best performance on MNIST. These findings in- dicate that GKSF, and MKSE can surpass a range of existing methods on small to medium--izee datasets.
GINE
0.5498 = 0.0079
0.3547 = 0.0045
GatedGCN
0.5864 1 0.0077
0.3420 0.0013
GatedGCN+RWSE
0.6069 1 0.0035
0.3357 + 0.0006
GaledGCN+FddyeWSF
0.6002 0.0048
0.2679 0.0015
GatedGCN+HodgelLap
0.5926 + 0.0059
0,2632 = 0.0008
Transformer+appPE
0,6326 1 0.0126
0.2529 1 0.0016
SAN+LapPE
0,6384 1 0.0121
0.2683 1 0.0043
SAN-RWSE
0.6439 + 0.0075
0.2545 = 0.0012
GPS
0.6535 1 0.0041
0.2500 0.0005
GPS+EdgeRWSE
0.6625 0.0042
0,2501
0.0012
GPS ITap
0.6584 0.0033
0.2505
0.0014
GRIT+RRWP
0.6988 + 0.0082
0,2460 = 0.0012
GRIT+GKSE (ours)
0,6976 1 0.0097
0.2452 1 0.0012
GRIT+MKSE (ours)
0.6784 1: 0.0057
0.2457 1 0.0013
PCQM4My2 from OGB-LSC [Hu et al., 2021]. The PCQM4Mv2 dataset [Hu al., 2021], one of the largest molecular datasets available, serves critical benchmark for GTs. Our methods was compared against various base- lines described in Appendix A.2. Given the extensive size of the dataset, we followed the setup of prior studies [Ram- pášek et al., 2022]. Due to time constraints, we did not engage in hyperparameter exploration; instead, we utilized the hyperparameter settings from GraphGPS [Rampášek et al., 2022]. Detailed descriptions of the experimental setup and hyperparameters can be found in Appendix A.1 and Table 7, respectively. We carried out experiments with 4 random seeds to confirm our proposed SEs' performance and found that GRIT+GKSE achieved an MAE of 0.0837, which is much better than previously reported results, as illustrated in the Table 3.
Long-Range Graph Benchmark [Dwivedi al., 2022b]. We further evaluate our methods on two peptide graph benchmarks from the LRGB (Dwivedi et al., 2022b] suite: Peptides-func and Peptides-struct. These benchmarks were selected to test the capability of our methods in capturing long-range dependencies within input graphs. Our meth- ods was compared against various baselines described in Appendix A.2. Our experimental setup and hyperparam-
6

---

Green and Martin Kernels for Graph Transformers
Table 3. Test performance on PCQM4Mv2 benchmark from the
Table 4. Test performance on two benchmarks from the OCB [Dong et al., 2023J. Shown is the mean I s.d. of 4 runs with different random seeds. Highlighted are the top first, second, and third results.
OCB-LSC [Hu et al., 2021J. Shown is the result of single run, excluding experiments with GKSE and MKSE, which consists of 4 runs with different random seeds. Highlighted are the top first, second, and third results.
Ckt-Bench101
Ckt-Bench301
Model
Model
MAE 4
Param
MAET
MAE
GCN
0.1379
2.0M
GCN
0.0801 + 0.0017
0.0584 + 0.0006
GCN-virtual
0.1153
4.9M
GAT
0.0719 + 0.0012
0.0583 + 0.0016
GIN
0.1195
3.8M
GIN
0.0691 + 0.0011
0.0528 + 0.0004
GIN-virtual
0.1083
6.7M
GraphSAGE
0.0662 + 0.0004
0.0545 + 0.0005
GatedGCN
0.0668 + 0.0006
0.0527 + 0.0004
TokenGT (ORF)
0.0962
48.6M
TokenGT (Lap)
0.0910
48.5M
GPS+LapPE
0.0440 + 0.0011
0.0199 + 0.0004
GRPE
0.0890
46.2M
GRIT-DAGPE
0.0444 - 0.0011
0.0240 + 0.0004
EGT
0.0869
89.3M
GRIT+RRWP
0.0418 + 0.0021
0.0190 + 0.0005
Graphormer
0.0864
48.3M
GRIT+GKSE (ours)
0.0395 + 0.0033
0.0188 + 0.0004
Specformer-medium
0.0916
4.1M
GRIT+MKSE (ours)
0.0409 + 0.0016
0.0192 + 0.0004
GPS-small
0.0938
6.2M
GPS-medium
0.0858
19.4M
GRIT-RRWP
0.0859
16.6M
GRIT+GKSE (ours)
0.0837 +: 0,0002
11,8M
graphs and observed that GKSE and MKSE, compared to RRWP, represents these features in fundamentally different ways.
GRIT-MKSE (ours)
0.0839 + 0.0002
11.8M
First, the molecular graph dataset is characterized by a large number of substructures, such as hexagonal benzene rings. In Figure 1, we visualize three SE values, RRWP, GKSE, and MKSE, on the fluorescein molecule graph. For RRWP. the edges with higher RRWP values form hexagons when k is odd, on the other side they form a star shape when k is even. This phenomenon arises because the hexagonal subgraph is non-aperiodic. In fact, transition probabilities on non operioiio graphs oscillate indefinitely. Mathemat- ical details supporting this stability are provided in Ap- pendix D.1. In contrast, our proposed SEs provide more stable and consistent representations under non-aperiodic structures, accurately reflecting the original graph structures, as illustrated in Figure 1 and Figure 3. Based on our ex- perimental results, we hypothesize that the stability of our proposed SFs in handling non-aperiodic substructures con- tributes to their improved performance. Related indirect experimental evidence can be found in Appendix B.4. How- ever, as our experimental results address only limited set of cases, they do not serve definitive evidence confirm our assumptions. Thus, further observations and theoretical investigations are necessary to substantiate this hypothesis and gain deeper insights into the underlying mechanisms.
Open Circuit Benchmark [Dong et al., 2023]. We con- duct experiments using our methods on two datasets from the OCB [Dong et al., 2023], specifically Ckt-Bench 101 and Ckt-Bench301. These datasets represent the first ana- log circuit benchmarks modeled as DAGs. In our eval- uation, we compared our methods against various base- lines described in Appendix A.2. Detailed information on dataset preparation and the experimental hyperparameters can be found in Appendix A.1 and Table 8, respectively. As shown in Table 4, the GT models outperformed the MPNNs, with GRIT+GKSE achieving the best results and GRIT+MKSE achieving the second-best results or compara- ble with GRIT+RRWP. We also conducted sensitivity anal- ysis on the choice of K values, with the results provided in Appendix B.3. These results suggest that GKSE and MKSE are highly effective on datasets modeled as DAGs, further demonstrating their versatility and robustness in various graph structures.
5.2. Analysis of Experimental Results
Our proposed SEs showed strong performance on 7 out of 8 benchmarks, with superior performance on regres- sion tasks compared to classification tasks. In particular, our proposed SEs outperformed on PCQM4Mv2 and Ckt- Bench101, which we attribute the advantage of our pro- posed approaches in encapsulating graph structural infor- mation more effectively than existing SEs in certain graphs. We have explored which properties of our proposed SEs contribute to the improvement in performance compared with another RW-based SE, specifically RRWP. We inves- tigated the unique characteristics of molecule and circuit
Second, our proposed SEs also demonstrate strong perfor- mance on datasets with DAG structures, such as OCB, which is common in the circuit domain. In DAGs, RWs terminate after finite number of steps due to the inability return to previously visited nodes, leading to sparse representa- tions when using RRWP-especially for values of K that are larger than diameter of the graph. This sparsity can weaken the representational power of the graph structure. Indeed, in datasets where graph samples have varying diameters,
7

---

Green and Martin Kernels for Graph Transformers
k=1
k=2
k=3
k=4
k=5
RRWP
GSKE
MKSE
Figure 1. Visualization of RRWP, OKSE, and MKSE fluorescein molecule graph for k-steps ranging from to 5. In each graph. the thickness and color intensity of the edges represent the magnitude of the corresponding SE values, with higher values indicated by thicker and darker edges.
k=1
k=2
k=3
k=4
k=5
RRW
GKSE
Figure 2. Visualization of RRWP and GKSE on a OCB graph sample for k-steps ranging from to 5. In each graph, the thickness and color intensity of the edges represent the magnitude of the corresponding SE values, with higher values indicated by thicker and darker edges.
fixed hyperparameter K may fit well for some samples but result in overly sparse SEs for others with low diame- ters. Related indirect experimental evidence can be found in Appendix B.5. Such imbalance can negatively affect overall learning performance. However, our proposed SEs maintain consistent representations even for large K, making it suitable for capturing the structural information of DAGs, as shown in Figure 2. This enhanced efficacy directed graphs can be attributed to the intrinsic properties of the SEs.
6. Conclusion
In this work, we introduced novel SEs, GKSE and MKSE, to expedite GTs by leveraging theoretical insights into the Green and Martin kernels within graph data. These en- codings provide a foundational approach to extending RW- based methods, enhancing the expressiveness and efficiency of GTs. Our proposed SEs demonstrated significant im- provements across multiple benchmarks, demonstrating strong performance in 7 out of 8 tasks. These results confirm that our methods not only achieve superior performance but also effectively represent both molecular and circuit data, aligning with our theoretical analyses. The ability of GKSE and MKSE to capture unique structural features across diverse graph domains suggests promising directions for future research. We plan to further explore these capa- bilities to develop more expressive SEs with theoretically provable properties and to design model architectures that
Overall, we infer that our proposed SEs are particularly beneficial for regression tasks involving non-aperiodic sub- structures or DAGs. The performance advantage of GKSE and MKSE be attributed their ability to effectively capture intricate structural details in such graphs, thereby enhancing the learning capabilities of GTs across diverse applications.
8

---

Green and Martin Kernels for Graph Transformers
fully leverage this enhanced expressiveness. By providing deeper understanding of the underlying kernels and prac- tical approach to improve GTs, this study contributes to the advancement of graph representation learning. It paves the way for developing more sophisticated and capable GT models in future research.
Bresson, X. and Laurent, T. Residual gated graph convnets.
arXiv preprint arXiv:1711.07555 2017.
Broise-Alamichel, A., Parkkonen, J., and Paulin, F. Equidistribution and counting under equilibrium states negative curvature and trees. Springer. 2019.
Chen, D., O'Bray, L., and Borgwardt, K. Structure- aware transformer for graph representation learning. International Conference on Machine Learning, pp. 3469-3489. PMLR, 2022a.
Impact Statement
We contribute to the technological progress in the domain of electronic design automation, which is very important but still underrepresented in terms of graph representation learning (GRL) techniques, by developing new SEs. As a general GRL method, we do not expect any negative soci- etal consequences in the immediate future, but we believe that thorough validation is needed in areas such drug discovery and computational biology.
Chen, J., Gao, K., Li, G., and He, K. Nagphormer: A tokenized graph transformer for node classification in large graphs. arXiv preprint arXiv:2206.09910, 2022b.
Chung, F. and Yau, S.-T. Discrete green's 's functions. Journal of Combinatorial Theory, Series A. 91(1-2):1912114 2000.
References
Corso, G., Cavalleri, L., Beaini, D., Liò, P., and Veličković, P. Principal neighbourhood aggregation for graph nets. Advances in Neural Information Processing Systems, 33: 13260-13271, 2020.
Alon, U. and Yahav, E. On the bottleneck of graph neural networks and its practical implications. arXiv preprint arXiv:2006.05205, 2020.
Dong, Z., Cao, W., Zhang, M. Tao, D., Chen, Y., and Zhang, X. Ckignn: Circuit graph neural network for electronic de- sign automation. arviv preprint arXiv:2308. 16406, 2023.
Barceló, P., Kostylev, E. V., Monet, M., Pérez, J., Reutter, J., and Silva, J.-P. The logical expressiveness of graph neural networks. In 8th International Conference on Learning Representations (ICLR 2020), 2020.
Dosovitskiy, A., Beyer, L., Kolesnikov, A., Weissenbor, D., Zhai, X., Unterthiner, T., Dehghani, M., Minderer, M., Heigold, G., Gelly, S., et al. An image is worth 16x16 16 Transformers for image recognition at scale. arXiv preprint arXiv:2010.11922 2020.
Barlow, M. Random walks and heat kernels on graphs volume 438. Cambridge University Press, 2017.
words:
Beaini, D., Passaro, S., Létourneau, V., Hamilton, W., Corso, G., and Liò, P. Directional graph networks. In International Conference on Machine Learning, pp. 748- 758. PMLR, 2021.
Dwivedi, V. P. and Bresson, X. A generalization of transformer networks to graphs. arXiv preprint arXiv:2012.09699, 2020.
Bevilacqua, B., Frasca, F., Lim, D., Srinivasan, B., Cai, C., Balamurugan, G., Bronstein, M. M., and Maron, H. Equivariant subgraph aggregation networks. arXiv preprint arXiv:2110.02111 2021.
Dwivedi, V. P., Luu, A. T., Laurent, T., Bengio, Y., and Bresson, X. Graph neural networks with learn- able structural and positional representations. In International Conference Learning Representations, 2022a. URL https: / /wpp/reveeeeeeeeeeeeeeeeeee net forum? i dd=TTT jnvGphy.
Billingsley, Probability and measure, John Wiley Sons, 2017.
Dwivedi, V. P., Rampášek, L., Galkin, M.. Parviz, A., Wolf, G., Luu, A. T., and Beaini, D. Long range graph benchmark. Advances in Neural Information Processing Systems, 15:22326-223442 2022b.
Black, M., Wan, Z., Mishne, G., Nayyeri, A., and Wang, Y. Comparing graph transformers via positional encodings. arXiv preprint 2422 2024.
Bo, D., Shi, C., Wang. L., and Liao, R. Specformer: Spectral graph neural networks meet transformers. arXiv preprint arXiv:2303.0100 2023.
Dwivedi, P., Joshi, C. K., Luu, A. T., Laurent, T., Bengio, Y., and Bresson, X. Benchmarking graph neural net- works. Journal of Machine Learning Research, 24(43): 1-48, 2023.
Brandes, U. On variants of shortest- path betweenness cen- trality and their generic computation. Social networks, 30(2):136-15) 2008
Evans, C. Partial differentiall equations, volume 19,
American Mathematical Society, 2022.

---

Green and Martin Kernels for Graph Transformers
Fey, M. and Lenssen, J. E. Fast graph representa- tion learning with pytorch geometric. arXiv preprint arXiv: 1et..09990.228... 2019.
Advances in Neural Information Processing Systems, 35:
14582-14595, 2022.
Kipf, T. N. and Welling, M. Semi-supervised classifica- tion with graph convolutional networks. arXiv preprint Xiv: 1 009907, 2016.
Geisler, S., Li, Y., Mankowitz, D. J., Cemgil, A. T., Gün- nemann, S., and Paduraru, C. Transformers meet di- rected graphs. In International Conference on Machine Learning, pp. 11 11144-1111 11172. PMLR, 2023.
Kreuzer, D., Beaini, D., Hamilton, W., Létourneau, V., and
Tossou, P. Rethinking graph transformers with spectral attention. Advances in Neural Information Processing Systems, 34:21618-21629, 2021.
Gilmer, J., Schoenholz, S. S., Riley, P. F., Vinyals, O., and Dahl, G. E. Neural message passing for quantum chem- istry. International conference on machine learning,
pp. 1263-1272. PMLR, 2017.
Li, P.. Wang, Y., Wang, H., and Leskovec, J. Distance en- coding: Design provably more powerful neural networks for graph representation learning. Advances in Neural Information Processing Systems, 33:4465 4478, 2020.
Goh, K.-I., Kahng, B., and Kim, D. Universal behavior of load distribution in scale-free free networks. Physical review letters, 87(27)2278701, 2001.
Lim, D., Robinson, J. D., Zhao, L., Smidt, T., Sra, S., Maron, H., and Jegelka, Sign and basis invariant networks for spectral graph representation learning. In The Eleventh International Conference Learning Representations, 2023. URL https: /twp////ppeeeeeeeeeeeepeeeeeeeee setpenreview.net/Eeee net. forum? ##=0-UHqMrzzil
Hagberg, A.,
Swart, P., and S Chult, D. Exploring net- work structure, dynamics, and function using networkx. Technical report, Los Alamos National Lab(LANL), Los Alamos, NM (United States), 2008.
Hamilton, W., Ying, Z., and Leskovec, J. Inductive repre- sentation learning on large graphs. Advances in neural information processing systems, 30, 2017.
Lim, D., Robinson, J., Jegelka, S., and Maron, H. Expressive sign equivariant networks for spectral geometric learning. Advances in Neural Information Processing Systems, 36, 2024.
Hornik, K., Stinchcombe, M., and White, H. Multi- layer feedforward networks are universal approximators. Neural networks, 2(5):359-366, 1989.
Loshchilov, and Hutter, F. Decoupled weight decay regu- larization. arXiv preprint urXiv:1711.051 2017.
Hu, W., Liu, B., Gomes, J., Zitnik, M., Liang, P., Pande, V., and Leskovec, J. Strategies for pre-training graph neural networks. arXiv preprint arXiv: 12265, 2019.
Luo, Y., Thost, V., and Shi, L. Transformers over di- rected acyclic graphs. Advances in Neural Information Processing Systems, 36, 2024.
Hu, W., Fey, M. Ren, H., Nakata, M. Dong, Y., and Leskovec, J. Ogb-lsc: A large-scale challenge for machine learning on graphs. arXiv preprint arXiv:2103.09430, 2021.
Lyons, R. Equivalence of boundary measures on covering trees of finite graphs. Ergodic Theory and Dynamical Systems, 14(3):575-597, 1994.
Hussain, M. S., Zaki, J., and Subramanian, D. Global self-attention replacement for graph convolution. In Proceedings of the 28th ACM SIGKDD Conference Knowledge Discovery and Data Mining, pp. 655-665, 665, 2022.
Lyons, R. and Peres, Y. Probability trees and networks, volume 42. Cambridge University Press, 2017.
Ma, L., Lin, C., Lim, D., Romero-Soriano, A., Dokania, P. K., Coates, M., Torr, P., and Lim, S.-N. Graph in- ductive biases transformers without message passing. International Conference on Machine Learning, pp. 23321-23337 PMLR, 2023a.
Irwin, J., Sterling, T., Mysinger, M. M., Bolstad, S., and Coleman, R. G. Zine: free tool to discover chemistry for biology. Journal of chemical information and modeling, 52(7):1557-1768, 2012.
Ma, L., Pal, S., Zhang, Y., Zhou, J., Zhang, Y., and Coates, M. Ckgconv: General graph convolution with continuous kernels. arXiv preprint arXiv:2404.1366 2024.
Johnson, S., Domínguez V., Donetti, I.., and Muñoz, M. A. Trophic coherence determines food-web stability. Proceedings of the National Academy of Sciences, 111 (50): 799119192-7988 2014.
Ma, X., Chen, Q., Wu, Y., Song, G., Wang, L., and Zheng,
B. Rethinking structural encodings: Adaptive graph trans- former for node classification task. In Proceedings of the ACM Web Conference 2023, pp. 533-544, 2023b.
Kim, J.. Nguyen, D., Min, S., Cho, S., Lee, M., Lee, H., and Hong, S. Pure transformers are powerful graph learners.
10

---

Green and Martin Kernels for Graph Transformers
Min, E., Chen, R., Bian, Y., Xu, T., Zhao, K., Huang, W., Zhao, P., Huang, J., Ananiadou, S., and Rong. Y. Trans- former for graphs: An overview from architecture per- spective. arXiv preprint arXiv:2202.08455, 2022.
Tsuji, M. Potential theory in modern function theory. Maruzen, 1959.
Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A. N., Kaiser, E., and Polosukhin, At- tention is all you need, Advances in neural information processing systems, 30, 2017.
Morris, C., Ritzert, M., Fey, M., Hamilton, W. L.,, Lenssen, J. E., Rattan, G., and Grohe, M. Weisfeiler and le- man neural: Higher-order graph neural networks. In Proceedings of the AAAI conference on artificial intelligence, volume 33, pp. 4602-4609, 2019.
Velickovic, P., Cucurull, G., Casanova, A., Romero, A., Lio, P., Bengio, Y., et al. Graph attention networks. stat, 1050 1205:00-4850, 2017.
Müller, L., Galkin, M.. Morris, C., and Rampášek, L. Attending to graph transformers. arXiv preprint arXiv:2302.04181, 2023.
Woess, W. Random walks on infinite graphs and groups. Number 138. Cambridge university press, 2000.
Oono, K. and Suzuki, T. Graph neural networks exponen- tially lose expressive power for node classification. arXiv preprint arXiv: 190.: 2019.
Xu, H. and Yau, S.-T. Discrete green's functions and ran- dom walks graphs. Journal of Combinatorial Theory, Series A, 120(2):483-499) 2013.
Park, W., Chang, W., Lee, D., Kim, J., and Hwang, S.-w. Grpe: Relative positional encoding for graph transformer. arXiv preprint arXiv:2201.1278)) 2022.
Xu, K., Hu, W., Leskovec, J., and Jegelka, S. How powerful are graph neural networks? arXiv preprint arxiv: 1xXiv:8110000 810.00886. 2018.
Paulin, F., Pollicott, M., and Schapira, B. Equilibrium states in negative curvature. arXiv preprint arXiv: 1,642, 2012.
Ying, C., Cai, T., Luo, S., Zheng, S., Ke, G., He, D., Shen, Y., and Liu, T.-Y. Do transformers really perform badly for graph representation? Advances in neural information processing systems, 14-28877-288888 2021.
Rampäšek, L., Galkin, M., Dwivedi, V. P. Luu, A. T., Wolf, G., and Beaini, D. Recipe for a general, powerful, seal- able graph transformer. Advances in Neural Information Processing Systems, 35:1 15:14501-14515 2022.
You, J., Ying, Z.., and Leskovee, J. Design space for graph neural networks. Advances Neural Information Processing Systems, 11177009-17220 2020.
Rusch, T. K., Bronstein, M. M., and Mishra, S. A survey on oversmoothing in graph neural networks. arXiv preprint arXiv:2303.10999, 2023.
Zhang, X., He, Y., Brugmone, N., Perlmutter, M., and Hirn, Magnet: neural network for directed graphs. Advances in neural information processing systems, 34: 27003 2021.
Singh, S., Chaudhary, K., Dhanda, K., Bhalla, S., Usmani, S. S., Gautam, A., Tuknait, A., Agrawal, P., Mathur, D., and Raghava, G. P. Satpdb: database of structurally annotated therapeutic peptides. Nucleic acids research, 44(DI)D1119-DII 2016.
Zhou, C., Wang, X., and Zhang. M. Facilitating graph neural networks with random walk on simplicial complexes. Advances in Neural Information Processing Systems, 36, 2024.
Strang, G. Linear algebra and its applications. 2012.
Sun, Q., Li, J., Yuan, H., Fu, X., Peng, H., Ji, C., Li, Q., and Yu, P. S. Position-aware structure learning for graph topology-imbalance by relieving under-reaching and over- squashing. In Proceedings of the 31st ACM International Conference on Information & Knowledge Management, pp. 18548-857,10 2022.
Toenshoff, J., Ritzert, M., Wolf, H., and Grohe, M. Graph learning with 1 convolutions on random walks. arXiv preprint arXiv:2102.08786, 2021.
Topping, J., Di Giovanni, F., Chamberlain, B. P., Dong, X., and Bronstein, M. M. Understanding over-squashing and bottlenecks on graphs via curvature. arXiv preprint arXiv:2111.14522 2021.

---

Green and Martin Kernels for Graph Transformers
A. Experimental Details
A.1. Description of Benchmark Datasets
A detailed overview of the statistical properties and characteristics of the benchmark datasets is presented in Table 5. The initial five datasets are sourced from the Benchmarking [Dwivedi et al., 2023], followed by the subsequent two from the LRGB [Dwivedi al., 2022b], one dataset in the middle is from the OGB-LSC [Huu et al., 2021], and the final two datasets are provided by the OCB [Dong et al., 2023].
Table 5. Overview of the graph learning benchmark datasets used in this study [Dwivedi et al., 2023; 2022b; Hu et al., 2021; Dong al., 2023]
Avg. # nodes
Avg. edges
Prediction
Prediction
Dataset
Graphs
Directed
Metric
level
task
ZINC
12,000
23.2
24.9
graph
regression
Mean Abs. Error
MNIST
70,000
70.6
564.5
Yes
graph
10-elass classification
Accuracy
CIFARIO
60,000
117.6
941.1
Yes
graph
10-class classification
Accurucy
PATTERN
14,000
118.9
3,039.3
No
inductive node
binary classification
Weighted Accuracy
CLUSTER
12,000
117.2
2,150.9
No
inductive node
6-class classification
Weighted Accuracy
Peptides-fund
15,535
150.9
307.3
No
graph
10-task classification
Avg. Precision
Peptides-struct
15,535
150.9
307.3
No
graph
11-task regression
Mean Abs. Error
PCQM4My2
3.746.620
14.1
14.6
graph
regression
Mean Abs. Error
Ckt- 11--Bench111 101
10,000
9.6
14.5
Yes
graph
regression
Mean Abs. Error
Ckt-Bench301 47,248
9.9
15.5
Yes
graph
regression
Mean Abs. Error
ZINC [Dwivedi et al., 2023] comprises 12,000 molecular graphs sampled from the ZINC database [Irwin et al., 2012] of commercially available chemical compounds. These molecular graphs contain between and 37 nodes, where each node corresponds to heavy atom from one of 28 possible atom types, and each edge represents one of three possible bond types. The task associated with this dataset is to predict molecular property known constrained solubility (logP). The dataset is provided with a predefined split of 10,000 training. 1,000 validation, and 1,000 test samples.
MNIST and CIFARIO [Dwivedi et al., 2023] are derived from their corresponding classical image classification datasets by constructing 8 nearest- heirestt graphs of SLIC superpixels for each image. The resulting graphs contain 40-75 nodes for MNIST and 85-150 nodes for CIFARIO. The 10-class classification tasks and standard dataset splits mirror the original image classification datasets, specifically 55K/5K/10K for MNIST and 45K/5K/10K for CIFAR1O in terms of rrain/vaiiatiiontess graphs. These datasets serve as sanity checks, with most GNNs expected achieve near 100% accuracy for MNIST and perform sufficiently well for CIFARIO.
PATTERN and CLUSTER [Dwivedi et al., 2023] are synthetic datasets derived from a probabilistic block model, specifically designed for inductive node-level classification tasks. In the PATTERN dataset, the objective is to identify nodes that belong to one of 100 possible subgraph patterns. These patterns are randomly generated using different Stochastic Block Model (SBM) parameters from the rest the graph. the CLUSTER dataset, each graph is divided into six clusters, all generated using the same SBM distribution. Within each cluster, only one node has unique cluster ID. The task is to determine the cluster ID for each node based on the structure of the graph.
Peptides-func and Peptides-struct [Dwivedi et al., 2022b] datasets consist of atomic graphs of peptides. Derived from a collection of 15,535 peptides encompassing total of 2.3 million nodes from SATPdb [Singh et al., 2016], these two datasets share the same set of graphs but differ in their prediction tasks. In the Peptides-func dataset, the task is to classify each graph into one or more of 10 non-exclusive peptide functional classes. In the Peptides regress 11 distinct 3D structural properties of the peptides. These graphs are designed to require inference of long-range interactions (LRI) for robust performance. With an average of 150.9 nodes per graph and a mean graph diameter of 57, they provide challenging benchmark for GT's and other GNNs aimed at capturing LRIs.
dataset, the goal is to
PCQM4Mv2 [Hu et al., 2021] dataset is an extensive graph regression benchmark comprising almost 3.7 million molecular graphs. The objective is to predict the HOMO-LUMO gap, quantum mechanical property computed using Density Functional Theory. The true labels for the original "test-dev" and "test-challenge" dataset splits are withheld by the OGB-LSC challenge organizers to ensure the integrity of the competition. Thus, we utilized the original validation set as our test set, excluding 150,000 randomly selected molecules to refine the validation process. This adjustment ensures rigorous
12

---

Green and Martin Kernels for Graph Transformers
evaluation while maintaining consistency with the dataset's intended use in benchmarking advanced GNN models.
Ckt-Bench101 and Ckt-Bench301 [Dong et al., 2023] are pioneering datasets in the circuit domain, specifically designed for optimizing both analog circuit topologies and device parameters. 1kttBench1011 comprises 10,000 operational amplifier (OpAmp) circuits, each topology represented as a directed acyclic graph (DAG). Ckt-Bench301 includes 47,248 OpAmp circuits, after excluding 2,752 invalid simulation results from the original 50,000 entries. For regression tasks, performance metrics for these circuits have been meticulously extracted using a circuit simulator. The OCB dataset provides critical performance metrics such as gain, bandwidth, phase margin, and a figure of merit (a composite metric of these parameters) as labels. The OCB dataset provides both subgraph-level and node-level graphs for CkIGNN, a nested-GNN leveraging domain-specifee knowledge of circuits. In this study, we focused on extracting node-level graph information and organizing the data for use within the GraphGPS framework [Rampášek et al., 2022]. Each node in the dataset has node attributes of a circuit device, annotated with device-specific types and feature values, including resistance r, capacitance and transconductance 9m- Due to the lack of inherent edge attribute values in the domain, we introduced a three-dimensionss edge feature vector derived from the structural properties of the graphs. These features include edge betweenness [Brandes, 2008), edge load centrality [Goh et al., 2001; Hagherg et al., 2008], and trophic differences [Johnson et al., 2014], all computed using NetworkX [Hagberg et al., 2008J. The preprocessed Ckt-Bench101 and Ckt-Bench301 datasets are provided in the github (https:/ / / /gi thub. com/ www//oom/////eeeeec/
COS////KSEEEESSS for further research.
A.2. Baselines
Comparison for the BenchmarkingGNNs,, we benchmark our approaches against several widely used GNN models, including prominent MPNNs and leading GNNs (GCN [Kipf & Welling, 2016), GAT [Velickovic et al., 2017], GIN [Xu et al., 2018),
GraphSAGE (Hamilton et al., 2017], GatedGCN [Bresson & Laurent, 2017], PNA [Corso et al., 2020], CRaW1 1 [TTeeshofff et al., 2021]); and GTs with various PE and SE ( EGT [Hussain et al., 2022], GraphGPS [Rampášek et al., 2022], GRIT [Ma et al.. 2023a]). Comparison for the LRGB, we compare our methods against various MPNNs with several PESE (GCN [Kipf & Welling, 2016]. GINE [Hu et al., 2019], GatedGCN [Bresson & Laurent, 2017]) as well as several GTs (Transformer [Vaswani et al., 2017], SAN [Chen et al., 2022a], GraphGPS [Rampášek et al., 2022], and GRIT [Ma et al., 2023a], EdgeRWSE, and Hodge Iapp [Zhou et al., 2024J). Comparison for the PCQM4Mv2, our methods was compared against two MPNNs with and without virtual nodes (GCN [Kipf& & Welling, 2016), GIN [Xu et al., 2018)) as well several GTs (TokenGT [Kim et al., 2022], GRPE [Park et al., 2022], EGT [Hussain et al., 2022], Graphormer [Ying et al., 202 1], Specformer [Bo et al., 2023], GraphGPS [Rampášek et al., 2022], and GRIT [Ma et al., 2023al). Comparison for the OCB, we compare our methods against various MPNNs (GCN [Kipf& & Welling, 2016], GAT [Velickovic et al., 2017]. GIN [Xu et al., 2018], GraphSAGE [Hamilton et al., 2017], GatedGCN [Bresson & Laurent, 2017]) as well as two prominent GTs (GraphGPS [Rampášek et al., 2022], GRIT [Ma et al., 2023a]). We also implemented directed acyclic graph positional encodings (DAGPE) [Luo et al., 2024] as a baseline of DAG. This comprehensive comparison ensures a robust assessment of our methods relative performance across diverse graph benchmarks.
A.3. Dataset Splits and Random Seeds
For the datasets under evaluation, we adhere to the standard train//aliddaiinntest splits established by the benchmarks. We conduct four experimental runs on each dataset, utilizing distinct random seeds (0, 1, 2. 3). We then report both the mean performance and the standard deviation across these runs to ensure the robustness and reproducibility of our results.
A.4. Hyperparameter Settings
Due to constraints in time and computational resources, an exhaustive or grid search for hyperparameters was not conducted. Instead, we primarily adhered the hyperparameter settings of GraphGPS [Rampášek et al., 2022], making minor adjustments where necessary to align with commonly used parameter budgets. For benchmarking various datasets, we adhered to the standard parameter budgets widely accepted in the literature [Dwivedi et al., 2023; 2022b]. Specifically, we used a maximum of 500K parameters for the ZINC, PATTERN, CLUSTER, Peptides-func, and Peptides-struee datasets. For the MNIST and CIFAR1O datasets, the parameter budget was capped at 100K parameters. Across all experiments, we utilized the Adam W optimizer [Loshchilov & Hutter, 2017] with default settings of 31 0.9, 82 = 0.999, and c = 10-8 same the GraphGPS [Rampášek et al., 2022]. The learning rate schedule featured a linear "warm-up" phase at the beginning of training, followed by a cosine decay. The duration of the warm-up period, the base learning rate, and the total number of epochs were tuned for each dataset. The final hyperparameter configurations are detailed in Tables 6, 7, and 8.
13

---

Green and Martin Kernels for Graph Transformers
Table 6. Hyperparameters of GKSE and MKSE for five benchmarks from the BenchmarkingGNNN: [Dwivedi al., 2023]
Category
Hyperparameter
ZINC
MNIST
CIFARIO
PATTERN
CLUSTER
# Transformer Layers
10
3
3
10
16
Hidden dim # Heads
64
52
52
48
8
4
4
8
GTs
Dropout
0
0
0
0.01
Atlention dropout
0.5
0.5
0.5
Graph pooling
sum
mean
mean
Batch size
32
16
8
32
16
Learning Rate
0.001
0.001
0.001
0.0005
0.001
Training
# Epochs
2000
200
200
100
100
# Warmup epochs Weight decay
50
5
5
5
5
le-5
le-5
le-5
1e-5
le-5
ksteps (RW-steps)
19
18
17
26
40
GKSE
PE encoder # Parameters
linear
linear
linear 99,382
linear
linear
473,217
102,138
478,593
432,438
ksteps (RW-steps) PE encoder # Parameters
18
16
17
MKSE
linear
linear
linear 99,382
linear 477,057
linear
473,089
101,930
432,534
Table Hyperparameters of GKSE and MKSE for benchmarks from the LRRGB [Dwivedi al., 20226] and PCQM4Mv2 benchmark from the OGB-LSC [Hu et al., 2021]
Category
Hyperparameter
Peptides-func
Peptides-struct
PCQM4Mx2
# Transformer Layers
4
4
16
Hidden dim
96
96
256
# Heads
4
8
8
GTs
Dropout
0
0
0.1
Attention dropout
0.5
0.5
0.1
Graph pooling
mean
mean
mean
Batch size
8
32
256
Learning Rate
0.0003
0.0003
0.0002
Training
# Epochs
200
200
150
# Warmup epochs Weight decay
5
5
10
0
0
0
ksteps (RW-steps)
26
24
16
GKSE MKSE
PE encoder # Parameters
linear
linear
linear
445,162
449,579
11.8M
B. Supplementary Experiments
B.I. Experiments inductive node-level task
We our methods on two inductive node-level classification task benchmark datasets from the Benchmarking- GNN [Dwivedi al., 2023]: PATTERN and CLUSTER. We primarily compare methods against the SOTA GT model, GRIT [Ma et al., 2023a), and various baselines described in Appendix A.2. To ensure a fair comparison with prior studies, we adopted experimental settings similar to those in the GraphGPS [Rampášck et al., 2022] and GRIT [Ma et al., 2023a] papers, maintaining parameter limits of approximately 500K for both datasets. Detailed hyperparameter configurations are provided the Table 6. The experimental results show that except for GRIT+GKSE performing well on the PATTERN dataset, the other results are slightly lower of comparable to the GRIT+RRWP summarized in Table 9. We
14

---

Green and Martin Kernels for Graph Transformers
Table Hyperparameters of GKSE and MKSE for benchmark datasets from the Open Cireuit Benchamark [Dong al., 2023]
Category
Hyperparameter
Ckt-Bench101
Ckt-Bench301
# Pre Message Passing Layers
2
# Message Passing Layers
2
# Post Message Passing Layers Hidden dim
1
MPNNs
64
64
Dropout
0
0
Aggregation
mean
mean
# Transformer Layers
10
10
Hidden dim
64
64
# Heads
8
8
GT's
Dropout
0
0
Attention dropout
0.2
0.2
Graph pooling
mean
mean
Batch size
32
64
Learning Rate
0.001
0.001
Training
# Epochs
200
200
# Warmup epochs Weight decay
5
le-5
le-5
GPS-MPNN GPS-GlobAttn
GINE
GINE
Transformer
Transformer
PE PE dim
LapPE
LapPE
GPS
8
PE encoder
DeepSet
DeepSet
RRWP
ksteps (RW-steps)
18
21
GKSE
PE encoder # Parameters
linear
linear
MKSE
471,745
472,129
Table Test performance on two inductive node-level task benchmarks from Benchmarking GNNs. Shown is mean d: s.d. runs with different random seeds. Highlighted the top first, second, and third results.
PATTERN
CLUSTER
Model
W. Accuracyt
W. Aceurayy
GCN
71.892 + 0.334
68.498 + 0,976
GAT
78.271 + 0.186
70.587 + 0.447
GIN
85.387 + 0.136
64.716 + 1.553
GraphSAGE
50.492 = 0.001
63.844 = 0.110
GatedGCN
85.568 = 0.088
73.840 0.326
SAN
86.581 + 0.037
76.691 + 0.065
EGT
86.821 + 0.020
79.232 = 0.348
GPS
86.685 + 0.059
78.016 + 0.180
GRIT+RRWP
87.196 + 0.076
80.026 + 0.277
GRIT+GKSE (ours)
87.328 + 0.216
79.858 + 0.034
GRIT+MKSE (ours)
87.150 + 0.194
79.729 + 0.145
believe this is partly due to the high average number of edges in graphs of PATTERN and CLUSTER. The dense connectivity in these datasets may hinder the ability of RWs to represent structural nuances effectively. Additionally, the synthetic nature of the datasets, derived from SBM with specific patterns and clustring tasks, might require alternative encoding strategies better suited for dense graphs and node-level classification.
15

---

Green and Martin Kernels for Graph Transformers
B.2. Experiments CKGConv architecture
To provide further evidence of the broad applicability of our SEs, we have integrated them into the recently accepted CKGCN model [Ma al., 2024]. Using the authors' publicly available code repository and configurations, conducted experiments five benchmarks. For the ckt-benchl01 and ckt-bench301 datasets, used the configurations described in our paper. As the results indicated in Table 10, integrating our SEs into CKGCN led to performance improvements on all datasets except CIFARIO. These findings suggest that our SEs can enhance models beyond GRIT.
Table 10. Test performance of GKSE and MKSE on CKGCN architecture. Shown is the mean + s.d. of 4 runs with different random seeds. Highlighted are the top first results.
ZINC
MNIST
CIFAR10
Ckt-bench100
Ckt-bench300
Model
MAET
Accuracyt
Accuracyt
MAET
MAEJ
CKGCN+RRWP
0.0621 + 0.0049
98,426 + 0.155
72.785 = 0.436
0.0449 + 0.0007
0.0190 + 0.0003
CKGCN+GKSH (ours)
0.0605 + 0.0040
98.490 + 0.138
72.328 + 0.152
0.0443 + 0.0006
0.0187 + 0.0006
CKGCN+MKSE (ours)
0.0611 + 0.0034
98.492 + 0.063
72.225 + 0.104
0.0435 + 0.0003
0.0189 + 0.0003
B.3. Sensitivity Analysis
We conducted a sensitivity analysis on the parameter K for RRWP and GKSE using the Ckt-Bench101 dataset. The results, presented in Table 11, provide insights into how varying K impacts model performance. For this analysis, all other hyperparameters were held constant. Notably, GKSE outperformed RRWP across most values of K, except for K = 15. Furthermore, GKSE maintained the same MAE values at K 18 (where RRWP performed best) even when utilizing shorter SE length of K = 6. Remarkably, at an extremely short K = 3. the performance of GKSE remained comparable to that of GraphGPS, as indicated in Table 4. These findings suggest that GKSE are highly efficient in representing DAGs. The robustness of their performance across different values of indicates their capability to effectively capture graph structures with reduced SE lengths, demonstrating their adaptability and efficiency in various graph scenarios.
Table 11. Sensitivity Analysis of K steps of RRWP and GKSE on Ckt-Bench100 101 [Dong et al., 2023] dataset. Shown the mean + s.d. of 4 runs with different random seeds. Highlighted indicate comparable values the GRIT+GKSE, GRIT+RRWP, and GPS+LapPE in the Ckt-Bench101 column of Table 4, respectively.
GRIT+RRWP
GRIT+GKSE
K
MAEІ
MAEJ
3
0.0443 + 0.0009
0.0440 + 0.0003
6
0.0425 + 0.0010
0.0418 + 0.0010
9
0.0434 0.0008
0.0423 + 0.0015
12
0.0435 + 0.0008
0.0429 + 0.0010
15
0.0427 = 0.0003
0.0431 + 0.0015
18
0.0418 = 0.0021
0.0395 + 0.0033
21
0.0440 + 0.0004
0,0409 + 0.0005
24
0.0430 + 0.0022
0,0424 + 0.0021
27
0.0426
+ 0.0012
0.0423 + 0.0017
30
0.0433 + 0.0016
0.0426 + 0.0010
B.4. Experiments for checking expressiveness of proposed SEs on non-aperiodic substructures
To verify, even indirectly, the expressive power of our proposed SEs on non-aperiodic structures, we conducted experiments on subsets of the PCQM4Mv2 dataset, focusing on the presence of benzene rings (a representative non-aperiodic structure). Specifically, we sampled 50,000 graphs containing benzene rings (with-ring) and 50,000 graphs without any hexagonal ring structures (without-ring). These subsets allowed us to analyze the performance of RRWP and GKSE in isolation. Due to resource constraints and the similarity performance between GKSE and MKSE, we only included GKSE these
16

---

Green and Martin Kernels for Graph Transformers
comparisons. For these experiments, used the same hyperparameters as in the ZINC dataset experiments, with the exception of limiting the training to 100 epochs. The results summarized in Table 12.
Table 12. Test performance on PCQMAMv2-subset with or without non-aperiodic substruactures. Shown is the mean + s.d. of 4 runs with different random seeds. Highlighted are the top first results.
PCQM4MM--subbeewiitrringg
PCQMAAMr>ssubbetwiittouu--
Model
MAE
MAE
GRIT+RRWP
0.1941 + 0.0191 GRIT+GKSE 0,1917 + 0.0108
0.1944 + 0.0148
0,2128 0.0358
For with-ring graphs, GKSE consistently outperforms RRWP, demonstrating its ability better capture the structural properties of non-aperiodic substructures. For without-ring graphs, RRWP shows better performance, likely due to its design being more suited to periodic or simpler graph structures. We further analyzed the full PCQM4My2 dataset and found that the ratio of with-ring to without-ring graphs is approximately 1.95:1 (with 2,477, 194 graphs containing rings and 1,269,426 without). This distribution explains why GKSE performs better than RRWP on the full dataset, as it better represents the dominant structural characteristics. Based on these findings, we hypothesize that using GKSE for with-ring graphs and RRWP for without-ring graphs could lead to further performance improvements on molecular datasets. This hybrid approach would leverage the strengths of each encoding based on the underlying graph structures.
B.5. Experiments for checking expressiveness of proposed SEs on DAGs
To verify,, even indirectly, the expressive power of our proposed SEs on DAGs, we analyzed the MAE for test samples of ckt-bench100 101 with smaller graph diameters. Specifically, there are 1,836 DAGs with diameter 1 and 1,164 DAGs with diameter 2 in the ckt- ekt-bench101 datasets. These subsets allowed us to analyze the performance of RRWP and GKSE in terms of sparsity of representations. Due resource constraints and the similarity in performance between GKSE and MKSF, we only included GKSE in these comparisons. For these experiments, we used the same hyperparameters in the ekt-bench101 dataset experiments. The results are summarized in Table 13
Table 13. Test performance on ckt-bench1 10 with diameter 1 or 2. Shown is the mean + s.d. of 4 runs with different random seeds. Highlighted are the top first results.
Diameter 1 MAEІ
Diameter 2 MAEL
Model
GRIT+RRWP
0.0433 + 0.0706
0.0513 + 0.0776
GRIT+GKSE
0.0398 + 0.0647
0.0479 = 0.0741
As hypothesized, RRWP's sparse representations for smaller-diameter graphs may lead to a loss of critical structural information, weakening its performance. In contrast, GKSE maintains denser representations, resulting in superior performance these cases. While this is consistent with our claim, we recognize that a more targeted comparative experiment would strengthen our argument and plan to explore this in future work.
B.6. Asymtotic Complexity, Experimental Environment and Computing Resources
The asymtotic complexities of GKSE and MKSE are O (|(E))) and O(K]VI + K|ε)) respectively, where the number of hops of PEs, |E| is the number of edges and | is the number of nodes, the asymtotic complexity of GRIT [Ma al., 2023a]. We implemented our study based on the GraphGPS [Rampášek et al., 2022] and GRIT [Ma al., 2023a] repositories, leveraging the PyG [Fey & Lenssen, 2019] library and its GraphGym [You et al., 2020] module. All experiments were conducted in a compute cluster environment equipped with various CPUs, as well as NVIDIA A6000 (48GB) and A 100 (40GB) GPUs. As shown in Table 14, we present the runtime and GPU memory consumption metrics for the GRIT+RRWP baseline, GKSE and MKSE on the ZINC dataset. The runtime measurements were obtained using the GraphGPS pipeline, while the GPU memory usage was monitored via the NVIDIA System Management Interface (nvidia-smi). All these experiments are carried out on a single NVIDIA A100 (40GB) GPU.
17

---

Green and Martin Kernels for Graph Transformers
Table 14. Computing result statistics of GRIT+RRWP, GRIT+GKSE, and GRIT+MKSE ZINC dataset with hyperparameters Table 6
ZINC
GRIT+RRWP
GRIT+GKSE (ours) GRIT+MKSE (ours)
MAEL
0.059 0.001
0.058 0.002
0.056 + 0.021
PE Precompute-time
7.9 sec
9.5 sec
18.0 sec
GPU Memory
1252MB
1277MB
1208MB
Training time
23.8 sec/epoch
23.6 sec/epoch
23.1 sec/epoch
C. Mathematical Details
In this section, we will examine the RW from the perspective stochastic processes and discuss the specific meanings and implications of the Green kernel and Martin kemee hold that context. For convenience, we use the following notations:
Pr (e)(())
(20)
Eg (wen(())
(21)
C.1. Markov Properties
We note that a RW on a graph defined in section 3.1 is a Markov process. Markov process possesses two key properties: the simple Markov property for fixed times and the strong Markov property for the first hitting times. These properties stated in the following lemma, which is essential for proving various theoretical results.
For j E NU {0), we define the shift map 8 Ω2 by
0z((wo wT, wI....)) = (wj, wjj....).., V(wo,w,....) E Ω.
(22)
We see that (,(O,w) Xi+s(w) for NU {0} and w Ω. Lemma C.1. Let v, E V and E N U {0}. Let E. be random variables with some regularity conditions. Then
1. (simple Markov property)
Bp [s(n o 0 = F2 [s [xx [v]]
2. (strong Markov property) Eg [E(n 0. 0,,)) = Ex IS En[n]
The detailed statement can be found in the [Barlow, 2017]. In this paper, we present only a brief version and omit the detailed conditions. Nevertheless, random variables in the proofs below satisfy the regularity conditions.
C.2. Finite Step Green Function
In section 4.2, we define the finite-step Green kernel (b) using recursive relations as in eq. (12). We can describe G(k) in the explicit form as follows: for à E N and x, y
V,
G (x, (x.0
(23)
1=0
in which (00 I.
In order to interpret the finite-step Green kernel in terms of the stochastic process as described in the previous subsection, we first define the counting function k Ω + NU {0) formally, as follows: for w E
(w) Σ 1 [x(())=))
(24)
==0
where [(x,)==)) : Ω > {0.1) is the indicator function, meaning it takes the value if (,(w) = and 0 otherwise. follows directly from the definition that the value of (k))()) y within k-steps.
(w) is equal to the number of times that the trajectory w visits node
18

---

Green and Martin Kernels for Graph Transformers
We now turn to Theorem 4.1, As described above, for w S2 the value of I.y (w) equal to the number of times that the trajectory visits node y within k-steps. Recall that the probability Px is concentrated on the set of all trajectories starting at node x. Thus, after applying the expectation Ez[] to the counting function ( its value equal to the expected number of times that a trajectory starting at node x visits node y within k-steps. Finally, we provide the following proof at the end of this section.
Proof of Theorem 4.1. The proof is inspired by [Barlow, 2017], which addresses the case when = co. follows from the definition that:
Ex
Ex
Σ
1 (x(
1=0
Ex [1 (x)(w)=v)
==0
Σ ==0
Pr [w] vl
&
Σ P' P' v)
==
G (x,
Thus, we prove the theorem.
C.3. Finite-Step Martin Kernel with the first hitting time map
To prove the theorem 4.2, we first observe what the finite-step Martin kernel with the first hitting time map M approximates. The following lemmas will be used in the proof of theorem 4.2.
Lemma C.2. For & E NU {0} and 2, E V, let (6) be defined in eq. (14). Then, the following equality holds:
H (x.v)
0 s Palyy SA M (I,
(25)
where (K) (z, v) = (T( Ty s k] E2 [1 5k) Ty] is the k-step hitting time, meaning the expectation of the first hitting
time within k-steps.
Proof. By Theorem 4.1, we have
(Z, = =E, [1/00 Ez [11TSSAA
(26)
The second equality comes from the fact that if Ty (w)) k. then T. (w)
(w) = 0 for all w Ω.
19

---

Green and Martin Kernels for Graph Transformers
Observe that
Σ
(X.=)
k
[X==))
(27)
1xx++ =0
1 (x:=y) o Or,
1 0Ty
Combining with eq. (26) and eq. (27), we have
G ( (sr, y) Bz 1 (r,st) (n. (o o0:0.)
(28)
Σz [(t My (
(29)
Ez 11TSS By (100
Ex
( By
Σ
[x,
(30)
Ty+-
Here, the strong Markov property in Lemma C.1 is applied for the second equality. We note that By In (k-
which is in
eq. (29), is not constant, but a function of w Ω such that Xo(w) For the first term in eq. (30),
Fx I (T)SH) Ey [.,00] = Er, =E.
(TwS)) By [I,00]] PA(TT S ( (v.u).
(31)
For the second therm in eq. (30), first observe that for Q such that Xo(w)
[xx(-)=) Sy(ww,
(32)
i= (w)))
and hence,
& Σ
S E,
(X)(w)=))
$ Ey [r,[w)] = Ty (w)
(33)
i= (w)+
Thus the second term in eq. (30) is
0 < E,
(ryS Ey
Σ [xx=v}
Eg
[1I (T)5K) Ty]
(34)
Ex [Ty Ty $ k]
(1))
Using eq. (28-34), we have
Palty S k) G (v.
( < (x, s PPIT, s k] (K)) (v. v),
(35)
20

---

Green and Martin Kernels for Graph Transformers
or
(z.)
G (z.y)
( (z,y)
s PA(T S k]
(36)
(y.y)
00 (v.
We complete the proof.
Lemma C.3. For & [N and v, y E V, let (() be defined in eq. (14). Then, the following equality holds:
M (x. v)
S1
(37)
G (u,)
Pa Ty S kj
Proof. From eq. (29), we have
(x, = Ex [1 (r [ [
(38)
Σ
Ez L [ By L (1 ]]
(39)
1=1
Po ITy i (2.
(40)
i=0
Σ
Pr (Ty
(41)
Pr [Ty S k).
(42)
Thus, we have
G (I,,)))) v)
(43)
P. (Ty S k]
and hence
M (z, v) Pa Iy S kj
(44)
G v)
The upperbound comes from the lowerbound in Lemma C.2, which is
0 < Palty < k]
M (1) (I,
(45)
These two inequalities complete the proof.
C.4. Finite Step Martin Kernel
Recall that, for E V, the first hitting time map To and the first return time map Ty is defined as follows: for w E Ω
Ty (w) = min Nu (0) X,(w) = f);
(46)
T (w) = min(i : X,(w) = y).
(47)
We note that w starts from a node other than then (w) = ग, (w)) This is because random walk requires at least one step to visit another node, so the minimum in eq. (46) cannot be attained when i O.
Proof of in Theorem 4.2. Let & E N. We first prove the case when r = y E V. By the definition of the first return time and the first hitting time, for S2
(w) min 2 Xi(w) = x}
minfi 2 0 Xi+1(w) = =x) +1
(48)
min(i 2 0 X,(0ww) = +1
(01w)) +1.
21

---

Green and Martin Kernels for Graph Transformers
By eq. (48), we have
Px 1r 5k]
Ez
1 [r sk
Ez [ Sk
= Ez (rr 001
= Ex [xx (+rsskx-1
(49)
= [Px, Sh 1I]
Px([X] =2 P/ I k - 1]
sEV
Σ 2(. Px S 1].
=EV
Here, the third equality comes from the simple Markov property in Lemma C.I. From Lemma C.2,
H (2,x) (x, x)
M (- (2,
P2/TT S k - 1]s ((h1 (2,
--1]
(50)
Combining with eq. (49) and eq. (50), we get the following two inequalities
P s S Σ
P(x, 2)
M = (P M(+ (x)
(51)
=EV
M2 (2,
Pa[T
S N Σ
P(r, 2)
(52)
(Ir
+EV
P x (+ (2,
= -(P x (( (2)
G (k- 1) (x)
By definition, (P ()) (I,z) = (I, It remains to show (P (( (2, & H(()) (r) Indeed,
P P H(()))))) (x, x))
P(r, 2) H (2, x))
NEV
> Pa
[X1 [x
12],T[Ts To S -k-1] 1]
zCV
En
[Ex, [ (T. (T. [
En [(1(ta5k-1) Tz o 8
(53)
Ex
[1 [k) (T - -1]
E2 [ + sk]
- -P < k]
S Ex : < k)
H (z.x)
Here, the fourth equality comes from the simple Markov property in Lemma C.I and the fifth equality comes from eq. (48).
Now, we prove the case when x + y E V. Obeserve that (w) = T (w) for all w E Ω such that Xo(w) = x, since a RW
requires at least one step to move from node x to y. Thus we have
Pait & k] = Pz(Ty S k]
(54)
(x) v) E.It + < k] E. Ty S kj = H (x.)) (z.9).
(55)
We also have (zr, y) = M (x) v/ by definition. The proof follows from Lemma C.2.
22

---

Green and Martin Kernels for Graph Transformers
Proof of in Theorem 4.2. Let k E N. We first prove the case when y V. From Lemma C.3,
PuITa I k -1 G (x)x) I M (K 1) (x, (x,x) - P S k 1].
(56)
Applying convolution to each instance with P. by eq. (49) and the definition of M(A), we have
Pa P S k)
& M
PPlT S k).
(57)
(x,
which complete the proof in the case y.
Now, we prove the case when x * y V. By eq. (54), eq. (55) and the definition of M( the proof follows from the Lemma C.3.
D. Representational Power
D.I. Aperiodicity of Graphs
Let (V.8) be graph. The period pg of G is defined by the greatest common divisor of the lengths of its cycles:
pg ged(n Xo(w) Xn (w), E St}.
(58)
We call graph G is aperiodic if Pg and non-aperiodic if Pg > 1.
One important remark about the period a graph is it affects the spectrum of the transition probability matrix P the graph. By the Froron-Foobeiuus theorem for irreducible non-negative matrix [Strang, 2012], there exists exact Pg eigenvalues attaining the maximal absolute value.
For example, the hexagon graph Cg. which is the cycle graph on 6 nodes as illustrated in Figure has Pcs = 2 and its transition probability matrix has eigenvalues 1 and -1. In this case, the eigenvectors associated with the eigenvalues I and is Φ1 = (1, 1, 1, 1, 1) and Φ-1 = (1, 11 1, - 1, 1, 11),, respectively. It can be observed by spectral analysis that for any vector v E & that is not spanned by Φ1 or 1 pdv oscillates between Φi + Φ- and Φi - Φ- as + +00. This phenomenon may leads to the unstability RRWP.
Formally, let g be the one-hot vector supported at node x E V. Then we have
P(x,)) v) 1 P 1
Yz, Y V.
(59)
Since Ly is not spanned by di 1- Pily oscillates k - to and hence P(x, v) also oscillates as k - +00.
However, G (xx y) diverges to +00 and ( v2, converges to as h - +oo for recurrent graphs. Thus, (k)
and (A) do not oscillate indefinitely as illustrated in Figure 3, indicating that they are more stable under the choice of K E NU (0) and capture the structural property graph well.
Despite the above observations, remains unclear whether the absence of oscillation in GKSE and MKSE actually enables better detection of non-aperiodic substructures. As noted in [?]. detecting specifie substructures is an extremely challenging task and is proven to be infeasible with many existing GNN models. Nevertheless, since GKSE and MKSE exhibit distinct patterns compared to traditional methods, we are optimistic that they could provide some advantage. Further research is necessary to confirm this hypothesis.
D.2. Generalized RWs
Mathematically, the transition probability matrix can be defined as a real-valued matrix whose row sums equal 0 or 1. We allow the row sum to be since we consider the sink node with an out-degree of 0. To avoid irregular cases, we assume that there exists a positive lower bound & < for the transition probabilities. The assumption is not superflous since a transition probability matrix for a simple RW also satisfies this assumption with 1/dmax. where dmax is the maximum degree of the nodes in the graph. Formally, the transition probability matrix P for generalized RW satisfies
1. Σvey P(z,v) = 1, Vy E
23

---

Green and Martin Kernels for Graph Transformers
k=1
k=2
k=
k=4
k=5
k=6
RRWP
GKSE
MKSE
Figure 3. Visualization RRWP, GKSE, and MKSE on hexagon graph k-steps ranging from
2. P(r,u) e (r,μ)EE.
In this generalized setting, RRWP, GKSE, and MKSE can still be defined in accordance with the transition probability matrix P for general RWs. We will prove the theorems and corollaries in the generalized setting.
D.3. Expressiveness of GKSE and MKSE
In this section, we present several theoretical results illustrating the expressiveness of GKSE and MKSE when combined with MLP. Our findings are inspired by the study in [Ma et al., 2023a], yet extend to more general scenarios involving RWs with con-identical transition probabilities. We note that, the case of simple RW, the transition probabilities from one node adjacent node in the next step identical.
The following theorem, restatement of Theorem 4.3 (1), suggests that the expressiveness of GKSE when integrated with an MLP is equivalent to that of RRWP. Analogous to the proposition in [Ma et al., 2023a], we derive Corollary D.2, which implies that GKSE can approximate various graph propagation matrices with precision up to an arbitrary positive error c. We prove the theoretical results in the general setting, specifically for non-simple RW case
Theorem D.1. GKSE with MLP has exactly the same expressive power as RRWP with MLP.
Corollary D.2. Let n. K N and lei be sufficiently small. Then there exists MLP from RRKK to lR R&K such that the for any GKSE R=xxxx K derived from a graph with nodes, MLL((KSSS can approximate any of the following: for all U.U. V,
(a) MLP(GKSE((,, v)) = SPD (x;
(b) MLP(GKSE((R.)) (EK- 0g pk) (x,y);
(c) MLP(GKSE((,, v)) =0 (0. + A) (x,
within error. Here, SPDK-1(4,9) v) represents the truncated shortest path distance, and 0g E R are arbitrary coefficients.
We prove that MKSE possesses a unique expressiveness that cannot be achieved by RRWP alone, highlighting its potential to enhance the representational capability of GNNs in distinguishing complex graph structures. Furthermore, despite its different representational range, MKSE can also approximate several graph propagation matrices, stated in Proposition D.4. The proofs can be found in Appendix D.4. We begin by restating Theorem 4.3 (2) as follows.
Theorem D.3. RRWP with MLP cannot approximate MKSE.
24

---

Green and Martin Kernels for Graph Transformers
Proposition D.4. Let n., K N and let be sufficiently small. Then there exists MLP from RR R or RKK such that the for any MKSE R derived from graph with nodes and no self-loop, MLP approximate any of the following: for all x, E V.
(a) MLP(MKSE(Z; u)) = SPDD SPDx-1(Z,8)
(b) MIP(MKSE(E, v)) (0.1 02 A) (x. v)
within error. Here, SPD (x, represents the K truncated shortest path distance, and Og R are arbitrary coefficients.
D.4. Proofs: Expressiveness of GKSE and MKSE
For convenience, we denote SEs follows: for K N,
(RRWP)
R = [,,(()) p(K- E Raxuxk
(60)
(GKSE)
G I. G ..K.,,.(--)] gnxax;
(61)
(MKSE)
M = ML) M(K,I] E gaxaxk
(62)
Proof of Theorem D.I. Let K E N. It suffices to show that there exists continuous bijective function ş R - R with continuous inverse such that for all æ, E V. (G(x, R(x, y). The reason this completes the proof is as follows. Supppose there exists a function that can be expressed by some continuous function f as f (R(x, y)). Then, by the above observation, it is equivalent to (f o up) (G, y)). The converse also holds. Therefore, according to the standard universal approximation reuslts [Hornik al., 1989], the expressivenss of GKSE with MLP is entirely equivalent the expressiveness of RRWP with MLP.
k by Now, we define the linear map yp IRK
p IK. 1) = (zo, x1 20. x2
- IK-2).
(63)
By the definition, for all x, e V. (G(#, v)) R(r,y). Obviously, it is continuous and has continuous inverse y- given by
x1, (xx.,,,..,, = (vo, xi + xı, to + 21 + 22, + ... xI-.).
xk
(64)
This completes the proof.
Proof of Corollary D.2. We first prove the Proposition 3.1 from [Ma et al., 2023a] in the generalized RW setting stated in Appendix D.2. Then by Theorem D. the results follows.
claim that for all = I,..., , K 1, each nonzero entry P is greater than & We will prove the claim by using induction. The case when y, y with p*+1(x: y) + 0,
obvious by definition. Then we assume that the claim holds for We note that for
p++ p
Σ
p (*x,))P(2z.)
(65)
zEV. P (n.2) & (x.N)EE
Since pk++ (x.v) y) # O, there exists at least one such E V. Also, by assumption, Pd (2,2) th and P(z, v) > É. Thus have (k++1) (x, v) > gh+11 proving the claim.
Following the claim, by replacing the lower bound L with gk-1 in the proof of Proposition 3.1 in [Ma et al., 2023a], the proof is completed.
25

---

Green and Martin Kernels for Graph Transformers
1
Figure 4. (Left) (4.2)Hollipop graph and (Right) A graph consisting of a 4-cycle and a 2-path connected by single edge.
Proof of Theorem D.3. We will prove the theorem by providing two examples of graphs with 6 nodes for which each RRWP with MLP cannot approximate each MKSE simulteneously Suppose that there exists function yp R - TRK constructed by MLP such that for all graphs with 6 nodes and x, y E V. (R((z, y)) approximates M(r, y) within e < 1/15 error.
Consider the graph G1, which is the (4, -lLollppp graph consisting of the complete graph K, on nodes, the path graph P2 on 2 nodes, and one edge connecting K.4 and P2. Also, consider the graph G2, which is obtained by 91 by replacing K4 with the cycle graph C4 on nodes. Let æ, y E V be the nodes of 91 or G2, where æ the terminal node of P2, and y is in the K4 or Ca connected to P2. We visualize 91 G2 and x, y in Figure 4.
Now, for i = 1, 2, we denote RRWP, GKSE, and MKSE with K = 3 for Gi by R., G., and M,, respectively. Then, we have
1
T
R, (x, = 0,0,
=
R2(r,)) = 0,0, 2) ;
2
(66)
3
T
1,0 1 T
R1(y,))
1,0,
R2(y,))
8
Using eq. (66). we obtain
G1(r,)) = 0,0, 1 T
Gz(r,)) = 0,0, 1
2
2
(67)
11 T
T
Gv = 1, 8
G2(y,)) = 1, (1,1
and hence
4 T
))²
M2(0,)) 0,0, 3))
(1 v)
0,0, 0,
(68)
11
Observe that (2, = R2(2, y) but [M 3) ol = 1/15 > c. Thus, we conclude that (0, 0, 1/2) cannot approxiate both M2 (x. y) and M2(r,)) y) simulteneously within c error. This contradiction proves the theorem.
Proof of Proposition D.4. From the proof of Corollary D.2, for k I,..., K and x, E V with pK(x, y) * O, we have Pk p*x,,10 (x,y) g1-
Now, let 1 = 1,.... K 1 and let x; y E V such that G (1) y) F Then, by the definition of GKSE, of the P (2. y) is nonzero among = 0. ... k. Thus,
have G (*)) (x. v) > gk- Also, note that P y) S 1 for all i 1,..., lc and x, E V. which implies that G (k) (a, y) < le < K for all == 1...., & and v E V. Lastly, it is obvious from the definition
of the MKSE that G*(xvv) v) * O iff M (x. v).
Using these observation, we have that for k = O..... K and x. y E V such that M (z. 8) + O.
(xx
gk-1
(1,
(69)
G( (v.
K
26

---

Green and Martin Kernels for Graph Transformers
(a) Let S1: RK + RRK be continuous function such that [1)),; 0 if 24 0 and 1 if Pk-1/K. Then have that for k = 0, .., 1,
(M v))a {
(ar can reach y in & hops) or (æ = y)
(70)
else.
Let f2 :RK + R K be defined by f2(x) = max </ Tws, which is continuous. Then we have for k: = 0,.... ......K K 1,
RRK
f2 o fi(M(z {
iPD S
(71)
else.
The remainder the proof follows the same steps as the proof of Proposition 3.1 in [Ma et al., 2023a].
(b) Observe that
fM u)) = {
(a can reach y in hops) or (a = y)
(72)
else.
By the assumption that graph have no self-loop. the cases where (æ can reach y hops) and (a = y) do not oceur simultaneously. Thus have (Mr y))
(x v), where A is the adjacency matrix of the graph.
Now we take f3 RK + R² given by fa(x) ((Op 01 kro 01 and f4 R R given by fe + .n Then we have
f4 fa fi (M v)) = 001 + A.A.
(73)
The remainder proof follows the same steps as the proof of Proposition 3.1 in [Ma al., 2023a].
Proof of Theorem 4.5. We will prove the theorem based on the proof of Proposition 3.2 [Ma et al., 2023a]. note that
minfk G (8) (I. v) + 0} = minfk ( (z) y) * 0} = SPD v),
(74)
where SPD is the shortest path distance. This shows that GKSE and MKSE are more expressive than SPD, and thus, they refine SPD. Using this observation, along with Lemma in [Bevilacqua et al., 2021], we conclude that GD-WL with GKSE or MKSE stronger than GD-WL with SPD.
Next, we prove that GD-WL with GKSE MKSE is streitly stronger by providing some example graphs. Specifically, the Desargues graph and the Dodecahedral graph cannot be distinguished by GD-WL with SPD. However, GD-WL with GKSE or MKSE, using at least 5 steps, can distinguish between them.
27


Reviews:
[{"review_id": "GzD7uob8p9", "reviewer": "Reviewer_KW69", "summary": "This paper proposes to utilize green and martin kernels to build new SEs for better graph transformers. The proposed method extends previous RW-based SE such as RRWP in GRIT, demonstrating great empirical accuracy across multiple datasets.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer for the detailed and thoughtful feedback. Below, we clarify the key motivations, contributions, and empirical implications of our work, while responding to specific concerns regarding novelty, positioning, and evaluation scope.\n\n---\n\n## 1. Novelty Beyond RRWP and Value of Kernel-based SEs\n\nWhile our proposed SEs share a random-walk foundation with RRWP, they originate from **Green and Martin kernels**, classical constructs from potential theory and stochastic processes. These kernels reflect **asymptotic behaviors** of random walks, capturing structural phenomena such as **non-aperiodicity**, **absorbing components**, and **hierarchical depth**—aspects that finite-length walk-based encodings like RRWP may overlook.\n\nOur contribution lies not in incremental variation, but in **reformulating these kernels** into scalable encodings for modern graph transformers, retaining their mathematical meaning. We believe this offers a new direction for structural encoding design, grounded in well-established theory.\n\n---\n\n## 2. Empirical Gains and Practical Implications\n\nWe agree that performance gains on standard benchmarks may seem modest overall, which reflects the nature of these datasets where local attention often dominates. However, we observe **notable improvements** in datasets with more complex global structures—**PCQM4Mv2** (molecules) and **Ckt-Bench101** (circuits)—where the structural sensitivity of GKSE and MKSE becomes evident (Table 3, 4; Appendix B.4–B.5).\n\nCrucially, these gains are obtained **without changing model architecture**, demonstrating the practicality of our SEs as **drop-in modules**. Even small but consistent improvements from theoretically grounded, efficient encodings can accumulate meaningfully across applications in circuits, molecules, or program graphs.\n\n---\n\n## 3. Positioning Relative to Recent Literature ([1], [2])\n\nWe thank the reviewer for referencing [1] *Recurrent Distance Filtering* and [2] *Graph as Point Set*. These represent powerful yet fundamentally different approaches:\n\n- [1] adapts message passing using learned filters based on node distance.\n- [2] maps graphs to sets via spectral regularization and permutation-invariant networks.\n\nBoth methods involve **architecture-level changes** and rely on **eigendecomposition**, which can hinder scalability. In contrast, our SEs are **model-agnostic**, require no spectral operations, and target transformer-style models that lack native graph inductive bias.\n\nThough our work differs in intent and scope, we agree that comparing across such methods adds valuable context. We are preparing further experiments and will include comparative discussion in the final version.\n\n---\n\n## 4. Experimental Scope and Use of GRIT\n\nWe chose **GRIT** as our primary architecture because it provides an explicit SE framework, including both **absolute and relative** positional encoding. It also uses RRWP as a core module, making it a **natural baseline** for assessing our SEs under controlled conditions.\n\nNonetheless, our SEs are not limited to GRIT. In **Appendix B.2**, we apply them to **CKGConv**, a structurally different graph transformer, and observe consistent improvements. This supports the general applicability of our method. We plan to expand these evaluations to additional models in future work.\n\n---\n\n## 5. Broader Relevance and Future Directions\n\nOur work aims to bridge **mathematical theory with practical GNN design**. Reformulating Green and Martin kernels into usable SEs represents a principled step toward designing **structural encodings with formal guarantees**.\n\nThis approach opens promising future directions:\n\n- Exploring other theoretical kernels (e.g., hitting time, diffusion).\n- Applying to domains with structured topology (e.g., program graphs, knowledge graphs).\n- Integrating with adaptive architectures like [1] for further synergy.\n\nWe hope this inspires more mathematically grounded exploration in GNN research.\n\n---\n\n## Conclusion\n\nWe thank the reviewer again for their valuable insights. In response, we will:\n\n- Clarify the novelty of GKSE and MKSE versus RRWP.\n- Highlight broader architectural compatibility beyond GRIT.\n- Expand the discussion to include recent related works and future directions.\n\nWe hope these clarifications address the reviewer’s concerns and underscore the contribution and relevance of our work.", "claims_and_evidence": "- Both theoretical and empirical analyses of the proposed method clearly show its effectiveness. \n\n- Extending RW-based SEs with Green and Martin kernels can potentially bring more insights and observations for future research. Nonetheless, besides the observation of the connection between Green/Martin kernels and SEs, the proposed method may not bring fundamental improvement/breakthrough, i.e., the derived SEs seem to have minor differences compared with RRWP, and the empirical accuracy across multiple datasets only demonstrates marginal improvement, which may pose questions on the necessity/benefits of the proposed method and the positioning of the paper.", "methods_and_evaluation_criteria": "The evaluation criteria follow the standard of this area. The widely used datasets for evaluating graph transformers are included. However, this paper centers its comparison mostly on GRIT, without including newer results from the literature, e.g., [1]. Newer results without RRWP-like SE may exhibit even better empirical performance, which may again bring the concern about the necessity/positioning of the proposed SEs.\n\n[1] Ding, Yuhui, et al. \"Recurrent distance filtering for graph representation learning.\" arXiv preprint arXiv:2312.01538 (2023).", "theoretical_claims": "I did not check the appendix, but I have checked the theoretical part in the main text, which justifies the design of GKSE & MKSE and their expressiveness.", "experimental_designs_or_analyses": "See above.", "relation_to_broader_scientific_literature": "This paper is related to designing better graph transformers, in terms of both accuracy and efficiency. This paper centers mostly on the accuracy part by designing better SEs, a core part in graph transformers. More specifically, this paper is very related to GRIT, a paper utilizing RRWP to empower graph transformers with better performance. By extending RRWP with Green and Martin kernels, this paper further improves GRIT.", "essential_references_not_discussed": "There are graph transformer-like methods that can improve performance without requiring complex design of SEs. The authors may want to discuss them, e.g., [1, 2]\n\n\n[1] Ding, Yuhui, et al. \"Recurrent distance filtering for graph representation learning.\" arXiv preprint arXiv:2312.01538 (2023).\n\n[2] Wang, Xiyuan, Pan Li, and Muhan Zhang. \"Graph as point set.\" arXiv preprint arXiv:2405.02795 (2024).", "other_strengths_and_weaknesses": "Even though the empirical improvement does not seem that significant, the observed connection between Green/Martin kernels and SEs may potentially bring more insights for future research.", "other_comments_or_suggestions": "No.", "questions_for_authors": "See above.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "gprkMMbP6H", "reviewer": "Reviewer_uA7X", "summary": "This paper proposes two new structural encodings for graph transformers, Green and Martin kernels. These two kernels are some extension of the random walk kind. This paper also demonstrates that the proposed two kernels outperform the existing one.", "questions": "", "limitations": "", "rating": 1, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer’s detailed feedback and critical questions, which allow us to clarify both the motivation and contributions of our work. Below, we address the main concerns.\n\n---\n\n### 1. Limitations of Existing Random Walk-Based SEs\n\nWe agree that random walk (RW)-based SEs, such as RRWP, are already effective in many graph transformer models. Our work does not claim these methods are flawed; rather, we aim to reformulate the concept of structural encoding through a more mathematically grounded lens. Existing SEs are typically designed heuristically based on the network centrality theory, or with limited theoretical support beyond local transition statistics.\n\nOur SEs—GKSE and MKSE—are derived from stochastic process theory. Green and Martin kernels arise in the asymptotic analysis of random walks and are widely used in potential theory to describe the global behavior of Markov chains on graphs. They can uniquely encode specific structural information, such as non-aperiodic and DAG-like structures. As shown in Section 5.2, the values produced by our SEs differ significantly from RRWP across various graph topologies, highlighting their distinct representational properties.\n\n---\n\n### 2. Difference Between Green Kernel and PageRank\n\nAlthough Green kernels are algebraically similar to Generalized PageRank (GPR) [1], they differ in key ways:\n\n- **Mathematical Origin**: GPR focuses on signal smoothing and centrality, while Green kernels emerge from the resolvent of the Laplacian and describe expected visit counts in infinite random walks. This gives them a formal stochastic interpretation, which we rigorously connect to structural encoding via Theorem 4.1 and 4.2.\n\n- **Usage in GNN**: GPR is typically used as a node feature or precomputation step. In contrast, we use Green and Martin kernels as absolute and relative SEs that directly guide attention in graph transformers.\n\nTo our knowledge, this is the first work to adapt Green and Martin kernels as structural encodings in GNNs.\n\n---\n\n### 3. Why Use These SEs Despite Marginal Gains?\n\nWe agree that performance differences can be small on standard benchmarks, which often favor architectures over SE design. Still, our SEs show meaningful gains on topology-sensitive datasets like OCB (Ckt-Bench101, 301) and PCQM4Mv2, which contain DAG and non-aperiodic structures.\n\nMore importantly, our methods:\n\n- Are **model-agnostic** and plug into any transformer architecture  \n- Are **computationally efficient**, computing recursively and avoiding eigendecomposition  \n- Are **theoretically grounded**, derived from stochastic process theory\n\nEven modest gains can be impactful when combined with scalability and theoretical robustness, making these SEs useful in large-scale, real-world settings.\n\n---\n\n### 4. Theoretical Contributions of GKSE and MKSE\n\nOur work provides several new theoretical insights:\n\n- We connect Green and Martin kernels to SEs with provable structural meanings  \n- We establish formal results (Theorems 4.1–4.5) showing their expressiveness  \n- We show MKSE captures non-linear random walk behavior distinct from both RRWP and GKSE (Theorem D.3)\n\nTo the best of our knowledge, these are the first such results making these stochastic tools directly applicable to GNNs while preserving their mathematical essence.\n\n---\n\n### 5. Summary of Key Contributions\n\nTo summarize:\n\n- **Theoretical Innovation**: Reformulating classical random walk kernels into structural encodings  \n- **Architectural Generality**: Easily applicable to transformer architectures  \n- **Efficiency**: No eigendecomposition, scalable to large graphs  \n- **New Direction**: Enables broader use of mathematical kernels in GNNs\n\nWe also acknowledge the reviewer’s note about wording in the abstract and will revise it to avoid vague phrases like “AI-ready” or “promise,” in favor of more precise claims.\n\n---\n\n### 6. Final Remarks\n\nWe appreciate the reviewer’s critical perspective and hope this rebuttal clarifies our contributions. Although the gains may be modest in some benchmarks, we believe the theoretical foundation, practical utility, and extensibility of our SEs make a compelling case.\n\nWe will revise the manuscript to clarify our distinctions from existing methods, including [1], and better communicate our theoretical and empirical contributions.\n\nThank you again for your thoughtful and constructive feedback.", "claims_and_evidence": "The theoretical claims are interesting. Particularly, Thm 4.1 and Thm 4.2 give theoretical foundations of the proposed algorithms. \n\n\nHowever, a real question is, why do we need this?\n\ni) Almost all experimental results do not show a significant improvement over the random walk + GRIT, where the figures shown is very close to each other.\n\nii) The formulation of Green Kernel kind is somewhat similar to the page-rank based on in [1]? Can you please give an explanation of the difference between the Green Kernel and [1]?\n\nI am quite not sure why we need a newer version than random walk. What is the limitation of random walk one? What is the advantage of the proposed ones? In which scenario these can improve the existing random walk? Since this paper aims to provide theoretical justification, it would be very nice if you can provide theoretical explanation.\n\nTherefore, I am not that convinced by the claims this paper made.\n\n[1] Pan Li et al. Distance Encoding: Design Provably More Powerful Neural Networks for Graph Representation Learning. NeurIPS 2021.", "methods_and_evaluation_criteria": "I am not quite sure which problem authors try to address. What is wrong with random walk, given the very marginal improvement in the experiment.", "theoretical_claims": "Theoretical claims are interesting -- if this is a novel result.", "experimental_designs_or_analyses": "The authors provided a fair experimental setting.", "relation_to_broader_scientific_literature": "As I repeatedly say, I am not quite sure what is the key contribution of this paper. What is the improvement over the existing work?", "essential_references_not_discussed": "Maybe it would be very nice if the authors can relate to [1]", "other_strengths_and_weaknesses": "N/A", "other_comments_or_suggestions": "This comment does not directly affect my rating. \n\nAuthors may want to come up with better prompt to save \"big words\", if authors rely on the GenAI writing tools. For example, in abstract, \n\n> This work underlines the promise of theoretically grounded, AI-ready kernels in advancing the capability and scope of Transformer architectures for graph-based learning.\n\nWhat is the promise? What is the AI-ready kernels? These big words may blur the authors' real contributions. \n\nI cannot rule out I am indirectly affected by these big words, since my questions are concentrated on the questions like what are the key contributions.", "questions_for_authors": "I encourage authors to answer the question above.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "B0tfSbDHbl", "reviewer": "Reviewer_zGzV", "summary": "This paper builds on the framework introduced in GRIT, where a carefully chosen set of relative positional/structural embedding (SE) is defined at the input of the model, which is then updated every layer. Specifically, the paper introduces two random-walk based SEs - GKSE and MKSE, which are well motivated with the included theory. Experimental results are also provided on a variety of popular graph benchmarks.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the positive comments on our theoretical development, writing quality, and comprehensive benchmarking. We also appreciate the thoughtful concerns raised regarding statistical significance and generalization. Below, we respond to each point in detail.\n\n---\n\n### 1. Clarification on SOTA Claims and Statistical Significance\n\nWe fully agree that our previous statement claiming “SOTA on 7 benchmarks” was overstated. Since many improvements fall within the margin of error (N = 4), we will remove all such claims from the paper.\n\nRegarding (a), we used N = 4 to match the experimental setup in GRIT and ensure consistent comparisons. However, we acknowledge this is insufficient for statistical rigor. We are currently running additional trials with a larger number of seeds across datasets and will include extended results in the final version.\n\nRegarding (b), we conducted t-tests and observed statistically significant improvements (p < 0.05) in PCQM4Mv2 and OCB (results in Table 3, 4). Other cases did not show significance, likely due to small sample size. We agree that larger N is needed to draw solid conclusions, and will re-run all key experiments with more seeds.\n\n---\n\n### 2. Empirical Justification for Theoretical Advantages\n\nWe appreciate the reviewer’s acknowledgment of the connection between theory and empirical results. PCQM4Mv2 and Ckt-Bench101, with non-aperiodic and DAG-like structures, clearly demonstrate the strengths of our SEs.\n\nWe agree that additional evidence would be valuable. While benchmarks with similar structure are limited, we are exploring domains such as knowledge graphs and program analysis, where our methods may further excel.\n\n---\n\n### 3. Evaluation Beyond GRIT\n\nThe reviewer highlights the need to evaluate the generality of our SEs on other architectures. GRIT was selected because it cleanly isolates the effect of SEs by explicitly using both absolute and relative encodings. This allowed us to assess the performance impact of replacing RRWP with our SEs in a controlled setting.\n\nNonetheless, our SEs are not limited to GRIT. As shown in Appendix B.2, we applied them to CKGConv—a different architecture—and observed consistent gains. We plan to extend evaluations to additional GNNs in future versions.\n\n---\n\n### 4. Relationship Between GKSE and RRWP\n\nAs noted in Appendix D.4, GKSE can be expressed as a linear transformation of RRWP under specific conditions. However, despite this theoretical link, our experiments show that initializing with GKSE leads to better empirical performance.\n\nThis mirrors known results in deep learning: different initializations (e.g., Xavier vs. He) can lead to distinct learning behaviors, even when functionally equivalent in theory. Thus, GKSE and RRWP differ in practice in meaningful ways.\n\n---\n\n### 5. Experimental Scope\n\nWe thank the reviewer for acknowledging our broad experimental coverage. While gains vary across datasets, our SEs provide consistent improvements, particularly in graphs with structural complexity. Even when improvements are small, our SEs offer a principled, scalable, and interpretable alternative to existing approaches.\n\nTheir effectiveness is most pronounced in domains where global structure and asymmetry matter—settings that standard benchmarks may not fully reflect. We believe our work lays the foundation for broader adoption of mathematically grounded SEs.\n\n---\n\n### 6. Summary of Actions\n\n- Removed all exaggerated SOTA claims.\n- Expanded experiments with more seeds for reliable significance testing.\n- Clarified the theoretical and empirical differences between GKSE and RRWP.\n- Demonstrated broader applicability through CKGConv results (Appendix B.2).\n\n---\n\n### Conclusion\n\nWe thank the reviewer again for the constructive and fair evaluation. Your feedback has helped us refine our claims and improve the clarity and rigor of the paper. We believe the theoretical insights, along with targeted empirical results and ongoing evaluations, support the relevance and contribution of this work.", "claims_and_evidence": "The paper introduces GKSE and MKSE, and their formulation appears to be rigorously defined. The extension of random walks using Green and Martin kernels appears to be a valid theoretical contribution.\n\nThe paper claims that the method achieves SOTA results on 7 benchmarks but based upon the margin-of-error with $N=4$ different seeds, there is only evidence for SOTA performance on 3 benchmarks. In particular:\n- Table 1: Only MNIST shows a statistically significant improvement over baselines.\n- Table 2: None of the two datasets show statistically significant improvement over GRIT+RRWP. Moreover, the numbers reported do not come close to the leader in the leaderboard present at [2] (maintained by the original authors of the dataset's paper).\n- Table 3: Improvement over baselines is statistically significant on PCQM4Mv2.\n- Table 4: Only Ckt-Bench101 with GRIT+GKSE shows a statistically significant improvement.\n\nSince improvements on other benchmarks are small in comparison to the margin of error, if the paper wishes to claim for SOTA performance on the other tasks presented, it should either (a) provide experiments with a higher $N$ (number of seeds) so that any reasonable statistical support for this claim may be made independently by the readers, or (b) present convincing statistical analysis of its own supporting this claim.\n\nThe claim that GKSE and MKSE handle non-aperiodic substructures (present in molecular datasets) is nicely aligned with their theoretical properties. However, clear empirical evidence for such an increased ability to deal with molecular datasets is only provided in the PCQM4Mv2 benchmark (Table 3). More examples of such clear improvements over baseline would be needed to better support this claim.\n\nThe paper claims the theoretical properties of GKSE and MKSE make it suitable for datasets with DAG structures. However, similar to the previous point, a stronger empirical justification would help strengthen this claim. Of the two circuit datasets considered, the presented technique shows improvements larger than the margin of error (barely) on only one dataset.\n\n[2] https://github.com/vijaydwivedi75/lrgb", "methods_and_evaluation_criteria": "Yes, evaluation on the included graph-level tasks makes sense for testing a relative structural encoding scheme.", "theoretical_claims": "I have checked the proofs for Theorems 4.1 and 4.2, and they seem correct.", "experimental_designs_or_analyses": "I have concerns regarding the statistical significance of many of the SOTA results claimed by the paper and are detailed in point 2 of the \"Claims And Evidence\" part of the review.", "relation_to_broader_scientific_literature": "Position/Structural encodings for graph transformers is an active and important area of research. This paper builds on an existing SE framework (GRIT) and proposes two new encodings, resulting in a broadening of the library of SEs presented in literature.", "essential_references_not_discussed": "None noted", "other_strengths_and_weaknesses": "Strengths:\n- The paper is well written, with easy to follow text and math.\n- The development of the GRIT framework with well-motivated SE initializations is a valuable contribution.\n- Experimental results are provided on a large collection of benchmarks.\n- A well-chosen set of theorems and proofs is included in the paper.\n\nWeaknesses:\n- Since the paper is presenting general SEs that could be used with many base graph-transformer architectures, it would be necessary to see results on all datasets with architectures other than GRIT in the main text. Currently results are only presented for some datasets in the Appendix.", "other_comments_or_suggestions": "None", "questions_for_authors": "- My main concern with this paper is regarding the strength of empirical results presented. This concern is described in the second point of \"Claims And Evidence,\" and I would request the authors to take action to improve the statistical significance of the results presented.\n\n- Isn't GKSE a linear transformation of RRWP? In that case, could the network not easily learn GKSE from RRWP in the first layer itself?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "MvtSfTlDdy", "reviewer": "Reviewer_342d", "summary": "This paper proposes a new graph transformer model using Green and Martin kernels. Specifically, GKSE and MKSE are defined as the structural encoding (SE) using Finite-Step Green Kernel and approximated finite-step Martin Kernel, respectively. They are used as the graph transformer's attention mechanism.\n\nTheoretical analysis compares the representational power of the proposed methods, GKSE and MKSE, with other SEs. Numerical experiments apply graph transformers with GKSE and MKSE to graph prediction tasks to evaluate practical performances. In addition, encodings of molecules (aperiodic graphs) and circuits (DAGs) are visualized to tweak the factors that improve the prediction performances.\n\n## Update after rebuttal\nI thank the authors for responding to my review comments. I am satisfied with them. Although the numerical evaluations are rigorous, they are not significant enough to be eligible for strong acceptance, even though the novelty and significance lie in the theoretical aspects. Therefore, I keep my score (4. accept)", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer for the constructive and encouraging feedback. We are glad that the mathematical rigor, clarity, and structure of our paper were positively noted. Below, we address each comment in detail.\n\n---\n\n### 1. Motivation and Problem Statement\n\nWe appreciate the suggestion to clarify our motivation. Our goal is to connect theoretical kernels from stochastic process theory with structural encodings (SEs) in graph neural networks.\n\nClassical kernels such as Green and Martin kernels capture long-term behavior of random walk and global structural properties. While widely used in potential theory, they are often inapplicable in graph learning due to assumptions like non-finiteness or transience of the graph. As explained in Section 3.3, many such kernels do not extend directly to real-world graphs.\n\nOur contribution lies in reformulating these kernels into scalable and adaptable encodings—GKSE and MKSE—which preserve theoretical grounding while enabling practical use as absolute and relative SEs. This reformulation retains the theoretical meaning while making them usable in practice.\n\n---\n\n### 2. Broader Applicability Beyond GRIT\n\nOur main experiments use GRIT because it separates the effect of SEs and supports both absolute and relative encodings. This makes it ideal for isolating the impact of replacing RRWP with our proposed SEs.\n\nTo demonstrate generality, we also applied our SEs to **CKGConv**, a different GNN architecture (Appendix B.2). These results show consistent gains, indicating our SEs are not GRIT-specific. We plan to expand to more architectures in future versions.\n\n---\n\n### 3. Hyperparameter Sensitivity and Fairness\n\nWe agree that the number of steps \\( K \\) is a key hyperparameter. For the OCB datasets (Ckt-Bench101, Ckt-Bench301), we reused hyperparameters from ZINC due to their similar size and structure (see Tables 6 and 8). We varied \\( K \\) linearly and presented results in Table 11, which show meaningful performance changes and confirm that an optimal \\( K \\) exists.\n\nImportantly, even when \\(K\\) is not finely tuned, our SEs achieve performance comparable to strong baselines, suggesting that they exhibit enough performance without extensive hyperparameter search. This also implies that using smaller \\( K \\) can reduce precomputation time without sacrificing much performance.\n\nWe also evaluated whether similar trends hold for RRWP, a structurally comparable SE. However, we observed that RRWP does not yield the same level of performance as our proposed SEs under similar conditions, further validating the effectiveness of our kernel-based approach. These details will be added to Appendix B.3.\n\n---\n\n### 4. Clarification of SPD (l.253)\n\nSPD stands for **Shortest Path Distance**, defined earlier in line 248. We will ensure the abbreviation is properly introduced upon first use to improve clarity.\n\n---\n\n### 5. Comparison with Prior Work and RRWP\n\nWe appreciate the reviewer’s summary that positions our work within the broader literature on random walk-based SEs. As noted, our method extends this line of research by connecting SEs to well-established mathematical kernels. Unlike methods such as RRWP, which compute expected walk counts over fixed-length paths, GKSE and MKSE derive from limiting behaviors of Markov chains, capturing deeper global structure.\n\nThe instability of RRWP in non-aperiodic or DAG-like graphs is discussed in our experimental results and qualitative analyses (e.g., Figure 1 and 2). These issues are theoretically motivated and practically observable in molecular and circuit datasets.\n\nAdditionally, prior works like [Dwivedi et al. 2022a, Geisler et al. 2023, Zhou et al. 2024] mainly design absolute SEs without supporting relative SEs—a key distinction from our approach.\n\n---\n\n### 6. Summary of Contributions\n\nTo summarize:\n\n- We introduce **GKSE and MKSE**, novel SEs grounded in Green and Martin kernels with strong theoretical backing.\n- These SEs are efficiently computable and compatible with both absolute and relative forms.\n- We show empirical gains in datasets where global or asymmetric structures are important (e.g., PCQM4Mv2, Ckt-Bench101).\n\nWe appreciate the reviewer’s recognition of the mathematical contributions and clarity of our work. We will revise the introduction and implementation sections to better communicate our motivation and ensure reproducibility.\n\n---\n\n### Conclusion\n\nWe thank the reviewer once again for the detailed and constructive feedback. Your comments have helped refine both our presentation and experimental justification. We are encouraged by your evaluation and will incorporate all suggestions in the final version.", "claims_and_evidence": "This paper makes the following claims about GKSE and MKSE:\n\n1. High performance in prediction tasks on various sizes of graph benchmark datasets.\n2. Ability to capture long-range interactions.\n3. High performance on molecular graphs, including aperiodic graphs, and circuit graphs, including DAGs.\n\nThese claims are well-supported by evidence for the following reasons:\n1. Datasets with various average node sizes are adopted (Table 5.)\n2. Long-range datasets are adopted (Table 2.) \n3. Molecular dataset (PCQM4Mv2) and circuite dataset (Ckt-Bench101, Ckt-Bench301) are adopted.\n\n\nThis paper also claims in the abstract that the proposed method is theoretically grounded. This claim is well-supported because of the theoretical guarantees on the representation capability (Theorem 4.3, Corollary 4.4, Theorem 4.5) and the quantitative approximation between the Kernel used in MKSE and the finite-step Martin Kernel (Theorem 4.2).", "methods_and_evaluation_criteria": "If I do not miss any information, it is not indicated (at least explicitly) what kind of problem this paper wants to solve or what kind of issues the existing Graph Transformer research has (in my understanding, this paper's motivation for employing Green and the Martin Kernels is that Graph Kernel theory suggests that it captures the topology of graphs.) However, the numerical experiments employ diverse datasets and baseline models, which is appropriate for supporting claims 1--3 above.", "theoretical_claims": "I check the proof of the theorems in the Appendix. I did not check it rigorously enough to reproduce the proof by myself. However, as far as I check, I do not find any critical mistakes. In addition, the mathematical statements and proofs are clearly written and easy to read.", "experimental_designs_or_analyses": "The proposed methods are applied to GRIT only in the main text. However, CKGCN, another type of graph transformer, is employed in the Appendix (Section B.2). Therefore, the performance improvement is not specific to a particular type of graph transformer, although it is difficult to say that the proposed methods are universally effective.\n\nRegarding hyperparameters, sensitivity analysis is performed for the number of steps $K$, which is the most important parameter. However, since it is not explicitly stated how the hyperparameter search is conducted (unless I missed it), I cannot judge whether comparing the proposed and baseline methods is fair in terms of hyperparameter choice.", "relation_to_broader_scientific_literature": "Methods for structural encoding using random walks on graphs were proposed by [Dwivedi et al. 2022a, Geisler et al. 2023, Ma et al. 2023a, Zhou et al. 2024]. Since this paper proposes new methods of structural encoding using Green and Martin Kernels, which are random-walk-based kernels that capture a graph's topology, we can place this paper in this line of research. The issues of existing studies are not explicitly stated in the abstract or introduction. However, for RRWP [Ma et al., 2023a], this paper points out in the experiments that it is unstable in aperiodic graphs and DAGs and that the proposed methods solve this problem.", "essential_references_not_discussed": "To the best of my knowledge, I do not find any references that are not cited.", "other_strengths_and_weaknesses": "The paper is clear and readable. The organization is good, and the mathematical description is accurate and easy to read. In addition, the appendix provides basic knowledge about Markov chains on graphs, which makes the paper accessible to those who are not familiar with this field.", "other_comments_or_suggestions": "- l.253 (right): What does SPD stand for?", "questions_for_authors": "N.A.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {"ethical_review_concerns": "N.A."}}]

Author rebuttal:

Meta-review: This paper suggests strucutural encodings for graph transformers via random walks based on the Green and Martin Kernels. Results across multiple benchmarks were consistenly better, often but not always very marginally so. The reviewers had no argument with the soundness of the paper, but some of them were not convinced by the importance of the problem or significance of the empirical results. I recommend acceptance, if there is room, since overall this paper present a novel idea, with theoretical grounding and reasonably good empirical results.
Decision: Accept (poster)