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:
- 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.
- 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.
Furthermore, the method demonstrated superior accuracy across all tested datasets, as summarized in the following table:
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