{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,15]],"date-time":"2026-01-15T01:09:11Z","timestamp":1768439351888,"version":"3.49.0"},"reference-count":51,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2023,2,20]],"date-time":"2023-02-20T00:00:00Z","timestamp":1676851200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,2,20]],"date-time":"2023-02-20T00:00:00Z","timestamp":1676851200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1452425"],"award-info":[{"award-number":["1452425"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Knowl Inf Syst"],"published-print":{"date-parts":[[2023,6]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Given a node-attributed graph, how can we efficiently represent it with few numerical features that expressively reflect its topology and attribute information? We propose <jats:sc>A-DOGE<\/jats:sc>, for attributed DOS-based graph embedding, based on density of states (DOS, a.k.a. spectral density) to tackle this problem. <jats:sc>A-DOGE<\/jats:sc> is designed to fulfill a long desiderata of desirable characteristics. Most notably, it capitalizes on efficient approximation algorithms for DOS, that we extend to blend in node labels and attributes for the first time, making it fast and scalable for large attributed graphs and graph databases. Being based on the entire eigenspectrum of a graph, <jats:sc>A-DOGE<\/jats:sc> can capture structural and attribute properties at multiple (\u201cglocal\u201d) scales. Moreover, it is unsupervised (i.e., agnostic to any specific objective) and lends itself to various interpretations, which makes it suitable for exploratory graph mining tasks. Finally, it processes each graph independent of others, making it amenable for streaming settings as well as parallelization. Through extensive experiments, we show the efficacy and efficiency of <jats:sc>A-DOGE<\/jats:sc> on exploratory graph analysis and graph classification tasks, where it significantly outperforms unsupervised baselines and achieves competitive performance with modern supervised GNNs, while achieving the best trade-off between accuracy and runtime.<\/jats:p>","DOI":"10.1007\/s10115-023-01836-3","type":"journal-article","created":{"date-parts":[[2023,2,23]],"date-time":"2023-02-23T16:37:56Z","timestamp":1677170276000},"page":"2455-2483","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Density of states for fast embedding node-attributed graphs"],"prefix":"10.1007","volume":"65","author":[{"given":"Lingxiao","family":"Zhao","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Saurabh","family":"Sawlani","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Leman","family":"Akoglu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,2,20]]},"reference":[{"issue":"3","key":"1836_CR1","doi-asserted-by":"publisher","first-page":"347","DOI":"10.1007\/s10115-007-0103-5","volume":"14","author":"N Wale","year":"2008","unstructured":"Wale N, Watson IA, Karypis G (2008) Comparison of descriptor spaces for chemical compound retrieval and classification. Knowl Inf Syst 14(3):347\u2013375","journal-title":"Knowl Inf Syst"},{"issue":"6","key":"1836_CR2","doi-asserted-by":"publisher","first-page":"853","DOI":"10.1093\/bioinformatics\/btq091","volume":"26","author":"N Przulj","year":"2010","unstructured":"Przulj N (2010) Biological network comparison using graphlet degree distribution. Bioinform 26(6):853\u2013854","journal-title":"Bioinform"},{"key":"1836_CR3","unstructured":"Duen H, Carey N, Jeffrey W, Adam W, Christos F (2011) Polonium: tera-scale graph mining for malware detection. In: SIAM SDM"},{"key":"1836_CR4","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1016\/j.neucom.2017.01.119","volume":"326","author":"B Ribeiro","year":"2019","unstructured":"Ribeiro B, Chen N, Kovacec A (2019) Shaping graph pattern mining for financial risk. Neurocomputing 326:123\u2013131","journal-title":"Neurocomputing"},{"key":"1836_CR5","volume-title":"Graph spectra for complex networks","author":"PV Mieghem","year":"2011","unstructured":"Mieghem PV (2011) Graph spectra for complex networks. Cambridge University Press, Cambridge"},{"issue":"3","key":"1836_CR6","doi-asserted-by":"publisher","first-page":"430","DOI":"10.1137\/0611030","volume":"11","author":"A Pothen","year":"1990","unstructured":"Pothen A, Simon HD, Liou K-P (1990) Partitioning sparse matrices with eigenvectors of graphs. SIAM J Matrix Anal Appl 11(3):430\u2013452","journal-title":"SIAM J Matrix Anal Appl"},{"key":"1836_CR7","doi-asserted-by":"crossref","unstructured":"Fill JA (1991) Eigenvalue bounds on convergence to stationarity for nonreversible markov chains, with an application to the exclusion process. Ann Appl Probab 62\u201387","DOI":"10.1214\/aoap\/1177005981"},{"issue":"4","key":"1836_CR8","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1284680.1284681","volume":"10","author":"D Chakrabarti","year":"2008","unstructured":"Chakrabarti D, Wang Y, Wang C, Leskovec J, Faloutsos C (2008) Epidemic thresholds in real networks. ACM TISSEC 10(4):1\u201326","journal-title":"ACM TISSEC"},{"key":"1836_CR9","doi-asserted-by":"crossref","unstructured":"Jin S, Zafarani R (2020) The spectral zoo of networks: embedding and visualizing networks with spectral moments. In: KDD, pp 1426\u20131434","DOI":"10.1145\/3394486.3403195"},{"key":"1836_CR10","doi-asserted-by":"crossref","unstructured":"Dong K, Benson AR, Bindel D (2019) Network density of states. In: KDD, pp 1152\u20131161","DOI":"10.1145\/3292500.3330891"},{"key":"1836_CR11","unstructured":"Verma S, Zhang Z-L (2017) Hunt for the unique, stable, sparse and fast feature learning on graphs. In: NIPS, pp 88\u201398"},{"key":"1836_CR12","doi-asserted-by":"crossref","unstructured":"Tsitsulin A, Mottin D, Karras P, Bronstein A, M\u00fcller E (2018) Netlsd: hearing the shape of a graph. In: KDD, pp 2347\u20132356","DOI":"10.1145\/3219819.3219991"},{"key":"1836_CR13","unstructured":"Narayanan A, Chandramohan M, Venkatesan R, Chen L, Liu Y, Jaiswal S (2017) graph2vec: learning distributed representations of graphs. arXiv:1707.05005"},{"key":"1836_CR14","first-page":"2539","volume":"12","author":"N Shervashidze","year":"2011","unstructured":"Shervashidze N, Schweitzer P, van Leeuwen EJ, Mehlhorn K, Borgwardt KM (2011) Weisfeiler\u2013Lehman graph kernels. J Mach Learn Res 12:2539\u20132561","journal-title":"J Mach Learn Res"},{"key":"1836_CR15","unstructured":"Kriege NM, Giscard P-L, Wilson RC (2016) On valid optimal assignment kernels and applications to graph classification. In: NIPS, pp 1615\u20131623"},{"key":"1836_CR16","unstructured":"Wu L, Zhang Z, Nehorai A, Zhao L, Xu F, Learning AS (2019) Sage: Scalable attributed graph embeddings for graph classification. In: ICLR workshop on representation learning on graphs and manifolds"},{"issue":"2","key":"1836_CR17","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1007\/s10994-015-5517-9","volume":"102","author":"M Neumann","year":"2016","unstructured":"Neumann M, Garnett R, Bauckhage C, Kersting K (2016) Propagation kernels: efficient graph kernels from propagated information. Mach Learn 102(2):209\u2013245","journal-title":"Mach Learn"},{"key":"1836_CR18","unstructured":"Zhang Z, Wang M, Xiang Y, Huang Y, Nehorai A (2018) RetGK: graph kernels based on return probabilities of random walks. In: NeurIPS, pp 3968\u20133978"},{"key":"1836_CR19","doi-asserted-by":"crossref","unstructured":"Huang L, Graven AJ, Bindel D (2021) Density of states graph kernels. In: SDM, pp 289\u2013297. SIAM","DOI":"10.1137\/1.9781611976700.33"},{"key":"1836_CR20","unstructured":"Kipf TN, Welling M (2017) Semi-supervised classification with graph convolutional networks. In: ICLR"},{"key":"1836_CR21","unstructured":"Xu K, Hu W, Leskovec J, Jegelka S (2019) How powerful are graph neural networks? In: ICLR, pp 1\u201317"},{"key":"1836_CR22","unstructured":"Defferrard M, Bresson X, Vandergheynst P (2016) Convolutional neural networks on graphs with fast localized spectral filtering. In: NIPS, pp 3837\u20133845"},{"issue":"1","key":"1836_CR23","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1109\/TSP.2018.2879624","volume":"67","author":"R Levie","year":"2019","unstructured":"Levie R, Monti F, Bresson X, Bronstein MM (2019) CayleyNets: graph convolutional neural networks with complex rational spectral filters. IEEE Trans Sign Process 67(1):97\u2013109","journal-title":"IEEE Trans Sign Process"},{"issue":"1","key":"1836_CR24","doi-asserted-by":"publisher","first-page":"6","DOI":"10.1007\/s41109-019-0195-3","volume":"5","author":"NM Kriege","year":"2020","unstructured":"Kriege NM, Johansson FD, Morris C (2020) A survey on graph kernels. Appl Netw Sci 5(1):6","journal-title":"Appl Netw Sci"},{"key":"1836_CR25","unstructured":"Balcilar M, Guillaume R, H\u00e9roux P, Ga\u00fcz\u00e8re B, Adam S, Honeine P (2021) Analyzing the expressive power of graph neural networks in a spectral perspective. In: ICLR"},{"key":"1836_CR26","unstructured":"Xu K, Hu W, Leskovec J, Jegelka S (2019) How powerful are graph neural networks? In: ICLR"},{"issue":"10","key":"1836_CR27","doi-asserted-by":"publisher","first-page":"2050","DOI":"10.1103\/PhysRevLett.86.2050","volume":"86","author":"F Wang","year":"2001","unstructured":"Wang F, Landau DP (2001) Efficient, multiple-range random walk algorithm to calculate the density of states. Phys Rev Lett 86(10):2050","journal-title":"Phys Rev Lett"},{"key":"1836_CR28","unstructured":"Li C, Sra S, Jegelka S (2016) Gaussian quadrature for matrix inverse forms with applications. In: International conference on machine learning. PMLR, pp 1766\u20131775"},{"issue":"106","key":"1836_CR29","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1090\/S0025-5718-69-99647-1","volume":"23","author":"GH Golub","year":"1969","unstructured":"Golub GH, Welsch JH (1969) Calculation of gauss quadrature rules. Math Comput 23(106):221\u2013230","journal-title":"Math Comput"},{"issue":"3","key":"1836_CR30","doi-asserted-by":"publisher","first-page":"687","DOI":"10.1007\/BF02510247","volume":"37","author":"GH Golub","year":"1997","unstructured":"Golub GH, Meurant G (1997) Matrices, moments and quadrature ii; how to compute the norm of the error in iterative methods. BIT Numer Math 37(3):687\u2013705","journal-title":"BIT Numer Math"},{"issue":"2","key":"1836_CR31","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.64.026704","volume":"64","author":"IJ Farkas","year":"2001","unstructured":"Farkas IJ, Der\u00e9nyi I, Barab\u00e1si A-L, Vicsek T (2001) Spectra of real-world graphs: beyond the semicircle law. Phys Rev E 64(2):026704","journal-title":"Phys Rev E"},{"issue":"2","key":"1836_CR32","doi-asserted-by":"publisher","first-page":"395","DOI":"10.3934\/nhm.2008.3.395","volume":"3","author":"A Banerjee","year":"2008","unstructured":"Banerjee A, Jost J (2008) Spectral plot properties: towards a qualitative classification of networks. Netw Heterog Media 3(2):395","journal-title":"Netw Heterog Media"},{"issue":"3","key":"1836_CR33","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.77.031102","volume":"77","author":"PN McGraw","year":"2008","unstructured":"McGraw PN, Menzinger M (2008) Laplacian spectra as a diagnostic tool for network structure and dynamics. Phys Rev E 77(3):031102","journal-title":"Phys Rev E"},{"key":"1836_CR34","unstructured":"Cucuringu M, Mahoney MW (2011) Localization on low-order eigenvectors of data matrices. arXiv:1109.1355"},{"issue":"2","key":"1836_CR35","doi-asserted-by":"publisher","first-page":"026123","DOI":"10.1103\/PhysRevE.80.026123","volume":"80","author":"M Mitrovi\u0107","year":"2009","unstructured":"Mitrovi\u0107 M, Tadi\u0107 B (2009) Spectral and dynamical properties in classes of sparse networks with mesoscopic inhomogeneities. Phys Rev E 80(2):026123","journal-title":"Phys Rev E"},{"key":"1836_CR36","unstructured":"Meurant G (2007) Matrices, moments, and quadrature. In: Milestones in matrix computation: the selected works of Gene H. Golub with commentaries, p 380"},{"key":"1836_CR37","doi-asserted-by":"crossref","unstructured":"Yanardag P, Vishwanathan S (2015) Deep graph kernels. In: Proceedings of the 21th ACM SIGKDD international conference on knowledge discovery and data mining, pp 1365\u20131374","DOI":"10.1145\/2783258.2783417"},{"issue":"suppl-1","key":"1836_CR38","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1093\/bioinformatics\/bti1007","volume":"21","author":"KM Borgwardt","year":"2005","unstructured":"Borgwardt KM, Ong CS, Sch\u00f6nauer S, Vishwanathan S, Smola AJ, Kriegel H-P (2005) Protein function prediction via graph kernels. Bioinformatics 21(suppl-1):47\u201356","journal-title":"Bioinformatics"},{"issue":"4","key":"1836_CR39","doi-asserted-by":"publisher","first-page":"771","DOI":"10.1016\/S0022-2836(03)00628-4","volume":"330","author":"PD Dobson","year":"2003","unstructured":"Dobson PD, Doig AJ (2003) Distinguishing enzyme structures from non-enzymes without alignments. J Mol Biol 330(4):771\u2013783","journal-title":"J Mol Biol"},{"key":"1836_CR40","doi-asserted-by":"crossref","unstructured":"Riesen K, Bunke H (2008) Iam graph database repository for graph based pattern recognition and machine learning. In: Joint IAPR international workshops on statistical techniques in pattern recognition (SPR) and structural and syntactic pattern recognition (SSPR), pp 287\u2013297. Springer","DOI":"10.1007\/978-3-540-89689-0_33"},{"issue":"16","key":"1836_CR41","doi-asserted-by":"publisher","first-page":"4165","DOI":"10.1016\/j.physa.2011.12.021","volume":"391","author":"AL Traud","year":"2012","unstructured":"Traud AL, Mucha PJ, Porter MA (2012) Social structure of facebook networks. Physica A 391(16):4165\u20134180","journal-title":"Physica A"},{"key":"1836_CR42","first-page":"10383","volume":"33","author":"C Zhengdao","year":"2020","unstructured":"Zhengdao C, Lei C, Soledad V, Bruna J (2020) Can graph neural networks count substructures? Adv Neural Inf Process Syst 33:10383\u201310395","journal-title":"Adv Neural Inf Process Syst"},{"key":"1836_CR43","unstructured":"Corso G, Cavalleri L, Beaini D, Li\u00f2 P, Veli\u010dkovi\u0107 P (2020) Principal neighbourhood aggregation for graph nets. Adv Neural Inf Process Syst 33:13260\u201313271"},{"key":"1836_CR44","unstructured":"Duvenaud DK, Maclaurin D, Aguilera-Iparraguirre J, G\u00f3mez-Bombarelli R, Hirzel T, Aspuru-Guzik A, Adams RP (2015) Convolutional networks on graphs for learning molecular fingerprints. Adv Neural inf Process Syst 28"},{"key":"1836_CR45","doi-asserted-by":"crossref","unstructured":"Fan W, Ma Y, Li Q, He Y, Zhao E, Tang J, Yin D (2019) Graph neural networks for social recommendation. In: The world wide web conference, pp 417\u2013426","DOI":"10.1145\/3308558.3313488"},{"key":"1836_CR46","doi-asserted-by":"crossref","unstructured":"Shi L, Zhang Y, Cheng J, Lu H (2019) Skeleton-based action recognition with directed graph neural networks. In: Proceedings of the IEEE\/CVF conference on computer vision and pattern recognition, pp 7912\u20137921","DOI":"10.1109\/CVPR.2019.00810"},{"key":"1836_CR47","unstructured":"Bouritsas G, Frasca F, Zafeiriou S, Bronstein MM (2020) Improving graph neural network expressivity via subgraph isomorphism counting. arXiv:2006.09252"},{"key":"1836_CR48","first-page":"25280","volume":"34","author":"P Barcel\u00f3","year":"2021","unstructured":"Barcel\u00f3 P, Geerts F, Reutter JL, Ryschkov M (2021) Graph neural networks with local graph parameters. Adv Neural Inf Process Syst 34:25280\u201325293","journal-title":"Adv Neural Inf Process Syst"},{"key":"1836_CR49","doi-asserted-by":"crossref","unstructured":"Sato R, Yamada M, Kashima H (2021) Random features strengthen graph neural networks. In: Proceedings of the 2021 SIAM international conference on data mining (SDM), pp 333\u2013341. SIAM","DOI":"10.1137\/1.9781611976700.38"},{"key":"1836_CR50","doi-asserted-by":"crossref","unstructured":"Abboud R, Ceylan \u0130\u0130, Grohe M, Lukasiewicz T (2021) The surprising power of graph neural networks with random node initialization. In: Proceedings of the thirtieth international joint conference on artifical intelligence (IJCAI)","DOI":"10.24963\/ijcai.2021\/291"},{"key":"1836_CR51","doi-asserted-by":"crossref","unstructured":"Babai L, Grigoryev DY, Mount DM (1982) Isomorphism of graphs with bounded eigenvalue multiplicity. In: Proceedings of the fourteenth annual ACM symposium on theory of computing, pp 310\u2013324","DOI":"10.1145\/800070.802206"}],"container-title":["Knowledge and Information Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10115-023-01836-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10115-023-01836-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10115-023-01836-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,4,7]],"date-time":"2023-04-07T05:07:19Z","timestamp":1680844039000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10115-023-01836-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,2,20]]},"references-count":51,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2023,6]]}},"alternative-id":["1836"],"URL":"https:\/\/doi.org\/10.1007\/s10115-023-01836-3","relation":{},"ISSN":["0219-1377","0219-3116"],"issn-type":[{"value":"0219-1377","type":"print"},{"value":"0219-3116","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,2,20]]},"assertion":[{"value":"27 January 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 January 2023","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 January 2023","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 February 2023","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}