Coloring graph neural networks for node disambiguation
Authors: George Dasoulas
Ludovic Dos Santos
Kevin Scaman
Aladin Virmaux
Venue:  (2020)
Keywords: Graph neural networks
separability
node disambiguation
universal approximation
representation learning

Abstract: In this paper, we show that a simple coloring scheme can improve, both theoretically and empirically, the expressive power of Message Passing Neural Networks (MPNNs). More specifically, we introduce a graph neural network called Colored Local Iterative Procedure (CLIP) that uses colors to disambiguate identical node attributes, and show that this representation is a universal approximator of continuous functions on graphs with node attributes. Our method relies on separability, a key topological characteristic that allows to extend well-chosen neural networks into universal representations. Finally, we show experimentally that CLIP is capable of capturing structural characteristics that traditional MPNNs fail to distinguish, while being state-of-the-art on benchmark graph classification datasets.

Under review as a conference paper at ICLR 2020
COLORING GRAPH NEURAL NETWORKS FOR NODE DISAMBIGUATION
Anonymous authors Paper under double-blind review
ABSTRACT
In this paper, we show that simple coloring scheme can improve, both theoreti- cally and empirically, the expressive power of Message Passing Neural Networks (MPNNs). More specifically, we introduce graph neural network called Colored Local Iterative Procedure (CLIP) that uses colors to disambiguate identical node at- tributes, and show that this representation is a universal approximator of continuous functions on graphs with node attributes. Our method relies on separability, a key topological characteristic that allows to extend well-chosen neural networks into universal representations. Finally, we show experimentally that CLIP is capable of capturing structural characteristics that traditional MPNNs fail to distinguish, while being state-of-the-art on benchmark graph classification datasets.
INTRODUCTION
Learning good representations is seen by many machine learning researchers as the main reason behind the tremendous successes of the field in recent years (Bengio et al. 2013). In image analy- sis (Krizhevsky et al., 2012), natural language processing (Vaswani et al. 2017) reinforcement learning (Mnih et al. 2013), groundbreaking results rely on efficient and flexible deep learning architectures that are capable of transforming a complex input into simple vector while retaining most of its va valuable features. The universal approximation theorem (Cybenko 1989 Hornik et al. 1989 Hornik 199T Pinkus 1999) provides theoretical framework analyze the expressive power of such architectures by proving that, under mild hypotheses, multi-layer perceptrons (MLPs) can uniformly approximate any continuous function on compact set. This result provided a first theoret- ical justification of the strong approximation capabilities of neural networks, and was the starting point of more refined analyses providing valuable insights into the generalization capabilities of these
architectures (Baum and Haussler 1989
Geman et al. 1992. Saxe et al. 2014 Bartlett et al.) 2018).
Despite large literature and state-of-the-art performance on benchmark graph classification datasets, graph neural networks yet lack similar theoretical foundation (Xu al. 2019). Universality for these architectures is either hinted at via equivalence with approximate graph isomorphism tests (k-WL tests in Xu et al. 2019 Maron et al. 2019a), proved under restrictive assumptions (finite node attribute space in Murphy et al. 2019). In this paper. we introduce Colored Local Iterative Procedure") (CLIP), which tackles the limitations of current Message Passing Neural Networks (MPNNs) by showing, both theoretically and experimentally, that adding a simple coloring scheme can improve the flexibility and power of these graph representations. More specifically, our contributions are: 1) we provide a precise mathematical definition for universal graph representations, 2) we present a general mechanism to design universal neural networks using separability, 3) we propose novel node coloring scheme leading to CLIP, the first provably universal extension of MPNNs, 4) we show that CLIP achieves state of the art results on benchmark datasets while significantly outperforming traditional MPNNs as well as recent methods on graph property testing.
The rest of the paper organized as follows: Section 2 gives an overview of the graph representation literature and related works. Section provides a precise definition for universal representations, as well as a generic method to design them using separable neural networks. In Section we show that most state-of-the-art representations are not sufficiently expressive to be universal. Then, using the analysis of Section Section S provides CLIP, a provably universal extension of MPNNs. Finally,
Cooee will he available at htttts//ggihhuh.co///aaa after the review process.

---

Under review as a conference paper at ICLR 2020
Section shows that CLIP achieves state-of-the-ar accuracies on benchmark graph classification taks, as well as outperforming its competitors on graph property testing problems.
RELATED WORKS
The first works investigating the use of neural networks for graphs used recurrent neural networks to represent directed acyclic graphs (Sperduti and Starita 1997; Frasconi et al. 1998). More generic graph neural networks were later introduced by Gori et al. (2005); Scarselli et al. (2009) and may be divided into two categories. 1) Spectral methods (Bruna et al. 2014 Henafi et al. 2015 Defferrard et al. 2016 Kipf and Welling 2017) that perform convolution on the Fourier domain of the graph through the spectral decomposition of the graph Laplacian. 2) Message passing neural networks (Gilmer et al. 2017), sometimes simply referred to as graph neural networks, that are based on the aggregation of neighborhood information through local iterative process. This category contains most ofate-o--the-ade graph representation methods such as (Duvenaud et al. 2013 Grover and Leskovec 2016 [ei al. 2017 Ying et al. 2018 Verma and Zhang 2019), Deep (Perozzi it al. 2014), graph attention networks (Velickovic et al. al. 2018). graphSAGE (Hamilton et al. 2017)
or GIN (Xu al. 2019).
Recently, (Xu et al., 2019) showed that MPNNs were, at most, as expressive as the Weisfeiler- Lehman (WL) test for graph isomorphism WWisfeiler and Lehman 1968). This suprising result led to several works proposing MPNN extensions to improve their expressivity. and ultimately tend towards universality (Maron et al. 2019abbec Murphy et al., 2019; Chen et al. 2019). However, these graph representations are either as powerful as the k- WL test (Maron et al. 2019a), or provide universal graph representations under the restrictive assumption of finite node attribute space (Murphy et al.. 2019). Other recent approaches (Maron et al., 20T9c) implies quadratic order of tensors in the size of the considered graphs. Some more powerfull GNNs are studied and benchmarked on real classical datasets and on graph property testing (Kriege et al. 2018 Murphy et al. 2019 Chen et al. 2019): set of problems that classical MPNNS cannot handle. Our work thus provides a more general and powerful result of universality, matching the original definition of (Cybenko 1989) for MLPs.
3 UNIVERSAL REPRESENTATIONS VIA SEPARABILITY
In this section we present the theoretical tools used to design our universal graph representation. More specifically, we show that separable representations are sufficiently flexible to capture all relevant information about a given object, and may be extended into universal representations.
3.1 NOTATIONS AND BASIC ASSUMPTIONS
Let X, be two topological spaces, then F(X', y) (resp. (()) denotes the space of all functions (resp. continuous functions) from X' to Y Moreover, for any group G acting on set X, X/G denotes the set of orbits of X under the action of G (see Appendix for more details). Finally, ||- is norm Rdd, and P,, is the set of all permutation matrices of size In what follows. assume that all the considered topological spaces are Hausdorff (see e.g. (Bourbaki) 1998) for an in-depth review): each pair of distinct points can be separated by two disjoint open sets. This assumption is rather weak (e.g. all metric spaces are Hausdorff) and is verified by most topological spaces commonly encountered in the field of machine learning.
3.2 UNIVERSAL REPRESENTATIONS
Let X be a set of objects (e.g. vectors, images, graphs, or temporal data) to be used as input information for machine learning task (e.g. classification, regression or clustering). what follows, we denote as vector representation of X' function f X - Ie that maps each element x E X' to a d-dimensional vector f(x) E Rd. A standard setting for supervised representation learning is to define class of vector representations 3a C F(X, Rd) (e.g. convolutional neural networks for images) and use the target values (e.g. image classes) to learn a good vector representation in light of the supervised learning task (i.e. one vector representation f E 3a that leads to good accuracy the learning task). In order to present more general results, we will consider neural network architectures that output vectors of any size, i.e. 3 C Uden- F(X, Rd), and will denote S. = 3 n F(X, Rd)
2

