Directed Probabilistic Watershed
Year: 2022

Abstract:
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.

heading: 1 Introduction
text: In the last years, machine learning has experienced a great boost thanks to the large quantity of available data and increasing accessibility of less expensive and more powerful processing capacities. However, the acquisition of labeled data is still laborious in some applications like computer-aided diagnosis or drug discovery. Semi-supervised learning is the subfield of machine learning that utilizes both labeled and unlabeled data. It permits exploiting the large amount of unlabeled data available in many use cases jointly with frequently smaller sets of labeled data. When data is encoded as a network, graph-based semi-supervised learning aims to assign a label or class to each of the nodes of a network based on its topology and a given set of labeled nodes / seeds. Graph-based semi-supervised learning has been applied in multiple domains like computer vision [6, 15, 17], NLP [2, 28, 31], social networks [1, 45] and biomedical science[24]. Most graph-based semi-supervised learning algorithms focus on undirected weighted graphs [5, 36], though directed graphs appear naturally in many cases like in k-Nearest Neighbors graphs or citation and recommendation networks among others. Instances of methods proposed for directed graphs are [9, 11, 42, 48, 49].
Recently, [12] proposed the transductive graph-based semi-supervised learning algorithm Probabilistic Watershed (ProbWS). It envisages a Gibbs distribution over the labeled nodes separating forests (forests whose trees contain a unique labeled node) that span a weighted undirected graph. The probability of each forest is proportional to its weight. By means of the Matrix Tree Theorem [19, 40], the ProbWS computes the probability of sampling a seed separating forest such that a query node is connected to a single labeled node / seed. This approach turns out to be equivalent computationally and by result to the Random Walker / Harmonic energy minimization [3, 15, 47, 50].
The Matrix Tree Theorem [19, 40] has been generalized to directed graphs [25]. We propose an extension of the ProbWS, the “Directed Probabilistic Watershed" (DProbWS), that can be applied
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
to directed graphs. Instead of considering seed separating spanning forests, we deal with incoming directed forests rooted at the seed nodes (see Figure 1). We analyze the DProbWS from a theoretical point of view and generalize the results presented in [12] to directed graphs. Building on the arguments used in the original ProbWS paper, we
• analytically compute the probability that a graph node is assigned to a particular seed in an ensemble of Gibbs distributed incoming directed spanning forests rooted at the seeds,
• demonstrate the equivalence of the Directed Probabilistic Watershed and the directed version of the Random Walker presented in [15],
• propose a natural extension of the Power Watershed [6] to directed graphs, • run an illustrative experiment to show the empirical performance of the Directed Probabilistic
Watershed and compare it with other semi-supervised transductive methods.

heading: 1.1 Related work
text: Semi-supervised learning is an important subfield of machine learning due to is ability to exploit both labeled and unlabeled data [41]. If data is represented as a graph, graph based semi-supervised learning exploits, in addition to the labeled samples, the topology of the graph to infer the class of the unlabeled nodes. Undirected graphs have received more attention in this field than the directed ones [5, 36]. Nonetheless, there have been methods proposed for directed graphs. In [48, 49] the labels are inferred by minimizing a regularized function that forces highly connected subgraphs to have the same label. The paper [42] builds a symmetric pairwise similarity via co-linkage analysis from the directed graph in order to apply algorithms for undirected graphs. The work presented in [11] proposes a method based on game theory, where the game’s Nash equilibrium defines the labeling of the data. Related to our work by the use of absorbing random walks is the one proposed in [9]. Their algorithm assigns the label of the seed that maximizes the accumulated expected number of visits from the unlabeled query node before being absorbed by an artificially added metanode. We, instead,
prove that the DProbWS turns out to assign the label of the seed that maximizes the probability of absorption of a random walker.
Our method extends the Probabilistic Watershed (ProbWS) [12], which, in turn, is based on the Watershed algorithm [7]. The ProbWS paper established a link between the Watershed [7] and the Random Walker [3, 15, 47, 50]. Another such connection was made by the Power Watershed paper [6]. We extend these relations to the directed graph framework.
We smooth the combinatorial minimum spanning in-forest via entropic regularization. More specifically, we consider a Gibbs distribution over all spanning in-forests, as was proposed in the original ProbWS paper [12]. Entropic regularization has been applied in other situations like the randomized shortest path framework [14, 20] or optimal transport [8]. If applied in conjunction with deep networks, it allows end-to-end training [32].
The Matrix Tree Theorem (MTT) is key to the theory developed in our work. The directed version of the MTT [25] allows us to compute in closed form the weight of a set of incoming forests. The MTT has been also applied in NLP [22], biology [38] and network analysis [37, 39]. A generalization of the MTT, the Matrix Forest Theorem (MFT), was used by [4] to define a distance between the nodes of a graph. Similar to our approach, [34] defines a Gibbs distribution over the forests using the MFT.

