We thank the reviewer for their very valuable suggestions and questions that have helped us to improve our paper. We are pleased that you found our approach novel and liked our thorough theoretical analysis.

W3: Visual presentation

We appreciate your feedback on visual presentation, which is very important to us. The color schemes in our figures are specifically designed to visually compare MPC complexity values with empirical accuracy trends. With the higher page limit for the camera-ready version, we have extended figure captions to be more detailed and informative. We would be very happy to revise specific figures based on any additional feedback you might have to ensure maximum clarity.

Q1 & W1: Connection to over-smoothing

Over-smoothing is usually defined as the convergence of node representation to one global representation as the number of message passing layers increases with a progressive loss of initial node feature information [53,54]. This loss of individual node feature information is precisely what our retaining information task measures (Sec. 5): whether nodes can recover their initial features $f_v(G) = X_v$ after $L$ layers of message passing.

Our theoretical framework captures this phenomenon through the random walk connection. From Lemma 4.10, we can lower bound the complexity of information retention as: $\text{MPC}(f\_v,G) \ge -\log((I^L)\_{vv})$ where $(I^L)\_{vv}$ is the $L$-step random walk return probability. A high return probability indicates that the node retains its local information, resulting in low MPC complexity. Conversely, a low return probability indicates that information diffuses throughout the graph, leading to high complexity. The scaling of complexity with depth depends on how quickly the random walk approaches its stationary distribution. This is in line with established over-smoothing literature that shows a direct connection between the rate of over-smoothing and how fast random walks approach their stationary distribution [52,54].

Empirically, our results in Section 5 validate this connection: Standard MPNNs like GCN, known to be suffering from over-smoothing, show increasing MPC complexity with depth (at least linear growth per Lemma 5.1) and correspondingly lower empirical information retention abilities.

We have added these theoretical connections to Section 4.2 and have expanded the information retention paragraph in Section 5 to explicitly discuss how MPC captures over-smoothing through this task.

Q2 & W2: Comparison to other expressivity measures

Existing expressivity measures have fundamental limitations for measuring task difficulty that make meaningful comparison with MPC across tasks difficult:

Task-agnostic measures: Most expressivity frameworks characterize architectures through specific capabilities (e.g., substructure recognition [49], biconnectivity [50]) and provide only global architecture rankings independent of the task (see Sec. 7, App. A). For example, the substructure-based measure would rank: standard MPNNs = MPNNs+virtual node < GSN < FragNet/CIN. However, our empirical results show that performance varies significantly across tasks—GCN-VN excels at information propagation while CIN excels at ring transfer—contradicting any fixed ranking.

Binary characterizations: Logic-based expressivity measures [3,22] determine theoretical feasibility but, like our WLC baseline, offer only binary possible/impossible classifications. Since all our tasks are theoretically learnable by standard MPNNs, these measures cannot reveal/explain any performance differences between architectures or tasks.

Restrictive assumptions: The only other task-specific measure—based on maximal "mixing" [14] requires twice-differentiable tasks with continuous features independent of graph topology, assumptions that don't apply to our tasks. Moreover, it also provides only binary possible/impossible statements.

To our knowledge, MPC is the first framework with continuous difficulty quantification for arbitrary graph tasks, thereby flexibly capturing practical difficulties beyond theoretical feasibility.

We have made this very important comparison more clearly in our Related Work and Evaluation sections.

Q3: Real-world benchmarks

Yes, we have evaluated MPC on graphs from real-world benchmarks, specifically graphs from the ZINC dataset (>100,000 molecular graphs, Fig. 23) and the LRGB peptides benchmark (>15,000 larger peptide molecules, Fig. 17). MPC can be very efficiently simulated (< 1 minute on consumer CPUs, see App. D) on these datasets for the tasks we tested using the approach detailed in App. D.5.

Moreover, we have now added in Sec. 5 an additional experiment on the ogbn-products graph, one of the largest OGB datasets [55] (>2 million nodes, >60 million edges) where MPC can still be efficiently simulated (< 10 minutes for simulation compared to >15 hours of training GNNs). We evaluated the retaining information task using GCN with a varying number of layers, with MPC trends aligning with empirical performance:

Besides this, MPC also allows the derivation of complexity bounds that require no computation whatsoever (e.g., Lemma 5.1 - 5.3).

