Title: Neural Embeddings for Nearest Neighbor Search Under Edit Distance

Abstract: The edit distance between two sequences is an important metric with many applications. The drawback, however, is the high computational cost of many basic problems involving this notion, such as the nearest neighbor search. A natural approach to overcoming this issue is to embed the sequences into a vector space such that the geometric distance in the target space approximates the edit distance in the original space. However, the known edit distance embedding algorithms, such as Chakraborty et al. ( 2016), construct embeddings that are data-independent, i.e., do not exploit any structure of embedded sets of strings. In this paper we propose an alternative approach, which learns the embedding function according to the data distribution. Our experiments show that the new algorithm has much better empirical performance than prior data-independent methods.

1. Introduction:

The edit distance is a popular metric for computing the dissimilarity between two strings. Given strings x and y, the edit distance d E (x, y) between them is equal to the minimum number of character insertions, deletions and substitutions needed to transform x into y. The metric and its many variants have been defined and studied since the 1960s (Levenshtein, 1966; Wagner and Fischer, 1974) . It has found many applications in computational biology (to measure the similarity between DNA/RNA sequences), natural language processing, information theory and other fields.

From the algorithmic perspective, the main drawback of edit distance is its computational complexity. The best known algorithm for computing the distance between two strings of length n takes time that is roughly quadratic in n (Masek and Paterson, 1980) ; there is also evidence that this runtime is essentially optimal (Backurs and Indyk, 2015) . Furthermore, many applications require finding the closest string in a large collection of (say) N strings. Thus, even if we could estimate the edit distance in time O(n), computing the distances to all strings in the collection would take O(N n) time, which is infeasible for large data sets.

A natural approach to resolving both issues relies on low-distortion embeddings. The idea is to construct a mapping f that maps strings into a d-dimensional space d , such that the edit distance d E (x, y) is approximated by the distance f (x) -f (y) between the images of the strings, up to some factor D called distortion. If the mapping f can be evaluated efficiently, this immediately implies an efficient way to compute the edit distance. Furthermore, embedding strings into space equipped with a norm • makes it possible to use nearest neighbor search algorithms designed for that norm. For many normed spaces, e.g. Minkowski norms d p , many efficient approximate nearest neighbor search algorithms are available. This dual goal has motivated a long line of research focused on designing efficient low-distortion embeddings of variants of edit distance into normed spaces (Muthukrishnan and Sahinalp, 2000; Cormode et al., 2001; Ostrovsky and Rabani, 2005; Batu et al., 2006; Jowhari, 2012; Andoni and Onak, 2012; Chakraborty et al., 2016) . The method given in the last paper (Chakraborty et al., 2016) was shown to yield good results in practice, in the context of large scale similarity joins, i.e., identifying all pairs of similar sequences (Zhang and Zhang, 2017) .

Figure 1 : Triplet loss for embedding DNA sequence inputs. Given anchor point A, a positive point P that is close to A in terms of edit distance, and a negative point N that is not close to A. We hope our embedding function f satisfies f (A) is closer to f (P ) than f (N ) in p .

A weakness of the aforementioned algorithms is that they are data-independent, i.e., they do not exploit any structure of embedded sets of strings. In contrast, over the last decade, a large body of research on "learning to hash" showed that data-dependent methods often yield (binary) embeddings with a significantly lower distortion than their data-independent counterparts (Wang et al., 2018) . Such methods, however, are typically tailored to obtaining binary representations of vectors that already live in a geometric (typically Hilbert) space. It is thus natural to investigate whether similar benefits of data-dependent methods can be obtained for edit distance embeddings as well.

In this paper we investigate whether the "learning to hash" approach can yield lower distortion embeddings than those obtained using data-independent methods. Since our goal is to obtain distance-preserving mappings of sequences, we use Recurrent Neural Networks as a model implementing those mappings. Specifically, we leverage a two-layer GRU network, depicted in Figure 2 and described in more details in Section 4. The network inputs a sequence of characters (e.g., A, G, T or C for DNA sequences), and outputs a vector of symbols, such that the distance between the vectors approximates the edit distance between the original sequences.

