Riepilogo Tecnico: CHRONOS

1. Enunciato del Problema

I marketplace di dati per Grafi della Conoscenza Temporali (KG) affrontano tre fallimenti accoppiati quando progettati con architetture statiche:

1. Indicizzazione Obsoleta: Gli indici ibridi vettore-grafico (es. HNSW) si basano su archi scorciatoia costruiti al momento della creazione. Man mano che il KG sottostante evolve (aggiunta/rimozione di archi), queste scorciatoie diventano obsolete, degradando silenziosamente il richiamo (recall). I sistemi dinamici esistenti gestiscono gli aggiornamenti vettoriali ma non riescono a modellare l'obsolescenza strutturale del grafico o a fornire limiti di richiamo legati ai tassi di evoluzione.
2. Valutazione Stazionaria: L'attribuzione equa dei dati si basa tipicamente sui valori di Shapley, che assumono una funzione caratteristica stazionaria. Nei marketplace in evoluzione, gli spostamenti distribuzionali (es. focolai di malattie, cambiamenti normativi) causano variazioni brusche dei valori marginali dei dataset. Le valutazioni statiche attribuiscono erroneamente il valore, distorcendo gli incentivi del marketplace.
3. Budget di Privacy Non Coordinato: I marketplace di produzione eseguono agenti concorrenti che condividono un budget finito di privacy differenziale (DP). Senza coordinamento, le richieste simultanee di aggiornamenti dell'indice, ricalcolo delle valutazioni ed elaborazione delle query esauriscono il budget prematuramente. I framework esistenti mancano di un accoppiamento formale tra la pianificazione e il consumo DP.

Queste sfide sono non decomponibili perché gli aggiornamenti dell'indice, il ricalcolo delle valutazioni e l'attesa consumano tutti dalla stessa allocazione finita $(\epsilon, \delta)$.

2. Metodologia: L'Architettura CHRONOS

CHRONOS è un'architettura a tre livelli con curatore fidato che fornisce un trattamento unificato di queste sfide con una separazione esplicita pubblico/privato.

Livello 1: T-LEGEND (Indice Ibrido Temporale)

T-LEGEND applica un decadimento temporale basato su ODE neurali agli archi scorciatoia, consentendo all'indice di degradarsi elegantemente invece di fallire silenziosamente.

• Meccanismo: Un ODE neurale modella il decadimento dell'utilità dell'arco nel tempo ($\Delta t$). La funzione di decadimento è la prima componente della soluzione ODE, addestrata su snapshot storici del KG utilizzando una perdita temporale contrastiva.
• Separazione Pubblico/Privato: La struttura dell'indice ($H_T$) e le liste di vicinato sono costruite deterministicamente da dati pubblici pre-marketplace (embedding congelati e partizioni della comunità). Gli archi contribuiti dai venditori non alterano la topologia dell'indice; influenzano solo la matrice di affinità privata a livello di epoca.
• Garanzia Teorica: Il sistema fornisce un limite atteso di perdita di richiamo per query di $O(P_q \lambda \Delta t)$. Un nuovo certificato a involucro monotono stringe questo limite, riducendo il divario tra il limite teorico e la perdita osservata a 1,8–3,2$\times$. I limiti formali sono estesi anche alle dinamiche di Hawkes per gestire cambiamenti di archi correlati.

Livello 2: Valutazione MPV Condizionata agli Eventi (EC-MPV)

Questo livello condiziona la valutazione di Shapley sui punti di cambiamento distribuzionale rilevati da BOCPD (Rilevamento Online Bayesiano dei Punti di Cambiamento).

• Meccanismo: Invece di un ricalcolo continuo, le valutazioni sono raggruppate e condizionate sugli eventi rilevati ($E$). Il contributo marginale di un venditore è calcolato come $\phi_i(D_{priv} \cup D_{pub} | E, t) - \phi(D_{pub} | E, t)$.
• Efficienza: Impiega Data Shapley a Varianza Ridotta (VRDS) con variabili di controllo per ridurre la varianza di campionamento.
• Garanzie: Il sistema fornisce garanzie di errore su campioni finiti sotto campionamento di coalizioni e rumore DP, con un'identità di efficienza temporale che assicura che la somma delle valutazioni sia uguale al valore totale del contributo dei dati privati.

Livello 3: Coordinatore Temporale

Un meta-agente che pianifica le operazioni (Aggiornamento Indice, Rivalutazione o Null) per imporre il budget DP condiviso.

• Algoritmo: Utilizza EXP3-IX (un algoritmo a bandita multi-braccio) su tre azioni di pianificazione.
• Rimpianto: Raggiunge un rimpianto di $O(\sqrt{T \log T})$ imponendo la $(\epsilon_{total}, \delta_{total})$-DP tramite contabilità dei momenti.
• Gestione del Budget: Bilancia le richieste concorrenti, assicurando che la manutenzione dell'indice e la valutazione non si escludano a vicenda. Sovrascrive le azioni che violerebbero il budget, convertendole in "Null" o "Aggiornamento Indice" come sovrascritture di sicurezza.

Meccanismo di Privacy: Pipeline DP a Dimensione Fissa

CHRONOS impiega una rigorosa separazione pubblico/privato:

• Pubblico: Embedding, struttura dell'indice e vettori di query non comportano alcun costo DP.
• Privato: Gli archi dei venditori, i punteggi di valutazione e le statistiche di obsolescenza dell'indice sono protetti.
• Politica di Rilascio: Il sistema rilascia una matrice di affinità privatizzata a dimensione fissa ($\tilde{A}(t)$) una volta per epoca attiva utilizzando il meccanismo Gaussiano.
• Post-Processing: Tutto il recupero per query e il ranking top-$k$ sono eseguiti come post-processing sulla matrice rumorosa. Di conseguenza, non comportano alcun costo privacy aggiuntivo.
• Contabilità: Il sistema utilizza la composizione standard additiva zCDP su $\rho$, raggiungendo un $\epsilon$ totale di 4,25 a $\delta = 10^{-6}$ attraverso molteplici meccanismi (statistiche dell'indice, valutazione, affinità).

Meccanismo di Liquidazione

Per affrontare la natura dominata dal rumore dei rilasci di valutazione esterni (dove la deviazione standard del rumore $\gg$ segnale), CHRONOS introduce un meccanismo di liquidazione a livello di coalizione multi-epoca. Aggregando le valutazioni su $W$ epoche e raggruppando i venditori in coalizioni, il Rapporto Segnale-Rumore (SNR) migliora, consentendo l'attribuzione a livello di tendenza (es. distinguere contributi sopra/sotto la mediana) per $W \ge 7$ epoche.

3. Risultati Chiave

Gli esperimenti sono stati condotti su quattro benchmark: FB15K-237, WN18RR (sintetico), MIMIC-IV e Yelp (mondo reale).

• Prestazioni: CHRONOS ottiene un richiamo@10 di 0,937 su Yelp con 2,74 query/s e una latenza P50 di 161 ms.
• Stabilità del Richiamo: Su MIMIC-IV, T-LEGEND degrada di soli 0,0021 punti di richiamo/giorno, un miglioramento di 4,2$\times$ rispetto a Plain-HNSW e di 2,8$\times$ rispetto a FreshDiskANN.
• Trade-off Privacy-Utilità: A parità di $\epsilon=4,25$, CHRONOS supera significativamente i meccanismi DP per query (es. OneShot Laplace, Joint Exponential), che soffrono di un QPS inferiore di 6–10$\times$ (0,28–0,43 vs 2,74).
• Scalabilità: Il sistema scala fino a 500 venditori. All'aumentare del numero di venditori ($n$), la sensibilità diminuisce ($\propto 1/\sqrt{n}$), causando una crescita sublineare del totale $\epsilon$ (da 4,25 a $n=10$ a 5,13 a $n=500$).
• Impatto della Coordinazione: Rimuovere il Coordinatore Temporale (usando round-robin) degrada il richiamo di 3,3 punti e aumenta $\epsilon$ del 26,6%, confermando la necessità di un design congiunto.
• Confronto VSAG: Mentre VSAG (un HNSW di produzione) offre un QPS grezzo più elevato, manca di punteggio temporale per KG. Integrare il layout di VSAG con la costruzione consapevole del decadimento di CHRONOS dovrebbe produrre un aumento di velocità di 1,5$\times$ senza sacrificare il richiamo.

4. Significato e Affermazioni

Il documento afferma che CHRONOS rappresenta il primo sistema ad accoppiare freschezza dell'indice, correttezza della valutazione e gestione coordinata del budget DP all'interno di un framework multi-agente per grafi della conoscenza temporali.

• Trattamento Unificato: Dimostra che queste tre sfide non possono essere risolte in isolamento; è necessario un design congiunto per prevenire l'esaurimento del budget e il degrado delle prestazioni.
• Rigor Teorico: Il lavoro fornisce limiti formali di richiamo (Teoremi 2–4) che incorporano strutture Lipschitz ODE e processi di Hawkes, andando oltre le assunzioni statiche.
• Privacy Pratica: Stabilisce un punto operativo vitale per il recupero ad alta utilità e bassa latenza sotto vincoli DP rigorosi, sfruttando strutture di indice pubbliche e ammortizzando i costi DP su epoche anziché per query.
• Liquidazione Azionabile: Offre un meccanismo concreto per i pagamenti ai venditori che concilia l'alto rumore dei rilasci DP con la necessità di un'attribuzione equa, utilizzando l'aggregazione di coalizioni per recuperare il segnale.

5. Limitazioni

Gli autori riconoscono esplicitamente diverse limitazioni:

• Rilassamento dei Limiti: Il limite a involucro monotono rimane 1,8–3,2$\times$ più lasco rispetto alla perdita osservata; colmare questo divario richiede un'analisi di correlazione dei percorsi sui nodi hub.
• Segnali Dominati dal Rumore: Al livello di privacy scelto ($\epsilon=4,25$), le valutazioni e i punteggi di affinità rilasciati esternamente sono dominati dal rumore. L'utilità del sistema deriva principalmente dall'instradamento dell'indice pubblico e dalla pianificazione adattiva guidata da statistiche DP a bassa sensibilità, non dal segnale privato in sé.
• Modello di Fiducia: Il design attuale si basa su un curatore fidato che detiene tutti i dati grezzi dei venditori. Sebbene siano proposti come lavoro futuro estensioni a due server e DP locale, non sono pienamente implementati o validati in questo studio.
• Privacy delle Query: Le query degli acquirenti sono trattate come pubbliche. Se le query sono sensibili, sono necessari meccanismi aggiuntivi (es. schizzi count-min), che non fanno parte della valutazione principale.