---

Under review as a conference paper at ICLR 2020
Input (c gruph)
Output (voctor)
(f.9)
Separable representation
MLP
9
Universal representation
input hidden layer output
Figure 2: Universal representations can eas- ily be created by combining separable rep- resentation with an MLP.
Figure 1: Concatenation of two MLPs f and
the set of d-dimensional vector representations of A natural characteristic ask from the class & is to be generic enough to approximate any vector representation, notion that we will denote as universal representation (Hornik et al., 1989).
Definition 1. A class of vector representations & C UaEN F(X, Rd) is called universal represen- tation of X' if for any compact subset K C X and d E N , F is uniformly dense in C(K, IR..
In other words, is a universal representation of normed space if and only for any continuous function Φ X + Rd, any compact K C X and any >> 0, there exists f E 3 such that
Vr E K, [Ø(z) - f())]l E.
(1)
One of the most fundamental theorems of neural network theory states that hidden layer MLPs are universal representations of the m-dimensional vector space R"
R -> be a continuous non polynomial activation function. For any compact K C Ih and d E N two layers neural networks with activation are uniformly dense in the set C(K,
Theorem (Pinkus] 1999 Theorem 3.1). Let yo
However, for graphs and structured objects, universal representations hard to obtain due to their complex structure and invariance to a group of transformations (e.g. permutations of the node labels). We show in this paper that key topological property, separability, may lead universal representations of those structures.
3.3 SEPARABILITY IS (ALMOST) ALL YOU NEED
Loosely speaking, universal representations can approximate any vector-valued function. It is thus natural to require that these representations are expressive enough separate each pair of dissimilar elements of X.
Definition 2 (Separability). A set of functions 3 F(X,)) is said separate points of X if for every pair of distinct points and y. there exists f E 3 such that f(x) # f(y).
For a class of vector representations C UnEN-F(Xt, IR,), we will say that & is separable if its 1-dimensional representations 31 separates points of X. Separability is rather weak, require the existence different outputs for every pair of inputs. Unsurprisingly, we now show that is necessary condition for universality (see Appendix for all the detailed proofs).
only
Proposition 1. Let 3 be universal representation of X. then 31 separates points of X.
While separability is necessary for universal representations, it is also key to designing neural network architectures that can be extended into universal representations. More specifically, under technical assumptions, separable representations can composed with a universal representation of Rd (such MLPs) to become universal.
Theorem 2. For all d 2 0, ler Ma be universal approximation of R.d. Let & be class of vector representations of X such that:
(i) Continuity: every E 3 is continuous,
(i) Stahility by concatenation: for all J.g 3, x. (f()),g(x)) E

---

Under review as a conference paper at ICLR 2020
(iii) Separability: 31 separates points of X.
Then o EE 2 1 s.t. & Ma E $) is universal representation of X.
Stability by concatenation is verified by most neural networks architectures, as illustrated for MLPs in Figure [ The proof of Theorem 2
relies the Kione-Weierstraat theorem (see e.g. Rudin 1987. Theorem 7.32) whose assumptions are continuity, separability, and the fact that the class of functions an algebra. Fortunately, composing separable and concatenable representation with universal representation automatically leads to an algebra, and thus the applicability of the Stone- Weierstrass theorem and the desired result. complete derivation available in Appendix A Since MLPs are universal representations of IR Theorem 2 implies convenient way to design universal representations of more complex object spaces: create a separable representation and compose it with simple MLP (see Figure 2
Corollary 1. A continuous, concatenable and separable representation of X composed with an MLP universal.
Note that many neural networks of the deep learning literature have this two steps structure, including classical image CNNs such as AlexNet (Krizhevsky et al.) (2012) or Inception (Szegedy et al., (2016). In this paper, we use Corollary to design universal graph and neighborhood representations, although the method is much more generic and may be applied to other objects.
4 LIMITATIONS OF EXISTING REPRESENTATIONS
In this section, we first provide a proper definition for graphs with node attributes, and then show that message passing neural networks are not sufficiently expressive to be universal.
4.1 GRAPHI WITH NODE ATTRIBUTES
Consider a dataset of n interacting objects (e.g. users of social network) in which each object i E [1, ni] has vector attribute E Rm and is node in undirected graph G with adjacency matrix A E Raxn
Definition 3. The space of graphs of size n with m-dimensional node attributes is the quotient space
Graphm,n {(v, g= R } PPn,
where A is the adjacency matrix of the graph, contains the m-dimensional representation of each node in the graph and the set of permutations matrices P,, is acting on (u, A) by
vP Pn. P. (v.A) (Pv, PAPT).
Moreover, we limit ourselves to graphs of maximum size Tmmax where mmax is large integer. This allows us to consider functions on graphs of different sizes without obtaining infinite dimensional spaces and infinitely complex functions that would be impossible to learn via finite number of samples. We thus define Graph,, m = Un Graph m.n. More details on the technical topological aspects of the definition are available in Appendix as well as a proof that Graph,,, Hausdorff.
4.2 MESSAGE PASSING NEURAL NETWORKS
A common method for designing graph representations is to rely on local iterative procedures. Following the notations of Xu al. (2019), a message passing neural network (MPNN) (Gilmer
et al. 2017) is made of three consecutive phases that will create intermediate node representations Ji, for each node i E [1. n] and a final graph representation IG as described by the following procedure: 1) Initialization: All node representations are initialized with their node attributes
Fio0 = Uj. 2) Aggregation and combination: T local iterative steps are performed in order to capture larger and larger structural characteristics of the graph. 3) Readout: This step combines all final node representations into a single graph representation: 26 = READOUT( ([=,r he(..)). where READOUT is permutation invariant.
4

---

Under review as a conference paper at ICLR 2020
2
22
Figure 3: Example of two valid colorings of the same attributed graph. Note that each V2 contains nodes with identical attributes.
Unfortunately, while MPNNs are very efficient in practice and proven to be as expressive as the Weisheiler-Lehman algorithm (Weisfeiler and Lehman 1968 Xu et al. 2019), they not sufficiently expressive to construct isomorphism tests or separate all graphs (for example, consider k-regular graphs without node attributes, for which small calculation shows that any MPNN representation will only depend on the number of nodes and degree & (Xu et al. (019)). As a direct application of Proposition I MPNNS are thus not expressive enough to create universal representations.
EXTENDING MPNNS USING A SIMPLE COLORING SCHEME
In this section, we present Colored Local Iterative Procedure (CLIP), an extension of MPNNs using colors to differentiate identical node attributes, that is able to capture complex structural graph characteristics than traditional MPNNs. This is proved theoretically through universal approximation theorem in Section 5.3 and experimentally in Section 6 CLIP is based three consecutive steps: 1) graphs are colored with several different colorings, 2) neighborhood aggregation scheme provides a vector representation for each colored graph, 3) all vector representations are combined provide final output vector. We now provide more information on the coloring scheme.
5.1 COLORS TO DIFFERENTIATE NODES
In order to distinguish non non-isomorphic graphs, our approach consists in coloring nodes of the graph with identical attributes. This idea inspired by classical graph isomorphism algorithms that colors to distinguish nodes (McKay 1981), and may be viewed as an extension of one-hot encodings used for graphs without node attributes (Xu al. 2019).
For any E N. let C3 be a finite set of colors. These colors may be represented as one-hot encodings (O& is the natural basis of R*) or more generally any finite set of & elements. At initialization, we first partition the nodes into groups of identical attributes Vi, VK C [1, n]. Then, for subset 1/2 of size VVll we give to each of its nodes distinct color from Cg (hence a subset of size VVl). For example, Figure shows two colorings of the same graph, which is decomposed in three groups V/1 122 and V/3 containing nodes with attributes a, and e respectively. Since Vi contains only two nodes, coloring of the graph will attribute two colors ((1, 0) and (0, 1), depicted as blue and red) to these nodes. More precisely, the set of colorings (v, A) of a graph G = (u, A) are defined as
C(v, A) = (ci,.., Go) AK E [1. K1. (G))ev, is permutation of Civil
(4)
5.2 THE CLIP ALGORITHM
In the CLIP algorithm, we add a coloring scheme to an MPNN in order to distinguish identical node attributes. This achieved by modifying the initialization and readout phases of MPNNs as follows.
1. Colored initialization: We first select set C2 C C(v, A) of k distinct colorings uniformly at random (see Eq. (4). Then, for each coloring E C₁. node representations are initialized with their node attributes concatenated with their color: zT.0 (t)..).
2. A Aggregation and combination: This step is performed for all colorings E C₁ using uni-
versal set representation as the aggregation function: af,411 1000 (x ΣjeN, (1)()))
5