heading: 2 Background

heading: 2.1 Notation and terminology
text: In this section, we introduce the main definitions and notation used in the paper. Most of them have been borrowed from [12, 25]. Let G = (V,E,w, c) be a directed graph where V denotes the set of nodes, E the set of edges and w and c are functions that assign a weight w(e) ∈ R≥0 and a cost c(e) ∈ R to each edge e ∈ E. The edge e = (i, j) indicates that there is a directed edge from i to j. If (i, j) /∈ E, we set c ( (i, j) ) =∞ and w ( (i, j) ) = 0. The set S = {s1, s2} ⊂ V will denote the set of seed / labeled nodes and U = V \S the unlabeled ones. In order to ease the exposition we only consider the 2-seed scenario, although the method can be generalized to the n-seed scenario. We will use the terms seed and labeled node interchangeably.
Definition 1. Let t = (Vt, Et) be a graph then we say that it is an incoming directed spanning tree rooted at r ∈ Vt (in-tree for short) if: 1) every vertex u 6= r has one and only one outgoing edge; 2) the root node r does not have any outgoing edges; 3) t does not have directed cycles, i.e., there does not exist a directed path in t such that the initial and final vertex are the same. Note that condition 3), in conjunction with the other conditions, implies that no cycles (directed or undirected) will be formed.
Equivalently, one can define an in-tree as a graph in which, for any vertex u ∈ Vt there is exactly one directed path from u to the root r, and the root does not have any out-going edges.1 Note that an in-tree becomes a tree in the classical sense if the directions of the edges are ignored. We say that an in-tree is spanning on G = (V,E) if t is a subgraph of G and Vt = V . The set of spanning in-trees of G rooted at r will be denoted by T −→r .
Analogously, the set F−→v−→u represents the set of 2-in-trees spanning forests rooted at u and v, i.e., the spanning graphs of G consisting of two disjoint in-trees, such that u and v are the respective roots of the in-trees. Furthermore, if we consider a third node q, we define F−→v−→u ,q ⊆ F
−→v−→u , as the set of all 2-in-trees spanning forests where q is connected to u by a directed path. In order to shorten the notation we will refer to 2-in-trees spanning forests simply as 2-in-forests or in-forests.
We define the weight of an arbitrary graph (e.g. in-forests)) as the product of the weights of all its edges, w(G) = ∏ e∈E w(e). The weight of a set of graphs, w({Gi}ni=0) is the sum of the weights of the graphsGi. In a similar manner, we define the cost of a graph as the sum of the costs of all its edges, c(G) = ∑ e∈E c(e). As in the Probabilistic Watershed [12], we consider w(e) = exp(−µc(e)), µ ≥ 0, which will be a consequence of the definition of a Gibbs distribution over the 2-in-forests in F−→v−→u . Thus, a low edge-cost corresponds to a large edge-weight, and a minimum edge-cost spanning
1One can define analogously an outgoing tree (out-tree) rooted at r as a tree where there is exactly one directed path from the root r to any other node, and the root does not have any incoming edges.
in-forest (mSF) is equivalent to a maximum edge-weight spanning in-forest (MSF). Depending on the context, the abbreviations mSF and MSF will be also used for the undirected versions of the minimum/maximum spanning forests. Via the Directed Matrix Tree Theorem [25], we aim to compute the weight of the set of the 2-in-forests rooted at the seeds. The theorem makes use of the out-Laplacian matrix which we define next. Definition 2. Given a weighted directed graph G = (V,E,w) we define the out-Laplacian of G as
L := D −A>, (1) where A ∈ R|V |×|V | is the vertex-adjacency matrix of G represented entry-wise as Aij = w ( (i, j) ) and D denotes the diagonal matrix defined as Dii = ∑ j∈V Aij , i.e., Dii is the out-degree of vertex i.2 For brevity, we will refer to the out-Laplacian just as Laplacian. For any v ∈ V , L[v] will stand for the Laplacian after removing the row and column indexed by v.

