Understanding and learning the characteristics of network paths has been of particular interest for decades and has led to several successful applications. Such analysis becomes challenging for urban networks as their size and complexity are significantly higher compared to other networks. The state-of-the-art machine learning techniques allow us to detect hidden patterns and, thus, infer the features associated with them. However, very little is known about the impact on the performance of such predictive models by the use of different input representations. In this paper, we design and evaluate six different graph input representations (i.e. representations of the network paths), by considering the network’s topological and temporal characteristics, for being used as inputs for machine learning models to learn the behavior of urban network paths. The representations are validated and then tested with a real-world taxi journeys dataset predicting the tips of using a road network of New York. Our results demonstrate that the input representations that use temporal information help the model to achieve the highest accuracy (root mean-squared error of 1.42$).
ArunKRejimoanR (2016) A survey on network path identification using bio inspired algorithms. In: Proceedings of 2nd international conference on Advances in Electrical, Electronics, Information, Communication and Bio-Informatics (AEEICB). Chennai, India: IEEE, pp.387–389.
4.
BengioYCourvilleAPascalV (2013)
Representation learning: A review and new perspectives. IEEE Transactions on Pattern Analysis and Machine Intelligence35: 1798–1828.
5.
BondyJA (1976) Graph Theory with Applications.
Amsterdam:
Elsevier Science Ltd.
6.
CompagnonPOlliverK (2016) Graph embeddings for social network analysis, state of the art. Master’s Thesis, INSA Lyon, France.
7.
CoxDR (1958)
The regression analysis of binary sequences. Journal of the Royal Statistical Society. Series B (Methodological) 20(2): 215–242.
8.
DaleMR (2017) Applying Graph Theory in Ecological Research.
Cambridge:
Cambridge University Press.
9.
DiestelR (2005) Graph Theory (Graduate Texts in Mathematics).
New York:
Springer.
10.
DijkstraEW (1959)
A note on two problems in connexion with graphs. Numerische Mathematik1(1): 269–271.
11.
DuvenaudDKMaclaurinDIparraguirreJ, et al. (2015) Convolutional networks on graphs for learning molecular fingerprints. In: Cortes C, Lawrence ND, Lee DD, et al. (eds) Advances in Neural Information Processing Systems 28. Red Hook, NY: Curran Associates, Inc., pp.2224–2232.
12.
Ferozuddin RiazKA (2011) Applications of graph theory in computer science. In: 3D digital imaging and modeling, international conference on. Bali, Indonesia: IEEE, pp.142–145.
13.
GoriMMonfardiniGScarselliF (2005) A new model for learning in graph domains. In: Proceedings of IEEE international joint conference on neural networks. Montreal, Que., Canada: IEEE, pp.729–734.
14.
GrossJLYellenJ (2005) Graph Theory and Its Applications, Second Edition (Discrete Mathematics and Its Applications).
Boca Raton, FL:
Chapman & Hall/CRC.
15.
GroverALeskovecJ (2016) Node2vec: Scalable feature learning for networks. In: Proceedings of the 22nd ACM SIGKDD international conference on knowledge discovery and data mining, KDD’16. San Francisco, CA, USA: ACM, pp.855–864.
16.
HoTK (1995) Random decision forests. In: Proceedings of the third international conference on document analysis and recognition, Volume 1, ICDAR 95, pp.278–282. Washington, DC: IEEE Computer Society.
17.
JainAZamirARSavareseS, et al. (2016) Structural-RNN: Deep learning on spatio-temporal graphs. In: Proceedings of the IEEE conference on computer vision and pattern recognition. Las Vegas, NV, USA: IEEE, pp.5308–5317.
18.
JiangMCuiPBeutelA, et al. (2016) Catching synchronized behaviors in large networks: A graph mining approach. ACM Transactions on Knowledge Discovery from Data 10(4): 35.
KanoulasEDuYXiaT, et al. (2006) Finding fastest paths on a road network with speed patterns. In: The 22nd international conference on Data Engineering (ICDE’06). Atlanta, GA, USA: IEEE, pp.10–20.
21.
KearnsMJ (1989) The computational complexity of machine learning. PhD Thesis, Harvard University, USA.
22.
KipfTNWellingM (2017) Semi-supervised classification with graph convolutional networks. In: Proceedings of ICLR.
23.
KotsiantisSB (2007) Supervised machine learning: A review of classification techniques. In: Proceedings of the 2007 conference on emerging artificial intelligence applications in computer engineering: Real word AI systems with applications in eHealth, HCI, Information Retrieval and Pervasive Technologies. The Netherlands: ACM, IOS Press Amsterdam, pp.49–268.
24.
KwakHLeeCParkH, et al. (2010) What is twitter, a social network or a news media? In: Proceedings of the 19th international conference on world wide web, WWW ’10. Raleigh, North Carolina, USA: ACM, pp.591–600.
25.
LeeWHTsengSSTsaiSH (2009)
A knowledge based real-time travel time prediction system for urban network. Expert Systems with Applications36(3): 4239–4247.
26.
MehlhornKSandersP (2008) Algorithms and Data Structures: The Basic Toolbox. 1st ed.
New York:
Springer Publishing Company, Inc.
27.
MichalskiSRCarbonellGJMitchellMT (eds) (1986) Machine Learning an Artificial Intelligence Approach.
Vol. 2.
San Francisco, CA:
Morgan Kaufmann Publishers Inc.
28.
Murphy KP (2012) Machine Learning: A Probabilistic Perspective. The MIT Press.
29.
Noulas A, Salnikov V, Lambiotte R, et al. (2015) Mining open datasets for transparency in taxi transport in metropolitan environments. EPJ Data Science 4(1): 23.
PapaJPFalcãoAXSuzukiCTN (2009)
Supervised pattern classification based on optimum-path Forest. International Journal of Imaging Systems and Technology19(2): 120–131.
32.
PedregosaFVaroquauxGGramfortA, et al. (2011)
Scikit-learn: Machine learning in python. Journal of Machine Learning Research 12: 2825–2830.
33.
PerozziBAl-RfouRSkienaS (2014) Deepwalk: Online learning of social representations. In: Proceedings of the 20th ACM SIGKDD international conference on knowledge discovery and data mining, KDD’14. New York, NY, USA: ACM, pp.701–710.
34.
Ramrez-CoronaMSucarLEMoralesEF (2016)
Hierarchical multilabel classification based on path evaluation. International Journal of Approximate Reasoning68: 179–193.
35.
RossiABarlacchiGBianchiniM, et al. (2019) Modelling taxi drivers’ behaviour for the next destination prediction. IEEE Transactions on Intelligent Transportation Systems, 1–10.
36.
ScarselliFGoriMTsoiAC, et al. (2009) The graph neural network model. IEEE Transactions on Neural Networks, 61–80.
37.
SchmidhuberJ (2015)
Deep learning in neural networks: An overview. Neural Networks61: 85–117.
38.
SrinivasanBVKumarAGuptaS, et al. (2014) Stemming the Flow of Information in a Social Network.
New York:
Springer.
39.
SrivastavaNHintonGKrizhevskyA, et al. (2014)
Dropout: A simple way to prevent neural networks from overfitting. Journal of Machine Learning Research15: 1929–1958.
Van WoenselTVandaeleN (2007)
Modeling traffic flows with queueing models: A review. Asia-Pacific Journal of Operational Research (APJOR) 24(4): 435–461.
42.
WangBLuoXZhangF, et al. (2018) Graph-based deep modeling and real time forecasting of sparse spatio-temporal data. In: Proceedings of KDD’18.
43.
YuBYinHZhuZ (2018) Spatio-temporal graph convolutional networks: A deep learning framework for traffic forecasting. In: Proceedings of JCAI’18. Stockholm, Sweden, pp.3634–3640.
Supplementary Material
Please find the following supplemental material available below.
For Open Access articles published under a Creative Commons License, all supplemental material carries the same license as the article it is associated with.
For non-Open Access articles published, all supplemental material carries a non-exclusive license, and permission requests for re-use of supplemental material or any part of supplemental material shall be sent directly to the copyright owner as specified in the copyright notice associated with the article.
