Graph-based Generalization Bounds for Learning Binary Relations

We investigate the generalizability of learned binary relations: functions that map pairs of instances to a logical indicator. This problem has application in numerous areas of machine learning, such as ranking, entity resolution and link prediction. Our learning framework incorporates an example labeler that, given a sequenceX of n instances and a desired train-ing size m, subsamples m pairs from X ×X without replacement. The challenge in ana-lyzing this learning scenario is that pairwise combinations of random variables are inher-ently dependent, which prevents us from us-ing traditional learning-theoretic arguments. We present a unified, graph-based analysis, which allows us to analyze this dependence using well-known graph identities. We are then able to bound the generalization error of learned binary relations using Rademacher complexity and algorithmic stability. The rate of uniform convergence is partially deter-mined by the labeler’s subsampling process. We thus examine how various assumptions about subsampling affect generalization; un-der a natural random subsampling process, our bounds guarantee Õ(1/ n) uniform con-vergence.