Unsupervised Path Representation Learning with Curriculum Negative Sampling

1 Introduction

Path representations are crucial for various transportation applications, e.g., travel cost estimation [Hu et al., 2020; Pedersen et al., 2020a], routing [Guo et al., 2020; Pedersen et al., 2020b], path recommendation [Yang and Yang, 2020; Guo et al., 2018], and traffic analysis [Hu et al., 2019; Cirstea et al., 2021]. Path representation learning (PRL) aims to obtain distinguishable path representations for different

∗Corresponding Author: Jilin Hu

paths in a transportation network and hence facilitating various downstream applications. Existing studies on PRL often learn path representations in a supervised manner, which has two limitations. First, they require a large amount of labelled training data. Second, the learned path representations are task-specific, e.g., working well for the task with labels, but generalize poorly to other tasks. The two limitations restrict supervised path representation learning from broader usage, thus calling for unsupervised path representation learning.

Although unsupervised graph representation learning methods exist, they are not designed to capture representations of paths. Node representation learning [Tang et al., 2015; Grover and Leskovec, 2016] learns representations for individual nodes in a graph but does not consider paths, i.e., sequences of nodes. Simply aggregating the node representations of the nodes in a path fails to capture the sequential information in paths. Whole graph representation learning [Sun et al., 2020] learns representations for different graphs, while path representation learning considers different paths from the same graph. In addition, unsupervised graph representation learning often utilize random negative sampling to enable training, which is ineffective for path representation learning.

We propose an unsupervised path representation learning framework Path InfoMax (PIM), including a curriculum negative sampling method and a path representation learning method. First, we propose a curriculum negative sampling strategy to generate a small number of negative paths for an input path. Instead of randomly select other input paths as negative paths, the strategy follows the principles of curriculum learning [Bengio et al., 2009] to first generate paths that are largely different from the input path and thus are easy to be distinguished from the input path. Then, we gradually generate paths that are increasingly similar to the input path and thus are more difficult to be distinguished from the input path. The proposed curriculum negative sampling facilitates effective learning of distinguishable path representations.

Next, we propose two different discriminators, a path-path discriminator and a path-node discriminator, to jointly learn path representations. The path-path discriminator captures the representation differences between an input path and its negative paths, which we refer to as a global view. The pathnode discriminator captures the representation difference between an input path and the representations of the nodes that only appear in its negative paths, which we refer to as a local view. The two discriminators ensure the quality of the learned path representations, because they are distinguishable from not only the representations of negative paths from a global view but also the representations of the nodes in negative paths from a local view. To the best of our knowledge, PIM is the first work that studies unsupervised path representation learning. We make the following contributions.

1. We propose a curriculum negative sampling strategy for path representation learning.
2. We propose the path-path and path-node discriminators to learn jointly path representations from a global and a local view.
3. We conduct extensive experiments on two data sets with two downstream tasks to demonstrate the effectiveness of PIM.

2 RelatedWork

Path Representation Learning. Existing proposals on path representation learning are all under the supervised learning setting. Such proposals often require large amount of labeled training data and the learned path representations cannot be easily reused for other tasks. For example, Deepcas [Li et al., 2017], ProxEmbed [Liu et al., 2017], and PathRank [Yang et al., 2020; Yang and Yang, 2020] employ different kinds of RNNs to combine node representations of the nodes in a path to obtain a path representation. Then, the training is performed in an end-to-end fashion by using the labeled training data. Instead, we propose an unsupervised path representation learning framework PIM that does not require labeled training data and it generalizes nicely to multiple downstream tasks (cf. Table 1 in Section 5.2). In addition, PIM can be used as a pre-training method to enhance existing supervised path representation learning (cf. Figure 3 in Section 5.2). An unsupervised trajectory representation learning method transforms trajectories into images and thus do not apply on paths in graphs [Kieu et al., 2018].