heading: 2.2 Matrix Tree Theorem
text: Theorem 2.1 (MTTdir, [25]). For any edge-weighted directed graph G with an arbitrary fixed node r ∈ V the weight of the set of incoming directed spanning trees rooted at r, w(T −→r ), is equal to3
w(T −→r ) := ∑ t∈T −→r w(t) = ∑ t∈T −→r ∏ e∈Et w(e) = det(L[r]).
Note that Theorem 2.1 generalizes the original Matrix Tree Theorem [19, 40] if we consider an undirected graph as a directed graph with both directions present for each edge. In this case, any spanning tree in the undirected graph can be interpreted as an in-tree rooted at an arbitrary root r once the direction of the edges has been set appropriately. Hence, for an undirected graph the choice of the root r is irrelevant and we retrieve the original MTT.
We propose to follow the approach taken in [12], but with the generalization of the Matrix Tree Theorem to directed graphs and thus obtain a directed version of the ProbWS.

heading: 2.3 Random Walker and Power Watershed
text: In this section, we summarize the Random Walker [15] and Power Watershed [6], two semi-supervised graph-based algorithms which are directly connected to the Probabilistic Watershed. Both algorithms consider an undirected graph, G, with a set of seeds S = {s1, s2}, i.e., labeled nodes. The Random Walker paper [15] addresses the following problem: What is the probability that a random walker starting at node q reaches seed s1 before reaching seed s2? The solution to this question can be obtained by solving the combinatorial Dirichlet problem, which consists of finding the minimizer of
1 2 x>Lx = 1 2 ∑ e={u,v}∈E w(e)(xu − xv)2, s.t. xs1 = 1, xs2 = 0, (2)
where L denotes the undirected Laplacian of G. The minimizer of equation (2) is the solution of the following linear system
LUx si U = −B > si , (3)
where xsiU represents the probability that the unlabeled nodes in U are absorbed by si, LU is the square submatrix of L indexed by the elements in U and B>si is the row si of L without the seeds.
The Power Watershed generalizes the framework of the Random Walker and minimizes the following objective function ∑
e={u,v}∈E
wα(e)(xu − xv)β , s.t. xs1 = 1, xs2 = 0, (4)
2Analagously, the in-Laplacian is defined as Lin = Din − A, where Din is the diagonal matrix with the in-degrees of the nodes.
3The weight of the out-trees can be calculated using the in-Laplacian instead of the out-Laplacian.
for α, β ≥ 0. For instance, α = 1 and β = 2 define the Random Walker’s objective function. The Power Watershed analyzes the case α → ∞ and β = 2, and boils down to computing a mSF (minimum cost Spanning Forest) and applying the Random Walker in the plateaus (connected subgraphs with constant edge weight), resolving the ambiguity of which mSF is sampled when there is more than one.
The generalization of these algorithms to directed graphs is not straightforward if one takes the objective function approach. Solving (2) directly is equivalent to solve the problem with an undirected graph whose edge-weights are equal to the sum of the edge-weights in both directions of the original directed graph. The method proposed in [35] generalizes the combinatorial Dirichlet problem (2) by interpreting the graph as an electrical network with diodes. This approach is not equivalent to the random walk on a directed graph anymore.
The Random Walker can also be generalized to the directed case if we use the intuitive approach instead, i.e., we consider the probability of a random walker (constrained to follow the directions of the edges) being absorbed by a certain seed. In the supplemental material, we give a proof of how these probabilities can be computed in the directed case. We demonstrate that the solution of the linear system (3) with the Laplacian transposed provides the desired probabilities. In section 5, we show how the Power Watershed can be generalized to directed graphs by means of the DProbWS.

