Maximally Expressive GNNs for Outerplanar Graphs
Authors: Franka Bause
Fabian Jogl
Patrick Indri
Tamara Drucks
David Penz
Nils Morten Kriege
Thomas Gärtner
Pascal Welke
Maximilian Thiessen
Venue: Accepted by TMLR ()

Abstract: We propose a linear time graph transformation that enables the Weisfeiler-Leman (WL) algorithm and message passing graph neural networks (MPNNs) to be maximally expressive on outerplanar graphs. Our approach is motivated by the fact that most pharmaceutical molecules correspond to outerplanar graphs. Existing research predominantly enhances the expressivity of graph neural networks without specific graph families in mind. This often leads to methods that are impractical due to their computational complexity. In contrast, the restriction to outerplanar graphs enables us to encode the Hamiltonian cycle of each biconnected component in linear time. As the main contribution of the paper we prove that our method achieves maximum expressivity on outerplanar graphs. Experiments confirm that our graph transformation improves the predictive performance of MPNNs on molecular benchmark datasets at negligible computational overhead.

Published in Transactions on Machine Learning Research (12/2024)
Maximally Expressive Graph Neural Networks for Outerplanar Graphs
Franka Bause Fabian Jog!'31, Patrick Indri', Tamara Drucks David Penzá. Nils M. Kriege Thomas Gärtner', Pascal Welke", Maximilian Thiessen"
Faculty of Computer Science, University of Vienna, Vienna, Austria
UniVie Doctoral School Computer Science, University of Vienna, Vienna, Austria
Machhie Learning Researeh Unit, TU Wien, Vienna, Austria
Center for Artificial Intelligence and Machine Learning, Vienna, Austria Multimedia Mining and Search, Johannes Kepler University Line, Linz, Austria Research Network Data Science, University of Vienna, Vienna, Austria.
ffrrstnamellastname) (univve,,, tuwien).ac.at
Reviewed OpenReview: https: openreview. net/ formm???? id= X=bQAAssRRC
Abstract
We propose linear time graph transformation that enables the Weisfeiler-LLman (WL) algorithm and message passing graph neural networks (MPNNs) to be maximally expressive on outerplanar graphs. Our approach is motivated by the fact that most pharmaceutical molecules correspond to outerplanar graphs. Existing research predominantly enhances the expressivity of graph noural networks without specific graph familics in mind. This often leads to methods that are impractical due to their compulational complexity. contrast, the restriction outerplanar graphs enables us to encode the Hamiltonian cycle of each biconnected component in linear time. As the main contribution of the paper we prove that method achieves maximum expressivity outerplanar graphs. Experiments confirm that our graph transformation improves the predictive performance of MPNNs on molecular benchmark datasets at negligible computational overhead.
1 Introduction
We study graph neural networks (GNNs) for the class of outerplanar graphs and devise a linear time pre- processing step that message passing graph neural networks (MPNNs) to distinguish all non-isomorphic outerplanar graph. Morris et al. (2019) and Xu al. (2019) showed that MPNNs have limitod expressivity, i.e., there exist non-isomorphie graphs on which each MPNN produces the same embedding. Such graphs exist even within the restricted class of outerplanar graphs (see Figure 1). This led to the development of GNNs that are more expressive than MPNNs, often called higher-order GNNs. However, the increase in expressivity usually comes with a significant increase in computational complexity. For example, k- GNNs (Morris et al., 2019) have a time complexity of (([V1*). Other higher-order GNNs count pattern graphs such as cliques (Bodnar et al., 2021b), cycles (Bodnar et al., 2021a;b), and general subgraphs (Bouritsas et al., 2022), which can take time exponential in the pattern size. However, for certain domains of interest, the graph structure can be exploited to build efficient higher-order GNNs. In this work, we focus on the pharmaceutical domain and on graphs that represent molecules. Over 92% to 97% of the graphs in widely used benchmark datasets in this domain are outerplanar (see Table 1). The properties of outerplanar graphs have been exploited by algorithms for graph mining (Horváth et al., 2010) and molecular similarity computation (Schietgat et al., 2013; Droschinsky et al., 2017), but not yet for GNNs. We focus on this
"Equal contribution.

---

Published in Transactions on Machine Learning Research (12/2024)
The molecules bicyclopentyl (left) and decalin (right) which correspond to outerplanar graphs that cannot be distinguished by MPNNs and 1-WL.
Figure 1:
class of graphs and devise linear time transformation that allows MPNNs to become maximally expressive outerplanar graphs. This implies that, in principle, our architecture can solve any learning task on outerplanar graphs. While this does not mean that any given maximally expressive model will perform well in practice, our experiments show that our proposed transformation improves the predictive performance of several GNN architectures on multiple benchmark learning tasks.
We propose to docompose outerplanar graphs into biconnected outerplanar components and trees. Using the fact that each biconnected outerplanar component has a unique Hamiltonian cycle that can be computed in linear time, we split each component into two graphs corresponding to the directed Hamiltonian cycles, and prove that MPNNs are maximally expressive on biconnected outerplanar graphs transformed in this way. Taking advantage of the well-known fact that MPNNs are maximally expressive on labeled trees (Arvind et al., 2015; Kiefer, 2020), we exlend our result to a linear time graph transformation called Cyclic A Adjacency Transform (CAT) that works on all outerplanar graphs. We benchmark CAT with common MPNNs on a varicty of molccular graph benchmarks and show that CAT consistently boosts the performance of MPNNs.
Main contributions. We propose CAT, a lincar time graph transformation that renders MPNNs max- imally expressive on outerplanar graphs. Experimentally, CAT consistently improves the performance of MPNNs with little increase in runtime.
2 Discussion and Related Work
Since the expressivity of MPNNs is bounded by the 1-WL algorithm (Morris et al., 2019; Xu et al., 2019), any pair of non-isomorphic graphs that cannot be distinguished by 1-WL will get mapped the same embedding by any given MPNN. One such pair of graphs are the molecules decalin and bicyclopentyl (see Fig. 1). As these two graphs are outerplanar, it follows that MPNNs graphs. Furthermore, in the graph mining community it is well known that many pharmaceutical molecules are outerplanar (Horváth et al., 2006; Horváth & Ramon, 2010). Outerplanarity has also been discussed in the context of reconstruction with GNNs (Cotta et al., 2021). This motivates the need for GNNs that are highly expressive on outerplanar graphs. Outerplanar graphs have treewidth at most two (Bodlacnder, 1998), and Kiefer (2020) showed that 3- is sufficiently expressive to distinguish all outerplanar graphs. Hence, any GNN that matches the expressivity of WL, such as 3-IGN (Maron al., 2019) or 3-GNN (Morris et al., 2019), is capable of solving main goal of distinguishing all outerplanar graphs. However, single iteration of a naive implementation of the 3-WL algorithm (Immerman & Lander, 1990; Kiefer, 2020), which can be infeasible even for medium-sized real-world graphs. Similarly, a single 3-GNN or 3-IGN layer runs in roughly Onn3) time (Maron et al., 2019; Morris et al., 2019). Even when additionally restricting the graph class to biconnected outerplanar graphs, MPNNs are not sufficiently expressive. Furthermore, Zhang et al. (2023b) have shown that most GNNs cannot even detect simple properties associated with biconnoctivity such as articulation vertices. They find that only their distance-based GNN and specific GNNs based on subgraphs (Bevilacqua et al., 2021; Frasca et al., 2022) are able to detect some of these properties. Again, these approaches have at least quadratic worst case runtime.
not sufficiently expressive for outerplanar
graph with vertices is at least O(n")
It is not straight forward to use outerplanarity to efficiently improve the expressivily of GNNs, as even finding a subgraph remains NP-hard for outerplanar graphs (Syslo, 1982). Thus, methods like the graph structural network (Bouritsas et al., 2022) that rely on counting subgraphs remain computationally expensive even on outerplanar graphs. Subgraph GNNs model graphs as a collection of subgraphs (Frasca al., 2022), which usually requires a pre-processing with at least quadratic runtime, depending on the method used to extract
2

---

Published in Transactions on Machine Learning Research (12/2024)
179
189
189
179
139
179
170
139
19
Figure 2: A graph and both directions of its directed Hamiltonian cycle. Nodes are annotated with their HALs, the distances on the Hamiltonian cycle to their neighbors (Colbourn & Booth, 1981).
subgraphs. For example, Node-delete (Bevilacqua et al., 2021) creates all subgraphs that are obtained by deleting a single node creating Onn²) nodes in total. k-ego-net (Bevilacqua et al., 2021) extracts the k-hop neighborhood for each node which for k 2 2 can create O(n²) nodes in the worst case, for example for star graphs which are also outerplanar.
Recently, Dimitrov et al. (2023) have proposed PlanE, GNN architecture that can distinguish all planar graphs in O(n²) time. As consequence, PlanE is also able to distinguish all outerplanar graphs. However, this comes at the cost of (1) runtine, (2) flexibility, and counter-intuitively (3) expressivily. (1) PlanE requires a quadratic time pre-processing whereas our proposed CAT+MPNN runs in linear time. (2) PlanE is a GNN architecture while CAT is a graph transformation. This means, that CAT can be combined with any GNN while PlanE requires specialized GNN layers which are not casily combined with other architectures. (3) Without changes to PlanE's pre-processing, PlanE incapable of operating on graphs with non-planar components whereas CAT still achieves at least 1-WL expressivity on such graphs. This leads to the counter-intuitive result that vanilla PlanE is incomparable in expressivity to CAT (sce Prop. 2 and 3 in the Appendix).
Finally, while there exist many GNNs that are provably more expressive than WL, little is known about the precise class of graphs for which such GNNs are provably maximally expressive. Furthermore, proving an upper bound on the expressivity of an architecture is considered difficult and requires significant effort as demonstrated by Zhang et al. (2023a). In contrast, we identify outerplanar graphs as a large practical graph family that our proposed method CAT can distinguish.
3 Preliminaries
A graph G= (V,EE,,,,)) consists of a set of nodes V, a set of edges E S V x V and attributes (also called features) for the nodes μ:: + X and edges v: E + X, respectively, where X is a set of arbitrary altributes. We refer to an edge from u to by we and in case of undirected graphs ur vu. The in-neighhors of a node u E V are denoted by [u) = {o vu E E}. The out-neighbors of a node u V are denoted by Nour = {u uv E E} and in case of undirected graphs, Nn Nout- In this paper, the input graphs are undirected and are transformed into directed ones. A graph G' = (V', F', ju',()) )') is subgraph of graph G, denoted by G' C G, iff V CV, E" C E, Vu E V': V": p'()) = =(v), and Ve E E" v'(e) = v(e). A (directed) 0,04+1 E E and d&tl E E.
cycle (VI,..., U2) is a sequence of k 2 3 distinct nodes, with Vi E (l,..., 1) 1} A graph is acyelic if it does not contain a cycle. Given a graph G, we denote the shortest path distance between two nodes u and e by da(u, v), or d(u, v) if G is clear from the context. We denote the diameter of graph G by (G)) max d(u,u).
A graph is outerplanar if it can be drawn in the plane without edge crossings and with all nodes belonging to the exterior face (see Appendix A for details). We call an undirected graph with at least three vertices biconmected if the removal of any single node does not disconnect the graph. A biconnected component is a maximal biconnected subgraph. We refer to the outerplanar biconnected components a graph as blocks.
Two graphs G and H are isomorphic, V(G): p(v) = p(v(v)) A we E E(G) + (())((u) E E(H) A Yur E E(G): v(w)) v(v(w)(())). We call sp isomorphism between G and H. An in-tree T is directed, acyelic graph with distinct root
there exists a bijection s: V(G) - V(H), so that Vu, v e
3

