Simple Path Structural Encoding for Graph Transformers
Authors: Louis Airale
Antonio Longa
Mattia Rigon
Andrea Passerini
Roberto Passerone
Venue: ICML 2025 poster (2025)
Keywords: Graph transformer
structural encoding
simple paths
Primary area: deep_learning->graph_neural_networks
TL;DR: We present a structural encoding based on simple path counts for graph transformer, with theoretical and experimental validation.

Abstract: Graph transformers extend global self-attention to graph-structured data, achieving notable success in graph learning. Recently, Relative Random Walk Probabilities (RRWP) has been found to further enhance their predictive power by encoding both structural and positional information into the edge representation. However, RRWP cannot always distinguish between edges that belong to different local graph patterns, which reduces its ability to capture the full structural complexity of graphs.
This work introduces Simple Path Structural Encoding (SPSE), a novel method that utilizes simple path counts for edge encoding. We show theoretically and experimentally that SPSE overcomes the limitations of RRWP, providing a richer representation of graph structures, particularly in capturing local cyclic patterns. To make SPSE computationally tractable, we propose an efficient approximate algorithm for simple path counting.
SPSE demonstrates significant performance improvements over RRWP on various benchmarks, including molecular and long-range graph datasets, achieving statistically significant gains in discriminative tasks. These results pose SPSE as a powerful edge encoding alternative for enhancing the expressivity of graph transformers.

