Trajectory-User Linking via Variational AutoEncoder

1 Introduction

Geo-tagged social media (GTSM) data, such as ones generated by Instagram, Foursquare and Twitter (to name but a few sources), provides an opportunity for better understanding and use of motion patterns in various applications [Zheng, 2015], such as POI recommendation [Yang et al., 2017a]; next visit-location [Liu et al., 2016]; user interest inference and individual activity modeling [Li et al., 2017a]; etc.

An important aspect, and often an initial component, of many applications based on GTSM data is the TrajectoryUser Linking (TUL), which links trajectories to users who generate them. For example, ride-sharing (bike, car) apps generate large volumes of trajectories - but the user identities are unknown - for the sake of privacy. However, correlating such trajectories with corresponding users seems desirable in many real world applications: it might lead to better, more personalized and/or precise recommendations; it may help in identifying terrorists/criminals from sparse spatio-temporal data such as transient check-ins [Gao et al., 2017].

†Corresponding author.

Common approaches for modeling human trajectories rely on Markov Chain (MC) or Recurrent Neural Networks (RNN) to model human mobility based on their historical check-ins. MC based methods [Zhang et al., 2016], e.g., Ranking based Markov chain (FPMC) and ranking based MC transition, are implemented under a strong independence assumption among non-adjacent locations, which limits their performance on capturing long term dependency of locations. RNN, on the other hand, is a special neural network that is able to handle variable-length input and output. It predicts the next output in a sequence, given all the previous outputs, by modeling the joint probability distribution over sequences. It has been successfully used in many spatiotemporal location predictions [Liu et al., 2016] and recently in identifying human mobility patterns in TUL context [Gao et al., 2017]. However, applying RNN directly in modeling check-in sequences in GTSM confronts the following challenges: (1) data sparsity: the density of check-ins such as those from Foursquare and Yelp are usually around 0.1% [Li et al., 2017a]; (2) structural dependency: strong and complex dependencies among check-ins or trajectories exist at different time-steps [Chung et al., 2015]; and (3) shallow generation: model variability (or stochasticity) occurs only when an output (e.g., location in POI sequence) is sampled [Serban et al., 2017].

In this paper, we tackle the above challenges in modeling human trajectories and linking trajectories to their generatingusers with a novel method - TULVAE (TUL via Variational AutoEncoder). The main benefits of TULVAE are:

1. It alleviates the data sparsity problem by adapting semisupervised variational autoencoder [Kingma et al., 2014] to utilize a large volume of unlabeled data to improve the performance of the TUL task.

(2) It instantiates an architecture for learning the distributions of latent random variables to model the variability observed in trajectories. By incorporating variational inference into the generative model with latent variables, TULVAE exposes an interpretable representation of the complex distribution and long-term dependencies over POI sequences.

1. By exploiting the practical fact that users' mobility tra-

jectories exhibit high spatio-temporal regularity (e.g., more than 90% of nighttime mobility records are generated in the same POI [Xu et al., 2017a]), TULVAE is able to capture the semantics of subtrajectories inherently representing the uniqueness of individual's motion. Furthermore, users' mobility trajectories exhibit hierarchical properties - e.g., frequent POIs within a subtrajectory, and some implicit patterns (e.g., the meaning of destinations) encoded across trajectories. This motivates us to exploit hierarchical mobility patterns for improving human mobility identification, as well as performance. As our main contributions:

• We take a first step towards addressing the data sparsity problem in GTSM with semi-supervised learning, especially via incorporating unlabeled data.
• We propose an optimization-based approach for modeling and inferring latent variables in human mobility, which, to our best knowledge, is the first variational trajectory inference model and opens up a new perspective for spatial data mining.
• We tackle the problem of hierarchical structures and complex dependencies of mobility trajectories by modeling both within- and across-trajectory semantics.
• We provide experimental evaluations illustrating the improvements enabled by TULVAE, using three publicly available GTSM datasets and comparing with several existing models.

