NEUROMLR: Robust & Reliable Route Recommendation on Road Networks
Year: 2022

Abstract:
Predicting the most likely route from a source location to a destination is a core functionality in mapping services. Although the problem has been studied in the literature, two key limitations remain to be addressed. First, our study reveals that a significant portion of the routes recommended by existing methods fail to reach the destination. Second, existing techniques are transductive in nature; hence, they fail to recommend routes if unseen roads are encountered at inference time. In this paper, we address these limitations through an inductive algorithm called NEUROMLR. NEUROMLR learns a generative model from historical trajectories by conditioning on three explanatory factors: the current location, the destination, and real-time traffic conditions. The conditional distributions are learned through a novel combination of Lipschitz embeddings with Graph Convolutional Networks (GCN) using historical trajectory data. Through in-depth experiments on realworld datasets, we establish that NEUROMLR imparts significant improvement in accuracy over the state of the art. More importantly, NEUROMLR generalizes dramatically better to unseen data and the recommended routes reach the destination with much higher likelihood than existing techniques.

heading: 1 Introduction and Related Work
text: Given historical trajectory data, we study the problem of predicting the most likely route from a source node to a destination node in a road network. This problem has two prominent applications: route recommendation and route recovery. Route recommendation is one of the core functionalities in GPS-aided mapping applications. They are routinely used in the cab and food-delivery industry [26, 7, 34, 6], as well as by common people through navigation systems when they are unfamiliar with their surroundings [30]. Route recovery, as the name suggests, focuses on recovering the actual traversed route from a partially observed GPS trajectory [9]. Due to various reasons, for instance, limiting the power consumption of GPS devices, trajectories are often recorded at low sampling rate.

heading: 1.1 Existing work
text: The simplest approach is to predict the shortest or the quickest path (route) between the source and destination. However, several studies have shown that human beings rarely travel in shortest paths [21]. Rather, the probability of a path being taken is a complex mixture of several latent factors such as road quality [5, 22], road scenery [21, 14], pollution levels [23], presence of road tolls, etc. Furthermore, it has also been shown that human beings systematically misperceive travel time[20]. Modeling these complex factors is challenging. Consequently, a large body of work exists on predicting the most likely route [1, 28, 33, 4, 10, 27], with DEEPST [10] and CSSRNN [27] being the best performing algorithms. CSSRNN models the trajectory patterns through a Recurrent Neural Network and exploits the topological constraints presented by the road network. DEEPST learns representations for the trajectories, destination and traffic conditions using variational autoencoders. ∗denotes equal contribution
35th Conference on Neural Information Processing Systems (NeurIPS 2021).

heading: 1 2 5 10 20 50 100

heading: 1.2 Limitations of existing work
text: • Reachability: Existing techniques have primarily used recall and precision to measure accuracy of predictions [10, 27]. Critically, these ignore whether the predicted trajectory actually reaches the destination. The deployability of any route recommendation algorithm is severely compromised if the recommended route does not reach the destination. Our experiments reveal that for both DEEPST and CSSRNN, a significant portion of recommended routes fail to reach the destination (See Table. 2). Further, the state of the art does not scale well to large road networks (see Fig. 1c). The performance gap between CSSRNN and NEUROMLR becomes more prominent with increasing network size.
• Inductive Learning: A good prediction model should be capable of making predictions on parts of the road network which were unseen or rarely seen during training. From Fig 1b we can observe that there is a significant percentage of nodes in the road network that remain unseen even if we use the entire training data. Both CSSRNN and DEEPST learn node embeddings in a transductive manner, limiting knowledge sharing across nodes. Hence, quality on unseen/lesser seen nodes suffers. DEEPST employs a clustering-inspired approach for sharing statistical strength across trips having similar destinations. However, this introduces a limitation that different destinations get mapped to identical representations, impairing reachability.
• Prediction Accuracy: The accuracy of even the best performing techniques is often below 50% [10]. Consequently, there is scope for improvement.

