기술 요약: CHRONOS

1. 문제 정의

정적 아키텍처로 설계된 시계열 지식 그래프 (KG) 데이터 마켓플레이스는 세 가지 결합된 실패에 직면합니다:

1. 구식 인덱싱 (Stale Indexing): 하이브리드 벡터 - 그래프 인덱스 (예: HNSW) 는 구축 시 생성된 단축 경로 (shortcut) 에지 (edges) 에 의존합니다. 하부 KG 가 진화 (에지 추가/삭제) 함에 따라 이러한 단축 경로는 구식화되어 정밀도 (recall) 를 침묵 속에서 저하시킵니다. 기존 동적 시스템은 벡터 업데이트를 처리하지만, 그래프 구조적 구식화를 모델링하거나 진화율과 연계된 정밀도 하한을 제공하지는 못합니다.
2. 정적 가치 평가 (Stationary Valuation): 공정한 데이터 귀속은 일반적으로 정적 특성 함수를 가정하는 샤플리 (Shapley) 값에 의존합니다. 진화하는 마켓플레이스에서는 분포 변화 (예: 질병 발생, 규제 변경) 로 인해 한계 데이터셋 가치가 급격히 변동합니다. 정적 가치 평가는 가치를 잘못 귀속시켜 마켓플레이스 인센티브를 왜곡합니다.
3. 조정되지 않은 프라이버시 예산: 생산 마켓플레이스는 유한한 차분 프라이버시 (DP) 예산을 공유하는 동시 에이전트들을 운영합니다. 조정 없이는 인덱스 업데이트, 가치 평가 재계산, 쿼리 처리에 대한 동시 요구가 예산을 조기에 고갈시킵니다. 기존 프레임워크는 스케줄링과 DP 소비 간의 공식적 결합이 부족합니다.

이러한 도전 과제는 인덱스 업데이트, 가치 평가 재계산, 대기 시간이 모두 동일한 유한한 $(\epsilon, \delta)$ 할당량에서 소모되므로 분해 불가능합니다.

2. 방법론: CHRONOS 아키텍처

CHRONOS 는 명시적인 공개/비공개 분리를 통해 이러한 도전 과제를 통합적으로 처리하는 신뢰할 수 있는 큐레이터 기반 3 계층 아키텍처입니다.

계층 1: T-LEGEND (시계열 하이브리드 인덱스)

T-LEGEND 는 단축 경로 에지에 신경 ODE 시계열 감쇠를 적용하여 인덱스가 실패하는 대신 정중하게 저하되도록 합니다.

• 메커니즘: 신경 ODE 는 시간 ($\Delta t$) 에 따른 에지 유틸리티의 감쇠를 모델링합니다. 감쇠 함수는 ODE 해의 첫 번째 구성 요소로, 대비적 시계열 손실을 사용하여 과거 KG 스냅샷으로 학습됩니다.
• 공개/비공개 분리: 인덱스 구조 ($H_T$) 와 이웃 목록은 공개된 마켓플레이스 전 데이터 (고정된 임베딩 및 커뮤니티 파티션) 에서 결정론적으로 구축됩니다. 판매자가 기여한 에지는 인덱스 위상을 변경하지 않으며, 에포크 수준의 비공개 친밀도 행렬에만 영향을 미칩니다.
• 이론적 보장: 시스템은 쿼리당 기대 정밀도 손실 상한 $O(P_q \lambda \Delta t)$를 제공합니다. 새로운 **단조 포장 증명 (monotone-envelope certificate)**은 이 상한을 강화하여 이론적 상한과 관측된 손실 간의 격차를 1.8~3.2 배로 줄입니다. 공식적 상한은 상관된 에지 변화를 처리하기 위해 Hawkes 역학으로 확장됩니다.

계층 2: 이벤트 조건부 MPV (EC-MPV)

이 계층은 BOCPD(베이지안 온라인 변화점 감지) 로 감지된 분포 변화점에 샤플리 가치 평가를 조건부로 적용합니다.

