{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:10:10Z","timestamp":1750201810777,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":45,"publisher":"ACM","license":[{"start":{"date-parts":[[2020,4,20]],"date-time":"2020-04-20T00:00:00Z","timestamp":1587340800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2020,4,20]]},"DOI":"10.1145\/3366423.3380026","type":"proceedings-article","created":{"date-parts":[[2020,5,4]],"date-time":"2020-05-04T08:11:44Z","timestamp":1588579904000},"page":"2697-2703","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":12,"title":["Just SLaQ When You Approximate: Accurate Spectral Distances for Web-Scale Graphs"],"prefix":"10.1145","author":[{"given":"Anton","family":"Tsitsulin","sequence":"first","affiliation":[{"name":"University of Bonn"}]},{"given":"Marina","family":"Munkhoeva","sequence":"additional","affiliation":[{"name":"Skoltech"}]},{"given":"Bryan","family":"Perozzi","sequence":"additional","affiliation":[{"name":"Google Research"}]}],"member":"320","published-online":{"date-parts":[[2020,4,20]]},"reference":[{"key":"e_1_3_2_1_1_1","unstructured":"Ryan\u00a0P Adams Jeffrey Pennington Matthew\u00a0J Johnson Jamie Smith Yaniv Ovadia Brian Patton and James Saunderson. 2018. Estimating the spectral density of large implicit matrices. arXiv preprint arXiv:1802.03451(2018).  Ryan\u00a0P Adams Jeffrey Pennington Matthew\u00a0J Johnson Jamie Smith Yaniv Ovadia Brian Patton and James Saunderson. 2018. Estimating the spectral density of large implicit matrices. arXiv preprint arXiv:1802.03451(2018)."},{"volume-title":"DDGK: Learning Graph Representations for Deep Divergence Graph Kernels. In The World Wide Web Conference.","year":"2019","author":"Al-Rfou Rami","key":"e_1_3_2_1_2_1"},{"volume-title":"LAPACK Users","author":"Anderson Edward","key":"e_1_3_2_1_3_1"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"crossref","unstructured":"Haim Avron and Sivan Toledo. 2011. Randomized algorithms for estimating the trace of an implicit symmetric positive semi-definite matrix. Journal of the ACM (JACM)(2011).  Haim Avron and Sivan Toledo. 2011. Randomized algorithms for estimating the trace of an implicit symmetric positive semi-definite matrix. Journal of the ACM (JACM)(2011).","DOI":"10.1145\/1944345.1944349"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"crossref","unstructured":"Samuel\u00a0L Braunstein Sibasish Ghosh and Simone Severini. 2006. The Laplacian of a graph as a density matrix: a basic combinatorial approach to separability of mixed states. Annals of Combinatorics(2006) 291\u2013317.  Samuel\u00a0L Braunstein Sibasish Ghosh and Simone Severini. 2006. The Laplacian of a graph as a density matrix: a basic combinatorial approach to separability of mixed states. Annals of Combinatorics(2006) 291\u2013317.","DOI":"10.1007\/s00026-006-0289-3"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"crossref","unstructured":"Thomas B\u00fchler and Matthias Hein. 2009. Spectral clustering based on the graph p-Laplacian. In ICML. 81\u201388.  Thomas B\u00fchler and Matthias Hein. 2009. Spectral clustering based on the graph p-Laplacian. In ICML. 81\u201388.","DOI":"10.1145\/1553374.1553385"},{"volume-title":"RLGM workshop.","year":"2019","author":"Cai Chen","key":"e_1_3_2_1_7_1"},{"key":"e_1_3_2_1_8_1","unstructured":"Pin-Yu Chen Lingfei Wu Sijia Liu and Indika Rajapakse. 2019. Fast Incremental von Neumann Graph Entropy Computation: Theory Algorithm and Applications. In ICML.  Pin-Yu Chen Lingfei Wu Sijia Liu and Indika Rajapakse. 2019. Fast Incremental von Neumann Graph Entropy Computation: Theory Algorithm and Applications. In ICML."},{"key":"e_1_3_2_1_9_1","unstructured":"Fan\u00a0RK Chung. 1997. Spectral graph theory. Number\u00a092. American Mathematical Soc.  Fan\u00a0RK Chung. 1997. Spectral graph theory. Number\u00a092. American Mathematical Soc."},{"volume-title":"Overview of the TREC 2009 web track. Technical Report. DTIC Document.","year":"2009","author":"Clarke L","key":"e_1_3_2_1_10_1"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"crossref","unstructured":"David Cohen-Steiner Weihao Kong Christian Sohler and Gregory Valiant. 2018. Approximating the Spectrum of a Graph. In KDD.  David Cohen-Steiner Weihao Kong Christian Sohler and Gregory Valiant. 2018. Approximating the Spectrum of a Graph. In KDD.","DOI":"10.1145\/3219819.3220119"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"crossref","unstructured":"Paul\u00a0D Dobson and Andrew\u00a0J Doig. 2003. Distinguishing enzyme structures from non-enzymes without alignments. Journal of molecular biology(2003) 771\u2013783.  Paul\u00a0D Dobson and Andrew\u00a0J Doig. 2003. Distinguishing enzyme structures from non-enzymes without alignments. Journal of molecular biology(2003) 771\u2013783.","DOI":"10.1016\/S0022-2836(03)00628-4"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"crossref","unstructured":"Kun Dong Austin\u00a0R. Benson and David Bindel. 2019. Network Density of States. In KDD.  Kun Dong Austin\u00a0R. Benson and David Bindel. 2019. Network Density of States. In KDD.","DOI":"10.1145\/3292500.3330891"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"crossref","unstructured":"Ernesto Estrada. 2000. Characterization of 3D molecular structure. Chemical Physics Letters(2000) 713\u2013718.  Ernesto Estrada. 2000. Characterization of 3D molecular structure. Chemical Physics Letters(2000) 713\u2013718.","DOI":"10.1016\/S0009-2614(00)00158-5"},{"key":"e_1_3_2_1_15_1","first-page":"749","article-title":"\u00dcber die abgrenzung der eigenwerte einer matrix","volume":"6","author":"Gershgorin Semyon\u00a0Aranovich","year":"1931","journal-title":"Izv. Akad. Nauk."},{"volume-title":"moments and quadrature with applications","author":"Golub H","key":"e_1_3_2_1_16_1"},{"volume-title":"Calculation of Gauss quadrature rules. Mathematics of computation 23, 106","year":"1969","author":"Golub H","key":"e_1_3_2_1_17_1"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"crossref","unstructured":"Ivan Gutman and Bo Zhou. 2006. Laplacian energy of a graph. Linear Algebra and its applications(2006) 29\u201337.  Ivan Gutman and Bo Zhou. 2006. Laplacian energy of a graph. Linear Algebra and its applications(2006) 29\u201337.","DOI":"10.1016\/j.laa.2005.09.008"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.patrec.2012.03.016"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3269206.3271788"},{"volume-title":"On Krylov subspace approximations to the matrix exponential operator","series-title":"SIAM J. Numer. Anal.(1997)","author":"Hochbruck Marlis","key":"e_1_3_2_1_21_1"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1080\/03610918908812806"},{"key":"e_1_3_2_1_23_1","unstructured":"Kristian Kersting Nils\u00a0M. Kriege Christopher Morris Petra Mutzel and Marion Neumann. 2016. Benchmark Data Sets for Graph Kernels. (2016). http:\/\/graphkernels.cs.tu-dortmund.de  Kristian Kersting Nils\u00a0M. Kriege Christopher Morris Petra Mutzel and Marion Neumann. 2016. Benchmark Data Sets for Graph Kernels. (2016). http:\/\/graphkernels.cs.tu-dortmund.de"},{"volume-title":"DELTACON: A Principled Massive-Graph Similarity Function. In SDM.","year":"2013","author":"Koutra Danai","key":"e_1_3_2_1_24_1"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"crossref","unstructured":"Jure Leskovec Jon Kleinberg and Christos Faloutsos. 2005. Graphs over time: densification laws shrinking diameters and possible explanations. In KDD.  Jure Leskovec Jon Kleinberg and Christos Faloutsos. 2005. Graphs over time: densification laws shrinking diameters and possible explanations. In KDD.","DOI":"10.1145\/1081870.1081893"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.acha.2010.09.005"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"crossref","unstructured":"Giorgia Minello Luca Rossi and Andrea Torsello. 2018. On the von Neumann entropy of graphs. Journal of Complex Networks(2018).  Giorgia Minello Luca Rossi and Andrea Torsello. 2018. On the von Neumann entropy of graphs. Journal of Complex Networks(2018).","DOI":"10.1093\/comnet\/cny028"},{"key":"e_1_3_2_1_28_1","series-title":"SIAM review","volume-title":"Nineteen dubious ways to compute the exponential of a matrix, twenty-five years later","author":"Moler Cleve","year":"2003"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"crossref","unstructured":"Maria\u00a0CV Nascimento and Andre\u00a0CPLF De\u00a0Carvalho. 2011. Spectral methods for graph clustering\u2013a survey. European Journal of Operational Research(2011) 221\u2013231.  Maria\u00a0CV Nascimento and Andre\u00a0CPLF De\u00a0Carvalho. 2011. Spectral methods for graph clustering\u2013a survey. European Journal of Operational Research(2011) 221\u2013231.","DOI":"10.1016\/j.ejor.2010.08.012"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"crossref","unstructured":"Huda Nassar Nate Veldt Shahin Mohammadi Ananth Grama and David\u00a0F Gleich. 2018. Low rank spectral network alignment. In WWW. 619\u2013628.  Huda Nassar Nate Veldt Shahin Mohammadi Ananth Grama and David\u00a0F Gleich. 2018. Low rank spectral network alignment. In WWW. 619\u2013628.","DOI":"10.1145\/3178876.3186128"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"crossref","unstructured":"Ryan\u00a0A. Rossi and Nesreen\u00a0K. Ahmed. 2015. The Network Data Repository with Interactive Graph Analytics and Visualization. In AAAI. http:\/\/networkrepository.com  Ryan\u00a0A. Rossi and Nesreen\u00a0K. Ahmed. 2015. The Network Data Repository with Interactive Graph Analytics and Visualization. In AAAI. http:\/\/networkrepository.com","DOI":"10.1609\/aaai.v29i1.9277"},{"volume-title":"GEM workshop.","year":"2019","author":"Schulz Till","key":"e_1_3_2_1_32_1"},{"volume-title":"Kurt Mehlhorn, and Karsten\u00a0M Borgwardt.","year":"2011","author":"Shervashidze Nino","key":"e_1_3_2_1_33_1"},{"volume-title":"Normalized cuts and image segmentation. PAMI","year":"2000","author":"Shi Jianbo","key":"e_1_3_2_1_34_1"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"crossref","unstructured":"David\u00a0E Simmons Justin\u00a0P Coon and Animesh Datta. 2018. The von Neumann Theil index: characterizing graph centralization using the von Neumann index. Journal of Complex Networks(2018).  David\u00a0E Simmons Justin\u00a0P Coon and Animesh Datta. 2018. The von Neumann Theil index: characterizing graph centralization using the von Neumann index. Journal of Complex Networks(2018).","DOI":"10.1093\/comnet\/cnx061"},{"volume-title":"Spectral Graph Complexity. In Companion Proceedings of The 2019 World Wide Web Conference(WWW \u201919)","year":"2019","author":"Tsitsulin Anton","key":"e_1_3_2_1_36_1"},{"key":"e_1_3_2_1_37_1","unstructured":"Anton Tsitsulin Davide Mottin Panagiotis Karras Alexander\u00a0M. Bronstein and Emmanuel M\u00fcller. 2018. NetLSD: Hearing the Shape of a Graph. In KDD.  Anton Tsitsulin Davide Mottin Panagiotis Karras Alexander\u00a0M. Bronstein and Emmanuel M\u00fcller. 2018. NetLSD: Hearing the Shape of a Graph. In KDD."},{"key":"e_1_3_2_1_38_1","unstructured":"Anton Tsitsulin Marina Munkhoeva Davide Mottin Panagiotis Karras Alex Bronstein Ivan Oseledets and Emmanuel M\u00fcller. 2020. The Shape of Data: Intrinsic Distance for Data Distributions. In ICLR.  Anton Tsitsulin Marina Munkhoeva Davide Mottin Panagiotis Karras Alex Bronstein Ivan Oseledets and Emmanuel M\u00fcller. 2020. The Shape of Data: Intrinsic Distance for Data Distributions. In ICLR."},{"volume-title":"Fast Estimation of tr(f(A)) via Stochastic Lanczos Quadrature","series-title":"SIAM J. Matrix Anal. Appl.(2017)","author":"Ubaru Shashanka","key":"e_1_3_2_1_39_1"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"crossref","unstructured":"Amir Vaxman Mirela Ben-Chen and Craig Gotsman. 2010. A multi-resolution approach to heat kernels on discrete surfaces. In TOG.  Amir Vaxman Mirela Ben-Chen and Craig Gotsman. 2010. A multi-resolution approach to heat kernels on discrete surfaces. In TOG.","DOI":"10.1145\/1833349.1778858"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"crossref","unstructured":"Ulrike Von\u00a0Luxburg. 2007. A tutorial on spectral clustering. Statistics and computing(2007) 395\u2013416.  Ulrike Von\u00a0Luxburg. 2007. A tutorial on spectral clustering. Statistics and computing(2007) 395\u2013416.","DOI":"10.1007\/s11222-007-9033-z"},{"volume-title":"Mathematische grundlagen der quantenmechanik","author":"Von\u00a0Neumann John","key":"e_1_3_2_1_42_1"},{"key":"e_1_3_2_1_43_1","unstructured":"Herbert\u00a0S Wilf. 1962. Mathematics for the physical sciences. (1962).  Herbert\u00a0S Wilf. 1962. Mathematics for the physical sciences. (1962)."},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"crossref","unstructured":"Pinar Yanardag and SVN Vishwanathan. 2015. Deep graph kernels. In KDD.  Pinar Yanardag and SVN Vishwanathan. 2015. Deep graph kernels. In KDD.","DOI":"10.1145\/2783258.2783417"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"crossref","unstructured":"Jaewon Yang and Jure Leskovec. 2012. Defining and Evaluating Network Communities Based on Ground-Truth. In ICDM.  Jaewon Yang and Jure Leskovec. 2012. Defining and Evaluating Network Communities Based on Ground-Truth. In ICDM.","DOI":"10.1109\/ICDM.2012.138"}],"event":{"name":"WWW '20: The Web Conference 2020","sponsor":["SIGWEB ACM Special Interest Group on Hypertext, Hypermedia, and Web"],"location":"Taipei Taiwan","acronym":"WWW '20"},"container-title":["Proceedings of The Web Conference 2020"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3366423.3380026","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3366423.3380026","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:33:16Z","timestamp":1750199596000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3366423.3380026"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,4,20]]},"references-count":45,"alternative-id":["10.1145\/3366423.3380026","10.1145\/3366423"],"URL":"https:\/\/doi.org\/10.1145\/3366423.3380026","relation":{},"subject":[],"published":{"date-parts":[[2020,4,20]]},"assertion":[{"value":"2020-04-20","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}