heading: 1.3 Contributions
text: • Decoupled route prediction: Our proposed problem formulation (§ 2) allows decoupling the problem into two independent subproblems of route search (§ 3) and predicting transition probabilities (§ 4). This allows us to reduce the problem of finding the most likely route to that of identifying the shortest path in a modified road network, thus guaranteeing destination reachability (§ 3).
• Generalization capability: We propose an inductive learning method using a novel combination of Lipschitz embeddings with Graph Convolutional Networks. Lipschitz embeddings serve as a rich initialisation derived from the global road network structure, independent of historical data. GCNs, via message passing, further propagate information learnt during training, to unseen and rarely seen nodes.
• Empirical Evaluation: Extensive experiments on five large, real datasets establish: (1) NEUROMLR is up to 100% more accurate and 4 times faster, (2) the recommended route reaches destination with > 0.96 probability, which is up to 90% better than the state of the art, and (3) NEUROMLR is dramatically more effective in generalizing to unseen data.

heading: 2 Problem Formulation
text: Definition 1 (Road Network). A road network is a directed graph G = (V, E , δ, τt), where V is the set of nodes representing road intersections, E ⊆ V × V is the set of edges representing road
segments, a distance function δ : E → R representing the length (weight) of each road segment, and function τt : E → R representing the average time taken to traverse each road segment at time t. We use the notation e = (u, v) to denote a road segment (edge) from node u to v and its length is denoted by δ(e). Definition 2 (Route). A route (a.k.a path) R(s, d) = {v1, · · · , vk} corresponds to a simple path from the source node s = v1 to destination d = vk in the road network G, i.e., path without cycles. Analogously, a route can also be expressed in terms of a sequence of edgesR(s, d) = {e1, · · · , ek−1}, where ei = (vi, vi+1).
To denote a generic route between any arbitrary source and destination nodes, we useR instead of R(s, d). We use the notation |R| to denote the number of edges inR and R.ei to refer to the ith edge inR. Furthermore, e ∈ R denotes thatR goes through edge e. The above notations are analogously extended from edges to nodes.
We assume we have access to a dataset of historical trajectories. A trajectory is a sequence of GPS pings, made by a vehichle, which corresponds to a path in the road network. Each GPS ping is a tuple of the form 〈latitude, longitude, time〉, which records a vehicle’s location at a particular time. Definition 3 (Query). In a route recommendation query, the input is a tuple q : 〈s, d, t〉, where s, d ∈ V are the source and destination nodes respectively, and t is the time at which the journey is to be taken. Problem: Most Likely Route: Given a road network G, a historical database D of trajectories, and query q : 〈s, d, t〉, we would like to infer the mostly likely routeR∗(s, d) based on the traffic patterns embodied in D. Formally,
R∗(s, d) = arg max ∀R(s,d)∈G Pr(R(s, d) | q) (1)

heading: 2.1 Problem Characterization
text: The route recommendation problem can be framed as a path search problem on the graph corresponding to the road network. Mathematically, the probability of a routeR can be expressed in terms of its constituent edges.
Pr(R | q) = |R|∏ i=1 Pr(R.ei | R.e0 → R.ei−1, s, d, t) (2)
Here, Pr(R.ei | R.e0 → R.ei−1, s, d, t) represents the probability that routeR goes through edge R.ei given the path taken so far and the query parameters q : 〈s, d, t〉 Past studies have shown that human mobility patterns conform to the Markovian assumption [1, 25]. Thus, Eq. 2 reduces to:
Pr(R | q) = |R|∏ i=1 Pr(R.ei | vi, d, t) (3)
With these simplifications, Eq. 1 reduces to:
R∗(s, d) = arg max ∀R∈G |R|∏ i=1 Pr(R.ei | vi, d, t) = arg min ∀R∈G |R|∑ i=1 − log(Pr(R.ei | vi, d, t)) (4)
To summarize the above observations, there are two key challenges that we need to tackle:
• Route Search: Given the conditional transition probability distribution, searching the route (path) minimizing Eq. 4. •Modeling: Learning the conditional distribution that governs transitions in the road network, from the historical trajectory dataset D. Henceforth, while talking about transitions in the road network, we will use the notation curr to refer to the current location(node), curr ∈ V .

