Homomorphism Counts as Structural Encodings for Graph Learning

## Abstract

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 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 widely studied molecular property prediction datasets.

## 1 Introduction

Graph Neural Networks (GNNs) have been the prominent approach for graph machine learning in the last decade. Most conventional GNNs fall under the framework of 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., ). More recently, Transformer architectures (Vaswani et al., ) have been applied to the graph domain and achieved impressive empirical performance (Rampásek et al., ; Ma et al., ), especially in molecular property prediction.

While MPNNs operate by exchanging messages between adjacent nodes in a graph, Transformers can be seen as a 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 an 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 message-passing layers (Yun et al., ; Rampásek et al., ; Bar-Shalom et al., ) or by incorporating additional pre-computed features that encode the topological context of each node. These additional features are referred to as positional or structural encodings. Common encodings include the Laplacian positional encoding (LapPE) (Dwivedi et al., ) and the random-walk structural encoding (RWSE) (Dwivedi et al., ). The quality of these encodings are reported as the key ingredients in the success of Transformers on graphs (Dwivedi et al., ; Rampásek et al., ).

Motivation. While empirical studies have observed the impact of structural or positional encodings on model performance (Dwivedi et al., ; Rampásek et al., ), our theoretical understanding of the expressive power of different encodings remains limited. This represents an important gap in the literature, especially since the expressive power of Transformer-based architectures heavily rely on the specific choice of the structural or positional encoding (Rosenbluth et al., ).
Let us consider RWSE, which has been empirically reported as the most successful encoding on molecular benchmarks (Rampásek et al., ). We now illustrate a serious limitation of RWSE in its power to distinguish nodes.

Figure: (a) The nodes $u_{1}$ and $u_{2}$ (resp., $v_{1}$ and $v_{2}$) can be distinguished by 1-WL, but not by RWSE.
Refer to caption: extracted/5948923/molecule-labeled.png

How expressive is RWSE?
The expressive power of MPNNs is upper bounded by the *1-dimensional Weisfeiler Leman graph isomorphism test (1-WL)* (Xu et al., ; Morris et al., ). This means that the node invariants computed by MPNNs are at most as powerful as the node invariants computed by 1-WL. As a result, an MPNN can distinguish two nodes *only if* 1-WL can distinguish them. Some MPNN architectures, such as Graph Isomorphism Networks (GIN) (Xu et al., ), can match this expressiveness bound and distinguish any pair of nodes that can be distinguished 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(^1^11Throughout the paper, we refer to the folklore version of the WL hierarchy (Grohe & Otto, ).)(Proposition 4.4). Additionally, RWSE node invariants are incomparable to node invariants computed by 1-WL (Proposition 4.7). In fact, there are simple node pairs which can be distinguished by 1-WL but not by RWSE (and vice versa).

###### Example 1.1 .

Consider the nodes from the graphs $G$ and $H$ from Figure 1 (a). Observe that the nodes $u_{1}$ and $u_{2}$ can be distinguished by 1-WL. Interestingly, however, they are indistinguishable to RWSE for *all* lengths $\ell$ of the considered random walk. This observation also applies to the nodes $v_{1}$ and $v_{2}$. Moreover, this limitation is not merely of theoretical interest, as it readily applies to real-world molecules, where the use of RWSE is prominent. Figure 1 (b) depicts a molecule from the ZINC dataset, where the nodes $u_{1}$ and $u_{2}$ (resp., $v_{1}$ and $v_{2}$) cannot be distinguished by RWSE although they can be distinguished by MPNNs. In practical terms, this implies that RWSE cannot distinguish a Dinitrile group from a Morpholine group.    $\triangle$

Motif structural encodings as a flexible and powerful approach. In this paper, we propose motif structural encodings (MoSE) as structural encodings that leverage homomorphism count vectors to capture the graph structure. Homomorphism counts have been investigated in the context of MPNNs to overcome well-known theoretical limitations in their expressivity (Barceló et al., ; Jin et al., ) with promising theoretical and empirical findings (see Section 2). Building on the existing literature, we show that MoSE is a parameterizable, flexible, and powerful alternative to existing positional and structural encoding schemes in the context of Transformers. In fact, we show that unlike RWSE, MoSE cannot be strictly confined to one particular level of the WL hierarchy (Proposition 4.3), and MoSE can provide non-trivial expressiveness gains exceeding that achieved by RWSE (Theorem 4.6).

###### Example 1.2 .

