NetSMF: Large-Scale Network Embedding as Sparse Matrix Factorization

Abstract

We study the problem of large-scale network embedding, which aims to learn latent representations for network mining applications. Previous research shows that 1) popular network embedding benchmarks, such as DeepWalk, are in essence implicitly factorizing a matrix with a closed form, and 2)the explicit factorization of such matrix generates more powerful embeddings than existing methods. However, directly constructing and factorizing this matrix---which is dense---is prohibitively expensive in terms of both time and space, making it not scalable for large networks. In this work, we present the algorithm of large-scale network embedding as sparse matrix factorization (NetSMF). NetSMF leverages theories from spectral sparsification to efficiently sparsify the aforementioned dense matrix, enabling significantly improved efficiency in embedding learning. The sparsified matrix is spectrally close to the original dense one with a theoretically bounded approximation error, which helps maintain the representation power of the learned embeddings. We conduct experiments on networks of various scales and types. Results show that among both popular benchmarks and factorization based methods, NetSMF is the only method that achieves both high efficiency and effectiveness. We show that NetSMF requires only 24 hours to generate effective embeddings for a large-scale academic collaboration network with tens of millions of nodes, while it would cost DeepWalk months and is computationally infeasible for the dense matrix factorization solution. The source code of NetSMF is publicly available (https://github.com/xptree/NetSMF).

11 pages, in Proceedings of the Web Conference 2019 (WWW 19)

References in corpus (6)

• Distributed Representations of Words and Phrases and their Compositionality
• DeepWalk: Online Learning of Social Representations
• LINE: Large-scale Information Network Embedding
• Graph Convolutional Neural Networks for Web-Scale Recommender Systems
• Network Embedding as Matrix Factorization: Unifying DeepWalk, LINE, PTE, and node2vec
• VERSE: Versatile Graph Embeddings from Similarity Measures

Cited by in corpus (16)

• GCC: Graph Contrastive Coding for Graph Neural Network Pre-Training
• Representation Learning for Attributed Multiplex Heterogeneous Network
• APAN: Asynchronous Propagation Attention Network for Real-time Temporal Graph Embedding
• Recommender systems based on graph embedding techniques: A comprehensive review
• FREDE: Anytime Graph Embeddings
• Subset Node Anomaly Tracking over Large Dynamic Graphs
• REFINE: Random RangE FInder for Network Embedding
• Large-Scale Network Embedding in Apache Spark
• OAG-Bench: A Human-Curated Benchmark for Academic Graph Mining
• SketchNE: Embedding Billion-Scale Networks Accurately in One Hour
• Towards Improving Embedding Based Models of Social Network Alignment via Pseudo Anchors
• Multiple Kernel Representation Learning on Networks
• QUINT: Node embedding using network hashing
• Accelerating Dynamic Network Embedding with Billions of Parameter Updates to Milliseconds
• HUGE: Huge Unsupervised Graph Embeddings with TPUs
• Towards Lightweight and Automated Representation Learning System for Networks