Differentiable Mathematical Programming for Object-Centric Representation Learning
Authors: Adeel Pervez
Phillip Lippe
Efstratios Gavves
Venue: ICLR 2023 poster (2023)

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.

Published as a conference paper at ICLR 2023
DIFFERENTIABLE MATHEMATICAL PROGRAMMING FOR OBIECT-CENTRIE REPRESENTATION LEARNING
Adeel Pervez QUVA Lab,
Phillip Lippe QUVA Lab, Informatics Institute
Efstratios Gavves QUVA Lab, Informatics Institute University of Amsterdam e -ggavvesevvv
Informatics Institute University of Amsterdam a a.a. w.a.pervvezuva...o
University of Amsterdam p 1 p.lippe@uva.nl
ABSTRACT
We propose topology-aware feature partitioning into disjoint partitions for given scene features as a method for object-centee centric representation learning. To this end, we propose to use minimum s-t graph cuts as 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 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
INTRODUCTION
Object-centric representation learning aims to learn representations of individual objects in scenes given as static images or video. Object-centric representations can potentially generalize across range of computer vision tasks by embracing the compositionality inherent in visual scenes arising from the interaction of mostly independent entites. (Burgess al.) 2019 Locatello et al., 2020) Elsayed et al., 2022). One way to formalize object-centric representation learning is consider it as an input partitioning problem. Here we are given set of spatial scene features, and we want to partition the given features into k per-object features, or slots, for some given number of objects k. A useful requirement for a partitioning scheme that it should be topology-aware. For example, the partitioning scheme should be aware that points close together in space often related and may form part of the same object. A related problem is to match object representations in two closely related scenes, such as frames in video, to learn object permanence across space and time.
In this paper we focus on differentiable solutions for the partitioning and matching problems that also efficient and scalable for object-centric learning. We formulate the topology-aware k-part partitioning problem as the problem of solving k minimum s-t cuts in the image graph (see Figure] and the problem of matching as bipartite matching problem.
An interesting feature of the minimum s-t cut and bipartite matching problems is that they can both be formulated as linear programs. We can include such programs as layers in a neural network by parameterizing the coefficients of the objective function of the linear program with neural networks. However, linear programs by themselves are not continuously differentiable with respect to the objective function coefficients (Wilder et al. 2019). A greater problem is that batch solution of linear programs using existing solvers too inefficient for neural network models, especially when the programs have a large number of variables and constraints. We solve these problems by I) approximating linear programs by regularized equality constrained quadratic programs, and 2) pre- computing the optimality condition (KKT matrix) factorizations so that optimality equations can be quickly solved during training.
The advantage of using equality constrained quadratic programs is that they can be solved simply from the optimality conditions. Combined with the appropriate precomputed factorizations for the task of object-centric learning, the optimality conditions can be solved very efficiently during training.

---

Published as a conference paper at ICLR 2023
Algorithm 1 Feature k-Part Partitioning
Require:
Input features of dimension H W with channels, height И and width W
1: Compute quadratic program parameters y; = fz(r), for i E {l,...k k} where fy are CNNs.
2: Optionally transform spatial features f = (x)), where fz is an MLP transform acting on the channel dimension. z has dimension D H W.
3: Solve regularized quadratic programs for minimum s-1 cut and extract vertex variables qsolve(1)) for each y/- Each 2, has dimension
x W.
4: Normalize across cuts i = 1.... k for each pixel with temperature-scakee softmax.
5: Multiply 2; with z along H, W for each to obtain masked features maps ri.
6: Return as the k-partition.
A second advantage of using quadratic programming approximations is that quadratic programs can be differentiated relative to program parameters using the implicit function theorem as shown in prior literature (Barratt 20188 Amos and Kolter 2017).
To learn the objective coefficients of the cut problem by a neural network, the linear program needs to be solved differentiably, like hidden layer. For this, we relax the linear program to quadratic program and employ techniques from differentiable mathematical programming (Wilder et al. 2019 Barratt 2018) to obtain gradients. This amounts to solving the KKT optimality conditions which then result in the gradients relative to the parameters of the quadratic program (Amos and Kolter 2017 Barrati 2018). However, with a naive relaxation, the required computations for both the forward and backward pass are still too expensive for use in object-centric representation learning applications.
Given that the techniques generally employed for differentiably solving quadratic programs are limited to smaller program sizes (Amos and Kolter 2017). we introduce optimizations in the gradient computation specific the problem of solving graph cuts for image data. For instance, we note that the underlying s-t flow graph remains unchanged across equally-sizee images, allowing us pre-compute large matrix factorization. Furthermore, we replace the forward pass by a regularized equality constrained quadratic program constructed from the linear programming formulation of the minimum s-l cut problem. When combined with these task specific optimizations, equality constrained quadratic programs can be solved significantly more efficiently than general quadratic programs with mixed cquality and inequality constraints (Wright and Nocedal 1999). The regularization of slack variables ensures that the output of the new quadratic program still be interpreted as s-f cut solution. The use of sparse matrix computations the forward and backward passes ensures that time and memory usage is significantly reduced.
To summarize, we make the following contributions in this paper.
We formulate object-centric representation learning in terms of partitioning and matching.
2. We propose s-t cuts in graphs for topology-awar partitioning with neural networks.
3. We propose to use regularized equality constrained quadratic programs as a differentiable, general, efficient and scalable scheme for solving partitioning and matching problems with neural networks.
2 MINIMUM s-t CUTS FOR TOPOLOGY-AWARS PARTITIONING
We first describe the general formulations of the graph partitioning problem specialized for images and then describe limitations when considering graph partitioning in image settings. With these limitations in mind, we describe the proposed neural s-t cul and matching algorithms, which allow for efficient and scalable solving of graph partitioning and matching. Last, we describe how to learn end-to-end object-centric representations for static and moving objects with the proposed methods.
2.1 MINIMUM s-t GRAPH CUTS
The problem of finding minimum s-t cuts in graphs is well-known combinatorial optimization problem closely related to the max-flow problem (Kleinberg and Tardos (005).. We are given a directed graph G (V, F) with weights for edge vw,v) denoted by Wu,e and two special vertices
2

---

