Resumen Técnico: Representaciones Geométricas Compactas de Jerarquías

Planteamiento del Problema

El artículo aborda el desafío de computar representaciones geométricas (embeddings) para la recuperación de datos jerárquicos. En el aprendizaje automático moderno, la recuperación densa suele mapear consultas y documentos en un espacio de embedding compartido donde la relevancia se determina mediante el producto escalar de sus vectores. Si bien este enfoque es efectivo para la recuperación plana, enfrenta desafíos cuando la relevancia se define por razonamientos complejos o estructuras jerárquicas, como los Grafos Acíclicos Dirigidos (DAGs).

Específicamente, el artículo investiga los embeddings de alcanzabilidad. Dado un DAG $G=(V, E)$, el objetivo es construir dos mapeos $a, b: V \to \mathbb{R}^d$ tales que para cualquier par de nodos $u, v$, el producto escalar $\langle a(u), b(v) \rangle > 0$ si y solo si $v$ es alcanzable desde $u$ en $G$ (denotado como $u \leadsto_G v$).

Trabajos previos (You et al., 2025) establecieron que si el número de descendientes para cualquier nodo está acotado por $s$, existen embeddings en una dimensión $O(s \log n)$. Sin embargo, este límite se degrada significamente para jerarquías profundas (por ejemplo, árboles donde $s \approx n$), lo que podría requerir dimensiones proporcionales al número total de nodos. La cuestión central es si existen embeddings compactos cuya dimensión dependa de parámetros estructurales del grafo (como el ancho de árbol o las aristas transversales) en lugar de solo el número total de nodos o la profundidad.

Metodología

Los autores proponen algoritmos constructivos para embeddings de alcanzabilidad que aprovechan parámetros de grafos específicos para lograr dimensiones bajas. La metodología se divide en tres contribuciones teóricas principales:

1. Árboles y Bosques Dirigidos

Para árboles dirigidos enraizados, los autores utilizan los tiempos de descubrimiento y finalización de un recorrido de Búsqueda en Profundidad (DFS) estándar.

• Mecanismo: En un árbol DFS, $v$ es un descendiente de $u$ si y solo si el intervalo $[d_v, f_v]$ está contenido dentro de $[d_u, f_u]$.
• Construcción: Definen vectores en $\mathbb{R}^3$ tales que el producto escalar es igual a $(f_u - d_v)(d_v - d_u)$. Este producto es positivo si y solo si $d_u < d_v < f_u$, lo cual corresponde exactamente a la condición de alcanzabilidad.
• Resultado: Esto produce un embedding de dimensión constante ($d=3$) para cualquier árbol dirigido, independiente del tamaño o la profundidad del árbol.

2. DAGs Parametrizados por Aristas Transversales (Cross-Edges)

Para DAGs generales, los autores extienden el embedding de bosques considerando las "aristas transversales" (aristas en el DAG que no forman parte de un bosque de expansión elegido).

• Mecanismo: Comienzan con el embedding de 3 dimensiones para el bosque de expansión. Para cada arista transversal $(x_i, y_i)$, introducen una coordenada adicional.
• Construcción: La nueva coordenada se activa (con un valor grande $M$) si el nodo de la consulta puede alcanzar a $x_i$ y el nodo del documento es alcanzable desde $y_i$. Un $M$ suficientemente grande asegura que cualquier camino que utilice una arista transversal produzca un producto escalar positivo, mientras que los pares no alcanzables no lo hacen.
• Resultado: La dimensión del embedding es $d = 3 + k$, donde $k$ es el número de aristas transversales.

3. DAGs Parametrizados por Ancho de Árbol (Treewidth)

Para grafos con un ancho de árbol $t$ acotado, los autores emplean una construcción recursiva basada en separadores de vértices balanceados.

• Mecanismo: Utilizando la propiedad de que los grafos con ancho de árbol $t$ tienen separadores de tamaño $\le t+1$ que dividen el grafo en componentes de tamaño máximo $2n/3$, embeben subgrafos de forma recursiva.
• Construcción: El embedding consta de tres partes:
  1. Coordenadas Recursivas: Embeddings para los subcomponentes.
  2. Coordenadas de Separación: Dos coordenadas que imponen una penalización negativa grande en pares $(u, v)$ donde $u$ y $v$ se encuentran en componentes diferentes, evitando falsos positivos a través de la división.
  3. Coordenadas de Conexión: $|S|$ coordenadas (donde $S$ es el separador) que contribuyen con un término positivo grande si existe un camino a través de un vértice del separador.
