The seeded Watershed algorithm / minimax semi-supervised learning on a graph computes a minimum spanning forest which connects every pixel / unlabeled node to a seed / labeled node. We propose instead to consider all possible spanning forests and calculate, for every node, the probability of sampling a forest connecting a certain seed with that node.

The Probabilistic Watershed is a semi-supervised learning algorithm applied on undirected graphs. Given a set of labeled nodes (seeds), it defines a Gibbs probability distribution over all possible spanning forests disconnecting the seeds. It calculates, for every node, the probability of sampling a forest connecting a certain seed with the considered node. We propose the Directed Probabilistic Watershed, an extension of the Probabilistic Watershed algorithm to directed graphs. Building on the Probabilistic Watershed, we apply the Matrix Tree Theorem for directed graphs and define a Gibbs probability distribution over all incoming directed forests rooted at the seeds. Similar to the undirected case, this turns out to be equivalent to the Directed Random Walker. Furthermore, we show that in the limit case in which the Gibbs distribution has infinitely low temperature, the labeling of the Directed Probabilistic Watershed is equal to the one induced by the incoming directed forest of minimum cost. Finally, for illustration, we compare the empirical performance of the proposed method with other semi-supervised segmentation methods for directed graphs.

Neural Information Processing Systems http://nips.cc/

Neural Information Processing Systems http://nips.cc/

(line 45).

The authors prove that the probabilities they obatin are equivalent to the probabilities yielded by the Random Walker algorithm. The authors state that this result has been shown in the original Random Walker work, yet is little known, and their proof is different and more self-contained, not relying on potential theory. Excitingly, their way of proof yields a novel interpretation of the Random Walker / Probabilistic Watershed probabilities in terms of the triangle equation on effective resistances between graph nodes. Last but not least the authors relate their theory to the Power Watershed, again yielding an exciting new insight, namely that for parameters beta 2 and alpha towards infinity, the latter computes marginals over all seed-separating *maximum* spanning forests (i.e.

Brings new insights to old algorithms accept.