heading: 3 Route Search
text: In this section, we assume that the transition probability Pr(e|curr, d, t) for any edge e ∈ E is known. Our algorithm to learn this distribution is discussed in § 4.
The Optimal Search: We first note that the negative log likelihood of a transition probability (see Eq. 4) would be non-negative. Thus, we have an edge weight for each edge in the road network and
our goal is to identify the path from the source to the destination that has the minimum cumulative weight. This computational task maps to the problem of finding the shortest path in a graph and can be solved using Dijkstra’s Algorithm. More importantly, the optimal path is guaranteed to reach the destination. The pseudocode for this search algorithm is provided in App. A. Computational Complexity: The complexity of the Dijkstra’s Algorithm is O(|V| + |E| log(|V|)). This may be prohibitively expensive on large road networks where real-time predictions are desired.
Greedy Approach: We start from the source node and greedily choose the transition with the highest probability till the destination is reached. Inaccurate estimation of transition probabilities may however divert us towards the wrong direction and we may never reach the destination. This may result in |V| iterations in the worst case. To handle cases of this nature, we terminate when either the destination is reached or the Haversine distance from the current node to the destination is significantly higher than the closest point in the current route to the destination. This idea is motivated from the fact that, in general, a vehicle progressively moves closer to the destination with each transition [31]. The pseudocode of the greedy approach can be found in Alg. 2 in App. B . Computational Complexity: At each node inR∗, we evaluate each neighbor and select the one with highest likelihood. Hence, the complexity is O(g|R∗|), where g is the average degree in G.

heading: 4 NEUROMLR: The Neural Approach to the Most Likely Route Problem
text: Revisiting Eq. 4, the key requirement is to accurately model the conditional transition probability function Pr(e | curr, d, t) where e = (curr, v). We want to estimate the true distribution that governs transitions in the road network. However, this distribution is hidden from us and we only have access to D, which is a sample drawn from this distribution. Mathematically, we wish to estimate the underlying transition probability distribution from D using a surrogate function Q(n|c, d, t; Θ), such that, Q(e|curr, d, t; Θ) ≈ Pr(e|curr, d, t). We learn Θ using the neural network depicted in Fig. 2. Our core idea is to learn useful representations of road intersections (nodes) and real-time traffic conditions, and use them to infer the transition probabilities. To learn inductive node representations, we use a novel combination of GCN [8] with Lipschitz embeddings [2]. In addition, a low-dimensional traffic representation of the road network at any time t is learned using Principal Component Analysis (PCA). To predict P (e = (curr, v) | curr, d, t), we concatenate the representations of v, curr, d and traffic status at time t, and pass them through a Multi-layered Perceptron (MLP) to predict the transition probability. The entire network is trained end-to-end. We next discuss each of the sub-components. By convention, we used bold font for vectors and matrices.

heading: 4.1 Constructing Node Attributes
text: In this section, we describe the process of constructing node attributes for our GCN. We wish to learn embeddings where nodes with similar routes to common destinations are close in the embedding space. While latitude and longitude may be used as node attributes, they do not characterize node positions accurately since movement of vehicles is constrained by the network structure. Rather, we need to learn node attributes that reflect road network distances. Towards that end, we use Lipschitz embeddings.
Definition 4 (Attribute Embedding). Let A = {a1, · · · , ak} ⊆ V be a randomly selected subset of nodes. We call them anchors. The distance d(u, v) between two nodes u, v ∈ V is defined as sp(u,v)+sp(v,u)
2 , where sp(u, v) is the spatial shortest path distance 2 from u to v. We embed all nodes
in V in a k-dimensional feature space νL(u) = [x1, · · · , xk], where xi = d(u, ai). The dimensionality of the attribute space dictates how well the original shortest path distances are preserved. To gain a formal understanding of distance preservation, we introduce the definition of distortion. Definition 5 (Distortion). Given two metric spaces (O, d) and (O′, d′) and an embedding function f : O → O′, f has a distortion α if ∀o1, o2 ∈ O, 1αd(o1, o2) ≤ d′(f(o1), f(o2)) ≤ d(o1, o2). In our case, d(o1, o2) is the average two-way shortest path distance. d′(), along with dimensionality k, remains to be defined. To define them, we use Bourgain’s Theorem. Bourgain’s Theorem [2] establishes that a low distortion Lipschitz embedding exists for any metric space. Theorem 1 (Bourgain’s Theorem [2]). Given any finite metric space (O, d) with distance function d(·), there exists an embedding of in (O, d) into Rk under any lp metric, where k = O(log2 n) and the distortion of the embedding is O(log n), where n = |O|. To apply Bourgain’s Theorem on our problem, we need to show that d(u, v) is metric. Lemma 1. d(u, v) is a metric distance function. For proof, refer App. C

