Resumen Técnico: CQD-SHAP

Planteamiento del Problema

La Respuesta a Consultas Complejas (CQA, por sus siglas en inglés) en Grafos de Conocimiento (KG) va más allá de la simple predicción de enlaces para manejar consultas que requieren razonamiento de múltiples saltos y operadores lógicos (conjunción, disyunción). Aunque han surgido enfoques neurosimbólicos como CQD (Descomposición de Consultas Complejas) para abordar la incompletitud de los KG del mundo real mediante la inferencia de enlaces faltantes, estos funcionan principalmente como modelos de caja negra. Los métodos de explicabilidad existentes para la predicción de enlaces se centran en identificar triples o rutas importantes para predicciones de un solo salto y no se aplican directamente a consultas complejas. Además, los métodos actuales de CQA neurosimbólica carecen de transparencia respecto a la contribución específica de los diferentes componentes de la consulta (átomos) al ranking de un answer final. Esta opacidad dificulta la confianza del usuario, la depuración y la capacidad de los expertos en el dominio para identificar brechas en el KG o refinar las consultas.

Metodología: CQD-SHAP

El artículo propone CQD-SHAP, un marco para explicar los resultados de los modelos de CQA neurosimbólicos (específicamente CQD) cuantificando la contribución de cada átomo de la consulta al ranking de una entidad respuesta específica utilizando los valores de Shapley de la teoría de juegos cooperativos.

Definiciones Centrales

1. Jugadores: Los átomos (partes constituyentes) de una consulta compleja $Q$ son tratados como jugadores en un juego cooperativo.
2. Coaliciones: Un subconjunto de átomos $S$ se ejecuta utilizando el enfoque neural (infiriendo enlaces faltantes mediante un predictor de enlaces), mientras que los átomos restantes se ejecutan utilizando un enfoque simbólico (dependiendo estrictamente de los hechos observados en el KG).
3. Función de Valor: El valor de una coalición $S$ para una entidad objetivo $e_i$ se define mediante la Cantidad de Interés (QoI) de $\Delta$Rank. Esto mide la mejora en la posición de ranking de $e_i$ cuando los átomos en $S$ se ejecutan de forma neural en comparación con una ejecución puramente simbólica de toda la consulta.
   • Formalmente: $val_{e_i}(Q_S) = r_i(Q_{\emptyset}) - r_i(Q_S)$, donde $r_i$ es el rango de la entidad $e_i$ en un entorno filtrado.
4. Cálculo del Valor de Shapley: La contribución de un átomo específico $a$ se calcula como la contribución marginal promedio de ese átomo a través de todas las coaliciones posibles de otros átomos. Esto satisface los axiomas fundamentales de Shapley, incluyendo la eficiencia (la suma de las contribuciones de todos los átomos es igual a la mejora total del ranking obtenida mediante la ejecución neural completa).

Detalles de Ejecución

• Ejecución Neural: Utiliza un predictor de enlaces (por ejemplo, de CQD) para asignar puntuaciones a las entidades, permitiendo la inferencia sobre grafos incompletos.
• Ejecución Simbólica: Realiza el recorrido del grafo en el KG observado (incompleto), asignando puntuaciones constantes a los hechos existentes y puntuaciones bajas a los no existentes.
• Computación Exacta: Debido al pequeño número de átomos en las consultas complejas (típicamente $\le 4$), el artículo calcula los valores de Shapley exactos sin aproximaciones.

Contribuciones Clave

1. Primera Explicación basada en Shapley para CQA: Según el conocimiento de los autores, esta es la primera aproximación para explicar modelos de respuesta a consultas complejas neurales utilizando valores de Shapley.
2. Definición Formal de Explicaciones a Nivel de Átomo: El artículo define un marco de explicación formal al nivel de los átomos de la consulta, distinguiéndolo de las explicaciones a nivel de triple o de ruta utilizadas en la predicción de enlaces.
3. Métrica Novedosa (CQD-SHAP): Introduce un método para cuantificar cuánto contribuye la ejecución neural de un átomo específico al ranking de una respuesta objetivo en comparación con la ejecución simbólica.
4. Redefinición de los Criterios de Evaluación: Extiende los conceptos de explicaciones Necesarias y Suficientes de la predicción de enlaces al dominio de CQA:
   • Necesaria: Reemplazar el átomo más importante con la ejecución simbólica causa una caída significativa en el ranking de la respuesta (medida por $\Delta$MRR).
   • Suficiente: Ejecutar solo el átomo más importante de forma neural (mientras los otros son simbólicos) mejora significamente el ranking en comparación con un baseline puramente simbólico.

Resultados Experimentales

Los autores evaluaron CQD-SHAP en FB15k-237, NELL995 y sus variantes más difíciles (+H) a través de varios tipos de consulta (proyecciones, intersecciones, uniones).

• Desempeño: CQD-SHAP superó consistentemente a todos los baselines (First, Last, Random y selección basada en Score) tanto en los escenarios de evaluación necesaria como suficiente.
  • En el escenario Necesario, CQD-SHAP redujo el Mean Reciprocal Rank (MRR) hasta en un 45.70% (para consultas 2u en NELL995), significativamente más que el mejor baseline.
  • En el escenario Suficiente, aumentó el MRR hasta en un 58.90% (para consultas 2u en NELL995+H).
• Sensibilidad a la Estructura de la Consulta: El método demostró una mayor efectividad para las consultas de intersección (ej. 3i, 4i) en comparación con las consultas de proyección. Los autores atribuyen esto a la naturaleza estructural de las intersecciones (usando t-normas), donde una única rama crítica actúa como un filtro fuerte, mientras que las consultas de proyección suelen tener caminos alternativos.
• Eficiencia: A pesar de la naturaleza NP-hard de los valores de Shapley, el pequeño número de átomos permitió la computación exacta con baja latencia (promedio de ~30–140 ms por par consulta-respuesta dependiendo del dataset).
• Perspectiva (Insight): El análisis reveló que el átomo más importante no siempre es un "enlace faltante". En algunos casos, un átomo correspondiente a un hecho existente en el KG puede ser el principal motor del ranking debido a la proximidad de los embeddings o al ruido introducido por la ejecución neural de otras partes.

Significancia y Reivindicaciones

El artículo afirma que CQD-SHAP proporciona una forma matemáticamente rigurosa y efectiva de interpretar la respuesta a consultas neurosimbólicas. Al satisfacer los axiomas de Shapley, asegura una atribución justa del crédito a los componentes de la consulta. Los autores sostienen que este enfoque:

• Ayuda a los expertos en el dominio a identificar brechas en los KG al revelar qué partes de la consulta dependen fuertemente del conocimiento inferido.
• Asiste en la depuración de consultas al mostrar qué átomos influyen más en el ranking final.
• Proporciona una visión transparente de cómo los predictores neurales aprovechan los datos incompletos en comparación con la recuperación simbólica.

Los autores declaran explícitamente que este es el primer trabajo en aplicar valores de Shapley para explicar los resultados de la respuesta a consultas complejas, yendo más allá de las limitaciones de los métodos de explicación de predicción de enlaces existentes. Señalan que, si bien el trabajo actual se centra en explicaciones locales (respuesta única), las direcciones futuras incluyen explicaciones globales y generación de lenguaje natural para hacer que estos valores sean legibles para los humanos.