heading: 2.4 Probabilistic Watershed review
text: The Probabilistic Watershed (ProbWS) [12] is based on the Watershed algorithm. The Watershed algorithm calculates a minimum cost spanning forest, mSF, such that the seeds belong to different components [7]. A query node inherits the label of the seed to which it is connected in the mSF. The ProbWS instead, considers all possible seed-separating spanning forests. It defines a Gibbs probability distribution over the forests and analytically computes, for every node, the probability of sampling a forest connecting a certain seed with that node via the application of the Matrix Tree Theorem (for undirected graphs).
In [12] it was shown that the ProbWS turns out to be equivalent to the Random Walker algorithm proposed in [15]. Additionally, it was shown that the Power Watershed potentials [6] were given by the ProbWS probabilities when the latter is restricted to mSFs instead of all spanning forests. This restriction manifests when the entropy of the Gibbs distribution of forests is minimized.
In this work, we extend the ProbWS framework to directed graphs and call it Directed Probabilistic Wasterhsed. In this case, the spanning forests considered are formed by in-forests rooted at the seeds, i.e., directed trees with a unique path from every node to the seed. Inspired by [12], we define a Gibbs Probability distribution over the in-forests and we apply the Matrix Tree Theorem for directed graphs to compute the probability of sampling a forest connecting a certain seed with a query node in closed-form. Next, we demonstrate the equivalence to the Directed Random Walker and finally we propose an extension of the Power Watershed for directed graphs.

heading: 3 Directed Probabilistic Watershed

heading: 3.1 Gibbs probability distribution
text: As in [12], we define a Gibbs probability distribution over 2-in-forests with given entropy J , such that the 2-in-forests with a lower cost have a higher probability mass. Formally, the 2-in-forests are sampled from the distribution which minimizes
min P ∑ f∈F
−→s2−→s1
P (f)c(f), s.t. ∑ f∈F
−→s2−→s1
P (f) = 1 and H(P ) = J, (5)
where H(P ) is the entropy of P . The lower the entropy, the more probability mass is given to the 2-in-forests of lowest cost. The minimizing distribution is the Gibbs distribution ([see 43, 3.2]):
P (f) = exp (−µc(f))∑
f ′∈F −→s2−→s1
exp (−µc(f ′)) =
∏ e∈Ef exp(−µc(e))∑
f ′∈F −→s2−→s1
∏ e′∈Ef′ exp(−µc(e′)) = w(f)∑ f ′∈F
−→s2−→s1
w(f ′) , (6)
where µ can be interpreted as the inverse temperature of the Gibbs distribution. The parameter µ implicitly determines the entropy. A higher µ (lower temperature) implies a lower entropy. Equation (6) motivates our choice of edge weights w(e) = exp(−µc(e)). Definition 3 (Probabilities of the Directed Probabilistic Watershed). Given two seeds s1 and s2 and a query node q, we define the Directed Probabilistic Watershed’s probability that q and s1 have the same label as the probability of sampling a 2-in-forest from F
−→s2−→s1 that connects q to s1 by a directed
path, i.e., they belong to the same in-tree rooted at s1: P (q ∼ s1) := ∑
f∈F −→s2−→s1,q
P (f) = ∑
f∈F −→s2−→s1,q
w(f) / ∑ f ′∈F
−→s2−→s1
w(f ′) = w ( F −→s2−→s1,q )/ w ( F −→s2−→s1 ) . (7)
The Directed Probabilistic Watershed (DProbWS) takes all spanning 2-in-forests into account according to their cost (see Figure1). The resulting assignment probability of each node provides an uncertainty measure. Assigning each node to the seed for which it has the highest probability can yield a labeling different from the in-forest with highest individual probability, the mSF. Remark 3.1. Note that the probability given by the DProbWS is well defined if and only if w ( F −→s2−→s1 ) 6= 0, that is if and only if there exists at least one in-forest rooted at the seeds. As far as any node is connected by a directed path to at least one of the seeds, such an in-forest will exist. If the seeds were not reachable from a node q, this node would have no connection with the seeds and therefore we could not infer any label. These nodes are termed zero-knowledge nodes. We can still use the proposed method by removing all nodes in the zero-knowledge components [30]. In the remaining we will assume w ( F −→s2−→s1 ) 6= 0.
Remark 3.2. Note that the DProbWS probabilities have been based on the concept of incoming forests. The same reasoning can be extended for outgoing forests just by reversing the edge directions.

