Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 10: strong accept, should be highlighted at the conference
review_content: summary_of_the_paper: This paper introduces a new approach to study the separation power and approximation properties of graph neural networks (GNN). The authors introduce the Tensor Languages (TL) and show the representation of GNN as TL expressions. In Section 4, they show the separation power of TL and relate it to color refinement algorithms like k-WL. In particular, they are able to characterize the separation power of such algorithms after a given number of iterations. These results allows them to compute in Section 5 the separation power of GNNs. They are able to recover all results in the literature in an unified way and prove some new results. In Section 6, they give consequences of their results in term of approximation of GNNs, recovering known results and proving new ones.
This is a theoretical paper without any experimental results.
main_review: Strengths: the paper is very clearly written and makes a clear new connection between programming language and deep learning. Formalizing GNN as a TL is a new toolbox that allows the authors to get an unified theoretical analysis of the separating power of GNNs. In particular, they are able to get new results characterizing the expressive power of GNNs as a function of the number of layers. This alone is a very nice contribution.

Weakness: I think Section 6 on function approximation is less relevant. The main reason is that the authors consider the discrete topology on the set of graphs so that any function is continuous. But GNN are more restricted functions and are continuous as mapping acting on tensors. As a consequence, I think:
1- the results presented in section 6 are correct but could probably be proved with simpler arguments similar to the ones used in Appendix A of 'On the equivalence between graph isomorphism testing and function approximation with GNNs' by Zhengdao Chen, Soledad Villar, Lei Chen, Joan Bruna.
2- the consequences of Theorem 6.1 and Corollary 6.2 are not clear for GNNs as GNNs cannot model any function taking a graph as argument. Indeed the importance of continuity is highlighted in section 3 of 'On the Limitations of Representing Functions on Sets' by Edward Wagstaff, Fabian Fuchs, Martin Engelcke, Ingmar Posner, Michael Osborne.
I think the authors should address this issue in Section 6.2 by explaining the possible limitation of their approach. Note that Azizian and Lelarge probably consider continuous functions of tensor representation of the graph for this reason.
summary_of_the_review: Very nice contribution making a new connection between programming language and GNN to study their expressive power.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper defined formal languages for describing tensor expressions. It showed that their expressive power is identical to (suitably parameterized) color refinement algorithms or (vertex/graph) WL algorithms. Then, by translating existing GNNs into the tensor languages, this paper provided upper bounds for the expressive power of GNNs, which recovered several existing results. In addition, this paper characterized the closure of a function class by functions whose expressive power is equal to or less than the functions (Theorem 6.1). As an application, this paper characterized the expressive power of several GNNs via the tensor language (Corollary 6.2, Proposition E.3).
main_review: # Post-rebuttal Comments (11/29/2021)

I appreciate the authors for their response. I am satisfied with their answers. So, I want to keep my score and vote for acceptance.

# Initial Comments

【Strength】
- [1] This paper gives a general procedure for deriving the upper bound of expressive power for any GNN as long as we can translate it into the tensor language.
- [2] Theorem 6.1 and Corollary 6.2 allow us to give lower bounds on the expressive power of GNNs as well.

【Weakness】
- [1] Compared to the upper bound, it is more difficult to show the lower bound of expressive power because the former needs individual proof for concrete GNNs.
- [2] Those familiar with GNNs but not with the first-order logic may be hard to follow up the discussion of the paper.

【Correctness】
- [1] As far as I checked, I could not find any inappropriate points in the proofs.
- [2] What I am wondering is that in Theorem 4.1, the equivalence relation $\rho_1(\mathsf{TL}_{k+1}(\Omega))$ is independent of the choice of $\Omega$. Considering the case of $\Omega=\emptyset$, does this result imply that the separation power of the tensor language does not increase even if we add expressive functions such as non-linear activation functions or MLPs?