Published as a conference paper at ICLR 2023
and t. The minimum s-t cut problem is to find partition of the vertex set V into subsets V1 and V2, V1 i = 0. such that E V1, E V22 and the sum of the weights of the edges going across the partition from Ví to V2 is minimized. In classical computer vision. the minimum cut problem has been used extensively for image segmentation (Boykov and Jolly) 2001 [Shi and Malik 2000). The problem of image segmentation into foreground and background can be reduced to minimum s-t by representing the image as a weighted grid graph with the vertices representing pixels (Figure where the weights on the edges represent the similarity of neighbouring pixels. Next, the vertices and i' are introduced and for each pixel vertex we include edges (s, v) and t). The weights on edges Wa,v, W1, represent the relative background and foreground weight respectively for the pixel vertex v. For example, Wx,r > Wt.- may indicate that is more likely to be in the foreground rather than the background. At the same time, the neighbouring edge weights Wa,r indicate that similar pixels should go in the same partition. Solving the min-cut problem on this graph leads to segmentation of the image into foreground and background. Note that this procedure encodes the underlying image topology in the graph structure.
Solving Cut Problems. Given a directed graph G = (V, E) with edge weights w and two special vertices and f, problem as a linear program (Dantzig and Fulkerson 1955). To do so, we introduce variable Pu for each vertex in the linear program. Similarly, for each edge (u, u), we introduce a variable denoted du,v- The edge weights Wa,v act as objective function parameters the linear program.
formulate the min-cut
minimize
Σ Wen
subject to
dur 2 Pu Pa
(u,v) E.
(1)
Ds Pt 2 1,
du, 20 0
(u, E E, u uEV
Pe 2 0
The program can then be fed to linear programming solver for the solution. Although there are other more efficient methods of solving min-cut problems, resort to the linear programming formulation because of its flexibility and that it can be approximated with differentiable proxies.
2.2 TOPOLOGY-AWARE PARTITIONING WITH GRAPH CUTS
Figure 1: (Top) Im- age graph for 2- partition with an s-t cut and 3 parallel graphs for 3-partition (Below).
We propose finding minimum s-t cuts in the image graph with weights param- eterized by neural networks, Wa, = f(x) with image x, for partitioning im- age feature maps, x' g(x), into & disjoint partitions. Solving the standard minimum s-t cut problem can divide the vertex set of an input graph into two partitions. We generalize the minimum s-t cut problem graph into any fixed k number of partitions by solving k parallel min-cut prob- lems and subsequently normalizing the vertex (or edge) variables sum to across the k copies of the graph. We note that 2-partition can also be formulated as a subset selection problem (Xie and Ermon 2019). The advantage of using minimum cuts for partitioning is that the method then depends on the underlying topology and neighbourhood relations of image data represented in the image graph.
partition a given
Partitioning Generalization. We generalize the minimum s-t cut method for 2-partition to partitions by solving & parallel 2- 2-partition problems and normalizing the vertex variables pi,. i denoting partition index. from the optimum solution of equation [ with softmax over é. We also experimented with solving the k-part partitioning problem with a single graph cut formulation. However, we found such formulation to have high memory usage with increasing k and limited ourselves to the parallel cut formulation which worked well for our experiments.
Obstacles. There are some obstacles in the way of including linear programs as hidden layers neural networks in way that scales to solving large computer vision problems. The first of these is that linear programs are not continuously differentiable with respect to their parameters. One solution to this is to use the quadratic programming relaxation suggested by Wilder et al. (2019). However, the gradient computation for general large quadratic programs requires performing large matrix factorization which is infeasible in terms of computing time and memory when working with image-scale data.
3

---

Published as a conference paper at ICLR 2023
A second obstacle is that established quadratic programming solvers such OSQP (Stellato et al.) 2020) and Gurobi (Gurobi Optimization, LLC| (202) run on CPU and cannot solve programs in large batches essential for fast neural network optimization. There have been attempts to solve general quadratic programs with GPU acceleration (Amos and Kolter 2017). However, in practice, these attempts do not scale well to quadratic program solving in batch setrings with the tens of thousands of variables and constraints that arise when working with image data.
3 DIFFERENTIABLE MATHEMATICAL PROGRAMMING FOR NEURAL s-t CUT
We describe our proposed method and optimizations to differentiably solve approximations of the s-t cut problems as quadratic programs. Our method depends the fact that 1) quadratic program solutions, unlike linear programs, can be differentiated relative to the objective function parameters (Amos and Kolter 2017 Wilder et al.) (2019) and 2) that quadratic programs with equality constraints only can be solved significantly more quickly than general quadratic programs (Wright and Nocedal 1999). Combining the method with specific optimizations allows to solve large batches of quadratic programs on GPU allowing us to scale to image data.
3.1 REGULARIZED EQUALITY CONSTRAINED QUADRATIC PROGRAMS
We use the fact that quadratic programs with equality constraints only can solved much more quickly and easily than programs with mixed equality and inequality constraints. Given an equality constrained quadratic programming, we can directly solve it by computing the KKT matrix factoriza- tion and solving the resulting triangular system (Wright and Nocedal 1999).
In general, linear or quadratic programs (such as those for s-t cut) have non-negativity constraints for variables which cannot be represented in equality constrained quadratic programs. Instead, regularization terms in the objective function which ensure that variables remain within a reasonable range. After solving the regularized equality constrained program, the solutions be transformed, for example by sigmoid or softmax, to bring them within the required range.
We approximate the minimum s-t cut linear program (equation with equality constraints only.
by the following quadratic program
minimize
Σ Wootthr + E(P + +rae)) + Σ
P
2
subject to
duy Two Pu
Pe (u, E,
Tat 1,
where the variables Far are slack variables and 7 is regularization coefficient. We achieve this by first adding one slack variable Tav per inequality constraint to convert them into equality constraints plus any non-negativity constraints. Next, add diagonal quadratic regularization term for all variables, including slack variables in the objective function. Finally, we remove any non-negativity constraints obtain a quadratic program with equality constraints only.
Parameterization. Given input features x, we can include regularized equality constrained programs for s-t cut in neural networks by parameterizing the edge weights Wayv by ConvNet f as = fxx). Assuming the image graph in Figure [ has height H and width W. we can parameterize the weights for the partition by using a ConvNet f with output dimensions (6k, H, W) giving the weights for edges (4 neighbor edges and and i edges) per pixel per partition. Our experiments show that the output of the regularized equality-constranne quadratic program for minimum s-f. cut can easily be interpreted cut after a softmax and works well for image-scale data.
Forward and backward pass computations. We now describe the computations required for solving regularized equality constrained quadratic programs and their gradients relative to the objective function parameters. A general equality constrained quadratic program has the following form.
minimize
5z + z'c
(3)
subject to A= =b b,
where E [Rx=
x is the constraint matrix with constraints, b E R,, G E Rax= and c E R", For case of quadratic program proxies for linear programs, G is multiple of identity, G =
4

---

Published as a conference paper at ICLR 2023
and corresponds to the regularization term. For particular applications, is the only learnable parameter and A and b are fixed and encode the image graph constraints converted to equality constraints by use of slack variables. Any non-negativity constraints are removed.
minimize
Σ Cunduv
MLP
subject to
Pa + du 1, Pv + du [, E, du 2 20 (u, E
(4)
Feeture map
Paramo
QP Selver
Parttioning
Partifioned
k-partition
Figure 2: Linear program for matching
Figure Schematic of partitioning module
The quadratic program can be solved directly by solving the following KKT optimality conditions for some dual vector À (Wright and Nocedal
1999).
G
A' 0
[-]
A
where the matrix on the left the KKT matrix. We can write the inverse the KKT matrix using Gaussian elimination (the Schur complement method, (Wright and Nocedal 1999)), with G 71, as
11
A'
C
E F
A
E
where C = 4 7 (AA*)-1 appears in inverted form in equation @ which does not change and can be pre-computed. We can pre-compute once using a Cholesky factorization to factor A as AA LL' in terms of a triangular factor L. Then during training whenever need to solve the KKT system by computing C'2' or Ez' (equation 6) for some z', we can do this efficiently by using forward and backward substitution with the triangular factor L.
- A E = A'(AA")-1 and F -AAAA---- We note that only
Once we have the KKT matrix factorization equation 6 we can reuse it for the gradient computation. The gradient relative to parameters is obtained by computing Vel(c) -V where I(.) is loss function and is solution of the quadratic program (see Amos and Kolter (2017) for details). can reuse the Cholesky factor for the gradient making the gradient computation very efficient.
Sparse Matrices. The final difficulty is that the constraint matrix A can be very large for object-centric applications since the image graph scales quadratically with the image resolution. For 64x64 images we get s-t cut quadratic programs with over 52,000 variables and over 23,000 constraints (resulting in a constraint matrix of size over 4GB) which have to solved in batch for each training example. Since the constraints matrices are highly sparse (about 6% non-zero elements for 64x64 images) we use sparse matrices and a sparse Cholesky factorization (Chen et al. 2008). During training we use batched sparse triangular solves for the backward and forward substitution solve batch of quadratic programs with different right hand sides in equation Assuming a graph size of N, solving the quadratic program directly (with dense Cholesky factorization) has complexity about O(N)) and is even greater for general quadratic programs. With our optimizations this reduces to O(N))). where ny is the number of nonzero elements, which is the time required for a sparse triangular solve.
3.2 EXTENSION TO MATCHING
We can extend the regularized quadratic programming framework to the problem of matching. Given two sets of k-part partitions P1 and Pz we want to be able to match partitions in P1 and Pg. We can treat this bipartite matching problem which can be specified using linear program 4 We denote nodes variables as Pu. for node u, edge variables for edge {u, } as d and the edge cost as Cu,.-
Unlike the s-t cut problems, the matching problems that we use in this paper quite small with the bipartite graph containing no more than 2 x 12 = 24 nodes. For such small problems one could conceivably employ (after suitable relaxation (Wilder et al.] (019)) one of the CaU-based solvers or the parallel batched solution proposed by Amos and Kolter (2017). However, in this paper, we use the same scheme of approximating the regularized equality constrained quadratic programs that
5

---

Published as a conference paper at ICLR 2023
use for graph eut problems for the matching problem and leave the more exact solutions to further work. See Appendix C for details of the formulation of regularized quadratic programs for matching.
4 APPLICATION TO OBIECT-CENTRIC REPRESENTATION LEARNING
We now discuss how to use the specific k-part partitioning formulation described above for object- centric learning. Given scene features, z, of dimension C' x H x W as input, we transform the features into k vectors or slots where each slot corresponds to and represents specific object in the scene. The objective is that, by means of graph cuts that preserve topological properties of the pixel space, the neural network can learn to spatially group objects together in a coherent fashion, and not assign far-off regions to the same slot arbitrarily.
We use a similar encoder-decoder structure as Slot Attention (Locatello et al. 2020). Crucially, however, we replace the slot attention module by our min-cut layer. Specifically, based on scene features that are extracted by an CNN backbone, we compute k minimum s-t cut quadratic pro- gram parameters using small CNN. We solve the & quadratic programs and softmax-normalln the vertex variables. This gives us (soft) spatial masks 2; normalized across i. We multiply the masks 2; with the (optionally transformed) scene features broadcasting across the channel dimen- sion. This gives us masked features r; of dimensions D x H x W that form partition. The proce- dure is described in Algorithm To obtain slot object representations, we add position encoding to the scene features x before partitioning. After partitioning, we average each partition r; of dimension D H X W across the spatial dimensions obtain & vectors of dimension D) which are then trans- formed by MLPs to obtain the slots. Finally, each slot is separately decoded with a separate output channel to combine the individual slot images. This combined image is then trained to reconstruct the original scene We make no changes to the reconstruction loss function in (Locatello et al. 2020)
Algorithm 2 Slots Computation
Require: Input features ær of dimension C' x H x W with C' channels, height H and width W
1: Add position encoding to features
Partition using Algorithm to obtain partitions
r. of dimensions D x H W.
Average r; across H7, W.
4: Transform each r; to get 8; = f(r)) with MLP f.
S: Return slots = {81....,.8)) 8.
Background slot. The basic object-centric framework described in Algorithms D and 2 can easily be extended to work with specialized background slot. We do this by computing one set of masks for a 2-partition and one for & - 1-part partition, denoted mask_ fg, mask_ mask_objeee ject,, and multiplying the foreground and object masks mask_ fg mask ob ject. In experiments, we find that computing slots in this way specializes a slot for the background.
Matching and motion. We extend the model for learning representations of moving objects in video by combining the model with the match- ing procedure described in Algorithm 3 We work with pairs of frames. For each frame, compute k per-frame slot representations as be- fore. Next using the matching procedure we match the two sets of slots to get new slots r, as in Algorithm 3 and transform the new slots by MLP transformations. The new slot is used in the decoder to reconstruct the input pair of frames by optimizing the sum of the reconstruc- tion error for the two frames.
Algorithm 3 Matching slots for scene pairs
Require:
Input features 21, 22 of dimension C' H W with C channels, height II and width W
Compute slots S, T for 3 22 respectively using Algorithm[2]
2: Compute a cost for each pair of slots s; E S and
f E T by computing inner products as c.j - (s)
3: Solve matching using method in 3.2 to obtain
matching matrix Maj-
Apply softmax with temperature to Ma along di- mension j.
5: Compute paired slot r; = Mr.T
6: Return k slots pairs (s,,r.).
RELATED WORK
Partitioning. The problem partitioning input data frequently appears in computing tasks. One commonly used approach casts the problem as one of selecting subsets. An input x (a vector or sequence) is treated as a set where each element of the set is assigned a weight. Next, one can select elements with the largest weight using one of the available relaxation of the Top-k operator (Plötz and Roth 2018 Grover et al. 2018). If a stochastic sample is desired then the weights might be treated unnormalized probabilities and the Top-k relaxation combined with ranking distribution such as

