Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper proposes a probabilistic clustering method based on two losses: Dasgupta loss and Tree-sampling divergence. A scalable sampling-based optimization is proposed. The modes is optimized with the projected gradient descent.
main_review: The idea of hierarchical probabilistic clustering inference from the trees seems novel and interesting. Dasgupta loss is a relatively new development in the clustering literature; the contributions of this work are timely.
Note: since this is an emergence review, I did not check correctness of the proofs in the Appendix. 

The experimental section is very unconvincing, however. The comparisons are performed only wrt. primitive graph clustering methods; for instance, in a graph clustering paper I would expect to find heuristic greedy modularity optimization (Blondel et al., 2008), hierarchical SBM fitting, and possibly some non-hierarchical algorithms.

Crucially, the metric space clustering baselines are given very suboptimal features for the clustering: DeepWalk's d=10 is far too low. The original DW paper uses d=128 for all graph sizes, and neural embedding-based models are known to perform poorly in low dimensional regime.

The scalability of the method is concerning as well. While the paper claims scalability, it is only being evaluated on one large-scale dataset, which is not supporting the claim.

Based on two findings above, I am ready to raise my score, given that the paper is updated with:
- A re-run of the experiments, or at least a sample of them (Table 2), with d=128, as is default for DeepWalk.
- A comparison (Tables 2-3, and possibly 5) some classical graph baselines for clustering, including Louvain.
- Results from OBG-arXiv to Table 2, and add at least one-two more medium-scale dataset (# of nodes 50k+) without graph subsampling tricks.

In the current state, it is very hard to find support for the claims in the paper experimentally. I am sorry for asking quite a lot in a short timeframe; I hope the authors/ACs do understand my reasoning. In case authors think my asks are unreasonable, please suggest some alternative ways to prove the points that are currently weak.
summary_of_the_review: The idea and the model in the paper sound reasonable; however, the experimental results are very unconvincing: (1) Three of the baselines are operating on the embedding of the data potentially built by an ill-configured model (2) the claimed scalability is only empirically supported on *one* dataset of size 100000 (3) there is a ton of missed baselines from the graph clustering literature.

After seeing the rebuttal I raise my score to the accept category.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper proposes a probabilistic model of tree-based hierarchical clustering by considering a continuous relaxation. The authors establishes the theorical connections between tree-sampling and the Markov chain that is specifically constructed. This allows an end-to-end gradient-based learning to optimize the internal metrics of graph clustering, namely the Dasgupta cost and Tree Sampling Divergence. This method allows efficient and effective modeling of the graph clustering. Extensive experiments results on different types of graph, including some of the large scale ones, suggests the proposed method behave favorably. 
main_review: 1) This paper is well-written and organized. The notations used throughout the paper is consistent and easy to follow. 2) Instead of providing a heuristic driven method, this method proposed in this paper has solid theoretical supports. 3) The model optimizes directly for the objectives in an end-to-end fashion. It is scalable and achieves state-of-art performance compared with both past and current baselines. 4) The experimentation setting is complete and very informative. 

However, the implementation part could add more details. Also, the implementation/code is claimed to be present in the supplement materials but it is not.
summary_of_the_review: This paper proposes a novel graph clustering method with solid theoretical supports and strong practical performance. The paper itself provides complete reasonings of the motivations and derivations. Overall, it is a impressive paper that brings huge improvement to an important problem of graphs.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper presents a hierarchical clustering over graphs using a probabilistic model via continuous relaxation of the discrete tree-based hierarchies. It uses two metrics the Dasgupta cost and the Tree-Sampling Divergence. The paper presents an efficient vectorized computation and discusses several details on the choice of hyper parameters. The article presents empirical evaluation on 8 real datasets and compares the technique with several baselines on hierarchical clustering (using NMI), comparing also results on controlled clusters (ground truth class labels, synthetic stochastic block-model) and link prediction (best or second based performance), as well as on meta-analysis which includes ablation, scalability, runtime, and a qualitative assessment.
main_review: Among the strengths of this paper I can mention that: 
Using the adjacency information of the graph structure to identify tree-based hierarchies can be useful and computationally a good strategy as proved in other works.
The use of a Markov chain over the tree defines an acyclic chain that could be used for inference. 
The block formulation of the vectorized computation could be useful for efficient implementations.
With respect to the weaknesses, there are a few items that could be clarified. Namely:
The paper states that in early experiments “PGD optimization leads to faster and better convergence” can you ellaborate what the early experiments entailed?
The paper states that the baselines were trained 5 times and results were reported for the best run, could you also report the variance for the baseline and the proposed model to have an estimate of the stability of the results?
Why were only a few datasets selected to report in certain experiments? e.g. in Table 2 only three datasets appear.
summary_of_the_review: The paper has some strengths that could be useful in applications of graph or network clustering and inference. I find the continuous tree-based hierarchy and associated Markov chain interesting and results promising. I do have some reservations about some decisions made about what to report as I highlighted above. Overall, it may be an interesting addition to ICLR if the authors can improve on the weaknesses I pointed out.
review_title: null

Meta-review: The authors introduce a novel probabilistic hierarchical clustering method for graphs. In particular they design an end-to-end gradient-based learning to optimize the Dasgupta cost and Tree Sampling Divergence cost at the same time.

Overall the paper presents solid results both from a theoretical and experimental perspective so I think it is a good fit for the conference and I suggest accepting it.
Decision: Accept (Poster)