Abstract Non-negative Matrix Factorization (NMF) has received considerable attentions in various areas for its psychological and physiological interpretation of naturally occurring data whose representation may be parts-based in the human brain. Despite its good practical performance, one shortcoming of original NMF is that it ignores intrinsic structure of data set. On one hand, samples might be on a manifold and thus one may hope that geometric information can be exploited to improve NMF’s performance. On the other hand, features might correlate with each other, thus conventional L2 distance can not well measure the distance between samples. Although some works have been proposed to solve these problems, rare connects them together. In this paper, we propose a novel method that exploits knowledge in both data manifold and features correlation. We adopt an approximation of Earth Mover’s Distance (EMD) as metric and add a graph regularized term based on EMD to NMF. Furthermore, we propose an efficient multiplicative iteration algorithm to solve it. Our empirical study shows the encouraging results of the proposed algorithm comparing with other NMF methods.