acceptodds
Under review as a conference paper at ICLR 2027

Expressivity Barriers in Categorical Equivariant Networks

Abstract

Categorical equivariant networks process features linked by restriction maps—rules that transfer a feature between related objects—and require outputs to commute with these transfers. We ask when such networks can approximate every continuous target obeying this rule, with arbitrarily small uniform error on compact sets. For a specified layer class, we give two complementary results that remain valid as depth and hidden width increase. First, in a simple graph example, every network output is affine, so the target z ↦ ‖z‖²z, which obeys the same rule, has a positive minimum approximation error. Input-dependent scalar gates restore nonlinear dependence but may leave output directions unreachable. For graph systems whose cycle symmetries form a finite group, a target can be approximated arbitrarily well exactly when its value at each input lies in the available directions. Independent inputs can make deficient spans rare, reducing average error while leaving nonzero worst-case error at deficient inputs. We formalize the algebraic parts in Cubical Agda and test the obstruction and a repair in a controlled experiment. These results guide whether to add scalar information, independent inputs, or vector features when depth and width cannot help.

Primary area:
learning theory
Keywords:
equivariant neural networks, expressivity, universal approximation, category theory, cellular sheaves, holonomy, homotopy type theory, formal verification

Reviews

Among:
Shape:
1234this paper, Top 4%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.33 over 3 reviews, above 96% of the others.
Reviewer_nn8FOpenReview ↗
Rating
3
Confidence
3(+1)
Informativeness
3
Presentation
1
Soundness
3
Read review
Paper summary

The paper studies whether categorical equivariant networks, whose layers must respect prescribed feature transfers, can approximate every continuous target satisfying those same constraints. It shows that increasing depth and width cannot overcome certain restrictions imposed by the permitted layers. Its main contributions are:

  • It proves that increasing network size may not improve expressivity. For the specified layer class, the paper identifies restrictions that survive arbitrary depth and hidden width. In certain graph settings, every network remains affine despite containing nonlinear operations, so it cannot approximate even simple compatible nonlinear targets arbitrarily well (Theorems 3.2 and 4.2).
  • It explains the capabilities and limitations of more flexible scalar gates. For the graph systems studied, the paper characterizes exactly which targets become approximable when gates can depend on the input. These gates restore nonlinear behavior, but they may still fail to produce the output directions required by the target (Theorem 6.1).
  • It establishes when the bundle-based construction supports universal approximation. The paper characterizes when a linear readout can recover output features from their collected views. When such a readout exists, ordinary neural networks operating inside the bundle can approximate every continuous target satisfying the consistency requirements (Proposition 7.1).

I find the paper’s broader framework and its insights into architectural expressivity interesting, and I lean toward acceptance. The theoretical results appear sound based on my understanding, although I cannot confidently verify the correctness of every proof. My confidence in this recommendation is therefore limited.

Critical strengths

The categorical perspective provides a broader analysis of equivariant architectures. By considering relations between different feature spaces, including noninvertible restrictions, the paper examines architectural constraints that are not fully described by a symmetry group alone. It distinguishes the functions allowed by the consistency requirements from those realizable by the permitted layers, and proves that this gap can persist despite arbitrary depth and hidden width. These results may provide useful guidance on when improving expressivity requires changes to the feature representation or layer construction.

Critical weaknesses
  • The presentation is difficult to follow. The main text assumes substantial familiarity with categorical thoery and does not sufficiently explain its connection to familiar equivariant architectures. A concise terminology guide and a complete worked example of the network computation would make the motivation and scope of the theoretical results clearer.

  • The practical relevance of the analyzed architecture needs stronger motivation. The complete characterizations concern particular graph feature systems, and the scalar-gate result additionally requires finite holonomy. Although these assumptions are acknowledged, their relevance to realistic learning problems remains insufficiently established. A concrete application motivating the restriction would help readers understand when the proposed criteria provide useful architectural guidance.

Questions for authors
  • Connection to equivariant approximation theory. Could the authors explicitly distinguish systematic degeneration that is unavoidable for all equivariant maps between the chosen feature spaces from additional degeneration caused by a specific model parameterization? Prior work has identified limitations in preserving orientation information with certain equivariant features [1-3]. How do the restrictions on output directions in this paper relate to these phenomena? Explaining how these phenomena can be overcome by changing the equivariant parameterization.

  • Guidelines for model design. Could the authors try to translate their theoretical findings into clear guidelines for designing expressive equivariant models? In particular, how should feature representations, nonlinear operations, and readout maps be chosen to avoid the identified expressivity barriers?

