We address the problem of item recommendation in social media sharing systems. We adopt a multi-relational framework capable to integrate different entity types available in the social media system and relations between the entities. We then model different recommendation tasks as weighted random walks in the relational graph. The main contribution of the paper is a novel method for learning the optimal contribution of each relation to a given recommendation task, by minimizing a loss function on the training dataset. We report results of the relation weight learning for two common tasks on the Flickr dataset, tag recommendation for images and contact recommendation for users.