Space partitions of R d underlie a vast and important class of fast nearest neighbor search (NNS) algorithms. Inspired by recent theoretical work on NNS for general metric spaces (Andoni et al., 2018b;c), we develop a new framework for building space partitions reducing the problem to balanced graph partitioning followed by supervised classification. We instantiate this general approach with the KaHIP graph partitioner (Sanders & Schulz, 2013)  and neural networks, respectively, to obtain a new partitioning procedure called Neural Locality-Sensitive Hashing (Neural LSH). On several standard benchmarks for NNS (Aumüller et al., 2017), our experiments show that the partitions obtained by Neural LSH consistently outperform partitions found by quantization-based and tree-based methods as well as classic, data-oblivious LSH.
Recently, there has been a large body of work that studies how modern machine learning techniques (such as neural networks) can help tackle various classic algorithmic problems (a partial list includes Mousavi et al. (2015); Baldassarre et al. (2016); Bora et al. (2017); Dai et al. (2017); Metzler et al. (2017); Kraska et al. (2018); Balcan et al. (2018); Lykouris & Vassilvitskii (2018); Mitzenmacher (2018); Purohit et al. (2018)). Similar methods-under the name "learn to hash"-have been used to improve the sketching approach to NNS (Wang et al., 2016). However, when it comes to indexing, while some unsupervised techniques such as PCA or k-means have been successfully applied, the full power of modern tools like neural networks has not yet been harnessed. This state of affairs naturally leads to the following general question: Can we employ modern (supervised) machine learning techniques to find good space partitions for nearest neighbor search?
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?