Network Embedding as Matrix Factorization: Unifying DeepWalk, LINE, PTE, and node2vec

Abstract

Since the invention of word2vec, the skip-gram model has significantly advanced the research of network embedding, such as the recent emergence of the DeepWalk, LINE, PTE, and node2vec approaches. In this work, we show that all of the aforementioned models with negative sampling can be unified into the matrix factorization framework with closed forms. Our analysis and proofs reveal that: (1) DeepWalk empirically produces a low-rank transformation of a network's normalized Laplacian matrix; (2) LINE, in theory, is a special case of DeepWalk when the size of vertices' context is set to one; (3) As an extension of LINE, PTE can be viewed as the joint factorization of multiple networks' Laplacians; (4) node2vec is factorizing a matrix related to the stationary distribution and transition probability tensor of a 2nd-order random walk. We further provide the theoretical connections between skip-gram based network embedding algorithms and the theory of graph Laplacian. Finally, we present the NetMF method as well as its approximation algorithm for computing network embedding. Our method offers significant improvements over DeepWalk and LINE for conventional network mining tasks. This work lays the theoretical foundation for skip-gram based network embedding methods, leading to a better understanding of latent network representation learning.

9 pages, published in WSDM 2018 proceedings

References in corpus (1)

• LINE: Large-scale Information Network Embedding

Cited by in corpus (69)

• Graph Contrastive Learning with Adaptive Augmentation
• GCC: Graph Contrastive Coding for Graph Neural Network Pre-Training
• Predicting Dynamic Embedding Trajectory in Temporal Interaction Networks
• DeepInf: Social Influence Prediction with Deep Learning
• Representation Learning for Attributed Multiplex Heterogeneous Network
• Learning Graph Embedding with Adversarial Training Methods
• Link Prediction Based on Graph Neural Networks
• REGAL: Representation Learning-based Graph Alignment
• APAN: Asynchronous Propagation Attention Network for Real-time Temporal Graph Embedding
• Graph Convolutional Networks for Graphs Containing Missing Features
• NetSMF: Large-Scale Network Embedding as Sparse Matrix Factorization
• GraphVite: A High-Performance CPU-GPU Hybrid System for Node Embedding
• Self-Supervised Temporal Graph learning with Temporal and Structural Intensity Alignment
• Semi-supervised Learning on Graphs with Generative Adversarial Nets
• On Proximity and Structural Role-based Embeddings in Networks: Misconceptions, Techniques, and Applications
• Adversarially Regularized Graph Autoencoder for Graph Embedding
• A Comparative Study for Unsupervised Network Representation Learning
• C-SAW: A Framework for Graph Sampling and Random Walk on GPUs
• CONE-Align: Consistent Network Alignment with Proximity-Preserving Node Embedding
• Global Vectors for Node Representations
• Recommender systems based on graph embedding techniques: A comprehensive review
• Multi-Task Representation Learning with Multi-View Graph Convolutional Networks
• GLEE: Geometric Laplacian Eigenmap Embedding
• Is a Single Vector Enough? Exploring Node Polysemy for Network Embedding
• FREDE: Anytime Graph Embeddings
• Understanding WeChat User Preferences and "Wow" Diffusion
• Propositionalization and Embeddings: Two Sides of the Same Coin
• Adversarial Attack Framework on Graph Embedding Models with Limited Knowledge
• Binarized Graph Neural Network
• Embedding-based Silhouette Community Detection
• Unifying Graph Convolution and Contrastive Learning in Collaborative Filtering
• G-CREWE: Graph CompREssion With Embedding for Network Alignment
• Beyond Low-Pass Filters: Adaptive Feature Propagation on Graphs
• PANE: scalable and effective attributed network embedding
• REFINE: Random RangE FInder for Network Embedding
• Analysis of node2vec random walks on networks
• Large-Scale Network Embedding in Apache Spark
• Densest Diverse Subgraphs: How to Plan a Successful Cocktail Party with Diversity
• Counterfactual Learning on Graphs: A Survey
• SketchNE: Embedding Billion-Scale Networks Accurately in One Hour
• Semi-supervised Network Embedding with Differentiable Deep Quantisation
• Link Prediction with Mutual Attention for Text-Attributed Networks
• Link prediction in dynamic networks using random dot product graphs
• Zoo Guide to Network Embedding
• SCE: Scalable Network Embedding from Sparsest Cut
• Network Embedding via Deep Prediction Model
• Towards Improving Embedding Based Models of Social Network Alignment via Pseudo Anchors
• Multiple Kernel Representation Learning on Networks
• Learning Scalable Structural Representations for Link Prediction with Bloom Signatures
• SNoRe: Scalable Unsupervised Learning of Symbolic Node Representations
• QUINT: Node embedding using network hashing
• Towards Deeper Understanding of PPR-based Embedding Approaches: A Topological Perspective
• Deep Node Ranking for Neuro-symbolic Structural Node Embedding and Classification
• Semi-Supervised Learning on Graphs Based on Local Label Distributions
• Graph Summarization via Node Grouping: A Spectral Algorithm
• Heterogeneous Graph Neural Networks for Large-Scale Bid Keyword Matching
• Model-free hidden geometry of complex networks
• Next Waves in Veridical Network Embedding
• FairMILE: Towards an Efficient Framework for Fair Graph Representation Learning
• Accelerating Dynamic Network Embedding with Billions of Parameter Updates to Milliseconds
• Temporal Network Embedding via Tensor Factorization
• Generating Post-hoc Explanations for Skip-gram-based Node Embeddings by Identifying Important Nodes with Bridgeness
• Semantic Graph Neural Network with Multi-measure Learning for Semi-supervised Classification
• On Representation Learning for Scientific News Articles Using Heterogeneous Knowledge Graphs
• GraphScale: A Framework to Enable Machine Learning over Billion-node Graphs
• A Hidden Challenge of Link Prediction: Which Pairs to Check?
• Towards Lightweight and Automated Representation Learning System for Networks
• Measuring Research Interest Similarity with Transition Probabilities
• Efficient Integration of Multi-View Attributed Graphs for Clustering and Embedding