Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 6: Weak Accept
review_content: The authors propose a learnable space partitioning nearest-neighbour algorithm where the model learns a hierarchical space partition of the data (using graph partitioning) and learns to predict which buckets a query will reside in (using a learnable model).

The paper is an interesting combination of classical optimization and deep learning.

The authors make a concerted effort to compare to a range of space-partitioning-based nearest neighbour algorithms, however crucially none of these algorithms are state-of-the-art in comparison to some of the best PQ NNS or hierarchical Navigable Small World Graphs. 

In terms of writing, the model description requires significant overhaul. I had to re-read it several times and sketch out what exactly you are doing. I would recommend an algorithm box to summarize both the hierarchical graph partitioning *and* the learnable query network. 

4.3 "additional experiments" is some of the most interesting parts of the paper, I would recommend promoting these experimental results to the main paper.

I would recommend accepting this paper because I think it may lead to state-of-the-art NNS algorithms with theoretical guarantees, especially with a more powerful query network.
review_title: Official Blind Review #4

final_score: rating: 6: Weak Accept
review_content: 
The paper proposes a scheme to learn space partitions for improved
nearest neighbor search by first converting the search problem into a
supervised classification problem by graph-partitioning the
k-nearest-neighbor graph, and then using some machine learning model
to learn space partitions corresponding to the supervised problem. The
scheme is theoretically motivated and the empirical results
demonstrates the utility of the proposed scheme against various
baselines.  


While the paper presents a promising new direction for
nearest-neighbor search with space partitioning schemes, I am somewhat
on the border, leaning towards reject. This is mostly due to my lack
of understanding why Cayton & Dasgupta (2007) and Li et al. (2011) are
not valid baselines and are dismissed as "hyperplane
partitions". It would be very helpful to me as a reader to understand
why this literature does not warrant to be a valid
baseline. Especially given the following connection points:

- Firstly, the theoretical results presented by the authors also
  limit to hyperplane splits. 
- Secondly, the authors present empirical evaluation of recursive
  hyperplane partitions where the proposed scheme is the only learning
  based scheme while the techniques presented in Cayton & Dasgupta
  (2007) and Li et al. (2011) would have been the learning based
  partitioning baseline to beat.
- Thirdly, LSH space partitioning is considered as a baseline in
  Section 4.2 with the Neural LSH and Neural Catalyzer + k-means being
  the only learning based baseline; Cayton & Dasgupta (2007)'s learned
  LSH scheme would have been a valid baseline to the best of my
  understanding. 
- Finally, the authors mention the need for coupling the graph
  partitioning and the supervised learning phase. Li et al., 2011
  utilizes a loss function that essentially promotes a sparse graph
  cut while preserving near-neighborhoods, providing the closely
  coupled scheme. In the original paper, the authors utilize a
  recursive hyperplane partitioning scheme. However, a neural network
  with a softmax layer can be trained to minimize this closely coupled
  loss directly, obviating the need for the separate graph
  partitioning and supervised learning phases proposed in this
  paper. But it is possible that I have misinterpreted the connection
  and any clarification here would be very helpful.

Minor:

- It would be very helpful as a reader to understand how sensitive the
  neural network based partioning scheme is to the network
  architecture and hyperparameters. Some intuition behind the choices
  would be very useful.
- It is a little unclear how the plots in Figure 2 are generated --
  for each query, we would have access to the accuracy vs. number of
  candidates curve. In that case, it is unclear how the curves are
  aggregated across queries to generate average number of candidates
  (and 0.95 quantile) vs. accuracy curves. Given that not all queries
  in all the methods (including the proposed ones) will have the same
  sequences of accuracies, the quantile curve is especially unclear.
- The authors mention that neural LSH is only useful when the bin
  sizes are large, and otherwise k-means is more useful. Is there a
  straightforward way to decide when to switch between the two? Is it
  another hyperparameter we need to tune over while generating these
  space partitions?
- Theorem 3.1 considers only hyperplane partitions while neural
  networks usually generate nonlinear partitions. What are the
  conditions on the nonlinear splits that allows the guarantees to
  improve (or at least not degrade)? Is it obviously always improved?

review_title: Official Blind Review #1

final_score: rating: 3: Weak Reject
review_content: This paper proposes a technique for partitioning (presumably large number of) points in a d-dimensional, such that approximate nearest neighbor search in this space can be efficiently performed by reducing to search in a smaller partition. To this end, the paper provides the following procedure:
1. Build an exact k nearest neighbor graph of the provided dataset.
2. Partition this graph into m balanced sets while minimize inter-partition edges.
3. Train a neural net or linear model to predict the partition for each point. They also propose creating hierarchical partitions in the same way and also propose training with "soft" partition labels.

At test time, the trained model is used to predict probably partitions which are then searched over for nearest neighbors. The authors compare this technique to, most notably, a k-means based technique where centroids are used to partition the space. They show that on Glove and SIFT datasets, the neural partitioning approach is more accurate i.e. it can correctly identify correct nearest neighbors significantly more than k-means.

######
Pros:
1. This proposed approach of using neural techniques to build partitions of space for fast nearest neighbors is novel. While k-means-style techniques have been proposed to learn index structures, this is the first application of neural techniques as far as I can tell.
2. The paper is well-written and is easy to read. The experiments are sufficiently detailed and well documented.

Cons:
1. Experiments: The paper reports the number of correct neighbors obtained while searching on average and at 0.95 quantile. However, the core motivation of the paper is *fast* nearest neighbors search. In that vein, the metric of interest must incorporate time e.g. queries per second at a fixed level of accuracy. This is not new -- e.g. the benchmarks provided by Andoni and co-authors are evaluated on a QPS basis (https://github.com/erikbern/ann-benchmarks). The same holds for Amueller et al. 
2. Baselines: A related point is, what happens to baseline algorithms when they are given more "capacity". E.g. comparing with k-means baselines with a significantly large value of k or a multi-level k-means algorithm (e.g. considered by "FAST APPROXIMATE NEAREST NEIGHBORS WITH AUTOMATIC ALGORITHM CONFIGURATION" by Muje and Lowe). The comparison in the paper with k-means baseline with k=50 does not seem fair here. E.g. a hierarchical neural LSH approach with 256 partitions at top and 10 k means partitions at the second level performs 2560 distance computations. Alternatively, the authors can directly compare QPS as stated above.
3. The proof provided in the appendix is not entirely clear. E.g. after step 3, how does the next step (before (4)) follow? It is easy to see the denominator but the numerator is not clear.


Suggestions:
1. Please cite the following paper which is highly related and highly cited: FAST APPROXIMATE NEAREST NEIGHBORS WITH AUTOMATIC ALGORITHM CONFIGURATION.

review_title: Official Blind Review #3

Meta-review: This paper proposes a new framework for improved nearest neighbor search by learning a space partition of the data, allowing for better scalability in distributed settings and overall better performance over existing benchmarks.

The two reviewers who were most confident were both positive about the contributions and the revisions. The one reviewer who recommended reject was concerned about the metric used and whether comparison with baselines was fair. In my opinion, the authors seem to have been very receptive to reviewer comments and answered these issues to my satisfaction. After author and reviewer engagement, both R1 and myself are satisfied with the addition of the new baselines and think the authors have sufficiently addressed the major concerns. For the final version of the paper, I’d urge the authors to take seriously R4’s comment regarding clarity and add algorithmic details as per their suggestion.

Decision: Accept (Poster)