# Trajectory-User Linking via Hierarchical Spatio-Temporal Attention Networks

Wei Chen1, Chao Huang2, Yanwei Yu1, ✉, Yongguo Jiang1, Junyu Dong1

Corresponding author: Yanwei Yu. 1College of Computer Science and Technology,
Ocean University of China, Qingdao, China
2Department of Computer Science, The University of Hong Kong, Hong Kong, China
<EMAIL_ADDRESS><EMAIL_ADDRESS>
{yuyanwei, jiangyg<EMAIL_ADDRESS>
###### Abstract

Trajectory-User Linking (TUL) is crucial for human mobility modeling by
linking different trajectories to users with the exploration of complex
mobility patterns. Existing works mainly rely on the recurrent neural
framework to encode the temporal dependencies in trajectories, have fall short
in capturing spatial-temporal global context for TUL prediction. To fill this
gap, this work presents a new hierarchical spatio-temporal attention neural
network, called AttnTUL, to jointly encode the local trajectory transitional
patterns and global spatial dependencies for TUL. Specifically, our first
model component is built over the graph neural architecture to preserve the
local and global context and enhance the representation paradigm of
geographical regions and user trajectories. Additionally, a hierarchically
structured attention network is designed to simultaneously encode the intra-
trajectory and inter-trajectory dependencies, with the integration of the
temporal attention mechanism and global elastic attentional encoder. Extensive
experiments demonstrate the superiority of our AttnTUL method as compared to
state-of-the-art baselines on various trajectory datasets. The source code of
our model is available at https://anonymous.4open.science/r/Attn_TUL.

###### Index Terms:

Trajectory-user linking, attention neural networks, trajectory representation
learning, spatio-temporal data

##  I Introduction

The development of mobile computing techniques enables the collection of
massive mobility data from various sources, including location-based social
networks, geo-tagged social media and GPS enabled mobile applications [1, 2].
Among various mobility modeling applications, a recently introduced
Trajectory-User Linking (TUL) task, which aims to link anonymous trajectories
to users who generate them, is crucial and beneficial for a broad range of
spatial-temporal mining applications, ranging from location-based
recommendations [3] to urban anomaly detection [4, 5]. For example, vehicle-
mounted terminals and ride-sharing services usually anonymize user identities
in collecting mobility data due to the privacy issue. Effective linking
trajectories with their corresponding users can not only enable accurate
location-based recommendations, but also identify abnormal events from users’
GPS traces. Therefore, the linking results between users and their anonymous
trajectories are important for advancing the business intelligence and smart
city applications [6, 7].

Figure 1: An illustrated example of linking anonymous mobility trajectories
with corresponding users. Based on the mobility trajectories of five users, we
find that the anonymous trajectory (red) is much closer to the trajectory of
user $E$ (dark gray). Thus, we can link the anonymous trajectory with user
$E$.

In this paper, we tackle the trajectory-user linking challenge via exploring
the spatio-temporal movement patterns from the mobility data. Figure 1
presents an intuitive example of linking anonymous trajectories with the
corresponding users. Our goal in this work is to link anonymous mobility
trajectories to the users who are most likely to produce them based on the
historical trajectories. Due to the strong representation ability of deep
learning techniques, existing studies attempt to solve the TUL problem based
on various trajectory representation learning models [8, 9, 10]. For example,
TULVAE [9] incorporates VAE model into the TUL problem to learn hierarchical
semantics of check-in trajectories with RNN to improve the prediction
accuracy. DeepTUL [8] proposes to integrate recurrent networks with attention
mechanism to model higher-order and multi-periodic mobility patterns by
learning from historical traces. AdattTUL [11] and TGAN [12] utilize
Generation Adversarial Network (GAN) to study the TUL problem with adversarial
mobility modeling. Recently, SML-TUL [13] uses contrastive learning to encode
the predictive representations from the user mobility itself constrained by
spatio-temporal factors.

Despite their effectiveness, four key limitations exist in these methods.
First, all existing methods still suffer from data sparsity, and cannot learn
quality representations over low-sampling trajectories (e.g., check-ins of
inactive users). Second, existing methods generally rely on the recurrent
neural frameworks to model trajectory sequence, and thus can hardly capture
the long-term dependencies among the long sequence mobility traces [14].
Previous approaches show suboptimal performance when dealing with long
sequence data in our evaluation. Third, most of existing works are limited to
inject the global spatial and temporal context into the intra- and inter-
trajectory pattern modeling. In practical scenarios, human trajectory are
often exhibited with hierarchical mobility patterns across different time
granularities [9]. Lastly, few of previous approaches incorporate the rich
external contextual features into the representation of human mobility data.

To address the aforementioned challenges, we propose AttnTUL, a hierarchical
spatio-temporal attention network, to realize high predictability for TUL
problem. Particularly, AttnTUL is built on a graph neural architecture to
encode both local and global trajectory transitional patterns. Our graph-based
message passing paradigm is able to alleviate the data sparsity issue by
effectively performing knowledge transfer among geographical regions and
trajectories based on our generated hierarchical spatial graphs. To capture
the intra-trajectory transitional regularities, we develop a temporal self-
attention mechanism to encode the long-term mobility dependencies. To model
the inter-trajectory relationships, AttnTUL enhances the trajectory
representation paradigm by preserving the spatial context across the entire
urban space, with the introduced global elastic attentive encoder. The
integrated local and global embeddings will be fed into the prediction layer
for linking trajectories to their corresponding users. With the design of
local and global hierarchical modeling, our proposed AttnTUL method is general
and robust for both dense GPS trajectory data and sparse check-in trajectory
data

In our evaluation, experimental results on three types of real-life mobility
datasets show that our model significantly outperforms several strong
baselines (21.75% ACC@1 gain and 24.34% Macro-F1 gain on average) in TUL task
on both sparse and dense trajectory data. Additionally, our perform ablation
study to justify the model design rationale with component-wise effect
investigation.

Our contributions can be summarized as follows:

  * •

We propose AttnTUL, a hierarchical spatio-temporal attention network model to
solve the TUL problem. Our AttnTUL simultaneously models local and global
spatial and temporal characteristics of users’ mobility trajectories over a
graph neural architecture.

  * •

We design a hierarchical spatio-temporal attention network which contains a
temporal self-attention encoder to learn the local sequential dependencies
within trajectory, and a global elastic attention encoder to capture the
complex inter-trajectory dependencies.

  * •

We conduct extensive experiments on three types of real-life mobility
datasets. Results show that our model significantly outperforms state-of-the-
art baselines by 12.73%$\sim$46.85% and 18.90%$\sim$50.97% improvements in
terms of ACC@1 and Macro-F1.

##  II Related Work

In literature, measuring the similarity or distance between trajectories which
is essential to trajectory pattern mining. Similarity measures, e.g., Dynamic
Time Warping (DTW) [15], Longest Common Sub-Sequence (LCSS) [16], Trajectory-
Hausdorff Distance [17], Spatio-Temporal Linear Combine distance [18], and
Spatiotemporal Signature [19], are often used to discover the user similarity
from their trajectories. However, such approaches are artificially designed,
and thus only suitable for specific scenario. Recently, deep representation
learning has been used for trajectory similarity computation [20, 21, 22, 23,
24]. However, these methods focus more on improving the efficiency of
trajectory similarity computation. Trajectory classification is another way to
understand mobility patterns. Existing trajectory classification works focus
on labeling trajectories as different motion patterns, such as Driving, Biking
and Walking in transportation classification [25] and Occupied, Non-occupied
and Parked in taxi status inference [26]. These approaches mainly rely on
extraction of spatio-temporal characteristics of trajectories.

TUL problem was recently introduced in [10], which links trajectories to their
generating-users, and gradually becomes a hot topic in spatio-temporal data
mining by classifying trajectories by users. Due to its broad range of
applications in personalized recommendation systems, location-based services
and urban planning, it gradually becomes a hot topic in spatio-temporal data
mining. Several methods have been proposed to solve the TUL problem [10, 9, 8,
27, 28]. TULER [10] utilizes RNN based models to learn sequential transition
patterns from trajectories, and links them to users. It first uses word
embedding to learn the representations for locations in the trajectories and
feed them into RNN model to capture mobility patterns for TUL. However, the
standard RNN based models suffer from data sparsity problem and lacking of
understanding hierarchical semantics of human mobility. In their follow-up
work [9], TULVAE is proposed to improve the prediction accuracy by
incorporating VAE into TUL task to learn hierarchical semantics of check-in
sequences. However, it fails to utilize existing abundant features and also do
not consider multi-periodic mobility regularities. DeepTUL [8] proposes using
the attentive recurrent network in TUL to alleviate the data sparsity problem
by leveraging historical data, and capture multi-periodic regularities of
human mobility to improve prediction accuracy. AdattTUL [11] and TGAN [12]
introduce Generation Adversarial Network (GAN) to deal with the TUL problem.
Recently, SML-TUL [13] uses contrastive learning to learn the predictive
representations from the user mobility itself constrained by the spatio-
temporal factors. Nevertheless, these methods use RNNs for modeling or
prediction, which cannot effectively model long-term dependencies of
trajectories, and all above methods ignore the contribution of global spatial
modeling to TUL prediction.

In addition, a few recent works are proposed to identify users across
different mobility datasets [7, 29]. DPLink [7] is designed to model the
correlations between trajectories to measure the trajectory similarity from
different data source. Recently, attention mechanism [30] has also been
studied in spatio-temporal data mining. Researchers combine attention with RNN
for mobility modeling, such as mobility prediction [31] and mobility inference
[32], and personalized route recommendation [33]. Thanks to the
characteristics of attention mechanism, it can make up for the deficiency of
RNN in capturing long-term dependencies to some extent. Different from the
previous studies, to our best knowledge, we are the first to abandon RNN and
adopt the fully attention neural network to solve TUL problem.

##  III Preliminaries

Figure 2: The overview of the proposed framework

In this section, we first introduce some preliminary concepts and then
formally define the problem of TUL.

Let $\mathcal{U}=\\{u_{1},u_{2},\dots,u_{i}\\}$ denote a set of moving users.

######  Definition 1 (Spatio-Temporal Point).

A spatio-temporal point is a uniquely entity in the form of $\langle
t,\ell\rangle$, where $t$ is the visited timestamp, and $\ell$ represents the
geographical coordinates of the point (i.e., longitude and latitude).

######  Definition 2 (Trajectory).

A trajectory is a sequence of spatio-temporal points $(\langle
t_{1},\ell_{1}\rangle,\langle t_{2},\ell_{2}\rangle,\dots,\langle
t_{m},\ell_{m}\rangle)$ generated by user $u_{i}$ in chronological order
during a certain time interval $\tau$, which is denoted by
$Tr_{u_{i}}^{\tau}$.

The time interval can be one hour, one day, one week or even one month. A
trajectory is called unlinked, if we do not know the user who generated it.
Let $T$ denote the whole time interval. The known trajectories generated in
previous time intervals by all users, i.e., linked trajectories, are denoted
by $Tr_{u}=\\{Tr_{u_{i}}^{\tau}|u_{i}\in\mathcal{U}\land\tau\in T\\}$.

Based on the above definitions, we now state our studied problem as below:

######  Problem (Trajectory-User Linking).

Given a set of unlinked trajectories $\overline{Tr}$ generated by users
$\mathcal{U}$ and corresponding linked trajectories $Tr_{u}$, our goal is to
learn a mapping function $f:\overline{Tr}\rightarrow\mathcal{U}$ that links
anonymous trajectories to users.

Key notations used in the paper are summarized in Table I.

TABLE I: Main notations and their definitions. Notation | Definition
---|---
$\mathcal{U}$ | the set of moving users
$\langle t,\ell\rangle$ | a spatio-temporal point
$Tr_{i}$ | a trajectory
$m$ | the number of spatio-temporal points in $Tr_{i}$
$\tau$ | the time interval
$Tr_{u_{i}}^{\tau}$ | a trajectory generated by $u_{i}$
$T$ | the whole time interval
$Tr_{u}$ | the set of linked trajectories
$\overline{Tr}$ | the set of unlinked trajectories
$\mathcal{G}_{l}=(\mathcal{V}_{l},\mathcal{E}_{l})$ | the local spatial graph
$\mathbf{A}_{l}$ | the adjacency matrix of local spatial graph
$\mathbf{X}_{l}$ | the feature matrix of local spatial graph
$\mathcal{G}_{g}=(\mathcal{V}_{g},\mathcal{E}_{g})$ | the global spatial graph
$\mathbf{A}_{g}$ | the adjacency matrix of global spatial graph
$\mathbf{X}_{g}$ | the feature matrix of global spatial graph
$\mathbf{H}_{l}$ | the embeddings of all grids
$\mathbf{H}_{g}$ | the global embeddings of all trajectories
$z_{i}^{l}$ | the local representation for $Tr_{i}$
$z_{i}^{g}$ | the global representation for $Tr_{i}$

##  IV Methodology

In this section, we present the details of our neural network model AttnTUL
(as shown in Figure 2), consisting of four key components: (1) local and
global graph modeling, (2) spatial convolutional networks, (3) hierarchical
spatio-temporal attention networks, and (4) linking layer. First, we construct
a local graph and a global graph to model micro and macro spatial
relationships for all trajectories, respectively. Second, we present the
spatial convolutional networks on the two graphs to learn initial embedding
for each divided grid and each trajectory. Third, we employ a multi-head
temporal self-attention network to capture the temporal dependency in local
embeddings of each trajectory and fuse the local embeddings. We also design an
global elastic attention encoder to obtain global representation. Finally, we
use a linking layer to classify trajectories by users.

###  IV-A Local and Global Graph Modeling

In this section, we introduce how to construct local and global spatial
graphs.

####  IV-A1 Preprocessing

To facilitate the construction of local spatial graph, we employ a gridding
technique to divide the geographic space of all trajectories into discrete
grids. More specifically, given grid size $s$, the whole geographic space is
divided into $n$ grids. Consequently, we constrict a grid mapping function
$f_{g}:\ell_{i}\rightarrow g_{i}$, so that each trajectory $Tr=(\langle
t_{1},\ell_{1}\rangle,\langle t_{2},\ell_{2}\rangle,\dots,\langle
t_{m},\ell_{m}\rangle)$ can be mapped to a grid sequence
$Tr^{{}^{\prime}}=(\langle t_{1},g_{1}\rangle,\langle
t_{2},g_{2}\rangle,\dots,\langle t_{m},g_{m}\rangle)$.

####  IV-A2 Local Spatial Graph Construction

To capture the correlations among spatial locations in all trajectories, we
first construct a local spatial graph
$\mathcal{G}_{l}=(\mathcal{V}_{l},\mathcal{E}_{l})$, where each grid is a node
in $\mathcal{G}_{l}$, and edges indicate the connectivity between grids. That
is, an edge is created between grid $g_{i}$ and grid $g_{j}$ if a trajectory
contains a consecutive snippet from $g_{i}\backslash g_{j}$ to
$g_{j}\backslash g_{i}$. In high-sampling trajectories, some consecutive
spatio-temporal points may be mapped to same grid. For this case, we remove
the self-loop edges in $\mathcal{G}_{l}$. The weight on edge
$e_{i,j}\in\mathcal{E}_{l}$ is defined as the number of trajectories that
contains the consecutive snippet $(g_{i}\backslash g_{j}\rightarrow
g_{j}\backslash g_{i})$.

Furthermore, the semantic context of nodes can be expressed by a feature
matrix. In this paper, we adopt a one-hot vector (the length is the number of
grids) for each node $g_{i}$ to express the uniqueness of its location in the
feature matrix. We use $\mathbf{A}_{l}$ and $\mathbf{X}_{l}$ to denote the
adjacency matrix and feature matrix of local spatial graph, respectively.

####  IV-A3 Global Spatial Graph Construction

To model spatial correlations between trajectories and known linkages between
users and trajectories, we next construct a global spatial graph
$\mathcal{G}_{g}=(\mathcal{V}_{g},\mathcal{E}_{g})$, which is a heterogeneous
graph that contains the above two relationships.

Specifically, $\mathcal{G}_{g}$ includes two types of nodes – trajectory nodes
and user nodes, i.e., each trajectory is treated as a node and each user is
also regarded as a node. If two trajectories share common grids, then an edge
is created between these two trajectory nodes. The weight of the edge between
two trajectory nodes is defined as the number of shared grids in two
trajectories. In addition, the labeled trajectories are connected to their
users, and the weights on the edges between user node and trajectory node are
uniformly defined as the maximum weight between trajectory nodes, which
indicates that the relationship strength between labeled trajectories and
their users is maximized, and further the relationship between the
trajectories of the same user is also strengthened.

For each trajectory node $Tr_{i}$ and user node $u_{j}$, we encode its spatial
features (passed grids) into a multi-hot vector (the length is the number of
grids) to represent their spatial characteristics. We use $\mathbf{A}_{g}$ and
$\mathbf{X}_{g}$ to denote the adjacency matrix and feature matrix of global
spatial graph, respectively.

Notably, when the number of trajectories is very large, if the traversal
method is used to search for pairs of interactive trajectories (i.e., share
common grids), the construction of the global spatial graph is actually very
time-consuming. To improve the construction efficiency and reduce the time
cost, we propose a fast implementation trick. We first use grid coding to
represent each trajectory, that is, use one hot coding, for each grid, if the
trajectory contains the grid, then the code is 1, otherwise 0. Thus we can
obtain the grid coding matrix of all trajectories, denoted by
$\mathbf{C}_{g}$. Therefore, the adjacency matrix $\mathbf{A}_{g}$ can be
calculated directly by:
$\mathbf{A}_{g}=\mathbf{C}_{g}\cdot{\mathbf{C}_{g}}^{\mathsf{T}}.$

###  IV-B Spatial Graph Convolutional Networks

####  IV-B1 Local Graph Convolution

GCNs have been widely used in graph representation learning to capture graph
topological structure by aggregating neighbor features and have achieved great
success [34, 35]. We employ GCN on the local spatial graph and global spatial
graph constructed by different granularities to learn the hierarchical
embeddings of trajectories.

To jointly capture the topological structures and spatial location information
among grids, we first perform convolution operation on local graph $G_{l}$.
Following [36], multi-layer spatial convolution network performs following
layer-wise propagation rule:

$\mathbf{H}_{l}^{(i+1)}=\operatorname{ReLU}\left(\tilde{\mathbf{D}}_{l}^{-\frac{1}{2}}\tilde{\mathbf{A}}_{l}\tilde{\mathbf{D}}_{l}^{-\frac{1}{2}}\mathbf{H}_{l}^{(i)}\mathbf{W}_{l}^{(i)}\right),$
(1)

where $\mathbf{W}_{l}^{(i)}$ is a layer-specific trainable weight matrix,
$\tilde{\mathbf{A}}_{l}=\mathbf{A}_{l}+\mathbf{I}$, and
$\tilde{\mathbf{D}}_{l_{ii}}=\sum_{j}\tilde{\mathbf{A}}_{l_{ij}}$.
$\mathbf{H}_{l}^{(0)}=\mathbf{X}_{l}$, where $\mathbf{X}_{l}$ is the feature
matrix of $\mathcal{G}_{l}$. $\mathbf{H}_{l}^{(i)}\in\mathbb{R}^{n\times d}$
is the output of $i$-th layer where $d$ is the embedding dimension, denoting
the initial embeddings of all grids.

####  IV-B2 Global Graph Convolution

Although local graph convolution can learn the embeddings for all grids, it
may not be able to capture the correlations between trajectories and between
users and their produced trajectories from a global perspective. Therefore, to
learn the embeddings of trajectories and users, we next perform convolution
operation on global spatial graph:

$\mathbf{H}_{g}^{(i+1)}=\operatorname{ReLU}\left(\tilde{\mathbf{D}}_{g}^{-\frac{1}{2}}\tilde{\mathbf{A}}_{g}\tilde{\mathbf{D}}_{g}^{-\frac{1}{2}}\mathbf{H}_{g}^{(i)}\mathbf{W}_{g}^{(i)}\right),$
(2)

where $\mathbf{W}_{g}^{(i)}$ is a layer-specific trainable weight matrix, and
$\mathbf{H}_{g}^{(0)}=\mathbf{X}_{g}$. We can learn the embedding for each
trajectory and each user via global graph convolutional network, which
captures the key spatial characteristics of trajectories from the whole.

###  IV-C Hierarchical Spatio-Temporal Attention Networks

####  IV-C1 Semantic Location Encoder

In addition to spatial information, contextual features in mobility data,
e.g., motion state and time feature, can be considered into location embedding
for trajectory sequence modeling. Therefore, location encoder is a multi-modal
embedding module. Following [37], we divide the motion state into $(i)$ speed-
related operations (i.e., acceleration, deceleration, and constant speed) and
$(ii)$ direction-related operations (i.e., turning left, turning right, and
moving straight), and combine them into nine motion states. For time feature,
we divide the whole time into time windows according to a certain time
granularity (e.g., 10 minutes). Figure 3 shows an example of state encoder and
time encoder in semantic location encoder.

Specifically, we design two sparse linear embedding layers to encode motion
state $s_{i}$ and time window $t_{i}$ (e.g., one-hot), and then concatenate
the corresponding grid embedding to obtain an ensemble vector $x_{i}$. The
formulation of location encoder is as follows:

$x_{i}=\operatorname{Tanh}\left(FC([\mathbf{W}_{t}t_{i}+b_{t};\mathbf{W}_{s}s_{i}+b_{s};\mathbf{H}_{l}(g_{i})])\right),$
(3)

where $\mathbf{W}_{t}$, $\mathbf{W}_{s}$, $b_{t}$ and $b_{s}$ are learnable
parameters of embedding layers, $\mathbf{H}_{l}(g_{i})$ denotes the local
embedding of grid $g_{i}$, and $\mathbf{[;;]}$ denotes the concatenate
function. $\operatorname{Tanh}(\cdot)$ is the non-linear activation function,
and $FC(\cdot)$ is a fully connected layer.

Figure 3: State/time encoder in semantic location encoder

####  IV-C2 Temporal Self-Attention Encoder

To capture the long-term temporal dependencies in trajectory sequence which is
difficult to model and learn by RNN-based models, we employ a multi-head
temporal self-attention mechanism to learn the intra-trajectory correlations.

To supplement sequence information, the input first adds the position
encoding:

$\begin{split}\mathbf{M}_{i}=\mathbf{X}_{i}+\mathbf{P},\\\ \end{split}$ (4)

where $\textbf{X}_{i}=\\{x_{1},x_{2},\dots,x_{m}\\}$ are location embeddings
for all grids in trajectory $Tr_{i}$, and $\mathbf{P}$ denotes the position
encoding, which aims to distinguish the sequence position. Notice that
$\mathbf{P}$ is fixed and defined as in [38].

Then, $\mathbf{M}_{i}$ is then sent to the self-attention module to integrate
the sequence information:

$\begin{split}\left(\mathbf{Q}_{i},\mathbf{K}_{i},\mathbf{V}_{i}\right)^{\mathsf{T}}=\mathbf{M}_{i}\left(\mathbf{W}^{Q},\mathbf{W}^{K},\mathbf{W}^{V}\right)^{\mathsf{T}},\\\
\mathbf{Z}_{i}=\operatorname{Softmax}\left(\frac{\mathbf{Q}_{i}\mathbf{K}_{i}^{\mathsf{T}}}{\sqrt{d}}\right)\mathbf{V}_{i},\\\
\end{split}$ (5)

where $\mathbf{W}^{Q},\mathbf{W}^{K},\mathbf{W}^{V}\in\mathbb{R}^{d\times d}$
are learnable projection matrices. The spatiotemporal correlation is
calculated by dot product. $\operatorname{Softmax}(\cdot)$ is used to
normalize the spatiotemporal dependencies, and the scale $\sqrt{d}$ prevents
the saturation led by $\operatorname{Softmax}$ function. Besides, we also
employ a residual connection to solve the problem of network degradation,
followed by layer normalization.

In addition, multiple dependency patterns from location embeddings in a single
trajectory can be learned through a multi-head attention mechanism:

$\begin{split}\mathbf{Z}_{i}=FC(\operatorname{concat}(\mathbf{Z}_{i}^{(1)},\mathbf{Z}_{i}^{(2)},\dots,\mathbf{Z}_{i}^{(\\#head)})),\end{split}$
(6)

By stacking multiple temporal self-attention layers, we can effectively
capture the complex temporal dependencies in trajectory sequence.

Furthermore, the updated location embeddings $\mathbf{Z}_{i}=\\{z_{i}^{1},\\\
z_{i}^{2},\ldots,z_{i}^{m}\\}$ of trajectory $Tr_{i}$ are sent to a pooling
layer to extract important location information in the trajectory:

$z_{i}^{l}=\operatorname{Pooling}\left(z_{i}^{1},z_{i}^{2},\ldots,z_{i}^{m}\right),$
(7)

For $\operatorname{Pooling}$, we select the Max-Pooling to detect the
significant information. Consequently, the local representation
$z_{i}^{l}\in\mathbb{R}^{d}$ for trajectory $Tr_{i}$ is obtained by fusing the
local location information.

####  IV-C3 Global Elastic Attention Encoder

Inspired by [39, 40], we design an elastic attention module to select the most
relevant global information. Specifically, we first find the global embedding
$\mathbf{H}_{g}(i)$ for given trajectory $Tr_{i}$, and the attention score
w.r.t. trajectory $Tr_{j}$ is defined as:

$\begin{split}a_{i,j}^{s}=\frac{\mathbf{H}_{g}(i)\mathbf{H}_{g}(j)^{\mathsf{T}}}{\|\mathbf{H}_{g}(i)\|\left\|\mathbf{H}_{g}(j)^{\mathsf{T}}\right\|},\\\
\mathbf{A}_{i}^{s}=\\{a_{i,1}^{s},a_{i,2}^{s},\dots,a_{i,\|Tr\|}^{s}\\},\\\
\mathbf{W}_{i}^{g}=\operatorname{Sparsemax}\left(\mathbf{A}_{i}^{s}\right),\end{split}$
(8)

where $\|Tr\|$ is the number of trajectories, and $\operatorname{Sparsemax}$
is an alternative to $\operatorname{Softmax}$ which tends to yield sparse
probability distributions:

$\operatorname{Sparsemax}(\bm{x})=\underset{\bm{p}\in\Delta^{d}}{\operatorname{argmin}}\|\bm{p}-\bm{x}\|^{2},$
(9)

where $\Delta^{d}=\left\\{\bm{p}\in\mathbb{R}^{d}:\bm{p}\geq
0,\|\bm{p}\|_{1}=1\right\\}$. The predictive distribution
$\bm{p}^{*}=\operatorname{Sparsemax}(\bm{x})$ is likely to assign exactly zero
probability to low-scoring choices, which retains the most important factors.

Finally, the output of global elastic attention encoder is the weighted sum of
the global embedding vectors based on attention weights $\mathbf{W}_{i}^{g}$:

$z_{i}^{g}=\mathbf{W}_{i}^{g}\mathbf{H}_{g},$ (10)

where $z_{i}^{g}\in\mathbb{R}^{d}$ is the global representation of trajectory
${Tr}_{i}$.

###  IV-D Linking Layer

The linking layer aims to obtain the probability distribution of users
(labels) from the representations learned by hierarchical spatio-temporal
attention networks. The linking layer first concatenates $z_{i}^{l}$ and
$z_{i}^{g}$ for each trajectory to obtain a higher-level representation. Then,
a fully connected layer is used to project the high-level representation into
a vector with $|\mathcal{U}|$ dimension. The formulation is as follows:

$\mathbf{y}_{i}=\left(W_{c}\left[\begin{array}[]{c}z^{l}_{i}\\\
z^{g}_{i}\end{array}\right]+b_{c}\right)$ (11)

where $\mathbf{W}_{c}\in\mathbb{R}^{|\mathcal{U}|\times 2d}$ and
$b_{c}\in\mathbb{R}^{|\mathcal{U}|}$ are learnable weight matrix and bias, and
the vector $\mathbf{y}_{i}$ is the estimated probability of users for
trajectory $Tr_{i}$.

To train our model, we apply cross-entropy as loss function and use back
propagation algorithm to optimize our model. We define our cross-entropy-based
loss function as follows:

$\mathcal{L}(\Theta)=-\frac{1}{\zeta}\sum_{i=1}^{\zeta}c_{i}\log\left(\sigma\left(\mathbf{y}_{i}\right)\right)+\frac{\lambda}{2}\|\Theta\|^{2}$
(12)

where $c_{i}$ is the one-hot ground truth label of trajectory ${Tr}_{i}$,
$\sigma(\cdot)$ is the softmax function, $\zeta$ is the number of training
trajectories, and $\Theta$ is the set of all trainable parameters. $\lambda$
is an L2 regularization hyperparameter to alleviate overfitting.

###  IV-E Algorithm Pseudo-Code

Algorithm 1 shows the pseudo-code of our proposed AttnTUL framework guided by
the above objective function (i.e., Eq. (12)).

Algorithm 1 The Learning Process of AttnTUL

0: Input local spatial graph $\mathcal{G}_{l}$, global spatial graph
$\mathcal{G}_{g}$, feature matrix $\mathbf{X}_{l}$ and $\mathbf{X}_{g}$,
embedding dimension $d$, the number of convolution layers $l_{n}$

0: Model parameters $\mathbf{\Theta}$

1: while ! convergence do

2: Perform graph convolutional networks

3: for $i=1$ to $l_{n}$ do

4:
$\mathbf{H}_{l}^{(i)}\leftarrow\operatorname{ReLU}\left(\tilde{\mathbf{D}}_{l}^{-\frac{1}{2}}\tilde{\mathbf{A}}_{l}\tilde{\mathbf{D}}_{l}^{-\frac{1}{2}}\mathbf{H}_{l}^{(i-1)}\mathbf{W}_{l}^{(i-1)}\right)$;

5:
$\mathbf{H}_{g}^{(i)}\leftarrow\operatorname{ReLU}\left(\tilde{\mathbf{D}}_{g}^{-\frac{1}{2}}\tilde{\mathbf{A}}_{g}\tilde{\mathbf{D}}_{g}^{-\frac{1}{2}}\mathbf{H}_{g}^{(i-1)}\mathbf{W}_{g}^{(i-1)}\right)$;

6: end for

7:
$\mathbf{X}\leftarrow\operatorname{Tanh}\left(FC([\mathbf{W}_{t}t+b_{t};\mathbf{W}_{s}s+b_{s};\mathbf{H}_{l}])\right)$;

8: Get $z_{i}^{l}$ using Eqs. (4)-(7);

9: Get $z_{i}^{g}$ using Eqs. (9)-(10);

10:
$\mathbf{y}_{i}\leftarrow\left(W_{c}\left[{z}_{i}^{l};{z}_{i}^{g}\right]+b_{c}\right)$

11: Calculate $\mathcal{L}$ using Eq. (12);

12: Back propagation and update parameters in AttnTUL;

13: end while

14: Return $\mathbf{\Theta}$;

We now analyze the time complexity of our model. The time consumption of our
model mainly lies in spatial GCNs, temporal self-attention encoder, and global
elastic attention encoder. First, the time complexity of spatial GCN block is
$O(|\mathcal{E}|d)$ and $O(|\mathcal{V}|^{2}d)$ for the GCN operation and the
spatial attention operation, respectively, for every iteration. Second, for
each trajectory, the time complexity of temporal self-attention encoder is
$O(m^{2}d)$ for the multi-head self-attention operation for each layer. It is
clear that the time complexity of the global elastic attention encoder is much
smaller than that of the temporal self-attention encoder. Therefore, the time
complexity of our model is mainly composed of the spatial GCNs and the
temporal self-attention encoder, and also depends on the number of layers of
networks, the number of trajectories, and the average length of trajectories.

##  V Experiments

TABLE II: Statistics of the datasets. traj.: trajectories, $\overline{len}$: average length of trajectories, and H: hour(s). Datasets | #users | #traj. | #points | #POIs | $\tau$ | $\overline{len}$
---|---|---|---|---|---|---
Gowalla | 547 | 38,567 | 15,967 | 15,892 | 6H | 2
222 | 18,808 | 11,979 | 11,960 | 6H | 3
PrivateCar | 71 | 4,178 | 135,085 | 10,493 | 1H | 32
42 | 2,797 | 87,719 | 7,514 | 1H | 31
GeoLife | 90 | 6,035 | 945,971 | 23,369 | 3H | 157
56 | 4,064 | 768,533 | 19,384 | 3H | 189

In this section, we evaluate our proposed model on three types of real-world
mobility datasets. The following research questions (RQs) are used to guide
our experiments:

  * •

RQ1. How does our AttnTUL perform in TUL problem on real-world datasets
compared to existing methods?

  * •

RQ2. How does each component contribute to the performance of the proposed
AttnTUL?

  * •

RQ3. How does AttnTUL perform with different parameter settings (e.g., grid
size $s$, dimension $d$, and time window size)?

  * •

RQ4. Whether the trajectory representation learned by our AttnTUL is better
than DNN-based baselines?

  * •

RQ5. How does our AttnTUL perform efficiently compared to existing methods?

###  V-A Datasets

We conduct extensive experiments on three publicly available real-world
datasets: Gowalla111http://snap.stanford.edu/data/loc-gowalla.html,
PrivateCar222https://github.com/HunanUniversityZhuXiao/PrivateCarTrajectoryData,
and GeoLife333https://www.microsoft.com/en-us/research/project/geolife-
building-social-networks-using-human-location-history/.

  * •

Gowalla [10] is a user check-in dataset from a location based social network
service. For each user, we concatenate all check-in locations to form a
trajectory which will be further divided into sub-trajectories based on given
time interval.

  * •

PrivateCar [41] is a GPS trajectory dataset of private cars collected in
Shenzhen, China from January 1 to January 15 in 2016. The sampling rate of the
private car trajectory dataset is relatively high, 1$\sim$60 seconds (average:
15.3 seconds and standard deviation: 7.8 seconds).

  * •

GeoLife [42] is a GPS trajectory dataset collected in Beijing from April 2007
to August 2012. This dataset includes a broad range of users’ outdoor
movements, including sightseeing, hiking, cycling and so on. 91% of the
trajectories are logged densely, e.g., every 1$\sim$5 seconds or every
5$\sim$10 meters per point.

Notice that our model does not requires POI data. Some baselines (e.g., TULER
and TULVAE) are designed to work on sparse check-in data. To ensure fair
comparison, we map GPS trajectories to POI check-in data to make these
baselines can handle GPS trajectory data. To fairly reproduce the results of
baselines, we crawl POIs in Shenzhen and Beijing from
BaiduMap444https://map.baidu.com/ as the additional geographical context for
PrivateCar and GeoLife datasets.

In order to check the robustness of our model, we select two different number
of users from each dataset. The statistics of these datasets are summarized in
Table II. Following [10], $\tau$ is set as a reasonable time interval on
different datasets (i.e., 6 hours, 1 hour and 3 hours for Gowalla, PrivateCar
and GeoLife datasets, respectively).

TABLE III: Performance comparison with deep neural network models on three real-world datasets. Dataset | Methods | ACC@1 | ACC@5 | Macro-P | Macro-R | Macro-F1 | ACC@1 | ACC@5 | Macro-P | Macro-R | Macro-F1
---|---|---|---|---|---|---|---|---|---|---|---
$|\mathcal{U}|=222$ | $|\mathcal{U}|=547$
Gowalla | TULER-L | 41.67% | 51.23% | 43.45% | 34.11% | 36.03% | 37.61% | 46.97% | 40.96% | 32.47% | 34.24%
TULER-G | 41.56% | 50.96% | 41.06% | 33.08% | 34.64% |  38.88% | 48.61% |  42.20% |  33.69% |  35.15%
Bi-TULER | 41.19% | 50.36% | 41.88% | 33.92% | 35.83% | 36.88% | 46.85% | 41.09% | 32.20% | 33.80%
TULVAE | 40.13% | 49.72% | 39.71% | 32.01% | 33.68% | 37.18% | 46.44% | 40.39% | 32.30% | 33.67%
DeepTUL |  42.36% | 51.87% | 43.81% | 35.32% |  37.22% | 37.99% | 48.16% | 41.15% | 32.96% | 34.48%
DPLink | 41.51% |  52.94% | 41.32% |  35.36% | 36.15% | 37.19% |  49.72% | 36.11% | 33.18% | 32.65%
T3S | 40.80% | 50.04% |  44.52% | 33.68% | 35.77% | 34.53% | 45.97% | 35.58% | 30.76% | 30.50%
AttnTUL |  46.17% |  55.44% |  45.92% |  39.54% |  40.03% |  44.90% |  54.72% |  45.40% |  38.44% |  39.63%
PrivateCar |  | $|\mathcal{U}|=42$ | $|\mathcal{U}|=71$
TULER-L | 21.92% | 44.90% | 19.41% | 21.05% | 18.42% | 15.43% | 32.12% | 15.20% | 12.47% | 12.16%
TULER-G | 21.92% | 45.94% | 19.35% | 19.61% | 18.01% | 16.13% | 32.77% | 15.96% | 14.37% | 13.29%
Bi-TULER | 22.46% | 47.79% | 21.52% | 21.54% | 19.76% | 16.57% | 36.62% | 15.76% | 15.14% | 13.80%
TULVAE | 23.98% |  50.44% | 25.34% | 20.34% | 20.45% | 16.89% | 31.81% | 16.92% | 15.38% | 14.59%
DeepTUL | 22.99% | 49.71% | 22.95% | 22.53% | 20.16% | 17.65% | 33.09% | 15.68% | 16.97% | 14.24%
DPLink | 23.47% | 47.12% | 25.36% | 23.32% | 22.23% | 20.71% |  41.79% | 19.14% | 16.83% | 15.27%
T3S |  26.53% | 47.90% |  31.30% |  25.07% |  25.59% |  21.28% | 39.45% |  24.13% |  20.05% |  20.01%
| AttnTUL |  35.11% |  60.40% |  33.24% |  32.80% |  31.49% |  31.25% |  54.74% |  32.25% |  32.24% |  30.21%
GeoLife |  | $|\mathcal{U}|=56$ | $|\mathcal{U}|=90$
TULER-L | 41.79% | 71.81% | 33.78% | 34.94% | 31.70% | 36.84% | 60.28% | 32.91% | 30.41% | 29.32%
TULER-G | 43.93% | 70.08% | 37.09% | 36.50% | 33.33% | 35.51% | 61.24% | 33.88% | 31.73% | 30.25%
Bi-TULER | 44.50% | 74.09% | 38.14% | 35.82% | 33.76% | 37.99% | 61.85% | 35.82% | 33.16% | 32.12%
TULVAE | 46.04% | 70.99% | 42.32% | 39.73% | 36.87% | 39.27% | 64.30% | 36.23% | 33.83% | 32.31%
DeepTUL | 51.23% | 79.19% | 45.84% | 41.82% | 39.36% | 44.92% | 69.93% | 38.19% | 38.35% | 35.99%
DPLink |  53.80% |  80.03% |  48.23% |  46.63% |  45.03% |  47.83% |  73.95% |  43.93% |  40.80% |  39.63%
T3S | 51.10% | 77.40% | 45.47% | 43.84% | 43.13% | 44.33% | 70.65% | 40.18% | 39.52% | 38.18%
| AttnTUL |  61.37% |  85.87% |  59.20% |  59.59% |  58.53% |  53.92% |  79.47% |  49.94% |  50.29% |  48.24%

###  V-B Baselines

In our evaluation, we compare our AttnTUL against the following two categories
of baselines.

####  V-B1 Classic models

  * •

LCSS [16] – It adopts LCSS to compute trajectory similarity, and searches the
most similar trajectory in training set to find the corresponding user.

  * •

LDA [43] – We apply Linear Discriminant Analysis (LDA) to TUL task by
embedding trajectories into one-hot vectors and using SVD to decompose the
within-class scatter matrix.

  * •

DT [44] – Decision Tree (DT) is a classic classification method for trajectory
data. We use entropy as the criterion in TUL problem, which shows better
performance than Gini index.

  * •

SR [19, 45] – Signature Representation (SR) is a state-of-the-art trajectory
similarity measure for moving object linking.

####  V-B2 Deep neural network models

  * •

TULER [10] – This is the original RNN model for solving TUL task. There are
three variants: RNN with Gated Recurrent Unit (TULER-G), Long Short-Term
Memory (TULER-L) and bidirectional LSTM (Bi-TULER).

  * •

TULVAE [9] – It utilizes VAE to learn the hierarchical semantics of trajectory
with stochastic latent variables that span hidden states in RNN.

  * •

DeepTUL [8] – This is a recurrent network with attention mechanism to solve
TUL problem, which is a state-of-the-art method. It learns from labeled
historical trajectory to capture multi-periodic nature of user mobility and
alleviate the data sparsity problem.

  * •

DPLink [7, 29] – DPLink is a state-of-the-art method to link user accounts
from heterogeneous mobility data.

  * •

T3S [24] – T3S is a state-of-the-art trajectory representation learning method
for trajectory similarity computation.

Notice that we extend T3S with multi-class classification supervision to
support TUL prediction. DPLink also cannot be directly applied to TUL problem,
thus we extend it to perform user identification in a single mobility dataset
in our experiments. The source code of our model is available at
https://anonymous.4open.science/r/Attn_TUL.

Figure 4: Performance comparison with classic models.

###  V-C Evaluation Metrics

We use the widely used $ACC@k$, Macro-P, Macro-R and Macro-F1 to evaluate the
performance, which are common metrics in multi-classification task.
Specifically, $ACC@K$ is used to evaluate the accuracy of TUL prediction as:

$ACC@K=\frac{|\\{Tr_{i}\in\overline{Tr}:u^{*}(Tr_{i})\in\mathcal{U}_{K}(Tr_{i})\\}|}{|\overline{Tr}|},$
(13)

where $u^{*}(Tr_{i})$ is the ground truth user, and $\mathcal{U}_{K}(Tr_{i})$
is the predicted top-$K$ user set. It is considered correct if the ground
truth user $u^{*}(Tr_{i})$ lies within the predicted top-k user set
$\mathcal{U}_{K}(Tr_{i})$.

Macro-F1 is regarded as an overall performance indicator, taking into account
the precision and recall across all classes in multi-classification task,
which is defined as:

$\begin{split}Macro\text{--}P=\frac{1}{|c|}\sum^{|c|}_{i=1}{P_{i}},\\\
Macro\text{--}R=\frac{1}{|c|}\sum^{|c|}_{i=1}{R_{i}},\\\
Macro\text{--}F1=\frac{1}{|c|}\sum^{|c|}_{i=1}{\frac{2\times P_{i}\times
R_{i}}{P_{i}+R_{i}}}\end{split}$ (14)

where $|c|$ is number of classes, and $P_{i}$ and $R_{i}$ are precision and
recall of each class (user in TUL) respectively.

###  V-D Experimental Settings

In our experiments, we use the first 60% of each user’s trajectories as the
training set on all datasets, the following 20% as the validation set, and the
remaining 20% as test set.

We use the source code released by authors for baselines, and use the
parameter setting recommended in the original paper and fine-tune them on each
dataset to be optimal. In the experiment, we set embedding dimension $d$ to
128, grid size $s$ to 40 meters on Gowalla and 120 meters on the other two
datasets, the length of time window to 2 hours, 10 minutes and 20 minutes on
Gowalla, PrivateCar and GeoLife, the number of GCN layers to 2, the number of
self-attention layers to 3, $\\#head$ to 4, and $\lambda$ to $5e$-4 for our
AttnTUL. For fair comparison, for all learning methods, we set epoch to 80,
batch size to 16, dropout to 0.5, tune learning rate from 0.0001 to 0.01, use
early stopping mechanism, and set patience to 10 to avoid over fitting. In
each experiment, we repeat 10 runs and report the average.

All experiments for model efficiency evaluation are conducted on a machine
with Intel Xeon Gold<EMAIL_ADDRESS>12 cores CPU, 192GB memory, and NVIDIA Tesla
V100-SXM2 (16GB) GPU.

Notice that all the user personal information in our datasets are anonymized
to protect user’s privacy.

###  V-E Experiment Results

####  V-E1 Overall Performance (RQ1)

We first evaluate the overall performance of the proposed model on three
categories of trajectory datasets in comparison with state-of-the-art
baselines. The overall performance is reported in Table III, where the best is
shown in bold and the second best is shown as underlined. We also show the
comparison with classic models in Figure 4.

Notice that SML-TUL [13] and TGAN [12] are not compared in our experiments
because there are no publicly available source codes for them. However,
according to the results reported in [13], our AttnTUL significantly
outperforms SML-TUL and TGAN in terms of Acc@$k$ and Macro-F1 on Gowalla, even
though our AttnTUL links more users on the same Gowalla dataset. The specific
results are as follows: AttnTUL vs. SML-TUL vs. TGAN: 46.17% vs. 45.71% vs.
43.79% in ACC@1, and 40.03% vs 36.15% vs. 33.06% in Macro-F1 on Gowalla.

From the results in Figure 4, our AttnTUL significantly outperforms all
classic baseline methods in terms of all evaluation metrics, achieving 23.22%,
67.02%, 17.44% improvements in terms of ACC@1 over SR method on Gowalla,
PrivateCar, and Geolife datasets, respectively. SR performs better than other
classic baselines in terms of ACC@1, ACC@5, and Macro-F1 on three datasets as
it considers the similarity of two trajectories from four representation
strategies (i.e., sequential, temporal ,spatial and spatiotemporal). However,
SR is still based on the defined distance calculation, and cannot
automatically learn the similarity or dependency between trajectories based on
the relationship among trajectories on different mobility datasets.

From the results in Table III, we can see that AttnTUL achieves the best
performance in terms of all metrics on three different categories of
trajectory datasets. This is because our designed local and global graph model
effectively captures both micro- and macro-spatial features for spatio-
temporal trajectories. In addition, our hierarchical spatio-temporal attention
network can learn the long-term dependencies in time dimension and adaptively
fuse the local and global representations. This is main reason that our
AttnTUL performs the best on both sparse check-in dataset (i.e., Gowalla) and
dense GPS trajectory datasets (i.e., PrivateCar and GeoLife). Results in Table
III show that our model significantly outperforms state-of-the-art baselines
by 12.73%$\sim$46.85% and 18.90%$\sim$50.97% improvements in terms of ACC@1
and Macro-F1. Specifically, AttnTUL achieves average gains of 21.75% ACC@1 and
24.34% Macro-F1 score in comparison to the best performed baseline across all
datasets. Considering that the performance gain in TUL prediction reported in
recent works [8, 9] is usually around 2.74-9.26% ACC@1 and 1.11-11.00%
Macro-F1, this performance improvement achieved by our AttnTUL is significant.
Among various baselines, DPLink performs the best on most of metrics, because
they extract comprehensive trajectory features. However, our AttnTUL
consistently outperforms DPLink by 11.23-50.89% ACC@1 and 10.73-97.84%
Macro-F1 score across all datasets, which suggests the rationality of our
designed hierarchical spatio-temporal attention network architecture. Although
T3S and DeepTUL use the attentive recurrent neural framework, they are still
limited by the only consideration of the information within the trajectory,
and do not consider the complex cross-trajectory correlations.

We also observe that model performance on data with fewer users is better than
that on data with more users. This is intuitive as the more users the more
difficult the classification becomes. Among all baselines, DeepTUL and T3S
perform best in terms of ACC@1 and Macro-F1 on both Gowalla and PrivateCar
datasets, and DPLink performs the best in terms of ACC@1 and Macro-F1 on
GeoLife dataset. However, our AttnTUL achieves more improvement over the best
performed baseline in terms of ACC@1 and Macro-F1 on data with more users,
e.g., on Gowalla, 15.48% improvement in ACC@1 for $|\mathcal{U}|=547$ vs.
8.99% improvement for $|\mathcal{U}|=222$, and on PrivateCar, 46.85%
improvement in ACC@1 for $|\mathcal{U}|=71$ vs. 32.34% improvement for
$|\mathcal{U}|=42$.

TABLE IV: Results of ablation study. Mac: Macro. Data | Methods | ACC@1 | ACC@5 | Mac-P | Mac-R | Mac-F1
---|---|---|---|---|---|---
Gowalla ($|\mathcal{U}|$=222) | TUL-L | 43.66% | 53.28% | 45.14% | 37.95% | 38.56%
TUL-G | 41.87% | 52.61% | 37.03% | 33.31% | 33.29%
TUL-SA | 43.20% | 52.70% |  45.82% | 36.58% | 37.99%
TUL-EA | 39.99% | 51.58% | 37.12% | 31.73% | 32.08%
TUL-TS |  44.01% |  54.13% | 45.47% |  38.72% |  39.92%
AttnTUL |  46.17% |  55.44% |  45.92% |  39.54% |  40.03%
PrivateCar ($|\mathcal{U}|$=71) | TUL-L | 19.83% | 44.74% | 18.26% | 20.86% | 16.01%
TUL-G | 30.09% | 53.14% | 27.50% | 31.05% | 27.16%
TUL-SA | 28.31% |  53.92% | 27.40% | 27.67% | 24.97%
TUL-EA | 28.49% | 52.12% |  28.36% | 24.54% | 23.64%
TUL-TS |  30.58% | 53.20% | 26.96% |  31.52% |  27.41%
AttnTUL |  31.25% |  54.74% |  32.25% |  32.24% |  30.21%
GeoLife ($|\mathcal{U}|$=90) | TUL-L | 49.51% | 78.43% | 45.49% | 45.48% | 43.04%
TUL-G | 48.97% | 75.46% | 43.82% | 43.61% | 42.03%
TUL-SA | 51.06% | 78.65% | 47.01% | 47.15% | 44.01%
TUL-EA | 46.38% | 74.35% | 41.98% | 40.56% | 38.59%
TUL-TS |  52.07% |  79.25% |  47.58% |  47.41% |  45.02%
AttnTUL |  53.92% |  79.47% |  49.94% |  50.29% |  48.24%

(a) Gowalla

(b) PrivateCar

Figure 5: Parameter sensitivity w.r.t. grid size $s$, embedding dimensionality
$d$, the number of attentive representation heads $\\#head$ and time window
length $T_{W}$ on Gowalla and PrivateCar data. Performances are measured by
ACC@1, Macro-P, Macro-F1.

####  V-E2 Ablation Study (RQ2)

To validate the effectiveness of each component in AttnTUL, we further conduct
the ablation study. We compare our AttnTUL with five carefully designed
variants. Despite the changed part(s), all variants have the same framework
structure and parameter settings.

  * •

TUL-L – It removes the whole local spatial module to demonstrate the
importance of local modeling.

  * •

TUL-G – It removes the whole global spatial module to demonstrate the
importance of global modeling.

  * •

TUL-SA – It removes the self attention module and directly sends the location
embeddings to pooling layer to fuse local information.

  * •

TUL-EA – It uses $\operatorname{Softmax}$ to replace our proposed elastic
attention in global module.

  * •

TUL-TS – In this variant, we remove the time and state encoders to verify the
importance of them.

The results of ablation study on three datasets are shown in Table IV. As we
can see, AttnTUL outperforms all variants on three datasets, which
demonstrates that our key components all contribute to performance improvement
of AttnTUL. A noteworthy phenomenon is that TUL-TS performs the second best on
three datasets. A potential reason is that time information is not as
important as spatial information in TUL problem. Similar conclusion has also
been verified in [19, 45].

The comparison between TUL-L and AttnTUL highlights the effectiveness of the
proposed local modeling for capturing intra-trajectory dependencies in TUL
problem. The comparison between TUL-G and AttnTUL reflects the effectiveness
of the proposed global modeling for extracting inter-trajectory corrections in
TUL problem. Compared to AttnTUL, TUL-L and TUL-G perform much worse
demonstrating the importance of both local and global modelling in our model.

In addition, we can see that TUL-SA performs much worse than AttnTUL in terms
of ACC@1 on PrivateCar and GeoLife, indicating that our designed temporal
self-attention network could better capture long-term dependencies for long
sequence trajectories. Nevertheless, TUL-SA also performs worse than AttnTUL
on Gowalla datasets, which demonstrates that the self-attention mechanism can
also capture temporal dependencies for sparse check-in trajectories.
Furthermore, we also find an important observation that TUL-EA produces worse
results than TUL-G in terms of most metrics on three datasets. This adequately
demonstrates the crucial role of our designed elastic attention of global
module in extracting relevant global representation for TUL prediction.

(a) TULER-L (b) TULER-G (c) Bi-TULER (d) TULVAE

(e) DPLink (f) T3S (g) DeepTUL (h) AttnTUL

Figure 6: Spatial-temporal representation visualization of trajectories
learned by AttnTUL and other baselines on Gowalla.

(a) TULER-L (b) TULER-G (c) Bi-TULER (d) TULVAE

(e) DPLink (f) T3S (g) DeepTUL (h) AttnTUL

Figure 7: Spatial-temporal representation visualization of trajectories
learned by AttnTUL and other baselines on GeoLife.

####  V-E3 Robustness Analysis (RQ3)

We also evaluate the robustness of AttnTUL w.r.t. different settings of grid
size $s$, embedding dimension $d$, the number of heads $\\#head$ and the
length of time window $T_{W}$. The results in terms of ACC@1, Macro-P and
Macro-F1 on both sparse Gowalla ($|\mathcal{U}|=222$) and dense PrivateCar
($|\mathcal{U}|=71$) are depicted in Figure 5.

The effect of the grid size. From two left sub-figures in Figure 5, we find
that the performance of AttnTUL decreases as $s$ increases on Gowalla, while
first increases and then decreases with the growth of $s$ from 40 to 200
meters. This phenomenon is easy to understand. Recall that Gowalla is a sparse
check-in data, while PrivateCar is a dense GPS trajectory data. If grid is too
large, the spatial information would be lost, which is reflected more obvious
on sparse Gowalla than on dense PrivateCar. If grid is too small, some spatial
interactions among trajectories would not be reflected, which affects the
prediction performance.

The effect of the embedding dimension. As shown in the two sub-figures of the
second group, the performance of AttnTUL first increases and then decreases on
both Gowalla and PrivateCar as $d$ increases, reaching the best at $d=64$ and
$d=128$ on Gowalla and PrivateCar, respectively. This is because Gowalla is
very sparse, and thus few grids are involved. The lower embedding
dimensionality has little effect on it, while PrivateCar is denser. When the
dimensionality is very low, it has a greater impact on the prediction
performance. However, larger embedding dimensionality may contain superfluous
information which hurts the TUL prediction performance.

The effect of the number of heads. To investigate the effect of the number of
heads in temporal self-attention encoder, we show the evaluation results with
the settings of different head numbers in the third group of sub-figures in
Figure 5. As we can see, the performance of AttnTUL has little effect w.r.t.
the number of heads $\\#head$ on Gowalla, first increases and then decreases
on PrivateCar as $\\#head$ increases, and the model performance achieves the
best when $\\#head=4$ on PrivateCar. The possible reason is that sub-
trajectories in Gowalla are too sparse, so the intra-trajectory dependencies
are not complicated, and thus the effect of multi-head attention mechanism is
not obvious. While sub-trajectories in PrivateCar are relatively dense, and
the use of multi-head attention mechanism effectively captures the complex
temporal dependencies within the trajectory.

The effect of the length of time window. From two right sub-figures in Figure
5, we can see that the model performance also first increases and then
decreases as the length of time window increases on both Gowalla and
PrivateCar datasets. Considering the sparsity of Gowalla, denseness of
PrivateCar, and the length of trajectories in these two datasets, we vary the
length of time window from 30 to 240 minutes on Gowalla and from 2 to 30
minutes on PrivateCar. Specifically, the model performance achieves the best
when $T_{W}$ is set to 2 hours on Gowalla and 10 minutes on PrivateCar. That
is, on the sparse check-in mobility data Gowalla, when two-hour time window is
set to the same encoding, the best results are obtained, indicating that
check-ins within such a length of time can be considered to be
indistinguishable in time. Similarly, on the dense GPS trajectory data
PrivateCar, the best performance is achieved with the same encoding for the
spatial-temporal points within 10 minutes, which also shows that there is no
temporal difference between the different sub-trajectories in 10-minute time
window.

####  V-E4 Visualization (RQ4)

To further verify the effectiveness of our model in learning spatiotemporal
representation of trajectories, we adopt a visualization way to compare the
representation vectors of trajectories learned by different models.

To this end, we use t-SNE [46] to plot the latent space of trajectories
learned by DNN-based models. Specifically, we randomly select 20 users and
their corresponding trajectories from Gowalla and GeoLife. The learned
representation of each trajectory is projected to the 2D space. The
visualization results of learned trajectory reorientation on Gowalla
($|\mathcal{U}|=222$) and GeoLife ($|\mathcal{U}|=90$) are shown in Figure 6
and Figure 7, where points with the same color represent trajectories from the
same user.

From Figures 6 and 7, we can observe that the trajectory representations
generated by our AttnTUL show an apparent clustering effect, and the
clustering is tighter than other methods (i.e., Figure 6(h) and Figure 7(h)).
This indicates that AttnTUL is able to effectively distinguish trajectories
generated by different users, which is crucial for TUL prediction task.
Although DeepTUL and DPLink can also distinguish some clusters (users), there
are obviously plenty of trajectories from different users intertwined
together, and thus it is difficult to identify the correct users for these
trajectories.

Furthermore, we also observe that all baselines perform poorly on sparse
check-in dataset (i.e., Gowalla) compared to the easily distinguishable dense
GeoLife dataset, while our model effectively distinguishes the trajectories
produced by most users (see Figure 6(h)).

####  V-E5 Model Efficiency Analysis (RQ5)

(a) Classic models (b) DNN models

Figure 8: Model Efficiency Evaluation

We also compare the efficiency of our AttnTUL with all baselines on Gowalla
($|\mathcal{U}|=222$) data. We report the experiment results w.r.t. classic
methods and DNN-based methods in Figure 8.

Since classic methods have no training time, we only compare the running time.
As can be seen from Figure 8(a), the prediction time of our AttnTUL is much
less than the running time of classic methods. This is because the classic
methods need to calculate a large number of distances between trajectories, so
the time cost is relatively high. For example, LCSS, LDA, and DT all consume
more than 300 times the prediction time of our model.

From the results in Figure 8(b), we can see that the running time (i.e., the
testing time) of DNN-based models is much less than that of classic methods.
Although the testing time of our model is not the best, it is faster than
state-of-the-art DeepTUL, and the testing time is also less than 2 seconds.
Since we adopt the early stopping mechanism for all DNN-based models, the
number of rounds of early stopping is different for different models. For a
fair comparison, we report the average training time per each epoch. In terms
of model training time, the efficiency of our AttnTUL is in the middle level,
better than state-of-the-art models (i.e., TULVAE, DeepTUL, and T3S), and
worse than the simple TUL models (i.e., TULER and its variants) and DPLink. It
takes around 5.6 seconds for each epoch on Gowalla using a Tesla V100 GPU
card. Specifically, our AttnTUL is 2.4 times and 7.3 times faster than TULVAE
and DeepTUL per epoch, respectively. The potential reason is that DeepTUL
needs to use historical trajectory data, so a large number of trajectory
distances need to be calculated, while TULVAE needs to use variational
inference, which requires expensive time cost.

##  VI Conclusion

In this paper, we present a novel hierarchical spatio-temporal attention
network, called AttnTUL, for TUL problem. AttnTUL effectively learns the local
and global representations for each trajectory by the designed hierarchical
spatio-temporal attention network to classify trajectories by users. AttnTUL
first employs GCN on the constructed local and global graphs to learn
embeddings for grids and trajectories. Then, it uses a hierarchical spatio-
temporal attention network to obtain the local and global representations for
each trajectory, respectively. Eventually, a linking layer is designed to fuse
the two representation to classify trajectories by users. Experiments on three
real-world mobility datasets demonstrate that our model significantly
outperforms state-of-the-art baselines in terms of all metrics for TUL
problem. For future work, we plan to enhance our proposed AttnTUL model with
the ability of handling streaming mobility trace data for real-time
trajectory-user linking scenario.

## References

  * [1] Y. Zheng, “Trajectory data mining: an overview,” _TIST_ , vol. 6, no. 3, pp. 1–41, 2015.
  * [2] S. Wang, J. Cao, and P. Yu, “Deep learning for spatio-temporal data mining: A survey,” _TKDE_ , 2020.
  * [3] W. Liu, Z.-J. Wang, B. Yao, and J. Yin, “Geo-alm: Poi recommendation by fusing geographical information and adversarial learning mechanism.” in _IJCAI_ , vol. 7, 2019, pp. 1807–1813.
  * [4] M. Zhang, T. Li, H. Shi, Y. Li, P. Hui _et al._ , “A decomposition approach for urban anomaly detection across spatiotemporal data,” in _IJCAI_ , 2019.
  * [5] C. Huang, J. Zhang, Y. Zheng, and N. V. Chawla, “Deepcrime: Attentive hierarchical recurrent networks for crime prediction,” in _CIKM_ , 2018, pp. 1423–1432.
  * [6] Y. Chen, X. Wang, M. Fan, J. Huang, S. Yang, and W. Zhu, “Curriculum meta-learning for next poi recommendation,” in _KDD_ , 2021, pp. 2692–2702.
  * [7] J. Feng, M. Zhang, H. Wang, Z. Yang, C. Zhang, Y. Li, and D. Jin, “Dplink: User identity linkage via deep neural network from heterogeneous mobility data,” in _WWW_ , 2019, pp. 459–469.
  * [8] C. Miao, J. Wang, H. Yu, W. Zhang, and Y. Qi, “Trajectory-user linking with attentive recurrent network,” in _AAMAS_ , 2020, pp. 878–886.
  * [9] F. Zhou, Q. Gao, G. Trajcevski, K. Zhang, T. Zhong, and F. Zhang, “Trajectory-user linking via variational autoencoder,” in _IJCAI_ , 2018, pp. 3212–3218.
  * [10] Q. Gao, F. Zhou, K. Zhang, G. Trajcevski, X. Luo, and F. Zhang, “Identifying human mobility via trajectory embeddings,” in _IJCAI_ , vol. 17, 2017, pp. 1689–1695.
  * [11] Q. Gao, F. Zhang, F. Yao, A. Li, L. Mei, and F. Zhou, “Adversarial mobility learning for human trajectory classification,” _IEEE Access_ , vol. 8, pp. 20 563–20 576, 2020.
  * [12] F. Zhou, R. Yin, G. Trajcevski, K. Zhang, J. Wu, and A. Khokhar, “Improving human mobility identification with trajectory augmentation,” _GeoInformatica_ , vol. 25, no. 3, pp. 453–483, 2021.
  * [13] F. Zhou, Y. Dai, Q. Gao, P. Wang, and T. Zhong, “Self-supervised human mobility learning for next location prediction and trajectory classification,” _Knowledge-Based Systems_ , p. 107214, 2021.
  * [14] U. Khandelwal, H. He, P. Qi, and D. Jurafsky, “Sharp nearby, fuzzy far away: How neural language models use context,” in _ACL_ , 2018, pp. 284–294.
  * [15] E. J. Keogh and M. J. Pazzani, “Scaling up dynamic time warping for datamining applications,” in _KDD_ , 2000, pp. 285–289.
  * [16] J. J.-C. Ying, E. H.-C. Lu, W.-C. Lee, T.-C. Weng, and V. S. Tseng, “Mining user similarity from semantic trajectories,” in _SIGSPATIAL Workshop on LBSNs_ , 2010, pp. 19–26.
  * [17] S. Atev, G. Miller, and N. P. Papanikolopoulos, “Clustering of vehicle trajectories,” _IEEE Transactions on Intelligent Transportation Systems_ , vol. 11, no. 3, pp. 647–657, 2010.
  * [18] S. Shang, L. Chen, Z. Wei, C. S. Jensen, K. Zheng, and P. Kalnis, “Trajectory similarity join in spatial networks,” _VLDB_ , vol. 10, no. 11, 2017.
  * [19] F. Jin, W. Hua, J. Xu, and X. Zhou, “Moving object linking based on historical trace,” in _ICDE_. IEEE, 2019, pp. 1058–1069.
  * [20] X. Li, K. Zhao, G. Cong, C. S. Jensen, and W. Wei, “Deep representation learning for trajectory similarity computation,” in _ICDE_. IEEE, 2018, pp. 617–628.
  * [21] D. Yao, G. Cong, C. Zhang, and J. Bi, “Computing trajectory similarity in linear time: A generic seed-guided neural metric learning approach,” in _ICDE_. IEEE, 2019, pp. 1358–1369.
  * [22] D. Yao, G. Cong, C. Zhang, X. Meng, R. Duan, and J. Bi, “A linear time approach to computing time series similarity based on deep metric learning,” _TKDE_ , 2020.
  * [23] H. Zhang, X. Zhang, Q. Jiang, B. Zheng, Z. Sun, W. Sun, and C. Wang, “Trajectory similarity learning with auxiliary supervision and optimal matching,” in _IJCAI_. AAAI, 2020, pp. 3209–3215.
  * [24] P. Yang, H. Wang, Y. Zhang, L. Qin, W. Zhang, and X. Lin, “T3s: Effective representation learning for trajectory similarity computation,” in _ICDE_. IEEE, 2021, pp. 2183–2188.
  * [25] Y. Zheng, Q. Li, Y. Chen, X. Xie, and W.-Y. Ma, “Understanding mobility based on gps data,” in _UbiComp_ , 2008, pp. 312–321.
  * [26] Y. Zhu, Y. Zheng, L. Zhang, D. Santani, X. Xie, and Q. Yang, “Inferring taxi status using gps trajectories,” _arXiv preprint arXiv:1205.4378_ , 2012.
  * [27] Y. Yu, H. Tang, F. Wang, L. Wu, T. Qian, T. Sun, and Y. Xu, “Tulsn: Siamese network for trajectory-user linking,” in _IJCNN_. IEEE, 2020, pp. 1–8.
  * [28] T. Sun, Y. Xu, F. Wang, L. Wu, T. Qian, and Z. Shao, “Trajectory-user link with attention recurrent networks,” in _ICPR_. IEEE, 2021, pp. 4589–4596.
  * [29] J. Feng, Y. Li, M. Zhang, Z. Yang, H. Wang, H. Cao, and D. Jin, “User identity linkage via co-attentional neural network from heterogeneous mobility data,” _TKDE_ , pp. 1–1, 2020.
  * [30] D. Bahdanau, K. H. Cho, and Y. Bengio, “Neural machine translation by jointly learning to align and translate,” in _ICLR_ , 2015.
  * [31] Q. Gao, F. Zhou, G. Trajcevski, K. Zhang, T. Zhong, and F. Zhang, “Predicting human mobility via variational attention,” in _WWW_ , 2019, pp. 2750–2756.
  * [32] F. Zhou, X. Yue, G. Trajcevski, T. Zhong, and K. Zhang, “Context-aware variational trajectory encoding and human mobility inference,” in _WWW_ , 2019, pp. 3469–3475.
  * [33] J. Wang, N. Wu, W. X. Zhao, F. Peng, and X. Lin, “Empowering a* search algorithms with neural networks for personalized route recommendation,” in _KDD_ , 2019, pp. 539–547.
  * [34] Z. Wu, S. Pan, F. Chen, G. Long, C. Zhang, and S. Y. Philip, “A comprehensive survey on graph neural networks,” _TNNLS_ , vol. 32, no. 1, pp. 4–24, 2020\.
  * [35] W. L. Hamilton, R. Ying, and J. Leskovec, “Inductive representation learning on large graphs,” in _NeurIPS_ , 2017, pp. 1025–1035.
  * [36] T. N. Kipf and M. Welling, “Semi-supervised classification with graph convolutional networks,” in _ICLR_ , 2017.
  * [37] P. Wang, X. Li, Y. Zheng, C. Aggarwal, and Y. Fu, “Spatiotemporal representation learning for driving behavior analysis: A joint perspective of peer and temporal dependencies,” _TKDE_ , 2019.
  * [38] A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, Ł. Kaiser, and I. Polosukhin, “Attention is all you need,” in _NeurIPS_ , 2017, pp. 5998–6008.
  * [39] A. Martins and R. Astudillo, “From softmax to sparsemax: A sparse model of attention and multi-label classification,” in _ICML_. PMLR, 2016, pp. 1614–1623.
  * [40] B. Peters, V. Niculae, and A. F. Martins, “Sparse sequence-to-sequence models,” in _ACL_ , 2019, pp. 1504–1519.
  * [41] Y. Huang, Z. Xiao, X. Yu, D. Wang, V. Havyarimana, and J. Bai, “Road network construction with complex intersections based on sparsely sampled private car trajectory data,” _TKDD_ , vol. 13, no. 3, pp. 1–28, 2019.
  * [42] Y. Zheng, X. Xie, W.-Y. Ma _et al._ , “Geolife: A collaborative social networking service among user, location and trajectory.” _IEEE Data Eng. Bull._ , vol. 33, no. 2, pp. 32–39, 2010.
  * [43] H. R. Shahdoosti and F. Mirzapour, “Spectral–spatial feature extraction using orthogonal linear discriminant analysis for classification of hyperspectral data,” _European Journal of Remote Sensing_ , vol. 50, no. 1, pp. 111–124, 2017.
  * [44] Z. Jiang, “A survey on spatial prediction methods,” _TKDE_ , vol. 31, no. 9, pp. 1645–1664, 2018.
  * [45] F. Jin, W. Hua, T. Zhou, J. Xu, M. Francia, M. Orowska, and X. Zhou, “Trajectory-based spatiotemporal entity linking,” _TKDE_ , 2020.
  * [46] L. Van der Maaten and G. Hinton, “Visualizing data using t-sne.” _Journal of machine learning research_ , vol. 9, no. 11, 2008.