HGAMN: Heterogeneous Graph Attention Matching Network for Multilingual POI Retrieval at Baidu Maps
Jizhou Huang Haifeng Wang Yibo Sun Miao Fan Zhengjie Huang Chunyuan Yuan Yawen Li


















  Baidu Inc., Beijing, China  
  ^†Beijing University of Posts and Telecommunications


huangjizhou01, wanghaifeng, sunyibo, fanmiao, huangzhengjie, yuanchunyuan@baidu.com;warmly0716@bupt.edu.cn











§ ABSTRACT 
The increasing interest in international travel has raised the demand of retrieving point of interests (POIs) in multiple languages. This is even superior to find local venues such as restaurants and scenic spots in unfamiliar languages when traveling abroad. Multilingual POI retrieval, enabling users to find desired POIs in a demanded language using queries in numerous languages, has become an indispensable feature of today's global map applications such as Baidu Maps. This task is non-trivial because of two key challenges: (1) visiting sparsity and (2) multilingual query-POI matching. To this end, we propose a Heterogeneous Graph Attention Matching Network (HGAMN) to concurrently address both challenges. Specifically, we construct a heterogeneous graph that contains two types of nodes: POI node and query node using the search logs of Baidu Maps. First, to alleviate challenge #1, we construct edges between different POI nodes to link the low-frequency POIs with the high-frequency ones, which enables the transfer of knowledge from the latter to the former. Second, to mitigate challenge #2, we construct edges between POI and query nodes based on the co-occurrences between queries and POIs, where queries in different languages and formulations can be aggregated for individual POIs. Moreover, we develop an attention-based network to jointly learn node representations of the heterogeneous graph and further design a cross-attention module to fuse the representations of both types of nodes for query-POI relevance scoring. In this way, the relevance ranking between multilingual queries and POIs with different popularity can be better handled. Extensive experiments conducted on large-scale real-world datasets from Baidu Maps demonstrate the superiority and effectiveness of HGAMN. In addition, HGAMN has already been deployed in production at Baidu Maps, and it successfully keeps serving hundreds of millions of requests every day. Compared with the previously deployed model, HGAMN achieves significant performance improvement, which confirms that HGAMN is a practical and robust solution for large-scale real-world multilingual POI retrieval service.









<ccs2012>
<concept>
<concept_id>10002951.10003227.10003245</concept_id>
<concept_desc>Information systems Mobile information processing systems</concept_desc>
<concept_significance>500</concept_significance>
</concept>
<concept>
<concept_id>10002951.10003317.10003325</concept_id>
<concept_desc>Information systems Information retrieval query processing</concept_desc>
<concept_significance>500</concept_significance>
</concept>
</ccs2012>


[500]Information systems Mobile information processing systems
[500]Information systems Information retrieval query processing






HGAMN: Heterogeneous Graph Attention Matching Network for Multilingual POI Retrieval at Baidu Maps
    
	Jizhou Huang, 
	Haifeng Wang,
	Yibo Sun, 
	Miao Fan, 
	Zhengjie Huang, 
	Chunyuan Yuan,
    Yawen Li

    
===========================================================================================================









§ INTRODUCTION




As one of the key components of the search engines in almost all global map applications, such as Baidu Maps, multilingual POI retrieval plays a significant role in providing on-demand map services as the retrieved results directly influence the success or failure of routing and navigation, and hence impact the long-term user experience. For the 169 million Chinese tourists who traveled abroad in 2019 <cit.>, Baidu Maps, which covers more than 150 million POIs in 200 countries and territories worldwide, is their prior choice to find specific locations and navigate to desired destinations. Figure <ref> shows an example of the multilingual POI retrieval feature at Baidu Maps, where the query “TokyoΧ5854” consists of an English word “Tokyo” and a Chinese character “Χ5854”, meanwhile the name of the retrieved POI is composed of English words “Tokyo Tower” or Japanese words “67714EAC30BF30EF30FC”. To enable users who are traveling abroad to obtain their desired POIs effectively when finding local venues in unfamiliar languages and areas, it is crucial for a multilingual POI retriever to fill the gaps between queries and POIs in different languages and formulations. 

