# Relevance Proximity Graphs for Fast Relevance Retrieval

Stanislav Morozov
Yandex,
Lomonosov Moscow State University
<EMAIL_ADDRESS>&Artem Babenko
Yandex,
National Research University
Higher School of Economics
<EMAIL_ADDRESS>
###### Abstract

In plenty of machine learning applications, the most relevant items for a
particular query should be efficiently extracted, while the relevance function
is based on a highly-nonlinear model, e.g., DNNs or GBDTs. Due to the high
computational complexity of such models, exhaustive search is infeasible even
for medium-scale problems. To address this issue, we introduce Relevance
Proximity Graphs (RPG): an efficient non-exhaustive approach that provides a
high-quality approximate solution for maximal relevance retrieval. Namely, we
extend the recent similarity graphs framework to the setting, when there is no
similarity measure defined on item pairs, which is a common practical use-
case. By design, our approach directly maximizes off-the-shelf relevance
functions and does not require any proxy auxiliary models. Via extensive
experiments, we show that the developed method provides excellent retrieval
accuracy while requiring only a few model computations, outperforming indirect
models. We open-source our implementation as well as two large-scale datasets
to support further research on relevance retrieval.

##  1 Introduction

Retrieval of most relevant items for a particular query is a key ingredient of
a wide range of machine learning applications, e.g., recommender services,
retrieval-based chatbot systems, web search engines. In these applications,
item relevance for a particular query is usually predicted by pretrained
models, such as deep neural networks (DNNs) or gradient boosted decision trees
(GBDTs). Typically, relevance models get a query-item pair as input and output
the relevance of the item to the query. In the most general case, queries and
items are described by different sets of features and belong to different
spaces. For instance, in recommender systems, queries are typically described
by user gender, age, usage history, while the item features mostly contain
information describing the content. Let us denote the query space by $Q$ and
the item space by $V$. Then the problem of maximal relevance retrieval can
formally be stated as follows. Let us have a large finite set $S$ of items
$S\subset V$, query $q\in Q$ and the function $f(q,v)$ that maps query-item
pairs to relevance values:

$f:Q\times V\rightarrow\mathbb{R}$ (1)

For a given query $q\in Q$ we aim to find an item that maximizes the relevance
function $f(q,v)$:

$\operatorname*{arg\,max}\limits_{v\in S}f(q,v)$ (2)

or, more generally to find top-$K$ items from $S$ that provide maximal
relevance values. An important special case of problem (2) when
$Q=V=\mathbb{R}^{n}$ and

$f(q,v)=-\|q-v\|^{2}$ (3)

is a well-known problem of nearest neighbor search, which was investigated by
the machine learning community for decades (?; ?; ?).

However, current applications typically use more complex and highly-nonlinear
relevance functions $f(\cdot,\cdot)$. For instance, many modern recommender
services (?) use the deep neural networks for relevance prediction, while
chatbots (?) and many other applications use GBDT models. Naive exhaustive
search requires $|S|$ relevance function computations, which is not feasible
for million-scale databases and computationally expensive models. In this
paper, we propose a method that provides an approximate solution of high
quality while computing $f$ only for a small fraction of $S$.

The proposed method expands the approach of similarity graphs, which was shown
to provide exceptional performance for the nearest neighbor search problem (?;
?; ?). This approach organizes the set of items in a graph, where close items
are connected by edges, and the search process is performed via a greedy
exploration of this graph. In this paper, we extend similarity graphs to the
setting, when there is no similarity measure defined on item pairs.
Specifically, we describe each item by a vector of relevance values for a
representative subset of queries, and experimentally show that the graph
exploration can be successfully guided by the DNN/GBDT models. Below we refer
to our method as Relevance Proximity Graphs (RPG).

The contributions of the paper can be summarized as follows:

  1. 1.

We tackle a new problem of general relevance retrieval, which so far received
little attention from the community.

  2. 2.

We extend the similarity graphs framework to the setting without a similarity
measure defined in the item space.

  3. 3.

We open-source the implementation111https://github.com/stanis-morozov/rpg of
the proposed method as well as two million-scale datasets and state-of-the-art
pretrained models for further research on general relevance retrieval.

The rest of the paper is organized as follows: in Section 2, we briefly review
prior work related to the proposed approach. Section 3 formally describes the
construction and the usage of RPG. In Section 4, we perform an extensive
evaluation of RPG on several datasets and several models and empirically
confirm its practical usefulness. Section 5 concludes the paper.

##  2 Related work

Relevance retrieval problem. Probably, the closest work to ours is (?), which
also notes that large-scale relevance retrieval is computationally infeasible
for multi-layer DNN models. They tackle this problem by learning a
hierarchical model with a specific structure, which organizes the set of items
into a tree during the training stage. While this model allows non-exhaustive
retrieval, their approach cannot be directly applied to existing models and
requires training the model from scratch. Another work (?) proposes a cascade
scheme when cheap auxiliary models provide short-lists of promising candidates
and expensive relevance models are used only for candidate reranking. While
being efficient, such schemes can result in low recall if the capacity of
auxiliary models is insufficient to extract precise candidates lists. In
contrast, the proposed RPG approach directly maximizes relevance given by
arbitrary off-the-shelf models. We confirm this claim for several GBDT and DNN
models in the experimental section.

Nearest neighbor search. As mentioned above, problem (2) generalizes the well-
known problem of nearest neighbor search (NNS). Overall, machine learning
community includes three separate lines of research on NNS: locality-sensitive
hashing (LSH) (?; ?), partition trees (?; ?; ?) and similarity graphs (?).
While LSH-based and tree-based methods provide solid theoretical guarantees,
the performance of graph-based methods was shown to be much higher (?). The
proposed approach is based on the similarity graph framework, hence we provide
a brief review of its main ideas below.

For a set of items $S$, the directed similarity graph has a vertex
corresponding to each of the items. Vertices $v_{i}$ and $v_{j}$ are connected
by an edge if $v_{j}$ belongs to the set of $k$ nearest neighbors of $v_{i}$
in terms of similarity function $s$. The usage of similarity graphs for the
NNS problem was initially proposed in the seminal work (?). This approach
constructs the similarity graph and then performs the greedy walk on this
graph on the retrieval stage. The search process starts from a random vertex
and then on each step moves from the current vertex to a neighbor, that
appears to be the closest to the query. The process terminates when we reach a
local minimum, i.e., there are no adjacent vertices, closer to the query.
Since (?) the general pipeline described above, was modified by a large set of
additional heuristics (?; ?; ?), outperforming LSH-based and tree-based
methods.

