{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,25]],"date-time":"2026-06-25T09:10:16Z","timestamp":1782378616854,"version":"3.54.5"},"reference-count":41,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2018,1,23]],"date-time":"2018-01-23T00:00:00Z","timestamp":1516665600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["NSF-DMS-1418265, NSF-EAR-1520870"],"award-info":[{"award-number":["NSF-DMS-1418265, NSF-EAR-1520870"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Knowl. Discov. Data"],"published-print":{"date-parts":[[2018,6,30]]},"abstract":"<jats:p>\n            An increasing number of applications are modeled and analyzed in network form, where nodes represent entities of interest and edges represent interactions or relationships between entities. Commonly, such relationship analysis tools assume homogeneity in both node type and edge type. Recent research has sought to redress the assumption of homogeneity and focused on mining heterogeneous information networks (HINs) where both nodes and edges can be of different types. Building on such efforts, in this work, we articulate a novel approach for mining relationships across entities in such networks while accounting for user preference over relationship type and interestingness metric. We formalize the problem as a top-\n            <jats:italic>k<\/jats:italic>\n            lightest paths problem, contextualized in a real-world communication network, and seek to find the\n            <jats:italic>k<\/jats:italic>\n            most interesting path instances matching the preferred relationship type. Our solution, PROphetic HEuristic Algorithm for Path Searching (PRO-HEAPS), leverages a combination of novel graph preprocessing techniques, well-designed heuristics and the venerable A* search algorithm. We run our algorithm on real-world large-scale graphs and show that our algorithm significantly outperforms a wide variety of baseline approaches with speedups as large as 100X.\n          <\/jats:p>\n          <jats:p>To widen the range of applications, we also extend PRO-HEAPS to (i) support relationship analysis between two groups of entities and (ii) allow pattern path in the query to contain logical statements with operators AND, OR, NOT, and wild-card \u201c.\u201d. We run experiments using this generalized version of PRO-HEAPS and demonstrate that the advantage of PRO-HEAPS becomes even more pronounced for these general cases. Furthermore, we conduct a comprehensive analysis to study how the performance of PRO-HEAPS varies with respect to various attributes of the input HIN. We finally conduct a case study to demonstrate valuable applications of our algorithm.<\/jats:p>","DOI":"10.1145\/3154401","type":"journal-article","created":{"date-parts":[[2018,1,23]],"date-time":"2018-01-23T14:53:36Z","timestamp":1516719216000},"page":"1-27","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Prioritized Relationship Analysis in Heterogeneous Information Networks"],"prefix":"10.1145","volume":"12","author":[{"given":"Jiongqian","family":"Liang","sequence":"first","affiliation":[{"name":"The Ohio State University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Deepak","family":"Ajwani","sequence":"additional","affiliation":[{"name":"Bell Labs, Ireland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Patrick K.","family":"Nicholson","sequence":"additional","affiliation":[{"name":"Bell Labs, Ireland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Alessandra","family":"Sala","sequence":"additional","affiliation":[{"name":"Bell Labs, Ireland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Srinivasan","family":"Parthasarathy","sequence":"additional","affiliation":[{"name":"The Ohio State University"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2018,1,23]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2465315"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/11427995_77"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/210332.210337"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/BDCloud.2014.101"},{"key":"e_1_2_1_5_1","volume-title":"Keyword searching and browsing in databases using BANKS","author":"Bhalotia Gaurav","unstructured":"Gaurav Bhalotia , Arvind Hulgeri , Charuta Nakhe , Soumen Chakrabarti , and Shashank Sudarshan . 2002. Keyword searching and browsing in databases using BANKS . In ICDE. IEEE. Gaurav Bhalotia, Arvind Hulgeri, Charuta Nakhe, Soumen Chakrabarti, and Shashank Sudarshan. 2002. Keyword searching and browsing in databases using BANKS. In ICDE. IEEE."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/944919.944937"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/971617.971643"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/1618595.1618605"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1718487.1718537"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1014052.1014068"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.14778\/2078331.2078339"},{"key":"e_1_2_1_12_1","volume-title":"Johnson","author":"Garey Michael R.","year":"2002","unstructured":"Michael R. Garey and David S . Johnson . 2002 . Computers and Intractability, Vol . 29. WH Freeman . Michael R. Garey and David S. Johnson. 2002. Computers and Intractability, Vol. 29. WH Freeman."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICPR.2002.1048250"},{"key":"e_1_2_1_14_1","volume-title":"An efficient implementation of an algorithm for finding k shortest simple paths. Networks 34.2","author":"Hadjiconstantinou Eleni","year":"1999","unstructured":"Eleni Hadjiconstantinou and Nicos Christofides . 1999. An efficient implementation of an algorithm for finding k shortest simple paths. Networks 34.2 ( 1999 ), 88--101. Eleni Hadjiconstantinou and Nicos Christofides. 1999. An efficient implementation of an algorithm for finding k shortest simple paths. Networks 34.2 (1999), 88--101."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1290672.1290682"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.65.026107"},{"key":"e_1_2_1_17_1","volume-title":"Proceedings of the VLDB Endowment","author":"Kacholia Varun","year":"2005","unstructured":"Varun Kacholia , Shashank Pandit , Soumen Chakrabarti , S. Sudarshan , Rushi Desai , and Hrishikesh Karambelkar . 2005 . Bidirectional expansion for keyword search on graph databases . Proceedings of the VLDB Endowment (2005), 505--516. Varun Kacholia, Shashank Pandit, Soumen Chakrabarti, S. Sudarshan, Rushi Desai, and Hrishikesh Karambelkar. 2005. Bidirectional expansion for keyword search on graph databases. Proceedings of the VLDB Endowment (2005), 505--516."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230120406"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989323.1989418"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.14778\/2535569.2448952"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10994-010-5205-8"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2872427.2883007"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975321.18"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2736277.2741123"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.5555\/525"},{"key":"e_1_2_1_26_1","first-page":"97","article-title":"Artificial Intelligence: A modern approach","volume":"25","author":"Russell Stuart","year":"1995","unstructured":"Stuart Russell and Peter Norvig . 1995 . Artificial Intelligence: A modern approach . Pearson Education 25 (1995), 97 -- 104 . Stuart Russell and Peter Norvig. 1995. Artificial Intelligence: A modern approach. Pearson Education 25 (1995), 97--104.","journal-title":"Pearson Education"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1089\/cmb.2006.13.133"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/543613.543620"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2013.2297920"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2016.2598561"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2806416.2806528"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/bts212"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/2530531"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/2481244.2481248"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/2124295.2124373"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.14778\/3402707.3402736"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/1150402.1150448"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/321921.321925"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/HiBi.2009.21"},{"key":"e_1_2_1_40_1","volume-title":"Proceedings of the 5th Innovative Applications of Artificial Intelligence Conference","volume":"3","author":"Wolverton Michael","year":"2003","unstructured":"Michael Wolverton , Pauline Berry , Ian W. Harrison , John D. Lowrance , David N. Morley , Andres C. Rodriguez , Enrique H. Ruspini , and Jerome Thomere . 2003 . LAW: A workbench for approximate pattern matching in relational data . In Proceedings of the 5th Innovative Applications of Artificial Intelligence Conference , Vol. 3 . 143--150. Michael Wolverton, Pauline Berry, Ian W. Harrison, John D. Lowrance, David N. Morley, Andres C. Rodriguez, Enrique H. Ruspini, and Jerome Thomere. 2003. LAW: A workbench for approximate pattern matching in relational data. In Proceedings of the 5th Innovative Applications of Artificial Intelligence Conference, Vol. 3. 143--150."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.17.11.712"}],"container-title":["ACM Transactions on Knowledge Discovery from Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3154401","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3154401","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3154401","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T02:11:26Z","timestamp":1750212686000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3154401"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,1,23]]},"references-count":41,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2018,6,30]]}},"alternative-id":["10.1145\/3154401"],"URL":"https:\/\/doi.org\/10.1145\/3154401","relation":{},"ISSN":["1556-4681","1556-472X"],"issn-type":[{"value":"1556-4681","type":"print"},{"value":"1556-472X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,1,23]]},"assertion":[{"value":"2017-01-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-10-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-01-23","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}