Multi-Graph Fusion Networks for Urban Region Embedding

Learning the embeddings for urban regions from human mobility data can reveal the functionality of regions, and then enables the correlated but distinct tasks such as crime prediction. Human mobility data contains rich but abundant information, which yields to the comprehensive region embeddings for cross domain tasks. In this paper, we propose multi-graph fusion networks (MGFN) to enable the cross domain prediction tasks. First, we integrate the graphs with spatio-temporal similarity as mobility patterns through a mobility graph fusion module. Then, in the mobility pattern joint learning module, we design the multi-level cross-attention mechanism to learn the comprehensive embeddings from multiple mobility patterns based on intra-pattern and inter-pattern messages. Finally, we conduct extensive experiments on real-world urban datasets. Experimental results demonstrate that the proposed MGFN outperforms the state-of-the-art methods by up to 12.35% improvement.


Introduction
Revealing urban region embedding aims to learn quantitative representations of regions from multi-sourced data, such as Point-of-Interests (POI), check-in, and human mobility [Wang and Li, 2017]. Human mobility data reflects the human interactions and cooperation, and thus can be used to conduct distinct tasks such as epidemic [Wu et al., 2021], economics [Xu et al., 2020], crime [Xia et al., 2021] prediction, etc.
The cross-domain downstream tasks such as crime prediction and check-in prediction, are used to verify the effectiveness of region embeddings. Existing studies Wang and Li, 2017;Yao et al., 2018] taking all detailed timeseries mobility records as input, could merely learn a specific representation (e.g., change of traffic flows), rather than generalized urban region embeddings. * These authors contributed equally to this work † Corresponding author: fanxiaoliang@xmu.edu.cn  Figure 1: A motivating example. The complexity of mobility patterns depends on both urban periodicity and regional functionality distribution. For two regions (A is a residential area, and B is a office area), there could be two distinct patterns (i.e., variation, similarity).
Human mobility data contains both abundant information and complex patterns [Dang et al., 2022], which yields to the comprehensive region embeddings for cross domain tasks. For example, Figure 1 (left) shows two repeated patterns, which can be integrated as Pattern 1 (morning peak) and Pattern 2 (weekend) respectively. Figure 1 (right) shows the complexity of mobility patterns that there are two distinct patterns (i.e., variation and similarity). Measuring a generalized region embeddings from abundant human mobility data is challenging: Challenge 1: How to process the fine-grained mobility data to learn a generalized embedding? In our considered scenario, learning from abundant human mobility data may only attain the change of mobility flows, rather than a generalized embedding.
Solution 1: Mobility graph fusion. To attain an effective and generalized embedding from abundant human mobility data, we first approach regions as interactive and interdependent nodes by constructing the human mobility data as mobility multi-graph. Then, we aggregate mobility graphs as selected mobility patterns according to the spatio-temporal distance between any two mobility graphs.
Challenge 2: How to jointly learn from mobility patterns? Training a separate pattern mining model on each of them may not capture comprehensive representation of regional characteristics.
Solution 2: Mobility Pattern Joint Learning. The constructed mobility graphs possess regularized characteristics, which are fully connected, directed, and weighted with multiple edges (i.e., multi-graph). Different from previous graph representation models [Zhang et al., 2020], we take advantage of above characteristics by designing two modules: (1) Intra-pattern message passing, which utilizes structural information inside each graph to learn a local embedding; and (2) Inter-pattern message cross attention, which conducts attention mechanism among different graphs to jointly learn comprehensive region embeddings.
The major contributions of this paper are: • We study the urban region representation problem on fine-grained human mobility data, and propose a mobility graph fusion module with spatio-temporal dependencies where redundant graphs are integrated as patterns. • We propose a mobility pattern joint learning module, which learns the region embedding from intra-pattern message and inter-pattern message simultaneously in a new manner, with the hope that the cross-graph information can mutually enhance each other. • Extensive experimental results show that our mobility graph fusion method can effectively uncover the complex mobility patterns. And our method outperforms state-of-the-art baselines up to 13.11% in crime and check-in prediction tasks in terms of various metrics.

Problem Statement
We provide necessary preliminary concepts in this work, and formalize the problem of urban region embedding. Definition 1 (Mobility Graph). The mobility graph at the time step t is defined as a directed and weighted graph G t = (V, E t ), where V denotes the node set with node v i ∈ V representing region v i , and E t denotes the edge set with edge e t ij = (v i , v j , ω t ij ) ∈ E t representing the number of people ω ij move from urban region v i to v j at time t. Definition 2 (Mobility Multi-graph). It is defined as a directed and weighted multi-graph G = ∪ T −1 t=0 {G t = (V, E t )}, where G t is a mobility graph at time t, and V denotes the node set that corresponds to regions, and E t denotes the edge set that corresponds to mobility condition at time t. Definition 3 (Mobility Pattern). The mobility patterns G = {G 0 , G 1 , ..., G N −1 } are the result of fusing similar mobility multi-graph. A pattern G k is also a directed and weighted graph with the same node set V as mobility multi-graph. Definition 4 (Urban Region Embedding). Given mobility multi-graph G, the goal of urban region embedding is to learn a mapping function φ : v i → R d to generate low dimensional embeddingĤ ∈ R |V |×d of each region v i ∈ V , where d represents the dimension of urban region embeddings.

