VC-Dimension Based Generalization Bounds for Relational Learning

In one of the most common settings in statistical relational learning (SRL), we are given a single relational structure from which we need to learn a model, and this model is then used to make predictions on previously unseen structures. For example, the global relational structure could correspond to a large social network, with the training data specifying the relationships that hold among a small subset of the users, along with their attributes. Clearly, in order to provide any guarantees on the accuracy of these predictions, we need to make (simplifying) assumptions about how the training and test structures are related. In this paper, we follow the setting from [10, 9], where it is assumed that these structures, which we will call relational examples, are all obtained by sampling domain elements from a larger global structure (uniformly and without replacement).