Towards Lightweight and Automated Representation Learning System for Networks

Abstract

We propose LIGHTNE 2.0, a cost-effective, scalable, automated, and high-quality network embedding system that scales to graphs with hundreds of billions of edges on a single machine. In contrast to the mainstream belief that distributed architecture and GPUs are needed for large-scale network embedding with good quality, we prove that we can achieve higher quality, better scalability, lower cost, and faster runtime with shared-memory, CPU-only architecture. LIGHTNE 2.0 combines two theoretically grounded embedding methods NetSMF and ProNE. We introduce the following techniques to network embedding for the first time: (1) a newly proposed downsampling method to reduce the sample complexity of NetSMF while preserving its theoretical advantages; (2) a high-performance parallel graph processing stack GBBS to achieve high memory efficiency and scalability; (3) sparse parallel hash table to aggregate and maintain the matrix sparsifier in memory; (4) a fast randomized singular value decomposition (SVD) enhanced by power iteration and fast orthonormalization to improve vanilla randomized SVD in terms of both efficiency and effectiveness; (5) Intel MKL for proposed fast randomized SVD and spectral propagation; and (6) a fast and lightweight AutoML library FLAML for automated hyperparameter tuning. Experimental results show that LIGHTNE 2.0 can be up to 84X faster than GraphVite, 30X faster than PBG and 9X faster than NetSMF while delivering better performance. LIGHTNE 2.0 can embed very large graph with 1.7 billion nodes and 124 billion edges in half an hour on a CPU server, while other baselines cannot handle very large graphs of this scale.

References in corpus (14)

• 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
• PyTorch-BigGraph: A Large-scale Graph Embedding System
• Watch Your Step: Learning Node Embeddings via Graph Attention
• NetSMF: Large-Scale Network Embedding as Sparse Matrix Factorization
• GraphVite: A High-Performance CPU-GPU Hybrid System for Node Embedding
• Theoretically Efficient Parallel Graph Algorithms Can Be Fast and Scalable
• Global Convergence of Stochastic Gradient Descent for Some Non-convex Matrix Problems
• Spectral Sparsification of Random-Walk Matrix Polynomials
• Concurrent Hash Tables: Fast and General?(!)
• A Matrix Chernoff Bound for Markov Chains and Its Application to Co-occurrence Matrices
• Streaming Low-Rank Matrix Approximation with an Application to Scientific Simulation