[20240621_LabSeminar_Huy]Spatial-Temporal Interplay in Human Mobility: A Hierarchical Reinforcement Learning Approach with Hypergraph Representation.pptx

Spatial-Temporal Interplay in Human Mobility: A Hierarchical Reinforcement Learning Approach with Hypergraph Representation

1. Quang-Huy Tran Network Science Lab Dept. of Artificial Intelligence The Catholic University of Korea E-mail: [email protected] 2024-06-21 Spatial-Temporal Interplay in Human Mobility: A Hierarchical Reinforcement Learning Approach with Hypergraph Representation Zhaofan Zhang et al. AAAI-2024: Proceedings of the Thirty-Eight Conference on Artificial Intelligence

2. OUTLINE MOTIVATION INTRODUCTION METHODOLOGY EXPERIMENT & RESULT CONCLUSION

3. MOTIVATION Human mobility: patterns and behaviors associated with how and where individuals move or travel within physical spaces . Offer valuable insights with applications spanning transportation, urban planning, public health, business, etc. Overview From a decision-making standpoint, the selection of the next-visit site by humans : influenced by the interplay between spatial and temporal: individual needs and preferences.

4. MOTIVATION Overview: Previous works and Limitation Existing works rely on two main approaches: Temporal oriented approaches: emphasize the time dimension, modeling preferences that evolve over time, while incorporating spatial context as a secondary element. Spatial-oriented strategies: prioritize the spatial dimension, preserving spatial autocorrelation through graph representation learning and viewing the interplay as temporal graph dynamics. Common limitation of these methods. P redominant reliance on either the spatial or temporal dimension. potentially oversimplifying the intricate interactions between the two in decision-making.

5. INTRODUCTION propose “Spatial-Temporal Induced Hierarchical Reinforcement Learning” (STI-HRL) framework formulates the human mobility as a two layered decision-making process with a spatial-temporal Decoupling-Integration schema. Low-level: decouples spatial-temporal interplay with a spatial agen tand a temporal agent to focus on each dimension. High-level: integrates the insights from two agents in the low-level to make the final decision on mobility To facilitate STI-HRL with a proper environment, propose a Mobility Hypergraph to organize the multi-aspect semantics of mobility . hyperedge embeddings serve as the state to support the decision-making process.

6. METHODOLOGY Main Architecture - LSTF 3 main components: Hypergraph Representation. Hierarchical RL environment.

7. METHODOLOGY Graph Construction and Problem Definition Hetegeneous Mobility Hypergraph V and E denote the vertex set and hyperedge set. Vertices: union of four semantic channels: POI channel, denoted as P; POI category channel, denoted as C; zone channel, denoted Z; and time channel, denoted as T. Hyperedge: connects two or more vertices. 4 types: POI hyperedge: linking all POI vertices a user has visited. Zone hyperedge: connecting all the zone vertices visited by a user.   Formulate human mobility as MDP (Markov Decision Process) - (S, A, , R, E) : States S , Actions A, Transition Probabilities , Rewards R, Environments E.   Time hyperedge: associating all the time vertices visited by a user. event hyperedge, which interlinks the POI, category, zone, and time vertices of a specific check-in event

8. METHODOLOGY Hypergraph Embedding for State Representation Vertex embedding: attention . Hyperedge embedding : homogeneous hyperedges aggregate all the vertex embedding within the hyperedge to represent the hyperedge embedding. aggregate information from hyperedges on other channels that are interlinked by the same event hyperedge to update hyperedge embedding .  

9. METHODOLOGY Spatial-Temporal Induced Hierarchical Reinforcement Learning Low-level : Decoupling Spatial-Temporal Interplay seeks to distinguish users’ preferences within the spatial and temporal dimensions. a spatial agent and a temporal agent: discern human mobility decision patterns within these dimensions. State : represents a specific spatial temporal context derived from historical records Spatial agent: aims to capture the preferences and interactions on spatial factors. Concatenate associated POI hyperedge embeddings and zone hyperedge embeddings Temporal agent: concatenate the associated POI hyperedge embeddings and time hyperedge embeddings

10. METHODOLOGY Spatial-Temporal Induced Hierarchical Reinforcement Learning Low-level : Decoupling Spatial-Temporal Interplay Reward : reward received after transitioning from state s to state s′ due to action a. Spatial agent: evaluate decision-making performance from POI-POI geographic distance (eciprocal of the geographic distance between the actual and predicted), POI-POI category similarity (cosine similarity between predicted and actual), POI-POI relative ranking (ranking order of the actual visited POI in the predicted list) Temporal agent: measurement , Kullback – Leibler (KL) divergence between the visiting frequency distribution of the actual and predicted POIs across the time span.  

