Rethinking the Expressiveness of GNNs: A Computational Model Perspective

Dear Reviewer b62D,

Thank you for taking the time to review our paper. We would like to address your concerns as follows:

W1:

Our primary goal is to reveal limitations in current analyses of GNNs' expressive power and to introduce a new analytical approach that addresses these issues, rather than to develop a specific GNN model with enhanced performance or expressiveness. Specifically, as demonstrated in Theorems 5-8, we leverage the RL-CONGEST framework to provide a more reasonable evaluation of GNNs' expressive power on simulating one iteration of the WL test. Additionally, in Section 5, we also propose open questions that may be investigated within the RL-CONGEST framework. It is important to note that our RL-CONGEST framework is designed to assess a model's expressive power in executing algorithmic tasks or achieving "algorithmic alignment", rather than to predict its quantitative performance on learning tasks such as node classification.

W2:

Yes, the second half of your question, "different features have varying degrees of power; some can help count more complex graph structures than others", precisely reflects what we aim to convey. Under the non-anonymous setting, CONGEST and MPGNNs can exhibit greater expressiveness than the anonymous WL test. Our main argument in Section 3.2 is that while existing works claim their models' expressiveness advantage by proving they can perform tasks beyond the WL test's scope, this approach is questionable. Equating anonymous WL with MPGNNs, as previous works have done, is not entirely reasonable, and consequently, concluding that MPGNNs are weak because the WL test is weak is also debatable. In fact, MPGNNs can perform certain algorithms (such as solving edge biconnectivity in $O(D)$ rounds within the CONGEST model [Pritchard, 2006]).

Our logical flow is as follows:

1. Numerous studies claim that the vanilla WL test has limited expressive power --- a claim that we affirm, as discussed in Figure 2. However, the appropriateness of using the anonymous WL test to characterize MPGNNs is debatable, given that real-world graphs often contain rich features. Additionally, [Loukas, 2020] demonstrated that with unique IDs (and other assumptions), MPGNNs can perform a wide range of algorithmic tasks.
2. To address the "limited" expressiveness of MPGNNs (stemming from the limitation of the vanilla WL test), some works incorporate additional features (e.g., [Loukas, 2020]) to enhance the expressiveness of their proposed models. Nonetheless, as outlined in (1), the suitability of the anonymous WL test as a characterization for MPGNNs is questionable. Consequently, the practice in some studies of demonstrating the advantage of their model's expressiveness by proving it can perform algorithmic tasks beyond the WL test's capabilities may not be entirely valid. A more reasonable approach would be to compare these models with MPGNNs under a non-anonymous setting (as suggested in [Loukas, 2020]). Further, evidence from [Loukas, 2020; Suomela, 2013; den Berg et al., 2018; You et al., 2021; Abbound et al., 2021; Sato et al., 2021] suggests that the non-anonymous setting can enhance model expressiveness, highlighting a mismatch in works that argue for a "weak MPGNN" yet use additional features that break the anonymous setting in the WL test to improve expressiveness.
3. As you mentioned, "different features have varying degrees of power; some can help count more complex graph structures than others", our RL-CONGEST analysis framework can be applied in studies proposing new GNN variants that use additional features and claim the ability to perform certain algorithmic tasks, with the only requirement being a clear specification of the preprocessing time complexity of the features.

Additionally, points (1) and (2) highlight the need to reconsider the validity of comparing a proposed model's expressiveness directly with the vanilla WL test. We hope this discussion encourages the community to more accurately assess existing results on GNNs' expressiveness.

Thank you again for reviewing our paper, and we are looking forward to any further discussions with you.

Thank the authors for the detailed response to my concerns. I have some follow-up questions.

RL-CONGEST framework is designed to assess a model's expressive power in executing algorithmic tasks or achieving "algorithmic alignment"

I am a little confused about this. First, I don't find such a statement in the paper. I assumed that the authors were talking about the general expressivity of GNNs and their downstream performance.

I quite agree with the authors for the arguments they made in the paper: (1) hidden precomputation time; (2) constrained analysis on anonymous WL test. However, I agree with them mainly from a more general perspective. If we confine the discussion to algorithmic tasks, things become different. First, most papers discuss the expressiveness of GNNs in the general setting: to improve the performance of GNNs on downstream tasks. However, downstream tasks not only contain algorithmic tasks. For example, GD-WL [1] forms the story from the bi-connectivity problem, which can be solved with less complexity than computing resistance distance. However, the GD-WL can be used to approximate many other graph properties or count important substructures [2, 3], which is crucial for downstream tasks and may not be done with an algorithm of less complexity.

Back to my original question (W1), I think the authors did a great job of formulating all these conclusions in the paper and I do find many conclusions interesting and original. However, when I start to think about these conclusions from a broader perspective, for example, whether these conclusions can help me gain more insight into evaluating or comparing existing GNNs, or can help me design new expressive GNNs, these conclusions seem limited. That is said, the GNNs are eventually designed for solving real-world problems like node classification or graph classification, which is much more boring than algorithmic tasks.

anonymous WL vs MPNN + ID

