Differential Privacy for Markov Chain State Trajectories

Resumo Técnico: Privacidade Diferencial para Trajetórias de Estados de Cadeias de Markov

Declaração do Problema
Sistemas orientados por dados frequentemente dependem de trajetórias de estados geradas por cadeias de Markov para modelar comportamentos como migração de risco de crédito, padrões de tráfego urbano e navegação na internet. Embora essas trajetórias sejam úteis, compartilhá-las acarreta riscos significativos à privacidade, pois sequências curtas podem frequentemente ser usadas para reconstruir identidades de usuários. Métodos existentes para privatizar trajetórias de cadeias de Markov frequentemente tratam a cadeia como um autômato de estados finitos não determinístico, selecionando estados privados via caminhadas aleatórias uniformes que ignoram as probabilidades de transição. Essa abordagem frequentemente gera trajetórias "atípicas" que carecem das propriedades estruturais da cadeia de Markov subjacente, degradando assim a utilidade dos dados privatizados para análises subsequentes. Além disso, trabalhos anteriores frequentemente privatizam trajetórias offline ou falham em aproveitar as dinâmicas de transição específicas para manter a similaridade estrutural.

Metodologia
Os autores propõem um novo framework para gerar trajetórias de estados $\epsilon$-diferencialmente privadas online, o que significa que a trajetória privada é gerada simultaneamente com a sensível. O núcleo da metodologia envolve tratar a cadeia de Markov como um grafo direcionado ponderado onde os pesos das arestas são os logaritmos negativos das probabilidades de transição ($W_{ij} = -\log(P_{ij})$).

1. Indução de Grafo e Distância: Os autores definem uma distância de caminho mais curto $G(i, j)$ neste grafo. A Proposição 1 estabelece que o caminho mais curto neste grafo corresponde ao caminho mais provável entre dois estados na cadeia de Markov.
2. Definição de Adjacência: Uma nova noção de adjacência de trajetória é introduzida (Definição 4). Duas trajetórias são consideradas adjacentes se a soma das distâncias de caminho mais curto simétricas de seus estados correspondentes for limitada por um parâmetro $\rho$. Isso difere do trabalho anterior que depende da distância de Hamming (contagem de entradas divergentes), permitindo uma definição de similaridade mais matizada baseada na probabilidade de transições.
3. Design de Mecanismo (Mecanismo 1): O mecanismo proposto gera estados privados online usando uma estratégia inspirada no mecanismo permute-and-flip. Em cada passo de tempo $t$, dado o estado privado anterior $s'_{t-1}$ e o estado sensível atual $s_t$, o mecanismo seleciona o próximo estado privado $s'_t$ a partir do vizinhança viável $N(s'_{t-1})$. A probabilidade de seleção é enviesada pela função de utilidade $u(w, w') = -\sum G(s'_t, s_t)$, que penaliza estados que estão longe do estado verdadeiro em termos de distância de grafo.
4. Análise de Drift: Os autores modelam o processo conjunto dos estados sensíveis e privados como um modelo de Markov oculto. Eles utilizam a análise de drift de Foster-Lyapunov para provar que a trajetória privada exibe "drift negativo", o que significa que é estatisticamente provável que ela retorne a uma vizinhança da trajetória sensível se ela se desviar.

Principais Contribuições
O artigo apresenta quatro contribuições primárias:

• Novo Mecanismo e Definição de Privacidade: Os autores introduzem uma nova definição de adjacência para trajetórias de estados de cadeias de Markov baseada em distâncias de caminho mais curto e desenvolvem o Mecanismo 1, um mecanismo $\epsilon$-diferencialmente privado online adaptado a essa definição.
• Limites de Erro: Eles fornecem um limite de concentração (Teorema 2) sobre a probabilidade de a trajetória privada desviar-se significativamente da trajetória sensível, mostrando que erros grandes ocorrem com probabilidade exponencialmente decrescente.
• Limites de Tipicidade e Entropia: Os autores limitam a entropia empírica esperada das trajetórias privadas (Teorema 3) e fornecem um limite de concentração (Teorema 4) mostrando que as trajetórias privadas residem no conjunto $\eta$-típico da cadeia de Markov subjacente com alta probabilidade. Isso garante que os dados privatizados mantenham as propriedades estatísticas do processo original.
• Validação Empírica: O mecanismo é testado em três conjuntos de dados do mundo real: migração de crédito, tráfego urbano (Gainesville, FL) e tráfego de internet (Wikispeedia).

Resultos
Simulações numéricas demonstram que o Mecanismo 1 supera significativamente o mecanismo de última geração (Chen et al., 2023b) em termos de utilidade, mantendo o mesmo nível de privacidade:

• Redução de Entropia: Sob 3-privacidade diferencial, o Mecanismo 1 exibe até uma redução de 80% na entropia em comparação com o estado da arte anterior. Isso indica que as trajetórias privadas geradas estão muito mais próximas da distribuição estatística real da cadeia de Markov.
• Probabilidade de Erro: O mecanismo reduz a probabilidade de erros grandes (desvios na distância de caminho mais curto) em até 4 ordens de magnitude em comparação com métodos existentes. Por exemplo, no exemplo de migração de crédito, a probabilidade de um erro grande ($v=15$) caiu de 0,003 para $2 \times 10^{-7}$.
• Similaridade Estrutural: Ao contrário de métodos anteriores que frequentemente degeneram em caminhadas aleatórias (aumentando a entropia conforme a trajetória cresce), o Mecanismo 1 mantém um nível de entropia constante após um certo comprimento de trajetória, preservando a integridade estrutural dos dados.

Significância
O artigo afirma que seu framework aborda o equilíbrio crítico entre privacidade e utilidade nos dados de cadeias de Markov. Ao aproveitar as probabilidades de transição para definir distância e adjacência, o mecanismo garante que as trajetórias privatizadas permaneçam "típicas" e estruturalmente similares aos dados sensíveis. Isso permite que sistemas subsequentes utilizem os dados privatizados de forma eficaz sem comprometer a privacidade do usuário. Os autores enfatizam que sua abordagem não requer redes neurais ou funções de distância específicas de contexto, tornando-a diretamente aplicável a qualquer cenário de cadeia de Markov onde as probabilidades de transição sejam conhecidas. O trabalho estabelece que é possível gerar trajetórias privadas online que respeitem a dinâmica subjacente do sistema, uma melhoria significativa sobre métodos que tratam espaços de estados como conjuntos não estruturados.