Q4: Different Aggregation/Update Functions

In its current formulation, MPC cannot differentiate between models with identical message passing graphs, as it abstracts from implementation details to isolate topological complexity (Sec. 6, App. B).

Rationale: While different update functions have distinct theoretical properties, the common choice of MLPs with sum aggregation can approximate any update function [56]. This suggests that for many tasks and models, message-passing topology may dominate difficulty over specific aggregation choices. Empirically, almost all of our experiments across diverse architectures (GCN, GIN, GraphSage, FragNet, CIN) show strong MPC-performance correlations despite different aggregation schemes, indicating our abstraction captures the primary complexity source for the tasks we tested.

Extension potential: MPC can incorporate aggregation-specific effects when needed. Currently, we assume uniform message loss probabilities $I_{uv}$ for messages to $v$, but these can be adapted—e.g., for GIN's emphasis on self-loops in the aggregation, we could set $I_{vv} > I_{wv}$ (for $w \neq v$).

While MPC currently abstracts from the choice of update function, it successfully isolates topological constraints that appear to be the dominant complexity source in our experiments. Our framework's flexibility allows for incorporating aggregation-specific effects when they significantly impact task complexity. We have expanded our discussion of this in the Limitations section.

Summary

We thank the reviewer for their detailed and very valuable review that has helped us improve our paper greatly by more clearly presenting the connection to over-smoothing (Sec. 4 & 5), adding an additional real-world benchmark (Sec. 5) and improving the comparison to other expressivity measures (Sec. 5 & 7).

Additional References

[52] Xu et al. Representation Learning on Graphs with Jumping Knowledge Networks. ICML 2018.

[53] Zhao et al. PairNorm: Tackling Oversmoothing in GNNs. ICRL 2020.

[54] Giraldo et al. On the Trade-off between Over-smoothing and Over-squashing in Deep Graph Neural Networks. CIKM 2023

[56] Zaheer et al. Deep sets. Neurips 2017.

We thank the reviewer for their thoughtful and detailed review, which has helped us improve our paper. We are very pleased that you appreciated our discussion of the limitations of iso expressivity and the theoretical as well as the empirical comparison to MPC.

1. Reliance on knowing task $f_v$

You raise an important point about dependency on knowing $f_v$. While we acknowledge this limitation (Sec. 6), MPC can provide valuable insights - even if we do not know the true task - through well-chosen proxy tasks:

1. Fundamental capabilities: Test universal MPNN requirements (information retention, propagation) that capture empirically relevant failure modes (over-smoothing, over-squashing) affecting real-world performance regardless of specific tasks.
2. Domain-informed proxy tasks: Use domain knowledge to identify key capabilities—e.g., ring identification for small molecule predictions, long-range propagation for proteins.

Empirical validation: We demonstrate on the ZINC benchmark that proxy task insights can translate to unknown target tasks. While the exact function for predicting penalized logP is unknown, domain knowledge indicates that identifying rings is crucial [42]. This suggests our ring-transfer task as a suitable proxy for the complicated unknown graph-level task. Indeed, our ring-transfer task yields MPC complexities on ZINC graphs (Fig. 22) that accurately match performance trends on the actual benchmark task:

Of course, no measure can capture the full complexity of unknown tasks. But unlike most existing measures limited to one specific capability, MPC enables analysis of arbitrary domain-relevant proxy tasks. In the experiment on the ZINC benchmark (that we have now included in Sec. 5), we have shown that insights from these proxy tasks can translate to the unknown task. MPC therefore narrows the theory-practice gap by flexibly focusing on capabilities that matter for specific applications.

2. Connection to other expressivity measures

Thank you for the pointer to line 123, we have now clarified in our revision that our statement about virtual nodes (line 123) refers specifically to iso expressivity. As you correctly note, virtual nodes can improve other expressivity measures while maintaining identical WL expressivity. We now highlight this explicitly in the theoretical discussion of the information propagation task in Sec. 5.

Additionally, we have expanded our discussion of non-iso expressivity measures in Sec. 7, particularly the connection to Di Giovanni et al. [14]:

Expanded related work on expressivity measures in Sec. 7:

Beyond iso expressivity, several other frameworks characterize MPNN expressivity through specific capabilities. Wang et al. [52] analyze spectral MPNNs through their ability to learn polynomial filters. Zhang et al. [49] rank architectures by the set of substructures they can recognize, while Zhang et al. [50] compare models through their ability to solve the graph biconnectivity problem. Another line of research characterizes learnable functions through fragments of first-order logic [3, 22], offering a more nuanced understanding by considering the effects of different activation functions [28]. However, these expressivity characterizations share key limitations with iso expressivity: they remain binary (can/cannot solve) and assume lossless information propagation, limiting their insights for real-world MPNNs. For a more in-depth comparison, we refer the reader to App. A.

Most relevant to our approach is the work by Di Giovanni et al. [14], which derives expressivity limitations from over-squashing theory. They show tasks become impossible when the required "mixing" between nodes (measured via maximal Hessian entries) exceeds what MPNNs with smooth activations can generate. Like MPC, this can capture practical impossibilities arising from over-squashing. However, their framework considers only pairwise interactions with restrictive assumptions on the task (twice differentiable tasks, not dependent on graph topology). In contrast, MPC applies to arbitrary graph tasks, captures difficulties beyond pairwise interactions (e.g., substructure identification, over-smoothing), subsumes impossibility results from iso expressivity, and is empirically validated across diverse tasks.

3. Impact of MPC on the future of graph learning research

Lastly, we address your two key questions about MPC's practical impact:

Q1: Better alignment between theory and practice

How can MPC be used to align expressivity to accuracy on real-world tasks?

MPC is specifically designed to better align with empirical performance (Sec. 3 & 4) by:

• Capturing practical limitations arising from the lossy information propagation of real-world MPNNs (e.g., over-smoothing, over-squashing)
• Providing a continuous difficulty measure rather than binary possible/impossible statements
• Flexibly considering arbitrary tasks relevant to the domain instead of focusing on one fixed task.

Our empirical evaluation in Section 5 validates this: across 8 architectures, we demonstrate strong correlation between MPC complexity and performance of trained MPNNs on fundamental tasks covering common failure modes.

Moreover, our ZINC benchmark analysis (see Point 1) shows that even when the true target functions are unknown or too complex to evaluate, MPC insights from domain-informed proxies can successfully predict real-world performance trends.

While we, of course, cannot completely close the gap between theory and practice, we can at least narrow it.

Q2: Role of MPC for developing new architectures

How can MPC be used to improve models and how would this differ from reducing the commute time?

First, we show how MPC can help the theoretical analysis/design of future MPNNs, and then we give concrete practical examples of potential architectural modification guided by MPC.

Theoretical contributions on future architectural design

A first and important contribution of our work is clearly identifying all the limitations of the pre-dominant iso expressivity framework. We hope that this already will shift attention in future model design toward problems that more meaningfully constrain practical performance.

Second, MPC enables a more fine-grained theoretical analysis. For example, MPC can reveal when architectures theoretically capable of solving a task will struggle in practice due to high complexity, making previously hidden problems visible to researchers. For instance, we showed poor complexity scaling for recent higher-order MPNNs on the propagating information task.

Third, rather than seeking universally "best" models, MPC recognizes that graph tasks have diverse requirements. By analyzing complexity for specific capabilities (e.g., substructure identification), researchers can precisely optimize architectures for domain-specific needs rather than generic expressivity maximization.

Concrete examples of how MPC can guide model improvement for specific capabilities needed in certain domains:

• Multi-node aggregation: Many tasks require aggregated information from groups of related nodes (e.g., identifying ring types in molecules, transaction analysis in relational learning [54]). MPC analysis suggests introducing dedicated hub nodes that consolidate information within each group (e.g., all nodes in a transaction or ring). This reduces MPC complexity by replacing many individual messages with a single message from hub to target node. This principle (partly) explains the empirical success of molecular architectures like HIMP [53] which introduce higher-order nodes for rings and junctions. Future research could apply this principle to other domains (e.g., relational deep learning) to reduce MPC complexity.
• Substructure identification tasks: MPC complexity bounds (Lemma 5.3) reveal that even simple ring detection is very complex and scales at least linearly with ring size, indicating that architectural modifications alone may be insufficient for learning complex substructures, even when theoretically possible. This MPC insight suggests that expressive positional encodings or preprocessing steps (as used by FragNet [42] or CIN [6]) that directly reduce task complexity may be more effective than purely architectural approaches, highlighting a promising research direction.

