DeepNC

• Verfasst von: Cong Tran [VerfasserIn]
• Verfasst von: Shin, Won-Yong [VerfasserIn]
• Verfasst von: Spitz, Andreas [VerfasserIn]
• Verfasst von: Gertz, Michael [VerfasserIn]
• Titel: DeepNC
• Titelzusatz: Deep generative Network Completion
• Verf.angabe: Cong Tran, student member, IEEE, Won-Yong Shin, senior member, IEEE, Andreas Spitz, and Michael Gertz
• Jahr: 2022
• Umfang: 16 S.
• Fussnoten: Date of publication 19 Oct. 2020 ; Gesehen am 05.04.2022
• Titel Quelle: Enthalten in: Institute of Electrical and Electronics EngineersIEEE transactions on pattern analysis and machine intelligence
• Ort Quelle: New York, NY : IEEE, 1979
• Jahr Quelle: 2022
• Band/Heft Quelle: 44(2022), 4, Seite 1837-1852
• ISSN Quelle: 1939-3539
• DOI: doi:10.1109/TPAMI.2020.3032286
• Datenträger: Online-Ressource
• Sprache: eng
• Sach-SW: Autoregressive generative model
• Sach-SW: deep generative model of graphs
• Sach-SW: Deep learning
• Sach-SW: inference
• Sach-SW: Matrix decomposition
• Sach-SW: network completion
• Sach-SW: partially observable network
• Sach-SW: Pattern analysis
• Sach-SW: Prediction algorithms
• Sach-SW: Predictive models
• Sach-SW: Social networking (online)
• K10plus-PPN: 179742436X

Abstract

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.