Locality Sensitive Hashing in Fourier Frequency Domain For Soft Set Containment Search
Authors: Indradyumna Roy
Rishi Agarwal
Soumen Chakrabarti
Anirban Dasgupta
Abir De
Venue: NeurIPS 2023 spotlight (2023)
Keywords: Locality sensitive hashing
Fourier transform
Order embeddings
TL;DR: We design an asymmetric LSH in the Fourier frequency domain, for soft set containment search.

Abstract: In many search applications related to passage retrieval, text entailment, and subgraph search, the query and each 'document' is a set of elements, with a document being relevant if it contains the query. These elements are not represented by atomic IDs, but by  embedded representations, thereby extending set containment to *soft* set containment. Recent applications address soft set containment by encoding sets into fixed-size vectors and checking for elementwise *vector* *dominance*. This 0/1 property can be relaxed to an asymmetric *hinge* *distance* for scoring and ranking candidate documents. Here we focus on data-sensitive, trainable indices for fast retrieval of relevant documents. Existing LSH methods are designed for mostly symmetric or few  simple asymmetric distance functions, which are not suitable for hinge distance. Instead, we transform hinge distance into a proposed *dominance* *similarity* measure, to which we then apply a Fourier transform, thereby expressing dominance similarity as an expectation of inner products of functions in the frequency domain. Next, we approximate the expectation with an importance-sampled estimate. The overall consequence is that now we can use a traditional LSH, but in the frequency domain. To ensure that the LSH uses hash bits efficiently, we learn hash functions that are sensitive to both corpus and query distributions, mapped to the frequency domain. Our experiments show that the proposed asymmetric dominance similarity is critical to the targeted applications, and that our LSH, which we call FourierHashNet, provides a better query time vs. retrieval quality trade-off, compared to several baselines. Both the Fourier transform and the trainable hash codes contribute to performance gains.

