Abstract Online social networks continue to witness a tremendous growth both in terms of the number of registered users and their mutual interactions. In this paper, we focus on online signed social networks where positive interactions among the users signify friendship or approval, whereas negative interactions indicate antagonism or disapproval. We introduce a novel problem which we call the link label prediction problem: Given the information about signs of certain links in a social network, we want to learn the nature of relationships that exist among the users by predicting the sign, positive or negative, of the remaining links. We propose a matrix factorization based technique MF-LiSP that exhibits strong generalization guarantees. We also investigate the applicability of logistic regression [8] in this setting. Our experiments on Wiki-Vote, Epinions and Slashdot data sets strongly corroborate the efficacy of these approaches.