Missing Mass for Differentially Private Domain Discovery

이 논문은 차분 프라이버시 (Differential Privacy, DP) 하에서 알려지지 않은 도메인 (Unknown Domain) 을 가진 데이터에 대한 도메인 발견 (Domain Discovery) 문제를 다룹니다. 각 사용자가 공유되지만 미지의 도메인에서 항목의 부분 집합을 보유하고 있을 때, 유용한 항목의 부분 집합을 출력하는 것을 목표로 합니다.

논문은 가중치 가우시안 메커니즘 (Weighted Gaussian Mechanism, WGM) 을 기반으로 한 새로운 접근법을 제시하며, 이를 통해 기존 알고리즘들의 이론적 한계를 극복하고 실용적인 성능을 입증했습니다.

주요 내용은 다음과 같습니다.

1. 문제 정의 및 배경

• 배경: 현대 데이터 분석 (쿼리, 리뷰, 구매 내역 등) 은 사전에 알려지지 않았거나 방대한 도메인 (예: 고정된 길이의 모든 문자열 집합) 에서 이루어집니다. 이러한 데이터에 대한 효율적인 하위 응용을 위해서는 도메인 발견이 필수적입니다.
• 문제: 차분 프라이버시를 유지하면서 데이터의 '도메인' (전체 고유 항목 집합) 을 파악하는 것은 어렵습니다. 기존 연구들은 대부분 경험적 성능에 의존하거나, 특정 제한된 설정 (예: 사용자가 단일 항목만 기여) 에서만 최적성을 증명했습니다.
• 목표:
  1. Set Union (집합 합집합): 입력된 모든 항목 중 가능한 한 많은 항목을 복원하는 것.
  2. Private Top-k: 알려진 도메인이 주어지지 않은 상태에서 빈도수가 높은 상위 $k$개 항목을 찾는 것.
  3. Private k-Hitting Set: $k$개의 항목을 선택하여 가능한 많은 사용자의 데이터와 교차 (hit) 하도록 하는 것.

2. 핵심 방법론: 가중치 가우시안 메커니즘 (WGM) 활용

저자들은 기존에 실용적으로 사용되던 WGM (Weighted Gaussian Mechanism) 을 재해석하고 이를 도메인 발견의 핵심 도구로 활용합니다.

• WGM 작동 원리:
  1. 샘플링: 각 사용자의 항목 집합에서 무작위로 $\Delta_0$개 이하의 항목을 추출하여 데이터 크기를 제한합니다.
  2. 가중치 히스토그램: 추출된 항목에 대해 가중치를 부여한 히스토그램을 생성합니다 (기여도가 큰 사용자의 항목은 더 큰 가중치를 가짐).
  3. 노이즈 추가 및 임계값: 가우시안 노이즈를 추가한 후, 임계값 $T$ 이상의 항목만 선택합니다.
• 성공적인 전략 (Meta-Algorithm):
  • WGM 을 도메인 발견의 전처리 (Precursor) 단계로 사용합니다.
  • 전체 프라이버시 예산의 절반을 WGM 을 실행하여 잠재 도메인 (Candidate Domain) 을 추출하는 데 사용합니다.
  • 나머지 절반의 예산을 사용하여, 추출된 도메인 내에서 기존에 알려진 알려진 도메인 알고리즘 (Known-domain algorithms) 을 실행합니다.
  • 이를 통해 복잡한 "알려지지 않은 도메인" 문제를 "알려진 도메인" 문제로 변환하여 해결합니다.

3. 주요 기여 (Key Contributions)

3.1. 이론적 유틸리티 보장 (Utility Guarantees)

기존 연구가 항목 수 (Cardinality) 에 초점을 맞췄다면, 이 논문은 Missing Mass (누락된 질량) 개념을 도입하여 성능을 평가합니다. Missing Mass는 누락된 항목들의 전체 빈도 비율을 의미하며, 더 강력한 지표입니다.

