Empirical Risk Minimization and Stochastic Gradient Descent for Relational Data
This work addresses a fundamental gap in prediction methods for relational data, which is important for domains like social networks or bioinformatics, but it appears incremental as it builds on existing graph sampling and optimization techniques.
The authors tackled the problem of extending empirical risk minimization to relational data by defining an empirical risk and obtaining unbiased stochastic gradients using graph sampling theory, and demonstrated its effectiveness in applications like semi-supervised node classification and learning embedding vectors for vertex attributes, with experiments showing the sampling scheme strongly affects performance.
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.