Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper introduces DIGRAC, a novel GNN approach for clustering based on the edges that are not present in a digraph. The architecture achieves this by finding node embeddings for digraphs that directly maximizes flow imbalance between clusters. The paper presents empirical results on both real and synthetic datasets, showing the effectiveness of the proposed approach.
main_review: **Summary** This paper presents an empirical study of clustering nodes based on a given graph structure. The clustering model is a deep approach that produces embeddings of the nodes that can be used for other tasks like node classification, etc. 

**Merits**. This paper demonstrates that it can achieve the desired goal of node representations with the DIGRAC architecture and the "DIRECTED MIXED PATH AGGREGATION (DIMPA)" layer in particular. To better understand this deep model, the authors provide synthetic empirical results, which demonstrate the performance of the method under different kinds of data.

**Concerns**. My primary concern for this paper is that I find it difficult to understand the empirical performance gains provided by the method. In many of the ARI graphs on synthetic data, it seems many of the methods are quite close together in performance. In the real data, it seems that methods overlap in their error bars. I am also wondering whether more can be said about when DIGRAC's model for clustering is appropriate for a dataset and when it is not. And how adaptive the model can be in terms of performance despite those considerations. Apologies if I have misunderstood the empirical results, if so, I would like to better understand them. 
summary_of_the_review: An interesting paper with a self-supervised novel architecture for node clustering using an objective based on missing edges in a digraph. There are some concerns regarding the empirical gains provided by the method.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper studies the problem of clustering directed graphs where clustering structure is defined in terms of flow imbalances between clusters. The method proposed in this paper first computes node embeddings via directed mixed path aggregation, which takes directionality into account. In order to perform clustering, the node embeddings are transformed to an assignment probability matrix, which is then used to compute a flow imbalance score. The model is trained end-to-end to maximize the flow imbalance score (or its variants). Empirical experiments show that the proposed method has good performances.
main_review: **Strengths**

Overall, the paper is well written.

**Weaknesses**

I am concerned with the practicality of the problem and consequently the method studied in this paper. In Section 4, the authors mention that "real data sets with ground-truth flow imbalances are not available to date", so they use normalized imbalance scores to evaluate clustering performance. This feels a bit like going against the natural order of how machine learning models are typically developed. Usually, we start with a real, practical problem at hand, and then we try and develop a new method to solve it, if existing methods do not yield satisfying results. However, I feel like this paper is going backwards: It starts with inventing a method that solves a possibly made-up problem. The experiments in Section 4 do not demonstrate the practical importance of clustering with respect to flow imbalances. Since this is an empirical paper, I believe that a solid empirical evidence that showcases the need for clustering with respect to flow imbalances is required.

More about empirical evaluations: The authors use 80% of all nodes for training. Isn't this percentage too much? Can't we use, e.g., 5% of all nodes for training?
summary_of_the_review: I have concerns regarding both the problem setting and the empirical evaluation, so I do not view this paper as ready for publication at this time.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper introduces DIGRAC, an end-to-end model for clustering in directed graphs. The novelty of the model stems from the fact that it optimizes the directed flow imbalance to identify clusters that go beyond density-based criteria.  The proposed problem formulation is interesting: the loss function is defined in order to capture imbalance flow among clusters. Then, a GNN model is used to obtain the probabilistic assignment matrix that defines clusters. In terms of empirical analysis, the paper performs experiments on various artificial and real-world datasets, comparing the performance of the proposed model to various baselines.
main_review: Strengths:
- The paper provides an interesting pipeline for clustering in directed graphs. In particular, the idea of modeling the imbalance flow is very useful.
- Interesting benchmark graphs. I really liked the idea of using a modified DSBM model to express information flow.

Weaknesses:
- The theoretical contributions of the paper are somewhat vague at some points, and overall could be enhanced. 
- It is not very clear what are the novel aspects of the DIMPA model.
- The baseline models could be enhanced. 


**Detailed comments.**

Despite the interesting formulation of the problem, there are several aspects of the paper that are not quite clear and need further development. Next, I provide a detailed discussion of points that need to be addressed.

To begin with, despite having an interesting formulation of the imbalance flow, the loss function defined in Eq. (2) and (3), is not well-understood. I can see the semantics behind the imbalance term, but the theoretical properties are not clear at all. Is there any theoretical characterization for this loss? Are there cases where it could lead to degenerate solutions? It would also be important to clearly present the constraints of the optimization problem. Examining how the loss behaves in terms of convergence, is also important.

The other important point has to do with the novelty of the DIMPA algorithm. It’s not clear to me what are the novel parts of this model w.r.t. previous works. As far as I understand, the paper shares common ideas with message passing GNNs as well as with the KernelGCN model. Therefore, it’s difficult to evaluate its novelty w.r.t. state-of-the-art baseline models.

I really appreciated the effort that the authors put into the empirical analysis, especially on the parts related to the stochastic block model. Regarding the baseline models, the paper discusses why many “traditional” models are not part of the empirical analysis. Nevertheless, I would expect to add models that capture information flow, including for instance algorithms that rely on stochastic blockmodels (e.g., “Directed network community detection: A popularity and productivity link model”, SDM 2010). Besides, it would be interesting to have a model that is based on directed modularity (e.g., E. A. Leicht, M. E. J. Newman, “Community structure in directed networks”, PRL 2008).

Lastly, despite mentioning the complexity of the model, there are no scalability experiments with the running time of the algorithm and its comparison to baseline models.

summary_of_the_review: The paper proposes an interesting approach to end-to-end flow-based clustering in directed graphs. Nevertheless, particular aspects of the paper, especially those related to the properties of the loss function and, partly, the experiments, need further development.
review_title: null

Meta-review: The authors propose a new algorithm for clustering direct networks. The key idea behind the paper is to introduce a new flow imbalance measures and a new self-supervised GNN model to solve the task.

Overall, the paper is interesting and it introduces some new ideas although it needs additional work before being published. 

In particular,
- the experiments could be improved by emphasizing more the evaluation on vol_sum/vol_max/etc metrics and by adding additional results on them
- the clarity of the experimental results should also be improved(for example, metrics / claims around Figure 4 still a bit hard to parse)
- finally, the paper would benefit by some theoretical results on the guarantees of the algorithm(most previous work in the area present interesting theoretical guarantees)
Decision: Reject