The Surprising Power of Graph Neural Networks with Random Node Initialization
Authors: Ralph Abboud
Ismail Ilkan Ceylan
Martin Grohe
Thomas Lukasiewicz
Venue:  (2021)
Keywords: graph representation learning
graph neural networks
expressiveness
universality
random node initialization
Weisfeiler-Lehman heuristic
higher-order graph neural networks

Abstract: Graph neural networks (GNNs) are effective models for representation learning on graph-structured data. However, standard GNNs are limited in their expressive power, as they cannot distinguish graphs beyond the capability of the Weisfeiler-Leman (1-WL) graph isomorphism heuristic. This limitation motivated a large body of work, including higher-order GNNs, which are provably more powerful models. To  date, higher-order invariant and equivariant networks are the only models with known universality results, but these results are practically hindered by prohibitive computational complexity. Thus, despite their limitations, standard GNNs are commonly used, due to their strong practical performance. In practice, GNNs have shown a promising performance when enhanced with random node initialization (RNI), where the idea is to train and run the models with randomized initial node features. In this paper, we analyze the expressive power of GNNs with RNI, and pose the following question: are GNNs with RNI more expressive than GNNs? We prove that this is indeed the case, by showing that GNNs with RNI are universal, a first such result for GNNs not relying on computationally demanding higher-order properties. We then empirically analyze the effect of RNI on GNNs, based on carefully constructed datasets. Our empirical findings support the superior performance of GNNs with RNI over standard GNNs.  In fact, we demonstrate that the performance of GNNs with RNI is often comparable with or better than that of higher-order GNNs, while keeping the much lower memory requirements of standard GNNs. However, this improvement typically comes at the cost of slower model convergence. Somewhat surprisingly, we found that the convergence rate and the accuracy of the models can be improved by using only a partial random initialization regime.

Under review as a conference paper at ICLR 2021
THE SURPRISING POWER OF GRAPH NEURAL NET- WORKS WITH RANDOM NODE INITIALIZATION
Anonymous authors Paper under double-blind review
ABSTRACT
Graph neural networks (GNNs) are effective models for representation learning on graph-structured data. However, standard GNNs are limited in their expressive power, as they cannot distinguish graphs beyond the capability of the Weisfeiler- Leman (1-WL) graph isomorphism heuristic. This limitation motivated large body of work, including higher-order GNNs, which are provably more powerful models. To date, higher-order invariant and equívariant networks are the only models with known universality results, but these results are practically hindered by prohibitive computational complexity. Thus, despite their limitations, standard GNNs are commonly used, due to their strong practical performance. In practice, GNNs have shown promising performance when enhanced with random node initialization (RNI), where the idea is to train and run the models with randomized initial node features. In this paper, we analyze the expressive power of GNNs with RNI, and pose the following question: are GNNs with RNI more expressive than GNNs? We prove that this is indeed the case, by showing that GNNs with RNI are universal, first such result for GNNs not relying on computationally demanding higher-order properties. We then empirically analyze the effect of RNI on GNNs, based on carefully constructed datasets. Our empirical findings support the superior performance demonstrate that the performance of GNNs with RNI is often comparable with or better than that of higher-order GNNs, while keeping the much lower memory requirements of standard GNNs. However, this improvement typically comes at the cost of slower model convergence. Somewhat surprisingly, we found that the convergence rate and the accuracy of the models can be improved by using only a partial random initialization regime.
GNNs with RNI over standard GNNs. In fact, we
INTRODUCTION
Graph neural networks (GNNs) (Scarselli et al. 2009 Gori et al., 2005) are neural architectures de- signed for learning functions over graph-structie data, and naturally encode desirable properties such as permutation invariance (resp.. equivariance) relative to graph nodes, and node-level compu- tation based on message passing between these nodes. These properties provide GNNs with a strong inductive bias, enabling them to effectively learn and combine both local and global graph features (Battaglia et al. (0188) As a result, GNNs have been applied to a multitude of tasks, ranging from protein classification GGimmer et al., 2017) and synthesis (You et al. 2018), protein-protein interac- tion (Fout et al. 2017). and social network analysis (Hamilton et 2017). to recommender systems
Ying et al. 2018) and combinatorial optimization [Bengio et al. 2018 Selsam et al. 2019).
However, popular GNN architectures, primarily based on message passing (MPNNs), are limited in their expressive power. In particular, MPNNs are at most as powerful as the Weisfeiler- (1-WL) graph isomorphism heuristic (Morris et al., 2019 Xu et al., 2019). and thus cannot discern between several families of non-isomorphic graphs, e.g., sets of regular graphs (Cai et al.) 1992). To address this limitation, alternative GNN architectures with provably higher expressive power than MPNNs have been proposed. These models, which we refer to higher-order GNNs, inspired by the more powerful generalization of 1-WL to k-tuples of nodes, known as k-WL (Grohe, 2017). These models are the only GNNs with established universality result, but these models are computationally very demanding. As a result, MPNNs, despite their limited expressiveness, remain the standard GNN model for graph learning applications.

---

Under review as a conference paper at ICLR 2021
In parallel development, MPNNs have recently achieved significant empirical improvements using random node initialization (RNI), through which initial graph node embeddings are randomly set. Indeed, RNI has enabled MPNNs to distinguish instances that 1-WL cannot distinguish, and is proven to enable better approximation of a class of combinatorial problems (Sato et al. 2020).. However, the effect of RNI on the expressive power of GNNs has not yet been comprehensively studied, and its impact on the inductive capacity and learning ability of GNNs remains unclear.
In this paper, we thoroughly study the impact of RNI on MPNNs. First, we prove that MPNNS enhanced with RNI are universal, in the sense that they can approximate every function defined on graphs of any fixed order. This follows from a logical characterisation of the expressiveness of MPNNs (Barceló et al., 2020) combined with an argument on order-invariant definability. Our result strongly contrasts with existing I-WL. limitations for deterministic MPNNs, and provides a foundation for developing very expressive and memory-efficient MPNN models.
To empirically verify our theoretical findings, we carry out careful empirical study to quantify the practical impact of RNI. To this end, we design EXP, synthetic dataset requiring 2-WL expressive power for models to achieve above-random performance, and run MPNNs with RNI on it, to ob- serve how well and how easily this model can learn and generalize based on this dataset. Then, we propose CEXP, a modification of EXP with partially 1-WL distinguishable data, and evaluate the same questions in this more variable setting. Overall, the contributions of this paper are as follows:
We prove that MPNNs with RNI are universal, significant improvement over the 1-WL limit of standard MPNNs and, to our knowledge, a first universality result for memory GNNs.
We introduce two carefully designed datasets, EXP and CEXP, based on graph pairs only distin- guishable by 2-WL or higher, to rigorously evaluate the impact of RNI.
Using these datasets, we thoroughly analyze the effects of RNI on MPNN, and observe that (i) MPNNs with RNI can closely match the performance of higher-order GNNs, (ii) the improved performance of MPNNs with RNI comes at the cost of slower convergence (compared to higher- order GNNs), and (iii) using partial random initialization regime over node features typically improves convergence rate and the accuracy of the models.
We additionally perform the same experiments with analog, sparser datasets, with longer training, and observe similar behavior, but more volatility.
2 GRAPH NEURAL NETWORKS
Graph neural networks (GNNs) (Gori al. 2005 Scarselli al., 2009) are neural architectures dedicated to learning functions over graph-structun data. In a GNN, nodes in the input graph are assigned vector representations, which are updated iteratively through series of invariant or equivariant computational layers. We recall message passing neural networks (MPNNs) (Gilmer al., 2017), a popular family of GNN models, and its expressive power in relation to the Weisfeiler- Leman graph isomorphism heuristic. We discuss alternative GNN models in Section 3 for a broader coverage, we refer the reader to the literature (Hamilton) 2020).
In MPNNs, node representations aggregate messages from their neighboring nodes, and use this information to iteratively update their representations. Formally, given a node x; its vector represen- tation Un, time t, and its neighborhood N N(z), message passing update can be written
Ur f1, = combine Uz.t, aggregate (eggregate((Fg.lll E N(=))))
where combine and aggregate are functions, and aggregate is typically permutation-invariant, Once message passing complete, the final node representations are then used to compute target outputs. Prominent message passing GNN architectures include graph convolutional networks (GCNs) (Kipf
& Welling 2017) and gated graph neural networks (GGNNs) (Li et al. 2016).
It is well-known that standard MPNNs have the same power as the 1 1-dimensional Weisfeiler-Lemal algorithm (1-WL) (Xu al. 2019 Morris et al., 2019). This entails that two nodes in graph cannot be distinguished if 1-WL does not distinguish them, and neither can two graphs be distinguished if 1-WL cannot distinguish them.
2

---

