On the Computational Capability of Graph Neural Networks: A Circuit Complexity Bound Perspective

Xiaoyu Li, Yingyu Liang, Zhenmei Shi, Zhao Song, Wei Wang, Jiahao Zhang

Introduction

Graphs are ubiquitous representations for relational data, describing interconnected elements with interactions in domains such as molecules , social networks , and user-item interactions in recommendation systems . Graph Neural Networks (GNNs) have emerged as a dominant tool for learning expressive representations from graphs, enabling tasks like node property prediction , link prediction , and graph classification . The key to GNNs’ success lies in the message-passing mechanism , which aggregates information from local neighborhoods through a graph convolution matrix, followed by nonlinear transformations to update node representations.

Despite their empirical success, concerns regarding the computational limitations of GNNs are emerging . A fundamental research question arises from the concern:

What computational capabilities do GNNs and their variants possess, and what classes of problems can they provably solve?

Addressing these questions is crucial for understanding GNNs from a principled and theoretically robust perspective, identifying their limitations, and building trust in their deployment for real-world applications.

Previous work has made significant strides in addressing these questions. A notable line of research connects GNN expressiveness to the Weisfeiler-Leman (WL) graph isomorphism test , which iteratively refines color labels on $k$ -tuples of nodes (known as $k$ -WL) and distinguishes graphs by the resulting color histograms. For example, the Graph Isomorphism Network (GIN) equipped with summation aggregator and injective readout function is as expressive as $1$ -WL, while $k$ -GNNs achieve expressiveness equivalent to $k$ -WL by encoding $k$ -node subgraphs as hypernodes in message passing. However, these results focus on graph isomorphism tasks and do not address a broader range of graph query problems. Moreover, the WL framework only provides a specific level of expressiveness without establishing the theoretical upper bounds, and it often ignores the interplay between node features and graph topology, which is central to GNNs.

In this paper, we take a fundamentally different approach to analyzing the computational limitations of GNNs by examining the circuit complexity bounds. Circuit complexity is a foundational topic in theoretical computer science, characterizing computational models based on the types of Boolean gates they use and the depth and size of their circuits. Importantly, circuit complexity bounds provably reflect the set of problems solvable within a given model. For instance, models (e.g., Transformers) bounded by the $\mathsf{TC}^{0}$ complexity class can only solve $\mathsf{TC}^{0}$ problems (e.g., Dyck language recognition) but cannot solve $\mathsf{NC}^{1}$ -complete problems like arithmetic formula evaluation unless $\mathsf{TC}^{0}=\mathsf{NC}^{1}$ . Analogously, if we demonstrate that GNN computations lie within a particular circuit complexity class, we can formally identify problems that GNNs can solve and cannot solve.

Our approach evaluates the circuit complexity of GNN components, from basic activation functions to the entire graph convolution process. We show that GNNs with a constant number of layers, $\operatorname{poly}(n)$ precision, and embedding sizes $d=O(n)$ can be approximated by uniform $\mathsf{TC}^{0}$ circuits. Consequently, unless $\mathsf{TC}^{0}=\mathsf{NC}^{1}$ , such GNNs cannot solve problems like graph connectivity problems or graph isomorphism problems. These findings illuminate the fundamental expressivity limitations of GNNs despite their empirical success and also establish a novel framework for analyzing their expressiveness, which can be seamlessly generalized to more GNN models and decision problems on graphs.

Our contributions are summarized as follows:

We prove that a uniform $\mathsf{TC}^{0}$ circuit family can approximate GNNs with a constant number of layers, $\operatorname{poly}(n)$ precision, and $d=O(n)$ embedding size (Theorem 4.14).

We establish that unless $\mathsf{TC}^{0}=\mathsf{NC}^{1}$ , graph neural networks with a constant number of layers, $\operatorname{poly}(n)$ precision and $d=O(n)$ embedding size cannot solve the graph connectivity problems (Theorem 5.11 and Theorem 5.12).

Roadmap. Section 2 reviews relevant works. Section 3 introduces GNNs and basic concepts from theoretical computer science. Section 4 presents the circuit complexity bounds for GNNs. Section 5 discusses the hardness of specific graph problems. Finally, Section 6 concludes our findings.

