What Expressivity Theory Misses: Message Passing Complexity for GNNs
Authors: Niklas Kemper
Tom Wollschläger
Stephan Günnemann
Venue: NeurIPS 2025 spotlight ()
Keywords: gnn
mpnn
expressivity
theory
complexity
message passing
over-squashing
under-reaching
over-smoothing
WL
practice
higher-order
Primary area: theory

Abstract: Expressivity theory, characterizing which graphs a GNN can distinguish, has become the predominant framework for analyzing GNNs, with new models striving for higher expressivity. However, we argue that this focus is misguided: First, higher expressivity is not necessary for most real-world tasks as these tasks rarely require expressivity beyond the basic WL test. Second, expressivity theory's binary characterization and idealized assumptions fail to reflect GNNs' practical capabilities.
To overcome these limitations, we propose Message Passing Complexity (MPC): a continuous measure that quantifies the difficulty for a GNN architecture to solve a given task through message passing.
MPC captures practical limitations like over-squashing while preserving the theoretical impossibility results from expressivity theory, effectively narrowing the gap between theory and practice.
Through extensive validation on fundamental GNN tasks, we show that MPC's theoretical predictions correlate with empirical performance, successfully explaining architectural successes and failures. Thereby, MPC advances beyond expressivity theory to provide a more powerful framework for understanding and developing GNN architectures.

What Expressivity Theory Misses: Message Passing Complexity for GNNs
Niklas Kemper School of Computation, Information and Technology & Munich Data Science Institute
Tom Wollschläger
Stephan Günnemann
Technical University of Munich
(niklas.kemper, t. toollschl,,,r gugnnemann
Abstract
Expressivity theory, characterizing which graphs a GNN can distinguish, has be- come the predominant framework for analyzing GNNs, with new models striving for higher expressivity. However, we argue that this focus is misguided: First, higher expressivity is necessary for most real-world tasks these tasks rarely require expressivity beyond the basic WL test. Second, expressivity theory's binary characterization and idealized assumptions fail to reflect GNNs' practical capa- bilities. To overcome these limitations, we propose Message Passing Complexity (MPC): continuous measure that quantifies the difficulty for GNN architecture to solve given task through message passing. MPC captures practical limitations like over-squashing while preserving theoretical impossibility results from expres- sivity theory, effectively narrowing the gap between theory and practice. Through extensive validation on fundamental GNN tasks, we show that MPC's theoretical predictions correlate with empirical performance, successfully explaining architec- tural successes and failures. Thereby, MPC advances beyond expressivity theory provide more powerful and nuanced framework for understanding and improving GNN architectures.
Introduction
From weather forecasting to drug design, Graph Neural Networks (GNNs) have shown remarkable success across diverse applications. However, the seminal works by Morris al. [36] and Xu et al. [48] revealed a key limitation of standard Message Passing Neural Networks (MPNNs): Their ability distinguish non-isomorphic graphs can be bounded by the Weisfeiler-Leman (WI.) graph isomorphism test [45].
In response, significant research effort has focused on developing more expressive architectures that surpass the WL test [27]. The underlying hypothesis is that increased expressivity translates to better empirical performance, with improved benchmark results often attributed to higher expressivity [46]. Isomorphism-bart (Iso) expressivity theory, which characterizes the sets of graphs an architecture distinguish through the WL test and its extensions, has thus become the predominant framework for analyzing MPNNs.
We argue that this focus on iso expressivity is misguided. While it provides valuable impossibility results, we identify two key limitations that prevent from explaining real-world MPNN performance. First, higher expressivity is often not necessary for real-world tasks: almost all graphs in standard benchmarks are already distinguishable by the basic WL. test, making unclear why higher expressiv- ity would improve performance [54]. Second, iso expressivity theory fails capture practical model capabilities. It assumes unrealistic conditions like lossless information propagation over unbounded layers, ignoring practical limitations like over-squashing [1]. Moreover, its binary view (can vs. cannot distinguish) offers no insight into the relative difficulty learning specific real-world tasks.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

To address these limitations, we propose shifting from binary expressivity tests to a continuous complexity measure, MPC, that quantifies the message-passingg complexity of arbitrary tasks for given architecture. MPC builds upon novel probabilistic WI. test. It captures practical limitations of MPNNs, such as under-re [3] and over-squashing [1], which are known to hinder empir- ical performance, while preserving impossibility results from iso expressivity theory effectively narrowing the gap between theory and practice.
Through extensive validation, we show that trends in MPC complexity align with empirical per- formance across a range of fundamental graph tasks.' 1 Notably, success is determined not by iso expressivity but by architectural choices that minimize complexity for specific tasks. For instance, a simple GCN with virtual node outperforms strictly more expressive, higher-order models at long- rongerange tasks, as MPC correctly predicts. By providing quantitative measure of architectural capabilities for specific tasks, MPC both reveals current model limitations and offers clear optimization targets for future architectural innovations, shifting focus from maximizing expressivity to minimizing task-specific complexity.
In summary, our key contributions are:
We identify limitations of iso expressivity theory that prevent it from explaining MPNN performance in real-world tasks ($ 3).
We introduce MPC, continuous peessae-passiiggg complexity measure rooted in novel probabilistic WL test that characterizes task-specific difficulty. MPC captures existing MPNN limitations, such over-smoothing and under-reaching, while retaining impossibility results from iso expressivity theory ($ 4).
We extensively validate MPC, showing its consistency with empirical performance and its superiority over classical expressivity theory in explaining real-world MPNN behavior ($ 5).
2 Background
Notation Let G = -VG, X) denote an (undirected) graph with nodes VG. edges Eg, fea- tures X, for v E VG and adjacency matrix A. With Á = + define the influence matrix Iuv := Aur/ /w Auw as the normalized adjacency (with self-loops). Let dg v) be the shortest path distance between and and No(v) be the set of neighbors of v. Let G denote set of graphs and G the set of all graphs. Let Gy = {(GGu) | E G, u E Va denote the set of graph-node pairs. We will mainly consider node-level functions or tasks of the form f : Gy + RR. For brevity, we will often write (G) for v(G We define log(0) = oo and ((- (-B is multiset. Let WL. Gy + R denote the color assignment of the 1-th round of the WI test, defined as: WI X, and WL HASH (WI
[-1 ff [-
N))
Message Passing Framework Standard MPNNs MM have hidden representations h2 for each node which are updated iteratively at each layer / E (1....,,L) L} by aggregating messages m m from neighboring nodes in the graph G:
msgi (11-1) 10 msg! (h)--)
if w = else
and h1 = :p= (fmm w w Na(()
m 10
Here, msg/. msg/. and upd' can be arbitrary (learned) functions, often MLPs. Typical choices for the aggregation function agg are mean or sum. We differentiate between a model architecture M that only specifies which nodes exchange messages (abstracting away from the choice of mag, upd, and agg), and (learned) model instantiation M E M with fully specified mag, upd and agg functions. Standard MPNNs Ms perform message passing directly on the input graph G. In contrast, more recent architectures propagate messages on a transformed message passing (MP) graph G f(G) [42]. They introduce modifications like additional virtual nodes [18], rewired edges [41], or higher- order graphs [46]. For simplicity, we mainly focus on standard MPNNs Ms in the main text, and defer general framework encompassing architectures M with arbitrary MP graphs G to App. B.I.
Find our implementation at https: //te:://wwwweee cit, tum, /t/ wwwpppan-ccmseeeeeeeeeeeeee complexity/

---

3 Limitations of Expressivity Theory
MPNN architectures differ in their theoretical capacity to solve graph tasks, such as detecting specific substructures [53]. Most prior expressivity theory captures differences by considering an architecture's ability distinguish non-isomorphic graphs relative to a reference isomorphism test a [22, 5, 46, 37]. Formally:
Definition 3.1 (Iso Expressivity). Let a be graph isomorphism test. An architecture M is at least as expressive as a 3M E . such that VG, G" E g":
M(G) M(') = a(G) = a(G") Contrarily, M is at most as expressive as or Vf E M and VG, g
(I)
a(G) = aG') = M(G) M(G)).
(2)
Standard MPNNS MMs are at most expressive the WL test [36, 48]. In response, recent GNN research has focused on developing architectures that surpass the WL test in expressivity. Their strong performance on benchmarks such as ZINC [5, 8, 16, 46] is often motivated by and attributed to their higher iso expressivity [46, 8, 16]. This builds on the premise that theoretical iso expressivity correlates with empirical performance. Consequently, this line of expressivity research rests on two fundamental assumptions, both of which we show to be problematic (Fig. 1):
1. Iso expressivity theory accurately describes the practical capabilitiess of trained MPNNs. The theoretical higher expressivity of higher-order MPNNs translates to a higher practical capability to learn more complex tasks, contributing to improved empirical performance.
2. Iso expressivity beyond WL is important for real-world performance. The limited expressivity of standard MPNNs restricts their performance on real-world tasks.
We first critique Assumption 1, showing that iso expres- sivity theory relies on idealized assumptions and provides incomplete insights about practical MPNN capabilities. Positive expressivity results only guarantee the existence of model instance within the architecture that is more ex- pressive than a. These proofs typically rely on a maximally expressive model M with injective upd functions and an unbounded number of layers [5]: conditions under which every node can access the complete information from all other nodes. This idealized setup ignores fundamental limitations of real-world MPNNs. In practice, message passing is lossy: information is often bottlenecked (over- squashing [1]), blurred lover-smoothing [33]). simply out of reach due to shallow depth (under-reaching [3]). As result, real-world MPNNs often fail to propagate infor- mation even between nearby nodes, let alone replicate the idealized behavior assumed in expressivity theory. Second, expressivity theory provides strictly binary results [38]: can vs. cannot distinguish, with no indication of difficulty. This binary lens cannot account for the wide variation in empirical performance between architectures of equal ex- pressivity on the same task. For example, adding a virtual node does not increase iso expressivity [46] but often leads to performance gains on long-range tasks [9]. Additionally,
Iso Expressivity
MPC
binary
continnaus
idealized model
practical limitations
SM
single task
any task
+
global worst-case
local
all graphs
real graphs
Vrest
Figure 1: Limitations of iso expressivity vs. benefits of MPC. Top: Iso expres- sivity gives an idealized, binary view that misses GNNs practical capabilities. Bottom: Limited expressivity rarely re- stricts real-world performance as it fo- cuses on worst-case graphs and tasks.
berween theoretically solvable tasks, iso expressivity theory provides no insight into their relative dif- ficulty. Some tasks might be trivially learnable in practice while others may be practically impossible to learn with finite data and training time. In summary, the assumptions behind positive expressivity results diverge sharply from the realities of real-world MPNNs, and the binary view can offer only limited insights for practice. Our empirical results in $ 5 reinforce this, showing that even highly expressive MPNN architectures struggle with elementary tasks like maintaining initial node features. This highlights gap between positive iso expressivity results and practical performance.
3

---

We now challenge Assumption 2, asking whether negative expressivity results reflect meaningful limitations in practice. Iso expressivity theory considers only the hardest possible task: distinguishing all -oommoooo graphs. However, many real-world applications, such as social network analysis or relational learning, often require only aggregating (local) information. In these cases, the inability to distinguish certain non non-isomorphic graphs does not constitute a meaningful limitation in practice. By focusing exclusively on this worst-case task, expressivity theory overlooks the specific requirements of practical problems. Second, expressivity theory makes global statements over the set of graphs G*, demonstrating a lack of expressivity through single, carefully constructed counterexamples [46, 22, 5j. However, these counterexamples are rare: the probability of encountering WL. equivalent graphs in random graphs approaches 0 [2], and real-world graphs often carry rich node features that further break WL equivalences. Hence, the mere existence of theoretical countercxamples provides limited insight into model's practical performance on large, diverse datasets. Lastly, iso expressivity theory is graph-family agnostic. Its results are derived for the set of all possible graphs G whereas real-world applications typically involve restricted graph families. For example, molecular datasets primarily contain planar graphs with bounded degrees. Tasks infeasible over all graphs may become solvable for standard MPNNs within these restricted graph families [13, 40]. Moreover, shown in Tab. 1, the basic WL test already distinguishes almost all graph pairs in popular benchmarks across different domains [54]. Therefore, iso expressivity theory cannot explain why expressivity beyond the WI. test would benefit these real-world tasks or account for the performance differences between architectures.
Our analysis shows that iso expressivity theory, while valuable for establishing theoretical limitations, provides limited insights for practical MPNN applications. It assumes idealized conditions and focuses on theoretical worst cases, leading to a disconnect with practice: high iso expressivity does not imply good performance (contradicting Assumption 1), and limited iso expressivity does not imply poor performance (contradicting Assumption 2). While alternative expressivity approaches such logic-based characterizations address certain limitations of iso expressivity (see $ 7), none can characterize the varying degrees of practical learning difficulty encountered in real-world tasks. These findings suggest that pursuing higher expressivity alone may be misguided, highlighting the need for a framework that captures theoretical limitations and practical learning challenges.
4 Message Passing Complexity
To move beyond the limitations of expressivity theory, we propose our continuous, task-specific message passing complexity (MPC). Unlike iso expressivity theory, which only asks whether an MPNN can distinguish certain graphs in theory, MPC quantifies how difficult it is for messages to propagate through graph to solve a given task. By accounting for the inherently lossy information propagation of real-world MPNNs, MPC can explain practical performance trends that expressivity theory misses. While many complexity measures exist in machine learning and theoretical computer science, they fail address this unique challenge of MPNNs: propagating information effectively across graph structures. MPC specifically isolates this challenge from other general sources of difficulty in machine learning for instance, learning high- polynomials is a well-understood difficulty not specific to graph learning. For clarity, we focus on node-level tasks fo and standard MPNNs Ms in this section, with generalizations broader architectures and tasks provided in App. B.
As initial step, we define local task-specific complexity measure based on the WL test that considers individual graphs and individual tasks rather than making global worst-case statements over all graphs and tasks. For this, we first need to formalize when one individual function output provides sufficient information to determine another (Fig. 7):
Definition 4.1. Let a X B. X + Z be two functions. Let x E X be fixed. Then, ((z) can be deduced from a(x), axx) Fx (zx), iff
Val E X a(x) a(x') = ((x) = B(x').
If (f) Fx B(x) for all E X, we write a Fx .3 and say is more more fine-grained than B
Intuitively, (x) Fx ((z) means that a(x) provides sufficient information to uniquely determine 3(z). Using this, we can define a first complexity measure dependent on a specific task fu and
individual graph G. The complexity should be maximal if a task f. is infeasible for all M E Ms. i.., the WL coloring WL. (C) of in the graph G contains insufficient information to deduce (G):
4

---

Definition 4.2. For G U. E Gv, task f over Gy and an L-layer standard MPNN Ms. define
(I. f o (G) fa(G)
0
else.
While WLC considers specific tasks fo and graphs G, it still inherits a fundamental limitaatio of iso expressivity: only distinguishes between possible (complexity 0) and impossible (complexity oo) tasks. This binary characterization fails to capture the varying difficulties observed in practice. Moreover, as discussed in $ 3, the WL test assumes lossless information propagation between nodes, contrasting sharply with the lossy message passing observed in trained real weal-world MPNNs.
4.1 Weisfeiler & Leman Go Lossy
To extend our complexity measure beyond the binary characterization of the standard WL test, we need account for the varying difficulty arising from the lossy message passing observed in practice. This difficulty inherently relies on the graph topology, i.e., the difficulty of propagating a message from one node to another node depends on 1) the number of L-length walks connecting and u and 2) the degrees of the nodes on the walk. This can be formalized as the random walk probability I from v with edge probabilities and has been connected the amount of gradient information node receives from u [47] and to the oversquashing phenomenon [19]. Correspondingly, I serves as a measure of difficulty for the simple task of propagating a message from u to
How can we adapt this measure of difficulty to arbitrary tasks? propose lossy WL, probabilistic variant of the WL test that models the possibility of message loss.
For this,
This allows us to quantify difficulty even for WL-distinguishable real-world graphs Specifically, mes-
sage my sent from a node to its neighbor u E Nu) survives with probability Iou (Fig. 2). As a result, the color lossyWI.", of node v at iteration I becomes a random vari- able rather than a deterministic value.
Definition 4.3 (lossy WL). For given graph G, let m be the (potentially lost) message from u to v at iteration I:
ma-+o z -oossyLL 1-1
with independent Z ~ Bernouli([Tww,, indicating whether the message successfully transmitted. The node colors of the probabilistic WL tests are then recursively defined as:
lonsy lossyWI, - HASHIOO, (O.O.OI)
Figure 2: Update step of Wossy for node v. Every message m (green) survives independently with probabil- ity Iea. lossyWL. models the lossy message propagation observed in real- world MPNNs.
lossyWL. X
lossy WL. = HASH (m...: Hm u E Na(u)
Similar to how we can transform the WL test into WLC, we can define our complexity measure, MPC, based account for probabilistic functions such that P[a(()) = 3(x)) represents the probability that (zx can be uniquely deduced from the probabilistic output of (<x)) (Fig. 8).
probabilistic lLssyWL test. To do this, we first extend the Definition 4.1 of F= to
Definition 4.4. Let 8 X + Z be deterministic function and X + Y be probabilistic function that can be represented as deterministic function a, where is a seed drawn uniformly at random from (finite) set S. For fixed X, define:
Pfa(x) Fx [(x)] P. P.ss(Va' X, E: az(x) = = 3(x))
With this in place, we define our message passing complexity: intuitively. if there is high probability of preserving the information needed for fu, the task should have low complexity, and vice versa. Definition 4.5 (MPC). For G, v E Gy, a function f over By and an L-layer MPNN My, define
MPC (Jo. G) log PloossyWI.[CG Fgy fo(G))
5

---

MPC is based on the probability that under lossy message passing on G, the output after L layers contains sufficient information to deduce f.. Intuitively, a high MPC value indicates that the task Jo requires 1) combining information from many nodes through 2) messages of low probability, such as messages through bottlenecks. Conversely, a low MPC value means the task depends on information that remains reliably accessible even under lossy message passing conditions. Note that MPC implicitly also depends on g. which we omit for simplicity. While we focus here on standard MPNNs Ms. MPC generalizes naturally to a wide range of architectures M by performing lossyWL on modified message passing graphs (see App. B. All in all, MPC effectively addresses the discussed limitations of iso expressivity theory, narrowing the gap between theory and practice.
4.2 MPC describes theoretical and practical limitations of MPNNS
Having defined our complexity measure MPC, we now demonstrate that unifies theoretical expres- sivity with practical GNN limitations in single framework. We first establish that MPC preserves impossibility results from iso expressivity theory, then show how it captures practical phenomena such as over-squashing and under-reaching. We begin by characterizing when MPC becomes infinite, which precisely corresponds to tasks that are theoretically impossible for a given architecture M.
Theorem 4.6 (Infeasibility). The complexity for G. v E Gv and function f is MPCM G) co if and only if there exist G', Gy such that fG) + (G') but M,(G) Mw (G') for all model instantiations M E M.
This shows that MPC becomes infinite precisely when model architecture fundamentally cannot dis- tinguish between two different nodes that require different outputs. We can also globally characterize the functions architecture can express:
Lemma 4.7. There exists no model instantiation M E . such that Ma(G) = Sv(G) for all G, E Gy if and only if there exists G, u Gv with () oc.
By choosing an isomorphism test (like the WL test) as task f. can recover all impossibility statements from iso expressivity theory (Lemma C.7). Thus, MPC subsumes iso expressivity theory while providing a continuous difficulty measure for possible tasks. Having established when MPC becomes infinite, we now characterize how MPC scales with function granularity: a finer, more discriminative task can never have lower complexity than the coarser task it refines. For example, counting the exact number of cycles in a graph should be more complex than merely detecting whether any cycle exists.
Theorem 4.8 (Function refinement). Let f be a function that is more fine fine-grained than i.e. Fgv g. Then for any G, v E Gv: MPCM(ff: G) 2 MPCMM(g.. G).
Like other complexity measures, MPC satisfies compositionality: solving tasks jointly cannot be more complex than solving them separately, and may be casier when tasks share information.
Lemma 4.9 (Task Triangle Inequality). Let I and be functions, and || denote concatenating function oufputs. Then for any G, E Gv: MPC MPCMM(f (frllgg,, G) < MPC G) + MPC G).
However, MPC connects not only properties of classical complexity and expressivity theory but also captures real-world limitations of MPNNs such as over-squashing and under-reaching, These phenomena, extensively studied significant constraints on MPNN performance, are overlooked by traditional expressivity theory. We first relate MPC to over-squashing by showing that it is lower bounded in terms of the L-step random walk probability from u, (I²) a quantity that also motivated our design of lossy WL in Š 4.1.
Lemma 4.10 (Informal version of Lemma C.10). Consider a task f and G, v Gy where Sn "depends on" information x, from node u. Then
MPCM G) 2 log ((T+)
A lower probability (I²),u indicates that node receives less gradient signal from u, making it more susceptible to over-squashing [19,4] 47]. Our complexity measure captures this: when (I²) )ou is small, tasks requiring information flow from we consider under-reaching, which occurs when the number of MPNN layers is less than the graph diameter, preventing nodes from receiving information from distant parts of the graph [3, I]:
have high complexity. As simple special case,
We defer all proofs to App. C.

---

Corollary 4.11. Consider a task fo and graph G E 9 where fo "depends on" information X. from a node u outside of the receptive field, i.e. dz(u,v) v) > L. Then MPCM(fes G) = xo.
These results show that MPC captures both theoretical expressivity and practical limitations of GNNs, providing more unified framework that bridges both perspectives.
5 MPC in Practice: Explaining Empirical MPNN Behavior
We now demonstrate that MPC quantitatively explains empirical MPNN behavior. Through analysis of fundamental graph restinre information, propagating information, and extracting topologiaal features we show that: 1) MPC enables the derivation of meaningful task-specific complexity bounds; 2) trends in MPC complexity correlate strongly with empirical performance, better reflecting the practical behavior of MPNNs than iso expressivity theory; 3) optimal architectures vary by task, with success determined by minimizing task-specific MPC complexity through appropriate inductive biases, not maximizing expressivity. Experimental Setup: We verify this for a wide range of architectures, including an MLP baseline (message passing on an empty graph), standard models like GCN [31], GIN [48], GraphSage [25], and GCN with virtual node, GCN-VN [18), well as higher-order models like GSN [8] which incorporates aubstructure-informatioo as node-feature, FragNet [46] which builds higher-level graph of fragments and the appoloiicalinssieee model CIN [5]. We evaluate on random r-regular graphs G and show that the results transfer to graphs from the ZINC dataset [15] and the long-range graph benchmark [14]. We provide theoretical complexity bounds and Monte- Carlo simulated complexity values. We compare MPC to the WL-based WLC baseline rather than directly to other expressivity measures, as they have fundamental limitations for task-specific difficulty analysis: they typically provide only global, task-agnostic architecture rankings [53, 52] or impose restrictive assumptions incompatible with our tasks [20] (see $ 7).
First, we evaluate the task (G) = X,, which tests a model's 's ability to re- tain its initial node features. This task is fundamentally important across all domains with informative node features (e.g., atom type in molecules). Although seemingly simple, it is closely linked to the well-studied over-smoothing [33] phenomenon, where deeper GNNs lose distinguishability between nodes as their representations converge. making it difficult to recover the original node features [21]. Our complexity measure captures this difficulty as MPC increases least linearly with depth L:
Retaining information
Lemma 5.1. Assume the degree r Z 2. EG [M G)] grows at least linearly with L, i.e. is in ((L), for all MPNNs M.
Then the expected MPC complexity for this task
For empirical validation, we train all model archi- tectures on 2000 randomly generated 3-regular graphs with varying numbers of layers L. As shown in Figs. and 9, the complexity measure based iso expressivity theory, WLC, assigns constant zero complexity regardless of depth L, indicating only theoretical solvability. In contrast, MPC shows perfect negative Spearman correlation with accuracy for most architectures, capturing the increasing difficulty with L.. Only CIN and Graph- Sage maintain perfect accuracy throughout, due explicit residual connection optimization-an an im- plementation choice our frrameorr abstracts from. These results demonstrate that, unlike binary ex- pressivity measures, MPC accurately quantifies the progressive difficulty of this task for most ar- chitectures, capturing important real-world limita- tions beyond theoretical impossibility statements.
GCN
GSN
FragNet
Acc
Acc
AcC
WLC
0
2
0.92
1.5
0
0.9
1.5
0.92
1.7
+
0.8
2.2
0.88
2.2
0.85
Num
2.8
0.35
8
0.29
3.2
0
0.27
3.2
0.16
3.3
-1
0.4
Accursy
Cormunstt
Figure 3: Test accuracy for retaining initial node features compared with complexity mea- sures MPC and WLC. Simulated MPC (in con- trast to WL-based WLC) shows perfect negative Spearman correlation (p.- = 1) with accuracy, capturing increasing difficulty with depth (over- smoothing). Complete results in Fig. 9.
Propagating Information We next analyze the task (G) X... where is a specially marked source node at distance D = (u, u) from target node v. This task directly tests a model's ability to propagate information in relation to the distance D, exposing practical limitations like ovurssquagiin and under-reaching that classical expressivity theory overlooks.
Lemma 5.2. Assume L is the minimum depth required to solve this task with M. Then the expected complexity R. M G)) is S 2 llg(n) for GCN-VN, while for standard MPNNs is > D log(r) provided n is sufficienlly large given D.
7

