Current depth map sensing technologies capture depth maps at low spatial resolution, rendering serious problems in various applications. In this paper, we propose a single depth map super-resolution method that combines the advantages of model-based methods and deep learning approaches. Specifically, we formulate a linear inverse problem which we solve by introducing a graph Laplacian regularizer. The regularization approach promotes smoothness and preserves the structural details of the observed depth map. We construct the graph Laplacian matrix by deploying latent features obtained from a pretrained deep learning model. The problem is solved with the Alternating Direction Method of Multipliers (ADMM). Experimental results show that the proposed approach outperforms existing optimization-based and deep learning solutions.