Is uniform expressivity too restrictive? Towards efficient expressivity of GNNs

Thanks for the positive appreciation of our paper and your feedback!

Regarding your comments about the weaknesses of the paper:

a) Despite the uniform expressivity limitations, these same GNNs have indeed efficient approximation properties. Our results indeed indicate that uniform expressivity is only one measure that can be completed with efficient approximate expressivity. An additional insight is that, if some knowledge about the depth of GC2 query to be learned, then one can theoretically restrict to GNNs with combination functions of some depth. However, we agree that a fine-grained guidance on the design of GNNs would complement this work further.

b) For the update part, to the best of our knowledge, such results do not exist in the exact same setup. We do an extended comparison of the existing results in the literature in the introduction that included the main results we are aware of at the interface of logic and expressivity of GNNs.

Regarding your last question:

Thanks for the interesting question. We are unable to provide a complete answer. However, let us point two observations: 1) Note that CReLU is bounded, and so boundedness alone is not an obstruction to uniform expressivity of GC2 formulas. 2) Also, as the paper "`The logic of rational graph neural networks", cited in the references, shows that unboundedness alone is not sufficient for uniform expressivity, since GNNs with rational activation functions cannot express uniformly GC2 formulas.

Miscellaneous:

1. Thank you. We corrected it.

2. Thank you. We corrected it.

3. There is a typo in Corollaries 5.6 and 5.7, we have corrected them.

Thank you a lot for taking the time to review our paper! We appreciate the comments that you raised about our paper.

Regarding the weaknesses that you bring up, these are our answers:

W1) It is true that ReLU is not a step-like activation function (according to our definition). In general, our proof of Theorem 3.4 relies on being able to approximate CReLU efficiently. However, we ignore the exact domain of applicability of Theorem 5.1. The question that you raise is an interesting question, but we are unable to provide a meaningful answer. However, we believe that step-like activation functions cover many of the cases with a monotone sufficiently smooth activation function—we hope that our examples showcase this.

W2) You are right, $\sigma'$ stands for the derivative. Also, $\sigma^N$ stands for the composition of $\sigma$ with itself $N$ times. We have added this in the Notation section, as well as in other parts, to avoid confusion.

W3 & W4) Observe that if we can express an activation function $\tilde{\sigma}$ as an NN with activation function $\sigma$ (of course this NN has both a 1-dimensional domain and codomain as it is expressing a function $\tilde{\sigma}:\mathbb{R}\rightarrow\mathbb{R}$), then any NN with activation function $\tilde{\sigma}$ can be converted into an NN with activation function $\sigma$. Of course, this will affect the parameters of the resulting NN, but not in a significant way.

Being more explicit, assume that $\tilde{\sigma}$ can be written as an NN with activation function $\sigma$ with $m$ layers of respective width $r_{\text{input}}=1,r_1,\ldots,r_{m},r_{\text{output}}=1$, where $r_{\text{input}}$ denotes the width of the input layer, $r_o$ the width of the output layer, and $r_1,\ldots,r_m$ the middle layers where the activation function $\sigma$ is applied. Then every NN with activation function $\tilde{\sigma}$ with $\ell$ layers $w_{\text{input}},w_1,\ldots,w_{\ell},w_{\text{output}}$, where $w_{\text{input}}$ is the dimension of the input vector and $w_{\text{output}}$ the dimension of the output vector, can be converted into a NN with activation function $\sigma$ with $\ell m$ layers

One can see that such an NN is not general having a lot of zero-weights and a so a very particular block structure. However, to show expressivity we only need to show that there is a NN that can express the function at hand.

In our setting, the NN to express $\tilde{\sigma}$ in terms of $\sigma$ is a small fixed NN. In this way, using our definition of size of the NN (the sum of the widths), we can see that the size of the new NN

is bounded by the product of the sizes of the NN using $\tilde{\sigma}$ and the NN that expresses $\tilde{\sigma}$ using $\sigma$. Similar expression can be obtained for the number of parameters, but we hope that this clarifies why the combination of NNs that we do is permitted.

Further, we added an appendix specifying this to make it clear in the paper.

Minor Issues: We have corrected this. Thanks for pointing them out.