---

GCN-VN
GCN
GCNAN
FrogNe:
Cesance
MPO
MPC
0.1
100
200
500
1000
202
520
1200 A22
202
500
1000
Ducawer: 2.20
Detaset Stne
Datenut Size
Figure 4: Simulated MPC complexities for propagating features from source nodes u (colored by MPC) to target node v (square). Despite identical iso expressivity, MPC reveals the significant advantage virtual nodes offer for long-range dependencies.
Figure 5: Test accuracy vs. training data size for the propagation task [C) X, for different distances D. Colors indicate average simulated MPC for each dis- tance. Higher MPC values reflect greater task difficulty, evidenced by increased sample complexity. All results in Fig. 13; for real-world graphs from Irgb in Fig. 17.
The bounds reveal that MPC captures two critical insights missed by classical expressivity: First, MPC increases with distance D for most MPNNs, explaining why they struggle with long-range de- pendencies despite theoretical learnability. Second, virtual node fundamentally changes complexity scaling from O(D) to (log n), explaining its empirical advantage despite unchanged expressivity (see Fig. 4). Moreover, MPC also captures under-reaching: by Corollary 4. complexity becomes infinite when (2(u, v) > L.
Experiments for models with L = layers validate these predictions: MPC correlates negatively with accuracy (Fig. 14) and captures the increased sample complexity with distance (Figs. 5 and 13). Crucially, all models except GCN-VN fail at D = 5. showing that high MPC complexity indicates practical limitations even before the theoretical impossibility at > 5. Importantly, these find- ings-strong ueC-ppefformance correlation and practical failure before theoretical real-world graphs from the long-range graph benchmark (Fig. 17).
in
In summary, these results demonstrate why MPC offers a more complete and practical understanding of MPNN capabilities than classical expressivity theory. Unlike binary expressivity tests. MPC explains why even highly expressive architectures, such as GSN, FragNet, and CIN, struggle with fundamental tasks like retaining or propagating node information empirically validating our critique in $ 3 that iso expressivity poorly captures practical capabilities. Furthermore, MPC accounts for the success of architectural choices like virtual nodes, which consistently improve performance on real-world long-range tasks [9] despite unchanged iso expressivity [46].
Topological Feature Extraction Our final experiment examines how models extract topological features through cycle detection. We consider random r-regular graphs with unique node labels X, E {I....,7) n), modified to contain cycle of size that includes designated node v. The task fo is to identify the labels of all nodes in this cycle, jointly testing the model's ability to detect cycles and propagate information across them. We can derive complexity bounds for all considered MPNNs:
Lemma 5.3 (Informal version of Lemma C.13). Assume L is the minimal depth required to solve this task with architecture M and that there only single cycle in the [s/2]-hop neighborhood of v. Then, the expected MPC complexities are:
For CIN & FragNet: O(log(s))
For GSN: S (og(r +1)
For all others: 2 s slog(r)
These bounds reveal that MPC captures crucial architectural differences missed by iso expressivity: standard MPNNs have complexity scaling linearly with cy- cle size, while CIN and FragNet achieve logarithmic scaling, capturing their cycle- oriented inductive biases. Experiments on random 4-regular graphs confirm these theoretical predictions, with trends in MPC complexity matching empirical performance (see Figs. and 18; in rela- tion dataset size: Fig. 19).
GCN
Sage AP MPC WLC
GSN AP MPCWLC
FragNet
AP
MPC
WLC
AP MPCWLC
0.73
4.2
0.0
0.76
4
0.0
0.95
1
0.0
3.96
2.7 0.0
Ring
0.58
5.5
0.0
0.55
5.5
0.0
0.70
8 0.0
0.82 3.0
0.0
0.45
0.0
0.50
0.0
0.63
3.2
Ps
0.2
0.4
0.6
0.8
1.0
Awerage Prectons
Complesity
Figure 6: Average precision (AP) for the ring task com- pared with complexity values MPC and WLC (MPC val- ues for SAGE& & GCN are lower bounds). MPC (in con- trast to WLC) is negatively Spearman correlated with AP and captures the advantage of cycle-oriented inductive biases in GSN and FragNet, See also Figs. 18 and 23.
Because of the unique node labels, (at least WL expressive) architectures are
8

---

theoretically able to solve this task, yet performance varies dramatically. While iso expressivity theory cannot capture these differences, MPC provides clear explanation: GSN, CIN and FragNet's architectural bias towards cycles reduces their message-passinng complexity for this task, providing them with a performance advantage. This insight extends to real-world graphs from the ZINC molecular regression benchmark [15] (Fig. 6), where the identification of molecular rings is crucial. As shown in Tab. 2, architectures with lower ring detection complexity consistently achieve better performance ZINC on both the synthetic and the real task. The superior performance of higher- order MPNNs like GSN, FragNet or CIN cannot be explained by their greater iso expressivity- -s discussed in 3, almost all graphs in ZINC are already WL-ddisinguishable-- but by their cycle- oriented inductive biases that reduce the complexity of learning molecular structures.
Overall, our results demonstrate that trends in MPC consistently correlate with empirical performance across all tested tasks, offering a more fine- fine-grained, complete, and practical understanding of MPNN capabilities than iso expressivity theory's 's idealized binary characterization. Crucially, we find that no single architecture performs best across all tasks peessss-rrrrmaceee depends not on iso expressivity but the alignment between model's inductive biases and the task requirements. While the global task-agnostic architecture rankings of most existing expressivity measures fail to capture this variation, MPC quantifies the alignment between architecture and task-explaining why virtual nodes excel at long-range tasks or why cycle-aware designs help for ring-transfer. This provides task-specific guidance for architectural design that pure expressivity theory cannot offer.
6 Limitations & Future Work
While we have demonstrated that our complexity measure closely aligns with empirical performance for many tasks, it abstracts away from the parametrization and implementation of the upd and agg functions and the optimization process as discussed in $ 5. Additionally, our MPNN framework does not include models with attention. However, we repeat all our experiments with the most common attention- based MPNNs in App. D.I, showing similar empirical trends to the MPNNs that we consider. Secondly, exact target functions in real-world applications are usually unknown, Still, can analyze two types of proxy tasks: fundamental capabilities required across all domains (like retaining information) and domain -speiff operations (like cycle detection). As shown in Tab. 2, the insights from these proxy tasks can translate to real-world performance. Third, exact complexity values can be difficult to compute for sophisticated tasks. However, as our experiments demonstrate, theoretical bounds can provide valuable practical insights. Finally, the complexity values should not be interpreted in isolation to determine whether an architecture can solve a given task, as they only characterize the message-passiceg complexity of task. Instead, they are most useful for identifying trends and comparing architectures across a single dimension of freedom.
These limitations point to promising extensions of the MPC framework. MPC could be extended to incorporate additional sources of practical difficulty, such as feature noise (App. B.3), providing a more complete view of empirical task complexity. Furthermore, the framework could be modified to capture aggregation and weights Zun (as in attention-based models), enabling analysis of how different update functions affect message passing complexity.
effects by incorporating non-uniform or learnable message
More broadly, hope that MPC will enable more principled architectural design: By quantifying fine-grained task complexities, MPC can reveal practical limitations of current architectures and guide the development of models with low complexity for specific capabilities relevant to target domains. As a concrete example, consider substructure identification. Our analysis in $ shows that all considered MPNNs without additional pre-processing steps exhibit very high complexity for this task, even when it is theoretically solvable. This suggests that architectural modifications alone may be insufficient, pointing toward studying expressive preprocessing steps or positional encodings -as successfully employed by FragNet [46] and CIN [5]- that directly reduce task complexity. More generally, this exemplifies how MPC can shift architectural design from maximizing universal expressivity toward strategically minimizing complexity for domain-specific requirements.
7 Related Work
Iso-expressivity frameworks. The predominant approach for analyzing GNNs compares their ability to distinguish non-isomorphic graphs relative to the WL test and its extensions [36, 48, 37]. This has

---

motivated extensive research on developing higher-order architectures that surpass standard MPNNS in expressivity [37,5, 22, 46]. However, as discussed in $ 3, iso-expressivity theory relies on idealized assumptions and provides only binary characterizations, limiting its practical relevance.
Alternative expressivity characterizations. Beyond iso-expressivity, several frameworks theoreti- cally characterize MPNN capabilities through specific tasks. Zhang et al. [53] rank architectures by the set of substructures they can recognize, while Zhang al. [52] compare models through their ability to solve graph biconnectivity. Wang and Zhang [44] analyze spectral MPNNs through their ability to learn polynomial filters. Logic- based approaches [3. 23] characterize learnable functions through fragments of first-order logic, providing more nuanced insights by considering, for example, the effects of different activation functions [29]. 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.
Continuous graph distances. To move beyond binary expressivity, some works have proposed continuous graph similarity measures, including tree-based [12], graphon-based [7], and Wasserstein- based distances [10]. However, these metrics are task-agnostic and architecture-indeenndnn limiting their relevance for explaining practical GNN performance.
Practical GNN limitations. A parallel line of research studies individual practical limitations of GNNs, such over-smoothing [33], under-reaching [3], and over-squashing [1, 19, 41]. Most relevant to our approach is the work by Giovanni et al. [20]. which derives expressivity limitations from over-squashing theory. They show tasks become impossible when the required "mixing" between nodes (measured via the Hessian) exceeds what MPNNs can generate. Like MPC, this can capture practical impossibilities arising from over-squashin. However, their framework considers only pairwise interactions with restrictive assumptions on the task (twice differentiable tasks, not dependent on graph topology).
While these works study individual theoretical or practical limitations of GNNs, MPC is the only framework that captures both theoretical expressivity and practical limitations while allowing analysis of arbitrary tasks.
8 Conclusion
We show that classical expressivity theory cannot explain MPNN performance in real-world settings. To narrow the gap between theory and practice, we propose MPC: a continuous complexity measure that quantifies the sassage-passing difficulty of tasks for different architectures. By building upon novel probabilistic variant of the WL test, MPC retains all impossibility results from iso expressivity theory while capturing practical limitations like over-squashing and under-reaching. Our extensive validation on fundamental MPNN tasks reveals that trends in MPC complexity correlate with empirical performance, explaining phenomena that iso expressivity theory cannot address. Notably, our analysis indicates that the success of (higher-order) MPNNs often stems from low task complexity rather than increased iso expressivity. This perspective shifts focus from maximizing expressivity minimizing task-specific MPC complexity, providing clear directions for architectural innovation.
Acknowledgments
We would like to thank Nicholas Gao and Aman Saxena for proofreading this manuscript, and the anonymous reviewers for their constructive comments. This research is supported by the Bavarian Ministry of Economic Affairs, Regional Development and Energy with funds from the Hightech Agenda Bayern.
References
[1] U. Alon and E. Yahav. On the bottleneck of graph neural networks and its practical implications. In ICLR, 2021.
[2] I. Babai, Erdös, and S. M. Selkow. Random graph isomorphism. SIAM Comput., 9()): 628 6635, 1980.
10