Related Work

We present related works on the computational limitation of GNNs and existing circuit complexity bounds for neural networks.

Graph Neural Networks (GNNs) have demonstrated impressive performance on graph learning and mining tasks. However, their inherent limitations in solving decision problems on graphs remain an open question. The predominant framework for analyzing GNN limitations is the Weisfeiler-Lehman (WL) hierarchy , a well-established tool for assessing GNNs’ ability to address the graph isomorphism problem—an NP-intermediate problem not solvable in polynomial time . The WL hierarchy leverages the computationally efficient heuristic of color refinement to bound the capability of differentiating non-isomorphic graphs.

The expressiveness of message-passing GNNs is bounded by the $1$ -WL test . Standard GNN models such as GCN , GAT , and GIN are either equivalent to or strictly limited by the expressiveness of $1$ -WL. To go beyond $1$ -WL, high-order GNNs extend message-passing mechanisms to $k$ -node subgraphs , mimicking the $k$ -WL or $k$ -FWL (Folklore WL) tests. Models like $k$ -GNN and $k$ -FGNN match the expressiveness of these higher-order tests, offering stronger guarantees than standard message-passing GNNs. However, the parameter $k$ cannot be scaled to sufficiently large values due to inherent computational and memory constraints.

Another promising line of research involves subgraph GNNs, which aim to address the inherent symmetry of graphs that cannot be distinguished by WL tests. These models transform the original graph into a set of slightly perturbed subgraphs, which are then processed by GNNs . Recent work has shown that for an $n$ -node graph, subgraph GNNs operating on subgraphs with $k$ nodes are strictly bounded by $(k+1)$ -FWL . Besides, distance-aware GNNs inject distance information—overlooked by both message-passing GNNs and $1$ -WL—into their architectures. For instance, $k$ -hop MPNNs aggregate information from $k$ -hop neighbors in each layer and have been shown to be strictly bounded by $2$ -FWL . Additionally, the subgraph WL hierarchy demonstrates that distance encoding can be represented by local $2$ -WL tests .

Despite the widespread use of the WL framework in analyzing GNNs’ computational limitations, it often overlooks the role of node features and focuses exclusively on the graph isomorphism problem, making it insufficiently comprehensive and unsuitable for generalizing to other graph decision problems. A detailed comparison of our work with WL-based GNN expressiveness is provided in Section 5.4.

2 Circuit Complexity and Neural Networks

Circuit complexity, a foundational area in theoretical computer science, studies the computational power of Boolean circuit families. Various circuit complexity classes play a significant role in analyzing machine learning models. For instance, the class $\mathsf{AC}^{0}$ represents problems solvable in parallel using standard Boolean gates, while $\mathsf{TC}^{0}$ extends this by incorporating threshold or modulo gates. The stronger class $\mathsf{NC}^{1}$ corresponds to problems solvable by circuits with $O(\log n)$ depth and bounded fan-in . A key result relevant to machine learning is the complexity inclusion $\mathsf{AC}^{0}\subset\mathsf{TC}^{0}\subseteq\mathsf{NC}^{1}$ , though whether $\mathsf{TC}^{0}=\mathsf{NC}^{1}$ remains an open question .

Circuit complexity bounds have been effectively used to analyze the computational power of various neural network architectures. For example, Transformers, including two canonical variants—Average-Head Attention Transformers (AHATs) and SoftMax-Attention Transformers (SMATs)—have been studied in this context. Specifically, shows that AHATs can be simulated by non-uniform constant-depth threshold circuits in $\mathsf{TC}^{0}$ , while demonstrates that SMATs can also be simulated in a $L$ -uniform manner within $\mathsf{TC}^{0}$ . A follow-up study unifies these results, concluding that both AHATs and SMATs are approximable by $\mathsf{DLOGTIME}$ -uniform $\mathsf{TC}^{0}$ circuits. Beyond standard Transformers, RoPE-based Transformers , a widely adopted variant in large language models, have also been analyzed using circuit complexity frameworks . Similarly, the emerging Mamba architecture falls within the $\mathsf{DLOGTIME}$ -uniform $\mathsf{TC}^{0}$ family . Additionally, Hopfield networks, initially introduced as associative memory systems, have also been shown to exhibit $\mathsf{TC}^{0}$ circuit complexity bounds .

