Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper addresses the object retrieval problem from images. Traditional query expansion methods can only utilize very similar images, resulting in low recall. On the other hand, diffusion propagation methods on a image graph often ambiguity problem of propagation. Instead, spatial verification has to be used for the accurate detection of true positive images. However, in an ordinary graph with scalar edge weights, spatial verification cannot be done. Furthermore, spatial verification is very computationally heavy. To address the problem, a hypergraph is proposed to map image's internal structural information, and a community selection technique is employed for hypergraph propagation without heavy spatial verification. Experiments are conducted which show promising results.
main_review: Strong points:
- The solution is well motivated, intutive and reasonable.
- The paper is well presented and easy to follow, even for someone not specifically working on object retrieval
- Experiments show that the solution is promising, with both quantitative and qualitative results.

Weak points:
- The solution appears straightforward and quite heuristic. Though technically valid, it is not sure if there is any guarantee on the community based method. 
- The community method: only top 1 image is treated as the dominant community. There could be a robustness problem if top 1 image happens to be a false positive.
- I did not figure out how the communities are found. Different community detection method may have an impact on the retrieval performance.

-- update after rebuttal --
Based on the rebuttal, I will maintain my current rating.
limitations_and_societal_impact: fine with me.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: This paper proposes a hypergraph model to settle the ambiguity problem of propagation.
main_review: originality, from technical perspectives, the proposed model is quite simple and common. No many brilliant designs are shown.
quality, it outperforms the listed state-of-the-art methods.
clarity, in the introduction, there is no sufficient instruction to make me understand the necessity of using the hypergraphs.
significance, there are novel designs but this work also has some problems.
limitations_and_societal_impact: 1, In the introduction section of the story's beginning, there is no sufficient instruction on why we have to use a hypergraph. What are the benefits of the hypergraph?

2, According Fig. 1 a), the ordinary graph is not the key factor to link false-positive images, since we could also link the similar features in local ranges to break the connection between x1 and x5.

3，The propagation method is still quite simple based on Euclidean distance and constrained by hyperedges. There is not an explicit difference between the proposed hypergraph and an ordinary graph.
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: This work tackles the problem of image retrieval, specifically in the domain of re-ranking with ambiguous objects. It proposes two core ideas to improve upon existing query expansion and diffusion techniques, namely

1) Introduction of the hypergraph which unifies both global and local relations in the graph propagation process, hence resolving potential ambiguities.
2) Community selection, which resolves the ambiguities in initializing the graphs.

The proposed method shows strong performance on the standard ROxf-RPar (and the 1M distractor set) datasets over existing image retrieval methods with the re-ranking process. Qualitative results are also provided to help understand the way it increases the precision of top-ranked results.
main_review: ## Originality
To my best knowledge, the concept of hypergraphs for re-ranking is novel to the image search problem. In fact, this work is also the first attempt to combine the two existing classes of re-ranking methods: local descriptor-based geometric verification and global descriptor-based (query expansion and diffusion) into a single framework with the proposal of the hypergraph. I think this is a very elegant way of solving the existing ambiguities mentioned by the authors and the results speak for themselves.

The other novelty proposed in the work, Community selection, is less technical. However, this does not prevent it from being a good novelty as the motivation for it is intuitively explained and has the potential to be adopted in all general image retrieval pipelines.

## Quality
The submission is technically sound. 

After assessing the methods and experiments sections, I think the contribution of both novelties is well-justified by the experimental results and ablation studies. It is truly impressive the addition of hypergraph propagation alone already outperforms state-of-the-art (SoTA) in the ROxf-RPar [25] benchmark by a huge margin (12.5% increase in mAP over DELG [5] with local re-ranking on ROxf+1M-Hard, which is notoriously difficult due to the queries having cropped regions that cause extreme zooms *v.s.* database images, a lot of ambiguous regions/textures/objects, let alone the 1-million distractors). The impact of community selection is also clearly justified by the results in Table 2, and the great addition of Figure 4 to qualitatively show how the proposed re-ranking components significantly improve the retrieval results on arguably the most difficult query among the whole dataset.

There are a few minor questions, which clarifications from the author would be greatly appreciated:
1) It is hypothesized in L237-238 that “if all the top $S$ images in $G_s$ constitute a single component, we are very certain that all of them contain the same object with the query image”. Although this is intuitively correct, I wonder if the authors had a sanity check of whether this is actually true, *e.g.* by actually detecting and classifying the objects and checking whether they all fall into the same “community”? Although this does not affect the validity of the contribution of community selection, I think these results would be very interesting for the image retrieval community and provide domain knowledge for future works.
2) Why are the results from [14] not included in Table 1, since they are a very recent work? It would also be interesting to see if the hypergraph propagation can be incorporated with a Transformer (just out of curiosity, not asking for extra experiments).
3) In L277-278 the method runs on multiple CPUs and requires a huge amount of memory (896GB). 

    a) Would the performance drop a lot if you limit the RAM usage to a more normal amount (*e.g.* <50GB)?

    b) Could the authors provide a runtime breakdown analysis, especially how long it takes to run on the 1M datasets? 

    c) Is GPU acceleration an option? If so, how much does it improve the runtime?

## Clarity
The paper is very well-written, easy to follow. I believe the technical details presented allow for reproduction of the reported results.

## Significance
With reference to the **Quality** section, I believe the contributions in the work would be impactful for the field of image/object search & retrieval, not only by advancing the state-of-the-art by a big step, but also potentially inspire a lot of future work along this line. Clarifications from the authors on 3c) above in **Quality** would be a bonus, as it helps understand whether the compute requirement would be too much for other researchers to replicate and build upon the impressive results reported in this work.

limitations_and_societal_impact: The authors have addressed the limitations and potential negative societal impact of this work.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper proposes a new query expansion method for image object retrieval. Firstly, they propose a hypergraph among local features of base images. To expand new queries, it is time-consuming to check whether the query is related to initial search results. They propose a community selection method to speed up the procedure. In experiments, the proposed method outperforms traditional methods. 

main_review: Positive points:
The proposed community selection method seems reasonable and is efficient in new query expansion.

My concerns and questions:
1. The motivation for using hypergraphs is weird. At least the example in Figure 1 is misleading. In Figure 1 (a), the ordinary graph is constructed at the image level, so it leads to ambiguity. Can the ambiguity be solved by constructing ordinary graphs by local features as in Figure 1 (b)? Say, x_2 and x_5 are connected based on local features in purple frames while x_2 and x_3 are connected based on orange frames. In this way, the ambiguity would be solved. 
2. Inter hyperedges are only constructed between two images. Is it possible to construct a hyperedge involves more than two images?
3. Section 4.1 is difficult to follow. What is the difference between "activated local features" and "local features"? What are "IN" and "OUT"? If they are concepts from other papers. They should be introduced here to let this paper be self-contained. These concepts are important for understanding.

Minor problems:
1. On my side, Figure 1 (b) is difficult to read after printing.
2. Typo: Line 36, 'research' -> 'search'.
limitations_and_societal_impact: Yes.
review_title: null

Meta-review: This seems like a good approach which reviewers considered well motivated, and with promising results. Some weak points were identified such as lack of theoretical guarantees, and minor weaknesses/lack of clarity in the presentation. Reviewers largely appreciated the author response, and it seems if the changes are made the manuscript can be of good value to the NeurIPS audience.
Decision: Accept (Poster)