Bridging Graph Position Encodings for Transformers with Weighted Graph-Walking Automata
Authors: Patrick Soga
David Chiang
Venue: Accepted by TMLR ()

Abstract:  A current goal in the graph neural network literature is to enable transformers to operate on graph-structured data, given their success on language and vision tasks. Since the transformer's original sinusoidal positional encodings (PEs) are not applicable to graphs, recent work has focused on developing graph PEs, rooted in spectral graph theory or various spatial features of a graph. In this work, we introduce a new graph PE, Graph Automaton PE (GAPE), based on weighted graph-walking automata (a novel extension of graph-walking automata). We compare the performance of GAPE with other PE schemes on both machine translation and graph-structured tasks, and we show that it generalizes several other PEs. An additional contribution of this study is a theoretical and controlled experimental comparison of many recent PEs in graph transformers, independent of the use of edge features.

Published in Transactions on Machine Learning Research (3/2023)
Bridging Graph Position Encodings for Transformers with Weighted Graph-Walking Automata
Patrick Soga
psoga@nd.eds edu
Deportment of Computer Science and Engineering University of Notre Dame
David Chiang
dchiang edu
Department Computer Science and Engineering University of Notre Dame
Reviewed on OpenReview: https: // openreview. net/ forum? id= Edd=tE2N:0000 tE2N:
Abstract
A current goal in the graph neural network literature is to enable transformers to operate on graph-structured data, given their success on language and vision tasks. Since the trans- former's original simusoidal position encodings (PEs) are not applicable to graphs, recent work has focused on developing graph PEs, rooted in spectral graph theory or various spa- tial features of graph. In this work, we introduce new graph PE, Graph Automaton PE (GAPE), based weighted graph-walking automata (a novel extension of graph-walking automata). We compare the performance of GAPE with other PE schemes on both machine translation and graph-structured lasks, and we show that it generalizes and connects with several other PEs. An additional contribution of this study is a theoretical and controlled experimental comparison of many recent PEs in graph transformers, independent of the use of edge features.
1 Introduction
Transformers (Vaswani et al., 2017) have seen widespread use and success in recent years in deep learning, operating on numerous types of data. It is natural to also apply transformers to grapt-structured data, treating the input graph's vertices as a bag of tokens. There are two important issues to be resolved for a proper formulation of a graph transformer: first, how should a graph's edges and edge features be taken into account in the transformer architecture, and second, what is an appropriate position encoding (PF) for transformer operating on a graph? We focus on answering the latter by using graph automaton compute the PEs for graph transformer.
Designing PFs for graph transformers is not new topic in the graph neural network (GNN) literature. Broadly speaking, following the terminology used by Zhang et al. (2019) to describe approaches in developing graph convolutional networks, PEs can be categorized as being (1) spectral or (2) spatial in nature. Spectral methods leverage the graph Laplacian, an highly useful descriptor of key structural features of the graph that are able describe and model phenomena such as heat diffusion and electrostatic interactions. In contrast, spatial methods use local, node-level features help the transformer differentiate nodes in the graph. Examples of these features include node degree, shortest-path distance, and land-lgnding probability during random walk.
In this work, we propose GAPE (Graph Automaton PE), a PE scheme that is inspired by neither spectral nor spatial methods but rather weighted graph automata. GAPE provides a more principled approach with connections various previous PEs while performing comparably. We show connections between GAPE and other PE schemes, including the sinusoidal encodings of Vaswani theoretical basis for its generalization of PEs from strings graphs. Further, although do not
(2017), providing a more satisfying

---

Published in Transactions on Machine Learning Research (3/2023)
provide experimental results, GAPE is able to give PEs for directed graphs unlike spectral methods which assume undirected graphs.
In addition, GAPE is able to provide distributed representations for use as PEs. Other graph PE schemes have different strategies for delivering a k-dimensional encoding; spectral methods might use the first k eigenvectors of the Taplacian (Dwivedi et al., 2020), while spatial methods might consider random walks of up to k steps (Dwivedi al., 2022). These are not distributed representations, in the sense that particular dimensions of the PE of node correspond to particular features of that node in the graph. One consequence of this is that the choice of k may depend on the size of the graph for example, the graph might not even have k cigenvectors.
To outline our contributions, GAPE (1) can theoretically and empirically simulate sinusoidal PEs and achieves nearly the same BLEU score on machine translation (MT), (2) has mathematical connections with other graph PEs including personalized PageRank (Page et al., 1998) and the Laplacian encoding by Dwivedi al. (2020) under certain modifications, (3) competes with other recent. PEs on several graph and node-level tasks, and (4) gives k-dimensional distributed representation for any desired k. In addition, while we do not provide experiments, GAPE is able to encode directed graphs, unlike spectral PE methods. Further, we provide a controlled experimental comparison of recent position encodings independent of the use of edge features.
2 Related Work
Spectral methods use the eigenvalues and eigenvectors of a graph's Laplacian matrix to construct a PE. In- formally, a graph's Laplacian matrix can be thought to measure the "smoothness" of functions defined on the graph; and its cigenvoctors happen to be the smoothest functions. The cigenvoctors can then be interpreted as descriptors of how information propagates through the graph. For example, Laplacian eigenvectors can be used for graph clustering (Fiedler, 1973; Shi & Malik, 2000), modeling heat diffusion (Coifman & Lafon, 2006), and solving the max-flow /min-cut problem (Chung, 1997). Given these traits, deriving PE based on the eigenvalues and eigenvectors of the graph Laplacian is well-motivated.
Dwivedi & Bresson (2021) draw on ideas from Belkin & Niyogi (2003) and use the smallest & eigenvectors of the graph Laplacian according to their associated eigenvalues as PEs. Dwivedi et al. (2020) also claim that these eigenvectors are generalization of the original Transformer's sinusoidal encodings. We test the effectiveness of these eigenvectors as PFs in an MT context in Section 4. Kreuzer et al. (2021) take a more comprchensive approach, employing an attention-bascd method to produce PE informed by potentially the entire spectrum of the graph Laplacian. However, save for augmentations by Zhang et al. (2021), these methods restrict the graph transformer to operating on undirected graphs. This is to ensure that each graph's Laplacian matrix is symmetric and therefore has real cigenvalucs.
In rastr spatial hot utilize local node properties such as node degree (Ying et al., 2021), self-landing probability during random walk (Dwivedi et al., 2022), and shortest path distance (Li et al., 2020; Ying et al., 2021; Mialon et al., 2021). These methods improve the performance of graph transformers and GNNs in general, and they are less theoretically motivated than the spectral methods, leading to specific cases where their effectiveness may be limited. For example, in regular graphs and cycles, a node's degree is not enough to uniquely identify its position. Other techniques such as those involving random walks are highly local; PEs such as one by Dwivedi et al. (2022) require a choice of fixed neighborhood size to walk. To our knowledge, most PFs such as those currently discussed fall into the spectral or spatial categories with no overall framework connecting them.
Regarding the use of finite automata in neural networks, Johnson et al. (2020) develop Graph Finite-State Automaton (GFSA) layer to learn new edge types. They treat learning the automaton's states and actions as reinforcement learning problem and compute a policy governing when the automaton halts, returns to its initial state, or adds an edge to its output adjacency matrix. The GFSA layer can successfully navigate grid-world environments and learn static analyses of Python ASTs, A key difference between the GFSA layer and GAPE that GAPE primarily concerned with generating node PEs rather than learning new odge types. Further, the GFSA layer sees its most efficient use on DAGs or graphs with few initial nodes whereas GAPE is intended to be used on arbitrary graphs.
2

---