Despite the success of circuit complexity in analyzing other neural networks, its application to GNNs is underexplored. While some prior works have attempted to characterize the computational power of GNNs within circuit computation models , these efforts are orthogonal to our contributions. A detailed discussion is provided in Section 5.4.

Preliminary

This section provides fundamental definitions for this paper. We first introduce some notations. In Section 3.1, we present an in-depth overview of the computation of floating point numbers. In Section 3.2, we review several basic definitions of the Graph Neural Networks (GNNs). In Section 3.3, we present some basic concepts of circuit families and their complexity.

1 Floating Point Numbers

In this subsection, we introduce fundamental definitions of floating-point numbers and their operations. These concepts establish a critical computational framework for implementing GNNs on real-world machines.

Building upon the fundamental concepts introduced above, we present the critical floating-point operations used to compute the outputs of graph neural networks.

Let $x,y$ be two integers. We first denote the integer division operation $\mathbin{/\!/}$ as:

The basic operations described above can be efficiently computed in parallel using simple hardware implementations in $\mathsf{TC}^{0}$ circuits, as formalized in the following lemma:

We denote the number of digits as a positive integer $p$ . If $p\leq\operatorname{poly}(n)$ , then:

Iterated Operations: The product of $n$ $p$ -bit $\mathsf{FPN}$ s and the sum of $n$ $p$ -bit $\mathsf{FPN}$ s (with rounding applied after summation) can be both computed with $O(1)$ -depth uniform threshold circuits with $\operatorname{poly}(n)$ size. Let the maximum circuit depth required for multiplication be $d_{\otimes}$ and for addition be $d_{\oplus}$ .

Beyond these basic floating-point operations, certain specialized floating-point operations are also known to be computable within $\mathsf{TC}^{0}$ circuits, as demonstrated in the following lemmas:

2 Graph Neural Networks

With the foundational framework of $\mathsf{FPN}$ operations, we now formalize the components of Graph Neural Networks (GNNs) in floating-point representations. This subsection commences by introducing activation functions and the softmax operation, which are fundamental building tools for GNN layers.

where $\boldsymbol{1}_{d}$ is a $d$ -dimensional column vector of ones.

These activation functions and softmax operations form the basis of GNN computation. We now introduce the convolution matrices central to the message-passing scheme of GNNs, focusing on three widely used GNN models: GCN , GIN , and GAT .

The GAT convolution matrix is then given by:

Therefore, we unify the three commonly used graph convolution matrices with basic components to define a general GNN layer.

By stacking multiple GNN layers, we obtain a multi-layer GNN capable of learning expressive node embeddings. Different prediction tasks, such as node-level, link-level, or graph-level tasks, require graph pooling operations to aggregate information from specific node subsets. We introduce two commonly used $\mathsf{READOUT}$ functions for graph pooling:

Graph readout functions in Definitions 3.15 and 3.16 support decision problems at various levels, including but not limited to node, link, and graph tasks, since one can target specific nodes, edges, or the entire graph by appropriately selecting the subset $B$ .

Finally, we introduce the MLP prediction head, essential for converting the aggregated embedding into specific predictions:

Finally, we integrate all the previously defined GNN components to present the complete formulation of a multi-layer GNN.

3 Circuit Complexity Classes

In this subsection, we introduce the fundamental concepts of circuit complexity, a key concept of theoretical computer science and computational complexity.

A Boolean circuit with $n$ binary inputs and one binary output is a mapping $C_{n}$ between $\{0,1\}^{n}$ and $\{0,1\}$ , represented as a directed acyclic graph (DAG). The graph consists of:

$n$ input nodes, each with in-degree zero, corresponding to the input variables.

One output node, each with out-degree zero, representing the output variable.

