This paper presents a new algorithm to restore the sparse multispectral data acquired by single photon LiDAR. Regarding to its sparsity, the robustness of depth estimation is improved by exploiting the correlations between wavelengths and multi-scale information. Furthermore, the non-local spatial correlations between pixels/patches are learned by the affinity graph and used as prior information to prompt the smoothness for both depth and reflectivity images. To reduce the computational cost, a non-uniform sampling algorithm and clustering strategy are adopted, where flexible sampling points were assigned to reduce the size of the graph while minimizing the loss in details and different spatial clusters can be processed in parallel. Finally, the restoration was achieved by optimizing a cost function which account for both multi-scale information and non-local spatial correlations. The cost function is efficiently solved by ADMM algorithm that present fast convergence. Results on simulated data showed the benefits of the proposed algorithm by comparing with state-of-the-art algorithms, and the fast computation justified the supreme performance.