Large-Scale Unsupervised Object Discovery
Authors: Huy V. Vo
Elena Sizikova
Cordelia Schmid
Patrick Perez
Jean Ponce
Venue: NeurIPS 2021 Poster (2021)
Keywords: large-scale
unsupervised
object discovery
ranking
distributed
parallel computation
graph centrality

Abstract: Existing approaches to unsupervised object discovery (UOD) do not scale up to large datasets without approximations that compromise their performance. We propose a novel formulation of UOD as a ranking problem, amenable to the arsenal of distributed methods available for eigenvalue problems and link analysis. Through the use of self-supervised features, we also demonstrate the first  effective fully unsupervised pipeline for UOD. Extensive experiments on COCO~\cite{Lin2014cocodataset} and OpenImages~\cite{openimages} show that, in the single-object discovery setting where a single prominent object is sought in each image, the proposed LOD (Large-scale Object Discovery) approach is on par with, or better than the state of the art for medium-scale datasets (up to 120K images), and over 37\% better than the only other algorithms capable of scaling up to 1.7M images. In the multi-object discovery setting where multiple objects are sought in each image, the proposed LOD is over 14\% better in average precision (AP) than all other methods for datasets ranging from 20K to 1.7M images. Using self-supervised features, we also show that the proposed method obtains state-of-the-art UOD performance on OpenImages.

Large-Scale Unsupervised Object Discovery
Huy V. Vo
Elena Sizikova'
Cordelia Schmid'
Patrick Pérez²
Jean Ponce! 1.
INRIA, Département d' d'informatique de I'ENS, ENS, CNRS, PSL University, Paris, France *Center for Data Science, New York University
a
{van-huy vo, cordelia.
jean. jean.ponce) ponce)einria..fr es5223dnyu. edu Sbbrick.perezdvales.
Abstract
Existing approaches unsupervised object discovery (UOD) do not scale up large datasets without approximations that compromise their performance. We propose novel formulation of UOD as ranking problem, amenable arsenal of distributed methods available for eigenvalue problems and link analysis. Through the use of self self-super features, also demonstrate the first effective fully unsupervised pipeline for UOD. Extensive experiments on COCO [42] and OpenImages [35] show that, in the single-object discovery setting where single prominent object is sought in each image, the proposed LOD (Large-scale Object Discovery) approach is on par with, or better than the state of the for medium- scale datasets (up 120K images), and over 37% better than the only other algorithms capable of scaling up to 1.7M images. In the multi-object discovery setting where multiple objects are sought in each image. the proposed LOD is over 14% better in average precision (AP) than all other methods for datasets ranging from 20K to 1.7M images. Using self- supervvee features, also show that the proposed method obtains sfate-of-the-art UOD performance on Openlmages'.
the
Figure 1: Sample UOD results obtained by LOD on the OpenImages dataset [35] which contains 1.7M images. Ground-truth boxes are shown in yellow, and predictions in red. Best viewed in color.
1 Introduction
This paper addresses the problem of identifying prominent objects in large image collections without manual annotations, process known unsupervised object discovery (UOD). Early approaches to UOD focused mostly on finding clusters of images featuring objects of the same category [22, 58, 61, 62, 64, 69]. Some of them [58, 61, 62] also output object locations in images, but their evaluations are limited to small datasets with distinctive object classes. More recent techniques [8, 66, 67] focus on the discovery of image links and individual object locations within much more diverse image collections. They typically rely on combinatorial optimization to select objects, or rather, object bounding boxes, among thousands of candidate region proposals [46, 65, 67, 83) given similarity scores computed for pairs of proposals associated with different images. Although these techniques achieve promising results, their computational cost and inherently sequential nature limit the size of the dataset they can be applied to. Attempts to scale up the Sate-of-the-ann approach [67] by reducing the search space size have revealed that this compromises its ability to discover multiple objects in
Our code is publicly available at httths:://gthhhhh httt:::://ggtuu..../////rrro/ com/huyvvo/LOO..
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

