Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: The paper investigated the quality of LSH binary coding for efficient nearest neighbor retrieval. They proposed a simple strategy to extract binary codes from Random Fourier Feature (RFF) and designed a new measure called ranking efficiency to evaluate the binary coding performance of different LSH methods. Extensive experiments validated the effectiveness and consistency of ranking efficiency from theoretical evaluation and the superiority of SignRFF with sufficient binary codes.

strengths_and_weaknesses: Strengths

S1. The authors simplify the binary coding based on RFF, and they demonstrate the new SignRFF is still locality-sensitive. 

S2. The new measure of ranking efficiency is very interesting to me, especially its consistency in both theory and practice. As the LSH efficiency (called by the authors) mainly targets the efficiency and space overhead of LSH schemes, it seems to be a good complement measure of accuracy.

S3. The experimental results are comprehensive and convincing. 

S4. This paper is well written and easy to follow.

Weaknesses

W1.I have a minor concern about the contributions of this paper, especially on the part of SignRFF. As the demonstration of the locality-sensitive property of SignRFF primarily comes from Lemma 1 [26], this part might be more solid if they could make an empirical analysis (or theoretical analysis if possible, will be better) of the variance reduction by removing the noise $\xi$. 

W2. Even though the ranking efficiency (RE) is very interesting to me, the operation to directly removing the covariance $V_{xy}$ is less promising. It will be more convincing to me if they could conduct experiments to validate that the values of $V_{xy}$ for most cases of $\rho$ and $c$ are much small than the values $(V_x + V_y) / 2$. 

questions: Q1. Followed by W1, as they have the formulas of collision probability for SQ-RFF and Sign-RFF (Equations 6 and 8), can they provide more empirical results (or theoretical analysis) about the variance reduction?

Q2. Followed by W2, can they follow the same settings of Figure 1 and plot the curves of $V_{xy}$ compared with $(V_x + V_y) / 2$?

limitations: Yes.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: The authors propose an RFF-based binary coding method that drops the additional perturbation term from the previously popular stochastic quantization RFF method. They not only demonstrate improved performance on retrieval tasks but also prove locality-sensitivity for their proposed method. 
strengths_and_weaknesses: The proposed algorithm is simple yet powerful with empirical success on the retrieval task.

questions: In all the cases, the KLSH performs better than SQ-RFF but never outperforms Sign-RFF. Could you elaborate more on why that is happening? What exactly is making SQ-RFF lag behind KLSH, and how sign-RFF is able to overcome that?
limitations: n/a
review_title: null

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: This paper modified the LSH method on RFF feature in [35] by removing the random noise and prove that it is still a LSH. Moreover, this paper also provides a new metric ranking efficiency to evaluate hash codes. Experiments are conducted on multiple data sets like SIFT, CIFAR, MNIST, comparing the proposed method to original one in [35] as well as other unsupervised hashing methods and one deep hashing method. 
strengths_and_weaknesses: Strengths:

--The theoretical part of the proposed modification looks sound.

--The experiments show the proposed modification outperforms the original one in [35].

Weaknesses:

--To prove the proposed SignRFF is LSH, the major technical difficulty (and hence contribution) is to formulate $f(z_x, z_y | \rho)$ and prove  it is increasing with $\rho$, which, however, is borrowed from [26]. So the technical contribution is not high.

--To get the ranking efficiency metric, $V_{xy}$ is discarded from equation (10). However, is it reasonable?  Is $V_{xy}$ close to 0, or very small, compared to $V_{x}$ and $V_{y}$, at least under some conditions? It is  is not rigorous to discard the term simply because it is hard to derive.

--There are many unsupervised deep hashing methods, and only one of them is compared.

--Only hamming ranking with long codes is used to evaluate the hash codes in this paper. However, the real practical way to use hash codes is actually constructing multi hash tables, each with a short code, which is how the sub-linear performance of LSH can be achieved, (and also how the complexity bound is proved).
questions: --A more rigorous analysis about why $V_{xy}$ can be discarded.
--Compared to more SOTA unsupervised deep hashing methods.
--Evaluate the codes with multi hash tables besides hamming ranking.
limitations: I did not find the discussion of the technical limitation or potential negative societal impact, even though the authors claims they are discussed.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper studies the problem of binary code constructions, which can be used to approximate the original high-dimensional vectors of real numbers. The approximation can save storage space and accelerate similarity search runtime. The paper introduces a new method, called SignRFF and claims the following contributions: (1) better performance than extensive baselines (i.e. LSH, ITQ, SpecH, BRE, SQ-RFF, and KLSH) (2) introduces a new metric called ranking efficiency to evaluate the quality of binary codes.      
strengths_and_weaknesses: Strengths:

S1: Novel technical contribution. The paper targets at SQ-RFF algorithm, which is becoming a standard for binary code construction and has over 750 citations since 2010. The paper reveals that the random noise component of the SQ-RFF algorithm is unnecessary, and it proposes a new algorithm SignRFF to remove the component. Experiments verify that SignRFF is more effective than SQ-RFF. 

S2: Solid experiments. The paper compares SignRFF with not only SQ-RFF but also a set of other strong baselines, including LSH, ITQ, SpecH, BRE, SQ-RFF. These baselines have broad impact in the field. For example, both LSH and ITQ have gained more than 1000 citations since the works were published.  

Weaknesses:

W1: Unclear motivation about new metric. The paper introduces a new metric called ranking efficiency to evaluate the quality of binary codes. The new metric is a key contribution claimed by the authors. It is unclear why we need a new metric. There are already a set of metrics commonly used in the field, including recall@#bits or recall@topk. It will be convincing if the paper explains the motivation and how the new metric differs from common ones.
  
W2: no deep hashing methods in key experiments. Figures 3 and 4 show that the proposed method outperforms a number of baselines. But none of the baselines is deep learning based. The paper moves comparison with deep hashing (i.e. CIB) to Figure 5, where the metric differs from Figures 3 and 4. It will be more convincing if the papers can add the performance numbers of CIB to Figures 3 and 4.   

questions: Address the weaknesses
limitations: N.A.
review_title: null

Meta-review: metareview: This was a borderline paper, with three (mostly) positive reviews and one somewhat negative review.

Some of the concerns raised by the reviewers include marginal contributions as well as some issues with the empirical results (though some reviewers felt the results were strong).  It does seem that at least the first reviewer was satisfied by the rebuttal response, and the concerns of the more negative reviewer seemed to be addressed at least somewhat in the rebuttal.

I also took a close look at the paper.  I am somewhat on the fence with this paper but I think the merits outweigh any flaws and that the paper could be accepted at the conference.  The paper has two somewhat disjoint contributions (one on the SignRFF method and the other introducing the ranking efficiency measure), each of which alone is not enough to carry a NeurIPS paper.  I think together it's OK but a bit non-traditional in its presentation.  It might be good in the final version to consider (if possible) adding additional comparisons, particularly to deep hashing methods.
confidence: Less certain
Decision: Accept