Directed Probabilistic Watershed
Authors: Enrique Fita Sanmartín
Sebastian Damrich
Fred A Hamprecht
Venue: NeurIPS 2021 Poster (2021)
Keywords: Directed Graph
Matrix Tree Theorem
Semi-Supervised Learning
Watershed
Random Walker

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.

Directed Probabilistic Watershed
Enrique Fita Sanmartín, Sebastian Damrich, Fred A. Hamprecht HCI/WWR Heidelberg University, 69120 Heidelberg, Germany (enrique. fita. sttmartinn sebastian. aabaastiaandmmrichh.... damrich, fred. hamprecht) @iwr uni www.umi-heiidllerg..de
Abstract
The Probabilistic Watershed is a semi- sumii-upeeeised learning algorithm applied on undirected graphs. Given a set of labeled nodes (seeds), it defines a Gibbs prob- ability distribution over all possible spanning forests disconnecting the seeds. It calculates, for every node, the probability of sampling 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 Gibbs probability distribution over all incoming directed forests rooted at the seeds. Similar the undirected case, this turns out to be equivalent to the Directed Random Walker. Furthermore, show that in the limit case in which the Gibbs distribution has infinitely low temperature, the labeling of the Directed Probabilistic Watershed is equal the induced by the incoming directed forest minimum cost. Finally, for illustration, we compare the empirical performance of the proposed method with other semi-supervised segmentation methods for directed graphs.
Introduction
In the last years, machine learning has experienced 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-aidee diagnosis or drug discovery. Semi-supervised learning the subfield of machine learning that utilizes both labeled and unlabeled data. It permits exploiting the large amount of unlabeled data available many use cases jointly with frequently smaller sets labeled data. When data encoded as a network, graph-based semi-supervised learning aims assign label or class to each of the nodes of network based on its topology and given set labeled nodes / seeds. Graph-based
cupessupee learning has been applied in multiple domains like computer vision [6] [5] 17), NLP [2] 28 31],
social networks [I] [55 and biomedical science 24). Most graph-based semi-supervised learning algorithms focus undirected weighted graphs [ 36), though directed graphs appear naturally in
many cases like k-Nearest Neighbors graphs or citation and recommendation networks among
others. Instances of methods proposed for directed graphs are 99
48 49].
Recently, 12 proposed the transductive graph-baseee based cumi-supereieed learning algorithm Probabilistic Watershed (ProbWS). It envisages 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 seed separating forest such that query node is connected to single labeled node / seed. This approach turns out be equivalent computationally and by result to the Random Walker Harmonic energy minimization 3
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 (NcurIPS 2021).

---