[1]: Joshi et al. (2023). "On the Expressive Power of Geometric Graph Neural Networks", ICML 2023.

[2]: Kaba et al. (2023). "Improving Equivariant Networks with Probabilistic Symmetry Breaking", NeurIPS 2023 Workshop on Symmetry and Geometry in Neural Representations.

[3]: Lin et al. (2026). "Reducing Symmetry Increase in Equivariant Neural Networks", ICLR 2026.

2 comments

Thank you for the careful reading and for identifying where the architectural consequences need a clearer explanation. We have added explanations of the basic terms where they first appear and a worked edge computation in Section 2, and expanded the design discussion in Sections 6–7. The additions and replacement passages are marked in red.

  1. Symmetry constraints versus restrictions of the parameterization

The holonomy group H is generated by transporting features around graph cycles. For an input x, the stabilizer H_x consists of the symmetries in H that fix x. Equivariance requires each of these symmetries to fix f(x) as well. Thus every deterministic equivariant map satisfies f(x) ∈ W^{H_x}, where W^{H_x} is the set of output vectors fixed by those symmetries. The chosen output feature space can force additional output symmetries, as studied by Lin et al. (2026).

Our layers impose a further restriction. Even after allowing multiplication by any continuous invariant scalar function, their outputs at x must lie in E(x), the set of values Lx + c where L is an equivariant linear map and c is fixed by all symmetries in H. Here an invariant scalar function is one whose value does not change under these symmetries. Theorem 6.1 proves that, for the stated graph feature diagrams with finite H, this enlarged class can approximate every continuous equivariant map uniformly on compact sets if and only if E(x) = W^{H_x} at every input. This separates the output values allowed by symmetry from those available to our layers.

For example, consider the planar action of D4, the eight symmetries of a square. A nonzero input x off the reflection axes is fixed only by the identity, so symmetry allows any output vector. Nevertheless, our enlarged class can only output a multiple of x. The identity map f(x) = x belongs to this class: its output is unchanged, so it has exactly the same symmetries as the input. Preserving those symmetries therefore does not guarantee that the class can approximate every equivariant target. In particular, it cannot approximate a target whose value at x lies outside the line through x.

For planar vectors written as complex numbers z, the added vector feature p(z) = conjugate(z)^3 supplies the missing directions. Combinations of z and p(z) with suitably chosen invariant scalar coefficients can approximate every continuous D4-equivariant map uniformly on compact sets. Section 6 gives this construction, which preserves deterministic equivariance.

We have added the suggested references to Section 9 (Discussion) and clarified their relation to our results. Joshi et al. (2023) analyze how tensor features and the invariant scalars computed from them affect geometric GNN expressivity. Lin et al. (2026) study when feature representations force outputs to have more symmetries than their inputs. We cite the suggested probabilistic symmetry-breaking paper as Lawrence et al. (2025), following the published author list and year. Their method allows individual samples to break input symmetries while the output distribution conditional on the input remains equivariant. Our construction instead adds vector features to approximate deterministic equivariant targets.

  1. Guidelines for model design and practical scope

The revised Section 6 explains the separate roles of scalar and vector features: invariant scalar features distinguish inputs not related by symmetry, while equivariant vector features span the output vectors allowed by symmetry at each input. For the input distributions analyzed in the paper, supplying several independently varying input vectors can reduce average approximation error because their span is less often deficient. Duplicating a single vector in more hidden channels does not enlarge its span. Section 7 gives a test based on linear equations for whether a linear readout that commutes with the prescribed transfers can recover each output feature from the collection of its restricted copies. A successful test supplies the reconstruction used in the approximation theorem. A failed test rules out this reconstruction, but does not by itself rule out approximation.

Section 9 describes a possible application: learning response functions F_a and F_b in two local coordinate frames, with a fixed map T transferring features between them. Processing a feature and then transferring the response must agree with transferring the feature and then processing it: F_b(Tz) = T F_a(z). Our experiments use simple feature diagrams with fixed transfer maps and target responses that satisfy this equation. They test whether the permitted layers can approximate these responses and whether the proposed changes to the layers or features remove the approximation barrier. They do not establish performance on a real sensor or graph benchmark, and the revised text states this limitation explicitly.

