Resumo Técnico: Triade de Dependência (DT) para Quantificação de Dependências em Privacidade Diferencial Local

1. Definição do Problema

A coleta de dados multidimensionais de usuários sob Privacidade Diferencial Local (LDP) enfrenta um desafio crítico: a Vazamento de Privacidade Induzido por Correlação (CPL). Embora os mecanismos de LDP (ex: $\epsilon$-LDP) limitem o vazamento para atributos individuais, as dependências entre atributos podem inadvertidamente revelar informações correlacionadas, aumentando as vulnerabilidades de privacidade além do orçamento pretendido.

As soluções existentes para quantificar CPL sofrem de duas limitações primárias que impedem sua aplicabilidade prática:

1. Escalabilidade e Restrições de Mecanismo: Muitos algoritmos existentes (ex: ITS, CBP, HCC-1/2, LTM) são restritos a mecanismos de LDP específicos (ex: perturbação de dois níveis) ou sofrem de alta complexidade de tempo e espaço (ex: $O(a^2b^2)$ ou $O(a^2b \log b)$) em relação aos tamanhos de alfabeto dos atributos ($a, b$). Isso os torna intratáveis para atributos de alta cardinalidade ou calibração iterativa de orçamento de privacidade.
2. Dependência de Distribuições de Verdade Fundamental (Ground-Truth): Os métodos atuais assumem o acesso à distribuição de probabilidade conjunta exata e de verdade fundamental entre os atributos. Em cenários reais de LDP, essa distribuição raramente é conhecida; ela é frequentemente estimada a partir de dados prévios, conjuntos de dados públicos ou subconjuntos da população. Discrepâncias entre o conhecimento prévio (prior) e a distribuição real (devido a mudanças demográficas, viés de amostragem ou obsolescência) podem levar à subestimação do vazamento, criando vulnerabilidades de privacidade, ou à superestimação, reduzindo a utilidade dos dados.

O artigo postula que há necessidade de uma métrica que possa estimar CPL em tempo constante, seja compatível com distribuições esparsas e permaneça robusta à incerteza distributiva sem exigir conhecimento da verdade fundamental.

2. Metodologia: A Triade de Dependência (DT)

Os autores propõem a Triade de Dependência (DT), uma nova métrica que resume a informação de dependência pareada relevante para CPL usando três parâmetros: $(\alpha, \beta, \delta)$.

A. Conceito Central

Em vez de armazenar a distribuição conjunta completa de $a \times b$, a DT comprime a estrutura de dependência em três parâmetros escalares. Isso permite a estimativa em tempo constante ($O(1)$) do CPL para qualquer orçamento de privacidade $\epsilon$.

B. Derivação de Parâmetros

A derivação envolve a aproximação dos vetores de probabilidade condicional $G$ e $G'$ (representando $P(\hat{X}|X_k=x)$ e $P(\hat{X}|X_k=x')$) através de suas razões elemento a elemento.

1. $\alpha$ (Limite Superior de Razões): Representa a razão de verossimilhança máxima, regendo o comportamento de vazamento no regime de baixa privacidade (grande $\epsilon$). É definido como:
   $$\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)$$
   onde $\Delta$ representa a matriz de incerteza.

