Learning to Anneal and Prune Proximity Graphs for Similarity Search
Authors: Minjia Zhang
Wenhan Wang
Yuxiong He
Venue:  (2020)
Keywords: Similarity search
Proximity graph
Learning to prune
Edge heterogeneity
Annealing
Efficiency

Abstract: This paper studies similarity search, which is a crucial enabler of many feature vector--based applications. The problem of similarity search has been extensively studied in the machine learning community. Recent advances of proximity graphs have achieved outstanding performance through exploiting the navigability of the underlying graph structure. In this work, we introduce the annealable proximity graph (APG) method to learn and reshape proximity graphs for efficiency and effective similarity search. APG makes proximity graph edges annealable, which can be effectively trained with a stochastic optimization algorithm. APG identifies important edges that best preserve graph navigability and prune inferior edges without drastically changing graph properties. Experimental results show that APG achieves state-of-the-art results not only by producing proximity graphs with less number of edges but also speeding up the search time by 20--40\% across different datasets with almost no loss of accuracy.


Under review as a conference paper at ICLR 2020
LEARNING TO ANNEAL AND PRUNE PROXIMITY GRAPHS FOR SIMILARITY SEARCH
Anonymous authors Paper under double-blind review
ABSTRACT
This paper studies similarity search, which is a crucial enabler of many feature vector-based applications. The problem of similarity search has been extensively studied in the machine learning community. Recent advances of proximity graphs have achieved outstanding performance through exploiting the navigability of the underlying graph structure. In this work, we introduce the annealable proximity graph (APG) method learn and reshape proximity graphs for efficiency and effective similarity search. APG makes proximity graph edges annealable, which can be effectively trained with a stochastic optimization algorithm. APG identifies important edges that best preserve graph navigability and prune inferior edges without drastically changing graph properties. Experimental results show that APG achieves state-of-the-an results not only by producing proximity graphs with less number of edges but also speeding up the search time by 20-40% across different datasets with almost no loss of accuracy.
INTRODUCTION
Similarity search (nearest neighbor search) is an integral and indispensable task in many machine learning applications, such as non-parametric classfficatio//eegrssso computer vision, informa- tion retrieval, and language modeling. Recently, it has been demonstrated that it is possible to build a vector search engine to support semantic search (Chen al., 2018; Sullivan 2018 Wang et al. 201 8a Johnson et al., 2017), which leverages high-quality neural ranking models (Nogueira Cho 2019 Xiong et al. [017 Zamani et al., 2018a) to encode both natural language query and documents into dense continuous feature vectors and performs similarity search to retrieve relevant documents with vast data volumes (e.g., based on Euclidean distance). This approach has demon- strated significant relevance gains in wide range of applications and outperforms existing term matching baselines, such as web search (Huang et al., 2003 Zamani et al.) 2018b). question and answering YYu al. (2014), ad-hoc retrieval (Mitra al. [20 2017
al. 2017 Guo al.,
2016), mobile search (Aliannejadi et al. 2018), and product search (Van Gysel et al. (016)).
The efficiency and effectiveness of the similarity search approaches have become problem of great interest, due to the widespread commercial value and the exciting prospect. Recent ad- vance of proximity graphs has demonstrated great potential for fast and accurate nearest neighbor retrieval (Malkov & Yashunin 2016; Fu et al. 2019), and the empirical performance of proximity graphs outperforms existing tree- based (Bentley 1975 Beckmann et al.) 1990 Yianilos 1993 Muja
& Lowe, 2014). locality sensitive hashing based (Gionis et al. 1999). and product quantization based methods (Jegou al. 201T Ge et al.) 2013 Norouzi & Fleet 2013 Lempitsky 2012] Kalan-
tidis & Avrithis 2014) by large margin. Proximity graphs exploit the navigability of graph struc- tures, which the search process relies on to converge and achieve good efficiency. practice, that of- ten results in dense connectivity and large memory consumption because they need to have sufficient edges to maintain specific graph propertics, which is a major limitation of this class of approaches.
We wish to improve the efficiency of similarity search. In this paper, we address the following research question: can we learn to prune edges of a proximity graph while still being accurate to find nearest neighbors? Specifically, the pruned proximity graph should be more efficient than the state-of-te -ftt----rtth-tttt proximity graphs with comparable accuracy. Before providing a definite answer to the question, briefly review the findings in percolation theory that motivates research.

---

