AI Chat Paper
Note: Please note that the following content is generated by AMiner AI. SciOpen does not take any responsibility related to this content.
{{lang === 'zh_CN' ? '文章概述' : 'Summary'}}
{{lang === 'en_US' ? '中' : 'Eng'}}
Chat more with AI
Powered by AMiner. Clicking this button will take you away from SciOpen.
Home Green Energy and Intelligent Transportation Article
Article Link
Cite
EndNote(RIS) BibTeX
Collect
Submit Manuscript
Show Outline
Outline
Show full outline
Hide outline
Outline
Show full outline
Hide outline
Full Length Article | Open Access

Extracting multi-objective multigraph features for the shortest path cost prediction: Statistics-based or learning-based?

School of Engineering and Materials Science, Queen Mary University of London, Mile End Road, London E1 4NS, United Kingdom
Show Author Information

HIGHLIGHTS

● Node physical patterns are offered for multigraph shortest path cost prediction.

● Important node physical patterns are identified.

● Multigraph simplification methods are proposed for node embedding algorithm usability.

● Trimming parallel edges is the most recommended method to simplify multigraphs.

● Simplifying by duplicating multigraph nodes produces embeddings that predict the best.

Graphical Abstract

Abstract

Efficient airport airside ground movement (AAGM) is key to successful operations of urban air mobility. Recent studies have introduced the use of multi-objective multigraphs (MOMGs) as the conceptual prototype to formulate AAGM. Swift calculation of the shortest path costs is crucial for the algorithmic heuristic search on MOMGs, however, previous work chiefly focused on single-objective simple graphs (SOSGs), treated cost enquires as search problems, and failed to keep a low level of computational time and storage complexity. This paper concentrates on the conceptual prototype MOMG, and investigates its node feature extraction, which lays the foundation for efficient prediction of shortest path costs. Two extraction methods are implemented and compared: a statistics-based method that summarises 22 node physical patterns from graph theory principles, and a learning-based method that employs node embedding technique to encode graph structures into a discriminative vector space. The former method can effectively evaluate the node physical patterns and reveals their individual importance for distance prediction, while the latter provides novel practices on processing multigraphs for node embedding algorithms that can merely handle SOSGs. Three regression models are applied to predict the shortest path costs to demonstrate the performance of each. Our experiments on randomly generated benchmark MOMGs show that (ⅰ) the statistics-based method underperforms on characterising small distance values due to severe overestimation; (ⅱ) A subset of essential physical patterns can achieve comparable or slightly better prediction accuracy than that based on a complete set of patterns; and (ⅲ) the learning-based method consistently outperforms the statistics-based method, while maintaining a competitive level of computational complexity.

Keywords

Feature extractionRegressionMulti-objective multigraphShortest path cost predictionNode patternsNode embeddings

References

[1]

Chen J, Weiszer M, Stewart P, Shabani M. Towards a more realistic, cost effective, and greener ground movement through active routing: part 1 - optimal speed profile generation. IEEE Trans Intell Transport Syst 2016;17(5):1196–209. https://doi.org/10.1109/TITS.2015.2477350.
Crossref Google Scholar
[2]

Chen J, Weiszer M, Locatelli G, Ravizza S, Atkin JA, Stewart P, et al. Towards a more realistic, cost-effective, and greener ground movement through active routing: part 2 - a multi-objective shortest path approach. IEEE Trans Intell Transport Syst 2016;17(12):3524–40. https://doi.org/10.1109/TITS.2016.2587619.
Crossref Google Scholar
[3]

Wang X, Brownlee AEI, Weiszer M, Woodward JR, Mahfouf M, Chen J. An interval type-2 fuzzy logic-based map matching algorithm for airport ground movements. IEEE Trans Fuzzy Syst 2023;31(2):582–95. https://doi.org/10.1109/TFUZZ.2022.3221793.
Crossref Google Scholar
[4]
Weiszer M, Burke EK, Chen J. Multi-objective routing and scheduling for airport ground movement. In: Transp. Res. C: Emerg. Technol., vol. 119; 2020. p. 102734–56. https://doi.org/10.1016/j.trc.2020.102734.
Crossref
[5]
Serafini P. Some considerations about computational complexity for multi-objective combinatorial problems. In: Proc. Int. Conf. On vector Optimisation; Aug. 1986. p. 222–32. https://doi.org/10.1007/978-3-642-46618-2_15.
Crossref
[6]
Liu S, Chen J, Weiszer M. Multi-objective multigraph A* search with learning heuristics based on node metrics and graph embedding. In: Proc. IEEE 11th Int. Conf. Intell. Syst.; Oct. 2022. p. 186–93. https://doi.org/10.1109/IS57118.2022.10019653.
Crossref
[7]