---

[3] P. Barceló, E. V. Kostylev, M. Monet, J. Pérez, J. L. Reutter, and J. P. Silva. The logical expressiveness of graph neural networks. In ICLR, 2020.
[4] Bause, Jogl, Indri, T. Drucks, D. Penz, N. M. Kriege, T. Gärtner, P. Welke, and M. Thiessen. Maximally expressive gnns for outerplanar graphs. Trans. Mach. Learn. Res., 2025, 2025.
[5] C. Bodnar, F. Frasca, N. Otter, Y. Wang. Liò, G. F. Montúfar, and M. M. Bronstein, Weisfeiler and lehman go cellular: CW networks. In NewrlPS, pages 2625-2640 2021.
[6] C. Bodnar, F. Frasca, Y. Wang. N. Otter, G. F. Montúfar, P. Lió, and M. M. Bronstein. Weisfeiler and lehman go topological: Message passing simplicial networks. In ICMI,, volume 139 of Proceedings of Machine Learning Research, pages 1026-1037. PMLR, 2021.
[7] J. Böker, R. Levie, N. Huang, S. Villar, and C. Morris, Fine-grained expressivity of graph neural networks. NeurIPS, 2023.
[8] G. Bouritsas, Frasca, S. Zafeiriou, and M. M. Bronstein. Improving graph neural network expressivity via subgraph isomorphism counting. IEEE Trans. Pattern Anal. Mach. Intell., 45 (1):657-668, 2023.
[9] C. Cai, S. Hy, R. Yu, and Y. Wang. On the connection between MPNN and graph transformer. In ICML, volume 202 of Proceedings of Machine Learning Research, pages 1008--330... PMLR, 2023.
[10] Chen, S. Lim, F. Mémoli, Z. Wan, and Y. Wang. Weisfeiler-lehman meets gromov-wassersteine In ICML,, volume 162 of Proceedings of Machine Learning Research, pages 3371-3416. PMLR, 2022.
[11] Z. Chen, L. Chen, S. Villar, and J. Bruna. Can graph neural networks count substructures? In NeurlPS, 2020.
[12] C. Chuang and S. Jegelka. Tree mover's distance: Bridging graph metrics and stability of graph neural networks. In NeurIPS, 2022.
[13] R. Dimitrov, Zhao, Abboud, and i. f. Ceylan. Plane: Representation learning over planar graphs. In NeurIPS, 2023.
[14] V. P. Dwivedi, L. Rampásek, M. Galkin, A. Parviz, G. Wolf, A. T. Luu, and D. Beaini. Long range graph benchmark. In NeurIPS, 2022.
[15] V. P. Dwivedi, C. K. Joshi, T. Luu, Laurent, Y. Bengio, and X. Bresson. Benchmarking graph neural networks. J. Mach. Learn. Res., 14:43:1-43:44 2023.
[16] J. Feng, I.. Kong, H. Liu, D. Tao, F. Li, M. Zhang, and Y. Chen. Extending the design space of graph neural networks by rethinking folklore weisfeiler-lehman. NeurlPS, 2023.
[17] M. Fey and J. E. Lenssen. Fast graph representation learning with pytorch geometric. CoRR, abs/1903. 022488, 2019.
[18] J. Gilmer, S. S. Schoenholz, P. F. Riley, O. Vinyals, and G. E. Dahl. Neural message passing for quantum chemistry. In /CML, volume 70 of Proceedings of Machine Learning Research, pages 1263-1272. PMLR, 2017.
[19] F. D. Giovanni, L. Giusti, F. Barbero, G. Luise, P. Lio, and M. M. Bronstein. On over-squashing in message passing neural networks: The impact of width, depth, and topology. In ICML, volume 202 of Proceedings of Machine Learning Research, pages 7865-7885. PMLR, 2023.
[20] F. D. Giovanni, T. K. Rusch, M. M. Bronstein, A. Deac, M. Lackenby, S. Mishra, and P. Velick- ovic. How does over-squashing affect the power of gons? Trans. Mach. Learn. Res., 2024, 2024.
[21] J. H. Giraldo, K. Skianis, T. Bouwmans, and F. D. Malliaros. On the trade-off between over- smoothing and over-squashing in deep graph neural networks. CIKM, pages 566-576. ACM, 2023.
11

---

[22] L. Giusti, T. Reu, F. Ceccarelli, C. Bodnar, and P. Liò. CIN++: enhancing topologiaa message passing. CoRR, abs/2306.03561, 2023.
[23] M. Grohe. The descriptive complexity of graph neural networks. TheoretiCS, 3, 2024.
[24] A. A. Hagberg, D. A. Schult, and P. J. Swart. Networkx: Network analysis with python. pages 11-15, 2008.
[25] W. L.. Hamilton, Z. Ying, and J. Leskovec. Inductive representation learning on large graphs In NIPS, pages 1024-1034, 2017.
[26] S. loffe and C. Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. In ICML, volume 37 of JMLR Workshop and Conference Proceedings, pages 448-456. JMLR.org, 2015.
[27] S. Jegelka. Theory of graph neural networks: abs/2204.07697, 2022.
Representation and learning. CoRR,
[28] C. I. Kanatsoulis and A. Ribeiro. Counting graph substructures with graph neural networks, In ICLR, 2024.
[29] S. Khalife and J. Tonelli-Cueto. Is uniform expressivity too restrictive? towards efficient expressivity of graph neural networks. CoRR, abs/2410.01910, 2024.
[30] D. P. Kingma and J. Ba. Adam: A method for stochastic optimization. In ICLR (Poster), 2015.
[31] T. N. Kipf and M. Welling. Semi-supervised classification with graph convolutional networks. In ICLR (Poster), 2017.
[32] Klicpera, J. GroB, and Günnemann. Directional message passing for molecular graphs. In ICLR, 2020.
[33] Q. Li, Z. Han, and X. Wu. Deeper insights into graph convolutional networks for semi-supervised learning. In AAAI, pages 3538-3543 AAAI Press, 2018
[34] A. Longa, V. Lachi, G. Santin, M. Bianchini, B. Lepri, P. Lio, F. Scarselli, and A. Passerini. Graph Neural Networks for temporal graphs: State of the art, open challenges, and opportunities, July 2023. URL http: //tp////avvvv///a org/ abs /tt///bb/22222111/ 01018. arXiv:2302.01001 [cs].
[35] A. Loukas. How hard is to distinguish graphs with graph neural networks? In NeurlPS, 2020.
[36] C. Morris, M. Ritzert, M. Fey. W. L. Hamilton, J. E. Lenssen, G. Rattan, and M. Grohe. Weisfeiler and leman go neural: Higher-order graph neural networks. In AAAI, pages 4602- 4609, AAAI Press, 2019.
[37] C. Morris, Y. Lipman, H. Maron, B. Rieck, N. M. Kriege, M. Grohe, M. Fey, and K. M. Borgwardt. Weisfeiler and leman go machine learning: The story so far. CoRR, abs/2112.09992. 2021.
[38] C. Morris, F. Frasca, N. Dym, H. Maron, i. i. Ceylan, R. Levie, D. Lim, M. M. Bronstein, M. Grohe, and S. Jegelka. Position: Future directions in the theory of graph machine learning. In ICML, 2024.
[39] A. Paszke, S. Gross, F. Massa, A. Lerer, J. Bradbury, G. Chanan, T. Killeen, Z. Lin, N. Gimelshein, L. Antiga, A. Desmaison, A. Köpf, E. Z. Yang, Z. Detioo, M. Raison, A. Tejani, S. Chilamkurthy, B. Steiner, L.. Fang, J. Bai, and S. Chintala. Pytorch: An imperative style, high-performance deep learning library. In NeurlPS, pages 8024-8035, 2019.
[40] P. Pellizzoni, T. H. Schulz, and K. M. Borgwardt. Graph neural networks can (often) count substructures. In ICLR, 2025.
[41] Topping, D. Giovanni, P. Chamberlain, Dong, and M. M. Bronstein. Understanding over-squashing and bottlenecks on graphs via curvature. In ICLR, 2022.
[42] P. Velickovic. Message passing all the way up. CoRR, abs/2202. 11097 2022.
12

---

[43] Q. Wang, D. Z. Chen, A. Wijesinghe. S. Li, and M. Farhan. NS WL: A New Hierarchy of Expressivity for Graph Neural Networks. September 2022. URL https:// openreview net. wnt.at//oorrrrttitttAAAtogg///
[44] X. Wang and M. Zhang. How powerful are spectral graph neural networks. In ICML, volume
162 of Proceedings of Machine Learning Research, pages 13341-23366 PMLR, 2022.
[45] B. Weisfeiler and A. Leman. The reduction of graph to canonical form and the algebra which appears therein. Nauchno- sanchho--Tchhnnchhekkyy Informatsia, 2(9):12-16, 16, 1968.
[46] Wollschläger, N. Kemper, L. Hetzel, Sommer, and S. Günnemann. Expressivity and generalization: Fragment- biases for molecular gnns. In ICML, 2024.
[47] K. Xu, C. Li, Y. Tian, T. Sonobe, K. Kawarabayashi, and S. Jegelka. Representation learning on graphs with jumping knowledge networks. In ICMI., volume 80 of Proceedings of Machine Learning Research, pages 5449-5455 PMLR, 2018
[48] K. Xu, W. Hu, J. Leskovec, and S. Jegelka. How powerful are graph neural networks? In ICLR, 2019.
[49] K. Xu, J. Li, M. Zhang, S. S. Du, K. Kawarabayashi, and S. Jegelka. What can neural networks reason about? In ICLR, 2020.
[50] Xu. Towards a complete logical framework for GNN expressiveness. In ICLR, 2025.
[51] M. Zaheer, S. Kottur, S. Ravanbakhsh, B. Póczos, R. Salakhutdinov. and A. J. Smola. Deep sets. In NIPS, pages 3391-3401, 2017.
[52] B. Zhang, S. Luo. L. Wang, and D. He. Rethinking the expressive power of gnns via graph biconnectivity. In ICLR, 2023.
[53] B. Zhang. J. Gai, Y. Du, Q. Ye, D. He, and L. Wang. Beyond weisfeiler-lehman: quantitative framework for GNN expressiveness. In ICLR, 2024.
[54] M. Zopf. 1-wl expressiveness (almost) all you need. In IJCNN, pages 1-8, IEEE, 2022.
13

---

NeurIPS Paper Checklist
Claims
Question: Do the main claims made in the abstract and introduction accurately reflect paper's contributions and scope?
Answer: [Yes]
Justification: Our abstract and introduction accurately reflect three main claims: 1) traditional expressivity theory has limitations that prevent it from explaining real-world GNN performance, 2) proposed MPC captures practical limitations of MPNNs while pre- serving theoretical impossibility results, and 3) MPC correlates with empirical performance where expressivity theory fails to differentiate. In 3, thoroughly analyze limitations of expressivity theory. $ 4.2 establishes formal connections between MPC and practical phe- nomena like over-squashing and under-reaching, while proving MPC preserves expressivity theory's impossibility results. $ 5 empirically validates that MPC complexity correlates with MPNN performance across multiple tasks.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results be expected to generalize to other settings.
It is fine include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We provide dedicated section that discusses key limitations ($ 6), including our abstraction from model parameterization, limited support for attention-based models, challenges with exact complexity computation, and the fact that complexity values should only be compared across single dimension of freedom.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-ter system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they seale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimess.
14

---

While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: All theoretical results include the full set of assumptions and are properly numbered and cross-referenced. For Lemmas and 5.3 we provide only an informal version in the main body and defer formal version to App. C. All proofs of theorems can found App. C.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
We provide comprehensive experimental details in App. D.I, including model architectures, hyperparameters, and dataset specifications that allow reproduc- tion of all experiments. An algorithm for simulating MPC complexity values is de- fined with pseudocode in Algorithm 1. Additionally, we provide our code at https: / //www.cs.com cs. tum. de/ hee/daml/messaaa wwweeessag--ppssingge. complexity/
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
15

---