heading: 4.2 Learning Node Representations through GCN
text: In addition to capturing road network distances in node representations through Lipschitz embeddings, we would also like to generalize to unseen nodes in the road network. To illustrate, let us assume node v13 in Fig. 1a has not appeared in any training trajectory. If we fine-tune representations for only seen nodes, then the representation of v13 would remain unchanged from its Lipschitz embedding. A GCN avoids this scenario by message passing among neighbors. More specifically, information is shared among L-hop neighbors in GCN, where L is the number of layers. Thus, if a subset of these neighbors have appeared in training trajectories, then this information is shared in its neighborhood, which infuses information beyond Lipschitz embeddings even for unseen nodes.
To train the GCN, Lipschitz embeddings ν(·) corresponding to |V| nodes are stacked as original input features. Specifically, ∀u ∈ V, h0u = ν(u). Next, we compute:
hlu = σ Wl ∑ v∈N(u)∪u hl−1v√ (|N(v)|+ 1)(|N(u)|+ 1)  (5) Here,Wl stands for layer-specific learnable weight matrix for lth layer, hlu is the embedding of node u at layer l and σ(·) denotes an activation function (ReLU in our implementation). Furthermore, N(u) = {v ∈ V | (u, v) ∈ E} denotes the neighbors of node u in the road network. The vector formed in the final layer L is zu = hLu .

heading: 4.3 Traffic representation
text: The simplest option is to partition D into various time slots (Ex: 8AM-11AM, 11-AM-2PM, etc.) and learn a model separately for each time slot. This strategy, however, assumes that traffic is homogeneous in each time slot on all days. Clearly, this assumption is not true in real life (Ex: weekends vs. week days). Further, this scheme is data inefficient since the traffic-dependent travel patterns across different time-slots might be similar.
In order to characterize the real-time traffic conditions for the entire road network at time t, we obtain the top-5% of the most frequently traversed edges E ⊆ E in D. The raw traffic representation at time t is the |E|-dimensional vector of speeds on these edges. Specifically, rt = [τt(e) | e ∈ E]. We use only the top-5% edges since the frequency distribution of edges follows a power-law (See App. H). Consequently, we do not use noisy speed information on less-travelled edges.
It is natural for neighboring road segments (edges) to exhibit co-variance in speed. To remove such information redundancy, we learn a low-dimensional representation of rt through PCA. Specifically, let the training trajectories in D span the time range [tmin, tmax]. Thus, we have a collection of
2We assume that the road network is strongly connected, which is typically true.
traffic representations in the form of R = {rt | t ∈ [tmin, tmax]}. We perform PCA to learn the eigenvectors on R. Given any raw traffic vector rt, it is projected on the top-k eigenvectors to construct the low-dimensional representation zt. Mathematically, zt = rt V , where V ∈ R|E|×k. The columns of V contain the eigenvectors with the k largest eigenvalues.

heading: 4.4 Aggregating Node embedding with Traffic representation
text: Q(e|curr, d, t; Θ) is a function of four input features: current node curr, destination d, traffic condition at time t, and the transition node v corresponding to edge e = (curr, v). GCN provides the embeddings zcurr, zv, zd of curr, v, d respectively and the traffic representation zt is constructed as discussed above. All these embeddings are concatenated 3 as :
z = [zcurr||zv||zd||zt] (6)

