🤖 AI

Separation Power of Equivariant Neural Networks

This paper provides a comprehensive characterization of the separation power of equivariant neural networks, revealing that non-polynomial activations achieve maximum expressivity, depth offers improvements only up to a specific threshold, and block decomposition creates a hierarchical framework for comparing model capabilities.

Original authors: Marco Pacini, Xiaowen Dong, Bruno Lepri, Gabriele Santin

Published 2026-06-05

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Marco Pacini, Xiaowen Dong, Bruno Lepri, Gabriele Santin

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you have a team of detectives (the neural networks) trying to solve a mystery. Their job is to look at a pile of clues (the input data) and decide: "Are these two clues actually the same thing, or are they different?"

Sometimes, the clues are disguised. Maybe one clue is just the other clue rotated, flipped, or shuffled around. A good detective team needs to know when to say, "Hey, these are actually the same!" (because of the disguise) and when to say, "Nope, these are totally different."

This paper is about measuring the "Separation Power" of these detective teams. In simple terms, it asks: How good is this specific type of AI at telling different things apart, while still respecting the rules of the game (like symmetry or rotation)?

Here is a breakdown of what the authors discovered, using everyday analogies:

1. The Core Problem: The "Twin" Trick

To figure out if a detective team can tell two things apart, the authors invented a clever trick. Instead of asking, "Can you tell Clue A from Clue B?", they ask: "If you look at Clue A and Clue B at the same time, can you prove they are identical?"

They created a "Twin Network" that takes two inputs and subtracts them. If the result is zero, the network thinks they are the same. The paper maps out exactly which pairs of inputs will always result in zero, no matter how the network is tweaked. This map tells us the limits of the network's vision.

