Tree Sampling Divergence: An Information-Theoretic Metric for Hierarchical Graph Clustering

1 Introduction

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, 2007].

Hierarchical graph clustering is a common technique for the analysis of the multi-scale structure of large graphs. Rather than looking for a simple partition of the set of nodes, as in usual clustering techniques, the objective is to represent the graph by some rooted binary tree, whose leaves are the nodes of the graph. This tree can then be used to find relevant clusterings at different resolutions by suitable cuts at different levels of the tree.

∗Contact Author.

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; Huang et al., 2010; Chang et al., 2011; Tremblay and Borgnat, 2014; Bateni et al., 2017; 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 a simple clustering [Newman and Girvan, 2004].

A cost function has recently been proposed by Dasgupta [Dasgupta, 2016] to assess the quality of a hierachical clustering and has been further analysed and extended in [Roy and Pokutta, 2016; Cohen-Addad et al., 2017; Cohen-Addad et al., 2018]; it can be viewed as the expected size of the smallest cluster encompassing two nodes sampled at random from the edges of the graph.

In this paper, we assess the quality of a hierarchical clustering through the Kullback-Leibler divergence between two probability distributions over the nodes of the tree: those induced respectively by sampling clusters encompassing random edges and node pairs of the graph. We refer to this metric as Tree Sampling Divergence (TSD). If the tree captures the hierarchical structure of the graph, the TSD tends to be large since most edges are sampled from nodes belonging to small clusters of the graph (i.e., deep nodes of the tree), whereas most node pairs, sampled independently, belong to large clusters of the graph (i.e., shallow nodes of the tree, close to the root).

A fundamental property of the proposed metric is that it is interpretable in terms of graph reconstruction. Specifically, it quantifies the ability to reconstruct the graph from the tree. In particular, the TSD is maximum when perfect reconstruction is feasible, i.e., when the graph has a full hierarchical structure and can be reconstructed exactly from the corresponding tree. While a similar property has been proved in [CohenAddad et al., 2018] for Dasgupta's cost, this applies only to a graph that has a full hierarchical structure, when perfect reconstruction is possible; there is no interpretation in terms of graph reconstruction for an arbitrary graph. The TSD quantifies the gap to perfect reconstruction for any graph: this gap is exactly the information lost in the reconstruction of the graph.

Another key property of TSD is that it applies to any tree, not necessarily binary. In particular, the TSD applies to trees of height 2, corresponding to the case of usual clustering (not hierarchical) where the output is a partition of the set of nodes. The TSD can thus be viewed as a universal metric, applicable to any type of clustering. Moreover, the TSD can be used in practice to compress a binary tree while minimizing the information loss in terms of graph reconstruction, so as to get a compact representation of the hierarchical structure of a graph.

The paper is structured as follows. We first introduce in sections 2 and 3 the notions of graph sampling and graph distance, which play a key role in our approach. The Tree Sampling Divergence (TSD) is presented in section 4. In section 5, we show how to compute the TSD in practice through graph aggregation. The properties of the TSD in terms of graph reconstruction are presented in section 6. The case of general trees is considered in section 7, the practically interesting case of flat clustering (trees of height 2) being presented in section 8. Some extensions of the TSD are described in section 9. The behavior of the TSD is illustrated by experiments on both synthetic and real data in section 10. Section 11 concludes the paper.

2 Graph Sampling

Consider a weighted, undirected, connected graph G = (V,E) of n nodes and m edges. 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:

We denote by w the total weight of nodes:

These weights induce two ways to sample the graph.

Edge sampling. Sampling edges at random in proportion to their weights yields the following joint probability distribution on V :

This distribution is symmetric in the sense that:

Observe that the graph G is fully characterized by its edge sampling distribution P and its total weight w, since the weight of edge u, v is given by w(u, v) = wP (u, v).

Node sampling. Sampling nodes at random in proportion to their weights yields the following probability distribution on V :

This is the marginal distribution of the edge sampling distribution:

Observe that the graph structure cannot be recovered from the node sampling distribution. The best reconstruction given this distribution and the total weight w consists in assigning the weight wP(u)P(v) to edge u, v. Following Newman [Newman and Girvan, 2004], we refer to this graph as the null model associated to graph G.

