{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:12:21Z","timestamp":1750219941569,"version":"3.41.0"},"reference-count":62,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2023,6,13]],"date-time":"2023-06-13T00:00:00Z","timestamp":1686614400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100000923","name":"Australian Research Council","doi-asserted-by":"publisher","award":["DP220101434"],"award-info":[{"award-number":["DP220101434"]}],"id":[{"id":"10.13039\/501100000923","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2023,6,13]]},"abstract":"<jats:p>Due to various reasons such as noisy measurement and privacy preservation, a network\/graph is often uncertain such that each edge in the network has a probability of existence. In this paper, we study finding the most probable shortest path which has the highest probability of being the shortest path between a given pair of nodes in an uncertain network. Despite significant progress being made, this problem still suffers from the efficiency and scalability issue. To solve this problem, the state-of-the-art adopts a two-phase approach where Phase 1 generates some candidate paths and Phase 2 estimates their probabilities of being the shortest path and returns the one with the highest probability as the solution. Notably, Phase 2 requires a large number of simulations over all edges in the network and can easily dominate the cost of the whole process. In this paper, we aim to resolve the efficiency and scalability issue by optimizing Phase 2. Specifically, we first propose a non-learning based fast approximation technique which significantly reduces the number of samples for the probability estimation in each simulation. Afterwards, we further propose a learning-based method which can directly estimate the probability of each candidate path without costly simulations. Extensive experiments show that (1) compared to the state-of-the-art, our fast approximation technique and learning-based method can achieve up to 5x and 210x speedups in Phase 2 respectively while maintaining highly competitive or even equivalent results, (2) the training process is highly scalable and (3) the prediction function can work effectively under the problem settings different from the one it was trained.<\/jats:p>","DOI":"10.1145\/3589286","type":"journal-article","created":{"date-parts":[[2023,6,20]],"date-time":"2023-06-20T20:26:45Z","timestamp":1687292805000},"page":"1-25","source":"Crossref","is-referenced-by-count":0,"title":["Shortest Paths Discovery in Uncertain Networks via Transfer Learning"],"prefix":"10.1145","volume":"1","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9165-758X","authenticated-orcid":false,"given":"Shixun","family":"Huang","sequence":"first","affiliation":[{"name":"RMIT University, Melbourne, VIC, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2477-381X","authenticated-orcid":false,"given":"Zhifeng","family":"Bao","sequence":"additional","affiliation":[{"name":"RMIT University, Melbourne, VIC, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2023,6,20]]},"reference":[{"key":"e_1_2_2_1_1","unstructured":"2023. https:\/\/github.com\/rmitbggroup\/MPSP."},{"key":"e_1_2_2_2_1","first-page":"15","article-title":"Managing uncertainty in social networks","volume":"30","author":"Adar Eytan","year":"2007","unstructured":"Eytan Adar and Christopher Re. 2007. Managing uncertainty in social networks. IEEE Data Eng. Bull. 30, 2 (2007), 15--22.","journal-title":"IEEE Data Eng. Bull."},{"key":"e_1_2_2_3_1","volume-title":"Predicting protein complex membership using probabilistic network reliability. Genome research 14, 6","author":"Asthana Saurabh","year":"2004","unstructured":"Saurabh Asthana, Oliver D King, Francis D Gibbons, and Frederick P Roth. 2004. Predicting protein complex membership using probabilistic network reliability. Genome research 14, 6 (2004), 1170--1175."},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3289600.3290967"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/TR.1986.4335422"},{"key":"e_1_2_2_6_1","volume-title":"Injecting uncertainty in graphs for identity obfuscation. arXiv preprint arXiv:1208.4145","author":"Boldi Paolo","year":"2012","unstructured":"Paolo Boldi, Francesco Bonchi, Aris Gionis, and Tamir Tassa. 2012. Injecting uncertainty in graphs for identity obfuscation. arXiv preprint arXiv:1208.4145 (2012)."},{"key":"e_1_2_2_7_1","unstructured":"Francesco Bonchi Aristides Gionis Francesco Gullo and Antti Ukkonen. 2014. Distance oracles in edge-labeled graphs. In EDBT. 547--558."},{"key":"e_1_2_2_8_1","volume-title":"Multi-task Gaussian process prediction. NeurIPS 20","author":"Bonilla Edwin V","year":"2007","unstructured":"Edwin V Bonilla, Kian Chai, and Christopher Williams. 2007. Multi-task Gaussian process prediction. NeurIPS 20 (2007)."},{"key":"e_1_2_2_9_1","volume-title":"Quoc Viet Hung Nguyen, and Xue Li","author":"Chen Hongxu","year":"2018","unstructured":"Hongxu Chen, Hongzhi Yin, Weiqing Wang, Hao Wang, Quoc Viet Hung Nguyen, and Xue Li. 2018. PME: projected metric embedding on heterogeneous networks for link prediction. In SIGKDD. 1177--1186."},{"key":"e_1_2_2_10_1","doi-asserted-by":"crossref","unstructured":"Yurong Cheng Ye Yuan Guoren Wang Baiyou Qiao and Zhiqiong Wang. 2014. Efficient sampling methods for shortest path query over uncertain graphs. In DASFFA. 124--140.","DOI":"10.1007\/978-3-319-05813-9_9"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11390-015-1559-5"},{"key":"e_1_2_2_12_1","unstructured":"The Koblenz Network Collection. 2017. http:\/\/konect.uni-koblenz.de."},{"key":"e_1_2_2_13_1","first-page":"27","article-title":"The neuro bureau preprocessing initiative: open sharing of preprocessed neuroimaging data and derivatives","volume":"7","author":"Craddock Cameron","year":"2013","unstructured":"Cameron Craddock, Yassine Benhajali, Carlton Chu, Francois Chouinard, Alan Evans, Andr\u00e1s Jakab, Budhachandra Singh Khundrakpam, John David Lewis, Qingyang Li, Michael Milham, et al . 2013. The neuro bureau preprocessing initiative: open sharing of preprocessed neuroimaging data and derivatives. Frontiers in Neuroinformatics 7 (2013), 27.","journal-title":"Frontiers in Neuroinformatics"},{"key":"e_1_2_2_14_1","unstructured":"Hanjun Dai Bo Dai and Le Song. 2016. Discriminative embeddings of latent variable models for structured data. In ICML. 2702--2711."},{"key":"e_1_2_2_15_1","first-page":"540","article-title":"Transferring naive bayes classifiers for text classification","volume":"7","author":"Dai Wenyuan","year":"2007","unstructured":"Wenyuan Dai, Gui-Rong Xue, Qiang Yang, and Yong Yu. 2007. Transferring naive bayes classifiers for text classification. In AAAI, Vol. 7. 540--545.","journal-title":"AAAI"},{"key":"e_1_2_2_16_1","doi-asserted-by":"crossref","unstructured":"Wenyuan Dai Qiang Yang Gui-Rong Xue and Yong Yu. 2008. Self-taught clustering. In ICML. 200--207.","DOI":"10.1145\/1390156.1390182"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.5555\/1622559.1622562"},{"key":"e_1_2_2_18_1","doi-asserted-by":"crossref","unstructured":"Jesse Davis and Pedro Domingos. 2009. Deep transfer via second-order markov logic. In ICML. 217--224.","DOI":"10.1145\/1553374.1553402"},{"key":"e_1_2_2_19_1","volume-title":"Catherine Lord, F Xavier Castellanos, and Michael P Milham.","author":"Martino Adriana Di","year":"2011","unstructured":"Adriana Di Martino, Clare Kelly, Rebecca Grzadzinski, Xi-Nian Zuo, Maarten Mennes, Maria Angeles Mairena, Catherine Lord, F Xavier Castellanos, and Michael P Milham. 2011. Aberrant striatal functional connectivity in children with autism. Biological psychiatry 69, 9 (2011), 847--856."},{"key":"e_1_2_2_20_1","doi-asserted-by":"crossref","unstructured":"Xingbo Du Junchi Yan and Hongyuan Zha. 2019. Joint Link Prediction and Network Alignment via Cross-graph Embedding.. In IJCAI. 2251--2257.","DOI":"10.24963\/ijcai.2019\/312"},{"key":"e_1_2_2_21_1","volume-title":"Convolutional networks on graphs for learning molecular fingerprints. NeurIPS 28","author":"Duvenaud David K","year":"2015","unstructured":"David K Duvenaud, Dougal Maclaurin, Jorge Iparraguirre, Rafael Bombarell, Timothy Hirzel, Al\u00e1n Aspuru-Guzik, and Ryan P Adams. 2015. Convolutional networks on graphs for learning molecular fingerprints. NeurIPS 28 (2015)."},{"key":"e_1_2_2_22_1","series-title":"SIAM Journal on computing 28, 2","volume-title":"Finding the k shortest paths","author":"Eppstein David","year":"1998","unstructured":"David Eppstein. 1998. Finding the k shortest paths. SIAM Journal on computing 28, 2 (1998), 652--673."},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.14778\/3055330.3055337"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSSC.1969.300225"},{"key":"e_1_2_2_25_1","volume-title":"Neocognitron: A self-organizing neural network model for a mechanism of visual pattern recognition. In Competition and cooperation in neural nets. 267--285.","author":"Fukushima Kunihiko","year":"1982","unstructured":"Kunihiko Fukushima and Sei Miyake. 1982. Neocognitron: A self-organizing neural network model for a mechanism of visual pattern recognition. In Competition and cooperation in neural nets. 267--285."},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pone.0075941"},{"volume-title":"On a routing problem within probabilistic graphs and its application to intermittently connected networks","author":"Ghosh Joy","key":"e_1_2_2_27_1","unstructured":"Joy Ghosh, Hung Q Ngo, Seokhoon Yoon, and Chunming Qiao. 2007. On a routing problem within probabilistic graphs and its application to intermittently connected networks. In IEEE INFOCOM. 1721--1729."},{"key":"e_1_2_2_28_1","doi-asserted-by":"crossref","unstructured":"Aditya Grover and Jure Leskovec. 2016. node2vec: Scalable feature learning for networks. In SIGKDD. 855--864.","DOI":"10.1145\/2939672.2939754"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.14778\/3311880.3311884"},{"key":"e_1_2_2_30_1","doi-asserted-by":"crossref","unstructured":"Jiafeng Hu Reynold Cheng Zhipeng Huang Yixang Fang and Siqiang Luo. 2017. On embedding uncertain graphs. In CIKM. 157--166.","DOI":"10.1145\/3132847.3132885"},{"key":"e_1_2_2_31_1","doi-asserted-by":"crossref","unstructured":"Ming Hua and Jian Pei. 2010. Probabilistic path queries in road networks: traffic uncertainty aware path selection. In EDBT. 347--358.","DOI":"10.1145\/1739041.1739084"},{"key":"e_1_2_2_32_1","doi-asserted-by":"crossref","unstructured":"Shixun Huang Zhifeng Bao J Shane Culpepper and Bang Zhang. 2019. Finding temporal influential users over evolving social networks. In ICDE. 398--409.","DOI":"10.1109\/ICDE.2019.00043"},{"volume-title":"Temporal network representation learning via historical neighborhoods aggregation","author":"Huang Shixun","key":"e_1_2_2_33_1","unstructured":"Shixun Huang, Zhifeng Bao, Guoliang Li, Yanghao Zhou, and J Shane Culpepper. 2020. Temporal network representation learning via historical neighborhoods aggregation. In ICDE. IEEE, 1117--1128."},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.14778\/3565816.3565821"},{"key":"e_1_2_2_35_1","volume-title":"International conference on machine learning. 448--456","author":"Ioffe Sergey","year":"2015","unstructured":"Sergey Ioffe and Christian Szegedy. 2015. Batch normalization: Accelerating deep network training by reducing internal covariate shift. In International conference on machine learning. 448--456."},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.14778\/2002938.2002941"},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/321992.321993"},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1983.35"},{"key":"e_1_2_2_39_1","volume-title":"Mohammad Al Hasan, and Rojin Rezvansangsari","author":"Ke Xiangyu","year":"2020","unstructured":"Xiangyu Ke, Arijit Khan, Mohammad Al Hasan, and Rojin Rezvansangsari. 2020. Reliability maximization in uncertain graphs. TKDE (2020)."},{"key":"e_1_2_2_40_1","volume-title":"An in-depth comparison of st reliability algorithms over uncertain graphs. arXiv preprint arXiv:1904.05300","author":"Ke Xiangyu","year":"2019","unstructured":"Xiangyu Ke, Arijit Khan, and Leroy Lim Hong Quan. 2019. An in-depth comparison of st reliability algorithms over uncertain graphs. arXiv preprint arXiv:1904.05300 (2019)."},{"key":"e_1_2_2_41_1","doi-asserted-by":"crossref","unstructured":"Neil D Lawrence and John C Platt. 2004. Learning to learn with the informative vector machine. In ICML. 65.","DOI":"10.1145\/1015330.1015382"},{"key":"e_1_2_2_42_1","doi-asserted-by":"crossref","unstructured":"Su-In Lee Vassil Chatalbashev David Vickrey and Daphne Koller. 2007. Learning a meta-level prior for feature relevance from multiple related tasks. In ICML. 489--496.","DOI":"10.1145\/1273496.1273558"},{"key":"e_1_2_2_43_1","unstructured":"Xiaodong Li Reynold Cheng Yixiang Fang Jiafeng Hu and Silviu Maniu. 2018. Scalable evaluation of k-NN queries on large uncertain graphs. In EDBT."},{"key":"e_1_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.14778\/3364324.3364330"},{"key":"e_1_2_2_45_1","unstructured":"Samuel Madden. 2004. Intel lab data. http:\/\/db.csail.mit.edu\/labdata\/labdata.html."},{"key":"e_1_2_2_46_1","first-page":"608","article-title":"Mapping and revising markov logic networks for transfer learning","volume":"7","author":"Mihalkova Lilyana","year":"2007","unstructured":"Lilyana Mihalkova, Tuyen Huynh, and Raymond J Mooney. 2007. Mapping and revising markov logic networks for transfer learning. In AAAI, Vol. 7. 608--614.","journal-title":"AAAI"},{"key":"e_1_2_2_47_1","volume-title":"Proceedings of the AAAI-08 workshop on transfer learning for complex tasks.","author":"Mihalkova Lilyana","year":"2008","unstructured":"Lilyana Mihalkova and Raymond J Mooney. 2008. Transfer learning by mapping with minimal target data. In Proceedings of the AAAI-08 workshop on transfer learning for complex tasks."},{"key":"e_1_2_2_48_1","unstructured":"OpenStreetMap contributors. 2017. Planet dump retrieved from https:\/\/planet.osm.org . https:\/\/www.openstreetmap.org."},{"key":"e_1_2_2_49_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2009.191"},{"key":"e_1_2_2_50_1","doi-asserted-by":"crossref","unstructured":"Panos Parchas Francesco Gullo Dimitris Papadias and Franceseco Bonchi. 2014. The pursuit of a good possible world: extracting representative instances of uncertain graphs. In SIGMOD. 967--978.","DOI":"10.1145\/2588555.2593668"},{"key":"e_1_2_2_51_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920967"},{"key":"e_1_2_2_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/3366423.3380073"},{"key":"e_1_2_2_53_1","doi-asserted-by":"crossref","unstructured":"Rajat Raina Alexis Battle Honglak Lee Benjamin Packer and Andrew Y Ng. 2007. Self-taught learning: transfer learning from unlabeled data. In ICML. 759--766.","DOI":"10.1145\/1273496.1273592"},{"key":"e_1_2_2_54_1","first-page":"1188","article-title":"Shortest paths and centrality in uncertain networks","volume":"14","author":"Saha Arkaprava","year":"2021","unstructured":"Arkaprava Saha, Ruben Brokkelkamp, Yllka Velaj, Arijit Khan, and Francesco Bonchi. 2021. Shortest paths and centrality in uncertain networks. VLDB 14, 7 (2021), 1188--1201.","journal-title":"VLDB"},{"key":"e_1_2_2_55_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0378-3758(00)00115-4"},{"key":"e_1_2_2_56_1","doi-asserted-by":"publisher","DOI":"10.1137\/0208032"},{"key":"e_1_2_2_57_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-87481-2_36"},{"key":"e_1_2_2_58_1","volume-title":"How powerful are graph neural networks? arXiv preprint arXiv:1810.00826","author":"Xu Keyulu","year":"2018","unstructured":"Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. 2018. How powerful are graph neural networks? arXiv preprint arXiv:1810.00826 (2018)."},{"key":"e_1_2_2_59_1","doi-asserted-by":"crossref","unstructured":"Ye Yuan Lei Chen and Guoren Wang. 2010. Efficiently answering probability threshold-based shortest path queries over uncertain graphs. In DASFFA. 155--170.","DOI":"10.1007\/978-3-642-12026-8_14"},{"key":"e_1_2_2_60_1","doi-asserted-by":"crossref","unstructured":"Bianca Zadrozny. 2004. Learning and evaluating classifiers under sample selection bias. In ICML. 114.","DOI":"10.1145\/1015330.1015425"},{"key":"e_1_2_2_61_1","doi-asserted-by":"publisher","DOI":"10.1109\/JPROC.2020.3004555"},{"key":"e_1_2_2_62_1","doi-asserted-by":"crossref","unstructured":"Lei Zou Peng Peng and Dongyan Zhao. 2011. Top-K possible shortest path query over a large uncertain graph. In WISE. 72--86.","DOI":"10.1007\/978-3-642-24434-6_6"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3589286","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3589286","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T17:48:54Z","timestamp":1750182534000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3589286"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,13]]},"references-count":62,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2023,6,13]]}},"alternative-id":["10.1145\/3589286"],"URL":"https:\/\/doi.org\/10.1145\/3589286","relation":{},"ISSN":["2836-6573"],"issn-type":[{"type":"electronic","value":"2836-6573"}],"subject":[],"published":{"date-parts":[[2023,6,13]]}}}