• 메커니즘: 지속적인 재계산 대신, 가치 평가는 감지된 이벤트 ($E$) 에 조건부로 배치됩니다. 판매자의 한계 기여도는 $\phi_i(D_{priv} \cup D_{pub} | E, t) - \phi(D_{pub} | E, t)$로 계산됩니다.
• 효율성: 제어 변수를 사용하는 분산 감소 데이터 샤플리 (VRDS) 를 사용하여 샘플링 분산을 낮춥니다.
• 보장: 시스템은 연합 샘플링 및 DP 노이즈 하에서 유한 표본 오류 보장을 제공하며, 가치 평가의 합이 비공개 데이터 기여의 총 가치와 같음을 보장하는 시계열 효율성 항등식을 제공합니다.

계층 3: 시계열 조정자

공유 DP 예산을 강제하기 위해 작업 (인덱스 업데이트, 재평가, 또는 Null) 을 스케줄링하는 메타 에이전트입니다.

• 알고리즘: 세 가지 스케줄링 작업에 대해 EXP3-IX(다중 암 밴딧 알고리즘) 를 사용합니다.
• 후회 (Regret): 모멘트 계정을 통해 $(\epsilon_{total}, \delta_{total})$-DP 를 강제하면서 $O(\sqrt{T \log T})$ 후회를 달성합니다.
• 예산 관리: 경쟁하는 요구 사항을 균형 있게 조정하여 인덱스 유지 관리와 가치 평가가 서로를 고갈시키지 않도록 합니다. 예산을 위반할 수 있는 작업은 "Null"또는 "인덱스 업데이트"로 변환하는 안전 재정의 (safety overrides) 를 통해 재정의됩니다.

프라이버시 메커니즘: 고정 차원 DP 파이프라인

CHRONOS 는 엄격한 공개/비공개 분리를 사용합니다:

• 공개: 임베딩, 인덱스 구조, 쿼리 벡터는 DP 비용을 전혀 발생시키지 않습니다.
• 비공개: 판매자 에지, 가치 평가 점수, 인덱스 구식화 통계는 보호됩니다.
• 배포 정책: 시스템은 가우시안 메커니즘을 사용하여 활성 에포크당 한 번 고정 차원 비공개 친밀도 행렬($\tilde{A}(t)$) 을 배포합니다.
• 후처리: 모든 쿼리당 검색 및 상위 $k$개 순위 매기기는 노이즈가 있는 행렬에 대한 후처리로서 수행됩니다. 결과적으로 추가 프라이버시 비용이 발생하지 않습니다.
• 계정: 시스템은 $\rho$에 대한 표준 가산 zCDP 조합을 사용하여 여러 메커니즘 (인덱스 통계, 가치 평가, 친밀도) 을 통해 $\delta = 10^{-6}$에서 총 $\epsilon = 4.25$를 달성합니다.

정산 메커니즘

외부 가치 평가 배포의 노이즈 우세 특성 (노이즈 표준편차 $\gg$ 신호) 을 해결하기 위해 CHRONOS 는 다중 에포크 연합 수준 정산 메커니즘을 도입합니다. $W$개의 에포크에 걸쳐 가치 평가를 집계하고 판매자를 연합으로 그룹화함으로써 신호 대 잡음비 (SNR) 가 향상되어 $W \ge 7$개 에포크에서 추세 수준 귀속 (예: 중앙값 이상/이하 기여도 구분) 이 가능해집니다.

3. 주요 결과

실험은 FB15K-237, WN18RR(합성), MIMIC-IV, Yelp(실제) 의 네 가지 벤치마크에서 수행되었습니다.

