More Web Proxy on the site http://driver.im/

research-article

Incremental Spatio-Temporal Graph Learning for Online Query-POI Matching

Authors:

Hui XiongAuthors Info & Claims

WWW '21: Proceedings of the Web Conference 2021

Pages 1586 - 1597

https://doi.org/10.1145/3442381.3449810

Published: 03 June 2021 Publication History

Abstract

Query and Point-of-Interest (POI) matching, aiming at recommending the most relevant POIs from partial query keywords, has become one of the most essential functions in online navigation and ride-hailing applications. Existing methods for query-POI matching, such as Google Maps and Uber, have a natural focus on measuring the static semantic similarity between contextual information of queries and geographical information of POIs. However, it remains challenging for dynamic and personalized online query-POI matching because of the non-stationary and situational context-dependent query-POI relevance. Moreover, the large volume of online queries requires an adaptive and incremental model training strategy that is efficient and scalable in the online scenario. To this end, in this paper, we propose an Incremental Spatio-Temporal Graph Learning (IncreSTGL) framework for intelligent online query-POI matching. Specifically, we first model dynamic query-POI interactions as microscopic and macroscopic graphs. Then, we propose an incremental graph representation learning module to refine and update query-POI interaction graphs in an online incremental fashion, which includes: (i) a contextual graph attention operation quantifying query-POI correlation based on historical queries under dynamic situational context, (ii) a graph discrimination operation capturing the sequential query-POI relevance drift from a holistic view of personalized preference and social homophily, and (iii) a multi-level temporal attention operation summarizing the temporal variations of query-POI interaction graphs for subsequent query-POI matching. Finally, we introduce a lightweight semantic matching module for online query-POI similarity measurement. To demonstrate the effectiveness and efficiency of the proposed algorithm, we conduct extensive experiments on two real-world datasets collected from a leading online navigation and map service provider in China.

References

[1]

HA Almohamad and Salih O Duffuaa. 1993. A Linear Programming Approach for the Weighted Graph Matching Problem. IEEE Trans. Pattern Anal. Mach. Intell. 15, 5, 522–525.

Digital Library

[2]

Buru Chang, Yonggyu Park, Donghyeon Park, Seongsoon Kim, and Jaewoo Kang. 2018. Content-Aware Hierarchical Point-of-Interest Embedding Model for Successive POI Recommendation. In IJCAI. ijcai.org, 3301–3307.

[3]

Chen Cheng, Haiqin Yang, Michael R Lyu, and Irwin King. 2013. Where You Like to Go Next: Successive Point-of-Interest Recommendation. In IJCAI. IJCAI/AAAI, 2605–2611.

[4]

Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2019. Bert: Pre-training of Deep Bidirectional Transformers for Language Understanding. In NAACL-HLT (1). Association for Computational Linguistics, 4171–4186.

[5]

Shanshan Feng, Xutao Li, Yifeng Zeng, Gao Cong, and Yeow Meng Chee. 2015. Personalized Ranking Metric Embedding for Next New POI Recommendation. In IJCAI. AAAI Press, 2069–2075.

[6]

Chaoyang He, Tian Xie, Yu Rong, Wenbing Huang, Yanfang Li, Junzhou Huang, Xiang Ren, and Cyrus Shahabi. 2019. Bipartite Graph Neural Networks for Efficient Node Representation Learning. arXiv preprint arXiv:1906.11994(2019).

[7]

Sepp Hochreiter and Jürgen Schmidhuber. 1996. LSTM Can Solve Hard Long Time Lag Problems. In NIPS. MIT Press, 473–479.

[8]

Po-Sen Huang, Xiaodong He, Jianfeng Gao, Li Deng, Alex Acero, and Larry Heck. 2013. Learning Deep Structured Semantic Models for Web Search using Clickthrough Data. In CIKM. ACM, 2333–2338.

[9]

Kalervo Järvelin and Jaana Kekäläinen. 2002. Cumulated Gain-Based Evaluation of IR Techniques. ACM Trans. Inf. Syst. 20, 4, 422–446.

Digital Library

[10]

Takeshi Kurashima, Tomoharu Iwata, Takahide Hoshide, Noriko Takaya, and Ko Fujimura. 2013. Geo Topic Model: Joint Modeling of User’s Activity Area and Interests for Location Recommendation. In WSDM. ACM, 375–384.