heading: 3.2 Computation of the Directed Probabilistic Watershed probabilities
text: In this section, we explain how to compute the probabilities defined by the DProbWS. While for undirected graphs it is possible to compute w(Fs2s1 ) as a difference of the weight of the set of spanning trees of the graph G and the weight of the set of spanning trees of G after adding an edge connecting the seeds, this is not possible for w(Fs2s1,q).
4 In [12], w(Fs2s1,q) is obtained by solving a linear system involving w(Fs2s1 ), w(F q s2) and w(F q s1). In contrast to the undirected case, we can bypass the auxiliary linear system due to the directions of the edges which restrict the number of possible directed forests. This permits us to express w(F
−→s2−→s1 ) and w(F −→s2−→s1,q ) in terms of the weight of
the set of in-trees of an augmented graph as it is shown in the following lemma. Lemma 3.3. Let G = (V,E,w) be a directed graph. Given s1, s2, q ∈ V , define the graphs Ḡ1 = (V,E ∪ (s2, s1), w̄1) and Ḡ2 = (V,E ∪ (s2, q), w̄2) where w̄1(e) = w̄2(e) = w(e) ∀e ∈ E and w̄1 ( (s2, s1) ) = w̄2 ( (s2, q) ) = 1. Then
a) w ( F −→s2−→s1 ) = w ( T −→s1 Ḡ1 ) − w ( T −→s1 G ) b) w ( F −→s2−→s1,q ) = w ( T −→s1 Ḡ2 ) − w ( T −→s1 G ) .
4Fs2s1,q , F s2 s1 , F q s2 and F q s1 are equivalents to F −→s2−→s1,q , F −→s2−→s1 , F −→q −→s2 and F −→q −→s1 but defined in an undirected graph.
Proof: We will only prove a). Note that w ( T −→s1 Ḡ1 ) − w ( T −→s1 G ) is the weight of all the spanning trees of Ḡ1 rooted at s1 containing the edge (s2, s1). It is easy to see that for any f ∈ F −→s2−→s1 , there exists a unique t ∈ T −→s1 Ḡ1 containing (s2, s1) such that w(t) = w(f). Indeed, if we add the edge (s2, s1) to f we obtain a tree t ∈ T −→s1 Ḡ1 since for every node in V , there exists a unique path to s1 (see Figure 2b). Conversely, any tree in t ∈ T −→s1 Ḡ1 containing the edge (s2, s1) will be transformed into a forest f ∈ F −→s2−→s1 after the removal of the edge of (s2, s1). Due to w̄1 ( (s2, s1) ) = 1 the equality of weights w(f) = w(t) follows. The argument for b) is analogous to the previous case (see Figure 2c).
The following result (Lemma 3.4) provides a closed formula for w ( F −→s2−→s1 ) and w ( F −→s2−→s1,q ) in terms of the in-trees of G rooted at the seeds. The proof makes use of the MTTdir (Theorem 2.1), Lemma 3.3 and the well-known Determinant Lemma [16] (Theorem A.1 appendix). Due to its technicality, we defer the proof to the supplemental material.
Lemma 3.4. Let G = (V,E,w) be a directed graph. Let l−1,[v]ij represent the entry ij of the matrix( L[v] )−1 for any v ∈ V . Given s1, s2 and q:
a) w ( F −→s2−→s1 ) = w(T −→s1)l−1,[s1]s2s2 = w(T −→s2)l−1,[s2]s1s1 , b) w ( F −→s2−→s1,q ) = w(T −→s1)(l−1,[s1]s2s2 − l −1,[s1] s2q ).
As a consequence of Lemma 3.4, we can conveniently find a closed form for the probabilities of the DProbWS (Definition 3): Theorem 3.5. The Directed Probabilistic Watershed probabilities are equal to
Pr(q ∼ s1) = l −1,[s1] s2s2 − l −1,[s1] s2q
l −1,[s1] s2s2
and Pr(q ∼ s2) = l −1,[s1] s2q
l −1,[s1] s2s2
,
or equivalently
Pr(q ∼ s2) = l −1,[s2] s1s1 − l −1,[s2] s1q
l −1,[s2] s1s1
and Pr(q ∼ s1) = l −1,[s2] s1q
l −1,[s2] s1s1
.
Our discussion was constrained to the case of two seeds only to ease our explanation. We can reduce the case of multiple seeds per label to the two seed case by merging all nodes seeded with the same label. Similarly, the case of more than two labels can be reduced to the two label scenario by using a “one versus all strategy": We choose one label and merge the seeds of other labels into one unique seed. In both cases we might add multiple edges between node pairs. While having formulated our arguments for simple graphs, they are also valid for multigraphs by the same arguments as in [12].