0.10
0.00
0.6
0.65
1.00
0.37
0.48
0.00k
Figure 1: The DProbWS computes the expected seed assignment of every node for Gibbs distribution over all exponentially many spanning in-forests in closed-form. It thus avoids the winner-takes-all behaviour of the minimum cost spanning in-forest (mSF). (Top right) Two-seeded directed graph with edge costs represented by the widths of the arrows. (Bottom left) The mSF and other, higher cost in-forests. The mSF assigns the query node to 81. Other in-forests of low cost might however induce different labelings. (Top left) We therefore consider Gibbs distribution over all spanning in-forests with respect to their cost (see equation (6)) Each green bar corresponds to the cost of one of the 60 possible spanning in-forests. (Bottom right) DProbWS probabilities for assigning a node to 82. The dashed lines indicate the cut of the assignment. Query q is now assigned to $2- Considering distribution over all spanning in-forests gives uncertainty measure and can yield a different assignment from the mSF's. contrast to the 60 forests in this toy graph, for real-life graphs the number of in-forests increases exponentially with the number of edges and nodes.
to directed graphs. Instead of considering seed separating spanning forests, we deal with incoming directed forests rooted at the seed nodes (see Figure [p. We analyze the DProbWS from theoretical point of view and generalize the results presented in [2] to directed graphs. Building on the arguments used in the original ProbWS paper,
analytically compute the probability that graph node is assigned to a particular seed in an ensemble of Gibbs distributed incoming directed spanning forests rooted the seeds,
demonstrate the equivalence of the Directed Probabilistic Watershed and the directed version the Random Walker presented in [15].
propose a natural extension of the Power Watershed 6 directed graphs,
illustrative experiment show the empirical performance of the Directed Probabilistic Watershed and compare with other semi-supervised transductive methods.
1.1 Related work
Semi-supervised learning is important subfield of machine learning due ability exploit both labeled and unlabeled data [41]. If data is represented as a graph, graph based semi-supervised learning exploits, in addition 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
(6). Nonetheless, there have been methods proposed for directed graphs. In [48 49 the labels are inferred by minimizing regularized function that forces highly connected subgraphs to have the same label. The paper [42] builds symmetric pairwise similarity via co-linkage analysis from the directed graph in order to apply algorithms for undirected graphs. The work presented in [I]] proposes 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 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) 122 which, in turn, is based on the
Watershed algorithm [7]. The ProbWS paper established link between the Watershed (7] and the
Random Walker [3 [5 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 specifi- cally, we consider Gibbs distribution over all spanning in-forests, was proposed in the original ProbWSS paper [1].. Entropic regularization has been applied in other situations like the random- ized shortest path framework [14 20 optimal transport [8]. If applied in conjunction with deep
networks, it allows end-to-end training
(22
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 [9]. A generalization of the MTT, the Matrix Forest Theorem (MFT), was used by 4 to define a distance between the nodes of graph. Similar to our approach, (34] defines Gibbs distribution over the forests using the MFT.
2 Background
2.1 Notation and terminology
In this section, we introduce the main definitions and notation used in the paper. Most of them have been borrowed from I2 25). Let G (V, E, w. c) be directed graph where V denotes the set of nodes, E the set of edges and w and are functions that assign a weight w(e) E R20 and cost c(e) E R to each edge E E. The edge e = (i.j) indicates that there is directed edge from i j. and w (i..)) = O. The set S = {s1, C V will denote the set
If (i. & E, we set (((. of seed labeled nodes and U V 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 (Vi E,) be graph then say that it is an incoming directed spanning tree rooted at r E Vi (in-tree for short) if: 1) every vertex u # r has one and only one outgoing edge; 2) the root node r does not have any outgoing edges: 3) does not have directed cycles, i.e., there does not exist a directed path in such that the initial and final vertex are the same. Note that condition 3), in conjunction with the other conditions, implies that cycles (directed undirected) will be formed.
Equivalently, one can define an in-tree as graph in which, for any vertex E V. there is exactly one directed path from u to the root r, and the root does not have any out-going edges 11 Note that an in-tree becomes tree in the classical sense if the directions of the edges are ignored. We say that an in-tree is spanning on = (V, ) if t is a subgraph of G and V = V. The set of spanning in-trees of G rooted at r will be denoted by T
Analogously, the set F3 represents the set of 2-in-trees spanning forests rooted at u and v, i.c., the spanning graphs of G consisting of two disjoint in in-trees, such that and are the respective roots of the in-trees. Furthermore, if we consider a third node q, define F3 C FE as the set of all 2-in-trees spanning forests where q is connected 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)= = Ieeg w(e). The weight of set of graphs, w w[{G, )= is the sum of the weights of the graphs G.. In similar manner, we define the cost of a graph as the sum of the costs of all its edges, cGG) Eesg c(e). As in the Probabilistic Watershed [12]. we consider w(e) = exp(-uc(e))
O, which will be a consequence of the definition of a Gibbs distribution over the 2-in-forests in Thus, a low edge-cost corresponds to a large eeigh, and a minimum edge-cost spanning
'One can define analogously an outgoing tree (out-tree) rooted at as a tree where there is exactly one directed path from the root r any other node, and the root does not have any incoming edges.
3

---

in-forest (mSF) is equivalent to maximum adge-weight spanning in-forest (MSF). Depending on the context, the abbreviations mSF and MSF will be also used for the undirected versions of the minimun/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
where A E R is the vertex-adjacency matrix of G represented entry-wise A.; w (i.,)) and D denotes the diagonal matrix defined as D;: = Σjev Aij, i.e., Ds: is the out out-degree of vertex For brevity, we will refer to the out- out-Laplacian just as Laplacian. For any V, L will stand for the Laplacian after removing the row and column indexed by
2.2 Matrix Tree Theorem
Theorem 2.1 (MTTdir, (25). For any edge-weightee directed graph G with an arbitrary fixed node r E V the weight of the set of incoming directed spanning trees rooted r, w(T is equal to
w(T
II wle) (L) IET LET CEE.
Σ w(1)=
Σ
Note that Theorem 2. 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. this case, any spanning tree in the undirected graph can be interpreted an in-tree rooted an arbitrary root once the direction the edges has been set appropriately. Hence, for an undirected graph the choice of the root is irrelevant and retrieve the original MTT.
We propose to follow the approach taken [12. but with the generalization of the Matrix Tree Theorem to directed graphs and thus obtain a directed version of the ProbWS.
2.3 Random Walker and Power Watershed
In this section, we summarize the Random Walker 1. 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
{81, 82), i.e. labeled nodes.
The Random Walker paper [15 addresses the following problem: What is the probability that random walker starting at node q reaches seed s before reaching seed 82? The solution this question can be obtained by solving the combinatorial Dirichlet problem, which consists of finding the minimizer of
1 2
L
Σ (U.N)EE
w(e)(a N.)2 s.t. Usi 1, 3sz 0,
where L denotes the undirected Laplacian of G. The minimizer of equation 2 is the solution of the following linear system
Lya -
where zt represents the probability that the unlabeled nodes in U are absorbed by s, Lu is the square submatrix of L indexed by the elements in U and B,, the row s; of L without the seeds.
The Power Watershed generalizes the framework of the Random Walker and minimizes the following objective function
wh - 22) s.t. Ls. = 1, Tea = 0,
(4)
2 AAnalagously, the in-Laplacian is defined Lin Din A. where Din the diagonal matrix with in-degrees the nodes.
"The weight of the out-trees be calculated using the in in-laplaainn instead of the Lat-Lapnn

---

for 8 2 0. For instance. a 1 and 3 = 2 define the Random Walker's objective function. The Power Watershed analyzes the case - 2o and
and boils down to computing 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 the sum of the edge-weights 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 not equivalent to the random walk on a directed graph anymore.
The Random Walker can also be generalized the directed case if we 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 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 33) with the Laplacian transposed provides the desired probabilities. In section [ we show how the Power Watershed can be generalized to directed graphs by means of the DProbWS.
2.4 Probabilistic Watershed review
The Probabilistic Watershed (ProbWS) [2] is based on the Watershed algorithm. The Watershed algorithm calculates a minimum cost spanning forest, mSF, such that the seeds belong to different components 77]- 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 forest connecting a certain seed with that node via the application of the Matrix Tree Theorem (for undirected graphs).
In [2] it was shown that the ProbWS turns out to be equivalent to the Random Walker algorithm proposed in [13]. Additionally, it 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 ProbWSS framework to directed graphs and call Directed Probabilistic Wasterhsed. In this case, the spanning forests considered are formed by in-forests rooted at the seeds, ie.. directed trees with 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 query node in closed-form. Next, we demonstrate the equivalence to the Directed Random Walker and finally propose an extension of the Power Watershed for directed graphs.
3 Directed Probabilistic Watershed
3.1 Gibbs probability distribution
As in 112,, we define 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())()) s.t.
Σ P()=1 and H(P) = J, FEF
(5)
FEF
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 ([see43] 3.2]):
exp (-po(s))
I exp(-uc(e)
w(J)
P()) Σ P exp (=p(())()") Σ E HEEE, exp(-ue(e')) Eperg w(f')
(6)
5

---

(a) f E F
RI. C
(b) T
(c) E T
to spanning in-tree in G1 and G2 as defined Transformation of into an in-tree E T after adding the edge (s2, $1) (thick edge). (2c Transformation f into an in-tree E To after adding the edge (#2. q) (thick edge).
Figure 2: Procedure to transform an in-forest in F si.9
F
in Lemma 3.3 2a In-forest f
F
-
where μr can be interpreted as the inverse temperature of the Gibbs distribution. The parameter implicitly determines the entropy. higher j (lower temperature) implies a lower entropy. Equation (6) motivates our choice of edge weights w(e) = exp(-pc(e))
Definition (Probabilities of the Directed Probabilistic Watershed). Given two seeds $1 and 82 and query node we define the Directed Probabilistic Watershed's probability that and $1 have the same label the probability of sampling 2-in-forest from F that connects q 81 by directed path, i.e., they belong to the same in-tree rooted at 81:
P(a~ (1a~8)) 81)
Σ P()
Σ w(n)
Σ w(f)) - PE
F
81.9
FE
SE
PINN
The Directed Probabilistic Watershed (DProbWSS) takes all spanning 2-in-forests into account ac- cording to their cost (see ). The resulting assignment probability of each node provides an uncertainty measure. Assigning each node to the seed for which has the highest probability can yield labeling different from the in-forest with highest individual probability, the mSF.
Remark 3.1. Note that the probability given by the DProbWS well defined if and only 0. that is if and only if there exists least in-forest rooted at the seeds. As far as any node is connected by directed path to at least one of the seeds, such an in-forest will exist. If 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 gero-knowledge components [30]. In the remaining will assume
reachable from node q. this node would have no connection with the seeds
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.
3.2 Computation of the Directed Probabilistic Watershed probabilities
In this section, we explain how to compute the probabilities defined by the DProbWS. While for undirected graphs it is possible to compute w(FF)) 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(Fss $1.0 In [12, w(F+ ) is obtained by solving a linear system involving w(Fss), w(F2 82) ) and w(FY) ). 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 and w (F in terms of the weight of the set of in-trees of an augmented graph as it is shown in the following lemma.
s1.g)
Lemma 3.3. Let G (V, E, w) be directed graph. Given 31, s2, V. define the graphs G = (V, EUEUR (s2, 81), (1) and G2 = (V, E (82, q), (2) where to (e) = (z(e) = w(e) Ve e E
and w1 (52, $1)) = W2 ((22 = 1. Then
a) F
Te.
T
b)
F
(T..)
$1.4
Fot 5i.q a. Fo2 F2 and Fq equivalents to F "T.8"
F F and 7 but defined in undirected graph.

---

(T is the weight of all the spanning trees of Gi rooted at 81 containing the edge (s2, 51). ). It is easy to see that for any f F there exists unique t T containing (1) such that w(t) w: w(f)) Indeed, if we add the edge (s2, $1) to we obtain a tree TH since for every node V. there exists unique path to $1 (see Figure 2b). Conversely, any tree in t E TGi containing the edge ($2, 81) will be transformed into a forest S F after the removal of the edge of (*2, 81). Due to Wi ((82, .1)) = 1 the equality of weights w(f) wtt) follows. The argument for b) is analogous to the previous case (see Figure 2
Proof: We will only prove a). Note that w (TG)
The following result (Lemma 3.4 provides a closed formula for w
and w the in-trees of G rooted at the seeds. The proof makes use of the MiTdir (Theorem 2.1 Lemma 3.3 and the well-known Determinant Lemma [16] (Theorem A.I appendix). Due to its technicality, we defer the proof the supplemental material.
in terms of
Lemma 3.4. Let G = (V, E, w) be a directed graph. Let Lij
represent the entry ij of the matrix
(Ll=l) for any V. Given 81, 82 and q:
a) w w (T
)1 -11|e:] = we w L|
$282
b) w
F = w(
81.9)
(1 1,/o]] (=1(el)).
529
As consequence of Lemma 3.4 DProbWS (Definition 3) Theorem 3.5. The Directed Probabilistic Watershed probabilities are equal to
conveniently find closed form for the probabilities of the
2229 [.1
La202
Pr(q ~ 81)
and Pr(g ~ 82)
1,11
111
l228
or equivalently
19181
1,[22]
1519
1.122
1s1
1-1,
Pr(q 82)
and Pr(g 81) =
1,eea]
8181
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 "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
4 Equivalence of DProbWS and the Directed Random Walker
Resembling the ProbW'S 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 [5]. we could not find any suitable reference for the directed case 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 complete derivation.
Theorem 4.1. The probability, xr²' that random walker directed graph starting at node q first reaches s before reaching 82 is given by the solution of the following linear system
LTay -BT
where 2 represents the probability that the nodes in U are absorbed by 8s, Ly is the square submatrix of L. indexed by the elements in U and [B]], the column $1 of L without the entries indexed by the seeds.
'However, there exist closed formulas to compute the absorbing probabilities of Markov chains in terms of the fundamental matrix (18).
7

