  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 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.