The proposed approach for the relevance retrieval problem could be based on
any state-of-the-art similarity graph. In this paper, we employ Hierarchical
Navigable Small World (HNSW) (?) graphs implementation that is publicly
available. In HNSW, the search is performed in a semi-greedy fashion, via a
variant of beam search (?), as described in Algorithm 1 in detail. During the
construction stage, HNSW builds the graph via incrementally adding vertices
one-by-one. There is a parameter $M$, denoting for the maximum degree of
vertices in the graph. For each vertex $v$ we perform the search described in
Algorithm 1 and connect $v$ to the $M$ closest vertices that already exist in
the graph. HNSW builds a nested hierarchy of graphs, where the lowest layer
contains all vertices, and each higher layer contains only a subset of the
vertices of the lower layer. The search is performed from top to bottom and
the result from each upper layer is used as an entry point to the lower layer.

Beyond the NNS problem, similarity graphs were also shown to provide decent
performance for more general similarity functions, e.g., inner product,
Kullback-Leibler divergence, cosine distance, Itakura-Saito distance, and
others (?). In this paper, we show that this framework can be extended to work
with the setting where there is no specified similarity measure between the
item space elements and the relevance functions defined by state-of-the-art ML
models, such as DNNs or GBDTs.

##  3 Relevance Proximity Graphs (RPG)

The key idea of our approach is to represent the set of items as a graph and
to perform the search on this graph using the given relevance function. The
retrieval stage remains unchanged, that is, we perform semi-greedy graph
exploration, guided by the relevance function $f(\cdot,\cdot)$ (Algorithm 1).
As will be shown in the experiments, the state-of-the-art DNN and GBDT models
successfully guide the graph exploration process given that the item set is
organized in an appropriate graph.

However, the question ”How to construct an appropriate graph?” becomes
nontrivial as items and queries belong to different spaces. Moreover, in some
scenarios, there is no similarity defined in the item space, hence the
existing approaches to graph construction cannot be directly applied.

Algorithm 1 Graph Exploration

Input: Graph $G$, relevance function $f(q,v)$, query $q$, entry vertex
$v_{0}$, beam width $L$

Candidate set $C=\\{v_{0}\\}$

Set of visited vertices $V=\\{v_{0}\\}$

List of the most relevant vertices $W=\\{v_{0}\\}$

while $|C|>0$ do

extract to $v_{curr}$ the most relevant element from $C$

extract to $b$ the less relevant element from $W$

if $f(q,v_{curr})<f(q,b)$ then

break

for $v_{adj}$ adjacent to $v_{curr}$ in $G$ do

if $v_{adj}\not\in V$ then

$V=V\cup\\{v_{adj}\\}$

if $f(q,v_{adj})>f(q,b)$ or $|W|<L$ then

$C=C\cup\\{v_{adj}\\}$

$W=W\cup\\{v_{adj}\\}$

if $|W|>L$ then

erase the less relevant element from $W$

return $W$

### Relevance-aware similarity in the item space

For graph construction, we exploit the natural idea that two items $u$ and $v$
are similar if the corresponding functions $f(\cdot,u)$ and $f(\cdot,v)$ are
”close”, i.e. the items are both relevant or irrelevant for the same query. As
a straightforward way to define the similarity between functions, we use
$L_{2}$ distance over some measure $\mu$ defined on the query space (we put
minus sign as similarity search is traditionally formulated as a maximization
problem):

$s(u,v)=-\Big{(}\int\limits_{Q}(f(q,u)-f(q,v))^{2}d\mu(q)\Big{)}^{1/2}$ (4)

We choose the proper measure over the query space $\mu$ based on the following
intuition. Let us have a probability space $(Q,\mathcal{F},\mathbb{P})$
defined on the query space. For most applications, it is natural to force
functions $f(q,u)$ and $f(q,v)$ to be closer in the regions where the density
of the query distribution is high. Then, it corresponds to the following
similarity function:

$s(u,v)=-\Big{(}\int\limits_{Q}(f(q,u)-f(q,v))^{2}d\mathbb{P}(q)\Big{)}^{1/2}$
(5)

that is equivalent to the expectation over the probability space:

$s(u,v)=-\Big{(}\mathop{\mathbb{E}}_{q\sim Q}(f(q,u)-f(q,v))^{2}\Big{)}^{1/2}$
(6)

In practice, we use the Monte-Carlo estimate of this value. Let us have a
random sample $X$ of size $d$ from the query distribution. We enumerate this
random sample:

$X=\\{q^{(1)},q^{(2)},\dots,q^{(d)}\\}$ (7)

Then we define a vector $r_{u}$ corresponding to the item $u$ in the following
way:

$r_{u}^{i}=f(q^{(i)},u)$ (8)

We refer to the vector $r_{u}\in\mathbb{R}^{d}$ as a relevance vector as it
contains the relevance values for the item $u$ and queries in the sample $X$.
Note that we choose the sample $X$ only once and it remains the same for all
the items. Then the similarity between items $u$ and $v$ can be defined as:

$s(u,v)=-\|r_{u}-r_{v}\|$ (9)

Given this similarity measure, we can apply the existing graph construction
method from (?). Note, that for the fair evaluation, only hold-out training
queries were used to obtain the relevance vectors in all the experiments,
while the relevance retrieval accuracy was calculated for a separate set of
test queries.

### RPG construction

We summarize the graph construction scheme more formally. Let us have the item
set $S\subset V$ and the train query set $\\{q_{1},\dots,q_{N}\\}$. The main
parameter of our scheme is a dimensionality of relevance vectors, which is
denoted by $d$.

  1. 1.

Select $X$ — $d$ queries from $\\{q_{1},\dots,q_{N}\\}$, which will be used to
construct the relevance vectors.

  2. 2.

Compute the relevance vectors for items from $S$: $\\{r_{u}^{i}\\}_{u\in
S,q^{(i)}\in X}=\\{f(q^{(i)},u)\\}_{u\in S,q^{(i)}\in X}$

  3. 3.