3 Graph Distance

We have seen that any graph is characterized by its edge sampling distribution and its total weight. Thus the edge sampling distribution can be used to define a distance between two graphs, up to some multiplicative constant on the edge weights. Specifically, let G1, G2 be two graphs over the same set of nodes V and denote by P1, P2 the corresponding edge sampling distributions. We define the distance between G1 and G2 by the Kullback-Leibler divergence between P1 and P2, that is:

Observe that, like the Kullback-Leibler divergence, this distance is not symmetric. The graphs G1 and G2 are equivalent for this distance, in the sense that D(G1, G2) = 0, if and only if P1 = P2, i.e., edge weights are equal up to a multiplicative constant.

The above distance can be used to quantify the difference between the graph G and its null model. This distance is:

the mutual information between nodes when sampled from the edges. This is a simple yet meaningful metric to quantify the clustering structure of the graph: if nodes are organized in clusters, the mutual information between two nodes u, v sampled from an edge is expected to be large (given node u, you get information on the other node v); on the other hand, if the graph has no clustering structure (e.g., a complete graph), then the mutual information between two nodes u, v sampled from an edge is small (given node u, you have little information on the other node v; this information is null for a complete graph).

We shall see in section 6 that the mutual information I is directly related to our metric: this is the maximum value of the TSD, which is attained by a tree if and only if perfect graph reconstruction from this tree is feasible.

4 Tree Sampling Divergence

Consider some hierarchical clustering of a graph, represented as a rooted binary tree whose leaves are the nodes of the graph. For any u, v ∈ V , we denote by u ∧ v the closest common ancestor of leaves u and v in the tree.

Let T be the set of nodes of the tree. Note that V ⊂ T and |T| = 2n - 1. The graph sampling distributions introduced in section 2 induce the following probability distributions on T :

and

The former is that induced by edge sampling while the latter is that induced by independent node sampling. Equivalently, these are the distributions induced by edge sampling for the original graph and the null model, respectively. We expect these distributions to differ significantly if the tree indeed represents the hierarchical structure of the graph. Specifically, we expect p to be mostly concentrated on deep nodes of the tree (far from the root), as two nodes u, v connected with high weight w(u, v) in the graph typically belong to a small cluster, representative of the clustering structure of the graph; on the contrary, we expect q to be concentrated over shallow nodes (close to the root) as two nodes u, v sampled independently at random typically belong to large clusters, less representative of the clustering structure of the graph.

This motivates the following metric for the quality of the tree T as hierarchical structure of the graph:

This is the Kullback-Leibler divergence 1 between the probability distributions p and q. The larger the divergence, the better the tree for representing the graph. In the following, we refer to this metric as the Tree Sampling Divergence (TSD). We shall see in section 6 that the quantity I -Q, with I given by (1), can be interpreted in terms of information loss in the problem of graph reconstruction from the tree.

5 Graph Aggregation

The sampling distributions p, q can be simply computed by graph aggregation (see Algorithm 1). The algorithm consists in iteratively merging two nodes u, v of the graph that are leaves of the tree into a single node x = u ∧ v, their common parent in the tree. This node has weight:

and a self-loop with weight:

in the aggregate graph. We get the sampling probabilities of node x ∈ T as:

and the TSD follows from (2).

6 Graph Reconstruction

We consider the problem of graph reconstruction from the tree. Specifically, given the tree T and the weights of nodes, we would like to build some graph ˆG that is as close as possible to G. The hierarchical clustering can then be viwed as

1 Note that Q is finite since the support of q is T (because P (u) > 0 for each u ∈ V ).

Algorithm 1: Computation of TSD (binary trees)

Input: Graph G = (V, E) with sampling distribution P ;