[11]

Zhihui Li, Feiping Nie, Xiaojun Chang, Yi Yang, Chengqi Zhang, and Nicu Sebe. 2018. Dynamic Affinity Graph Construction for Spectral Clustering using Multiple Features. IEEE Trans. Neural Networks Learn. Syst. 29, 12, 6323–6332.

[12]

Hao Liu, Jindong Han, Yanjie Fu, Jingbo Zhou, Xinjiang Lu, and Hui Xiong. 2020. Multi-Modal Transportation Recommendation with Unified Route Representation Learning. VLDB Endowment 14, 3 (2020), 342–350.

[13]

Hao Liu, Yongxin Tong, Jindong Han, Panpan Zhang, Xinjiang Lu, and Hui Xiong. 2020. Incorporating Multi-Source Urban Data for Personalized and Context-Aware Multi-Modal Transportation Recommendation. IEEE TKDE (2020).

Digital Library

[14]

Shenghao Liu, Bang Wang, Minghua Xu, and Laurence T Yang. 2019. Evolving Graph Construction for Successive Recommendation in Event-Based Social Networks. Future Gener. Comput. Syst. 96, 502–514.

Digital Library

[15]

Giang Hoang Nguyen, John Boaz Lee, Ryan A Rossi, Nesreen K Ahmed, Eunyee Koh, and Sungchul Kim. 2018. Continuous-Time Dynamic Network Embeddings. In WWW (Companion Volume). ACM, 969–976.

[16]

Hamid Palangi, Li Deng, Yelong Shen, Jianfeng Gao, Xiaodong He, Jianshu Chen, Xinying Song, and R Ward. 2014. Semantic Modelling with Long-Short-Term Memory for Information Retrieval. arXiv preprint arXiv:1412.6629.

[17]

John W Ratcliff and David E Metzener. 1988. Pattern-Matching-the Gestalt Approach. Dr Dobbs Journal 13, 7, 46.

[18]

Aravind Sankar, Yanhong Wu, Liang Gou, Wei Zhang, and Hao Yang. 2020. DySAT: Deep Neural Representation Learning on Dynamic Graphs via Self-Attention Networks. In WSDM. ACM, 519–527.

[19]

Chaoming Song, Tal Koren, Pu Wang, and Albert-László Barabási. 2010. Modelling the scaling properties of human mobility. Nature Physics 6, 10 (2010), 818.

[20]

Weiping Song, Zhiping Xiao, Yifan Wang, Laurent Charlin, Ming Zhang, and Jian Tang. 2019. Session-Based Social Recommendation via Dynamic Graph Attention Networks. In WSDM. ACM, 555–563.

[21]

Ke Sun, Tieyun Qian, Tong Chen, Yile Liang, Quoc Viet Hung Nguyen, and Hongzhi Yin. 2020. Where to Go Next: Modeling Long-and Short-Term User Preferences for Point-of-Interest Recommendation. In AAAI. AAAI Press, 214–221.

[22]

Qinyong Wang, Hongzhi Yin, Tong Chen, Zi Huang, Hao Wang, Yanchang Zhao, and Nguyen Quoc Viet Hung. 2020. Next Point-of-Interest Recommendation on Resource-Constrained Mobile Devices. In WWW. ACM / IW3C2, 906–916.

[23]

Qitian Wu, Hengrui Zhang, Xiaofeng Gao, Peng He, Paul Weng, Han Gao, and Guihai Chen. 2019. Dual Graph Attention Networks for Deep Latent Representation of Multifaceted Social Effects in Recommender Systems. In WWW. ACM, 2091–2102.

Digital Library

[24]

Xiangye Xiao, Qiong Luo, Zhisheng Li, Xing Xie, and Wei-Ying Ma. 2010. A Large-Scale Study on Map Search Logs. ACM Trans. Web 4, 3, 8:1–8:33.

Digital Library

[25]

Xiwang Yang, Harald Steck, Yang Guo, and Yong Liu. 2012. On Top-k Recommendation using Social Networks. In RecSys. ACM, 67–74.

[26]

Yang Yang, Da-Wei Zhou, De-Chuan Zhan, Hui Xiong, and Yuan Jiang. 2019. Adaptive Deep Models for Incremental Learning: Considering Capacity Scalability and Sustainability. In KDD. ACM, 74–82.

