Resumo Técnico: CHRONOS

1. Declaração do Problema

Mercados de dados de Grafos de Conhecimento Temporais (KG) enfrentam três falhas acopladas quando projetados com arquiteturas estáticas:

1. Indexação Obsoleta: Índices híbridos vetor-grafo (por exemplo, HNSW) dependem de arestas de atalho construídas no momento da criação. À medida que o KG subjacente evolui (adição/remoção de arestas), esses atalhos tornam-se obsoletos, degradando silenciosamente o recall. Sistemas dinâmicos existentes lidam com atualizações de vetores, mas falham em modelar a obsolescência estrutural do grafo ou fornecer limites de recall vinculados às taxas de evolução.
2. Valoração Estacionária: A atribuição justa de dados geralmente depende de valores de Shapley, que assumem uma função característica estacionária. Em mercados em evolução, mudanças distribucionais (por exemplo, surtos de doenças, alterações regulatórias) causam mudanças bruscas nos valores marginais dos conjuntos de dados. Valorações estáticas atribuem erroneamente o valor, distorcendo os incentivos do mercado.
3. Orçamento de Privacidade Descoordenado: Mercados de produção executam agentes concorrentes que compartilham um orçamento finito de privacidade diferencial (DP). Sem coordenação, demandas simultâneas por atualizações de índice, recálculo de valoração e processamento de consultas esgotam o orçamento prematuramente. Estruturas existentes carecem de acoplamento formal entre agendamento e consumo de DP.

Esses desafios são não decomponíveis porque atualizações de índice, recálculo de valoração e espera consomem todos do mesmo orçamento finito $(\epsilon, \delta)$.

2. Metodologia: A Arquitetura CHRONOS

O CHRONOS é uma arquitetura de três camadas com curador confiável que oferece um tratamento unificado desses desafios com separação explícita público/privado.

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

O T-LEGEND aplica decaimento temporal neural-ODE às arestas de atalho, permitindo que o índice degrade-se graciosamente em vez de falhar silenciosamente.

• Mecanismo: Um ODE neural modela o decaimento da utilidade da aresta ao longo do tempo ($\Delta t$). A função de decaimento é o primeiro componente da solução do ODE, treinada em snapshots históricos do KG usando perda temporal contrastiva.
• Separação Público/Privado: A estrutura do índice ($H_T$) e as listas de vizinhança são construídas deterministicamente a partir de dados públicos pré-mercado (embeddings congelados e partições de comunidade). Arestas contribuídas por vendedores não alteram a topologia do índice; elas influenciam apenas a matriz de afinidade privada no nível da época.
• Garantia Teórica: O sistema fornece um limite esperado de perda de recall por consulta de $O(P_q \lambda \Delta t)$. Um novo certificado de envelope monótono apertar esse limite, reduzindo a lacuna entre o limite teórico e a perda observada para 1,8–3,2$\times$. Limites formais também são estendidos para dinâmicas de Hawkes para lidar com mudanças de arestas correlacionadas.

Camada 2: MPV Condicionada a Eventos (EC-MPV)

Esta camada condiciona a valoração de Shapley a pontos de mudança distribucional detectados por BOCPD (Detecção Online Bayesiana de Pontos de Mudança).

• Mecanismo: Em vez de recálculo contínuo, as valorações são agrupadas e condicionadas a eventos detectados ($E$). A contribuição marginal de um vendedor é calculada como $\phi_i(D_{priv} \cup D_{pub} | E, t) - \phi(D_{pub} | E, t)$.
• Eficiência: Emprega Shapley de Dados com Redução de Variância (VRDS) com variáveis de controle para reduzir a variância de amostragem.
• Garantias: O sistema fornece garantias de erro de amostra finita sob amostragem de coalizão e ruído de DP, com uma identidade de eficiência temporal garantindo que a soma das valorações seja igual ao valor total da contribuição de dados privados.

Camada 3: Coordenador Temporal

Um meta-agente que agenda operações (Atualização de Índice, Reavaliação ou Nulo) para impor o orçamento de DP compartilhado.

• Algoritmo: Utiliza EXP3-IX (um algoritmo de banda multi-arma) sobre três ações de agendamento.
• Arrependimento: Alcança um arrependimento de $O(\sqrt{T \log T})$ enquanto impõe $(\epsilon_{total}, \delta_{total})$-DP via contagem de momentos.
• Gerenciamento de Orçamento: Equilibra demandas concorrentes, garantindo que a manutenção do índice e a valoração não se esgotem mutuamente. Sobrepõe ações que violariam o orçamento, convertendo-as em "Nulo" ou "Atualização de Índice" como sobrescritas de segurança.

Mecanismo de Privacidade: Pipeline de DP de Dimensão Fixa

O CHRONOS emprega uma estrita separação público/privado:

• Público: Embeddings, estrutura de índice e vetores de consulta incorrem em custo zero de DP.
• Privado: Arestas de vendedores, pontuações de valoração e estatísticas de obsolescência do índice são protegidas.
• Política de Liberação: O sistema libera uma matriz de afinidade privatizada de dimensão fixa ($\tilde{A}(t)$) uma vez por época ativa usando o mecanismo Gaussiano.
• Pós-processamento: Toda recuperação por consulta e classificação top-$k$ são realizadas como pós-processamento na matriz ruidosa. Consequentemente, elas incorrem em nenhum custo extra de privacidade.
• Contabilidade: O sistema usa composição aditiva padrão de zCDP sobre $\rho$, alcançando um $\epsilon$ total de 4,25 em $\delta = 10^{-6}$ através de múltiplos mecanismos (estatísticas de índice, valoração, afinidade).

Mecanismo de Liquidação

Para abordar a natureza dominada por ruído das liberações externas de valoração (onde o desvio padrão do ruído $\gg$ sinal), o CHRONOS introduz um mecanismo de liquidação no nível da coalizão de múltiplas épocas. Ao agregar valorações ao longo de $W$ épocas e agrupar vendedores em coalizões, a Razão Sinal-Ruído (SNR) melhora, permitindo atribuição no nível de tendência (por exemplo, distinguir contribuição acima/abaixo da mediana) em $W \ge 7$ épocas.

3. Resultados Chave

Experimentos foram conduzidos em quatro benchmarks: FB15K-237, WN18RR (sintético), MIMIC-IV e Yelp (mundo real).

• Desempenho: O CHRONOS alcança 0,937 de recall@10 no Yelp com 2,74 consultas/s e uma latência P50 de 161 ms.
• Estabilidade do Recall: No MIMIC-IV, o T-LEGEND degrada-se apenas em 0,0021 pontos de recall/dia, uma melhoria de 4,2$\times$ sobre o Plain-HNSW e 2,8$\times$ sobre o FreshDiskANN.
• Compromisso Privacidade-Utilidade: Em $\epsilon=4,25$ correspondente, o CHRONOS supera significativamente mecanismos de DP por consulta (por exemplo, Laplace OneShot, Exponencial Conjunta), que sofrem 6–10$\times$ menos QPS (0,28–0,43 vs. 2,74).
• Escalabilidade: O sistema escala para 500 vendedores. À medida que o número de vendedores ($n$) aumenta, a sensibilidade diminui ($\propto 1/\sqrt{n}$), fazendo com que o $\epsilon$ total cresça sublinearmente (de 4,25 em $n=10$ para 5,13 em $n=500$).
• Impacto da Coordenação: Remover o Coordenador Temporal (usando round-robin) degrada o recall em 3,3 pontos e aumenta o $\epsilon$ em 26,6%, confirmando a necessidade de design conjunto.
• Comparação com VSAG: Embora o VSAG (um HNSW de produção) ofereça QPS bruto mais alto, ele carece de pontuação de KG temporal. A integração do layout do VSAG com a construção consciente de decaimento do CHRONOS é projetada para gerar um aumento de velocidade de 1,5$\times$ sem sacrificar o recall.

4. Significado e Alegações

O artigo afirma que o CHRONOS representa o primeiro sistema a acoplar frescor do índice, correção de valoração e gerenciamento coordenado de orçamento de DP dentro de um framework multiagente para grafos de conhecimento temporais.

• Tratamento Unificado: Demonstra que esses três desafios não podem ser resolvidos isoladamente; um design conjunto é necessário para evitar o esgotamento do orçamento e a degradação de desempenho.
• Rigor Teórico: O trabalho fornece limites formais de recall (Teoremas 2–4) que incorporam estruturas Lipschitz de ODE e processos de Hawkes, indo além de suposições estáticas.
• Privacidade Prática: Estabelece um ponto operacional viável para recuperação de alta utilidade e baixa latência sob restrições estritas de DP, aproveitando estruturas de índice públicas e amortizando custos de DP ao longo de épocas em vez de por consulta.
• Liquidação Acionável: Oferece um mecanismo concreto para pagamentos a vendedores que reconcilia o alto ruído das liberações de DP com a necessidade de atribuição justa, usando agregação de coalizão para recuperar o sinal.

5. Limitações

Os autores reconhecem explicitamente várias limitações:

• Frouxidão do Limite: O limite de envelope monótono permanece 1,8–3,2$\times$ mais frouxo que a perda observada; fechar essa lacuna requer análise de correlação de caminho em nós hub.
• Sinais Dominados por Ruído: No nível de privacidade escolhido ($\epsilon=4,25$), as valorações e pontuações de afinidade liberadas externamente são dominadas por ruído. A utilidade do sistema deriva principalmente do roteamento de índice público e agendamento adaptativo impulsionado por estatísticas de DP de baixa sensibilidade, e não do sinal privado em si.
• Modelo de Confiança: O design atual depende de um curador confiável que detém todos os dados brutos dos vendedores. Embora extensões de dois servidores e DP Local sejam propostas como trabalho futuro, elas não estão totalmente implementadas ou validadas neste estudo.
• Privacidade de Consulta: Consultas de compradores são tratadas como públicas. Se as consultas forem sensíveis, mecanismos adicionais (por exemplo, sketches count-min) são necessários, os quais não fazem parte da avaliação central.