Graph Learning with Loss-Guided Training

Eliav Buchnik, Edith Cohen

Graph Learning with Loss-Guided Training

Abstract

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 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 loss-guided training in a new domain of node embedding methods pioneered by 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.

Introduction

In the landscape of machine learning, "hard example mining" has long been a staple for accelerating training in domains like computer vision. The intuition is simple: not all training examples are equally informative. Some are mastered quickly, while others—the "hard" examples—require more focus to refine the model's decision boundaries.

However, applying this concept to graph node embeddings (e.g., DeepWalk or Node2Vec) presents a unique challenge. Unlike image datasets with fixed labels, these methods generate an implicit, massive set of training pairs via random walks. Because the number of potential node pairs scales quadratically with the number of nodes, tracking the loss for every possible pair is computationally prohibitive. Consequently, most state-of-the-art graph embedding tools rely on "static" training, where every part of the graph is sampled with equal frequency, regardless of the model's current state of learning.

Methodology: Loss-Guided Random Walks

The proposed approach introduces a meta-algorithm that shifts the focus from individual node pairs to entire random walks. By assigning a "loss score" to candidate walks, the model can prioritize those that are most likely to provide informative gradient updates.

Walk Scoring Functions

The authors propose two primary heuristics for scoring:

  1. $Lscore_{all}$: This calculates the average loss of all positive pairs generated by a complete random walk.
  2. $Lscore_{t'}$: A "fail-fast" heuristic that only evaluates the loss of the first $t'$ edges of a walk. This significantly reduces preprocessing overhead by allowing the algorithm to discard "easy" walks before they are fully generated.

Biased Selection and the Power Parameter

During training, the algorithm generates a pool of candidate walks but only selects a subset for gradient updates. This selection is performed via weighted sampling biased toward higher loss scores. A hyperparameter $p$ (the power parameter) controls the "greediness" of this selection; a higher $p$ focuses more aggressively on the hardest examples.

Empirical Evaluation

The effectiveness of loss-guided training was evaluated across diverse real-world datasets, including Facebook page networks for clustering, citation networks (Cora, Pubmed) for classification, and Protein-Protein Interaction (PPI) graphs for multi-label tasks.

Modularity scores over training epochs for three Facebook datasets (Athletes, Company, Politicians). Loss-guided methods (colored lines) reach peak performance significantly faster than the static DeepWalk baseline (black line).

As shown in the figure above, loss-guided training consistently accelerates the convergence of modularity scores in clustering tasks. On the Facebook datasets, the number of epochs required to reach peak performance was reduced by 13% to 25%.

Micro-F1 score vs. training epochs on the PPI dataset. The loss-guided variants demonstrate a steeper learning curve compared to the baseline, particularly in the middle stages of training.

In classification tasks, such as those performed on the PPI dataset, the acceleration is equally evident. The model spends its computational budget on the "frontiers" of its knowledge—complex boundaries or noisy regions—rather than over-training on well-understood, isolated communities.

Conclusion

Loss-guided training offers a robust framework for accelerating graph learning without sacrificing accuracy. By identifying "hard" walks through efficient prefix scoring, the method achieves overall computational gains of 6% to 20%, even when accounting for the overhead of loss calculation. Future work remains in automating hyperparameter tuning and exploring the applicability of these techniques to Graph Neural Networks (GNNs).

Summary updated

Abstract

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.
BibTeX
@inproceedings{buchnik2020graph,
  author = {Eliav Buchnik and Edith Cohen},
  title = {{Graph Learning with Loss-Guided Training}},
  booktitle = {GRADES-NDA@SIGMOD},
  year = {2020},
  doi = {10.1145/3398682.3400060},
}
Figure