I think the authors are totally right in the statement that: by equipping MPNN with non-anonymous node features, MPNN can solve many algorithmic tasks that previous literatures claim not. However, I think the discrepancy here is still the scope of the discussion. Most existing works use anonymous WL tests as a tool because they want to make sure the result expressive GNNs are still permutation invariant and equivariant. Without this assumption, the result GNNs cannot have good performance on real-world tasks. It's true that given a unique ID, MPNN can solve many algorithmic tasks, but it cannot transfer to real-world tasks. For example, [4] injects random features into MPNN to improve expressiveness but many follow-up experiments actually show it achieves bad performance in real-world tasks.

Back to my original question, what I really want to ask is that: additional features can improve the expressive power of MPNN by (1) breaking symmetry and leveraging message passing to learn on that and enhance performance; (2) directly adding additional knowledge about graph structures. It the proposed framework quantitively or qualitatively analyze the portion of these two parts given node features? Or, whether the proposed model can be used to analyze the effect of node features in real-world datasets for the expressiveness of MPNN?

I still hold a positive perspective on the paper. But the above concerns somehow prevents me from further increasing my score.

Reference

[1] Zhang, Bohang, et al, Rethinking the Expressive Power of gnns via Graph Biconnectivity, ICLR23.

[2] Zhang, Bohang, et al, A Complete Expressiveness Hierarchy for Subgraph GNNs via Subgraph Weiisfeiler-Lehman Tests ICML23.

[3] Zhang, Bohang, et al, Beyond Weisfeiler-Lehman: A Quantitative Framework for GNN Expressiveness ICLR24.

[4] Sato, Ryoma, et al, Random Features Strengthen Graph Neural Networks, SDM21.

Dear Reviewer b62D,

Thank you for your kind reply. We believe there are two key points where we may not yet have reached a consensus, and we would like to further clarify our perspective.

On "node IDs" and "non-anonymity":

These terms refer to unique features that allow nodes to be distinguishable (e.g., $[n] = \\{0, 1, \cdots, n - 1\\}$ would also suffice). The distinct-feature setting is commonly applied in almost all existing models, as listed below:

1. LINKX [Lim et al., 2021]:

LINKX uses:

• $\mathbf{H}^{(\mathbf{A})} = \mathrm{MLP}_{\mathbf{A}}(\mathbf{A})$
• $\mathbf{H}^{(\mathbf{X})} = \mathrm{MLP}_{\mathbf{X}}(\mathbf{X})$
• $\mathbf{Y} = \mathrm{MLP}(\sigma(\mathbf{W}[\mathbf{H}^{(\mathbf{A})}; \mathbf{H}^{(\mathbf{X})}] + \mathbf{H}^{(\mathbf{A})} + \mathbf{H}^{(\mathbf{X})}))$

The $\mathbf{H}^{(\mathbf{A})}$ term can be reformulated as $\mathrm{MLP}'(\sigma(\mathbf{A} \cdot \mathbf{I} \cdot \mathbf{W}))$, which uses the identity matrix (unique node features).

2. GCN, GAT, etc., on real-world datasets:

These models often use real-world features, which are unique and distinguishable with high probability. Actually, models that are applicable to real-world datasets fall into this category.

3. GNN expressiveness works (e.g., [Loukas, 2020; Sato et al., 2021]):

These works use random features, which are unique with high probability. For example, assigning each node a feature randomly chosen from $[n^4]$ would result in distinct features with high probability.

4. GD-WL framework:

In the GD-WL framework by Zhang et al., resistance distances $R(s, t)$ are used as features. Since $R(s, t) = 0$ iff $s = t$, each row of the resistance distance matrix is unique, creating distinguishable node features.

Actually, according to our theory, they are all capable of solving the biconnectivity problem using the unique features.

On whether unique features break equivariance or invariance:

Unique features do not break permutation equivariance or invariance. Instead, it is the properties of the update functions and pooling layers that determine whether a GNN model is equivariant or invariant. For example, in LINKX, when performing node classification, $\mathrm{MLP}(\mathbf{A})$ ensures permutation equivariance. To achieve permutation invariance for graph classification, we only need to add a permutation-invariant pooling layer after this step.

Similarly, consider Dijkstra's single-source shortest path algorithm. Unique IDs are used solely to determine whether the shortest path to a node has been found. The resulting shortest path distance vector is always permutation equivariant. This demonstrates that it is not the presence of unique IDs but rather the design of the update function that determines whether a GNN model is permutation equivariant or invariant.

We hope these clarifications address your concerns and further show the flexibility of our framework. Thank you again for your engagement and constructive feedback.

Reference:

[Lim et al., 2021]. Large Scale Learning on Non-Homophilous Graphs: New Benchmarks and Strong Simple Methods. NeurIPS 2021. [Sato et al., 2021] Ryoma Sato, Makoto Yamada, and Hisashi Kashima. Random Features Strengthen Graph Neural Networks. SDM 2021.

The LINKX is only applicable to transductive settings, where we only have a single graph and do not require the model to generalize. At this time, by assigning each nodes a unique ID, the single MLP can achieve a "universal approximation" on any functions within this particular graph. If this is the unique ID you are referring, I think the statement becomes somehow meaningless. All GNN's expressiveness is analyzed with an assumption of the inductive setting, that is we want to train a GNN on some train graphs set and generalize it to unseen graphs with different sizes and graph distribution. And that's why the permutation invariant and equivariant are important.

