Homomorphism Counts as Structural Encodings for Graph Learning
Authors: Linus Bao
Emily Jin
Michael M. Bronstein
Ismail Ilkan Ceylan
Matthias Lanzinger
Venue: ICLR 2025 Poster (2025)
Keywords: graph transformers
structural encodings
homomorphism counts
expressivity
Primary area: learning on graphs and other geometries & topologies

Abstract: Graph Transformers are popular neural networks that extend the well-known Transformer architecture to the graph domain. These architectures operate by applying self-attention on graph nodes and incorporating graph structure through the use of positional encodings (e.g., Laplacian positional encoding) or structural encodings (e.g., random-walk structural encoding). The quality of such encodings is critical, since they provide the necessary \emph{graph inductive biases} to condition the model on graph structure. In this work, we propose \emph{motif structural encoding} (MoSE) as a flexible and powerful structural encoding framework based on counting graph homomorphisms. Theoretically, we compare the expressive power of MoSE to random-walk structural encoding and relate both encodings to the expressive power of standard message passing neural networks. Empirically, we observe that MoSE outperforms other well-known positional and structural encodings across a range of architectures, and it achieves state-of-the-art performance on a widely studied molecular property prediction dataset.

Published as a conference paper at ICLR 2025
HOMOMORPHISM COUNTS AS STRUCTURAL ENCODINGS FOR GRAPH LEARNING
Linus Bao" University of Oxford
Emily Jin'
Michael Bronstein
University of Oxford
University of Oxford AITHYRA
ismail Ilaa Ceylan University of Oxford
Matthias Lanzinger
TU Wien
arXiv:2410.18676V2 [cs.LG] 2 Feb 2025
ABSTRACT
Graph Transformers are popular neural networks that extend the well-known Transformer architecture to the graph domain. These architectures operate by applying self-attention on graph nodes and incorporating graph structure through the use of positional encodings (e.g., Laplacian positional encoding) or structural encodings (e.g., random-walk structural encoding). The quality of such encodings is critical, since they provide the necessary graph inductive biases to condition the model on graph structure. In this work, we propose motif structural encoding (MoSE) as flexible and powerful structural encoding framework based counting graph homomorphisms. Theoretically, we compare the expressive power of MoSE random-walk structural encoding and relate both encodings to the expressive power of standard message passing neural networks. Empirically, we observe that MoSE outperforms other well-known positional and structural encodings across a range of architectures, and it achieves state-of-the-an performance on widely studied molecular property prediction dataset.
INTRODUCTION
Graph Neural Networks (GNNs) have been the prominent approach to graph machine learning in the last decade. Most conventional GNNs fall under the framework Message Passing Neural Networks (MPNNs), which incorporate graph structure - the so-called graph inductive bias in the learning and inference process by iteratively computing node-level representations using "messages" that are passed from neighboring nodes (Gilmer et al. (0077). More recently. Transformer architec- tures (Vaswani et al. 2017) have been applied to the graph domain and achieve impressive empirical performance (Rampásek et al. 2022 Ma et al. 2023 especially in molecular property prediction.
While MPNNs operate by exchanging messages between adjacent nodes a graph, Transformers can be seen special type of GNN that operates on complete graphs. On the one hand, this allows for direct communication between all node pairs in a graph, regardless of whether there exists edge between two nodes in the original input graph. On the other hand, since the node adjacency information is omitted, the Transformer lacks any "built-in" graph inductive bias. Instead, the underlying graph structure is usually provided by combining Transformer layers with local message-passing layers (Yun et al., 2019 Rampásek et al., [022 Bar-Shalom et al.) 2024) or by incorporating additional pre-computed features that encode the topological context each node. These additional features are referred to as positional or structural encodings. Common encodings include Laplacian positional encoding (LapPE) (Dwivedi et al.) (023) and random- walk structural encoding (RWSE) (Dwivedi et al. 2022a). The quality of these encodings are key ingredient in the success of Transformers on graphs (Dwivedi et al., 2022a Rampásek al. 2022).
Motivation. While empirical studies have observed the impact of structural or positional encodings on model performance (Dwivedi et al.) [2022a] RRamássek et al.) 2002). our theo- retical understanding of the expressive power of different encodings remains limited. This represents an important gap in the literature, especially since the expressive power of
"Equal contribution.

---

Published as a conference paper at ICLR 2025
Transformer-bsser architectures heavily rely the specific choice of the structural posi- tional encoding (Rosenbluth et al.) (024). Let us consider RWSE, which has been empiri- cally reported as the most successful encoding on molecular benchmarks (Rampásek et al.) 2022).
We now illustrate a serious limitation of RWSE in its power to distinguish nodes.
How Expressive RWSE? The expressive power of MPNNs is upper bounded by the I-dimensional Weisfeiler Leman graph isomorphism test (I- WL) (Xu et al., 2019; Morris et al., 2019). This means that the node invariants computed by
G
H
VI
U/2
MPNNs are at most as powerful as the node invari- ants computed by 1-WI. As result, an MPNN can distinguish two nodes only if 1-WL. can dis- tinguish them. Some MPNN architectures, such as Graph Isomorphism Networks (GIN) (Xu et al. 2019), can match this expressiveness bound and distinguish any pair of nodes that can be distin- guished by 1-WL. We relate the expressive power of RWSE to that of the Weisfeiler Leman hierarchy by proving that node invariants given by RWSE are strictly weaker than node invariants computed by 2-WL (Proposition/ 4.4 Additionally, RWSE node invariants are incomparable to node invari- ants computed by 1-WL (Proposition (.7). fact, there are simple node pairs which can be distin- guished by 1-WL but not by RWSE (and vice versa).
(a) The nodes dn and U2 (also, i1 and 02) can be distinguished by I-WL, but not by RWSE.
11
V/2
Dinitrile
Morpholine
(b) A molecule from the ZINC dataset, with Car- bon, Nitrogen, and Oxygen atoms. The nodes 4n and u2 are indistinguishable by RWSE and so are U1 and U2.
Figure RWSE is weaker than 1-WL in distin- guishing certain nodes (a), which holds for all choices of random walk length. This limitation is observed in real-world molecular graphs (b).
Example 1.1. Consider the nodes from the graphs G and H from Fi) Observe that the nodes W1 and u2 can be distinguished by 1-WL. Inter- estingly, however, they are indistinguishable RWSE for all lengths é of the considered random walk. This observation also applies to the nodes "1 and U22 Moreover, this limitation is not merely of theoretical interest, as readily applies to real-world molecules, where the use of RWSE is prominent. Figure [b) depicts molecule from the ZINC dataset, where the nodes #1 and U2 (also, 01 and 02) cannot be distinguished by RWSE although they can be distinguished by MPNNs. In practical terms, this implies that RWSE cannot distinguish key nodes in a Dinitrile group from those a Morpholine group.
A
Motif Structural Encoding as Flexible and Powerful Approach. In this paper, propose motif structural encoding (MoSE) as a method of leveraging homomorphism count vectors to capture graph structure. Homomorphism counts have been investigated in the context of MPNNs to overcome Jin et al. 2024) with promising theoretical and empirical findings (see Section 2). Building on the existing literature, show that MoSE is general, flcxible, and powerful alternative to existing positional and structural encoding schemes in the context of Transformers. In fact, show that unlike RWSE, MoSE cannot be strictly confined to one particular level of the WL hierarchy (Proposition 4.3) and MoSE can provide significant expressiveness gains exceeding that achieved by RWSE (Theorem 4.6).
well-known theoretical limitations their expressivity (Barceló et al. 2021 1
Example 1.2. Consider the graphs G' and H from running example, and observe that H/ has cycle of length six, while G has no cycles. The node-level homomorphism counts Hom..y O G) o Hom-pa ts
H) (defined formally in Section 4.2) provide sufficient information to distinguish the nodes U1 and U2. Analogous statements can also be made for in and u2.
A
Contributions. Our key contributions can be summarized as follows:
We introduce MoSE and detail the expressiveness guarantees that can be achieved by using homomorphism counts as a graph inductive bias (Section 4.1).
Throughout the paper, we refer the folklore version of the WT. hierarchy Grroh & Otto 2015
2

---

