Liberação Privada de Estatísticas de Grafos usando Funções de Escada

Proteger a privacidade dos indivíduos em dados estruturados em grafos enquanto disponibiliza versões precisas dos dados é um dos problemas mais desafiadores em privacidade de dados. A maioria dos esforços até agora para realizar essa liberação de dados acaba presa em complexidade, sobrecarrega o sinal com ruído e não é eficaz para uso na prática. Neste artigo, introduzimos um novo método que garante privacidade diferencial. Ele especifica uma distribuição de probabilidade sobre possíveis saídas que é cuidadosamente definida para maximizar a utilidade para a entrada dada, ao mesmo tempo em que fornece o nível de privacidade requerido. A distribuição é projetada para formar uma 'escada', de modo que cada saída atinja o 'degrau' mais alto (máxima probabilidade) em comparação a saídas menos preferíveis. Mostramos como nossa estrutura de escada pode ser aplicada a problemas de contagem do número de ocorrências de subgrafos, um objetivo vital na análise de grafos, e apresentamos algoritmos cujo custo é comparável ao de computar a contagem exatamente. Nosso estudo experimental confirma que nosso método supera os métodos existentes para contagem de triângulos e estrelas em termos de precisão, e fornece soluções para alguns problemas para os quais nenhum método efetivo era conhecido anteriormente. Os resultados de nossos algoritmos podem ser utilizados para estimar os parâmetros de modelos de grafos adequados, permitindo que grafos sintéticos sejam amostrados.