Under review as a conference paper at ICLR 2021
Consider the graphs G and H shown in Figure 1 1-WL cannot distinguish any two nodes of the graph G. Thus, for example, the invariant function f (G) - R that maps all nodes in the 4-cycle of G to and all nodes in the triangle to 0 is not expressible (or approximable) by a GNN. Moreover, 1-WL cannot distinguish the graphs G, H. even though they are obviously non-isomorphic, so no classifier based on the node embeddings com- puted by an MPNN can distinguish the two graphs.
G
H
Figure G and H are indistinguishable by 1-WL and hence by (1-WL) GNNs.
A somewhat trivial limitation in the expressiveness of MPNNs is that information is only propagated along edges, and hence can never be shared between distinct connected components of a graph (Barceó et al. 2020 Xu et al.) 2019). An easy way to overcome this limitation is by adding global readouts, that is, permutation-inen invariinn functions that aggregate the current states of all node Throughout the paper, we therefore focus on MPNNs with global readouts (also called aggregate- combine GNNs with global readout, i.e., ACR-GNNs (Barceló et al. 2020
RELATED WORK & MOTIVATION
Developing more expressive GNNs is active research area due the prominence of GNNs for relational learning (Hamilton et al. 2017) and combinatorial optimization (Bengio et al. 2018). As mentioned earlier, standard GNN models are most as expressive 1-WL (Morris et al. 2019 Xu
et al., 2019), and thus cannot distinguish between non-isomorphic input instances. In this section, we describe theoretical results quantifying the expressive power of existing GNNs.
Higher-order GNNs, We recall the following families of higher-order GNN models:
Invariant (resp., equivariant) graph networks: Invariant (resp., equivariant) graph networks (Maron et al. (011b) represent graphs as a tensor where node adjacency is directly encoded, and implicitly pass information between nodes through invariant (resp., equivariant) computational blocks. Hence, these models are themselves invariant (resp., equivariant), a desirable property for computations on graphs. Following intermediate blocks, higher-order tensors are typically returned, and the order of these tensors correlates directly with the expressive power of the overall model. Indeed, invariant networks (Maron et al. 2019c), and later equivariant networks (Keriven) & Peyré 2019), are shown to be universal, but with tensor orders of ((VV)), where [V] denotes the number of graph nodes. Furthermore, invariant (resp., equivariant) networks with intermediate tensor order l are shown to be equivalent in power to (k- 1) (Maron et al. (019aa), which is strictly more expressive as increases (Cai et al. 1992). Therefore, such universal higher-order models require intractably-sized intermediate tensors in practice.
The k- WL hierarchy has been directly emulated in GNNs, such that these models learn embeddings for tuples of nodes, and perform messaging passing between them, as opposed to individual nodes. This approach has yielded models such as k- (Morris et al.) 2019). GNGN have (I- WL expressive power but need ((V]))) memory to run, leading to excessive memory requirements.
Higher-order MPNNs:
Provably powerful graph networks (PPGNs): PPGN is an invariant GNN Maron et al., (019a), based on "blocks" of multilayer perceptrons (MLPs) and matrix multiplication, which theoreti- cally has 2-WL expressive power, and only requires memory O(IV?2 (compared to O(V))) for 3-GNNs). However, PPGN theoretically requires exponentially many samples in the number of graph nodes to learn necessary functions for 2-WL expressiveness (Puny et al. 2020).
GNNs with random node initialization. MPNNs have been enhanced with random node initial- ization Sato et al. 2020), such that the model trains and runs with partially randomized initial
In the terminology of Maron et al. (2019c), such global readouts are tensors of order 1 that are invariant under the symmetric group of the vertex set of the input graph.
'In the literature, one can find different (though equally expressive) versions of the Weisfeiler Leman al- gorithm leading to inconsistent dimension counts. For example, the (k + 1)-WL and the (k + 1)-GNNs of Morris et al. allaal/.20)) (2019) are equivalent in expressiveness to the k- of et al. [1992) Grohe (2017). We follow the version of Cai et al. (1992). it has been adopted as the standard in the literature graph isomorphism testing.
3

---

Under review as a conference paper at ICLR 2021
node features. These models, denoted rGNNs, are shown to near-optimally approximate solutions to specific combinatorial optimization problems, and are able to distinguish between 1-WL indistin- guishable graph pairs. rGNNs also detect characteristic sub- graphs in an input graph with high probability. Nonetheless, it remains open as to how much expressive power is exactly gained through RNI, and, in general, whether GNN model that is universal, scalable, and structure-prs structure-preservinng can be developed. Our work strongly improves the theoretical result of (Sato et al. (220)) as it shows universality of MPNNs with RNI, and thus that arbitrary real-valued functions over graphs can be leamned by MPNNs with the help of RNI. On the empirical side, we highlight the power of RNI in a significantly more challenging setting than rGNN, using target function (SAT) beyond their theoretical scope. Indeed, for SAT, approximation is known to be hard, and fixed local structures are not useful for prediction.
Similar work to RNI has also been conducted in terms of randomly adding features from pre- determined set of colors (Dasoulas et al., 2020) to disambiguate between nodes. This model, known as CLIP, is similar in spirit to RNI, in that it introduces randomness to node representations, but explicitly makes graphs distinguishable by construction. By contrast, we study random features produced by RNI, which (i) are not designed priori to distinguish nodes, (ii) do not explicitly introduce a fixed underlying structure, and (iii) yield potentially infinitely many representations for single graph. In this more general setting, we nonetheless show that RNI adds expressive power to distinguish between nodes with high probability, leads to a universality result, and performs strongly in challenging problem settings.
4 RANDOM NODE INIIIALIZATION MAKES GNNS UNIVERSAL
We present the main result of the paper. showing that random node initialization significantly in- creases the expressiveness and makes MPNNS universal, in natural sense. Our work is first positive result for the universality of MPNNs. This result is not based on a new model, but rather on random initialization of node features, which is widely used in practice, and in this respect, it also serves as a theoretical justification for models that are successfully employed in practice.
It may appear somewhat surprising, and even intuute-, that randomly initializing node fea- tures, on its own, would deliver such a gain in expressiveness. In fact, on the surface, random initialization no longer preserves the invariance of MPNNs, since the result of the computation of an MPNN with RNI not only depends on the structure (i.e., the isomorphism type) of the input graph, but also on the random initialization. The broader picture is, however, rather subtle, as we can view such a model as computing a random variable (or as generating an output distribution), and this random variable would still be invariant. This means that the outcome of the computa- tion of an MPNN with RNI does still not depend on the specific representation of the input graph, which fundamentally maintains invariance. Indeed, random features vary around a mean which, in expectation, will inform GNN predictions, and is identical across all nodes as randomization is i.i.d. However, the variability between different samples, and the variability of a random sample relative to this mean, enable graph discrimination and improve expressiveness. Hence, in expectation, all samples over training and evaluation fluctuate around a unique value, preserving invariance, whereas single-sample variance achieves the improved expressiveness.
Formally, let Gn, be the class of all n-vertex graphs, i.e., graphs that consist of at most n ver- tices, and let f 9n R. We say that f is invariant if for isomorphic graphs G, H. e Gn, holds that f(G)= f(H). We say that a randomized function X' that associates with every graph G e Gn random variable (G) is an (e, d) aaprroximation of if for all G Gn it holds that Pr
s XG)) 1-8. Note that MPNNs with RNI compute functions X' of this type. If X is computed by an MPNN A with RNI, we say that N (E, apppprooxsssass f.
Theorem 4.1 (Universal approximation). Let 2 1, and let f Gn, R be invariant. Then, for all 8 > O, there is a MPNN with RNI that (c, (c,,))ap -approximaaes f.
For ease of presentation, we state the theorem only for real-valued functions, but it can be ex- tended to equivariant functions defined on the nodes of a graph (that is, functions f mapping graphs G to vectors x (G) with the property that for every permutation of V(G) it holds that f(GT)= = fG))" and even higher-order equivariant functions. The result can also be extended to weighted graphs, but then the function f that approximate needs to be continuous.
4

---

Under review as a conference paper at ICLR 2021
we first show that MPNNS with RNI can capture arbitrary Boolean functions, by building on the result of Barceló et al. (2020). which states that any logical sentence in C² can be captured by an MPNN with global readout, The logic C is the extension of first-order predicate logic using counting quantifiers of the form 3d for k 2 0, where (²)))( means that there are at least l elements x satisfying y,, and C² is the two-variable fragment of C (see appendix for further details). We establish that any graph with identifying node features, which we call individualized graphs, can be represented by sentence in C². Then, we extend this result to sets of individualized graphs, and thus to Boolean functions mapping these sets to True, by showing that these functions are represented by C² sentence, namely the disjunction of all constituent graph sentences. Follow- ing this, we provide construction with node emheddings based on random node initialization, and show that, with high probability, RNI makes the input graph individualized. Thus, with high proba- bility, RNI makes that MPNNs learn a Boolean function over individualized graphs. Since all such functions can be captured by a sentence in C², and an MPNN with global readout can capture any Boolean function by Barceló et al. (2020), we conclude that MPNNs with RNI can capture arbitrary Boolean functions. Finally, the result is extended to real-valued functions via natural mapping, yielding universality.
To prove Theorem 4.1
The concrete implications of Theorem 4.1 can be summarized as follows: First, MPNNs enhanced with RNI are able to distinguish individual graphs, already with an embedding dimensionality poly- nomial in the inverse of desired confidence 6, namely On225-1), where n is the number of graph nodes. Second, our universality results holds also with partial RNI. More specifically. it already holds with only one randomized dimension. Third, although Theorem 4.1 can potentially result in very large constructions, we note that it is very adaptive and tightly linked to the descriptive com- plexity of the function that we want to approximate. That is, for a more restricted class of functions, there may be more efficient constructions, and our proof does not rely on a particular construction. This deserves more thorough investigation, which we leave for future work. Finally, our construc- tion provides logical characterization of the power of MPNNs with RNI, and substantiates the means through which randomization yields expressiveness improvements. This construction there- fore also serves as basis for a more logically grounded theoretical study of randomized MPNN models, based on particular architectural or parametric choices.
Similarly to other universality results, Theorem 4.1 can potentially result in very large constructions. This is simple consequence of the general nature of such universality results: Theorem 4.1 applies to families of functions, describing problems of arbitrary computational complexity, including prob- lems that are computationally hard (even to approximate). Thus, a practically more relevant aspect is to empirically verify the formal statement, and test the capacity of MPNNs with RNI, in comparison to higher-order GNNs. Higher-order GNNs typically suffer from prohibitive space requirements, which is not the case for MPNNs with RNI, and this already makes them more viable in practice. As we discuss later in detail, our experiments demonstrate that MPNNs with RNI indeed combine expressiveness with efficiency in practice.
5 DATASETS FOR EVALUATING THE EXPRESSIVE POWER OF GNNS
GNN models are evaluated on prominent real-world datasets, such as IMDB, TU, and Proteins Kersting et al. 2016). These datasets are not tailored for evaluating the expressive power of GNNs,
as they do not contain instances or edge cases requiring expressiveness beyond 1-WL. In fact, higher- order models only marginally outperform MPNNs on these datasets (Maron et al., 2019a Dwivedi jet al. 2020), which further highlights their unsuitability for expressiveness evaluation.
We develop the datasets ExP and CEXP. EXP is designed to explicitly evaluate the expressiveness of GNN models, and consists of set of graph instances [G.... Hy... H,), such that each in- stance is graph encoding of propositional formula. The classification task is to determine whether the formula is satisfiable (SAT). Each pair (G,, H.)) respects the following properties: (i) G, and H; are non-isomorphic, (ii) G; and H, have different SAT outcomes, that is, G; encodes a satisfiable formula, while H, encodes an unsatisfiable formula, (iii) G2 and H; are 1-WL indistinguishable, so guaranteed to be classified in the same way by standard MPNNs, and (iv) G, and H; are 2-WL distinguishable, so can be classified differently by higher-order GNNs. Thanks to these propertics, can explicitly compare the performance of MPNNs with RNI to these higher-order models.
5