heading: 4 Equivalence of DProbWS and the Directed Random Walker
text: Resembling the ProbWS equivalence with the Random Walker, the DProbWS also turns out to be equivalent to the directed version of the Random Walker. Although multiple references exist on how to compute the absorbing probabilities of a random walker in terms of the Laplacian matrix for undirected graphs [13, 15], we could not find any suitable reference for the directed case.5 We sketch how the absorbing probabilities can be obtained for the directed case in terms of the Laplacian matrix and refer to the supplemental material for a complete derivation. Theorem 4.1. The probability, xs1q , that a random walker on a directed graph starting at node q first reaches s1 before reaching s2 is given by the solution of the following linear system
L>Ux s1 U = − [ B>1 ] s1 , (8)
where xsiU represents the probability that the nodes inU are absorbed by si, LU is the square submatrix of L indexed by the elements in U and [ B>1 ] s1
is the column s1 of L without the entries indexed by the seeds.
5However, there exist closed formulas to compute the absorbing probabilities of Markov chains in terms of the fundamental matrix [18].
Proof sketch: Let P denote the transition probability matrix defined by the absorbing random walker. We note that the probability of being absorbed by s1 at q can be obtained by computing the entry (q, s) of Pn when n tends to infinity, i.e., xs1q = limn→∞ [P
n]qs. By expressing the transition matrix in terms of the Laplacian, we find a closed formula of the matrix Pn by induction. By taking the limit to infinity, we obtain the desired result. See the supplemental material for further details.
Remark 4.2. Note that (8) is the transposed version of the linear system solved by the undirected Random Walker and equivalently the ProbWS (3), i.e., (LU ) yU = −B>1 . Since [12, 15] consider an undirected graph ( L>U ) = LU , the transposition becomes irrelevant in the undirected case.
The next theorem states the equivalence between the DProbWS and the Directed Random Walker. The proof is analogous to Theorem 4.1 in [12] and we replicate the proof in the supplemental material.
Theorem 4.3. The probability, xs1q , that a random walker on a directed graph starting at node q first reaches s1 before reaching s2 is equal to the Directed Probabilistic Watershed’s probability (Definition 3)
xs1q = P (q ∼ s1).
The equivalence stated by Theorem 4.3 combined with Theorem 4.1 implies that in order to obtain the DProbWS probabilities defined in Theorem 3.5, it is just necessary to solve a linear system for each seed node (see Algorithm 1), as it is the case for the Random Walker algorithm.
Algorithm 1: DProbWS Input: G = (V,E,w), seeds Output: x // DProbWS probabilities
1 U = V \ seeds // Unlabeled nodes 2 L=outLaplacian(G) 3 LU = L[U ;U ] // squared submatrix of L indexed by the unlabeled nodes 4 for s ∈ seeds do 5 Bs = L[U ; s] // s column of L restricted to unlabeled nodes 6 x[U ; s]=solve(L>U ,−Bs) // Solves the linear system L>U ∗ xsU = −Bs

