On the adversarial robustness of Locality-Sensitive Hashing in Hamming space

Nearest neighbor search is one of the most fundamental data structure problems in machine learning. In particular, the development of efficient data structures for nearest neighbor search in high dimensions is a challenge and finding the exact nearest neighbor often requires a linear scan over the data [35]. Therefore, people also started to investigate approximate nearest neighbor search. One important technique to design approximate nearest neighbor data structures is locality sensitive hashing (LSH) which has been introduced in the seminal paper by Indyk and Motwani [22]. LSH is widely used in many applications including music retrieval [33], video anomaly detection [39], and clustering [26] (see also the survey [23] for further examples).

LSH is a randomized data structure and as such its performance guarantees depend on its internal randomness. The standard analysis assumes an oblivious adversary, i.e. queries may not depend on answers to earlier queries for the guarantees to apply. What are the consequences, if we would like to have the LSH performance guarantees when LSH is used as a data structure in an algorithm? It essentially says that for the guarantees to hold, the algorithm must be able to specify at a single point of time a set $Q$ of query points and it gets all answers to these query points at once. Then it can do any computation with the answers but it may not ask further queries. Such a restricted functionality significantly limits the strength of the guarantees provided by LSH as more often than not future queries depend on the result of earlier queries. Therefore, it would be great to better understand the LSH guarantees in the adaptive setting. Even though some work on LSH such as constructions without false negatives [31, 1] (see also Related Work for further discussions) are motivated by this question, there is still a lack of knowledge about how resilient standard LSH data structures are if we allow adaptive adversaries.

In this paper, we address this question by developing a randomized query scheme (adversarial algorithm) for LSH under the Hamming distance with the goal of efficiently generating a query that makes LSH return an incorrect answer. We show that for a wide setting of parameters, if a point set has a somewhat isolated point, then we can make LSH have a false positive (that is, returning no point while there is a near point) much faster than this would happen with non-adaptive queries.

Let us discuss this further on a simple example. We may use LSH for an approximate version of a $1$-nearest neighbor classifier (see [2] for a related study), that is, we store the training set in an LSH data structure and on a query we return the label of the (approximate) nearest point in the training set that is returned by LSH. In this setting LSH will satisfy its standard guarantees when the choice of queries does not depend on previous answers. This happens, for example, when queries are independently sampled from a fixed query distribution. However, one could potentially design a carefully engineered sequence of queries to construct queries on which the algorithm returns an incorrect answer. This is particularly problematic if the algorithm is used for a sensitive task and relies on strong guarantees.

Our results. Our main result is an algorithm for generating an adversarial query:

Note that to find such a point through random sampling, one would have to make $\Omega(1/\delta)$ queries in expectation Theorem 3.3, which is exponentialy slower in $\delta$ than the proposed adversary. We then evaluate our data structure experimentally in various settings to understand how the efficiency and effectiveness of our approach depends on the various parameters.

Monte-Carlo Locality-Sensitive Hashing. Most of the work dedicated to Locality-Sensitive Hashing was done in the Monte-Carlo model, which we consider to be the standard model in this paper. That is, the goal is to construct a data structure with deterministically bounded query time that correctly answers the queries with high probability. Constructions of locality-sensitive hash families are known for several different metrics, including Hamming distance [22, 7], $\ell_{1}$ [19], the Euclidean metric [3], Jaccard similarity [13, 18], angular distance [4, 25, 29] and more. Asymmetric LSH solutions, which allow to reduce query time at the expense of an increase in space, or reduce space at the expense of increasing query time, have received significant attention in the literature and are quite well understood by now [32, 24, 15, 6]. Distance sensitive hash families, where collision probabilities are not necessarily monotone in the distance between points being hashed, have also been constructed [9]. Data-dependent results, which adapt the locality-sensitive hash family to the dataset to achieve better exponents, are also known [5, 6].

Las-Vegas Locality Sensitive Hashing. In an attempt to avoid the problem of having false negatives, another line of work seeks to construct LSH instances that answer the queries deterministically correctly, but the running time is a random variable and guarantees are usually on its expectation. It was first shown by [31] that such a scheme exists, however this scheme for general parameter settings requires more space than the standard LSH. A later work by [1] achieves the same space-time trade-off as in [22]. [36] further improves on it for $\ell_{p}$, and offers a data-dependent construction following [3]. Although Las Vegas constructions avoid the problem of having false negatives, their guarantees still hold only against an oblivious adversary. It is entirely possible that an adaptive adversary can find a sequence of queries with an average response time much larger than what is guaranteed against an oblivious adversary. In any case, investigation of such adversaries lies outside of the scope of this paper.

