Recovering tree models via spectral graph theory

Modeling data by latent tree models is a powerful approach in multiple applications. A canonical example of this setting is the “tree of life”, where the evolutionary history of a set of organisms is inferred by their DNA. Generally, in latent tree models, the main task is to infer the structure of the tree, given only observations of its terminal nodes. While inferring a tree structure is a common task, in many applications, a robust algorithm for the recovery of large trees is still missing.

In this talk, we will see a new method for the recovery of latent tree models, which is based on spectral graph theory. We show that the hidden tree structure is strongly related to the spectral properties of a graph, defined over the terminal nodes of the tree. Finally, we see that while in terms of accuracy the method performs similarly to state-of-the-art methods, it is significantly more computationally efficient.