This paper studies theoretically the capacity limits of graph neural networks falling within the message-passing framework (GNN mp ). Two main results are presented. First, GNN mp are shown to be Turing universal under sufficient conditions on their depth, width, node identification, and layer expressiveness. Second, it is discovered that GNN mp can lose a significant portion of their power when their depth and width is restricted. The proposed impossibility statements stem from a new technique that enables the repurposing of seminal results from theoretical computer science and leads to lower bounds for an array of decision, optimization, and estimation problems involving graphs. Strikingly, several of these problems are deemed impossible unless the product of a GNN mp 's depth and width exceeds (a function of) the graph size; this dependence remains significant even for tasks that appear simple or when considering approximation.
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.