---

Published as a conference paper at ICLR 2023
Figure 4: Unsupervised object discovery on Clevr, ClevrTex and CAMO. Columns (left to right) show original image, overall reconstruction and per-slot reconstruction for each of 12 slots.
Gumbel Softmax to obtain differentiable samples without replacement (Xie and Ermon 2019). Or one might sample elements independently and employ a regularization method such Lo regularization (Louizos et al. 2018 De Cao al., 2020) control the number selected elements. For problems involving partitions of images, the selection of a pixel makes it likely that neighboring pixels will also be chosen. Current methods often treat the problem as one of independent choice and rely learning.
Graph Cuts in Vision. Both directed and undirected version of graph cuts have been considered previously for computer vision applications including image segmentation (Boykov and Jolly 200T, Wu and Leahy] 1993 Boykov and Lunka-Leeg 2006). image restoration (Greig et al.) 1989), multi-view reconstruction (Kolmogorov and Zabih| 2001). ). For image segmentation with global cuts, normalized Shi and Malik (2000) has been popular method to prevent the method from cutting small isolated sets. The work Boykov and Jolly (200T) uses s-l cuts which the approach taken in this work.
Object-Centric Representation Learning. Currently, most works object-centric representation learning deploy a slot-based approach (Locatello et al. 2020). In this, the input is represented by a set of feature vectors, also called slots, where each slot encodes a different object. For instance, Slot Attention (Locatello et al. 2020) uses an iterative attention mechanism to encode an input image into slots. The model trained via reconstruction loss by decoding each slot is separately, and combining the image via an alpha channel afterwards. Recent works extend Slot Attention to video data (Kipf) al. 2022 Elsayed et al. 2022; Kabra al. 202T]. Another group of works slot-based object- centric representation learning explicitly split the input image into multiple parts by predicting one mask per object (Burgess al. 2019 Engelcke al. 2019) Greff et al.] [2019] Engelcke al.) 2021).
However, all previously mentioned works do not exploit the topology of the input image partition into objects. For this, [in et al. (2020); Diang and Ahn (2020); [rrwford and Pineau (2019) predict bounding- boxes to locate objects that are reconstructed on top of a background slot. Alternatively to slots, Löwe et al. y Reichert and Serre (2014) use complex-valuee activations to partition the feature space via phase (mis-)ald mhiis))aligmments and Smirnov al. 202T); Monnier et al, (2021) learn recurring sprites as object prototypes.
6 EXPERIMENTS
6.1 OBJECT DISCOVERY
Model. We use the architecture in Locatello et al. (2020) and replace the slot attention mechanism by the k-partition module with background partitioning as described in Section 4 The architecture an encoder-decoder architecture with a standard CNN (or ResNet) as the encoder and spatial broadcast decoder. We use a CNN with 64 features maps in the encoder per layer for Clevr and a ResNet with blocks with 100 features maps for ClevrTex. The feature maps downsampled in the first layer to 64x64. The decoder in both cases is the same which broadcasts each slot across an 8x8 grid and upsamples to the input dimensions. We use 3-layer convNet in the k-partition module output the
7

