Neural Discovery of Permutation Subgroups

Pavan Karjol, Rohan Kashyap, A. P. Prathosh

Introduction

In deep learning, inductive biases—such as translation invariance in Convolutional Neural Networks (CNNs) or permutation invariance in Deep Sets—are fundamental to achieving high performance and data efficiency. However, these biases typically require researchers to specify the exact symmetry group of the data beforehand. In many real-world applications, the underlying symmetry may be unknown or only partially understood. For instance, a dataset might be invariant under a specific subset of permutations or a particular cyclic order.

Manually identifying the correct subgroup from the permutation group $S_n$ is computationally intractable due to the explosive growth of possible subgroups as $n$ increases. This paper proposes a framework for the automatic discovery of permutation subgroups, allowing a model to learn the specific symmetry of the data while simultaneously training for a downstream task.

The Framework for Symmetry Discovery

The authors introduce an elegant architectural modification to address the discovery problem. Instead of designing a network specifically for an unknown subgroup $H$, they utilize a network $\phi$ that is invariant to a larger, known "parent" group $G$ (such as the full permutation group $S_n$ or a cyclic group $Z_n$).

The model is defined as: $$\psi(x) = \phi(M x)$$ where $M$ is a learnable linear transformation.

During training, the weights of $M$ are optimized via backpropagation. As the model minimizes the task loss, $M$ learns to transform the input data into a canonical form that the $G$-invariant backbone can process effectively. In practice, $M$ acts as a mechanism to "mask" irrelevant features or "reorder" inputs to align with the symmetries recognized by $\phi$. This leverages the concept of conjugacy: many subgroups are essentially shuffled versions of one another, and a linear layer is perfectly suited to "un-shuffle" these inputs.

Theoretical Expressivity

A key contribution of the paper is the theoretical justification for this approach. The authors prove that for several significant classes of subgroups—including subset permutations ($S_k$), cyclic groups ($Z_k$), and dihedral groups ($D_{2k}$)—there exists a linear transformation $M$ that enables a $G$-invariant network to represent any $H$-invariant function. This suggests that the flexibility of the linear layer, when combined with a broader symmetry backbone, is sufficient to capture more restricted, hidden symmetries without hardcoding them.

Experimental Evaluation

The framework was evaluated on two distinct tasks designed to test different types of subgroup discovery:

  1. Image-Digit Sum (MNIST): Given a set of $n$ MNIST images, the model must predict the sum of a specific subset of $k$ images. This requires the model to discover the $S_k$ subgroup—identifying which indices are relevant and treating them invariantly.
  2. Symmetric Polynomial Regression: The model is tasked with regressing synthetic polynomials invariant under specific subgroups like $Z_5$ or $Z_8$. This tests the ability to recover cyclic and dihedral structures from raw numerical data.

Key Results

  • Performance: In the Image-Digit Sum task, the proposed method significantly outperformed recurrent architectures like LSTMs, which often struggle with long-range permutation symmetries. Notably, it achieved accuracy levels nearly identical to "Deep Sets" models that were explicitly told the subgroup $S_k$ in advance.
  • Discovery Accuracy: For polynomial regression, the model identified the correct indices of the hidden subgroup with 80% to 100% accuracy across various group sizes ($Z_4$ to $Z_{16}$), provided sufficient training data was available.
  • Interpretability: The learned matrix $M$ provides transparency. In the MNIST experiments, $M$ often converged to a sparse mask, clearly identifying the indices the model deemed relevant to the symmetry, providing a clear window into what the model discovered.

Discussion and Limitations

While the framework successfully discovers specific subgroups, it currently requires the user to specify the class of the subgroup (e.g., cyclic vs. subset) to select the appropriate $G$-invariant backbone. Furthermore, the work is presently limited to discrete permutation subgroups.

Future research directions include extending this logic to continuous symmetries (such as 3D rotations or Lie groups) and exploring unsupervised symmetry discovery, where the model identifies patterns without the need for explicit task labels. By moving away from hardcoded symmetries, this approach paves the way for more flexible and adaptive geometric deep learning.

Summary updated

BibTeX
@inproceedings{karjol2023neural,
  author = {Pavan Karjol and Rohan Kashyap and A. P. Prathosh},
  title = {{Neural Discovery of Permutation Subgroups}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2023},
}
Figure