Timezone: »

 
Tree Covers: An Alternative to Metric Embeddings
Roshni Sahoo · Ines Chami · Christopher Ré

Fri Dec 11 08:30 AM -- 09:30 AM (PST) @
in Differential Geometry meets Deep Learning (DiffGeo4DL) »

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.

Author Information

Roshni Sahoo (Stanford University)
Ines Chami (Stanford University)
Christopher Ré (Stanford)

More from the Same Authors