Build a similarity graph on $S$, using $L_{2}$ distance metric on the
relevance vectors as a similarity measure, via HNSW method (?).

Given the graph, the maximal relevance retrieval is performed for a query $q$
via Algorithm 1, using the model $f(\cdot,\cdot)$ to guide the graph
traversal. As in (?), for all queries, we use the same entry vertex $v_{0}$ in
RPG, which corresponds to the item with id${=}0$.

##  4 Experiments

(a) SIFT1M

(b) DEEP1M

Figure 1: The comparison of RPG with HNSW for euclidean nearest neighbor
benchmarks. For both datasets we retrieve top-$5$ items.

In this section, we present the experimental evaluation of the proposed RPG
approach for the top-K relevance retrieval problem on three real-world
datasets. Our code is written in C++, and the implementation of similarity
graphs is based on the open-source HNSW
implementation222https://github.com/yurymalkov/hnsw. In our experiments, we
use two standard performance measures. Commonly used Recall measure is defined
as the rate of successfully found neighbors, averaged over a set of queries.
The second is Average relevance that is defined as the average of relevance
values for the query and retrieved top-K items, averaged over the set of
queries.

### Datasets

We report experimental results obtained on three datasets described below. To
the best of our knowledge, there are no publicly available large-scale
benchmarks for relevance retrieval with highly-nonlinear models without the
similarity measure between item space elements, therefore we collect and open-
source two datasets. We expect that these datasets will be valuable for the
community, given the abundance of relevance retrieval problem in applications.

Collections dataset. This dataset originates from a proprietary image
recommendation service. Here we also sampled one million most-viewed images
and $2,000$ random warm users. Each user-item pair is characterized by $138$
features, where $93$ of them are item features, $16$ are user features and
$29$ are pairwise user-item features. Then we trained the state-of-the-art
GBDT model (?) on these features, which we open-source along with the dataset.

Video dataset. This dataset originates from a proprietary video recommendation
service. We sampled one million most-viewed videos and $2,000$ random warm
users. Each user-item pair is characterized by $2,715$ features, where $562$
of them are item features, $2,080$ are user features and $73$ are pairwise
user-item features. We trained the GBDT model (?) on these features, which we
open-source as well.

Pinterest. We also evaluate our approach on the medium-scale Pinterest dataset
(?) with the deep neural network model for relevance prediction proposed in
(?). This datasest contains $9,916$ items and $55,187$ queries without any
feature representations, i.e. only a rating matrix is provided.

For all datasets we randomly selected $1,000$ users as train queries and
$1,000$ users as test queries. We use the train queries for the relevance
vector computation, and we average the evaluation measures over the test
queries.

### Sanity check

To demonstrate the reasonableness of the proposed scheme we evaluate RPG on
two common nearest neighbor benchmarks SIFT1M (?) and DEEP1M (?) with the
euclidean distance between queries and items, that is $Q=V=\mathbb{R}^{n}$ and

$f(q,v)=-\|q-v\|^{2}$ (10)

On Figure 1(a) and Figure 1(b) we provide the results of the comparison of RPG
with HNSW (?). For both methods we use $M=8$ and $100$-dimensional relevance
vectors for RPG. Indeed, the graphs constructed based on distances between
relevance vectors (9) are less accurate but still provide decent retrieval
performance. In particular, it is sufficient to perform only a few thousand
distance evaluations to achieve $0.9$ recall level.

We conjecture that the reason of the decent performance even with suboptimal
graphs is that on the graph exploration stage the search process is ”guided”
by the correct similarity measure, which is negative $L_{2}$ distance between
the original data vectors in this experiment. Furthermore, as we show in the
experiments below, the graphs constructed on relevance vectors perform
exceptionally well even when the relevance function $f(\cdot,\cdot)$ is based
on highly-nonlinear DNN or GBDT models.

Figure 2: The dependence on the number of relevance function computations on
database size to achieve $0.90$ Recall on the Collections dataset.

### Ablation and preliminary experiments

Now we investigate RPG performance with varying database sizes and different
parameter values.

RPG vertex degree. First, we investigate the dependence of RPG performance on
the vertex degree $M$. For the Collections dataset, the recall-vs-complexity
curves for the different $M$ values are shown in Figure 3. Here, the length of
the relevance vectors is equal to $d{=}1000$ for all $M$ values. Surprisingly,
Figure 3 demonstrates that the best results are obtained for a quite small
degree $M{=}8$, which is smaller than the typical vertex degrees in graphs for
metric nearest neighbor search (?). In all the experiments below we use
$M{=}8$ for all datasets.

Length of relevance vectors. Next, we investigate how the RPG accuracy depends
on the length of relevance vectors $d$. We used a random sample of $1,000$
queries for the computation of relevance vectors (RPG) and evaluated recall
for $d=10,100,1000$ for all three datasets. The results are shown in Figure 4
and illustrate Recall for different number of model computations. As expected,
higher $d$ results in the more accurate retrieval due to the Monte Carlo
estimates in (6) becoming more accurate. On the other hand, Figure 4
demonstrates diminishing returns from higher $d$ as the performance difference
between $d=100$ and $d=1,000$ is only marginal.

Figure 3: The RPG performance with the different vertex degree $M$ on the
Collections dataset.

Search scalability. Finally, to investigate the empirical scalability of RPG
we varied Collections database size $|S|$ in
$\\{10^{3},10^{4},10^{5},10^{6}\\}$ and determined the number of relevance
function computations, required to achieve $0.90$ Recall for the top size
$K{=}5$. The results, shown in Figure 2, imply the power dependence
$|S|^{\alpha}$. Note, however, that the exponent $\alpha$ of the power law is
less than $1$ (approximately $1/3$), hence the empirical scalability of RPG is
sublinear in database size.

(a) Collections

(b) Video

(c) Pinterest

Figure 4: The dependence on the length of relevance vectors for three datasets
in terms of Recall. For all datasets we retrieve top-$5$ items. Figure 5: The
comparison with baselines for three datasets in terms of Recall/number of
model computations trade-off. For all datasets we retrieve top-$5$ items.
Figure 6: The comparison with baselines for three datasets in terms of Average
relevance/number of model computations trade-off. For all datasets we retrieve
top-$5$ items. Figure 7: The comparison with baselines for three datasets in
terms of Recall/number of model computations trade-off. For all datasets we
retrieve top-$100$ items.

