Network Completion: Beyond Matrix Completion

Cong Tran, Won Yong Shin

Research output: Chapter in Book/Report/Conference proceedingConference contribution


Due to practical reasons such as limited resources and privacy settings specified by users on social media, most network data tend to be only partially observed with both missing nodes and missing edges. Thus, it is of paramount importance to infer the missing parts of the networks since incomplete network data may severely degrade the performance of downstream analyses. In this paper, we provide a comprehensive survey on network completion, which is a more challenging task than the well-studied low-rank matrix completion problem in the sense that a row and a column of an adjacency matrix shall be entirely unobservable when a node is completely missing from the given network. Specifically, we first define the problem of network completion. Then, we review two state-of-the-art algorithms for discovering the missing part of an underlying network, namely KronEM and DeepNC. We also show a performance comparison between the two algorithms via experimental evaluation. Finally, we discuss the potentials and limitations of the two algorithms.

Original languageEnglish
Title of host publication35th International Conference on Information Networking, ICOIN 2021
PublisherIEEE Computer Society
Number of pages4
ISBN (Electronic)9781728191003
Publication statusPublished - 2021 Jan 13
Event35th International Conference on Information Networking, ICOIN 2021 - Jeju Island, Korea, Republic of
Duration: 2021 Jan 132021 Jan 16

Publication series

NameInternational Conference on Information Networking
ISSN (Print)1976-7684


Conference35th International Conference on Information Networking, ICOIN 2021
Country/TerritoryKorea, Republic of
CityJeju Island

Bibliographical note

Funding Information:
This research was supported by the Republic of Korea’s MSIT (Ministry of Science and ICT), under the High-Potential Individuals Global Training Program (No. 2020-0-01463) supervised by the IITP (Institute of Information and Communications Technology Planning Evaluation), by the Technology Innovation Program (No. 10039010, Development of Lightweight Materials with Superb Mechanical Properties Based on AI) funded By the Ministry of Trade, Industry & Energy (MOTIE, Korea), and by the Yonsei University Research Fund of 2020 (2020-22-0101). 1

Publisher Copyright:
© 2021 IEEE.

All Science Journal Classification (ASJC) codes

  • Computer Networks and Communications
  • Information Systems


Dive into the research topics of 'Network Completion: Beyond Matrix Completion'. Together they form a unique fingerprint.

Cite this