Tree T Output: Tree sampling distributions p, q 1 for x ∈ V do 2 p(x) ← P (x, x); q(x) ← P (x)2 3 while |V | > 1 do 4 u, v ← leaves of the tree T, with common parent x // aggregate nodes u, v into x 5 V ← V \ {u, v}; V ← V ∪ {x} // update P 6 for y neighbor of u or v do 7 if y ̸= x then 8 P (x, y) ← P (u, y) + P (v, y); P (y, x) ← P (x, y) 9 else 10 P (x, x) ← P (u, u) + P (v, v) + 2P (u, v) 11 P (x) ← P (u) + P (v) // update p, q 12 p(x) ← P (x, x); q(x) ← P (x)2 // update T 13 T ← T \ {u, v}

the latent representation of the graph G in the auto-encoding process:

We first need to define the decoding scheme, that is the process to build some graph ˆG from the tree T. To do this, we assign some weight σ(x) to each node x ∈ T \ V . This corresponds to the weight of cluster x and will be determined so as to minimize the distance between the original graph G and its reconstruction ˆG. We let the weight of edge u, v in graph ˆG equal to:

Thus the weight of edge u, v is proportional to the respective weights of nodes u, v and to the weight of their smallest common cluster u ∧ v, as given by the tree.

It remains to find the cluster weights σ that minimize the distance between the original graph G and its reconstruction ˆG. For this, we use the graph distance defined in section 3, corresponding to the Kullback-Leibler divergence between the corresponding edge sampling distributions, P and ˆ P . Observe that:

with:

We obtain:

where I , given by (1), is the mutual information between nodes when sampled from the edges and

Observe that I is independent of ˆ P so that J is the quantity to be maximized. Finding where the derivative of J with respect to σ(x) is equal to 0 yields:

We get:

For this optimal value of σ, we obtain:

which is equal to Q, the tree sampling divergence.

Finally, the optimal reconstruction of the graph corresponds to the sampling distribution:

and the distance between the original graph G and its optimal reconstruction G⋆ is:

We deduce that the information loss in the optimal autoencoding process G → T → G⋆ is I - Q. In particular, Q ≤ I, with equality if and only if perfect reconstruction from the tree T is possible.

7 Tree Compression