Methodology
In this section, we first introduce the mobility graph fusion module, in which we propose a novel mobility graph distance to measure the similarity between different mobility graphs. Then, we present an effective mobility pattern joint learning module, which contains intra-pattern message passing and inter-pattern message cross attention to capture comprehensive regional characterise by mobility patterns.

MGD Calculation
Agglomerative Clustering Figure 2: MGFN Framework. The architecture transforms human mobility patterns into representation abilities for downstream tasks (e.g., crime, check-in prediction). Our framework consists of two modules: 1) Mobility Graph Fusion module where time-series multi-graph are fused by a Mobility Graph Distance (MGD) measurement method; and 2) Mobility Pattern Joint Learning module (detailed in Figure 3) which learns the region embedding by both intra-pattern message and inter-pattern message.

Mobility Graph Fusion
Human mobility reveals the functions and properties of urban regions [Wang and Li, 2017]. Our intuition is that mobility patterns are able to describe the urban region functionality thus in favour of learning the generalized representation. For example, estimate whether a region is work area or residential area according to the human mobility direction during the morning peak hours (i.e., 7-9 a.m.). Therefore, instead of learning how human mobility changes, we model the problem as time-series mobility multi-graph fusion (MGF) to extract the mobility patterns. First, we define mobility graph distance (MGD) to calculate the distance between mobility graphs, and apply clustering methods with MGD to cluster similar mobility graphs. Second, in each cluster, we aggregate edges in all mobility graphs to form a mobility pattern.

Spatial Structure Distance on Mobility Graph
Data with similar mean and variance may have higher similarity. Specifically, for a mobility graph G, we assume that the weight w of edge e = (u, v, w) is sampled from a Gaussian distribution, and calculate its mean µ G and variance σ G : Then, the mean distance and variance distance between the mobility graph G a and G b are expressed as: It is not sufficient to only compare the mean and variance. For example, The mean and variance of the morning and evening peak hours are similar, but their destinations are different (working and residential areas, respectively). Specifically, to pay attention to flow imbalance of two regions, we first propose the unidirectional flow distance: where U niF Then, to highlight the high-weight edges in mobility graph G t , we encode G t as a spatial structure label matrix E t , where each element E t ij represents whether the weight ω t ij of edge e t ij in G t is large enough: where µ ij = 1 T T t=1 µ t ij represents the mean value of edge weight between node v i and v j over the time series.
Afterwards, the spatial structure encoding distance between mobility graphs G a and G b is defined as follows: where ⊕ is the xor operation.

Temporal Aggregation with Mobility Graph Distance
After calculating the distances between mobility graphs, considering mobility graphs with close temporal distance are similar, we take temporal similarity into account. We define mobility graph distance (MGD) between mobility graphs G a and G b as the sum of above distance weighted by the temporal similarity with non-linearity, given as follows: where c i is the weight of i-th distance, D i could be D mean , D var , D unif , D ss , M(·) denotes the normalization function such as MinMaxScaler, Z(·) is an activation function. ∆t denotes the time interval between G a and G b . Finally, we calculate the distance between mobility graphs through MGD, and use the clustering method (i.e., hierarchical cluster) to aggregate mobility graphs with different patterns thus to generate mobility patterns G.

Mobility Pattern Joint Learning
In order to learn the underlying information of urban regions from mobility patterns, we present a mobility pattern joint learning module as shown in Figure 3. The framework mainly consists of two parts: intra-pattern message passing and interpattern message cross attention. In the first part, the region hidden representations are updated by intra-pattern message propagating and aggregating in each mobility pattern thus extracting the spatial correlations between regions. In the second part, the cross-attention mechanism is used to integrate the inter-pattern message between the different mobility patterns for each region. Comprehensive embeddings output by two parts with residual connections [He et al., 2016] are integrated by a fully connected layer to generate the final region embeddings.

Inter-Pattern Message Cross Attention
Inter-pattern message

Mobility Patterns
Figure 3: The architecture of mobility pattern joint learning module (left) mainly consists: 1) intra-pattern massage passing (upper right), 2) inter-pattern message cross attention (down right). The former aggregates intra-pattern message to generate region embeddings in N patterns. The latter obtains a fused region embeddings by attention mechanism using inter-pattern message.