[27]

Haochao Ying, Fuzhen Zhuang, Fuzheng Zhang, Yanchi Liu, Guandong Xu, Xing Xie, Hui Xiong, and Jian Wu. 2018. Sequential Recommender System based on Hierarchical Attention Network. In IJCAI. ijcai.org, 3926–3932.

[28]

Fuqiang Yu, Lizhen Cui, Wei Guo, Xudong Lu, Qingzhong Li, and Hua Lu. 2020. A Category-Aware Deep Model for Successive POI Recommendation on Sparse Check-in Data. In WWW. ACM / IW3C2, 1264–1274.

[29]

Quan Yuan, Gao Cong, Zongyang Ma, Aixin Sun, and Nadia Magnenat Thalmann. 2013. Time-Aware Point-of-Interest Recommendation. In SIGIR. ACM, 363–372.

[30]

Quan Yuan, Gao Cong, and Aixin Sun. 2014. Graph-Based Point-of-Interest Recommendation with Geographical and Temporal Influences. In CIKM. ACM, 659–668.

[31]

Zixuan Yuan, Hao Liu, Yanchi Liu, Denghui Zhang, Fei Yi, Nengjun Zhu, and Hui Xiong. 2020. Spatio-Temporal Dual Graph Attention Network for Query-POI Matching. In SIGIR. ACM, 629–638.

[32]

Weijia Zhang, Hao Liu, Yanchi Liu, Jingbo Zhou, and Hui Xiong. 2020. Semi-Supervised Hierarchical Recurrent Graph Neural Network for City-Wide Parking Availability Prediction. In AAAI, Vol. 34. 1186–1193.

[33]

Ji Zhao, Dan Peng, Chuhan Wu, Huan Chen, Meiyu Yu, Wanji Zheng, Li Ma, Hua Chai, Jieping Ye, and Xiaohu Qie. 2019. Incorporating Semantic Similarity with Geographic Correlation for Query-POI Relevance Learning. In AAAI. AAAI Press, 1270–1277.

[34]

Ji Zhao, Meiyu Yu, Huan Chen, Boning Li, Lingyu Zhang, Qi Song, Li Ma, Hua Chai, and Jieping Ye. 2019. POI Semantic Model with a Deep Convolutional Structure. arXiv preprint arXiv:1903.07279.

[35]

Pengpeng Zhao, Anjing Luo, Yanchi Liu, Fuzhen Zhuang, Jiajie Xu, Zhixu Li, Victor S Sheng, and Xiaofang Zhou. 2019. Where to Go Next: A Spatio-Temporal Gated Network for Next POI Recommendation. In AAAI. AAAI Press, 5877–5884.

[36]

Fan Zhou, Ruiyang Yin, Kunpeng Zhang, Goce Trajcevski, Ting Zhong, and Jin Wu. 2019. Adversarial Point-of-Interest Recommendation. In WWW. ACM, 3462–34618.

Cited By

Tang HWu SSun XZeng JXu GLi Q(2024)TCGC: Temporal Collaboration-Aware Graph Co-Evolution Learning for Dynamic RecommendationACM Transactions on Information Systems10.1145/368747043:1(1-27)Online publication date: 27-Aug-2024
https://dl.acm.org/doi/10.1145/3687470
Zhang WHan JXu ZNi HLiu HXiong HBaeza-Yates RBonchi F(2024)Urban Foundation Models: A SurveyProceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining10.1145/3637528.3671453(6633-6643)Online publication date: 25-Aug-2024
https://dl.acm.org/doi/10.1145/3637528.3671453
Yang LLuo ZZhang STeng FLi T(2024)Continual Learning for Smart City: A SurveyIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2024.344712336:12(7805-7824)Online publication date: Dec-2024
https://doi.org/10.1109/TKDE.2024.3447123
Show More Cited By

Recommendations

Spatio-Temporal Dual Graph Attention Network for Query-POI Matching
SIGIR '20: Proceedings of the 43rd International ACM SIGIR Conference on Research and Development in Information Retrieval

In location-based services, such as navigation and ride-hailing, it is an essential function to match a query with Point-of-Interests (POIs) for efficient destination retrieval. Indeed, due to the space limit and real-time requirement, such services ...
Incremental graph pattern matching

