Expressivity Barriers in Categorical Equivariant Networks

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.