  Attributed network embedding aims to learn low-dimensional vector
representations for nodes in a network, where each node contains rich
attributes/features describing node content. Because network topology structure
and node attributes often exhibit high correlation, incorporating node
attribute proximity into network embedding is beneficial for learning good
vector representations. In reality, large-scale networks often have
incomplete/missing node content or linkages, yet existing attributed network
embedding algorithms all operate under the assumption that networks are
complete. Thus, their performance is vulnerable to missing data and suffers
from poor scalability.
  In this paper, we propose a Scalable Incomplete Network Embedding (SINE)
algorithm for learning node representations from incomplete graphs. SINE
formulates a probabilistic learning framework that separately models pairs of
node-context and node-attribute relationships. Different from existing
attributed network embedding algorithms, SINE provides greater flexibility to
make the best of useful information and mitigate negative effects of missing
information on representation learning. A stochastic gradient descent based
online algorithm is derived to learn node representations, allowing SINE to
scale up to large-scale networks with high learning efficiency. We evaluate the
effectiveness and efficiency of SINE through extensive experiments on
real-world networks. Experimental results confirm that SINE outperforms
state-of-the-art baselines in various tasks, including node classification,
node clustering, and link prediction, under settings with missing links and
node attributes. SINE is also shown to be scalable and efficient on large-scale
networks with millions of nodes/edges and high-dimensional node features. The
source code of this paper is available at https://github.com/daokunzhang/SINE.