Intra-Pattern Message Passing
The property of an urban region is affected by other regions with different impacts due to the spatial correlations. We assume that such impact is highly correlated to the human mobility condition of a region. To capture the spatial correlations, inspired by [Gilmer et al., 2017], we design a intrapattern message passing layer to propagate the inner flow messages between different regions in each mobility pattern.
This part takes mobility patterns G as input. We initialize the 0 th -layer hidden representations of regions v i in mobility pattern G k as input region features x k vi , i.e.: (0) h k vi = x k vi . Considering the mobility flow from region v j to region v i , inspired by [Veličković et al., 2017], we compute the message sent along the mobility flow edge v j → v i by self-attention mechanism. The message function is defined as follows: where ·, · is inner product, W q p and W k p are two trainable projection matrices, and N (v i ) is neighbor region set of v i . Here, the message from region v j to v i is also attention score. Afterwards, region v i aggregates the messages sent by its neighbor regions N (v i ), and updates its hidden representation by a weighed sum from N (v i ), given as follows.
where (l) W v p is a learnable projection matrix in l th layer.
Here, as the mobility pattern is a directed complete graph, the neighbors of each region are all the regions.
To stabilize the learning process and learn information at different conceptual levels, we extend the self-attention mechanism to be multi-head ones [Vaswani et al., 2017]. Specifically, we concatenate F parallel attention message functions with different learnable projections: where || represents concatenation operation, and (f ) m k vivj represents the attention score calculated by the message function in the f th head attention.
Taking the importance of mobility directions and the difference between in-flow and out-flow mobility for a region into account, we divide each mobility pattern G k into two parts: source mobility pattern G s k and target mobility pattern G t k . Here, we regard the out-flow and in-flow mobility as node features of source intra-pattern X s k and target intra-pattern X t k , and apply intra-message passing layer in these two type of patterns, respectively, where X s k = X t k . To fuse these two region representations, we project the concatenation of them to generate hidden representation of v i : } extracting spatial dependency of N mobility patterns are generated by stacking L intra-pattern message passing layers.

Inter-Pattern Message Cross Attention
Intra-pattern message passing provides a robust mechanism for capturing the spatial correlations between regions in each mobility pattern. For learning the cross interactions between different mobility patterns for a region, we allow region to interact across mobility patterns via a self-attention mechanism [Vaswani et al., 2017].
Considering the region v i in mobility pattern G a and G b , let the node features in G a and G b are h a vi and h b vi , respectively. Then, for every such pair, we compute the correlation between G a and G b using attention as follows: where W q c and W k c are two trainable projection matrices, and the attention score α vi ab reveals how G a attends to the features of region v i of G b . Afterwards, we compute an interpattern message for the region v i of mobility pattern G a by a weighed sum, where the multi-head attention is applied again: where W v c is a learnable projection matrix. Finally, the fused region embedding of v i is updated by aggregating the inter-pattern message with mean aggregator: Objective Function With the residual connection of intra-pattern message passing, we use a fully connected layer as an output layer to obtain the final region embeddingsĥ vi : Following [Wang and Li, 2017], we use region embeddings to estimate the distribution of mobility, and learn the embedding by minimizing the difference between the true distribution and the estimated distribution. Given the source v i , we calculate the transition probability of destination v j : Then, given the region embeddingĥ vi ,ĥ vj for region v i , v j , we estimate the transition probability: Finally, the objective function can expressed as:

Evaluation
This section aims to answer the following research questions: RQ1 How is the performance of out MGFN as compared to various state-of-the-art methods? RQ2 How do different components (e.g., mobility graph fusion, mobility pattern joint learning) affect the results? RQ3 Can the proposed mobility graph fusion module really discover mobility patterns? What are its advantages compared with other methods? RQ4 Why did other models perform worse than ours? Is it true that the other methods learned how traffic flow changes? (as we assume in Section 1)  Parameter Settings Following [Zhang et al., 2020], the dimension of region embeddings d is 96. In mobility graph fusion module, the weight c i in MGD is set as 1, and the number of mobility patterns N is set as 7. In mobility pattern joint learning module, the number of layers L is set as 1.