---

Proof sketch: Let P denote the transition probability matrix defined by the absorbing random walker. We note that the probability of being absorbed by 8 g can be obtained by computing the entry (g. s) of pa when tends to infinity, i.e., x = lim [Px] "gs By expressing the transition matrix in terms of the Laplacian, we find a closed formula of the matrix P" by induction. By taking the limit to infinity, we obtain the desired result. See the supplemental material for further details. D
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., (Lv) yt = B Since [2 15 consider an undirected graph (LT) Lu. the transposition becomes irrelevant in the undirected case.
The next theorem states the equivalence between the DProbWSS and the Directed Random Walker. The proof analogous to Theorem 4.1 in [2] and replicate the proof in the supplemental material.
Theorem 4.3. The probability, " that a random walker on a directed graph starting at node first reaches 8 before reaching $2 equal to the Directed Probabilistic Watershed's 's probability (Definition 3)
9 = P(q $1).
The equivalence stated by Theorem 4.3 combined with Theorem 4.1 implies that in order to obtain the DProbWSS probabilities defined in Theorem 3.5 it is just necessary to solve a linear system for each seed node (see Algorithm T). the case for the Random Walker algorithm.
Algorithm 1: DProbWS
Input: G (V, E,, w), seeds
Output:
// DProbWS probabilities // Unlabeled nodes
U Vl seeds
L=ouLLaplacian(G)
Lu L(U; U] // squared submatrix L indexed by the unlabeled nodes
for E seeds do
B, s
11 column of L restricted to unlabeled nodes // Solves the linear system T. st -B
x/U: 8) =oolve([T..
Directed Power Watershed
In the ProbW'S 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 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 DP is restricted to the minimum cost spanning in-forests (mSF). This permits us to define a natural extension the Power Watershed to directed graphs.
In Section 3.1 we defined the weight of an edge as w(e) exp(- where c(e) was the edge-cost and j implicitly determined the entropy of the 2-in-forest distribution. When μ + oc, 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 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 81 and 82. Let further Wmax
max SE add w()). If the entropy of
the Gibbs distribution over the in-forests minimized (6) then
{f E 3 नl w(f) = Wmax
[EE
F w(s) = Wmax
8

---

1.00
10
16
GTC
0.00
LUD
DevaltS
0.5
ULC
Dhol//Sow
0.00
2-0
0.4
02
0.4
0.8
(a) Digits
(b) 20Newsgroups
Email-EU
3.0
Allatr
LUJ
0.4
ULD
Dhuers5
02
0.2
12
E-4
236
63
02
0.4
6.6
38
(d) Cora
(e) CiteseerX
Figure 3: Accuracy comparisons on the Digits, 20Newsgroups Email-EU, Cora and CiteseerX datasets. In all plots, the horizontal axis denotes the fraction of labeled notes in the graph varying from 0.1 to 0.9 with 0.1 increment. We depict the average accuracy over 20 runs with error bars of one standard deviation. Our methods DProbWS and DProbWStrw are on par with existing methods and sometimes outperfrom them.
Experiments
Although work has been motivated from theoretical perspective, men o 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 often used in practice. Due to its asymmetric nature, they can be regarded as directed graphs. We construct kNN graphs, with 5, from the UCI datasets [10) Digits 44 and 20Newsgroups 23] Additionally we consider the We compare the DProbWS with the methods exposed in
illustrative experi-
[26] 27 46), the Cora network 229 and CiteseerX network
49 referred ARW. GTG and
LLUD respectively. More details about the datasets, the comparison methods and the construction of the graphs can found the supplemental material. Due the high sparsity of the Cora and CiteseerX networks, many of the nodes are zero-knon vero-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 replacement of the natural one, in the same way it is applied in 49 (see supplemental material), The methods ARWtrw and Dprob Wttw 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 the accuracy, we also include the zero-knowledge nodes. Inspired by [9, we sample certain fraction r of all nodes from each class uniformly seeds. In Figure show the average accuracy over runs for each the r values between 0.1 and 0.9. We observe that method obtains comparable empirical results sometimes outperforming all competing methods.
7 Conclusion
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 Gibbs distri- bution over all the directed spanning in-forests rooted at the seeds of directed graph (Definition 3). We also demonstrated, using the directed version of the Matrix Tree Theorem 225. 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
CCode publicly
available
com/hci
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 [2 triangle inequality gap of the triangle given by the 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 the triangle inequality gap of the effective resistance or any other distance in the directed setting. However, we conjecture that there may exist 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.
8 Broader impact
Our work has been motivated by theoretical understanding of already existing algorithms. The speculation of 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 graph- based 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 spanning in-forests and the Directed Random Walker, expect that 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 Forschungsgemeinschaat (DFG, German Research Founda- tion) under Germany's 's Excellence Strategy EXC 2181/1 -390900948 (the Heidelberg STRUCTURES Excellence Cluster).
References
[1] F. Alam, S. R. Joty, and M. Imran. Graph based semi-supervised learning with convolution 2018. http
neural networks classify crisis related tweets. CoRR,
//ar 1180/ 06289
[2] M. Aliannejadi, M. Kiaeeha, S. Khadivi, and S. S. Ghidary. Graph-based semi-supervised conditional random fields for spoken language understanding using unaligned data. CoRR, abs/1701 085533, 2017. URL http:://axxiii. org wtrg/ab//101.085333 08533
[3] M. Belkin, P. Niyogi, and V. Sindhwani. Manifold regularization: A geometric framework for learning from labeled and unlabeled examples. JMLR, 7:2399-2453 -2349, 2006.
[4] Y. Chebotarev and E. Shamis. The matrix-forest theorem and measuring relations in small social groups1. Automation and Remote Control, 58:1505-1514, 1997.
[5] Y. Chong, Y. Ding, Q. Yan, and S. Pan. Graph-based semi-supervised learning: A re- view. Neurocomputing 408:216-230, 2020. ISSN 0925-2312. doi: http:://doi.org/1011116 neucom.2019.12.15 URL htttp::/www.siiineddrrrc..ooo htt.:/awwweeeeececoo////////nena $092523112208049888
[6] C. Couprie, L. Grady, L.. Najman, and H. Talbot. Power watershed: A unifying graph-based optimization framework. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2011.
10

---

[7] J. Cousty, G. Bertrand. L. Najman, and M. Couprie. Watershed cuts: Minimum spanning forests and the drop of water principle. IEEE Transactions on Pattern Analysis and Machine Intelligence, 31:1362-74, 2009. doi: 10.1 109/TPAMI.2008.
[8] M. Cuturi. Sinkhorn distances: Lightspeed computation of optimal transport. In NIPS, pages 2292-2300, 2013.
[9] De, X. Zhang, Lin, and Cheng. Transduction on directed graphs via absorbing random walks. IEEE Transactions Pattern Analysis and Machine Intelligence, 40(7):170--174,, 2018. doi: 10. 10.110/TPAM.2201:273661..
[10] D. Dua and C. Graff. UCI machine learning repository, 2017. URL http://arrchive.ccs uci. edu/ml
[11] A. Erdem and M. Pelillo. Graph transduction non-cooperative game. In X. Jiang. M. Ferrer, and A. Torsello, editors, Graph-Based Representations in Pattern Recognition, pages 195-204, Berlin, Heidelberg, 2011. Springer Berlin Heidelberg. ISBN 978-3-642-208442
[12] E. Fita Sanmartin, S. Damrich, and F. A. Hamprecht. Probabilistic watershed: Sampling all spanning forests for seeded segmentation and semi-supervised learning. H. Wallach, H. Larochelle, A. Beygelzimer, F. d Alché-Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems 32, pages 2780-2791. Curran Associates, Inc., 2019.
[13] F. Fouss, M. Saerens, and M. Shimbo. Algorithms and models for network data and link analysis. Cambridge University Press, 2016.
[14] K. Françoisse, I. Kivimäki, A. Mantrach, F. Rossi, and M. Saerens. A bag-of-patee framework for network data analysis. Neural Networks, 90:90-111, 2017.
[15] L. Grady. Random walks for image segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2006. ISSN 01628828. doi: 1..100//PAMM..200.2233
[16] D. A. Harville. Matrix Algebra From Statistician's Perspective. Springer- Verlag New York, 1997. ISBN 978-0-387-78356-77
[17] G. He, X. Liu, F. Fan, and J. You. Classification-wwar semi-supervised domain adaptation. In 2020 IEEE/CVF Conference on Computer Vision and Pattern Recognition Workshops (CVPRW), pages 4147-4156 2020. doi: 10.1 10.110//VPRW550498.2200 2020000099
[18] J. G. Kemeny and J. L. Snell. Finite markov chains, undergraduate texts mathematics. 1976.
[19] G. Kirchhoff. Über die Auflösung der Gleichungen, auf welche man bei der Untersuchung der linearen Vertheilung galvanischer Ströme geführt wird. Annalen der Physik, 148:497-50$ 1847.
[20] I. Kivimäki, M. Shimbo, and M. Saerens. Developments in the theory of randomized shortest paths with comparison of graph node distances. Physica A: Statistical Mechanics and its Applications, 393:600-616, 2014.
[21] D. Klein and M. Randić. Resistance distance. Journal of mathematical chemistry, 12(1): 81 81-95. 1993.
[22] Koo. A. Globerson, X. Carreras, and M. Collins. Structured prediction models via the matrix-tre theorem. In EMNLP-CONLL, 2007.
[23] K. Lang, Newsweeder: Learning to filter netnews. Proceedings of the Twelfth International Conference on Machine Learning, pages 331-339, 1995.
[24] R. Lang, R. Lu, C. Zhao, H. Qin, and G. Liu. Graph- semi-supervised one class support vector machine for detecting abnormal lung sounds. Applied Mathematics and Computation, 364:124487, 2020. ISSN 0096-3003. doi: https://wwe http://wwwwwccincccree..c.oooo
URL.

---

[25] P. D. Leenheer. An elementary proof of a matrix tree theorem for directed graphs SIAM. Aug. 2020. doi: 10.1137/9M1/265193 URL htttps:/ siam. wwwg/doiabs///ee 1137/ 19N1 265193 Publisher: Society for Industrial and Applied Mathematics.
[26] Leskovec and A. Krevl. SNAP Datasets: Stanford large network dataset collection, http:
httpppsttttorrredd/dddtttt June 2014.
[27] Leskovec, J. Kleinberg, and C. Faloutsos. Graph evolution: Densification and shrinking diameters. ACM Trans. Knowl. Discov. Data, 1(1):2-es, Mar. 2007. ISSN 1 1556-4681. doi: 10.1145/1217299, 1217301. URL TRRIhttps:: http:///ooooooo...//1// 11151/0111111111999999999999 1217301
[28) H. Linmei, T. Yang, C. Shi, H. Ji, and X. Li. Heterogeneous graph attention networks for semi-supervised short text classification. In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference Natural Language Processing (EMNLP-IJCNLA pages 4821 Hong Kong, China, Nov. 2019. Association for Computational Linguistics. doi: 10. 10.18653/1/DD1-1144555 URL http:: //wp: welleb.org/aan www.gg/gtolooggg/////ar DD9-
[29] S. A. Macskassy and F. Provost. Classification in networked data: A toolkit and univariate case study. Journal of Machine Learning Research, 8(34):935-98) 2007. URthttp:: hthp:://mmm org/paperss v www.ssssaaaa....m. html
[30] S. A. Macskassy and F. Provost. Classification in networked data: A toolkit and a univariate case study. Journal of Machine Learning Research, 8(34):935-95)) 983, 2007. httht //jt:: org/papera/ /varrr/////a htt///aaaaaaaa0.... html
[31] Q. Mei, D. Zhang, and C. Zhai. A general optimization framework for smoothing language models on graph structures, pages 61 1-618, 01 2008. doi: 10.1145/139033,, 1390438,,
[32] A. Mensch and M. Blondel. Differentiable dynamic programming for structured prediction and attention. In ICML, 2018.
[33] R. A. Rossi and N. K. Ahmed. The network data repository with interactive graph analytics and visualization. In AAAI, 2015. URL BRLLattp://neesoorrrpssttoo
[34] M. Senelle, S. Garcfa-Díez, A. Mantrach, M. Shimbo, M. Saerens, and F. Fouss. The sum- over-forests density index: Identifying dense regions in graph. IEEE Transactions on Pattern Analysis and Machine Intelliencee 36: 1es11668-127 2014.
[35] D. Singaraju, L. Grady, and R. Vidal. Interactive image segmentation via minimization of quadratic energies on directed graphs. 2008 IEEE Conference on Computer Vision and Pattern Recognition, pages 1-8, 2008. doi:
[36] Z. Song, X. Yang, Z. Xu, and I. King. Graph-based semi-supervised learning: comprehensive review, 2021.
[37] A. Teixeira, P. Monteiro, J. Carriço, M. Ramirez, and Francisco. Spanning edge betweenness. In Workshop on Mining and Learning with Graphs, volume 24, pages 27-31, January 2013.
[38] A. Teixeira, P. Monteiro, J. Carriço, M. Ramirez, and P. Francisco. Not seeing the forest for the trees: Size of the minimum spanning trees (msts) forest and branch significance in mst-based phylogenetic analysis. PLOS ONE, 10, 2015. doi: 10. 10.1371/jouu h171//orrall.pome pone.01 mopne.011931.. 19315.
[39] F-S. Tsen, T.-Y. Sung, M.-Y. Lin, L.-H. Hsu, and W. Myrvold. Finding the most vital edge with respect to the number spanning trees. IEEE Transactions on Reliability, 43:600-602, 1994.
[40] W. T. Tutte. Graph theory. Encyclopedia of mathematics and its applications. Addison-Weste Wesley, 1984. ISBN 0-201-13520-5 and 978-0-201-13520-6
[41] J. E. van Engelen and H. H. Hoos. A survey on semi-supervised learning. Mach Learn, 109(2): 373-440, Feb. 2020. ISSN 0885-6125, 1573-0565. doi: 10. 1010000/1199944-9--05555555 URI.
attp://link. springer com/ 10. 1007 01tp://1119944-11-88-5-55-
12

---

[42] H. Wang, C. Ding, and H. Huang. Directed graph learning via high-ont -odhrrrder co- co-linkage analysis. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pages 451-466. Springer, 2010.
[43] G. Winkler. Image analysis, random fields and Markov chain Monte Carlo methods: mathematical introduction, volume 27. Springer Science & Business Media, 2012.
[44] L. Xu, A. Krzyžak, and Suen. Methods combining multiple classifiers and their applications to handwriting recognition. IEEE Trans. Syst. Man Cybern., 22:418 435, 1992.
[45] C. Yang, L. Bai, C. Zhang, Q. Yuan, and J. Han. Bridging collaborative filtering and semi- supervised learning: A neural approach for poi recommendation. In Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD '17, page 1245-122 1254,, New York, NY, USA, 2017. Association for Computing Machinery. ISBN 9781450348874, doi: 10. (0.1145/3999983330060 3098099 URL https: htttps://doi.org/// 1145/ 1145/ 0097963.3088083
[46] H. Yin, A. R. Benson, J. Leskovee, and D. F. Gleich. Local higher-order graph clustering. In Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD '17, page 555-564, New York, NY. USA, 2017. Association for Computing Machinery, ISBN 9781450348874,
doi: 10.1145/3097983 URL https:
//doi.org/100 1145 02145//009963... 309899633008869 3098069
[47] D. Zhou, O. Bousquet, T. N. Lal, J. Weston, and B. Schölkopf. Learning with local and global consistency. In NIPS, pages 321-328, 2004.
[48] D. Zhou, T. Hofmann, and B. Schölkopf. Semi-supervised learning on directed graphs. In
L. K. Saul, Y. Weiss, and L. Bottou, editors, Advances Neural Information Processing Systems 17, pages (633-1640. MIT Press, 2005. URL httt::/paperr:: wepppprssnips..... cctiaperrr/ppp 2718 semi -
[49] D. Zhou, Huang. and Schölkopf. Learning from labeled and unlabeled data on directed graph. In Proceedings of the 22nd International Conference on Machine Learning, ICML '05, page 1036-1043, New York, NY, USA, 2005. Association for Computing Machinery. ISBN 1059938005 doi: 10.1 1023111,111152455555 1102482
httpssts::///at 111.o/oor//11...1/1110000.
[50] X. Zhu, Z. Ghahramani, and J. Lafferty. Semi-supervised learning using gaussian fields and harmonic functions. In ICML, pages 912-919, 2003. ISBN 1-57735-189-4, URL http:
//dl. acml.acm.co sng/citation cfm.idd334118...com 3041953
13


Reviews:
[{"review_id": "k04FRm821Wa", "reviewer": "Reviewer_1WWq", "summary": "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.\n\nThis 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.\n\nIn 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.\n\nThe 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.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The results of this paper are a natural extension of known results for the undirected case. The results do not seem too difficult to prove, once one is familiar with the undirected case. Still, since this is a fairly fundamental problem, writing down the details of this seems like an important service to the community. Overall, I would be open to seeing the paper accepted if there is space in the program. However, the level of novelty is arguably a bit borderline.\n\nOnce the directed graph and seeds are given, the method is quite principled and feels like the \"right\" way to approach the problem. However, the procedure by which the graph is built from the dataset (using k-nearest neighbors) feels more \"ad hoc\". In particular, the original dataset doesn't seem to contain \"directed\" information, so transforming it into a directed graph feels a bit artificial. I wonder if one could do just as well by instead building an undirected graph.\n\nIt is interesting that the new method seems to significantly outperform [9] on the digits dataset. The ARW method from [9] appears similar at first glance, as it is also based on random walks (but seems slightly less principled than the current paper). It would improve the paper if the authors could explain why we see this discrepancy, i.e., what exactly is going wrong with the ARW method and what makes the new method better?\n\nSpecific comments:\npg 1: The weight of a forest hasn't been defined yet. It might be good to clarify that this means the product of the weights of the edges.\npg 3: The definitions here are a bit confusing because you formally define a spanning in-tree (Def 1) but then use (non-spanning) in-trees to define a \"2-in-trees spanning forest\".\npg 8: It would help to define \"accuracy\", even if informally.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Ok", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "dq94AszKOJE", "reviewer": "Reviewer_j9jR", "summary": "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.", "questions": "", "limitations": "", "rating": 6, "confidence": 1, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The manuscript is well written but is not easy to read since the proofs are difficult. In particular, I cannot yet verify if Theorems 4.1 and 4.3 are correct. And these are the main theorems in the manuscript.\n\nQuestions:\n\n1. Since the \"directed\" Laplacian is not symmetric, notions of non-negative definiteness do not apply (and if accepted, please fix the language since the concept itself is meaningless for non-symmetric matrices). Consequently, the authors pursue a directed random walk approach instead of the objective function approach. How can you then have a Gibbs distribution if there's no \"energy function\" since the two are joined at the hip? Unless the distribution is not Gibbsian due to the directedness of the graph? Please clarify. Perhaps you meant the stationary distribution.\n2. How is your work related to work on sampling directed graphs with random walks (Ribeiro et al.)\n3. This is a tangential question. There are strong relationships between the determinants in MTT and eigenvectors. Since your matrices are not symmetric, eigenvectors if they exist can be complex. Have these relationships been worked out?\n4. Can everything be done for out-forests rather than in-forests? Seems like that would be the case.\n\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The manuscript does fundamental work and so this question does not apply.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3 hours"}, "extra_text": {"ethical_concerns": "This is some woke stuff which is irrelevant for this manuscript.\n\nOr rather, since the original Metropolis-Hastings MCMC sampling algorithm was connected to research on atomic bombs, perhaps this paper should be banned? "}}, {"review_id": "bjcjuduAOgf", "reviewer": "Reviewer_ctCN", "summary": "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.", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This is an interesting paper, and the proposed contribution is certainly not trivial and generalizes the class of methods upon which it builds. Furthermore, the theoretical results, namely the equivalence with the random walker method is interesting and completes the proposed generalization.\n\nOn the negative side, I think the contribution of the paper is rather marginal and the experimental evaluation of the proposed method is quite limited. The motivation of why it is at all relevant to use directed graphs in graph-based semi-supervised classification is only mentioned in the experiments section, where the authors use kNN graphs, which are not guaranteed to be symmetric. The only comparison is with another method for directed graphs, but this begs the obvious question: What would be the results of symmetrizing the graph and then using the undirected probabilistic watershed algorithm? This comparison, if advantageous for the proposed method, would give some experimental support to the relevance of what is proposed in the paper. \n\nThe authors do claim that \"although our work has been motivated from a theoretical perspective, we run an illustrative experiment\", but this is not a good enough excuse. These graph-based semi-supervised classification methods are very heuristic, in the sense that they lack any decision-theoretic support or any formal (statistical learning theoretic) guarantees. They are based on ideas that seem reasonable, but that is not enough to justify their relevance. Consequently, for this type of method, \"the proof is in the pudding\", thus experimental results are all there is to justify their relevance and applicability, and the only way to justify the relevance of some new contribution to this class of methods.\n\nTrue, the methods are mathematically sophisticated and interesting, and the paper even includes a few interesting theorems. However, from a machine learning perspective, these theorems are somewhat \"internal\", in the following sense: they establish properties of the methods, and equivalences with related methods, but they say nothing about the performance of the method. \n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "They have.\n", "review_text": "", "extra_scores": {"ethical_concerns": "None.\n", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "3dqwiKghvMz", "reviewer": "Reviewer_CQ5E", "summary": "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.\n\n\n\n\n\n", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is well written, original, and makes significant contribution. The one weakness is the incompleteness of numerical results and comparisons.\n  \nNovelty:\nThe author's extension of ProbWS [12] and PW [6]  to directed graphs is interesting and non-trivial.  Using the directed version of the Matrix Tree Theorem they provide a way to analytically compute the directed probabilistic watershed probabilities, specified by Gibbs probability distributions, that specifiy the probability that an (unlabelled) graph node is assigned to a particular seed (labelled node) in an ensemble of incoming directed spanning forests rooted at the seed. This results in Thm 3.5, characterizing the probabilities exactly, and an equivalence of ProbWS to  DRW.  \n\n\nScholarship:\nThe paper does an excellent job relating the contribution to prior work, which is extensively discussed and cited in the paper. They make it very clear what their contribution is and what innovation on the theory is needed to develop their extension.  \n\n\nExperimental completeness: The experimental section is brief - most of the paper centers on the theoretical contributions. The authors show favorable comparisons of the directed ProbWS to another algorithm ARW [9] for 3 different data sets (Digitsm 20Newsgroups, Email-EU). More extensive numerical illustrations would help to establish the practical significance of the paper.  This would include: comparisons to other methods proposed for directed graph segmentation, e.g., spectral methods [Fagiolo, PR-E 2007], graph cuts [Meila and Pentney, SIAM Data Mining 2007] and conductance methods [Yin et al, KDD 2017]; exploration of the  influence of the choice of the fraction of nodes (r) used as seeds; influence of the local topology of these seeds; and scalability of the computation to larger networks.    \n\n\nQuality of writing:\nThe paper is very well-written.\n\n\nAuthors' statements on the questionnaire:\nQuestion 3 not accurate - there is no code provided in the paper as far as we have seen. The hardware is mentioned in the supplementary material. Some details on implementation are mentioned in the supplementary material as well, including some of the hyperparameters.  However, it is not explained why their particular value of r was chosen to create the directed graphs. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No negative implications. ", "review_text": "", "extra_scores": {"ethical_concerns": "No ethical concerns.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2-3 hours"}, "extra_text": {}}, {"review_id": "3M5jNyGJYmE", "reviewer": "Reviewer_L2ar", "summary": "The paper introduces an extension of the Probabilistic Watershed method in semi-supervised learning from undirected graphs to directed graphs. The paper makes the connection between the Directed Probabilistic Watershed and the Directed Random Walker, which is an extension of the Ransom Walker to directed graphs and is also introduced in this paper.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper brings forth a theoretical contribution in the form of the Directed Probabilistic Watershed and Directed Random Walker methods. The main results of the paper are the computation of the probabilities that any query node is connected to any of the labeled nodes. \nHowever, these contributions are purely theoretical and the authors make no effort in being more accessible to the researchers that might just want to use the method for their semi-supervised learning or image segmentation application. To this end, a precise description of the Directed Probabilistic Watershed or Directed Random Walker algorithm is missing from the paper. This limitation makes the paper only accessible to theoretical researchers and limits its practical applicability.\nIn contrast, the Random Walker is a segmentation algorithm with an exact description that can be used for labeling undirected graphs. \nThe experiments are limited and not described properly, therefore not reproducible. It is not clear how the kNN graph was obtained, what are the nodes, and what the edge weights are.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have addressed the societal impact, but not the limitations.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}]

Author rebuttal:

Meta-review: In this paper the authors proposed a semi-supervised learning algorithm for segmenting directed graphs, extending previously proposed methods designed  for undirected graphs The proposed method builds upon the watershed algorithm, an approached, based on building "separating forests"  and defining a Gibbs distribution, as in statistical physics, on this set of forests. The main contribution, beyond generalisation of this method to directed graphs, is given in the form  theoretical results related. 

After the first round of rebuttal, the paper was found interesting and looked upon favourably on it theoretical part. The new theorems (for instance an equivalence with the random walker method) were all found strong and interesting by the reviewers. The numerical part, however, was found was rather weak and incomplete and the paper initially received mixed grading.

The authors did present a very good case in their rebuttal, giving new additional data and quantifying the comparative performance in their response to all the criticisms of the reviewers. After the rebuttal, it seemed that all reviewers (but one who did not reply, but whose criticism seemed to have been addressed) agreed that the paper was stronger and definitely of value to the Neurips community, actually increasing their score and assessment of the paper. 

Given the authors successfully answered the criticism of the referee, I therefore recommend acceptance to Neurips.




Decision: Accept (Poster)