---

Published in Transactions on Machine Learning Research (12/2024)
Figure 3: Biconnected outerplanar graph G, (G), and unfolding tree of node b.
having no outgoing edges and all other nodes having one outgoing edge and for every node there is exactly one path from it the root.
Weisfeiler-Leman. The 1-dimensional Weisfeiler-Leman algorithm (WL) assigns colors (usually rep- resented by numbers) to nodes. The color of node E V(G) is updated iteratively according to (++1()) = h (c)(v), (()) E (m))), where h is an injective function and co = μ.. Note, that this variant of WL makes use of edge features and works on directed graphs. While traditionally WL is defined for undirected and unlabeled graphs this is a common assumption in similar lines of work.
The unfolding tree with height of a node u V(G) is defined as the in-tree F = (v, [ | u E (n))) where Fü = (fv), 0). The unfolding trees FỤ" and F;" of two nodes v and w are isomorphic and only if the colors of the nodes in ileration i are equal, see, e.g., Kriege (2022). The Weisfeiler-Leeaan algorithm has historically been used as a heuristic for graph isomorphism. Let WL(G)- fcx (v) v E V(G) be the multisct of node colors in the stable coloring (Arvind et al., 2015). Two graphs G and H are not isomorphic if WL(G) * WL(H). However, non-isomorphic graphs G and H with WL(G)- = WL(H) exist. WL for example cannot distinguish the molecular graphs in Figure or a G-cycle from two triangles.
Expressivity. Let G denote the set of all graphs and Gn = {G e g [V(G) S n} for all n E N. Let d, &p be two graph embedding algorithms, which map graphs to embodding spaces (e.g., Rd). We say o is at least as eapressive as vb if for all pairs of graphs G, G' with v²G) A ((G') it holds that ((G) + @(G'). Let g' S G be family of graphs, for example, the set of all outerplanar graphs. We say that a graph embedding algorithm & is mazimally expressive for G' if for every non-isomorphic pair of graphs G, G' E g' it holds that (GG) + o(G"). We can generalize this to paramcterized graph embeddings such as GNNs: Let &w be graph embedding with parameters w (e.g., the weights of a neural network). A parameterized graph embedding &u is maximally expressive for G' if for all n E N there exists a parameter choice Wn. such that for every non-isomorphic pair of graphs G, G' E g' n nn,, it holds that ow., (G) + uw.. (G').
Hamiltonian adjacency lists. A Hamiltonian cycle of a graph is a cycle containing each node exactly once. A Hamiltonian cycle (u) on an undirected graph, can be separated into two directed Hamilto- nian cycles C' = (V1...., Ux) with corresponding edges vi 02.,,... 1x21 and C = (v.)...,,1) with corresponding edges bg.k-....., Ug. Biconnected outerplanar graphs have a unique Hamiltonian cycle that can be found in linear time (Mitchell, 1979). Hamiltonian adjacency lists (HATs) are derived by annotating each node with the sorted distances do to all its neighbors on the two directed variants of the Hamiltonian cycle C. Figure 2 shows graph annotated with its HALs in both directions of the Hamiltonian cycle. Following the Hamiltonian cycle in one direction and concalenating the HALs gives a HAL sequence S (and reverse sequence R, for the other direction).
A sequence of length n is a cyclic shift of another sequence S' of length n if there exists an é E N such that S, = for all i e [I....,n] n) where j = i + mod n. The HAL sequence uniquely identifies a biconnected outerplanar graph (if both directions and cyclic shifts are considcred):
Lemma 1 (Colbourn & Booth 1981). Two biconnected outerplanar gruphs G and H with HAL and reverse sequences SG, Sy and RG, Ry are isomorphic, iff So is a cyclic shift of Su or Ra-
4

---

Published in Transactions on Machine Learning Research (12/2024)
Table 1: Common benchmark datasets and per-
Table 2: Pre-processing time of CAT on the training splits of all datasets and relative addi- tional training/ evaluation time with CAT.
centage of outerplanar graphs in them.
Dataset
#Graphs
Outerplanar
ZINC
12000
98 %
Dataset
CAT Runtime
Eval.
PCQM-Contact
529431
98 %
Time Change
MOLESOL
1128
97 %
MOLESOL
2
%
MOLTOXCAST
8576
96 %
MOLBBBP
5 1
36 %
XOLTOX21
7831
96 %
MOLSIDER
6 1 s
21 %
MOLLIPO
4200
96 %
MOLBACE
6 1
42 %
XOLCLINTOX
1477
94 %
MOLLIPO
14+1 1
38 %
NCI-2000
250251
94 %
NOLTOX21
15 15+11
%
peptides-func
15535
93 %
MOLTOXCAST
16 16:11
13 %
KOLBACE
1513
93 %
ZINC
44 1
%
MOLSIDER
1427
92 %
MOLHIV
152
152
31 %
KOLBBBP
2039
92 %
MOLHIV
41127
92 %
4 Identifying Outerplanar Graphs Using Weisfeile--Leman
We develop graph transformation called cyclic adjacency transform (CAT), that enables WL to distinguish all outerplanar graphs. We first introduce CAT", enabling WL to distinguish any pair of non-isomorphic biconnected outerplanar graphs, and then extend it to all outerplanar graphs.
In CAT* (see Scction 4.1), nodes are duplicated to represent the Hamiltonian cycle in both directions. Wo annolate edges not. in the Hamiltonian cycle with the distance their endpoints have on the Hamiltonian cycle. This allows the Shiifeiler-Leman algorithm encode HAL sequences in the unfolding trees of the nodes and in turn distinguish pairs of non-isomorphic biconnected outerplanar graphs.
To exlend our transformation to all outerplanar graphs (see Section 4.2), need to ensure that the bicon- nected components keep their unique encoding. It should also be ensured that non-isomorphic graphs with the same biconnected components (but arrangod or rotated differently) can be distinguished. We address this by introducing articulation and block pooling vertices. These nodes contain all the information about their respective blocks and their position in these blocks. Together with nodes outside of blocks, this forms forest which encodes the entire original graph. As it is known that WL is maximally expressive on forests, it follows that WL is maximally expressive such graphs.
4.1 Identifying Biconnected Outerplanar Graphs Using Weisfeiler-Leman
We first present a graph transformation called CAT*, that allows the Weisfeiler- algorithm to distin- guish any two non-isomorphic biconnected outerplanar graphs. Figure 3 shows an example of CAT*. Note that CAT* consists of two disjoint copies of G, with directed and annotated edges. We first describe the transformation informally for ease of understanding, followed by the formal definition.
We start with an empty graph and add the (unique) Hamiltonian cycle of the original graph twice, directed in opposite ways (steps 1 and 2). Then, we add the remaining edges of the original graph to both cycles, directed in both directions each (step 3). Finally, we set node and edge features to the original features, and extend edge features with the distance their endpoints the Hamiltonian cycle (step 4).
Definition 1. The CAT (G) = G" transformation maps a biconnected outerplanar graph G = (V,E,,,)) to a new gruph G' = (V', E', p''p','u p', as follows:
1. Let (M1,..., vn) be the Homiltonian cycle of G and C and C be its directed versions.
Add node and edge disjoint copies of C and Ō together with the corresponding edges an empty graph G' and de E E' set (e) (1,v(e))-
5

---

Published in Transactions on Machine Learning Research (12/2024)
3
1
e
Figure 4: One part of the CAT transformation of the graph from Figure 3 and an example unfolding tree of one of its nodes from which the HAL sequence of the original graph can be reconstructed.
Let D E be the edges of not on the (undirected) Hamillonian cycle. Add edges in both directions to G' for the copies of C and C for each edge in D: E' = EEUEE with Ea = Unp o/ and E = -ol
for copies v/ of ve in C (resp. oo in C).
4. Vel, of E V' set (l(e)) = p'(x)) u(e.). Verey E Ea set v' v((ewu)) (do(y;, uz), v(vrz))) and Volutz E Eg set v' (((ee)))
(()jo))
Using CAT" we prove our first main result.
Theorem 1. Two biconnected outerplanar graphs G and H are isomorphic, if and only if (L(CATT = WT(CAT
Proof. Two graphs are distinguished by WL if and only the multisets of node colors of their stable colorings differ. Trivially, [VGG) # [V()) + (V (G)) + (H)) + WL(CAT (G)) # WL(CAT' (H)), only focus on graphs with [V(G)| = [VH)]. Two nodes only get the same color if their unfolding trees are isomorphic. The first number in the HAL of each node is always 1, so it can be ignored, and the last number is always [V(G)| -1, 1, so this can simply be reconstructed by (GCAT"(G)): The rest of the HAL sequence and the node labels of G can be reconstructed from the unfolding tree of any node in CAT (G): Trivially, each node has two direct neighbors in the Hamiltonian cycle. In the unfolding tree these are the parent and the single child with the 1-annotated edge. All other neighbors in the HAL can be reconstructed by looking the weights of the edges that do not have weight 1. Figure 4 shows an example. Looking at any two biconnected outerplanar graphs with nodes, the Weisfeller-Leman algorithm will be able to distinguish them after at most iterations, iff they non-isomorphic: Since the HAL sequence is encoded in the unfolding trees from all starting points (cyclic shift) and in both directions (reverse direction), this identifies isomorphism by Lemma 1.
4.2 Extending CAT* to All Outerplanar Graphs
While CAT* is defined for single blocks (biconnected outerplanar components), outerplanar graph contain multiple of them, as well as additional connections. We define the CAT transformation by applying CAT* to the blocks of the graphs and adding additional nodes and edges, which enable WL to distinguish any two non-isomorphic outerplanar graphs. We first give an informal description to provide an intuition for the various steps before stating the formal definition.
Starting from an empty graph, add the graph induced by all edges not in blocks and nodes in more than one block (steps 1 and 2). For each block, add the result of CAT" applied to the block (step 3.1). We refer to nodes created in this step Hamiltonian cycle nodes. Add pooling nodes connecting the two Hamiltonian cycle nodes corresponding to the same original node (step 3.2). Add node for each block (block nodes) and connect it to the pooling nodes of that block (step 3.3). Relabel the nodes from step 2, that belong to at least one block (articulation nodes) and connect them to the pooling nodes corresponding to the same original node (stop 3.6). Finally, create a global (block) pooling node and connect it to the block nodes (step 4). For each node we add, its initial features (if present) are extended by label referring to the type (Hamiltonian cycle node, pooling node, articulation node, etc.).

---

Published in Transactions on Machine Learning Research (12/2024)
G
CAT(G)
Figure 5: A graph and its CAT transformation. Original node labels are represented by letters, edge and node labels from the CAT transform are represented by colors. Note that CAT(G) looks like a cat.
Definition 2. The CAT(G) = G' transformation maps a graph G to new graph G' as follows:
Let Bi...., any block plus the nodes that are present in more than one block. Let [1 pa, x, D} be distinct node labels not in X.
B.....,,, Be be the blocks of G and let F be the graph induced by the edges of G that are not in
Add to G' with labels yl(v) = (L.)((u) for all v F.
3. For each block B, in G:
3.1. Let B Bi be the two connected components in CAT (B.). Add B₁ and Di to G¹.
3.2. For all pairs (v, T) of corresponding nodes in B3 and Bi add node Po with μ (pv) (K,)) and edges p.v, up Pv T Tp, to G'.
3.3. Add node ba to G' with (bbb))=] For all v E V(B)) add edges byp and pubi-
8.4. Let A; = ((B)) V(F) be the nodes of B; in F.
3.5. Let "/ A4 + (BB) map nodes of F to their copy in By.
3.6. For each E A., let pl(a) = (De, p(a)) and add edges Paaaa and ap)y(a) to G'.
4. Add node with p² (g) = A to G' and for all nodes b,, add edges gb, and big to G².
Let CAT(G) G².
An example of the CAT transformation can be seen in Figure 5. Appendix F contains additional visualizations of the transformation on real- life molecular graphs. Informally, a graph transformed using CAT by uniquely encoding all its blocks (using CAT*) and then connecting the results to encode also the position within the graph and the orientation using the original graph structure. All nodes and edges that are not part of a block are of course also added to the transformed graph.
We can now prove our main result, which implics that MPNNs together with CAT are maximally expressive on outerplanar graphs.
Theorem 2. Two outerplanor graphs G and are isomorphic, if and only if WL(CAT(G)) WL(CAT(H)).
Proof. Following Theorem 1, each block will be uniquely identified by WL. Since the additional nodes have distinct labels, they will not cause WL. to falsely report two blocks isomorphic when they not. The

---

Published in Transactions on Machine Learning Research (12/2024)
Table 3: Resistance and diameter before and after the CAT transformation. p(G) and (C) denote the average and maximum pair-wise effective resistance for graph G. Results are reported as mean and slandard deviation across all graphs in the datasets. In all cases, smaller is better.
Dataset
(G)
((CAT(G))
p(G)
((CAT(G)
maxp(()
maXx(CAT(C))
ZINC
12.5 + 2.6
9.9 1.6
4.0 0.7
2.6 0.4
10.0
1.79
MOLESOL
6.6 6.6 3.3
6.9
1.0
2.1
5.5
6.0 2.8
MOLTOXCAST
4.7
8.4
3.5
2.3
4.3
7.9
MOLTOX21
4.6
4.7
3.1
1.3
4.2
3.7
MOLLIPO
13.8
9.9
1.2
0.5
10.7
3.4
7.9 2.3
MOLBACE
1.21
11.5
1.3
2.7
12.5
9.1 2.6
MOLSIDER
11.8
7.3
4.1
2.2
10.4
8.9 6.8
MOLBBBP
3.77
9.1
3.4111
2.6
8.8
7.5 2.5
MOLHIV
11.9 5.2
9.9 3.8
3.7
2.7
4.7
8.2 + 3.8
information about the entire HAL sequence of each block is stored in the block nodes b. The pooling nodes p connect the block and block nodes to the rest of the graph (through the articulation nodes a), determining the orientation of the block. Note that the graph returned by CAT without the CAT* blocks and the global pooling node y a tree. Relying on the labels of the pooling and block nodes, we can reconstruct the original graph from this tree. As WL can distinguish non-isomorphic labeled trees (Arvind et al., 2015; Kiefer, 2020), it can thus distinguish non-isomorphic outerplanar graphs using CAT. For the other direction, note that CAT is permutation invariant: for two isomorphic graphs G and H, the graphs CAT(G) and CHT(H) are isomorphic and WL will give the same coloring for both.
Importantly, can compute CAT(G) in linear time. The computational complexity is dominated by the computation of the blocks (Tarjan, 1972) and their Hamiltonian cycles (Mitchell, 1979), which both require linear time. Note that we only add linear number of nodes and edges. From Morris et al. (2019) and Xu et al. (2019) it follows, that MPNNs, that are as expressive as 1-WL, can distinguish CAT(G) and CAT(H) for non-isomorphic outerplanar graphs G and H.
Note that our proof used an important property of the WL algorithm: Adding uniquely labeled nodes and edges to WL-distinguishable graphs never leads WL-indistinguuisaable graphs. We use this property add a global pooling node in step 4 of CAT which is connected to all block pooling nodes. This allows to pass messages between block nodes in fewer iterations in the subsequent MPNN step.
CAT can also be applied to non-outerplanar graphs. In this case, our graph transformation performs the steps described in Definition 2. However, if a non-outerplanar biconnected component B; is encountered, only one copy B is created in CAT(G)) and its vertices are connected to the corresponding pooling nodes. An example for this is depicted in Appendix D. While this never reduces expressivity, it is also not guaranteod to improve expressivity on non-outerplanar graphs. Note that it can be determined in linear time whether block is outerplanar while trying to compute the Hamiltonian cycle of the block (Mitchell, 1979). Hence, the CAT transformation always only requires linear time.
4.3 Influence of CAT on Graph Connectivity
As poor graph connectivity may nogatively influence the predictive performance of GNNs (Alon & Yahav, 2021), we investigate the effects of CAT on different measures of graph connectivity such as the diameter (G) of graph. We refer to the shortest path distance between two nodes the distance between them. Observation 1. For a block B of a graph G, it holds that ((CAT(B))
Proof. Let u (CCATBB). By definition all nodes in CAT are either from a Hamiltonian cycle created by CAT", a pooling node, or block node. If both nodes are from a Hamiltonian cycle, then there is a path u. Pu: b, Pe, v between them, where Pus Pv are pooling nodes and is the block node. Hence, dCAT(a)) (u, S If u is pooling block node, then the above path implies that dCAT(G) (u, < 4.
8

---

Published in Transactions on Machine Learning Research (12/2024)
Table 4: Predictive performance of MPNNS with and without CAT on different molecular benchmark datasets. Arrows indicate whether smaller (4) bigger (f) results better. Bold entries an MPNN with CAT that outperforms the samne MPNN without CAT.
Dataset +
ZINC
ZINC250k
MOLHIV
MOLBACE ROC-AUC f
MOLBBBP ROC-AUC t
Model
MAE 4
MAE
ROC-AUC
GIN
0.168 0.007
0.033 0.003
77.9 1.0
74.6
66.0 2.1
CAT+GIN
0.101 1 0.004
0.034 + 0.003
76.7 1.8
79.5 2.5
67.2 1: 1.8
GCN
0.184 1 0.013
0.067 0.005
76.7 1.4
77.9 1 1.7
2.4
CAT+GCN
0.123 + 0.008
0.034 + 0.003
1..1
79.2
68.3 + 1.7
GAT
0.375 + 0.013
0.103 0.004
76.6
81.7 11.7+22 2.3
66.2 1.4
CAT+GAT
0.201 + 0.022
0.046 0.004
75.3 1.6
79.3 + 1.6
66.0
Dalaset
MOLSIDER ROC-AUC f
MOLESOL
MOLTOXCAST ROC-AUC
MOLLIPO RMSE +
MOLTOX21
Model
RMSE
ROC-AUC f
GIN
56.6 + 1.0
1,15 0.077
65.3 0.6
0.717
75.8 + 0.7
CAT+GIN
58.2 0,9
0.985 0.055
0.5
0.798 + 0.031
74.8 1.0
GCN
56.7 + 1.5
1.053 - 0.087
0.4
0.748 0.018
7
CAT+GCN
57.9 + 1.8
1.006 0.036
6.8
0.771 + 0.023
71.9
GAT
58.4 1.0
1.037 0.063
0.8
0.728 + 0.024
7.6
CAT+GAT
58.3 = 1.3
1.09 = 0.048 6.85
0.754 +754+0.00
7.7
Observation 2. Let B; and Bj be two blocks of a graph G. In CAT(G), the marimum distance between any node in CA)(B:) and any node in CAT(B;) is 6.
Proof. Let E V(CAT(B.)) and V(CAT(B))). B; By, then Observation implies (u, v) < If B; F Bj. then there exists path u, Pu, bi, g. bj, bj, where Pa, are pooling nodes, b,. by are the block node for block Bi, Bj, and is the global block pooling node. Thus, (u, s 6.
Observations 1 and 2 show that for some subgraphs CAT provides constant upper bounds in diameter. On the graph level, CAT can only lead to small increase of the diameter.
Proposition 1. For an outerplanar graph G, ((CAT(G)) < ((G) +7.
Proof sketch. To prove the proposition we bound the distance between any pair nodes in CAT(G) by case analysis based on the type of nodes. We defer the full proof Appendix B.
In most practical cases, the short-cutting inside or between blocks leads to CAT reducing the graph diame- ter (see Observations and 2). In Table 3, we demonstrate this on molecular benchmark datasets. Besides the diameter, another useful graph connectivity measure is the effective resistance. The notion of effec- resistance originates electrical engincering (Kirchhoff, 1847) and has implications on several graph properties. For example, the effective resistance between two nodes proportional to the commute time between them (Chandra et al., 1989). Intuitively, large effective resistance between two nodes suggests that information propagation between the nodes is hindered. Recently, effective resistance has been in fact linked to over-squashing (Black et al., 2023) in GNNs, which is a negative effect that leads to long-range interactions having little impact on the predictions of a GNN. Effective resistance as introduced by Kirchhoff (1847) is naturally only defined for undirected graphs. As CAT produces directed graphs, we therefore use an extension of effective resistance introduced by Young al. (2015) that is applicable to directed graphs. We refer to Young al. (2015) for more details. In Table 3 we demonstrate that CAT reduces the pair-wise effective resistance molecular benchmark datasets.

---

Published in Transactions on Machine Learning Research (12/2024)
5 Experimental Evaluation
We investigate whether our proposed method CAT can improve the predictive performance of MPNNs molecular benchmark datasets.? We utilize three commonly used MPNNs: GIN (Xu el al., 2019), GCN (Kipf & Welling, 2017), and GAT-v2 (Veličković et al., 2018; Brody et al., 2022). We train on the commonly used ZINC (C6mez-Bombarde) et al., 2018; Starling & Irwin, 2015) and MOLHIV (Hu et al., 2020) datascts, which contain graphs representing molecules. We supplement these with 7 small datasets (see Table 4) from the OGB collection (Hu et al., 2020). In addition to the ZINC dataset with 12k graphs we also use the larger ZINC250K variant with 250k graphs. In total, we train three MPNNs on ten datasets with and without CAT, For each configuration, we separately tune hyperparameters the best hyperparameters ten times on the training set and evaluate it on the test set. The only exception to this is ZINC250k where we evaluate the final hyperparameter configuration five times, due to the large dataset size. For each dataset we report the mean and standard deviation of the most common evaluation metric on the test set in the epoch with the best validation performance. For ZINC we use a batch size of 128 and an initial learning rate of 10-3 that gets halved if the validation metric does not improve for 20 epochs. The training stops after 500 epochs or if the Icarning rate dips below 10-5, For all other datascts we train with a fixed learning rate for 100 epochs and a batch size of 128. We use the same hyperparameter grid for all models and provide more details in Appendix E. Besides measuring the predictive performance, we also mcasure the time needed for applying CAT (averaged over ten runs), and the training and evaluation time for GIN and GIN+CAT with the same hyperparameters on all datasets (averaged over five runs). Finally, we report the values for the diameters and effective resistances as described in Section 4.3.
the validation set and train a model with
Results. Table 2 shows the pre- pre-processing time of CAT. Note that this is the performance of running CAT on only a single CPU core. It is possible to achieve faster runtimes by simply paralleizzng different graphs over different cores. This negligible runtime allows applying the transformation even in realistic high-throughput screening applications (Krasoulis et al., 2022), for example, on MOLHIV takes only 5ms to process a graph. Training and prediction time on CAT transformed graphs increases by 29% on average. Table 4 shows the predietive performance of all models. Note that our bascline models obtain strong results, oflen surpassing the performance of (higher-order) GNNs reported in the literature, and that we train each MPNN and MPNN+CAT with exactly the same sets of hyperparameters. Overall, CAT improves the predictive performance of GIN and GCN in the majority of datasets (6 / 10 and 8 / 10, respectively). For GIN and GCN, performance increases reliably on all datasets, except MOLLIPO and MOLTOX21. Surprisingly, CAT does not work well with GAT and only improves its performance in 2 / 10 datasets. Most notably on ZINC, CAT achieves very strong results boosting the predictive performance of MPNNs between 33% (GCN) and 46% (GAT). This is only surpassed by higher-order GNNs such as CW Networks (Bodnar et al., 2021a) which obtain a MAE of 0.079 + 0.006 at the cost of potentially exponential pre-processing runtime due to enumerating cycles in the graph. Table 3 shows that CAT reduces both graph diamcter and maximum pair- wise resistance on most datasets. Furthermore, CAT reduces the average pair-wise resistance in all datasets. This suggests that CAT is effective at improving graph connectivity in real-life molecular graphs.
6 Conclusion
We proposed Cyclic Adjacency Transform (CAT), a linear time graph transformation, that enables the Weisfeiler-Leman algorithm to be maximally expressive outerplanar graphs. We rely on the fact that bicomnected outerplanar graphs can be uniquely identified by their Hamiltonian adjacency list sequences, which CAT encodes in unfolding trees. It follows that a combination of MPNNs and CAT can distinguish all outerplanar graphs. We achioved promising empirical results on standard molecular benchmark datasets where CAT improved the performance of GTN and GCN in most cases, while for GAT we could not observe this benefit. Computing CAT takes linear time and our implementation of CAT typically runs in the order of seconds. Motivated by the recent interest in the over-squashing phenomenon, we also studied the effect of CAT on graph connectivity. We proved that in the worst-case CAT increases the diameter of outerplanar graphs by a small additive constant. However, inspecting CAT on real- world data, we find that
1 'Qur code can be found http:://ggtthhhbcccc/aaatttaeeee htt.aa/........cctctttaattaaaaaa
10

---

Published in Transactions on Machine Learning Research (12/2024)
the diameter decreases most of the time. Similarly, we observed that the maximum and average pair-wise effective resistance, which is associated with over-squashing, typically decreases after applying CAT.
Our work highlights the value of GNNs designed for specific graph classes. This perspective aligns with a recent position paper, in which Morris et al. (2024) propose to investigate the runtime complexity of maximally expressive GNNs on practically relevant graphs (Challenge IT.4). In general, achieving high expressivity computationally expensive. However, for some graph classes this might not be the case. In this work, have demonstrated that for outerplanar graphs maximal expressivity can be achieved in linear time.
Focusing on specific graph classes allows making use of existing graph theoretical results. This could lead to novel GNNs that are both runlime efficient and highly expressive. Possible applications are infrastructure and road networks, which are characterized by near-planor graphs that tend to have low graph degeneracy (Eppstein & Gupta, 2017). More generally, scems promising to study sparse graphs, such as bounded expansion graphs (Nešetřil & De Mendez, 2012). Finally, in the future plan to exlend our work to k-outerplanar graphs, which are known to capture even more molecular graphs (Horváth et al., 2010).
Acknowledgement
This work was supported in part by the Vienna Science and Technology Fund (WWTF) through projects [10.47379/ (79399/V and (TT2225// by the TU Wien DK SecInt; and by the Austrian Science Fund (FWF) through project NanOX-ML (6728). MT acknowledges support from a DOC fellowship of the Austrian academy of sciences (ÖAW).
References
Uri Alon and Eran Yahav. On the bottleneck of graph neural networks and its practical implications. In ICLR, 2021.
Vikraman Arvind, Johannes Köbler, Gaurav Rattan, and Oleg Verbitsky. On the power of color refinement. In Fundamentals of Computation Theory, 2015.
Beatrice Bevilacqua, Fabrizio Frasca, Derek Lim, Balasubramaniam Srinivasan, Chen Cai, Gopinath Bala- murugan, Michael Bronstein, and Haggai Maron. Equivariant subgraph aggregation networks. In ICLR, 2021.
Lukas Biewald. Experiment tracking with weights and biases, 2020. URL www.w. com/. Soft- ware available from wandb.com.
Mitchell Black, Zhengchao Wan, Amir Nayyeri, and Yusu Wang. Understanding oversquashing in GNNs through the lens of effective resistance. In ICML, 2023.
Hans L. Bodlacnder. A partial k-arboretum of graphs with bounded treewidth. Theoretical Computer Science, 209(1-2):1 1-,,, 1998.
Cristian Bodnar, Fabrizio Frasca, Nina Otter, Yu Guang Wang, Pietro Liò, Guido Montúfar, and Michael Bronstein. Weisfeiler and Lehman go cellular: CW networks. In NewrIPS, 2021a.
Cristian Bodnar, Fabrizio Frasca, Yu Guang Wang, Nina Otter, Guido Montufar, Pietro Lio, and Michael Bronstein. Weisfeiler and Lehman go topological: Message passing simplicial networks. In TCML, 2021b.
Giorgos Bouritsas, Fabrizio Frasca, Stefanos Zafeiriou, and Michael M Bronstein. Improving graph neural network expressivity via subgraph isomorphism counting. Transactions on Pallern Analysis and Machine Intelligence, 45(1):657-668, 2022.
Shaked Brody, Uri Alon, and Eran Yahav. How attentive are graph attention networks? In ICLR, 2022.
Ashok K Chandra, Prabhakar Raghavan, Walter Ruzzo, and Roman Smolensky. The electrical resistance of graph captures its commute and cover times. In STOC, 1989.
11

---

Published in Transactions on Machine Learning Research (12/2024)
Charles J. Colbourn and Kellogg S. Booth. Linear time automorphism algorithms for trees, interval graphs, and planar graphs. STAM Journal on Compuling, 10(1):203-22) 225, 1981.
Leonardo Cotta, Christopher Morris, and Bruno Ribeiro. Reconstruction for powerful graph representations. NewrIPS, 2021.
Reinhard Diestel. Graph theory. Springer, 2024.
Radoslav Dimitrov, Zeyang Zhao, Ralph Abboud, and Ismail Ceylan. Plane: Representation learning over planar graphs. NeurIPS, 2023.
Andre Droschinsky, Nils Kriege, and Petra Mutzel. Finding largest common substructures of molecules quadratic time. In International Conference on Current Trends in Theory and Practice of Informatics, 2017.
David Eppstein and Siddharth Gupta. Crossing patterns in nonplanar road networks. In Proceedings of the 25th ACM SIGSPATIAL International Conference on Aduances in Geographic Information. Systems. 2017.
István Fáry. On straight line representation of planar graphs. Acla Sei. Moth. (Szegee)),, 11:229 233, 1948.
Stefan Felsner. Geometric graphs and arrangemenls: some choplers from combinatorial geomelry. Springer, 2012.
Matthias Fey and Jan E. Lenssen. Fast graph representation learning with PyTorch Geometric. ICLR Workshop on Representation Learning on Graphs and Manifolds, 2019.
Fabrizio Frasca, Beatrice Bevilacqua, Michael M. Bronstein, and Haggai Maron. Understanding and extend- ing subgraph GNNs by rethinking their symmetries. In NeurIPS, 2022.
Rafacl Nombazlombarreli, Jennifer N. Wei, David Duvenaud, José Miguel Hernández-Lobato, Benjamín Sánchez-Lengeling Dennis Sheberla, Jorge Iggirara-larrraguirre, Timothy D. Hirzel, Ryan P. Adams, and Alán Aspuru-Guzik Automatic chemical design using a data-driven continuous representation of molecules. ACS Central Science, 2018
Tamás Horváth and Jan Ramon. Efficient frequent connected subgraph mining in graphs of bounded tree- width. Theorelical Computer Science, :11331-33):2784 2797, 2010.
Tamás Horváth, Jan Ramon, and Stefan Wrobel. Frequent subgraph mining in outerplanar graphs. In KDD, 2006.
Tamás Horváth, Jan Ramon, and Stefan Wrobel. Frequent subgraph mining in outerplanar graphs. Data Mining and Knowledge Discovery, 2133):472-508, 2010.
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open Graph Benchmark: Datasets for machine learning graphs. In NewrIPS, 2020.
Neil Immerman and Eric Lander. Describing graphs: A first-order approach to graph cononization. Yale University Press, 1990.
Sandra Kiefer. Power and limits of the Weisfeiler-Leman algorilhm. PhD thesis, RWTH Aachen University, 2020.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. ICLR, 2017.
Gustav Kirchhoff. Ueber die Auflösung der Gleichungen, auf welche man bei der Untersuchung der linearen Vertheilung galvanischer Ströme geführt wird. Annalen der Physik, 148(12):497 508, 1847.
12

---

Published in Transactions on Machine Learning Research (12/2024)
Agamemnon Krasoulis, Nick Antonopoulos, Vassilis Pitsikalis, and Stavros Theodorakis. Denvis: Scalable and high-throughput. virtual screening using graph neural networks with atomic and surface protein pocket features. Journal of Chemical Information and Modeling, 62(19):4642 4659, 2022.
Nils M Kriege. Weisfeiler and Leman go walking: Random walk kernels revisited. In NewrIPS, 2022.
Haggai Maron, Heli Ben-Hamu, Hadar Serviansky, and Yaron Lipman. Provably powerful graph networks. NewrIPS, 2019.
Sandra I.. Mitchell. Linear algorithms to recognize outerplanar and maximal outerplanar graphs. Information Processing Letters, 9(5):229 232, 1979.
Christopher Morris, Martin Ritzert, Matthias Fey, William Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe. Weisfeiler and Leman go neural: Higher-order graph neural networks. In AAAI, 2019.
Christopher Morris, Fabrizio Frasca, Nadav Dym, Haggai Maron, Ismail Ilkan Ceylan, Ron Levie, Derek Lim, Michael M Bronstein, Martin Grohe, and Stefanie Jegelka. Position: Future directions in the theory of graph machine learning. In ICML, 2024.
Jaroslav Nešetril and Patrice Ossona De Mendez. Sparsily: graphs, structures, and algorithmss, volume 28.
Springer Science Business Media, 2012.
Leander Schietgat, Jan Ramon, and Maurice Bruynooghe. A polynomial-time maximum common subgraph algorithm for outerplanar graphs and its application to chemoinformatics. Annals of Mathematics and Artificial Intelligence, 69(4):343 376, 2013.
Teague Sterling and John J. Irwin. Zinc 15 - ligand discovery for everyone. Journal of Chemical Information and Modeling, 2015.
Maciej M. Systo. The subgraph isomorphism problem for outerplanar graphs. Theorelical Computer Science, 17(1):91-99) 97, 1982.
Robert Endre Tarjan. Depth-first search and linear graph algorithms. SIAM Journal of Computing, 1(2): 146-160, 1972.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph Attention Networks. In ICLR, 2018.
Zhenqin Wu, Bharath Ramsundar, Evan N. Feinberg, Joseph Gomes, Caleb Geniesse, Ancesh S. Pappu, Karl Leswing, and Vijay Pande. Moleculenet: benchmark for molecular machine learning. 2018.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanic Jogelka. How powerful are graph neural networks? ICLR, 2019.
George Forrest Young, Luca Scardovi, and Naomi Ehrich Leonard. A new notion of effective resistance for directed part I: Definition and properties. Transactions on Automatic Control, (7)):17777-1736 2015.
Bohang Zhang, Guhao Feng, Yiheng Du, Di He, and Liwei Wang. A complete expressiveness hierarchy for subgraph GNNs via subgraph Weisfeiler-Lehmaat tests. In ICML, 2023a.
Bohang Zhang, Shengjie Luo, Liwei Wang, and Di He. Rethinking the expressive power of GNNs via graph biconnectivity. In ICLR, 2023b.
13

---

Published in Transactions on Machine Learning Research (12/2024)
A Outerplanar Graphs
Let G = =(V be an undirected graph. planar emabeddiig of G consists of an injective mapping ʃ of nodes V to vectors the plane IR2 and for each pair of adjacent nodes u, v a continuous path between f(()) and f(v) such that no pair of such paths cross. More formally, a continuous path from f(u) to f(v) is a continuous function p. [0, 1] - R² such that p(0) = fu) and p(1) f(v). Two such continuous paths p.p' cross if there exist 1' E (0, 1) such that p(t) p'').. The graph G is planar if it has a planar embedding. By Fáry's theorem each planar graph always has a planar embedding with straight line segments as paths (Fáry, 1948). Intuitively a planar embedding dissects the plane into regions called faces. Formally these are the (topologically) connected regions of R² with all the edge paths p removed. Any planar embedding has a unique face not bounded by paths (the only non-compact face), which called the outer face. A graph is outerplanar if it has planar embedding with all nodes lying on the boundary of the outer face. See, for example, Felsner (2012) for more details.
We can also characterize outerplanar graphs using forbidden graph minors. A graph H is minor of G, if H can be obtained from G by a series of node deletion, edge deletion, and edge contractions (i.e., removing an edge and replacing the two endpoints by a new node). Tet Ka,b be the complete bipartite graph with bi-partition AUA B = V with a = |A| and b = [B] and Ke be the complete graph on с nodes. A graph G is outerplanar if and only if G has no K2,3 minor and no K₃ minor. Similarly, planar graphs can be characterized by the Kuratowski theorem as graphs with no K3,3 and no Kş minor. For more details see, for example Diestel (2024).
B Proof of Proposition 1
We prove Proposition 1 which states that ((CAT(G)) < (G) 7 for every outerplanar graph G.
Proof. Let u E V(CAT(G)) such that dCAT(O)) (u, v) = (CAT(GG)) We call a node a free node if it was not part of a block in G and was not created by CAT. A node that is not a tree node is either a Hamiltonian cycle node, a pooling node, a block pooling node, or a global block pooling node.
Case 1: Both u, y are not tree nodes. By Observation 2: dCNT(a)(u, v) < 6.
Case 2: Node u is a tree node and e is not. Let a E V(G) be the closest articulation node to in CAT(G). Then, there is a path of length do (u, a) in CAT(G) from u to We can extend this path by one node to reach a pooling node. By Definition 2, there exists path of length at most 6 from this pooling node to v. Thus dCAT(G) v) I da(u, a) + 7 7 (G) 7
Case 3: Both u, e are tree nodes.
Case 3a: Suppose that the shortest path between and v in G does not contain any edge inside of an outerplanar block, then dC (u, dc(u, v) s (G)).
Case 3b: Suppose that the shortest path between u and v in G contains one more edges inside exactly one block. Then, we can enter and exit this block in CAT(G) through a path a1,Pi, b, p2, a2, where a1 are articulation nodes, Pt, P2 are pooling nodes, and 5 is a block node. Note that the articulation nodes were part of the path in G which implies dCAT(O) (u, v) = da(u, a1) + da(a2, v) + = da(u, v) - de(a1, 02) + 4. Furthermore, we do not need take the one or more edges inside the block to go from an to 02- Using a2) 2 1 we obtain dexr(a) (u, v) do(u, v) da(ar, a2) + do(u, v) + < (GG) +3.
Case 3c: Suppose that the shortest path between u and v in G contains two more edges that are contained in two or more different blocks. Then, for CAT(G) we can shorteut from the first to the last block node of the shortest path bet u and v through a path ai, ai,Pi, bi, b2, P2, 02, where ai, are articulation nodes, P1, P2 are pooling nodes, b, by are block nodes, and g is the global block pooling node. Note that the articulation nodes were part of the path in G which implics that dCAT(a)(u, v) =
+ da(az))) v) + + do(u, v) do(a1, az) + 6. By assumption, we know that do 02) 2 which implics doAT(G) (u, v) do(u,v) v) do (a1, + 6 E do(u, v) + 4 < (G) +4.
14

---

Published in Transactions on Machine Learning Research (12/2024)
3
34
54
6
2
0
Figure 6: Additional examples for CAT The biconnected outerplanar graphs on the left are transformed
using Definition
Figure 7: Two nomplanar graphs which PlanE cannot distinguish. However, CAT can distinguish the graphs by their two central outerplanar biconnected components.
C Additional Examples for CAT*
Here, we provide additional examples for CAT*. Figure shows two graphs and the results, when transformed using CAT As described in Definition 1, the original graph is copied twice and the edges of the Hamiltonian cycle are directed in each direction once (with their label extended with 1). The remaining edges added to each copy directed in both directions, with their label being extended to describe the distance of their two nodes when only using edges from the Hamiltonian cycle.
D Incomparable Expressivity of CAT and PlanE
The expressivity of CAT and PlanE is incomparable. This follows from Propositions 2 and showing that there are pairs of graphs that are distinguishable by CAT and not PlanE and vice versa. Proposition 2. There exists non-planor graphs that CAT can dislinguish and PlanE cannol distinguish.
Proof. The claim follows from Figure! 7.
15

---

Published in Transactions on Machine Learning Research (12/2024)
Figure 8: Two planar (but not outerplanar) graphs which CAT cannot distinguish.
Proposition 3. There exisls planar graphs that PlanE distinguish and CAT connol distinguish.
Proof. The claim follows from Figure 8.
E Details for Experimental Evaluation
Our models are implemented in PyTorch-Geone Geometric (Fey & Lenssen, 2019) and trained on a single NVIDIA GeForce RTX 3080 GPU. We use WandB (Biewald, 2020) for tracking. The used server has 64 GB of RAM and an 11th Gen Intel(R) Core(TM) 19-11900KF CPU running at 3.50GHz. Table shows the hyperparameters of our MPNNs for different datasets. We use the same hyperparameter grid for MPNNs combined with CAT. We used smaller hyperparameter grid for MOLHIV as MOLHIV is larger than the most of the other datascts, mcaning that training takes much longer. When benchmarking the speed of GIN against CIN+CAT we train for 100 epochs with batch size of 128 all datasets with the same hyperparameters for both models (see Table 5).
CAT implementation. CAT adds an additional feature to each node which encodes the type of that node, i.., nodes from Hamiltonian cycles, block nodes, pooling nodes, articulation nodes and or global block nodes. Furthermore, we create additional edge features encoding the types of nodes incident to this edge i.e, an edge between two different nodes a Hamillonian cycle has different type than an edge from a pooling node the block node. For newly created nodes and edges we set their remaining features to the feature of the node edge they are based on; for example, a pooling node will have the features of the node they are performing the pooling operation for. For nodes that have natural representation in the graph (block and block pooling nodes) we set these features to O. To ensure that only these nodes get assigned 0 features, we shift the values of these features for all other nodes by 1.2 Note that our MPNNs treat the distance on edges in blocks as a categorical feature. Representing the distances as numerical features did not improve performance preliminary experiments.
Table Hyperparameter grids for GIN, GCN and GAT on different datasets.
Speed Benchmarks
All datasets except MOLHIV
Parameter
MOLHIV
(Table 2)
Message passing layers
2, 3, 4, 2
4, 5
4
Final MT.P layers
2
2
Pooling operation Embedding dimension
mean, sum
mean, sum mean
64, 128, 256
64,128
64
Jumping knowledge
last 0, 0.5
concat 0.5 0
concat
Dropout rate
Dataset description. All graphs our datasets represent molecules and have graph-level tasks. For all tasks we use the metries that are commonly used by the community, egg., MAE for ZINC or ROC-AUC
2This assumes that the features categorical and not numerical-which the the used datasets.
16

---

Published in Transactions on Machine Learning Research (12/2024)
for MOLHIV. For ZINC (10k graphs) and ZINC250K (250k graphs) Kr6mez-Bombarelli et al., 2018; Sterling & Trwin, 2015) the task is to predict the constrained solubility which is a regression task. All other datasets are from the Open Graph Benchmark (Hu et al., 2020) based on MoleculeNet (Wu et al., 2018) and the task is always to predict some molecular property. On MOLHIV, the task to prodict whether a molecule inhibits HTV virus replication or not (Hu al., 2020). For the tasks of the other datasets, we refer to Wu et al. (2018).
F Additional Figures
We provide additional visualizations of the CAT transformation. In all figures, the color of the vertices in the transformed graph have the following meaning: red nodes are from Hamiltonian cycles, blue nodes correspond to blocks, yellow nodes pool the nodes from Hamiltonian cycles, orange nodes correspond to articulation nodes and the gray node pools block nodes. Figure 9 shows synthetic example with non- outerplanar graph. Figure 10 demonstrates CAT on various synthetic graphs. Figure 11 shows the result of CAT on molecular graphs from ZINC and MOLHIV. Somewhat ironically, CAT often generates frog graphs on MOLHIV as can be seen Figure 12.
Figure 9: Left: example non-outerplanar graph. Right: result of applying CAT to the graph. Colors indicate the type of node (see Appendix F).
17