• 성능: CHRONOS 는 Yelp 에서 2.74 쿼리/초와 161ms의 P50 지연 시간을 가지며 0.937 의 recall@10을 달성합니다.
• 정밀도 안정성: MIMIC-IV 에서 T-LEGEND 는 하루당 0.0021 개의 정밀도 포인트만 저하되어 Plain-HNSW 대비 4.2 배, FreshDiskANN 대비 2.8 배의 개선을 보입니다.
• 프라이버시 - 유틸리티 트레이드오프: 일치된 $\epsilon=4.25$에서 CHRONOS 는 QPS 가 610 배 낮은 (0.280.43 대 2.74) 쿼리당 DP 메커니즘 (예: OneShot Laplace, Joint Exponential) 보다 훨씬 뛰어납니다.
• 확장성: 시스템은 500 명의 판매자까지 확장됩니다. 판매자 수 ($n$) 가 증가함에 따라 민감도는 감소 ($\propto 1/\sqrt{n}$) 하여 총 $\epsilon$은 $n=10$에서 4.25 에서 $n=500$에서 5.13 으로 아선형적으로 증가합니다.
• 조정 영향: 시계열 조정자를 제거하고 (라운드 로빈 사용) 정밀도가 3.3 포인트 저하되고 $\epsilon$이 26.6% 증가하여 공동 설계의 필요성이 확인되었습니다.
• VSAG 비교: 생산용 HNSW 인 VSAG 는 더 높은 원시 QPS 를 제공하지만 시계열 KG 점수 매기기가 부족합니다. VSAG 의 레이아웃을 CHRONOS 의 감쇠 인식 구축과 통합하면 정밀도를 희생하지 않고 1.5 배의 속도 향상을 얻을 것으로 예상됩니다.

4. 중요성 및 주장

이 논문은 CHRONOS 가 시계열 지식 그래프를 위한 다중 에이전트 프레임워크 내에서 인덱스 신선도, 가치 평가 정확성, 조정된 DP 예산 관리를 결합한 최초의 시스템이라고 주장합니다.

• 통합 처리: 이 세 가지 도전 과제는 고립적으로 해결될 수 없음을 보여줍니다. 예산 고갈과 성능 저하를 방지하기 위해 공동 설계가 필요합니다.
• 이론적 엄밀성: 이 작업은 정적 가정을 넘어 ODE Lipschitz 구조와 Hawkes 과정을 통합한 공식적 정밀도 상한 (정리 2~4) 을 제공합니다.
• 실용적 프라이버시: 공개 인덱스 구조를 활용하고 쿼리당 대신 에포크에 걸쳐 DP 비용을 분산시킴으로써 엄격한 DP 제약 하에서 고유틸리티, 저지연 검색을 위한 실행 가능한 운영 지점을 확립합니다.
• 실행 가능한 정산: 연합 집계를 통해 신호를 복원하여 DP 배포의 높은 노이즈와 공정한 귀속 필요성 사이의 모순을 해결하는 판매자 지급을 위한 구체적인 메커니즘을 제공합니다.

5. 한계

저자들은 명시적으로 몇 가지 한계를 인정합니다:

• 상한의 느슨함: 단조 포장 상한은 관측된 손실보다 1.8~3.2 배 느슨합니다. 이 격차를 좁히기 위해서는 허브 노드에서의 경로 상관관계 분석이 필요합니다.
• 노이즈 우세 신호: 선택된 프라이버시 수준 ($\epsilon=4.25$) 에서 외부 배포된 가치 평가 및 친밀도 점수는 노이즈에 의해 지배됩니다. 시스템의 유틸리티는 주로 공개 인덱스 라우팅과 낮은 민감도 DP 통계에 기반한 적응형 스케줄링에서 비롯되며, 비공개 신호 자체에서 비롯된 것은 아닙니다.
• 신뢰 모델: 현재 설계는 모든 원시 판매자 데이터를 보유하는 신뢰할 수 있는 큐레이터에 의존합니다. 두 서버 및 로컬 DP 확장은 향후 작업으로 제안되었으나, 본 연구에서는 완전히 구현되거나 검증되지 않았습니다.
• 쿼리 프라이버시: 구매자 쿼리는 공개로 간주됩니다. 쿼리가 민감한 경우, 핵심 평가의 일부가 아닌 카운트 - 최소 스케치 (count-min sketches) 와 같은 추가 메커니즘이 필요합니다.