Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The authors propose a scalable approach (compared to existing ones)
for the 'unsupervised object discovery' task, based on graph and link
analysis methods. They show on several datasets and on the two tasks
of single and multiple object discovery, that their method is either
substantially more scalable and/or has better accuracy.
main_review: 
Summary of review:

-- Interesting approach and problem, but I couldn't convince myself that the idea of using a graph could
improve results so much:
Why should the overall idea of link-analysis/ranking by 'authority/hubs' idea, behind the particular objective and their particular  algorithms,
substantially help for this problem? it would be useful  to give more
 intuition (the authors do try to explain/motivate in a few cases)... (see below for more details on this ..)

-- use of 'supervised features' defeats the purpose/motivation  of the 'unsupervised'  task. The
 authors have a nice section on using recent work that doesn't use
 supervised features ... perhaps  they should start with that and make that more central
 (because it appears that they are testing on datasets where labels
 overlap significantly between where the features were trained on (eg
 imagenet) and those datasets ) ..

-- sensitivity analysis to various params (eg max number of neighbors or
 random perturbations?): do they do this in the paper?

-- a number  of clarity (presentation) issues. please see below.

---------------
More details (the numbers refer to line numbers):

why should this work? it would be useful to give more intuition..

in particular: objectness based on votes of similarity of neighbors.. it seems that
if two proposed regions are very similar we may get high objectness
for both regions.. and/or (more generally) if there is a large
(semi)clique of very similar regions in different images, we could get
high (in paper, it's called y) scores..  So what if we replicated each
image k times in the corpus.. (some sufficiently large replication factor above max
number of neighbors in the optimization) would that that foil this
approach?


61: do you mean link 'regions' vs 'images' in 'and link images that
contain similar objects..' (since an image can contain multiple
regions/objects?)

62: does every image have exactly r proposals?  It's not clear whether
this is variable or fixed.  It would be good to give clear
(mathematical) definitions too (instead of solely relying on English).
If r is fixed, what happens to images that should get no or only one or 
 fewer than r proposals (do we create dummy proposals for such?). Good to make
this clear.
...


66: not sufficiently clear.. what does 'correspond to visual content
shared' mean?  what does 'share' mean? This definitely  needs to be clarified,
since this is problem definition (see below too).

One clarification is wrt to number, assuming 'sharing similar visual
content' means same objects: do you mean, some of the neighbors have
the same object, or *all* the neighbors, or at one least one, etc:
"Similarly, let x_kp ∈ {0,1} for p = 1,2,...,n and k = 1,2,...,r be
indicator variables such that x_kp = 1 when region proposal k of image
p corresponds to visual content shared with its neighbors and let xp =
(x1p , . . . , xrp )T ."

- this approach depends very largely on accuracy of region
  proposals.. (very much depends on..)

- minor: as an aside: why tao and rho are constants.  It seems making the
  number of neighbors image and region dependent, perhaps based on a
  similarity threshold, would be better... The nature of the two
  parameters seem different: one (max number of regions per image) is
  property of the data and region detection algorithms used, while the
  other (max number of neighbors allowed) seems to be a meta
  parameter, provided by the user.


- minor: again, the English description of tao is not very clear.  It
  likely means over all the images, take the maximum.  if written in
  mathematics, in addition or instead of, just saying it in English,
  it would be clearer.


- 243: (in multiple object regime) Does the user specify M or
 otherwise, in an unsupervised problem, what can M be?? (I am thinking
 in their experiments, they know what M is from the datasets..)  in
 "we return up to M regions per image, where M is the maximum number
 of objects in any image in the dataset. "


- 311: doesn't defeat the purpose of 'unsupervised' object discovery to
use image-net trained models (even for features??).. in
"Self-supervised features vs. supervised features. LOD and all of the
optimization-based base-lines [32, 67, 71] rely on a VGG [60]-based
classifier trained on ImageNet [11]."

- 400: '87x'   in   "..allows us to scale up UOD to the OpenImages [35] dataset
(Op1.7M) with 1.7M images, 87 larger
than datasets considered in the previous state-of-the-art technique [67], and outperforms

- multi objective performances seem very low .. perhaps some
  discussion of that?

=============

After seeing author replies and other reviewers.

I have read the reviews and authors' responses.   Thank you all. Given the authors' responses, I have increased
my rating to leaning to accept, as I trust the authors will address a main issue, use of supervised vs unsupervised features, well, and considering the other author responses to various issues I raised, and the other reviewers' feedback (and the presentation issues can be mostly addressed). Thank you.


limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: This paper deals with object discovery problems (single object discover as well as multiple object discover). It proposed to solve the challenge as a ranking problem. It first generates object proposals on all images in the dataset. Then object proposals are ranked based on their similarity to regions in other images. The ranking task in the paper is performed with PageRank. The experiment shows it achieves promising results on the COCO and OpenImage dataset.
main_review: Originality: Utilizing ranking for object discovery seems original to me.
Clarity: The paper lacks motivations/discussions of the proposed technology, making it hard to follow why a mathematical method is employed in the framework. Adding intuitive discussions about why ranking is a good technical solution for object discovery would improve the quality of the paper.
Quality: The paper is technically correct to me. Graph connection density is definitely an implication about the frequently appearing objects. However, it corresponds to discovering the frequent objects. The paper could add more discussion about whether the technology is a good fit for the task of object discovery which looks to discover single/all foreground objects. 
Significance: The paper is of interest of the community. 
limitations_and_societal_impact: I wonder whether performing ranking based on object proposal similarity with other regions in the dataset leads to an ill configuration of the unsupervised object detection problem. It encourages discovery of frequently appearing objects, when suppressing objects rarely appear.  I would be great if the paper could provide the performance over object categories with different   instance numbers, respectively.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This is a very interesting paper. It builds upon object discovery formulation by [Vo et al., CVPR’19; ECCV’20], which formulates the discovery as (co-)detection of frequently occurring patterns within an image collection. This approach assumes input in the form of object proposals (together with a feature extractor or related mechanism that will be used to determine pairwise similarities) and formalizes object co-detection as a combinatorial optimization problem that seeks object proposals with high connectivity across the dataset. It has been established by [Vo et al., CVPR’19; ECCV’20] that this approach performs notably better compared to sliding window-based approaches that rank proposals in images independently [e.g., Zitnick et al., ECCV’14]. The paper makes a case that optimization methods proposed in prior work, do not scale to very large datasets, largely because they are not parallelizable. To tackle the scalability issue, this paper draws parallels between the discovery objective [Vo et al., CVPR’19] and object ranking, cast as a quadratic optimization problem, and well-known PageRank algorithm, as well as a combination of the two. Under this formulation, optimal ranking of proposals can be obtained via Eigenvalue decomposition of the adjacency matrix using the power iteration algorithm. While single-core implementation does not present a significant advantage over solvers proposed to tackle the original optimization formulation [Vo et al., CVPR’19; ECCV’20], this approach is highly parallelizable and, in turn, allows to apply this method to very large datasets, such as OpenImages, containing over 1.7M images and is on-par or slightly better in terms of the object discovery performance. 
main_review: Pros

———————

* This paper is very well written, motivated, and presents a very good case. Object discovery in image collection is indeed a very relevant problem, as we are slowly approaching the limits of the supervised learning paradigm. Nowadays, image data is abundant; therefore, I see the contribution of methods that can scale well to very large datasets as very valuable to our community. 
* In general, I find that the technical contribution of this paper stands on very solid ground: I love the insight that the formulation by [Vo et al., CVPR’19] can be re-interpreted as a ranking problem over a fully-connected graph of proposals and establishing the link to well-understood and mature methodology for link analysis. 
* The implications of this insight are important and will allow performing object discovery on (abundant) large-scale unlabelled photo collections. The contribution is orthogonal to (from my side anticipated) future efforts in unsupervised object-centric representation learning. 
* The paper presents solid experimental analysis on COCO dataset (and subsets), as well as the large-scale OpenImage dataset. Analysis shows that the only competitive method [Vo et al., ECCV’20] is not applicable to OpenImages (I do have some criticism on this point, though- see the weaknesses section). I also appreciate the detailed discussion on the impact of different object proposals and features (ImageNet-supervised and self-supervised), and the comparison between three variants of this ranking formulation. 
* Besides parallelization, it is also very nice that this formulation is scalable enough that it doesn’t need to limit the number of object proposals per image, which I assume is the main reason behind slightly better performance compared to [Vo et al., ECCV’20]. At the same time, I would also like to note that it would be nice to discuss this experimentally. 


Cons

———————

