Fundamental Limits of Crystalline Equivariant Graph Neural Networks: A Circuit Complexity Perspective

Yang Cao, Zhao Song, Jiahao Zhang, Jiale ZhaoSubmission to ICLR 2026 · Rejected

TL;DR

This paper characterizes the expressive limits of Equivariant Graph Neural Networks (EGNNs) tailored for periodic crystal structures through the lens of circuit complexity. The authors prove that standard, constant-depth crystalline EGNNs with polynomial precision can be simulated by uniform $\mathsf{TC}^0$ threshold circuits of polynomial size and explicit constant depth. This establishes a theoretical computational ceiling, pinpointing which problems these architectures provably cannot solve unless scaled in depth, width, or geometric complexity.

What Problem Does This Paper Address?

Equivariant Graph Neural Networks (EGNNs) are widely used to model crystals and periodic materials for tasks like property prediction and generative flow matching. They achieve strong empirical success by respecting 3D Euclidean symmetries ($E(3)$) and periodic boundary conditions via fractional coordinates and lattice vectors.

However, their fundamental expressive limits remain poorly understood:

  • Weisfeiler–Lehman (WL) tests fall short: Classical GNN expressivity analyses rely on the discrete graph isomorphism WL hierarchy, which ignores continuous coordinates, periodic lattice transformations, and geometric equivariance.
  • Circuit complexity gaps: While circuit complexity has recently been applied to Transformers and standard GNNs, existing frameworks do not account for the continuous coordinate updates and periodic boundary math central to crystalline materials.

The authors ask: What are the intrinsic computational and expressive limits of crystalline EGNNs?

Methods

The authors adopt a circuit complexity approach, mapping the building blocks of crystalline EGNNs to Boolean threshold circuits (circuits with unbounded fan-in $\mathrm{AND}$, $\mathrm{OR}$, and $\mathrm{MAJORITY}$/$\mathrm{THRESHOLD}$ gates):

  1. Formalizing Crystalline EGNNs: A crystal is represented by atomic attributes $A$, fractional coordinates $F \in [0, 1)^{3 \times n}$, and a lattice basis $L \in \mathbb{R}^{3 \times 3}$. The network maps relative fractional positions through a $k$-order Fourier feature transform $\psi_{\text{FT}, k}(f_i - f_j)$, incorporates lattice metric tensors ($L^\top L$), and updates representations via multi-layer perceptrons (MLPs) and neighborhood aggregations.
  2. Circuit Simulation of Primitives:
  3. Demonstrating that basic floating-point arithmetic (addition, multiplication, division, iterated sums, and matrix multiplication) over $p \le \mathrm{poly}(n)$ precision can be carried out in constant depth and polynomial size ($\mathsf{TC}^0$).
  4. Showing that trigonometric functions ($\sin, \cos$) and thus the $k$-order Fourier transform can be evaluated in $O(1)$ depth.
  5. Layer-wise and Network-level Composition: By chaining the message function $\phi_{\text{msg}}$, summation aggregations, and update MLPs $\phi_{\text{upd}}$, the authors compute an explicit circuit depth bound for a single layer and compose them over $q$ layers.

Datasets

Not discussed in the paper. (This is a purely theoretical paper containing mathematical proofs; no empirical benchmarks or datasets were used.)