Robustness to adaptive adversaries. One of the main motivations of this paper is to study the behavior of a classic data structure solving against an adaptive adversary. One of the most studied class of algorithms that is relevant to our paper is linear sketches. Some of the notable early works here include [20], which proposed an efficient attack on the linear sketch for norm estimation, and [30], which proposed deterministic sketch constructions for a range of problems that work for all inputs and provide lower bounds on their size. In [27] an adversarially robust approach to solving approximate nearest neighbor in Hamming space is proposed, which does not use LSH. It is improved upon by [14], which gives a robust construction for vector $\ell_{p}$-norm estimation, for $0<p\leq 2$. On the other side of the spectrum, an adaptive attack on CountSketch was proposed by [17, 16], with the latter also proposing a robustifycation of this sketch.

Another fruitful line of work covers the use of differential privacy to make existing algorithms more robust against adaptive adversaries [10, 37, 21, 11, 8]. The main idea is to use differentially private mechanisms to hide the random bits of the algorithm from the adversary. This approach turned out to be applicable to a wide range of estimation problems.

For $x>0$, $\log x:=\log_{2}x$ will denote binary logarithm of $x$. For $n\in\mathbb{N}$, $[n]:=\{1,\ldots,n\}$ will be the set of integers from $1$ to $n$. For a point $p\in\{0,1\}^{d}$ and $i\in[d]$, $p_{i}$ is the value of the point $p$ along $i$-th dimension. For two points $p,q\in\{0,1\}^{d}$, $\operatorname*{dist}(p,q)=\sum_{i\in[d]}|p_{i}-q_{i}|$ is their Hamming distance.

Basics of Locality Sensitive Hashing. Locality sensitive hashing is a technique to derive randomized data structures for near neighbor search. This can be formalized as follows. A (randomized) data structure for the $(c,cr)$-approximate near neighbor problem in a metric space $(X,\operatorname*{dist})$ preprocesses a point set $P\subset X$ in such a way that for a query point $q\in X$ with probability at least $1-\delta$ it (a) returns $p\in P$ with $\operatorname*{dist}(p,q)\leq cr$, if there is $p^{\prime}\in P$ with $\operatorname*{dist}(p^{\prime},q)\leq r$, (b) returns $\bot$, if there is no point $p\in P$ with $\operatorname*{dist}(p,q)\leq cr$, and (c) returns either $\bot$ or $p\in P$ with $\operatorname*{dist}(p,q)\leq cr$, otherwise. Here $\delta$ is the failure probability of the data structure. In this paper, we will consider the Hamming space, i.e. $X=\{0,1\}^{d}$ and $\operatorname*{dist}$ is the Hamming distance and in the following discussion we focus on this setting.

The key component of LSH schemes is a locality-sensitive hash family. The idea behind them is that a function from such a family is more likely to map close points to the same bucket than far ones.

For a $d$-dimensional Hamming space $\{0,1\}^{d}$, the locality-sensitive hash family has a very simple form [22]. Let $\mathcal{H}=\{h^{(i)},i\in[d]:\forall p\in\{0,1\}^{d},h^{(i)}(p)=p_{i}\}$ be the elementary hash function family. That is, it consists of hash functions $h^{(i)}:\{0,1\}^{d}\to\{0,1\}$, which project points from $\{0,1\}$ to their $i$-th bit. It is known that

Indyk and Motwani give the following guarantee (assuming that the points come from a $d$-dimensional space):

In the following, we briefly describe the construction of an LSH data structure, which can be used to prove the above theorem. An LSH data structure consists of a multiset of $G$ of $L$ hash functions in the product $\mathcal{H}^{k}=(h_{1},h_{2},\ldots,h_{k}),h_{j}\in\mathcal{H},j\in\{1,2,\ldots,k\},$ i.e. $G\subseteq\mathcal{H}^{k}$ In other words, each element of $G$ is constructed by sampling a sequence of $k$ elementary hash functions $h_{1},\ldots,h_{k}$ uniformly at random from $\mathcal{H}$ and then setting $g:\{0,1\}^{d}\to\{0,1\}^{k}$, $g(x)=(h_{1}(x),\ldots,h_{k}(x))$ to be their concatenation. That is, $\forall p\in\{0,1\}^{d}$, $g(p)=(h_{1}(p),\ldots,h_{k}(p))$. The intuition is that concatenating hash functions from $\mathcal{H}$ allows to exponentially increase the gap between probabilities $p_{1}$ and $p_{2}$ in such a way that if we sample $L$ hash functions then two points $p,q$ with distance at most $r$ are likely to have at least one $g_{i}$ with $g_{i}(p)=g_{i}(q)$ and we can recover the point. At the same time, the number of points with $\operatorname*{dist}(p,q)>cr$ and $g_{i}(p)=g_{i}(q)$ will be small, so that the recovery can be done efficiently.

