[1]孟祥福,崔江燕,邓敏超.基于图卷积神经网络的最短路径距离估计方法[J].智能系统学报,2024,19(6):1518-1527.[doi:10.11992/tis.202309006]
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]
点击复制
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]
基于图卷积神经网络的最短路径距离估计方法
《智能系统学报》[ISSN 1673-4785/CN 23-1538/TP] 卷:
19
期数:
2024年第6期
页码:
1518-1527
栏目:
学术论文—人工智能基础
出版日期:
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
- 分类号:
- TP302.7
- 摘要:
- 路网最短路径距离估计问题的关键是提高估计准确度和减少模型训练时间。现有基于嵌入的最短路径距离估计方法要么模型的训练时间较长，要么通过牺牲估计精度来降低模型训练时间。针对以上问题，通过分析基于嵌入的最短路径距离估计方法，提出路网最短路径距离估计编码器-解码器框架，归纳和整合这类方法的核心过程，并将核心过程分为嵌入方法、采样方案和模型训练3部分。在此基础上，提出一种基于图卷积网络的路网顶点嵌入方法（road graph convolutional networks and distance2vector, RGCNdist2vec），用于捕获路网的结构信息。在模型训练样本的采样方面，设计一种基于图逻辑分区的三阶段采样方法，能够选取少量优质样本用于模型训练。为验证模型及采样方案的有效性，在4个真实路网数据集上开展实验，并与现有相关模型进行对比，结果表明所提模型具有较高的估计准确性，并且模型训练时间降低为现有基线模型的1/4。
- 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.
- 相似文献/References:
-
[1]吴国栋,查志康,涂立静,等.图神经网络推荐研究进展[J].智能系统学报,2020,15(1):14.[doi:10.11992/tis.201908034]
WU Guodong,ZHA Zhikang,TU Lijing,et al.Research advances in graph neural network recommendation[J].CAAI Transactions on Intelligent Systems,2020,15():14.[doi:10.11992/tis.201908034]
[2]张勇,高大林,巩敦卫,等.用于关系抽取的注意力图长短时记忆神经网络[J].智能系统学报,2021,16(3):518.[doi:10.11992/tis.202008036]
ZHANG Yong,GAO Dalin,GONG Dunwei,et al.Attention graph long short-term memory neural network for relation extraction[J].CAAI Transactions on Intelligent Systems,2021,16():518.[doi:10.11992/tis.202008036]
[3]周俊,张志强,曹月恬,等.地理位置和时间感知的表示学习框架[J].智能系统学报,2021,16(5):909.[doi:10.11992/tis.202104011]
ZHOU Jun,ZHANG Zhiqiang,CAO Yuetian,et al.A geography and time aware representation learning framework[J].CAAI Transactions on Intelligent Systems,2021,16():909.[doi:10.11992/tis.202104011]
[4]卢毅,陈亚冉,赵冬斌,等.关键点图对比图像分类方法[J].智能系统学报,2023,18(1):36.[doi:10.11992/tis.202112001]
LU Yi,CHEN Yaran,ZHAO Dongbin,et al.Keypoint-based graph contrastive neural network for image classification[J].CAAI Transactions on Intelligent Systems,2023,18():36.[doi:10.11992/tis.202112001]
[5]车飞虎,张大伟,邵朋朋,等.基于四元数门控图神经网络的脚本事件预测[J].智能系统学报,2023,18(1):138.[doi:10.11992/tis.202203042]
CHE Feihu,ZHANG Dawei,SHAO Pengpeng,et al.Script event prediction based on a quaternion-gated graph neural network[J].CAAI Transactions on Intelligent Systems,2023,18():138.[doi:10.11992/tis.202203042]
[6]孟祥福,温晶,李子函,等.多重注意力指导下的异构图嵌入方法[J].智能系统学报,2023,18(4):688.[doi:10.11992/tis.202204006]
MENG Xiangfu,WEN Jing,LI Zihan,et al.Heterogeneous graph embedding method guided by the multi-attention mechanism[J].CAAI Transactions on Intelligent Systems,2023,18():688.[doi:10.11992/tis.202204006]
[7]周贤琛,马扬,程光权,等.战场目标实体类型识别的鲁棒图神经网络方法[J].智能系统学报,2023,18(6):1156.[doi:10.11992/tis.202111025]
ZHOU Xianchen,MA Yang,CHENG Guangquan,et al.Robust graph neural network method for target entity type recognition in a battlefield environment[J].CAAI Transactions on Intelligent Systems,2023,18():1156.[doi:10.11992/tis.202111025]
[8]曹汉童,陈璟.融合Doc2vec与GCN的多类型蛋白质相互作用预测方法[J].智能系统学报,2023,18(6):1165.[doi:10.11992/tis.202212029]
CAO Hantong,CHEN Jing.Prediction of multitype protein interactions combining Doc2vec and GCN[J].CAAI Transactions on Intelligent Systems,2023,18():1165.[doi:10.11992/tis.202212029]
[9]刘晓光,李梅.基于深度学习的药物-靶标相互作用预测研究综述[J].智能系统学报,2024,19(3):494.[doi:10.11992/tis.202308024]
LIU Xiaoguang,LI Mei.A survey of deep learning-based drug-target interaction prediction[J].CAAI Transactions on Intelligent Systems,2024,19():494.[doi:10.11992/tis.202308024]
[10]王闪闪,巩长庆,秦华锋,等.基于深度学习的K近邻图迭代静脉识别算法研究[J].智能系统学报,2024,19(5):1149.[doi:10.11992/tis.202307009]
WANG Shanshan,GONG Changqing,QIN Huafeng,et al.Vein recognition algorithm combining K-nearest neighbor and graph iterative based on deep learning[J].CAAI Transactions on Intelligent Systems,2024,19():1149.[doi:10.11992/tis.202307009]
备注/Memo
收稿日期:2023-9-2。
作者简介:孟祥福，教授，博士生导师，主要研究方向为top-k查询、时空大数据。主持国家自然科学基金项目2项、辽宁省各类基金项目4项，发表学术论文20余篇，出版学术专著2部。E-mail: marxi@126.com;崔江燕，硕士研究生，主要研究方向为图嵌入、最短路径距离计算。E-mail: 1315249764@qq.com;邓敏超，硕士研究生，主要研究方向为异构图嵌入、社交网络分析。E-mail: 1093523593@qq.com。
通讯作者:孟祥福. E-mail: marxi@126.com
更新日期/Last Update:
2024-11-05