Fu L, Sun D, Rilett LR. Heuristic shortest path algorithms for transportation applications: state of the art. Comput Oper Res 2006;33:3324–43. https://doi.org/10.1016/j.cor.2005.03.027.
Crossref Google Scholar
[8]

Tung CT, Chew KL. A multicriteria pareto-optimal path algorithm. Eur J Oper Res 1992;62(2):203–9. https://doi.org/10.1016/0377-2217(92)90248-8.
Crossref Google Scholar
[9]

Dijkstra EW. A note on two problems in connexion with graphs. Numer Math 1959;1(1):269–71. https://doi.org/10.1007/BF01386390.
Crossref Google Scholar
[10]

Hart PE, Nilsson NJ, Raphael B. A formal basis for the heuristic determination of minimum cost paths. IEEE Trans Syst Sci Cybern 1968;4(2):100–7. https://doi.org/10.1109/TSSC.1968.300136.
Crossref Google Scholar
[11]

Floyd RW. Algorithm 97: shortest path. Commun ACM 1962;5(6):345. https://doi.org/10.1145/367766.368168.
Crossref Google Scholar
[12]
Rizi FS, Schloetterer J, Granitzer M. Shortest path distance approximation using deep learning techniques. In: 2018 IEEE/ACM Int. Conf. Adv. Soc. Netw. Anal. And Min. (ASONAM); Aug. 2018. p. 1007–14. https://doi.org/10.1109/ASONAM.2018.8508763.
Crossref
[13]
Chechik S. Approximate distance oracles with improved bounds. In: Proc. 47th Annu. ACM Symp. Theory computing; Jun. 2015. p. 1–10. https://doi.org/10.1145/2746539.2746562.
Crossref
[14]
Sankaranarayanan J, Samet H. Distance oracles for spatial networks. In: IEEE 25th Int. Conf. Data Engineering; Mar. 2009. p. 652–63. https://doi.org/10.1109/ICDE.2009.53.
Crossref
[15]

Thorup M, Zwick U. Approximate distance oracles. J ACM 2005;52(1):1–24. https://doi.org/10.1145/1044731.1044732.
Crossref Google Scholar
[16]
Potamias M, Bonchi F, Castillo C, Gionis A. In: Fast shortest path distance estimation in large networks. Info. Knowl. Mgmt; 2009. p. 867–76. https://doi.org/10.1145/1645953.1646063.
Crossref
[17]
Qi J, Wang W, Zhang R, Zhao Z. A learning based approach to predict shortest-path distances. In: Proc. Int. Conf. Extd. Database Technol.; 2020. p. 367–70.
[18]

Chen X, Wang S, Li H, Lyu F, Liang H, Zhang X, et al. Ndist2vec: node with landmark and new distance to vector method for predicting shortest path distance along road networks. ISPRS Int J Geo-Inf 2022;11(514):1–12. https://doi.org/10.3390/ijgi11100514.
Crossref Google Scholar
[19]
Brunner D. Distance preserving graph embedding,” B.S. thesis. Zurich: ETH Zürich; 2021 [Online], https://pub.tik.ee.ethz.ch/students/2021-FS/BA-2021-17.pdf.
[20]

Lelis LHS, Stern R, Felner A, Zilles S, Holte RC. Predicting optimal solution cost with conditional probabilities. Ann Math Artif Intell 2014;72:267–95. https://doi.org/10.1007/s10472-014-9432-8.
Crossref Google Scholar
[21]

Goyal P, Ferrara E. Graph embedding techniques, applications, and performance: a survey. Knowl Base Syst 2018;151:78–94. https://doi.org/10.1016/j.knosys.2018.03.022.
Crossref Google Scholar
[22]
Hamilton WL, Ying R, Leskovec J. Representation learning on graphs: methods and applications. ArXiv abs/1709.05584 2017. https://doi.org/10.48550/arXiv.1709.05584. n. pag.
[23]
Cao S, Lu W, Xu Q. GraRep: learning graph representations with global structural information. In: Proc. 24th ACM Int. Conf. Info. Knowl. Mgmt.; Oct. 2015. p. 891–900. https://doi.org/10.1145/2806416.2806512.
Crossref
[24]
Grover A, Leskovec J. Node2vec: scalable feature learning for networks. In: Proc. ACM SIGKDD Int. Conf. Knowl. Discov. Data Min.; Aug. 2016. p. 855–64. https://doi.org/10.1145/2939672.2939754.
Crossref
[25]
Zhang J, Dong Y, Wang Y, Tang J, Ding M. ProNE: fast and scalable network representation learning. In: Proc. 28th Int. Joint Conf. Artif. Intell.; 2019. p. 4278–84. https://doi.org/10.24963/ijcai.2019/594.
Crossref
[26]
Song F, Guo Z, Mei D. Feature selection using principal component analysis. In: Proc. Int. Conf. Syst. Sci., Eng. Design Manuf. Informatisation; Nov. 2010. p. 27–30. https://doi.org/10.1109/ICSEM.2010.14.
Crossref
[27]
Haykin S. Neural networks: a comprehensive foundation. Hoboken, New Jersey: Prentice Hall PTR; 1994 [Online]. https://dl.acm.org/doi/abs/10.5555/521706. [Accessed 30 March 2023].
[28]

Wang X, Brownlee AEI, Woodward JR, Weiszer M, Mahfouf M, Chen J. Aircraft taxi time prediction: feature importance and their implications. Transp Res C: Emerg Tech 2021;124:102892–914. https://doi.org/10.1016/j.trc.2020.102892.
Crossref Google Scholar
[29]

Friedman JH. Stochastic gradient boosting. Comput Stat Data Anal 2002;38(4):367–78. https://doi.org/10.1016/S0167-9473(01)00065-2.
Crossref Google Scholar
[30]
Nickel M, Kiela D. Poincaré embeddings for learning hierachical representations. In: Proc. 31st Int. Conf. Neural Inf. Process. Syst.; Dec. 2017. p. 6341–50. https://doi.org/10.48550/arXiv.1705.08039.
[31]

Zhou J, Cui G, Hu S, Zhang Z, Yang C, Liu Z, et al. Graph neural networks: a review of methods and applications. AI Open 2020;1:57–81. https://doi.org/10.1016/j.aiopen.2021.01.001.
Crossref Google Scholar
[32]

Barrat A, Barthélemy M, Pastor-Satorras R, Vespignani A. The architecture of complex weighted netwroks. Proc Natl Acad Sci USA 2004;101(11):3747–52. https://doi.org/10.1073/pnas.0400087101.
Crossref Google Scholar
[33]

Bonacich P. Power and centrality: a family of measures. Am J Sociol 1986;92(5):1170–82.
Crossref Google Scholar
[34]

Freeman LC. Centrality in social networks conceptual clarification. Soc Netw 1979;1(3):215–39. https://doi.org/10.1016/0378-8733(78)90021-7.
Crossref Google Scholar
[35]
Brandes U, Fleischer D. Centrality measures based on current flow. In: Proc. Ann. Symp. Theor. Aspects Comput. Sci.; 2005. p. 533–44. https://doi.org/10.1007/978-3-540-31856-9_44.
Crossref
[36]

Stephenson K, Zelen M. Rethinking centrality: methods and examples. Soc Netw 1989;11(1):1–37. https://doi.org/10.1016/0378-8733(89)90016-6.
Crossref Google Scholar
[37]

Newman MEJ. A measure of betweenness centrality based on random walks. Soc Netw 2005;27(1):39–54. https://doi.org/10.1016/j.socnet.2004.11.009.
Crossref Google Scholar
[38]

Goh K-I, Kahng B, Kim D. Universal behaviour of load distribution in scale-free networks. Phys Rev Lett 2001;87(27):1–4. https://doi.org/10.1103/PhysRevLett.87.278701.
Crossref Google Scholar
[39]

Kermarrec A-M, Merrer EL, Sericola B, Trédan G. Second order centrality: distributed assessment of nodes criticity in complex networks. Comput Commun 2011;34(5):619–28. https://doi.org/10.1016/j.comcom.2010.06.007.
Crossref Google Scholar
[40]

Boldi P, Vigna S. Axioms for centrality. Internet Math 2014;10(3–4):222–62. https://doi.org/10.1080/15427951.2013.865686.
Crossref Google Scholar
[41]
Hagberg A, Schult D, Swart P. Exploring network structure, dynamics, and function using NetworkX. In: Proc. 7th Python Sci. Conf.; 2008. p. 11–6.
[42]
Zhang P, Wang J, Li X, Li M, Di Z, Fan Y. Clustering coefficient and community structure of bipartite networks. Phys. A: Stat Mech Appl 2008;387(27):6869–75. https://doi.org/10.1016/j.physa.2008.09.006.
Crossref
[43]

