Evaluating similarities between node pairs in a graph is an important task for data analytics and mining. Among various similarity measures proposed in recent years, SimRank is regarded as one of the most influential measures. However, the computation of SimRank is very expensive especially for large graphs. Although pruning technique and random walk based methods were proposed to accelerate the computation, the accuracy of SimRank score is still very low. In this paper, we propose a novel matrix random sampling approach to accelerate computation speed and reduce memory cost. The matrix random sampling technique not only guarantees the sparsity of the involved matrices, but also enhances the precision of estimated SimRank scores. Moreover, we design a fast sparse matrix–matrix multiplication technique which makes the time complexity of single-source query free of the graph size. We further exploit the Steepest Decent technique to accelerate the speed of convergence. The experimental results show our proposed algorithms outperform the state-of-the-art SimRank algorithms.