Intermediate nodes, called gates, perform logical operations (e.g., $\mathsf{NOT}$ , $\mathsf{OR}$ , $\mathsf{AND}$ ) on the inputs. Each gate has one out-edge, representing the result of the computation. The in-degree of gate nodes is also referred to as their fan-in.

The structure of the graph allows the Boolean circuit to evaluate logical functions based on the input values, producing a corresponding output.

The size of a Boolean circuit $C$ is defined as the number of nodes in its computation graph. The depth of $C$ is the length of the longest path in its computation graph.

To analyze the expressiveness of specific Boolean circuits, we first formally define the concept of languages recognized by a circuit family.

A circuit family $\mathcal{C}$ denotes a set of Boolean circuits. The circuit family $\mathcal{C}$ can recognize a language $L\subseteq\{0,1\}^{*}$ if, for every string $s\in\{0,1\}^{*}$ , there exists a Boolean circuit $C_{|s|}\in\mathcal{C}$ with input size $|s|$ such that $C_{|s|}(s)=1$ if and only if $s\in L$ .

We now define complexity classes of languages based on the circuit families capable of recognizing them, with a focus on the resources (e.g., depth, size) these circuits require:

A language $L$ belongs to the class $\mathsf{NC}^{i}$ (Nick’s Class) if there is a family of Boolean circuits that can recognize $L$ , where the circuits have $\operatorname{poly}(n)$ size, $O((\log n)^{i})$ depth, and $\mathsf{NOT}$ , $\mathsf{OR}$ , $\mathsf{AND}$ logical gates with bounded fan-in.

A language $L$ belongs to the class $\mathsf{AC}^{i}$ if there is a family of Boolean circuits that can recognize $L$ , where the circuits have $\operatorname{poly}(n)$ size, $O((\log n)^{i})$ depth, and $\mathsf{NOT}$ , $\mathsf{OR}$ , $\mathsf{AND}$ logical gates with unbounded fan-in.

A language $L$ belongs to the class $\mathsf{TC}^{i}$ if there is a family of Boolean circuits that can recognize $L$ , where the circuits have $\operatorname{poly}(n)$ size, $O((\log n)^{i})$ depth, and unbounded fan-in gates for $\mathsf{NOT}$ , $\mathsf{OR}$ , $\mathsf{AND}$ , and $\mathsf{MAJORITY}$ operations, where a $\mathsf{MAJORITY}$ gate outputs one if more than $1/2$ of its inputs are ones.

The $\mathsf{MAJORITY}$ gates in Definition 3.25 can be substituted with prime-modulus $\mathsf{MOD}$ gates or $\mathsf{THRESHOLD}$ gates. Any Boolean circuit utilizing one of these gates is called a threshold circuit.

Next, we define the complexity class $\mathsf{DET}$ , which plays a critical role in certain hardness results.

A Boolean circuit belongs to the $\mathsf{DET}$ family if it computes a problem that is $\mathsf{NC}^{1}$ -reducible to the computation of the determinant $\det(A)$ of an $n\times n$ matrix $A$ with $n$ -bit integers.

As noted on page 116 of and page 110 of , it is well-known that $\mathsf{NC}^{i}\subsetneq\mathsf{AC}^{i}\subsetneq\mathsf{TC}^{i}$ for $i=0$ . However, whether $\mathsf{TC}^{0}\subsetneq\mathsf{NC}^{1}$ remains an open problem in circuit complexity. Additionally, as discussed on page 18 of , it is unlikely that $\mathsf{DET}\subseteq\mathsf{AC}^{1}$ , despite $\mathsf{DET}$ being bounded between $\mathsf{NC}^{1}$ and $\mathsf{NC}^{2}$ .

We have formulated non-uniform circuit families that allow different structures for different input lengths. While flexible, this lack of uniformity is impractical compared to computational models like Turing machines, where the same device handles all input lengths. To address this, we introduce uniform circuit families, where circuits for all input lengths can be systematically generated by a Turing machine under specific time and space constraints. We begin by introducing $\mathsf{L}$ -uniformity.

