LINE: Large-scale Information Network Embedding

Abstract

This paper studies the problem of embedding very large information networks into low-dimensional vector spaces, which is useful in many tasks such as visualization, node classification, and link prediction. Most existing graph embedding methods do not scale for real world information networks which usually contain millions of nodes. In this paper, we propose a novel network embedding method called the "LINE," which is suitable for arbitrary types of information networks: undirected, directed, and/or weighted. The method optimizes a carefully designed objective function that preserves both the local and global network structures. An edge-sampling algorithm is proposed that addresses the limitation of the classical stochastic gradient descent and improves both the effectiveness and the efficiency of the inference. Empirical experiments prove the effectiveness of the LINE on a variety of real-world information networks, including language networks, social networks, and citation networks. The algorithm is very efficient, which is able to learn the embedding of a network with millions of vertices and billions of edges in a few hours on a typical single machine. The source code of the LINE is available online.

WWW 2015

References in corpus (4)

• Distributed Representations of Words and Phrases and their Compositionality
• DeepWalk: Online Learning of Social Representations
• Distributed Representations of Sentences and Documents
• Node Classification in Social Networks

Cited by in corpus (272)

• A Comprehensive Survey on Graph Neural Networks
• Geometric deep learning: going beyond Euclidean data
• Graph Embedding Techniques, Applications, and Performance: A Survey
• Self-supervised Learning: Generative or Contrastive
• struc2vec: Learning Node Representations from Structural Identity
• MAGNN: Metapath Aggregated Graph Neural Network for Heterogeneous Graph Embedding
• A Comprehensive Survey on Graph Anomaly Detection with Deep Learning
• GCC: Graph Contrastive Coding for Graph Neural Network Pre-Training
• PTE: Predictive Text Embedding through Large-scale Heterogeneous Text Networks
• Network Embedding as Matrix Factorization: Unifying DeepWalk, LINE, PTE, and node2vec
• DeepInf: Social Influence Prediction with Deep Learning
• Neural Network-based Graph Embedding for Cross-Platform Binary Code Similarity Detection
• Graph Self-Supervised Learning: A Survey
• AM-GCN: Adaptive Multi-channel Graph Convolutional Networks
• Representation Learning for Attributed Multiplex Heterogeneous Network
• Graph Learning: A Survey
• Attributed Social Network Embedding
• Graph Embedding on Biomedical Networks: Methods, Applications, and Evaluations
• Attributed Network Embedding for Learning in a Dynamic Environment
• Learning Graph Embedding with Adversarial Training Methods
• A Semi-supervised Graph Attentive Network for Financial Fraud Detection
• A Comprehensive Survey on Deep Graph Representation Learning
• Visualizing Large-scale and High-dimensional Data
• SHINE: Signed Heterogeneous Information Network Embedding for Sentiment Link Prediction
• Graph Representation Learning in Biomedicine
• VERSE: Versatile Graph Embeddings from Similarity Measures
• REGAL: Representation Learning-based Graph Alignment
• Deep Multi-View Spatial-Temporal Network for Taxi Demand Prediction
• GETNext: Trajectory Flow Map Enhanced Transformer for Next POI Recommendation
• Graph Representation Learning: A Survey
• Adaptive Graph Encoder for Attributed Graph Embedding
• Fi-GNN: Modeling Feature Interactions via Graph Neural Networks for CTR Prediction
• SumGNN: Multi-typed Drug Interaction Prediction via Efficient Knowledge Graph Summarization
• ST-GRAT: A Novel Spatio-temporal Graph Attention Network for Accurately Forecasting Dynamically Changing Road Speed
• Learning Combinatorial Embedding Networks for Deep Graph Matching
• IntentGC: a Scalable Graph Convolution Framework Fusing Heterogeneous Information for Recommendation
• HDMI: High-order Deep Multiplex Infomax
• Exploiting Cross-Session Information for Session-based Recommendation with Graph Neural Networks
• TTAGN: Temporal Transaction Aggregation Graph Network for Ethereum Phishing Scams Detection
• Through a Gender Lens: Learning Usage Patterns of Emojis from Large-Scale Android Users
• Easing Embedding Learning by Comprehensive Transcription of Heterogeneous Information Networks
• MCNE: An End-to-End Framework for Learning Multiple Conditional Network Representations of Social Network
• Ad Hoc Table Retrieval using Semantic Similarity
• Graph Convolutional Networks for Graphs Containing Missing Features
• MR-GNN: Multi-Resolution and Dual Graph Neural Network for Predicting Structured Entity Interactions
• STP-UDGAT: Spatial-Temporal-Preference User Dimensional Graph Attention Network for Next POI Recommendation
• Attention-based graph neural networks: a survey
• Personalized Graph Neural Networks with Attention Mechanism for Session-Aware Recommendation
• Deep Network Embedding for Graph Representation Learning in Signed Networks
• NetSMF: Large-Scale Network Embedding as Sparse Matrix Factorization
• Dressing as a Whole: Outfit Compatibility Learning Based on Node-wise Graph Neural Networks
• Is a Single Embedding Enough? Learning Node Representations that Capture Multiple Social Contexts
• GraphVite: A High-Performance CPU-GPU Hybrid System for Node Embedding
• Network Together: Node Classification via Cross network Deep Network Embedding
• Comprehensive evaluation of deep and graph learning on drug-drug interactions prediction
• Multiplex Heterogeneous Graph Convolutional Network
• GAD-NR: Graph Anomaly Detection via Neighborhood Reconstruction
• Streaming Graph Neural Networks via Continual Learning
• EvoKG: Jointly Modeling Event Time and Network Structure for Reasoning over Temporal Knowledge Graphs
• TREND: TempoRal Event and Node Dynamics for Graph Representation Learning
• M2GRL: A Multi-task Multi-view Graph Representation Learning Framework for Web-scale Recommender Systems
• Representation Learning for Natural Language Processing
• Semi-supervised Learning on Graphs with Generative Adversarial Nets
• On Proximity and Structural Role-based Embeddings in Networks: Misconceptions, Techniques, and Applications
• Generating Reliable Friends via Adversarial Training to Improve Social Recommendation
• SATAR: A Self-supervised Approach to Twitter Account Representation Learning and its Application in Bot Detection
• Multiscale Spatio-Temporal Graph Neural Networks for 3D Skeleton-Based Motion Prediction
• K-Core based Temporal Graph Convolutional Network for Dynamic Graphs
• Unsupervised Social Bot Detection via Structural Information Theory
• A Hierarchical Attention Model for Social Contextual Image Recommendation
• MGDCF: Distance Learning via Markov Graph Diffusion for Neural Collaborative Filtering
• Anomaly Detection in Dynamic Graphs: A Comprehensive Survey
• Distributed Representations of Signed Networks
• Principled approach to the selection of the embedding dimension of networks
• MODEL: Motif-based Deep Feature Learning for Link Prediction
• RoSGAS: Adaptive Social Bot Detection with Reinforced Self-Supervised GNN Architecture Search
• TIMME: Twitter Ideology-detection via Multi-task Multi-relational Embedding
• A Comparative Study for Unsupervised Network Representation Learning
• Exploring Student Check-In Behavior for Improved Point-of-Interest Prediction
• MAUIL: Multi-level Attribute Embedding for Semi-supervised User Identity Linkage
• MultiVERSE: a multiplex and multiplex-heterogeneous network embedding approach
• Network Embedding with Completely-imbalanced Labels
• Source Localization of Graph Diffusion via Variational Autoencoders for Graph Inverse Problems
• Self-supervised Consensus Representation Learning for Attributed Graph
• Global Vectors for Node Representations
• GloDyNE: Global Topology Preserving Dynamic Network Embedding
• Attention Is Not the Only Choice: Counterfactual Reasoning for Path-Based Explainable Recommendation
• Continual Learning on Dynamic Graphs via Parameter Isolation
• TwHIN: Embedding the Twitter Heterogeneous Information Network for Personalized Recommendation
• Leveraging Deep Graph-Based Text Representation for Sentiment Polarity Applications
• Multi-Task Representation Learning with Multi-View Graph Convolutional Networks
• Recommender systems based on graph embedding techniques: A comprehensive review
• Artificial intelligence and machine learning applications for cultured meat
• Review on Learning and Extracting Graph Features for Link Prediction
• Bringing Your Own View: Graph Contrastive Learning without Prefabricated Data Augmentations
• Artificial Intelligence and Deep Learning Algorithms for Epigenetic Sequence Analysis: A Review for Epigeneticists and AI Experts
• AEGCN: An Autoencoder-Constrained Graph Convolutional Network
• Machine Learning Partners in Criminal Networks
• HMSG: Heterogeneous Graph Neural Network based on Metapath Subgraph Learning
• Graph Contrastive Learning with Generative Adversarial Network
• Hashing-Accelerated Graph Neural Networks for Link Prediction
• Unbiased Graph Embedding with Biased Graph Observations
• Human Values and Attitudes towards Vaccination in Social Media
• Learning Graph Neural Networks with Positive and Unlabeled Nodes
• A Spatial-Temporal Graph Neural Network Framework for Automated Software Bug Triaging
• Heterogeneous Graph Contrastive Learning with Meta-path Contexts and Adaptively Weighted Negative Samples
• FREDE: Anytime Graph Embeddings
• Learning to Make Predictions on Graphs with Autoencoders
• Explicit Time Embedding Based Cascade Attention Network for Information Popularity Prediction
• Is a Single Vector Enough? Exploring Node Polysemy for Network Embedding
• paper2repo: GitHub Repository Recommendation for Academic Papers
• Graph Mining for Cybersecurity: A Survey
• Deep Collaborative Embedding for information cascade prediction
• Meta-Inductive Node Classification across Graphs
• Identifying translational science through embeddings of controlled vocabularies
• Understanding WeChat User Preferences and "Wow" Diffusion
• SI-spreading-based network embedding in static and temporal networks
• Propositionalization and Embeddings: Two Sides of the Same Coin
• Network representation learning systematic review: ancestors and current development state
• Capturing Edge Attributes via Network Embedding
• Higher-order Spectral Clustering for Heterogeneous Graphs
• Adversarial Attack Framework on Graph Embedding Models with Limited Knowledge
• Embedding-based Silhouette Community Detection
• Nowcasting the Stance of Social Media Users in a Sudden Vote: The Case of the Greek Referendum
• Binarized Graph Neural Network
• X-GOAL: Multiplex Heterogeneous Graph Prototypical Contrastive Learning
• Beyond Low-Pass Filters: Adaptive Feature Propagation on Graphs
• Benchmarking Network Embedding Models for Link Prediction: Are We Making Progress?
• G-CREWE: Graph CompREssion With Embedding for Network Alignment
• Shortest path distance approximation using deep learning techniques
• An Attention-based Graph Neural Network for Heterogeneous Structural Learning
• Improving Neural Relation Extraction with Implicit Mutual Relations
• Learning and Transferring IDs Representation in E-commerce
• PANE: scalable and effective attributed network embedding
• Hyper-Path-Based Representation Learning for Hyper-Networks
• STWalk: Learning Trajectory Representations in Temporal Graphs
• A Framework for Quantifying Controversy of Social Network Debates Using Attributed Networks: Biased Random Walk (BRW)
• A Self-supervised Riemannian GNN with Time Varying Curvature for Temporal Graph Learning
• Pre-train and Learn: Preserve Global Information for Graph Neural Networks
• Uniform Manifold Approximation with Two-phase Optimization
• CLDG: Contrastive Learning on Dynamic Graphs
• Visualizing Graph Neural Networks with CorGIE: Corresponding a Graph to Its Embedding
• Region2Vec: Community Detection on Spatial Networks Using Graph Embedding with Node Attributes and Spatial Interactions
• REFINE: Random RangE FInder for Network Embedding
• RMove: Recommending Move Method Refactoring Opportunities using Structural and Semantic Representations of Code
• BHIN2vec: Balancing the Type of Relation in Heterogeneous Information Network
• Temporal Aggregation and Propagation Graph Neural Networks for Dynamic Representation
• Transition Propagation Graph Neural Networks for Temporal Networks
• Learning Social Image Embedding with Deep Multimodal Attention Networks
• Multi-View Collaborative Network Embedding
• Time-aware Metapath Feature Augmentation for Ponzi Detection in Ethereum
• Unsupervised Inductive Graph-Level Representation Learning via Graph-Graph Proximity
• Network Alignment
• JNET: Learning User Representations via Joint Network Embedding and Topic Embedding
• Revisiting Dynamic Graph Clustering via Matrix Factorization
• Graph Representation Learning Beyond Node and Homophily
• ExEm: Expert Embedding using dominating set theory with deep learning approaches
• Hypergraph Partitioning With Embeddings
• Deep Learning for Learning Graph Representations
• Hierarchical Aggregations for High-Dimensional Multiplex Graph Embedding
• Challenging the Myth of Graph Collaborative Filtering: a Reasoned and Reproducibility-driven Analysis
• An Unsupervised Framework for Comparing Graph Embeddings
• Cross-domain Network Representations
• GSim: A Graph Neural Network based Relevance Measure for Heterogeneous Graphs
• The Effects of Randomness on the Stability of Node Embeddings
• SWAG: Item Recommendations using Convolutions on Weighted Graphs
• OAG-Bench: A Human-Curated Benchmark for Academic Graph Mining
• Counterfactual Learning on Graphs: A Survey
• RPT: Toward Transferable Model on Heterogeneous Researcher Data via Pre-Training
• Measuring Friendship Closeness: A Perspective of Social Identity Theory
• Investigating Extensions to Random Walk Based Graph Embedding
• SketchNE: Embedding Billion-Scale Networks Accurately in One Hour
• CSNE: Conditional Signed Network Embedding
• Recommending on graphs: a comprehensive review from a data perspective
• Semantic Table Retrieval using Keyword and Table Queries
• Multitask Learning on Graph Neural Networks: Learning Multiple Graph Centrality Measures with a Unified Network
• Semi-supervised Network Embedding with Differentiable Deep Quantisation
• Embedding and trajectories of temporal networks
• Effective and Efficient PageRank-based Positioning for Graph Visualization
• Generative Graph Convolutional Network for Growing Graphs
• CoarSAS2hvec: Heterogeneous Information Network Embedding with Balanced Network Sampling
• Node-Centric Graph Learning from Data for Brain State Identification
• Learning event representations for temporal segmentation of image sequences by dynamic graph embedding
• Advancing Biomedicine with Graph Representation Learning: Recent Progress, Challenges, and Future Directions
• Adversarially Regularized Graph Attention Networks for Inductive Learning on Partially Labeled Graphs
• Dual Policy Learning for Aggregation Optimization in Graph Neural Network-based Recommender Systems
• SurfCon: Synonym Discovery on Privacy-Aware Clinical Data
• Learning Edge Properties in Graphs from Path Aggregations
• BSAL: A Framework of Bi-component Structure and Attribute Learning for Link Prediction
• Weakly Supervised Learning for Analyzing Political Campaigns on Facebook
• Complex systems: features, similarity and connectivity
• Initialization Matters: Regularizing Manifold-informed Initialization for Neural Recommendation Systems
• Temporal Graph Representation Learning with Adaptive Augmentation Contrastive
• Zoo Guide to Network Embedding
• SCE: Scalable Network Embedding from Sparsest Cut
• Towards Improving Embedding Based Models of Social Network Alignment via Pseudo Anchors
• Multiple Kernel Representation Learning on Networks
• Network Embedding via Deep Prediction Model
• Graph Representation Learning for Popularity Prediction Problem: A Survey
• Adaptive Multi-Order Graph Regularized NMF with Dual Sparsity for Hyperspectral Unmixing
• SSNE: Effective Node Representation for Link Prediction in Sparse Networks
• SNoRe: Scalable Unsupervised Learning of Symbolic Node Representations
• Multi-Graph based Multi-Scenario Recommendation in Large-scale Online Video Services
• Embedding Node Structural Role Identity Using Stress Majorization
• Topic-aware latent models for representation learning on networks
• CaEGCN: Cross-Attention Fusion based Enhanced Graph Convolutional Network for Clustering
• Modeling Event Propagation via Graph Biased Temporal Point Process
• Word Embeddings for Entity-annotated Texts
• Deep Node Ranking for Neuro-symbolic Structural Node Embedding and Classification
• QUINT: Node embedding using network hashing
• Deep Kernel Supervised Hashing for Node Classification in Structural Networks
• Consistency and Discrepancy-Based Contrastive Tripartite Graph Learning for Recommendations
• Towards Deeper Understanding of PPR-based Embedding Approaches: A Topological Perspective
• Modeling Graphs with Vertex Replacement Grammars
• Better with Less: A Data-Active Perspective on Pre-Training Graph Neural Networks
• Model-free hidden geometry of complex networks
• Towards Interpretable Graph Modeling with Vertex Replacement Grammars
• Twitter User Representation Using Weakly Supervised Graph Embedding
• An Interpretable Ensemble of Graph and Language Models for Improving Search Relevance in E-Commerce
• Cross-domain Aspect Category Transfer and Detection via Traceable Heterogeneous Graph Representation Learning
• EvalNE: A Framework for Evaluating Network Embeddings on Link Prediction
• Time-Series Snapshot Network for Partner Recommendation: A Case Study on OSS
• Temporal Network Embedding via Tensor Factorization
• Generating Post-hoc Explanations for Skip-gram-based Node Embeddings by Identifying Important Nodes with Bridgeness
• Accelerating Dynamic Network Embedding with Billions of Parameter Updates to Milliseconds
• PushNet: Efficient and Adaptive Neural Message Passing
• Next Waves in Veridical Network Embedding
• SCOREH+: A High-Order Node Proximity Spectral Clustering on Ratios-of-Eigenvectors Algorithm for Community Detection
• NetDP: An Industrial-Scale Distributed Network Representation Framework for Default Prediction in Ant Credit Pay
• Determinable and interpretable network representation for link prediction
• Author Name Disambiguation via Heterogeneous Network Embedding from Structural and Semantic Perspectives
• SMARTQUERY: An Active Learning Framework for Graph Neural Networks through Hybrid Uncertainty Reduction
• Non-linear Attributed Graph Clustering by Symmetric NMF with PU Learning
• Sampled in Pairs and Driven by Text: A New Graph Embedding Framework
• Symbolic Graph Embedding using Frequent Pattern Mining
• Link Prediction via controlling the leading eigenvector
• GPSP: Graph Partition and Space Projection based Approach for Heterogeneous Network Embedding
• Improving link prediction accuracy of network embedding algorithms via rich node attribute information
• GraphScale: A Framework to Enable Machine Learning over Billion-node Graphs
• Empirical Comparison of Graph Embeddings for Trust-Based Collaborative Filtering
• Position-Sensing Graph Neural Networks: Proactively Learning Nodes Relative Positions
• Enhanced Single-Cell RNA-seq Embedding through Gene Expression and Data-Driven Gene-Gene Interaction Integration
• NODDLE: Node2vec based deep learning model for link prediction
• Span-core Decomposition for Temporal Networks: Algorithms and Applications
• Refined Graph Encoder Embedding via Self-Training and Latent Community Recovery
• Towards Lightweight and Automated Representation Learning System for Networks
• Block Model Guided Unsupervised Feature Selection
• HUGE: Huge Unsupervised Graph Embeddings with TPUs
• Topological Node2vec: Enhanced Graph Embedding via Persistent Homology
• Understanding the Design Principles of Link Prediction in Directed Settings
• Link Prediction in Bipartite Networks
• DINE: A Framework for Deep Incomplete Network Embedding
• Representation Learning on Large Non-Bipartite Transaction Networks using GraphSAGE
• Block-Approximated Exponential Random Graphs
• ECHO: Encoding Communities via High-order Operators
• RNE: A Scalable Network Embedding for Billion-scale Recommendation
• ${\text{H}}^2\text{TNE}$: Temporal Heterogeneous Information Network Embedding in Hyperbolic Spaces
• Contributions to Representation Learning with Graph Autoencoders and Applications to Music Recommendation
• Context-Aware Interpretable Representations for Retrieval and Graph Convolutional Network Classification
• Constructing Graph Node Embeddings via Discrimination of Similarity Distributions
• Graph Embedding via Diffusion-Wavelets-Based Node Feature Distribution Characterization
• Graph Embedding Augmented Skill Rating System
• Toward Efficient Testing of Graph Neural Networks via Test Input Prioritization
• Distributed-Memory Vertex-Centric Network Embedding for Large-Scale Graphs
• One Node at a Time: Node-Level Network Classification
• Data-Driven Self-Supervised Graph Representation Learning
• RNA-KG v2.0: An RNA-centered Knowledge Graph with Properties
• mQAPViz: A divide-and-conquer multi-objective optimization algorithm to compute large data visualizations
• A Framework of Transferring Structures Across Large-scale Information Networks
• FeatureNorm: L2 Feature Normalization for Dynamic Graph Embedding
• Attributed Graph Modeling with Vertex Replacement Grammars
• Link prediction on multi-relational graphs from an influence propagation perspective