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):
- 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.
- Circuit Simulation of Primitives:
- 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$).
- Showing that trigonometric functions ($\sin, \cos$) and thus the $k$-order Fourier transform can be evaluated in $O(1)$ depth.
- 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