Is uniform expressivity too restrictive? Towards efficient expressivity of GNNs

Authors: Sammy Khalife, Josué Tonelli-Cueto
Primary area: learning on graphs and other geometries & topologies
Keywords: Graph Neural Networks, Expressivity, Efficiency, Activation Function, Queries, Logic

Abstract:
Uniform expressivity  guarantees that a Graph Neural Network (GNN) can express a query without the parameters depending on the size of the input graphs. This property is desirable in applications in order to  have number of trainable parameters  that is independent of the size of the input graphs. Uniform expressivity of the two variable guarded fragment (GC2) of first order logic is a well-celebrated result for Rectified Linear Unit (ReLU) GNNs [Barcelo &. Al, 2020]. In this article, we prove that uniform expressivity of GC2 queries is not possible for GNNs with a wide class of Pfaffian activation functions (including the sigmoid and $\tanh$), answering a question formulated by [Grohe, 2021]. We also show that despite these limitations, many of those GNNs can still efficiently express GC2 queries in a way that the number of parameters remains logarithmic on the maximal degree of the input graphs. Furthermore, we demonstrate that a log-log dependency on the degree is achievable for a certain choice of activation function. This shows that uniform expressivity can be successfully relaxed by covering large graphs appearing in practical applications. Our experiments illustrates that our theoretical estimates hold in practice.

Decision: accept (poster)
Reviewer scores: 6, 8, 6, 8

Reviews and discussion:
<thread>
creation date:
1730535009990

thread_type:
official_review

<thread_object>
creator: reviewer_6aa7

<content>
summary:
This papers studies the following fundamental question. Any node binary classification task can be defined as a logic formula. The paper tries to understand whether common GNN architectures can learn a given logic formulas **uniformly** (over all graphs with unbounded size). This is in stark contrast with prior research, which typically allows the model size to grow with input graph size. The authors gave both negative and positive results, showing that GNNs with sigmoid/tanh activations cannot uniformly approximate GC2 logic formulas, but they can almost-uniformly approximate them. The authors gave both counterexamples and constructions in their proof. Finally, they conduct experiments to verify their results.

strengths:
I would like to say this is a quite interesting paper and I like it a lot. First, this paper studies GNN expressivity from a novel perspective. Unlike prior work which largely focuses on graph isomorphism (which is mainly TCS/graph theory perspectives), this paper is clearly more relevant to real neural network architectures instead of abstract color refinement algorithms, making it especially relevant to the community. On the other hand, this paper differs from traditional function approximate theory, as these theories often let the model size to grow in order to approximate better with a larger input domain. Instead, this paper gives both positive and negative results on whether a *fixed* model can deal with graph learning tasks for all inputs. This ability is unique for graph learning tasks.

Secondly, the paper provides a rigorous theoretical foundation. All definitions and statements are well-defined and accessible, which enhances clarity. I find the results nontrivial and impactful, and it enhances our understanding in the community.

weaknesses:
One potential weakness of these results is that almost-uniform expressivity is perhaps already sufficient. Therefore, the limitations of sigmoid/tanh networks is not that severe in practice. So this paper may have a limited impact in guiding practical design of GNNs.

Update: I should acknowledge that I am not very familiar with first-order logics beyond the paper of Barcelo (2020). I am not sure if similar ideas have been raised in prior work (possibly under a different community).

questions:
I am curious about the insights behind the theoretical results. I suspect this may be due to the sigmoid/tanh function is bounded, so it can not  express a quantity that grows with input size. On the other hand, ReLU/CReLU is not bounded. I wonder whether any unbounded non-linear activation is sufficient for uniform expressivity?


Miscellaneous：
1. Definition 2.4: U should be $U$.
2. Page 7, line 350: the word "the" is redundant.
3. What is the difference between Corollaries 5.6 and 5.7? I suspect there is a typo here.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730607120043

thread_type:
official_review

<thread_object>
creator: reviewer_mu1a

<content>
summary:
In the study of GNN expressivity, it is crucial for practical usage to take the number of parameters needed into consideration. To this end, uniform expressivity has been proposed to test whether GNNs can express a query with the number of parameters independent on the size of the input graphs. However, in this paper the authors found that uniform expressivity tends to be too restricted for a wide class of GNN models. This paper then relaxes the concept of uniform expressivity into almost-uniform expressivity and further show that most GNNs can be still quite expressive when restricting the number of parameters to be logarithmic on the maximal degree, satisfying most practical needs. The results in this paper are justified by both theoretical analysis and numerical experiments.

