{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,8,7]],"date-time":"2024-08-07T07:32:38Z","timestamp":1723015958961},"publisher-location":"California","reference-count":0,"publisher":"International Joint Conferences on Artificial Intelligence Organization","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2019,8]]},"abstract":"<jats:p>We introduce the tree sampling divergence (TSD), an information-theoretic metric for assessing the quality of the hierarchical clustering of a graph. \nAny hierarchical clustering of a graph can be represented as a tree whose  nodes  correspond to   clusters of the graph. The TSD is the Kullback-Leibler divergence between two probability distributions over the nodes of this tree: those induced respectively by  sampling   at random edges and   node pairs of the graph. \nA 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 terms of information loss. In particular, the TSD  is maximum when perfect reconstruction is feasible, i.e., when the graph has a complete  hierarchical structure.\nAnother key property of TSD is that it applies to any tree, not necessarily binary. \nIn particular, the TSD can be used 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. \nWe illustrate the behavior of TSD compared to existing metrics on  experiments based on both synthetic and real datasets.<\/jats:p>","DOI":"10.24963\/ijcai.2019\/286","type":"proceedings-article","created":{"date-parts":[[2019,7,28]],"date-time":"2019-07-28T07:46:05Z","timestamp":1564299965000},"page":"2067-2073","source":"Crossref","is-referenced-by-count":1,"title":["Tree Sampling Divergence: An Information-Theoretic Metric for Hierarchical Graph Clustering"],"prefix":"10.24963","author":[{"given":"Bertrand","family":"Charpentier","sequence":"first","affiliation":[{"name":"Technical University of Munich"}]},{"given":"Thomas","family":"Bonald","sequence":"additional","affiliation":[{"name":"Telecom ParisTech"}]}],"member":"10584","event":{"number":"28","sponsor":["International Joint Conferences on Artificial Intelligence Organization (IJCAI)"],"acronym":"IJCAI-2019","name":"Twenty-Eighth International Joint Conference on Artificial Intelligence {IJCAI-19}","start":{"date-parts":[[2019,8,10]]},"theme":"Artificial Intelligence","location":"Macao, China","end":{"date-parts":[[2019,8,16]]}},"container-title":["Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence"],"original-title":[],"deposited":{"date-parts":[[2019,7,28]],"date-time":"2019-07-28T07:48:16Z","timestamp":1564300096000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ijcai.org\/proceedings\/2019\/286"}},"subtitle":[],"proceedings-subject":"Artificial Intelligence Research Articles","short-title":[],"issued":{"date-parts":[[2019,8]]},"references-count":0,"URL":"https:\/\/doi.org\/10.24963\/ijcai.2019\/286","relation":{},"subject":[],"published":{"date-parts":[[2019,8]]}}}