{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,22]],"date-time":"2025-11-22T11:02:44Z","timestamp":1763809364345,"version":"3.41.0"},"reference-count":30,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2014,8,25]],"date-time":"2014-08-25T00:00:00Z","timestamp":1408924800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000145","name":"Division of Information and Intelligent Systems","doi-asserted-by":"publisher","award":["CNS-1017529 and IIS-1218437"],"award-info":[{"award-number":["CNS-1017529 and IIS-1218437"]}],"id":[{"id":"10.13039\/100000145","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000144","name":"Division of Computer and Network Systems","doi-asserted-by":"publisher","award":["CNS-1017529 and IIS-1218437"],"award-info":[{"award-number":["CNS-1017529 and IIS-1218437"]}],"id":[{"id":"10.13039\/100000144","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Knowl. Discov. Data"],"published-print":{"date-parts":[[2014,10,7]]},"abstract":"<jats:p>Consider a social network and suppose that we are only given the number of common friends between each pair of users. Can we reconstruct the underlying network? Similarly, consider a set of documents and the words that appear in them. If we only know the number of common words for every pair of documents, as well as the number of common documents for every pair of words, can we infer which words appear in which documents? In this article, we develop a general methodology for answering questions like these.<\/jats:p>\n          <jats:p>\n            We formalize these questions in what we call the R\n            <jats:sc>econstruct<\/jats:sc>\n            problem: given information about the common neighbors of nodes in a network, our goal is to reconstruct the hidden binary matrix that indicates the presence or absence of relationships between individual nodes. In fact, we propose two different variants of this problem: one where the number of connections of every node (i.e., the degree of every node) is known and a second one where it is unknown. We call these variants the\n            <jats:italic>degree-aware<\/jats:italic>\n            and the\n            <jats:italic>degree-oblivious<\/jats:italic>\n            versions of the R\n            <jats:sc>econstruct<\/jats:sc>\n            problem, respectively.\n          <\/jats:p>\n          <jats:p>Our algorithms for both variants exploit the properties of the singular value decomposition of the hidden binary matrix. More specifically, we show that using the available neighborhood information, we can reconstruct the hidden matrix by finding the components of its singular value decomposition and then combining them appropriately. Our extensive experimental study suggests that our methods are able to reconstruct binary matrices of different characteristics with up to 100% accuracy.<\/jats:p>","DOI":"10.1145\/2641761","type":"journal-article","created":{"date-parts":[[2014,8,26]],"date-time":"2014-08-26T12:08:55Z","timestamp":1409054935000},"page":"1-22","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":15,"title":["Reconstructing Graphs from Neighborhood Data"],"prefix":"10.1145","volume":"8","author":[{"given":"D\u00f3ra","family":"Erd\u0151s","sequence":"first","affiliation":[{"name":"Boston University, Boston MA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rainer","family":"Gemulla","sequence":"additional","affiliation":[{"name":"Max Planck Institut f\u00fcr Informatik, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Evimaria","family":"Terzi","sequence":"additional","affiliation":[{"name":"Boston University, Boston MA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2014,8,25]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(03)00025-4"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1921168.1921197"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btm204"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btp433"},{"volume-title":"CVPR IEEE Conference on Computer Vision and Pattern Recognition.","author":"Boykov Yuri","key":"e_1_2_1_5_1"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10208-009-9045-5"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/320241.320250"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1242572.1242610"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539704442696"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02288367"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2012.154"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.10073"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1718487.1718518"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2010.2046205"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2004.1262177"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1644873.1644874"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2339530.2339663"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536474"},{"volume-title":"Discovery Science","author":"Mielik\u00e4inen Taneli","key":"e_1_2_1_19_1"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10618-008-0107-0"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2010.93"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2020408.2020424"},{"key":"e_1_2_1_23_1","doi-asserted-by":"crossref","unstructured":"Rudy Raymond and Hisashi Kashima. 2010. Fast and scalable algorithms for semi-supervised link prediction on static and dynamic graphs. In ECML\/PKDD. 131--147.   Rudy Raymond and Hisashi Kashima. 2010. Fast and scalable algorithms for semi-supervised link prediction on static and dynamic graphs. In ECML\/PKDD. 131--147.","DOI":"10.1007\/978-3-642-15939-8_9"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00180-009-0158-8"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btr500"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972801.5"},{"key":"e_1_2_1_27_1","doi-asserted-by":"crossref","unstructured":"Zheng Xia Ling-Yun Wu Xiaobo Zhou and Stephen TC Wong. 2010. Semi-supervised drug-protein interaction prediction from heterogeneous biological spaces. BMC Syst. Biol. (2010) 4(Suppl 2):S6.  Zheng Xia Ling-Yun Wu Xiaobo Zhou and Stephen TC Wong. 2010. Semi-supervised drug-protein interaction prediction from heterogeneous biological spaces. BMC Syst. Biol. (2010) 4(Suppl 2):S6.","DOI":"10.1186\/1752-0509-4-S2-S6"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btn162"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/1526709.1526781"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1557019.1557128"}],"container-title":["ACM Transactions on Knowledge Discovery from Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2641761","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2641761","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T06:56:19Z","timestamp":1750229779000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2641761"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,8,25]]},"references-count":30,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2014,10,7]]}},"alternative-id":["10.1145\/2641761"],"URL":"https:\/\/doi.org\/10.1145\/2641761","relation":{},"ISSN":["1556-4681","1556-472X"],"issn-type":[{"type":"print","value":"1556-4681"},{"type":"electronic","value":"1556-472X"}],"subject":[],"published":{"date-parts":[[2014,8,25]]},"assertion":[{"value":"2013-05-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-12-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-08-25","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}