* The most problematic aspect of this paper is the very vague definition of what “other top-performing methods cannot handle” (Tab 1.). This is further related to Sec. 4.1, run time discussion, which states that “[32] and [67] did not finish in reasonable time”. What is considered to be a reasonable time? One week (par. “Quantitative evaluation” mentions that)? For example, training neural networks can easily take one week or more, and if a method needs more than a week (2 weeks?) to finish, I would not say that it is not applicable to such a large dataset. I understand that one cannot wait for the optimization to converge for months, but I am really in the dark here what kind of time spans we are talking about, and I would like to see a discussion on this (also the final version of the paper must be more precise here). Also, let me remark here that “reasonable time” will be different in the future with better compute (although it is true that datasets will be growing as well). 
* It can be seen that optimization-based methods scale linearly (i.e., scale very well). Therefore we can also expect that these methods should be very applicable in the future. I definitely see that the major advantage of the proposed method due to the fact that it is nicely parallelizable, but this aspect is related to the core contribution of this paper. Finally, I do not understand why EB runtime is constant? It should be linear wrt. the number of images (when processed serially), or else I dramatically misunderstood something. 
* This might be no an issue with this paper per se, but more general- is AP the right metric for this? In my opinion, it isn’t because object discovery is not well-defined (part vs. whole object ambiguity), and therefore, every (possibly relevant) discovered region that is not labeled would be considered as FP and penalize the performance. Using incorrect metrics may hinder progress in this field. Why not evaluating (average) recall wrt. pre-fixed proposal thresholds instead? 
* This is also a more general comment: object discovery formulation, as tackled in this paper (and formalized by Vo et al., CVPR’19), is inherently about finding commonly occurring patterns in the image collection. Wrt. the long-tailed distribution of object classes, this will only be applicable to the “head” classes and will dismiss the tail. I am not saying that methods tackling the discovery of frequently occurring objects/patterns are not valuable, but I believe that this venue explicitly encourages discussion of limitations, and this is certainly one of them! 



Justification

———————

I think this paper presents a nice contribution for scalable optimization-based object discovery. Besides having solid theoretical ground, I find this paper well explained and experimentally validated and overall find that it should be a nice contribution to this venue. 

Post-rebuttal:


———————

This is my summary of my thoughts on the other reviews and rebuttals:

**3zeH, N6wG express doubts on object discovery using a graph-based formulation that finds common patterns based on connectedness analysis:**

I find that this approach to object discovery has already been well-motivated and established in the community (Vo et al., CVPR’19, and ECCV’20). I agree that this is a bit exotic research direction, but I still think it is one worth pursuing, especially given that nowadays, we are collecting large amounts of unlabeled data that “we don’t know what to do with.” Moreover, the novelty of this paper is not in proposing to pose discovery as a combinatorial optimization problem, but rather seeing parallels between methods by Vo et al., and link analysis that admits highly parallelizable algorithms.

**Use of ‘supervised features’ and on the dependability on object proposals (3zeH):**

I believe this work follows the experimental protocol proposed in papers by Vo et al., plus analyses performance using both hand-crafted and deep features.
I think pretty much all discovery methods depend on object proposals (as do several object detectors). I see no issue here.

**Finding commonly-occurring patterns will inherently ignore the “long-tail”** — I’ve had a similar concern as N6wG on this; however, the rebuttal reports a weak correlation with object occurrence frequency. I would like to see a more detailed discussion on this, but either way, I also do believe that the discovery of frequently occurring objects is an open and very challenging problem worthy of new contributions.

**Re-formulation is incremental:** I respectfully disagree with FJwA that establishing this link is of incremental nature; it certainly is obvious in hindsight, but noting the link, re-formulating the objective proposed in Vo et al., and demonstrating experimentally that this yields a highly scalable and parallelizable solution is a solid contribution in my view.

Overall I find this paper relevant and valuable, and I think that the paper should be accepted. 
limitations_and_societal_impact: As I noted above, authors should address limitations better.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper introduces an efficient approach for Unsupaervised Object Discovery (UOD). This efficiency was achieved by considering the exising UOD formulation as a ranking problem by modifying the binary importance vector as having a floating value. This modification allows to apply this approach to a very large-scale dataset (up to 1.7M images) without compromising accuracy.
main_review: - pros
1. It was very nice to reformulate the existing UOD formulation to be fit to a PageRank solution.
2. First to introduce an UOD approach to be applied in the large-scale dataset (Op1.7M).

- cons
1. Reformulation that modifying the binary importance vector y as having a float value to become PageRank vector v is incremental.

2. A more explanation is needed on how this method can be processed in parallel and why other methods can not. P matrix computed on the large-scale dataset must be very large. How can this matrix be divided into multiple chunks?

In L112, what does it mean "inherently sequential" for other baselines?


---------------------------------------------------------------------------------------------
After reading authors' responses and other reveiwers' comments, I raise my rating to "lean to accept". My concerns are well addressed.
limitations_and_societal_impact: As I mentioned, my main concern is that its technical contribution is very limited. Other than that, the impact of this work on large-scale object discovery is quite satisfactory.
review_title: null

Meta-review: The formulation of unsupervised object detection as a PageRank problem is neat, and allows to scale up to significantly larger datasets.  
The paper is accepted, but authors are encouraged to better motivate the use of supervised features (and/or highlight the experiments with self-supervised features more).

Decision: Accept (Poster)