Random Spanning Trees and the Prediction of Weighted Graphs

Abstract

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, the optimal number of prediction mistakes can be 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 in expectation the optimal mistake bound on any polynomially connected weighted graph. Our algorithm draws a random spanning tree of the original graph and then predicts the nodes of this tree in constant expected 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 generally faster in practice.

Appeared in ICML 2010

References in corpus (2)

• Active Learning on Trees and Graphs
• Low congestion online routing and an improved mistake bound for online prediction of graph labeling

Cited by in corpus (8)

• Active Learning on Trees and Graphs
• Online Similarity Prediction of Networked Data from Known and Unknown Graphs
• Large-Scale Semi-Supervised Learning via Graph Structure Learning over High-Dense Points
• A Correlation Clustering Approach to Link Classification in Signed Networks -- Full Version --
• A Scalable Multiclass Algorithm for Node Classification
• See the Tree Through the Lines: The Shazoo Algorithm -- Full Version --
• A Linear Time Active Learning Algorithm for Link Classification -- Full Version --
• On Pairwise Clustering with Side Information