Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Random Spanning Trees and the Prediction of Weighted Graphs   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.

0
The categories of this paper are: hep-ph
20
The categories of this paper are: acc-phys
30
The categories of this paper are: q-alg
21
The categories of this paper are: adap-org
31
The categories of this paper are: ao-sci
27
The categories of this paper are: comp-gas
10
The categories of this paper are: q-bio
23
The categories of this paper are: solv-int
36
The categories of this paper are: cmp-lg
35
The categories of this paper are: mtrl-th
25
The categories of this paper are: patt-sol
8
The categories of this paper are: hep-ex
12
The categories of this paper are: nucl-th
15
The categories of this paper are: nucl-ex
26
The categories of this paper are: bayes-an
4
The categories of this paper are: cond-mat