{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T15:50:24Z","timestamp":1753890624381,"version":"3.41.2"},"reference-count":65,"publisher":"Frontiers Media SA","license":[{"start":{"date-parts":[[2024,11,19]],"date-time":"2024-11-19T00:00:00Z","timestamp":1731974400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["frontiersin.org"],"crossmark-restriction":true},"short-container-title":["Front. Big Data"],"abstract":"<jats:p>With graph reachability query, one can answer whether there exists a path between two query vertices in a given graph. The existing reachability query processing solutions use traditional reachability index structures and can only compute exact answers, which may take a long time to resolve in large graphs. In contrast, with an approximate reachability query, one can offer a compromise by enabling users to strike a trade-off between query time and the accuracy of the query result. In this study, we propose a framework, dubbed ActiveReach, for learning index structures to answer approximate reachability query. ActiveReach is a two-phase framework that focuses on embedding nodes in a reachability space. In the first phase, we leverage node attributes and positional information to create reachability-aware embeddings for each node. These embeddings are then used as nodes' attributes in the second phase. In the second phase, we incorporate the new attributes and include reachability information as labels in the training data to generate embeddings in a reachability space. In addition, computing reachability for all training data may not be practical. Therefore, selecting a subset of data to compute reachability effectively and enhance reachability prediction performance is challenging. ActiveReach addresses this challenge by employing an active learning approach in the second phase to selectively compute reachability for a subset of node pairs, thus learning the approximate reachability for the entire graph. Our extensive experimental study with various real attributed large-scale graphs demonstrates the effectiveness of each component of our framework.<\/jats:p>","DOI":"10.3389\/fdata.2024.1427104","type":"journal-article","created":{"date-parts":[[2024,11,19]],"date-time":"2024-11-19T06:19:43Z","timestamp":1731997183000},"update-policy":"https:\/\/doi.org\/10.3389\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["ActiveReach: an active learning framework for approximate reachability query answering in large-scale graphs"],"prefix":"10.3389","volume":"7","author":[{"given":"Zohreh","family":"Raghebi","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Farnoush","family":"Banaei-Kashani","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1965","published-online":{"date-parts":[[2024,11,19]]},"reference":[{"key":"B1","doi-asserted-by":"publisher","first-page":"253","DOI":"10.1145\/66926.66950","article-title":"Efficient management of transitive relationships in large data and knowledge bases","volume":"18","author":"Agrawal","year":"1989","journal-title":"SIGMOD Rec"},{"key":"B2","doi-asserted-by":"crossref","first-page":"44","DOI":"10.1145\/1150402.1150412","article-title":"\u201cGroup formation in large social networks: Membership, growth, and evolution,\u201d","volume-title":"Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD '06","author":"Backstrom","year":"2006"},{"key":"B3","first-page":"585","article-title":"\u201cLaplacian eigenmaps and spectral techniques for embedding and clustering,\u201d","volume-title":"Proceedings of the 14th International Conference on Neural Information Processing Systems: Natural and Synthetic, NIPS'01","author":"Belkin","year":"2001"},{"key":"B4","doi-asserted-by":"crossref","first-page":"845","DOI":"10.1145\/1367497.1367611","article-title":"\u201cOn incremental maintenance of 2-hop labeling of graphs,\u201d","volume-title":"Proceedings of the 17th International Conference on World Wide Web, WWW '08","author":"Bramandia","year":"2008"},{"key":"B5","article-title":"Active learning for graph embedding","author":"Cai","year":"2017","journal-title":"arXiv preprint arXiv:1705.05085"},{"key":"B6","first-page":"243","article-title":"\u201cGeneral spanning trees and reachability query evaluation,\u201d","volume-title":"Proceedings of the 2Nd Canadian Conference on Computer Science and Software Engineering, C3S2E '09","author":"Chen","year":"2009"},{"key":"B7","doi-asserted-by":"publisher","DOI":"10.14778\/2350229.2350247","article-title":"\u201cK-reach: who is in your small world,\u201d","author":"Cheng","year":"2012","journal-title":"Proceedings of the VLDB Endowment"},{"key":"B8","doi-asserted-by":"publisher","DOI":"10.1109\/ICDCS.2015.109","article-title":"\u201cThe reachability query over distributed uncertain graphs,\u201d","author":"Cheng","year":"2015","journal-title":"2015 IEEE 35th International Conference on Distributed Computing Systems"},{"key":"B9","first-page":"937","article-title":"\u201cReachability and distance queries via 2-hop labels,\u201d","volume-title":"Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '02","author":"Cohen","year":"2002"},{"key":"B10","first-page":"2142","article-title":"\u201cActive discriminative network representation learning,\u201d","volume-title":"Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, IJCAI-18","author":"Gao","year":"2018"},{"key":"B11","doi-asserted-by":"publisher","DOI":"10.1109\/INFCOM.2007.201","article-title":"\u201cOn a routing problem within probabilistic graphs and its application to intermittently connected networks,\u201d","author":"Ghosh","year":"2007","journal-title":"IEEE INFOCOM 2007"},{"key":"B12","doi-asserted-by":"publisher","first-page":"78","DOI":"10.1016\/j.knosys.2018.03.022","article-title":"Graph embedding techniques, applications, and performance: a survey","volume":"151","author":"Goyal","year":"2018","journal-title":"Knowl.-Based Syst"},{"key":"B13","doi-asserted-by":"crossref","first-page":"855","DOI":"10.1145\/2939672.2939754","article-title":"\u201cNode2vec: scalable feature learning for networks,\u201d","volume-title":"Proceedings of the 22Nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD '16","author":"Grover","year":"2016"},{"key":"B14","article-title":"\u201cInductive representation learning on large graphs,\u201d","author":"Hamilton","year":"2017","journal-title":"Advances in Neural Information Processing Systems, 30"},{"key":"B15","first-page":"745","article-title":"\u201cAsap: fast, approximate graph pattern mining at scale,\u201d","volume-title":"OSDI'18","author":"Iyer","year":""},{"key":"B16","first-page":"745","article-title":"\u201cBridging the gap: towards approximate graph analytics,\u201d","volume-title":"GRADES-NDA'18","author":"Iyer","year":""},{"key":"B17","doi-asserted-by":"publisher","first-page":"558","DOI":"10.1145\/99935.99944","article-title":"A compression technique to materialize transitive closure","volume":"15","author":"Jagadish","year":"1990","journal-title":"ACM Trans. Datab. Syst"},{"key":"B18","doi-asserted-by":"publisher","first-page":"551","DOI":"10.14778\/2002938.2002941","article-title":"Distance-constraint reachability computation in uncertain graphs","volume":"4","author":"Jin","year":"2011","journal-title":"Proc. VLDB Endow"},{"key":"B19","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1145\/2213836.2213856","article-title":"\u201cScarab: Scaling reachability computation on large graphs,\u201d","volume-title":"Proceedings of the 2012 ACM SIGMOD International Conference on Management of Data, SIGMOD '12","author":"Jin","year":"2012"},{"key":"B20","article-title":"Simple, fast, and scalable reachability oracle","author":"Jin","year":"2013","journal-title":"CoRR, abs\/1305.0502"},{"key":"B21","doi-asserted-by":"crossref","first-page":"813","DOI":"10.1145\/1559845.1559930","article-title":"\u201c3hopp: a high-compression indexing scheme for reachability query,\u201d","volume-title":"Proceedings of the 2009 ACM SIGMOD International Conference on Management of Data, SIGMOD'09","author":"Jin","year":"2009"},{"key":"B22","doi-asserted-by":"crossref","first-page":"595","DOI":"10.1145\/1376616.1376677","article-title":"\u201cEfficiently answering reachability queries on very large directed graphs,\u201d","volume-title":"Proceedings of the 2008 ACM SIGMOD International Conference on Management of Data, SIGMOD '08","author":"Jin","year":"2008"},{"key":"B23","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1007\/BF02289026","article-title":"A new status index derived from sociometric analysis","volume":"18","author":"Katz","year":"1953","journal-title":"Psychometrika"},{"key":"B24","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1145\/956750.956769","article-title":"\u201cMaximizing the spread of influence through a social network,\u201d","volume-title":"Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD '03","author":"Kempe","year":"2003"},{"key":"B25","article-title":"Betweenness centrality: algorithms and lower bounds","author":"Kintali","year":"2008","journal-title":"CoRR, abs\/0809.1906"},{"key":"B26","article-title":"Semi-supervised classification with graph convolutional networks","author":"Kipf","year":"2017","journal-title":"arXiv preprint arXiv:1609.02907"},{"key":"B27","doi-asserted-by":"crossref","first-page":"489","DOI":"10.1145\/3183713.3196909","article-title":"\u201cThe case for learned index structures,\u201d","volume-title":"Proceedings of the 2018 International Conference on Management of Data, SIGMOD '18","author":"Kraska","year":"2018"},{"key":"B28","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1145\/1081870.1081893","article-title":"\u201cGraphs over time: densification laws, shrinking diameters and possible explanations,\u201d","volume-title":"Proceedings of the Eleventh ACM SIGKDD International Conference on Knowledge Discovery in Data Mining, KDD '05","author":"Leskovec","year":"2005"},{"key":"B29","article-title":"Efficient estimation of word representations in vector space","author":"Mikolov","year":"2013","journal-title":"arXiv preprint arXiv:1301.3781, 3781"},{"key":"B30","first-page":"464","article-title":"\u201cA model for learned bloom filters and optimizing by sandwiching,\u201d","volume-title":"Advances in Neural Information Processing Systems","author":"Mitzenmacher","year":"2018"},{"key":"B31","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3105760","article-title":"Efficient attack graph analysis through approximate inference","volume":"20","author":"Mu noz Gonz\u00e1lez","year":"2017","journal-title":"ACM Trans. Priv. Secur"},{"key":"B32","doi-asserted-by":"crossref","DOI":"10.1145\/3209889.3209890","article-title":"\u201cLearning state representations for query optimization with deep reinforcement learning,\u201d","volume-title":"Proceedings of the Second Workshop on Data Management for End-To-End Machine Learning, DEEM'18","author":"Ortiz","year":"2018"},{"key":"B33","doi-asserted-by":"crossref","first-page":"1105","DOI":"10.1145\/2939672.2939751","article-title":"\u201cAsymmetric transitivity preserving graph embedding,\u201d","volume-title":"Proceedings of the 22Nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD'16","author":"Ou","year":"2016"},{"key":"B34","doi-asserted-by":"crossref","first-page":"701","DOI":"10.1145\/2623330.2623732","article-title":"\u201cDeepwalk: Online learning of social representations,\u201d","volume-title":"Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD '14","author":"Perozzi","year":"2014"},{"key":"B35","doi-asserted-by":"publisher","DOI":"10.1109\/BigData.2018.8622578","article-title":"\u201cEfficient processing of probabilistic single and batch reachability queries in large and evolving spatiotemporal contact networks,\u201d","author":"Raghebi","year":"2018","journal-title":"2018 IEEE International Conference on Big Data (Big Data)"},{"key":"B36","doi-asserted-by":"publisher","first-page":"2323","DOI":"10.1126\/science.290.5500.2323","article-title":"Nonlinear dimensionality reduction by locally linear embedding","volume":"290","author":"Roweis","year":"2000","journal-title":"Science"},{"key":"B37","doi-asserted-by":"crossref","first-page":"360","DOI":"10.1109\/ICDE.2005.57","article-title":"\u201cEfficient creation and incremental maintenance of the hopi index for complex xml document collections,\u201d","author":"Schenkel","year":"2005","journal-title":"21st International Conference on Data Engineering (ICDE'05)"},{"key":"B38","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1609\/aimag.v29i3.2157","article-title":"Collective classification in network data","volume":"29","author":"Sen","year":"2008","journal-title":"AI Magazine"},{"key":"B39","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2019.00049","article-title":"\u201cArrow: approximating reachability using random walks over web-scale graphs,\u201d","author":"Sengupta","year":"2019","journal-title":"2019 IEEE 35th International Conference on Data Engineering (ICDE)"},{"journal-title":"Active learning literature survey","year":"2009","author":"Settles","key":"B40"},{"key":"B41","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2013.6544893","article-title":"\u201cFerrari: flexible and efficient reachability range assignment for graph indexing,\u201d","author":"Seufert","year":"2013","journal-title":"2013 IEEE 29th International Conference on Data Engineering (ICDE)"},{"key":"B42","doi-asserted-by":"publisher","first-page":"848","DOI":"10.14778\/2311906.2311912","article-title":"Efficient reachability query evaluation in large spatiotemporal contact datasets","volume":"5","author":"Shirani-Mehr","year":"2012","journal-title":"Proc. VLDB Endow"},{"key":"B43","doi-asserted-by":"crossref","first-page":"322","DOI":"10.1145\/1644893.1644932","article-title":"\u201cScalable proximity estimation and link prediction in online social networks,\u201d","volume-title":"Proceedings of the 9th ACM SIGCOMM Conference on Internet Measurement, IMC '09","author":"Song","year":"2009"},{"key":"B44","doi-asserted-by":"publisher","first-page":"683","DOI":"10.1109\/TKDE.2016.2631160","article-title":"Reachability querying: can it be even faster?","volume":"29","author":"Su","year":"2017","journal-title":"IEEE Trans. Knowl. Data Eng"},{"key":"B45","doi-asserted-by":"crossref","DOI":"10.1145\/2736277.2741093","article-title":"\u201cLine: large-scale information network embedding,\u201d","volume-title":"Proceedings of the 24th International Conference on World Wide Web","author":"Tang","year":"2015"},{"key":"B46","doi-asserted-by":"publisher","first-page":"2319","DOI":"10.1126\/science.290.5500.2319","article-title":"A global geometric framework for nonlinear dimensionality reduction","volume":"290","author":"Tenenbaum","year":"2000","journal-title":"Science"},{"key":"B47","doi-asserted-by":"crossref","first-page":"845","DOI":"10.1145\/1247480.1247573","article-title":"\u201cFast and practical indexing and querying of very large graphs,\u201d","volume-title":"Proceedings of the 2007 ACM SIGMOD International Conference on Management of Data, SIGMOD '07","author":"Tri-ssl","year":"2007"},{"key":"B48","doi-asserted-by":"crossref","first-page":"913","DOI":"10.1145\/1989323.1989419","article-title":"\u201cA memory efficient reachability data structure through bit vector compression,\u201d","volume-title":"Proceedings of the 2011 ACM SIGMOD International Conference on Management of Data, SIGMOD '11","author":"van Schaik","year":"2011"},{"key":"B49","article-title":"Graph attention networks","author":"Velickovi\u0107","year":"2017","journal-title":"arXiv preprint arXiv:1710.10903"},{"key":"B50","article-title":"\u201cReachability queries in very large graphs: A fast refined online search approach,\u201d","author":"Veloso","year":"2014","journal-title":"EDBT"},{"key":"B51","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2006.53","article-title":"\u201cDual labeling: answering graph reachability queries in constant time,\u201d","author":"Wang","year":"2006","journal-title":"22nd International Conference on Data Engineering (ICDE'06)"},{"key":"B52","doi-asserted-by":"publisher","first-page":"1191","DOI":"10.14778\/2732977.2732992","article-title":"Reachability querying: an independent permutation labeling approach","volume":"7","author":"Wei","year":"2014","journal-title":"Proc. VLDB Endow"},{"key":"B53","article-title":"Active learning for graph neural networks via node feature propagation","author":"Wu","year":"2021","journal-title":"arXiv preprint arXiv:1910.07567"},{"key":"B54","doi-asserted-by":"publisher","first-page":"4","DOI":"10.1109\/TNNLS.2020.2978386","article-title":"A comprehensive survey on graph neural networks","volume":"32","author":"Wu","year":"2021","journal-title":"IEEE Trans. Neural Netw. Lear. Syst"},{"key":"B55","first-page":"1601","article-title":"\u201cFast and scalable reachability queries on graphs by pruned labeling with landmarks and paths,\u201d","volume-title":"Proceedings of the 22nd ACM International Conference on Information and Knowledge Management, CIKM '13","author":"Yano","year":"2013"},{"key":"B56","doi-asserted-by":"publisher","first-page":"276","DOI":"10.14778\/1920841.1920879","article-title":"Grail: Scalable reachability index for large graphs","volume":"3","author":"Yildirim","year":"2010","journal-title":"Proc. VLDB Endow"},{"key":"B57","doi-asserted-by":"crossref","DOI":"10.1145\/3219819.3219890","article-title":"\u201cGraph convolutional neural networks for web-scale recommender systems,\u201d","volume-title":"Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery &Data Mining","author":"Ying","year":"2018"},{"key":"B58","article-title":"\u201cPosition-aware graph neural networks,\u201d","author":"You","year":"2019","journal-title":"International Conference on Machine Learning"},{"key":"B59","article-title":"Graphsaint: graph sampling based inductive learning method","author":"Zeng","year":"2020","journal-title":"arXiv preprint arXiv:1907.04931"},{"key":"B60","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1145\/3555041.3589408","article-title":"\u201cAn overview of reachability indexes on graphs,\u201d","volume-title":"Companion of the 2023 International Conference on Management of Data, SIGMOD '23","author":"Zhang","year":"2023"},{"key":"B61","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2007.368984","article-title":"\u201cMonkey: approximate graph mining based on spanning trees,\u201d","author":"Zhang","year":"2007","journal-title":"2007 IEEE 23rd International Conference on Data Engineering"},{"key":"B62","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v31i1.10962","article-title":"\u201cActive discriminative text representation learning,\u201d","author":"Zhang","year":"2016","journal-title":"Proceedings of the AAAI Conference on Artificial Intelligence"},{"key":"B63","article-title":"Fast and scalable analysis of massive social graphs","author":"Zhao","year":"2011","journal-title":"arXiv preprint arXiv:1107.5114"},{"key":"B64","doi-asserted-by":"crossref","first-page":"375","DOI":"10.1145\/3035918.3035927","article-title":"\u201cDag reduction: fast answering reachability queries,\u201d","volume-title":"Proceedings of the 2017 ACM International Conference on Management of Data, SIGMOD '17","author":"Zhou","year":"2017"},{"key":"B65","doi-asserted-by":"publisher","first-page":"723","DOI":"10.1007\/s10115-016-0961-9","article-title":"Towards efficient top-k reliability search on uncertain graphs","volume":"50","author":"Zhu","year":"2017","journal-title":"Knowl. Inf. Syst"}],"container-title":["Frontiers in Big Data"],"original-title":[],"link":[{"URL":"https:\/\/www.frontiersin.org\/articles\/10.3389\/fdata.2024.1427104\/full","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,11,19]],"date-time":"2024-11-19T06:20:01Z","timestamp":1731997201000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.frontiersin.org\/articles\/10.3389\/fdata.2024.1427104\/full"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,11,19]]},"references-count":65,"alternative-id":["10.3389\/fdata.2024.1427104"],"URL":"https:\/\/doi.org\/10.3389\/fdata.2024.1427104","relation":{},"ISSN":["2624-909X"],"issn-type":[{"type":"electronic","value":"2624-909X"}],"subject":[],"published":{"date-parts":[[2024,11,19]]},"article-number":"1427104"}}