I have a similar feeling to reviewer YAM3 that authors always try not to answer my concerns directly and ignore some of my questions. So I try to make my question even more direct:

Could the authors give me a concrete example of how to use RL-CONGEST model and distinct-feature to train an MPNN model that can solve the bi-connectivity problem with some training graphs and labels? How can the model generalize to unseen graph samples with different graph structures and size?

I believe if your example is reasonable, most of my concerns can be solved.

Dear Reviewer b62D,

Thank you for your response. We would like to further clarify our ideas and address your concerns.

On Existence and Trainability

We have clearly stated in our previous response that in our paper, we focus on existence and impossibility results, and do not address how to use real-world optimizers to train a model to solve problems like biconnectivity. These are two aspects of independent interest. It is not fair to criticize us that we are "avoiding problems" simply because we state that trainability is beyond the scope of this paper. Furthermore, we are not aware of any GNN expressiveness paper (proving that GNNs can solve specific algorithmic tasks) that has theoretically showed how to train a GNN using SGD or other optimization techniques to solve such tasks. If you are aware of such works, please list them, as we would be eager to learn from their techniques for future improvements.

In our paper, as in the works we cite, we prove theorems of the form: "for each graph $G$, there exists an RL-CONGEST model that operates on it and solves the algorithmic task". These existence results are universal and hold for every graph. However, we do not claim to prove how such a model can be practically trained.

On LINKX in the Inductive Learning Setting

Simply stating that LINKX is not applicable to the inductive learning setting is a misunderstanding. We can address this by setting a maximum number of nodes for graphs, say $N$, and padding all adjacency matrices $\mathbf{A}_i \in \mathbb{R}^{n_i \times n_i}$ to $\mathbf{A}_i' = \begin{bmatrix} \mathbf{A}_i & 0 \\\\ 0 & 0 \end{bmatrix} \in \mathbb{R}^{N \times N}$. This approach mirrors the padding technique commonly used in the NLP domain.

Your concerns are akin to questions in the NLP area like, "The length of inputs varies, how can they be input into the same Transformer?" or "Your model can only handle sequences of the same length and cannot be applied to the inductive setting". The first concern is resolved using padding, and the second has been validated by the success of Transformer-based large language models.

Overall, we deeply appreciate your effort in engaging in discussions with us.

Dear Reviewer DTJH,

Thank you for reviewing our paper. We are very grateful for your detailed feedback and appreciate the opportunity to address some misunderstandings that may have arisen in the “Weaknesses” section of your review.

Regarding Unlimited Computational Resources in the CONGEST Model:

We respectfully disagree with the comment that "just use a more restrictive computation class for the node updates". Our goal is to introduce flexible constraints on the resources class $\mathsf{C}$ to derive different independent results, as discussed in Lines 381-389. For instance, setting $\mathsf{C} = \mathsf{R}$ (the class of recursive languages decidable by Turing machines) and network width $w = O(1)$ transforms our RL-CONGEST framework into the CONGEST model. By setting $\mathsf{C}$ to a class such as $\mathsf{TC}^0$, which reflects the capabilities of MLPs, the resulting model would resemble "real-world" GNNs with MLPs as update functions. Alternatively, if node update functions used transformer-based LLM agents enhanced by Chain-of-Thought (CoT) reasoning, which are claimed to solve problems in $\mathsf{P}$ exactly [Merrill et al., 2024; Li et al., 2024], we could set $\mathsf{C} = \mathsf{P}$ to derive new theoretical results based on this adjustment. We hope that our framework can inspire future research on graph agents, and have added it in red color in the revised PDF (Lines 384-387). As discussed in Lines 381-389, adjusting $\mathsf{C}$ in different ways may yield diverse outcomes, making our RL-CONGEST framework a "framework scheme" or "framework template".

We respect your statement that "is more defined by approximation quality of whatever computation it needs to perform". We recognize the importance of the Universal Approximation Theorem (UAT) in machine learning and are aware of work addressing the approximation capabilities of GNNs, such as [Azizian et al., 2021; Wang et al., 2022]. However, as indicated by our paper's title, our work aligns with a different research path, focusing on a model's expressiveness through its capability to perform algorithmic tasks. For example, [Loukas, 2020] uses the CONGEST model to analyze MPGNNs' algorithmic abilities, while the Outstanding Paper at ICLR 2023 [Zhang et al., 2023] assesses GNNs' power to determine graph biconnectivity. These two lines of research --- expressiveness for algorithmic tasks versus approximation quality --- are largely orthogonal and develop independently. Additionally, discussions in the literature (e.g., Section 1.1 in [Loukas, 2020], which states that "Turing completeness is a strictly stronger property than universal approximation") suggest that Turing completeness is indeed a stronger property than universal approximation. Therefore, we believe that our focus on computability is sufficiently general and without loss of scope.

Dear Reviewer DTJH,

