games [@Bowling2006], predicting proteins that interact with other proteins in bioinformatics [@Yamanishi2004], retrieving documents that are similar to a target document in text mining [@Yang2009], investigating the persons that are friends of each other on social network sites [@Taskar2004], etc. All these examples represent fields of application in which specific machine learning and data mining algorithms have been successfully developed to infer relations from data; pairwise relations, to be more specific.

The typical learning scenario in such situations can be summarized as follows. Given a dataset of known relations between pairs of objects and a feature representation of these objects in terms of variables that might characterize the relations, the goal usually consists of inferring a statistical model that takes two objects as input and predicts whether the relation of interest occurs for these two objects. Moreover, since one aims to discover unknown relations, a good learning algorithm should be able to construct a predictive model that can generalize for unseen data, i.e., pairs of objects for which at least one of the two objects was not used to construct the model. As a result of the transition from predictive models for single objects to pairs of objects, new advanced 