To build an effective multilingual POI retriever in both the academic and industrial fields, we must address two key challenges: 

	
  * Visiting Sparsity.	
	To the best of our knowledge, existing approaches on multilingual POI retrieval for industrial use mainly leverage large-scale user click logs for query-POI relevance scoring.
	However, the average visits of 150 million POIs at Baidu Maps are highly sparse.
	We empirically study a large-scale search log of Baidu Maps, which contains billions of search records. Statistics show that only 6.4% of the POIs have been clicked by one or more users. 
	The effectiveness of a POI retrieval model would significantly decline when handling the majority of POIs that have sparse click logs.
	
	
  * Multilingual Query-POI Matching. In real applications, most of the users search the overseas POIs by their native languages, which are more likely to be inconsistent with the languages of the target POIs. For example, a Chinese user may search the “Tokyo Tower” located in Japan using queries composed of Chinese words, meanwhile, the information of this POI is probably maintained in Japanese or English. As a result, a simple literal matching method cannot meet the demands of such cross-language retrieval. Moreover, queries are sometimes mixed keyboard inputs of multi-languages (e.g., English and Japanese, Chinese and Pinyin Alphabets), which further necessitates multilingual POI retrieval. 


In this paper, we present our recent efforts in designing and implementing an effective multilingual POI retrieval framework, which has already been deployed in production at Baidu Maps and has achieved great success in addressing both problems, as illustrated by Figure <ref>.
The framework can provide a data sparsity-tolerant multilingual POI retrieval function, which facilitates tens of millions of users to find their desired POIs every day.

This new framework is powered by a Heterogeneous Graph Attention Matching Network (HGAMN).
Specifically, we first construct a heterogeneous graph that contains two types of nodes: POI node and query node using the search logs of Baidu Maps. 
In this graph, to alleviate the visiting sparsity problem, we construct edges between different POI nodes to 
link the low-frequency POIs with the high-frequency ones, which enables the transfer of knowledge from the latter to the former.
To address the multilingual query-POI matching challenge, we construct edges between POI and query nodes based on the co-occurrences between queries and POIs, where queries in different languages and formulations can be aggregated for individual POIs.
Upon the constructed graph, we design an attention-based network to learn the representations of POI and query nodes.
Then, we use a multi-source information learning module to learn the location and multilingual text representations of the queries and POIs.
Finally, we fuse the node representations of a POI and its linked queries via a cross-attention module and use the fused representation to calculate the relevance score between the user's query and a candidate POI.
To facilitate the model training, we apply an in-batch negative sampling strategy <cit.> to produce more sample pairs and increase the number of training examples.

We evaluate HGAMN both offline and online using large-scale real-world datasets. For offline evaluation, the training and test sets consist of tens of millions of search records for several months, covering hundreds of cities and tens of millions of POIs worldwide. Experimental results show that HGAMN achieves substantial (absolute) improvements compared with several mainstream methods. For online evaluation, we launch our framework online to serve a portion of the search traffic at Baidu Maps. A/B testing was conducted between HGAMN and the previously deployed models. Experimental results show that the improvements are consistent with those obtained by the offline evaluation.

The main contributions can be summarized as follows:

	
  * Potential impact: We propose an end-to-end neural framework, named HGAMN, as an industrial solution to the multilingual POI retrieval task in global map applications. In addition, this framework has already been deployed in production at Baidu Maps, and it successfully keeps serving hundreds of millions of POI search requests every day.

	
  * Novelty: The design of HGAMN is driven by the novel idea that addresses the data sparsity problem and the multilingual matching problem by enhancing the representations of POIs via a heterogeneous graph. 
	
	
  * Technical quality: We evaluate HGAMN both offline and online using large-scale real-world datasets. Extensive experimental results show that our framework achieves significant improvements on multiple evaluation metrics compared with several mainstream methods.
	
	
  * Reproducibility: 
    We have made the source code publicly available  at <https://github.com/PaddlePaddle/Research/tree/master/ST_DM/KDD2021-HGAMN/>. 








§ HGAMN


HGAMN consists of three modules: multi-source information learning module, heterogeneous graph learning module, and POI ranker module. First, we feed a query, the candidate POIs, and the historical queries to the multi-source information learning module to learn the text and location representations of them. Then, we construct the heterogeneous graph of different POIs and historical queries. The constructed graph enables us to learn the POI representations from it by the heterogeneous graph learning module. Finally, we calculate the relevance score between the representations of the query and the candidate POIs by the POI ranker module. Figure <ref> shows the architecture of HGAMN. Subsequently, we introduce them in detail.




 §.§ Multi-Source Information Learning
  
Unlike traditional text retrieval, POI retrieval in map services mainly measures the relevance between a query and POIs rather than plain text. Besides its name, a typical POI also contains other multi-sourced and heterogeneous information such as the address, category, and GPS coordinates. Utilizing such information can facilitate retrieving more relevant POIs. Here we mainly introduce the location and text representations of a query q ∈𝒬 and a POI P_i ∈𝒫, where 𝒬 and 𝒫 denote a set of query and POI, respectively.




  §.§.§ GPS Encoding


