Hierarchical clustering is a common approach to analysing the multi-scale structure of graphs observed in practice. We propose a novel metric for assessing the quality of a hierarchical clustering. This metric reflects the ability to reconstruct the graph from the dendrogram encoding the hierarchy. The best representation of the graph for this metric in turn yields a novel hierarchical clustering algorithm. Experiments on both real and synthetic data illustrate the efficiency of the approach.
This paper proposes a new formulation of hierarchical clustering for graphs.
Quality:
The proposed formulation has not been analyzed in detail and its advantage is not clear compared to existing approaches.
In addition, there are some existing measures for hierarchical clustering, for example, the dendrogram purity[1].
It would be interesting to analyze the relationship between the proposed method and such existing measures. 
[1] Heller, K. A. and Ghahramani, Z.: Bayesian Hierarchical Clustering, ICML2005
Clarity:
This paper is clearly written and easy to read.
The proposed criteria is carefully derived and well explained.
I feel that the title of the paper is not appropriate as it says the paper is about graph representation learning while a graph (representation) is already given as an input in the setting discussed in this paper. "Learning hierarchical representation ..." would be better.
Originality:
The originality is not high as most of theoretical discussion is based on the existing work and the resulting hierarchical clustering algorithm is a straightforward extension of the average linkage method.
Of course, it is quite interesting if a minor change makes a big difference in clustering performance (theoretically and/or empirically), but such result is not given.
Significance:
Significance of the contribution is not high as the advantage of the proposed formulation is not clear.
One of interesting questions is: how about higher order relationships between nodes?
The proposed method takes up to second order relationships between nodes, that is, edges into account.
Since the proposed formulation can naturally include higher order relationships, it would be interesting to analyze such relationships in hierarchical clustering.
Pros:
- The paper is clearly written.
- The proposed formulation of hierarchical clustering is interesting.
Cons:
- The advantage of the proposed formulation is not presented.
- Experiments are not thorough.