Under review as a conference paper at ICLR 2020
Percolation describes the phase transition of a physical system when change abruptly after a slight change in controlling variables (c.g., temperature, pressure, or oth- ers) (Broadbent & Hammersley 1957). Prototypical percolation processes include water turning into ice or steam, and the spontaneous emergence of magnetization and superconductivity in metals. Percolation theory mathematically models these physical systems complex networks and phase transition as a dramatic change of the properties of network connections, We believe that if we can model edge importance as the robustness of proximity graphs the removal of the edges between vertices, we can produce proximity graph with less number of edges without dramatically changing the navigability of the graph.
of its properties
We present Annealable Proximity Graph (APG), for simplifying proximity graphs. In particular, we make the following contributions:
We introduce the annealable proximity graph and summarize its key characteristics.
To learn edge importance, we present a percolation inspired method for identifying impor- tant edges and introduce a domain-specific loss derived from search distance errors.
Our formulation makes it possible to leverage a stochastic optimization algorithm to opti- mize the objective and prune edges with low importance.
We prove the convergence of our optimization process and a theoretical guarantee of the search quality of the pruned graph.
This approach is unique compared with previous proximity graph algorithms, where most of them only exploit the structure of the underlying index instead learning from query distribution to reshape proximity graphs. We provide detailed empirical analysis of our approach. Experimental results show that our approach reduces the number of edges of sfate-of-the-art proximity graphs significantly by 50% while also speeds up the search time by 20-40% across different datasets with almost no loss of accuracy.
2 RELATED WORK
In this section, we review the main ideas from the existing work that is relevant our approach.
Approximate nearest neighbor search (ANN). The problem of similarity search has been exten- sively studied in the literature of ANN algorithms, which trade the guarantee of exactness against high-efficiency improvement. Some representative methods include tree structure-basce
(Bent-)
ley 1975 Beckmann et al., 1990. Yianilos)
1993 Muja & Lowe 2014), locality sensitive hash- ing (LSH) based (Gionis et al., 1999), product quantization (PQ) based (Jegou et al., [011 Ge
cct al., 2013 Norouzi & Fleet 2013: Lempitsky 2012 Kalantidis Avrithis 2014). and nearest neighbor graph-based (Hajebi et al. 2011: Fu & Cail 2016) approaches. Although some of these methods, such as LSH, have strong theoretical performance guarantee even in the worst case (Indyk) & Motwani 1998), recent advances of the proximity graphs have demonstrated logarithmic search complexity and outperformed prior approaches by a large margin (Malkov & Yashunin 2016 Douzel
al. 2018 Fu et al. 2019 al. 2019).
Proximity graphs. A proximity graph exploits the closeness relationship among feature vectors support similarity search. In particular, let V {or R 1, ..., N) be database of vectors, a proximity graph GVV, E) is a directed graph, where each vertex corresponds to one of the vectors and the whole graph achieves great local connectivity (as lattice graph) combined with a small graph diameter (as in a random graph) (Malkov et al. 2014 Malkov & Yashunin 2016 Fu et al.) 2019). Such a graph exhibits strong navigability and enables quick search with an N-greedy best- first search algorithm. During the search, candidate queue of size I. is used to determine the trade- off between the searching time and accuracy. Recent studies look into optimizing proximity graphs with product quantization (Douze et al.) 2018 Baranchuk et al.) 2018). However, these approaches often suffer from a considerable amount recall loss on large datasets because quantization errors tend to be large dense continuous feature vectors (e.g., generated by neural networks).
Learning to prune. Pruning is a common method to derive sparse neural networks and reduce their heavy inference cost (Han et al. 2015a These methods annihilate the non-important weights
2

---

Under review as a conference paper at ICLR 2020
through the introduction of an Ly or L1 regularizer to the loss function. Many of them remove weights and keep important weights to best preserve the accuracy. Neural network pruning can also be viewed
architecture search technique, where the network is viewed as computational graph where the vertices denote the computation nodes and the edges represent the flow of tensors (Wang et al., (0188) 8b. Liu et al. 2019).. To the best of our knowledge, learning prune has not yet been applied to the task of proximity graphs for similarity search. However, it appears to be a natural fit for restructuring the proximity graphs to improve similarity search.
3 CHALLENGES
The navigability of proximity graphs comes as a result of approximating monotonicity graphs, e.g., Delaunay graphs (Lee & Schachter 1980). According the graph monotonicity theory (Dearholt) et al. 1988), monotonicity graph has strong guarantee to find the exact nearest neighbor by following monotonic path with 1-greedy search (Fu et al. 2019). However, monotonicity graphs in high dimensional space quickly become almost fully connected, and search in fully connected graphs would be infeasible, due the out-degree explosion problem (Hajebi et al. 2011.. To address the problem, proximity graphs limit each node to connect to only a number of R neighbors, aiming to minimize the loss of graph monotonicity while still letting greedy search be effective.
However, several challenges remain. The correct choice of R is not so obvious. R cannot be too small, because then the graph tends lose too much monotonicity and search can frequently get stuck at non-global local minima, hurting accuracy. A sufficiently large R is often required to reach high accuracy, but it also increases the number of edges significantly and decreases efficiency: (I) It ubiquitously raises the connections of both "hubs" (i.e., nodes in dense areas) and nodes in sparse areas; and (2) makes the graph more densely connected with many vertices sharing a lot of common neighbors, increasing unnecessary distance computations. Ideally, each vertex should have a different R that best preserves graph monotonicity. The problem beyond selecting a good value for R and seems to require more fundamental changes to existing proximity graphs
METHODS
In this section, we propose the annealable proximity graph (APG), which supports the exploration of edge heterogeneity in proximity graphs and learning to prune such graphs with an eye towards getting to the nearest neighbor as quickly as possible with minimal loss accuracy.
4.1 OVERVIEW
APG starts with augmenting a pre-built proximity graph with a learnable weight associated with each edge, representing its importance to preserve graph monotonicity, and keep probability (33 4.2 The weight is updated in an iterative manner according to a learning rule.
APG employs a multi-step learning process, as illustrated in Fig. T At initialization of APG, all edges have equal weights. Since no edge heterogeneity has been learned so far, applying pruning at this stage could lead to premature decisions. Therefore, we start with performing a "warm-up" iteration over the edge weights only, without optimizations, i.e., as the grace-period.
Once this warm-up ends, we introduce a systematic and principled approach to optimize the edge keep probability distribution of the APG (6 4.4). In particular, APG models edge importance the robustness of graph monotonicity to edge removal and defines an objective function that reflects the destruction of graph monotonicity, based on relative search distance errors (5 4.3). It then generates a sequence of randomized subgraphs through a sampling policy to learn edge importance and uses a predefined annealing schedule to optimize the objective function.
The process ends once we meet a stopping criterion. After this step, APG marks low weight edges as less important and perform hard pruning remove inferior edges, shown in Fig. ?
3

---

Under review as a conference paper at ICLR 2020
Hops
Prosimity Generation
Graph Annealing
Spanse
Entry
Query
Annealable
Warm-up
Prouiiity
Sampling
Pruring
Figure 1: APG overview.
Figure 2: Example of before and after pruning proximity graph.
4.2 ANNEALABLE PROXIMITY GRAPH (APG)
Given proximity graph GVV F.,, annealable proximity graph GV F.) is obtained by augment- ing each edge E E with a weight variable the, and a keep probability function -> (0. 1) such that p(e) Pe indicates the keep probability of e E. That an independent Bernoulli random variable Rgg where F(R. = 1) Pe: (Re = 0) = Pe is assigned to each e.
Intuitively, Pe should be: (i) monotonically increasing we increases; and (ii) limm--+-o Pe 1. and -im Pe = 0. More importantly, it is desirable to have we initialized to similar values for all edges, allowing each edge have an equal probability of consideration when there little information about edge importance. As the optimization process continues, should converge into degenerated distribution that allows identifying subset of removable edges that do not signifi- cantly change graph properties. Moreover, we introduce an additional parameter, the temperature E (0, oo), which smooths the probabilities Pe as following. If T + oc (at the beginning), the probabilities Pe converges uniformly to the same value regardless of edge on the other hand, if + 0 (at the end), the probabilities P. converges to either or 0, for important and not important edges, respectively. To satisfy the above conditions, introduce the following function p:
(T) + exp (- WetH
where μ is normalizing factor to keep
E eEB
Pe (T) C constant.
4.3 ROBUSTNESS OF GRAPH MONOTONICITY
To efficiently find nearest neighbors, all the previous algorithms try exploit the proximity graph structure of V vectors by letting each vertex connect number of R neighbors. However, some connections could be more crucial for preserving graph monotonicity, which important for search efficiency, while the rest is less important. How do identify those important edges?
One naive approach is to keep those edges that appear as part of the shortest path from the en- try vertex to the ground truth nearest neighbor for query. Such approach significantly suffers overfitting: non-shortest-pa patt edges may still contain possibly relevant closeness relation for unseen queries the test query set. Another possibility is to treat all checked edges during the search process as important. However, the checked and taken edges are then not differentiated, and some checked but not taken edges may even hurt accuracy by misleading the route. Both of these results are undesirable. As g 3 mentioned, proximity graphs rely on the approximation of graph mono- tonicity converge and achieve their efficiency. Can we identify important edges based on their robustness to preserve graph monotonicity?
Entry
Figure A high-level depiction of learning edge importance for proximity graphs.

---

Under review as a conference paper at ICLR 2020
Identifying important edges. Inspired by the phase transition in percolation (Broadbent & Ham- mersley, 1957| Callaway et al.) 2000), we introduce a method for identifying edge importance in proximity graphs. In particular, as Fig. shown, for given G we randomly delete each edge with probability - Pe (remember that Pe denotes the keep probability of e), independently of all other edges, and denote the resulting random graph by G (V, F. F), where F is the set of deleted edges. For any query if we can find the exact nearest neighbor in G but not in G* under search budget, then we treat the edge hops along the search path of g in G, including those erroneous paths, to be important for preserving the robustness of graph monotonicity, because it is their deletion that causes the failure find the nearest neighbor in G
Relative distance errors. Once we get the set of edge hops for a query (let us denote it as H9), we update the weight wh. of h E H4 to increase the importance of those edges, based on how far off the found candidate is relative to the true nearest neighbor, similar to the Teacher Forcing scheme (Williams & Zipser 1989). In particular, assume G answers the query q by returning a point we define the weight update as:
p, and G answers with found candidate p',
8(p'.9) - 1) 77, vh E H Awhh = 5(p. 9)
(2)
where :) represents the distance between two vertices and is the learning rate. It measures the delta of searching q's nearest neighbor in a subgraph G versus in the full graph by removing F edges. The update is designed based on the following intuition: when the returned candidate p' in G is the exact nearest neighbor as returned by G. then the deleted edges are less important and the relative distance error O. Otherwise, the larger d'p/, .g) in comparison to 8(p q), the more importance Hº indicates, and the edge weights of H7t should increase more.
Objective. Based on Eqn. we propose to learn the keep probability distribution of APG while minimizing the relative distance eπror over a learning set Q. In particular, the learning objective function is defined as:
minimize
Σ LA
Awn
(3)
QQ
QEQ
Based on the learned keep probability, we identify a subgraph G that robust to the deletion of subset of edges F' with minimal loss of graph monotonicity.
4.4 OPTIMIZATION
The main objective of the optimization is to construct proper learning framework to optimize the objective defined in Eq 3 Similar to bagged ensemble learning (Bengio et al.) 2017). one approach is to initialize a set of graphs, each with a subset of edges randomly deleted. Then it individually learns edge importance on each subgraph and finally combines learned weights. However, bag- ging ignores the dependency among the individual subgraphs, and the edge importance does in fact depend on the chosen subgraph. In this paper, we introduce a learning algorithm. inspired by sim- ulated annealing (Ingber 1993) and stochastic optimization process (Bottou Bousquet] (207)), where we probabilisticaly generate a sequence of sampled subgraphs to learn the important edges that preserve graph monotonieity. The benefit that gradually discovers important edges while also allowing edges with lower keep probability to be sampled to demonstrate their values.
Generating a sequence of random subgraphs. For given G we generate a sequence of ran- domized subgraphs: G (1) - GO (2) - ... + G (K), which correspond to K optimization steps. At each step k. the keep probability of each edge is computed from the weight of the previous step w(k - 1).. The subgraph G* (k) is obtained via sampling edges from G* by randomly picking a set of (())((E(k) < [E\) edges based on this keep probability. The new weight w(k) is then obtained through learning to minimize the relative distance errors measured on G (k). As a strin-
gent control, the expected number of edges to be selected by the algorithm is [E() = [X(k) [E]],
where 0 < A(k) < 1 denotes the sampling ratio at iteration k and is governed by a sampling policy.
5

---

Under review as a conference paper at ICLR 2020
Gradual sampling policy. The sampling policy ((k) decides how many edges sampled sub- graph G* (k)) has. We found that the simplest solution to having a fixed value A(k) = 1 a works reasonably well in most cases, where is the final pruning ratio (the fraction of pruned edges). In this paper, inspired by the formula suggested in (Zhu & Gupta 2018), we define {(k) as:
^(#) = = (A -0- k
(4)
K
where e E {1,3} and ( is the initial sampling rate. Take a = 0.5 and X(0) = as an example, intuitively, this policy allows to select more edges for exploration in the beginning and gradually becomes more selective as the optimization is close to the end.
Binomial weight normalization. The expectation of the number of edges of a random subgraph G (k:) follows Poisson binomial distribution: It is the of Bernoulli random variables Re, e 1,.... [E] each taking on values 0 and with probabilities 1 1-Pe and Pe. respectively. However, since Aw in Eq 2 how expect the sampled graph G (k) have [L(()) edges given that increased weights also increase the sum of R.? To address this issue, we do a binomial normalization to
adjust the edge weights at each iteration by adding normalizing factor p(k) (as Eq all edge weights so that the sum of R. equals to [k(]]]
[E() E
Σ
Rh
[P((T) Σ
(5)
we LNCE
1+c
cEE
where vuk) is calculated through binary search the computed sum probabilities, which has time complexity of O(EE) (e((max(((())) min(w(k))).
Annealing schedule. To balance exploration and exploitation of edge importance, approach includes an annealing schedule ((k) to determine the temperature T, which is updated along the iterations. The schedule choice dominated by a trade-off. On one hand, fast temperature decay simplifies the optimization objective and reduces the complexity, assisting the edge weights to con- verge, since inferior edges quickly have their keep probability driven to 0 and excluded from subsequent optimizations. However, premature decisions could lead to a sub-optimal keep proba- bility distribution. This suggests that should choose slow temperature decay, which provides more opportunities for testing random subgraphs during the pre-convergence phase, but also may find a better subgraph during the convergence phase.
The solution we propose is based on observations explored in simulated annealing, which share a similar trade-off between the continuity of the optimization process and the time required for deriving the solution (Ingber] 1993). Among the many alternatives, we choose the exponential schedule, which has been shown to be effective in multiple other tasks, e.g. (Kirkpatrick et al. 1983 Nourani & Andresen, 1998).
+ (kk = To g
(6)
This schedule starts with a relatively high temperature and decays fast with a decay factor B.
Hard pruning. The optimization process ends when it meets a stopping criterion. In our current implementation, we use simple criterion that stops after a given number of iterations. Once the optimization finishes, we re-rank edge weight and prune less important edges according to desired pruning ratio a. While pruning, we avoid deleting bridges that disconnect the graph. After prun- ing, we add a minimal number edges to keep the graph strongly connected through connectivity augmentation (Hsu et al. 2017). The overall learning algorithm is given in Algorithm
Convergence and correctness proof. We demonstrate the effectiveness of our approach empir- ically in g 5) and provide a theoretically derived proof of the convergence and correctness of our algorithm in Theorem (.T

---

Under review as a conference paper at ICLR 2020
Algorithm
APG learning algorithm
1: Input: Unpruned proximity graph G(V, learning set Q, candidate queue length L.
2: Output: Pruned graph G(V, E F).
3: Parameters: Learning 7, starting temperature To, decay factor B, pruning ratio o,
iteration K
4: Init: T To k
5: Convert E)) to G* (V, E), w + 0
6: Update w according to warm up run
7: while k < K do
8: À 1- + (A(0) 0 1) (1 _1
)
9: Normalize w s.t. [(k] = [A( 1
Σ
Heexp Momuiki
CEE
10: Randomly sample subgraph G* (1:)VV B(k))
for q in Q do p' - search( (k).q. L) p. 499 <- search(G,
12:
14:
if p + p' then for h in H do
Awn. + A(p' 1)
16:
8lp.g)
17:
Wh
Wh Awh
18:
T To gt
19:
Shuffle Q
20:
Remove |F| = a E lowest ranking edges from G*
Convert G (V, F) to G(V, F FF
5 EVALUATION
5.1
METHODOLOGY
Datasets. We evaluate APG on three publicly available datasets, which are widely used as similarity search benchmarks:
SIFTIM classical dataset containing 288diimensional SIFT descriptors (Jegou al. 2011
It consists 1,000,000 base vectors, 100,000 learning vectors, and 10,000 testing vectors.
Deep random 1,000,000 subset of one billion of 96-dimensional vectors produced by CNN (Babenko & Lempitsky 2016). We sample 100,000 vectors from the provided 350M learn set as the learning set. For testing, we take the original 10,000 queries.
GloVe is collection of 200-dimensional word embedding vectors from Twitter data (Pennington et al. (014)). We randomly sample from the original 1,193.514 vectors to get base, learning, and testing sets, each containing 1,000,000, 100,000, and 10,000 vectors, respectively.
For each dataset, we use one of the state-of-the-ard approaches, Hierarchical Navigable Small World graph (Makkov & Yashunin 2016), to build the proximity graph using the base set, which refer to as PG (proximity graph). We use the learning set to learn and prune the bottom layer of HNSW and use the testing set for final evaluation. We do not prune the edges in the upper layers of HNSW since there are much fewer edges in those layers. We set hyperparameters as To = 1, = 20, 0.8, 7) 0.1, and 0.5. The training time is 77, 40, and 128 minutes for SIFTIM, Deep1M, and GloVe, respectively.
Setup. All the experiments were done on 64-bit Linux Ubuntu 16.04 server with Intel Xeon CPU ES-2655 v4 @ 2.20GHz processor.
Implementations. APG and the learning algorithm are implemented in C++. Subgraph sampling implemented by using binary mask map, which is of the same size the number of edges, to determines edges that are kept in the sampled subgraph. The weights that are masked in the sampled subgraph do not get updated during the weight update phase.
7

---

Under review as a conference paper at ICLR 2020
Evaluation metries. To measure the pruning effectiveness, we report the number of edges before and after pruning and the search time. We measure the accuracy by calculating the rate of queries for which the exact nearest neighbor is found. Since it is essential to be both fast and with high accuracy, we focus on the high accuracy range.
5.2 EXPERIMENT RESULTS
In this section we evaluate the proposed method by comparing the following schemes for each dataset:
Original PG. We construct proximity graph over the base vectors using the HNSW algo- rithm.
Ours. Our main algorithm as described in 4 the pruning ratio to = 0.5, which forces half of the edges to be useful for preserving the graph properties.
We use the same initial R as PG and set
PG + sampling. As a heuristic baseline, we uniformly sample half of the edges from PG remove without iteration optimizations and annealing edge weights.
Sparse-PG. Unlike ours, this approach directly constructs a proximity graph with only half edges to begin with. Hence all the edges still have equal importance.
Table 1 shows the accuracy, the edge counts, the search time for all three datasets. To compare the performance of baselines and approach apples apples, perform controlled experiments to keep all approaches to reach the same accuracy target in order to compare the edge reduction rate and the search time improvement. Given an accuracy target (e.g., 0.99 for SIFTIM, 0.94 for DeepIM, and 0.83 for VEo,E), we vary L to find the minimum latency to reach the desired accuracy.
Overall, compared to the original proximity graph, ours reduces the number of edges by 50%, mak- ing PG more memory efficient. On SIFTIM and GloVe IM, ours further makes the search 26. 1% and 1.8% faster, respectively. This is because pruning simplifies the proximity graph while preserving the graph monotonicity, so that a query still gets to the nearest neighbor but is faster by avoiding checking less important edges. On Dc, the fastest search time achieved by the unmodified PG, because when the target accuracy is really high (e.g., 0.99), there are much fewer redundant edges. And for this particular dataset, after pruning 50% edges, ours needs to search little bit more to reach the same level of accuracy.
Both PG + subsampling and sparse-PO have a similar number of edges like ours. However, reducing the number of edges alone does not necessarily lead to better search efficiency. If the search takes fixed number of hops to reach the nearest neighbor, then pruning edges will lead to less number of vectors being checked. However, for proximity graphs, the search stop condition is (1) greedy search until reaching a local optimum and (2) the search time budget has exhausted, so the search may end up searching the same amount of edges even after pruning edges. Since subsampling does not take into graph monotonicity into account, it leads to poor search efficiency either because query needs to take detour to find the nearest neighbor or may not even find the nearest neighbor if the graph becomes disconnected. In fact, randomly removing edges is so destructive that GMM cannot get the desired 0.83 accuracy even if the search time has increased from 0.55ms to 1.45ms. On the other hand, the sparse-PG directly restricts the number of edges of each node during the graph construction phase. However, as described in g 3 a smaller R hurts the connectivity of the proximity casily get stuck at local minimum. In order reach the same accuracy, this
graph, and search approach needs to search more, which causes the degradation of search time. As a result, APG makes the search 25-74.2% faster compared to these two approaches.
Impact of pruning ratio We evaluate the impact of different pruning ratio o. Fig 4a shows that, as a increases, the number of edges left in the pruned graph linearly decreases, which is expected because our algorithm enables accurate control of pruning given number of edges.
Fig evaluates evaluates the impact on accuracy varying a, under different L = 20, 50, 100. The accuracy remains almost par as the unpruned proximity graph when the pruning ratio is equal or less than 50%. It starts to drop significantly once the pruning ratio is beyond 50%. The results suggest that our approach prunes large number of edges while still being able to let queries find their nearest
8

---

Under review as a conference paper at ICLR 2020
Edge reduction
Search time improvement
Dataset
Configuration
Recall @1
#Edges
Latency (ms)
rate
Original PG
0.993
40.3M
0.23
50.0%
26.1%
PG sampling
0.992
20.2M
0.43
0.0%
60.5%
SIFTIM
Sparse-PG 0.991
20.2M
0.66
0.0%
74.2%
Ours
0.993
20.2M
0.17
Original PG
0.947
43.2M
0.1
50.0%
-40%
PG + sampling
0.945
21.6M
0.16
0.0%
35.0%
DeepIM
Sparse-PG 0.943
21.6M
0.14
0.0%
25.7%
Ours
0.943
21.6M
0. 0.104
Original PG
0.831
20.6M
0.55
50.0%
1.8%
PG + sampling
0.814
10.3M
1.45
0.0%
62.8%
GloVeIM
Sparse-PG 0.83
10.3M
0.74
0.0%
27.0%
Ours
0.833
10.3M
0.54
Table 1: Comparison between APG and different baselines over SIFTIM, Deep and GloVe.
neighbors, as long as the proximity graph has not entered a phase transition where starts to quickly lose graph monotonicity.
To demonstrate the impact of the pruning ratio on search efficiency, we present Fig 4c and Fig 4d which illustrate the distance computations and search time under different The results show that larger a often leads to fewer distance computations and shorter search time, with varying L. This expected, because APG makes the proximity graph sparser and saves both distance computations and search time by avoiding checking less important edges.
1.
Distance computations
2300
om0
G43
Edges (million)
C9
2000
6=0.3
0.3
Recall@1
2500
2.00.5
Search time
18
L-20
2000
-.0.7
0.7
1m
1500
020
1000
0.0
0.5
0.5
0.5
0.5
00
01
02
03 04
05
0.5
07
Praning ratio
Pruning
(d)
Figure 4: Impact of different pruning ratio. (a) #Edges v.s. pruning ratio; (b) Accuracy v.s. pruning ratio under different L; (3) and (4) Distance computations and search time under different o.
Impact on degree distribution. To see how pruning affects the graph topology. Fig in Ap- pendix B shows the frequency distributions of in-degree and out-degree for all nodes before and after pruning (ar 0.5). We found that the out-degree tends to be smoothed out to have power-law distribution after the pruning, and the in-degree remains to have a binomial distribution but with only slight shift after the pruning.
Internal of APG learning process. To reveal the internal learning process, Fig. Zin in the Appendix demonstrates the snapshot of the keep probability distribution at different iterations. The distribu- tion starts with a relatively high temperature and high sampling ratio X, so that most edges having an equal probability being selected (e.g., 0.8-1). 1).. Then as the iteration goes on, the temperature decays by following the annealing schedule (k) (Eqn. 6 and the sampling ratio follows the sampling pol- icy A(k) (Eqn. 4.. As result, those edges that are less important for preserving graph monotonicity have their probability gradually reduced. This process keeps going until the distribution becomes very biased: most of the edge probability are distributed around the two peaks. This is expected because Theorem A. shows, the optimization eventually converge with the joint distribution of Re (T') for all edges being equal for T + oo and sparsely supported for T' - 0.
5.3 COMPARISON WITH EXISTING METHODS
We include the comparison between APG and two state-of-the-art proximity graphs: (1) HNSW (Malkov & Yashunin 2016) and (2) NSG (Navigable Spread-out Graph) (Fu et al. 2019.

---

Under review as a conference paper at ICLR 2020
We further report the comparison group results from the corresponding sparse counterparts: (3) HNSW-sparse and (4) NSG-sparse, both of which have a similar number of edges like ours. We also provide comparison to (5) HNSW with random pruning
We first consider the compromise between the search time and accuracy. Fig. illustrates the accuracy-latency tradeoff between APG and the other configurations. We observe that on SIFTIM, APG is reaches the highest accuracy (0.995) when having the same search time budget (e.g.. 0.2ms) and is the fastest to reach the same accuracy (e.g.. 0.99), which indicates that by pruming redundant edges APG makes graph similarity search faster. On the other hand, compared to the sparse coun- terparts, APG delivers better accuracy- ceuurcc-latteney tradeoff than both -INSrssparse and NSG-sparse. APG is 34% and 66% faster than HNSW-sparse and NSG-sparse to reach the same accuracy (0.98) and achieves the highest accuracy under the same search time budget (e.g., <0.3ms), which indi- cates it is preferable to first build proximity graph with large number of edges and then prune to obtain a simplified one than directly build proximity graph with size comparable to the pruned graph. Random pruning has the worst performance, because it considers neither the graph structure nor edge importance. For Deep IM and GloVe, APG outperforms HNSW-sparse, NSG-sparse, and HNSW-rand. Compared to HNSW and NSG, APG achieves almost on-par accuracy-latend trade- off, but it has 50% less number of edges than HNSW and NSG (Fig. 5d and therefore is much more memory efficient.
05
Search time (ms)
Search time (mS)
MSG
033
RSG
So0-sparse
NSG sparse
HN:W
HNSW
INSS-spprrs
HISS rand
HNSW-rand
APG
APG
1990
0.02
031
636
0.00
1.00
8.00
692
0.94
330
690
1000
Accuracy (Top-1 recall)
Accuracy (Top-1 recall)
(a) SIFTIM
(b) DeepIM
VGG
Sparcs
Search timre (11))
0.4
INCA
30
edges (n
28
3.0
3.3
12
sparse
Accuracy (Top-1 recall)
DoepoN
GloVi
(c) GloVe
(d)
Figure 5: Comparison to existing approaches and alternatives.
CONCLUDING REMARKS
Proximity graph an important data structure for building large scale vector search engine of many machine learning systems. It is crucial to make it answer queries with low latency, low memory cost, and high accuracy. To the best of our knowledge, this the first work on prox- imity graphs that demonstrate that we can learn to anneal and prune proximity graphs without losing much accuracy. This has several benefits: pruned edges reduce the memory cost; and the pruned proximity graphs perform similarity search 21-41% faster than existing and the state-of- the-art approaches with minimal loss of accuracy. The cost is a small investment on learning and optimization time. We open-sourced the code httptttt/////m httpps:///dvvee google...o.e.................... com/ open ?id= Ge
15vhhS50091 -
APG is built with R = 64 and pruning ratio 0.5. (1) and (2) are built with R = 64, (3) and (4) are built with R 32. (5) is built with R 64 but with 50% of edges randomly deleted.
10

---

Under review as a conference paper at ICLR 2020
REFERENCES
Mohammad Aliannejadi, Hamed Zamani, Fabio Crestani, and W. Bruce Croft. Target Apps Selec- tion: Towards Unified Search Framework for Mobile Devices. In SIGIR 2018, pp. 215-224, 2018.
Artem Babenko and Victor S. Lempitsky. Efficient Indexing of Billion-Scale Datasets of Deep Descriptors. In CVPR 2016, pp. 2055 2063, 2016.
Dmitry Baranchuk, Artem Babenko, and Yury Malkov. Revisiting the Inverted Indices for Billion- Scale Approximate Nearest Neighbors. In 2018 pp. 209-224, 2018.
Norbert Beckmann, Hans-Peter Kriegel, Ralf Schneider, and Bernhard Seeger. The R*-Tree: An Efficient and Robust Access Method for Points and Rectangles. In SIGMOD 1990, pp. 322-331, 1990.
Yoshua Bengio, Ian Goodfellow, and Aaron Courville. Deep learning, volume 1. Citeseer, 2017.
Jon Louis Bentley. Multidimensional Binary Search Trees Used for Associative Searching. Com- munications of the ACM, 18(9):509-51, September 1975. ISSN 0001-0782.
Léon Bottou and Olivier Bousquet. The Tradcoff's of Large Scale Learning. In Advances in Neu- ral Information Processing Systems 20, Proceedings of the Twenty-Fürst Anmual Conference on Neural Information Processing Systems, pp. 161-168, 2007.
Simon R Broadbent and John M Hammersley. Percolation processes: I. Crystals and mazes. In Mathematical Proceedings of the Cambridge Philosophical Society, volume 53, pp. 629-641, 1957.
Duncan S Callaway, Mark EJ Newman, Steven H Strogatz, and Duncan J Watts. Network robustness and fragility: Percolation on random graphs. Physical review letters, 85(25):5468, 2000.
Qi Chen, Haidong Wang, Minggin Li, Gang Ren, Scarlett Li, Jeffery Zhu, Jason Li, Chuanjie Liu, Lintao Zhang, and Jingdong Wang. SPTAG: A library for fast approximate nearest neighbor search, 2018. URL httptttts://gleeeee
com/ Mi http///iccooooot//SSTA....
DW Dearholt, N Gonzales, and G Kurup. Monotonic search networks for computer vision databases. In Swenty-Second Asilomar Conference on Signals, Systems and Computers, volume 2, pp. 548- 553, 1988.
Mostafa Dehghani, Hamed Zamani, Aliaksci Severyn, Jaap Kamps, and W. Bruce Croft. Neural Ranking Models with Weak Supervision. In SIGIR 2017, pp. 65-74, 2017.
Matthijs Douze, Alexandre Sablayrolles, and Hervé Jégou. Link and Code: Fast Indexing With
Graphs and Compact Regression Codes. In CVPR, 2018.
Cong Fu and Deng Cai. EFANNA An Extremely Fast Approximate Nearest Neighbor Search Algorithm Based on kNN Graph. CORR, abs/1609.0723) 2016.
Cong Fu, Chao Xiang, Changxu Wang, and Deng Cai. Fast Approximate Nearest Neighbor Search with the Navigating Spreading-out Graph. In VLDB' 19, 2019.
Tiezheng Ge, Kaiming He, Qifa Ke, and Jian Sun. Optimized Product Quantization for Approximate Nearest Neighbor Search. In CVPR 2013, 2013.
Aristides Gionis, Piotr Indyk, and Rajeev Motwani. Similarity Search High Dimensions via Hashing. In VLDB' 199 pp. 518-529, 1999.
Jiafeng Guo, Yixing Fan, Qingyao Ai, and W. Bruce Croft. A Deep Relevance Matching Model for Ad-hoc Retrieval. In CIKM 20/6, pp. 55-64, 2016.
Kiana Hajebi, Yasin Abbasi- Yadkori, Hossein Shahbazi. and Hong Zhang. Fast Approximate Nearest-neighhor Search with K-nearest Neighbor Graph. In IJCAP' 2011.

---

Under review as a conference paper at ICLR 2020
Song Han, Huizi Mao, and William J Dally. Deep compression: Compressing deep neural networks with pruning, trained quantization and huffman coding. arXiv preprint arXiv: 2015a.
Song Han, Jeff Pool, John Tran, and William Dally. Learning both weights and connections for efficient neural network. In Advances in neural information processing systems, pp. 1135-1143, 2015b.
D. Frank Hsu, Xiaojie Lan, Gabriel Miller, and David Baird. A Comparative Study of Algorithm for Computing Strongly Connected Components. DASC 2017.
Po-Sen Huang, Xiaodong He, Jianfeng Gao, Li Deng, Alex Acero, and Larry Heck. Learning deep structured semantic models for web search using clickthrough data, In CIKM '13 pp. 2333-2338, 2013.
Piotr Indyk and Rajeev Motwani. Approximate nearest neighbors: towards removing the curse of dimensionality. In Proceedings of the thirtieth annual ACM symposium on Theory of computing, pp. 604-613, 1998.
Lester Ingber. Simulated annealing: Practice versus theory. Mathematical and computer modelling, 18(11):29-57, 1993.
Herve Jegou, Matthijs Douze, and Cordelia Schmid. In Product Quantization for Nearest Neighbor Search, 2011.
Jeff Johnson, Matthijs Douze, and Hervé Jégou. Billion-scale similarity search with GPUs. CoRR, abs/1702.08734, 2017. |ttp::////arxx http:///aaaa.i..oor/////2222222/ 08734
Yannis Kalantidis and Yannis S. Avrithis. Locally Optimized Product Quantization for Approximate Nearest Neighbor Search. In CVPR 2014, pp. 2329-2336, 2014.
Scott Kirkpatrick, C Daniel Gelatt, and Mario P Vecchi. Optimization by simulated annealing. Science, 220(4598):671-689) 1983.
D. T. Lee and Bruce J. Schachter. Two algorithms for constructing a Delaunay triangulation. Inter- national Journal of Parallel Programming, 93)):219-242, 1980.
Victor Lempitsky. The inverted multi-index. In CVPR '12, pp. 3069-3076, 2012.
Wen Li, Ying Zhang, Yifang Sun, Wei Wang. Wenjie Zhang, and Xuemin Lin. Approximate Nearest Neighbor Search on High Dimensional Data Experiments, Analyses, and Improvement. 1EEE Transactions on Knowledge and Data Engineering, 2019.
Zhuang Liu, Mingjie Sun, Tinghui Zhou, Gao Huang, and Trevor Darrell. Rethinking the Value of Network Pruning. In 7th International Conference Learning Representations, ICLR 2019, 2019.
Yury Malkov, Alexander Ponomarenko, Andrey Logvinov, and Vladimir Krylov. Approximate near- est neighbor algorithm based navigable small world graphs. hnf. Syst., 45:61-68 68, 2014.
Yury A. Malkov and D. A. Yashunin. Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs. CoRR, arXiv preprint abs/1603.09320, 2016.
Bhaskar Mitra, Fernando Diaz, and Nick Craswell. Learning to Match using Local and Distributed Representations of Text for Web Search. In WWW 2017, 2017.
Marius Muja and David G. Lowe. Scalable Nearest Neighbor Algorithms for High Dimensional Data. TPAMI 2014, 36(11)222772244, 2014.
Rodrigo Nogueira and Kyunghyun Cho. Passage Re-ranking with BERT. CoRR, abs/ Abs/199 2019.
Mohammad Norouzi and David J. Fleet. Cartesian K-Means. In CVPR 2013, 2013.
Yaghout Nourani and Bjarne Andresen. A comparison of simulated annealing cooling strategics. Journal of Physics A: Mathematical and General, 31(41):8373, 1998.
12

---

Under review as a conference paper at ICLR 2020
Jeffrey Pennington, Richard Socher, and Christopher D. Manning. GloVe: Global Vectors for Word Representation. In EMNLP, pp. 1532-1543, 2014.
Danny Sullivan. Faq: All about the google rankbrain algorithm. 2018.
Christophe Van Gysel, Maarten de Rijke, and Evangelos Kanoulas. Learning Latent Vector Spaces for Product Search. In CIKM 16, pp. 165-174, 2016.
Jizhe Wang, Pipei Huang. Huan Zhao, Zhibo Zhang, Binqiang Zhao, and Dik Lun Lee. Billion- scale Commodity Embedding for E-commerce Recommendation in Alibaba. In KDD 2018, pp- 839-848, 2018a.
Mengdi Wang, Qing Zhang, Jun Yang, Xiaoyuan Cui, and Wei Lin. Graph-Adaptive Pruning for Efficient Inference of Convolutional Neural Networks. CoRR, abs/1811.08558 2018b.
Ronald Williams and David Zipser. A Learning Algorithm for Continually Running Fully Recur- rent Neural Networks. Neural Computation, 1(2):270-280, 1989.
Chenyan Xiong, Zhuyun Dai, Jamie Callan, Zhiyuan Liu, and Russell Power. End-to-End Neural Ad-hoc Ranking with Kernel Pooling. In SIGIR 2017, pp. 55-64, 2017.
Peter N. Yianilos. Data Structures and Algorithms for Nearest Neighbor Search in General Metric Spaces. In SODA 193, pp. 311-321, 1993.
Lei Yu, Karl Moritz Hermann, Phil Blunsom, and Stephen Pulman. Deep Learning for Answer Sentence Selection. CoRR, abs/ 141..1632, 2014.
Hamed Zamani, Mostafa Dehghani, W. Bruce Croft, Erik G. Learned-Miller, and Jaap Kamps. From Neural Re-Ranking to Neural Ranking: Learning a Sparse Representation for Inverted Indexing. In CIKM 2018, pp. 497-506, 2018a.
Hamed Zamani, Bhaskar Mitra, Xia Song, Nick Craswell, and Saurabh Tiwary. Neural Ranking Models with Multiple Document Fields. In WSDM '18, 2018b.
Michael Zhu and Suyog Gupta. To Prune, or Not to Prune: Exploring the Efficacy of Pruning for Model Compression. In ICLR 2018, 2018.
13

---

Under review as a conference paper at ICLR 2020
A PROOF OF THEOREM
Theorem A.I. Let Go(V, En) be the original graph prune, and let Q be the query set. Suppose there exists a subset of edges E" - Eu such that the average recall of retrieving the nearest neighbor in V for all queries q Q using edges in E is 1. Let G(R) be the random graph iteration running Algorithm I, and let {Re (k) be the family of Bernoulli random variables defined on the edges of (k)), with P( PRR (k) =1 (k..k). Assume that pelke) < for e. E Eo (E at some step
ke. Also assume that T(k) 2 ( + for all k. If = -1-1F- F/) then:
(1) EEEF- Pelk + 1) 2 Ecer E. (k( for all sufficiently large k. In particular, limg-+ EeEE- (k) exists.
(2) lllmm- T(k) 0. then lim (k(k) for all E", and limg- Pk(k) = 0 for all e E Eo\
(3) With the condition in (2), suppose r(k) denotes the average expected recall of retrieving the ground truth nearest neighbor of a query E Q in a subgraph of G(k) randomly sampled from the joint distribution (k)). Then lim r(k)
Theorem
1.1
We start with showing (1). Note that the probability sum constraints
(c) + Σ
Pe(k) = (1 (1- o) =
EE
eEEo\E
is satisfied for all k. It then suffices to show that
Σ po(k+))
Σ Pk( CEEVE"
EEEVE
for sufficiently large k. Observe that wr(k) remains a constant (= w. (0) for all and all E", E Eo) Ex, and that jak) monotonically decreases k increases. We claim that pe (k+1) S pe (k(k) for all k 2 ke- Together with the probability sum constraints this shows that Eesr (k) monotonically increasing for le 2 max, ke- Since EeEg Pk(k) is bounded from above, lim Ever. (k) = sup; EeEF- (o(k) exists.
For (2), since lim; Ti:
observe that lime-zoe Pe Pk(k) + 0 all e E Thus the probability sum constraint enforces that lim, EEEE. Pe(k) = E... Recall that lim inf 2i + supp 8k 2 lim inf (I + y/k) for any real sequences I and yı. Now consider any E E*, we have
lim inf pe (k) k-200
lim
Σ
(k( lim
Σ
(k)
100
EE
k0000
e'EE'Me')
M
Σ
lim Per (k)
el e'EE-Mee'
k
Σ
C'ER' (fe))
E - -1)=11))=1 1.
which implies that lim; Pe (k) 1.
To prove (3), we first define the notation X(q, E') to be the indicator function of whether the ground truth nearest neighbor of query 9 be retrieved in G using subset of edges E C Eg. More precisely, X(q, E) = if the nearest neighbor of q can be retrieved using edges in E; and x(g. E) = O otherwise. Note that the average recall step ie can be written
Fk
ΣΣ QEQ ECE,
x(g, F.P((F is chosen from G(k)),
Q
14

---

Under review as a conference paper at ICLR 2020
where the second summation is amongst all subsets of Eg. Since each edge being chosen is inde- pendent of other edges, we can expand the probability and it follows that
Th
E PEQ
X(a
E)
II eEB
(k(
II
Pa Pa
Q
ECE,
egE
Since we assumed that E") for all q Q, it follows that x(g, E) for all E 2 E Thus
Σ Σ
Pc
(1- pc())((())))
2
101
DEQ E EE
AEE
egE
Note that
Σ E' E'CECE, En
Il CEE
pe)k) (1- pek)) cgE
E E'CECED
II Pa(k) II
(k(k) II egE
(k))
CEEE-
oE DEE)E"
II (b)
Σ
II CEEVE
(k( II - pc():)
EEE-
EECE
og
II Pe (k)
Σ
PPE is chosen from Eg (E*)
cEE.
ECCECE.
II (b)).
EEE*
Therefore
lim inf r% R-+00
lim k
Σ
II
Pe(k)
Q
nEQ
lim inf II
Pk(k)
Q
1-
QEQ
CEE-
2 QQ
lim inf (k R
QEQ AEF
1
1==1.
=
Q
REQ
This shows that limg-soo Tk 1 and completes the proof of the Theorem.
15

---

Under review as a conference paper at ICLR 2020
B FREQUENCY DISTRIBUTION OF DEGREE
50
50
Before pruning
Frequencies (thousand)
Before pruning
Frequencies (thousand)
40
40
After pruning
After pruning
30
30
20
20
10
10
0
100
200
300
16
24
32
40
48
56
64
# In-coming edges
# Oul-going edges
(a) In-degree
(h) Out-degree
Figure 6: Frequency distributions of in-degree and out-degree of proximity graph before and after pruning over SIFTIM.
C INTERNAL OF APG LEARNING PROCESS
K=1. T=0.8, A=1
T00.107, A-0.583
k-15,
T-0.112 1.0.5
Figure 7: Distribution of keep probability at different steps of the optimization.
16


Reviews:
[{"review_id": "rJe2gvhV9S", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper studies the problem of improving proximity graph for nearest neighbor search. It formulates the task of pruning the graph as a problem of learning annealable proximity graph. A hard pruning processes is used after the learning process, and the results shows that the proposed method can reduce 50% of the edges and speed up the search time by 16-41%.\n\nThe biggest concern I have is how to evaluate the performance.  The proposed method is mainly based on the comparison with [Malkov 2016], which did not use an extra training set to learn the NPG as proposed in this paper. So it is not surprising the proposed method will perform better. I would like to see more comparisons with at least the following methods: (1) a heuristic pruning strategy (2) the state of the arts of tree based NN search and hashing based search (3) the recent work in proximity graph [Fu et al 2019]\n\nTo summarize, I think the paper studies an important problem and the proposed method is reasonable. However, I cannot be convinced it is the state of the art for large scale nearest search unless I see more comparisons in the new version. \n\nDetailed comment:\n- in section 5.2, \"APG reduce the number of edges by 2 times \" -> \"APG reduce the number of edges by 50\\%\"", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I did not assess the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I made a quick assessment of this paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "SJlUc3mVtH", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "\nSummary:\nThe authors propose an extension of proximity graphs, Annealable Proximity Graphs (APG) for similarity search. APG augments pre-built proximity graph with a learnable weight and a keep probability with each edge in the graph which are updated in an iterative manner. This allows identifying important edges while preserving graph monotonicity which is important for search efficiency. All the edge weights are initialized with uniform weights and are updated using a stochastic optimization algorithm. Once the optimization finishes, edge weights are ranked and less important edges are pruned as per the desired pruning ratio. The authors also theoretically prove convergence and correctness of their proposed algorithm. The results demonstrate that APG maintains almost the same accuracy while decreasing search time by 21-41 %. Overall, I find that the proposed method and its results are convincing. The paper is very well written and all steps are rightly justified. \n\nQuestions:\n1. In Figure 4, for all three datasets, the performance starts to drop exactly after 50%. Can you provide any intuition behind this consistent pattern across all datasets?\n\n2.  In Figure 7(b), can you explain the cause behind the discontinuity of the “Before Pruning” plot?\n", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}, {"review_id": "S1gwLVxpYB", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper suggests an approach for learning how to sparsify similarity search graphs. Graph-based methods currently attain state of the art performance for similarity search, and reducing their number of edges may speed them up even further. The paper suggests a learning framework that uses sample queries in order to determine which edges are more useful for searches, and prune the less useful edges. This is a sensible and potentially useful approach in line with the recent flurry of work on improving algorithms with tool from machine learning.\n\nWhile I like the overall approach and believe it could work, the experiments seem to have some weaknesses:\n\n1. It is not clear to me why Table 1 contains only UPG and APG with pruning half the edges, without natural pruning baselines like uniformly subsampling the edges by a factor of half, or constructing the graph with half as many edges to begin with. Both of these baseline appear in the plots afterwards, which suggest very similar performance to APG, and it would be interesting to see the numbers side by side. The numbers for UPG and APG alone do not say much: the fact that the number of edges drops by half and the search speed drops by somewhat less than half are inevitable artifacts of the construction. The interesting part is the effect on the accuracy, and its quality is hard to assess without comparison to any baselines.\n\n2. The plots leave the impression that the proposed algorithm does not actually perform that well. It is superior on SIFT, but does not improve performance on GloVe, and is outperformed on Deep1M. This seems to render the textual description of the results somewhat overstated, if I read it right (is it referring only to SIFT?).\n\nIn conclusion, while I am optimistic about the paper and the approach, I am tentatively setting my score below the bar in light of the somewhat unsatisfactory experimental performance. The paper would be significantly helped by showing non-negligible improvement on more than one dataset or in more settings.\n\nOther comments:\n1. What is NSG? I could not find a spelling out of the abbreviation nor a reference.\n2. HNSW-sparse and HNSW-rand are very nearly impossible to tell apart in the plots. I suggest using a clearer visual distinction.\n3. \"Interestingly, pruning provides the benefits of improved search efficiency\" - isn't that the point of pruning?\n4. It is curious that using HNSW with R=32 instead of R=64 hurts the performance so much on Deep1M, while it has hardly any effect on SIFT and GloVe, do you perhaps have an explanation for this result?\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proposes a method to prune edges in proximity graphs for faster similarity search. The method works by making the graph edges annealable and optimizing over the weights. The paper tackles an important and practically relevant problem as also acknowledged by the reviewers. However there are some concerns about empirical results, in particular about missing comparisons with tree-structure based algorithms (perhaps with product quantization for high dimensional data), and about modest empirical improvement on two of the three datasets used in the paper, which leaves room for convincing empirical justification of the method. Authors are encouraged to take the reviewers' comments into account and resubmit to a future venue. 


Decision: Reject