---

Under review as a conference paper at ICLR 2021
Ensuring these properties in ExP is highly non-trivial, and the construction of this dataset is cum- bersome. Fundamentally, every (G,, H.) is carefully constructed on top of a basic building block, the core pair, such that the 2 cores underlie G, and H,, respectively. In this core pair, both cores based on propositional clauses, such that one core is satisfiable and the other is not, and that these cores exclusively determine the satisfiability of G, (resp., H2) and have graph encodings enabling all aforementioned properties. Core pairs, and their resulting graph instances in EXP are planar and are also carefully constrained to ensure they are 2-WL distinguishable. Hence, core pairs are key substructures within EXP, and distinguishing these cores is essential for good performance.
Building on ExP, CEXP includes instances with varying expressiveness requirements. Specifically, CEXP is a standard ExP dataset where 50% of all satisfiable graph pairs are modified, such that they become 1-WI. distinguishable from their unsatisfialle counterparts, only differing from these by small number of added edges. Hence, CEXP consists of 50% "corrupted" data, which can be distinguished and learned by standard MPNN model (1-WL), which we label CORRUPT, and 50% unmodified data, generated analogously to EXP, and requiring expressive power beyond I- WL. which we refer to as EXP. Thus, CExP contains the same core structures as ExP, but these now lead to different SAT values in EXp and CORRUPT, and this makes the overall learning task more challenging than learning ExP or CORRUPT in isolation. Complete details of the overall data generation process for both datasets can be found in the appendix.
6 EXPERIMENTAL EVALUATION
In this section, we first evaluate the practical effect of RNI on MPNN expressiveness based on EXP, and compare MPNN-RNI against established higher-order GNNs. We then extend our empirical analysis to CEXP. Both experiments are conducted using the following models:
1-WL GCN (1-GCN): A GCN with 8 distinct message passing iterations, ELU non-linearities Clevert et 2016). 64-dimensional embeddings, and deterministic learnable initial node em-
beddings indicating node type. This model is guaranteed to achieve 50% accuracy on EXP.
GCN Random node initialization (GCN-RNI): An analogous model to 1-GCN with an identi- cal architecture, enhanced with RNI. We evaluate this model with four initialization distributions, namely the standard normal distribution N(O, 1) (N), the uniform distribution over [-1, (U),
Xavier normal (XN), and the Xavier uniform distribution (XU) (Glorot & Bengio 2010). We
denote the respective models GCN-RNI(D), where D e (N,U.XNXXU;
GCN Partial Random node initialization (GCN-z % RNI): A GCN-RNI model, where only percentage x of initial node embedding dimensions are randomized. That is, for d-dimensional node embeddings, GCN-r% RNI randomizes | _d dimensions, and sets the remaining dimen- sions deterministically from input features, namely, one-hot representation of the two possible node types (literal and disjunction) in the input graph representation (see appendix for more de- tails). We set x to the extreme values 0 and 100%, 50%, as well as near-edge cases of 87.5% and 12.5%, respectively.
Provably Powerful Graph Network (PPGN) (Maron et al., 2019a): A higher-order GNN with 2- expressive power, and which requires quadratic memory relative to the number of graph nodes. We set up PPGN with eight 400-dimensional computational blocks.
1-2-3-GCN-L: A higher-order GNN (Morris al.. 2019) emulating 2-WL on 3-tuples of nodes. 1 1-2-3-GCN-L operates at increasingly coarse node granularities, starting with single nodes and rising to 3-tuples. The model first computes all possible 3-tuples of nodes, then represents them as standard graph nodes. These nodes are connected to one another following the 2-WL neighbor- hood definition, i.e., tuples that exchange messages in 2- are connected by an edge in 3-GCN. 3-GCN-L implements a connected relaxation of 2-WL. in that only 3-tuples forming a connected graph are used, which comes the cost of some theoretical guarantees. Nonetheless, the compu- tation and representation of all tuples still imposes a severe overhead relative to MPNNs. We set up 1-2-3-GCN-L with 64-dimensional embeddings, 3 message passing iterations at level 1, 2 at level 2 and 8 at level 3.
3-GCN: A modification to 1-2-3-GCN-L, such that (i) only the 3rd level is used, and (ii) the full 2-WL procedure is implemented, i.e., all 3-tuples computed, as in standard 2-WL, rather than only the connected ones.

---

Under review as a conference paper at ICLR 2021
6.1 EXPERIMENT 1: How DOES RNI IMPROVE MPNN EXPRESSIVENESS?
In this experiment, we evaluate GCNs using different RNI settings on ExP, and compare with stan- dard GNNs and higher-order models. Specifically, we generate an EXP dataset consisting of 600 graph pairs, and discuss this generation more detail the appendix. Then, we evaluate all mod- els on ExP using 10-fold cross- validaaaii We train 3-GCN for 100 epochs per fold, and all other systems for 500 epochs. Mean test accuracy across all validation folds is measured and reported.
Full test accuracy results for all models are reported in Table D and model convergence for 3-GCN and all GCN-RNT models are shown in Figure 2 In line with Theorem 4.1 GCN-RNI achieves a near-perfect perfor- mance on EXP, substantially surpassing 50%. Indeed, all fully randomized GCN-RNI models achieve perfor- mance above 95% with all four RNI distributions. This finding supports observations made in related studies on RNI (Sato et al.) 2020). which suggest that RNI enables (sub)structure detection beyond the theoretical limits of 1-WL. Empiricall, we observed that GCN-RN is highly sensitive to changes in learning rate, activation function, and/or randomization distribution, and required delicate tuning to achieve its best performance.
Table 1: Accuracy results on EXP.
Test Accuracy (%)
Model
GCN-RNI(U)
97.3 + 2.55
GCN-RNI(N)
98.0 1.85
GCN-RNI(XU)
97.0 + 1.43
GCN-RNI(XN)
96.6 + 2.20
PPGN
50.0
1-2-3-GCN-L
50.0
3-GCN
99.7 + 0.004
Surprisingly, PPGN does not achieve performance above 50%, despite being theoretically 2-WL expressive. Essentially, PPGN learns an approximation of 2-WL. based on power-sum multi- symmetric polynomials (PMP), but fails to distinguish EXP graph pairs, despite extensive training. This suggests that PPGNs struggle to Iearn the required PMPs, and could not improve these results, both for training and testing, with hyperparameter tuning. Furthermore, as mentioned in Section 3 PPGN requires exponentially many data samples in the size of the input graph (Puny et al. 2020) for learning. Hence, PPGN is likely struggling to discern between EXP graph pairs due to the smaller sample size and variability of the dataset. 1-2-3-GCN-L also only achieves 50% accuracy, which can be attributed to theoretical model limitations. Indeed, the local and connected algorithm drops necessary information distinguish graph pairs, as it only considers 3-tuples of nodes that form a connected sub-graph. Thus, 1-2-3-GCN-L discards disconnected 3-tuples that crucially are where the difference between the ExP cores lies. This further highlights the difficulty of EXP instances, as even relaxation of costs the model the ability to achieve above-random performance. Note that 3-GCN achieves near-perfect performance, as explicitly has the suffi- cient theoretical power needed for the task, irrespective of learning constraints, and must only learn appropriate injective aggregation functions for neighbor aggregation (Xu et al. 2019).
In terms of model convergence, we observe that 3- GCN converges significantly faster than all GCN- RNI models, for all randomization percentages. In- deed, 3-GCN only requires about 10 epochs to achieve its optimal performance, whereas GCN-RNI models all require in excess of 100 epochs. The rp Intuitively, the slower convergence of GCN-RNI can be attributed to a significantly harder learning task compared to 3- GCN: Whereas 3-GCN must learn from a determinis- tic set of node embeddings, and is naturally capable of discerning between dataset cores, GCN-RNI relies on RNI to discern between data points in EXP, via an ar- tificial node ordering. This in turn implies that GCN- RNI must first leverage RNI detect structure, then subsequently learn robustness against the variability of RNI, which makes the learning task for GCN-RNI pecially challenging.
70
3-GCN
GUN-RNI
60
GCN-50%RNI
GCN- 87 SSRRT
GCN- 125-11258RR1
50
0
100
200
400
500
Epoch
Figure 2: Learning curves on EXP.
Our findings suggest that RNI can practically improve the expressiveness of MPNNs, and make them competitive with higher-order models, despite being significantly less demanding computationally. Indeed, for typical ExP instance with 50 nodes, GCN-RNI only requires 3200 parameters (using
7

---

Under review as a conference paper at ICLR 2021
90
90
80
80
70
70
60
60
50
50
200
400
500
100
2000
300
400
500
Epoch
Epoch
3-GCN
I-GCN
GCN-RNI
GCNCC
GCN-RNDCC GCN-50%IC
GCN-50%
GCN-81.5%
GCN-12.5%
.... GCNE .... RNME .... GCN 50%/E
(a) Learning curves for all GCN-RNI models and
(b) Learning curves for CEXP, split across EXP
3-GCN CExP.
(/E) and CORRUPT (/C).
Figure 3: Model convergence results for Experiment 2 on CExP on all models.
64-dimensional embeddings), whereas 3-GCN requires 1,254,400 parameters. Nonetheless, GCN- RNI performs comparably to 3-GCN, and, unlike the latter model, can easily scale to larger instances exceeding the range used in our datasets. This increase in expressive power, however, comes the cost of slower convergence. Even so, RNI proves to be a promising direction for building scalable yet powerful MPNNs.
6.2 EXPERIMENT 2: HOW DOES RNI AFFECT MPNN ON MORE VARIABLE DATASETS?
In Experiment 1, we observed that RNI practically improves the expressive power of GCNs over ExP. However, ExP solely designed for expressiveness evaluation, and this leaves multiple ques- tions open: How does RNI impact learning when data contains instances with varying expressive- ness requirements, and how does RNI affect model generalization on more variable datasets? We experiment with CEXP to explicitly address these questions.
Analogously to Experiment 1, we generate an EXP dataset with 600 pairs of graphs. Then, we create CEXP by selecting 300 graph pairs and modifying their satisfiable graph, yielding CORRUPT. CExP well-suited for evaluating the efficacy of RNI more holistically, as allows (i) the evaluation of the contribution of RNI on EXP conjointly with a second learning task on CORRUPT involving very similar core structures, and (ii) study of the effect of different degrees of randomization on overall and subset-specific model performance.
In this experiment, we train GCN-RNI (with varying randomization degrees) and 3-GCN on CEXP, and compare their test accuracy across all cross-validation splits. For GCN-RNI models, we observe the effect of RNI on specifically learning ExP and CORRUPT, and the interplay between these two tasks. In all experiments, we exclusively use normal distribution initialization, given its strong performance in Experiment 1.
The learning curves of all GCN-RNI and 3-GCN on CEXP are shown in Figure 3a and the same curves for the EXP and CORRUPT subsets are shown in Figure 3b As on ExP, we observe that 3- GCN converges very quickly, exceeding 90% test accuracy within 25 epochs on CExP. By contrast, GCN-RNI, for all randomization levels, converges much slower, around after 200 epochs, despite the small size of input graphs (~70 nodes at most). Furthermore, fully randomized GCN-RNI performs worse than partly randomized GCN-RNI models, particularly on CEXP, due to its weak performance on CORRUPT, as shown in Figure 3b
First, we observe that partial randomization can significantly improve model performance. This can clearly be seen on CEXP, in Figure Ba and Figure 3b) where GCN-12.5%RNI and GCN-87.5%RNI achieve the best performance, by far outperforming GCN-RNI, which struggles on CORRUPT. This can be attributed to having a better inductive bias than a fully randomized model. Indeed, GCN- 12.5% has mostly deterministic node embeddings, which simplifies learning CORRUPT.
8