(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm.
(b) If the contribution is primarily
model architecture, the paper should descrihe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the partieular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
5. Open access to data and code
Question: Does the paper provide open access the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: We provide our code at https://www cs. cstttt.......................... tum. /a/mmmm/
message paaniggg-a-ii------- passing-complexity// complexity/.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.. cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: / httppssccc/bblcc//uuuuu/ httpi//gggiieee/eeeuuubiiiiii CoodeSubdieieeeeeeee
www.bbmmsssiooooooooi..o for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: All experimental details including the type of optimizer, the model hy- perparameters and how they were chosen are provided in App. D.1. Key experimental parameters are also detailed in the main paper (e.g., number of layers L for retaining infor- mation task). For our experiments on benchmark datasets, we use the standard pre-defined splits.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
16

---

The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: All performance results are averaged over 3 random seeds. For all lineplots. we use Seaborn's 's built-in functionality which displays shaded regions representing the 95% confidence interval around the mean.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall
run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
All compute resources used for every experiment are detailed in App. D.I.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https://neuripss httpr//pp.p.ppppplcc/ccssttttees
Answer:
[Yes]
Justification:
The research conforms in every respect with the NeurlPS Code of Ethics.
Guidelines:
17

---

The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is special consid- cration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: Our work is foundational theoretical research on graph neural network ex- pressivity and does not have direct societal impacts. We introduce complexity measure that helps understand GNN limitations but does not create new capabilities that could be misused.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairesss considerations (e.g., deploymeen of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
Safeguards
Question:
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Answer: [NA]
Justification: Our work introduces theoretical complexity measure for GNNs and uses only synthetic graphs and public benchmarks (ZINC, LRGB) that pose no risk for misuse. We release models or datasets that require safeguards.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
18

---

We recognize that providing effective safeguards is challenging, and many papers do require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: We properly cite all datasets (ZINC, LRGB) and software libraries (Py Torch Geometric) used our work. We include their licenses our experimental details section (App. D.1).
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g.. website). the copyright and terms of service of that source should be provided.
If assets released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re-packaged, both the original license and the license of the derived asset (if it has changed) should provided.
If this information is not available online, the authors are encouraged to reach out to the asset's ' creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moddl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
19

---

Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if' applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing. editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: LLMs were not part of the core method development of this work.
Guidelines:
The answer NA means that the method development in this research does involve LLMSs as any important, original, or non-standard components.
Please refer to our LLM policy (https (bttps://eeur) //nerrips....// cc/ /ote//ooreencco2225////////////e for what should or should not be described.
20

---

A Extended Related Work
Existing efforts address the limitations of iso expressivity theory typically target only one limita- tion, focusing on either overcoming its task-agnostic nature, the unrealistic assumption of lossless information propagation, or its binary characterization of expressivity.
Task-Specific expressivity While iso expressivity theory is task-agnostic, recent works have proposed studying specific graph-related tasks to get a more fine-grained hierarchy of the expressivity of higher-order MPNNs (beyond the WL test). For example, expressivity has been analyzed in the context of substructure recognition [53] and graph biconnectivity [52].
A separate line of work characterizes the node-level functions computable by MPNNs in terms of fragments of first-order logic [23]: Barceló et al. [3] showed that standard MPNNs with sum aggrega- tion and ReLU activations can uniformly express graded modal logic. Subsequent work analyzed the effect of different activation functions [29], and more recently, these logical characterizations were extended to various higher-order MPNNs [50].
However, all these works only provide existence results: they show whether there exists some model instance of an architecture that can solve a task or not. Such results neglect practical limitations like information loss (seem in phenomenons like over-squashing or over-smoothing) occurring in trained real-world models. Moreover, the characterizations are inherently binary (solvable or not), offering limited insight into the practical difficulty.
Accounting for Lossy Information Propagation. Some works explicitly account for the lossy information propagation inherent in practical GNNs. Negative results have been derived by consider- ing limited hidden dimensions [35] or by analyzing the maximal "mixing" of node representations [20]. However, these approaches are restricted to specific model architectures and provide binary results, rather than nuanced understanding of how lossy propagation impacts practical performance in arbitrary tasks.
Beyond Binary Expressivity. To address the binary nature of classical expressivity theory, some works define distances between graphs to represent the difficulty of distinguishing them. Examples include tree-based distances [12). graphon-based distances [7], and Wasserstein- distances [10]. While these metrics provide a continuous measure, they remain task-agnostic and are independent of model architecture
Restricted Graph Families. Classical expressivity theory evaluates GNNs on the set of all possible graphs, which may not align with the restricted graph families encountered in real-world applications. Recent works examine expressivity within specific graph families, such as planar graphs [13] and outer-planar graphs [4], providing more relevant insights for certain domains.
Higher-order MPNNs and variants of the WL Test. A plethora of higher-order MPNNs [5, 6, 46, 36] have been developed to surpass the WL test in iso expressivity. To quantify and compare their expressivity corresponding (higher-order) variants of the WL test [36, 5, 46, 43) have been developed. However, we show in Tab. 1 similar to Zopf [54] that the standard WL test already suffices to distinguish almost all graphs in standard benchmarks. Hence, expressivity theory statements that only focus on expressivity beyond the WL test cannot offer explanations for performance differences of models that are at least WL expressive on these popular benchmarks.
Table 1: Fraction of graphs with unique WL hashes (ig- noring isomorphic graphs). Similar to Zopf [54].
Dataset
Unique WL
Reddit- Reddit-Binary Peptides
100%
100%
Mulag
100%
Enzymes
100%
100%
Many of these higher-orde order methods, along with an overview of WL variants, are comprehensively surveyed in Morris et al. [37].
ZINC-subset
100%
ZINC-full
99.99%
Real world limitations of GNNs Several fundamental limitations of GNNs have been identified in practical applications. Under-reaching [3] occurs when nodes cannot access information from distant parts of the graph due to insufficient layer depth, effectively limiting the receptive field of each node. Over-squashing [1, 41, 19] describes how graph topology can create bottlenecks in message passing, preventing effective information flow between nodes even when they are theoretically within each
21

---

other's receptive field. This is distinct from over- smoothing [33], where increasing the number of layers causes node representations to become indistinguishable as all nodes converge the same representation. These limitations highlight crucial gap between theoretical expressivity and practical capabilities of GNNs.
Practical power of standard GNNs A few other works highlight a disconnect between theoretical expressivity limitations and the practical capabilities of standard GNNs. While expressivity theory establishes that standard GNNs cannot count any non-trivial substructure [11], recent studies reveal important exceptions. Pellizzoni et al. [40] identify specific conditions on the graph family g under which standard GNNs can count substructures and demonstrate that many real-world datasets satisfy these conditions for important substructures like small cycles. Similarly, Kanatsoulis and Ribeiro [28] showed that adding randomized node features enables standard GNNs to count small cycles.
Task-Model Alignment. Beyond expressivity, our work aligns with efforts to quantify the compati- bility between a model and its target task. For instance, Xu et al. [49] define on higher level the concept of algorithmic alignment between general neural network and an algorithm, showing that higher alignment leads to lower sample complexity. Similarly, our proposed complexity measure can be interpreted as quantifying the alignment between a specific graph task and the message passing steps needed to solve it for given MPNN architecture.
In summary, while existing works address individual limitations of classical expressivity theory, none provide a unified framework addressing all limitations.
B Extending MPC: More Architectures, Graph-Level Functions, and Feature Noise
In the following, we show how MPC can be extended to a wide range of architectures beyond standard MPNNS and graph-level functions. Additionally, we sketch a potential extension to include additional sources of complexity, such as feature noise. Furthermore, we sketch how one could easily adapt the framework operate on temporal graphs.
B.1 General Message Passing Framework
In the following, we provide general message passing framework for MPC that captures wide range of existing MPNN architectures M.
While standard MPNNs Ms perform message passing directly the input graph G, other architec- tures operate transformed message passing graph G t(G):
msgi ( (h(=1) mag' ( 11) else
if w = and hi = upd' (mmm ww U
m 10
The transformation / defines the MP graph structure & by determining which nodes exchange messages. While standard MPNNS used the input graph G directly as G, recent architectures introduce modifications like virtual nodes [18), rewired edges [41], or higher-order graphs [46]. We assume preserves original nodes Ve while potentially adding nodes or adding/modifying edges. A general MPNN architecture M is defined through the transformation i and the number of layers L. characterizing which nodes exchange information. It abstracts away from the specific choice of aggregation method and update function, which is sensible simplification since many recent models treat the choice of aggregation method hyperparameter and use MLPs as update functions (providing universal function approximation capabilities..
This framework captures many existing MPNNs (potentially with some simplifying assumptions):
Standard MPNNs
Standard architectures like GCN [31]. GraphSage [25], GIN [48] perform
message passing directly on the input graph, i.e., I = (G) = G. They differ in aggregation method mean). Some architectures, like GCN, restrict the possible choices of
(mean, sum, Beggre-normalize msg and upd function and do not distinguish self-loops from normal edges, i.e., msg, = msg1- Note that, as discussed above, our MPNN framework abstracts away these architectural choices.
22

---

Virtual nodes, rewiring and additional features Modifications to the input graph such as addi- tional virtual nodes [18], edge rewiring [41], or additional node features (e.g., including substructure information like in GSN [8]) can be directly modeled in our framework by choosing the appropriate transformation function t.
Higher-order MPNNS Higher-order MPNNs that augment the input graph with higher-level struc- tures are also representable. FragNet [46] builds an additional higher-Ievel graph of fragments (for an arbitrary fragmentation scheme). We will focus here on the FragNet model with a fragmentation scheme identifying rings without edge representations. We model this by adding additional fragment nodes connected to all constituent input nodes, with labels corresponding to fragment types. The CIN [5] model follows a similar approach by having representations for all original nodes, edges, and CW-cells (rings). Upper messages are messages from nodes to their corresponding edge rep- resentation, and from edges to the corresponding ring representation (if any). Boundary messages are messages between nodes sharing an edge and between edges that are both in the same ring. The initial representation of CW cells an aggregation of the features of their constituent nodes. We represent edges and CW cells (rings) by additional nodes in G. The initial feature of a ring node is the aggregation of all node features of the ring. We have edges between: neighboring original nodes, original nodes and their edge nodes, edge nodes within the same ring, and edge nodes and their rings (if any). Note that we cannot represent in our framework that boundary messages also contain information from the corresponding upper neighborhood. Importantly, both fragNet and CIN use different update functions for different types of messages. This too can not be modeled in our formulation of Mt instead, we assume just one update function. While one could, in theory, extend framework include different kinds of message updates, we choose against this as existing framework, with this simplification, already captures the models' empirical performance well.
3D GNNs: DimeNet Next, we sketch how our framework can model GNNs incorporating 3D information, exemplified by DimeNet [32]. 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 61 (2/, tx), e2 = (vk, U/) E E, have (e1, e2) E É. The angular and distance features of DimeNet can then be incorporated as edge/node features in this transformed message passing graph.
Given this general message passing framework, we can naturally extend MPC from standard MPNNS Ms to general MPNNs M by applying lossyWL to the transformed message passing graph G t(G) rather than the input graph:
Definition B.1 (MPC). For G, Gv. function over Gy and L-layer MPNN M. define
MPCM G) = log PloossyWI.. Fov f.(G)).
Analogously, we can extend our baseline WLC to general MPNNs M: Definition B.2. For G v e Gv. a function f over Gv and a L-layer MPNN M, define
for irWL) Ksv [u)
WLCM(fe,
(0 clse
B.2 Graph-Level Tasks
Additionally, we can generalize MPC to graph-level tasks f: 9 R*. A graph-level output of an MPNN architecture A is learned by aggregating all final node representations h/ and transforming the aggregated result. This can be represented in MPNN framework by having an additional readout node Vglobal that receives messages from all other nodes only in the + 1-th layer. MPC is then defined over the graph, node pairs {G, Ugloba) G E 9).
B.3
Additional Sources of Complexity: Feature Noise
While MPC is designed to isolate the complexity arising from the message passing topology, it can also be extended to include additional sources of complexity arising in practice, such as feature noise, thereby providing more unified practical understanding of tisk-difficulty. We sketch here such a possible extension:
23

---

Let X be the true feature of node v, and let X, be the observed noisy feature according to some noise distribution X. N₂ (X,). Our probabilistic formulation naturally accommodates this additional source of difficulty by modifying the initialization step in Definition 4.3 to incorporate noise:
lossyWL, = X, with X ~ (X.).
Notice that this general model of feature noise subsumes missing features special case. All in all, this demonstrates a promising direction for incorporating additional practically relevant sources of complexity within unified framework in future work.
B.4 Temporal Graphs
MPC can be naturally extended to temporal graphs as well. Consider snapshot graphs G' time point T, defined in Longa al. [34]. The complexity for a task fo then becomes time dependent:
MP (fu. G) - log Pllossy (ll (t)GT) Fov fo(G)).
This extension opens up interesting directions for future work, such as analyzing how the complexity of specific tasks evolves over time the underlying graph changes.
C Proofs and Extended Theorems
In this section, we present all proofs and extended/formal versions of the theorems in the main body, Extended Notation Let denote function composition. Additionally, let a be the preimage of a function a X + YY i.e., a (y) fx E X a(x) = y). If X is clear from the context, we will simply write a == 3 instead of a Fx 3. We define WL, == WL and lossyWL, := JossyWL.. iee, we omit the layer superscript for the final layer L. Additionally, we say a message m/ in the lossyWL test lost, if Z 0, otherwise we say it was successful. Let (G) denote the final output h.: of a model node Additionally, we will say set S 2 of sets over universe U is upward-closed if A E S implies that any B S U with A C also in S, i.e., E S. 1 [condition] denotes the indicator function defined if the condition is true and 0 else. We use the terms "ring" and "cycle" interchangeably.
We will often represent a probabilistic function with domain X and finitely many possible proba- bilistic outputs in (each with rational probability) as a deterministic function 7(x, 8) or T. (xx) with seed drawn uniformly random from finite set of seeds S. We will sometimes (slightly abuse notation and) write T(Z, s) Fxxs 3(x) for a non non- coo--rbbabilistic function 3 X - Z if
Val X.Vs' S: T(z, s) -(x',( ,s')
B(z) 3(x))
iee. if one can deduce B(x) from the output of T(x, s). With this notation, we can nicely write Definition 4.4 as
Plr(z) Fx 3(x)] == P. P.es|T(a; Fxxs 3(x)].
Additionally, we will define the concept of necessary and sufficient messages that we will use in several proofs.
Definition C.1. We call set S of messages (or rather message identifiers (a, b, 1)) sufficient for function fo on graph G, it is possible to deduce fu from lossy given that the messages were successful, or more formally:
A (o,b,))SS
Z =1,-1 = lossyWL, Fgv fG)
Definition C.2. We call set $ of messages necessary for function fo on graph G, if it not possible to deduce Jn from lossyWL, if any of the messages in were lost, or more formally:
3(a,b,1) E ES: 2
lossyWL, (())) Ko, f.(G).
Lastly, we define the probability of set $ of messages as the probability that all messages were successful:
24

---

