Neural Scalable Symbolic Search Framework for Complex Logical Queries with Multiple Free Variables

Resumen Técnico: Marco de Búsqueda Simbólica Escalable Neural para Consultas Lógicas Complejas con Múltiples Variables Libres

Planteamiento del Problema
La respuesta a consultas complejas (CQA) sobre Grafos de Conocimiento (KG) incompletos es una tarea fundamental para el razonamiento y el descubrimiento de conocimiento. Si bien se han logrado avances significativos en la respuesta a consultas de lógica de primer orden existencial con una sola variable libre ($EFO_1$), la respuesta a consultas con $k$ variables libres ($EFO_k$) sigue siendo un cuello de botella crítico. El principal desafío reside en el crecimiento exponencial del espacio de respuestas candidatas ($E^k$, donde $E$ es el conjunto de entidades). Las metodologías y puntos de referencia existentes dependen típicamente de clasificaciones marginales, donde cada variable libre se clasifica de forma independiente. Sin embargo, las clasificaciones marginales son un mal proxy para la verdadera clasificación conjunta de las tuplas de respuesta, fallando a menudo en eliminar combinaciones inválidas (por ejemplo, si la respuesta verdadera es $(1,3)$, las clasificaciones marginales podrían validar incorrectamente $(1,2)$). Además, la inferencia conjunta exhaustiva sobre $E^k$ es computacionalmente prohibitiva para KGs realistas, y los métodos existentes basados en redes neuronales-simbólicas o incrustaciones luchan por escalar a la inferencia conjunta multivariable sin sacrificar precisión o eficiencia.

Metodología: Búsqueda Simbólica Escalable Neural (NS3)
Los autores proponen Búsqueda Simbólica Escalable Neural (NS3), un marco presupuestado diseñado para aproximar clasificaciones conjuntas para consultas $EFO_k$ sin enumerar todo el espacio $E^k$. NS3 extiende los métodos de búsqueda neural-simbólica (originalmente desarrollados para $EFO_1$) controlando explícitamente el espacio de búsqueda conjunta a través de tres mecanismos centrales:

1. Marginalización como Condición Necesaria: El marco resuelve primero subconsultas marginalizadas (cuantificando existencialmente subconjuntos de variables libres) para obtener conjuntos candidatos necesarios. Estos resultados marginales sirven como un mecanismo de poda; cualquier tupla que viole una restricción marginal se descarta de forma segura. Este paso aprovecha las capacidades existentes de búsqueda simbólica para estimar eficientemente los conjuntos de respuestas marginales.
2. Transformación de Fusión (Hipernodos): Para habilitar el razonamiento conjunto, NS3 fusiona múltiples variables libres con dominios podados en un único hipernodo. El dominio de este hipernodo representa el producto cartesiano de los dominios de las variables individuales, pero está significativamente reducido en función de los resultados de la poda marginal.
3. Presupuestación Progresiva y Construcción de Dominio Reducido: Un presupuesto dinámico $B$ controla el tamaño del dominio conjunto. El marco emplea un algoritmo de presupuestación que fusiona de manera codiciosa pares de variables (o hipernodos) con los productos de dominios marginales estimados más pequeños. Esta estrategia prioriza la fusión de las variables más restringidas primero para limitar el crecimiento de los dominios conjuntos intermedios. La consulta resultante se transforma en una consulta $EFO_1$ equivalente sobre un dominio reducido, la cual se resuelve luego utilizando búsqueda simbólica con segmentación de restricciones (actualizando vectores difusos mediante multiplicación elemento a elemento con máscaras) en lugar de la enumeración explícita.

Contribuciones Clave

• Marco NS3: El primer marco que infiere directamente clasificaciones conjuntas para consultas $EFO_k$ reduciendo progresivamente el espacio de candidatos conjunto mediante marginalización y fusión de hipernodos.
• Nuevo Punto de Referencia: Los autores lanzan un nuevo punto de referencia escalable de clasificación conjunta que extiende los conjuntos de datos existentes de $EFO_1$ a $k=3$. Este conjunto de datos incluye estructuras de consulta diversas (desconectadas, en cadena y cíclicas) para evaluar sistemáticamente las capacidades de razonamiento multivariable.
• Escalabilidad y Eficiencia: Al operar sobre un dominio reducido presupuestado en lugar del producto cartesiano completo, NS3 logra una complejidad temporal polinómica relativa a $k$ (bajo un presupuesto fijo), haciendo viable la inferencia conjunta para valores mayores de $k$.

Resultados Experimentales
El marco se evaluó en tres conjuntos de datos de KG estándar: FB15k, FB15k-237 y NELL.

• Rendimiento Marginal: En el punto de referencia existente de CQA-$EFO_k$ (centrado en clasificaciones marginales), NS3 (M) superó consistentemente a todos los puntos de referencia (incluyendo BetaE, LogicE, ConE, CQD, FIT y LMPNN) en las métricas Marginal, Multiplicada y Conjunta. Notablemente, mostró un rendimiento sólido en consultas cíclicas desafiantes.
• Rendimiento Conjunto: En el nuevo punto de referencia escalable (hasta $k=3$), NS3 (J), que realiza la clasificación conjunta directa, logró mejoras sustanciales sobre todos los puntos de referencia. En promedio, NS3 (J) rindió entre dos y tres veces mejor que el método anterior de última generación (FIT).
• Ablación y Sensibilidad: Los experimentos que variaron el presupuesto $B$ demostraron que las ganancias de rendimiento se saturan a medida que aumenta el presupuesto, con $B=4000$ (para FB15k-237) reteniendo más del 99% de las tuplas doradas mientras mantiene la eficiencia computacional. Se demostró que el algoritmo de presupuestación progresiva supera a las estrategias que fusionan todas las variables simultáneamente.
• Tiempo de Ejecución: NS3 es significativamente más rápido que FIT (el principal punto de referencia simbólico capaz de razonamiento conjunto), evitando errores de falta de memoria en grafos más grandes y reduciendo el tiempo de inferencia de horas a minutos.

Significado y Afirmaciones
El artículo afirma que NS3 cierra la brecha entre el objetivo teórico de la clasificación de tuplas conjunta y las limitaciones prácticas de los métodos existentes. Al transformar consultas complejas $EFO_k$ en consultas $EFO_1$ manejables sobre dominios reducidos, NS3 habilita un razonamiento interpretable y escalable para consultas lógicas multivariables. Los autores enfatizan que, aunque sus experimentos se centran en $k \le 3$ debido a la disponibilidad de puntos de referencia, el marco está diseñado para escalar polinómicamente con $k$ bajo un presupuesto fijo, ofreciendo un camino viable hacia el manejo de estructuras lógicas más complejas en grafos de conocimiento incompletos. El trabajo destaca la necesidad de ir más allá de las clasificaciones marginales para lograr una inferencia conjunta verdadera en la respuesta a consultas complejas.