---

Published in Transactions on Machine Learning Research (12/2024)
Figure 10: Left: example graphs. Right: result of applying CAT to these graphs. Colors indicate the type of node (see Appendix F).
18

---

Published in Transactions on Machine Learning Research (12/2024)
20
Figure 11: Left: example graphs from MOLHIV (top) and ZINC (bottom). Right: result of applying CAT to these graphs. Colors indicate the type of node (see Appendix F).
19

---

Published in Transactions on Machine Learning Research (12/2024)
17
Figure 12: Left: example graphs from MOLHIV. Right: result of applying CAT to the graph. Colors indicate the type of node (sce Appendix F).
20


Reviews:
[{"review_id": "NixU4aIxbo", "reviewer": "Reviewer_D1E5", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n\n- The paper is well-motivated to transform the graph structure into a more expressive manner.\n- The theoretical analysis proves that graph transformation by CAT improves the expressive of MPNN. \n- The experiments are comprehensive on multiple datasets and GNNs\n\nWeakness:\n\n- The proposed method scales up the graph and costs more in computation for downstream GNNs as shown in Table 2. Assuming we have a large enough dataset, the extra computation can be in turn used for more GNN layers or more model parameters which can also lead to better performance. It would be great to compare the computation cost with CAT and under different model sizes.\n-  It would be better to introduce the dataset and tasks used in the paper/appendix for background knowledge.\n- Need more analysis on the dataset and form of GNN where CAT failed to improve the performance", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper proposes a graph transformation algorithm to improve MPNNs maximal expressiveness on outerplanar graphs. The algorithm enables WL to distinguish all non-isomorphic outerplanar graphs, which can be completed in linear time. Experiments and theory show that the algorithm does not essentially harm the graph connectivity. Also, the newly constructed graph has better performances in multiple GNNs on multiple tasks and datasets.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "See weakness", "broader_impact_concerns": "No broader impact concerns", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "wefttFuRMF", "reviewer": "Reviewer_eiRW", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n1. The motivation of the paper is well-written, and the intuition behind the proposed algorithm is well-described. \n\n2. The discussion of the algorithm and corresponding theoretical insights are clear and convincing. \n\nWeakness:\n\n1. The theoretical analysis is incomplete, as it lacks connections to graph neural networks and does not include any optimization or generalization analysis.\n\n2. The experimental setup is unclear. The implementation of CAT in graph neural networks is not clearly described, and the algorithm only improves the performance in part of the graph neural networks. \n\n3. There is no numerical experiments to quantitatively verify the theoretical insights.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper proposes a graph transformation called CAT, which enhances the expressiveness of the WL algorithm on outerplanar graphs. This transformation can potentially be utilized in certain types of graph neural networks to improve their performance. The improved performance is verified using standard molecular benchmark datasets.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "See weakness. Additionally, I have several questions that need the authors' clarification.\n\n1. Could the authors verify some fast GNN algorithms, such as FastGCN, which utilize a pruned graph architecture?\n\n2. What is the reasoning behind the lack of significant improvement when applying CAT to GAT?\n\n3. How does the graph structure affect the performance of CAT? Could the authors provide insights into how certain characteristics of the graph-structured data might help determine whether CAT should be implemented?", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "olpKI2vXVG", "reviewer": "Reviewer_qtTB", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n- The mathematical component of this paper, where the authors introduce a new transformation algorithm for mapping outer planar graphs, appears to be interesting. Plus the empirical evidences are supportive of the utility of this transformation.\n\n- The paper is easy to read for the most part. However, the targeted audience is not clear and the paper would require a major revision at its current form in my opinion.\n\nWeaknesses:\n\n- The empirical evaluations are relatively weak. The baseline models are from five years ago, which are a bit outdated at this point. The coverage of different datasets/applications is not clearly stated, making the implications a bit narrow at this point.\n\n- The connection between the theoretical component (expressivity) and the empirical results is completely missing at this point. This is a major omission in my opinion and needs to be addressed (before the paper can be accepted); I'm thus marking no for claims and evidences partly due to this reason.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper introduces a transformation algorithm on graphs, called the cyclic adjacency transform. Using this transformation algorithm, this paper shows that the transformed graphs can be used along with the Weisfeiler-Leman GI test to differentiate between two isomorphic graphs.\n- A graph is called outerplanar if it can be drawn in the plane without edge crossings and with all nodes belonging to the exterior face.\n\nThis cyclic adjacency transform is first applied to biconnected outerplanar graphs, then designed for all outerplanar graphs:\n- A graph is called biconnected if removing any node of the graph will not cause the graph to be disconnected.\n- For a biconnected outerplanar graph, the transform first obtains the directed Hamiltonian cycle of the graph and the reverse of the graph.\n- In the newly transformed graph, it adds two disjoint copies of both Hamiltonian cycles.\n- Then, it joins two edges belonging to the same edge in the original graph from both directions of the Hamiltonian.\n- Finally, it sets the edge/node embeddings from the original graph.\n- For general outerplanar graphs, the transform separates the graph into multiple blocks; then, it applies a transform similar to the above to each block. Finally, it concatenates all the transformed blocks together into the final output.\n\nThe main result shows that with this transform, the two outerplanar graphs are isomorphic if and only if their WL colorings are the same.\n\nThe paper ends with some empirical evaluations to show that this transform can improve the predictive performance of several GNNs, including GIN, GCN, and GAT.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Below please find a list of editorial changes that can enhance the readability of the manuscript:\n\n- I'm not quite sure what exactly is the problem statement/scope of this paper: My current understanding based on the main theoretical result + empirical evaluation is that this paper is designing transformation procedures that can be used to enhance the predictive performance of GNNs. Please correct me if I am wrong. If so, I think that a major missing component is why does the CAT procedure lead to empirical performance improvements; This has to be substantiated by concrete results, either from a theoretical or an empirical perspective. In either case, the paper can be improved by clearly stating the scope/goal.\n\n- Related work: Please clearly describe the technical innovation of the main theoretical result, and what is new from a technical standpoint.\n\n- Experimental evaluation: This contribution of this part is relatively weak to justify an acceptance in my honest opinion.\n    - The datasets + GNN architectures are a bit restrictive, in my opinion. There are many ways to improve the performance of GNNs in practice. I'm not convinced that running the proposed transformation would be the most effective way for practitioners.\n    - There are no ablation analysis or robustness checks done here to ensure that results would generalize to different types of empirical applications.\n\n- Page 3: Please include the mathematical definition of a graph being outerplanar.\n\n- Lemma 1: Please include a proof of this result in the appendix. Similarly, the citation to Mitchell (1979) might appear unfamiliar to most TMLR audience (as well as various other citations to the graph-theoretic literature; please check).\n\n- Page 5: Please include some examples for the transformation in Definition 1 to help readers digest this concept.\n\n- Page 6: Likewise, please add more explanations to Definition 2. My concern is that this would be difficult to understand for many of the TMLR audiences.\n\n- Minor: What do you mean by \"maximally expressive\"? I would like to know what the mathematical definition of this is and I think it would be helpful if this is defined somewhere in the preliminaries.", "broader_impact_concerns": "The focus of this manuscript is on the expressivity of GNNs for outerplanar graphs. There are no immediate implications to ethical aspects from this work (either positive or negative).", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: See the answer to "Claims and Evidence."
Decision: Accept (poster)