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. Copyright 2010 by the author(s)/owner(s).

Random spanning trees and the prediction of weighted graphs / N. Cesa-Bianchi, C. Gentile, F. Vitale, G. Zappella - In: Proceedings of the 27th International Conference on Machine LearningMadison : Omnipress, 2010. - ISBN 9781605589077. - pp. 175-182 (( Intervento presentato al 27. convegno International Conference on Machine Learning tenutosi a Haifa, Israel nel 2010.

Random spanning trees and the prediction of weighted graphs

N. Cesa-Bianchi;G. Zappella
2010

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. Copyright 2010 by the author(s)/owner(s).
Settore INF/01 - Informatica
http://shop.omnipress.com/icml2009conferenceproceedingsbook1211-1.aspx
Book Part (author)
File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate

Caricamento pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/2434/154732
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 15
  • ???jsp.display-item.citation.isi??? ND
social impact