PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Jiezhong Qiu, Yuxiao Dong, Hao Ma, Jian Li, Kuansan Wang, Jie Tang

arXiv:1710.02971v4cs.SIcs.LGstat.ML

TL;DR

Network embedding methods based on skip-gram were effective empirically, but their theoretical mechanisms and relationships to network structure were not well understood. The paper unifies DeepWalk, LINE, PTE, and node2vec as implicit matrix factorizations with closed forms, then introduces NetMF to explicitly factorize these matrices. NetMF achieves consistent improvements over DeepWalk and LINE, including relative improvements of up to 50% in reported experiments.

  • Problem

    Skip-gram-based network embedding methods lacked a unified theoretical account connecting their implicit word-context factorizations to network structure.

  • Method

    The paper derives closed-form implicit matrix factorizations for DeepWalk, LINE, PTE, and node2vec, and proposes NetMF to explicitly factorize the matrices targeted by DeepWalk and LINE.

  • Results

    NetMF’s direct factorization achieves consistent performance improvements over DeepWalk and LINE, with relative improvements of up to 50% in experiments on four networks.

  • Takeaways & Limitations

    The closed forms unify these methods and reveal their relationships with graph Laplacians, providing a theoretical basis for understanding skip-gram-based network representations.

  • Takeaways & Limitations

    Modeling node2vec’s full second-order dynamics is difficult because its transition-probability tensor and stationary distribution are expensive to compute and store.

Abstract

from arXiv · show

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.

1 INTRODUCTION

Network embedding learns compact vertex representations to capture network structure, but the theoretical relationships among skip-gram-based methods remained unclear. This work unifies DeepWalk, LINE, PTE, and node2vec as implicit matrix factorizations and connects their closed forms to graph structure.

  • Network embedding maps each vertex to a low-dimensional vector that captures structural properties for tasks such as label classification and community detection.
  • Skip-gram-based network embedding emerged by treating random-walk vertex paths as sentences and learning latent vertex representations.DeepWalk pioneered this adaptation of word embedding to networks.
  • The theoretical mechanisms and deeper relationships among DeepWalk, LINE, PTE, and node2vec were previously insufficiently understood.The paper also notes that earlier theoretical analysis of DeepWalk was not fully consistent with the original setting.
  • The paper shows that DeepWalk, LINE, PTE, and node2vec perform implicit matrix factorizations with closed-form factorized matrices.These forms expose relationships among the methods and connections with graph Laplacians.
  • LINE is a special case of DeepWalk when the skip-gram context window size T equals 1, while PTE factorizes a joint matrix of multiple networks.
  • NetMF explicitly factorizes DeepWalk’s closed-form matrix and improves over DeepWalk and LINE by up to 50% in experiments on four networks.The method uses the connection between DeepWalk’s implicit matrix and graph Laplacians.

2 THEORETICAL ANALYSIS AND PROOFS

The paper analyzes LINE, PTE, DeepWalk, and node2vec as implicit matrix-factorization methods with closed-form factorized matrices. It derives connections among these methods and characterizes their assumptions, random-walk constructions, and theoretical relationships.

  • 2.1 LINE and PTE: LINE (2nd) is shown to factorize a closed-form matrix derived from edge weights, vertex degrees, and the negative-sampling distribution.The analysis assumes a degree-proportional noise distribution, PN(j) = d_j/vol(G).
  • 2.1 LINE and PTE: PTE extends LINE to heterogeneous text networks by jointly factorizing matrices associated with word-word, document-word, and label-word sub-networks.Non-negative weights α, β, and γ balance the three sub-networks and satisfy α vol(Gww) = β vol(Gdw) = γ vol(Glw).
  • 2.2 DeepWalk: DeepWalk constructs a multiset of vertex-context pairs from random walks and trains skip-gram with negative sampling on that multiset.The context window groups pairs according to their forward and backward random-walk distances.
  • 2.2 DeepWalk: Under connected, undirected, non-bipartite graph assumptions and stationary initialization, DeepWalk’s pair counts and implicit matrix are expressed through random-walk transition probabilities.With long walks, the same characterization holds even when walks start from other distributions.
  • 2.2 DeepWalk: LINE (2nd) is a special case of DeepWalk when the skip-gram context window size is T = 1.This follows by comparing the closed-form matrices derived for the two methods.
  • 2.3 node2vec: node2vec uses an unnormalized transition probability tensor parameterized by p and q, then normalizes it for a second-order random walk.Its analysis gives a closed form, but the paper does not formulate the corresponding matrix form.

3 NetMF: NETWORK EMBEDDING AS MATRIX FACTORIZATION

NetMF analyzes DeepWalk as a closed-form matrix factorization connected to the normalized graph Laplacian, then factorizes an adjusted DeepWalk matrix with SVD. The analysis shows that increasing the context window filters toward a low-rank positive semidefinite representation, while NetMF provides small- and large-window computation strategies.

  • Framework: NetMF unifies the analyzed network embedding methods through closed-form matrix factorization, focusing on DeepWalk because its matrix is more general than LINE's and more efficient than node2vec's.The framework covers LINE, PTE, DeepWalk, and node2vec, while this section studies the DeepWalk matrix for subsequent analysis and computation.
  • Connection to Graph Laplacian: The DeepWalk matrix is related to the normalized graph Laplacian through the eigendecomposition of D^-1/2AD^-1/2 = I − L.The normalized Laplacian has real eigenvalues in [0, 2], and the associated normalized adjacency eigenvalues lie between -1 and 1.
  • Connection to Graph Laplacian: DeepWalk applies a spectral filter to normalized adjacency eigenvalues that favors large positive values, with stronger preference as the window size T increases.As T grows, the filter approximates a low-rank positive semidefinite matrix by retaining large positive eigenvalues.
  • Connection to Graph Laplacian: In the Cora example, the DeepWalk matrix filters out negative and small positive eigenvalues of the normalized adjacency-related matrix.The comparison uses eigenvalue spectra for Cora with T = 10.
  • Empirical Outcome: NetMF improves over DeepWalk and LINE by up to 50% in relative performance across experiments on four networks.The reported experiments use four networks associated with DeepWalk and node2vec.
  • NetMF Algorithms: For small T, NetMF computes the DeepWalk matrix, replaces entries below 1 before taking element-wise logarithms, and obtains embeddings from a rank-d SVD.The replacement avoids log 0 and produces a sparse, consistent version of the logged matrix.
  • NetMF Algorithms: For large T, NetMF approximates the DeepWalk matrix using its low-rank spectral structure and sparse-matrix eigensolvers before applying the same adjustment and SVD pipeline.The large-window method uses only the top-h eigenpairs and provides error bounds for approximating both M and log M′.
  • Limitation: A key computational limitation is that the element-wise logarithm must still be computed explicitly because available tools do not adequately analyze that operator.This remains a drawback even after obtaining a good low-rank approximation of M.

4 EXPERIMENTS

The experiments evaluate NetMF against LINE and DeepWalk on multilabel vertex classification across four network datasets and varying labeled-data ratios. NetMF generally improves predictive performance, especially when labels are sparse, while Wikipedia favors short-range methods; DeepWalk’s sampling approximation remains a limitation.

  • Experimental setup: The evaluation compares NetMF (T = 1 and T = 10) with LINE (2nd) and DeepWalk on multilabel vertex classification across four datasets.The experiments use BlogCatalog, PPI, Wikipedia, and Flickr, with one-vs-rest logistic regression for prediction.
  • Results: NetMF (T = 10) achieves significantly better Micro-F1 and Macro-F1 performance than baseline approaches on BlogCatalog, PPI, and Flickr.The reported improvement holds for both evaluation metrics on these three datasets.
  • Results: On Wikipedia, NetMF (T = 1) performs best on Micro-F1, whereas LINE performs best on Macro-F1.The authors attribute this pattern to Wikipedia’s dense word co-occurrence structure and conclude that short-term dependence is sufficient there.
  • Results: 46.34% and 33.85% are NetMF (T = 1)’s relative gains over LINE on PPI with 10% training data for Micro-F1 and Macro-F1, respectively.With the same setting, NetMF (T = 10) exceeds DeepWalk by 50.71% and 39.16% on the two metrics.
  • Limitation: DeepWalk’s random-walk sampling can leave gaps between exact and empirical vertex-context distributions because real networks are large and practical walks are limited.The authors state that these gaps negatively affect DeepWalk’s performance despite convergence being guaranteed by the law of large numbers.

5 RELATED WORK

Network embedding builds on spectral clustering and social dimension learning, with recent methods using random-walk contexts and skip-gram prediction. Related approaches differ in how they define vertex context, including first-order, second-order, and meta-path walks.

  • Research background: Network embedding follows earlier work in spectral clustering and social dimension learning, including DeepWalk and later methods such as LINE, PTE, and node2vec.These approaches learn low-dimensional representations of network structure for downstream analysis.
  • Context-based methods: DeepWalk, node2vec, and metapath2vec define vertex context using first-order random walks, second-order random walks, and meta-path-based random walks, respectively.Their context-prediction formulation is motivated by skip-gram with negative sampling.

6 CONCLUSION

The work unifies four skip-gram-based network embedding methods through implicit matrix factorizations and introduces NetMF for explicit factorization. Its analysis relies on random-walk convergence arguments, while future work remains for faster approximations and node2vec’s second-order walks.

  • The paper analyzes DeepWalk, LINE, PTE, and node2vec as implicit matrix factorizations with closed-form matrices connected to graph Laplacians.NetMF explicitly factorizes the closed-form matrices that DeepWalk and LINE implicitly approximate and factorize.
  • Future work includes fast approximations for closed-form matrices, computation of node2vec’s second-order random walks, and dynamic or heterogeneous network embedding.These directions are presented as unresolved topics for deepening the understanding of network embedding.
  • The convergence proof models vertex-context occurrences with indicator variables and applies the S.N. Bernstein law of large numbers.The proof uses finite expectations, bounded variances, and covariances that decay with temporal separation.
  • The expected vertex-context occurrence is expressed through the random walk’s stationary distribution and r-step transition probabilities.The proof identifies E[Yj] with a degree- and volume-weighted transition probability before establishing convergence of the sample average.
  • The analysis extends from one sampled vertex sequence to multiple sequences by defining a combined random-variable sequence satisfying the same law-of-large-numbers condition.The resulting sequence supports the same convergence conclusion for the general case N > 1.
Loading 1710.02971v4…