The proof of [22] essentially follows by choosing the parameters $k$ and $L$ appropriately, which is done as follows. We set $p_{1}=1-r/d$ and $p_{2}=1-cr/d$ such that $\mathcal{H}$ is $(r,cr,p_{1},p_{2})$-sensitive. We define $\rho=\frac{\log 1/p_{1}}{\log 1/p_{2}}$ and $\ell=n^{\rho}$. For an input set $P\subseteq\{0,1\}^{d}$ of $n$ points we set $k=\lceil\log_{1/p_{2}}n\rceil$. For this setting of parameter, we get the guarantees provided in the above Theorem. In order to get a smaller failure probability we set $L=\lceil\lambda\ell\rceil$, which results in a failure probability of $1-\exp({-\Omega(\lambda)})$.

One particular property of the above LSH construction is that there is a chance of incorrectly returning that there is no near point (i.e. returning $\bot$). Such an incorrect answer will be called a false negative.

Defining the adversary. The goal of this paper is to study how one can force LSH to return a false negative by doing adaptive queries. We take the role as an adversary and our goal is design an adversarial algorithm that has access to an LSH instance and quickly forces it to return a false negative. In particular, we provide guarantees on the number of queries required until LSH makes a false negative.

In the following, we will describe our formal setting. Our LSH instance is constructed according to the scheme described in Section 3. Recall that this LSH scheme samples a multiset $G$ of $L$ hash functions $g_{1},\dots,g_{L}$ uniformly at random from the set of allowed hash functions of the form $g:\{0,1\}^{d}\rightarrow\{0,1\}^{k}$ with $g(p)=(h_{1}(p),\dots,h_{k}(p))$ for elementary hash function $h_{j}$. The LSH scheme receives as input a point set $P\subseteq\{0,1\}^{d}$ of size $n$ and parameters $n,d,c,r$ and $\lambda$ and calculates $\ell,\rho,L$ and $k$ as described earlier. Our adversarial algorithm may use the input point set $P$, its size $n$ and dimension $d$, and the parameters $r,c$ and $\lambda$ of the LSH scheme and can interact with the LSH data structure using the procedure 1 described below. That is, the LSH data structure is in a black box and the only interaction uses procedure 1. In particular, the randomness used to construct the LSH instance and so the hash functions is unknown to the adversarial algorithm.

Note that in an LSH implementation one would store all buckets of $g$ in a hash table. This way, line 3 can be implemented without going through all points. We also remark that since we do not have control of the parameters and point set our adversarial algorithm cannot be expected to work in all settings (for example, if the number of hash functions is very large, then no false negatives exist).

Define the set $\textsc{Coll}(p,q)=\{g\in G:g(p)=g(q)\}$ to be the set of hash functions in $G$ that collide on $p$ and $q$. Our algorithm starts with finding a point $z$ in the dataset such that any other point is at least at a distance of $2cr$ from $z$. We assume that such a point exists, and we experimentally explore the case when it doesn’t in Section 6. We also show that this assumption is reasonable for a randomly chosen point set in Lemma A.7. We refer to $z$ as origin point.

Algorithm outline. The idea of the algorithm is to query a random point $q$ at distance $r-t$ such that the expected number of hash functions hashing $q$ to the same bucket as $z$ is at most $t/2$. We show that this is true when $t=2e^{2}(\lambda+1)$, which is the value we use throughout this section. This implies that with a constant probability $|\textsc{Coll}(q,z)|\leq t$. The algorithm now does $t$ iterations and in each of them it moves point $q$ away from $z$ by flipping one bit in it in such a way that the size of the set $\textsc{Coll}(q,z)$ also decreases by at least $1$.