heading: 4.5 Model Training
text: Following the pass through GCN, the concatenated embedding z (Eq. 6) is passed through an MLP to convert the vector into a scalar (unnormalised) confidence value i.e f(v, curr, d, t) = MLP (z). The predicted transition value is defined as a softmax over all possible transitions from curr. Mathematically,
Q ((curr, v)|curr, d, t; Θ) = exp (f (v, curr, d, t))∑ v′∈N(curr) exp (f (v ′, curr, d, t)) (7)
Loss(Θ) = − 1|D| ∑ ∀R∈D |R|∑ j=1 log Q(R.ej |R.vj ,R.d,R.t; Θ) (8)
Finally, in Eq. 8 above, the model parameters Θ are optimized through cross-entropy loss over trajectories in D. The pseudocode of the training procedure can be found in Alg. 3 in App. D.

heading: 4.6 Inference Phase
text: Given any query q : 〈s, d, t〉, we follow one of the route search algorithms discussed in § 3. Both search mechanisms require only the transition probabilities as edge weights. Prediction of a transition probability Pr(e = (curr, v) | curr, d, t) simply involves a forward pass through the architecture. Complexity analysis: Time complexity of predicting Pr(e = (curr, v) | curr, d, t) isO(g ·LM ·d2f ). Here, LM is the number of the layers in the MLP, g is the average degree in the road network, df is the output feature vector dimension of the GCN. Refer Appendix. E for detailed derivation.

heading: 5 Experiments
text: In this section, we benchmark NEUROMLR against DEEPST and CSSRNN and establish that:
• Accuracy: NEUROMLR is more accurate in terms of precision and recall when compared to the state-of-the-art algorithms of DEEPST [10] and CSSRNN [27]. • Reachability: NEUROMLR, with its greedy route search mechanism, is more efficient, and achieves significantly higher reachability than DEEPST and CSSRNN. • Inductive Learning: Due to its inductive learning capability, NEUROMLR learns more effectively and generalizes significantly better to unseen/lesser seen parts of the road network. • Scalability: NEUROMLR generates high quality routes on large road networks. The performance of CSSRNN, on the contrary, deteriorates heavily with increase in road network size(Fig. 1c).
Our code-base is available at https://github.com/idea-iitd/NeuroMLR.