---

Under review as a conference paper at ICLR 2020
where & and yp are MLPs with continuous non-poln non-polynomial activation functions and sx y) denotes the result of & applied to the concatenation of x and y. The aggregation scheme we propose is closely related to DeepSet (Zaheer et al. 2017), and direct application of Corollary 1 proves the universality of our architecture. More details, as well as the proof of
universality, available in Appendix [
3. Colored readout: This step performs maximum over all possible colorings in order to obtain final iirreingnideeeeeent graph representation. In order to keep the stability by concatenation, the maximum is taken coefficient-v wise
T1
DG
v
max CECr
(5)
where db is an MLP with continuous non polynomial activation functions.
We treat k as hyper-paramettr of the algorithm and call k-CLIP (resp. co-CLIP) the algorithm using & colorings (resp. all colorings, i.e. k [C(v, A)). Note that, while our focus is graphs with node attributes, the approach used for CLIP is easily extendable to similar data structures such as directed or weighted graphs with node attributes, graphs with node labels, graphs with edge attributes or graphs with additional attributes at the graph level.
5.3 UNIVERSAL REPRESENTATION THEOREM
As the colorings are chosen at random, the CLIP representation is itself random soon as l < (C(u, and the number of colorings 1 will impact the variance of the representation. However, co-CLIP is deterministic and permutation invariant, as MPNNs are permutation invariant. The separability is less trivial and is ensured by the coloring scheme.
Theorem 3. The co-CLIP algorithm with one local iteration (T = 1) a universal representation of the space Graph,, of graphs with node attributes.
The proof of Theorem Saaarem@rrliie relies on showing that co-CLIP is separable and applying Corollary [ This achieved by fixing a coloring on one graph and identifying all nodes and edges of the second graph using the fact that all pairs (vi, es) are dissimilar (see Appendix D). Similarly to the case of MLPss only one local iteration is necessary to ensure universality of the representation. This rather counter-intuitive result is due to the fact that all nodes can be identified by their color, and the readout function can aggregate all the structural information for MLPs, one may expect poor generalization capabilities for CLIP with only local iteration, and deeper networks may allow for more complex representations and better generalization. This point is addressed in the experiments of Section 6 Moreover, co-LLIP may be slow in practice due to a large number of colorings, and reducing k will speed-up the computation. Fortunately, while k-CLIP is random, similar universality theorem still holds even for lc
complex and non-trivial way. However, as
Theorem 4. The 1-CLIP algorithm with one local iteration (T 1) is random representation whose expectation is a universal representation of the space Graph,, of graphs with node attributes.
The proof of Theorem 4 relies on using co-CLIP on the augmented node attributes =/ (wi, cc). As all node attributes are, by design, different, the max over all colorings in Eq. (5) disappears and, for any coloring, 1-CLIP returns an E-approximation of the target function (see Appendix D).
Remark 1. Note that the variance of the representation may be reduced by averaging over multiple samples. Moreover, the proof of Theorem shows that the variance can be reduced an arbitrary precision given enough training epochs, although this may lead to very large training times in practice.
5.4 COMPUTATIONAL COMPLEXITY
As the local iterative steps are performed T' times on each node and the complexity of the aggregation depends on the number of neighbors of the considered node, the complexity is proportional to the number of edges of the graph E and the number of steps T. Moreover, CLIP performs this iterative aggregation for each coloring, and its complexity is also proportional to the number of chosen colorings k = |Cx|- Hence the complexity of the algorithm is in O(kFT))

---

Under review as a conference paper at ICLR 2020
Note that the number of all possible colorings for a given graph depends exponentially in the size of the groups Vi...., VR.
K
C(v, A) II V&l!
(6)
and thus co-CLIP is practical only when most node attributes are dissimilar. This worst case exponential dependency the number of nodes can hardly avoided for universal representations. Indeed, universal graph representation should also be able to solve the graph isomorphism problem. Despite the existence of polynomial time algorithms for a broad class of graphs (Luks, 1982] Bodlaender 1990). graph isomorphism is still polyiopoly in general (Babai) 2016). As result, creating a universal graph representation with polynomial complexity for all possible graphs and functions to approximate is highly unlikely, it would also induce graph isomorphism test of polynomial complexity and thus solve very hard and long standing open problem of theoretical computer science.
EXPERIMENTS
In this section we show empirically the practical efficiency of CLIP and its relaxation. We run two sets of experiments to compare CLIP w.r.t state-of-the-arr methods supervised learning settings: i) on 5 real-world graph classification datasets and ii) on 4 synthetic datasets to distinguish structural graph properties and isomorphism. Both experiments follow the same experimental protocol as described in Xu al. (2019) 10-fold cross validation with grid search hyper-parameter optimization. More details on the experimental setup are provided Appendix E
6.1 CLASSICAL BENCHMARK DATASETS
We performed experiments on five benchmark datasets extracted from standard social networks (IMDBb and IMDBm) and bio-informatics databases (MUTAG, PROTEINS and PTC). All dataset characteristics (e.g. size, classes), as well as the experimental setup, are available in Appendix E Following standard practices for graph classification on these datasets. we use one-hot encodings of node degrees as node attributes for IMDBb and IMDBm (Xu al., 2019), and perform single- label multi-class classification on all datasets. We compared CLIP with six state-of-the-ar baseline algorithms: WL. Weisfeiler-Lehmee
subtree kernel (Shervashidze et al.) 2011]. I 2) AWL: Anony-
neural mous Walk Embeddings (Ivanov and Burnaev 2018). 3) DCNN: Diffusion-convolution
networks (Atwood and [owsley]][016 4) PS: PATCHY-SAN (Niepert et al. 2016). 5) DGCNN: Deep Graph CNN (Zhang et 20118) and 6) GIN: Graph Isomorphism Network (Xu et 2019). WL and AWL are representative of unsupervised methods coupled with an SVM classifier, while DCNN, PS, DGCNN and GIN are four deep learning architectures. As the same experimental protocol as that of Xu et al. (2099) was used, we present their reported results on Table
Table I: Classification accuracies of the compared methods on benchmark datasets. The best performer w.r.t. the mean is highlighted with an asterisk. We perform unpaired t-test with asymptotic significance of 0. w.r.t the best performer and highlight with boldface the ones for which the difference is not statistically significant, O-CLIP is the CLIP architecture without any colorings.
Dataset
PTC
IMDBb
IMDBm
PROTEINS
MUTAG
WL
59.9
73,813.9
50.913.8
75.0
90.415.77
DCNN
56.6
49.1
33.5
61.3
67.0
PS
60.0
71.0+2.2
45.2+22.8
75.9+
92.6+t4.2
DGCNN
58.6
70.0
47.8
75.5
85.8
AWL
74.5+5.99
51.5+13.6
87.949.8
GIN
64.6.17.00
75.145.1
52.3-12.8
76.2.1
89,4415.6
0-CLIP
65.9+14.0 67.9+7.1*
75.4+22.0
52.5++2.6*
77.0+3.22
90,0
CLIP
76.0+-2.7
52.5+33.0*
77.1+-4.4"
93.9-14.0*
As Table D shows, CLIP can achieve state-of-the-aa performance on the five benchmark datasets. Moreover, CLIP consistent across all datasets, while all other competitors have least weak
7

