Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: 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.  
strength_and_weaknesses: Strengths:

- idea of Neural Graph cut is interesting. Experiments on two datasets show the effectiveness of the method wrt some baselines considered in the paper.

Weakness:

- 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.

- 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.

- 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.
clarity,_quality,_novelty_and_reproducibility: The submission provide enough details for reproducibility. for clarity and novelty, please see comments above.
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.
review_title: null

final_score: rating: 8: accept, good paper
review_content: 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.
strength_and_weaknesses: Strength:

The idea of approximating the original linear problem by a special quadratic program, which is differentiable is interesting.

In this way, graph cuts and modern neural networks can be combined in a reasonable way.


Weaknesses:

The experimental results are ambiguous. It is not fully clear for which kind of problems the approach would be meaningful in practice?

The structure and the presentation must be improved to increase the readability.
clarity,_quality,_novelty_and_reproducibility: Overall, the contribution is clear, however, the structure and the presentation might be overworked:

The arrangement of figures, algorithms, and tables is hampering the reading flow.

The font size in Table 1 is too small. The table is hard to read.

The related work sections does not really discuss related work. This is just general an overview of works in this topic.

The mathematical writing must be seriously checked!

The bibliography entries needs to be seriously checked!
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.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: 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.
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.

Their 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.

The 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.

The paper lack ablation study on gamma. How does performance of the method changes when changing gamma closer to 0?
clarity,_quality,_novelty_and_reproducibility: Overall clarity and quality is fair. The approach seems novel.

The notation is somewhat confusing. The overall loss function is not defined (Is it the quadratic program objective?). In (2), $s$ is used as both the slack variables and sink node. Unclear the details of solving KKT equations in Eq.6 (why solution is Ez and Cz?).
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.
review_title: null

final_score: rating: 8: accept, good paper
review_content: 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.

The 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.

The paper explores how this representation learning helps in object discovery tasks and matching tasks.
strength_and_weaknesses: Strengths:
+ The method is well motivated and emphasizes the main challenges of the approach (differentiability, runtime and memory consumption)
+ 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.
+ The results are promising and demonstrate the usefulness of an LP layer in a deep learning framework

Weaknesses:
- 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.
- 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.
- The experiments are a bit underwhelming, since semantic image segmentation experiments (CityScape) are missing
clarity,_quality,_novelty_and_reproducibility: The paper is well written and easy to understand. Every design choice is well explained. Therefore, it should be easy to reproduce the results, even without the code. Since the authors promise to provide the code, there are no reproducibility issues.
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.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: Thank you for your submission to ICLR.  Although there was some disagreement amongst the reviewers, having gone through the paper and reviews myself, I agree with the more positive assessments of the paper.  In particular, I believe that the paper presents a notable contribution to the field, first in terms of a reasonable advance to the field in terms of representation learning (where the results are compelling in and of themselves).  But the work also represents a nice illustration of differentiable optimization and implicit layers themselves (with specialized algorithms for solving the optimization problems here), showcasing a valuable illustration of the power and potential of these approaches.  Overall, these two contribution together make a strong contribution.

Several reviewers did have some confusion regarding terminology and/or requested additional ablation experiments.  It would be great to address these clarification points in the camera ready version, plus adding the additional ablation experiments if possible.
justification_for_why_not_higher_score:  The paper is quite strong, but still likely in a somewhat narrow niche area for the entirety of ICLR.  There were also a number of additional ablation experiments that, as the reviewers pointed out, could strengthen the work as it currently stands.
justification_for_why_not_lower_score:  The paper presents a valuable contribution both to object-centric learning and a compelling application of differentiable optimization methods.  Overall these combine to make a compelling final contribution, and one definitely worth accepting.
Decision: Accept: poster