heading: 5 Directed Power Watershed
text: In the ProbWS paper [12], it was proven that the Power Watershed [6] is equivalent to applying the ProbWS restricted to the minimum cost spanning forests. This restriction corresponds to the case of a Gibbs distribution of minimal entropy over the forests. In this section, we will prove the analogous result for the DProbWS: When the entropy of the Gibbs distribution over the directed in-forests (3.1) is minimal, then DProbWS is restricted to the minimum cost spanning in-forests (mSF). This permits us to define a natural extension of the Power Watershed to directed graphs.
In Section 3.1, we defined the weight of an edge e as w(e) = exp(−µc(e)), where c(e) was the edge-cost and µ implicitly determined the entropy of the 2-in-forest distribution. When µ→∞, the distribution will have minimal entropy. Consequently, only for minimum cost spanning in-forests, mSFs (or analogously the maximum weight spanning in-forests, MSFs) the limit does not yield a zero probability, so that only they will be considered in the sampling. The proof can be found in the supplemental material.
Theorem 5.1. Given two seeds s1 and s2. Let further wmax := maxf∈F−→s2−→s1 w(f). If the entropy of the Gibbs distribution over the in-forests is minimized (6), then
xs1q = ∣∣∣{f ∈ F−→s2−→s1,q : w(f) = wmax}∣∣∣∣∣∣{f ∈ F−→s2−→s1 : w(f) = wmax}∣∣∣ .

heading: 6 Experiments
text: Although our work has been motivated from a theoretical perspective, we run an illustrative experiment6 to show the performance of the DProbWS on node classification. Given a graph with some labeled nodes, we infer the label of the rest of nodes. k-Nearest Neighbors (kNN) graphs are often used in practice. Due to its asymmetric nature, they can be regarded as directed graphs. We construct kNN graphs, with k = 5, from the UCI datasets [10] Digits [44] and 20Newsgroups[23]. Additionally we consider the Email-EUnetwork [26, 27, 46], the Cora network[29] and CiteseerX network[33]. We compare the DProbWS with the methods exposed in [9, 11, 49] referred as ARW, GTG and LLUD respectively. More details about the datasets, the comparison methods and the construction of the graphs can be found in the supplemental material. Due to the high sparsity of the Cora and CiteseerX networks, many of the nodes are zero-knowledge nodes and therefore its label can not be inferred (see Remark 3.1). To remedy this, we make use of the teleporting random walker (TRW) as a replacement of the natural one, in the same way it is applied in [49] (see supplemental material). The methods ARWtrw and DprobWStrw will refer to the versions that make use of the TRW. To evaluate the methods we use the accuracy (number of correctly labeled nodes divided by the total number of nodes). In the computation of the accuracy, we also include the zero-knowledge nodes. Inspired by [9], we sample a certain fraction r of all nodes from each class uniformly as seeds. In Figure 3, we show the average accuracy over 20 runs for each of the r values between 0.1 and 0.9. We observe that our method obtains comparable empirical results sometimes outperforming all competing methods.

heading: 7 Conclusion
text: In this work, we presented an extension of the Probabilistic Watershed algorithm [12] that can be applied to directed graphs.
Following the rationale exposed in the Probabilistic Watershed article [12], we defined a Gibbs distribution over all the directed spanning in-forests rooted at the seeds of a directed graph (Definition 3). We also demonstrated, using the directed version of the Matrix Tree Theorem [25], that the Directed Probabilistic Watershed is computationally and also by result equivalent to the Directed Random Walker as in the case for the undirected version. Finally, we showed that when the entropy of the
6Code publicly available at https://github.com/hci-unihd/Directed_Probabilistic_ Watershed.git
Gibbs distribution is minimized, we obtain an extension of the Power Watershed potentials [6] to directed graphs.
In the original Probabilistic Watershed paper [12] it was showed that the effective resistance distance [21] triangle inequality gap of the triangle given by the two seeds and the query node is proportional to the probabilities of the Random Walker / ProbWS. In contrast, we have not been able to prove that the probabilities defined by the DProbWS are proportional to the triangle inequality gap of the effective resistance or any other distance in the directed setting. However, we conjecture that there may exist a distance / dissimilarity on the directed graph such that the DProbWS probability is proportional to the triangle inequality defined by the seeds and the query node. This conjecture is left for future work.