---

Under review as a conference paper at ICLR 2021
This also applies to CCN-87.5%RNV where the number of deterministic dimensions, though small, remains sufficient for learning over CORRUPT. Both models also benefit from randomization to perform strongly on Exp, and have sufficient randomization to perform similarly to a fully random- ized GCN. GCN-12.5%RNN and GCN-87.5% RNII effectively achieve the best of both worlds on CEXP, leveraging inductive bias from deterministic node embeddings, while harnessing the power of random embeddings to perform strongly on EXP. This is best shown Figure 3b) where stan- dard GCN fails to learn EXP. fully randomized GCN-RNI struggles to learn CORRUPT, and the semi ranimrandomized GCN-50%RNI achieves perfect performance on both subsets. Overall, this is a surprising finding. as it suggests that MPNNs can perform significantly better with partial, and even small, amounts of randomization.
Second, we observe that the fully randomized GCN-RNI performs substantially worse than its partially randomized counterparts. Whereas fully randomized GCN-RNI only performs marginally worse on EXP (cf. Figure 2) than partially randomized models, this gap is very large on CExP, primarily due to CORRUPT. This observation concurs with the carlier idea of inductive bias: Fully randomized GCN-RNI loses all node type information, which is valuable for making robust and consistent decisions, and therefore struggles Indeed, the model fails to achieve even 60% accuracy on CORRUPT, where other models are near perfect, and also relatively struggles on EXP, only reaching 91 % accuracy and converging slower.
match 3-GCN and partially randomized models.
Third, all GCN-RNI models, at all randomization levels, converge significantly slower on both datasets than 3-GCN, similarly to Experiment 1. However, an interesting phenomenon can be seen on CEXP: All GCN-RNI models hover around 55% accuracy within the first 100 epochs over CExP (ef. Figure 3a suggesting a struggle jointly fitting both CORRUPT and EXP, before these models ultimately improve. This, however, is not observed with 3-GCN, Unlike on EXP, randomness is not necessarily beneficial on CEXP, as it can hurt performance on CORRUPT. Hence, RNI-enhanced models must additionally learn to isolate deterministic dimensions for CORRUPT, and randomized dimensions for ExP. These findings consolidate the earlier observations made on ExP on the impact of RNI on MPNN learning behavior, and highlight that the variability and slower learning for RNI also hinges on the variability and complexity of the input dataset.
Finally, we observe that both fully randomized GCN-RNI, and, surprisingly, 1-GCN, struggle to learn CORRUPT relative to partially randomized GCN-RNI. We can also observe that 1-GCN does not present "struggle" phase, and begins improving consistently from the start of training. These observations can be attributed to key conceptual, but very distinct hindrances impeding both models. In the case of I-GCN, the model is jointly trying to learn both EXP and CORRUPT, when it is proven that it cannot fit the former. This joint optimization severely hinders CORRUPT learning, as data pairs from both subsets are highly similar, and share identically generated UNSAT graphs (cf. Appendix). Hence, I-GCN, in attempting to fit SAT graphs from both subsets, knowing it cannot distinguish EXP pairs, struggles to learn the simpler difference in CORRUPT pairs. For GCN-RNI, the model discards key type information, so must only rely on structural differences to learn CORRUPT, which impedes its convergence. All in all, this further consolidates the promise of partial RNI means to combine the strengths of both deterministic and random features.
Further the earlier two experiments, we also conducted analogous experiments using sparser analogs of the datasets ExP and CEXP. In these cases, we observed similar behavior, albeit with slower convergence overall. More details on these experiments be found in the appendix.
7 SUMMARY AND OUTLOOK
We studied the expressive power of MPNNs with RNI, and showed that these are universal models. We empirically evaluated this model on carefully designed datasets, and observed that RNI prac- tically improves the learning abilities of MPNNs for challenging data, though it does slow down model convergence owing to the need to learn robustness against random variability. Our work delivers a strong theoretical result, supported by empirical evaluation and practical insights, to rig- orously quantify the effect of RNI on GNNs. Somewhat surprisingly, our experiments suggest that partial randomization may be the best strategy in most practical scenarios. An important direction for future work is to theoretically study the sensitivity of RNI to model architectures and initializa- tion distributions, to yield more complete understanding of the benefits and limitations of RNI.

---

Under review as a conference paper at ICLR 2021
REFERENCES
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 Proceedings of the Eighth International Conference Learning Representations, (ICLR), 2020.
Peter W. Battaglia, Jessica B. Hamrick, Victor Bapst, Alvaro Sanchez-Gonzalez, Vinícius Flores Zambaldi, Mateusz Malinowski, Andrea Tacchetti, David Raposo, Adam Santoro, Ryan Faulkner, Çaglar Gülçehre, H. Francis Song, Andrew J. Ballard, Justin Gilmer, George E. Dahl, Ashish Vaswani, Kelsey R. Allen, Charles Nash, Victoria Langston, Chris Dyer, Nicolas Heess, Daan Wierstra, Pushmeet Kohli, Matthew Botvinick, Oriol Vinyals, Yujia Li, and Razvan Pascanu. Relational inductive biases, deep learning, and graph networks. CoRR, abs/1 806.01261, 2018.
Yoshua Bengio, Andrea Lodi, and Antoine Prouvost. Machine learning for combinatorial optimiza- tion: methodological tour d' d'Horizon. CoRR, abs/1811.00 (0088111006121 1...110......1 2018.
Gunnar Brinkmann, Brendan D McKay, et al. Fast generation of planar graphs. MATCH Commun. Math. Comput. Chem, 58(2):323-3577 2007.
Jin-yi Cai, Martin Fürer, and Neil Immerman. An optimal lower bound on the number of variables for graph identifications. Comb., 12(4):389-410, 1992.
Djork-Amé Clevert, Thomas Unterthiner, and Sepp Hochreiter. Fast and accurate deep network learning by exponential linear units (clus). In Proceedings of the Fourth International Conference on Learming Representations (ICLR), 2016.
Stephen A. Cook. The complexity of desorem-proving procedures. In Proceedings of the Third Annual ACM symposium on Theory of Computing, pp. 151-158. ACM, 1971.
George Dasoulas, Ludovic Dos Santos, Kevin Scaman, and Aladin Virmaux. Coloring graph neu- ral networks for node disambiguation. In Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI 2020, pp. 2126-2132, 2020.
Vijay Prakash Dwivedi, Chaitanya K. Joshi, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Benchmarking graph neural networks. CoRR, abs/2003.0099 2020.
Alex Fout, Jonathon Byrd, Basir Shariat, and Asa Ben Hur. Protein interface prediction using graph convolutional networks. In Proccedings of the Thirtieth Annual Conference Advances in Neural Information Processing Systems (NIPS), pp. 6530-6539, 2017.
Justin Gilmer, Samuel S. Schoenholz, Patrick F. Riley, Oriol Vinyals, and George E. Dahl. Neu- ral message passing for quantum chemistry. In Proceedings of the Thirty-Fourth International Conference on Machine Learning (ICML), pp.
2017.
Xavier Glorot and Yoshua Bengio. Understanding the difficulty of training deep feedforward neural networks. In Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics (AISTATS), pp. 249-256, 2010.
Marco Gori, Gabriele Monfardini, and Franco Scarselli. new model for learning in graph domains. In Proceedings of the 2005 IEEE International Joint Conference on Neural Networks (LJCNN), volume 2, pp. 729-734, 2005.
Martin Grohe. Descriptive Complexity, Canonisation, and Desinable Graph Structure Theory, vol- ume of Lecture Notes Logic. Cambridge University Press, 2017.
William L. Hamilton. Graph Representation Learning. Morgan and Claypool Publishers, 2020.
William L. Hamilton, Rex Ying, and Jure Leskovec. Representation learning on graphs: Methods and applications. IEEE Data Eng. Bull., 40(3):52-74, 2017.
Haryy B Hunt III, Madhav Marathe, Venkatesh Radhakrishnan, and Richard E Stearns. The complexity of planar counting problems. SIAM Journal Computing, 27(4):1142-111 1998.
10

---

Under review as a conference paper at ICLR 2021
Nicolas Keriven and Gabriel Peyré. Universal invariant and equivariant graph neural networks. In Proceedings of the Thirty-ecoond Anmual Conference on Advances in Neural Information Pro- cessing Systems (NeurIPS), pp. 7090-7099, 2019.
Kristian Kersting, Nils M. Kriege, Christopher Morris, Petra Mutzel, and Marion Neumann. Bench- mark data sets for graph kernels, 2016. http:///grapkeeree..s. cs. tu do muund. de
Sandra Kiefer, Iia Ponomarenko, and Pascal Schweitzer. The Weisfeiler-Leman dimension of pla- nar graphs is at most 3. ACM, 66(6):44:1 -4:33111 2019.
Diederik Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In Proceedings of the Third International Conference on Learning Representations, ICLR, 2015.
Thomas Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In Proceedings of the Fifth International Conference on Learning Representations (ICLR), 2017.
Yujia Li, Daniel Tarlow, Mare Brockschmidt, and Richard Zemel. Gated graph sequence neural networks. Proceedings of the Fourth International Conference on Learning Representations (ICLR), 2016.
Haggai Maron, Heli Ben-Hamu, Hadar Serviansky, and Yaron Lipman. Provably powerful graph networks. In Proceedings of the Thioty-Second Annual Conference on Advances in Neural Infor- mation Processing Systems (NeurIPS), pp. 2153-2151221 2164, 2019a.
Haggai Maron, Heli Ben-Hamu, Nadav Shamir, and Yaron Lipman. Invariant and equivariant graph networks. In Proceedings of the Seventh International Conference on Learning Representations (ICLR), 2019b.
Haggai Maron, Ethan Fetaya, Nimrod Segol, and Yaron Lipman. On the universality of invariant networks. In Proceedings of the Thirty-Sixth International Conference Machine Learning, (ICML), pp. 4363-4371, 2019c.
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. In Proceedings of the Thirty-Third AAAI Conference on Artificial Intelligence (AAAI), pp. 4602- 4609, 2019.
Omri Puny, Heli Ben-Hamu, and Yaron Lipman. From graph low-rank global attention 2-FWI. approximation. CoRR, hass/2006007846, 2020.
Ryoma Sato, Makoto Yamada, and Hisashi Kashima. Random features strengthen graph neural networks. CoRR, abs/2002.03155,, 2020.
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEFE Transactions Neural Networks, 20(1):61-80, 2009.
Daniel Selsam, Matthew Lamm, Benedikt Bünz, Percy Liang, Leonardo Leonardo de Moura, and David Dill. Learning SAT solver from single-bit supervision. In Proceedings of the Seventh International Conference on Learning Representations (ICLR), 2019.
Keyulu Xu, Weihua Hu, Jure Leskovee, and Stefanie Jegelka. How powerful are graph neural networks? In Proceedings of the Seventh International Conference Learning Representations (ICLR), 2019.
Rex Ying, Ruining He. Kaifeng Chen, Pong Eksombatchai, William L. Hamilton, and Jure Leskovec. Graph convolutional neural networks for web-scale recommender systems. In Pro- ceedings of the Twenty-Fourd Fourth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), pp. 974 00e--98, 2018.
Jiaxuan You, Bowen Liu, Zhitao Ying, Vijay S. Pande, and Jure Leskovec. Graph convolutional policy network for goal-directed molecular graph generation. In Proceedings of the Thirty-First Anmual Conference on Advances in Neural Information Processing Systems, (NeurIPS), pp. 6412- 6422, 2018

---

Under review as a conference paper at ICLR 2021
A APPENDIX
A.1 PROPOSITIONAL LOGIC
We briefly present propositional logic, which underpins the dataset generation. Let S be a (finite) set of propositional variables. A literal is defined as v, or (resp., -U), where E S. A disjunction of literals is clause. The width of clause is defined as the number of literals it contains. A formula y is in conjunctive normal form (CNF) if it is a conjunction of clauses. A CNF has width k if it contains clauses of width most k. and is referred as a k-CNF. To illustrate, the formula 4 = (I1 V -23) A (34 V 21) is a CNF with clauses of width 2.
S {0, maps variables to False (0), or True (1), and satisfies yo which denote by /E = sp. in the usual sense, where += is propositional entailment. Given propositional formula sp, the satisfiability problem, commonly known SAT, consists of determining whether yp admits satisfying assignment, and is NP-complete (Cook 197I..
An assignment
A.2 PROOF OF THEOREM
We first prove a Boolean version of the theorem.
Lemma A.1. Let n 2 1, and let f 9n + {0,1} be an invariant Boolean function. Then, for all 6, 0 there is MPNN with RNI that (epp)xapprs f.
To prove this lemma, always assume to admit global readouts. Let C be the extension first-order predicate logic using counting quantifiers of the form 3²*x for & O, where x=xx))))) means that there are least elements x satisfying sp
logical characterization of the expressiveness of MPNNs, which
For example, consider the formula
((x) == = y( ((x, =3*==
(A.1)
This is a formula in the language of graphs; E(x, y) means that there is an edge between the nodes interpreting x and y. For a graph G and vertex v E V(G), we have G ((v) ("G satisfies o if the variable r is interpreted by the vertex v"") if and only if v has at most 2 neighbors in G that have degree at least 5.
We will not only consider formulas in the language of graphs, but also formulas in the language of colored graphs, where in addition to the binary edge relation we also have unary relations, that is, sets of nodes, which we may view colors of the nodes. For example, the formula
(xx) = 3dd y( [((x,)) A RED(U))
says that node has least 4 red neighbors (more preciscly, neighbors in the unary relation RED). Formally, we assume we have fixed infinite list R1, R2,... ... of color symbols that we may use in our formulas. Then colored graph is graph together with mapping that assigns finite set p(v) of colors R; to each vertex (so we allow one vertex to have more than one, but only finitely many, colors).
A sentence (of the logic C or any other logic) is a formula without free variable. Thus a sentence expresses a property of graph, which can also view Boolean function. For sentence yp denote this function by [[ If yp is a sentence the language of (colored) graphs, then for every (colored) graph G we have [G](G)) G &p and [G) otherwise.
It is easy to see that C is only a syntactic extension of first order logic FO-for every C-formula there a logically equivalent FO-formula. To see this, note that we can simulate 3²* by k ordinary existential quantifiers: 3²*0 is equivalent to .... /Asiicjs
Iz Azsisk sp(x;) ). How- ever, counting quantifiers add expressiveness if we restrict the number of variables. The C-formula 3at x (x x) (saying that there are at least i vertices) with just one variable is not equivalent to any FO-formula using less than & variables. By C formulas with most l variables.
we denote the fragment of consisting of all
12

---

Under review as a conference paper at ICLR 2021
For example, the formula ((x) in A.1 is in C², but not in C². But co(x) is equivalent to the following formula ('(x) (x) in C
<'(x) y (E(x,)) 1 xEy,,))))
(A.2)
The fragments Cº interesting for us, because their expressiveness corresponds to that of 1)- WL. and hence to that of k-GNNs. More precisely, for all k 2, two graphs G and H satisfy the same
C -seteences if and only if (k -LL does not distinguish them (Cai et al. 1992). By the results of (Morris et al. 2019 Xu et al. 201 2019) this implies, particular, that two graphs are indistinguishable by all MPNNS if and only if they satisfy the same C -seettencss. Barceló et al. (2020) strengthened this result and showed that every C² -sentence can be simulated by an MPNN.
Lemma A.2 (Barceló et al. 2020). For every C² -sentence ip and every > O there is an MPNN that e-approximates [:p].
Since here are talking about deterministic MPNNs, there is no randomness involved, and we just say "e-approximates" instead of (appro-appo
Lemma A.2 not only holds for sentences in the language of graphs, but also for sentences in the language of colored graphs. Let us briefly discuss the way MPNNs access such colors. We encode the colors using one-hot vectors that are part of the initial states of the nodes. For example, if we have a formula that uses color symbols among R1 Rg, then we reserve h places in the initial state H, (Iu1....,.Tp) ) of each vertex (say, for convenience, Zpl....,Zphl and we initialize x, by letting
1 if v is in R2 and zoi 0 otherwise.
Let us call a colored graph G individualized if for any two distinct vertices v, w E V(G) the sets p(v). p(w) of colors they have are distinct. Let us say that sentence x identifies a (colored) graph G if for all (colored) graphs we have += x and only if is isomorphic to G.
Lemma A.3. For every individualized colored graph G there is C² -sentence XG that identifies G.
Proof. Let be an individualized graph. For every vertex E ( let
(x)
R(x) Re(Ba.....oo)pppl
A
-R(x).
REp(o)
Then is the unique vertex of G such that G av(). For every pair v, w V(G) of vertices, let
Bow (I,z) v) = (x)( A ahe (v) F(I,,))
if (n. F(G).
an (x) (1) BE
if (1. w) E(G).
We let
XG ==
^
vEV(G)
is easy to see that XG identifies G.
For n. k N, we let Gn,k be the class of all individualized colored graphs that only use colors among Ri,..., Ry-
Lemma A.4. Let h Gn,k 1) be invariant Boolean function. Then there exists C²- sentence Uh such that for all Gn,k it holds that [vn](G) h(G).
Proof. Let H Go.kk be the subset consisting of all graphs H with h(H)= We let
V X#-
HeH
We climinate duplicates in the disjunction. Since up to isomorphism. the class Gn.k is finite, this makes the disjunction finite and hence 4h, well-defined.
The restriction of colored graph G is the underlying plain graph, that is, the graph G obtained from the colored graph G by forgetting all the colors. Conversely, colored graph G is an expan- sion of plain graph G if G (
13

---

Under review as a conference paper at ICLR 2021
Corollary A.1. Let In {0.1} be invariant Boolean function. Then there exists C²- sentence f4 (in the language of colored graphs) such that for all E In it holds that [W)](G)) f(G*).
Towards proving Lemma A.I we fix an 7 2 and a e, 6.00.. We let
2 and k:= c² n c=
The technical details of the proof of Lemma A. and Theorem 4. depend on the exact choice of the random initialization and the activation functions used in the neural networks, but the idea is always
the same. For simplicity, we assume that we initialize the states z. (I.1....., Fwe) of all vertices to (Tu, .,... 0), where for e ((G) are chosen independently uniformly at random from [0, 1J. As our activation function o, we choose the linearized sigmoid function defined by azx) = for for 0 S x 1, and o(x) for 1.
< 0, or (xx)
Lemma A.5. Let .i...... .n be chosen independently uniformly at random from the interval [0, 1]. For S i S n and
$ S c.n.. let
k
S6j k c-n2
Then with probability greater than 1 the following conditions are salisfied.
(i) For all i (I.....,n].I] (l,...,, c.n) it holds that (ssi)) < 10,
(ii) For all distinct i, (l,..., n.) there exists j E (l,...,c.nn)) such that (sss)) (8v;).
Proof. For every let p. [r, kj. Since k- ; is uniformly random from the interval [0, k.]. the integer is uniformly random from (0...., 1}. Observe that 0 < (ssy) < 1 only if p; (j
& 1)- o = 0 (here we use the fact that k is divisible by e.n²). The probability that this happens is g. Thus, by the Union Bound,
Pr (Bi.j: O< ((1s) (066)))<0))) < <1) c-n k
(A.3)
Now let i, / be distinct and suppose that (sij) (855) for all j. Then for all j we have sij 82j S and therefore [S15] S = [sr;] S O. This implies
k
k
Vj E e.....,.n.)) Pt S (j- 1)
Pr s(-
(A.4)
c. c-
c-n²²
Let jr (I....,. n²) such that ps {(i- 1)
o 1). Then by (A.4) we have
pl ((i- that this happens is most
- 1) o ""
k - 1]. As pr is independent of p. and hence of j", the probability on
{ on on This proves that for all distinct i, the probability that on Hence, again by the Union Bound,
(sig) ($2r) is at most
Pr (yj: (8is) = (8v5)) s
(A.5)
A.3 and A.5 imply that the probability that either (i) or (ii) is violated is at most
C- n 1 2
k s s 8.
c
Proof of Lemma A.7 For given function f 9n (0, 1), choose the sentence v/y according
to Corollary A.I Applying Lemma A.2 to this sentence and obtain an MPNN N₂ that colored graph G e Fn.k computes an e-approximation of f(G)).
Without loss of generality,
assume that the vertex set of the input graph to our MPNN is (I....,7). We choose & (the dimension of the state vectors) in such a way that & 2 c. and at least large as the dimension of the state vectors of Ny. Recall that the state vectors
14

---

Under review as a conference paper at ICLR 2021
initialized xi (0) (ri, 0, 0) for values r; chosen independently uniformly at random from the interval [0. 1].
In the first step, MPNN computes the purely local transformation (no messages need to be passed) that maps x to x
(x ,..., (1) with
for 1 sssccnn o kk (1-1) c
11) 5
0
for c. n
Since we treat k c, n as constants, the mapping rÚ + k.r. (j - + is just a linear mapping applicd to T; Ta
(1) mutually distinct (0, 1 --vectors, By Lemma A.5 with probability least 1 ō, the vectors a; which we view as encoding a coloring of the input graph with colors from R1,-.., R2- Let Gh be the resulting colored graph. Since the vectors z:(0) mutually distinct, G is individualized and thus in the class Gn.k. We now apply the MPNN NV, and it computes a value e-close to [&>) f((G))) f(G).
Proof of Theorem 4.1 Let f: In + R be invariant. Since In is finite, the range == f(Gn) is finite. To be precise, we have N = |Y] | = 2()).
Say, Y {yI,,..,,,,, UNN). For 1, , N, let gr : In - {0, be the Boolean function defined by
9 (G) (
if J(G) yt- otherwise.
Note that gi is invariant.
Let e, 8 0 and e' := m and == - By Lemma A.1 for every E {I...., .N3 there an MPNN with RNI Mú that deapprpooxiss gi. Putting all the Nr together, we obtain an invariant MPNN N that computes a function g: 9n (0.1)* 1, We only need apply the linear transformation
N
24 y4
to the output N to obtain the desired approximation of f.
Remark 1. Obviously, our construction yields MPNNs with a prohibitively large state space. In particular, this is the case for the brute force step from Boolean to general functions. We doubt that there are much more efficient approximators, after all we make assumption whatsoever on the function f.
The approximation of Boolean functions more interesting. It may still happen that the GNNs get exponentially large in n; this seems unavoidable. However, the nice thing here is that our con- struction very adaptive and tightly linked to the descriptive complexity of the function we want to approximate. This deserves more thorough investigation, which we leave for future work.
As opposed to other universality results for GNNs, our construction needs no higher-order tensors defined on tuples of nodes, with practically infeasible space requirements on all but very small graphs. Instead, the complexity of our construction goes entirely into the dimension of the state space. The advantage of this is that we treat this dimension hyperparameter that ily adapt and that gives us more fine-grained control over the space requirements. Our experiments show that usually in practice small dimension already yields very powerful networks.
cas-
Remark 2. In our experiments, we found that partial random initialization, which only assigns random values to a fraction of all node embedding vectors, often yields very good results, sometimes better than a full random initialization. There is plausibility to this from a theoretical perspective. For most graphs, we do not lose much by only initializing a small fraction of vertex embeddings, because in few message-passiinn construction above, individualize the full input graph. On the other hand, we reduce the amount of noise models have handle when only randomize partially.
rounds GNNs can propagate the randomness and, referring
15

---

Under review as a conference paper at ICLR 2021
d3
d.
d6
do
d2
20
20
21
1
22
22
33
33
d7
ds
(a) The encoding of the formula (P1-
d4
ds
d6
d7
Too
TD
F1
22
32
F3y
33
do
d3
d1
d2
(b) The encoding the formula (22-
Figure 4: Illustration of planar embeddings for the formulas Φ and (22 for n 2.
A.3 DETAILS DATASET CONSTRUCTION
There is interesting universality result for functions defined on planar graphs. It is known that 3- WL can distinguish between any pair of planar graphs (Kiefer et al,, 2019). Since 4-GCNs can sim- ulate 3-WL,, this implies that functions defined planar graphs be approximated by 4-GCNs. This result can be extended to much wider graph classes, including all graph classes excluding a fixed graph as a minor (Grohe 2017).
Inspired by this, we generate planar instances, and ensure that they can be distinguished by 2- WL., by carefully constraining these instances further. Hence, any GNN with 2-WL expressive power can approximate solutions to these planar instances. This, however, does not imply that these GNNs will solve ExP in practice, but only that an appropriate approximation function exists and can theoretically be learned.
A.3.1 CONSTRUCTION OF EXP
We now explain the construction and composition of EXP. Fundamentally. EXP consists of two main components, (i) pair of cores, which are non-isomorphic, planar, 1-WL indistinguishable, 2-WL distinguishable, and decide the satisfiability of every instance, and (ii) an additional randomly generated and satisfiable planar component, identically added the core pair, to add variability to ExP and make learning more challenging. We first present both components, and then provide further details about graph encoding and planar embeddings.
16

---

Under review as a conference paper at ICLR 2021
Core pair. In ExP, core pair consists of two CNF formulas (P,, (2,, both defined using 2n vari- ables, n E N+, such that fi is unsatisfiable and p2 is satisfiable, and such that their graph encodings are 1-WL indistinguishable and planar. (Pi and (22 are constructed using two structures which we refer to as variable chains and variable bridges respectively.
A variable chain Pehhain is defined over set of 2 Boolean variables, and imposes that all variables be equally set. The variable chain can be defined in increasing or decreasing order over these variables. More specifically, given variables Ti,...;j
Chain (i.j)
A (o v (=)((+1)9(())--))) and
(A.6)
j-1 (tainpec(t.)) A (xx (+()))))))))))))))
(A.7)
Additionally, a variable bridge is defined over an even number of variables To,,.., 12n-1 as
m-1
Abridge A (Z: A (T. 82n-1-1))
(A.8)
A variable bridge makes the variables it connects forcibly have opposite values, c.g., zo = σ for = 1. We denote variable bridge over z0, .... 12n-1 as Bridge(2n)..
To get şi and p2, we define yp as a variable chain and bridge on all variables, yielding contrasting and unsatisfiable constraints. To define (Pz, "cut" the chain in half, such that the first n variables can differ from the latter n, satisfying the bridge. The second half of the "cut" chain is then flipped to decrementing order, which preserves the satisfiability of (22, but maintains the planarity of the resulting graph. More specifically, this yields:
= Chainie (0, 2m) B2id and
(A.9)
22 Chain (0, n) A Chain (n,2n) A Bridge(2n).
(A.10)
Planar component. Following the generation of 9 and 42,, a disjoint satisfiable planar graph component PPllnnrr is added. Pplanar shares variables or disjunctions with the cores, so is primarily introduced to create noise and make learning more challenging. iPplanar is generated starting from random 2-connected (i.e., at least 2 edges must be removed to disconnect component within the graph) bipartite planar graphs from the Plantri tool (Brinkmann et al. 2007). such that (i) the larger set of nodes in the graph is the variable se (ii) cighee-connected disjunctions are split in planarity- preserving fashion to maintain disjunction widths not exceeding 5, (iii) literal signs for variables are uniformly randomly assigned, and (iv) redundant disjunctions, if any, are removed. If this Pplanar is satisfiable, then it is accepted and used. Otherwise, the formula is discarded and new Pplanar is analogously generated until satisfiable formula is produced.
Since the core pair and Pllanr are disjoint, it is easy to deduce that the graph encoding of Pplanar and (pplanrr A P2 are both planar and 1-WL indistinguishable. Furthermore, P A (P1 is satisfiable, and (pplanar P22 is not. Hence, the introduction of PPllanrr maintains all the desirable core properties, all while making any generated ExP dataset more challenging.
The structural properties of the cores, combined with the combinatorial difficulty of SAT, make EXP a challenging dataset. For example, even minor formula changes, such as flipping a literal, can lead to change in the SAT outcome, which enables the creation of near-identical, yet seman- tically different instances. Moreover, SAT is NP-complete (Cook) 1971), and remains so on planar instances (Hunt III et al. 1998). Hence, EXP is cast to be challenging, both from an expressiveness and computational perspective.
Remark 3. Intuitively, 9i and 22, generated as described, can be distinguished by 2- WL, as 2- detect the break in cycles resulting from the aforementioned "cut". In other words, 2- 2-WL can identify that the chain has been broken in between these two formulas, and thus will return distinct colourings. Hence, spi and i22 can be distinguished by 3-GCNs.
"Ties are hroken arhitrarily if the are equally sized.
17

---

Under review as a conference paper at ICLR 2021
Graph encoding. We the following graph encoding, denoted by Enc: (i) Every variable is encoded by two nodes, representing its positive and negative literals, and connected by an edge, (ii) Every disjunction is represented by a node, and an edge connects a literal node to disjunction node the literal appears in the disjunction, and (iii) Variable and disjunction nodes are encoded with different types. We opt for this encoding, as it is commonly used in the literature (Selsam al.) 2019), and is sufficient, for the sake of our empirical evaluation, to yield planar encodings for EXP graph pairs.
Planar embeddings for core pair. We show planar embeddings for Eno(y)) and Enc((p) for in Figure 4 and these embeddings can naturally be extended to any n. Enc((1) and Enc((p2) can also be shown to be 1-WL indistinguishable. This can be observed intuitively, as node neighbor- hoods in both graphs are identical and very regular: all variable nodes are connected to exactly one other variable node and two disjunction nodes, and all disjunction nodes are connected to exactly two variables.
A.3.2 CONSTRUCTION OF CEXP
Given a ExP dataset with N pairs of graphs, we create CEXP by selecting N/2 graph pairs and modifyyng them yield CORRUPT. The unmodified graph pairs are therefore exactly identical in type to EXP instances, and we refer to these instances within CEXP as EXP.
For every graph pair, we discard the satisfiable graph and construct new graph from a copy of the unsatisfiable graph as follows.
1. Randomly introduce new literals to the existing disjunctions of the copy of the unsatisfiable graph, such that no redundancies are created (i.e., adding x to a disjunction when x or T is already present), until literals are added and the formula becomes satisfiable. Literal addition is done by creating new edges in the graph between disjunction and literal nodes. To do this, disjunctions with less than 5 literals are uniformly randomly selected, and the literal to add is uniformly randomly sampled from the set of all non-redundant literals given the selected disjunction.
2. Once satisfiable formula is reached, iterate sequentially over all added edges, and elimi- nate any edge whose removal does not restore unsatisfiability. This ensures that a minimal number of new edges, relative to the original unsatisfiable graph, are added.
Observe that these modifications have several interesting effects the dataset. First, they preserve the existing UNSAT core nodes and edges, while flipping the satisfiability of their overall formulas, which makes the learning task go beyond structure identification. Second, they introduce significant new variability to the dataset, in that the planar component and cores can share edges. Finally, they make the graph pairs 1-WL distinguishable, which gives standard GNNs chance perform well on CORRUPT.
A.3.3 DATASET GENERATION FOR EXPERIMENTS
To create the EXP dataset, we randomly generate 600 core pairs, where (cf. Appendix A.3 uniformly randomly set between 2 and 4 inclusive. Then, we generate the additional planar component using Plantri, such that 500 Pplamar formulas are generated from 12-node planar bipartite planar graphs, and the remaining 100 from planar bipartite graphs with 15 nodes.
This generation process implies that every formula has number of variables ranging between 10 (4 core variables when 2 plus minimum 6 variables from the larger bipartite set during Pplanar generation from 12-node graphs) and 22 variables (8 core variables for n 4 plus maximally variable subset of 14 nodes for Pplanar generation from 15-node graphs)
Furthermore, the number of disjunctions also ranges from 10 (8 core disjunctions for 2 plus the minimum disjunctions for the case where Pplanar. generated from 12-node graphs, has 10 variables and 2 disjunctions) to 30 disjunctions (16 core disjunctions for 4 plus at most 14 disjunctions for the case where plaanar generated from 15-node graphs, initially has variables and 7 disjunctions, which can most lead to 14 final disjunctions following step (ii)).
18

---

Under review as a conference paper at ICLR 2021
A.4 STANDARD DEVIATION OF OCN-50%RNI ON EXP OVER TRAINING
In this subsection, investigate the variability of GCN-RNI learning across validation folds, and do so with representative model and dataset, namely the semi-randomized GCN- 50%RNI model and the standard Exp dataset. The standard deviation of the test accuracy of GCN-50%RNI over EXP, across all 10 cross-validation folds relative to the number of epochs, is shown in Figure From this figure, see that standard deviation spikes sharply at the start of training, and only begins dropping after 100 epochs. This suggests that the learn ing behavior of GCN-50% RNI is quite vari- able, sometimes requiring few epochs to con- verge, and in other cases requiring a very high number of epochs. Furthermore, standard de- viation converges to almost zero following 200 epochs, corresponding
8-10--
6-10-2
MM
4-10
M
2-10-2
Mmma
200
300
400
500
Training Epoch
Figure 5: Standard deviation of test accuracy over all 10 validation splits of 5ON-50%RNI on EXP.
the phase where validation folds have achieved near-perfect test performance. From these findings, we further con- firm that RNI introduces volatility to GCN training, this time manifesting in variable convergence times across validation folds, but that this volatility does not ultimately hinder convergence and performance, as all folds eventually reach satisfactory performance within a reasonable amount of epochs, and subsequently stabilize at this level.
A.5 ADDITIONAL EXPERIMENTS
In addition to the experiments in the main body of the paper, we additionally evaluate RNI on sparser analog datasets to EXP and CEXP, namely SPARSEEXP and SPARSECEXP. These datasets only contain 25% of the number of instances of their original counterparts, and are used to study the behavior and impact of RNI when data is sparse.
A.5.1 EXPERIMENT ON SPARSEEXP
In this experiment, we generate SPARSEEXP analogously to ExP, except that this dataset only con- sists of 150 graph pairs, i.e., 300 graphs in total. We then train 3-GCN for 200 epochs, and all other systems for 1000 epochs on SPARSEEXP, as opposed to 100 and 500 respectively for EXP, to give all evaluated models a better opportunity to compensate for the smaller dataset size. We show the learning curves for all models SPARSEEXP, and reproduce the original figure for Exp, in Figure for easier comparison.
First, observe that all models converge slower SPARSEEXP compared EXP. This is not surprising, as a lower data availability makes learning a well-performing function slower and more challenging. More specifically, sparsity implies that (i) fewer weight updates are made per epoch, and (ii) these updates are of lower quality, as they are computed from a less representative and com- plete dataset. Nonetheless, the same relative convergence patterns between GCN-RNI models and 3-GCN are also visible in this setting, further highighting the increased convergence time required by GCN-RNI models.
We also observe that all GCN-RNI models, though also eventually converging, do so in a more volatile fashion. Indeed, GCN-RNI models suffer from the sparseness the dataset, as this makes them more sensitive to RNI. As a result, these models require more training to effectively learn robustness against RNI values, and learn this from a smaller sample set, increasing their variability further. Moreover, the nature of SPARSEEXP makes learning more difficult, it fully relies RNI for MPNNs to have a chance of achieving above-random performance, and thus encourages MPNNs to fit specific RNI values. Hence, RNI introduces significant volatility and variability to training, particularly with sparser data, and requires substantial training and epochs for GCN-RNI models to effectively develop robustness RNI instantiations.
19

---

Under review as a conference paper at ICLR 2021
100
100
3-GCN
3-GCN
GCN-RNI
GCN-RNI
60
GCN-50% RNI
GCN-SO&RNI
OCN-87,55RRN
GCN-87
0CN-12.96RNI
GCN-12.58RNI
50
200
300
400
500
2010
400
600
800
1,000
Epoch
Epoch
(a) Learning curves EXP.
(b) Learning curves SPARSEEXP.
Figure 6: Model convergence results for Experiment on the datasets EXP and SPARSEEXP.
100
100
90
90
80
70
60
50
0
100
200
300
430
500
100
200
300
4000
500
Epach
Epoch
3-GCN
1-GCN
GCN-RNI
GCN-RNDC GCN-50%IC GCNE
GCNCC
12.5%
GCN-RNUE GCN-50%V
(a) Learning curves for all GCN-RNI models and
(b) Learning curves for CEXP, split across EXP
3-GCN on CExP.
(/E) and CORRUPT (/C).
100
100
90
90
80
80
200
400
600
800
1,000
200
400
600
800
1,000
Epoch
Epoch
3-GCN
1-GCN
GCN- GCN-RNI RNI
GCN-50%
GCN-87.5%
GCN-12.55
GCN/E GCN- GCN-50WWE
(c) Learning curves for GCN-RNI models and 3- 3-GCN on SPARSECEXP.
(d) Learning curves SPARSECEXP, split across
EXP (/E) and CORRUPT (/C).
Figure 7: Model convergence results for Experiment on CEXP and SPARSECEXP.
A.5.2 EXPERIMENT ON SPARSECEXP
Analogously to Experiment 1, we generate a SPARSECEXP dataset similarly to CEXP, but only generate 150 graph pairs. Then, select 75 graph pairs and modify them, described in Ap- pendix A.3.2 We report the learning curves for all models on SPARSEČEXP, as well as the original curves for CEXP from the main body, in Figure
20

---

Under review as a conference paper at ICLR 2021
Table 2: Hyper-parametce configurations for all GCN-RNland 3-GCN experiments.
Dataset
ExP
CEXP
A
p
A
GCN
1x 10
N/A
1x 10
N/A
GCN-12.5%RNN
2x 10-4
N
2x 10
N
GCN-50%RNI
2x 10-4
N
2x 10
N
GCN-87.5%RNI
2x 10
N
5 10
N
GCN-RNI
5 10
N
5 10
N
3-GCN
5 10-4
N/A
2 10
N/A
Table 3: Performance of GCN-RNI models the ExP dataset with the hyperbolic tangent activation function.
Model
Testing Accuracy (%)
GCN-RNI(U)
92.7 = 5.61
GCN-RNI(N)
96.0 = 2.11
GCN-RNI(XU)
64.6 = 19.9
GCN-RNI(XN)
63.0 + 20.9
As in the previous subsection, similar behavior is observed on SPARSECEXP compared with CEXP, only differing by slower convergence the former case. However, we note that the "struggle" phase described in the main paper, which only occurs during the first 100 epochs over CExP, lasts for around 500 epochs on SPARSEEXP. Intuitively, this "struggle" phenomenon is due to conflicting learning requirements, stemming from CORRUPT and EXP, which effectively require models to "isolate" deterministic dimensions for CORRUPT, and other randomized dimensions for EXP. This in itself is already challenging on CEXP, but is made even more difficult on SPARSECEXP due to its sparsity. Indeed, sparsity makes that further samples needed in expectation find a reasonable solution, leading lengthy "struggle" phase, in which both CORRUPT and ExP data points conflict with one another during optimization.
A.6 HYPER-PARAMETER DETAILS
All GCN models with (partially or completely) deterministic initial node embeddings map 2- dimensional one-hot encoding of node type (literal or disjunction) to k-dimensiona embedding space, where corresponds the dimensionality of the deterministic embeddings. Furthermore, the final prediction for every graph is computed by aggregating all node embeddings following message passing using the max function, and then passing the result through a multi-layer perceptron layers with dimensionality æ. 32 and respectively, where is the embedding dimensionality used in the given model. The activation function for the first two MLP layers is the ELU function (Clevert al. 2016), and the softmax function is used make final prediction at the final MI.P layer.
All neural networks in this work are optimized using the Adam optimizer KKngmma & Ba 2015
All training is conducted with fixed learning rate X, for fairer comparison between all models. Initially, decaying learning rates were used, but these were discarded, as they yielded sub-optimal convergence for all GCN-RNI models. Finally, all experiments were run V100 GPU. Detailed hyper-parameters, namely learning rate X and RNI distribution p. per model on every evaluation dataset are shown in Table 2
A.6.1 RESULTS FOR GCN-RNI WITH HYPERBOLIC TANGENT ACTIVATION
In addition experimenting with the RNI probability distribution, we also experimented with dif- ferent activation functions for the GCN message passing iterations. Results are shown Table Performance with tanh is significantly more variable across distributions than ELU, which shows that RNI can be highly sensitive to practical choices of hyper-parameters.
21


Reviews:
[{"review_id": "oW_KpNFOhq", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper study the effects of adding random features (RF) to graph neural networks (GNN). First, it is shown that, quite surprisingly, adding random features makes GNN universal approximators of invariant functions. Next, a novel dataset is defined that is aimed at evaluating the performance of models that have high expressive power. Finally, several experiments show that adding RF performs well on the proposed dataset.\n\nI think the paper is well written and well organized. The theoretical aspect seems novel and quite surprising, especially since it shows that adding RF makes GNN more expressive than k-GCN (or k-IGN) for any k. The new proposed dataset is interesting, and the experimental result looks promising, especially since RF performs quite well compared to 3-GCN while having much fewer parameters. Also, the observation that only partial randomness can already be beneficial is interesting.\n\nI have a couple of concerns regarding the paper for which I would be happy to see the authors’ comment:\n1)\tThe phrasing of Theorem 4.1 is a bit vague because it is stated with an \\epsilon, \\delta approximation while there is no clear explanation of how these parameters affect the theorem. I suppose that smaller \\epsilon, \\delta would mean a wider network, but this dependence should be shown explicitly. For \\delta, this dependence is somewhat shown in the proof of Lemma A.5, but for \\epsilon it is very unclear and is probably related to Lemma A.2 which cited from another paper.\n2)\tIf I understand the proof correctly, the width of the network in Lemma A.1 (and also in Theorem 4.1) should be super-exponential, no matter what is the target function. That is because in Lemma A.4 the sentence takes into account every graph in G_{n,k}, the number of such graphs is super-exponential and I suppose that the width of the GNN that realizes the sentence depends on the length of the sentence (or at least the number of literals). If this is true, then I think it is important to point that out in the main text.\n3)\tContinuing the previous point, the paragraph after Remark 1 isn’t clear: why the construction is adaptive to the descriptive complexity of the target function if for any target function the construction requires memorization of all graphs with n nodes?\n4)\tRegarding the Experimental results, I think it is important to also test RF on real datasets. The reason is that without this experiment it is not clear if adding RF doesn’t actually harm the performance of GNN and thus are actually very impractical. As the authors stated, I don’t expect RF to significantly improve performance on real datasets because high expressivity might not be required, but I am concerned that it will hurt the performance. \n\nI also highly suggest uploading the EXP and CEXP datasets as supplementary material, since these are newly generated datasets, and this way other people could also experiment on them and compare performance.\n\nTo conclude, I think this is a very nice and well-written paper that adds a novel view on adding RF to GNN, both theoretically and empirically. With that said, there are some issues with the vague form in which the main theorem is stated, and experiments on real datasets would help clarify whether adding RF could actually prove helpful (or at least not harmful) for practical uses.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "hU64h-c5P-R", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper studies the power of message passing neural networks (MPNNs) with random node initialization (RNI). Although the power of standard MPNNs is limited to 1-WL, the main result of the paper is to prove that RNI makes MPNNs universal. The paper also introduces two graph classification datasets where each graph is a SAT problem and the label is the satisfiability/unsatisfiability. The datasets have been created in a way that their graphs are 1-WL indistinguishable to serve as a test-bed for graph neural networks with power beyond 1-WL. The results on these two datasets show the merit of adding RNI to MPNNs.\n\nMy biggest reservation with this work is that the theoretical and empirical results do not seem to offer much more than what has already been provided in [1]. In fact, if [1] didn't exist, I would have given a strong acceptance to this paper. I’ll elaborate on each of these aspects below:\n\nTheoretical result: While Theorem 4.1 is quite strong as it imposes no restrictions on the function f, two things are not clear to me: 1- What classes of functions does the Theorem 1 of [1] not cover that Theorem 4.1 of this paper does?, 2- Is the Theorem 4.1 of this paper a straightforward extension of the Theorem 1 in [1]?\n\nEmpirical results: While I appreciate the two datasets developed in this work and I believe they can be useful for future research, I have a hard time understanding what intuition/insights the results provide that has not been already provided in [1]. It has been already shown in [1] that RNI increases the power of MPNNs and enables them to do well on graphs that are 1-WL indistinguishable, where existing MPNNs fail. If Theorem 4.1 covers a larger class of models than Theorem 1 of [1], then I would expect at least some experiments covering those classes of models. Right now, the only added insight of the empirical results seems to be that randomizing a subset of the nodes is better than randomizing all of them.\n\nAll mentioned about the connection between this work and [1] is “Indeed, RNI has enabled MPNNs to distinguish instances that 1-WL cannot distinguish, and is proven to enable better approximation of a class of combinatorial problems (Sato et al., 2020). However, the effect of RNI on the expressive power of GNNs has not yet been comprehensively studied, and its impact on the inductive capacity and learning ability of GNNs remains unclear.”, which does not seem satisfactory.\n\nOther comments/questions: 1- Some experiments on standard benchmarks can strengthen the paper. 2- For GCN-x%RNI, how do you initialize the other (1-x)% of the nodes? Do you initialize them as all 0s? 3- In [1], a new random feature is assigned every time the procedure is called. Is this what you do as well? 4- Any reason why the results of 1-GCN and GCN-x%RNI are not reported in Table 1?\n\n[1] Sato, Ryoma, Makoto Yamada, and Hisashi Kashima. \"Random Features Strengthen Graph Neural Networks.\" arXiv preprint arXiv:2002.03155 (2020).", "extra_scores": {}, "extra_text": {}}, {"review_id": "atROVkh4ai", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "**Post Rebuttal**\nI thank the authors for the quick replies and updates to the paper. \nI keep my positive score.\n\n---\n\n\n**Summary of Contributions**\nThe paper analyzes the model of Random features in GNNs as suggested by Sato et.al., in the paper called RNI.\nA result proving the universality of the RNI framework is introduced, a first of its kind in low tensor degree GNNs. \nTo evaluate the expressiveness of RNI and other more expressive GNNs, the authors design two datasets wich require 2-WL distinguishing power (which is higher than the ones MPNNs have)\n\n**Strengths**\n- Novelty - The universality result on RNI is novel and further extends the hints of improved expressiveness explored by Sato et.al.\n- Dataset design - the design of new datasets for expressiveness discrimination are an important contribution to the community. \n\n**Weaknesses**\n\n- Regarding invariance of RNI - a more rigorous explanation would be fit there. Why does RNI preserve invariance? \n- The main theoretical result of the paper is just appearing in the paper without details and intuitions towards the proof, a proof sketch or some discussion of that flavor would make the result more clear. \n- The experimental setting is not clear enough as presented in the main body of the paper. A lot of important details has to be dug our from the appendix which is tedious for the reader. For example:\n1. The partial RNI is not well explained in the paper, and it was not clear whether the partial applies to the feature dimensions or the nodes. \n2.  The input features in the designed datasets are not mentioned in the body of the paper. \n3. An elaborate description of the 3-GCN variant is missing. \n\n- *Partial RNI* - can the authors provide an intuition as to why it works? In a way, the universality comes from the network not taking into account the node features due to the full randomness but more of a statistical behavior and the fact that the nodes are completely distinguishable. So why does partial randomness work?\n\n\n**Recommendation**\nThe paper states an important and surprising result which can contribute greatly to the graph learning community. \nA good paper, Accept.\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "EglAglYx-v", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper studies the how random initialization of node states can improve the expressivity of message passing graph neural networks. Theoretically the paper shows that RNI makes MPNNs universal approximators for invariant functions over graphs. To supplement this claim, the authors evaluate GNNs with RNI and higher-order GNNs over a carefully constructed synthetic dataset and show that RNI (even if only a fraction of the nodes are randomly initialized) are as expressive as higher order GNNs. They also highlight some drawbacks of this approach, such as slower training and sensitivity to hyperparameter tuning.\n\nOverall, I find the topic and the findings of the paper quite interesting. However, explanations as to why or how randomness helps is missing in the paper. There is also room for improvement in the presentation and writing. The statement of Theorem 4.1 is a little vague; it would help if its made more precise (e.g., how much randomness is required, what is the depth of the MPNN required, the state dimensions etc.). The notion of invariance and equivariance can also be defined much earlier in the paper. \n\nWhile it’s interesting that randomness can yield MPNNs to be universal approximators, could you please give some intuition as to what makes randomness so essential? In the proof of Theorem 4.1 (in Appendix A.2), the random initialization together with the linearized sigmoid activation function is used to show that the vectors $x_i^(1)$ are mutually distinct {0, 1} vectors with high probability. To my understanding, this is the only place where the randomness of the initialization is used. If that is the case, why can’t any deterministic initialization that ensures mutually distinct {0, 1} vectors for $x_i^(1)$ suffice?  \n\nThe datasets EXP and CEXP seem to be motivated as graph encoding of SAT problems. Are they bipartite graphs? Could you give a sense for how the graphs look like (number of nodes, edges etc.)? \n\nIn the partial random node initialization (GCN-x% RNI), are you initializing some nodes randomly and other deterministically? Or are you initializing some entries in the state vector randomly and remaining entries deterministically? \n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: In this paper, the authors show the effect of RNI on the expressive power of GNN for the first time, where the RNI was initially proposed in Sato et al. 2020. Overall, I like the idea of random node initialization because it is simple, effective, and theoretically well-founded. The key concern was that the novelty over the Sato's paper and the reviewers were still not convinced by the response. Therefore, the paper is still below the acceptance threshold.  I strongly encourage authors to revise the paper based on the reviewer's comments and resubmit it to a future venue. 

Decision: Reject