Drawback of Enforcing Equivariance and its Compensation via the Lens of Expressive Power

Technical Summary: Drawback of Enforcing Equivariance and its Compensation via the Lens of Expressive Power

Problem Statement
Equivariant neural networks (ENNs) have become a dominant approach for leveraging intrinsic data symmetries, achieving strong performance in domains ranging from point cloud processing to graph neural networks. These networks typically enforce equivariance either through architectural design (Layer-wise Equivariant Networks, or LENs) or optimization constraints (General Equivariant Networks, or GENs). While the benefits of equivariance regarding generalization and sample efficiency are well-documented, the trade-off concerning expressive power remains theoretically under-explored. Specifically, it is unclear whether restricting the hypothesis space to equivariant models inherently reduces the network's ability to approximate target functions compared to general networks (GNs) of the same size, and whether enforcing equivariance at every layer (LENs) imposes stricter limitations than global equivariance (GENs).

Methodology
The paper investigates this trade-off by focusing on two-layer ReLU networks. The authors employ a geometric analysis of the network's internal structure, specifically examining boundary hyperplanes (where the piece-wise linear function changes slope) and channel vectors (the weight vectors defining the activation boundaries).

1. Geometric Characterization: The authors define boundary hyperplanes and prove that for a GEN, the set of these hyperplanes must be symmetric with respect to the group representation. For LENs, they derive a stricter condition: the channel vectors themselves must form a symmetric set under the group action.
2. Constructive Counter-Examples: To demonstrate the limitations, the authors construct specific invariant target functions on $\mathbb{R}^2$ and analyze the approximation capabilities of GNs, GENs, and LENs under fixed neuron counts (specifically 1-neuron and 3-neuron settings).
3. Compensation Analysis: The paper investigates whether increasing the model size (number of neurons) can compensate for the expressive power loss. This involves constructing specific LEN architectures that replicate the functions of smaller GNs or GENs and analyzing the resulting hypothesis space dimensionality.

Key Contributions and Results

• Expressive Power Deficit: The paper proves that enforcing equivariance strictly reduces expressive power for a fixed model size.

  • GNs vs. GENs: For a specific invariant target function, a 1-neuron GN can approximate the function with non-zero error, whereas the only 1-neuron GEN is the zero function, resulting in strictly higher expected loss.
  • GENs vs. LENs: For a target function requiring three neurons to be perfectly represented by a GN or GEN, a LEN requires at least six neurons. This is because the symmetry constraints on channel vectors in LENs force the network to include parallel vectors (e.g., $\alpha$ and $-\alpha$) as distinct channels to satisfy layer-wise equivariance, effectively doubling the necessary capacity for certain symmetries.

• Compensation via Model Enlargement: The authors prove that the expressive power loss can be fully compensated by enlarging the model size.

  • Upper Bounds: They demonstrate that enlarging a GEN to a LEN by a factor of $|G|$ (the size of the symmetry group) allows the LEN to represent any invariant function representable by the GEN.
  • Tighter Bounds: Further analysis shows that for invariant functions, a LEN requires at most double the model size of a GEN to represent the same set of functions. This is achieved by constructing a LEN where channel vectors are grouped by their orbits and merged where possible.

• Reduced Hypothesis Complexity: A surprising finding is that while enlarged LENs have more neurons (larger model size), they possess a lower-dimensional hypothesis space compared to GNs of equivalent expressive power.

  • In the constructed example, a 6-neuron LEN representing a specific function has a parameter space of $\mathbb{R}^5$, whereas a 3-neuron GN representing the same function has a parameter space of $\mathbb{R}^9$.
  • This reduction in dimensionality arises because the structural constraints of equivariance force parameters to lie in specific subspaces, reducing the number of independent learnable parameters despite the increased neuron count.

Significance and Claims
The paper claims to provide the first in-depth theoretical examination of the expressive power of layer-wise equivariant neural networks. Its primary significance lies in:

1. Identifying a Drawback: Explicitly demonstrating that equivariance constraints, particularly at the layer level, can inherently limit a model's ability to approximate functions if the model size is not adjusted.
2. Quantifying Compensation: Providing formal upper bounds (specifically a factor of $|G|$ or a factor of 2) on the model size enlargement required to recover the lost expressive power.
3. Reconciling Generalization: Arguing that the "cost" of increased model size is offset by a reduction in hypothesis space dimensionality. This suggests that appropriately sized LENs may offer superior generalizability compared to standard GNs, not just due to inductive bias, but because they operate in a lower-dimensional parameter space while maintaining comparable approximation capabilities.

The authors conclude that while enforcing equivariance has a drawback in raw expressive power for fixed sizes, this is a manageable trade-off. By appropriately scaling the model, LENs become a competitive solution that balances approximation capability with improved generalization potential through reduced hypothesis complexity.