Learning Graph Representations by Dendrograms
Year: 2018

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

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

heading: 1 Introduction
text: Many datasets have a graph structure. Examples include infrastructure networks, communication networks, social networks, databases and co-occurence networks, to quote a few. These graphs often exhibit a complex, multi-scale structure where each node belong to many groups of nodes, so-called clusters, of different sizes (Caldarelli and Vespignani (2007)).
Hierarchical graph clustering is a common technique for the analysis of the multi-scale structure of large graphs. Instead of looking for a single partition of the set of nodes, as in usual clustering techniques, the graph is represented by a hierarchical structure known as a dendrogram, which can then be used to find relevant clusterings at different resolutions, by suitable cuts of this dendrogram.
While many hierarchical graph clustering algorithms have recently been proposed (see for instance Newman (2004); Pons and Latapy (2005); Sales-Pardo et al. (2007); Clauset et al. (2008); Lancichinetti et al. (2009); Ronhovde and Nussinov (2009); Huang et al. (2010); Chang et al. (2011); Tremblay and Borgnat (2014); Bonald et al. (2018)), it proves very difficult to evaluate their performance due to the absence of public datasets of graphs with ground-truth hierarchy. A natural approach is then to define some quality metric based on the graph itself, just like modularity is a popular metric for assessing the quality of graph clustering (Newman and Girvan (2004)).
A cost function has been proposed by Dasgupta (2016) for hierachical graph clustering and has been further analysed and extended by Cohen-Addad et al. (2018); it can be viewed as the expected size of the smallest cluster induced by the hierarchy and containing two nodes sampled at random from the edges of the graph. In this paper, we propose a quality metric based on the ability to reconstruct the graph from the hierarchy. It is equal to the relative entropy of the probability distribution on node sets induced by the hierarchy compared to that induced by independent node sampling. Finding the best graph representation for this metric yields a novel hierarchical clustering algorithm, which can in turn be interpreted in terms of modularity.
In the next section, we introduce sampling distributions of nodes and node sets induced by the graph, which play a key role in our approach. We then formalize the problem of graph representation by a dendrogram. Our quality metric follows from the characterization of the optimal solution in terms of graph reconstruction. The corresponding hierarchical graph clustering algorithm is then presented and interpreted in terms of modularity. The results are illustrated by some experiments on both real and synthetic data.

heading: 2 Sampling distribution
text: Consider a weighted, undirected, connected graph G = (V,E) of n nodes, without self-loops. Let w(u, v) be equal to the weight of edge {u, v}, if any, and to 0 otherwise. We refer to the weight of node u as:
w(u) = ∑ v∈V w(u, v).
We denote by w the total weight of nodes: w = ∑ u∈V w(u) = ∑ u,v∈V w(u, v).
Observe that the weight of each edge is counted twice in this sum.
Similarly, for any sets A,B ⊂ V , let w(A,B) = ∑
u∈A,v∈B w(u, v),
and w(A) = ∑ u∈A w(u).
Node sampling. The weights induce a probability distribution on node pairs:
∀u, v ∈ V, p(u, v) = w(u, v) w ,
with marginal distribution: ∀u ∈ V, p(u) = ∑ v∈V p(u, v) = w(u) w .
This joint probability distribution is symmetric in the sense that p(u, v) = p(v, u) for all u, v ∈ V . This is the relative frequency of moves from node u to node v by a random walk in the graph, with transition probability:
∀u, v ∈ V, p(v|u) = p(u, v) p(u) = w(u, v) w(u) .
Observe that p(u, u) = 0 for all u ∈ V due to the absence of self-loops in the graph.
Node set sampling. For any partition P of V , the weights induce a probability distribution on P:
∀A,B ∈ P, p(A,B) = w(A,B) w ,
with marginal distribution: ∀A ∈ P, p(A) = ∑ B∈P p(A,B) = w(A) w .
Again, this joint probability distribution is symmetric in the sense that p(A,B) = p(B,A) for all A,B ∈ P. This is the relative frequency of moves from A to B by the random walk.

