Deep Learning with Sets and Point Clouds

Siamak Ravanbakhsh, Jeff Schneider, Barnabas PoczosICLR 2017 · OpenReview

TL;DR

This paper introduces a simple, computationally efficient "permutation equivariant" layer designed specifically for data structured as sets, such as 3D point clouds or groups of images. By using a clever parameter-sharing scheme, the authors enable deep networks to process unordered collections of data in linear time, achieving state-of-the-art results in 3D object classification and novel applications like set-based anomaly detection.

The Challenge of Unordered Data

Standard deep learning architectures, like Multi-Layer Perceptrons (MLPs) or Convolutional Neural Networks (CNNs), assume that input data has a fixed, meaningful order (like pixels in a grid or words in a sentence). However, many real-world data types are sets: collections where the order of elements is arbitrary.

If you have a set of 100 points representing a 3D chair, there are $100!$ (a massive number) of ways to order those points.

Point cloud representation of a 3D object

A standard MLP would treat each permutation as a completely different input, requiring an impossible amount of data to learn that they all represent the same chair. The challenge is to design neural network layers that are mathematically "indifferent" to the ordering of the input—a property known as permutation invariance (for a single output) or permutation equivariance (for an output that matches the input's structure).

The Permutation-Equivariant Layer

The core contribution is the Permutation-Equivariant Layer. The authors prove that for a standard linear layer to be equivariant (meaning if you swap two inputs, the corresponding outputs also swap), the weight matrix must follow a very specific pattern:

  1. All diagonal elements must be equal ($\lambda$).
  2. All off-diagonal elements must be equal ($\gamma$).

In practice, this means the output for any single element in a set is a combination of two things: a transformation of the element itself, and a transformation of the aggregate (sum or max) of the entire set. Mathematically, this looks like: $$f(\mathbf{x}) = \sigma(\lambda \mathbf{I}\mathbf{x} + \gamma (\mathbf{11}^T)\mathbf{x})$$

Key Features: * Linear Complexity: The operation is $O(N)$ relative to set size $N$, making it highly scalable. * Weight Sharing: Because weights are tied across the set, the model is forced to learn features that are universal to any member of the set. * Invariance via Pooling: To get a single label for a whole set (e.g., "this is a chair"), the authors simply apply a commutative pooling operation (like max or sum) over the equivariant features.

Datasets and Applications

The authors evaluated their method across four diverse tasks:

  1. MNIST Summation: A toy task where the model must sum the values of $N$ handwritten digits without knowing the individual labels.
  2. ModelNet40: A benchmark for 3D object classification. Objects are represented as point clouds (sets of $x, y, z$ coordinates).
  3. CelebA: Used for a "set-outlier" task. The model is given a set of 16 faces where 15 share two attributes (e.g., "brown hair" and "smiling") and one does not.
  4. redMaPPer Galaxy Catalog: A real-world cosmology dataset used to estimate the "red-shift" (distance/age) of galaxies by looking at them within the context of their galaxy clusters.

Key Insights and Results

  • MNIST Summation Success: The set-layer architecture drastically outperformed baseline methods (like concatenating or stacking the images) when predicting the sum of multiple MNIST digits, demonstrating its ability to learn permutation-invariant representations effectively.
Validation accuracy for predicting the sum of MNIST digits from sets of images
  • 3D Classification: On ModelNet40, the "set-layer" achieved 90% accuracy using 5,000 points. This was highly competitive with (and often better than) contemporary methods that used much more complex voxel-based or multi-view representations.
  • Anomaly Detection: The model successfully identified the "odd-one-out" face in the CelebA dataset in 75% of test cases, a task that is surprisingly difficult for humans. A standard non-equivariant baseline performed no better than random guessing (~6%).
  • Cosmology: By treating galaxy clusters as sets, the model reduced the error (scatter) in galaxy red-shift estimates from .025 to .023, demonstrating that set-based context provides a measurable boost over treating galaxies as independent points.
  • Context Matters: In semi-supervised tasks (like red-shift estimation), an individual's label can be predicted more accurately if the model "sees" the rest of the set. The equivariant layer naturally captures this "context" by allowing each element to see the set-wide aggregate.
  • Max vs. Sum: While the theory works for summation, the authors found that using the max of the set as the global context often performed better in practice, likely because it acts as a form of normalization.
  • Simultaneous Dropout: When regularizing these layers, the authors found it's better to drop out the same feature channels for all members of a set simultaneously. Otherwise, the network simply learns to "borrow" the missing information from other set members.

Limitations and Future Work

  • Graph Comparison: While the set-layer is faster than Graph Convolutional Networks (GCNs), the authors noted that GCNs might capture more intricate local structures if a meaningful graph can be constructed.
  • Distribution Regression: The authors suggest this work is a step toward "distribution regression," where the goal is to map a sample of points to a property of the underlying distribution they were drawn from.
  • Architecture Depth: The paper primarily focuses on the layer itself; further exploration into very deep "set-resnets" or similar architectures was left for future investigation.

Summary updated

Abstract

We introduce a simple permutation equivariant layer for deep learning with set structure. This type of layer, obtained by parameter-sharing, has a simple implementation and linear-time complexity in the size of each set. We use deep permutation-invariant networks to perform point-could classification and MNIST digit summation, where in both cases the output is invariant to permutations of the input. In a semi-supervised setting, where the goal is make predictions for each instance within a set, we demonstrate the usefulness of this type of layer in set-outlier detection as well as semi-supervised learning with clustering side-information.
BibTeX
@inproceedings{ravanbakhsh2017deep,
  author = {Siamak Ravanbakhsh and Jeff Schneider and Barnabas Poczos},
  title = {{Deep Learning with Sets and Point Clouds}},
  booktitle = {International Conference on Learning Representations},
  year = {2017},
  url = {https://openreview.net/forum?id=HJF3iD9xe},
}
Figure