{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,25]],"date-time":"2026-07-25T03:42:10Z","timestamp":1784950930570,"version":"3.55.0"},"reference-count":67,"publisher":"Association for Computing Machinery (ACM)","issue":"9","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2020,5]]},"abstract":"<jats:p>\n            We investigate the problem of\n            <jats:italic>correlated subgraphs mining<\/jats:italic>\n            (CSM) where the goal is to identify pairs of subgraph patterns that frequently co-occur in proximity within a single graph. Correlated subgraph patterns are different from frequent subgraphs due to the flexibility in connections between constituent subgraph instances and thus, existing frequent subgraphs mining algorithms cannot be directly applied for CSM. Moreover, computing the degree of correlation between two patterns requires enumerating and finding distances between every pair of subgraph instances of both patterns - a task that is both memory-intensive as well as computationally demanding. To this end, we propose two holistic\n            <jats:italic>best-first<\/jats:italic>\n            exploration algorithms: CSM-E (an exact method) and CSM-A (a more efficient approximate method with near-optimal quality). To further improve efficiency, we propose a top-\n            <jats:italic>k<\/jats:italic>\n            pruning strategy, while to reduce memory footprint, we develop a compressed data structure called\n            <jats:italic>R<\/jats:italic>\n            eplica, which stores all instances of a subgraph pattern on demand. Our empirical results demonstrate that the proposed algorithms not only mine interesting correlations, but also achieve good scalability over large networks.\n          <\/jats:p>","DOI":"10.14778\/3397230.3397245","type":"journal-article","created":{"date-parts":[[2020,6,29]],"date-time":"2020-06-29T11:46:24Z","timestamp":1593431184000},"page":"1511-1524","source":"Crossref","is-referenced-by-count":16,"title":["Mining Top-\n            <i>k<\/i>\n            pairs of correlated subgraphs in a large network"],"prefix":"10.14778","volume":"13","author":[{"given":"Arneish","family":"Prateek","sequence":"first","affiliation":[{"name":"Indian Institute of Technology, Delhi"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Arijit","family":"Khan","sequence":"additional","affiliation":[{"name":"Nanyang Technological University, Singapore"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Akshit","family":"Goyal","sequence":"additional","affiliation":[{"name":"Indian Institute of Technology, Delhi"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sayan","family":"Ranu","sequence":"additional","affiliation":[{"name":"Indian Institute of Technology, Delhi"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2020,6,26]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"GO for utility process. http:\/\/www.candidagenome.org\/cgi-bin\/GO\/go.pl?goid=1901522.  GO for utility process. http:\/\/www.candidagenome.org\/cgi-bin\/GO\/go.pl?goid=1901522."},{"key":"e_1_2_1_2_1","unstructured":"Kendall's Tau. https:\/\/en.wikipedia.org\/wiki\/Kendall_rank_correlation_coefficient.  Kendall's Tau. https:\/\/en.wikipedia.org\/wiki\/Kendall_rank_correlation_coefficient."},{"key":"e_1_2_1_3_1","unstructured":"Source for Chemical dataset. http:\/\/pubchem.ncbi.nlm.nih.gov.  Source for Chemical dataset. http:\/\/pubchem.ncbi.nlm.nih.gov."},{"key":"e_1_2_1_4_1","unstructured":"Source for Citeseer dataset. http:\/\/networkrepository.com\/citeseer.php.  Source for Citeseer dataset. http:\/\/networkrepository.com\/citeseer.php."},{"key":"e_1_2_1_5_1","unstructured":"Source for Coauthor and Citation (DBLP) datasets. https:\/\/www.aminer.org\/citation.  Source for Coauthor and Citation (DBLP) datasets. https:\/\/www.aminer.org\/citation."},{"key":"e_1_2_1_6_1","unstructured":"Source for LastFM dataset. https:\/\/www.last.fm\/.  Source for LastFM dataset. https:\/\/www.last.fm\/."},{"key":"e_1_2_1_7_1","unstructured":"Source for Memetracker dataset. https:\/\/snap.stanford.edu\/data\/memetracker9.html.  Source for Memetracker dataset. https:\/\/snap.stanford.edu\/data\/memetracker9.html."},{"key":"e_1_2_1_8_1","unstructured":"Source for MiCo dataset. http:\/\/academic.research.microsoft.com.  Source for MiCo dataset. http:\/\/academic.research.microsoft.com."},{"key":"e_1_2_1_9_1","unstructured":"Source for Yeast dataset. http:\/\/string-db.org\/cgi\/download.pl.  Source for Yeast dataset. http:\/\/string-db.org\/cgi\/download.pl."},{"key":"e_1_2_1_10_1","volume-title":"VLDB","author":"Agrawal R.","year":"1994"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1038\/75556"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.5555\/844380.844706"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-68125-0_84"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2017.2696940"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687627.1687711"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1613\/jair.43"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732286.2732289"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920878"},{"issue":"1","key":"e_1_2_1_19_1","first-page":"1161","volume":"3","author":"Fan W.","year":"2010","journal-title":"Graph Homomorphism Revisited for Graph Matching. PVLDB"},{"key":"e_1_2_1_20_1","volume-title":"MLG","author":"Fiedler M.","year":"2007"},{"key":"e_1_2_1_21_1","volume-title":"AAAI FS.","author":"Gallagher B.","year":"2006"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989323.1989421"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2737791"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2007.45"},{"issue":"1","key":"e_1_2_1_25_1","first-page":"730","volume":"2","author":"Hasan M. A.","year":"2009","journal-title":"Output Space Sampling for Graph Patterns. PVLDB"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.5555\/795662.796255"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.5555\/951949.952101"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.5555\/645804.669817"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.14778\/2824032.2824106"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2012.49"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807262"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2009.54"},{"key":"e_1_2_1_33_1","doi-asserted-by":"crossref","unstructured":"B. P. Kelley B. Yuan F. Lewitter R. Sharan B. R. Stockwell and T. Ideker. PathBLAST: A Tool for Alignment of Protein Interaction Networks. Nucleic Acids Res 32(Web-Server-Issue):83--88 2004.  B. P. Kelley B. Yuan F. Lewitter R. Sharan B. R. Stockwell and T. Ideker. PathBLAST: A Tool for Alignment of Protein Interaction Networks. Nucleic Acids Res 32(Web-Server-Issue):83--88 2004.","DOI":"10.1093\/nar\/gkh411"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989323.1989418"},{"issue":"3","key":"e_1_2_1_35_1","first-page":"181","volume":"6","author":"Khan A.","year":"2013","journal-title":"NeMa: Fast Graph Search with Label Similarity. PVLDB"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807261"},{"key":"e_1_2_1_37_1","doi-asserted-by":"crossref","unstructured":"R. Koike T. Amemiya M. Ota and A. Kidera. Protein Structural Change upon Ligand Binding Correlates with Enzymatic Reaction Mechanism. Journal of molecular biology 379:397--401 07 2008.  R. Koike T. Amemiya M. Ota and A. Kidera. Protein Structural Change upon Ligand Binding Correlates with Enzymatic Reaction Mechanism. Journal of molecular biology 379:397--401 07 2008.","DOI":"10.1016\/j.jmb.2008.04.019"},{"key":"e_1_2_1_38_1","first-page":"2060","article-title":"Alteration of State and Domain Architecture is Essential for Functional Transformation between Transferase and Hydrolase with the Same Scaffold. Protein Science : a Publication of the Prote","volume":"18","author":"Koike R.","year":"2009","journal-title":"Society"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.5555\/645496.658027"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972740.32"},{"key":"e_1_2_1_41_1","doi-asserted-by":"crossref","unstructured":"E. A. Lee S. Fung H. Sze-To and A. K. C. Wong. Discovering Co-occurring Patterns and their Biological Significance in Protein Families. BMC Bioinformatics 15(S-12):S2 2014.  E. A. Lee S. Fung H. Sze-To and A. K. C. Wong. Discovering Co-occurring Patterns and their Biological Significance in Protein Families. BMC Bioinformatics 15(S-12):S2 2014.","DOI":"10.1186\/1471-2105-15-S12-S2"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btl287"},{"issue":"4","key":"e_1_2_1_43_1","first-page":"310","volume":"5","author":"Ma S.","year":"2012","journal-title":"Capturing Topology in Graph Pattern Matching. PVLDB"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2016.7498233"},{"issue":"2","key":"e_1_2_1_45_1","first-page":"199","volume":"8","author":"Mongiov\u00ec M.","year":"2010","journal-title":"SIGMA: A Set-Cover-Based Inexact Graph Matching Algorithm. J. Bioinfo. and Comp. Bio."},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2016.0048"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10115-017-1129-y"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/1014052.1014134"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.14778\/3137628.3137647"},{"issue":"9","key":"e_1_2_1_50_1","first-page":"809","volume":"30","author":"Ranu S.","year":"2011","journal-title":"Probabilistic Substructure Mining From Small-Molecule Screens. Molecular Informatics"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/2487575.2487692"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2610524"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2009.133"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1021\/ci900035z"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/2247596.2247666"},{"issue":"5","key":"e_1_2_1_56_1","first-page":"466","volume":"5","author":"Silva A.","year":"2012","journal-title":"Mining Attribute-structure Correlated Patterns in Large Attributed Graphs. PVLDB"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0806627105"},{"issue":"2","key":"e_1_2_1_58_1","first-page":"232","volume":"23","author":"Tian Y.","year":"2006","journal-title":"SAGA: A Subgraph Matching Tool for Biological Graphs. Bioinfo."},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2008.4497505"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1145\/321921.321925"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1145\/3308558.3313448"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.5555\/844380.844749"},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1007\/11564126_39"},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376662"},{"key":"e_1_2_1_65_1","volume-title":"ICDM","author":"Yan X.","year":"2002"},{"key":"e_1_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1145\/956750.956784"},{"key":"e_1_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2009.96"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3397230.3397245","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T10:22:54Z","timestamp":1672222974000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3397230.3397245"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,5]]},"references-count":67,"journal-issue":{"issue":"9","published-print":{"date-parts":[[2020,5]]}},"alternative-id":["10.14778\/3397230.3397245"],"URL":"https:\/\/doi.org\/10.14778\/3397230.3397245","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2020,5]]}}}