strengths:
- Compared with general expressivity measurement of GNNs, uniform expressivity sometimes tends to be too strict, thus provides negative results for GNNs: as shown in this paper, MPNNs with sigmoid activations cannot uniform express GC2 queries. To this end, it is nice to find a balance between general expressivity (which does not consider the number of parameters) and uniform expressivity (where the number of parameters is independ w.r.t. input graphs) for practical needs. The log complexity of parameters described in this paper is realizable for most practical situations.
- This paper considers a wide class of activations, defined as step-like activation functions. The authors show that their results are applicable for many practical activation functions including sigmoid and tanh.

weaknesses:
- The study in this paper relies on the definition of step-like activation functions. The properties of step-like activation function still requires more discussion. Specially, I have some concerns regarding the definition of step-like activation functions:
  - The Relu function ReLU(x)=max{0,x} clearly is not a step-like activation function since it disobeys (a): $\sigma(1)=1$. A question naturally arises: is the set of all possible step-like activation functions large enough to cover up most situations (or further, is it possible to find the maximal set of activation functions that satisfies Theorem 3.4)?
  - In Definition 5.1, I assume in (b), $\sigma'$ is the derivative of $\sigma$. What does $\sigma^N$ in (c) mean? I searched over the paper but couldn't find an explanation.
  - To derive Corollary 3.5 from Theorem 3.4 it is necessary to show that sigmoid and tanh are special cases of step-like activation functions with $\eta=0$. However, Proposition 5.3 and Proposition 5.4 states that only a 3-layer NN with tanh and a 5-layer NN with sigmoid can be step-like activations. If this is the case, it largely restricts the structure of GNNs: the results in this paper are only applicable to MPNNs whose activations are again multi-layer NNs. This setting should be mentioned in the former parts of the paper when defining GNNs.
  - Continuing from the above concern. In Proposition 5.3 (and similarly in Proposition 5.4), a 3-layer NN is needed to express step-like activation function. Note that an activation function is a **point-wise** function that applies independently to each element of the input vector. How does the 3-layer NN behave like a poin-wise function to the input vectors in the whole GNN computation procedure? For example, let $X=[x]$ be the input and $W=[w_1,w_2]^T$ be the parameter at first layer. The output is $[w_1 x,w_2 x]^T$. If the dimension input is changed to be $X=[x_1,x_2]$, how does this reflect to $W$? To me this can be done by setting $W=[[w_1,w_2,0,0]^T,[0,0,w_1,w_2]^T]$ but this makes the number of parameters in each layer linerly grows w.r.t. the input dimension ( and thus makes the total number of parameters $O(d^2)$). Please correct me if I am wrong.

## Minor Issues:
- Corollary 5.5, 5.6, 5.7 all considers tanh activation. Should this be changed to arctan, tanh and sigmoid respectively?

## Suggestions:
- This paper can be further strengthened by discussing more complex GNN variants, e.g. higher-order GNNs. I suspect the number of parameters is logarithmic w.r.t. $N^{k-2}$ for $k$-order MPNNs, with $N$ being the number of nodes.

questions:
Please refer to Weakness. There are some concerns that limit the impacts of the theory in this paper. I am willing to change the score if the concerns / problems are properly discussed / solved.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730661539259

thread_type:
official_review

<thread_object>
creator: reviewer_ikke

<content>
summary:
The paper aims to more closely characterize the uniform approximation capabilities of graph neural networks as a function of the activation functions applied to each aggregation of messages. There are primary theoretical contributions:
1. While previous results suggest that bounded-size guarded model logic (GC2) queries can be expressed by fixed-size GNNs with CReLU activations, Section 3.1 proves that certain GC2 circuits cannot be expressed by GNNs with sigmoid and tanh activations (or more generally, for superpolynomial Pfaffian activations). This limits the universality properties of GNNs. The proof involves constructing pairs of tree graphs whose outputs will be identical as a result of their activations.
2. However, Section 3.2 shows that all bounded-size GC2 queries can be expressed by a GNN whose size grows slowly as a function of the graph degree for sigmoid and tanh activations (and more generally, for "step-like activations").

