Long non-coding RNAs (lncRNAs) and microRNAs (miRNAs) have been involved in various biological processes. Emerging evidence suggests that the interactions between lncRNAs and miRNAs play an important role in the regulation of genes and the development of many diseases. Due to the limited scale of known lncRNA-miRNA interactions, and expensive time and labor costs for identifying them by biological experiments, more accurate and efficient lncRNA-miRNA interaction computational prediction approach urgently need to be developed. In this work, we proposed a novel computational model, GNMFLMI, to predict lncRNA-miRNA interactions using graph regularized nonnegative matrix factorization. More specifically, the similarities both lncRNA and miRNA are calculated based on known interaction information and their sequence information. Then, the affinity graphs for lncRNAs and miRNAs are constructed using the p-nearest neighbors, respectively. Finally, a graph regularized nonnegative matrix factorization model is developed to accurately infer potential interactions between lncRNAs and miRNAs. To assess the performance of GNMFLMI, five-fold cross-validation experiments are carried out. The AUC values achieved by GNMFLMI on two datasets are 0.9769 and 0.8894, respectively, which outperform the compared methods. In the case studies for lncRNA nonhsat159254.1 and miRNA hsa-mir-544a, 20 and 16 of the top-20 associations predicted by GNMFLMI are confirmed, respectively. Rigorous experimental results demonstrate that GNMFLMI can effectively predict novel lncRNA-miRNA interactions, which can provide guidance for relevant biomedical research. The source code of GNMFLMI is freely available at https://github.com/ haichengyi/GNMFLMI.