heading: 3 Representation by a dendrogram
text: Assume the graph G is represented by a dendrogram, that is a rooted binary tree T whose leaves are the nodes of the graph, V . We denote by int(T ) the set of internal nodes of the tree T (all nodes except leaves). For each i ∈ int(T ), a positive number d(i) is assigned to node i, corresponding to its height in the dendrogram. We assume that the dendrogram is regular in the sense that d(i) ≥ d(j) if i is an ancestor of j in the tree. For each i ∈ int(T ), there are two subtrees attached to node i, with sets of leaves A and B; these sets uniquely identify the internal node i so that we can write i = (A,B) = (B,A) and d(i) = d(A,B) = d(B,A).
Ultrametric. The dendrogram defines a metric on V : for each u, v ∈ V , we define d(u, v) = 0 if u = v and d(u, v) = d(i) otherwise, where i ∈ int(T ) is the closest common ancestor of u and v in the corresponding tree. This is an ultrametric in the sense that: ∀u, v, x ∈ V, d(u, v) ≤ max(d(u, x), d(v, x)). Conversely, any ultrametric defines a dendrogram, which can be built from bottom to top by successive merges of the closest nodes, where the distance of the node resulting from the merge of two nodes u and v, which we denote by u ∪ v, to any other node x is defined by:
d(u ∪ v, x) = max(d(u, x), d(v, x)).
Nested clustering. The tree T induces a clustering C of the set of nodes, with A ∈ C if and only if A is the set of leaves of a subtree of T . This is a nested clustering in the sense that: ∀A,B ∈ C, A ⊂ B or A ∩B = ∅. Although C is not a partition of V , we get a probability distribution on cluster pairs by restricting the sampling to cluster pairs A,B such that (A,B) ∈ int(T ):∑
A,B:(A,B)∈int(T )
p(A,B) = ∑
i∈int(T ) ∑ u,v:i=u∧v p(u, v) = ∑ u,v∈V p(u, v) = 1,
where u ∧ v denotes the closest common ancestor of u and v in the tree T .
Graph representation. To assess the quality of the dendrogram, we address the issue of the reconstruction of the graph from the dendrogram. In general, some information about the relative node weights may be known in addition to the dendrogram. Thus we introduce some probability distribution π on V representing this prior information: the distribution π is uniform in the absence of such information and is equal to the sampling distribution p for a perfect knowledge of the relative node weights. Now we look for the best representation of G by a dendrogram d in the sense of the reconstruction of G from d, π, which can be viewed as the autoencoding scheme:
G 7−→ d, π 7−→ Ĝ, where Ĝ is the reconstruction of G.
Since d(u, v) can be interpreted as a distance between u and v, its inverse corresponds to a similarity. Accounting for the prior information about the relative weights of u and v, we define the weight ŵ(u, v) between nodes u, v ∈ V in the graph Ĝ as:
ŵ(u, v) = π(u)π(v)
d(u, v) 1{u6=v}. (1)
Denoting by ŵ the total weight,
ŵ = ∑ u,v∈V ŵ(u, v), (2)
we get the following node pair sampling distribution associated with Ĝ:
p̂(u, v) = ŵ(u, v)
ŵ . (3)
The distance between graphs G and Ĝ can then be assessed through the Kullback-Leibler divergence between the respective sampling distributions,
D(p||p̂) = ∑ u,v∈V p(u, v) log p(u, v) p̂(u, v) ,
which can be written as the relative entropy D(p||p̂) = H(p, p̂)−H(p), where H(p, p̂) = − ∑ u,v∈V p(u, v) log p̂(u, v) and H(p) = − ∑ u,v∈V p(u, v) log p(u, v)
are the cross-entropy between the probability distributions p and p̂ and the entropy of the probability distribution p, respectively. Observe that H(p, p̂) ≥ H(p), with equality if and only if p̂ = p.
Optimization problem. Minimizing the Kullback-Leibler divergence D(p||p̂) in p̂ is equivalent to minimizing the cross-entropy H(p, p̂) in p̂. In view of (1) and (3), we have
H(p, p̂) = H(p, π) + ∑ u,v∈V p(u, v) log d(u, v) + log(ŵ),
where π here denotes the bivariate probability distribution π(u, v) = π(u)π(v). Thus the problem reduces to minimizing the cost function:
J(d) = ∑ u,v∈V p(u, v) log d(u, v) + log  ∑ u,v∈V π(u)π(v) d(u, v)  , over all ultrametrics d defined on V . Observe that J(αd) = J(d) for any α > 0, so that the best ultrametric is defined up to a multiplicative constant. Using the fact that d(u, v) = d(i), where i = u ∧ v is the closest common ancestor of u and v in the tree, we get:
J(d) = ∑
A,B:(A,B)∈int(T )
p(A,B) log d(A,B) + log  ∑ A,B:(A,B)∈int(T ) π(A)π(B) d(A,B)  , (4) with π(A) = ∑ u∈A π(u). The problem of the best representation of G by a dendrogram d now reduces to the optimization problem:
arg min d J(d), (5)
over all ultrametrics d on V .

