Initialization for Network Embedding: A Graph Partition Approach

Abstract

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

arXiv commentFull Research Paper accepted in the 13th ACM International Conference on Web Search and Data Mining (WSDM 2020)

References in corpus (10)

• Distributed Representations of Words and Phrases and their Compositionality
• Inductive Representation Learning on Large Graphs
• Graph Embedding Techniques, Applications, and Performance: A Survey
• word2vec Explained: deriving Mikolov et al.'s negative-sampling word-embedding method
• A Comprehensive Survey of Graph Embedding: Problems, Techniques and Applications
• HARP: Hierarchical Representation Learning for Networks
• Structural Deep Embedding for Hyper-Networks
• A Survey on Network Embedding
• A Tutorial on Network Embeddings
• MILE: A Multi-Level Framework for Scalable Graph Embedding

Cited by in corpus (3)

• GraphZoom: A multi-level spectral approach for accurate and scalable graph embedding
• Measuring Friendship Closeness: A Perspective of Social Identity Theory
• Bridged-GNN: Knowledge Bridge Learning for Effective Knowledge Transfer