Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 3: Weak Reject
review_content: 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.
review_title: Official Blind Review #1

final_score: rating: 6: Weak Accept
review_content: 
The 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:

Although 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. 

I 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.

Intuitively 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?

It 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.

review_title: Official Blind Review #3

final_score: rating: 1: Reject
review_content: 
This 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.

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

2. 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?

3. This paper exceeds 8 pages which means higher requirements are needed. The novelty of this paper is incremental and not technically sound.

Suggestions:

Figure out ways to ensure permutation invariant would be a great plus.
review_title: Official Blind Review #2

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