Workshop: Differential Geometry meets Deep Learning (DiffGeo4DL)

Tree Covers: An Alternative to Metric Embeddings

Roshni Sahoo · Ines Chami · Christopher RĂ©


We study the problem of finding distance-preserving graph representations. Most previous approaches focus on learning continuous embeddings in metric spaces such as Euclidean or hyperbolic spaces. Based on the observation that embedding into a metric space is not necessary to produce faithful representations, we explore a new conceptual approach to represent graphs using a collection of trees, namely a tree cover. We show that with the same amount of storage, covers achieve lower distortion than learned metric embeddings. While the distance induced by covers is not a metric, we find that tree covers still have the desirable properties of graph representations, including efficiency in query and construction time.

Chat is not available.