Non-negative matrix factorization (NMF) is an efficient model in learning parts-based data representation. Since the local geometrical structure can be effectively modeled by a nearest neighbor graph, the graph regularized NMF (GNMF) was proposed to make the learned representation more faithfully and better characterize the intrinsic structure of data. However, GNMF shares a similar paradigm with most of existing graph-based learning models which perform learning tasks on a fixed input graph. In this paper, we propose a new Flexible NMF model with adaptively learned Graph regularization (Γ NMΓ G) in which the graph is jointly learned with simultaneous performing the matrix factorization. An efficient iterative method with guaranteed convergence and relative low complexity is developed to optimize the FNMFG objective. Experiments compare FNMFG method with state-of-the-art algorithms and demonstrate its improved performance.