Multi-Graph Fusion Networks for Urban Region Embedding

1 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 [Du et al., 2019; 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

Human mobility data contains both abundant information and complex patterns [Hou and Li, 2016], 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 frommobility 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 12.35% in crime and check-in prediction tasks in terms of various metrics.

2 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 Gt = (V, Et), where V denotes the node set with node vi ∈ V representing region vi, and Et denotes the edge set with edge etij = (vi, vj, ωt ij ) ∈ Et representing the number of people ωij move from urban region vi to vj at time t.

Definition 2 (Mobility Multi-graph). It is defined as a directed and weighted multi-graph G = ∪T -1 t=0 {Gt = (V,Et)}, where Gt is a mobility graph at time t, and V denotes the node set that corresponds to regions, and Et denotes the edge set that corresponds to mobility condition at time t.

Definition 3 (Mobility Pattern). The mobility patterns G = {G0, G1, ..., GN-1} are the result of fusing similar mobility multi-graph. A pattern Gk 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 ϕ : vi → Rd to generate low dimensional embedding ˆH ∈ R|V |×d of each region vi ∈ V , where d represents the dimension of urban region embeddings.

3 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. Figure 2 shows the overall architecture of our multi-graph fusion network.

3.1 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 Ga and Gb 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 UniF(Gt) = ∑vi∈V ∑vj∈V ∣∣ωt ij - ωt ji ∣∣ is the unidirectional flow index of the graph, and Dunif(Ga,Gb) = Dunif (Gb, Ga).

Then, to highlight the high-weight edges in mobility graph Gt, we encode Gt as a spatial structure label matrix E t , where each element E t ij represents whether the weight ωt ij of edge etij in Gt is large enough:

where µij = 1 T ∑Tt=1 µtij represents the mean value of edge weight between node vi and vj over the time series.

Afterwards, the spatial structure encoding distance between mobility graphs Ga and Gb 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 Ga and Gb as the sum of above distance weighted by the temporal similarity with non-linearity, given as follows:

where ci is the weight of i-th distance, Di could be Dmean,Dvar,Dunif ,Dss, M(·) denotes the normalization function such as MinMaxScaler, Z(·) is an activation function. ∆t denotes the time interval between Ga and Gb.

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.

3.2 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.

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 0th -layer hidden representations of regions vi in mobility pattern Gk as input region features xkvi , i.e.: (0)hkvi = xkvi . Considering the mobility flow from region vj to region vi, inspired by [Veliˇckovi´c et al., 2017], we compute the message sent along the mobility flow edge vj → vi by self-attention mechanism. The message function is defined as follows:

where ⟨·, ·⟩ is inner product, Wqp and Wkp are two trainable projection matrices, and N(vi) is neighbor region set of vi. Here, the message from region vj to vi is also attention score.

Afterwards, region vi aggregates the messages sent by its neighbor regions N(vi), and updates its hidden representation by a weighed sum from N(vi), given as follows.

where (l)Wvp is a learnable projection matrix in lth 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)mkvivj represents the attention score calculated by the message function in the f th head attention.

Taking the importance of mobility directions into account, we divide each mobility pattern Gk into two parts: source mobility pattern G s k and target mobility pattern G tk . Here, we regard the out-flow and in-flow mobility as node features of source intra-pattern Xs k and target intra-pattern Xtk , and apply intra-message passing layer in these two type of patterns, respectively, where Xs k = Xtk ⊤. To fuse these two region representations, we project the concatenation of them to generate hidden representation of vi:

where f(·) represents a linear projection. The region hidden representations hvi = {h0vi , h1vi , ..., hN-1 vi } extracting spatial dependency of N mobility patterns are generated by stacking L intra-pattern message passing layers.

Inter-Pattern Message Cross Attention

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 vi in mobility pattern Ga and Gb, let the node features in Ga and Gb are havi and hbvi , respectively. Then, for every such pair, we compute the correlation between Ga and Gb using attention as follows:

where Wqc and Wkc are two trainable projection matrices, and the attention score αvi ab reveals how Ga attends to the features of region vi of Gb. Afterwards, we compute an interpattern message for the region vi of mobility pattern Ga by a weighed sum, where the multi-head attention is applied again:

where Wvc is a learnable projection matrix.

Finally, the fused region embedding of vi 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 ˆhvi :

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 vi, we calculate the transition probability of destination vj :

Then, given the region embedding ˆhvi , ˆhvj for region vi, vj , we estimate the transition probability:

Finally, the objective function can expressed as:

4 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 Howdo 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)

4.1 Experiment Settings

Data Description We evaluate the performance of our method on New York City (NYC) datasets from NYC open data website 1 . Census blocks gives the boundaries of 180 regions split by streets in Manhattan, NYC. Taxi trips describes around 10 million taxi trip records during one month in the studied area. Crime count consists of around 40 thousand crime records during one year in the studied area.

1 opendata.cityofnewyork.us

Check-in count contains over 100 thousand check-in locations of over 200 fine-grained categories. Land usage type divides the borough of Manhattan into 12 districts by the community boards. We follow the settings in [Zhang et al., 2020] and apply taxi trip data as human mobility data and take the crime count, check-in count, land usage type as prediction tasks, respectively.

Baselines We compare MGFN with the following baseline methods: (1) node2vec [Grover and Leskovec, 2016] uses biased random walks to learn node latent representations by skip-gram models; (2) LINE [Tang et al., 2015] optimizes the objective function that preserves both the local and global network structures. (3) HDGE [Wang and Li, 2017] jointly embeds a spatial graph and a flow graph with temporal dynamics. (4) ZE-Mob [Yao et al., 2018] models spatio-temporal co-occurrence of zones in the embedding learning; (5) MV-PN [Fu et al., 2019] learns region embeddings with multi-view PoI network within the region; (6) MVURE [Zhang et al., 2020] enable cross-view information sharing and weighted multi-view fusion with human mobility and inherent region attributes data (e.g. POI, check-in).

Parameter Settings Following [Zhang et al., 2020], the dimension of region embeddings d is 96. In mobility graph fusion module, the weight ci 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.

4.2 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 (R2 ). 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 12.35% improvement in terms of R2 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.

4.3 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, MGFN-NP and MGFN-NC, respectively. Figure 4 shows the MAE, ARI and RMSE results of MGFN

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.

4.4 Graph SimilarityMeasurement (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.

4.5 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.

5 RelatedWorks

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ˇckovi´c 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. Fu et al. [2019] 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.

6 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).

Acknowledgments

The research is supported by Natural Science Foundation of China (61872306), and Fundamental Research Funds for the Central Universities (20720200031).