Let $\mathcal{C}$ denote a circuit family, and let $\mathsf{C}$ denote a language class recognizable by $\mathcal{C}$ . A language $L\subseteq\{0,1\}^{*}$ belongs to the $\mathsf{L}$ -uniform class of $\mathsf{C}$ if there exists an $O(\log n)$ -space Turing machine that can produce a circuit $C_{n}\in\mathcal{C}$ with $n$ variables for any input $1^{n}$ . The circuit $C_{n}$ must recognize $L$ for inputs of size $n$ .

Next, we define $\mathsf{DLOGTIME}$ -uniformity, which refines $\mathsf{L}$ -uniformity by introducing a more computationally practical time constraint. Throughout this paper, references to uniform circuit families specifically denote their $\mathsf{DLOGTIME}$ -uniform versions.

Let $\mathsf{C}$ be an $\mathsf{L}$ -uniform language class as defined in Definition 3.30. A language $L\subseteq\{0,1\}^{*}$ belongs to the $\mathsf{DLOGTIME}$ -uniform class of $\mathsf{C}$ if there exists a Turing machine that can produce a circuit $C_{n}\in\mathcal{C}$ with $n$ variables for any input $1^{n}$ within $O(\log n)$ time. The circuit $C_{n}$ must recognize the language $L$ for inputs of size $n$ .

Complexity of Graph Neural Networks

In this section, we establish foundational complexity results for each component of a graph neural network (GNN) and then combine these results to derive a circuit complexity bound for the entire multi-layer GNN. Section 4.1 examines activation functions, which form the basics for graph convolution computations. Section 4.2 explores the computation of graph convolution matrices. Section 4.3 analyzes a single GNN layer, the fundamental building block of a multi-layer GNN. In Section 4.4, we investigate graph readout functions and the MLP prediction head, essential for making predictions with a multi-layer GNN. Finally, in Section 4.5, we integrate all components and analyze the complete multi-layer GNN structure, culminating in Section 4.6, where we present the key result: the circuit complexity bound of graph neural networks.

In this subsection, we first establish a useful fact about computing pairwise $\max$ and $\min$ functions with $\mathsf{TC}^{0}$ circuits. We then demonstrate that the $\mathsf{ReLU}$ and $\mathsf{LeakyReLU}$ activation functions on embedding matrices can be efficiently computed by uniform threshold circuits.

2 Computing Graph Convolution Matrices

In this subsection, we present results on the computation of representative graph convolution matrices using uniform threshold circuits.

Before discussing the $\mathsf{TC}^{0}$ implementation of the GAT convolution matrix, we introduce a key fact on the softmax mechanism, which is crucial for attention computation in GAT.

Combining these circuits, the total depth is:

Building on the softmax computation fact, we show that the GAT convolution matrix can indeed be computed with $\mathsf{TC}^{0}$ circuits, as formalized in the following lemma.

following Definition 3.13. We examine the three terms separately:

For the second term $E^{2}_{i,j}$ , since its computation is equivalent to the first term, we can conclude that the depth of the second term $d_{2}$ equals $d_{1}$ .

3 Computing Single Graph Neural Network Layer

In this subsection, we combine the results on graph convolution matrices and basic activation functions to determine the circuit depth requirement for a complete GNN layer.

4 Computing Pooling Layer and Prediction Head

As shown in Definition 3.15, Definition 3.16, and Definition 3.18, we have described basic components for transforming GNN node embeddings into predictions. Here, we present results on computing these components with uniform threshold circuits, starting with two graph readout layers.

Before delving into the graph maximum readout layer, we establish a useful fact about computing maximum and minimum values in $\mathsf{TC}^{0}$ .

Once $C^{\max}$ and $C^{\min}$ are computed, we compute the dominance vector $D^{\max}\in\{0,1\}^{n}$ in parallel using a 1-depth Boolean circuit, where $D^{\max}_{i}=\bigwedge_{j=1}^{n}C^{\max}_{i,j}$ . Here, $D^{\max}_{i}=1$ indicates that $x_{i}$ is a maximum value. Similarly, we can compute $D^{\min}\in\{0,1\}^{n}$ in parallel, where $D^{\min}_{i}=\bigwedge_{j=1}^{n}C^{\min}_{i,j}$ , to identify the minimum value.

