A General View for Network Embedding as Matrix Factorization

We propose a general view that demonstrates the relationship between network embedding approaches and matrix factorization. Unlike previous works that present the equivalence for the approaches from a skip-gram model perspective, we provide a more fundamental connection from an optimization (objective function) perspective. We demonstrate that matrix factorization is equivalent to optimizing two objectives: one is for bringing together the embeddings of similar nodes; the other is for separating the embeddings of distant nodes. The matrix to be factorized has a general form: S - beta.1. The elements of S indicate pairwise node similarities. They can be based on any user-defined similarity/distance measure or learned from random walks on networks. The shift number beta is related to a parameter that balances the two objectives. More importantly, the resulting embeddings are sensitive to beta and we can improve the embeddings by tuning beta. Experiments show that matrix factorization based on a new proposed similarity measure and beta-tuning strategy significantly outperforms existing matrix factorization approaches on a range of benchmark networks.