To find this bit, the algorithm flips bits in $q$ at $cr-\operatorname*{dist}(q,z)$ randomly chosen positions among those where $q$ is equal to $z$ and obtains a point $\tilde{q}$. $\tilde{q}$ is located at distance $cr$ from $z$, so with a high probability $\textsc{QueryLSH}(\tilde{q})=\bot$. Now consider a path between $q$ and $\tilde{q}$, i.e. a sequence of points starting with $q$ and ending with $\tilde{q}$, where each two consecutive points differ in one bit and where each point is further away from $z$ than its predecessor. Because $\tilde{q}$ doesn’t hash with $z$ but $q$ does, there are two consecutive points $q^{\prime}$, $q^{\prime\prime}$ on this path with the same property. Consider the bit where they differ. Because $\textsc{Coll}(q^{\prime},z)\neq\emptyset$ and $\textsc{Coll}(q^{\prime\prime},z)=\emptyset$, this bit must lie in the support of all functions in $\textsc{Coll}(q^{\prime},z)$.¹¹1 for an elementary hash function $h^{(i)}\in\mathcal{H}$ its support is defined as the set $\{i\}$. For a hash function $g\in G$, $g=(h_{1},\ldots,h_{k})$ its support is the union of supports of $h_{1},\ldots,h_{k}$. Therefore, by flipping it in $q$ the algorithm removes these functions from $\textsc{Coll}(q,z)$. It is easy to see that at the end we get a point $q$ at a distance at most $r$ from $z$ such that $\textsc{Coll}(q,z)=\emptyset$, so $\textsc{QueryLSH}(q)=\bot$ and $q$ is a false negative.

In the following we prove Lemmas 4.3 and 4.4, which are the key results underpinning the correctness of our algorithm. Lemma 4.3 essentially shows that a point $q$ sampled at distance $r-t$ collides with $z$ in at most $O(t)$ hashings with constant probability. Lemma 4.4 that says that if we move this point randomly and monotonically away from $z$ to distance $cr$, it will not hash at all with $z$.

A key property of these lemmas is that, unlike in the standard analysis of LSH, we fix the hash functions and sample points at random. This gives us a different perspective on how LSH behaves when queried with random points, which reflects the fact that our goal is to construct an adversary for LSH.

First, we state some intermediate results bounding the size of $k$ and the support of hash functions. Their proof is given in Appendix A.

The next two lemmas lower bound the size of the support of hash functions in LSH when they are chosen as described in Section 3. We now show the first lemma, which bounds the number of hash functions hashing a point at distance $r-t$ from $z$ in the same bucket with $z$. We outline the proof below, and present the full proof in Section A.1.

We now prove the second lemma, which bounds the probability that a point at distance $cr$ will be hashed with the origin.

As was mentioned in Section 2, there already exists large literature on the robustification of LSH, many of which work against our adversary. In particular, we highlight [1], which provides a false-negative-free Las-Vegas type data structure with query time $dn^{1/c+o(1)}$ and used space $dn^{1+1/c+o(1)}$, achieving the same asymptotic performance as [22], as well as [14], which can be applied to LSH to guarantee perfect robustness by paying $O(d)$ times more space.

However, both approaches are not perfect within the same parameter bounds, as approach of [1] doesn’t give any guarantees on query time in this setting, and the space usage of [14] is too prohibitive in settings with large $d$. We experimentally investigate how the latter, and a construction based on differential privacy, fares against our adaptive adversary when the available space is limited in Experiment 6 in Appendix C. Interestingly, these defences perform well in this setting, which suggests that they might be reasonably effective even against a general adversary.

The goal of this section is to verify the efficacy of our adversary on real datasets, where an isolated point does not necessarily exist, and for parameter configurations outside of the guarantees of Theorems A.4 and A.6.

Implementation details. Our implementation of LSH follows Algorithm 1 in Section 3 [22]. To summarise, given a query point $q$, we iterate through all points in the dataset that hash together with $q$ under some hash function, then return the first one which lies at distance at most $cr$ from $q$, and return nothing if there is no such point. The adversary is implemented according to Algorithm 3.

Experiment 1: Influence of parameters on success probability. The goal of this experiment is to explore within which parameter setting the algorithm works. For this experiment we use synthetic datasets, since for them we can easily vary the number of points and dimensions. We use two datasets:

Zero. This dataset entirely consists of $n$ copies of the all-zero point. This dataset is the easiest for our algorithm to find a false negative in, as it is equivalent to a dataset containing only a single point, which would automatically be isolated.