### Comparison with baselines

We compare the proposed RPG method with several baselines for general
relevance retrieval. In particular, we evaluate the following methods:

Top-scored

For every item, we compute its average relevance values for train queries and
select $N$ items with the maximal global query-independent relevance. Then we
rerank these $N$ items based on the actual relevance value, computed by the
query-item relevance model. We vary $N$ to achieve runtime/accuracy trade-off.
Intuitively, this selects the most ”popular” items.

Item-based graph

is the baseline that uses the similarity graph, constructed on the item
features only, instead of the relevance vectors. Let us denote by $h_{u}$ the
$L_{2}$-normalized vector of features of item $u$. Then the similarity between
two items can be defined as

$s(u,v)=-\|h_{u}-h_{v}\|$ (11)

Note, that compared to RPG, the item-based graph has two crucial deficiencies:

  1. 1.

The item-based graph construction does not use any information about the query
distribution or the relevance prediction model.

  2. 2.

The dataset could lack item-only features (e.g., Pinterest), hence in such
cases the item-based graph could not be constructed.

In practice, one could use a less accurate, computationally cheaper model
(e.g., linear) to produce a list of candidates that are then reranked by the
expensive GBDT/DNN model. To compare the proposed RPG framework with such two-
stage approaches we propose the following baseline:

Two-tower

We learn a ”two-tower” DNN that encodes query and item features into
50-dimensional embeddings. The DNN has separate query and item branches,
consisting of three fully-connected layers, each having $128$ neurons for
Collections and $512$ neurons for Video with ELU non-linearity and Batch
Normalization. The relevance for a query-item pair is predicted as a dot
product of the corresponding embeddings. We train this model with the same
target as the original GBDT model, with the Adam optimizer (?) and OneCycle
(?) learning rate schedule. During the retrieval stage, we select $N$ items
that provide maximum dot-product (?) with a given query and rerank them based
on the actual relevance value. We vary $N$ for runtime/accuracy trade-off. An
important weakness of the Two-tower baseline is that it ignores the query-item
pairwise features, when producing candidates, and we show that this weakness
can be crucial.

Note, however, that the usage of cheaper models for candidate selection could
be nicely combined with the RPG search, as described in the following RPG+
modification of our approach.

RPG+

The pure RPG uses the same predefined entry vertex to start the graph
exploration. However, if there is given a promising candidate from an
auxiliary model, then we can use it as an entry point instead. In RPG+ we
start from the best candidate achieved with the DNN from the Two-tower model.
Note, that we do not need any relevance function computations to obtain the
candidate. Intuitively, starting from the sufficiently relevant entry vertex,
the graph exploration in RPG+ requires much smaller hops to reach the
”relevant region” of the database.

Table 1: The importance of different feature groups, computed by the GBDT model. Dataset | Item features | User features | Pairwise features
---|---|---|---
Collections | 0.1466 | 0.0260 | 0.0642
Video | 0.0099 | 0.0027 | 0.4114

(a) Video

(b) Pinterest

Figure 8: The comparison of RPG performance with baselines under restriction
of $5,000$ relevance function computations for Video and $500$ relevance
function computations for Pinterest dataset.

Figure 5 and Figure 6 present the dependence of Recall and Average relevance
on the number of relevance function computations, respectively. Figure 6
reports also the ideal values of Average relevance, obtained via exhaustive
search. For all datasets, these plots show that the proposed RPG method
outperforms all baselines by a large margin in the high-recall regions.
Furthermore, RPG+ can boost the performance in the low-recall operating point,
given a cheap candidate selection model. Note that RPG reaches almost ideal
average relevance in a few numbers of model computations. In these
experiments, we report the performance when $K{=}5$ items are retrieved, but
we claim that RPG consistently outperforms the baselines for larger $K$ as
well. Figure 7 presents the dependence of Recall on the number of relevance
function computations for $K{=}100$ and confirms the superiority of the
proposed techniue over baselines.

Interestingly, the baselines perform differently on different datasets. In
particular, the Two-tower baseline is quite competitive on Collections, while
giving poor results on Video. To explain this observation, we compare the
feature importance, computed by the GBDT
model333https://catboost.ai/docs/concepts/fstr.html. In a nutshell, for every
feature, the importance value shows how the loss function, computed on the
train set, changes if this feature is removed. Then we sum the importances
across all item, user, and pairwise features and report them in Table 1. Note,
that for the Collections dataset item features are more important, while for
the Video dataset the pairwise features contain most signal. Consequently, the
Top scored and Two-tower baselines show decent performance on Collections, as
they could capture the signal from the user and item features and provide
precise candidate lists for reranking. Meanwhile, they are not competitive on
Video, because they lose the information from the pairwise features, which are
the most important on this dataset. The RPG/RPG+ provides top performance for
both datasets.

### Reducing to matrix factorization problem

The problem of maximal relevance retrieval can potentially be solved by the
matrix factorization methods (?). Let us have a fixed set of queries $P$. Then
one can construct embedding vectors $v_{i}$ for all items and embedding
vectors $u_{j}$ for all the queries that are obtained via a low-rank
decomposition of the full relevance matrix $F=V^{T}U$, where
$F_{ij}=f(s_{i},p_{j})$, $F\in\mathbb{R}^{|S|\times|P|}$,
$V\in\mathbb{R}^{r\times|S|}$, $U\in\mathbb{R}^{r\times|P|}$ and $r$ denotes
the decomposition rank. Then for a given query we can retrieve $K$ best items
in terms of dot product $\langle u,v\rangle$ and then rerank these top-$K$
items exhaustively based on the values of the original relevance function
$f(q,v)$. We evaluate the described baseline, performing approximate matrix
factorization via Alternating Least Squares implementation from the Implicit
library444https://github.com/benfred/implicit. The comparison of ALS with the
graph-based methods for two datasets is presented on the Figure 8. On this
figure ALS-$N$ means that we randomly selected $N$ items for each query from
$P$, computed the corresponding relevance values and performed ALS for the
obtained sparse relevance matrix. Note, that the described approach is able to
retrieve the relevant items only for queries from $P$ and does not directly
generalizes to unseen queries. As operating points, we use $r=50$ and
$K=5,000$ for Video and $r=20$ and $K=500$ for Pinterest. Figure 8
demonstrates that ALS cannot reach the quality of the graph-based methods.

