Better Set Representations For Relational Reasoning

Qian Huang, Horace He, Abhay Singh, Yan Zhang, Ser-Nam Lim, Austin R. BensonNeurIPS 2020 · OpenReview

TL;DR

Standard neural networks struggle with relational reasoning because they cannot easily map unstructured data (like images) into clean sets of distinct objects. This paper introduces the Set Refiner Network (SRN), a module that uses iterative inference to "search" for the best set representation, leading to superior object decomposition and a massive boost in model robustness.

What Problem Does This Paper Address?

Relational reasoning—the ability to understand how different entities relate to one another (e.g., "the red ball is to the left of the blue cube")—is a hallmark of advanced intelligence. To perform this kind of reasoning, a model must first extract a set of entities from raw, unstructured data.

However, there is a mathematical catch: the responsibility problem. The authors prove that any function mapping an input to a list of distinct entities must be discontinuous. Because standard deep learning models are built from continuous functions, they struggle to make the "jumps" required to assign specific objects to specific latent slots. Instead of a clean set where one slot equals one object, standard models often "smear" objects across multiple slots or hallucinate extra entities. This lack of proper decomposition makes downstream reasoning fragile and inaccurate.

Comparison of continuous set extraction vs. the Set Refiner Network (SRN).

Methods: The Set Refiner Network (SRN)

The authors propose the Set Refiner Network (SRN) to bypass the limitations of continuous feedforward mapping.

Instead of relying on a single forward pass to generate a set, the SRN uses iterative inference:

  1. Embedding: The model first generates a global latent embedding of the input.
  2. Initial Guess: It starts with an initial "noisy" set of entities.
  3. Refinement Loop: It uses a permutation-invariant encoder to map the current set back into the embedding space. It then calculates the error between this set-embedding and the original target embedding.
  4. Gradient Descent: The model performs several steps of gradient descent on the set itself to minimize that error.

By "searching" for a set that matches the input embedding through an optimization loop, the model can effectively model the discontinuous jumps needed to separate objects properly.

Datasets

The researchers evaluated the SRN across four diverse domains:

  • Circles Dataset: A synthetic dataset of 64x64 images containing 0-10 colored circles, used to test unsupervised object decomposition.
  • Sort-of-CLEVR: A visual question-answering benchmark involving 2D shapes and questions about proximity ("Furthest"), distance ("Closest"), and quantity ("Count").
  • Atari (Pong & Space Invaders): Used within the Contrastive Structured World Model (C-SWM) framework to predict state transitions in reinforcement learning.
  • CLUTRR: A natural language reasoning task where the model must infer kinship relationships from short stories.

Key Insights and Ideas

  • Discontinuity is Necessary: The paper provides a formal proof that the "responsibility problem" isn't just a training difficulty—it's a fundamental mathematical limitation of continuous neural networks when dealing with sets.
  • Decomposition without Supervision: One of the most impressive findings is that the SRN learns to decompose images into individual objects without being given ground-truth object masks or labels. The pressure to represent the input as a set of identical slots naturally forces the model to assign one object to one slot.
  • Robustness is the Real Prize: While accuracy improves, the gain in robustness is staggering. Standard models often "overfit" to the specific positions of objects. Because SRN enforces a true set structure, it is far less likely to break when objects are rotated or translated in ways the model hasn't seen before.

Key Results

  • Extreme Robustness: In a synthetic robustness test involving rotating and translating shapes, the baseline model's accuracy plummeted to 1.5%, while the SRN-augmented model maintained 96.7% accuracy.
  • Sort-of-CLEVR: Adding the SRN to a standard Relational Network (RN) reduced the relative error by over 50% on the "Furthest" object task, which requires the most global reasoning.
  • Object Decomposition: On the Circles dataset, the SRN successfully decomposed objects in 65-95% of images. In contrast, the baseline method failed almost entirely as the number of circles increased, dropping to less than 2% success.
Unsupervised object decomposition on the Circles dataset.
  • World Modeling: In the "Space Invaders" environment, which contains many identical moving objects, the SRN significantly improved the model's ability to track state transitions over multiple steps.

Limitations and Future Work

  • Computational Overhead: Because the SRN requires an internal optimization loop (multiple steps of gradient descent) during every forward pass, it is computationally more expensive than a standard feedforward network.
  • Graph Complexity: The authors experimented with a Graph Refiner Network (GRN) for relational data but found it much harder to train and less effective than the set-based version. Improving the stability of the GRN is a noted area for future research.
  • Scaling to Real-World Images: While the results on synthetic data (CLEVR, Atari) are strong, the "objects" are still relatively simple shapes. Testing the SRN on complex, high-resolution natural images remains a significant next step.

Summary updated

Abstract

Incorporating relational reasoning into neural networks has greatly expanded their capabilities and scope. One defining trait of relational reasoning is that it operates on a set of entities, as opposed to standard vector representations. Existing end-to-end approaches for relational reasoning typically extract entities from inputs by directly interpreting the latent feature representations as a set. We show that these approaches do not respect set permutational invariance and thus have fundamental representational limitations. To resolve this limitation, we propose a simple and general network module called Set Refiner Network (SRN). We first use synthetic image experiments to demonstrate how our approach effectively decomposes objects without explicit supervision. Then, we insert our module into existing relational reasoning models and show that respecting set invariance leads to substantial gains in prediction performance and robustness on several relational reasoning tasks. Code can be found at github.com/CUAI/BetterSetRepresentations.
BibTeX
@inproceedings{huang2020better,
  author = {Qian Huang and Horace He and Abhay Singh and Yan Zhang and Ser-Nam Lim and Austin R. Benson},
  title = {{Better Set Representations For Relational Reasoning}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2020},
  url = {https://openreview.net/forum?id=qPqhE3J5Ac},
}
Figure