---

Under review as a conference paper at ICLR 2020
performance. This is good indicator of the robustness of the method to multiple classification tasks and dataset types. Finally, the addition of colors does not improve the accuracy for these graph classification tasks, except the MUTAG dataset. This may come from the small dataset sizes (leading to high variances) or an inherent difficulty of these classification tasks, and contrasts with the clear improvements of the method for property testing (see Section (.2)) More details the performance of CLIP w.r.t. the number of colors k are available in Appendix
Remark 2. In three out of five datasets, none of the recent tfate-of-the-ar algorithms have statistically significantly better results than older methods (c.g. WL). We argue that, considering the high variances of all classification algorithms on classical graph datasets, graph property testing may be better suited to measure the expressiveness of graph representation learning algorithms in practice.
6.2 GRAPH PROPERTY TESTING
We now investigate the ability of CLIP identify structural graph properties, task which was previ- ously used to evaluate the expressivity of graph kernels and on which the Weisfeiler-L subtree kernel has been shown to fail for bounded-degree graphs (Kriege et al.] 2018 The performance of our algorithm is evaluated for the binary classification of four different structural properties: I) connectivity, 2) bipartiteness. 3) triangle-frreness. 4) circular skip links (Murphy et al., (209) (see Appendix E for precise definitions of these properties) against three competitors: a) GIN, arguably the most efficient MPNN variant yet published (Xu al., (019), Ring-GNN, a permutation invariant network that uses the ring of matrix addition and multiplication (Chen et al., 2019). c) RP-GIN, the Graph Isomorphism Network combined with Relational Pooling, as described by Murphy et al. (2019), which is able to distinguish certain cases of non-isononn non-isomorphie regular graphs. We provide all experimental details in Appendix E
Table 2: Classification accuracies of the synthetic datasets. k-RP-GIN refers to a relational pooling averaged over k random permutations. We report Ring-GNN results from Chen et al. (2019).
Property
Connectivity mean +'2 std
Bipartiteness mean + std
Triangle-freeness mean + std
Circular skip links
mean std
max
min
GIN
55.2 + 4.4
53.1 +:4.7
50.7++6.1
10.0 0.0
10.0
10.0
Ring-GNN
(?) + 15.7
80.0
10.0
1-RP-GIN
66.1155.
66.0155.1
63.0+3.6
20.0 7.0
28.6
10.0
16-RP-GIN
83.347.9
64.9114.1
65.7+3.3
37.6 + 12.9
53.3
10.0
O-CLIP
56.5 + 4.0
55.4 + 5.7
59.6 + 3.8
10.0 + 0.0
10.0
10.0
1-CLIP
73.3 2.2
63.3 11.9
63.5 47.3
61.9 111.9
80.7
36.7
16-CLIP
99.7 + 0.5
99.2 + 0.9
94.2-13.4
90.8 + 6.8
98.7
76.0
Table
shows that CLIP is able to capture the structural information of connectivity, bipartiteness, freeness and circular skip links, while MPNN variants fail to identify these graph properties. Furthermore, we observe that CLIP outperforms RP-GIN, that was shown provide very expressive representations for regular graphs (Murphy et al. 2019), even with a high number of permutations (the equivalent of colors in their method is k 16). Moreover, both for k-RP-GIN and k-CLIP, the increase of permutations and colorings respectively lead to higher accuracies. In particular, CLIP can capture almost perfectly the different graph properties with as little as k 16 colorings.
CONCLUSION
In this paper, we showed that a simple coloring scheme can improve the expressive power of MPNNs. Using such a coloring scheme, we extended MPNNs create CLIP, the first universal graph representation. Universality was proven using the novel concept of separable neural networks, and our experiments showed that CLIP is state-of-the-art on both graph classification datasets and property testing tasks. The coloring scheme is especially well suited to hard classification tasks that require complex structural information to learn. The framework is general and simple enough to extend to other data structures such as directed, weighted labeled graphs. Future work includes more detailed and quantitative approximation results depending on the parameters of the architecture such the number of colors kt or number of hops of the iterative neighborhood aggregation.
8

---

Under review as a conference paper at ICLR 2020
REFERENCES
Atwood, J. and Towsley, D. (2016). Diffusion-comvolutionn neural networks. In Advances in Neural Information Processing Systems.
Babai, L. (2016). Graph isomorphism in quasipolynomial time. In Proceedings of the the forty- anmual ACM symposium Theory of Computing, pages 684-697. ACM.
Bartlett, P., Helmbold, D., and Long, P. (2018). Gradient descent with identity initialization efficiently learns positive definite linear transformations. In International Conference on Machine Learning, pages 520-529.
Baum, E. B. and Haussler, D. (1989). What size net gives valid generalization? In Advances in neural information processing systems, pages 81-90.
Bengio, Y., Courville, A., and Vincent, P. (2013). Representation learning: A review and new perspectives. IEEE transactions on pattern analysis and machine intelligence, 7788)1178--1888
Bodlaender, H. (1990). Polynomial algorithms for graph isomorphism and chromatic index on partial k-trees. Journal of Algorithms, 11(4):6316643
Bourbaki, N. (1998). General Topology: Chapters 1-4. Number vol. 4 in Addison-Wesler series in mathematics. Springer.
Bruna, J., Zaremba, W., Szlam, A., and Lecun, Y. (2014). Spectral networks and locally connected networks graphs. ICLR.
Chen, Z., Villar, S., Chen, L., and Bruna, (2019). On the equivalence between graph isomorphism testing and function approximation with gnns. NewrIPS 2019, abs/ abs/1905, (905,125600
Cybenko, G. (1989). Approximation by superpositions of a sigmoidal function. Mathematics of control, signals and systems, 244)3303-314
Defferrard, M., Bresson, X., and Vandergheynst, P. (2016). Convolutional neural networks on graphs with fast localized spectral filtering. In Advances in Neural Information Processing Systems, pages 3844-3852.
Duvenaud, D. K., Maclaurin, D., Iparraguirre, J., Bombarell, R., Hirzel, T., Aspuru-Guzik, A., and Adams, R. P. (2015). Convolutional networks graphs for learning molecular fingerprints. In Advances in neural information processing systems, pages 2224-2232.
Erdös, P. and Rényi, A. (1959). On random graphs i. Publicationes Mathematicae Debrecen, 6:290.
Frasconi, P., Gori, M., and Sperduti, A. (1998). A general framework for adaptive processing of data structures. IEEE transactions on Neural Networks, 95):766-7786
Geman, S., Bienenstock, E., and Doursat, R. (1992). Neural networks and the bias/variance dilemma.
Neural computation, 4(1):1-58.
Gilmer, J., Schoenholz, S. S., Riley, P. F.,. Vinyals, O., and Dahl, G. E. (2017). Neural message passing for quantum chemistry. ICML.
Gori, M., Monfardini, G., and Scarselli, F. (2005). A new model for learning in graph domains. In Neural Networks, 2005. IJCNN'05. Proceedings. 2005 IEEE International Joint Conference on, volume 2, pages 729-734. IEEE.
Grover, A. and Leskovec, J. (2016). node2vec: Scalable feature learning for networks. In Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining. pages 855-864 ACM.
Guttenberg, N., Virgo, N., Witkowski, O., Aoki, H., and Kanai, R. (2016). Permutation-cquivariaal neural networks applied to dynamics prediction. arXiv preprint arXiv:1612.04530.
Hamilton, W., Ying, Z. and Leskovec, J. (2017). Inductive representation learning on large graphs. In Advances in Neural Information Processing Systems, pages 1024-1033.