As an upper bound for baselines, which construct dot-product based embeddings
for items and users we implemented SVD for matrix $F$. Note, that this is an
extremely infeasible baseline as it requires an explicit computation of the
full matrix $F$ and this is the same computationally hard as to precompute
answers for all the users by exhaustive search. Despite this, SVD still cannot
reach the graph methods accuracy. In particular, for the Video dataset and
$r=50$, SVD achieves recall $0.693$ and for the Pinterest dataset and $r=20$
it achieves recall $0.988$.

##  5 Conclusion

In this paper, we have proposed and evaluated the Relevance Proximity Graph
(RPG) framework for non-exhaustive maximal relevance retrieval with highly-
nonlinear models. Our approach generalizes similarity graphs to the scenario,
where the relevance function is given for query-item pairs, and there may be
no similarity measure for items. Our framework can be applied to a
comprehensive class of relevance models, including deep neural networks and
gradient boosted decision trees. While being conceptually simple, RPG
successfully solves the relevance retrieval problem for million-scale
databases and state-of-the-art models, as demonstrated by extensive
experiments. As an additional contribution, we open-source the implementation
of our method as well as two large-scale relevance retrieval datasets to
support further research in this area.

## References

  * [Andoni and Indyk 2008] Andoni, A., and Indyk, P.  2008\.  Near-optimal hashing algorithms for near neighbor problem in high dimension.  Communications of the ACM 51(1):117–122.
  * [Babenko and Lempitsky 2016] Babenko, A., and Lempitsky, V.  2016\.  Efficient indexing of billion-scale datasets of deep descriptors.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2055–2063.
  * [Bentley 1975] Bentley, J. L.  1975\.  Multidimensional binary search trees used for associative searching.  Communications of the ACM 18(9):509–517.
  * [Boytsov 2017] Boytsov, L.  2017\.  Efficient and Accurate Non-Metric k-NN Search with Applications to Text Matching.  Ph.D. Dissertation, Carnegie Mellon University.
  * [Dasgupta and Freund 2008] Dasgupta, S., and Freund, Y.  2008\.  Random projection trees and low dimensional manifolds.  In Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing, STOC ’08.
  * [Dasgupta and Sinha 2013] Dasgupta, S., and Sinha, K.  2013\.  Randomized partition trees for exact nearest neighbor search.  In Conference on Learning Theory, 317–337.
  * [Fu and Cai 2016] Fu, C., and Cai, D.  2016\.  Efanna: An extremely fast approximate nearest neighbor search algorithm based on knn graph.  arXiv preprint arXiv:1609.07228.
  * [Fu et al. 2017] Fu, C.; Xiang, C.; Wang, C.; and Cai, D.  2017\.  Fast approximate nearest neighbor search with the navigating spreading-out graph.  arXiv preprint arXiv:1707.00143.
  * [Geng et al. 2015] Geng, X.; Zhang, H.; Bian, J.; and Chua, T.-S.  2015\.  Learning image and user features for recommendation in social networks.  In Proceedings of the IEEE International Conference on Computer Vision, 4274–4282.
  * [He et al. 2017] He, X.; Liao, L.; Zhang, H.; Nie, L.; Hu, X.; and Chua, T.-S.  2017\.  Neural collaborative filtering.  In Proceedings of the 26th International Conference on World Wide Web, 173–182.  International World Wide Web Conferences Steering Committee.
  * [Indyk and Motwani 1998] Indyk, P., and Motwani, R.  1998\.  Approximate nearest neighbors: Towards removing the curse of dimensionality.  In Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, Dallas, Texas, USA, May 23-26, 1998, 604–613.
  * [Kingma and Ba 2014] Kingma, D. P., and Ba, J.  2014\.  Adam: A method for stochastic optimization.  arXiv preprint arXiv:1412.6980.
  * [Lowe 2004] Lowe, D. G.  2004\.  Distinctive image features from scale-invariant keypoints.  International journal of computer vision 60(2):91–110.
  * [Malkov and Yashunin 2016] Malkov, Y. A., and Yashunin, D.  2016\.  Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs.  arXiv preprint arXiv:1603.09320.
  * [Mehta and Rana 2017] Mehta, R., and Rana, K.  2017\.  A review on matrix factorization techniques in recommender systems.  In 2017 2nd International Conference on Communication Systems, Computing and IT Applications (CSCITA).
  * [Navarro 2002] Navarro, G.  2002\.  Searching in metric spaces by spatial approximation.  The VLDB Journal 11(1):28–46.
  * [Prokhorenkova et al. 2018] Prokhorenkova, L. O.; Gusev, G.; Vorobev, A.; Dorogush, A. V.; and Gulin, A.  2018\.  Catboost: unbiased boosting with categorical features.  In Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS 2018, 3-8 December 2018, Montréal, Canada., 6639–6649.
  * [Shapiro 1987] Shapiro, S. C.  1987\.  Encyclopedia of Artificial Intelligence.
  * [Smith and Topin 2017] Smith, L. N., and Topin, N.  2017\.  Super-convergence: Very fast training of neural networks using large learning rates.  arXiv preprint arXiv:1708.07120.
  * [Wang, Lin, and Metzler 2011] Wang, L.; Lin, J.; and Metzler, D.  2011\.  A cascade ranking model for efficient ranked retrieval.  In Proceedings of the 34th international ACM SIGIR conference on Research and development in Information Retrieval, 105–114.
  * [Yu et al. 2018] Yu, J.; Qiu, M.; Jiang, J.; Huang, J.; Song, S.; Chu, W.; and Chen, H.  2018\.  Modelling domain relationships for transfer learning on retrieval-based question answering systems in e-commerce.  In Proceedings of the Eleventh ACM International Conference on Web Search and Data Mining, WSDM 2018, Marina Del Rey, CA, USA, February 5-9, 2018, 682–690.
  * [Zhu et al. 2018] Zhu, H.; Li, X.; Zhang, P.; Li, G.; He, J.; Li, H.; and Gai, K.  2018\.  Learning tree-based deep model for recommender systems.  In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, 1079–1088.  ACM.


