Graph Learning with Loss-Guided Training
This work addresses the challenge of inefficient training in graph learning for practitioners, though it is incremental as it adapts existing loss-guided methods to a new domain.
The paper tackles the problem of accelerating node embedding methods like DeepWalk by introducing loss-guided training, which dynamically adjusts the training distribution based on example loss, resulting in significant acceleration in training time and computation across multiple datasets.
Classically, ML models trained with stochastic gradient descent (SGD) are designed to minimize the average loss per example and use a distribution of training examples that remains {\em static} in the course of training. Research in recent years demonstrated, empirically and theoretically, that significant acceleration is possible by methods that dynamically adjust the training distribution in the course of training so that training is more focused on examples with higher loss. We explore {\em loss-guided training} in a new domain of node embedding methods pioneered by {\sc DeepWalk}. These methods work with implicit and large set of positive training examples that are generated using random walks on the input graph and therefore are not amenable for typical example selection methods. We propose computationally efficient methods that allow for loss-guided training in this framework. Our empirical evaluation on a rich collection of datasets shows significant acceleration over the baseline static methods, both in terms of total training performed and overall computation.