Lower Order Information Preserved Network Embedding Based on Non-Negative Matrix Decomposition

Abstract

Network embedding has been successfully used for a variety of tasks, e.g., node clustering, community detection, link prediction and evolution analysis on complex networks. For a given network, embedding methods are usually designed based on first-order proximity, second-order proximity, community constraints, etc. However, they are incapable of capturing the structural similarity of nodes. The bridge nodes with small proximity and located in different communities, should be similar in embedding space since they have the same surrounding structure. In this paper, these structural features are referred to as lower-order information, which could reveal and modify the structural similarity of nodes in the embedding space. Specifically, we propose to construct the feature matrix with the lower-order information of the network. In order to effectively fuse the structural features of nodes into embedding space, an intuitive, interpretable and feasible method named LONE-NMF is proposed, which adopts the representation learning framework based on non-negative matrix factorization. It can effectively learn the representation vectors of nodes in the network via preserving the proximity and lower-order information. Moreover, an optimization algorithm is designed for LONE-NMF. Extensive experiments based on clustering and link prediction show that the proposed method achieves significant performance improvement comparing with some baselines. Finally, we validate the principle and advantage of LONE-NMF through a case study.

Publication
Information Sciences