Locality Sensitive Hashing in Fourier Frequency Domain For Soft Set Containment Search
Indradyumna Roy Rishi Agarwal
Soumen Chakrabarti
Anirban Dasgupta Abir De
TIT Bombay, IIT Gandhinagar [indraroy15, rishiagarval18, soumen, abir) wit...tbbi.... ac anirbandgacse iitgn.ac... in
Abstract
In many search applications related to passage retrieval, text entailment, and sub- graph search, the query and each 'document" is set of elements, with a document being relevant it contains the query. These elements are not represented by atomic IDs, but by embedded representations, thereby extending set containment to soft set containment. Recent applications address soft set containment by encoding sets into fixed-size vectors and checking for elementwise vector dominance. This 0/1 property can be relaxed to an asymmetric hinge distance for scoring and ranking candidate documents. Here we focus on data-sensitive, trainable indices for fast retrieval of relevant documents. Existing LSS methods are designed for mostly symmetric few simple asymmetric distance functions, which are not suitable for hinge distance. Instead, we transform hinge distance into a proposed dominance similarity measure, to which we then apply Fourier transform, thereby expressing dominance similarity as an expectation of inner products of functions the fre- quency domain. Next, approximate the expectation with estimate. The overall consequence is that now we can use a traditional LSH, but the frequency domain. To ensure that the LSH uses hash bits efficiently, we learn hash functions that are sensitive to both corpus and query distributions, mapped to the frequency domain. Our experiments show that the proposed asymmetric domi- nance similarity is critical to the targeted applications, and that our LSH, which we call FOURIERHASING compared to several baselines. Both the Fourier transform and the trainable hash codes contribute performance gains.
importance-sampll
provides a better query time retrieval quality trade-off,
1 Introduction
Consider corpus X of sets (which we call 'documents') over some universe of discrete items, and let 9 be a query which is also subset of this universe. We wish retrieve those x e which satisfy C ar. In most real-world applications, the items in the universe are not just opaque IDs, but are embedded in rich feature space, demanding that the definition of "q x" be generalized suitably.
We formalize the notion of soft containment by writing q {qr } and corresponding sets of item embeddings as { and {Ø+}. q. x are sentences, g. म, may be per- word contextual embeddings output from transformer. If q, x are graphs. Ti, H, may be contextual node embeddings, such as those output by Graph Neural Network (GNN). These set-of-vector representations of and simple pooling [1] or trainable Deep Set [60] or Set Transformer [27] network, converts them fixed-size vectors given by q = SetEne( (g:)) and SetEnc( ({::)) with x; g R Several applications [52 26
{x,} and the
generally of variable sizes. A suitable set encoding gadget, such as
10 31 then use the test "q < x. (elementwise vector dominance) as a surrogate
for testing q C
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

To convert the Boolean test for vector dominance, q S into graded score suitable for ranking (and backpropagation), these applications [52 26
10 31 use a form of (asymmetric) hinge distance
d(q. x) = |||9 - x]+||| = E max(0, q(k] x[k]}.
(I)
d(g. 2²) = 0 when q S. æ holds elementwise, and measures the extent of the constraint violation otherwise. A search system must retrieve the top-r documents r with the smallest d(g. z). given query q. Several example applications that fit into this framework are elaborated in Appendix[B] Even if an application does not fit ① exactly, our technique may help address other asymmetric distances.
Our goal When corpus X is large, it is impractical to evaluate (I) for each document z. Our goal is to retrieve these documents without explicitly evaluating d(q. z)) for all E X, within query time that scales slowly with [X]. To achieve this, we design an asymmetric Locality Sensitive Hashing (ALSH) method tailored for hinge distance ① which then immediately addresses soft. set-containment based search.
Prior work and their limitations When set elements are represented by atomic IDs, Bloom filters (36] and maximum inner product search (MIPS) can be used to find the best r corpus items that are closest to being supersets [46 59 45 2 However, these techniques are designed specifically for items with opaque IDs, rather than contextual embeddings. LSH
17 19 I
has been
established as a standard technique for fast approximate wear-neighbor search (e.g.. FAISS (PP) in the space of contextual embeddings. However, they predominantly work for symmetric notions of relevance, such as Jaccard similarity, dot product, cosine similarity, or Hamming distance, rather than asymmetric distances like relevance (ALSH), but it does not provide a satisfactory solution for (T). as our experiments show.
[ Neyshabur and Srebro (35) propose LSH suited for asymmetric
1.1 Our contributions
Responding to the above motivations, we present FOURTERHASHNETT, a new LSH for hinge distance- based asymmetric distance measures. Specifically, we make the following contributions.
Scalable hinge distance search for soft set containment From several applications, we distil the strongly-motivatee problem of fast top-r retrieval using hinge distance ( to capture soft set containment. To our knowledge, (A)LSH for hinge distance has not been explored till date.
Transformation of hinge distance to enable ALSH design One could leverage its shift-invarian property to apply a Fourier transform on the negative distance, express as the dot product similarity between the corresponding Fourier features and then use Asymmetric LSH (ALSH) [35]. However, as we show in Section 3.1 using the negative distance leads to singularities of the underlying Fourier transform at some points. This in turn does not allow us to design an LSH for such measure. We circumvent this problem by a suitable transformation of hinge distance to a dominance similarity, whose Fourier transform is absolutely convergent.
Design of Fourier features Next, we propose a novel method of lifting the dense vectors to frequency domain, such that the dominance similarity in the original space can be expressed as the cosine similarity between the infinite dimensional Fourier features. However, our dominance similarity function is not positive definite kernel. Hence, unlike Rahimi and Recht [40]. we cannot apply Bochner theorem [44] to obtain finite dimensional Fourier features. Instead, we first scale the Fourier features with a sine function and then obtain finite dimensional Fourier features via importance sampling.
Trainable hashcode design The cosine similarity between the sampled Fourier features is the unbiased estimate of our dominance similarity measure. This allows the use of conventional random hyperplane LSH. However, such an LSH is not guided by the underlying data distribution. To mitigate this limitation, we compute the hashcodes by feeding the Fourier features into a trainable neural hashing network. Prior approaches [54] 15 to trainable hashing encourage bucket balance over the entire corpus, regardless of the query workload. However, this approach not optimal if most corpus items are irrelevant for most queries, as is usually the case. We propose a new loss function that encourages the best best-match hash bucket for a query to include relevant documents and exclude irrelevant documents.
Experiments We show, through extensive experiments, that HOURIERHA TOURIERHASHNER AET is more effective than existing LSH schemes, and that both frequency domain representations and the new trainable hashcode contribute to gains.
2

---

2 Preliminaries
Notation Throughout, we will use [K] to mean {1...., }} {O..... K-1K-11 1} convenient. We use 9 to indicate a query and x to indicate a corpus 'document'. Their (possibly learnt) representations denoted by x; q E RKK, For supervision, x) may come with binary relevance judgment rel(g.)) E {0, 1.. We have defined a potentially learnable distance d(q. x) - a computable surrogate for rel(g, 2) above in Eqn. ( One can define similarity measure sim(q, x) by applying
monotonically decreasing function the distance d(g., æ). We define v-1 and denote the set of corpus items as X = (2.., T.y. }. We indicate the domain of query and corpus items as Q and X' respectively. Given function st), , its Fourier transform is the function S C + C which satisfies st) I ((w)e dw, where w is the frequency variable and S(w) J J s(t)e -wtdt. dt. For a vector q or æ E R the Fourier transform is synthesized using frequency vector w E B of same dimension as a or q. Here, a function s(x) can be expanded as s(x) = -WERX S(w)e x dw.
2.1 Locality sensitive hashing
Indexing corpus items Given a set of corpus items X = {I1, 22,.... n. an LSH will hash each item z;, L times, which is called the number of trials. For each trial & E [L], it prepares B buckets, which are indexed as the pair b) with é E [Z] and b E [B]. In the context of LSH, we draw L independent samples of hash functions (*) from a single hash family H. such that h()), RK + [B]. A corpus item x is inserted in the bucket indexed (c, (x)), for each & E [4].
Symmetric LSH Given query a symmetric LSH computes bucket indices (c)) for all L using the same hash functions (e) used for indexing the corpus. Only those items x that are in bucket (E, A (2) (q)) are considered as candidates; overall, the candidates are in the union of these buckets. In the rest of the paper, we will describe retrieval for one bucket under one trial, with the understanding that L buckets will contribute candidates. An LSH exists if the query and corpus items are hashed in the same bucket with high (low) probability as long as their similarities are high (low). Formally, we define symmetric LSH as follows.
Definition 2.1 (Symmetric I Locality Sensitive Hashing (LSH)). Given a domain of queries Q and corpus X' with 2, Z and similarity measure sim: : Z x Z - R. A distribution over mappings H z + N is said to be a (So, cSo, Pl, P2) P2)-LSH for the similarity function sim(-) if for all q E Q and x E X' we have, with pı > P2 and <
* if sim x) 2 So. then Pr [b(g)= = h(x)] 2 P1
if simm x²) S cSo. then Pra-H [b(g)= = h<=) P2 p2.
The hash family H. is tailored to the specific choice of similarity function sim(q, (equivalently, the distance d(g, 2²). When q, x E IR and sim(q. cos(g, x), the choice of H. corresponds to the
uncountable set of all hyperplanes in K dimensions passing through the origin [9] When simn (g, the Jaccard similarity (q O n////l /q U 2z), H is the space of minwise independent hash functions 77.
Asymmetric LSH (ALSH) In many applications, like the current setup [ we have asymmetric similarity where sim(q. x) A sim(2, q). In such cases, we employ two different hash families G and H. to determine the bucket of query and corpus respectively. Formally, define ALSH follows:
Definition 2.2 (Asymmetric Locality Sensitive Hashing (ALSH) (35)). An asymmetric LSH is (So, cSo, PI, p2) J-LSH for a similarity function sim o) over Q. X' we have two different distributions over mappings G and H such that, with p1 P2 and < 1,
if sim x) > So then Prą~G.A~Hlo(p) = h(x)] 2
if simmg, x) S cS, then ATg-0,A-H|p (g(() = h(z)) S p2.
As an example, given ||ж||| < 1. consider sim(g. x) = q x l2. which can be re-written as cos(a(g)) where axg)) [0; //llq//2]l 3xx) = |v [ x B z)). Thus,
apply random
hyperplane hash on both (<x)) and ((x) to construct g(g) = sign(w (w a())) and h((x) = sign(w (w- 3(x)) with w ~ NO, I). If ||a||| is unbounded, no ALSH exists for sim(q, x) = q a w//lq/laa (35). In (So, CSo, P1,22)-ALSSH retrieval of items with similarity score more than So out of database of items having a similarity score less than cSS, will admit time-complexity O(n log n) and space complexity O +P) where p logP1/ log P2 35
3

---

2
hxx))
-+ Fourier
Øx
W tanh(.)
Fs (
COS- CE loss
Q Øx
d(q. x) ) losss Q X W
Fourier Fo(
rel (q. x))
+
W tanh
g
(a) Fourier transform
(b) Data driven hashcode training
Figure 1: Outline of FOURIERHASHNEH (a) Given the input query embedding q and corpus
embedding æ. we apply the asymmetric transformation in Eq. (10 obtain corresponding Fourier features Fg (Iw)...)) and Fg (Iw (b) We use the generated Fourier features inputs. to train asymmetric Fourier transformation networks Og and Φ using Eq. (12). This generates transformed Fourier representations 2n - d, ( (wwt...))))) and 2n = Φs Fa (1w (......))) )), which are in turn used to train the random hyperplanes W using Eq. (1). The trained de oz and W thus obtained are used to generate final hashcodesg(g) = sign W 0g (F (ww M)), h(x) = sign W oz (F (us
2.2 Problem statement
Given the set of training queries Q and corpus X, with supervised relevance scores rel(g, E {0, and the surrogate score d(g, æ)) defined in Eq. ( we aim design an LSH of the distance d(q.2)) which can efficiently retrieve top-r corpus items for any new query d'
Why are existing methods not suitable? As we discussed Section 2.1 relevance metrics for popular LSHs mostly symmetric, e.g., cosine, dot-p dot-product, and Jaccard similarity. In particular, Jaccard similarity, although commonly used in set-related applications, is not suitable for our problem, where we define rel(g, x) = when q S x and 0 otherwise - it is possible that there exists higher overlap between and æ when Z sr, and lower overlap when C I. E.g., suppose & = {a, b}. and rel(g,
31 = {a, b, c, cl e), and 22 {b). Here, re)(g,21) similarity J(q, 2) is not able to reflect the order of rel(q, x) since ((q, = 2/5 < J J xq, = 1/2.
0. However, the Jaccard
As discovered by Charikar g Lemma 1], the similarity functions in symmetric L.SH are inversely related to metric, which must satisfy symmetry and triangle inequality. Although a query normalized dot product similarity appears asymmetric, can be expressed using cosine similarity. This readily allows us to use a random hyperplane based (asymmetric) LSH. In contrast, it is not immediately apparent how to find such a connection for our asymmetric hinge distance (I).
3 FOURIERHASHNETT A new ALSH for hinge distance search
Overview of our approach We design an ALSH for d(q,2) in three steps. In the first step, construct a suitable dominance similarity function sim(z, x) from d(g, x) in such a way that there exists probability distribution p: RRK -> [0, 1] and bounded Fourier representations (rw)) and Fg (1w) of both query & and corpus items x such that
sim x)
(u(w)) Fz Fx(w)p(w))e Bwwnp() (F((()) Faw))
WERK
In the second step, we approximate the expected value of the F2 T F((()) using finite sample of Fourier features. This allows us to apply random hyperplane LSH similar to asymmetric dot product I.SH. However, these hyperplanes are drawn from an isotropic Gaussian distribution in data-oblivious manner, which results in suboptimal bucket distribution in terms of accuracy-efffciency trade off. To tackle this issue, in the third step, train the random hyperplanes W which takes the Fourier features as input and give (soft) binary hashcodes, which are optimized to effectively trade off between accuracy and efficiency. Next, we provide the details of the above three steps.
3.1 Design of dominance similarity function sim(g, from hinge distance
Limitations of simple choices of dominance similarity function (.. A dominance similarity function sim(q. æ)) is inversely related to the hinge distance d(g, x). Chierichetti and Kumar [II] characterized that, any function of similarity measure is LSHable, if and only if this function is probability generating function. However, this characterization applies only to symmetric LSH and no such guiding principle is available for an AL.SH. In this context, one can experiment with simple designs of sim that are inversely related to d. An immediate choice is sim(g, x) -d(g,

---

However, if we allow and a to be any vector from R then (g. x) is not bounded. Finding ALSH for unbounded similarity measures is extremely difficult not impossible. For example, no ALSH exists even for dot product similarity in two or more dimensions RS Moreover, suppose we express sim(1, 3)) using the Fourier expansion
= Σ
S(wg))e (all))) dwk.
KE[K]
Then, ((w); i.e., the Fourier transform of the function s(1) -10+ used in each dimension, has a singularity at : = O. In particular, we have S(w)) --0 -wd((w) 1/2mu² Here, ('() is the derivative of Dirac delta functional. Thus, S((w) becomes unbounded as 0. These issues eventually prevent us from designing bounded Fourier features Fg (ww) and ((w) for Eq. (
sim(q, x)) with bounded Fourier transform The key reason for which S(w) becomes unbounded as w -> O is that the function s()) = - [+] is unbounded at f - co. However, in practice, the
embeddings are bounded and we have a bounded difference [q[k] - 2 ==[b]] S T. Thus, is reasonable
to ignore the effect of [q[k] x [K]]] when [g[k] =[k|| > T. To this end, we compute sim(g. x) as
T t
i
simm(q,x) x))
Σ s(glk] a+()),, RE[K]
where s()
T
if - -T
(4)
0
otherwise.
In practice we choose 7 as hyperparameter greater than max; g(()] x<<) computation within this domain, one can immediately show that sim(q, KT d(q,ar).
[K]]- Upon restricting the
3.2 Computation of finite dimensional Fourier features for dominance similarity sim(q. x)
Fourier transform of st) We next compute the Fourier representation S(w) of s R
Proposition 3.1. (Proven in Appendix D s(t) specified in Eq.
④ has Fourier transform
T Tsin(wT) sin Sin?(45) (TT)
sin(wT) T (oos(WT)
S(w) = 2nw
+
(5)
TW
2
2mT
Re(S(w))
Im Im(S(ww))
While the Fourier transform of -[1]+ + is unbounded w-+0, here, S(ww) is bounded everywhere.
Computation and sampling of Fourier features Once we compute S(ww using Eq. (5), we use
Eq. (3) compute sim(q, x.) as follows:
sim(q. x)
Σ
(Re(S(())) + Im(((ww)))]e (n (q]4) (q/A)-((k)) dwy
(6)
KE]K]
Now, we define (ww) and S., (ww), the query and corpus specific Fourier representations:
(1wx) uu (Re(((() cos(wr [k]), sin(wn a (k:)).
Uk v [m ((w)))]][[ sin(w, sin(w cos()))))c(((x(()))) (Iwx)) (e((((wx))) cos(wrca]k)] [k]), (w)) [k))],
v [m((s())) cos(wy sin [+]]
(7)
They ensure that the dot-product S, (wwx) (wwx) equals the real part of the integrand in the RHS of Eq. O Since the dominance similarity sim(g, æ) is real quantity, the imaginary part of the RHS integrates to zero. Therefore, using the dot product of the vectors S,((w)) and (Iwx), which are purely real, we can express
Here, us = sign(Re(S(wwn)) Us =
sim(g.x)=
Σ (p((k)) (w
S.
WERK
kE(K)
Here. S.ww) (S.( ),.., S. ((ww)) )}, w [w,,-.,wk) Note that, the expression of S, (Iwx) is
different from Sz (ww) in Eq. 77. This maintains the asymmetry in the final dot product in Eq. (8)
Inspired by the seminal work of Rahimi and Recht [4), several works 50
37 have exploited Fourier
transformations to approximate various functions using inner product between the feature maps. However, the functions that Rahimi and Recht 40 considered are shift invariant positive definite kernels. This allowed them to leverage Bochner's theorem 44) which establishes that the Fourier
5

---

transformation of these kernels are probability distributions. However, in Eq. (). there is no such readily available probability distribution. In response, we attempt to find out a probability distribution p(w) which allows us to draw samples using an importance sampling like procedure, as follows:
sim(g. x)- = Bwwp(w)) [g (ww) Eg ([w)] where, Fu(w)) = S,((w)
(w(
Vp(w) F(w())
Vp(w)
Let fw 1 p(w) be M iid random samples. We compute the Monte Carlo estimate follows:
1
2i =
Σ F(((w)) T Fz(wo)) x cos( ( (wwt..M) Fa (1wo..A)))
(10)
M
JE[M]
Here, Fo (.. = [F. (1wwt), F. (.. Note that, as suggested by Eqs. and
[1F (uul...)lll = (Ls .......) 1|12 =E Σ |Ree (e(sstu()))-u(((uee))) ([tww))) Thus, the value is in-
M
plu()
dependent of the query corpus, which leads to the proportionality relation. We choose the probabil- ity distribution p(w) guided the proportionality constant || F. (1w1 and set p(w) = [ p(w), where p(w) < (ww))) + [ Therefore, set the support of p(w) between [-wmax, Wmax], thus eliminating the higher frequency terms. The effect on the overall score is small. Attenuation of the higher frequency signals can be seen as a multiplication with a low pass filter in the frequency domain, which affects a convolution in the time domain. Its impact on the similarity score is proportional to 1/ 1/Wmax. This still allows us for ALSH despite frequency truncation.
However, the integral of these terms may not be bounded.
Theorem 3.2. (Proven in Appendix D Let q, x E RRK cos-1 be Lipschitz with Lipschitz constant Loos: the hyperparameter T in Eq.
(4) be chosen such that T > l1q - mllbo: the frequency sampling distribution p(w{) [[Re(S(w)) O) + [nm(S(w))]I with the support set W/ E [-wmax- Wmax] and
-_amx [Re(S(w)) + [Im(S(w))]]dd: Then, the mapping [ = sign(w, (w)....))))) and [x] = sign(w w Fg (w)...)) where w, ~ NO, IT), consti-
the proportionality constant [wmma)
tutes a (So, cSo, P1, P2) P2)-P22) -ALSH for some p1 and p2 if we choose the support set
(-wmaxx mmax] and
the number of samples M as follows:
4K
2T
4Leas
2
Wmax
6 T max a q
and M > (1-c))So K KI(wmax). (11)
T(1 So
Based on the outlined assumptions, the above Theorem guarantees that FOURIERHASHNETT is an (So, cSp, P1, P1.P2) (PsS-ASSH for the asymmetric dominance similarity score, subject to appropriate choices of Wmax to bound the effect of frequency truncation and M bound the variance of the Monte Carlo sample estimate.
3.3 Trainable hashing network
Random hyperplane LSH Eq. (0)) provides an asymmetric transformation the input query- corpus pair, which maps it into the cosine similarity space, thus allowing for Random Hyperplanes hashing. We sample H spherically symmetrically distributed normal vectors (w,) i.e., w; N (0, I), each perpendicular to a random hyperplane passing though the origin. For each query q and the corpus x, we can generate H- H-bit hashcodes g(g), h(x)) {=1} from the Fourier features (IO) as follows: [i] sign( w Fg (1)) and [i] sign(w,
(w: Fa ()) Consequently, we can index the given corpus with N items, into hash table with 2 buckets. For each query q, we restrict our search within bucket = g(g). If the corpus items are uniformly distributed across all buckets, then it enables sub-quadratic time retrieval with N/2" comparisons (per trial).
Data driven hashcode generation The above random hyperplane LSH approach suffers from two distinct limitations: (1) the quality of Monte Carlo approximation obtained in Eq. (IO). depends on the suitability of p(w), and (2) the hyperplanes are data oblivious. Data oblivious hyperplanes provide the best efficiency if the corpus embeddings are uniformly spread over the K dimensional sphere, which allows the random hyperplanes to evenly allocate the corpus items across different hashcodes. However, in practice, the spatial distribution of the embeddings not uniform. This results in a skewed distribution of the corpus items across the hash buckets.
To tackle the first problem, we improve the quality of the Fourier features through a trainable nonlinear transformation. Here, we use two networks dy and Φ2 which takes the Fourier features for the query and corpus, i.e., (wwl...M and Fg Fz (ww L.. input and outputs corresponding

---

transformed Fourier representations 2, 0, (ww () and 25 = Φz = ((w We train dg and O₂ by minimizing& BCE loss on {cos(z, zzg 2n) , rel(q. x)} pairs for q E Q and X as follows:
min Egequrex - [rel(q, 2²) log(1 (1 + cos( 2yy: =n,)) + rel(g. x) log(1 cos zx))] (12)
0v:9z
Next, we train the random hyperplanes
Algorithm 1 FOURIERHASHNE
[W1, wa...] using the transformed Fourier fea-
tures {2g} and {zz}- The final hashcodes g(g) and h(x) are obtained as g(g) = sign(W zn),
1: function Train(X..Q. (rel(q, 2) (Eq,.ex))))
2: Draw w....M -(w))
3: Compute (y(wh... ). Pa (u (Fg. 9
h(z) = sign( W= zz), where W are the final trained random hyperplanes. For training pur- poses, we use tanh W as a smooth surrogate of sign( ( .. The loss function (os X W) used to train W consists of three components.
4: Train du, the from rel(g, r), Fe (ww
(Eq.
5: Train W by minimizing the loss 14
Return 6x, Qq. W
1: function Index([Ea (No (no"... I.. Hlex)
Require: Trained networks de,
(1) Collision minimizer For any query g. our goal is to ensure that assigned bucket contains only positive items. Assuming corpus items are uniformly distributed across buckets, we ensure
3:
h(()) + sign [ de (Fa (I 1..
(I (]) Va E X
4:
for a E X do
5: hash x to bucket b = h(x)
6: Return the bucket sets B
1:
function Retrieve(y')
that for any query q, the N/2 most relevant items Xyv measured in terms of d(q, .r) will have higher amount of bit overlap than rest of the items Xax. Here, Xgv and Xax indicate positive and negative silver instances (not gold instances) indi- cating top N/2" items in terms of the (possibly trained) hinge distance d(q, I). We encode this by minimizing the following ranking loss.
2: Require: Trained networks Oo.
3: Computc Fy M...M) based on q'
g(g') <- sign( (F I...MM }))
Rank all x in bucket glq') based on the
distance d(g',z) to obtain the list Listgr-
6: Return Listy'
A = Σ
[1+ tittann(WW W 2 tanh W 2n/ - tanh W z,y) tanh ( (aa+)]]
(13)
PEQ x w Exx
This loss encourages that tanh W zgg (tanh(Zz,) z.) > tanh W xTyT tanh W ).) + 1, i.e., the number of common bits between g and X,v atleast one more than the same between q and x'.
(2) Fence Sitting We set fence sitting loss as A2 =xeex Ill tanh xx,) 1l|1- This prevents the optimizer from arriving at a trivial solution by setting all hashcodes to zero.
(3) Bit Balance We set the bit balance loss as A3 = EvE Evex tanh( W zz [ This enforces that each position should have an equal number of +1 and -1, thus ensuring that each random hyperplane evenly splits the set of points. Finally, we estimate W by minimizing the loss, with X. as hyperparameters such that Σ, A = which is given as follows:
(Q, X (W) = = + X2 + As4s,
(14)
| Algorithm summarizes the overall procedure.
Difference from existing trainable LSH LSH training has been extensively studied 54
15
with Fence Sitting and Bit Balance losses being well known. However, the Collision Minimizer loss differs significantly from existing approaches. Current techniques seek to ensure load balance across hash buckets for all corpus items, including the ones that may be relevant to most queries. This is unnecessary for query workloads which touch upon only a small subset of the corpus to generate the best responses. In contrast, our Collision Minimizer loss ensures that only the top-most bucket for any given query allows relevant items and explicitly denies irrelevant items. Thus. it is informed by the query workload, rather than assuming load balance for all items in the corpus. Such an approach may result in balanced bucket loads, but not necessarily.
Experiments
In this section, we provide a comprehensive evaluation of our method against several baselines and ablations on four datasets. Appendix F describes additional experiments. Our code in http::///ghaab..oossstuuulaaaaar Bachangghhhhhaaa fhashnet
4.1 Experimental setup
Datasets We experiment on datasets sampled from anonymized real-world Web log data, viz, MSWEB and MSNBC. MsWEB (5) is generated using logs from www.microsoff.com, containing
7

---

0.8
0.8
0.8
1 0.6
0.0
T..0
0.6
Fo
Hou
0.4
RRH
0.4
IHH
MAP
0.4
+HH
.RH
DP-RH
DI-RH
DP-RH
DD--H
01.2
WMM
0.2
WMH
0.2
wWHH
0.2
WWM
0.0
0.0
0.0
0.0
0.0
0.1
0.2
0.0
0.1
0.2
2
2
Time (sEc)
Time (sec)
Time (sec)
Time (sec)
(a) MSWFR-1
(b) MsWER-2
(c) MsNBC-1
(d) MsNBC-2
Figure 2: Effect of different similarity measures on LSH, measured in terms of variation of MAP vs.
average query time (in sec) for all methods. Here, the final score used for ranking the relevant items is that similarity score for which the LSH is designed for.
records of the areas of the website visited by the users. MSNBC [8] is collection of logs of user page requests from msnbb.com. In both cases, a record (either @ or z)), is a passage that is regarded as a bag of words. Given collection V of such word bags, (V) = 11234 for MSWEB and [V] 111290 for MsNBC), we sample [Q| = 500 bags from V. designating them as queries, and designate the rest as corpus items X Q. Consistent with typical information retrieval application scenarios [51]. we generate gold relevance labels based on (multi) containment for Ms WFB (MSNBC). (Additional methods for evaluation are explored in Appendix (F) We build the query set Q, such that the number of relevant items No = K E X rel(g, x) = +1}- E [5, 500] for each query q. We create four datasets by changing average relevance counts per query, N ee- They are: (1) MsWEB-I
where N q 35.624. (2) MsW where Nge qe 20.392. (3) MsNBC-1 where N g8 = 24.09 (4) MsNBC-2 where N 9B = 19.78 The set of queries Q is partitioned into 20% training set Qu. 20% validation set Q and 60% test set Quest
Design of query and corpus embeddings q, We begin with a pre-trained sentence transformer model 41 to obtain 768 dimensional dense contextual representations feature, and feature, for the each word in bags q and z. Embeddings of words belonging to bag are fed into a deep set [60] network to obtain a bag representation q E RK with K = 294 (chosen via hyperparameter sweep). To train the parameters inside the deep set network, we use q, x to compute the proposed asymmetric hinge distance d(g, x)) (1, feed it into trainable sigmoid layer a and minimize
Σg BCE (rel(g, 2)) x(d((,,)))
(15)
which uses a BCE loss on the gold relevance labels. Once we obtain q and x, we use Algorithm | to
obtain trained og. 6x and W (Train(-)) +), which are then used for indexing (Index(-)).
Evaluation Given a test query q E Qrest and set of N₂ candidate corpus items, we rank them in increasing order of their hinge distances d(g,,)). Then we evaluate the average precision (AP) for the query and average over queries to report mean average precision (MAP) - see Appendix E.6
4.2 Effect of different similarity measures on LSH
Setup Here, we compare FOURIERHASINGG against the three LSH baselines, viz, Random hyperlane (RH) 19. Dot product LSH (DP-RH) 35 and Weighted MinHash (WMH) [12. that are tailored towards cosine similarity, dot product similarity and Weighted Jaceard Similarity, respectively. For each LSH method, we train the embeddings q. æ and the final hashcodes g(q) and h(z)) using the same networks, as in our method. Furthermore, we set the final relevance measure for ranking to be the similarity score for which the LSH is designed.
Results We vary the mixing hyperparameters x₁ and 22 in our loss 14p and the number of buckets B to explore the tradeoff between accuracy (MAP) and average query time. In Figure we summarize the results. We observe that: (1) FOURIERHASHNET outperforms all the basclines by providing significantly better time-vs.-MAP trade-off across all datasets. In MSWEB datasets, all the baselines except DP-RH show poor performance. All baselines perform poorly for the MSNBC dataset. We remark that cosine similarity, dot product or weighted Jaccard similarity are not suited for vector dominance search. Therefore, the maximum possible MAP obtained by them are severely constrained. (2) In Ms WEB datasets, DP-RH performs moderately, by achieving a MAP value around 0.4-0.42 within 0.03 seconds (average query time). This is because dot product can be computed significantly faster than all the other sistance/similarity measures. particular, is ~7.5x faster than our hinge distance 10.33 faster than cosine, and ~5.1x faster than Jaccard similarity.
8

---

0.5
0.6
ORH Hing
16
11.6
@DP-RE Hingo
0..4
10.4
aFlora
Hinge
0.2
0.2
0.0
0.0
0.0 80
0.0
0.00
0.02
0.00
0.01
0.02
0.0
0.1
0.2
0.0
Time (sec)
Time (sec)
Time (50c)
Time (sec)
(a) MSW
(b) MSWEB-2
(c) MSNBC-1
(d) MsNBC-2
Figure 3: Trade-off between query time and accuracy (MAP) for MSWEB and MSNBC datasets where there is 2 10X speedup compared to exhaustive search. We apply different LSH methods on hinge distance guided emheddings, viz, HH+Hinge, DP-RH+Hinge, WMH+Hinge, FL.OR and FOURIERHASHNFTT and, then use the hinge distance to finally rank the retrieved items.
4.3 Comparison against other efficient indexing techniques
In Section we used the similarity score corresponding to each LSH method for final candidate ranking. The baselines performed poorly, which may result from poor choice of final similarity score or the indexing method. Here, we evaluate FOURIER ASHNET against baseline indexing methods applied hinge distance guided embeddings. We consider LSHH and Inverted File Indexing (IVF) based indexing variants in this section, and discuss graph- based indexing methods in Appendix FF
Comparison with LSH based indexing Shrivastava and Li (47 showed that an LSH not tailored to the final scoring function may still provide an effective filter. Accordingly, we set the final similarity function to be dominance similarity, and compare against four possible LSH baselines.
Given the embeddings q, æ trained [T.) using hinge distance, we feed them into the four baselines. each of which trains a hashing network in a different way. (1) RH+Hinge: We train set of random hyperplanes represented by W and compute the hashcodes as h(q) = sign( (W)) q) and (2) Di-RH++inge: We train random hyperplanes W for these embeddings to compute the hashcodes as g(9) = sign [W[0, q/l /[l) and h(z) sign [WI/
h(x) = sign(Wæ)).
|| x)).
(3) WMH++inge: We use the best performing WMH implementation from DrHash toolkit [58] to obtain the hashcodes. (4) FL.RA [15): We train asymmetric hash networks (net1, netz) using an end-to-end data-driven approach, which minimizes bit balance and decorrelation loss, along with a consistency loss which predicts the final similarity score using cos(net, (q), net)(=)).
Figure 3 compares the performance of FOURIERHASHNET. RH+Hinge, DP-RH DP-RH+Hinge, WMH++inge and FL.ORA in terms of MAP for Ms WEB EB and MsNBC datasets. Here we ana- lyze the section of the trade-off curve which provides > 10X speedup compared to exhaustive search. The complete tradeoff curve is provided
Appendix [F] (1) The newly designed baselines are now seen to perform significantly better than those used in the previous experiments with Figure 2 How- ever FOURIERHASINETT still outperforms all the baselines. (2) RH+Hinge, despite achieving the second highest scores in many cases, is seen to suffer from large variance in performance within any given time budget. This would make it difficult to tune the hyperparameters to achieve the requisite performance v/s retrieval speed trade-off. (3) DP- Hi-RH+Hinge is seen have significantly worse performance than FOURIER FOURIERHASHNET everywhere. This indicates that DP-RH is ill-suited to asymmetric hinge distance based retrieval. (4) We observe that for the same amount of query time invested, FLORA's 's MAP can lag ours by over 10%, particularly when faster average query times required. FLORA'S 's hyperparameter tuning is also more delicate, with there being unsuccessful settings (where MAP grows very slowly with query time) very close to relatively successful ones.
Comparison with IVF indexing We use the widely used FAISS-IVE 21 library, which supports IVF indexing based on L2 distance (IVF-L.2 and Inner Product similarity (IVF-IP). Additionally, we propose an alternative Fourier+IVF+IP, where we apply Fourier transformation on the input embeddings, before using IVF-IP. We provide embeddings q, x. trained using hinge distance to all the methods, and use hinge distance to rank retrieved items.
Figure 4 compares the performances in terms MAP, across all datasets. We observe that: (1) FOURIERHASHNET outperforms both IVF-L2 and IVF-IP across all datasets. FAISS-IVE retrieval suffers because quantizers, that assign vectors to the Voronoi cells, rely on metric like L2 or IP, which are unsuitable for asymmetric hinge distance. (2) Fourier transformation provides significant boost performance across all datasets, as seen while comparing Fourier+IVF+IP against IVF+IP. However, FOURIERHASHNES still outperforms Fourier+IVF+1I. most noticeably in MSWEB-2.

---

0.8
0.6
IVF+12
MAP
0.4
MAP
IVF+IIP
0.2
0.3
0.2
No. of Corpus
Corpus
201X10
Corpus
101
No. Corpus
(a) MSWEB-l
(b) MsWEB-2
(c) MSNBC-1
(d) MSNBC-2
Figure Trade-off between number of corpus items being evaluated and accuracy (MAP) for
Ms WB and MSNBC datasets where there is 2 10X speedup compared to exhaustive search. We apply HoURIERHASHNE and different IVF methods, viz, IVF+1.2, IVF+IP, and Fourier+IVF+IP, on hinge distance guided embeddings; and then use the hinge distance to finally rank the retrieved items.
4.4 Ablation study
HashNet FHash (Untrained)
RiI-Hinge (Untrained)
DP-RH H Hinngo (Untrained) 0.6
Data driven vs data oblivious LSH To perform ablation study on our proposed hashcode training method, we propose an alternative FHASH (UN- TRAINED). This applies our Fourier features fol- lowed by data oblivious random hyperplane LSH, without any data driven hashcode training.
0.0
0..4
1.04
0.0
0.00
0.01
0.02
0.00
0,01
0.02
Time (seec
Time (sec)
In Figure 5 we compare the complete design of method, i.e., FOURIERHASHNG and FHASH (UNTRAINED) against the untrained versions of RH+Hinge and DP- Hi-RHeHinge. We make the following observations: (1) Benefit of Fourier transfor-
(a) MSWEB-1
(b) MsWEB-2
Figure 5: Effect of untrained RH
mation: The MAP vs time trade-off curve of FHASH (UNTRAINED) consistently dominates all the baselines across both datasets. (2) Benefit of hashcode training: Compared to FHASH (UNTRAINED), we observe that FOURIER H ASHNET allows for significantly more choices of trade-off points, where higher MAP is required.
Ablation on collision minimizer Here, we replace the collision minimizer in loss(Q. X W) [4) with decorrelation loss which encourages hashcodes to be dissimilar:
A Exyly Byyy tanh(W za) 'tanh(W (, commonly used loss in prior work [54 15
Figure 6 compares the performance the vari- ations of the losses in terms of MAP, for MSWEB datasets. We observe that: (1) Our loss contain- ing the collision minimizer term performs better than its variant which uses the decorrelation loss.
1
0.5
MAP
0.3
Callision Minianiee
Collssoo Minimiace
In Ms WFB-2, latter provides MAP of 0.4 in 0.014 secs, which our loss achieves in 50% of the time. (2) Our method allows for greater freedom in navigating the performance vs average query time trade-off, as seen in MsWEB-2, it is more spread out across the time axis.
Decorrelation
0.1
Decorrelaton
0.02 Time (sec) -
0.01
Time (sec) +
(a) MSWEB-1
(b) MsWEB-2
Figure 6: Collision minimizer decorrelation.
5 Conclusion
We have presented FOURIERHASHNET. an ALSH for asymmetric hinge distance, strongly motivated by text, image and graph retrieval applications. By converting hinge distance to a proposed dominance similarity and applying suitable Fourier transform to the dominance similarity, we can estimate the distance as an inner product over an importance-sampled spectrum, which further enables the use of a trainable LSH in the frequency domain. Experiments show that FOURTER HASHNET dramatically speeds up queries while preserving or improving retrieval accuracy. Our approach can extended to any shift invariant functions including Chamfer distance, box embeddings, etc. Box embeddings known to model more complex set operations like set overlap and set difference 42 13, making them interesting avenue for future research. One limitation of FOURIERHASHNY simple symmetric LSHs is the increase in computational cost to compute the Fourier transform. One can explore other types of transformations to mitigate this cost.
compared to
10

---

References
[1] Alexandr Andoni, Piotr Indyk, and Ilya Razenshteyn. Approximate nearest neighbor search in high dimensions. In Proceedings of the International Congress of Mathematicians: Rio de Janeiro 20/8, pages 3287-3318, World Scientific, 2018.
[2] Alex Auvolat, Sarath Chandar, Pascal Vincent, Hugo Larochelle, and Yoshua Bengio. Clustering efficient for approximate maximum inner product search. arXiv preprint arXiv:1507.05911 557.00590, 2015.
[3] Haim Avron, Huy Nguyen, and David Woodruff. Subspace embeddings for the polynomial kernel. Advances in neural information processing systems, 27, 2014.
[4] Samuel R Bowman, Gabor Angeli, Christopher Potts, and Christopher Manning. A large annotated corpus for learning natural language inference. arXiv preprint 050.0.5600.0336. 2015.
[5] John S Breese, David Heckerman, and Carl Kadie. Empirical analysis of predictive algorithms for collaborative filtering. arXiv preprint orXiv:1301.3300 2013.
[6] Andrei Z Broder. On the resemblance and containment of documents. Proceedings. Com- pression and Complexity of SEQUENCES 1997 (Cat. No. 97TB100171), pages 21-29, IEEE, 1997.
[7] Andrei Z Broder, Moses Charikar, Alan M Frieze, and Michael Mitzenmacher. Min-wise independent permutations. In Proceedings of the thirtieth annual ACM symposium on Theory of computing, pages 327-336, 1998.
[8] Igor Cadez, David Heckerman, Christopher Meek, Padhraic Smyth, and Steven White. Visual- ization of navigation patterns on web site using model-based clustering. In Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, pages 280- 284, 2000.
[9] Moses Charikar. Similarity estimation techniques from rounding algorithms. Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, pages 380-388. 2002.
[10] Tejas Chheda, Purujit Goyal, Trang Tran, Dhruvesh Patel, Michael Boratko, Shib Sankar Dasgupta, and Andrew McCallum. Box embeddings: An open-source library for representation learning using geometric structures. arXiv preprint arXiv:2109.04990 //www. iesl. cs. umass. edu/box- hedt/box--ebeeddnnee wwweddingg/
2021. URL https
wwwpiiii///aaiaiiiie/ii/iiiiiiee http//ainnn//aa irriiiininnexxxe iidexx.ixx. html
[11] Flavio Chierichetti and Ravi Kumar. Lsh-preserving functions and their applications. Journal of the ACM (JACM), 62(5):1-25, 2015.
[12] Ondrej Chum, James Philbin, Andrew Zisserman, et al. Near duplicate image detection: Min-hash and tf-idf weighting. In Bmve, volume 810, pages 812-815, 2008.
[13] Shib Sankar Dasgupta, Michael Boratko, Siddhartha Mishra, Shriya Atmakuri, Dhruvesh Patel, Xiang Lorraine Li, and Andrew McCallum. Word2box: Capturing set-theoretic semantics of words using box embeddings. arXiv preprint arXiv:2106. 00t::2106..461,,, 2021.
[14] Jacob Devlin, Ming- Wei Chang, Kenton Lee, and Kristina Toutanova. BERT: Pre-training of deep bidirectional transformers for language understanding. In NAACL Conference, 2019. URL https::/ http://wwwwwwww.b.b.//./. org/ httgg//nthooggy.og NN1-oogyyyytiii 1423.
[15] Khoa Doan, Shulong Tan, Weijie Zhao, and Ping Li. Asymmetric hashing for fast ranking via neural network measures. arXiv preprint arXiv:2211.00611 2022.
[16] Sreenivas Gollapudi and Rina Panigrahy. Exploiting asymmetry in hierarchical topic extraction. In Proceedings of the 15th ACM international conference on Information and knowledge management, pages 475-482, 2006.
[17] E. Grant, C. Hegde, and P. Indyk. Nearly optimal linear embeddings into very low dimensions.
In Global Conference Signal and Information Processing (GlobalSIP), 2013.

---

[18] Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. Advances in neural information processing systems, 30, 2017.
[19] Piotr Indyk, Ilya Razenshteyn, and Tal Wagner. Practical data-dependent metric compression with provable guarantees. Advances in Neural Information Processing Systems, 30, 2017.
[20] Sergey loffe. Improved consistent sampling, weighted minhash and 11 sketching. In 2010 IEEE international conference on data mining, pages 246-255. IEEE, 2010.
[21] Jeff Johnson, Matthijs Douze, and Hervé Jégou. Billion-scale similarity search with GPUs. IEEE Transactions on Big Data, 7(3):535-547, 2019.
[22] Justin Johnson, Ranjay Krishna, Michael Stark, Li-Jia Li, David Shamma, Michael Bernstein, and Li Fei-Fei. Image retrieval using scene graphs. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 3668-3678, 2015.
[23] Purushottam Kar and Harish Karnick. Random feature maps for dot product kernels. In Artificial intelligence and statistics, pages 583-591 PMLR, 2012.
[24] Vladimir Karpukhin, Barlas Oguz, Sewon Min, Patrick Lewis, Ledell Wu, Sergey Edunov, Danqi Chen, and Wen-tau Yih. Dense passage retrieval for open-domain question answering. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 6769-6766777 6781, Online, November 2020. Association for Computational Linguis- tics. doi: 10. (11118663v1122 1 1/2/2/2000//m 0ttp::00000mmmmmmi555505555 URL htttp::/wwwet htttp::/www..clwee..orrr.. org/ a 2020. emn p- www..amiin...... -mmmin.-mmmm.mmmmmm
550)
[25] Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. arXiv preprint 1609. 2016.
[26] Alice Lai and Julia Hockenmaier. Learning to predict denotational probabilities for modeling entailment. In Proceedings of the 15th Conference of the European Chapter of the Association for Computational Linguistics: Volume 1, Long Papers, pages 721-730, Valencia, Spain, April 2017. Association for Computational Linguistics. E17-1068
org/
[27] Juho Lee, Yoonho Lee, Jungtaek Kim, Adam Kosiorek, Seungjin Choi, and Yee Whye Teh. Set transformer: A framework for attention-based permutation-invariian neural networks. In International conference on machine learning, pages 3744-3753. PMLR, 2019.
[28] Ping Li. O-bit consistent weighted sampling. In Proceedings of the 21th ACM SIGKDD International conference on knowledge discovery and data mining, pages 665-674, 2015.
[29] Jimmy J. Lin, Rodrigo Nogueira, and Andrew Yates. Pretrained transformers for text ranking: Bert and beyond. WSDM Conference, 2021. URL. https::/dll acm.///llccmmmmm///mmm/ acm. ott.mm///////pff////////////////
1 1145/34 33379633 3441667
[30] Fanghui Liu, Xiaolin Huang, Yudong Chen, and Johan AK Suykens. Random features for kernel approximation: A survey on algorithms, theory, and beyond. arXiv preprint arXiv:2004.11154 2020.
[31] Zhaoyu Lou, Jiaxuan You, Chengtao Wen, Arquimedes Canedo, Jure Leskovec, et al. Neural subgraph matching. arXiv preprini arXiv:2007.03092 2020.
[32] Qin Lv, William Josephson, Zhe Wang, Moses Charikar, and Kai Li. Multi-probe Ish: efficient indexing for high-dimensional similarity search. In Proceedings of the 33rd international conference on Very large data bases, pages 950-961, 2007.
[33] Yu A Malkov and Dmitry A Yashunin. Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs. IEFE transactions on pattern analysis and machine intelligence, 42(4):824 836, 2018.
[34] Bhaskar Mitra and Nick Craswell. An introduction to neural information retrieval. Foundations and Trends in Information Retrieval, 13:1-126, 2018. URI.httpa :tttps://www//
com/ amm www.//eeaaaai--eeeeeeeeee
12

---

[35] Behnam Neyshabur and Nathan Srebro. On symmetric and asymmetric Ishs for inner product search. In International Conference on Machine Learning. pages 1926-1934. PMLR, 2015.
[36] Anna Pagh, Rasmus Pagh, and S Srinivasa Rao. An optimal bloom filter replacement. In Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, pages 923-829, 2005.
[37] Hao Peng, Nikolaos Pappas, Dani Yogatama, Roy Schwartz, Noah A Smith, and Lingpeng Kong. Random feature attention. arXiv preprini
2021.
[38] Ninh Pham and Rasmus Pagh. Fast and scalable polynomial kernels via explicit feature maps. In Proceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining. pages 239-247, 2013.
[39] Maxim Raginsky and Svetlana Lazebnik. docality-sensitive binary codes from thift-invariant kernels. Advances in neural information processing systems, 22, 2009.
[40] Ali Rahimi and Benjamin Recht. Random features for large-scale kernel machines. Advances neural information processing systems, 20, 2007.
[41] Nils Reimers and Iryna Gurevych. Sentence-bert: Sentence embeddings using siamese bert- networks. In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing. Association for Computational Linguisties, 11 2019. URL https: org/
abs/1908. 10084) 10084
[42] Hongyu Ren, Weihua Hu, and Jure Leskovec. Query2box: Reasoning over knowledge graphs in vector space using box embeddings. arXiv preprint arXiv:2002.05969, 2020.
[43] Indradyumna Roy, Abir De, and Soumen Chakrabarti. Adversarial permutation guided node representations for link prediction. In AAAI Conference, 2021. URL httpt://aarri org/ 02sp/2222.88974
[44] Walter Rudin. Fourier analysis on groups. Courier Dover Publications, 2017.
[45] Fumin Shen, Wei Liu, Shaoting Zhang, Yang Yang, and Heng Tao Shen. Learning binary codes for maximum inner product search. In Proceedings of the IEEE International Conference on Computer Vision, pages 4148-4156, 2015.
[46] Anshumali Shrivastava and Ping Li. Asymmetric LSH (ALSH) for sublinear time maximum inner product search (MIPS). NeurIPS, abs//445.5586, 2014. URL https: org/ pdf/1405 11/1//5505.666. pdf
[47] Anshumali Shrivastava and Ping Li. In defense of minhash over simhash. In Artificial Intelli- gence and Statistics, pages
PMLR, 2014.
[48] Konstantinos Skianis, Giannis Nikolentzos, Stratis Limnios, and Michalis Vazirgiannis. Rep the set: Neural networks for learning set representations. In Silvia Chiappa and Roberto Calandra, editors, Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, volume 108 of Proceedings of Machine Leurning Research, pages 1410-1420. PMIR, 26-28 Aug 2020. /ttp::tts//ppoooeediiiii
mlr, wwwppppwsssssseeeeeeeeeee www.sisaanniissssmm html
[49] Zhao Song, David Woodruff, Zheng Yu, and Lichen Zhang. Fast sketching of polynomial kernels of polynomial degree. In International Conference on Machine Learning, pages 9812-9823. PMLR, 2021.
[50] Matthew Tancik, Pratul Srinivasan, Ben Mildenhall, Sara Fridovich-Keil Keil, Nithin Raghavan, Utkarsh Singhal, Ravi Ramamoorthi, Jonathan Barron, and Ren Ng. Fourier features let networks learn high frequency functions in low dimensional domains. Advances in Neural Information Processing Systems, 33:7537-7547, 2020.
[51] Manolis Terrovitis, Panagiotis Bouros, Panos Vassiliadis, Timos Sellis, and Nikos Mamoulis. Efficient answering of set containment queries for skewed item distributions. In Proceedings of the 14th International Conference Extending Database Technology, pages 225-236 2011.
13

---

[52]
Ivan Vendrov, Ryan Kiros, Sanja Fidler, and Raquel Urtasun. Order-embeddingg of images and language. arXiv preprint arXiv:1511.06366, 2015. URL http:://aaaxi..orr////////////// http:///ppppppp///p///////// /151
06361
[53] Kilian Weinberger, Anirban Dasgupta, John Langford, Alex Smola, and Josh Attenberg. Feature hashing for large scale multitask learning. In ICML, pages 1113-1120, 2009. URL https
//arxiv. www.oogg//po..o /ttp 09002.0902... 2206. pdff
[54] Yair Weiss, Antonio Torralba, and Rob Fergus. Spectral hashing, Advances in neural information processing systems, 21, 2008.
[55] Wei Wu, Bin Li, Ling Chen, and Chengqi Zhang. Canonical consistent weighted sampling for real-value weighted min-hash. 2016 IEEE 16th International Conference on Data Mining (ICDM), pages 1287-1292. IEEE, 2016.
[56] Wei Wu, Bin Li, Ling Chen, and Chengqi Zhang. Consistent weighted sampling made more practical, In Proceedings of the 26th International Conference on World Wide Web, pages 1035-1043, 2017.
[57] Wei Wu, Bin Li, Ling Chen, Chengqi Zhang, and S Yu Philip. Improved consistent weighted sampling revisited. IEEE Transactions on Knowledge and Data Engineering, 31(12))2332-2344, 2018.
[58] Wei Wu, Bin Li, Ling Chen, Junbin Gao, and Chengqi Zhang. A review for weighted minhash algorithms. IEEE Transactions on Knowledge and Data Engineering, 34(6):2553-2573, 2022.
[59] Xiao Yan, Jinfeng Li, Xinyan Dai, Hongzhi Chen, and James Cheng. Norm-ranging Ish for maximum inner product search. 31, 2018.
[60] Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabas Poczos, Russ R Salakhutdinov, and Alexander J Smola. Deep sets. Advances in neural information processing systems, 30, 2017.
14

---

Locality Sensitive Hashing in Fourier Frequency Domain For Soft Set Containment Search
(Appendix)
A Limitations of our work
(1) In Eq. (9). the probability distribution p(w) is determined based on the proportionality constant
I|| and we set p(w) = [ [K] p(w), where p(w) [Re(S(w))] + [Im(S(w))] We note that this choice of distribution is not informed by the data distribution. Doing so may further improve FOURIERHASHNET.
[IF (ww "..
(2) our approach, the dominance similarity function represented as an expectation of inner products of functions in the frequency domain, as described in Eq. (10). The accuracy of this representation relies on the quality of Monte Carlo approximations, which is influenced by the number of w samples used. Our experimental findings, presented in Figure[33 suggest that it may be necessary to generate up to 100 samples per dimension to reduce the approximation error to acceptable levels. A better choice of p(w) may reduce the number of samples needed.
(3) During our experimental investigations, we discovered that the computation of our proposed dominance similarity score is approximately 7.5X slower, compared to the dot product similarity our datasets. This aligns with earlier observations where matrix subtraction operations have been known be significantly slower than dot product. This disparity in computation speed represents another potential limitation of our approach, which could be addressed by exploring alternative designs for the dominance similarity function.
B Example applications of soft set containment
Natural Language Inference (NLI) In (NLI) Q anddd are sentences, regarded as sequences of
converts each sentence to an embedding vector. We infer = q if S x (26). Consider now a claim verification application that, given a claim as a query and a Web-scale corpus, needs to quickly retrieve passages that best support the given claim. This application exactly motivates FOURIERHASHNET..
words as items. A transformer network 14 41
Market basket Given basket of supermarket items, we may query purchase logs for frequent supersets to make recommendations. The corpus contains itemsets purchased in the past, each is a 'document" x. The query q the current basket. Hard set containment tests for q C x. However, we would like to 'soften' items in (say, from one toothpaste brand to another. Each item has a short textual description, which is passed into BERT [4] and the [CLS] embedding read as the item representation. An itemset is then embedded using a (suitably fine-tuned) set encoder (such as Deep Set), giving us q and æ. To the extent q S. x. we regard the query basket "soft-contained" in the document basket.
Knowledge graph (KG) completion Vendrov et al. [2 embedded types and entities in a KG to vectors such that if two types are related via t is-subtype-of l2 then i < lz was encouraged, and if entity e is-instance-of I, then E was encouraged suitable loss functions. Later, these order embeddings were generalized to box embeddings where is-subtype-of and is-instance-of were modeled as boxes in high dimensions contained in other boxes 110. These models naturally motivate fast retrieval using dominance similarity.
Subgraph isomorphism search Here we expect a corpus graph x will be relevant if query graph subgraph of xr i.e., that x has subgraph that is isomorphic to q. In reality, we want to score highly corpus graphs that have subgraphs almost isomorphic to the query graph. A graph neural network (GNN) [25 [8] can build suitable contextual embeddings q and æ for the entire graphs, which can be used to test for approximate subgraph isomorphism, i.e., < æ. There are several applications of subgraph isomorphism search. In material and drug design, there are large molecule databases. A researcher wishes to predict properties of a new query molecule by retrieving similar molecules in the database. Each molecule is modeled as a modest-sized graph with nodes (atom, DNA bases) and edges (valence, etc.). In image search [22], the query y may be graph fragment, e.g., (person, feeding, pet), and the goal is to find corpus graphs æ where q is approximately subgraph [31], e.g., x can contain (man, feeding, dog).
15

---

C Further discussion on related work
In this section, we discuss existing work related to each of the three major components of our work- set embeddings, of frequency domain for computing representations, and locality sensitive hashing.
Neural set embeddings Motivated by various machine learning questions that are better formalized by using set of items as primitive, there has also been recent line work on set embeddings. Zaheer al. [60] consider models that act on sets and characterize the structure of such permutation-ineee tnnvaiationnnvarriant models, but do not consider asymmetric query based measures e.g., containment. Skianis et al. [48] casts the similarity measurement between sets as a combinatorial flow problem, which in turn is approximated by linear program. Lee et al. [27] propose the Set Transformer, model that uses self-attention to model interactions among the input set elements. Our model is different from the existing line of work in focusing asymmetric metrics that can measure containment, as well as in using the frequency domain representation the metric to build a scalable LSH.
Application of frequency domain transformation in machine learning One of the most cele- brated uses of the frequency domain representation was by 40). who proposed using random Fourier features for shift-invariant kernels. Since dot-product kernels are shift-invariant, Bochner's theorem, a key tool in creating random Fourier features, does not apply. Hence, alternative ran- dom feature- based approximations have been proposed, primarily focusing on polynomial ker- 30]. All of the above work is on symmetric kernels. For our asymmetric dominance similarity function, we design a sampling distribution by taking into account the individ- ual frequency-lever coefficients of the Fourier representation. Raginsky and Lazebnik (39 provided a random Fourier based approach for LSH. However they only focused on similarity of the Mercer Kernel class, which is symmetric in nature.
nels [23
38
3
49
Locality sensitive hashing The third main pillar of our work is locality sensitive hashing (LSH) which enables efficient retrieval. Answering queries using sketches hashes in order to measure the similarity or containment of documents has a long history. pioneered by Broder [ In more recent years, semantic search vector search, sometimes called "dense passage retrieval" (24] employing
scalable near-neighbor search engines, has emerged as a credible, often more powerful, alternative standard information retrieval schemes, the vector embeddings can capture more nuanced contextualization and semantics. While there are a number of variants of LSH, including multi-probe (32), our presentation and experimentation focus on dingle-probe setting in which the hashing hyperplanes are learned from the data. In particular, we build upon the asymmetric hash constructions Shrivastava and Li 46 and Neyshabur and Srebro 35
34 29
16

---

D Proofs of the technical results
D.1 Proof of Proposition 3.1
Proof. Consider two functions B (for arbitrary positive constants a, and RELU, defined as
follows:
a if -b
BO
(16)
0 clse
(t = (o clse
(17)
Observe that 8 can be written in terms of these new functions as follows: s(1) = BBOX,, (1)
(E)UT((). By linearity of Fourier transform,
S(w) = FBoxr, (uw) -FRELL (Iw)
(18)
where, Fy((w) denotes Fourier transform of ftt for any function f. Now let us compute FRELU, (ww).
/
FRELUZ (ww)
te de-widt
(19)
2T
1
e e-
Te-
(20)
2nw
2Tw2
2Tw
1
cos(wl)
=isn((w))
T( cos(wW)) + sin(wT))
(21)
2mw
2Tw2
2Tw
sin
(wT/22
T Tin((W)) sin(wT)
T Tcos(wT)
+
(22)
2
2nw
2nw
2mw
Since Boxr,T is rectangular pulse, its Fourier transform is
FBox,, (w) = 2T 2 sin((T)
(23)
2TT
Substituting the above Eqs.
22 and 23 into Eq. (8)) we get ((w) as follows.
S(ww 27 sin(wT)
2 sin
(2)
T Tsin(w)) sin(wT)
T (oos(w))
+
(24)
2Tw
2
2Tw
2Tw2
2Tw
Boxx,7 (12)
G(()
Re(S(ww)
sin((W)
sin 2 WT
sin(wT)
T cos(wTT)
T 2TT
22
+1
(25)
2
2mw
2mw
Im(S(w))
D.2 Proof of Theorem 3.2
Theorem
3.2
Let q. E R cos- 1 be Lipschitz with Lipschitz constant Leos; the hyperparameter be chosen such that T llq ælloci the frequency sampling distribution p(w{) oc
T in Eq.
([ee(S(W)))
(S(2)))) with the support set w/ E [- Wmax]. Furthermore, we define T
Asim
T- m-Xx, y x alooo and [(wmax) = fumaa [[Re (Re()((w) + [Im(S(w))]]da Then, the mapping [ sign(w, w; Fg (w (w) and h())[t] sign(w) (w. Fo Fw where w, (O,
constitutes a (So. cS. P1, P2) -ALSH for some P1 and if
4A sim
4Leos
2
Wmax
x1
So
M>
(1 S)
KT KT(wmax).
(26)
Proof
Define Q2 [-wimxx- Wmnax]
K For Ω. have the following relationships:
Re((S(w)) + [I
(wo... -I|Fa (W....M }113
Σ
MKT; (27)
p(w()
kE|K]

---

We also define that sim (g, = Swen (1w) F (w )p()) This gives us the following result:
1
Fg (wt..MM T F (ot....)))
Pr(g(g) h(x))[w]] = coos-
(28)
9.
π
F1 Fg (w (w..M.))
1
(Jo Folww) Fr
cos
Fg (w]lll (will
1 cos
F (ww!l..
(L Wen
Fg Fq(ww) Fg ( (wW))())
+ cos -1
(29)
M MKI (KIax))
Fg (w
F Fo(w))
(wimas)
sim 9.
sim (g. x)
sSiDaimse (q.2))
cos
cos
cos
KI (Wmaxx)
π
KT (Wmaxx)
KI (u
Term-1
Fg (wl....)
F
(J
Fy(ww) Fg (((ww)
COS
+ π
cos-1
(30)
π
MK MKI(waxx)
(I(amax)
Temm-2
Next we bound Term-1 and Term-2. First we bound Term-1 follows:
sim((q,2)
) cos
[siMwimax (g,
Loos
simn (q, x)) - sim (q,
cos
KT (KT(waxx)
(TWwman (wiax))
K
x KT
(31)
2T
K Leos
6 maN a x 911
Drm
nt KI (W Wmax
(32)
The last inequality is due to Lemma D.I
Next we bound Term-2 in Eq. 30
Fg (w...... Fa(w!..M) + cos (
Fg (ww)) F. Fa(ww)
CO8 11
M HHKK(uman
K K(Wmax)
(33)
Lreos
Fy(W (w...... D/M
Fg(ww) (rw p(w))
(34)
n KI
WED
Leoss
Σ Fw(w") Fa(w)) 1 Fu(ww) Fs (ww ) www) JE(M]
(35)
n (KTaax
SweSt
Taking expectation with respect to w, we have:
Fg (w.....)) Fu (w!!...
-( Fo(ww) T F Fo(w) K KI(wmax)
cos
+ cos
(36)
MKI (w)ax)
Lecos
E
Σ Fo(w*) FF ((o) Fa (ww))p())d
(37)
K (Wmax)
JE[M]
1/2
Lons
Variance
F3(W2)/M)) Σ Fg(w)) ([WW))FF(W"//)))
(E| S /E|ZZ
(38)
π K (W
JE(M]
Leos
Variance Fy((w)) Fo(ww)
1/2
(39)
T I VM VM
Loos
Variance Fy(wn) ( Fa(wm))
1/2
Loos
VK
(40)
T (Wmaxx) VM
TVKM
18

---

The last inequality follows from bound on the variance due the following: Fu(wx) (u(wx) (y(wx) T (((:://pxu)))
(41)
(tc(((w) cos wk (g 28 [R:) [m]] sin we (g[k) x({))
(42)
[e + [m][S(]]]]
Re (w) I1I + Im (w))) =
(43)
Re S [w))] 7m [(w)]]
Putting Eqs. 32
40
into Eq. (30). we will have the upper bound for sim(g, S cSpi
(sim(g,a)
Leos
A
[( (w"]
9.
S P2
cos
KI [II
TVKM
TT2 2I (Wmax Wmax
(44)
Similarly, we have the lower bound for sim(q, x)) Sb:
sim((g,x)
Loos
A sim
E(Pr(g(q) = hx=))=01] 2
cos
KT (wmaxx)
K
RVKM nt KI (mmax) M
(45)
Now, note that:
1
cSo
)
So
]
d
cos -1
cos
(c 1)80
cos (s)
KI KI (wmaxx)
KI (wmax)
TK I (Wmaxx)
ds
sE(cSo.50)
1
(c- --)
T K KKNumax
v1 - 52
(1 (1-c) c)So
T [
V1
7T. T.. [WWmxx)
24sim
2
πT 22KI )
πT TV K (W M
(46)
The last inequality (i) is due the conditions that:
4 sim
4Lcos 2
Wmax
M
K (WWax))
(47)
x
So
(1 So
This leads us to the following relationship:
1
cSo
Teas
Agin
1 cos
+
KI (xmax)
RVKM
TT ?2KI KI ?
So
Loos
Asim
< 1
cos
(48)
KI ((Wax)
TVKM
17 2 [K[[aa )
Thus, have:
sim(g,x)
Lens
Asim
P2
1
cos
π
Kl (w/mxx)
TVKM
22K (wmmx Whaxx
1
cSo
Lons
Asim
<
cas
-1
KT(wmax
TVKM
2 K KTKT (Wmax Wmmax
So
Lrgos
Asim
<
cos
KI (I(mmxx)
TVKM
2t KI [I[ Winax
1
sim((g
Loos
Asim
<
COS
-1
KT (Wmax)
siim(g.))>So/
TVKM
T22K KT (umaax 2 Jumax
Pi
(49)
19

---

D.3 Effect of truncating frequencies
Lemma D.1. Let sim (g, x) Bwwp(w)) (ew) F ((w))
with p(w) being defined follows:
p(w) [IEE[K] (Re(S()))) + [l [Imw)( if, w E [-Wmax Wmax otherwise
(50)
Then, if'' maxx. x glooo. then we have:
T
6K + 2K max
T max g
x
wim (q. a) - sim(g, x)]
(51)
mWmax
Proof Let S(w) be the Fourier transform of s(t). J- is the inverse Fourier transform, * is the convolution operator. Further, define the LOWPASS(w [mmax) is defined as
LowPAss (max)) 1 [ S Wmax and otherwise.
(52)
Let us define the filtered or frequency truncated signal of s()) as defined in Eq. (4) as:
Susua (1) F-1 (((w) LoWPsS(u (imax)]
=F =F--[S(ww) + F [LOWPASS(W [maxx]]
(53)
In this context, sims (), can be expressed as follows:
sim (q. x)
wen F9(wW) F (IW())(())d
(54)
[
wen " Se(w))dw
(55)
Σ
[Re(S(wwx)) cos(wn =[k])) - Im(S(wwx)) sin(ws ze [[k
kE[K]
(56)
[Re(S(w:)) cos(ws x x=k))) Im 1m (S(ww))) sin (q(k) - x [((l))]dw>x
KE|K]
Wanax
Im(S(ww)) cos(w> cos(w))))))))))))))))))))))))))) x=())) + Re Re(S(ww)) sin(wx (q]h) x: =<k()) duy
kE[K]
Wimax
function wa
(57)
Σ
Re((S(wk)) + AI((S(wa)) exp (xp(ucu(qlt) - ddw
(58)
KE[K]
S(wn) exp( (q[k) =llk))ddwx
(59)
kE[K]
Whax
Σ
S(ww)) LOWPASS Wimxx) (amp(((((ll)) x dklk
(60)
k
Σ
F ([((w)) LOWPASS(UN, [wnax)]
(61)
KE[K]
(60)
Sumar (q[k] -x(k))]]) x(k])
(62)
RE[K]
Equality (i) is due to the fact that the newly added imaginary integrand is an odd function (since,
Im(S(ww) = -mm(S(((w) and Re(S(w)) Re(S(-ww)) and thus, the integral from -whaax and Wmax is zero. Equality (ii) is due to Eq. 133. Next we focus Swmm. (t). Since F F= =
20

---

st)) and F [LOWPASS(W) [maxx) sin
we have:
sin Wmax dr
man (1)
8(1 T)
(63)
T
sin dr
(64)
Wmax nI
sin
sin T
s(t)
dt
+
s(t)
dr
(65)
TT
Wmax
nT
As(t
wmax
000
sin T
sin 7 T
s(1)
dr
8
s(1)
dr
(66)
TTT
-00
Winax
Do(t-
= sin T
100
=(t)) +
_00
8
s(()
dr
(67)
Wmax
TT
We only consider the case when t E (-T,T), We decompose the error term Burmax (t) - s(() as: Suluan (1) 1)-8(1 s(1)
sin T
mumart
sin dr
As
dr
As 1-
Wmax
(t-2)
Wmax
n
(68)
(max((++
sinT
sin T
As t
dr
As t
dr
Wmaxe!
Wmax
n8
Wmax
. (69)
Bounding the error [wwmae (1) - [(t)] when <5<60 We separately bound the four integrals
as follows:
Bound on the first integral | (t-2) As t
dr:
Thus,
and
Wmixx
x7
Wmmx
r-) )
As
s(t) T.
We compute the bound on the first term as:
wimxx
Wmaxe
(1
sin T
Wmax (t- 7)
sin T n
As t-
dr = =-T
dr
(70)
Wmax
sin dr
-T
(71)
Wmmn (1- TT
Thus, from Proposition
D.2, have:
(t T) As
sin T
2T wwx
2
dr <
(since 1 < <0)
(72)
Wmax
(T t)
Tw
Bound on the second integral
(uamss (t- T) As (t
sin dr: Since (wmax (t - TT), wmaxt). ot
Wimx
we have < - T/wmax < Thus, 8
Wimax
Wamax
We compute the bound the second term as: Wmaxt
sin dr n
As
(73)
Smaa (T-T)
Wmax
wmant
sin T
T - t
T
dr
(74)
Junaa (1-T)
Wmax
nT
Wmaxt
sin T dt +
T
sin
dr
(75)
Wana (2- T) Winxx π
Wmart
sin T
coS Leswmax (t T) cos Wmaxt
dr +
(76)
(t n
TWmax
21

---

Thus, from Proposition
D.2,
we have:
As
l
7
s
dt n
2t
2
4
(77)
Wmnx
Twmax
mwmma
TWmaa
S ( As (t- sin dr: When T (wmaxt, Wmax T)}
Bound on the third integral we have -T S (T/T/On //maxx
O. Moreover, -T S O. Thus, s(1) = 8(1 - T 7//mmxx) = T
resulting in As (1- Wmax
0 and the third integral zero.
sin dr
As
(78)
Wmaxt
Wmax
Bound the fourth integral J (1+T) As
sin dr: When E (Wmax T); oo),
Winax
x5
have -00 T/ T/Wmax - Then,
O.
Wwoxx
We compute the bound the first term as:
fon Wmaee (T++)
sin
sin dr
As Wmax
dr -T
(79)
n
(mxx(T+t)) ITT
(80)
Thus, from Proposition D.2 we have:
As (1
sin dr
2T
5
(81)
mmax (max(T+()
Wmax
TT
TWmax (T + 1)
Bounding the error
S Wmaxx
(t) - s({) when 0 <
Winax (t-T)
T sin
Wimase
As (1- T
sin T
Buiaaa (1) - s(1)
As 1
dr
dr
Wynax
TT
Wmox(t-21)
Winax
nT
(82)
sin T
As (
dr
(83)
wmaxe
Wmax
TT
Now, since 0 S t < T, we have s(t) = - t. throughout the next part of the proof.
Bound on the first integral l (w)a As
dr: Since T E (-00, wmmx (t: T)), we
Wimaa
have T S St-11 SL-T/WWmas Wmax < 00. Thus, $ (t Waan = O and As (1.
Wanux = 8 Wanxx
T
- s()) =
(T t).
Wmmrr (l-T)
As T sin dr
Wmax πT
Wmaxe Wmmaelt-7 (1-T)
sin
(1)
2
2
(T t)
dr
(T
t)
(84)
Wmax (T' t)π
Wmaxx
Inequality (i) is due to Proposition D.2
Bound on the second integral pummrt T)
As
(
T
dr: Since 7 (wmmx (1 - T), Wmax!),
Wimax
we have < - T/ 7/wmax < Thus, s
sin T
Wanast
sin
As t--
dr
[T- (t T r//wmax) - (T t)]
Wamastt T)
Wmax
nT
Wmax
Smaxt
sinT dl
(85)
At-x(t-77
mwmmax
Twlaa
22

---

Bound on the third integral
Sumast [ummr(((t)) As
(l+2)
sin I dr: When (Wmaxt, Wmax T)}.
Wmax
mr T.
have -T S 1.- T T/Wmax O. Thus, s(1
T
Wmax
Wulna (t-T)
As 8
7
sin
dr
Wasax (1+T)
T (T' t)]
sin dr
(86)
Wanaxt
Winxx
n
Wanax
n
Wmaa (f+7)
sin dr
(87)
Wmaxt
πT
B (t+T)
sin dt
2
(88)
Winant
T Wmaxl
TWmax
Inequality (i) is due to Proposition D.2
Bound on the fourth integral S (1+1) As (t-
sin dr: x
When T E (Wmax (t + T), 00), we
Wmax
have 000 < t T T/Wmax < - Then,
sin T
sin 7
As t-
dr
(T t)
dr
Wmax
Wmaxe (1+T)
(T 1) x
(89)
Wmax
(t +T
2 Twlmax
(90)
Inequality (i) is due to Proposition D.2 Hence,
T
6 - 2 max
1, T
Summax (1) (0)=
(91)
TWmax
The above result, together with sim EKE[K] s(q[k] xz(k)) and wim (q. = EME(K] Suame [g æ=(k) prove the Lemma. Q.E.D.
Proposition D.2. a and have the same sign and a < 3, then we have:
2.
if 3
0
sin t dt 5
za
(92)
nt
if B
x
d cost
sint
cos
Proof
Note that
Then have:
dt
t
f2
3 sin l
|
d
costt"
8
cos dt
dt
dt
(93)
t
t
t2
cos Cos B
cos
dt.
(94)
8
t2
This gives us the following inequality:
sint
cos
COS 3
3
cost
dt
dt
(95)
B
12
1
Cos
+
+
dl
(96)
0
13
12
1
1
1
a
[3
3
2
i >
a >
0
0/2
(97)
>0>0>>0
B
23

---

E Additional details about the experimental setup
E.1 Dataset Generation
We obtain the MEW and MSNBC datassts from the UCI Machine Learning repository. Both of the datasets contain anonymized logs of real world user web activity. Each data item in MSWEB is set of text snippets denoting areas of the website www.microsoff..com visited by an user within specified time frame. Similarly, MEWEB consists of multi-sets denoting user page requests under www.msnbe.com.. Overall, we regard each data items, each item being a bag of words. For each data set, we sample a subset of items and designate them as queries, and the remaining items are designated corpus items. The (binary) query-corpus relevance for MSWER- 1 and MSWFR: are governed by set containment, while for MsNBC-1 I and MsNBC-2 we use multi-set (bag) containment. Le.. x relevant for q iff g S x. To test the ability of FOURIERHASHNN only on MAP based on gold labels but also scores of the top-10 candidates (Figure The dataset characteristics are summarized in Table 7 We create datasets which differ greatly in terms of corpus size (10734 for MSWEB-L and MsWER EB, 110790 for MsNBC- 1 and MsNBC-2), as well as span range of average query selectivity between 1.7x10- and 3.3x 10 We set aside 100 query graphs each for training and validation, and use the remaining 300 for testing.
various news categories
a collection of
to retrieve semantically similar items close to the gold items, we report not
Dutaset
1Q
|X]
E,egwex rol(yss)
minueoxe x rel(g.r))
mAX,cd- y mllgia))
Lecowe x rel(q.e]]
Q
Q
MSWEB-1 1
500
10734
35,624
9
327
0.0033
MsWER-2
500
10734
20,392
9
0.0019
MSNBC-1
500
110790
24.09
9
44
0.00022
MsNBC-2
500
110790
19.78
0,00017
Table 7: Dataset statistics. From left to right: Datasets name, number of queries, number of corpus, the average number of relevant corpus items per query, the minimum num of relevnt corpus items per query, the maximum number of corpus items per query and the average query selectivity.
E.2 Learning Representations for and x for the baselines
During experiments for Section 4.2 in each of the baseline method (Cosine similarity, Dot product and Weighted Jaccard), we use the respective similarity scoring functions, and minimize a pairwise ranking loss on the gold relevance labels to learn the deep set network. We observed that the pairwise ranking loss performs better than the BCE loss for the baselines. The margin enabled pairwise ranking loss is specified
Loss Σ
[margin + sim(q,x²) sim(q,
(98)
DEQ ZEX
x' ExE
where sim the choice of similarity scoring baseline, Xgr: Xex are the set of relevant and irrelevant corpus items for the query q. We use the best performing margin among 01...
E.3 Sampling from arbitrary distribution
One key component of FOURIERHASINNG is sampling wI...M p(w). We have chosen set p(w) & [Re(S(w)) + (Im(S(w)), with the support set between p(w) between [-100, 100). The samples are drawn using Inverse Transform Sampling
E.4 Details about fourier transformation network
In our experiments, we generate M = 10 samples for w. The neural networks dy and da are linear layers which output 10 dimensional transformed Fourier representations 2, = 2 (..M )) and
z, = Φz (Fa These are trained using the BCE loss specified Eq. (2)
uci http:///w............ooo.aooooaa
24

---

E,5 Details about hashcode generation network
We use the same hashcode training procedure for FOURIERHASHNET, as well as the DP-RH and RH baselines. In all three cases, we generate 64 dimensional hashcodes. For FOURIERHASHNET,, the random hyperplanes W are trained on 10 dimensional trained Fourier representations Zn, Zz. For RH
the original embeddings q and For DP-RH, we use the augmented embeddings g(g) sign(W[0, q/ //Il and h(z) = sign WW || x)).
E.6 AP and MAP measurements
Suppose query q associated with Nup relevant corpus items (as judged by humans). Suppose the system provides a ranking over all N corpus items, and the relevant items occur at ranks 71. NN
Then AP for query q is defined as (1/Nge) EiE (i/r:). This is because, up to position 7s we have seen relevant items, which means the sum as NoD Σ precur x rel@r, where is the size of the whole corpus, and relür the (0/1) ) relevance of the item at rank r. In case the retrieval algorithm does not assess all N corpus items, but stops with the best I. hash buckets, which contain, say, N2 items, should use the following
shorthand i/r; prec@i (precision at t). We can rewrite
N' Ei precăr x relūr. Note that we should still divide by Nga. otherwise an algorithm that maps the query to densely relevant but small bin, which fails to retrieve most relevant items, might be rewarded in an unfair manner.
formula for AP:
Ng#
E.7 Top-10 score measurement
we provide additional experiments where we compare FOURIERHASHNEH with all the baselines not only in terms of MAP, but also in terms of the Top-10 score. We the sum of Top-10 scores normalized in [0, 1] via the sigmoid transformation used in Eq. (15): Top-10(g) = ExeTop-10(N; <-d((q z)). Any hashing protocol is expected to retrieve the corpus items, which have the highest similarity scores with respect to any given query. The Top- 10 score evaluates independently of how the retrieved items match with truc relevant items. Therefore, the Top-10 scores provide an evaluation mechanism that is independent of the gold relevance labels and solely relies on the scores dictated by the trained embeddings. This offers valuable means of assessing performance without being influenced by subjective human judgments.
In Appendix F
E.8 Licenses
We utilize a publicly available pre-trained sentence transformer model 41, which is licensed under the Apache License 2.0. Additionally, employ the DrHash toolkit (58 for various implementations of the baseline Weighted Minhash (WMH) algorithms. The DrHash toolkit is publicly available under the MIT License. We duly acknowledge the original authors of the bascline methods in our citations.
25

---

Additional experiments
F.1
Applying baseline LSHs on hinge distance guided embeddings
In continuation of the results reported in Figure 3 in Figure 8 the zoomed versions of the trade-off curves for all datasets.
we present the complete view as well
FestierllashNet
RII+ Hinge
DP-RII+ OP-RII+Ilinge
WMI++
FLORA
0,8
1 0.08
f 0.6
1 0.0
1 0.0
MAP
0.4
0.4
0.2
0.2
0.0
0.0
0.0
0.0
0.0
0.5
1.0
1.5
2.0
0.0
0.5
1.0
1.5
2.0
Time
(sce)
Time
(sec)
Time (sec) +
Time
(sec)
Top-10 Score -
Top-10 Score
Top-10 Score
Top-10 10 Score
8
6
12
10
0.00
0.03 0.10 0.15 0.20
0.00
0.05
0.10 0.15 0.20
Time
(sec) 7
Time (sexc) +
Time (sec) -
Time (sec) +
MSWEB-1
(b) MSWEB-2
(c) MsNBC-1
(d) MSNBC-2
0.6
0.6
0.6
0..4
0.4
MA MAP
0.4
MAP
0.4
0.2
0.2
0.2
0.2
0.0
0.00
0.01
0.02
0.1
0.00
0.01
0.02
0.0
0.1
0.2
Time (sec)
Time (sec) +
Time (sec)
+
Time (sec)
-
Top-10 Score
Top-10 Score
Top-10 Score
Top 10 Score
6
6
4.
2
0.00
0.01
0.02
0.0
0.1
0.2
0.00
0.01
0.02
0.0
0.1
0.2
Time (sec)
Time (sec)
Time (sec)
Time (sec)
(a) MSWEB-1
(b) MsNBC-1
(c) MsWEB-2
(d) MsNBC-2
Figure 8: Trade-off between average query time and accuracy (MAP and Top-10 scores) for Ms and MsNBC datasets (First rows: complete view across full time axis, last two rows: Zoomed version of first two rows until the average query time there is 2 10X speedup compared to exhaustive search). We apply different LSH methods hinge distance guided embeddings similar to Figure then use the hinge distance to finally rank the retrieved items.
Beyond the observations made in Figure 3 we make the following additional observations. (1) The complete view for both Top-10 score and MAP score, clearly demonstrates FLORA's high sensitivity to hyperparameter tuning. FLORA is seen to have the highest variance in scores for any given time budget across all the baselines.
terms of Top-10 score, while FLORA is marginally ahead of AOURIERHASHNE in a few instances in the MSWEB datasets, it is significatly outperformed by FOURIER A NEN in the MSNBC datasets. This may due to the significantly higher average query selectivity in the MSNBC datasets.
(2) In terms of Top-10 score, FOURIERHASHNFT achieves the maximum possible value 4x faster than the nearest competitor RH+Hinge, in MSWEB-I 1 and MsWEB-2. In terms of MAP score,
26

---

HH+Hinge and WMH+HHing achieve maximum MAP of 0.5 in MSWEB-L 1 and MsWEB-2, and 0.62 in MSNBC-1 and MsNBC-2. However, FOURIERHASHNET achieves the same MAP values 1.33x faster in MSWEB- I and MSW and 2x faster in MsNBC-1 and MsNBC-2.
(3) Interestingly, the gap between FOURIERHASHNET and Hine seems to widen for MBW2.- when compared to MSWEB-1. 1. This is possibly due to the presence of several queries in MB-B. which have 2300 relevant corpus items. This affords RH+Hinge a greater opportunity to fetch high scoring items, which is not the case in MsWEB-2.
F.2 Ablation study hashcode training
In continuation of the results reported in Figure in Figure present the complete view well as the zoomed versions the trade-off curves for all datasets.
HourierHashNet
FHash (Untrained)
RH+H (Untrained)
DP-RH- RR-Hingee( Me-RH--HingeUuueeee Untrained)
0.8
0.8
0.9
f 0.6
0.6
1 0.6
MAP
0.4
MAP
0..4
0.2
0.2
0.2
0.0
0.0
0.0
0.00 0.05 0.10 0.15 0.20
0.0
0.5
1.0
1.5
2.0
0.00
0.05
0.10 0.15 0.20
0.0
0.5
1.0 1.5 (sec)
2.0
Time (sec) ->
Time
(sec)
Time (sec) ->
Time
10
10
Top-10 Score
Top-10 Score
Top-10 10 Score
Top-10 Score
8
>
13
0.00 0.05 0.10 0.15 0.20
0.0 0.5
1.0
1.5 2.0
0.00 0.05 0.10 0.15 0.20
0.0 0.5
2.0
Time (sec) -
Time
(sec)
+
Time (sec) +
Time (sec) +
(a) MSWEB-I
(b) MsWEB-2
(c) MsNBC-1
(d) MSNBC-2
0.8
0.8
1 0.44
1 0.6
1 0.1
MAP
MAP
0.4
0.2
0.2
0.0
0.0
Time (sec) +
Time (sec) +
Time (sec) +
Time (sec) +
10
10
10
Top- 10 Score
Top-11 10 Score
8
Top-10 10 Score
8
Top-11 10 Score
6
0.00
0,01
0.02
0.0
0.1
0.2
0.00
0.01
0.02
0.0
0.1
0.2
Time (soc)
Time (sec)
Time (sec)
Time (sec)
(a) Ms
(b) MsNBC-1
(c) MsWEB-2
(d) MsNBC-2
Figure 9: Trade-off between average query time and accuracy (MAP and Top-10 scores) for Ms WBB and MsNBC datasets (First two rows: complete view across full time axis, last two rows: Zoomed version of first two rows until the average query time there is > 10X speedup compared to exhaustive search). We compare FHASH (UNTRAINED) against the untrained versions of RH+Hinge and DP. RH+Hinge, well as against FOURIERHASHNET..
Beyond the observations made in Figure 5 we make the following additional observations. (1) In terms of both Top-10 10 score and MAP score, FHASH (UNTRAINED) clearly outperforms both RinHinge and DP-RE Hi-RHe across all four datasets. This strongly highlights the advantage of our
27

---

Fourier feature generation method. (2) In every setup, FOURIERHASHNET enables wider range of options for accuracy score vs retrieval time trade-off.
F.3
Ablation study on collision minimizer 14
Collision Minimiss
Daegy iinio
0.6
0.5
MAP
MAP
0.0
Collision Minimizer
Collision Minimiser
Collision Minimison
Decorrvttiion
Decorrelation
Decorolation
0.2
0.00
0.05
8.30
8.35
0.20
Do
0.5
14
15
20
0.50
0.s Time (see) -
0,05
0.1
0.0
0.0
15 Time (sec) -
0.
1.0
2.
Time
(sec)
Time (sec)
-
Top-10 10 Score
9.5
Top- 10 Score
9.5
Top-10 Score
9.75
9.50
9.0
9.25
8.5
9.00
8.0
8.75
Collisiop
CollisSon Minimize
Collision Mininises
8.50
Collisii Minimizes
7.5
Decorrelation
Decorvdlatonn
Decorrebation
8.25
Dicorrelation
0.00 0.05 0.10 0.15 0.20
0.0
1.
1,5 2.0
0.00 0.05 0.10 0,15 0.20
0.0
0.5
1.0 1.5 2.0
Time (sec) +
Time (sec) +
Time (sec) +
Time (sec)
(a) Ms 1
(b) MSNBC-1
(c) MsWEB-2
(d) MsNBC-2
0.8
Decorrelation
Collision Minimiser
Decorielation
Collision Minimizer
0.8
1 0.6
MAP
0.6
MAP
0.6
MAP
0.4
0.4
Collisson
0.3
Collision Minimizer
Decorelation
Decorcelation
0.2
0.00
0.01
01.2
0.000.050. 1.00110.1100.0000
0.00
0.01
0.02
0.000.050.100.1
1.0....0...00000 100.150.200.2.
Time (sec)
Time (sec) +
Time (sec)
Time (sec) >
Top-10 Score f
10
T 9.75
9.5
Top- 10 Score
Top-10 Score
Top- 10 Score
9.50
9.0
9.0
9.25
8.5
9.00
8.0
8.5
8.75
Collision Minimizne
Collision Mininsisce
Collision Miniminee
8.50
Minimisue
7.5
Decorrclation
Decorrelation
Decoprelation
8.25
Decorrclation
0.000.050 000..050.10..13 250.155.20
0.00
0.01
0.02
0.000.050. 100.0050110.11110 50.200.25
Time (sec)
Time (sec) +
Time (sec)
+
Time (sce) -
(a) MsWEB-1
(b) MSNBC-1
(c) MsWEB-2
(d) MsNBC-2
Figure 10: Trade-off between mean query time and accuracy (MAP and Top- scores) for MsWER and MsNBC datasets (First two rows: complete view across full time axis, last two rows: Zoomed version of first two rows until mean query time there 10X speedup compared to exhaustive search). We compare our hashcode training loss loss(Q, X W) (14), against variant which replaces the collision minimizer component A₁ with decorrelation loss Σnボy |tanh( W 2x) tanh W zy)l-
In continuation of the results reported Figure 6 zoomed versions of the trade-off curves for all datasets. Beyond the observations made in Figure we make the following additional observations.
we present the complete view as well as the
(1) In MSWEB-I 2, the alternative variant shows sudden plunge in MAP performance trade-off at around 0. seconds. This type of discontinuous drop is not observed in any of our cases. (2) In MSWEB-I. there is variation of 0.1 MAP at around 0.05 seconds. Such high variability is not observed for any of our trade-off curves.
F.4 Identifying best performing Weighted Minhash algorithm for our datasets
For implementation of baseline Weighted Minhash (WMH) algorithm, we use the best performing WMH implementation available in the DrHash toolkit [58) to obtain the hasheodes. We comapare
28

---

mielaahh
11.8
11.5
0.5
Hewa
0.00
pone
01.
0.6
0.6
MAP
MAP
0.4
0.4
gillaguol22
[UI)
0.01
Time (sec) +
(snr)
Time (sec)
(scc)
10
Top-10 Scorm
Rop- 10 Score
Scort 10 Fodoo
Jum
News
Sewa
liew
Top- 10
pets
pows
Jowss
octra
gollljjud12
gollsgodd1
-pllaapddi
0.00
0.01
0.02
0.2
0.00
0.81
0.02
0.0
0.1
6.2
Time (sec)
Time (sec)
Time (soc)
Time (sec)
(a) MSWEB-1
(b) MsNBC-1
(c)
MsWEB-2
(d) MSNBC-2
Figure 11: We compare performance of Weighted Minhash variations, in terms of trade-off between
mean query time and accuracy (MAP and Top-10 10 scores) for MSWEB and MsNBC datasets, until the query time there 10X speedup compared exhaustive search.
across the 8 available baselines in the toolkit: minhash 77. chum 28]. cews (55). i2cws [57] and gollapudi2 [16].
icws 20 pews [56. liews
We make the following observations.
(1) Across all four of our datasets, for both MAP and Top-10 score, the top performers are minhash, gollapudi2 and chum. The remaining algorithms are often significantly worse in performance, as can be seen for MAP in all 4 datasets and for Top- in MsNBC-2.
(2) Among the top performers, chum is to be the best perform in terms for both MAP and Top-10 10 score, in WEB-B2 MSNBC-1 and MsNBC-2, In MsWEB- 1, chum is tied with minhash and gollapudi2 for the top position.
Driven by these observations, we choose chum as the representative baseline for WMH our experiments.
29

---

F5
Effect of M, number of samples of w on FOURIERHASHNET performance
Top- 10 Secore
Tuo
You gr-in Scou
MAP
RourirtHabNNeetDD
NnurertlashNett00
Fourier (ee
HourcHHalNoo1100)
I.10 Time (sec)
6:8 6:15
DE0
DU00
0.10
0.15
0.u
0 0.15 a.o
Time (soc)
Time (sec)
Time (sec)
(a) MSWEB-1
(b) MSWEB-1
(a) MsWEB-I
(b)
MSWEB-2
Figure 12: Effect of M, number of samples, the trade-off between mean query time and accuracy
(MAP and Top-10 10 scores) for MsW WEB datasets.
Here we check the impact of varying the number of samples (M) for w. We consider three different values of M, i.e., 10, 50 and 100, for generating the fourier features (1w..... and F, (I. which are then fed into the neural networks 0y and by for learning the transformed Fourier representa- tions 2y and zg. using the BCE loss specified in Eq. (12). Finally, train the random hyperplanes W and check the MAP and Top-10 score performances for the three variations FOURIERHASHNETTE COURIERHAHHNETEE
We observe that the final performance trade- off of both MAP and Top-10 10 scores, remains roughly the same across all three variants. This shows that trainable Fourier transformation is able compensate for the quality of Monte Carlo approximations affected by the number of w samples M.
and FOURIERHASHNNET(ION
Next, we investigate how well the MC estimates of the Fourier features approximate the dominance similarity function sim(g, Here, we set the dimension of q and æ as K 20 and we sample q, x simas (), |.F.(u..."' cos( Fo (1o2..M)) F2 ()) and measure the variation of 6im M aq -00 [||sim(g. x) sim (g. =)]l] with M, the number of samples of w. Figure 13 sum- marizes the results, which shows as M increases, Gai decreases.
We set
Uni 20). Finally, we compute
35
30
25
20
15
10
5
# w samples (M) +
Figure 13: Variation of 6sim Un ssmmmm x)) sim (g, with M. the number of
samples.
30

---

F.6 Applying baseline LSHs on hinge distance guided embeddings with noisy labels
certain applications, the accuracy of ground truth labels can be compromised by noise or subjective human judgments of relevance. We evaluate the performance of FOURIERHASHNEI and the baselines noisy label setup test its robustness.
Starting with the hinge distance guided embeddings, initially rank the corpus items based their dominance similarity scores. Subsequently, we intentionally flip the labels of the bottom-ranking 10% of positive labels to negative, and equal number of highest ranked negatively labeled items to positive. This simulation reflects a plausible scenario since the lowest ranked positive items and the highest ranked negative items are particularly susceptible to misclassification in real-world settings. Furthermore, this approach ensures that the average query selectivity for each dataset remains unchanged.
As before, we apply different the LSH methods on hinge distance guided embeddings, viz, RH+Hinge, Hi-Re, WMHH+Hinge, FLORA and HOURIERHASHNETT and, then use the hinge distance to finally rank the retrieved items.
FourierHashhett
Ringe
DP-RH+ Hinge
W WMH+ WMH+Hinng
FLORA
0.8
f 0.6
0.00
0.6
0.0
MAP
0.4
0.4
MAP
0.4
0.2
0.0
0.0
0.0
0.0
0.0
0.5
1.0
1.5
2.0
0.0
0.5
1.0
1.5
2.0
Time (sec)
Time
(sec)
Time (sec)
Time (sec)
10
10
Top-10 Score
Top-10 1op-10 Score
Top-10 10 Score
Top-10 Score
6
6
12
1
0.20
Time (sec) >
Time (sec)
Time (sec) ->
Time (sec) +
MsWEB-
(b) MsWEn-2
(c) MsNBC-1
(d) MsNBC-2
0.6
0.6
0.6
MAP
0.4
0.4
MAP
0..4
0.2
0.2
0.2
0.2
0.0
0.0
0.0
0.0
Time (sec)
Time (sec) +
Time (sec) +
Time (sec)
10
10
Top-10 Score
Top- 10 Score
Top- 10 Score
Top- 10 Score
1
0.00
0.01
0.02
0.1
0.2
0.00
0.01
0.02
0.0
0.1
0.2
Time (sec)
Time (sec)
Time (sec)
Time (sec)
(a) MsWEB-1
(b) MsNBC-1
(c) MsWEB-2
(d) MsNBC-2
Figure 14: Trade-off between average query time and accuracy (MAP and Top-10 10 scores) for Ms MB and MSNBC datasets (First two rows: complete view across full time axis, last two rows: Zoomed version of first two rows until the average query time there is > 10X speedup compared to exhaustive search). We apply different LSH methods on hinge distance guided embeddings similar Figure and then use hinge distance to rank retrieved items. Evaluations are conducted using noisy labels.
31

---

We make the following observations.
(1) In terms of MAP score, FOURIERHASHNET continues to outperform all other baselines across all four datasets. Furthermore, when comparing the performance in the presence of noise, as depicted in Figure [4] to the corresponding results obtained the noiseless setting illustrated in Figure X we observe that FOURIERHASHNET outperforms all its competitors by significantly higher margin in the presence noise.
(2) In terms of Top-10 score, we note that the results in Figure 14 for the noisy setup are identical to the results presented in the noiseless setting shown in Figure 8 This observation indicates that the evaluation based on Top-10 score is unaffected by label noise. This supports the argument made in Appendix E.7 that Top- 10 score evaluation enables more subjective assessment of performance, focusing on the quality of the embeddings themselves.
F.7 Comparison with graph based indexing methods
Here, we compare the performance of FOURIER with a representative graph based indexing method. We use the Hierarchical Navigable Small Worlds (HNSW) implementation of Hnswlib [3 We extend the Interface class of amslib/aet Hts///mslbbbbb to implement HNSW for hinge distance. In order track the number of distance computations performed by HNSW during retrieval, used a counter inside fstdistfunc_. We count the number of distance computations as a surrogate for real time, avoid non-determinism in measurements and low-level implementation differences. We search across different values of M, ef and ef construction, and track the number of distance computations against corresponding MAP values.
#calls to fstdistti snfuct_
MAP
Method
839
0.17
HNSW
1162
0.53
FOURIERHASHNET
1549
0.43
HNSW
1668
0.51
HNSW
1846
0.58
FOURIERHASHNET
2578
0.59
HNSW
3529
0.71
HNSW
3926
0.72
FOURIERHASHNETT
4773
0.77
HNSW
Table 15: Number of distance computations and the corresponding MAP values on MsWEB ffr HNSW and FOURIERHASHNET.
Table presents our study on MsWEB- dataset with 10734 corpus items. We observe that FOURIER- HASHNET LSH has an edge over HNSW in the regime of fewer distance computations, with a MAP of 0.53 using 1162 distance computations. However, when allowed more distance computations, HNSW outperforms FOURERRASHNNET with MAP of 0.71 in 3528 computations, and MAP of 0.77 in 4773 computations.
32


Reviews:
[{"review_id": "rXvFVgQ6aj", "reviewer": "Reviewer_2JDE", "summary": "This paper studies a new search problem called vector dominance (or set containment), where the authors provide strong motivation from various real-world applications. They present a new approach named FourierHashNet along with a fresh asymmetric vector dominance distance to address this problem. Through extensive experimentation, the study confirms the effectiveness of the proposed distance measure and demonstrates the superior performance of FourierHashNet compared to established LSH and ALSH baselines.", "questions": "Please further proofread and polish the paper.", "limitations": "This work does not appear to have any negative social impact.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The authors study a new yet significant problem, which contains many well-motivated applications regarding text, image, and graph retrieval.\n\n- They propose an effective distance measure customized for the problem they looked at.\n\n- The FourierHashNet is interesting, and it is reasonable to combine learning to hash together with Fourier features.\n\n- They conduct extensive experiments to confirm the effectiveness of FourierHashNet.", "weaknesses": "Overall, in my opinion, this is a well-written paper in various aspects. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "The authors thank reviewer 2JDE for the positive feedback. We will undertake thorough proofreading and polishing for the final version of the manuscript."}, {"review_id": "EAPhemR7uj", "reviewer": "Reviewer_AbHb", "summary": "Locality-sensitive hash (LSH) functions are mappings from sets of queries and documents to \"buckets,\" in such a way that similar queries and documents are assigned to the same bucket. This paper proposes an asymmetric LSH where the notion of similarity is related to the hinge distance (called dominance similarity, based on the element-wise inequalities between components of two vectors). The method conceptually follows three steps: truncate, transform, and sample. First, the dominance similarity is truncated to a bounded region of the input domain; this is done so that the problem is tractable. Then, the similarity is Fourier-transformed into a form where the contributions from different vectors separate into an inner product. This form is used to sample Fourier representations that are used to compute the LSH in practice.\n\nThe paper also contains experiments comparing the proposed ALSH with other LSH algorithms on two web log datasets, where the task is to perform vector search under the hinge distance. FourierHashNet outperforms these methods by a sizable margin. To further improve practical performance, the paper proposes a learnable version of the algorithm and conducts ablations to investigate its effect.\n\n**Post rebuttal:** The authors provide a general framework for ALSH, of which the hinge distance LSH is a specific instance. This substantially extends the utility and impact of the method over the original proposal.\n", "questions": "I like this line of research and would be willing to raise my score if some of the following items can be addressed. In particular, I'm looking for evidence that the hinge distance is an important bottleneck and for evidence that the new techniques developed in this paper could be useful more broadly.\n\n- Is it possible to generalize the sampling process (bottom of page 5) into a generic algorithm with theoretical guarantees (e.g. on the expectation and possibly variance of the estimate)? This would go a long way towards addressing W2, as it would be a result that other works could build off of.\n\n- Is element-wise vector inequality the current state-of-the-art for the applications mentioned in the paper? ColBERT (which examines all pairwise relationships between the two sets) and follow-ups have shown very good results in natural language applications, and determinental point processes are SOTA in many market basket analysis applications (e.g. \"Learning Nonsymmetric Determinantal Point Processes\" at [NeurIPS 2019](https://proceedings.neurips.cc/paper_files/paper/2019/file/cae82d4350cc23aca7fc9ae38dab38ab-Paper.pdf)). I am less familiar with the knowledge graphs and subgraph isomorphism applications mentioned in the appendix so it might be possible that the problem is very strongly motivated by these areas. I did take a quick look at the references but I did not find this search problem mentioned.\n\n- Can this algorithm handle box embeddings (perhaps with some modifications to the algorithm / the embeddings)? Search over box embeddings is a known bottleneck and is one reason why, despite modeling advantages, they have not replaced angular-similarity embeddings in major industrial recommendation pipelines.\n\n- Is it possible to prove that this scheme is an ALSH (i.e. satisfies Defintion 2.2) for the hinge distance? Due to the truncation in Equation (4), it might be necessary to restrict the domain over which we expect Definition 2.2 to hold (but this would be fine and would not affect the quality of the theoretical result).\n\n- Just to clarify - what are the \"gold\" and \"silver\" instances on page 6? Is this the same as the gold relevance labels from the datasets (page 7)?\n", "limitations": "Yes - no issues.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 4, "strengths": "**S1: Important topic.** The problem of designing an asymmetric LSH with an exotic collision probability is useful and interesting. There is not much work in this area, but there are several emerging LSH applications (not just search) where this capability will be helpful. For example, the [LGD sampler [NeurIPS 2019]](https://proceedings.neurips.cc/paper_files/paper/2019/file/a1e865a9b1065392ed6035d8ccd072d9-Paper.pdf) uses LSH functions that are sensitive to classification loss functions. Some of these are non-symmetric, so new ways to construct asymmetric LSH can correspond to faster optimization routines for more problems. \nThe efficient kernel-matrix multiplication algorithm of Backurs et. al. [[ICML 2021]](https://arxiv.org/abs/2102.08341) is based on LSH and currently only works for symmetric kernels - asymmetric LSH could substantially extend this framework.\nAn asymmetric LSH was recently developed for the linear regression/classification loss and was used to learn differentially-private classifiers [[CCS 2021]](https://dl.acm.org/doi/abs/10.1145/3460120.3485255); new ALSH functions will also directly expand the usefulness of this framework.\nTherefore, ALSH is an increasingly important topic with the potential to impact search, ranking, optimization, numerical linear algebra, differential privacy, and likely other areas.\n\n**S1: Novelty.** This paper attacks a technically difficult problem (ALSH for the hinge distance) and introduces some new ALSH techniques to do the design. I checked the math and the results seem to be correct. Note that I did not check details (e.g. the algebra involved in going from (7) to (8), or the derivation of (5) in the appendix).\n", "weaknesses": "**W1: Presentation.** The presentation and flow of the argument can be improved. Here are some specific examples:\n- The \"i\" used to denote sqrt(-1) should probably be the standard italic i (with a dot) rather than the symbol \\i. \n- It may be more correct to refer to the \"hinge distance\" as the \"hinge quasimetric\" or the \"hinge divergence\" because it is not strictly speaking a metric (it obeys all properties except symmetry).\n- On line 177, consider mentioning that Equation (3) is just the Fourier Transform of -d(q,x) from Equation (1). It took me a moment to determine why (3) was written as the sum rather than as K iterated integrals.\n- Equation (4) could be introduced as a \"clamped\" or \"truncated\" version of -d(q,x), to make its definition more clear to the reader.\n- The \"Fence Sitting\" and \"bit balance\" losses don't seem particularly well-known (the only reference I could find was in \"Adversarial Permutation Guided Node Representations for Link Prediction\" in [AAAI 2021](https://arxiv.org/abs/2012.08974) - this paper should probably be cited). Therefore, these losses could possibly use some more explanation.\n- The results figures for the experiments would benefit from better layout to make the graphics larger (e.g. using subplots with tight_layout or similar).\n- Several components seem out of place. For example, the formal definitions of LSH and ALSH are introduced but are not used to prove that the hash function is indeed an ALSH. Observations about symmetric LSH (e.g. the paper by Chierichetti and Kumar) are mentioned throughout the development of the asymmetric LSH in Section 3, and it might be clearer to collect all these arguments in Section 2. The sampling algorithm is fairly involved and probably merits its own section. \n\n**W2: Impact.** The main contribution of the paper is an asymmetric LSH function for a very specific similarity function. This paper could have an impact on the LSH algorithm area and on any area that uses the hinge distance for set search. However, I have some concerns about the applicability of the ideas outside of what seems to be a fairly niche search problem.\n\n- **On LSH.** As mentioned above, there are several problems that can benefit from asymmetric LSH. However, it is hard to see which contributions from this paper might be more broadly applicable. It would be much more interesting (and appeal to a wider audience) if this algorithm can be generalized into a broader \"truncate - transform - sample\" template. Such a template might apply directly to other applications. It is also fairly essential to demonstrate that this is, indeed, an ALSH (that provably satisfies Definition 2.2).\n- **On set-search.** The community seems to be moving away from representing sets as a single vector and toward approaches that examine the pairwise similarity between all elements in the set (e.g. [ColBERT](https://arxiv.org/pdf/2004.12832.pdf), [ColBERT v2](https://arxiv.org/abs/2112.01488), [PLAID](https://arxiv.org/abs/2205.09707), several follow-ups). This approach was originally motivated by the comparatively high cost of performing transformer inference but is now [doing very well](https://arxiv.org/abs/2212.01340) on tasks like passage ranking. Many of the papers cited as applications are more than five years old (pre-2019), so it is not clear whether search with the hinge distance is still a pressing problem.\n\n**W3: Experiments.** The baselines in the experiments are not very competitive, leading to a limited evaluation. LSH is a classical, standard technique but it is no longer state-of-the-art for most search/ranking problems. Other approaches (like FAISS-IVF or HNSW) have taken over as the search algorithm of choice. These methods are also compatible with the hinge distance (though, this does require use of the C++ APIs rather than the simpler Python API). They also tend to be an order of magnitude faster than LSH, according to well-established benchmarks ([ann-benchmarks](https://ann-benchmarks.com), see also the NeurIPS 21 competition [big-ann-benchmarks](https://big-ann-benchmarks.com)).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank reviewer AbHb for the spectacular feedback.\n> Proof that FourierHashNet is an ALSH\n\nNote that $p(\\omega^j_k)\\propto|Re(S(\\omega _k ^{j}))|+|Im(S(\\omega _k ^{j}))|$. Let $I$ be the proportionality constant.  Assume $\\mathrm{sim}(q,x)>s _m>0$ and  $\\cos^{-1}$ is $L _{\\cos}$-Lipschitz. \n\nWe have: $||\\pmb{F} _q(\\pmb{\\omega}^{1...M})|| _2^2=||\\pmb{F} _x(\\pmb{\\omega}^{1...M})|| _2^2= \\sum _{i\\in[M],k\\in[K]}\\frac{|Re(S(\\omega\\_k^j))|+|Im(S(\\omega\\_k^j))|}{p(\\omega^j _k)}=MKI$.\n\nWe use $\\Pr _{g,h}[g(q)=h(x)]=\\mathbb{E} _{\\pmb{\\omega^{j}}}[\\Pr _{g,h}[g(q)=h(x)|\\pmb{\\omega}^j]]$ to write\n\\begin{align}\n&\\Pr _{g,h}[g(q)=h(x)|\\pmb{\\omega}^i]=1-\\frac{1}{\\pi}\\cos^{-1}\\bigg(\\frac{\\pmb{F} _q(\\pmb{\\omega}^{1...M})^{\\top}\\pmb{F} _x(\\pmb{\\omega}^{1...M})}{||\\pmb{F} _q(\\pmb{\\omega}^{1...M})||\\ ||\\pmb{F} _x(\\pmb{\\omega}^{1...M})||}\\bigg) \\\\\\\\\n&=1-\\frac{1}{\\pi}\\cos^{-1}\\bigg(\\frac{\\operatorname{sim}(q,x)}{KI}\\bigg) \\\\\\\\\n&-\\frac{1}{\\pi}\\cos^{-1}\\bigg(\\frac{\\pmb{F} _q(\\pmb{\\omega}^{1...M})^{\\top}\\pmb{F} _x(\\pmb{\\omega}^{1...M})}{MKI}\\bigg)\n+\\frac{1}{\\pi}\\cos^{-1}\\bigg(\\int _{\\omega}\\frac{\\pmb{F} _q(\\pmb{\\omega})^{\\top}\\pmb{F} _x(\\pmb{\\omega})p(\\pmb{\\omega}) d \\pmb{\\omega}}{KI}\\bigg)---(A)\n\\end{align}\nNote\n\\begin{align}\n&\\mathbb{E}\\bigg[-\\cos^{-1}\\bigg(\\frac{\\pmb{F}_q(\\pmb{\\omega}^{1...M})^{\\top}\\pmb{F}_x(\\pmb{\\omega}^{1...M})}{MKI}\\bigg)\n+\\cos^{-1}\\bigg(\\int _{\\omega}\\frac{\\pmb{F}_q(\\pmb{\\omega})^{\\top}\\pmb{F}_x(\\pmb{\\omega})p(\\pmb{\\omega}) d \\pmb{\\omega}}{KI}\\bigg) \\bigg] \\\\\\\\\n&\\le\\frac{L _{\\cos}}{KI}\\mathbb{E}\\bigg|\\sum _{j\\in[M]}\\pmb{F}_q(\\pmb{\\omega}^{j})^{\\top}\\pmb{F}_x(\\pmb{\\omega}^{j})/M-\\int _{\\omega} \\pmb{F} _q(\\pmb{\\omega})^{\\top}\\pmb{F} _x(\\pmb{\\omega})p(\\pmb{\\omega}) d \\pmb{\\omega}\\bigg|\n\\\\\\\\\n&=\\frac{L _{\\cos}}{KI\\sqrt{M}}\\sqrt{K}\\bigg(\\text{Var}\\bigg[\\pmb{F}_q(\\omega_k)^{\\top}\\pmb{F}_x(\\omega_k )\\bigg]\\bigg)^{1/2}\\le\\frac{L _{\\cos}}{\\sqrt{KM}}---(B)\n\\end{align}\nThe last inequality follows from a bound on variance via\n\\begin{align}\n&\\pmb{F}_q(\\omega_k)^{\\top}\\pmb{F}_x(\\omega_k)\\\\\\\\\n&=\\pmb{S}_q(\\omega_k)^{\\top}\\pmb{S}_x(\\omega_k)/p(\\omega_k)\\quad(\\text{Eq 9 in paper})\\\\\\\\\n&=\\frac{Re[\\pmb{S}(\\omega)]\\cos\\omega_k(q[k]-x[k])-Im[\\pmb{S}(\\omega)]\\sin\\omega_k(q[k]-x[k]))}{(1/I)[|Re[\\pmb{S}(\\omega)]|+ |Im[\\pmb{S}(\\omega)]|]}\\\\\\\\\n&\\le I\\frac{|Re[\\pmb{S}(\\omega_k)]|+|Im[\\pmb{S}(\\omega_k)]|}{|Re[\\pmb{S}(\\omega)]|+|Im[\\pmb{S}(\\omega)]|}=I\n\\end{align}\n\nPutting (B) into (A), we have\n\\begin{align}\n\\mathbb{E}[\\Pr\\_{g,h}[g(q)=h(x)|\\pmb{\\omega}^{j}]]\\le p_2=1-\\frac{1}{\\pi}\\cos^{-1}\\bigg(\\frac{\\operatorname{sim}(q,x)}{KI}\\bigg)+ L_{\\cos}/\\pi\\sqrt{KM}\n\\end{align}\nSimilarly, we have:\n\\begin{align}\n\\mathbb{E}[\\Pr\\_{g,h}[g(q)=h(x)|\\pmb{\\omega}^{j}]]\\ge p_1=1-\\frac{1}{\\pi}\\cos^{-1}\\bigg(\\frac{\\operatorname{sim}(q,x)}{KI}\\bigg)- L_{\\cos}/\\pi\\sqrt{KM}\n\\end{align}\n\nIf we ensure\n\\begin{align}\nM>\\frac{4L _{\\cos}^2}{K\\left[\\cos^{-1}\\big(\\frac{c\\cdot s _m}{KI}\\big)-\\cos^{-1}\\left(\\frac{s _m}{KI}\\right)\\right]^2},\n\\end{align}\nthen we have $p_1>p_2$. This satisfies the condition for ALSH.\n\n> *W3: Experiments. ColBERT/FAISS/HNSW vs A/LSH and FourierHashnet*\n\nFourierHashNet beats FLORA (Fig 3 in main), which is a very recent (2023) neural retrieval model that outperforms HNSW.\n\nIn response to your highlighting FAISS-IVF, we compare the retrieval performance of FAISS-IVF variants against FourierHashNet (Fig. 14 and 15 of the rebuttal PDF). FAISS-IVF retrieval suffers because its quantizers, that assign vectors to the Voronoi cells, rely on a metric like L2 or IP, which are unsuitable for asymmetric hinge distance. Also, IVF-style retrieval may fall short in other applications. We will incorporate the following discussion into the manuscript.\n\n**Textual entailment** (SNLI, MNLI) is usually presented as *classification*: (text_a, text_b) → {implies, contradicts, none} etc. The most accurate methods inject ([CLS], text_a, [SEP], text_b) into an early-cross-interaction transformer, and predict the label from the output [CLS] embedding.  The associated *retrieval* problem is, given text_b and a large corpus, quickly find top-K corpus text_a that are most likely to imply text_b. Early-cross-interaction precludes effective indexing/hashing. Lai+Hockenmaier propose asymmetric late interaction: separately obtain embeddings of text_a and text_b, and force the former to elementwise dominate the latter (by fine-tuning the transformer). Thanks to our work, dominance distance is now hashable.\n\n**Box embeddings** and **order embeddings** are used to model type hierarchies in knowledge graphs (KGs) and object hierarchies in images. If type t1 is subtype-of t2, we expect their order embeddings to follow elementwise dominance, or the box embeddings of t1 to be contained in that of t1. They can be used in our setup; see global response.\n\n> *In set-search, elementwise cross-interaction better than single set embeddings?*\n\nFor applications other than retrieving soft supersets of the query set (as is the case in ColBERT-type passage retrieval) ColBERT and follow-ups may not be the best choice:\n* ColBERT uses a symmetric term-to-term similarity, which is inadequate for detecting subgraph isomorphism. unlike hinge distance — see Table 16 in rebuttal PDF. \n* If we are looking for subsets (rather than supersets) of the query, then our hinge distance continues to work. But ColBERT can now assign multiple query atoms to the same passage atom.\n* If the query (text or graph) is large, ColBERT (using IVF) will still hit many FAISS clusters and thus amass a large number of corpus items to score. This can be controlled better using ALSH in Fourier space.\n\nFor these reasons we believe ALSH for hinge distance remains very strongly motivated.\n\n>*\"gold\" and \"silver\"*\n\nInstances with gold labels means ground-truth relevance labels.  After training with gold labels, silver labels are predicted from hinge distances. These are used to train the hashing protocol.\n\n>*broader application of \"truncate - transform - sample\" template.*\n\nPlease refer to general response."}, {"review_id": "JxaJ57oJ95", "reviewer": "Reviewer_wHYk", "summary": "This paper presents a novel approach, called FourierHashNet, for fast soft set containment search. The key idea is to extend set containment to soft set containment by representing query and document elements as embedded representations, instead of atomic IDs. The authors propose a dominance similarity measure based on hinge distance and transform it into the frequency domain using a Fourier transform. This allows for the efficient use of traditional LSH techniques. \n", "questions": "Is it possible to discuss the potential of FourierHashNet in the similarity search of general kernel measure?", "limitations": "Yes, the authors adequately addressed the limitations", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Strength:\n\n1. The significance of the proposed asymmetric dominance similarity measure is emphasized, indicating its critical role in the targeted applications. By transforming the dominance similarity measure into the frequency domain, the authors enable the utilization of traditional LSH methods. This approach not only enhances retrieval efficiency but also demonstrates a better trade-off between query time and retrieval quality.\n\n2. This paper is well-written. It effectively communicates the technical aspects of the proposed method, including the use of the Fourier transform and the learning of data-sensitive hash codes. \n", "weaknesses": "NA", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "The authors thank reviewer wHYk for the positive feedback. \nIn the general response,  we delve into a broader application context of FourierHashNet, particularly for similarity search involving shift invariant functions. \nPlease reach out to us if you have further inquiries or points for clarification. "}]

Author rebuttal:
# Truncate-transform-sample paradigm

### General Framework

Indeed, our algorithm can be generalized to include a wide variety of scoring functions, including Box embedding based volume scores, facility location scores used by ColBERT, etc.

Our framework extends to any shift-invariant scoring function of the form: $a(\pmb{q} -\pmb{x})$, which remains unchanged if $\pmb{q}$ and $\pmb{x}$ are shifted by the $\pmb{\delta}$. Assuming bounded values $||\pmb{q}|| _{\infty} \le q _{\max}$ and $||\pmb{x}|| _{\infty} \le x _{\max}$, a truncated function $sim(q,x) = s(\pmb{q} -\pmb{x}) = a(\pmb{q} -\pmb{x}) -a
_{\min}$, is active only within the specified bounds, and zero otherwise (In our case, $a = -d(q,x)$ and $a _{min} = -KT$).

This allows an absolutely convergent (because of trunctation) Fourier transformation:

\begin{align}
S(\pmb{\omega})=\frac{1}{(2\pi)^K} \int_{\pmb{t} \in \mathbb{R}^K}s(t) e^{-i \pmb{ \omega}^\top \pmb{t} } d \pmb{ t } 
\end{align}
and the Inverse Fourier Transform of $s(\pmb{q} -\pmb{x})$ as:
\begin{align}
 s(\pmb{q} -\pmb{x}) & = \int_{\pmb{\omega} \in \mathbb{R}^K} S(\pmb{\omega})  e^{i \pmb{ \omega}^\top (\pmb{q} -\pmb{x}) } d \pmb{ \omega} 
  = \int_{\pmb{\omega} \in \mathbb{R}^K} \pmb{S}_q(\pmb{\omega}) ^{\top} \pmb{S}_x(\pmb{\omega}) d\pmb{\omega} 
\end{align}

Here,
\begin{align}
  \pmb{S}_q( \pmb{\omega}) {=} \Big[\text{Sign}(Re(S(\pmb{\omega}))\sqrt{|Re(S(\pmb{\omega}))|} \big[\cos(\pmb{\omega}^\top \pmb{q}), \sin(\pmb{\omega}^\top \pmb{q})\big],  
\text{Sign}(Im(S(\pmb{\omega})) \sqrt{| Im(S(\pmb{\omega})|}\big[-\sin(\pmb{\omega}^\top \pmb{q}), \cos(\pmb{\omega}^\top \pmb{q}) \big]\Big]
\end{align}
and
\begin{align}
  \pmb{S}_x( \pmb{\omega}) {=} \Big[ \sqrt{|Re(S(\pmb{\omega}))|} \big[\cos(\pmb{\omega}^\top \pmb{q}), \sin(\pmb{\omega}^\top \pmb{q})\big],  
  \sqrt{| Im(S(\pmb{\omega})|}\big[\cos(\pmb{\omega}^\top \pmb{q}), \sin(\pmb{\omega}^\top \pmb{q}) \big]\Big]
\end{align}

Above expressions are similar to Eq (7) in our paper, where they were defined for each component frequency $\omega_k$, thanks to the decomposability of the score functions as a sum of independent scores across dimensions $(s(\pmb{q}-\pmb{x}) = \sum  _{k=1} ^K s(q[k]-x[k]) )$. In contrast, here, we show that the setup can be extended to generic (shift invariant) scoring functions which need not be decomposable as a sum across dimensions. 

However, we can define a similar distribution $p(\pmb{\omega})$ over the vector $\pmb{\omega}$ and obtain $s(\pmb{q} -\pmb{x})  = \mathbb{E} _{p(\pmb{\omega})}  [  \pmb{S}_q( \pmb{\omega})^{\top}   \pmb{S}_x( \pmb{\omega})/p(\pmb{\omega})]$.

### ColBERT

E.g., given a query $q = (q _1,.., q _m)$ and one corpus item $x  = (x_1,...,x_n)$, ColBERT computes the (facility location based) similarity scores between these two sets as
\begin{align}
\operatorname{sim}(q,x) =\sum _{i =1} ^m  \max _{j \in [n]} a(q _i,x _j) 
\end{align}
If $a$ is a shift invariant score $a(\pmb{q} _i-\pmb{x} _j)$, say, inverse to Euclidean distance, then we can write its soft surrogate
\begin{align}
\operatorname{sim}(q,x) &=\frac{1}{\lambda} \sum _{i =1} ^m \log \left( \sum _{j\in [n]} \exp(\lambda a(\pmb{q} _i-\pmb{x} _j) )\right) 
\end{align}
 
Note that the function $sim(q,x)$ is a shift invariant function of the form $s(\pmb{q}-\pmb{x})$.

### Box Embeddings

The box embedding based volume score can be expressed as a shift invariant score $a(\pmb{q} - \pmb{x})$. Here, the query and corpus items are expressed as boxes denoted by $(\pmb{z} _q, \pmb{Z} _q )$ and $(\pmb{z} _x, \pmb{Z} _x )$ respectively (the lower and upper corner coordinate vectors). The hard intersection between $q$ and $x$ is then the box $(\pmb{z, Z})$ where $\pmb{z} _{q,x}=  \max ( \pmb{z} _q, \pmb{z} _x, )$ and  $\pmb{Z} _{q,x} =  \min ( \pmb{Z} _q, \pmb{Z} _x, )$. Then the score between q,x is measured as:
\begin{align}
\operatorname{sim}(q,x) = \prod _{k = 1} ^K [\pmb{Z} 
_{q,x}[k]- \pmb{z} _{q,x}[k]] _+  \hspace{3cm} ---(S)
\end{align}


We will show that there exists embedding $\pmb{q}$ and $\pmb{x}$ for which $sim (q,x) = a( \pmb{q} - \pmb{x})$. We first note that $\max(x,y) = x + (y-x) _+$ and $\min(x,y) =  y - (y-x) _+$. Using them, we have  $\pmb{z} _{q,x} =  \pmb{z} _{q} +( \pmb{z} _{x}-\pmb{z} _{q}) _+$ and $\pmb{Z} _{q,x} =  \pmb{Z} _{x} -( \pmb{Z} _{x}-\pmb{Z} _{q}) _+$. Thus, Eq. (S) is written as

\begin{align}
\operatorname{sim}(q,x) = \prod _{k = 1} ^K [  \pmb{Z} _{x} -\pmb{z} _{q} -( \pmb{z} _{x}-\pmb{z} _{q})
_+ -( \pmb{Z}
 _{x}-\pmb{Z}
 _{q}) _+ ]   _+ [k]
\end{align}

If we represent $\pmb{q} = [\pmb{z} _{q} , \pmb{z} _{q} ,\pmb{Z} _{q}  ]$ and $\pmb{x} = [\pmb{Z} _{x}, \pmb{z} _{x}, \pmb{Z}  _{x}   ]$, then we have
$\operatorname{sim}(q,x) = \prod _{k = 1} ^K [A  _1 ( \pmb{q}  -\pmb{x} ) -  [A _2 ( \pmb{q}  -\pmb{x} )  ] _+ -[A _3  ( \pmb{q}  -\pmb{x} )] _+] _+$ where $A _1 = -[\mathbb{I}, 0 ,0], A _2 = -[ 0, \mathbb{I} ,0]$ and $A _3= -[0,0,\mathbb{I}]$.

Thus $\operatorname{sim}(q,x)$ is shift invariant with respect to $\pmb{q}$ and $\pmb{x}$. Thus, we can extend our algorithm to box embedding setup.

# Citations

[Box and Order Embeddings]
T Chheda et al.  "Box Embeddings: An open-source library for representation learning using geometric structures". arXiv:2109.04997

[FLORA]
K Doan et al. "Asymmetric Hashing for Fast Ranking via Neural Network Measures". SIGIR 2023. arXiv:2211.00619

[NeuroMatch]
R Ying et al. "Neural Subgraph Matching" arXiv:2007.03092

[BERT-INT]
X Tang et al. “BERT-INT: A BERT-based Interaction Model For Knowledge Graph Alignment.”  IJCAI 2020.

[SNLI]
S Bowman et al. A large annotated corpus for learning natural language inference. EMNLP 2015.

[MNLI]
A Williams et al. A Broad-Coverage Challenge Corpus for Sentence Understanding through Inference. NAACL 2018.

Meta-review: The paper presents a neat idea of LSH in Fourier domain for set containment search, a very important problem in information retrieval when the query and data have asymmetrically different lengths or norms. Two reviewers were very excited about the papers and one raised concerns. The rebuttal was able to convince the concerned reviewer and in the end all reviewers unanimously agree that this paper is above the bar for acceptance.
Decision: Accept (spotlight)