Random spanning trees and the prediction ofweighted graphs.

Nicolò Cesa-Bianchi, Claudio Gentile, Fabio Vitale, Giovanni ZappellaJMLR 2013 · OpenReview

TL;DR

This paper introduces a novel algorithm, WTA, for predicting labels on nodes of weighted graphs. It leverages random spanning trees to achieve near-optimal prediction accuracy with a provably efficient and robust method, outperforming existing approaches in both speed and accuracy on real-world datasets.

What Problem Does This Paper Address?

The paper tackles the challenge of online graph prediction, specifically predicting binary labels for nodes in a weighted graph. In this setting, nodes are presented one by one, and the algorithm must predict their labels sequentially without knowing the full graph structure or labels in advance. This is a crucial problem in many applications where data is naturally represented as a graph (e.g., social networks, biological interactions) and labels need to be inferred dynamically. A key difficulty is that the order of node presentation and label assignments can be adversarial, making it hard to guarantee good performance. Existing methods often struggle with scalability or don't fully exploit the rich information in weighted graphs.

Methods

The core of the paper's contribution lies in the Weighted Tree Algorithm (WTA). WTA operates in two main phases:

  1. Random Spanning Tree Extraction: The algorithm first samples a random spanning tree from the input weighted graph. This is a crucial step as it simplifies the graph structure while preserving essential connectivity information. The paper explores various methods for generating these trees, including those that consider edge weights and those that ignore them.
  2. Tree Linearization and Prediction: The extracted spanning tree is then transformed into a linear structure (a "line graph"). This linearization process, which involves duplicating nodes and carefully re-weighting edges, is key to WTA's efficiency and robustness. Finally, a nearest-neighbor prediction rule is applied on this line graph using a resistance distance metric. This approach allows for predictions in constant expected amortized time per node.

The paper also provides a theoretical framework, showing that the optimal number of prediction mistakes is related to the "cutsize" of a random spanning tree, which is a measure of disagreement in labels across edges. WTA is designed to achieve bounds close to this theoretical optimum.

Datasets

The authors evaluated their algorithm on several real-world datasets:

  • RCV1: Text categorization dataset.
  • USPS: Optical character recognition dataset.
  • KROGAN: Protein-protein interaction network.
  • COMBINED: A combination of three biological datasets.
  • WEBSPAM: A large inter-host link dataset from the Web Spam Challenge.

They generated graphs from RCV1 and USPS using k-NN with different values of k (10 and 100), and binarized multiclass problems for KROGAN and COMBINED.

Key Insights and Ideas

  • Random Spanning Trees as a Regularizer: The paper demonstrates that using a random spanning tree is an effective way to regularize the graph prediction problem. By focusing on a tree structure, the algorithm simplifies the problem while still capturing important connectivity, leading to better performance guarantees.
  • Linearization for Efficiency and Robustness: The novel tree linearization technique is a key innovation. It transforms the tree into a manageable line graph, enabling fast, sequential predictions and making the algorithm robust to noise or perturbations in the input labels.
  • Cutsize as a Measure of Hardness: The paper establishes a theoretical link between the optimal number of prediction mistakes and the "cutsize" of a random spanning tree. This provides a fundamental understanding of the problem's complexity.
  • Weight Exploitation: While some methods ignore edge weights, WTA effectively uses them in both spanning tree generation and the prediction phase, leading to improved accuracy.

Key Results

  • Near-Optimal Performance: WTA achieves prediction mistake bounds that are optimal up to logarithmic factors, closely matching theoretical lower bounds.
  • Efficiency: The algorithm offers a significant speedup, with predictions taking constant expected amortized time per node after the initial spanning tree construction.
  • Robustness: WTA is shown to be robust to label noise, meaning small perturbations in the input labels do not drastically degrade performance.
  • Superiority over Baselines: Experiments show WTA outperforms established methods like the Perceptron algorithm (GPA) and Label Propagation (LABPROP) on various datasets.
  • MST as the Best Spanning Tree: For WTA and GPA, using a Minimum Spanning Tree (MST) generally yielded the best performance, suggesting that prioritizing lighter edges is beneficial.

Limitations and Future Work

  • Slack in Theoretical Bounds: The authors acknowledge a potential slack in their theoretical upper bounds compared to the general lower bound, particularly for unweighted trees with small diameters. Reducing this slack is an open question.
  • Cutsize vs. Weighted Cutsize: The paper uses the unweighted cutsize as a primary measure of hardness. They suggest exploring whether a weighted cutsize or other bias measures might offer a more natural and tighter characterization of the problem's difficulty.
  • Random Spanning Tree Generation Time: While WTA's prediction phase is efficient, the time complexity of generating random spanning trees, especially for weighted graphs, can still be a bottleneck for very large graphs. The paper mentions Wilson's algorithm for unweighted graphs but notes the complexity for weighted cases.
  • Further Exploration of Robustness: The authors suggest further investigating the robustness properties of WTA and exploring other criteria for bias that are robust to small perturbations.

Summary updated

Abstract

We investigate the problem of sequentially predicting the binary labels on the nodes of an arbitrary weighted graph. We show that, under a suitable parametrization of the problem, the optimal number of prediction mistakes can be characterized (up to logarithmic factors) by the cutsize of a random spanning tree of the graph. The cutsize is induced by the unknown adversarial labeling of the graph nodes. In deriving our characterization, we obtain a simple randomized algorithm achieving in expectation the optimal mistake bound on any polynomially connected weighted graph. Our algorithm draws a random spanning tree of the original graph and then predicts the nodes of this tree in constant expected amortized time and linear space. Experiments on real-world data sets show that our method compares well to both global (Perceptron) and local (label propagation) methods, while being generally faster in practice.
BibTeX
@article{cesabianchi2013random,
  author = {Nicolò Cesa-Bianchi and Claudio Gentile and Fabio Vitale and Giovanni Zappella},
  title = {{Random spanning trees and the prediction ofweighted graphs.}},
  journal = {J. Mach. Learn. Res.},
  year = {2013},
  url = {https://openreview.net/forum?id=KDM-svAdbYT},
}

Loading related content...

Figure