As we are now midway through the rebuttal phase, we want to kindly follow up to ensure that our responses have adequately addressed your concerns. Your feedback is highly valued, and we still looking forward to further discussion to clarify or expand on any points as needed. Please feel free to share any additional thoughts or questions you might have.

Thank you once again for your time and effort in reviewing our paper.

Thank you for your rebuttal.

I have a few additional followups on your response:

Our framework permits nodes to access unique IDs, but this does not imply that models must use them.

Can you give an example of how a model without such features (or better yet with say 5 potential features/classes, think atom types, with number of nodes n >> 5) would be analysed in your framework?

We do not aim to design a specific GNN model with improved performance or expressiveness or to provide guidance for such future work. Rather, we hope our framework will assist future research by helping to avoid issues discussed in Section 3 and encouraging a re-evaluation of common assumptions in GNN expressiveness studies.

I never asked for any state of the art results. What I meant, similar to the comment above, is that it would be helpful if the paper would actually use RL-CONGEST to analyse a few different popular existing GNN architectures. To show how it's done and that RL-CONGEST can provide a meaningful differentiation between different GNN approaches, that was not possible so far.

Dear Reviewer DTJH,

Thank you for your response. We would like to further clarify our ideas and address your concerns.

On the Usage of Unique IDs

First, let us state "unique IDs" more precisely: they refer to nodes being uniquely identifiable, such as through distinct features.

Second, our intended meaning can be formally described as follows: when analyzing GNN expressiveness from an algorithmic alignment perspective using the RL-CONGEST model, the RL-CONGEST model requires unique IDs solely to identify nodes and compare whether two nodes are distinct, as in traditional graph algorithms. The model does not rely on the concrete values of the IDs, as these values are typically arbitrary and carry no intrinsic meaning.

In our paper, in line with related works, we primarily focus on the algorithmic tasks that GNNs can perform rather than downstream tasks, so we provide an example of constructing an RL-CONGEST model (or equivalently, a distributed algorithm) to solve the edge-biconnectivity problem. This algorithm is designed by Pritchard [Pritchard, 2006]. For further details, we encourage reviewers to consult Pritchard's slides (http://ints.io/daveagp/research/2006/ac-bicon.pdf), which include visual aids and proofs of correctness.

Steps:

1. Build a spanning tree $T$ with the FLOOD algorithm rooted at node $0$ (Since nodes have unique features and are distinguishable, we can "rename" them as $\\{0, 1, \cdots, n-1\\}$ for the description):
2. Compute the number of descendants on $T$:
   • Step 2.1: The root node $0$ sends a message to its children: "Compute the number of descendants". This message propagates down the tree.
   • Step 2.2: Leaf nodes determine their size as $1$ (since each node is its own descendant) and report this value to their parent. Internal nodes wait for responses from all their children, sum the values, add $1$ for themselves, and report the total to their parent.
3. Preorder (i.e., the label of a vertex is smaller than the label of each of its children) the nodes:
   • Step 3.1: The root assigns itself label $1$.
   • Step 3.2: When node $v$ assigns itself label $x$, it determines labels for its children $c_1, c_2, \cdots$ in some arbitrary order. For child $c_i$, the label is computed as: \ell_i = x + 1 + \sum_{j < i} \\#\text{desc}(c_j).
