A Systematic Approach to Universal Random Features in Graph Neural Networks
Authors: Billy Joe Franks
Markus Anders
Marius Kloft
Pascal Schweitzer
Venue: Accepted by TMLR ()

Abstract: Universal random features (URF) are state of the art regarding practical graph neural networks that are provably universal. There is great diversity regarding terminology, methodology,  benchmarks, and evaluation metrics used among existing URF. Not only does this make it increasingly difficult for practitioners to decide which technique to apply to a given problem, but it also stands in the way of systematic improvements. We propose a new comprehensive framework that captures all previous URF techniques. On the theoretical side, among other results, we formally prove that under natural conditions all instantiations of our framework are universal. The framework thus provides a new simple technique to prove universality results. On the practical side, we develop a method to systematically and automatically train URF. This in turn enables us to impartially and objectively compare all existing URF. New URF naturally emerge from our approach, and our experiments demonstrate that they improve the state of the art.

Published in Transactions on Machine Learning Research (08/2023)
A Systematic Approach to Universal Random Features in Graph Neural Networks
Billy Joe Franks
billy. www.frrnkssrrpuu.. de
Deportment of Computer Science
University of Kuiserslauterr-Landeee (RPTU)
Markus Anders
Department of Mathematics
TU Darmstadt
Marius Kloft
Department of Computer Science
University of Koiserslauterr--anddey (RPTU)
Pascal Schweitzer
Department of Mathematics
TU Darmsladt
Reviewed on OpenReview: https: // // operreview. net/ pett/foruet forum? id= AXULAIXOPM
Abstract
Universal random features (URF) are state of the art regarding practical graph neural net- works that are provably universal. There is great diversity regarding terminology, method- ology, benchmarks, and evaluation metrics used among existing URF. Not only does this make increasingly difficult for practitioners to decide which tochnique apply to given problem, but also stands in the way of systematie improvements. We propose new comprehensive framework that captures all previous URF techniques. On the theoretical side, among other results, we formally prove that under natural conditions all instantiations of our framework are universal. The framework thus provides new simple technique to prove universality results. On the practical side, we develop a method to vystematically and automatically train URF. This in turn enables us to impartially and objectively com- pare all existing URF. New URF naturally emerge from our approach, and our experiments demonstrate that they improve the state of the art.
1 Introduction
Structured data is omnipresent in the modern world. Graphs are fundamental data type in machine learning (ML) on structured data and used a variety of learning algorithms (Shervashidze et al. 2011
Nickel et al. 2016 Hamilton et al. 2017), including graph neural networks (GNNs) (Zhou et al. 2020 Wu
ct al. 2021). ). GNNs, and espocially message passing neural networks (MPNNs) (Gimmer ct al.] 2017). have
found widespread applications, from drug design to friendship recommendation in social networks (Song
et al. 2019 Tang et al. 2020). However, severe limitations of MPNNs have recently been proven formally.
In fact, MPNNs are at most expressive as color refinement (Xu et al. 2019 Morris et al. 2019 Color
refinemment also known as the 1-dimensional Weisfeiler-Leman algorithm
is a simple algorithm inducing
a non-universal similarity measure on graphs. Thus MPNNs fail to be universal function approximators, a fundamental property known for multilayer perceptrons since the 1980s (Cybenko 1989
Addressing this lack, universal random features (URF) Murphy al. 2019 Dasoulas al. 2020 Sato
al. 2021 Abboud et. al. 2021) were developed, which provably enable MPNNs to be universal function

---

Published in Transactions on Machine Learning Research (08/2023)
approximators. URF enhances the nodes of the graph with random values, thus artificially breaking its intrinsic symmetries and facilitating the distinction of previously indistinguishable nodes. URF represent the state of the art in practical, efficient, and universal GNNs. Recently, numerous variations of URF have been developed (Murphy et al. 2019 Dasoulas et al.) 2020 Sato et al. 2021 No systematic comparison of these URF is available and unclear how their trainability, genera lizaility,, and expressivily (Raghu ct al., 2017) compare to one another, because of inconsistent terminology, differing or incomplete data sets for benchmarking, and orthogonal evaluation metries. This makes it difficult for practitioners to decide which technique to apply. It also stands in the way of systematic improvements.
Our contributions. We propose two systematic approaches to dealing with URF: 1) The individualization- refinement. node initialization (IRNI) framework, a theoretical description that encompasses all currently known URF schemes (and even proposes new ones, see Figure The foundation for our framework is graph isomorphism theory, particularly the iatiiiddallaatioo-reenneeee (IR) paradigm. 2) A tuning tochnique based on bayesian hyperparanter optimization (BHO), designed specifically to tune methods based on the TRNT framework.
Armed with these new systematic approaches, we make the following contributions:
We demonstrate that our framework IRNT is comprehensive. In fact, we show that all previous URF techniques are captured.
We formally prove that all instantiations of the IRNT framework that satisfy a natural compatibility condition are universal and equivariant, even ones not considered so far. Furthermore, we prove that already a very limited version of IRNI is universal on almost all graphs, including all 3-connected planar ones. We also quantify the amount of randomness required to ensure universality of all but exponentially small fraction of all graphs.
We apply and systematically test "ensembling over randomness" on all URF, This is a particular form of ensembling that previously has been applied in some but not all URF (Murphy et al. 2019: Dasoulas et al., 2020). Our crucial new insight is that ensembling over randomness significantly improves the performance of all URF, even in cases in which it had not been considered previously.
The IRNI framework also suggests a new most natural URF directly related to practical graph isomorphism solvers.
We compare all previous URF methods using the same BHO tuning approach. This leads to multiple new state-of-the-art performances. In particular, all previous URF methods are improved upon. Additionally, we discover that even though random node initialization (RNT) was reported to be harder to train than other URF (Abboud et al. 2021 our tuning approach resolves this issue.
In our evaluation, and somewhat surprisingly, we find that currently, there seems to be no clear best strategy in practice. There are strengths and weaknesses to all considered URF. However, this marks the first direct comparison of all the different URF and thus enables a more informed choice of which method to use in practice.
Our hope is that our systematic approach also cases future development of URF, in particular for developing and evaluating new algorithmic ideas.
Individualization refinement in a nutshell: The individuallzation-renneenn framework is a general tech- nique to devise algorithms for tasks revolving around symmetry. Specifically, it can be used to compute isomorphisms, automorphisms (or symmetries), and canonical forms of graphs other combinatorial ob- jects. The idca is first to use efficient subroutines to distinguish vertices according to simple structural properties preserved by symmetries. An example, which in fact, is similar to what is computed by color refinement (also known as the 1-dimensional Weisfeiler- on the degree of neighbors of a vertex and the degrees of the neighbors of the neighbors and so on. These efficient subroutines must be isomorphism invariant and refine the partition of vertices into indistinguisaable parts (and are therefore called refinements).
algorithm),, iteratively collects information
2

---

Published in Transactions on Machine Learning Research (08/2023)
Input Graph
Random "IR tree" path
GNN
strengthens
provably universal
madels many techniques
HNI
RP
Otherz
CLIP
Figure 1: Summary of our new approach: we describe a framework based on "random IR tree paths", called IRNI. Through its parameters, the model is able to exactly model many previous techniques. We prove that any IRNI-enhanced GNN is universal.
Once a state is reached where refinements no longer yield new information, an IR algorithm artificially distinguishes vertex with so-called individualization. This individualization breaks apparent symmetry and allows us to recurse by applying another refinement step, and on. Since the individualization is also have to perform the individualization in backtracking
artificial, to preserve isomorphism-invariee manner with all vertices which have not been distinguished from the vertex at this point. The backtracking process finishes once all vertices have been distinguished, making symmetry computations trivial. We refer to Section 4 for a more in-depth explanation of the TR machinery necessary for this work.
Why individualization refinement. We explain why the IR-framework is natural choice for the develop- ment of efficient universal GNNs. (For general strengths and weaknesses beyond ML see (McKay & Piperno,
2014 Neuen & Schweitzer 2017 First of all, the introduction of graph isomorphism techniques in the context of machine learning on graphs already led to two success stories, namely the efficient Weisfeiler- Leman (WL) Kernels (Shervashidze ot al. 2011 based on color refinement (1-WL) and the more theorctical higher-order graph neural networks (Morris al.] 2019)) based on higher-dirennsoonll WL.
However, when comes to practical graph isomorphism, the use of the 2-dimensional WL already pro- hibitive. This is not only due to excessive running time but also due to excessive memory consumption. In the world of isomorphism lesting, higher-dimensional Weisleiler-Leman algorithrs remain the theoreti- cal side. In truth, without fail, modern solvers are IR algorithmss (McKay 1981 Junttila & Kaski 2011
McKay & Piperno 2014 Anders & Schweitzer 2021a).. They only use color refinement and instead of higher- dimensional WL rather use individualizations to achieve universality. In contrast to nigher-dimensional WL, the TR approach is generic, universal, and practical. Uncontested for more than 50 years, TR algorithms have the fastest computation times and acceptable memory consumption for graph isomorphism (McKay & Piperno 2014). In that sense, the IRNI approach universal graph isomorphism techniques that are truly used in practice are transferred into machine learn- ing context. An important consequence of this is that ML practitioners can now readily transfer existing IR-related results to ML on graphs (Sec. 4.3
introduce in this paper is the first time in which
2 Related Work
Graphs are a powerful mcans of representing semantic information. Since graphs are a very general data type and most her data types are special cases, graphs have many applications. They can be used to extend or combine other data types like text, images, or time series (Noble Cook 2003 Vazirgiannis et al. 2018) and there are also data sets specific to graphs. Most commonly, these data sets are related biology or chemistry. However, computer vision, social networks, and synthetic graphs without related field are also present (Morris et al. 2020a). Neural learning on structured data like graphs first introduced in
3

---

Published in Transactions on Machine Learning Research (08/2023)
[askknn et al. 1997 Sperduti & Starita 1997). Recently, more specific deep learning model was pioneered for graphs, the graph neural network (GNN) Gori et al. 2005 Scarselli et al. 2009). The GNN led to the development of a multitude of related models Duvenaud et al. 2015 Li et al. 2016) usually referred to just as GNNs. GNNs allow for the joint training of graph feature extraction and classification, which previous models did not., Gilmer et al. (2017) gave a very general characterization of GNNs called message-passing neural networks (MPNN), which most GNN models can be characterized as. Lately, multiple concepts from other domains of deep learning have been transferred to GNNs like the attention mechanism (Velickovic 2018 and hierarchical pooling (Ying et al. 2018).
et al.
Cybenko 1989 proved the first universality result for one of the carliest deep learning models, the smallest possible multilayer perceptron (MLP). This result. has since then been expanded to different activation functions (Leshno et al.] 1993 Barron 1994), to width-bounded MLPs (Lu et al. 2017 Liang & Srikant 2017), and more recently to different layered artificial neural networks like the convolutional neural network [Zhou 2020). Analogous results had been lacking for MPNNs, which are now well-cstablished
be non- 2019 Morris et al. 2019 Abboud et al. 2021 Following this finding, multiple attempts were made to establish universal ML models graph data. Murphy et al. (2019) proposed relational pooling 2021)) | proposed random node initialization (RNT), and Dasoulas et al. (2020) proposed the colored local iterative procedure (CLIP), all of which provide universality to MPNNs (Abboud et al.) 2021 and are closely related to one another as methods using universal random features (URF). Morris et al.
universal (Xu et al.
(RP), Sato ct al.
(2019 2020b) proposed k-GNNs based on the k-dimensional Weisfeiler-Leman algorithm and expanded on it by proposing the 8-k-GNN a local approximation variant of the k- k-GNN. |Maon et al. (2019a b) propose provably powerful graph networks, which are 2-WT. powerful, and invariant, graph networks, which are proven to be universal, sce Morris ct al. 2021 for further pointers.
In this paper, we only consider methods that are scalable, practical, and universal at the same time. For a comparison between universal and non- unnveriveraal approaches we refer to existing literature (Dasoulas et al. 2020 Morris et al. 2019 2020b Maron et al. 2019a). As expected non-universal approaches can outperform universal approaches in lasks that do not require high expressivily. However, non-universal approaches fail to achieve high performance on tasks that require high expressivity. Therefore, only methods employing random foatures that grant universality (Murphy et al.] 2019 Dasoulas et al.] 2020 Sato et al., 2021)
universal random features (URF), are considered. Some readers might wonder if typical graph data augmentation schemes should also be considered here. Examples would include deleting/ /adgin/ edges/nod:s nodes. While these changes to graphs can induce the capacity to distinguish graphs from one another, we expected that universality of these methods is hard to prove. For delctions, this is essentially due to the various reconstruction conjectures, which so far have no proof. is currently unknown if the set of all graphs with one node/odge deleted can be used to reconstruct the original graph, which would be required for these operations to be universal. As for node addition, the IRNI framework subsumes this operation as coloring set of nodes is equivalent to node addition. Lastly, edge addition can be viewed as removing edges from the inverted graph and therefore has the same issues as edge deletion. For these reasons, we do not consider
the vast number of data augmentations that are not provably universal (Puny et al. 2020 Papp et al. 2021
Ding et al. 2022).
3 Background
Here we cover existing background necessary to understand the IRNI framework. Specifically we define graphs as well as how they are used in ML followed by coloring of graphs. We then cover color refinement a fundamental backbone of individualization refinement, the practical algorithm the IRNI framework is based on. This is followed by a definition of GIN networks the specific MPNN model we use. Lasty, we cover the specifics of RP, RNI, and CLIP, which are the related methods that can be described in the IRNI framework and that we compare later on.
4

