Coloring Graph Neural Networks for Node Disambiguation

1 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].

Despite a large literature and state-of-the-art performance on benchmark graph classification datasets, graph neural networks yet lack a similar theoretical foundation [Xu et al., 2019]. Universality for these architectures is either hinted at via equivalence with approximate graph isomorphism tests (kWL tests in [Xu et al., 2019; Maron et al., 2019a]), or 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 a 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.

1 A longer version of the paper with detailed proofs of propositions and theorems is available at https://arxiv.org/pdf/1912.06058.pdf.

The rest of the paper is organized as follows: Section 2 gives an overview of the graph representation literature and related works. Section 3 provides a precise definition for universal representations, as well as a generic method to design them using separable neural networks. In Section 4, we show that most state-of-the-art representations are not sufficiently expressive to be universal. Then, using the analysis of Section 3, Section 5 provides CLIP, a provably universal extension of MPNNs. Finally, Section 6 shows that CLIP achieves stateof-the-art accuracies on benchmark graph classification taks, as well as outperforming its competitors on graph property testing problems.

2 RelatedWorks

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; Henaff 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 a local iterative process. This category contains most state-of-the-art graph representation methods such as [Duvenaud et al., 2015; Grover and Leskovec, 2016; Lei et al., 2017; Ying et al., 2018; Verma and Zhang, 2019], DeepWalk [Perozzi et al., 2014], graph attention networks [Velickovic et al., 2018], graphSAGE [Hamilton et al., 2017] or GIN [Xu et al., 2019].

Recently, [Xu et al., 2019] showed that MPNNs were, at most, as expressive as the Weisfeiler-Lehman (WL) test for graph isomorphism [Weisfeiler 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., 2019a; Maron et al., 2019b; Maron et al., 2019c; 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., 2019c] 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]: a 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, Y be two topological spaces, then F(X, Y) (resp. C(X, Y)) denotes the space of all functions (resp. continuous functions) from X to Y. Moreover, for any group G acting on a set X , X/G denotes the set of orbits of X under the action of G. Finally, ‖ · ‖ is a norm on Rd , and Pn is the set of all permutation matrices of size n. In what follows, we 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 a machine learning task (e.g. classification, regression or clustering). In what follows, we denote as vector representation of X a function f : X → Rd that maps each element x ∈ X to a d-dimensional vector f(x) ∈ Rd . A standard setting for supervised representation learning is to define a class of vector representations Fd ⊂ 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 ∈ Fd that leads to a good accuracy on the learning task). In order to present more general results, we will consider neural network architectures that can output vectors of any size, i.e. F ⊂ ∪d∈N∗F(X , Rd ), and will denote Fd = F∩F(X , Rd ) the set of d-dimensional vector representations of F. A natural characteristic to ask from the class F is to be generic enough to approximate any vector representation, a notion that we will denote as universal representation [Hornik et al., 1989].

Definition 1. A class of vector representations F ⊂ ∪d∈N∗F(X,Rd ) is called a universal representation of X if for any compact subset K ⊂ X and d ∈ N∗ , F is uniformly dense in C(K, Rd ).

In other words, F is a universal representation of a normed space X if and only if, for any continuous function φ : X → Rd , any compact K ⊂ X and any ε > 0, there exists f ∈ F such that

One of the most fundamental theorems of neural network theory states that one hidden layer MLPs are universal representations of the m-dimensional vector space Rm.

Theorem 1 ([Pinkus, 1999]). Let ϕ : R → R be a continuous non polynomial activation function. For any compact K ⊂ Rm and d ∈ N∗ , two layers neural networks with activation ϕ are uniformly dense in the set C(K, Rd ).

However, for graphs and structured objects, universal representations are 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 a key topological property, separability, may lead to 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 to separate each pair of dissimilar elements of X .

Definition 2 (Separability). A set of functions F ⊂ F(X , Y) is said to separate points of X if for every pair of distinct points x and y, there exists f ∈ F such that f(x) ̸= f(y).

For a class of vector representations F ⊂ ∪d∈N∗F(X , Rd ), we will say that F is separable if its 1-dimensional representations F1 separates points of X. Separability is rather weak, as we only require the existence of different outputs for every pair of inputs. Unsurprisingly, we now show that it is a necessary condition for universality.

Proposition 1. Let F be a universal representation of X, then F1 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 be composed with a universal representation of Rd (such as MLPs) to become universal.

Theorem 2. For all d ≥ 0, let Md be a universal approximation of Rd . Let F be a class of vector representations of X such that:

• (i) Continuity: every f ∈ F is continuous,
• (ii) Stability by concatenation: for all f, g ∈ F, x ↦→ (f(x), g(x)) ∈ F,
• (iii) Separability: F1 separates points of X.

Then {ψ ◦ f : ∃d ≥ 1 s.t. ψ ∈ Md, f ∈ F} is a universal representation of X .

