  Empirical risk minimization is the main tool for prediction problems, but its
extension to relational data remains unsolved. We solve this problem using
recent ideas from graph sampling theory to (i) define an empirical risk for
relational data and (ii) obtain stochastic gradients for this empirical risk
that are automatically unbiased. This is achieved by considering the method by
which data is sampled from a graph as an explicit component of model design. By
integrating fast implementations of graph sampling schemes with standard
automatic differentiation tools, we provide an efficient turnkey solver for the
risk minimization problem. We establish basic theoretical properties of the
procedure. Finally, we demonstrate relational ERM with application to two
non-standard problems: one-stage training for semi-supervised node
classification, and learning embedding vectors for vertex attributes.
Experiments confirm that the turnkey inference procedure is effective in
practice, and that the sampling scheme used for model specification has a
strong effect on model performance. Code is available at
https://github.com/wooden-spoon/relational-ERM.