Thank you for your detailed response. It’s been a pleasure discussing this paper with you. Your clarification offers useful insight into the expressivity limitations of equivariant models that rely on scalarization. I have increased my confidence in my assessment accordingly and will maintain my score, which already supports acceptance.

Reviewer_UeK5OpenReview ↗
Rating
4
Confidence
4
Informativeness
3
Presentation
2
Soundness
3
Read review
Paper summary

Categorical equivariant networks were recently developed as an extension of Cohen-Welling's G-CNN (group-equivariant networks). This paper studies categorical equivariant networks, especially the expressivity limits of categorical equivariant networks, including an affine barrier, exact characterizations of reachable output directions, and necessary and sufficient approximation criteria under finite holonomy.

Critical strengths

The paper clarifies when expressivity barriers arise in categorical equivariant networks and how they can be repaired. The contributions are mathematically substantial and technically rigorous (as far as I was able to check), including precise approximation error bounds and supporting controlled experiments. I especially find the necessary and sufficient condition for equivariant compilation is interesting and valuable (where note that equivariant compilation is one of the mathematical conditions under which the universal approximation theorem for categorical equivariant neural networks has been established in prior work). I also found the use of homotopy type theory interesting. Overall, I think this is a significant contribution deserving acceptance/publication at ICLR.

Critical weaknesses

The paper is mathematically quite heavy and might be difficult to understand for some ML researchers. The experiments are limited to synthetic tasks (although the main contributions are theoretical/mathematical and those synthetic experiments support the theory/math). Appropriate citations are lacking occasionally: for example, although the paper says "a property we call categorical equivariance" in the first paragraph of the introduction, this notion was actually introduced in prior work and the paper does not cite the source here.

Questions for authors

The universal approximation theorem for categorical equivariant networks has been established already, under several mathematical conditions including equivariant compilation. The paper analyzes when equivariant compilation holds, providing a necessary and sufficient condition for equivariant compilation in the finite category case, if I understand correctly.

Q1. Then, my question is: how easy/straightforward is it to check the necessary and sufficient condition provided? This question concerns how useful the paper result is for checking the condition in practice (practical applicability matters).

Q2. The original categorical equivariant neural networks were formulated in a broader setting covering both finite and infinite categories. Even classic Cohen-Welling-style group-equivariant neural networks (as a special case of categorical equivariant neural networks) often use infinite groups of transformations, e.g. continuous Lie groups such as SE(3). Can you say anything about expressivity of such a broader class of categorical equivariant neural networks?

2 comments

Thank you for the careful assessment and the questions about the usefulness and scope of the reconstruction criterion. We also agree that the opening attribution was insufficient: the first paragraph now explicitly credits Maruyama (2025) for categorical equivariance. Additions and replacement passages are marked in red.

Q1. How can the criterion be checked?

For an explicitly specified finite category and fixed restriction matrices, it is a linear feasibility problem. Introduce a matrix R_a: DY(a) → Y(a) at each object and impose, for every arrow u: b → a,

Y(u) R_a = R_b DY(u),       R_a (Δ_Y)_a = I_{Y(a)}.

Every coefficient is known. A solution constructs a natural linear compiler; inconsistency rules out that reconstruction. Gaussian elimination is polynomial in the size of the assembled system, although the arrow bundle can be large. With rational restriction matrices, the calculation is exact. Floating-point residuals require care near rank deficiency.

We have added these equations in Section 7 and the system dimensions in Appendix B.3. The revised Section 2 also works through the edge example: naturality forces every linear readout DY → Y to be zero, so none can invert Δ_Y. Changing the edge feature to two independent endpoint values admits the coordinate-selecting compiler of Appendix H.1. The finite-poset implementation was already part of the verification code described in Appendix F.1.

The criterion characterizes this natural linear reconstruction, not every possible architecture or every route to universality. Its failure alone does not imply non-density; the negative results require the separate invariant proved in the paper.

Q2. What extends beyond finite holonomy or finite categories?

