{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,15]],"date-time":"2026-07-15T07:11:46Z","timestamp":1784099506226,"version":"3.55.0"},"reference-count":47,"publisher":"Association for Computing Machinery (ACM)","issue":"5","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2021,1]]},"abstract":"<jats:p>Queries to detect isomorphic subgraphs are important in graph-based data management. While the problem of subgraph isomorphism search has received considerable attention for the static setting of a single query, or a batch thereof, existing approaches do not scale to a dynamic setting of a continuous stream of queries. In this paper, we address the scalability challenges induced by a stream of subgraph isomorphism queries by caching and re-use of previous results. We first present a novel subgraph index based on graph embeddings that serves as the foundation for efficient stream processing. It enables not only effective caching and re-use of results, but also speeds-up traditional algorithms for subgraph isomorphism in case of cache misses. Moreover, we propose cache management policies that incorporate notions of reusability of query results. Experiments using real-world datasets demonstrate the effectiveness of our approach in handling isomorphic subgraph search for streams of queries.<\/jats:p>","DOI":"10.14778\/3446095.3446097","type":"journal-article","created":{"date-parts":[[2021,3,23]],"date-time":"2021-03-23T16:36:58Z","timestamp":1616517418000},"page":"730-742","source":"Crossref","is-referenced-by-count":27,"title":["Efficient streaming subgraph isomorphism with graph neural networks"],"prefix":"10.14778","volume":"14","author":[{"given":"Chi Thang","family":"Duong","sequence":"first","affiliation":[{"name":"EPFL"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Trung Dung","family":"Hoang","sequence":"additional","affiliation":[{"name":"HUST"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Hongzhi","family":"Yin","sequence":"additional","affiliation":[{"name":"The University of Queensland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Matthias","family":"Weidlich","sequence":"additional","affiliation":[{"name":"Humboldt-Universit\u00e4t zu Berlin"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Quoc Viet Hung","family":"Nguyen","sequence":"additional","affiliation":[{"name":"Griffith University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Karl","family":"Aberer","sequence":"additional","affiliation":[{"name":"EPFL"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2021,3,23]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"DBProxy: A dynamic data cache for Web applications","author":"Amiri Khalil"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.14778\/3311880.3311887"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.14778\/3157794.3157801"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2915236"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/1887854.1887873"},{"key":"e_1_2_1_6_1","volume-title":"Dynamic Structural Similarity on Graphs. arXiv preprint arXiv:1805.01419","author":"Castrillo Eduar","year":"2018"},{"key":"e_1_2_1_7_1","unstructured":"ChemSpider. 2020. ChemSpider Data Sources. www.chemspider.com\/DataSources.aspx.  ChemSpider. 2020. ChemSpider Data Sources. www.chemspider.com\/DataSources.aspx."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2004.75"},{"key":"e_1_2_1_9_1","volume-title":"Marc Van Kreveld, and Mark Overmars","author":"Berg Mark De","year":"2008"},{"key":"e_1_2_1_10_1","volume-title":"Ha The Hien Dang, Quoc Viet Hung Nguyen, and Karl Aberer.","author":"Duong Chi Thang","year":"2019"},{"key":"e_1_2_1_11_1","volume-title":"Matthias Weidlich, Quoc Viet Hung Nguyen, and Karl Aberer.","author":"Duong Chi Thang","year":"2020"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.14778\/1453856.1453917"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2484702.2484709"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.5555\/3305381.3305512"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2939672.2939754"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/971697.602266"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.5555\/3294771.3294869"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2465300"},{"key":"e_1_2_1_19_1","volume-title":"Maximum common subgraph: some upper bound and lower bound results. BMC bioinformatics 7, 4","author":"Huang Xiuzhen","year":"2006"},{"key":"e_1_2_1_20_1","volume-title":"Thang Huynh Quyet, Quoc Viet Hung Nguyen, Abdul Sattar, et al.","author":"Huynh Thanh Trung","year":"2019"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/253262.253347"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.14778\/2824032.2824054"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3196917"},{"key":"e_1_2_1_24_1","volume-title":"Semi-supervised classification with graph convolutional networks. NIPS","author":"Kipf Thomas N","year":"2016"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2011.5767909"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.5555\/977401.978167"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2012.37"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.14778\/2535568.2448946"},{"key":"e_1_2_1_29_1","doi-asserted-by":"crossref","volume-title":"Workload-Aware Subgraph Query Caching and Processing in Large Graphs","author":"Liang Yongjiang","DOI":"10.1109\/ICDE.2019.00190"},{"key":"e_1_2_1_30_1","unstructured":"D\u00e1niel Marx and Michal Pilipczuk. 2014. Everything you always wanted to know about the parameterized complexity of Subgraph Isomorphism. (2014).  D\u00e1niel Marx and Michal Pilipczuk. 2014. Everything you always wanted to know about the parameterized complexity of Subgraph Isomorphism. (2014)."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v33i01.33014602"},{"key":"e_1_2_1_32_1","volume-title":"Fast approximate nearest neighbors with automatic algorithm configuration. VISAPP (1) 2, 331--340","author":"Muja Marius","year":"2009"},{"key":"e_1_2_1_33_1","volume-title":"subgraph2vec: Learning distributed representations of rooted sub-graphs from large graphs. arXiv preprint arXiv:1606.08928","author":"Narayanan Annamalai","year":"2016"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1961659.1961663"},{"key":"e_1_2_1_35_1","volume-title":"Cache Optimization Models and Algorithms. arXiv preprint arXiv:1912.12339","author":"Paschos Georgios","year":"2019"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/2623330.2623732"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.14778\/3021924.3021929"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.14778\/1453856.1453899"},{"key":"e_1_2_1_39_1","doi-asserted-by":"crossref","volume-title":"Optimised KD-trees for fast image descriptor matching","author":"Silpa-Anan Chanop","DOI":"10.1109\/CVPR.2008.4587638"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.eswa.2019.112883"},{"key":"e_1_2_1_41_1","volume-title":"Nguyen Thanh Tam, Hongzhi Yin, Matthias Weidlich, and Nguyen Quoc Viet Hung.","author":"Trung Huynh Thanh","year":"2020"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/321921.321925"},{"key":"e_1_2_1_43_1","volume-title":"Deep graph infomax. ICLR","author":"Veli\u010dkovi\u0107 Petar","year":"2018"},{"key":"e_1_2_1_44_1","doi-asserted-by":"crossref","unstructured":"Neal E Young. 2008. Online paging and caching. (2008).  Neal E Young. 2008. Online paging and caching. (2008).","DOI":"10.1007\/978-0-387-30162-4_267"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/1516360.1516384"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.5555\/1325851.1325957"},{"key":"e_1_2_1_47_1","volume-title":"Jeffrey Xu Yu, and Hong Cheng","author":"Zhu Yuanyuan","year":"2019"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3446095.3446097","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T11:19:57Z","timestamp":1672226397000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3446095.3446097"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,1]]},"references-count":47,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2021,1]]}},"alternative-id":["10.14778\/3446095.3446097"],"URL":"https:\/\/doi.org\/10.14778\/3446095.3446097","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2021,1]]}}}