DeepNC: Deep generative Network Completion
Most network data are collected from partially observable networks with both missing nodes and missing edges, for example, due to limited resources and privacy settings specified by users on social media. Thus, it stands to reason that inferring the missing parts of the networks by performing networ...
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Article (Journal) |
| Language: | English |
| Published: |
2022
|
| In: |
IEEE transactions on pattern analysis and machine intelligence
Year: 2022, Volume: 44, Issue: 4, Pages: 1837-1852 |
| ISSN: | 1939-3539 |
| DOI: | 10.1109/TPAMI.2020.3032286 |
| Online Access: | Verlag, lizenzpflichtig, Volltext: https://doi.org/10.1109/TPAMI.2020.3032286
|
| Author Notes: | Cong Tran, student member, IEEE, Won-Yong Shin, senior member, IEEE, Andreas Spitz, and Michael Gertz |
MARC
| LEADER | 00000caa a2200000 c 4500 | ||
|---|---|---|---|
| 001 | 179742436X | ||
| 003 | DE-627 | ||
| 005 | 20220820160216.0 | ||
| 007 | cr uuu---uuuuu | ||
| 008 | 220404s2022 xx |||||o 00| ||eng c | ||
| 024 | 7 | |a 10.1109/TPAMI.2020.3032286 |2 doi | |
| 035 | |a (DE-627)179742436X | ||
| 035 | |a (DE-599)KXP179742436X | ||
| 035 | |a (OCoLC)1341458216 | ||
| 040 | |a DE-627 |b ger |c DE-627 |e rda | ||
| 041 | |a eng | ||
| 084 | |a 27 |2 sdnb | ||
| 100 | 0 | |a Cong Tran |e VerfasserIn |0 (DE-588)1254847839 |0 (DE-627)1797634666 |4 aut | |
| 245 | 1 | 0 | |a DeepNC |b Deep generative Network Completion |c Cong Tran, student member, IEEE, Won-Yong Shin, senior member, IEEE, Andreas Spitz, and Michael Gertz |
| 264 | 1 | |c 2022 | |
| 300 | |a 16 | ||
| 336 | |a Text |b txt |2 rdacontent | ||
| 337 | |a Computermedien |b c |2 rdamedia | ||
| 338 | |a Online-Ressource |b cr |2 rdacarrier | ||
| 500 | |a Date of publication 19 Oct. 2020 | ||
| 500 | |a Gesehen am 05.04.2022 | ||
| 520 | |a Most network data are collected from partially observable networks with both missing nodes and missing edges, for example, due to limited resources and privacy settings specified by users on social media. Thus, it stands to reason that inferring the missing parts of the networks by performing network completion should precede downstream applications. However, despite this need, the recovery of missing nodes and edges in such incomplete networks is an insufficiently explored problem due to the modeling difficulty, which is much more challenging than link prediction that only infers missing edges. In this paper, we present DeepNC, a novel method for inferring the missing parts of a network based on a deep generative model of graphs. Specifically, our method first learns a likelihood over edges via an autoregressive generative model, and then identifies the graph that maximizes the learned likelihood conditioned on the observable graph topology. Moreover, we propose a computationally efficient $\sf DeepNC$DeepNC algorithm that consecutively finds individual nodes that maximize the probability in each node generation step, as well as an enhanced version using the expectation-maximization algorithm. The runtime complexities of both algorithms are shown to be almost linear in the number of nodes in the network. We empirically demonstrate the superiority of DeepNC over state-of-the-art network completion approaches. | ||
| 650 | 4 | |a Autoregressive generative model | |
| 650 | 4 | |a deep generative model of graphs | |
| 650 | 4 | |a Deep learning | |
| 650 | 4 | |a inference | |
| 650 | 4 | |a Matrix decomposition | |
| 650 | 4 | |a network completion | |
| 650 | 4 | |a partially observable network | |
| 650 | 4 | |a Pattern analysis | |
| 650 | 4 | |a Prediction algorithms | |
| 650 | 4 | |a Predictive models | |
| 650 | 4 | |a Social networking (online) | |
| 700 | 1 | |a Shin, Won-Yong |e VerfasserIn |4 aut | |
| 700 | 1 | |a Spitz, Andreas |e VerfasserIn |4 aut | |
| 700 | 1 | |a Gertz, Michael |e VerfasserIn |0 (DE-588)1038076579 |0 (DE-627)756636973 |0 (DE-576)392095645 |4 aut | |
| 773 | 0 | 8 | |i Enthalten in |a Institute of Electrical and Electronics Engineers |t IEEE transactions on pattern analysis and machine intelligence |d New York, NY : IEEE, 1979 |g 44(2022), 4, Seite 1837-1852 |h Online-Ressource |w (DE-627)324486421 |w (DE-600)2027336-8 |w (DE-576)094110980 |x 1939-3539 |7 nnas |
| 773 | 1 | 8 | |g volume:44 |g year:2022 |g number:4 |g pages:1837-1852 |g extent:16 |a DeepNC Deep generative Network Completion |
| 856 | 4 | 0 | |u https://doi.org/10.1109/TPAMI.2020.3032286 |x Verlag |x Resolving-System |z lizenzpflichtig |3 Volltext |
| 951 | |a AR | ||
| 992 | |a 20220404 | ||
| 993 | |a Article | ||
| 994 | |a 2022 | ||
| 998 | |g 1038076579 |a Gertz, Michael |m 1038076579:Gertz, Michael |d 110000 |d 110300 |e 110000PG1038076579 |e 110300PG1038076579 |k 0/110000/ |k 1/110000/110300/ |p 4 |y j | ||
| 999 | |a KXP-PPN179742436X |e 4111798411 | ||
| BIB | |a Y | ||
| SER | |a journal | ||
| JSO | |a {"id":{"doi":["10.1109/TPAMI.2020.3032286"],"eki":["179742436X"]},"name":{"displayForm":["Cong Tran, student member, IEEE, Won-Yong Shin, senior member, IEEE, Andreas Spitz, and Michael Gertz"]},"recId":"179742436X","physDesc":[{"extent":"16 S."}],"title":[{"title":"DeepNC","title_sort":"DeepNC","subtitle":"Deep generative Network Completion"}],"type":{"bibl":"article-journal","media":"Online-Ressource"},"language":["eng"],"note":["Date of publication 19 Oct. 2020","Gesehen am 05.04.2022"],"origin":[{"dateIssuedDisp":"2022","dateIssuedKey":"2022"}],"relHost":[{"language":["eng"],"type":{"media":"Online-Ressource","bibl":"periodical"},"note":["Gesehen am 07. März 2019"],"title":[{"title":"IEEE transactions on pattern analysis and machine intelligence","title_sort":"IEEE transactions on pattern analysis and machine intelligence","subtitle":"TPAMI"}],"origin":[{"publisher":"IEEE","dateIssuedKey":"1979","dateIssuedDisp":"1979-","publisherPlace":"New York, NY"}],"disp":"Institute of Electrical and Electronics EngineersIEEE transactions on pattern analysis and machine intelligence","physDesc":[{"extent":"Online-Ressource"}],"recId":"324486421","id":{"eki":["324486421"],"issn":["1939-3539"],"zdb":["2027336-8"]},"part":{"year":"2022","volume":"44","pages":"1837-1852","extent":"16","text":"44(2022), 4, Seite 1837-1852","issue":"4"},"corporate":[{"role":"aut","display":"Institute of Electrical and Electronics Engineers"}],"name":{"displayForm":["Institute of Electrical and Electronics Engineers"]},"titleAlt":[{"title":"Transactions on pattern analysis and machine intelligence"},{"title":"TPAMI"}],"pubHistory":["1.1979 -"]}],"person":[{"family":"Cong Tran","role":"aut","given":"","display":"Cong Tran"},{"role":"aut","given":"Won-Yong","family":"Shin","display":"Shin, Won-Yong"},{"role":"aut","given":"Andreas","family":"Spitz","display":"Spitz, Andreas"},{"display":"Gertz, Michael","family":"Gertz","role":"aut","given":"Michael"}]} | ||
| SRT | |a CONGTRANSHDEEPNC2022 | ||