[1]MENG Xiangfu,CUI Jiangyan,DENG Minchao.Road network shortest distance estimation method based on graph convolutional networks[J].CAAI Transactions on Intelligent Systems,2024,19(6):1518-1527.[doi:10.11992/tis.202309006]
Copy
Road network shortest distance estimation method based on graph convolutional networks
CAAI Transactions on Intelligent Systems[ISSN 1673-4785/CN 23-1538/TP] Volume:
19
Number of periods:
2024 6
Page number:
1518-1527
Column:
学术论文—人工智能基础
Public date:
2024-12-05
- Title:
- Road network shortest distance estimation method based on graph convolutional networks
- Keywords:
- shortest path distance computation; graph neural networks; data sampling; representation learning; graph convolutional networks; graph partitioning; deep learning; topology
- CLC:
- TP302.7
- DOI:
- 10.11992/tis.202309006
- Abstract:
- Improving the accuracy of estimating the shortest path distance while reducing model training time is crucial. Existing methods for embedded shortest path distance estimation often take too long to train or sacrifice accuracy to save time. To solve these problems, an encoder-decoder framework has been designed to estimate the shortest distance in a road network by analyzing existing embedded systems-based shortest-path distance estimation methods. The core process is broken down into three parts: embedding method, sampling method, and model training. A road network vertex embedding method, RGCNdist2vec, leverages road graph convolutional networks to capture the structural information of the road network. For model training, a three-stage sampling method using graph logical partitioning is designed to select a small number of high-quality samples. Experiments conducted on four real road network data sets demonstrate that the proposed model achieves higher estimation accuracy while reducing training time by nearly four times compared to existing baseline models.
- References:
-
[1] DIJKSTRA E W. A note on two problems in connexion with graphs[J]. Numerische mathematik, 1959, 1(1): 269-271.
[2] FLOYD R W. Algorithm 97: Shortest path[J]. ACM, 1962, 5(6): 345.
[3] GEISBERGER R, SANDERS P, SCHULTES D, et al. Contraction hierarchies: faster and simpler hierarchical routing in road networks[C]//International Workshop on Experimental and Efficient Algorithms. Berlin: Springer, 2008: 319-333.
[4] OUYANG Dian, QIN Lu, CHANG Lijun, et al. When hierarchy meets 2-hop-labeling: efficient shortest distance queries on road networks[C]//Proceedings of the 2018 International Conference on Management of Data. New York: ACM, 2018: 709-724.
[5] GEISBERGER R, SCHIEFERDECKER D. Heuristic contraction hierarchies with approximation guarantee[C]// Proceedings of the Third Annual Symposium on Combinatorial Search. Menlo Park: AAAI, 2010: 31-38.
[6] CHECHIK S. Approximate distance oracles with improved bounds[C]//Proceedings of the forty-seventh annual ACM on symposium on Theory of Computing. Portland: ACM, 2015: 1-10.
[7] TANG Liying, CROVELLA M. Virtual landmarks for the internet[C]//Proceedings of the 2003 ACM SIGCOMM Internet Measurement Conference. Miami Beach: ACM, 2003: 143-152.
[8] ZHAO Xiaohan, ZHENG Haitao. Orion: shortest path estimation for large social graphs[C]//3rd Workshop on Online Social Networks. Boston: USENIX, 2010: 9.
[9] ZHAO Xiaohan, SALA A, ZHENG Haitao, et al. Efficient shortest paths on massive social graphs[C]//Proceedings of the 7th International Conference on Collaborative Computing: Networking, Applications and Worksharing. Orlando: IEEE, 2011: 77-86.
[10] GUBICHEV A, BEDATHUR S, SEUFERT S, et al. Fast and accurate estimation of shortest paths in large graphs[C]//Proceedings of the 19th ACM international conference on Information and knowledge management. Toronto: ACM, 2010: 499-508.
[11] QI J, WANG W, ZHANG R, et al. A learning based approach to predict shortest-path distances[C]//Proceedings of the 23rd International Conference on Extending Database Technology. Copenhagen: OpenProceedings, 2020: 367-370.
[12] RIZI F S, SCHLOETTERER J, GRANITZER M. Shortest path distance approximation using deep learning techniques[C]//2018 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining. Barcelona: IEEE, 2018: 1007-1014.
[13] HUANG Shuai, WANG Yong, ZHAO Tianyu, et al. A learning-based method for computing shortest path distances on road networks[C]//2021 IEEE 37th International Conference on Data Engineering. Chania: IEEE, 2021: 360-371.
[14] CHEN Xu, WANG Shaohua, LI Huilai, et al. Ndist2vec: node with landmark and new distance to vector method for predicting shortest path distance along road networks[J]. ISPRS international journal of geo-information, 2022, 11(10): 514.
[15] DARMOCHWAL A. The euclidean space[J]. Formalized mathematics, 1991, 2(4): 599-603.
[16] KLEINBERG R. Geographic routing using hyperbolic space[C]//IEEE INFOCOM 2007-26th IEEE International Conference on Computer Communications. Anchorage: IEEE, 2007: 1902-1909.
[17] ANIRBAN S, WANG Junhu, ISLAM M S. Experimental evaluation of indexing techniques for shortest distance queries on road networks[C]//2023 IEEE 39th International Conference on Data Engineering. Anaheim: IEEE, 2023: 624-636.
[18] PACINI F, GUNBY-MANN A, COHEN S, et al. ANEDA: adaptable node embeddings for shortest path distance approximation[C]//2023 IEEE High Performance Extreme Computing Conference. Boston: IEEE, 2023: 1-7.
[19] LUO Jiaqi, DAI Baisheng, CHANG Penghao, et al. Determination of rice leaf midrib deflection in field environment by using semantic segmentation and shortest distance algorithm[J]. Computers and electronics in agriculture, 2023, 215: 108326.
[20] LEI Yi, SHAO Hu, WU Ting, et al. An accelerating algorithm for maximum shortest path interdiction problem by upgrading edges on trees under unit Hamming distance[J]. Optimization letters, 2023, 17(2): 453-469.
[21] KIPF T N, WELLING M. Semi-supervised classification with graph convolutional networks[C]//Proceedings of the 5th International Conference on Learning Representations. France: ICLR, 2017: 1-14.
[22] GROVER A, LESKOVEC J. Node2vec: scalable feature learning for networks[EB/OL]. (2016-07-03)[2021-01-01]. https://arxiv.org/abs/1607.00653.
[23] NICKEL M, KIELA D. Poincaré embeddings for learning hierarchical representations[C]//Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017. New York: Curran Associates, 2017: 6338-6347.
[24] VELICKOVIC P, CUCURULL G, CASANOVA A, et al. Graph attention networks[C]//Proceedings of the International Conference on Learning Representations. Vancouver: ICLR, 2018: 566-577.
[25] GILMER J, SCHOENHOLZ S S, RILEY P F, et al. Neural message passing for quantum chemistry[C]// Proceedings of the 34th International Conference on Machine Learning. New York: PMLR, 2017: 1263-1272.
[26] ZHOU Jie, CUI Ganqu, HU Shengding, et al. Graph neural networks: a review of methods and applications[J]. AI open, 2020, 1: 57-81.
[27] WU Zonghan, PAN Shirui, CHEN Fengwen, et al. A comprehensive survey on graph neural networks[J]. IEEE transactions on neural networks and learning systems, 2021, 32(1): 4-24.
[28] HAMILTON W L, YING R, LESKOVEC J. Inductive representation learning on large graphs[C]//Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017. New York: Curran Associates, 2017: 1024-1034.
[29] KARYPIS G, KUMAR V. Analysis of multilevel graph partitioning[C]//Proceedings of the 1995 ACM/IEEE conference on Supercomputing. San Diego: ACM, 1995: 29.
[30] 闫群民, 马瑞卿, 马永翔, 等. 一种自适应模拟退火粒子群优化算法[J]. 西安电子科技大学学报, 2021, 48(4): 120-127.
YAN Qunmin, MA Ruiqing, MA Yongxiang, et al. Adaptive simulated annealing particle swarm optimization algorithm[J]. Journal of Xidian University, 2021, 48(4): 120-127.
[31] 孟祥福, 赖贞祥, 崔江燕. 集合空间关键字内聚组查询方法[J]. 智能系统学报, 2024, 19(3): 707-718.
MENG Xiangfu, LAI Zhenxiang, CUI Jiangyan. Cohesive group query approach for collective spatial keywords[J]. CAAI transactions on intelligent systems, 2024, 19(3): 707-718.
- Similar References:
Memo
-
Last Update:
2024-11-05