For the task of tag-based item recommendations, the underlying tensor model faces several challenges such as high data sparsity and inferring latent factors effectively. To overcome the inherent sparsity issue of tensor models, we propose the graded-relevance interpretation scheme that leverages the tagging data effectively. Unlike the existing schemes, the graded-relevance scheme interprets the tagging data richly, differentiates the non-observed tagging data insightfully, and annotates each entry as one of the "relevant", "likely relevant", "irrelevant", or "indecisive" labels. To infer the latent factors of tensor models correctly to produce the high quality recommendation, we develop a novel learning-to rank method, Go-Rank, that optimizes Graded Average Precision (GAP). Evaluating the proposed method on real-world datasets, we show that the proposed interpretation scheme produces a denser tensor model by revealing "relevant" entries from the previously assumed "irrelevant" entries. Optimizing GAP as the ranking metric, the quality of the recommendations generated by Go-Rank is found superior against the benchmarking methods.