Published as a conference paper at ICLR 2025
We compare MoSE to RWSE in terms of expressivity and relate them to the expressive power of MPNNs through the well-known WL hierarchy (Section 4.2).
We empirically validate our theoretical findings and demonstrate the efficacy of MoSE on a variety of real-world and synthetic benchmarks. We report consistent performance gains over existing encoding types and achieve state-of-the-ar results on the ZINC molecular benchmark (Section 5).
2 RELATED WORK
(Graph) Transformers and Encodings, Vaswani et al. (0117) first highlighted the power of self- attention when they introduced their Transformer architecture. Dwivedi & Bresson (220)) generalized the concepts presented in Vaswani et al. (2017) to the graph domain. In recent years, several different Graph Transformer architectures have arisen. Yun et al. (2019) first combined message-passing layers with Transformer layers, and other models have followed this approach (Rampásek et al., [022] Bar-Shalom et al. 2024; Shirzad et al., 2023). Relatedly, Transformer architectures dedicated to knowledge graphs have also been developed (Zhang et al. 2023c; Liu et al. 2022). [hehhadd et al. 20244 present a survey of existing Graph Transformer models and how they compare to each other.
A key component in the success of Graph Transformer models is the of effective graph inductive biases (Dwivedi et al. 2022a).
Dwivedi & Bresson (2020), Laplacian positional encodings (LapPE), which were introduced by a popular choice, but they break invariancd" as they are dependent on an arbitrary choice of eigenvector sign and basis (Lim et al. 2023b a). RRampasek et al. (2022) present framework for building general, powerful, and scalable Graph Transformer models, and they perform ablations with a suite of different encoding types, promoting the use of random-walk structural encoding (RWSE) on molecules. Ying et al. (202I) introduced Graphormer, which uses an attention mechanism based on shortest-palt path (and related) distances in graph. Ma et al. (2023) present GRIT as a novel Graph Transformer that relies solely on relative random walk probabilities (RRWPs) for its graph inductive bias.
Expressive power of GNNs MPNNs capture the vast majority of GNNs (Gilmer et al. 2017 and their expressive power is upper bounded by 1-WI. (Xu et al., 2019, Morris et al. 2019) This limitation has motivated a large body of work, including higher-order GNN architectures (Morris al.] 2019: Maron et al. 2019a b Keriven & Peyré. 2019), GNNs with unique node features (Loukas 2020), and GNNs with random features (Sato et al. 202T; Abbouud et al. (02T), to achieve higher expressive power. The expressivity of GNNs has also been evaluated in terms of their ability to detect graph components, such as biconnected components (Zhang et al. 2023b), and in terms of universal approximation permutation invariant functions (Chen al. 2019). Fully expressive architectures have been designed for special graph classes, e.g., for planar graphs (Diiirrov et al.) 2023).
Our work is most closely related to approaches that design more expressive architectures by injecting the counts of certain substructures, widely referred to as motifs. Bouriitaa et al. (2023) present an early work that enhances node feature encodings for GNNs by counting subgraph isomorphisms for relevant patterns. [Barcel et al. (202T) follow up on this work by proposing to instead count the number of homomorphism from set of pertinent substructures. Several other works have identified homomorphism counts as a key tool for understanding the expressive power of MPNNs (Neuen
2023 Lanzinger& & Barceló, 2024, Wang & Zhang 2024). ZZhang et al. (202)) also recently proposed a new framework that characterizes the expressiveness of GNNs in terms of homomorphism counts. Through tight connections between counting homomorphisms and counting (induced) subgraphs CCurticapean et al.) 2017 Bressan et al. 2023 Roth & Schmitt 2020), these expressiveness results can be lifted to a wide range of functions (Lanzinger & Barceló] As such, Jin et al. (2024) built upon these theoretical observations to establish a general framework for using homomorphism counts in MPNNs. In particular, they show that homomorphism counts that capture certain "bases" of graph mappings provide a theoretically well-founded approach enhance the expressivity of GNNs. Maehara & N 2024) reiterate the benefits of using homomorphism in GNNs.
By sacrificing invariance, it becomes much easier to design very expressive architectures. In fact, Graph Transformer architectures with LapPE: are universal (Krewzer et al.] 2021). but so is 2-layer MI.P and single-layer GNN using LapPE (see Proposition 3.1 of Rosenbluth (2024)
3

---

Published as a conference paper at ICLR 2025
3 PRELIMINARIES
Graphs and Homomorphism Counts. An undirected graph is set of nodes V(G) and set of edges E(G) _ V(G) x V(G) which satisfy symmetry: (u, E E(G) if and only if (v, u) E B(G). Unless otherwise stated, we take all graphs to be finite, and we take all graphs to be simple: (v, v) & B(G) for all v E V(G) and there exists at most one edge (up to edge symmetry) between any pair of nodes. We describe nodes u, u V adjacent if (u, v) E(G). The set of all nodes adjacent to v E (G) is the neighborhood of v, notated (v)). The number of neighboring nodes [V()) is the degree of e, notated d(v).
A homomorphism from graph G to graph H is function f : VGG) + V(H) such that (u, v) E E(G) implies (f()), f(u)) E E(H). We say homomorphism is isomorphism if the function f is bijective, and if it additionally satisfies (u, v) E E(G) if and only if f(U)) E E(H). In this case, we describe the graphs G and H as being isomorphic, denoted G = H. We write Hom H) for the number of homomorphisms from G to H. If we restrict to counting only homomorphisms which map a particular node g V(G) to the node h V(H), we denote this rooted homomorphism count as Homy-n (G, H). Sometimes the choice of is unimportant, so we use Hom-, (G, H) to notate the rooted homomorphism count Homg-i (G. H) where I can be fixed as any arbitrary node in V(G). We use Hom(G: G, -) to denote the function which maps any graph H to the integer Hom H), and we define rooted homomorphism count mappings analogously. If G a collection of graphs, then we treat Hom(G, -) function that maps any input graph H to the ordered tuple (or integer vector) defined as Hom(g, (G H)- = (Hom(G. (G, H))e,, and analogously for rooted counts.
Curticapean et al. 2017) describe graph motif parameters as functions r(.) that map graphs into Q such that there exists a basis of graphs Supp(T)= = {E) and corresponding coefficients {ax S (u{O} which decompose I as a finite linear combination r(-) Ei= a; Hom F,, -). Given G, the function which maps any H to the number of times that G appears as a subgrapt of H is graph motif parameter (Lovász, 2012) whose basis is known as Spasm(G). Many mappings of interest can be described as graph motif parameters, so the theory of such bases bolsters homomorphism counts as broadly informative and powerful (Jin et al. 2024).
Nguyen & Machara (2020) present generalization of homomorphism counts that allow for vertex weighting. For graph G, let w V(G) - 1220 describe node weights. The weighted homomorphism count from graph F into G is given as:
w-Hom (FG)
Σ JEH
II w((()) (EV(F)
where H is the set of all homomorphisms from F to G. We define the node-rooted version w-Homm.-e (F, G) by restricting H to only those homomorphisms which map u E VFF) to E V(G). defined analogously to the un-weighted case: the graph-node pair (G, u) gets mapped to w-Homm..o (F, G) where E V(F) is fixed arbitrarily. Setting (u)) 1 for all v E (G) recovers the un-weighted count w-Homm[F F, G) Hom( F, G). and similarly for the node-rooted version. Weighted homomorphism counts are well-studied in the context of their connection to graph isomorphism (Freedman et al. 2004 Cai & Govorov 2021). and in the context of the universal approximation capabilities and empirical performance of graph classifiers which use w-Homm(,, -) counts as graph embedding (Nguyen & Machara (020).
The mapping (,,
Expressive Power. A graph invariant is a function {(-) which acts on graphs, satisfying {(G) = {(H) whenever G = H for all graphs G and H. For indexed families of graph invariants {A, and (B, be., we define the expressivity relation A to denote: for any choice of I, there exists choice of E J such that (G) B, (H) implies that A.(G)
A.) for all G and H. If A < B and B 3 A, then we say that A ~ B. We write < B when B has strictly greater expressive power, A = B but A 7 B. When we reference - for some fixed graph invariant E(-). we interpret & as a family which contains only one graph invariant (hence the indexing is trivial).
IIf the graphs in G are ordered initially, we arbitrarily fix some indexnng of the elements in & so that they become ordered.
'We count the number of times one can find graph H'' with V(H') C V(H) and F.(T') C E(H) such that G x H'
4

---

Published as a conference paper at ICLR 2025
Noting that GNN architecture can be treated as a family of graph invariants indexed by the model weights, the relation 3 generalises common notions of the graph-distinguishabiii for GNNs (Zhang et al. 2023a). As we will see in Section [ the 3't relation naturally extends to expressivity comparisons between structural/posiiiioaal encoding schemes as well.
expressive power
MPNNs and Weisfeiler--Lhhman Tests. Given graph G, the 1-WL test induces the node coloring e()); VVG) - E for all i up until some termination step T, at which point the graph-level I-WL label is defined the multiset of final node colors I-WL(G) f(( (v) E V(G) Graphs G and H are considered I-WL indistinguishable if they have identical graph labels I-WL(G) = I-WL(HH) Crucially, it holds that MPNN N 1-WL where we treat "MPNN" as family of graph invariants indexed by both the choice of pesssae-paasiigg architecture and the model parameters, and we treat 1-WL as a singleton family containing only the graph invariant G + I-WL(G) (Xu et al. 2019).
We extend the Weisfeiler-Lehmat test to "higher dimensions" by coloring k-tuples of nodes. The k-WL test induces node tuple coloring elt) : VVG)* + Σ for f = 1,... T iterations, and then aggregates a final graph-level k-WL label analogously to 1-WL (Huang & Villar 2021). In this work, we refer to the folklore k- WL. test, which is provably equivalent to the alternative oblivious k-WL formulation up to re-indexing of k (Grohe & Otto 2015). It has been shown that the k-WL tests form a well-ordered hierarchy of expressive power, where k-WL < (k + 1)- (Cai et al. 1989). Here, treat k-WL singleton family (trivial indexing) for each particular choice of k.
Self-Attention and Positional/Structural Encoding. Central to any Transformer architecture is the self-attention mechanism. When applied graphs, single "head" of self-attention learns a t -layer hidden representation h E Rd of every node v E V(G) by taking the weighted sum (A) = ( alfuhh ((-))) where the attention coefficients are 0 evitt) (n!"")) h (
(t)
functions. The most common implementation of ((4) and e)((t) scaled dot product attention, as defined by Vaswani et al. (007)): although some Transformers such as GRIT (Ma al. (2023) deviate from this. In most Transformers, utilize multiple attention heads in parallel (whose outputs are concatenated at each layer), and we interweave self-attention layers with fully-connected feed-forward layers.
Here, (f and 2b(t)) are
Since basic self-attention does not receive the adjacency matrix as an input, many Graph Transformer models choose inject a graph's s structural information into the model inputs by way of node dositional/structuur encoding. For example, the widely used k-length random walk structural encoding (RWSE&) assigns to each node its corresponding diagonal entry of the degree normalized adjacency matrix (D-1A)* for all powers i = 1,... & (Rampásek et al. 2022 Dwivedi et al. 2022a Ma et al. 2023). Each node's RWSE; vector then concatenated or added to the node's initial feature vector and the resulting node embedding is passed into the Transformer as an input. More broadly,
we can define node positional or structural encoding to mean any isomorphism-invee -nvarraan mapping pe which takes in mode-graph pair (v. G) and outputs vector label pe(t, G) Rd. Then, the graph-level PE label is defined as the multiset of node-level labels PE(G) = (peee, G):u V(G) }-
In this way, can treat RWSE, family of graph invariants (mapping into multisets with elements in IRd) indexed by k. Hence, we can compare the graph-level expressivity of RWSE, and any other general positiinal//sruuuuuall encoding scheme PE under
4 HOMOMORPHISM COUNTS AS A GRAPH INDUCTIVE BIAS
In this section, we formally define motif structural encoding (MoSE). Just with other node-level structural or positional encodings, MoSE provides a way to encode the structural characteristics of a node in terms of numerical vector. Such encodings then provide graph inductive bias to models, such as Transformers, that cannot (or only in a limited fashion) take graph structure into account. All proof details are provided in Appendix A
$ 'eere notates the diagonal degree matrix, and A the adjacency matrix. 'Sometimes, the initial node feature and the RWSE vector are passed through ML.Ps before being combined and fed into the GNN.
5

---

Published as a conference paper at ICLR 2025
4.1 MOTIF STRUCTURAL ENCODING (MoSE)
The motif structural encoding (MoSE) scheme is parameterized by a choice of initeppatter graph family 9 = (G,,..., Ga), as well as a choice of node weighting scheme w which sends any (v, H) to a non-negative weight (w, H) E Rgo. For each node v of graph H, the node-level MoSEg, label of v is:
MoSEg (v, H) w-Homm.. (G,, H)
ER"
(I)
i=1
We will notate eg. :- MoSEg (v, H) for shorthand when w and H are either clear from context, or any arbitrary choice can be made. Unless otherwise specified, we use the constant w weighting which sends all nodes in all graphs to 1, aligning MoSEg,, with the un-weighted homomorphism counts used in previous works (Jin et al.] 2024; Barceló et al.) 2021). In this case, we omit w from our notation, using MoSEg to denote our encoding. When reference MoSEg, - at the graph-level, mean the multiset of node-labels MoSEg. (H)- {ef u V(H) }. It holds that .o is a graph invariant because for any two graphs H and F with isomorphism L. : V(H) - V(F), we have ege = - ((w)
for every vertex U E V(H) (Nguyen & Machara 2020).
MoSE offers a highly general and flexible approach to structural encoding on account of two key parameters: the graphs G and the vertex weight function w. Both of these parameters can be adapted to fit the problem domain and the model architecture as desired. The choice of G can be informed in precise terms by desired levels of expressiveness as shown below in Proposition [.3 Furthermore, the choice of G can build on range of empirical studies on structural information in MPNNs (Barceló) (tt al. 2021; Jin et al., 2024 Wang & ZZhang 2024] [Bouritsas et al., 2023). Additional choice of a non-trivial weight function adds further power and flexibility. In particular, we show that even simple weight function that maps nodes to the reciprocal of their degree is enough to exactly express RWSE in terms of MoSE (Proposition 4.5)
In the following, we will provide insight into the expressivity of MoSE by leveraging established connections between homomorphism counts and MPNNs. For Transformer architectures, similar frameworks of expressivity are not yet established. Recent work by |Rosenbluth et al. (2024) shows that Transformer architectures do not inherently contribute expressivity, and that positional//truccurall encoding is instead the key ingredient of their expressivity. We therefore study the expressivity of the encodings themselves, which in turn translates to the expressivity of models that utilize- and heavily depend on these encodings. In particular, any typical Graph Transformer architecture with MoSE will naturally be at least as expressive as MOSE and thus inherit all lower bounds from our analysis.
Our first two propositions establish that MoSE is, in sense, incomparable to the WL-hierarchy, For every fixed set of graphs & that induces an encoding, we can provide an upper bound in terms of k-WL for some k dependent on G. At the same time, given any fixed choice of k. the expressiveness of even MoSE encodings induced by a single pattern graph cannot be confined to the expressive power of k- (Proposition 4.2).
Proposition 4.1. Let G be a finite set of graphs and let i be the maximum treewidth of graph in G. Then, MoSEg is at most as distinguishing as k-W That is, MoSEg = k-
Although we cannot distinguish all graphs distinguished by k-WL using MoSEg with a finite G, we can distinguish any particular pair of graphs distinguished by k-WL. In fact, we only need a single graph in & in order to do this.
Proposition 4.2. For k 2 1, let G and H be two non-isomorphic graphs that are equivalent under k-WL. Then, there exists graph F such that MoSE{F) distinguishes G and H.
Lanzinger & Barceló (024) and Jin et al. (2024) studied the expressivity of MPNNs with respect to functions that map graphs to numbers. For a large class of these graph motif parameters, the distinguishing power of such a function relates closely to homomorphism counts from its homomor- phism basis (Jin et al., (2024). Building on these results, we establish very broad lower bound for MoSE-enhanced Transformers while also providing a practical method for selecting G.
Proposition 4.3. Let f be graph motif parameter with basis 93 S G. Then MoSEg is at least as distinguishing as f. That is, if F is the family of all graph motif parameters, we have F A MOSE
We require that G be a finite set, and that each graph within G have finite size.
With respect to the definition of <, both sides in this case represent singleton families of graph invariants.

---

Published as a conference paper at ICLR 2025
SW
MoSE
RWSE
MUSE
0.1666
0,0555
12
0.8555
12
0J0749
0.0617
0.8617
0.0637
450
0.8637
450
Figure 2: The x Rook's ' Graph (left) and the Shrikhande Graph (right) are non-isomorphic strongly regular graphs that have the regularity parameters. RWSE produces the same vector every vertex of both graphs whereas a simple construction of MoSE using Spasm(Cr) U Spaam homomorphism counts easily distinguishes the two graphs.
4.2 COMPARING THE EXPRESSIVITY OF MOSE TO RWSE
From above we see that MoSE is closely aligned to the k-WL hierarchy, and we can use this possible to entirely contain MoSE within the WL hierarchy. In the following, we show that this is not the case for RWSE. In fact, the expressiveness of RWSE, regardless of length parameter, is fully contained within 2-WL.
alignment to inform the choice of However,
Proposition 4.4. For every & 2 2, any graph which can be distinguished by RWSE can be distin- guished by 2- WL. That is, RWSE 2-WL.
This in itself has wide-ranging consequences. For instance, is known that 2- 2-WL cannot distinguish strongly regular graphs (Fuhlbrück et al. (021). and therefore neither can RWSE, For MoSE, there exist no such limitations (Figure 2) beyond those dependent on the choice of g (Proposition 4.1
While MoSE cannot fully capture 2-WL, it is in fact possible to express RWSE, for every E> 2 as special case of MoSE. contrast to previous results, our result here requires a node-weighting scheme that is not constant. However, even straightforward node-weighting by degrees which comes no cost practice is enough for our proof. Letting G consist of cycle graphs with size at most l gives the desired result (see Appendix A for details).
Proposition 4.5. For any E N, there exists a finite family of graphs G and weighting scheme such that the node-level ( H) label is uniquely determined by MoSEg,w w (v, H) for all v and H. In fact, RWSE, is simply the special case of MoSEg,,, where w + 1/d(r) and G = {C.)e
Proposition 4.5 immediately shows that RWSE < MoSE, and the example from Figure demonstrates that this inclusion is in fact strict.
Theorem 4.6. Motif structural encoding is strictly more expressive than random walk structural encoding: RWSE - MoSE
Finally, we note that on the node-level, there are even cases where RWSE is weaker than 1-WL. Specifically, there are nodes for which 1-WL assigns different labels, but RWSE, assigns the same label for every [ There are also, of course, instances in the other way around.
Proposition 4.7. RWSE is incomparable to 1-WL in terms of node-level expressiveness.
5 EXPERIMENTS
In this section, empirically demonstrate the efficacy of MoSE several real-world and synthetic datasets across a range of models. Full experimental details and additional results are presented in Appendix B Time and complexity details for computing MoSE encodings are in Appendix B.
7

---

Published as a conference paper at ICLR 2025
Table 1: Performance of different positional (PE) and structural (SE) encoding types with the GPS
model. MoSE consistently outperforms other encodings at relatively low computational cost.
ZINC-12K
PCQM4My2-subsel
CIFARIO
Encoding
PE/SE
MAE
MAE +
Acc. f
none
0.113
0.1355
71.49#0.19
PEG
PE
#0.006
0.1209+0.000 0003
72.10=0.46
LapPE
PE
0.116#0.000
0.1201 +0 0003
70.31
SignNet MLP
PE
0.090#0.007
0.1158 00.000
71.74=10.00
SignNetDeepSetts DeepSets
PE
0.079 006
0.1144 0002
72.37=0.34
RWSE MoSE (ours)
SE
0.070 002
0.1159+0 0004
71.96=0.40
SE
0.062 0.0002
0.1133
73.50
Table 2: We report mean absolute error (MAE) for graph regression on ZINC-12K (with edge features) across several models. MoSE yields substantial improvements over RWSE for every architecture.
Table 3: We achieve SOTA on ZINC- by replacing the random walk encoding from GRIT with MoSE. MP denotes if the model performs local message passing.
Model
Encoding Type
Model
MAE +
MP
none
RWSE
MoSE (ours)
GSN
0.101 #0.010
CIN
0.079
MLP-E
0.606#0.002
0.361#0.011 #0.010
0.347 00.003
GPS
0.070=0.002
GIN-E
0.243
0.122 003
0.118=0.007
Subgraphormer++EE
0,063
GIN-E+VN
0.151:10.006
0.085 00003
0.068
GT-E
0.195
GT-E GPS
0.195
0.104:10.025
0.089
GRIT+RRWP
0.059 10.002
0.11940.011
0.06940.001
0.062#0.002
GRIT+MoSE (ours)
0.056
5.1
COMPARING MOSE TO OTHER ENCODINGS
We begin by extending the positional and structural encoding analysis from GPS (Rampásek et al. 2022) to include MoSE. We evaluate MPS+MoSE on three different benchmarking datasets, including ZINC (Irwin et al., 2012 Dwivedi et al. 2023), PCQM4Mv2 (Hu et al., [202T). and CIFARIO Krizhevsky et al. 2009 Dwivedi et al.) 2023). ZINC and PCQM4Mv2 are both molecular datasets, whereas CIFAR 10 is an image classification dataset. Following the protocol from Rampásek et al. (2022), we use a subset the PCQM4My2 dataset.
Experimental Setup. For ZINC, construct MoSEg using G = Spasm (C) U Spasm Ca) in accordance with Jin et al. (2024). For the PCQM4Mv2-suloe and CIFAR 10 datasets, we take G to be the set of all connected graphs with most 5 nodes. Details for all other encodings described by |Rampásek et al. (2022).
Results. Our results are presented in Table I The reported baselines for all encodings except MoSE are taken from Rampásek et al. 2022). We see that MoSE consistently outperforms other encoding types, including a number of spectral methods. When compared to RWSE, a prominent structural encoding, MoSE achieves over 10% relative improvement on ZINC. MoSE's strong performance on the CIFAR 10 image classification benchmark highlights its effectiveness beyond molecular datasets. Additional results for MoSE on the MNIST image classification dataset (Deng) 2012 Dwivedi et al.
2023) and the LRGB Peptides datasets are in Appendix B.5 and Appendix B.6 respectively.
5.2 GRAPH REGRESSION ON ZINC
As mentioned above, ZINC is molecular dataset that presents graph-level regression task. Follow- ing Dwivedi et al. 2023), we use subset of the ZINC dataset that contains 12,000 molecules, and we constrain all of our models to under 500k learnable parameters. We include the use of edge features in Table 2 referring readers to the appendix (Table [3) for results on ZINC without edge features. As before, construct MoSEg using G Spasm (7) Spasm(Cs) for all ZINC experiments.
8

---

Published as a conference paper at ICLR 2025
Table 4: We report MAE results for GPS with various feature enhancements the QM9 dataset. The best model is highlighted in red, the second best is blue, and the third best is olive.
Property
R-GIN
R-GIN+FA
R-SPN
E-BasePlanE
GPS
RWSE
MoSE (ours)
2.64
2.54
2.21=0.25
1.97=0.00
1.47
1.43+0.02
alpha
4.672
2.28+0.01
1.66=0.06
1.63#+0.01
1,52+0.27
1,48:t0.16
HOMO
1.42.00.01
1.2610.02
1.20
1.1510.01
0.911
0.9110.001
LUMO
1.50.10.09
1.34
1,20=0.06
1.06:10.02
0,90
0.86.10.01
gap
2.27+0.09
1.96+0.04
1,77=0.06
1.73++0.02
1.47
1.45++0.02
R2
15.63=1.40
12.61
10.63+1.01
10.53:20.55
6.11
6.22+0019
ZPVE
12.93
5.0340.36
2.58=0.13
10
2.63
2.43+0.27
UO
5.88+11.01
2.21+0.12
0.89=0.05
0.95
0.83
0,85+0.08
U
18.71+223.0
2.32+0.18
0,93=0.03
0.94#0.04
0.83
0.75+0.03
H
1.62.
2.2611011
0.92
0.92.1.004
0,8610.15
0.831.0.09
10.75
2.04.10.24
0.83
0.80
0.83
0.80.10.14
Cv
3.53
1.86+0.03
1.23=0.06
1,20++.00
0.25
1.02+0.04
Omega 1.05+0.11
0.80+0.04
0.52=0.02
0.45
0.39
0.38+0.01
Comparing MoSE to RWSE across Multiple Architectures. Because Rampásek al. (2022) find that RWSE performs best on molecular datasets, we provide a detailed comparison of MoSE and RWSE across range of architectures on ZINC. We select a baseline multi-layer perceptron (MLP-E), a simple self-attention Graph Transformer (GT-E), and GPS (Rampásek et al. 2022) for our models. Note that all models are adapted account for edge features (see Appendix [B2 for details). For reference, we include MPNN results from GIN-E and its virtual-node extension GIN-E+VN (Hu al. 2020 We follow Rampásek et benchmarks on ZINC.
2022) and use random-walk length for our RWSE
Results. MoSE consistently outperforms RWSE across all models in Table Even though the graphs in ZINC are relatively small and a random-walk length of 20 already traverses most of the graph, our experiments show that structural information provided by MoSE yields superior performance. also note that GIN-E+ VN becomes competitive with leading Graph Transformer models when using MoSE. This highlights the effectiveness of MoSE in supplementing the benefits of virtual nodes, an MPNN-enhancement aimed at capturing long- rangrange node interactions (Southern al. (025)..
Comparing MoSE to RRWP. GRIT (Ma et al. 2023) a recent Graph Transformer architecture that incorporates graph inductive biases without using message passing. GRIT utilizes relative random walk positional encodings (RRWP) at both the node representation level as well as the node-pair formulation, GRIT+MoSE,
representation level. node and node-pair representations, and replace them with MoSE encodings at the node level.
remove all RRWP encodings for both the
Results. Using MoSE in conjunction with the GRIT architecture (Ma et al. 2023) yields state- of-the-art results on ZINC, as detailed in Table 3 Recall that we substituted MoSE for RRWP only the node level, completely omitting pairwise encodings. This suggests that even without explicit node-pair encodings, the relevant structural information captured by MoSE still surpasses that of RRWP. This especially interesting given that GRIT is intentionally designed to exploit the information provided by RRWP, insofar that Ma et al. (023) present theoretical results ensuring that GRIT is highly expressive when equipped with RRWP encodings. Despite this, we show that GRIT achieves superior empirical performance when MoSE is used instead of RRWP.
5.3 GRAPH REGRESSION ON QM9
QM9 is a real- world molecular dataset that contains over 130,000 graphs (Wu et al., 2018 Brockschmidt 2020). The node features include atom type and other descriptive features. Un- like ZINC, where there is only one regression target, QM9 presents 13 different quantum chemical properties regress over, making it much more robust benchmark.

---

Published as a conference paper at ICLR 2025
Frequency
Table 5: MAE results for our synthetic dataset. MoSE consistently performs the best, with MLP+MoSE even outperforming the Graph Transformer with LapPE and RWSE.
Encoding
MLP
GT
1.0
1.5 2.0 2.5
3.0
3.5
4.0
4.5
5.0
Fractional Domination Number
LapPE
0.482.1.00:
0.0841.001
RWSE
0.075 0001
0.0611.001
Figure 3: Plot of the distribution of fractional domination numbers in our synthetic dataset.
MoSE (ours)
0.058= 001
0.055#.001
Experimental Setup. We select GPS (Rampásek al. 2022) due its modularity and compare GPS+RWSE to GPS+MoSE. We follow Jin et al. in constructing MoSEg with the set of all connected graphs of at most vertices and the 6-cycle: g 2225 U Cp. Since there are several regression targets for QM9, our choice of G is advantageous as it accounts for a diverse set of motifs, allowing GPS to express varied graph motif parameters (Proposition 4.3). We keep a random- walk length of 20 for RWSE to align with Rampásek et al. (2022). Finally, provide several leading GNN models for comparison (Brockschmidi |020] Alon & Yahav 2021 Abboud et al. 2022 Dimitrov et al. 2023).
Results. MoSE consistently outperforms RWSE across multiple targets, achieving the best MAE on 11 of the 13 molecular properties (Table 4). GPS+MoSE comfortably outperforms leading GNN models, including R-SPN (Abboud et al.) 2022) and E-BasePlane (Dimitrov et al. 2023), the latter of which is isomorphism-comples over planar graphs. By contrast, GPS+RWSE is occasionally outperformed by these GNN architectures, despite being more computationally demanding.
5.4 SYNTHETIC DATASET: PREDICTING FRACTIONAL DOMINATION NUMBER
We generate a new synthetic dataset where the task is to predict each graph's 's fractional domination number. This target relies on complex long-range interactions, being an inherently global property, unlike other popular metrics (e.g., clustering coefficients) which are aggregations of local properties. The target distribution our dataset is complex (Figure 3). making the task highly challenging. Furthermore, fractional domination is important for range of applications, such optimizing resource allocation (G. et al. 2024). Specific details for our dataset are given in Appendix B.9
Experimental Setup. We focus on isolating the performance of MoSE compared to LapPE and RWSE. For this, we select a 4-layer MLP and a basic Graph Transformer (Dwivedi & Bresson 2020) as our reference models. Since neither architecture contains local message passing component, neither model contains any inherent graph inductive bias. Hence, all structure-awarenes. comes from the encodings. We choose G = Spasm (C+) U (Cp) for MoSEg, random walk length 20 for RWSE, and dimension 8 for LapPE.
Results. Table that MoSE outperforms LapPE and RWSE across both models. Strikingly, even the simple MLP+MoSE model outperforms the more advanced +T+RWSE and GT+LapPE models. These results suggest that MoSE able to capture complex graph information context broader than just the molecule and image domains. We also note that MLP+LapPE performs significantly worse than other configurations. This indicates that the self-attention mechanism of GT is a key component in allowing the model to leverage spectral information provided by LapPF.
6 DISCUSSION AND FUTURE WORK
We propose motif structural encoding as a flexible and powerful graph inductive bias based on count- ing graph homomorphisms. MoSE is supported by expressiveness guarantees that translate naturally to architectures using MoSE. In particular, we show that MoSE is more expressive than RWSE, and we relate these encoding schemes to the expressive power of MPNNs as well as the WL hierarchy more generally. We empirically validate the practical effects of our theoretical results, achieving strong benchmark performance across a variety of real-world and synthetic datasets. Although our work takes closer look at the expressivity of different graph inductive biases, there remains several open questions (e.g., the relationship between MoSE and spectral methods). Furthermore, we have yet explore the full potential of the node-weighting parameter in encoding scheme.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENTS
Emily Jin partially funded by AstraZeneca and the UKRI Engineering and Physical Sciences Research Council (EPSRC) with grant code EP/S024093/1. Matthias Lanzinger acknowledges support by the Vienna Science and Technology Fund (WWTF) [10.47579/CC220]]] This research is partially supported by EPSRC Turing AI World-Leading Research Fellowship No. EP/X040062/1 and EPSRC AI Hub on Mathematical Foundations Intelligence: An "Erlangen Programme" for Al No. EP/Y028872/1.
REFERENCES
Ralph Abboud, ismail ilkan Ceylan, Martin Grohe, and Thomas Lukasiewicz. The surprising power of graph neural networks with random node initialization. IJCAI, 2021.
Ralph Abboud, Radoslav Dimitrov, and ismail ilkan Ceylan. Shortest path networks for graph property prediction. In LoG, 2022.
Uri Alon and Eran Yahav. On the bottleneck of graph neural networks and its practical implications. In ICLR, 2021.
Guy Bar-Shalom, Beatrice Bevilacqua, and Haggai Maron. Subgraphormer: Unifying subgraph gnns and graph transformers via graph products. In NewrlPS, 2024.
Pablo Barceló, Floris Geerts, Juan L. Reutter, and Maksimilian Ryschkov. Graph neural networks with local graph parameters. In NeurlPS, 2021.
Giorgos Bouritsas, Fabrizio Frasca, Stefanos Zafeiriou, and Michael M. Bronstein. Improving graph neural network expressivity via subgraph isomorphism counting. IEEE Trans. Pattern Anal. Mach. Intell., 45(1):657-666 2023.
Marco Bressan, Matthias Lanzinger, and Mare Roth. The complexity of pattern counting in directed graphs, parameterised by the outdegree. STOC, 2023.
Mare Brockschmidt. GNN-FiLM: Graph neural networks with feature-wise linear modulation. In ICML, 2020.
Jin-Yi Yi Cai and Artem Govorov. On a theorem of lovász that hom h) determines the isomorphism type of h, 2021. https:tts:://eet /ttss:///axvvv.e/ http://////aaii.oo////a////// www.///ggg../eeeeeee../eeeeeeeee /1099. 03693
Jin-Yi Cai, Martin Fürer, and Neil Immerman. An optimal lower bound on the number of variables for graph identification. 30th Annual Symposium Foundations of Computer Science, pp. 612-617, 1989. /ttt:t/s:://apt
Zhengdao Chen, Soledad Villar, Lei Chen, and Joan Bruna. On the equivalence between graph isomorphism testing and function approximation with gnns. CoRR, abs/1995.112560 2019. URL
http::/arxiis
org/ http://wwwwgg//////ro///ee /00bs//995..m 12560
Radu Curticapean, Holger Dell, and Dániel Marx. Homomorphisms are a good basis for counting small subgraphs. In STOC, 2017.
Li Deng. The mnist database of handwritten digit images for machine learning research. IEEE Signal Processing Magazine, 1911)141 2012.
Radoslav Dimitrov, Zeyang Zhao, Ralph Abboud, and ismail ilkan Ceylan. PlanE: representation learning over planar graphs. In NeurlPS, 2023.
Zdenek Dvorák. On recognizing graphs by numbers of homomorphisms. Graph Theory, 64(4): 330-342, 2010.
Vijay Prakash Dwivedi and Xavier Bresson. A generalization of transformer networks to graphs. arXiv preprint arXiv:20/2.09699 2020.
Vijay Prakash Dwivedi, Anh Tuan Luu, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Graph neural networks with leamable structural and positional representations. In ICI.R, 2022a.
11

---

Published as a conference paper at ICLR 2025
Vijay Prakash Dwivedi, Ladislav Rampášek, Michael Galkin, Ali Parviz, Guy Wolf, Anh Tuan Luu, and Dominique Beaini. Long range graph benchmark. In NewrIPS, 2022b.
Vijay Prakash Dwivedi, Chaitanya K Joshi, Anh Tuan Luu, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Benchmarking graph neural networks. Journal of Machine Learning Research, 24 (43):1-48, 2023.
M. Freedman, L.. Lovasz, and A. Schrijver. Reflection positivity, rank connectivity, and homomor- phism of graphs, 2004.
Frank Fuhlbrück, Johannes Köbler, Ilia Ponomarenko, and Oleg Verbitsky. The weisfeiler-leman algorithm and recognition of graph properties. Theor. Comput. Sci., 895:96- 114, 2021. doi: TC..6//.CCS..02..0000
/ http:/doi..om http://///oooooo.111110111
tcs. 2021 09. 033
Uma G., S Amutha, Anbazhagan Neelamegam, B Koushick, and George Taylor. Exploring prism graphs with fractional domination parameters. Mathematics and Statistics, 12:448 454, 08 2024.
doi: 10.13 (0.13189/s..om 2024............. 2024..20006......
Justin Gilmer, Samuel S. Schoenholz, Patrick F. Riley, Oriol Vinyals, and George E. Dahl. Neural message passing for quantum chemistry. In ICML, 2017.
Martin Grohe and Martin Otto. Pebble games and linear equations. The Journal of Symbolic Logic, 80(3):797-844, 2015.
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. In NeurIPS, 2020.
Weihua Hu, Matthias Fey, Hongyu Ren, Maho Nakata, Yuxiao Dong, and Jure Leskovec. Ogb-Isc: A large-scale challenge for machine learning graphs. 2021.
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). IEEE, June 2021. doi: 10. 00.1109/cass3339788 018...2221..1133 URL http: dx doi. org/ 1109 ICASSP 7728 2021. 9413523
John J Irwin, Teague Sterling, Michael M Mysinger, Erin S Bolstad, and Ryan Coleman. Zinc: a free tool to discover chemistry for biology. Journal of chemical information and modeling, 52(7): 1757-1768, 2012.
Emily Jin, Michael M. Bronstein, ismail Îlkan Ceylan, and Matthias Lanzinger. Homomorphism counts for graph neural networks: All about that basis. In ICML, 2024.
Nicolas Keriven and Gabriel Peyré. Universal invariant and equivariant graph neural networks. In NeurlPS, 2019.
Devin Kreuzer, Dominique Beaini, Will Hamilton, Vincent Létourneau, and Prudencio Tossou. Rethinking graph transformers with spectral attention. In M. Ranzato, A. Beygelz- imer, Y. Dauphin, P.S. Liang and Wortman Vaughan (eds.), Advances in Neural In- formation Processing Systems, volume 34, pp- neur i ps cc/paper fillss/paper/2221
Curran Associates, Inc.,
2021. URL htttps::/prrceeeeiiii i.le/b4fdld2cbbll (bw.:399ebbbbdadeeeeeeeeeee 76 Paper. .pdf
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
Matthias Lanzinger and Pablo Barceló. On the power of the weisfeiler-leman test for graph motif parameters. In /CLR, 2024.
Moritz Lichter, Ilia Ponomarenko, and Pascal Schweitzer. Walk refinement, walk logic, and the iteration number of the weisfeiler-leman algorithm. In IJCS, 2019.
Derek Lim, Joshua Robinson, Stefanie Jegelka, and Haggai Maron. Expres- sive sign equivariant networks for spectral geometric learning. In NeurIPS.
URL http:://ppprs..npss.coo http:///aaeaaaaaaa/////aaaaaaaaa 351 (35e2333177770000077244449444440
2023a.
/
12

---

Published as a conference paper at ICLR 2025
Derek Lim, Joshua David Robinson, Lingxiao Zhao, Tess E. Smidt, Suvrit Sra, Haggai Maron, and Stefanie Jegelka. Sign and basis invariant networks for spectral graph representation learning. In ICLR 2023. OpenReview.net, 2023b. URL https:://////.
Q Q-UHqMorzi1l
Xiao Liu, Shiyu Zhao, Kai Su, Yukuo Cen, Jiezhong Qiu, Mengdi Zhang, Wei Wu, Yuxiao Dong, and Jie Tang. Mask and reason: Pre-training knowledge graph transformers for complex logical queries. In SIGKDD, 2022.
Andreas Loukas. What graph neural networks cannot learn: depth width. In ICLR, 2020.
László Lovász. Operations with structures. Acta Mathematica Hungarica, 18(3-4):32-3225, 1967.
László Lovász. Large Networks and Graph Limits, volume 60 Colloquium Publications. American Mathematical Society, 2012.
Liheng Ma, Chen Lin, Derek Lim, Adriana Romero-Soriano, Puneet Dokania, Mark Coates, Philip H. S. Torr, and Ser-Nam Lim. Graph inductive biases transformers without message passing. In ICML, 2023.
Takanori Machara and Hoang NT. Deep homomorphism networks. In NeurIPS, 2024.
Haggai Maron, Heli Ben-Hamu, Hadar Serviansky, and Yaron Lipman. Provably powerful graph networks. In NeurIPS, 2019a.
Haggai Maron, Ethan Fetaya, Nimrod Segol, and Yaron Lipman. On the universality of invariant networks. In ICML, 2019b.
Dániel Marx. Can you beat treewidth? Theory Comput., 6(1):85-112, 2010.
Christopher Morris, Martin Ritzert, Matthias Fey, William L. Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe. Weisfeiler and Leman go neural: Higher-order graph neural networks. In AAAI, 2019.
Daniel Neuen. Hononorphism-ddsiiigiihhnng closedness for graphs of bounded tree-width, arXiv preprint arXiv:2304.07011, 2023.
Hoang Nguyen and Takanori Maehara. Graph homomorphism convolution. In ICMI., 2020.
Ladislav Rampásek, Michael Galkin, Vijay Prakash Dwivedi, Anh Tuan Luu, Guy Wolf, and Do- minique Beaini. Recipe for general, powerful, scalable graph transformer. In NewrIPS, 2022.
Eran Rosenbluth, Jan Tönshoff, Martin Ritzert, Berke Kisin, and Martin Grohe Distinguished in uniform: Self-attention vs. virtual nodes. ICLR, 2024.
Marc Roth and Johannes Schmitt. Counting induced subgraphs: A topological approach to #W[1]- hardness. Algorithmica, 82)):222772 2020.
Ryoma Sato, Makoto Yamada, and Hisashi Kashima. Random features strengthen graph neural networks. In SDM, 2021.
Edward R Scheinerman and Daniel H Ullman. Fractional graph theory: rational approach the theory of graphs. Courier Corporation, 2013.
Ahsan Shehzad, Feng Xia, Shagufta Abid, Ciyuan Peng, Shuo Yu, Dongyu Zhang, and Karin Verspoor. Graph transformers: A survey. arXiv preprint arXiv:2407.09777, 2024.
Hamed Shirzad, Ameya Velingker, Balaji Venkatachalam, Danica J Sutherland, and Ali Kemal Sinop. Exphormer: Sparse transformers for graphs. In JCML, 2023.
Joshua Southern, Francesco Di Giovanni, Michael M. Bronstein, and Johannes Lutzeyer. Under- standing virtual nodes: Oversquashing and node heterogeneity. In The Thirteenth International Conference on Learning Representations, 2025, URL httt::::/pppeeeeeeeees www.roruutttttt
Nd=
13

---

Published as a conference paper at ICLR 2025
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention all you need. In NeurIPS, 2017.
Yanbo Wang and Muhan Zhang. Towards better evaluation of gnn expressiveness with brec dataset. In JCML, 2024.
Zhenqin Wu, Bharath Ramsundar, Evan N Feinberg, Joseph Gomes, Caleb Geniesse, Aneesh S Pappu, Karl Leswing, and Vijay Pande. Moleculenet: benchmark for molecular machine learning. Chemical science, 9()):513-300, 2018.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In ICLR, 2019.
Chengxuan Ying, Tianle Cai, Shengjie Luo, Shuxin Zheng, Guolin Ke, Di He, Yanming Shen, and Tie-Yan Liu. Do transformers really perform badly for graph representation? In NeurlPS, 2021.
Seongjun Yun, Minbyul Jeong, Rachyun Kim, Jaewoo Kang, and Hyunwoo Kim. Graph transformer networks. In NeurIPS, 2019.
Bingxu Zhang, Changjun Fan, Shixuan Liu, Kuihua Huang, Xiang Zhao, Jincai Huang, and Zhong Liu. The expressive power of graph neural networks: A survey, 2023a. URL https:
08235
Bohang Zhang, Shengjie Luo, Liwei Wang, and Di He. Rethinking the expressive power of Gans via graph biconnectivity. In ICLR, 2023b.
Bohang Zhang, Jingchu Gai, Yiheng Du, Qiwei Ye, He, and Liwei Wang. Beyond weisfeiler- lehman: A quantitative framework for gnn expressiveness. In ICLR, 2024.
Wen Zhang. Yushan Zhu, Mingyang Chen, Yuxia Geng, Yufeng Huang, Yajing Xu, Wenting Song. and Huajun Chen. Structure pretraining and prompt tuning for knowledge graph transfer. In WwW, 2023c.
A TECHNICAL DETAILS
Proof of Proposition 4.7 Dvorák (2010) showed that if and H are equivalent under k- WL,, then
every graph F with treewidth at most & has Hom F, G) Hom F, H). This extends also to the vertex level. Let E VG) and o' E (HH) such that v and v' have equivalent k-WL labels. Then also Hom( F, v) Hom(F, (F, H, E²) (see Lanzinger & Barceló 2022). Lemma 12). Hence, if the maximum treewidth in G is k, then equivalence under k- &L implics also that they are equivalent under MoSEg.
Proof of Proposition 4.2 It is well known Lováss 1967) that for every two non-isomorphic graphs G and H, there is graph F' such that Hom (F, G) Hom(F, H). We have that MoSE will distinguish the two graphs.
Suppose the opposite, i.e., there is pair of graphs G, H such that f(G of (H), but MoSEr,, where , is set of graphs in the basis of f, creates the same multiset of labels on both graphs. Then specifically, also Hom(F, (F, G) Hom(F, H)) for every F E T But since is graph motif parameter, f(G) = fHH) and we arrive at contradiction.
Proof of Proposition 4.3
A.1 THEOREM 4.6
Take any graph H and notate V(H) = 21. For u, E V(H), define P(v 4 v') to be the probability starting a length random walk at node v and ending it at node r'. Here, "length !" refers the number of edges in the random walk where allow repeat edges, and "random walk" refers to a walk where each step (say we are currently at node v) assigns a uniform probability 1/d(w) moving any of the neighbors in M(v).
Proof of Proposition 4.5
14

---

Published as a conference paper at ICLR 2025
As shorthand, define M D A where D and A are the diagonal degree matrix and adjacency matrix of H respectively. Let us first prove that (M') (M') P(e + o') for any nodes v' E V and for all powers i by performing induction on The base case i holds trivially because assume that random steps are taken uniformly over neighbors. Assume as the inductive hypothesis that our claim holds for some 2 1, and note that:
(M (M )o,or (M M Jo
Σ Mu M
but base and inductive hypothesis tell that
Σ
M M a
Σ
P(e P(o 4)) P(x 4 v²)
x=1
By the law of total probability:
P(x 40) P(u +tt 6¹)
This completes the induction. Hence, for any node in any graph H, the node-level RWSE, vector is equivalent to:
RWSEx(v, (M²) 0..0 )o,0
i-1 = [p(o + u)
E E
i=1
Now, let us show that we can recover this random-walk vector using MOSE. Consider the family of all cycles with up to nodes G = {Ca)i= and let w be the vertex weighting which maps any node to the reciprocal of its degree. Of course, the "cycles" C1 and C2 are not well-defined, let us set C1 to be the empty graph (with no nodes and no edges) and C2 to be the graph with two nodes connected by edge. We say that there are zero homomorphisms from C1 into any other graph purely as a notational convenience aligning with the fact that (M²).,, ) is always O.
For each C G with i 1, enumerate the nodes V(C+) {uo, u1,..., 24- } such that (Mg ue++1) E(C;) for all l O, O..., i 2 and (w:-1, un) E E(C²). Take any node in any graph H, and define H; be the of all homomorphisms from Cj G which map node uo C2 node E G. Each homomorphism in f E Hi can be constructed by making - choices of node image f(ue) E N (f(u))1) for é I, ..... 1 such that (u)(=))) N (f(()))) where we have fixed f(oo) v. In other words, each homomorphism f H, corresponds to i-edge walk (allowing edge repeats) starting and ending at node which we will call Wy. This correspondence is described by taking the induced subgraph W, = G[S(C,)] where f(C,) is the image of C, under homomorphism f. In the reverse direction, any i-edge walk
Wf
(0))
( ( v H
that starts and ends at node corresponds homomorphism f Hi which maps f(ue) (()) Hence, we have described a bijective correspondence between H, and the set of i-edge walks starting/ending at v.
For any f E H4, we have:
II wf(()) = II 1/d(v) II (1) (EV(C,)
nEW,
E=
Since the probability of stepping from node v( E V(W)) to node (++ E V(W,) in a random walk is simply lfd(v(()), it holds that:
i-1 II I//((((0) PPW,)
t=O
where P(W,) is the probability of performing the random walk Wy. Thus,
w-Hom (C, G)
Σ
P(W,) P(e i v)
SEH.
15

---

Published as a conference paper at ICLR 2025
giving
MoS w w--Hom. H1)
P(u 4 v) i=1
RWSE,
i=1
Proof of Proposition 4.4 We first recall the walk refinement procedure from Lichter al. (2019) such that we can relate it directly to RWSE.
The scheme at its basis assumes directed complete colored graph G (V, H, where the coloring X always assigns different colors to self-loops than to other edges. For tuples of m vertices (V1, 122 ......., mm) E V we define
X(v1, U2,
....... .... Um) = ((x(1), 02), x(v2, va),..., X1 0m)).
Ultimately, we want use the scheme undirected uncolored graphs. An undirected (and uncolored)
graph G. converted into the setting above by adding the coloring X V(G) - {-1, 0, 13 as follows: for all self-loops X assigns -1, i.e., x(v, v) =1 For all distinct pairs u, we set x(1, u) if (v, u) E EGG and X(U, u) = if (v, u) & E(G). For the directed edges recall that we consider complete directed graphs and hence E = V2
With this in hand we can define the walk refinement procedure of Lichter et al. (011). Formally, for k 2, the k-walk refinement of colored complete directed graph G = (V, E, x) the function that gives the new coloring [w[ss] to every edge as follows
XW (v, u) (x(u, wi,--- wh.----;h-1,,u w. E EVB
Intuitively, the refinement takes into account all walks of length k: in the graph. Note that walks of length shorter than & are also captured via self-loops (because of their different weights always aware that a self-loop is taken and that a specific tuple in the multi-set represents a shorter walk. As with the Prisfeiler-eemad color refinement procedure, k-walk refinement can be iterated until it reaches a stable refinement (after finitely many steps). We will write x'(u, u) to designate the color obtained after steps of the refinement (with x(v, u) x (v, u)). Importantly, Lichter et al. (2019) (Lemma 4) show that the stable refinements of the k-walk refinement procedure is always reached after finitely many steps and produces the same partitioning of vertices 2-WL. That is, any pairs (u, v) and (I, y) that receive the same label by 2-WL refinement, also have x (v, u) x²x (I,
also
All that then left show that the stable W[k] refinement uniquely determines the RWSE, feature vector for every vertex In particular, we show that every entry of the RWSE, vector of any vertex can be uniquely derived from the W[k] labeling of the pair (u, v). As shown in Proposition 4.5) the k'th entry of the RWSE, vector for v, is uniquely determined by the number of k k'-hop paths beginning and ending in v, together with the degrees along every such path. In the following, we observe that this combination of information can be directly computed from the W W[K] labeling of (v, v).
We first observe that xi (v, v) uniquely determines the degree of v. It is equivalent to the number of k-walks that move adjacent vertex and continue with self-loops for the l remaining steps. That is:
degree(v) (v) (xgree(Xiissf v)) = [[(, (111,-1-144 -1) (w,
(2)
Similarly, it is straightforward to recognise the original label x(v, u) from (w,g
X(e, u) = = - {-13* k E xiviq u)
(3)
that and only if u can be reached from only through self-loops. Similarly we can determine the other labels, and we only state the case for an edge existing here:
X(v, =
(1,
1) E Xwrx (u, u).
(4)
We similarly retrieve the label x(e, u) from X2 (v, u), since in any tuple of the form ((x(11 02). X(v2, vz), ... ((vm vm))
16

---

Published as a conference paper at ICLR 2025
know by Equation (3) and Equation whether the respective pair of vertices are adjacent or equal. We can then naturally iterate the definitions from Equation (3) and Equation (4). Thus, for every 1 k' I k, we can directly enumerate all paths from v to by inspecting the multiset x (v, v).
To complete the argument outlined above, we need to show that for every v, u, (v, u) determines the degree of u. Now above degree. We have X(e, u) = -1, if and only if there is a tuple for the walk (v, v; V....,,) u) E x² (and the tuple can be recognised). The degree then directly determined by the first tuple through Equation (2). Similarly, x(v, u) = 1, if and only if there is a tuple (u, u,..., u) E (", u) that corresponds original labels (-1, (-1.-l..... -..... 1. 1). We can thus again obtain the degree from the first position of this tuple, and analogously for the 0 label.
determine X(e, u) and for each case observe how obtain the (u,,u) u)
In summary, we see that after steps of k-walk refinement, every label of (u, v) has enough information to uniquely determine all to k-walks from to together with the degree of every node of the walk. As seen in the proof of Proposition 4.3 this determines the RWSE, vector.
We note that the proof in fact shows stronger statement than RWSE, being most expressive as 2-WL. It shows that RWSE& & is at most as expressive as 2-steps of k-walk refinement. This can be further related equivalence under certain number of 2-WL steps through the work Lichter et al. 2011))
One direction is shown in Figure 1 which shows two graphs G and H, with highlighted green and black nodes each. For every step length E, RWSE produces the same node features for both green vertices (u1 u2)) and both black vertices (V1, 02), respectively. At the same time, it is straightforward to see that the 1-WL labeling of the green/black nodes is different in the two graphs.
Proof of Proposition 4.7
For the other direction, and the graph containing the veretxx cycle as drawn below (Figure H well known that all nodes in both graphs have the same 1-WI. label. In contrast, RWSEg labels the nodes in G differently from the nodes in H, and the respective vectors are given below.
the classic example comparing the graph G consisting of two triangles
0.5
0.5
(0.25)
Figure 4: The 6 vertex cycle (left) and the disjoint sum of 2 triangles (right) are indistinguishable by 1-WL. but distinguishable by RWSE already after steps. The RWSE vectors in the respective graphs are all the same and are given next to the graphs.
B ADDITIONAL EXPERIMENTAL DETAILS
We provide additional experimental details and hyperparameters for results in Section 5
All code and instructions on how to reproduce our results are available at the following link: http://gthubb.cooo//usss/////ooo
Compute Resources. All experiments were conducted on a cluster with 12 NVIDIA A10 GPUs (24 GB) and NVIDIA H100s. Each node had 64 cores of Intel(R) Xeon(R) Gold 6326 CPU at 2.90GHz and 500GB of RAM. All experiments used at most 1 GPU at time.
B. COMPLEXITY OF COMPUTING HOMOMORPHISE COUNTS FOR MOSE
Practically, computing the homomorphism counts for MoSE highly parallelizable since the homo- morphisms from each pattern be counted independently from another. In experiments,
17

---

Published as a conference paper at ICLR 2025
Table Time compute MoSE embeddings used all experiments reported as elapsed real time (wall time). Reported times are normalized by dataset size (i.e. per graph). 1225 refers to the set of all connected graphs with most 5 nodes, and C, the eycle graph nodes.
Avg. # nodes
Avg. # edges
Dataset
# Graphs
Motifs
Time (sec)
ZINC
12,000
23.2
49.8
Spasm (Cz) U Spasm
0.03
QM9
130,831
18.0
37.3
D U Cs
0.02
PCQM4Mv2-subeet
446,405
14.1
14.6
2 U Ce
0.03
CIFARIO
60,000
117.6
941.1
2
0.08
MNIST
70,000
70,6
564.5
Q
0.06
Synthetic func/struct
10,000
23.5
137.9
Spasm (Cz) Ü Spasm
0.06
15,535
150.9
307.3
Both
0.01
*The "Both" motif refers Spasm (C+) U Spasm(Cs) and 52 U Cs, henchmarked seperately.
computing the MoSE encodings took only fraction of second per graph (see Table o By contrast, training various Transformer models on these datasets took between 15-30 hours for single run. Hence, the time to compute MoSE is almost negligible overall.
From a theoretical perspective, the complexity MoSE is very intricate. With constant uniform weighting, counting homomorphisms from H is feasible time O (G[tt(H)) where tw H) is the treewidth of H. It is known that this exponent cannot be substantially improved upon (Marx 2010). The complexity of computing MoSE encodings thus fundamentally depends on the choice of patterns and their treewidth.
As we show in Proposition 4.5 RWSE is simply a limited special case of MoSE for one specific set of pattern graphs (cycles) and specific weighting scheme (w<v) 1/d(e)). Cycles always have treewidth 2, and thus RWSE always feasible quadratic time. However, RWSE cannot capture other treewidth motifs that MoSE can accommodate for essentially the same cost.
B.2 MODEL DEFINITIONS
We give definitions for those architectures which are not taken directly from the literature. Given graph G' and node E V (G)), let the node representation h e Rd be vector concatenation of the initial node label and the struccuraa/positiioaal encoding v. To apply an L-layer MLP on G, we update each node representation in parallel for 1,
ReLU
W ( + b(0)
YOE V(G)
(5)
When edge features are available, MLP-E applies two MLPs in parallel to process node representations and edge representations separately. That is, node representations h are learned according to
equation 5 using a of weights { (t) (t) Me while the edge representations (t) Rd
noder
learned using a different set of weights:
ReLU
(w (t- + +b(()
A (w, E E(G)
edgo
for f. 1,... Te. Note that do not require that d de and L Le-
The GT model updates node representations by using scaled dot- not-product attention (Vaswani et al. 2017]:
h = MLP(()
()) h=1
wit
Σ
(t-1)
(6)
V.h
GEV(G)
w h (e-1))
(
(t-1)
(8)
softmax,
K.A
vd
18

---

Published as a conference paper at ICLR 2025
fort 1,.., L. Here, the @ symbol denotes vector concatenation, and softmax is computed relative to the vector formed by iterating the expression inside the softmax argument over E V(G). When provided with edge labels that come from a finite collection of discrete edge types, the GT-E models uses a learnable look-up embedding to learn a representation e(t) u,n,h E R2 for every node pair u # v E V(G), every attention head = 1 !,.... Rs, and every layer 1 = 1,... L. Non- adjacent node pairs (u, v) & F(G) assigned some pre-defined "null edge-type". Then, these edge representations bias the attention as:
dot Not[wol) (1) Q. Q.h
h (1-1)
w (t) (t-1) (1) K. ha
u.v.A.
u,u,A = softmax,
(8)
vd
where
dotja, b, c) Σ a: b,
The node update equation of GT-E defined by simply plugging in the edge-biased attention values (c) ao,u, given by equation (8) into the node update equation (6). Our method of "biasing" attention values with edge representations (eq. ( is inspired by the edge-type gege-type-aweer peparware graph transformer models of Dwivedi & Bresson (2020) and Kreuzer al. (02TT)
The final node representations are sum pooled in order to produce a graph representation hg. The MLP-E model additionally pools edge representations and concatenates the edge pool to the node pool:
hg
Σ VEV(G)
hg
for MIP, GT, and GT-E
hg
Σ (EV(G)
h
(L)
+
Σ
u
(Le)
for MLP-E
(u.))EE(G)
Finally, an MLP prediction head applied on hG produce an output label. The reader should note that equations 5 5 only describe the essential aspects of our models; when we implement these models in practice, we additionally include the usual regularization/auxllliry modules at each layer (e.g., batch normalization and dropout), specified by the hyperparameter details below.
B.3 HYPERPARAMETER PROTOCOL
For all experiments which compare multiple positional//sructuuall encodings, we perform the same grid-search on each encoding independently (however, this does not necessarily apply to reference results that we draw from other works). For some of our experiments, we take the shortcut of grid searching wider range of values the baseline none-encoding (where we use the model without any positional//strucuraa encoding). and then we proceed to search only a strict subset of frigh-performing" values for each non contyy encoding (e.g., MoSE, RWSE, and LapPE). In this case, since the grid search for RWSE/MoSE/L.n apPE is strictly less exploratory than our baseline search, reported results for RWSF/MSSE/LapPH improvement they provide over the none-encoding baseline, or (at best) a perfectly fair comparison.
(at worst) conservative under-estimate of the
See the appendix sections that follow for details on our hyperparameter configurations and hyper- parameter searches. We try to give as many relevant specifics as possible here in the appendix, but some of the hyperparameter details (especially those for our large Transformer models) are excessive for the purposes of this appendix, and are much better expressed in model configuration file. Hence, we only outline the most important details here, asking readers reference the online code repository http://ghhuub.coo/iiuussa///////
for all other information.
Blanket Hyperparameters. There are number of hyperparameters which remain fixed across all of our experiments, so we state them here once to avoid redundancy. In all models, a 2-layer MLP is used to embed the raw positional//truuturaal encoding values. The dimension of this embedding scales according to the width of the main model being used (see the code repository for exact values). Unless otherwise specified, all models utilize global sum- sum-ooolig followed by 3-layer MLP prediction head where each layer subsequently reduces the hidden dimension by factor of 1/2 (other than the output layer, which has dimension equal to the number targets). Lastly, all models use the ReLU activation function.
19

---

Published as a conference paper at ICLR 2025
B.4 EXPERIMENTAL DETAILS FOR ENCODING COMPARISON ANALYSIS
We give experimental details for the MoSE results shown in Table I All of our MoSE results in Table
are are the mean (# standard deviation) of 4 runs with different random seeds. Table resullss for encodings other than MoSE are taken from Rampásek et al. (2022)
B.4.1 ZINC-12K 12K
We subset of the ZINC molecular dataset that contains 12,000 graphs (Dwivedi al. 2023), The dataset is split into 10,000 graphs for training, 1,000 graphs for validation, and 1,000 graphs for testing. Each graph in the dataset represents molecule, where the node features indicate the atom type, and the edge features indicate the bond type between two atoms. The dataset presents graph-level regression task predict the constrained solubility of given molecule. Following Rampásek et al. 20222. we constrain all models to 500K parameter budget.
GPS Hyperparameter details for GPS+MoSE results on ZINC in Table I are identical to those used in Appendix B.7.3
B.4.2 PCQM4MV2-SUBSS
PCQM4Mv2-subaae is subset of the Large-Scale Open Graph Benchmark PCQM4Mv2 dataset (Hu al. 2021) As mentioned in Rampásek et al. (2022), this subset samples the original PCQM4Mv2 dataset as follows: 10% of the original training set, 33% of the original validation set, the entire test set. This results in 322,869 training graphs, 50,000 validation graphs, and 73,545 test graphs, for a total dataset size of 446.40 molecular graphs. In order to align with Rampásek al. (2022), use the exact same PCQM4Mv2-subset graphs that they use in their original ablation study.
Similarly to ZINC, PCQM4Mv2 is molecular dataset, where each graph represents molecule, with nodes denoting atoms and edges denoting bonds. The dataset presents a graph-level regression task to predict the DFT-calculated HOMO-LUMO energy gap of given molecule.
We do not perform a structured grid search for GPS+MoSE results on PCQM4Mv2 in Table T Instead, we simply try few different model configurations (which can be found in code repository) inspired by our experiments on ZINC and QM9. The final model used in our reported results is summarized follows:
GPS
MPNN Type: GatedGCN
Attention Type: Standard*
Layers: 12
Width/Heads: 256 /
Batch Size: 256
Optimizer: AdamW
Weight Decay: ()
Base LR: 0.0002
Max Epochs: 300
LR Scheduler: Cosine
LR Warmup Epochs: 10
Attention Dropout: 0.1
*The "Standard" attention type refers to multi-hean scaled dot product attention.
B.4.3 CIFARIO
The original CIFAR 10 dataset consists of 60,000 32x32 color images in 10 classes, with 6,000 images in each class (Krizhevsky et al., 2009). From this, Dwivedi et al. (023) generate a graph benchmarking dataset by constructing an 8 nearest-neighhor graph of SLIC superpixels for each image. The graph benchmarking dataset maintains the same splits as the original image dataset, which contains 45,000 training. 5,000 validation, and 10,000 test graphs. Following Rampásek et al. (002), we constrain our reported model 100K tunable parameters.
GPS We grid search GPS+MoSE CIFARIO (Table I as follows. First, we fix the following hyperparameters:
MPNN Type: GatedGCN
Attention Type: Standard
Attention Heads: 4
Batch Size: 16
Base LR: 0.001 Optimizer: AdamW
Max Epochs (warmup): 100 (5)
LR Scheduler: Cosine
Attention Dropout: 0.5
20

---

Published as a conference paper at ICLR 2025
Then, grid-search all combinations of the following: (the best configuration with 100K parame- ters is shown in bold)
Layers: (2.3)
Width: {36, 52,,52.77 72]
Weight Decay: {10-3 10 10
Dropout of Feed-forward and MPNN Layers: {0.0, 0.2,0.4)
Additional Results Our reported results in Table use homomorphism counts from the family 2g In Table 7 helow, we also report results for MoSE constructed from Spasm(C7) U Spasm(Cs). as well as results that exceed the 100K parameter budget (hyperparameter details for these extra experiments can be found the code repository).
Table 7: We benchmark GPS+MoSE on CIFAR1O. Our pattern families are S = Spasm(Cr) U Spasm(Cs) and Ω 2oon. GPS+LapPE results from Rampásek al. (2022) are included for reference. MoSE outperforms LapPE across the board, and larger models perform best.
Model
CIFAR1O (Aec. f)
Parameters
GPS+LapPE
72.31
112,726
Gml MoSSEs (ours)
73.34+0.50
110,188
GPS MooSE (ours)
10.59
267,134
GPS +MoSE (ours)
73.50
114,330
GPS MoSEn (ours)
74.73+0.64
215,794
B.5 MNIST
Due to the success of MoSE on CIFARIO, we conduct an additional experiment with GPS+MoSE on the MNIST image classification dataset. The original MNIST dataset consists of 70,000 28x28 black and white images in 10 classes, representing handwritted digits (Deng 2012). From this, Dwivedi al. (2023) follow the same procedure as for CIFAR10 10 and generate graph benchmarking dataset by constructing an 8 nearest-neighbor graph of SLIC superpixels for each image. The graph dataset also has the
original dataset splits of 55,000 training, 5,000 validation, and 10,000 test graphs.
free with other leading GNN and Graph Transformer models, and we follow (ooopásaa et al. (2022) in constraining our model to ~ 1000 tunable parameters. In (C2), as well as GPS+MoSE models that exceed the 100K parameter budget. We do not grid-search GPS+MoSI on MNIST, and instead we simply extrapolate from our grid-search on CIFARIO 10 to infer our model configurations (see code repository for details). All results for GPS+MoSE are the mean (# standard deviation) of 4 runs with different random seeds, and all results for other models are taken from Rampásek al. 20022. We observe that GPS+MoSE is competitive with leading GNNs MNIST.
In Table 8, we compare GPS MoSSM
Table we report additional MPS+E results using counts from
Table 8: Results on MNIST with ~ 100K parameter models. Best results in red, second best blue.
Table 9: GPS+MoSE on MNIST with various configura- tions. We include EGT and GPS+LapPE for reference. S Spasm (C>) Spasm and f Qooon Best results in red, second best in blue.
Model
Acc, 1
Model
Acc.
~ Parameters
GIN
96.485 25.
GAT
95.535
EGT
98.173++.087
100K
CRaWI
97.944=0.00
(LaP(L)
98.05 126
100K
GRIT
98.108 10.1111
*GPS small +MoSEs
98.090.1..500
100K
EGT
98.173:10.087
*GPS
Dig MoSSS
98,273 10.075
400K
GPS(+LapPE)
98.051 126
* *GPS small MoSEa
98. 13.13544.000
100K
*GPS+MoSE
98. 40.0002
GPS MoSE
98. 1..19940..80
200K
* denotes model.
* denotes model.
21

---

Published as a conference paper at ICLR 2025
B.6 RESULTS ON PEPTIDES-STRUCT AND PEPTIDES-FUNT DATASETS
The Peptides-func and Peptides-struct datasets were introduced in the Long Range Graph Benchmark (Dwivedi et al., 2022b). Similar to other chemistry benchmarks, each graph represent peptide, where nodes denote atoms and edges denote the bonds between atoms. However, peptides are generally much larger than the small drug-like molecules in other datasets, such ZINC.
Peptides-fune presents a 10-class multilabel classification task, whereas Peptides- presents an -trrgee regression task. We compare the performance of MoSE with motif patterns Spasm (C=) Spasm(Cs), MoSE with motifs D25 U Cs. and RWSE of length 8 because each of these three encoding have similar "reach" (i.e., the edge-radius each node encoding ' receptive field). order to isolate the power of our encodings, we decide to use a standard self-attention Graph Transfer Dwivedi & Bresson (2020) as our reference model. Since this model does not contain any built-in graph inductive biases, all expressive power is derived from the encodings. Also, note that GT does not utilize the edge features provided in the Peptides dataset because GT does not receive the adjacency matrix explicit input. Table 10 shows that MoSE again outperforms RWSE both Peptides-fun func and Peptides-struct.
Table 10: We benchmark on the peptides-struct and peptides-fune datasets using self-attention Graph Transformer to isolate the performance gains of MoSE vs RWSE. Our pattern families are S = Spasm(C+) Spasm (Ca) and Ω 22 L Cg. Reported results are the mean (# std dev.) of rums with different random seeds. Best results are in red, second best in blue.
Model
Peptides-struct (MAE 4)
Peptides-func (AP
GT+none
0.45440.027
0.44710.017
GT+RWSE
0.344
0.625+0.012
GT+MoSEs (ours)
0.33940.007
0.635+10.011
GT+MoSEn (ours)
0.318+0.010
0.6294+0.011
GT We do not perform hyperparameter tuning on Peptides-fune, using 4-layer GT with width 96 for all encoding types. On Peptides-struct, the training behavior is slightly more erratic, so we conduct a minimal hyperparameter search for each encoding (we search the same configurations on each encoding independently for fair comparison). We omit the details here, but the reader may reference the code repository for exact configurations. Table IT gives a summary of our hyperparameters on Peptides-strue All models (for both tasks) trained for 200 epochs using the AdamW optimizer, batch size 128, and a base LR 0.0003 (annealed with a cosine scheduler).
Table 11: A summary of the GT hyperparameters used for Peptides-struct results.
Model
Layers
Width
Encoding dim
GT+none
4
96
N/A
GT+RWSE
1
36
16
GT+MoSEs (ours)
1
36
24
GT+MoSEa (ours)
36
16
B.7 ZINC EXPERIMENTAL DETAILS & ADDITIONAL. RESULTS
We use the same ZINC dataset setup described above in Appendix B.4.1 All reported results are the mean (+ standard deviation) of 4 runs with different random seeds.
B.7.1 ADDITIONAL RESULTS ZINC WITH EDGE FEATURES
In Table 12 we provide additional results on ZINC-126 12k with edge features. Namely, we reiterate Table 2 while also including R-GCN results for each encoding type, well RWSE+MoSE results where we concatenate the RWSE vector to the MoSE vector for a combined encoding. As stated in the main text, MoSE consistently outperforms RWSE Interestingly, the comparison between MoSE
22

---

Published as a conference paper at ICLR 2025
and the combination of RWSE+MOSE is less consistent. Although RWSE+MoSE contains more information than MoSE alone, there are practical limitations of the combined encoding which may explain its comparatively -wose performance by two positional//trruturaa encodings requires drastic changes in the model hyperparameters, such increase in model width, which may degrade performance information improves it (especially if the two encodings contain redundant information). Regardless, the differences between MoSE and RWSE+MoSE are small across all tasks.
models c.g.. the extra information provided
than the additional encoding
Table 12:
We report mean absolute error (MAE) for graph regression on ZINC-12K (with edge features) across several models. MoSE yields substantial improvements over RWSE for every architecture. Best results are shown in red, second best in blue
Model
Encoding Type
none
RWSE
MoSE
RWSE+MOSE
MLP-E
0,606=10.002
0..61000010
0,347=0.000
0,349#0.000 003
R-GCN
0.413#0.008
0.207
0.197=0.006
0,188=0.000 005
GIN-E
0.243:10.006
0.122.10.003 0.003
0.118:10.00r
0.117:10.00
GIN-E+VN
0.151
0.085 1008500.000
0.068:10.00t
0.064
GT-E
0.195
0.104
0.089=0.018
0.090
GPS
0.119#0.011
0.069+0.001
0.062+40002
0.06540.002
Note: The GPS+RWSE result presented in Tables 12 and is marginally different from the result presented in Table T (0.069 MAE versus 0.070 MAE, respectively). This discrepancy is due to difference in GPS hyperparameters: the results in Table [2llo procedure given in Appendix [B..3] whereas Table |
hyperparameter-seardd pulls the reported GPS+RWSE result from Rampásek et al. 2022) and thus follows their hyperparameter procedure.
B.7.2 ADDITIONAL RESULTS ON ZINC WITHOUT EDGE FEATURES
Dwivedi al. 2023) also present set of experiments that uses the ZINC-12K dataset without edge features. This is because there are number of models that do not take edge features into account. Therefore, we also perform set of experiments report these results in Table [3] Similarly to our experiments with edge features, we see that MoSE consistently outperforms RWSE across all models, whereas the comparison between MoSE and RWSE+MoSE yields mixed results.
ZINC that do not include edge features and
Table 13: We report additional MAE results for various models on ZINC-12K without edge features.
Best results are shown in red, second best in blue
Model
none
RWSE
MoSE
RWSE+MoSE
MLP
0.66340.002
0.263 .006
0.218+0.005
0.202=0.001
GIN
0.29410.011
0. 0.19040..00 200044
0.158
0.168
GT
0.67420.001
0.217=0.00 007
0.209+0.020
0.184=0.001
GPS
0.176
0.116 001
0.10220.001
00105
B.7.3 ZINC HYPERPARAMETERS
We describe the hyperparameters and grid-searches used for our experiments ZINC (Tables 2
3
and 12). Note that all models are restricted to a parameter budget of 500K. See Table [4 for a rough summary of the final hyperparameters.
23

---

Published as a conference paper at ICLR 2025
Table 14: Hyperparameter summary for MoSE results on ZINC from Table
Model
Layers
Hidden Dim
Batch Size
Learning Rate
Epochs
MoSE dim
#1Heads
MLP-E
8
64
0.001
1200
N/A
GIN-E
4
110
128
0.001
1000
42
N/A
GIN-E+VN
4
110
32
0.001
1000
42
N/A
GT-E
10
64
32
0.001
2000
28
4
GPS
8
92-64
0.001
2000
4
MLP-E We perform a grid-search on MLP-E for our ZINC results presented in Table We first fix the following hyperparameters:
Batch Size: 32
Optimizer: Adam
Weight Decay: 0.001
Base LR: 0.001 Scheduler: Cosine
Max Epochs: 1200
LR Warmup Epochs: 10
Then, we search MLP-Etnone on every combination of the following values, with the best values shown in bold:
Node Encoder Layers: [2, 4, 8}
Node Encoder Width: {64, 128, 256]
Edge Encoder Layers: {2, 8
Edge Encoder Width: {32, 64, 128)
Graph Encoder Depth: {1,2.4]
Here, the "graph encoder" is an MLP that follows sum-pooling and precedes the MLP prediction head described in Appendix B.3 The graph encoder width is the of the node encoder width and the edge encoder width. Using the best edge encoder and graph encoder from this first search, we then search E-RSEE and MLP-E+MoSE all combinations of:
Node Encoder Layers: (2,4",8)
Node Encoder Width (64,125 256}
where the best values for MoSE are shown in bold and the best values for RWSE have an asterisk*.
R-GCN and GIN-E We do not conduct hyperparameter searches on our MPNN results on ZINC (0024). Size hyperparameters for R-GCN refer to the results in Table 12] and hyperparameters that are not specific R-GCN or GIN-E used by both models in our experiments. The configurations are as follows:
shown in Tables 2 and 12, opting instead use the configurations from Jin
Batch Size: 128
Optimizer: Adam
Max Epochs: 1000
Base LR: 0.001
LR Scheduler: Reduce on plateau
LR Warmup Epochs: 50
LR Reduce Factor: 0.5
LR Patience (min): 10 (1e-5)
GIN-E Layers: 4
GIN-E Width: 110
R-GCN Layers: 4
R-GCN Width: 125
GIN-E+VN
Again, do not conduct hyperparameter searches for GIN-E+VN ZINC (Table 2). Our configuration is as follows:
Batch Size: 32
Optimizer: AdamW
Max Epochs: 1000
Base LR: 0.001
LR Scheduler: Cosine annealing
LR Warmup Epochs: 50
GIN-E Layers: 4
GIN-E Width: 110
Weight Decay: 0.00001
24

---

Published as a conference paper at ICLR 2025
GT-E
We describe hyperparameter search for ZINC GT-E results given in Table following hyperparameters are fixed:
The
Batch Size:
Optimizer: AdamW
Weight Decay: le-5
Base LR: 0.001 Scheduler: Cosine
Max Epochs: 2000
LR Warmup Epochs: 50
Attention Dropout: 0.5
For all feature injections (none, RWSE, MoSE), we search the following model sizes (formatted as a tuple where components indicate layers, width, and number of heads, respectively):
{8, 84, 4), (10, 64, 4), (4, 120, 8), (4 + 6, 92 + 64, 4))
where (4 + 6, 92 + 64, 4) denotes a varied size model which has an initial width 92 for layers, and then (after being down-projected by a linear layer) has final width of 64 for 6 more layers. The (10, 64, 4) size model was best for all feature injections.
GPS We describe hyperparameter search for ZINC GPS results given in Table 2 The following hyperparameters remain fixed throughout:
MPNN Type: GIN-E
Attention Type: Standard
Batch Size: 32
Optimizer: AdamW Base LR:: 0.001
Weight Decay: 1e-5
Max Epochs: 2000
LR Scheduler: Cosine
LR Warmup Epochs: 50
Attention Dropout: 0.5
For all feature injections (none, RWSE, MoSE), we search the following models sizes (formatted as tuple where components indicate layers, width, and number of heads, respectively):
{8, 76, 4), (10, 64, 4), (4, 104, 8), (2 - 6, 92 - 64, 4)}
where - 6, 92 64, 4) denotes varied size model which has initial width of 92 for 2 layers, and then (after being down-prowe projected by a linear layer) has final width of 64 for 6 more layers. The (8, 76, 4) model performed best for none-encoding, while (2 + 6, 92 64, 4) was best for RWSE and MoSE
For the GRIT results presented in Table we simply remove the RRWP node and node-pair encodings from the configuration used in Ma et al. (2023), and replace them with MoSE that is constructed from Spasm(Cs C7) U Spasm(Cs) (Cs). We summarize the hyperparameters as follows:
GRIT
Layers: 10
Width/Hleads: 64 8
Batch Size: 32
Optimizer: AdamW
Weight Decay: le-5
Base LR: 0,001
Max Epochs: 2000
I.R Scheduler: Cosine
LR Warmup Epochs: 50
Attention Dropout: 0.2
Other Experiments ZINC Hyperparameter searches for RWSE+MoSE. results in Table T2 are conducted identically to the searches for MoSE and RWSE detailed above. Searches for ZINC without edge features (Table 13) are conducted analogously. See the code repository for details.
B.8 8 QM9 EXPERIMENTAL DETAILS ADDITIONAL RESULTS
The QM9 dataset is another molecular dataset that consists of 130,831 graphs (Wu et al. 2018). They are split into 1 110,831 graphs for training, 10,000 for validation, and 10,000 for testing. Node features indicate the atom type and other additional atom features, such its atomic number, the number of Hydrogens connected to it, etc. The edge features indicate bond type between two atoms. The task in this dataset is to predict 13 different quantum chemical properties, ranging from molecule's 's dipole moment (μ)) to its free energy (G). For experiments except those using the GT model (Table include the use of edge features. All GPS results in Table 4 are the mean (+: standard deviation)
25

---

+RWSE+MoSE Published as a conference paper at ICLR 2025
of 5 runs with different random seeds, while results for other models taken directly from their
original works (Brockschmidt 2020; Alon & Yahav 2021 Abboud et al., 2022] Dimitrov et al. 2023). All appendix results in Tables 15 16 and [ those that copied from Table are the mean (+: standard deviation) of runs with different random seeds.
B.8.1 ADDITIONAL RESULTS QM9
Table 15 provides additional results for GPS on QM9 where we use the combined encoding MoSE+RWSE Additionally, provide QM9 experiments with MLP-E (Appendix (3.2) and the GT model (Dwivedi & Bresson 2020) in Table I6 and Table 17 respectively. Across all models, see that MoSE typically outperforms RWSE. There notable exceptions however, such as GT on the tasks UO, U, and H, where GT+RWSE does particularly well (Table 17p. The comparison between MoSE alone and RWSE+MoSE consistently favors the combined encoding on MIP-- and GT (Tables and 17). whereas the results on GPS are more mixed, with more tasks favoring MoSE (Table 15). In Table 16 we also experiment with MLP-E+HHm where Hom denotes the un-rooted homomorphism counts Hom(G,-) with G = Spasm (7) U Spasm(Cs. We inject these counts as graph-level feature by concatenating them to the learned graph representation prior the final MLP prediction head. We see in Table 16]that the node-rooted MoSE consistently outperforms its graph-level counterpart.
Table 15: We report MAE results for GPS with various encodings on the QM9 dataset.
Property
GPS
+RWSE
+MoSE
mu
1.52.10.2
1.47:0.02
1.43:1.02
1.45
alpha
2.62:2.38
1.52:0.27
1.48
1.72+0.11
HOMO
1.17=0.41
0.91
0.91
0.92+0.01
LUMO
0.92=0.01
0.90+0.06
0.8640.01
0.
gap
1.46=00022
1.47+00.0
1.45
1..0
R2
6.82=0.31
6.11
6.22+0.19
6.01+0.03
ZPVE
2.25=0.18
2.63+0.41
2.43+0.27
2.23+0.25
UO
0.96
0.83
0.85
0.80
U
0,81 10.05
0.83
0.75
0.78
0.81
0.86+..15
0.83+0.09
0.87+0.16
G
0.77=0.04
0.83+0.12
0.80
0.72+0.03
Cv
2.56=0.72
1.25+0.05
1.02+0.04
1.03+t0.08
Omega
0.40=0.01
0.39#0.02
0.38+0.01
0.39
Table 16: We report MAE results for MLP-E with various encodings the QM9 dataset.
Property
MLP-E
+RWSE
+MoSE
+Hom
+RWSE+MoSE
mu
5.31
4091
4.88=0.05
5.21
4.84+tu.0
alpha
6.76=10.0
1,08
5.11=0.11
5.52#0.06
4.83++0.09
HOMO
2.96-10.08
2.46+0.08
2.36=0.01
2.75=0.01
2.34+0.02
LUMO
1..04
2.7610.3
2.65
3.1110.01
2.5010.03
gap
4.30210.02
3..0
3.45
4.08 1..07
3.35.10.04
R2
43.69+1.08
26.69+0.31
26.50+0.43
35.85
24.97+0.45
ZPVE
14.36+20.00
10.42+1.24
8.94
11.51
10.28
UO
8.06:1078
5,39
5.30=
5.45
4.74
8.33
5.34
5.19
5,17
5.10+0.62
H
8.19440.3
5.1740.28
4.77-0.16
5.49
5.08
G
7.58
5.83
5,28
5.04
5.03-10.36
Cv
6.06.1014
3.80
3.73
4.1910.16
3.72.00.4
Omega
1.61+0.04
1.29+0.02
1.17=0.02
1.49+0.02
1.2440.05
26

---

Published as a conference paper at ICLR 2025
Table 17: We report MAE results for GT with various encodings on the QM9 dataset.
Property
GT
+RWSE
+MoSE
+RWSE+MoSE
mu
0.025
2.53:10.06
2.43.10.01
2.006
alpha
8.80
1.43:00.33
2.00
1.32.0.01
HOMO
1.72.10.01
1.15.10.01
1.11:0.00
1.08
LUMO
1.63=0.01
1.05=00002
1.02=#0.01
0.99=0.01
gap
2.38=0000
1.67+00001
1.62#t0.01
1.57
R2
2..73
8.30.10.32
10.6941.56
7.80
ZPVE
1..39
2.46:10.04
4.66:12.09
2.37
UO
1.27
0.94
2.56
0.98
U
5.38
0.92+00.33
3.10
1.40
H
5,30=0.17
0.92+0.06
3.49
0.96+0.51
G
0.54
0,88+0.08
2.72++1221
0.63+0.03
Cv
4.32+0.07
1.25+0.01
1.43+0004
1.15+0.01
Omega
1.25
0.50.1..01
0.47
0.4611.01
B.8.2 QM9 HYPERPARAMETERS
We give a rough summary of the hyperparameters that we use for our QM9 experiments in Table 21 and we describe our search procedures below. Different tasks different hyperparameters. The precise setup can be found in our code repository.
MLP-E We do not perform any grid searching for MIP-E QM9 (Table 16) and simply the same hyperparameters for every task and every encoding method, given below:
Node Encoder Depth: 4
Node Encoder Width: 220
Edge Encoder Depth: 2
Edge Encoder Width: 32
Graph Encoder Depth: 3
Graph Encoder Width: 260
Batch Size: 128
Optimizer: Adam
Weight Decay: 0.001
Base LR: 0.001
Max Epochs: 800
LR Scheduler: Cosine
LR Warmup Epochs: 10
Dropout: 0.1
GPS
We perform a 2-round hyperparameter search for GPS results on QM9 (Table the following default hyperparameters remain constant throughout:
[5 Firstly,
Batch Size: 128
Optimizer: AdamW W
Weight Decay: 1e-5
Base LR: 0.001 IRR. Scheduler: Cosine
Max Epochs: 1200
LR Warmup Epochs: 20
Attention Dropout: 0.5
We grid-search each encoding method independently (on reduced 700 epochs). The first round only includes the tasks R2, ZPVE, UO, and gap, and we search over tuples of the form MPNN-type x depth width x heads:
(R-GON, GIN-E) x {(8, 128, 4), (10, 64, 4)} U [[GIINE, 12, 256, 8)}
One should interpret the x symbol as the Cartesian product on sets. Then, the set above describes the tuples (and thus the model configurations) that search over. After performing this search, the best two models for each task are subsequently searched every task/encoding according to the task groups given in Table 20 These task groups are formed according to notions of task similarity described by Gilmer et al. (2017).
For example, the best performing MOS+ model on the gap task in the first round our search is (R-GCN, 10, 64, 4), and the second best model is (GIN-E, 8, 128, 4). Since the LUMO task is in gap's group (as per Table 20). we proceed to search these two GPS+MoSE models, (R-GCN, 10, 64, 4) and (GIN-E, 8, 128, 4), the LUMO task. This second round of searching reveals the final configuration for GPS+MoSE on LUMO, which turns out to be (R-GCN, 10, 64, 4). We repeat this procedure for every task-encoding pair, and end up with the model configurations given in Table 18
27

---

Published as a conference paper at ICLR 2025
GT For GT results QM9 (Table perform the same 2-round search procedure with GPS, starting from the same default configuration (except we use 700 epoch for our final runs instead of 1200). Our first round searches over tuples in depth x width heads base LR:
{(8, 128, 8), (10, 64, 4), (12, 256, 8)) x {0.0001, 0.00001}
Our second round proceeds analogously to that described in the GPS search (again using Table 20)) but highly varied training behavior across the tasks requires us to perform some additional (minor) task-specific tuning in the second round. We omit the details of this tuning here, asking readers to refer the code repository. Ultimately, we get the final model configurations shown in Table
Table 18: The final GPS configurations for QM9 results.
None
RWSE
MoSE
RWSE+MoSE
[R-GCN, 10, 64)
(R-GCN, 10, 64)
(R-GCN, 10, 64)
(R-GCN, 10, 64)
al alpha
[R-GCN, 10, 64)
(R-GCN, 10,64)
(R-GCN, 10, 64)
[R-GCN, 8, 128)
HOMO
(GIN-E, 8, 128)
(R-GCN, 14)
(R-GCN, 14)
(R-GCN, 10,
LUMO
[R-GCN, 10, 64)
(R-GCN, 10,64)
(R-GCN, 10,
(R-GCN, 64)
gap
[R-GCN,
(R-GCN, 10,64)
(R-GCN, 64)
(R-GCN,
R2
[R-GCN,
B,
(R-GCN, 64)
(R-GCN, 8, 128)
ZPVE
(GIN-E, 14)
(GIN-E, 128)
(GIN-E, 128)
(GIN-E, 10, 64)
UO
(GIN-E, 14,
(GIN-E, 128)
(GIN-E, 8, 128)
(R-GCN, 10, 64)
(R-GCN, 64)
(GIN-E, 10, 64)
(GIN-E, 128)
(GIN-E, 10, 64)
H
(GIN-E, 10, 64)
(GIN-E, 14)
(GIN-E, 128)
(GIN-E, 10, 64)
(R-GCN, 10, 64)
(GIN-E, 64)
(GIN-E, 128)
(GIN-E, 10, 64)
Cv
(R-GCN, 10, 64)
(GIN-E, 10, 64)
(R-GCN, 10, 64)
(R-GCN, 10, 64)
Omega
(GIN-E, 64)
(GIN-E, 10, 64)
(R-GCN, 10, 64)
(R-GCN, 10, 64)
*Tuples are given (MPNN-type, depth, width). All of our final models use 4 attention heads.
Table 19: The final GT configurations for QM9 results.
None
RWSE
MoSE
RWSE+MoSE
mu
(8, 128, 10 0)
(12, 256, 10 0)
(12, 256, 10 0)
(12, 256, 10 0)
alpha
128, 10
(12, 252, 25,,10
10 18,
12,256,104
HOMO
(12, 10
104.0)
(12,256,10
(12,256,
LUMO
(12,256, 10-1,.00000
(16,
12,256611-41)
(12,
gap
21,,
216,
12,256,1044.
(12,256,
R2
(10,64,103.0)
212,
20
(12,256,
ZPVE
184,0.1
(8, 18,188,00-.0)
18,128,10-.0
12.12,10-111
UO
(10,64,104,.0
18,128,10-40)
(8, 18,1281001.0
(1,,256,00)
U
112,2661104.0
18,128,104.0)
(8, 12,188100-.0)
(12, 22,
H
(10,64,104.0.3
(8, (8,128,104.0)
(10,64,104.0)
12,
18,48,104.00
(8, (8,128,10440)
(10,64,104.0)
(12, 25,,
Cv
(8, 18,48,18 (8,48,10-.00 10-
(8,128, 10-10)
(8, 12128, 18,11.0001.0 10-10)
(8, 128, 10-
Omega (8,48, 10
(8, 128, 104.0)
(8, 128, 104.0)
(8, 128, 10
Tuples are given (depth, width, base-LR, dropout), where dropout is applied the cood-forward tuned the task-specific portion of second round. The number of heads can be inferred from the depth/width.
modules interweaving attention layers,
28

---

Published as a conference paper at ICLR 2025
Table 20: Task groups for QM9 grid-searching procedure.
1st Round
2nd Round
R2
R2, mu, alpha ZPVE, Omega, Cv
ZPVE
UO
UO, H. G, U gap, HOMO, LUMO
gap
Table 21: High-level summary of hyperparameters used for our QM9 experiments.
Model
Layers
Hidden Dim
Batch Size
Learning Rate
Epochs
#Heads
MLP-E
220 48, 64, 128, 256
128
0.001
800
N/A
GT
8, 10, 12
128
0.001, 0.0001
700
4, 8
GPS
8, 10
64, 128
128
0.001
1200
B.9 SYNTHETIC DATASET EXPERIMENTAL DETAILS
We generate new synthetic dataset where the goal to predict the fractional domination number of graph. The dataset contains 10,000 eandomly-generated Erdös-Rényí graphs, where edge density varies between [0.25, 0.75] and the number of nodes varies between [16, 32]. There are no initial node features edge features provided, so the model must infer the target using only graph structure.
A fractional dominating function of graph G is weight assignment a V(G) + [0, 1] such that for every vertex v, the sum of the weights assigned v and its neighbors is least 1. The total weight of a is given by Eve((g) (<(v). The fractional domination number of G is the smallest total weight of any fractional dominating function on G (Scheinerman & Ullman 2013).
We select a 4-layer MLP and a simple Graph Transformer (Dwivedi & Bresson 2020) for our experiments in order to focus solely on the power of the graph inductive biases (MoSE, RWSE, LapPF). That is, MLP and GT do not receive the adjacency matrix, initial node features, initial edge features node-level positional/structuraal encoding vectors provided.
input: our model must infer the fractional domination number using only the
In Table 5| report the mean (#: standard deviation) of 4 runs with different random seeds. For each model, we do not perform any hyperparameter tuning. In order to control for the large homomorphism count values generated by MoSE this dataset, scale the raw counts down by taking the log of the true values. Please refer to the code repository for specific configurations and data files.
MIPP Our MLP experiments on the synthetic dataset (Table use the following hyperparameters for all encodings:
Depth:
Width: 145
Global Pooling: Mean
Batch Size: 128
Optimizer: Adam
Weight Decay: 0.0
Base LR: 0.001
Max Epochs: 1000
LR Scheduler: Reduce on Plateau
LR Reduce Factor: 0.5
Dropout: 0.2
LR Patience (min): 10 (le-5)
Our GT experiments on the synthetic dataset (Table use the following hyperparameters for all encodings:
GT
Depth: 10
Width: 64
Heads: 4
Batch Size: 128
Optimizer: AdamW
Weight Decay: 0,001
Base LR: 0.0001
Max Epochs: 1200
LR Scheduler: Cosine
LR Warmup Epochs: 30
Attention Dropout: 0.5
29


Reviews:
[{"review_id": "ylDxud1KuE", "reviewer": "Reviewer_MzSj", "summary": "The paper proposes Motif Structural Encoding (MoSE), a novel structural encoding method based on homomorphism counts for graph learning tasks. MoSE leverages homomorphism counts to represent graph structure effectively, aiming to surpass limitations found in common positional and structural encodings such as Random Walk Structural Encoding (RWSE). Theoretically, MoSE demonstrates enhanced expressiveness compared to RWSE and is shown to be independent of the Weisfeiler-Leman (WL) hierarchy, thus providing a broader graph representation power. The paper provides empirical validation, showing that MoSE achieves superior results over other encoding methods on various datasets, including molecular property prediction on ZINC and QM9.", "questions": "Please see Weaknesses", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- MoSE’s homomorphism count-based encoding enhances expressiveness beyond RWSE and aligns well with complex graph structures, as it provides unique structural insights through flexible motif selection.\n- The paper rigorously compares MoSE to established methods and relates its expressiveness to the WL hierarchy, grounding its effectiveness in theoretical proofs.\n- MoSE achieves state-of-the-art results on benchmarks, showcasing its applicability and effectiveness in both real-world and synthetic datasets, particularly in molecular graph prediction tasks.", "weaknesses": "- The performance of MoSE may vary depending on the choice of motif graphs, requiring task-specific tuning to achieve optimal results.\n- Calculating homomorphism counts for large and complex graphs could increase computational requirements, potentially limiting scalability for very large datasets.\n- The theoretical analysis of the expressivity of homomorphism counts has been established and well-studied by recent works (e.g., Jin et al. 2024). It is not very clear what additional theoretical contribution this paper has.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "VN2y56dXZd", "reviewer": "Reviewer_yaCD", "summary": "The paper introduces MoSE, a graph structural encoding based on homomorphism counts. The authors present theoretical arguments suggesting that MoSE has greater expressive power than RWSE and demonstrate competitive empirical performance when integrated with GTs.", "questions": "What are the time and space complexities for computing MoSE encodings? How does the empirical preprocessing time compare to RWSE, RRWP, and LapPE?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "1. The experiments supports the claim that MoSE improves performance on molecular property prediction tasks.\n2. The theoretical arguments provide a plausible explanation for the observed performance gains.\n3. The paper is well-organized and easy to follow.", "weaknesses": "1. The paper focuses on comparing MoSE with RWSE, justified by RWSE's empirical success. However, several recent graph transformers, such as GRIT, can incorporate edge features and encodings. RRWP, as proposed in the GRIT paper, builds on RWSE by incorporating non-diagonal terms and achieves both greater theoretical expressiveness and empirical performance improvements over RWSE. Although the paper shows that GRIT+MoSE outperforms GRIT+RRWP, a theoretical explanation (e.g., specific examples or proofs, similar to the RWSE discussion) would strengthen this claim. Additionally, more detailed discussion on when and why node-level structural encodings remain competitive despite SOTA GNNs' ability to process edge features and encodings would be beneficial.\n2. MoSE's evaluation is based on two molecular datasets, ZINC and QM9. While these datasets are standard in GNN benchmarking, limiting evaluation to these two datasets might be too restrictive.\n    - If the paper's primary aim is to propose an encoding specifically for molecular property prediction (as supported by Example 1, which is plausible), evaluation across additional molecular datasets, such as [PCQM4M](https://pytorch-geometric.readthedocs.io/en/2.5.2/generated/torch_geometric.datasets.PCQM4Mv2.html#torch_geometric.datasets.PCQM4Mv2), [Peptides-struct](https://pytorch-geometric.readthedocs.io/en/2.5.2/generated/torch_geometric.datasets.LRGBDataset.html#torch_geometric.datasets.LRGBDataset), [Peptides-func](https://pytorch-geometric.readthedocs.io/en/2.5.2/generated/torch_geometric.datasets.LRGBDataset.html#torch_geometric.datasets.LRGBDataset), and [AQSOL](https://pytorch-geometric.readthedocs.io/en/2.5.2/generated/torch_geometric.datasets.AQSOL.html#torch_geometric.datasets.AQSOL), could reinforce the validity of MoSE within this domain. Furthermore, clarifying this scope within the paper—by showing that the phenomena in Example 1 generalize across molecular property tasks—would align well with the empirical objectives. My overall rating assumes this as the paper’s main focus.\n    - Conversely, if the goal is to propose a general-purpose graph encoding, then broader evaluation across datasets from other domains is necessary. Evaluating MoSE beyond molecular property datasets would better support a general claim. In this case, datasets from [GNN Benchmark Datasets](https://pytorch-geometric.readthedocs.io/en/2.4.0/generated/torch_geometric.datasets.GNNBenchmarkDataset.html) beyond ZINC can help validate MoSE's general applicability.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "EiFLtuBh2B", "reviewer": "Reviewer_bcpS", "summary": "This paper studies the topic of positional/structural encodings for graph learning which are typically influential in Graph Transformers since these incorporate the graph inductive biases coming from the adjacency matrix as its often not directly used during the self attention computation. The paper investigates the expressivity of one of such encodings, the random walk based structural encoding (RWSE), and address their shortcomings by proposing a homomorphism count based structural encoding called MoSE, which are claimed powerful than the RWSE. The content of the paper presents the characteristics brought by MoSE, also using example illustrations where RWSE may fail, and demonstrates in details their performance advantages on molecular datasets as well as one synthetic dataset of random graphs.", "questions": "included with weaknesses.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "- the paper is a beautiful read on the limitations of existing RW structural encoding for graph transformers, and how the proposed homomorphism count based SE can address it.\n- although the paper does not present a sophisticated new model, the presented SE is carefully studied, and experiments show the advantage (although marginal) brought by MoSE over existing methods in GTs.\n- the comparison section of RWSE and MoSE is insightful and shows RWSE is strictly weaker than MoSE, which is reflected in the experimental results, as well as one of the ZINC illustrations.\n- the proposed structural encoding has no limitations of LapPE such as sign ambiguity", "weaknesses": "- although the MoSE is useful as studied, a concerning factor is of the computational complexity of getting the vectors. how does this compare experimentally?\n- the utility of the propose structural encoding may be limited to addressing specific failure cases of prior SEs as indicated by the minor changes in experimental numbers.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Hx7JGRbrSu", "reviewer": "Reviewer_7PEY", "summary": "The paper introduces a novel positional encoding (PE) for graph transformers based on homomorphism counts and explains it's expressivity in terms of k-WL and the comparison to the random-walk positional encoding. The model is evaluated with two different graph transformers as base models and, over molecule and synthetic data, it shows some improvements.", "questions": "Maybe the authors can point out why they evaluate on only these datasets.", "limitations": "", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The research topic makes sense given the recent insights of using homomorphisms in MPNNs.\n- The paper is well-structured\n- The synthetic data experiment is interesting, and the authors consider two different transformers as base models\n- The model seems to achieve good improvements generally (the number of evidence seems a bit low)", "weaknesses": "- The paper is sometimes annoying to read:\n     - The reader is assumed to know quite some details (e.g., \nW/o knowing the details of RWSE, you don't get the introductory example; the tables mention models like GSN and CIN, which are never explained; oblivious k-WL; l.232 how does GRIT deviate from this? What is Spasm(C7∪C8)?)\n     - The expressivity analysis is interesting but it would have been nice if the papers would have provided some ideas about the proofs, to better get to know the nature of the PE.\n\n- With all the molecular datasets considered, it would have been nice if the evaluation contained some baseline from the chemistry domain, to see how the model compares in realistic settings.\n- Regarding the QM9 experiment, I am computer scientist myself and cannot entirely judge the validity, but wanted to point out that some chemists have strong doubts about this kind of experiment:\n\"While I appreciate that some claim a 1D representation like SMILES can capture some component of a 3D structure, predicting a property of one molecular conformation from a SMILES doesn’t make much sense. \"\nhttps://practicalcheminformatics.blogspot.com/2023/08/we-need-better-benchmarks-for-machine.html\n\n- Beyond that, there's only Zinc12k, which is a bit of a low number of datasets for evaluation\n\nSmaller comments:\n- typo: alternative olibious k-WL\n- l. 296 \"f a graph in G.\" Is this \\mathcal{G} ?\n- FYI There's a recent related work: Deep Homomorphism Networks\nhttps://neurips.cc/virtual/2024/poster/95659", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "sifihaefsF", "reviewer": "Reviewer_aNPU", "summary": "Graph Transformers apply self-attention on graph nodes and to capture the graph structure, they use positional or structural encodings. This paper proposes to use homomorphism count vectors as the employed structural encoding. The authors show that homomorphism counts are more expressive than the commonly used random walk structural encoding. The proposed encoding is evaluated on two molecular property prediction datasets (ZINC-12k and QM9), and also on a synthetic dataset. The results demonstrate that the proposed encoding outperforms other well-known positional and structural encodings across a range of architectures.", "questions": "- The proposed method relies on a finite set of fixed pattern graphs. One needs to choose the types of considered pattern graphs and this usually requires some domain knowledge. In case such knowledge is not available, what kind of patterns should be chosen?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "- The proposed structural encoding seems to better capture the graph structure than other enocodings since it outperforms the baseline encodings (including the commonly used random walk structural encoding) on all considered datasets.\n\n- Besides the empirical results, the paper makes a substantial theoretical contribution since it is shown that the proposed encoding is strictly more expressive than the random walk structural encoding.\n\n- The paper is dense in some parts, but overall it is very well-written and the presentation is clear.", "weaknesses": "- Even though the proposed encoding outperforms the random walk structural encoding, the reported results are not very convincing. On most datasets, the difference in performance between the random walk structural encoding and the proposed encoding is very small. On QM9, the random walk structural encoding even outperforms the proposed encoding for some targets. It is thus unclear whether there is indeed a need for a new encoding in this setting since it does not lead to significance performance gains over the existing method.\n\n- The complexity of computing the proposed encoding is not discussed in the paper, but I would expect that the time required to compute this encoding is significantly higher than the one required to compute the random walk structural encoding. In my understanding, the running time depends on the pattern graph family $\\mathcal{G}$. I would thus suggest the authors report in the paper the pre-processing time for each one of the considered encodings. If the additional computational cost is high and given the marginal performance improvements it offers, why one would choose the proposed encoding over other encodings?\n\n- One of my main concerns with this paper is regarding the novelty of the work. Clearly this is not the first paper to use homomorphism counts in the field of graph machine learning. Several previous works which are discussed in section 2 in the paper have annotated nodes with homomorphism counts. The main difference between those works and this paper is that the learning models employed in this paper are Graph Transformers and not MPNNs. However, I doubt if this in enough for the paper to be considered novel.\n\n- The authors choose to integrate the proposed encoding into Graph Transformers, but all the theoretical results presented in the paper hold for the encoding itself (no assumptions are made about the underlying model). Thus, Graph Transformers could be replaced with MPNNs, and all the results would still hold. I thus wonder why the authors chose to place that much focus of the paper on Graph Transformers.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)