Suggestion: We agree that this might be possible to do. However, we feel that this goes beyond the scope of the paper: to show that almost-uniform expressivity is possible for many activation function for which uniform expressivity fails. Even though we are certain the positive results from Section 5 would extend to higher order GNNs, we believe that there is not a simple extension of the impossibility results of Section 4.

Thank you for your response. I think the response has addressed most of my concerns.

About W3 & W4

However, to show expressivity we only need to show that there is a NN that can express the function at hand.

This is true and I agree with you. Nevertheless, considering the major contribution of this paper is to show that MPNNs with step-like activations can express logic formulas without using too many parameters, I believe it is still necessary to explicitly discuss the number of parameters induced by similuting $\sigma$ functions with NNs. Therefore, the authors are encouraged to add relevent discussions in the final version. (I didn't see an Appendix section discussing about this; am I missing something?)

Going on, I am still concerned about the correstness of Corollary 5.5, 5.6, 5.7. E.g., using your example, shouldn't the size of the GNNs in Corollary 5.5 have a term $O(d)$? Please correct me if I was wrong.

Overall, I thank the authors for the response, and hope the above concerns could be clarified.

Thank you for taking the time to read the paper! We appreciate your comments.

We answer now the weaknesses that you are raising:

1. We have further proofread the paper and to eliminate existing typos and errors. In particular, we have corrected all the ones that you have pointed out. Thank you for such an extensive list.

2. We have clarified that the trees $T[x,k,m]$ are rooted trees in $s$. Also, note that a leaf node of a tree is defined as a vertex of degree $1$. So as soon as $m> 1$, $s$ is never a leaf of $T[x,k,m]$.

3. In Section 6, we have now renamed the number of layers of the combine functions to $\ell$ to avoid confusion with the number of vertices at depth $2$ of the input graphs, $m$. The statement around line 495 was that the ability of the GNNs to separate both trees $T[0, k, m]$ and $T[1, k,m]$ is increasing as a function of $\ell$. We further proofread section 6 and made explanations clearer.

4. Thanks for pointing this out. We agree that the formulation was too sudden. We replaced this part as follows: ``The combination functions using step-like activation functions used in our approximation of GC2 queries have large gradients. We suspect this adds to the difficulty to efficiently train these networks to optimality, despite their ability to approximate queries to an arbitrary level of precision''.

Thanks for your detailed reading and appreciation of our work!

Regarding the weaknesses that you raise:

In answer to your comment about explicit connections between tanh, Sigmoid and their Pfaffian chain, we have added to the proof of Proposition 2.1 also an explicit chain for tanh. Regarding the parameters of step-like activation functions, we will a remark after Definition 5.1 or in the appendix if length does not permit.

• We have corrected this in Example 2.1 and added a description of the interpretation of $E(x,y)$ in our context, which means that the variables $x$ and $y$ (as vertices) are connected in the considered graph.

• Agreed. We have rewritten Definition 2.4. to be more explicit about what a Pfaffian function is, adding that is a function that is the last term $f_r$ of a Pfaffian chain.

• Thank you. We have corrected this in the article.

• Thank you. We have corrected this in the article.

• We believe the answer to this question should appear in the lines 292 and 293 just below.

• This notations refers to composition, we have added an explanation of the notation in the paragraph ``Notations'' of Section 2.

Regarding your three questions:

• Indeed, we are concerned about it. Because of this, at the end of Section 6, we present some preliminary experimental results show the difficulty to actually learn GC2 queries. However, we plan a deeper study of learnability for future work.

• Note that $N$, $H$ and $\varepsilon$ are interrelated due to (c) and (d) in Definition 5.1. For example, a large $H$ and a small $\varepsilon$ force a larger $N$. In this way, the parameters $H$ and $\epsilon$ influence the size of $N$ that is the one explicitly appearing in the complexity estimates that we give.

• The GC2 query to be expressed will impact the amplitude of the weights. However, the parameters $\eta, \epsilon, N, H$ in the assumptions of Theorem 5.1 will not impact the weights amplitude, as we compose the step-like activation with itself. Only the speed of convergence to the step function, and so the number of layers, may depend on these parameters.