Differentiable Mathematical Programming for Object-Centric Representation Learning

Adeel Pervez, Phillip Lippe, Efstratios Gavves

Object-centric representation learning aims to break down a scene into its constituent parts, allowing models to understand images as collections of distinct objects rather than just grids of pixels. Many state-of-the-art methods, such as Slot Attention, treat image features as a "bag of words." They use iterative attention to group features into "slots," but in doing so, they often ignore the spatial topology of the image—the fundamental prior that pixels belonging to the same object are usually close together.

While combinatorial optimization problems like "graph cuts" are perfect for partitioning spatial data, they are traditionally non-differentiable and computationally expensive to solve within a neural network's training loop. This paper introduces a "topology-aware" approach that bridges this gap, formulating feature partitioning as a differentiable minimum $s-t$ graph cut problem.

A Differentiable Mathematical Programming Layer

To incorporate spatial priors, the authors propose replacing standard attention mechanisms with a differentiable mathematical programming layer.

Architecture of the k-partition module

The approach relies on several key innovations:

  1. Topology-Aware Partitioning: The image is represented as a grid graph where vertices are pixels and edges represent neighborhood relationships. Partitioning the image into $k$ objects is formulated as solving $k$ parallel minimum $s-t$ cuts.
  2. Differentiable Relaxation: Because the standard min-cut (a Linear Program) is not continuously differentiable, the authors relax it into a regularized, equality-constrained Quadratic Program (QP).
  3. The Efficiency Trick: General QP solvers are notoriously slow. However, while the weights of the graph change (predicted by a CNN), the structure of the image grid remains constant. By pre-computing Cholesky factorizations of the KKT (Karush-Kuhn-Tucker) optimality matrices, the model can solve the optimization and compute its gradients using fast forward and backward substitutions.
  4. Sparse Operations: To handle the massive number of variables in standard image resolutions, the method utilizes sparse matrix computations, drastically reducing complexity.
  5. Object Matching in Video: The framework is also extended to video by formulating object permanence as a bipartite matching problem, which is similarly solved via a differentiable QP.

Key Results: Conquering Textures and Camouflage

The model was evaluated across several benchmarks, ranging from simple geometric shapes (CLEVR) to highly complex environments (ClevrTex, CAMO, and MOVi-A).

By explicitly encoding that neighboring pixels are likely to belong to the same object, the model becomes significantly more robust to "distractor" textures that typically confuse standard attention-based models.

Quantitative results comparing the proposed method against baselines
  • Superiority on Textures: On the challenging ClevrTex dataset, which features complex textures on both objects and backgrounds, the proposed method achieved a 42.4 mIoU, nearly doubling the performance of Slot Attention (22.58 mIoU).
  • Breaking Camouflage: On the CAMO dataset, where object and background textures are nearly identical, the model reached 38.9 mIoU. The best pixel-space baseline struggled at 19.83 mIoU, highlighting the power of the min-cut's edge-weight logic in finding boundaries even when colors match.
  • Video Tracking: In the MOVi-A tracking task, the model achieved a foreground ARI (ARI-FG) of 65.6%, compared to a meager 4.2% for Slot Attention, proving that the differentiable bipartite matching effectively learns object permanence.

Insights and Future Directions

This work demonstrates that we don't need to rely on slow, "black box" solvers to integrate discrete optimization into deep learning. By carefully choosing the mathematical form (equality-constrained QP) and exploiting the fixed topology of image graphs, we can derive analytical gradients that are both exact and fast.

While the method is highly effective, it does have limitations. Like many slot-based methods, it requires the number of partitions ($k$) to be specified upfront. Additionally, despite sparse matrix optimizations, the KKT matrix for very high-resolution images (e.g., 512x512) remains massive, suggesting that future work may need to explore multi-scale or patch-based approaches to scale further. Finally, moving from the current "soft" assignment matching algorithm toward more exact, yet still differentiable, matching solutions remains a promising next step.

Summary updated

Abstract

We propose topology-aware feature partitioning into $k$ disjoint partitions for given scene features as a method for object-centric representation learning. To this end, we propose to use minimum $s$-$t$ graph cuts as a partitioning method which is represented as a linear program. The method is topologically aware since it explicitly encodes neighborhood relationships in the image graph. To solve the graph cuts our solution relies on an efficient, scalable, and differentiable quadratic programming approximation. Optimizations specific to cut problems allow us to solve the quadratic programs and compute their gradients significantly more efficiently compared with the general quadratic programming approach. Our results show that our approach is scalable and outperforms existing methods on object discovery tasks with textured scenes and objects.
BibTeX
@inproceedings{pervez2023differentiable,
  author = {Adeel Pervez and Phillip Lippe and Efstratios Gavves},
  title = {{Differentiable Mathematical Programming for Object-Centric Representation Learning}},
  booktitle = {International Conference on Learning Representations},
  year = {2023},
  url = {https://openreview.net/forum?id=1J-ZTr7aypY},
}
Figure