Mutual Information Maximization on Graphs. Motivated by Deep InfoMax [Hjelm et al., 2019], mutual information maximization has been applied for unsupervised graph representation learning. Deep Graph Infomax (DGI) [Velickovic et al., 2019] and Graph Mutual Information (GMI) [Peng et al., 2020] learn node representations and InfoGraph [Sun et al., 2020] learns whole graph representations. Here, negative samples are often randomly drawn from a different graph and the mutual information only considers a local view, e.g., a node representation vs. a graph representation. In PIM, we propose a curriculum negative sample strategy to generate negative paths with different overlapping nodes with the input paths from the same graph, which facilitates training. Other advanced negative sampling approaches exist [Wang et al., 2018; Ding et al., 2020], but they are not proposed for graphs and do not follow curriculum learning. In addition, we compute mutual information on both a local view (i.e., the representations of input paths vs. the node representations of negative paths) and a global view (i.e., the representations of input paths vs. negative paths) and use them jointly to train the model, which improves accuracy.

3 Preliminaries

Graph. We consider a directed graph G = (V, E), where V is the node set and E is the edge set and we have |V| = N and |E| = M. Each node Vi ∈ V is associated with a node feature vector vi ∈ RD .

Path. A path P = 〈V1, V2, . . . , VZ〉 is a sequence of nodes, where Z is the path length and P.s = V1 and P.d = VZ are the source and destination of path P, respectively. Each pair of adjacent nodes (Vk, Vk+1) is connected by an edge in E, 1 ≤ k < Z. We use IV (P) ∈ RZ×D to represent the concatenation of the node feature vectors of the nodes in path P . We call IV (Pi) the initial view of path Pi.

ProblemDefinition. Given a set of path P in graphG, Path Representation Learning (PRL) aims at learning a path representation vector pi ∈ RD′ for each path Pi ∈ P. Formally, PRL learns a path encoder PEψ that takes as input the initial view IV (Pi) of path Pi, i.e., the node features of the nodes in path Pi, and outputs its path representation vector pi.

where ψ indicates the learnable parameters for the path encoder, e.g., weights in a neural network, Z is the length of path Pi, and D′ ≪ Z ×D is an integer indicating the dimension of the learned path representation vector pi.

The learned path representation vectors are supposed to support a variety of downstream tasks, e.g., path ranking and path travel time estimation.

4 Path InfoMax

Figure 1 offers an overview of the proposed framework Path InfoMax (PIM). PIM employs contrastive learning, specifically mutual information maximization, to train the path encoder to produce path representations without requiring taskspecific labels.

The path encoder takes as input the initial view of an input path and outputs its path representation (cf. Sec. 4.1). Training the path encoder is supported by a path-path discriminator and a path-node discriminator using negative samples. To this end, we first introduce the curriculum negative sampling strategy to generate negative paths (cf. Sec. 4.2). Then, the path-path discriminator guides the path encoder to produce path representations such that the path representations of input paths can be distinguished from the path representations of negative paths (cf. Sec. 4.3). In addition, the path-node discriminator guides the path encoder to produce path representations such that the path representations of input paths can be distinguished from the node features of the nodes that only appear in the negative paths (cf. Sec. 4.4). Finally, we discuss the final training objectives of PIM.

4.1 Path Encoder

Since a path consists of a sequence of nodes, we use a model that is able to encode sequential data, e.g., a recurrent neural network [Hochreiter and Schmidhuber, 1997; Cho et al., 2014] or a Transformer [Vaswani et al., 2017] as the path encoder PEψ, where ψ represents the parameters to be learned for the path encoder.

Given a path Pi = 〈V1, V2, . . . , VZ〉, we use its initial view IV (Pi) ∈ RZ×D as the input to the path encoder, which returns its path representation vector pi ∈ RD′ .

4.2 CurriculumNegative Sampling

Motivated by curriculum learning [Bengio et al., 2009], we propose a curriculum negative sampling method to generate negative samples. The idea behind curriculum learning is that we start to train a model with easier samples first, and then gradually increase the difficulty levels. In our setting, we first generate negative paths that are different from the input path, e.g., paths without any overlapping nodes with the input path. In this case, it can be easy to train a path encoder that returns distinguishable representations of the input path and the negative paths. Then, we gradually generate negative paths that are increasingly similar to the input path, e.g., sharing the same source and destination with the input path and with increasingly overlapping nodes. This makes more difficult for the path encoder to generate distinguishable path representations. Figure 2 shows three negative paths ¯ P1, ¯ P2, and ¯ P3 with increasingly difficulties for input path P1, along with the underlying road network graph.

