In e-commerce, head queries account for the vast majority of gross merchandise sales and improvements to head queries are highly impactful to the business. While most supervised approaches to search perform better in head queries vs. tail queries, we propose a method that further improves head query performance dramatically. We propose XWalk, a random-walk based graph approach to candidate retrieval for product search that borrows from recommendation system techniques. XWalk is highly eficient to train and inference in a large-scale high trafic e-commerce setting, and shows substantial improvements in head query performance over state-of-the-art neural retreivers. Ensembling XWalk with a neural and/or lexical retriever combines the best of both worlds and the resulting retrieval system outperforms all other methods in both ofline relevance-based evaluation and in online A/B tests.
Modern large-scale search systems are tiered [
Most evaluations for search systems use an evaluation query set in which every query is
assumed to be equally important and has equal impact on the accuracy metric. However, in
reality, query frequency distributions are exponential [
Historically, graph-based approaches in search were used to create features (e.g. PageRank,
click graphs [
The recommendation systems have long used implicit interaction graphs to directly generate
recommendations. Commonly, users and product listings are represented as nodes in a graph
and edges represent a logged interaction between a user and product listing (e.g. the user
purchasing the listing). Random walks in graphs is a powerful technique used to generate
recommendations from interaction graphs [
XWalk uses a random walk based approach to perform candidate retrieval for product search. In XWalk, we cast search as a query-to-listing recommendation problem (as opposed to user-tolisting), that is, we transform our query log into a implicit interaction graph between queries and product listings, and perform candidate retrieval by “recommending” listings to queries. Our approach trains using a fraction of the time and resources used by neural dense retrievers and GNNs, and is highly eficient in inference – XWalk scales to real-time search over graphs of billions of nodes and tens of billions of edges. XWalk also excels in head queries, where implicit feedback signals are plentiful.
While XWalk on its own sufers in tail and novel queries, we show that when results from XWalk are ensembled with a typical retriever that uses text similarity, even one as basic as plain BM25, it substantially improves overall candidate retrieval accuracy compared to strong neural dense retrieval and hybrid retrieval baselines, especially over the head query region, which is responsible for the overwhelming majority of sales in e-commerce. Furthermore, we show that XWalk is complementary to both dense retrieval and BM25, and demonstrate the strength of ensembling all three approaches.
To summarize, our novel contributions are: a) showing that XWalk substantially improves performance in the head query region, which accounts for the overwhelming majority of sales in e-commerce; b) presenting an eficient random walk inference algorithm that can efectively serve queries at scale; c) showing that XWalk is complementary to other common retrieval methods and showing the strength of a simple ensemble approach that combines XWalk, BM25, and dense retrieval.
We take inspiration from the recommendation space and recast the search problem as a queryto-product listing recommendation problem using implicit feedback: predict the best product listings to “recommend” to a query , by learning from implicit user feedback, i.e. a query log. From the query log, we construct an undirected, weighted bipartite graph = (, , , ) where are nodes representing queries, are nodes representing product listings, are edges = {, = (, ) | ∈ ∧ ∈ }, and are edge weights.
ℎ that Given a query log which records for each query the set of listings , , the user clicked on, added to their shopping cart, and purchased, respectively, we construct our graph through the following process: 1. For each unique (by text string) query in the query log ˆ, add ˆ to . 2. For each unique (by listing ID) listing in the query log , add to . 3. Collate the query log by query-listing pairs (ˆ, ), counting the number of occurrences of , , , , and ℎ, interactions for each unique (ˆ, ) pair. 4. For each (ˆ, ), add , to and its weight , to , where , is calculated Equation 1.
Intuitively, edge weights represent the popularity or trustworthiness of the edge, i.e. if many diferent users bought listing from query , , will be higher because we are more confident in the relationship represented by the edge. To weight edges, we use a simple linear combination: , = 1 · | clicki,j | + C2 · | carti,j | + C3 · | purchasei,j | (1)
In practice, the best coeficients are 1 < 2 < 3, as the goal is to bias walks toward listings which convert well for a given query. 2.1.1. Graph representation for eficient inference XWalk is designed for sparse graphs scaling up to billions of nodes and tens of billions of edges. The costliest part of random walk graph inference is sampling edges to walk, especially from high degree nodes. For eficient inference, we choose our graph representation carefully.
We store edge weights as cumulative distribution functions in order to use Inverse Transform Sampling, which allows sampling in (( )) time. Note, we choose this approach over the alias method, which allows for constant time sampling, due to the doubling of memory needed for the transform. As XWalk’s space complexity is dominated by edges and corresponding weights, we develop other methods for eficient sampling (Section 2.2).
To transform edge weights in to CDF format, for each node , we sort its adjacent edges ,* in decreasing order of their weights ,* , such that , > ,+1. We then compute the cumulative distribution of all weights: , = ∑︀=0 , ∑︀|=0,* | , (2)
To sample an edge from ,* , we randomly sample ∼ (0, 1) and find the corresponding edge through binary search. This formulations provides us a few valuable advantages: 1. Weighted sampling is ((|,* |). Given some nodes have degrees in the millions, logarithmic growth is critical for performance. 2. Normalizing the CDF to 1 allows us to reconstruct the the transition probability for outbound edges. This is key for the Metropolis-Hastings sampling strategy (Section 2.2). 3. Better cache coherence as the bulk of the weights are located near the front of the distribution.
Finally, we convert the graph into Compressed Sparse Row format, guaranteeing a (1) lookup cost for edges.
Note that all of the above graph construction steps are simple ETL (extract, transform, load) operations with no expensive parameter training steps. Compared to neural dense retrievers, “training” an XWalk graph model takes only a fraction of the cost and time.
Inferencing a graph with random walks is challenging to do eficiently. Despite the (1) edge
lookup guarantee of the Compressed Sparse Row format used in graph construction, a naive
walk approach that uses depth first search and binary search node lookups create random
memory access patterns which result in high rates of costly cache misses [
At query time, XWalk retrieves relevant listings for a query by sampling nodes in using
-hop fixed paths [
To reduce costly random memory access patterns, we use a breadth first search instead of depth first search for our random walks. We also improve upon the Inverse Transform Sampling strategy by using the Metropolis-Hastings algorithm (a Markov chain Monte Carlo method) in most places. Given the sorted CDF format of edge weights (Eq. 2), we can reconstruct the original edge transition probabilities: ( |,* ) = , − ,− 1. As Metropolis-Hastings requires a symmetric distribution, we take the absolute value of the proposal index for each edge and sample from the Normal distribution. Ablation testing indicated XWalk is not sensitive to the variance for the proposal distribution, 2. We set 2 = 0.2.
Metropolis-Hastings improves the cost of edge samples to (log(|,* |)) + compared to * (log(|,* |)) of Inverse Transform Sampling. In cases where is large (e.g. the initial query node), the computational improvements are substantial. A known limitation of MCMC methods is the auto-correlation of samples, usually requiring a mix time prior to sampling. Therefore, for our first sample, we use Inverse Transform Sampling to get an unbiased starting point and use Metropolis-Hastings for subsequent samples. In preliminary testing we found no reduction in model accuracy for this implementation compared to using only Inverse Transform Sampling while seeing the expected substantial latency benefits.
Our overall random walk strategy is presented in Algorithm 1.
Our e-commerce platform is a two-sided marketplace and our inventory comes from independent sellers. Thus, listings are naturally grouped by shops. In addition, sellers may add tags to their listings to better describe them (e.g. “christmas”, “gift”, etc.).
Algorithm 1: XWalkBFSSampler 1 Global variables: Var of Normal distribution 2, Dictionary of nodes to counts 2 Input: Starting node , Number of walks , Walk-length , Edges , Weights ,
Multiplier (default 1) 3 ∼ (0, 1) 4 = ℎ(,* , ,* , )
/* the ’th node of ordered neighbors of 5 [(,)]+ = 6 for step = {2, .., c} do 7 = (, ,* , ,* , 2) /* the ’th node of ordered neighbors of [(, )]+ = 1 = = ( ∈ ) in non-increasing order {[1] ≥
[2] . . . ≥ [||]} return Nodes 19 20 end */ */
For the sake of notation simplicity, we described the graph construction and inference above assuming our graph only contains two types of nodes, and . However, in practice, we extend the graph by adding shop nodes () and tag nodes ( ) to the graph; this allows us to retrieve listings without implicit user feedback (e.g. the cold start problem) and further increase connectivity of the graph. Note that remains bipartite: {, , } is a separate partition from and thus the algorithms described in this section can be used unchanged. The weights of edges between shops/tags and listings are set to 1. , = , = 1.
For our experiments, we sought to closely emulate a real-world e-commerce setting, where the main source of training data is implicit user feedback from query logs, and models are evaluated under a realistic query popularity distribution. Unfortunately, most public search datasets do not reflect a realistic query distribution and rarely have implicit user feedback as training data. While recommendation system datasets have implicit user feedback, they do not have a text query that is usable by BM25 or dense retrieval, which retrieve based on query to listing text similarity. Therefore, we curated a training and evaluation dataset from our e-commerce platform.
For training data, we collected 365 days of implicit feedback data, comprising of records of queries and the product listings that were clicked, added to cart, or purchased from a given query. Queries are represented by their query text. Listings are represented by their unique ID and the title of the product. In addition, as mentioned in Section 2.3, listings are associated with seller-provided tags, and each listing belongs to exactly one seller’s shop.
Over the time period used for this experiment there were 137,824,871 unique listings, 147,174,817 unique queries, 62,803,463 unique tag, and 3,018,713 unique shops. There were a total of 1,349,734,328 query-listing interactions recorded, where 3.46% were purchases, 6.19% were cart adds and 90.3% were clicks. Altogether, there were 1,395,759,140 edges. Example records are found in Table 1.
query wedding dress wedding gown wedding dress
ID l12 l12 l34
listing title beautiful bridal wedding gown custom embroidered wedding dress ethereal dress with chifon skirt interaction
click purchase click shop s00 s00 s11
tags wedding wedding, gown dress, chifon
Evaluation data was curated to be a representative query distribution, sampled from a single day immediately following the last day of the training data window. We randomly sampled 11,521 queries that resulted in at least one purchase. As the sample is intended to be reflective of the true query popularity distribution, we did not de-duplicate the query set. Figure 1 shows the distribution of the query frequency in the evaluation set.
For each query, the listings that were purchased from that query are considered the relevant document. 82.3% of queries had only one purchase, 12.0% had two purchases and 5.6% had more than two purchases. For each one of these queries, we assigned them to a head/torso/tail frequency bin based on how frequently they occurred in the previous 365 day period. The bins were created such that the total counts of requests are roughly equal among those bins. Of the evaluation queries, 31.0% were in the head bin, 47.9% were in the torso bin, and 43.9% were in the tail bin.
We compare XWalk against two other methods of candidate retrieval. First is lexical retrieval using BM25 scoring (BM25). We use Pyserini [19] to build a Lucene index based on listing titles in our dataset and then retrieve candidates using BM25 rankings using bag-of-words representations. We used the default analyzer and default BM25 parameters (k1=1.2, b=0.75).
The second baseline is a state of the art neural dense retrieval system [20] trained on search trafic for candidate retrieval (NIR). NIR uses a smaller time window of training data (30 days) due to the time and expense of training on larger data sets. NIR is a Transformer-based, two tower model that uses a multi-part hinge loss to distinguish between interactions that involve a purchase, cart add, favorite, click, or nothing. The model was trained over one epoch. It was designed for better semantic matching between queries and listings by incorporating title, query as well as additional features such as tags, and listing taxonomy.
In addition to the above, we also compare results against hybrid systems of NIR+BM25 [
As shown in Table 2, when compared independently against other methods, XWalk out-performs other methods in most metrics despite the fact that it is unable to return results for novel queries, due to its strength in the head query bin. When combined with BM25, it outperforms in every metric, both NIR and the hybrid NIR+BM25. Finally, the ensemble of all three methods (XWalk+BM25+NIR) substantially outperforms all other configurations.
We see in Table 2 that BM25 is significantly weaker in performance compared to NIR and XWalk and does not always improve the overall results of NIR and XWalk, especially for MAP. While BM25 can improve recall by adding listings that were not retrieved by NIR and XWalk, its poor ranking drags down MAP in the hybrid systems. For the most popular short queries, BM25 is not able to distinguish between the many listings with titles that token match similarly to the query. Whereas methods like XWalk and NIR are able to provide a more reliable ranking of the highly purchaseable listings based on training data.
However, in Table 3 we see that XWalk is complementary to BM25; XWalk is stronger in the head and torso bins while BM25 outperforms XWalk in the tail bin. This is due to the fact that XWalk sufers from cold start problems: it performs best with many prior examples and is unable to handle novel queries. BM25, as a lexical matching system, is more able to handle novel queries. Furthermore, XWalk+BM25 is still yet complementary with NIR. The semantic matching of dense retrieval excels in the tail, where queries are typically longer. When all three systems are ensembled, it is the highest performing across all query bins. XWalk’s success in the head query bin is particularly notable – in an e-commerce setting, the head query bin is responsible for a large majority of merchandise sales.
BM25 NIR XWalk NIR+BM25 XWalk+BM25 XWalk+BM25+NIR
BM25 NIR XWalk NIR+BM25 XWalk+BM25 XWalk+BM25+NIR tail 0.471 0.738 0.260 0.804 0.595 0.836 torso 0.420 0.728 0.813 0.779 0.875 0.931
We tested XWalk in a live online A/B experiment on a large e-commerce platform. The experiment ran for 23 and 25 days on our mobile and web version of our platform, respectively. Our search system is a two-stage search system, which uses an ensemble of candidate retrievers in the ifrst pass, followed by a second pass re-ranker. In our A/B experiment, an ensemble of NIR+Solr as the candidate retrieval system was compared against an ensemble of XWalk+NIR+Solr.
We saw a statistically significant and substantial increase in conversion rate for the search system including XWalk in both the web and mobile platforms, +1.2% on web and +1.98% on mobile. In addition, in a production setting, we saw that XWalk was our lowest latency retrieval engine. The 99th percentile latency is only 58% of the NIR engine and 22% that of our Solr inverted index.
Head queries are responsible for the large majority of purchases in e-commerce. We presented XWalk, a novel candidate retrieval engine, which by frames search as a query-to-product recommendation problem, leverages powerful, highly eficient graph methods to substantially improve head query performance in product search. XWalk is also complementary to other common retrieval engines such as BM25 and dense retrieval, and ensembling produces a powerful retrieval engine. at Cache Eficiency, in: Proceedings of the ACM SIGOPS 28th Symposium on Operating Systems Principles CD-ROM, ACM, Virtual Event Germany, 2021, pp. 311–326. URL: https://dl.acm.org/doi/10.1145/3477132.3483575. doi:10.1145/3477132.3483575. [19] J. Lin, X. Ma, S.-C. Lin, J.-H. Yang, R. Pradeep, R. Nogueira, Pyserini: A Python toolkit for reproducible information retrieval research with sparse and dense representations, in: Proceedings of the 44th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR 2021), 2021, pp. 2356–2362. [20] P. Nigam, Y. Song, V. Mohan, V. Lakshman, W. Ding, A. Shingavi, C. H. Teo, H. Gu, B. Yin, Semantic product search, CoRR abs/1907.00937 (2019). URL: http://arxiv.org/abs/1907.00937. arXiv:1907.00937.