2. $\delta$ (Correção de Esparsidade): Considera casos onde a distribuição é esparsa (ou seja, denominadores tornam-se zero). Ele captura a concentração de massa em casos extremos onde $p(\hat{x}|x') = 0$.

3. $\beta$ (Limite Inferior Calibrado): Originalmente, um parâmetro $\gamma$ (razão mínima) era usado. No entanto, os autores descobriram que $(\alpha, \gamma, \delta)$ poderia levar a erros de superestimação. Para melhorar a precisão mantendo um limite superior conservador, eles introduzem uma etapa de calibração. $\beta$ é derivado calibrando o limite inferior em um orçamento de privacidade específico $\epsilon_0$ (tipicamente $\epsilon_0 \to 0$) para corresponder ao CPL exato ($CPL^\star$) da distribuição conhecida. Isso garante que o estimador seja um limite superior apertado para todos os $\epsilon \geq \epsilon_0$.

C. Tratamento de Incerteza Distributiva

Para abordar a falta de dados de verdade fundamental, a DT incorpora explicitamente um conjunto de incerteza $\Delta$ em torno da distribuição conhecida $P_K$. Os parâmetros $(\hat{\alpha}, \hat{\beta}, \hat{\delta})$ são computados otimizando sobre a região viável definida por $P_K \pm \Delta$. Isso garante que a estimativa de CPL resultante seja um limite superior conservador, mesmo se a distribuição real $P_A$ desviar de $P_K$ dentro dos limites de incerteza.

D. Algoritmos

• Algoritmo 1: Computa os parâmetros $(\alpha, \beta, \delta)$ a partir de uma distribuição conhecida e matriz de incerteza. Envolve iterar sobre pares de atributos e resolver um Programa Linear (LP) relaxado para encontrar $\phi$ (usado para $\beta$), resultando em uma complexidade de pré-computação de $O(a^2b^{3.5})$.
• Algoritmo 2: Estima o CPL usando os parâmetros DT pré-computados e o orçamento de privacidade $\epsilon$ em tempo constante $O(1)$.

3. Principais Contribuições

1. Métrica Inovadora (DT): A primeira métrica especificamente desenhada para resumir dependências pareadas para análise de vazamento de LDP usando apenas três parâmetros. Ela serve como um substituto (surrogate) conservador para a distribuição conjunta completa.
2. Garantias Teóricas:
   • Limite Superior: Os autores provam que o estimador baseado em DT é um limite superior apertado sobre o verdadeiro CPL ($CPL^\star$), garantindo que o vazamento relatado nunca subestime a perda real de privacidade.
   • Robustez à Incerteza: A métrica é provada como válida e conservadora mesmo quando a distribuição prévia é incerta ou desalinhada.
   • Complexidade: Reduz a complexidade de espaço de $O(ab)$ para $O(1)$ e o tempo de avaliação de polinomial para constante.
3. Mecanismo de Calibração: Um método para calibrar o parâmetro $\beta$ para minimizar o erro de estimativa enquanto preserva a garantia de privacidade, abordando as lacunas de precisão das simples aproximações de razão.
4. Validação Empírica: Experimentos extensos em cinco conjuntos de dados do mundo real (SPM, CelebA, Adult, CVD, DSS) e dados sintéticos demonstram que a DT estima consistentemente o CPL com baixo Erro Quadrático Médio Normalizado (NMSE < 0,025) através de diversos regimes de dependência e orçamentos de privacidade.

4. Resultados Experimentais

• Precisão: A DT alcança erros de estimativa muito baixos em comparação com o $CPL^\star$ ótimo (computado por baselines como HCC-2 e LTM) em conjuntos de dados reais. Em regimes de alta privacidade ($\epsilon \in (0, 1]$), o NMSE é excepcionalmente baixo (< 0,003).
• Escalabilidade: Ao contrário das baselines que exigem recomputação para cada orçamento de privacidade, a DT permite avaliação rápida. Em um cenário de calibração de orçamento, a DT completou a tarefa em 7 segundos comparado a 61 segundos da baseline LTM.
• Robustez à Incerteza: Quando testada com desvios distributivos (simulados variando margens de erro até 10%–20%), a DT manteve um limite superior apertado sobre o vazamento real, enquanto métodos que ignoram a incerteza arriscaram a subestimação.
• Regimes Estruturais: A DT teve bom desempenho em várias estruturas de dependência (baixa entropia, esparsa, um-para-muitos, etc.). Foi extremamente precisa para dependências concentradas e conservadoramente precisa para distribuições esparsas ou sensíveis à cauda.
• Troca Privacidade-Utilidade: Em tarefas de ataque de inferência de atributo e estimativa de marginais k, a calibração de orçamento habilitada pela DT alcançou utilidade comparável ou melhor (menor Distância de Variação Total) do que os métodos de divisão padrão (SPL) ou amostragem aleatória (RS), particularmente para marginais de ordem superior, mantendo resistência robusta a ataques de inferência.

5. Significância e Alegações

O artigo afirma que a Triade de Dependência (DT) preenche a lacuna entre a análise teórica de privacidade e a implementação prática em ambientes LDP multidimensionais.

• Aplicabilidade Prática: Ao remover o requisito de distribuições de verdade fundamental e permitir a estimativa em tempo constante, a DT torna a análise rigorosa de CPL viável para pipelines de coleta de dados do mundo real onde as distribuições são incertas e de alta dimensão.
• Segurança: A natureza conservadora do estimador garante que as garantias de privacidade não sejam comprometidas por desalinhamentos distributivos, um requisito crítico para implantar LDP em ambientes não confiáveis.
• Eficiência: A capacidade de realizar estimativa de vazamento em tempo constante permite a calibração dinâmica e iterativa do orçamento de privacidade, otimizando a troca entre privacidade e utilidade sem incorrer em custos computacionais proibitivos.

Os autores concluem que, embora a DT não caracterize totalmente a distribuição conjunta subjacente, ela fornece um bloco de construção suficiente, tratável e teoricamente sólido para avaliar o vazamento total de privacidade em configurações multidimensionais, superando as limitações de escalabilidade e disponibilidade de dados dos métodos existentes.