---

Under review as a conference paper at ICLR 2020
Henaff, M., Bruna, J., and LeCun, Y. (2015). Deep convolutional networks graph-structured data. arXiv preprint arXiv: 15XX::1500..0663.
Horikk, K. (1991). Approximation capabilities of multilayer feedforward networks. Neural networks, 4(2):251-257.
Hornik, K., Stinchcombe, M., and White, H. (1989). Multilayer feedforward networks are universal approximators. Neural networks, 255):35--366.
Ivanov, S. and Burnaev, E. (2018). Anonymous walk embeddings. ICML.
Kipf, T. N. and Welling, M. (2017). Semi-supervised classification with graph convolutional networks. ICLR.
Kriege, N. M., Morris, C.,, Rey, A., and Sohler, C. (2018). A property testing framework for the theoretical expressivity of graph kernels. In Proceedings of the Twenty-Seventh International Joint Conference Artificial Intelligence, IJCAI-18, pages 2348 2354. International Joint Conferences on Artificial Intelligence Organization.
Krizhevsky, A., Sutskever, I., and Hinton, G. E. (2012). Imagenet classification with deep convolu- tional neural networks. In Advances in Neural Information Processing Systems, pages 1097-1105.
Lei, T., Jin, W., Barzilay, R., and Jaakkola, T. (2017). Deriving neural architectures from sequence and graph kernels. ICML.
Luks, E. M. (1982). Isomorphism of graphs of bounded valence can be tested in polynomial time. Journal of Computer and System Sciences, 25(1):42 65.
Maron, H., Ben-Hamu, H., Serviansky, H., and Lipman, Y. (2019a). Provably powerful graph networks. NeurlPS.
Maron, H., Ben-Hamu, H., Shamir, N., and Lipman, Y. (2019b). Invariant and equivariant graph networks. In International Conference on Learning Representations.
Maron, H., Fetaya, E., Segol, N., and Lipman, Y. (2019c). On the universality of invariant networks. (CMI.2019)
McKay, B. D. (1981). Practical graph isomorphism. Congressus Numerantium, 30:45-87.
Mnih, V., Kavukcuoglu, K., Silver, D., Rusu, A. A., Veness, J., Bellemare, M. G., Graves, A., Riedmiller, M., Fidjeland, A. K., Ostrovski, G., Petersen, S., Beattic, C., Sadik, A., Antonoglou, I,, King, H., Kumaran, D., Wierstra, D., Legg. S., and Hassabis, D. (2015). Human-level control through deep reinforcement learning. Nature, 518(7540):529-533
Murphy, R., Srinivasan, B., Rao, V., and Ribeiro, B. (2019). Relational pooling for graph represen- tations. In Chaudhuri, K. and Salakhutdinov, R., editors, Proceedings of the 36th International Conference Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages Long Beach, California, USA. PMLR.
Niepert, M., Ahmed, M., and Kutzkov, K. (2016). Learning convolutional neural networks for graphs. In International conference on machine learning.
Perozzi, B., AI-Rfou, R., and Skiena, S. (2014). Deepwalk: Online learning of social representations. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 701-710. ACM.
Pinkus, A. (1999), Approximation theory of the mlp model neural networks. Acta numerica. 8:143-195.
Qi. C. R., Su, H., Mo, K., and Guibas, L. J. (2017). Pointnet: Deep learning on point sets for 3d classification and segmentation. CVPR.
Rudin, W. (1987). Real and Complex Analysis, 3rd Ed. McGraw-Hill, Inc., New York, NY, USA.
10

---

Under review as a conference paper at ICLR 2020
Saxe, A. M., McClelland, J. L., and Ganguli, S. (2014). Exact solutions to the nonlinear dynamics of learning in deep linear neural networks. ICLR.
Scarselli, F,, Gori, M., Tsoi, A. C., Hagenbuchner, M., and Monfardini, G. (2009). The graph neural network model. IEEE Transactions on Neural Networks, 20(1):61-80.
Shervashidze, N., Schweitzer, P., Leeuwen, E. v., Mehlhorn, K., and Borgwardt, K. M. (2011). Weisfeiler-lhmman graph kernels. Journal of Machine Learning Research.
Sperduti, A. and Starita, A. (1997). Supervised neural networks for the classification of structures. IEEE Transactions on Neural Networks, (3):714-733)
Szegedy, C., Vanhoucke, V., loffe, S., Shlens, J., and Wojna, Z. (2016). Rethinking the inception architecture for computer vision. In Proceedings of the IEEE conference computer vision and pattern recognition, pages 28 18182282..
Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, N., Kaiser, L., and Polosukhin, I. (2017). Attention all you need. In Advances Neural Information Processing Systems, pages 5998-6008. Curran Associates, Inc.
Velickovic, P., Cucurull, G., Casanova, A., Romero, A., Lio, P., and Bengio, Y. (2018). Graph attention networks. ICLR.
Verma, S. and Zhang, Z.-L. (2019). Graph capsule convolutional neural networks. ICLR.
Weisfeiler, B. and Lehman, A. (1968). A reduction of a graph to a canonical form and an algebra arising during this reduction. Yauchno-Technncchesayyy Informatsia, 2(9):12-16.
Xu, K., Hu, W., Leskovec, J., and Jegelka, S. (2019). How powerful are graph neural networks? ICLR.
Ying. R., You, J., Morris, C., Ren, X., Hamilton, W. L.,, and Leskovec, J. (2018). Hierarchical graph representation learning with differentiable pooling. In Advances in Neural Information Processing Systems, pages 4805-4815.
Zaheer, M., Kottur, S., Ravanbakhsh, S., Póezos, B., Salakhutdinov, R., and Smola, A. (2017). Deep sets. In Advances in Neural Information Processing Systems.
Zhang. M., Cui, Z., Neumann, M., and Chen, Y. (2018). An end-to-end deep learning architecture for graph classification, In Proceedings of AAAI Conference on Artificial Inteligence.

---