To select the maximum value, we compute each bit $k\in[p]$ of the output $o^{\max}=\max\{x_{1},x_{2},\cdots,x_{n}\}$ in parallel using a 2-depth Boolean circuit:

in which $(x_{i})_{k}$ is the $k$ -th bit of $x_{i}$ . Since all maximum values are equal, if a specific bit $k$ of all maximum values is 1, the OR operation ensures $o_{k}^{\max}=1$ ; similarly, if all maximum values have 0 in bit $k$ , then $o_{k}^{\max}=0$ . Thus, this approach guarantees correctness regardless of the number of maximum values. Similarly, each bit $k\in[p]$ of the minimum output $o^{\min}=\min\{x_{1},x_{2},\cdots,x_{n}\}$ is computed using:

With this fact, the graph maximum readout layer can be computed seamlessly using $\mathsf{TC}^{0}$ circuits, as stated in the following lemma:

Next, we introduce the circuit depth for computing an MLP prediction head.

Combining all the aforementioned circuits, we have the total circuit depth:

5 Computing Multi-Layer Graph Neural Network

Since we have presented the circuit depths for all the components of an entire multi-layer GNN, we now derive the overall circuit depth of the entire GNN in this subsection.

Combining the circuits to compute each layer of the entire model, we have the following total circuit depth:

6 Main Result: Graph Neural Networks Circuit Complexity

Finally, this subsection presents the circuit complexity bound of graph neural networks, which is the main result of this paper.

By Lemma 4.13 and $m=O(1)$ , the circuit to compute $\mathsf{GNN}(x)$ has depth

and size $\operatorname{poly}(n)$ . Then, we can conclude that a uniform $\mathsf{TC}^{0}$ circuit family can simulate $\mathsf{GNN}(x)$ , following Definition 3.25. Hence, we finish the proof. ∎

The main result in Theorem 4.14 establishes that unless $\mathsf{TC}^{0}=\mathsf{NC}^{1}$ , graph neural networks with $\operatorname{poly}(n)$ precision, constant depth, and $O(n)$ embedding size belong to the uniform $\mathsf{TC}^{0}$ circuit class. This highlights an inherent expressiveness limitation of GNNs, despite their empirical success, as they cannot solve problems beyond the capability of $\mathsf{TC}^{0}$ circuits. In the next section, we illustrate this limitation by analyzing two practical graph query problems.

Hardness

We explore two critical decision problems on graphs and their associated hardness results. Section 5.1 introduces two graph connectivity problems. Section 5.2 presents the basic concepts of the graph isomorphism problem. In Section 5.3, we present the main hardness result of this paper, which theoretically demonstrates that graph neural networks cannot solve these problems.

To formally define the graph connectivity problem, we begin by introducing two basic concepts related to sequences of connected nodes in graphs: walks and paths.

Given a graph $\mathcal{G}=(\mathcal{V},\mathcal{E})$ , a walk in $\mathcal{G}$ is a finite sequence of nodes, denoted by

where $v_{0},v_{1},v_{2},\dots,v_{m}\in\mathcal{V}$ and any two consecutive nodes are connected (i.e., $\forall i\in[m],(v_{i-1},v_{i})\in\mathcal{E}$ ).

For a walk $v_{0}\rightarrow v_{1}\rightarrow v_{2}\rightarrow\cdots\rightarrow v_{m}$ , if all the nodes $v_{0},\dots,v_{m}$ and all the edges $(v_{0},v_{1}),\cdots,(v_{m-1},v_{m})$ are distinct, then we call this walk as a path.

Building upon these basic concepts, we now formally define two types of graph connectivity problems: the pairwise s-t connectivity problem, which checks whether two specific nodes are connected, and the global graph connectivity problem, which verifies the connectivity of all nodes.

Let $\mathcal{G}=(\mathcal{V},\mathcal{E})$ be an arbitrary undirected graph. The undirected s-t graph connectivity problem is: Does there exist a path between two specific nodes $s,t\in\mathcal{V}$ ?

