Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 8: Accept
review_content: This paper studies impossibility results of GNN in the worst-case sense. In particular, it reduces GNN to a distributed computing model CONGEST and adapt the impossibility result from distributed computing to GNNs. The impossibility results show that for certain problems, e.g., subgraph detection, there exists a graph such that GNN can not solve the problem unless the product of a GNN’s depth and width exceeds (a function of) the graph size.

I am not an expert of distributed computing and I did not check all the proofs thoroughly. But I do think this paper provides a solid contribution to broaden the community’s understanding about what the limitations of GNNs are. Overall, I tend to accept it and would like to increase the score based on authors’ feedback.

Pros:

1, I like the contribution of the paper which tries to build connections between GNNs and distributed computing models. From the perspective of computation, GNNs and distributed algorithms do share a lot of similarities. Therefore, some algorithm design choices in distributed computing would shed some light on designing novel GNNs. This may open a new direction for the community.

2, The depth and width dependency results are novel in the context of GNNs.

Cons & Questions & Suggestions:

1, Since these impossibility results for a certain subclass of GNNs are in the worst-case sense, it is not clear how it would be useful for practical machine learning problems. Some discussion along this line would be very helpful.

2, It would be great to discuss the relationship between the Turing universality and the universality of function approximation studied in [1]. 

3, For people who have no background of distributed computing, it would be great to describe CONGEST before going to the impossibility results reduced from CONGEST to GNNs.

4, I do not recommend authors to refer to the computation model 1 as GNN. You could name it as MPNN in order to make the claim more accurate. GNN in general has a few variants which does not fall into this category and could have higher capacity than MPNN. For example, the authors claim that “graph neural networks always sum received messages before any local computation”. However, this is not true in GraphSAGE [2] where the aggregation is a LSTM rather than a simple sum. It makes the model resemble more to the computational model 2. Recent spectral graph convolutional networks [3,4] leverages Krylov subspace methods to compute approximated eigenvalues and eigenvectors of the graph Laplacian which are further used to compute long-range propagation / high-power Laplacian to improve representation power. The results on depth may not hold for these models any more since one layer graph convolution could aggregate multi-hop information. Therefore, being more specific on the model class would make the conclusion more accurate. It would be great to discuss these models separately from the computation model 1.

[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.
[2] Hamilton, W., Ying, Z. and Leskovec, J., 2017. Inductive representation learning on large graphs. In Advances in Neural Information Processing Systems (pp. 1024-1034).
[3] Liao, R., Zhao, Z., Urtasun, R. and Zemel, R.S., 2019. Lanczosnet: Multi-scale deep graph convolutional networks. arXiv preprint arXiv:1901.01484.
[4] Luan, S., Zhao, M., Chang, X.W. and Precup, D., 2019. Break the Ceiling: Stronger Multi-scale Deep Graph Convolutional Networks. arXiv preprint arXiv:1906.02174.

======================================================================================================

The response from authors address most of my concerns. I improved the score.

review_title: Official Blind Review #1

final_score: rating: 6: Weak Accept
review_content: This paper studies theoretical properties of GNN in particular their expressive power. There are many recent works on this topic and the 2019 ICLR paper 'How Powerful are Graph Neural Networks?' is the closes related to this paper. In the 2019 paper connects GNN with the  Weisfeiler-Lehman graph isomorphism test in theoretical computer science. This paper makes a connection between GNN and the locality notion developed in distributed computing.
This connection is rather obvious and GNN being particular local algorithms, their expressive power is at least as limited as the expressive power of local algorithms. In this paper, results in distributed computing are reformulated in a GNN framework mapping the number of rounds required by a local algorithm to the depth of the GNN in order to solve a given graph problem in a worst case scenario.
In my opinion, this paper is rather incremental. In order to improve it, it would be nice to see experiments supporting the theoretical results in section 4. Here it is not clear at all if the bounds given are tight in practice.

###
The authors added experiments supporting their theoretical results. I am upgrading my rating to weak accept.
review_title: Official Blind Review #2

final_score: rating: 8: Accept
review_content: Summary

This paper studied the expressive power of graph NNs, specifically, their universality and limitations under the non-anonymous setting, via the theory of distributed computations. For the universality, it proved the Turing completeness of graph NNs if messaging and aggregation functions are sufficiently strong. For the limitation, it characterized the lower bound of width for solving graph-theoretic tasks (such as subgraph detection, subgraph verification, approximate, and exact optimization problems) using graph NNs. The key idea is to reduce the computation model of graph NNs to LOCAL (for Turing completeness) or CONGEST (for limitations), which are well-studied in the literature of distributed computations and use the known results for these models.


Decision
This paper gave us a new approach to analyzing the expressive power of graph NNs. Not only does this paper give new theoretical results, but also it opens the door to a new research direction by bridging the theories of graph NNs and distributed computations. However, I cannot confirm the correctness of the proof of Theorem 3.1 (see Suggestions section). For now, I am tending to accept the paper. But I want to determine the final decision after I am certain that the proof of the theorem is correct.
We can roughly divide existing approaches for studying the expressive power of graph NNs into two. One is to compare the power of discriminating non-isomorphic graph pairs with isomorphism tests such as the WL isomorphism test (Xu et al., 2019). The other one is to theoretically justify the oversmoothing phenomena (Li et al., 2018). The proof techniques the authors used are different from both of the two. It related a graph NN to the computational models LOCAL and CONGEST, and enabled to incorporate the theory of distributed computations. By doing so, the authors successfully derived many lower bounds in a systematic way, proving the effectiveness of their strategy. I think we can expect that a more refined analysis inspired by this approach will appear in the future.

Regarding the Experience Assessment: I have published several papers in graph NNs (4). But I do not know much about the area of the theory of distributed algorithms (1--3).


Suggestions

- Section 3.2
	- Theorem 3.1 proves the equivalence of GNN_n and LOCAL. However, the definition of equivalence is missing. Please write it in the main part, since this theorem is the key result of this paper.
	- I could not find any reference for the Turing completeness of the LOCAL model. Could you add the reference for it?
	- The description of the CONGEST model is only available in the appendix informally (Appendix B.3). Could you write it in the main part?
	- The authors emphasized the importance of the universality and limitation results in the introduction and paragraph after Corollary 3.1. In my opinion, the importance of such tasks is in machine learning community (Cybenko's paper on the universality of MLPs (Cybenko, 1989) is one of the most cited papers in the community). Rather, I think many graph NN researchers who are expected to read this paper are not familiar with the theory of distributed computations. Therefore, I would recommend to use page resources to explain the basic concepts of the distributed computation theory.


Questions

- Is there any existing work which tries to solve the graph theoretical tasks using graph NNs? If there is, can the theorems in this paper give explanations for the results?


[Cybenko, 1989] Cybenko, George. Approximation by superpositions of a sigmoidal function. Mathematics of control, signals and systems 2.4 (1989): 303-314.
[Li et al., 2018] Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learning. In Proceedings of the 32nd AAAI Conference on Artificial Intelli- gence, pp. 3538–3545, 2018.
[Xu et al., 2019] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In International Conference on Learning Representations, 2019.

review_title: Official Blind Review #3

Meta-review: This paper provides a theoretical background for the expressive power of graph convolutional networks. The results are obviously useful, and the discussion went in the positive way. All reviewers recommend accepting, and I am with them.
Decision: Accept (Poster)