Unifying Skip‑gram and Matrix Factorization for Graph Embedding and Enhancing It with Sparse Matrix Techniques

The article begins by noting that graph models combining representation learning and deep learning have become popular, but constructing task‑specific graph structures from massive data remains difficult, especially in domains like healthcare where semi‑structured medical knowledge graphs provide valuable priors.

It revisits earlier work on skip‑gram models (DeepWalk, LINE, node2vec) and shows, following Tang et al., that these methods are mathematically equivalent to matrix factorization of a graph‑derived co‑occurrence matrix. Detailed derivations for LINE and DeepWalk illustrate how the loss functions can be rewritten as factorized matrix forms.

The paper then introduces the NetMF framework, which treats the factorized matrix as the target for singular value decomposition, and explains how window size influences computational cost and sparsity. For large windows, NetMF approximates the matrix via top‑h eigenvectors to keep the computation tractable.

Building on NetMF, the NetSMF method applies graph sparsification to construct a sparse approximation of the matrix M, followed by random SVD to obtain low‑dimensional embeddings. The algorithm includes edge sampling based on original graph topology and weight computation through path lengths, achieving significant speed‑ups over DeepWalk and NetMF.

The article also discusses practical obstacles when applying graph representation learning, such as ambiguous context in textual data and the need for richer heterogeneous graphs. It highlights GATNE, which learns separate edge embeddings for multiple edge types and combines them with base node embeddings using attention mechanisms, supporting both transductive and inductive settings.

Finally, the paper surveys deep clustering methods for graphs, including DAEGC, which couples an auto‑encoder with attention‑enhanced embeddings, and SDCN, which integrates GCN layers to capture structural information. Both approaches demonstrate that incorporating graph‑aware components improves clustering performance on several benchmark datasets.

In conclusion, unifying skip‑gram models under matrix factorization opens the door to leveraging a broad set of graph‑theoretic tools, while sparse matrix techniques and heterogeneous graph models address scalability and real‑world applicability challenges.