Magnus C. Schaaf

# AutoEFT: Constructing and exploring on-shell bases of effective field
theories

###### Abstract

Effective Field Theories provide a framework for capturing the effects of yet
unseen heavy degrees of freedom in a model-independent manner. However,
constructing a complete and minimal set of operators, especially at higher
mass dimensions, is challenging. We present AutoEFT, an implementation of an
algorithm that systematically handles redundancies among operators due to
equations of motion, integration-by-parts identities, Fierz identities, and
repeated fields. This algorithm enables the construction of on-shell bases for
a broad range of EFT. Additionally, it facilitates the exploration of various
aspects within this field, such as investigating higher mass dimensions or the
relationship between different operator bases. AutoEFT can be applied to
phenomenologically relevant theories like the Standard Model and its
extensions, including new light particles or additional symmetry groups.

##  1 Introduction

Since current and potential future colliders have a limited energy reach, the
on-shell discovery of new heavy particles beyond the Standard Model (SM) may
be challenging. In recent years, there has been a growing interest in
searching for new physics in virtual effects. To correctly associate any
deviation to new physics, these effects need to be parameterized
systematically. For this approach, EFT have become invaluable.

In this article, we feature AutoEFT [1], an independent open-source
implementation of a systematic algorithm [2, 3] developed for the on-shell
operator basis construction of EFT. AutoEFT is published under the MIT license
[4] and is implemented in Python [5], combined with the open-source
mathematics software system SageMath [6]. It is available for download on the
_Python Package Index_ [7] and the _conda-forge_ [8] community channel. For
installation details and the usage of AutoEFT, we refer the reader to Ref.
[1].

##  2 Effective field theories

In the _bottom-up_ formulation of an EFT, the renormalizable Lagrangian
$\mathcal{L}^{(\leq 4)}$, describing a low-energy theory, is extended by
effective interactions mediated by some unknown high-energy physics. These
interactions are encoded in so-called _operators_ $\mathcal{O}_{i}^{(d)}$,
composed out of the field content of $\mathcal{L}^{(\leq 4)}$, and $d$
denoting the combined mass dimension of the participating fields. For
consistency with the low-energy theory, the operators must be invariant under
the symmetries imposed on $\mathcal{L}^{(\leq 4)}$. Depending on the scenario,
one may even impose additional symmetries on the operators, for example, some
of the accidental or approximate symmetries of $\mathcal{L}^{(\leq 4)}$.

Since any operator with a mass dimension equal to or less than four is already
part of $\mathcal{L}^{(\leq 4)}$, the effective operators are necessarily to
higher mass dimension. To cancel the surplus mass dimension of the operators
$\mathcal{O}_{i}^{(d)}$ in the Lagrangian, they must be multiplied by an
additional mass scale $\Lambda^{4-d}$, where $\Lambda$ is related to heavy new
physics. The effects of these operators contribute with a factor
${(E/\Lambda)}^{d-4}$ to the physical amplitudes, where $E$ denotes the
typical energy of the low-energy process. Assuming the mass scales obey the
hierarchy $E\ll\Lambda$, the effects up to order ${(E/\Lambda)}^{\mathcal{N}}$
can be incorporated by

$\mathcal{L}_{\text{EFT}}=\mathcal{L}^{(\leq
4)}+\sum_{d=5}^{\mathcal{N}+4}\frac{1}{\Lambda^{d-4}}\sum_{i}C_{i}^{(d)}\mathcal{O}_{i}^{(d)}\,,$
(1)

where the so-called _Wilson coefficients_ $C_{i}^{(d)}$ parameterize the
effective couplings. They can be fitted to experimental measurements or
matched to high-energy theories.

##  3 Operator bases and redundancies

Determining an independent set of operators at a given mass dimension is not
unique. There are nontrivial relations between different operators, rendering
a subset of them redundant. The redundant operators are, however,
indistinguishable in physical processes. In practical applications, this leads
to an over-determined set of Wilson coefficients so that no unique solution
can be identified. Consequently, it is necessary to avoid or eliminate these
superficial operators and construct an independent _operator basis_
$\set{\mathcal{O}_{i}^{(d)}}$ for each mass dimension $d$.

Some _redundancies_ arise from the presence of (covariant) derivatives acting
on the fields inside the operators. Others are purely algebraic, related to
the tensor structure of an operator. Finally, we consider redundancies induced
by the symmetry structure of the tensors linked to the occurrence of multiple
fields transforming in equal representations under all symmetry groups inside
an operator. In the following, we display the crucial redundancies to consider
in the operator basis construction.

Equations of Motion

Operators proportional to the EoM of some field $\Phi$ can be eliminated from
the Lagrangian by an appropriate field redefinition in the path integral of
the generating functional. Consequently, operators $\mathcal{O}$ and
$\mathcal{O}^{\prime}$, related by

$\mathcal{O}\sim\mathcal{O}^{\prime}+\frac{\delta
S}{\delta\Phi}\mathcal{O}^{\prime\prime}\,,$ (2)

where $S$ denotes the action, result in the same physical $S$-matrix elements.
It is, therefore, sufficient to only consider one of $\mathcal{O}$ and
$\mathcal{O}^{\prime}$ in the on-shell basis.

Integration by Parts (IbP)

Operators proportional to total derivatives do not contribute to the
perturbative action and can thus be eliminated from the Lagrangian. Hence,
operators $\mathcal{O}$ and $\mathcal{O}^{\prime}$, related by

$\mathcal{O}\sim\mathcal{O}^{\prime}+\partial\mathcal{O}^{\prime\prime}\,,$
(3)

yield the same perturbative $S$-matrix elements, and only one of the operators
should be considered as part of the EFT basis.

Fierz identities

Fierz identities relate products of spinor bilinears to linear combinations of
products of different spinor bilinears. It is, hence, possible to identify
operators with apriori different spinor structures with each other. Consider,
for example, the identity

$g_{\mu\nu}\sigma^{\mu}_{\alpha\dot{\alpha}}\sigma^{\nu}_{\beta\dot{\beta}}=2\epsilon_{\alpha\beta}\epsilon_{\dot{\alpha}\dot{\beta}}\,,$
(4)