The standard loss function for optimizing the network is the triplet loss (see Figure 1 ), which has two problems in our scenario. The first problem is distance scaling: triplet loss only controls the relative distance ordering among data points after embedding, rather than the absolute embedding distance between any two data points. This prevents us from getting accurate edit distance estimation from the embedding. To alleviate this issue, we designed a warm-start phase (Phase 1) before optimizing triplet loss (Phase 2), which initializes the embedding so that the discrepancy between the original edit distance and the embedding distance is minimized. The second problem is worst case performance of our model. Due to the nature of learning, the network we learned fits the training data better, and may not do well on unseen hard examples. To alleviate this issue, we append a back up phase (Phase 3), which deals with hard cases.

We emphasize that all the three phases are optimizing the same network. We run Adam algorithm for each phase until convergence, and then use its final state as the initial state for the next phase. Although in principle one may use a single phase with combination of different loss functions to train our model, this requires additional hyperparameter adjustment for the combining ratios. Our current three phase training does not need additional hyperparameters, and therefore can easily fit different scenarios.

The Phase 3 design is non-trivial. Our starting observation is that Recurrent Neural Networks that we employ are not "compatible" with the data-independent mappings of Chakraborty et al. (2016) (which we call CGK from now on). This is because CGK can generate different number of copies for every input character, which is a discrete decision that is hard to be learned by neural networks. We show, however, that this "extra power" of the algorithm is not necessary. In particular, we introduce a "truncated" version of the CGK algorithm (referred to as CGK'), that outputs only 1 or 2 symbols per round. We then show that CGK' has the same guarantees as the original CGK algorithm. Based on this observation, we design our Phase 3 to be an optimized version of CGK'. Specifically, since each round there will be either 1 or 2 symbols in CGK', we can directly compare the two cases and use the difference as approximation to the gradients to train our model. Empirically, Phase 3 does not affect the recall on ordinary datasets much, but greatly improves performance on hard instances.

To evaluate the embeddings, we employ them for nearest neighbor search in a collection of sequences, and compare their performance to CGK. As in Zhang and Zhang (2017) we use three data sets: Gen50ks (containing sequences from the human genome project), UniRef (protein sequence dataset from the UniProt project) and Trec (containing textual information from Medline, an online medical information database). After learning the embeddings, we generate a set of queries, and for each query we identify C sequences in the data set (called candidates) that are closest to the query in the embedded space. We then measure "top-K recall", i.e., the fraction of the actual top K nearest neighbors (computed using the exact edit distance) returned as one of the C candidates. Our results demonstrate that, over a wide range of parameters K and C, our learned embedding consistently achieves higher recalls than the algorithm of CGK, often by a factor of 3 or more. Similarly, our method often obtains identical recall to that of CGK while using an order of magnitude fewer candidates. This means that in a typical nearest neighbor search "filtering" pipeline, where the candidates are quickly identified in the embedded space and then the exact edit distance is computed between the candidates and queries to identify the final answers, our method reduces the number of exact edit distance computations by up to one order of magnitude. Moreover, our learned embedding also has much more organized structure than CGK, as shown in Appendix A.4.

2. Related work 2.1 Edit Distance Computing:

Exact and approximate algorithms for edit distance computation have been broadly studied, see Navarro (2001) for an overview. For exact algorithms, Wagner and Fischer (1974) gave O(n 2 )-time algorithm using dynamic programming. This was later improved to O(n 2 / log n) by Masek and Paterson (1980) . Faster approximation algorithms were studied as well, see e.g., Landau et al. (1998) ; Batu et al. (2003) ; Bar-Yossef et al. (2004) ; Batu et al. (2006) ; Andoni et al. (2010) ; Andoni and Onak (2012) . The current state of the art consists of a near-linear algorithm of Andoni et al. (2010) guaranteeing (log n) c -approximation (with a trade-off between the running time and the exponent c), and a constant factor approximation O(n 2-2/7 )-time algorithm of Chakraborty et al. (2018) . To the best of our knowledge, neither algorithm has been implemented.

2.2. Edit Distance Embedding:

As mentioned in the introduction, there has been a long line of research focused on designing embeddings of various variants of the edit distance into geometric space. For the edit distance as defined in the introduction, the best known algorithm is due to Ostrovsky and Rabani (2005) , who designed an embedding into the Hamming space with distortion 2 O( √ log n log log n) . This algorithm was quite complex, and to the best of our knowledge has never been implemented. Recently, Chakraborty et al. (2016) gave a substantially different embedding with distortion O(k) where k is the edit distance between the original strings. The empirical evaluation of the algorithm, given in Zhang and Zhang (2017) , demonstrated that the embedding yields good results in practice, and that the empirical distortion of this embedding is typically much lower than the worst case bound. Zhang and Zhang (2019) also proposed a novel string partition based algorithm for edit similarity join, without generating embeddings. Gomez-Bigorda et al. (2017) presented a novel approach for word embedding in Levenshtein space to improve downstream handwritten word spotting. Their method is similar to our Phase 1, but our model deals with longer sequences instead of words, and also adopts triplet loss training to capture sequence similarity (Phase 2) and CGK based algorithm to learn sequence alignment (Phase 3).

2.3. Similarity Capturing:

Neural models are powerful to learn embeddings that capture latent similarity. For example, word2vec (Mikolov et al., 2013) learns semantic and syntactic similarity of a word from its linguistic context. The idea has been extended to learn sentence or document similarity (Le and Mikolov, 2014) , biological sequence similarity (Asgari and Mofrad, 2015; Ng, 2017) .

GRU GRU GRU GRU GRU GRU GRU GRU x [ 1 0 1 1 • • • ] Linear Layer f (x) [ A B C D • • • ] • • • • • •

The aforementioned methods characterize input representations based on their context. A different approach aims to learn a distance metric, see Kulis (2013) for an overview. Among them, triplet network (Weinberger and Saul, 2009; Hoffer and Ailon, 2015; Schroff et al., 2015) uses triplet loss to learn similarity over triplets. Part of our model gets inspiration from triplet network.

3. Preliminaries:

We use D to denote the alphabet, i.e., the set of symbols used in the strings. For any two strings x, y ∈ D * we use d E (x, y) to denote the edit distance between x and y, i.e., the minimum number of symbol insertions, deletions or substitutions needed to transform x into y. We define the distance metric d(x, y) = ||x -y|| 2 2 . If the strings have different lengths, we pad the shorter string to make their lengths equal. In the binary case, d(x, y) corresponds to the Hamming distance between x and y.

The CGK algorithm is described below. Its input consists of a string x of length n (to be embedded), and a sequence of 6n random bits r, which are interpreted as a sequence of 3n random hash functions h 1 , • • • , h 3n : {0, 1} → {0, 1}. It produces a sequence f (x, r), obtained by replicating each symbol in x at least once (the actual number is a random variable depending on x and r).

Algorithm 1 CGK Embedding Function f:

Input: x ∈ {0, 1} n , and a random string r ∈ {0, 1} 6n Output: f (x, r) ∈ {0, 1} 3n

Interpret r as the description of

h 1 , • • • , h 3n : {0, 1} → {0, 1}. Initialization: i = 1, a = (0, • • • , 0) ∈ {0, 1} 3n for j = 1, 2, • • • , 3n do a j = x i ; i = i + h j (x i ); end for Set f (x, r) = a.

4. Learning-based Embedding Method:

Recurrent Neural Network (RNN) models proved effective for sequence embedding tasks like language modeling (Mikolov et al., 2011) , image captioning (Mao et al., 2015) , protein sequence embedding (Bepler and Berger, 2019) , etc. Long Short Term Memory (LSTM) (Hochreiter and Schmidhuber, 1997) and Gated Recurrent Unit (GRU) (Cho et al., 2014) utilize gates to overcome the long-term dependency problem and often yield improved empirical results. Our learning-based embedding model leverages two-layer GRU depicted in Figure 2 . The input is a sequence of n characters in one-hot encoding, x = {x 1 , x 2 , ..., x n }. We feed the input sequence x into two-layer GRU and a linear layer to get the embedding sequence y = f (x). Here δ i represents the dropout rate in GRU. We use Adam optimizer and 4:1 train:validation split for cross-validation to tune the hyper-parameters. 

f 1 (y) |d E -d| Phase 2 p a n Embed Embed Embed f 2 (p) f 2 (a) f 2 (n) triplet loss Phase 3 f 3 (x) [ A B C • • • ] f 3 (x) [ A B C • • • ] A B C

Add minor? Figure 3 : Our three phase training method: Phase 1 as warm start; Phase 2 learns similarity; Phase 3 for hard case. Embed refers to embedding model depicted in Figure 2 .

EQUATION

EQUATION

y i = W h 2 i + b (3) y = {y 1 , y 2 , ...y n } (4)

4.1. Phase 1: Absolute Loss as Warm Start:

We use Phase 1 to tune the embedding such that the absolute difference between the edit distance and the embedding distance is small. In every iteration, we take a pair of input strings x and y, and pass it through two embedding networks denoted as f 1 , which share weights. The loss is defined as:

L 1 = |d E (x, y) -d(f 1 (x), f 1 (y))| (5)

4.2 Phase 2: Triplet Loss for Similarity Capturing Phase 2 initializes the network with weights computed in Phase 1. It leverages triplet loss (Weinberger and Saul, 2009) to capture the dependencies between string similarities. In each iteration we randomly choose an original string as the anchor and define positive and negative strings with respect to their edit distances from the anchor. More specifically, We randomly sample the positive pairs from top-5 edit distance and sample negative pairs as the top-30 distance in the embedded space, which is a fairly standard approach for triplet loss (Weinberger and Saul, 2009; Sablayrolles et al., 2019) . The anchor, the positive and the negative string form a triplet. The triplets are passed through three networks, denoted by f 2 , which share common weights. For an anchor a, a positive string p and a negative string n, we formulate the triplet loss as:

EQUATION

Further, we set margin to be d E (a, n) -d E (a, p). Intuitively, we hope that the difference between the hamming distance between the positive and the negative pairs is larger than that of the edit distance, namely

d(f 2 (a), f 2 (n)) -d(f 2 (a), f 2 (p)) ≥ d E (a, n) -d E (a, p).

See Figure 1 for illustration.

4.3. Phase 3: Insertion Loss for Hard Cases:

Phase 3 is initialized using weights computed in Phase 2. During each iteration a pair of input strings is passed through two embedding networks denoted as f 3 , which share weights. Let x and y represent the original input strings and f 3 (x) and f 3 (y) denote their embeddings. Denote the CGK' (a variant of CGK, see Algorithm 3 in the appendix) with random initialization as g, and we apply it on f 3 (x), f 3 (y) and get f 3 (x) = g(f 3 (x)), f 3 (y) = g(f 3 (x)). f 3 is our final embedding function, which is essentially a concatenation of an embedding network f and the CGK' algorithm g.

Optimization in Phase 3 has two different losses: the absolute loss and the insertion loss.

The absolute loss (L 3 ) ensures that the distance of the final embedding is close to the edit distance of x and y. The insertion loss is defined as follows. For each character c in f 3 (x), we compare the two cases that with or without duplication of c to optimize the hash functions and the threshold. See Appendix A.1 for more details.

L 3 = |d E (x, y) -d(f 3 (x), f 3 (y))| (7)

As we mentioned before, we use CGK' instead of CGK because it restricts the number of replications of each symbol to be at most 2, therefore we can compare the two cases to get an approximation to the gradient, and then optimize the parameters in CGK'. In what follows we show that this modification does not affect the worst-case guarantees of the method (i.e., CGK' with random initialization). See Appendix A.2 for the proof.

Theorem 1. The mapping f : {0, 1} n × {0, 1} 4n → {0, 1} 2n computed by Algorithm 2 satisfies the following properties:

(1) Given r ∈ {0, 1} 4n and f (x, r) ∈ {0, 1} 2n as the input, we can always decode x.

(2) For every x, y ∈ {0, 1} n , d E (x, y)/2 ≤ d(f (x, r), f (y, r)).

(3) There exists a constant c 0 such that for every positive constant c ≥ c 0 and every x, y ∈ {0, 1} n , d(f (x, r), f (y, r)) ≤ c • d E (x, y) 2 with probability at least 1/2.

5. Experiments:



5.1. Datasets:

We evaluate our neural embedding with three datasets as in Zhang and Zhang (2017) . Specifically, we use Gen50ks: a genetic sequence dataset from the human genome project; UniRef : UniRef90 protein sequence dataset from the UniProt project; and Trec: a reference dataset from Medline (an online medical information database). See Table 1 for their properties. Furthermore, following Zhang and Zhang (2017) we truncate some input strings to avoid dealing with very long outlier strings. For Gen50ks dataset, the string lengths sharply concentrate around 5000, so we set the truncation length to be 5000 and thresholding affects the distances only minimally. For UniRef and Trec dataset, string lengths vary drastically. In order to avoid biasing the original data distribution, we set a rather large threshold(1500 and 2500) so that only a small proportion(1.16% and 0.97%) of the strings exceed the threshold. For Gen50ks, UniRef and Trec dataset, we train our model with 1000, 2000, 2000 strings (including base and query) respectively, which means that we train with less than 2% data points in the whole dataset. We evaluate our model in the context of nearest neighbour search. We randomly select 100 queries and use the remainder of the dataset as the base set. Our goal is to find strings in the base set most similar to the query strings. To this end we use linear scan to identify the C sequences in the data set (called candidates) that are closest to the query in the embedded space. We compare embeddings generated by our neural model, CGK and its close variant CGK', as well as the identity embedding (which is optimal if no insertions or deletions are needed). Since CGK and its variants are randomized, we measure the average of five independent runs. For all three datasets we observe that our neural model offers significant performance gains compared to the other embedding methods. 

5.2.2. LSH-based Approximate Nearest Neighbor Search:

In the previous section we used linear scan to find C nearest neighbors in the embedded space. Although this task can be often accomplished efficiently (e.g., using GPUs), in many scenarios more efficient approximate nearest neighbor search algorithms need to be employed. In this section we investigate one such instantiation employing Locality-Sensitive Hashing (LSH). We note that the same framework was used in Zhang and Zhang (2017) to evaluate CGK.

We use the cross-polytope LSH family under the Euclidean distance with multi-probe LSH (Andoni et al., 2015) . For genetic dataset Gen50ks, we build 50 hash tables and 10-bit hash functions(We vary the number of hash bits and find 10-bit hash functions give the best performance). We test with five randomly selected 100 queries and record the mean and standard deviation as in Table 2 . ±1.8 ±3.8 ±3.7 ±2.9 ±3.0 ±2.9 ±1.7 ±2.1 ±2.6 ±1.3 ±1.5

5.3. String Similarity Join:

Zhang and Zhang (2017) adopts the vanilla bit-sampling LSH for hamming distance, which does not suit our embedding as the neural embedded strings are continuous values instead of discrete characters. So for our string similarity join experiments, we continue to use the cross-polytope LSH family under the Euclidean distance with multi-probe LSH.

The LSH table parameters are the same with the approximate nearest neighbor setting. We run PassJoin (Li et al., 2011) to evaluate our join results.

5.4. Ablation Study:

We further do ablation study to evaluate the function of three phases in our model. We notice a performance drop by removing Phase 1 or Phase 2. We explain this as Phase 1 provides good initialization which makes similarity learning easier while Phase 2 learns string similarity. Removing phase 3 generally does not lower the performance of top-1 recall much. This might be that these datasets do not contain many hard instances(like coexisting small shift and small substitution). Phase 3 does show its effectiveness in our synthetic hard case dataset, see Appendix A.3. We further show the standard deviation by testing with five different query sets, each of which contains 100 randomly selected strings.

6. Conclusion:

In this paper, we introduce the idea of using neural embedding for computing nearest neighbor search under edit distance. Our method has three phases, i.e., the warm-start phase for generating an initial network with the correct scale, the triplet loss phase for learning relative distance among data points, and the back up phase for dealing with hard cases. Our last phase is non-trivial, because we designed a truncated version of CGK algorithm (aka CGK') and proved that it has worst case performance guarantee. Our phase 3 directly optimizes CGK' and easily solves hard cases. Overall, our method gives much better empirical results than the existing methods for nearest neighbor search. (3) Conditioned on t ≤ T , ∆ j -∆ j = 1, w.p. 2/3 0, w.p. 1/3 , Proof. Since j is the first aligned index after j, we know that for any j < j o < j , j o is not aligned, therefore one of f x jo and f y jo is major and the other one is minor. By Algorithm 2, for the string with the minor copy, with probability 1, the next copy on j o + 1 is a major copy; and for the string with the major copy, the next copy on j o + 1 is a major copy or minor copy with equal probability. However, if both copies on j o + 1 is major, we know j o + 1 is aligned, and thus j = j o + 1. In other words, this case only happens for the index j o = j -1, and for other indices, the two strings are not aligned, and have major copies in turn. That already proves (1).

Since the two strings have major copies in turn, and only major copies will increment the value of idx(x, j), we know ∆ j -∆ j = 1, if t is odd 0, otherwise , See Figure 7 for the two possible cases. Moreover, every step from j + 1 to j holds with probability 1/2, so the probability that the sub-index string has length t is 2 -t . By summing over the probabilities of t from 1 to T , we proved (2). Finally, (3) holds by comparing the probabilities of t ≤ T being odd and being even, which is exactly 2 : 1.

Remark 1. Based on Lemma 2(2), if there are l sub-index strings, and for a given T (to be determined later), the probability that all sub-index strings are within length T is bounded by 1 -l • 2 -T using union bound. Below we discuss the case conditioned on this event.

Lemma 2(3) states that if an aligned index j has a sub-index string, and f x j+1 is a major copy, then ∆ j will be incremented by 1 with probability 2/3, and stay unchanged with probability 1/3. Since f x j , f y j are major copies, we know that this case happens with probability 1/4. The symmetric case where f x j+1 is a minor copy and f y j+1 is a major copy also happens with probability 1/4. Combine the two possible cases for aligned index j (with or without sub-index string), and assuming the next aligned major index is j . If f x j and f y j are minor copies, or are the same, we have ∆ j -∆ j = 0 by simple case analysis. Otherwise, we have:

EQUATION

This is because for the two aligned major copies at index j, with probability 1/2, the next index j + 1 is still aligned, and as a result ∆ j does not change. With probability 1/2, there exists a sub-index string for index j, but conditioned on this, the probability that ∆ j does not change is 1/3. So the total probability for being unchanged is 1/2+1/6 = 2/3. The other two cases are symmetric, so each has probability (1 -2/3)/2 = 1/6. This defines a random walk process for ∆ j , and the remaining analysis is similar to the analysis in Chakraborty et al. (2016) .

Proof of Theorem 1. (1) is trivially true, because we can simulate Algorithm 2 using the random string r to decide for each index of f x whether it is a major copy or not.

To see ( 2) is true, we need to do case analysis. We scan f x and f y from left to right, and skip all indices that are the same. For the first different index j, there are three cases:

1. j is aligned major, and j + 1 is aligned minor.

2. j is aligned major, and j + 1 is also aligned major.

3. j is aligned major, and j + 1 is not aligned.

For the first two cases, it suffices to replace the bit at idx(x, j) of x, and we can keep scanning starting from the next aligned major. For the third case, we can do induction on the length t of the sub-index string for j, to show that it suffices to make at most s edits if there are s different bits from j to j + t. Without loss of generality, we assume that the index j + 1 of f x is a major copy while j + 1 of f y is a minor copy.

• If t = 1, which means j + 2 is aligned major. In this case, if bits at index j + 1 of f x and f y are matched, it suffices to edit the bit at index j. Otherwise, it suffices to delete idx(x, j) of x, and replace the bit at idx(x, j + 1) of x to match y.

• If t = 2, which means j + 3 is aligned major, and the index j of f y is a major copy.

In this case, we check whether the bits at j + 2 for f x , f y are the same.

-If yes, it means, idx(y, j + 2) of y and idx(x, j + 2) of x are the same. In this case, it suffices to replace idx(x, j) of x to match y.

-If no, it suffices to replace both idx(x, j), idx(x, j + 1) of x to match y.

• If t > 2, we also check whether the bits at j + t for f x , f y are the same.

-If yes, it means, idx(y, j + t) of y and idx(x, j + t) of x are the same. Then we may reduce the analysis to the t -2 case. By induction, we know that from j to j + t -2, we can make the proper edit to match x and y.

-If no, it means idx(y, j + t) of y and idx(x, j + t) of x are different. We make one edit on idx(x, j + t) to match idx(y, j + t) of y, and then reduce the analysis to the t -2 case.

Notice that in the above two sub-cases, we did not analyze the case at index j +t-1. This is because this index is not aligned, and the minor copy is included in the analysis of index j to j + t -2, while the major copy is included in the analysis of index j + t.

The above analysis shows that it suffices to make at most d(f x , f y ) edits to match x and y until one of f x or f y starts to pad zeros. Since there are at most d(f x , f y ) deletions or insertions on x, and originally x and y have the same length, we know that there are at most d(f x , f y ) padded zeros. Combine the two cases together, we have d E (f x , f y )/2 ≤ d(f x , f y ).

(3) Apply Lemma 3, we know that with probability (1 -e -l 24 ) • (1 -12k 6 l ), there are at most l aligned major indices that satisfies f x j = f y j . Notice that, if for any indices, if f x j = f y j , it does not affect d(f x , f y ). Hence below we consider other cases when f x j = f y j :

• If j is an aligned minor, we know that j -1 is aligned major such that f x j = f y j , and also j + 1 is an aligned major index. Thus the number of such indices is at most l.

• If j is not aligned, we know that j belongs to a sub-index string for an aligned major index j < j. Notice that f x j = f y j , otherwise j won't have sub-index string. We bound the number of such indices below. We have generated a synthetic data set to illustrate the algorithm effectiveness. First we have chosen some prefix strings from the Gen50ks dataset as the query set. Then, for each query, we generate its small shifts (one or two) and small substitution strings (three or four), which are used as the base set. For each query we want to find the closest edit distance string in the base set. The performance of all studied algorithms on this data set are shown in Table 6 . It can be seen that adding Phase 3 improves the performance of our method.

A.4 Visualization:

We visualize the embedding results for both CGK and our model using t-SNE (van der Maaten and Hinton, 2008) . For CGK embedding, the points distribute over the 2D space randomly no matter what hyper-parameters are used. For neural embedding, on the other hand, points are well clustered. Figure 8 shows 2D t-SNE projections with perplexity 8 and learning rate 10.

:



Figures and Tables:

Figure 2: Our embedding model leveraging two-layer GRU.

Figure 4: Gen50ks: top K recalls for our algorithm (Neural) vs. CGK, CGK' and identity, as a function of the number of candidates.

Figure 5: Uniref: top K recalls for our algorithm (Neural) vs. CGK, CGK' and identity, as a function of the number of candidates.

Figure 6: Trec: top K recalls for our algorithm (Neural) vs. CGK, CGK' and identity, as a function of the number of candidates.

Figure 7: Two possible cases of the sub-index string

Statistical analysis of three datasets.

Table content: <table><tr><td>Dataset</td><td colspan="2">Gen50ks UniRef</td><td>Trec</td></tr><tr><td>Alphabet Size</td><td>4</td><td>25</td><td>37</td></tr><tr><td>Dataset Size</td><td>50000</td><td>400000</td><td>233435</td></tr><tr><td>Avg Len.</td><td>5000</td><td>445</td><td>1217</td></tr><tr><td>Max Len.</td><td>5152</td><td>35213</td><td>3947</td></tr><tr><td>Min Len.</td><td>4829</td><td>200</td><td>80</td></tr><tr><td>5.2 Nearest Neighbor Search</td><td/><td/><td/></tr><tr><td colspan="2">5.2.1 Exact Nearest Neighbor Search</td><td/><td/></tr></table>

Top-1 Recall for Gen50ks using LSH

Table content: <table><tr><td>Number of Probes</td><td>50</td><td>100</td><td>200</td><td>400</td><td>800</td><td>1600</td><td>3200</td></tr><tr><td>Neural</td><td colspan="7">50.2±2.7 63.6±1.8 74.0±1.6 84.2±2.8 93.0±3.5 98.6±1.3 99.8±0.4</td></tr><tr><td>CGK</td><td colspan="7">18.0±2.9 23.6±2.8 34.4±2.0 47.6±3.7 68.6±5.2 88.8±3.4 98.2±1.3</td></tr><tr><td>CGK'</td><td colspan="7">11.0±2.6 16.8±2.2 26.0±3.0 43.0±3.8 65.8±4.6 83.6±3.4 98.0±0.6</td></tr><tr><td>Identity</td><td colspan="7">4.6±0.4 9.8±1.6 19.2±1.7 33.2±4.0 56.8±3.7 83.4±2.6 97.4±0.8</td></tr></table>

Top-1 Recall for the Synthetic Dataset. Candidate number is one.

Table content: <table><tr><td>Model</td><td>Top-1 Recall(%)</td></tr><tr><td>Phase 1+2+3</td><td>64.3</td></tr><tr><td>Phase 1+2</td><td>40.9</td></tr><tr><td>CGK</td><td>60.1</td></tr><tr><td>CGK'</td><td>58.0</td></tr><tr><td>Identity</td><td>40.6</td></tr></table>

Peer review (iclr2020):
The paper proposes a scheme to learn representations for sequences using neural networks such that the Hamming distance in the embedded space is close to the edit distance in the original representation of the sequences. This is achieved through a 3-phase algorithm which are clearly motivated and technically sound. The empirical results clearly demonstrate the gains from the representation learning on multiple data sets and scenarios. Given the clarity, technical soundness and the improved empirical performance, I am leaning towards an accept. However, there are a couple of open questions that, if addressed, would help me better understand the contributions: - The main concern is the need for the separated out phases instead of directly minimizing some combinations of these different terms. Is there any inherent reason why the loss function cannot be combined to just train a single neural network in an end-to-end manner instead of this phase-wise manner. The presence of these distinct phases require the reader to figure out when to switch phases, and how dependent the downstream performance is to the phase change decision. - As expected, there is a cost to Phase 3. The text is Sec. 5.4 does not appear to match up with the Table 5. The table indicates that removing phase 3 actually improves performance in all but the top-10 and top-200 case. The text says something different. Please clarify. - Moreover, if there is a cost to Phase 3, can this be properly explained? If there is a cost to it, could there be a way to decide if/when we require the phase 3? Minor: - It would also be important to understand the effect of the network architecture on the downstream performance. Why is a 2 layer GRU necessary and/or sufficient? Some intuition regarding this would be very useful and can indicate the ease of applicability of the proposed scheme across different data sets.