heading: 8 Broader impact
text: Our work has been motivated by a theoretical understanding of already existing algorithms. The speculation of a broader impact on this kind of works is therefore less applicable. Nonetheless, we believe that the extension of the Probabilistic Watershed to directed graphs may enrich the graphbased semi-supervised learning field, where less effort has been invested in the directed framework. Furthermore, although we believe that the Directed Random Walker extension presented here must be known, we have not found any reference applying it. By delving into the relations between the spanning in-forests and the Directed Random Walker, we expect that a better understanding of the algorithm is gained and also show the community that such extension for the directed setting exists.
From a practical point of view, the application of the Directed Probabilistic Watershed / Directed Random Walker used in conjunction with other machine learning technology may be used for many applications, both good and bad. In general, any progress on semi-supervised learning will have these same consequences.
Acknowledgments and Disclosure of Funding
This work is supported by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) under Germany’s Excellence Strategy EXC 2181/1 - 390900948 (the Heidelberg STRUCTURES Excellence Cluster).

Review summaries:
This is a very interesting manuscript and an enjoyable read. Essentially, it extends random walks on graphs which perform probabilistic watersheds to random walks on directed graphs which perform directed probabilistic watershed. This is not a trivial extension and is hence a significant contribution - if correct. The caveat is necessary since it will be difficult for any conference reviewer to find the time needed to verify the result.

Suppose we have a weighted directed graph with 2 (or more) nodes designated as "seeds" (call them 0 and 1), and we want to assign a "score" to each node depending on its proximity to seed 0 relative to seed 1. This is a sub-routine that can be used for some semi-supervised learning tasks: for example, think of the nodes as images of cats and dogs, and the two seeds as one image of each type whose classification is known; the goal is to classify the remaining images.  This paper proposes a natural method for assigning a "score" to each node in the above setup. The method is based on sampling a random forest from a certain Gibbs measure. This is proven to be equivalent to the following more intuitive interpretation: imagine starting a random walk at some node q, where the transition probabilities depend in a natural way on the directed edge weights; the "score" assigned to node q is the probability that this random walk reaches seed 1 before reaching seed 0. It is shown that these probabilities can be computed in closed form using the directed matrix tree theorem, so there is no need to actually simulate the random walk. All of this generalizes to the case where there are more than 2 seeds, in which case each node gets assigned a probability distribution over the seeds.  In the case of an undirected graph, the results of this paper were already known and called the "Probabilistic Watershed algorithm" (NeurIPS 2019). This paper provides the natural generalization to directed graphs.  The paper includes some experiments on three different datasets, including classifying images of digits 0-9. To construct the graph, each image is connected to its 5 nearest neighbors (in some metric), with a weight depending on the distance. A fraction r of the nodes are chosen at random to have their labels revealed (these are the "seeds"). The experiments show that the new method seems to perform a bit better than the prior work [9], particularly on the digits dataset.

This paper proposes an extension of a previous graph-based method for semi-supervised learning. Specifically, the proposed method builds upon the probabilistic watershed algorithm, which is a transductive graph-based algorithm for semi-supervised classification, based on building "separating forests" (i.e., in which each tree contains a single labeled node) and defining a Gibbs distribution on this set of forests.  The main contribution of the paper is a generalization of this method to directed graphs, and showing a couple of theoretical results related to the proposed generalization.

The paper proposes a semi-supervised learning algorithm for segmenting directed graphs - obtaining extensions to several previously proposed methods for segmenting undirected graphs. The authors' build on  the 2019 Probabilistic Watershed (ProbWS) paper [12], a graph segmentation algorithm, to construct the directed graph extension. The author's use the Matrix Tree Theorem (MTT), obtaining a Gibbs distribution characterization that they prove is equivalent to the Directed Random Walker (DRW) image segmentation algorithm [15], in analogy to the undirected case studied in [12].  analytical computations of probabilities. They then obtain a directed version of the Power Watershed (PW) graph partitioning algorithm [6]. A numerical study is performed to illustrate and compare the directed ProbWS approach.