{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,30]],"date-time":"2026-08-30T21:52:51Z","timestamp":1788126771849,"version":"build-2803163510"},"reference-count":64,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2020,12,7]],"date-time":"2020-12-07T00:00:00Z","timestamp":1607299200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Knowl. Discov. Data"],"published-print":{"date-parts":[[2021,2,28]]},"abstract":"<jats:p>\n            In this article, we introduce a generalization of graphlets to heterogeneous networks called\n            <jats:italic>typed graphlets<\/jats:italic>\n            . Informally, typed graphlets are small typed induced subgraphs. Typed graphlets generalize graphlets to rich heterogeneous networks as they explicitly capture the higher-order typed connectivity patterns in such networks. To address this problem, we describe a general framework for counting the occurrences of such typed graphlets. The proposed algorithms leverage a number of combinatorial relationships for different typed graphlets. For each edge, we count a few typed graphlets, and with these counts along with the combinatorial relationships, we obtain the exact counts of the other typed graphlets in\n            <jats:italic>o<\/jats:italic>\n            (1) constant time. Notably, the worst-case time complexity of the proposed approach matches the time complexity of the best known untyped algorithm. In addition, the approach lends itself to an efficient lock-free and asynchronous parallel implementation. While there are no existing methods for typed graphlets, there has been some work that focused on computing a different and much simpler notion called colored graphlet. The experiments confirm that our proposed approach is orders of magnitude faster\n            <jats:italic>and<\/jats:italic>\n            more space-efficient than methods for computing the simpler notion of colored graphlet. Unlike these methods that take hours on small networks, the proposed approach takes only seconds on large networks with millions of edges. Notably, since typed graphlet is more general than colored graphlet (and untyped graphlets), the counts of various typed graphlets can be combined to obtain the counts of the much simpler notion of colored graphlets. The proposed methods give rise to new opportunities and applications for typed graphlets.\n          <\/jats:p>","DOI":"10.1145\/3418773","type":"journal-article","created":{"date-parts":[[2020,12,7]],"date-time":"2020-12-07T19:04:16Z","timestamp":1607367856000},"page":"1-43","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":15,"title":["Heterogeneous Graphlets"],"prefix":"10.1145","volume":"15","author":[{"given":"Ryan A.","family":"Rossi","sequence":"first","affiliation":[{"name":"Adobe Research, Park Ave, San Jose, CA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Nesreen K.","family":"Ahmed","sequence":"additional","affiliation":[{"name":"Intel Labs, Santa Clara, CA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Aldo","family":"Carranza","sequence":"additional","affiliation":[{"name":"Stanford University, Via Ortega, Stanford, CA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"David","family":"Arbour","sequence":"additional","affiliation":[{"name":"Adobe Research, Park Ave, San Jose, CA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Anup","family":"Rao","sequence":"additional","affiliation":[{"name":"Adobe Research, Park Ave, San Jose, CA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sungchul","family":"Kim","sequence":"additional","affiliation":[{"name":"Adobe Research, Park Ave, San Jose, CA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Eunyee","family":"Koh","sequence":"additional","affiliation":[{"name":"Adobe Research, Park Ave, San Jose, CA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2020,12,7]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Dunlavy","author":"Acar Evrim","year":"2011"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.14778\/3137628.3137651"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2015.141"},{"key":"e_1_2_1_4_1","first-page":"1","article-title":"Graphlet decomposition: Framework, algorithms, and applications","volume":"50","author":"Ahmed Nesreen K.","year":"2016","journal-title":"Knowledge and Information Systems"},{"key":"e_1_2_1_5_1","volume-title":"Proceedings of the AAAI PAIR (Plan, Activity, and Intent Recognition) Workshop. 1--7.","author":"Ahmed Nesreen K.","year":"2017"},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of the Statistical Relational AI Workshop.","author":"Ahmed Nesreen K.","year":"2018"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10618-014-0365-y"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972771.14"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1177\/1073858406293182"},{"key":"e_1_2_1_10_1","volume-title":"Higher-order organization of complex networks. Science 353, 6295","author":"Benson Austin R.","year":"2016"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1038\/nrn2575"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2806416.2806512"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3394486.3403045"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3047307"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00012580"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/BIBM.2015.7359684"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/BigData.2017.8257974"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00779-005-0046-3"},{"key":"e_1_2_1_19_1","first-page":"17","article-title":"On the evolution of random graphs","volume":"5","author":"Erd\u0151s Paul","year":"1960","journal-title":"Publications of the Mathematical Institute of the Hungarian Academy of Sciences"},{"key":"e_1_2_1_20_1","volume-title":"Proceedings of the Conference on Applications, Technologies, Architectures, and Protocols for Computer Communication. ACM, 262","author":"Faloutsos M."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.122653799"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2939672.2939754"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1038\/s41598-018-30831-w"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/bts729"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btv227"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/WCNC.2008.389"},{"key":"e_1_2_1_27_1","volume-title":"Proceedings of the 2013 ACM International on Conference on Information and Knowledge Management. 179--188","author":"Kong Xiangnan"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1088\/1742-5468\/2011\/11\/P11005"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1089\/cmb.2006.13.182"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1772690.1772752"},{"key":"e_1_2_1_31_1","first-page":"985","article-title":"Kronecker graphs: An approach to modeling networks","author":"Leskovec Jure","year":"2010","journal-title":"Journal of Machine Learning Research 11"},{"key":"e_1_2_1_32_1","volume-title":"Proceedings of the 2012 International Conference on World Wide Web. 1019--1028","author":"Ryan"},{"key":"e_1_2_1_33_1","volume-title":"Proceedings of the 23rd International Conference on Machine learning.","author":"Long Bo"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comnet.2011.08.019"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1146\/annurev.soc.27.1.415"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.4137\/CIN.S680"},{"key":"e_1_2_1_37_1","doi-asserted-by":"crossref","unstructured":"R. Milo S. Shen-Orr S. Itzkovitz N. Kashtan D. Chklovskii and U. Alon. 2002. Network motifs: Simple building blocks of complex networks. Science 298 5594 (2002) 824--827.  R. Milo S. Shen-Orr S. Itzkovitz N. Kashtan D. Chklovskii and U. Alon. 2002. Network motifs: Simple building blocks of complex networks. Science 298 5594 (2002) 824--827.","DOI":"10.1126\/science.298.5594.824"},{"key":"e_1_2_1_38_1","volume-title":"Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 631--636","author":"Noble C. C."},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1038\/nature03607"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/2623330.2623732"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/3038912.3052597"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btl301"},{"key":"e_1_2_1_43_1","volume-title":"Modeling interactome: Scale-free or geometric?Bioinformatics 20, 18","author":"Pr\u017eulj N.","year":"2004"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0400054101"},{"key":"e_1_2_1_45_1","doi-asserted-by":"crossref","volume-title":"Discovering colored network motifs","author":"Ribeiro Pedro","DOI":"10.1007\/978-3-319-05401-8_11"},{"key":"e_1_2_1_46_1","volume-title":"Proceedings of the 29th AAAI Conference on Artificial Intelligence. 4292--4293","author":"Ryan"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/3336191.3371843"},{"key":"e_1_2_1_48_1","volume-title":"Proceedings of the 2013 IFIP Networking. 1--9.","author":"Rossi Ryan A.","year":"2013"},{"key":"e_1_2_1_49_1","volume-title":"Rossi and Rong Zhou","author":"Ryan","year":"2016"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1186\/s40537-018-0121-z"},{"key":"e_1_2_1_51_1","volume-title":"Proceedings of the 12th International Conference on Artificial Intelligence and Statistics.","author":"Shervashidze Nino","year":"2009"},{"key":"e_1_2_1_52_1","first-page":"2539","article-title":"Weisfeiler-lehman graph kernels","author":"Shervashidze Nino","year":"2011","journal-title":"The Journal of Machine Learning Research 12"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/bts376"},{"key":"e_1_2_1_54_1","doi-asserted-by":"crossref","unstructured":"Richard P. Stanley. 1986. What is Enumerative Combinatorics? Springer.  Richard P. Stanley. 1986. What is Enumerative Combinatorics? Springer.","DOI":"10.1007\/978-1-4615-9763-6"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.14778\/3402707.3402736"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/2736277.2741093"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.5555\/1756006.1859891"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ssci.2009.02.002"},{"key":"e_1_2_1_59_1","doi-asserted-by":"crossref","unstructured":"D. J. Watts and S. H. Strogatz. 1998. Collective dynamics of small-world networks. Nature 393 6684 (1998) 440--442.  D. J. Watts and S. H. Strogatz. 1998. Collective dynamics of small-world networks. Nature 393 6684 (1998) 440--442.","DOI":"10.1038\/30918"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btl038"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1145\/1557019.1557123"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1145\/2556195.2556259"},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNNLS.2015.2444417"},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2013.249"}],"container-title":["ACM Transactions on Knowledge Discovery from Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3418773","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3418773","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:02:28Z","timestamp":1750197748000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3418773"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,12,7]]},"references-count":64,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,2,28]]}},"alternative-id":["10.1145\/3418773"],"URL":"https:\/\/doi.org\/10.1145\/3418773","relation":{},"ISSN":["1556-4681","1556-472X"],"issn-type":[{"value":"1556-4681","type":"print"},{"value":"1556-472X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,12,7]]},"assertion":[{"value":"2019-03-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-08-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-12-07","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}