Learning Efficient Positional Encodings with Graph Neural Networks
Authors: Charilaos Kanatsoulis
Evelyn Choi
Stefanie Jegelka
Jure Leskovec
Alejandro Ribeiro
Venue: ICLR 2025 Poster (2025)
Keywords: positional encodings
graph neural networks
graph transformers
Primary area: learning on graphs and other geometries & topologies

Abstract: Positional encodings (PEs) are essential for effective graph representation learning because they provide position awareness in inherently position-agnostic transformer architectures and increase the expressive capacity of Graph Neural Networks (GNNs). However, designing powerful and efficient PEs for graphs poses significant challenges due to the absence of canonical node ordering and the scale of the graph. In this work, we identify four key properties that graph PEs should satisfy: stability, expressive power, scalability, and genericness. We find that existing eigenvector-based PE methods often fall short of jointly satisfying these criteria. To address this gap, we introduce PEARL, a novel framework of learnable PEs for graphs. Our primary insight is that message-passing GNNs function as nonlinear mappings of eigenvectors, enabling the design of GNN architectures for generating powerful and efficient PEs. A crucial challenge lies in initializing node features in a manner that is both expressive and permutation equivariant. We tackle this by initializing GNNs with random node inputs or standard basis vectors, thereby unlocking the expressive power of message-passing operations, while employing statistical pooling functions to maintain permutation equivariance. Our analysis demonstrates that PEARL approximates equivariant functions of eigenvectors with linear complexity, while rigorously establishing its stability and high expressive power. Experimental evaluations show that PEARL outperforms lightweight versions of eigenvector-based PEs and achieves comparable performance to full eigenvector-based PEs, but with one or two orders of magnitude lower complexity. Our code is available at https://github.com/ehejin/Pearl-PE.

Published as a conference paper at ICLR 2025
LEARNING EFFICIENT POSITIONAL ENCODINGS WITH GRAPH NEURAL NETWORKS
Charilaos I. Kanatsoulis 1+ Evelyn Choi', Stephanie J Leskovec'
Alejandro Ribeiro*:
Stanford University MIT Technical University of Munich 4 University of Pennsylvania
ABSTRACT
Positional encodings (PEs) are essential for effective graph representation learning because they provide position awareness in inherently sesition-annoste trans- former architectures and increase the expressive capacity of Graph Neural Net- works (GNNs). However, designing powerful and efficient PEs for graphs poses significant challenges due the absence of canonical node ordering and the scale of the graph. In this work, we identify four key properties that graph PEs should satisfy: stability, expressive power, scalability, and generieness. We find that exist- ing cigenvector-baser PE methods often fall short of jointly satisfying these criteria. To address this gap, we introduce PEARL, a novel framework of learnable PEs for graphs. Our primary insight is that message-passeeeee passing GNNs function nonlinear mappings of eigenvectors, enabling the design of GNN architectures for generating powerful and efficient PEs. A crucial challenge lies in initializing node features in a manner that both expressive and permutation equivariant. We tackle this by initializing GNNs with random node inputs standard basis vectors, thereby unlocking the expressive power of message- passing operations, while employing statistical pooling functions maintain permutation equívariance. Our analysis demonstrates that PEARL approximates equivariant functions of eigenvectors with linear complexity, while rigorously establishing its stability and high expres- sive power. Experimental evaluations show that PEARL outperforms lightweight versions of eigenvector-basee PEs and achieves comparable performance to full eigenvector- based PEs, but with one or two orders of magnitude lower complexity. Our code is available at wthttps://githata com/ ehe jin jin/Pearl-PP
INTRODUCTION
Positional encodings (PEs) are fundamental components of graph representation learning and play key role in the design of effective Graph Transformers (Dwivedi & Bresson 2021 Rampašek et al.) 2022) and Graph Neural Networks (GNNs) (Kipf & Welling 2016; Hu et al. 2020). Transformer architectures (Vaswani 2017) are inherently agnostic to structure and node identities, and PEs provide a powerful mechanism to incorporate positional and structural information. On the other hand, mnessge-passsnng GNNs often struggle with low expressiveness, especially when node features exhibit the same symmetries as the graph structure (Xu et al.] 2019: Morris et al. 2019; Kanatsoulis & Ribeiro 2024). By integrating structural and positional information, PEs enhance GNNs' capacity to capture patterns that would otherwise be difficult to learn and generalize.
Several graph PE methods have been proposed in the literature, which broadly be categorized into two main types: absolute PEs and relative PFs. Absolute PEs assign an embedding to each node in the graph, reflecting the node's 's role within the graph structure. Common approaches include Laplacian cigenvectors (Dwivedi & Bresson, 2021). substructure encodings (Tahmasebi et al. 2020 You al. 202T Bouritsas al. (022), random walk (RW) encodings (Rampašek et al. 2022). and eigenvector- based methods (Kreuzer et al. 2021a; Lim et al. Huang et al.). Relative PEs, on the other hand, assign representations pairs of nodes and typically utilize measures such as shortest-pane and resistance distances (Ying et al. 2021 Zhang et al. 2023), as well as RW matrices (Ma et al.
"Correspondance
EEqual senior authorship.

---

Published as a conference paper at ICLR 2025
2023:
Geisler et al. 2023). A thorough comparison between absolute and relative PEs can be found in (Black et al. (024)..
In this paper, we study absolute PEs for graphs based on four key criteria: expressive power, scalability, stability under perturbations, and generality. We find that PEs based on eigenvectors of graph Laplacian or other graph operators often struggle to satisfy all these criteria simultaneously. To better understand this, we divide rigenvector-basee approaches into two categories: those that compute the full set of eigenvectors and those that only consider the K largest. Full eigenvector approaches offer high expressive power but come with a computational complexity of ((N2) and memory complexity of ((N2), which is prohibitive for even coddium-sized graphs. The full set of eigenvectors can also be used to learn spectral graph filters (Huang et al.), which result in stable PEs. Note that stability particularly crucial for out-of-distribute generalization.
However, when only subset of eigenvectors is computed, several limitations arise. First, this intro- duces an inductive bias, as different graphs encode different information across eigenvalues, especially when they differ in size. Second, the expressive power and stability are reduced, becoming dependent on the eigengap between the selected eigenvalues. These methods also face challenges terms of stability and generalization when applied to different unseen graph structures. Consequently, this approach often leads to significantly poorer performance. Substructure- based encodings face similar challenges: while generally stable, they also introduce inductive bias and highly expressive versions require combinatorial complexity. The aforementioned challenges raise a critical research question:
Question: Can we learn generic PEs that are simultaneously expressive, stable, and scalable?
In this work, we provide an affirmative answer by proposing PEARL, a powerful and efficient framework for learnable PEs, entirely generated via message-passinggg GNNs. We begin by showing that message-pant -aasgggggagnggggggee GNNs can be understood as nonlinear mappings of eigenvectors of the graph Laplacian other graph shift operators. This insight enables the computation of rigenvector-baser PEs efficiently with linear or quadratic complexity, leveraging message- paaagggg operations. A central challenge in developing effective PEs with GNNs lies in initializing node features to ensure both expressiveness and permutation equivariance. We address this by initializing each node with a set of MM random samples, effectively breaking the symmetries between the graph structure and node features. Each sample is processed independently by GNN, and the output samples are aggregated via statistically -desiigg pooling functions to guarantee permutation equivariance. Our analysis demonstrates that PEARL is basis universal, surpasses the expressiveness of the Weisfeiler- (WL) test (Weisfeiler & Leman 1968). and generalizes the ability of counting key graph substructures. PEARL is also provably stable, inheriting the stability guarantees of GNNs (Gama et al. 2020). which are independent of the eigenvalue gap.
We further analyze the sample complexity of PEARL and show that the number of samples re- quired for effective encoding is independent of graph size. This enables the generation of powerful eigenvector- based PEs for large graphs with linear complexity. For smaller graphs, where the number of samples is comparable to the graph size, we propose an alternative model that initializes node features with basis vectors. This approach approximates the PEs in (Huang et al.) with significantly lower computational and memory complexity. We evaluate the proposed PEARL on graph classifica- tion and regression tasks on molecular graphs and social network datasets, and compare against eigen-based and structure-basee -ased absolute PEs. The results demonstrate that PEARL consistently outperforms structure- based PEs and lightweight variants of eigenvector sraervector-based PEs, achieving sig- nificant improvement on graph classification tasks. In comparison to full eigenvector-based PEs, which have computational complexity of (NN3), PEARL delivers comparable performance with significantly reduced complexity, scaling at O(N) O(N9).
2 PRELIMINARIES
A graph G = (V, E), is represented by a set of vertices V = (I.....N}, N., a set of edges E {(e, u)}. and graph shift operator (GSO) S E NNN, The GSO is typically sparse, with common choices including the adjacency matrix, the Laplacian matrix, their normalized variants, or the RW transition matrix. The nodes (vertices) in the graph are often associated with node signals x. Rd each with d features, while edges can carry edge attributes X ((,.) E &d with de features. An important operation in graphs is the spectral decomposition of the graph and refers to the eigenvalue decomposition the
2

---

Published as a conference paper at ICLR 2025
GSO, S = VAVT. Matrix V= (efei..... Un] is the orthonormal matrix of eigenvectors, and A is the diagonal matrix of eigenvalues {A, / When represents the Laplacian matrix, V are the Laplacian eigenvectors that are commonly used as node features or PEs for GNN architectures. In this paper, we study standard message- passiing GNNs, defined by the following recursive formula:
x -g (1
x ( (fa!-":.ENN(C E
Here, (u)) represents the I-hop neighborhood vertex v. The function f()) aggregates information from the multiset of signals coming from neighboring vertices, while g()) combines the signal of each vertex with the aggregated information from its neighbors. Common choices for ( and g() include the single- and multi-layer perceptron (MLP), the linear function, and the summation function.
3 OUR WORK: LEARNABLE, EFFICIENT, AND POWERFUL PEs WITH GNNs
3.1 GNNS ARE NONLINEAR FUNCTIONS OF GSO EIGENVECTORS
Our first observation is that message- passing GNNs are nonlinear functions of eigenvectors. To see this, let f() be one of the following aggregation functions:
message-passing
Σ (w)
Fus du Be
Σ MEN(())
Vd.da Fu
Fu Σ
Ty
(2)
de
du
(EN()
(EN(U)
(EN(w)
where dy is the degree of node v. Then Eq. [1 can be written as X -=-1=1) (X ()).
where S represents the adjacency matrix, the Laplacian matrix, the normalized adjacency, the normalized Laplacian, and the RW matrix, for the five choices of (() in respectiive and X E N represents the signals of all vertices at layer 1. Now let g be an equivariant MLP operating on each node independently. Note that the MLP is a common choice for function (()) for the majority be cast as: of effective GNN architectures due to its expressiveness properties. Then Eq.
K-1 Σ
x
x H
where 2, H3 E FL-I are the trainable parameters, and ar is a point wise nonlinear activation function. Note that Eq. 3 defines single-layer graph perceptron, but it can be easily generalized to a multi-layer graph perceptron by letting a represent an equivariant MLP acting on the node signals. Additionally, while we set K 2 here, higher values of K can be considered for more generalized GNN layers. It is worth emphasizing that S is never explicitly instantiated; instead, S (1-1) is computed using recursive message-passing operations, as outlined in Eq. (2).
Proposition 3.1 (GNNs are nonlinear functions of cigenvectors) A GNN defined in Eq. 7 with f()) being one of the functions in Eq. (2) and g() being multi-layer perceptron, operates nonlinear function of the GSO eigenvectors, i.e., x!!" MLP (v(*)), w Viu, :J" The trainable
purameters of the first MLP layer are not independent but depend on the eigenvalues ( and eigenvectors { of the GSO, as well as the node features X the graph:
( MLP (D()) = MIP(-1) (o (WTTOO)))
(4)
P
W 1n, Σ
Σ
X
H
11 (i, (a (1-1) (E, [E)
(5)
K=
where a,, Un when the GSO is symmetric and an V ---( when is not. MIP(-1) denotes all the layers of the MLP except the first layer.
The proof is provided in Appendix B According to Proposition 3.1 the update for node v, defined by the function g o f (g.RFt 1) Fi, can be interpreted as a nonlinear mapping (MLP) applied to Vl, but the weights of the first layer of this mapping are also mappings, i.e., W [2, f]
3

---

Published as a conference paper at ICLR 2025
Input Graphh
X, X
g
sode atcrtbaae aeseraraed
(()) fa
900
p(
(o M
Transformer
(G.
mi mi 1d
g(M)
P(M)
Emi Ar
Graph Reprosetation Leuming Framework
(9) ( Feunt
Preprocesting
Figure 1: PEARL framework: The input graph undergoes anonymization by removing its node and edge attributes. For each node, set of M random or basis attributes is generated. Each sample is then independently processed by message-passing GNN, and pooling function is applied to produce equivariant PEs. The graph structure, together with the generated PEs and any node or graph attributes, is subsequently processed using either GNN or a Graph Transformer.
(G, (G + R. The degrees freedom in the first layer of MLP are K FiFi-i (as described Eq. ()) rather than FiN, which would be the case for independent weights W. Furthermore, the dot product (ar,, X (:, depends on the eigenvectors and, for the update of node v, it only involves the components X ((-))) :],, E N,. Proposition 3.1 is applicable to most pesssag-ppassing GNN models, including, but not limited to, Graph Convolutional Networks (GCNs) (Kipf & Welling 2016). Graph Isomorphism Networks (GINs) (Xu et al. 2019), and GraphSAGE (Hamilton et al. 2017).
3.2 PEARL: EXPRESSIVE AND EQUIVARIANT POSITIONAL ENCODING NETWORKS
Following the derivation of Proposition 3.1 critical question arises: what is the optimal choice of node features that allow GNN to compute expressive and equivariant functions of the eigenvectors? Equivariant structural features augment GNNs with valuable information, but they come at the cost of increased computational complexity and inductive bias. Moreover, these features share the same symmetries as the graph structure, limiting the expressiveness of message-passing GNNs. Alternatively, unique identifiers, such as random node features, can break the structural symmetries and improve expressiveness but at the expense of permutation equivariance, which limits the model's generalization capability. To address this trade-off between equivariance and expressiveness, we propose to momentarily break the structural symmetries by initializing each node with set of M unique identifiers, while maintaining permutation equivariance in the model output via the use of statistical pooling functions. The proposed PE framework (PEARL) is illustrated in Fig. and, as we see next, ensures both high expressiveness and strong generalization.
Consider a graph G = (V,E) with N nodes. For each node E V in G, we design set of M (1) (2)
1 didmensioonl node signals {9. -00 ......th qu. [ where each q! operates as a unique identi- fier. Graph G is now associated with a of M independent initial node features represented as M
(T)) -== q (mm) E N Each pair of {G, ((m)) is independently processed via GNN 4(-), which is described by Eq. T or to produce a set of M independent outputs:
P (m)
T (g (m)
E IR Nxd,
m = 1,..,, M
Since (m) m=1 operate as unique identifiers, they break the structural symmetries and unlock the expressive power of pressage-passingg operations. However, each p(m) is not permutation equivariant, and thus not generalizable. address this, we design an equivariant function p. that involves pooling operation over the independent outputs {[(mm) Im=1, to generate the final PE for each node:
P P= ② G, (1)
+ (g.q [ E R Nxd,
(7)
4

---

Published as a conference paper at ICLR 2025
The PEARL framework can universally approximate any continuous basis invariant function.
Theorem 3.1 (Basis Universality) Let G be a graph with GSO S = VAVT. and f be a continuous function such that f(V) = f(VQ), Q O (diag (A)), for for any eigenvalues A. Then there exist GNN and a continuous equivariant p. such that f(V) p (g, q()) ...., (GG.g(")))
The proof can be found in Appendix Theorem 3.1 can be extended to handle multiple graphs by considering G as a collection of graphs represented as disconnected components. In this case, the GSO takes block diagonal form, where each block corresponds to the GSO of an individual graph.
In the following sections, we explore options for the initial node features { | and pooling functions p. key aspect of PEARL designing M independent initial attributes for each node, which enables permutation equivariance at the model's output through the use of pooling functions. This stands contrast classical methods, which typically assign a single unique identifier per node.
OUR WORK: RANDOM POSITIONAL ENCODING NETWORK (R-PEARL)
Next, we present our Random PE Network (R-PEARL). In R-PEARL we define inital node features {q(m)) m== by sampling them randomly from a probability distribution. Specifically, let [ge, 982....... Auyl" where 2, E V, be a random vector with joint distribution f. The set {q(m) } AM m= consists of M independent N-dimensional realizations of q. drawn from fq- In our experiments and analysis, q is either set of independent and identically distributed (i.id.) Gaussian random variables or set of i..dd random variables with EE [4:] and E [4"] = 1, where p 2 2.
When these samples are processed by GNN Φ the result is M (N ddmmedimnnio samples of the random matrix output (G,, q). To practically preserve permutation equivariance, we note that the distribution of & (G q) is itself permutation equivariant, as are any statisties derived from it. Therefore,
the function / can be any empirical statistic computed from the samples { ((m)) m==1 each capturing different characteristics. For instance, o could represent any statistical moment, such as the mean variance, other measures the empirical mode median. In this paper, choose to be the empirical mean due to its favorable convergence and stability properties, as well as its simplicity in implementation and low computational and memory complexity:
M Σ m=1
M
P P- .....
M Φ
(m))
1
Σ m=1
p(m)
(8)
M
4.1 SAMPLE COMPLEXITY
In this section, we analyze the number of samples required such that 1 ΣM= ((m) approximates M E o (9,g) with negligible error. To that end, make the following assumptions.
Assumption 4.1 The pointwise nonlinearity is Lipschitz continuous with Lipschitz constant Ca.
This is common assumption in deep learning and is satisfied by the widely used nonlincarities. In most cases, such as the Rectified Linear Unit (ReLU), hyperbolic tangent, and sigmoid, it holds that
C. = 1. Before introducing the second assumption, we first need to examine Eq.
3 more closely. Notice that its linear component involves Fz Fi graph filters of the form Σ k= S which is also explicitely shown in Appendix
Eq. 53
Assumption 4.2 The linear operators H (S) are bounded, ie.. | (S)] < B.
K-1 S* involved in the projection of Eq. kk=
This is another common assumption in deep learning, where the value of 3 varies depending on the architecture and task. We can now present Theorem 4.3 which characterizes the number of samples M needed for our approach to converge to the true E (G,4)].
Theorem 4.3 (Sample Complexity) Let P denote the output of the architecture described in Eq. for a graph G with ii.d. initial node features with unit variance. Also let t be I, L--layer GNN
5

---

Published as a conference paper at ICLR 2025
described by Eq. 43 with F hidden dimensions at each layer. CC 1 and 3 1/F, the number of samples M required such that:
M
Σ M m=
(G.q(m)) - EE[ (G.9)) <,, with probability at least 6,
(9)
satisfies:
M S 22
(10)
is worth noting that the above bound is independent of the size of the graphs, which suggests that proposed PE framework is well-suited for large-scale graphs. In practice, have observed that 10 100 samples are typically sufficient.
4.2 EXPRESSIVE POWER
In this section, we establish the expressive power of our proposed R-PEARL.
Corollary 4.4 (Structure Counting) Let q [qI...., [N] be set of N i.i.d. random variables such that E [g] and E[g]] = 1 for p 2 2. Then, there exists parametrization & defined by Eq. 33 such that E [ (:.4) counts the number of 3-, 4., 5-, 6-, and 7-node cycles for any given graph.
Corollary 4.4 not only highlights the expressive power of the R-PEARL framework but also provides valuable insights into its generalization ability. Essentially, the R-PEARL framework can leam not just the number of cycles each node in given graph participates in, but also a counting function that generalizes this capability to any node in any graph. The proof can found Appendix [F and based on the results in (Kanatsoulis & Ribeiro). In Corollary 4.5 we characterize the expressive power of message-pad passsiggg GNNs with our proposed PEs with respect to the Baklore--eisffillre (FWL) test (Cai et al. 1992 Morris et al. 2019 Huang & Villar 2021).
Corollary 4.5 (Expressive Power) A GNN defined in Eq. 4 with PEs produced by Eq. strictly more powerful than the 1-FWL test, when f, 9 are injective functions.
8 is
The proof of Corollary 4.5 is a consequence of Corollary 4.4 and the analysis in (Xu et al. 2019).
Note that the previous results can be improved (e.g., count cycles and cliques of higher order, go beyond 2-FWL test) when the samples {m) - m=1 drawn from structurally aware distribution, but this will increase the number of computations and outside of the scope of this paper.
4.3 STABILITY
The proposed PEs are purely generated by GNN architectures and as a result they inherit favorable stability properties of GNNs. Any stability results for GNNs hold for R-PEARL as well. For instance. let Č be perturbed version of G such that S = S + E. We can use the stability results in Gama al. 2020) and derive the following proposition.
Corollary 4.6 (Stability) Let & be a perturbed version of such that S = S with E S E. Let & be an L-layer GNN described by Eq. (3), where each layer consists of F² Lipschitz continuous filters lcf. Eq. (..2 with constant C. Under assumptions 4.1 and 4.2 with C. = and B = 1/F, the following holds:
1 M
1 M
Σ + (G.)
< (1+8VV) LE LE+
(11)
where I|-1|p is the distance modulo permutation (cf. G.I and M is the number of samples.
We can further normalize the proposed PEs by VN- L to improve the stability bound. Notably, result remains independent of the eigengap 8x. which is the difference between consecutive eigenvalues of the GSO. However, this independence does not hold for the stability of eigenvectors. According the Davis- Davis-Kahan Theorem (Davis & Kahan 1970), even small perturbation in the

---

Published as a conference paper at ICLR 2025
graph can lead to arbitrarily large differences between the eigenvector encodings of the original and perturbed GSOs. This limitation also applies to the eigenvector-bas PEs in (Lim et al.). The stability bound of the PEs in (Huang et al.) is inversely proportional to the eigengap òx between the d-th and (d + )-th smallest eigenvalues when using the first eigenvectors. This dependence mitigated if all eigenvectors
computed, but doing requires ((N3) complexity, which is impractical for large graphs. Further details on stability results are provided in Appendix G
4.4 COMPUTATIONAL COMPLEXITY
To implement R-PEARI,, we process each initial random attribute independently using message- passing GNN. Consequently, the computational complexity of the feed-forward pass is equivalent to that message- pesssag--asssing GNN multiplied by the number of samples, i.c., e (M + M) where H' represents the hidden dimension of each GNN layer. The memory complexity of serial implementation θ (NF), while for a parallel implementation, it is θ (MNF).
5
OUR WORK: BASIS POSITIONAL. ENCODING NETWORKS (B-PEARL)
The previous approach, R-PEARL, particularly advantageous for large graphs where the number of samples is much smaller than the number of nodes and edges, resulting in approximately linear computational and memory complexity. However, for smaller-scale graphs, such as molecular graphs, the computational complexity becomes quadratic. In these cases, propose using standard basis
vectors {em m= as the initial node features, where em [m] 1 and e. o m] O, thus setting M = N. Similar to the previous approach, when these samples are processed by GNN 4, the result N (N diimensoiil outputs. To maintain permutation equivariance, any equivariant function can be applied, but in this paper, we choose the summation pooling for p. Overall, B-PEARL. is cast as:
N
N
P= p (9, (G, [N)
= Σ 370
em
Σ <(())
(12)
m
Remark 5.1 (Expressivity, Stability) B-PEARL admits the same expressivity and stability properies as R-PEARL, iee. Corollaries 4.3 and 4.6 also apply, and B-PEARL can count the number 3f, 3-, 4,, 5-, 6-, and 7-node cycles, for any given graph.
5.1 RELATION TO EIGENVECTOR BASED ENCODINGS
The B-PEARL framework highly related the SPE encodings (Huang al.). defined as SPE (V, A) = p ([V (a1 (A)) VT Vdiag (ar (A)) V2J). where {as are continu- ous functions and p equivariant function. The suggested SPE implementation SPE (V, A) EN d[Viiag (a1 (A)) Vinl...., ddiag (as (A)) [(ra]),, where is a GNN, and {ar] are MLPs. The computational and memory complexity of SPE is (N*). and O (N2) respectively.
Remark 5.2 When {as) SPE (V, A) are pointwise analytic functions the SPE architecture equivalent to the proposed B-PEARL architecture in Eq. (12). The proof can be found in Appendix
5.2 COMPUTATIONAL COMPLEXITY
To implement B-PEARL, process each initial basis encoding independently using message- passing GNN. As a result, the computational complexity is θ [22 F), where F represents the hidden dimension of each GNN layer. The memory complexity for serial implementation is e (NF), while for a parallel implementation, it increases to θ (N²P).
EXPERIMENTS
In this section, we assess the performance of PEARL on graph classification, graph regression and recommendation tasks. All experiments conducted on a Linux server with NVIDIA A100 GPU.
7

---

Published as a conference paper at ICLR 2025
Table 1: Graph classification accuracy on REDDIT-B and REDDIT-M (OOM stands for out-of- memory). R-PEARL outperforms all baselines in both REDDIT-B and REDDIT-M. R-PEARL has much lower complexity than the well perl-oerfonn eigen- eigen-based methods.
Method
Computational Complexity
Memory Complexity
REDDIT-B
REDDIT-M
GCN
(N)
((N)
50.0
GIN
O (N)
(N)
91.8 1.0
56.9 2.0
GIN + rand id
O (N)
0 (N)
91.8
57.0
GSN with cliques
(N²)
(N)
91.1 1.8
56.2 1:
SignNet-8S
O (X3)
(N)
92.4
57.8
SignNet-8L
O (N)
(N)
79.5 12.3
2.7 OOM
SiguNet-full
O (X9)
O (N7)
0OM
BasisNet
O (NS)
O (NZ)
0OM
OOM
SPE
(NN)
O (N
0OM
OOM
(-PEARL((orr)
(MN)
O (NN) (MMN)
9300
59.4 1.0
6.1 ARCHITECTURES
To generate the proposed PE, & is an L-layer paessag GNN with batch normalization layers and skip connections, where
{7, 87,8,99 9). The first layer of & is a generalized GNN layer, as described in Eq. (3), and K can be greater than two. All the remaining layers in & are GIN layers (Xu et al. 2019). J. When K = 2 we omit this generalized GNN layer, and solely use GIN layers. We denote R-PEARL the architecture with random samples, described in Eq. (8), and B-PEARI. the architecture with basis vectors, described in Eq. (12). In all experiments we evaluated our model on selected values of K ranging from 18, as well as different sample sizes ranging from 10 to 200, and selected the best model accordingly. For the graph-level tasks, the R-PEARL and B-PEARL encodings are fed GINE (Hu al., 2020) architecture, which a message-passidn GNN that processes node and edge attributes, as well as the graph structure and PEs. For the recommendation tasks, the R-PEARL and B-PEARL PEs are further processed via heterogeneous identity-aware GNNs (You et al. 2021).
6.2 BASELINES
The baseline models for comparison are grouped into four categories: i) GNNs without PEs: GCN (Kipf & Welling 2016), GIN (Xu et al., 2019); ii) GNNs with unique identifiers: GIN with random IDs (Xu et 2019]]
et al.) [021] Sato et al., 2019): ; iii) GNNs with structural PEs: GSN
with cycles, GSN with cliques (Bouritsas et al. 2022 iv) GNNs with eigenvector-based PEs:
SignNet, BasisNet (Lim et al.), PEG (Wang et al.
2022
SPE (Huang et al.).
In addition, we implement SignNet-8S, BasisNet-8S and SPE-8S which are variants of the full SignNet, BasisNet, and SPE models. These variants employ the eigenvectors corresponding to the 8 smallest eigenvalues of the normalized Laplacian that still need O(N3) computational complexity. In SPE-8S and BasisNet-8S the memory complexity remains O(N²), ), but in SignNet-8S it reduces from ONN) to O(N). Furthermore, we implement SignNet-8L. utilizing only the 8 largest eigenvectors, which reduces both the memory and computational complexity O(N).
6.3 GRAPH CLASSIFICATION ON SOCIAL NETWORKS
We first evaluate our architecture on graph classification tasks using the REDDIT-B (2,000 graphs, 2 classes, 429.6 average nodes) and REDDIT-M (5,000 graphs, 5 classes, 508.5 average nodes) datasets (Yanardag & Vishwanathan, 2015). Each graph represents an online discussion thread, with nodes representing different users, and edges indicating whether one user responded to another's comment. In both datasets, the task is to predict the subreddit to which particular discussion graph belongs. To train the GNN models, we conduct 10-fold mooss-vaiidttio.. Table Table[ summarizes the mean and standard deviation of classification accuracy the 10 folds. We report the best performance observed during 350 epochs of training, as is the standard practice for this dataset. The results are presented in Table []]
We observe that R- R-PERRL outperforms all baselines on REDDIT-B and REDDIT-M. SignNet-8S achieves the second best performance, but with one two orders of magnitude higher computational
8

---

Published as a conference paper at ICLR 2025
Table 2: logP Prediction in ZINC. B-PEARL ouperforms all the baselines both in MAE and Generalization gap. It is notable that B-PEARL achieves these results with quadratic complexity compared to the second best (SPE) that operates with cubic complexity.
PE Method
NPEs
Test MAE
Training MAE
General. Gap
No PE GCN
N/A
0.1772 + 0.00-10
0.1509 = 0.0086
0.0263 0.0113
N/A
0.469 + 0.002
GIN
N/A
0.209 + 0.018
GSN with cycles
10
0.115 + 0.012
GIN rand id
0.279 = 0.023
SiguNet-8S
8
0.1034 + 0.0056
0,0418
0.0101
0.0602 + 0.0112
SignNet
Full
0.0853 + 0.0026
0.0319 = 0.0078
0.0502 : 0.0103
BasisNet-88
0.1554 0.0048
0.0513 0.0053
0.1042 0.0063
BasisNet
Full
0.1555 + 0.0124
0.0G84 0.0202
0.0989 + 0.0258
SPE-8S
8
0.0736 = 0.0007
0.0321 = 0.0058
0.0113 + 0.0057
SPE
Full
0.0093 0.0040
0.0334 0.0054
0.0359 + 0.0087
R-PEARL(OUr))
N/A
0.0696 0.004
0,0319 0.007
0.0377 0.008
B- 3-PEARL(Ours)
N/A
0.0644 + 0.001
0.0290 0.003
0,0353 0.002
complexity. Notably, SignNet-full, BasisNet, and SPE are unable to handle these datasets due to their quadratic memory complexity.
6.4 GRAPH REGRESSION ON MOLECULAR GRAPHS
We also evaluate our model on the task of predicting the penalized water-octanol partition coefficient (logP) for molecules from the ZINC dataset (Irwin et al. 2012] Dwivedi et al. 2023). We use the standard split for this dataset, which entails 10,000 molecules for training, 1,000 for validation, and another 1,000 for testing. We report the mean and standard deviation of the MAE for the model achieving the highest validation accuracy, averaged over different seeds. The results can found in Table 2 We observe that B-PEARL achieves the best results, and also the best generalization gap between the competing methods. It is also notable that R-PEARL and B-PEARL also outperform all the remaining competing methods.
We conduct experiments on the DrugOOD dataset (Ji et al. 2022). The dataset evaluates models on nut-of-distribution (OOD) generalization, focusing on three specific types of domain shifts: Assay, Scaffold, and Size. The Assay, Scaffold, and Size splits test the ability to generalize to different bioassays, molecules with different structures, and molecules of different sizes, respectively. The results are presented in Table 3 We observe that stable methods generally work better than SignNet and BasisNet, which have reduced stability. B-PEARL improves the AUC by 9.5% compared to BasisNet, and 3.8% compared to SignNet in Size OOD generalization. B-PEARL achieves a 4.6% improvement in AUC over both SignNet and BasisNet in Scaffold OOD generalization. Furthermore, B-PEARL demonstrates an advantage over SPE in size OOD generalization. This improvement likely attributed the linear scaling of SPE's stability bound with graph size, compared to the square-root scaling of PEARL's stability bound, which enhances its size generalization capabilities.
6.5 LARGE-SCALE LINK PREDICTION ON RELATIONAL DATABASES (RELBENCH)
We also test the performance of the proposed PEARL on large-scale link prediction using the Stack Exchange Q&A Website Database. To that end we utilize the rel-stack dataset for the relational deep learning benchmark (RelBench) (Fey et al.; Robinson et al. 2024). Rel-stack is a temporal and heterogemeous graph with approximately 38 million nodes. We consider two different tasks: i) pheer-post-comeent
where we predict a list of existing posts that user will comment on in the next two years, and ii) post-post--o re 1 ated, where we predict a list of existing posts that users will link given post to in the next two years. The results for the two tasks can be found in Table 4
The backbone model for this RelBench task is a heterogeneous identity-aware GNN (You et al. 202 l) and all methods are trained with batch size of 20. From Table we observe that PEARL has an 1 11 benefit over the identity-aware backbone model with no PE on the user-post poer-poott-ooment task and 2% benefit on the post--pottrrlated task. PEARL works similarly Sign but with lower complexity. It also works similarly to SignNet-8L on the -ser-post-tee comment task, while achieving 5% better performance than SignNet-8L. on the post rel ated task.

---

Published as a conference paper at ICLR 2025
Table 3: Binding Affinity AUROC results (5 random seeds) on DrugOOD, PEARL outperforms
SignNet and BasisNet, and performs comparably to SPE, while maintaining lower computational complexity.
Domain
PE Method
ID-Val
ID-Test (AUC)
OOD-Val (AUC)
OOD-Test (AUC)
No PE
92.9210.14
92.8910.14
71.0210.99
716811110
PEG
92.51100117
92.57:1.222
70.86:10.44
71.98.10.65
SignNet
92.2610021
92.43:0.27
70.1610.56
72.27:10.97
Assay
BasisNet
88.9621.35
89442=1.18
71.19#0.72
71.6620.05
SPE
92.8410.20
92.9410.15
71.2610.62
72.53:0.66
SPE-8S
92.36+0.18
92.62=0.110
70.71+0.47
71.72 0.71
(-PEARL(Our))
92.71 10
92.92=0.12
00.57+0.72
72.24=0.30
B-PEARL(ours)
90.5420.89
90.81 =0.79
70.53+0.67
71222=0:42
No PE
96.56.10.10
87.95
79.07
68.00.10.60
PEG
95.65110.29
86.20:20.14
79.171.0.97
69.15:10.75
Scaffold
SiynNet
95.48.10.34
86.73.1..56
10.70
6.64
BasisNet
85.80113.75
28.44:245
73.3611144
66.32415.68
SPE
96.322:028
88.12=0.41
80.03+0.558
69.642:0449
SPE-8S
96.44:10.099
87.88
79.3411.50
68.72:10.63
R-PEARL(Our))
06.0920.32
88.01=0.43
78.72+0..02
69.20=11.00
B-PEARL((urs)
96.06+0.29
87,56=0..8
86+-0.58
69.51=0.62
No PE
93.78+-0. 12
93.60--0.27
72-70-00
66.04-00700
PEG
92.46.00.35
92.67.10.23
82 12.4.99
66.01
Size
SignNet
93.302:0.43
03.20=20.39
80.6710.50
64.03110.70
BasisNet
86.04:14.00
85.51.1.004
11.77
60.79..3.19
SPE
92-461:0.35
92.67:0.23
82.12-10.99
66.02 :: 0.49
SPE-8S
93.68+0.20
93.86=0.122
83.04+0.63
93.32-t0.34
93.92-0.200
02.0940.44
65.89 + 1.30
B-PEARL(ours)
93.18 = 0:45
93.29 = 0.46
83.14 0.37
66.58 = 0.67
Table 4: Validation and test mean average precision (MAP) on large-scale RelBench recom- mendation tasks. PEARL has 11% benefit over the backbone model with no PE the user-post-commen task and a 2% benefit on the post-post www-p-pss--llteeeeeeeeeeeeeeeeee task.
Task
Evaluation
No PE
SignNer-SL
SignNet-8S
B-PEARL((uus)
R R-PEARL(ous))
Val. MAP
15.20
15.33
15.47
15.13
15.24
User User-post- -commett
Test
12.47
13.76
13.77
13.80
13.87
Val. MAP
8.10
7.90
7.70
8.00
8.40
Post-post-re rrelated
Test MAP
10.73
10.39
10.86
10.94
10.86
RELATED WORK
The works that are mostly relevant to our work can be grouped in categories: i) Eigenvector-
Positional Encodings, e.g., (Dwivedi & Bresson 2021
Rampášek et al. 2022 Kreuzer et al. 202
Mialon et al.) 2021 Feldman et al. 2022 Huang et al. Zhang et al. ); 11) Graph Neural Networks
with unique node identifiers, c.g., (Loukas 2019 Abboud et al. [021 Sato al. 2021 Abboud
ct al. 202 Sato et al.) 2021 Eliasof et al. 2023);
1223;111 m1i) Graph Representation Learning with Structural
Encodings, e.g., (Li et al. 2020 Ying al. [202]] You al., 2019 2021 Dwivedi al.)
Ma et al.
2023 Kanatsoulis & Ribeiro); iv) (Wang et al. [ & Ribeiro
Murphy et al.
2018).
detailed discussion can be found Appendix
CONCLUSION
In this paper, we proposed novel framework for learnable positional encodings (PEs) that addresses key limitations in existing cigenvector-bacee methods, particularly in terms of stability, expressive power, scalability, and genericness. By leveraging bessage-passing GNNs as nonlinear mappings of eigenvectors, we designed efficient PEs that maintain permutation equivariance through the use of statistical pooling functions. Our approach not only ensures high expressiveness and stability but also significantly reduces computational complexity. Experimental results demonstrate that our method consistently outperforms lightweight eigenvector- eigenvector-brit based methods, all while offering substantial improvements in computational efficiency. These findings open new avenues for developing scalable, expressive, and robust graph representation techniques, paving the way for advancements in graph-hased learning tasks.
PEs and matches the performance full
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENTS
We gratefully acknowledge the support of NSF under Nos. OAC-1835598 (CINES), CCF-1918940 (Expeditions), DMS-2327709 (IHBEM), IIS-2403188 (III;; Stanford Data Applications Initiative, Wu Tsai Neurosciences Institute, Stanford Institute for Amazon, Genentech, GSK, Hitachi, SAP, and UCB.
AI, Chan Zuckerberg Initiative,
The content solely the responsibility of the authors and does not necessarily represent the official views of the funding entities.
REFERENCES
Ralph Abboud, Ismail Ilkan Ceylan, Martin Grohe, and Thomas Lukasiewicz. The surprising power of graph neural networks with random node initialization. IJCAI, 2021.
Mitchell Black, Zhengchao Wan, Gal Mishne, Amir Nayyeri, and Yusu Wang. Comparing graph transformers via positional encodings. arXiv preprint arXiv:2402.14202, 2024.
Stéphane Boucheron, Gábor Lugosi, and Olivier Bousquet. Concentration inequalities. In Summer school on machine learning, pp. 208-240. Springer, 2003.
Giorgos Bouritsas, Fabrizio Frasca, Stefanos Zafeiriou, and Michael M Bronstein. Improving graph neural network expressivity via subgraph isomorphism counting. IEEE Transactions on Pattern Analysis and Machine Intelligence, 45(1):657-668, 2022.
Jin-Yi Yi Cai, Martin Fürer, and Neil Immerman. An optimal lower bound the number of variables for graph identifications. Combinatorica, 12(4):389-410, 1992.
Gabriele Corso, Luca Cavalleri, Dominique Beaini, Pietro Liò, and Petar Veličković. Principal neigh- bourhood aggregation for graph nets. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and
H. Lin (eds.). Advances in Neural Information Processing Systems, volume 33, pp. 13260-13271. Curran Associates, Inc., 2020. URL httpp::/prrcceeerrss.see wwwp::eddiiinn..eeees.........m
Chandler Davis and William Morton Kahan. The rotation of eigenvectors by perturbation. iii. SIAM
Journal on Numerical Analysis, 7(1):1-46, 1970.
Mohammed Haroon Dupty, Yanfci Dong, and Wee Sun Lee, Pf-gmm: Differentiable particle filtering based approximation of universal graph representations. In International Conference Learning Representations.
Vijay Prakash Dwivedi and Xavier Bresson. generalization of transformer networks to graphs. 2021.
Vijay Prakash Dwivedi, Anh Tuan Luu, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Graph neural networks with learnable structural and positional representations. In International Conference on Learning Representations.
Vijay Prakash Dwivedi, Ladislav Rampášek, Michael Galkin, Ali Parviz, Guy Wolf, Anh Tuan Luu, and Dominique Beaini. Long range graph benchmark. In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave. K. Cho, and A. Oh (eds.), Advances in Neural Informa- fion Processing Systems, volume 35, pp. 22326-22340. Curran Associates, Inc., 2022. wttp://eeee/ellee////eeeeeeeeeee www.fllspppprrra.e.eepppppppp http//ppppe//222/1122l. htppra/sssnrrrrr..seeprrrrrrrrre
URL.
(0116688200557772266667777744480 Datasets and Benchmarks. pdf
Vijay Prakash Dwivedi, Chaitanya K Joshi, Anh Tuan Luu, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Benchmarking graph neural networks. Journal of Machine Learning Research, 24 (43):1-48, 2023.
Moshe Eliasof, Fabrizio Frasca, Beatrice Bevilacqua, Eran Treister, Gal Chechik, and Haggai Maron. Graph positional encoding via random feature propagation. In International Conference on Machine Learning, pp. 9202-9223. PMLR, 2023.

---

Published as a conference paper at ICLR 2025
Or Feldman, Amit Boyarski, Shai Feldman, Dani Kogan, Avi Mendelson, and Chaim Baskin. Weisfeiler and leman go infinite: Spectral and combinatorial pre-colorings. Transactions on Machine Learning Research, 2022.
Matthias Fey and Jan Eric Lenssen. Fast graph representation learning with pytorch geometrie, 2019.
URL httts:://tatttttt org/ abs/ /25//1900 1903. 02428
Matthias Fey, Weihua Hu, Kexin Huang, Jan Eric Lenssen, Rishabh Ranjan, Joshua Robinson, Rex Ying, Jiaxuan You, and Jure Leskovec. Position: Relational deep learning saaning-graph representation learning relational databases. In Forty-first International Conference Machine Learning.
Fabrizio Frasca, Beatrice Bevilacqua, Michael Bronstein, and Haggai Maron. Understand- ing and extending subgraph gnns by rethinking their symmetries. In S. Koyejo, S. Mo- hamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh (eds.). Advances in Neural In- formation Processing Systems, volume 35, pp. 31376-31390. Curran Associates, Inc., 2022. URL httpt: httttp:://proceeddnnne neur oetp http:///eooo.o/////ao/aaa//////.
Fernando Gama, Joan Bruna, and Alejandro Ribeiro. Stability properties of graph neural networks.
IEEE Transactions on Signal Processing, 68:5680-5695, 2020.
Simon Geisler, Yujia Li, Daniel J Mankowitz, Ali Taylan Cemgil, Stephan Günnemann, and Cosmin Paduraru. Transformers meet directed graphs. In International Conference on Machine Learning, pp. 11144-11172 PMLR, 2023.
Simon Geisler, Arthur Kosmala, Daniel Herbst, and Stephan Günnemann. Spatio-spectral graph neural networks. arXiv preprint 2411 2024.
Aditya Grover and Jure Leskovec. node2vec: Scalable feature learning for networks. In Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 855-864, 2016.
William I. Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning large graphs. In Proceedings of the 31st International Conference on Neural Information Processing Systems, pp. 1025-1035, 2017.
Xiaoxin He, Bryan Hooi, Thomas Laurent, Adam Perold, Yann LeCun, and Xavier Bresson. generalization of vit/mlp-mixer to graphs. In International conference machine learning, pp. 12724-12745. PMLR, 2023.
W Hu, B Liu, J Gomes, M Zitnik, P Liang, V Pande, and J Leskovee. Strategies for pre-training graph neural networks. In International Conference on Learning Representations (ICLR), 2020.
Ningyuan Teresa Huang and Soledad Villar. A short tutorial on the weisfeiler-lehman test and its variants. In ICASSP 2021-2021 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 5533-8537. IEEE, 2021.
Yinan Huang, William Lu, Joshua Robinson, Yu Yang, Muhan Zhang, Stefanie Jegelka, and Pan Li. On the stability of expressive positional encodings for graphs. The Twelfth International Conference on Learning Representations.
John J Irwin, Teague Sterling, Michael M Mysinger, Erin S Bolstad, and Ryan G Coleman. Zinc: free tool to discover chemistry for biology. Journal of chemical information and modeling, 52(7): 1757-1768, 2012.
Yuanfeng Ji, Lu Zhang, Jiaxiang Wu, Bingzhe Wu, Long- Huang, Tingyang Xu, Yu Rong. Lanqing Li. Jie Ren, Ding Xue. Houtim Lai, Shaoyong Xu, Jing Feng, Wei Liu, Ping Luo, Shuigeng Zhou, Junzhou Huang. Peilin Zhao, and Yatao Bian. Drugood: Out-of-distribution (ood) dataset curator and benchmark for ai-aided drug discovery a focus on affinity prediction problems with noise annotations, 2022. URL Ittps:: / //axx www.orgg.........o.... 2201 09637
Charilaos Kanatsoulis and Alejandro Ribeiro. Counting graph substructures with graph neural networks. In The Twelfth International Conference Learning Representations.
12

---

Published as a conference paper at ICLR 2025
Charilaos Kanatsoulis and Alejandro Ribeiro. Graph neural networks powerful than think. In ICASSP 2024-2024 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 7550-7554, IEEE, 2024.
Jinwoo Kim, Dat Nguyen, Seonwoo Min, Sungjun Cho, Moontae Lee, Honglak Lee, and Seunghoon Hong. Pure transformers are powerful graph learners. Advances in Neural Information Processing Systems, 35:14582-11495, 2022.
Thomas Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. arXiv preprint arXi::1609.009000 2016.
Devin Kreuzer, Dominique Beaini, Will Hamilton, Vincent Léturrneau, and Prudencio Tossou. Rethinking graph transformers with spectral attention. Advances in Neural Information Processing Systems, 34:21618-2162,, 2021a.
Devin Kreuzer, Dominique Beaini, Will Hamilton, Vincent Létourneau, and Prudencio Tossou. Rethinking graph transformers with spectral attention. In M. Ranzato, A. Beygelz- imer, Y. Dauphin, P.S. Liang, and Wortman Vaughan (eds.), Advances in Neural In- formation Processing Systems, volume 34, pp. 21618-21629, Curran Associates, Inc., 202lb. URL
neur httppagssaeeepppppppppppeeee wttpp/scceeppeeeeeseeseeee/eee/e www.ss/apprree/22222 Paperaap..... pdf
File
Juho Lee, Yoonho Lee, Jungtaek Kim, Adam Kosiorek, Seungjin Choi, and Yee Whye Teh. Set trans- former: A framework for attention-based permutationninvariint neural networks. In International conference on machine learning, pp. 3744-3753, PMLR, 2019.
Pan Li, Yanbang Wang, Hongwei Wang, and Jure Leskovec. Distance encoding:
Design provably more powerful neural networks for graph representation learning. Advances in Neural Information Processing Systems, 33:4465-4478 2020.
Yujia Li, Daniel Tarlow, Mare Brockschmidt, and Richard S. Zemel. Gated graph sequence neural networks. In Yoshua Bengio and Yann LeCun (eds.), 4th International Conference on Learning Representations, ICLR 2016, San Juan, Puerto Rico, May 2-4, 2016, Conference Track Proceedings, 2016. URL httpttt::/aixii.oooo org/ /1tbl.///11..... 15411.1111111
Derek Lim, Joshua David Robinson, Lingxiao Zhao, Tess Smidt, Suvrit Sra, Haggai Maron, and Stefanie Jegelka. Sign and basis invariant networks for spectral graph representation learning. In The Eleventh International Conference on Learning Representations.
Andreas Loukas. What graph neural networks cannot learn: depth vs width. In International Conference on Learning Representations, 2019.
Liheng Ma, Chen Lin, Derek Lim, Adriana Comero-Soriano, Puneet K Dokania, Mark Coates, Philip Torr, and Ser-Nam Lim. Graph inductive biases in transformers without message passing. In International Conference on Machine Learning, pp. 23321-23337. PMLR, 2023.
Haggai Maron, Heli Ben-Hamu, Nadav Shamir, and Yaron Lipman. Invariant and equivariant graph networks. In International Conference on Learning Representations, 2018
Grégoire Mialon, Dexiong Chen, Margot Selosse, and Julien Mairal. Graphit: Encoding graph structure in transformers, 2021. URL WRLLhttts://axxiis wttggbga//g/gooa/////////// 05667
Christopher Morris, Martin Ritzert, Matthias Fey, William L Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe Weisfeiler and leman go neural: higher-order graph neural networks. In Proceedings of the Thirty-Thire AAAI Conference on Artificial Intelligence and Thirty-Fine First Innovative Applications of Artificial Intelligence Conference and Ninth AAAI Symposium Educational Advances Artificial Intelligence, pp. 4602-4609, 2019.
Ryan Murphy, Balasubramaniam Srinivasan, Vinayak Rao, and Bruno Ribeiro. Relational pooling for graph representations. In International Conference on Machine Learning, pp. 4673. PMLR, 2019.
13

---

Published as a conference paper at ICLR 2025
Ryan L Murphy, Balasubramaniam Srinivasan, Vinayak Rao, and Bruno Ribeiro. Janossy pool- ing: Learning deep sermutation-invariin functions for variable-size inputs. arXiv preprint arXiv:1811.01900, 2018
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Köpf, Edward Yang, Zach Vito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style. high- high-perfrmmacce deep learning library, 2019. URL https: wttpvaiivvvv..////////////aaaava org/ abs/ 11122//191... 01703
Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. Deepwalk: online learning of social representations. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, volume 2 of KDD '14, pp. 701-710. ACM, August 2014. doi: 10.1 14/22433663330. 2623732. URL http: //cx doi org/10 10. www.11112223332 2623732
Ladislav Rampášek, Michael Galkin, Vijay Prakash Dwivedi, Anh Tuan Luu, Guy Wolf, and Do- minique Beaini. Recipe for a general, powerful, scalable graph transformer. Advances in Neural Information Processing Systems, 15:14501-145111 2022.
Joshua Robinson, Rishabh Ranjan, Weihua Hu, Kexin Huang, Jiaqi Han, Alejandro Dobles, Matthias Fey, Jan E Lenssen, Yiwen Yuan, Zecheng Zhang, et al. Relbench: A benchmark for deep learning on relational databases. arXiv preprint arXiv:2407.200: 20060, 2024.
Ryoma Sato, Makoto Yamada, and Hisashi Kashima. Approximation ratios of graph neural networks for combinatorial problems. Advances in Neural Information Processing Systems, 32, 2019.
Ryoma Sato, Makoto Yamada, and Hisashi Kashima. Random features strengthen graph neural networks. In Proceedings of the 2021 SIAM International Conference on Data Mining (SDM), pp. 333-341. SIAM, 2021.
Balasubramaniam Srinivasan and Bruno Ribeiro. On the equivalence between positional node embeddings and structural graph representations. In International Conference on Learning Repre- sentations.
Behrooz Tahmasebi, Derek Lim, and Stefanie Jegelka. Counting substructures with higher-order graph neural networks: Possibility and impossibility results. arXiv preprint arXiv:2012.03174, 2020.
A Vaswani. Attention is all you need. Advances in Neural Information Processing Systems, 2017.
Haorui Wang, Haoteng Yin, Muhan Zhang, and Pan Li. Equivariant and stable positional encoding for more powerful graph neural networks. In International Conference on Learning Representations, 2022.
Boris Weisfeiler and Andrei Leman. The reduction of graph to canonical form and the algebra which appears therein. N77, Series, 2(9):12-16, 1968.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In International Conference on Learning Representations, 2019. URL https //openreview net/ http://ommmmmddyyyaaa
Pinar Yanardag and SVN Vishwanathan. Deep graph kemels. In Proceedings of the 21th ACM SIGKDD international conference on knowledge discovery and data mining, pp. 1365 1374, 2015.
Chengxuan Ying, Tianle Cai, Shengjie Luo, Shuxin Zheng, Guolin Ke, Di He, Yanming Shen, and Tie-Yan Liu. Do transformers really perform badly for graph representation? Advances in neural information processing systems, 34:28877-28888, 2021.
Jiaxuan You, Rex Ying, and Jure Leskovec. Position-awand awwree graph neural networks. In International conference on machine learning, p 7134-7143. PMLR, 2019.
Jiaxuan You, Jonathan M Gomes-Selman Rex Ying, and Jure Leskovec. Identity-aware graph neural networks. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp. 10737-10745, 2021.
14

---

Published as a conference paper at ICLR 2025
Bohang Zhang, Lingxiao Zhao, and Haggai Maron. On the expressive power of spectral invariant graph neural networks. In Forty-first International Conference on Machine Learning.
Bohang Zhang, Shengjie Luo, Liwei Wang, and Di He. Rethinking the expressive power of gnns via graph biconnectivity. In The Eleventh International Conference on Learning Representations, 2023.
L Lingxia Zhao, Wei Jin, Leman Akoglu, and Neil Shah. From stars to subgraphs: Uplifting any GNN with local structure awareness. In International Conference on Learning Representations, 2022. URL wttpthtss//ppppeeieeeeee net/
htwpeewwwwee//eetmtteee forum? id=Mspk WYKOEH
A RELATED WORK
Eigenvector-based Positional Encodings: Positional encodings are crucial component in applying transformers to graph data and further integrating structural information in graph neural networks (GNNs). A notable approach for such positional encodings (PEs) is the use of Laplacian eigenvec- tors. These eigenvector-base graph-related tasks, as demonstrated in (Dwivedi Bresson 202T) and (Rampášek et al. 2022). Additionally, they can be incorporated in attention mechanisms as seen in (Kreuzer et al. 202
PEs have been shown to enhance performance in transformers on
Miilonn et al./ 2021), and (He et al. 2023). Laplacian cigenvectors can also be used to improve performance in the context of GNNs (Kim et al. 2022).
However, eigenvector baced positional encodings face challenges with stability and sign ambiguity. Small structural changes in graphs can cause significant change in eigenvectors and their correspond- ing positional encodings. In addition, the sign ambiguity eigenvectors can introduce unwanted inconsistencies in these positional encodings. Works such as (Lim et al.) and (Huang et al.) ad- dress these issues by designing sign-invariant or basis-invariant models to produce these PEs, or by making the PEs more robust and stable. (Zhang al.) introduced the concept of the expressive power of spectral invariant GNNs, which are GNN architectures augmented with invariant spectral features, and provided a unified theoretical framework to analyze them. Feldman et al. (2022) 2 used eigenvector- heat kernels to generate node embeddings to overcome the limitations of the WL test. Geisler et al. (2024) combine spatial and spectral graph filters in a unified GNN architecture.
Randomized Graph Neural Networks Initializing GNNs with unique node identifiers to enhance the expressive power has been first proposed by (Loukas 2019 9 Abboud et al. 2021 Sato et al. (02T). In particular, (Abboud et al. 1)21) and (Sato et al.. 2021 used random node features as inputs to GNNs, leading to enhanced function approximation. though at the expense of permutation equivariance, a key property in graph learning. Eliasof et al. (2023) proposed a method for generating PEs in graph neural networks by leveraging random feature propagation, inspired by the power iteration method and its gemeralizations. The core of their approach involves concatenating several intermediate steps to compute the dominant eigenvectors of a propagation matrix. Dupty et al. proposed a randomization technique through particle filtering. The
method that approximates the individualization-reenee particle filtering GNN (PF-GNN) employs 1-WL-based initialization method, which is subsequently refined with particle filtering sampling to overcome the 1-WL limitations.
Structural encodings are also impor- tant capturing aspects of a graph's 's structure, such connectivity and neighborhood information. (Li et al. 2020) uses distance PEs for GNNs (distance from an anchor node) using shortest paths and random walks. One approach using distance-based information between nodes through methods like shortest paths or random walks, to captural structural information for transformers (Ying et al., 202T) (You et al., (219)) YYuu et al. (02T). Other methods learn structural PEs directly. For instance, (Dwivedi et a learn embeddings that are initialized with Laplacian eigenvectors or random walks. Similarly, (Ma et al. 2023) learn a linear combination of the Laplacian for creating relative PEs.
Graph Representation Learning with Structural Encodings:
Node Embedding Methods: One foundational approach capturing meaningful graph represen- tations is through node embeddings. DeepWalk (Perozzi et al., 2014) and node2vec (Grover & Leskovee 2016) are early instances of these approaches and leverage random walk strategies to learn node embeddings on graphs. Although these methods show the significance of capturing structural information, they lack expressivity and do not incorporate many learnable components.
15

---

Published as a conference paper at ICLR 2025
Similar techniques to ours have been introduced in (Wang et al. 2022) which generate PEs by applying transformations on the Laplacian. On the other hand, Kanatsoulis & Ribeiro recently analyzed the capability of GNNs to count substructures using expectation pooling functions. Srinivasan & Ribeiro explored the equivalence between node embeddings and structural represen- tations, showing that the expectation of node embeddings serve structural representations of the graph, and proposed methods to sample informative node embeddings for enhanced graph representation learning. Finally, Murphy et al. (2018) investigated models of permutation-ine invvrriann functions as averages of permutation sensitive functions applied to all reorderings of a group.
Equivariant pooling:
A.1 COMPARING PEARL STRUCTURAL PES
The proposed PEARL framework can provably count important substructures in any graph, such as cycles, cliques, and quasi-cliques. More importantly, can generalize the counting function to graphs not seen during training, demonstrating the robust generalization ability of PEARL. This naturally invites comparison with methods that explicitly compute these substructures independently. Below, we summarize the key comparison points with such methods:
not limited pre-defined motifs, such as cycles or cliques. can compute other potentially important substructures, such as dense subgraphs, chordal cycles, or combinations of motifs, that explicit counting methods might omit simply because they are not pre-specified. Notably, the number of possible motifs in graph grows combinatorially, highlighting the flexibility and breadth of PEARL.
Expressivity: PEARL
Explicitly counting high-order motifs, especially at the node level, can be computation- ally expensive. PEARL bypasses this challenge by learning to capture these structures implicitly, making it more scalable large and complex graphs
Complexity:
Bias: Predetermining which motifs to count introduces bias into the model. For example, molecular graphs often benefit from detecting cycles, while social networks emphasize cliques dense sub- graphs. In contrast, PEARL task-agnostic and allows the data to guide which motifs are most relevant, adapting the specific requirements of the application. On the flip side, when the training data have small sizes, learning can benefit from the specific biases that structural PEs admit.
B PROOF OF PROPOSITION 3.1
Under the ussumptions of Proposition 3.1 the GNN has the following recursive formula:
( K-1
Σ ( Sh x
x (1) MLP sxx("-)) MLP(-1)
(13)
where MLP(-1) denotes all the layers of MLP except the first layer, and K = 2. We compute the eigenvalue decomposition 5 VA* VT, and some extra algebraic manipulations.
K-1 Σ
X 1-)
VV
H
(14)
K
(-)
σ
k Un w. (1-1))
(15)
1m x=1
K-1
|;, P. H )) (16)
(-1(
Unn
0
(1-1 |;, 1]
of x (1-1)
k= ==
16

---

Published as a conference paper at ICLR 2025
where Vl:nn] Un and A In n| = An. We now focus the output of the first MLP layer X (11)
X (1) MLP (x(1.))
Then each feature of X (1.1) can be written as follows:
( =
n
x
15 1]
1 x (
1ss Fi-1]]
H
(17)
K-1
Σ
H (i, flo (1) [::1]
(18)
Σ F K-1
Σ Σ (1. < Bn. x11 [::1] On
(19)
Σ W [n, Un
(20)
where
Pi-1 K-1
W W [n
Σ
(i < Un (111) [i,d)>
(21)
As result ( = a (VW). When S is not symmetric we can replace US with [- This concludes the proof.
C BASIS UNIVERSALITY OF PEARL
We consider the general form of PEARL:
P= p 1 (G.
..... 1 (i) E IR Nxd,
(22)
where is an unrestricted equivariant function and t is a message- masssng GNN with skip connections.
We let (mm) e. and M N. From Proposition 3.1
we have:
x
MLP (V) MLP(-1) (VW))
(23)
Rl K-
W In fl = Σ
x H k
[i,
fl (111) 1.
(24)
k=U
We omit the nonlinearities from the GNN, and for X Cm have:
K-1 x(k) = vW, W [n, (Wn, em)
Σ
h
(25)
k=0
As a result, W [n. f] is a polynomial on the cigenvalues hy (An) = Ek-1 h IflA sealed by (Un, em) We will now use the following lemma.
Lemma C.1 Let 9 be a graph with N nodes and GSO S E NNN, S (f AN }} be the multiist of eigenvalues of S: S can have repeated elements (eigenvalues). In addition, let M = (ui...., } be the ordered set of all distinct (non-repeated) eigenvalues of S. We can always design poynomial filter such that
(A) = { (15)
x Pj
(0
(26)
17

---

Published as a conference paper at ICLR 2025
Proof: Let
h (11) h (12)
Mi u ...
ho hn
122 112 ... ...112
Bhh
(27)
(14)
Mg Mig ... p4
K-
[h
B is a Vandermonde matrix and when K q, the determinant of B takes the following form:
det (B)
II
(M--1))
(28)
1Si<iS9
Since the values μ4, are distinct, B has full column rank and there exists a polynomial h with unique parameters h === B-eeey (115) such that h (A) = 7 (15)) if = μs,, and h (A) = 0 if = μ3 # Pt-
Using Lemma C.1 we can design hy (An) = Ek-1 hs [ such that hy (An)
1, if Am M4
(29)
0, AS = P4 #1
Under this parametrization, X(K)
(K) takes the form:
x (K) [V V em: em...., Mg VT em] RN
(30)
My
where Vay is the eigenspace (orthogonal space of the cigenvectors) corresponding to eigenvalue Fz Since we independently feed e,....,e eN to the PEARL architecture, we will have output samples for each output feature, i.e., N samples for (: ʃ]. We represent the m-tth sample as x [;, m), and for the fh output feature, we have the following samples:
(
[Va ei....... Vu, VT ex] Vu, VT py?
(31)
process the output samples of each feature an equivariant function p. to get the final output embedding:
== (VA) VT ME..... ....... Vu VT) We can choose p to operate on each feature independently i.e..
(32)
Y Y=p ( (V V g(9)) (Ve,
(33)
where { i=1 is universally approximating permutation equivariant or invariant function, such high-order tensor IGN (Maron al.) 2018). Equation (33 is the definition of BasisNet (Lim cct al.). BasisNet universally approximates all continuous basis invariant functions, which proves that PEARL is also universal approximator of basis invariant functions.
D PEARL IS A UNIVERSAL FUNCTION OF EIGENVALUES
Theorem D.1 (Eigenvalue Universality) Let be a graph with GSO S V VAVT and f be any continuous function of eigenvalues f (diag (A)). Then there exists a GNN + and a continuous invariant functtont such that (diag (A)) [ (9.q()) ()...) ①b (g q ())].
Proof: Going back to Eq. performs graph pooling. Then the output y E I29 takes the form:
33 we can set p g = 1s diag (-), which is an invariant function that
y 1dd diag (V,,, VH
1 diag (Vn, vz) = [1 (Va)). 2,,..., 1s (Vr,.) 21]
(34)
[mult (n1) ...., mult (H,)),
(35)
where mult (1s) is the multiplicity of eigenvalue μ4:
18

---

Published as a conference paper at ICLR 2025
Using Lemma C.1
design hy (An)
Ek= K-1 h
such that
My. if An Ps
hy (Nn)
(36)
0, if An = H4 + p4
24
As result we can design a set of 2q filters
such that
f=1
h2f-1 (Ax)
[1s, if An = 14s
(37)
0, if An = 11 + 14
1, if An = =1
has (An)
(38)
0, if An = Mi + 14
Under this parametrization, ( takes the form:
V ( [V V ii emy V VT ii Em...., Ma Mig
emr Vi,, V V.eem My
em E RRNx22
(39)
and according to previous analysis we have
= (V V HiS
Vn VT HY Kapga Pg
VT
Va, VT
(40)
We can choose o to be invariant function that involves graph pooling operations:
p MLP [1" diag (),.... 1d diag (-)
(41)
Then the output 2o takes the form:
a1 ..... 1s diag (Vn,ll V.T. Mg) y = MLP 1 diag (V A1 ViT.) 1 diag (V,,, VT)
1 diag
(V V
MLP [1" (Vn,) (Vp.).1pp 31p,, 1s (Va)) . .1....,1"" 1s (Vp.) 21 1s (Vn,).²4 = MLP [mult (fr ) ,n, mult (fn)... mult (Fg) Mag mult (14))) which is universal function of eigenvalues. This concludes our proof.
(42)
(43)
E SAMPLE COMPLEXITY
To prove Theorem 4.3 and characterize the sample complexity of our approach, we will use this version of Chebychet's inequality (Boucheron et al., 2003):
1 M
Σ (p(m) - Ei (G, (G.)))) Ze S
(4 (9,
(44)
M 22
To establish bound for the variance of the output (G 9). we begin by analyzing how pointwise nonlinearity affects the variance of a random variable. Let X be a random variable with variance Var(X), ). and let a be Lipschitz continuous function with Lipschitz constant C.. Our goal is to examine the impact of applying a to X, specifically focusing on how it influences the variance of the transformed variable a (X).
E.1 EFFECT OF POINTWISE ACTIVATION TO THE VARIANCE OF A RANDOM VARIABLE
Since is Lipschitz continuous with constant Co. for any values of X and E[X], apply the Lipschitz condition:
lo (X) (E[x)) < - E[X]].
Squaring both sides, we have
- (3
Taking the expectation of both sides gives the following:
Bi(a (X) (E[x])) C -[x]))
19

---

Published as a conference paper at ICLR 2025
Since [ [[[ Var (X), this simplifies:
BI (X) (E(XI)) & O2 (X).
Now we expand the left-hand side of the previous equation.
El(ar (X) (E[X))) E (0 (X) (X)) (R(XT))²
(45)
B[(a (X) - ((l - a (B[X)))²
(46)
+ 2B|< (ar (X) - B/o (X)))
(E(XT)) >
(47)
B[(o (X) (Ex a (E[X)))
(48)
Var (ar (X)) + (Blr (X)] (E[()))²
(49)
Let (Blo (X)] - - (I[X))), then the variance of (xX) is bounded:
Var(o((X)) C² Var(X) ,² S Var(X).
(50)
This shows that the Lipschitz constant C. acts scaling factor on the variance of the random variable. If C, is large, the variance of (X) can be significantly larger, and if C is small, it can shrink the variance accordingly. For the majority of nonlinearities used in deep learning, such as ReLU, sigmoid, and hyperbolic tangent, C₂ = 1, and Var(o(X)) S Var(X).
E.2 EFFECT OF GRAPH CONVOLUTION TO THE VARIANCE OF A RANDOM NODE SIGNAL
The next step study the effect of graph convolution (linear message saagee--asing) operations set of node features. In particular, let ( E R-NxFi be the node input the 1 th GNN layer. Then define ( NxF the following:
K-1
x (0) = o (2 2
Σ
S x (1-1)
(51)
k=
After some algebraic manipulations, we have
K-
Fi-1 K
z 1
S
(1-1) (1 HAAA
S x ( AH
(52)
k=
k=0
and each feature of (1) can be cast as the following:
- 3 = ΣΣ x [I dE (I,...,Fi) Fi..
(53)
K=
The above equation implies that each feature Z [ d] is generated by summation over Fi features of the following type:
K-1
Σ
h H (S)
(54)
We assume that the norm of H (S) = Σn h4 S is bounded, i.c.. (S) 3. As result, we will first analyze the variance of z when the input æ has the following covariance matrix:
(xc E [x)) (x -E [x)] C
(55)
The covariance of z is therefore written as follows:
K-1 CS = Σ
K-1
2 - E [x)) (z - E[2))
S* Σ
St
(56)
k
m=O
K K-IK-1
hih S m
(57)
0= m=0
20

---

Published as a conference paper at ICLR 2025
and the variance for each individual variable z[i] is
K-IK
var (z [i])
hgh, "t.
(58)
high Σ
Σ
Sh m]s' n|cov (xc [m]] [n])
(59)
mEA((A) nEA,
hyhs Σ
Σ
Sh mls'(iii (i. n2 cov (xr [m]] x [n])]
(60)
mEAt (k)
nEA?
hyhh Σ
Σ
s m|s' n] max (var (æ [i])
(61)
mEA(()) nEw!
h hggg
Smax deg'uax max (var (a: [i)))
(62)
hydegmaax
Σ
hidegimax max (var (x [i])) s 3 max (var (æ [i]))
(63)
where degmaxx is the maximum degree of St and is equal to degmax = 1, when is the normalized adjacency matrix the random walk matrix. The inequality in (61) follows from the Cauchy-
Schwartz inequality, the inequality in (62) follows from the definition of S and the last inequality in (63) is due the boundedness of the operator H (S).
Overall,
(= [i]
S B max (var (æ [t])
(64)
The final step is to analyze the the variance of a random variable that is sum of dependent random variables, =[i] Σド= z [i].
Then
Fi-1
Σ 2 )
Fi-1 F
F1 F
var (z (=)))) EE
E [1
E [E,
(65)
F2 max (var (zy (i))),
(66)
where the last inequality in (61) follows from the respect the length of the GNN layer. Combining Eq. (50). (64), and (65) we conclude:
inequality, and is quadratic with
var (
C max var X xx(-1))
(67)
If we assume that F for all hidden layers, we have
var X (Z) S (C, 22 max (var [X])
(68)
In our proposed approach max (var XX) 1. If we further assume that C₂ = 1, which is typically the case practice, and that 3 = 1/F, implying that the magnitude of trainable parameters is inversely proportional to the number of hidden dimensions in each layer, then we obtain:
var
(7)
S 1.
(69)
This concludes the proof for Theorem
4.3 which is repeated below:
Theorem E.1 (Sample Complexity) Let P denote the output of the architecture described in Eq. for a graph G with ii.d. initial node features with unit variance. Also let t be I, L--layer GNN
21

---

Published as a conference paper at ICLR 2025
described by Eq. (3 with F hidden dimensions at each layer. Ca 1 and 3 1/F, the number of samples required such that:
M
Σ m=1
(g.q(mi) - - (9.9)) c, with probability at least 6,
(70)
M
satisfies:
M S .2
(71)
Theorem 4.3 bounds the number of samples required for the output of R-PEARL to approximate the expected value E (G, q)] where q E R. is random vector. It also describes the number of samples required for R-PEARL to preserve equivariance. To be more precise, since q is processed using an equivariant GNN (G -), the resulting distribution of (G q) is permutation equivariant. Consequently, the expected value [ q)] is also permutation equivariant.
R-PEARL computes the empirical mean È (G, q)). enabling it to approximate E [ q) with high precision. In essence, R-PEARL achieves equivariance with increasing accuracy the number of samples M grows. For very small sample sizes, R-PEARL is not equivariant; however, in practice, modest number of samples is sufficient to render it effectively equivariant. This is evident in our experiments. In Tables and 2, the "GIN + rand id" model corresponds to R-PEARL with a single sample, which not equivariant. We observe that "GIN + rand id" performs significantly worse morse-more than four times worse in logP prediction for molecular graphs compared to R-PEARL.
F PROOF OF COROLLARY
To prove Corollary 4.4
we assume that the pointwise nonlincarities a are elementwise power for integer values of p 2. Using this assumption, we can apply Theorem
functions, i.c., a K.1 from (Kanatsoulis & Ribeiro) to establish the result. For approximate results, classical smooth nonlinearities such as the hyperbolic tangent, the sigmoid, or the Swish function can be employed and analyzed via their Taylor series expansion around zero:
K-1 (p)
(σ)
Σ
(72)
where (P) represents the p-th derivative of (xx) evaluated at 0. It is straightforward to observe that elementwise power functions appear in this expansion, enabling approximate cycle counting. In any case, the proposed PEs will contain rich information relevant to cycle counts.
B-PEARL achieves the same level of expressivity as R-PEARL. Specifically, there exists parametrization h, defined by Eq. (3), such that B-PEARL can count the number of 3-, 4-, 5-, 6-, and 7-node cycles in which each node participates for any given graph. This equivalence holds because B-PEARL can be thought as special case of R-PEARL, where the input æ has higher-order moments:
E x oxooo...o oz I
The structural expressivity of R-PEARL depends on E l o x ... o æt.. which generate tensor product operations, shown in (Kanatsoulis Ribeiro).
G STABILITY ANALYSIS
Let Ø be perturbed version of graph G, with GSOs Š and S, respectively. We consider two perturbation models, i.c., additive and relative perturbation:
Additive perturbation model: 5 S + E
(73)
Relative perturbation model: 5 SE SE
(74)
In order to measure the distance between Š and S, as well as the GNN outputs when the input graphs perturbed versions of each other define the distance modulo permutation:
22

---

Published as a conference paper at ICLR 2025
Definition G.1 (Linear operator distance modulo permutation) (Gama et al. 2020) Given linear
operators A and A we define the operator distance modulo permutation
A Allp
min II
max
[Az) - A(TTxx)]]
(75)
x=||||=
where II is permutation matrix.
G.1 LIPSCHITZ AND INTEGRAL LIPSCHITZ FILTERS
Next, we need to define the notion of Lipschitz and Integral Lipschitz filters. First, we note that graph filters pointwise operators in the graph frequency domain, i.e.,
K-1
K
K Σ A==0
H
(S)
Σ S
h4 Vv =
A VI.
(76)
k=0
k=
We can therefore define the graph frequency response of the filter as:
K-1
1(A)
h
(77)
R=0
To continue our analysis we define the following filter types.
Definition G.2 (Lipschitz Filter) (Gama et al. 2020) Given a filter h {hk
1-1 its frequency
response (A) is given by equation 77 We say the filter is Lipschitz if there exists a constant C. > 0
such that for all x and X2.
(h(22) - h(x1) & 2/ - -a
(78)
Definition G.3 (Integral Lipschitz Filter)
Gama et al. 2020) Given a filter h = [ its
frequency response (A) is given by equation 77
We say the filter is integral Lipschitz there exists
a constant C O such that for all d and A2.
A22 -A1l
(h(A2) h(x1) S C
(79)
A1 A2 /
G.2 STABILITY BOUNDS FOR RANDOM AND BASIS PEs
We can use any stability bounds for GNNs. To see this, let
x (G. ( [. + (G. |s. 1B:51/1 ST
(80)
Then
M
+ (G.-)
Σ Φ (..) [i
1
Σ $ (g.-) -(
Φ (g.)) l.
M
M
M
m=1
p
(G.-) - - (g.)) l.
<
M
m=1
(81)
Using the previous definitions and Eq. (81 we can now use the analysis in (Gama et al. 2020 to establish the stability of the proposed PEs.
Proposition G.1 (Stability to additive perturbations) Let ② be perturbed version of G such that
Š S + E with E|| < s. Let t be an La-ryer GNN described by Eq. 3 where each layer
consists of Lipschitz filters with constant C. Under assumptions 4.1 and with C, and
3 = 1/F, the following holds:
M
M
Σ
s (G.
1
Σ m=1
Φ
(g.))
[.
S (1+8VN) Le + 0(62)
(82)
M
M
m=1
23

---

Published as a conference paper at ICLR 2025
Proposition G.2 (Stability to relative perturbations) Ler & be a perturbed version of G such that S S SE + ES with p S. Let d be an L-layer GNN described by Eg. 3 where
each layer consists of Integral Lipschitz filters filters with constant C. Under assumptions 4.1 and 4.2 with C. and 3 = F,F, the following holds:
M
M
1 M m=1
Σ
(9.))
1
Σ + (9.)) m=
$2 1+ (2(1+8VN) LE LE+ 0(s²) +
(83)
M
P
H SPECTRAL FILTERS WITH GRAPH FILTERS
The suggested implementation in Huang et al.) is:
N-1
SV, Σ
p ([Vdiag (01 (A)) V[n]²
..... Vdiag (as (A)) V[nl'])
(84)
N-1
Σ n=0
P ([dia (a1 (A)) V eay..., Vdiag (arss (A)) V enl)
(85)
where P represents multiple GIN layers. If we assume that am are analytic element wise functions, then we can take the taylor series expansion and represent am as polynomial. Then SPE can be cast as:
N-1
K- EMa
K
V" en e..)
1) (86)
SPE (V, A) =
Σ
0
Vdiag
V V'ea..... en...., Vdiag
Σ K=O
had A
==0
N-1
K-1
K-1 ALA'VTen eni...,, V
P
V
Σ
M
V En
(87)
R=
k=0
K--1
K-1
Σ
P
VVVVVV
Cn
hi
V en
(88)
k=0
K-1
)
N N-1
K-1
A
en.
Σ
A
e.
Σ
p n=U
Σ A
h
(89)
k=
k=0
k=0
The expression in Eq. (89 coincides with the B-PEARL architecture, which concludes our proof.
I IMPLEMENTATION DETAILS
All results for the SPE, SignNet, and BasisNet models using only 8 eigenvectors were either sourced from their original papers, when available, or obtained by retraining the original models with 8 eigenvectors corresponding to the 8 largest or smallest eigenvalues. All other baseline results were sourced from their original papers. For both the R-PEARL and B-PEARL models, batch normalization is applied within the & layers. Additionally, when K > 2, the output of the first & layer is passed through shallow MLP consisting of I or layers before continuing through the remaining layers.
For the REDDIT datasets, we train R-PEARL with 30-40 samples and K omitting the first layer described in Eq. (3). During execution we use 40-200 samples. R-PEARL uses 8 GIN layers with 64 hidden dimensions, each followed by batch normalization, to generate the PEs. For SignNet, we used 4 GIN layers with 128 hidden dimensions and batch normalization. We experimented with both 4 and 8 layers for SignNet and found that using layers yielded the best results. The PEs are further processed by a base model consisting of 6 additional GIN layers. In R-PEARL, skip connections are applied across the GIN layers, followed by a linear layer at the end. SignNet uses residual connections instead, and also uses MLP encoders for the eigenvectors, well as a Set Transformer (Lee et al. 2019). For both models, we train with a batch size of 128 for REDDIT- BINARY and REDDIT-MMU.T.
24

---

Published as a conference paper at ICLR 2025
Table 5: Estimated runtime per epoch in Minutes for different models on RelBench.
Task
No PE
SignNet-largest
SigaNettsmallest
B-PEARL
R-PEARL
00:03
00:07
01:22
00:13 00:05
00:17
00:01
00:08
00:26
00:01
On the ZINC datasets, R-PEARL, B-PEARL, and SPE use batch size of 128. The base model for each is 4-layer GINE. Similar to the SPE model, we inject the original positional encoding into every layer by passing it through an MLP and adding it to the layer's input. Notably, GIN layers with 40 hidden units for h, whereas SPE uses an 8-layer GIN with 128 hidden units, in addition to 3 MLPs. For R-PEARL we use 50-120 10 samples and K 12, while for B-PEARL use K = 4.
model employs 8
For the DrugOOD datasets, R-PEARL, B-PEARL, SPE, and SignNet all use 4-layer GINE base models. Both R-PEARL and B-PEARL use a 3-layer GIN for o. To process positional encodings, in addition 3-layer GIN, SPE uses 16 3-layer MLPs on the Scaffold and Size splits, while SignNet uses 3-layer MLP across all splits. At each layer of the base model, all models concatenate the original positional encodings with the input features. In the Assay and Size splits we use R- PEARL with K 14 and 80 samples, while for the Scaffold split, we use K 16 and 200 samples.
For the RelBench tasks, both R-PEARL and B-PEARL models use K = 7. The R-PEARL model employs a 5-layer GIN with 40 hidden units and 120 samples. The B-PEARL model uses either 5-layer 7-layer GIN, depending on the task: 5 layers for post-post-related and 7 layers for peer-post-commnn, both with the same number of hidden units. For the SignNet models, we use an 8-layer GIN with batch normalization to generate positional encodings. The positional encodings from the models are incorporated as additional node features for each node. The original node features are generated by Tabular ResNet model, which learns representations over the various node features. These combined features are then fed into the base GNN model. All models follow the same setup as in RelBench for the base model, which employs a 2-layer ID-GNN. Training is conducted with a batch size of 20.
Table presents the runtime of our end-to- and-to-end PE models on the RelBench tasks. Notably, our R-PEARL and B-PEARL achieve shorter runtimes compared to SignNet-smalle smalles across both tasks.
For the Peptides-sttee struct dataset we use an 8-layer GatedGCN base model for B-PEARL, and a 6-layer GINE model for R-PEARL. We use 9-layer GIN to generate the positional encodings for both models, with K- 4 for R- R-PEARL and K for B-PEARL.
For our experiments and model training pipeline we follow the codebases of (Huang et al.) and (im a..). using Python, PyTorch (Paszke et al.) (2019), and the PyTorch Geometric (Fey & Lenssen 2019 libraries. Our code can be found here: https: //g1 htg/tttttu/ thub. com/
ADDITIONAL EXPERIMENTS
J.1 EXPERIMENTS ON GRAPHI ISOMORPIISM
We conduct experiments on the Circular Skip Link (CSL) dataset (Murphy et al. (209)) which the golden standard when it comes to benchmarking GNNs for graph isomorphism (Dwivedi et al. 2023). CSL contains 150 4-regular graphs, where the edges form a cycle and contain skip-links between nodes. Each graph consists of 41 nodes and 164 edges and belongs to one of 10 classes. Message- passing GNNs with WI--related PEs fail to classify these graphs and classification is completely random. This is due to the inability of the WL algorithm to handle regular graphs.
The proposed PEARL architectures, however, have no issue in processing regular graphs and achieve 100% classification accuracy. In particular, let & be two-layer GNN, where each layer is defined by Eq. (3) with K = 5, Fu = Fi = 1, and (.) = Re)u(.). The generated node PE P is processed by summation graph pooling function to produce scalar embedding for each graph. Then, both B-PEARL and R-PEARL can perfectly classify the CSL graphs with 100% classification accuracy, for any randomly generated trainable weights. This means that B-PEARL and R-P R-PEARI can
25

---

Published as a conference paper at ICLR 2025
Table 6: B-PEARL PE for every class of the CSL graphs. B-PEARL can perfectly classify the CSL graphs with 100% classification accuracy.
CLASS
3
7
8
27351.6 8800.2
25779.9
20458.4
17197.2
15861.3
24055.6
4106.8
17667.0
perfectly classify the CSL graphs without any training. For example let & consist of two identical layers with parameters (hn, ha, h,2 h3, h4) (0, 1, 2:3 -1). The output 1 of B-PEARL. is presented in 6 The output remains the same for all graphs within the same class, and differs distinctly for graphs belonging different classes. Consequently, perfect classification accuracy can be achieved by feeding the B-PEARL encoding into simple linear classifier or even linear assignment algorithm.
J.2 EXPERIMENTS ON PEPTIDES-STRUCT DATASET
Table 7: Test MAE on the Peptides-struct dataset. B-PEARL achieves the second-best performance, behind Graph VIT, within 500k parameter budget. Graph ViT utilizes additional random walk information, while B-PEARL should learn this information via training.
R-PEARL B-PEARL
SAN+LapPE SAN+RWSE
GNN-AK
Graph
0.24720.001 0.008 0.25220.001
0.268
0. 0.25540.001
0.27420.00
0.245 0.250
We conduct experiments on the Peptides-struct dataset from the Long Range Graph Benchmark dataset (Dwivedi et al., (2022). This dataset comprises over 15,000 graphs containing more than 2 million nodes in total, with each graph ranging from 8 to 444 nodes. It is designed to evaluate model's ability to capture long-range interactions. The metric used is Mean Absolute Error (MAE), and the task involves regressing on the 3D structure of peptides to predict properties such as their length. We compare the performance of R-PEARL and B-PEARL against state-of-the-ard models within a 500k parameter budget: GPS (Rampášek et al., 2022), SAN (Kreuzer et al., 2021b). SUN (Frasca et al. 2022). GNN-AK (Zhao et al. 2022). and VIT HHe al. 2023). The results can be found in Table
We observe that B-PEARL achieves the second-best performance, trailing Graph VIT by only 0.002. However, it is important to note that Graph ViT leverages additional random walk information, whereas B-PEARL must learn this information during training. This distinction can be particularly significant, especially given that both models operate within the same constrained 500k parameter budget.
K ABLATION STUDIES
K.1 ABLATION ON DIFFERENT BACKBONE MODELS
Table 8: Test MAE of B-PEARL and R-PEARL with different backbones within a 500k parameter budget on the ZINC dataset.
Model
GINE
GatedGCN
PNA
B-PEARL
0.0679 1 O 0.0026
0.0765 1 0.0018
0.0740 1 0.0010
R-PEARL 0.0721 1 0.0045
0.0810 + 0.0039
0.0946 + 0.0032
We conduct additional base model ablations for our model, using PNA and GatedGCN addition to GINE on the ZINC dataset (Corso et al.] 2020 Li et al.) 2016). Our results are shown in Table S] We observe that PEARL demonstrates strong performance across various backbones. PEAALL consistently outperforms equivalent SignNet models with the same backbones, while R- outperforms SignNet with the GatedGCN backbone (Lim et al.). All models in the table kept within the 500k parameter budget.
26

---

Published as a conference paper at ICLR 2025
Table logP Prediction in ZINC with different R-PEARL Y values.
PE Method
#PEs
K
Test MAE
Training MAE
General. Gap
SignNet-8S
N/A
0.1034 0.0056
0.0418 + 0.0101
0.0602 0.0112
SignNet
Full
N/A
0.0853
0.0026
0.0349 0.0078
0.0502 0.0103
BasisNet-8S
8
N/A
0.1554
0.0048
0.0513 1 0.0053
0.1042 0.0063
BasisNet
Full
N/A
0.1555
0.0124
0.0684 + 0.0202
0.0989 + 0.0258
SPE-8S
8
N/A
0.0736
0.0007
0.0324 + 0.0058
0.0413 + 0.0057
SPE
Full
N/A
0.0693
0.0040
0.0334 1: 0.0034
0.0359 0.0087
R- PEARL
N/A
0.0699 + 0.002
0.0366 + 0.006
0.0333 = 0.007
(-PEARL(ours)
N/A
2
0.0831 = 0.005
0.0725 + 0.0125
0.0106 = 0.008
R-PEARL(omne
N/A
0.0699 = 0.002
0.0366 0.006
0.0333 = 0.007
B-PEAR ((our)
N/A
0.0644 0.001
0.0290 0.003
0.0353 0.002
B-PEARL(curs)
N/A
0.0680
0,0023
0.0381
0.004
0.0299
0.0033
B-PEARL(Ours)
N/A
12
0.0676 0.0016
0.0403 = 0.0104
0.0273 + 0.0090
K.2 ABLATION ON K
We also report our results on the ZINC dataset (Irwin et al., 2012) with alternate values of K for R-PEARL and B-PEARL. In the case K = we omit the first layer described Eq. (3). using solely 8-layer GIN for Φ. These results are shown in Tabld9 We observe that even with K = our model outperforms SignNet. Furthermore, even with low value of 4, B-PEARL outperforms SPE.
K.3 ABLATION ON NUMBER OF SAMPLES M
We conduct ablation studies the number of samples used by R-PEARL across the REDDIT datasets to examine the impact of sample size on model performance. These results are illustrated in Fig. 2 For each dataset, we evaluate the original model with 200 samples on a single test fold, varying the number of samples from to 200. The test accuracy is then plotted, and Monte Carlo simulation-baser smoothing is applied generate the plots. Notably, we observe that model performance begins to converge with as few as 10 samples-an an order of magnitude lower than the graph size.
6.00
(a) Sample Ablation on REDDIT-BINARY
(b) Sample Ablation on
Figure 2: Ablation studies on the sample size for R-PEARL; it converges with only a few samples.
K.4 ABLATION ON THE NUMBER OF GNN LAYERS IN PEARL
Table 10: Ablation on the number of GIN layers in B-PEARL. for the ZINC Dataset over 4 seeds.
GIN Layers
Test MAE
0.0701 0.005
0.067 0.003
0.069 0.001 0.0644 0.001
The results in Table [h]shww that B-PEARL achieves strong performance the ZINC dataset with less layers in the GNN producing the positional encodings. With only layers, B-PEARL outperforms SPE.
27

---

Published as a conference paper at ICLR 2025
K.5 ABLATION ON DIFFERENT PARAMETER SIZE
Table II presents our ablation study on the number of parameters for the ZINC dataset. Notably, all models outperform SignNet even within the 500k parameter budget. Furthermore, B-PEARL achieves superior performance compared to SPE on full eigenvectors, even with fewer parameters.
Table 1I: logP Prediction in ZINC over number of parameters.
PE Method
PParameters
Test MAE
Training MAE
General. Gap
SignNet
487k
0.0853 0.0026
0.0349
0.0078
0.0502
0.0103
SPE
650k
0.0693 1 0.0040
0.0334
0.0054
0.0359 0.0087
R-PEARL
644k
0.0699 + 0.002
0.0366
0.006
0.0333 + 0.007
B-PEARL.
644k
0.0644 + 0.001
0.0290 + 0.003
0.0353 + 0.002
R-PEARL
487k
0.0696 1 0.004
0.0319 0.007
0.0377 1 0.008
B-PEARL
487k
0.0655 + 0.004
0.0252 0.005
0.0403 + 0.004
28


Reviews:
[{"review_id": "ZOxaw6LG7D", "reviewer": "Reviewer_J67b", "summary": "The authors propose learning positional encodings by using spectral graph filters in the initial layers. They argue that this approach corresponds to learning non-linear functions of the eigenvectors. The spectral GNN is applied to the input graph without using node features; instead, random features are added to the nodes. Although this breaks permutation equivariance, the authors argue that using a sufficient number of samples and specific aggregation functions preserves permutation equivariance. The authors argue that this method is expressive, scalable and stable.", "questions": "- Equation (3) does not accurately represent all possible MPNNs, even when restricting $g$ to be an MLP and $f$ to result from multiplication with a GSO. Specifically, using an MLP from $\\mathbb{R}^k$ to $\\mathbb{R}^k$ does not trivially extend to a graph signal of dimension $\\mathbb{R}^{n \\times h}$. It seems that the authors are actually performing matrix multiplications from the right with learnable matrices, and using more than one. Similarly, in Proposition 3.1, the representation in Equation (12) is assumed before the proof begins, which is actually what the authors aim to prove.\n- In Proposition 4.3, what is the variable $m$ summing over? The entire proposition lacks clarity, and it appears there is no novelty compared to the existing results from Gama et al.\n- The authors claim that Equation (6) is permutation equivariant, which does not seem to be correct. It is only equivariant in expectation, similar to the random positional encodings introduced by Sato et al. (2020).\n- What are the contributions to the stability and expressivity analysis? It seems that older results are merely being reused.\n- Did the authors follow the standard experimental setup? For example, in the ZINC dataset, it is customary to use a parameter budget of 500K parameters.\n- The authors argued that their method is more scalable. Could you a) test on larger graphs, and b) measure the improved speed?\n\n## Additional Comment:\n\nThe primary novelty appears to be the use of random features as input for learning positional encodings, instead of typically using eigenvectors. It appears that PEARL is a specific variant of SPE where the equivariant sequence-to-sequence function is replaced by a point-wise function applied to eigenvalues. This point-wise function is simply a learnable polynomial, offering the clear advantage of not requiring eigen decomposition, thus making it faster and more memory-efficient. However, it is unclear whether this approach improves or decreases expressivity or leads to better stability or generalization bounds. Notably, the out-of-distribution (OOD) generalization in the experiments appears to be better for the SPE positional encodings. However, it is not clear why since SPEs are also stable. Finally, I want to direct the authors to \"Spatio-Spectral Graph Neural Networks\" by Geisler et al., which also uses spectral and spatial layers in GNNs.\n\nRecommendation:\nI recommend rejecting the paper in its current form and suggest that the authors improve the clarity of the manuscript (in terms of novely and also writing) and better integrate it into the existing literature.", "limitations": "", "rating": 3, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 1, "strengths": "- Most other methods based on eigenvectors require computing the eigenbasis, leading to problems on large graphs. In contrast, the authors argue for a worst-case $N^2$ forward complexity without high preprocessing-complexity.\n- The experimental results appear promising.", "weaknesses": "- The paper is not well-integrated into the existing literature. It is unclear what advantages it offers compared to other methods that count cycles. Although related work is mentioned, the authors do not clearly differentiate their approach or highlight their novel contributions.\n- The theoretical results often seem incorrect or lack necessary details. Additionally, many of the results appear to be summaries of theoretical findings from related works. Specific examples are provided in the questions section.\n- While the method is more expressive than the 1-WL test, this is not surprising. You can basically do anything to increase beyond 1-WL. For instance, simply adding the number of connected components as a feature would make the model more expressive than 1-WL. It would be beneficial to include quantitative results, such as whether the method is weaker than the 2-FWL test, and to compare it with other methods that have proven counting properties for example.\n- A more significant issue is that, although the method is more expressive, it also breaks permutation symmetry. It is well known that adding unique node identifiers can make a model universal but breaks permutation symmetry. \n- In Section 5, it is unclear what is meant by having a basis as an input. Additionally, Remark 5.1 is incorrect. In Huang et al., the $\\alpha_i$ are always analytic and are sequence-to-sequence mappings, whereas in this work, they are always real-valued mappings that operate on each eigenvector independently. This makes the approach less expressive, at least in the frequency domain.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "extra_scores": {}}, {"review_id": "StrylJKKqi", "reviewer": "Reviewer_BGAo", "summary": "This work aims to propose a new framework for graph positional encoding that is expressive, scalable, stable and generalizable. The proposed framework generates positional encoding as aggregated outputs of GNNs with random or basis inputs, which is then fed into downstream GNNs for performance evaluation. The proposed framework is accompanied with theoretical arguments and empirical verification on graph regression and classification tasks.", "questions": "Please see the above major concerns.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. Good motivations: the topic of graph positional encoding is a significant direction, which requires sufficiency, efficiency and easiness for generalization.\n2. The proposed method is easy for plug-in: it proposes positional encodings as aggregation of GNNs' outputs with random/basis inputs, which are quite simple with standard implementation.\n3. The empirical performance of the proposed method is comparable with SPE methods in Table 2, but it is much more efficient than SPE in Table 1 for larger graphs.\n4. Different choices of input with random or basis are good with a consideration of different scales of problems, with the sample size of random inputs examined in Figure 2.", "weaknesses": "Major:\n1. A key assumption is missing in proposition 3.1: GSO $S$ is required to be symmetric if we want to use the decomposition in line 105. So  the random walk matrix in Eq(2) does not satisfy this condition.\n2. in line 463, it might be a little sudden to claim ''SPE can be efficiently implemented by B-PEARL with lower computational and memory complexity'': the argument seems coming from the comparison of numbers in Table 2. Although the numbers of SPE and the proposed methods are close, it would be better to conduct more careful analysis to provide such a ''subset'' or ''equivalence'' relationship between the methods, or refer to remark 5.1 for theoretical insights.\n3. in line 60 of introduction, the paper argues '' stability is particularly crucial for out-of-distribution generalization'', which is one of the main motivations for this work. However, such a benefit of size generalization is not provided with enough evidence in this work. Actually in Table 3, the OOD-size performance is not improved by stable methods like SPE and the proposed R-PEARL.\n4. in line 397, a 9-layer MPNN is used for experiments, which is relatively deep in the practice of GNNs. Could you please reveal how depth will impact the empirical results? Meanwhile, such a deep method with random inputs is quite similar to power iterations for eigenvalues, so some discussion between these might be helpful.\n\nMinor: \n1. in line 133-134, the definition of $F_{l-1}$ is not clearly stated, and it should be $F_l$ for $X^{(l)}$.\n2. in line 293, it seems to be ''a consequence of Prop 4.1'' instead of 4.2", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "extra_scores": {}}, {"review_id": "X1MqL10QaO", "reviewer": "Reviewer_eV2C", "summary": "Beforehand, I want to say that I am not familiar with this topic.\n\nThe paper introduces PEARL, a novel framework for learnable positional encodings (PEs) in graph representation learning. It addresses the limitations of eigenvector-based methods by leveraging message-passing Graph Neural Networks (GNNs) to compute efficient and expressive PEs. The authors propose initializing node attributes with random or basis vectors to ensure both expressiveness and permutation equivariance. The framework is validated through comprehensive theoretical analysis and empirical evaluation, showing significant improvements in scalability and performance compared to existing methods.", "questions": "The paper introduces PEARL as a scalable and efficient alternative to eigenvector-based positional encodings. While the theoretical advantages are well articulated, can the authors provide more detailed insights or case studies on how PEARL performs in real-world applications or large-scale industrial settings? Specifically, what types of graphs or domains would benefit the most from the proposed method, and are there any observed limitations in practical deployments?", "limitations": "", "rating": 6, "confidence": 2, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "1. Innovative Approach: The use of message-passing GNNs as nonlinear mappings of eigenvectors is a novel contribution, enabling efficient computation of PEs.\n2. Comprehensive Analysis: The paper rigorously proves the stability, expressiveness, and computational efficiency of PEARL.\n3. Empirical Validation: Experimental results demonstrate that PEARL outperforms traditional methods on various graph classification and regression tasks while maintaining lower computational complexity.\n4. Scalability: The framework is designed to handle large graphs efficiently, addressing a critical limitation of eigenvector-based methods.\n5. Theoretical Contributions: The analysis of sample complexity and stability provides a solid foundation for the proposed approach.", "weaknesses": "1. Limited Discussion on Practical Implications: While the theoretical and empirical results are robust, the paper could benefit from a deeper discussion on the practical applications of PEARL in real-world scenarios.\n2. Complexity of Understanding: The mathematical depth and complexity might pose a barrier to readers unfamiliar with the intricacies of GNNs and spectral graph theory.\n3. Comparative Baselines: Although the paper includes several baselines, additional comparisons with more recent or diverse methods could strengthen the empirical validation.\n4. Ablation Studies: While ablation studies are presented, further exploration of the impact of different initialization strategies and pooling functions on performance could provide more insights.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "extra_scores": {}}, {"review_id": "W3AyM6vDSM", "reviewer": "Reviewer_KVQZ", "summary": "This work proposes PEARL, using the output of Message Passing Neural Network (MPNN) with noise/basis node feature as input for PE. PEARL's stability, sample complexity, and expressivity are further analysis. Experiments illustrates that PEARL achieves good performance in graph tasks.", "questions": "Please refer to Weaknesses.", "limitations": "", "rating": 3, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1. Good performance on ZINC dataset.\n2. Detailed analysis of R-PEARL.", "weaknesses": "1. The abstract states that this work investigates positional encodings (PEs) for graphs based on four key criteria: stability, expressive power, scalability, and genericness. However, the focus is primarily on eigenvector-based PE, and the analysis is limited to the authors' proposed method, R-PEARL, regarding these criteria. A more comprehensive theoretical analysis and comparison with other PEs are needed.\n2. The rationale behind using Message Passing Neural Networks (MPNNs) to generate PEs is not clearly explained. Proposition 3.1 appears to be trivial, as graphs (represented by adjacency matrices and node features) can be bijectively mapped to eigenvectors, eigenvalues, and node features. Consequently, all graph functions, including PEs, can be seen as functions of eigenvectors when parameters include both eigenvalues and eigenvectors. Therefore, the justification for choosing MPNNs as eigenvalue function over other graph models is not evident.\n3. While the expectation of R-PEARL is equivariant, the actual R-PEARL method is not, due to the involvement of noise.\n4. Theorem 4.3 and the claim that \"our proposed PE framework is well-suited for large-scale graphs\" are questionable. The proof of Theorem 4.3, specifically Formula (45), includes the maximum degree of the graph, which is latter included in $\\beta$. Considering $\\beta$ as a constant is problematic because large social networks often contain nodes with high degrees, which would require more samples for accurate representation.\n5. Most theoretical results (Theorem 4.3, Proposition 4.1, 4.2, 4.3) are direct corollories of previous conclusions.\n6. The experimental section is limited to four datasets. To strengthen the validity of the results, additional datasets should be included as in [1].\n7. The PE is used in conjunction with a GNN backbone, but the backbone for PEARL appears to be fixed across all experiments. To demonstrate the broad applicability and ensure a fair comparison among different PEs, experiments on PEs with different GNN backbones should be added, as recommended in [2].\n\n\n[1] Xiaoxin He, Bryan Hooi, Thomas Laurent, Adam Perold, Yann LeCun, Xavier Bresson: A Generalization of ViT/MLP-Mixer to Graphs. ICML 2023\n[2] Ladislav Rampásek, Michael Galkin, Vijay Prakash Dwivedi, Anh Tuan Luu, Guy Wolf, Dominique Beaini: Recipe for a General, Powerful, Scalable Graph Transformer. NeurIPS 2022", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "extra_scores": {}}, {"review_id": "qQ4QjbElwt", "reviewer": "Reviewer_8uLD", "summary": "The paper deals with learning effective positional encodings for graph structures to be used in conjunction with graph neural networks. Previously, eigenvectors and random features  have been used for such posiitonal encodings. In this paper, the authors first observe that the message passing GNNs are akin to non-linear functions of eighenvectors and therefore can be used to learn positional encodings which can function similarly to eigenvector-based positional encodings. Following this observation, they propose PEARL, a GNN based approach which takes in random feature inputs on the graph (without accompanying node-features) and learns to output encodings which can be interpreted as positional encodings. To preserve permutation invariance upto the expectation, they use multiple IID samples and aggregate with equivarient sample statistics. The authors show that such a approach preserves  stability, improves expressive power, scalability, and genericness. Experiments are presented to validate the approach.", "questions": "Please see weaknesses.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The paper addresses an important problem of learning positional encodings on graphs\n1. The approach of learning PEs as outputs of GNN with random feature inputs on the graph is well-motivated with the observation discussed that GNNs are non-linear functions of eigenvectors of graph shift operators.\n1. The paper is well-written and presentation is good.", "weaknesses": "1. Essentially, the outputs of GNNs on random input features are taken as positional encodings. However, there are no loss functions to bias learning towards such functions. While it is clear the random inputs along with GNN message passing, can encode the relative positional information and the supporting evidence that GNNs compute non-linear maps of eigenvectors of adjacency/laplacians, further regularizing loss functions may be able to make the learning encodings better. One example is enforcing the encodings of each node to be orthogonal to other encodings.\n1. It is not clear to me why eigenvectors need to be used in place of random features for smaller sized graphs. Empirical results to show the difference between eigenvector inputs and random inputs for smaller sized graphs would be beneficial.\n1. Important works are missing in related work and comparison experiments. In experiments, Random GNN [1] and PF-GNN [2] are not compared, which are highly related to using randomization to improve expressive power and in a way, compute positional encodings. \n1. The paper claims that the proposed approach is more expressive. Then empirical results showing it is needed. For example, identifying graphs  not identifiable by GNNs would be useful. A comparison with random GNN[1] and PFGNN[2] would be beneficial in this respect.\n\n\n### References:\n\n\\[1\\] $~$  Sato, Ryoma, Makoto Yamada, and Hisashi Kashima. \"Random features strengthen graph neural networks.\" Proceedings of the 2021 SIAM international conference on data mining (SDM). Society for Industrial and Applied Mathematics, 2021.\n\n\\[2\\] $~$ Dupty, Mohammed Haroon, Yanfei Dong, and Wee Sun Lee. \"PF-GNN: Differentiable particle filtering based approximation of universal graph representations.\" arXiv preprint arXiv:2401.17752 (2024).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)