---

Published as a conference paper at ICLR 2023
Table 1: Object discovery performance on Clevr, ClevrTex with evaluation on OOD and CAMO
Karazija et al. 2021). Boldface indicates best metric. Underlined scores indicate second best.
Clevr
ClevrTox Textured Object-BGi
OOD (eval-enly)
CAMO (eval-ouly)
Out-of-dist, shapetexture
Camouilaged objjects
Model
mioU
ARI-PG
MSE
ARI-FG
ARI-FG
ARI-PG
Glimpse-based based Methods
SPAIR Crawforr and Pincau 2019
65.95
77.13
55
0.0
0.00
1101
0.0
0.000
1166
0.0
0.0
668
SPACE
26.31
22.75
9.14
17.53
298
6.87
12.71
387
8.6
10.55
251
GNM
Dang 3nd Alm 2020
59.92
65.05
43
42.25
53.37
383
40.84
48.43
626
17.56
15.73
353
Sprite-based Methods
MN
Smimow et al
M11
56.81
72.12
75
10.46
38.31
335
12.13
37.29
409
8.79
31,52
265
1311
Mommer ml
48.74
89.54
33.79
79.90
438
32,55
73.67
590
27.54
72,90
377
Pixe--Space Methods
Gen. V2
Engelcke et al. 102
9.48
57,90
158
7.93
31.19
315
8.74
29.04
539
7.49
29.60
278
Emani
341
19.53
315
MONet Burzess ex 2019
30.66
54.47
58
19.78
36.66
146
19.30
32.97
231
10.52
12.44
112
10DINE
Greff et 2019
45.14
93.81
44
29.16
59,52
340
26.28
$3.20
504
17.52
36.31
315
Slot Attentoo
or 2020
36.61
95.89
22.58
62.40
254
58.45
487
57.54
215
Ours
49.04
42.4
202
38.0
22.6
38.9
189
parameters of the quadratic program. The partitioning module works with 64x64-size feature maps. The image features are transformed by MLPs before applying the partitioning and again after the partition. We use a fixed softmax temperature of 0.1 for the combined slots and temperature of 0.5 for the foreground slots. We set the regularization parameter y = 0.5.
Datasets. We experiment with the Clevr (Johnson et al. 2017) and ClevrTex datasets (Karazija et al., 2021). For Clevr we use the version with segmentation masks ClevrTex is more complex version of Clevr with textured objects and background. ClevrTex also provides two evaluation sets, OOD: an out-of-distributtin dataset with textures and shapes not present in the training set and CAMO: a camouflaged version with the same texture used for the objects and background. It was shown in (Karazija al. (02T) that current methods perform poorly with the presence of textures and performance is drastically worse on the CAMO evaluation set. We crop and resize the images to 80% of the smaller dimension and taking the center crop. We then resize the images 128x128 This is the same setup as used by (Karazija et al. 2021
Metrics. For comparison of segmentation performance, the adjusted rand index with foreground pixels (ARI-FG) only has been used in prior work. It has been suggested (Karazija et al. 202 that mean intersection over union (mIoU) might be better metric since it also considers the background. Thus in this paper, we report both the foreground ARI and mIoU for the models.
Results. The results are shown in Table ! For Clevr, we find that the segmentation performance for our method exceeds all other pixel-space methods in terms of mloU. In terms of foreground ARI, our method matches the best performing model on this metric, namely Slot Attention, being only slightly worse. Finally, our method constitutes the best reconstruction performance on CLEVR. Example reconstructions from the validation set can seen Fig The figure shows that our method is able to achieve very sharp reconstructions CLEVR.
On the full ClevrTex dataset, our method outperforms all baselines in both mloU and ARI-FG, providing improvement of 12% and 18% respectively compared to the best pixel-space baseline. Furthermore, the strong reconstruction quality in terms of the background pattern in Fig rresult in low reconstruction loss. This shows the benefit of topology-awe awwre partitioning for objects with complex textures.
Generalization. To test the generalization ability of our model, took the model trained on the ClevrTex dataset and evaluated it on the OOD and CAMO evaluation datasets bundled with ClevrTeex The results are shown in Table [ While all models experience decrease in segmentation performance, our method remains one of the best to generalize. Especially on the CAMO dataset, our method outperforms all baselines in both mloU and ARI-FG, even increasing the gap the best pixel- space baseline in terms of mloU to 19%. The reason for this is that the min-cut problem can easily take into account the sharp transitions in the image between the background and foreground objects by increasing the weight for the edges that connect the pixels at the transitions. Other pixel-space
https://gi tttp::///gtttbb...oo com dwwpmi nd /
8

---

Published as a conference paper at ICLR 2023
methods like Slot Attention often focus the color and texture for partitioning the image (Karazija et al. 2021] Dittadi et al. 2022). This makes the CAMO dataset much more difficult since all objects
almost identical in these attributes to the background.
6.2 MATCHING VALIDATION
Next validate the matching procedure by ing the experiment for bipartite matching with learned weights used by Wilder et al.] (2019) with the Cora citation dataset. The task is to pre- dict the presence of an edge only using the node features. A neural network predicts the param- eters of the matching linear program which is relaxed to a quadratic program in Wilder et al. (2019) for training. We replace the relaxed quadratic program with regularized equality constrained quadratic program with y 0.1. The main difference is that do not have non-negativity constraints for the variables and regularization instead. For evaluation evaluate using the true linear program with the learned parameters using an LP solver. For this experiment we achieve an average (maximiza- tion) objective function value of 7.01 which is improvement over 6.15 reported by Wilder et al. (2019).
Figure 5: Capturing moving object on the MOVi-A dataset (without cropping). Top row shows original objects, second row shows object masks
Qualitative Validation. We also validate the matching method qualitatively on the MOVi-A dataset. We take two far separated frames and reconstruct the pair of frames using slot match- ing as described in Algorithm 3] In this test we take frame index 5 and 20. An example is shown in Figure Ø in Appendix A where we show reconstructions for the two separated frames that have been successfully matched even though some objects are far from their original positions.
Table Evaluation results on MOVi-A
6.3 MOVING OBJECTS
Model
ARI-FG (%)
ARI (%)
Slot Attention
4.2
0.3
We work with the MOVi-A (Greff et al. 2022) of moving object videos with 24 frames in each video. We crop the frames to 0.8 times side, take the center and resize to 128x128 and use slots per frame. We train the object discovery model on pairs of adjacent frames. Given pairs of scene features the slots module produces two sets of slots which are then matched together using the method described in Algorithm 3 into a single set of slots. The new set slots is then used reconstruct the two frames. Reconstructions from the background slot and object slots (identified by position) are shown in Figure 5) The slot is able to track the object over multiple steps.
Ours
65.6
77.7
We compare against slot attention baseline where train slot attention individual frames. Next, during evaluation, we match sets of slots for consecutive frames using the Hungarian algorithm, using inter slot inner product as the similarity score. The results are shown in Table We see from the results that slot attention has no better than random clustering performance, whereas our cut-based method obtains a foreground ARI of 65.6 even though it was trained only with pairs of frames.
CONCLUSION
We propose method for object-centric learning with partitioning and matching. We also present an efficient and scalable mathematical programming approach based quadratic programming approximation for solving the partitioning and matching problems. In the experiments we showed that our approach be used in both static and moving object settings. We also show that the method outperforms competing methods on object discovery tasks in textured settings ?
"Code repository: http:///ttthhhh...////////////aa
thub

