Random spanning trees and the prediction of weighted graphs

We show that the mistake bound for predict-ing 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 ran-dom spanning tree of the original graph and then predicts the nodes of this tree in con-stant amortized time and linear space. Ex-periments on real-world datasets show that our method compares well to both global (Perceptron) and local (label-propagation) methods, while being much faster. 1