Academic
Publications
Random Spanning Trees and the Prediction of Weighted Graphs

Random Spanning Trees and the Prediction of Weighted Graphs,Nicolò Cesa-Bianchi,Claudio Gentile,Fabio Vitale,Giovanni Zappella

Random Spanning Trees and the Prediction of Weighted Graphs   (Citations: 1)
BibTex | RIS | RefWorks Download
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.
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
Sort by: