DeepNC

DeepNC infers missing nodes and edges in partially observed networks using an autoregressive deep generative model to reconstruct underlying graph topology.

Key Features:

• Deep Generative Model of Graphs: DeepNC uses an autoregressive generative model to learn likelihoods over edges in a graph.
• Autoregressive Edge Likelihood Learning: The model estimates edge probabilities conditioned on the observed topology to enable prediction of missing components.
• Graph Maximization: DeepNC identifies the graph configuration that maximizes the learned likelihood conditioned on the observable parts of the network.
• Efficient Algorithms: Two algorithms are provided: a stepwise algorithm that selects nodes maximizing probability at each generation step, and an enhanced version leveraging the expectation-maximization algorithm, both with almost linear runtime relative to the number of nodes.

Scientific Applications:

• Social network analysis: Infer missing users and interactions in social media networks affected by limited resources or privacy settings.
• Biological network reconstruction: Reconstruct partially observed biological networks by inferring missing nodes and edges.
• General network completion: Apply network completion techniques to any domain requiring inference of missing nodes and edges in incomplete graphs.

Methodology:

DeepNC learns edge likelihoods through an autoregressive generative model, maximizes the learned likelihood conditioned on observed topology to reconstruct missing parts, and employs two efficient algorithms (a stepwise node-selection algorithm and an expectation-maximization–enhanced variant) with almost linear runtime relative to the number of nodes.