Technische Samenvatting: Dependency Triad (DT) voor het Kwantificeren van Afhankelijkheden in Local Differential Privacy

1. Probleemstelling

De verzameling van multidimensionale gebruikersgegevens onder Local Differential Privacy (LDP) staat voor een kritieke uitdaging: Correlation-Induced Privacy Leakage (CPL). Hoewel LDP-mechanismen (bijv. $\epsilon$-LDP) de lekkage voor individuele attributen begrenzen, kunnen afhankelijkheden tussen attributen onbedoeld gecorreleerde informatie onthullen, wat de privacykwetsbaarheden verhoogt boven het beoogde budget.

Bestaande oplossingen voor het kwantificeren van CPL lijden aan twee primaire beperkingen die hun praktische toepasbaarheid hinderen:

1. Schaalbaarheid en Mechanismebeperkingen: Veel bestaande algoritmen (bijv. ITS, CBP, HCC-1/2, LTM) zijn ofwel beperkt tot specifieke LDP-mechanismen (bijv. twee-niveau perturbatie) of lijden onder hoge tijd- en ruimtecomplexiteit (bijv. $O(a^2b^2)$ of $O(a^2b \log b)$) ten opzichte van de alfabetgroottes van de attributen ($a, b$). Dit maakt ze onhandelbaar voor attributen met een hoge cardinaliteit of iteratieve privacybudget-kalibratie.
2. Afhankelijkheid van Ground-Truth Distributies: Huidige methoden gaan uit van toegang tot de exacte, ground-truth gezamenlijke waarschijnlijkheidsverdeling tussen attributen. In real-world LDP-scenario's is deze verdeling zelden bekend; deze wordt vaak geschat vanuit eerdere data, publieke datasets of subsets van de populatie. Discrepanties tussen de bekende prior en de werkelijke distributie (door demografische verschuivingen, steekproefbias of veroudering) kunnen leiden tot een onderschatting van de lekkage, wat privacykwetsbaarheden creëert, of een overschatting, wat de bruikbaarheid van de data vermindert.

Het artikel stelt dat er behoefte is aan een metriek die CPL in constante tijd kan schatten, compatibel is met ijle (sparse) distributies, en robuust blijft tegen distributionele onzekerheid zonder kennis van de ground-truth te vereisen.

2. Methodologie: De Dependency Triad (DT)

De auteurs stellen de Dependency Triad (DT) voor, een nieuwe metriek die de pairwise afhankelijkheidsinformatie relevant voor CPL samenvat met behulp van drie parameters: $(\alpha, \beta, \delta)$.

A. Kernconcept

In plaats van de volledige $a \times b$ gezamenlijke distributie op te slaan, comprimeert DT de afhankelijkheidsstructuur in drie scalaire parameters. Dit maakt een constante-tijd ($O(1)$) schatting van CPL mogelijk voor elk privacybudget $\epsilon$.

B. Parameterafleiding

De afleiding omvat het benaderen van de conditionele waarschijnlijkheidsvectoren $G$ en $G'$ (die $P(\hat{X}|X_k=x)$ en $P(\hat{X}|X_k=x')$ vertegenwoordigen) via hun elementgewijze ratio's.