They validate their theoretical results by training GNNs to learn two synthetic GC2 queries on different graph sizes. These experiments reveal sharp thresholds between the abilities of different activations to distinguish between similar graph instances.

strengths:
The results of the paper are well-motivated theoretically---it is interesting to understand the trade-offs of different activations and the limitations of universal approximation. In particular, such fine-grained separations between constant-size and near-constant-size architectures are interesting, seeing as most graphs are small enough for the $\log\log\Delta$ scaling to be surmountable. 

As far as I can tell, the mathematical results are correct. The proof ideas of distinguishing similar tree graphs and constructing separations with step-wise activations are intuitive.

weaknesses:
In general, the presentation of the results would be improved by more context for Pfaffian and step-like activations. A more close linkage between tanh and sigmoid and the parameters of Pfaffian chain of order would appreciated, along with more examples of step-like activations and an intuitive discussion of their parameters.

While individually unimportant, there are several areas with ambiguous notation or minor mistakes that I would appreciate the authors clarifying:
* Definition 2.3 and Example 2.1 have some inconsistent notation, e.g. $E$ and $Edge$ are used interchangeably, and $\exists^{\geq p}$ is not defined (although it is fairly intuitive). The formula in Example 2.1 appears to indicate that at least one neighbor has at least two neighbors that are _red_, not blue.
* Definition 2.4 introduces a Pfaffian chain of order, but not Pfaffian functions. The relationship between the two should be made explicit.
* In Theorem 3.1, "Conversely, any (aggregation-combine) GNN expresses with activation function CReLU expressed a
GC2 query" does not parse.
* Grammar nit on line 250: "superpolynomial if it non constant".
* On line 291, what is the $y$ limit over? $y$ appears to be vector-valued.
* If Definition 5.1, does the $\sigma^N$ notation reference exponentiation or composition?

questions:
In general, (approximate) linear threshold activations are not practical in neural networks because of lack of bounded derivatives. Are the authors concerned about the learnability of their constructions in Section 5 that simulate threshold activations?

What is the significance of the parameters $H$ and $\epsilon$ on the construction in Theorem 5.1? The other parameters seem to have influence on size complexity, but not those.

Likewise, do know whether the network weights for Theorem 5.1 can be bounded?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730697935933

thread_type:
official_review

<thread_object>
creator: reviewer_ir8p

<content>
summary:
This is a theoretical work about the connection between GC2 and GNNs with various activation functions. Its first contribution is to prove that uniform expressivity is not possible for GNNs with bounded Pfaffian activations. The second contribution is to build non-uniform expressivity for GNNs with Pfaffian activations via a constructive approach. Some synthetic experiments are provided to verify the theoretical arguments.

strengths:
1. The motivation is good: rigorously understanding the expressive power of GNNs is a significant direction, especially it requires carefully quantify expressive capacities with sizes and depths. This work follows this motivation.
2. A rich family of activation functions is considered (such as arctan, tanh, sigmoid), as an extension of previous works about positive and negative results with simpler activation functions. And the general definition of Pfaffian functions makes it possible to generalize to other activations in the future.
3. The presented theory in the main text looks good.

Note that I didn't check all the proof in the appendix.

weaknesses:
1. The presentation seems incomplete in some places, so thorough proofread and revision are necessary. For example:
    * in theorem 3.1, the last sentence is confusing in grammar.
    * in line 197, ''two blue neighbors'' should be ''red''.
    * in line 195, 199, 202, please check whether the parentheses are complete or not.
    * in line 279, the last sentence is not complete.
    * in Figure 2, $l_i$'s are missing. I suppose they are the leaf nodes.
    * around line 318, notations are not consistent, where line 685 uses $\nu_{t,m}(k)$ instead of $\nu_{t}(k,m)$
    * in line 363, what is the meaning of $\\sigma^N(R\\setminus (\\epsilon, 1-\\epsilon))$?
    * in Corollary 5.5, tanh -> arctan
    * in Figure 3, please use different linestyles for easiness of reading, instead of only using different colors
    * in line 495, a ''second'' shall be removed