Random. Each point is sampled i.i.d. uniformly, with each bit having a $1/2$ probability to be set to $1$.

For each point on the plots, the experiments were run $1000$ times, and the result is the mean of the associated values. Plots contain error bars computed as standard error of the mean, but sometimes they are too small to be visible.

The parameters that we vary are $n$, $d$, $r$, $\lambda$, $c$ and $t$. Each parameter is changed individually. The default setting of parameters is $n=1000$, $d=300$, $\lambda=4$, $r=30$, $c=2$. The origin point $z$ is picked at random. The offset $t$ is set to $r$, or, in other words, the initial point $q$ is initialized to be equal to $z$. This is different than what was used in Algorithms 2 and 3. However, the intuition is that if instead of setting $q$ to be a random point at distance $2e^{2}(\lambda+1)$ from $z$ we set $q=z$ and then move it away from $z$ in a way that ensures that the size of $\textsc{Coll}(q,z)$ decreases for every changed bit, the probability that the algorithm will find a false negative query would only increase. This intuition ends up being supported by the experiment results.

The results are presented in Figure 1. The sixth subplot, counting left-to-right and top-to-bottom, supports the claim that we just made: the lower the starting distance of the point $q$, which is equal to $r-t$, the higher the success probability of the algorithm. The first and fifth subplots are straightforward. The number of points $n$ has a very weak effect on the success probability. Parameter $c$ also has a weak influence if it is large enough, and when it is small it is unlikely that a point at distance $cr$ does not hash with $z$, see Lemma 4.4. The drop in probability on the left-hand side of the third subplot where the near radius $r$ is varied and the right-hand side of the fourth where $\lambda$ is varied can be explained by the fact that a random point at distance $r$ has in expectation $\Omega(\lambda)$ hash functions hashing it with $z$. Hence, intuitively, for it to be possible to eliminate all collisions with $z$, it must be that $t\geq\Omega(\lambda)$, which also implies that $r\geq\Omega(\lambda)$ is necessary.

Experiment 2: Efficiency across datasets. In this experiment we measure how well our algorithm performs on a variety of different datasets. We use the datasets from Experiment 1, as well as one additional synthetic dataset and 3 datasets with real data. The new synthetic dataset is Sparse random. Each point there is generated by independently sampling each bit to be $1$ with probability $1/15$, and to be $0$ otherwise. The remaining datasets are: We use embeddings of the data sets MNIST [28], Anonymous Microsoft Web Data (MSWeb) [12] and Mushroom [34, 38] into Hamming space. For MNIST we flatten the images into vectors whose Boolean variables indicate the presence of a pixel. For MSWeb and Mushroom we use one-hot encoding to map the data into Hamming space. A more detailed description can be found in the Appendix C.

Due to computational constraints, we choose to limit the size of each dataset to at most $10000$. For MNIST and MSWeb we only use the first $10000$ points. We use all $8124$ points in Mushroom. For the synthetic datasets we generate $10000$ points with the dimension $300$, which is about the same order of magnitude as the dimensions of real datasets. We choose a setting of parameters with which our algorithm has a good chance of success as per the results of Experiment 1. As the number of dimensions varies depending on the dataset, we set $r=0.15d$. $c=2$, $\lambda=4$ and the starting distance is $0$ on the second subplot. Otherwise, we use the same setup as Experiment 1, except that for fixed datasets the origin point is the first one in the dataset. On the first subplot the starting distance is measured as a fraction of $r$. On the second subplot the goal of the algorithm is to find a query to the LSH data structure that returns $\bot$ at a distance from the origin specified by the $x$ axis as a fraction of the $cr$. The dashed black vertical line represents the radius $r$ and is located at $0.5$ since $c=2$. The results in the first subplot of Figure 2 show that success probability drops monotonically for all datasets as the starting distance grows. This is natural to expect given that similar behaviour was observed in Experiment 1. On the second subplot we can see that for the most datasets we can reliably find a negative query only at distance much larger than $r$. This, in a way, allows us to compare the “hardness” of datasets, as further away from the origin we move, the less functions collide the origin point $z$ and our current point, the less bits we need to change for the query to become negative. As one can see, all of the real datasets lie between the Random and Sparse random on the second subplot. This can be explained by the fact that the points in real datasets are much sparser than the Random, and the maximum distance from the most isolated point to the nearest point is smaller than the ideal $2cr$.