While existing quality metrics are typically defined for binary trees (see for instance Dasgupta's cost and extensions in [Cohen-Addad et al., 2017]), the TSD equally applies to general trees. The definition is exactly the same. As for the computation, Algorithm 1 applies except that the aggregation must be applied simultaneously to all leaves of the tree having the same parent (see Algorithm 2).

Algorithm 2: Computation of TSD (general trees)

This is a very interesting property as dense trees are sought in practice, the information provided by a binary tree being to rich to be directly exploited by data scientists or engineers. Moreover, it provides a way to compress a binary tree in an optimal way, by minimizing the information loss caused by tree compression. In view of (2), the information loss caused by the merge of cluster x ∈ T (internal node of the tree) with its parent y is:

Observe that the merge of x and y does not modify the edge sampling distributions on the other nodes of the tree. In particular, the information loss ∆(x, y) can be computed for all branches of the tree, with a complexity in O(n) given p and q, and successive merges be done in increasing order of these information losses. The stopping criterion may be related to some target number of internal nodes in the tree, or some maximum total information loss.

8 Graph Clustering

Since the TSD applies to any tree, it applies in particular to trees of height 2, corresponding to usual graph clustering (i.e., a partition of the nodes).

Let C1, . . . ,CK be K clusters, forming a partition of V . This can be represented as a tree of height 2, with k internal nodes x1, . . . , xK at level 1 (the clusters) and n leaves at level 2 (the nodes of the graph). For each cluster k = 1, . . . , K, we have:

where

denotes the internal weight of cluster k (total weight of edges within the cluster). Similarly,

where

denotes the weight of cluster k (total weight of nodes in the cluster). Assuming that there are no self loops, we get for the root, which we denote by 0,

Thus the TSD takes the form:

This is a novel metric for evaluating the quality of a clustering, different from modularity [Newman and Girvan, 2004], the usual metric given by:

The key property of the TSD is that it quantifies the ability to reconstruct the graph in terms of information loss; this applies to any tree and thus to usual graph clustering as well. There is no such interpretation with modularity.

9 Extensions

The TSD can be extended in several ways. First, the node pair sampling distribution q can be replaced by the uniform distribution (i.e., the null model is the complete graph). This boils down to the initialization P(x) ← 1n for all x ∈ V before applying Algorithm 1 or 2. Second, the Kullback-Leibler divergence can be replaced by some other divergence, like the square Euclidean distance between the probability measures, ∑x∈T (p(x)-q(x))2 . The experiments presented below suggest however that it is preferable to use the Kullback-Leibler divergence.

10 Experiments

The Python code and the datasets used for the experiments are available online 2 .

Graph Representation

We first show how TSD is able to detect the quality of a tree in terms of graph representation. For this, we generate two noisy versions of the same graph, say G1 and G2, and return the corresponding trees, say T1 and T2, by the hierarchical clustering algorithm described in [Bonald et al., 2018]. We then assess the ability of TSD to identify the best tree associated to each graph (e.g., T1 should be better than T2 for graph G1). The classification score (in proportion of correct answers) is given in Table 1 for two metrics, TSD and Dasgupta's cost. Each classification score is based on 1000 samples of the graphs G1 and G2; the original graph G, generated at random from a random hierarchy, has 100 nodes and average degree 10; the two graphs G1 and G2 are derived from G by replacing some random subset of the edges at random (the higher the noise, the easier the classification task).

Graph Reconstruction

Next, we show how TSD captures the quality of a tree in terms of graph reconstruction. To this end, we consider a hierarchical stochastic block model (HSBM) of 80 nodes and 3 levels of hierarchy (binary tree with clusters of 10 nodes on leaves) with different parameters, see [Lyzinski et al., 2017]. For each graph, we apply various graph clustering algorithms, so as to get hierarchies of different qualities. The reconstruction procedure is that described in section 6.

Figure 1 shows the quality of the reconstruction for usual scores (detailed below) with respect to the quality / cost of the hierarchy, for three metrics: TSD, Dasgupta's cost, and the version of the TSD based on the Euclidean distance, we refer to as the Euclidean divergence (see section 9). The results suggest that TSD is the best metric in terms of graph reconstruction, with a clear correlation between the metric and the reconstruction scores. The correlation is also present but more noisy for Dasgupta's cost; there is no correlation with the Euclidean divergence.

The quality of the reconstruction is based on the following classical scores [Bordes et al., 2013; Nickel and Kiela, 2017; Nickel et al., 2016; Bojchevski and G¨unnemann, 2018]. First, keeping all edges of the reconstructed graph whose weight is larger than some threshold provides a set of graphs with different false positive and false negative rates, from which we get the Area Under ROC Curve (AUC) and the Average Precision Score (APS). Second, we compute the rank of each edge of the original graph among all possible edges ending in one of the two nodes in the reconstructed graph, in decreasing order of weights. This rank score is averaged over all nodes and normalized by the number of nodes to get a score between 0 and 1; the lower the rank, the better the reconstruction.

2 See https://github.com/sharpenb/Tree-Sampling-Divergence.

Tree Compression

Next, we show the pratical interest of TSD in terms of tree compression. We consider OpenFlights 3 , a weighted graph of 3,092 nodes and 18,193 edges representing flights between the main airports of the world. We first apply the hierarchical clustering algorithm described in [Bonald et al., 2018] then apply the algorithm described at the end of section 7 to compress the resulting tree with minimum information loss. Specifically, we merge 3, 000 levels among the 3, 092 levels of the original binary tree.

The results are shown in Figure 2, together with a clustering derived from this compressed tree. We observe that the compressed tree still captures the hierarchical structure of the graph, despite the very high compression rate applied here (only 3% of the hierarchical levels are retained). The compressed tree is clearly much easier to exploit in practice than the original tree.

3 https://openflights.org

(a) Binary tree (3092 levels)

• (c) Clustering extracted from the compressed tree (20 clusters)

Figure 2: Tree compression on the Openflights graph.

11 Conclusion

We have presented a novel quality metric for hierarchical graph clustering. This metric, inspired by information theory, reflects the ability to reconstruct the initial graph from a hierarchy representing this graph. It is applicable to general trees (not only binary trees) and can be used for tree compression.