Kernighan BW, Lin S. An efficient heuristic procedure for partitioning graphs. Bell Sys Tech J 1970;49(2):291–307. https://doi.org/10.1002/j.1538-7305.1970.tb01770.x.
Crossref Google Scholar
[44]
Esfahanian A-H. Connectivity algorithms. cse.msu.edu, http://www.cse.msu.edu/~cse835/Papers/Graph_connectivity_revised.pdf. [Accessed 6 April 2023].
[45]

Langville AN, Meyer CD. A survey of eigenvector methods for web information retrieval. SIAM Rev 2005;47(1):135–61. https://doi.org/10.1137/S0036144503424786.
Crossref Google Scholar
[46]

Burt RS. Structural holes and good ideas. Am J Sociol 2004;110(2):349–99. https://doi.org/10.1086/421787.
Crossref Google Scholar
[47]

Burt RS. Structural holes: the social structure of competition. Cambridge: Harvard University Press; 1995.
[48]
Brandes U. Network analysis: methodological foundations. New York: Springer; 2005 [Online], http://books.google.com/books?id=TTNhSm7HYrIC. [Accessed 6 April 2023].
[49]

Luce RD, Perry AD. A method of matrix analysis of group structure. Psychometrika 1949;14(2):95–116. https://doi.org/10.1007/BF02289146.
Crossref Google Scholar
[50]

Holland PW, Leinhardt S. Transitivity in structural models of small groups. Comp Group Stud 1971;2(2):107–24. https://doi.org/10.1177/104649647100200201.
Crossref Google Scholar
[51]

Watts DJ, Strogatz S. Collective dynamics of ‘small-world’ networks. Nature 1998;393(6684):440–2. https://doi.org/10.1038/30918.
Crossref Google Scholar
[52]

Altmann A, Toloşi L, Sander O, Lengauer T. Permutation importance: a corrected feature importance measure. Bioinformatics 2010;26(10):1340–7. https://doi.org/10.1093/bioinformatics/btq134.
Crossref Google Scholar
[53]
Lundberg SM, Lee S. A unified approach to interpretin model predictions. In: Proc. 31st Int. Conf. Neural Inf. Process. Syst.; Dec. 2017. p. 4768–77. https://doi.org/10.48550/arXiv.1705.07874.
[54]

Xu Y, Zhang D, Yang JY. A feature extraction method for use with bimodal biometrics. Pattern Recogn 2010;43(3):1106–15. https://doi.org/10.1016/j.patcog.2009.09.013.
Crossref Google Scholar
[55]
Mikolov T, Chen K, Corrado G, Dean J. Efficient estimation of word representations in vector sapce. arXiv preprint 2013. https://doi.org/10.48550/arXiv.1301.3781.
[56]

Kubat M. Neural networks: a comprehensive foundation by Simon Haykin, Macmillan, 1994. Knowl Eng Rev 1995;13(4):409–12. https://doi.org/10.1017/s0269888998214044.
Crossref Google Scholar
[57]
Nair V, Hinton GE. Rectified linear units improve restricted Boltzmann machines. In: Proc. 27th Int. Conf. Mach. Learn. ICML-10); 2010. p. 807–14.
[58]
Glorot X, Bordes A, Bengio Y. Deep sparse rectifier neural networks. In: Proc. 14th Int. Conf. Artif. Intell. Stats.; 2011. p. 315–23. 10.1.1.208.6449.
[59]
Kingma DP, Ba JL. Adam: a method for stochastic optimisation. CoRR abs/1412.6980 2014. https://doi.org/10.48550/arXiv.1412.6980. n. pag.
[60]
Pedregosa F, Varoquaux G, Gramfort A, Michel V, Thirion B, Grisel O, et al. Scikitlearn: machine learning in Python. arXiv preprint 2012. https://doi.org/10.48550/arXiv.1201.0490.
Green Energy and Intelligent Transportation
Volume 3 Issue 1,
February 2024
Article number: 100129
DOI: 10.1016/j.geits.2023.100129
Cite this article:
Liu S, Wang X, Weiszer M, et al. Extracting multi-objective multigraph features for the shortest path cost prediction: Statistics-based or learning-based?. Green Energy and Intelligent Transportation, 2024, 3(1): 100129. https://doi.org/10.1016/j.geits.2023.100129

109

Views

0

Crossref

0

Web of Science

0

Scopus

Altmetrics
Received: 29 April 2023
Revised: 30 August 2023
Accepted: 31 August 2023
Published: 20 January 2024
© 2023

This is an open access article under the CC BY-NC-ND license (http://creativecommons.org/licenses/by-nc-nd/4.0/).
Return