Source-linked AI summary
LINE: Large-scale Information Network Embedding
Jian Tang, Meng Qu, Mingzhe Wang, Ming Zhang, Jun Yan, Qiaozhu Mei
TL;DR
Embedding massive information networks is useful but difficult because existing graph-embedding methods often do not scale to networks with millions of nodes. LINE preserves first- and second-order structure across arbitrary network types with efficient edge sampling, and experiments report effective, efficient embeddings at million-node and billion-edge scale.
Problem
Existing graph-embedding methods often do not scale to real-world information networks with millions or billions of nodes, despite embeddings’ usefulness for network analysis and applications.
Method
LINE preserves first- and second-order proximities for undirected, directed, and weighted networks, using edge sampling to optimize its objective efficiently.
Results
Experiments on varied real-world networks report that LINE is effective and efficient, scaling to millions of vertices and billions of edges.
Takeaways & Limitations
LINE provides a scalable embedding approach for arbitrary information networks while preserving complementary local and global network structure.
Takeaways & Limitations
When a new vertex has no observed connections, LINE requires other information such as vertex text, which the paper leaves for future work.
Abstract
from arXiv · showhide
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.
1. INTRODUCTION
The paper introduces LINE for embedding very large, arbitrary information networks while preserving first- and second-order proximity. It also proposes edge sampling to improve optimization and evaluates LINE’s effectiveness and efficiency on real-world networks.
- Motivation and challenges: Real-world information networks can contain millions of nodes and billions of edges, making many existing graph embedding algorithms difficult to scale.The Twitter followee-follower network had 175 million active users and around twenty billion edges in 2012.
- Evaluation: Experiments on language, social, and citation networks evaluate LINE through word analogy, text classification, and node classification tasks.The reported results support the effectiveness and efficiency of LINE against competitive baselines.
- Model and objective: LINE embeds undirected, directed, weighted, or unweighted information networks and scales to millions of nodes.Its objective preserves both first-order proximity from observed links and second-order proximity from shared neighborhoods.
- Optimization: LINE’s edge-sampling algorithm addresses limitations of classical stochastic gradient descent and improves inference effectiveness and efficiency.The sampling process keeps the objective function unchanged while preventing edge weights from affecting gradients.
2. RELATED WORK
The related work includes classical graph-embedding methods, graph factorization, and DeepWalk. These approaches have limitations involving scalability, preservation of global network structure, or clarity about preserved network properties.
- Classical graph embedding: Classical methods such as MDS, IsoMap, LLE, and Laplacian Eigenmap construct affinity graphs from data features and typically require solving leading eigenvectors.Examples include K-nearest-neighbor affinity graphs embedded into low-dimensional spaces.
- Graph factorization: Graph factorization obtains low-dimensional embeddings through affinity-matrix factorization optimized with stochastic gradient descent, but its objective is not designed for networks.Consequently, it does not necessarily preserve global network structure.
- DeepWalk: DeepWalk uses truncated random walks for social-network embedding but lacks a clear objective articulating which network properties are preserved.DeepWalk emphasizes second-order proximity, whereas LINE preserves both first-order and second-order proximities.
- Empirical comparison: The proposed model is empirically compared with these methods on various real-world networks.The comparison is reported in Section 5.
3. PROBLEM DEFINITION
Large-scale information network embedding represents each vertex in a low-dimensional space while preserving both first-order local pairwise proximity and second-order neighborhood-structure similarity. The problem accommodates directed or undirected networks with nonnegative binary or real-valued edge weights.
- Network Definition: An information network is G = (V, E), with vertices as data objects and weighted ordered-pair edges representing relationships.For undirected graphs, edge direction and weights are symmetric; for directed graphs, they need not be.
- Network Definition: The framework covers directed or undirected networks whose edge weights are binary or any nonnegative real values.Examples include citation, social, and co-occurrence networks; negative weights are excluded.
- Proximity Definitions: First-order proximity is the local pairwise proximity encoded by edge weight wuv, while unobserved pairs have proximity 0.This captures directly linked vertex relationships.
- Proximity Definitions: First-order proximity alone is insufficient because sparse networks contain missing links between intrinsically similar vertices.Second-order proximity addresses this by comparing vertices’ neighborhood network structures through their proximity vectors pu and pv.
- Embedding Objective: The embedding learns fG: V → R^d with d ≪ |V| while preserving both first-order and second-order proximities.This formalizes the large-scale information network embedding objective.
4. LINE: LARGE-SCALE INFORMATION NETWORK EMBEDDING
LINE is designed for large information networks by preserving first-order and second-order proximity while supporting directed, undirected, and weighted edges. It combines separately trained proximity embeddings and uses negative sampling with alias-table edge sampling for efficient optimization whose overall time complexity is linear in the number of edges.
- LINE targets embeddings that preserve first-order and second-order proximity, scale to millions of vertices and billions of edges, and support directed, undirected, and weighted networks.
- LINE preserves the two proximities separately and concatenates their learned embeddings for each vertex; joint optimization is identified as future work.
- First-order proximity captures local pairwise relationships but applies only to undirected graphs, whereas second-order proximity compares vertices through their distributions over shared contexts and supports directed and undirected graphs.
- Negative sampling replaces the expensive summation over all vertices with observed-edge and noise-edge terms, using K negative edges drawn from Pn(v) ∝ d_v.
- When edge weights have high variance, their gradient scales diverge and make learning-rate selection difficult; unfolding weighted edges avoids this but substantially increases memory requirements.
- O(dK|E|) is LINE’s overall time complexity because alias-table sampling takes O(1), each optimization step takes O(dK), and the number of steps is usually proportional to |E|.
5. EXPERIMENTS
The experiments evaluate LINE’s effectiveness and efficiency on several large-scale real-world networks spanning language, social, and citation domains.
- The experiments assess LINE’s effectiveness and efficiency.
- LINE is evaluated on several large-scale real-world networks.
- The evaluation covers a language network, two social networks, and two citation networks.
5.1 Experiment Setup
The experiments evaluate LINE on language, social, and citation networks against scalable graph-embedding methods. They compare edge-sampled LINE variants with direct stochastic-gradient optimization and establish common embedding and optimization settings.
- Datasets: Experiments use an English Wikipedia word co-occurrence network, Flickr and Youtube social networks, and two types of citation networks.Wikipedia words co-occur within 5-word sliding windows, and words occurring fewer than 5 times are filtered out.
- Compared methods: LINE is compared with scalable methods including graph factorization, DeepWalk, and direct LINE-SGD optimization.Classical methods such as MDS, IsoMap, and Laplacian eigenmap are excluded because they cannot handle networks at this scale.
- Compared methods: The evaluated variants include first- and second-order LINE and LINE-SGD, plus a concatenated LINE (1st+2nd) representation.First-order variants apply only to undirected graphs, whereas second-order variants apply to both undirected and directed graphs.
- Implementation settings: All methods use mini-batch size 1, with learning rate ρ0 = 0.025 and ρt = ρ0(1−t/T); embedding dimensions are 200 for the language network and 128 for other networks.The supplied settings also specify T = 10 billion for LINE(1st) and LINE(2nd), T = 20 billion for GF, and final vector normalization to ||w||2 = 1.
5.2 Quantitative Results
Across language and social-network evaluations, LINE—especially its second-order or combined proximities—generally outperforms competing embedding methods, while remaining efficient at million-node scale. The experiments also show that edge sampling improves LINE over direct SGD and that second-order proximity better captures semantic similarity.
- Language Network: LINE(2nd) outperforms all other methods, including graph embedding methods and SkipGram, on Wikipedia word analogy.The result indicates that second-order proximity better captures word semantics than first-order proximity.
- Language Network: Less than 3 hours are required for LINE(1st) and LINE(2nd) to process a network with 2 million nodes and a billion edges on one machine.Both variants are at least 10% faster than graph factorization, while DeepWalk is five times slower.
- Language Network: On Wikipedia page classification, edge-sampling optimization substantially improves LINE over direct SGD, while LINE(2nd) surpasses LINE(1st) and is slightly better than graph factorization.Graph factorization outperforms DeepWalk because DeepWalk ignores edge weights, whereas LINE-SGDs suffer from divergent edge weights.
- Social Networks: LINE(1st+2nd) significantly outperforms all other methods on Flickr multi-label classification.The evaluation samples different percentages of vertices for training, averages results over 10 runs, and uses the five most popular communities as categories.
- Social Networks: On a reconstructed social network, GF, LINE(1st), and LINE(2nd) all improve, with LINE(2nd) outperforming DeepWalk in most cases.LINE(1st+2nd) changes little relative to the original network, suggesting that combining proximities already works well there.
5.3 Network Layouts
This section evaluates network embeddings for visualizing a DBLP co-author network in two dimensions. LINE(2nd) produces a meaningful layout, with same-community nodes distributed closer together than under competing approaches.
- Network visualization: Network embedding is applied to create meaningful two-dimensional visualizations of information networks.The visualization task is motivated as an important application of network embedding.
- Network visualization: The study constructs a DBLP co-author network from conferences spanning data mining, machine learning, and computer vision.Authors with degree less than 3 are excluded before mapping the network into a low-dimensional space and then into 2-D with t-SNE.
- Network visualization: Graph factorization fails to cluster authors from the same communities, while DeepWalk improves but tightly clusters many different-community authors in the center.The center concentration mostly involves high-degree vertices.
- Network visualization: LINE(2nd) performs quite well and generates a meaningful layout, with same-color nodes distributed closer together.The figure compares layouts produced from different embedding approaches after t-SNE mapping.
5.4 Performance w.r.t. Network Sparsity
The section analyzes how network sparsity affects LINE(1st) and LINE(2nd) using social networks. Performance generally improves with vertex degree, while LINE(2nd) outperforms LINE(1st) on the original Youtube network except in an unspecified case.
- Performance w.r.t. Network Sparsity: The study evaluates LINE(1st) and LINE(2nd) under varying network sparsity using social networks as examples.Different percentages of links are sampled from Flickr to construct networks with varying sparsity.
- Performance w.r.t. Network Sparsity: Flickr is selected because it is much denser than Youtube, enabling evaluation across different percentages of links.Figure 3(a) reports performance with respect to the percentage of Flickr links.
- Performance w.r.t. Network Sparsity: Overall, model performance increases as vertex degree increases across groups on the original and reconstructed Youtube networks.Vertices are grouped by degrees (0, 1], [3],, [7] [12], [13, 30], and [31, +∞).
- Performance w.r.t. Network Sparsity: On the original Youtube network, LINE(2nd) outperforms LINE(1st) except for an unspecified case.The supplied passage does not identify the exception.
5.5 Parameter Sensitivity
The section examines how embedding dimension and optimization sample count affect performance on the reconstructed YouTube network, comparing LINE variants and DeepWalk. Performance for LINE(1st) and LINE(2nd) declines when the dimension becomes too large.
- Parameter Sensitivity: The study evaluates performance against embedding dimension d on the reconstructed YouTube network.Figure 4(a) reports the LINE model’s performance as d varies.
- Parameter Sensitivity: Performance for LINE(1st) and LINE(2nd) drops when the dimension becomes too large.This result is shown in Figure 4(a).
- Parameter Sensitivity: The study compares LINE and DeepWalk as the number of optimization samples increases.Figure 4(b) reports their results with respect to the number of samples during optimization.
5.6 Scalability
The LINE model scales effectively with edge sampling and asynchronous stochastic gradient descent across multiple threads. On YouTube, speedup is close to linear while classification performance remains stable during parallel updates.
- 5.6 Scalability: The scalability evaluation uses edge sampling and asynchronous stochastic gradient descent with multiple optimization threads.The method is assessed on the YouTube dataset.
- 5.6 Scalability: On YouTube, speedup with increasing thread count is quite close to linear.This result is shown in Fig. 5(a).
- 5.6 Scalability: Classification performance remains stable when multiple threads update the model.This result is shown in Fig. 5(b).
6. CONCLUSION
LINE is a scalable network embedding model for networks with millions of vertices and billions of edges. Its objective preserves complementary first- and second-order proximities, while efficient edge sampling addresses stochastic-gradient limitations on weighted edges without sacrificing efficiency.
- Scalability: LINE scales to networks with millions of vertices and billions of edges.The paper presents LINE as a model that can easily scale to these network sizes.
- Network structure: Its carefully designed objective functions preserve complementary first-order and second-order proximities.The two proximity types are described as complementary.
- Inference: An efficient edge-sampling method addresses stochastic gradient descent’s limitation on weighted edges without compromising efficiency.The method is proposed for model inference and is characterized as both efficient and effective.