Consider the graphs $G$ and $H$ from our running example, and observe that $H$ has a cycle of length six, while $G$ has no cycles. The node-level homomorphism counts $\mathsf{Hom}_{\mathrel{\mathchoice{\mkern 2.0mu\leavevmode\leavevmode\hbox{
\leavevmode\hbox to6.26pt{\vbox to5.58pt{\pgfpicture\makeatletter\hbox{\hskip 0
.0pt\lower-0.58333pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }
\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}
\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }
\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox to0.0pt{{}{}{}{}
\pgfsys@moveto{0.0pt}{-0.58333pt}\pgfsys@lineto{0.0pt}{5.0011pt}\pgfsys@lineto
{6.26111pt}{5.0011pt}\pgfsys@lineto{6.26111pt}{-0.58333pt}\pgfsys@closepath
\pgfsys@clipnext\pgfsys@discardpath\pgfsys@invoke{ }{{{}{}{{}}{}
{{}{{}}}{{}{}}{}{{}{}}
{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1.
0}{0.0pt}{0.0pt}\pgfsys@invoke{ }\hbox{{\leavevmode\hbox{\hskip-2.68335pt\hbox
{\set@color{$\displaystyle\vphantom{+}{\shortrightarrow}$}}}}}\pgfsys@invoke{
\lxSVG@closescope }\pgfsys@endscope}}}}
{}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope }
\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}{\mkern 2.0mu
\leavevmode\leavevmode\hbox{ \leavevmode\hbox to6.26pt{\vbox to5.58pt{
\pgfpicture\makeatletter\hbox{\hskip 0.0pt\lower-0.58333pt\hbox to0.0pt{
\pgfsys@beginscope\pgfsys@invoke{ }\definecolor{pgfstrokecolor}{rgb}{0,0,0}
\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0}
{0}\pgfsys@invoke{ }\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to
0.0pt{{}{}{}{}\pgfsys@moveto{0.0pt}{-0.58333pt}\pgfsys@lineto{0.0pt}{5.0011pt}
\pgfsys@lineto{6.26111pt}{5.0011pt}\pgfsys@lineto{6.26111pt}{-0.58333pt}
\pgfsys@closepath\pgfsys@clipnext\pgfsys@discardpath\pgfsys@invoke{ }{{{}{}{{}
}{}
{{}{{}}}{{}{}}{}{{}{}}
{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1.
0}{0.0pt}{0.0pt}\pgfsys@invoke{ }\hbox{{\leavevmode\hbox{\hskip-2.68335pt\hbox
{\set@color{$\textstyle\vphantom{+}{\shortrightarrow}$}}}}}\pgfsys@invoke{
\lxSVG@closescope }\pgfsys@endscope}}}}
{}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope }
\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}{\mkern 2.0mu
\leavevmode\leavevmode\hbox{ \leavevmode\hbox to4.38pt{\vbox to3.91pt{
\pgfpicture\makeatletter\hbox{\hskip 0.0pt\lower-0.40833pt\hbox to0.0pt{
\pgfsys@beginscope\pgfsys@invoke{ }\definecolor{pgfstrokecolor}{rgb}{0,0,0}
\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0}
{0}\pgfsys@invoke{ }\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to
0.0pt{{}{}{}{}\pgfsys@moveto{0.0pt}{-0.40833pt}\pgfsys@lineto{0.0pt}{3.50076pt
}\pgfsys@lineto{4.38277pt}{3.50076pt}\pgfsys@lineto{4.38277pt}{-0.40833pt}
\pgfsys@closepath\pgfsys@clipnext\pgfsys@discardpath\pgfsys@invoke{ }{{{}{}{{}
}{}
{{}{{}}}{{}{}}{}{{}{}}
{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1.
0}{0.0pt}{0.0pt}\pgfsys@invoke{ }\hbox{{\leavevmode\hbox{\hskip-1.87834pt\hbox
{\set@color{$\scriptstyle\vphantom{+}{\shortrightarrow}$}}}}}\pgfsys@invoke{
\lxSVG@closescope }\pgfsys@endscope}}}}
{}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope }
\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}{\mkern 2.0mu
\leavevmode\leavevmode\hbox{ \leavevmode\hbox to3.13pt{\vbox to2.79pt{
\pgfpicture\makeatletter\hbox{\hskip 0.0pt\lower-0.29166pt\hbox to0.0pt{
\pgfsys@beginscope\pgfsys@invoke{ }\definecolor{pgfstrokecolor}{rgb}{0,0,0}
\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0}
{0}\pgfsys@invoke{ }\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to
0.0pt{{}{}{}{}\pgfsys@moveto{0.0pt}{-0.29166pt}\pgfsys@lineto{0.0pt}{2.50055pt
}\pgfsys@lineto{3.13055pt}{2.50055pt}\pgfsys@lineto{3.13055pt}{-0.29166pt}
\pgfsys@closepath\pgfsys@clipnext\pgfsys@discardpath\pgfsys@invoke{ }{{{}{}{{}
}{}
{{}{{}}}{{}{}}{}{{}{}}
{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1.
0}{0.0pt}{0.0pt}\pgfsys@invoke{ }\hbox{{\leavevmode\hbox{\hskip-1.34167pt\hbox
{\set@color{$\scriptscriptstyle\vphantom{+}{\shortrightarrow}$}}}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}}
{}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope }
\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}}v_{1}}(\leavevmode
\hbox to0pt{\vbox to0pt{\pgfpicture\makeatletter\hbox{\hskip 0.0pt\lower 0.0pt
\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }\definecolor{pgfstrokecolor}{
rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }
\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\pgfsys@setlinewidth{0.4pt}
\pgfsys@invoke{ }\nullfont\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}
}{{}}\GraphInit[vstyle=Classic]\SetVertexNoLabel\SetVertexMath\SetVertexSimple
[MinSize = 1pt,
LineWidth = 0pt,
LineColor = black,FillColor = black]
\par\SetGraphUnit{1}
\Vertices{circle}{A,B,C,D,E,F}
\Edges(A,B,C,D,E,F,A)
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{}{}{}\hss}
\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hss}}
\lxSVG@closescope\endpgfpicture}},G)\neq\mathsf{Hom}_{\mathrel{\mathchoice{
\mkern 2.0mu\leavevmode\leavevmode\hbox{ \leavevmode\hbox to6.26pt{\vbox to
5.58pt{\pgfpicture\makeatletter\hbox{\hskip 0.0pt\lower-0.58333pt\hbox to0.0pt
{\pgfsys@beginscope\pgfsys@invoke{ }\definecolor{pgfstrokecolor}{rgb}{0,0,0}
\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0}
{0}\pgfsys@invoke{ }\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to
0.0pt{{}{}{}{}\pgfsys@moveto{0.0pt}{-0.58333pt}\pgfsys@lineto{0.0pt}{5.0011pt}
\pgfsys@lineto{6.26111pt}{5.0011pt}\pgfsys@lineto{6.26111pt}{-0.58333pt}
\pgfsys@closepath\pgfsys@clipnext\pgfsys@discardpath\pgfsys@invoke{ }{{{}{}{{}
}{}
{{}{{}}}{{}{}}{}{{}{}}
{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1.
0}{0.0pt}{0.0pt}\pgfsys@invoke{ }\hbox{{\leavevmode\hbox{\hskip-2.68335pt\hbox
{\set@color{$\displaystyle\vphantom{+}{\shortrightarrow}$}}}}}\pgfsys@invoke{
\lxSVG@closescope }\pgfsys@endscope}}}}
{}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope }
\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}{\mkern 2.0mu
\leavevmode\leavevmode\hbox{ \leavevmode\hbox to6.26pt{\vbox to5.58pt{
\pgfpicture\makeatletter\hbox{\hskip 0.0pt\lower-0.58333pt\hbox to0.0pt{
\pgfsys@beginscope\pgfsys@invoke{ }\definecolor{pgfstrokecolor}{rgb}{0,0,0}
\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0}
{0}\pgfsys@invoke{ }\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to
0.0pt{{}{}{}{}\pgfsys@moveto{0.0pt}{-0.58333pt}\pgfsys@lineto{0.0pt}{5.0011pt}
\pgfsys@lineto{6.26111pt}{5.0011pt}\pgfsys@lineto{6.26111pt}{-0.58333pt}
\pgfsys@closepath\pgfsys@clipnext\pgfsys@discardpath\pgfsys@invoke{ }{{{}{}{{}
}{}
{{}{{}}}{{}{}}{}{{}{}}
{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1.
0}{0.0pt}{0.0pt}\pgfsys@invoke{ }\hbox{{\leavevmode\hbox{\hskip-2.68335pt\hbox
{\set@color{$\textstyle\vphantom{+}{\shortrightarrow}$}}}}}\pgfsys@invoke{
\lxSVG@closescope }\pgfsys@endscope}}}}
{}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope }
\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}{\mkern 2.0mu
\leavevmode\leavevmode\hbox{ \leavevmode\hbox to4.38pt{\vbox to3.91pt{
\pgfpicture\makeatletter\hbox{\hskip 0.0pt\lower-0.40833pt\hbox to0.0pt{
\pgfsys@beginscope\pgfsys@invoke{ }\definecolor{pgfstrokecolor}{rgb}{0,0,0}
\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0}
{0}\pgfsys@invoke{ }\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to
0.0pt{{}{}{}{}\pgfsys@moveto{0.0pt}{-0.40833pt}\pgfsys@lineto{0.0pt}{3.50076pt
}\pgfsys@lineto{4.38277pt}{3.50076pt}\pgfsys@lineto{4.38277pt}{-0.40833pt}
\pgfsys@closepath\pgfsys@clipnext\pgfsys@discardpath\pgfsys@invoke{ }{{{}{}{{}
}{}
{{}{{}}}{{}{}}{}{{}{}}
{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1.
0}{0.0pt}{0.0pt}\pgfsys@invoke{ }\hbox{{\leavevmode\hbox{\hskip-1.87834pt\hbox
{\set@color{$\scriptstyle\vphantom{+}{\shortrightarrow}$}}}}}\pgfsys@invoke{
\lxSVG@closescope }\pgfsys@endscope}}}}
{}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope }
\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}{\mkern 2.0mu
\leavevmode\leavevmode\hbox{ \leavevmode\hbox to3.13pt{\vbox to2.79pt{
\pgfpicture\makeatletter\hbox{\hskip 0.0pt\lower-0.29166pt\hbox to0.0pt{
\pgfsys@beginscope\pgfsys@invoke{ }\definecolor{pgfstrokecolor}{rgb}{0,0,0}
\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0}
{0}\pgfsys@invoke{ }\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to
0.0pt{{}{}{}{}\pgfsys@moveto{0.0pt}{-0.29166pt}\pgfsys@lineto{0.0pt}{2.50055pt
}\pgfsys@lineto{3.13055pt}{2.50055pt}\pgfsys@lineto{3.13055pt}{-0.29166pt}
\pgfsys@closepath\pgfsys@clipnext\pgfsys@discardpath\pgfsys@invoke{ }{{{}{}{{}
}{}
{{}{{}}}{{}{}}{}{{}{}}
{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1.
0}{0.0pt}{0.0pt}\pgfsys@invoke{ }\hbox{{\leavevmode\hbox{\hskip-1.34167pt\hbox
{\set@color{$\scriptscriptstyle\vphantom{+}{\shortrightarrow}$}}}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}}
{}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope }
\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}}v_{2}}(\leavevmode
\hbox to0pt{\vbox to0pt{\pgfpicture\makeatletter\hbox{\hskip 0.0pt\lower 0.0pt
\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }\definecolor{pgfstrokecolor}{
rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }
\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\pgfsys@setlinewidth{0.4pt}
\pgfsys@invoke{ }\nullfont\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}
}{{}}\GraphInit[vstyle=Classic]\SetVertexNoLabel\SetVertexMath\SetVertexSimple
[MinSize = 1pt,
LineWidth = 0pt,
LineColor = black,FillColor = black]
\par\SetGraphUnit{1}
\Vertices{circle}{A,B,C,D,E,F}
\Edges(A,B,C,D,E,F,A)
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{}{}{}\hss}
\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hss}}
\lxSVG@closescope\endpgfpicture}},H)$ (defined formally in Section 4.2) are not equal, which provides sufficient information to distinguish these nodes. Analogous statements can also be made for $u_{1}$ and $u_{2}$.    $\triangle$

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).
- •
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 the theoretical findings and demonstrate efficacy of MoSE on a variety of benchmarks (Section 5). We report state-of-the-art performance on the widely studied ZINC-12k dataset by simply replacing a random-walk based encoding with MoSE in an existing Transformer model. We also achieve competitive results on the QM9 molecular dataset for almost all properties.
- •
Finally, we experiment on a new synthetic dataset that further highlights the wide-ranging applicability of homomorphism counts as a graph inductive bias.

###### Example 1.1 .

###### Example 1.2 .

## 2 Related Work

(Graph) Transformers and Encodings.
Vaswani et al. () first highlighted the power of self-attention when they introduced their Transformer architecture. Dwivedi & Bresson () generalized the concepts presented in Vaswani et al. () to the graph domain. In recent years, several different Graph Transformer architectures have arisen. Yun et al. () first combined message-passing layers with Transformer layers, and other models have followed this approach (Rampásek et al., ; Bar-Shalom et al., ; Shirzad et al., ). Relatedly, Transformer architectures dedicated for knowledge graphs have also been developed (Zhang et al., ; Liu et al., ). Shehzad et al. () presents a survey of existing Graph Transformer models and how they compare to each other.

A key component to the success of graph transformer models is the use of effective graph inductive biases (Dwivedi et al., ). Laplacian positional encodings (LapPE), which were introduced by Dwivedi & Bresson (), are a popular choice, but they break invariance(^2^22By sacrificing invariance, it becomes much easier to design very expressive architectures. In fact, Graph Transformer architectures with LapPE are universal (Kreuzer et al., ), but so is a 2-layer MLP, or a single-layer GNN under LapPE (see Proposition 3.1 of Rosenbluth et al. ()).), as they are *not* invariant to the changes of signs and basis of eigenvectors (Lim et al., ; ).
Rampásek et al. () presented a framework to build general and scalable Graph Transformer models, and performed ablations with a suite of different encoding types, including random-walk structural encodings (RWSE). Ying et al. () introduced Graphormer, which uses an attention mechanism that is based on shortest-path (and related) distances in a graph. Ma et al. () presented GRIT as a novel framework that relies solely on Relative Random Walk Probabilities (RRWPs) for inductive bias.

Expressive power of MPNNs. MPNNs capture the vast majority of GNNs (Gilmer et al., ) and their expressive power is upper bounded by 1-WL (Xu et al., ; Morris et al., ). This limitation has motivated a large body of work, including *higher-order* GNN architectures (Morris et al., ; Maron et al., ; ; Keriven & Peyré, ), GNNs with unique node features (Loukas, ), or GNNs with random features (Sato et al., ; Abboud et al., ) to achieve higher expressive power. Expressive power of GNNs has also been evaluated in terms of their ability to detect graph components, such as biconnected components (Zhang et al., ), and fully expressive architectures designed for special graph classes, e.g., for planar graphs (Dimitrov et al., ).

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. Bouritsas et al. () present an early work that enhances node feature encodings for GNNs by counting adjacent subgraph isomorphism of different patterns. Barceló et al. () follow up on this work by proposing to instead count the number of homomorphism from a set of pertinent substructures. Several other works have identified homomorphism counts as a key tool for understanding the expressive power of MPNNs (Neuen, ; Lanzinger & Barceló, ; Wang & Zhang, ). Zhang et al. () 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 (Curticapean et al., ; Bressan et al., ; Roth & Schmitt, ), these expressiveness results can be lifted to a wide range of functions (Lanzinger & Barceló, ).
As such, Jin et al. () 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 to enhance the expressivity of GNNs.

## 3 Preliminaries

Graphs and Homomorphism Counts. An undirected *graph* is a set of *nodes* $V(G)$ and a set of *edges* $E(G)\subseteq V(G)\times V(G)$ which satisfy symmetry: $(u,v)\in E(G)$ if and only if $(v,u)\in E(G)$. Unless otherwise stated, we take all graphs to be finite, and we take all graphs to be *simple*: $(v,v)\notin E(G)$ for all $v\in V(G)$ and there exists at most one edge (up to edge symmetry) between any pair of nodes. We describe nodes $u,v\in V(G)$ as *adjacent* if $(u,v)\in E(G)$. The set of all nodes adjacent to $v\in V(G)$ is the *neighborhood* of $v$, notated $\mathcal{N}(v)$. The number of nodes $|\mathcal{N}(v)|$ is the *degree* of $v$, notated $d(v)$.

A *homomorphism* from graph $G$ to graph $H$ is a function $f:V(G)\to V(H)$ such that $(u,v)\in E(G)$ implies $(f(u),f(v))\in E(H)$. We say a homomorphism is an *isomorphism* if the function $f$ is bijective, and if it additionally satisfies $(u,v)\in E(G)$ if and only if $(f(u),f(v))\in E(H)$. In this case, we describe the graphs $G$ and $H$ as being *isomorphic*, denoted $G\cong H$. We write $\text{Hom}(G,H)$ for the number of homomorphisms from $G$ to $H$. If we restrict to counting only homomorphisms which maps a particular node $g\in V(G)$ to the node $h\in V(H)$, we denote this *rooted homomorphism count* as $\text{Hom}_{g\mathrel{\mathchoice{\mkern 2.0mu\leavevmode\leavevmode\hbox{
\leavevmode\hbox to6.26pt{\vbox to5.58pt{\pgfpicture\makeatletter\hbox{\hskip 0
.0pt\lower-0.58333pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }
\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}
\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }
\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox to0.0pt{{}{}{}{}
\pgfsys@moveto{0.0pt}{-0.58333pt}\pgfsys@lineto{0.0pt}{5.0011pt}\pgfsys@lineto
{6.26111pt}{5.0011pt}\pgfsys@lineto{6.26111pt}{-0.58333pt}\pgfsys@closepath
\pgfsys@clipnext\pgfsys@discardpath\pgfsys@invoke{ }{{{}{}{{}}{}
{{}{{}}}{{}{}}{}{{}{}}
{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1.
0}{0.0pt}{0.0pt}\pgfsys@invoke{ }\hbox{{\leavevmode\hbox{\hskip-2.68335pt\hbox
{\set@color{$\displaystyle\vphantom{+}{\shortrightarrow}$}}}}}\pgfsys@invoke{
\lxSVG@closescope }\pgfsys@endscope}}}}
{}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope }
\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}{\mkern 2.0mu
\leavevmode\leavevmode\hbox{ \leavevmode\hbox to6.26pt{\vbox to5.58pt{
\pgfpicture\makeatletter\hbox{\hskip 0.0pt\lower-0.58333pt\hbox to0.0pt{
\pgfsys@beginscope\pgfsys@invoke{ }\definecolor{pgfstrokecolor}{rgb}{0,0,0}
\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0}
{0}\pgfsys@invoke{ }\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to
0.0pt{{}{}{}{}\pgfsys@moveto{0.0pt}{-0.58333pt}\pgfsys@lineto{0.0pt}{5.0011pt}
\pgfsys@lineto{6.26111pt}{5.0011pt}\pgfsys@lineto{6.26111pt}{-0.58333pt}
\pgfsys@closepath\pgfsys@clipnext\pgfsys@discardpath\pgfsys@invoke{ }{{{}{}{{}
}{}
{{}{{}}}{{}{}}{}{{}{}}
{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1.
0}{0.0pt}{0.0pt}\pgfsys@invoke{ }\hbox{{\leavevmode\hbox{\hskip-2.68335pt\hbox
{\set@color{$\textstyle\vphantom{+}{\shortrightarrow}$}}}}}\pgfsys@invoke{
\lxSVG@closescope }\pgfsys@endscope}}}}
{}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope }
\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}{\mkern 2.0mu
\leavevmode\leavevmode\hbox{ \leavevmode\hbox to4.38pt{\vbox to3.91pt{
\pgfpicture\makeatletter\hbox{\hskip 0.0pt\lower-0.40833pt\hbox to0.0pt{
\pgfsys@beginscope\pgfsys@invoke{ }\definecolor{pgfstrokecolor}{rgb}{0,0,0}
\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0}
{0}\pgfsys@invoke{ }\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to
0.0pt{{}{}{}{}\pgfsys@moveto{0.0pt}{-0.40833pt}\pgfsys@lineto{0.0pt}{3.50076pt
}\pgfsys@lineto{4.38277pt}{3.50076pt}\pgfsys@lineto{4.38277pt}{-0.40833pt}
\pgfsys@closepath\pgfsys@clipnext\pgfsys@discardpath\pgfsys@invoke{ }{{{}{}{{}
}{}
{{}{{}}}{{}{}}{}{{}{}}
{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1.
0}{0.0pt}{0.0pt}\pgfsys@invoke{ }\hbox{{\leavevmode\hbox{\hskip-1.87834pt\hbox
{\set@color{$\scriptstyle\vphantom{+}{\shortrightarrow}$}}}}}\pgfsys@invoke{
\lxSVG@closescope }\pgfsys@endscope}}}}
{}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope }
\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}{\mkern 2.0mu
\leavevmode\leavevmode\hbox{ \leavevmode\hbox to3.13pt{\vbox to2.79pt{
\pgfpicture\makeatletter\hbox{\hskip 0.0pt\lower-0.29166pt\hbox to0.0pt{
\pgfsys@beginscope\pgfsys@invoke{ }\definecolor{pgfstrokecolor}{rgb}{0,0,0}
\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0}
{0}\pgfsys@invoke{ }\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to
0.0pt{{}{}{}{}\pgfsys@moveto{0.0pt}{-0.29166pt}\pgfsys@lineto{0.0pt}{2.50055pt
}\pgfsys@lineto{3.13055pt}{2.50055pt}\pgfsys@lineto{3.13055pt}{-0.29166pt}
\pgfsys@closepath\pgfsys@clipnext\pgfsys@discardpath\pgfsys@invoke{ }{{{}{}{{}
}{}
{{}{{}}}{{}{}}{}{{}{}}
{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1.
0}{0.0pt}{0.0pt}\pgfsys@invoke{ }\hbox{{\leavevmode\hbox{\hskip-1.34167pt\hbox
{\set@color{$\scriptscriptstyle\vphantom{+}{\shortrightarrow}$}}}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}}
{}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope }
\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}}h}(G,H)$. Sometimes the choice of $g$ is unimportant, so we use $\text{Hom}_{\mathrel{\mathchoice{\mkern 2.0mu\leavevmode\leavevmode\hbox{
\leavevmode\hbox to6.26pt{\vbox to5.58pt{\pgfpicture\makeatletter\hbox{\hskip 0
.0pt\lower-0.58333pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }
\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}
\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }
\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox to0.0pt{{}{}{}{}
\pgfsys@moveto{0.0pt}{-0.58333pt}\pgfsys@lineto{0.0pt}{5.0011pt}\pgfsys@lineto
{6.26111pt}{5.0011pt}\pgfsys@lineto{6.26111pt}{-0.58333pt}\pgfsys@closepath
\pgfsys@clipnext\pgfsys@discardpath\pgfsys@invoke{ }{{{}{}{{}}{}
{{}{{}}}{{}{}}{}{{}{}}
{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1.
0}{0.0pt}{0.0pt}\pgfsys@invoke{ }\hbox{{\leavevmode\hbox{\hskip-2.68335pt\hbox
{\set@color{$\displaystyle\vphantom{+}{\shortrightarrow}$}}}}}\pgfsys@invoke{
\lxSVG@closescope }\pgfsys@endscope}}}}
{}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope }
\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}{\mkern 2.0mu
\leavevmode\leavevmode\hbox{ \leavevmode\hbox to6.26pt{\vbox to5.58pt{
\pgfpicture\makeatletter\hbox{\hskip 0.0pt\lower-0.58333pt\hbox to0.0pt{
\pgfsys@beginscope\pgfsys@invoke{ }\definecolor{pgfstrokecolor}{rgb}{0,0,0}
\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0}
{0}\pgfsys@invoke{ }\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to
0.0pt{{}{}{}{}\pgfsys@moveto{0.0pt}{-0.58333pt}\pgfsys@lineto{0.0pt}{5.0011pt}
\pgfsys@lineto{6.26111pt}{5.0011pt}\pgfsys@lineto{6.26111pt}{-0.58333pt}
\pgfsys@closepath\pgfsys@clipnext\pgfsys@discardpath\pgfsys@invoke{ }{{{}{}{{}
}{}
{{}{{}}}{{}{}}{}{{}{}}
{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1.
0}{0.0pt}{0.0pt}\pgfsys@invoke{ }\hbox{{\leavevmode\hbox{\hskip-2.68335pt\hbox
{\set@color{$\textstyle\vphantom{+}{\shortrightarrow}$}}}}}\pgfsys@invoke{
\lxSVG@closescope }\pgfsys@endscope}}}}
{}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope }
\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}{\mkern 2.0mu
\leavevmode\leavevmode\hbox{ \leavevmode\hbox to4.38pt{\vbox to3.91pt{
\pgfpicture\makeatletter\hbox{\hskip 0.0pt\lower-0.40833pt\hbox to0.0pt{
\pgfsys@beginscope\pgfsys@invoke{ }\definecolor{pgfstrokecolor}{rgb}{0,0,0}
\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0}
{0}\pgfsys@invoke{ }\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to
0.0pt{{}{}{}{}\pgfsys@moveto{0.0pt}{-0.40833pt}\pgfsys@lineto{0.0pt}{3.50076pt
}\pgfsys@lineto{4.38277pt}{3.50076pt}\pgfsys@lineto{4.38277pt}{-0.40833pt}
\pgfsys@closepath\pgfsys@clipnext\pgfsys@discardpath\pgfsys@invoke{ }{{{}{}{{}
}{}
{{}{{}}}{{}{}}{}{{}{}}
{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1.
0}{0.0pt}{0.0pt}\pgfsys@invoke{ }\hbox{{\leavevmode\hbox{\hskip-1.87834pt\hbox
{\set@color{$\scriptstyle\vphantom{+}{\shortrightarrow}$}}}}}\pgfsys@invoke{
\lxSVG@closescope }\pgfsys@endscope}}}}
{}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope }
\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}{\mkern 2.0mu
\leavevmode\leavevmode\hbox{ \leavevmode\hbox to3.13pt{\vbox to2.79pt{
\pgfpicture\makeatletter\hbox{\hskip 0.0pt\lower-0.29166pt\hbox to0.0pt{
\pgfsys@beginscope\pgfsys@invoke{ }\definecolor{pgfstrokecolor}{rgb}{0,0,0}
\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0}
{0}\pgfsys@invoke{ }\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to
0.0pt{{}{}{}{}\pgfsys@moveto{0.0pt}{-0.29166pt}\pgfsys@lineto{0.0pt}{2.50055pt
}\pgfsys@lineto{3.13055pt}{2.50055pt}\pgfsys@lineto{3.13055pt}{-0.29166pt}
\pgfsys@closepath\pgfsys@clipnext\pgfsys@discardpath\pgfsys@invoke{ }{{{}{}{{}
}{}
{{}{{}}}{{}{}}{}{{}{}}
{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1.
0}{0.0pt}{0.0pt}\pgfsys@invoke{ }\hbox{{\leavevmode\hbox{\hskip-1.34167pt\hbox
{\set@color{$\scriptscriptstyle\vphantom{+}{\shortrightarrow}$}}}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}}
{}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope }
\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}}h}(G,H)$ to notate the rooted homomorphism count $\text{Hom}_{g\mathrel{\mathchoice{\mkern 2.0mu\leavevmode\leavevmode\hbox{
\leavevmode\hbox to6.26pt{\vbox to5.58pt{\pgfpicture\makeatletter\hbox{\hskip 0
.0pt\lower-0.58333pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }
\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}
\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }
\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox to0.0pt{{}{}{}{}
\pgfsys@moveto{0.0pt}{-0.58333pt}\pgfsys@lineto{0.0pt}{5.0011pt}\pgfsys@lineto
{6.26111pt}{5.0011pt}\pgfsys@lineto{6.26111pt}{-0.58333pt}\pgfsys@closepath
\pgfsys@clipnext\pgfsys@discardpath\pgfsys@invoke{ }{{{}{}{{}}{}
{{}{{}}}{{}{}}{}{{}{}}
{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1.
0}{0.0pt}{0.0pt}\pgfsys@invoke{ }\hbox{{\leavevmode\hbox{\hskip-2.68335pt\hbox
{\set@color{$\displaystyle\vphantom{+}{\shortrightarrow}$}}}}}\pgfsys@invoke{
\lxSVG@closescope }\pgfsys@endscope}}}}
{}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope }
\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}{\mkern 2.0mu
\leavevmode\leavevmode\hbox{ \leavevmode\hbox to6.26pt{\vbox to5.58pt{
\pgfpicture\makeatletter\hbox{\hskip 0.0pt\lower-0.58333pt\hbox to0.0pt{
\pgfsys@beginscope\pgfsys@invoke{ }\definecolor{pgfstrokecolor}{rgb}{0,0,0}
\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0}
{0}\pgfsys@invoke{ }\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to
0.0pt{{}{}{}{}\pgfsys@moveto{0.0pt}{-0.58333pt}\pgfsys@lineto{0.0pt}{5.0011pt}
\pgfsys@lineto{6.26111pt}{5.0011pt}\pgfsys@lineto{6.26111pt}{-0.58333pt}
\pgfsys@closepath\pgfsys@clipnext\pgfsys@discardpath\pgfsys@invoke{ }{{{}{}{{}
}{}
{{}{{}}}{{}{}}{}{{}{}}
{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1.
0}{0.0pt}{0.0pt}\pgfsys@invoke{ }\hbox{{\leavevmode\hbox{\hskip-2.68335pt\hbox
{\set@color{$\textstyle\vphantom{+}{\shortrightarrow}$}}}}}\pgfsys@invoke{
\lxSVG@closescope }\pgfsys@endscope}}}}
{}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope }
\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}{\mkern 2.0mu
\leavevmode\leavevmode\hbox{ \leavevmode\hbox to4.38pt{\vbox to3.91pt{
\pgfpicture\makeatletter\hbox{\hskip 0.0pt\lower-0.40833pt\hbox to0.0pt{
\pgfsys@beginscope\pgfsys@invoke{ }\definecolor{pgfstrokecolor}{rgb}{0,0,0}
\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0}
{0}\pgfsys@invoke{ }\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to
0.0pt{{}{}{}{}\pgfsys@moveto{0.0pt}{-0.40833pt}\pgfsys@lineto{0.0pt}{3.50076pt
}\pgfsys@lineto{4.38277pt}{3.50076pt}\pgfsys@lineto{4.38277pt}{-0.40833pt}
\pgfsys@closepath\pgfsys@clipnext\pgfsys@discardpath\pgfsys@invoke{ }{{{}{}{{}
}{}
{{}{{}}}{{}{}}{}{{}{}}
{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1.
0}{0.0pt}{0.0pt}\pgfsys@invoke{ }\hbox{{\leavevmode\hbox{\hskip-1.87834pt\hbox
{\set@color{$\scriptstyle\vphantom{+}{\shortrightarrow}$}}}}}\pgfsys@invoke{
\lxSVG@closescope }\pgfsys@endscope}}}}
{}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope }
\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}{\mkern 2.0mu
\leavevmode\leavevmode\hbox{ \leavevmode\hbox to3.13pt{\vbox to2.79pt{
\pgfpicture\makeatletter\hbox{\hskip 0.0pt\lower-0.29166pt\hbox to0.0pt{
\pgfsys@beginscope\pgfsys@invoke{ }\definecolor{pgfstrokecolor}{rgb}{0,0,0}
\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0}
{0}\pgfsys@invoke{ }\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to
0.0pt{{}{}{}{}\pgfsys@moveto{0.0pt}{-0.29166pt}\pgfsys@lineto{0.0pt}{2.50055pt
}\pgfsys@lineto{3.13055pt}{2.50055pt}\pgfsys@lineto{3.13055pt}{-0.29166pt}
\pgfsys@closepath\pgfsys@clipnext\pgfsys@discardpath\pgfsys@invoke{ }{{{}{}{{}
}{}
{{}{{}}}{{}{}}{}{{}{}}
{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1.
0}{0.0pt}{0.0pt}\pgfsys@invoke{ }\hbox{{\leavevmode\hbox{\hskip-1.34167pt\hbox
{\set@color{$\scriptscriptstyle\vphantom{+}{\shortrightarrow}$}}}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}}
{}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope }
\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}}h}(G,H)$ where $g$ can be fixed as any arbitrary node in $V(G)$. We use $\text{Hom}(G,\cdot)$ to denote the function which maps any graph $H$ to the integer $\text{Hom}(G,H)$, and we define rooted homomorphism count mappings analogously. If $\mathcal{G}$ is a collection of graphs, then we treat $\text{Hom}(\mathcal{G},\cdot)$ as a function that maps any input graph $H$ to the ordered(^3^33If the graphs in $\mathcal{G}$ are not ordered initially, we arbitrarily fix some indexing of the elements in $\mathcal{G}$ so that they become ordered.) tuple (or integer vector) defined as $\text{Hom}(\mathcal{G},H)=(\text{Hom}(G,H))_{G\in\mathcal{G}}$, and analogously for rooted counts.

Curticapean et al. () describe *graph motif parameters* as functions $\Gamma(\cdot)$ that map graphs into $\mathbb{Q}$, such that there exists a *basis* of graphs $\text{Supp}(\Gamma)=\{F_{i}\}_{i=1}^{\ell}$ and corresponding coefficients $\{\alpha_{i}\}_{i=1}^{\ell}\subseteq\mathbb{Q}\backslash\{0\}$ which decompose $\Gamma$ as a finite linear combination $\Gamma(\cdot)=\sum_{i=1}^{\ell}\alpha_{i}\cdot\text{Hom}(F_{i},\cdot)$. Given $G$, the function which maps any $H$ to the number of times that $G$ appears as a subgraph(^4^44We count the number of times one can find a graph $H^{\prime}$ with $V(H^{\prime})\subseteq V(H)$ and $E(H^{\prime})\subseteq E(H)$ such that $G\cong H^{\prime}$.) of $H$ is a graph motif parameter (Lovász, ) whose basis is known as the $\mathsf{Spasm}$. 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., ).

Nguyen & Maehara () present a generalization of homomorphism counts that allow for “vertex weighting”. For graph $G$, let $\omega:V(G)\to\mathbb{R}_{\geq 0}$ describe *node weights*. The *weighted homomorphism count* from a graph $F$ into $G$ is given as:

$$ $\omega\text{-Hom}(F,G)=\sum_{f\in\mathcal{H}}\left(\prod_{v\in V(F)}\omega(f(v ))\right)$ $$

where $\mathcal{H}$ is the set of all homomorphisms from $F$ to $G$. We define the node-rooted version $\omega\text{-Hom}_{u\mathrel{\mathchoice{\mkern 2.0mu\leavevmode\leavevmode
\hbox{ \leavevmode\hbox to6.26pt{\vbox to5.58pt{\pgfpicture\makeatletter\hbox{
\hskip 0.0pt\lower-0.58333pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }
\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}
\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }
\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox to0.0pt{{}{}{}{}
\pgfsys@moveto{0.0pt}{-0.58333pt}\pgfsys@lineto{0.0pt}{5.0011pt}\pgfsys@lineto
{6.26111pt}{5.0011pt}\pgfsys@lineto{6.26111pt}{-0.58333pt}\pgfsys@closepath
\pgfsys@clipnext\pgfsys@discardpath\pgfsys@invoke{ }{{{}{}{{}}{}
{{}{{}}}{{}{}}{}{{}{}}
{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1.
0}{0.0pt}{0.0pt}\pgfsys@invoke{ }\hbox{{\leavevmode\hbox{\hskip-2.68335pt\hbox
{\set@color{$\displaystyle\vphantom{+}{\shortrightarrow}$}}}}}\pgfsys@invoke{
\lxSVG@closescope }\pgfsys@endscope}}}}
{}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope }
\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}{\mkern 2.0mu
\leavevmode\leavevmode\hbox{ \leavevmode\hbox to6.26pt{\vbox to5.58pt{
\pgfpicture\makeatletter\hbox{\hskip 0.0pt\lower-0.58333pt\hbox to0.0pt{
\pgfsys@beginscope\pgfsys@invoke{ }\definecolor{pgfstrokecolor}{rgb}{0,0,0}
\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0}
{0}\pgfsys@invoke{ }\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to
0.0pt{{}{}{}{}\pgfsys@moveto{0.0pt}{-0.58333pt}\pgfsys@lineto{0.0pt}{5.0011pt}
\pgfsys@lineto{6.26111pt}{5.0011pt}\pgfsys@lineto{6.26111pt}{-0.58333pt}
\pgfsys@closepath\pgfsys@clipnext\pgfsys@discardpath\pgfsys@invoke{ }{{{}{}{{}
}{}
{{}{{}}}{{}{}}{}{{}{}}
{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1.
0}{0.0pt}{0.0pt}\pgfsys@invoke{ }\hbox{{\leavevmode\hbox{\hskip-2.68335pt\hbox
{\set@color{$\textstyle\vphantom{+}{\shortrightarrow}$}}}}}\pgfsys@invoke{
\lxSVG@closescope }\pgfsys@endscope}}}}
{}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope }
\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}{\mkern 2.0mu
\leavevmode\leavevmode\hbox{ \leavevmode\hbox to4.38pt{\vbox to3.91pt{
\pgfpicture\makeatletter\hbox{\hskip 0.0pt\lower-0.40833pt\hbox to0.0pt{
\pgfsys@beginscope\pgfsys@invoke{ }\definecolor{pgfstrokecolor}{rgb}{0,0,0}
\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0}
{0}\pgfsys@invoke{ }\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to
0.0pt{{}{}{}{}\pgfsys@moveto{0.0pt}{-0.40833pt}\pgfsys@lineto{0.0pt}{3.50076pt
}\pgfsys@lineto{4.38277pt}{3.50076pt}\pgfsys@lineto{4.38277pt}{-0.40833pt}
\pgfsys@closepath\pgfsys@clipnext\pgfsys@discardpath\pgfsys@invoke{ }{{{}{}{{}
}{}
{{}{{}}}{{}{}}{}{{}{}}
{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1.
0}{0.0pt}{0.0pt}\pgfsys@invoke{ }\hbox{{\leavevmode\hbox{\hskip-1.87834pt\hbox
{\set@color{$\scriptstyle\vphantom{+}{\shortrightarrow}$}}}}}\pgfsys@invoke{
\lxSVG@closescope }\pgfsys@endscope}}}}
{}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope }
\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}{\mkern 2.0mu
\leavevmode\leavevmode\hbox{ \leavevmode\hbox to3.13pt{\vbox to2.79pt{
\pgfpicture\makeatletter\hbox{\hskip 0.0pt\lower-0.29166pt\hbox to0.0pt{
\pgfsys@beginscope\pgfsys@invoke{ }\definecolor{pgfstrokecolor}{rgb}{0,0,0}
\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0}
{0}\pgfsys@invoke{ }\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to
0.0pt{{}{}{}{}\pgfsys@moveto{0.0pt}{-0.29166pt}\pgfsys@lineto{0.0pt}{2.50055pt
}\pgfsys@lineto{3.13055pt}{2.50055pt}\pgfsys@lineto{3.13055pt}{-0.29166pt}
\pgfsys@closepath\pgfsys@clipnext\pgfsys@discardpath\pgfsys@invoke{ }{{{}{}{{}
}{}
{{}{{}}}{{}{}}{}{{}{}}
{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1.
0}{0.0pt}{0.0pt}\pgfsys@invoke{ }\hbox{{\leavevmode\hbox{\hskip-1.34167pt\hbox
{\set@color{$\scriptscriptstyle\vphantom{+}{\shortrightarrow}$}}}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}}
{}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope }
\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}}v}(F,G)$ by restricting $\mathcal{H}$ to only those homomorphisms which map $u\in V(F)$ to $v\in V(G)$. The mapping $\omega\text{-Hom}_{\mathrel{\mathchoice{\mkern 2.0mu\leavevmode\leavevmode
\hbox{ \leavevmode\hbox to6.26pt{\vbox to5.58pt{\pgfpicture\makeatletter\hbox{
\hskip 0.0pt\lower-0.58333pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }
\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}
\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }
\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox to0.0pt{{}{}{}{}
\pgfsys@moveto{0.0pt}{-0.58333pt}\pgfsys@lineto{0.0pt}{5.0011pt}\pgfsys@lineto
{6.26111pt}{5.0011pt}\pgfsys@lineto{6.26111pt}{-0.58333pt}\pgfsys@closepath
\pgfsys@clipnext\pgfsys@discardpath\pgfsys@invoke{ }{{{}{}{{}}{}
{{}{{}}}{{}{}}{}{{}{}}
{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1.
0}{0.0pt}{0.0pt}\pgfsys@invoke{ }\hbox{{\leavevmode\hbox{\hskip-2.68335pt\hbox
{\set@color{$\displaystyle\vphantom{+}{\shortrightarrow}$}}}}}\pgfsys@invoke{
\lxSVG@closescope }\pgfsys@endscope}}}}
{}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope }
\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}{\mkern 2.0mu
\leavevmode\leavevmode\hbox{ \leavevmode\hbox to6.26pt{\vbox to5.58pt{
\pgfpicture\makeatletter\hbox{\hskip 0.0pt\lower-0.58333pt\hbox to0.0pt{
\pgfsys@beginscope\pgfsys@invoke{ }\definecolor{pgfstrokecolor}{rgb}{0,0,0}
\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0}
{0}\pgfsys@invoke{ }\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to
0.0pt{{}{}{}{}\pgfsys@moveto{0.0pt}{-0.58333pt}\pgfsys@lineto{0.0pt}{5.0011pt}
\pgfsys@lineto{6.26111pt}{5.0011pt}\pgfsys@lineto{6.26111pt}{-0.58333pt}
\pgfsys@closepath\pgfsys@clipnext\pgfsys@discardpath\pgfsys@invoke{ }{{{}{}{{}
}{}
{{}{{}}}{{}{}}{}{{}{}}
{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1.
0}{0.0pt}{0.0pt}\pgfsys@invoke{ }\hbox{{\leavevmode\hbox{\hskip-2.68335pt\hbox
{\set@color{$\textstyle\vphantom{+}{\shortrightarrow}$}}}}}\pgfsys@invoke{
\lxSVG@closescope }\pgfsys@endscope}}}}
{}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope }
\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}{\mkern 2.0mu
\leavevmode\leavevmode\hbox{ \leavevmode\hbox to4.38pt{\vbox to3.91pt{
\pgfpicture\makeatletter\hbox{\hskip 0.0pt\lower-0.40833pt\hbox to0.0pt{
\pgfsys@beginscope\pgfsys@invoke{ }\definecolor{pgfstrokecolor}{rgb}{0,0,0}
\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0}
{0}\pgfsys@invoke{ }\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to
0.0pt{{}{}{}{}\pgfsys@moveto{0.0pt}{-0.40833pt}\pgfsys@lineto{0.0pt}{3.50076pt
}\pgfsys@lineto{4.38277pt}{3.50076pt}\pgfsys@lineto{4.38277pt}{-0.40833pt}
\pgfsys@closepath\pgfsys@clipnext\pgfsys@discardpath\pgfsys@invoke{ }{{{}{}{{}
}{}
{{}{{}}}{{}{}}{}{{}{}}
{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1.
0}{0.0pt}{0.0pt}\pgfsys@invoke{ }\hbox{{\leavevmode\hbox{\hskip-1.87834pt\hbox
{\set@color{$\scriptstyle\vphantom{+}{\shortrightarrow}$}}}}}\pgfsys@invoke{
\lxSVG@closescope }\pgfsys@endscope}}}}
{}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope }
\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}{\mkern 2.0mu
\leavevmode\leavevmode\hbox{ \leavevmode\hbox to3.13pt{\vbox to2.79pt{
\pgfpicture\makeatletter\hbox{\hskip 0.0pt\lower-0.29166pt\hbox to0.0pt{
\pgfsys@beginscope\pgfsys@invoke{ }\definecolor{pgfstrokecolor}{rgb}{0,0,0}
\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0}
{0}\pgfsys@invoke{ }\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to
0.0pt{{}{}{}{}\pgfsys@moveto{0.0pt}{-0.29166pt}\pgfsys@lineto{0.0pt}{2.50055pt
}\pgfsys@lineto{3.13055pt}{2.50055pt}\pgfsys@lineto{3.13055pt}{-0.29166pt}
\pgfsys@closepath\pgfsys@clipnext\pgfsys@discardpath\pgfsys@invoke{ }{{{}{}{{}
}{}
{{}{{}}}{{}{}}{}{{}{}}
{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1.
0}{0.0pt}{0.0pt}\pgfsys@invoke{ }\hbox{{\leavevmode\hbox{\hskip-1.34167pt\hbox
{\set@color{$\scriptscriptstyle\vphantom{+}{\shortrightarrow}$}}}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}}
{}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope }
\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}}(\cdot)}(F,\cdot)$ is defined analogously to the un-weighted case: the graph-node pair $(G,v)$ gets mapped to $\omega\text{-Hom}_{u\mathrel{\mathchoice{\mkern 2.0mu\leavevmode\leavevmode
\hbox{ \leavevmode\hbox to6.26pt{\vbox to5.58pt{\pgfpicture\makeatletter\hbox{
\hskip 0.0pt\lower-0.58333pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }
\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}
\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }
\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox to0.0pt{{}{}{}{}
\pgfsys@moveto{0.0pt}{-0.58333pt}\pgfsys@lineto{0.0pt}{5.0011pt}\pgfsys@lineto
{6.26111pt}{5.0011pt}\pgfsys@lineto{6.26111pt}{-0.58333pt}\pgfsys@closepath
\pgfsys@clipnext\pgfsys@discardpath\pgfsys@invoke{ }{{{}{}{{}}{}
{{}{{}}}{{}{}}{}{{}{}}
{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1.
0}{0.0pt}{0.0pt}\pgfsys@invoke{ }\hbox{{\leavevmode\hbox{\hskip-2.68335pt\hbox
{\set@color{$\displaystyle\vphantom{+}{\shortrightarrow}$}}}}}\pgfsys@invoke{
\lxSVG@closescope }\pgfsys@endscope}}}}
{}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope }
\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}{\mkern 2.0mu
\leavevmode\leavevmode\hbox{ \leavevmode\hbox to6.26pt{\vbox to5.58pt{
\pgfpicture\makeatletter\hbox{\hskip 0.0pt\lower-0.58333pt\hbox to0.0pt{
\pgfsys@beginscope\pgfsys@invoke{ }\definecolor{pgfstrokecolor}{rgb}{0,0,0}
\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0}
{0}\pgfsys@invoke{ }\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to
0.0pt{{}{}{}{}\pgfsys@moveto{0.0pt}{-0.58333pt}\pgfsys@lineto{0.0pt}{5.0011pt}
\pgfsys@lineto{6.26111pt}{5.0011pt}\pgfsys@lineto{6.26111pt}{-0.58333pt}
\pgfsys@closepath\pgfsys@clipnext\pgfsys@discardpath\pgfsys@invoke{ }{{{}{}{{}
}{}
{{}{{}}}{{}{}}{}{{}{}}
{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1.
0}{0.0pt}{0.0pt}\pgfsys@invoke{ }\hbox{{\leavevmode\hbox{\hskip-2.68335pt\hbox
{\set@color{$\textstyle\vphantom{+}{\shortrightarrow}$}}}}}\pgfsys@invoke{
\lxSVG@closescope }\pgfsys@endscope}}}}
{}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope }
\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}{\mkern 2.0mu
\leavevmode\leavevmode\hbox{ \leavevmode\hbox to4.38pt{\vbox to3.91pt{
\pgfpicture\makeatletter\hbox{\hskip 0.0pt\lower-0.40833pt\hbox to0.0pt{
\pgfsys@beginscope\pgfsys@invoke{ }\definecolor{pgfstrokecolor}{rgb}{0,0,0}
\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0}
{0}\pgfsys@invoke{ }\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to
0.0pt{{}{}{}{}\pgfsys@moveto{0.0pt}{-0.40833pt}\pgfsys@lineto{0.0pt}{3.50076pt
}\pgfsys@lineto{4.38277pt}{3.50076pt}\pgfsys@lineto{4.38277pt}{-0.40833pt}
\pgfsys@closepath\pgfsys@clipnext\pgfsys@discardpath\pgfsys@invoke{ }{{{}{}{{}
}{}
{{}{{}}}{{}{}}{}{{}{}}
{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1.
0}{0.0pt}{0.0pt}\pgfsys@invoke{ }\hbox{{\leavevmode\hbox{\hskip-1.87834pt\hbox
{\set@color{$\scriptstyle\vphantom{+}{\shortrightarrow}$}}}}}\pgfsys@invoke{
\lxSVG@closescope }\pgfsys@endscope}}}}
{}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope }
\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}{\mkern 2.0mu
\leavevmode\leavevmode\hbox{ \leavevmode\hbox to3.13pt{\vbox to2.79pt{
\pgfpicture\makeatletter\hbox{\hskip 0.0pt\lower-0.29166pt\hbox to0.0pt{
\pgfsys@beginscope\pgfsys@invoke{ }\definecolor{pgfstrokecolor}{rgb}{0,0,0}
\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0}
{0}\pgfsys@invoke{ }\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to
0.0pt{{}{}{}{}\pgfsys@moveto{0.0pt}{-0.29166pt}\pgfsys@lineto{0.0pt}{2.50055pt
}\pgfsys@lineto{3.13055pt}{2.50055pt}\pgfsys@lineto{3.13055pt}{-0.29166pt}
\pgfsys@closepath\pgfsys@clipnext\pgfsys@discardpath\pgfsys@invoke{ }{{{}{}{{}
}{}
{{}{{}}}{{}{}}{}{{}{}}
{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1.
0}{0.0pt}{0.0pt}\pgfsys@invoke{ }\hbox{{\leavevmode\hbox{\hskip-1.34167pt\hbox
{\set@color{$\scriptscriptstyle\vphantom{+}{\shortrightarrow}$}}}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}}
{}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope }
\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}}v}(F,G)$ where $u\in V(F)$ is fixed arbitrarily. Setting $\omega(v)=1$ for all $v\in V(G)$ recovers the un-weighted count $\omega\text{-Hom}(F,G)=\text{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., ; Cai & Govorov, ), and in the context of universal approximation capabilities as well as empirical performance of graph classifiers which use $\omega\text{-Hom}(F,\cdot)$ counts as a graph embedding  (Nguyen & Maehara, ).

Expressive Power. A *graph invariant* is a function $\xi(\cdot)$ which acts on graphs, satisfying $\xi(G)=\xi(H)$ whenever $G\cong H$ for all graphs $G$ and $H$. For indexed families of graph invariants $A_{i}$ and $B_{j}$ (where $i\in I$ and $j\in J$ respectively), we define the *expressivity* relation $A\preceq B$ to denote: for any choice of $i\in I$, there exists a choice of $j\in J$ such that $B_{j}(G)=B_{j}(H)$ implies that $A_{i}(G)=A_{i}(H)$ for all $G$ and $H$. If $A\preceq B$ and $B\preceq A$, then we say that $A\simeq B$. We write $A\prec B$ when $B$ has strictly greater expressive power, $A\preceq B$ but $A\not\simeq B$. When we reference $\preceq$ for some fixed graph invariant $\xi(\cdot)$, we interpret $\xi$ as a family which contains only one graph invariant (hence the indexing is trivial). Noting that a GNN architecture can be treated as a family of graph invariants indexed by the model weights, the relation $\preceq$ generalises common notions of the graph-distinguishability expressive power for GNNs (Zhang et al., ). As we will see in Section 4, the $\preceq$ relation naturally extends to expressivity comparisons between structural/positional encoding schemes as well.

MPNNs and Weisfeiler-Lehman Tests. Given graph $G$, the 1-WL test induces the node coloring $c^{(t)}:V(G)\to\Sigma$ for all $t$ up until some termination step $T$, at which point the graph-level 1-WL label is defined as the multiset of final node colors $\text{1-WL}(G)=\{\!\!\{c^{(T)}(v):v\in V(G)\}\!\!\}$. Graphs $G$ and $H$ are considered *1-WL indistinguishable* if they have identical graph labels $\text{1-WL}(G)=\text{1-WL}(H)$. Crucially, it holds that $\text{MPNN}\preceq\text{1-WL}$ where we treat “MPNN” as a family of graph invariants indexed by both the choice of message-passing architecture and the model parameters, and we treat 1-WL as a singleton family containing only the graph invariant $G\mapsto\text{1-WL}(G)$  (Xu et al., ).

We extend the Weisfeiler-Lehman test to “higher dimensions” by coloring $k$-tuples of nodes. The $k$-WL test induces node tuple coloring $c^{(t)}:V(G)^{k}\to\Sigma$ for $t=1,...,T$ iterations, and then it aggregates a final graph-level $k$-WL label analogously to $1$-WL  (Huang & Villar, ). In this work, we refer to the *folklore $k$-WL test*, which is provably equivalent to the alternative *olibious $k$-WL* formulation up to a re-indexing of $k$  (Grohe & Otto, ). It has been shown that the $k$-WL tests form a well-ordered hierarchy of expressive power, where $k\text{-WL}\prec(k+1)\text{-WL}$  (Cai et al., ). Here, we treat $k$-WL as a singleton family (trivial indexing) for any particular choice of $k$.

Self-Attention and Positional/Structural Encoding. Central to any Transformer architecture is the *self-attention* mechanism. When applied to graphs, a single “head” of self-attention learns a $t^{\text{th}}$-layer hidden representation $\bm{h}_{v}^{(t)}\in\mathbb{R}^{d}$ of every node $v\in V(G)$ by taking the weighted sum $\bm{h}_{v}^{(t)}=\phi^{(t)}(\sum_{u\in V(G)}\alpha^{(t)}_{v,u}\bm{h}_{u}^{(t-1
)})$ where the *attention coefficients* are $\alpha^{(t)}_{v,u}=\psi^{(t)}(\bm{h}_{v}^{(t-1)},\bm{h}_{u}^{(t-1)})$. Here, $\phi^{(t)}$ and $\psi^{(t)}$ are learnably-parameterized functions. The most common implementation of $\phi^{(t)}$ and $\psi^{(t)}$ is *scaled dot product attention*, as defined by Vaswani et al. (); although some Transformers such as GRIT (Ma et al., ) deviate from this. In most Transformers, we 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.

Since basic self-attention does not receive the adjacency matrix as an input, many graph Transformer models choose to inject a graph’s structural information into the model inputs by way of node positional/structural encoding. For example, the widely used *$k$-length random walk structural encoding* ($\text{RWSE}_{k}$) assigns to each node its corresponding diagonal entry of the degree normalized adjacency matrix(^5^55Here, $\bm{D}$ notates the diagonal degree matrix, and $\bm{A}$ the adjacency matrix.) $(\bm{D}^{-1}\bm{A})^{i}$ for all powers $i=1,...,k$  (Rampásek et al., ; Dwivedi et al., ; Ma et al., ). Each node’s $\text{RWSE}_{k}$ vector is 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 refer to any isomorphism-invariant mapping $pe$ which takes in a node-graph pair $(v,G)$ and outputs a vector label $pe(v,G)\in\mathbb{R}^{d}$. Then, the graph-level PE label is defined as the multiset of node-level labels $\text{PE}(G)=\{\!\!\{pe(v,G):v\in V(G)\}\!\!\}$. In this way, we can treat $\text{RWSE}_{k}$ as a family of graph invariants (mapping into multisets with elements in $\mathbb{R}^{d}$) indexed by $k$. Hence, we can compare the graph-level expressivity of $\text{RWSE}_{k}$ and any other general positional/structural encoding scheme PE under $\preceq$.

## 4 Homomorphism Counts as a Graph Inductive Bias

In this section we formally define motif structural encoding (MoSE). Just as with other vertex-level structural or positional encodings, MoSE provides a way to encode the structural characteristics of each graph vertex in terms of a numerical vector. Such encodings can then provide graph inductive bias to machine learning architectures, such as Transformers, that cannot (or only in a limited fashion) take graph structure into account. All proof details are provided in Appendix A.

### 4.1 Motif Structural Encoding (MoSE)

The *motif structural encoding* (MoSE) scheme is parameterized by a choice of a finite(^6^66We require that $\mathcal{G}$ be a finite set, and that each graph within $\mathcal{G}$ have finite size.) pattern graph family $\mathcal{G}=\{G_{1},\dots,G_{d}\}$, as well as a choice of node weighting scheme $\omega$ which sends any $(v,H)$ to a non-negative weight $\omega(v,H)\in\mathbb{R}_{\geq 0}$. For each node $v$ of graph $H$, the node-level $\text{MoSE}_{\mathcal{G},\omega}$ label of $v$ is:

$$ $\text{MoSE}_{\mathcal{G},\omega}(v,H)=\bigg{[}\omega\text{-Hom}_{\mathrel{ \mathchoice{\mkern 2.0mu\leavevmode\leavevmode\hbox{ \leavevmode\hbox to6.26pt {\vbox to5.58pt{\pgfpicture\makeatletter\hbox{\hskip 0.0pt\lower-0.58333pt \hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }\definecolor{pgfstrokecolor}{ rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ } \pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\pgfsys@setlinewidth{0.4pt} \pgfsys@invoke{ }\nullfont\hbox to0.0pt{{}{}{}{}\pgfsys@moveto{0.0pt}{-0.58333 pt}\pgfsys@lineto{0.0pt}{5.0011pt}\pgfsys@lineto{6.26111pt}{5.0011pt} \pgfsys@lineto{6.26111pt}{-0.58333pt}\pgfsys@closepath\pgfsys@clipnext \pgfsys@discardpath\pgfsys@invoke{ }{{{}{}{{}}{} {{}{{}}}{{}{}}{}{{}{}} {{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1. 0}{0.0pt}{0.0pt}\pgfsys@invoke{ }\hbox{{\leavevmode\hbox{\hskip-2.68335pt\hbox {\set@color{$\displaystyle\vphantom{+}{\shortrightarrow}$}}}}}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@endscope}}}} {}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope } \pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}{\mkern 2.0mu \leavevmode\leavevmode\hbox{ \leavevmode\hbox to6.26pt{\vbox to5.58pt{ \pgfpicture\makeatletter\hbox{\hskip 0.0pt\lower-0.58333pt\hbox to0.0pt{ \pgfsys@beginscope\pgfsys@invoke{ }\definecolor{pgfstrokecolor}{rgb}{0,0,0} \pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0} {0}\pgfsys@invoke{ }\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox to 0.0pt{{}{}{}{}\pgfsys@moveto{0.0pt}{-0.58333pt}\pgfsys@lineto{0.0pt}{5.0011pt} \pgfsys@lineto{6.26111pt}{5.0011pt}\pgfsys@lineto{6.26111pt}{-0.58333pt} \pgfsys@closepath\pgfsys@clipnext\pgfsys@discardpath\pgfsys@invoke{ }{{{}{}{{} }{} {{}{{}}}{{}{}}{}{{}{}} {{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1. 0}{0.0pt}{0.0pt}\pgfsys@invoke{ }\hbox{{\leavevmode\hbox{\hskip-2.68335pt\hbox {\set@color{$\textstyle\vphantom{+}{\shortrightarrow}$}}}}}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@endscope}}}} {}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope } \pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}{\mkern 2.0mu \leavevmode\leavevmode\hbox{ \leavevmode\hbox to4.38pt{\vbox to3.91pt{ \pgfpicture\makeatletter\hbox{\hskip 0.0pt\lower-0.40833pt\hbox to0.0pt{ \pgfsys@beginscope\pgfsys@invoke{ }\definecolor{pgfstrokecolor}{rgb}{0,0,0} \pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0} {0}\pgfsys@invoke{ }\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox to 0.0pt{{}{}{}{}\pgfsys@moveto{0.0pt}{-0.40833pt}\pgfsys@lineto{0.0pt}{3.50076pt }\pgfsys@lineto{4.38277pt}{3.50076pt}\pgfsys@lineto{4.38277pt}{-0.40833pt} \pgfsys@closepath\pgfsys@clipnext\pgfsys@discardpath\pgfsys@invoke{ }{{{}{}{{} }{} {{}{{}}}{{}{}}{}{{}{}} {{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1. 0}{0.0pt}{0.0pt}\pgfsys@invoke{ }\hbox{{\leavevmode\hbox{\hskip-1.87834pt\hbox {\set@color{$\scriptstyle\vphantom{+}{\shortrightarrow}$}}}}}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@endscope}}}} {}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope } \pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}{\mkern 2.0mu \leavevmode\leavevmode\hbox{ \leavevmode\hbox to3.13pt{\vbox to2.79pt{ \pgfpicture\makeatletter\hbox{\hskip 0.0pt\lower-0.29166pt\hbox to0.0pt{ \pgfsys@beginscope\pgfsys@invoke{ }\definecolor{pgfstrokecolor}{rgb}{0,0,0} \pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0} {0}\pgfsys@invoke{ }\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox to 0.0pt{{}{}{}{}\pgfsys@moveto{0.0pt}{-0.29166pt}\pgfsys@lineto{0.0pt}{2.50055pt }\pgfsys@lineto{3.13055pt}{2.50055pt}\pgfsys@lineto{3.13055pt}{-0.29166pt} \pgfsys@closepath\pgfsys@clipnext\pgfsys@discardpath\pgfsys@invoke{ }{{{}{}{{} }{} {{}{{}}}{{}{}}{}{{}{}} {{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1. 0}{0.0pt}{0.0pt}\pgfsys@invoke{ }\hbox{{\leavevmode\hbox{\hskip-1.34167pt\hbox {\set@color{$\scriptscriptstyle\vphantom{+}{\shortrightarrow}$}}}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}} {}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope } \pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}}v}(G_{i},H)\bigg{]}_ {i=1}^{d}\in\mathbb{R}^{d}$ (1) $$

We will notate $e^{\mathcal{G}}_{v}:=\text{MoSE}_{\mathcal{G},\omega}(v,H)$ for shorthand when $\omega$ and $H$ are either clear from context, or any arbitrary choice can be made. Unless otherwise specified, we use the constant $\omega$ weighting which sends all nodes in all graphs to 1, aligning $\text{MoSE}_{\mathcal{G},\omega}$ with the un-weighted homomorphism counts used in previous works (Jin et al., ; Barceló et al., ). In this case, we omit $\omega$ from our notation, using $\text{MoSE}_{\mathcal{G}}$ to denote our encoding. When we reference $\text{MoSE}_{\mathcal{G},\omega}$ at the graph-level, we mean the multiset of node-labels $\text{MoSE}_{\mathcal{G},\omega}(H)=\{\!\!\{e^{\mathcal{G}}_{v}:v\in V(H)\}\!\!\}$. It holds that $\text{MoSE}_{\mathcal{G},\omega}(\cdot)$ is a graph invariant because for any two graphs $H$ and $F$ with isomorphism $\iota:V(H)\to V(F)$, we have $e^{\mathcal{G}}_{v}=e^{\mathcal{G}}_{\iota(v)}$ for every vertex $v\in V(H)$  (Nguyen & Maehara, ).

We stated above that MoSE offers a very flexible solution to structural encodings. This flexibility comes from the two key parameters: the graphs $\mathcal{G}$ and the vertex weight function $\omega$. Both of these parameters can be adapted to fit the problem domain and architecture as desired. The choice of $\mathcal{G}$ can be informed in precise terms by desired levels of expressiveness as shown below in Proposition 4.3. Furthermore, the choice of $\mathcal{G}$ can build on a range of empirical studies on structural information in MPNNs (Barceló et al., ; Jin et al., ; Wang & Zhang, ; Bouritsas et al., ). Additional choice of a non-trivial weight function $\omega$ adds further power and flexibility. In particular, we show that even a 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 connections to the established relations between homomorphism counts and MPNNs. For Transformer architectures, similar frameworks of expressivity are not yet established. Recent work by Rosenbluth et al. () shows that Transformer architectures do not inherently contribute to expressivity, but that positional and structural encodings are the key ingredient to the expressivity of these architectures. We therefore study the expressivity of the positional encodings themselves, which in turn also translate to models that combine an architecture with MoSE. 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 a sense incomparable to the WL-hierarchy. For every fixed set of graphs $\mathcal{G}$ that induces an encoding, we can provide an upper bound in terms of $k$-WL for some $k$ dependent on $\mathcal{G}$. At the same time, given any fixed choice of $k$, the expressiveness of even MoSE encodings induced by a single graph cannot be confined to the expressive power of $k$-WL (Proposition 4.2).

###### Proposition 4.1 .

Let $\mathcal{G}$ be a finite set of graphs and let $k$ be the maximum treewidth of a graph in $G$. Then $\text{{MoSE}}_{\mathcal{G}}$ is at most as distinguishing as $k$-WL. That is, $\text{MoSE}_{\mathcal{G}}\preceq k\text{-WL}$(^7^77With respect to the definition of $\preceq$, both sides in this case represent singleton families of graph invariants.).

Although we cannot distinguish *all* graphs distinguished by $k$-WL using $\text{{MoSE}}_{\mathcal{G}}$ with a finite $\mathcal{G}$, we can distinguish any particular pair of graphs distinguished by $k$-WL. In fact, we only need a single graph in $\mathcal{G}$ in order to do this.

###### Proposition 4.2 .

For $k\geq 1$, let $G$ and $H$ be two graphs that are equivalent under $k$-WL. Then there exists a graph $F$ such that $\text{{MoSE}}_{\{F\}}$ distinguishes $G$ and $H$.

Lanzinger & Barceló () and Jin et al. () 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 homomorphism basis (Jin et al., ). Building on these results, we establish a very broad lower bounds for Transformer architectures with MoSE that provide a practical basis for choice of $\mathcal{G}$.

###### Proposition 4.3 .

Let $f$ be a graph motif parameter with basis $\mathcal{G}_{f}\subseteq\mathcal{G}$. Then $\text{{MoSE}}_{\mathcal{G}}$ is at least as distinguishing as $f$. That is, if $\mathcal{F}$ is the family of all graph motif parameters, we have $\mathcal{F}\preceq\text{MoSE}$.

###### Proposition 4.1 .

###### Proposition 4.2 .

###### Proposition 4.3 .

### 4.2 Comparing the Expressivity of MoSE to RWSE

Figure: Figure 2: The $4\times 4$ Rook’s Graph (left) and the Shrikhande Graph (right) are non-isomorphic strongly regular graphs that have the same regularity parameters. RWSE produces the same vector on every vertex of both graphs whereas a simple construction of MoSE using $\mathsf{Spasm}(C_{7})\cup\mathsf{Spasm}(C_{8})$ homomorphism counts easily distinguishes the two graphs.
Refer to caption: x1.png

From above we see that MoSE is closely aligned to the $k$-WL hierarchy, and we can use this alignment to inform the choice of $\mathcal{G}$. However, it is not 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.

###### Proposition 4.4 .

For every $\ell\geq 2$, any graph which can be distinguished by $\text{RWSE}_{\ell}$ can be distinguished by 2-WL.

This in itself already has wide-ranging consequences. For instance, it is known that 2-WL cannot distinguish strongly regular graphs (Fuhlbrück et al., ), and therefore neither can RWSE . For MoSE, there exist no such limitations (Figure 2) beyond those dependent on the choice of $\mathcal{G}$, as stated in Proposition 4.1.

While MoSE cannot fully capture 2-WL, it is in fact possible to express RWSEℓ for every $\ell\geq 2$ as a special case of MoSE. In contrast to previous results, our result here requires a vertex-weighting scheme that is not constant. However, even straightforward vertex-weighting by degrees – which comes at no cost in practice – is enough for our proof. We note that $\mathcal{G}$ consisting of cycle graphs with size at most $\ell$ is sufficient to do so (see Appendix A for details).

###### Proposition 4.5 .

For any $\ell\in\mathbb{N}$, there exists a finite family of graphs $\mathcal{G}$ and a vertex-weighting scheme $\omega$ such that the node-level $\text{RWSE}_{\ell}(v,H)$ label is uniquely determined by $\text{MoSE}_{\mathcal{G},\omega}(v,H)$ for any node $v$ in any graph $H$. In particular, this holds already for the vertex-weighting scheme $\omega:v\mapsto 1/\mathit{degree}(v)$.

Combining Proposition 4.4 and Proposition 4.5 immediately shows $\text{RWSE}\preceq\text{MoSE}$. The example from Figure 2 demonstrates that this inclusion is in fact strict.

###### Theorem 4.6 .

Motif structural encoding is strictly more expressive than random walk structural encoding: $\text{RWSE}\prec\text{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 vectors to both nodes for every $\ell\geq 1$ (Figure 1).

###### Proposition 4.7 .

RWSE is incomparable to 1-WL in terms of node-level expressiveness.

###### Proposition 4.4 .

###### Proposition 4.5 .

###### Theorem 4.6 .

###### Proposition 4.7 .

## 5 Experiments

We empirically demonstrate the efficacy of using MoSE as a graph inductive bias on several real-world datasets across a range of models. First, we provide an in-depth comparison of MoSE with other positional and structural encoding methods on the ZINC molecular dataset (Irwin et al., ; Dwivedi et al., ) in Section 5.1. Next, we specifically contrast the performance of MoSE and RWSE on the QM9 dataset (Wu et al., ) in Section 5.2.
Finally, we conduct a synthetic experiment to highlight the flexibility of MoSE across different domains in Section 5.3. To align with previous works (Jin et al., ; Barceló et al., ), we use the trivial vertex-weighting where $\omega$ maps all vertices to 1. Although this implementation does not fully recover RWSE, we show that even this weaker version is enough to outperform RWSE.
Full experimental details are in Appendix B.

### 5.1 Graph Regression on ZINC

ZINC (Irwin et al., ; Dwivedi et al., ) is a molecular dataset, where the goal is to predict the constrained solubility of a given molecule. Each graph in the dataset represents an individual molecule, where the node features denote atom type, and edge features denote bond type. In accordance with Dwivedi et al. (), we use a subset of the ZINC dataset with edge features that contains 12,000 molecules and constrain all our models to under 500k parameters.

Experimental Setup.   We begin by selecting GPS (Rampásek et al., ) as our reference model and compare the performance of MoSE against other popular encoding methods, such as RWSE, LapPE, etc. Then, we combine MoSE with GRIT (Ma et al., ), a recent graph transformer model 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 representation level. In our formulation, GRIT+MoSE, we remove all RRWP encodings for both the node and node-pair representations. For all ZINC experiments, we construct MoSE using the $\mathsf{Spasm}(C_{7})\cup\mathsf{Spasm}(C_{8})$ homomorphism counts in accordance with Jin et al. (). All other experimental details can be found in Section B.2.

**Table 1: We report the mean absolute error (MAE) for GPS with various positional/structural encodings on the ZINC-12k dataset (with edge features). MoSE outperforms several popular encoding methods.**
| Encoding Type | MAE $\downarrow$ | Rel. Change |
| --- | --- | --- |
| none | 0.113$\pm{}0.007$ | $\pm$ 0 % |
| PEG${}^{\textit{LapEig}}$ | 0 161$\pm{}0.006$ | + 29.81 % |
| LapPE | 0.116$\pm{}0.009$ | + 2.59 % |
| SignNet^MLP | 0.090$\pm{}0.007$ | - 25.56 % |
| SignNet^DeepSets | 0.079$\pm{}0.006$ | -43.04% |
| RWSE | 0.070$\pm{}0.002$ | -61.43% |
| MoSE (*ours*) | 0.062$\pm{}0.002$ | -82.26% |

**Table 3: 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. The best feature encoding is highlighted in bold.**
| Model | Encoding Type |  |  |
| --- | --- | --- | --- |
|  | none | RWSE | MoSE |
| MLP-E | 0.606$\pm{}0.002$ | 0.361$\pm{}0.010$ | 0.347$\pm{}0.003$ |
| GIN-E | 0.243$\pm{}0.006$ | 0.122$\pm{}0.003$ | 0.118$\pm{}0.007$ |
| GIN-E+VN | 0.151$\pm{}0.006$ | 0.085$\pm{}0.003$ | 0.068$\pm{}0.004$ |
| GT-E | 0.195$\pm{}0.025$ | 0.104$\pm{}0.025$ | 0.089$\pm{}0.018$ |
| GPS | 0.119$\pm{}0.011$ | 0.070$\pm{}0.002$ | 0.062$\pm{}0.002$ |

Results.
We compare MoSE to other prominent positional and structural encoding methods. Our results are presented in Table 2 with baseline results for all encodings except MoSE taken from Rampásek et al. (). We see that MoSE significantly outperforms the other encoding types, especially the spectral methods, such as PEG^LapEig (Wang et al., ) and LapPE (Dwivedi & Bresson, ). When compared to RWSE, the most prominent structural-based encoding method, MoSE still achieves over 10% relative improvement.

Furthermore, using MoSE in conjunction with the GRIT architecture (Ma et al., ) yields state of the art results on ZINC, as detailed in Table 2. Recall that when we substituted MoSE in place of the RRWP encoding for GRIT, we only did so at the node level. This suggests that even without explicit node-pair encodings, MoSE still captures a meaningful amount of structural information about the graph. Not only does MoSE surpass the expressivity of RWSE (Section 4.2), but the information encoded in MoSE can aid the model in recovering specific substructure information (Jin et al., ).

Comparing MoSE to RWSE across Multiple Architectures.
Because Rampásek et al. () find that RWSE performs better for molecular datasets, we provide a detailed comparison of how MoSE performs against RWSE across a range of architectures. We select a simple 4-layer multi-layer perceptron (MLP-E), the self-attention Graph Transformer (GT-E) from (Dwivedi & Bresson, ), and GPS (Rampásek et al., ) as our models. Note that all models are adapted to account for edge features. GRIT is omitted since its node-pair encoding mechanism does not make it directly comparable to the other models. For reference GNN models, we report results for GIN-E and its extention GIN-E+VN, which includes a virtual node (Hu et al., ). As before, MoSE uses the set of homomorphism counts for $\mathsf{Spasm}(C_{7})\cup\mathsf{Spasm}(C_{8})$. For RWSE, we follow the protocol from Rampásek et al. () and set the random-walk length to 20.

Results.   We see from Table 3 that MoSE performs better than RWSE across all models. 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 the structural information provided by MoSE yields superior performance.
We also note that GIN-E+VN becomes competitive with the state-of-the-art when using MoSE. This is consistent with our theoretical findings and aligns with recent results that suggest the use of virtual nodes can improve model performance of MPNNs (Tönshoff et al., ).

### 5.2 Graph Regression on QM9

**Table 4: We report MAE results for GPS with various feature enhancements on 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) |
| mu | 2.64$\pm{}0.11$ | 2.54$\pm{}0.09$ | 2.21$\pm{}0.21$ | 1.97$\pm{}0.03$ | 1.47$\pm{}0.02$ | 1.43$\pm{}0.02$ |
| alpha | 4.67$\pm{}0.52$ | 2.28$\pm{}0.04$ | 1.66$\pm{}0.06$ | 1.63$\pm{}0.01$ | 1.52$\pm{}0.27$ | 1.48$\pm{}0.16$ |
| HOMO | 1.42$\pm{}0.01$ | 1.26$\pm{}0.02$ | 1.20$\pm{}0.08$ | 1.15$\pm{}0.01$ | 0.91$\pm{}0.01$ | 0.91$\pm{}0.01$ |
| LUMO | 1.50$\pm{}0.09$ | 1.34$\pm{}0.04$ | 1.20$\pm{}0.06$ | 1.06$\pm{}0.02$ | 0.90$\pm{}0.06$ | 0.86$\pm{}0.01$ |
| gap | 2.27$\pm{}0.09$ | 1.96$\pm{}0.04$ | 1.77$\pm{}0.06$ | 1.73$\pm{}0.02$ | 1.47$\pm{}0.02$ | 1.45$\pm{}0.02$ |
| R2 | 15.63$\pm{}1.40$ | 12.61$\pm{}0.37$ | 10.63$\pm{}1.01$ | 10.53$\pm{}0.55$ | 6.11$\pm{}0.16$ | 6.22$\pm{}0.19$ |
| ZPVE | 12.93$\pm{}1.81$ | 5.03$\pm{}0.36$ | 2.58$\pm{}0.13$ | 2.81$\pm{}0.16$ | 2.63$\pm{}0.44$ | 2.43$\pm{}0.27$ |
| U0 | 5.88$\pm{}1.01$ | 2.21$\pm{}0.12$ | 0.89$\pm{}0.05$ | 0.95$\pm{}0.04$ | 0.83$\pm{}0.17$ | 0.85$\pm{}0.08$ |
| U | 18.71$\pm{}23.36$ | 2.32$\pm{}0.18$ | 0.93$\pm{}0.03$ | 0.94$\pm{}0.04$ | 0.83$\pm{}0.15$ | 0.75$\pm{}0.03$ |
| H | 5.62$\pm{}0.81$ | 2.26$\pm{}0.19$ | 0.92$\pm{}0.03$ | 0.92$\pm{}0.04$ | 0.86$\pm{}0.15$ | 0.83$\pm{}0.09$ |
| G | 5.38$\pm{}0.75$ | 2.04$\pm{}0.24$ | 0.83$\pm{}0.05$ | 0.88$\pm{}0.04$ | 0.83$\pm{}0.12$ | 0.80$\pm{}0.14$ |
| Cv | 3.53$\pm{}0.37$ | 1.86$\pm{}0.03$ | 1.23$\pm{}0.06$ | 1.20$\pm{}0.06$ | 1.25$\pm{}0.05$ | 1.02$\pm{}0.04$ |
| Omega | 1.05$\pm{}0.11$ | 0.80$\pm{}0.04$ | 0.52$\pm{}0.02$ | 0.45$\pm{}0.01$ | 0.39$\pm{}0.02$ | 0.38$\pm{}0.01$ |

QM9 is a real-world molecular dataset that contains over 130,000 graphs (Wu et al., ; Brockschmidt, ). The node features include the atom’s type and other descriptive features. Unlike ZINC, where there is only one regression target, QM9 presents 13 different quantum chemical properties to regress over, making it a much more robust benchmark.

Experimental Setup.   We select GPS (Rampásek et al., ) as our base model due to its modularity. Again, we compare the performance of GPS+RWSE to the performance of GPS+MoSE. We follow the protocol from and construct MoSE using the set of homomorphism counts on connected graphs with at most 5 vertices and the 6-cycle. This is because there are several regression targets for QM9, so GPS will benefit from a graph inductive bias that can account for a more diverse set of motifs (Proposition 4.3). We keep a random-walk length of 20 for RWSE to align with the hyperparameter setting for molecular datasets outlined by Rampásek et al. (). Finally, we provide several leading GNN models on the QM9 dataset for comparison (Brockschmidt, ; Alon & Yahav, ; Abboud et al., ; Dimitrov et al., ).

Results.   From Table 4, it is clear that MoSE outperforms RWSE consistently across multiple different regression targets. Specifically, GPS+MoSE achieves the same or a lower MAE on 11 of the 13 molecular properties. It also comfortably outperforms the leading GNN models, including R-SPN (Abboud et al., ) and E-BasePlane (Dimitrov et al., ). In contrast, GPS+RWSE is occasionally outperformed by these GNN architectures, despite being computationally more demanding than the GNN baselines. These findings further support our theoretical results and show that MoSE is a very promising structural encoding scheme.

### 5.3 Synthetic Dataset: Predicting Fractional Domination Number

To supplement our real-world dataset examples, we also generate a new synthetic dataset where the task is to predict the fractional dominance number of a graph. The dataset is comprised of 10,000 randomly-generated Erdős-Rényi graphs of various densities (Erdős & Rényi, ). The exact range of the number of vertices and density is provided in Section B.4.

We select the fractional dominance number of a graph as our target of interest for two reasons: first, the property is inherently global and relies on complex long-range interactions. This is unlike other popularly used metrics for synthetic experiments, e.g., clustering coefficients, which are aggregations of local properties. Second, the distribution of this parameter over our set of random graphs is complex (Figure 4), making the task more challenging.
Furthermore, (fractional) dominating sets are important for a range of applications, such as optimizing network coverage (Kutten & Peleg, ).

Experimental Setup.
We focus on measuring the practical performance of MoSE compared to other positional and structural encoding methods. For this we select a 4-layer MLP and a self-attention Graph Transformer (Dwivedi & Bresson, ) as our reference models. Since neither model contains a message passing component, they both are considered architectures without inherent graph inductive biases. We use the homomorphism counts for $\mathsf{Spasm}(C_{7})\cup\mathsf{Spasm}(C_{8})$ for MoSE, use a random walk length of 20 for RWSE, and set the dimension of LapPE to 8.

Figure: Figure 3: Plot of the distribution of the fractional domination numbers in our synthetic dataset.
Refer to caption: extracted/5948923/fracdom-dist.png

Results.
Figure 4 shows that across both models, MoSE performs the best compared to the other graph inductive biases. This suggests that MoSE is able to capture more complex graph information in the broader context. We also note that MLP+LapPE performs significantly worse than all other configurations. This indicates that the self-attention mechanism in GT is a key component to allowing the model to leverage the spectral graph information provided by LapPE.

## 6 Discussion and Future Work

In this work, we propose motif structural encodings as a flexible new graph inductive bias that is based on counting graph homomorphisms. MoSE is supported by expressiveness guarantees, which transfer to architectures that use MoSE as their graph inductive bias. In particular, we show that MoSE is a more expressive encoding than RWSE and relate these encoding schemes to the expressive power of MPNNs and more generally to the WL hierarchy.
We empirically validate that the theoretical advantages of MoSE also translate to performance gains across a set of real-world and synthetic datasets. Although our work takes a closer look at the expressivity of different graph inductive biases, there remain several open questions in this area of characterizing different encoding methods. Furthermore, we have yet to explore the full potential of the vertex-weighting parameter of our encoding scheme.

#### Acknowledgments

Emily Jin is 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.47379/ICT2201]. This research is partially supported by EPSRC Turing AI World-Leading Research Fellowship No. EP/X040062/1 and EPSRC AI Hub on Mathematical Foundations of Intelligence: An “Erlangen Programme” for AI No. EP/Y028872/1.

## Appendix A Technical Details

###### Proof of Proposition 4.1 .

Dvorák () showed that if $G$ and $H$ are equivalent under $k$-WL, then every graph $F$ with treewidth at most $k$ has $\mathsf{Hom}(F,G)=\mathsf{Hom}(F,H)$.
This extends also to the vertex level. Let $v\in V(G)$ and $v^{\prime}\in V(H)$ such that $v$ and $v^{\prime}$ have equivalent $k$-WL labels. Then also $\mathsf{Hom}(F,G,v)=\mathsf{Hom}(F,H,v^{\prime})$ (see Lanzinger & Barceló (), Lemma 12).
Hence, if the maximum treewidth in $\mathcal{G}$ is $k$, then equivalence under $k$-WL implies also that they are equivalent under $\text{{MoSE}}_{\mathcal{G}}$.
∎

###### Proof of Proposition 4.2 .

It is well known (Lovász, ) that for every two non-isomorphic graphs $G$ and $H$, there is a graph $F$ such that $\mathsf{Hom}(F,G)\neq\mathsf{Hom}(F,H)$.
We have that $\text{{MoSE}}_{\{F\}}$ will distinguish the two graphs.
∎

###### Proof of Proposition 4.3 .

Suppose the opposite, i.e., there is a pair of graphs $G,H$ such that $f(G)\neq f(H)$, but $\text{{MoSE}}_{\Gamma_{f}}$, where $\Gamma_{f}$ is set of graphs in the basis of $f$, creates the same multiset of labels on both graphs. Then specifically, also $\mathsf{Hom}(F,G)=\mathsf{Hom}(F,H)$ for every $F\in\Gamma_{f}$. But since $f$ is a graph motif parameter, $f(G)=f(H)$ and we arrive at a contradiction.
∎

###### Proof of Proposition 4.1 .

###### Proof of Proposition 4.2 .

###### Proof of Proposition 4.3 .

### A.1 Theorem 4.6

###### Proof of Proposition 4.5 .

Take any graph $H$ and notate $V(H)=\{1,2,...,n\}$. For $v,v^{\prime}\in V(H)$, define ${P}(v\xrightarrow{i}v^{\prime})$ to be the probability of starting a length $i$ random walk at node $v$ and ending it at node $v^{\prime}$. Here, “length $i$” refers to the number of edges in the random walk where we 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(v)$ to moving to any of the neighbors in $\mathcal{N}(v)$.

As shorthand, define $\bm{M}=\bm{D}^{-1}\bm{A}$ where $\bm{D}$ and $\bm{A}$ are the diagonal degree matrix and adjacency matrix of $H$ respectively. Let us first prove that $(\bm{M}^{i})_{v,v^{\prime}}={P}(v\xrightarrow{i}v^{\prime})$ for any nodes $v,v^{\prime}\in V$ and for all powers $i\in\mathbb{N}$ by performing induction on $i$. The base case $i=1$ holds trivially because we assume that random steps are taken uniformly over neighbors. Assume as the inductive hypothesis that our claim holds for some $i\geq 1$, and note that:

$$ $(\bm{M}^{i+1})_{v,v^{\prime}}=(\bm{M}^{1}\bm{M}^{i})_{v,v^{\prime}}=\sum_{x=1} ^{n}\bm{M}_{v,x}\cdot\bm{M}^{i}_{x,v^{\prime}}$ $$

but our base case and inductive hypothesis tell us that

$$ $\sum_{x=1}^{n}\bm{M}_{v,x}\cdot\bm{M}^{i}_{x,v^{\prime}}=\sum_{x=1}^{n}{P}(v \xrightarrow{1}x)\cdot{P}(x\xrightarrow{i}v^{\prime})$ $$

By the law of total probability:

$$ $\sum_{x=1}^{n}{P}(v\xrightarrow{1}x)\cdot{P}(x\xrightarrow{i}v^{\prime})={P}(v \xrightarrow{i+1}v^{\prime})$ $$

This completes the induction. Hence, for any node $v$ in any graph $H$, the node-level $\text{RWSE}_{k}$ vector is equivalent to:

$$ $\text{RWSE}_{k}(v,H)=\bigg{[}(\bm{M}^{i})_{v,v}\bigg{]}_{i=1}^{k}=\bigg{[}{P}( v\xrightarrow{i}v)\bigg{]}_{i=1}^{k}\in\mathbb{R}^{k}$ $$

Now, let us show that we can recover this random-walk vector using MoSE. Consider the family of all cycles with up to $k$ nodes $\mathcal{G}=\{C_{i}\}_{i=1}^{k}$, and let $\omega$ be the vertex weighting which maps any node to the reciprocal of its degree. For each $C_{i}\in\mathcal{G}$, enumerate the nodes $V(C_{i})=\{u_{0},u_{1},...,u_{i-1}\}$ such that $(u_{\ell},u_{\ell+1})\in E(C_{i})$ for all $\ell=0,...,i-2$ and $(u_{i-1},u_{0})\in E(C_{i})$.

Take any node $v$ in any graph $H$, and define $\mathcal{H}_{i}$ to be the set of all homomorphisms from $C_{i}$ to $G$ which map node $u_{0}\in C_{i}$ to node $v\in G$. Each homomorphism in $f\in\mathcal{H}_{i}$ can be constructed by making $i-1$ choices of node image $f(u_{\ell})\in\mathcal{N}\left(f(u_{\ell-1})\right)$ for $\ell=1,...,i-1$ such that $f(u_{(i-1)})\in\mathcal{N}(f(u_{0}))$ where we have fixed $f(u_{0})=v$. In other words, each homomorphism $f\in\mathcal{H}_{i}$ corresponds to a $i$-edge walk (allowing edge repeats) starting and ending at node $v$, which we will call $W_{f}$. This correspondence is described by taking the induced subgraph $W_{f}=G[f(C_{i})]$ where $f(C_{i})$ is the image of $C_{i}$ under homomorphism $f$. In the reverse direction, any $i$-edge walk

$$ $W_{f}:\quad v=v^{(0)},v^{(1)},....,v^{(i-1)},v^{(i)}=v\quad\text{in }H$ $$

that starts and ends at node $v$ corresponds to a homomorphism $f\in\mathcal{H}_{i}$ which maps $f(u_{\ell})=v^{(\ell)}$. Hence, we have established a bijective correspondence between $\mathcal{H}_{i}$ and an $i$-edge walk starting/ending at $v$.

For any $f\in\mathcal{H}_{i}$, we have:

$$ $\prod_{v\in V(C_{i})}\omega(f(v))=\prod_{v\in W_{f}}1/d(v)=\prod_{\ell=0}^{i-1 }1/d(v^{(\ell)})$ $$

Since the probability of stepping from node $v^{(\ell-1)}\in V(W_{f})$ to node $v^{(\ell)}\in V(W_{f})$ in a random walk is simply $1/d(v^{(\ell-1)})$, it holds that:

$$ $\prod_{\ell=0}^{i-1}1/d(v^{(\ell)})=P(W_{f})$ $$

where $P(W_{f})$ is the probability of a random walk starting in $v^{(0)}$ and ending in $v^{(i)}$ being exactly the walk $W_{f}$. Thus,

$$ $\omega\text{-Hom}_{u_{0}\mathrel{\mathchoice{\mkern 2.0mu\leavevmode \leavevmode\hbox{ \leavevmode\hbox to6.26pt{\vbox to5.58pt{\pgfpicture \makeatletter\hbox{\hskip 0.0pt\lower-0.58333pt\hbox to0.0pt{ \pgfsys@beginscope\pgfsys@invoke{ }\definecolor{pgfstrokecolor}{rgb}{0,0,0} \pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0} {0}\pgfsys@invoke{ }\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox to 0.0pt{{}{}{}{}\pgfsys@moveto{0.0pt}{-0.58333pt}\pgfsys@lineto{0.0pt}{5.0011pt} \pgfsys@lineto{6.26111pt}{5.0011pt}\pgfsys@lineto{6.26111pt}{-0.58333pt} \pgfsys@closepath\pgfsys@clipnext\pgfsys@discardpath\pgfsys@invoke{ }{{{}{}{{} }{} {{}{{}}}{{}{}}{}{{}{}} {{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1. 0}{0.0pt}{0.0pt}\pgfsys@invoke{ }\hbox{{\leavevmode\hbox{\hskip-2.68335pt\hbox {\set@color{$\displaystyle\vphantom{+}{\shortrightarrow}$}}}}}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@endscope}}}} {}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope } \pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}{\mkern 2.0mu \leavevmode\leavevmode\hbox{ \leavevmode\hbox to6.26pt{\vbox to5.58pt{ \pgfpicture\makeatletter\hbox{\hskip 0.0pt\lower-0.58333pt\hbox to0.0pt{ \pgfsys@beginscope\pgfsys@invoke{ }\definecolor{pgfstrokecolor}{rgb}{0,0,0} \pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0} {0}\pgfsys@invoke{ }\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox to 0.0pt{{}{}{}{}\pgfsys@moveto{0.0pt}{-0.58333pt}\pgfsys@lineto{0.0pt}{5.0011pt} \pgfsys@lineto{6.26111pt}{5.0011pt}\pgfsys@lineto{6.26111pt}{-0.58333pt} \pgfsys@closepath\pgfsys@clipnext\pgfsys@discardpath\pgfsys@invoke{ }{{{}{}{{} }{} {{}{{}}}{{}{}}{}{{}{}} {{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1. 0}{0.0pt}{0.0pt}\pgfsys@invoke{ }\hbox{{\leavevmode\hbox{\hskip-2.68335pt\hbox {\set@color{$\textstyle\vphantom{+}{\shortrightarrow}$}}}}}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@endscope}}}} {}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope } \pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}{\mkern 2.0mu \leavevmode\leavevmode\hbox{ \leavevmode\hbox to4.38pt{\vbox to3.91pt{ \pgfpicture\makeatletter\hbox{\hskip 0.0pt\lower-0.40833pt\hbox to0.0pt{ \pgfsys@beginscope\pgfsys@invoke{ }\definecolor{pgfstrokecolor}{rgb}{0,0,0} \pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0} {0}\pgfsys@invoke{ }\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox to 0.0pt{{}{}{}{}\pgfsys@moveto{0.0pt}{-0.40833pt}\pgfsys@lineto{0.0pt}{3.50076pt }\pgfsys@lineto{4.38277pt}{3.50076pt}\pgfsys@lineto{4.38277pt}{-0.40833pt} \pgfsys@closepath\pgfsys@clipnext\pgfsys@discardpath\pgfsys@invoke{ }{{{}{}{{} }{} {{}{{}}}{{}{}}{}{{}{}} {{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1. 0}{0.0pt}{0.0pt}\pgfsys@invoke{ }\hbox{{\leavevmode\hbox{\hskip-1.87834pt\hbox {\set@color{$\scriptstyle\vphantom{+}{\shortrightarrow}$}}}}}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@endscope}}}} {}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope } \pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}{\mkern 2.0mu \leavevmode\leavevmode\hbox{ \leavevmode\hbox to3.13pt{\vbox to2.79pt{ \pgfpicture\makeatletter\hbox{\hskip 0.0pt\lower-0.29166pt\hbox to0.0pt{ \pgfsys@beginscope\pgfsys@invoke{ }\definecolor{pgfstrokecolor}{rgb}{0,0,0} \pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0} {0}\pgfsys@invoke{ }\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox to 0.0pt{{}{}{}{}\pgfsys@moveto{0.0pt}{-0.29166pt}\pgfsys@lineto{0.0pt}{2.50055pt }\pgfsys@lineto{3.13055pt}{2.50055pt}\pgfsys@lineto{3.13055pt}{-0.29166pt} \pgfsys@closepath\pgfsys@clipnext\pgfsys@discardpath\pgfsys@invoke{ }{{{}{}{{} }{} {{}{{}}}{{}{}}{}{{}{}} {{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1. 0}{0.0pt}{0.0pt}\pgfsys@invoke{ }\hbox{{\leavevmode\hbox{\hskip-1.34167pt\hbox {\set@color{$\scriptscriptstyle\vphantom{+}{\shortrightarrow}$}}}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}} {}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope } \pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}}v}(C_{i},G)=\sum_{f \in\mathcal{H}_{i}}P(W_{f})=P(v\xrightarrow{i}v)$ $$

giving us:

$$ $\text{MoSE}_{\mathcal{G},\omega}(v,H)=\bigg{[}\omega\text{-Hom}_{\mathrel{ \mathchoice{\mkern 2.0mu\leavevmode\leavevmode\hbox{ \leavevmode\hbox to6.26pt {\vbox to5.58pt{\pgfpicture\makeatletter\hbox{\hskip 0.0pt\lower-0.58333pt \hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }\definecolor{pgfstrokecolor}{ rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ } \pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\pgfsys@setlinewidth{0.4pt} \pgfsys@invoke{ }\nullfont\hbox to0.0pt{{}{}{}{}\pgfsys@moveto{0.0pt}{-0.58333 pt}\pgfsys@lineto{0.0pt}{5.0011pt}\pgfsys@lineto{6.26111pt}{5.0011pt} \pgfsys@lineto{6.26111pt}{-0.58333pt}\pgfsys@closepath\pgfsys@clipnext \pgfsys@discardpath\pgfsys@invoke{ }{{{}{}{{}}{} {{}{{}}}{{}{}}{}{{}{}} {{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1. 0}{0.0pt}{0.0pt}\pgfsys@invoke{ }\hbox{{\leavevmode\hbox{\hskip-2.68335pt\hbox {\set@color{$\displaystyle\vphantom{+}{\shortrightarrow}$}}}}}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@endscope}}}} {}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope } \pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}{\mkern 2.0mu \leavevmode\leavevmode\hbox{ \leavevmode\hbox to6.26pt{\vbox to5.58pt{ \pgfpicture\makeatletter\hbox{\hskip 0.0pt\lower-0.58333pt\hbox to0.0pt{ \pgfsys@beginscope\pgfsys@invoke{ }\definecolor{pgfstrokecolor}{rgb}{0,0,0} \pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0} {0}\pgfsys@invoke{ }\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox to 0.0pt{{}{}{}{}\pgfsys@moveto{0.0pt}{-0.58333pt}\pgfsys@lineto{0.0pt}{5.0011pt} \pgfsys@lineto{6.26111pt}{5.0011pt}\pgfsys@lineto{6.26111pt}{-0.58333pt} \pgfsys@closepath\pgfsys@clipnext\pgfsys@discardpath\pgfsys@invoke{ }{{{}{}{{} }{} {{}{{}}}{{}{}}{}{{}{}} {{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1. 0}{0.0pt}{0.0pt}\pgfsys@invoke{ }\hbox{{\leavevmode\hbox{\hskip-2.68335pt\hbox {\set@color{$\textstyle\vphantom{+}{\shortrightarrow}$}}}}}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@endscope}}}} {}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope } \pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}{\mkern 2.0mu \leavevmode\leavevmode\hbox{ \leavevmode\hbox to4.38pt{\vbox to3.91pt{ \pgfpicture\makeatletter\hbox{\hskip 0.0pt\lower-0.40833pt\hbox to0.0pt{ \pgfsys@beginscope\pgfsys@invoke{ }\definecolor{pgfstrokecolor}{rgb}{0,0,0} \pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0} {0}\pgfsys@invoke{ }\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox to 0.0pt{{}{}{}{}\pgfsys@moveto{0.0pt}{-0.40833pt}\pgfsys@lineto{0.0pt}{3.50076pt }\pgfsys@lineto{4.38277pt}{3.50076pt}\pgfsys@lineto{4.38277pt}{-0.40833pt} \pgfsys@closepath\pgfsys@clipnext\pgfsys@discardpath\pgfsys@invoke{ }{{{}{}{{} }{} {{}{{}}}{{}{}}{}{{}{}} {{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1. 0}{0.0pt}{0.0pt}\pgfsys@invoke{ }\hbox{{\leavevmode\hbox{\hskip-1.87834pt\hbox {\set@color{$\scriptstyle\vphantom{+}{\shortrightarrow}$}}}}}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@endscope}}}} {}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope } \pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}{\mkern 2.0mu \leavevmode\leavevmode\hbox{ \leavevmode\hbox to3.13pt{\vbox to2.79pt{ \pgfpicture\makeatletter\hbox{\hskip 0.0pt\lower-0.29166pt\hbox to0.0pt{ \pgfsys@beginscope\pgfsys@invoke{ }\definecolor{pgfstrokecolor}{rgb}{0,0,0} \pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0} {0}\pgfsys@invoke{ }\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox to 0.0pt{{}{}{}{}\pgfsys@moveto{0.0pt}{-0.29166pt}\pgfsys@lineto{0.0pt}{2.50055pt }\pgfsys@lineto{3.13055pt}{2.50055pt}\pgfsys@lineto{3.13055pt}{-0.29166pt} \pgfsys@closepath\pgfsys@clipnext\pgfsys@discardpath\pgfsys@invoke{ }{{{}{}{{} }{} {{}{{}}}{{}{}}{}{{}{}} {{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1. 0}{0.0pt}{0.0pt}\pgfsys@invoke{ }\hbox{{\leavevmode\hbox{\hskip-1.34167pt\hbox {\set@color{$\scriptscriptstyle\vphantom{+}{\shortrightarrow}$}}}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}} {}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope } \pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}}v}(C_{i},H)\bigg{]}_ {i=1}^{d}=\bigg{[}{P}(v\xrightarrow{i}v)\bigg{]}_{i=1}^{k}=\text{RWSE}_{k}(v,H)$ $$

∎

###### Proof of Proposition 4.4 .

We first recall the walk refinement procedure from Lichter et al. () such that we can relate it directly to RWSE.

The scheme at its basis assumes a directed complete colored graph $G=(V,H,\chi)$ where the coloring $\chi$ always assigns different colors to self-loops than to other edges. For tuples of $m$ vertices $(v_{1},v_{2},\dots,v_{m})\in V^{m}$, we define

$$ $\bar{\chi}(v_{1},v_{2},\dots,v_{m})=((\chi(v_{1},v_{2}),\chi(v_{2},v_{3}), \dots,\chi(v_{m-1},v_{m})).$ $$

Ultimately, we want to use the scheme on undirected uncolored graphs. An undirected (and uncolored) graph $G$, is converted into the setting above by adding the coloring $\chi:V(G)\to\{-1,0,1\}$ as follows: for all self-loops $\chi$ assigns $-1$, i.e., $\chi(v,v)=-1$. For all distinct pairs $v,u$, we set $\chi(v,u)=1$ if $(v,u)\in E(G)$ and $\chi(v,u)=0$ if $(v,u)\not\in E(G)$. For the directed edges recall that we consider complete directed graphs and hence $E=V^{2}$.

With this in hand we can define the walk refinement procedure of Lichter et al. (). Formally, for $k\geq 2$, the $k$-walk refinement of a colored complete directed graph $G=(V,E,\chi)$ as the function that gives the new coloring $\chi_{W[k]}$ to every edge is as follows

$$ $\chi_{W[k]}(v,u)=\{\!\!\{\bar{\chi}(v,w_{1},\dots,w_{k-1},u)\mid w_{i}\in V\} \!\!\}$ $$

Intuitively, the refinement takes into account all walks of length $k$ in the graph. Note that walks of length shorter than $k$ are also captured via self-loops (because of their different weights we are also always aware that a self-loop is taken and that a specific tuple in the multi-set represents a shorter walk.
As with the Weisfeiler-Leman color refinement procedure, $k$-walk refinement can be iterated until it reaches a stable refinement (after finitely many steps). We will write $\chi^{i}(v,u)$ to designate the color obtained after $i$ steps of the refinement (with $\chi(v,u)=\chi^{0}(v,u)$). Importantly, Lichter et al. () (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 as 2-WL. That is, any pairs $(u,v)$ and $(x,y)$ that receive the same label by 2-WL refinement, also have $\chi^{\infty}(v,u)=\chi^{\infty}(x,y)$.

All that is then left is to show that the stable $W[k]$ refinement uniquely determines the RWSEk feature vector for every vertex $v$. In particular, we show that every entry of the RWSEk vector of any vertex $v$ can be uniquely derived from the $W[k]$ labeling of the pair $(v,v)$. As shown in Proposition 4.5, the $k^{\prime}$-th entry of the RWSEk vector for $v$, is uniquely determined by the number of $k^{\prime}$-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[k]$ labeling of $(v,v)$.

We first observe that $\chi^{1}_{W[k]}(v,v)$ uniquely determines the degree of $v$. It is equivalent to the number of $k$-walks that move to an adjacent vertex and continue with self-loops for the $k-1$ remaining steps. That is:

$$ $\mathsf{degree}(v)=\mathsf{degree}(\chi^{1}_{W[k]}(v,v)):=|\{(1,-1,-1,\dots,-1 )\in\chi^{1}_{W[k]}(v,v)\}|$ (2) $$

Similarly, it is straightforward to recognise the original label $\chi(v,u)$ from $\chi^{1}_{W[k]}(v,u)$:

$$ $\chi(v,u)=-1\iff\{-1\}^{k}\in\chi^{1}_{W[k]}(v,u)$ (3) $$

that is $v=u$ if and only if $u$ can be reached from $v$ only through self-loops. Similarly we can determine the other labels, and we only state the case for an edge existing here:

$$ $\chi(v,u)=1\iff(1,-1,-1,\dots,-1)\in\chi^{1}_{W[k]}(v,u).$ (4) $$

We can similarly retrieve the label $\chi(v,u)$ from $\chi^{2}_{W[k]}(v,u)$, since in any tuple of the form

$$ $((\chi(v_{1},v_{2}),\chi(v_{2},v_{3}),\dots,\chi(v_{m-1},v_{m}))$ $$

we know by Equation 3 and Equation 4 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\leq k^{\prime}\leq k$, we can directly enumerate all paths from $v$ to $v$ by inspecting the multiset $\chi^{2}(v,v)$.

To complete the argument outlined above, we need to show that for every $v,u$, $\chi^{2}(v,u)$ determines the degree of $v$. Now as above we can determine $\chi(v,u)$ and for each case observe how to obtain the degree. We have $\chi(v,u)=-1$, if and only if there is a tuple for the walk $(v,v,\dots,v)\in\chi^{2}(v,u)$ (and the tuple can be recognised). The degree is then directly determined by the first tuple through Equation 2. Similarly, $\chi(v,u)=1$, if and only if there is a tuple $(v,u,\dots,u)\in\chi^{2}(v,u)$ that corresponds to original labels $(-1,-1,\dots,-1,1)$. We can thus again obtain the degree from the first position of this tuple, and analogously for the 0 0 label.

In summary, we see that after 2 steps of $k$-walk refinement, every label of $(v,v)$ has enough information to uniquely determine all $1$ to $k$-walks from $v$ to $v$, together with the degree of every node of the walk. As seen in the proof of Proposition 4.5, this determines the RWSEk vector.
∎

We note that the proof in fact shows a stronger statement than RWSEk being at most as expressive as $2$-WL. It shows that RWSEk is at most as expressive as $2$-steps of $k$-walk refinement. This can be further related to equivalence under a certain number of 2-WL steps through the work of Lichter et al. ().

###### Proof of Proposition 4.7 .

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 $\ell$, RWSE produces the same node features for both green vertices ($u_{1},u_{2}$) and both black vertices ($v_{1},v_{2}$), 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.

For the other direction, we use the classic example comparing the graph $G$ consisting of two triangles and the graph $H$ containing the 6-vertex cycle as drawn below (Figure 5). It is well known that all nodes in both graphs have the same 1-WL label. In contrast, RWSE3 labels the nodes in $G$ differently from the nodes in $H$, and the respective vectors are given below.

Figure: Figure 5: The 6 vertex cycle (left) and the disjoint sum of 2 triangles (right) are indistinguishable by 1-WL, but distinguishable by RWSE already after 3 steps. The RWSE vectors in the respective graphs are all the same and are given next to the graphs.

∎

###### Proof of Proposition 4.5 .

###### Proof of Proposition 4.4 .

###### Proof of Proposition 4.7 .

## Appendix B Additional Experimental Details

We provide additional experimental details and hyperparameters relating to the results that were presented in Section 5. All code and instructions on how to reproduce our results are available at the following link: [https://github.com/linusbao/MoSE](https://github.com/linusbao/MoSE).

##### Compute Resources.

All experiments for ZINC, QM9, and the synthetic dataset were conducted on a cluster with 12 NVIDIA A10 GPUs (24 GB) and 4 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 a time.

### B.1 Model Definitions

We give definitions for those architectures which are not taken directly from the literature. Given a graph $G$ and a node $v\in V(G)$, let the node representation $\bm{h}^{(0)}_{v}\in\mathbb{R}^{d}$ be a vector concatenation of the initial node label and the structural/positional encoding of $v$. To apply an $L$-layer MLP on $G$, we update each node representation in parallel for $t=1,...,L$:

$$ $\bm{h}_{v}^{(t)}=\text{ReLU}\bigg{(}\bm{W}^{(t)}\bm{h}_{v}^{(t-1)}+\bm{b}^{(t) }\bigg{)},\qquad\forall\text{ }v\in 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 $\bm{h}_{v}^{(t)}$ are learned according to equation (5) using a set of weights $\{\bm{W}_{\text{node}}^{(t)},\bm{b}^{(t)}_{\text{node}}\}_{t=1}^{L}$, while the edge representations $\bm{e}_{u,v}^{(t)}\in\mathbb{R}^{d_{e}}$ are learned using a different set of weights:

$$ $\bm{e}_{u,v}^{(t)}=\text{ReLU}\bigg{(}\bm{W}_{\text{edge}}^{(t)}\bm{e}_{u,v}^{ (t-1)}+\bm{b}_{\text{edge}}^{(t)}\bigg{)},\qquad\forall\text{ }(u,v)\in E(G)$ $$

for $t=1,...,L_{e}$. Note that we *do not* require that $d=d_{e}$ and $L=L_{e}$.

The GT model updates node representations by using scaled dot-product attention (Vaswani et al., ):

$$ $\displaystyle\bm{h}_{v}^{(t)}$ $\displaystyle=\text{MLP}^{(t)}\bigg{(}\bm{W}^{(t)}_{O}\bigoplus_{h=1}^{n_{H}} \bm{W}^{(t)}_{V,h}\sum_{u\in V(G)}\alpha^{(t)}_{v,u,h}\bm{h}_{u}^{(t-1)}\bigg{)}$ (6) $\displaystyle\alpha^{(t)}_{v,u,h}$ $\displaystyle=\text{softmax}_{u}\left(\frac{\bm{W}^{(t)}_{Q,h}\bm{h}_{v}^{(t-1 )}\cdot\bm{W}^{(t)}_{K,h}\bm{h}_{u}^{(t-1)}}{\sqrt{d}}\right)$ (7) $$

for $t=1,...,L$. Here, the $\oplus$ symbol denotes vector concatenation, and softmax is computed relative to the vector formed by iterating the expression inside the softmax argument over $u\in V(G)$. When we are 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 $\bm{e}_{u,v,h}^{(t)}\in\mathbb{R}^{d}$ for every node pair $u\neq v\in V(G)$, every attention head $h=1,...,n_{H}$, and every layer $t=1,...,L$. Non-adjacent node pairs $(u,v)\notin E(G)$ are assigned some pre-defined “null edge-type”. Then, these edge representations bias the attention as:

$$ $\alpha^{(t)}_{v,u,h}=\text{softmax}_{u}\left(\frac{\text{dot}\big{[}\bm{W}^{(t )}_{Q,h}\bm{h}_{v}^{(t-1)},\bm{W}^{(t)}_{K,h}\bm{h}_{u}^{(t-1)},\bm{e}_{u,v,h} ^{(t)}\big{]}}{\sqrt{d}}\right)$ (8) $$

where

$$ $\text{dot}[\bm{a},\bm{b},\bm{c}]=\sum_{i}\bm{a}_{i}\cdot\bm{b}_{i}\cdot\bm{c}_ {i}$ $$

The node update equation of GT-E is defined by simply plugging in the edge-biased attention values $\alpha^{(t)}_{v,u,h}$ given by equation (8) into the node update equation (6). Our method of “biasing” attention values with edge representations (eq. 8) is inspired by the edge-type-aware graph transformer models of Dwivedi & Bresson () and Kreuzer et al. ().

The final node representations are sum pooled in order to produce a graph representation $\bm{h}_{G}$. The MLP-E model additionally pools edge representations and concatenates the edge pool to the node pool:

$$ $\displaystyle\bm{h}_{G}$ $\displaystyle=\sum_{v\in V(G)}\bm{h}_{v}^{(L)}\qquad\text{for MLP, GT, and GT-E}$ $\displaystyle\bm{h}_{G}$ $\displaystyle=\left(\sum_{v\in V(G)}\bm{h}_{v}^{(L)}\right)\oplus\left(\sum_{( u,v)\in E(G)}\bm{e}_{u,v}^{(L_{e})}\right)\qquad\text{for MLP-E}$ $$

Finally, an MLP prediction head is applied on $\bm{h}_{G}$ to produce an output label. The reader should note that equations (5)-(8) only describe the essential aspects of our models; when we implement these models in practice, we additionally include the usual regularization/auxiliary modules at each layer (e.g., batch normalization and dropout), as specified by the hyperparameter details below.

### B.2 ZINC Experimental Details

We use a subset of the ZINC molecular dataset that contains 12,000 graphs (Dwivedi et al., ). 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 a molecule, where the node features indicate the atom type, and the edge features indicate the bond type between two atoms (i.e. nodes).

#### B.2.1 ZINC with Edge Features

In Table 5, we provide additional results on ZINC-12k with edge features. Observe that the trend for MoSE performing better than RWSE remains consistent. For completeness sake, we also perform a series of experiments where we combine RWSE+MoSE encodings. The combination does not have any significant effect on the results. All results are reported as the average of 4 runs at different seeds.

**Table 5: 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.**
| Model | Encoding Type |  |  |  |
| --- | --- | --- | --- | --- |
|  | none | RWSE | MoSE | RWSE+MoSE |
| MLP-E | 0.606$\pm{}0.002$ | 0.361$\pm{}0.010$ | 0.347$\pm{}0.003$ | 0.349$\pm{}0.003$ |
| R-GCN | 0.413$\pm{}0.005$ | 0.207$\pm{}0.007$ | 0.197$\pm{}0.004$ | 0.188$\pm{}0.005$ |
| GIN-E | 0.243$\pm{}0.006$ | 0.122$\pm{}0.003$ | 0.118$\pm{}0.007$ | 0.117$\pm{}0.005$ |
| GIN-E+VN | 0.151$\pm{}0.006$ | 0.085$\pm{}0.003$ | 0.068$\pm{}0.004$ | 0.064$\pm{}0.003$ |
| GT-E | 0.195$\pm{}0.025$ | 0.104$\pm{}0.025$ | 0.089$\pm{}0.018$ | 0.090$\pm{}0.005$ |
| GPS | 0.119$\pm{}0.011$ | 0.070$\pm{}0.002$ | 0.062$\pm{}0.002$ | 0.065$\pm{}0.002$ |

#### B.2.2 ZINC without Edge Features

Dwivedi et al. () also present a set of experiments that uses the ZINC-12k dataset without edge features. This is becaue there are a number of models that do not take edge features into account. Therefore, we also perform a set of experiments on ZINC that do not include edge features and report the results in Table 6. Similarly to our experiments with edge features, we see that MoSE consistently outperforms RWSE across all models.

**Table 6: We report additional MAE results for various models on ZINC-12k without edge features.**
| Model | none | RWSE | MoSE | RWSE+MoSE |
| --- | --- | --- | --- | --- |
| MLP | 0.663$\pm{}0.002$ | 0.263$\pm{}0.006$ | 0.218$\pm{}0.005$ | 0.202$\pm{}0.001$ |
| GIN | 0.294$\pm{}0.012$ | 0.190$\pm{}0.004$ | 0.158$\pm{}0.004$ | 0.168$\pm{}0.005$ |
| GT | 0.674$\pm{}0.001$ | 0.217$\pm{}0.007$ | 0.209$\pm{}0.020$ | 0.184$\pm{}0.001$ |
| GPS | 0.178$\pm{}0.016$ | 0.116$\pm{}0.001$ | 0.102$\pm{}0.001$ | 0.105$\pm{}0.006$ |

#### B.2.3 Hyperparameters

We detail a rough summary of the hyperparameters that we use for the ZINC experiments in Table 7. These correspond to the results that are shown in Table 5. Note that all models are restricted to a parameter budget of roughly 500k.

For all models, we perform the same grid-search on each feature enhancement (none, RWSE, MoSE) independently. For MLP-E, we grid search depth $\times$ width:

$$ $\{2,4,8\}\times\{156,220,284,348\}$ $$

and each of these models is searched with a StepLR scheduler and a Cosine Annealing scheduler. For GT-E and GPS, we search depth $\times$ width $\times$ number of heads:

$$ $\{(8,74,4),(10,64,4),(10,92,4),(4,104,8)\}$ $$

Note that for GPS, we use a GIN-E message passing component to be able to account for the edge features. For the GIN-E and GIN-E+VN models, we use configurations that align with Jin et al. (). For the GRIT results that are presented in Table 2, we simply remove the RRWP node and node-pair encodings, and replace them with MoSE that is constructed from $\mathsf{Spasm}(C_{7})\cup\mathsf{Spasm}(C_{8})$. We conduct minimal hyperparameter tuning by only slightly adjusting the width of the model to account for the extra features. The exact configuration files can be found in our code repository.

**Table 7: Hyperparameters for ZINC experiments reported in Table 5.**
| Model | Layers | Hidden Dim | Batch Size | Learning Rate | Epochs | PE dim | #Heads |
| --- | --- | --- | --- | --- | --- | --- | --- |
| MLP-E | 4 | 128 | 128 | 0.001 | 1000 | 64 | N/A |
| GIN-E | 4 | 128 | 128 | 0.001 | 1000 | 64 | N/A |
| GIN-E+VN | 4 | 128 | 128 | 0.001 | 1000 | 64 | N/A |
| GT-E | 4 | 92 | 64 | 0.005 | 2000 | 64 | 4 |
| GPS | 4 | 92 | 64 | 0.005 | 2000 | 64 | 4 |

### B.3 QM9 Experimental Details

The QM9 dataset is another molecular dataset that consists of 130,831 graphs (Wu et al., ). They are split into 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 as its atomic number, the number of Hydrogens connected to it, etc. The edge features indicate bond type between two atoms (i.e. nodes). The task in this dataset is to predict 13 different quantum chemical properties, ranging from a molecule’s dipole moment ($\mu$) to its free energy ($G$). Note that for this dataset, we use the edge features provided for all of our experiments.

#### B.3.1 Additional Results on QM9

We provide additional results on the QM9 dataset for GPS in Table 8. All reported results are the average of 5 different runs at different seeds. Additionally, we provide the same analysis with a 4-layer MLP-E and the GT-E (Dwivedi & Bresson, ) model. These results are presented in Table 9 and Table 10 respectively. We consistantly see that across all models, MoSE outperforms RWSE. The division between using MoSE alone and a combination of RWSE+MoSE is less trivial than in the case of ZINC though. This is because in the QM9 dataset, due to the large number of tasks to regress over, some tasks may not be influenced by topological structure as much. Therefore, the benefit of using MoSE is less significant.

**Table 8: We report MAE results for GPS with various feature enhancements on the QM9 dataset.**
| Property | GPS | +RWSE | +MoSE | +RWSE+MoSE |
| --- | --- | --- | --- | --- |
| mu | 1.52$\pm{}0.02$ | 2.64$\pm{}0.11$ | 1.47$\pm{}0.02$ | 1.43$\pm{}0.02$ |
| alpha | 2.62$\pm{}0.38$ | 1.52$\pm{}0.27$ | 1.48$\pm{}0.16$ | 1.72$\pm{}0.11$ |
| HOMO | 1.17$\pm{}0.41$ | 0.91$\pm{}0.01$ | 0.91$\pm{}0.01$ | 0.92$\pm{}0.01$ |
| LUMO | 0.92$\pm{}0.01$ | 0.90$\pm{}0.06$ | 0.86$\pm{}0.01$ | 0.88$\pm{}0.16$ |
| gap | 1.46$\pm{}0.02$ | 1.47$\pm{}0.02$ | 1.45$\pm{}0.02$ | 1.48$\pm{}0.01$ |
| R2 | 6.82$\pm{}0.31$ | 6.11$\pm{}0.16$ | 6.22$\pm{}0.19$ | 6.01$\pm{}0.03$ |
| ZPVE | 2.25$\pm{}0.18$ | 2.63$\pm{}0.44$ | 2.43$\pm{}0.27$ | 2.23$\pm{}0.25$ |
| U0 | 0.96$\pm{}0.34$ | 0.83$\pm{}0.17$ | 0.85$\pm{}0.08$ | 0.80$\pm{}0.05$ |
| U | 0.81$\pm{}0.05$ | 0.83$\pm{}0.15$ | 0.75$\pm{}0.03$ | 0.78$\pm{}0.03$ |
| H | 0.81$\pm{}0.26$ | 0.86$\pm{}0.15$ | 0.83$\pm{}0.09$ | 0.87$\pm{}0.16$ |
| G | 0.77$\pm{}0.04$ | 0.83$\pm{}0.12$ | 0.80$\pm{}0.14$ | 0.72$\pm{}0.03$ |
| Cv | 2.56$\pm{}0.72$ | 1.25$\pm{}0.05$ | 1.02$\pm{}0.04$ | 1.03$\pm{}0.08$ |
| Omega | 0.40$\pm{}0.01$ | 0.39$\pm{}0.02$ | 0.38$\pm{}0.01$ | 0.39$\pm{}0.01$ |

**Table 9: We report MAE results for MLP-E with different structural encodings on the QM9 dataset.**
| Property | MLP-E | +RWSE | +MoSE | +RWSE+MoSE |
| --- | --- | --- | --- | --- |
| mu | 5.31$\pm{}0.03$ | 4.91$\pm{}0.06$ | 4.88$\pm{}0.05$ | 4.84$\pm{}0.03$ |
| alpha | 6.76$\pm{}0.04$ | 5.08$\pm{}0.18$ | 5.11$\pm{}0.11$ | 4.83$\pm{}0.09$ |
| HOMO | 2.96$\pm{}0.03$ | 2.46$\pm{}0.03$ | 2.36$\pm{}0.04$ | 2.34$\pm{}0.02$ |
| LUMO | 3.17$\pm{}0.04$ | 2.76$\pm{}0.3$ | 2.65$\pm{}0.03$ | 2.57$\pm{}0.03$ |
| gap | 4.34$\pm{}0.02$ | 3.58$\pm{}0.02$ | 3.45$\pm{}0.05$ | 3.35$\pm{}0.04$ |
| R2 | 43.69$\pm{}1.08$ | 26.69$\pm{}0.31$ | 26.50$\pm{}0.43$ | 24.97$\pm{}0.45$ |
| ZPVE | 14.36$\pm{}0.60$ | 10.42$\pm{}1.24$ | 8.94$\pm{}0.83$ | 10.28$\pm{}0.35$ |
| U0 | 8.06$\pm{}0.78$ | 5.39$\pm{}0.58$ | 5.30$\pm{}0.41$ | 4.74$\pm{}0.28$ |
| U | 8.33$\pm{}0.56$ | 5.34$\pm{}0.59$ | 5.19$\pm{}0.39$ | 5.10$\pm{}0.62$ |
| H | 8.19$\pm{}0.33$ | 5.17$\pm{}0.28$ | 4.77$\pm{}0.16$ | 5.08$\pm{}0.33$ |
| G | 7.58$\pm{}0.14$ | 5.83$\pm{}0.46$ | 5.28$\pm{}0.54$ | 5.03$\pm{}0.36$ |
| Cv | 6.06$\pm{}0.14$ | 3.80$\pm{}0.15$ | 3.73$\pm{}0.25$ | 3.72$\pm{}0.44$ |
| Omega | 1.61$\pm{}0.04$ | 1.29$\pm{}0.02$ | 1.17$\pm{}0.02$ | 1.24$\pm{}0.05$ |

**Table 10: We report MAE results for GT-E with different structural encodings on the QM9 dataset.**
| Property | GT-E | +RWSE | +MoSE | +RWSE+MoSE |
| --- | --- | --- | --- | --- |
| mu | 4.12$\pm{}0.05$ | 2.53$\pm{}0.06$ | 2.43$\pm{}0.01$ | 2.31$\pm{}0.06$ |
| alpha | 8.80$\pm{}4.65$ | 1.43$\pm{}0.03$ | 2.00$\pm{}0.08$ | 1.32$\pm{}0.01$ |
| HOMO | 1.72$\pm{}0.01$ | 1.15$\pm{}0.01$ | 1.11$\pm{}0.01$ | 1.08$\pm{}0.01$ |
| LUMO | 1.63$\pm{}0.01$ | 1.05$\pm{}0.02$ | 1.02$\pm{}0.01$ | 0.99$\pm{}0.01$ |
| gap | 2.38$\pm{}0.03$ | 1.67$\pm{}0.01$ | 1.62$\pm{}0.01$ | 1.57$\pm{}0.02$ |
| R2 | 26.73$\pm{}8.59$ | 8.30$\pm{}0.32$ | 10.69$\pm{}1.56$ | 7.80$\pm{}0.17$ |
| ZPVE | 10.39$\pm{}1.35$ | 2.46$\pm{}0.04$ | 4.66$\pm{}2.09$ | 2.37$\pm{}0.03$ |
| U0 | 6.27$\pm{}1.95$ | 0.94$\pm{}0.10$ | 2.56$\pm{}1.66$ | 0.98$\pm{}0.57$ |
| U | 5.38$\pm{}0.17$ | 0.92$\pm{}0.03$ | 3.10$\pm{}2.75$ | 1.40$\pm{}0.72$ |
| H | 5.30$\pm{}0.17$ | 0.92$\pm{}0.06$ | 3.49$\pm{}2.02$ | 0.96$\pm{}0.51$ |
| G | 5.44$\pm{}0.51$ | 0.88$\pm{}0.08$ | 2.72$\pm{}1.21$ | 0.63$\pm{}0.03$ |
| Cv | 4.32$\pm{}0.07$ | 1.25$\pm{}0.01$ | 1.43$\pm{}0.04$ | 1.15$\pm{}0.01$ |
| Omega | 1.25$\pm{}0.01$ | 0.50$\pm{}0.01$ | 0.47$\pm{}0.02$ | 0.46$\pm{}0.01$ |

#### B.3.2 Hyperparameters

We detail a rough summary of the hyperparameters that we use for the QM9 experiments in Table 11. Different tasks use different hyperparameters. The precise setup can be found in the github repository.

For MLP-E, we do not perform any grid searching and simply use the same hyperparameters for every task and every feature enhancement. For GPS and GT-E, we grid-search each feature enhancement independently (on a reduced number of epochs: 700). We first search the tasks R2, ZPVE, U0, and GAP on the following MPNN-type $\times$ depth $\times$ width $\times$ head $\times$ learning rate values:

$$ $\{\text{RGCN},\text{GINE}\}\times\{(8,128,8),(10,64,4),(12,256,8)\}\times\{0.0 001,0.00001\}$ $$

Then, the best two models from each results is searched on the corresponding tasks for each injection:

| Initial Search | Corresponding tasks |
| --- | --- |
| R2 | MU, ALPHA |
| ZPVE | OMEGA, Cv |
| U0 | U, H, G |
| GAP | HOMO, LUMO |

**Table 11: High-level summary of hyperparameters used for all 13 targets in QM9 experiments.**
| Model | Layers | Hidden Dim | Batch Size | Learning Rate | Epochs | PE Dim | #Heads |
| --- | --- | --- | --- | --- | --- | --- | --- |
| MLP-E | 4 | 220 | 128 | 0.001 | 800 | 64 | N/A |
| GT-E | 8, 10, 12 | 64, 128, 256 | 128 | 0.0001, 0.00001 | 1200 | 64 | 4, 8 |
| GPS | 8, 10, 12 | 64, 128, 256 | 128 | 0.0001, 0.00001 | 1200 | 64 | 4, 8 |

### B.4 Synthetic Dataset Details

We generate a new synthetic dataset where the goal is to predict the fractional domination number of a graph. The dataset contains 10,000 randomly-generated Erdős-Rényi graphs. The density range for the graph generation is between [0.25, 0.75], and the number of nodes varies from [16, 32].

A *fractional dominating set* of a graph $G$ is a weight assignment $\alpha:V(G)\to[0,1]$, such that for every vertex $v$, the weight assigned to it and its neighbours is at least 1. The weight of a fractional dominating set $\alpha$ is $\sum_{v\in V(G)}\alpha(v)$. The fractional domination number of $G$ is the least weight of a fractional dominating set of $G$ (Scheinerman & Ullman, ).

We select a 4-layer MLP and a standard self-attenion Graph Transformer (Dwivedi & Bresson, ) as our models in order to focus solely on the power of the graph inductive biases (MoSE, RWSE, LapPE). The percentage mean absolute error results for each model and configuration are reported in Table 12. For each model, we do not perform any hyperparameter tuning and use the settings from the ZINC experiments outlined above. In order to control for the high homomorphism count values, we scale the raw counts down by taking the log10 of the true values to construct MoSE. Please refer to our code for the specific configuration and data files.

**Table 12: Percentage MAE results for prediction the fractional dominantion number on our synthetic dataset. MoSE outperforms LapPE and RWSE in both an MLP and GT model.**
|  | LapPE | RWSE | MoSE |
| --- | --- | --- | --- |
| MLP | 48.22%$\pm{}.31$ | 7.53%$\pm{}.07$ | 5.79%$\pm{}.09$ |
| GT | 8.35%$\pm{}.06$ | 6.05%$\pm{}.08$ | 5.46%$\pm{}.10$ |

## Peer Reviews

confidence: 3
contribution: 2
initial_rating: 6
presentation: 3
questions: Please see Weaknesses
soundness: 3
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.
- The paper rigorously compares MoSE to established methods and relates its expressiveness to the WL hierarchy, grounding its effectiveness in theoretical proofs.
- 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.
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.
weaknesses: - The performance of MoSE may vary depending on the choice of motif graphs, requiring task-specific tuning to achieve optimal results.
- Calculating homomorphism counts for large and complex graphs could increase computational requirements, potentially limiting scalability for very large datasets.
- 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.

---

confidence: 3
contribution: 3
initial_rating: 6
presentation: 3
questions: What are the time and space complexities for computing MoSE encodings? How does the empirical preprocessing time compare to RWSE, RRWP, and LapPE?
soundness: 2
strengths: 1. The experiments supports the claim that MoSE improves performance on molecular property prediction tasks.
2. The theoretical arguments provide a plausible explanation for the observed performance gains.
3. The paper is well-organized and easy to follow.
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.
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.
2. 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.
    - 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.
    - 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.

---

confidence: 4
contribution: 3
initial_rating: 8
presentation: 4
questions: included with weaknesses.
soundness: 4
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.
- 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.
- 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.
- the proposed structural encoding has no limitations of LapPE such as sign ambiguity
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.
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?
- 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.

---

confidence: 5
contribution: 3
initial_rating: 6
presentation: 3
questions: Maybe the authors can point out why they evaluate on only these datasets.
soundness: 3
strengths: - The research topic makes sense given the recent insights of using homomorphisms in MPNNs.
- The paper is well-structured
- The synthetic data experiment is interesting, and the authors consider two different transformers as base models
- The model seems to achieve good improvements generally (the number of evidence seems a bit low)
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.
weaknesses: - The paper is sometimes annoying to read:
     - The reader is assumed to know quite some details (e.g., 
W/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)?)
     - 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.

- 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.
- 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:
"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. "
https://practicalcheminformatics.blogspot.com/2023/08/we-need-better-benchmarks-for-machine.html

- Beyond that, there's only Zinc12k, which is a bit of a low number of datasets for evaluation

Smaller comments:
- typo: alternative olibious k-WL
- l. 296 "f a graph in G." Is this \mathcal{G} ?
- FYI There's a recent related work: Deep Homomorphism Networks
https://neurips.cc/virtual/2024/poster/95659

---

confidence: 4
contribution: 3
initial_rating: 5
presentation: 3
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?
soundness: 4
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.

- 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.

- The paper is dense in some parts, but overall it is very well-written and the presentation is clear.
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.
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.

- 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?

- 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.

- 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.

Meta-review: (a) The paper proposes Motif Structural Encoding (MoSE), a novel structural encoding method for graph learning. It shows MoSE has greater expressive power than Random Walk Structural Encoding (RWSE) and is independent of the Weisfeiler-Lehman (WL) hierarchy. Empirically, MoSE outperforms other encodings on various datasets, especially in molecular property prediction.

(b) Strengths: 
Theoretically, MoSE's expressiveness is rigorously analyzed and compared with RWSE, providing a solid theoretical foundation. 
Empirically, it achieves state-of-the-art results on benchmarks, validating its effectiveness.
The paper is well-structured and the presentation is clear, facilitating understanding.

(c) Weaknesses: 
MoSE's performance may depend on motif graph choice, requiring task-specific tuning.
The theoretical contribution regarding homomorphism counts' expressivity may not be highly novel compared to some recent works.

(d) Reasons for acceptance: 
Despite the weaknesses, the paper makes a significant contribution. The proposed MoSE is a powerful encoding technique with clear theoretical and empirical advantages over existing methods. The authors addressed reviewers' concerns well, providing additional experiments and explanations. For example, they showed the negligible computational time for MoSE compared to training time, and demonstrated its flexibility in different scenarios. The overall quality of the paper, in terms of scientific content and presentation, justifies its acceptance.

Decision: Accept (Poster)