---

Published as a conference paper at ICLR 2023
8 ACKNOWLEDGEMENTS
This work financially supported by Qualcomm Technologies Inc., the University of Amsterdam and the allowance Top consortia for Knowledge and Innovation (TKIs) from the Netherlands Ministry of Economic Affairs and Climate Policy.
REFERENCES
Christopher P Burgess, Loic Matthey, Nicholas Watters, Rishabh Kabra, Irina Higgins, Matt Botvinick, and Alexander Lerchner. Monet: Unsupervised scene decomposition and representation. arXiv preprint arXiv: 11390, 2019.
Francesco Locatello, Dirk Weissenborn, Thomas Unterthiner, Aravindh Mahendran, Georg Heigold, Jakob Uszkoreit, Alexey Dosovitskiy, and Thomas Kipf. Object-centric learning with slot attention. Advances in Neural Information Processing Systems, 33:1 1525 1538, 2020.
Gamaleldin F Elsayed, Aravindh Mahendran, Sjoerd van Steenkiste, Klaus Greff, Michael C Mozer, and Thomas Kipf. Savi++: Towards end-to-end object-centric learning from real-world videos. arXiv preprint arXiv:2206.07764 2022.
Bryan Wilder, Bistra Dilkina, and Milind Tambe. Melding the data-decisions pipeline: Decision- focused learning for combinatorial optimization. In Proceedings of the AAAI Conference Artificial Intelligence, volume 33, pages 1658-1665, 2019.
Shane Barratt. On the differentiability the solution to convex optimization problems. arxiv:1804.05000 2018.
Brandon Amos and J Zico Kolter. Optnet: Differentiable optimization layer in neural networks. In International Conference on Machine Learning, pages 136-145. PMLR, 2017.
Stephen Wright and Jorge Nocedal. Numerical optimization. Springer Science, 35(67-68):7, 1999.
Jon Kleinberg and Éva Tardos. Algorithm Design. Pearson, 2005.
Y.Y. Boykov and M.-P. Jolly. Interactive graph cuts for optimal boundary & region segmentation of objects in n-d images. In Proceedings Eighth IEEE International Conference on Computer Vision. ICCV 2001, volume I, pages 105-112. IEEE Comput. Soc, 2001, ISBN 177--0-7695--143-66 doi: 10.1 10.1109//CC/2000111 .937505.
Jianbo Shi and Jitendra Malik. Normalized cuts and image segmentation. IEEE Trans. Pattern Anal. Mach. Intell., 22(8):888-905 aug 2000. ISSN 0162-8828. doi: 10.1109/34.86688
George Bernard Dantzig and Delbert Ray Fulkerson. On the max flow min cut theorem of networks.
Technical report, RAND CORP SANTA MONICA CA, 1955.
Sang Michael Xie and Stefano Ermon. Reparameterizable subset sampling via continuous relaxations. In International Joint Conference on Artificial Intelligence, 2019.
B. Stellato, G. Banjac, P. Goulart, A. Bemporad, and S. Boyd. OSQP: an operator splitting solver for quadratic programs. Mathematical Programming Computation, 12(4):637-672, 2020. doi: 10. 10.10077/12332-42000019999999
Gurobi Optimization, LLC. Gurobi Optimizer Reference Manual, 2022.
Yanqing Chen, Timothy A Davis, William W Hager, and Sivasankaran Rajamanickam. Algorithm 887: Cholmod, superoodal sparse cholesky factorization and update/downdate. ACM Transactions on Mathematical Software (TOMS), 35(3):1-14, 2008.
Tobias Plötz and Stefan Roth. Neural nearest neighbors networks. Advances in Neural information processing systems, 31, 2018.
Aditya Grover, Eric Wang, Aaron Zweig, and Stefano Ermon. Stochastic optimization of sorting networks via continuous relaxations, In International Conference on Learning Representations, 2018.
10

