Será defendida no dia 28 de agosto de 2026, às 14:00 horas, por videoconferência, a Tese de Doutorado intitulada “Abordagem de Otimização para Alocação de Privacy Budget no Problema de Agrupamento Diferencialmente Privado”, do candidato ao título de Doutor em Computação – Augusto César Fadel.

Link para defesa: https://meet.google.com/hai-kgtu-pii

Abordagem de Otimização para Alocação de Privacy Budget no Problema de Agrupamento Diferencialmente Privado

Resumo:

Nas últimas décadas, a crescente digitalização intensificou os riscos de reidentificação e exposição de dados sensíveis, tornando a privacidade um desafio central na análise de dados, ao mesmo tempo em que o compartilhamento de dados é cada vez mais estratégico. Nesse contexto, abordagens tradicionais de proteção são frequentemente custosas ou insuficientes, o que tem impulsionado o uso de Tecnologias de Aprimoramento da Privacidade (Privacy Enhancing Technologies – PETs), com destaque para a Privacidade Diferencial (PD), reconhecida por oferecer garantias formais e matematicamente rigorosas de proteção à privacidade.

Apesar de sua robustez teórica, a aplicação de PD ainda impõe desafios relevantes, sobretudo na definição e alocação adequada de privacy budget, parâmetro que afeta diretamente o equilíbrio entre privacidade e utilidade. Esse desafio torna-se particularmente relevante no contexto da análise de agrupamentos, em que os algoritmos podem realizar sucessivas operações sobre os dados durante o processo de formação dos grupos. Nesse cenário, o DPk-means, variante diferencialmente privada do k-means, destaca-se como uma das abordagens mais estudadas devido à sua simplicidade e escalabilidade. Entretanto, sua natureza iterativa torna crítica a alocação de privacy budget, uma vez que a perda de privacidade se acumula ao longo das atualizações dos centroides. Alocações inadequadas podem introduzir ruído excessivo e degradar significativamente a qualidade das soluções de agrupamento produzidas.

Embora diversos trabalhos proponham a incorporação de PD em algoritmos de agrupamento, a alocação de privacy budget ainda é majoritariamente abordada por meio de estratégias heurísticas, com limitada exploração de técnicas de otimização capazes de tratar sistematicamente o compromisso entre utilidade e privacidade. Nesse sentido, esta tese investigou o uso de metaheurísticas para o problema de alocação de privacy budget no DPk-means, partindo da hipótese de que abordagens baseadas em otimização podem aumentar a utilidade das soluções sem comprometer as garantias formais de privacidade.

Para isso, foi proposta uma representação baseada em chaves aleatórias para modelar a alocação de privacy budget ao longo das iterações do DPk-means, buscando melhorar a qualidade dos centroides e das partições geradas. Essa representação foi combinada com as metaheurísticas BRKGA, ILS e VNS, dando origem a três algoritmos implementados por meio do framework Random-Key Optimizer (RKO), que exploram o espaço de alocações em busca de configurações que maximizem a utilidade da solução de agrupamento sob restrições de privacidade.

Os experimentos computacionais realizados com 30 instâncias demonstraram superioridade consistente das abordagens propostas em relação às principais estratégias da literatura. Em particular, o algoritmo baseado no BRKGA apresentou o melhor desempenho global, em termos dos índices utilizados para avaliar a utilidade das soluções de agrupamento obtidas. Considerando o mecanismo de melhor desempenho, apresentou mediana do gap percentual em relação à melhor solução de aproximadamente 6%, enquanto a melhor estratégia da literatura obteve cerca de 110% sob o mesmo cenário. Esses resultados evidenciam a magnitude do ganho obtido e reforçam o potencial de abordagens baseadas em otimização para a alocação de privacy budget, contribuindo para o avanço do estado da arte no agrupamento diferencialmente privado.

Abstract:

In recent decades, increasing digitalization has intensified the risks of re-identification and exposure of sensitive data, making privacy a central challenge in data analysis, while data sharing is becoming increasingly strategic. In this context, traditional protection approaches are often costly or insufficient, which has driven the adoption of Privacy Enhancing Technologies (PETs), particularly Differential Privacy (DP), recognized for providing formal and mathematically rigorous privacy guarantees.

Despite its theoretical robustness, the application of DP still poses significant challenges, particularly regarding the definition and allocation of the privacy budget, a parameter that directly affects the trade-off between privacy and utility. This challenge becomes especially relevant in the context of clustering analysis, where algorithms may perform successive operations on the data throughout the cluster formation process. In this setting, DPk-means, the differentially private variant of k-means, stands out as one of the most widely studied approaches due to its simplicity and scalability. However, its iterative nature makes privacy budget allocation critical, since privacy loss accumulates over successive centroid updates. Inadequate allocations may introduce excessive noise and significantly degrade the quality of the resulting clustering solutions.

Although several studies propose incorporating DP into clustering algorithms, privacy budget allocation is still predominantly addressed through heuristics strategies, with limited exploration of optimization techniques capable of systematically handling the privacy–utility trade-off. In this context, this thesis investigated the use of metaheuristics for the privacy budget allocation problem in DPk-means, based on the hypothesis that optimization-based approaches can increase solution utility without compromising formal privacy guarantees.

To this end, a random-key-based representation was proposed to model privacy budget allocation across DPk-means iterations, aiming to improve the quality of the resulting centroids and partitions. This representation was combined with the BRKGA, ILS, and VNS metaheuristics, giving rise to three algorithms implemented within the Random-Key Optimizer (RKO) framework, which explore the allocation space in search of configurations that maximize the utility of clustering solution under privacy constraints.

Computational experiments conducted on 30 instances demonstrated the consistent superiority of the proposed approaches over the leading strategies reported in the literature. In particular, the BRKGAPD algorithm achieved the best overall performance according to clustering quality metrics. Under the best-performing privacy mechanism, it achieved a median percentage gap of approximately 6% relative to the best-known solution, whereas the best strategy from the literature obtained a gap of about 110% under the same conditions. These results highlight substantial performance gains and reinforce the potential of optimization-based approaches for privacy budget allocation, contributing to the advancement of the state of the art in differentially private clustering.

Banca examinadora:

Prof. Luiz Satoru Ochi, UFF – Presidente

Prof. Igor Machado Coelho, UFF

Prof. Fábio Protti, UFF

Prof. José André de Moura Brito, ENCE/IBGE

Prof. Gustavo Silva Semaan, UFRRJ

Prof. Gustavo da Silva Ferreira, ENCE/IBGE

Prof. Leonardo Silva de Lima, UFPR

Prof. Mauricio Guilherme de Carvalho Resende, UNIFESP