Expressivity-Preserving GNN Simulation
Authors: Fabian Jogl
Maximilian Thiessen
Thomas Gärtner
Venue: NeurIPS 2023 poster (2023)
Keywords: Graph Neural Networks
GNNs
Graphs
Message Passing
Expressiveness
Graph Transformations
Message Passing Graph Neural Networks
TL;DR: We systematically investigate graph transformations that enable standard message passing to simulate state-of-the-art graph neural networks without loss of expressiveness.

Abstract: We systematically investigate graph transformations that enable standard message passing to simulate state-of-the-art graph neural networks (GNNs) without loss of expressivity. Using these, many state-of-the-art GNNs can be implemented with message passing operations from standard libraries, eliminating many sources of implementation issues and allowing for better code optimization. We distinguish between weak and strong simulation: weak simulation achieves the same expressivity only after several message passing steps while strong simulation achieves this after every message passing step. Our contribution leads to a direct way to translate common operations of non-standard GNNs to graph transformations that allow for strong or weak simulation. Our empirical evaluation shows competitive predictive performance of message passing on transformed graphs for various molecular benchmark datasets, in several cases surpassing the original GNNs.

Expresivity-Preserving GNN Simulation
Fabian Jogl
Machine Learning Research Unit
Center for Artificial Intelligence and Machine Learning TU Wien, Vienna, Austria fabian. jogl@ ac.at
Maximilian Thiessen
Thomas Gärtner
Machine Learning Research Unit TU Wien, Vienna, Austria
Machine Learning Research Unit
TU Wien, Vienna, Austria thomas ganiasgggartnerrtuiienn wcw.enaaccccc.o..mmmm at
maximilian thisssenStuwien ac at
Abstract
We systematically investigate graph transformations that enable standard message passing to simulate state-of-the-an art graph neural networks (GNNs) without loss of expressivity. Using these, many state-of-the-art GNNs can be implemented with message passing operations from standard libraries, eliminating many sources of implementation issues and allowing for better code optimization. We distinguish between weak and strong simulation: weak simulation achieves the same expressiv- ity only after several message passing steps while strong simulation achieves this after every message passing step. Our contribution leads to direct way to translate common operations of non-standard GNNs to graph transformations that allow for strong or weak simulation. Our empirical evaluation shows competitive predictive performance of message passing on transformed graphs for various molecular benchmark datasets, in several cases surpassing the original GNNs.
1 Introduction
We systematically investigate which variants of non-standard message passing graph neural networks can be implemented with standard message passing graph neural networks (MPNNs) on transformed graph without losing expressivity. While MPNNs are a very popular type of graph neural networks (GNNs), they are not able represent every function on the space of graphs [Xu et al., 2019, Morris et al., 2019] due to their limited expressivity: for all MPNNs, there are pairs of non-isomorphic graphs which always have the same embedding. common approach to create more expressive GNNs is to change the message passing function of MPNNs. If GNN is more expressive than MPNNs by adapting the message passing function, we call this non non-standann standard message passing. Examples of this are message passing variants that operate et al., 2021] or tuples nodes [Morris et al., 2019, 2020, 2022]. known that some variants of non-standard message passing be implemented with MPNNs transformed graph without losing expressivity as demonstrated by Morris et al. [2019, 2020, 2022] and Qian et al. [2022]. We formalize this transformation such that combining an MPNN with that graph transformation is at least as expressive the GNN. As simulation only requires graph transformations pre-proces meeprocessing, it allows the use of off-the-shelf MPNN implementations which simplifies and speeds up the implementation of GNNs. Another advantage is that simulation is programming framework agnostic: only the graphs needs to be cunsforrned-iddeeenddde
subgraphs [Frasca et al., 2022, Bevilacqua
MPNN simulating GNN: GNN can be simulated if there exists graph
of how the MPNN is implemented. Finally, simulation allows easily exchange GNNs in existing workflows without requiring changes to the model. Despite
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

the benefits of simulation, this approach has not been thoroughly investigated: there is currently no formal definition of simulation and it is not known which GNNs can be simulated. In this paper, we define simulation and provide sufficient criteria for non-standard message passing to be simulated.
Related Work. Xu al. [2019] and Morris et al. [2019] proved that MPNNs have limited expressivity. This lead to the development of new GNNs that have higher expressivity than MPNNs. Such GNNs often operate on structures that differ from graphs, for example (1) Morris et al. [2019, 2020, 2022] proposed GNNs operating on k-tuples of nodes, (2) Bodnar et al. [2021a.b] proposed GNNs on topological structures, and (3) Bevilacqua et al. [2021] proposed GNNs operating on subgraphs. The idea of implementing non-standard message passing by standard message passing dates back to at least Otto [1997] who showed that instead of performing the higher-order message passing of k-WL it is possible to use 1-WL (classical message passing) on transformed structure [Grohe et al., 2021]. To the best of our knowledge, the first GNN that has been implemented through a graph transformation is k-GNN [Morris et al., 2019], which is a generalization from k- 5-WL. to GNNs. Already Morris et al. [2019] refer to this concept as simulation. In follow up work, Morris al. [2020] and Morris et al. [2022] implemented similar GNNs with non-standard message passing as MPNNs together with graph transformations. Similarly, k-OSWL [Qian et al., 2022] was designed to utilize WL. However, none of these papers have formalized the idea of simulation for GNNs (or WL) explicitly. To this end, we [Jogl et al., 2022a,b] showed that CW Networks [Bodnar et al., 2021a], DS [Bevilacqua et al., 202 1], DSS [Bevilacqua et al., 202 1]. and can be implemented as an MPNN on a transformed graph. A similar high-level idea was proposed in positional paper by Veličković [2022]. In parallel, Hajij et al. [2023] introduced combinatorial complexes that generalize structures such as graphs or cell complexes and showed that computations on these complexes can be realized as message passing on graphs. While simulation has been used and advocated in the past there is no unified solution to obtaining graph transformations, theoretical justification, or thorough empirical evaluation. We fill this gap and find many GNNs can be simulated by MPNNs on transformed graphs. More details can be found in Appendix A and Appendix B.
[Morris et al., 2020]
Our Approach. We introduce simulation of non-standard message passing, which formalizes the idea of implementing a GNN, which uses non-standard message passing. through an MPNN on a transformed graph. A message passing algorithm can be strongly simulated if an MPNN together with a graph transformation can achieve the same expressivity in every iteration of message passing. To prove that many GNNs can be strongly simulated, define the class of augmented message passing (AMP) algorithms which contains many common GNNs. We prove that all AMP algorithms can be strongly simulated and present meta algorithm generate the necessary graph transformations. This allows us to show that eleven recently proposed GNNs can be strongly simulated. Specifically, the GNNs by Morris al. [2019, 2020, 2022] and Qian al. [2022] perform AMP. This gives an additional mathematical justification to their approach by proving that their GNNs can be implemented with MPNNs without losing expressivity over an implementation with non- non-standard message passing.
Furthermore, we investigate three constructions that demonstrate the limits of strong simulation: time dependent neighborhoods, nested aggregations, and non- non-pairwise message passing. We prove that these constructions either cannot be strongly simulated efficiently or cannot be strongly simulated at all. However, if we are only interested in the MPNN achieving the same expressivity as the GNN with ntn-standard message passing after a sufficient number of layers, it is possible to implement all three constructions with an MPNN We call this weak simulation: a message passing algorithm can be weakly simulated if there exists a non-negative integer ( such that an MPNN together with graph transformation can achieve the same expressivity as the message passing algorithm in one iteration after every { iterations of message passing. We show that Message Passing Simplicial Networks [Bodnar et al., 2021b] CW Networks [Bodnar et al., 2021a]. DSS [Bevilacqua et al., 2021]. and K K-hop message passing [Feng et al., 2022] can be weakly simulated. Finally, we evaluate a representative set of graph transformation empirically. Our graph transformations lead competitive performance compared to the simulated algorithms and often lead to more accurate predictions.
Main Contributions. We introduce the concept of strong and weak simulation (Section 3) of message passing. This generalizes existing ideas behind the implementation of several GNNs [Morris et al., 2019, 2020, 2022, Qian et al., 2022]. We provide an automated way of proving that GNN can be simulated and deriving the necessary graph transformations. We prove that there exist architectures that cannot be strongly simulated (Section 4) but only weakly simulated (Section 5). Our empirical evaluation (Section 6) demonstrates that simulation achieves competitive performance.
2

---

2 Background
A graph G is triple G E. consisting of set of vertices V, set of directed edges E - [(r, y) z.y VV # y), and a function F that assigns a feature to every vertex and edge. For set of objects U and integer > 0, we denote by 2 (X X C U the powerset of U, i.e., the set of all subsets of U, and by U = {(u,,.... 24) ........ u4 U' the set of all tuples of length built from U. In this paper we work on generalization of graphs we call relational structures that use a generalized notion of neighhorhood. For a set of objects U, we call any function N: U - 2(0"), neighborhood function. A neighborhood function assigns to every object a set of tuples of length i which we call its neighbors. We use ((NV to denote the length of these tuples. We call any tuple (w, u) a directed edge where u E U and w E (u)) (the in-neighbours) with {(N) = 1. For an integer k > O, we use [k] to denote the set (1,..., k. and {{-} to denote a multiset.
Definition 2.1. (Relational Structure) Let k 2 be an integer, U be a set of objects, and let .,,....,V, .o be neighborhood functions over U. Furthermore, let F be function such that F(u) assigns a feature every u E U and ('((2, u)) assigns a feature to every directed edge with E [ and x E (u) with ((V.) = 1. Then, the tuple X (U,NI.....M) F)) is relational structure.
it clear from context from which neigh- borhood N₁ an edge (2r, u) is, we will sim- ply write its features as F((x, u)) instead of F*((,, u)). If the number of neighbor- hoods is important we call such a structure a k-relational structure. Note, that a graph G = (V, F' is a special case of 1- relational structure with only one neighbor- hood (v)
{w (w, v) E Egg. i.c., G = -V.NG, F). For graphs G, H we refer to their vertices, edges, and features by adding the graph as a subscript. We say that G, H are isomorphic if there ex- ists an edge and feature preserving bijec- tive function a : Ve - VH between their vertices: for every vertex E VG it holds that FF(v) = (a(())) and for every y, E Ve. it holds that (x, E EG if and only if (a(x), a(y)) E En with Fa y)) FH polynomial time algorithm is known which decides whether two graphs are isomorphic [Babai, 2016]. However, heuristics such as those based on colorings and color update functions allow us to distinguish many pairs of non-isomorphic graphs. Furthermore, they allow us to model the ability of GNNs distinguish graphs [Xu et al., 2019, Morris et al., 2019]. For a relational structure over a set of objects U, a coloring is a function e U - where X known set of colors. Suppose we have two disjoint sets U and U' with two colorings e over U and c' over U". Then, we define the joint coloring cU d' for every x E (U U U') as c(x) if I E U and c' c'xx) otherwise. For two colorings and d defined over the same set of objects U, we say that e refines d if for every pair of objects u, E U it holds that Cu G. + du = d,. Let U, U' be sets of objects with U S U. Let e be a coloring of U and d a coloring of U". Then, e refines if for every pair of objects u, E U' it holds that C. = C.- = du = dr.
Figure 1: Left: graph. Center: regular cell complex built from the graph through a graph-to-structure en- coding [Bodnar et al., 2021a]. Vertices correspond to O-dimensional cells, edges to 1-dimensional cells yellow) ) and induced cycles to 2-dimensional cells
blue Right: a graph created by structure-to-graph encoding the regular cell complex to a graph. Vertices corresponds cells as indicated by color.
No
Definition 2.2. (Color Update Function) Let k > 1 be an integer and X' set of k-relational structures. A color update function takes any X- = (U,N)...., and outputs a new color p(u, X,c) of u. We denote the new coloring of the whole set U as c)..)).
F') E X, a coloring of U, and a u E U
We assume color update functions & to be computable and denote the time to compute ó with respect to an input U as ((U)). Color update functions are used to iteratively update initial coloring d such that c'+ = o o(X,c") ct) for every 2 O. We denote applications of o to compute c' as of (X.c²) c)). We also say that 6 c = cO The initial coloring is often given by the features e = Flu. meaning the color e" is given by the domain restriction of F to the set of objects U. Then, the color of each object u E U is e = Fu. If we are not given features, then we use constant coloring, i.e., a coloring that assigns the same (arbitrary) color to each object. Color update functions can sometimes
3

---

be used to determine whether two graphs are isomorphic. For this, coloring is computed for both graphs. If at some iteration the colorings of the two graphs are different this implies that the graphs are not isomorphic. If the colorings are never different, then the result of this method is inconclusive. common color update function is the Weisfeiler-Lemma algorithm (WI.). this work we define WL to use edge features.
Definition 2.3. (WL) The Weisfeiler-Leman algorithm (WL) is a color update function operating on a graph G = =V. E, F) defined as WL(e,, G.c) = HASH (c,, if (Ca, F ((u, v)) u E Na(v))) for E V where HASH is an injective mapping colors.
Message passing graph neural networks (MPNNs) can be seen as generalization of WL where the colors correspond to learned node embeddings and each layer of the MPNN corresponds to color update function. The color update function in layer > of an MPNN is defined as o(v, G, = COMB' (c.. (H(cz. F((z, v)) x E (N(() where COMB' and AGG' are learnable functions, e.g., multi-layer perceptrons (MLPs). We refer to WL and MPNNs as standard message passing. It has been shown that MPNNS are at most as expressive as WL, i.e., it can only distinguish non-isomorphic graphs that WL can distinguish. As there exist pairs of graphs that WL cannot distinguish this means that there exists graphs that MPNNs cannot distinguish either [Xu et al., 2019, Morris et al., 2019]. A common approach to improve the expressivity of standard message passing is to apply function T that transforms graphs to other relational structures. We call this mapping 7' from graph to a relational structure a traph-to-structuue an graph-to-structun -ttuucturr encoding can be seen in Figure 1. This mapping T is combined with a color update function e tailored to this new structure. We use non-standard message passing to refer to color update functions that operate on relational structures that are not graphs. Some examples of non-standard message passing are k-WL [Immerman and Lander, 1990] which operates on k-tuples of nodes and CW Networks [Bodnar et al., 202 which operate on regular cell complexes.
encoding. An example of
3 Strong Simulation
We show that standard message passing together with graph transformations can achieve the same expressivity as many algorithms with non-standard message passing. As standard message passing operates on graphs we need to map relational structures to graphs. Note that merely guaranteeing at least the same expressivity as a color update function & in each iteration can easily be achieved by, e-g., using the final coloring of & as node features. To avoid such a trivial solution, we enforce straightforward restrictions on the generated graphs.
Definition 3.1. (Structure-ter to-grohhgghheoo encoding) Let R be mapping R: X + G that maps relational structures X = (U,N,..... ,N .N,, F)) to graphs G = (V, E, F"). We call R a structure- toae-to--raaa to-graph encoding if it can be written as R(X)= Rieal (Rgruph (U,N1, NNk), F) such that
1. Ramph maps a relational structure without features to a graph G (V, Fggph).
2. Riea((V E, Fgraph), F) = (V, F") creates the features F* by concatenating each (node or edge) feature from Fggaph with the corresponding feature from F if it exists.
As graph-to-strue tospuuto-tt encoding T maps graphs to structures and a structure-to-get to-graph encoding R maps structures to graphs, this means that Ro T' maps graphs graphs. We call such functions Rt T graph transformations, an example can be seen in Figure 1. As we define relational structures over sets of objects, this implies that R is permutation equivariant with respect to permutation of the objects. Furthermore, since R is a function it is also deterministic. Next, we define strong simulation of color update functions.
Definition 3.2.
(Strong Simulation) Let e be a color update function. Let R be a structure-to-grant encoding that runs in (TT(( for every relational structure with object set U and creates graph with vertex set V 2 U. We consider two arbitrary relational structures from the domain of
o, say X = (U,N1, NN, F)) and X' = (U', (U',NY......A
F'). Let (V1, E1, Fi) R(X) and
(V2, Ez, F2) = R(X'). We say e can be strongly simulated under R if for every 2 it holds that WL' WL'(R(X), Filv)) (L'()(X"), Fa v)) refines &' Flu) U (X', F'lor).
'Here, define MPNNs to use edge features which practically is almost always the case.

---

Intuitively, color update function & can be strongly simulated if instead of running iterations of & on relational structure X we can instead run WL on the graph R(X) for iterations and achieve at least the same expressivity in every iteration. Strong simulation is a stronger property than expressivity: strong simulation implies being at least as expressive in every iteration whereas expressivity usually refers only to the final coloring. This guarantees that WL on R(X) is always at least as expressive as and not just in some iteration. There exist MPNNs that are as expressive as WL in every iteration [Xu et al., 2019]. Thus, every layer of an MPNN can be as expressive as the corresponding iteration of WL. Note that as long as we restrict the size of the graphs (the number of vertices), strong simulation allows to learn color update function o, e.g., GNN, exactly. Indeed, if we combine each layer of an MPNN with a large enough MLP (with appropriate activation), we can learn to map the MPNN's embeddings to the output of Φ. This problem of fitting a finite number of points exactly is well studied and known as memorization, see e.g. Yun et al. [2019] for an overview.
To strongly simulate a large number of GNNs we introduce a class of color update functions we call augmented message passing (AMP). AMP is designed to capture many GNNs and we prove that AMP can be strongly simulated. AMP makes use of building block we call atoms. Atoms model operations of color update functions such as colors, constants, or features that are focused on single vertices or pairs of vertices. AMP extends atoms with more general operations that are not necessarily focused on a single vertex such as function applications or aggregations over neighborhoods.
F)) be a relational structure. Let v, w E and Cn, Gw be the colors of v and w. Then, an atom plu, Cu. w, Cw) is function that has exactly one of the following four forms:
Definition 3.3. (Atom). Let X = (U,N1,...
(A1) p(u, Cos wi cw) = k(v, w) for constant k(U, w) that only depends on u and w but not on the colors,
(A2) p(u, Co, w. Gw) E (F(v), Flw), F(w,, v))} where F((w, v)) is only part of this set if the edge (w, v) is part of at least one neighborhood of X,
(A3) p(u, Gos w. Gw) E {Cu, C. or
(A4) p(u, Cos w. ) = (pi(v, co w. cw)..... (v, cv: W.C,W.Cl cw with atom p. for all i e [m]] Definition 3.4. (Augmented Message Passing). Let = (U.NI......N NN, F`) be relational structure with E(N)) for all i [k.] We call color update function é augmented message passing (AMP) if for all E U and coloring e of X, it can recursively be defined as exactly one of the following four forms:
(S1) o(u, x)) plu, Cui u, Gu) where p an atom,
(S2) d(u, x) Up(u, Ca, w. (wr) w E (u)) where p is any atom and any E [A]].
(S3) o(u, x) (d, X. c)..... ... Pm (u, X))
where all $1..... om are AMP, or (S4) o(u, x) f (d' (u, x)) where ff maps colors colors and o' is AMP.
Having defined AMP, we next prove that AMP can be strongly simulated by providing a structure-to- graph encoding for every color update function from AMP. Full proofs are in Appendix C.
Theorem 3.5. Augmented message passing can be strongly sinulated.
Proof sketch. We define augmented message encoding (AME) which returns a structure-to-grant encoding for every given AMP algorithm. Let be AMP that operates on a relational structure X (U.NN...... .Ns, F). AME,(X) returns a graph G with vertex set Vo = U. Any constant value atom (A1) in ó and any feature in F is stored in the vertex or edge features of G. If messages are passed between two objects then the graph will have an edge between the corresponding vertices with an edge feature encoding the neighborhood. We prove that every AMP & can be strongly simulated under the structure-to- graph encoding AME
AMP does not only contain variants of WI. but also GNN layers such as the layer of GSN [Bouritsas et al., 2022]. We say a GNN can be strongly simulated, if all of layers correspond color update functions that can be strongly simulated by the same structure-to-graph encoding R. This means
5

---

(
2 ))
HO
o
,0,00 o (ó
1 ))
2
Figure 3: WL on the graph on the left (right) side weakly simulates the nested aggregations (non-pairwise message passing) from Figure by adding additional vertices yellow ) This shows how weak simulation of both construc- tions is done in similar way with the difference being that for non-pairwise aggregation we en- code the order the tuples the edges.
Figure 2: Left: nested aggregations, Right: non- pairwise message passing of 2-tupes. In both examples the state of two vertices gets com- bined and sent to the blue vertex. Note that for non-pairwise aggregations we have an order on the nodes in tuple whereas for nested aggrega- tions the aggregated vertices are unordered.
that for every relational structure X and every 2 O, WL achieves at least the same expressivity in iteration on R(X) as layer t the GNN on X. We prove that this always the case for color update functions that only differ in their use of function applications (S4) (see Appendix C.3). Different layers a GNN commonly only differ by function applications (S4) as these correspond to learned functions. As many GNN layers use AMP, we can state one of the main results of this paper.
Corollary 3.6. The following GNNs and variants of WL can be strongly simulated:
1. VVc-GNN [Sato et al., 2019]
7. k-OSWL/ / OSAN [Qian et al., 2022]
k-WL GNN [Morris al., 2019]
8. Mj. GNN [Papp and Wattenhofer, 2022]
3. 8-I=(LL)W1. (L)GNN [Morris et al., 2020]
9. GMP [Wijesinghe and Wang, 2022]
GSN-e and GSN-v [Bouritsas et al., 2022]
10. Shortest Path Networks [Abboud al., 2022]
4. (k, s)-LWL. SpeqNet [Morris et al., 2022]
11. Generalized Distance WL [Zhang et al., 2023]
DS-WL/ GNN [Bevilacqua et al., 2021]
Proof sketch. The proof consists of showing that the color update function underlying the non- standard message passing is AMP. By Theorem 3.5 this implies that the color update function can be simulated.
Runtime Complexity. AME creates vertex for every object and edges for every pair of objects that exchange messages. This implies that, creating the encoding requires the same amount time as one iteration of AMP. Furthermore, classical message passing on the transformed graphs passes the same number of messages as AMP in every iteration. Thus, the overall runtime complexity of strongly simulating AMP is equivalent to that of running AMP itself.
Example. We illustrate AMP on the example of WL with triangle counts and without edge features. For every E VG. denote by D. the number of triangles in the graph containing We define the color update function of WL with triangle counts: Φ(v, G, c) = (Co, Il (Cu, A.)) u E (N) We show that WL with triangle counts is AMP. Consider the tuple (Cu, A.), this consists of a color cu atom (A3) with a constant Du atom (A1) combined into a tuple atom (A4). Thus, (Cu, 2.)) is an atom which means that g (c.,, Aw) Na (S2). Finally, this AMP is combined with the color atom G, (A1) and combined into a tuple AMP (S3). Thus, the color update function of WL with triangle counts performs AMP which implies that can be strongly simulated. For this it suffices to attach Dg to the features of every vertex v E V.
NN(()) AMP that aggregates this atom over the neighborhood
4 Limits of Strong Simulation
To show the limits of strong simulation we identify three constructions that either cannot be strongly simulated cannot be strongly simulated efficiently: time dependent neighborhoods, nested ag-

---

gregations, and non-pairwise message passing. These constructions have previously been used by Deac et al. [2022]. Bevilacqua et al. [2021]. Feng et al. [2022], Bodnar et al. [2021b], and Bodnar et al. [2021a]. We begin with time dependent neighborhoods which are used in the alternating message passing of Deac et al. [2022]. We illustrate them via the following example. Consider a color update function that updates the color of a vertex based on the color of in iteration t but not in iteration t'. As it depends on the iteration whether a and are neighbors, we call this time dependent neighborkoods. To model this in graph, we require an edge between and b in iteration t or we would lose expressivity whenever the color of b is important for the coloring of a. However, this means that the color of a will also be updated with the color of b in iteration t'. Thus, we can strongly simulate time dependent neighborhoods but we cannot do so efficiently (i.e., with the same number of sent messages), as we might need to send many more messages.
Nested aggregations are a form of color update functions used by Bevilacqua et al. [2021] and Feng et al. [2022]. Consider the following color update function from DSS-WI. DBvilla et al., 2021] Φ(v, c) = (ce, If il Gy y E eN(x) B x E (u) (see Figure left). 2 We call this nesting of two aggregations (He. E EN(-) B) nested aggregation. To strongly simulate this we need an edge from every vertex of (n (xx) to v. Furthermore, we need a way to group vertices N(x)
together for every E (v)). We prove that this is impossible with structure-to-ree graph encoding and thus that gested-aggregatiin
cannot be strongly simulated.
The third construction that we cannot strongly simulate is non-pairwise message passing which has been used by Bodnar et al. [2021b,a]. Non-pairwise message passing refers to aggregating colors as ordered tuples over a neighborhood N with E(N) > 1. As an example, suppose we want to update the color of vertex based the ordered tuple of colors (c):Ct) of vertices and (see Figure 2 right). This is different from the aggregation by WL or AMP as those aggregations are unordered, i.e., ffee Cb B- An issue arises when multiple such ordered tuples have to be used to update a color, as there is no way this can be done within the concept of strong simulation. Similar to nested aggregations, non-pairwise message passing cannot be strongly simulated. Note that non-pairwise message passing is a special case of nested- aggreeatggnss where an additional order on the aggregated objects given as is demonstrated in Figure 2.
Theorem 4.1. Nested aggregations and non-pairwise message passing cannot be strongly simulated.
Proof sketch. To prove this (in Appendix D), construct two relational structures that can be distin- guished with nested aggregations in one iteration. These two structures have the same adjacencies but different features. We prove that structure-to- to-graph encoding can create two graphs that one iteration of WL can distinguish. By the definition of graph-to-structury encoding, it is not possible for the original features. Thus, the two relational structure
the edges of the resulting graph to depend will lead to two graphs that have the same edges. We prove that WL. cannot distinguish these two graphs in one iteration. The proof for non-pairwise message passing works similarly.
5
Weak Simulation
We have shown in the previous section that not all color update functions can be strongly simulated. In this section, we introduce the more general concept of weak simulation and show that color update functions can be weakly simulated that are impossible to strongly simulate. Weak simulation differs from strong simulation by requiring only the same expressivity after certain number of iterations instead of every iteration.
Definition 5.1. (Weak Simulation) Let & be a color update function. Let R be a structure-to-graph encoding that runs in (TT((())) for every relational structure with object set U and creates graph with vertex set V 2 U. We consider two arbitrary relational structures from the domain of o, say X = (U,N1, NN,, F) and X' "U',,N.....,NN F'). F'). Let EV, F1) R(X) and (V2, E,, F2) = R(X'). We say 6 can be weakly simulated under R with simulation factor Ç 2 1
for every t 2 0 it holds that WLS (R()), Filv;) ) U UWL (R(*( F2lv;) refines Φ'(X, Flu) (l)) U ('(X', F.
We have altered the notation of DSS-WL from the original paper for the sake of simplicity.
7

---

The simulation factor Ç measures the relative slowdown of weak simulation with respect to the original GNN. follows that strong simulation is special case of weak simulation as every strongly simulatable algorithm is weakly simulatable with simulation factor of 1. Next, we prove that it possible to weakly simulate non-pairwise aggregations and nested aggregations. This shows that weak simulation contains a larger set of color update functions than strong simulation. The full proof can be found in Appendix E.
Theorem 5.2. Nested aggregations and non-pairwise message passing can be weakly simulated with simulation factor 2.
For weak simulation of nested aggregations consider the following construction. Sup- pose nested aggregation {{ l, y ((x) } ((u) B. For every E .V(v) we create incoming edges from ((x) and an outgoing edge (z, v) (see Figure 3 left). This allows for weak simulation with a simulation factor of 2. Non-pairwise message passing can be weakly simulated in similar way. Suppose we intend update the color of vertex based on the ordered tuple of colors (Ca, C6) of vertices a and b. Then, we create a vertex x and an edge (z, v) for this message. Furthermore, create edge (a,z) 2) labeled with 1 to indicate that it is the first element in the tuple and an edge (b, r) labeled with (see Figure 3 right). This construction weakly simulates the non-pairwise message passing with simulation factor 2.
sketch. sketch.
As consequence, we can weakly simulate the following algorithms. Corollary 5.3. The following GNNs and variants of WL can be weakly simulated:
1. Message Passing Simplicial Networks [Bodnar et al., 2021b]
2. CW Networks [Bodnar al., 2021a]
3. DSS [Bevilacqua et al., 2021]
K-hop message passing and KP-GNNs [Feng et al., 2022]
Discussion. It is possible design graph transformations that result in smaller graphs, enabling more efficient weak simulation than the transformations automatically following from Theorem 5.2. We demonstrate that this is possible for all algorithms from Corollary 5.3. For Message Passing Simplicial Networks and CW Networks it is possible to construct graphs that require no additional vertices for weak simulation (see Appendix F.1). Similarly, it is possible to weakly simulate DSS without creating a large number of additional edges by adding a second copy of the original graph if we accept increasing the simulation factor to 3 as trade-off (see Appendix F.2). Interestingly, K K-hop message passing and KP-GNNs induce an additional order on the message passing which even allows for efficient strong simulation (see Appendix F.3). We did not find any architectures where weak simulation led to large increases in time and space complexity. However, in general, we cannot rule out the possibility architectures that exhibit such an increase. This indicates the possibility for more powerful non-standard message passing, opening promising direction for future work.
6 Experiments
We have shown many cases in which graph transformation based methods achieve the same expres- sivity non-standard message passing. In this section, we empirically investigate whether MPNNs together with graph transformations can also achieve similar predictive performance as the simulated GNNs with non-standard message passing. We strongly simulate DS [Bevilacqua et al., 2021]. weakly simulate DSS [Bevilacqua et al., 2021] and weakly simulate CW Networks (CWN) [Bodnar et al., 2021a], as representative approaches. For non-standard message passing algorithm, we denote the corresponding graph transformation with bar, e.g., DSS. The code for our experiments can be found thub. com/ Catatias/GNNNN Simmlationn.
at https::/ //tp:::///tt thw.b//..ttt..././//g
Models. With GIN [Xu et al., 2019] and GCN [Kipf and Welling, 2017] we use two of the most common MPNNs as baselines. We combine these MPNNs with the graph transformations DS, DSS and CWN. DS. DS, DSS, and DSS require policy that maps a graph to subgraphs, for this we chose the common 3-egonets policy that extracts the induced 3-hop neighhorhood for each node [Bevilacqua et al., 2021]. We chose this policy creates only small subgraphs and Bevilacqua
8

---

Table 1: Predictive Performance of different GNNs on 10 different datasets. BEATS MPNN is the percentage of datasets on which the model beats the corresponding MPNN (either GIN or GCN, as noted in the model name). BEATS NSMP is the percentage of datasets where the graph transformation based model beats the corresponding non-standard message passing model. BEST MODEL the percentage of datasets where this model achieves the best results among all models.
BEATS MPNN
BEATS NSMP
BEST
MODEL
GIN
0%
GCN
0%
DS (GIN)
60%
10%
DS + GIN
60%
60%
0%
DS + GCN
70%
30%
DSS (GIN)
70%
20%
DSS GIN
70%
60%
30%
DSS GCN
70%
30%
10%
CWN
60%
20%
CWN + GIN
60%
50%
0%
CWN + GCN
50%
30%
10%
al. [2021] reported good results for it. More details DSS can be found in Appendix F.2. For CWN and CWN we construct cells as described by Bodnar al. [2021a]. More details on CWN can be found in Appendix and F.1. We apply the same training and evaluation procedure to all GNNs.
Datasets. Due the large number of combination of models and graph transformations, we focus on medium size datasets. To experimentally investigate how the graph transformations increase expressivity, we perform initial investigation with GIN the synthetic CSL dataset [Murphy et al., 2019, Dwivedi et al., 2023]. For real world prediction tasks, we use all real world datasets with less than 10t graphs that provide train, validation, and test split used in Bodnar al. [2021a], Bevilacqua et al. [2021]: ZINC [Gómez-Bombarce Bombarelli et al., 2018, Sterling and Irwin, 2015], ogbg-molbn and ogbg-moltoxe [Hu et al., 2020]. Additionally, we add seven small molecule datasests from OGB [Hu et al., 2020]. In total, we evaluate on 10 real-life datasets."
Setup. For real-life datasets we combine all baseline models (GCN, GIN) with all graph transformations (DS, DSS, CWN) and tune hyperparameters individually (including CWN, DS and DSS; see Appendix H). We also measure the preprocessing and training speeds for different models (details and speed results are Appendix H.3).
Table 2:
Accuracy on CSL. Bold results outperform GIN.
CSL ACCURACY
MODEL
Results. Table 2 shows the results on CSL. GIN achieves 10% accuracy whereas all other methods achieve perfect accuracy. This
GIN
0.1 0.0
CWN
1.0
confirms that just like standaadd message passing, MPNNs with
CWN + GIN
1.0
graph transformations have superior expressivity compared to GIN. Table summarizes the results on all real life datasets. Indeed,
DSS
1.0
DSS + GIN
1.0
MPNNs with graph transformations achieve the best result on half of them. Just like non-standard message passing, MPNNs with graph transformations outperform MPNNs in the majority of experiments. Notably, graph transformations combined with GIN outperform non- standard message passing in more than half of the experiments. This shows that simulated networks not only have provably at least the same expressivity but also perform surprisingly well in practice.
DS
1.0
DS GIN
1.0
'We use the following datasets: ZINC with 12k nodes, ogbg-molhiv, ogbg-moltoz2 ogbg-molesol. mobg-eolbace, sglg-oolclintox. ogbg molbbbp,, molg-molsider, tolgxoootoxcast. and ogbg-mollipo.

---

7 Discussion and Conclusion
Discussion. The purpose of simulating a GNN is to allow an MPNN to learn similar embeddings of graphs the GNN. We expect such embeddings to model the similarity of graphs in more fine-grained way than just distinguishing graphs. Thus, we have to avoid trivial solutions: any MPNN can be made expressive as any other GNN when the output of the GNN is attached the input of the MPNN. In fact, it is even possible to make an MPNN maximally expressive by precomputing the isomorphism class of the graph, c.g.. a number uniquely encoding whether two graphs are isomorphic, and inputting it into the MPNN. However, such techniques defeat the purpose of learning a graph representation in the first place and potentially require super-polynomin runtime [Babai, 2016]. To avoid such scenarios, we introduce two requirements for weak and strong simulation: (1) the features of the resulting graph depend on the original features solely by concatenation and (2) the transformation must operate in linear time relative to the simulated color update function. These two constraints render impossible to precompute the colors generated by the simulated method for non-constant number of iterations and prohibit the computation of graph isomorphism classes.
Implications. Our work has implications on (1) the theory of GNNs, (2) the design of new GNNs, and (3) the implementation GNNs with graph transformations. For (1): simulation allows to investigate the expressivity of different GNNs through a unified lens by analyzing the corresponding graph transformation. It should be possible to obtaín VC bounds for any weakly simulatable GNN by using the results from Morris et al. [2023]. Similarly, we believe that it is possible to use Geerts and Reutter [2022] to get expressivity upper-bounds in term of the k- &L test for any weakly simulatable GNN. For (2): our theorems indicate that nested aggregations and non- non-pairwise message passing cannot be strongly simulated and are thus fundamentally different from the message passing paradigm. Thus, to build GNNs that go beyond MPNNs in expressivity it seems promising to investigate such constructions. For (3): instead of implementing a GNN with non-standard message passing, our theorems imply it can be implemented as graph transformation together with an MPNN. This makes it easier to implement GNNs as of-the-shelf MPNNs can be used and makes the resulting method agnostic from the deep learning framework as the graph transformation does most of the heavy lifting.
Conclusion. We introduced weak and strong simulation of non-standard message passing. Simu- lation allows an MPNN together with a graph transformation to obtain the same expressivity every < layers (weak simulation) or in every layer (strong simulation) as GNNs with non-standard mes- sage passing. We have proposed a straightforward way of proving that an algorithm can be simulated and to generate the corresponding graph transformations. This generalizes previous ideas [Otto, 1997, Morris et al., 2019, 2020, 2022, Qian et al., 2022] and makes simulating GNNs accessible to anyone who intends build novel GNNs. In total, we have shown that 15 GNNs can be simulated. We chose these 15 models to showcase the variety of GNNs that fall under augmented message passing and expect many more GNNs to simulatable as well. future research, we will investigate the use of simulation to analyze aspects of GNNs such generalization, oversmoothing, and oversquashing.
Acknowledgements. Part of this work has been supported by the Vienna Science and Technology Fund (WWTF) project ICT22-059. The authors would like to thank the reviewers for the feedback. We are especially thankful to our colleagues Pascal Welke and Tamara Drucks for giving extensive feedback on a draft of this paper.
References
R. Abboud, i. i. Ceylan, M. Grohe, and T. Lukasiewicz. The surprising power of graph neural networks with random node initialization. In IJCAI, 2021.
R. Abboud, R. Dimitrov, and I. I. Ceylan. Shortest path networks for graph property prediction. In Learning on Graphs Conference, 2022.
L. Babai. Graph isomorphism in quasipolynomial time. STOC, 2016.
Barceló, F. Geerts, J. L.. Reutter, and M. Ryschkov. Graph neural networks with local graph parameters, In NewrIPS, 2021.
10

---

B. Bevilacqua, F. Frasca, D. Lim, B. Srinivasan, C. Cai. G. Balamurugan, M. Bronstein, and H. Maron. Equivariant subgraph aggregation networks. In ICLR, 2021.
L. Biewald. Experiment tracking with weights and biases, 2020. URL httpss//www. wwndb//wwwwwwww.......m/mm...... com/ Software available from wandb.com.
C. Bodnar, Frasca, N. Otter, Y. G. Wang, P. Liò, Montúfar, and M. Bronstein. Weisfeiler and Lehman go cellular: CW networks. In NeurIPS, 2021a.
C. Bodnar, F. Frasca, Y. G. Wang, N. Otter, G. Montufar, P. Lio, and M. Bronstein. Weisfeiler and Lehman go topological: Message passing simplicial networks. In ICML, 2021b
G. Bouritsas, F. Frasca, S. Zafeiriou, and M. M. Bronstein. Improving graph neural network expressivity via subgraph isomorphism counting. Transactions on Pattern Analysis and Machine Intelligence, 45(1):657-668, 2022.
G. Dasoulas, L. Dos Santos, K. Scaman, and A. Virmaux. Coloring graph neural networks for node disambiguation. In IJCAI, 2020.
A. Deac, M. Lackenby, and P. Veličković. Expander graph propagation. In Learning on Graphs Conference, 2022.
V. P. Dwivedi, C. K. Joshi, A. T. Luu, T. Laurent, Y. Bengio, and X. Bresson. Benchmarking graph neural networks. Journal of Machine Learning Research, 24(43): 188 2023.
Ebli, M. Defferrard, and G. Spreemann. Simplicial neural networks. In NeurIPS, 2020.
J. Feng, Y. Chen, F. Li, A. Sarkar, and M. Zhang. How powerful are K K-hop message passing graph neural networks. NeurIPS, 2022.
M. Fey and E. Lenssen. Fast graph representation learning with PyTorch Geometric. In ICLR Workshop Representation Learning Graphs and Manifolds, 2019.
Frasca, B. Bevilacqua, M. M. Bronstein, and H. Maron. Understanding and extending subgraph GNNs by rethinking their symmetries. In NeurlPS, 2022.
F. Geerts and J. I.. Reutter. Expressiveness and approximation properties of graph neural networks. In ICLR, 2022.
M. Grohe, P. Schweitzer, and D. Wiebking. Deep Weisfeiler Leman. In SODA, 2021.
R. Gómez-Bombarelli, N. Wei, D. Duvenaud, M. Hernández-Lobato, B. Sänchez-Lengelingg D. Sheberla, J. aguilera-Iparraguine T. D. Hirzel, R. P. Adams, and A. Aspuru-Guzik, Automatic chemical design using data-driven continuous representation of molecules. ACS Central Science, 2018.
M. Hajij, K. Istvan, and G. Zamzmi. Cell complex neural networks. In Topological Data Analysis and Beyond Workshop at NeurIPS, 2020.
M. Hajij. G. Zamzmi, T. Papamarkou, N. Miolane, A. Guzmán-Sáenz, K. N. Ramamurthy, T. Birdal, T. K. Dey, S. Mukherjee, S. N. Samaga, N. Livesay, R. Walters, P. Rosen, and M. T. Schaub. Topological deep learning: Going beyond graph data. 2rXiv:2006.00606633, 2023.
W. Hu, M. Fey, M. Zitnik, Y. Dong, H. Ren, B. Liu, M. Catasta, and J. Leskovec. Open Graph Benchmark: Datasets for machine learning on graphs. In NeurIPS, 2020.
N. Immerman and E. Lander. Describing graphs: A first-order approach to graph canonization. In Complexity Theory Retrospective, pages 59 01. 1990.
Jogl, M. Thiessen, and T. Gärtner. Reducing learning on cell complexes to graphs. In Workshop on Geometrical and Topological Representation Learning at ICLR, 2022a.
Jogl, M. Thiessen, and Gärtner. Weisfeiler and Leman return with graph transformations. In International Workshop Mining and Learning with Graphs ECMLPKDD, 2022b.

---

A. D. Keros, V. Nanda, and K. Subr. Dist2Cycle: A simplicial neural network for homology localization. In AAAI, 2022.
Kipf and M. Welling. Semi-supervised classification with graph convolutional networks. In ICLR, 2017.
C. Morris, M. Ritzert, M. Fey, W. Hamilton, J. Lenssen, G. Rattan, and M. Grohe. Weisfeiler and Leman go neural: Higher-order graph neural networks. In AAAI, 2019.
C. Morris, G. Rattan, and P. Mutzel. Weisfeiler and Leman go sparse: Towards scalable higher-order graph embeddings. In NeurIPS, 2020.
C. Morris, G. Rattan, S. Kiefer, and Ravanbakhsh. SpeqNets: Sparsity-aware permutation- equivariant graph networks. In ICML, 2022.
C. Morris, F. Geerts, J. Tönshoff, and M. Grohe. WL meet VC. In /CML, 2023.
R. L. Murphy, B. Srinivasan, V. Rao, and B. Ribeiro. Relational Pooling for Graph Representations. In ICML, 2019.
M. Otto. Bounded variable logics and counting study in finite models. In Volume of Lecture Notes in Logic, 1997.
A. Papp and R. Wattenhofer. A theoretical comparison of graph neural network extensions. In ICML, 2022.
A. Paszke, S. Gross, F. Massa, A. Lerer, J. Bradbury, G. Chanan, T. Killeen, Z. Lin, N. Gimelshein, L. Antiga, A. Desmaison, A. Kopf. E. Yang, Z. DeVito, M. Raison, A. Tejani, S. Chilamkurthy, B. Steiner, L. Fang, J. Bai, and S. Chintala. PyTorch: An imperative style, high-performance deep
learning library. NeurlPS, 2019.
C. Qian, G. Rattan, Geerts, C. Morris, and M. Niepert. Ordered subgraph aggregation networks. In NeurlPS, 2022.
R. Sato, M. Yamada, and H. Kashima. Approximation ratios of graph neural networks for combinato- rial problems, In NewrIPS, 2019.
R. Sato, M. Yamada, and H. Kashima. Random features strengthen graph neural networks. In SDM, 2021.
Sterling and Irwin. ZINC 15 ligand discovery for everyone. Journal of Chemical Information and Modeling, 2015.
E. Thiede, W. Zhou, and R. Kondor. Autobahn: Automorphism-basee based graph neural nets. In NeurIPS, 2021.
P. Veličković. Message passing all the way In ICLR Workshop on Geometrical and Topological Representation Learning, 2022.
A. Wijesinghe and Q Wang. new perspective on "how graph neural networks go beyond Weisfeiler- Lehman?". In ICLR, 2022.
K. Xu, W. Hu, J. Leskovec, and S. Jegelka. How powerful are graph neural networks? In ICLR, 2019.
C. Yun, S. Sra, and A. Jadbabaie. Small ReLU networks powerful memorizers: tight analysis of memorization capacity. NeurIPS, 2019.
B. Zhang, S. Luo, L. Wang, and D. He. Rethinking the expressive power of GNNs via graph biconnectivity. In ICLR, 2023.
12

---

A Related Work: Expressivity of GNNs
In this section, we talk about research on the expressivity of GNNs and how it relates to our paper. Xu et al. [2019] and Morris et al. [2019] proved that MPNNs have limited expressivity. This lead to the development of new GNNs that have higher expressivity than MPNNs. We distinguish between GNNs that perform non-standard message passing and GNNs that use an MPNN on a transformed graph. We begin with approaches that correspond to MPNNs on a transformed graph. A common approach for this adds additional features to the graph. It has been proven that adding random features to vertices improves the expressivity of GNNs [Abboud et al., 2021, Dasoulas et al., 2020, Sato et al., 2021] which allows them to learn every function defined on a graph and thus gives them maximum expressivity. However, to do this they sacrifice determinism, and permutation invariance / equivariance. Some permutation equivariant approaches extend the graph features by counting patterns such as Barceló et al. [2021] which extend the MPNN with rooted homomorphism counts of a set of patterns. All approaches that consist of deterministically adding additional features to vertices and edges in permutation equivariant way can be trivially strongly simulated and belong to augmented message passing. Graph Structural Networks (GSN-e and GSN-v; Bouritsas et al. [2022]) introduce a new graph convolution layer which extends messages with subgraph isomorphism counts. This cannot be directly seen as transforming graphs. However, it is very similar to adding these subgraph isomorphism counts to the vertex features and thus to an MPNN operating on a transformed graph.
Next, we consider approaches that use non-standard message passing. Such approaches often operate on different structures such as (1) k-tuples of nodes, (2) topological objects such as simplical complexes or regular cell complexes, and (3) subgraphs. Type (1) passes messages between k- tuples of nodes. Higher dimensional WL (k-WL) is a generalization of WL and forms a sequence of algorithms that are stronger than WL [Immerman and Lander, 1990]. Increasing k increases expressivity at the cost of exponentially increasing the runtime. Morris et al. [2019] introduced k-dimensional GNNs which extend the concept of k- k- GNNs. For every there exist k-GNNs that have equal expressivity as k-WL. However, as k increases, the runtime of k-GNNs grows exponentially. To combat this, Morris et al. [2020] introduced (local) 8-k dimensional WL and GNNs; Morris et al. [2022] introduce (k, LLLL and (k: s)-SpeqNets. These methods make use of the sparsity of the graph to reduce computation time. Type (2) operates on topological structures such as simplical complexes or regular cell complexes. Three prominent examples of this idea are Simplical Networks [Bodnar et al., 2021b], CW Networks [Bodnar et al., 2021a] and message- passing combinatorial complex neural networks (Hajij et al., 2023]. Other algorithms that work on topological structures are Simplical Neural Networks [Ebli et al., 2020], Dist2Cycle [Keros et al., 2022], and Cell Complex Neural Networks [Hajij et al., 2020]. Type (3) decomposes the graph into subgraphs and then performs message passing on these subgraphs. Examples of these algorithms are Automorphism-bait based Neural Networks [Thiede et al., 2021]. Subgraph GNNs [Frasca et al., 2022], and Equivariant Subgraph Aggregation Networks (ESAN; Bevilacqua et al. [2021]) J). ESAN uses a policy to transform a graph into set of subgraphs and then processes them either separately (DS-WL WL GNN) or in a way that allows information transfer between the subgraphs (DSS WL/ GNN). The GNN Mr [Papp and Wattenhofer, 2022] separately processes subgraphs consisting of the entire original graph with & nodes that are marked. Ordered subgraph aggregation networks (K-OSAN) [Qian al., 2022] operate on k-ordered vertex subgraphs, k-OSAN is upper bounded in expressivity by (k+ + I)- and incomparable to k-W Frasca et al. [2022] proves that GNNs based on subgraphs are upper bounded by 3-WL. Finally, we list other GNNs with non-standard message passing that we can simulate: - [Sato et al., 2019] have been shown to be stronger than standard message passing GNNs in approximating algorithmic problems such as minimum dominating set. Wijesinghe and Wang [2022] introduce a generalized message passing framework (GMP) which allows them to inject local structure into the aggregation scheme. K-hop message passing [Feng et al., 2022] extend MPNNs from h-hop neighborhoods to K K-hopp neighborhoods. KP-GNNs [Feng et al., 2022] extends K-hop message passing by including additional information about the subgraphs induced by the K K-hop neighborhood. In summary, there exist many GNNs that are more expressive than MPNNs. Despite the conceptual differences between these GNNs we show that many of them are some form of augmented message passing and thus can be simulated.
13

---

B Related Work: Simulating Message Passing
We investigate previous approaches simulating GNNs with MPNNS transformed graphs by ana- lyzing papers and source code of different architectures. We begin with algorithms from Corollary 3.6. GSN-e / GSN-v [Bouritsas et al., 2022] and DS-WL/ DS-GN [Bevilacqua al., 2021] were not implemented via graph transformations. In practice however, there little difference between their implementation of DS-WL/ W GN and our implementation with graph transformations: Bevilacqua et al. [2021] implement subgraphs as separate graphs while we implement them as separate subgraphs of the same graphs. For VV-GGNNs [Sato et al., 2019], we could find indication that they were im- plemented with graph transformations. M&-GNNS [Papp and Wattenhofer, 2022] is a purely theoretic work and has not been implemented by the corresponding authors. For GMP [Wijesinhhe and Wang, 2022], we are not sure if their code can count as being implemented as graph transformation as they adapt message passing layers to use their structural information. However, for this they change the definition of the layers whereas we only change the graphs. Morris et al. [2019] introduced E-GNNs and implemented them with MPNNS on a transformed graph. Morris al. [2019] even call this simulation and give a short proof that WL can simulate k- WL on transformed graphs. This corresponds to our concept of strong simulation, and this property of k- WL was already noticed by Otto [1997] [Grohe et al., 2021].
For 6-K-(L)GNN, Morris al. [2020] write that they implemented 6-L-(L)GNNS
[...] using PYTORCH GEOMETRIC, using Sython-wrapped C++11 prepro- cessing routine to compute the computational graphs for the higher-order GNN. We used the GIN-e layer to express [ and fage of [...].
An inspection of their code reveals that they create a similar graph structure we propose in the proof of Corollary 3.6. For 5-k-GNN they create graph where the vertices represent the k-tuples. They add an edge between two nodes if the tuples are j-neighbors, with j E [k]. Just like in our graph transformation the edge type encodes whether the tuples are local or global j-neighbors and the neighborhood j. For (k. SeSSpqNee (or (ki s)-WW)) Morris et al. [2022] write that (k,, Neta were implemented
[...] I using PyTorch Geometric, using a Python-wrapped C++1l preprocessing routine to compute the computational graphs for the higher-order GNNs. We used the GIN-e layer to express f and f of [...].
Similar to our graph transformation from Corollary 3.6, they create a new graph where each node corresponds to an ordered subgraph v E Vg of size k with most connected components in this subgraph. Just like in our graph transformation, edges are added between nodes if their tuples only differ at position j E [K] and the nodes at position j are neighbors. Additionally, the edge features in the transformed graph encode the edge features from the original graph in way that allows them to encode j. Thus, their graph transformation follows ours. Both Morris et al. [2020] and Morris et al. [2022] reference Morris et al. [2019] to argue that there exist instantiations powerful enough for f and fWW; For k-OSWL/ OSAN, Qian et al. [2022] state in their paper
[...] I the computation of k- O-OSSL's coloring relies the simple and easy-to- implement 1-WL..
follows that the authors of these four papers were aware of simulation. However, to the best of our knowledge they have never formalized or fully explained their idea. In contrast, we fully formalize the idea of simulation and provide proofs that show that these graph transformations provably simulate the corresponding GNNs. Additionally, we provide recipes for obtaining graph transformations for augmented message passing algorithms.
To the best of our knowledge, so far Simplical Message Passing Networks [Bodnar et al., 202 lb], CWN [Bodnar et al., 202 20] OSS-GNN// / WL [Bevilacqua et al., 2021]. K-hop message passing and KP-GNNs [Feng et al., 2022] have not been implemented using weak simulation. However, another topological deep learning network the combinatorial complex neural network [Hajij et al., 2023] has been implemented based on GNNs. For this, the authors transformation to an augmented Hasse graph by transforming cells to vertices and adding edges between vertices corresponding to adjacent cells. This is similar to CWN, our proposed transformation from regular cell complexes to graph. Specifically, Hajij et al. [2023] state the following about their implementation TopoEmbedX:
14

---

TopoEmbedXX [..] supports higher-order representation learning on cell complexes, simplicial complexes, and CCs. [...] TopoEmbedX converts a given higher-order domain into subgraph of the corresponding augmented Hasse graph, and then utilizes existing graph representation learning algorithms to compute the embedding of elements of this subgraph.
Finally, Veličković [2022] proposes that all functions over graphs that are of interest can be computed with message passing over a transformed graph. They call this augmented message passing which inspired our use of this term. They discuss how to perform some particular variants of non-standard message passing through standard message passing. This is helpful and demonstrates the wide applicability of this approach. However, their work is intended as positional paper and thus mostly stays high level and does not provide sufficient formal proofs to back up their claims. Providing the necessary proofs is non-trivial: once one understands simulation it is straightforward to apply it to a large number of architectures and is simple to prove simulatability for any one given architecture. However, difficulty arises when one tries to prove this for large number of architectures. Thus, the difficulty is not proving simulatability but defining a framework that allows us to prove this for many different architectures. We provide such a framework based on color update functions. Furthermore, Veličković [2022] does not provide a formal definition of simulation (or in their case augmented message passing). Indeed, it is trivially possible to build maximally expressive MPNNs by precomputing the isomorphism class of the input graph. Thus, without a restriction on the transformation, the general statement that GNN can be implemented as an MPNN plus transformation is only meaningful if the transformation is in some sense close to what the GNN does. We solve this issue through our careful definition of truuctre-to-grapee encoding which restrict how the transformation can access features of the structure and through the definition of weak / strong simulation that pose a runtime restriction on the transformation.
C Proofs for Strong Simulation (Section 3)
C.1 Rewriting AMPs (Lemma C.1)
We use the following Lemma that allows us to rewrite AMPs without losing the strong simulation property. For a function & use IM[ő] to denote the image of ø.
Lemma C.1. Let d be color update function. We are given set of objects with neighborhood functions from the domain of & and colors. Let (()) be a color update functions such that there exists an injective (bijective) mapping between IM[Ø and [M]] Then, a coloring obtained from I'()) refines coloring obtained from 6. Furthermore, if the mapping A is bijective the coloring from ó refines the coloring from lo)
This lemma allows to simplify AMPs by replacing functions (S4) with the identity function i.e. f()) is replaced by é. This transformation is bijective if f is injective. Furthermore, we can use this flatten tuples (A4) (S3) i.e. (-.., (#1 (Øi...., (n)....) is replaced by (..., 61, $1,... ..... Pn. .... Flattening tuples with the same structure is bijective. Thus, we can apply these transformations without losing the simulatable property. We prove the correctness of the above lemma.
Proof. Let A be the injective mapping from the color assigned to objects from 6 to I(Ø). For an arbitrary iteration, let Tw. Tp be the colors assigned to w E W. E P by I(Ø) and Cp the colors assigned to them by Φ. We start by showing that if there exists the required injective mapping, then the coloring æ from ((O) refines the coloring e from Φ. For this, we assume that & can distinguish w, p and show that this implies that (()) can also distinguish them. Formally, we show Gu * Cp 7 nw * Tp. this is the contraposition of the definition of refinement. Suppose Cw * Cp.
then from Te = A(cw) and T. = A(cp) and the fact that A is injective follows that Nw # Tp.
Next, we show that if A is bijective then the colorings from e and l'(Ø) refine each other. We assume that A is bijective. From the above argument, then follows that the coloring from I'(() refines the coloring from o. It remains to show that the coloring from é refines that from [()). Similar above, we show that if [()) can distinguish w and p. then so can o. Thus, we assume Te 7 Яр and show
Cu # Cp- Using the bijectiveness of follows from our assumption that A (m))) 7 A - (TT)) and
thus that ew # Cp. This concludes the proof.
15

---

Algorithm Helper algorithm for atoms
Input: atom p type (AI), (A2).A33,, graph (V, E, P'graph), object w, object y, indices i,
Output: updated graph G = (V, F,gpp) grahh)
if p is of type (A2) or (A3) then
return (V, E, Fggrph)
else p(w, Cuss 9, Cq) is constant k(w, q)
if w is then
Feraph( (w) = ENC( graph (w), i, kww, w))
else
F'gaahh ((q, w)) = ENC graph ((g, w)) 8, k(w, 4))
end if
end
return (V, graph)
Algorithm 2 Helper algorithm for (S2)
Input: AMP (S2) shape (p(w, c q, dg) | g E (N(ww) } where p is an atom and E(N,) = 1; graph E, Fgaph), relational structure (U,NG) without features, indices i.j.
Output: updated graph G (V, EY,,Fgggmi gmph)
for E do
for E (u) do e == (g, u)
if & E' then
= EU {c}
F graph (e) empty vector
end if
F "graph(e (e) ENC( (rC((Frra((()),, (.,
end for
end for
/* has the shape (pi(w, Cw. Q1. cg). .., , (w, Cw Pm, cy)) "1
for l [m]] do
/* Pt is either an (A1), (A2) an (A3) %
for U do
for (u) do
(V, E, Fgraph) == Algorithm 1(pi, (V, E, Fguppt), u, u,q, (,
end for end for end for return (V, E, Fgrph))
C.2 Augmented Message Passing can be Simulated (Theorem 3.5)
We are interested in showing the following theorem.
Theorem 3.5. Augmented message passing can strongly simulated.
To prove the above theorem we define augmented message encoding (AME) in Algorithm 4. For this we assume a function ENC: (æ, i, (,,,) + x', that updates a feature & to x' by attaching the color at the indices i. l. We assume that applying ENC multiple times never overwrites information if different indices are used. For example, we can think of the feature æ as 3d-tensor such that ENC(x, i, c) updates this vector by writing the entry position j. Observe, that in Algorithm 4 never happens that the same indices are used, thus whenever AME encodes information in the graph, this information does not get overwritten by latter operations. We prove the theorem by showing that AME+ can simulate any given AMP.
Proof. (Theorem 3.5) Let ø be an arbitrary augmented message passing algorithm. We consider two arbitrary relational structures from the domain of Φ. say X (U,N1,....,NN F) and X' (U', .Y ,Y....,,N F*). Let Fi, R(X) and (U', Eg, F2) R(X'). We prove (1) that
16

---

Algorithm 3 Helper algorithm for AMP
Input: AMP color update function ó (01, ......, .0)) where each individual AMP is (AI), (A2), (A3) or (S2), graph (V. E, F gmph), relational structure (U.NN.....,N), without features where ((NG) for all [[]]] index i.
Output: updated graph G E, graph))
for j E [m]] do
if Φ3 is (A1), (A2) (A3) then
for u E U do
(V. E, F ggrap)) == Algorithm 1(0j, (V, E, F Fggap)) ú, 0)
end for
else
/" di has the shape Kp(w, Cw. q, cq) l q E (.WW))) where p is an atom and & [k] (V. E, Fgraph) == Algorithm 2(0;, (V, E, Fenph), (U,Ne), i,5)
end if
end for return (V, F Frrah))
Algorithm 4 Augmented message encoding (AME)
Input: relational structure X = (U,W1,..... Nkk. F) where ((N,) = for every E [k]] AMP color update function é). Output: graph G (U, LUEE,YY
R Rgraph" / E :
F ggapph empty features Replace function applications (S4) in by the identity function, i.c., f(o) becomes ø.
Flatten all (A4), (S3) constructions in & except the outermost, i.c., (...,()),.... (eI..... o.)....) becomes
(..., $1.... .n....).
1" Φ has the shape (ØI...., @n) where each o; with i E [n] is one of (A1), (A2), (A3) (S2) */
(U, F, grraph) Algorithm ((Ø, (U, E, F Fgaph), (U, .,,,),,,)))))
1" Rreat /
F' : empty features
for E do
F'(u): == concat (F(u), F Frraph (u))
end for
for E E do
F'(e) == concat (F(e,, Fgraph (e))
end for return (U,E.F')
AME, is a smucture-to-grapp encoding such that R(X) runs in (TTT((U))): (2) for every t 2 0 the coloring WL' ())()(X), F WL' (XX'), Feler) on AME (X) refines the coloring Ø'(X, Flo)u 6'(X",F'le"
We begin by proving (1). Observe that Algorithm can be split into Rgaph and RA as required by the definition of structure-to- to-grphh encoding, Furthermore, Algorithm 4 first iterates through all AMPs @ and all possible objects that are relevant to these AMPs. Hence, Algorithm 4 runs in the same runtime as one iteration of AMP which is in (UU
Next, we prove (2). We use T T. and cf of. to denote the colors assigned vertex object u (U U U²) in iteration t by WL on R(X), R(X') or on X, X', respectively. We show by induction that WL cannot distinguish u and r given iteration then neither can 6. Formally, -f = ci which implies that WI. (X) F Filv) (R((R( F2le)) refines
we show x. (X, Flu) U O F" (tr) as the domain of the coloring computed by Φ is the same as the domain of the coloring computed by WL UU')
17

---

Algorithm 4 starts by replacing all function applications (S4) by the identity function and flattens all tuples (A4) (S3). Recall that this transformation is either injective or bijective. By applying Lemma C.1 they do not influence the strong simulation property. From now on we assume that = (01,.... Φn) such that all Φj with j E [n]] are either (A1), (A2) (A3), or (S2) and if they are an atom, then the first and third function argument are identical. We use w to denote the object the AMP is defined to update. Algorithm iterates through all .1,..., on and encodes them in the graph.
Base case: We show that T. = .. + - - C.. For this, we assume that Th =Tp- Since the initial colors of WL correspond to the vertex features which encode the object features of X and X' that are used as the initial coloring of AMP, this implies that ch c..
Induction hypothesis: We assume that ot गे c ct holds for all t S T.
Induction step: We show that Ty T+1 x, I+1 = C T+1 2T+1 We assume π T+1 = n. T+1 We iterate through all AMPs from 01..... On and show that they must all return the same result for and r which implies c c[+1 = c of+ We do a case distinction on the type of this AMP. Note that in AMP the object/ / edge features are referred to us F(.) whereas in the relational structures X and X' they are denoted as (.) and (').). Below, when we argue that two AMP constructions are equal and use the F-) notation and neglect (-))) for the sake of simplicity.
(A1) (k(u,u) u) - ((r,))) This atom was encoded into the graph by Algorithm 1. These constants are part of the vertex features of the graphs R(X), R(X') and thus are part of the initial coloring Th =f. Since WL refines colorings, the assumption that m -T+1 म. T+I implies = = ".. =m Thus, k(u, u) = r)r
(A2) [F(u) = F(r)). As the object features are encoded into the vertex features of R(X), R(X') (see Rien in Algorithm 4), they are part of the initial coloring Tu Th Since WL refines colorings, the assumption that n. ., T+1 implies x. = .τ. Thus, F(u) F(r).
(A3) (o) 1 cf) This atom was not encoded into the graph. From our assumption we know that T T+1 = म.. -T= Since WL refines colorings this implies that π. = प,-- By applying the induction hypothesis obtain that c/ =
_T+1 then for every neighborhood relation N₁ there exists bijective c2) | N((u)) 1 (p(r, B. y ( This AMP was en- (S2) (Up(,, 2,,
coded into the graph by Algorithm 2. Note that the neighborhood relation Nr was en- coded edges with edge features labeled i, this means that if two nodes have the same color n T+1
a : (u) + N((r) such that for all E NN(u)) it holds that n. = nT and that the edges (xr u). (a(z). r) have the same edge features. From the induction hypothesis it then follows that ofe = ca(z) Let p(: of D, o = (pr(s of Q1, (h),. .eo)),..,,,,,,, (m ( of 2m, (fm)
a(a)
for some m M 1. We show for an arbitrary j E [m]] that Pj (u,ck' R2 c.)
Pj (n.. Sg. T where either 22 u. = r, or 22 = x, S2' = a(x). We do case distinction the type of Pj-
(A1) 05 k(a, b). We do case distinction whether b:
* Case = b. By assumption we need to show k(u, u) - k(r,r). Recall that the vertex features (u), (r) encode k(u, u) and k(r, where μt, (1,2) (see Algorithm 1), respectively. Hence, the initial colors Th and n. also encode k(u, u) and k(r,, r). As WL. refines colorings and x. = =T holds that x = xf which implies that k(u, u) = k(r,r).
* Case # b. Then (b, a) forms an edge meaning we need to show that k(u, x)) _ k(r, (x)). Recall that the feature Fa((2, u)) encodes k(u, x)) and that feature F(((((z), r) encodes kir, a(x)) where, 14, R E {1, 2) (Algorithm 1). From the definition of a follows that the edges (z, u) and (a(x)),)) r) have the same features and thus that i(u,, x) = k(r, a(x)). (A2) We do a case distinction:
18

---

* Case F(u) - F(r). See proof of (A2) above.
* Case F(x) = F((())) We know that T = T a(x) Recall that the object features encoded in the vertex features and thus in the initial coloring л.. Since WL refines colorings, it follows from o T that To = = =a(x) which implies F(z) F(a(x)).
a((a)
Case (((I,,))) F((a(x).r)) As argued above we know that the edges (a, u) and (a( have the same features which implies F((z, u))) = F((a(x), r)).
(A3) P3 c.. We do case distinction
* Case is the vertex to update i.e., and r. Then, we need to show that of 1 of. We know that Th = o.. and by the induction hypothesis follows that cy c.. Case is the neighboring vertex i..., and a(x). Then, need to show that T ((w)) We combine o nh (()) with the induction hypothesis to obtain 2 a())'
Thus we conclude that P2(u, ct. S. ct) Pj (r.c,, co(z) which means that cox),
plu, = p (r. a(x), (.)) This concludes the proof of the induction step.
C.3 Strongly Simulating GNNs
We prove theorem that allows to simulate combination of multiple AMPs that differ only by function applications (S4). This allows us to simulate GNNs whose layers correspond to AMPs.
Theorem C.2. Let o1...., dt be 1 2 AMPs that only differ in function application (S4). Let encoding where v is the AMP obtained by removing function
R = AME be structure-to-geet applications from Φ1. Then, it holds for every pair of relational structures X,X' from the domain of ......, &i and every 1 > Z 1 that iterations WL R(X) and R(X') refines the coloring produced by (Ø) .... o dr) on X and X'.
Note that it does not matter whether construct t by removing function applications from ái or any other AMP from $1,..., Φt as these AMP only differ by function application.
Proof. Let X = (U.N No. F) and X' (U',N,,.... No. F') be two arbitrary relational structure from the domain of é1 ....o oi and let l > 2 1. By Lemma C.1 any coloring produced by refines the corresponding coloring from every AMP from Φ1.... .I..... ... 01. Thus, v Flu) refines
(di .... (X, Flu) and w (X', Fllrr) refines (Φ) o o... (X) F' Fl By Theorem 3.5 can strongly simulate v under R. Thus, the theorem follows.
C.4 List of Strongly Simulatable Algorithms (Corollary 3.6)
We prove Corollary 3.6.
Corollary C.3. The following GNNs and variants of WL can be strongly simulated:
1. VVc-GNN [Sato et al., 2019]
7. k-OSWL/ OSAN [Qian et al., 2022]
k-WL / GNN [Morris et al., 2019]
8. Mr, GNN [Papp and Wattenhofer, 2022]
3. 3-k-(L)WL/ (L)GNN [Morris al., 2020]
9. GMP [Wijesinghe and Wang, 2022]
GSN-e and GSN-v [Bouritsas et al., 2022]
10. Shortest Path Networks [Abboud et al., 2022]
4. (k, s)-LWL SpeqNet [Morris et al., 2022]
11. Generalized Distance WL [Zhang al., 2023]
DS- DS-WL- /L/ GNN [Bevilacqua et al., 2021]
Proof. The proofs consist of showing that the update rule underlying the corresponding algorithms
AMP. By invoking Theorem 3.5 this proves that the algorithm is strongly simulatable. For
19

---

algorithms that have both a GNN and a WL variant we only prove this for the WL variant as for GNN the proof can be done analogously. Note that most variants of WL and GNNs contain the color of the vertex they want to update in the updated color. An example of this the color c in the definition
of k-WL: ct = HASH (c--1, (s). ..... (s))) where (s) = HASH (ff c s' E (s)ss B)) This color can be modeled by color atom (A3). We will argue this again for the first two algorithms and will assume that this is obvious for the latter algorithms.
1. VVc-GNNs [Sato al., 2019]: Let A be the maximum degree of the vertices. Suppose
we are given port numbering with functions (,) : V x [ - V {-} and Pu V x [ -> [A] (-).4
The color update function for VVo-GNNs is
1+1 = S6 2/0 L 20
"Pmn(t.1):P((t, Pa(,, 1), = 2p) Pa(e, 2).... L ()) Pr(e, A).)
Let i E [A]. The color update function applies function S/ (S4) to a tuple. We need to show that this tuple corresponds to tuple AMP construction (S3) by show- ing that each element of the tuple is AMP. The first element of the tuple is 2 which corresponds to an AMP (SI) atom. Each Pn(u, can be seen as a constant atom (A1). Each z (aa(o,s) can be seen as {=L w E {Pran(u })}} when (w i) * and the empty set 0 otherwise which defines neighborhood function. Thus, 2 2/ Shattat Poa(u,1))
o Pa(u, 1), 2))(,,)) Pa Pu 2),... o () Pa A), is an AMP tuple (S3)
of a color atom (A3) 2 constant atoms (Al) and aggregation AMPs (S2), Hence, the color update function is strongly simulatable.
2. k- WL [Morris et al., 2019]: Let W -VG be the set of k-tuples of vertices for a given graph G. Then, k- WL can be written as de = HASH (C)....
where (s) HASH (1 / E (+))))) Both hash functions are function application AMPs (S4) and and c²-1 is a color atom AMP (S1). Here, encodes the j-neighborhood of the k-tuple This means that each C (s) corresponds to aggregation AMP (S2). Then, the combination into (s). C (s)) is a tuple of AMPs (S3). Hence, the color update functions is a AMP implying that k- WL is strongly simulatable.
3. 6-I- [Morris et al., 2020]: We only show this for 5-k- WL. as 5-k-LWL. is a special case obtained by removing elements from the color update function of 5-k-WL. Let W = (GG)* be the set of k-tuples of vertices for a given graph G. We use bold v to denote a k-tuple and a to denote a vertex. For j E [k]], the function o; w) returns the k-tuple obtained by replacing the j-th vertex of v by w. The function adj (v, w) returns 1 if the two vertices that distinguish the j-neighbors v and w are neighbors in G and 0 otherwise. Then,
6-k-WL can be written as cf+1
(ct, M (v)) with
M (v) -(f( (f(((crooo))) adj(v, ΦI (v)v) I w | Ev
H( (ol(v.)) adj(v. (x(v, w)) w v(Gi)))
Let j E [K] be arbitrary. Note, that adj(v, S, (v, w)) is an edge constant atom k(v k(v,oz(v,,) (A1) and that di (v.w)) is a color atom (A3) for object (y(V, w). Thus, (Saymre)) adj(v, (v, w))) is a tuple atom (A4). Furthermore, we can rewrite the aggre- gation by replacing (v, w) with w as {( (ch, k(v, w)) w NvGB where NV = (v,(v. w) w E V(G)). Thus, each {f (c) (vap) adj(v, "e (v), w V ff is an
aggregation AMP (S2) and M (v) is a tuple AMP (S3). Thus, the update rule of 8-k-WL is strongly simulatable.
*We think that there is a small typographical emorr in these functions signatures as defined by Sato et al. [2019]. There, they define them (,a(e, i): V x A (u() and Pa V x A Au(-}.
20

---

4. (k. S)-LWL and (k, SetS [Morris et al., 2022]: This algorithm is very similar to 6-K-LWL and we use the same definition of & as above. We prove this only for (k, s) 3\-LWL as (k, SeeSpNessss can be argued analogously. In what follows we use #com(G[v)) to denote the number of connected components in the graph induced by the k-tuple of nodes v of G i.e., the subgraph of G that contains only vertices from and all edges from E(G) incident to these vertices. For & 2 1 and 1 S 8 S k, let
V(G) { V* #com(Glv)) Ss).
Similarly to 8-k-LWI, (k, s)-LWI. assigns a color to k-tuples. However, (k, s\-LWI works on elements from V(G), Hence, W = V()) The update function can the be defined as:
s+1 = (c. M, (v))
with
Ma) (ff (v)=((((
w E ((u) and dv e v(G))
{{ (Coornmms www E ((v) and ou(v, E v(Ga)))
where vs is the i-th element of k-tuple the aggregation in all multisets. Let i E [k] then we define Ni(v))
Similar to above, we can rewrite
{ol(v, w)) w ([;) and (v, w)) E V(G) which allows us to rewrite the multisets as ( x MM... This implies that each the multisets is an aggregation AMP (S2) and that (v) is a tuple AMP (S3). With this it follows that the color update function is simulatable.
5. GSN-e and GSN-v [Bouritsas et al., 2022]: We only prove this for GSN-v as GSN-c can be argued similarly. Let W = VG).. The update function behind GNS-v is defined
h UP'+1 (Kg.
with
m M++1 (A (bi, Ki N. aY ew.,) luE (
In this definition UP*+1 is an arbitrary function approximator such as an MLP and M is neighborhood aggregation function meaning meaning an arbitrary function that operates on multisets. We can see M Up*+1 as function applications (S4). Additionally, = x and Cu,v are vectors encoding subgraph isomorphism counts with respect to some set of patterns. These isomorphism counts correspond to atom constants (A1): k(U, v), k(u, u) and k(u, v). As h2 and hi, are color atoms (A3) and Ca is constant atom (A1) it follows that (ht, h/ Mi =V eu,e) is tuple atom (A4) and {{ (ht hy a eu,v) xx,) u E (v))) } is aggregation AMP (S2). Applying the function M (S4) to this AMP yields m. m Thus, the update rule is strongly simulatable.
6. DS-WL [Bevilacqua et al., 2021]: For a given graph G and a policy ा that compute subgraphs define the set of objects W as the disjoint union of the vertices in each subgraph W ÜSE V(S). We identify each object from W by its original vertex v E V and subgraph S E (G) that created it. This means that c is the color of vertex u from subgraph S. Then, the update rule of DS- BS can be written
v.5 HASH (ci,s) C(.ss (x. E (v,
where (), ((, x E Nss
} is the set of all neighbors of vertex in subgraph S. Hence, {[ (['_. (x, 5) E (u, S))} is an aggregation AMP (S2) which implies that the update rule is strongly simulatable.
7. k-OSWL and k-OSANs [Qian et al., 2022]: We only argue the case of k-OSWL as the proof works similarly for k-OSANs. In what follows we use g E G3 to denote & tuple of vertices from V(G) corresponding to k-vertex induced subgraph of G. We use G5 to denote the set of all veveree induced subgraphs of G. The algorithm computes colors for each
21

---

combination of a vertex with vevertex induced subgraph combination i.e. W = V(G) x Gk. It uses the color update function:
Ci+1 o.
= RELABEL (C {1 u EE))).
Here, O is either (v) the neighborhood relation in the graph G, V(G) the set of all vertices, Since both neighborhood allows us to define corresponding neighborhood functions it follows that C. u E [}} is an aggregation AMP (S2) and thus that the color update function is strongly simulatable.
8. MNNN [Papp and Wattenhofer, 2022]: As Papp and Wattenhofer [2022] note, their approach is related ESAN [Bevilacqua et al., 2021]. For graph G with some set of marked nodes the following update rule that computes the colorings:
++1 UPDATE (h 1
with
a maGGRard (H 1 U (ar(w)) + AGGRmarked (H E ())
Where Nu and No are the neighborhood relations referring to marked (unmarked) neigh- bors in the subgraphs, respectively. Thus, {hū | E (WM(u)) B and ( | (N are aggregation AMPs (S2). We can model at, as a function o((x; v)) = AGGRR (x) markerr (y) with x = (hh v E Nas (w) and y = (h e E (u B- Hence, d' is function AMP (S4) applied to a tuple AMP (S3). Thus, the color update function is strongly simulatable.
9. GMP [Wijesinghe and Wang, 2022]: The color update function underlying GMP has the shape
m a AGGREGATE (H((),, I (()))) m AGGREGATE (H / E K
!+1 1 COMBINE (m(,,m)) Cy
Here, Avu E IR structural coefficients encoding local structures in the graph around U, Note that we can model AGGREGATE (ff Apu E (()))) then write m k(U, v) ht fmmi((( (k(u, v), ht)) where (1. y) = x. y. Hence, m is a function application (S4) to a tuple (S3) of a constant node specific value (A1) together and color (A3). Furthermore, m is an aggregation (S2) of tuples (A4) of a constant value (A1) combined with a color (A3). Thus, the color update function is strongly simulatable.
constant atom
(A1) k<.,, v). Thus,
10. Shortest Path Networks [Abboud al., 2022]: Let G FV be graph, v V vertex and i 2 an integer. We denote by (N) the i-hop shortest path neighborhood i.e., the set of all vertices that can be reached from in shortest path of length i. Then, the color update function of shortest path message passing graph neural networks (SP-MPNNs) are defined
++ = COM (ct, AGG, (ff u (EN((()))) ..... (AGG, (ff u (c)
where & 2 1 is an integer, COM is a combination function and AGG... are functions that map multisets of colors to single color. Let W = V. Obviously, COM and all AGG functions are function applications (S4). It is clear that cf, corresponds to color atom (A3). Next we investigate the term (4, AGG, (ffe u (N) where j [k.. In this term, {(c u E NV is the aggregation AMP (S2) of color atoms (A3). Thus, (ct, AGG, (ch u (
tuple AMP (S3). It follows that the color update functions of SP-MPNNs corresponds to AMP which implies that SP-MPNN can be strongly simulated.
11. Generalized Distance WL [Zhang et al., 2023]: Note that this generalizes shortest path networks. Let G = (V, E, F) be graph. Let de(..)) be an arbitrary distance metric i.e., function de x V - R.. The color update function of generalized distance Weisfeiler-
Leman (GD-WL) is defined cf+1 HASH (fl (do (u, v), ct))
VB). Let W = V. It
22

---

follows that Hf (ddc(,,), v),,,)) u V is an aggregation AMP (S2) that aggregates tuple atom (A4) (do(u, v). c built from a constant atom (A1) da v) and a color atom (A3)
dy As HASH corresponds to function application (S4) we conclude that GD-WI. is AMP
and can be strongly simulated.
D Proofs for Limits of Strong Simulation (Section 4)
D.I Cannot Simulate Nested Aggregation (Theorem 4.1 Part 1)
We prove the correctness of Theorem 4.1 for the nested aggregations. Theorem 4.1. Nested aggregations and non-pairwise message passing cannot be strongly simulated.
Proof. We define two relational structures X1, X2 that can be distinguished the first round of message passing with nested aggregations, but cannot be distinguished in the first round of WL when representing the relational structures as graphs. Consider the set of objects U = {z, a, b, c, d, h, h²3 with neighborhood functions:
Mi(a = (b = Mi(c) Mi = (x)
N2(x)) (1,
(h))) = (a,
Ns(h)) (c.d} d].
In the above definition, the neighborhood function returns the empty set for all other objects. Both relational structures will have the same objects and neighborhood functions but different initial features:
(a) (b) D.
[((c) = (d) = O.
Fx(x) = (1) Fi(N) =A,
F2(a) (2 D.
(b) = F2(c) = O. and
(2(x) = (2(h) (2( A.
We define the two relational structures as X, = (U,Ni, Fi) and X₂ = We define color update function with nested-aggregations over these relations structures:
F2).
+
HASH (c&, c e ((())) {f cf Na(z)) = N2()))
where ot is the color of object in iteration t. We use æı, 22 to denote the color ct for X1 and X2. respectively, By definition we know that
1 = HASH (4, 0, KHO.O,,,,
T2 HASH (A,, 0,
Obviously Wi TT. Suppose there exists structure-to-graph encoding R such that WL can distinguish the color of the vertex corresponding to object for the two graphs R(X,), R(X2). We use Tı, 72 to denote the color of vertex æ after one iteration of WL on R(X,), Since the color of x depends on a, b, d, we can assume that there are edges from these vertices to x in both graphs. Since R is structure-to- to-ghaph encoding makes use of the mappings Reragh and Riea- By definition of Rgraph it has no access to the features thus the graph created for X2 by Reraph are identical. Hence, the graphs R(X1) and R(X2) only differ by the features assigned to a, b, d. By definition of WI., the colors 71, only depend on the features of the neighbors of x and are independent from any other vertices (or adjacencies between other vertices). Let = .1..... Von be all neighbors of that not b, c, d. Note that the features of the vertices of Y is the same for
respectively.
23

---

both graphs as all vertices from Y are either not from U or they are assigned the same color by Fi and F2. We add the relational structure X; (for {1,2}) subscript the color notation to indicate where the color is originally coming from, e.g., c2 X2 is the initial color of vertex x in graph R(X1). By definition of WL it holds that:
71 = HASH (C2,x, H.xx 0 X1 xx, cx. U (( IvE
= HASH (c2,x,, xx, N. xx ca. H.,, (ye))).
As Reraph assigns the same features and all vertices of Y for the two graphs and Rea concate- nates the vertex features with the features from the structures, it follows that c,,, = c x, and H Hey.x, y Hf e EYY- As we intend to argue that there exists no R such that Ti T2 we intend to argue that
([ b. xx
cxx }3 1 fa, - xxxx
c.
By definition the color of a vertex v E b, c, in graph R(X;) (with E (1,2)) the color assigned to by (X:):
C. = concat(( graph (())).
We argue that all v E {a, c, d} have the same feature g() for all i E [1,2]. First, any two v, {a, b, c, d) that are part of the same set in N3 (fa, b), fc, d)) necessarily assigned the same feature as they are indistinguishable for geapph based on the input N2. Second, {a,b, c, d} that are not part of the same set in N3. (e.g.
for two v, can detect that they are part of different sets but cannot encode this into the vertex features. Any such encoding would treat the sets {a, b) and {c, d} differently which is possible since the function operates on (multi)sets and thus permutation equivariant. Together with the fact that Fi (a), (b),, Fi (c), (d)) (f F2()), F2 (b), (c), } it follows that 7 72- This con- tradicts the initial assumption and proves that no structure-to meneture-to-grahh to-graph encoding R exists that allows for strong simulation on X and X2. This proves the theorem.
a, c), Rgaph
D.2 Non-pairwise message passing cannot be simulated (Theorem 4.1 Part 2)
We prove the correctness of Theorem 4.1 for non-pairwise message passing-
Theorem 4.1. Nested aggregations and non-pairwise message passing cannot strongly simulated.
Proof. The proof is similar to the case of nested aggregation (Appendix D.1). We define two relational structures X1, X2 that can be distinguished in the first round of message passing with non- non-pairwise aggregations, but cannot be distinguished in the first round of WL. when representing the relational structures as graphs. Consider the of objects U {x, a, c, d3 with neighborhood functions:
- (a) (1) - (x).
N2(x)) (aa, b). (c,
In the above definition, the neighborhood function returns the empty set for all other objects. Both relational structures will have the same objects and neighborhood functions but different initial features:
(a) = (b) D (((c) F (d) O.
Fx(x) = A.
Pz(a) = (2(d) = D.
Fa(b) F2(c) O. and
F2(x) = AA.
24

---

We define the two relational structures as X1 (U.W1.NN. Fi) and X2 = (U, F2). We define a color update function with non nan-pair aggregations over these relational structures:
HASH (c,, c w E (G( |l (C c)) (z. Na(w)))),
where of is the color of object in iteration t. We use w1, m2 to denote the color d for X and X2. respectively. By definition we know that
11 HASH (A, D, ((,,))
72 = HASH (A, 0,
Obviously T1 # T2. Suppose there exists structure-to toe-tto--rrae to-graph encoding R such that WL can distinguish the color of the vertex corresponding to object for the two graphs R(X1), R(x2). We use T2 to denote the color of vertex æ after one iteration of WL on R(X1), R(X2) respectively. Since the color of x depends on a, b, c, we can assume that there are edges from these vertices to in both graphs. Since R is structure-to-gue -o-gaph and Rieu. By definition of Rgraph it has no access to the features thus the graph created for X1, X2 by R Rggaph are identical. Hence, the graphs R(X1) and 2(X2) only differ by the features assigned to a, c, d. By definition WL, the colors Ti, 72 only depend on the features of the neighbors of x and are independent from any other vertices (or adjacencies between other vertices). Let Y y1...... Mm same for
graph encoding it makes use of the mappings Ryrpph
be all neighbors of x that are not a, b, c, d. Note that the features of the vertices of both graphs as all vertices from Y are either not from U or they assigned the same color by Fi and F2. We add the relational structure X, (for E (1) as subscript to the color notation to indicate where the color is originally coming from, c.g., C2 x, is the initial color of vertex in graph R(X,). By definition of WL it holds that:
T1 HASH (c2.1,, Ul... & C.X. Cx U (l IVEY
HASH (c2,x,, Hca... C.x,, C..,, ex U H. (yE
Uf
As Rgraph assigns the same features to x and all vertices of for the two graphs and Reea concate- nate the vertex features with the features from the structures, it follows that cx,x, = d x2 and ( x. lv y = {f x yy B-- As we intend to argue that there exists no R such that T2 we intend to argue that
(c.... S.x ex Cdx,, L (C -o, Sxxx, C.xx,x..x, Co.x, Sd,x2 cdx,,,
By definition the color of vertex from a, c, d in graph X, from X1, X2 where F (v) the color assigned to u by R Rgmph Xx):
C, = concat( (Frrph. Fl(1)).
We prove the the two multisets of color equal by showing ca,x, C.,x,. Cx,, cd,x,' da,x, x²,x, and dx,x, xx This follows from the observation that two vertices VR(X,) and y RR(X,) are indistinguishable by Reraph if they are in the same position of tuple in N2. For example, both b and d are in position 2 of their respective tuple. This means that Rymph has to assign the same features both b and d implying F 1 (b) F Fgraph.2 (d). As (b) (2 it follows that Cxx, cd.x, An analogous argument allows us show the rest of the equalities which implies This contradicts the initial assumption and shows that no structure-to-gett to-graph encoding R exists that allows for strong simulation of non pairwise message passing on X1 and Xg. This proves the theorem.
E Proofs for Weak Simulation (Section 5)
E.1 Weak simulation of nested aggregations and non-pairwise message passing (Theorem 5.2)
We prove the correctness of Theorem 5.2.
Theorem 5.2. Nested aggregations and con-pairwise message passing can be weakly simulated with simulation factor 2.
25

---

For this we define the class of generalized augmented message passing (gAMP) color update functions. This class contains augmented message passing (AMP) but also non-pairwis message passing and nested aggregations.
F). F) be a relational structure. We call a color update function @ generalized augmented message passing (gAMP) if for all u E U and coloring c of X, it can recursively be defined as exactly one of the following five forms:
Definition E.1. (Generalized Augmented Message Passing. Let X = (U..N......N..
(WI) o(u, x)) vilu, (U. MM, c) where & is AMP and {M...... M,} is subset of (N!....,NNf only containing neighborhood functions N where E(V) = 1.
where E [A]. This is called (W2) o(u, x)) = H(co,..... Cam)) ) (ui....,,u, um) E NN(u) B non-pairwise message passing.
(W3) d(u, X. (a (U.M a neighborhood aggregation (S2), i E [[]] and (M1...., M,} is a subset of (Ni..... ..e) only containing neighborhood functions N where ((N) 1. This construction is called nested aggregation.
x E Mi( where & is AMP that contains
Φn,u, X, (.,.).,,,((.... (W5) o(u, x, c) = [(v(u, x)) where f maps colors to colors and ab is gAMP.
(W4) o(u, x, c) = (d) (u, c),, .)..,.,
where $1,.....0 On are gAMP.
We want to prove that we can weakly simulate all coloring algorithms in this class. For this we define a structure-to-gee -o-grapp encoding in Algorithm 6 for every color update function in this class. We use the same encoding function ENC as defined in Appendix C. We assume that if a feature function is called with an vertex, object or edge that is assigned no features, it returns a fixed default color. We prove that combining Algorithm with WL is at least as expressive as the corresponding non-standard message passing algorithm.
Proof. (Theorem 5.2) This proof works similarly to the proof of Theorem 3.5. We prove weak simulatability for (= 2. Let ø be an arbitrary generalized augmented message passing algorithm. We consider two arbitrary relational structures from the domain of ø, say X = and X"
F) F"). Let E,, Fi) = R(X) and (V2, Ez, F2) = R(X'). We prove (1) that gAME, is structure-to-grapt encoding that runs in O(Ta(UU))) (2) for every t > 0 the coloring WL WLL"((I(X)) Filv;) U WLL"(R((") F2lv;) gAME,(X) refines the coloring (XX, o (X', (.).
,NY.....
We begin by proving (I). Observe that Algorithm 6 can be split into Rgmph and Biea as required by the definition of structure-to tancture-to-graph -o-grapp encoding. Furthermore, Algorithm 6 first iterates through all gAMPs in ø and all possible objects that are relevant to these gAMPS. Hence, Algorithm 6 runs in the same runtime as one iteration of gAMP which in (FT((())))
Next, we prove (2). We use of T. and ch of to denote the colors assigned to vertex / object u,r (UUU") in iteration by WI. on R(X), R( R(X') or é on X, X', respectively. Let u. r E (UUU") be arbitrary objects/ / vertices. We show by induction that if WL. distinguish and r in iteration 2t then é cannot distinguish them in iteration t. Formally, we show that T 2t ct &
which implies that WL" (R((), Filu, ) (WL"((((")) F2lv;) refines o' (X, Flo as (U OŪ') C (V1 U V2) (by Algorithm 5).
Algorithm 6 starts by replacing all function applications (S4), (W5) by the identity function and flattens all tuples (A4), (S3), (W4). Recall that this transformation is either injective or bijective. By applying Lemma C. they do not influence the strong simulation property and thus also do not influence the weak simulation property. From now on we assume that Φ = (ØI..... On) such that all 2j with j E [n] are either (WI) 1) (which means they are one of (AI), (A2) (A3), (S2)), (W2), or (W3) and if they are an atom, then the first and third function argument are identical. We use w to denote the object the gAMP is defined to update. Algorithm 3 iterates through all Φ1 $1...., On and encodes them in the graph.
We show that = = x = ch = cQ. For this, we assume that _ = n0 As the initial colors correspond to vertex or object features and Algorithm encodes the object features in the vertex features it follows that e) = o..
Base case:
26

---

Algorithm 5 Rymph for generalized augmented message encoding
Input: relational structure X = NU. Na)
without features, gAMP color update function ø
that has the shape (#1, ................................ On.) where each @s with E [[x] is one of (A1), (A2), (A3), (S2), (W2) or (W3).
Output: graph G (V, F., grrphh)
V W F. := 0
I g'gpph empty features
for i E [r-]]] do
if o; (A1), (A2) or (A3) then
for u E U do
(V, E, Fgraph == Algorithm 1( (V, F....gn graphh), u, u, 0,
end for
else if di is (S2) which aggregates on neighhorhood. N then
(V. F. F graphh) := Algorithm 2(0;, (V, E, F guuhh: (U, i,
else if Φ; is (W2) then
1" de has the shape
cm 1 um) E [NG(u)] where j E [k]
for u E U do
for (wI, MU...... Um) (N) do
V VU (Uut....,amm))
E EU (( .... u)}
F F(((EEmnnMa))
ENC(empty features, 1,
F Fu
u)
ENC(empty features, 0,
for r E [m] do
E = E {(up, Uus.......................... Mmm F(ur, Uas Umm.....mm : (NC(empyy features, i, 0,
end for end for end for
else if Φ; is (W3) then 1' di has shape kv(x, (I.. Replace function applications (S4) in de by the identity function, i.e., ((p) becomes sp
| (N) where AMP
Flatten tuples (A4), (S3) in tb except outermost, i.e., (P..,, pr),... becomes
Pl..... ..).....
1" vp has shape (V1...., Un) where each Uh with E [n] is one of (A!), (A2), (A3) or (S2) (V, E, F Feraph) == Algorithm 3(t,, (V, E, graph), (U, (U. i,),
for u E U do
for x E M, (u) do u() F(x, u) ENC(empty features, i, 1,
E
end for end for
end if end for
return (V, E, Fgraph)
Induction hypothesis: We assume that n = n, 3 c/ = cx holds for all f S T.
Induction step: We show that To 2(T+1) TT 2(T+1)
c
T+1 We assume 2(T+))
πr 2(T+1) which equivalent to n
27 x 2T We prove for an arbitrary gAMP from $1...., On.
that it returns the same result for and which implies cT T- = cT We do case distinction on type of this gAMP. Note that gAMP and AMP the object edge features are referred to us F(.) whereas in the relational structures X and X' they are denoted as F(-) and F'(.). Below, when we argue that two AMP constructions are equal and use the F(.) notation and neglect F'(-) for the sake of simplicity.
27

---

Algorithm 6 Generalized augmented message encoding (gAME) Input:
relational structure X (U,NI, F), gAMP color update function ø. Output: graph G = EV)
Replace function applications (W5), (S4) in ø by the identity function, i.e., f(() becomes Ø. Flatten all (W4), (A4). (S3) constructions & except the outermost, i.e., (..., (0.....,.)).... becomes (...,01,-- -.,,-.., .n)...).
l" @ has the shape (#), .ol...... 0n) where each @ with E [m] one of (A1), (A2), (A3), (S2), (W2)
or (W3) *
1" Rgraph" "/
(V, E, grapp) == Algorithm S((U,N
/" Rieat"
F' empty features
for v E do
F'(v)= == concat (F(v), Fgraph(())
end for
for E E do
(e(e) == concat (F()), ('gaph(() (e))
end for return FV
o, (r, Then, o, is one of (A1), (A2), (A3), (S2). Observe that, then Algorithm 6 performs the same operations as Algorithm 4: for atoms (A1), (A2), (A3) it instantiates Algorithm and for (S2) it instantiates Algorithm 2. We apply the induction step of the proof of Theorem 3.5 in slightly altered form: instead of proving म. =T++1 x, + cf'+1 = cf we instead prove n. -?7++1 T. + c = c.. Note, that by the induction hypothesis we already know the stronger fact -
(WI)
n. 27'42 However, we only use the fact n 2T+ π 2T+1 so that we can later apply this argument in a context where only the weaker x 2,27+1 n 222 holds. We obtain a proof for n 21+ x 2TT+1 = c c, from the induction step in the proof of Theorem 3.5 by replacing x." and n. T+1 by n. and 27+1
respectively. Thus, we know that for AMP dh holds that &s (u, X, c.)
(W2)
(fi...., rm) E (N)))) From " 22 = +2 +2 it follows that there exists bijective function or No(u) + Na(r) that maps vertices assigned the same color by 22T+1 to another. Note, that NN is the set of all neighboring vertices of vertex in the graph generated from X or X'. By the construction of the edge features, it follows that a maps vertices from {"li,....M.. (ui,..., Mm) E [N) to (Fr........ (f1....,
I.. (uI...., um) E (n) 1
Fin) E (r(r)) Let 3 be the restriction of the function a to these two sets as its domain and image, respectively. This implies that
2T+1 Pugg...m (ui..... um) E NgGWw
{f - 2T+1
TT (FI...., E N
Let fu (ui....,, um) NN(())3 be arbitrary with x "u...... Then, call ((x) = Tri.....m Note that all neighbors that send messages to x are U1 Mmm-
Similarly, all neighbors of (zx) that send messages to ((x) are Tı, fi,...,, Tm- Since n 27 + (ri,..., mapping vertices assigned the same color by n² to each other. Note for every i [m] the edge connecting u; to x is labeled with and the same holds for and 3(x). Thus, 7(4,) = r; which implies (ui"'
2TT1 it holds that there exists a bijective function ((x): (ur....,
"B(a)
From the induction hypothesis it holds that (cT T (cT of ). From the fact that /3 is a bijection and by iterating over all possible vertices for x be we obtain
22') = (r7",... r.)
. ).
((CTT (c ... ......,.)) Fom) (u.,..., um) E N2( ([ (F, 1. ( (N,))))
28

---

(W3) (o"
1 (((x NNj(r}} where I AMP, X' MIM,,.,,M,, and all neighborhoods of X' have f(-)=11. =1 We use the function defined above. By definition all vertices from (N(u)) and (r) are connected to u and by an edge with special edge label encoding j. Thus, there exists a restriction from a bijective a to a bijective 3 (w) + (r) such that for every E .N5(u) it holds 2T++1 Next, we can apply the above induction step proof for gAMP that that +1 xx -(x))
correspond AMP (WI). From this proof follows that for every x E (Ng(u) it holds that ( ) ((3(z),, X', X','") c."). Together with the fact that is bijective we obtain that
(1) X² eT) NG(w (0,xx, 2 (gGr))
which contradicts the initial assumption.
This concludes the proof.
E.2 List of Weakly Simulatable Algorithms (Corollary 5.3)
Next, we leverage Theorem 5.2 to prove Corollary 5.3.
Corollary E.2. The following GNNs and variants of WL can be weakly simulated:
1. Message Passing Simplicial Networks [Bodnar et al., 2021b]
CW Networks [Bodnar al., 2021a]
3. DSS [Bevilacqua et al., 2021]
K-hop message passing and KP-GNNs [Feng et al., 2022]
Proof. Note that this has already been proven for Message Passing Simplicial Networks and CW Networks in Theorem F.I. We start by proving the corollary for DSS [Bevilacqua al., 2021] by showing that its color update rule performs gAMP. We reuse the notation from the proof of Corollary 3.6. The update rule for DSS-WL can be written as
HASH ch.s, Hics l Ns(u)) C. Ho.H | E No(u))
where (U) the set of all neighbors of vertex v in subgraph S, NG)) is the set of all neighbors of v in the original graph, and C. contains the colors of across different subgraphs
Ct = f ct,s S E (G) and E V(S)))
We define the set of objects W as the disjoint union of all vertices in subgraphs W = Üseexcy V(S) and identify each object from W by its original vertex and the subgraph it created. The update- rule applies HASH function (W5) to a tuple (W4) of other gAMPs. The first element of the tuple is c/ which is a color atom (A3). The second element is an aggregation over neighbors (S2), The third element can also be thought an aggregation over neighbors (S2) C ((ct.s) S' E (T) and v E V(S))) = {( S E (2 (1, S)} where (2, S) {S' S E (G) and u E V(S)). Finally, the fourth element of the tuple is a nested aggregation (W3) that aggregates over the AMP defined the previous sentence (with x instead of v) for all E Na(v). Thus, the color update function performs gAMP and DSS can be weakly simulated.
'There some more subtlety to this. The notation W's implies separate neighborhood function NVs for each subgraph which would give an unbounded number different neighborhood functions which does not directly work with our definitions. Instead, we need to create a new neighborhood function AG ((v, s)) {o x (v) The same holds for the following definition of N''.
29

---

Next, we prove the corollary for KP-GNNS [Feng et al., 2022], K K-hop message passing [Feng et al., 2022] will follow as a special case of this. The color update function of KP-GNNs is defined as
1+1,k my
MES normal (H Env)
Chit (
S(C
S(G v.G) = EMB( Ck)),
h UPD m.t.A 1/be 1b):
h++1 COMBINE' (H 1.,.....,KKK
Here, t E (gd, spd} with gd graph diffusion and spd = shortest path distance. The set Qtied contains all nodes from (G) that can be reached within k-steps of random walk diffusion steps from v. The set gh contains all nodes from V(G) whose shortest-path to node v is exactly
Let W V(G) U fox I & E V(G), [K]] be set of objects with associated features F. We define three neighborhood functions N2,
1. (v) {uk & [K]].
2. (2(w)) {0].
3. Na(vx) = Qti,.-
For all other vertices the neighborhood functions return the empty set. We prove that h4t1 performs gAMP it inside out, starting with m lllkk We represent m as AMP 6(0,, (W, N2 F),FF) 3 Let p(u; My u, h() = (Mi, Cwrz) where Cuvy is an edge con- stant depending on u, ug. By definition p an atom that constructed by combining color atom
prove
(A3) with constant atom (A1) into tuple atom (A4). Note that MES
{[(Mg Ewe)
(2te3) is AMP that applies the function MES nommlll (S4) to an AMP that aggregates (S2) the atom p(u, My, u, hl)) over all u E Na(ux). Next, f(G can be seen as constant atom (AI) k(vn, vk) f(Gbt)) Let y,, be two AMPs, then we define the addition AMP as f+ ((v9,)) Ø)) = 4p + &b Hence, we can represent mft as an AMP
o(vx, Ng. = f+ (MES
(H(1)) uuE otd f s(ott)))
Next, we argue that I. AMP represented as spll, NW, Observe, that we can write to as a function application of UPD1, to a tuple
(Φ(v), (W.Ng,NN2. F), (h', x E Ne(ew)))
where (h', x N2((x) is AMP (S2) that aggregates the only N2 neighbor. As N2(u) {v} holds that ylou, (W, N2, F) corresponds to 1,11, Finally, we argue that h is gAMP (e, NW.NG,N.... F). We write vp as a function application (W5) of COMBINE' to the nested aggregation (W3)
Hl h., W.NN..NG.AG) E (N)
Thus, (b (W, W1 F) corresponds to h4+1 As h++1 is gAMP it follows by Theorem 5.2 that KP-GNN can be weakly simulated.
We obtain proof that K K-hop message passing [Feng et al., 2022] can be weakly simulated special case of the above proof by removing the term ((C from the definition of ml|1.k
"Note that atoms, AMP and gAMP are generally defined over all objects. However, by construction this AMP will only be used to aggregate colors of objects vs with E VGG), & E [K]. Thus, we denote it only for these objects despite it being defined over all objects. We the similar simplifications throughout this proof.
30

---

F Handcrafted Efficient Graph Transformations
F1 CWN: Efficient Weak Simulation of CW Networks
We define a transformation CWN that allows for more efficient weak simulation of CW Networks. We prove the following theorem:
Theorem F.1. Message Passing Simplicial Networks [Bodnar et al., 202 and CW Networks [Bodnar et al., 202 can be weakly simulated by CWN with a simulation factor of 2 such that the number of vertices is equal the number of cells.
Proof. We prove this theorem for CW Networks as they a generalization of Message Passing Simplicial Networks. We begin with definitions required for the proof. regular cell complexes consists of different cells each with a fixed dimension. We have a boundary relation < given on the cells. For a cell we call B(ar) {- T σ) its boundary adjacent cells and C(rr
{T < 7 its co-boundary adjacent cells. We define C(), = C. CC For a cell a we call (o) {T] 38 such that σ < 6 and T < 63 its upper adjacent cells. For color cf at iteration t we use the notation (0) to denote the color of all objects in F(o) at iteration t meaning (x())= = fc x E F(r... For given cell a in a regular cell complex X a CW Network computes
its color in iteration t + 1 with the color update function
(1)))((),c((o))
UPD1 (a, x²) HASH
where (o) performs the non pairwise message passing
(o)=
= ((((((. <g)) l E N+(o) and ó E C(a,11)
is straightforward to show that the color update function UPD, performs generalized augmented message passing and that CWN can thus be weakly simulated with simulation factor of However, for this Algorithm 6 would generate more vertices than cells. Instead, we present a hand-crafted graph transformation that requires no additional vertices. We define color update function that replaces the non pairwise message passing into separate pairwise message aggregations:
c UUDD (o,X,c') HASH TT (x (0), (o)) Nix, ,i,
where
(a = ( ENN(O)) and d E Cla, p)}.
We require the dimension of cells to be encoded in the initial coloring, Note that UPD2 performs augmented message passing: T is a color atom (A3) and (o), ,x (a), Tx, (a) correspond to a
AMPs (S2) that aggregates a color over a neighborhood from N4 (o). Hence, we can strongly simulate UPD2 by Theorem 3.5. Next, we show that for every 2 0 the coloring produced in iteration 2/ of UPD2 refines the coloring produced by / iterations of UPD, (CWN). Combining this with the fact that we can strongly simulated UPD₂ means that the coloring produced by 2/ iterations of strongly simulating UPD, refines the coloring from iterations of CWN. This proves that we can weakly simulated CWN with simulation factor of 2. We use CWN to denote the transformation AMELPD,
Let / 2 0 be an integer. Let X, X' be two arbitrary regular cell complexes. Let a, v be two arbitrary cells from these cell complexes. We show by induction on / that if UPD, is unable distinguish from # in iteration 21, then UPD, is unable to distinguish cell a from cell v in iteration L. We use ct to denote the color assigned to cell a by the coloring from iteration of UPD1. We use o to denote the color assigned to vertex a in from iteration of UPD,. To prove the theorem, we show that ?t 2 + cr ct The base case (t 0) holds trivially, as the features of the cells are encoded in the vertex features. Next, we assume the statement holds for t = T and prove that it holds
for T 1. This means assume no 2(T+1) my
2(T+1) and have to show:
T+1 T (2,,
1
(())) o++
2(T+1) From ne मy hypothesis it then follows that of of. From no
2(T+1) it follows that क
+2 π
2T+2 and n n 2T By the induction +1
n +2 it follows that mB(o)2T+1
31

---

Figure 4: A graph (left) transformed into bags of subgraphs (center) by policy and the result of applying DSS to the graph and bags of subgraphs (right), Yellow vertices represent the original graph and red vertices the subgraphs.
( Hence, there exists a bijective function a B(()) - BB)) that maps vertices with the same color assigned by 2TT+1 to another, meaning for all x E (()) it holds that x 2T+ 2T and Tzz - a(x)' The existence of a and the induction hypothesis imply that cf(lo) (v). Similarly, there exist a function B (o) + (v) that bijectively map vertices assigned the same color by n2T+1 to another. Thus, for every æ E (aa(a)) it holds that n = 2T+1 and n- = 27 *f(z)
[a(a)
"(aa)"
Furthermore, it holds that for every x E (o) there exists a bijective function 7/ B(x) + ((a(x)) that maps cells another that get assigned the same color by 2²T Combining this yields
T T "y H y B(x), (n) = [1 ((==²
27 "y 2T y B(x), (n())
By construction each y has a higher dimension than æ. This is encoded in the features, thus it follows that
(TT2T mT y B(x), E No = (T 2T my
1 E E
From the induction hypothesis it follows that
{{ (c +t) y B(x), E Nn(o)}] H| (ch o)) B(x), Nn
(1)
We prove that this is equivalent to showing that of (o) of (v). For this, we show that for every cell p it holds that
0(,,0 μ B(6), 6 Nx(()) 1 ((,,0) μ Nt(p) and d e C(p,
First, we show that the set on the left is a subset of the set on the right. Suppose an arbitrary element (14, 8) with μ E B(8) and 8 E (2) from the left set. Note that l B(5) implies μ Furthermore, 8 E (p) means, p < Thus, 8 E C(p. p). Finally, this also implies that μ E (T(). Hence, (p, 5) is an element of the right set. Next, we show that the set on the right is a subset of the left set. Let (),6) with μ E Ny(p) and 8 E C(p, ()) be arbitrary element from the set on the right. From d E C(p, J it follows that p < 8 and μ < By the definition B, follows that p B(() and E B()). It remains to show that 5 E (n) meaning we need to show that E {y x E N+ and y C(6,))) By definition we know that μ E (8) and that E C(8, μ)) Hence, 8 e (p). This implies that (n, 5) is element of the set the left. meaning that the set on the right is subset of the set on the left. Thus, the two sets are equal. We use this to rewrite Equation I into
(C= ()) I E (a( and y E C(a, x)} (( | E Ny(v) and y C(v, x)
Hence, ()) cf (v). This concludes the proof.
F22 DSS: Weakly Simulating DSS Efficiently
Recall that the color update function of DSS WI. defined as
S HASH Co.s. fffeft e Ns(v)) Cr ( 1 [cENc()))
32

---

where Ns(v) is the set of all neighbors of vertex v in subgraph S, and C contains the colors of across different subgraphs
C% = 1l H, | S (G)) and E V(S))
Let VG).. According to the graph transformation from Algorithm 6 with simulation factor we would create separate helper vertex for each vertex from X = {x E (G(()) where each I X is connected to all instances of æ across the different subgraphs.
straightforward way to do this, is to add an additional copy of the original graph. A drawback of the graph transformation from Algorithm 6 that because of C.¹- = H[ (i,s S' E (T) and v E (S we need to create edges between every copy of among all subgraphs, that means we create up to [V] (T) extra edges. We can remedy this by adding edges between v in the original graph and all instances of v in the other subgraphs. Thus, it suffices to create at most [E(G)] + [V) [T) edges. Similarly, for every u V(G' and all subgraphs S E T (G) containing e we need to add edges the corresponding helper node for all neighbors (v(v). Interestingly, it is not necessary to add these edges and instead is possible to rely on the edges generated by adding an additional copy of the original graph. However, this means that for a vertex v it takes three steps obtain the information {[C% a E Nc(e)): B. Thus, this comes the cost of increasing the simulation factor to 3. We call the resulting graph transformation DSS. Figure 4 shows an example of DSS.
Definition F.2 (DSS). Given a graph G and policy x we define G = (V Ex, Xx, Yx) to be the graph obtained by DSS. Where
V Ü V(S),
SET(G)UG
F =
U SET(G)UG
F(S) ((vG, IS E (G) and o E V(S)).
For unlabeled graphs we introduce a vertex feature that encodes whether was created from a subgraph S (G) or was created from G. For labeled graphs extend the features correspondingly. We add edge features that allow us to distinguish whether an edge was created due from ES)) or from {(v,, ]s} S E TTG) and V(S)}.
We show that for arbitrary policies and graphs WL on the transformed graphs is at least as expressive as DSS-WL on the original graphs.
Theorem F.3. DSS weakly simulates DSS- WL with simulation factor of 3.
Proof. Let G and H be two graphs and policy. We use Ti.s to denote the coloring of vertex us obtained by iteration of WL on Gx Hy, and Th. to denote the color in iteration of WL of vertex u that was created from the original graph (respectively Tf. T(,H). We use et,s to denote the color of vertex in subgraph S obtained in the t-th iteration of WL. We prove that for every t 2 it holds that
Ve, w V(G), E (G)) T..9 TW.T + C C
by induction on the iteration of DSS-WL.
Base case: All vertices Us E V(G wr E ((H²) are assigned the same initial color (except the indicator that they were created from subgraph) their counterpart from DSS-WL. Thus from Th.s = T it follows that ci = &..r-
Induction hypothesis: We assume the statement holds for all < n where an arbitrary non- negative integer.
Induction step: Let E V(G), E V(H),S E (G), T (H)). We assume that 3(n+1) a+1 3(n+1) holds and want to show c, -
T..5
T
It is equivalent to the assumption that 7 T..T
3n+3 +-
which also implies 13. = 33 w We need to show that
1. ch c
33

---

2. L (&r u Ez (T and
3. C = and fCCT E No(v) = H E NN(ww)]
From the induction hypothesis and Jn 73n 11 m. immediately follows that co. = C..T
We want to show that f( (s(vv) = (//r/ I From TH.S -3+ 33 it follows that there exists a bijection 8 Naa (vs) + NN,, (WT) where for every I E Na. (ws) it 3n+2 which implies T = "((z)' Additionally, all neighbors of us are from the subgraph S or the original graph G and the vertex features allow us to distinguish between those two types. Thus, 3 maps vertices from V(S) to vertices from V(T). ). Note that these are exactly the vertices whose colors are in {I (c x E (w)) H[ E (N() Thus, by combining this with the induction hypothesis we obtain that (C T ( = Hc I E (rw
holds that Tx 73n++2 = B(x))
We want to show that C = C. We use the function B defined the previous paragraph. Due to the vertex features we know that 3 must map lg to wH as there exists only one neighbor with the "created from the original graph" feature among us" and wy's neighbors. Hence, T. 33++2 = -3342
which implies 7-3x++1 neighbors of og to neighbors of we such that they are assigned the same color by T The vertex to and we in the copy of H have two types of neighbors: neighbors (G (w) from the original graph and copies of v. w over different subgraphs. By the vertex features we can distinguish these two types of neighbors. Thus, y maps copies of v from the different subgraphs to copies of w over different subgraphs. As these vertices correspond to S and w, I" for all S' E (G),, T" E (G), we can combine this with the induction hypothesis to obtain that C (e.ss S E (G) and E V(S')] =f ff T E TT (H) and w E V(T')) C
=H -3++1 This implies that there exists a bijective function y mapping
Finally, we want to show ((T IE NEG - (|CT 1 E (H Since the copy of and w created from the original graph can be uniquely identified by its vertex feature from NG, (H) (w) know that maps these two vertices together and thus that - 33n+2 T..H Hence, there exists bijective function a NN(()) - (w))w) such that for every neighbor x No(()) holds that 33++1 1
G, H We want to show that for every such neighbor E Na(u) holds that CT Ca(ay
Let be one such vertex. As "2 7 73++1
use the same argument in the previous paragraph to obtain that CT Ca(u). This concludes the proof of the induction hypothesis and
(=)
shows that the theorem holds.
F33 Strong Simulation of K-hop GNNs and KP-GNNs
We prove the following Theorem: Theorem F44 K-hop message passing and KP-GNNs [Feng et al., 2022] can be strongly simulated.
We prove the theorem only for KP-GNN: as K-hop message passing is special case of KP-GNNs. In the proof we define a new message passing algorithm we call simple KP-GNN (sKP-GNN). We prove that (1) sKP-GNNs strongly simulatable. The theorem then follows from the combination of (1) and (2). We begin with the definition of sKP-GNN.
expressives as KP-GNNs in every iteration; and (2) that sKP-GNN is
Definition F.5. (sKP-GNN) The color update function of sKP-GNNs is defined as
m MES normal (M ewr) u Q. + s(G
f(G EMB CEMB(EE(QU) (E(Q Ck
1+1, = JPD
m m
1+1
441 COMBINE' (1141,1
B4+1KK)
Note that sKP-GNN only differs from KP-GNN by the definition of h1+1
34

---

Proof. The proof reuses large parts the proof that KP-GNNs can be weakly simulated (Theorem 5.3). As sKP-GNN only differs from KP-GNN in the definition of ht+ follows from the proof that h,+1k AMP for every E [K]. Then, h is AMP that applies the function COMBINE' (S4) to sKP-GNN: A+ COMBINE' (K, h,t,,, and
KP-GNN: 16t1 COMBINE' ((( k == 1, 1.,...... K K})-
It is important to note that this transformation from rested-aggregation tuple is only possible because there is a natural order on the multisets aggregated (the hop size k). We prove that sKP-GNN as expressive KP-GNN in every iteration.
Lemma E.6. Suppose both sKP-GNN and KP-GNN use injective COMBINE' function. Then, for every graph G (V, E, F) and integer | 2 it holds that the coloring sKP-GNN' (G, Flv) refines the coloring KP-GNN (G, Flv).
Proof. Let G = E, and G' = (V",'" F") be two graphs, v, w E (VUV), and 2 0, K 2 1 be integers. We furthermore assume that the COMBINE function is injective. We prove that if
COMBINE' (1 ,..., k
COMBINE' (h 1...,,yy (1.K)
(3)
then
COMBINE' (H k 1.2..... KH) COMBINE' (HE k 1,2..... KH).
(4)
From Equation 3 and the assumption that the COMBINE function is injective it follows that k)
(h--111 k) (h---
Thus, for every E [K] it holds that 1 N N1t1,, This implies Equation 4.
Lemma F.7. sKP-GNN can be strongly simulated.
a tuple (S3) built from the AMPs 1,41,11 ,...,, M441K From Theorem 3.5 it follows that sKP-GNN can be strongly simulated.
Proof. (Theorem F.4) The theorem follows from Lemma F.6 and Lemma F.7.
G Intuition for CWN and CWN
Figure 5: Left: graph. Center: regular cell complex built from the graph through a graph-to-struetie encoding [Bodnar al., 2021a]. Vertices correspond to O-dimensional cells, edges to I-dimensional cells yellow) and induced cycles to 2-dimensional cells blue Right: a graph created by structure- to-graph encoding the regular cell complex to a graph. Vertices corresponds to cells as indicated by color.
CW Networks [Bodnar al., a, CWN] perform message passing on topological structures called regular cell complexes. A regular cell complex is built out of individual cells of some dimension.
35

---

Similar to message passing on graphs, CWN computes a representation (or color) for each cell by aggregating from the neighboring cells. To apply CWNs to graphs, a regular cell complex has be constructed from graph (see Figure 5), we call this process graph-to-structurg encoding. For this vertices are transformed into O-dimensional cells and edges into I-dimensional cells. In this process additional structures such as (induced) cycles or cliques can also be lifted to cells to improve the expressiveness and connectivity in the structure. In the experiments we use lifting map that lifts induced cycles of length at most 6 to cells. Figure 5 shows how a regular cell complex is transformed to graph and shows how our structure-to to -o-grrpph encoding CWN transforms the complex back to graph. Note that in our implementation of CWN we use undirected instead of directed for the sake of simplicity. When transforming cell to vertex, we set the vertex features to the most common feature of the vertices making the cell for each feature. For example, a cell that corresponds to a cycle v w, p is transformed a vertex whose features are the most common of the features of t; w, p. Similarly, the features of edges connecting cells are the most common of the edge features between the vertices making up the cells.
H More Details about the Experiments
We provide further details about our experiments. In Section H.1 we elaborate on our setup and in Section H.2 we present more details on the results from the main paper: In Section H.3 we present an additional evaluation of transformation and training speed. The code for experiments can be found at https githut..hhhh.. hetp/ocatias//nn Swwps/GNN-SSSSSiiiiii.i Simulation.
H.1 Setup
All models are implemented in Pytorch Geometric [Fey and Lenssen, 2019]. We use WandB [Biewald, 2020] to track our experiments. Unfortunately, CWN requires an old version of Py Torchh [Paszke et al., 2019] meaning that we have to train on older GPUs. CWN training and all speed evaluations are performed on an an NVIDIA GeForce GTX 1080 GPU. All other experiments are performed on NVIDIA GeForce RTX 3080 GPUs.
Type Pooling. In our transformations DSS and CWN vertices get assigned additional features that encode the type of vertex. In CWN, these features encode whether the cell was built from vertex, edge or cycle. In DSS, these features encode whether vertex is part of the original graph or in subgraph. Inspired by pooling operation by Bodnar et al. [2021a] we propose type pooling. The idea is that vertices with different types contain different information and have varying importance. Thus, instead of pooling all vertices in a graph, we instead pool all vertices of a type. To get single output for the entire graph, we then apply multilayer perceptron with ReLU activation function to each pooled vector and then sum the results. Let POOL be a pooling operation such as Σ. Let T be the set of types and let H, with i. E 7 be the multiset of all representations of vertices of type 1,, and MIP, be multilayer perceptron with activation function. Then, type pooling computes
Type-Pook Pool
Σ MLP, (H.OL.(H)).
We use type pooling for all combinations of an MPNN plus DS, DSS and CWN. Note that for DS all nodes have just one type.
Hyperparameter Tuning. Table contains all hyperparameter grids for the real life tasks. During preliminary experiments we found that it is crucial to tune the pooling operation and number of layers to achieve strong results. For DS(S) we do not tune the pooling function the code provided by Bevilacqua et al. [2021] does not directly support this. Since CWN is very slow, we use a smaller hyperparameter grid, containing superset of the hyperparameters used by Bodnar et al. [2021a].
Setup Real-Life Datasets. For all real-life datasets we tune the hyperparameters on the validation set and evaluate the best hyperparameters on the test set 10 times. We report the average and standard deviation of the metric that is typically used on the given dataset. For all OGB datasets, we train with a batch size of 32 for 100 epochs with fixed learning rate to allow for fast training of many models. For ZINC we train as described by Bevilacqua al. [2021], Bodnar et al. [2021a] and Dwivedi et al.
36

---

Table 3: Hyperparameter grid used for the real life datasets. The learning rate is only tuned on OGB tasks. On ZINC all models used the same initial learning rate that decays over time.
MODEL
GIN, GCN
DSS, DS
CIN ON OGB
CIN ON ZINC
PARAMETERS
EMBEDDING DIMENSION
64, 256 I.....
64, 256
64, 256
64, 256
NUMBER OF LAYERS
1..... 5
1,2,3
3,4.5
LEARNING RATE
10-3,10 10-4
10 10-3,10-1
10 10 10-"11011
10-3
POOLING OPERATION
MEAN
SUM, MEAN
SUM, MEAN
DROPOUT RATE
0.5
0.5
[2023] i.c., for up to 500 epochs with a batch size of 128 with an initial learning rate of 10-3 that reduces by factor of 0.5 every time the validation result has not improved for 20 epochs. If the learning rate dips below 10 the training stops.
Setup CSL. For the synthetic CSL dataset, we only evaluate GIN plus the graph transformations and compare the results reported by Bevilacqua et al. [2021] and Bodnar et [2021a]. We perform 10-fold cross validation on this dataset. For all models with graph transformations we replicate the hyperparameters used by the corresponding non-standard message passing algorithms described in the original papers. For GIN, we tune hyperparameters as described for real-life datasets.
H.2 Results on Real-Life Datasets
Tables 4 and 5 show the prediction quality of models all real-life datasets.
Table 4: Bold results are better than the corresponding message passing baseline, red results are graph transformation based methods that are better than the corresponding non-standard message passing variation. + means lower is better. 1 means higher is better.
DATA SET J MODEL
MOLHIV ROC-AUC f
MOLTOX21 ROC-AUC t
MOLESOL
ZINC
RSMSE
MAE |
GIN
1.0
76.1 + 0.5
0.946 + 0.086
0.306 + 0.035
GCN
1.0
74.9 0.6
0.928 0.049
0.456 + 0.021
MLP
72.2
0.7
1.128
1.44 0.001
DS
1.4
0.6
0.986 0.051
0.161 1 0.008
DS + GIN
1.2
0.6
0.924
0.143 1 0.008
DS + GCN
7.8
7.66
0
0.285 + 0.044
DS MLP
6.1
7.8
1.281 0.002
DSS
1.3
1.00
0.864
0.105 + 0.005
DSS GIN
1.3
7.71
0.853
0.149 = 0.008
DSS + GCN
2.1
7.7
0.868
0.221 + 0.028
DSS MLP
7.89
0.5
1.272
1.283 = 0.006
CWN
1..6
0.9
L117
0.13 0.003
CWN + GIN
1.54
7.7
0.958 +: 0.021
0.137 + 0.007
CWN + GCN
7.01
0.9
0.933 0.036
0.155 0.013
CWN + MLP
0.8
0.5
1.217 0.032
1.045 - 0.006
H.3 Speed Evaluation
Setup. We evaluate the preprocessing and training speed on ZINC for GIN and our graph transfor- mations against DS(S) and CWN. We select the hyperparameters for all GNNs such that they all have roughly 8 10 trainable parameters. measurement after the graphs have been loaded into memory and stop before we store the final objects. For our graph transformations, this measures how long it takes to run graph transformations, For CWN, this measures how long it takes to create the cell complexes from the graphs. Additionally, we measure how long takes to train the model for 100 epochs on ZINC evaluating after every epoch. We average all time measurements over 10 trials.
measure the transformation speed, we begin the time
37

---

Table 5: Bold results better than the corresponding message passing baseline, red results graph transformation based methods that are better than the corresponding non-standard message passing variation. + means lower is better. means higher is better.
MOL.- BACE
MOL. CLINTOX
MOL- BBBP ROC-AUCT
MOL.- SIDER
MOL. TOXCAST
MOL.- LIPO
DATA SET J MODEL
ROC-AUC 1
ROC-AUC
ROC-AUC f
ROC-AUC
RMSE
GIN
75.3
87.1
66.8
56.8
64.2 0.7
0.787 + 0.026
GCN
76.9
88.2 1.2
6.16
0.9
0.5
0.793 + 0.028
MLP
41.6
5.9
1.8
1.49
0.3
1.048 1 0.009
DS
2.9
1.34
60.6111
0.5
0.736 0.736 0.022
DS + GIN
75.3
4.2
6.82
0.9
6.5
0.716 0.014
DS GCN
77.7
83.8
6..0
6.9
6..1
0.754 0.018 0.018
DS + MLP
71.8 5.6
5.04
63.6
1.6
5.5
1.048 0.011 0.011
DSS
7.4
2.
6..5+1.5
1.5
66.4+0.8
0.652 0.009
DSS GIN
77.2
8.2
2.53
1.10+
6.4
DSS GCN
3.9
1.
67.3
1.0
6.61
DSS MLP
72.8
5.7
63.5+2..
2.06
0.8
1.054
CWN
2.70
24.7
6.6
1.6
6.9
CWN GIN
75.2
2.
68.1
6.1 1.
0.749 0.013
CWN + GCN
3.8
1.
6..
62.4111
6.64
0.787 + 0.016
CWN MLP
38.1
55.7 1 4.8
62.7
59.9 1.1
63.1 1 0.5
1.055 + 0.01
Table Speed comparison of different GNNs. TRANSFORM the time to transform the graphs to the required structure perform message passing over. TRAIN is the time train model to train for 100 epochs. COMBINED is the combined time of training and transformation. Bold indicates the best result for given non-standard message passing algorithm and corresponding graph transformation.
TRANSFORM
TRAIN. SEC. +
COMBINED
MODEL
SEC. $
SEC. +
GIN
NA
170 +
170
CWN
37 +
3259 = 16
3296 = 17
CWN GIN
67 1
286 =
353 7
DSS
95 44
955 5
1050 + 9
DSS GIN
183 1
1466 7
1649 + 15
DS
95
1235 5
1330 = 9
DS GIN
171
1060 1.
1231 1 13
Results. Table 6 shows the results of the speed evaluation. We can see that the graph transformation are roughly twice as slow the alternative transformation for the non-standard message passing. However, this runtime is still significantly smaller than the time it takes to train the model a single time. Thus, the runtime of graph transformations insignificant as the transformation only needs to be performed a single time whereas the model might need to be trained dozens of times to find good hyperparameters. With respect to the training time, DSS+GIN is roughly 54% slower than DSS and DS+GIN is roughly 17% faster than DS. Interestingly, CWN+GIN is times faster than CWN. While it might seem surprising that graph transformation based variant of CWN is 1xx faster than the original implementation, the reasons for that might be: (1) a bug, for example in how the original code of CWN interacts with our environment; (2) CWN requires large amount of code built on top of Py Torch Geometrie, whereas CWN+GIN just performs standard message passing: (3) the implementation CWN by Bodnar et al. [202 la] is not compatible with newer variants of Py PyTocc (Geometric) meaning that CWN+GIN can make use of speed increases due improvements in PyToch (Geometric). Reasons (2) and (3) highlight the strength of graph transformations in that they are mostly platform and implementation independent as the transformed graphs can be stored in file formats that are independent from the used deep learning framework.
38


Reviews:
[{"review_id": "tWdzPMyLVk", "reviewer": "Reviewer_YhPG", "summary": "The paper proposes a novel approach to simulate state-of-the-art graph neural networks (GNNs) using standard message passing. The authors introduce graph transformations that preserve the expressivity of GNNs and allow for better code optimization and competitive predictive performance on various molecular benchmark datasets. The paper presents two types of simulation, weak and strong, and evaluates their performance empirically. ", "questions": "- How sensitive is the performance of the proposed method to the choice of hyperparameters?\n", "limitations": "N/A", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "- The paper is highly original and presents a novel approach to simulating GNNs. \n- The authors provide a thorough evaluation of the proposed method on 10 benchmark datasets. \n- The paper is well-written and easy to follow, with clear explanations of the proposed method and its evaluation. \n- The proofs in the supplementary are comprehensive. I am impressed by the detailed step-by-step illustrations\n", "weaknesses": "Lack of Clarification. \n- The intro is not logically coherent. For example. it lacks a formal definition of “simulation” before expanding on it (e.g. simulation is using graph transformations so that standard message passing can reach comparable performances as state-of-the-art graph neural networks? In the introduction, no formal definition of “simulation” is given before expanding on “strongly/weakly simulated” MP algorithms.\n- Likewise, how do you define graph transformations and what are all possible types of graph transformations? Only until Section 3 were formal definition given\n\nThere are claims in the introduction that seem not grounded, which require justification and explanation:\n- Line 19-20: This is due to their limited expressivity: for all MPNNs, there are 20 pairs of non-isomorphic graphs that get the same embedding\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the positive review and appreciate that the reviewer acknowledges our paper novel approach, thorough evaluation, and highly original paper which is `well-written and easy to follow'. The reviewer raises only some lack of clarification as weakness which we address below.\n\n### Concerning the Weaknesses\n> Lack of Clarification.\n\n\n> The intro is not logically coherent. For example. it lacks a formal definition of “simulation” before expanding on it (e.g. simulation is using graph transformations so that standard message passing can reach comparable performances as state-of-the-art graph neural networks? In the introduction, no formal definition of “simulation” is given before expanding on “strongly/weakly simulated” MP algorithms.\n    \n>Likewise, how do you define graph transformations and what are all possible types of graph transformations? Only until Section 3 were formal definition given\n\nTo address the points raised, we will provide some intuition and give a high-level definition of our central concepts simulation and graph transformation in the introduction.\n\n> There are claims in the introduction that seem not grounded, which require justification and explanation: \n\n> Line 19-20: This is due to their limited expressivity: for all MPNNs, there are pairs of non-isomorphic graphs that get the same embedding\n\nWe will clarify in the camera ready version that this follows from the fact the MPNNs are bounded by $1$-WL in their expressivity (Morris et al., 2019, Xu et al., 2019).\n\n### Concerning the Question\n> How sensitive is the performance of the proposed method to the choice of hyperparameters?\n\nIn our experiments our approaches (simulating other GNNs) were similarly sensitive to hyperparameters as the original GNNs. In particular the number of message passing layers and graph pooling operations are important to tune. \n"}, {"review_id": "t8BURNmKKL", "reviewer": "Reviewer_5K9U", "summary": "This work presents a simulation theory/method for efficiently approximating non-standard GNN functions via standard MPNNs plus graph transformers. It starts from the cases that can be strongly simulated and extends to weak simulation for a comprehensive conclusion. A simulation algorithm is also proposed and verified with experimental results.\n\n", "questions": "A. Major\n\n      1. Lines 21-22 should give more examples of 'non-standard' message passing and 'standard' MPNNs for better readability at the beginning. Better to use a table.\n      2. As I understand it, the core of the work is to transfer these 'non-standard' MP functions to MPNNs plus graph transformation functions. Why can these graph transformation functions not also be understood as MPNNs? If this is not the case, is this the essential contribution, rather than just giving them a different name?\n      3. It seems that strongly simulated GNNs are equivalent to higher-order WL architectures. For example, subgraph-based GNNs.\n      4. For the experiments, the most important aspect is the time cost, while Table 6 mixes the convergence epochs and the computational complexity. More statistics on FLOPs and convergence analysis are recommended.\n\n\nB. Minor\n\n      1. Is the expressiveness of MPNNs in this paper about the 1-WL test? Or the authors should provide different explanations for the word \"expressivity\" each time it is used. For example, in line 503 of the appendix,  should it read 1-WL test？\n      2. Some errors in citation notation, e.g., lines 42-45.\n      3. In line 94, the definition of the neighborhood function, should it be $\\mathcal{N}_l$? Since $l$ is a parameter of the function, or two functions with different settings of $l(\\mathcal{N})$ can never know. There may be some misunderstanding of line 95.", "limitations": "N/A， ", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "   1. The problem is new (especially focused on non-standard GNNs), clearly defined and rigorously investigated. The motivation is quite practical (if I understand correctly).\n   2. Experiments on graph classification tasks verify the effectiveness of the proposed algorithms, including performance on AUC, time cost, RMSE, etc.", "weaknesses": "   1. The structure of the paragraphs dramatically reduces the readability.\n   2. See the questions below.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the positive review and appreciate that the reviewer acknowledges our rigorous investigation of a practically motivated novel problem.\n\nThe reviewer mentions that the \"structure of paragraphs\" reduces readability. Could you give us more details so we can fix it? Do you mean the inline equations and/or rather long paragraphs? We will improve readability in the camera-ready version using the extra page.\n\n### Concerning the Questions\n**Major**\n\n>   1. Lines 21-22 should give more examples of 'non-standard' message passing and 'standard' MPNNs for better readability at the beginning. Better to use a table.\n\nWe will add more examples to this section. With standard message passing we refer to MPNNs - the most common type of GNNs, which aggregate messages over each node's neighborhood and expressivity bounded by $1$-WL (Morris et al., 2019, Xu et al., 2019). With non-standard message passing we mean any other GNN, typically with expressivity surpassing $1$-WL.\n\n>   2. As I understand it, the core of the work is to transfer these 'non-standard' MP functions to MPNNs plus graph transformation functions. Why can these graph transformation functions not also be understood as MPNNs? If this is not the case, is this the essential contribution, rather than just giving them a different name?\n\nOn the one hand, graph transformations take graphs as input and output a modified graph. We use them as pre-processing. On the other hand MPNNs are differentiable functions that take graphs as input and output either node or graph embeddings (in Euclidean space). Furthermore, graph transformations cannot be seen as MPNNs: graph transformations can perform operations that are fundamentally impossible to do for MPNNs alone. For example, the transformation in Figure 1 transforms induced cycles in the graph to specially labeled vertices. As it is known (Chen et al., 2020) that MPNNs cannot detect induced cycles it follows that this transformation cannot be based on an MPNN.\n\n>  3. It seems that strongly simulated GNNs are equivalent to higher-order WL architectures. For example, subgraph-based GNNs.\n\nIt depends on what we regard as \"higher-order\": $k$-WL specifically or more generally some variants of WL. Strongly simulatable GNNs do not necessarily correspond (as far as we know) to some $k$-WL test and might have expressivity incomparable to it. However, any strongly or weakly simulatable GNN can be loosely seen as a variant of WL, potentially increasing expressivity. In particular, replacing the final \"function application (S4)\" step in augmented passing with any injective function (i.e., the identity function) will result in a color update function, which can be viewed as a variant of WL. Hence, our work makes WL / MPNNs at least as expressive as any strongly simulatable GNN through graph transformations.\n\n>   4. For the experiments, the most important aspect is the time cost, while Table 6 mixes the convergence epochs and the computational complexity. More statistics on FLOPs and convergence analysis are recommended.\n\nFair empirical convergence analysis in realistic settings is difficult as the different architectures often use different hyperparameters and performance dependence strongly on them. An extensive empirical comparison of time vs performance over different hyperparameters or tuning strategies goes well beyond the scope of this paper (we are not aware of any paper presenting such an analysis). \n\nHaving said that, we like the idea of adding more statistics like FLOPS to the final version of the paper and will do so as long as time permits. \n\n**Minor**\n\n>   1. Is the expressiveness of MPNNs in this paper about the 1-WL test? Or the authors should provide different explanations for the word \"expressivity\" each time it is used. For example, in line 503 of the appendix,  should it read 1-WL test？\n\nWhen talking about about expressivity (or expressiveness) we mean the ability of a GNN (or any function defined on graphs) to distinguish non-isomorphic graphs i.e. its ability to map different graphs to different embeddings. MPNNs are at most as expressive as the $1$-WL test and there are specific MPNNs (such as GIN) that are exactly as expressive as $1$-WL (Morris et al., 2019, Xu et al., 2019). Thus, when we compare the expressivity of some GNN to an MPNN we also compare it to the $1$-WL test. Line 503 reads: _This lead to the development of new GNNs that have higher expressivity than MPNNs._ Hence, line 503 equivalently also means: _This lead to the development of new GNNs that have higher expressivity than the $1$-WL graph isomorphism test._\n\n> 2. Some errors in citation notation, e.g., lines 42-45.\n\nThank you, we will fix this.\n\n> 3. In line 94, the definition of the neighborhood function, should it be $\\mathcal{N}_\\ell$? Since $\\ell$ is a parameter of the function, or two functions with different settings of $\\ell(\\mathcal{N})$ can never know. There may be some misunderstanding of line 95.\n\nWe do not fully understand the question. Can you please explain more exactly what you mean? We agree that it might be useful to make the parameter $\\ell$ explicit in $\\mathcal{N}_\\ell$. However, this would clash with with other notation we are already using. We will add further explanations to clarify the definition of neighborhood function.\n\n#\n\n(Morris et al., 2019): Morris et al.; Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks; AAAI, 2019\n\n(Xu et al., 2019): Xu et al.; How Powerful are Graph Neural Networks?; ICLR, 2019\n\n(Chen et al., 2020): Chen et al.; Can Graph Neural Networks Count Substructures?; NeurIPS, 2020\n"}, {"review_id": "dteWISnqKD", "reviewer": "Reviewer_GmCj", "summary": "The paper formally introduces the notions of MPNN simulating GNN with graph transformation. With the definitions, the authors further investigate which class of GNN can be simulated by MPNN.", "questions": "It would be nice to see more empirical investigations under the notions of simulations. ", "limitations": "Limitations have been adequately addressed.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The work presents the first systematic theoretical investigation toward understanding which GNN can be simulated by MPNN.", "weaknesses": "The simulation is based on expressiveness equivalence, so more empirical investigations may be required to understand the equivalence in practice.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their positive feedback and appreciate that the reviewer acknowledges the `first systematic theoretical investigation toward understanding which GNN can be simulated by MPNN'. Concerning the weakness and question:\n> (Weakness) The simulation is based on expressiveness equivalence, so more empirical investigations may be required to understand the equivalence in practice.\n\n> (Question) It would be nice to see more empirical investigations under the notions of simulations.\n\nOur experiments indicate that simulation achieves similar performance as the simulated algorithms. We compare simulation via MPNNs against 3 different non-standard message passing GNNs on 11 different datasets (see Tables 1, 2, 4, 5). \n\nWe agree that additional empirical investigations would further our understanding of GNNs and simulations in practice. While this is highly interesting, a fair comparison with a large number of higher-order GNNs requires that all higher-order GNNs are evaluated with a fair selection of hyper-parameters (and bounded run-time). This goes well beyond the scope of the current paper (we are not aware of any such study) and is an avenue for future work. Note that for transformations+simulation only, the fair comparison will be much easier as the same MPNN implementation and structure can be used.\n"}, {"review_id": "ANHX8QADeM", "reviewer": "Reviewer_r6Zx", "summary": "The authors introduce methods for simulating certain graph neural networks (GNNs) using standard message-passing algorithms composed with graph transformations. To do so, the authors introduce a class of nonstandard message-passing algorithms they call \"augmented message passing\" (AMP) algorithms, demonstrate that many standard GNNs are composed of AMP layers, and explicitly construct graph transformations such that standard message passing on the transformed graph input is at least as expressive as a given AMP algorithm. The authors also discuss \"weak simulation,\" and consider more specifically existing techniques that can be weakly simulated via the methods introduced by the authors. Finally, the authors numerically evaluate the performance of their introduced methods.", "questions": "I think this work is very nicely done, and only recommend some further exposition on the potential utility of the authors' work.", "limitations": "The authors have adequately discussed the limitations of their work.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The authors contribute a novel method for constructing message-passing neural networks (MPNNs) on transformed graph inputs that are at least as expressive as a wide class of GNNs with nonstandard message passing. This gives a standard way of viewing GNNs composed of AMP layers, which encompasses many state-of-the-art GNNs. This also formalizes previous work that considered graph transformations composed with MPNNs as a way to make MPNNs more expressive; simultaneously, it gives motivation for constructing GNNs that do not fit within this framework to construct more expressive GNNs This mapping between certain GNNs with nonstandard message passing and MPNNs acting on graph transformations also gives a potentially simpler framework for analyzing properties of such GNNs, though the authors are saving such study for future work.", "weaknesses": "One weakness is that it is not immediately apparent what practical advantages the introduced simulation methods yield over direct implementations of the GNNs being simulated. The authors mention one advantage being that standard libraries for implementing MPNNs can be used once a given GNN architecture has been shown to be simulable via an MPNN acting on a graph transformation, but that is a relatively minor advantage.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the very encouraging and positive feedback!\n\nOn the reviewers remark:\n\n> I think this work is very nicely done, and only recommend some further exposition on the potential utility of the authors' work.\n\nWe will provide further information on the utility of this work in the final version of this paper. Our work has three main utilities: (1) theory of expressivity, (2) design of new GNNs and (3) implementing GNNs with graph transformations. \n\n**(1) theory of expressivity:** Simulation allows to investigate the expressivity of different GNNs through a unified lens by analyzing the corresponding graph transformation. For example, it should be possible to apply the results of Geerts and Reutter (2022) to obtain this result: Any GNN that can be weakly simulated whose graph-to-structure and structure-to-graph encoding can be written in a tensor language with $k+1$ indices is upper bounded in expressivity by $k$-WL. Similarly, it should be possible to apply the results of Morris et al (2023) to obtain VC bounds for any weakly simulated GNN.\n\n**(2) design of new GNNs:** As noted by the reviewer, our theorems indicate that certain constructions (nested aggregations and non-pairwise message passing) **cannot** be strongly simulated and are thus fundamentally different from the message passing paradigm. Thus, to build GNNs that go beyond MPNNs in expressivity it seems promising to investigate such constructions.\n\n**(3) implementing GNNs with graph transformations:** Instead of implementing a GNN with non-standard message passing it can be implemented as a graph transformation together with an MPNN. We see the main advantage of this method as it being easier to implement a graph transformation than non-standard message passing and that the resulting method is:\n\n- Framework agnosticism: graphs can be stored independent from the used library for example as plain text.\n- Ease of use: to use a GNN implemented via a graph transformation it is only necessary to apply the graph transformation to the data and use a standard MPNN. Thus, it is not necessary to implement a complex model, incorporate it into an existing codebase and get it to work.\n\nThis utility is also relevant to the only weakness raised by the reviewer: \n\n> One weakness is that it is not immediately apparent what practical advantages the introduced simulation methods yield over direct implementations of the GNNs being simulated. The authors mention one advantage being that standard libraries for implementing MPNNs can be used once a given GNN architecture has been shown to be simulatable via an MPNN acting on a graph transformation, but that is a relatively minor advantage.\n\nFor many GNNs it is often not straightforward to use the publicly available implementations. Consider the examples of the GNNs we used in this paper: CWN and DSS. \nCWN is compatible with PyTorch 1.7 and CUDA 10.2 [(source)](https://github.com/twitter-research/cwn) which is too old to be compatible with RTX 3080 GPUs as they are based on the Ampere architecture [(source)](https://www.nvidia.com/en-us/geforce/graphics-cards/30-series/) which requires CUDA 11 [(source)](https://www.nvidia.com/en-us/geforce/graphics-cards/30-series/) (and trying to get it to work with newer versions failed for us, we actually had to find old hardware to run the model).\nDSS is implemented for PyTorch Geometric 1.7.2 which by now is almost 2 years out of date. In version 2.0.2 of PyTorch Geometric the behavior of  attributes with `batch` in the name in PytorchGeometric changes  (line 420 [here](https://github.com/pyg-team/pytorch_geometric/blob/2.0.2/torch_geometric/data/data.py)) compared to 1.7.2 (line 190 [here](https://github.com/pyg-team/pytorch_geometric/blob/1.7.2/torch_geometric/data/data.py#L178)) which causes issues with the `subgraph_batch` attribute in the implementation of DSS. This means that DSS requires a fix to work for newer versions of PyTorch. This shows that it is non-trivial to use existing implementations of GNNs with non-standard message passing. We believe that having a simplified way of running many GNNs would move the field forward by making it easier to use existing GNNs.\n\n#\n\n(Geerts and Reutter 2022): Floris Geerts and JL. Reutter; Expressiveness and Approximation Properties of Graph Neural Networks; ICLR, 2022\n\n(Morris et al 2023): Morris Christopher, Martin Grohe, Jan Martin Tönshoff, and Floris Geerts; WL meets VC; ICML, 2023\n"}, {"review_id": "A17y1x1VIF", "reviewer": "Reviewer_sQdR", "summary": "The paper investigates the idea of simulating (replacing) non-standard message passing networks (MPNs) using simple standard MPNs by first applying a graph transformation (new nodes and edges). The paper provides a formal construction of graphs and their generalizations in the form of relational structures that allows for describing e.g. non-pair-wise interactions and cellular complexes. The step through relation structures is important to make arrive to the main theorem of the paper, which is that many non-standard MPNs (based on higher-order relational structures) can be simulated with standard MPNs if the relational structure is converted to a graph in an appropriate way. The theoretical results are underpinned with experiments, showing that indeed simple MPNs on transformed graphs perform on-par (or even outperform) advanced non-standard MPNs.", "questions": "Although figure 1 was very helpful in getting the idea across. Figure 2 was less clear, mainly due to the notion of “nested aggregation” not being well explained. E.g. line 273 shows a color update function that depends on a nesting of sets, but how do I relate this to Figure 2? Also I read this as nested sets, but it is written “nested aggregation functions”, is $C_x$ an aggregation function then? I’m confused here as to what aggregation refers to, could you explain this?\n\nLine 94 the notation $2^{(U^l)}$ was unknown to me so I had to google it. It means the space of all mappings/functions $a: U^l\\rightarrow\\{0,1\\}$, right? Perhaps some detail/definition can be added.\n\nAre there any general recommendations for how to derive the graph transform to simulate non-standard MPNNs, or is this a case by case analysis? E.g., it is still unclear to me how one should derive/define R.\n \n", "limitations": "Limitations are appropriately discussed.", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "* The paper is precise and clear and systematically builds up to the theorems. The various formal definitions provided along the way are helpful in getting a high level picture of the graph NN field. At the same time, I must admit, that the formal approach does require quite some attention from the reader as the paper is dense with information and intuition is sometimes hard to acquire.\n\n* The experiments are effectively presented. Table 1 and 2 are interpretable and convincing.\n\n* The paper provides a novel analysis \n\n* The paper gives useful insights into the expressivity of various forms of graph NNs.\n\n* The paper seems reproducible with a link to clean (anonymous) code in the supplementary materials, and the supplementary materials are otherwise very thorough as well.\n", "weaknesses": "The main paper has few details for practitioners. E.g., how to convert a relational structure to a graph is not explained. Details are however provided in the supplementary materials. The paper could benefit from a running example, perhaps the CWN case (fig 1) in which the struct2graph conversion is intuitively explained, as well as why one can similar CWN on this new graph. An example is given at line 248, but feels a bit too abstract for me.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their positive feedback and appreciate that the reviewer acknowledges that our paper is precise, clear, has convincing experiments, and provides a novel analysis of graph neural networks. \n\n> At the same time, I must admit, that the formal approach does require quite some attention from the reader as the paper is dense with information and intuition is sometimes hard to acquire.\n\nThank you for pointing this out, we will add more examples to aid with intuition.\n\n### Concerning the Weakness\n> The main paper has few details for practitioners. E.g., how to convert a relational structure to a graph is not explained. Details are however provided in the supplementary materials. The paper could benefit from a running example, perhaps the CWN case (fig 1) in which the struct2graph conversion is intuitively explained, as well as why one can similar CWN on this new graph. An example is given at line 248, but feels a bit too abstract for me.\n\nWe provide some tips on how to transform structures to graphs in the proof sketch of Theorem 3.5. However, we agree that the main paper does not give enough explanations. We will add CWN as a running example.\n\n\n### Concerning the Questions\n> Although figure 1 was very helpful in getting the idea across. Figure 2 was less clear, mainly due to the notion of “nested aggregation” not being well explained. E.g. line 273 shows a color update function that depends on a nesting of sets, but how do I relate this to Figure 2? Also I read this as nested sets, but it is written “nested aggregation functions”, is $C_x$ an aggregation function then? I’m confused here as to what aggregation refers to, could you explain this?\n\nIn the paper we write _nested aggregation function_ but we think that the word function might be confusing and will thus change it to just _nested aggregation_. Furthermore, we will explain nested aggregations better in the final version of the paper. In the definition $C_x$ is meant to be an aggregation $C_x = \\\\{\\\\!\\\\{ c_y \\\\mid y \\\\in \\\\mathcal{N}(x) \\\\}\\\\!\\\\}$ (see line 273).  A nested aggregation is an aggregation inside another aggregation. For example, $\\\\{\\\\!\\\\{ c_y^t \\\\mid y \\\\in \\\\mathcal{N}_2(x) \\\\}\\\\!\\\\}$  is a single aggregation and $\\\\{\\\\!\\\\{ \\\\{\\\\!\\\\{ c_y^t \\\\mid y \\\\in \\\\mathcal{N}_2(x) \\\\}\\\\!\\\\} \\\\mid x \\\\in \\\\mathcal{N}_1 (v) \\\\}\\\\!\\\\}$ is a  a nested-aggregation. Consider the vertices in Figure 2 left, we refer to the top vertices as $a, b$ and the bottom vertices as $x, y$. Then Figure 2 is meant to be read as the blue vertex receives the colors $\\\\{\\\\!\\\\{ \\\\{\\\\!\\\\{ c_a^t, c_b^t \\\\}\\\\!\\\\}, \\\\{\\\\!\\\\{ c_x^t, c_y^t \\\\}\\\\!\\\\} \\\\}\\\\!\\\\}$. \n\n> Line 94 the notation $2^{(U^l)}$ was unknown to me so I had to google it. It means the space of all mappings/functions $a: U^l \\\\to 0,1$, right? Perhaps some detail/definition can be added.\n\nThe _power set_ of a set $X$ contains all subsets $2^X=\\\\{Y \\\\mid Y \\\\subseteq X\\\\}$ of that set $X$. For a set $U$ and an integer $\\\\ell > 1$, the set $U^\\\\ell=\\\\{ (u_1, \\\\ldots, u_\\\\ell) \\\\mid u_1 \\\\in U, \\\\ldots, u_\\\\ell \\\\in U \\\\}$ is the set containing all tuples of length $\\\\ell$ built from elements of $U$. Thus, for a set of objects $U$, the set $2^{(U^\\\\ell)}$ consists of all possible sets built from $\\\\ell$-tuples of $U$. For example, $U = \\\\{x, y \\\\}$ and $\\\\ell = 2$. Then, $U^\\\\ell = \\\\{ (x,x), (x,y), (y,x), (y,y) \\\\}$ and $2^{(U^l)} = \\\\{\\\\emptyset, \\\\{  (x,x) \\\\}, \\\\{  (x,y) \\\\}, \\\\{  (y,x) \\\\}, \\\\{  (y,y) \\\\}, \\\\{  (x,x), (x,y) \\\\}, \\\\ldots, \\\\{(x,x), (x,y), (y,x), (y,y) \\\\} \\\\}$. Finally, the neighborhood function $\\\\mathcal{N}$ assigns one set in the domain $2^{(U^l)}$ to each element $u\\\\in U$. We will add some details about this to the paper. \n\n\n> Are there any general recommendations for how to derive the graph transform to simulate non-standard MPNNs, or is this a case by case analysis? E.g., it is still unclear to me how one should derive/define R.\n\nWe provide an automated way of deriving the graph transformations with Algorithm 4 (strong simulation) and Algorithm 6 (weak simulation). We see this as one of the key strengths of our paper: it is no longer necessary to design the graph transformations by hand for every architecture and to prove their correctness. Instead, our algorithms automatically yield the required graph transformations to simulate the given non-standard MPNN. For strong simulation, the algorithm first creates a vertex for every object and then adds edges between two vertices if the corresponding two objects exchange messages in the simulated algorithm. The main difference for weak simulation are the cases with non-pairwise message passing and nested aggregations where we need to add dummy vertices (see proof sketch of Theorem 5.2). \n"}, {"review_id": "5nt8qcBWSQ", "reviewer": "Reviewer_sDHK", "summary": "The paper deals with supervised machine learning with graphs, specifically with expressive GNNs, and how to implement them efficiently. Specifically, it investigates the expressive power of graph transformations to transform an input graph such that an ordinary 1-WL-equivalent message-passing GNN can simulate, e.g., k-WL-equivalent GNNs, in a layer-wise fashion (strong simulation). To that, the authors formally define this transformation and show that an MPNN can simulate many popular, more expressive GNNs, see Corollary 3.6. \n\nThe authors acknowledge that such a transformation is folklore knowledge.\n\nMoreover, they investigate the regime (weak simulation) where the MPNN on the transformed graph needs more iterations to distinguish the same pairs of non-isomorphic graphs. Restricted to their particular definition of transformation, they show that some GNN layers cannot be strongly simulated but weakly simulated. \n\nEmpirically, they show that their transformations often beat standard message-passing GNNs regarding predictive performance on standard benchmarks. Somewhat surprisingly, they show that they sometimes even beat the architectures they are aiming to simulate. \n\n\n", "questions": "Q1: Do you, to some extent, understand why the simulated architectures often lead to better predictive performance over their simulated counterpart?\n\nQ2:  Do you, to some extent, know if the simulation factor influences predictive performance? For example, does a high simulation factor lead to better or worse predictive performance?", "limitations": "It seems that the proof of Theorem 4.1 strongly exploits specific details of \"Structure-to-graph encoding\" (Def. 3.1), which makes the results somewhat narrow. This should be clarified.\n", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The paper is easy to read, and everything is formalized appropriately. The proofs seem to be correct, and the theoretical results are plausible. \n\nTo the best of my knowledge, Theorem 5.2 and Corollary 5.3 are new and somewhat interesting. \n\nThe experimental study is well conducted, and the presented results are somewhat interesting. ", "weaknesses": "Section 3 just contains more or less obvious results known within the graph learning community. (This is also clearly acknowledged by the authors in the introduction and the appendix.). However, with this in mind, it is unclear why Section 3 occupies 1/3 of the main paper.\n\nIt seems that the proof of Theorem 4.1 strongly exploits specific details of \"Structure-to-graph encoding\" (Def. 3.1), which makes the results somewhat narrow. The authors should be more clear about this.\n\nThe reasoning in lines 191 -- 195 is highly handwavey. You seem to implicitly assume that the function is continuous on a compact domain. \n\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the feedback.\n\n### Concerning the Weaknesses\n>Section 3 just contains more or less obvious results known within the graph learning community. (This is also clearly acknowledged by the authors in the introduction and the appendix.). However, with this in mind, it is unclear why Section 3 occupies 1/3 of the main paper.\n\nWe agree, parts of the graph learning community know that some specific GNN architectures can be simulated (some of these GNNs are even implemented through an MPNN applied on a transformed graph, as discussed in our appendix).\nHowever, formalizing and proving such informal knowledge is an added value for the GNN community. Additionally, we prove that is it possible to simulate further GNNs for which it was previously not know. In particular, the key results of Section 3 are:\n\n(1) a formal definition of strong simulation (i.e., preserving expressivity in each iteration / layer), \n\n(2) a general algorithm that yields the required graph transformations to strongly simulate GNNs that follow our definition of augmented message passing, and \n\n(3) simulation results for 9 GNNs, 5 of which were not known to be simulatable before (and were originally implemented though non-standard message passing).\n\nAs far as we know, the formal definition of strong simulation is novel. Through this definition we generalize individual results into a general theoretical paradigm. Furthermore, while such results might be obvious to the original authors of a GNN, coming up with a corresponding graph transformations is non-trivial and previously has required proving their correctness for every single architecture. With (2) we streamline this approach: our algorithm yields a graph transformation (with guaranteed strong simulation) for any GNN that follows our definition of augmented message passing.\n\nRemark on (3): skimming recent LoG and ICML paper, we found two more strongly simulatable GNNs that have not been known to be simulatable before and were implemented through non-standard message passing (see global response for more details). A thorough literature review would most likely yield many more strongly simulatable GNNs.     \n\n>It seems that the proof of Theorem 4.1 strongly exploits specific details of \"Structure-to-graph encoding\" (Def. 3.1), which makes the results somewhat narrow. The authors should be more clear about this.\n\nTo obtain a useful definition of simulation it is **necessary** to put restrictions on the transformations (eg a computationally expensive way to simulate any GNN is to encode the isomorphism class in any graph label).\nOur definition of structure-to-graph encoding details these necessary restrictions.\n\nWe enforce two natural restrictions on structure-to-graph encoding and simulation. The first restriction limits the asymptotic runtime of the encoding to the runtime of a single iteration of the simulated algorithm. This avoids the case of precomputing isomorphism classes and running other expensive algorithms. However, this still allows to use the simulated algorithm for a large (but constant) number of iterations to produce features in the structure-to-graph encoding. The second restriction decouples the generation of the graph structure from the features of the original structure which avoids this issue. These two restrictions allow the simulation of many common GNN architectures and simultaneously forbid the previously discussed trivial cases. \n\nWe explain this partly in the discussion section of our paper but we will make it clearer in the camera ready version.\n\n>The reasoning in lines 191 -- 195 is highly handwavy. You seem to implicitly assume that the function is continuous on a compact domain.\n\nThanks for spotting. We will fix this and add the required assumptions to the camera-ready version.\n\n\n### Concerning the Questions\n> Q1: Do you, to some extent, understand why the simulated architectures often lead to better predictive performance over their simulated counterpart?\n\nAs indicated in Table 2, GIN + a graph transformation beats the original GNN in 50-60% of experiments. This is exactly the expected behavior: our simulation performs on par with the original GNN; it's basically a fair coin flip, which of the two is better. We refer the remaining performance differences to randomness / noise in training and hyperparameter search.\n\n> Q2: Do you, to some extent, know if the simulation factor influences predictive performance? For example, does a high simulation factor lead to better or worse predictive performance?\n\nThis is an interesting question for follow-up work as we have two opposing ideas about this. A higher simulation factor means that when an MPNN simulates a higher-order GNN it will need more layers to achieve the same expressivity. We hypothesize that this could lead to worse predictive performance as deeper GNNs are harder to train due to issues such as oversmoothing. However, there has been recent work [Bause 2022] [Azabou 2023] that argued that slowing down message passing (hence using more layers to perform one standard $1$-WL aggregation) can lead to better predictive results. As a simulation factor greater than 1 slows down message passing compared to the simulated architecture, this could also improve the predictive performance. Overall, more research into this direction is needed.\n\n#\n\n[Azabou 2023]: Azabou et al.; Half-Hop: A graph upsampling approach for slowing down message passing; ICML, 2023\n\n[Bause 2022]: Bause and Kriege; Gradual Weisfeiler-Leman: Slow and Steady Wins the Race; Learning on Graphs Conference, 2022\n"}]

Author rebuttal:
Dear reviewers, we thank you very much for your detailed comments and respond to your reviews individually below. We appreciate that you acknowledge the novelty, originality, the systematic theoretical investigation, and the well-conducted experiments.  

Dear all, to further extend the generality of our approach we have taken a quick look at some recent papers and could prove that two additional GNNs can be strongly simulated: shortest path networks [Abboud et al., 2022] and generalized distance weisfeiler-leman [Zhang et al., 2023]. We have added a list of utilities that our work provides to the review of r6Zx and look forward to the discussion with you.

Best,

The authors of Expressivity-Preserving GNN Simulation



#


[Abboud et al., 2022]: Abboud et al.; Shortest Path Networks for Graph Property Prediction; Learning on Graphs Conference, 2022

[Zhang et al., 2023]: Zhang et al.; RETHINKING THE EXPRESSIVE POWER OF GNNS VIA
GRAPH BICONNECTIVITY; ICLR, 2023


Meta-review: The reviewers are overall quite positive about the paper (6-6-7-7-8), except for Reviewer sDHK leaning towards rejection (4). The author-reviewer discussion has been constructive and has led a number of recommendations to improve the paper. The novelty of the paper is debated by Reviewer sDHK, who argues the results are mostly implicitly known to the community. Nevertheless, provided that shortcomings are addressed, Reviewer sDHK is also not against acceptance. For these reasons, we request the authors to address as much as possible the reviewers' comments in the final version of the paper.
Decision: Accept (poster)