Z
Figure 7: Example for Definition 4.1 showing sets X,Y, Y, and functions o, B. We have a F B as a. Contrarily,
(xx) F B(x) for all E X. By Lemma C.4, there exists function with 8 3 * a as there exist 21, 22 E X with 3(x1) = (ax)) but a(z)) + a(x2). Intuitively, this means that function more fine-grained than 3.
Z
Oxy Oleg
Figure Example for Definition 4.4 showing sets X, Y. Z and a probabilistic function a and deterministic function B. The probabilistic function functions ( Oag where the seed is drawn uniformly at random. We then have Pla(x1) F= 3(x1)] = 1. Intuitively, we can deduce ((x)) for every probabilistic outcome of cx(1). Whereas for 22, 43, have P(a((22) F 8(x2)] P(a((z)) F ((ra) = 0.5.
be represented by two deterministic
Definition C.3, Define the probability set messages as
P
II
PiZZ, = 1].
(o.b,))
To simplify notation, we will prove all statements Apps. C.2 C.5 for Ms. The proofs for general model architectures M follow completely analogously by performing lossy WL on G t(G) instead of G. i.e., by replacing G with t(G) and Ms with M.
C.1 Function Refinement
First, we will now prove the following useful lemma (see also Fig. 7).
Lemma C.4 (Refinement). If. and only if. a += 3, there exists a function T such that 3 = 7
Proof. First, we will show that 3 implics that there exists a function 7 with 8 = T o a. Define T: a(X) + Z as
-(y) B(x) for x c
This function is well-defined because by definition of F, we have for all æ 22 E a (y): 3(x1) ((x2). And it follows immediately that 3 r a.
Next, we will show that a 3 implies that there does not exist such a function 7 with 8 = T a. Assume for the sake of contradiction that 7 exists. From F B, it follows that there exist 3i, 22 with a(x1) a(x2) but (xx) # ((x2). Then
T(a(x1)) r(a(z2)) = 3(x2) + ((x1) ((((1)))
Hence, T(a(21)) r(a(z1)) which is contradiction.
25

---

C.2
Connection of standard MPNNs to WL
Next, we will show that there exists model in our standard MPNN framework that least as expressive as the WL test. In fact, there exists a model performing exactly the WL test:
Lemma C.5. There exists a model M E MM that performs exactly the WL test, for all G, E Gv M,(G) (G).
Proof. We show this inductivcly over the number of layers L. For this follows immediately from (G) x, and MG) X, for any 0-layer model M M. For -= >>> 0, assume that there exists a model M with M WL. Then consider model M that executes M in the first - layers:
ms (WL 1-1)
if ===v and hy := upd (agg (4m I w e U
m
msg] (W
else
We now need to show that there exist functions msgg msgi agg and upd such that for all G, e
h = WI = HASH (WI, ((WI. u Na(
Zaheer et al. [51] show that one can represent any ceermutation-ivaarinn function aXX) operating on a set X as 3 (Exex p(z)). As we can differentiate between msg1, and msgo is easy to see that there also exists functions msg', msgi and upd such that with sum-aggregation, we have:
WL. = HASH (WI. [WW u E (a
= upd'
msg1 [w=o] (WI
WE WENo)))Uf
= upd'
Σ wENo(o)Ufu}
m
= hh
..)
C.3 When MPC becomes infinite: Connections to iso expressivity theory
We will prove important theoretical properties of MPC. For this, we will first prove the following useful lemma showing that MPC is infinite precisely for the same tasks and graphs where WLC is infinite:
Lemma C.6.
We have:
Pflossy PllossyWL...G) Fov fo(G)) >
if and only if
Fg) (G).
Proof. We will say a message m is visible to lossy WL, if there exists a / length walk from b to
We will first assume that WL. Fg. (G). The proof idea for this direction is that with positive probability JL loses no to e visible message and performs exactly the normal WL test. This coloring will always be different from lossyWL. colors with visible lost messages and can, hence, by assumption, be used to deduce f..
Formally, notice that with probability > 0 lossyWL, performs exactly the normal Weisfeiler-Lehmmnn test at node v. i.e., no to lossy WL, visible messages are lost (Z = for all visible messages). Now consider such a seed E S for which no visible messages are lost. Then for all seeds $2 S and G2 w E Gy for which messages visible to lossyWL, (G₂) are lost, we have
lossyWL, s1) * (G2, (G2,
26

---

because of the injectiveness of the HASH function, and only lossy WL w (t(G), s2) has visible lost messages m 0. Hence, we have for any $2 E S and G2, w E Jv
lossyWL, $1) = lossy WT, (G2, $2) = WL. (G) (L,)(G)
as lossy WL,, (G, $1) lossyWL... G22 $2) implies that 82 loses no to w visible messages, i.e., performs exactly the WL test at w as well. Therefore,
lossy BasyyW,,GGss s1) Fouxs WL.(G). And from the assumption and the transitivity of F, it follows that
JossyWL,(G, (L. fc(),
yielding
PlossyyLL,(G) Fs, [o(G)) >0
Now we show that from (G) Kg, f.(G), follows that P/lossy , (G) Fev fo(G)] = 0, i... losing messages cannot make the probabilistic WL test more expressive than the deterministic WL test. WL, # (G) implies there G', E Gy with (G) = WL"((") but [x(G) o [G²(")). Then, for every seed 81 S,, there exists seed 82 E S such that
(G, = Jo. 82),
(the messages to WL equivalent nodes in G and G' are lost). Hence by Definition 4.4, P(lossyWL, Fgv fo(G)) =
Using this, we can prove when MPC becomes infinite:
Theorem 4.6 (Infeasibility). The complexity for G, v E Gy and function f is MPC G)= =0 if and only if there exist G', Gy such that (G) # (G') but M.(G) Mw (G') for all model instantiations E M.
Proof. Assume first that there exists G, Gy with MPCMs (f,G) co. By definition, this implies that
Pllossy (oasyyWL,CG) Fav fo(G)] = 0.
From Lemma C.6 it follows that
WL. Kgv (G)
By definition of F this implies that there exists G', w Gy with (L) = (L" but f.(G) + far (G'). Now follows from the fact that the WL test upper-bounds the expressivity of standard MPNNs Ms [36] that also all models M E M cannot differentiate G, from G", w, i.e. M.)
Mi (G').
Now, assume that MPCMs (f, + oc. By definition, this implies that PllossyWL.(G) Fgv fo(G)) 0.
From Lemma C.6 it follows that
WL. Fev Ju(G).
By definition of F= this implies that there do not exist G', w E Gy with WL) = WL. but (G) * (G'). Now note that by Lemma C.5 there exists a model M E MMs performing exactly the WL test. Hence, there exists M E MM such that there does not exist G², w E Gy with (G) = M (G') but (G) + (G').
With this, we can also globally characterize which functions an MPNN can express:
Lemma 4.7. There exists no model instantiation M E M such that Mo(G) = Jv(G) for all G. E Gv if and only if there exists G, Gy with MPC G) =0)=00 xc.
Proof. If there exists M E M such that My(G)- = (G) for all G, E Gv, it follows directly from Thm. 4.6 that there does not exist G, v E By with MPC (Sv, G) xo.
If there does not exist G, v E Gy with MPC (Se, G) = co, this implies that for all G, v E Gy PllossyWI..(G) Fov (.)) > 0.
27

---

Hence, by Lemma C.6 for all G, E Gv
WLo(G) Fov fo(G).
So
WL Fgv f.
By Lemma C.5 there exists M E Ms with M Fg, f. And by Lemma C.4 a function such that for all G, E Gv
M.) f.)
But then we can squash the function also in the last update layer M, i.c., upd T upa'. With this, we have found model M such that
(G Gz)
for all G, v E Gv.
As special case, we can recover the iso expressivity statements defined in Definition 3.1. For this, we use the graph-level formulation of MPC. Note that all previous theorems generalize completely analogously also to this graph-level version.
Lemma C.7 (MPC preserves impossibility statement of Iso Expressivity). Let be graph isomor- phism test. Then M is at least as expressive as a if and only if there does not exist G E g with (PC OC.
Proof. If MPC G) = oo for some G E 9" then by Thm. 4.6, there exists G' E g such that M(G) M(G) for all M M but aGG) * (G")). From this follows directly that M is not at least expressive as a.
Now assume that there does not exist G E g" with (P G) Then by Lemma 4.7 there exists M E M with M(G) = aGG) for all G e g". Therefore, M at least as expressive as a. L
C.4 Bounding MPC: Function Refinement & Compositionality
Next, will prove bounds MPC relating to how fine-grained task is and how it can be decomposed into individual subtasks. First, we prove that a more fine-grained function cannot have lower complexity than the coarser function refines:
Theorem 4.8 (Function refinement). Let f be function that is more fine-grained than i.e. Fov g. Then for any G, v E Gy: MPCM((f. G) MPCM( G).
Proof. The intuitive idea for this proof is that if the set of successful messages in lossy WL suffices deduce f, it is also always possible to deduce the more coarse- -aasseggaiied g.
First, note that }= is transitive. Then, it follows directly that for every seed e S for which Besy Favxs fu also lossy WL, s) Favxs Ge. Therefore
P[lossyWL,(G) Fs. fo (G)] < PllosyWWL,(C) Fav (o)),
And hence,
(PC G) Z MPC G).
Now, we will prove the compositional property of MPC. Lemma 4.9 (Task Triangle Inequality). Let and be functions, and denote foucatenntiinggunccio oufputs. Then for any G, E Gv: (frlll,, G) MPC G) MPC (go, G).
Proof. Let Lg be a sufficient set of messages for f. on graph G. Let L, denote the set of all such sufficient sets Ly. Notice that L, is upward-closed, i.e., any superset of L, E L is also sufficient and therefore in ILy. This intuitively means that more successful messages cannot hurt. Define analogously T. for the task g.
For set of messages S define (S) = 1[S E L.]. Then, a is an increasing function over sets, i.e., S SCS S' = aS) S (S"),,, because L, is upward-closed. From the Kattin--Kattele--Giibbe
28

---

(FKG) inequality, we then have (where S follows the distributions of the sets of successful messages IossyWL):
(lar(S) ( [S)
implying
( (os,,,,,))) (.)
2 (G) f((G) PlloosyWL,.G)) (PP g.(G))
and thereby
(PCl MPCM((fs G) MPC G).
C.5
Connection of MPC to Over-squashing and Under-reaching
To formalize Lemma 40, we first need to define when a task fu requires information from another node u.
Definition C.8. We say task fo over graphs G requires (node-feature) information from a node u there exists G¹, G² E G that are identical except for the node features X, * X and
(G' + (o
So task requires information from node u, if without this information it would be impossible compute fu.
With this in place, give formal version of Lemma 4.10:
Lemma C.10. Consider a task fo and a graph G E 9 where fo requires node-feature information from Then
MPCM G) 2 log ((I*)vu).
Proof. Intuitively, we will show that order deduce fo from lossy there needs to exist an L-length walk from where all messages were successful (as fe requires information from u). The probability of this can be turn upperbounded by the random walk prohability.
Formally, we need to show that
PlossyWL,(CG) fc(G]] S (I")
For this will upper bound P|lossyLL,,GG) fG)) by the L step random walk probability from v to u.
For this, let Was be the event that there exists æı, #T-1 E Va with
Za
22
z3
24-1 2 1
ZL 2
We then say Z contains (L-length) walk from b. Additionally, let W be the event that Z contains specific walk from to with fully specified intermediate nodes Tj. Then the probability of Wi. is (using the independence of the variables Z):
ab
Pl Pi 1] TP [2 = 1)... ..'. 12
-,,a Inges
IESZ-1
This is precisely the probability for a random walk from to a over all intermediate nodes x; with edge probabilities I. If we now consider all L-length walks W Wi...., W from a to b, we get:
IP IP(W..) S PP(W +
P(W+)
PP L-sepp random walk from b to with edge probabilities I]
(14) bm
Now note that if not W... i.e., Z contains no walk from to it is by Definition C.8 not possible to deduce (G) from lossyWI., as v will not receive any information from u.
Hence,
Plloss WL) fo(G) < P(W Tsn
< (1 va.
29

---

With this we can easily prove Corollary 4.11:
Proof. If du v) > L there exists no L. step walk from to on G. Therefore (Th).u 0 and by definition of MPC:
MPCMu(fe,G oc.
C.6 Complexity bounds in 5
First, will prove useful lemmas upper and lower bound the MPC complexities Lemma C.11. Let S be sufficient of messages for function fo on graph G. Then
M G) S log(((()).
Proof. By Definition C.1 we have:
P[
A (a,b,
E = 1]
P[]]
And corresponding lower bound:
Lemma C.12. Let S be a necessary set of messages for a function fo on graph G. Then
MPC(M, fur G) 2 - (og(())
Proof. It follows directly from Definition C.2 that
(t))))WL,(t(())) F f.(G) P A
1%,, =
(a,b,1)
TP(S]
Retaining information We will first prove the complexity bound Lemma 5.1 for the task of retaining the initial node feature: [o(G) X,-
Lemma 5.1. Assume the degree 2 2. Then the expected MPC complexity for this task Eg (M G)] grows at least linearly with L, i.e., in (LL), for all MPNNs M.
Proof. Note that for 2, Lab < for all nodes a, VG for all model architectures except the MLP. Then, with positive probability, all messages are lost in layer I, i.e., Z 0 for all a, E VG- Hence, only with probability & < any message is successful in layer l. A necessary condition for retaining the initial node feature is that in every layer, at least one message is successful. Thereby, we have the following lower bound:
PlossyWI,((CG)) S dL.
follows immediately, that
MPC fu. G) 2 L (l0))
Propagating Information We will now prove the complexity bound Lemma 5.2 for the task GG) X of propagating information from a source node to a target node v at distance D= (u)
Lemma 5.2. Assume L is the minimum depth required to solve this task with M. Then the expected complexity R., M G)) is S log(n) for GCN-VM while for standard MPNNs is > D log(r) provided n is sufficiently large given D.
30

---

Proof. Trivially, for the MLP baseline and D > O, we have:
MPCMLP(fer. G) = 0c.
For GCN-VN, notice that each original node G has degree r + (r neighbors in the input graph, the self-loop, and the connection to the virtual node) and the virtual node has degree 1/n. It is easy to see that for = 0 and D = I, the minimal depth required to solve this task
= 0 and L = I, respectively. Trivially, the MPC complexities for these cases are 0 and log(r + 2). Both are S 2 log(n).
For D 2 2, the minimal depth required to solve this tasks is L = 2: One sufficient set of messages consists of the message from u to the virtual node (which has probability of success 1/n) and from the virtual node to (which has probability of success 1/(r + 2)). By Lemma C.11, this implies
MPCacN G) & log(n(r 2)).
And hence,
MPCCcNvvN(Fr G) < log(n).
For all other MPNNs, notice that the probability that G, v Gy contains cycle where every node is in the D-hop neighborhood around v approaches 0 as n - oa for a given D. Hence, we can choose n such that this probability is S e for any e O.
Then, we can bound the expected complexity by (as MPC is always non non-negative):
En (MC G)]
2 P[no cycle around u| (
G) no cycle around v]
(1 - e) EG (MPCMM(er, G) no cycle around v)
where "no cycle around v" denotes the event that there is no cycle where every node is in the D-hop neighborhood around v.
Next, we need to bound EG MMC G) no cycle around v). For this, we will show that (f,, G) 2 ())( for any G, E Gy without a cycle around v. It is easy to see that for all considered MPNNs without virtual node, the minimal depth required
solve this task is then I, = D. Then, a necessary set of messages consists of the messages on the only (as there is no cycle around v) D-length path from u to v. Each message on this path has a success probability < 1/(r 1). By Lemma C.12, this implies:
MPC, 2 log((r + 1)
Finally, by choosing e small enough, we have
EG, [Mp G)]
2 (1 -c) E.G [MPCM G) no cycle around v)
2 (1 1-c) c) log(((r + P)
2 D log(r)
Extracting topological information Lastly, we consider the ring transfer task. To simplify nota- tions here, we will consider the complexity of fG( X,, for single node u on the cycle of size that v is part of. The tasks involve 1) identifying that u is part of the cycle 2) propagating the node feature information from u to w. We will now prove the complexity bounds in Lemma 5.3:
Lemma C.13. Assume L is the minimal depth required solve the task fe(G)= = X,, with architec- ture M where u is a node on the cycle of size that is part of. Further assume that there is only single cycle in the [s/2] -hop neighborhood of v. Then, the expected MPC complexities are:
For CIN & FragNet: O(log(s))
For GSN: < [s/2] log(r+1)
For all others: 2 slog(r)
is the minimal depth required to solve this task. With L= 2 a sufficient set of messages involves a message from to the fragment node that represents this cycle (with message success probability 1/s) and from the fragment node to v (with message success probability 1/(r + 2)). Using Lemma C. the bound follows immediately.
Proof. FragNet: Notice that for FragNet
31

---

CIN: Again, for CIN L = 2 is the minimal depth required to solve this task. A sufficient set of messages involves a message from the ring node (which contains as initial encoding all node features from the nodes in the ring) to an edge node. And from the edge node to Notice that the edge node has degree 8 + (an edge to every other edge node in the cycle, an edge to the ring node and two edges to the original nodes) and has degree 2r + 1 (edges to all neighboring nodes in G. edges to corresponding edge nodes, and self-loop). Hence, we have message success probabilities 1/(s + 2) and 12 1). Again, using Lemma C.11, the bound follows immediately.
Notice that for GSN the cycle information is already contained in the initial node-feature. So the task is simply to propagate the node feature information to for distance of at most [s/2]. Hence, sufficient set of messages consists of the messages on path of length L S [s/2] from to v, each with success probability 1/(r + 1). Again, using Lemma C.11, the bound follows immediately.
GSN:
For all other MPNNs, the minimum depth required to solve this task is I = 8 (for L s, is impossible detect the cycle). It is easy to see that in order to identify the cycle at node v, there needs to be a set of successful messages going around the full cycle returning to v. Or more formally, for a cycle consisting of nodes u, a1, 022 .... 0s-1; U, we define two possible message traversal patterns:
All other MPNNs:
Cycley == %:003 = 1 22
A A T
T8--10 =1
0102
and
Cycle, := 2 1 2
1 Z 20, =
2 aiv =I
10,
Additionally, node must retain its unique node feature throughout all L layers to recognize that the returning messages originated from itself.3 Hence, a necessary condition for lossyWL, (G)
is
Z = 1 A Zee = 1A... A Z = =
A (Cycle, V Cycley).
Therefore, we have
(P]) F fo (G)] S PIZ = 1A Zz, 1 Z A (Cycle, V Cycle,)].
Notice that Pl 1/(r + 1) for any message, as every node has degree and the additonal self-loop. Then, because of the independence of all Ze we have
Pl) F. s P(Z = 1 7
A
Z A (Cycle, Cy
P = 1 A z = 1 ... A Z 1] P(Cycle, V Cycley]
$ 1/2 P[Cyyle V Cycle,)]
S 1/2- 2 [[Cycle,
1 r + 1
1
While this bound is not tight (we'v ve made several relaxations), it is sufficient to establish the 2 s slog(r) MPC complexity lower bound.
MLP: The complexity trivially infinite.
Lastly, we give short proof why WLC is 0 for this task. For this, we generally show that for graphs with unique node features any (at least WI--expressive) architecture with at least one layer can distinguish all non-isomorphic graphs, and hence solve any task.
Lemma C.14. Let G be a family of graphs with unique node features, ie., for any G E G, no two nodes v. w E Va have the same node features. Then the WL output after one iteration (WL; u E VeB differs for any two non con-isomorphic graphs in G.
Proof. Let G1, G2 E be two non-isomorphic graphs. Suppose, for contradiction, that the WL output after one iteration is the same for both graphs, i.c., ([ ([WL; v E Var = [WL | w E Vez as multisets.
A sufficient condition for this task would be even stronger, requiring all nodes in the cycle to retain their features until the messages through the cycle reach them.
32

---

Since all node features in 11 and G2 are unique within each graph, the initial WL labels WL, are dis- tinct for all nodes e in each graph. After one iteration, each WI.,, consists of the node's 's original feature combined with the multiset of its neighbors' features, i.e., WL, = (WL., {[WL u E B))
Given that (f WLL U E V&1 H = (WLL, | w E VG2B. there must exist a bijection f VG1 + VG2 such that WL WL for all v E Vai.
This implies that for each v E VGi: (1) WL. = WL)(() (the original node features match), and (2) (WL2 a E [N) ([W w E N(f(v))B (the multisets of neighbor features match).
From (1), since node features are unique within each graph, f maps each node in G1 to a unique
node in G2 with identical features.
From (2), for each E VG1. there must exist a bijection go N(O)) N(f(u)) such that WL. WL (w) for all u E N(v).
(w)
Due to the uniqueness of node features and (1), we must have g.(u) f(u) for all u E N(o). This implies that for all u E VC1 and u E Vei u E (w) è f(u) E (N(())) Therefore, f is an isomorphism between G1 and G2, contradicting our assumption that the graphs are non-isomorphic. Thus, the WL output after one iteration must differ for any two non-isomorphic graphs in g.
D Additional results and Experimental Details
We present the following additional results:
Extended figures showing all considered model architectures across all tasks.
Robustness analysis demonstrating that MPC predictions hold across different hyperparame- ter choices (hidden dimensions) for the information retention task.
Validation on Erdös-Rényi (ER) graphs, confirming that MPC accurately matches perfor- mance trends also different synthetic graph family.
Real-world validation on graphs from ZINC [15] and peptides datasets [14] showing that MPC explains performance better than classical expressivity theory for real-world graph structures.
Results showing that insight on synthetic proxy tasks can mirror performance trends on real-world benchmarks where the precise tasks are unknown.
Additionally, we carefully describe all experimental details and setups.
D.1 Implementation Details and Experimental Setup
We use pytorch [39] and -orme-gcometric [17] (rcleased under an MIT license) for the implementation of all models. For optimization, we use the Adam optimizer [30]. The training, validation and test sets containing random r r-regular graphs are generated using networkx [24]. For all standard MPNNs we use their pytorch geometric implementation. Note that GSN [8] only specifies the additional node features and not the downstream MPNN. We use the most common MPNN, GCN, as downstream MPNN for all experiments for GSN. For CIN [5] we use our own implementation following exactly the method proposed in their paper. Additionally, for FragNet, we use a custom implementation of their FR- model without edge representations using GCN base MPNN. For CIN, GSN, and FragNet we use a fragmentation scheme identifying every cycle of size at most 6 (unless otherwise noted). For all models we use an initial feature embedding layer and a final output MLP. Additionally, we use BatchNorm [26] for normalization. We found little difference between learning rates in (0.001, 0.005, 0.01} for all models and tasks. The shown results are for the learning rate 0.005. We train all models for all settings using three different seeds for maximum of 50 epochs, showing the average results. All experiments are conducted on NVIDIA GeForce GTX 1080 GPUs with 16GB memory allocation per job. Training times vary by model architecture, ranging from 10-30 minutes. Monte Carlo simulations for complexity calculations run on a single Intel Xeon E5-2630 v4 CPU (2. (2.20GHz) and complete in under 10 seconds. The peptides dataset of the Irgb [14] is released under a CC BY-NC 4.0 license. The ZINC dataset [15] is distributed under a custom license (free to use for everyone).
33

---

MLP
GCN
GIN
GCN-VN
ACC
MPC
WLC
ACC
MPC
WLC
ACC
MPC
WLC
ACC
MPC
WLC
ACC
MPC
WLC
Num Layers:
1.00
0.0
0.0
1.00
0.0
0.0
1.00
0.0
0.0
1.00
0.0
0.0
1.00
0.0
0.0
1.0
Complexity
2 1.00
0.0
0.0
1.00
6.9
0.0
0.92
1.5
0.0
0.91
1.5
0.0
0.92
1.9
0.0
Accuracy
1.00
0.80
1.00
0.34
3.6
1.00
0.0
0.0
1.00
2.4
0.0
0.29
3.2
0.0
0.26
3.2
0.0
0.31
4.1
0.0
GSN
FragNet
CIN
GAT
GATv2
ACC
MPC
WLC
Acc
MPC
WLC
ACC
MPC
WLC
ACC
MPC
WLC
ACC
MPC
WLC
Num Layers: L
1.00
0.0
0.0
1.00
6.0
0.0
1.00
0.0
0.0
1.00
0.0
0.0
1.00
0.0
0.0
Camplexity
Accuracy
0.888
2.2
0.85
1.00
0.62
0.65
2.2
0.35
2.8
0.0
0.20
2.9
0.0
1.00
3.2
0.0
0.55
2.8
0.0
0.52
2.8
0.0
0.27
3.2
0.0
0.16
3.3
0.0
1.00
3.6
0.0
0.47
3.2
0.0
0.41
3.2
0.0
Figure 9: Test accuracy for retaining initial node features compared with complexity measures MPC and WLC for all models. Simulated MPC (in contrast to WL-based WLC) matches trends in empirical accuracy (for all models except for Sage and CIN), capturing increasing difficulty with depth.
D.2 Retaining information
For the task (G) = X.. randomly generate 3-regular graphs with 50 nodes where each node is randomly assigned to one of ten possible classes. We use a training set of size 2000, a validation of size 500 and test set of size 2000. We simulate the complexities using Monte Carlo simulation on 100 different graphs from the test set, and for each graph 1000 trials (with the same method explained in App. D.3). Fig. 9 shows the accuracy and simulated MPC complexity for all considered model architectures. Additionally, Fig. 10 shows that the complexity measure is robust to changes the hidden dimension hyperparameter, i.e., trends in MPC complexity align with empirical performance also for different hidden dimensions. Moreover, Fig. 11 shows how complexity and accuracy changes for different levels of sparsity.
Erdös-Rényi graphs We repeat the retaining information experiment with Erdōs-Rééy' (ER) graphs with 50 nodes and node connection probability p 0.06. Fig. 12 shows that generally, trends in MPC complexity align with trends in empirical performance (except for Sage and CIN, the two models that directly optimize the weight of the residual channel) as well for ER graphs
34

---

Hidden Dimension: 32
AcC
MPC
WLC
Acc
MPC
WLC
AcC
MPC
WLC
Acc
MPC
WLC
ACC
MPC
WLC
Num Layers:
11.00
0.0
0.0
1.00
0.0
0.0
1.00
0.0
0.0
1.00
0.0
0.0
1.00
0.0
0.0
1.0
Complexity
I 11000
0.0
0.90
1.5
Accuracy
-100
0.0
0.0
0.66
0.0
0.83
2.2
0.87
2.2
0.0
0.74
0.0
60 -1.00
0.0
0.0
0.36
2.8
0.0
0.34
2.8
0.0
0.33
2.8
0.0
0.33
2.9
0.0
b. Hidden Dimension:
FragNet
Acc
MPC
WLC
Acc
MPC
WLC
Acc
MPC
WLC
Acc
MPC
WLC
Acc
MPC
WLC
Num Layers:
-1.00
0.0
0.0
1.00
0.0
0.0
1.00
0.0
0.0
1.00
0.0
0.0
1.00
0.0
0.0
1.0
Comploxity
~1000
0.0
0.0
0.0
0.91
1.5
0.90
1.5
0.0
0.92
0.0
Accuracy
-1.00
0.0
0.87
2.2
0.88
2.2
0.0
0.83
0.0
1 -1.00
0.0
0.0
0.35
2.8
0.0
0.38
2.8
0.0
0.38
2.8
0.0
0.18
2.9
0.0
1100
0.27
C. Hidden Dimension:
FragNet
MPC
WLC
MPC
MPC
Num Layers-L
-1.00
0.0
0.0
1.00
0.0
0.0
1.00
0.0
0.0
1.00
0.0
0.0
1.00
0.0
0.0
1.0
Complexity
2 ~1000
0.0
0.0
0.92
0.0
0.91
1.5
0.90
1.5
0.0
0.91
1.7
0.0
Accuracy
1.00
0.0
0.0
0.35
2.8
0.0
0.39
2.8
0.0
0.33
2.8
0.0
0.10
2.9
0.0
1100
0.0
0.0
0.29
0.0
0.24
3.2
0.26
3.2
0.0
0.11
0.0
Figure 10: Influence of hidden dimension hyperparameter. Test accuracy for retaining initial node feature task compared with complexity measures MPC and WLC for hidden dimension size 32, b. 64 and 128 (for selection of models). Even with larger hidden dimensions, MPNNs face fundamental ove-ssmoothin limitations that MPC captures while WLC does not. MPC consistently predicts performance trends across all hidden dimension choices.
35

---

Degree?2
MLP
GCN
GIN
GSN
FragNet
Acc
MPC
WLC
Acc
MPC
WLC
ACc
MPC
WLC
ACC
MPC
WLC
ACC
MPC
WLC
1100
1.0
Complexity
I 1.00
0.0
0.0
0.87
1.2
0.0
0.88
12
0.0
0.88
12
0.0
0.87
12
0.0
Accuracy
Num
1.000
0.0
0.0
0.44
2.2
0.0
0.46
2.2
0.0
44
2
0.0
0.5
2
0.0
1.00
Dogree
FragNet
Acc
MPC
WLC
AcC
MPC
WLC
ACC
MPC
WLC
ACC
MPC
WLC
Acc
MPC
WLC
1.0
O
1.000
0.0
0.0
1.00
0.0
0.0
1.00
0.0
0.0
1.00
0.0
0.0
1.00
0.0
0.0
Complexity
1100
Accuracy
1.00
0.0
0.0
0.82
2.2
0.0
0.86
2
0.0
0.88
2
0.0
0.86
2.5
0.0
0.5
11000
0.0
0.0
0.29
3.2
0.0
0.23
3.2
0.0
0.27
3
0.0
0.10
3.4
0.0
Dogree 4
MLP
GCN
GIN
GSN
FragNet
Acc
WLC
ACC
WLC
ACC
WLC
ACC
WLC
Acc
WLC
1.00
1.00
1.00
1.00
1.00
1.0
Complexty
N -1.00
0.0
0.0
0.91
1.7
0.0
0.91
0.0
0.91
0.0
0.92
2.1
0.0
Accuracy
11000
0.5
9 -1.00
0.0
0.0
0.27
3.2
0.0
0.32
3.2
0.0
37
3
0.0
114
3.5
0.0
-1.00
Figure 11: Influence of degree the random regular graphs. Test accuracy for retaining initial node feature task compared with complexity measures MPC and WLC for hidden dimension size 32, b. 64 and c. 128 (for a selection of models). Unlike MPC, MPC captures the increasing difficulty graph degree increases, demonstrating the importance of considering the graph topology.
Retaining Information Task with ER graphs
MLP
Sage
GCN
GIN
GCN-VN
GSN
FragNet
CIN
GAT
GATY2
Number of Loyers:
-1.00 0.0
1.00 0.0
1.00 0.0
1.00 0.0
1.00
0.0
1.00 0.0 1.00 0.0 1.00 0.0 1.00 0.0 1.00 0.0
0.8
~ -1.00 0.0 1.00 0.7
0.87 1.3
0.81 1.3
0.87 1.9
0.88
1.3
0.88
1.5
1.00 1.7
0.83 1.3
1.00 1.3
Complexity
Accuracy
11.00 0.0 1.00 1.3
0.59 1.8
0.62 1.8
0.61
3.0
0.57
1.8
0.37
2.0
1.00
2.2
0.60 1.8
0.61 1.8
0.4
6 -1.00 0.0
1.00
0.44
2.1
0.46
2.1
0.45
3.7
0.48
2.1
0.31
1.00
2.4
0.45
0.57
2.1
-1.00 0.0
1.00
1.9
0.37
2.3
0.22
2.3
0.39
4.2
0.37
2.3
0.30
0.10
2.6
0.53
0.50
2.3
Figure 12: MPC captures practical difficulty across different graph families. Test accuracy and average simulated MPC complexity for retaining initial node features on Erdós-Rényi graphs (50 nodes, connection probability p = 0.06). Models are trained on 2000 graphs. MPC complexity (C) correctly increases with layer depth (WLC would be 0 everywhere), demonstrating that our complexity measure generalizes beyond random regular graphs to capture practical learning difficulties.
36

---

MLP
Sage
GCN
1.0
Distance
Telt Accuracy
Distance
0.7
0.4
100
200
100
200
500
1000
1000
Stze
GIN
GCN-VN
GSN
1.0
Test Accuracy
Distance
100
200
500
1000
100
200
500
1000
100
200
500
1000
Complesty
Size
FragNet
CIN
GAT
Distance
Distannce
Distance
Test Accuracy
100
200
500
1000
100
200
500
1000
100
200
500
1000
Dataset Size
Dataset
Dataset Size
GATv2
That Accuraty
Distance
0.4
0.1
100
200
500
1000
Dataset Size
Figure 13: Test accuracy by training data size for the information propagation task (z) X, for different distances D. Colored by average simulated MPC complexity per distance. MPC correctly captures the increasing sample complexity with distance and the performance advantage that virtual node offers for long-range dependencies.
D.3 Propagating Information
For the task GG) X., we randomly generate 3-regular graphs with 50 nodes. In each graph, randomly select target node v. For given distance D, select node with distance D from v. Then, e gets the unique label 0 identifying it as target node, u is randomly assigned target label in {L...., 10}. and all other nodes get random label from {11, ........ 20). For each distance D, use training sets of different sizes and a validation set of size 500 and a test set of size 2000, We simulate the complexities using Monte Carlo simulation for each graph 1000 trials. Fig. 13 shows the average test accuracy by training data size and Fig. 14 shows the test accuracy and the complexity for the dataset size 1000.
100 different graphs from the test set, and
Erdós-Rényi graphs Again, we repeat the information propagation experiment with ER graphs with n 50 nodes and node connection probability p 0.04. Fig. 15 show that trends in MPC complexity align with trends in empirical performance as well for ER graphs.
Peptides dataset Additionally, repeat the information propagation task graphs from the real-world Spprides-func/peptties--ttt dataset. It comprises larger peptide molecules that require models to consider long-range interactions [14]. Therefore, the information propagation task, testing
37

---

MLP
Sage
GCN
GIN
GCN-VN
Acc
WLC
Acc
WLC
Acc
WLC
MPC
WLC
Acc
MPC
WLC
0.10
1.00
2.2
0.0
1.00
2.7
0.0
1.00
2.7
0.0
1.00
3.4
0.0
Distance:
0.10
1.00
3.2
0.0
1.00
3.2
0.0
1.00
3.2
0.0
1.00
3.8
0.0
0.10
1.00
6.8
0.0
1.00
4.9
0.0
0 4.
4.9
0.0
1.00
4.5
0.0
0.10
0.10
9.5
0.0
0.10
6.2
0.0
0.10
6.2
0.0
1.00
4.7
0.0
0.10
0.10
0.10
0.10
1.00
4.7
-0.97
-0.79
FragNet
GAT
GATv2
Acc
MPC
WLC
Acc
MPC
WLC
Acc
MPC
WLC
Acc
MPC
WLC
Acc
MPC
WLC
1.00
2.7
0.0
1.00
2.9
0.0
1.00
3.2
0.0
1.00
2.7
0.0
1.00
2.7
0.0
Distance:
0.99
3.2
0.0
0.89
3.4
0.0
1.00
4.0
0.0
1.00
3.2
0.0
1.00
3.2
0.0
0.59
4.9
0.0
0.22
5.2
0.0
0.41
6.6
0.0
0.81
4.9
0.0
0.77
4.9
0.0
0.4
0.10
6.2
0.0
0.10
6.5
0.0
0.0
0.59
6.2
0.83
6.2
0.10
0.10
0.11
0.90
0.90
-0.90
Figure 14: Test accuracy for retaining initial node features compared with complexity measures MPC and WLC for the information propagation task f.(G)= X,, for all models (for dataset size 1000). Simulated MPC matches trends empirical accuracy (highly negative Spearman correlated ps). capturing increasing difficulty with distance while preserving impossibility statements from WLC.
Information Propagation Task with ER graphs
Sage
GCN-VN ACC C
FragNet
ACC
ACC
Acc
Acc
Acc
Acc.
Acc C
ACC
C
ACC
10.0
1.0
0.90
0.8
Comple Complesity
Accurac
Distance:
0.6
0.10
0.1010.0
0.11
6.3
0.79
4.6
0.10
6.3
0.10
0.10
8.8
0.11
0.78 4.7
0.10
0.10
0.10
0.2
Figure 15: Test accuracy by distance for the information propagation task fo(G) X., (for varying train dataset sizes) and simulated MPC complexity (C) for ER graphs with n 50 nodes and connection probability p = 0.04. MPC again matches empirical performance trends, demonstrating that our complexity measure generalizes beyond random regular graphs to capture practical learning difficulties.
the models' ability to exchange information over varying distances, is particularly well-suited for this dataset.
Similar to our approach for random regular and ER graphs, we randomly select one node of each graph in the dataset as target node v. For given distance D, we randomly select node with distance D from v as the source node. Then, v gets the unique label identifying it as target node, u randomly assigned label in {1,... ... 10), and all other nodes get random label from {11, 20). We then randomly sample different numbers graphs from the dataset as train graphs. In summary, this allows analyze and isolate the information propagation capability of models real-world graphs requiring long-range interactions.
Fig. 17 shows again a connection between sample complexity needed to achieve perfect accuracy and MPC complexity, underlining that MPC is also good predictor of performance for graph topologies occurring in the real world.
38

---

Real-workh Long-range Graphs: Peptides
MLP
Sage
GCN
1.0
Text Accuracy
Distance
Distance
Distance
0.7
0.4
0.1
100
200
500
1000
100
200
500
1000
100
200
500
1000
Dataset Size
Dataset Size
Datase: Size
GIN
GCN-VN
GSN
1.0
Accuracy
Distance
Distance
Distance
0.7
0.4
0.1
Complexity
100
200
500
1000
100
200
500
1000
100
200
500
1000
Dataset Size
Dataset Size
Dataset: Size
FragNet
CIN
GAT
1.0
Teat Accuraty
Distance
Distance
Distance
0.7
0.4
0.1
100
500
1000
100
500
1000
100
500
Dataset Size
Dataset Size
Datase: Size
GATv2
Accuracy
Distance
0.7
0.1
100
200
500
1000
Dataset
Figure 17: MPC captures task difficulty real-world graphs. Test accuracy by distance for the information propagation task [o(G) = X,, across varying training dataset sizes, with simulated MPC complexity shown for real-world graphs from the ppppiidesfuuncppppidesssttttt Higher MPC complexity corresponds to greater learning difficulty, as evidenced by increased sample complexity requirements, demonstrating that MPC effectively captures practical task difficulty beyond synthetic graph families.
dataset [14].
39

---

Table 2: Comparison of MPC for ring transfer task (for ring size 6) and Mean Absolute Error on prediction penalized logl, both on graphs from subses, Trends in MPC on the synthetic ring task match trends on the real-world task, where identifying large rings is important.
Standard MPNNs
Substructure Encodings
Substructure Graphs
GIN
GraphSage
GCN
GSN
FragNet
CIN
MPC (Ring Task)
7.3
7.3
7.3
3.6
3.2
2.9
MAE (ZINC)
0.53
0.40
0.37
0.12
0.078
0.077
D.4
Extracting topological information
For the ring transfer task, we use randomly generated 4-regular graphs with n = 50 nodes conditioned having cycle of size The multilabel classification task fu (G) is then to classify which labels
node (and smaller cycle). Each node is randomly assigned
unique label in between and 50 are part of the cycle that contains For each cycle size, generate training sets of varying size, validation set of size 1000 and a test set of size 10000. For GSN, FragNet, and CIN we use a fragmentation scheme identifying cycles of size at most For all models, we use the minimal number of layers with which they can solve all tasks: for FragNet and CIN: 2, for all other models: 5. For CIN and FragNet, we explicitly compute the complexities. For all other models, we use the bounds provided in Lemma 5.3. All results show the binary average precision. Fig. 18 shows the average precision and complexities for this task for the maximal dataset size of 10000. Additionally, Fig. 19 shows the average precision in relation to dataset size.
Erdós-Rényi graphs Again, we repeat the ring transfer task with ER graphs with 50 nodes and edge probability p = 0.04 conditioned on having ring of size at node v. The label assignment is done in the same way as for the random regular graphs. Fig. 20 shows that complexities also align with MPC complexities for ER graphs
ZINC dataset We additionally test the ring transfer capabilities the models on real-world graphs from the ZINC molecular regression dataset [15]. The ZINC dataset comprises small molecules and the benchmark task is to predict the penalized logP score which involves the number of cycles. Therefore the graphs from the ZINC dataset well-suited to test our models cycle detection capabilities. For this, we first filter all graphs to contain rings of size s. Second, we randomly choose
MLP
Sage MPC WLC
GCN
GIN
GCN-VN
AP
MPC
WLC
AP
AP
MPC
WLC
AP
MPC
WLC
AP
MPC WLC
Ring Size
0.42
0.76
4.2
0.0
0.73
4.2
0.43
4.2
0.0
0.71
4.8
Complexity
0.36
0.55
5.5
0.0
0.58
5.5
0.32
5.5
0.0
0.57
6.4
0.33
0.45
6.9
0.0
0.48
6.9
0.24
6.9
0.0
8.0
0
GSN
FragNet
CIN
GAT
GATv2
Average Precision
MPC
WLC
AP
MPC
WLC
MPC
WLC
AP
MPC
WLC
MPC WLC
1.0
Ring Size
0.95
0.96
2.7
0.0
0.96
2.5
0.73
4.2
0.0
4.2
0.5
+
0.70
2.8
0.82
3.0
0.0
0.86
2.7
0.56
5.5
0.0
5.5
0.50
3.5
0.0
0.63
3.2
0.0
0.66
2.9
0.0
0.50
6.9
0.0
0.47
6.9
0.0
Figure 18: Test average precision for the ring transfer task compared with complexity measures MPC and WLC across all models (dataset size 10000, MPC values for all standard MPNNs are lower bounds). Simulated MPC aligns with empirical accuracy trends, capturing both the increasing difficulty with ring size and the superior performance GSN, FragNet, and CIN due to their cycle- oriented inductive biases.
40

---

Ring Size 3
Models
Ring Size
Average Precision
1.0
CIN
CIN
FragNet
FragNet
GSN
Complexity
GSN
Comple eipiiityy
0.6
GATv2
GCN
0.4
Sage
GATv2
GCN
GCN-VN
GAT
GAT
0.0
GCN-VN
Sage
500
1000
2000
500010000
GIN
500 1000 2000
500010000
MLP
Dataset Size
Dataset Size
MLP
GIN
Ring Size 5
Models
1.0
Average Precision
FragNet
0.8
Complextyy exity
GSN
GCN-VN
0.4
GCN
0.2
GATv2
Sage
500
1000
2000
500010000
MLP
GIN
Figure 19: Test average precision and by dataset size for the ring transfer task in relation dataset size. Models are colored by their simulated MPC complexity.
Ring Transfer Task with ER graphs
MLP
Sage AP
GCN
GIN
GEN-YN
GAT
GATY2
A
AP
CIN
Awerage Precision
5.2
Complexity
6
7.0
0.6
8.7
0.4
Figure 20: Test average precision and average MPC complexity (C) for the ring transfer task with ER graphs for all models for training data size 10000 (complexity values for standard MPNNs are lower bounds), demonstrating again that MPC matches performance trends for graphs from different distribution.
41

---

Real-world Graphs: ZINC
MLP
Sage
GCN
GIN
GCN-VN
MPC
WLC
AP
MPC WLC
MPC
WLC
AP
MPC
WLC
AP
MPC
WLC
0.43
0.0
0.92
3.7
0.0
0.85
3.7
0.0
0.55
3.7
0.0
0.71
4.5
0.0
Ring Size
Complexity
0.37
0.0
0.67
5.0
0.0
0.69
5.0
0.0
0.41
5.0
0.0
0.58
6.0
0.0
5
7.5
5
0.34
0.53
7.3
0.0
0.65
7.3
0.0
0.40
0.0
0.58
8.8
0.0
GSN
FragNet
CIN
GAT
GATV2
Average Precision
AP
MPC
WLC
AP
MPC
WLC
AP
MPC
WLC
AP
MPC
WLC
AP
MPC
WLC
1.0
0.98
1.8
0.0
0.98
2.5
0.0
1.00
2.3
0.0
0.91
3.7
0.0
0.93
3.7
0.0
Ring Size
0.93
2.5
0.0
0.94
0.99
2.6
0.0
0.75
0.0
0.5
0.84
3.1
0.0
0.93
0.97
2.7
0.0
0.72
6.2
0.70
6.2
0.0
0.77
3.6
0.0
0.91
3.2
0.0
0.93
2.9
0.0
0.69
7.3
0.0
0.67
7.3
0.0
Figure 22: Test average precision compared with complexity measures MPC and WLC for the ring transfer task for real-world graphs from the ZINC dataset, where cycle detection is crucial subtask (dataset size 10000, complexity values for standard MPNNs are lower bounds). MPC can account for performance differences in this real-world dataset that classical expressivity theory misses: The superior performance of GSN, CIN, and FragNet cannot be explained by their increased iso expressivity(LLCC for all MPNNs) but by their reduced MPC due their cycle-oriented inductive bias.
node u that part of cycle for each graph. The labels are assigned in the same way as for the random regular graphs and the ER graphs.
Figs. 22 and 23 show that trends in MPC complexity align again with empirical performance. Again, the superior performance of GSN, CIN, and FragNet cannot be explained by their increased iso expressivityWLLC for all MPNNs) but by their reduced MPC due their cycle-oriented inductive bias.
Additionally, compare results the synthetic ring transfer task to empirical performance the standard ZINC molecular property prediction task (penalized logP), where ring identification is crucial for accurate predictions. As shown in Tab. 2, trends in MPC on the synthetic ring task match trends in empirical performance on ZINC: architectures with lower ring detection complexity (GSN, FragNet, CIN) significantly outperform standard MPNNs both tasks. This demonstrates that MPC analysis of targeted proxy tasks can provide valuable insights into real-world performance, even when exact target functions unknown complexity values computationally infeasible to derive.
42

---

Real-world Graphs: ZINC
Ring Size 3
Models
Ring Size 4
Models
1.0
CIN
CIN
Average Precision
FragNet
FragNet
GSN
Complexity
Complexity
0.6
GATv2
GATv2
0.4
Sage
GAT
GCN
Sage
GCN-VN
GCN-NN
200
500
1000
2003000
GIN
200
500
1000
200D000
Dataset Size
MLP
Ring Size 5
Models
Ring Size
Models
1.0
CIN
CIN
Average Precision
0.8
FragNet
FragNet
GSN
Complexxe eexilyyxty
GSN
GAT
GAT
Complexity
0.4
GATv2
GATv2
GCN
GCN
0.2
Sage
GCN-VN
0.0
GCN-VN
Sage
200
1000
2008000
GIN
200
500
1000
2008000
GIN
Dataset Size
MLP
Dataset Size
Figure 23: Test average precision compared with complexity measures MPC and WLC for the ring transfer task for real-world graphs from the ZINC dataset in relation to dataset size. MPC captures the performance advantage of the cycle-oriented GSN, CIN, and FragNet across different dataset sizes.
43

---

D.5 Simulation of Complexities
We show in Algorithm for the exemplary task propagating information from source node u to target node how the complexities can be efficiently simulated using Monte Carlo simulation.
Algorithm Propagating Information Simulation
Input: Source node u, target node v, number of trials T, graph G, edge weights I, and maximum steps L
success 0 for /. = to T do
active u for 8 = to I. do
newActive for e E active do
0
for u E Na(v) U {0} do if Random (0, 1) < Ieu then newActive t newActive U {u}
end if end for end for active newActive end for u E active then success success + 1 end end for
Output: lollloossccc (success/T)
44


Reviews:
[{"review_id": "flpL5LDpQV", "reviewer": "Reviewer_1N1Q", "summary": "This paper studies the topic of understanding (expressive or complexity) power of a graph neural network model that has traditionally been done using Weisfeiler leman tests. Such existing theory for GNNs are limited which is well-known. This paper provides an excellent discussion on this limitation and proposes Message Passing Complexity (MPC) as an alternative framework. It argues that traditional WL expressivity measurements has 2 limitations (i) it assumes idealized conditions that may not often reflect practical GNN behavior and (ii) it provides only binary characterizations rather than quantifying difficulty in a task. As a result, this paper introduces MPC, which is called a continuous complexity measure based on a probabilistic improvement of the Weisfeiler-Leman test called lossyWL. Through lossyWL message loss during propagation can be measured with probabilities based on the influence matrix which is a function of the graph structure. Controlled experiments on information retention, propagation and topological characteristics are done on both synthetic and real graphs where the MPC measure is proportional to task complexity and model performance which traditional WL like tests fail to incorporate or model. Overall, the paper is clearly written, the proposed method helps explain phenomenons such as virtual nodes, long distance complexity, etc. which are of much interest in GNN literature.", "questions": "included in weaknesses", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "Strengths:\n- The paper includes a convincing discussion on the limitations of existing WL expressivity framework and shows how normalized adjacency matrix can be used to improvise the WL kind of coloring.\n- The proposed MPC framework provides a new continuous measure to understand how difficult a task is and what would its affect be on message passing mechanism based GNNs.\n- MPC helps explain effectiveness of components such as virtual nodes and challenges of distant information propagation which are not traditionally explained by WL test.\n- The proxy tasks design in both synthetic and real world graphs and the evaluation using multiple architectures demonstrates correlation between MPC and performance, and is well executed.\n- Overall, the insights provide a better understanding of message passing as a mechanism and how certain shortcomings can be addressed, for instance why virtual node improves reachability.\n\nWeaknesses:\n- One analysis that seems missing (and this perhaps may not be straightforward) is how the proposed framework quantifies/ranks current representative GNN architectures? This has often been seen for prior studies with WL tests.\n- There can be complexity in computing MPC in real tasks.\n- The implications of MPC in future architecture design is not explicit in the paper which can be through a resulting model, or through guidance on how the presented insights can help develop better architectures.", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\n## 1. Complexity in computing MPC\nFirst, 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).\n\n**Practical solutions**: We address this limitation through two complementary approaches:\n\n1. **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.\n2. **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.\n\nIn 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.\n\n## 2. MPC for future architecture design\nFirst, 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.\n\n**Theoretical Contributions on future architectural design**\n- 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).\n- 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.\n- 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).\n\n\n**Concrete examples of how MPC can guide model improvement** for specific capabilities needed in certain domains:\n- **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.\n- **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.\n\nWe have included a discussion of the concrete ways in which MPC can benefit future MPNN design in  Sec. 6.\n\n## 3. Ranking of MPNNs\nWhile 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**:\nOur 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.\n\n**Therefore, we provide task-specific complexity comparisons** (e.g., Lemmas 5.1 - 5.3) rather than universal rankings:\n- Ring Transfer task: FragNet/CIN < GSN < standard MPNNs (with/without virtual node)\n- Information propagation task:  GCN-VN < all other\n\nThese 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).\n\nIn summary, the task-specific formulation of MPC enables a **more fine-grained and application-specific architecture comparison than universal rankings**.\n\n## Summary\nWe 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).\n\n\\[1] Fey et al. Hierarchical Inter-Message Passing for Learning on Molecular Graphs. arXiv:2006.12179\n\n\\[2] Wollschläger et al. Expressivity and Generalization: Fragment-Biases for Molecular GNNs. ICML 2024.\n\n\\[3] Bodnar et al. Weisfeiler and Lehman Go Cellular: CW Networks. Neurips 2021.\n\n\\[4] Fey et al. Relational Deep Learning: Graph Representation Learning on Relational Databases. arXiv:2312.04615."}, {"review_id": "yxbzJQEbHL", "reviewer": "Reviewer_rbkh", "summary": "This paper proposes a novel framework, Message Passing Complexity (MPC), to evaluate the capabilities of GNNs beyond traditional isomorphism-based expressivity theory. Different from prior work that primarily focuses on whether a GNN can distinguish graph structures in theory, MPC provides a continuous, task-specific measure that quantifies the difficulty of solving a task via message passing under realistic constraints such as over-squashing and under-reaching. Built on a probabilistic extension of the WL test, MPC better explains empirical performance across diverse tasks and architectures. Extensive theoretical analysis and empirical validation demonstrate that MPC correlates well with real-world performance.", "questions": "- The framework assumes that node features are reliable and informative. In practice, GNNs often deal with noisy or missing features and labels, and it is unclear how MPC accounts for this.\n- Can the proposed MPC framework extend to dynamic or temporal graphs where structure and features evolve?", "limitations": "Please see weaknesses and questions.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 2, "strengths_and_weaknesses": "Strengths:\n\n- The paper introduces the MPC framework as a novel extension to traditional expressivity theory. It provides a continuous, task-specific, and new measure for evaluating GNNs.\n- MPC explicitly models real-world issues such as over-squashing and lossy information propagation, bridging the gap between idealized expressivity theory and the practical performance of GNNs.\n- The paper conducts extensive experiments across different tasks and widely used general GNN architectures to support the practical relevance of MPC.\n\nWeaknesses:\n\n- It does not evaluate MPC on 3D GNNs like DimeNet++ [1], SphereNet [2], or PaiNN [3], which are widely used in molecular tasks. Whether MPC extends to architectures with geometric or directional message passing remains unclear.\n\n- The MPC is not evaluated on large-scale benchmarks such as ogbl-ppa, ogbn-products, and ogbg-molhiv [4]. Thus, MPC's scalability and practical applicability in real-world settings remain unverified.\n\n[1] Gasteiger J, Giri S, Margraf J T, et al. Fast and uncertainty-aware directional message passing for non-equilibrium molecules[J]. arXiv preprint arXiv:2011.14115, 2020.\n\n[2] Liu Y, Wang L, Liu M, et al. Spherical message passing for 3d graph networks[J]. arXiv preprint arXiv:2102.05013, 2021.\n\n[3] Schütt K, Unke O, Gastegger M. Equivariant message passing for the prediction of tensorial properties and molecular spectra[C]//International Conference on Machine Learning. PMLR, 2021: 9377-9388.\n\n[4] https://ogb.stanford.edu/docs/dataset_overview/", "was_revised": true, "final_justification": "The authors have addressed all the issues I proposed during the review process, so I raised my score from 3 to 4.", "rebuttal": "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. \n\nWhile 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.\n\n## Weakness 1: 3D GNNs\n\nWhile 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).\n\nTo 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. \n\nThis 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.\n\n## Weakness 2: Large-scale Benchmarks\n\nFirst, 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.\n\nTo 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:\n\n| Num Layers | MPC | Accuracy |\n|------------|-----|----------|\n| 2          | 3.6 | 0.44     |\n| 4          | 4.7 | 0.26     |\n| 6          | 5.2 | 0.10     |\n| 8          | 5.3 | 0.10     |\n\n**Key observations**: \n- MPC trends match trends in empirical performance. \n- GCN training required >15 hours on A100 GPUs while MPC simulation required <10 minutes on consumer CPU  (using approach in App. D.5).\n\n\nThis 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.\n\n## Question 1: Missing features\n\nWhile 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.\n\nWe 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.\n\nFor a first empirical demonstration, we conduct our information propagation experiment (D=5, GCN) with varying levels of missing node feature probabilities:\n\n| Missing Feature Probability | MPC | Accuracy |\n|----------------------------|-----|----------|\n| 0.0                        | 4.9 | 0.69     |\n| 0.2                        | 5.1 | 0.47     |\n| 0.4                        | 5.4 | 0.14     |\n| 0.6                        | 5.8 | 0.11     |\n\nThe results show that the adapted **MPC accurately captures the increasing difficulty with feature loss** in this initial experiment. \n\nMore 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.\n\n## Question 2: Temporal Graphs\nWhile 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]. \n\n\nFor **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:\n\n| Time Step | MPC | Accuracy |\n| -------- | -------- | -------- |\n|1|1.9| 0.52|\n|2|2.9|0.35|\n|3|3.4|0.22|\n|4|3.6|0.17|\n|5|3.7|0.16|\n|6|3.8|0.15|\n\n**Key observations:**\n- MPC correctly **captures the decreasing empirical accuracy** as graphs densify over time \n- Thereby, MPC **quantifies how structural evolution over time affects task difficulty**\n\n\nThis 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.\n\n## Summary\nWe 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.\n\n\\[1] Gasteiger et al. Directional Message Passing for Molecular Graphs. ICLR 2020.\n\n\\[2] Longa et al. Graph Neural Networks for temporal graphs: State of the art, open challenges, and opportunities. arXiv:2302.01018\n\n\\[3] Hu et al. Open Graph Benchmark: Datasets for Machine Learning on Graphs. Neurips 2020."}, {"review_id": "M75UaZ7rlG", "reviewer": "Reviewer_46h7", "summary": "The authors highlight limitations with Iso expressivity; higher-expressivity is often not required for a task, it is binary and makes idealized assumptions. To overcome this, the authors present Message Passing Complexity (MPC). Effectively, this measures how hard it is to learn a function on a node under lossy message-passing. The authors show how this relates to some current expressivity measures and how it aligns with practically relevant tasks.", "questions": "My score will be increased with a better understanding of the impact MPC can have on the field and addressing my weaknesses. Concretely:  \n- How can MPC be used to align expressivity to accuracy on real-world tasks?\n- How can MPC be used to improve models and how would this differ from reducing the commute time?", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 2, "strengths_and_weaknesses": "**Strengths** \n\n- *Well-described problem definition*. The limitations of currently used iso expressivity are very clearly described and your approach is thus extremely well motivated. In general, this problem is a huge concern for the community and addressing this problem in a positive way is very impactful.\n\n- *Excellent theoretical comparison to iso expressivity*. I really appreciate Section 4.2. It clearly outlines the benefits of the continuous measure and how it relates to and encompasses Iso expressivity.\n\n- *Toy examples are well motivated and clearly identify benefits of the approach*. The experiments are thoughtfully designed and clearly show the benefits of the approach in terms of being more fine-grained and aligning with over-smoothing/over-squashing in comparison to iso expressivity.\n\n\n**Weaknesses**\n\n- The main weakness is the reliance on knowing the function f_v. This restricts the analysis to toy examples and we have no way of knowing how to compare models and approaches on datasets where we can't easily obtain this node-level function. Given that one of the highlighted limitations of iso expressivity is not aligning with real-world tasks, I don't think MPC solves this issue. Additionally, if the task is graph-level and depends on a complex aggregation of node-functions at different layers L (as expected in practical scenarios), then it is not clear how useful MPC can be in such a case. \n\n- The paper focuses on iso expressivity and only briefly or doesn't mention expressivity related to learning polynomial filters [1], counting substructures [2]  and over-squashing [3]. The differences between these expressivity measures and iso expressivity are sometimes not clarified in the paper. For example, in line [123], the authors state that \"adding a virtual node does not increase expressivity\". However, in [4], although it doesn't improve iso expressivity, they do show that it improves in terms of the expressivity described in both [1] and [3]. In general, I believe a stronger discussion of [3] is warranted given the strong connection to your approach (both indicate that a task is hard if it requires combining information from many nodes through messages of low probability such as messages through bottlenecks.) \n\n- I think the paper would be improved if some suggestions could be proposed for how MPC would be used beyond previous measures in improving model design. The success of iso expressivity has arguably been how it's been quite easily used to suggest more powerful and expressive architectures. For MPC, it is not clear to me how it can be used in the same way beyond current measures [3]. What would be the difference between reducing MPC and reducing the commute time between nodes [3]? How could we use this to design better models? I think understanding this would go a long way to assessing the impact this paper would have on the field. \n\n[1] Wang et al. How powerful are spectral graph neural networks. In International Conference on Machine Learning. PMLR 2022. \n\n[2] Bouritsas et al. Improving graph neural network expressivity via subgraph isomorphism counting. IEEE Transactions on\nPattern Analysis and Machine Intelligence 2023.\n\n[3] Di Giovanni et al. How does over-squashing affect the power of gnns?  TMLR 2023.\n\n[4] Southern et al. Understanding Virtual Nodes: Oversquashing and Node Heterogeneity. ICLR 2025.", "was_revised": true, "final_justification": "The authors have addressed the few concerns which I originally had", "rebuttal": "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.\n\n## 1. Reliance on knowing task $f_v$\nYou 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**:\n\n1. **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.\n2. **Domain-informed proxy tasks**: Use domain knowledge to identify key capabilities—e.g., ring identification for small molecule predictions, long-range propagation for proteins.\n\n**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**:\n\n| Model | MPC (Ring Task) | MAE (ZINC)|\n|--|-|-----|\n| GraphSage | 7.3 | 0.40 |\n| GCN | 7.3 | 0.37 |\n| GSN | 3.6 | 0.12 |\n| FragNet | 3.2 | 0.078 |\n| CIN | 2.9 | 0.077 |\n\nOf 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.\n\n\n## 2. Connection to other expressivity measures\nThank 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. \n\nAdditionally, we have expanded our discussion of non-iso expressivity measures in Sec. 7, particularly the connection to Di Giovanni et al. \\[14]:\n\n**Expanded related work on expressivity measures in Sec. 7**: \n\nBeyond 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].\nHowever, 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.\n\nMost 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.\nHowever, 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.\n\n## 3. Impact of MPC on the future of graph learning research\nLastly, we address your two key questions about MPC's practical impact:\n\n### Q1: Better alignment between theory and practice\n**How can MPC be used to align expressivity to accuracy on real-world tasks?**\n\nMPC is specifically designed to better align with empirical performance (Sec. 3 & 4) by:\n- Capturing practical limitations arising from the lossy information propagation of real-world MPNNs (e.g., over-smoothing, over-squashing)\n- Providing a continuous difficulty measure rather than binary possible/impossible statements\n- Flexibly considering arbitrary tasks relevant to the domain instead of focusing on one fixed task.\n\nOur **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.\n\nMoreover, 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**. \n\nWhile we, of course, cannot completely close the gap between theory and practice, we can at least narrow it.\n\n### Q2: Role of MPC for developing new architectures\n**How can MPC be used to improve models and how would this differ from reducing the commute time?**\n\nFirst, 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.\n\n**Theoretical contributions on future architectural design**\n\nA 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.\n\nSecond, 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.\n\nThird, 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.\n\n\n**Concrete examples of how MPC can guide model improvement** for specific capabilities needed in certain domains:\n- **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.\n- **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.\n\n**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.\n\nWe have now included a discussion of the concrete ways in which MPC can benefit future MPNN design in Sec. 6.\n\n\n## Summary\nWe 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.\n\n### Additional References\n\\[52]  Wang et al. How powerful are spectral graph neural networks. ICML 2022.\n\n\\[53] Fey et al. Hierarchical Inter-Message Passing for Learning on Molecular Graphs. arXiv:2006.12179\n\n\\[54] Fey et al. Relational Deep Learning: Graph Representation Learning on Relational Databases. arXiv:2312.04615."}, {"review_id": "RfWeSj2Fpg", "reviewer": "Reviewer_Z8aj", "summary": "The core argument is that classical expressivity theory is centered around whether a GNN can distinguish graphs under variants of the Weisfeiler-Lehman (WL) test fails to explain the practical performance of GNNs. This paper introduces Message Passing Complexity (MPC) -- a continuous complexity measure for analyzing Graph Neural Networks (GNNs), based on a probabilistic variant of the WL test. The authors argue that MPC better captures the real-world limitations (e.g., over-squashing, under-reaching) and correlates more closely with empirical behavior.", "questions": "**Q1:** How does MPC explicitly capture over-smoothing? \n\n**Q2:** Can you compare MPC empirically or theoretically (with use of simple examples) to other expressivity frameworks? \n\n**Q3:** Have you tried computing MPC for real-world benchmarks (beyond synthetic graph families)? If not, can MPC be feasibly computed or approximated for those settings?\n\n**Q4:** Can MPC differentiate between two models with identical MP graphs but different aggregation schemes or activation functions?", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\n**S1:** The paper is novel -- shifting focus from binary expressivity to continuous and task-specific expressivity. The chosen expressivity measure also connects well with the known GNN limitation of over-squashing.\n\n**S2:** The theoretical analysis is thorough, including preserved impossibility results and proofs of key properties of MPC.\n\nWeaknesses:\n\n**W1:** The relation between MPC and existing phenomena such as over-smoothing remains vague. Although the authors claim to capture it in their \"retaining information\" task, there is no direct experimental study of over-smoothing, nor a clear connection to existing literature on the subject.\n\n**W2:** The paper does to compare with or compare against existing expressivity measures beyond WL-based ones, which is my main concern.\n\n**W3**: Visual presentation (e.g., figure readability and color scheme) detracts from clarity. Some figures are overly dense or poorly captioned.", "was_revised": true, "final_justification": "The authors’ rebuttal addresses the key concerns raised in my review. Most notably, they establish a clear theoretical and empirical connection between MPC and over-smoothing by relating information retention to random walk return probabilities. They also provide a thoughtful comparison to existing expressivity measures, arguing that MPC uniquely offers a continuous, task-specific framework that avoids the limitations of binary or task-agnostic approaches. These clarifications and additions motivated my score increase from 3 to 4.", "rebuttal": "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.\n\n## W3: Visual presentation\nWe 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.\n\n## Q1 & W1: Connection to over-smoothing\nOver-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].\nThis 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.\n\n**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: \n$\\text{MPC}(f\\_v,G) \\ge -\\log((I^L)\\_{vv})$\nwhere $(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. \nThis 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].\n\n**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. \n\nWe 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.\n\n## Q2 & W2: Comparison to other expressivity measures\n\nExisting expressivity measures have fundamental limitations for measuring task difficulty that make meaningful comparison with MPC across tasks difficult:\n\n**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.\n\n**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.\n\n**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.\n\nTo our knowledge, MPC is the first framework with continuous difficulty quantification for arbitrary graph tasks, thereby flexibly capturing practical difficulties beyond theoretical feasibility.\n\nWe have made this very important comparison more clearly in our Related Work and Evaluation sections.\n\n\n## Q3: Real-world benchmarks\n\nYes, 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.\n\nMoreover, 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:\n\n| Num Layers | MPC | Accuracy |\n|------------|-----|----------|\n| 2          | 3.6 | 0.44     |\n| 4          | 4.7 | 0.26     |\n| 6          | 5.2 | 0.10     |\n| 8          | 5.3 | 0.10     | \n\nBesides this, MPC also allows the **derivation of complexity bounds** that require no computation whatsoever (e.g., Lemma 5.1 - 5.3).\n\n\n\n## Q4: Different Aggregation/Update Functions\nIn 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).\n\n**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.\n\n**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$).\n\n 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.\n\n## Summary\nWe 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).\n\n### Additional References\n\\[52] Xu et al. Representation Learning on Graphs with Jumping Knowledge Networks. ICML 2018.\n\n\\[53] Zhao et al. PairNorm: Tackling Oversmoothing in GNNs. ICRL 2020.\n\n\\[54] Giraldo et al. On the Trade-off between Over-smoothing and Over-squashing in Deep Graph Neural Networks. CIKM 2023\n\n\\[56] Zaheer et al. Deep sets. Neurips 2017."}]

Author rebuttal:

Meta-review: The paper argues that the current dominance of WL-style iso-expressivity for analyzing GNNs is misaligned with practical performance. It proposes Message Passing Complexity (MPC)—a continuous, task-specific measure derived from a probabilistic WL (lossyWL)—to quantify how difficult it is for an MPNN to solve a task under lossy message passing. MPC preserves impossibility results from iso-expressivity, captures practical phenomena such as over-squashing and over-smoothing, and correlates with empirical performance across multiple architectures and tasks. The authors support these claims with theory (e.g., lemmas bounding complexity) and controlled studies on synthetic and real graphs, plus added analyses during rebuttal.

# Strengths

* Timely reframing: Moves beyond binary expressivity to a continuous measure aligned with practice; well-motivated and clearly articulated.

* Bridges theory and practice: Explains phenomena (over-squashing/over-smoothing, long-range propagation) and why components like virtual nodes help.

* General framework: Clean abstraction via message-passing graphs; preserves impossibility results while enabling task-specific analysis.

* Empirical validation: Consistent correlation between MPC and accuracy across 8+ architectures and tasks, with real-graph evidence (ZINC, LRGB) and a large-scale ogbn-products demonstration added in rebuttal.

* Actionable insights: Task-specific complexity suggests design levers (e.g., hub nodes / higher-order nodes for multi-node aggregation; substructure-aware encodings such as CIN/FragNet) rather than chasing iso-expressivity.

# Weakness

* Computation at scale / complex tasks: Exact MPC can be costly or intractable; reliance on proxy tasks and bounds is sensible but not a full substitute.

* Presentation: Some figures dense; authors commit to improved captions/visual clarity.

# Reasons for decision.
During rebuttal, the authors focused on making MPC practical and broadly applicable. They outlined an efficient estimation path using proxy tasks and theoretical bounds (App. D), and showed that MPC tracks accuracy on large graphs. They mapped the framework to 3D/directional GNNs via directed line graphs, and discussed extensions to settings with missing/noisy features and to temporal graphs. They also clarified the link to over-smoothing through random‑walk return probabilities, and strengthened baselines, figures, and exposition. Collectively, these updates addressed the central concerns, prompting score increases and a confident Accept (Spotlight) consensus.
Decision: Accept (spotlight)