---

Published as a conference paper at ICLR 2023
Christos Louizos, Max Welling, and Diederik P. Kingma. Learning Sparse Neural Networks through L_0 Regularization. In International Conference on Learning Representations, 2018.
Nicola De Cao, Michael Sejr Schlichtkrull, Wilker Aziz, and Ivan Titov. How do decisions emerge across layers in neural models? interpretation with differentiable masking. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 3243- 3255. Association for Computational Linguistics, 2020.
Zhenyu Wu and Richard Leahy. An optimal graph theoretic approach to data clustering: Theory and its application to image segmentation. IEEE transactions on pattern analysis and machine intelligence, 15(1 (5(11):1001 101-1111,,,,,11 1993.
Yuri Boykov and Gareth Funka-Lea. Graph cuts and efficient n-d image segmentation. 70(2):109- 131, 2006. ISSN 0920-5691, 1573-1405. doi: 10.1007/6 1263-006-7934-5.
Dorothy M Greig, Bruce Porteous, and Allan H Scheult. Exact maximum a posteriori estimation for binary images. Journal of the Royal Statistical Society: Series B (Methodological), 51(2)2271- 51Q))) 279, 1989.
Vladimir Kolmogorov and Ramin Zabih. Computing visual correspondence with occlusions using graph cuts. In Proceedings Eighth IEEE International Conference on Computer Vision. ICCV 2001, volume 2, pages 508-515, IEEE, 2001.
Thomas Kipf, Gamaleldin F Elsayed, Aravindh Mahendran, Austin Stone, Sara Sabour, Georg Heigold, Rico Jonschkowski, Alexey Dosovitskiy, and Klaus Greff. Conditional object-centric learning from video. International Conference on Learning Representations (ICLR), 2022.
Rishabh Kabra, Daniel Zoran, Goker Erdogan, Loic Matthey, Antonia Creswell, Matt Botvinick, Alexander Lerchner, and Chris Burgess. Simone: View-invariant, temporally-abstracte object representations via unsupervised video decomposition. Advances in Neural Information Processing Systems, 34, 2021.
Martin Engelcke, Adam R Kosiorek, Oiwi Parker Jones, and Ingmar Posner. Genesis: Gener- ative scene inference and sampling with object-centric latent representations. arXiv preprint 1rXhv:1907.13052. 2019.
Klaus Greff, Raphaël Lopez Kaufman, Rishabh Kabra, Nick Watters, Christopher Burgess, Daniel Zoran, Loic Matthey, Matthew Botvinick, and Alexander Lerchner. Multi-object representation learning with iterative variational inference. In International Conference on Machine Learning. pages 2424-2433, PMLR, 2019.
Martin Engelcke, Oiwi Parker Jones, and Ingmar Posner. Genesis-v2: Inferring unordered object representations without iterative refinement. Advances in Neural Information Processing Systems, 34:8085-8094, 2021.
Zhixuan Lin, Yi-Fu Wu, Skand Vishwanath Peri, Weihao Sun, Gautam Singh, Fei Deng, Jindong Jiang, and Sungjin Ahn. Space: Unsupervised object-oriented scene representation via spatial attention and decomposition. arXiv preprint Stt::2001.02400 2020.
Jindong Jiang and Sungjin Ahn. Generative neurosymbolic machines. Advances in Neural Information Processing Systems, 13:12222-12582 2020.
Eric Crawford and Joelle Pineau. Spatially invariant unsupervised object detection with convolutional neural networks. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 3412-3420, 2019.
Sindy Löwe, Phillip Lippe, Maja Rudolph, and Max Welling. Complex-valuee autoencoders for object discovery. arXiv preprint arXiv:2204.02075, 2022.
David P Reichert and Thomas Serre. Neuronal synchrony in complex- valued deep networks. Interna- fional Conference on Learning Representations (ICLR), 2014.
11

---