In the rest of the paper, we review related work in Section 2 and introduce preliminaries in Section 3. Section 4 introduces the technical detail of TULVAE, followed by experimental observations presented in Section 5 and concluding remarks in Section 6.

2 RelatedWork

Mining human mobility behavior is a trending research topic in AI [Zhuang et al., 2017], GIS [Zheng et al., 2008] and recommendation systems [Yang et al., 2017a] and trajectory classification (i.e., categorizing trajectories into different motion patterns) is one of the central tasks in understanding mobility patterns [Zheng et al., 2008]. TUL was recently introduced [Gao et al., 2017] for correlating (unlabeled) trajectories to their generating-users in GTSM, using RNN based models to learn the mobility patterns and classify trajectories by users. However, the standard RNN based supervised trajectory models suffer from lacking of understanding hierarchical semantics of human mobility and fail to leverage the unlabeled data which embeds rich and unique individual mobility patterns. Trajectory recovery problem was studied in a similar manner in [Xu et al., 2017a], inferring individual's identity using trajectory statistics - essentially an equivalent TUL problem. The performance is greatly limited by the extreme sparsity issue in GTSM data: as observed in [Li et al., 2017a] the density of check-ins in Foursquare and Yelp data is around 0.1%, and that of the Gowalla data is around 0.04% [Yang et al., 2017a].

Deep generative models, such as Generative Adversarial Networks (GAN) [Goodfellow et al., 2014], autoregressive models [van den Oord et al., 2016] and Variational AutoEncoder (VAE) [Kingma and Welling, 2014], have been successful in image generation and natural language modeling [Yang et al., 2017b]. Semi-supervised generative learning, utilizing both labeled and unlabeled data for modeling complex high dimensional latent variables, has recently attracted increasing attention [Kingma et al., 2014; Hu et al., 2017]. VAE has shown promising performance on text classification [Xu et al., 2017b] and language generation tasks [Serban et al., 2017], however, its application in modeling human mobility has not been well investigated and previous VAE based models cannot be applied to TUL due to the data sparsity and complex semantic structures underlying humans' check-in sequences. TULVAE proposed in this paper differs from earlier works in: (1) tackling the latent variable inference problem in human mobility trajectories; (2) learning hierarchical semantics of human check-in sequences; and (3) incorporating the unlabeled data for identifying individual mobility pattern and for solving the TUL problem in the manner of semi-supervised learning.

Recent research in Moving Objects Databases (MOD) community has tackled problems related to managing spatiotextual trajectories (cf. [Issa and Damiani, 2016]) - however, most of the works pertain to efficient query processing and are complementary to the problems investigated in this paper.

3 Preliminaries

We now introduce the TUL problem and basics of VAE.