Comparison to commute time: Commute time approaches [14] are limited to pairwise interactions, while MPC can quantify the difficulty of arbitrary tasks that often require coordinated information from multiple nodes (as expected in many real-world tasks and demonstrated by our multi-node aggregation and substructure identification examples). Moreover, MPC provides impossibility statements by subsuming iso expressivity results (Lemma C.3), offering a more unified theoretical framework.

We have now included a discussion of the concrete ways in which MPC can benefit future MPNN design in Sec. 6.

Summary

We thank the reviewer for the very helpful review that helped us improve our manuscript greatly by 1) comparing MPC more clearly to existing measures in Sec. 7 and 2) more concretely demonstrating how the insights of MPC can capture real-world tasks and guide future model design in Sec. 5.

Additional References

[52] Wang et al. How powerful are spectral graph neural networks. ICML 2022.

[53] Fey et al. Hierarchical Inter-Message Passing for Learning on Molecular Graphs. arXiv:2006.12179

[54] Fey et al. Relational Deep Learning: Graph Representation Learning on Relational Databases. arXiv:2312.04615.

We thank the reviewer for their thoughtful review and valuable suggestions for extending MPC. We are particularly pleased that you found our work successfully bridges the gap between idealized expressivity theory and the practical performance of GNNs.

While our work focuses on establishing MPC in static graphs with general-purpose MPNNs, we want to address your specific concerns about broader applicability. Below, we describe how MPC's framework can extend to the settings you mentioned (demonstrating its flexibility), along with some first empirical evidence.

Weakness 1: 3D GNNs

While our work focuses on general purpose MPNNs (covering 8 different standard, higher-order, and topological architectures across multiple tasks), MPC can also capture 3D GNNs through appropriate message passing graph transformations, defined in our general framework (App. B).

To illustrate this, consider DimeNet [1]: This architecture maintains representations for all directed edges and incorporates angular information. In our framework, this can be captured by using the directed line graph $G'=(V',E')$ of the original graph $G$ as the message passing graph, where $V'=E$ (the original edges become nodes) and for any $e_1 = (v_j, v_k), e_2 = (v_k, v_i) \in E$, we have $((v_j, v_k), (v_k, v_i)) \in E'$. The angular and distance features can be incorporated as edge/node features in this transformed message passing graph.

This highlights the flexibility of MPC to capture new architectures. We have added the complete MP graph definition for DimeNet to our general framework in App. B and added a paragraph on the potential of studying the complexities of 3D GNNs to our future work section.

Weakness 2: Large-scale Benchmarks

First, we note that we already evaluated MPC on graphs from large real-world datasets: the ZINC dataset (>100,000 molecular graphs, Fig. 23) and the LRGB peptides benchmark (>15.000 larger peptide molecules, Fig. 17). As described in App. D.1, MPC can be simulated in <10 seconds for our considered tasks on these graphs and has linear complexity in the number of nodes and edges reachable from v. Additionally, MPC enables derivation of theoretical bounds (e.g., Lemma 5.1-5.3) requiring no computation, providing architectural insights without any expensive training.

To directly address scalability concerns, we conducted additional experiments on ogbn-products [3], one of the largest OGB datasets (>2 million nodes, >60 million edges). We evaluated the retaining information task using GCN with a varying number of layers:

Key observations:

• MPC trends match trends in empirical performance.
• GCN training required >15 hours on A100 GPUs while MPC simulation required <10 minutes on consumer CPU (using approach in App. D.5).

This demonstrates that MPC maintains both its predictive power and computational advantages for this large-scale dataset. We have included this additional experiment in Sec. 5 and thank the reviewer for this suggestion, which has strengthened our manuscript.

Question 1: Missing features

While our current work specifically focuses on isolating message-passing complexity from other sources, the probabilistic foundation of MPC offers potential for extension to additional complexity sources like missing features.

We can extend MPC by modifying the initial step in Def. 4.3 to model feature availability: $\text{lossyWL}_v^0 = L_v \cdot X_v$ where $L_v \sim \text{Bernoulli}(p_v)$ represents the probability of feature availability.

For a first empirical demonstration, we conduct our information propagation experiment (D=5, GCN) with varying levels of missing node feature probabilities:

The results show that the adapted MPC accurately captures the increasing difficulty with feature loss in this initial experiment.

More broadly, this demonstrates the potential of our probabilistic formulation to extend to other complexity sources beyond message passing — something existing expressivity measures based on logic or WL tests cannot seamlessly accommodate. We have added a discussion of this extension to the future work section of our manuscript.

Question 2: Temporal Graphs

While our current work focuses on static graphs, MPC can be naturally extended to temporal graphs: MPC becomes time-dependent, i.e., $\text{MPC}_t(f_v, G)$, by performing our probabilistic WL test (lossyWL) on snapshot graphs $G^t$ as defined in [2].

For an empirical demonstration of this capability, we conducted an experiment on random dynamic graphs where edges are added progressively (p=0.06 per timestep), modeling the densification common in real-world networks (e.g., social interactions, biological systems). We evaluated MPC for a 4-layer GCN on the retaining information task:

Key observations:

• MPC correctly captures the decreasing empirical accuracy as graphs densify over time
• Thereby, MPC quantifies how structural evolution over time affects task difficulty

This demonstrates MPC's adaptability to temporal settings and opens interesting research directions for understanding GNN behavior in dynamic environments. We have added this extension of MPC to the future work section of our manuscript.

Summary

We thank the reviewer again for their valuable suggestions. They demonstrate the flexibility of our probabilistic MPC formulation and its potential for extensions beyond standard graph learning settings, and have greatly improved our manuscript.

[1] Gasteiger et al. Directional Message Passing for Molecular Graphs. ICLR 2020.

[2] Longa et al. Graph Neural Networks for temporal graphs: State of the art, open challenges, and opportunities. arXiv:2302.01018

[3] Hu et al. Open Graph Benchmark: Datasets for Machine Learning on Graphs. Neurips 2020.

We thank the reviewer for the question and clarification. You are right - we only showed the extension to missing features. While our focus is to isolate the difficulty arising from the message passing process (Sec. 4), we can also extend our framework to include complexity arising from noise.

Extension to noisy features: Very similar to how feature loss can be incorporated into our framework, we can also incorporate noisy features. In general, let $X_v$ be the true feature of node $v$, and let $\tilde{X}_v$ be the observed noisy feature according to some noise distribution $\tilde{X}_v \sim N_v(X_v)$.

We modify the initial step in Definition 4.3 to incorporate noise: $\text{lossyWL}_v^0 = \tilde{X}_v$ where $\tilde{X}_v \sim N_v(X_v)$. Notice that this approach subsumes feature loss as a special case.

Empirical demonstration: Similar to our feature loss experiment, we conducted an initial experiment on the information propagation task ($D=4$, GCN) with noisy features. For our categorical features (with $k$ classes), we consider a noise distribution where $\mathbb{P}[\tilde{X}\_v = c] = 1-p\_{\text{noise}}$ for $c = X_v$ and $\mathbb{P}[\tilde{X}_v = c] = p\_{\text{noise}}/(k-1)$ for $c \neq X\_v$. This models uniform noise on discrete node features.

The results show that MPC successfully captures the increasing task difficulty as feature noise increases, with performance degrading correspondingly.

Broader significance: This demonstrates an advantage of our probabilistic framework—it can flexibly incorporate various sources of complexity beyond the difficulty arising from message passing, including both missing and noisy features. To our knowledge, no other graph expressivity framework studies these sources of difficulty or can seamlessly accommodate them.

We have modified our future work discussion to include this general approach to include feature noise and thank the reviewer for this valuable suggestion that highlights MPC's broader applicability to real-world scenarios.

We thank the reviewer for their thorough review of our work. We are particularly happy that you found that our discussion of the limitations of WL-based expressivity is convincing and that the insights of MPC provide a better understanding of message passing.

1. Complexity in computing MPC

First, note that for our evaluated tasks, MPC can be efficiently simulated using the approach detailed in App. D. However, we acknowledge that computing exact MPC values can become challenging for sophisticated tasks (see our discussion in Sec. 6).

Practical solutions: We address this limitation through two complementary approaches:

1. Proxy task analysis: Focus on fundamental capabilities required across domains (e.g., information retention, propagation) or domain-specific operations informed by the true task or prior knowledge (e.g., ring identification for molecular tasks). Our results (see Answer to Reviewer 46h7) show that these proxy insights can translate to real-world performance trends even on sophisticated tasks.
2. Theoretical bounds: Even when exact computation is infeasible, complexity bounds (Lemmas 5.1-5.3) can provide sufficient insight to capture empirical performance trends (Sec. 5) requiring no computation at all.

In summary, exact MPC computation faces limitations for sophisticated tasks—as one would expect for any practical complexity measure. However, our framework still provides valuable task-specific architectural insights through proxy analysis and theoretical bounds that do capture practical performance trends—insights that binary expressivity measures cannot offer.

2. MPC for future architecture design

First, we show how MPC can help the theoretical analysis/design of future MPNNs, and then we give concrete practical examples of potential architectural modification guided by MPC.

Theoretical Contributions on future architectural design

• By clearly identifying the limitations of iso expressivity, we shift attention in future model design from iso expressivity maximization towards problems that more meaningfully constrain practical performance (e.g. lossiness of message passing).
• MPC enables a more fine-grained theoretical analysis that enables uncovering previously hidden problems (e.g., high complexity scaling for substructure identification, bottlenecks in long-range propagation) and allows a more nuanced comparison of models.
• By analyzing complexity for specific tasks (e.g., substructure identification), researchers can precisely optimize architectures for domain-specific needs rather than generic expressivity maximization (see also Point 3).

Concrete examples of how MPC can guide model improvement for specific capabilities needed in certain domains:

• Multi-node aggregation: Many tasks require aggregated information from groups of related nodes (e.g., identifying ring types in molecules, transaction analysis in relational learning [4]). MPC analysis suggests introducing dedicated hub nodes that consolidate information within each group (e.g., all nodes in a transaction or ring). This reduces MPC complexity by replacing many individual messages with a single message from hub to target node. This principle (partly) explains the empirical success of molecular architectures like HIMP [1] which introduce higher-order nodes for rings and junctions. Future research could apply this principle to other domains (e.g., relational deep learning) to reduce MPC complexity.
• Substructure identification tasks: MPC complexity bounds (Lemma 5.3) reveal that even simple ring detection is very complex and scales at least linearly with ring size, indicating that architectural modifications alone may be insufficient for learning complex substructures, even when theoretically possible. This MPC insight suggests that expressive positional encodings or preprocessing steps (as used by FragNet [2] or CIN [3]) that directly reduce task complexity may be more effective than purely architectural approaches, highlighting a promising research direction.

We have included a discussion of the concrete ways in which MPC can benefit future MPNN design in Sec. 6.

3. Ranking of MPNNs

While many existing expressivity works rank architectures globally based on one specific binary measure (e.g., distinguishing non-isomorphism graphs, identifying substructures), a key result of our work is that architecture performance varies significantly across tasks: Our evaluation shows no single architecture dominates across all tasks. For example, GCN-VN performs best for information propagation while FragNet/CIN excel at ring transfer.

Therefore, we provide task-specific complexity comparisons (e.g., Lemmas 5.1 - 5.3) rather than universal rankings:

• Ring Transfer task: FragNet/CIN < GSN < standard MPNNs (with/without virtual node)
• Information propagation task: GCN-VN < all other

These complexity rankings align very well with trends in empirical performance for these individual tasks: Lower MPC complexity correlates with better empirical performance, explaining the superior performance of the respective models in the respective tasks (Sec. 5).

In summary, the task-specific formulation of MPC enables a more fine-grained and application-specific architecture comparison than universal rankings.

Summary

We thank the reviewer for the thoughtful review. It helped improve our manuscript greatly by clarifying how MPC can guide future model design (in Sec. 5), how MPC can be used for complex tasks (in Sec. 5), and stressing the importance of considering individual tasks (in Sec. 3 & 4).

[1] Fey et al. Hierarchical Inter-Message Passing for Learning on Molecular Graphs. arXiv:2006.12179

[2] Wollschläger et al. Expressivity and Generalization: Fragment-Biases for Molecular GNNs. ICML 2024.

[3] Bodnar et al. Weisfeiler and Lehman Go Cellular: CW Networks. Neurips 2021.

[4] Fey et al. Relational Deep Learning: Graph Representation Learning on Relational Databases. arXiv:2312.04615.