Diverse Graph-based Nearest Neighbor Search

We thank the reviewer for helpful feedback. Below we address specific comments and questions.

“The dual version has been studied with LSH-based solution (Abbar et al. 2013b) and the primal version is resolved in this work using graph-based index”

We would like to clarify that, in this paper, we give graph-based algorithms for both the primal and the dual version of the problem, whereas in prior work of Abbar et al that used LSH, only the dual problem was solved.

“Could you provide a complexity analysis of the initialization step and discuss how it impacts the overall query time.”

To clarify, the initialization does not depend on the query and thus needs to be run only once over all the queries. It is true that different values of $C$ require different initialization steps but only $\log \Delta$ such searches suffice. The runtime of the initialization algorithm is indeed $O(n^2)$. However, we present this initialization algorithm mostly as a backup option to handle very hard instances which we do not expect to occur in practice. In particular, in our experiments we simply sample random points and verify they are sufficiently diverse.

“Though graph-based indexes show advantages compared to hash-based solutions on standard ANNS, it is not well-understood that graph-based solutions will be better than hash-based solutions on diversity-awared ANNS. ... Could you add hash-based solutions baselines for diversity-aware ANNS?”

Because of their wide applicability of graph-based methods, the focus of this work is to provide diversity aware search that specifically uses the graph-based methods. Since many companies already use graph-based methods, switching to other methods is less preferable. For example, one product group may want to use a single (standard) indexing algorithm and depending on the query, either use standard search or diverse search.

That said, we also reached out to the authors of the diverse NNS using LSH-based methods and we were informed that they unfortunately no longer have the code or datasets, as those papers were written over one decade ago.

“While the proposed theory (Theorem 1.1) works on a general \rho, the empirical results consider the specific $\rho$ ('colorful' version), which clearly not align well to the theory.”

This special case of $\rho$ was motivated by the application where the goal was to show $k$ product ads to the user such that they all come from different sellers. It turned out that a more relaxed version, in which we require the number of ads from a single seller be bounded by at most $k’$, also works well for the user perspective. Thus, our experimental evaluation is focused on this case.

We note that the diversity metric \rho used in Abbar et al is different from ours - it is induced by the distance in one dimension. This demonstrates practical use cases that go beyond the colorful case. However, their data sets are unfortunately not available.

“The emprical setting is not clearly described. For example, since standard greedy search on graph will be much faster than diverse search, one can set r much larger than k to expect get better recall with post-processing. Also, since we consider k = 100, I wonder why we only set L = 200 since this value seems to be the default setting of graph-based index for k = 10.”

For the post-processing approach, we precisely do what you outline. We seek $r \gg k$ candidates using a vanilla search, and then run a diversification step as post-processing. We vary $r$ to as high as 1000 in this step. For instance: if we use the non-diverse build and do the standard search with a post-processing step (Baseline), to achieve >90% recall for Max per color = 10, the values of $r$ are roughly 800, 700 and 400 for Real, Arxiv and SIFT datasets respectively. For Max per color =1, the values of $r$ are roughly 1000 and 500 for Arxiv and SIFT datasets. However on the Real data set the baseline algorithm doesn’t even achieve 50% recall even for $r = 1000$. Apologies if this is not clear.

The $L$ parameter is what we use for indexing. It is pretty robust in the real world to the target value of $k$.

It would be great if you could point us to where $L = 200$ is the default setting for $k = 10$ in practical applications. The graph degree, and $L$ parameter are indeed tunable, but much more robust in our opinion than the parameters in other ANN approaches, across dataset dimension and recall target $k$. For example, we ran the experiments for the SIFT dataset (Max per color=1), using $L = 400$ during the index build, and the results were very similar to that in Figure 3 in the paper that was computed using $L = 200$.

“It might be better to move the proof to the appendix to have room to explain the algorithms in high levels.”

Thank you for your suggestion, we will move the proofs to the appendix and provide a high level overview of the algorithms and give further intuitions instead.

Thank you for your detailed feedback. However, I believe my concerns remain valid and significant

