{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:58:27Z","timestamp":1750309107107,"version":"3.41.0"},"reference-count":55,"publisher":"Association for Computing Machinery (ACM)","issue":"8","license":[{"start":{"date-parts":[[2023,5,12]],"date-time":"2023-05-12T00:00:00Z","timestamp":1683849600000},"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":[[2023,9,30]]},"abstract":"<jats:p>Feature extraction is an essential task in graph analytics. These feature vectors, called graph descriptors, are used in downstream vector-space-based graph analysis models. This idea has proved fruitful in the past, with spectral-based graph descriptors providing state-of-the-art classification accuracy. However, known algorithms to compute meaningful descriptors do not scale to large graphs since: (1) they require storing the entire graph in memory, and (2) the end-user has no control over the algorithm\u2019s runtime. In this article, we present streaming algorithms to approximately compute three different graph descriptors capturing the essential structure of graphs. Operating on edge streams allows us to avoid storing the entire graph in memory, and controlling the sample size enables us to keep the runtime of our algorithms within desired bounds. We demonstrate the efficacy of the proposed descriptors by analyzing the approximation error and classification accuracy. Our scalable algorithms compute descriptors of graphs with millions of edges within minutes. Moreover, these descriptors yield predictive accuracy comparable to the state-of-the-art methods but can be computed using only 25% as much memory.<\/jats:p>","DOI":"10.1145\/3591468","type":"journal-article","created":{"date-parts":[[2023,4,8]],"date-time":"2023-04-08T10:32:05Z","timestamp":1680949925000},"page":"1-25","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Computing Graph Descriptors on Edge Streams"],"prefix":"10.1145","volume":"17","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5590-5235","authenticated-orcid":false,"given":"Zohair Raza","family":"Hassan","sequence":"first","affiliation":[{"name":"Rochester Institute of Technology, Rochester, NY, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8121-2168","authenticated-orcid":false,"given":"Sarwan","family":"Ali","sequence":"additional","affiliation":[{"name":"Georgia State University, Atlanta, GA, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6955-6168","authenticated-orcid":false,"given":"Imdadullah","family":"Khan","sequence":"additional","affiliation":[{"name":"Lahore University of Management Sciences, Lahore, Punjab, Pakistan"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6961-0961","authenticated-orcid":false,"given":"Mudassir","family":"Shabbir","sequence":"additional","affiliation":[{"name":"Information Technology University, Lahore, Punjab, Pakistan"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9013-1463","authenticated-orcid":false,"given":"Waseem","family":"Abbas","sequence":"additional","affiliation":[{"name":"University of Texas at Dallas, Richardson, TX, USA"}]}],"member":"320","published-online":{"date-parts":[[2023,5,12]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ins.2020.01.037"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.3127\/ajis.v21i0.1563"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ins.2020.05.032"},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1145\/2601438"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1109\/AECT47998.2020.9194211"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1145\/3442390"},{"key":"e_1_3_2_8_2","first-page":"684","volume-title":"Proceedings of the Symposium on Theory of Computing","author":"Babai L.","year":"2016","unstructured":"L. Babai. 2016. Graph isomorphism in quasipolynomial time. In Proceedings of the Symposium on Theory of Computing. 684\u2013697."},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975321.38"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1145\/2492517.2492582"},{"key":"e_1_3_2_11_2","first-page":"244","volume-title":"Proceedings of the 23rd International Conference on Neural Information Processing Systems","author":"Bo L.","year":"2010","unstructured":"L. Bo, X. Ren, and D. Fox. 2010. Kernel descriptors for visual recognition. In Proceedings of the 23rd International Conference on Neural Information Processing Systems. 244\u2013252."},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2005.132"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00026-006-0289-3"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/2806416.2806512"},{"key":"e_1_3_2_15_2","first-page":"1091","volume-title":"Proceedings of the International Conference on Machine Learning","author":"Chen P.","year":"2019","unstructured":"P. Chen, L. Wu, S. Liu, and I. Rajapakse. 2019. Fast incremental von Neumann graph entropy computation: Theory, algorithm, and applications. In Proceedings of the International Conference on Machine Learning. 1091\u20131101."},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1145\/3110025.3110042"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1145\/3446668"},{"key":"e_1_3_2_18_2","first-page":"5119","volume-title":"Proceedings of the 31st International Conference on Neural Information Processing Systems","author":"Duran A.","year":"2017","unstructured":"A. Duran and M. Niepert. 2017. Learning graph representations with embedding propagation. In Proceedings of the 31st International Conference on Neural Information Processing Systems. 5119\u20135130."},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1109\/TNNLS.2018.2884700"},{"key":"e_1_3_2_20_2","first-page":"6935","volume-title":"Proceedings of the 31st International Conference on Neural Information Processing Systems","author":"Farhan M.","year":"2017","unstructured":"M. Farhan, J. Tariq, A. Zaman, M. Shabbir, and I. Khan. 2017. Efficient approximation algorithms for strings kernel based sequence classification. In Proceedings of the 31st International Conference on Neural Information Processing Systems. 6935\u20136945."},{"key":"e_1_3_2_21_2","volume-title":"Proceedings of the 35th Conference on Neural Information Processing Systems Datasets and Benchmarks Track (Round 1)","author":"Freitas S.","year":"2021","unstructured":"S. Freitas, Y. Dong, J. Neil, and D. H. Chau. 2021. A large-scale database for graph representation learning. In Proceedings of the 35th Conference on Neural Information Processing Systems Datasets and Benchmarks Track (Round 1). 13."},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1145\/2939672.2939754"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-47426-3_60"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/17.1.107"},{"issue":"3","key":"e_1_3_2_25_2","first-page":"58","article-title":"Toward understanding and evaluating structural node embeddings","volume":"16","author":"Jin J.","year":"2021","unstructured":"J. Jin, M. Heimann, D. Jin, and D. Koutra. 2021. Toward understanding and evaluating structural node embeddings. ACM Transactions on Knowledge Discovery from Data 16, 3, Article 58 (2021), 32 pages.","journal-title":"ACM Transactions on Knowledge Discovery from Data"},{"key":"e_1_3_2_26_2","first-page":"2982","volume-title":"Proceedings of the 30th International Conference on Neural Information Processing Systems","author":"Kondor R.","year":"2016","unstructured":"R. Kondor and H. Pan. 2016. The multiscale Laplacian graph kernel. In Proceedings of the 30th International Conference on Neural Information Processing Systems. 2982\u20132990."},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.1145\/2824443"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972825.75"},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.1145\/2487788.2488173"},{"key":"e_1_3_2_30_2","article-title":"A simple baseline algorithm for graph classification","author":"Lara N.","year":"2018","unstructured":"N. Lara and E. Pineau. 2018. A simple baseline algorithm for graph classification. In Proceedings of the Relational Representation Learning Workshop.","journal-title":"Proceedings of the Relational Representation Learning Workshop"},{"issue":"1","key":"e_1_3_2_31_2","first-page":"3221","article-title":"Accelerating t-SNE using tree-based algorithms","volume":"15","author":"Maaten L.","year":"2014","unstructured":"L. Maaten. 2014. Accelerating t-SNE using tree-based algorithms. Journal of Machine Learning Research 15, 1 (2014), 3221\u20133245.","journal-title":"Journal of Machine Learning Research"},{"key":"e_1_3_2_32_2","article-title":"TUDataset: A collection of benchmark datasets for learning with graphs","author":"Morris C.","year":"2020","unstructured":"C. Morris, N. Kriege, F. Bause, K. Kersting, P. Mutzel, and M. Neumann. 2020. TUDataset: A collection of benchmark datasets for learning with graphs. In Proceedings of the ICML 2020 Workshop on Graph Representation Learning and Beyond.","journal-title":"Proceedings of the ICML 2020 Workshop on Graph Representation Learning and Beyond"},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v33i01.33014602"},{"key":"e_1_3_2_34_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10994-015-5517-9"},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.1109\/TCDS.2020.3025137"},{"key":"e_1_3_2_36_2","doi-asserted-by":"publisher","DOI":"10.1145\/3340531.3412757"},{"key":"e_1_3_2_37_2","doi-asserted-by":"publisher","DOI":"10.1145\/3340531.3411866"},{"key":"e_1_3_2_38_2","doi-asserted-by":"publisher","DOI":"10.1145\/3446637"},{"key":"e_1_3_2_39_2","doi-asserted-by":"publisher","DOI":"10.1145\/3357384.3357983"},{"key":"e_1_3_2_40_2","doi-asserted-by":"publisher","DOI":"10.1109\/TSMC.1983.6313167"},{"key":"e_1_3_2_41_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipm.2020.102204"},{"key":"e_1_3_2_42_2","doi-asserted-by":"publisher","DOI":"10.1145\/3473911"},{"key":"e_1_3_2_43_2","doi-asserted-by":"publisher","DOI":"10.5555\/1953048.2078187"},{"key":"e_1_3_2_44_2","first-page":"488","volume-title":"Proceedings of the International Conference on Artificial Intelligence and Statistics","author":"Shervashidze N.","year":"2009","unstructured":"N. Shervashidze, S. Vishwanathan, T. Petri, K. Mehlhorn, and K. Borgwardt. 2009. Efficient Graphlet kernels for large graph comparison. In Proceedings of the International Conference on Artificial Intelligence and Statistics. 488\u2013495."},{"key":"e_1_3_2_45_2","doi-asserted-by":"publisher","DOI":"10.1145\/3495011"},{"key":"e_1_3_2_46_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-93040-4_51"},{"key":"e_1_3_2_47_2","doi-asserted-by":"publisher","DOI":"10.1145\/2939672.2939771"},{"key":"e_1_3_2_48_2","first-page":"200","volume-title":"Proceedings of the Pacific Asia Conference on Information Systems","author":"Tariq J.","year":"2017","unstructured":"J. Tariq, M. Ahmad, I. Khan, and M. Shabbir. 2017. Scalable approximation algorithm for network immunization. In Proceedings of the Pacific Asia Conference on Information Systems. 200."},{"key":"e_1_3_2_49_2","doi-asserted-by":"publisher","DOI":"10.1145\/3219819.3219991"},{"key":"e_1_3_2_50_2","doi-asserted-by":"publisher","DOI":"10.1145\/3366423.3380026"},{"key":"e_1_3_2_51_2","first-page":"88","volume-title":"Proceedings of the 31st International Conference on Neural Information Processing Systems","author":"Verma S.","year":"2017","unstructured":"S. Verma and Z. Zhang. 2017. Hunt for the unique, stable, sparse and fast feature learning on graphs. In Proceedings of the 31st International Conference on Neural Information Processing Systems. 88\u201398."},{"key":"e_1_3_2_52_2","doi-asserted-by":"publisher","DOI":"10.1145\/3147.3165"},{"key":"e_1_3_2_53_2","volume-title":"Proceedings of the International Conference on Learning Representations","author":"Xu K.","year":"2019","unstructured":"K. Xu, W. Hu, J. Leskovec, and S. Jegelka. 2019. How powerful are graph neural networks?. In Proceedings of the International Conference on Learning Representations. 17."},{"key":"e_1_3_2_54_2","doi-asserted-by":"publisher","DOI":"10.1145\/2783258.2783417"},{"key":"e_1_3_2_55_2","doi-asserted-by":"publisher","DOI":"10.24963\/ijcai.2018\/502"},{"key":"e_1_3_2_56_2","doi-asserted-by":"publisher","DOI":"10.24963\/ijcai.2020\/192"}],"container-title":["ACM Transactions on Knowledge Discovery from Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3591468","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3591468","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T22:48:47Z","timestamp":1750286927000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3591468"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,5,12]]},"references-count":55,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2023,9,30]]}},"alternative-id":["10.1145\/3591468"],"URL":"https:\/\/doi.org\/10.1145\/3591468","relation":{},"ISSN":["1556-4681","1556-472X"],"issn-type":[{"type":"print","value":"1556-4681"},{"type":"electronic","value":"1556-472X"}],"subject":[],"published":{"date-parts":[[2023,5,12]]},"assertion":[{"value":"2022-06-06","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-04-05","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-05-12","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}