Published in Transactions on Machine Learning Research (3/2023)
3
GAPE: Graph Automaton Position Encoding
3.1 Weighted graph-walking automata
In this section, we define weighted version of graph-walking automata (Kunc & Okhotin, 2013). Graph- walking automata, as originally defined, run on undirected, node-labeled graphs; the graphs also have a distinguished initial node, and for every node, the incident edges are distinguished by labels called "direc- tions." Here, we consider directed graphs (and handle undirected graphs simply by symmetrizing them). Our graphs do have initial nodes.
Definition 1. Let Σ be finite alphabet. A directed node-labeled graph over Σ is tuple G (V, where
(I.....n) is a finite set of nodes;
f: V - maps nodes to labels;
gaxa is an adjacency matrix, that is, Aij = if there is an edge from / to j, and Aij 0 otherwise.
If E (1....m mm.
also think of as matrix in {0, 1) moxn such that each column has single 1. Definition 2. Let Σ (l.....m) be finite alphabet. A weighted gruph-walking automaton (WGWA) over Σ is a tuple M = (Q. S. o, (4, T), where
{1, . k) is finite set of states;
S is set of starting states;
R kxm is matrix of initial weights;
μ: Σ R kxk maps labels to matrices of transition weights;
E fxm is matrix of final weights."
If m == then for simplicity we just write μ. Definition Let M be a WGWA and G be a directed graph. A configuration of M on is a pair (q. v); where q E Q and E V. A of M G from (q.u) to (r, with weight w, where q S, is a sequence of configurations (11, ..... (gr, PT), where (q1,v1) u), (gr, vT) (r,v), Aw.eas for all and
(g.((v))
[ Pacsten Tr,((v)-
(1)
We can think of a graph automaton as simulating random walks with state. At cach time step, the automaton is ioned at some node and in some state. At time / 1, 1, the automaton starts at some node in state 4 with weight dg.((n) Then at each time step, if the automaton at node a in state q, it either moves to node and transitions to state r with weight μ(E(u)) halts with weight (q,((M)-
3.2 Position encodings
To encode the position of node v using a WGWA M, we use the total weight of all runs of M starting in any configuration and ending in configuration (r, v). Let R, be the set all runs of on G ending configuration (r, v). Define the forward weights R kxn as
Pr.v
Σ
(al)gim Han.ap Mgr-1.4r
(q1.1) (ar RR,
T-1
Σ
(al) I
The initial and final weights commonly called 2 and p (for "left" and "right"), respectively, but since these letters commonly used for eigenvalues and spectral radii, respectively, we use and instead.
3

---

Published in Transactions on Machine Learning Research (3/2023)
which is the total weight of all run prefizes ending in configuration (r, We can rewrite this
Pr,y = (a0r,
Σ
(al)
Myr4--1 [=1
(g).)) (ann).ngr..reee (g.er))RR..
T>1
T-2 Hgiges
= (al)r.
Σ
Σ
(al)gr.
ugg Auv
4.ut
= =alrr, +
Pa Pquullgr
q,0
The matrix version of the above is
P= P=+
(2)
Setting == 1, then (APEM(1) p..v ol (where is elementwise multiplication) is our PE for v. Notice that whether particular node is able to be assigned PE does not depend on k, unlike the random walk encoding (Dwivedi et al., 2022) Laplacian eigenvector PE (Dwivedi al., 2020). The columns of P can be viewed as a distributed reprosentation in the number of states of the WGWA. It should also be noted that one could in principle replace A with any weighted adjacency matrix, which we do in Section 3.3 when connecting GAPE with other PEs. Doing so results in a minor conceptual change to GAPE, scaling the transition weights of the WGWA for each of its runs.
To solve Eq. (2) for P, one may use the "vec trick" (Petersen & Pedersen, 2012, p. 59 60):
vee P vec PA+ al (A" H vec + al
(I- AT AT vec P= al
where vec flattens matrices into vectors in column-major order, and @ the Kronecker product. However, solving the above linear system directly for vec P runs in O(k3n²)) time due to inverting (I-A* @ b p²),, which is impractical for even small graphs given a large enough batch size. We need a more efficient method.
Note that solving for P in Eq. (2) is essentially computing the graph's stationary state, or fixed point, according to the weights of runs taken by the WGWA. A similar mathematical approach is taken by Park et al. (2022) and Scarselli et al. (2009) who compute fixed points graphs outside of the context of automata. Unlike these approaches which attempt approximate the fixed point for tractability (Park al., 2022) or because the fixed point may not be guaranteed (Scarselli et al., 2009), we compute the fixed point exactly using the Bartels-Stewart algorithm (Bartels & Stewart, 1972): an algorithm for solving Sylvester equations (Horn & Johnson, 2013, p. 111), family of mairix equations to which Eq. (2) belongs.
Using this algorithm, Eq. (2) can be solved more efficiently than using matrix inversions in O(n + k3) time. To solve Eq. (2), we use an implementation of the Bartels-Stewart algorithm from SciPy (Virtancn et al., 2020). This solver is unfortunately non-differentiable, and 8o, unless otherwise indicated, we randomly initialize a and a using orthogonal initialization (Saxe et al., 2014) without learning them.
In practice, if Xy Rd is the feature vector for where d is the number of node features, then use x =,, + GAPF (v) as input to the transformer. Tf k # d, then we pass GAPFM(v) through linear layer first to reshape it. Further, because, in Eq. (2), P is not guaranteed to converge unless 1 where is the spectral radius of we scale by an experimentally chosen "damping" factor y < 1.
3.3
Connection with other PEs
We move draw connections between GAPE and other PEs.
3.3.1
Sinusoidal encodings
For any string w -i--- Wny we define the graph of w be the graph with nodes (1,.... n). labeling ((1) and ((i) for i 1, and edge from i to (i+ for all i = 1, n=
4

---

Published in Transactions on Machine Learning Research (3/2023)
Proposition 1. There erists WGWA M such that for any string w, the encodings GAPEM for all nodes in the graph of w are equal to the sinusoidal PEs of Vaswoni et al. (2017).
Proof. G is the graph of string, the behavior of M G is similar to unary weighted finite automaton (that is, weighted finite aulomaton with singleton input alphabet), which DeBenedetto & Chiang (2020)
have shown can recover the original sinusoidal PEs. Let
0
0
cos 01
sin 01
0
1
0
sin 01
cos 01
0
1
0
0
0
COs 02
sin f
J
T
0
sin 02
cos 02
:
where 02 = 1000000-------- Then the PE for node is (a:,1) which can casily be checked to be equal the original sinusoidal PEs.
To verify the above proposition, we ran an MT experiment benchmarking several graph PE schemes and compared their performance with GAPE using the open-source Transformer implementation Witwicky, with default settings. Results and complete experimental description below in Section 4.
3.3.2 Laplacian eigenvector encodings
Next, we turn to connect GAPE and LAPE (Dwivedi et al., 2020), which is defined as follows.
Definition 4. Define the graph Laplacian to be L D where D is the degree of node Let V be the matrix whose columns some permutation of the eigenvectors of L, that is,
LV VA
where A is the diagonal matrix of eigenvalues. Then if k S define
LAPE(r) Vv
Remark 2. If we assume an undirected graph and use the Laplacian matrix I. in place of A, then there is a WGWA M with n states that computes LAPE encodings. Namely, let m 1, a = 0, let μ be constrained to be diagonal, and let Tg.1 for all q. Modifying Eq. (2), we are left with solving = =PPL for
But observe that μ - and p VT solution to this equation, in which case GAPF LAPE(V).
While the above truc, some cavcats are order. First, the choice μ does depend on L and therefore the input graph. Second, the theoretical equivalence of GAPE and LAPE requires using the graph Laplacian in place of A, which is less interpretable in automaton setting. Third, since we require a 0, then the system (I-A² & μ) vec P = al is no longer guaranteed unique solution, and so there are also trivial solutions to P = LPL that need to be removed from consideration when solving for P. The connection between GAPE and LA PF is therefore largely formal.
3.3.3 Personalized PageRank & random-wal walk encoding
Next, we discuss a connection between GAPE and Personalized PageRank (PPR) and the random-walk PE (RW) used by Dwivedì et al. (2022), which simplificatinn of work by Li et al. (2020).
As described by Zhang et al. (2016), the vth entry of the PPR vector PPR(u) of node u is the probability that a random walk from u reaches v with some damping value B [0. That is, at each time step, the random walker either restarts with probability & or continues to a random neighbor with probability 1 1- B.
hhtpss//gthhuubomm//////////// wtt////www/////wwwcckk.
5

---

Published in Transactions on Machine Learning Research (3/2023)
Table 1: RW vs PPRP with min-man max normalization to bring both PEs to similar scales, Dataset descriptions
and experimental details regading the transformer and its hyperparameters are Section
PE scheme
CYCLES (1) ZINC (J)
RW
99.95
0.2077
PPR
100.00
0.198
(P)(") therefore be interpreted PE for where PPR(u), measures the relative importance of with respect to Formally, we define
PPR(u) = Beu (1-B1) -B
where en is a one-hot hot vector for a and = AD-1 where D the degree matrix of the graph. In matrix form, the PPR matrix II is
BI+ (1 (I.
Written this way, we see a similarity between Eq. (3) and Eq. (2).
Remark 3. we replace with W, there a WGWA M with states that computes Namely, replace A with W and set
n, μ (1 B)I, and al BI. Then GAPEM (4) PPR(u) for all nodes u.
The choice to replace with results dividing the automaton's transition weights during each run according to each traversed node's out-degree. Under this modification and the substitutions in the above remark, GAPE nearly generalizes PPR, minorly differing in how transition weights are computed.
Next, draw a connection between GAPE and RW bridged by PPR.
Definition 5. Let be node in the graph. Then RW( is defined by
(u) Wmar (W2) Jaur.... (W*) E ER
for some experimentally chosen k.
In other words, RWu)); the probability that a random walk of length starting at u returns to u. Now, Eq. (3) can be seen as a way of calculating something analogous to RW. Since Nu, is the probability of a node landing on node y during an infinitely long random walk, then I,, is the self-landing probability of random walker starting al node и, which captures similar information is that RW(u) is determined by random walks of a fixed length. It turns out encodings as RW(u) by taking the diagonals of the PPR matrix for successive powers of W. That is, if 11 is the PPR matrix using W', then we can define the PPR Power (PPRP) encoding of a node by
RW(u). The only difference
recover very similar
PPRP(u)
[n (II MUC............................. (IT(K)) )mm] E
Intuitively, PPRP(u); is the self-landing probability of random walker during an infinitely long random walk with step size of i. Interestingly, while PPRP and RW are not equal, their relative values are nearly identical, and they give nearly identical performance on certain graph tasks as depicted in Fig. 1 and Table 1, respectively. With this, the same postprocessing steps to construct RW can be applied to GAPE through GAPE's connection with PPR construct PPRP, PE that is analogous and empirically equivalent RW.
4 Experiments
In this section, we compare GAPE experimentally to the following graph PEs:
RW Random Walk (Dwivedi et al., 2022; Li et al., 2020)
LAPE LAplacian PE (Dwivedi al., 2020; Dwivedì & Bresson, 2021)

---

Published in Transactions on Machine Learning Research (3/2023)
RW
PPRP
1.0
1.0000
42
42
40
0.8
0.9998
32
30
30
28
28
26
24
Node
20
18
16
0.4
16
18
0.9994
14
14
12
0.9992
2-
2
0
0.0
0
PE dimension
PE dimension
Figure 1: Comparison of RW with PPRP where & = and B 0.999 for graph in CYCLES, While PPRP is not calculating self-landing probabilities, the relative differences are the same.
SA Spectral Attention (Kreuzer et al., 2021)
SPD+C Shortest Path Distance + Centrality (Ying et al., 2021)
Ying et al. (2021) use "Centrality" to refer to node degree. We compare all of the graph PEs with GAPE in two kinds of tasks: MT and graph and node-level tasks.
4.1 Machine translation
Our first experiment tests how well these various non-simusoidal graph PEs perform on MT from English to Vietnamese. To test GAPE, we use the adjacency matrix of the directed path graph of n vertices, where is the number of tokens in the input sequence, and use k 512. We also initialize a,1 with a normal initialization and set all other columns of to 0 in order to force the WGWA to start walking the path graph from its first node.
For LAPE, we experiment with two different graphs: the path graph of n vertices and the cycle graph of n vertices. We use the path graph to explore the suggestion that the Laplacian eigenvectors of the path graph are a natural gencralization of the sinusoidal encodings (Dwivedi et al., 2020). We also experiment with the cycle graph because its Taplacian eigenvectors form the columns of the DFT matrix (Davis, 1979) which Bronstein et al. (2021) note share similar structure with Transformer's original sinusoidal encodings. LAPE with the path graph is denoted by LAPE-P while LAPE with the cycle graph is denoted by LAPE-C. For SA,
the cycle graph.
However, the sinusoidal encoding for a node in a sequence does not depend on the length of the sequence, but LAPE for a node и does. So, to try to obtain a better fit to sinusoidal encodings, we try an additional variant of LAPE, which we call LAPE-C1OK, where the cycle graph is fixed with 10, 000 vertices in which the path graph representing the input sentence can be embedded.
For RW, we the path graph of 1024 vertices (the transformer's maximum input length) with 20-hop neighborhood. SPD+C uses the same path graph RW and uses shortest path distance embedding size of 256 and degree embedding size of 2 since any node in the path graph can have maximum degree of 2.
The results are shown in the first column of Table 2. We see that GAPE achieves higher BLEU score than every other graph PE and very nearly matches the original sinusoidal PEs of Vaswani et al. (2017), giving empirical evidence confirming Proposition and establishing GAPE as a generalization of sinusoidal PEs. Further, despite previous speculations on the connection between eigenvectors of the cycle graph Laplacian and the sinusoidal encodings, I.PPE-,, LAPF-C, LAPF-C1OK, and SA underperform. While the

---

Published in Transactions on Machine Learning Research (3/2023)
eigenvectors of the path and cycle graph Laplacians are indeed simusoidal, it appears they are unable to recover the performance of the original transformer's PE in practice.
Surprisingly, SPD+C performs poorly despite its shortest path distance encoding being closely related to the relative PE by Shaw et al. (2018); Huang et al. (2019). However, it makes sense that the degree encoding is of little use since there are only two degree types in the path graph: one to denote the beginning and end of the sentence, and another to represent the positions of all other tokens. Under the degree encoding, no two tokens' positions between the start and end tokens are distinguishable.
4.2 Graph- and node-level tasks
4.2.1 Datasets
We additionally compare performance of GAPE with the other PEs on 7 undirected graph tasks, Below, we give descriptions of each dataset, their importance, and experimental details.
ZINC (Irwin et al., 2012) is graph regression dataset with the task of predicting the solubility of various molecules. Given the wide applications of GNNs on molecular data, we thought to use ZINC as it is one of the most popular molecular graph datasets used in the literature. For consistency with the literature on transformer PEs, we use the 12K subset of the full 500K dataset used by Dwivedi et al. (2020) and Kreuzer et al. (2021) and use batch size of 128.
CSL (Murphy et al., 2019) is a graph classification dataset of circular skip link (CSL) graphs. Each CSL graph is 4-regular with n nodes in a cycle and skip links of length k which define isomorphism classes to distinguish. We use the same datasot as Murphy et al. (2019) and follow Chen et al. (2019) choosing n = 41 and k 10. Murphy al. (2019) and Xu et al. (2019) show that the 1-dimensional Weisfeiler-Lchmar isomorphism test (1-WL, test) (Weisfeiler & Teman, 1968) is unable to distinguish between isomorphism classes of CSL graphs and that messagg-passing passing GNNs are at most as powerful as the 1-WL test. So, PE that succeeds on this datasct can be seen as enhancing the expressive power of its host GNN. There are 150 graphs lotal, and following Murphy et al. (2019), we perform a 5-fold cross validation split with 5 sets of train, validation, and test data and report the average accuracy. We use a batch size of 5.
CYCLES (Murphy et al., 2019; Loukas, 2020) cycle detection dataset also meant to test the theoretical power of given GNN. Loukas (2020) showed the minimum necessary width and depth of a message message-passing GNN to detect 6-cycles, and in this task, we are interested in the additive power of cach PE in detecting 6-cycles. We use the same train, test, and validation splits as Loukas (2020), using 200 graphs for training, 1000 graphs for validation and 10,000 graphs for test with a batch size of 25.
CYCLES-V is also a cycle detection datasct, except with varying cycle lengths. Each graph is a copied from CYCLES, and nodes are added to lengthen cycles and maintain similar graph diameters. Whereas positive samples of CYCLES only contains 6-cycles, positive samples of CYCLES-V contain cycles of length ranging from 6 to 15. We made this adjustment to CYCLES because we wanted to test the generalizability of RW sceing as the choice of random- walk neighborhood size crucially affects its performance; clearly, RW will be able to detect cycles of length k if its neighborhood size is at least k. We use the same train, validation, and test splits and batch size as CYCLES.
PATTERN and CLUSTER (Dwivedi et al., 2020; Abbe, 2018) are node classification datasets generated using the Stochastic Block Model (Abbe, 2018), which is used to model communities within social networks according to certain eyperparameters such as community membership probability. PATTERN has 2 node classes task while CLUSTER has 7. We use the same splits as Dwivedi et al. (2020) with 10,000 graphs for train and 2,000 graphs for validation and test. We use batch size of 26 and 32 for PATTERN and CLUSTER, respectively.
PLANAR is a new dataset we generate to test the abilities of each PE to help the transformer correctly classify whether a given graph has a planar embedding. We introduce this task as another test of the theoretical power of cach PE. For many graphs, non-planarity can be detected by merely counting nodes since a graph is not planar if [E| > 3/V|- by Euler's formula. However, exactly determining whether a graph is non-planar requires checking whether there are subgraphs homeomorphic to the complete graph K5
8

---

Published in Transactions on Machine Learning Research (3/2023)
the utility graph K3,3 (Kuratowski, 1930; Wagner, 1937). We use 7,000 graphs for training and 1,500 for validation and testing. On average, each graph has 33 nodes. We use a batch size of 32.
PCQM4M<2 is a dataset from the Open Graph Benchmark Large-Scale Challenge (OGB-LSC) (Hu et al., 2021), a series of datsets intended to test the real-world performance of graph ML models on large-scale graph tasks. PCQ24Mv2 is a graph regression dataset with the task of predicting the HOMO-LUMO energy gap of molecules, an important quantum property. As labels for the test set are private, we report performance the validation set. The train set is comprised of 3,378,606 molecules while the validation set has 73,545 molecules. We use batch size of 1024. Due to time and hardware constraints, report metrics based on the 80th epoch during training.
For GAPE, on MT, we used PE dimension k = 512 and a damping factor = 1. On the graph-level tasks, we use k = 32 and y = 0.02. For RW, we choose = 20 on all tasks except for CYCLES-V, V, where we chose k 9 in order to test its generalizability to longer cycle lengths. For LAPE, we use = 20 on all tasks, following Dwivedi & Bresson (2021). For SA, we use k 10 on all tasks, following Kreuzer et al. (2021).
4.2.2 Experimental setup
We use the graph transformer from Dwivedi & Bresson (2021) for our backbone transformer, as it is a faithful implementation of the original Transformer model capable of working on graphs. All models for the graph tasks were subject to a parameter budget of around 500,000 as strictly as possible similar to Dwivedi & Bresson (2021) and Kreuzer et al. (2021). Since there is little consensus how to incorporate edges and edge features into graph transformer, omit the use of edge features in all of our tests for a fair comparison, only using node features.
Across all tasks, we use the Adam (Kingma & Ba, 2015) optimizer. For nearly all tasks, we use 10 layers in the graph transformer, 80 node feature dimensions, 8 attention heads, learning rate of 0.005, reduce factor of 0.5, and patience of 10. For ZINC, we follow Dwivedi et al. (2020) and use learning rate of 0.007 and patience of 15. CSL is such a small dataset that we opted to shrink the number of transformer layers down to 6 and maintain paramcter budget of around 300,000 for greater training speed and to avoid overparamettixalion.
SA uses transformer encoder to compute its PE. For this transformer, we use 1 attention layer, 4 attention heads, and 8 feature dimensions in order to respoct the 500,000 paramcter budget. For CSL, we reduced the number of attention heads to to respect the 300,000 parameter budget.
For SPD+C, we vary the size of the node degree and shortest-path embeddings according to each dataset since each dataset contains graphs of varying sizes. Degree embedding sizes ranged from 64 to 256, and the shortest-path embedding sizes ranged from 64 to 512.
Table 2 shows performance on graph datasets using neighborhhodd-levl attention. Bold numbers indicate the best score of that column up to statistical significance (I-Lest, p=0.05). For MT, best metrics are indicated considering only the non-sinusoidal encodings.
For the graph tasks, Bascline refers to the absence of any PE. For MT, Bascline refers to the original sinusoidal encodings by Vaswani et al. (2017). For each dataset, we take the average of 4 runs each conducted with different random seed. We report metrics from each dataset's test set based on the highest achieved metric on the corresponding validation set.
4.2.3 GAPE variants
We also try several variations of GAPE, with the following normalization and initial weight vector selection strategies.
GAPE Row-wise softmax on μ without damping factor y.
GAPE Same as GAPE' but with a column-wise softmax on a.
GAPE; GAPE# Like GAPE" and GAPE*, respectively, but use m = 20 node labels and initialize each initial weight vector ar to different random vector for each label t.
9

---

Published in Transactions on Machine Learning Research (3/2023)
Table 2: Results on MT and Graph Tasks. MT is measured by BLEU score, ZINC and PCQM4M<2 are measured by mcan absolute error (MAE), and the rest are measured by accuracy. OOM stands for Out Of Memory.
PE scheme
MT (1)
ZINC (1)
CSL (T)
CYCLES (1)
PATTERN (1)
CLUSTER (T)
PLANAR (T) CYCLES (T)
POQM4M+2 (1)
Baxeliue
32.6
0.337
0.10
50.00
83.91
71.77
50.00
73.31
0.123
LAPE.P
17.3
LAPE-C
LAPE-CIaK
16.1
LAPE
0.311
100.00
97.08
85.05
72.14
96.11
88.53
0.120
SA
16.9
0.248
87.67
89.52 99.52
83.61
72.84
97.45
81.11
0.158
20.8
0.207
93.50
99.95
86.07
72.32
98.50
90.97
0.116
SPD+C
0.263
10.00
88.44
96.00
GAPE
0.251
10.00
79.03
0.122
GAPE
2.863
10.00
$1.39
84.82
74.03
64.35
90.68
0.313
GAPES
1 1,330
48.67
84.66
69.96
70.57
75.12
89.01
0.556
GAPE
2.067
10.00
83. 12
83.46
72.39
63.33
91.76
0.914
GAPES
0.837
58.00
85.43
81.53
72.06
70.48
95.12
0.440
GAPE
0.539
86.01
71.87
95.05
0.319
Table 3: Runtime for computing PEs (k 20) in seconds. Results averaged across runs on Ubuntu
22.04 LTS desktop equipped with an AMD Ryzen 7 3700X 8-core CPU and 32GB DDRA RAM.
PE scheme
ZINC (L)
CYCLES (L)
PATTERN (L)
LAPE
13.79
28.59
886.46
RW
28.93
49.61
446.80
GAPE
8.34
19.40
769.21
GAPEmax Like GAPE* but different node label for each node (m n)) and initialize each initial weight vector different random vector.
The rationale behind versions of GAPE is that it is counter-intuise for the transition weights of an automaton be negative, and so normalizing the rows of μ should give a more probabilistic interpretation of the WGWA's traversal of the graph. The rationale behind is to normalize the columns of according the PPR understanding of GAPE; teleportation probabilities cannot be negative.
Finally, recall that a, the matrix of initial weights from Eq. (2), assigns different initial weights to each node label. While our base variation of GAPE uses only one node label, we also tried using m = 20 labels. The hope is that varying the initial weights can help GAPE learn on graphs with high levels of symmetry, such as those from CSL. By assigning each node a different initial weight vector, the automaton should be forced compute different weights for nodes with similarly structured neighborhoods. We also experiment with giving every node unique initial weight vector by letting N, where N is larger than the size of any graph in the given dataset, and giving every node different node label.
4.2.4 Discussion
The graph lasks reveal the shortcomings of the vanilla transformer. Without a PE, it is unable adequately distinguish non-isomorphic graphs in CSL, and also struggles to detect 6-cycles and planar caanar/non-oo /non-planar graphs. All other PEs are able improve on the baseline transformer, except the CSL task where most PEs do not achieve 100% accuracy.
It is interesting that SA underperforms relative to LAPE on many graph tasks given how its approach positions it as an improvement on LAPE and performs better than LAPE when incorporated in the spectral attention graph transformer devised by Kreuzer et al. (2021). While the encoder used to create the PE may need more parameters, a more likely explanation is that performance suffers from lack of incorporating edge embeddings, which the spectral attention graph transformer assumes but we omit for fairer comparison of the node PFs alone.
10

---

Published in Transactions on Machine Learning Research (3/2023)
0.3
0.010
0.2
0.005
0.1
Node
0.000
0.0
00.
-0,005
-0,010
-0.3
10
12
14
16
18
20
22
24
26
28
30
10 12 14 16
18
20
22 24 26 28 30
PE dimension
Figure Comparing GAPE with varying number of node labels m. Left is GAPE with m 1, and right is GAPE with m 20. Nodes are ordered according the order in which they were inserted into the graph when CSL was constructed.
We think it is natural to see that RW performs nearly perfectly finding 6-cycles since 20-hop neighbor- hood is enough to uniquely encode nodes in those 6-cycles, but performance begins to fall on CYCLES-V as expected as a 9-hop neighborhood is unable to provide a unique encoding to nodes in cycles of length greater than
GAPE's (y = 0.02) performance surpasses other PEs only on PATTERN and CLUSTER, with the other variants showing more competitive performance in other datasets. We give a discussion on the various factors causing these trends in the following subsections.
Table 3 compares the runtime for computing LAPE, RW, and GAPE according to three different sized datasets. ZINC, CYCLES, and PATTERN are increasing in average graph size. ZINC has 12K graphs with 23.16 nodes on average; CYCLES has 11.2K graphs with 48.96 nodes on average; PATTERN has 12K graphs with 118.89 nodes on average.
We that GAPE faster to compute for smaller graphs, but RW overtakes both LAPE and GAPE for large graphs. This is likely because RW is computable via matrix powers while cigendecomposition for LAPE and use of the Bartels-Stewart algorithm for GAPE are more computationally demanding. Despite GAPE's theoretical time complexity being at least as large as that of LAPE, we suspect that GAPE's advantage regarding smaller graphs is due to efficiencies in the Sylvester equation solver.
4.2.5 Effect of number of states on performance
One thought for improving performance of GAPE on the graph tasks is to increase the number of states used in the WGWA on which it is based. However, we observed no positive trend in performance as we increase the number of states. For most tasks, increasing the number of states can even worsen performance. Table 4 shows performance on ZINC, CYCLES, CLUSTER, and PATTERN as the number of states varies using the base GAPE method in Table 2 with damping factor y 0.02. One thought is that adding states to the automaton adds risk of instability; if the GAPE encoding of node the total weight of all runs from any initial configuration to ru, for all possible r, then adding states means adding possible runs which may lead to weights that are too large, depending on the initialization of μ.
4.2.6 Effect of number of initial weight vectors
Another thought to consider how performance varies the number node labels increases. We see Table that increasing from 1 to 20 grants noticeable but not very large performance gains nearly all
11

---

Published in Transactions on Machine Learning Research (3/2023)
Table 4: GAPE Performance as k varies
k
ZINC (1)
CYCLES (1)
CLUSTER (T)
PATTERN (T)
8
0.281
79.70
72.41
85.76
16
0.279
86.80
72.55
78.24
32
0.251
79.03
73.40
85.99
64
0.278
80.36
69.90
75.52
128
0.269
82.28
72.14
79.49
datasets except for CSL. We think this is because increasing m forces GAPE to assign different initial weights for runs starting at otherwise seemingly identical nodes. In other words, increasing is akin to conditioning the automaton's 's starting weights on distinet node labels on the graph. Such a labeling allows GAPE to distinguish between nodes with the same neighbors and nodes with neighbors with the same features, aiding in classifying highly symmetric graphs like CST graphs. This explanation applies to the cycle detection datasets as well as increasing m presents up to 3.36% increase in accuracy on CYCLES-V.
We further note that when assigning every node unique initial weight vector in consistent fashion in GAPF we see further improved performance on many of these highly symmetric graph datasets, most notably achieving 100% on CSL. However, on none of these GAPE variants where m > 1 do we see a performance gain on PATTERN, CLUSTER, or PLANAR; we instead see a significant amount of overfitting, An explanation is that increasing m may encourage the transformer to rely too heavily on each node's 's initial weight vectors to memorize node positions, leading to poor gencralizability on graphs that do not have highly symmetric structure. In other words, increasing strengthens the transformer's notion of node "identity" which is useful for distinguishing nodes in symmetric substructures like atom rings and cycles but less useful for tasks where nodes are part of variety of less symmetric substructures.
Fig. 2 illustrates more clearly the effects of increasing m for CSL graphs. We see that setting m = 1 results in assigning the same PE to every node in the CSL graph, preventing the transformer from learning the task. In contrast, setting m = 20 diversifies the PE, allowing the graph transformer to distinguish between identical neighbors and neighbors with identical features.
5 Limitations and Conclusion
While GAPE and its variants are competitive on certain datasets, they struggle to outperform the other PEs on datasets like CST, CYCLES, and CYCLES-V without setting m 1. Further, even with m > 1, GAPE's performance worsens on other datasets. Improvements on GAPE should seek to improve performance on data involving highly symmetrical structures like cycles, and more work needs to be done to ensure GAPE is able to retain performance even increases. As it stands, it seems doubtful that a transformer equipped with GAPE with m = should be more powerful than the 1-WL test, and there is no single variant of GAPE that results in better performance overall.
Another limitation of GAPE, is the computational difficulty of solving for P. Using the "vec trick" allows us learn и and a, but runs far too slow and consumes too much memory. We run out of memory when testing PATTERN with a batch size of 26 and k = 32, and shrinking the batch size to 18 and number of states to k = 10 results in a single epoch taking over 1.25 hours, making learning μ and a impractical with this method. Keeping μ and random means giving up possible performance gains and stability. We leave alleviating limitations to future work.
To sum up, GAPE provides a more theoretically principled framework for developing graph PEs. It is gencralization of the original sinusoidal encodings on strings, and it has connections with personalizod PageRank and LAPE under certain modifications. With this, GAPE can be seen as a step towards bridging the spatial and spectral frameworks of graph PFs under graph automata.
12

---

Published in Transactions on Machine Learning Research (3/2023)
Acknowledgements
We thank the anonymous reviewers for their valuable comments. This material is based upon work supported by the US National Science Foundation under Grant Nos. IIS-2137396 and ITS-2146761.
References
Emmanuel Abbe. Community detection and stochastic block models: Recent developments. Journal of Machine Learning Research, 18(17)):1-86, 2018. URL http://jmlr. wtt.pppprrsvv///L1... 1tt.1.mmm....1. html.
R. H. Bartels and G. W. Stewart. Solution of the matrix equation AX + XB C [F4]. Communicalions of the ACM, (5(9)-800-82) 1972. doi: 011144/366173..611
Mikhail Belkin and Partha Niyogi. Laplacian eigenmaps for dimensionality reduction and data representation.
Newral Computation, 15()):1373-139, 2003. doi: 10. N0.1162/0809977003311770000
Michael M. Bronstein, Joan Bruna, Taco Cohen, and Petar Velickovie. Geometric deep learning: Grids, wwwpxiii..rg//b...
groups, graphs, geodesics, and gauges. CoRR, abs/2104.13478, 2021. URL
2104.13478.
Zhengdao Chen, Soledad Villar, Lei Chen, and Joan Bruna. On the equivalence between graph isomor- phism testing and function approximation with GNNs. In H. Wallach, H. Larochelle, A. Beygelzimer, d' d'Alché-Bue, Buc, E. Fox, and R. Garnelt (eds.), Advances Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019. URL pdf.
F. R. K. Chung. Spectral Gruph Theory. American Mathematical Society, 1997.
Ronald R. Coifman and Stéphane Lafon. Diffusion maps. Applied and Compulational Harmonic Analysis, 21(1):5-30, 2006. ISSN 1063-5208. doi: http:///bb..ogg/0..00////aatiti
URL https:// www.sciencedrrect.. ott.a//ccc.............c..//ooaa Special Issue: Diffusion Maps and Wavelets.
Philip J. Davis. Circulant Matrices. Wiley, New York, 1979. ISBN 0-471-05771-1.
Justin DeBenedetto and David Chiang. Representing unordered data using complex-weightee multiset au- tomala. In Proc. ICML, volume 119 of Proceedings of Machine Learning Research, pp. 2412 2420, 2020.
Vijay Prakash Dwivedi and Xavier Bresson. A generalization transformer networks to graphs. AAAI Workshop on Deep Learning on Graphs: Methods and Applications, 2021.
Vijay Prakash Dwivedi, Chaitanya K. Joshi, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Bench- marking graph neural networks. CoRR, abs/2003.00982. 2020. URL https://arxiv http//aaaivv..../aalaaa ab200 00982.
Vijay Prakash Dwivedi, Anh Tuan Luu, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Graph neural networks with learnable structural and positional representations. International Conference on Learning Representations, 2022.
Miroslav Fiedler. Algebraic connectivity of graphs. Czechoslovak Mathematical Journal, 23(2):298-300 305, 1973.
URL http://eudml. org/doc/ 127233.
Roger A. Horn and Charles A. Johnson. Matrir Analysis. Cambridge Univ. Press, 2nd edition, 2013.
Weihua Hu, Matthias Fey, Hongyu Ren, Maho Nakata, Yuxiao Dong, and Jure Leskovec. OGB-LSC: A largo-scale challenge for machine learning on graphs. In Thirty-fifth Conference on Neural Information Processing Systems Datasets and Benchmarks Track (Round 2). 2021. URL sttps://openrevier: net/ PorpmmiddgkeLLxo05211.
13

---

Published in Transactions on Machine Learning Research (3/2023)
Cheng-Zhi Anna Huang, Ashish Vaswani, Jakob Uszkorcit, Ian Simon, Curtis Hawthorne, Noam Shazeer, Andrew M. Dai, Matthew D. Hoffman, Monica Dinculescu, and Douglas Eck. Music transformer: Gen- erating music with long-term structure. In International Conference on Learning Representations, 2019. URL https:
John J. Irwin, Teague Sterling, Michael M. Mysinger, Erin S. Bolstad, and Ryan G. Coleman. Zinc: A free tool to discover chemistry for biology. Journal of Chemical Information and Modeling, 52(():1757-11) 1768, 2012. doi:
URL setps://doo http:///oo.ooo//////// 10211022110000 c13001277 PMID: 22587354.
Daniel Johnson, Hugo Larochelle, and Daniel Tarlow. Learning graph structure with finite-state automaton layer. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin (eds.), Advances in Newral Information Processing Systems, volume 33, pp. 3082 3093. Curran Associates, Inc., 2020. URL https: .dff
/ //proceedings. neurips. hwtpcccaii...aarppp.c.pppppppp/p
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In Yoshua Bengio and Yann LeCun (eds.), 3rd International Conference on Learning Representations, ICL, 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings, 2015. URL http:://aatitii http:://arxiiv.orgaab////
6980.
Devin Kreuzer, Dominique Beaini, Will Hamilton, Vincent Létourneau, and Prudencio Tossou. Rethink- ing graph transformers with spectral attention. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan (eds.), Advances in Neural Informalion Processing Systems, volume 34, pp. 21618 21629. Curran Associates, Inc., 2021. URL https: attps://proceediiggs www.ips.cc/pappeeeeeeeeeee .df.
Michal Kunc and Alexander Okhotin. Reversibility of computations graph-walking automata. In Proc. Mathematical Foundations of Computer Science, volume 8087 of LNCS, pp. 595 606, 2013. doi: 10.1007/ 978- 1--3--44-4000 4441-033--22 20001-2233....
Casimir Kuratowski. Sur problème des courbes gauches en topologie. Fundamenta Mathematicae, 15(1): 271-283, 1930. URL http://eudml.. http:://eedmllor/ddo//..oo org/doc///2355555
Pan Li, Yanbang Wang, Hongwei Wang, and Jure Leskovee. Distance encoding: Design provably more powerful neural networks for graph representation learning. Advances in Newral Information Processing Systems, 33:4465-4478, 2020.
Andreas Loukas. What graph neural networks cannot learn: depth vs width. In International Conference on Learning Representations, 2020. URL https://openrrviii http://///paoooooooooooo//////a/
Grégoire Mialon, Dexiong Chen, Margot Selosse, and Julien Mairal. GraphiT: Encoding graph structure in transformers. CoRR, abs/2106.05666 2021. URL https: atttps://aat wrtp:////...bbb.......... 2566://0/./21000666....
Ryan Murphy, Balasubramaniam Srinivasan, Vinayak Rao, and Bruno Ribeiro. Relational pooling for graph representations. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th In- ternational Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 4663 4673, Long Beach, California, USA, 09 15 Jun 2019. PMLR. URL http://proceedings mlr. press/v97/mmss gresss/v97/murrhy11.0 /ttp//muurphaa////// html.
Lawrence Page, Sergey Brin, Rajeev Motwani, and Terry Winograd. The PageRank Citation Ranking: Bringing Order to the Web. Technical report, Stanford Digital Library Technologies Project, 1998. URL http://citeseerx. ist psu. http///iedoo//umaarya/aaaaa
1768.
Junyoung Park, Jinhyun Choo, and Jinkyoo Park. Convergent graph solvers. In International Conference on Learning Representations, 2022. URL
Kaare Brandt Petersen and Michael Syskind Pedersen. The matrix cookbook, November 2012. URL http: //www2. compute. dtu.
Andrew M. Saxe, James L. McClelland, and Surya Ganguli. Exact solutions the nonlinear dynamics of learning in deep linear neural networks. Tn International Conference Learning Representations, 2014.
14

---

Published in Transactions on Machine Learning Research (3/2023)
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE Transactions on Neural Networks, 20(1):61-80)) 10010,00,-00 2009. doi: 10.1109/TNN. 2008.2005605.
Peter Shaw, Jakob Uszkoreit, and Ashish Vaswani. Self-attention with relative position representations. Proceedings of the 2018 Conference of the North American Chapler of the Association for Compula- tional Linguistics: Human Language Technologies, Volume (Short Papers), pp. 464-468, New Orleans, Louisiana, June 2018. Association for Computational Linguistics. doi: 10.18663/v1/N18/ https://ac.lanthollgr hww.c//antttooog.oogg///---1001-
URL
Jianbo Shi and Jitendra Malik. Normalized cuts and image segmentation. IEEE Trans. Pattern Anal. Mach. Intell,, 2288))888 905, August 2000. ISSN 0162-8828. doi: 10.1109 0011099344888666 URL http://dx. doi. org/ 10. 1109/1994..... 8886688.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukh in. Attention is all you need. In I. Guyon, U. Von Luxburg, S. Bengio, H. Wallach, R. F ergus, S. Vishwanathan, and R. Garnett (eds.), Advances in Newral Information Processing Systems, volume 30. Curran Associates, Inc., 2017. URL https: http:////oeeeg........ wwwessseerriscpco cc/paper/2017/E1a Paper. .dff.
Pauli Virtanen, Ralf Gommers, Travis E. Oliphant, Matt Haberland, Tyler Reddy, David Cournapeau, Ev- geni Burovski, Pearu Peterson, Warren Weckesser, Jonathan Bright, Stéfan van der Walt, Matthew Brett, Joshua Wilson, K. Jarrod Millman, Nikolay Mayorov, Andrew R. J. Nelson, Eric Jones, Robert Kern, Eric Larson, C J Carey, ilhan Polat, Yu Feng, Eric W. Moore, Jake VanderPlas, Denis Laxalde, Josef Perktold, Robert Cimrman, Ian Henriksen, E. A. Quintero, Charles R. Harris, Anne M. Archibald, Antônio H. Ribeiro, Fabian Pedregosa, Paul van Mulbregt, and SciPy 1.0 Contributors. SciPy 1.0: Fundamental Algorithms for Scientific Computing in Python. Nature Methods, 17:261 272, 2020. doi: 10.1038/s41592 019--66--..
Wagner. Über eine eigenschaft der ebenen komplexe. Mathemalische Annalen, 114(1):570 590, 1937. doi: 10.1007/BP015594199 URL https://dol. org/10. 1007
B. Yu. Weisfeiler and A.A. Leman The reduction of a graph to canonical form and the algebra which appears therein. Nauchno-Tedhee Technicheskaya Informatsiya, 2(9):12 16, 1968. Translation from Russian to English by Grigory Ryabov.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? International Conference on Learning Representations, 2019. URL https://openreviier wtwp:ppeerreeeeeee/eorouutraaaaa net/forummid- ryGs6iA5Km.
Chengxuan Ying, Tianle Cai, Shengjie Luo, Shuxin Zheng, Guolin Ke, Di Hc, Yanming Shen, and Tic-Ya Yan Liu. Do Transformers really perform badly for graph representation? In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan (eds.), Advances in Newral Information Processing Sys- lems, volume 34, pp. 28877 28888. Curran Associates, Inc., 2021. URL Pap.:eecccc-aaa...p......
neurips..
Hongyang Zhang, Peter Lofgren, and Ashish Goel. Approximate personalized pagerank on dynamic graphs. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD '16, pp. 1315-1324, New York, NY, USA, 2016. Association for Computing Machinery. ISBN 0781450343322. doi:
URL httpp:///do..org/1... 1141//1999/6622.. 2939804.
Si Zhang, Hanghang Tong, Jiejun Xu, and Ross Maciejewski. Graph convolutional networks: a comprehensive review. Computational Social Networks, 6(1):11, 2019. doi: 10.1186//4400444-0110066434 URL https: //doi. 100 1tt.o//rrrr...118844444400000000 00001111000000000--00000-------0
Xitong Zhang, Yixuan He, Nathan Brugnone, Michael Perlmutter, and Matthew Hirn. MagNet: A neural network for directed graphs. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and
15

---

Published in Transactions on Machine Learning Research (3/2023)
J. Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, volume 34, pp. 27003- 27015. Curran Associates, Inc., 2021. URL
16


Reviews:
[{"review_id": "4bmKQGBB74", "reviewer": "Reviewer_kBUH", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n* I found the principled approach of starting with a graph automaton and the reachability relation over its configurations using weighted transitions and labeling quite interesting.\n* The connections of GAPE to some of the existing PEs can help improve our understanding of the space of PEs for graphs.\n* The paper conducts experiments to compare GAPE with other PEs.\n\nWeaknesses\n* The actual linkage of GAPE with existing PEs is not strong. The result on sinusoidal encodings follows from DeBenedetto and Chiang (2020). PPR is also shown to be a special case. The connection to LAPE and PPRP/RW is demonstrated empirically.\n* The experimental results show that GAPE can only outperform the baselines methods in 1/8 datasets. That dataset is machine-translation which is not really on graph-structured data.\n* The authors start with simplest automata (single-state or unary alphabets) and extend the scope to some variants and multiple states and alphabet symbols. However, these explorations do not yield much benefits. Therefore, GAPE dos not show empirical benefits.\n* GAPE can be computed in cubic time in the number of graph nodes or automaton states (possibly smaller). The paper doesn't report computing costs vs. other PEs.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The success of transformers in language, vision, etc. has given rise to interest in using them for graph-structured data. However, the notion of what constitutes position and positional encoding in this setting is unclear. This paper proposes to use the formulation of weighted graph-walking automata (WGWA) to derive positional encodings (PEs) called graph automaton positional encoding (GAPE). They show how this connects to sinusoidal encodings, LAPE, personalized-pagerank and random walk based PEs. They experimentally compare GAPE with these and other PEs on machine translation and graph/node tasks.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "* Section 3.1: The authors say _We consider directed graphs_ and _Our graphs do not have initial nodes or “directions.”_. This is confusing because \"directions\" in directed edges are arrow heads. I am assuming that \"directions\" wrt initial nodes refers to the incoming edges to initial nodes that do not have source nodes. Unless it is essential, you can avoid using the term \"directions\" for the latter. Else please clarify the terms in the paper.\n* The matrix $\\ell$ can have only one 1 in each column. Please state this because $\\ell$ as a matrix does not impose this constraint.\n* What is $S$ in $q \\in S$ in Def. 3?\n* I believe the terms $\\mu(\\ell(u))_{qr}$ and $\\tau(\\ell(u))_{q,\\ell q}$ have typos, in their use of $\\ell(u)$ and $\\ell q$ respectively.\n* There other popular forms of PEs on linear data like strings, e.g., relative and rotary PEs. Any insights on how do they relate to GAPE?\n* In the proof of Prop. 2, if $m = 1$ (unary) then why do $\\alpha$ and $\\tau$ have 2 columns?\n* Why is the English to Vietnamese dataset selected for machine translation study?\n* Last para, section 4.3.4: \"GAPE's performance surpasses other PEs on PATTERN and CLUSTER.\" As per Table 3, on PATTERN, RW is the best.", "broader_impact_concerns": "Nothing specific.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "N8jji3tUEP", "reviewer": "Reviewer_Pqa9", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "$\n\\newcommand{\\R}{\\mathbb{R}}\n$\n\n## Strengths\n- The idea of using an automaton to construct positional embeddings is an interesting one, and there do seem to be some interesting relationships between their proposed embeddings and some that have been proposed previously.\n- The authors conduct some informative ablations of their technique, showing how its expressivity varies based on the number of states and on the impact of introducing random labels.\n\n## Weaknesses\n- The theoretical claims seem to have a number of correctness issues. The authors argue that their approach is a generalization of Laplacian eigenvector encodings, but I believe their derivation is incorrect. I also believe there are (fairly minor) issues with their connection to Personalized Page Rank.\n- The proposed approach is based on an automaton that walks the graph and switches states. However, the state transitions are independent of the node's position on the graph or its movement, and only seem to influence the number of steps that the automaton takes before stopping. This seems like a big limitation for the expressivity of this approach, since the automaton is essentially doing a \"blind\" random walk. (Note that the graph-walking automata defined by Kunc & Okhotin (2013), the stated starting point for the approach proposed here, gain their expressive power by using node and edge labels to influence transitions.)\n- Section 3.2, which defines the method, is quite difficult to follow. What P means, or why it satisfies (2), aren't clearly explained or well motivated.\n- The proposed algorithm appears to require a fairly-expensive matrix-inversion step, which might make it impractical to use as a position embedding for large graphs. I'm also not sure that scaling $\\mu$ by a hyperparameter at initialization is sufficient to ensure that the method doesn't break later in training due to bad conditioning.\n- Their empirical validation of their method's ability to recover Laplacian eigenvector encodings seems insufficient. They show that their method can replicate the other encodings for a fixed graph, but there is a trivial solution for recovering any encoding for a fixed graph, so this doesn't mean much.\n- Some details regarding the way their approach is actually used are unclear. For instance, their method takes as input some vectors of \"initial weights\" which are indexed by the nodes in the graph. If this is to be used as a positional encoding for new graphs, how are these initial weights determined? Are they learned for each graph separately, or are they produced by a network?\n- Some related work is not cited.\n- Their experimental results are not particularly strong and are primarily on synthetic data.\n\n## Additional comments on weaknesses\n\n### Correctness of the connection with Laplacian eigenvector encodings (3.3.2)\nThe authors claim their approach generalizes LAPE, by arguing that the output of LAPE is also the output of their approach given a particular configuration of inputs. However, I do not think this is actually true.\n\nSpecifically, the way the authors compute GAPE, described in section 2, is to solve a linear system, given the result $\\alpha \\ell$ of a matrix product. In 3.3.2, the authors rewrite the LAPE embedding to resemble the form of the GAPE embedding. However, this rewriting has $\\alpha \\ell = 0$! This means that there is not a unique solution to the (modified) GAPE equation, and the linear solver will not necessarily produce the one corresponding to LAPE. (Indeed, it is likely to produce a zero vector instead.) Actually recovering the LAPE output would require running an eigenvector computation algorithm instead of solving a linear system.\n\nEven ignoring this issue, there are also other problems that the authors discuss. Specifically, the transition matrix now depends on the graph Laplacian, and so would not generalize to new graphs, and the modified equation now uses the Laplacian instead of an adjacency matrix, making it not correspond well to an automaton.\n\n### Correctness of connection to Personalized Page Rank\nThe authors similarly attempt to show that their method is equivalent to PPR. However, I don't think this claim is accurate either. Specifically, although equations (2) and (4) are structurally similar, the matrices are the wrong dimensions. The authors set $k = 1$ and then write $\\alpha = \\beta I$, but $\\alpha \\in \\R^{k \\times m} = \\R^{1 \\times m}$ and $\\beta I \\in \\R^{m \\times m}$. Additionally, the term for $\\ell$ appears to be missing.\n\nPerhaps the authors meant to specify $\\alpha \\ell = \\beta I$, with $k = m = n$, and $\\ell = \\mu = I_{n \\times n}$? This would correspond to having each node getting a different label, every label leading to a different starting automaton state, and the automaton always staying in the same state?\n\n### Ability to recover LAPE in practice\nAlthough the authors present some empirical results on the ability of their method to recover LAPE, I didn't find their methodology convincing, and I don't think their actual findings here mean much. Specifically, they test whether, given a specific graph and its LAPE embeddings, they can learn to approximate those specific embeddings using GAPE. However, as the authors note, there is a trivial solution to this for ANY embedding (not just LAPE): set $\\mu = 0$ and $\\alpha$ as the desired embedding.\n\nThe authors argue that their approach doesn't learn this particular trivial embedding, but there are likely many other equally-trivial solutions. In order to be convincing, this experiment would have to verify that GAPE can match the LAPE embeddings for new unseen graphs, without having a per-graph learning step.\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This work presents a method for computing node embeddings for graph neural networks, motivated by the need for positional embeddings in transformers. As far as I understand it, the method is based on summing over the weights of all paths of of an automaton that (a) start at any node with a node-label-dependent initial state, (b) repeatedly transition to any neighboring node, (c) simultaneously (but independently of the node or edge traversed) transition to a different state, (d) end at any node with a node-label-dependent final state. Mathematically, this involves solving a linear fixed-point equation with a solver algorithm, written in terms of Kronecker products.\n\nThe authors argue that this approach generalizes a wide number of existing positional encodings, but I believe there are correctness issues with many of their claims. *(Note: Most of these issues have been resolved in the updated submission, see comments below.)*\n\nThe authors show that their method can learn to reproduce a fixed embedding on a fixed graph, and that it learns well-performing embeddings for sequences if sequences are interpreted as directed graphs. They also present results on a number of synthetic datasets of graphs, finding that it performs fairly similarly to previous methods, and explore how variants of their method affect performance.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "## Important requested changes\nThis paper has a number of issues that should be addressed before I would recommend acceptance for this work.\n\n### Correctness issues\nAs I stated above, the paper has a number of correctness issues regarding its connection to LAPE and PPR. I would like to see those issues fixed.\n\n### Recovery of LAPE embeddings\nI think section 4.1 is somewhat misleading due to the presence of trivial solutions for any embedding of interest on a fixed graph, not just LAPE. If the authors want to argue that their approach provides the same benefits as LAPE, they need to show that it simulates LAPE on new graphs that it was not trained on. Otherwise, I think keeping this section would just be confusing to the reader, and I would suggest removing it.\n\n### Statements about incorrectness of prior work\nThe authors state that they \"show to be false\" the claims in Dwivedi et al. (2020) about Laplacian eigenvectors being a generalization of Transformer sinusoidal embeddings. The evidence for this appears to be that models trained using Laplacian-based positional encodings do not perform well at machine translation, whereas sinusoidal position encodings do perform well. In my view this is a strong statement that isn't supported by a lot of evidence, and is unnecessarily adversarial toward prior work.\n\nLooking at Dwivedi et al. (2020), the claim there is that the eigenvectors of the line graph are cosine and sine functions, and that this is a \"natural generalization\" of the Transformer's embeddings. The authors here also state that a cycle graph's eigenvectors are also sinusoidal. So, what is the claim being disputed here? Whether they are sinusoidal or not? Whether being sinusoidal is enough to count as a generalization? Whether they produce the same performance in a specific case?\n\n(If the authors just want to state that, despite being sinusoidal as Dwivedi et al. (2020) say, LAPE/SA encodings don't perform as well as a different type of sinusoidal embeddings, I think it would be clearer to focus on that specific claim instead of on the accuracy of prior work.)\n\n## Other suggestions and comments\n\n- Some additional related work that I think would be worth discussing:\n  - [Learning Graph Structure With A Finite-State Automaton Layer (Johnson et al. 2020)](https://arxiv.org/abs/2007.04929), which also uses automata for processing graphs and uses a linear system to compute embeddings,\n  - [The Graph Neural Network Model (Scarselli et al. 2009)](https://ro.uow.edu.au/cgi/viewcontent.cgi?article=10501&context=infopapers), an early approach to graph neural networks which also involved solving for a fixed point (but interpreted it as a fixed point of message passing rather than a sum over automaton weights), and which seems closely related mathematically.\n  - [Convergent graph solvers (Park et al. 2022)](https://arxiv.org/abs/2106.01680), another more recent approach to graph neural networks using fixed points\n- Section 3.1 mentions that the approach uses directed graphs but also that the graphs do not have \"directions\", this is a bit confusing.\n- It was difficult to follow why (2) gives \"the weights for all possible r\"; it might be worth explaining this more intuitively.\n- I'm not sure what the authors mean by \"we pass $P^T$ through a linear layer\"?\n- I don't understand what the runtime of the algorithm has to do with the orthogonality of $\\alpha$ at initialization.\n- In 3.3.2, statements about \"the eigenvectors\" and \"the solution\" should be more precise, since there are multiple solutions and eigenvectors can appear in multiple orders.\n- In 3.3.3., $\\beta$ is described as giving the probability of terminating the walk, but I believe it actually gives the probability of teleporting back to the start node? (Teleportation is later referred to in section 4.3.3 without being introduced beforehand.)\n- It wasn't clear to me why the PPRP encoding is interesting, and the method for computing it (by taking diagonals of a bunch of powers) seems just as complex as computing RW itself, without GAPE adding any value here.\n", "broader_impact_concerns": "No broader impact concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "lfe9bSNQuh", "reviewer": "Reviewer_NPZV", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strengths\n\n- It seems the proposed positional encoding can generalize to the existing positional encodings.\n\n### Weakness & questions\n- The motivation is not clear. \n  -  It is not clear why the author proposed \"weighted graph-walking automata\". The author claimed there are some shortcomings in previous Positional Encodings, but how the proposed \"weighted graph-walking automata\" addressed these shortcomings?  \n- The method section is not clear.\n  - From Sec. 3.1, it is not easy to understand what are \"graph-walking automata\" and \"weighted graph-walking automata\". It would be better if some examples/figures are provided.\n  - Is the \"w\" in eq(1) a vector or scalar? I am assuming it is a scalar. \n  - It is unclear to me, how Sec. 3.2. connects to Sec. 3.1. Why do we need to solve the eq.(2)?\n  - Is the $k$ in Sec. 3.1 the same as in Sec. 3.2?\n- The experiment looks not impressive. From table 3, the proposed method can only outperform previous baselines in 2/8 tasks. Besides, some top 1 results are not marked in bold.  \n- The dataset used in experiments seems very small, for example, 12K subsample graphs from ZINC, 150 graphs from CSL. Previous works, like graphormer, usually use large-scale dataset, like PCQM4M. I think there should be some experiments on large-scale datasets to demonstrate the proposed method is better.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper proposed a new graph PE, Graph Automaton PE (GAPE), based on weighted graph-walking automata, which can generalize several other PEs.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Refer to the \"Weaknesses & Questions\".", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: Two reviewers lean towards rejection, while the most thorough reviewer leans towards acceptance. One of the main reasons to argue for rejection was unconvincing empirical improvements, but I found the writing to be modest enough that this doesn't lead to a strong mismatch between claims and evidence. I don't think this is grounds for rejection by TMLR standards.

The main reasons for rejection are the following (independently from two different reviewers):
* the claim that it "bridges" PE for graph transformers is not demonstrated well
* the framing of their method as a generalization of other PEs is a bit exaggerated

Given that the authors were receptive to addressing other issues that arose during review and that there seems to be consensus amongst authors and Reviewer Pqa9 about the technical details around how GAPE needs to be modified to recover LAPE/PPR, I believe we should extend some trust that the writing can be updated a bit more in the camera ready version to mitigate these concerns. Please see, for example, the last discussion with Pqa9 around, "I still think it's a bit of an inaccurate claim." I'd strongly encourage the authors to update the text in the camera-ready version to precisely describe the relationship in a way that the reviewers would describe as accurate.
Decision: Accept (poster)