Graph pattern matching is commonly used in a variety of emerging applications such as social network analysis. These applications highlight the need for studying the following two issues. First, graph pattern matching is traditionally defined in terms ...
Incremental graph pattern matching
SIGMOD '11: Proceedings of the 2011 ACM SIGMOD International Conference on Management of data

Graph pattern matching has become a routine process in emerging applications such as social networks. In practice a data graph is typically large, and is frequently updated with small changes. It is often prohibitively expensive to recompute matches ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

WWW '21: Proceedings of the Web Conference 2021

April 2021

4054 pages

ISBN:9781450383127

DOI:10.1145/3442381

Editors:
Jure Leskovec
Stanford
,
Marko Grobelnik
Jožef Stefan Institute
,
Marc Najork
Google
,
Jie Tang
Tsinghua University
,
Leila Zia
Wikimedia Foundation

Copyright © 2021 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGWEB: ACM Special Interest Group on Hypertext, Hypermedia, and Web

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 03 June 2021

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed limited

Conference

WWW '21

Sponsor:

SIGWEB

WWW '21: The Web Conference 2021

April 19 - 23, 2021

Ljubljana, Slovenia

Acceptance Rates

Overall Acceptance Rate 1,899 of 8,196 submissions, 23%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

8
Total Citations
View Citations
601
Total Downloads

Downloads (Last 12 months)57
Downloads (Last 6 weeks)2

Reflects downloads up to 01 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Tang HWu SSun XZeng JXu GLi Q(2024)TCGC: Temporal Collaboration-Aware Graph Co-Evolution Learning for Dynamic RecommendationACM Transactions on Information Systems10.1145/368747043:1(1-27)Online publication date: 27-Aug-2024
https://dl.acm.org/doi/10.1145/3687470
Zhang WHan JXu ZNi HLiu HXiong HBaeza-Yates RBonchi F(2024)Urban Foundation Models: A SurveyProceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining10.1145/3637528.3671453(6633-6643)Online publication date: 25-Aug-2024
https://dl.acm.org/doi/10.1145/3637528.3671453
Yang LLuo ZZhang STeng FLi T(2024)Continual Learning for Smart City: A SurveyIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2024.344712336:12(7805-7824)Online publication date: Dec-2024
https://doi.org/10.1109/TKDE.2024.3447123
Ning YLiu HWang HZeng ZXiong HOh ANaumann TGloberson ASaenko KHardt MLevine S(2023)UUKGProceedings of the 37th International Conference on Neural Information Processing Systems10.5555/3666122.3668849(62442-62456)Online publication date: 10-Dec-2023
https://dl.acm.org/doi/10.5555/3666122.3668849
Balsebre PYao DCong GHuang WHai Z(2023)Mining Geospatial Relationships from TextProceedings of the ACM on Management of Data10.1145/35889471:1(1-26)Online publication date: 30-May-2023
https://dl.acm.org/doi/10.1145/3588947
Liu HJiang WLiu SChen XSingh ASun YAkoglu LGunopulos DYan XKumar ROzcan FYe J(2023)Uncertainty-Aware Probabilistic Travel Time Prediction for On-Demand Ride-Hailing at DiDiProceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining10.1145/3580305.3599925(4516-4526)Online publication date: 6-Aug-2023
https://dl.acm.org/doi/10.1145/3580305.3599925
Chen HAi QWu ZWang ZLiu YZhang MMa SHu JTan NChai HChen HDuh WHuang HKato MMothe JPoblete B(2023)Behavior Modeling for Point of Interest SearchProceedings of the 46th International ACM SIGIR Conference on Research and Development in Information Retrieval10.1145/3539618.3591955(1843-1847)Online publication date: 19-Jul-2023
https://dl.acm.org/doi/10.1145/3539618.3591955
Wang YYuan LChen ZZhang WLin XLiu Q(2023)Towards Efficient Shortest Path Counting on Billion-Scale Graphs2023 IEEE 39th International Conference on Data Engineering (ICDE)10.1109/ICDE55515.2023.00198(2579-2592)Online publication date: Apr-2023
https://doi.org/10.1109/ICDE55515.2023.00198

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

HTML Format

View this article in HTML Format.

Media

Figures

Other

Tables

View Table of Contents