POI's GPS coordinates are numerical pairs consisting of longitude and latitude. However, in the online system, the coordinates are usually stored as a Geohash string for its better properties: (1) it is easy to be used to index the POI and (2) it is convenient to be used to calculate the distance of two POIs. 

Instead of directly taking this numerical pair as a 2-dimensional feature vector, we use the Geohash algorithm <cit.> to encode the geographic coordinates into a short string of letters and digits. Specifically, given the latitude x_v and longitude y_v of a POI, the Geohash algorithm is performed as follows:

    s_GPS = 𝐆𝐞𝐨𝐡𝐚𝐬𝐡((x_v, y_v))   ,

where the length |s_GPS| ∈ [1, 12]. 

Given the Geohash string s_GPS=“wx4g09np9p”, we split the string to character sequence and add `[PAD]' at the beginning of the sequence if its length is less than 12, i.e., X = [`[PAD]', `[PAD]', `w', `x', `4', `g', `0', `9', `n', `p', `9', `p' ]. Then, we transform them into character embeddings 𝐗∈ℝ^12 × d_c, where d_c = 64 is the dimension of the character embedding.

An essential property of Geohash string is that POIs with a longer common prefix are closer to each other in geographic distance. Thus, the Geohash string is order-sensitive. To encode this kind of property, we utilize the bidirectional gated recurrent unit to encode the character embeddings, which is formulated by:

    𝐡_t = [𝐆𝐑𝐔(𝐗_t); 𝐆𝐑𝐔(𝐗_t)]   .


The last state 𝐡_12 is used as the representation of the POI's GPS. We use this module to transform each POI's GPS coordinates into an embedding, and obtain an embedding matrix 𝐆∈ℝ^|𝒫| × d, where |𝒫| denotes the size of 𝒫. 

We regard a query's location as the place where the user is typing in the query. Similarly, we can obtain the query's location representation 𝐆_u according to the user's GPS coordinates.





  §.§.§ Text Encoding
  
For multilingual POI retrieval in map services, the text data such as queries, POI names, and POI addresses are critical for improving the retrieval performance.

To better handle the multilingual matching problem, we take a sequence (such as a query or POI name) consisting of multilingual characters and alphabets as input and adopt a pre-trained language model to obtain its representation.

Specifically, we use the pre-trained language model ERNIE <cit.> as the basic component, which shows better performance on extracting multilingual features and semantic information. 
We directly utilize ERNIE to obtain q's text representation 𝐪 by:

    𝐪 = 𝐄𝐑𝐍𝐈𝐄([c_1, c_2, …, c_L])  ,

where [c_1, c_2, …, c_L] is the character sequence of the query. 


After analyzing the query logs, we found that a query's location helps retrieve the desired POI because users usually demand the nearest target. To utilize such location features, we combine a query's location representation with its text representation. Thus, the final representation of a query is represented as:  𝐪 = 𝐪 + 𝐆_u.

For each POI P_i, we use 𝐐_P_i to denote the matrix of the representations of the top-4 queries associated with it, i.e., 𝐐_P_i = [𝐪_1, 𝐪_2, 𝐪_3, 𝐪_4].


For each POI P_i, we concatenate its name and address as a long character sequence and apply ERNIE to extract its text representation. Similarly, we combine P_i's location and text representations to obtain its final representation 𝐏_i ∈ℝ^1 × d by:

    𝐏_i = 𝐄𝐑𝐍𝐈𝐄([x_1, x_2, …, x_L, a_1, a_2, …, a_L]) + 𝐆_i  ,

where [x_1, x_2, …, x_L] is the character sequence of P_i's name and [a_1, a_2, …, a_L] is the character sequence of P_i's address. 𝐆_i is the GPS encoding of P_i. We stack each POI's embedding together as a POI embedding matrix 𝐏∈ℝ^|𝒫| × d.



 §.§ Heterogeneous Graph Learning
 
Here, we introduce how to construct the heterogeneous graph from search logs and how to learn POI representations from the heterogeneous graph.




  §.§.§ Graph Construction

Multilingual POI retrieval faces the visiting sparsity and multilingual matching problems. To alleviate the visiting sparsity problem, we construct edges between different POI nodes to link the low-frequency POIs with the high-frequency ones, which enables the transfer of knowledge from the latter to the former.
Furthermore, to mitigate the multilingual matching problem, we construct edges between POI and query nodes based on the co-occurrences between queries and POIs. Thus, the graph can aggregate queries in different languages and formulations for each POI. 
As shown by Figure <ref>, both types of nodes and edges constitute a heterogeneous graph 𝒢(𝒱, ℰ). 

The construction of the heterogeneous graph is as follows. A user's search behaviors produce a visited POI sequence in search logs. We extract relations of POI-POI from the historical search sequences. A search sequence is a period of time that consists of “a sequence of interactions” for the similar information need <cit.>, which can reflect the similarities of successive POIs. To capture the similarity between two POIs, we define the co-occurrence frequency of them in the search sequences as the graph's edge.
To extract this kind of relation, a 2-gram sliding window is perform on the search sequences. We apply the pointwise mutual information (PMI) to calculate the weight of the edges by:

    𝐀^pp_ij = PMI(P_i, P_j) = log Pr(P_i, P_j)/Pr(P_i) · Pr(P_j) ,  
        Pr(P_i, P_j) = #W(P_i, P_j)/#W ,  
        Pr(P_i) = #W(P_i)/#W ,

where #W(P_i, P_j) is the number of sliding windows that contain both P_i and  P_j. #W denotes the number of sliding windows, and #W(P_i) is the number of sliding windows that contain P_i. 

After typing in a query, a user would click on the desired POI from a list of ranked POIs that the POI search engine suggested.
This process produces a large-scale query-POI pairs where the multilingual expressions of each POI can not only effectively mitigate the multilingual matching problem, but also bridge the semantic gap between queries and POIs. For example, users usually make spelling errors or use abbreviations, which would lead to poor results when directly matching query and POI text information. Motivated by this observation, we try to model the relations between historical queries and POIs. 

Specifically, we select the top-4 searched queries for each POI and connect an edge for every POI and its historical query nodes for POI-Query relations. In this way, we can build connections between POIs and Queries. Formally, the adjacency matrix can be formulated as follows:

    𝐀^pq_ij = c_i,j/∑_k=1^|𝒬_P_i| c_i,k ,

where c_i,j is the frequency of query-POI pair (q_j, P_i), q_j ∈𝒬_P_i.




  §.§.§ Heterogeneous Graph Learning
  
To learn representations of POIs and queries from the heterogeneous graph, we use attention-based graph neural network to aggregate neighbors for generating a distributed representation of each node based on the heterogeneous graph, which enables us  to learn a high-level hidden representation for each vertex.

As shown by Figure <ref>, there are two types of nodes (POI node and query node) and two types of edges (POI-POI correlation and POI-Query semantic relation) in the graph. For a certain node n_i, its initial embedding: 𝐧_i ∈ℝ^d_n, is randomly initialized by a uniform distribution. 


First, we introduce how to produce edge embeddings for the heterogeneous graph. We apply an aggregator proposed in GraphSAGE <cit.> to integrate neighbor node embeddings for edge embedding 𝐞_j:

    𝐞^(k)_j = σ( 𝐦𝐚𝐱({𝐖^(k)𝐧_t, n_t∈𝒩_j } ) )   ,

where 𝐖^(k) is the trainable weight of k-th layer, σ(·) is the sigmoid activation function. 𝒩_j is the neighbor set of edge e_j.

Suppose the node n_i has m edges connected with it, we concatenate edge embeddings for the node n_i as 𝐄_i ∈ℝ^m × d_e: 

    𝐄_i = (𝐞_i,1, 𝐞_i,2, …, 𝐞_i,m)  .


Next, we apply the cross attention mechanism to fuse 𝐄_i into a vector ẽ_i ∈ℝ^d_e by: 

    α_i   = 𝐬𝐨𝐟𝐭𝐦𝐚𝐱(𝐧_i tanh(𝐖_r 𝐄^T_i) ⊙𝐀^(r)_i )   , 
    ẽ_i    = α_i^T𝐄_i  ,

where ⊙ denotes the element-wise multiplication operation. α_i∈ℝ^m is the coefficients. 𝐖_r ∈ℝ^d_n × d_e is a trainable weight for edge type r. 𝐀^(r)_i∈{𝐀_i,1:m^pp, 𝐀_i,1:m^pq} denotes the weights of m edges which belong to the type r and connect with n_i.


Then, the overall node representation of n_i can be computed by:

    𝐧_i = 𝐧_i + 𝐖_1ẽ_i  + 𝐖_2 𝐧^'_i   ,

where 𝐖_1 ∈ℝ^d_n × d_e, 𝐖_2 ∈ℝ^d_n × d are two trainable parameters and 𝐧^'_i ∈{𝐐_P_i,𝐏_i }.
𝐐_P_i and 𝐏_i denote P_i's associated query representations and its POI embedding, respectively.

Finally, the graph learning module produces the representations of all POIs:   𝐏∈ℝ^|𝒫| × d_n, and the representations of all queries: 𝐐∈ℝ^|𝒬| × d_n.




 §.§ POI Ranker



The POI ranker module calculates the relevance between a query q and a candidate POI P_i based on the learned representations.
This module also considers P_i's historical queries 𝒬_P_i when predicting the relevance since 𝒬_P_i conveys substantial evidence to bridge the semantic gap between P_i and q.
Both P_i and 𝒬_P_i contain essential information for calculating the relevance, but their importance is different. How to automatically determine the importance of them for measuring the relevance is still a challenge. 


In this paper, we apply an attention module to automatically determine their importance and fuse them as a feature vector. Specifically, we regard the representation of q as the key, while regard the representations of P_i and 𝒬_P_i as the value. We stack the representations of P_i and 𝒬_P_i as a new matrix  𝐌 = [𝐏_i, 𝐐_P_i ]. Each attention weight ϕ_k is defined as follows:

    s_k = 𝐖_4tanh ([𝐪; 𝐌_k] 𝐖_3 + b)   ,  
       ϕ_k = exp(s_k)/∑_j=1^|𝐌| exp(s_j)  ,

where 𝐖_3 ∈ℝ^2d_n × d_n and  𝐖_4 ∈ℝ^1 × d_n are trainable matrices. 


We use the attention weight to fuse the representations of P_i and 𝒬_P_i by:

    𝐦 = ∑_k=1^|𝐌|ϕ_k 𝐌_k   ,
 
where 𝐦∈ℝ^d_n is the fused POI representation.

Finally, we concatenate 𝐪 with 𝐦, and feed them into the output softmax layer for relevance calculation by:

    Pr(c_i|q, P_i, 𝒢) = 𝐬𝐨𝐟𝐭𝐦𝐚𝐱([𝐪; 𝐦] 𝐖_v)   ,

where 𝐖_v ∈ℝ^2d_n × 2 is the trainable parameter, and Pr(c_i|q, P_i, 𝒢) is the probability vector of a category c_i ∈{0, 1}. The category 1 (0) indicates that P_i is relevant (irrelevant) to q. We use the output probability of category 1 as the score for ranking.



 §.§ Model Training

We train the model in a supervised manner by minimizing the cross-entropy loss of relevance classification described above, whose loss function is defined as follows:

    ℒ = - ∑_i=1^|𝒫| y_i𝐥𝐨𝐠 Pr(c_i|q, P_i, 𝒢)   ,

where |𝒫| denotes the amount of total training POIs, and y_i is the label of the instance POI P_i.

To increase the number of training instances inside each batch and improve the computing efficiency, we apply an in-batch negative sampling strategy <cit.>. Specifically, assuming that we have B queries in a mini-batch, each one is associated with a relevant POI. Let 𝐐̂ and 𝐏̂ be the (B × d) matrix of query and POI embeddings in a batch of size B. 𝐒 = 𝐐̂𝐏̂^T is a (B × B) matrix of similarity scores, where each row corresponds to a query, paired with B POIs. In this way, we reuse computation and effectively train on B^2 (q_m, P_n) query-POI pairs in each batch. Any (q_m, P_n) pair is a positive example when m = n, and negative otherwise. This procedure creates B training instances in each batch, where there are B - 1 negative POIs for each query.




§ EXPERIMENTS
  
To thoroughly test HGAMN, we conduct extensive experiments in both offline and online settings. 



 §.§ Comparison Models


We evaluate HGAMN against the following four groups of methods. Furthermore, to understand the relative importance of several facets of HGAMN, variations of this model with different settings are implemented for comparison.



  §.§.§ Text Matching Group


	
  * DSSM <cit.> is a widely-used text matching model in which a deep neural network is employed to predict the relevance between keywords and documents. In our experiments, for all DSSM based models, we treat queries as keywords while POI name and POI address as documents. 
	
	
  * ARC-I <cit.> uses pre-trained word embeddings to represent the text. It then uses a convolutional network to learn the semantic features and feeds the feature vectors to a multi-layer perceptron for prediction. 
	
	
  * Conv-DSSM <cit.> extends DSSM by adding extra convolutional layers to extract sentence-level features from n-gram word representations.





  §.§.§ Query-POI Matching Group


	
  * DPSM <cit.> is a POI latent semantic model based on neural networks, which extracts query and POI semantic features for the similarity calculation.
	
	
  * PALM <cit.> is an attention-based neural network. It uses semantic similarity and geographic correlation to quantify the query-POI relevance. 
	






  §.§.§ Our Model and Its Variants


	
  * HGAMN is the complete model defined in Section <ref>. In this setting, we use it independently as a POI retriever to return the desired POIs.
	
	
  * HGAMN w/o POI-POI Graph. In this setting, we remove the edges between different POIs in the graph learning module described in Section <ref>. The removed part is designed to mitigate the visiting sparsity problem.  
	
	
  * HGAMN w/o POI-Query Graph. In this setting, we remove the edges between different POIs and queries in the graph learning module described in Section <ref>. The removed part is designed to mitigate the multilingual matching problem.  
	
	
  * HGAMN w/o Heterogeneous Graph. In this setting, we remove the entire graph learning module described in Section <ref> and directly use the query and POI's representations described in section <ref> for calculation.  





  §.§.§ Online Model Group


    
  * LTR is the basic model for online multilingual POI retrieval system at Baidu Maps <cit.>. It adopts GBRank <cit.> as the specific learning-to-rank model. This model mainly uses heuristic features, including the popularity of POIs, the demographic information on users, and the spatial-temporal features of each POI, such as the frequency of search on specific types of POIs at different times and locations.
    
  * LTR + HGAMN is trained with all the features employed by LTR and the similarity feature computed by HGAMN. It is expensive to  directly deploy HGAMN online to serve hundreds of millions of requests every day. For this reason, we instead use the feature generated by HGAMN offline as one of the features fed to the LTR model.




 §.§ Offline Evaluation



  §.§.§ Dataset

The services of Baidu Maps cover over 200 countries and territories worldwide, where the sessions on POI search dominate about 80% search traffic. A POI search session refers to a sequence of interactions between a user and the POI search engine.

We collect a large number of POI search sessions from the search logs of international services at Baidu Maps for offline evaluation. Each example of the dataset consists of the query typed by the user, the POI list that the POI search engine suggested, and the exact POI that the user clicked. Table <ref> shows the statistics of the large-scale dataset sampled from one-month search logs for model training (abbr. Train), hyper-parameter tuning (abbr. Valid), and performance testing (abbr. Test).








  §.§.§ Evaluation Metrics


We use several widely-used metrics in information retrieval for offline performance evaluation.

The first group of metrics, Success Rate (SR) at Top-K (SR@K), is the coarse metric that denotes the average percentage of ground-truth POIs ranked at or above the position K in the ranked list provided by a POI retriever. Because of the limited space for display on mobile phones, Baidu Maps can mostly display 3 POIs on the first screen when the input keyboard is launched and at most 10 POIs when the input keyboard is closed. Therefore, we consider SR@1, SR@3, and SR@10 for offline evaluation.

Another group of fine-grained metrics, including Mean Reciprocal Rank (MRR) and normalized Discounted Cumulative Gain at Top-K (nDCG@K), concerns more about the exact position where a POI retriever arranges the ground-truth POI in the returned list. We consider nDCG@1, nDCG@3, and nDCG@10 for offline evaluation due to the display limitations on  mobile phones.



  §.§.§ Model Configuration

The dimensionality of POI and query embeddings d is set to 128. The sequence length of query text, POI name, and POI address is set to 30. The POI graph learning module consists of two graph attention layers with output dimensionality of d=128 and d'=256, respectively. The number of heads in the multi-head attention K is chosen from {1, 2, …, 10 }, and finally, set to 4. 

During training, we use Adam optimizer <cit.>, with the learning rate initialized to 0.001 and gradually decreased during the process of training. 
To prevent overfitting, we use the dropout strategy with a dropout rate of 0.5. The maximum training epoch is set to 40, and the batch size of the training set is set to 64. 



  §.§.§ Experimental Results

In this section, we evaluate the effectiveness of HGAMN for the multilingual POI retrieval task. Table <ref> shows the performance of offline assessments on the models mentioned in Section <ref>. From the results, we can see that the proposed model HGAMN significantly outperforms all baseline methods on the large-scale real-world dataset. Specifically, we have the following observations.

(1) HGAMN significantly outperforms all conventional text retrieval methods (i.e., DSSM, ARC-I, and Conv-DSSM). Furthermore, the “HGAMN w/o POI-POI Graph” model also achieves better performance compared with these methods. The main reason is that the POI-Query graph is able to model multilingual features between a POI and its historical queries, which enables us to mitigate the gap between a query and the candidate POIs.

(2) Compared with recently proposed neural-based POI retrieval methods (i.e., DPSM and PALM), HGAMN achieves better performance. Although these methods combine geographic or spatial-temporal features with text representations for POI retrieval, they do not take the POI visiting sparsity problem into account, which is a critical problem in industrial map services. The POI-POI graph builds connections between low-frequency POIs and their similar high-frequency ones, which is able to transfer the abundant supervisory signals from high-frequency POIs to facilitate learning better representations of the low-frequency POIs. The  results verify that HGAMN is able to effectively relieve this problem.

(3) After removing the POI-POI graph and POI-Query graph separately (“HGAMN w/o POI-POI Graph” and “HGAMN w/o POI-Query Graph”), the performance of HGAMN decays considerably compared with the complete model. This indicates that both components in HGAMN are essential for multilingual POI retrieval, and they are complementary to each other.

(4) In the last section of Table <ref>, we observe that the LTR model outperforms the single HGAMN model. The reason is that the LTR model is one of the typical industrial ranking models based on a large set of time-proven high-quality features <cit.>. 
However, after adding the feature computed by HGAMN into the LTR model, the “LTR + HGAMN” model achieves significant improvements. Since it is challenging to create a new feature that is able to significantly improve the overall performance of industrial ranking models, the improvements made by “LTR + HGAMN” further confirm the effectiveness of HGAMN. This shows that HGAMN can not only be used as an individual ranking model, but also be used to obtain a single strong feature that is robust to an industrial ranking framework.




 §.§ Online A/B Testing




  §.§.§ Traffic of Data

Before being launched in production, we would routinely deploy the new model online and make it randomly serve 5% traffic of the POI search. During the A/B testing period, we monitor the performance of the new model and compare it with the previously deployed models. This period conventionally lasts for at least one week. 




  §.§.§ Experimental Results

We use SR@1, SR@3, and SR@10 as the metrics for online evaluation, which are also adopted by offline evaluation. Table <ref> shows the experimental results of the online A/B testing on different models mentioned in Section <ref>. All models were selected by the test set for offline evaluations, and we launched the best-performed ones. They are tested by 5% search traffic of Baidu Maps.



Compared with the offline evaluation results, we gain lower results on SR@1, SR@3, and SR@10 in the online A/B testing. The main reason is that the POI lists returned by our POI search engine might be ignored entirely by a small proportion of users, mainly because they prefer directly typing in the full names of their desired POIs and then click the search button. In this interactive mode, Baidu Maps will directly provide users with the relevant POIs. This results in a phenomenon that none of the returned POIs were clicked, which may lead to much lower performance on Success Rate (SR). However, the relative improvements of these models are consistent with those obtained by the offline evaluation.




§ DISCUSSION
  
Here we explore the reason why HGAMN is able to boost both the offline and online performance of the POI search engine. Generally speaking, as an end-to-end framework for multilingual POI retrieval, HGAMN can produce an intermediate feature vector, i.e., the graph-based representation of a POI (denoted by “HGAMN”). The probability from the classifier, taking the vector as input, is a reliable indicator to decide the rank order of candidate POIs in the model. The significance of this indicator has already been proved by the experimental results of both offline and online evaluations, which are reported by Table <ref> and Table <ref>, respectively. 

Moreover, we are curious about how much this probability from the intermediate vector, as a feature, can contribute to the GBRank-based multilingual POI retrieval model LTR, which has kept serving online in the search engine of international service at Baidu Maps. From the perspective of industrial practice, we need to figure out the relative importance of a proposed feature among all features leveraged by the GBRank model for multilingual POI retrieval.



GBRank can provide a score that indicates how useful a feature was in constructing the boosted decision trees within the model, which can help investigate the impact of different features (e.g., <cit.>). The more a feature is used to make critical decisions for decision trees, the higher its relative importance is allocated. 
Figure <ref> illustrates the weights of the top-10 most important features in “LTR + HGAMN”, and the total weight of them is 71.67%. 
Among all features, the importance of the graph-based representation (i.e., f1, colored in green) ranks 1^st with the weight of 16.89%.
This further demonstrates that HGAMN is able to significantly improve the effectiveness of multilingual POI retrieval.




§ RELATED WORK
 
Here we briefly review the closely related work in the fields of text retrieval, POI retrieval, and heterogeneous graph neural network.



 §.§ Text Retrieval
  
Text retrieval aims to provide the most relevant documents for a query <cit.>. There are three conventional categories of methods for text retrieval: pointwise (such as logistic regression <cit.>), pairwise (such as RankSVM <cit.> and RankBoost <cit.>), and listwise (such as ListNet <cit.> and  AdaRank <cit.>). The major difference between them lies in the input document space, output space, and loss function. These methods require manually designed features. However, such features may be sparse and insufficient to effectively encode the semantic information of queries and documents. Moreover, designing effective features is usually time-consuming and heavily relies on expert knowledge in particular areas <cit.>.

With the rapid development of deep learning, researchers adopt neural networks to automatically learn representations for text retrieval. For example,  huang2013learning propose a DSSM model to map the query and the document into a semantic space and treat the similarity between two embeddings as the relevance score. Subsequently, Conv-DSSM <cit.> and LSTM-DSSM <cit.> are proposed to improve the ability of semantic feature extraction of DSSM.  pang2016text propose to model text matching as the problem of image recognition and employ a convolutional neural network to extract matching features. DeepRank <cit.> further simulates the human judgment process to capture important features. 

Multilingual POI retrieval task is different from text retrieval task in that it requires not only capturing semantic similarities between text data but also addressing the cross-language matching problem and textual-geographic matching problem (i.e., computing the relevance between a query and a POI by taking both text data and geolocations into consideration), which are generally not required in text retrieval task.




 §.§ POI Retrieval

There is a growing body of work that explores and assesses POI retrieval <cit.>. Here, we briefly review recent attempts on applying neural networks to address this task. To address the mistyping or an alias inquiry problem,  zhao2019poi propose a POI latent semantic model based on deep learning, which can effectively extract query and POI features for similarity calculation.  p4ac-kdd21 propose a personalized POI retrieval model which also has the ability to provide time- and geography-aware results. Furthermore, geographic information <cit.> and spatial-temporal factors <cit.> have been considered in recent work. 

However, little work has considered the problems of visiting sparsity and multilingual query-POI matching, which are two main challenges that must be tackled for POI retrieval in global map applications such as Baidu Maps. To address both problems, we first encode a POI's multi-source information to enrich its representation. Then, we establish the relations among different POIs and queries by constructing a heterogeneous graph. Finally, we produce enhanced representations of queries and POIs via the heterogeneous graph, which has a significant effect on POI retrieval performance.




 §.§ Heterogeneous Graph Neural Network

The heterogeneous graph, which constitutes multiple types of nodes or edges, is ubiquitous in real-world applications.     Previous studies <cit.> focus on different aspects of the heterogeneous graph to learn node representations. For example,  sun2018joint propose a meta-graph-based network embedding model, which simultaneously considers the hidden relations of all meta information of a meta-graph.  wang2019heterogeneous propose a heterogeneous graph neural network, which utilizes hierarchical attention, including node-level and semantic-level attentions, to learn node representations from meta-path based neighbors.  cen2019representation propose a unified attributed multiplex heterogeneous network to solve the multiplex heterogeneous graph embedding problem with both transductive and inductive settings.  zhu2020hgcn propose a heterogeneous graph convolution network to directly learn the complex relational hierarchy, potential incompatible semantics, and node-context relational semantics.

Inspired by the recent success in heterogeneous graph representation learning, we build a heterogeneous graph from search logs, which links the low-frequency POIs with the high-frequency ones and aggregates queries in different languages and formulations for individual POIs. As a result, the visiting sparsity and multilingual matching problem can be effectively alleviated by enhancing the representations of queries and POIs via the heterogeneous graph. 




§ CONCLUSIONS AND FUTURE WORK
  
This paper presents an industrial solution to the multilingual POI search for international services at Baidu Maps. We propose a heterogeneous graph attention matching network (HGAMN) to address the visiting sparsity and multilingual query-POI matching problems. HGAMN is composed of three modules: (1) a multi-source information learning module, which learns the text and location representations of the multilingual query,  POI name, and POI address; (2) a heterogeneous graph learning module, which constructs the connections of different POIs and historical queries, and learns the node representations from the heterogeneous graph; and (3) a POI ranker module, which calculates the relevance between a query and candidate POIs.
We conduct both offline and online evaluations using large-scale real-world datasets. The experimental results show that HGAMN achieves significant improvements over several mainstream approaches, which demonstrates the effectiveness of enhancing the representations of queries and POIs via the heterogeneous graph to improve multilingual POI retrieval.

The user input habits and preferences are not taken into account in this paper. In the future, we intend to utilize these kinds of vital information for personalized POI searches. In addition, previous studies have shown that context <cit.> and explanation <cit.> can bring significant improvements in recommendation effectiveness and increase user satisfaction. As future work, we plan to investigate whether multilingual POI retrieval could benefit from the adoption of such factors.


ACM-Reference-Format






