Random Spanning Trees and the Prediction of Weighted Graphs

Nicolo' Cesa-Bianchi, Claudio Gentile, Fabio Vitale +1

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,…