Let $\mathcal{G}=(\mathcal{V},\mathcal{E})$ be an arbitrary undirected graph. The undirected graph connectivity problem is: Does there exist a path between all the nodes in $\mathcal{V}$ ?

With these problem formulations, we proceed to their computational complexity results.

The undirected graph s-t connectivity problem in Definition 5.3 is $\mathsf{NC}^{1}$ -complete.

The undirected graph connectivity problem in Definition 5.4 is $\mathsf{NC}^{1}$ -hard.

2 Graph Isomorphism Problem

In this subsection, we turn to the graph isomorphism problem, a core challenge in understanding the expressiveness of GNNs . This problem involves determining whether two graphs are structurally identical by examining possible permutations of their nodes.

Let $\mathcal{G}_{1}=(\mathcal{V}_{1},\mathcal{E}_{1})$ and $\mathcal{G}_{2}=(\mathcal{V}_{2},\mathcal{E}_{2})$ be two graphs. An isomorphism between $\mathcal{G}_{1}$ and $\mathcal{G}_{2}$ is a bijection $\phi$ the between their sets of vertices $\mathcal{V}_{1}$ and $\mathcal{V}_{2}$ which preserves the edges, i.e. $\forall v_{1},v_{2}\in\mathcal{V}_{1},(v_{1},v_{2})\in\mathcal{E}_{1}~\Leftrightarrow~(\phi(v_{1}),\phi(v_{2}))\in\mathcal{V}_{2}$ and $\forall v_{1},v_{2}\in\mathcal{V}_{2},(v_{1},v_{2})\in\mathcal{E}_{2}~\Leftrightarrow~(\phi(v_{1}),\phi(v_{2}))\in\mathcal{V}_{1}$ .

We can now define the graph isomorphism problem, which checks the existence of such an isomorphism.

Let $\mathcal{G}_{1}=(\mathcal{V}_{1},\mathcal{E}_{1})$ and $\mathcal{G}_{2}=(\mathcal{V}_{2},\mathcal{E}_{2})$ be two graphs. The graph isomorphism problem is: Does there exist a graph isomorphism $\phi$ between $\mathcal{G}_{1}$ and $\mathcal{G}_{2}$ ?

The computational complexity of the graph isomorphism problem is summarized in the following results:

The graph isomorphism problem in Definition 5.8 is hard for the class $\mathsf{DET}$ under $\mathsf{AC}^{0}$ reductions.

The graph isomorphism problem in Definition 5.8 is $\mathsf{N}C^{1}$ -hard.

By Lemma 5.9, it is known that the graph isomorphism problem is hard for the class $\mathsf{DET}$ under $\mathsf{AC}^{0}$ reductions. Following Fact 3.28, since $\mathsf{AC}^{0}\subseteq\mathsf{NC}^{1}\subseteq\mathsf{DET}$ , we can conclude that the graph isomorphism problem is $\mathsf{DET}$ -hard ignoring the $\mathsf{AC}^{0}$ reduction condition. Thus, we can apply Fact 3.28 for the second time and conclude that the graph isomorphism problem is $\mathsf{NC}^{1}$ -hard, which finishes the proof. ∎

3 Hardness Results

This subsection presents the main hardness results, which highlight the limitations of GNNs on two practical graph decision problems. We begin by showing that GNNs are unable to solve both types of graph connectivity problems.

Unless $\mathsf{TC}^{0}=\mathsf{NC}^{1}$ , a graph neural network with $\operatorname{poly}(n)$ precision, constant number of layers, embedding size $d=O(n)$ cannot solve the graph s-t connectivity problem.

By Theorem 4.14, we have already shown that the graph neural network is in the $\mathsf{TC}^{0}$ circuit family. We can also conclude that the graph s-t connectivity problem is in $\mathsf{NC}^{1}$ by Lemma 5.5. Thus, combining with Fact 3.28, we can complete the proof. ∎

By Theorem 4.14, we have already shown that the graph neural network is in the $\mathsf{TC}^{0}$ circuit family. We can also conclude that the graph connectivity problem is $\mathsf{NC}^{1}$ -hard by Lemma 5.6. Thus, combining with Fact 3.28, we can complete the proof. ∎