Specifically, for each input path P1, we first randomly select a path from the path set P as the first negative path. Next, we use the source and the destination of P1 as the input to call the top-k diversified shortest path algorithm [Liu et al., 2018] to generate paths that share the same source and destination of P1. This algorithm allows us to set different diversity thresholds, enabling us to generate negative paths with different overlapping nodes with the input path.

4.3 Global Mutual InformationMaximization

We proceed to the learning of the path encoder using the negative paths. We first consider a global view of the path representations. We expect that the learned path representations are distinguishable from the path representations of the negative paths.

To this end, we first construct negative and positive pairs for training a path-path discriminator DPP ω1 . In a negative pair 〈(pi, ¯ pj),-〉, pi and ¯ pj represent the path representations of input path Pi and a negative path ¯ Pj, respectively, which are both returned by the path encoder PEψ. In a positive pair 〈(pi, IV (Pi),+〉, pi is still the path representations of input path Pi returned by the path encoder and IV (Pi) is the initial view of path Pi (cf. Section 4.1). Here, pi and IV (Pi) represent two different views, i.e., a view from the path encoder vs. a view from the node features, of the same input path Pi. Figure 1 shows examples of a negative and a positive pair.

Next, we use mutual information maximization to train the path-path discriminator DP P ω1 such that it is able tomake a binary classification on the negative vs. positive pairs. Specifically, we aim at maximizing the estimated mutual information (MI) over the positive and negative pairs.

where Iψ,ω1 (·, ·) is the MI estimator modeled by the pathpath discriminator DPP ω1 that is parameterized by parameters ω1 and the path encoder PEψ that is parameterized by parameters ψ. Path Pi is an input path from P and pi is its path representation returned by the path encoder. NPi includes the negative paths of Pi. Following [Velickovic et al., 2019; Hjelm et al., 2019], we use a noise-contrastive type objective with a standard binary cross-entropy loss on the positive pairs and the negative pairs, as shown in Equation 2.

Here, we use EP and ENPi to denote expectations w.r.t. the empirical probability distribution of the input paths and the negative paths. Note that pi and ¯ pj are the path representations returned by the path encoder PEψ. Thus, maximizing the MI estimator enables the training of both the path encoder (i.e., parameters ψ) and the path-path discriminator (i.e., parameters ω1).

4.4 Local Mutual InformationMaximization

We proceed to consider a local view of the path representations. We expect that the learned path representations are distinguishable from the node feature vectors of the nodes from input vs. negative paths. This is particularly important when distinguishing two paths with significant overlapping nodes. We introduce a positive node set Xi that includes nodes appearing only in the input path Pi but not the negative paths and a negative node set Yi that includes nodes appearing only in the negative paths but not the input path Pi. We then construct negative and positive pairs for training a pathnode discriminator DPN ω2 . In a negative pair 〈(pi, vj),-〉, pi represents the path representations of input path Pi, returned by the path encoder PEψ; vj represents the node feature vector of a negative node Vj ∈ Yi. Similarly, in a positive pair 〈(pi, vk),+〉, vk represents the node feature vector of a positive node Vk ∈ Xi. Figure 1 shows examples of two negative and two positive such pairs for the path-node discriminator.

Similar to the path-path discriminator training, we also employ mutual information maximization to train the path-node discriminator DPN ω2 . In particular, we have

where Iψ,ω2 is the MI estimator modeled by the path-node discriminator DPN ω2 that is parameterized by parameters ω2 and the path encoder PEψ that is parameterized by parameters ψ. We use a noise-contrastive with a BCE loss, similar to Equation 2, to compute Iψ,ω2 (pi,X∪Y) as follows.

4.5 Maximization of PIM

We combine both the global and local mutual information maximization when training the final PIM model, see below.

5 Experiments

We conduct experiments to investigate the effectiveness of the proposed unsupervised path representation learning framework PIM on two downstream tasks using two data sets. In addition, we also demonstrate that PIM is able to use as a pre-training method to enhance supervised path representation learning.

5.1 Experimental Setup

Road Network and Paths

We obtain two road network graphs from OpenStreetMap. The first is from Aalborg, Denmark, consisting of 8,893 nodes and 10,045 edges. The second is from Harbin, China, consisting of 5,796 nodes and 8,498 edges. We also obtain two substantial GPS trajectory data sets on the two road networks. We consider 52,494 paths in the Aalborg network and 37,079 paths in the Harbin network.

Downstream Tasks

Path Travel Time Estimation. Each path is associated with its travel time (seconds) obtained from trajectories. We aim at building a regression model to estimate the travel time of paths. We evaluate the accuracy of the estimations by Mean Absolute Error (MAE), Mean Absolute Relative Error (MARE) and Mean Absolute Percentage Error (MAPE).

Path Ranking. Given a set of paths, which often share the same source and destination, each path is associated with a ranking score in range [0, 1]. The ranking scores are obtained with the help of trajectories by following an existing study [Yang et al., 2020]. In path ranking, we aim at building a regression model to estimate the ranking scores of the paths. To evaluate the accuracy of the estimated ranking scores, we not only report the MAE of the estimated ranking scores but also use Kendall rank correlation coefficient (denoted by τ) and Spearman's rank correlation coefficient (denoted by ρ) to measure the consistency between the ranking derived by the estimated ranking scores vs. the ranking derived by the ground truth ranking scores. Smaller MAE and higher τ and ρ values indicate higher accuracy.

Baselines

We compare PIM with seven baseline methods.

• Node2vec [Grover and Leskovec, 2016], Deep Graph InfoMax (DGI) [Velickovic et al., 2019], Graphical Mutual Information Maximization (GMI) [Peng et al., 2020] are three unsupervised node representation learning models, which output the node representation for each node in a graph. We use the average of the node representations of the nodes in a path to get the path representation of the path. We also consider using concatenation instead of average, but resulting worse accuracy.
• Memory Bank (MB) [Wu et al., 2018] is an unsupervised learning approach to obtain representations from high-dimensional data. It uses amemory bank to achieve the negative samples from current batch to train an encoder, then gets the representation based on contrastive loss. We re-implement MB with an LSTM encoder to better capture the sequential information to get the path representations.
• InfoGraph [Sun et al., 2020] is an unsupervised whole graph representation learning model. Here, we treat a path as a graph to learn the path representation.
• BERT [Devlin et al., 2019] is an unsupervised language representation learning model. To enable training, we (1) treat a path as a sentence and mask some nodes in the path; and (2) split a path P into two sub-paths

P1 and P2, and consider (P1, P2) as a valid Q&A pair and (P2, P1) as an invalid Q&A pair because the former keeps a meaningful order while the latter does not.

• PathRank [Yang et al., 2020] is a supervised path representation learning model based on GRU. PathRank takes into account the labels from a specific downstream task to obtain path representations.

Among these baselines, Node2vec, DGI, GMI, MB, InfoGraph, and BERT are unsupervised learning approaches, which do not employ labels from specific downstream tasks to produce path representations. In contrast, PathRank is a supervised learning approach, where it employ labels from specific downstream tasks to produce path representations, meaning that the obtained path representations are different when using labels from different downstream tasks.

Regression Model

For all unsupervised learning approaches, we first obtain a task-independent path representation and then apply a regression model to solve different downstream tasks using taskspecific labels. In the experiments, we choose Gaussian Process Regressor (GPR) to make travel time and ranking score estimation. We randomly choose 85%, 10%, and 5% of the paths as the training, validation, and test sets.

Implementation Details

We use an LSTM as the path encoder. We use node2vec [Grover and Leskovec, 2016], an unsupervised node representation learning method, to obtain a 128 dimensional node feature vector for each node, i.e., D = 128. We set the path representation size D′ = 128. In the curriculum negative sampling, for each input path, we generate four negative paths-the first two paths are randomly selected from P and the third and the fourth paths are two paths returned by the top-k diversified shortest paths with different overlapping nodes with the input path. We use Adam [Kingma and Ba, 2015] for optimization with learning rate of 0.001. All algorithms are implemented in Pytorch 1.7.1. We conduct experiments on Ubuntu 18.04.5 LTS, with 40 Intel(R) Xeon(R) Gold 5215 CPUs @ 2.50GHz and four Quadro RTX 8000 GPU cards. Code is available at https://github.com/Sean-Bin-Yang/Path-InfoMax.git.

5.2 Experimental Results

Overall accuracy on both downstream tasks

Table 1 shows the results on travel time and ranking score estimation. PIM consistently outperforms all baselines on both tasks and on both data sets. Node2vec, DGI, and GMI fail to capture the dependencies among node feature vectors in paths. In contrast, PIM considers such dependencies by using the LSTM based path encoder. In addition, the two discriminators further improve the accuracy.

InfoGraph implicitly considers node feature vector sequences. However, the discriminator in InfoGraph only considers the local view. In addition, InfoGraph considers other paths in the same batch as negative samples, whereas PIM employs curriculum negative sampling to generate negative samples. PIM outperforms InfoGraph suggests that the proposed curriculum negative sampling and jointly consider both local and global views are effective.

Although MB and BERT also capture dependencies among the node feature vectors in paths, such methods only achieve relatively poor accuracy. This is because MB often requires large amount of negative samples (e.g., more than 256), which is not feasible in our setting. Although the unsupervised training strategy in BERT works well for NLP, it does not fit our problem setting on learning path representations.

Using PIM as a Pre-training Method

In this experiment, we consider PIM as a pre-training method for the supervised method PathRank. PathRank employs an GRU that takes as input node feature vectors in a path and predicts travel time or ranking scores. To use PIM as a pretraining method for PathRank, we use a GRU based path encoder. Then, we first train PIM in an unsupervsied manner, and then use the learned parameters in the GRU path encoder to initialize the GRU in PathRank. Finally, we use the labelled training paths to fine tune PathRank.

Figure 3 shows the travel time estimation performance of PathRank with vs. without pre-training on both data sets. When not using pre-training, we train PathRank using 10K labelled training paths. We observe that: (1) when using pre-training, we are able to achieve the same accuracy of the non-pre-training PathRank using less labelled training paths, e.g., ca. 7K for Aalborg and 6K for Harbin. (2) when using 10K labelled training paths, the pre-training PathRank achieves higher accuracy than the non-pre-training PathRank. We observe similar results on the other task of path ranking, suggesting that PIM can be used as a pre-training method to enhance supervised methods.

5.3 Ablation Studies

Impact of Local and Global MI Maximization

We investigate the impact of jointly using both path-path and path-node discriminators to consider both the local and global MI maximization. We consider two variants of PIM where (1) we only use the path-path discriminator to maximize the global MI and (2) we only use the path-node discriminator to maximize the local MI. Table 4 shows that jointly maximizing both the local and global MI achieves the best accuracy, which justifies our design choices of using both the path-path and path-node discriminators.

Impact of Curriculum Negative Sample Strategy

To investigate the effectiveness of the proposed curriculum negative sample strategy, we compare it with the following two strategies.

1. Random only: it randomly selects paths from P.
2. Top-k only: it employs the top-k diversified shortest path algorithms to generate negative paths sharing the same origin and destination with the input path with different overlapping nodes.

To make a fair comparison, we use each strategy to generate the same number of negative paths, i.e., 4. Table 3 shows that the top-k only strategy is better than random only, suggesting that it is important to distinguish the representations of input paths vs. paths sharing the same origin and destination. The proposed curriculum negative sampling strategy achieves the best accuracy, suggesting that training PIM from easy to hard negative paths help further improves accuracy.

Impact of Negative Path Numbers

We investigate the impact of using different numbers of negative paths. We vary the number of negative paths K from 1, 2, 3, to 4. Recall that when using curriculum negative sampling, the first two paths are from P and the last two paths are from the top-k diversified shortest path finding algorithm. Table 4 suggests that when using more negative paths, the accuracy improves. The accuracy improvements from 2 to 3 is the largest, suggesting that the top-k algorithm is very effective on generating high quality negative paths.

Impact of Positive/Negative Nodes in local MI

To study the impact of positive and negative nodes, we consider cases where we only use 20%, 40%, 60%, 80% of positive or negative nodes. Table 5 shows that the accuracy increases when using more less positive and negative nodes.

6 Conclusions

We study unsupervised path representation learning without using task-specific labels. We propose a novel contrastive learning framework Path InfoMax (PIM), including a curriculum negative sampling strategy to generate a small number of negative paths and a training mechanism that jointly learns distinguishable path representations from both a global and a local view. Finally, we conduct experiments on two datasets with two downstream tasks. Experimental results show that PIM outperforms other unsupervised methods and, as a pretraining method, PIM is able to enhance supervised path representation learning.

Acknowledgments

This work was supported by Independent Research Fund Denmark under agreements 8022-00246B and 8048-00038B, the VILLUM FONDEN under agreement 34328, and the Innovation Fund Denmark centre, DIREC.