Resumen Técnico: CHRONOS

1. Declaración del Problema

Los mercados de datos de Grafos de Conocimiento (KG) temporales enfrentan tres fallos acoplados cuando se diseñan con arquitecturas estáticas:

1. Indexación Obsoleta: Los índices híbridos vector-grafo (por ejemplo, HNSW) dependen de aristas de atajo construidas durante la creación. A medida que el KG subyacente evoluciona (se añaden o eliminan aristas), estos atajos se vuelven obsoletos, degradando silenciosamente la recuperación. Los sistemas dinámicos existentes manejan actualizaciones vectoriales, pero fallan al modelar la obsolescencia estructural del grafo o proporcionar límites de recuperación vinculados a las tasas de evolución.
2. Valoración Estacionaria: La atribución justa de datos suele basarse en valores de Shapley, que asumen una función característica estacionaria. En mercados en evolución, los cambios distribucionales (por ejemplo, brotes de enfermedades, cambios regulatorios) provocan que los valores marginales de los conjuntos de datos cambien bruscamente. Las valoraciones estáticas atribuyen incorrectamente el valor, distorsionando los incentivos del mercado.
3. Presupuesto de Privacidad No Coordinado: Los mercados de producción ejecutan agentes concurrentes que comparten un presupuesto finito de privacidad diferencial (DP). Sin coordinación, las demandas simultáneas de actualizaciones de índices, recálculo de valoraciones y procesamiento de consultas agotan el presupuesto prematuramente. Los marcos existentes carecen de un acoplamiento formal entre la programación y el consumo de DP.

Estos desafíos son no descomponibles porque las actualizaciones de índices, el recálculo de valoraciones y la espera consumen todos del mismo presupuesto finito $(\epsilon, \delta)$.

2. Metodología: La Arquitectura CHRONOS

CHRONOS es una arquitectura de tres capas con curador de confianza que ofrece un tratamiento unificado de estos desafíos con una separación explícita pública/privada.

Capa 1: T-LEGEND (Índice Híbrido Temporal)

T-LEGEND aplica decaimiento temporal de ODE neuronal a las aristas de atajo, permitiendo que el índice se degrade con elegancia en lugar de fallar silenciosamente.

• Mecanismo: Una ODE neuronal modela el decaimiento de la utilidad de la arista a lo largo del tiempo ($\Delta t$). La función de decaimiento es el primer componente de la solución de la ODE, entrenada sobre instantáneas históricas del KG utilizando una pérdida temporal contrastiva.
• Separación Pública/Privada: La estructura del índice ($H_T$) y las listas de vecindad se construyen de manera determinista a partir de datos públicos pre-mercado (incrustaciones congeladas y particiones de comunidad). Las aristas contribuidas por los vendedores no alteran la topología del índice; solo influyen en la matriz de afinidad privada a nivel de época.
• Garantía Teórica: El sistema proporciona un límite esperado de pérdida de recuperación por consulta de $O(P_q \lambda \Delta t)$. Un nuevo certificado de envolvente monótona estrecha este límite, reduciendo la brecha entre el límite teórico y la pérdida observada a 1.8–3.2$\times$. Los límites formales también se extienden a dinámicas de Hawkes para manejar cambios de aristas correlacionados.

Capa 2: Valoración MPV Condicionada a Eventos (EC-MPV)

Esta capa condiciona la valoración de Shapley a puntos de cambio distribucionales detectados por BOCPD (Detección de Cambios en Línea Bayesiana).

• Mecanismo: En lugar de un recálculo continuo, las valoraciones se agrupan en lotes y se condicionan a eventos detectados ($E$). La contribución marginal de un vendedor se calcula como $\phi_i(D_{priv} \cup D_{pub} | E, t) - \phi(D_{pub} | E, t)$.
• Eficiencia: Emplea Shapley de Datos con Reducción de Varianza (VRDS) con variables de control para disminuir la varianza de muestreo.
• Garantías: El sistema proporciona garantías de error en muestras finitas bajo muestreo de coaliciones y ruido DP, con una identidad de eficiencia temporal que asegura que la suma de las valoraciones sea igual al valor total de la contribución de datos privados.

Capa 3: Coordinador Temporal

Un meta-agente que programa operaciones (Actualización de Índice, Revaloración o Nulo) para hacer cumplir el presupuesto DP compartido.

• Algoritmo: Utiliza EXP3-IX (un algoritmo de banda multi-brazo) sobre tres acciones de programación.
• Arrepentimiento: Logra un arrepentimiento de $O(\sqrt{T \log T})$ mientras hace cumplir la DP $(\epsilon_{total}, \delta_{total})$ mediante contabilidad de momentos.
• Gestión del Presupuesto: Equilibra demandas competitivas, asegurando que el mantenimiento del índice y la valoración no se agoten mutuamente. Anula acciones que violarían el presupuesto, convirtiéndolas en "Nulo" o "Actualización de Índice" como sobrescrituras de seguridad.

Mecanismo de Privacidad: Pipeline DP de Dimensión Fija

CHRONOS emplea una estricta separación pública/privada:

• Público: Las incrustaciones, la estructura del índice y los vectores de consulta incurren en cero costo DP.
• Privado: Las aristas de los vendedores, las puntuaciones de valoración y las estadísticas de obsolescencia del índice están protegidas.
• Política de Liberación: El sistema libera una matriz de afinidad privatizada de dimensión fija ($\tilde{A}(t)$) una vez por época activa utilizando el mecanismo gaussiano.
• Post-procesamiento: Toda la recuperación por consulta y la clasificación top-$k$ se realizan como post-procesamiento sobre la matriz ruidosa. En consecuencia, no incurren en ningún costo de privacidad adicional.
• Contabilidad: El sistema utiliza la composición aditiva estándar de zCDP sobre $\rho$, logrando un $\epsilon$ total de 4.25 en $\delta = 10^{-6}$ a través de múltiples mecanismos (estadísticas de índice, valoración, afinidad).

Mecanismo de Liquidación

Para abordar la naturaleza dominada por el ruido de las liberaciones de valoración externas (donde la desviación estándar del ruido $\gg$ la señal), CHRONOS introduce un mecanismo de liquidación a nivel de coalición de múltiples épocas. Al agregar valoraciones sobre $W$ épocas y agrupar a los vendedores en coaliciones, la Relación Señal-Ruido (SNR) mejora, permitiendo la atribución a nivel de tendencia (por ejemplo, distinguir contribuciones por encima/por debajo de la mediana) en $W \ge 7$ épocas.

3. Resultados Clave

Los experimentos se realizaron en cuatro puntos de referencia: FB15K-237, WN18RR (sintético), MIMIC-IV y Yelp (mundo real).

• Rendimiento: CHRONOS logra una recuperación@10 de 0.937 en Yelp con 2.74 consultas/s y una latencia P50 de 161 ms.
• Estabilidad de Recuperación: En MIMIC-IV, T-LEGEND se degrada solo en 0.0021 puntos de recuperación/día, una mejora de 4.2$\times$ sobre Plain-HNSW y de 2.8$\times$ sobre FreshDiskANN.
• Compensación Privacidad-Utilidad: Con $\epsilon=4.25$ igualado, CHRONOS supera significativamente a los mecanismos DP por consulta (por ejemplo, Laplace OneShot, Exponencial Conjunta), que sufren un 6–10$\times$ menos de QPS (0.28–0.43 vs. 2.74).
• Escalabilidad: El sistema escala a 500 vendedores. A medida que aumenta el número de vendedores ($n$), la sensibilidad disminuye ($\propto 1/\sqrt{n}$), haciendo que el $\epsilon$ total crezca de forma sublineal (de 4.25 en $n=10$ a 5.13 en $n=500$).
• Impacto de la Coordinación: Eliminar el Coordinador Temporal (usando round-robin) degrada la recuperación en 3.3 puntos y aumenta $\epsilon$ en un 26.6%, confirmando la necesidad de un diseño conjunto.
• Comparación con VSAG: Aunque VSAG (un HNSW de producción) ofrece un QPS en bruto más alto, carece de puntuación de KG temporal. Integrar la disposición de VSAG con la construcción consciente del decaimiento de CHRONOS se proyecta que produzca una aceleración de 1.5$\times$ sin sacrificar la recuperación.

4. Significado y Afirmaciones

El artículo afirma que CHRONOS representa el primer sistema que acopla frescura del índice, corrección de valoración y gestión coordinada del presupuesto DP dentro de un marco de múltiples agentes para grafos de conocimiento temporales.

• Tratamiento Unificado: Demuestra que estos tres desafíos no pueden resolverse de forma aislada; se requiere un diseño conjunto para evitar el agotamiento del presupuesto y la degradación del rendimiento.
• Rigor Teórico: El trabajo proporciona límites formales de recuperación (Teoremas 2–4) que incorporan estructuras Lipschitz de ODE y procesos de Hawkes, superando las asunciones estáticas.
• Privacidad Práctica: Establece un punto operativo viable para la recuperación de alta utilidad y baja latencia bajo estrictas restricciones de DP, aprovechando estructuras de índices públicos y amortizando los costos DP a lo largo de épocas en lugar de por consulta.
• Liquidación Accionable: Ofrece un mecanismo concreto para los pagos a vendedores que reconcilia el alto ruido de las liberaciones DP con la necesidad de una atribución justa, utilizando la agregación de coaliciones para recuperar la señal.

5. Limitaciones

Los autores reconocen explícitamente varias limitaciones:

• Holgura de los Límites: El límite de la envolvente monótona sigue siendo 1.8–3.2$\times$ más holgado que la pérdida observada; cerrar esta brecha requiere un análisis de correlación de trayectorias en los nodos hub.
• Señales Dominadas por Ruido: En el nivel de privacidad elegido ($\epsilon=4.25$), las valoraciones y puntuaciones de afinidad liberadas externamente están dominadas por el ruido. La utilidad del sistema deriva principalmente del enrutamiento de índices públicos y la programación adaptativa impulsada por estadísticas DP de baja sensibilidad, no de la señal privada en sí misma.
• Modelo de Confianza: El diseño actual depende de un curador de confianza que posee todos los datos crudos de los vendedores. Aunque se proponen extensiones de dos servidores y DP Local como trabajo futuro, no están completamente implementadas ni validadas en este estudio.
• Privacidad de Consultas: Las consultas de los compradores se tratan como públicas. Si las consultas son sensibles, se requieren mecanismos adicionales (por ejemplo, sketches de conteo mínimo), que no forman parte de la evaluación central.