heading: 5.1 Experimental Setup
text: The system configuration details are present in App. F. All experiments are repeated 5 times and we report the average of the metric being measured. Datasets: We use publicly available real datasets from five different cities. Table 1 summarizes the statistics of the datasets. The first four cities namely Chengdu4, Porto[15], Harbin [11] and
3We also tried the Attention mechanism [24] to capture the importance of each of the explanatory factors. Details can be found in Appendix. N.
4Chengdu dataset link
Beijing[12] are taxi datasets. The fifth dataset is a publicly available food delivery dataset[7]. The authors did not reveal the name of the city, other than the fact that, in terms of food delivery volume, this city ranks among the highest in India. We extract the road network of each city from OpenStreetMap [17]. To align the GPS sequences to the road network we use map-matching[29]. The temporal edge weight τt(e) is set to the average travel time of all vehicles going over e in the past one hour.
Baselines: We benchmark the performance of NEUROMLR against, (1) DEEPST, (2) CSSRNN, (3) shortest path (SP), and (4) the quickest path (QP). For NEUROMLR, we consider two versions: NEUROMLR-Dijkstra (NEUROMLR-D) and NEUROMLR-Greedy (NEUROMLR-G) corresponding to the two route search algorithms described in § 3. We do not consider personalized route recommendation algorithms [25], since we do not consider the personalization aspect. The codebase of CSSRNN, shared by the authors, is implemented in TensorFlow 1.15. DEEPST and NEUROMLR are implemented in PyTorch 1.6.0.
Train-Validation-Test setup: For a fair comparison of NEUROMLR with DEEPST and CSSRNN,we train all models till convergence of the validation loss. Before splitting, we sort the trajectories on the basis of the start timestamp. Unless specifically mentioned, we use the first 60% of the trajectories for training, next 20% for validation and remaining 20% for inference.
Evaluation metrics: For evaluation, we pick each routeR in the test set and issue the corresponding query q : 〈s, d, t〉, where s = R.v1, d = R.v|R|+1, and t is the time at whichR was initiated. The predicted trajectoryR∗ for q is then generated and compared withR. We use four metrics to evaluate prediction quality.
Precision = ∑ e∈(R∩R∗) δ(e)∑ e∈R∗ δ(e) , Recall = ∑ e∈(R∩R∗) δ(e)∑ e∈R δ(e)
Reachability = { 1 if d = d∗
0 otherwise , Reachability Distance = Haversine (d, d∗)
In the above equations, δ(e) denotes the length of edge e and d∗ denotes the last node inR∗. Note that the reachability metrics are relevant for only NEUROMLR-Greedy, DEEPST and CSSRNN since the rest of the algorithms guarantee reachability.
Parameters: The default parameters for NEUROMLR are provided in App. G.

heading: 5.2 Accuracy and Reachability
text: Table 2 presents the performance of the various algorithms across the three larger datasets - Harbin, Beijing and City India5. The following observations emerge from Table 2.
5Due to space limitations, the results for the other datasets (Porto, Chengdu) can be found in App. L
Precision and Recall: Both versions of NEUROMLR consistently outperform the baselines6. As expected, NEUROMLR-Dijkstra is marginally better than NEUROMLR-Greedy. Among the four considered baselines, CSSRNN achieves the best result. Furthermore, NEUROMLR significantly outperform both SP and QP, which validates past work that people rarely follow shortest/quickest paths: automobile travellers select routes based on several latent factors such as the presence of tolls [16, 19], travel time reliability [3], traffic lights [18], and road aesthetics [21, 32].
Reachability: NEUROMLR-Greedy outperforms both DEEPST and CSSRNN and achieves more than 96% reachability across all datasets. This superior performance of NEUROMLR-Greedy establishes the efficacy of Lipschitz embeddings with GCN in modeling transitions that govern vehicle movements. The reachability performance is weakest in DEEPST due to the clustering based approach it adopts. Specifically, several nodes are allotted the same destination representation and hence reachability is compromised.
Impact of Trip Length: To further evaluate robustness, we examine the performance against the distance between the source and destination in the query. As the trip length increases, more possible paths emerge, and the modeling task gets harder. This pattern is visible in Fig. 3 7. Consistent with previous results, NeuroMLR continues to be the most accurate algorithm.

heading: 5.3 Inductive Learning
text: To showcase the benefits of inductive learning, we compare the two best performing algorithms of NEUROMLR with CSSRNN8.
Impact of training data: In Figs. 4a- 4b, we examine how effectively each algorithm learns as the volume of training data is varied. As clearly evident, NEUROMLR obtains significantly more accurate performance at low volumes of training data than CSSRNN. This is a direct consequence of the inductive ability to share information among nodes and thereby generalize for unseen test data.
Performance on unseen data: In Figs. 4c-4i 9, we investigate how NEUROMLR and CSSRNN perform on test trips that originate or end at unpopular nodes. A node is termed unpopular if its frequency of occurrence in the training trips is less than a threshold frequency. We segregate the test trips into four categories based on the popularity of source and destination nodes: P-P, U-P, P-U and U-U. For example, P-U refers to trips starting at a popular node and ending at an unpopular one. As expected, the majority of test trips are of type P-P and thus the performance on P-P (Figures 4d, 4g) is similar to the aggregate results mentioned in Table 2. We have not included the performance variation of trips of type U-U for different thresholds, since the percentage of such trips is relatively insignificant (Fig.4c). The performance on P-U trips (Figs. 4i, 4f) undergoes a dramatic drop for CSSRNN since the destination is unpopular and there is not much information to direct the model. For U-P (Figs. 4h, 4e), the performance lies between P-P and P-U since even after a rocky start, it could transit to a popular node and from there may reach the destination. In all cases NEUROMLR adapts more gracefully and highlights the benefits of inductive learning. Note that at zero threshold frequency, unpopular nodes are equivalent to nodes unseen during training.
6In absolute terms, the precision and recall might seem low. This is because, for the same input (sourcedestination pair), we may have different outputs (routes). For more details, refer to App. P.
7For similar analysis on other datasets, refer to App. I 8Here, we have restricted our model’s comparisons to CSSRNN since DEEPST performed poorly on all
metrics. Some potential reasons can be found in App. M. 9For similar analysis on other datasets, refer to App. O.

heading: 5.4 Ablation study
text: Impact of GCN and Lipschitz Embeddings: We investigate the individual impact of using Lipschitz embeddings and employing GCNs in Figs. 5a-5b by comparing the performance of NEUROMLR on the four possible combinations. As visible, the combined combination of Lipschitz embeddings and GCN imparts a significant improvement in both prediction accuracy and reachability. Employing either one individually also enhances the model’s performance, thereby justifying their importance. For similar studies on other datasets see App. J.
Impact of Traffic: The impact of traffic on route prediction can be found in App. J.

heading: 5.5 Inference Time
text: Table 3 presents the number of queries solved by the three best performing algorithms per second. Since the performance of DEEPST was found to be much inferior to these three algorithms (Table 2), we skip its efficiency analysis. As evident, NEUROMLR-Greedy is the fastest. Consistent with its computational complexity, NEUROMLR-Dijkstra is slower. CSSRNN is slower than NEUROMLRGreedy since it uses a more complex auto-regressive model where each transition is also conditioned on the path taken so far. Owing to significantly faster inference and accuracy that is almost identical to NEUROMLR-Dijkstra, our recommendation is to use NEUROMLR-Greedy as the default algorithm.

heading: 6 Conclusion
text: For a route recommendation algorithm to be deployable in the real world, it must ensure that the recommended route reaches the destination. In addition, it must show good generalization performance on queries over unseen/rarely seen data. Existing techniques for predicting the most likely route lack the above mentioned abilities. In this paper, we propose NEUROMLR which overcomes these limitations through a novel combination of Lipschitz embedding and Graph Convolutional networks. This strategy ensures inductive learning and enhances reachability. Specifically, even those nodes that are not seen adequately in training data, get good representations due to Lipschitz embedding capturing network position and GCN ensuring information propagation from neighboring nodes. Further, the model decouples probability transition modelling and route search, allowing us to use popular route search algorithms to guarantee reachability. All-in-all, NEUROMLR is more reliable, scales to larger cities, robust to unseen data and more effective in learning from low volume of data.
Limitations: In the future, we would like to work on capturing the personalization aspect of the problem and learn to transfer knowledge from one city to another.
Potential for Negative Societal Impact: Our proposed work facilitates robust and reliable computation of the mostly likely route in road networks. To the best of our understanding, we do not see any potential of negative societal impact from this work.

Review summaries:
This paper presents a new approach for route recommendation. The key idea of the approach is to model the mobility pattern as a Markov process and learn the local transition probability from historical data through a GCN with Lipschitz embedding. The proposed approach overcomes two limitations in the existing works - (1) limited reachability and (2) limited generalizability on unseen/lesser-seen nodes. The paper evaluates their approach on public datasets with a few baselines. The improvement is significant and there are also a good amount of ablation studies and case studies to help the readers better understand the effectiveness of the proposed solution. 

The paper introduces a route recommendation model based on graph neural networks with Lipschitz embedding initialization. The proposed model is compared with several baseline models and the evaluation shows that it outperforms baselines in terms of precision, recall, and reachability. Ablation study is done to demonstrate the importance of both Lipschitz embedding and GCN components. The model which uses inductive learning shows that it significantly outperforms baselines when the source/destination node is unpopular. 

This paper proposes a method for recommending travel routes in a city. As shown in Figure 2, in order to consider the meaningful representation of road network, this paper uses a combination of Graph Convolutional Network with Lipschitz embeddings. Multi-layered Perceptron (MLP) is then applied to predict the next visit.