• Set Union (Zipfian 데이터):
  • WGM 이 Zipfian 분포 (빈도가 $r^{-s}$로 감소) 를 따르는 데이터에서 $\ell_1$ Missing Mass에 대해 거의 최적 (Near-optimal) 의 보장을 제공함을 증명했습니다 (Theorem 3.3).
  • $s$가 클수록 (빈도 편차가 큼) 누락된 질량이 감소함을 보였습니다.
• Distribution-Free $\ell_\infty$ 보장:
  • 데이터 분포에 관계없이 (Zipfian 여부와 상관없이) 최대 누락 빈도 ($\ell_\infty$ Missing Mass) 에 대한 보장을 증명했습니다 (Theorem 3.6). 이는 Top-k 및 k-Hitting Set 문제에 필수적입니다.
• 하한 (Lower Bound) 증명:
  • 제안된 알고리즘의 성능이 이론적으로 최적에 가깝다는 것을 보여주기 위해, 차분 프라이버시를 만족하는 임의의 알고리즘이 달성할 수 있는 성능의 하한을 증명했습니다.

3.2. 확장된 알고리즘 설계

• Private Top-k: WGM 으로 도메인을 먼저 추출한 후, Peeling Exponential Mechanism을 적용하여 Top-k 항목을 선택합니다. 이는 알려진 도메인 설정에서의 Top-k 알고리즘을 확장한 것으로, Missing Mass에 대한 유틸리티 보장을 제공합니다 (Theorem 4.3).
• Private k-Hitting Set: WGM 으로 도메인을 추출한 후, Greedy 알고리즘 (User Peeling Mechanism) 을 적용하여 $k$개의 항목을 선택합니다. 이는 부분 모듈러 최대화 (Submodular Maximization) 문제를 차분 프라이버시 하에서 해결하며, 최적 해에 근접한 성능을 보장합니다 (Theorem 4.5).

4. 실험 결과 (Results)

실제 6 가지 데이터셋 (Reddit, Amazon Games, Movie Reviews, Steam Games 등) 을 사용하여 실험을 수행했습니다.

• Set Union: WGM 기반 방법은 기존 최첨단 (SOTA) 알고리즘 (Policy Gaussian, Policy Greedy) 과 유사하거나 더 나은 Missing Mass 성능을 보였습니다. 특히 WGM 은 계산 비용이 훨씬 낮아 확장성 (Scalability) 면에서 우수했습니다.
• Top-k: 제안된 방법은 기존 알려진 도메인 알고리즘 (Durfee & Rogers, 2019) 보다 일관되게 더 낮은 Top-k Missing Mass를 달성했습니다. 특히 $k$가 커질수록 성능 차이가 벌어졌습니다.
• k-Hitting Set: 알려진 도메인 알고리즘 (공식적으로 공개된 도메인을 가정) 과 비교했을 때, 제안된 방법은 공개 도메인을 가정하지 않음에도 불구하고 유사하거나 더 나은 성능을 보였습니다. 이는 WGM 이 고품질 항목을 포함하면서도 도메인 크기를 줄여 2 단계 알고리즘의 부하를 줄였기 때문입니다.

5. 의의 및 결론

• 이론적 공백 해소: 차분 프라이버시 하의 Set Union 문제에 대해 절대적인 유틸리티 보장 (Absolute Utility Guarantees) 을 최초로 제공했습니다. 기존 연구는 상대적 비교에 그쳤으나, 이 논문은 Missing Mass에 대한 구체적인 상한과 하한을 제시했습니다.
• 실용성: 복잡한 적응형 (Adaptive) 알고리즘 대신 단순하고 확장 가능한 WGM 을 기반으로 하여, 이론적 보장과 실용적 효율성을 동시에 달성했습니다.
• 일반화: Zipfian 분포를 가정하지 않는 $\ell_\infty$ 보장을 통해 다양한 실제 데이터셋에 적용 가능한 강력한 프레임워크를 제시했습니다.

요약하자면, 이 논문은 WGM 을 도메인 발견의 핵심 도구로 재조명하고, 이를 통해 Set Union, Top-k, k-Hitting Set 문제에 대해 이론적으로 엄밀한 유틸리티 보장과 높은 실용적 성능을 동시에 달성하는 새로운 패러다임을 제시했습니다.