Initialization for Network Embedding: A Graph Partition Approach
  Network embedding has been intensively studied in the literature and widely
used in various applications, such as link prediction and node classification.
While previous work focus on the design of new algorithms or are tailored for
various problem settings, the discussion of initialization strategies in the
learning process is often missed. In this work, we address this important issue
of initialization for network embedding that could dramatically improve the
performance of the algorithms on both effectiveness and efficiency.
Specifically, we first exploit the graph partition technique that divides the
graph into several disjoint subsets, and then construct an abstract graph based
on the partitions. We obtain the initialization of the embedding for each node
in the graph by computing the network embedding on the abstract graph, which is
much smaller than the input graph, and then propagating the embedding among the
nodes in the input graph. With extensive experiments on various datasets, we
demonstrate that our initialization technique significantly improves the
performance of the state-of-the-art algorithms on the evaluations of link
prediction and node classification by up to 7.76% and 8.74% respectively.
Besides, we show that the technique of initialization reduces the running time
of the state-of-the-arts by at least 20%.