Published as a conference paper at ICLR 2023
Dmitriy Smirnov, Michael Gharbi, Matthew Fisher, Vitor Guizilini, Alexei Efros, and Justin M Solomon. MarioNette: Self-supervised sprite learning. Advances in Neural Information Processing Systems, 34:5494-5505, 2021.
Tom Monnier, Elliot Vincent, Jean Ponce, and Mathieu Aubry. Unsupervised layered image decom- position into object prototypes. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 5540-8650, 2021.
Laurynas Karazija, Iro Laina, and Christian Rupprecht. Clevitex: A texture-rich benchmark for unsu- pervised multi-object segmentation. In Thirty-fifth Conference on Neural Information Processing Systems Datasets and Benchmarks Track (Round 2), 2021.
Patrick Emami, Pan He, Sanjay Ranka, and Anand Rangarajan. Efficient iterative amortized inference for learning symmetric and disentangled multi-object representations. In International Conference on Machine Learning, pages 2970-2981, PMLR, 2021.
Justin Johnson, Bharath Hariharan, Laurens Van Der Maaten, Li Fei-Fei, C Lawrence Zitnick, and Ross Girshick. Clevr: diagnostic dataset for compositional language and elementary visual reasoning. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 2901-2910, 2017.
Andrea Dittadi, Samuele Papa, Michele De Vita, Bernhard Schölkopf, Ole Winther, and Francesco Locatello. Generalization and robustness implications in object-centric learning. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato, editors, Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceed- ings of Machine Learning Research, pages 5221-5285. PMLR, 17-23 Jul 2022.
Klaus Greff, Francois Belletti, Lucas Beyer, Carl Doersch, Yilun Du, Daniel Duckworth, David Fleet, Dan Gmanapragasam, Florian Golemo, Charles Herrmann, Thomas Kipf, Abhijit Kundu, Dmitry Lagun, Issam Laradji, Hsueh-Ti (Derek) Liu, Henning Meyer, Yishu Miao, Derek Nowrouzezahrai, Cengiz Oztireli, Etienne Pot, Noha Radwan, Daniel Rebain, Sara Sabour, Mehdi S. M. Sajjadi, Matan Sela, Vincent Sitzmann, Austin Stone, Deqing Sun, Suhani Vora, Ziyu Wang, Tianhao Wu, Kwang Moo Yi, Fangcheng Zhong, and Andrea Tagliasachhi. Kubric: a scalable dataset generator. 2022.
Ryosuke Okuta, Yuya Unno, Daisuke Nishino, Shohei Hido, and Crissman Loomis. Cupy: A numpy- compatible library for nvidia gpu calculations. In Proceedings of Workshop on Machine Learning Systems (LearningSys) in The Thirty-fire Annual Conference on Neural Information Processing Systems (NIPS), 2017.
CUDA Nvidia. Cusparse library. NVIDIA Corporation, Santa Clara, California, 2014.
12

---