each image. Other approaches to UOD focus on learning image representations by decomposing images into objects [5, 12, 23, 43, 47]. These techniques do not scale up (yet) to large natural image collections, and focus mostly on small datasets containing simple shapes in constrained environments.
Table 1: Large-scale object discovery performance and comparison to the state of the art on COCO [42] (C120K), OpenImages [35] (Op1.7M) and their respective subsets C20K and Op50K, in three standard metrics. Using VGG16 features [60]. the proposed method LOD achieves top performance in both single and multi-object discovery, and scales better to 1.7M images in 1p1.7M than the previous state of the art [67]. When running with self-supervised features (L.OD Self [18] 18); it yields the hest results on Op1.7M, showing the first effective fully unsupervised pipeline for UOD. See Sec. 4 for more details.
Single-ohject
Multi-ohject
Method
CorLoc
AP50
AP@' [5:95]]
C20K
C120K
Op50K
Opl.7M
C120K
Op50K
OpI.7M
C20K
C120K
Op50K
OpI.7M
EB [83]
28.8
29.1
32.7
32.8
4.86
4.91
5.46
5.49
1.41
1.43
1.53
1,53
Wei [71]
38.2
38.3
34.8
34.8
2.41
2.44
1.86
1.86
0.73
0.74
0.6
0.6
Kim [32]
35.1
34.8
37.0
3.93
4.13
0,96
0.98
Vo [67]
48.5
48.5
48.0
47.8
5.18
5.03
4.98
4.88
1.62
1.6
1.58
1.57
Ours (LOD+Self (18)
41.1
42.4
49.5
49.4
4.56
4.90
6.37
6.28
1.29
1.37
1.87
1.86
Ours (LOD)
48.5
48.6
48.1
47.7
6.63
6.64
6.46
6,28
1.98
2.0
1.88
1.83
is natural to cast unsupervised object discovery (UOD) as the task of finding repetitive visual patterns in image collections. Recent approaches (e.g., [66, 67J) to UOD formulate it as combinatorial optimization problem in a graph of images, selecting simultaneously image pairs that contain similar objects and region proposals that correspond to objects. with the corresponding computational limitations. The motivation behind our work is to formulate UOD as a simpler graph-theoreee theoretical problem with a more efficient solution, where objects correspond to well-connected nodes in graph whose nodes are region proposals (instead of images in [66, 67],. and edges are weighted by region similarity and objectness. In this scenario, finding object-proposal nodes is now ranking problem where the goal is to rank the nodes based on how well they are connected in the graph. From another perspective, ranking rather natural modelization choice for UOD in our context, discovering objects means finding the most object-like regions in a set of initial region proposals which naturally amounts to ranking them according to their "objectness". As result, large array of methods available for eigenvalue problems and link analysis [48] can be applied to solve UOD on much larger datasets than previously possible (Fig. 1). We consider three variants of this approach: the first one re-defines the UOD objective [66, 67] as an eigenvalue problem on the graph of region proposals, the second variant explores the applicability of PageRank [4, 48) for UOD, and the final variant combines the other two into hybrid algorithm, dubbed LOD (for large-scale object discovery), which uses the solution of the eigenvalue problem to personalize PageRank. LOD offers a fast, distributed solution to object discovery on very large datasets. We show in Sec. 4.1 and Table I that its performance is comparable or better than the state of the art in the single object discovery setting for datasets of up to 120K images, and over 37% better than the only algorithms we aware of that can handle up to 1.7M images. In the multi-object discovery setting, LOD significantly outperforms all existing techniques on datasets from 20K to 1.7M images. While LOD does not explicitly address discovering relationships between images (c.g., grouping images into classes), we demonstrate that categories can be discovered so far all use supervised region proposals and/or features. We also demonstrate for the first time in Sec. 4.1 that self-super features can give good UOD performance. Our main contributions can be summarized as follows:
post-processing step (see Sec. 4.2). The best performing approaches to UOD
We propose new formulation of UOD as ranking problem, allowing the application of parallel and distributed link analysis methods [4, 48).
We scale UOD up to datasets 87 times larger than those considered in the previous state of the art [67]. Our novel LOD algorithm outperforms others on medium-size datasets by up to 32%.
We propose to use self-supervised features for UOD and show that LOD, combined with these features, offers a viable UOD pipeline without any supervision whatsoever.
We conduct extensive experiments the COCO [42] and Openlmages [35] datasets to empirically validate our method. We also demonstrate applications of our approach to object category discovery and retrieval, outperforming other existing unsupervised baselines on both tasks by large margin.
2

---

2 Problem statement and related work
2.1 Problem statement
Consider collection of n images, each equipped with a set region proposals [66, 67]. For the sake of simplicity, we assume in this presentation that all images have exactly region proposals. We wish to find which ones of these correspond to objects, and link images that contain similar objects, without any information other than how similar pairs of proposals are. This problem is known as unsupervised object discovery (UOD) and can be formulated as an optimization problem [67] over a graph where images are represented as nodes. Let Epg E {0, 1 for p,g q = 1, ..... n be a set of binary variables indicating if two images are connected in the graph, with Epg I when images p and q share similar visual content. Similarly, let = E {0,1] for p = 1, 2.2..... n and k = 1.2.....! be indicator variables such that 2 when region proposal & of image p is an object-like region in image p that is similar to object-like region in one of the neighbors of image p. Let also xp be (a....... "²)"" )T be the
matrix whose rows are Zp for p 1.2.................... ..... n and e be the binary adjacency matrix of the image graph. Then, the object discovery problem can be formulated as a combinatorial maximization problem:
a
max 2y.
Σ
Σ (p)(p)
T Spoiig Ep
S.L. Σ
o and Σ k=1
Cpg ST VISpSn, n, (C)
qpP
where Spg E RR is a matrix whose entry Spg 2 0 measures the similarity between region & of image p and region E of image q as well as the saliency of the respective regions, N (p))) is a set of potential high-similarity neighbors of image p, and and are predefined constants corresponding to the maximum number of objects in an image and the maximum number of its neighbors, respectively. Previous approaches [66, 67] to UOD solve convex relaxation of (C) in the dual domain and/or use coordccooe ascent on its variables I and e. The similarity scores Syke are typically computed using the Probabilistic Hough Matching (PHM) algorithm from [8], which combines local appearance and global geometric consistency constraints to compare pairs of regions. A high PHM score between a pair of proposals is an indicator of whether the corresponding two proposals may correspond to a common foreground object. We follow this tradition and also use PHM scores (Sec. 4).
pg
The objective of UOD as formulated in (C) is to find both the objects (variables x²)) and the edges linking the images that contain them (variables 6pg). Its combinatorial nature makes it hard to scale up to large values of n and [67] uses block-coordinate ascent algorithm (C), updating variables and alternatively to optimize the objective. It attempts to scale up (C) with a drastic approximation, running on parts of the image collection reduce only 50 before running on the entire dataset. However, using significantly reduced sets of region proposals hinders its ability to discover multiple objects (Table 1). Moreover, this algorithm is inherently sequential. According to [66], in each iteration of optimizing x, an index i is chosen and x; is updated while e and all 2j with j & i are kept fixed. The update of z; depends on the updated values of other xy if 2, is updated before ri. This is crucial to guarantee that the objective always increases. If all x; are updated in parallel, there no guarantee that the objective would increase. Consequently, this process is not parallelizable, preventing the algorithm from scaling up to datasets with millions of images. We therefore drop the second objective of UOD, and rely only on fully connected, weighted graph of proposals where edge weights encode proposals' similarity (edge weights can be zeros, see Sec. 3). In turn, we can reformulate UOD as a ranking problem [4, 30, 34, 36, 51], amenable to the panoply of large-scale distributed tools available for eigenvalue problems and link analysis. We consider two different ranking formulations: the first (Q) tackles a quadratic optimization problem, and the second (P) is based on the well-known PageRank algorithm [4, 48]. We combine these two approaches into a joint formulation (LOD) that gives the best results on large-scale datasets. See Sections 3 and 4 for details.
2.2 Related work
Unsupervised object discovery. Early works on unsupervised object discovery focused on finding groups of images depicting objects of the same categories, employing probabilistic models [58, 61, 69], non-negative matrix factorization (NMF) [62] or clustering techniques [22], see [64] for a survey. In addition to finding image groups, some of these approaches, e.g., multiple instance learning (MIL) [82), graph mining [75]. contour matching [39] and topic modeling [58, 61] J. also output object locations, but focus on smaller datasets with only a handful of distinctive object classes. Saliency detection [80] is related to UOD, but seeks to generate a per-pixel map of saliency scores, while UOD attempts to find bounding boxes around objects in each image without supervision. Object discovery
3

---

in large real-world image collections remains challenging due to a high degree of intra-class variation, occlusion, background clutter and appearance of multiple object categories in one image. For this challenging setting, [8] proposes an iterative algorithm which alternates between retrieving image neighbors and localizing salient regions. Based on this approach, [66] is the first to formulate UOD as the optimization problem (C), finding first an approximate solution to a continuous relaxation, then applying block-coordinate ascent to find the solution of the original problem. The first step involves solving max-flow problem [I] exactly, which is too costly for medium- to large-scale datasets. The datasets have scaled up with successive approaches, from about 3,500 images for [8, 66] to 20,000 for [67], an extension of [66] using two-stage approach to UOD and new approach to region proposal design. However, these works are inherently sequential and difficult to scale further. Additionally, [67] operates reduced sets of region proposals containing only tens of regions, compromising its ability to discover multiple objects (Table 1). In contrast, our proposed approach considers all region proposals, is parallelizable and can be implemented in distributed way. Thus, it scales well to very large datasets without compromising performance. Indeed, we demonstrate effective UOD in challenging datasets with up to 1.7 million images (Fig. 1).
Heakky-supervised object localization and image co-localization. These problems are related to UOD but take advantage of image-level labels. Weakly-superrvie object localization (WSOL) considers scenarios where the input dataset contains image-level labels [9]. Most recent WSOL methods localize objects using saliency maps obtained from convolutional features in neural features, various strategies
network [7, 59, 81]. Since networks tend to learn dategory-ddscriminatee for improving the quality of features for localization have been proposed [2, 10, 76-79]. Co- localization is another line of work where all input images are assumed to contain at least one instance of single object category. [63] uses discriminative clustering [28] for co-localization in noisy image sets and [29] extends this work to the video setting. [41] learns to co-localize objects by learning sparse confidence distributions, mimicking behaviors of supervised detectors. [70] and [71] observe that activation maps generated from CNN features contain information about object locations. They propose cluster locations in the images into background and foreground using PCA and return the tight bounding box around the foreground pixels as an object. Since [71] can deal with large-scale datasets and can be easily adapted to UOD, we use it as baseline in our experiments.
Ranking applications in computer vision. The goal of ranking is to assign a global importance rating to each item in a set according to some criterion [48]. Many computer vision problems admit a ranking formulation, including image retrieval [6], object tracking [3], person re-identification [44], video summarization [72], co-segmentation [52] and saliency detection [40]. Several techniques specifically designed for large-scale ranking problems [34, 48] have been used to explore large datasets of images [27] and shapes [16]. PageRank- based approaches in particular have been popular [27, 49, 56] due to their scalability. [31] proposed an algorithm for object discovery that combines appearance and geometric consistency with PageRank-based link analysis for category discovery. However, it does not scale beyond 600 images. A more scalable follow-up work by [32] discovers regions of interest (Rols) from images with successive applications of PageRank. This algorithm includes two main steps. The first one attempts to find object representatives (hubs) from the current Rols of all images using PageRank. PageRank is then utilized again in the second step to analyze the links between regions in each image and the hubs, this time to update the Rols of the images. Finally, good Rols are found by repeating these two steps until convergence. We compare method to this technique in Sec. 4.1.
3 Proposed approach
3.1 Quadratic formulation
Let us represent region proposals by graph G with N = nr nodes, where is the number of images and r is the number of proposals in each image. Each node corresponds to a proposal, and any two nodes (p. k) and (g. f). corresponding to proposals and of images p and q, respectively, are linked by an edge with weight Ské G is represented by an N N symmetric adjacency matrix W. consisting of r x r blocks Spn for g.g = 1,... nT; Syn is defined in Sec. 2.1 and is computed via PHM algorithm [8] if p # q, and the diagonal blocks are taken to be zero since only inter-image region similarity matters in our setting. Let yı 2 0 denote some measure of importance that we want to estimate for node i and set y = (y1. yN )T. Define the support of node given y as Zy (2) E, Wiyy, so that taking 2y = (2, (1). By (N))T we have zn = Wy. Intuitively, given y. (i) quantifies how well i is connected to (or "supported by")) the rest of the nodes j in the graph,

---

taking into account the similarity Wiy between and j as well as the importance yj of that node. We would like find the importance scores that rank the nodes as well as possible, so that the order corresponds to their amount of support. As shown by the following lemma, it turns out that this "chicken-and-ege" problem admits a simple solution.
Lemma 1. Suppose W is irreducible (i.e., represents a strongly connected graph G). The solution y² of the quadratic optimization problem:
y argmax e't
51,20
is the unique unit, non-negative eigenvector of W associated with its largest eigenvalue.
This is a classic result and can be proved using Perron- Frobenius theorem [15, 50]. We include the complete proof in the supplemental material. In our context. W is not, in general, irreducible (i.e., for all pairs (i.j), there exists m 2 1 such that (i.j) > 0) since some proposal similarities may be zero. Reminiscent of PageRank [48], we add a small term yee? /N to W, with being the vector with all entries equal to 1 in R-V and 7 = 10-2, deliberately chosen small so that the added term does not influence the similarity score much, make W irreducible. This term ensures that the resulting ranking is unique and serves the same purpose as the similar term in PageRank. Note: since y" associated with W's largest eigenvalue X², which is positive according the Perron-Frobenius theorem, we have X-y" = Wyy Ey.. Hence, the importance score v of each node is, up to a positive constant, equal to its support, and can thus be used rank the nodes desired. Notice that (C) and (Q) are closely related problems when the graph of images in (C) is assumed to be complete. In this case, (C) can be written as max, (0.1)
x x Wa, s.t., for all p from 1 to n. Ex=1 Fr(p-1)+t S v. Here, we stack 24 (i - ....., n) into a vector æ. (Q) can thus be seen
continuous relaxation of (C) where the binary variables are replaced by continuous ones, and the linear constraints attaching the proposals to their source images are dropped. The order induced by the dominant eigenvector y of W on the nodes of G is reminiscent of the PageRank approach [4, 48] to link analysis. This remark leads to a second approach to UOD through ranking, discussed next.
3.2 PageRank formulation
When defining PageRank, [48] does not start from optimization problem like (Q), but directly formulates ranking as an eigenvalue problem. Following [37], let A denote the transition matrix of the graph associated with Markov chain, such that a.y 2 0 is the probability of moving from node to node i. In our context, A can be taken as WDD1 where D is the diagonal matrix with D,j = Σ. Waz. By definition [4, 48), the PageRank vector e of the matrix of the matrix P. associated with its largest (unit) eigenvalue, where P is defined as:
the unique non-negative eigenvector v
(P) where 3 is a damping factor. Here, u, the so-called personalized vector, is an element of I such that e u 1. As noted earlier, the second term ensures that P irreducible, so that, by the Perron- Frobenius theorem, the eigenvector 2 O is unique [38]. The vector u is typically taken equal to e/N, but can also be used to "personalize" the ranking by attaching more importance certain nodes. This leads to the hybrid formulation proposed in the next section.
P= (1 3) + Bue",
(Q) and (P) are closely related, and the v vector can also be seen as the solution of a quadratic optimization problem [45]. Besides this formal similarity, the goals of the two formulations are also similar. Quoting [48], "a page has a high rank (according to PageRank) if the sum of the ranks of its backlinks is high". The solution of both (Q) and (P), eigenvector associated with the largest eigenvalue, provides ranking based on the support function and can be found with the power iteration algorithm [68]. This algorithm involves only matrix-vector multiplications and can be implemented efficiently in distributed way.
3.3 Using (Q) to personalize PageRank
The above discussion suggests combining the two approaches. We thus propose to use the maximizer of (Q) generate the personalized vector for (P). (Q) and (P) are two different optimization problems for ranking region proposals, and combining them may help improve the final performance. Intuitively, region proposals with high scores given by (Q) are reliable and we should be able to rank the "objectness" of other regions more accurately based on the "feedback" of these top-scoring proposals. We compute the personalized vector from the solution of (Q) as follows. Given a factor a, the top region in each image is chosen as candidates, then the top a percent of regions amongst these candidates are selected. Since only regions that have a high probability of being correct are beneficial, we choose a sufficiently small (see Sec. 4) to select only the most likely correct regions.
5

---

Given the set of selected regions, the personalized vector u is the L1 noromaale indicator vector with u, = 1/K K where K is the total number of selected regions proposal is selected and u, = otherwise. We set the initialization up of the power iteration algorithm to u to further bias (P) toward reliable regions found by (Q). In what follows, we refer to this hybrid algorithm as Large-Scale Object Discovery (LOD).
4 Experimental analysis
Datasets. We consider two large public datasets: C120K, a combination of all images in the training and validation sets of the COCO 2014 dataset [42], except those contain only "crowd" objects, with approximately 120,000 images depicting 80 object classes and OpenImages (Op1.7M) [35], the largest dataset ever evaluated for UOD far, with 1.7 million images. The latter dataset is 87 times the size of the previous largest dataset evaluated by the state-of of-te--f-the-arr UOD method [67]. We resize all images in this dataset that their largest side does not exceed 512 pixels. To facilitate ablation studies and comparisons, we also evaluate our methods on C20K, a subset of C120K containing 19,817 images used by [67] and Op50K, a subset of 1p1.7M containing 50,000 images.
Implementation details. We use the proposal generation method of [67] since it gives the best object discovery performance among the unsupervised region proposal extraction methods [67]. We use VGG16 [60], trained with and without image class labels (Sec. 4.1) I) on the ImageNet [1 dataset, to both generate (with [67]) and represent (extracting with RoiPool [20]) proposals. We have also experimented with VGG19 [60] and 0e [25], but found they give worse performance, possibly because they are more discriminative and less helpful in localizing entire objects. We compute the similarity score between proposals with the PHM algorithm [8] similar to prior work [8, 66, 67]. For large datasets, computing all score matrices Spg is intractable. In this case, we only compute the similarity scores for the 100 nearest neighbors of each image, computed based on the Euclidean distance between image features from the fcó layer. For optimization, we choose and a = 10% in LOD. To select objects from ranked proposals in an image, we choose proposal as an object if it has the highest score the image or the intersection over union (IoU) between and each of the previously selected object regions is at most 0.3. When using proposals from [67], which are divided into disjoint groups, we additionally impose that the newly chosen region must be in a group different from the groups of the previously selected objects. See supplemental material for discussions on LOD's s sensitivity to hyper-parameters and more implementation details.
10-4 in (P)
Metrics and evaluation settings. We consider two settings: single- and the multi-object discovery. In the single-object setting. we return m region per image, which is the region most likely to be an object. In the multi-object setting, we return up to M regions per image, where M is the maximum number of objects in any image in the dataset. Following [43], we assume M known during evaluation. In a real application, one could use a rough "budget estimate" of the upper bound on how many objects per image one may try to detect. Measuring performance of UOD always difficult task due to the ambiguity of the notion of an object in unsupervised setting: object parts vs. objects, individual objects vs. crowd objects, etc. Following previous works [8, 66, 67], we consider the annotated bounding boxes in the tested datasets as the only correct objects and use them to evaluate our methods. We evaluate UOD results according to the following metrics:
1. Correct localization score (CorLoc) percentage of images correctly localized, i.c., where the ToU score between one of the ground-truth regions and the top predicted region is at least a = 0.5. Note that it is equivalent to precision of returned regions. This metric is commonly used to evaluate single-object discovery [8, 66, 67].
single-
2. Average Precision (AP) - the area under the precision-recal curve with precision and recall computed at each value of from 1 to M. A ground-truth object is considered discovered if its intersection with any predicted region is at least a. This metric is used to evaluate multi-object discovery. We report AP50 where a = 50 and AP AP@[50) [50:95], where we average AP at 10 equally spaced values of a from 0.5 to 0.95. Note that AP is different from [67]'s metrics for multi-object discovery, which is the object recall (detection rate) at predefined value of This metric depends on the number of selected regions per image m while our metrics do not. In contrast, AP is a standard metric in object detection-like tasks [19-21, 24, 54, 55, 57]. Note that since the precision decreases significantly with increasing m. AP appears much smaller than CorLoc.
4.1 Large-scale object discovery
In this section, we compare our methods to the state of the art in UOD [32, 67, 71]. We also compare to Edgeboxes (EB) [83], an unsupervised method which outputs regions with importance score.

---

EB is baseline of the type of information bounding boxes alone can provide in our setting. For a fair comparison, we have re-implemented Kim [32] using supervised VGG16 features [60] and proposals from Vo [67]. For Wei [71], we modified their public code, taking bounding boxes around more than one connected component of positive locations from the image indicator matrix to return more regions. For other methods, we explicitly evaluate their public code.
Quantitative evaluation. We evaluate baselines and the proposed method on C20K, C120K, Op50K and Op1.7M in Table 1. Since tffe--of-hhhar--- approaches to UOD report results using supervised features [60], we have used these features as well in our comparisons. We additionally report LOD's performance with self-supervised features [18] on these datasets. Overall, LOD obtains of the-art object discovery performance all settings and datasets. Using VGG16 features [60], outperforms Kim [32], Wei [71] and EB [83] by large margins: by 26% in single-object discovery and by 14% in multi-object discovery settings. In comparison to Vo [67], LOD performs similarly in the single-object setting, but outperforms Vo [67] by at least 19% in the multi-object setting. This is likely due to the fact that our proposed LOD method considers the full proposal graph and does not reduce the number of region proposals (see supplementary material). is also noteworthy that LOD scales better than [67] and runs much faster on the large datasets C120K and Op1.7M (Fig. 2). On the Op1.7M dataset, it takes 53.7 hours to run while Vo [67] needs more than month to finish. It is also interesting that self-suuprvised features [18] works better with LOD than supervised ones [60], yielding the state of the art performance on Op1.7M dataset.
Run time. Next, we compare scalability and run times of the proposed technique and of the baselines. All tested methods ([32, 67, 71, 83] and LOD) use similar pre-processing steps: feature extraction, proposal generation and similarity compu- tation, which are done separately across all images. This is followed in [32. 67] and LOD by optimization stage. The optimization step in [67] is inherently sequential, but [32] and
2004
1000
20
25 [S]
LOD can be parallelized. In our experiments, we use 4,000
Actual rum Time (hrs)
Wia [2])
Kin
CPUs for preprocessing for all methods, and 48 CPUs for the
optimization step in [32] and LOD, the maximum possible with
Clan [AAUI
the MatLab parallel toolbox used in our implementation. The
timings in Fig. include both pre-processing and optimization,
100
200
when the latter is used. It can be seen that [32, 71, 83] and LOD scale nearly linearly with the number of images, while [67] exhibits superlinear pattern. Note that [83] and [71] are 70 times faster than LOD, but at a significant decrease in perfor- mance. These methods are not initially designed for object discovery, but serve as good, scalable baselines. Compared to previous top UOD methods, LOD runs at least 2.8 times faster than [32] on all datasets, at least times faster than [67] on datasets between 120K and 1.7 million images. Here, we evaluate only the parallel implementation typical for modern computing setups. In serial implementation, compute times will be similar between top performing UOD methods [32, 67] and LOD, but none of the methods would be able to run on 1.7M images in reasonable time. Note also that additional computational resources can further speed up processing for both Kim [32] and LOD.
Number of images (in thousands)
Figure 2: Comparison of run time as a function of input images. LOD achieves significant improvement in performance and/or savings in run time compared to previous works. EB [83] and Wei [71] are linear in the number of images but their run time are very small compared to other methods and look flat in the figure.
Qualitative evaluation. We present sample qualitative multi-object discovery results of LOD on C120K and 0p1.7M in Fig. (additional OpI.7M results are presented in Fig. 1). LOD discovers both the larger objects (people in the first and sixth images, food items in the second and third images) and the smaller ones (tennis balls and racquet in the first image). It may fail of course, and two typical failure cases are shown on the right of Fig. 3. In the first case, objects are too small and in the second case, LOD returns object parts instead of entire objects. Note that there is some ambiguity in what parts of the image are labelled ground truth objects. For example, the leaves in the bottom left image are not labelled as objects, while the flowers are.
Self-supervised features vs. supervised features. LOD and all of the optimization-bul based base- lines [32. 67, 71] rely on a VGG [60]- based classifier trained on ImageNet [11]. In this section, we investigate their performance when the underlying classifier is trained with (Sup) and without (Self) image labels, f.e., in a self-supervised fashion. To obtain self-supervised features, we use a VGG16 model trained with OBoW [18), a recent method which yields state-of-the-an performance in
7

---

Figure 3: Examples where our method (I.O)) succeeds (left) and fails (right) to discover ground-truth objects in the Op1.7M dataset [35]. Ground-truth objects are in yellow, our predictions are in red. Best viewed in color.
object detection after fine-tuning. This model is tested for both the proposal generation and similarity computation steps in optimization-bused methods. The results of several variants of each optimization method, depending on the proposal generation algorithm (EB [83], [67]+Self or [67]+ and the region proposal representation (Self or Sup) are presented in Table (left). [67] generates proposals from local maxima of the image's 's saliency map obtained with CNN features. To evaluate [67]+Self and [67]+Sup for UOD, we assign each proposal score equal the saliency of the local maximum it is generated from. If two regions have the same score, the larger one is ranked higher so that entire objects instead of object parts selected. Finally, when EB [83] proposals are used for [67] and LOD, we multiply their features with their EB scores before computing their similarity.
In general, variants with supervised features perform better in UOD than those with self- culf-supervised features, except for Wei [71] and LOD in single-object discovery on Op50K. Kim [32] is the most dependent supervised features. Its performance drops by at least 63% when switching to self- supervised features. It is also noteworthy that the performance of Vo [67] and LOD with supervised and self-supervised features Op50K much closer than C20K. This is likely due to the fact that the supervised features [60] are trained on the 1000 ImageNet object classes which contain all of the COCO classes and thus offer a stronger bias toward these classes than the self-supervised features. Using self-supervised features, variants of LOD are the best performer in both single-object discovery (with Vo [67]+Self proposals) and multi-object discovery (with EB proposals). They yield reasonable results on both datasets compared to variants with supervised features. In particular, self supervirdd object proposals [67] and self supe-super features, combined with LOD, give the best results of all tested methods on Op50K in singlc-object discovery. These results show that LOD combined with supervieed features is viable option for UOD without any supervision whatsoever.
Comparing ranking formulations. We compare the UOD performance of Q P and LOD with different proposals and features in Table (right). It can be seen that LOD outperforms Q and P in almost all datasets and settings. These results confirm the merit of our proposed method, using Q's solution to personalize PageRank.
4.2 Category discovery
Contrary to [8, 66, 67], our work aims specifically at localizing objects in images and omits the discovery of the image graph structure, i.e., identifying image pairs that contain objects of the same category. However, objects localized by our methods can be used to perform this task in post-processing step. To this end, we define similarity between two images the maximum similarity between pairs of selected proposals. Similarity is measured using cosine distance between features extracted from fcó layer. We compare LOD [8. 66, 67] in image neighbor retrieval task on VOC_all all, subset of Pascal VOC2007 dataset [13] used as a benchmark in [8, 66, 67]. Similar to these works, we retrieve 10 nearest neighbors per image. Then, CorRet [8] (the average % of retrieved image neighbors that are actual neighbors in the ground-truth image graph over all images) used to compare different methods. Results are shown in Fig. 4. LOD outperforms [8, 66, 67]. This is surprising since the other methods are specifically formulated to discover image neighbors, while our method not. This result highlights that our localized objects can be potentially beneficial for other tasks. To go further, we cluster images into categories using proposals selected by our algorithms. Imposing that images are represented by their proposal with the highest score, we perform this task by applying K-means the La normalizee feb features representing these proposals. We
8

---

Table 2: Left: UOD performance with supervised [60] (Sup) and self-supervised features [18] (Self) C20K Op50K datasets. Region proposals are generated by methods from [83] and Vo [67] with different types of features. LOD with sule--ud features yields reasonable results compared to supervised features. Variants of our proposed method LOD yield state-of the-----t-t--ttt-- performance in all settings. Right: A comparison of different ranking methods for UOD. LOD is better than Q and P in most of the cases.
Single-object
Mukriobjject
Opt.
Proposal
Fenture
Corl.ne
AP50
AP@ [50:55]
C20K
Op50K
C20K
Op50K
C20K
Op50K
Singlo-objeet
Multi-abject
None
[67+ Sup
EB [83]
None
29.7
28.8
39.8
32.7
2.47
4.86
3.72
5,46
0.61
1.41
1.53
1.0
Opt.
Proposal
Feature
CorLonc
AP50
(S09950:95]
23.6
38.1
4.07
1.39
C20K
Op50K
C20K
Op50K
C20K
Op50K
Wei (71]
None
Self
Sup
37.9
58.2
34.8
42.4
2.41
2.53
3.13
1.86
0.69
0.73
0.9
0.6
Q
[67]
(83)
Self
Sup
36.0
32.8
38.7
41.1
48.9
4.38
4.15
5.72
6.43
6.39
6.49
1.17
1.47
1.67
1.84
1.7
Kim [32)
[67]+ScIf
Sup
EB 1831
Sclf
Sup
Self
Sup
35.1
15.6
4.7
5.5
20.2
4.6
0.13
3.93
1.96
0.29
0.79
2.56
0.13
0.36
0.96
0.02
0.05
0.15
0.98
0.47
[67]+Sup
[67]
EB (83)
Self
41.2
43.8
38.9
35.5
41.3
49.5
47.5
39.7
6.21
6.51
4.91
4.38
6.73
6,66
6.99
1.74
1.76
1.34
1.24
1,88
1.81
1,75
1.86
EB [83]
Self
35.6
43.6
3.34
4.43
0.99
1.39
[67]+Sup
Sup
47.5
47.8
6.25
6.19
1.87
1.81
No [67]
[67]4Self
[67]+Sup
Self
Sup
Sup
57.8
40.2
48.5
44.0
48.1
5.18
2,65
4.0
4.98
4.19
4.47
0.82
1.21
1.58
1.41
1,45
LOD
[67]+Self
EB [83]
Self
Sup
35.5
41.1
38.9
41.3
49.5
4.56
6.52
5.87
7.01
6.37
1.29
1.76
1.57
1.86
1.76
1,87
LOD
EB [83]
Self
Sup
55.5
38.9
39.7
5:87
6.52
6.73
1.57
1.86
1.76
[67]+Sup
Sup
48.5
6.63
[67]48elf
Self
41.1
49.5
4.56
6.37
1.29
1.87
Sup
48.3
48.1
6.63
6.46
1.98
1.88
80
72.3
75-2
Table 3: Purity (1) of our clustering method compared to the state of the art in category discovery on the SIVAL dataset [53]. Following prior work, we perform the task on a partition of the dataset and report the average purity its parts as the final result. Results of other methods are from [75].
00-
Corlot
36.6
31.2
200
Datase/Method
Ours (LOD)
[75]
[82]
[14]
[73]
[74]
[31]
[33]
18
[77]
Ous (LDD)
Method
SIVALI
97.4
89.0
95.3
80.4
39.3
38.0
27.0
45.0
SIVAL2
99.0
93.2
54.0
71.7
40.0
33.3
35.3
33.3
SIVAL3
88.3
88.4
74.7
62.7
37.3
38.7
26.7
41.3
Figure 4: Comparison to prior work on the image neighbor re- trieval task (CorRet. 1).
SIVAL4
97.7
87.8
94.0
86.0
33.0
37.7
27.3
53.0
SIVAL5
94_3
92.7
75.3
70.3
35.3
37.7
25.0
48.3
Average
84.7
74.2
37.1
28.3
conduct experiments on the SIVAL [53] dataset, a popular benchmark for this task. This dataset consists of 25 object categories, each containing about 60 images. Following [82], we partition the 25 object classes into 5 groups, named SIVAL1 to SIVAL5, and use purity (average percentage of the dominant class in the clusters) an evaluation metric. Intuitively, purity measures the extent to which a cluster contains images of single dominant class. A comparison between our method and other popular object category discovery methods is given in Table 3. can be seen that our method outperforms the state of the art by significant margin, attaining an average purity of 95.3. It is also noteworthy that the performance drops 23.7 when the features of entire images are used instead of the representative top proposals. This finding shows that our performance gain is in great part due to the object localization performance of our method. Since individual images the SIVAL dataset [53] contain only one object, we conduct a similar experiment on the more challenging VOC_all [13] dataset. In this experiment, histogram computed for each cluster, showing the score of each ground-truth object category (a category score is the sum of contributions of all its images). An image contribution is computed as 1/nc, with is the number of object categories appearing in the image and is the number of images in the cluster. We then match the clusters to the ground-truth categories by solving a stable marriage problem with the Galc Sale-Shapley algorithm [17] using the preference orders induced by the histograms.
The confusion matrix generated by combining these histograms, revealing the correspondence between the clusters and the classes, is shown in Fig. 5. Our method is able to discover 17 categories (which are dominant in at least one cluster) out of 20 ground-trui undiscovered categories: sheep is dominated by similar class cow in cluster 10; sofa is dominated by co-occurring class chair in cluster 9; dinninglable suffers from being often largely occluded in images. Interestingly, it seems that our method might be used to discover pairs of categories that often appear together, for instance: bicycle and person, horse and person, motorbike and person (clusters 2, 13 and 14 have two corresponding dominating classes each). Quantitatively, using the top
categories. As for the three

---

extracted proposals from our method achieves a purity of 68.6 on this dataset, which is better than the purity of 61.8 obtained when features of entire images are used.
>100
0.35
92
0
0
0
0
0
0
5
36
0.3
0
0
0
1
0
0
O
0
0
0
0
0
0
0
6
0
0
0
0.2
39
TO
O
0
0
17
0
0
B
O
B8
O
O
O
2
0
0
39
O
0
0
10
0.1
11
50
O
0
0
0
O
0
0
7
0
0
0.05
19
O
O
4
3
50
0
41
20
40
60
class index
15
0
0
9
16
0
0
0
0
0
3
84
0
0
Figure 6: Performance of LOD by object cat- egory and category frequency (number of ob- ject occurrences of each category) on the C20K dataset. Results are reported with Average Pre- cision at a = 0.5 (AP50), higher numbers are better. Object categories are indexed in decreas- ing order category frequency. Performance of LOD is not well-correlated (correlation -0.09) with category frequency.
16
D
12
0
0
0
0
0
0
14
0
20
0
Figure 5: Confusion matrix revealing links hetween the object classes and the clusters found by (LOD) on VOC all.
4.3 Discussions
Without a formal definition of objects, casting objects as frequently appearing salient visual patterns natural. However, findings could be biased toward popular object classes and ignore rare classes in image collections that contain a long-tail distribution of object classes. To have an insight to this potential bias, we compute LOD's performance by object category on C20K dataset. Surprisingly, we have observed little correlation between the performance on an object class and its appearance frequency (the corresponding correlation is only -0.09, see Figure 6). A possible explanation is that even though we rank all regions in the image collection at once, we choose objects (based on the ranking) on the image level. Therefore, regions can selected as objects if they stand out more from the background and are better connected in the graph than other regions in the same image, even if they represent objects of a rare class.
Conclusion and future work
We have demonstrated novel formulation of unsupervised object discovery (UOD) ranking problem, allowing application of efficient and distributed algorithms used for link analysis and ranking problems. In particular, we have shown how to apply the personalized PageRank algorithm to derive a solution, and proposed a new technique based on eigenvector computation to identify the personalized vector in Pagerank. The proposed LOD algorithm naturally admits a distributed implementation and 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-ar technique [67], and outperforms (in single- and multi-object discovery) all existing algorithms capable of scaling to this size. In multi-object discovery, LOD better than all other methods on medium and large-scale datasets. State-of of-the-an solutions to UOD rely on supervised region proposals [8] or features [71, 67]. thus their output requires at least in part on some sort of supervision. We have proposed to combine LOD with self-supervised features, offering a solution to fully unsupervised object discovery. Finally, we have shown that LOD yields state-of-the-ard results in category discovery which is obtained as a post- post-processing step. A limitation of our method is that it works well only with VGG-based features which prevents it from benefiting from more powerful features [25, 26). Future work will be dedicated to investigating these features for LOD, Another interesting avenue for future research is to better discover smaller objects.
Effective solutions to UOD have the potential for great impact on existing visual classification, detection, and interpretation technology by harnessing the vast amounts of non-annotated image data available on the Internet today. In turn, the application of this technology has its known potential benefits (from natural human computer interfaces to X-ray image screening in medicine) and risks (from state-sponsore surveillance or military target acquisition). We believe that such concerns are ubiquitous in machine learning in general and computer vision in particular, and beyond the scope of this scientific presentation.
10

---

Acknowledgments and Disclosure of Funding
This work was supported in part by the Inria/NYU collaboration, the Louis Vuitton/ENS chair on artificial intelligence and the French government under management of Agence Nationale de la Recherche as part the "Investissements d' d'avenir" program, reference ANR 1NR199P31A-0001 (PRAIRIE 31A Institute). Elena Sizikova was supported by the Moore-Sloan Data Science Environment initiative (funded by Alfred P. Sloan Foundation and the Gordon and Betty Moore Foundation) through the NYU Center for Data Science. Huy V. Vo was supported in part by Valeo/Prairie CIFRE PhD Fellowship. We thank Spyros Gidaris for providing the VGG16 b-ased OBoW W model. Finally, we thank anonymous reviewers for their helpful suggestions and feedback for the paper.

---

References
[1] Francis Bach. Learning with submodular functions: A convex optimization perspective. Foundations and
Trends in Machine Learning. 2013.
[2] Kyungjune Baek. Minhyun Lee, and Hyunjung Shim. Psynet: Self-supervised approach to object localiza-
tion using point symmetric transformation. In AAAI, 2020.
[3] Yancheng Bai and Ming Tang. Robust tracking via weakly supervised ranking SVM. In CVPR, 2012.
[4] Sergey Brin and Lawrence Page. The anatomy of large-scale hypertextual web search. Computer Networks, 1998.
[5] Christopher Burgess, Loic Matthey, Nicholas Watters, Rishabh Kabra, Trina Higgins, Matt Botvinick, and Alexander Lerchner. Monet: Unsupervised scene decomposition and representation. voXiv:/901.11
2019.
[6] Fatih Cakir, Kun He, Xide Xia, Brian Kulis, and Stan Sclaroff. Deep metric learning to rank. In CVPR. 2019.
[7] Aditya Chattopadhay, Anirban Sarkar, Prantik Howlader, and Vineeth Balasubramanian. Grad-cam++:
Generalized gradient-based visual explanations for deep convolutional networks. In WACV, 2018. [8] Minsu Cho, Suha Kwak, Cordelia Schmid, and Jean Ponce. Unsupervised object discovery and localization in the wild: Part-based matching with bottom-up region proposals. In CVPR, 2015.
[9] Junsuk Choe, Seong Joon Oh, Seungho Lee. Sanghyuk Chun, Zeynep Akata, and Hyunjung Shim.
Evaluating weakly supervised object localization methods right. In CVPR. 2020.
[10] Junsuk Choe and Hyunjung Shim. Attention-bass dropout layer for weakly supervised object localization.
In CVPR, 2019.
[11] Jia Deng. Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei.
ImageNet: A Large-Scale
Hierarchical Image Database. In CVPR, 2009.
[12] Martin Engelcke, Adam Kosiorek, Oiwi Parker Jones, and Ingmar Posner. Genesis: Generative scene inference and sampling with object-centric latent representations. In ICLR, 2020.
[13] Mark Everingham, Luc Van Gool, Christopher KI Williams, John Winn, and Andrew Zisserman. The PASCAL visual object classes challenge 2007 (VOC2007) results, 2007.
[14] Jie Feng, Yichen Wei, Litian Tao, Chao Zhang. and Jian Sun. Salient object detection by composition. In
ICCV, 2011.
[15] Ferdinand G. Frobenius. Über matrizen aus nicht negativen elementen. 1912.
[16] Thomas Funkhouser, Patrick Min, Michael Kazhdan, Joyce Chen, Alex Halderman, David Dobkin, and David Jacobs. A search engine for 3D models. ACM Trans. on Graphics, 2003.
[17] David Gale and Lloyd Shapley. College admissions and the stability of marriage. American Mathematical Monthly, 1962.
[18] Spyros Gidaris, Aandrei Bursue, Gilles Puy, Nikos Komodakis, Matthicu Cord, and Patrick Pérez. Online
oo--oofiial-worrrree generation for unsupervised representation lcarning. In CVPR, 2021. [19] Spyros Gidaris and Nikos Komodakis. Object detection via a multi-region and semantic segmentation-awware
enn model. In ICCV, 2015,
[20] Ross Girshick. Fast R-CNN. In ICCV, 2015.
[21] Ross Girshick, Jeff Donahue, Trevor Darrell, and Jitendra Malik. Rich feature hierarchies for accurate
object detection and semantic segmentation. In CVPR, 2014.
[22] Kristen Grauman and Trevor Darrell. Unsupervised learning of categorics from sets of partially matching
image features. In CVPR, 2006.
[23] 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 ICML.
[24]
Kaiming He. Georgia Gkioxari. Piotr Dollar, and Ross Girshick. Mask R-CNN. In ICCV, 2017.
[25]
Kaiming He, Xiangyu Zhang. Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition.
In CVPR, 2016
[26] Gao Huang, Zhuang Liu, Laurens van der Maaten, and Kilian Q Weinberger. Densely connected
convolutional networks. In CVPR, 2017.
[27] Yushi Jing and Shumeet Baluja. Visualrank: Applying Pagerank to large-scale image search. IEEE Trans.
Pattern Anal. Machine Intell., 2008
[28]
Armand Joulin, Francis Bach, and Jean Ponce. Discriminative clustering for image co-segmentation. In
CVPR, 2010.
[29] Armand Joulin, Kevin Tang, and Li Fei-Fei. Efficient image and video co-localization with Frank- -Woffe algorithm. In ECCV, 2014.
[30]
Leo Katz. A new status index derived from sociometric analysis. Psychometrika, 18:39-43, 1953. Gunhee Kim, Christos Faloutsos, and Martial Hebert. Unsupervised modeling of object categorics using link analysis techniques. In CVPR, 2008.
[31]
[32]
Gunhee Kim and Antonio Torralba. Unsupervised detection of regions of interest using iterative link analysis. In NIPS, 2009.
[33]
Gunhee Kim and Eric P Xing. On multiple foreground cosegmentation. In CVPR, 2012.
[34]
Jon M Kleinberg. Authoritative sources in a hyperlinked environment. JACM, 1999.
[35] Ivan Krasin, Tom Duerig, Neil Alldrin, Vittorio Ferrari, Sami Abu-El El-Haija, Alina Kuznetsova, Hassan Rom, Jasper Uijlings. Stefan Popov. Andreas Veit, Serge Belongie, Victor Gomes, Abhinav Gupta. Chen
Sun, Gal Chechik, David Cai, Zheyun Feng, Dhyanesh Narayanan, and Kevin Murphy. Openimages: A
12

---

public dataset for large-scale multi-label and multi-class image classification. Dataset available from http:://giflub.com//pp compopeninages. 2017.
[36]
Endmund Landau. Zur relativen wertbemessung der turnierresultate. Deutsches Wochenschach, 11:366-
369, 1895.
[37]
Amy Langville and Carl Meyer. Deeper inside Pagerank. Internet Mathematics, 2004.
[38]
Amy Langville and Carl Meyer. Google's PageRank and beyond: The science of search engine rankings.
2011.
[39]
Yong Jae Lee and Kristen Grauman. Shape discovery from unlabeled image collections. In CVPR, 2009.
[40] Changyang Li. Yuchen Yuan, Weidong Cai, Yong Xia, and David Dagan Feng. Robust saliency detection
via regularized random walks ranking- In CVPR, 2015.
[41] Yao Li, Linqiao Liu, Chunhua Shen, and Anton den Hengel. Image co-localization by mimicking
good detector's ' confidence score distribution. In ECCV, 2016.
[42] Tsung-Yo Yi Lin, Michael Maire, Serge Belongie, James Hays, Pietro Perona, Deva Ramanan, Piotr Dollár, and Lawrence Zitmick. Microsoft COCO: common objects in context. In ECCV, 2014.
[43] Francesco Locatello. Dirk Weissenborn, Thomas Unterthiner, Aravindh Mahendran, Georg Heigold. Jakob Uszkoreit, Alexey Dosovitskiy, and Thomas Kipf. Object-centric learning with slot attention. In NeurlPS, 2020.
[44] Chen C. Loy, Chunxiao Liu, and Shaogang Gong. Person re-identification by manifold ranking. In ICIP, 2013.
[45] Michael W. Mahoney and Lorenzo Orecchia. Implementing regularization implicitly via approximate
eigenvector computation. 2010.
[46] Santiago Manen, Matthieu Guillaumin, and Lue Van Gool. Prime object proposals with randomized prim's 's algorithm. In ICCV, 2013. [47]
Tom Monnier, Elliot Vincent, Jean Ponce, and Mathicu Aubry. Unsupervised layered image decomposition into object prototypes. arXiv:2104. /4575, 2021,
[48] Lawrence Page, Sergey Brin, Rajeev Motwani, and Terry Winograd. The Pagerank citation ranking: Bringing order to the web. Technical report, Stanford InfoLab, 1999.
[49]
Shahram Payandeh and Eddie Chiu. Application modified Pagerank algorithm for anomaly detection in movements of older adults. IJTA, 2019.
[50]
Oskar Perron, Grundlagen für eine theorie des jacobischen kettenbruchalgoritmmus. 1907.
[51]
Gabriel Pinski and Francis Narin. Citation influence for journal aggregates of scientific publications:
Theory, with application to the literature of physics. Information Processing & Management, 12:297-312 312, 1976.
[52] Rong Quan. Junwei Han, Dingwen Zhang, and Feiping Nie. Object co-segmentation via graph optimized- flexible manifold ranking. In CVPR, 2016.
[53]
Rouhollah Rahmani, Sally A Goldman, Hui Zhang, John Krettek, and Jason E Fritts. Localized content- based image retrieval. IEEE Trans. Pattern Anal. Machine Intell., 2008
[54] Joseph Redmon, Santosh Divvala, Ross Girshick, and Ali Farhadi. You only look once: Unified, real-time object detection. In CVPR, 2016.
[55]
Joseph Redmon and Ali Farhadi. Yala9000: Better, faster, stronger. In CVPR, 2017.
[56]
Qinghua Ren and Renjie Hu. Saliency detection via pageank and local spline regression. Journal of Electronic Imaging, 2018
[57] Shaoqing Ren, Kaiming Hc, Ross Girshick, and Jian Sun. Faster R-CNN: Towards real-time object detection with region proposal networks. In NeuRIPS, 2015.
[58] Bryan Russell, William Freeman, Alexei Efros. Josef Sivic, and Andrew Zisserman. Using multiple weementatiinn segmentations to discover objects and their extent image collections. CVPR, 2006.
[59] Ramprasaath Selvaraju, Michael Cogswell, Abhishek Das, Ramakrishna Vedantam, Devi Parikh, and Dhruv Batra. Grad-Cam: Visual explanations from deep networks via gradient- localization. In ICCV, 2017.
[60] Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recogni-
tion. In ICLR, 2015,
[61]
Josef Sivic, Bryan Russell, Alexei Efros, Andrew Zisserman, and William Freeman. Discovering objects and their location in images. In ICCV. 2005.
[62] Jiayu Tang and Paul H Lewis. Non-negative matrix factorisation for object class discovery and image auto-annotation. In C/VR, 2008.
[63] Kevin Tang, Armand Joulin, and Li-jia Li. Co-localization in real-world images. In CVPR, 2014. Tinne Tuytelaars, Christoph Lampert, Matthew Blaschko, and Wray Buntine. Unsupervised object discovery: A comparison. Int. Journal on Computer Vision, 2010.
[64]
[65] Jasper Uijlings, Karin van de Sande, Theo Gevers, and Arnold Smeulders. Selective search for object recognition. Int. Journal on Computer Vision, 2013.
[66] Huy V. Vo. Francis Bach, Minsu Cho, Kai Han, Yann LeCun, Patrick Pérez, and Jean Ponce. Unsupervised
image matching and object discovery as optimization. CVPR, 2019.
[67] Huy V. Vo, Patrick Pérez. and Jean Ponce. Toward unsupervised, multi-object discovery in large-scale image collections. In ECCV, 2020.
[68] Richard von Mises and Hilda Pollaczek Pollaezek-Geiringerr Praktische verfahren der gleichungsauflsungg. ZAMM-
Journal of Applied Mathematics and Mechanics/Zeitschriff für Angewandte Mathematik und Mechanik,
1929.
13

---

[69]
Markus Weber, Max Welling, and Pietro Perona. Towards automatic discovery of object categories. In
CVPR, 2000.
[70]
Xiu-Shen Wei, Chen-Lin Zhang, Yao Li. Chen- Xie, Jianxin Wu, Chunhua Shen, and Zhi- -hu-Hua Zhou.
Deep descriptor transforming for image co-localization. In IJCAI, 2017.
[71]
Xiu-Shen Wei, Chen- Zhang, Jianxin Wu, Chunhua Shen, and Zhi-Hua Zhou. Unsupervised object
discovery and co-localization by deep descriptor transforming. Pattern Recegnition, 2019.
[72] Ting Yao, Tao Mci, and Yong Rui. Highlight detection with pairwise deep ranking for first-person vidco
summarization. In CVPR, 2016.
[73] Dan Zhang. Fei Wang, Luo Si, and Tao Li, Maximum margin multiple instance clustering with applications to image and text clustering. Transactions on Neural Networks, 2011.
[74] Min-L.nng Zhang and Zhi-Hua Zhou. Multi-instance clustering with applications to multi-instance predic-
tion. Applied Intelligence, 2009.
[75] Quanshi Zhang, Ying Nian Wu, and Song-Chun Zhu. Mining and-or graphs for graph matching and object
discovery. In ICCV, 2015.
[76] Runsheng Zhang. Yaping Huang, Mengyang Pu, Jian Zhang, Qingji Guan, Qi Zou, and Haibin Ling.
Mining objects: Fully unsupervised object discovery and localization from single image. IEEE Trans.
Image Processing. 2020.
[77] Xiaolin Zhang. Yunchao Wei, Jiashi Feng. Yi Yang, and Thomas S Huang. Adversarial complementary
learning for weakly supervised object localization. In CVPR, 2018.
[78] Xiaolin Zhang, Yunchao Wei, Guoliang Kang, Yi Yang, and Thomas Huang. Self-produced guidance for
seekly--upervised object localization. ECCV, 2018.
[79] Xiaolin Zhang. Yunchao Wei, and Yang. Inter image communication for weakly supervised localization.
In ECCV, 2020.
88]
Ting Zhao and Xianggian Wu. Pyramid feature attention network for saliency detection. CVPR. 2019. Bolci Zhou, Aditya Khosla, Agata Lapedriza, Aude Oliva, and Antonio Torralba. Learning deep features for discriminative localization. In CVPR, 2016.
[81]
[82]
Jun- Zhu, Jiajun Wu, Yan Xu, Eric Chang. and Zhuowen Tu. Unsupervised object class discovery via
saliency- multiple class learning. In CVPR, 2012.
[83]
Lawrence Zitnick and Piotr Dollár. Edge boxes: Locating object proposals from edges. In ECCV, 2014.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See Sec. 5
(c) Did you discuss any potential negative societal impacts of your work? [Yes] See Sec. 5
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as a URL)? [Yes] See supplemen- tal material.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See Sec. 4 and supplemental material.
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] See Sec. 4.1.
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes] See Sec. 4
(b) Did you mention the license of the assets? [Yes] See Sec. 4
(c) Did you include any new assets either the supplemental material or as URL? [Yes]
code
14