【Technical Novelty And Significance】
- [1] As mentioned in this paper, several studies such as [Barcelo et al., 2020 ] have studied the expressive power of GNNs via first-order logic. However, while [Barcelo et al., 2020] related GNNs to the existing first-order logic (namely, $\mathrm{FOC}_2$), this paper defined a new grammar, the tensor language $\mathsf{TL}$, and related GNNs to the first-order logic via this language. In this sense, the approach of this paper is novel.
- [2] This approach allows us to analyze expressive power independently of particular GNNs. In addition, it is relatively easy to derive the expressive power of a GNN because it is sufficient to translate the GNN into the tensor language. Therefore, I think this approach is significant.
- [3] There is no easy and general way to obtain the guarantees for the lower bound of the expressive power compared with the upper bound. We have to check the sufficient condition of Corollary 6.2 for each GNN, which needs proof tailored to the GNN. If we can find a general approach to obtain the guarantees, it would increase the paper's significance. (However, it is also notable that this paper obtained lower bounds systematically to some extent, as mentioned in Proposition E.3.)
- [4] The paper gives positive answers to the unresolved issues raised by existing studies. In this sense, this paper is significant.

【Empirical Novelty And Significance】
- [1] This paper does not have numerical experiments.

【Detailed Comments】
- [1] P.3: I think it is better to write the definition of irreflexivity as it is not well-known.
- [2] P.3: Initially, for a graph $G$ and $\mathbfit{v}\in V^k_G$, ... → I am afraid this sentence is hard to understand, especially the part "where, atp_k(G, v) is the atomic type...". Could you reconsider the sentence?
- [3] P.4: I think $S$ is undefined.
- [4] P.6: The definition of $\mathsf{C}_{k+1}$ does not appear in the main text (only available in Appendix).
- [5] P.13: $\pi_{\sigma\star G}\textlbrackdbl \varphi_1, \sigma \star \nu \textrbrackdbl \cdot \pi_{\star G}\textlbrackdbl \varphi_2, \sigma \star \nu \textrbrackdbl$ → $\star G$ should be $\sigma\star G$.
- [6] P.15: e..g., → e.g., 
- [7] P.16: Here the unravelling is the (infinite tree ... → remove the parenthesis
- [8] P.17: $\pi_{H}\textlbrackdbl \varphi_1, \mu[x_i \to v] \textrbrackdbl$ → $\pi_{G}\textlbrackdbl \varphi_1, \mu[x_i \to v] \textrbrackdbl$
summary_of_the_review: As far as I checked, I could not find any incorrect points in the proofs. I think this paper is technically novel and significant as it gave a model-agnostic approach for analyzing the expressive power of GNNs and solved several conjectures.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper proposes Tensor Language (TL), a language with which popular GNN models can be uniformly studied, so as to yield insights about their expressiveness and separation power. More specifically, the paper shows how TL corresponds to the WL hierarchy, and shows that summation depth in TL, as well as the number of index variables, correspond directly to iterations and tuple size for k-WL, respectively. Moreover, the paper establishes a direct correspondence between GNN update equations and expressions in TL, thus offering a simpler means to understand the expressive and separation power of GNNs, even considering their number of layers, by mapping their architectures to expressions in TL. TL , as well as its guarded fragment GTL, are then used to re-establish a set of known GNN results from the literature. 

Beyond expressive power, TL is also used to quantify the function approximation power of GNNs, and also shows that GNNs, characterized by a TL fragment, can learn functions with separation power upper-bounded by a refinement algorithm corresponding to this fragment. Finally, the TL framework is used to establish new results. In particular, it shows that k-IGN cannot achieve expressiveness beyond (k-1)-WL, as this model corresponds to tk iterations of (k-1)-WL, and also offers insights as to the expressiveness of k-IGN with a polynomial number of layers: Indeed, model power does not increase with more standard layers, e.g., those relying on the adjacency matrix, but rather, any increase in layers can only improve expressiveness by deriving GNN functions with e.g., increased treewidth.
main_review: The unified framework provided by TL is interesting, and allows a more uniform study of GNN models, and a simpler means to derive expressiveness bounds for new GNN models. The study of TL is also very well-grounded in the literature, as it includes most of the key works on GNN expressive power, and additionally confirms their findings. Furthermore, TL establishes a new set of results, thereby addressing some open questions in the field. In particular, it produces interesting insights about the effect of more layers, connecting this explicitly to treewidth and thus adding a nice nuance to this discussion. The results also appear intuitive and sound, though I did not check these thoroughly. Hence, the paper seems to be a valuable addition to the literature on GNNs.

Nonetheless, I find that the novelty of the approach is limited, particular relative to other frameworks characterizing GNNs. In particular, I cannot see the novelty proposed by TL relative to the matrix query languages mentioned in the paper. Therefore, I strongly suggest a more through comparison with related work. Furthermore, it is not clear how much simpler writing a TL expression for GNNs is, particularly with respect to non-standard GNNs involving, e.g, sub-structure counting. Hence, a more detailed presentation of specific model TL expressions, including some from the supplementary material, should be added into the paper to more clearly present the TL translation process. On a more minor note, the current writing style and notation are hard to follow. I refer specifically to Page 3, and the explanation of cr, gwl,vwl, etc. This section required multiple reads to be properly understood, and is quite dense. This is also true of other parts in the paper, e.g., Page 7. Therefore, a more simplified presentation, supported by examples, would be beneficial. Finally, the authors can also consider studying their framework with respect to classes of functions (or universality), as in Barcelo et al. [1], rather than just function approximation relative to separating power, to provide a more holistic overview of the GNN landscape. Alternatively, illustrations of functions with separation power limits can also benefit the presentation in this part of the paper. 

[1] Barcelo et al. The logical expressiveness of graph neural networks. ICLR 2020.
summary_of_the_review: The paper's main proposal, TL, offers a novel and simple means to characterize the power of GNNs irrespective of specific design choices, and helps derive some new results for GNNs. All in all, the paper makes good contributions, but some of its claims, namely the simplicity of TL translation, as well as its novelty, should be better explained.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper proposed a novel way of evaluating the expressive power of any arbitrary GNNs in terms of WL test order using tensor language. The main motivation of this paper is that there is no straight forward expressive power evaluation tool so far. All existing methods need architecture specific proofs. Main challenge is the translating given GNN into tensor language. Later, they easily parametrize given GNN by two numbers which are the number of indices of tensor language ($k$ ) and number of summation depth ($t$). Then, they claimed that given GNN's expressive power is equal to $k-1$-WL test when it applies $t$ coloring rounds.
main_review: ## Strong Points

1. Evaluation of the expressive power of GNN is indeed not straightforward and needs a lot of architecture specific proofs. Indeed, we need model agnostic way to evaluate expressive power of any GNN.  Thus the main motivation of the paper is appropriate and might have a significant effect on the literature.

2. Paper was written well, quite clear and understandable. It includes enough theoretical proofs and examples on how to find the expressive power of some well-known GNNs.

## Clarifying the used WL test order

Clarifying the used WL test order would be great. In GNN papers, generally we call CR as 1-WL, then original 1-WL as 2-WL and so on and so forth. It seems that this paper follows (Cai et al 1992) notations. It means the GNN in (Maron et al.,2019b) , known to have 3-WL power in the original paper, has 2-WL power according to this paper. It would be better if this point is clearly mentioned.

## Weak Points

1. The way of evaluating expressive power by tensor language is not new at all. According to my knowledge, this kind of evaluation was recently proposed in [1]. They introduced Geerts' matrix query language (MATLANG) for GNN world and showed how to use it in order to evaluate some well known GNN's expressive power by write down given GNN's forward calculations in matrix form. Then, they figured the expressive power out by determining which language can explain GNN's forward calculations. Thus, In Separation Power sections "We do not have any general technique allowing us to expand these results for arbitrary GNNs" and in Related Work section "general matrix query languages are known,albeit not in the context of GNNs" are basically not true. Also [1] falsified the claim that "In summary, our paper draws new and interesting connections between tensor languages, GNN architectures and classic graph algorithms". I strongly think the connection between the tensor language and WL-test order of GNN models is interesting and valuable, but not novel. Definitely the differences between similar recent works should be discussed.  

2. Showing how many iterations of the WL-test equivalent of the given GNN is trivial. It is well-known that an additional layer in GNN is equivalent to WL-test's additional iteration (coloring rounds). So in expressive power analysis, we can assume that we always have enough layers as we assume the WL test continues till the stabilization of colors. Introducing that depth parameter as a contribution seems a little exaggerated. In my mind, just WL test order equivalence is enough. 

3. Even though the main claim is that by this paper, anyone can determine the GNN's expressive power easily, is not that straight forward. One needs to write down the GNN layer in tensor form. It seems possible while using summation and/or weighted summation for neighborhood aggregation. How about other aggregations? Can PNA ( GNN that uses different aggregation such as max, min, std) be evaluated by this framework? I have seen that in Appendix, there is an example for GraphSage's version which uses sum aggregation. But the main version of GraphSage uses max.  There is no analysis for max aggregator of GraphSage. Is it possible to do it? Also some GNN such as Chebnet can be more powerful than 1-WL in some certain cases. But in general it is not less powerful than 1-WL. Can the proposed method determine this special case? Can Chebnet expressive power analysis be at least on the appendix?

4. By Geerts' matrix query language MATLANG, we can determine the expressive power up to 3-WL (or 2-WL in Cai et al 1992 notation). This paper extends this matrix language in order to determine the expressive power of GNN which goes beyond the 3-WL. However, due to the memory and cpu complexity it is not that practical and I have never seen any GNN in practice whose expressive power is more than 3-WL. So the main contribution of the paper beside what MATLANG provides, seems not necessary in practice at least for now. I am suspicious if we really need more powerful than 3-WL GNN. Thus maybe these theoretical analyses will never be used.

5. One of the main practical advantages of this theoretical work would be to give us some insight on how to increase the expressive power of GNN. Even though it is mentioned in the abstract, I am not sure these insights are clear enough. Can we create a new GNN architecture to use these insights? I see that experimental work such that proposing a new GNN is not the main idea of the authors. But at least some clear examples on how to increase expressive power would be very valuable.  


### Reference
[1] Muhammet Balcilar, Pierre Heroux, Benoit Gauzere, Pascal Vasseur, Sebastien Adam, and Paul Honeine. Breaking the limits of message passing graph neural networks. In Proceedings of the 38th International Conference on Machine Learning (ICML), 2021

summary_of_the_review: I think theoretical sounds of the paper is quite strong and the main motivation is valid.
I am slightly to lean to recommend acceptance for this paper. But  above 5 points should be addressed.

After rebuttal,the authors pointed out all my concerns very well. Therefore I would recommend clear acceptance for this work.
review_title: null

Meta-review: This paper gives a new theoretical framework to characterize the expressive power of graph neural networks that describes GNN by tensor language (TL) and then makes it possible to analyze its expressive power through the lens of TL. The authors connect the expressive ability of TL to the color refinement algorithms and (vertex/graph) k-WL algorithms. By doing so, the several existing results can be recovered in a unifying manner. In addition to that, the function approximation ability is also investigated. 

The paper gives a novel theoretical framework that gives a clear perspective to the problem of expressive power of GNN, which would be quite beneficial to the community and open up a new research direction. The reviewers have raised several questions on the paper, but the authors addressed all the concerns properly. Therefore, I recommend acceptance to ICLR2022.
Decision: Accept (Oral)