Published as a conference paper at ICLR 2023
A MATCHING VALIDATION
We validate the matching method qualitatively on the MOVi-A dataset. We take two far separated frames and reconstruct the pair of frames using slot matching described in Algorithm B In this test we take frame index and 20. An example is shown in figure O where we show reconstructions for the two separated frames that have been successfully matched even though some objects are far from their original positions.
Figure 6: Matching far separated frames.
B SPARSE MATRIX COMPUTATIONS
The constraint matrix A can be very large for object-centric applications since the image graph scales quadratically with the image resolution. For 64x64 images we get s-t cut quadratic programs with over 52,000 variables and over 23,000 constraints (resulting in a constraint matrix of size over 4GB) which have to solved batch for each training example. Since the constraints matrices are highly sparse (about 6% non-zero elements for 64x64 images) use sparse matrices and sparse Cholesky factorization (Chen et al.) 2008). During training we use batched sparse triangular solves for the backward and forward substitution to solve a batch of quadratic programs with different right hand sides in equation[3] Since current neural network frameworks do not support sparse triangular solves we use CuPy (Okuta et al.) 2017) which provides an interface cuSPARSE (Nvidia 2014). These optimizations result in fast computation of batches of quadratic programs and allow us to scale to image scale data. Assuming graph size of N, solving the quadratic program directly (with dense Cholesky factorization) has complexity about ((N3) and is even greater for general quadratic programs. With our optimizations this reduces to ON,,,,, where ng is the number nonzero elements which is the time required for sparse triangular solve.
C REGULARIZED EQUALITY CONSTRAINED QUADRATIC PROGRAM FOR MATCHING
We approximate problem by adding an extra slack variable to the constraints, remove the non- negativity constraint and add regularization terms to the objective. After solving the new quadratic program, we normalize the edge variables by using a softmax over the second vertex. Note that this does not give perfect matching of k-partitions in the bipartite graph since multiple nodes in the first partition can be associated with a single node the second. However, the regularization keeps the number of such multiple assignments small and this works well for our use case experiments. The alternative of skipping the quadratic program and directly using softmax over parameters frequently results in degenerate assignments of large number of P1 partitions assigned to a small number Pg partitions.
show in the
minimize
Eun + Σ di,, + Σ
p +
(7)
subject to Pu + due + Su 1,
Po + due + 8r
D TRAINING DETAIL FOR CLEVR AND CLEVRTEX
We train using either single A6000 GPU or GTX 1080Ti GPUs for 1.5 days for ClevrTex and on Clevr using batch size of 64. We Adam with learning rate of 4e-4, Training is generally stable
13

---

Published as a conference paper at ICLR 2023
and we did not require learning rate warm-up. Although not strictly necessary, trained with an exponential learning rate decay. For these experiments we used 12 slots with each slot having a size of 64.
E ABLATION EXPERIMENTS
E.1 EFFECT OF INTERPIXEL EDGE WEIGHT
We perform an experiment to judge the effect of the interpixel edge weights on performance. We fix the interpixel edges weights and learn only the and edge weights. For this experiment use the smaller varied background variant of ClevrTex downscaled to 64x64. We train the models with and without learning the interpixel edge weights for about 170 epochs with slots. The results are shown in Table 3 with image masks shown in Figure 7 Without learning interpixel we see large drop in segmentation performance of about points in mloU. The segmentation quality without learned edge weights is significantly poorer as also seen visually in Figure
Table 3: Ablation results for learning interpixel weights
Model
mloU (%)
ARI-FG (%)
W/O Interpixel Woight
19.4
52.7
With Interpixel Weight
27.3
67.1
Figure 7: Segmentation masks without learned interpixel weights (left) and with learned interpixel weights (right)
E.2 EFFECT OF THE REGULARIZATION PARAMETER 7
we perform experiments with various values for the {0.5, 1,2] and check evaluation set segmentation performance, Results are shown in Table We find that quantitative performance on the evaluation set is best with y and that performance significantly drops with large y. Very small values of can make training unstable since appear inverted in 6 in the block term C.
Using the same setup as in the Section E.
regularization parameter 7. We choose
Table 4: Effect of y on Segmentation Performance
mloU (%)
ARI-FG (%)
0.5
27.3
67.1
30.6
68.7
15.2
14


Reviews:
[{"review_id": "VnkTRRIx86", "reviewer": "Reviewer_miwq", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 1, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper on hand presents an approach for s-t graph cuts, relying on a differentiable quadratic approximation of the original problem. The approach is demonstrated for different applications.", "summary_of_the_review": "Even though the experimental results do not really show clear benefits, and also special cases are not discussed, the paper presents a fresh idea, going beyond just changing minor things in established methods. In particular, transferring a linear problem to a quadratic one, allowing to combine ideas from graph cuts with neural network learning is an interesting approach and a worthwhile contribution.", "strength_and_weaknesses": "Strength:\n\nThe idea of approximating the original linear problem by a special quadratic program, which is differentiable is interesting.\n\nIn this way, graph cuts and modern neural networks can be combined in a reasonable way.\n\n\nWeaknesses:\n\nThe experimental results are ambiguous. It is not fully clear for which kind of problems the approach would be meaningful in practice?\n\nThe structure and the presentation must be improved to increase the readability.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "Stw223RPKO", "reviewer": "Reviewer_9nSj", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies object centric representation learning and formulates it as a neural graph cut problem that involves parameterizing the coefficients of objective function of the linear program with neural networks. To this end, it converts the LP into a quadratic program that is easier to optimize with deep networks. The method is experimentally validated on object discovery as well as small scale matching tasks.  ", "summary_of_the_review": "I am not sure about the significance of the problem considered in this paper and technical novelty of the solution proposed. i am happy to reconsider my rating based on rebuttal and other reviews.", "strength_and_weaknesses": "Strengths:\n\n- idea of Neural Graph cut is interesting. Experiments on two datasets show the effectiveness of the method wrt some baselines considered in the paper.\n\nWeakness:\n\n- Presentation: why do we need to study object centric representation learning. the submission should motivate it somewhere with few lines and contextualize it in broader context IMHO..e.g. how it relates to scene graph parsing approach  or constrained CNN (pathak et al. , ICCV 2015) which also optimizes a quadratic program with CNN to achieve semantic segmentation.\n\n- Novelty: is there any technical novelty in section 3.1? maybe i am missing something but to me this section appears to be classic QP optimization..although the idea of  neural graph cut problem formulation is interesting, solution appears to be a straightforward extension of QP optimization..this is not a strong weakness but authors should clarify the novelty if any in this section. if not, much of this can be covered in a background section.\n\n- Baselines: I did not see any baselines involving classical optimization schemes such as graph cut or normalized cut in the experiment section.  why not build an affinity graph with state of the art pretrained-CNN features on the two datasets and simply run a classical method. is scalability an issue here? besides, I did not find a scalability comparison with some existing approaches as one of the main claim of submission is its scalability to other approaches.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "KE097tiCcM", "reviewer": "Reviewer_eQdL", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper addresses the problem of turning the optimization of an LP (linear program) into a differentiable layer. This is done by approximating the LP by a QP (quadratic program) and using the QP as a differentiable proxy for the LP. The specific focus of this paper is the LP of finding an optimal s-t cut in a directed graph.\n\nThe s-t cut is then extended to a multi-cut problem which is used for object segmentation. Since the segmentation is done based on specific object features (used to define the graph), the approach does in fact perform an object-centric representation learning.\n\nThe paper explores how this representation learning helps in object discovery tasks and matching tasks.", "summary_of_the_review": "Overall, the paper describes a nice approach on how to integrate s-t-cuts into a deep learning framework and demonstrates its usefulness for representation learning. The theoretical weaknesses are easy to fix for the final version. Due to the limiting experiments, I cannot give the maximal score. Nonetheless, I would like to see the paper presented at ICLR'23.", "strength_and_weaknesses": "Strengths:\n+ The method is well motivated and emphasizes the main challenges of the approach (differentiability, runtime and memory consumption)\n+ The method builds nicely on existing methods like implicit function approach (Amos and Kolter), diff. mathematical programming (Wilder), graph cut in computer vision (Boykov, Kolmogorov), sparse Cholesky factorization (Chen et al.), etc.\n+ The results are promising and demonstrate the usefulness of an LP layer in a deep learning framework\n\nWeaknesses:\n- The paper does not address the issue that the multi-cut problem is NP hard and that any solution can only be an approximation. Here, references to alpha-expansion or alpha-beta-swap [Boykov, Veksler, Zabih, ICCV'99] might be useful.\n- Page 4 describes the graph not entirely correctly. Every vertex (except for source, sink and image boundary vertices) has 5 incoming and 5 outgoing edges, since edges between neighboring vertices are bi-directional.\n- The experiments are a bit underwhelming, since semantic image segmentation experiments (CityScape) are missing", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "IAhRqnU9UD", "reviewer": "Reviewer_wmJ4", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper propose a new aggregation method for Object-Centric Representation Learning. That is, a conversion of CxHxW feature map into KxHxW masks with K objects. Instead of standard attention of softmax, the paper injects an optimization problem related to minimum cut problem.", "summary_of_the_review": "While overall approach seems novel and interesting, the significance of the results is not clear, see weakness section of the review.", "strength_and_weaknesses": "The interesting and promising aspect of the paper is that the initial minimum cut problem encodes pair-wise (topological) relationships between pixels.\n\nTheir actual formulation (2) is much different from minimum cut formulation in (1). By adding square regularization term and removing non-negativity constraints, the papers moves far from the original min cut. Their heuristic integration of k parallel s-t cuts is also quite far from classical definition of k-way cut. Though it still may be valuable, one can hardly use the seemed similarity to min cut for insights or explanations. It is a stretch to claim proposing graph cuts for k-partition with neural networks.\n\nThe paper lack ablation study of the pairwise weights. I.e. the experiment where all pairwise weights are set to 0 and only weights of edges connecting to s or t are learned.\n\nThe paper lack ablation study on gamma. How does performance of the method changes when changing gamma closer to 0?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster