Equivariant Maps for Hierarchical Structures

Renhao Wang, Marjan Albooyeh, Siamak Ravanbakhsh

Abstract

While using invariant and equivariant maps, it is possible to apply deep learning to a range of primitive data structures, a formalism for dealing with hierarchy is lacking. This is a significant issue because many practical structures are hierarchies of simple building blocks; some examples include sequences of sets, graphs of graphs, or multiresolution images. Observing that the symmetry of a hierarchical structure is the "wreath product" of symmetries of the building blocks, we express the equivariant map for the hierarchy using an intuitive combination of the equivariant linear layers of the building blocks. More generally, we show that any equivariant map for the hierarchy has this form. To demonstrate the effectiveness of this approach to model design, we consider its application in the semantic segmentation of point-cloud data. By voxelizing the point cloud, we impose a hierarchy of translation and permutation symmetries on the data and report state-of-the-art on Semantic3D, S3DIS, and vKITTI, that include some of the largest real-world point-cloud benchmarks.

Introduction

Deep learning has revolutionized the processing of "primitive" data structures by embedding domain-specific symmetries directly into network architectures. Convolutional Neural Networks (CNNs) exploit translation equivariance on grids, while DeepSets utilize permutation equivariance for unordered sets. However, real-world data is rarely primitive; it is often hierarchical. A text document is a sequence of sentences, which are sequences of words. A 3D point cloud can be represented as a grid of voxels, each containing a set of points.

Standard methods for combining group symmetries, such as the direct product, assume that all sub-structures transform in unison. This fails to capture the "independence" inherent in nested structures—for instance, words in one sentence shifting independently of words in another. This paper introduces a formal framework for designing neural networks equivariant to these hierarchical symmetries using the mathematical concept of the wreath product.

Modeling Hierarchy with the Wreath Product

To model hierarchical symmetries, the authors employ the wreath product ($K \wr H$). This group construction describes a symmetry where:

  1. Inner Symmetry ($K$): Each "leaf" or sub-structure can transform independently (e.g., points within a specific voxel can be permuted).
  2. Outer Symmetry ($H$): The higher-level structure transforms by permuting or shifting the sub-structures themselves (e.g., the voxels themselves are translated across a grid).
Hierarchical structure of nested symmetries represented by the wreath product.

As shown in Figure 1, this creates a tree-like symmetry structure where transformations at the top level ($h \in \mathcal{H}$) affect the arrangement of blocks, while lower-level transformations ($k_i \in \mathcal{K}$) act locally within those blocks.

The Equivariant Map Recipe

The core theoretical contribution of this work is Theorem 4.1, which proves that any linear map equivariant to a wreath product can be decomposed into two distinct, intuitive components:

  • The Local Part: Apply an equivariant map for the inner structure ($K$) to each sub-structure independently. This processes local details without regard for the global arrangement.
  • The Global Part: Pool information from all inner structures to create a high-level representation, apply an equivariant map for the outer structure ($H$), and then broadcast the result back to the individual leaves.

This "pool-apply-broadcast" architecture ensures that information flows across the hierarchy while maintaining the necessary symmetry constraints.

Inductive Bias and Efficiency

By moving from direct products to wreath products, the model gains a stronger inductive bias. The wreath product covers a much larger set of potential transformations, providing the model with a more precise "hint" about the data's underlying structure. This leads to significantly better sample efficiency.

Visualizing the difference between direct products and wreath products across different group symmetries.

Furthermore, the wreath product approach is highly parameter-efficient. In a direct product model, the number of parameters typically grows with the product of the building blocks' parameters. In contrast, the wreath product model's parameters grow with the sum, resulting in leaner, faster-to-train architectures.

Application: Wreath Product Net for 3D Point Clouds

The authors implemented this theory in the Wreath Product Net (WPN) for 3D point cloud segmentation. By voxelizing the point cloud, they created a hierarchy: a 3D grid (translation symmetry) of sets (permutation symmetry).

Key Results

The WPN achieved state-of-the-art results on major benchmarks:

  • Semantic3D: Reached a mean Intersection over Union (mIoU) of 77.4%.
  • S3DIS: Achieved 80.1% mIoU, vastly outperforming previous methods like SPG (62.1%) and PointNet++ (54.5%).
  • Computational Efficiency: On Semantic3D, WPN required only 4.39 hours of pre-processing, compared to 17.43 hours for SPG, demonstrating that theoretical rigor does not have to come at the cost of speed.

Conclusion

This work provides the first formal framework for hierarchical equivariance in deep learning. By leveraging the wreath product, the authors have created a principled way to build networks for complex, nested data structures. While currently focused on grids and sets, the underlying theory is general enough to extend to more complex hierarchies, such as graphs of graphs, in future research.

Summary updated

Abstract

While using invariant and equivariant maps, it is possible to apply deep learning to a range of primitive data structures, a formalism for dealing with hierarchy is lacking. This is a significant issue because many practical structures are hierarchies of simple building blocks; some examples include sequences of sets, graphs of graphs, or multiresolution images. Observing that the symmetry of a hierarchical structure is the "wreath product" of symmetries of the building blocks, we express the equivariant map for the hierarchy using an intuitive combination of the equivariant linear layers of the building blocks. More generally, we show that any equivariant map for the hierarchy has this form. To demonstrate the effectiveness of this approach to model design, we consider its application in the semantic segmentation of point-cloud data. By voxelizing the point cloud, we impose a hierarchy of translation and permutation symmetries on the data and report state-of-the-art on Semantic3D, S3DIS, and vKITTI, that include some of the largest real-world point-cloud benchmarks.
BibTeX
@inproceedings{wang2020equivariant,
  author = {Renhao Wang and Marjan Albooyeh and Siamak Ravanbakhsh},
  title = {{Equivariant Maps for Hierarchical Structures}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2020},
  url = {https://openreview.net/forum?id=SOPeAAu0VMX},
}
Figure