Next, we show the hardness results for the graph isomorphism problem, which demonstrates the expressiveness limitations of GNNs from a non-Weisfeiler-Lehman (WL) perspective.

By Theorem 4.14, we have already shown that the graph neural network is in the $\mathsf{TC}^{0}$ circuit family. We can also conclude that the graph connectivity problem is $\mathsf{NC}^{1}$ -hard by Corollary 5.10. Thus, combining with Fact 3.28, we can complete the proof. ∎

Our hardness results assume an embedding size of $d=O(n)$ , which is significantly stronger and encompasses the constant embedding sizes typically used in practice, where $d=O(1)$ . This highlights that the computational limitations of GNNs cannot be easily mitigated by simply increasing the embedding size.

4 Discussion

After presenting the main hardness results of this paper, we explore the connections and comparisons with a broad range of relevant works, highlighting the contribution of this paper.

The Weisfeiler-Lehman (WL) hierarchy is the most widely used framework for analyzing the expressiveness of GNNs, particularly for their ability to solve graph isomorphism problems . While our Theorem 5.13 similarly shows that GNNs cannot solve the graph isomorphism problem unless $\mathsf{TC}^{0}=\mathsf{NC}^{1}$ , our results differ fundamentally from previous WL-based findings. Unlike the WL framework, which focuses solely on the topological structure of graphs, our analysis considers practical factors such as floating-point precision and node features. This broader perspective allows us to bound the expressiveness of feature-enhanced GNNs, including those with position encodings or random node features . Moreover, while the WL framework is limited to graph isomorphism, we extend the analysis to show that GNNs cannot solve the graph connectivity problem (Theorem 5.11 and Theorem 5.12), a limitation that is difficult to capture using the WL framework.

Comparison to GNN computational models.

Recent studies have explored GNN expressiveness through computational models. For example, investigates the RL-CONGEST model, which examines the communication complexity of GNNs in distributed settings. However, this work focuses on communication cost rather than expressiveness and is less relevant to our study. The most similar work to ours is , which shows that aggregate-combine GNNs cannot capture a variant of first-order logic, $\mathsf{FOC}_{2}$ . Since counting in $\mathsf{FOC}_{2}$ can be simulated by $\mathsf{FO}$ and $\mathsf{FO}=\mathsf{AC}^{0}$ , their result implies that $\mathsf{AC}^{0}$ is not a complexity lower bound for AC-GNNs. In contrast, our work establishes that GNNs are upper-bounded by the $\mathsf{TC}^{0}$ circuit family, providing a clear upper bound rather than refusing a lower bound. This highlights a fundamental difference between our result and previous results in .

Conclusion

In this work, we show the computational limits of graph neural networks (GNNs). Unlike prior approaches based on the Weisfeiler-Lehman (WL) test, we adopt a fundamentally different perspective: circuit complexity. We show that GNNs with $\operatorname{poly}(n)$ precision, constant number of layers, and embedding sizes $d=O(n)$ , regardless of the specific message-passing mechanisms or global readout functions, belong to the uniform $\mathsf{TC}^{0}$ circuit complexity class. As a result, we establish critical hardness results for two practical graph decision problems: graph connectivity and graph isomorphism. Our findings demonstrate that GNNs cannot solve these problems beyond $\mathsf{TC}^{0}$ , unless $\mathsf{TC}^{0}=\mathsf{NC}^{1}$ . These results are significant as they extend previous GNN expressiveness limitations, which were framed from the WL perspective, by introducing a fundamentally different circuit complexity bound. Our analysis not only incorporates previously overlooked factors, such as floating-point number precision and the interactions between node embeddings and topological structure but also applies to a broader range of graph query problems, such as graph connectivity.

For future works, we believe our theoretical framework offers a trustworthy foundation that can be generalized to assess the expressiveness of other GNN architectures and the hardness of additional graph query problems. Our research may also inspire the development of new architectures that go beyond the complexity of the $\mathsf{TC}^{0}$ circuit family.