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.
Introduction
In the search for novel materials, predicting the physical properties of crystals is a foundational challenge. Crystalline structures are unique because they are not merely static graphs; they are defined by periodic boundary conditions—where the structure repeats infinitely in space—and must adhere to Euclidean symmetries (translations, rotations, and reflections).
Equivariant Graph Neural Networks (EGNNs) have become the standard architecture for these tasks because they are designed to handle these geometric constraints natively. However, while their empirical success is well-documented, their theoretical limits have remained elusive. Traditional methods for measuring GNN expressive power, such as the Weisfeiler-Lehman (WL) hierarchy, are designed for discrete graphs and struggle to account for the continuous 3D coordinates and periodic lattices inherent in crystallography. This research shifts the perspective to circuit complexity, establishing a formal computational "ceiling" for what these models can actually compute.
The Circuit Complexity Lens
To understand the fundamental limits of EGNNs, the authors ask: What is the simplest "computer" (circuit) that can simulate an EGNN? By mapping the operations of a neural network to the language of Boolean circuit complexity, we can identify which problems are fundamentally beyond the reach of specific architectures.
Specifically, the paper focuses on the complexity class $\mathsf{TC}^0$. This class consists of Boolean circuits with constant depth and polynomial size, using NOT, AND, OR, and "threshold" gates (which output 1 if at least $k$ inputs are 1). Threshold gates are essentially simplified versions of the neurons used in deep learning, making $\mathsf{TC}^0$ a natural fit for analyzing neural networks.
Methodology: Simulating Crystalline EGNNs
The study analyzes a version of EGNNs tailored for crystals, which processes three primary inputs:
- Node features: Atomic identities and properties.
- Atomic coordinates: Positions in 3D space.
- Lattice matrices: The vectors defining the periodic "box" of the crystal.
The core of the proof involves breaking down the EGNN's mathematical operations—message passing, coordinate updates, and $k$-order Fourier transforms used to handle periodic boundaries—and demonstrating that they can be simulated by a uniform $\mathsf{TC}^0$ circuit family.
A key bridge between theory and practice in this analysis is the assumption of polynomial precision (floating-point arithmetic). This ensures the results reflect how GPUs and hardware actually handle numerical data, rather than assuming infinite-precision real numbers which are physically unrealizable.
Key Results: The $\mathsf{TC}^0$ Ceiling
The primary contribution of this work is Theorem 5.1, which formally states that an EGNN with:
- Polynomial precision $p \le \text{poly}(n)$
- Embedding width $d = O(n)$
- A constant number of layers $q = O(1)$
- MLP components with constant depth
...can be realized by a uniform $\mathsf{TC}^0$ circuit of polynomial size.
The authors provide an explicit constant-depth bound for the resulting circuit: $q(18d_{std} + 4d_{\oplus} + 2d_{\otimes})$. This formula counts the logic gate "layers" required to simulate the network, providing a rigorous blueprint of its computational complexity.
Implications of the Ceiling
By situating EGNNs within $\mathsf{TC}^0$, the research identifies what these models cannot do. There are known problems (such as deep sequential logic or specific parity-related problems) that $\mathsf{TC}^0$ circuits cannot solve efficiently. This implies that standard, shallow EGNNs may have inherent "blind spots" regardless of the volume of training data provided.
Furthermore, the analysis reveals that complex-looking geometric operations—such as calculating lattice-aware distances or handling periodic boundaries via Fourier transforms—are computationally efficient enough to remain within the $\mathsf{TC}^0$ regime. They do not, by themselves, increase the fundamental complexity of the model.
Architectural Guidance and Future Work
This theoretical framework provides clear guidance for researchers looking to build more powerful models. To "break out" of the $\mathsf{TC}^0$ class and solve more complex physical problems, one must:
- Increase Depth: Move beyond $O(1)$ layers to allow for more sequential reasoning.
- Increase Width: Use wider layers that scale beyond $O(n)$.
- Richer Primitives: Introduce more complex geometric operations that cannot be reduced to constant-depth threshold logic.
Future research is needed to determine where specific physical properties fall on the complexity scale. For example, if predicting a crystal's "formation energy" is proven to be a problem harder than $\mathsf{TC}^0$, it would explain why current shallow EGNNs might struggle with that specific task, regardless of optimization. This work provides the mathematical foundation to begin aligning model architecture with the intrinsic difficulty of the physics problems they are meant to solve.
Summary updated