4. Marking cycles (from this step, we refer to nodes by its preorder label.):
   • Step 4.1: For a given non-tree edge $(u, v)$, a message $M[u, v]$ is sent along the edge in both directions: "If you are an ancestor of both $u$ and $v$, ignore this message. Otherwise, pass the message to your parent and mark the edge connecting you to your parent". A node $w$ checks the ancestry condition by verifying if \\{u, v\\} \subseteq \\{w, w + 1, \ldots, w + \\#\text{desc}(w) - 1\\}.
   • Step 4.2: Each node tracks the cumulative $\min u_i$ and $\max v_i$ of all $M[u_i, v_i]$ messages received.
   • Step 4.3: Even if $v$ determines that its edge to its parent should not be marked, it sends a token message to its parent.
   • Step 4.4: Once $v$ has received all non-to-parent edge messages, it sends a message to its parent.

After completing phases 1–4, the non-marked edges are bridges.

Using RL-CONGEST to Analyze Existing Models

Theorem 2 and Theorems 6-8 correspond to existing GNN models. Since we analyze the expressiveness of GNNs from an algorithmic alignment perspective, our results focus on the models' ability to solve algorithmic tasks rather than traditional node classification or link prediction tasks. Therefore, at this initial stage of using the RL-CONGEST analysis framework, we do not have results for models designed specifically for downstream tasks, such as GCN and GAT. Instead, our results focus exclusively on models proposed in GNN expressiveness studies. The findings are summarized in the table below.

Reference:

[Pritchard, 2006] David Pritchard. An Optimal Distributed Edge-Biconnectivity Algorithm. arXiv 2006.

Thank you for your further clarification and the model comparison.

From your answer about unique IDs, it stands to reason that models must have access to IDs and use them for the theory to hold. As pretty much all algorithms in distributed computing as you say, rely on nodes knowing which node sent which message (same in your example). Which contradicts your previous statement.

With the not-fully unique node example I was asking about, I was also interested again, in how your thery meshes with real world scenarios. In the paper you claim that features make the nodes uniquely identifyiable in most real tasks, but as far as I can see its at best possible not to an abosolute degree (partial idetifiability). So I was wondering if your theory can deal with that. Your answer doesn't really help in this regard.

I also looked at your discussion with the other reviewers who also largely expressed doubts. Thus I will keep my score.

W3:

Yes, the CONGEST model can still serve as an upper bound for computational capacity. Our point is that selecting the unrestricted CONGEST model as the computational model for GNNs would yield impractical outcomes, such as $O(m)$-depth GNNs that could theoretically solve $\mathsf{NP}$-$\mathsf{complete}$ problems on connected graphs (we appreciate your feedback on Theorem 4 and have now corrected this condition in red color, Lines 323). In reality, we cannot expect a polynomial-sized neural network to solve $\mathsf{NP}$-$\mathsf{complete}$ problems without error (unless $\mathsf{P} = \mathsf{NP}$). This misalignment results from overly strong assumptions about nodes' computational power. Our intention is to introduce flexible constraints on the computational resources class $\mathsf{C}$ to derive independent results, as is discussed in Lines 381-389. For instance, by setting $\mathsf{C}$ to a class reflecting MLPs, such as $\mathsf{TC}^0$, the resulting model would resemble "real-world" GNNs with MLPs as update functions. Alternatively, if nodes' update functions used transformer-based LLM agents enhanced by Chain-of-Thought (CoT) reasoning, which are claimed to solve problems in $\mathsf{P}$ [Merrill et al., 2024; Li et al., 2024], we could set $\mathsf{C} = \mathsf{P}$ and derive new theoretical results based on this adjustment. We hope our framework can inspire future research on graph agents, and have added it in red color in the revised PDF (Lines 384-387). As discussed in Lines 381-389, adjusting $\mathsf{C}$ in different ways may yield diverse outcomes. Thus, our RL-CONGEST framework serves as a "framework scheme" or "framework template".

W4:

As noted in the first open problem in Section 5, deriving general resource-round tradeoffs for the RL-CONGEST model is challenging, and we leave this problem for future work.

We also believe your statement "GNNs are usually implemented with fixed-size networks that run in constant time" may not be accurate, as a node $v$'s aggregation function takes at least $\Omega(d(v))$ time. Moreover, studies aligning GNNs' expressiveness with the WL test assume that MLPs can execute $\mathsf{HASH}$ functions for node recoloring --- an assumption whose practicality is also debatable. Your question supports our idea that WL tests may not be as straightforward as prior studies suggest, which aligns with our findings in Theorem 5. Regarding concerns about our framework's practicality, Theorems 5-8 illustrate our RL-CONGEST model's application in analyzing the unreasonableness of certain assumptions in previous studies. We invite you to kindly review these examples.

Q1:

Please note that our paper aims to conduct a theoretical analysis that identifies issues in existing studies on the expressive power of GNNs and to propose a new framework that avoids these issues. We do not intend to design a specific GNN model with improved performance or expressiveness, nor to offer guidance for future work directed toward these goals.

Q2:

As mentioned in our response to W3, we do not treat our entire framework, including the RL-CONGEST model with preprocessing and postprocessing, as a "benchmark model". Rather, it functions as a "framework scheme" or "framework template". We hope our framework will assist future research on GNN expressiveness by helping to avoid issues discussed in Section 3 and encouraging a re-evaluation of the validity of common assumptions in the field.

Q3:

We believe this point is addressed in Lines 381-389, and we reiterate it in our response to W3. Adjusting $\mathsf{C}$ in different ways may lead to varied outcomes. For example, setting $\mathsf{C} = \mathsf{R}$ (recursive languages, which Turing machines can decide) and network width $w = O(1)$ turns our RL-CONGEST model into the CONGEST model. Thus, the RL-CONGEST model can be seen as a generalization of the standard CONGEST model, allowing flexible settings on the computational resource class $\mathsf{C}$.

Q4:

As discussed in our response to W3, there is no universally "appropriate" complexity class for all GNN researchers. Researchers focused on current MPGNNs with MLP-based update functions might set $\mathsf{C} = \mathsf{TC}^0$ or $\mathsf{AC}^0$ to derive their theoretical results, while those interested in graph agents could set $\mathsf{C} = \mathsf{P}$. By setting $\mathsf{C} = \mathsf{R}$, our model also connects to CONGEST algorithms, so results proposed by Loukas [Loukas, 2020] are special cases within our RL-CONGEST framework.

Thank you again for your detailed feedback. We hope our response addresses your concerns and questions to some extent, and we look forward to further discussions with you.

Dear Reviewer YAM3,

We are very grateful for your detailed feedback and appreciate the opportunity to address some misunderstandings.

W1:

Yes, we use two examples to demonstrate that preprocessing complexity is often underestimated in the literature. Please note that the GD-WL paper [Zhang et al., 2023] was awarded Outstanding Paper at ICLR 2023. We chose this work as it is representative enough: its recognition by the community underscores that even well-regarded papers can exhibit this "underestimated preprocessing complexity" issue, making it a persuasive example to support our claim. However, we have also identified other examples, such as [Thiede et al., 2021, Bouritsas et al., 2022], which use hand-crafted features by recognizing subgraphs. The theoretical analysis also suggests that the proposed model achieves full expressiveness only when the subgraph is unrestricted, which is the same as [Wollschlager et al., 2024]. We have added them in Section 3.1 in red (Lines 212-216 in the revised PDF). Listing every example exhaustively is infeasible, so we have selected a recent example from ICML'24 [Wollschlager et al., 2024] and the notable ICLR'23 outstanding paper [Zhang et al., 2023] to substantiate our point in Section 3.1.

Additionally, we respectfully disagree with "computational complexity might just not be the main focus".

• First, for [Zhang et al., 2023] (and similar works), the authors show the model's expressiveness by assessing its capability in performing algorithmic tasks, making time complexity crucial in evaluating their results.
• Second, while the authors discuss preprocessing time complexity (as noted in Lines 223-230), their GD-WL framework requires $O(\min\\{mn, n^{\omega}\\})$ time to precompute all-pair resistance distances (RDs), though the target algorithmic task --- determining biconnectivity -- only requires $O(m)$ time. Additionally, as stated in our Theorem 2, RDs can directly imply edge biconnectivity; thus, the message-passing phase is actually unnecessary for this task in GD-WL framework when RDs are precomputed. We argue that overlooking the comparison between preprocessing time and the task's time complexity leads to questionable conclusions.
• Third, we also found that a CONGEST model proposed by [Pritchard, 2006] can solve the edge biconnectivity problem in $O(D)$ rounds (we add this in Lines 311-313 in red color). [Loukas, 2020] further suggests that the CONGEST model can handle many algorithms. These findings highlight that with unique IDs, MPGNNs might indeed solve the biconnectivity problem, supporting our view and challenging studies that rely on WL tests --- which they deem "weak" --- to define MPGNN expressiveness.

W2:

Thank you for your suggestion on clarifying this mismatch. Your review aligns with our discussion in the paper. Our main argument is that while existing works claim the proposed models' expressiveness advantage by proving they can perform tasks beyond the WL test's scope, this approach is questionable. The previous works' equating anonymous WL with MPGNNs is not entirely reasonable, and thus concluding that MPGNNs are weak because WL test is weak is also debatable. In fact, MPGNNs can perform certain algorithms (such as solving edge biconnectivity in $O(D)$ rounds within the CONGEST model [Pritchard, 2006], Lines 311-313). The logical flow of Section 3.2 is as follows:

1. The claim that the vanilla WL test has limited expressive power is true, as discussed in Figure 2. However, real-world graphs often contain rich features, and [Loukas, 2020] demonstrated that with unique IDs (and other assumptions), MPGNNs (Loukas used CONGEST to characterize) can perform a wide range of algorithmic tasks. Thus, using the anonymous WL test to characterize MPGNNs is debatable.
2. To address MPGNNs' "limited" expressiveness (stemming from the vanilla WL test's limitations, as many works use the WL test to characterize GNNs), some studies, such as [Zhang et al., 2023], incorporate additional features to enhance model expressiveness. Nonetheless, as outlined in (1), using the anonymous WL test as a characterization of MPGNNs is questionable. Consequently, demonstrating a model's expressiveness by proving it can perform tasks beyond the WL test's capabilities may not be entirely valid.
3. A more reasonable approach would be to compare these models to MPGNNs in a non-anonymous setting, as suggested in [Loukas, 2020]. Furthermore, evidence from [Suomela, 2013; den Berg et al., 2018; You et al., 2021; Abbound et al., 2021; Sato et al., 2021] indicates that the non-anonymous setting can enhance expressiveness, again highlighting the mismatch when works argue for "weak MPGNNs" but use additional features, breaking the WL test's anonymous setting to enhance expressiveness.

