\section{Introduction}

E-commerce search, which serves as an essential part of online shopping platforms, typically consists of three steps: query processing, candidate retrieval and ranking. In this paper, we focus solely on the candidate retrieval step which aims to retrieve thousands of candidates from billions of items.

Despite the recent advance of embedding based retrieval methods~\cite{zhang2020towards} and their successful applications in candidate retrieval stage, in practice we still notice a few drawbacks: 1) representations of low-frequency items are not well learned due to their rare occurrences; 2) Query embeddings are computed purely from a handful of query tokens, which sometimes can not capture the query semantic meanings well; 3) The training efficiency is low, mainly because that each training example consists of only one pair of query and clicked item.

In this paper, we explore Graph Convolution Networks (GCN) to enrich entity representations by aggregating related neighbor's information. In our case of e-commerce search, it is very likely that we can learn a better embedding representation for a user query, if we can aggregate information from the most clicked or bought items for the query to alleviate the shortage of query tokens. Likewise, we can learn a better item embedding representation, if we can aggregate information from the most frequent queries that lead to the item clicks or orders. Figure~\ref{fig:ecomm_graph} shows a quick glance of typical e-commerce graph  which illustrates how a query aggregates information from related items. Moreover, we explore how to 
improve the training efficiency by neighbor sampling.


\begin{figure}[!t]
    \centering
    \hspace*{4mm}
    \includegraphics[width=0.45\textwidth]{graph/graph_figure.pdf}
    \caption{Illustration of e-commerce search graph.}
    \label{fig:ecomm_graph}
    \vspace{-6mm}
\end{figure}



\section{Related Work}
\label{sec:related_work}

\subsection{Graph Convolution Network}
Neural networks that operate on graphs have previously been introduced in~\cite{gori2005} and~\cite{scarselli2009} as a form of recurrent neural network. Their frameworks apply propagation functions until node representations reach a stable fixed point. Later on, with the success of convolution neural networks in various domains, such as image classification~\cite{he2016}, semantic segmentation~\cite{jegou2017}, text classification~\cite{kim2014}, and machine translation~\cite{gehring2017},
there is an increasing interest in generalizing convolution network to graph domain. Advances in this Graph Convolution Network (GCN) directions are often categorized into spectral approaches and non-spectral approaches.

Spectral approaches work with a spectral representation of the graph. Originally, in the work of \citeauthor{bruna2013spectral}, the convolution operation is defined in the Fourier domain by computing the eigendecomposition of the graph Laplacian, which, however, requires intense computations. 
\citeauthor{kipf2016semi} alleviated the computational cost by developing an efficient layer-wise propagation rule based on a first-order approximation of spectral graph convolutions.
However, the layer-wise propagation rule still have two drawbacks during training procedure. First, the graph convolution requires full graph Laplacian, which is computational-expensive and even problematic for training with large graph. Second, the full graph Laplacian is computed from a fixed graph, which do not naturally generalize to unseen nodes.

The other non-spectral approaches define convolutions directly on the graph, by operating on a set of spatially close neighbors. GraphSAGE~\cite{hamilton2017inductive} avoided operating on the entire graph Laplacian by developing a learnable aggregation functions, which comprehensively scale the GCN algorithm to large graph and achieve the ability to generate node embeddings for previously unseen data. Additionally, the neighbor sampling in the work of GraphSAGE alleviate the computation cost to receptive fixed field during mini-batch training procedure. Later on, PinSAGE \cite{ying2018graph} scaled the GCN algorithm to the real item-item recommendation task with large graph having billions of nodes and edges, which paves the way of large-scale deep recommendation systems based on GCN architectures. 

Recently, there are plenty of GCN variants proved to be more effective than previous first wave of GCN exploration. LightGCN~\cite{he2020lightgcn} simplifies the GCN algorithm significantly by reducing the unnecessary and even noisy operations, feature transformation and nonlinear activation, and achieves state-of-the-art results on recommendation tasks.
Graph Attention Network \cite{velivckovic2017graph} leverages attention mechanisms in the neighbor aggregation process to improve the performance.

Our work differs from the above approaches, in that we develop a simple and effective GCN solution for a web-scale e-commerce embedding retrieval problem. To the best of our knowledge, we are the first to explore GCN's application to search embedding retrieval task. Accordingly, to make this happen, we have tried many techniques. In this paper, we will share our experience and present the best known approach.