Performance Comparison (RQ1)
For regression tasks (i.e., crime, check-in), we apply the Lasso regression [Tibshirani, 1996] with metrics of Mean Absolute Error (MAE), Root Mean Square Error (RMSE) and coefficient of determination (R 2 ). For the clustering task (i.e., land usage classification), we use K-means to cluster region embeddings with Normalized Mutual Information (NMI) and Adjusted Rand Index (ARI) with settings in [Yao et al., 2018]. Table 1 shows the results of crime prediction, land usage classification and check-in count prediction. We observe that: (1) urban region embedding approaches outperform traditional graph embedding methods, and graph modeling methods (i.e., MG-FN, MVURE) generally perform better than HDGE, ZE-Mob and MV-PN, indicating the spatial dependency between regions is a necessity for urban region embedding; and (2) our MGFN with only human mobility data outperforms the second best model MVURE with multisourced data (POI, check-in, mobility, etc.) and achieves up to 13.11% improvement in terms of R 2 in the check-in prediction task. It is noted that multi-sourced data used in MVURE is always unreachable or accompanied by many noise data in real urban application.   Figure 5: Comparison of clustering results using different distances. The x-axis represents hour of a day, and the y-axis is the day of a month. Each sub-figure represents the result of a measurement, respectively. Each color represents a certain pattern corresponding to the law of human mobility. Compared with other measurements, only MGD could effectively identify important patterns such as morning peaks (red block, from 7 to 9 am for week-days), weekends late night (purple block from 12 pm to 2 am for week-ends), etc.

Model Ablation Study (RQ2)
To further investigate the effect of each component in our model, we compare MGFN with its three variants by removing multi graph fusion module, intra-pattern message passing and inter-pattern message cross attention in mobility pattern joint learning module from our method, which are named as MGFN-NF, respectively. Figure 4 shows the MAE, ARI and RMSE results of MGFN and its variants in crime prediction, land usage classification and check-in prediction tasks respectively. We observe that MGFN performs better than MGFN-NF, demonstrating that the MGF module effectively eases the redundant temporal information for learning more general representations of urban regions. Moreover, MGFN consistently outperforms MGFN-NP and MGFN-NC, which indicates the effectiveness of intra message passing and aggregating between nodes in each mobility pattern and inter messages fusion between mobility patterns in modeling the complex spatial correlations.

Graph Similarity Measurement (RQ3)
To intuitively evaluate the performance of the proposed Mobility Graph Fusion module (Section 3.1), we visualize the mobility patterns extracted by our multi-graph distance (MGD) measurement compared with three measures in Section 3.1 including Mean, Std, and Uniflow using hierarchical  clustering. Specifically, in Figure 5, a certain color represents a specific pattern corresponding to the law of human mobility. We observe that different from other measures, our MGD ( Figure 5.d) is able to distinguish patterns of both morning/evening peaks and working days/weekends effectively, due to our integrated considerations with spatio-temporal information. We argue that this improvement is beneficial to enabling the cross-domain prediction (i.e., from traffic prediction to crime prediction) by uncovering the dynamic correlations contained in urban regional functionality.

Generalization Ability of MGFN (RQ4)
To show the generalization ability of our method, we compare our MGFN with other three methods on both supervised task (i.e., mobility prediction) and cross-domain task (i.e., crime prediction) in Figure 6. Other methods perform poorly on cross-domain tasks because they learn how traffic changes rather than a generalized region representation. Moreover, after removed MGF, the generalization performance is reduced by about 20%, which shows the importance of MGF.

Related Works
Graph Representation Learning Graph embedding aims to learn a low-dimensional vector by mapping the characteristics of nodes to a low-dimensional vector space so that the proximities of nodes can be well preserved [Cui et al., 2018]. Early works devote to learn the shallow representations by graph factorization approaches [Belkin and Niyogi, 2001] relying on spectral embedding from graph Laplacian and skip-gram based methods [Perozzi et al., 2014;Grover and Leskovec, 2016;Tang et al., 2015] learned by random walk objectives. More recently, graph neural networks (GNNs) have become a widely used tool for graph embedding [Veličković et al., 2017;Gilmer et al., 2017].
Region Representation Learning Several strategies have been studied to learn the representation of regions. The first strategy learns embeddings from time-series human mobility data. HDGE [Wang and Li, 2017] uses fine-grained human mobility to construct flow graph, and learn the region embedding at different times. ZE-mob [Yao et al., 2018] regards the region as a word and the mobility event as context, and learn the embedding via a word embedding method. The second strategy learns embeddings from multi-view cross-geotype(region and other spatio-temporal items) correlations.  take into account both intra-region structural information and inter-region spatial auto-correlations. Zhang et al.
[2020] use a cross-view information sharing method to learn comprehensive region embeddings.

Conclusion
In this paper, we focus on learning generalized embeddings to enable cross domain urban computing tasks. We proposed: (1) a novel mobility graph fusion method where redundant graphs are integrated as patterns; and (2) a novel mobility pattern joint learning method to enable the cross graph embeddings that mutually enhance each other and provide more effective representation for downstream tasks. Extensive experiments on real-world mobility data show the proposed MGFN outperforms all baseline methods. Besides, in-depth analysis reveals insightful observations, e.g., Late nights and evenings on weekends show a different pattern from workdays. In future, we will extend our framework to other downstream tasks (e.g., house price prediction).