Equivalence between LINE and Matrix Factorization
  LINE [1], as an efficient network embedding method, has shown its
effectiveness in dealing with large-scale undirected, directed, and/or weighted
networks. Particularly, it proposes to preserve both the local structure
(represented by First-order Proximity) and global structure (represented by
Second-order Proximity) of the network. In this study, we prove that LINE with
these two proximities (LINE(1st) and LINE(2nd)) are actually factoring two
different matrices separately. Specifically, LINE(1st) is factoring a matrix M
(1), whose entries are the doubled Pointwise Mutual Information (PMI) of vertex
pairs in undirected networks, shifted by a constant. LINE(2nd) is factoring a
matrix M (2), whose entries are the PMI of vertex and context pairs in directed
networks, shifted by a constant. We hope this finding would provide a basis for
further extensions and generalizations of LINE.