Key Insights and Ideas

  • Periodic geometry fits inside $\mathsf{TC}^0$: Despite the nonlinearities introduced by periodic boundary conditions (sinusoidal Fourier embeddings) and lattice metric projections ($L^\top L$), these operations do not increase circuit depth beyond $O(1)$.
  • Explicit depth quantification: The paper does not merely state asymptotic inclusion in $\mathsf{TC}^0$; it constructively derives an explicit depth bound for an EGNN layer ($16d_{\text{std}} + 3d_\oplus + 2d_\otimes$) and for the entire network ($q(18d_{\text{std}} + 4d_\oplus + 2d_\otimes)$), where $d_{\text{std}}$, $d_\oplus$, and $d_\otimes$ represent standard floating-point gate depths.
  • A hard ceiling on reasoning: Placing shallow crystalline EGNNs within uniform $\mathsf{TC}^0$ implies they inherit the known computational limits of $\mathsf{TC}^0$. For instance, they cannot compute problems that are complete for $\mathsf{NC}^1$, $\mathsf{L}$, or $\mathsf{P}$ (such as general graph connectivity across unbounded paths or certain iterative constraint-satisfaction problems).
  • Design implications for materials models: To surpass this computational ceiling, architects cannot simply tweak continuous activation functions or embeddings; they must either scale network depth with system size ($q = \omega(1)$), introduce non-local iterative loops, or incorporate higher-order tensor representations.

Key Results

  • Theorem 5.1 (Membership in Uniform $\mathsf{TC}^0$): Under polynomial precision ($p \le \mathrm{poly}(n)$), embedding dimension $d = O(n)$, Fourier order $k = O(n)$, constant layers $q = O(1)$, and $O(1)$-depth, $O(n)$-width MLP components, any crystalline EGNN can be simulated by a uniform threshold circuit family of polynomial size.
  • Circuit Depth: The total simulation depth is bounded by: $$\text{Depth} = q(18d_{\text{std}} + 4d_\oplus + 2d_\otimes) = O(1)$$ confirming that the architecture is strictly confined to $\mathsf{TC}^0$.

Limitations and Future Work

  • Upper Bound Only: The paper proves an upper bound ($\text{EGNN} \subseteq \mathsf{TC}^0$) but does not establish matching lower bounds or pinpoint whether crystalline EGNNs are strictly weaker than full $\mathsf{TC}^0$.
  • Constant Depth Assumption: The results apply to fixed-depth architectures ($q = O(1)$). Many real-world pipelines stack many layers or apply recursive/iterative message passing, which can escape $\mathsf{TC}^0$.
  • Generative Dynamics Excluded: While modern material generation uses diffusion or flow matching that queries an EGNN backbone across many time steps, the analysis covers only a single forward pass of the network, not the full multi-step numerical integration trajectory.

Summary updated

Abstract

Graph neural networks (GNNs) have become a core paradigm for learning on relational data. In materials science, equivariant GNNs (EGNNs) have emerged as a compelling backbone for crystalline-structure prediction, owing to their ability to respect Euclidean symmetries and periodic boundary conditions. Despite strong empirical performance, their expressive power in periodic, symmetry-constrained settings remains poorly understood. This work characterizes the intrinsic computational and expressive limits of EGNNs for crystalline-structure prediction through a circuit-complexity lens. We analyze the computations carried out by EGNN layers acting on node features, atomic coordinates, and lattice matrices, and prove that, under polynomial precision, embedding width $d=O(n)$ for $n$ nodes, $O(1)$ layers, and $O(1)$-depth, $O(n)$-width MLP instantiations of the message/update/readout maps, these models admit a simulation by a uniform $\mathsf{TC}^0$ threshold-circuit family of polynomial size (with an explicit constant-depth bound). Situating EGNNs within $\mathsf{TC}^0$ provides a concrete ceiling on the decision and prediction problems solvable by such architectures under realistic resource constraints and clarifies which architectural modifications (e.g., increased depth, richer geometric primitives, or wider layers) are required to transcend this regime. The analysis complements Weisfeiler-Lehman style results that do not directly transfer to periodic crystals, and offers a complexity-theoretic foundation for symmetry-aware graph learning on crystalline systems.
BibTeX
@misc{cao2025fundamental,
  author = {Yang Cao and Zhao Song and Jiahao Zhang and Jiale Zhao},
  title = {{Fundamental Limits of Crystalline Equivariant Graph Neural Networks: A Circuit Complexity Perspective}},
  year = {2025},
  eprint = {2510.05494},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2510.05494},
}

Loading related content...

Figure