Simple Path Structural Encoding for Graph Transformers
Louis Airale'
Antonio Longa'
Mattia Rigon'
Andrea Passerini
Roberto Passerone'
Abstract
2022; Lachi et al., 2024; Ferrini al., 2024; Duta & Liò,
Graph transformers extend global self-attention to graph-structured data, achieving notable suc- cess in graph learning. Recently, Relative Ran- dom Walk Probabilities (RRWP) has been found to further enhance their predictive power by en- coding both structural and positional information into the edge representation. However, RRWP cannot always distinguish between edges that be- long to different local graph patterns, which re- duces its ability to capture the full structural com- plexity of graphs. This work introduces Simple Path Structural Encoding (SPSE), a novel method that utilizes simple path counts for edge encod- ing. We show theoretically and experimentally that SPSE overcomes the limitations of RRWP, providing richer representation of graph struc- tures, particularly for capturing local cyclic pat- terns. To make SPSE computationally tractable, we propose an efficient approximate algorithm for simple path counting. SPSE demonstrates sig- nificant performance improvements over RRWP various benchmarks, including molecular and long-range graph datasets, achieving statistically significant gains in discriminative tasks. These results pose SPSE as a powerful edge encoding alternative for enhancing the expressivity graph transformers.
2024), yet these models often face challenges in capturing long- long-range dependencies and structural patterns due to their reliance on localized message passing (Alon & Yahav, 2021; Topping et al., 2022).
Inspired by their success in vision and sequence learning tasks (Vaswani, 2017; Dosovitskiy al., 2021). transform- ers have been extended to graph learning problems (Yun et al., 2019; Dwivedi & Bresson, 2020; Ying et al., 2021; Kreuzer et al., 2021). Unlike traditional GNNs, graph trans- formers leverage global self-attention,, allowing each node to attend to all others within a graph, regardless of dis- tance. This flexibility overcomes the limitations of message- passing approaches but introduces new challenges, particu- larly in designing suitable positional and structural encod- ings that capture the inherent irregularities of graphs
For directed acyclic graphs (DAGs), positional encod- ings (PEs) based on partial orderings can be directly ap- plied (Dong et al., 2022; Luo et al., 2024b; Hwang et al., 2024). However, for general undirected graphs, success- ful PEs often rely on eigendecoompsitions of the graph Laplacian, drawing inspiration from sinusoidal encodings in sequence transformers (Dwivedi & Bresson, 2020; Mialon et al., 2021). These approaches encode node-level informa- tion but fail to capture the full structural complexity of edge patterns in node neighborhoods.
To address this limitation, several graph transformer archi- tectures incorporate initial message-passing steps encode local substructures (Wu al., 2021; Mialon et al., 2021; Chen et al., 2022). While effective, these methods focus solely on node representations and do not exploit the poten- tial of injecting pairwise structural encodings directly into the self-attention mechanism. Recent studies have explored structural edge encodings in pure transformer architectures, based for instance on Laplacian eigenvectors, heat kernels, or shortest path distances (Kreuzer et al., 2021; Ying et al., 2021; Chen et al., 2023), Despite their utility, these encod- ings are limited in expressivity, particularly for capturing local cyclic patterns or higher-order substructures.
1. Introduction
Graphs are pervasive across diverse domains, representing complex relationships in areas such as social networks (Otte Rousseau, 2002), molecular structures (Quinn et al., 2017), and citation graphs (Radicchi et al., 2011). Recent ad- vances in graph neural networks (GNNs) have driven signif- icant progress in learning from graph-structure data (Kipf & Welling, 2017; Veličković et al., 2018; Bodnar et al.,
'University of Trento, Trento, Italy. Correspondence to: Louis Airale airiiiiaiaalluuii....ii Roberto Passcrone <roberto, croberto.passeroneee @unitrrneeunit.it>>.......... un?...it>>.
A promising alternative is the use of random walks as a structural encoding method (hereafter RRWP for Relative Random Walk Probabilities following Ma al. (2023)). whereby richer structural information is encoded at the
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Simple Path Structural Encoding for Graph Transformers
edge level by considering random walk probabilities, and which has led substantial improvements in the perfor- mance of state-of-the-art graph transformers (Ma et al., 2023; Menegaux et al., 2023). However, RRWP struggles to differentiate between distinct graph structures in certain cases. Meanwhile, parallel research on message-passinng GNNs has demonstrated the benefits of simple paths (or self- avoiding walks) in enhancing model expressivity beyond the 1-Weisneile--Leman (WL. isomorphism test (Michel et al., 2023; Graziani et al., 2024). These findings moti- vate the exploration of simple paths as structural encoding mechanism in graph transformers.
between nodes and j. and zero otherwise. The diago- nal degree matrix D E TR(V) is a square matrix where the diagonal element Di, represents the degree of node i. Formally, D = Ej Ai,j and Da.j = 0 for i $ Definition 2.1 (Walk). Given a graph G, a walk is a fi- nite sequence of nodes vo. V1...., Um where each consec- utive pair of nodes (vi, (441) is connected by an edge, iee, (Va, V++1) E E. The number of edges in walk is referred to as the walk length.
Definition 2.2 (Simple Path). A simple path (here indiffer- ently called path), is a walk in which all nodes are distinct. The number of edges in a simple path is called the simple path length (or path length). Paths themselves constitute graphs called path graphs. The distance between two nodes is the length of the shortest path between these two nodes. Definition 2.3 (Cycle). A eycle is a walk where all nodes are distinct, except for the first and last ones which are identical. A graph composed of single cycle is a cycle graph.
In this work, we introduce Simple Path Structural En- coding (SPSE), a novel method for structural edge encod- ing that replaces RRWP in graph transformers. SPSE en- codes graph structure by counting simple paths of varying lengths between node pairs, capturing richer structural infor- mation than random walks. To address the computational challenges encountered when exact simple path counting is unfeasible, we propose an efficient algorithm based on successive DAG decompositions using depth-first search (DFS) and breadth-first search (BFS). This approach avoids the exponential memory costs of path enumeration, enabling scalability to long path lengths.
Definition 2.4 (Random Walk Matrix). Given a graph G and k E N the k--op random walk matrix Ps E IR [ gives the landing probabilities of random walks of length k between all pairs of nodes. Its closed-form expression is Ps = (D-1A)
We validate SPSE on extensive benchmarks, including molecular datasets from Benchmarking GNNs (Dwivedi et al., 2023). Long-Range Graph Benchmarks (Dwivedi et al., 2022), and Large-Scall Graph Regression Bench- marks (Hu et al.. 2021). SPSE consistently outperforms RRWP in graph-level and node-level tasks, demonstrat- ing significant improvements in molecular and long-range datasets. We also characterize limit cases of the algorithm, and identify situations in which the performance might be more sensitive to approximate path counts.
Definition 2.5 (Simple Path Matrix). Similarly, we refer to the k-hop simple path matrix Sy E N/VIXIV as the matrix where the (i. )-th entry, (Sk) is the number of simple paths of length k from node to node j.
Unlike PR. S₃ does not have a closed-form solution, and computing it is computationally expensive (Vassilevska & Williams, 2009). In the following, we focus on the proper- ties of pairs of nodes (i. E V x V through different edge encoding methodologies. To facilitate the comparison with the encoding of another pair of nodes (I', in second graph G', we introduce the following equivalence relation for k 2 1:
The remainder of this paper is structured as follows. Sec- tion introduces key concepts and notations. Section 3 analyzes the limitations of RRWP and motivates SPSE. The proposed path-counting algorithm and encoding method are detailed in Section 4. Finally, experimental results and related works are discussed in Sections 5 and 6, respectively.
(1,1)8 (F'5'')'''' = (Px)s) (PWey.
where Pg is the k-hop random walk matrix of graph G'. Note that this does not require G' to have the same number of nodes as G. This can be generalized as:
2. Preliminaries
(i.j)² =n (1',5")'' + Vk N" (1.)) Sew (('j"))'
2.1. Graph Theory
The same equivalence relations can be defined for simple paths (writing- sp and =sp) by substituting Pe and P with S₁ and Sy
Let G = (V,,, X) be a graph, where V is the set of nodes, 3 3 V x is the set of edges, and X E R represents the node features of dimension d. The adjacency matrix A E {0, 1 is a square matrix that represents the connectivity of the graph, i.e. Aij is one if there is an edge
2.2. RRWP encoding in Graph Transformers
Pure graph transformers, which do not use any MPNN layer, typically encode structural and positional informa- tion directly in the self-attention layer. To compute the
'The Python implementation of the algorithm is available the project's Github page.
2

---

Simple Path Structural Encoding for Graph Transformers
RRWP matrix Egw. all k-hop random walk matrices up to maximum walk length K are concatenated into a matrix P = IP,,.... ,K] E [o, 1| which is then en- coded through a shallow neural network @ that maps K to a (usually larger) dimension d (Menegaux et al., 2023; Ma et al., 2023): Vnw = (PP) E X Egw both acts as a relative positional encoding, since contains the short- est path distance between nodes, and as a structural edge encoding, since walks encode information about the visited sub-structures. As standard positional encoding, it biases the pair-wise alignment between nodes given by the atten- tion matrix. Very generally, the resulting self-attention layer can be written as follows, where the precise implementation of Φi and 2e varies among different methods:
(A)
(B)
(D)
10.1)8a (0,1)0x
(0, (0.1) = (0,1)8o
10.1 the (0, 1)
(0. 10 Ahe (0, 1)00
Figure 1. RRWP encodes identically edges from very distinct graphs which are separated by SPSE (see the tree decomposi- tions in Appendix D)
cases of the following result which links RRWP edge en- codings in even-length cycle graphs and linear graphs (all proofs can be found in Appendix C):
ai th (WOI, xy; WK,,, Vz,, (gs)
az
aij Ex aix
(2)
Proposition 1. Let g = (V, E) be an even-length cycle graph, i.e. [V] = 2n for some n E N and G' = (V', a path graph such that [V = 2n + Then given any pair of nodes (i. in G, there exists a pair of nodes (V'.j) in G' such that (i. =Rw (1',"")
y1 Σ aiyo2(WV xj, (En))s))
(3)
with v; and xy the features of nodes and j. WQ, W and WV the query, key and value matrices, and yı the output from the self-attention layer for node i.
Each pair of nodes in even-length cycle graph is thus equivalent, under RRWP encoding, another pair of nodes in a linear graph (note that i and need not be adjacent). In other words, random walks transition probabilities cannot be used to distinguish between even-length cycles and paths when considering single node pairs. On the other end, it is easy to show that this does not apply to SPSE encoding (see Figure 1). This result illustrates how random walk-based structural encoding may fail to capture critical structural differences between node pairs, hence possibly leading to suboptimal performances of the overall graph transformer model.
3. Theoretical Properties of RRWP and SPSE
In this section, we highlight the limitations of RRWP in dis- tinguishing different graph structures, as it can assign iden- tical transition probabilities to edges in distinct topologies, potentially leading to suboptimal performance. Conversely, we show that SPSE naturally captures cycle-related infor- mation. In particular, SPSE enables cycle counting, which is crucial in applications such as molecular chemistry (c.g.. identifying functional groups like aromatic rings) (May & Steinbeck, 2014; Agúndez et al., 2023), social network anal- ysis (c.g., detecting communities) (Radicchi et al., 2004; Dhilber & Bhavani, 2020), and circuit design (e.g., analyz- ing feedback loops) (Horowitz et al., 1989).
It is also possible to prove a more general result about the ambiguities of RRWP by leveraging the fact that random walks measure probabilities rather than absolute counts. In particular, the following proposition can be easily proven by induction by considering central symmetries around des- tination node j.
3.1. Limitations of RRWP for Edge Encoding
Random walk probabilities possess the great advantage of being computable in closed form. However, their use intro- duces certain ambiguities, as illustrated in Figure 1. In these two examples, 9 and Go are cycle graphs, GB and GD are path graphs, and yet the following two relations hold (see Appendix D for a graphical proof up depth of 5):
Proposition' 2. Let G = (V,E) be graph and (i.j) E V x V a pair of nodes in G. Then there exists a non-isomorphi
graph g' = =V", E') ')annd a pair of nodes (i', (") E V V such that (i.j)ō =xw (i' "'''"'0"' i.e. (i.5) and (i', (") are equivalent under RRWP encoding.
The RRWP encoding of a pair of nodes is therefore never unique, and cannot be used to identify graph. Of course this is also obviously true for SPSE encoding. However, proving this result for adjacent nodes, in the cases of simple paths, still requires preserving the set of paths that connect them. This hints at the fact that the information contained in simple path edge encodings may be used to distinguish
(0, f) Rw (0, 1)
(0, 1) =aw (0, 9
Although the edges belong to clearly different graphs RRWP assigns them the same transition probabilities in the cycle and path graphs. These examples are two special
3

---

Simple Path Structural Encoding for Graph Transformers
certain local graph structures, as we discuss in the next section.
Algorithm 1 Count paths between all pairs of nodes (sim- plified)
1: Parameters: Proportion of root nodes R, maximum length K, maximum DFS depth DreS, maximum trial number NV
3.2. SPSE through the Prism of Cycle Counting
The relation between path and cycle counting has been well studied (Perepechko & Voropaev, 2009; Graziani et al., 2024). The following result, which was introduced by Perepechko & Voropaev (2009), connects SPSE encoding with cycle counting for adjacent nodes:
2: Input: Undirected graph G = (V,E)
3: Output: Path count matrix M NIVIXMI
4: M < x {Initialize count matrix)
5: NODES + DRAWNODES(RR, V) {Select R [V] nodes
from V}
for each v in NODES do
Proposition 3. Let (i, be two adjacent nodes in a graph - (V),,, ie. (i.j) E E, and Sy the k-hop simple path matrix of 9 for any k E N", such that (Sx)sz = ma E N. Then for k 2 2, there are exactly my cycles of length & + in G that admit [i as an edge.
7: DAGS + DAGIDECOMPOSEGG v. DDES, N)
[Reirieve list of node permutations starting with v} 8: for each DAG in DAGS do
9: M < UPDATE(M, DAG) {Update total path count} 10: end for
The case of k 1 simply corresponds to the number of parallel edges between nodes and j. Note that this is not the same as giving the number of cycles that possess i and j as vertices. Two illustrations of this result are presented in Figure? 2. Here, (Si)o1 = (Ss)o: = 1 unambiguously defines the edge (0, 1) as belonging to a six-atom cycle. In a second example, SPSE uniquely encodes the double carbon-oxygen bond of any carboxylic acid group. Note that Proposition 3 however does not hold if (i, & &, and that no equivalent result exists for RRWP since the landing probabilities can be made arbitrarily low by the addition of new edges to a cycle's nodes.
11: end for
12: Return: M
4. Simple Path Structural Encoding
It has been shown that the composition of MPNN layers paths is more expressive than the 1-WL test (Michel et al., 2023; Graziani et al., 2024). However, due to the combinatorial complexity of the problem, enumerating all paths beyond short path lengths becomes impractical. Re- sults from Section 3 indicate that counting distinct paths between nodes, while requiring significantly less memory, still possesses theoretical advantages over random walk probabilities an edge structural encoding method. This approach, however, introduces two challenges. First, while existing path-counting algorithms efficiently handle short paths (Perepechko & Voropaev, 2009; Giscard et al., 2019), certain graph topologies and path lengths necessitate approx- imate methods. Second, since the number of paths between two nodes can grow exponentially (bounded by ((V)2)) (IV- for length-k paths in a complete graph), an appropriate en- coding function is required. This section addresses both challenges.
This analysis of structural encodings through the lens of cycles therefore showcases structures for which SPSE is provably more informative than RRWP encoding.
Finally, while the results presented here focus on edge rep- resentations, we refer to Appendix B for a discussion on the expressivity of SPSE regarding graph isomorphism.
(R)
(A)
(C)
OH
*
(D)
4.1. Simple Path Counting
O1l
The SPSE encoding can accommodate any exact or approxi- mate path counting method, although the former are usually restricted to sparse graphs or short path lengths. On the other hand, approximate path counting methods are required when the density of the considered graphs prevents the use of exact methods.
(0, 1)0a Am 1)0a
(C=0)5c Fin (C=
(0, 1104- =. (0, 1)
(0=0) -ay O0=0
Figure 2. SPSE edge encoding of adjacent nodes characterizes the cycles to which the edge belongs. Thus honds in the 6-atom cycles of (A) and (B) are encoded identically (they both belong to a single such cycle), and so are the (C=0) bonds of (C) and (D).
The approximate method followed here relies on the extrac- tion of node orderings from an input undirected graph. Any such ordering can be used to turn the graph into a DAG, which allows to count paths by computing powers of the re-
4

---

Simple Path Structural Encoding for Graph Transformers
Algorithm DAGDECOMPOSE: Decomposition of in-
put graph into multiple DAGs
Parameters: Maximum DFS depth Dors, maximum trial
(1) Partial BFS step
number N
Input: Graph G (V,E), root node r, diameter MAAX
Output: List of node orderings II
Initialize II + EmptyList
(2) BFS step
for does = 0 to DEE do
for n = 1 to N do
Initialize f- EmptyList while π * V do for d = to DMAX do
(3) Random ordering of bodes the same level
if d < does then
π + DFS((, G, T)) {Start with dars DFS steps)
Figure 3. Discovering the two paths of length 3 between nodes 0 and in this Circular Skip Link graph requires partial BFS step in either 0 or 1 (not all child nodes are explored), followed by a BFS step. Nodes that are discovered concurrently are given an arbitrary order, allowing to travel back in the graph.
else d= dors then
x < PARTIALBES((, 9.
else
t BFS(r, G, π) {Continue with as many
BFS steps possible)
end if
end for end while
tion). Additional parameters include a repetition number N which accounts for random effects, such as the direc- tion taken by the DFS, and a parameter R controlling the proportion of root nodes. The computational cost is dom- inated by the powers of the adjacency matrix which must be computed for each DAG, for maximal complexity of O K (DDors-Ni11)) The additional factor RDpes can be of the order of tens to hundreds depending on the input graph, which makes SPSE calculation significantly more expensive than RRWP. This needs however to be computed only once a pre-processing step, and it is also much less than the total number of possible DAG decompositions 2 highlighting the effectiveness of the tree decomposition ap- proach. We discuss the choice of hyperparameters and their importance regarding path counts in Section 5.3 and provide actual values in Appendix A.
IT < ADD(II, T) (Append a to II}
end for end for Return: 11
sulting adjacency matrix. For paths of length K, this process incurs a computational complexity of 3) Different DAG decompositions of the input undirected graph allow the exploration of different paths, leading to increasingly more accurate path counts. We summarize the overall proce- dure in Algorithm 1. The detailed version of this algorithm can be found in Appendix E. It consists in updating run- ning path counts for all pairs of nodes and path length k; by comparing the counts yielded by each DAG with the stored values, and then storing the maximum of the two. The DAG mining function is presented in Algorithm Starting from root node, it decomposes graph into tree by combining DFS and BFS: DFS search is initiated at given root node, updating a list which is incremented with each newly visited node. After it reaches distance Drs from the root node, the search switches to BFS until cannot proceed further, and the whole process repeated until all nodes are visited.
4.2. Path Count Encoding
Compositions of logarithm functions are used to map the
obtained path count matrix S = =SS1... ... SK] to a manage- able value range for subsequent neural networks, as total counts can grow very large. Using superscript to denote the composition of function with itself, mapping f for a total count x::
the following
DAG can be obtained from the node ordering by directing edges towards nodes of higher indices. DFS allows long path discoveries but cannot simultaneously discover more than one path between nodes, while BFS alone will typically miss long paths, hence their use in combination. We add a partial BFS step between the two, which randomly explores a subset of the child nodes, thus allowing to travel through otherwise inaccessible paths (see Figure for an illustra-
+: +
(4)
with 9 + In(1 + r), and a, B and n being hyper- parameters to be adjusted for different graph collections. Normalized path counts f(S) can then be used in place of the random walk matrix P as input to the edge encoding network of graph transformer models, yielding the SPSE matrix Esp which replaces Faw in equations and
5

---

Simple Path Structural Encoding for Graph Transformers
5. Experiments
Clasuiication accusac
0.90
0.85
4
0.900
We first validate Proposition experimentally through a syn- thetic experiment (Section 5.1), and demonstrate the empiri- cal superiority of SPSE on real-world datasets (Section 5.2). We then present an ablation study on the algorithm parame- ters (Section 5.3) and discuss limitations (Section 5.4).
0.80
0. 1.990
0.996
0.75
0.985
0.70
GFLOPS (CONFIO
92)
GRI++SPSE
RRIP-
CSA+SPSE
CSA+RRWP
5.1. Cycle Counting Synthetic Experiment
Synthetic Dataset. To validate Proposition 3, we design synthetic dataset consisting of 12,000 graphs. Each graph is generated by randomly adding cycles of lengths between 3 and 8 until the total count for each cycle length reaches a value between 0 and 14. This process results in graphs with an average of 149 nodes and 190 edges. The dataset is split into training (10,000 graphs), validation (1,000 graphs), and test (1,000 graphs) sets. The objective is to determine the number of cycles for each of the six cycle lengths. We frame this as six simultaneous multiclass classification tasks and evaluate performance using mean accuracy. Examples of the generated graphs are provided in Appendix F.
Figure 4. Cycle counting accuracies for three training configura- tions of CSA and GRIT with either RRWP or SPSE edge encoding.
5.2. Real-World Benchmarks
Datasets. We conduct experiments on graph datasets from three distinct benchmarks, covering both node- and graph- level tasks. These include ZINC, CLUSTER, PATTERN, MNIST, and CIFARIO from Benchmarking GNNs (Dwivedi et al., 2023), from the Long-Range Graph Benchmark (Dwivedi et al., 2022), and the 3.7M-sample PCQM4Mv2 dataset from the Large-scale Graph Regression Benchmark (Hu et al., 2021). We shall see in Section 5.3 how constraints imposed by graph complexity and dataset sizes impact the path count precision in molecular datasets (ZINC, the two Peptides & PCQM4Mv2), image superpixel (MNIST & CIFARIO) and Stochastic Block Model (SBM) (PATTERN & CLUSTER) benchmarks, justifying a differenciated treatment.
lenniide-functionall and Peptides-structte structural
Models. We build upon two tfateoofthh--an art graph trans- former models that use RRWP as an edge encoding method: GRIT (Ma al., 2023) and CSA (Menegaux al., 2023). SPSE can seamlessly replace RRWP in these models by substituting the encoding matrix Esp, which captures path counts, for Egw in equations 1 and 3. To evaluate per- formance on the cycle counting task, we train these mod- els using three hyperparameter configurations adopted from (Menegaux et al., 2023). These correspond the setups used for ZINC (config #1), PATTERN (config #2), and CIFAR10 (config #3), covering a range of model com- plexities from 40 to 280 gigaflops. This provides compre- hensive assessment of the impact of the two edge encoding methods across diverse settings.
Experimental Setup. As before we replace RRWP with SPSE in GRIT and CSA. We also explore adding SPSE to the well-known GraphGPS model (Rampášek et al., 2022), in which case the edge encoding is restricted to the elements of E, and is only used to produce node-level positional encodings in the MPNN layer. In all cases, for better result robustness, we retrain the original model and the SPSE version on len random seeds (one seed for the large PCQM4Mv2) using the released training configurations, with two exceptions: the unstable CSA learning rate for ZINC reduced by factor 2, and configuration files are added train CSA on Peptides.
Results. The test accuracy for both model architectures across the three training configurations is reported in Fig- ure 4, along with standard deviations computed over 10 runs with different random seeds.
It is important to emphasize that no hyperparameter tun- ing is performed. This decision ensures a fair and unbi- ased comparison, isolating the contribution of SPSE as a drop-in replacement for RRWP, and demonstrating its effec- tiveness across different architectures without the need for task-specific adjustments.
In all but one case, SPSE encoding achieves significantly higher cycle counting accuracy than RRWP. All models learn to count cycles almost perfectly under the third train- ing configuration, which suggests that deep architectures can compensate for expressivity limitations in the edge encoding matrix (see Appendix F for details on configurations). How- ever, SPSE still performs significantly better than RRWP for CSA in this setting.
Note that replacing walks by path count is done at no addi- tional cost as the number of trainable parameters remains unchanged. Two-sided Student's t-tests are conducted to assess the significance of the obtained results. Finally, we compare with the following GNN methods: GCN (Kipf & Welling, 2017), GIN (Xu et al., 2019), GAT (Veličković
These results empirically validate the superior ability of simple paths to characterize cycles when used as an edge encoding method in graph transformers.
6

---

Simple Path Structural Encoding for Graph Transformers
Table 1. Test results on all eight benchmarks. GPS, CSA & GRIT w/ and w/o SPSE were re-trained on 10 random seeds (hence variations from seminal works) on all datasets (one run for PCQM4Mv2). Underline indicates difference between a baseline and the SPSE model version, and is used for significant gaps based on two-sided t-test (p-value I 0.05). Highlighted are best, second, and third best scores. GPS++GPS was not retrained and is therefore treated separately.
Molecular
SBM
Superpixel
Model
ZINC
Peptides-func
Peptides-struct
PCQM4MY2
PATTERN
CLUSTER
MNIST
CIFARIO
MAR
AP
M
MAE.
Accuracy
Accuracy
Accuracy
Accuracy 1
GCN
0.367 0.011
0.1379
71.892 = 0.331
68.198 = 0.976
90,705 = 0.218
GIN
0.526 2 0.051
0.1196
85,387 =: 0.136
61.716 1: 1.553
96,485 = 0.252
25.255 1: 1.327
GAT
+.00
78:271 + 0.186
70.587 + 0.447
95.535 = 0.205
64.223
0.455
GINE
0.5498 + 0.0079
0.3547
0.0045
GatedGCN
0.202++0.015
85.508 + 0.088
73.840 + 0.326
97.340 + 0.143
67.312 + 0.311
GIN-AK+
0.080 0.001
86.850 0.057
72.190 0.130
SAN (+RRWP)
0 0.006
0.6439 + 0.0075
0.2544 0.0012
86.581 + 0.037
76.691 0.65
Graphormer
0.122 0.006
0.0864
BUT
0,108 2 0.000
86,821 + 0.0220
79.232 1: 0.348
98,173 1: 0
68. 7U2 1 0.409
GTT
0.073 1. 0.001
0.6970 1 0.0080
0.2475
0.0015
97.422 1. 0.110
73.961 1 0.330
Exphormer
0.6527
0.0013
0.2181 0
86.7-1 0.015
78.071
0:037
0.039 98.550
74.696 0.125
Drew
0,7150 + 0.0044
0.2536 + 0.0015
GPS + GPSE!
0.065 + 0.003
0.0688 + 0.0151
0,2464 + 0.0025
98.08 = 0.13
72.31 + 0.25
SPSE used in MPNN for node representation
GPS
0.070+0.003
0.6801 0.0061
0.2509 0.0017
0.09122
06.698=000073
77.969 161
98.061
72. 72.0977+0.77
GPS+ SPSE (ours)
0.008++0.003
0.6608 + 0.0063
0.2506 + 0.0010
0.0034
86.634+00.05*
78.440++0.177
38.105+0.115
72. 14-+044-0
RW/SPSE used as edge feature in self-attention leyers
CSA-RRWP
0.069:10.000 003
0.6513 + 0.0061
0,2486 0.0012
0,0918
$7.008110.162
79.071 1:0. 1210
98.127 123
73.885:10.348
CSA-SPSE (ours)
0.001=
0.6600 0.009g
0,2482 0,0019
0.0911
87.064++0.022
78.9-10+0.10 132
98.269=0.078*
73.8 03.897+0.521
GRIT-RRWP
0.065:10005
0.680321000085
0,2480 0.0025
0,0838
87,229:00006
19.730
98,281=0.1997
76.246:10.954
GRIT-SPSE (owrs)
0.059
0.6941-0.0113'
0.2449:1.00118
0.0831
87.235=00.040
79.571=:0:122
98.294=0.147
77.022=004400
al., 2018), GatedGCN (Bresson & Laurent, 2017) and GIN-AK+ (Zhao et 2022), along with the graph trans- formers: SAN (Kreuzer et al., 2021), Graphormer (Ying et al., 2021), EGT (Hussain et al., 2022), Graph ViT (He et al., 2023), Exphormer (Shirzad et al., 2023), Drew (Gut- teridge et al., 2023) and GPSE (Cantürk et al., 2024). Re- sults are reported in Table 1.
edge encoding. In contrast, pure graph transformers do not benefit from SPSE on CLUSTER. A possible explanation is the increased difficulty of accurately counting paths in the densely connected SBM graphs, leading to underestimated counts. Further details on these limitations are provided in Section 5.4.
5.3. Path Count Sensitivity to Hyperparameters
Results and Discussion Replacing RRWP with SPSE im- proves performance in 21 out of 24 cases (underlined in Table 1), with variations depending on the benchmark and model. The most notable gains are observed for CSA and GRIT on molecular graphs, where SPSE achieves statisti- cally significant improvements in 5 out of 6 cases (marked with "*"). Improvements are also evident superpixel benchmarks, with two cases showing statistically significant differences, on both CSA and GRIT. These results indicate that leveraging the full structural encoding matrix in self- attention layers, rather than restricting it to & as done in GPS. an effective strategy for enhancing performance. The limited improvement for GPS is however also likely due to the constraint of leaving the total number of param- eters unchanged. In practice, this amounts to reducing the dimensionality of existing edge embeddings when using SPSE, limiting its potential benefit. This explanation is fur- ther supported by the significant improvements observed on SBM benchmarks, where GPS does not incorporate any
In this section, we examine how the number of paths dis- covered by Algorithm is affected by variations in hyper- parameters across different benchmarks. Those parameters are the proportion of root nodes R. the maximum DFS depth DaEs and the number of trials N (path length K is fixed to walk lengths). ZINC, PATTERN, and MNIST are used as representative benchmarks for molecular graphs, SBM, and superpixels, respectively. We measure the aver- age proportion of discovered paths relative to a canonical configuration (reported in Appendix A) and the computa- tion time per sample while varying a single hyperparameter. Results are reported in Figure 5, with path count proportions as solid lines (left y-axis) and computation time as dashed lines (right y-axis). The main parameter controlling the path count precision for ZINC and other molecular datasets is the root node proportion R which can be set to its maximum value (R = 1) due to its low computational cost. In contrast, DFS depth and the number of trials have little to no impact
7

---

Simple Path Structural Encoding for Graph Transformers
10a
10
Path count max contig
1.6
1.0
Path Count
Counting time sample
ZINC
1.4
101
104
PATTERN
1.2
10
1.0
MNIST
0.6
Time sample
100
0.4
10a
ZINC
0.6
109
PATTERN
0.4
0.2
MNIST
2
4
8
10
12
0.2
0.4
0.6
0.8
1.0
Trial number
depth
Root prop.
Figure Proportion of discovered paths and computation time per sample when varying one hyperparameter at a time, across ZINC, PATTERN, and MNIST datasets. Solid lines (left y-axis) represent the proportion of discovered paths, while dashed lines (right y-axis) indicate computation time per graph sample.
on path counts and can be kept at moderate or low values. MNIST benefits almost equally from increases in all three hyperparameters, though adjusting DoEs offers the lowest computational overhead. Notably, the trade-off setting of
N = 2, imposed by the large size of the dataset, results in approximately 40% fewer discovered paths compared to N = 8, potentially leading to suboptimal learning accuracy. For the PATTERN dataset, we prioritize increasing N over other hyperparameters, as it provides the most computation- ally efficient way improve path discovery. In this case, however, we expect a negligible fraction of paths to be missed due to the highly connected nature of SBM graphs, which sets limit the number of discoverable paths (see Section 5.4 for further discussion).
Input graph
Path
Path
Wanted graph decomposition
Figure 6. Discovering simultancously the two paths length between nodes and requires the directed graph decomposition on the right, which violates the acyclic property.
6. Related Work
Graph Transformers. Graph transformers are class of models designed to process graph-structured data by lever- aging self-attention, which provides a graph-wide receptive field (Vaswani, 2017; Ying et al., 2021), thereby avoiding common limitations of message-passing GNNs (Topping et al., 2022). Despite their advantages, graph transformers have not yet become the dominant architecture in graph learning, primarily due to the lack of unified structural and positional encodings that generalize well across di- verse graph tasks (Rampášek et al., 2022). This is evident from the continued success hybrid approaches that inte- grate message- sassage-passing with global self-attention (Wu et al., 2021; Rampášek et al., 2022; He al., 2023; Choi et al., 2024), highlighting ongoing opportunities for architectural improvements. Promising research directions include: more flexible spectral attention mechanisms (Bo et al., 2023), models that mitigate the quadratic memory footprint of self- attention (Shirzad et al., 2023), and hierarchical encodings that enhance structural representations (Luo al., 2024a). Expressivity of Path-Based MPNNs. The expressivity of message- paseee-ppssnggggg neural networks (MPNNs) paths has been studied in relation to the WL isomorphism test (Michel et al., 2023; Graziani et al., 2024). Notably, Graziani et al. (2024) demonstrated that iteratively updating node features via saassaggpsssing along paths originating from these nodes is strictly more expressive than the 1-WL test. How-
5.4. Limitations
In the proposed algorithm, the path count between two nodes is updated by comparing the value provided by each new DAG with the total currently stored in memory. The latter then replaced by the maximum of the two values. This approach necessary since paths are not enumerated be- cause of memory constraints. The obtained counts therefore constitute lower bounds on the exact number of paths (see line 16 of Algorithm in Appendix E). Failure cases can however arise because individual paths are not distinguished. For instance, consider the input graph illustrated in Figure 6. The total number of paths of length between nodes 0 and I is two (blue and green). The only directed graphs that would allow discover these paths simultaneously are not acyclic: algorithm can simply count them at time.
This limitation is especially true in high-density graphs, such as the CLUSTER dataset where our method does not yield any significant improvement. This suggests that there may exist cases where inaccurate path counts are detrimental to the overall performance, and where might be preferable to trade longer path lengths for exact counts on shorter paths.
8

---

Simple Path Structural Encoding for Graph Transformers
ever, these works consider only short path lengths, limiting their applicability more complex graph structures.
The societal impact of this work aligns with the broader advancements in Machine Learning and Graph Neural Net- works, with potential applications in drug discovery, rec- ommendation systems, and scientific knowledge extraction. However, as with any machine learning model, the deploy- ment of SPSE-based architectures should be approached with considerations for fairesss interpretability, and robust- ness, particularly in high-stakee upplications.
Counting Paths and Cycles in Graphs. The problem of counting paths and cycles in graphs has been extensively studied over the past decades (Johnson, 1975; Alon et al.,
1997; Flum & Grohe, 2004). Perepechko & Voropaev (2009) derived an explicit formula for counting paths of length up to 6 between two nodes, while Giscard et al. (2019) pro- posed algorithm for counting paths of any length based on enumerating connected induced subgraphs. However, these methods become impractical for the large graphs and long path lengths considered in our work, necessitating the use of efficient approximate counting methods.
We do not foresee any immediate ethical concerns risks associated with our contributions beyond those generally applicable to graph machine learning. Future work should consider potential biases in training data and energy effi- ciency of graph transformers, as large-scale models can have computationally intensive requirements.
7. Conclusion
This work introduced Simple Path Structural Encoding (SPSE), a novel structural encoding method for graph trans- formers that leverages path counts instead of random walk probabilities. By providing a more structurally informa- tive edge encoding. SPSE improves performance across various graph learning benchmarks. Our theoretical and experimental study shows that SPSE mitigates the limita- tions of random walk-based encodings while maintaining computational feasibility through an efficient approxima- tion algorithm. While promising, SPSE's applicability to extremely large-scale graphs and its interaction with dif- ferent transformer architectures would require further ex- ploration. In particular, SPSE bears particularly promising synergies with hierarchical methods, which would allow effi- cient path mining higher hierarchy levels while capturing valuable long-range structural information. Future research directions may also include optimizing its computational efficiency and extending its applicability to broader domains such as knowledge graphs and large social networks.
References
Agúndez, M., Marcelino, N., Tercero, B., and Cernicharo, J. Aromatic cycles are widespread in cold clouds. Astron- omy & Astrophysics, 677:L13, 2023.
Alon, N., Yuster, R., and Zwick, U. Finding and counting given length cycles. Algorithmica, 17(3):209-22 223, 1997.
Alon, U. and Yahav, E. On the bottleneck of graph neural networks and its practical implications. In International Conference on Learning Representations, 2021.
Bo, D., Shi, C., Wang, L., and Liao, R. Specformer: Spec- tral graph neural networks meet transformers. In Interna- tional Conference on Learning Representations. Openke- view.net, 2023.
Bodnar, C., Giovanni, D., Chamberlain, B. P., Lio, P., and Bronstein, M. M. Neural sheaf diffusion: A topo- logical perspective on heterophily and oversmoothing in GNNs. In Oh, A. H., Agarwal, A., Belgrave, D., and Cho, K. (eds.), Advances in Neural Information Processing Systems, 2022.
Acknowledgments
This work was funded in part by grant from Fondazione Caritro, under project GenlE. AL and AP acknowledge the support of the MUR PNRR project FAIR- Future AI Research (PE00000013) funded by the NextGenerationEU.
Bresson, X. and Laurent, T. Residual gated graph convnets. arXiv preprint arXiv:1711.0755:: 2017.
Cantürk, S., Liu, R., Lapointe-Gagné,
O., Létourneau, V.,
Wolf, G., Beaini, D., and Rampášek, L. Graph positional and structural encoder. In International Conference on Machine Learning, pp. 5533-5566. PMLR, 2024.
Impact Statement
This paper presents Simple Path Structural Encoding (SPSE), a novel structural encoding method for graph transformers, aimed at enhancing the expressivity of self- attention mechanisms by capturing richer structural patterns than existing random walk-based encodings. By improving edge encodings with simple path counts, SPSE contributes to the broader field of graph representation learning, offering more robust method for tasks involving molecular graphs social networks, and long-range dependencies.
Chen, D., O'Bray, L.,, and Borgwardt, K. Structure- aware transformer for graph representation learning. In Interna- tional Conference Machine Learning, pp. 3489-3489, PMLR, 2022.
Chen, Z., Tan, H., Wang, T. Shen, T., Lu, T., Peng, Q. Cheng, C., and Qi, Y. Graph propagation transformer for graph representation learning. In International Joint
9

---

Simple Path Structural Encoding for Graph Transformers
Conference on Artificial Intelligence, pp. 3559-3567. ij- cai.org, 2023.
Gutteridge, B., Dong, X., Bronstein, M. M., and Di Gio- vanni, E. Drew: Dynamically rewired message pass- ing with delay. In International Conference on Machine Learning, pp. 12252-12266 PMLR, 2023.
Choi, Y. Y., Park, S. W., Lee, M., and Woo, Y. Topology-informed graph transformer. arXiv preprint arXiv:2402.02005. 2024.
He, X., Hooi, B., Laurent, T., Perold, A., LeCun, Y., and Bresson, X. A generalization of vit/mip-mixer to graphs. In International conference on machine learning, pp. 12724-12745 PMLR, 2023.
Dhilber, M. and Bhavani, S. D. Community detection in so- cial networks using deep learning. In Distributed Comput- ing and Internet Technology: 16th International Confer- ence, ICDCIT 2020, Bhubaneswar, India, January 9-12, 2020, Proceedings 16, pp. 241-250 Springer, 2020.
Horowitz, P., Hill, W., and Robinson, I. The art of electron- ics, volume 2. Cambridge university press Cambridge, 1989.
Dong, Z., Zhang, M., Li, F., and Chen, Y. Pace: A paral- lelizable computation encoder for directed acyelic graphs. In International Conference on Machine Learning, pp. 5360-5377. PMLR, 2022.
Hu, W., Fey, M., Ren, H., Nakata, M., Dong, Y., and Leskovec, Ogb-Isc: A large-scale challenge for ma- chine learning on graphs. In Proceedings of the Neural Information Processing Systems Track on Datasets and Benchmarks 1, NeurlPS Datasets and Benchmarks, 2021.
Dosovitskiy, A., Beyer, L., Kolesnikov, A., Weissenbomn D., Zhai, X., Unterthiner, T., Dehghani, M., Minderer, M., Heigold, G., Gelly, S., Uszkoreit, J., and Houlsby, N. An image is worth 16x16 words: Transformers for image recognition at scale. In International Conference on Learning Representations. OpenReview.net, 2021.
Hussain, M. S., Zaki, M. J., and Subramanian, D. Global self-attention as a replacement for graph convolution. In Proceedings of the 28th ACM SIGKDI) Conference on Knowledge Discovery and Data Mining, pp. 655-665, 2022.
Duta, I. and Liò, P. Sphinx: Structural prediction us- ing hypergraph inference network. arXiv preprint arXiv:2410.03208, 2024.
Hwang, D., Kim, H., Kim, S., and Shin, K. Flower- former: Empowering neural architecture encoding using flow-aware graph transformer. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 6128-6137, 2024.
Dwivedi, V. P. and Bresson, X.
A generalization of transformer networks to graphs. arXiv preprint arXiv:2012.096699.0 2020.
Dwivedi, V. P., Rampášek, L., Galkin, M., Parviz, A., Wolf, G., Luu, A. T., and Beaini, D. Long range graph bench- mark. Advances in Neural Information Processing Sys- tems, 35:22326 22340,, 2022.
Johnson, D. B. Finding all the elementary circuits of directed graph. SIAM Journul on Computing, 4(1):77-84, 1975.
Dwivedi, V. P., Joshi, C. K., Luu, A. T., Laurent, T., Ben- gio, Y., and Bresson, X. Benehmarking graph neural networks. Journal of Machine Learning Research, 24 (43):1-48, 2023.
Kipf, T. N. and Welling, M. Semi-supervised classifica- tion with graph convolutional networks. In 5th Interna- tional Conference on Learning Representations. OpenRe- view.net, 2017.
Ferrini, F., Longa, A., Passerini, A., and Jaeger, M. Meta- path learning for multi- graph neural networks. In Learning on Graphs Conference, pp. 2-1. PMLR, 2024.
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 226299 2021.
Flum, J. and Grohe, M. The parameterized complexity of counting problems. SIAM Journal on Computing, 33(4): 892-922, 2004.
Lachi, V., Ferrini, F., Longa, A., Lepri, B., and Passerini, A. A simple and expressive graph neural network based method for structural link representation. In ICML 2024 Workshop on Geometry-gruunded grounded Representation Learn- ing and Generative Modeling, 2024.
Giscard, P.-I., Kriege, N., and Wilson, R. C. A general purpose algorithm for counting simple cycles and simple paths of any length. Algorithmica, 81:2716 16 2-17662777722 2019.
Graziani, C., Drucks, T., Jogl, F., Bianchini, M., franco scarselli, and Gärtner, T. The expressive power of path- based graph neural networks. In Forty-first International Conference on Machine Learning, 2024.
Luo, Y., Li, H., Shi, L., and Wu, X.-M. Enhancing graph transformers with hierarchical distance structural encod- ing. Advances in Neural Information Processing Systems, 2024a.
10

---

Simple Path Structural Encoding for Graph Transformers
Luo, Y., Thost, V., and Shi, L. Transformers over directed acyclic graphs. Advances in Neural Information Process- ing Systems, 36, 2024b.
Shirzad, H., Velingker, A., Venkatachalam, B., Sutherland, D. J., and Sinop, A. K. Exphormer: Sparse transform- ers for graphs. In International Conference Machine Learning, pp. 31613-31663 PMLR, 2023.
Ma, L., Lin, C., Lim, D., Romero-Soriano, A., Dokania, P. K., Coates, M., Torr, P., and Lim, S.-N. Graph in- ductive biases in transformers without message passing. In International Conference on Machine Learning, pp. 23321-23337 PMLR, 2023.
Topping. J., Giovanni, F. D., Chamberlain, B. P., Dong, X., and Bronstein, M. M. Understanding over-squashing and bottlenecks on graphs via curvature. In International Conference on Learning Representations, 2022.
Vassilevska, V. and Williams, R. Finding, minimizing, and counting weighted subgraphs. In Proceedings of the forty- first annual ACM symposium on Theory of computing, pp. 455 464, 2009.
May. J. W. and Steinbeck, C. Efficient ring perception for the chemistry development kit. Journal of Cheminformatics, 6:1-12, 2014.
Menegaux, R., Jehanno, E., Selosse, M., and Mairal, J. Self-attention in colors: Another take on encoding graph structure transformers. Trans. Mach. Learn. Res., 2023.
Vaswani, A. Attention all you need. Advances Neural Information Processing Systems, 2017.
Veličković, P., Cucurull, G., Casanova, A., Romero, A., Liò, P., and Bengio, Graph attention networks. In International Conference on Learning Representations, 2018.
Mialon, G., Chen, D., Selosse, M., and Mairal, J. Graphit: Encoding graph structure in transformers. arXiv preprint 1rXiv:2106.05667, 2021.
Michel, G., Nikolentzos, G., Lutzeyer, J. F., and Vazirgian- nis, M. Path neural networks: Expressive and accurate graph neural networks. In International Conference Machine Learning, pp. 24737-24755. PMLR, 2023.
Wu, Z., Jain, P., Wright, M., Mirhoseini, A., Gonzalez, J. E., and Stoica, Representing long-range context for graph neural networks with global attention. Advances Neural Information Processing Systems, 34:1 3266- 13279, 2021.
Otte, E. and Rousseau, R. Social network analysis: pow- erful strategy, also for the information sciences. Journal of information Science, 28(6):441-455 2002.
Xu, K., Hu, W., Leskovec, J., and Jegelka, S. How powerful are graph neural networks? In International Conference on Learning Representations, 2019.
Perepechko, S. and Voropaev, A. The number of fixed length cycles in an undirected graph. explicit formulae in case of small lengths. Mathematical Modeling and Computational Physics (MMCP2009), 148, 2009.
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 neural information processing systems, 34:28877-28885. 2021.
Quinn, R. A., Nothias, L.-F., Vining, O., Meehan, M., Es- quenazi, E., and Dorrestein, P. C. Molecular network- ing as a drug discovery, drug metabolism, and precision medicine strategy. Trends pharmacological sciences, 38(2):143- 2017.
Yun, S., Jeong, M., Kim, R., Kang, J., and Kim, H. J. Graph transformer networks. Advances in neural information processing systems, 32, 2019.
Zhao, I.., Jin, W., Akoglu, I.., and Shah, N. From stars to subgraphs: Uplifting any gnn with local structure aware- ness. In International Conference on Learning Represen- tations. OpenReview.net, 2022.
Radicchi, F., Castellano, C., Cecconi, F., Loreto, and Parisi, D. Defining and identifying communities in net- works. Proceedings of the national academy of sciences, 101(9):2658-266, 2004.
Radicchi, F., Fortunato, S., and Vespignani, A. Citation net- works. Models of science dynamics: Encounters between complexity theory and information sciences, pp. 233-257, 2011.
Rampäšck, L., Galkin, M., Dwivedi, V. Luu, A. T., Wolf, G., and Beaini, D. Recipe for a general, powerful, scal- able graph transformer. Advances in Neural Information Processing Systems, 35: 144501--15111 2022.

---

Simple Path Structural Encoding for Graph Transformers
Table Statistic, path counting hyperparameters and total counting time per dataset with the Python implementation of the algorithm.
Dataset
ZINC
PATTERN
CLUSTER
MNIST
CIFARIO
Peptides
PCQM4Mv2
Dataset Statistics
# of graphs
12,000
14,000
12,000
60,000
70,000
15,535
3,746,620
Avg. # of nodes per sample
23.2
118.9
117.2
70.6
117.6
150.9
14.1
Avg. # of edges per sample
24.9
3,039.3
2,150.9
564.5
941.1
307.3
14.6
Avg. density
0.10
0.43
0.36
0.23
0.14
0.03
0.16
Path count
R (# of root nodes, % of [V])
100%
40%
40%
55%
55%
100%
100%
K (max length)
20
16
16
17
17
23
15
DEs (max DFS depth)
6
2
2
11
11
(# of trials per depth)
1
7
7
2
2
Time (hr)
60
39
34
80
Model training
a
0.5
0.2
0.2
0.2
0.2
0.2
0.5
3
-0.2
-0.2
-0.2
-0.2
-0.2
n
3
3
3
3
A. Additional Path Count Statistics and Training Hyperparameters
Typical hyperparameter values for path counts with the respective computing duration reported in Table 2. The hyperparameter search was conducted on reduced pool of graphs and root nodes to optimize the trade-off between exhaustivity and duration. The reported figures should therefore not be viewed as optimal, but rather give an indication of how they affect the path count duration. The latter ranges from under one hour for ZINC to a bit more than three days for CIFARIO and the large PCQM4Mv2 dataset which contains 3.7M graphs. Once computed, path counts are stored and used for model training at no additional cost.
Path count encoding parameters a, 3 and nı In the absence of clear heuristics regarding the effects of parameters a, and of Equation (4), report in Table the values that led to the best results for each dataset. Among those, n primarily controls the compression of the dynamic range of path counts, while both and contribute to the adjustment of the output range of function of in Equation (4). Unsurprisingly, denser datasets call for a higher n, lower or a combination of both.
B. Expressivity of SPSE encoding
We provide here a discussion about the expressivity of the proposed SPSE encoding in light of findings from previous works. A reasoning similar to the followed for Path-Wr (Graziani et al., 2024) be used show that iterative node coloring algorithm based global attention with SPSE is more expressive than 1-WL. We note also that the results regarding the expressivity of GRIT remain valid when SPSE replaces RRWP as the chosen structural encoding method, except for the case of Proposition 3.1 (b) which requires access to transition probabilities.
However, no previous study allows the comparison of SPSE and RRWP expressivity. Contrary to WL- / Path-trees used Graziani et al. (2024) and Michel et (2023), SPSE and RRWP aggregate information over simple paths and walks without enumerating them, which prevents one from using the strategy of the proof of Theorem 3.3 of Michel al. (2023) to conclude. We leave the task of proving whether both encodings be compared for future work.
C. Proofs
C.1. Proof of Proposition
Proposition. Let g = (V, E) ) be an even-length cycle graph, i.e. [V] = 2n for some n E No, and g' = (V. E') a path
graph such that [V| = 2n + 1. Then given any pair of nodes (i. in G. there exists a pair of nodes (i',3)) ) in g' such that (1,j)9 =Rw (i', g"
12

---

Simple Path Structural Encoding for Graph Transformers
Proof. The proof is done by induction by considering landing probabilities of walks of length k and k 1 for any given l: in N To do that, we use the following notations:
Pk(i, - (P&ka
where Pe is the k-hop random walk matrix of g, and (Pe) is the random walk probability of length & between nodes and j. We also take advantage of the symmetries of the circular graph 9 to denote as pkk (J) the k-hop walk probability between any two nodes distant of S n. As G' is a linear graph with an odd number of nodes, we also use the notation
(L.)) = (P)))s
with P the k-hop random walk matrix of g', but use this time node indices to represent the distance from the central node of the graph. Hence ple (0. n)) is the k-hop walk probability between the central node and any of the two extremity nodes, Similarly, for all S j n. ()) refers to k-hop walks originating from the central node and ending on one of the two nodes distant of j.
The first part of the proof consists in showing that, for all I < and all k E N', pk()) = P&))), and p/((n) (n). The initialization, up to k = j. is straightforward as all nodes have exactly two neighbors, except from the extremity nodes in g' which have one. Suppose that the previous statement holds for & 2 1. Then we have:
(1) = pha(i - 1) x
2 + p1 + p
2
= (i) ifj < - 1,
1
Pk+1 1) = =rh(n - 22) + pk(()
2
1
1
=pa(n - -2) x 2
+ pz(n)) x 2
=p (11nn--)... 1),
1
(n+ = (n - -1) x 2
1 1
(2 pa - 1)
5)
2
1 P (n).
At this point, equivalent random walk edge encodings have been found in g' for any pair of nodes of G distant of less than n. from each other. The last part of the proof consists in showing that (nn = (n, 0) for all k 2 1, or equivalently, from the previous result, that P (n, 0) 2p)(n),
This is again done by induction, by proving the following statement for all i E N2, k E No such that 0 <i< j S
((.5)) = d)) ifj < n,
()) = -2 (n, 1).
As before, the initialization up to the distance between i and is direct all nodes have exactly two neighbors, except which has one. Suppose now that the statement holds for some & < 1. Then, if j < n:
Plet (i.j) = ((t ())( 1.5)
11p
-1442(i,1,,
13

---

Simple Path Structural Encoding for Graph Transformers
and
Pk41(i,n) = (1),n-1)p'(m 1,
x p1 n -n - -,,)
2
x (k+111,));
which concludes the proof.
C.2. Proof of Proposition 2
Proposition. Let = E) be graph and (i, E V XV a pair of nodes in G. Then there exists non-isomorpies graph ='= -V= "Y,E) E and pair of nodes (i',3') E V x V such that (i.j)² =Rw ('',")) i.e. (i,5) and (V'j') are equivalent under RRWP encoding.
Proof. We proceed by induction to show that given an edge (i,j) in graph G, there always exists non-isomorphic graph g' with an edge (i', j') such that (i,j) =xw (i',j")s" Without loss of generality, we take i = i' = 0 and j = j 1. and denote probabilities in G' with a prime superscript. We write Pij = (Pi) Peyy = (P))y with Ps and P% the k-hop random walk matrices of & and g'. Finally, we also write, Ak E N, (x) = (Px)os and pk((i') = (Pr)
The proof relies on the introduction of a graph g' as the result of a central symmetry of g around node 1. Concretely, each node i (respectively j) originally in & possesses symmetric node (respectively j') in G' such that:
Vi,jegiii, Pog = p/a Pij
(5)
ViEWing, thi = phg =
2 P1.+
(6)
where M1 is the neighborhood of node g', g is its restriction to G, and 1' = 1.
The initialization is straightforward as, for such G' and for any & lesser or equal to the shortest path distance between 0 and holds true that p/. (1) = pa((), Suppose now that for a given
have:
vi vsk. k, M() p(())
(7)
Let pī (i) designate the probability to travel from 0 to i in k steps in 9 without passing through 1, (i) the similar probability in g', and let px (i) and & (i) be respectively the probabilitics to travel to in & and g' while visiting at least once. is then possible to write p1)4(11 (1) as follows:
(1) - ΣntOph + EnhOr SENi
(8)
iEN
① Walks that through
① Walks that travel through
The first term rewrites simply:
Σ pl (0p/ = E (1)p
(9)
TEAM
iEAing
Σ
pt(1)pa
(10)
iEAing
For the second term, introduce WTL, as the set of random walks of length between nodes i and j that do not go through Thus, an element of Whi, is multiset of nodes such that w (w), (wi...., wx) with wi and wi j. We may now
14

---

Simple Path Structural Encoding for Graph Transformers
rewrite 2, and in partieular each 1%,(0 (i) in the sum as follows:
Σ
Σ
Σ
p((1)11
II m>1
Pum-1
(11)
Isk-1
JENI WEW ( jimt
= Σ Σ
Σ
(1())
Pij
II m>1
Pum-1 Wm
(12)
2
lgk- JENing wew (11) J
(t),
(13)
where equations 5, 6 and 7 used for (11) (12). Putting everything back together, have:
(1)+(1)=
Σ
pk(PPa +
E
(14)
iENing
iE.iing
-k++1 (1),
(15)
which concludes the proof.
C.3. Proof of Proposition 3
Proposition. Let (i,J) be two adjacent nodes in graph = (V, i.e. (i,3) E E, and Ss the k-hop simple path matrix of 9 for any k E N,, such that (Sk) = my N. Then for k 2 2, there are exactly my cycles of length k + in that admit (i
edge.
Proof. This be proved directly by noting that each cycle of length k + which the edge (i lies is walk of k + 2 nodes of the form i,..ji where only the first node is repeated. The restriction of the latter to its 1 first nodes is itself path of length & between and j. which therefore increments (Sk)ij. Conversely, all paths counted in (8k)iz can be completed by the edge ji to form a cycle of length k + 1, which proves the equality.
D. Tree Decompositions
The formal proof of the equivalence of the RRWP encodings in circular and linear graphs is given in Appendix C.I. Here we give graphical sketch of the proof for the two examples considered in Figure 1. The tree decompositions of the graphs in Figure 1 are presented in Figure for walks starting in node O and a maximum depth of 5. As nodes only have one or two neighbors, colors are used to represent the walk probabilities toward child nodes. Edges (0, 1) have the same random walk probabilities in (A) and (B) (Figure 7, top) on one hand, and in (C) and (D) (Figure 7, bottom) on the other hand, despite belonging to very different graphs. It is straightforward to extend these results to any depth, hence verifying that (0, 1 Rw (0, 1) and (0, 1) =x (0, P)
E. Full Path Counting Algorithm
We present in Algorithm 3 the detailed version of Algorithm 1. Once a list of node permutations is obtained from the DAGDECOMPOSE function, rows and columns of the adjacency matrix are first permuted according to each new node ordering, which then allows to retain only the elements that are above the diagonal (all edges are directed towards nodes of higher index). Subsequently. k-hop path counts are easily obtained by computing powers of the resulting nilpotent matrix Á. after which rows and columns are permuted back to the original ordering. The transpose of the resulting matrix A& yields the opposite paths and is then added to Aş before updating the running k-hop path count matrix My. If G is instead directed, this step is skipped and only A is used to update Mg.
F. Synthetic Experiment
Figure 8 shows three instances of randomly generated graphs for experiments in Section 5.1. These graphs possess an average of 149 nodes and 190 edges. We also detail the three configurations used for the synthetic experiments in Table 3.
15

---

Simple Path Structural Encoding for Graph Transformers
(A)
-
(15)
16 x 0.5 0.5
(Po)01
4 x 0.5
+ +4x
4.5
0.5
16 x 0.5
(D)
== 5
h
(Pr)or 11 0.5*
(Pr)or 9 0.5 + 0.5* 11 0.5
Figure 7. Tree decompositions for the graphs in Figure for walks rooted node 0, up to maximum depth of 5. Colors denote different probabilities to reach node a given depth level black lines are associated probability 0.5%, red lines 0.5 and green lines 0.5*
16

---

Simple Path Structural Encoding for Graph Transformers
Algorithm 3 Count paths between all pairs of nodes
1: Parameters: Proportion of root nodes R, maximum length K, maximum DFS depth Does. maximum trial number N
2: Input: Undirected graph 9 = (V, adjacency matrix A
3: Output: Path count matrix M E |IV|>|VV
4: Mi...., Mr < | {Initialize count matrices)
5: for to [V] do
6: r; SELECTROOTTODE(C, i)
7: II + DAGDECOMPOSE(G, Doss, N) {Retrieve list of node permatations starting with ri)
8: for each Ty in II do
9:
Ā + REORDER(A, Ty)) (Permute rows and columns according Ty
Ā TRIUP(A) (Keep elements above the diagonal, fill the rest with
11:
k+ 1
12:
As + Á
13:
while < K and Aş + 1ixild0 do
As + As À
15:
Aş + REORDER(A,, 95
16:
M₁ f max(MMs, A& + A {Add opposite paths and store new maximum counts)
+ ++1
end while
19: end for
20:
end for Return: ,I...., MK
21:
Figure 8. Examples of synthetic graphs generated for the cycle counting experiment.
Table 3. Model configurations used for the synthetic experiments.
Configuration
# 2
# 3
Transformer layers
6
10
Self-attention heads
4
4
8
Hidden dimension
52
64
64
Learning rate
10 10-3
x 10
5 10 -4
Epochs
100
300
400
17


Reviews:
[{"review_id": "8mmctrKKGf", "reviewer": "Reviewer_wLjL", "summary": "This work proposes a new structural encoding for empowering graph transformers, SPSE (Simple Path Structure Encoding). Rather than encoding random walk landing probabilities, SPSE encodes simple path counts, demonstrating superior expressivity in scenarios such as cycle counting. The authors propose an algorithm for computing an approximation of simple path counts between nodes show that SPSE outperforms a variety of structural/positional encodings on benchmark datasets.", "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": "Thank you for your thorough and thoughtful review. We are glad that you found the theoretical claims convincing and appreciated the clarity of our method and the rigor of our experimental setup.\n\nBellow we report the answers to the comments and questions.\n\n**Q1. Aspect contributing to runtime of path mining algorithm**\n\n**R1.** In the cases considered here, where the number of nodes does not exceed a few hundred, the critical aspect is graph density. \nFrom the algorithmic point of view, the parameters that impact the most the computation time are the fraction of selected root nodes, $R$, the number of trials per depth $N$, and to a lesser extent the maximum DFS depth $D_\\text{DFS}$, as can be seen in Figure 5. Although the worst-case complexity scales linearly with $D_\\text{DFS}$ and $N$, their contributions are most of the time smaller: we suspect that the sparser the input graph, the lesser the contributions of $D_\\text{DFS}$ and $N$ are (may it be at least as $N$ cannot exceed node degree), although this would require further and thorough analysis.\n\n**Q2: Similarity with Node2Vec**\n\n**R2**. A given DAG decomposition could be interpreted as an attempt to characterize the neighborhood of a root node in the sense of Node2Vec, in the limit case where the neighborhood is the whole graph. In this sense the two methods indeed share similarities. However, we characterize node pairs instead of single nodes, and rather than listing the neighboring nodes, we focus on the ordering in which the nodes were discovered by the search to unveil graph structures at various scales.\n\n**Q3. Choice of datasets used**\n\n**R3.** The practical reason that drove our choice of test datasets was that we looked for existing configurations for the training of GRIT and/or CSA, the two graph transformer methods implementing RWSE, in order to validate our methodology. \nThe exploration of the benefits of SPSE on more diverse graph topologies will be an exciting future research direction.\n\n**Q4. Parameter study on $\\alpha$, $\\beta$ and $n$**\n\n**R4**\nOur analysis of the path encoding parameters (Equation 4) revealed two main factors contributing significantly to variations in model performance:\n* Compression of the dynamic range of path counts (controlled primarily by parameter $n$).\n* Adjustment of the final output range (affected by both parameters $\\alpha$ and $n$).\n\nThese effects are demonstrated in the tables below, presenting model accuracy for GPS on the PATTERN dataset and GRIT on the MNIST dataset, across various hyperparameter configurations:\n\n| PATTERN / GPS  |     |      $n$      |\n|----------------|:------:|:----------:|\n| $\\alpha$       |    2   |      3     |\n|       0,2      | 86,815 | **86,834** |\n|       0,5      |    -   | 86,819     |\n\n| MNIST / GRIT |    |     $n$      |          |\n|--------------|:------:|:------:|:----------:|\n| $\\alpha$     |    1   |    2   |      3     |\n|      0,5     | 98,189 | 98,224 | **98,294** |\n\nIn these cases, the large path counts explain why the best results are obtained for a higher $n$ / lower $\\alpha$.\n\n**Q5. Expressivity regarding WL / RWSE**\n\n**R5:** \nWe provide below an initial discussion about the expressivity of the proposed SPSE encoding as an answer to this insightful comment.\nA reasoning similar to that employed for Path-WL [1] shows that composing $k$ global attention layers with SPSE results in a model that is strictly more expressive than $k$ iterations of the 1-WL color refinement algorithm.\nWe note also that all properties regarding the expressivity of GRIT remain valid when SPSE replaces RWSE as the chosen structural encoding method.\nHowever, comparing the expressivity of SPSE and RWSE through isomorphism tests is more complex. Contrary to WL- / Path-trees introduced in [1] and [2], SPSE and RWSE aggregate information over simple paths and walks without enumerating them, which prevents one from using the strategy of the proof of Theorem 3.3 of [2] to draw any conclusion.\nA rigorous theoretical analysis is required to characterize the precise relationship between the two encodings within the WL hierarchy, which is left as future work.\n\n[1] Graziani et al., \"The Expressive Power of Path-Based Graph Neural Networks.\" ICML, 2024.\n\n[2] Michel et al., “Path Neural Networks: Expressive and Accurate Graph Neural Networks”, ICML, 2023 \n\n**Q6. Missing SEs benchmark**.\n\n**R6.** The missing reference will be added to the benchmark.", "claims_and_evidence": "I am convinced the theoretical claims are correct, and the authors' assessment of SPSE in their experiments are also supported.", "methods_and_evaluation_criteria": "Using simple path counts is a straightforward and intuitively more powerful approach than random walk landing probabilities, and the proposed method is total sense for this problem. The evaluation metrics and datasets used are all standard in the graph PSE literature.", "theoretical_claims": "I read and checked all proofs introduced. I am convinced Propositions 1 and 3 are correct. I think Proposition 2 is also correct, although I am less certain.", "experimental_designs_or_analyses": "**Strengths**\n\n- The fact that the authors do no hyperparameter tuning on the main results is transparent for fair comparisons with other SEs.\n- The use of 10 runs and random seeds with significance testing strengthens the experimental design.\n\n**Weaknesses**\n\n- The datasets used are largely toy datasets. Results would be stronger if some experiments on more \"real-world\" graphs were used (e.g. MoleculeNet, citation graphs).", "relation_to_broader_scientific_literature": "This work is related to the graph positional/structural encoding literature, expanding on [1] and [2] to use path counts rather than random walk probabilities to encode structure. It is also following a line of work that uses counts of important topological features within a graph to supplement neural network features. For example, [3] and [4] explore counting specific subgraph structures.\n\n[1] Menegaux et al. Self-Attention in Colors: Another Take on Encoding Graph Structure in Transformers. TMLR.\n\n[2] Ma et al. Graph Inductive Biases in Transformers without Message Passing. ICML 2023.\n\n[3] Jin et al. Homomorphism Counts for Graph Neural Networks: All About That Basis. ICML 2024.\n\n[4] Charilaos I. Kanatsoulis and Alejandro Ribeiro. Counting Graph Substructures with Graph Neural Networks. ICLR 2024.", "essential_references_not_discussed": "To my knowledge, the authors discuss all essential references for their research problem.", "other_strengths_and_weaknesses": "**Strengths**\n\n- The authors do a great job of illustrating how their method works and specific failure cases of RWSE that SPSE remedies.\n- The limitations section is well-argued, and the failure case of SPSE is easily understood.\n\n**Weaknessees**\n\n- I think a parameter study on $\\alpha, \\beta,$ and $n$ would be valuable, similar to their study of the effect of $R, N, K, D_dfs$.\n- There is no discussion on the WL-expressivity of the proposed encoding. Given that most PSEs have some analysis regarding the WL-hierarchy, this work would be more convincing if the relationship between SPSE and WL were addressed. Similarly, there is no theoretical proof that SPSE is strictly more expressive than RWSE in a certain hierarchy.\n- There are some missing SEs in the main benchmark such as [1].\n\n[1] Cantürk et al. Graph Positional and Structural Encoder. ICML 2024.", "other_comments_or_suggestions": "Overall, I am convinced by this paper. The advantages of SPSE seem clear, and the experiments convince me of its effectiveness.\n\nMinor typos:\n\n- \"there _exits_\"", "questions_for_authors": "Please address the above weaknesses.\n\n- What aspect of a given graph contributes most to the runtime of the simple path mining algorithm?\n- Also, the proposed path count mining algorithm seems to bear some similarity with Node2Vec during the DAG decomposition phase given its combination of BFS and DFS, except the proposed algorithm alternates between phases of explicit DFS/BFS rather than a biased random walk. Can the authors comment on the connection between these works?", "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": "mxMupwIrXY", "reviewer": "Reviewer_Ybg7", "summary": "The paper introduces Simple Path Structural Encoding (SPSE), a novel method for encoding graph structures in graph transformers. SPSE leverages simple path counts between node pairs to capture richer structural information compared to traditional random walk structural encoding (RWSE). The authors propose an efficient approximate algorithm for counting simple paths, addressing the computational challenges associated with path enumeration. SPSE is shown to outperform RWSE in various benchmarks, including molecular and long-range graph datasets, demonstrating significant improvements in discriminative tasks. The method is particularly effective in capturing local cyclic patterns, which are crucial in applications like molecular chemistry and social network analysis.", "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": "Thank you for the detailed and constructive review. We appreciate your recognition of SPSE’s novelty, and of the clarity and comprehensiveness of our experimental validation. We're also glad you found the theoretical contributions, algorithmic details, and supplementary material valuable. \nWe address the questions below.\n\n**Q1. Addressing the computational cost of SPSE for large-scale graphs**\n\n**R1.** As the computational complexity of path counting incurs a cubic dependency with the number of nodes, scaling to large-scale graphs is a challenge. One possible solution is to apply pooling techniques [1] to reduce the graph size: computing simple paths between communities in a pooled graph would become manageable, and this could be followed by separate path discovery within each community. This shares links with the discussion in the answer to the next question.\nThat being said, accurately combining path counts within and between communities presents new and interesting challenges, constituting an avenue for future research.\n\n[1] Bianchi, F. M., & Lachi, V. The expressive power of pooling in graph neural networks. NeurIPS 2023.\n\n**Q2. Plans to combine SPSE with other SEs?**\n\n**R2.**\n Yes, one particularly promising direction is [2], which is complementary to our work and can also be used as a plug-in module within existing architectures. In particular, we expect that our two offline preprocessing workflows can be efficiently combined: mining paths at higher hierarchy levels can be done more easily because of simpler topologies, while capturing valuable long-range structural information. This will be mentioned in the discussion on future research direction.\n\n[2] Luo et al., Enhancing Graph Transformers with Hierarchical Distance Structural Encoding, NeurIPS 2024\n\n\n**Q3. SPSE for directed/weighted graphs**\n\n**R3.** The only difference that arises in our algorithm when the input graph is directed is that one must account for the fact that the adjacency matrix is no longer symmetric. This case is addressed in the attached Python file by setting the `directed` boolean to True. This prevents the summation with the transposed adjacency matrix in line 16 of the full algorithm (Algorithm 3 in Appendix D).\nIn the special case of a DAG input graph, the ``DAGDecompose`` step will be skipped. \nIt is also possible to use different edge attribute values (i.e. weights) inside the adjacency matrices, although the interpretation might be more intricate and calls for closer scrutiny.\n\n**Q4. Contextualization with hierarchical encoding / spectral attention**\n\n**R4.** Thank you for the suggestion. Adding a discussion —aligned with our response to **Q2**— on the potential synergies with hierarchical methods, especially, would help strengthen the future research directions section.\nSpectral attention, meanwhile, is natively used within both GRIT and CSA frameworks.\n\n\n**Q5. Further improvement with hyperparameter tuning**\n\n**R5.** We acknowledge that hyperparameter tuning could further improve SPSE's performance. Here, we intentionally chose not to alter the provided configurations for a transparent and fair comparison with existing structural encodings (a procedure that Reviewer wLjL also acknowledged), but future exploration of full SPSE capabilities will likely require adjusting model and optimization parameters.", "claims_and_evidence": "The claims made in the submission are generally supported by clear and convincing evidence. The theoretical analysis highlights the limitations of RWSE in distinguishing between different graph structures, which SPSE overcomes by capturing cycle-related information more effectively. Experimental results on synthetic and real-world datasets validate the superiority of SPSE over RWSE in cycle counting and other graph learning tasks. However, the performance of SPSE on densely connected graphs like the CLUSTER dataset is limited, indicating potential areas for improvement.", "methods_and_evaluation_criteria": "The proposed methods and evaluation criteria are well-suited for the problem at hand. The use of synthetic datasets for cycle counting and real-world benchmarks for molecular and long-range graphs provides a comprehensive assessment of SPSE's effectiveness. The comparison with RWSE and other graph transformer models using standard metrics (e.g., accuracy, mean absolute error) offers a fair evaluation of SPSE's performance.", "theoretical_claims": "The theoretical claims, such as Propositions 1, 2, and 3, are well-supported by proofs provided in the appendices. These propositions highlight the limitations of RWSE and the advantages of SPSE in capturing structural information. However, a detailed review of the proofs would require examining the appendices closely.", "experimental_designs_or_analyses": "The experimental designs are sound, involving a range of datasets and model configurations. The use of multiple hyperparameter settings and the retraining of models on different random seeds enhance the robustness of the results. However, the lack of hyperparameter tuning for SPSE might limit its full potential, as noted in the paper.", "relation_to_broader_scientific_literature": "SPSE contributes to the broader field of graph representation learning by offering a more expressive edge encoding method. It builds upon recent advances in graph transformers and message-passing neural networks, addressing the need for more effective structural encodings. The work is related to studies on path-based MPNNs and cycle counting algorithms, which have shown the benefits of using paths over random walks for enhancing model expressivity.", "essential_references_not_discussed": "While the paper cites key works in graph transformers and structural encodings, it might benefit from discussing recent developments in hierarchical encodings and spectral attention mechanisms, which could further enhance SPSE's effectiveness.", "other_strengths_and_weaknesses": "Strengths include the novel approach to edge encoding and the comprehensive experimental validation. Weaknesses include the computational cost of SPSE and its limited performance on densely connected graphs. The paper is well-structured and clear, making it accessible to readers familiar with graph learning concepts.", "other_comments_or_suggestions": "Future work could focus on optimizing SPSE's computational efficiency and exploring its applicability to other domains like knowledge graphs.", "questions_for_authors": "How do you plan to address the computational cost of SPSE for large-scale graphs?\n\nAre there plans to integrate SPSE with other structural encoding methods to further enhance its expressivity?\n\nHow might SPSE be adapted for directed graphs or graphs with weighted edges?", "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": "mizC6xY5ST", "reviewer": "Reviewer_r2Mc", "summary": "The work introduces a new perspective on structural encoding for Graph Transformers by leveraging Simple Path Structural Encoding (SPSE). The paper claims to be the first to propose encoding edge information based on simple path counts rather than random walk probabilities, addressing the limitations of Random Walk Structural Encoding (RWSE) in distinguishing local graph structures. It introduces an efficient approximation algorithm for counting simple paths, enabling SPSE to capture richer structural patterns, particularly in graphs with cyclic dependencies. Experimental results demonstrate that SPSE improves performance across various benchmarks, including molecular and long-range graph tasks, outperforming RWSE-based Graph Transformers.", "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 respectfully acknowledge the reviewer’s comments, and hereby attempt to address the different points that were raised.\n\n**Q1. Distinction of graphs A vs. B using RWSE / RWSE is not limited to a single value of k…**\n\n**R1.** We'd be happy to clarify.\nIn Figure 1, the objective is not to differentiate between entire graphs (e.g., Graph A vs. Graph B), but rather to compare how individual edges are represented under different encoding methods.\nTaking the concrete example of edge (0,1) in both Graph A and Graph B, the random walk probability of travelling from node 0 to node 1 in $k$ steps is exactly 0.5 if $k$ is odd and 0 if $k$ is even, and *this holds for any* $\\textit{k} \\in \\mathbb{N}^*$.\nThis implies that RW-based structural encoding cannot distinguish between edges (0,1) in Graph A and Graph B.\nThis property of RWSE is formalized in Proposition 1 of the manuscript, which we prove in Appendix B.1. We also sketch the manual derivation of the random walk probabilities of edge (0,1) of graphs A to D in Figure 7 (Appendix C).\n\n**Q3. How to get the approximated simple path count?**\n\n**R3.** Thank you for pointing this out. The details about the operation done in line 9 of Algorithm 1 (how the running path count is updated for each new node ordering) are given in the full path counting algorithm, in Appendix D: powers of the adjacency matrix given by the new DAG yield new path counts, and running counts are updated by taking the element-wise maximum across all node pairs and path lengths between the new path counts and the current running values. This will be made more explicit in the main text.\n\n**Q4. Error bound of the approximate counting algorithm**\n\n**R4.** Deriving the error bound is an intricate task, which would require identifying the failure cases and estimating their prevalence. It is however possible to empirically quantify this bound by running exact path counts on various graph topologies, within the runtime limits of these algorithms (i.e. largest possible value of maximum path length $K$, shown below for the `NetworkX` implementation). \n\nFor ZINC, MNIST and PATTERN, which contain graphs of respective average densities of 0.09, 0.23 and 0.43, we report below the proportion of paths discovered by our approximate path counting method.\n\n| Maximum   Path Length K |         | 2   | 3   | 4   | 5   | 6   | ... | 20  |\n|:---------------------:|:-------:|-----|-----|-----|-----|-----|-----|-----|\n|                       | ZINC    | 100 | 100 | 100 | 100 | 100 | ... |  99 |\n|     Path Count (%)    | MNIST   | 100 |  93 |  79 |  61 | OOM | ... | OOM |\n|                       | PATTERN | 100 | OOM | OOM | OOM | OOM | ... | OOM |\n\nWe observe from experiments that trading path count precision for longer path length can improve overall performances, but the precise interplay between exact path count (when they are affordable), maximum path length $K$ and model accuracy would require further study.\n\n**Q5. Reason behind $log$ in Equation (4)**\n\n**R5.** The only constraint on the encoding function of Equation 4 is injectivity. The use of logarithm composition was empirically driven by the need to reduce the very high magnitudes of total path counts reached for several graph collections (up to $10^{13}$ for $k=16$ on CLUSTER).\n\n**Q6. Differences between Table 1 results and original works**\n\n**R6.** Differences between results originally reported by the authors in CSA / GRIT and GPS and the ones in Table 1 are due to the fact that all models were re-trained (using publicly released code and configurations) on 10 random seeds, instead of 4, as is usually done. Retraining was important to compare RWSE and SPSE performances all things being equal, while running experiments on 10 seeds yielded much stronger results. For the large PCQM4Mv2 on which a single experiment was run, we found a MAE of 0.0838 for GRIT-RWSE, improving the reported value of 0.0859: this highlights the need for retraining, even when using the same number of seeds as the original work. The reason for the observation of such differences (be it better or worse) will be made very clear in the final version of the manuscript.", "claims_and_evidence": "1. In Figure 1, I'm confused why RWSE cannot distinguish A vs. B and C vs. D. Can the author elaborate and provide empirical numbers to prove that? RW of these graphs should be easy and fast enough to compute imo.\n- I would like to make a note here that RWSE used in, for example GRIT, is not limited to a single value of k, but it is a concatenation of multiple random walk matrix A_i for i \\in {1...k}.", "methods_and_evaluation_criteria": "1. For algorithm 2, how can we get the approximated simple path count from the list of node ordering? I believe this is worth mentioning in the paper to clarify the end2end pipeline.", "theoretical_claims": "1. What is the error bound of the proposed approximation algorithm for simple path counting?\n2. What is the theoretical reason behind using log() for Equation (4)?", "experimental_designs_or_analyses": "1. Some numbers in Table 1 seems to be off. For example, GRIT-RWSE on peptide-struct was reported as 0.2460 in their paper, while the authors provide 0.2480. Can the authors explain?", "relation_to_broader_scientific_literature": "The work proposes a new structural encoding method, i.e. simple path counting, to enhance transformers' performance on graph tasks. To the best of my knowledge, the work is the first one to do so.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "Generally, the paper offers a new structural encoding method, yet some points need to be addressed as I mentioned in the upper section. I'm willing to raise my score a bit if all of my concerns can be addressed.", "other_comments_or_suggestions": "Please see \"Other Strengths And Weaknesses\"", "questions_for_authors": "Please see \"Other Strengths And Weaknesses\"", "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": "y4OAPH7LRc", "reviewer": "Reviewer_Luky", "summary": "This paper introduces a novel graph structural encoding method, Simple Path Structural Encoding (SPSE), as a replacement for Random Walk Structural Encoding (RWSE) in graph transformers. SPSE encodes graph structure by counting simple paths of varying lengths between node pairs, providing more accurate structural information compared to random walks. To address the computational challenges of simple path counting, the authors propose an efficient algorithm based on successive DAG decompositions using depth-first search (DFS) and breadth-first search (BFS). This approach avoids the exponential memory costs associated with path enumeration, enabling scalability to longer path lengths.\nThe key innovations of this paper include:\n1.\tThe introduction of SPSE, a new graph structural encoding method that provides more accurate structural information;\n2.\tThe design of an efficient algorithm to tackle the computational difficulties of simple path counting, demonstrating strong scalability.", "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": "Thank you for your thoughtful and constructive review. We're glad that the clarity of our claims, the robustness of our experimental design, and the correctness of our theoretical contributions were appreciated. \nWhile no major concern was raised, we would like to contextualize the following point below:\n\n**Q1. Although SPSE performs better than RWSE in most cases, the improvement is only slight.**\n\n**R1.**\nWe completely agree that, although the performance gains over RWSE-based methods are statistically significant on 4 out of 7 datasets, they can sometimes appear modest. However, we would like to highlight that these results were obtained only by replacing walk probabilities by path counts, with no further alteration to the model input or architecture.\nThat said, we believe there is still untapped potential in SPSE, as suggested in Section 5.3 (\"Path Count Sensitivity to Hyperparameters\"). Furthermore, additional performance gains may be possible through more extensive tuning of SPSE's three key hyperparameters.", "claims_and_evidence": "The claims presented in the submission are well-supported by clear and compelling evidence. The authors substantiate their arguments with illustrative examples demonstrated in Figure 1 and Figure 2, as well as a detailed comparative analysis presented in Figure 4. Furthermore, the methodology employed for data collection and analysis is robust, thoroughly documented, and enhances the credibility of the findings.", "methods_and_evaluation_criteria": "Yes. SPSE mitigates the limitations of random walk-based encodings while maintaining computational feasibility through an efficient approximation algorithm. In addition to its application in this study, the algorithm also serves as an approximate solution to the fundamental graph theory problem known as Simple Path Counting.", "theoretical_claims": "Yes. I checked the correctness of proofs for Proposition 1, Proposition 2 and Proposition 3.", "experimental_designs_or_analyses": "The experimental design incorporates SPSE as an additional component to the existing advanced Graph Transformer architecture, and the implementation results demonstrate a consistent improvement in performance. Alternatively, when SPSE is used to replace the RWSE in these Graph Transformers, the experimental outcomes indicate that SPSE achieves better performance than RWSE.", "relation_to_broader_scientific_literature": "1.\tRandom walk structural encoding (RWSE), which encodes richer structural information by considering random walk probabilities as edge features. RWSE has shown substantial improvements in the performance of state-of-the-art graph transformers (“Self-attention in colors: Another take on encoding graph structure in transformers”, TMLR 2023). This paper uses simple path matrix instead of random walk matrix to perform structural encoding.\n2.\tSimple path counting, existing path-counting algorithms (“A general purpose algorithm for counting simple cycles and simple paths of any length”, Algorithmica) efficiently handle short paths, the graph topologies and path lengths considered necessitate approximate methods.", "essential_references_not_discussed": "There are no essential references missing from the paper.", "other_strengths_and_weaknesses": "Although SPSE performs better than RWSE in most cases, the improvement is only slight.", "other_comments_or_suggestions": "None", "questions_for_authors": "None", "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": {}}]

Author rebuttal:

Meta-review: This paper introduces Simple Path Structural Encoding (SPSE), a novel method for enhancing graph transformers by leveraging simple path counts instead of random walk probabilities, addressing limitations in capturing local graph structures. The reviewers unanimously recognized the theoretical and empirical contributions, with strong support for SPSE's improved expressivity, particularly in distinguishing cyclic patterns. While some concerns were raised about computational scalability and the need for further hyperparameter tuning, the authors provided thorough rebuttals, clarifying algorithmic details and proposing future directions for optimization. The experimental design was praised for its rigor, including significance testing and comparisons with RWSE across diverse benchmarks. Although performance gains were noted as modest in some cases, the method's novelty and potential for broader applications were deemed compelling. Given the paper's clear contributions, robust validation, and constructive reviewer feedback, we recommend acceptance to ICML 2025.
Decision: Accept (poster)