We have revised the introduction in Section 3.2 (Lines 253-258) and highlighted the changes in red to clarify our points more effectively.

Dear Reviewer YAM3,

Thank you for engaging in further discussion with us. We will begin by addressing your concerns regarding our case study, followed by a discussion of your other concerns.

Regarding Zhang et al.'s Paper as a Case Study

While the total runtime of GNNs for solving an algorithmic task does not necessarily need to outperform classical algorithms, this is not the focus of our argument. Instead, we emphasize that researchers need to be careful when the preprocessing time for features or graphs exceeds the algorithmic task's time complexity. If it happens, the theoretical results may become questionable, as the precomputed features may directly solve the task, rendering the GNNs less relevant. In such cases, attributing the results to GNN expressiveness might not be entirely appropriate.

Take Zhang et al.'s paper as an example. In our Theorem 2, we demonstrate that $R(u, v) = 1$ is equivalent to the edge $(u, v)$ being a cut edge, and hence $G$ is not edge-biconnected. For the edge-biconnectivity task, the precomputed features (RDs) directly provide the solution, which reduces the role of message-passing to unnecessary redundancy. As such, this result highlights the expressiveness of the precomputed features rather than that of the GNN itself.

To illustrate further, consider a binary classification task $\mathcal{X} \to Y = \\{0, 1\\}$, where the preprocessing $\mathcal{X} \to Z = \\{-1, 1\\}$ generates a binary feature $Z_v \in \\{-1, 1\\}$ for each sample $v$, such that $Z_v = -1$ iff $Y_v = 1$, and $Z_v = 1$ iff $Y_v = 0$. A simple model, such as an MLP or linear SVM, could easily solve the task using $Z_v$ as features. Does this suggest the model itself is expressive? We believe the answer is "No". It only shows "feature expressiveness" or "preprocessing expressiveness" rather than "model expressiveness". It is the preprocessing step, not the model, that contributes the expressiveness. Similarly, in Zhang et al.'s work, the RDs alone suffice to solve edge-biconnectivity (Theorem 2), and message-passing adds no significant value. Moreover, the preprocessing time is substantially higher than the direct complexity of solving the problem algorithmically. (A more reasonable approach for this problem can be found in Lines 312-313, where, with unique IDs, the CONGEST model solves the problem in $O(D)$ rounds without costly preprocessing such as computing RDs.)

