{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,2]],"date-time":"2026-05-02T14:55:34Z","timestamp":1777733734533,"version":"3.51.4"},"reference-count":48,"publisher":"Association for Computing Machinery (ACM)","issue":"6","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2021,2]]},"abstract":"<jats:p>\n            Low-dimensional representations, or\n            <jats:italic>embeddings<\/jats:italic>\n            , of a graph's nodes facilitate several practical data science and data engineering tasks. As such embeddings rely, explicitly or implicitly, on a similarity measure among nodes, they require the computation of a quadratic similarity matrix, inducing a tradeoff between space complexity and embedding quality. To date, no graph embedding work combines (i) linear space complexity, (ii) a nonlinear transform as its basis, and (iii) nontrivial quality guarantees. In this paper we introduce FREDE (\n            <jats:italic>FREquent Directions Embedding<\/jats:italic>\n            ), a graph embedding based on matrix sketching that combines those three desiderata. Starting out from the observation that embedding methods aim to preserve the covariance among the rows of a similarity matrix, FREDE iteratively improves on quality while individually processing rows of a nonlinearly transformed PPR similarity matrix derived from a state-of-the-art graph embedding method and provides,\n            <jats:italic>at any iteration<\/jats:italic>\n            , column-covariance approximation guarantees in due course almost indistinguishable from those of the optimal approximation by SVD. Our experimental evaluation on variably sized networks shows that FREDE performs almost as well as SVD and competitively against state-of-the-art embedding methods in diverse data science tasks, even when it is based on as little as 10% of node similarities.\n          <\/jats:p>","DOI":"10.14778\/3447689.3447713","type":"journal-article","created":{"date-parts":[[2021,4,12]],"date-time":"2021-04-12T16:20:06Z","timestamp":1618244406000},"page":"1102-1110","source":"Crossref","is-referenced-by-count":32,"title":["FREDE"],"prefix":"10.14778","volume":"14","author":[{"given":"Anton","family":"Tsitsulin","sequence":"first","affiliation":[{"name":"University of Bonn"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marina","family":"Munkhoeva","sequence":"additional","affiliation":[{"name":"Skoltech"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Davide","family":"Mottin","sequence":"additional","affiliation":[{"name":"Aarhus University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Panagiotis","family":"Karras","sequence":"additional","affiliation":[{"name":"Aarhus University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ivan","family":"Oseledets","sequence":"additional","affiliation":[{"name":"Skoltech"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Emmanuel","family":"M\u00fcller","sequence":"additional","affiliation":[{"name":"TU Dortmund"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2021,4,12]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Microsoft Academic Graph - KDD cup","year":"2016","unstructured":"2016. Microsoft Academic Graph - KDD cup 2016 . https:\/\/kddcup2016.azurewebsites.net\/Data. 2016. Microsoft Academic Graph - KDD cup 2016. https:\/\/kddcup2016.azurewebsites.net\/Data."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2500128"},{"key":"e_1_2_1_3_1","volume-title":"John Lee, Theodore Willke, Rong Zhou, Xiangnan Kong, and Hoda Eldardiry.","author":"Ahmed Nesreen","year":"2020","unstructured":"Nesreen Ahmed , Ryan Anthony Rossi , John Lee, Theodore Willke, Rong Zhou, Xiangnan Kong, and Hoda Eldardiry. 2020 . Role-based Graph Embeddings. TKDE ( 2020). Nesreen Ahmed, Ryan Anthony Rossi, John Lee, Theodore Willke, Rong Zhou, Xiangnan Kong, and Hoda Eldardiry. 2020. Role-based Graph Embeddings. TKDE (2020)."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.14778\/1929861.1929864"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/3336191.3371800"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.21"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.5555\/1496770.1496875"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2806416.2806512"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488620"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/1390681.1442794"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/15M1009718"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2939672.2939754"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.5555\/2981780.2981864"},{"key":"e_1_2_1_14_1","unstructured":"Zengfeng Huang. 2018. Near Optimal Frequent Directions for Sketching Dense and Sparse Matrices. In ICML. 2048--2057.  Zengfeng Huang. 2018. Near Optimal Frequent Directions for Sketching Dense and Sparse Matrices. In ICML. 2048--2057."},{"key":"e_1_2_1_15_1","volume-title":"Lee and Michel Verleysen","author":"John","year":"2007","unstructured":"John A. Lee and Michel Verleysen . 2007 . Nonlinear Dimensionality Reduction (1st ed.). Springer Publishing Company , Incorporated. John A. Lee and Michel Verleysen. 2007. Nonlinear Dimensionality Reduction (1st ed.). Springer Publishing Company, Incorporated."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.5555\/2969033.2969070"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1150402.1150436"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2487575.2487623"},{"key":"e_1_2_1_19_1","unstructured":"Matt Mahoney. 2011. Large text compression benchmark. http:\/\/www.mattmahoney.net\/text\/text.html.  Matt Mahoney. 2011. Large text compression benchmark. http:\/\/www.mattmahoney.net\/text\/text.html."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.5555\/2999792.2999959"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.5555\/867576"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.5555\/2969239.2969395"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2939672.2939751"},{"key":"e_1_2_1_24_1","unstructured":"Lawrence Page Sergey Brin Rajeev Motwani and Terry Winograd. 1999. The PageRank citation ranking: bringing order to the web. (1999).  Lawrence Page Sergey Brin Rajeev Motwani and Terry Winograd. 1999. The PageRank citation ranking: bringing order to the web. (1999)."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2623330.2623732"},{"key":"e_1_2_1_26_1","volume-title":"Yingtao Tian, Silvio Lattanzi, and Bryan Perozzi.","author":"Postavaru Stefan","year":"2020","unstructured":"Stefan Postavaru , Anton Tsitsulin , Filipe Miguel Gon\u00e7alves de Almeida , Yingtao Tian, Silvio Lattanzi, and Bryan Perozzi. 2020 . InstantEmbedding: Efficient Local Node Representations. CoRR abs\/2010.06992 (2020). Stefan Postavaru, Anton Tsitsulin, Filipe Miguel Gon\u00e7alves de Almeida, Yingtao Tian, Silvio Lattanzi, and Bryan Perozzi. 2020. InstantEmbedding: Efficient Local Node Representations. CoRR abs\/2010.06992 (2020)."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3308558.3313446"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/3159652.3159706"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3097983.3098061"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/3336191.3371843"},{"key":"e_1_2_1_31_1","doi-asserted-by":"crossref","unstructured":"Tara Safavi Caleb Belth Lukas Faber Davide Mottin Emmanuel M\u00fcller and Danai Koutra. 2019. Personalized Knowledge Graph Summarization: From the Cloud to Your Pocket. In ICDM. 528--537.  Tara Safavi Caleb Belth Lukas Faber Davide Mottin Emmanuel M\u00fcller and Danai Koutra. 2019. Personalized Knowledge Graph Summarization: From the Cloud to Your Pocket. In ICDM. 528--537.","DOI":"10.1109\/ICDM.2019.00063"},{"key":"e_1_2_1_32_1","volume-title":"BioGRID: a general repository for interaction datasets. Nucleic Acids Research","author":"Stark Chris","year":"2006","unstructured":"Chris Stark , Bobby-Joe Breitkreutz , Teresa Reguly , Lorrie Boucher , Ashton Breitkreutz , and Mike Tyers . 2006. BioGRID: a general repository for interaction datasets. Nucleic Acids Research ( 2006 ). Chris Stark, Bobby-Joe Breitkreutz, Teresa Reguly, Lorrie Boucher, Ashton Breitkreutz, and Mike Tyers. 2006. BioGRID: a general repository for interaction datasets. Nucleic Acids Research (2006)."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/2736277.2741093"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1645953.1646094"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/1044731.1044732"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/3178876.3186120"},{"key":"e_1_2_1_37_1","doi-asserted-by":"crossref","unstructured":"Santosh S Vempala. 2005. The random projection method. American Math. Soc.  Santosh S Vempala. 2005. The random projection method. American Math. Soc.","DOI":"10.1090\/dimacs\/065"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1561\/0400000060"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/2396761.2396823"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/3292500.3330951"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.14778\/3377369.3377376"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/3292500.3330860"},{"key":"e_1_2_1_43_1","volume-title":"TPA: Fast, scalable, and accurate method for approximate random walk with restart on billion scale graphs","author":"Yoon Minji","year":"2018","unstructured":"Minji Yoon , Jinhong Jung , and U Kang . 2018 . TPA: Fast, scalable, and accurate method for approximate random walk with restart on billion scale graphs . In ICDE. IEEE , 1132--1143. Minji Yoon, Jinhong Jung, and U Kang. 2018. TPA: Fast, scalable, and accurate method for approximate random walk with restart on billion scale graphs. In ICDE. IEEE, 1132--1143."},{"key":"e_1_2_1_44_1","unstructured":"R. Zafarani and H. Liu. 2009. Social Computing Data Repository at ASU. http:\/\/socialcomputing.asu.edu  R. Zafarani and H. Liu. 2009. Social Computing Data Repository at ASU. http:\/\/socialcomputing.asu.edu"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.5555\/3367471.3367636"},{"key":"e_1_2_1_46_1","doi-asserted-by":"crossref","unstructured":"Ziwei Zhang Peng Cui Haoyang Li Xiao Wang and Wenwu Zhu. 2018. Billion-scale Network Embedding with Iterative Random Projection. In ICDM. 787--796.  Ziwei Zhang Peng Cui Haoyang Li Xiao Wang and Wenwu Zhu. 2018. Billion-scale Network Embedding with Iterative Random Projection. In ICDM. 787--796.","DOI":"10.1109\/ICDM.2018.00094"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/3219819.3219969"},{"key":"e_1_2_1_48_1","first-page":"73","article-title":"Using Anytime Algorithms in Intelligent Systems","volume":"17","author":"Zilberstein Shlomo","year":"1996","unstructured":"Shlomo Zilberstein . 1996 . Using Anytime Algorithms in Intelligent Systems . AI Magazine 17 , 3 (1996), 73 -- 83 . Shlomo Zilberstein. 1996. Using Anytime Algorithms in Intelligent Systems. AI Magazine 17, 3 (1996), 73--83.","journal-title":"AI Magazine"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3447689.3447713","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T11:21:59Z","timestamp":1672226519000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3447689.3447713"}},"subtitle":["anytime graph embeddings"],"short-title":[],"issued":{"date-parts":[[2021,2]]},"references-count":48,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2021,2]]}},"alternative-id":["10.14778\/3447689.3447713"],"URL":"https:\/\/doi.org\/10.14778\/3447689.3447713","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2021,2]]}}}