2. around 335, the mentioned $T[0,k,m]$ and $T[1,k,m]$ seem to assume the tree in Figure 2 is rooted tree from $s$ without backtracking, which means $s$ is not in the leaf nodes. If so, please clarify this when defining the tree.
3. in line 495, please clarify how this layer argument is connected with theoretical results. Does it mean the different layers for activation functions in Prop 5.2-5.4?
4. in line 500, the conjecture about SGD is too sudden without evidence

questions:
Please see the above concerns.
</content>
</thread_object>

</thread>
<thread>
creation date:
1733242508462

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Global Response

comment:
We thank the reviewers for their detailed assessment of our work, and their appreciation for the novelty and the potential impact of our paper. We are sincerely excited by the reviewers' reception that finds that our paper "studies GNN expressivity from a novel perspective" (Reviewer 6aa7) for "a rich family of activation functions" (Reviewer ir8P) "find[ing] a balance between general expressivity [...] and uniform expressivity [...] for practical needs" (Reviewer Mu1a) and "validat[ing] their theoretical results through experiment" (Reviewer ikke). We are grateful for all the comments and constructive feedback that have definitely helped to improve the overall quality of the paper.

For the final version, we will address all the comments of the reviewers and make numerous changes to improve the paper. Unfortunately, we missed the deadline to upload our reviewed version, so we specify all the significant prospective changes below. We note that despite these changes, the paper would remain essentially the same but with broader accessibility and readability. 

In Section 2, we have simplified many of the definitions and expositions, making them more accessible. We have simplified Definition 2.1. regarding neural networks, we have restricted Definition 2.2. to the class of GNNs treated in our paper, we have rewritten Definitions 2.3 for GC2 queries, making it simpler and specifying precisely the depth; we have added a new definition to introduce the notation $Q(v,G)$ that was used before without definition; and we have simplified Definition 2.4 regarding Pfaffian functions. Additionally, we have added the meanings of $\sigma^N$ as composition power, $\sigma'$ as derivative and $\log$ as logarithm in base 2.

In Section 3, we have rewritten Definition 3.1. and Remark 3.1. for clarity. We further corrected the bounds of Theorem 3.4 and Corollary 3.5; see comments regarding Section 5 below.

In Section 4, we have added a description of the tree $T[x,m,k]$ within the text, as well as rearranged the update rule equations and corrected the formula $Q(v)$. We also added a comment to make clear that we are not restricted to one-dimensional vertex-embeddings.

In Section 5, we recall the notations $\sigma^N$ and $\sigma'$ before Definition 5.1. and we remark afterwards regarding the meaning of $N$, $\eta$, $H$ and $\varepsilon$. In Theorem 5.1, we have corrected, apart from an erroneous constant, two main errors in the bound: (1) The $d$ was not multiplying the two summands in the size expression. (2) The first bound should have been $1+\eta$ in the denominator and not $1-\eta$. In this way, the corrected bounds are respectively $\left(3+N+\frac{2+\log(\Delta+2)}{1-\log(1+\eta)}\right)d$ and $\left(3+N+\log\left(2+\log(\delta+2)\right)\right)$. Additionally, we have corrected the expressions depending on these expressions.

In Section 6, we have simplified the exposition of the numerical experiments to make it more accessible to the reader, making the exposition and notation more in line with the one used in the rest of the paper.

In Appendix A, we have rewritten Lemma A.2 to make it more comprehensive and added a lemma indicating the fact that a bounded Pfaffian function has a finite limit in $+\infty$. 

In Appendix B, we have mainly corrected typos and clarified that the proof holds for GNNs producing vertex embeddings of arbitrary size.

In Appendix C, we have made some exposition changes. In C.1, we have rewritten the proof of Theorem 5.1. to make it more accessible and uniform between cases. In C.3, we have added Proposition C.4. indicating how the size of NN increases when we encode an activation function in terms of another NN.

In Appendix D, we have simplified the exposition.
</content>
</thread_object>

</thread>


Metareview:
metareview:
This work  examines the connection between GC2 and GNNs with various activation functions, making two main contributions: proving the impossibility of uniform expressivity for GNNs with bounded Pfaffian activations, and demonstrating non-uniform expressivity through a constructive approach. The paper demonstrates solid theoretical foundations with well-motivated research direction, particularly in understanding GNN expressive power and the reviewers had a consensus that the paper has enough merits to be accepted.