Compact Geometric Representations of Hierarchies

This paper introduces compact reachability embeddings for hierarchical structures in directed graphs, demonstrating that a directed tree can be represented with a constant-dimensional embedding of size 3, regardless of its size or depth. It extends this to graphs with treewidth \( t \), providing embeddings of dimension \( O(t \log n) \) and establishing necessary lower bounds for general DAGs and treewidth \( t \). These findings are significant for practitioners in machine learning, as they enable more efficient representations of hierarchical data, potentially improving retrieval tasks in large-scale applications.