The paper proposes diverse-aware indexing and querying mechanisms for graph-based approximate nearest neighbor (ANN) search, where time complexity depends exponentially on the doubling dimension. The problem focuses on maximizing the diversity measure defined as the minimum value of \rho(p, p') for any pair p, p' in the returned set S.

From a theoretical perspective, the contribution is difficult to compare with standard locality-sensitive hashing (LSH), where complexity depends on the original data dimension. Additionally, the proposed indexing construction time of O(n^2) for the worst-case dataset is less favorable compared to LSH.

The practical setting of the paper considers the binary version \rho() \in {0, 1}. This relaxation reduces the theoretical significance for several reasons:

• Simpler solutions exist for the binary variant e.g. building different ANN index for different color, for each color getting a set of nearest neighbors, then forming the diverse-aware solutions based on these nearest neighbors. If the number of colors (e.g. sellers) is not large, or we merge several colors with small of number of points together, then several heuristic methods can outperform your proposed solution.

• The theory does not stand well on the binary relaxation of \rho() \in {0, 1} and C \in {0, 1}. For example, the initialization step (Line 262) might return NO solution with C = 1. I am not sure that Lemma 3.1 still holds in case C \in {0, 1}.

Regarding empirical results and settings, without comparing LSH solution with \rho \in [0, 1] is a big issue to me.

• Your proposed solution requires a new diverse-aware graph-based index (Alg 1), which means that we have to maintain two different graph-based indexes. The cost of building (diverse-aware) graph-based index is clearly larger than the cost of building (diverse-aware) LSH.

• On semi-synthetic data sets, I wonder why not considering any applications where \rho() \in [0, 1] (e.g. LDA to extract topics) so that we will have a fair comparison with Abbar et al. The setting that use embeddings and the binary variant of \rho() is not adequate to show the advantage of your work compared to Abbar et al. which has \rho() \in [0, 1]

Given the misalignment between theoretical analysis and practical settings, and the lack of comparison with LSH baselines on \rho \in [0, 1], I maintain my score.

Minor things:

• https://github.com/nmslib/hnswlib use ef_construction = 200 for k = 10.
• Heuristic method to solve the binary version: Given that the post-processing is around 2%, consider the color from {1, 2, 3} with prob 0.9 and {4, 5, ..., 1000} with prob 0.1, we can build 3 different indexes for color 1, 2 and 3. For the rest of data, breaking it into 100 clusters and build each index for each cluster. I think such solution can solve the color version for k = 100.

“What value of r do you use for the baseline method in the experiments and is it the same for each dataset?”

As per Figures 2 and 3, for the baseline method, the crucial parameter we vary at search time is the value of $r$, how many candidates to retrieve, before a diversity-aware post-processing. Higher $r$ gives higher recall. In all these experiments, the value of $r$ ranges between $100$ and $1000$. The value of $r$ depends not just on the value of $k$, but also on how non-diverse the local ball around the query is.

“Could you verify that the latencies you provide in Figures 2 and 3 are correct?”

We reran the experiments on the SIFT dataset with Max Per Color =1 and we observed similar latencies as reported in Figure 3. There are multiple reasons why the latency numbers don’t meet your expectation: Firstly, since we are using all 48 threads for search, this will maximize throughput (queries per second) while hurting latency (which is the time taken per query), due to resource contention between various threads. In case there is ambiguity, we would like to stress that mean latency is not 1/QPS, but rather 48/QPS, so more threads would not directly reduce latency. We re-ran the experiments with 1 thread and notice a 4-5X gain in latency across the board for all experiments. However, we prefer reporting numbers with higher thread utilization because real-world scenarios indeed involve multiple threads searching the index simultaneously. Another reason for higher latencies is that, to output a diverse set of results, one needs to fetch a large number of items. Finally, a small contribution (2%) to the increase comes from the additional post-processing step for the baseline algorithm.

“Is 20 the total number of sellers in the real-world data set or are there more?”

There are more. In the pie chart we are only showing the distribution of the top 20 sellers. The total number of sellers is approximately 2K.

“On the semi-synthetic data sets, I would also expect vanilla DiskANN to perform relatively much worse when k’= 1 compared to when k’= 10. Can you hypothesize why that is not the case?”

It is indeed worse with $k’=1$ compared to $k’=10$ for both the Arxiv and SIFT semi-synthetic datasets. For example, for the Arxiv dataset, the recall for $k’=10$ is around 90% for a latency of 60ms, while it is only 60% for the $k’=1$ case with the same latency bound. A similar trend is seen for the SIFT dataset also. Perhaps the real-world distribution is even more skewed (6 sellers account for 90% points, so seeking 100 diverse candidates for $k’=1$ is much harder than 10 diverse results for $k’=10$), so that shows in the results. In semi-synthetic, this measure is only 80% dominated by the big sellers.

We thank the reviewer for the helpful comments. Below we address specific comments and questions.

“The analysis is quite similar in parts to the earlier work of Indyk & Xu (2023) in studying graph-based ANN methods.”

While the overall structure of the analysis is similar to that of Indyk&Xu, the algorithms and the analysis build significantly on top of that. Even solving the problem for the much simpler case of k'=1 and binary metric $\rho$ turned out not to be easy to solve and analyze. In particular, coming up with the “right” notion of an iterative step in the search algorithm (lines 10…14) and quantifying the progress that such a step makes (Lemmas 3.3 and 3.5) took a fair amount of effort. Additional effort was needed to generalize the algorithm to arbitrary diversity metrics $\rho$ and $k’>1$.

“However, I do not see how the proposed heuristics in Algorithms 5-7 are based on the theoretical version presented in Algorithms 1 and 2. … Instead, the proposed empirical algorithm seems to be a relatively straightforward modification of the DiskANN algorithm ...”

Our heuristic algorithm is indeed a simple generalization of DiskANN with diversity in graph build and graph search and prune. We consider this minimal code modification to be a positive aspect of our result because it makes it easier for the diverse algorithm to be actually implemented for various use cases.

To better illustrate the connection between the theoretical and heuristic algorithms, below we present a simplified variant of our theoretical algorithm that works only for the colorful case, for the simple case of $k’=1$.

• In the indexing algorithm, in order to specify the out-neighbors of a point $p$,

  1. We sort and keep all the other points in a list $L$, and as long as $L$ is not empty we take the closest point $u$ to $p$, and connect $p$ to $u$.
  2. We then remove all points $v$ from $L$ such that $v$ is close to $u$ and either
  • color[$v$] = color[$u$]
  • Or we have already connected $p$ to $k$ points of different colors in close neighborhood of $v$.

• In the search algorithm,

  1. We start with $k$ vectors $a_1,...,a_k$ that all have different colors.
  2. As long as there exists a point $a_i$ that has a neighbor $v$ such that
     • $v$ is closer to the query and
     • $v$ has a different color than all other $a_j$; we replace $a_i$ with the closest such neighbor to the query.

We hope that the above pseudocode emphasizes the similarities between our theoretical and practical algorithms. If the reviewer agrees, we will add this description to the paper. (We did not include it earlier to avoid repetition).

“What is the rationale for choosing the distributions for the semi-synthetic datasets?”

We believe that it is indeed important to consider such skewed distributions. For example, in the real-world dataset, the top six colors account for nearly 90% of all vectors, which is a much more top-heavy setting than our synthetic distribution. Also, while one could take the two-index approach you suggested for our highly specialized distribution, we think it is hard to generalize this to other distributions, including our real-world dataset.

“Referring (line 146) to the difference between the main bound in the paper (Theorem 1.1) and the bound presented by Indyk & Xu (2023), you say that the latter does not depend on k or k’ as these parameters do not exist in the standard NN formulation.”

For the regular approximate nearest neighbor search problem formulation, the theoretical results typically only guarantee an approximation ratio for the top-1 returned neighbor. In particular, Theorem 3.4 in Indyk-Xu'23 indeed considers only the case of $k=1$. Unfortunately, we do not know how a generalization to $k>1$ would look like.

“Your results depend on the aspect ratio $\Delta$ which can grow arbitrarily high when the minimum distance between any two points gets closer to $0$”

Indyk-Xu'23 show that log Delta dependence is unavoidable for DiskANN-based algorithms, even for one-dimensional point sets. Please see Theorem 3.5 and its proof in the aforementioned paper for the reasoning.

“Roughly how much does the indexing time of your practical diverse indexing method differ from that of DiskANN?”

As discussed in the experiments section (4.2, Build Diversity Parameter Ablation), we have a tunable parameter m which enforces that an edge needs to be blocked by edges of $m$ different colors to not be added to the graph; this parameter is a proxy for $k/k'$ value which is equal to the number of different color edges that needed to be added in the ball. Higher value of m means that we are building the graph to enable higher diversity. In our experiments, higher values of $m$ yield higher build time. In the results reported in the paper, we choose $m=3$ for which the index build time is at most 2 times higher than the non-diverse build time. For $m=10$, the index build time is at most $2.6$ times higher.

Thank you for providing additional feedback and also for increasing your score.

According to the targeted application in shopping and search (see lines 417-421), we argue that real-world datasets are more likely to be skewed because similar products tend to be sold by the same seller, and each seller’s products cover a neighborhood within the product space. Therefore, it is reasonable to expect that the distributions are skewed, as supported by our real datasets. We will consider additional experiments on real-world datasets in future versions of our paper.

Per your initial suggestion, we have run our experiments on a different, correlated distribution and observed similar trends. Even though the distribution is globally not skewed, in any local neighborhood, most of the points belong to one color, according to our sampling procedure. Indeed, we partition the points into regions using random hyperplanes, and for each point within a region, choose a dominant color with 0.8 probability, and a uniformly random color out of 1000 colors with remaining probability. We see that our methods give good gains over the baseline approach.

Results: We have the full plot for SIFT dataset, Max per color=1, which we cannot post as a comment here. However, e.g. at latency 4 our algorithm is at over 95% of Recall@20, whereas the baseline algorithm is around 60%. At latency 6, we are at 98% whereas the baseline is at 85%.

We thank the reviewer for helpful feedback. Below, we address specific comments and questions.

• “The writing appears messy in many places.”

Apologies if the writing was unclear. We will fix the $OPT_k$ confusion (we defined $S(q)_k$ but did not extend this definition to $OPT_k$). Please let us know any other comments.

• “I'm slightly disappointed that allowing a factor of k′ fuzziness in the diversity constraint only serves to reduce the running time linearly in $k'$.”

For the case when $k=k’=1$, the diverse (approximate) nearest neighbor problem specializes to the regular (approximate) nearest neighbor. In this case the runtime bounds of our algorithm are qualitatively the same as the bounds for the regular approximate nearest neighbor in Indyk-Xu’23, but with a constant $8$ instead of $4$. Thus, we think it is unlikely that one could get a much larger improvement (say, polynomial in $n$) for other values of $k’$, unless the bounds for the regular version of the problem are improved as well. We also note that relaxing $k’$ to be greater than $1$ plays a very different role from the distance-based relaxation in approximate nearest neighbor.

• “In this case when $k’=1$ does it just become the nearest neighbor problem?”

When the diversity metric is binary (as in the experimental section), the case of $k’=1$ imposes the constraint that each of the $k$ points returned by the data structure must have a different color. To give an example, consider the main application motivating this paper, where the set of points is a collection of product ads shown to the user, each coming from a specific seller (e.g. Amazon, Ebay, etc). Furthermore, the user can be shown up to $k$ ads. Then setting $k'=1$ means that we require all the $k$ ads that we show to the user to come from different sellers, i.e., no seller should appear more than once. On the other hand, setting $k'=k$ means that we do not have any diversity constraints on the sellers.

In reality, setting $k'=1$ is stricter than necessary from a user’s perspective. This motivated the relaxation.

• “The experiment design is more or less limited. The authors only uses the binary distance metric.”

The case of binary diversity metric was in fact the main practical motivation for this paper - we wanted to design a fast algorithm that reports $k$ products such that no seller appears too often in the list. In this setting the diversity metric is binary, but the distance metric is Euclidean.

• “I'm also curious about how fast the running time scales with high dimensions in practice.”

The graph construction algorithm we use for the baseline index, as well as our diverse-build, scales linearly in the ambient dimension d of the dataset. This is because the algorithms use the distance metric as a black-box, and evaluating the Euclidean distance between two points takes time proportional to $d$.

On the other hand, one could imagine more complex experiments varying the intrinsic dimension of data. However, executing such an experiment with real data is difficult, as it would require a sequence of related data sets with varying intrinsic dimensionality.

• “It is nice observation that the greedy algorithm in Gonzalez (1985), combined with an initialization, can lead to desirable results in diversity guarantees.”

Thank you. We want to clarify though that we use the greedy algorithm only as one component in the pruning process. At a high level, to find the neighbors of a node $p$, we partition the space into balls of various radii, and use greedy within each ball and only connect $p$ to those $k/k'$ points returned by greedy. We then need to verify that such a sparsification is sufficient for our search algorithm to converge to an approximately optimal solution. (shown in lemma 3.3, lemma 3.5, and proof of theorem 1.1).

• “I haven't checked all the details, but the techniques used do not seem to be deep.”

We agree that the final algorithms are relatively simple (which we view as a plus, as simple algorithms are easier to implement). However, we believe that the simplicity of the final algorithms might have obfuscated several challenges that needed to be overcome. Even the algorithm for the simple case of $k'=1$ and binary metric $\rho$ metric turned out to be not easy to design and analyze. In particular, coming up with the “right” notion of an iterative step in the search algorithm (lines 10…14) and quantifying the progress that such a step makes (Lemmas 3.3 and 3.5) took a fair amount of effort. Additional effort was needed to generalize the algorithm to arbitrary diversity metrics $\rho$ and $k’>1$.