Compact Geometric Representations of Hierarchies

• URL: http://arxiv.org/abs/2606.18520v1
• Date: Tue, 16 Jun 2026 22:20:52 GMT
• Title: Compact Geometric Representations of Hierarchies
• Abstract summary: We prove that for any directed tree, there exists a reachability embedding in constant dimension 3, independent of the tree's size or depth.<n>We provide theoretical guarantees for representing hierarchies using embeddings whose dimension depends on structural graph parameters.<n>Our embeddings can be constructed on real world datasets, and that they give much smaller dimensions in high recall regimes.
• Score: 20.884220139918014
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Computing geometric representations of data is a cornerstone of modern machine learning, typically achieved by training dual encoders which map queries and documents into a shared embedding space. Recent work of You et al. [NeurIPS '25] has extended this approach to hierarchical retrieval, where relevance is determined by the ancestor-descendant relationships in a Directed Acyclic Graph (DAG). While previous work has shown that valid embeddings exist when the number of descendants is small, these bounds degrade significantly for deep hierarchies, requiring dimensions as large as the total number of nodes. In this paper, we investigate compact reachability embeddings for more general graph classes and provide theoretical guarantees for representing hierarchies using embeddings whose dimension depends on structural graph parameters. We prove that for any directed tree, there exists a reachability embedding in constant dimension 3, independent of the tree's size or depth. We generalize this result to graphs characterized by treewidth $t$, constructing embeddings of dimension $O(t \log n)$, where $n$ is the number of nodes. Complementing these upper bounds, we provide matching or near-matching lower bounds, showing that dimension $Ω(n)$ is necessary for general DAGs and $Ω(t/\log(n/t))$ is required for graphs of treewidth $t$. We also obtain upper and lower bounds parameterized by the number of cross-edges in the DAG. We additionally show that our embeddings can be constructed on real world datasets, and that they give much smaller dimensions in high recall regimes compared to prior embeddings with theoretical guarantees.

Related papers

• GraphTreeGen: Subtree-Centric Approach to Efficient and Supervised Graph Generation [6.138671548064356]
  GraphTreeGen (GTG) is a subtree-centric generative framework for efficient, accurate connectome synthesis.<n>GTG decomposes each connectome into entropy-guided k-hop trees capturing informative local structure.<n>Its modular design enables extensions to connectome super-resolution and cross-modality synthesis.
  arXiv  Detail & Related papers  (2025-08-13T11:02:38Z)
• The Geometry of Meaning: Perfect Spacetime Representations of Hierarchical Structures [0.0]
  We show that there is a fast algorithm that embeds hierarchical structures in three-dimensional Minkowski spacetime.<n>Our results seem to indicate that all discrete data has a perfect geometrical representation that is three-dimensional.
  arXiv  Detail & Related papers  (2025-05-07T20:41:06Z)
• Generalization, Expressivity, and Universality of Graph Neural Networks on Attributed Graphs [53.27010448621372]
  We analyze the universality and generalization of graph neural networks (GNNs) on attributed graphs with node attributes.<n>We prove a universal approximation theorem for GNNs and bounds generalization for GNNs on any data distribution of attributed graphs.<n>Our work extends and unites previous approaches which either derived theory only for graphs with no attributes, derived compact metrics under which GNNs are continuous but without separation power, or derived metrics under which GNNs are continuous and separate points.
  arXiv  Detail & Related papers  (2024-11-08T10:34:24Z)
• Heterogeneous Graph Neural Network on Semantic Tree [11.810900066591861]
  HetTree is a novel HGNN that models both the graph structure and heterogeneous aspects in a scalable and effective manner.<n>To effectively encode the semantic tree, HetTree uses a novel subtree attention mechanism to emphasize metapaths that are more helpful in encoding parent-child relationships.<n>Our evaluation of HetTree on a variety of real-world datasets demonstrates that it outperforms all existing baselines on open benchmarks.
  arXiv  Detail & Related papers  (2024-02-21T03:14:45Z)
• Hierarchical Aggregations for High-Dimensional Multiplex Graph Embedding [7.271256448682229]
  HMGE is a novel embedding method based on hierarchical aggregation for high-dimensional multiplex graphs. We leverage mutual information between local patches and global summaries to train the model without supervision. Detailed experiments on synthetic and real-world data illustrate the suitability of our approach to downstream supervised tasks.
  arXiv  Detail & Related papers  (2023-12-28T05:39:33Z)
• Data Topology-Dependent Upper Bounds of Neural Network Widths [52.58441144171022]
  We first show that a three-layer neural network can be designed to approximate an indicator function over a compact set. This is then extended to a simplicial complex, deriving width upper bounds based on its topological structure. We prove the universal approximation property of three-layer ReLU networks using our topological approach.
  arXiv  Detail & Related papers  (2023-05-25T14:17:15Z)
• Hierarchical clustering with dot products recovers hidden tree structure [53.68551192799585]
  In this paper we offer a new perspective on the well established agglomerative clustering algorithm, focusing on recovery of hierarchical structure. We recommend a simple variant of the standard algorithm, in which clusters are merged by maximum average dot product and not, for example, by minimum distance or within-cluster variance. We demonstrate that the tree output by this algorithm provides a bona fide estimate of generative hierarchical structure in data, under a generic probabilistic graphical model.
  arXiv  Detail & Related papers  (2023-05-24T11:05:12Z)
• Tight and fast generalization error bound of graph embedding in metric space [54.279425319381374]
  We show that graph embedding in non-Euclidean metric space can outperform that in Euclidean space with much smaller training data than the existing bound has suggested. Our new upper bound is significantly tighter and faster than the existing one, which can be exponential to $R$ and $O(frac1S)$ at the fastest.
  arXiv  Detail & Related papers  (2023-05-13T17:29:18Z)
• Hierarchies over Vector Space: Orienting Word and Graph Embeddings [14.367560758244624]
  We present a data structure that captures inherent hierarchical properties from an unordered flat embedding space. Inspired by the notion of textitdistributional generality, our algorithm constructs an arborescence (a directed rooted tree) by inserting nodes in descending order of entity power. We evaluate the performance of the resulting tree structures on three tasks: hypernym relation discovery, least-common-ancestor (LCA) discovery among words, and Wikipedia page link recovery.
  arXiv  Detail & Related papers  (2022-11-02T18:54:44Z)
• Geometric Graph Representation Learning via Maximizing Rate Reduction [73.6044873825311]
  Learning node representations benefits various downstream tasks in graph analysis such as community detection and node classification. We propose Geometric Graph Representation Learning (G2R) to learn node representations in an unsupervised manner. G2R maps nodes in distinct groups into different subspaces, while each subspace is compact and different subspaces are dispersed.
  arXiv  Detail & Related papers  (2022-02-13T07:46:24Z)
• Graph Neural Networks with Composite Kernels [60.81504431653264]
  We re-interpret node aggregation from the perspective of kernel weighting. We present a framework to consider feature similarity in an aggregation scheme. We propose feature aggregation as the composition of the original neighbor-based kernel and a learnable kernel to encode feature similarities in a feature space.
  arXiv  Detail & Related papers  (2020-05-16T04:44:29Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.