Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 6: Weak Accept
review_content: 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%.

The 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]

To 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. 

Detailed comment:
- in section 5.2, "APG reduce the number of edges by 2 times " -> "APG reduce the number of edges by 50\%"
review_title: Official Blind Review #1

final_score: rating: 6: Weak Accept
review_content: 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.

While I like the overall approach and believe it could work, the experiments seem to have some weaknesses:

1. 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.

2. 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?).

In 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.

Other comments:
1. What is NSG? I could not find a spelling out of the abbreviation nor a reference.
2. HNSW-sparse and HNSW-rand are very nearly impossible to tell apart in the plots. I suggest using a clearer visual distinction.
3. "Interestingly, pruning provides the benefits of improved search efficiency" - isn't that the point of pruning?
4. 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?

review_title: Official Blind Review #3

final_score: rating: 8: Accept
review_content: 
Summary:
The 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. 

Questions:
1. 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?

2.  In Figure 7(b), can you explain the cause behind the discontinuity of the “Before Pruning” plot?

review_title: Official Blind Review #2

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