Under review as a conference paper at ICLR 2020
A PROOFS OF THE UNIVERSALITY OF SEPARABLE NEURAL NETWORKS
Proof of Theorem 2
The proof relies on the Stone- weee-seeissssss theorem we recall below. We refer to Theorem 7.32) for a detailed proof of the following classical theorem.
Rudin 1987.
Theorem 5 (Stone-Weiersterr Weierstrass). Let A be an algebra of real functions on compact Hausdorff set K. If A separates points of K and contains a non-zero constant function, then A is uniformly dense in C K, R.).
verify that under the assumptions of Theorem the Stone- Weierstrass theorem applies. this setting, we first prove the theorem for and use induction for the general case.
Let K C X' be a compact subset
X. We will denote
Ao = ab o PE 2 1 s.t. vb E C(R. R). E 8),
and will proceed in two steps: we first show that Ao uniformly dense in CK,R). then that AA is dense in Ao. hence proving Theorem 2
Lemma 1, Au is a subalgebra of R).
Proof. The subset Ag contains zero and all constants. Let f, E Ao so that
f(z) b pp((x),
g(z) v o (x(x),
with wy Rdd + R and v. Rd + R. Consider &b Rdy+d, + I such that sba b) (b((a) + (b). We define (tx) = (50 (x)) E Rdy+d and by assumption E 8. We have
(f + (x) = + o p(r)
so that f+ E Ao and we conclude that Ao is vectorial subspace of C(K, R). We proceed similarly for the product order finish the proof of the lemma.
Because 31 separates the points of X' by assumption, Ag also separates the points of X. Indeed, let A two distinct points of X so that 3ʃ E such that f(x) + fly). There exists E C(R4, R)) such that (x)))) * g(f (f()). From Theorem 5 we deduce that Ag is uniformly dense in C(K, R) for all compact subsets K X.
Finally we state that:
Lemma 2. For any compact subset K C X, A is uniformly dense in Ao
Proof. Let e > 0 and h tho o E Ao with f E 3 and tho E C(Rd R). Thanks to the continuity of f. the image K = f(K) is a compact of Rd By Theorem there exists an MLP 1 such that wollo,l S e. We have o E A and || o w l|l K e which concludes the proof.
This last lemma completes the proof in the case m = 1. For m 2 2 consider Ag = (wo o 3d 2 E 8) and proceed in similar manner than Lemma by decomposing S f 1 s.t. vh E C(Ré, IR"",, sb C(Rd, Rem) as
(2(2)
(xx)=
ei (I)
and applying Lemma for each coefficient function uyy C(RA, R).
Proof of Proposition 7
Assume that there exists 2. X s.t. Vf E e1. f(x) = f(y) Then K
{x, y a compact subset of and let Φ E C(K, R) be such that ((x) = and σ(v) = Thus, for all 31, (ax.e(m.) [})(=) ʃ(=)]| 1/2 which contradicts universality (see Definition 1p.
12

---

Under review as a conference paper at ICLR 2020
B GROUP ACTION ON HAUSDORFF SPACES
In what follows, A' is always a topological set and G a group of transformations acting on X' The orbits of X under the action of G the sets Ga {g x G}. Moreover, we denote as X/G the quotient space of orbits, also defined by the equivalence relation: I ~ b 3g E G s.t. x = g y. As stated Section 5 graphs with node attributes can be defined using invariance by permutation of the labels. We prove here that the resulting spaces are Hausdorff.
Definition 4 (Group invariance). Let G group, function f X + y is G-invariant if
Vz E X. Ag E G.f(z) 2))
Lemma (Bourbaki 1998
$8.3).. Let X be Hausdorff space and R an equivalence relation of X. Then N/R is Hausdorff if and only if any two distinct equivalence classes in X are contained in disjoints saturated open subsets of X.
Thanks to this lemma we prove the following proposition.
Proposition 2. Let G finite group acting Hausdorff space X, then the orbit spuce X //G is Hausdorff.
Proof. Let Ga and Gy two distinct classes with disjoint open neighbourhood U and V. VB finiteness of G. the application æ X' X/G is open, hence the saturated sets Ú -- (m)) and == -=<][(<(V) are open. Suppose that there exists 2 E Ü n V, then π(2) E π (U) n (V) and we finally get that Gz C UNV = 0. Therefore Ü V empty and //G is Hausdorff by Lemma
Proposition 2 directly implies that the spaces Graph, and Neighborhood,, are HausdorfT.
C UNIVERSALITY OF THE NODE AGGREGATION SCHEME
We now provide more details the aggregation and combination scheme of CLIP, and show that simple application of Corollary | is sufficient to prove its universality for node neighborhoods. Each local aggregation step takes as input couple (x,, {zz }:eN;) where 2; E Fm the representation of node i. and {z, Jev, is the set of vector representations of the neighbors of node i. In the following, we show how to use Corollary to design universal representations for node neighborhoods.
Definition 5. The of node neighborhoods for m-dimennsiona node attributes is defined
Neighborhood,.. = Rm x
U RR /Pr) T.
(8)
where the set permutation matrices P, acting on Ru by P -- Pv.
The main difficulty to design universal neighborhood representations is that the node neighborhoods of Definition 55] are permutation invariant w.r.t. neighboring node attributes, and hence require permutation invariant representations. The graph neural network literature already contains several deep learning architectures for permutation invariant sets (Guttenberg et al., 2016) Qi et al.) [201]] Zaheer et al. 2017 Xu et al. 2019),, among which PointNet and DeepSet have the notable advantage of being provably universal for sets. Following Corollary L we compose separable permutation invariant network with an MLP that will aggregate both information from the node itself and its neighborhood. While final architecture similar to Deepset (Zaheer al. (017). this section emphasizes that the general universality theorems of Section 3 are easily applicable in many settings including permutation invariant networks. The permutation invariant representation used for the aggregation step of CLIP is as follows:
NODEACCCREGATION(1, S) = Σ p(u))
BES
where ab and are MLPs with continuous non polynolyloiall activation functions and vxxx, y) denotes the result of the MLP s applied the concatenation of and y.
13

---

Under review as a conference paper at ICLR 2020
Theorem 6. The set representation described in Eq. (9) is universal representation of Neighborhood,.
Proof. By construction, NODEAGGREGATION is a continuous and concatenable representation. Moreover, its final stage is MLP, and we thus only have to prove separability in order to use Corollary 1 and prove universality. Let (x', ( ) (x² S²) E Neighborhood, and suppose that separate æ² and x². Otherwise, S o 5
(a*, (t) 7 [a? (²). First, if x² & x² the final MIP and let us assume that S S² # 9 (otherwise S S * @ and the argument is identical). Since MLPs are universal representations of R", there exists an MLP ip such that, Vs S US.
( if S 552 [sp(5) Σ otherwise,
Taking (xx,)) y and 1/3 (S | we have
NODEAGGREGAATION(2 ,S') 2 2/3,
NODEAAGOREGATION ,5²) S 1/3,
which proves separability and, using Corollary | the universality of the representation.
D PROOF OF THE UNIVERSALITY OF CLIP
Proof of Theurem First all, as the activation functions of the MLPs are continuous, CLIP made of continuous and concatenable functions, and is thus also continuous and concatenable. Second, as the node aggregation step (denoted NODEAGGRENNTION below) is a universal set representation (see Appendix C). it is capable of approximating any continuous function. We will thus first replace this function by a continuous function o, and then show that the result still holds for MODEAGGREGATION:
by a simple density argument. Let G = (v²,At) and G = (v² A²) be two distinct graphs of respective sizes ni and n22 (up
permutation). If nd * n², then (xx) = x and ((x) = returns the number of nodes, and hence FG = -n o n² = IGa. Otherwise, let V {uf he[l),"',.EE(1. be the of node attributes of G and G2, c² be coloring of G'. (xx) = and be continuous function such that, Vo V and SVV.
(x, 11a= (t) [ c)
(10)
1=1
The existence of & E C(RT, R) assured by Urysohn's lemma (see e.g. Rudin 1987 lemma 2.1))). Then, ag counts the number matching neighborhoods for the best coloring, and we have IG n and Æg² I n - 1. Finally, taking < 1/2n² in the definition of universal representation leads to the desired result, then, using e-approximation of & NODEAGGREGATION!! we have Tign > n 1/2 zge.
Proof of Theurem 4 Consider continuous function v Graph + Rd and a compact K' C Graph,,. Let extend K' with K = K' x [0, 1] and define Ø Graph R with ø((v, A) = (vv A) for all E C(v, Since co-CLIP is universal there exists f E CLPL such that, for all ((v,c). A) K,
[lo((u,)), (((v,e), A)Il se,
(11)
hence
| 4) f((u, A)Il S
(12)
Moreover, observe that for any coloring c E C(o, A), x-CLLIP and 1-CLIP applied to ((1, c), A) returns the same result, as all node attributes are dissimilar (by definition of the colorings) and
C((u, c), A) = G. Finally, 1-CLIP applied to (u, A) is equivalent to applying 1-CLIP to ((v, C), A)
where C. is a random coloring in A(), and Eq. (2) thus implies that any random sample of 1-CLIP is within an & error of the target function v. As a result, its expectation is also within an error of the target function d/s which proves the universality of the expectation of 1-CLII.
n
14

---

Under review as a conference paper at ICLR 2020
E EXPERIMENTAL DETAILS
E
REAL-WORLD DATASETS
Table
summarizes the characteristics of all benchmark graph classification datasets used in Sec-
tion 6.1 We now provide complementary information these datasets.
Social Network Datasets (IMDBb, IMDBm): These datasets refer to collaborations between actors/actresses, where each graph is an ego-graph of every actor and the edges occur when the connected nodes/actors are playing in the same movie. The task is to classify the genre of the movie that the graph derives from. IMDBb is single-class classification dataset, while IMDBm is multi-class. For both social network datasets, we used one-hot encodings of node degrees as node attribute vectors.
Bio-informatics Datasets (MUTAG, PROTEINS, PTC): MUTAG consists of mutagenic aromatic and heteroaromatic nitrocompounds with 7 discrete labels. PROTEINS consists of nodes, which correspond to secondary structureelements and the edges occur when the connected nodes are neighbors in the anino-acidsequence in 3D space. It has discrete labels. PTC consists of chemical compounds that reports the carcinogenicity for male and female rats and has 19 discrete labels. For all bio-informatics datasets used the node labels node attribute vectors.
We follow the same experimental protocol as described in Xu et al. (2019), and thus report the results provided in this paper corresponding the accuracy of our six baselines in Table We optimized the CLIP hyperparameters by grid search according to 10-fold valsdvaadd accuracy means. We use 2-layer MLPs, an initial learning rate of 0.001 and decreased the learning rate by 0.5 every 50 epochs for all possible settings. For all datasets the hyperparameters we tested are: the number of hidden units within (32, 64), the number of colorings E {1, 4, 8), the number of MPNN layers within (1,3, 3, 5), the batch size within {32, 64), and the number of epochs, that means, we select single epoch with the best cross-valddation accuracy averaged over the 10 folds. Note that standard deviations are fairly high for all models due to the small size of these classic datasets.
Experimentation protocol:
Table 3: Characteristics of the benchmark graph classification datasets used in Section 6.1
Dataset
PTC
IMDBb
IMDBm
PROTEINS
MUTAG
# graphs
344
1000
1500
188
# classes
2
Avg # nodes
14.29
19.77
13.00
39.06
17.93
Avg degree
2.05
9.76
10.14
3.72
2.21
E.1.1 CLIP PERFORMANCES W.R.T. THE NUMBER OF COLORINGS k:
Table 4
summarizes the performances CLIP while increasing the number of colorings Overall a small increase in performances and reduction of the variances when & is increasing. Nevertheless we should not jump to any conclusions since none of the models are statistically significantly better than the others.
Table 4: Ablation study: classification accuracies of k-LIPP benchmark datasets w.r. k.
Dataset
PTC
IMDBb
IMDBm
PROTEINS
MUTAG
0-CLIP
65.914.0
75.412.0
52.5+2.6
77.013.2
90.015.11
1-CLIP
65.3++128
75.2+3399
52.2+:.0
75.1+
91.1=77.0
4-CLIP
65.9+15.7
75.8
51.81229
77.114.44
92.2-7.00
8-CLIP
67.917.1
75.743.8
52.5+3.0
76.8-L4.8
93.9-E4.1
16-CLIP
66.5+5.44
76.0+2.7
52.5=4.5
76.6+2.88
91.7++6.0
We note that on the IMDBb and PROTEINS datasets the difference between using or not a coloring scheme does not have big impact the performances. However, adding colors increases the
15

---

Under review as a conference paper at ICLR 2020
performances of the algorithm three out of five real world datasets. The property testing section (Section 6.2) shows empirically that the color scheme improves the expressiveness of CLIP.
E.2 GRAPH PROPERTY TESTING
In Section 6.2 we evaluate the expressive power of CLIP on benchmark synthetic datasets. Our goal is to show that CLIP is able to distinguish basic graph properties, where classical MPNN cannot. We considered a binary classification task and we constructed balanced synthetic dataset: for each of the examined graph properties. The 20-node graphs are generated using Frdös-Rényí model (Erdös) and Rényi 1959) (and its bipartite version for the bipartiteness) with different probabilities for edge creation. All nodes share the same (scalar) attribute. We thus have uninformative feature vectors.
In particular, we generated datasets for different classical tasks Kriege et al. (2018): 1) connectivity, 2) bipartiteness, 3) triangle-freeness, and 4) circular skip links (Murphy al. 2019). In the following, we present the generating protocol of the synthetic datasets and the experimentation setup we used for the experiments.
Synthetic datasets:
In every case of synthetic dataset we follow the same pattern: we generate a set of random graphs using vadös-Rééni model, which contain specific graph property and belong to the same class and by proper edge addition we remove this property, thus creating the second class of graphs. By this way, we assure that we do not change different structural characteristics other than the examined graph property.
Connectivity dataset: this dataset consists of 1000 (20-node) graphs with 500 positive samples and 500 negative ones. The positive samples correspond to disconnected graphs with two 10-node connected components selected among randomly generated graphs with an Erdös Frdös-Rényí model probability of 0.5. We constructed negative samples by adding to positive samples a random edge between the two connected components.
this dataset consists of 1000 (20-node) graphs with 500 positive samples and 500 negative ones. The positive samples correspond to bipartite graphs generated with an Erdös-Rényi (bipartite) model probability of p = 0.5. For the negative samples (non-bigg -ip-tiiaeee graphs) chose the positive samples and for each of them added edge between randomly selected nodes from the same partition, in order to form odd cycles]
Bipartiteness dataset:
Triangle-freeneet dataset: this dataset consists of 1000 (20-node) graphs with 500 positive samples and 500 negative ones. The positive samples correspond triangle-free graphs selected among randomly generated graphs with an Frdös-Rényi model probability of p = 0.1. We constructed negative samples by randomly adding edges to positive samples until it creates least one triangle.
Circular skip links: this dataset consists of 150 graphs of 41 nodes as described in (Murphy et al. 2019; Chen et al., 2019). The Circular Skip Links graphs are undirected regular graphs with node degree 4. We denote a Circular skip link graph by Gr. an undirected graph of n nodes, where (i.j) E holds if and only if j jl or k( mod n) This is a 10-class multiclass classification task whose objective is to classify each graph according to its isomorphism class.
We evaluate the different configurations of CLIP and its competitors GIN and RP-GIN based on their apper-paramtter.. For the architecture implementation of the GIN, we followed the best performing architecture, presented in Xu et al. (2019). In particular, we used the summation as the aggregation operator, MLPs as the combination level for the node embedding generation and the sum operator for the readout function along with its refined version of concatenated graph representations across all iterations/layers of GIN, as described in Xu et al. al.] (2019).
Experimentation protocol:
In all the tested configurations for CLIP and its competitors (GIN, RP-GIN) we fixed the number of layers of the MLPs and the learning rate: we chose 2-layer MLPs and we used the Adam optimizer with initial learning rate of 0.001 along with scheduler decaying the learning rate by 0.5 every 50 epochs. Concerning the other hyper-parameten we optimized: the number of hidden units within (16,32 32, 64) (except for the CSL task where we only use 16 hidden units to be fair w.r.t. RP-GIN
"The datasets are available upon request. Having an odd cycle in graph makes the graph non bipartite.
16

---

Under review as a conference paper at ICLR 2020
and Ring- GNNN benchmarks), the number of MPNN layers within 21, 5), the batch size within {32, 64), and ran the model over 400 epochs. Regarding the RP-GIN architecture (Murphy et al. 2019) optimized the one-hot encoding dimension of the first update within {5, 10, 15, 20, 25, 30 and the number of inference permutations within (1.5, 16). Regarding the CLIP algorithm, we 21,2,4, 4, 16). We then performed 10-fold cross validation with early stopping for the hyper-parameter parameter optimization and we reported the best 10-fold cross- validated mean accuracy with its associated standard deviation.
optimized the number of colorings
17


Reviews:
[{"review_id": "rylnm81RKr", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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": "\nThe paper presents an interesting work, called Colored Local Iterative Procedure (CLIP), to improve the expressive power of Message Passing Neural Networks (MPNNs). Considering the expressive power from the concept of universal representations, the authors introduced the concept of separability and combine the separable representation with MLP to achieve the universal representation for graphs. They then developed a coloring scheme to improve the MPNN, and obtained superior performance on benchmark graph classification datasets as well as in the graph property testing experiments. In general, I like the paper, but I have the following concerns:\n\nAlthough we can easily get the idea that universal representation is more expressive, however, I did feel a small conceptual gap between isomorphism test and universal representation. For example, in Section 4.2, when the authors talked about the fact that MPNN is not expressive to construct isomorphism tests for a k-regular graph, it is expected to have a more explicit explanation of how universal representations can solve this and how it is connected to isomorphism test. It seems that there is no such explanation in the paper. \n\nI am not very clear about how 1-CLIP gets the randomness. To my understanding, 1-CLIP uses one color, so the identical node attributes still have the same node attributes after coloring, and it is essentially equivalent to just concatenating extra node features to an MPNN? It also does not change the expressive power of MPNN.\n\nIntuitively k-CLIP should be better than p-CLIP if k>p, and it is also demonstrated in the graph property testing experiment. However, why do the authors use k as a hyperparameter to select the best results in classical benchmark datasets? Does it say sometimes the smaller k can also get a better result? Why not also just show the results of 1-CLIP and 16-CLIP?\n\nIt seems $k$ has different meanings in different places of the paper. For example, $k$ in $C_k$ is different the $k$ in Eq. (4). Maybe it is better to use a different variable to avoid confusion.\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory."}, "extra_text": {}}, {"review_id": "SJxoqd7TtB", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": null, "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": "\nThis paper proposes a coloring scheme that can increase the expressive power of GCNs. Based on this coloring scheme, a colored local iterative procedure is built. Experimental studies are performed and demonstrate the effectiveness of the methods.\n\n1. A major concern for this method is the permutation invariant in coloring scheme. In this work, nodes in a group is colored randomly. This means the graph will change with different coloring patterns. In section 5.3, inf-CLIP is claimed to be permutation invariant. However, this property can not be guaranteed for a normal k.\n\n2. The experimental studies are weak. There should be some ablation studies to evaluate the effectiveness of the coloring scheme. In section 7.2, the ablation studies are performed on synthetic datasets. Why not use real data?\n\n3. This paper exceeds 8 pages which means higher requirements are needed. The novelty of this paper is incremental and not technically sound.\n\nSuggestions:\n\nFigure out ways to ensure permutation invariant would be a great plus.", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "Bye8QHt0tH", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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 proposes an extension of MPNN which leverages the random color augmentation to improve the representation power of MPNN. Authors also prove that two variants of the proposed method have universal representation power (one is exact and the other holds in expectation) from the separability perspective. Experiments on some small graph benchmark datasets and structural property tests are reported. \n\nOverall, the paper seems to make a good contribution on advocating a new perspective of representation power of GNNs, i.e., separability, and proposes a variant to empirically improve representation power. However, I do have quite a few concerns listed as below which impedes my understanding and prevents me from giving a high score. \n\nPros:\n\n1, The separability perspective of representation power seems novel.\n\n2, The coloring based method is interesting and simple to implement.\n\n3, The graph property test experiments are good testbeds to verify the representation power of various GNNs.\n\nCons & Questions:\n\n1, The overall paper seems lack of focus in a sense that section 3 and 4 discuss too much on general universality whereas the main contribution, i.e., section 5 is not explained clearly.\n\n2, If I understood correctly, the max operator in Eq. (5) only aggregates the “colored” representation within the group of nodes which shared the same attributes. How do you further get the representation of the whole graph? When k=1, the max operator in Eq. (5) becomes identity, wouldn’t 1-CLIP method be equivalent to augmenting random color as extra node features to GNNs? \n\n3, The whole section 6 is just a very common GNN aggregation operator, I do not understand why authors claim it as “a novel universal neighborhood representation”. Also, the notation in Eq. (8) is not rigorous, what do you exactly mean by psi(x, y) as an MLP? Do you mean concatenating x and y as an input to MLP?\n\n4, The experimental results on the benchmark datasets are less impressive as the mean performances are close to the WL-test results and the variances are considerably large. Moreover, why is the MPNN baseline missing, not mentioning other state-of-the-art GNNs? Same GNN baselines are missing in the structural property tests as well.\n\n5, A closely relevant reference [1] is missing. The equivalence between universal approximation and graph isomorphism testing is studied in [1]. I think it is necessary to discuss the relationship. A comparison with [1] both theoretically and empirically would be make the paper more convincing.\n\n6, Since k-CLIP with some k such that 1 < k < infinity achieves the best performance in the experiments, does k-CLIP still have universal representation theoretically? \n\n7, Many notations are introduced without clear explanation. For example, what does lower-case c stand for? If it stands for the color per node, why does permutation appears in the definition of Eq. (4)? If I understood correctly, Eq. (4) is the set of all colorings which does not depend on permutation anyway. What does S refer to in Eq. (8)?\n\n8, What are variants of CLIP reported in Table 1? Are they 1-CLIP? Also, the multiple bold numbers in Table 1 are quite confusing. \n\n9, Wouldn't Eq. (6) indicate factorial growth rather than the claimed exponential one?\n\nTypos: CDNN in table 1 should be DCNN\n\n[1] Chen, Z., Villar, S., Chen, L. and Bruna, J., 2019. On the equivalence between graph isomorphism testing and function approximation with GNNs. arXiv preprint arXiv:1905.12560.", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper presents an extension of MPNN which leverages the random color augmentation to improve the representation power of MPNN. The experimental results shows the effectiveness of colorization. A majority of the reviewers were particularly concerned about lacking permutation invariance in the approach as well as the large variance issue in practice, and their opinion stays the same after the rebuttal. The reviewers unanimously expressed their concerns on the large variance issue during the discussion period. Overall, the reviewers believe that the authors has not addressed their concerns sufficiently.
Decision: Reject