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.
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. 
Overall, 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. 
Pros:
1, The separability perspective of representation power seems novel.
2, The coloring based method is interesting and simple to implement.
3, The graph property test experiments are good testbeds to verify the representation power of various GNNs.
Cons & Questions:
1, 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.
2, 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? 
3, 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?
4, 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.
5, 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.
6, 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? 
7, 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)?
8, What are variants of CLIP reported in Table 1? Are they 1-CLIP? Also, the multiple bold numbers in Table 1 are quite confusing. 
9, Wouldn't Eq. (6) indicate factorial growth rather than the claimed exponential one?
Typos: CDNN in table 1 should be DCNN
[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.