Bias-free hypothesis evaluation in multirelational domains

In machine learning one typically assumes that the true classification of an object depends only on the object itself and given the object, is independent of the classification of other objects. In this case, setting aside a sufficiently large and randomly chosen part of the training data as a test set, the observed sample error on the test set is an unbiased estimator of true error. However, in many application settings, those mainstream approaches to model evaluation might be inappropriate. As pointed out by [2], among others, whenever there is autocorrelation, i.e., whenever the target value of one object depends not only on the object itself, but also on other objects' classifications or information that is shared between objects, observed error on a randomly chosen test set may not be an unbiased estimator anymore. We introduce a sampling technique, generalized subgraph sampling, that avoids a bias in error estimation by establishing the required amount of linked objects in the test set.