Low Distortion Delaunay Embedding of Trees in Hyperbolic Plane

By Rik Sarkar. International Symposium Graph Drawing and Network Visualization, 2011

310 citations recorded by the source corpus.

Subfields: Computer Graphics and Computer-Aided Design, Mathematical Physics, Signal Processing

View Paper: https://www.semanticscholar.org/paper/5731795f184b2a5431fc909a0ce8bf7a9ec2c762

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Graphics and Computer-Aided Design

1. Ali Razavi
2. David Raposo
3. Mateusz Malinowski
4. Timothy M. Hospedales
5. Jure Leskovec
6. Misha Denil
7. Nando de Freitas
8. Christopher De Sa

In Mathematical Physics

1. Jure Leskovec
2. Nando de Freitas
3. Christopher De Sa
4. Razvan Pascanu
5. Christopher R'e
6. Qingxuan Jiang
7. Isay Katsman
8. Ines Chami

In Signal Processing

1. Christopher R'e
2. Albert Gu
3. Caglar Gulcehre
4. Christopher De Sa
5. Jure Leskovec
6. Ali Razavi
7. David Raposo
8. Thomas Hofmann

Citations in the corpus

• Hyperbolic Graph Convolutional Neural Networks (2019, methodology): “However, the volume of balls in Euclidean space only grows polynomially with respect to the radius, which leads to high distortion embeddings [34, 35], while in hyperbolic space, this volume grows exponentially.”
• Differentiating through the Fréchet Mean (2020, background): “Later analyses by Sarkar (2011) and Sala et al. (2018) demonstrate the empirical and theoretical improvement of this approach.”
• Hyperbolic Entailment Cones for Learning Hierarchical Embeddings (2018, background): “This exponential growth property enables hyperbolic spaces to embed any weighted tree while almost preserving their metric 3 (Gromov, 1987; Bowditch, 2006; Sarkar, 2011).”
• Representation Tradeoffs for Hyperbolic Embeddings (2018, background): “In fact, it is possible to embed trees into the Poincaré disk H2 with arbitrarily low distortion (Sarkar, 2011). Remarkably, trees cannot be embedded into Euclidean space with arbitrarily low distortion for any number of dimensions. These notions motivate the following two-step process for embedding”
• GEMSEC: Graph Embedding with Self Clustering (2018, unknown): “Representations in hyperbolic spaces have emerged as a technique to preserve richer network structures [22], [23], [24].”
• Hyperbolic Attention Networks (2018, background): “Moreover, Sarkar [35] describes a construction that embeds trees in two-dimensional hyperbolic space with arbitrarily low distortion, which is not possible in Euclidean space of any dimension [23].”
• Multi-relational Poincaré Graph Embeddings (2019, background): “Certain knowledge graph relations, such as “hypernym” and “has_part”, induce a hierarchical structure over entities, suggesting that embedding them in hyperbolic rather than Euclidean space may lead to improved representations [26, 23, 24, 12, 30].”
• Hyperbolic Image Embeddings (2019, unknown): “, tree graphs) with low distortion [39, 40].”