\subsection{Embedding Retrieval in Search Engine}
Recently, embedding retrieval technologies have been widely adopted in the modern recommendation and advertising systems~\cite{youtube2016, mind2019, tree2018}, while have not been widely used in search engine yet. We find a few works about retrieval problems in search engine~\cite{palangi2016deep,vu2017search}, while they have not been applied to the industrial production system. DPSR~\cite{zhang2020towards} is one of the first practical explorations in this direction of applying embedding retrieval in the industrial search engine system. Moreover, the well known DSSM~\cite{Huang:2013:LDS:2541176.2505665} and its following work  CDSSM~\cite{Shen:2014:LSR:2567948.2577348} have pioneered the work of using deep neural networks for relevance scoring, which is very different task from embedding retrieval though.














\section{Method}
\label{sec:method}


Given a graph $\G = (\mathcal{V}, \mathcal{E})$ where each $v\in \mathcal{V}$ stands for an entity node, and each $e \in \mathcal{E}$ stands for an edge between two entities, let's denote the set of all the neighbors for a node $v$ as $\mathcal{N}_v$, the set of queries as $\mathcal{Q}$, and the set of items as $\mathcal{I}$, where $\mathcal{Q} \subseteq \mathcal{V}$ and $\mathcal{I} \subseteq \mathcal{V}$.

\header{Neighbor Aggregation.}
The core of GCN is to compute the $l$-th layer's representation of a target node by all its neighbors and itself in $(l-1)$-th layer. Formally, we can define the aggregation operation as follows
\begin{equation*}
\mathbf{h}_{v}^{l} = \text{AGGREGATE}(\mathbf{h}_v^{l-1}, \mathbf{h}_{u}^{l-1}, \forall u \in \mathcal{N}_{v} ),
\end{equation*}
where $\mathbf{h}_v^l\in \mathbb{R}^{d}$ denotes the $d$-dimensional embedding representation of a node $v$ at $l$-th layer, the AGGREGATE function is a pooling function that takes the target node and all its neighbor nodes as inputs. 

In SearchGCN, we use the following neighbor aggregation function that can be explained as a weighted sum of all its neighbors,
\begin{equation}
\mathbf{h}_{v}^{l} = \sum_{u \in \mathcal{N}_{v}} \alpha^{l-1}_{vu} \mathbf{h}_{u}^{l-1},
\label{eq:attention_aggregation}
\end{equation}
\begin{equation}
\alpha^{l-1}_{vu} = \frac{\text{exp}\left(\text{LeakyReLU}\left({\mathbf{w}^{l-1}}^\top [\mathbf{h}^{l-1}_{v}||\mathbf{h}^{l-1}_{u}]\right) \right)} 
{\sum_{u\in\mathcal{N}_{v}} \text{exp} \left( \text{LeakyReLU}\left({\mathbf{w}^{l-1}}^\top [\mathbf{h}^{l-1}_{v}||\mathbf{h}^{l-1}_{u}]\right) \right)},
\label{eq:attention_weight}
\end{equation}
where $.^\top$ denotes the transpose operation, $||$ denotes the concatenation operation and $\mathbf{w}^{l-1} \in \mathbb{R}^{2d}$ is model parameter to learn. 

\header{Layer Combination.}
In our {SearchGCN}, to refine the embedding of query and item node, we sum the neighbor embeddings obtained by neighbor aggregation layer-by-layer to form the final embedding:
\begin{equation}
\mathbf{z}_{v} = \sum_{l=0}^{L} \mathbf{h}_{v}^{l}. \nonumber
\end{equation}

\header{Neighbor Sampling.}
Since our e-commerce graph has hundreds of millions of nodes and billions of edges, which is too large to be fully loaded into computer memory, and the e-commerce graph appears to be significant imbalance,  which makes the neighbor aggregation expensive. Therefore, to be practical in an industrial system, we need to develop a neighbor sampling approach that is efficient in both memory and computation.

First, we prune the neighborhood size for each node to at most $50$, by the weights of the edges between each neighbor and the target node, to allow us to load all edges into memory during the training. Second, we introduce randomness to neighbor sampling, by sampling some fixed number (\textit{e.g.}, $10$) of neighbors according to edge weights, to reduce the computational cost to aggregate neighbors and increase model generalization ability.








































\section{Experiments}
\label{sec:experiment}
We conduct experiments on a data set of $60$ days' user click logs and we can assume that if an item is clicked for a query, the item is relevant to the query.

\header{Offline Evaluation.}
We compare {SearchGCN} with a few baseline methods and report the evaluation results in Table~\ref{tab:offline_comparison}. \textit{SearchGCN-mean} adopts mean aggregator that gives equal weight to all neighbors. \textit{SearchGCN-attention} adopts attention mechanism in aggregation function as shown in Eqs. (\ref{eq:attention_aggregation}) and (\ref{eq:attention_weight}). \textit{SearchGCN-mask} adopts neighbor masking on both query and item side to mask the target query and item.