We believe that disregarding preprocessing time relative to the algorithmic task's time complexity can lead to problematic interpretations. For another instance, consider using GNNs to solve $\mathsf{NP}$-$\mathsf{Complete}$ problems such as $\mathsf{MIN}$-$\mathsf{VERTEX}$-$\mathsf{COVER}$ or $\mathsf{HAMILTON}$-$\mathsf{CYCLE}$. Without constraints on preprocessing, the answers could be computed as binary features (e.g., whether each node is in the vertex cover or each edge is in the cycle) using classical algorithms. This would enable a trivial one-layer GNN (or even a single neuron) to "solve" NP-complete problems with these precomputed features, creating a very absurd conclusion of the model's expressiveness.

We hope this clarification helps to clarify why we emphasize the importance of researchers exercising caution when the preprocessing time (not total running time) exceeds the algorithmic task’s time complexity.

We then address your other concerns as follows:

1. About Specific Applications

We have already demonstrated some initial results using our RL-CONGEST framework, as shown in Theorems 5-8. We kindly invite you to review these results. Please note that our exploration of this framework is in its early stages, and there is significant potential for future work, as outlined in Section 5.

2. How Our RL-CONGEST Framework Addresses the "Underestimated Preprocessing Time Complexity" Issue

The main point is the importance of carefully analyzing the relationship between preprocessing time complexity and the time complexity of the chosen algorithmic task to correctly evaluate a model's expressiveness. If the preprocessing time is less than or comparable to the algorithmic task's time, there are no inherent issues. However, if the preprocessing time significantly exceeds the algorithmic task's time, it becomes crucial to analyze whether the resulting features or graphs can directly imply the solution to the algorithmic task, as in the discussions above. If this is the case, the subsequent GNN model and message-passing steps are unnecessary. In such scenarios, it is more appropriate to attribute the success to "feature expressiveness" or feature engineering rather than GNN expressiveness, as the message-passing component becomes redundant.

Dear Reviewer YAM3,

It seems that there are two key points where we may not yet have reached a consensus, and we would like to further clarify our perspective.

On "node IDs" and "non-anonymity":

These terms refer to distinct features that allow nodes to be distinguishable (e.g., $[n] = \\{0, 1, \cdots, n - 1\\}$ would also suffice).

We have updated our PDF, replacing "anonymous" with "identical-feature" and "non-anonymous" with "distinct-feature" or "unique-feature" to make these concepts clearer and more accessible to readers. The modifications are highlighted in magenta, and we invite you to review them.

The distinct-feature setting is commonly applied in almost all existing models, as listed below:

1. LINKX [Lim et al., 2021]:

LINKX uses:

• $\mathbf{H}^{(\mathbf{A})} = \mathrm{MLP}_{\mathbf{A}}(\mathbf{A})$
• $\mathbf{H}^{(\mathbf{X})} = \mathrm{MLP}_{\mathbf{X}}(\mathbf{X})$
• $\mathbf{Y} = \mathrm{MLP}(\sigma(\mathbf{W}[\mathbf{H}^{(\mathbf{A})}; \mathbf{H}^{(\mathbf{X})}] + \mathbf{H}^{(\mathbf{A})} + \mathbf{H}^{(\mathbf{X})}))$

The $\mathbf{H}^{(\mathbf{A})}$ term can be reformulated as $\mathrm{MLP}'(\sigma(\mathbf{A} \cdot \mathbf{I} \cdot \mathbf{W}))$, which uses the identity matrix (unique node features).

2. GCN, GAT, and other models which can be applied to real-world datasets:

These models use real-world node features which are unique and distinguishable with high probability. Actually, all models that are applicable to real-world datasets fall into this category.

3. GNN expressiveness works (e.g., [Loukas, 2020; Sato et al., 2021]):

These works use random features, which are unique with high probability. For example, assigning each node a feature randomly chosen from $[n^4]$ would result in distinct features with high probability.

4. GD-WL framework: In the GD-WL framework by Zhang et al., resistance distances $R(s, t)$ are used as features. Since $R(s, t) = 0$ iff $s = t$, each row of the resistance distance matrix is unique, creating distinguishable node features.

Actually, according to our theory, they are all capable of solving the biconnectivity problem using the unique features.