where $\alpha,\beta$ and $\dot{\alpha},\dot{\beta}$ denote spinor indices and
$\mu,\nu$ denote Lorentz four-vector indices. Eq. 4 relates the direct
contraction of the spinor indices on the RHS to the contractions containing
$\sigma$-matrices in between on the LHS.

Algebraic identities

Algebraic identities relate the $\operatorname{SU}(N)$ tensor structures of
different operators. It is, therefore, possible to identify operators with
different contractions of the internal symmetry indices. Consider, for
example, the identity

$\epsilon^{ij}\epsilon^{kl}+\epsilon^{ik}\epsilon^{lj}+\epsilon^{il}\epsilon^{jk}=0\,,$
(5)

where $i,j,k,l$ denote fundamental indices of $\operatorname{SU}(2)$. Since
the same relation also holds for spinor indices instead, also called Schouten
identity, it gives rise to additional Fierz identities as well.

Repeated Field Redundancies

Operators that contain the same field more than once can suffer from RFR. On
the one hand, operators $\mathcal{O}$ and $\mathcal{O}^{\prime}$ that only
differ by a permutation $\pi_{\Phi}$ of the fields $\Phi$ inside the operator,
i.e.,

$\mathcal{O}\sim\pi_{\Phi}\circ\mathcal{O}^{\prime}\,,$ (6)

lead to the same physical processes. This statement also remains valid if the
field $\Phi$ appears in multiple generations, as the permutation of the
generation indices can be absorbed into the Wilson coefficient tensor. On the
other hand, the explicit contraction of the fields can induce a symmetry on
the generation indices, rendering some components of the Wilson coefficient
tensors dependent.

##  4 AutoEFT – An introduction

Provided the field content and symmetries of a low-energy theory, AutoEFT can
be used to construct on-shell operator bases for, in principle, arbitrary mass
dimensions automatically. The resulting operator bases are free of
redundancies by construction. In the following, we briefly showcase the
algorithm, the model files, and the output. An exhaustive description of
AutoEFT can be found in Ref. [1].

The algorithm

A systematic algorithm, taking care of all the redundancies while
simultaneously constructing explicit operator contractions, was proposed in
Refs. [2, 3]. It is based on on-shell methods and various techniques from the
representation theory of Lie groups and the symmetric group. Contrary to
existing efforts on the operator basis construction, the procedure does not
generate a superset of operators, which is subsequently reduced by eliminating
dependent operators using the redundancy relations introduced in Section 3.
Instead, the redundancies are avoided during the construction, so no
superficial operator needs to be considered. Notable exceptions to this are
the RFR, which still need to be eliminated after obtaining a super basis of
operators. Due to the generality of the algorithm, it can be applied to
various low-energy scenarios. A schematic overview of the algorithm and its
implementation in AutoEFT is displayed in Fig. 1.

The model file

The model file encodes all information about the symmetries and field content
of the low-energy theory and serves as input to AutoEFT. The model can contain
arbitrary products of local and global $\operatorname{SU}(N)$ and
$\operatorname{U}(1)$ symmetry groups. The fields of the low-energy theory
must be provided in irreducible representations under all symmetries. It is,
therefore, required to decompose any fields not transforming in irreducible
representations beforehand. For example, instead of providing a single
bispinor, the user must define its irreducible components as two Weyl spinors.
The reasonably simple input format enables the user to compose custom model
files and to construct the respective operator bases with minimal effort. A
variety of examples can be found in Ref. [1].

The output

Due to the nature of the algorithm, the operators generated by AutoEFT contain
fields with spinor indices only. For similar reasons, the fields carry only
fundamental indices of the non-abelian $SU(N)$ groups. Nevertheless, the
operators can be translated to a more familiar notation by performing the
substitutions provided in the appendix of Ref. [1]. The resulting bases are
provided in an electronic, human- and computer-readable output format. In
addition, it is possible to load operator bases with AutoEFT, for example, to
convert the operators to LaTeX expressions, or for further manipulation of the
explicitly contracted operators.

families$d$$T_{\text{Lorentz}}$typesmodel$T_{\text{internal}}$invariants$\set{\mathcal{O}_{i}^{(d)}}$LorentzinvarianceinternalsymmetryrestrictavoidEoM
& IbPavoidalgebraiceliminateRFR Figure 1:  Schematic depiction of the
algorithm implemented in AutoEFT. Green nodes denote the input required by
AutoEFT. In this case, $d$ is the mass dimension. Blue nodes label
intermediate objects also available in AutoEFT’s output. See Ref. [1] for a
detailed description of their meaning. The orange nodes denote the final bases
of operators generated by AutoEFT. The first one, labeled “invariants”, is the
super basis obtained by assuming that every field in the operator is distinct.
The second one is the (minimal) physical basis $\set{\mathcal{O}_{i}^{(d)}}$
without any RFR. Solid arrows indicate that no elimination of superficial
structures is required, as only independent sets of structures are generated.
The dashed arrow denotes a reduction of the basis by eliminating superficial
operators.

##  5 The standard model as effective field theory

One of the most prominent EFT in high-energy physics is the so-called Standard
Model Effective Field Theory (SMEFT). It can be used to parameterize the
effects of heavy new physics at current energies in a model-independent
manner. It is obtained by identifying $\mathcal{L}^{(\leq
4)}=\mathcal{L}_{\text{SM}}$ in Eq. 1, where $\mathcal{L}_{\text{SM}}$ denotes
the SM Lagrangian. The operators are thus composed of all SM fields and must
be invariant under the SM symmetries
$\operatorname{\operatorname{SO}^{+}}(1,3)\times\operatorname{SU}(3)\times\operatorname{SU}(2)\times\operatorname{U}(1)$.
The repeated attempts needed to arrive at minimal SMEFT bases, even at lower
mass dimensions, demonstrate the complexity of constructing a complete and
non-redundant set of operators. For example, the first version of Ref. [9]
provided the operators of type $LQ^{3}$ divided into two terms. Under the
exchange of the first two quark fields, the two terms are symmetric and
antisymmetric, respectively. However, both of them contain the same mixed
symmetry contribution so that the two terms are not independent [10, 11].

