Abstract: In order to effectively capture the potential structure of data and reduce the amount of computation, a recommender system prediction algorithm based on signal sampling reconstruction on undirected weighted graph is proposed. In order to utilize the information carried by unmarked items, users or items and their relationships were modeled as a weighted undirected graph. In order to reconstruct the sampled signal, the problem was approximately modeled as a quadratic unconditional optimization problem in reproducing kernel Hilbert space. In order to reduce the computational complexity, an approximate solution strategy was introduced. The experimental results on two open public databases show that the model significantly improves the prediction accuracy and greatly reduces the computational complexity.