Efficient Online Multiclass Prediction on Graphs via Surrogate Losses

Alexander Rakhlin, Karthik SridharanAISTATS 2017 · OpenReview

Abstract

We develop computationally efficient algorithms for online multi-class prediction. Our construction is based on carefully-chosen data-dependent surrogate loss functions, and the new methods enjoy strong mistake bound guarantees. To illustrate the technique, we study the combinatorial problem of node classification and develop a prediction strategy that is linear-time per round. In contrast, the offline benchmark is NP-hard to compute in general. We demonstrate the empirical performance of the method on several datasets.

Introduction

In online node classification, nodes of a graph are encountered sequentially. For each node, a label must be predicted (e.g., categorizing a blog post as "politics" or "tech") before the true label is revealed. The objective is to minimize the total number of prediction mistakes.

The ideal benchmark for this task is to perform as well as the best possible "smooth" labeling—one where neighboring nodes likely share the same label. However, finding this optimal labeling is an NP-hard combinatorial problem. Previous online approaches often relied on restrictive distributional assumptions or computationally expensive relaxations that were impractical for large-scale social networks or citation graphs. This paper introduces a framework that is both theoretically sound and fast enough for real-world applications.

Methodology

The proposed approach circumvents the computational complexity of traditional methods through two primary techniques:

  1. Surrogate Losses: Instead of directly minimizing the non-convex "zero-one loss" (the mistake count), the algorithm utilizes a convex surrogate loss—specifically, a variant of the hinge loss. The authors prove that minimizing this surrogate provides a rigorous upper bound on the actual number of mistakes made.
  2. Ellipsoidal Relaxations: To incorporate graph structure, the method employs the graph Laplacian, which represents node connectivity. By relaxing the discrete set of possible labelings into a continuous ellipsoid, the authors derive a closed-form solution for prediction scores at each step.

The resulting algorithm achieves $O(n)$ time complexity per round after initial pre-computation, enabling it to scale to massive graphs.

Experimental Evaluation

The authors evaluated the method on four diverse datasets: Political Blogs (1,222 nodes), Citeseer (3,312 nodes), Cora (2,708 nodes), and a noisy MNIST graph (12,000 nodes).

Key Results

In head-to-head tests, the proposed method consistently matched or outperformed established semi-supervised learning algorithms. As shown in the learning curve below, the average error rate of this method decreases more rapidly and stabilizes at a lower level than competing baselines.

Average error over time comparing the proposed method against baselines by Zhu et al. and Belkin et al.

Furthermore, the method demonstrated superior accuracy across all tested datasets, as summarized in the following table:

Accuracy comparison across MNIST, Citeseer, Cora, and Political datasets.

Beyond raw accuracy, the algorithm proved highly robust to hyperparameter selection (specifically the smoothness parameter $\kappa$) and maintained its linear-time efficiency, handling the 12,000-node MNIST graph with ease.

Discussion and Future Work

This work bridges the gap between theoretical mistake bounds and practical efficiency by leveraging the geometry of the graph Laplacian. While the current framework provides strong guarantees, it assumes a fixed graph structure. Future research could explore extending these surrogate loss techniques to evolving graphs where edges are added or removed over time. Additionally, incorporating node-specific features (such as text or image data) directly into the surrogate framework remains a promising direction for further improving classification performance.

Summary updated

Abstract

We develop computationally efficient algorithms for online multi-class prediction. Our construction is based on carefully-chosen data-dependent surrogate loss functions, and the new methods enjoy strong mistake bound guarantees. To illustrate the technique, we study the combinatorial problem of node classification and develop a prediction strategy that is linear-time per round. In contrast, the offline benchmark is NP-hard to compute in general. We demonstrate the empirical performance of the method on several datasets.
BibTeX
@inproceedings{rakhlin2017efficient,
  author = {Alexander Rakhlin and Karthik Sridharan},
  title = {{Efficient Online Multiclass Prediction on Graphs via Surrogate Losses}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2017},
  url = {https://openreview.net/forum?id=GvlVpmZPWTf},
}
Figure