Random Spanning Trees and the Prediction of Weighted Graphs
Abstract
We show that the mistake bound for predicting the nodes of an arbitrary weighted graph is 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 the optimal mistake bound on any weighted graph. Our algorithm draws a random spanning tree of the original graph and then predicts the nodes of this tree in constant amortized time and linear space. Experiments on real-world datasets show that our method compares well to both global (Perceptron) and local (label-propagation) methods, while being much faster.
Cite
Text
Cesa-Bianchi et al. "Random Spanning Trees and the Prediction of Weighted Graphs." International Conference on Machine Learning, 2010. doi:10.5555/2567709.2502620Markdown
[Cesa-Bianchi et al. "Random Spanning Trees and the Prediction of Weighted Graphs." International Conference on Machine Learning, 2010.](https://mlanthology.org/icml/2010/cesabianchi2010icml-random/) doi:10.5555/2567709.2502620BibTeX
@inproceedings{cesabianchi2010icml-random,
title = {{Random Spanning Trees and the Prediction of Weighted Graphs}},
author = {Cesa-Bianchi, Nicolò and Gentile, Claudio and Vitale, Fabio and Zappella, Giovanni},
booktitle = {International Conference on Machine Learning},
year = {2010},
pages = {175-182},
doi = {10.5555/2567709.2502620},
url = {https://mlanthology.org/icml/2010/cesabianchi2010icml-random/}
}