We have also updated our PDF to include the above discussions in Section 3.2, highlighted in magenta.

On whether unique features break equivariance or invariance:

Unique features do not break permutation equivariance or invariance. Instead, it is the properties of the update functions and pooling layers that determine whether a GNN model is equivariant or invariant. For example, in LINKX, when performing node classification, $\mathrm{MLP}(\mathbf{A})$ ensures permutation equivariance. To achieve permutation invariance for graph classification, we only need to add a permutation-invariant pooling layer after this step.

Similarly, consider Dijkstra's single-source shortest path algorithm. Unique IDs are used solely to determine whether the shortest path to a node has been found. The resulting shortest path distance vector is always permutation equivariant. This demonstrates that it is not the presence of unique IDs but rather the design of the update function that determines whether a GNN model is permutation equivariant or invariant.

We hope these clarifications address your concerns and further illustrate the flexibility of our framework. Thank you again for your feedback.

Reference:

[Lim et al., 2021]. Large Scale Learning on Non-Homophilous Graphs: New Benchmarks and Strong Simple Methods. NeurIPS 2021.

[Sato et al., 2021] Ryoma Sato, Makoto Yamada, and Hisashi Kashima. Random Features Strengthen Graph Neural Networks. SDM 2021.

Dear Reviewer ftna,

Thank you for your time and effort in reviewing our paper. We would like to address your concerns and questions as follows:

W1, W2, and Q1:

Thank you for these suggestions. Please note that our primary goal is to conduct a theoretical analysis to highlight issues in existing studies on the expressive power of GNNs and to propose a new analytical framework that avoids these issues. Our intention is not to design a specific GNN model with improved performance or expressiveness, nor to provide guidance for future work aimed at doing so.

Q2:

Yes, we believe the answer is affirmative. As discussed in Section 3.1 (Lines 201-209 in the revised PDF) of our paper, many GNNs conform to the "preprocessing-then-message-passing" framework. From a practical standpoint, mainstream GNN libraries, such as PyG (torch-geometric), implement GNNs with a "MessagePassing" base class, meaning that models built with these libraries naturally align with this framework. High-order GNNs, subgraph GNNs, and GNNs with additional features can also be implemented in these libraries by first constructing the $k$-WL graphs, subgraphs, or graphs with additional features, followed by message-passing operations, thereby fitting into the "preprocessing-then-message-passing" framework. As a result, we believe our analytical framework applies to the analysis of most GNNs.

Q3:

Yes, exactly. The resource limitation we consider reflects the constraints of real-world GNNs. Many GNNs use MLPs (or similar neural network models) as update functions, but these are far from Turing-complete, as required in condition (3) of Theorem 3 (Lines 308-310). For instance, we cannot expect an MLP of polynomial size to solve $\mathsf{NP}$-$\mathsf{complete}$ problems without error (unless $\mathsf{P} = \mathsf{NP}$). However, directly setting the resource limitation class $\mathsf{C}$ as a class specifically reflecting MLPs (e.g., $\mathsf{TC}^0$) would reduce flexibility, as future GNNs may adopt new architectures for update functions. Our framework remains adaptable by allowing adjustments to the class $\mathsf{C}$. For a hypothetical example, if we implemented the nodes' update functions with transformer-based LLM agents enhanced by Chain-of-Thought (CoT), which are claimed to solve problems within $\mathsf{P}$ [Merrill et al., 2024; Li et al., 2024], we could set $\mathsf{C} = \mathsf{P}$ and derive new theoretical results based on this adjustment. We hope that our analysis framework can also inspire future work on graph agents, and have added it in red color in the revised PDF (Lines 384-387). This point is already discussed in Lines 381-389 (of the revised PDF), adjusting $\mathsf{C}$ in different ways may lead to varied outcomes. In this way, our RL-CONGEST framework serves as a "framework scheme" or "framework template".

Q4:

As noted in our response to W1, W2, and Q1, our focus is on identifying issues in the existing analysis of GNN expressiveness and introducing a new framework for this analysis, rather than providing a guideline for future work to enhance expressiveness. The idea is that once researchers propose a new GNN model, they can analyze its expressive power using our framework, rather than using ad-hoc methods, which may have limitations as discussed in Section 3.

Q5:

Yes, we believe this is correct. We leave the exploration of specific tasks to future studies, and we also outline other open questions for further research in Section 5.

Thank you again for reviewing our paper. We hope this response clarifies our approach and addresses your questions. We look forward to any further discussions with you.

References:

[Merrill et al., 2024] William Merrill, and Ashish Sabharwal. The Expressive Power of Transformers with Chain of Thought. ICLR 2024.

[Li et al., 2024] Zhiyuan Li, Hong Liu, Denny Zhou, and Tengyu Ma. Chain of Thought Empowers Transformers to Solve Inherently Serial Problems. ICLR 2024.

Dear Reviewer ftna,

As we are now midway through the rebuttal phase, we want to kindly follow up to ensure that our responses have adequately addressed your concerns. Your feedback is highly valued, and we still looking forward to further discussion to clarify or expand on any points as needed. Please feel free to share any additional thoughts or questions you might have.

Thank you once again for your time and effort in reviewing our paper.