heading: 4 Optimal representation
text: We seek to solve the optimization problem (5), for some given graph G.
Optimal distances. We first assume that the binary tree T of the ultrametric is given and look for the best corresponding distance d : int(T ) → R+. For each (A,B) ∈ int(T ), we get by the differentiation of (4) in d(A,B),
p(A,B) d(A,B) = λ π(A)π(B) d(A,B)2 ,
where
λ =  ∑ A,B:(A,B)∈int(T ) π(A)π(B) d(A,B) −1 , that is
d(A,B) = λ π(A)π(B)
p(A,B) . (6)
Optimal tree. Replacing d(A,B) by its optimal value (6) in (4), we deduce that the optimization problem (5) reduces to:
arg max T ∑ A,B:(A,B)∈int(T ) p(A,B) log p(A,B) π(A)π(B) . (7)
The dendrogram is then fully determined by (6), for each internal node (A,B) of the tree T . Thus the objective is now to maximize the Kullback-Leibler divergence between two probability distributions on the nested clustering induced by the tree T : p (edge sampling) and π (independent node sampling). It provides a meaningful quality metric for hierarchical clustering, given by: ∑
A,B:(A,B)∈int(T )
p(A,B) log p(A,B)
π(A)π(B) . (8)
A key difference between our metric (8), we refer to as the relative entropy of the hierarchy, and the cost functions proposed in the literature (Dasgupta (2016); Cohen-Addad et al. (2018)) lies in the entropy term:
− ∑
A,B:(A,B)∈int(T )
p(A,B) log p(A,B).
Removing this term from (8) and inversing the sign yields the cost function:∑ A,B:(A,B)∈int(T ) p(A,B)(log π(A) + log π(B)), to be compared with usual cost functions, of the form:∑ A,B:(A,B)∈int(T ) p(A,B)(π(A) + π(B)). (9)
When π is the uniform distribution (no prior information on the node weights), these cost functions become respectively, up to some normalization constant:∑
A,B:(A,B)∈int(T )
p(A,B)(log |A|+ log |B|) and ∑
A,B:(A,B)∈int(T )
p(A,B)(|A|+ |B|).
The latter is Dasgupta’s cost function, equal to the expected size of the smallest cluster containing two random nodes sampled from p.
Consistency. Like Dasgupta’s cost function and its extensions considered in CohenAddad et al. (2018), the objective function (8) is consistent in the sense that, if the original graph has a hierarchical structure, then any solution to the optimization problem (7) is a tree generating the graph:
Proposition 1 Assume that the original graph G is generated by some ultrametric dG, in the sense that
∀u, v ∈ V, w(u, v) = π(u)π(v) dG(u, v) 1{u6=v}.
Then any tree T maximizing (8) is a tree induced by the ultrametric dG.
Proof. We have:
H(p) ≤ min p̂ H(p, p̂) ≤ H(p, π) + min d J(d)
= H(p, π)−max T ∑ A,B:(A,B)∈int(T ) p(A,B) log p(A,B) π(A)π(B) .
Since J(dG) = H(p)−H(p, π), any tree T maximizing the objective function (8) admits an ultrametric d such that J(d) = H(p) − H(p, π). The corresponding sampling distribution p̂, defined by (3), is such that H(p, p̂) = H(p). We deduce that p̂ = p, so that d = αdG for some constant α > 0 and T is a tree associated with the ultrametric dG.
Absence of bias. Another property of the objective function (8) is the absence of bias: if the graph G is a clique, then all trees T have the same relative entropy. This property is also satisfied by Dasgupta’s cost function and its extensions (Cohen-Addad et al. (2018)).
Proposition 2 If the graph G is a clique with unit weights, then all trees T have the same relative entropy (8).
Proof. Let δ = 1/π(u), for some u ∈ V . Observe that this quantity is independent of u. Now for any tree T , we have:∑ A,B:(A,B)∈int(T ) p(A,B) log p(A,B) π(A)π(B) = ∑ A,B:(A,B)∈int(T ) p(A,B) log δ2 n(n− 1) = log δ2 n(n− 1) .