In the following, we use AutoEFT to qualitatively examine this dependence.
Generating the operators for the mass dimension-six SMEFT operator type
$LQ^{3}$ with AutoEFT, one finds three terms with definite permutation
symmetry of the quark fields:
$\mathcal{O}_{[3]},\mathcal{O}_{[2,1]},\mathcal{O}_{[1,1,1]}$. Expressing the
two terms $Q_{qqq}^{(1)}$ and $Q_{qqq}^{(3)}$ of Ref. [9] in terms of the
AutoEFT basis yields

$Q_{qqq}^{(1)}=-\frac{1}{3}\mathcal{O}_{[3]}+\frac{1}{3}\mathcal{O}_{[2,1]}\qquad\text{and}\qquad
Q_{qqq}^{(3)}=-\frac{1}{3}\mathcal{O}_{[2,1]}-\mathcal{O}_{[1,1,1]}-\frac{2}{3}\mathcal{O}_{[2,1]}^{(23)}\,,$
(7)

where $\mathcal{O}_{[2,1]}^{(23)}$ is obtained from $\mathcal{O}_{[2,1]}$ by
interchanging the second and third quark fields. At this point, the dependence
is already evident since both terms contain the mixed symmetry contribution
from $\mathcal{O}_{[2,1]}$. In addition, one finds that neither
$Q_{qqq}^{(1)}$ nor $Q_{qqq}^{(3)}$ contain all of
$\mathcal{O}_{[3]},\mathcal{O}_{[2,1]},\mathcal{O}_{[1,1,1]}$ and thus do not
span the entire space. However, by changing basis to

$Q_{qqq}=-\frac{1}{2}(Q_{qqq}^{(1)}+Q_{qqq}^{(3)})\qquad\text{and}\qquad\tilde{Q}_{qqq}=-\frac{1}{2}(Q_{qqq}^{(1)}-Q_{qqq}^{(3)})\,,$
(8)

one finds that $Q_{qqq}$ contains each term exactly once. In addition, one can
identify $Q_{qqq}^{(12)}=\tilde{Q}_{qqq}$, rendering $\tilde{Q}_{qqq}$
redundant. It is thus sufficient to consider only the term $Q_{qqq}$ in the
operator basis, as was done in later versions of Ref. [9].

##  6 EFT bases

We have used AutoEFT to derive for the first time the on-shell SMEFT operator
bases for mass dimensions 10, 11, and 12 [12]. In addition, by exploiting the
generality of the algorithm, we constructed operators including gravitational
interactions up to mass dimension 12. We provide the bases generated by
AutoEFT in a public repository [13]. It can be used to examine different
operator bases, either by hand or by loading them into AutoEFT. Currently, we
provide the operator bases for SMEFT, its extension by gravitational
interactions, and its restriction to minimal flavor-violating scenarios. We
intend to extend the set of bases to other models in the future. In addition,
users of AutoEFT have the opportunity to submit operator bases to the
repository.

##  7 Summary

EFT have become an indispensable tool in the search for heavy new physics. We
have introduced the application AutoEFT, developed for the construction of on-
shell operator bases with minimal effort and for various low-energy scenarios.
Besides the operator construction, AutoEFT can be used to examine the
relations between different operator bases. It provides a foundation for
future EFT frameworks, and we intend to extend its capabilities in various
respects.

## Acknowledgments

I would like to thank Robert Harlander, Tim Kempkens, Jakob Linder, and
Maximilian Rzehak for their inspiring collaboration. This research was
supported by the Deutsche Forschungsgemeinschaft (DFG, German Research
Foundation) under grant 400140256 –- GRK 2497: The physics of the heaviest
particles at the LHC, and grant 396021762 -– TRR 257: P3H -– Particle Physics
Phenomenology after the Higgs Discovery.

## References

  * [1] R.V. Harlander and M.C. Schaaf, _AutoEFT: Automated operator construction for effective field theories_ , 2309.15783.
  * [2] H.-L. Li, Z. Ren, J. Shu, M.-L. Xiao, J.-H. Yu and Y.-H. Zheng, _Complete set of dimension-eight operators in the standard model effective field theory_ , _Phys. Rev. D_ 104 (2021) 015026 [2005.00008].
  * [3] H.-L. Li, Z. Ren, M.-L. Xiao, J.-H. Yu and Y.-H. Zheng, _Complete set of dimension-nine operators in the standard model effective field theory_ , _Phys. Rev. D_ 104 (2021) 015025 [2007.07899].
  * [4] _MIT license_ , 2018, https://spdx.org/licenses/MIT.html.
  * [5] Python Software Foundation, _Python language reference (Version 3.11)_ , 2022, http://www.python.org.
  * [6] The Sage Developers, _SageMath, the Sage Mathematics Software System (Version 10.1)_ , 2023, https://www.sagemath.org.
  * [7] Python Software Foundation, _Python Package Index - PyPI_ , 2023, https://pypi.org/.
  * [8] conda-forge community, _The conda-forge project: Community-based software distribution built on the conda package format and ecosystem_ , July, 2015, 10.5281/zenodo.4774216.
  * [9] B. Grzadkowski, M. Iskrzyński, M. Misiak and J. Rosiek, _Dimension-six terms in the standard model lagrangian_ , _JHEP_ 10 (2010) 085 [1008.4884].
  * [10] L.F. Abbott and M.B. Wise, _Effective hamiltonian for nucleon decay_ , _Phys. Rev. D_ 22 (1980) 2208.
  * [11] R. Alonso, H.-M. Chang, E.E. Jenkins, A.V. Manohar and B. Shotwell, _Renormalization group evolution of dimension-six baryon number violating operators_ , _Phys. Lett. B_ 734 (2014) 302 [1405.0486].
  * [12] R.V. Harlander, T. Kempkens and M.C. Schaaf, _Standard model effective field theory up to mass dimension 12_ , _Phys. Rev. D_ 108 (2023) 055020 [2305.06832].
  * [13] _EFT bases repository_ , 2023, https://gitlab.com/auto_eft/eft-bases.

  *[EFT]: Effective Field Theory
  *[SM]: Standard Model
  *[EoM]: Equation of Motion
  *[IbP]: Integration by Parts
  *[RFR]: Repeated Field Redundancy
  *[SMEFT]: Standard Model Effective Field Theory