Stability by concatenation is verified by most neural networks architectures, as illustrated for MLPs in Figure 1. The proof of Theorem 2 relies on the Stone-Weierstrass theorem (see e.g. [Rudin, 1987]) whose assumptions are continuity, separability, and the fact that the class of functions is an algebra. Fortunately, composing a separable and concatenable representation with a universal representation automatically leads to an algebra, and thus the applicability of the StoneWeierstrass theorem and the desired result. Since MLPs are universal representations of Rd , Theorem 2 implies a convenient way to design universal representations of more complex object spaces: create a separable representation and compose it with a simple MLP (see Figure 2).

Corollary 1. A continuous, concatenable and separable representation of X composed with an MLP is 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 1 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 Graphs with Node Attributes

Consider a dataset of n interacting objects (e.g. users of a social network) in which each object i ∈ J1, nK has a vector attribute vi ∈ Rm and is a node in an undirected graph G with adjacency matrix A ∈ Rn×n .

Definition 3. The space of graphs of size n with mdimensional node attributes is the quotient space

where A is the adjacency matrix of the graph, v contains the m-dimensional representation of each node in the graph and the set of permutations matrices Pn is acting on (v, A) by

Moreover, we limit ourselves to graphs of maximum size nmax, where nmax is a 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 a finite number of samples. We thus define Graphm = ⋃n≤nmax Graphm,n.

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 et al., 2019], a message passing neural network (MPNN) [Gilmer et al., 2017] is made of three consecutive phases that will create intermediate node representations xi,t for each node i ∈ J1, nK and a final graph representation xG as described by the following procedure: 1) Initialization: All node representations are initialized with their node attributes xi,0 = vi. 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: xG = READOUT({xi,T }i∈J1,nK), where READOUT is permutation invariant.

Unfortunately, while MPNNs are very efficient in practice and proven to be as expressive as the Weisfeiler-Lehman algorithm [Weisfeiler and Lehman, 1968; Xu et al., 2019], they are not sufficiently expressive to construct isomorphism tests or separate all graphs (for example, consider k-regular graphs without node attributes, for which a small calculation shows that any MPNN representation will only depend on the number of nodes and degree k [Xu et al., 2019]). As a direct application of Proposition 1, MPNNs are thus not expressive enough to create universal representations.

5 ExtendingMPNNs 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 more complex structural graph characteristics than traditional MPNNs. This is proved theoretically through a universal approximation theorem in Section 5.3 and experimentally in Section 6. CLIP is based on three consecutive steps: 1) graphs are colored with several different colorings, 2) a neighborhood aggregation scheme provides a vector representation for each colored graph, 3) all vector representations are combined to provide a final output vector. We now provide more information on the coloring scheme.

5.1 Colors to Differentiate Nodes

In order to distinguish non-isomorphic graphs, our approach consists in coloring nodes of the graph with identical attributes.

This idea is inspired by classical graph isomorphism algorithms that use colors to distinguish nodes [McKay, 1981], and may be viewed as an extension of one-hot encodings used for graphs without node attributes [Xu et al., 2019].

For any k ∈ N, let Ck be a finite set of k colors. These colors may be represented as one-hot encodings (Ck is the natural basis of Rk ) or more generally any finite set of k elements. At initialization, we first partition the nodes into groups of identical attributes V1, ..., VK ⊂ J1, nK. Then, for a subset Vk of size |Vk|, we give to each of its nodes a distinct color from Ck (hence a subset of size |Vk|). For example, Figure 3 shows two colorings of the same graph, which is decomposed in three groups V1, V2 and V3 containing nodes with attributes a, b and c respectively. Since V1 contains only two nodes, a 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 C(v, A) of a graph G = (v, A) are defined as

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 is achieved by modifying the initialization and readout phases of MPNNs as follows.

1. Colored initialization: We first select a set Ck ⊆ C(v, A) of k distinct colorings uniformly at random (see Eq. (4)). Then, for each coloring c ∈ Ck, node representations are initialized with their node attributes concatenated with their color: xci,0 = (vi, ci).
2. Aggregation and combination: This step is performed for all colorings c ∈ Ck using a universal set representation as the aggregation function: xci,t+1 = ψ(t) (xci,t , ∑j∈Ni ϕ(t) (xcj,t )), where ψ and ϕ are MLPs with continuous non-polynomial activation functions and ψ(x, 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 a direct application of Corollary 1 proves the universality of our architecture.
3. Colored readout: This step performs a maximum over all possible colorings in order to obtain a final coloringindependent graph representation. In order to keep the stability by concatenation, the maximum is taken coefficient-

wise

where ψ is an MLP with continuous non polynomial activation functions.

We treat k as a hyper-parameter of the algorithm and call k-CLIP (resp. ∞-CLIP) the algorithm using k 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 as soon as k < |C(v, A)|, and the number of colorings k will impact the variance of the representation. However, ∞-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∞-CLIP algorithm with one local iteration (T = 1) is a universal representation of the space Graphm of graphs with node attributes.

The proof of Theorem 3 relies on showing that ∞-CLIP is separable and applying Corollary 1. This is 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, ci) are dissimilar. Similarly to the case of MLPs, 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 in a complex and non-trivial way. However, as for MLPs, one may expect poor generalization capabilities for CLIP with only one 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, ∞-CLIP 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, a similar universality theorem still holds even for k = 1.

