{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T11:47:55Z","timestamp":1753876075096,"version":"3.41.2"},"reference-count":42,"publisher":"Oxford University Press (OUP)","issue":"5","license":[{"start":{"date-parts":[[2019,11,28]],"date-time":"2019-11-28T00:00:00Z","timestamp":1574899200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/journals\/pages\/open_access\/funder_policies\/chorus\/standard_publication_model"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2021,2,27]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Graph embedding is the transformation of vertices of a graph into set of vectors. A good embedding should capture the graph topology, vertex-to-vertex relationship and other relevant information about the graph, its subgraphs and vertices. If these objectives are achieved, an embedding is a meaningful, understandable and compressed representations of a network. Finally, vector operations are simpler and faster than comparable operations on graphs. The main challenge is that one needs to make sure that embeddings well describe the properties of the graphs. In particular, a decision has to be made on the embedding dimensionality which highly impacts the quality of an embedding. As a result, selecting the best embedding is a challenging task and very often requires domain experts. In this article, we propose a \u2018divergence score\u2019 that can be assigned to embeddings to help distinguish good ones from bad ones. This general framework provides a tool for an unsupervised graph embedding comparison. In order to achieve it, we needed to generalize the well-known Chung-Lu model to incorporate geometry which is an interesting result in its own right. In order to test our framework, we did a number of experiments with synthetic networks as well as real-world networks, and various embedding algorithms.<\/jats:p>","DOI":"10.1093\/comnet\/cnz043","type":"journal-article","created":{"date-parts":[[2019,10,25]],"date-time":"2019-10-25T19:24:20Z","timestamp":1572031460000},"source":"Crossref","is-referenced-by-count":9,"title":["An unsupervised framework for comparing graph embeddings"],"prefix":"10.1093","volume":"8","author":[{"given":"Bogumi\u0142","family":"Kami\u0144ski","sequence":"first","affiliation":[{"name":"Decision Analysis and Support Unit, SGH Warsaw School of Economics, Warsaw, Poland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pawe\u0142","family":"Pra\u0142at","sequence":"additional","affiliation":[{"name":"Department of Mathematics, Ryerson University, Toronto, ON, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Fran\u00e7ois","family":"Th\u00e9berge","sequence":"additional","affiliation":[{"name":"Tutte Institute for Mathematics and Computing, Ottawa, ON, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2019,11,28]]},"reference":[{"key":"2021030106021640800_B1","doi-asserted-by":"crossref","DOI":"10.1093\/acprof:oso\/9780199206650.001.0001","volume-title":"Networks: An Introduction","author":"Newman.","year":"2010"},{"key":"2021030106021640800_B2","doi-asserted-by":"crossref","first-page":"56001","DOI":"10.1209\/0295-5075\/111\/56001","article-title":"Interdisciplinary and physics challenges of network theory","volume":"111","author":"Bianconi,","year":"2015","journal-title":"Europhys. Lett."},{"key":"2021030106021640800_B3","doi-asserted-by":"crossref","first-page":"1090","DOI":"10.1198\/016214502388618906","article-title":"Latent space approaches to social network analysis","volume":"97","author":"Hoff,","year":"2002","journal-title":"J. Am. Stat. Assoc."},{"key":"2021030106021640800_B4","first-page":"1","article-title":"Clustering means geometry in networks","volume":"208302","author":"Krioukov,","year":"2016","journal-title":"Phys. Rev. Lett."},{"key":"2021030106021640800_B5","doi-asserted-by":"crossref","first-page":"9421","DOI":"10.1038\/srep09421","article-title":"Emergence of soft communities from geometric preferential attachment","volume":"5","author":"Zuev,","year":"2015","journal-title":"Sci. Rep."},{"key":"2021030106021640800_B6","doi-asserted-by":"crossref","first-page":"247","DOI":"10.1140\/epjb\/e2006-00046-8","article-title":"The spatial structure of networks","volume":"49","author":"Gastner,","year":"2006","journal-title":"Eur. Phys. J. B."},{"key":"2021030106021640800_B7","doi-asserted-by":"crossref","first-page":"7663","DOI":"10.1073\/pnas.1018962108","article-title":"Uncovering space-independent communities in spatial networks","volume":"108","author":"Expert,","year":"2011","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"2021030106021640800_B8","first-page":"201","volume-title":"CiE 2010","author":"Janssen,","year":"2010"},{"key":"2021030106021640800_B9","doi-asserted-by":"crossref","first-page":"1093","DOI":"10.1093\/bioinformatics\/btn079","article-title":"Fitting a geometric graph to a protein-protein interaction network","volume":"24","author":"Higham,","year":"2008","journal-title":"Bioinformatics"},{"volume-title":"Complex Networks and Their Applications VII. COMPLEX NETWORKS 2018","year":"2019","author":"Poulin,","key":"2021030106021640800_B10"},{"key":"2021030106021640800_B11","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1109\/18.61115","article-title":"Divergence measures based on the Shannon entropy","volume":"37","author":"Lin,","year":"1991","journal-title":"IEEE Trans. Inf. Theory"},{"key":"2021030106021640800_B12","doi-asserted-by":"crossref","first-page":"1617","DOI":"10.1109\/49.12889","article-title":"Routing of multipoint connections","volume":"6","author":"Waxman,","year":"1988","journal-title":"IEEE J. Select. Areas Commun."},{"key":"2021030106021640800_B13","doi-asserted-by":"crossref","DOI":"10.1209\/0295-5075\/82\/48005","article-title":"Structural properties of spatially embedded networks","volume":"82","author":"Kosmidis,","year":"2008","journal-title":"Europhys. Lett."},{"key":"2021030106021640800_B14","doi-asserted-by":"crossref","DOI":"10.1103\/PhysRevE.76.056115","article-title":"Spatially embedded random networks","volume":"76","author":"Barnett,","year":"2007","journal-title":"Phys. Rev. E"},{"key":"2021030106021640800_B15","doi-asserted-by":"crossref","first-page":"036106","DOI":"10.1103\/PhysRevE.82.036106","article-title":"Hyperbolic geometry of complex networks","volume":"82","author":"Krioukov,","year":"2010","journal-title":"Phys. Rev. E"},{"key":"2021030106021640800_B16","doi-asserted-by":"crossref","first-page":"175","DOI":"10.1080\/15427951.2008.10129305","article-title":"A spatial web graph model with local influence regions","volume":"5","author":"Aiello,","year":"2009","journal-title":"Internet Math."},{"key":"2021030106021640800_B17","doi-asserted-by":"crossref","first-page":"817","DOI":"10.1214\/12-AIHP480","article-title":"Scale-free percolation","volume":"49","author":"Deijfen,","year":"2013","journal-title":"Annales de l\u2019Institut Henri Poincare, Probabilites et Statistiques"},{"key":"2021030106021640800_B18","first-page":"1","article-title":"Sampling geometric inhomogeneous random graphs in linear time","volume":"20","author":"Bringmann,","year":"2017","journal-title":"ESA"},{"key":"2021030106021640800_B19","doi-asserted-by":"crossref","DOI":"10.1090\/cbms\/107","author":"Chung,","year":"2006","journal-title":"Complex Graphs and Networks"},{"key":"2021030106021640800_B20","doi-asserted-by":"crossref","DOI":"10.1103\/PhysRevE.85.056109","article-title":"Community structure and scale-free collections of Erd\u00f6s\u2013R\u00e9nyi graphs","volume":"85","author":"Seshadhri,","year":"2012","journal-title":"Phys. Rev. E."},{"key":"2021030106021640800_B21","doi-asserted-by":"crossref","first-page":"C424","DOI":"10.1137\/130914218","article-title":"A scalable generative graph model with community structure","volume":"36","author":"Kolda,","year":"2014","journal-title":"SIAM J. Sci. Comput."},{"key":"2021030106021640800_B22","doi-asserted-by":"crossref","DOI":"10.2172\/1239211","article-title":"An in-depth analysis of the Chung-Lu model","volume-title":"Lawrence Livermore Technical Report LLNL-TR-678729","author":"Winlaw,","year":"2015"},{"key":"2021030106021640800_B23","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1239\/aap\/1143936140","article-title":"On a conditionally Poissonian graph process","volume":"38","author":"Norros,","year":"2006","journal-title":"Adv. Appl. Prob."},{"key":"2021030106021640800_B24","article-title":"Community detection in complex networks via clique conductance","volume":"8","author":"Lu,","year":"2018","journal-title":"Nat. Sci. Rep."},{"key":"2021030106021640800_B25","doi-asserted-by":"crossref","DOI":"10.1103\/PhysRevE.78.046110","article-title":"Benchmark graphs for testing community detection algorithms","volume":"78","author":"Lancichinetti,","year":"2008","journal-title":"Phys. Rev. E"},{"key":"2021030106021640800_B26","doi-asserted-by":"crossref","first-page":"452","DOI":"10.1086\/jar.33.4.3629752","article-title":"An information flow model for conflict and fission in small groups","volume":"33","author":"Zachary,","year":"1977","journal-title":"J. Anthropol. Res."},{"key":"2021030106021640800_B27","doi-asserted-by":"crossref","first-page":"7821","DOI":"10.1073\/pnas.122653799","article-title":"Community structure in social and biological networks","volume":"99","author":"Girvan,","year":"2002","journal-title":"Proc. Natl. Acad. Sci."},{"volume-title":"SNAP Datasets: Stanford Large Network Dataset Collection","author":"Leskovec,","key":"2021030106021640800_B28"},{"volume-title":"Network Science","year":"2016","author":"Barabasi,","key":"2021030106021640800_B29"},{"key":"2021030106021640800_B30","doi-asserted-by":"crossref","first-page":"855","DOI":"10.1145\/2939672.2939754","article-title":"node2vec: scalable feature learning for networks","volume-title":"KDD.","author":"Grover,","year":"2016"},{"key":"2021030106021640800_B31","first-page":"539","article-title":"VERSE: Versatile Graph Embeddings from Similarity Measures","volume-title":"Proceedings of the 2018 World Wide Web Conference (WWW\u201918)","author":"Tsitsulin,","year":"2018"},{"key":"2021030106021640800_B32","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1007\/978-3-319-67810-8_3","volume-title":"International Workshop on Algorithms and Models for the Web-Graph","author":"Avrachenkov,","year":"2017"},{"key":"2021030106021640800_B33","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1016\/j.ejc.2018.02.002","article-title":"Similarities on graphs: Kernels versus proximity measures","volume":"80","author":"Avrachenkov,","year":"2019","journal-title":"Eur. J. Combin."},{"key":"2021030106021640800_B34","doi-asserted-by":"crossref","first-page":"811","DOI":"10.2307\/1968466","article-title":"Metric spaces and completely monotone functions","volume":"39","author":"Schoenberg,","year":"1938","journal-title":"Ann. Math."},{"key":"2021030106021640800_B35","doi-asserted-by":"crossref","first-page":"522","DOI":"10.1090\/S0002-9947-1938-1501980-0","article-title":"Metric spaces and positive definite functions","volume":"44","author":"Schoenberg,","year":"1938","journal-title":"Am. Math. Soc."},{"key":"2021030106021640800_B36","doi-asserted-by":"crossref","first-page":"1067","DOI":"10.1145\/2736277.2741093","article-title":"Line: large-scale information network embedding","volume-title":"Proceedings 24th International Conference on World Wide Web.","author":"Tang,","year":"2015"},{"article-title":"UMAP: uniform manifold approximation and projection for dimension reduction","year":"2018","author":"McInnes","key":"2021030106021640800_B37"},{"key":"2021030106021640800_B38","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/s41109-019-0162-z","article-title":"Ensemble clustering for graphs: comparison and applications","volume":"4","author":"Poulin,","year":"2019","journal-title":"Appl. Netw. Sci."},{"key":"2021030106021640800_B39","doi-asserted-by":"crossref","DOI":"10.1088\/1742-5468\/2008\/10\/P10008","article-title":"Fast unfolding of communities in large networks","volume":"2008","author":"Blondel,","year":"2008","journal-title":"J. Stat. Mech."},{"key":"2021030106021640800_B40","doi-asserted-by":"crossref","DOI":"10.1073\/pnas.0706851105","article-title":"Maps of random walks on complex networks reveal community structure","volume":"105","author":"Rosvall,","year":"2008","journal-title":"Proc. Natl. Acad. Sci."},{"key":"2021030106021640800_B41","article-title":"Clustering via hypergraph modularity","volume":"14","author":"Kami\u0144ski,","journal-title":"PLoS One"},{"volume-title":"Proceedings of the 16th Workshop on Algorithms and Models for the Web Graph (WAW 2019)","year":"2019","author":"Antelmi,","key":"2021030106021640800_B42"}],"container-title":["Journal of Complex Networks"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/academic.oup.com\/comnet\/article-pdf\/8\/5\/cnz043\/36409024\/cnz043.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"http:\/\/academic.oup.com\/comnet\/article-pdf\/8\/5\/cnz043\/36409024\/cnz043.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,3,1]],"date-time":"2021-03-01T06:02:45Z","timestamp":1614578565000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/comnet\/article\/doi\/10.1093\/comnet\/cnz043\/5645186"}},"subtitle":[],"editor":[{"given":"Ernesto","family":"Estrada","sequence":"additional","affiliation":[],"role":[{"role":"editor","vocabulary":"crossref"}]}],"short-title":[],"issued":{"date-parts":[[2019,11,28]]},"references-count":42,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2021,2,27]]}},"URL":"https:\/\/doi.org\/10.1093\/comnet\/cnz043","relation":{},"ISSN":["2051-1329"],"issn-type":[{"type":"electronic","value":"2051-1329"}],"subject":[],"published-other":{"date-parts":[[2020,10,1]]},"published":{"date-parts":[[2019,11,28]]},"article-number":"cnz043"}}