--- Summary --- The authors derive the Probabilistic Watershed: Given an undirected graph with seed nodes, the Probabilistic Watershed is a tractable method for computing marginals over *all seed-separating spanning forests* of nodes being assigned to seeds. 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. counts). --- Comments --- The paper is very clearly written and structured. The math is sound as far as I can see, and the notation is clear and convenient to read. The novel insights on Random Walker and Power Watershed are fundamental in that they offer concise and intuitive interpretations in both cases. I found this paper a pleasure to read. --- Minor Comments --- Typo line 128 denotes --> denote Line 147 "given its entropy" --> Hard to read (what is "it"?) Line 172 ff: For better readability, please introduce this paragraph by a short motivation. (in particular, it would be convenient to see in advance if it can be skipped to read on in line 182) Line 185: Again, it would ease readability here if you could shortly motivate what comes next. --- Post Author Feedback The examples for practical impact are very interesting; It would be great if you could add them to the paper or supplement.

Watershed is a well known and well studied segmentation procedure in graph theory. Over the last 20 years or so, our understanding of graph-based segmentation procedures have improved tremendously. This paper is an excellent contribution with a detailed stochastic approach that provides new interpretation of some links between watershed and other well-known graph-based procedures. Another key contribution is the uncertainty evaluation of the provided segmentation. Finally It shows how probabilistic watershed can provide better results by sampling over a larger set of forests.

The paper's is of theoretical nature and contains no empirical results or evidence to support the effectiveness of the proposed probabilistic watershed algorithm. On the theoretical side, its contribution seems to be limited to indicate equivalence, or bring new interpretation, to exisiting algorithms.