Theorem 4. The 1-CLIP algorithm with one local iteration (T = 1) is a random representation whose expectation is a universal representation of the space Graphm of graphs with node attributes.

The proof of Theorem 4 relies on using ∞-CLIP on the augmented node attributes v′i = (vi, ci). 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 ε-approximation of the target function.

Remark 1. Note that the variance of the representation may be reduced by averaging over multiple samples. Moreover, the proof of Theorem 4 shows that the variance can be reduced to 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 = |Ck|. Hence the complexity of the algorithm is in O(kET).

Note that the number of all possible colorings for a given graph depends exponentially in the size of the groups V1, ..., VK,

and thus ∞-CLIP is practical only when most node attributes are dissimilar. This worst case exponential dependency in the number of nodes can hardly be avoided for universal representations. Indeed, a 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 quasi-polynomial in general [Babai, 2016]. As a result, creating a universal graph representation with polynomial complexity for all possible graphs and functions to approximate is highly unlikely, as it would also induce a graph isomorphism test of polynomial complexity and thus solve a very hard and long standing open problem of theoretical computer science.

6 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-art methods in 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 et al., 2019]: 10-fold cross validation with grid search hyperparameter optimization.

6.1 Classical Benchmark Datasets

We performed experiments on five common benchmark datasets extracted from standard social networks (IMDBb and IMDBm) and bio-informatics databases (MUTAG, PROTEINS and PTC). 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 et al., 2019], and perform single-label multi-class classification on all datasets. We compared CLIP with six stateof-the-art baseline algorithms: 1) WL: Weisfeiler-Lehman subtree kernel [Shervashidze et al., 2011], 2) AWL: Anonymous Walk Embeddings [Ivanov and Burnaev, 2018], 3) DCNN: Diffusion-convolutional neural networks [Atwood and Towsley, 2016], 4) PS: PATCHY-SAN [Niepert et al., 2016], 5) DGCNN: Deep Graph CNN [Zhang et al., 2018] and 6) GIN: Graph Isomorphism Network [Xu et al., 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., 2019] was used, we present their reported results on Table 1.

As Table 1 shows, CLIP can achieve state-of-the-art performance on the five benchmark datasets. Moreover, CLIP is consistent across all datasets, while all other competitors have at least one weak performance. This is a 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 on 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 6.2).

Remark 2. In three out of five datasets, none of the recent state-of-the-art algorithms have statistically significantly better results than older methods (e.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 to identify structural graph properties, a task which was previously used to evaluate the expressivity of graph kernels and on which the WeisfeilerLehman subtree kernel has been shown to fail for boundeddegree graphs [Kriege et al., 2018]. The performance of our algorithm is evaluated for the binary classification of four different structural properties: 1) connectivity, 2) bipartiteness, 3) triangle-freeness, 4) circular skip links [Murphy et al., 2019] against three competitors: a) GIN, arguably the most efficient MPNN variant yet published [Xu et al., 2019], b) 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-isomorphic regular graphs.

The Connectivity, Bipartiteness and Triangle-Freeness datasets consist each of 1000 (20-node) graphs with 500 positive samples and 500 negative ones. Regarding the connectivity, the positive samples correspond to disconnected graphs with two 10-node connected components selected among randomly generated graphs and then we constructed negative samples by adding to positive samples a random edge between the two connected components. Regarding the bipartiteness, the positive samples correspond to bipartite graphs, while for the negative samples (non-bipartite graphs) we chose the positive samples and for each of them we added an edge between randomly selected nodes from the same partition, in order to form odd cycles. 2 . Regarding the triangle-freeness, the positive samples correspond to triangle-free graphs selected among randomly generated graphs and then we constructed negative samples by randomly adding new edges to positive samples until it creates at least one triangle. In all three datasets, we generated random graphs using the Erdös-Rényi model with probabilities p = 0.5, 0.5, 0.1 respectively. Lastly, the Circular skip links 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 Gn,k an undirected graph of n nodes, where (i, j) ∈ E holds if and only if |i - j| ≡ 1 or k( mod n) This is a 10-class multiclass classification task whose objective is to classify each graph according to its isomorphism class.

2 Having an odd cycle in a graph makes the graph non bipartite.

Table 2 shows that CLIP is able to capture the structural information of connectivity, bipartiteness, triangle-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 to 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 set to 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.

7 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 to 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 or labeled graphs. Future work includes more detailed and quantitative approximation results depending on the parameters of the architecture such as the number of colors k, or number of hops of the iterative neighborhood aggregation.