Equivalence between LINE and Matrix Factorization
This finding provides a theoretical basis for extending and generalizing LINE, which is incremental as it clarifies the underlying mathematical framework of an existing method.
The paper proves that the LINE network embedding method, which preserves local and global structures, is equivalent to matrix factorization for two specific matrices: LINE(1st) factors a matrix based on doubled Pointwise Mutual Information for undirected networks, and LINE(2nd) factors a matrix based on PMI for directed networks.
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.