Path Neural Networks: Expressive and Accurate Graph Neural Networks
Graph neural networks (GNNs) have recently become the standard approach for
learning with graph-structured data. Prior work has shed light into their
potential, but also their limitations. Unfortunately, it was shown that
standard GNNs are limited in their expressive power. These models are no more
powerful than the 1-dimensional Weisfeiler-Leman (1-WL) algorithm in terms of
distinguishing non-isomorphic graphs. In this paper, we propose Path Neural
Networks (PathNNs), a model that updates node representations by aggregating
paths emanating from nodes. We derive three different variants of the PathNN
model that aggregate single shortest paths, all shortest paths and all simple
paths of length up to K. We prove that two of these variants are strictly more
powerful than the 1-WL algorithm, and we experimentally validate our
theoretical results. We find that PathNNs can distinguish pairs of
non-isomorphic graphs that are indistinguishable by 1-WL, while our most
expressive PathNN variant can even distinguish between 3-WL indistinguishable
graphs. The different PathNN variants are also evaluated on graph
classification and graph regression datasets, where in most cases, they
outperform the baseline methods.
Gaspard Michel, Giannis Nikolentzos, Johannes Lutzeyer, Michalis Vazirgiannis
# Path Neural Networks: Expressive and Accurate Graph Neural Networks

###### Abstract

Graph neural networks (GNNs) have recently become the standard approach for learning with graph-structured data. Prior work has shed light into their potential, but also their limitations. Unfortunately, it was shown that standard GNNs are limited in their expressive power. These models are no more powerful than the \(1\)-dimensional Weisfeiler-Leman (\(1\)-WL) algorithm in terms of distinguishing non-isomorphic graphs. In this paper, we propose Path Neural Networks (PathNNs), a model that updates node representations by aggregating paths emanating from nodes. We derive three different variants of the PathNN model that aggregate single shortest paths, all shortest paths and all simple paths of length up to \(K\). We prove that two of these variants are strictly more powerful than the \(1\)-WL algorithm, and we experimentally validate our theoretical results. We find that PathNNs can distinguish pairs of non-isomorphic graphs that are indistinguishable by \(1\)-WL, while our most expressive PathNN variant can even distinguish between \(3\)-WL indistinguishable graphs. The different PathNN variants are also evaluated on graph classification and graph regression datasets, where in most cases, they outperform the baseline methods.

Machine Learning, Graph Neural Networks, Graph Neural Networks, Graph Neural Networks

## 1 Introduction

Graphs have emerged in recent years as a powerful tool for representing irregular data. Among many other applications, graphs have been used to model the relationships between individuals within a social network (Easley and Kleinberg, 2010) and the interactions between the atoms of a molecule (Stokes et al., 2020). The large availability of graph-structured data has motivated the development of machine learning algorithms that are designed for this kind of data. Notably, most of those algorithms belong either to the family of graph kernels (Kriege et al., 2020; Borgwardt et al., 2020; Nikolentzos et al., 2021) or to that of graph neural networks (GNNs) (Wu et al., 2020; Zhou et al., 2020). Due to some limitations that are inherent to kernels (e. g., they do not scale to large datasets, they struggle with continuous features, etc.), GNNs have become the most common approach for dealing with graph learning problems.

GNNs have been studied extensively in the past years. So far, research in the field has mainly focused on message passing architectures (Gilmer et al., 2017). These models follow a recursive neighborhood aggregation scheme where each node aggregates the representations of its neighbors along with its own representation to compute new updated representations. It has been shown that there is a connection between the neighborhood aggregation scheme of these models and the relabeling procedure of the Weisfeiler-Leman (WL) algorithm, a well-known heuristic for testing graph isomorphism (Xu et al., 2019; Morris et al., 2019). More importantly, it was shown that the standard message passing architectures are at most as powerful as the WL algorithm in terms of distinguishing non-isomorphic graphs. This has led to the development of more complex models that focus on subgraphs (Maron et al., 2019; 20; Cotta et al., 2021). Some of these models are inspired by higher-order variants of the WL algorithm (Morris et al., 2019, 2020).

Besides subgraphs, there are also other structures of graphs that can improve a model's expressive power. For instance, paths can distinguish connected from disconnected graphs, while the WL algorithm fails to distinguish this property. Unfortunately, finding all paths in a graph is NP-hard. However, some subsets of paths can be computed in polynomial time. For instance, computing shortest paths in a graph is a problem solvable in polynomial time (Dijkstra, 1959). It has been shown that models that use shortest path distances between nodes as features can provide more expressive power than the WL algorithm (Li et al., 2020). Furthermore, if we restrict the length of the paths to some small integer \(k\), the parameterized complexity of computing all the bounded length paths is tractable.

In this paper, we propose Path Neural Networks (PathNNs), a GNN that generates node representations that are based on paths emanating from the nodes of graphs. By computing
different subsets of paths, we derive different variants of the proposed model. We focus on subsets whose computation is possible in polynomial time, namely shortest paths and simple paths of bounded length. For each path length, the proposed model uses a recurrent layer to encode paths into vectors and then, the representations of all paths emanating from a node are aggregated to produce the node's new representation. We show that two of the three PathNN variants are strictly more powerful than the WL algorithm in terms of distinguishing non-isomorphic graphs. Our theoretical results are confirmed by experiments on synthetic datasets that measure the models' expressive power. Furthermore, we evaluate the PathNNs on real-world graph classification and regression datasets1. Our results demonstrate that the different PathNN variants achieve high levels of performance and outperform the baseline methods in most cases. Our main contributions are summarized as follows:

Footnote 1: Code available at [https://github.com/gasmichel/PathNNs_expressive](https://github.com/gasmichel/PathNNs_expressive)

* We develop PathNN, a neural network that computes node representations by aggregating paths of increasing length. We derive three different variants of the model that focus on single shortest paths, all shortest paths and all simple paths, respectively.
* We prove that two of the variants are strictly more powerful than the WL algorithm and we empirically measure their expressive power.
* We evaluate the proposed model on several graph classification and regression datasets where it achieves performance comparable to state-of-the-art GNNs.

## 2 Related Work

**GNNs and kernels that process paths.** Shortest path distances between nodes have been incorporated as structural features into several GNN architectures. For instance, Graphormer encodes shortest path distances between two nodes as a bias term in the softmax attention (Ying et al., 2021), while other models annotate nodes with features that emerge from shortest paths (e. g., shortest path distances) (Li et al., 2020; You et al., 2019). On the other hand, PEGN uses shortest path distances to create persistence diagrams based on which messages between nodes are re-weighted (Zhao et al., 2020). Instead of aggregating the representations of each node's direct neighbors, some models such as SP-MPNN (Abboud et al., 2022) also consider the nodes at shortest path distance exactly \(k\) from the node. A recently proposed GNN framework, so-called Geodesic GNN (Kong et al., 2022), generates representations for pairs of nodes by aggregating the representations of the nodes on a single shortest path between the two nodes and also the direct neighbors of the two nodes that are on any of their shortest paths. Perhaps the work most related to our approach is the PathNet model (Sun et al., 2022), which also aggregates path information. However, there are major differences between PathNet and our PathNNs. PathNet samples paths instead of enumerating all of them, it is only evaluated on node classification datasets, and lastly, the authors do not provide an extensive study of the expressive power of the model. There exist also models that instead of paths simulate walks which are then either aggregated (Jin et al., 2022) or processed by a convolution neural network (Toenshoff et al., 2021).

Our proposed PathNNs are also related to graph kernels which compare paths of two graphs to each other. Such kernels include the shortest path kernel (Borgwardt and Kriegel, 2005) and the GraphHopper kernel (Feragen et al., 2013). The former just compares shortest path distances to each other, while the latter is more similar to the proposed model since it also takes into account the attributes of the nodes that appear on a shortest path.

**Expressive power of GNNs.** Since we will study the expressive power of our PathNNs, our work is furthermore related to the extensive literature exploring the expressive power of GNNs. Several of those studies have investigated the connections between GNNs and the WL test of isomorphism (Barcelo et al., 2020; Geerts and Reutter, 2022). For instance, standard GNNs were shown to be at most as powerful as the WL algorithm in terms of distinguishing non-isomorphic graphs (Morris et al., 2019; Xu et al., 2019). Other studies capitalized on high-order variants of the WL algorithm to derive new models that are more powerful than standard GNNs (Morris et al., 2019, 2020). Another line of research focused on \(k\)-order graph networks (Maron et al., 2019). Importantly, \(k\)-order graph networks were found to be at least as powerful as the \(k\)-WL graph isomorphism test in terms of distinguishing non-isomorphic graphs, while a reduced \(2\)-order network containing just a scaled identity operator, augmented with a single quadratic operation was shown to have \(3\)-WL discrimination power (Maron et al., 2019). Furthermore, it was shown that a GNN with a maximum tensor order \(2\) defined on the ring of equivariant functions can distinguish some pairs of non-isomorphic regular graphs with the same degree (Chen et al., 2019). Graph isomorphism testing and invariant function approximation, the two main perspectives for studying the expressive power of GNNs, have been shown to be equivalent to each other (Chen et al., 2019). Recently, a large body of work focused on making GNNs more powerful than WL, e. g., by encoding vertex identifiers (Vignac et al., 2020), taking into account all possible node permutations (Murphy et al., 2019; Dasoulas et al., 2020), using random features (Sato et al., 2021; Abboud et al., 2021), using node features (You et al., 2021), spectral information (Balcilar
et al., 2021), simplicial and cellular complexes (Bodnar et al., 2021b;a) and directional information (Beaini et al., 2021). Furthermore, several recent studies extract and process subgraphs to make GNNs more expressive (Nikolentzos et al., 2020; Bevilacqua et al., 2022). For example, the expressive power of GNNs can be increased by aggregating the representations of subgraphs (produced by standard GNNs) that arise from removing one or more vertices from a given graph (Cotta et al., 2021; Papp et al., 2021). Finally, it was recently shown that models that process each node's \(k\)-hop neighborhood and which aggregate nodes at shortest path distance exactly \(k\) from that node (such as the SP-MPNN model (Abboud et al., 2022)) are more powerful than standard GNNs (Feng et al., 2022), while the expressive power of those models can be further improved by taking into account the edges that connect the nodes at shortest path distance exactly \(k\) from the considered node.

## 3 Path Neural Networks

In this section, we begin by introducing some key notation for graphs which will be used later, and then we describe Path Neural Networks (PathNNs), a message-passing GNN that learns representations of paths of increasing length which are aggregated to update node representations. We first introduce the theoretical framework of PathNNs and then detail their architecture.

### Notation

Let \(\{\!\!\}\) denote a multiset, i. e., a generalized concept of a set that allows multiple instances for its elements. Let \(G=(V,E)\) be an undirected graph consisting of a set of nodes \(V\) and a set of edges \(E\subseteq V\times V\). We denote by \(n\) the number of nodes in \(G\) and by \(m\) its number of edges. The set \(\mathcal{N}(v)\) represents the neighbors of vertex \(v\). When considering attributed graphs, each vertex \(v\in V\) is endowed with an initial node feature vector denoted by \(\mathbf{x}_{v}\) that can contain categorical or real-valued properties of \(v\).

A path from source node \(v\) to target node \(u\) is denoted by \(\pi=[v_{1},v_{2},\ldots,v_{k}]\) such that \(v_{1}=v\), \(v_{k}=u\) and \((v_{i},v_{i+1})\in E\) for \(i\in\{1,\ldots,k-1\}\). Note that paths only contain distinct vertices. We denote by \(\pi(j)=v_{j}\) the \(j\)-th node encountered when hopping along the path, and by \(|\pi|=k-1\) its length, defined by the number of edges it contains. In this work, we consider various collections of paths. The first collection is the set of shortest paths denoted as \(\mathcal{SP}\) containing a single shortest path for all possible node pair combinations. Multiple shortest paths between a source node and a target node might exist. We thus also consider the collection of all shortest paths that we denote as \(\mathcal{SP}^{+}\), containing all possible shortest paths between every node pair combinations. A simple path can be any path, not necessarily the shortest, from a source node to a target node. We denote by \(\mathcal{AP}\) the collection of all simple paths between node pair combinations. Figure 1 provides an example of these three collections of paths. Note that, we have \(\mathcal{SP}\subseteq\mathcal{SP}^{+}\subseteq\mathcal{AP}\). In practice, we only consider paths up to a fixed length \(k\). We use the notation \(\mathcal{P}^{k}_{v}=\{\pi\in\mathcal{P}:\;\pi(1)=v,\;|\pi|=k\}\) for \(\mathcal{P}\in\{\mathcal{SP},\mathcal{SP}^{+},\mathcal{AP}\}\) to denote all paths of length \(k\) contained in \(\mathcal{P}\) starting from node \(v\). Similarly, \(\mathcal{P}_{v}\) denotes the set of all paths in \(\mathcal{P}\in\{\mathcal{SP},\mathcal{SP}^{+},\mathcal{AP}\}\) starting from node \(v\) of any length.

### Theoretical Framework

In this section, we assume that for any graph \(G\), we have the collections of all paths of maximum length \(K\) at our disposal for all nodes in \(G\). We furthermore consider any collection of paths \(\mathcal{P}\in\{\mathcal{SP},\mathcal{SP}^{+},\mathcal{AP}\}\) that is induced by a graph \(G\). All proofs can be found in Appendix A. We begin by introducing the concept of _WL-Trees_ and _Path-Trees_. Path-Trees are an intuitive path-based, rather than walk-based, analogue to WL-Trees. We will then show that Path-Trees are not able to distinguish graphs at a node-level for all collections of paths, which will motivate us to instead define a model operating on annotated sets of paths, which we will show to disambiguate graphs at least as well as WL-Trees.

WL-Trees of a given root node are constructed one level

Figure 1: (a) A graph G with \(n=6\) vertices. (b) Shortest paths of length up to \(2\) starting from vertex \(v_{1}\), (c) all shortest paths of length up to \(2\) starting from vertex \(v_{1}\) and (d) all paths of length up to \(3\) starting from vertex \(v_{1}\).
at a time. At each iteration, level \(k+1\) of a WL-Tree is constructed by setting the children of any node at level \(k\) to its direct neighbors. In the context of the WL algorithm the color of a node \(v\) at iteration \(k\) of the 1-WL algorithm represents a tree structure of height \(k\) rooted at \(v\). The WL-Tree of the graph in Figure 1(a) is provided in Figure 2(a). Similarly, we define Path-Trees, where we make use of the notation \(\mathcal{T}\) to denote all Path-Trees, and \(\mathcal{T}^{k}\) to denote Path-Trees of height \(k\).

**Definition 3.1**.: (Path-Tree rooted at \(v\)) Let \(G=(V,E)\) and \(\mathcal{P}\in\{\mathcal{SP},\mathcal{SP}^{+},\mathcal{AP}\}\) be a collection of any type-specific paths in \(G\). A Path-Tree \(P_{v}\subseteq\mathcal{T}\), induced by \(\mathcal{P}_{v}\) for \(v\in V,\) is a tree such that the node set at level \(k\) of the tree is equal to the multisets of nodes that occur at position \(k\) in the paths in \(\mathcal{P}_{v}^{k}\), i.e., \(\{\!\!\{u:\pi(k)=u\text{ for }\pi\in\mathcal{P}_{v}^{k}\}\!\!\}\). Nodes at level \(k\) and level \(k+1\) in the tree are connected if and only if they occur in adjacent positions \(k\) and \(k+1\) in a given path in the set of paths \(\mathcal{P}_{v}\), i.e., \((x,y)\in P_{v}\) if \(\pi(k)=x\) and \(\pi(k+1)=y\) for any \(\pi\in\mathcal{P}_{v}\) such that each node at level \(k+1\) is connected only to a single node at level \(k\). The height \(k\) Path-Tree \(P_{v}^{k}\subseteq\mathcal{T}^{k}\) rooted at \(v\) corresponds to the Path-Tree of \(v\) pruned from all levels \(l>k\).

Different collections of paths lead to different Path-Trees, as shown in Figure 2. To give the reader a more practical understanding of Path-Trees we now explain how a \(k\) Path-Tree can be constructed from any collection of paths \(\mathcal{P}\in\{\mathcal{SP},\mathcal{SP}^{+},\mathcal{AP}\}\). We iteratively build the Path-Tree for a given source node \(v\) one level \(k\in\{1,\ldots,K\}\) at a time, where we make use of the subset \(\mathcal{P}_{v}^{k}\) of \(\mathcal{P}_{v}\subseteq\mathcal{P}\) to construct level \(k\) of the Path-Tree. In the first iteration we add the root node \(v\) to the Path-Tree. Then, at subsequent iterations we add the multiset of nodes at position \(k\) in the paths in \(\mathcal{P}_{v}^{k}\) to the Path-Tree. We then iteratively connect these added nodes to the Path-Tree via edges, where a given node \(u\) of the added nodes is connected to a single leaf \(w\) in the existing Path-Tree such that the ordered set of ancestors of \(w\) in the Path-Tree is identical to the ordered set of nodes preceding \(u\) in its path of length \(k\) from which the addition of \(u\) resulted.

Intuitively, for a given graph \(G\) and a given node \(v\) the \(\mathcal{SP}\)-Tree rooted at \(v\) is a subgraph of the \(\mathcal{SP}^{+}\)-Tree which is itself a subgraph of the \(\mathcal{AP}\)-Tree. Another interesting property of Path-Trees is provided in the following lemma.

**Lemma 3.2**.: _Let \(G=(V,E)\) and \(\mathcal{P}\in\{\mathcal{SP},\mathcal{SP}^{+},\mathcal{AP}\}\) be any collection of paths in \(G\). Let \(P_{v}^{k}\) be the Path-Tree rooted at \(v\) of height \(k\) and \(W_{v}^{k}\) be the WL-Tree rooted at \(v\) of height \(k\) for \(v\in V\). Then \(P_{v}^{k}\) is a subgraph of \(W_{v}^{k}\)._

Lemma 3.2 can be easily proved by noting that a WL-Tree rooted at node \(v\) of height \(k\) is equivalent to an enumeration of all walks that start at \(v\) of length up to \(k\). Since paths are a special case of walks, Path-Trees are subgraphs of WL-Trees, for all collections of paths.

Each type of Path-Trees contain a different type of structural information over the input graph. \(\mathcal{SP}\) and \(\mathcal{SP}^{+}\) Trees contain the most compressed information over shortest paths. In particular, they can only answer the question of _what is the shortest path distance between a given node and any other node in \(G\)?_ The \(\mathcal{AP}\)-Trees encode the largest amount of structural information over the input graph. Besides, they are not height-limited by the graph's diameter. However, they usually grow exponentially with the height \(k\) and the density of the input graph. We now state our main theorem on the relation between \(\mathcal{AP}\)-Trees and WL-Trees.

**Theorem 3.3**.: _Let \(G=(V,E)\) and \(\mathcal{AP}\) be the collection of all simple paths in \(G\). Let \(\{AP_{v}^{k},AP_{u}^{k}\}\subseteq\mathcal{T}^{k}\) be the \(\mathcal{AP}\)-Trees of height \(k\) rooted at \(v\) and \(u\), respectively, and \(W_{v}^{k}\), \(W_{u}^{k}\) be the WL-Trees of height \(k\) rooted at \(v\) and \(u\), respectively, for \(v,u\in V\). If \(W_{v}^{k}\) is structurally different (i. e., not isomorphic) than \(W_{u}^{k}\), then \(AP_{v}^{k}\) is structurally different than \(AP_{u}^{k}\). Additionally, \(AP_{v}^{k}\) and \(AP_{u}^{k}\) can be different even if \(W_{v}^{k}\) and \(W_{u}^{k}\) are identical._

Theorem 3.3 states that, if at iteration \(k\) 1-WL decides that two nodes have different colors, then their \(\mathcal{AP}\)-Trees are structurally different. Additionally, it states that \(\mathcal{AP}\)-Trees are also able to disambiguate nodes that the 1-WL algorithm would determine to be structurally similar. Hence, a model \(f:\mathcal{AP}\rightarrow\mathbb{R}^{d}\) that embeds \(\mathcal{AP}\)-Trees into \(d\)-dimensional

Figure 2: (a) WL-Tree rooted at node \(v_{1}\) for the graph of Figure 1(a). (b) One of the two \(\mathcal{SP}\)-Trees rooted at \(v_{1}\) of height \(2\). (c) \(\mathcal{SP}^{+}\)-Tree rooted at \(v_{1}\) of height \(2\) and (d) \(\mathcal{AP}\)-Tree rooted at \(v_{1}\) of height \(3\). Note that we consider only \(\mathcal{SP}\) and \(\mathcal{SP}^{+}\)-Trees of height up to \(2\) because there is no shortest path of length higher than \(2\) that starts at \(v_{1}\) in the input graph.
vectors, such that non-isomorphic trees are embedded into different vectors, also equipped with an injective readout function is more expressive than the 1-WL algorithm. Note that only considering \(\mathcal{AP}\)-Trees up to a fixed height \(K\) is sufficient to distinguish a broad class of graphs.

Now that we have considered the case of all paths \(\mathcal{AP}\), we turn our attention to the case of the shortest paths in \(\mathcal{SP}\) and \(\mathcal{SP}^{+}\). In Proposition 3.4 we show that \(\mathcal{SP}\)-Trees and \(\mathcal{SP}^{+}\)-Trees are unable to capture all differences in WL-Trees.

**Proposition 3.4**.: _Let \(G=(V,E)\) and \(\mathcal{P}\) be the collection of either single shortest paths \(\mathcal{SP}\) or all shortest paths \(\mathcal{SP}^{+}\) in \(G\). Let \(\{P^{k}_{v},P^{k}_{w}\}\subseteq\mathcal{T}^{k}\) be the \(\mathcal{P}\)-Trees of height \(k\) rooted at \(v\) and \(u\), respectively, and \(W^{k}_{v}\), \(W^{k}_{u}\) be the WL-Trees of height \(k\) rooted at \(v\) and \(u\), respectively, for \(v,u\in V\). If \(W^{k}_{v}\) is structurally different than \(W^{k}_{u}\), then \(P^{k}_{v}\) is not necessarily structurally different from \(P^{k}_{u}\)._

Hence, Path-Trees based on the collections of shortest paths do not necessarily allow us to disambiguate individual nodes structurally even when the WL test does so. We therefore propose to operate on annotated sets of paths instead of Path-Trees. We use \(\tilde{\mathcal{SP}},\tilde{\mathcal{SP}}^{+}\) and \(\tilde{\mathcal{AP}}\) to denote annotated paths in the single shortest path, all shortest path and all simple path collections, respectively. The annotations of nodes in \(\tilde{\mathcal{P}}\in\{\tilde{\mathcal{SP}},\tilde{\mathcal{SP}}^{+},\tilde{ \mathcal{AP}}\}\) depend on the length of the considered path. For paths of length 1, i.e., \(\tilde{P}^{1}\in\tilde{\mathcal{P}}\), all nodes have equal annotations. For paths of length 2, i.e., \(\tilde{P}^{2}\in\tilde{\mathcal{P}}\), all nodes \(v\) in these paths are annotated with hashes of their respective annotated path sets of length 1, i.e., \(\tilde{P}^{1}_{v}\). In general for paths of length \(k\), i.e., \(\tilde{P}^{k}\in\tilde{\mathcal{P}}\), all nodes \(v\) in these paths are annotated with hashes of their respective annotated path sets of length \(k-1\), i.e., \(\tilde{P}^{k-1}_{v}\). Each annotation of paths of length \(k>2\), is therefore a multiset of sequences of annotations. In Theorem 3.5 we demonstrate that any annotated path set \(\tilde{\mathcal{P}}\in\{\tilde{\mathcal{SP}},\tilde{\mathcal{SP}}^{+},\tilde{ \mathcal{AP}}\}\) allows us to disambiguate individual nodes structurally at least as well as the WL test. Consequently, any model composed of injective functions that operates on annotated sets of paths, which notably includes the PathNNs that we will define in Section 3.3, is able to disambiguate graphs at least as well as the WL algorithm.

**Theorem 3.5**.: _Let \(G=(V,E)\) and \(\tilde{\mathcal{P}}\in\{\tilde{\mathcal{SP}},\tilde{\mathcal{SP}}^{+},\tilde{ \mathcal{AP}}\}\) denote an annotated set of paths, in which every node is annotated according to a recursive annotation scheme, in which a node \(v\) occurring in a path of length \(k\) is annotated by the hash of \(v\)'s annotated path sets of length \(k-1\), i.e., \(\tilde{P}^{k-1}_{v}\) and the initial annotations of all nodes are equal. Let \(\tilde{P}^{k}_{v}\) and \(\tilde{P}^{k}_{u}\) be the annotated sets of paths of length \(k\) emanating from nodes \(v,u\in V\), respectively, and \(W^{k}_{v}\), \(W^{k}_{u}\) be the WL-Trees of height \(k\) rooted at \(v\) and \(u\), respectively, for \(v,u\in V\)._

_Then, if \(W^{k}_{v}\) and \(W^{k}_{u}\) are unequal, then \(\tilde{P}^{k}_{v}\) and \(\tilde{P}^{k}_{u}\) are unequal. Additionally, \(\tilde{P}^{k}_{v}\) and \(\tilde{P}^{k}_{v}\) can be different even if \(W^{k}_{v}\) and \(W^{k}_{v}\) are identical._

We want to remark that depending on the particular shortest path that is sampled in the single shortest path collection \(\tilde{\mathcal{SP}}\) it is possible that even isomorphic nodes have different annotated sets of paths. For \(\tilde{\mathcal{SP}}^{+}\) and \(\tilde{\mathcal{AP}}\) isomorphic nodes always have corresponding identical annotated sets of paths. Therefore, models operating on \(\tilde{\mathcal{SP}}^{+}\) and \(\tilde{\mathcal{AP}}\) are strictly more powerful than the WL algorithm for graph isomorphism. While models operating on \(\tilde{\mathcal{SP}}\) can only disambiguate graphs at least as well as the WL algorithm and are not strictly more powerful, since also isomorphic graphs could be mapped to different representations.

### Model Architecture

We adopt a message passing scheme that iteratively updates node representations using paths of increasing length. This message passing scheme allows us to refine sets of paths with additional structural information included in paths of length smaller than \(K\).

Noting that paths are ordered sequences of nodes, PathNNs learn to embed paths into \(d\)-dimensional feature vectors, using a function operating on sequences \(f:\mathbb{R}^{k\times d}\rightarrow\mathbb{R}^{d},\) where \(k\) is the path length. PathNNs employ a message-passing scheme that aggregates path embeddings to form updated node representations. Specifically, at each layer \(k\), paths of length \(k\) are embedded by \(f\) and aggregated. Let \(\pi\) be any path of length \(k\). Then, PathNNs compute the embedding of \(\pi\) by using the node representations of layer \(k-1\)

\[\mathbf{h}^{(k)}_{\pi}=f\left(\left[\mathbf{h}^{(k-1)}_{\pi(k+1)},\ldots, \mathbf{h}^{(k-1)}_{\pi(1)}\right]\right). \tag{1}\]

PathNNs start to encode paths of length \(1\) in the first layer (i. e., sequences of a node and its neighbors' representations), then iteratively encode paths of increasing length. Path representations form the message in the message passing architecture and are used to update node feature vectors in a similar way to traditional MPNNs

\[\mathbf{a}^{(k)}_{v} =\text{AGGREGATE}^{(k)}\left(\left\{\left\{\mathbbm{h}^{(k)}_{ \pi}|\pi\in\mathcal{P}^{k}_{v}\right\}\right\}\right),\] \[\mathbf{h}^{(k)}_{v} =\text{COMBINE}^{(k)}\left(\mathbf{h}^{(k-1)}_{v},\,\mathbf{a}^{(k) }_{v}\right).\]

Paths of length up to \(K\) are given as input to PathNNs by stacking \(K\) layers. Figure 3 illustrates the functioning of PathNNs. Graph representations are obtained using a permutation-invariant readout function

\[\mathbf{h}_{G}=\text{READOUT}\left(\left\{\mathbbm{h}^{(K)}_{v}|v\in V \right\}\right).\]

Without loss of generality, we propose to use a simple instance of PathNNs in this paper. The function \(f\) operating
on sequences is modeled and learned by a Long-Short-Term-Memory (LSTM) cell (Hochreiter and Schmidhuber, 1997). LSTMs are a valid choice for the function \(f\) thanks to the universal approximation results for Recurrent Neural Network (Hammer, 2000): they can approximate any injective sequence function arbitrarily well in probability, which is a desirable and necessary property for \(f\). Note that the last element in the sequence is the starting node representation. The LSTM operates on reversed paths as we hypothesize that the most important information in the sequence is the starting node's current representation. We project node initial feature vectors to match the LSTM's hidden dimension with a 2-layer Multilayer Perceptron (MLP). Using paths embeddings, PathNNs then update node representations using the following rule

\[\mathbf{g}_{v}^{(k)} =\text{NORM}^{(k)}\left(\mathbf{h}_{v}^{(k-1)}+\sum_{\pi\in \mathcal{P}_{v}^{k}}\mathbf{h}_{\pi}^{(k)}\right), \tag{2}\] \[\mathbf{h}_{v}^{(k)} =\phi\left(\mathbf{g}_{v}^{(k)}\right). \tag{3}\]

Noting that the collection of paths \(\mathcal{P}_{v}^{k}\) grows larger with graph density, the right hand side of Equation (2) can be of very high magnitude, leading to numerical instabilities. A Batch Normalization (BN) layer (Ioffe and Szegedy, 2015) is thus applied in Equation (2) to avoid such situations during training. After normalization, node representations are passed through a \(\phi\) function, which can be either the identity function or a 2-layer MLP. Both functions are a valid choice as sum and 2-layer MLPs are injective functions over multisets (Xu et al., 2019). Equipped with the identity aggregation function, the number of parameters of PathNNs only slightly increases with path length (caused by BN parameters), resulting in a low number of trainable parameters even for higher path lengths. Replacing the identity function with an MLP allows finer updated node representations but leads to higher time and memory complexity. Finally, PathNNs use the sum over the multiset of final node representations as a readout function to produce a vector representation of the entire graph

\[\mathbf{h}_{G}=\sum_{v\in V}\mathbf{h}_{v}^{(K)}. \tag{4}\]

### Time and Space Complexity

To enumerate all shortest paths and all simple paths of length up to \(k\) from a source vertex to all other vertices, we use the depth-first search (DFS) algorithm. The time complexity of the algorithm is at most \(\mathcal{O}(b^{k})\), where \(b\) is the branching factor of the graph which is upper bounded by the maximum of the nodes' degrees. Thus, for all the nodes of the graph, the time complexity is \(\mathcal{O}(nb^{k})\). The space complexity is \(\mathcal{O}(nbk)\) if duplicate nodes are not eliminated.

Real-world graphs are often small (e. g., molecules) and/or sparse (e. g., social networks), i.e., \(n\) is often small and/or \(b\ll n\). Thus, for bounded \(k\), the time and space complexity for enumerating the paths is not prohibitive.

The running time of the model depends on the number of paths which is \(\mathcal{O}(nb^{k})\). Typically, the larger the value of \(k\), the larger the number of paths and therefore, the complexity of our model increases as a function of \(k\). For \(k=1\), the complexity of our model is comparable to that of standard GNNs which aggregate \(2m\approx nb\) representations. However, for larger values of \(k\), the time complexity of our model is greater than that of standard GNNs which only aggregate

Figure 3: Aggregation process of PathNN with \(\mathcal{P}=\mathcal{SP}\) for two iterations. Node colors corresponds to node feature vectors.
\(2m\) representations in all neighborhood aggregation layers. We report the empirical running times of our PathNNs on two real-world datasets in Appendix B.

## 4 Experimental Evaluation

We now evaluate the performance of our PathNNs in synthetic experiments specifically designed to exhibit the expressiveness of GNNs in Section 4.1 and on a range of real-world datasets in Section 4.2.

### Synthetic Datasets

**Datasets.** We use \(3\) publicly available datasets: (1) the Circular Skip Link (CSL) dataset (Murphy et al., 2019); (2) the EXP dataset (Abboud et al., 2021); (3) the SR dataset.

**Experimental setup.** For all experiments, the aggregation function \(\phi\) of Equation (3) is set to the identity function and the normalization layer of Equation (2) is removed. We set initial node features to be vectors of ones, and process them using a \(2\)-layer MLP. A 1-layer MLP is applied to the final graph representation to generate predictions.

The benchmarks CSL and EXP-Class require the classification of graphs into isomorphism classes. To evaluate the model's performance, we used \(5\)-fold cross validation on CSL and \(4\)-fold cross validation on EXP-Class. Graphs contained in the CSL dataset present a maximum diameter of \(11\). We thus set \(K\) to \(11\) for PathNN-\(\mathcal{SP}\) and PathNN-\(\mathcal{SP}^{+}\). \(K\) is set to \(5\) for PathNN-\(\mathcal{AP}\). As EXP graphs are disconnected, we empirically set \(K\) to \(10\) for PathNN-\(\mathcal{SP}\) and PathNN-\(\mathcal{SP}^{+}\) and \(5\) for PathNN-\(\mathcal{AP}\) since these values allow the models to achieve perfect performance in this task. For both experiments and all models, we train for \(200\) epochs using the Adam optimizer with learning rate \(10^{-3}\). The hidden dimension size is set to \(64\). Batch sizes are set to \(32\) except for PathNN-\(\mathcal{AP}\) where we set it to \(8\) for CSL and \(16\) for CEXP to be able to fit all paths in memory. For PathNN-\(\mathcal{AP}\), we apply Euclidean normalization before feeding the representations to the LSTM. Euclidean normalization is used instead of BN because the latter results in training instabilities. All PathNN-\(\mathcal{AP}\) models are trained with distance encoding.

For the SR and EXP-Iso datasets, we investigate whether the proposed models have the right inductive bias to distinguish these pairs of graphs. Similarly to Bodnar et al. (2021), we consider two graphs isomorphic if the Euclidean distance between their representation is below a fixed threshold \(\varepsilon\). Graph representations are computed by an untrained model variant where the prediction layer is removed. We remove the normalization layer of Equation (2) and instead apply Euclidean normalization to the LSTM's input. For EXP-Iso, we use the same \(K\) as in the experiments on EXP-Class. For the SR datasets, we set \(K\) to \(4\) as retrieving all paths of lengths higher than \(4\) is computationally challenging on these densely connected graphs. Hidden dimension size is set to \(16\) and \(\varepsilon\) to \(10^{-5}\). The experiment is repeated with \(5\) different seeds.

**Results.** The results are given in Table 1 and in Figure 4. We observe that the two most expressive variants of the proposed model, namely Path-\(\mathcal{SP}^{+}\) and Path-\(\mathcal{AP}\), can distinguish all \(10\) isomorphism classes present in the CSL dataset. On the other hand, PathNN-\(\mathcal{SP}\) fails to distinguish one of the \(10\) classes, but still significantly outperforms the GIN model. All three variants of the proposed model achieve perfect accuracy on EXP-Class and never fail on the EXP-Iso dataset. Those datasets contain graphs that are not distinguishable by 1-WL, and thus, not surprisingly, GIN maps the graphs of each pair to the same vector. Finally, we evaluate the most expressive variant of our model (i. e., PathNN-\(\mathcal{AP}\)) on the SR dataset whose instances contain graphs not distinguishable by 3-WL. We can see in Figure 4 that in most cases, PathNN-\(\mathcal{AP}\) can successfully distinguish more than \(80\%\) of the graphs contained in each instance of the dataset. SR\((29,14,6,7)\) seems to be particularly hard for PathNN-\(\mathcal{AP}\) since its failure rate on this instance is high compared to its performance on other instances. Overall, our experiments confirm the high expressiveness of the proposed model in terms of distinguishing non-isomorphic graphs.

\begin{table}
\begin{tabular}{l c c c} \hline \hline Model & **CSL \(\uparrow\)** & **EXP-Class \(\uparrow\)** & **EXP-Iso \(\downarrow\)** \\ \hline GIN (Xu et al., 2019) & \(10.0\pm 0.0\) & \(50.0\pm 0.0\) & 600 \\ 3WLGNN (Maron et al., 2019) & \(97.8\pm 10.9\) & \(\textbf{100.0}\pm 0.0\) & **0** \\ \hline PathNN-\(\mathcal{SP}\) & \(90.0\pm 0.0\) & \(\textbf{100.0}\pm 0.0\) & **0** \\ PathNN-\(\mathcal{SP}^{+}\) & \(\textbf{100.0}\pm 0.0\) & \(\textbf{100.0}\pm 0.0\) & **0** \\ PathNN-\(\mathcal{AP}\) & \(\textbf{100.0}\pm 0.0\) & \(\textbf{100.0}\pm 0.0\) & **0** \\ \hline \hline \end{tabular}
\end{table}
Table 1: Test set classification accuracy (CSL, EXP-Class) and number of undistinguished pairs of graphs (EXP-Iso). Best results are highlighted in bold.

Figure 4: Failure rate on different instances of the SR dataset.
### Real-World Datasets

**Datasets.** We evaluate the proposed model on \(6\) datasets contained in the TUDataset collection (Morris et al., 2020): DD, NCI1, PROTEINS, ENZYMES, IMDB-B and IMDB-M. We also evaluate the proposed model on ogbg-molhiv, a molecular property prediction dataset from the Open Graph Benchmark (OGB) (Hu et al., 2020). We conduct an experiment on the ZINC 12K dataset (Dwivedi et al., 2020). Finally, we experiment with Peptides-struct and Peptides-func (Dwivedi et al., 2022), two datasets that require long-range dependencies between nodes to be captured.

**Experiment setup.** In all experiments, we use 2-layer MLPs with BN to map initial node representations to the desired dimension, and 2-layer MLPs without BN for prediction. All PathNN-\(\mathcal{AP}\) are trained with distance encoding.

Following Errica et al. (2020), we evaluate TUDatasets using a \(10\)-fold cross validation using their provided data splits. We let \(\phi\) be a ReLU non-linearity and choose hidden dimension size from \(\{32,64\}\). We apply dropout to the input of the LSTM layer and between the first and second layer of the final MLP. The dropout rate is chosen from \(\{0,0.5\}\). We run the experiment for various values of \(K\in\{1,2,3\}\) to analyze the effect of increased path length on performance. The batch size is set to \(32\) for all datasets and all values of \(K\) except for simple paths on DD with \(K=2\) where we had to decrease batch size to \(16\) because of memory constraints. The Adam optimizer is used with fixed learning rate \(0.001\). The diameter of the graphs contained in IMDB-B and IMDB-M is at most equal to \(2\). Thus, for those two datasets, we do not provide results for paths of length up to \(K=3\). Similarly to Errica et al. (2020), we use one-hot encodings of given node attributes for all datasets except IMDB-B and IMDB-M, where we instead use one-hot encodings of node degrees. We also include the \(18\) continuous node feature vectors available for ENZYMES. We fit each model for \(500\) epochs and stop training if validation accuracy does not increase for \(250\) epochs.

All other experiments are conducted using available data splits. We set \(\phi\) to a 2-layer MLP with BN for all experiments and set \(K\) and the layer's hidden size to respect the \(500K\) parameter budget for ZINC, Peptides-functional and Peptides-structural. Details about the hyperparameter configuration can be found in Appendix D. All of these datasets contain additional edge features. Similarly to the Distance aware LSTM cell described in Appendix C.1, we build an Edge LSTM cell that takes as input a sequence of node and edge representations. For \(\mathcal{AP}\), the LSTM cell encodes both edges in the path and distance from the central node. Further detail can be found in Appendix E.

**Results.** Table 2 illustrates the classification accuracy achieved by the proposed PathNNs and the baselines on the six datasets from the TUDataset collection. We observe that our PathNNs outperform the baselines on \(5\) out of the \(6\) datasets. When \(K=1\), all three variants of our model are identical, since all path variants are identical when paths of length one are considered. We denote this variant by PathNN-\(\mathcal{P}\). On most datasets, PathNN-\(\mathcal{P}\) provides the highest accuracy. This is not surprising for IMDB-B and IMDB-M since the graphs contained in these datasets are ego-networks of radius \(2\). On the other hand, it appears that on DD and NCI1, more global information needs to be captured. On these two datasets, models that consider paths of length up to \(K=3\) achieve the highest accuracy. On some datasets, the proposed model significantly outperforms the baselines. Notably, on the ENZYMES, NCI1 and

\begin{table}
\begin{tabular}{l|c c c c c c} \hline \hline  & **DD** & **PROTEINS** & **NCI1** & **ENZYMES** & **IMDB-B** & **IMDB-M** \\ \hline DGCNN (Zhang et al., 2018) & \(76.6\pm 4.5\) & \(72.9\pm 3.5\) & \(76.4\pm 1.7\) & \(38.9\pm 5.7\) & \(69.2\pm 3.0\) & \(45.6\pm 3.4\) \\ DiffPool (Ying et al., 2018) & \(75.0\pm 4.3\) & \(73.7\pm 3.5\) & \(76.9\pm 1.9\) & \(59.5\pm 5.6\) & \(68.4\pm 3.3\) & \(45.6\pm 3.4\) \\ ECC (Simonovsky \& Komodakis, 2017) & \(72.6\pm 4.1\) & \(72.3\pm 3.4\) & \(76.2\pm 1.4\) & \(29.5\pm 8.2\) & \(67.7\pm 2.8\) & \(43.5\pm 3.1\) \\ GIN (Xu et al., 2019) & \(75.3\pm 2.9\) & \(73.3\pm 4.0\) & \(80.0\pm 1.4\) & \(59.6\pm 4.5\) & \(71.2\pm 3.9\) & \(48.5\pm 3.3\) \\ GraphsSAGE (Hamilton et al., 2017) & \(72.9\pm 2.0\) & \(73.0\pm 4.5\) & \(76.0\pm 1.8\) & \(58.2\pm 6.0\) & \(68.8\pm 4.5\) & \(47.6\pm 3.5\) \\ GAT (Velickovic et al., 2018) & \(73.9\pm 3.4\) & \(70.9\pm 2.7\) & \(77.3\pm 2.5\) & \(49.5\pm 8.9\) & \(69.2\pm 4.8\) & \(48.2\pm 4.9\) \\ SPN (\(K=1\)) (Abboud et al., 2022) & \(72.7\pm 2.6\) & \(71.0\pm 3.7\) & \(80.0\pm 1.5\) & \(67.5\pm 5.5\) & NA & NA \\ SPN (\(K=5\)) (Abboud et al., 2022) & \(77.4\pm 3.8\) & \(74.2\pm 2.7\) & \(78.6\pm 3.8\) & \(69.4\pm 6.2\) & NA & NA \\ PathNet (\(N=10\), \(K=2\)) (Sun et al., 2022) & \(\text{OM}\) & \(70.5\pm 3.9\) & \(64.1\pm 2.3\) & \(69.3\pm 5.4\) & \(70.4\pm 3.8\) & \(49.1\pm 3.6\) \\ Nested GNN (Zhang \& Li, 2021) & \(\text{\boldmath{77.8}}\pm 3.9\) & \(74.2\pm 3.7\) & NA & \(31.2\pm 6.7\) & NA & NA \\ \hline PathNN-\(\mathcal{P}\) (\(K=1\)) & \(76.9\pm 3.7\) & \(\text{\boldmath{75.2}}\pm 3.9\) & \(77.5\pm 1.6\) & \(\text{\boldmath{73.0}}\pm 5.2\) & \(\text{\boldmath{72.6}}\pm 3.3\) & \(\text{\boldmath{50.8}}\pm 4.5\) \\ PathNN-\(\mathcal{SP}\) (\(K=2\)) & \(75.3\pm 2.7\) & \(73.1\pm 3.1\) & \(82.0\pm 1.6\) & \(71.6\pm 6.4\) & \(70.8\pm 3.5\) & \(50.0\pm 4.1\) \\ PathNN-\(\mathcal{SP}\) (\(K=3\)) & \(77.0\pm 3.1\) & \(72.2\pm 2.7\) & \(82.2\pm 1.7\) & \(69.2\pm 4.7\) & - & - \\ PathNN-\(\mathcal{SP}^{+}\) (\(K=2\)) & \(74.7\pm 3.0\) & \(73.1\pm 3.7\) & \(81.0\pm 1.4\) & \(72.5\pm 5.3\) & \(70.5\pm 3.4\) & \(50.7\pm 4.5\) \\ PathNN-\(\mathcal{SP}^{+}\) (\(K=3\)) & \(76.5\pm 4.6\) & \(73.2\pm 3.3\) & \(\text{\boldmath{83.2}}\pm 1.9\) & \(70.4\pm 3.1\) & - & - \\ PathNN-\(\mathcal{AP}\) (\(K=2\)) & \(75.0\pm 4.4\) & \(73.1\pm 4.9\) & \(81.3\pm 1.8\) & \(71.8\pm 4.8\) & \(71.7\pm 3.6\) & \(49.8\pm 4.2\) \\ PathNN-\(\mathcal{AP}\) (\(K=3\)) & \(\text{OOM}\) & \(73.1\pm 4.0\) & \(82.3\pm 1.7\) & \(69.0\pm 5.3\) & OOM & OOM \\ \hline \hline \end{tabular}
\end{table}
Table 2: Classification accuracy (\(\pm\) standard deviation) of our PathNNs and the baselines on the datasets from the TUDataset collection. Best performance is highlighted in **bold**. OOM means out-of-memory and NA means not available.
IMDB-M datasets, our PathNNs offer respective absolute improvements of \(3.6\%\), \(2.3\%\) and \(1.7\%\) in accuracy over the best competitor. Overall, our results indicate that PathNNs achieve high levels of performance on the TUDatasets.

We next evaluate the proposed model on the two datasets that require long-range interaction reasoning to achieve strong performance. The results are shown in Table 3. We can see that the variants of our PathNNs outperform the baselines on both datasets. On Peptides-Functional, our model offers a respective absolute improvement of \(8.86\%\) in average precision over GCN, while on Peptides-Structural, it offers a respective absolute improvement of \(8.80\%\) in mean absolute error over GatedGCN. To summarize, our results suggest that PathNNs can better capture long-range interactions between nodes than the baseline models.

Table 4 shows the ROC-AUC of the different methods on the ogbg-molhiv dataset. We observe that PathNN is ranked as the third best model on this dataset. Among the three variants of the proposed model, PathNN-\(\mathcal{SP}^{+}\) achieves the highest ROC-AUC score. The other two variants perform slightly worse than PathNN-\(\mathcal{SP}^{+}\). This experiment validates the effectiveness of the proposed model on large graph classification datasets.

Finally, we evaluate the proposed model in a graph regression task on ZINC\(12\)K in Table 5. The three PathNN variants outperform most of the baselines on this dataset, despite, some of the baseline models, such as 3WLGNN, ESAN and GNNML3, being very expressive models considered to be state-of-the-art for many graph learning problems. With regards to the three PathNN variants, PathNN-\(\mathcal{AP}\) performs best, but all three models exhibit promising performance.

## 5 Conclusion

We presented the PathNN model that aggregates path representations to generate node representations. We proposed three different variants that focus on single shortest paths, all shortest paths and all simple paths of length up to \(K\). We have shown some of our PathNNs to be strictly more powerful than the \(1\)-WL algorithm. Experimental results confirm our theoretical results. The different PathNN variants were also evaluated on graph classification and graph regression tasks. In most cases, our PathNNs outperform the baselines.

## Acknowledgements

G.N. is supported by ANR via the AML-HELAS (ANR-19-CHIA-0020) project and by the funding Ecole Universitaire de Recherche (EUR) Bertip, plan France 2030.

\begin{table}
\begin{tabular}{l|c} \hline \hline  & **ogbg-molhiv \(\uparrow\)** \\ \hline GCN (Kipf and Welling, 2017) & 76.06 \(\pm\) 0.97 \\ GIN (Xu et al., 2019) & 75.58 \(\pm\) 1.40 \\ GCN-FLAG (Kong et al., 2020) & 76.83 \(\pm\) 1.02 \\ GIN+FLAG (Kong et al., 2020) & 76.54 \(\pm\) 1.14 \\ GSN (Bourikans et al., 2022) & 77.99 \(\pm\) 1.00 \\ HIMP (Fey et al., 2020) & 78.80 \(\pm\) 0.82 \\ PNA (Corso et al., 2020) & 79.05 \(\pm\) 1.32 \\ DGN (Besini et al., 2021) & 79.70 \(\pm\) 0.97 \\ Graphcym (Ying et al., 2021) & 80.51 \(\pm\) 0.53 \\ CIN (Bodnar et al., 2021a) & **80.94**\(\pm\) 0.57 \\ ESAN (Bevilacqua et al., 2022) & 78.00 \(\pm\) 1.42 \\ E-SWN (Abboud et al., 2022) & 77.10 \(\pm\) 1.20 \\ GRWNN (Nikocntezos and Vizingiannis, 2023) & 78.38 \(\pm\) 0.99 \\ AgentNet (Marinkus et al., 2023) & 78.33 \(\pm\) 0.69 \\ \hline PathNN-\(\mathcal{SP}\)\((K=2)\) & 78.62 \(\pm\) 1.30 \\ PathNN-\(\mathcal{SP}^{+}\)\((K=2)\) & 79.17 \(\pm\) 1.09 \\ PathNN-\(\mathcal{AP}\)\((K=2)\) & 78.84 \(\pm\) 1.46 \\ \hline \hline \end{tabular}
\end{table}
Table 4: ROC-AUC score (\(\pm\) standard deviation) of the different methods on the ogbg-molhiv dataset. Results are averaged over \(10\) random seeds. Best performance is highlighted in **bold**.

\begin{table}
\begin{tabular}{l|c|c|c} \hline \hline  & \(K\) & **Peptides-Functional \(\uparrow\)** & \(K\) **Peptides-Structural \(\downarrow\)** \\ \hline GCN (Kipf and Welling, 2017) & 5 & 93.06 \(\pm\) 0.023 & 5 & 0.3496 \(\pm\) 0.0013 \\ GIN (Xu et al., 2019) & 5 & 54.98 \(\pm\) 0.79 & 5 & 0.3547 \(\pm\) 0.0045 \\ GatedGCN (Kipf and Welling, 2017) & 5 & \(86.64\) \(\pm\) 0.77 & 5 & 0.3420 \(\pm\) 0.0013 \\ (Breison and Laurent, 2017) & 5 & \(86.16\) \(\pm\) 0.26 & 4 & 0.2545 \(\pm\) 0.0032 \\ PathNN-\(\mathcal{SP}^{+}\) & 8 & \(67.84\) \(\pm\) 0.52 & 4 & **0.2540**\(\pm\) 0.0046 \\ PathNN-\(\mathcal{AP}\) & 7 & \(68.07\) \(\pm\) 0.72 & 4 & 0.2569 \(\pm\) 0.0030 \\ \hline \hline \end{tabular}
\end{table}
Table 3: Results on the Peptides-Functional and Peptides-Structural datasets (\(\pm\) standard deviation). Evaluation metrics are Average Precision and Mean Absolute Error, respectively. Best performance is highlighted in **bold**. Parameter budget is set to \(500\)K parameters. Results are averaged over \(4\) random seeds.

\begin{table}
\begin{tabular}{l|c} \hline \hline  & \(K\) & **ZINC12K \(\downarrow\)** \\ \hline GCN (Kipf and Welling, 2017) & 16 & 0.278 \(\pm\) 0.003 \\ GraphSAGE (Hamilton et al., 2017) & 16 & 0.398 \(\pm\) 0.002 \\ Moket (Monti et al., 2017) & 16 & 0.292 \(\pm\) 0.006 \\ GAT (Velikovic et al., 2018) & 16 & 0.384 \(\pm\) 0.007 \\ GIN (Xu et al., 2019) & 5 & 0.387 \(\pm\) 0.015 \\ GatedGCN (Bresson and Laurent, 2017) & 4 & 0.435 \(\pm\) 0.011 \\ GatedGCN-E (Bresson and Laurent, 2017) & 4 & 0.282 \(\pm\) 0.015 \\ RingCNN (Chen et al., 2019) & 2 & 0.353 \(\pm\) 0.019 \\
3WLGNN (Maron et al., 2019a) & 3 & 0.407 \(\pm\) 0.028 \\
3WLGNN-E (Maron et al., 2019a) & 3 & 0.256 \(\pm\) 0.054 \\ GNNML3 (Balcilar et al., 2021) & NA & 0.161 \(\pm\) 0.006 \\ Graphcym (Ying et al., 2012) & NA & 0.122 \(\pm\) 0.006 \\ CIN (Bodnar et al., 2021a) & NA & **0.079**\(\pm\) 0.006 \\ ESAN (Bevilacqua et al., 2022) & NA & 0.102 \(\pm\) 0.003 \\ KP-GIN (Feng et al., 2022) & NA & 0.093 \(\pm\) 0.007 \\ AgentNet (Marinkus et al., 2023) & NA & 0.258 \(\pm\) 0.033 \\ \hline PathNN-\(\mathcal{SP}\) & 4 & 0.104 \(\pm\) 0.002 \\ PathNN-\(\mathcal{SP}^{+}\) & 4 & 0.131 \(\pm\) 0.008 \\ PathNN-\(\mathcal{AP}\) & 4 & 0.090 \(\pm\) 0.004 \\ \hline \hline \end{tabular}
\end{table}
Table 5: Mean absolute error (\(\pm\) standard deviation) of the different methods on the ZINC\(12\)K datasets. Results are averaged over \(10\) random seeds. Best performance is highlighted in **bold**. Parameter budget is set to \(500\)K parameters.