11. METHODOLOGY Spatial-Temporal Induced Hierarchical Reinforcement Learning High -level : Integrative Synthesis of Space-Time Dynamics State : encapsulate the interplay of spatial and temporal dynamics for user u at time t Reward : calibrate the interplay between spatial and temporal realms by amalgamating the rewards from the low-level agents. employs a dedicated agent to integrate insights from the low-level agents. Synthesizing spatial and temporal considerations in interaction with the Mobility Hypergraph to produce the final human mobility decision. where and denote the weights for spatial and temporal rewards  

12. METHODOLOGY Spatial-Temporal Induced Hierarchical Reinforcement Learning Policy Learning : Workflow : In low-level process, spatial agent and temporal agent use embedding state to predict next location and visit event occur. states transit: High-level integrates and synthesizes a holistic representation of user behavior and transitions Optimization : primary objective is to maximize the expected rewards. agent policies are refined Where represents spatial S, temporal T, or high-level integration I. is result from MLP.  

13. METHODOLOGY Spatial-Temporal Induced Hierarchical Reinforcement Learning Policy Learning : Policy Integration and Adaptation : high-level agent seamlessly integrates policies from the low-level agents Recognizing the ever-evolving nature of spatial-temporal dynamics, the high-level agent dynamically adjusts β based on the relative performance of the integrated policies where represents a specific learning rate for weight adjustments   where is the weight to determine the balance between spatial and temporal inputs  

14. EXPERIMENT AND RESULT EXPERIMENT SETTINGs Dataset: New York (NYC) and Tokyo (TKY): user ID, POI ID, category, GPS coordinates, and the timestamp of each check-in event. Baselines: ST-RNN[1], DeepMove[2] (Feng et al. 2018), LSTPM [3], HST-LSTM [4], STAN [5], LBSN2Vec [6], FPMC[7] , KNN Bandit[8] [1] Liu, Q., Wu, S., Wang, L., & Tan, T. (2016, February). Predicting the next location: A recurrent model with spatial and temporal contexts. In Proceedings of the AAAI conference on artificial intelligence (Vol. 30, No. 1). [2] Feng, J., Li, Y., Zhang, C., Sun, F., Meng, F., Guo, A., & Jin, D. (2018, April). Deepmove : Predicting human mobility with attentional recurrent networks. In Proceedings of the 2018 world wide web conference (pp. 1459-1468). [3] Sun, K., Qian, T., Chen, T., Liang, Y., Nguyen, Q. V. H., & Yin, H. (2020, April). Where to go next: Modeling long-and short-term user preferences for point-of-interest recommendation. In Proceedings of the AAAI conference on artificial intelligence (Vol. 34, No. 01, pp. 214-221). [4] Kong, D., & Wu, F. (2018, July). HST-LSTM: A hierarchical spatial-temporal long-short term memory network for location prediction. In IJCAI (Vol. 18, No. 7, pp. 2341-2347). [5] Luo, Y., Liu, Q., & Liu, Z. (2021, April). Stan: Spatio -temporal attention network for next location recommendation. In Proceedings of the web conference 2021 (pp. 2177-2185). [6] Yang, D., Qu, B., Yang, J., & Cudre-Mauroux , P. (2019, May). Revisiting user mobility and social relationships in lbsns : a hypergraph embedding approach. In The world wide web conference (pp. 2147-2157). [7] Rendle , S., Freudenthaler , C., & Schmidt- Thieme , L. (2010, April). Factorizing personalized markov chains for next-basket recommendation. In Proceedings of the 19th international conference on World wide web (pp. 811-820). [8] Sanz-Cruzado, J., Castells, P., & López, E. (2019, September). A simple multi-armed nearest-neighbor bandit for interactive recommendation. In Proceedings of the 13th ACM conference on recommender systems (pp. 358-362). Measurement : Recall, F1. Mean Reciprocal Rank (MRR). Normalized Discounted Cumulative Gain (NDCG): compares rankings to an ideal order where all relevant items are at the top of the list.

15. EXPERIMENT AND RESULT RESULT – Overall Perfor mance

16. EXPERIMENT AND RESULT Result: Visualization

17. CONCLUSION Address the challenge of capturing the spatial-temporal interplay in human mobility. Frame as a two-tiered decision-making task: Low level focuses on disentangling spatial and temporal preference. high-level synthesizes these insights to produce a comprehensive mobility decision. leverages a hierarchical reinforcement learning framework. To effectively encapsulate the multifaceted semantics of spatial-temporal dynamics: introduce a Mobility Hypergraph to structure the mobility records. utilizing hyperedge embeddings as states for policy learning .