Equivariant Networks for Hierarchical Structures

Renhao Wang, Marjan Albooyeh, Siamak Ravanbakhsh

Overview

Deep learning has achieved massive success by baking "inductive biases" into model architectures—most notably through equivariance. For example, a Convolutional Neural Network (CNN) is equivariant to translation: if you shift an image, the feature map shifts accordingly. Similar equivariant building blocks exist for sets, graphs, and sequences.

However, this paper addresses a critical gap: many real-world data structures are hierarchical. Think of a document as a sequence of sentences, where each sentence is a sequence of words. Or consider a point cloud voxelized into a 3D grid, where each voxel contains a set of points. This paper introduces a formal framework for building neural networks that are equivariant to these hierarchical symmetries using the mathematical concept of wreath products. By capturing how nested data structures transform at multiple levels, the authors derive a parameter-efficient "pool-and-broadcast" architecture that achieves state-of-the-art results in 3D semantic segmentation.

The Challenge of Hierarchical Data

Standard models often treat hierarchical data as "flat" or use a "direct product" of symmetries, assuming everything moves together. This fails to capture the independent transformations possible at different levels of the hierarchy.

Hierarchical symmetries acting on a nested tree structure.

For instance, in a nested structure, the "inner" elements (like points in a voxel) can often be permuted or transformed independently of the "outer" elements (the voxels themselves). Failing to model this independence leads to weaker inductive biases and less efficient learning.

Methods: Wreath Products and Pool-and-Broadcast

The authors propose using the wreath product ($K \wr H$) to model these hierarchical symmetries.

  • Direct vs. Wreath Products: In a direct product (like a standard 2D image), all rows must translate together. In a wreath product (like a sequence of sequences), each "inner" sequence can translate independently, while the "outer" sequence can also be permuted or translated.
Matrix visualizations comparing direct products and wreath products for different symmetry groups.
  • The Equivariant Map: The paper derives a closed-form linear map that is equivariant to this wreath product. They show that any such map can be decomposed into a simple, intuitive recipe:
  • Pool: Aggregate information from the inner structures (e.g., mean-pooling points in a voxel).
  • Outer Map: Apply an equivariant map to the pooled "coarse" structure.
  • Broadcast: Distribute the coarse information back to the individual elements.
  • Inner Map: Simultaneously apply an equivariant map to each inner structure independently.
  • Combine: Sum these contributions.

This "pool-and-broadcast" pattern is common in computer vision (e.g., U-Nets or Feature Pyramid Networks), but this paper provides a rigorous group-theoretic justification for why this structure is mathematically optimal for hierarchical data.

Key Insights

  • Stronger Inductive Bias: By using wreath products instead of direct products, the model accounts for a much larger set of possible transformations. This forces the network to learn features that are robust to independent local changes, leading to better generalization.
  • Parameter Efficiency: In a direct product model, the number of independent parameters grows multiplicatively with the complexity of the building blocks. In the wreath product model, it grows linearly (the sum of the parameters of the inner and outer maps).

Experimental Results

The model, dubbed the Wreath Product Net, was applied to 3D point cloud segmentation by voxelizing the space. This imposes a hierarchy of translation symmetry (across voxels) and permutation symmetry (within each voxel). It was evaluated on three major point-cloud benchmarks:

  1. Semantic3D: A massive outdoor LiDAR dataset with over 4 billion points. The model achieved 95.2% Overall Accuracy (OA) and 77.4% mIoU, outperforming previous models like ConvPoint and SPG.
  2. S3DIS (Stanford Large-Scale 3D Indoor Spaces): Reached 95.8% OA and 80.1% mIoU.
  3. vKITTI (Virtual KITTI): Reached 90.7% OA and 69.5% mIoU.

Furthermore, the model proved significantly faster to pre-process and train than many competitors. For example, its pre-processing for Semantic-8 took roughly 4.4 hours compared to 17.4 hours for SPG.

Limitations and Future Work

While highly effective, the approach has a few limitations. First, performance is sensitive to the choice of voxel resolution: if the resolution is too high, the model begins to overfit; if too low, it loses fine-grained detail. Second, the current derivation assumes a regular grid for the "outer" structure (voxels). Extending this to irregular hierarchies, such as graphs of graphs, is a natural next step. Finally, the core theory focuses on linear equivariant maps. While the authors use ReLUs and attention to add non-linearity, a deeper exploration of non-linear hierarchical equivariance could yield even more powerful models.

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 Networks for Hierarchical Structures}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2020},
  url = {https://openreview.net/forum?id=SOPeAAu0VMX},
}
Figure