2. The Magic of the "Activation" (The Brain's Spark)

Neural networks have a special ingredient called an "activation function" (like ReLU or Sigmoid) that decides how neurons fire. It's like the spark that makes the brain think.

The Finding: As long as the spark isn't a simple, straight line (a polynomial), it doesn't matter which spark you use.
The Analogy: Imagine you are baking a cake. Whether you use a vanilla extract, a strawberry extract, or a chocolate extract (as long as it's not just plain water), the cake will rise to the same maximum height. The paper proves that any complex, non-linear activation function gives the network the maximum possible ability to distinguish between inputs. You don't need to hunt for a "super-spark"; the standard ones are already at the top of their game.

3. Depth: How Many Layers Make a Difference?

You might think that adding more layers (making the network deeper) always makes it smarter.

The Finding: Adding layers helps up to a certain point, but then it hits a ceiling.
The Analogy: Think of a game of "Telephone." If you whisper a message through 2 people, it might get clearer. If you whisper it through 10 people, it might get even clearer. But if you whisper it through 100 people, it doesn't get any more clear than it was at 10. The network's ability to tell things apart stabilizes. Once you reach a specific depth, adding more layers is just extra work with no extra vision.

4. The "Width" Trap: More Neurons Don't Mean Better Vision

In many AI models, people make the layers "wider" (adding more neurons) hoping it will help the model understand better.

The Finding: For these specific types of networks, making the hidden layers wider (adding more invariant features) does not help them tell different inputs apart.
The Analogy: Imagine a security guard at a door. If you hire 100 guards instead of 1, and they all have the exact same instructions and eyesight, the door isn't any safer. The network's ability to distinguish inputs depends on what it sees, not how many eyes are looking at it. Adding more "eyes" that see the same way doesn't improve the separation power.

5. The Hierarchy of "Blocks"

These networks are built out of different "blocks" or building blocks, which correspond to different types of symmetry (like rotating a shape vs. shuffling a deck of cards).

The Finding: Some blocks are better at separating inputs than others. There is a strict hierarchy.
The Analogy: Think of a set of keys. A master key (the "regular representation") can open every door (separate almost everything). A simple key (the "invariant representation") can only open one specific door. The paper shows that if you use the "master key" blocks in your network, you get the best possible separation. If you use the "simple key" blocks, your network is more limited. It's a ladder: the higher you go on the ladder of complexity, the more things you can tell apart.

6. Real-World Examples

The authors tested these rules on two common types of AI:

Invariant Graph Networks (IGNs): Used for analyzing social networks or molecules. They found that these networks are just as good at telling graphs apart as the famous "Weisfeiler-Leman" test (a gold standard in math), and they don't need huge, expensive networks to do it.
Circular CNNs: Used for things like analyzing circular data (like a clock face or a ring of sensors). They found that the size of the "filter" (how much of the circle the network looks at at once) changes how well it can tell patterns apart. A filter that looks at the whole circle is better than one that looks at just a tiny slice.

Summary

The paper gives us a rulebook for building these specific types of AI:

Don't worry about the activation function: Just pick a standard, non-linear one; they are all equally powerful.
Don't go too deep: Stop adding layers once you hit the stabilization point; extra depth is useless for separation.
Don't just make it wider: Adding more neurons doesn't help you tell things apart.
Choose your blocks wisely: Use the most complex "blocks" available if you want the network to see the most differences.

Essentially, the paper tells us that for these networks, quality of structure matters more than quantity of layers or neurons.

Technical Summary: Separation Power of Equivariant Neural Networks

Problem Statement

The expressivity of machine learning models is often quantified by their universality—the ability to approximate any function within a specific class. However, for equivariant neural networks (those respecting symmetries like permutations or rotations), universality is constrained by the network's inherent inability to distinguish between inputs that are equivalent under the symmetry group. This limitation creates a complex interaction between a network's capacity to discriminate distinct inputs and the invariant/equivariant structures it must preserve.

While the graph learning community has extensively studied the separation power of Graph Neural Networks (GNNs) using the Weisfeiler-Leman (WL) test and homomorphism counting, these combinatorial tools have severe limitations when applied to broader classes of equivariant models, particularly those processing geometric data or utilizing regular convolutions. There is a lack of fine-grained analytical tools to characterize the set of indistinguishable inputs (the identification relation) for general equivariant neural networks with non-polynomial activations, finite-dimensional representations, and permutation equivariance.

Methodology

The paper introduces a theoretical framework to characterize the separation power $\rho(\mathcal{N})$ of a family of equivariant neural networks $\mathcal{N}$ . The separation power is defined as the equivalence relation identifying pairs of inputs $(\alpha, \beta)$ such that $f(\alpha) = f(\beta)$ for all $f \in \mathcal{N}$ .

The core methodological contribution is the "Twin Network Trick", which transforms the problem of identifying indistinguishable inputs into a zero locus problem. By constructing a twin network $\hat{\eta}(\alpha, \beta) = \eta(\alpha) - \eta(\beta)$ , the authors reformulate the identification relation as finding the set of points mapped to zero by the twin network space.

This reduction allows the authors to apply recursive techniques derived from the theory of functional equations. Specifically, they leverage results regarding linear functional equations involving non-polynomial continuous functions (e.g., ReLU, sigmoid) to derive an explicit, recursive formula for the zero locus. This formula relates the zero locus of a network of depth $d$ to the zero loci of networks of depth $d-1$ , involving unions and intersections of specific subspaces defined by the network's architecture and bias terms.

The analysis assumes:

Permutation Representations: The networks act on spaces of real-valued functions over finite sets, equivariant under finite groups acting as permutations.
Non-Polynomial Activations: The activation functions are continuous and non-polynomial.
Complete Bias: The affine layers include bias terms subordinate to the orbit partition of the representation space.

Key Contributions and Results

1. Complete Characterization of Indistinguishable Inputs

The paper provides a complete characterization of the set of input pairs identified by networks with a fixed architecture.

Theorem 1 (Characterization Theorem): Establishes a recursive formula for the zero locus of a neural space. This formula decomposes the identification relation based on the network's depth, activation properties, and the partition of the representation space induced by the bias terms.

2. Equivalence of Non-Polynomial Activations

Theorem 2: Proves that for a fixed architecture, any continuous, real, element-wise, non-polynomial activation function yields the same separation power. Consequently, common activations like ReLU, sigmoid, and tanh are equivalent in their ability to distinguish inputs and all achieve the maximum possible separation power for that architecture. Polynomial activations are excluded from this equivalence.

3. The Role of Depth

Theorem 3: Demonstrates that increasing the depth of the network enhances separation power only up to a specific repetition threshold. Beyond this threshold, adding further layers of the same type does not improve the ability to distinguish inputs; the separation power stabilizes.
- For $k$ -Invariant Graph Networks (IGNs), this threshold is proportional to the threshold of the $k$ -WL test.
- For networks with regular hidden representations, stabilization occurs after just one layer repetition.

4. Independence from Hidden Feature Width and Invariant Features

Theorem 4 & Remark 1: Shows that the separation power is independent of the multiplicity of blocks in hidden representations. Specifically, increasing the width of invariant hidden features (e.g., the dimension of the feature space in IGNs) does not improve the network's ability to distinguish inputs. The separation power of a network with hidden representation $V \otimes \mathbb{R}^f$ is identical to that of a network with hidden representation $V$ .

5. Hierarchy of Representation Types

Theorem 5: Establishes a hierarchy in separation power based on the type of representation used in the layers. The separation power corresponds to the partial ordering of subgroups of the symmetry group.
- Representations induced by smaller subgroups (e.g., the trivial subgroup $\{e\}$ , corresponding to the regular representation) yield maximal separation power.
- Representations induced by larger subgroups (e.g., the group $G$ itself, corresponding to invariant vectors) yield minimal separation power.
- This implies that using regular representations ( $\mathbb{R}^G$ ) in hidden layers is sufficient to achieve the maximum separation power allowed by the architecture.

Implications for Practical Models

The authors apply these general results to specific practical models:

Invariant Graph Networks (IGNs): The results strengthen previous findings by showing that $k$ -IGNs match the separation power of the $k$ -WL test regardless of the hidden feature dimensions. This resolves the need for previous results that required "large" hidden feature widths to achieve universality.
Circular CNNs: The separation power of Circular Convolutional Neural Networks is shown to depend on the filter size. Specifically, networks with larger filter supports (approaching the full group size) have strictly finer separation power than those with smaller supports, forming a strict hierarchy.

Significance and Claims

The paper claims to provide a necessary condition for understanding the universality of equivariant neural networks. By precisely characterizing the identification relation $\rho(\mathcal{N})$ , the authors enable a classification of hyperparameters and architectural choices into two categories:

Separation-Determining: Choices that directly influence the set of distinguishable inputs (e.g., activation type, depth up to a threshold, representation type). These significantly impact both approximation ability and computational cost.
Separation-Independent: Choices that do not affect the set of distinguishable inputs (e.g., hidden feature width, multiplicity of blocks). These may influence approximation within the constraints of the separation power but do not expand the class of distinguishable inputs.

The authors emphasize that their framework is limited to permutation representations and non-polynomial activations. They acknowledge that their approach does not currently extend to models using Clebsch-Gordan coefficients or polynomial approaches, nor does it fully address cases where bias terms are absent (though it can provide bounds in such cases). The work serves as a foundational theoretical tool for analyzing the expressivity of equivariant models beyond the combinatorial constraints of graph-specific tests.