heading: 5 Hierarchical clustering
text: The optimization problem (8) is combinatorial. We believe that it is NP-hard, like the optimization problem associated with Dasgupta’s cost function (Dasgupta (2016)). The optimal distances (6) suggest the following greedy algorithm: start from n clusters (one per node) and successively merge the two closest clusters in terms of inter-cluster distance (6). This is a usual agglomerative algorithm with inter-cluster similarity (so-called linkage):
σ(A,B) = p(A,B)
π(A)π(B) . (10)
The dendrogram is built from bottom to top, with distance σ(A,B)−1 attached to the internal node (A,B) resulting from the merge of clusters A,B. The linkage is reducible, in the sense that: σ(A ∪B,C) ≤ max(σ(A,C), σ(B,C)). This inequality guarantees that the resulting dendrogram is regular (the sequence of distances attached to successive internal nodes is non-decreasing) and that the corresponding distance on V is an ultrametric.
Linkage. For π the uniform distribution (no prior information on the node weights), the linkage (10) is proportional to the usual average linkage:
σ(A,B) ∝ w(A,B) |A||B| ,
corresponding to the density of the cut separating clusters A and B. For π equal to p (perfect knowledge of the node weights), this is the linkage proposed in Bonald et al. (2018):
σ(A,B) = p(A,B)
p(A)p(B) .
Modularity. The linkage (10) can be interpreted in terms of modularity. The modularity of any partition P of the set of nodes V is defined by (Newman and Girvan (2004)):
Q = ∑ C∈P ∑ u,v∈C (p(u, v)− p(u)p(v)).
This is the difference between the probabilities that two nodes belong to the same cluster when sampled from the edges and independently from the nodes, in proportion to their weights. The former sampling distribution depends on the graph while the latter depends on the graph through the node weights only. A more general definition of modularity is:
Q = ∑ C∈P ∑ u,v∈C (p(u, v)− π(u)π(v)), (11)
where π is a probability distribution representing the prior knowledge on the node weights. For instance, it may be uniform (no prior information) or equal to p (the usual definition of modularity, where the information on the relative node weights is known)1.
The problem of modularity maximization generally provides a single clustering. To get clusterings with different granularities, reflecting the multi-scale structure of real graphs, it is common to introduce some positive parameter γ, called the resolution, that controls the respective weights of both terms in the definition of modularity (Reichardt and Bornholdt (2006); Lambiotte et al. (2014); Newman (2016)). The modularity of partition P at resolution γ is defined by:
Qγ = ∑ C∈P ∑ u,v∈C (p(u, v)− γπ(u)π(v)).
1Another common interpretation of modularity is the difference between the proportions of edge weights within clusters in the original graph and in some null model where nodes u and v are linked with probability π(u)π(v); for π the uniform distribution (no prior information on the node weights), the null model is an Erdős-Rényie graph while for π = p (perfect knowledge of the node weights), the null model is the configuration model (Van Der Hofstad (2017)).
When γ → 0, the second term becomes negligible and the best partition P is trivial, with a single cluster equal to the set of nodes V . When γ → +∞, the second term becomes preponderant and the best partition P has n clusters, one per node. Now the maximum resolution beyond which the best partition P has n clusters is given by:
max u6=v
p(u, v)
π(u)π(v) .
The first node pair to be merged (at maximum resolution) is that achieving this maximum, which is the closest pair in terms of linkage (10). The agglomerative algorithm based on linkage (10) can thus be interpreted as the greedy maximization of modularity at maximum resolution.