Trajectory-User Linking: Let tui = {ci1, ci2, ..., cin} denote a trajectory generated by the user ui during a time interval, where cij (j ∈ [1, n]) is a location at time tj for the user ui, in a suitable coordinate system (e.g., longitude + latitude, or some (xij, yij). We refer to cij as a check-in in this paper. A trajectory ¯ti = {c1, c2, ..., cm} for which we do not know the user who generated it, is called unlinked. The TUL problem is accordingly defined as: suppose we have a number of unlinked trajectories T = {¯t1, ...,¯tm} produced by a set of users U = {u1, ..., un} (m ≫ n). TUL learns a mapping function that links unlinked trajectories to users: T ↦→U [Gao et al., 2017].

Variational Autoencoders: Similar in spirit to text modeling (cf. [Yang et al., 2017b]), we consider a dataset consisting of pairs (tu1 , u1), · · · , (tum , um), with the i-th trajectory tui ∈ T and the corresponding user (label) ui ∈ U. We assume that an observed trajectory is generated by a latent variable zi. Following [Kingma and Welling, 2014], we omit the index i whenever it is clear that we are referring to terms associated with a single data point - i.e., a trajectory. The empirical distribution over the labeled and unlabeled subsets are respectively denoted by ˜ pl(t, u) and ˜ pu(t).

We aim at maximizing the probability of each trajectory t in the training set under the generative model, according to pθ(t) = ∫z pθ(t|z)pθ(z)dz, where: pθ(t|z) refers to a generative model or decoder; pθ(z) is the prior distribution of the random latent variable z, e.g., an isotropic multivariate Gaussian; pθ(z) = N(0, I) (I is the identity matrix); and θ is the generative parameters of the model. Typically, to estimate the generative parameters θ, the evidence lower bound (ELOB)

E d (t) (a.k.a. the negative free energy) on the marginal likelihood of a single trajectory is used as an objective [Kingma and Welling, 2014]:

where qφ(z|t) is an approximation to the true posterior pθ(z|t) (a.k.a recognition model or encoder) parameterized by φ. KL [qφ(·)||pθ(·)] is the Kullback-Leibler (KL) divergence between the learned latent posterior distribution q(z|t) and the prior p(z) (for brevity, we will omit the parameters φ and θ in subsequent formulas). Since the objective (of the model) is to minimize the KL divergence between q(z|t) and the true distribution p(z|t) - we can alternatively maximize ELOB E d (t) of log p(t) w.r.t. both θ and φ, which are jointly trained with separate neural networks such as multilayer perceptrons. We refer to [Kingma and Welling, 2014; Kingma et al., 2014] regarding the details of VAE and reparameterization approaches used for stochastic gradient descent training.

4 TUL via Variational AutoEncoder (TULVAE)

We now describe the details of the proposed TULVAE model consists of four RNN-based components: encoder RNN, intermediate RNN, decoder RNN and classifier, as illustrated in Figure 1.

qφ(z|t)

qφ(u|t)

Figure 1: Overview of the approach: TULVAE first uses trajectories to learn all check-in embeddings (low-dimension representation) T ∈ R|C|×d . Bottom Left: Encoder and intermediate RNNs are employed to learn the hierarchical structures of check-in sequences, with two-layer of latent variables concatenated to represent the latent space. Top Left: A sample z from the posterior qφ(z|t, u) and user u are passed to the generative network to estimate the probability pθ(t|u, z). Bottom Right: The unlabeled data is used to train a classifier qφ(z|t) to characterize label-distribution. Top Right: A user for a given unlinked trajectory is predicted by the deep neural networks.

4.1 Semantic Trajectory Segmentation

The trajectories of a user ui are originally separated by days, i.e., the original trajectory data Tui is segmented into k consecutive sub-sequences t1ui , ..., tkui , where k is the number of days that ui has check-ins. We consider two semantic factors: (1) Temporal influence: Following [Gao et al., 2017], each daily trajectory tjui (j ∈ [1, k]) is split into 4 consecutive subsequences tj,1 ui , ..., tj,4 ui based on time intervals of 6 hours. (2) Spatial influence: In Gowalla and Foursquare datasets, 90% of users' transition distances are less than 50km [Xu et al., 2017a] - indicating that users tend to visit nearby POIs. Thus, we further split a subtrajectory tj,m ui (m ∈ [1, 4]) if the continuous POI distance is more than 50 km.

4.2 Hierarchical Trajectory Encoding

Inspired by the hierarchical text models - e.g., in documentlevel classification [Zhang et al., 2018], and utterance-level dialogue generation [Serban et al., 2017], we model daily trajectories in a two-level structural hierarchy: a trajectory consists of subtrajectories that encode spatio-temporal moving patterns of an individual, while a subtrajectory is composed of sequential POIs:

where sn is the nth subtrajectory in a daily check-in sequence, sn,m is the mth POI in the nth subtrajectory, and Mn is the number of POIs in the mth subtrajectory.

At the POI level, a POI Long Short-Term Memory (LSTM) [Hochreiter and Schmidhuber, 1997] (or a Gated Recurrent Unit (GRU) [Chung et al., 2014]) is used to encode the POIs to form an implicit topic of a subtrajectory (e.g., "working", "Leisure" or "Home" in Figure 1). The last hidden states of the POI level encoder are fed into the intermediate LSTM (or GRU), where the internal hidden states are encoded into a vector to reflect the structured characteristics of daily mobility. The internal state of the hierarchical trajectory encoding is mathematically described as:

where respective LSTM(·) is a "vanilla" LSTM function:

where it, ft, ot and b∗ are respectively the input gate, forget gate, output gate and bias vectors; σ is the logistic sigmoid function; matrices W and U (∈ Rd×d ) are the different gate parameters; and vt is the embedding vector of the POI ct.

The memory cell ct is updated by replacing the existing memory unit ˜ct with a new cell, where tanh(·) is the hyperbolic tangent function, and ⊙ is the component-wise multiplication. The output encoding vector Evt is the final hidden layer. We refer the proposed hierarchical TUL learning as HTULERs, which alone improves the performance, in comparison with shallow POI-level learning methods (cf. Section 5).

4.3 TULVAE

To alleviate data sparsity problem, incorporating unlabeled data can improve the performance of identity linking - which may be partially addressed by the semi-supervised VAE [Kingma et al., 2014]. However, this has limitations in modeling hierarchical structures of latent variables due to estimating the posterior with a single layer of encoder and may fail to capture abstract representations. Similarly, recursively stacking VAEs on top of each other [Sønderby et al., 2016] is restricted by the overfitting of bottom generative layer - which alone learns sufficient representation to reconstruct the original data and renders the above layer(s) unnecessary [Zhao et al., 2017].

Thus, we prefer to encode abstract topics of subtrajectories on certain part of the latent variables, and POI sequence patterns in others - learning the inference model in a "flat" semiVAE framework. The basic idea of this implicit hierarchical generative model is inspired by the variational ladder autoencoder (VLAE) [Zhao et al., 2017], where shallow networks are used to express low-level simple features. Deep networks, in turn, express high-level complex features, and inject Gaussian noise at different levels of the network. We note, though, that VLAE is designed for continuous latent feature discriminative learning, while TULVAE is a semi-supervised learning framework for discrete trajectory data.

More specifically, we consider a two-layer of latent variables z1, z2, respectively denoting the POI-level (bottom) and abstract level (top) layer. The prior p(z) = p(z1, z2) is a standard Gaussian and the joint distribution p(t, z1, z2) can be thus factored as p(t, z1, z2) = p(t|z1, z2)p(z1|z2)p(z2). In the generative network, the latent variable z is a concatenation of two vectors z = [RNNm(z2); RNNn(z1)], where z2 and z1 are respectively parameterized by the intermediate RNN and POI RNN. For the inference network, the approximate posterior p(z|t) is a Gaussian N(µi, σi)(i = 1, 2) parameterized by two-level RNNs.

Given the implicit representation of the hierarchy of latent variables, we now learn the trajectories in a semi-supervised manner and essentially adapt in a single-layer model. Thus, when the user u corresponding to a trajectory is observed (labeled data Dl), we have:

Our goal is to approximate the true posterior p(z|t, u) with q(z|t, u), i.e., minimizing KL [q(z|t, u)||p(z|t, u)]. Therefore, we obtain the following ELOB E g 1 (t, u):

where KL [q(z|t, u)||p(z)] is the KL divergence between the latent posterior q(z|t, u) and the prior distribution p(z), which measures how much information is lost when approximating a prior over z. The expectation term is the reconstruction error or expected negative log-likelihood of the data, which encourages the decoder to reconstruct the trajectory from the latent distribution.

In the case of unlabeled trajectory data Du, the user identity u is predicted by performing posterior inference with a classifier qφ(u|t). We now have following ELOB E g 2 (t), by considering u as another latent variable:

where H(q(u|t)) is the information entropy, and the loss of the classifier qφ(u|t) during training is measured by L2 reconstruction error between the predicted user and the real label. Thus, the ELOB E on the marginal likelihood for the entire dataset is:

where the first RHS term includes an additional classification loss of classifier qφ(u|t) when learning from the labeled data, and hyper-parameter α controls the weight of labeled data learning.

We note that semi-VAE scales linearly in the number of classes in the data sets, which is raised by re-evaluating the generative likelihood for each class during training. For the task of text classification, the number of classes is small (e.g., 2 classes in IMDB and 4 classes in AG's News). However, the number of classes (i.e., users) in TUL is very large, which incurs heavy computation on evaluating classifier qφ(u|t). To overcome this problem, we employ the Monte Carlo method suggested in [Xu et al., 2017b] to estimate the expectation evaluations per class, where the baseline method from [Williams, 1992] is used to reduce the variance of the sampling-based gradient estimator: ▽φEz∼q(z|t,u)[q(u|t)(-E g 1 (t, u)]. Since ELOB E g 2 (t) determines the magnitude of classifier qφ(u|t), the baseline we use in TULVAE is the averaged E g 2 (t), following the choice in previous text classification works, i.e., [Xu et al., 2017b].

4.4 Training

At the early stage of TULVAE training, the term KL [q(z|t, u)||p(z)] in Eq.4 may discourage encoding interesting information into the latent variable z, thereby easily resulting in model collapse - largely because of the strong learning capability of autoregressive models such as RNN as observed in [Bowman et al., 2016]. One efficient solution is to control the weight of KL-divergence term by gradually increasing its co-efficiency β (from 0 to 1), which is also called KL cost annealing [Bowman et al., 2016].

The activation function used in the RNN models is softplus (i.e., f(x) = ln(1 + ex )), which applies nonlinearity to each component of its argument vector ensuring positive variances. In addition, we use the "bucket trick" to speed up the training process: we sort all trajectories by length, and put those with similar length into the same bucket, in which the data is padded to the same length and fed into the neural networks as a batch. This may yield efficiency - i.e., reduce the computation time since variable length data is one of the bottlenecks in RNN based training.

Finally, we use Bidirectional LSTMs in TULVAE which could jointly model the forward likelihood and the backward posterior for training the POI sequences, which could potentially capture richer representation of the mobility patterns and speed up the convergence of training.

Discussion: TULVAE formulates the solution to TUL problem in a semi-VAE framework combined with hierarchical trajectory modeling with RNNs. There exist several other choices in TULVAE - e.g., the decoder could be replaced with a CNN which has the potential to improve the efficiency since it only requires a convolution on one dimension for discrete data, such as dilation CNN decoder used in [Yang et al., 2017b] for text modeling. Another modification is to incorporate the label information to the latent representation, using the disentangled variables instead of introducing a classifier qφ(u|t) [Li et al., 2017b]. By dividing the latent representation into disentangled variables and non-interpretable variables, the categorical information can be explicitly employed to regularize the disentangled representation. However, in this work we focus on inferring the distribution of variables in human check-ins and improving the performance of TUL. The investigation of alternatives for TULVAE are left for our future work.

5 Evaluation

In this section we present the evaluation of the benefits of TULVAE using three real-word GTSM datasets. To ease the reproduction of our results, we have made the source code of TULVAE publicly available 1 .

Table 1: Data description: |U|: the number of users; |Tn|/|Te|: number of trajectories for training and testing; |C|: number of check-ins; R: average length of trajectories (before segmentation); Tr: range of the trajectory length

Datasets: We conducted our experiments on three publicly available GTSM datasets: Gowalla 2 , Brightkite 3 and Foursquare 4 . For Foursquare, we choose the most popular city - New York. We randomly select |U| users and their corresponding trajectories from the datasets for evaluation - for each dataset, we select two different numbers of those users (e.g., labels here) who generate varied trajectories for robustness check of model performance. Table 1 depicts the statistics of the three datasets.

Baselines and Metrics: We compare TULVAE with several state-of-the-art approaches from the field of trajectory similarity measurement and deep learning based classification. We also implemented three hierarchical variations of TULER (TUL via Embedding and RNN) [Gao et al., 2017] - namely: HTULER-L, HTULER-G and HTULER-B, respectively implemented with the hierarchical LSTM, GRU and Bi-directional LSTM but without variational inference. In our implementation, multivariate Gaussian distribution is used as the prior in TULVAE. The learning rate of all models is initialized with 0.001 and decays with rate of 0.9. The weight β (KL cost annealing) increases from 0.5 to 1; and the dropout rate is 0.5. We embed POIs in 250 dimensional vectors and used 300 units for classifier, 512 units for the encoder-decoder RNN and 100 units for latent variable z. Finally, the batch size is 64 for all RNN based models.

1 https://github.com/AI-World/IJCAI-TULVAE

2 http://snap.stanford.edu/data/loc-gowalla.html

3 http://snap.stanford.edu/data/loc-brightkite.html

4 https://sites.google.com/site/yangdingqi/home

The baselines used for benchmarking can be broadly categorized as:

(a) Traditional approaches, including LDA (Linear Discriminant Analysis, with SVD as matrix solver), DT (Decision Tree), RF (Random Forest) and SVM (Support Vector Machine, with linear kernel), which are widely used for measuring mobility patterns and classifying trajectories in literatures [Zheng, 2015].

(b) RNN based TUL, including TULER-LSTM, TULERGRU, TULER-LSTM-S, TULER-GRU-S and Bi-TULER proposed in [Gao et al., 2017], which are the state-of-the-art methods for trajectory-user linking.

We report the ACC@K, macro-P, macro-R and macro-F1 of all methods, which are common metrics in information retrieval area. Specifically, ACC@K is used to evaluate the trajectory-user linking accuracy as:

and macro-F1 is the harmonic mean of the precision (macro-P) and recall (macro-R), averaged across all classes (users in TUL):

Performance comparison

Table 2 summarizes the performance comparisons among the proposed method and RNN based baselines on three datasets, where the best method is shown in bold, and the second best is shown as underlined. We demonstrate the comparison to traditional approaches in Figure 2 only for Foursquare dataset - because, to our knowledge, these methods have already been shown to be inferior to TULERs [Gao et al., 2017] on Gowalla and Brightkite. From the results, we can see how the hierarchical trajectory modeling combined with latent representation in exploring human mobility patterns yields performance improvements over the baseline(s). In summary:

(1) TULVAE performs the best on most of metrics. This superior result is due to its capability of learning the complicated latent distribution of trajectories and leveraging the unlabeled data. By modeling the distribution of trajectories in a probabilistic generative model (rather than point estimation in "vanilla" RNNs), TULVAE is able to capture underlying semantics of mobility patterns. In addition, by incorporating unlabeled data into the training, the semi-supervised classifier in TULVAE may ameliorate the data sparsity problem inherent to the GSTM data. However, the latent representation learned is often not effective enough, especially when the data size is small, e.g., |U| = 34 in Brightkite. We conjecture that this is partially because of the entangled representation produced by the encoder, which results in difficulty on characterizing variations of relative small and sparse datasets.

(2) We note the improvements due to hierarchical trajectory modeling when focusing more specifically on comparison between HTULERs and TULERs. Although TULERs use variant RNNs, they suffer from the shallow generation in modeling check-in sequences. In contrast, HTULERs explore structural information of human mobility, which leads to a more robust performance - even superior on several metrics when the number of users is relative small.

(3) When it comes to the training process of various deep learning-based TUL methods, Figure 3 shows the results (ACC@1) on Foursquare and it shows that TULVAE exhibits fastest convergence. This demonstrates the effectiveness of inherent generative models in understanding human mobility. Similar results also hold for other metrics and other datasets but are omitted here due to the lack of space.

6 Conclusions

We presented TULVAE, a generative model to mine human mobility patterns, which aims at learning the implicit hierarchical structures of trajectories and alleviating the data sparsity problem with the semi-supervised learning. TULVAE achieves a significant performance improvement for the TUL problem in comparison to existing methods. In addition, TULVAE can be augmented by incorporating other representative features such as spatial and temporal information in the latent space, which we leave for our future investigation.

Acknowledgements

This work was supported by National Natural Science Foundation of China (Grant No.61602097, No.61472064 and No.61502087), NSF grants III 1213038 and CNS 1646107, ONR grant N00014-14-10215 and HERE grant 30046005, and the Fundamental Research Funds for the Central Universities (No.ZYGX2015J072).