Finite diagram size and finite holonomy are different assumptions. The affine barrier and Theorem 4.2 hold on the stated finite graph diagrams even when their orthogonal cycle transports generate an infinite group. Thus the 1/4 radial-cubic error floor does not require finite holonomy. The exact scalar-gate closure in Theorem 6.1 does use finite holonomy.

For infinite orthogonal holonomy, continuous equivariant maps are equivariant under its compact closure. Haar averaging then provides a mathematical approximation mechanism, as discussed in Appendix C; realizing it exactly with a prescribed finite network requires a further argument. We have made these boundaries explicit in Section 9. General infinite categories and noncompact groups such as SE(3) require additional choices of function spaces and continuity or boundedness assumptions. The finite-category reconstruction theorem does not establish a characterization in that broader setting.

Thanks for the reply. Considering the reply, I think my clear accept evaluation is appropriate for this paper.

Reviewer_iJDwOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

The paper studies the expressivity of categorical equivariant networks, whose layers must respect how features are passed between related objects, for example from an edge to its endpoints. The authors show that for a certain class of layers, some targets cannot be approximated arbitrarily well no matter how wide or deep a network is. They propose changes to the layers and features in order to fix this. The authors support their claims with proofs of their results, together with a partial Agda formalisation, and test their predictions with small synthetic experiments.

Critical strengths
  1. The main negative result (Theorem 3.2) holds for neural networks of any depth and width that are built from the layers that are given in Definition 2.1. This is important because it shows that the limitation comes from the choice of layers, rather than from the network being too small.
  2. I think that a core strength of the paper is that it suggests ways to overcome the negative result, such as introducing new nonlinear layers (Section 4), richer scalar gates, and an extra vector feature (Section 6). In particular, in Table 2, adding a vector feature brings the error close to zero while the other models stay at their predicted limits. This forms a key part of my overall score, as the authors do not only identify a limitation but also show how it can be addressed.
Critical weaknesses
  1. I found the theoretical sections hard to follow. This may reflect my own background more than the paper, but some extra intuition could help a general ML reader. This has limited my ability to judge the contribution, which is reflected in my low confidence score.
  2. I was not sure how widely the results apply in practice since the experiments are small and synthetic. The authors do acknowledge this in Section 9, however.
Questions for authors
  1. Following on from Definition 2.1, the authors mention that the CENN layers of Maruyama (2025) are covered by their results. Are there other commonly used architectures that are built only from the layers in Definition 2.1?
  2. It is noted in Section 9 that the experiments do not cover full graph-prediction tasks. Do the authors expect that the same problems will appear in real-world graph tasks?
2 comments

Thank you for the thoughtful assessment. We have used the additional revision space to make the mechanism easier to follow: Section 2 now explains the basic terminology more and traces an edge input through a bundle lift, nonlinear processing, and a readout. Section 6 explains the roles of scalar and vector features in the readout f_θ. Additions and replacement passages are marked in red.

Q1. Which other commonly used architectures are covered?

The established correspondence is to the CENN generators in the finite point-base setting specified in Section 2 and Appendix A. We do not claim that standard message-passing GNNs or Neural Sheaf Diffusion are built only from these generators. Their updates can combine independently stored neighboring features, whereas our layers process a feature and its prescribed restrictions and must commute with those restrictions. Bundle neural networks also use node mixing and frame-wise activations outside the analyzed class; the operation-level comparison is in Appendix H.

The feature diagram matters as well. With independent endpoint features, the configuration diagram in Appendix H.1 admits pointwise nonlinear processing through a natural compiler, even though it uses the same edge poset. Thus the results are diagnostics for a specified combination of feature diagrams and generators, not a general barrier for graph architectures.

Q2. Should the same problems occur in real-world graph tasks?

They would persist wherever a model actually satisfies the hypotheses and the required target falls outside the reachable class: increasing data, depth, or hidden width cannot remove that expressivity obstruction. Whether a particular practical graph task has those properties requires checking its features, operations, target, and input distribution. Our experiments do not establish how often this occurs in existing graph benchmarks.

Thank you for your response. I maintain my opinion that this paper will find interest at ICLR, which is why I will maintain my score, which was already a 3 (weak acceptance). I recommend that the authors continue to do anything they can to improve the paper's readability, particularly on the maths side of things.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.