heading: 6 Experiments
text: In this section, we show how our metric (8) and Dasgupta’s cost function (9) behave on both real and synthetic data. We do not claim that one metric is better than the other and thus the experimental results are presented for illustrative purposes only. We have coded the metrics in Python and grouped the experiments into a Jupyter notebook for the sake of reproducibility 1.
Real data. We consider two real datasets (other real datasets, with more than 1M edges, are available on the Jupyter notebook1):
• Openflights2, a weighted graph of 3,097 nodes and 18,193 edges representing flights between the main airports of the world, the weight between two nodes corresponding to the number of daily round-trip flights between these airports;
• Wikipedia for Schools3, a graph of 4,589 nodes and 106,644 edges representing the links between articles of Wikipedia selected for schools (see West et al. (2009)). The graph is considered as undirected (that is, there is an edge between two nodes if there is a link between the corresponding articles, in either direction). Weights are unitary.
Not surprisingly, both Paris and Newman provide much better hierarchies than the random algorithm. Paris is the best algorithm for the weighted metrics, while Newman is the best algorithm for the unweighted metrics (except on Openflights, where Paris is better than Newman in terms of unweighted Dasgupta’s cost). Considering the weighted metrics as more informative (just like the standard definition of modularity, given by (11) with π = p), both metrics tend to show that Paris provides a better hierarchy than Newman for both graphs.
Synthetic data. To differentiate both metrics, we proceed with the following experiments. We generate two noisy versions of the same graph, say G1 and G2, and return the corresponding hierarchies, say H1 and H2, by some hierarchical clustering algorithm. We then assess the ability of each metric to identify the best hierarchy associated to each graph (e.g., H1 should be better than H2 for graph G1). The classification score (fraction of correct answers) is indicated for each metric and for two algorithms, Paris (in black) and Newman (in grey). Each classification score is based on 1000 samples of the graphs G1 and G2; the original graph G, generated at random, has 100 nodes and the two graphs G1 and G2 are derived from G by replacing some fraction of the edges at random (i.e., one of both ends is chosen uniformly at random among the set of other nodes). The higher the distance between G1 and G2, the easier the classification task (since the corresponding hierarchies H1 and H2 differ more and more) and the higher the classification score.
Both metrics tend to show that the Paris algorithm (in black) provides a better hierarchy than Newman’s algorithm (in grey), the difference being more significant with the RE metric. For both the weighted and unweighted metrics, the best classification score is obtained by RE with the Paris algorithm. For a graph distance of 10%, the corresponding classification score is equal to 94.8% for the weighted metric and 92.5% for the unweighted metric, while it does not exceed 86.8% in all other cases.

heading: 7 Conclusion
text: We have proposed a novel metric for assessing the quality of hierarchical graph clustering, motivated by the problem of reconstruction of the graph from the dendrogram. This metric is the relative entropy between two probability distributions on the corresponding nested clustering, induced by edge sampling and independent node sampling, respectively. We have proved that, like Dasgupta’s cost function, our quality metric is consistent in the sense that, if the original graph has a hierarchical structure, then the best hierarchy according to this metric is the underlying hierarchy of the graph. Experiments on both real and synthetic data tend to show that the relative entropy is both meaningful and significantly different from Dasgupa’s cost. In future work, we would like to better characterize these differences, i.e., to identify the types of hierarchical structures that are best detected by each metric.

Review summaries:
This paper suggests a new metric for assessing the quality of hierarchical clustering. Dasgupta recently suggested the first such metric with interesting properties. This has encouraged a number of recent works about designing algorithms that work well for the metric and other similar metrics. This paper suggests a new metric for evaluating hierarchical clustering of given graph data.