---

Published in Transactions on Machine Learning Research (08/2023)
Figure A run of naive refinements on graph. The sequence of naive refinements ends the coarsest equitable coloring, which can not be refined further using the naive refinement. Note how each coloring is finer than the previous coloring.
3.1 Graphs and Colorings
We consider undirected, finite graphs G (V, E) which consist of a set of vertices V C N and a set of edges E C V2, where E is symmetric. From this point onward, let n := [V] and V = mn. Additionally, we let denote the set of all graphs, while 9n denotes the set of all graphs on n vertices.
In ML contexts, graphs typically carry a node representation in Rd, which denote by X = IR-tools require these node representations to be discrete. In other contexts, discretization can be difficult and techniques are being actively rescarched (Morris et al.) 2016). However, the discretization is not critical for our purpose since we only require this encoding to compute a tuple of nodes (W), W2,...) from an IR algorithm. After that, our approach continues on the original node representation. Let enc: R x G + be an arbitrary cooorphismminvartiii invariant encoding of the node representations. In practice, is best to choose an encoding for which enc(#., G) = enc(æ G) if and only if x, ww, however, this not a requirement for any of the results we present. Elaborating further, if enc(a,, G) enc( ( G) even though 2, A a. then more nodes might be "individualized" than strictly necessary, still resulting in universal and equivariant method as described in Sec. 4
( (.1...... Ln)
A (node) coloring is surjective map T: V + (1....,k), k]. We interpret the node representations as colors using enc, i.e πii) : enc(a,, G). We call π -i) S V the i-th cell for i e f1....,k). If [T()) = n then a is discrete. This means every node has a unique color in m. Note that in the following, we always use "discrete" in this sense. Furthermore, we say a coloring ı is finer than T' if (v)) T(o') = <'(v) = <'o') holds for every U, 0 E V. We may also say n' is coarser than æ. See Figure where each consecutive coloring of the graph is finer than the previous one.
k].
We should remark that the IR machinery generalizes to directed and edge-colored graphs. One example of achieving this is by subdividing each edge with additional colored vertices, where the additional vertices model the edge color or edge direction (sce McKay & Piperno for more dotails). Alternatively, said features can also be added to IR algorithms directly (Piperno) 20188).
We denote by Na(v) the neighborhood of node in graph G.
3.2 Color Refinement
We now define color refinement, which all practical graph isomorphism solvers use. A coloring π is equitable if for every pair of (not necessarily distinct) colors i,j, the number of j-colored neighbors is the same for all i-colored vertices. Equitable colorings are precisely the colorings for which color refinement cannot be employed to distinguish nodes further. For a colored graph (G, т) there (up renaming of colors) a unique coarsest equitable coloring finer than π (MeKay 1981) This is precisely the coloring computed by color refinement.
A more algorithmic way to doscribe the refinement is to define for a colored graph (G, л) the naively refined graph (G, where (1) = (T(v), {T(('' | o' E NG(v) The naive refinement is applied exhaustively, i.e., until vertices camnot be partitioned further. The result is precisely the coarsest equitable coloring. Figure illustrates the color refinement process.
Note that color refinement, and hence coarsest equitable colorings, are strongly related to MPNNs, as is explained below.
5

---

Published in Transactions on Machine Learning Research (08/2023)
3.3 Message Passing Neural Networks
Formally a message passing update can be formulated as:
2,1+1 combine( aggregate((#w,.du E Nc(e)))),
(1)
where G is a graph and Ee is the vector representation of node at time t. In this context, time is usually interpreted as the layer and the aggregate function is typically required to be invariant under isomorphisms. We want to point out the similarity between the refinement r in color refinement and the message passing MPNNs are just computing on the colors computed by color refinement, which why MPNNs are at most as powerful as color refinement in distinguishing graphs. We refer to Xu et al. (2019) and Morris et al. (2019) for formal comparison. Common instances of MPNNs
update (Equation
graph convolutional graph attention networks (Velickovic et al. 2018 and graph isomorphism We use GIN throughout this paper, arguably the most efficient of these
networks (Duvenaud et al. 2015).
networks (GIN) (Xu et al. 2019
models (Dasoulas et. al. 2020).
A GIN is characterized by being simple and yet as powerful as the color refinement algorithm. Given an arbitrary multi-layer perceptron MLP(²) in layer k, e(*) learnable parameter of layer k, and h the input reprosentation of node
GIN updates its node reprosentations h: in layer k follows:
((++. h
h(*h) = MLP(3)
1(--1)+
(k-11) uENote)
E
(2)
3.4 Random Features
Intuitively, using random features is a process that introduces randomized information into the input before processing it using machine learning techniques. For example, might delete a random node attach random numbers to feature vectors. We do not require a more formal notion since, in this paper, we are only interested in universal random features (URF). We use URF to refer to methods that provably enable their universality if used in conjunction with MPNNs. We next summarize all existing URF techniques.
RP attaches a random permutation to the graph by attaching to each node a onc-hot encoding of its image. To understand RNI, let G be graph with node representations { Fr and d E N constant, random node initalization (RNT) concatenates d features sampled from random distribution X' to each node Vv {I,...,nz n1) Fy concatennate(2., "....... r.....,,a..r.......... r...,
X. CLIP first apply color refinement and then individualize cach node of cach color class by assigning a one-hot encoding of natural number to it. C' is the set of all nodes of one color class, then each node v E C is randomly assigned a unique number in (O....,IC)
|C| - 1}, which is then one-hot encoded and concatenated onto its node representation Z..
4 Random Features from Individualization Refinement
First, we describe individnalizatioo--efeneeen trees followed by the individualizatoo--rrfeeneee node ini- tialization (IRNI) framework. Then, we demonstrate that RNI, CLIP, and RP can be expressed as a man- ifestation this framework. Lastly, we give several theoretical insights into the framework and prove a general universality for these methods under natural compatibility constraint.
4.1 Individualization Refinement Trees
Individualization refinement (IR) trees are the backtracking trees of practical graph isomorphism algorithms. We use randomly sampled leaves of these trees as random features. These leaves correspond to sequences of nodes (w,,..., wx) of the graph, which we translate into fcatures of the MPNN. One central property of the sequence is that distinguishing its nodes from other nodes in the graph and applying color refinement yields discrete coloring.

---

Published in Transactions on Machine Learning Research (08/2023)
Figure 3: In IR, refinement and individualization alternatingly applied. This continues until the coloring of the graph becomes discrete. Two nodes connected by squiggly line are considered one node of the IR. tree: they illustrate the coloring of the graph before and after color refinement.
In the following, describe all the necessary ingredients of IR for the purposes of this paper. The IR paradigm is complex machinery refined over many decades into sophisticated software librarics. We refer to McKay & Piperno (2014) and Anders & Schweitzer (2021a) for an exhaustive description.
Refinement. The most crucial subroutine of an IR algorithm is the refinement Ref G x IXXI - II, where II denotes the set of all vertex colorings of G and V denotes a string of vertices (* is the Kleene star). A refinement must satisfy two properties: it must be invariant under isomorphism and individualize vertices in # E V*, Le., let
Ref(G, n, v), then for all v E v it holds that π² n'= (a' (t)) = {e}. Our definition of refinement slightly more general compared to McKay Piperno 2014), which leads slight technicality that discuss in the appendix.
In practice IR tools use color refinement as their refinement (see Sec. 3.2 as CR(G, E), where denotes the empty sequence (explained further below).
We denote color refinement
Individualization. IR algorithms make use of individualization, process that artificially forces a node into its own color class, distinguishing it. To record which vertices have been individualized we use a sequence v = (v1...,, v)) E V*. We modify color refinement so that CR(G, म. v) is the unique coarsest equitable coloring finer than π in which every node in v a singleton with its own artificial color. Artificial distinctions caused by individualization are thus taken into account.
Cell selector. In a backtracking fashion, the goal of an IR algorithm to reach a discrete coloring using color refinement and individualization. For this, color refinement first applied. If this does not yield discrete coloring, individualization is applied, branching over all vertices in one non-singleton cell. The task of the cell selector is to coomorphimm-ivvrianttyy pick the non-singleton cell. Figure illustrates this process. While many choices within certain restrictions possible, one example that we will also use later on is the selector that always chooses the first, largest non-singleton cell of æ. We use the notation Sel to refer to a cell selector.
IR trees. We first give formal definition of the IR tree Ree x), followed by a more intuitive expla- nation. Nodes of Ree (G, x) are sequences of vertices of G and the root is the empty sequence e = (). If v = (ei...., uk) is a node I (RR T) and C = Sel(G, Ref(G, न. v)) the selected cell, then the set of children of v is {(),...., U2 w) v E C}, i.c., all extensions of by one node v of the selected cell C. The root represents the graph (with no individualizations) after refinement (sce Figure 3 A node v represents
the graph after all nodes in have been individualized followed by refinement. (see Figure 3). A root-to-v

---

Published in Transactions on Machine Learning Research (08/2023)
walk of the tree is naturally identified with a sequence of individualizations in the graph: in each step i of the walk, one more node vy belonging to a non-trivial color class C' is individualized (followed by refinement). The sequence of individualizations (Vi,..., v4) uniquely determines the node of the IR tree in which this walk ends. This is why we identify the name of the node with the sequence of individualizations necessary to reach the node: the sequence of individualizations necessary to reach is (#1,..., v%)) = u. (R, (,,,,) v) denotes the subtree of (ee,, x) rooted in v. We remark that the notation (G, x) simply means we apply tp to G and n, as noted in the lemma below. Isomorphism invariance of the IR tree follows from isomorphism invariance of Sel and Ref:
Lemma 1 (McKay & Piperno (2014)). Let 4:: V + V denote an automorphism of (G, i.e,, T), = (vvV), (()), :(T)) = E, = (G, Let Aut(G, T) denote all automorphisms of (G, Then, if v is a mode of T (R, T) and yp E Au)(G, then uP a node of Seet.se(G, and (G, n, u)f =
Seet,Se n. vP).
Generally, we refer to a process or object, as isomorphism-inuarian whenever it produces the same result for isomorphic inputs.
We want to remark again that leaves of an IR tree correspond to discrete colorings of a graph. In fact, the set of all leaves of an IR tree forms a complete isomorphism invariant: two isomorphic graphs will have the same set of leaves, whereas two non-isomorphic graphs are guaranteed to have distinct set of leaves (see Lemma 4 of McKay & Piperno 2014
Random IR walks. There are various ways to traverse and use IR trees. Traditionally, solvers (e.g., NaUty) solely used deterministic strategies, such as depth-first traversal (Mekay & Piperno, 2014). Only recently competitive strategics based solely on random traversal, i..,, DEJAVU (Anders & Schweitzer 2021a), have emerged (see Section ). We make use of this recent development, by using random root-to-leaf walks of the IR tree Rett, (G, R). We begin such a walk in the root node of (e, r). We repeatedly choose uniformly at random child of the current node until reach leaf v of the tree. Then, return the cetoorphimmiiivariant (Lemma
leaf v = (Wi,.... wk). A crucial property is that since Re (G, x) is random walks of I (a, R) are isomorphism-invarinn
as well:
Lemma 2 (Anders& & Schweitzer (202aa)) ). As a random variable, the graph colored with the coloring of the leaf resulting from a random IR walk is isomrphismmineurinn.
Lemma
2 is also true when restricting random walks to prefixes of a certain length d. We stress that random IR walks are conceptually unrelated to random walks in the graph itself considered elsewhere (Nikolentzos) & Vazirgiannis 2020). Our next step is to insert the sequence of nodes defined by random IR walks into MPNNs.
4.2 Individualization Refinement Node Initalization
Let G be graph with node representations {xI...., [p] and d N constant. Individualization--reeee node initalization (TRNT) computes random IR walk w (W1,... w..) in Taet,sa(G, r), where 7(i) == enc(æ;, G). If & 2 d, we take a prefix of length d, ie., (wi,..., wa), providing d nodes to be individualized. IRNI then concatenates d features that are either 0 or depending on this prefix: We set Ve E [1....,n) n) n. f- concatenate(( I w. 1 wwz=),, which means that the j-th feature of node v set to if is the j-th node that was individualized (i.c., Wy = v) and 0 otherwisc. This guarantees that node is individualized if and only it appears in the prefix. If < d, then we simply "fill up" the walk with nodes in ionnorphimm-ivvariant isomorphism invariant manner using the discrete coloring Ref(G, n, (Wi....,wy.. wx)): we add nodes in order of their color, first the node with the smallest color, then with the second smallest color, and so forth. We abbreviate IRNI with constant d as d-IRNI.
Due to the dependence on an underlying IR-tree, both the refinement Ref and cell selector Sel are natural hyperparameters of IRNL. Unless stated otherwise, we assume that an arbitrary refinement and an arbitrary cell selector are used. If we want to state a specific refinement or cell selector, we do so using d-IRNI(Ref) and d-IRNT(Reef, Sel), respectively.
8

---

Published in Transactions on Machine Learning Research (08/2023)
IRNI depends the random walk in the IR. tree and we will prove its universality in Theorem 4 Thus, IRNI is URF (analogous to RNT, CLIP, and RP). This justifies ensembling over this randomness, which we will refer to as ensembling over randomness (EoR). Specifically, we average the predictions of an MPNN over some URF.
We now define some specific instances of TRNT by applying different refinements. Let the trivial refinement TR(G, v) only individualize the vertices v in म, followed by no further refinement. A random walk of TTR (G, π) thus picks random permutation of vertices that respects only the initial color classes of (i.e., the first vertex will always be of the first selected color of π, and forth). In case of uncolored graphs (G, r) where æ is the trivial coloring, random walks truly only become random permutations of vertices of G. In this case, it follows that for G E 9n n-IRNI(TRR is equivalent to RP. However, we can enforce this even for colored graphs by actively ignoring the colors of т, resulting in what we call the oblivious refinement OR(G, n. v) == TR(G, V(G) H v. In this case, random walks are always random permutations of vertices of G. Hence, it follows that for G E In (OR) R.P. We remark that the only difference between RNI and RP is in the encoding of the individualizations
Based on TR and CR, we define CTR(G, T,) TR(G, CR(G, n, e), Note that CTR applies color refinement to the graph, followed by trivial refinement of nodes in the resulting color classes. By definition, for G E 9n (CIRNI(CTR) is thus an alternative description of CLIP.
4.3 IR algorithms and IRNI
We now discuss the relationship between IR algorithms and MPNNs using IRNL. First, we remark that in terms of solving graph isomorphism, the use of repcated random IR walks has recently been proven to be a near-optimal traversal strategy of IR trees (Anders & Schweitzer 2021b), where near-optimal refers to a logarithmic gap between the lower and upper bound. This is in contrast to deterministic traversal strategies such depth-first search or breadth-first search, which have a quadratic overhead (Anders & Schweitzer 2021b). URF are thus closely related to these optimal strategies. The ensembling defined in the previous section even seems to mimic the way the aforementioned near-optimal IR algorithm operates (Anders & Schweitzer 2021bb. In fact, the currently fastest practical graph isomorphism algorithm DEJAVU (Anders & Schweitzer 2021a] uses essentially the same strategy. Moreover, the use of random IR walks has additional inherent benefits, such as "implicit automorphism pruning", i.e., the automatic exploitation of symmetry in the input (Anders & Schweitzer 2021ab. This translates to MPNNs with IRNI, in that if individualizations across multiple random walks are made on nodes that are symmetrical to each other, this does not introduce any additional randomness: due to their camnorphism-ivvriiane (or equivariance), symmetrical nodes are indistinguishable by MPNNs by design.
Previously, we discussed that a crucial property of MPNNs is that their result is Somorphism-invariee i.c., it only depends on the isomorphism type. This is not true in the deterministic sense for IRNI. However, because of Lemma] 2 the result only depends on the isomorphism type and the randomness.
Lemma 3. Let Ref be any refinement. Let be the function computed by an MPNN with d-IRNI(Ref), mapping graph G and a random seed s E Q from the sample space of random IR walks Ω to value f(G, E R. Then for every permutation y, we have that the random variables + f(G,s) and s + f(p(G), s) have the same distribution.
Proof. The result follows directly from the isomophhism-invarianne of MPNNs and Lemma 2 Nevertheless, we give a more extensive proof here.
First, we recall that MPNNs are isomorphism-invariant (or equivariant): for every permutation so, by def- inition, a MPNN produces the same result for G as for (oG). Hence, we only need to proof that the augmentations made through random IR walks satisfy the claim.
We note that the IR tree of G is (G) and the IR tree of ((G) is (R))(p(G)) = p (G)) (soc Lemma in McKay & Piperno (0044)). Intuitively, this means that ignoring the permutation yp we are drawing randomly from the same distribution.
9

---

Published in Transactions on Machine Learning Research (08/2023)
Hence, randomly sampling walks from these trees will result in the same nodes, except for applying the permutation yp: if v E (C), then sp(v) E [R)r( We remark that G individualized with is isomorphic to ((G) individualized with v(v). This corresponds to the augmentation made to the MPNN in IRNI. Hence, overall, it follows that the MPNN must give the same result for G augmented with v, as well as (G) augmented with (p()).
We now provide a universality theorem for IRNI, in a similar fashion as Abboud el al. (2021) does for RNI. Let us first recall a definition of [bboud et al. (2021): let In denote the class of all n-vertex graphs and f: Gn + R. We say that some randomized function X that associates with a graph G E Gn a random variable ( is an (e, approximaooiioionnn.. of if for all Ge Gn it holds that Pr(If(G) - X(G) S c) 2 1 1 6.
The theorem proven by Abboud et al. (2021) is based on the fact that RNT fully individualizes a graph with high probability, and all fully individualized representations of a graph together constitute a complete isomrrphism invariant. The crucial insight we exploit is that IR trees constitute a complete isomorphism invariant as well, specifically, even the set of all leaves of an IR tree suffices. Since the power of MPNNs is limited by color refinement, the only additional requirement needed that the refinement used for random walks must be at most as powerful as color refinement.
Theorem 4. Let Ref be a refinement that computes colorings coorser or equal to CR, i.e., for any graph G = (V, E), coloring T,, and v E V*, Ref(G, v, is coarser or equal to CR(G, T.V) Let n 2 1 and let 9: - R be invariant. Then, for all c, > 0, there is an MPNN with (n - 1)-IRNI(Ref) that (c, 6) approzimates f.
Proof. We prove the theorem using a combination of Theorem 2 from (Morris et al. 2019), the universality result of RNIs given in (Abboud et al.) 2021), and the basic definition of IR trees. Since graphs have n nodes all possible random TR walks considered by (n - (ReI)N((Ree) are random IR walks ending in a leaf node of Tne .) (soe Scction 4.1.. If we were to individualize the soquence of nodes (Wi,...,wy, corresponding to leaf and apply the refinement Ref, the coloring of the entire graph would become discrete. By assumption, color refinement always produces colorings finer equal to Ref, so applying color refinement also produces a discrete coloring.
By the definition of (n- I)-IRN((Ref), the nodes contained in {wi,..., wx} all have distinct features not shared by any of the other nodes in the graph. This means that the nodes in {wi..... w& are indeed initially individualized the MPNN. Now, is well-known that Theorem of Morris al. (2019) (sce also (Xu et al. 2019)) shows that there is an MPNN that produces the same partitioning of colors that color refinement would, i.e., in our case, yields discrete partitioning of vertices. In other words, we can assume that the graph is individualized.
This suffices to apply the universality result of Abboud et al. (2021) (see Lemma A2, Lemma A3, and Lemma A4 in (Abboud et al. (021); which build upon (Barceló et al. 2020)), which solely depends on individualizing the graph. In particular, the proof of Abboud et al. (021) builds a C² sentence which identifies discretely colored graphs (Lemmn A3). In turn, a disjunction identifying any possible discretely colored graph for a given graph is constructed (Lemma A4). Since the set of leaves of an IR tree are a complete isomorphism invariant, it suffices to build this disjunction over only those discretely colored graphs that correspond to a leaf in the IR tree.
]
The hyperparameters of IR open up more opportunities to transfer results into the realm of MPNNs. We give one such example. We argue that with specific cell selector, 3-connected planar graphs can be detected with (CR..
Theorem 5.
Let Pn, denote the class of 9-connected planar graphs. Let n 2 1 and let f: Pn. + R be invariant. Then, for all e, > 0, there is a cell selector Sel (which does not depend on n) and an MPNN with 4-IRNI(CR, Sel) that (e, apprrrraprrs f.
Proof. First of all, we argue that individualizing a node of degree 5 and three of its neighbors surely suffices to make the graph discrete: this follows from Lemma 22 of Kiefer et al. (2017), which proves that individualizing 3 vertices on any common face followed by color refinement suffices to make the coloring discrete. Note that
10

---

Published in Transactions on Machine Learning Research (08/2023)
Method
PROTEINS
MUTAG
NCI
TRI
TRIX
EXP
CEXP
CSL
None
0.68 = 0.06
0.89 + 0.06
0.81 + 0.02
0.50 = 0.00
0.50 + 0.00
0.50 + 0.01
0.74 + 0.02
0.50 + 0.00
RNI
0.66 + 0.02
0.89 + 0.04
0.81 + 0.01
0.99
0.01
0.99
0.00
0.97 + 0,03
0.95
0.10
0.85 + 0.06
CLIP
0.65 = 0.05
0.85 0.09
0.81 0.01
0.99
0.00
0.81 = 0.05
0.99 = 0.04
0.99
0.02
1.00
0.01
RP
0.74 = 0.04
0.86 = 0.07
0.81 + 0.01
0.99
0.82 = 0.03
0.96
0.02
0.97
0.02
1.00 0.00
IRN[(CR)
0.75 +: 0.04
0.85 1 0.05
0.82 1 0.02
0.99
0.01
0.73 1: 0.04
0.99 1 0.04
0.95
0.14
1.00
0.00
RNI
0.69 = 0.05
0.94 + 0.03
0.85 + 0.02
1.00 + 0.00
1.00 = 0.00
0.99 + 0.01
0.98 + 0.05
0.93 + 0.06
CLIP BOR
0.67 = 0.03
0.92 = 0.05
0.82 = 0.02
1.00 = 0.00
0.95 + 0.05
1.00 = 0.00
0.97 + 0.08
1.00 = 0.00
RPE.R
0.78 + 0.04
0.84 = 0.12
0.87 + 0.02
1.00 = 0.00
0.95 + 0.05
1.00 = 0.00
1.00 + 0.00
1.00 = 0.01
IRNI(CR)
0.74 + 0.04
0.87 + 0.08
0.82 0.02
1.00
0.00
0.94 1 0.05
0.99 : 0.02
0.97 0.06
0.99 0.02
SOTA
0.81 = 0.03
0.95 = 0.03
0.88 + 0.01
0.91 + NA
0.93 + NA
NA
NA
NA
SO
0.77 = 0.04
0.94 + 0.04
NA
NA
NA
0.98 + 0.02
NA
0.91 + 0.07
Table 1: The AUROC of GIN network with RNI, CLIP, RP, IRNI(CR), and without any (None) of these selected data sets. Eoit indicates the use of ensembling over randomness. Bold entries indicate scatistically significant best values, for this EoR is treated as separate from no EoR. SOTAuRP indicates the state-of-thee art AUROC. SOTAURF indicates the state-of-the-arl accuracies, note that these are not directly comparable. Specifically, SOTAURF and SOTA refer to the results from the previous evaluations in (Murphy et al,
2019 Sato et al. 2021 Dasoulas et al. 2020 Abboud et al. 2021), from which we always chose the best value.
individualizing a node of degree 5 and three of its neighbors surely individualizes three vertices on common face. Using the arguments from the proof of Theorem 4 again, we can see that this would indeed suffice to show the claim.
It remains to be shown that there is a cell selection strategy achieving the above. In the first step, the cell selector chooses an (fsomrphisn-imvaaiint) color class consisting of degree 5 vertices. We remark that, due to Euler's formula, the average degree of a planar graph is less than 6, so such a node always exists. In the next step, we choose non-trivial class containing only neighbors of the individualized degree 5 node v. We argue that unless all neighbors of v have been individualized, there is a non-trivial color class consisting of neighbors of v. Indeed, if there is a non-trivial class containing neighbors of u, the class may only contain such neighbors since color refinement distinguishes neighbors of v from non-neighbors of v. Here we use that v is individualized. We repeat the step of choosing a non-singleton class of neighbors of v and individualizing a node within it. at any point no non-trivial class of neighbors exists, we are done: this means that the neighbors are fully discrete. This in turn suffices to show the claim.
More results of this kind can be shown. For example, it is known that strongly regular graphs require at most O( log n) individualizations (Babai 1980). In fact, for all but an exponentially small fraction of graphs, d-IRNI(CR) with small d suffices.
Theorem 6. There is an absolute constant c > 1 such that the following holds. Let n 2 1 and E N, then there is a graph class Gr containing all but at most a 1/edn fraction of all graphs for which the following holds. Let f: Gh + R be invariant, then, for all e, > 0, there an MPNN with d-IRNI(CR)) that (c, approcimates f.
Proof. To prove the theorem, we use the same technique as before. We only need to observe that for most graphs, after color refinement is applied, d arbitrary individualizations in non-singleton cells cause discretization of the graph. This, however, is a classic theorem by Babai & Kucera 1979 Theorem 4.1) showing the fraction of graphs for which this fails is at most d/cdn
5 Experiments
We compare the URF schemes RNI, CLIP, RP, and IRNI(CR) and verify their incrcase in expressivity. We do so by applying them to synthetically crafted, hard data sets well as standard practical data sets. Furthermore, we propose an automated training approach used throughout the benchmarks.
11

---

Published in Transactions on Machine Learning Research (08/2023)
Network architectures and optimization. For all experiments, we use the same general architecture, the Adam optimizer, and use the area under the receiver operating characteristic (AUROC). We optimize each method using a bayesian hyperparameter search in the same hyperparameter space. To estimate the perfor- mance, we use Monte Carlo cross-validation in an outer test loop and an inner validation loop estimating nested 10 x 9-fold cross-validation. The bayesian hyperparameter search is capped at evaluating 50 points in hyperparameter space. To encourage the models to optimize faster as well as to avoid overfitting, we add a penalty to the AUROC estimate based on some hyperparameters. The reported test AUROC does not include these penalties. To compute the node sequence for IRNI(CR) as well as the color refinement for CLIP we use DEJAVU (Anders & Schweitzer, 2021a). These choices are specified further in the appendix. In the following, we refer to a GIN without any URF as None, while we refer to a GIN with some initialization as RNI, CLIP, RP, or IRNI(CR) depending on the URF that is used. Each of these methods is also limited in the number of dimensions added.
Data sets. We evaluate different models on datasets used in prior work on URF, specifically EXP, CEXP, TRI, TRIX, CSL, PROTEINS, MUTAG, and NCI1 (Srinivasan et al. Borgwardt et al. 2005 Wale & Karypis 2006 Murphy et al., 2019 Sato et al. 2021 Abboud et al., 2021). EXP, CEXP, TRI, TRIX, and CSL are synthetic data sets made up of graphs not distinguishable by the color refinement algorithm. TRI and TRIX contain 3-regular graphs and use the same training set while differing in the test set. The task is to detect triangles. EXP and CEXP consist of graphs carefully constructed so that each graph is in pair that is indistinguishable by color refinement while encoding a satisfialle and unsatisfiable formula respectively. For CEXP 50% of all satisfiable graphs are modified to be distinguishable by color refinement from their unsatisfiable counterparts. CST consists of 41-cycles with regular skip-connections according to 10 co-primes of 41. Each co- co-prime defines one class for the CSL task. The results of this experiment can be found in Table 1
6 Discussion
We notice that on the synthetic hard datasets TRI, TRIX, EXP, CEXP, and CSL, all methods improve the discriminatory power compared to not using any form of URF. We now compare the methods based on the three primary parameters encoding, ensembling, and refinement.
Concerning the encoding on TRIX and CSL, there seem to be noticeable differences between RNI and the other methods. The poorer performance of CLIP, RP, and IRNI(CR) on TRIX is easily explained. Since the task is to detect triangles locally in the graph and the graph is regular, an individualization is required close to the triangle to be able to detect it. RNI individualizes everywhere simultancouslyy, while CLIP, RP, and [RN only individualize locally. This means the detection of triangles depends on random chance. EoR helps since it increases this chance. The difference on CSL is not so clearly explainable. We do not know why RNI performs significantly worse here. Looking more specifically at the difference between RP and RNI, we remark that RP substantially outperforms RNI on PROTEINS, while RNI outperforms RP on MUTAG.
EoR appears almost always to improve the performance. As such we would advise its consideration whenever one of these URF is used in practice. Notice that its use does not increase training time and only linearly increases prediction time. FoR also appears to guarantee that at least one of RNT, CLIP, RP, or IRNI(CR) will outperform models without this expressibility increase.
Considering the methods that use additional refinement to reduce the introduced randomness, namely CLIP and IRNI(CR), we observe they outperform RP on MUTAG, while RP outperforms the other two on PRO- TEINS and NCII. On the synthetic hard datasets, in particular with ensembling, the three met perform very similarly.
Overall, no method appears to be the uniformly best method for practical use. We suspect that overfitting to the different features introduced by RNI, CLIP, RP, and IRNI(CR) plays a significant role in which of these URF performs best.
12

---

Published in Transactions on Machine Learning Research (08/2023)
7 Conclusion
We introduced IR as it applics to machine lcarning in the form of the IRNI framework. This enables the development of many URF based on selecting refinement, cell selector, and how to encode individualizations into the network. No URF introduced so far is the clear front runner. However, the BHO tuning approach presented here feasibly allows for the optimization of the IRNI hyperparameters in addition to other model hyperparameters. The IRNI hyperparameters also serve the unifying IRNI umbrella, as we were able describe all existing and URF based these. Moreover, IRNI has rigorous theoretical foundation ensuring equivariance and universality. We hope this will aid in systematic improvements in future research regarding GNNs. Practically, our findings imply that for each new graph learning task all mentioned URF need to be evaluated to determine the best fit.
Acknowledgement
We thank the reviewers for their constructive feedback that helped improve the paper. The authors ac- knowledge support by the Carl-Zeiss Foundation, the BMWK award 01MK20014U, the DFG awards KL 2698/2-1, KL 2698/5-1, KL 2698/6-1 and KL 2698/7-1,and the BMBF awards 01 S11805A,, 03|B0770E, and S21010C. The research leading to these results has received funding from the European Research Coun- cil (ERC) under the Europcan Union's Horizon 2020 research and innovation programme (EngagoS: grant agreement No. 820148).
References
Ralph Abboud, ismail Îlkan Ceylan, Martin Grohe, and Thomas Lukasiewicz. The surprising power of graph neural networks with random node initialization. In Zhi-Hua Zhou (ed.), Proceedings of the Thirlieth International Joint Conference Artificial Intelligence, IJCAI-21, pp. 2112 2118. International Joint Conferences on Artificial Intelligence Organization, 8 2021. doi: 10.24963 222463/ijcaii.000 /ijcaaa..22/22991 URL https: //doi.org//i 11t/110..9993/jcaa11 2011/291 Main Track.
Markus Anders and Pascal Schweitzer. Engineering fast probabilistic isomorphism test. In Martin Farach- Colton and Sabine Storandt (eds.), Proceedings of the Symposium Algorithm Engineering and Ex- periments, ALENEX 2021, Virtual Conference, January 10-11, 2021, pp. 73 84. SIAM, 2021a. doi: 10.1187/1.771161117677722 URL https://doi.orge: 10. 1137/1 9781611976472.6
Markus Anders and Pascal Schweitzer. Search Problems in Trees with Symmetries: Near Optimal Traver- sal Strategies for IndividualliationnRReen
Algorithms. In Nikhil Bansal, Emanuela Merelli, and James Worrell (eds.), 48th International Colloquium on Automata, Tanguages, and Programming (ICALP 2021). volume 198 of Leibniz International Proceedings in Informatics (LIPIcs). pp. 16:1-16:21, Dagstuhl, Germany, 2021b. Schloss Dagstuhl Leibniz-Zentrum für Informatik. ISBN 978-3-95977-195-5. doi: Btt30/LIPIcs..CAL......
URL
László Babai. On the complexity of canonical labeling of strongly regular graphs SIAM J. Comput., 9(1):
212-216, 1980. doi: 10.1137/0209011 URL https://doi.org/: 1137702090118
László Babai and Ludek Kucera. Canonical labelling of graphs in linear average time. In 20th Annual Symposium on Foundations of Computer Science, San Juan, Puerto Rico, 29-31 October 1979, pp. 39 46. IEEE Computer Sociely, 1979. doi: 10.1109/SFCCS.1999.5
/tttp:///boo..ogg/00.000/////// 1979
8
Pablo Barceló, Egor V. Kostylev, Mikaël Monet, Jorge Pérez, Juan L. Reutter, and Juan Pablo Silva. The logical expressiveness of graph neural networks. In 8th International Conference Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020. URL
Andrew R Barron. Approximation and estimation bounds for artificial neural networks. Machine learning. (411:115-113) 1994.
13

---

Published in Transactions on Machine Learning Research (08/2023)
Igor I Baskin, Vladimir A Palyulin,, and Nikolai S Zefirov. A neural device for searching direct correlations between structures and properties of chemical compounds. Journal of chemical information and compuler sciences, 37(4):715 721, 1997.
Karsten M Borgwardt, Cheng Soon Ong, Stefan Schönauer, SVN Vishwanathan, Alex J Smola, and Hans- Peter Kriegel. Protein function prediction via graph kernels. Bioinformatics, 21(suppl 1):44 156, 2005.
George Cybenko. Approximation by superpositions of a sigmoidal function. Mathematics of control, signals and systems, 2(4): -344,, 1989.
George Dasoulas, Ludovic Dos Santos, Kevin Scaman, and Aladin Virmaux. Coloring graph neural net- works for node disambiguation. In Christian Bessiere (ed.), Proceedings of the Twenty-Vinth Interna- tional Joint Conference on Artificial Intelligence, IJCAI-20, pp. 2126-2132 International Joint Con- ferences on Artificial Intelligence Organization, 7 2020. doi: 10.24963 1124963/jjcai.. (jjcai.22002999 org/o.0 22tp///..2993/jjaa... 2020/294 Main track.
URL https:
Kaize Ding, Zhe Xu, Hanghang Tong, and Huan Liu. Data augmentation for deep graph learning: A survey. arXiv preprint vrXXi=2202.08235 2022.
David K Duvenaud, Dougal Maclaurin, Jorge Iparraguirre, Rafael Bombarell, Timothy Hirzel, Alan Aspuru- Guzik, and Ryan P Adams. Convolutional networks on graphs for learning molecular fingerprints. In C. Cortes, N. Lawrence, D. Lee, M. Sugiyama, and R. Garnett (eds.). Advonces in Newral Information Processing Systems, volume 28. Curran Associates, Inc., 2015. URL htt.:::/t////// ttttps://procceddnng httpeeediinnn.nnuriiipe meurips.rc..m cc/ pdff
Justin Gilmer, Samuel S. Schocnholz, Patrick F. Riley, Oriol Vinyals, and George E. Dahl. Neural message passing for quantum chemistry. In Doina Precup and Yee Whye Teh (eds.), Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pp. 1263-1272. PMLR, 06-11 Aug 2017. URL http::/pproceedngg....... mlr press/ ppwss//00/gttis 1et00//immee11aa/
Marco Gori, Gabriele Monfardini, and Franco Scarselli. A new model for learning in graph domains. Tn Proceedings. 2005 IEEE International Joint Conference on Neural Networks, 2005., volume 2, pp. 729-734 vol. 2, 2005. doi: 10.1109/IJGNI 2005.1555942 1555942.
William L. Hamilton, Rex Ying, and Jure Leskovec. Representation learning graphs Methods and applications. IEEE Data Eng. Bull., 40(3):52-74, 74, 2017. URL http::/ssites.compptt cumpptter.or/ddbulll/
A17sept/p52.pdl
Tommi A. Junttila and Petteri Kaski. Conflict propagation and component recursion for canonical label- ing. In Alberto Marchetti- Sprccatti-Spaccamlla and Michael Sogal (ods.), Theory and Practice of Algorithms in
(Compuler) Systems First International ICST Conference, TAPAS 2011, Rome, Ilaly, April 18-20, 2011. Proceedings, volume 6595 of Lecture Notes in Computer Science, pp. 151-162. Springer, 2011. doi: 16. URL https://doi. :ttt:::/oo1.org///0000///////
Sandra Kiefer, Ilia Ponomarenko, and Pascal Schweitzer. The weisfeiler-leman dimension of planar graphs is at most 3. In 32nd Annual ACM/IEEE Symposium Logic in Computer Science, LICS 2017, Reykjavik, Iceland, June 20-23, 2017, pp. 1-12. IEEE Computer Society, 2017. doi: N1.100//LICS.22117.005150 URL httpp://dol. org/ 10. 1109/LICS. 80005007
Moshe Leshno, Vladimir Ya. Lin, Allan Pinkus, and Shimon Schocken. Multilayer feedforward networks with a nonpolynomial activation function can approximate any function. Newral Networks, 6(6):861 867, 1993. ISSN 0893-6080. doi: huups//0biooog//10000////3330000 wwwencedireettccmm occhrcccccc...ooccccccrrrreeeaap
URL https://www.
Yujia Li, Daniel Tarlow, Marc Brockschmidt, and Richard S. Zemel. Gated graph sequence neural networks. In Yoshua Bengio and Yann LeCun (ods.), 4th International Conference on Learning Representations,
ICLR 2016, San Juan, Puerto Rico, May 2-4, 2016, Conference Track Proceedings, 2016. URL http:
05493
14

---

Published in Transactions on Machine Learning Research (08/2023)
Shiyu Liang and R. Srikant. Why deep neural networks for function approximation? In 5th International Conference on Learning Represenlations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings. OpenReview.net net, 2017. URL
net wtt.://ooorriiiisssss...e
Zhou Lu, Hongming Pu, Feicheng Wang, Zhiqiang Hu, and Liwei Wang. The expressive power of neural networks: A view from the width. In Proceedings of the 31st International Conference on Neural Infor- mation Processing Systems, NIPS'17, pp. 6232 6240, Red Hook, NY, USA, 2017. Curran Associates Inc. ISBN 9781510860964.
Haggai Maron, Heli Ben-Hamm,, Hadar Serviansky, and Yaron Lipman. Provably powerful graph networks. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Bue, E. Fox, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019a. URL https: //proceedings.o wwwrips....pp... hwtpe/ewwwwg..ue...pp.pp/aa////e
Haggai Maron, Heli Ben-Hamnt Nadav Shamir, and Yaron Lipman. Invariant and eqquvariint graph networss. In International Conference Learning Representations, 2019b. URL hiRLL/ttsss//penneriiseeee/////o
id Syx72jc9m
Brendan D. McKay. Practical graph isomorphism. In 10th. Monitoba Conference on Numerical Mathematics and Computing (Winnipeg, 1980), pp. 45 87, 1981.
Brendan D. McKay and Adolfo Piperno. Nauty and traces user guide. anu. edu. wwwpaaple//reennecceca hww.a//aaanaa///aatunngg/5 pdf
https://cs wtt.///ssauuuuae/eaaa/aae
Brendan D. McKay and Adolfo Piperno. Practical graph isomorphism, ii J. Symb. Comput., 60:94-112,
January 2014. ISSN 0747-7171. doi: 10.1016/1.sc.22133.0000 URL
jac.
0013.09.003
Christopher Morris, Nils M. Kriege, Kristian Kersting, and Petra Mutzel. Faster kernels for graphs with continuous attributes via hashing. In 2016 IEEE 16th International Conference on Data Mining (ICDM), pp. 1000- 2016. doi: 20.100//
Christopher Morris, Martin Ritzert, Matthias Fey, William L. Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe. Weisfeiler and leman go neural: Higher-order graph neural networks. Proceedings of the AAAI Conference Artificial Intelligence, (31):)46002 4609, Jul. 2019. doi: 1.1609/aaai.vaa 33014602. URL https://ojs.... aaai. wat.://aaaaa.rr///ooooo/ wwwpnddx.php//AA... phtp/AAA/AArttccc///////////
Christopher Morris, Nils M. Kriege, Franka Bause, Kristian Kersting, Petra Mutzel, and Marion Neumann. Tudataset: A collection of benchmark datasets for learning with graphs. CoRR, abs/2007.08660 2020a.
URL stttps//arxiv..ott has///bs/220 2ttas//007.00850
Christopher Morris, Gaurav Rattan, and Petra Mutzel. Weisfeiler and Leman go sparse: Towards scalable higher-order graph embeddings. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Bal- can, and H. Tin (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 21824- 21840. Curran Associates, Inc., 2020b. URL 33111445882221444402220688888883
Christopher Morris, Matthias Fey, and Nils Kriege. The power of the weisfeiler-leman algorithm for machine learning with graphs. In Zui-Hua Zhou (ed.), Proceedings of the Thirtjeth International Joint Conference Arlificial Intelligence, IJCAT-21, pp. 4543 -550. International Joint Conlerences on Artificial Intelligence Organization, 8 2021. doi: 10. 10.24963/ijoc 2021//18.. URL Survey Track.
Ryan Murphy, Balasubramaniam Srinivasan, Vinayak Rao, and Bruno Ribeiro. Relational pooling for graph representations. In International Conference on Machine Learning, pp. 4663 4673. PMLR, 2019.
Daniel Neuen and Pascal Schweitzer. Benchmark graphs for practical graph isomorphism. In Kirk Pruhs and Christian Sohler (ods.), 25th Annual European Symposéum on Algorithms, ESA 2017, September 4-6, 2017, Vienna, Austria, volume 87 of LIPIcs, pp. 60:1-60:14. Schloss Dagstuhl- Leibniz- Zentrum für Informatik, 2017. doi: 10.4230/L.IPlcs. ESA. 2017.60. URL httph:ttt:://e.t.
4230//II..3//IIIIc..c. ESA. ESA.2017.66
15

---

Published in Transactions on Machine Learning Research (08/2023)
Maximilian Nickel, Kevin Murphy, Volker Tresp, and Evgeniy Gabrilovich. A review of relational machine learning for knowledge graphs. Proceedings of the TEEE, 104(1):11-38) 2016. doi: 10.1109/JPROC:2015 2483592.
Giannis Nikolentzos and Michalis Vazirgiannis. Random walk graph neural networks. In Hugo Larochelle, Marc'Aurelio Ranzato, Raia Hadsell, Maria-Florina Balean, and Hsuan-Tien Lin (eds.), Advonces in Newral Information Processing Systems 33: Arenual Conference Neural Information Processing Systems 2020, meurips.cc/pappe
NewrIPS 2020, December 6- 12, 2020, virtual, 2020. URL
Caleb C. Noble and Diane J. Cook. Graph-based anomaly detection. In Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD '03, pp. 631-636, New York, NY, USA, 2003. Association for Computing Machinery. ISBN 1581137370. doi: 10.1145/ 956750.956831. URL https://dol. wwt/ 111.:/11111199950001110
Pål András Papp, Karolis Martinkus, Lukas Faber, and Roger Wattenhofer. Dropgmn: random dropouts increase the expressiveness graph neural networks. Advances in Neural Information Processing Systems, 34:21997- 22009, 2021.
Adolfo Piperno. Isomorphism test for digraphs with weighted edges. In Gianlorenzo D' D'Angelo (ed.), 17th International Symposium Experimental Algorithms, SEA 2018, June 27-29, 2018, L L'Aquila, Italy, volume 103 of LIPIcs, pp. 30:1-30:13. Schloss Dagstuhl- Leibniz-Zentrun für Informatik, 2018. doi: /.220///.PIcs.SEA.... 2018.30.. URL https://doi.... org/ 10. 4w30/L2IIIsss..... .EE.I....................... 2018.30
Omri Puny, Heli Ben-Hamm and Yaron Lipman. Global attention improves graph networks generalization. arXiv preprint ar Xiv:20006. 07846, 2020.
Maithra Raghu, Ben Poole, Jon Kleinberg, Surya Ganguli, and Jascha Sohl-Dickstein. On the expressive power of deep neural networks. In international conference on machine learning, pp. 2847 2854. PMLR, 2017.
Ryoma Sato, Makoto Yamada, and Hisashi Kashima. Random Fealures Strengthen Graph Neural Networks, pp. 333 341. 2021. doi: 1011187/19781611176700000 1. 1.9781611976700.33
URL httpttt///ppbbb:: siam. wttp//////b///..111111
Franco Scarsolli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE Transactions on Neural Networks, 20(1):61 80, 2009. doi: 10.1109/TMM 2008.2005605.
Nino Shervashidze, Pascal Schweitzer, Frik Jan van Leeuwen, Kurt Mehlhorn, and Karsten M. Borgwardt. Weisfeiler-Lehman graph kernels. Journal of Machine Learning Research, 12:2539 2561, 2011.
URL
http://dl. acm. wwt.:/aam...//ccc./// citation.
cfm?id=2078187 http:iaaiii....fmmm222011111
Weiping Song, Zhiping Xiao, Yifan Wang, Laurent Charlin, Ming Zhang, and Jian Tang. Session- social recommendation via dynamic graph allention networks. In Proceedings of the Twelfth ACM International
Conference on Web Search and Data Mining, WSDM '19, pp. 555 555,563, New York, NY, USA, 2019. URL https:
Association for Computing Machinery. ISBN 9781450359405. doi: 7/doi org/10. 1145/3289600.3222 32999998
Alessandro Sperduti and Antonina Starita. Supervised neural networks for the classification of structures. IEEE Transactions on Neural Networks, 8(3):714-78)) 735, 1997. doi: 11.1109/2..52208..
A Srinivasan, S Muggleton, M Sternberg, and R King. Theories for mutagenicity: study of first-order and feature-based induction. Artificial Intelligence, 85(1):2.
Bowen Tang, Skyler T Kramer, Mcijuan Fang, Yingkun Qiu, Zhen Wu, and Dong Xu. A self-attention basod message passing neural network for predicting molecular lipophilicity and aqueous solubility. Journal of Cheminformatics, 12(1):1-5 9, 2020.
16

---

Published in Transactions on Machine Learning Research (08/2023)
Michalis Vazirgiannis, Fragkiskos D. Malliaros, and Giannis Nikolentzos. GraphRep: Boosting text mining, NLP and information retrieval with graphs. In Proceedings of the 27th ACM International Conference on Information and Knowledge Management, CIKM '18, pp. 2295 2296, New York, NY, USA, 2018. URL https:
Association for Computing Machinery. ISBN 9781450360142. doi:
//doi.org/10 10. 1145/32692066666 3274273.
Pelar Velickovic, Guillem Cucurull, Aranixa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 - May 3, 2018, Conference Track Proceedings. OpenReview.net 2018.
URL https://openreviiet net seet/forumiiddxIXpppii
Nikil Wale and George Karypis. Acyelic subgraph based descriptor spaces for chemical compound retrieval and classification. Technical report, University of Minnesota, 2006.
Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and Philip S. Yu. comprehensive survey on graph neural networks. IEFE Transactions on Newral Networks and Learning Systems, 32(1): 4 24, 2021. doi: 10.1109/TTNIIS 20L.1//TNNN...200.220000
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka, How powerful are graph neural networks? In International Conference on Learning Representations, 2019. URL http:::/opppereriiee httpss//pppparreeeeeeeeeerooodod www.oormnneeoooo ryGa61A5Km
Rex Ying, Jiaxuan You, Christopher Morris, Xiang Ren, William L. Hamilton, and Jure Leskovec. Hierar- chical graph representation learning with differentiable pooling. In Proceedings of the 32nd International Conference on Newral Information Processing Systems, NIPS'18, pp. 4805-4815, Rod Hook, NY, USA, 2018. Curran Associates Inc.
Ding- Xuan Zhou. Universality of deep convolutional neural networks. Applied and Computational Harmonic Analysis, 7874) 2020. ISSN 1063-5203. doi: http:///bb.oor///.000//.aaaa.a 20....99.............0.. URL https://ww..sciencele http://wwwwaaieeceoooeeeeeeaaaaa
Jie Zhou, Ganqu Cui, Shengding Hu, Zhengyan Zhang, Cheng Yang, Zhiyuan Liu, Lifeng Wang, Changcheng Li, and Maosong Sun. Graph neural networks: A review of methods and applications. Al Open, 1: 57-81, 2020. ISSN 2666-6510.
doi:
20t......00.2..000000.... URL httpps:/www.
sciencedirect.
A Refinement Definition
We discuss the slight technicality in our definition refinement in the individuulizatton--efeeeee paradigm. Compared to McKay Piperno (2014), we are lacking the requirement that n' Ref æ, v/ must be finer than v, making our definition of refinements slightly more general. With respect to the results, this implies that for (non-trivially) colored graphs, discrete refined colorings might not respect the initial coloring. This potentially lead to issues with automorphisms and canonization since, essentially, the isomorphism invariant implicd by the refinement is too weak. However, there is simple fix using other components of the IR framework: we make use of invariants, which are not immediately relevant for IRNI itself. Whenever a coloring n' a node v in the tree is discrete, we can use the complete isomorphism invariant (G" .=') (note that since T' is discrete, also defines permutation on the vertices of G). Lc., we identitfy the node with the invariant (G*', x²)) As mentioned above, this does not influence any of the results of this paper directly it only serves to make the description sound in terms of the further discussion in McKay & Piperno 22014). We refer to McKay & Piperno (2014) for in-depth discussion of invariants.
B Relational Pooling
Relational pooling (RP) Murphy al. (2019) is more general than discussed in this paper. In its initial
formulation VV. Exesy [[ X*) it is not tractable and does thus not fit. into the comparison considered
17

---

Published in Transactions on Machine Learning Research (08/2023)
Table 2: The hyperparameter space for bayesian hyperparameter optimization. Penalty describes how the
parameter influences the hyperparameter optimization.
Parameter
batch size
epochs
learning rate
weight decay
features
layers
dimensions
step size
FoR
Minimum 8
32
le-6
lc-10
0.01
Maximum 256
512
le-2
1e-0.3
128
10
5
1.0
64
Data-Type Integer
Integer
Real
Real
Integer x/128
Integer
Integer None
Real None
Integer
Penalty (xxX/566)
x/512
None
None
x/10
x/64
here. In the original paper, three methods to make RP tractable are discussed. The first uses canonization, which itself is generally not tractable, and thus is not considered. The third uses fixed point tractable (FPT) formulation (essentially describing less expressive version of the k-dimensional WL algorithm), which is generally not universal unless the FPT paramcter is not fixed, and even then its costs are polynomial in the FPT parameter which is computationally too expensive for this comparison. Only the second discussed option, which is originally motivated by stochastically estimating the initial formulation, both universal and computationally practical, which is why it considered here. In particular, it also the only version implemented and tested in the original paper.
C Edge Coloring
We discuss the differences when using edge colors since the MUTAG data set contains edge labels, which we consider in the experiments.
In order to handle edge colors in DEJAVU for color refinement and random IR walks, we made the following modifications. We encode edge colors as vertex colors: we subdivide each edge of the graph using vertex and color that vertex according to the color of the edge. Then, we ensured that the cell selector never selects nodes that were inserted to subdivide edge, i.., the solver can still only individualize vertices that truly correspond to the original vertices of the graph.
We want to note that there is a more efficient albeit more involved way of resolving the issue Piperno 2018
D Color Encoding
We discuss preciscly how we encoded colors for the data sets discussed in this work. First, notice that we need to encode labels for nodes and for edges. We used the same method to encode colors for both. Almost all node and edge features can be considered binary numbers due how the data sets are encoded. The only exception to this rule is the PROTEINS data set which has natural number followed by a binary number. Thus, we simply read the node and edge features a binary number, where the first bit has the highest order, and the last bit has the lowest order. This ensures that node and edge features are encoded as different natural mumbers the original features were different. However, due to the size of natural numbers, that specifically the NCI1 dataset produces, as it has 37 node features, we also apply a modulo operation by 12345.
E
Experiments
Network architecture. Each MLP in each GIN layer has three layers (input, hidden, output) that widen to fixed number of features as soon as possiblc and remain there throughout all subsequent layers. The input and hidden layers of every MLP are followed by a batch-norm operation. For graph classification tasks, we use global mean pooling followed by a linear transform and dropout with = 0.5. We use the node embeddings after each GIN layer in this way and sum over all of them for the final graph represontation. As activation functions, we use only ReLU, For node-clasiffiction tasks, we do the same before without the global mean pooling.
18

---

Published in Transactions on Machine Learning Research (08/2023)
Bayesian hyperparameter optimization. We optimize over the batch size, the number of epochs, the learning rate, weight decay, the number of features the GIN layers expand to and operate on, the number of GTN layers, the number of dimensions added for the node initializations, the fraction of epochs after which the learning rate gets decrcased by 0.5 consecutively, and the number of random samples for EoR. Table 2 describes the hyperparameter space used for the experiments. For indepth description each parameter:
Batch size refers to the batch size used during training. The smaller it is, the more it penalizes the evaluation metric during the bayesian hyperparameter search.
Epochs refers to the number of epochs used during training. The bigger they are, the more they penalize.
Learning rate refers to the initial learning rate used inside of the Adam optimizer.
Weight decay refers to the typical weight decay parameter inside of the Adam optimizer.
Features refer to the number of features the MLPs inside of the GIN layers expand to. Each node will have features many features after the first GIN layers first MLP layer. The more features, the more they penalize.
Layers refer to the number of layers of the GIN networks. The more layers, the more they penalize.
Dimensions refer to the number of dimensions each node's features expanded by for the new features introduced by the different URF methods. This parameter is the same the d in d-IRNI.
Step size is a relative parameter that influences how the learning rate changed during training depending on the number of epochs. For instance, if the number of epochs is set at 100, then step size of 0.1 will mean the learning rate is divided by 0.5 every 10 epochs, a step size of 0.5 would mean the learning rate is divided by 0.5 once after 50 epochs, and step size of 1 indicates the learning rate is never dropped.
EoR refers to the number of random samples that are used to estimate the output of the network. For instance, for an EoR of 10 the input is modified 10 times i.i.d using the URF of choice. All 10 inputs are then passed through the network and the final predictions are then averaged for all 10 outputs.
Tables 4
19 show the mean and standard deviation of the best-found hyperparameters across their soeds for all the datasets and methods. For the learning rate and weight decay, only the exponent is given.
Monte Carlo cross-validation. Each dataset is split using stratified 10-fold cross-validation with random shuflling. The first fold is used as the test set and the 9 others are used for bayesian hyperparameler optimization. After the best model is found, it is trained on all 9 folds and its performance the test set is reported. This is repeated 10 times with different random shuffles. If the dataset initially already provides a test set, then the bayesian hyperparameter optimization is repeated for 10 different seeds. In the inner loop, which we referred to before as just bayesian hyperparameter optimization, the data is split using stratified 9-fold cross-validation. The first fold is used as a validation set and the other 8 folds are used to train the model, after which its performance is reported on the validation set. This repeated times with different random shuffles. This essentially estimates nested 10 x 9-fold vals-aaliit The 10 and 3 were chosen based time budget. The performance on PROTEINS, MUTAG, and NCT1 is particularly sensitive to the variance in the performance estimate, so expect to see an improved performance if more estimates are used.
Test system and time budget. made up of:
The system that was used to do the experiments mentioned in this work is
#60-Ubuntu SMP Tue Jul 2 18:22:20 UTC 2019 -.150--55-
19

---

Published in Transactions on Machine Learning Research (08/2023)
Table 3: The time in seconds for the entire evaluation process of seed of a GIN network with RNI, CLIP, RP, [RR)(CR), and without any of these selected data sets. Eoft indicates the use of ensembling over vandomness.
Method
PROTEINS
MUTAG
NCI
TRI
TRIX
EXP
CEXP
CSL
None
25672 5426
7275 5532
121487
63237
10878 +: 2328
10809 2288
20735
19652 :: 5739
2286
RNI
16968
27607
46855
53381
35114
4512
CLIP
36189 10374
12268 + 3955
151003
36904
52437 + 19898
48608
20161
65397
13000
55558 + 13902
10697 3146
RP
26042 + 8782
8783 + 2234
126282
36043
56640 + 35035
48930 + 34016
62605 + 29282
53750 + 25979
6321 + 1917
IRNI
33383 + 13685
7793 + 1560
156317 + 35831
12451 # 13367
40597 = 15643
61123 + 13112
50012 # 14155
10937 = 1895
RNLEot
26593 1: 9390
7810 +: 3740
106401
30762
26766 + 10270
25630 +: 14628
34604 +: 12037
33747 + 9654
8832 + 6506
CLIP Soo
65225
31132
8418 1: 2048
118096
17091
24487 1: 4718
28594 6917
38563 1: 7954
82525 1: 17467
6810 1807
RPEER BoR
6309
43888
22385 7073
31831 13730
2271
ERN
31337 12360
8204 3483
160859 55380
33799 + 4711
61533 21959
52990 13094
75701 + 18933
5528 1360
Table 4: The mean and standard deviation for each found hyperparameter for each method on the PRO-
TEINS dataset without FoR.
Parameter
batch size
epochs
learning rate
weight deray
features
layers
dimensions
step size
Noue
83.17
278.10 +: 185.29
3.21 0.76
5.12 1 2.72
76.00 = 35.85
5.80 -: 1.78
3.30 1.68
0.53 0.32
RNI
86.30 +: 82.32
303.50 +: 131.03
3.53
1.53:.0.80 0.89
5.72 2.14
59.50 = 41.13
5.30
3.30 +: 1.27
0.63 0.29
CLIP
141.90 93.62
224.20 = 140.10
-3.61 3.61:1000 1.06
2.70
60.40
38.66
3.80 1.33
3.60 1.50
0.58 0.30
RP
192.70
52.98
52.98
262.50 = 162.44
0.66
3.22
55.00
35.34
2.80 1.17
4.10
0.55 0.33
IRNI
308.30 = 165.17
1.17
-7.45
72.40 48.31
3.00 1.34
3.20 1.47
0.45 0.25
2 Intel(R) Xeon(R) Gold 6154 CPU @ 3.00GHz
754GiB System memory
10 GeForce RTX 2080 Ti
The experiments took approximately 20 days without testing and approximately 1 month with testing, where the machine was not used on full load always. Table shows the computation time in scconds for seed for each the methods on each separale dataset.
Python libraries. We used python 3.8.10 to implement all the models and conduct all the experiments:
dejavu-gi 0.1.3 (for IRNI(CR))
networkx 2.6.3 (for constructing TRI and TRIX)
numpy 1.21.4
scikit-learn 1.0.1
scikit-optimize 0.9.0 (for Bayesian hyperparameter optimization)
scipy 1.7.3
torch 1.10.0
torch-geometric 2.0.2 (specifically for graph related machine learning)
Random Seod For the experiments we used the random scods through as input to our code. However, our experiments might not be perfectly reproducible as DEJAVU the package we use to caleulate random IR. paths does not allow for its seed to be set.
20

---

Published in Transactions on Machine Learning Research (08/2023)
Table 5: The mean and standard deviation for each found hyperparameter for each method on the MUTAG
dataset. without FoR
Parameter
batch size
epochs
learning rate
weight decay
Ieatures
layers
dimensions
step size
None
157.10 +: 78.41
329.80 +: 152.31
3.67 1 0.63
6.36 1: 2.25
72.30 +: 32.85
5.70 +: 3.07
2.90 + 1.51
0.61 +: 0.30
RNI
145.10 +: 90.67
315.40
150.22
33.25 = 0.78
2.22
55.40 + 30.11
5.80 2.79
3.60
+ 1.43
0.76 :: 0.24
CLIP
142.20 + 94.73
208.90 + 139.70
-3.11 = 0.91
-7.12
102.30 = 17.73
6.30 2.93
2.90
+ 1.14
0.68 0.27
RP
181.90 = 64.39
256.20
+ 131.57
-3.07 = 0.77
-6.27
3.09
55.10 = 29.18
6.00 2.97
3.80
- 0.98
0.61 0.30
IRNI
167.20 + 78.88
371.80
+: 120.38
-3.21 # 1.09
-5.81 4: 3.25
68.10 +: 40.89
5.80 3.09
2.80
1.47
0.62 :: 0.27
Table 6: The mean and standard deviation for each found hyperparameter for each method on the NCII dataset without FoR
Parameter
batch size
epochs
learning rate
weight decay
festures
layers
dimensions
step size
None
75.20 60.04
270.60 1 138.40
-3.78 1 0.85
-5.43 1. 2.02
91.10 10011:20000 28.83
7.00
2.05
3.40 1.11
0.65 0.32
1.00 1 0.00
BNI
103 59.22
308 84.42
-2.77 4.73
-3.22 1.99
89.50
32.23
6.00
1.55
3,00 1.73
1.22:0023
1.00 0.00
CLIP
131.75
117.57
7.38
1.00
ORNI
157.00 81.81
362 70 13188
0.72
-6.06
2.200
69.00
22.95
3.40 + 1.69
3.30 = 1.19
0.45
1.00 0.00
IRNI
93.12 : 83.31
369.38 +: 93.77
-3.88 0.61
-6.40 2:22
103.50
26.80
8.12 1:2:2:2 2.32
1.12 = 0.33
0.37 0.29
1.00 0.00
Table 7:
The mean and standard deviation for each found hyperparameter for each method on the TRI
dataset without EoR
Parameter
batch size
epochs
learning rate
weight decay
features
layers
dimensions
step size
None
256.00 + 0.00
32.00 + 0.00
-4.15 + 1.90
-4.15
4.71
16.00 = 0.00
2.00 + 0.00
3.80 1.83
0.50 0.49
RNI
132.50 +: 91.25
454.30 55.92
-2.61
88.01
2.22
92.10
26.43
9.50 0.50::0..0
1.60 1.28
0.66 0.29
CLIP
129.30 +: 105.04
436.60 52.67
0.33
7.31
2.06
78.60
25.15
8.40 1.36
3.80 0.775
0.54 0.33
RP
161.40 +: 102.91
397.30 = 98.27
2.55
7,80
1.65
80.60
21.90
1.40
4.40
0.56 0.22
IRNI
147.70 1: 93.12
437.30 87.21
2.67
-688 2.14
78.30 27.22
8.10 1.51
3.80 3.80 0.98
0.68 0.29
Table 8: The mean and standard deviation for each found hyperparameter for each method on the TRIX
dataset without EoR
Parameter batch size
epochs
learning rate
weight decay
features
layers
dimensions
step size
None
256.00 0.00
32.00 + 0.00
-4.15 + 1.90
-4.15 = 4.71
16.00 + 0.00
2.00 + 0.00
3.80 + 1.83
0.50 + 0.49
RNI
126.40 +
67.20 67.20
431.20 + 43.66
-2.62 0.30
-7.63 + 2.11
94.80
24.86
9.40 + 0.80
2.00 + 1.34
0.46 +
0.19 0.19
CLIP
1 83.98
378.60
-2655 0.45
-7.15 1.79
67.90
16.12
8.10 = 1.45
4.00 4 0.89
0.61 0.226
RP
16.220
445.90 54.74
-2.63
-6.80 1.63
80.40 ::00=000 32.04
8.50 = 1.12
4.40
+ 1.02
0.69 - 0.28
IRNI
185.10 83.23
451.80 75.61
-2.59 0.31
-9.16 = 1.23
76.40 = 29.88
8.90 = 1.30
4.10 + 0.94
0.63 + 0.21
Table 9: The mean and standard deviation for each found hyperparameter for each method on the EXP dataset without EoR
Parameter
batch
epochs
learning
weight deray
features
layers
dimensions
step
Nome
205.90 + 67.09
172.10 +: 166.92
-4:29 1.82
4..0
3.54
52.10 = 40.55
4.30 +: 2.33
2.60
1.80
0.56 0.39
RNI
164.40 1 84.80
425.10 + 79.47
2.95 0.50
7.35 1 1.75
63.00 = 37.26
8.80 1: 1.40
2.30 +: 1.68
0.64 1 0.28
CLIP
223.20 + 51.71
307.30 : 120.73
2,78
2.50
63.50 = 41.48
7.60
1.80 -: 1.17
0.42 :: 0.23 0.23
RP
139.10 + 86.74
378.10
= 115.58
-3.59
2.211
81.90
41.42
8.50
300+ 1.25
4.70 0.46
0.52 :: 0.24
IRNI
174.50 + 78.69
210.80 = 159.69
-3.20 0.38
-7.32 2.63
33,20 = 12.40
8.20 + 1.54
1.80 +: 1.08
0.61 + 0.25
Table 10: The mean and standard deviation for each found hyperparameter for each method on the CEXP dataset without EoR
Parameter
batch size
epochs
learning rate
weight decay
features
layers
dimensions
step size
Noue
149.70 + 86.61
143.60
98.14
-.54
-5.26 1266220 2.77
49.20 30.00
6.80 +00+:0 2.23
2.70
0.33 0.25
RNI
153.40 + 86.97
430.10
102.38
-..3
-6.46 +:0
63.40 36.21
9.10 1.45
1.99
0.87 007200 0.14
CLIP
190.50 + 49.88
308.00 = 90.24
-7.61 -.77
54.30 30.84
8.30 1.55
2.10 1.37
0.66
RP
130.30
+ 85.78
353.30
99.67
-5.25 -3.65
27.93 75.90
8.80 1.08
4.60
0.53 0.27
IRNT
169.90 87.46
245.80 157.52
-3.13+0.59
-6.69 1.85
49.00 34.81
8.00 2.05
2.80 1.54
0.51 0.30
21

---

Published in Transactions on Machine Learning Research (08/2023)
Table 11:
The mean and standard deviation for each found hyperparameter for each method on the CSL
dataset without EoR
Parameter
batch size
epochs
learning
weight deray
feutures
layers
dimensions
step size
Noue
00. +: 0.00
32,00 + 0.00
4.15
-4.15 4.71
16.00 = 0.00
2.00 1:00::.00 0.00
3.80 1.83
0.50 0.49
74.90 + 86.57
481.70 = 58.11
0.455
-5.27
90.00 = 35.89
8.30 1.35
1.70 1.42
0.62 0.26
CLIP
179.10 73.78
312.10 = 91.59
0.35
-6.33
66.40 = 36.31
7.00 1.67
3.50
1.12
0.58 0.18
RP
185.00 + 70.37
319.30 = 88.94
0.45
-6.31
2.48
53.00 = 29.85
1.50
4,20
0.42 0.24
IRNI
191.9 + 58.75
240.00 = 114.25
-..56
-6.67 + 2.83
37.70 = 14.21
4.70 1.62
4.00 + 0.89
0.41 0.23
Table 12: The mean and standard deviation for each found hyperparameter for each method on the PRO- TEINS dataset with EoR
Parameser
opochs
learning
wright doray
fenturs
layers
dimensions
strp size
Foit
RNI
180.80 72.66
265.90
117.07
-3.98 + 1.03
-6.38
62.10
33.05
2.87
1.60 0.19
0.67 0.30
36.10
CLIP
92.10 69.64
194.30
153.41
-3.42 + 1.00
-3.85 2.41
63.70
+-3881
5.90 + 2.77
3.60 + 1.20
0.45 0.30
21.00 + 17.40
RP
157.00 = 78.16
281. + 153.80
-2.50 0.28
-4.09 3.19
06.00 39.44
2,50
1.17
2,90 = 1.04
0.41 0.25
41.60 + 17.45
163.70
296.30 169.70
2.83 1:
57.50 46.20
3.50
1.76
0.43 0.41
18.50
13.34
Table 13: The mean and standard deviation for cach found hyperparameter for cach method on the MUTAG
dataset with EoR
Parameter
batch size
epocha
learning rate
weight decay
Sentures
Layers
dimeusions
step size
EoRt
RNI
110.70 + 80.39
221.50
132.31
-3.57 + 0.89
-6.53 + 2.79
78.20 + 35.47
6.40 2.00
2.00 + 1.45
0.50 0.24
34.40 + 15.88
CLIP
111.70 1 88.57
263.30
114.02
-3.65 1: 0.61
-4.71 1: 3.12
80.30 1: 34.81
6,90 2:221
2.80 2 1.25
0.42 0.36
14.30
14.12
153.10
255.70
173.48
-296 0..89
-5.11
81.20 46.18
7.30 2.49
2.70
0.68
35.80
16.77
IRNT
158.40 84.20
310.00
129.19
-3.65 + 1.01
-4.81 + 2.33
76.00 + 43.38
5.60 3.14
2.10 + 1.37
0.61
0.18
30.30 + 21.87
Table 14: The mean and standard deviation for each found hyperparameter for each method on the NCI1 datasot with EoR
Paraneter
butch size
epochs
learning rate
weight decay
festtures
layens
dimecsioons
step size
Eolt
86.19
120.89
-5.09
96.10
8,20
3.20 1.17
17.35
CLIP
162.50 = 76.87
383 033.90+ + 109.63
-101 = 0.77
-7.20 2.36
86.70
35.18
7,90 = 1.87
2.40 1:20
0.41 0.31
35.30 = 14.49
RP
138.10 85.82
246.50 + 59.54
-4.54 + 0.41
-5.02 25
102 60 + 28 50
7.00
1.90
3.60 0.80
0.55 + 0.30
43.00 + 10.61
356.70
3..88
-7.05
102.60
7.50
0.33
7.50 12.67
Table 15:
The mean and standard deviation for each found hyperparameter for each method on the TRI
dataset with EoR
Parameter
batch size
epochs
learning rate
weight decay
festuree
layers
dimensions
step size
EoR
RNI
200.40 1 56.35
236.70
85.80
-2.54 1 0.52
-5.66 1 2.51
51.90 1 29.79
5.90 1.87
3.30 1 1.19
0.58 0.22
37.90 1.00011100 17.17
CLIP
205.10
13.87
219.50 :: 118.76
-2.79
-3.77 = 2.64
38.90
25.93
1.50
1.50=1.0 1.63
1.00 = 1.18
0.58 0.28
25.90 16.35
RP
214.00
47.44
214.90
137.52
-2.43
-7.08 2.65
31.30
22.45
5.30
= 2.28
4.40 0.06
0.44
0.27
25.30 15.07
IRNI
198.30 = 69.51
170.00
139.91
0.73
2.17
30.70
12:15
3,90 1.45
3.60 1.62
0.31
0.29
31.10 15.81
Table 16: The mean and standard deviation for each found hyperparameter for each method on the TRIX dataset with EoR
Parameter batch size
epocias
learning rate
weight decay
fentures
Layers
dimeusions
step size
EoRt
RNI
203.30 60.54
264.40
93.60
-2.50 + 0.44
-6.91
45.20 + 22.30
5.70
2.33
3.20
0.54 0.24
31.60 14.83
CLIP
187.10 73.91
977.70
-2.94 + 0.54
-6.43 3.27
49.60 +: 29.86
4.30
1.35
3.50 = 1.33
0.62 0.32
36.50 16.41
RP
190.20 1 78.03
182.80
124.46
-3.16
1. 0.68
-5.02
1 2.93
10.10.1
1. 27.94
3.50
1 1.54
4.00
1 1.18
0.64
0.18
32,20
1 18.42
IRNI
199.20 1 57.18
187.90
111.60
-2.60 + 0.62
-5.01 : 2.37
52.30 1 21.19
5.50
2:25
4.20
= 1.17
0.55 0.27
26.10 16.02
Table 17: The mean and standard deviation for each found hyperparameter for cach method the EXP dataset with EoR
Parameter
batch size
epochs
learning
weight decay
festures
layers
dimensions
step size
EoR
BNI
221.50 53.90
359.50
91.93
-3.35 1 0.58
-6.41 : 3.08
63.60 1: 35.13
7.70 1.35
2,50 2: 1.28
0.68 0.35
29.30 20.25
CLIP
196.80 2 53.20
225.50
93.81
-291
-6.13 2.73
51.70 20.40
1.00 1.00
3.20 = 1.54
0.19 119=000 0.26
25.60
9.79
198.60
72.36
249.90
107.72
-3.30 0.72
-6.20
53.20
+ 29.50
6.50
3.40
0.60
0.30
10 16.50
IRNI
165.80 + 70.00
236.20
120.13
-3.28
+..7
44.70 19.11
7.20 + 2.09
2.60 L.11
0.48
0.28
20.60 + 19.02
22

---

Published in Transactions on Machine Learning Research (08/2023)
Table 18: The mean and standard deviation for each found hyperparameter for each method on the CEXP
dataset with EoR
Parameser
size
epocha
learning rate
weight doray
fenturs
layers
dimensions
strp size
Folt
RNI CLIP
172.10 66.95
401.80
66.97
-3.78 +
-6.
77.00 + 36.91
8.30 3.30=1. L.55
1.30 = 0.16
0.74 0:21
22. 20.50-1
19.99
193.70 + 64.15
304.90
121.05
-3.05 + 0.72
-5.41 + 2.55
44.90 + 24.97
7.90
0.94
2.40 + 1.02
0.70 0.32
23.80 + 19.20
193.70 79.71
235.20
96.69
-3.37 1 0.46
-6.56 1: 2.48
68.70 1 40.74
7,60
1.56
3.20 4: 1.33
0.73
0.26
25.30 1: 13.50
190.40 63.72
224.10
155.54
-3.02 0.67
46.60 21.89
8.10
1.58
0.53
0.32
16.20 14.04
Table 19:
The mean and standard deviation for each found hyperparameter for each method on the CSL
dataset with EoR
Parameter
batch size
epochs
learning rate
wright docay
features
layers
dimensions
step site
FoR
RNI
161.50 + 105.35
161.00
102.96
-3.18 0,58
-7.16 = 2.07
89.70 41.53
9.10 + 1.01
1.70 1.42
0.58 # 0.23
50.50 + 10.13
CLIP
190.70 + 73.12
366.50
124.00
-255 +
0.44 0.45
-7.67 + 1.34
50. 1: 29.38
6.70 + 1.00
3.70 + 1.49
0:37 0.25
16:20 + 14.53
187.40
75.90
319.70
02.42
2.11
70.80
23.32
3.20
0.54
11.50
11.60
TRNT
193.40 54.00
217.40
74.28
-2633 0.45
6622 + 3.23
37.40 + 14.84
6.20 + 1.94
3.00 + 1.04
0.43 0.33
17.10 11.57
F
Trainability
Here we add an evaluation of the data from training all the models. More specifically, consider the trainability of all the methods on the evaluated dalasets. One aspect of trainability is: How easily can the model's hyperparameters be optimized? This question can be answered with BHO by evaluating how many hyperparameter optimization steps are necessary to reach a satisfactory performance. Alternatively, when comparing two models, the question can be answered by which model needs fewer steps to achieve greater performance. Considering our main experiment, we visualize the best-found performance at each BHO evaluation for each dataset and model. For each dataset and model, we have all BHO evaluations. From this, we compute each seed's best-found performance after each BHO step. We then average these seeds and visualize the BHO steps against the AUROC performance found (up to this point) in figures 4 and We follow the nomenclature of table in describing the datasets and the models. Note that the visualized performances are biased as we consider the maximum performance over multiple evaluations. Also, the best-found performances are not equal to the performance in table D as these figures use the validation set performances of the Monte Carlo cross-validation.
A clear difference notable between the synthetic datasets TRI, TRIX, EXP, CEXP, and CSL and the practical datasets PROTEINS, MUTAG, and NCI1. Each model converges independently datasets to its optimal performance, making comparisons between the models more difficult. On the synthetic datasets, this comparison is more straightforward, as the models mostly converge to the same optimum. Notably, RNI converges slower than all other models. Additionally, considering the other models, a rough order of trainability could be surmised to be: (1) IRNI, (2) CLIP, (3) ORNI, (4) RNI, however, this order is less significant than RNIs poor trainability. This order would coincide with the amount of randomness in each model. If we consider for each model the size of the IR tree on any given graph, then the order of size would be the same. IRNI requires the smallest amount of individualizations to reach completely distinguished graphs. ORNI and RNI have maximal trees since they ignore any color information present during the IR tree construction. CLIP's first step is the same as IRNI, and then it can be roughly compared to ORNT and RNI, so its tree size is in between the others. Lastly, RNI can be considered more random than ORNI since it uses continuous random variables, which results in a random space of infinite size. The possible graphs for IRNI, CLIP, and ORNI are always finite. From this, we conclude making use of less randomness improves trainability.
the practical
23

---

Published in Transactions on Machine Learning Research (08/2023)
PROTEINS
MUTAG
AUROC
AURDC
0.8
0.65
0.7
0.60
None
None
RM
RNI
0.6
[NN1
IAM
10
20
30
40
50
0
10
20
30
40
50
number of BHO
number BHQ
NCI1
TRI
0.85
1.0
0.9
None
AUROC
AUROC
0.8
CLIP
DRNI
0.7
CLIP
0.6
ORNI
0.5
20
30
40
30
40
number of BHO runs
number of BHO runs
TRIX
EXP
1.0
1.0
0.9
None
0.8
Mone
AUROC
0.8
RM
AUROC
RMI
CUP
0.7
0.7
RNN
HRNI
0.6
0.5
0.5
30
1.0
1.0
0.9
AUROC
AUROC
RNI
CLI
0.7
None
[RNI
RM
0.5
0.6
ORN
INNI
0.5
10
20
30
40
50
0
10
20
30
40
50
number of BHO
number BHO
Figure 4: These plots show the mean of the best performance (y) after BHO steps (x) over all seeds well as the standard deviation of the BHO training from table [ for the models without EoR.
24

---

Published in Transactions on Machine Learning Research (08/2023)
PROTEINS
MUTAG
0.75
0.90
0.85
AUROC
AiROO
0.80
0.65
0.75
None
0.70
None
RM
RNI
0.55
[NNI
IAM
10
20
30
40
50
0
10
20
30
40
50
number of BHO
number BHQ
NCI1
TRi
1.0
0.85
0.9
0.80
None
AUROC
0.75
AUROC
0.8
CLIP
0.7
DRNI
CUP
(RNI
0.5
20
30
40
30
40
number of BHO runs
number of BHO runs
TRIX
EXP
1.1
1.0
0.9
None
Mone
AUROC
0.8
RM
AUROC
0.8
RMI
CUP
CLIP
0.7
RRNI
0.6
HRNI
0.6
0.5
0.4
30
BHO runs
1.0
1.0
0.9
0.9
AUROC
AUROC
0.8
RNI
0.8
CLIP
0.7
ORNI
0.7
None
RM
0.6
0.6
ORN
INNI
0.5
10
20
30
40
50
0
10
20
30
40
50
number of BHO
number BHO
Figure 5: These plots show the mean of the best performance (y) after BHO steps (x) over all seeds well as the standard deviation of the BHO training from table [ for the models with EoR.
25


Reviews:
[{"review_id": "rHhPlEgixn", "reviewer": "Reviewer_Urhj", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n* The paper addresses an open problem in an interesting topic of the use of random node features in GNNs.\n\n* The paper (after the revisions) is easy to follow, also as a non-familiar with IR algorithm reviewer.\n\nWeaknesses:\n\n* Although this is not a proper weakness (but rather an observation), it is interesting that still, there is not a  clearly better method as far as random node features are concerned. I have read the discussion of the authors after the experimental section, but perhaps it would be possible to elaborate on why and when one would choose one method over the other? I think that this is an important point, in order to obtain a systematic way to work with random node features.\n\n* In the context of random node features, the paper can benefit from discussing [1].\n\nQuestions to the authors: \n\n* By taking random walk IR, is the 'level of randomness' decreased? at least with respect to the considered graph adjacency matrix?\n\n* Can the authors please explain the proposed method is related to positional encoding methods that use propagation of node features [2],[3]? Specifically, with respect to the random walk IR algorithm?\n\n* Why are the results in table 1 different between 'SOTA_{URF}' and the best of the methods {RNI,CLIP,RP, IRNI(CP)}? Are those simply results obtained in a different paper under the same settings or is there another difference?\n\n[1] Global attention improves graph networks generalization\n[2] From Local to Global: Spectral-Inspired Graph Neural Networks\n[3] Graph Positional Encoding via Random Feature Propagation", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper proposed IRNI - an individualization mechanism that builds on the combination of random node features and individualization refinement algorithms. Additionally, the authors propose a training framework based on Bayesian parameter optimization for hyperparameter tuning.\nThe authors present a rigorous theoretical study and analysis of the proposed method, followed by a comparison of different URF methods with IRNI on several real-world and synthetic datasets.\n\n", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please see my questions in my main review.", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "xttmMUSdRA", "reviewer": "Reviewer_q6bL", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- The work, to the best of my knowledge, is novel\n-  The method is well grounded in theory, makes sense intuitively, and works on several benchmarks\n\nWeaknesses:\n- The writing should be improved. The main issue with the writing is that the author uses non-trivial terms he doesn't explain, or explain after he talks about them thus making it confusing for the reader. \nExamples: (1) Universal random features (URF) never properly defined (I assume random features that make the inference a universal approximator)\n(2) IR and RNI acronyms not defined\n(3) Use discrete in a non-standard meaning which is confusing\n(4) \"Individualization refinement (IR) trees are the backtracking trees of practical graph isomorphism algorithms.\" isn't clear and should be explained better\n- The proofs are more proof sketches. Should have more detailed proofs in the supplementary (what about proof for lemma 3?)\n- ״Our crucial new insight is that ensembling over randomness significantly improves the performance of all URF, even in cases in which it had not been considered previously.״, I don't the experiments support this strong claim", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper describes a novel GNN that uses random features and extends previous works. They show it is a universal approximator and evaluate it on several benchmarks", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- Writing should be improved, and terms should be clearly explained\n- More detailed proofs", "broader_impact_concerns": "NA", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "17CiJNTwkb", "reviewer": "Reviewer_kbus", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n\nThis paper provides a framework that enables us to treat existing URFs in a unified manner. It offers the following advantages:\n- It provides a systematic method of making new URFs.\n- It provides a unified approach for proving universality approximation theorems for randomized feature initialization.\n- It provides the parameterization of URFs (by choice of refinement and selection algorithms), enabling us to evaluate these parameters' impact on empirical prediction performances.\n\n**Weaknesses**\n\n- There is room for improvement in writing. Specifically, I would suggest the following improvements (see Requested Changes for details):\n  - Write the basics of IR (in a self-contained manner, if possible.)\n  - Provide definitions for undefined mathematical terms and notations.\n  - Elaborate theorems' proofs\n- IRNI(CR), a new URF derived from the IRNI framework, does not outperform other URFs in numerical experiments, although its universality is shown.\n\n**Claim and Evidence**\n\nAs far as I have checked, I found no apparent incorrect point in the proof. However, since I am unfamiliar with the Individualization-Refinement algorithm, I am not confident that I check correctly.\nThe paper claims to propose a new Bayesian Hyperparameter Optimization method. Indeed, as far as I know, the optimization is new in that it adds a penalty computed by the hyperparameter values. However, the experiment uses the usual nested cross-validation if I get all the information. Therefore, I have a question about whether this optimization scheme is novel.\n\n**Audience**\n\nThe expressive power of GNNs is one of the main topics in GNN research. Universality is the most common way to evaluate models' expressive power. Several data initialization methods have been proposed to make GNNs universal (i.e., URFs). However, the relationship between them needs to be clarified. This paper provides a unified method to handle URFs, deepening our understanding. Therefore, this paper is of interest to TMLR audiences.\n\n**Clarity**\n\nAs mentioned in the Weaknesses section, I think writing has room for improvement.\nFirst, although this paper introduces some components of IR in Sections 4.1 and 4.2, if I get all the information, there is no explanation about how IR works and its basics. Readers without knowledge of IR may have difficulty grasping the paper's contents. I suggest adding the basic knowledge about IR (e.g., in Appendix) in a self-contained manner or providing pointers to necessary references.\nSecond, some mathematical terms and notations are used without definitions (see Requested Changes for details).\nFinally, it would be more understandable if the proof of the theorems on IRNI universality (Theorem 4--6) were more detailed than the current one.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper introduces Individualization Refinement Node Initialization (IRNI), a unified framework for randomized node initialization algorithms for GNNs. It is based on the Individualization-Refinement algorithm.\nExisting universal random features (URF), including Relational Pooling (RP), Random Node Initialization (RNI), and Colored Local Iterative Procedure (CLIP), fall into this framework. By using this framework, this paper proposed a new URF systematically.\nOn the theoretical side, this paper proves universal approximation theorems in the following scenarios:\n- Universality of the IRNI whose refinement is coarser than the color refinement.\n- Universality for invariant functions on 3-connected planner graphs.\n- Universality of a depth-fixed IRNI with the color refinement for the invariant functions on fixed-sized graphs (excluding an exponentially small number of graphs).\n\nEmpirically, this paper evaluates several URFs within the IRNI framework, whose hyperparameters are optimized by Bayesian Hyperparameter Optimization on five artificial datasets and two real datasets. ", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "P.1\n- Section 1, Paragraph 2: enhance -> enhances\n\nP.2\n- Section 1, Paragraph 7 (Paragraph titled *Why individualization refinement*): This paragraph explains why IR is used. However, since there is no explanation of what IR, readers may think this paragraph is abrupt. Therefore, I suggest the description of IR before this paragraph.\n\nP.5\n- Section 3.1, Paragraph 4: The reference McKay & Piperno has a form different from the other references.\n- Section 3.2, Paragraph 1: [...] colors $i$, $j$ the number of [...] -> [...] $i$, $j$, [...] (add a comma)\n\nP.6\n- Section 3.4, Paragraph 2:\n  - $\\boldsymbol{x}_v \\leftarrow \\boldsymbol{x}_v \\circ (r_1, \\ldots, r_d)$. I think $\\circ$ usually denotes function composition. Since this usage of $\\circ$ is unusual, I suggest explaining its definition.\n  - [...] by assigning it a one-hot encoding of natural numbers. -> [...] by assigning a one-hot encoding of natural numbers to it. \n  - $x_v$ -> $\\boldsymbol{x_v}$\n- Section 4.1, Paragraph 3:\n  - Write the definition of $V^{\\ast}$.\n  - Write explicitly that $\\nu \\in V^{\\ast}$.\n  - I think $\\mathrm{Ref}(G, \\pi, \\nu)^{-1} (v) = \\{v\\}$ is a little difficult to interpret. Since the value range of $\\mathrm{Ref}(G, \\pi, \\nu)$ is $\\{1, \\ldots, k\\}$, $v$ is incompatible as an argument of $\\mathrm{Ref}(G, \\pi, \\nu)^{-1}$.\n\nP.7\n- Section 4.1, Lemma 1:\n  - Since $\\mathrm{Aut}(G, \\pi)$ is only used in this lemma, the description would be more straightforward if we do not introduce the notation $\\mathrm{Aut}(G, \\pi)$ (Nevertheless, I think it is better to define the automorphism of a graph.)\n  - Superscript $\\varphi$ is undefined (e.g., $(G, \\pi)^{\\varphi}$)\n  - $(G, \\pi)^{\\varphi} = [...] = G$: there is a notational inconsistency regarding whether we should include the coloring $\\pi$ as a component of the graph $G$ or not.\n- Section 4.1, Lemma 2: The concept of isomorphism-invariant is undefined.\n\nP.8\n- Section 4.2, Paragraph 3: *IRNI depends on the random walk in the IR tree and is thus a URF [...].*: URF, by definition (P1, Section 1, Paragraph 2), makes MPNN a universal function approximator. However, since it is not shown that IRNI is a universal approximator before this sentence, it may not be appropriate to call IRNI a URF, at least at this point.\n- Section 4.3, Paragraph 1: *[...] The use of repeated random IR walks has recently been proven to be a near-optimal traversal strategy of IR trees*: I suggest explaining what you mean by near-optimal here. Also, I want some references supporting this claim.\n\nP.9, Section 4.3, Theorem 5\n- *Individualizing 3 vertices on a common face followed by color refinement suffices to make the coloring discrete.*: Is it correct to understand that the choice of face and vertices is arbitrary? In other words, is it sufficient to select *any* face in the planner graph and individualize *any* 3 vertices on the face suffices to make the color refinement discrete?\n\nP.9--10, Theorem 4--6\n- The concept of $(\\delta, \\varepsilon)$-approximation is not mathematically defined.\n\nP.10, Section 4.3, Theorem 6\n- $f$ is assumed to be invariant. Does it imply that the domain $\\mathcal{G}'\\_{n}$ is invariant under the action of the graph automorphism? Also, is it assumed that any graph in $\\mathcal{G}'\\_{n}$ originates has size $n$, that is, $\\mathcal{G}'\\_{n} \\subset \\mathcal{G}\\_{n}$?\n\nP.17, Appendix E\n- I suggest describing the implementation details of models used in the numerical experiments, specifically, the libraries used to implement the models, Bayesian hyperparameter optimization, and evaluation code.", "broader_impact_concerns": "No concerns about broader impacts.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "5H7QlbDg5o", "reviewer": "Reviewer_SXN8", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n\n1.\tThis paper is well-organized and well-written. The contributions are clearly illustrated in Introduction, and backgrounds on several crucial concepts are introduced.\n\n2.\tThe theoretical contributions look good to me. The authors reveal the relationship between IR algorithms and MPNNs using IRNI.\n\nWeaknesses\n\n1.\tThe authors mention no systematic comparison among these URF and the trainability, generalizability, and expressivity is unclear. What’s the trainability? How do you measure the trainability?\n2.\tIt would be better to only highlight theoretical contribution or comprehensive benchmark. The current version is insufficient to systematically compare all URF, particular in in terms of trainability and generalizability. The experiments are only conducted in GIN.\nv", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The existing terminology, methods, and benchmark for universal random features are highly diverse, which prevents the application of URF in practice. This paper proposes a new framework capturing all previous URF and provided comprehensive comparison for all URF. For the theoretical side, the authors formally prove the universality of all instantiations of the proposed framework IRNI under natural condition.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1.\tProvide more details on the trainability of URF.\n\n2.\tHighlight the main contribution appropriately. ", "broader_impact_concerns": "No", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper introduces a novel approach which unifies existing random feature initialization methods using the individual refinement algorithm and shows the universality of Message Passing neural Networks with IRNI for several settings. They also present a Bayesian approach for hyper-parameter tuning.

The paper was appreciated by all reviewer but they noted that its writing could be improved. The authors responded very well to the questions and revised the paper to the satisfaction of the reviewers who now all agree on accepting it.

While I do not think the paper needs a minor revision, I encourage the authors to add the clarifications to the last reviewer Urhj (and positioning/references) in the camera ready version of the paper.
Decision: Accept (poster)