• Resultado: Esto produce un embedding con una dimensión de $O(t \log n)$.

Contribuciones Clave y Límites Teóricos

El artículo proporciona tanto límites superiores (algoritmos constructivos) como límites inferiores coincidentes o casi coincidentes para la dimensión de embedding requerida para diversas clases de grafos.

Clase de Grafo	Límite Superior (Dimensión)	Límite Inferior (Dimensión)
DAG General	$O(n)$ (implícito)	$\Omega(n)$ (Teorema 6.3)
Árboles Dirigidos	3 (Teorema 3.1)	3 (Lema B.3)
Ancho de Árbol $t$	$O(t \log n)$ (Teorema 5.1)	$\Omega(t / \log(n/t))$ (Teorema 6.7)
Aristas Transversales $k$	$3 + k$ (Teorema 4.1)	$\Omega(k^{1/4})$ y $\Omega(\frac{k \log(n^2/k)}{n \log n})$ (Teoremas 6.8, 6.9)

Percepciones Teóricas Clave:

• Rigidez para Árboles: La dimensión constante de 3 es necesaria incluso para árboles dirigidos pequeños.
• Incomparabilidad: Los autores demuestran, mediante familias de grafos, que los límites basados en el ancho de árbol y las aristas transversales son incomparables; un grafo puede tener un ancho de árbol constante pero $\Omega(n)$ aristas transversales, o viceversa.
• Límites Inferiores: Para DAGs generales, una dimensión lineal $\Omega(n)$ es necesaria. Para un ancho de árbol acotado, la dimensión debe escalar con $t$, aunque el límite inferior es ligeramente más débil que el superior debido a los factores logarítmicos.

Resultados Experimentales

Los autores validan empíricamente su enfoque constructivo en conjuntos de datos jerárquicos del mundo real: WordNet (82k nodos), Gene Ontology (24k nodos) y Cora (2.7k nodos).

• Método: Implementaron la construcción basada en el separador recursivo (Sección 5) y la compararon con los "Embeddings Hechos a Mano" de You et al. (2025), que suman vectores de ancestros normalizados.
• Desempeño:
  • WordNet: El método propuesto logró un 100% de recall en una dimensión de 152. El baseline requirió una dimensión de 512 para alcanzar un 95% de recall y solo logró ~51% de recall en dimensión 128.
  • Cora y Gene Ontology: Se observaron tendencias similares, con el método propuesto garantizando la recuperación exacta en dimensiones significativamente menores a las requeridas por el baseline para lograr un alto recall.
• Significancia: Los experimentos confirman que el límite teórico de $O(t \log n)$ se sostiene en la práctica con factores constantes modestos, y que el método constructivo supera a los enfoques heurísticos previos en regímenes de alto recall.

Significancia y Reivindicaciones

El artículo afirma resolver la pregunta abierta de si existen embeddings finos para la recuperación jerárquica que estén parametrizados por propiedades estructurales del grafo en lugar de solo por el número total de nodos.

• Impacto Teórico: Establece que para árboles dirigidos, la alcanzabilidad puede capturarse en una dimensión constante (3), lo que representa una mejora significativa respecto a los límites previos que escalaban con la altura del árbol. Generaliza esto a grafos con ancho de árbol acotado, ofreciendo una dimensión de $O(t \log n)$.
• Impacto Práctico: La naturaleza constructiva de los embeddings permite la generación determinista y rápida sin un entrenamiento costoso (a diferencia de los embeddings aprendidos). El método garantiza un 100% de recall, mientras que los baselines aprendidos a menudo sacrifican la exactitud por dimensiones más bajas.
• Limitaciones: Los autores señalan que, si bien los límites son ajustados para los árboles, existe una brecha entre los límites superiores e inferiores para grafos parametrizados por ancho de árbol. Además, el método depende de encontrar buenos separadores de vértices, lo cual es un problema de aproximación en la práctica.

El trabajo proporciona una base rigurosa para representar jerarquías en espacios geométricos, demostrando que los parámetros estructurales como el ancho de árbol y las aristas transversales son las lentes correctas a través de las cuales ver la complejidad de los embeddings de alcanzabilidad.