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