Network completion via deep metric learning

Completing networks is often a necessary step when dealing with problems arising from applications in incomplete network data mining. This paper investigates the network completion problem with node attributes. We proposed a new method called DeepMetricNC by exploiting the correlation between node attributes and the underlying network structure. In DeepMetricNC, the correlation is modeled as a nonlinear mapping from node attributes to the probability of edge existence. To obtain the mapping, deep metric learning is applied with batch training and random negative sampling. DeepMetricNC has linear training time complexity and can adapt to large-scale network completion tasks. Experiments of real networks show that DeepMetricNC completes network structures better than other methods, and is more suitable when the portion of the observed part is small.