---

(d) Did you discuss whether and how consent was obtained from people whose data you' re using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
15


Reviews:
[{"review_id": "n3QpicMVjl0", "reviewer": "Reviewer_1AuG", "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. ", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "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": "Pros\n\n———————\n\n* 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. \n* 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. \n* 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. \n* 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. \n* 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. \n\n\nCons\n\n———————\n\n* 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). \n* 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. \n* 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? \n* 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! \n\n\n\nJustification\n\n———————\n\nI 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. \n\nPost-rebuttal:\n\n\n———————\n\nThis is my summary of my thoughts on the other reviews and rebuttals:\n\n**3zeH, N6wG express doubts on object discovery using a graph-based formulation that finds common patterns based on connectedness analysis:**\n\nI 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.\n\n**Use of ‘supervised features’ and on the dependability on object proposals (3zeH):**\n\nI believe this work follows the experimental protocol proposed in papers by Vo et al., plus analyses performance using both hand-crafted and deep features.\nI think pretty much all discovery methods depend on object proposals (as do several object detectors). I see no issue here.\n\n**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.\n\n**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.\n\nOverall I find this paper relevant and valuable, and I think that the paper should be accepted. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "As I noted above, authors should address limitations better. ", "review_text": "", "extra_scores": {"ethical_concerns": "I see no ethical issues. ", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4 hours"}, "extra_text": {}}, {"review_id": "iLNDz6GcCSy", "reviewer": "Reviewer_3zeH", "summary": "The authors propose a scalable approach (compared to existing ones)\nfor the 'unsupervised object discovery' task, based on graph and link\nanalysis methods. They show on several datasets and on the two tasks\nof single and multiple object discovery, that their method is either\nsubstantially more scalable and/or has better accuracy.", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "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": "\nSummary of review:\n\n-- Interesting approach and problem, but I couldn't convince myself that the idea of using a graph could\nimprove results so much:\nWhy should the overall idea of link-analysis/ranking by 'authority/hubs' idea, behind the particular objective and their particular  algorithms,\nsubstantially help for this problem? it would be useful  to give more\n intuition (the authors do try to explain/motivate in a few cases)... (see below for more details on this ..)\n\n-- use of 'supervised features' defeats the purpose/motivation  of the 'unsupervised'  task. The\n authors have a nice section on using recent work that doesn't use\n supervised features ... perhaps  they should start with that and make that more central\n (because it appears that they are testing on datasets where labels\n overlap significantly between where the features were trained on (eg\n imagenet) and those datasets ) ..\n\n-- sensitivity analysis to various params (eg max number of neighbors or\n random perturbations?): do they do this in the paper?\n\n-- a number  of clarity (presentation) issues. please see below.\n\n---------------\nMore details (the numbers refer to line numbers):\n\nwhy should this work? it would be useful to give more intuition..\n\nin particular: objectness based on votes of similarity of neighbors.. it seems that\nif two proposed regions are very similar we may get high objectness\nfor both regions.. and/or (more generally) if there is a large\n(semi)clique of very similar regions in different images, we could get\nhigh (in paper, it's called y) scores..  So what if we replicated each\nimage k times in the corpus.. (some sufficiently large replication factor above max\nnumber of neighbors in the optimization) would that that foil this\napproach?\n\n\n61: do you mean link 'regions' vs 'images' in 'and link images that\ncontain similar objects..' (since an image can contain multiple\nregions/objects?)\n\n62: does every image have exactly r proposals?  It's not clear whether\nthis is variable or fixed.  It would be good to give clear\n(mathematical) definitions too (instead of solely relying on English).\nIf r is fixed, what happens to images that should get no or only one or \n fewer than r proposals (do we create dummy proposals for such?). Good to make\nthis clear.\n...\n\n\n66: not sufficiently clear.. what does 'correspond to visual content\nshared' mean?  what does 'share' mean? This definitely  needs to be clarified,\nsince this is problem definition (see below too).\n\nOne clarification is wrt to number, assuming 'sharing similar visual\ncontent' means same objects: do you mean, some of the neighbors have\nthe same object, or *all* the neighbors, or at one least one, etc:\n\"Similarly, let x_kp ∈ {0,1} for p = 1,2,...,n and k = 1,2,...,r be\nindicator variables such that x_kp = 1 when region proposal k of image\np corresponds to visual content shared with its neighbors and let xp =\n(x1p , . . . , xrp )T .\"\n\n- this approach depends very largely on accuracy of region\n  proposals.. (very much depends on..)\n\n- minor: as an aside: why tao and rho are constants.  It seems making the\n  number of neighbors image and region dependent, perhaps based on a\n  similarity threshold, would be better... The nature of the two\n  parameters seem different: one (max number of regions per image) is\n  property of the data and region detection algorithms used, while the\n  other (max number of neighbors allowed) seems to be a meta\n  parameter, provided by the user.\n\n\n- minor: again, the English description of tao is not very clear.  It\n  likely means over all the images, take the maximum.  if written in\n  mathematics, in addition or instead of, just saying it in English,\n  it would be clearer.\n\n\n- 243: (in multiple object regime) Does the user specify M or\n otherwise, in an unsupervised problem, what can M be?? (I am thinking\n in their experiments, they know what M is from the datasets..)  in\n \"we return up to M regions per image, where M is the maximum number\n of objects in any image in the dataset. \"\n\n\n- 311: doesn't defeat the purpose of 'unsupervised' object discovery to\nuse image-net trained models (even for features??).. in\n\"Self-supervised features vs. supervised features. LOD and all of the\noptimization-based base-lines [32, 67, 71] rely on a VGG [60]-based\nclassifier trained on ImageNet [11].\"\n\n- 400: '87x'   in   \"..allows us to scale up UOD to the OpenImages [35] dataset\n(Op1.7M) with 1.7M images, 87 larger\nthan datasets considered in the previous state-of-the-art technique [67], and outperforms\n\n- multi objective performances seem very low .. perhaps some\n  discussion of that?\n\n=============\n\nAfter seeing author replies and other reviewers.\n\nI have read the reviews and authors' responses.   Thank you all. Given the authors' responses, I have increased\nmy 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.\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4.5"}, "extra_text": {}}, {"review_id": "RoY1Oa6EEKf", "reviewer": "Reviewer_FJwA", "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.", "questions": "", "limitations": "", "rating": 6, "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": "- pros\n1. It was very nice to reformulate the existing UOD formulation to be fit to a PageRank solution.\n2. First to introduce an UOD approach to be applied in the large-scale dataset (Op1.7M).\n\n- cons\n1. Reformulation that modifying the binary importance vector y as having a float value to become PageRank vector v is incremental.\n\n2. 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?\n\nIn L112, what does it mean \"inherently sequential\" for other baselines?\n\n\n---------------------------------------------------------------------------------------------\nAfter reading authors' responses and other reveiwers' comments, I raise my rating to \"lean to accept\". My concerns are well addressed.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "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_text": "", "extra_scores": {"ethical_concerns": "I did not find any ethical concerns in this paper.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "24 hours"}, "extra_text": {}}, {"review_id": "QtAa1PSgFSS", "reviewer": "Reviewer_N6wG", "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.", "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": "Originality: Utilizing ranking for object discovery seems original to me.\nClarity: 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.\nQuality: 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. \nSignificance: The paper is of interest of the community. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "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_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}]

Author rebuttal:

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)