Towards Graph Foundation Models: A Study on the Generalization of Positional and Structural Encodings
Authors: Billy Joe Franks
Moshe Eliasof
Semih Cantürk
Guy Wolf
Carola-Bibiane Schönlieb
Sophie Fellenz
Marius Kloft
Venue: Accepted by TMLR ()

Abstract: Recent advances in integrating positional and structural encodings (PSEs) into graph neural networks (GNNs) have significantly enhanced their performance across various graph learning tasks. However, the general applicability of these encodings and their potential to serve as foundational representations for graphs remain uncertain. This paper investigates the fine-tuning efficiency, scalability with sample size, and generalization capability of learnable PSEs across diverse graph datasets. Specifically, we evaluate their potential as universal pre-trained models that can be easily adapted to new tasks with minimal fine-tuning and limited data. Furthermore, we assess the expressivity of the learned representations, particularly, when used to augment downstream GNNs. We demonstrate through extensive benchmarking and empirical analysis that PSEs generally enhance downstream models. However, some datasets may require specific PSE-augmentations to achieve optimal performance. Nevertheless, our findings highlight their significant potential to become integral components of future graph foundation models. We provide new insights into the strengths and limitations of PSEs, contributing to the broader discourse on foundation models in graph learning.

Published in Transactions on Machine Learning Research (02/2025)
Towards Graph Foundation Models: A Study on the Gener- alization of Positional and Structural Encodings
Billy Joe Franks*
S.lly-frankssrpe
University of Laasersllater--Landda
Moshe Eliasof University of Cambridge
Semih Cantürk
Université de Montréal Mila Quebec Al Institue
Guy Wolf
Université de Montréal Mila Quebec Al Institue
Carola-Bibiane Schönlieb
University of Cambridge
Sophic Fellenz University of Koiserslauterm-Landaa
Marius Kloft University of Koisersloutern-Landaa
Reviewed OpenReview: https: openreview. net/ forum? id= @SoDRZZsqq
Abstract
Recent advances in integrating ponalional and structural encodings (PSFs) into graph neural networks (GNNs) have significantly enhanced their performance across various graph learn- ing tasks. However, the general applicability of these encodings and their potential to serve as foundational represenlations for graphs remain uncertain. This paper investigales the fine-tuning efficiency, scalability with sample size, and generalization capability of learnable PSEs across diverse graph datasets. Specifically, we evaluate their potential as universal pre- trained models that can be easily adapted to tasks with minimal fine-tuning and limited data. Furthermore, we assess the expressivity of the learned representations, particularly, when used to augment downstream GNNs. We demonstrate through extensive benchmark- ing and empirical analysis that PSEs generally enhance downstream models. However, some datasets may require specific PSE-angmentations to achieve optimal performance. Never- tholess, our findings highlight their significant potential to become integral components of future graph foundation models. We provide new insights into the strengths and limitations of PSEs, contributing to the broader discourse foundation models in graph learning.
1 Introduction
In recent years, graph neural networks (GNNs) and machine learning on graphs have gained significant attention due to their versatility in processing complex data across various domains, including biology,
"Equal contribution.

---

Published in Transactions on Machine Learning Research (02/2025)
social networks, chemistry, and recommendation systems. Comprehensive surveys on these advancements are available in Bronstein et al. (2021) and Waikhom and Paigiri 2023 GNNs are fundamentally designed to extend traditional deep learning techniques to grapb-structured data by aggregating information from local noighborhoods, thereby enabling the extraction of structural and relational features intrinsic to graphs. Despite considerable progress, these methods continue to face several challenges, including issues related to expressivity, such as the ability to distinguish between non-isomorphic graphs (Morris et al., 2019) and al., 2022), the generalization of models across different graph datasets and tasks :Ju et al., 2023), as well as the connection between generalization and expressivity that has been studied recently (Li et al. 2024).
substructure counting (Bevilacqua
In terms of expressivity, i.e,, the ability of GNNs to approximate functions (Huang and Villar 2021 message- passing neural networks (MPNNs) are known to have limitations that can hinder their performance in practi- cal applications (Morris et al. 2019 Xu et al. 2019 Morris et al. 2023 Zhang et al., 2021p. To address these limitations, various strategies have been proposod, with two prominent approaches focusing on augmenting the input node features of a graph with positional and structural encodings (PE and SE, respectively). One such approach involves using random node features (RNF) (Abboud et al. 2021 Sato et al. 2021 which have been shown to enhance the expressivity of MPNNs by increasing their ability to distinguish between nodes. However, despite the theoretical benefits, RNF has not consistently improved performance on real- world datasets (Bevilacqua et al. 2022: Bechler-Speicher et al. 2025). To address this inconsistency, recent studies have demonstrated that learned PEs (Eliasof et al. 2023 and learned graph normalization techniques (Eliasof et al. 2024) can leverage RNF to improve both expressivity and downstream task performance. An- other approach to overcoming the expressivity limitations involves incorporating spectral PRs, which are often derived from partial cigendecomposition of the graph-Laplacian matrix (Dwivedi and Bresson 2021 Kreuzer et al.] 2021 Wang et al.) 2022a; Lim et al.] 2023 Rampášek el al. 2022). Additionally, structural encodings based on random walks (Dwivedi et al. 2022a] have also proven to be beneficial. More recently, the graph positional and structural encoder (GPSE) (Cantürk et al. 2024 introduced a unified framework for learning from both positional and structural encodings while utilizing RNF. Overall, these methods have shown improvements, particularly on specific graph benchmarks where models are trained from scratch for each task. Notably, GPSE also demonstrated some degree of generalization to new tasks.
Simultancously with the advancements in GNNs, foundation models (FM) have emerged and revolutionized the fields of natural language processing (NIP)) and computer vision (CV). These developments present an exciting opportunity to bring similar transformative advances to machine learning on graphs. In NLP, models like BERT (Devlin et al. 2019) and GPT (Brown et al. 2020 have demonstrated how pre-training on large datasets can produce models that generalize effectively to a variety of rownstreem lasks with minimal to no fino-tuning. Inspired by these successes, recent works (Liu et al. 2023 Galkin et al., 2024 Huang ee al. 2023a Mao et al., 2024 Shi et al., 2024 Xia et al., 2024 Liu al. 2024) have begun exploring the creation of graph foundation models (GFM), which could offer similar benefits for graph- tasks. Such models would not only simplify the training process across multiple tasks but also significantly reduce the computational resources, energy consumption, and data requirements typically associated with task-speeific training. This aligns with the broader objective of developing more envirommentally sustainable machine learning practices.
However, building full-scale foundation models for graphs presents unique challenges. Unlike textual or visual data, which often exhibit relatively uniform structures, such as 2D grids with fixed resolutions in images, graphs can vary widely in their topology, size, and complexity. Additionally, the input feature space for graphs is highly heterogeneous; while pre-trained models for images typically operate on common input space (e.g., RGB values), different graph datasets often have vastly different input features, ranging from molecular atom types to paper attributes in citation networks. This variability across datasets complicates the design of a universal, pre-trained graph model. Given these challenges, while diverse input features remain an open issue, a promising direction is to focus on learning foundational graph representations that capture key structural properties inherent in graph data. In particular, this paper emphasizes the role of positional and structural encodings (PSEs), which enhance node identifiability within graph and offer more practical approach to developing versatile graph encoders that can generalize across various tasks and datasets. This work is inspired by the growing body of research on pre-trained encodings for graphs,
2

---

Published in Transactions on Machine Learning Research (02/2025)
particularly the recent work on the graph positional and structural encoder (GPSE), which introduces graph encoder specifically designed to capture diverse PSEs.
Our Contributions. In this paper, we both practically and theoretically assess whether PSEs can function as foundation models or, alternatively, as a building block for future foundation models. We especially focus on the recent GPSE model which we consider the state of the art when it comes to PSEs. We note that, our main contribution is the study of the role of GPSE as a building block within future GFMs, rather than proposing new methodology. We believe that these contributions are useful and important for the graph-learning community. To be precise we:
Discuss the expressivity of GPSE, as standalone model, as well as general PSEs contribution to expressivity when they are used to augment downstream GNN models (Section
Show that GPSE accelerates convergence to better performance. Specifically, it achieves strong results more quickly due to its pre-training phase (Section 5.1
Determine whether sample size affects model performance when using GPSE and other PSEs, pro- viding insights into their effectiveness in data-scarce settings (Section 5.2
Analyze and compare various PSE's performance across different datasets to assess their generaliza- lion capability. The evaluation indicates that GPSE seems perform generally best, while some failure cases still remain (Section 5.3
Our findings indicate that while GPSE and other PSEs do not yet function as standalone GFMs due to their performance being somewhat dependent on the dataset in question, they show potential as valuable components in future GFMs due their increased robustness in data-scarce settings and their improved generalization. This potential primarily attributed to GPSE's strong generalization capabilities, which we identify as critical factor for enhancing downstream performance (Section 5.3). These results underscore the importance of studying generalization in graph learning, key area for advancing the development and understanding of GFMs, as also highlighted by Morris et al. (0024)
2 Related Work
This work studies the connection between GFMs, PSEs, and expressivity, in GNNs. We now discuss related work on these lopics.
Graph foundation models. Inspired by the success of FMs in NLP (Brwn et al., 2020 and CV (Dsso- vitskiy et al. 2021), there has been incrcasing interest in developing similar models for graph-basce tasks. These GFMs aim to generalize across various graph-related lasks by leveraging large-scale pre-training and adaptable architectures. Liu et al. (2023) provide a comprehensive analysis of the current state of GFMs. Their study highlights significant challenges in the development of general GFMs, noting that the diversity of graph structures and tasks makes it difficult to create models with broad applicability. Shi et al. (2024) emphasize the potential impact of GFMs on a wide range of applications, from social network analysis to molecular modeling. Also, Mao et al. (2024) discuss the potential directions for designing effective GFMs, and propose a taxonomy of task-specific GFMs, outlining the key design principles required to achieve gen- eralization across various graph tasks. Xia et al. (2024); ; Liu et al. (2024), and HHang et al. (2023a) propose GFMs by use of graph-tokenization, text-attributod graphs, and in-context lcarning for graphs. These mod- els have difficulties with balancing task specificity with generalization capabilities or regression tasks. A promising example of domain-specific GFM is presented in Galkin et al. (2024), a GFM tailored for knowl- edge graph tasks was shown to be successful, excelling in tasks such as knowledge graph completion and link prediction, showcasing how specialized GFMs can achieve state-of-the-art results in specific domains. However, there is still a need to develop GFMs for other domains like biology and chemistry, where PSEs are commonly applied, as recently discussed in Frasca et al. 2024).
On a different note, recently, there has been a series of works that utilize large language models (LLMs) as FMs for graph learning tasks, such as in Fatemi et al. (2024): Perozzi et al. (2024) and others. We note
3

---

Published in Transactions on Machine Learning Research (02/2025)
that, this direction is very promising in terms of the large availability of pre-trained models, well as the abundance of textual data used in LLMs, compared with the scarcity of graph data. However, in this paper; we focus on employing GNNs and concepts within, to study whether and how they can be oriented towards GFMs, which can be later combined with LLM approaches.
Positional and structural encodings. PSEs are features that. provide information on the graph 's structure and node positions. The seminal work in Vaswani al. (2017) introduced the concept of positional encodings in the transformer architecture, demonstrating their effectiveness in capturing the order of sequences. In graph learning, the inclusion of PSEs was shown to be significant for enhancing the performance of models in various tasks (Srinivasan and Ribciro 2020), as we now discuss. Methods utilizing graph Laplacian eigenvectors as PEs (LapPE) have been explored by Kreuzer et al. (2021) and [Rampáčkk et al. (2022). Kreuzer et al. (2021) also investigated the use of electrostatic potential encodings, providing a novel approach to structural representation. Ying et al. (2021) proposed using shortest paths as encodings, which have shown promise in capturing graph structures. Shiv and Quirk (2019) introduced tree-based encodings, offering a unique perspective on hierarchical data representation. Random walk-based encodings (RWSE) have been explored by Rampášek et al. (2022) |; Dwivedi and Bresson (2021) | and Dwivedi et al. (2022b). highlighting their versatility in various applications. The use of heat kernels for SEs has been discussed by Kreuzer ct al.) Saograph-based encodings, which have been effective in capturing local graph structures, were the focus of Zhao et al. (2022): ; Bouritsas et al. (0022] Chen et al. (2022) and Yan et al.
{2021] and Mialon et al. (2021).
(0023). Additionally, Ying et al. (2021) considered node degree as a simple yet powerful SEs. Furthermore,
a different set of works has shown that RNF (Abboud al.) 2021 Sato et al. 2021 Franks et al.) (2023)
are theoretically strong PFs, and they were further utilized in Fliasof et al. (2023) for learnable PFs via
their propagation. Rocently, it was shown in Cantürk et al. (024)) that RNF can be combined with the aforementioned PSEs to learn general encoding, called graph positional and structural encoding (GPSE).
While PSEs have shown great promise in improving performance on varions tasks, their supposed effects on GFMs has been under-explored, with preliminary experimental results shown in Frasca et al. (2024). In this paper, we offer a detailed study on the generalization ability of learned PSEs, accompanied by a theoretical discussion of their expressiveness.
The expressivity of GNNs has been widely studied in recent years Xu et al. 2019 Maron et al. 2019a). highlighting the theoretical limits of GNNs. To improve the expressivity of GNNs, several approaches were proposed and studied, from substructure encodings (Bourit- sas et al. 2022], subgraph GNNs (Bevilacqua et al.) 2022; Zhao et al. 2022 Bevilacqua et al. 2024), to homomorphism counting (Zhang et al.] 2024), to the augmentation of input node features with PSEs such as RNF (Dasoulas et al. 2020: Murphy et al. 2019 Sato et al. 2021 Abboud et al.] 2021 Franks et al., 2023). In this work, following GPSE that utilizes RNF as part of its architecture, we thcoretically discuss the expressive power of GPSE, and study whether RNF are required in practice for downstream tasks when utilizing framework such as GPSE. A further discussion of expressivity not considered here can be found in Appendix A
Exprcssivity of GNNs
2019 Morris et al.
3 Notations and Background
Throughout this paper, we consider (undirected) graphs. An undirected graph G is defined by the pair (V))), E(G) with finite sets of nodes V(G), and edges E(G) S {uu "Hu, e V(G),. W.L.o.g. we assume that V(G) = (l....,m.. Within machine learning on graphs nodes typically carry feature vectors which lead to undirected labeled graphs G (V(G), E(G), f), where é: V(G) + Rd assigns each node a feature vector.
Color refinement (CR) CR is a well-studied heuristic for the graph isomorphism problem, originally proposed by Leman and Weisfeiler (1968). Intuitively, the algorithm determines if two graphs are non- isomorphic by iteratively coloring or labeling vertices. Formally, let G = (G), E(G), E) be a labeled graph. In each iteration, t > O, CR computes a vertex coloring CP:: : V(G) + N, depending on the coloring of the neighbors. That is, in ileration & > 0, we set.
CCAABEL(CCLLA (v) = RELABEL ((CLI()), (CC-L()),CCL N(o))).
4

---

Published in Transactions on Machine Learning Research (02/2025)
for all vertices v E V(G), where RELABEL injectively maps the above pair to unique natural number, which has not been used in previous iterations. In iteration O, the coloring Co = é is used, which can be converted to a natural number in a multitude of ways. To test whether two graphs G and H are non-isomorphic, we run the above algorithm in "parallel" on both graphs. If the two graphs have a different number of vertices colored E at some iteration, CR distinguishes the graphs as non-isomorphic. Moreover, the number of colors between two iterations, and (t + 1); does not change, i.c., the cardinalities of the images of Ct and S+t are equal, the algorithm terminates. For such i, we define the stable coloring as C2o()) (+)), for VHG
Message-passing neural networks (MPNNs) Intuitively, MPNNs learn a vectorial representation, i.c., d-dimensional real-valued vector, representing each node in graph by aggregating information from neighboring vertices. Formally, let G = (V(G), E) be a labeled graph with initial node features ((V) h. R.. A typical MPNN architecture is obtained by stacking permutation-cquivariint parameterized neural layers. Following, (Sarselli et al. (2008) and Gilmer et al. (2017). in each layer, / 2 0, we define the updated node features as:
h h@+1 = UPD(!+)) (1+1) (h AGG (th uue (()B)) Rd
(1)
for each V(G). The functions (?D and AGG are typically learned. Two examples of common MPNN layers, that will be considered in this work, are the graph isomorphism network (GIN) layer (Xu et al. 2019) defined as:
(a+
h (++1) = MLP((+))
Σ
h
(2)
(u.)EB((G)
where MLPP(++) is a multilayer perceptron (MLP) in layer 1 ++1 1 and (1+1) E TR is constant of layer I+ I differentiating node from its neighbors. Further, the gated graph convolutional network (GatedGCN) layer (Bresson and Laurent 2017) is defined as:
h(+1) ReLU
Σ
dhe о von!
(L.)
where que = (A BWn U10,, y00,A0) B(0 are linear layer weight. matrices, and a is the sigmoid
activation.
3.1 Graph positional and structural encoder (GPSE)
GPSE (Cantürk et al. 2024 is a recently introduced GNN model that aims to learn and predict robust and transferable representations for positional and structural encodings using RNFs as inputs, and constitutes the main architecture studied in our paper. In this paper, we choose to work with GPSE because it generalizes other PSEs, such as the graph Laplacian cigenvectors or random-walk structural encodings, in the sense that it learns these PSEs during its training phase. In what follows, we provide a brief standalone introduction to the model; further information is available via. the original paper.
GPSE model. GPSE employs an encoder-decoder architecture in which the encoder and decoder are trained jointly, whereas in inference, only the encoder is used. The encoder is deep MPNN consisting of stacked GatedGCN (Bresson and Laurent 2017) layers, with residual gating and skip-connections in-between layers. The decoder consists of multiple node-level MLP heads, each corresponding to a different PSE component.
The imputs to the model are graphs that are preprocessed to add a virtual node, and original node features replaced with 20-dimensional RNFs, æ; ~ I) E Ix20 which are first projected to match the inner dimension of the encoder, d (512 in the original paper):
h = ReLU x; Wipp)
(4)
5

---

Published in Transactions on Machine Learning Research (02/2025)
The resulting hidden representations are then passed through L GatedGCN layers: h 11+1)_
ReLU h h +
E (h." JEN(()
0 + +h w" @ (h) (nflw"))
(5)
where w Raxd are learnable parameters for layer I, a is the sigmoid function, and @ represents element- wise multiplication. The output of the encoder is a latent representation h h,")) which is decoded at each head by a two-layer MLP to predict the respective PSE component (e.g, absolute value of the second eigenvector, or the fifth RWSE) for each node:
0C = ReLU (n; (n..) Wh.2
(6)
with 1 E Rddd and Wx,2 E Rdx1 are learnable parameters.
GPSE additionally learns graph-lovel encodings in the absolute values of the graph Laplacian cigenvalues and cycle counts; do so the authors sum the node-level representations to obtain graph-level ones, which are then similarly passed through a 2-layer MLP per PSE.
From here we will assume that, given the structure of a graph G (V()), namely without any labels, as well as some random features X, GPSE provides node embeddings CPSE(G, X)()). Throughout most of this paper we consider GPSE to be pre-trained and thus fixed. We thus think of GPSE as PSE that provides node embeddings.
PSEs. In this work, we will be comparing multiple PSEs, including GPSE. Here we give a brief overview of the most relevant PSEs. The Laplacian cigenvector positional encoding (LapPE) (Dwivedi al.] 2020 Lim let al.) 2023) is the absolute value of the l2 normalized eigenvector associated with non-trivial eigenvalues of the graph Laplacian. The random walk structural encoding (RWSE) (Dwivedi et al. 2022b) is the probability of returning back to the starting state of random walk after k steps. We refer to the combination of all PSEs used in Cantürk et al. (2024) as AlIPSE. Lastly, we compare to Local-instance and Global-semantic Learning (GraphLog)) (Xu et al., 2021), which constructs a locally smooth latent space by aligning the embeddings of correlated graphs/subgrappe subgraphs. More details and some additional less relevant PSEs can found in Appendix D
Downstream universality. Throughout this work, we will be considering the expressivity that node augmentations (or positional and structural encodings) provide to GNNs. For example, previously shown in Sato et al. 2021];
|s Franks et al. (2023), random node features (RNF) added to GNN based on GIN layers enable the resulting model's universality. In this sense, RNF itself is not universal but we will refer to this as "RNF enables downstream universality". More generally, when we refer to the downstream universality or downstream expressivity of some PSE, then we are referring to the universality or expressivity that a GNN, that is able to approximate 1-WL, attains when its input features are augmented by this PSE.
4 The Expressivity of GPSE
In this section, we discuss the extent and relevance of expressivity for GPSE and other PSEs. We start by proving that GPSE using GatedGCN layers can universally approximate PSEs. We then discuss that PSEs do not enable downstream universality. In doing so, we also propose two additional GPSE-like models, that we call GPSE- and GPSE+ that verify the statements we make.
4.1 GPSE is a Universal Node Encoder
Since GPSE is mcant to be able to compute PSEs for any input graph and thus provide powerful positional and structural node encoding, it is important to verify that GPSE is indeed a universal node encoder. Because some PSEs are harder in a WL sense-to compute than CR, GPSE as an MPNN needs to be fully expressive. And indood, GPSE is a universal node encoder, because the input graph augmented with RNF, which we now show. First, note that GatedGCN layers can approximate GIN layers by the following theorem, which prove in Appendix B

---

Published in Transactions on Machine Learning Research (02/2025)
Theorem 1. Under mild assumptions the input graphs, an MPNN consisting of sufficiently many Gat- edGCN layers con upprozimate an MPNN made up of GIN layers arbilvarily well.
Combining Theorem with Theorem 3 from Xu et al. (2019), which states that an MPNN made up of GIN layers can learn to approximate 1-WL, proves that GatedGCN can also simulate 1-WL. Furthermore, Theorem 4 from Franks et al. (2023) shows that, assuming sufficiently many layers and sufficient width the layers within GPSE, any function on the graph structure (that is, functions of the form f((V, E)) ignoring node/odge features) can be computed. This proves that, indeod, under mild assumptions, GPSE universal and can learn to embed any PSE.
4.2 PSEs do not Guarantee Downstream Universality
While GPSE can learn to embed any PSE, this not sufficient to ensure the universality of the downstream model. In fact, PSEs in general do not provide universality of the downstream model. As shown in [Catürk ct al. 2024)) ; as well as in Table 1 GIN downstream network augmented with GPSE is not able to accurately generalize
the EXP, CEXP, CSL, TRI, and TRIX datasets, that are often used as expressivily benchmarks (Abboud et al., 2021 Murphy et al 2019). Let us assume that the pre-trained network in GPSE learned an identity mapping of the input random node features. Then, the resulting model is theoretically universal with high probability, as shown in Abboud et al. (2021) and Sato et al. (2021). This would imply that the issue lies in the pre-training of GPSE. That is, GPSE did not learn to encode PSEs which obtain high accuracy on some graphs that require high expressivity to distinguish.
GPSE+ We empirically verify that by adding relevant "hard" graphs, i.c., graphs that require high ex- pressivity, to the pre-training dataset of GPSE, GPSE is practically more expressive. Specifically, relevant hard graphs for the CSL dataset are 4-regular graphs Thus we define GPSE+to be the exact same model as GPSE trained on MolPCBA (>300.000 unique graphs), as well as 1000 random 4-regular graphs, cach with 24 nodes. We chose 24 nodes, as this is roughly the average number nodes for MolPCBA. Indeed, Table I shows that, by adding these hard graphs to the pro-training stage, the performance of GPSE on CSL increases significantly. The performance on EXP also increases; however, since the added graphs are not particularly relevant to the EXP dataset, the performance does not change dramatically as in the case of CSL. We also evaluated on TRI and TRIX, which are 3-regular graphs with triangles as labels, where again GPSE+ outperforms GPSE. We note, that the use of 4-regular graphs was merely demonstration focusing on the CSL dataset. In practice, either a task-tailored or a more general set of hard graphs would need to be used in the pretraining stage.
An interesting question that follows is, If the pre-training of GPSE is done as in GPSE+, is GNN aug- mented with GPSE universal? As stated before, if GPSE were to learn to output random features, the universality would be given for a sufficiently powerful downstream GNN. However, since GPSE is actu- ally trained to embed PSEs and not to output random features, node-embeddings contain at most marginal amounts of randomness, regardless of whether a GPSE or a OPSE+mode? is used. Alternatively, if, instead, GPSE does not output random features, then this implies that GPSE will, at best, learn to output node embeddings that represent the orbit partition (not considering the imput colors). Under this assumption, GPSE(G, (v) in the same orbit. However, under this assumption, there exist graphs A and B which a augmenndd MPNN cannot distinguish.
assumee that the GPSE computed
X) if and only and w are
Table 1: The inclusion of hard graphs in presatte- is crucial to the model's success on expressivity datasots. Without RNF, GPSE cannot perform well on these datascts. We report the accuracy (%)f of GPSE- GPSE, and GPSE+.
Method \
Dataset-+
EXP
CEXP
CSL
TRI
TRIX
GPSE-
49.8+0.3
71.9+2.99
9.3++3.3
74.8+11.1
95.1++0.0
GPSE
61.312.3
72.342.6
42.7+10.2
83.610.5
31.1
+
73.6+1.11
74.8+2.33
68.0+6.2
96.3+0.55
89.6+8.5
7

---

Published in Transactions on Machine Learning Research (02/2025)
Theorem 2. Let f G (V(G) D) be function such that f(G)(t) f(()(w) if v and in the same orbil of graph G. Then there exist colored graphs A = (VA, EA, LA) and B = (VB, EB, fB)) such that the colored graphs A' (VA, EA, (')) and B' = (VB, B, EB, BB) with (u) == RELABELLA, EA)(U) and (0(()= = RELABEL((B. f(Ve, Ey)(v)) cannot distinguished by the 1- 1-LL algorithm.
Proof. The graphs A and B are the graphs in Fig. 1c and Fig. ld Note that without the colors, both graphs are isomorphie, and all nodes are in one orbit, which is verified by the isomorphism in cycle notation (1, 4, 5, 6, 7, 9, 10, 11, 12). This means that (ạ(v) = (a(w) if and only if (v) = (ww) and ( = (g(w) and only if (v) ='g(w). Which implics that regardless of the specific function f. the partition of colors from la and En ''A and fB does not change and thus Fig. Tc and Fig. 1d also represent graphs A' and B'. Lastly, note that all nodes in Fig. Ic and Fig. 1d have two black and two red neighbors, which implies that these colors already represent the stable color partition C2 and thus 1-WL cannot distinguish these graphs
Note that, Theorem applies to all PSEs that do not involve random variable as output. Further, this means that if GPSE (assuming no randomness in its predictions) or other PSEs are used to process graphs that are more than 1-WL hard to distinguish, then the downstream GNN should be chosen based on expressivity, for instance, by also adding RNF into its input.
GPSE While the GPSE+ variant considers strengthening the pre-training stage with hard graphs, our experimental results in Section on real-world datasets do not read improved performance. Therefore, to address the question of the importance of expressivity in GPSE, we also replace the input RNF with constant feature vector, effectively removing the universality offered by RNF. We call this variant GPSE- It has the same model architecture as GPSE; however, instead of random normally distributed inputs, it uses vectors, i.e,, (G) == GPSE(G, ()) In practice, this implies that the SPPSE-modke is not capable of computing all PSEs for any input graph. As an example, GPSE cannot compute cycle counts for the graphs in Fig. la and Fig. 1b since GPSE cannot tell these two graphs apart. However, since molccules are almost trees (Ahn et al. 2022). -hooudshould be able to stiill learn the target PSEs for the pre-training dataset, MolPCBA, as well for the other evaluation datasets like ZINC-12k. Notably, Table [ shows that doSE-does not excel datasets that involve graphs harder than 1-WL. In particular, the performance of GPSE roughly in line with a constant model. On TRIX GPSE outperforms GPSE as well as GPSE+, because these other variants are having trouble generalizing well to the larger 3-regular graphs of TRIX, and actually perform worse than naive, constant predictor. The evaluations in Section 5 will demonstrate that, indeed, RNF not necessary for good practical performance either. In practice, al least for current datasets, GPSE, GPSE+, and GPSE perform comparably.
Practical implications. As will be demonstrated in the next section, the differences between GPSE, GPSE+ and GPSE-in in practice are virtually non-existent. This is likely due to the fact that expressivity is rarely relevant in practice. However, if expressivity is determined to be irrelevant GPSE probably be preferred, as the use of RNF in GPSE could lead to unpredictable results. While on the other hand,
(a)
(b)
(c)
(d)
Figure 1: GPSE without RNF cannot differentiate graphs (a) and (b). An MPNN with the orbit partition node features cannot differentiate graphs (c) and (d).
8

---

Published in Transactions on Machine Learning Research (02/2025)
Table 2: Using GPSE on ZINC-12k significantly reduces the number of epochs needed to reach the same test performance as other PSEs. This table shows the factor of speedup (in terms of epochs) of GPSE to reach the same MAE on ZINC-12k on various downstream GNNs and PSEs. For instance, means GPSE reaches the same performance with only half of the epochs. This table comparing GPSE-an and GPSE+to other PSEs can be found in Appendix G
PSE1 Downstream-
GCN
GatedGCN
GIN
GPS
none rand
71.2+11099
65.6412.2
60.2=
12.4
905.0:00.0
110.010.0
253.0=0.0
98.5=14.1
LapPE RWSE AlIPSE
43.8
45.5
31.9=4.7
14.7=1.7
20.5+2.
25.1#3.1
21.5=3.4
2.9
13.5+2.3
20.1+3.4
18.7=2.3
2.6+0.2
if expressivity is important, then an approach closer + be taken, specifically focusing on pretraining using hard graphs that are relevant to the task or generally hard graphs.
5 Experimental Results
We evaluate PSEs as well as the proposed GPSE variants from Section across three critical aspects of performance. First, we analyze the speed at which GPSE-angmenteed GNNs converge to the performance of other PSF-augmented GNNs. Specifically, we calculate the number of epochs required by GPSE to reach the performance attained by other bascline GNNs. Second, we explore the transfcrability of PSEs in data-scarce environments. To this end, we plot the amount of data (i.e., sample size) vs. performance, investigating how well PSE-angmented models perform with varying amounts of training data. Finally, we investigate why GPSE improves performance over other PSEs for most but not all datasets. We focus on ZINC-12K, the perhaps clearest example of good GPSE performance, and consider generalization by inspecting the gap between training and test. metrics.
Overall, experiments include three dataset types: (i) synthetic datasets EXP, CEXP, CSL, TRI, and TRIX (Abboud et al. 2021 Murphy et al. 2019 Sato et al. 2021). designated to study the expressivity of GPSE, as reported in Table 1 (ii) ZINC-12K, where we find GPSE to perform well across all considered
aspects, and (iii) MolNet, where we find that GPSE does not perform better than baseline methods in general. The evaluations on these diverse datasets allow us to provide well-grounded insights regarding the utilization of GPSE as a component in future GFMs. We provide details on the learning and evaluation procedures in Appendix E We elaborate the considered PSEs in Appendix D We elaborate the datascts and the
motivation for using them in Appendix F
5.1 GPSEs Convergence to PSEs Performance
The efficiency of neural network optimization critical, particularly in minimizing the time required for training models. Reducing the training time can result. significant. resource savings.
To evaluate the speedup GPSE enables, we compare how many epochs a GPSE-augmented GNN takes other PSE-angmented GNNs, shown in Table 2 Our results show
to reach the same performance that using GPSE yields good performance significantly faster compared with all other PSEs. The smallest speedup is factor of 2, and in almost all cases, GPSE obtains specdup factor of 10 or more. Reaching good performance laster not only saves training time during parameler tuning but also reduces the environmental impact by lowering CO2 emissions associated with prolonged computational efforts. We note here, that Table D does not imply that GPSE converges its optimal performance faster, it only implics that GPSE attains good performances faster than other PSEs. In fact, according our evaluations, GPSE converges at the same speed other PSEs (see Appendix G

---

Published in Transactions on Machine Learning Research (02/2025)
Difference in performance of Method to GPSE
ZINC-12K (GPS)
Difference in perforrance of Methed to GPSE
ToxCast (GINE)
AIIPSE
GraphLog
0.04
LapPE
LapPE
0.15
none
RWSE
RWSE
AlIPSE
0.02
0.10
GPSE
GPSE+
GPSE
GPSE
0.00
0.05
-0.02
0.00
-0.04
0.0125
0.025
0.05
0.1
0.2
0.4
0.8
0.0125
0.025
0.05
0.1
0.2
0.4
0.8
Training data ratio of all available data
Training data ratio of all all available data
(a)
(b)
Figure GPSE variants outperform all other PSEs regardless of the amount of available training data on 12kC-12k. Notably, for less available training data, the advantage of GPSE and its variants more strongly pronounced. However, for ToxCast the opposite true. This figure shows downstream training with fractions of the ZLNC-12K and ToxCast datasets. We show the difference in performance (MAE + for ZINC-12K and AUROC 1 for ToxCast) obtained by various PSEs, including GPSE and GPSE+. We show results additional datasets in Fig.
5.2 Influence of Sample Size
A common challenge in machine learning is the scarcity of available training data, which can significantly hinder model performance. It common in areas like NLP and CV to finetune pre-trained models in data- scarce applications. Some prominent examples are LLMs like GPT-3, which can be fine-tuned or used in zero-shot settings for various NLP tasks (Brown et al. 2020p. In CV, models like CLIP, which learn visual concepts from natural language supervision, have been effectively adapted to new tasks with minimal data RRdford et al. 2021). These approaches leverage powerful representations learned from large-scale data, making them highly effective in transfer learning scenarios.
To investigate how pro-trained GPSE models can mitigate the impact of limitod data, we conducted few- shot learning-inspired experiment. In this experiment, we progressively reduce the amount of training data for the downstream task, and evaluate the resulting performance of downstream GNN when combined with different PSEs against GPSE and its variants. As proposed in ablation study in Cantürk et al. (2024) we start with all training data (80% training, 10% validation, 10% testing) and iteratively halve the training data to just 1.25%, while leaving the validation and test data unchanged.
Fig. shows the results of the experiment on ZINC-12k and MolNet ToxCast datasets. GPSE's performance is used as baseline (black dotted line) and compared with other PSEs, including LapPE, RWSE, and the GPSE-an and
Both GPSE- and GPSE+ like models outperform all other PSEs, with the gap widening data decreases logarithmically. However, this advantage is not consistent across all datasets. For instance, on ToxCast, GPSF-like models outperform other PSEs with full training data but are surpassed by other PSEs in data-scarce scenarios. Additional results are provided in Fig. (Appendix highlighting the significant benofits of learned PSEs in future GFMs.
similarly to GPSE. On ZINC-12K, GPSE-
5.3 Generalization of PSEs
We now investigate why GPSE might or might not outperform other PSEs when used to augment downstream GNN models. We focus on two possible proxies for good performance: (i) better training loss and (ii) better generalization Notably, if one is kept constant, then the respective other will govern changes in
10

---

Published in Transactions on Machine Learning Research (02/2025)
Table 3: GPSE variants offer the largest (best) generalization error. This table shows the generalization
error (train test MAE) on ZINC-12k for various PSEs and downstream MPNN choices. The largest (best) values are bold, and insignificantly smaller values are underlined.
PSE 4 Downstreamm
GCN
GaledGCN
GIN
GPS
none rand
0.1133+0.010
-0.137=00013
-0.131+00001
-0.085=+00009
0.136==0.045
-0.234=0.041
-0.152:+0.02)
-0.158=0.000
LapPE
-0.112++..08
-0.118=0.009
-0.110=t0.007
-0.065++00032
RWSE
-0.091=0.007
-.008==0.010
-0.073::0.013
-0.048=0.006
AUPSE
-0.075=00000
-0.078=0.009
-0.060
-0.050++00007
GPSE
-0.03211.005
-..4550.004
-0.03440.004
-0.037=0.007
GPSE-
-0.033+-.000
-0.042- 0.005
-0.034+0.005
-0.042+0.005
GPSE+
-0.034400.006
-0.040=0.005
-0.035+00.004
-0.041+0.005
Table 4: GPSE does not always offer the lowest (best) generalization error. This table shows generalization error (train - test AUROC) on MolNet datasets. Smallest (bost) values are bold, and insignificantly larger values are underlined.
PSE 4 +
BACE
BBBP
ClinTox
HIV
MUV
SIDER
Tox21
ToxCast
GraphLog
17.311.6
32.0.1.2
21.7.1..
16.3.15.7
15.913.7
12.213.8
20.5.13.2
17.1 2.7
LapPE
6.1
27.6+2.1
18.0+4.5
13.146.3
14.6+3.1
11.8+1.5
14.1+1.2
17.4+1.4
RWSE
11.312.2
28.412.4
17.3124
12.91188
10.41.6
12.712.5
18.412.2
18.5118
AIPPSE
13.34-2.7
23.3+33.4
21.3+2.9
19.8+4.8
10.0+1.7
13.2+0.9
12.4+1.6
19.3+1.9
GPSE
10.6+2.44
25.6+4.3
16.8+7.4
17.2+4.8
17.6+0.7
12.4+3.0
13.5+1.8
19.1+1.3
GPSE-
9.943.6
26.313.8
17.4+5.1
13.846.7
17.9223
11.522.7
12.7+2.1
18.4=2.2
GPSE*
12.3444.0
26.5
18.2
12.8114.7
16.9.12.0
9.3
14.41199
19.6.10.7
test performance. In this set of experiments, we define the generalization error the difference between train performance and test performance, where the performance metric depends on the dataset and task of interest. For example, in the case of regression tasks such as on ZINC-12K, a larger valuc- on MAE- means better generalization, while for classification lasks, a lower value based on AUROC indicates better generalization. We provide the obtained generalization errors for ZINC-12k Table 3 and the respective train (and test) mean-absollte-erroo (MAE) in Table (and Table[16iin Appendix Db. On ZINC-12k the GPSE variants attain the best test performance regardless of the backbone (Table 16 in Appendix). Table 3 shows the GPSE variants altain the best generalization errors compared with other PSEs. In contrast, Table 5 shows that while GPSE attains fairly low training MAE, other PSEs "outperform" " the GPSE variants in terms of training performance. These observations imply that the performance gains of GPSE-augmented models are primarily due to better generalization, and not, for instance, due to a model that better fits the training set. However, this better generalization does not always hold. In contrast. previous observations, Table showing the generalization error for the MolNet datasets, demonstrates that GPSE and its variants be outperformed considering generalization examples). Better generalization and generally better performance are desired properties of foundation model. These results indicate that while GPSE shows some superior generalization capabilities, they need to be examined per case. While this work studied expressivity in Section 4 and generalization here, we are not attempting to conflate the two herein. The observations on expressivity and generalization are entirely scparate. Notably, even though GPSE- GPSE, and GPSE+hau have different practical expressivity, their generalization seems comparable, which agrees with previous work on the complexity of expressivity and generalization (Franks et. al. 2024
some downstream tasks (MUV and BACE are notable
11

---

Published in Transactions on Machine Learning Research (02/2025)
Table 5: GPSE variants do not offer the smallest (best) training error. This table shows the MAE on the trainset, which was also used as loss, on ZINC-12K for various PSEs and downstream MPNN choices. Smallest (best) values are bold, and insignificantly larger values are underlined.
PSE + \ Downstreamm>
GCN
GatedGCN
GIN
GPS
none
0.146+0.012
0.107=0.017
0.148=000014
0.038++0.012
rand
1.119=#0.067
0.988=00049
1.090=0.0021
0.711#000054
LapPE
0.106+00.010
0.071+00.009
0.107
0.076:t0.107
RWSE
0.086:00.008
0.078=0.011
0.102=00.011
0.027=0.008
AUPSE
0.077=0.006
0.064-0.0099
0.080
0.021
GPSE
0.093+00005
0.067+0.005
0.093+0.004
0.033
GPSE-
0.096+000006
0.071
0.096+000003
0.024+0.006
GPSE+
0.003:10.007
0.073=0.004
0.092-10.004
0.025+L0.006
6
Discussion and Conclusion
This paper explored PSEs on graphs, particularly the recently proposed GPSE. We found that the primary factor influencing PSE performance is their generalization ability, highlighting the need for deeper under- standing of strong generalization in GNNs a critical property for GFMs. Although GPSE offers promising approach, it does not consistently generalize well across tasks and graph structures, underscoring the need for models with improved generalization.
Future research should enhance generalization in GNNs, especially for graph SEs and PEs. Initial studies on the gencralization of PSEs and embeddings for substructures, such as Franks et al. (2024), suggest that subgraph-enhanced WL kernels' generalization depends the counted substructures. This may apply to MPNNs as well; for instance, PSEs used in GPSE pre-training generalize well on ZINC but poorly some MolNet datasets. The broader impact of graph structure generalization has been identified key challenge in ML on graphs (Challenge 3.2 in Morris et al. (2024)), ) and addressing these challenges will be crucial for advancing GFMs.
Acknowledgements
Part of this work was conducted within the DFG Research Unit FOR 5359 on Deep Learning on Sparse Chem- ical Process Data (BU 4042/2-1, KL 2698/6-1, and KL 2698/7-1) and the DFG TRR 375 (no. 511263698). SF and MK acknowledge support by the Carl-Zeiss Foundation (AI-Care, Process Engineering 4.0), the BMBF award 01/S2407A, and the DFG awards FE 2282/6-1, FE 2282/1-2, KL 2698/5-2 and KL 2698/11-1. ME is funded by the Blavatnik- Caik-Cabrrddge fellowship, the Cambridge Accelerate Programme for Scientific Discovery and the Maths4DL EPSRC Programme. Additional support is by Bourse en intelligence artificielle des Études supéricures et postdoctorales (ESP) 2023-2024 [SC]; Canada CIFAR AI Chair, IVADO (Institut de valorisation des données) grant PRF-2019-3588133922 FRQNT (Fonds de recherche du Québec Nature et technologies) grant 299376, NSERC Discovery grant 03267 and NSF DMS grant 2327211 [GW].
References
Michael M Bronstein, Joan Bruna, Taco Cohen, and Petar Veličković. Geometric deep learning: Grids, groups, graphs, geodesics, and gauges. arXiv preprint arXiv:2104.11 18478, 2021.
Lilapati Waikhom and Ripon Patgiri. A survey of graph neural networks in various learning paradigms: methods, applications, and challenges. Artificial Intelligence Review, 56(7):6295-633) 6364, 2023.
Christopher Morris, Martin Ritzert, Matthias Fey, William Hamilton, Jan Eric Lensson, Gaurav Rattan, and Martin Grohe. Weisfeiler and leman go neural: Higher-order graph neural networks. In Proceedings of the AAAT conference artificial intelligence, volume 33, 2019.
12

---

Published in Transactions on Machine Learning Research (02/2025)
Beatrice Bevilacqua, Fabrizio Frasca, Derek Lim, Balasubramaniam Srinivasan, Chen Cai, Gopinath Bal- amurugan, Michael M. Bronstein, and Haggai Maron. Equivariant subgraph aggregation networks. Tn International Conference on Learning Representations, 2022.
Haotian Ju, Dongyue Li, Aneesh Sharma, and Hongyang R Zhang. Generalization in graph neural networks: Improved pac-bayesian bounds on graph diffusion. International Conference on Artificial Intelligence and Statistics, pages 6314-6341. PMLR, 2023.
Shouheng Li, Floris Geerts, Dongwoo Kim, and Qing Wang. Towards bridging generalization and expressivity of graph neural networks. arXiv preprint arXiv:24 10. 10051, 2024.
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), pages 8533 8537. TEEE, 2021.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In International Conference on Learning Representations, 2019.
Christopher Morris, Yaron Lipman, Haggai Maron, Bastian Rieck, Nils M. Kriege, Martin Grohe, Matthias Fey, and Karsten Borgwardt. Weisfeiler and leman go machine learning: The story so far. Journal of Machine Learning Research, 24(333):1-59 2023. URL http::/jmmtrr.../// http:/rrr.....pppp///////2202000
.ttll
Muhan Zhang, Pan Lı, Yinglong Xia, Kai Wang, and Long Jin. Labeling trick: A theory of using graph neural networks for multi-node representation learning. Advances in Neural Information Processing Systems, 34: 9061-9073, 2021.
Ralph Abboud, ismail Îlkn Ceylan, Martin Grohe, and Thomas Lukasiewicz. The surprising power of graph neural networks with random node initialization. In Proceedings of the Thirtieth International Joint Conference on Artifical Intelligence (IJCAT), 2021.
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), pages 333 333-341. SIAM, 2021.
Maya Bechler-Speicher, Moshe Fliasof, Carola-Bibiane Schonlieb, Ran Gilad-Bachrach, and Amir Globerson. Towards invariance to node identifiers in graph neural networks, 2025. URL https://arxiv.or /bs// 2502. 13660
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, pages 9202 9223. PMLR, 2023.
Moshe Eliasof, Beatrice Bevilacqua, Carola-Bibiane Schönlieb, and Haggai Maron. Granola: Adaptive normalization for graph neural networks. arXiv preprint arXio:2404. 18344, 2024.
Vijay Prakash Dwivedi and Xavier Bresson. A generalivation of transformer networks to graphs. AAAI Workshop on Deep Learning on Graphs; Methods and Applications, 2021.
Devin Kreuzer, Dominique Beaini, Will Hamilton, Vincent Létourneau, and Prudencio Tossou. Rethinking graph transformers with spectral attention. Advances in Neural Information Processing Systems, 34: 11618-21629, 2021.
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, 2022a.
Derek Lim, Joshua David Robinson, Lingxiao Zhao, Tess Smidt, Suvrit Sra, Haggai Maron, and Stefanic Jegelka. Sign and basis invariant networks for spectral graph representation learning. In International Conference Learning Represendations, 2023.
13

---

Published in Transactions on Machine Learning Research (02/2025)
Ladislav Rampášek, Michael Galkin, Vijay Prakash Dwivedi, Anh Tuan Luu, Guy Wolf, and Dominique Beaini. Recipe for a general, powerful, scalable graph transformer. Advances in Neural Information Processing Systems, 15:14501-14515, 2022.
Vijay Prakash Dwivedi, Anh Tuan Luu, Thomas Laurent, Yoshna Bengio, and Xavier Bresson. Graph neural networks with learnable structural and positional representations. In International Conference on Learning Representations, 2022a.
Semih Cantürk, Remming Liu, Olivier Gagnin,e-Gagné, Vincent Létourneau, Guy Wolf, Dominique Beaini, and Ladislav Rampášek. Graph positional and structural encoder. In Ruslan Salakhuldinov, Zico Kolter, Katherine Heller, Adrian Weller, Nuria Oliver, Jonathan Scarlett, and Felix Berkenkamp, editors, Pro- ceedings of the 41st International Conference on Machine Learning, volume 235 of Proceedings of Machine Learning Research, pages 5533 5566. PMLR, 21 27 Jul 2024. URL https: https://proceedingss .ww.g...mm.....mmm.m.m.......... mlr press/ v235/ m735/annuur24a.0 html
Jacob Devlin, Ming-Wei Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. In North American Chapter of the Association for Computational Linguislics, 2019. URL https: set.aiicisemmmticccccooooarrrrr wtt.:aawtt...caaooooooooooooooaa 529673399
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert- Voss, Gretchen Krueger, Tom Hemighan, Rewon Child, Aditya Ramesh, Daniel Ziegler, Jeffrey Wu, Clemens Winter, Chris Hesse, Mark Chen, Fric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Πlya Sutskever, and Dario Amodei. Lan- guage models are few-shot learners. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 1877-1901) Cur- ran Associates, Inc., 2020. URL https://prroeeedings www.iinnn....u...eeeeeeeerrrie.e http://apppppeeeeee/pppppeeee fftles//pppe///222/111 Paperr pdf
Jiawei Liu, Cheng Yang, Zhiyuan Lu, Junze Chen, Yibo Li, Mengmei Zhang, Ting Bai, Yuan Fang, Lichao Sun, Philip S Yu, et al. Towards graph foundation models: A survey and beyond. arXiv preprint arXiv:2310.1182) 2023.
Mikhail Galkin, Xinyu Yuan, Hesham Mostafa, Jian Tang, and Zhaocheng Zhu. Towards foundation models for knowledge graph reasoning. In The Twelfth International Conference on Learning Representations. 2024. URL https: .eciiiewwweeeeeee www.eeeeee/ntiiieeee ddw.:mmiddijWooooFOO
Qian Huang, Hongyu Ren, Peng Chen, Gregor Kržmanc, Daniel Zeng, Percy S Liang, and Jure Leskovec. Prodigy: Enabling in-context learning over graphs. In A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine, editors, Advances in Neural Information Processing Systems, volume 36, pages 16302 16317. Curran Associates, Inc., 2023a. URL
neurips cctpsperrrpppeeeeeeeeeeeee /cce/pppe_ffeee/////p/e files/ pdf
Haitao Mao, Zhikai Chen, Wenzhuo Tang, Jianan Zhao, Yao Ma, Tong Zhao, Neil Shah, Mikhail Galkin, and Jiliang Tang. Position: Graph foundation models are alrcady here. In Forty-first International Conference on Machine Learning. 2024. URL https:///pperrevie http://ee/eeeeeeeeeee /tt.fforron-----000X.A0
Chuan Shi, Junze Chen, Jiawei Liu, and Cheng Yang. Graph foundation model. Frontiers of Computer Science, 1866):186355, 2024.
Lianghao Xia, Ben Kao, and Chao Huang. Opengraph: Towards open graph foundation models. arXio preprint arX:::2403.0111 011111 2024.
Hao Liu, Jiarui Feng, Locheng Kong, Ningyue Liang, Dacheng Tao, Yixin Chen, and Muhan Zhang. One for all: Towards training one graph model for all classification tasks. In The Twelfth International Conference on Learning Representations, 2024. URL. http:://ppppppeeereeeee//////ccs
14

---

Published in Transactions on Machine Learning Research (02/2025)
Christopher Morris, Fabrizio Frasca, Nadav Dym, Haggai Maron, Ismail Ilkan Ceylan, Ron Levie, Derek Lim, Michael M. Bronstein, Martin Grohe, and Stefanie Jegelka. Position: Future directions in the theory of graph machine learning. In Forty-first International Conference on Machine Learning, 2024. URL https://openreviirr net/ tet/
Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, et al. An image is worth 16x16 words: Transformers for image recognition at scale. In International Conference Learning Representations (ICLR), 2021.
Fabrizio Frasca, Fabian Jogl, Moshe Eliasof, Matan Ostrovsky, Carola-Bibiana Schönlicb, Thomas Gärtner, and Haggai Maron. Towards foundation models on graphs: An analysis on cross-dataset transfer of pretrained gnns. aieee preprint 0rXiv:2412.17600 2024.
Bahare Fatemi, Jomathan Halcrow, and Bryan Perozzi. Talk like a graph: Encoding graphs for large language models. In The Twelfth International Conference on Learning Representations, 2024. URL https:// openreview net/ forummorumm/m -idiuddddduxciCcr
Bryan Perozzi, Bahare Fatemi, Dustin Zelle, Anton Tsitsulin, Mehran Kazemi, Rami Al-Rfou, and Jonathan Halcrow. Let your graph do the talking: Encoding structured data for llms. arXiv preprint arXiv:2402.0553 2024.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Atlention is all you need. Advances in neural information processing systems, 30, 2017.
Balasubramaniam Srinivasan and Bruno Ribeiro. On the equivalence between positional node embeddings and structural graph representations. International Conference on Learning Representations, 2020. URL https://oppnrreveer wwt:/oorumidd
Chengxuan Ying, Tianle Cai, Shengjic Luo, Shuxin Zheng, Guolin Ke, Di Hc, Yanming Shen, and Tic- Yan Liu. Do transformers really perform badly for graph representation? Advances in neurol information processing systems, 34:28877- -28888 2021.
Vighnesh Shiv and Chris Quirk. Novel positional encodings to enable tree-based transformers. Advonces in neural information processing systems, 32, 2019.
Vijay Prakash Dwivedi, Anh Tuan Luu, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Graph neural networks with learnable structural and positional reprosentations. In International Conference on Learning Represendations, 2022b. URL http::/s/ppaaaarees.ssee///rrrrr
Grégoire Mialon, Dexiong Chen, Margot Selosse, and Julien Mairal. Graphit: Encoding graph structure in transformers. arXiv preprint arXiv:2106. 05667,, 2021.
Lingxiao 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
https:://openrevie http://pppppprorooeeeeeeoorrrarr
WYKoEH
Giorgos Bouritsas, Fabrizio Frasca, Stefanos Zafcirion, and Michael M Bronstein. Improving graph neural
network expressivily via subgraph isomorphism counting. IEEE Transactions on Pallern Analysis and Machine Intelligence, 45(1):657-666 2022.
Dexiong Chen, Leslie O'Bray, and Karsten Borgwardt. Structure-aware transformer for graph representation learning. In International Conference on Machine Learning, pages 3469 3489. PMLR, 2022.
Zuoyu Yan, Tengfei Ma, Liangcai Gao, Zhi Tang, Chao Chen, and Yusu Wang. Cycle invariant positional encoding for graph representation lcarning. In The Second Learning on Graphs Conference, 2023. URL
Billy Joe Franks, Markus Anders, Marius Kloft, and Pascal Schweitzer. A systematic approach to universal random features in graph neural networks. Transactions Machine Learning Research, 2023.
15

---

Published in Transactions on Machine Learning Research (02/2025)
Haggai Maron, Heli Ben-Hamu, Hadar Serviansky, and Yaron Lipman. Provably powerful graph networks. Advances in neural information processing systems, 32, 2019a.
Beatrice Bevilacqua, Moshe Eliasof, Eli Mcirom, Bruno Ribeiro, and Haggai Maron. Efficient subgraph GNNs by learning effective selection policies. In The Twelfth International Conference on Learning Rep- resentations, 2024. URL https://openrevier: net/ www.eeewwweettnnnnneeeeme httt:/oormiiddgppataae
Bohang Zhang, Jingchu Gai, Yiheng Du, Qiwei Ye, Di He, and Liwei Wang. Beyond weisfeiler-lehman: A
quantitative framework for GNN expressiveness. In The Twelfth International Conference on Learning Representations, 2024. URL httpps://openrevier hetppperrriie..ee///ooeoee rett/Eoruumicc:SKaa00177
George Dasoulas, Ludovic Dos Santos, Kevin Scaman, and Aladin Virmaux. Coloring graph neural networks for node disambiguation. In Christian Bessiere, editor, Proceedings of the Twenby-Nintt International Joint Conference on Artificial Intelligence, IJCAI-20, pages 1232. International Joint Conferences on Artificial Intelligence Organization, 2020. doi: 10.24963/ijee 200000022/44 2294. URL. https://doo....... org/10.
(1963//jca1.20200 294] Main track.
Ryan Murphy, Balasubramaniam Srinivasan, Vinayak Rao, and Bruno Ribeiro. Relational pooling for graph representations. In International Conference on Machine Learning, pages 4663-4673. PMLR, 2019.
Andrei Leman and Boris Weisfeiler. A reduction of a graph to a canonical form and an algebra arising during this reduction. Nauchno- Nouchno-Technicchen Technichesaaya Informatsiya, 2(9):12-16, 1968.
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE transactions on neural networks, 20(1):61-80, 2008.
Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In Proceedings of the 34th International Conference on Machine Learning- Volume 70, pages 1263- 1272. JMLR, org, 2017.
Xavier Bresson and Thomas Laurent. Residual gated graph convnets. arxiv preprint orXiv:1711.01553, 2017.
Vijay Prakash Dwivedi, Chaitanya K Joshi, Anh Tuan Luu, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Benchmarking graph neural networks. arXiv preprint arXiv:2003.000 00982, 2020.
Minghao Xu, Hang Wang, Bingbing Ni, Hongyu Guo, and Jian Tang. Self-supervised graph-level represen- tation learning with local and global structure. In Marina Meila and Tong Zhang, editors, Proceedinggs of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 11548-11558. PMLR, 18-24 Jul 2021. URL https: wttp://inw........s///s/3// pre9s/v139/ xu21g. html
Sungsoo Ahn, Binghong Chen, Tianzhe Wang, and Le Song. Spanning tree-based graph generation for molecules. In International Conference Learning Representations, 2022. URL https://
het/forumiid-wett 8T2m
Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agarwal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, et al. Learning transferable visual models from natural language supervision. In International conference on machine learning, pages 8748 8763. PMLR, 2021.
Billy Joe Franks, Christopher Morris, Ameya Velingker, and Floris Geerts. Weisfeiler-leman at the margin: When more expressivity matters. In Forty-frss International Conference on Machine Learning, 2024. URL https: wttp:/oonndd---
Emily Jin, Michael M. Bronstein, Ismail Πlka Ceylan, and Matthias Lanzinger. Homomorphism counts for graph neural networks: All about that basis. In Ruslan Salakhutdinov, Zico Kolter, Katherine Heller, Adrian Weller, Nuria Oliver, Jonathan Scarlott, and Felix Berkenkamp, oditors, Proceedings of the 4 1st International Conference on Machine Learning, volume 235 of Proceedings of Machine Learning Research, pages PMLR, 21-27 27 Jul 2024. URL httttt:://poceeeeee
mlr press/v235// in24a. html
16

---

Published in Transactions on Machine Learning Research (02/2025)
Christopher Morris, Gaurav Rattan, and Petra Mutzel. Weisfeiler and leman go sparse: Towards scal- able higher-order graph embeddings. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 21824 21840. Cur- ran Associates, Inc., 2020. URL
www.rddwnnnn.n.nn.oooemm (ttapppr_fileee/pprr/000///0// pdf
Zhaohui Wang, Qi Cao, Huawei Shen, Xu Bingbing, Muhan Zhang, and Xueqi Cheng. Towards efficient and expressive GNNs for graph classification via subgraph-aware weisfeiler-lhhman. In The First Learning on Graphs Conference, 2022b. URL httpps://oppnrreviv htt/foorumm//ddaahhphhhhhh
Haggai Maron, Ethan Fetaya, Nimrod Segol, and Yaron Lipman. On the universality of invariant networks. In Kamalika Chaudhuri and Ruslan Salakhutdinov,, editors, Proceedlings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Reseorch, pages 09-15 Jun 2019b. URL https::/proceeddiii mlr. wtt...pree/////////e http:///////mmmmm19.aaahccm
PMLR,
Bohang Zhang, Shengjie Luo, Liwei Wang, and Di He. Rethinking the expressive power of GNNs via graph biconnectivity. In The Eleventh International Conference Learning Representations, 2023. URL
https://opearevieu het:
Yinan Huang, Xingang Peng, Jianzhu Ma, and Muhan Zhang. Boosting the cycle counting power of graph neural networks with 28- In The Eleventh International Conference Learning Representations, 2023b. URL https://openrrviiew..t
Yujia Li, Daniel Tarlow, Mare Brockschmidt, and Richard Zemel. Gated graph sequence neural networks. In The Eleventh International Conference on Learning Representations, 2013.
Weihua Hu*, Bowen Liu", Joseph Gomes, Marinka Zitnik, Percy Liang, Vijay Pande, and Jure Leskovec. Strategics for pre-training graph neural networks. In International Conference on Learning Representa- lions, 2020.
Xiaoxin Hc, Bryan Hooi, Thomas Laurent, Adam Perold, Yamn LeCun, and Xavier Bresson. A generalization of vit/mlp-mixes to graphs. In International Conference on Machine Learning, pages 22724-12745. PMLR, 2023.
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovee. Open graph benchmark: Datascts for machine learning on graphs. Advances in neural information processing systems, 01-22118-22113 2020.
Zhenqin Wu, Bharath Ramsundar, Evan N Feinberg, Joseph Gomes, Caleb Geniesse, Aneesh Pappu, Karl Leswing, and Vijay Pande. Moleculenet: A benchmark for molecular machine learning. Chemical Science, 9, 10 2017. doi: 10. 10.1039/C75 C7888/264666
Vijay Prakash Dwivedi, Chaitanya K. Joshi, Anh Tuan Luu, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Benchmarking graph neural networks, 2022c. URL
00982
Rafael G6mez-Bombarell: Jennifer N. Wei, David Duvenaud, José Miguel Hernández-Lobato, Benjamín Sánchez- Lengeli-,,ng,,ing, Dennis Sheberla, Jorge quuilera-Iparaguirree Timothy D. Hirzel, Ryan P. Adams, and Alán Aspuru-Guzik. Automatic chemical design using a data-driven continuous representation of molecules. ACS Centrol Science, 4(2):268 276, Jan 2018. ISSN 2374-7951. doi: 10.1021/acscente 7b00572.
Ruoxi Sun, Hanjun Dai, and Adams Wei Yu. Does GNN pretraining help molecular representation? In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho, editors, Advances in Neural Infor- mation Processing Systems, 2022. URL https://openreviet: http:://opppaoeoeeeeoooooorrorre htt.://ww..tttoouu/////yrrggoon.
17

---

Published in Transactions on Machine Learning Research (02/2025)
A Expressivity
For the most part, in this work, we only consider expressivity attained from RNF because it was proposed as the method of attaining expressivity in Cantürk et al. (2024). Here we now discuss the reason for this choice as well as some related work on the topic of expressivity in machine learning on graphs. Related work on expressivity has focused on two main dircctions for attaining expressivity for MPNNs.
The first direction, which we discussed in detail in this paper, is essentially the use of PSEs. Notably PSEs
like LapPE (Kreuzer al.] 2021 Rampášek et al. 2022) and RWSE (Rampášek et al. 2022 Dwivedi and
Bresson 2021; Dwivedi ct al. 2022bb increase expressivity when used to augment downstrcam MPNNs but
have not been shown to be universal and in fact we show in this work that they cannot be universal.
Further
PSEs that are well-known to be universal are based on subgraph counting (Shiv and Quirk
2019
Bouritsas
ct al.
2022
Zhao ct al.
2022 Chen et al. 2022 or homomorphism counting (Jin et al.
2024
Bouritsas
ct al.
2022 Zhang et al.
2024 However, related work usually considers the setting of uncolored graphs, in
which case these PSF are indeed universal if sufficiently many subgraphs/homoooon /hhhhhooommisinnnnnnono are being counted.
Once more, according to Theorem [subgraph and homomorphism counting that disregards node colors will not grant universality to augmented downstream MPNNs considering colored graphs. The emphasis here is PSEs that disregard node colors, one could propose subgraph and homomorphism counting of colored subgraphs which would be fully universal. Lastly, RNF which can be considered PSE has been shown to grant universality when used to augment downstream MPNNs (Abboud et al.) 2021 Sato et al., 2021 Franks ct al. 2023). As RNF relies on randomness to differentiate nodes during computation, RNF is universal regard less of node colors. The universality or expressivity of PSEs inherently linked to the individualization refinement algorithm for which PSEs act as individualization functions as discussod in Franks et al. (2023) which is inherently elficient assuming that any precomputations of the PSEs can be done efficiently.
The second direction modifies an MPNN's computation to attain more expressivity. Common examples include the k-GNN (Morris et al. 2019 2020 Wang et al. 2022b) and PPGN (Maron et al. 2019a b).
These higher-order methods are essentially related to the k-dimensional Weisfeiler-Lemaa algorithm and, as a result, suffer from high computational and memory costs. However, they notably show advantages in performance some cases.
GPSE (Cantürk et al. 2024) used RNF instead of other methods of expressivity. Notably, of the met mentioned, only RNF, subgraph, and homomorphism counting, and higher-order methods are truly universal. Subgraph and homomorphism counting, however, require potentially very large set of graphs to be counted (which is even bigger if not infinitely large for colored graphs), and higher-order methods might require a very large order (in the case of k-GNNs, a very large k) for which the computational and memory cost can be prohibitively large. In this sense, then, RNF is the only simple, effective, and scalable method of granting GPSE universality, which makes the best choice for GPSE.
Lastly, in this work we focus mostly expressivity it pertains to the 1-WL, however, some more fine- grained approaches to expressivity have been recently proposed. For example, expressivity based on bicon- nectivity (Zhang et al. 2023) expressivity based on homomorphism counting (Zhang et al. 2024).
B Proof of Theorem 1
Theorem 1. Under mild assumptions the input graphs, an MPNN consisting of sufficiently many Gat- edGCN layers can approzimate MPNN made up of GIN layers arbitrarily well.
Proof. A GIN layer is defined as follows:
h (1+1) MI.P (1+))0)
Σ
h
(a.))EE(G)
For simplicity we will assume the MLP be made up of two linear transformations with ReLU activation. However, the following proof also be modified for other ML. choices.
18

---

Published in Transactions on Machine Learning Research (02/2025)
For the GatedGCN layers, will assume that the input graphs node features contain one feature that is
constant for all nodes, i.e., if the input graph is G = (V, F)) with node features X V - IR, without loss of generally, Ve E V X = 1. We will ensure that this is also true for the output after multiple GatedGCN layers. This means that we will be working with the invariance that Vv, (n!)) )o = Now, note that one GatedGCN layer defined as
hg (1+1) ReLU(U
E
The vO)!)
(a,))BBIG)
with
T (A + B0))
We first define a GatedGCN layer that approximates (1 + ) + (E ( Then, two GatedGCN layers are defined that compute the MLP. For this assume that we are trying to approximate layer of the GatedGCN. By abuse of notation, we will refer to the hidden
the GIN and are defining layer representations of the GIN of node i in layer I as h and refer the same for the GatedGCN h Note
that, if are approximating (1) by multiple GatedGCN layers starting at ha (1) then (1) equality in the first component.
1
hu
(
with
Let > a > 0, then by choosing A = lo- aa)1
0], that is the first column is filled with t- a)
and it is 0 everywhere else, and B = 0, (A h (1)
+ Bu') (")) = (1 a)1. Let B = (1 + e) a), then
0"
choosing (())
T
and U(())
BI
I
0 -31
ReLU(U()) (
+
Σ (u.))EE(G)
Ti
(1)
② (()ng))
= ReLU((1 - ar) ReeLU(-(1 aa) (1)
Notice that
[o I -1] We (())
+++
Mij 2 ((n)))))
((()
(a+c))++ +
=(1 -a)
(U.)EE((G)
From here on refer to
p=:= (1+c)h
Σ
h!!)
(L.)
and
o ReLU(U ((')
Σ
(1) Tij
2 (()))
(u.))
Now assume that the MLP of the GIN in layer is defined as follows:
MI. Rel.U(W.Re.U(Wwzz)
19

---

Published in Transactions on Machine Learning Research (02/2025)
0" 0"
We can choose v((+1) = O, a zero matrix, and U((++1) AU*+) and B((+1),
then regardless of the choice of
0
W,
Wi
ReLU(UR(+)) +
E
('+1) o v(r+))p))
ReLU(U((+D()
Mi
(u,e)EF(G)
(I-a)ReLU(WIpp)) =: =:
0"
Similarly, choosing V((+2) 00 and (1(+22)
W22
ReLU(U
(2+
C (((+2) p. = ReLL (W)
Mij
(u,))E((G)
(1 RRLLU((..RLU(()P)))
1
ah-a) (+1)
Considering the difference between the relevant components, we get that the approximation error is
max 1,
h
max 1,
[ - (1 -1 a
max(lah! 1'1
1,1
a max[|n]]] (1I] 2,
Assuming that maxi, is bounded, this quantity be arbitrarily small by choosing small enough. To be clear, the assumption on the input we require is that max is bounded and that each node carries a feature that is constant over all nodes, in this proof we assumed this constant to be 1, however, this is true for any such non-zero constant. Notably, we can also make weaker assumptions, by assuming that there is linear combination of features that is constant over all nodes. However, in practice, we can simply add constant 1 as feature to each node, which is a common augmentation ensure MPNNs count the size of neighborhoods.
C Additional expressivity experiment
Here we include an additional expressivity experiment based on Huang et al. (2023b). The task is to count the inclusion of nodes in certain substructures on random Erdös-Rényí graphs. As in the original work, we train 5-layer GatedGNNs (Li et al. 2013). We run the experiment with 10 difffrrent random seeds and report the test MAE divided by the label standard deviation referred to as normalized MAE in Table 6 and Table 7 Since GPSE is trained to predict cycle counts, would expect GPSE to perform well in Table 6 However, as demonstrated previously, GPSE only learns to count cycles for molccule-like graphs, because these are the only graphs included in the pre-training set. GPSE+has additional hard graphs added to its pre-training set, which appears to help its performance somewhat, although its performance is still a far cry from other al.) (2023b). Perhaps adding Erdös-Rényi graphs instead of random regular
mothods reported in Huang graphs would help with its performance. In some instances GPSE performs best, which might be due GPSE-ovvrritie less to the use of RNT.
20

---

Published in Transactions on Machine Learning Research (02/2025)
Table 6: The inclusion hard graphs in GPSE+ pare--rrrtttnnng crucial to the model's success on expressivity datasets. GPSE* performs perforrss noticeably better for 3-cycle and 4-cycle counting, while for 5-cycle and 6-cycle counting, the differences between the methods are reduced. Notably, GPSE GPSET outperforms GPSE, indicating that perhaps the use of RNI without adequate pre-training graphs leads to overfitting. We report the normalized mean absolute error & of GPSET, GPSE, and GPSE+of counting different subgraphs. This experiment is based on Huang et al. 2023b
Method Task
3-cycle
4-cycle
5-cycle
6-cycle
GPSE- GPSE
0.20810.002
0,167:0.001
0.155#0.001
0.117:10.001
0.220=000002
0.174+0.002
0.161#0.001
0.122
GPSE+
0.147=0.002
0.15610.001
0.152=0.001
0.122::0.001
Table 7: The inclusion of hard graphs in t pre-trainng crucial to the model's success on expressivity datasets. GPSE+ perforrs noticcably better for TT and CC counting while the differences between the methods for 4-clique and 4-path counting reduce. GPSE perforrms noticeably best for TR. We report the normalized mean absolute error | of GPSE", GPSE, and GPSE+ of counting different subgraphs. TT refers to a tailed triangle. CC refers to a chordal cycle. TR refers to a triangle rectangle. This experiment is basod
on Huang et al. 2023b
Method
Task
TT
CC
4-Clique
4-Path
TR
GPSE-
0.24440.002 0.260=00.001
0.195:0.002
0.14710.001
0.06311.0000
0.160=10.002
GPSE GPSE+
0.208=+0.022
0.148+0.001
0.065++0.001
0.174+00002
0.200=10.001
0.182:10.002
0.149
0.067:10.000
0.168:10.001
D PSEs
We consider simple undirected and unweighted graph G = E) with vertex set V and edge set E, and no node or edge features. The number of nodes and edges are denoted with [V] and m |E), respectively. The corresponding adjaceney matrix of graph G is M E 1 where My = if (v,,2) E and 0 otherwise. The graph Laplacian L is then defined as
L=D-M M
(7)
where e Nux* is the diagonal degree matrix such that D = deg(v:) ((x))) [u u) E}}. The graph Laplacian is real symmetric matrix, with its full cigendecomposition
L = UAUT
(8)
where, A# = X and U = are the ith eigenvalue and eigenvector (an eigenpair) of the graph Laplacian. We sort the cigenpairs from the smallest to largest cigenvalue, i.c., 0 = A1 S X2 S ... S An- We further denote Ô (and analogously the subdiagonal matrix Á) as the matrix of Laplacian eigenvectors corresponding non-trivial eigenvalues.
Ú (1,41
Finally, denote the (62) normalization operation normalize(r) ||=||
In Ürn et al. (2024), , the nodo-level PSEs presented below are normalized to zero mcan and unit standard deviation per graph when training GPSE; we follow this for training stability in training GPSE+and GPSE-. When used as standalone or combined benchmarks, the PSEs are normalized.
21

---

Published in Transactions on Machine Learning Research (02/2025)
Laplacian eigenvector positional encodings (LapPE)
LapPE is defined as the absolute value of the bg normalized eigenvectors associated with non-trivial eigen- values. By default, we use the first four LapPE to train GPSE.
= | normalize (U
(10)
The absolute value operation is needed to counter the sign ambiguity of the graph Laplacian cigenvoctors, a known issue to many previous works that use the Laplacian eigenvectors to augment the models (Dwivedi
et al. 2020 Lim et al,, 2023). We maintain learning this absolute value function the eigenvectors as per Cantürk et al. (2024). and similarly learn the cigenvalues as graph-level attributes.
Random walk structural encodings (RWSE) The random walk matrix is defined as the row- normalized adjacency matrix P = :DD Pij corresponds to the transition probability from us to vy at given step.
The hth RWSE (Dwivedi et al.) 2022b) is defined as the probability of returning back to the starting state of a random walk after & steps of random walk:
RWSE2 = diag(P*
(11)
AllPSE Cantürk et al. 2024) compare the learned encodings (GPSE) with combinations of multiple PSEs in addition to the standalone LapPE and RWSE for a fairer comparison. Two "combined" encodings are considered: Combining the two standalone encodings as LapPE+RWSE, and AlIPSE, which represents combination of all PSEs used in GPSE training. The following encodings thus not used in standalone form, but are relevant in that they are essential to GPSE training well the AllPSE benchmark.
Electrostatic potential positional encodings (ElstaticPE) ElstaticPE treats each node as charged particle to compute rostatti polentials between node pairs, based on the pseudoinverse of the graph Laplacian L with the diagonal set to (so that the potential of each node each node's potential on itself is 0) resulting in:
Q L diag (I
(12)
ElstaticPE for any node v; is then a collection of statistics that summarizes the electrostatic interaction of v, with other nodes, such as the minimum, mean and standard deviations of polentials from ey to all other nodes By or only its neighbors es (ex)) (Kreuzer al.) 2021).. We defer to Cantürk al. (2024) for more detailed definitions of its individual components.
Heat kernel diagonal structural encodings (HKdiagSE) As defined in
Cantürk et al. 2024
HKdiagSE,
Σ -k (orm.)
(13)
6
Cycle counting structural encodings (CycleSE) CycleSE counts the number of k-cycles in the graph (e.g., 3-cycles correspond triangles in the graph) to encode global graph structure. Similar LapPE cigenvalues, CycleSE is learned graph-level regression task in GPSE training.
CycleSE, [CCycles of length k)
(14)
22

---

Published in Transactions on Machine Learning Research (02/2025)
E
Training and Evaluation Details
(2024) and uses the exact same experimental setup as well as largely the same code. The code itself is modified to accommodate the additional experiments proposed here. That is, for the experiments shown in Fig. 2 and Fig. 3 as well as the additional datasets CEXP, TRI, and TRIX, presented Table We thus refer to Cantürk et al. (2024) for further details beyond those presented here.
This work is built upon Cantürk et al.
Details on model design are shown in Table and Table
Table 8: GPS+ hyperparameters for molecular property prediction benchmarks
Hyperparameter
ZINC-12k
# GPS Layers
10
Hidden dim
64
GPS-MPNN
GINE
GPS-SelfAitn
# Heads
4
Dropout
0.00
Atlention dropout
0.50
Graph pooling
mean
PE dim
32
PE encoder
2-Layer MLP
Input dropout
0.50
Output dropout
0.00
Batchnorm
yes
Batch size
32
Learning rate
0.001
# Epochs
200
# Warmup epochs Weight decay
50
1.00e-5
# Parameters
292,513
PE precompute
min
Time (epoch/total)
10s/5.781
MoleculeNet small benchmarks settings We used the default GINE architecture following previous studies Huu* et al. 2020), which has five hidden layers and 300 hidden dimensions. For all five benchmarks, we use the same GPSE processing encoder settings as shown in Table Da
CSL, EXP, and TRI synthetic graph benchmarks settings We follow He et al. 2023 and use GIN Xu et al. 2019 as the underlying MPNN model, with five hidden layers and 128 dimensions. We use the same GPSE processing encoder settings for CSL, EXP, CEXP, TRI, and TRIX as shown in Table 9b
E.1
Convergence to PSEs Performance
This experiment is modeled after the experiment in Table 3 of Cantürk models (GCN, GatedGCN, GIN, and GPS) are trained using varying PSE' (none, rand, LapPE, RWSE, AllPSE) well as GPSE, where as per usual use pre-trained GPSE node encoder trained on MolPCBA, ZINC-12k. The exact architectures, like the number of layers and embedding sizes of the downstream models, vary based on previous studics. We refer to the human-rcadable YAML files in our code and the code Crnattük el al. (2024). for the exact architectures. As in ürk el al. (2024), GCN, GatedGCN, and GIN are trained using Adam with a learning rate 10-3, 3, a weight decay of 10 for 1000 epochs with early stopping based on a validation split. Additionally, they use PyTorchs learning rate with 0.5 if the loss does not reduce for 10 consecutive epochs. GPS on other hand uses AdamW with the same learning rafe and weight. decay, but trained for 2000 epochs with the learning rate modified by
(2024). Different downstream
to multiply the
23

---

Published in Transactions on Machine Learning Research (02/2025)
Table 9: GPSE processing encoder hyperparameters for MoleculeNet small benchmarks and syuthetic WL graph benchmarks.
(a) MoleculeNet small benchmarks settings.
(b) Synthetic WL graph benchmarks settings.
Hyperparameter
Hyperparameter
PE dim
PE dim
128
PE encoder
Linear
PE encoder
Linear
Input dropout
0.30
Input dropout
0.00
Output dropout
0.10
Output dropout
0.00
Batchnorm
yes
Batchnorm
yes
Learning rale
0.003
Learning rate
0.002
# Epochs
100
# Epochs
200
# Warmup epochs
Weight decay
Weight decay
PyTorchs DosineAAmeallng@arRReettt with 50 warmup epochs a typical choice for transformer models. For Table 14 we collect for each backbone B using each PSE (except GPSE) P the number of epochs e until the best validation performance is achieved as well as the test performance at this point. We then compute how many epochs GPSE takes to reach this same test performance ég that is the speedup of GPSE over P.
GrSE>P We report aPSESP
E.2 Influence of Sample Size
This experiment is modeled after the experiment in Table 3 and Table of Cantürk et al. (2024) considering only the GPS backbone. The GPS backbone trained with varying PSEs (none, rand, LapPF, RWSE, AllPSE) as well GPSE, GPSE and GPSE+on ZINC-12K. Also, a GINE backbone is trained with varying PSEs (LapPE, RWSE, AllPSE) well GPSE, GPSE and GPSE+ on MolNet. All of these models are trained for a varying fraction of the dataset. The base case for this is split of 80% for the training set, 10% for the validation set, and 10% for the test set. This 80% for the training set is then progressively reduced by factors of 2 without changing the size of the validation and test sets. The smallest training set fraction 1.25% = 80% 1 for a total of different training set fractions. We average each of 26 these runs over 10 random seeds. Finally, we subtract from each method except GPSE the performance of GPSE for the respective training fraction and report the results in Fig. and Fig. including their standard deviation.
E.3
Generalization of PSEs
This experiment is almost the same as Table 2 The only difference that we do not report the speedup but
instead report the MAE the test set in Table 16 as well the train set in Table 5 In addition, also
report the difference of the two in TableB Following the experiment from Fig, 2 and Fig. 3 we also conduct this experiment for the MolNet datasets training before a GINE backbone instead of a GPS backbone for a slightly different set of PSEs. We present the AUROC on the test set in Table 17 and the difference between the AUROC on the test and train set Table 4
F Datasets
A collection of task information and classical graph properties for all considered datasets are presented in What follows are short descriptions and citations for each the used datasets.
Table 10 and Table []]
MolPCBA Hu et al.
2020 (MIT License) contains 400K small molecules derived from the MoleculeNet 2017). There are 323,555 unique molecular graphs in this dataset.
benchmark (Wu et al.
24

---

Published in Transactions on Machine Learning Research (02/2025)
Table 10: Task information for datasets used in transferability experiments. TRIX* shows the information
for the test set of TRIX.
Num. graphs
Nun. nodes
Num. edges
Pred.
Pred.
Num. tasks
Dataset
Metric
level
task
ZINC-12K
12,000
23.15
24.92
graph
reg.
MAE
MolHIV
41,127
25.51
27.46
graph
class.
(binary)
AUROC
MolPCBA
437,929
25.97
28.11
graph
class.
(binary)
128
AP
MoIBBBP
2,039
24.06
25.95
graph
class. (binary)
AUROC
MolBACE
1,513
34.09
36.86
graph
class. (binary)
AUROC
MolTox21
7,831
18.57
19.29
graph
class. (binary)
21
AUROC
MolTox
8,576
18.78
19.26
graph
class. (binary)
617
AUROC
MoISIDER
2,039
33.64
35.36
graph
class. (binary)
27
AUROC
CSL
150
41.00
82.00
graph
class. (10-way)
ACC
EXP
1,200
48.70
60.44
graph
class. (binary)
ACC
CEXP
1,200
55.78
69.78
graph
class. (binary)
ACC
TRI
1,000
20.00
30.00
node
class. (binary)
ACC
TRIX
1,000
100.00
150.00
node
class. (binary)
ACC
Classical graph properties of graph-level datasets used in transferability experiments. shows the classical graph properties for the test set of TRIX.
Table 11:
TRIX
Num. nodes
Num. edges
Approx. max clique
Cluster. coeff.
Num.
Density
Connectivity
Diameter
Centrality
triangles
ZINC-12k
23.15
24.92
0.101
1.00
12.47
2.06
0.101
0.006
0.06
MolHIV
25.51
27.46
0.103
0.927
11.06
2.02
0.103
0.002
0.03
MolPCBA
25.97
28.11
0.093
0.998
13.56
2.02
0.093
0.002
0.02
MoIBBRP
24.06
25.95
0.114
0.950
10.75
2.03
0.114
0.003
0.03
MoIBACE
34.09
36.86
0.070
1.00
15.22
2.10
0.070
0.007
0.10
MolTax21
18.57
19.29
0.157
0.976
9.37
2.02
0.159
0.003
0.03
MolToxCass
18.78
19.26
0.154
0.803
7.57
2.02
0.154
0.003
0.03
MoISIDER
33.64
35.36
0.103
0.856
12.45
2.02
0.120
0.004
0.04
CSL
41.00
82.00
0.100
3.98
6.00
2.10
0.100
0.050
4.10
EXP
48.70
60.44
0.054
0.00
1.00
2.00
0.054
0.000
0.00
CEXP
55.78
69.78
0.19
4.03
2.00
0.000
0.00
TRI
20.00
30.00
0.158
2.62
5.14
2.84
0.158
0.088
1.75
TRIX
100.00
150.00
0.030
2.94
8.76
2.81
0.030
0.017
1.66
25

---

Published in Transactions on Machine Learning Research (02/2025)
To extract unique molecular graphs, we use RDKit with the following steps:
For each molecule, convert all its heavy atoms to carbon and all its bonds to single-bond.
Convert the modified molccules into a list of SMILES strings.
3. Reduce the list to unique SMILES strings using the set operation in Python.
ZINC-12K Dwivedi et al. 2022c) (Custom license, free to use) 12K subset of the ZINC250K dataset (Gómez-Bombant
et al. 2018 Each graph is molecule whose nodes atoms (28 possible lypes) and whose edges are chemical bonds (3 possible lypes). The goal is to regress the constrained solu- bility (wiivedi et al., 2022c) (logP) of the molecules. This dataset comes with a pre-defined split with 10K training. 1K validation, and 1K testing samples.
MoleculeNet. small datasets (Hu el al. 2020 (MIT License) We follow Sun et al. (2022) and use the selection of five small molecular property prediction datasets from the MoleculeNet benchmarks, including BBBP, BACE, Tox21, ToxCast, and SIDER. Each graph is a molecule, and it processed the same way for MolHIV and MolPCBA. All these datasets adopt the scaffold splitting strategy that is similarly used on MolHIV and MolPCBA.
CSL Dwivedi et al. graphs (Murphy et al. 2019 The goal is to classify each graph into one of ten isomorphism classes. The dataset is baass-balanced. where each isomorphism class contains 15 graph instances. Splitting is done by stratified five-fold vols-valiiation.
2022c (MIT License) contains 150 graphs that are known as circular skip-link
EXP and CEXP (Abboud al. 2021 (wnknown license) contain 600 pairs of graphs (1,200 graphs in total) that cannot be distinguished by 1&2-WL, tests. The goal is to classify each graph into one of two isomorphism classes. Splitting is done by stratified five-fold cross-validation. CEXP is modified version of EXP, where 50% of pairs are slightly modified to be distinguishable by 1-WT.
TRI and TRIX (Sato et al.] 2021 (unknown license) contain 1000 3-regular 20-order graphs. The goal is to classify for each node whether it is contained in triangle. Since the node colors of regular graphs are stable under 1-WL, MPNNs cannot tell nodes in these graphs apart, and thus, this task cannot be solved by vanilla MPNNs. TRIX is extrapolation dataset of TRI, that shares the exact same training (and validation) dataset, however, the testset contains 1000 3-regular 100-order graphs. Splitting is done by five-fold cross- validation.
G GPSE Convergence to PSEs Performance
Here we present additional results showing the speedup GPSE (Table 12 and CEPS**TTable compared to the bascline PSEs instoad of GPSE on ZINC-12k.
13 offer
We also present the average epoch that early stopping stopped on for the GPSE variants and all PSEs Table [4] This table shows that GPSE and its variants do not always converge faster their respective optima when compared to other PSEs.
Further, we also present the speedup GPSE offers compared to baseline PSEs on MolNet in Table 15 Note that since GPSE does not always increase the overall performance, there are cases in which GPSE never reaches a better value than the baseline PSE. Thus, we mark each entry with an exponent indicating the number of seeds on which GPSE outperformed the baseline PSE and the statistics for these seeds. GPSE performs better on at least one seod, the average and standard deviation are shown. there no such seed, the table reads inf.
H Influence of Sample Size on MolNet
Fig. 3 shows the influence of the size of the training dataset on performance for all MolNet datasets. In the main body of this work, we presented the figure for ToxCast, which is arguably the worst case for GPSF,
26

---

rand Published in Transactions on Machine Learning Research (02/2025)
Table 12: Using GPSE on ZINC-12K significantly reduces the number of epochs needed to reach the same test performance as other PSEs. This table shows the factor of speedup (in terms of epochs) of GPSE to reach the same MAE on ZINC-12k on various downstream GNNs and PSEs. For instance, means reaches the same performance with only half of the epochs.
PSE| Downstream-+
GCN
GatedGCN
GIN
GPS
none
38.3 905.0=0..0
68.8#10.1
58.2+12.0
11.911.5
rand
110.0=0.00
253.0+0.00
95.0+116.1
LapPE
46. 16.5
47.4#7.6
33.2+3.3
14.1#1.8
RWSE
20.6+-2.2
26.4+:2.5
21.4+
2.7+0.3
AlIPSE
13.4
18.7=1.77
18.9
2.640.2
Table 13: Using GPSE+ on ZINC-12K6 significantly reduces the number of epochs needed to reach the same test performance as other PSEs. This table shows the factor of speedup (in terms of epochs) of GPSE+ reach the same MAE on ZINC-12K on various downstream GNNs and PSEs. For instance, mcans GPSE+ reaches the same performance with only half of the epochs.
PSE4 Downstream->
GCN
GatedGCN
GTN
GPS
68.9+13.5
66.1+12.7
56.9+10.2
11.6+1.3
905.0:10.0
110.0::..0
227.7:150.6
84.4117.2
LapPE
46.1
45.8
33.7
13.7+1.6
RWSE AUIPE
20.6++3.7
29.8+3.11
20.4++.0
2.8+0.4
13.0#2.2
21.1
18.742.5
2.6+0.2
Table 14: GPSE variants do not actually converge faster than other methods in optimal performance. This table shows the epoch on which early stopping stopped according to MAE on ZINC-12k on various downstream GNNs and PSEs.
PSEJ Downstream->
GCN
GatedGCN
GIN
GPS
none rand
$27.71:2014
591.2=348.4
863.84221.9
1304.9:311.5
667.11:219.9
189.7=114.9
386.542006.0
167.0+334.4
LapPE
669.9--239.2
628.6=256.8
838.3+108.1
1070.3#466.2
RWSE
934.5++
410.3 281.1
630.7++255.5
1373.2+
AIlPSE
715.7+169..6
425.7=252.0
506.44316.9
1543.8
GPSE
935.7+66.99
803.9-163.1
919.2+55.2
1238.2+224.
GPSE-
939. 139.14668.4 68.4
875.5 108.4
933.9112.4
1497.5+244.6
GPSE+
934.1 +4..0
357.0=171.5
910.8+119.4
1426.4+166.6
Table 15: No clear improvements be for GPSE the MolNet datasets with regard to the number of epochs needed to reach the same test performance other PSEs. This table shows the factor of speedup (in terms of epochs) of GPSE to reach the same AUC on various MolNet datascts and PSEs. For instance, means GPSE reaches the same performance with only half of the epochs. The exponent indicates the number of seeds for which GPSE achieved a better performance than the respective PSE. inf indicates that there is no seed for which GPSE outperforms the baseline PSE.
PSE Dataset-+
BACE
BBBP ClinTox HIV MUV
SIDER
Tox21
ToxCast
GraphLog
inf inf
inf inf
inf
4.2+1..510
1.2-:0.13 inf
2.1 inf inf inf
LapPE
17.8
inf inf inf
inf 1.
RWSE
20.6+22210
inf inf inf
inf
6.34+0.710
inf
AIIPSE
3.9+0.7100 inf
inf inf
0.9+-0.1
2.6+0.38
inf
27

---

Published in Transactions on Machine Learning Research (02/2025)
Table 16: GPSE and its variants always perform better than other PSEs regardless the backbone on ZINC-12k. In only one case, that is, using the GPS backbone, AllPSE performs only insignificantly worse than the GPSE variants. This table shows the test MAE (L) on ZINC-12k for various backbone networks and PSEs.
PSE 4 Downstream->
GCN
GatedGCN
GIN
GPS
none
0.289=00.008
0.244#0.011
0.278
0.123#0.01
rand
1.255-+0.027
1.221 1.0088
1.242:100015
0.87+10.014
LapPE
0.218=00.00%
0.18910.007
0.217=0.005
0.141
RWSE
0.177=0.000
0.165
0.175=0.005
0.075=t0.005
AlIPSE
0.152=0.000
0.142=0.005
0.15#0.004
0.071#0.009
GPSE
0.000-
0.112+0.003
0.127+0.003
0.07++0.005
GPSE
0.128 0.003
0.114+0.003
0.129
0.067+0.004
GPSE+
0.127=00002
0.113=0.002
0.128=0.002
0.066=0.0033
Table 17: GPSE or one of its variants frequently perform best or only insignificantly worse than other PSEs. This table shows the test AUROC(1) on MolNet datasets for different PSEs, with a GINE downstream network.
PSE 4 Datasct
BACE
BBBP
ClinTox
HIV
MUV
SIDER
Tox21
ToxCast
GraphLog
82.6+1.6
66.8+2.1
73.4+3.9
75.0+2.0
74.9+133
60.6+0.8
73.4+0.9
63.0=0.8
LapPE
78.112.6
6..7.12.8
75.412.8
76.2.1.5
75.011.2
60.710..
77.410.4
64.5.0..7
RWSE
81.4+2.2
66.3+2.0
73.4+4.0
78.6+1.0
77.1+0.9
59.2+0.8
76.0+0.7
63.9-0.55
AlIPSE
77.9122.8
66.810.7
72.023.5
74.7111.7
66.910.5
62.911.3
76.010.6
64.11004
GPSE
83.1+1.6
6..3+1.0
76.7+44.6
76.142.1
75.3+0.88
62.7+112
77.2+0.6
65.9+0.7
GPSE-
81.611.2
67.6111.
7..5
76.741.9
76,2+1.7
62.241.4
77.510.9
65.7-0.6
GPSE+
20.012..3
67.3
76.7-1244
77.54114
76.0
61.641.66
77.2.10.6
66.0.1..6 0.6
for smaller fraction of available training data, all PSEs overtake GPSE in performance. Tox21 is notably another good example of GPSE, as the difference in performance grows for smaller training data ratio. In combination, these figures indicate that GPSE's performance in a data-scarce regime depends on the dataset in question, even though GPSE better than other PSEs in most cases.
Generalization of PSEs
Here we show the test performance relation to Table 3 and Table As already shown in Cantürk et al. (2024), Table 16 and Table show the lest performance of various PSEs against. various downst ream backbones (on ZIN CINC-12k showing MAE) and various MolNet datasets (showing AUROC), Notably, GPSE only insignificantly
and its variants perform very well and usually either have the bost performance worse than the best performance. Notably, for only 3 datasets (BACE, HIV, and MUV), some GPSE variants don't 't belong to the best performers.
28

---

Published in Transactions on Machine Learning Research (02/2025)
BACE (GINE)
Difference in performance Methed to GPSE
BBBP (GINE)
Difference in performance Method to Difference in performance Method to performancc Method to
0.10
0.05
0.00
0.00
GraphLog
GraphLog
-0.05
LapPE
-0.02
LapPE
0.10
RWSE
AJIPS
-0.04
AlPSSE
RWSE
-0.15
GPSE-
GPSE+
-0.06
GPSE
-0.20
-0.08
0.0125
0.025
0.05
0.1
0.2
0.8
0.0125
0.025
0.05
0.1
0.2
0.4
0.8
Training data ratio of all available data
Training data ratio of all avaliable data
Cli (GINE)
Difference performance Method to GPSE
HIV (GINE)
0.05
0.05
0.00
-0.05
GraphLog
GraphLog
tapPE
LapPE
RWSE
RWSE
AIPSS
ANPSSE
GPSE+
GPSE-
0.20
GASE
0.0125
0.025
0.05
0.1
0.2
0.4
0.8
0.0125
0.025
0.05
0.1
0.2
0.4
0.8
Training data ratio all available data
Training data ratio of available data
MUV (GINE)
Difference performance Method to GPSE
SIDER (GINE)
0.100
GraphLog
LapPE
0.075
0.050
0.02
AIPSE
GPSE.
0.025
GPSE:
0.000
GraphLog LapRE
0.00
GRS6
RISSE
AIISSE
0.075
GPSE+
GPSE
-0100
0.0125
0.025
0.05
0.1
0.2
0.4
0.8
0.0125
0.025
0.05
0.1
0.2
0.4
0.8
Training data ratio all available data
Training data ratio of available data
perforancc Method GPSE
Tox21 (GINE)
Difference in performance Method GPSE
ToxCast (GINE)
GraphLog
0.02
LapPE
AlIPSE
GPSE-
GraphLog
GPSE
LapPE
-0.06
RWSE
AIPSE
GPSE
-0.10
GPSE
0.0125
0.025 0.05
0.1
0.2
0.4
0.8
0.0125
0.025 0.05
0.1
0.2
0.4
0.8
Training data ratio all available data
Training data ratio available data
Figure 3: In most cases, GPSE variants outperform other PSEs regardless of available training data the MolNet datasets. There are, however, also examples where GPSE is outperformed by other PSEs for less available training data. Results on additional datasets beyond what is shown in Fig. 2 Downstream training with fractions of the MolNet datasets. We show the difference performance (AUROC t) obtained by various PSEs, including GPSE and GPSE+.
29


Reviews:
[{"review_id": "XhhIyGLpc5", "reviewer": "Reviewer_qSbh", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n\n1. The article addresses a critical challenge in machine learning on graphs, effectively linking advancements in GNNs with the emerging concept of Graph Foundation Models (GFMs).\n2. It provides a thorough evaluation of GPSE and its variants (GPSE+, GPSE−) across both synthetic and real-world datasets, offering valuable insights into scalability and generalization.\n\n**Weaknesses**\n1. The article is somewhat difficult to follow for non-expert readers, as it requires frequent back-and-forth reference between the main text and the supplementary materials.\n2. Some decisions are not well motivated in the text.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The article explores the role of positional and structural encodings (PSEs) in Graph Neural Networks (GNNs) and their potential as foundational components for graph-based tasks. Building on the recently proposed GPSE model, the authors introduce and analyze two variants, GPSE+ and GPSE−. The study focuses on three key aspects: expressivity, scalability with varying sample sizes, and generalization performance across diverse datasets.\n\nWhile the article is of fundamental interest to the community I found the read a bit complex, overall I would suggest clarifying some aspects defined bellow.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. It is unclear why only 4-regular graphs are used in GPSE+. While the choice of the number of nodes aligns with the average graph size in the MolPCBA dataset, there are many WL-indistinguishable sets of graphs. Why were 4-regular graphs specifically chosen?\n2. The article relies heavily on the GPSE model. I suggest providing a more detailed explanation of it in the main text, rather than relegating it to the supplementary material.\n3. Several key concepts (e.g., LapPE, AllPSE) are explained only in the supplementary material. It would be helpful to include brief explanations of these in the main text for better clarity.\n4. Could you clarify the \"mild assumptions\" referenced in Theorem 1? Providing explicit details would make the theorem easier to understand.\n5. Tables and figures are positioned far from the text that discusses them (e.g., Table 1, Figure 1), making the paper harder to follow. Consider reorganizing to improve readability.", "broader_impact_concerns": "No concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "D28drpgK5e", "reviewer": "Reviewer_tBaA", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n\n- The paper is generally well-written.\n- The role of PSEs for graph foundation models is underexplored, and it is good to see that people are working on this.\n- The authors take a deeper dive compared to the original paper regarding GPSE's empirical performance and expressivity.\n\n**Weaknesses**\n- The theoretical contributions are rather modest. For instance, Theorem 1 and the discussion after it largely builds off of [1] and [2], and the points made essentially boil down to:\n\n1. GPSE is built on GatedGCN -> GIN can simulate 1-WL [1], and GatedGCN can simulate GIN -> GPSE can simulate 1-WL\n\n2. GPSE uses RNFs -> with sufficiently many layers of sufficient width, an MPNN with RNFs can compute any graph structure function [2] -> sufficiently wide and deep GPSE can compute any graph structure function\n\nFrom this perspective, if I'm understanding correctly, 1. seems redundant if you have 2.\n\n- It's not entirely clear to me why Theorem 2 implies that a random variable is required as output. More general and intuitive discussion as to why graphs A and B are 1-WL indistinguishable and why that's significant for PEs in general would be helpful.\n\n- Organizationally, this work reads a bit disjointed, like two smaller works combined. One part studies the expressivity of GPSE while the other studies the generalizability of GPSE with little discussion bridging the two topics. As the paper admits, they do not seek to conflate expressivity and generalization, but elucidating the relationship between the two for GPSE seems to be the most natural step in tying together all of the paper's main contributions. This does not hurt correctness, and the paper seems relatively modest about what it claims, but I think it does detract from its overall quality.\n\n[1] Xu et al. How Powerful are Graph Neural Networks? ICLR 2019.\n\n[2] Franks et al. A systematic approach to universal random features in graph neural networks. TMLR, 2023.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors examine GPSE and its generalization abilities in the context of graph foundation models. They also discuss the expressivity of GPSE and how it may affect the expressivity of downstream models. This work showcases comprehensive experiments examining GPSE's expressivity, convergence time, and generalization error. They also provide a more robust version of GPSE, GPSE+, which adds relevant \"hard\" graphs to GPSE's pre-training stage.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Besides, addressing the above weaknesses, here are some requested changes.\n\n- There is some missing discussion of [1]'s study on using biconnectivity to evaluate GNN expressivity.\n- Can the authors include some discussion of the significance of GPSE, GPSE^+, and GPSE^-'s performance and it means for GFM practitioners in the wild? It's difficult to find a concrete take-home message for PSEs for GFMs from these empirical studies. Also, it seems counterintuitive for GPSE^- to perform better than its more expressive variants on TRIX.\n\n[1] Zhang et al. Rethinking the Expressive Power of GNNs via Graph Biconnectivity. ICLR 2023.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "iYvEFbZJ9z", "reviewer": "Reviewer_zGyi", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n1. This work studies theoretical expressivity of GPSE.\n2. This work performs various experiments on GPSE, focusing on its convergence speed or generalization ability.\n3. This work introduces variants of GPSE, which improve the practical applicability of the method.\n\nWeaknesses/questions\n1. Since this work studies GPSE as the main target, there should be more insights on why GPSE is worth studying. To my understanding, GPSE is just a GNN trained to mimic PSEs, and I’m not convinced why we should use GPSE instead of the original PSEs despite its higher computational cost.\n2. Theorem 1 is an important contribution, but being able to approximate GIN is different from being able to compute “any” PSEs. There should be comprehensive analysis on the expressivity of PSEs to make such a claim, e.g., whether all PSEs can be approximated by GIN or not.\n3. The term “downstream universality” is not well defined. Test performance is often not alined with theoretical expressivity, and that is natural. The authors show in Table 1 actual performances of models on various datasets, but they may not be an appropriate way to report the expressivity of encodings for downstream tasks.\n4. Related to W1, I’m not sure why GPSE is able to achieve faster convergence (in Table 2) if they are trained to mimic PSEs. Is it because they work as a smooth approximator that helps models get better signals of the graph structure? More intuitions would be helpful.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "Recent advances in integrating positional and structural encodings (PSEs) into graph neural networks (GNNs) have significantly enhanced their performance across various graph learning tasks. However, the general applicability of these encodings and their potential to serve as foundational representations for graphs remain uncertain. This paper investigates the fine-tuning efficiency, scalability with sample size, and generalization capability of learnable PSEs across diverse graph datasets.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please see the weaknesses above. I'm not an expert in this field, so detailed explanation/intuition would be helpful.", "broader_impact_concerns": "No concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper provides a thorough evaluation of GPSE and variants across multiple datasets, providing insights in terms of scalability and efficiency. This is a more in depth exploration of GPSE (compared to the original paper introducing it) and is accompanied by theoretical results on the expressivity of these embeddings. During the rebuttal period the authors answered the questions raised by the reviewers, and improved the write-up. All reviewers agreed that the quality of the paper improved, 
Given the thoroughness of the paper reviewers recommend accept, which I think reflects the scholarly character of the work.
Decision: Accept (poster)