  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 efficient to train and inference in a
large-scale high traffic 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
offline relevance-based evaluation and in online A/B tests.