1. $\alpha$ (Bovengrens van Ratio's): Vertegenwoordigt de maximale likelihood-ratio, die het lekkagegedrag in het lage privacy-regime (grote $\epsilon$) bepaalt. Het is gedefinieerd als:
   $$\alpha = \ln \left( \max_{\hat{x}, x, x'} \frac{p(\hat{x}|x) + \Delta_{\hat{x},x}}{p(\hat{x}|x') - \Delta_{\hat{x},x'}} \right)$$
   waarbij $\Delta$ de onzekerheidsmatrix vertegenwoordigt.

2. $\delta$ (Sparsity Correctie): Houdt rekening met gevallen waar de distributie ijl (sparse) is (bijv. wanneer denominatoren nul worden). Het vangt de massa-concentratie op in randgevallen waar $p(\hat{x}|x') = 0$.

3. $\beta$ (Gekalibreerde Ondergrens): Oorspronkelijk werd een parameter $\gamma$ (minimale ratio) gebruikt. De auteurs ontdekten echter dat $(\alpha, \gamma, \delta)$ tot overschattingsfouten kon leiden. Om de nauwkeurigheid te verbeteren terwijl een conservatieve bovengrens behouden blijft, introduceren zij een kalibratiestap. $\beta$ wordt afgeleid door de ondergrens te kalibreren bij een specifere privacybudget $\epsilon_0$ (typisch $\epsilon_0 \to 0$) om overeen te komen met de exacte CPL$^\star$ van de bekende distributie. Dit zorgt ervoor dat de estimator een strakke bovengrens is voor alle $\epsilon \geq \epsilon_0$.

C. Omgaan met Distributionele Onzekerheid

Om de afwezigheid van ground-truth data aan te pakken, incorporeert DT expliciet een onzekerheidsset $\Delta$ rond de bekende distributie $P_K$. De parameters $(\hat{\alpha}, \hat{\beta}, \hat{\delta})$ worden berekend door te optimaliseren over de toegestane regio gedefinieerd door $P_K \pm \Delta$. Dit zorgt ervoor dat de resulterende CPL-schatting een conservatieve bovengrens is, zelfs als de werkelijke distributie $P_A$ afwijkt van $P_K$ binnen de onzekerheidsgrenzen.

D. Algoritmen

• Algoritme 1: Berekent de $(\alpha, \beta, \delta)$ parameters uit een bekende distributie en onzekerheidsmatrix. Dit omvat het itereren over attribuatparen en het oplossen van een gerelaxeerd Lineair Programma (LP) om $\phi$ te vinden (gebruikt voor $\beta$), wat resulteert in een pre-computatie complexiteit van $O(a^2b^{3.5})$.
• Algoritme 2: Schat de CPL met behulp van de vooraf berekende DT-parameters en het privacybudget $\epsilon$ in constante tijd $O(1)$.

3. Belangrijkste Bijdragen

1. Nieuwe Metriek (DT): De eerste metriek die specifiek is ontworpen om pairwise afhankelijkheden samen te vatten voor LDP-lekkageanalyse met behulp van slechts drie parameters. Het dient als een conservatieve surrogaat voor de volledige gezamenlijke distributie.
2. Theoretische Garanties:
   • Bovengrens: De auteurs bewijzen dat de DT-gebaseerde estimator een strakke bovengrens is op de ware CPL ($CPL^\star$), wat garandeert dat gerapporteerde lekkage de ware privacyverlies nooit onderschat.
   • Onzekerheidsrobuustheid: De metriek is bewezen geldig en conservatief te blijven, zelfs wanneer de prior-distributie onzeker of mismatch is.
   • Complexiteit: Het reduceert de ruimtekis van $O(ab)$ naar $O(1)$ en de evaluatietijd van polynomiaal naar constante tijd.
3. Kalibratiemechanisme: Een methode om de parameter $\beta$ te kalibreren om de schattingsfout te minimaliseren terwijl de privacygarantie behouden blijft, wat de nauwkeurigheidsverschillen van eenvoudige ratio-benaderingen aanpakt.
4. Empirische Validatie: Uitgebreide experimenten op vijf real-world datasets (SPM, CelebA, Adult, CVD, DSS) en synthetische data tonen aan dat DT consistent CPL schat met een lage Normalized Mean Square Error (NMSE < 0,025) over diverse afhankelijkheidsregimes en privacybudgets.

4. Experimentele Resultaten

• Nauwkeurigheid: DT bereikt zeer lage schattingsfouten vergeleken met de optimale $CPL^\star$ (berekend door baselines zoals HCC-2 en LTM) over echte datasets. In high-privacy regimes ($\epsilon \in (0, 1]$) is de NMSE uitzonderlijk laag (< 0,003).
• Schaalbaarheid: In tegenstelling tot baselines die voor elk privacybudget herberekening vereisen, maakt DT snelle evaluatie mogelijk. In een scenario van budgetkalibratie voltooide DT de taak in 7 seconden, vergeleken met 61 seconden voor de LTM-baseline.
• Robuustheid tegen Onzekerheid: Wanneer getest met distributionele verschuivingen (gesimuleerd door foutmarges tot 10%–20% te variëren), behield DT een strakke bovengrens op de werkelijke lekkage, terwijl methoden die onzekerheid negeren het risico liepen op onderschatting.
• Structurele Regimes: DT presteerde goed over diverse afhankelijkheidsstructuren (lage entropie, ijl, one-to-many, etc.). Het was extreem strak voor geconcentreerde afhankelijkheden en conservatief accuraat voor ijle of tail-sensitieve distributies.
• Privacy-Utility Afweging: In attributen-inferentie aanvallen en k-marginal schattingstaken bereikte DT-gestuurde budgetkalibratie een vergelijkbare of betere bruikbaarheid (lagere Total Variation Distance) dan standaard splitting (SPL) of random sampling (RS) methoden, met name voor hogere-orde marginalen, terwijl het robuuste weerstand tegen inferentie-aanvallen behield.

5. Betekenis en Claims

Het artikel claimt dat Dependency Triad (DT) de kloof overbrugt tussen theoretische privacyanalyse en praktische implementatie in multidimensionale LDP-omgevingen.

• Praktische Toepasbaarheid: Door de vereiste van ground-truth distributies weg te nemen en constante-tijd schatting mogelijk te maken, maakt DT rigoureuze CPL-analyse haalbaar voor real-world datacollectie-pipelines waar distributies onzeker en hoogdimensionaal zijn.
• Veiligheid: Het conservatieve karakter van de estimator zorgt ervoor dat privacygaranties niet in gevaar komen door mismatches in de distributie, een cruciaal vereiste voor het inzetten van LDP in onbetrouwbare omgevingen.
• Efficiëntie: Het vermogen tot constante-tijd lekkage-schatting maakt dynamische en iteratieve privacybudget-kalibratie mogelijk, waardoor de privacy-utility afweging wordt geoptimaliseerd zonder prohibitieve computationele kosten te veroorzaken.

De auteurs concluderen dat hoewel DT de onderliggende gezamenlijke distributie niet volledig karakteriseert, het een voldoende, hanteerbare en theoretisch solide bouwsteen biedt voor het beoordelen van totale privacy-lekkage in multidimensionale settings, waarbij de schaalbaarheids- en beschikbaarheidsbeperkingen van bestaande methoden worden overwonnen.