\begin{table}[tb]
    \centering
    \caption{Comparison between different methods.}
    \label{tab:offline_comparison}
    \begin{tabular}{c|cccc}
    \hline
        & Top-$1$   & Top-$10$   & AUC   & Sec./Step \\
    \hline
    DPSR~\cite{zhang2020towards} & $86.23\%$ & $99.59\%$ & $0.737$ & $0.276$ \\
    GraphSAGE~\cite{hamilton2017inductive} & $79.29\%$ & $95.97\%$ & $\mathbf{0.783}$ & $1.03$ \\
    PinSAGE~\cite{ying2018graph} & $68.59\%$ & $93.18\%$ & $0.736$ & $1.07$ \\
   
    \hline
    {SearchGCN}-mean & $86.76\%$ & $99.43\%$ & $0.764$ & $1.04$ \\
    {SearchGCN}-attention & $86.57\%$ & $99.27\%$ & $0.751$ & $1.05$ \\
    {SearchGCN}-mask & $\mathbf{87.72\%}$ & $\mathbf{99.67\%}$ & $0.768$ & $0.98$ \\
    \hline
    \end{tabular}
\end{table}



\header{Online A/B Tests.} We conducted live experiments over $10\%$ of the entire site traffic during a period of one week using a standard A/B testing configuration. To protect confidential business information, only relative improvements are reported. Table~\ref{tab:abtest} shows that the proposed {SearchGCN} retrieval improves the production system for core business metrics in e-commerce search, including user conversation rate (UCVR), revenue per mille (RPM) and gross merchandise value (GMV). As a result, the proposed {SearchGCN} has been deployed into JD.com's search production since July 2020.

\begin{table}[t]
\centering
    \caption{Improvements of {SearchGCN} in online A/B test.}
    \label{tab:abtest}
    
    \begin{tabular}{c|r r r r}
    \hline
            & UCVR  & RPM & GMV  \\
    \hline
    SearchGCN  & $+0.20\%$ & $+1.13\%$ & $+1.27\%$  \\
    \hline 
    \end{tabular}
   
\end{table}

\header{Improvement on Torso and Tail Query.}
We evaluate {SearchGCN}'s performance on different types of queries. We split our evaluation data set into three categories, head, torso and tail queries, according to the queries' frequency. 
As shown in Table~\ref{tab:tail_query}, we can see that the improvements on torso and tail queries are more significant than head queries. This observation strongly suggests that the GCN's neighbor aggregation could benefit more for the torso and tail queries, potentially because they can learn from their neighbor's representations. Similar trend also holds for long tail items, but we have to skip due to space limit.

\begin{table}[t]
    \centering
    \caption{Comparison between different methods on head, torso, and tail queries. The metric is top-1 score.}
    \label{tab:tail_query}
    \begin{tabular}{c|ccc}
    \hline
      & Head & Torso  & Tail \\
    \hline
    DPSR & $84.23\%$ & $92.61\%$ & $92.64\%$ \\
    SearchGCN & $85.73\%$ & $94.68\%$ & $94.77\%$ \\
    \hline
    Difference & $1.50\%$ & $2.07\%$ & $2.13\%$ \\
    Error reduction rate & $9.51\%$ & $28.01\%$ & $28.94\%$ \\
    \hline
    \end{tabular}
    \vspace{-4mm}
\end{table}
\section{Conclusion}
\label{sec:conclusion}
In this paper, we have proposed a GCN based approach for embedding retrieval in search engine. We also extensively study the offline comparison with other baseline models, and the results show that the proposed SearchGCN is both effective in retrieval quality metrics and training efficiency. Consequentially, we have successfully deployed SearchGCN to one of largest e-commerce search engine in the world, with significant business metric gains in the online A/B test.

\section{Company Profile}

\section{Presenter Profiles}
\header{Xinlin Xia} is a researcher in the Department of Search and Recommendation at JD.com Beijing. He received his master degree in Computer Science from Sichuan University, China. His research focuses on information retrieval.

\header{Han Zhang} is a researcher in the Department of Search and Recommendation at JD.com Beijing. She graduated from Natural Language Processing Lab, Department of Computer Science and Technology, Tsinghua University. Her research focuses on information retrieval.

\header{Wen-Yun Yang} is a principal scientist at JD.com and previously a research scientist at Facebook News Feed team. He had about 8 years experience of tech leading in search and recommendation backend systems, candidate retrieval, ranking and modeling in general. He received his Ph.D. degree in Computer Science from University of California, Los Angeles.

\end{document}
