[Formula: see text]: Deep Generative Network Completion.

Area of Science:

• Graph theory
• Network science
• Machine learning

Background:

• Real-world network data often suffer from missing nodes and edges due to resource limitations or privacy concerns.
• Network completion, inferring these missing components, is crucial for accurate downstream network analysis but remains challenging.
• Existing methods primarily focus on link prediction (missing edges) and do not adequately address the joint recovery of nodes and edges.

Purpose of the Study:

• To develop a novel deep generative model for comprehensive network completion, addressing both missing nodes and edges.
• To introduce computationally efficient algorithms for network completion with near-linear runtime complexity.
• To demonstrate the superior performance of the proposed method against state-of-the-art approaches.

Main Methods:

• Proposed DeepNC, a deep generative model utilizing an autoregressive approach to learn edge likelihoods.
• Developed a computationally efficient algorithm for node generation by iteratively maximizing probabilities.
• Enhanced the node generation process using the expectation-maximization algorithm.

Main Results:

• DeepNC effectively infers missing nodes and edges in partially observable networks.
• The proposed algorithms achieve near-linear runtime complexity with respect to the number of nodes.
• Empirical evaluations confirm DeepNC's superiority over existing state-of-the-art network completion methods.

Conclusions:

• DeepNC provides a robust and efficient solution for network completion.
• The method significantly advances the ability to reconstruct and analyze incomplete network data.
• This work paves the way for more accurate network analysis in various domains.