{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,24]],"date-time":"2026-06-24T03:55:07Z","timestamp":1782273307983,"version":"3.54.5"},"reference-count":32,"publisher":"National Academy of Sciences","issue":"11","license":[{"start":{"date-parts":[[2020,3,2]],"date-time":"2020-03-02T00:00:00Z","timestamp":1583107200000},"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":["CCF-1740850"],"award-info":[{"award-number":["CCF-1740850"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1813165"],"award-info":[{"award-number":["CCF-1813165"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000183","name":"DOD | United States Army | RDECOM | Army Research Office","doi-asserted-by":"publisher","award":["W911NF1910294"],"award-info":[{"award-number":["W911NF1910294"]}],"id":[{"id":"10.13039\/100000183","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["www.pnas.org"],"crossmark-restriction":true},"short-container-title":["Proc. Natl. Acad. Sci. U.S.A."],"published-print":{"date-parts":[[2020,3,17]]},"abstract":"<jats:title>Significance<\/jats:title>\n                  <jats:p>Our main message is that the popular method of low-dimensional embeddings provably cannot capture important properties of real-world complex networks. A widely used algorithmic technique for modeling these networks is to construct a low-dimensional Euclidean embedding of the vertices of the network, where proximity of vertices is interpreted as the likelihood of an edge. Contrary to common wisdom, we argue that such graph embeddings do not capture salient properties of complex networks. We mathematically prove that low-dimensional embeddings cannot generate graphs with both low average degree and large clustering coefficients, which have been widely established to be empirically true for real-world networks. This establishes that popular low-dimensional embedding methods fail to capture significant structural aspects of real-world complex networks.<\/jats:p>","DOI":"10.1073\/pnas.1911030117","type":"journal-article","created":{"date-parts":[[2020,3,2]],"date-time":"2020-03-02T20:35:41Z","timestamp":1583181341000},"page":"5631-5637","update-policy":"https:\/\/doi.org\/10.1073\/pnas.cm10313","source":"Crossref","is-referenced-by-count":32,"title":["The impossibility of low-rank representations for triangle-rich complex networks"],"prefix":"10.1073","volume":"117","author":[{"given":"C.","family":"Seshadhri","sequence":"first","affiliation":[{"name":"Department of Computer Science, University of California, Santa Cruz, CA 95064;"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Aneesh","family":"Sharma","sequence":"additional","affiliation":[{"name":"Google, Mountain View, CA 94043;"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Andrew","family":"Stolman","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of California, Santa Cruz, CA 95064;"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ashish","family":"Goel","sequence":"additional","affiliation":[{"name":"Department of Management Science and Engineering, Stanford University, Stanford, CA 94305"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"341","published-online":{"date-parts":[[2020,3,2]]},"reference":[{"key":"e_1_3_3_1_2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511815478"},{"key":"e_1_3_3_2_2","doi-asserted-by":"publisher","DOI":"10.1137\/S003614450342480"},{"key":"e_1_3_3_3_2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511761942"},{"key":"e_1_3_3_4_2","doi-asserted-by":"publisher","DOI":"10.1126\/science.286.5439.509"},{"key":"e_1_3_3_5_2","doi-asserted-by":"publisher","DOI":"10.1038\/30918"},{"key":"e_1_3_3_6_2","doi-asserted-by":"publisher","DOI":"10.1145\/1132952.1132954"},{"key":"e_1_3_3_7_2","first-page":"1025","volume-title":"Neural Information Processing Systems, NIPS\u201917","author":"Hamilton W. L.","year":"2017","unstructured":"W. L. Hamilton, R. Ying, J. Leskovec, \u201cInductive representation learning on large graphs\u201d in Neural Information Processing Systems, NIPS\u201917, I. Guyon, U. von Luxburg, S. Bengio, H. M. Wallach, R. Fergus, S. V. N. Vishwanathan, Roman Garnett, Eds. (Curran Associates Inc., 2017), pp. 1025\u20131035."},{"key":"e_1_3_3_8_2","first-page":"37","volume-title":"Conference on World Wide Web","author":"Ahmed A.","year":"2013","unstructured":"A. Ahmed, N. Shervashidze, S. Narayanamurthy, V. Josifovski, A. J. Smola, \u201cDistributed large-scale natural graph factorization\u201d in Conference on World Wide Web, V. A. F. Almeida, H. Glaser, R. Baeza-Yates, S. B. Moon, Eds. (ACM, 2013), pp. 37\u201348."},{"key":"e_1_3_3_9_2","first-page":"1145","volume-title":"AAAI Conference on Artificial Intelligence","author":"Cao S.","year":"2016","unstructured":"S. Cao, W. Lu, Q. Xu, \u201cDeep neural networks for learning graph representations\u201d in AAAI Conference on Artificial Intelligence, D. Schuurmans, M. P. Wellman, Eds. (Association for the Advancement of Artificial Intelligence, 2016), pp. 1145\u20131152."},{"key":"e_1_3_3_10_2","first-page":"701","volume-title":"SIGGKDD Conference of Knowledge Discovery and Data Mining","author":"Perozzi B.","year":"2014","unstructured":"B. Perozzi, R. Al-Rfou, S. Skiena, \u201cDeepwalk: Online learning of social representations\u201d in SIGGKDD Conference of Knowledge Discovery and Data Mining, S. A. M., C. Perlich, J. Leskovec, W. Wang, R. Ghani, Eds. (Association for Computing Machinery, 2014), pp. 701\u2013710."},{"key":"e_1_3_3_11_2","first-page":"1067","volume-title":"Conference on World Wide Web","author":"Tang J.","year":"2015","unstructured":"J. Tang , \u201cLine: Large-scale information network embedding\u201d in Conference on World Wide Web, A. Gangemi, S. Leonardi, A. Panconesi, Eds. (ACM, 2015), pp. 1067\u20131077."},{"key":"e_1_3_3_12_2","first-page":"855","volume-title":"SIGGKDD Conference of Knowledge Discovery and Data Mining","author":"Grover A.","year":"2016","unstructured":"A. Grover, J. Leskovec, \u201cnode2vec: Scalable feature learning for networks\u201d in SIGGKDD Conference of Knowledge Discovery and Data Mining, B. Krishnapuram, M. Shah, A. J. Smola, C. C. Aggarwal, D. Shen, R. Rastogi, Eds. (Association for Computing Machinery, 2016), pp. 855\u2013864."},{"key":"e_1_3_3_13_2","unstructured":"@twittereng Embeddings@twitter. https:\/\/blog.twitter.com\/engineering\/en_us\/topics\/insights\/2018\/embeddingsattwitter.html."},{"key":"e_1_3_3_14_2","doi-asserted-by":"publisher","DOI":"10.14778\/1929861.1929864"},{"key":"e_1_3_3_15_2","first-page":"505","volume-title":"Conference on World Wide Web","author":"Gupta P.","year":"2013","unstructured":"P. Gupta , \u201cWTF: The Who to Follow service at Twitter\u201d in Conference on World Wide Web, A. Gangemi, S. Leonardi, A. Panconesi, Eds. (ACM, 2013), pp. 505\u2013514."},{"key":"e_1_3_3_16_2","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.1611275114"},{"key":"e_1_3_3_17_2","doi-asserted-by":"publisher","DOI":"10.1016\/0378-8733(83)90021-7"},{"key":"e_1_3_3_18_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-77004-6_11"},{"key":"e_1_3_3_19_2","first-page":"1","article-title":"Statistical inference on random dot product graphs: A survey","volume":"18","author":"Athreya A.","year":"2018","unstructured":"A. Athreya , Statistical inference on random dot product graphs: A survey. J. Mach. Learn. Res. 18, 1\u201392 (2018).","journal-title":"J. Mach. Learn. Res."},{"key":"e_1_3_3_20_2","first-page":"861","volume-title":"Conference on World Wide Web","author":"Sala A.","year":"2010","unstructured":"A. Sala , \u201cMeasurement-calibrated graph models for social network experiments\u201d in Conference on World Wide Web, M. Rappa, P. Jones, J. Freire, S. Chakrabarti, Eds. (ACM, 2010), pp. 861\u2013870."},{"key":"e_1_3_3_21_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.85.056109"},{"key":"e_1_3_3_22_2","first-page":"1712","volume-title":"Conference on Information and Knowledge Management","author":"Durak N.","year":"2012","unstructured":"N. Durak, A. Pinar, T. G. Kolda, C. Seshadhri, \u201cDegree relations of triangles in real-world networks and graph models\u201d in Conference on Information and Knowledge Management, X-w. Chen, G. Lebanon, H. Wang, M. J. Zaki, Eds. (CIKM) (ACM, 2012), pp. 1712\u20131716."},{"key":"e_1_3_3_23_2","doi-asserted-by":"publisher","DOI":"10.21136\/CMJ.1973.101168"},{"key":"e_1_3_3_24_2","first-page":"1","article-title":"Community detection and stochastic block models: Recent developments","volume":"18","author":"Abbe E.","year":"2018","unstructured":"E. Abbe, Community detection and stochastic block models: Recent developments. J. Mach. Learn. Res. 18, 1\u201386 (2018).","journal-title":"J. Mach. Learn. Res."},{"key":"e_1_3_3_25_2","doi-asserted-by":"publisher","DOI":"10.1198\/016214502388618906"},{"key":"e_1_3_3_26_2","unstructured":"K. Swanapoel The rank lemma. https:\/\/konradswanepoel.wordpress.com\/2014\/03\/04\/the-rank-lemma\/."},{"key":"e_1_3_3_27_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(03)00227-9"},{"key":"e_1_3_3_28_2","unstructured":"T. Tao A cheap version of the Kabatjanskii-Levenstein bound for almost orthogonal vectors. https:\/\/terrytao.wordpress.com\/2013\/07\/18\/a-cheap-version-of-the-kabatjanskii-levenstein-bound-for-almost-orthogonal-vectors\/."},{"key":"e_1_3_3_29_2","unstructured":"J. Leskovec Stanford Network Analysis Project. http:\/\/snap.stanford.edu\/. Accessed 1 November 2019."},{"key":"e_1_3_3_30_2","unstructured":"STRING Consortium String database. http:\/\/version10.string-db.org\/. Accessed 1 November 2019."},{"key":"e_1_3_3_31_2","unstructured":"J. Tang J. Zhang L. Yao J. Li L. Zhang Z. Su Citation network dataset. https:\/\/aminer.org\/citation. Accessed 1 November 2019."},{"key":"e_1_3_3_32_2","doi-asserted-by":"publisher","DOI":"10.1145\/1401890.1402008"}],"container-title":["Proceedings of the National Academy of Sciences"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.pnas.org\/syndication\/doi\/10.1073\/pnas.1911030117","content-type":"unspecified","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/pnas.org\/doi\/pdf\/10.1073\/pnas.1911030117","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,4,13]],"date-time":"2022-04-13T04:55:38Z","timestamp":1649825738000},"score":1,"resource":{"primary":{"URL":"https:\/\/pnas.org\/doi\/full\/10.1073\/pnas.1911030117"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,3,2]]},"references-count":32,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2020,3,17]]}},"alternative-id":["10.1073\/pnas.1911030117"],"URL":"https:\/\/doi.org\/10.1073\/pnas.1911030117","relation":{},"ISSN":["0027-8424","1091-6490"],"issn-type":[{"value":"0027-8424","type":"print"},{"value":"1091-6490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,3,2]]},"assertion":[{"value":"2020-03-02","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}