Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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.
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.

Questions:

1. 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.
2. How is your work related to work on sampling directed graphs with random walks (Ribeiro et al.)
3. 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?
4. Can everything be done for out-forests rather than in-forests? Seems like that would be the case.



limitations_and_societal_impact: The manuscript does fundamental work and so this question does not apply.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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.

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

Once 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.

It 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?

Specific comments:
pg 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.
pg 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".
pg 8: It would help to define "accuracy", even if informally.
limitations_and_societal_impact: Ok
review_title: null

final_score: rating: 4: Ok but not good enough - rejection
review_content: 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.
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.

On 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. 

The 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.

True, 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. 


limitations_and_societal_impact: They have.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: 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.
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. 
However, 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.
In contrast, the Random Walker is a segmentation algorithm with an exact description that can be used for labeling undirected graphs. 
The 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.
limitations_and_societal_impact: The authors have addressed the societal impact, but not the limitations.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: 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.






main_review: The paper is well written, original, and makes significant contribution. The one weakness is the incompleteness of numerical results and comparisons.
  
Novelty:
The 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.  


Scholarship:
The 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.  


Experimental 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.    


Quality of writing:
The paper is very well-written.


Authors' statements on the questionnaire:
Question 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. 

limitations_and_societal_impact: No negative implications.
review_title: null

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)