Differential Privacy for Markov Chain State Trajectories

Resumen Técnico: Privacidad Diferencial para Trayectorias de Estados de Cadenas de Markov

Planteamiento del Problema
Los sistemas basados en datos dependen frecuentemente de trayectorias de estados generadas por cadenas de Markov para modelar comportos tales como la migración de riesgo crediticio, patrones de tráfico urbano y navegación por internet. Si bien estas trayectorias son útiles, compartirlas plantea riesgos de privacidad significativos, ya que las secuencias cortas a menudo pueden utilizarse para reconstruir identidades de usuarios. Los métodos existentes para privatizar trayectorias de cadenas de Markov suelen tratar la cadena como un autómata de estados finitos no determinista, seleccionando estados privados mediante caminatas aleatorias uniformes que ignoran las probabilidades de transición. Este enfoque genera frecuentemente trayectorias "atípicas" que carecen de las propiedades estructurales de la cadena de Markov subyacente, lo que degrada la utilidad de los datos privatizados para el análisis posterior. Además, el trabajo previo suele privatizar las trayectorias de forma offline o no logra aprovechar las dinámicas de transición específicas para mantener la similitud estructural.

Metodología
Los autores proponen un nuevo marco para generar trayectorias de estados $\epsilon$-diferencialmente privadas de forma online, lo que significa que la trayectoria privada se genera simultáneamente con la sensible. El núcleo de la metodología consiste en tratar la cadena de Markov como un grafo dirigido ponderado donde los pesos de las aristas son los logaritmos negativos de las probabilidades de transición ($W_{ij} = -\log(P_{ij})$).

1. Inducción de Grafo y Distancia: Los autores definen una distancia de camino más corto $G(i, j)$ en este grafo. La Proposición 1 establece que el camino más corto en este grafo corresponde a la ruta más probable entre dos estados en la cadena de Markov.
2. Definición de Adyacencia: Se introduce una nueva noción de adyacencia de trayectorias (Definición 4). Dos trayectorias se consideran adyacentes si la suma de las distancias de camino más corto simétricas entre sus estados correspondientes está acotada por un parámetro $\rho$. Esto difiere del trabajo previo que se basa en la distancia de Hamming (contar entradas diferentes), permitiendo una definición de similitud más matizada basada en la verosimilitud de las transiciones.
3. Diseño del Mecanismo (Mecanismo 1): El mecanismo propuesto genera estados privados online utilizando una estrategia inspirada en el mecanismo de permutación y volteo (permute-and-flip). En cada paso de tiempo $t$, dado el estado privado anterior $s'_{t-1}$ y el estado sensible actual $s_t$, el mecanismo selecciona el siguiente estado privado $s'_t$ de la vecindad factible $N(s'_{t-1})$. La probabilidad de selección está sesgada por la función de utilidad $u(w, w') = -\sum G(s'_t, s_t)$, la cual penaliza los estados que están lejos del estado real en términos de distancia de grafo.
4. Análisis de Deriva: Los autores modelan el proceso conjunto de los estados sensibles y privados como un modelo de Markov oculto. Utilizan el análisis de deriva de Foster-Lyapunov para demostrar que la trayectoria privada exhibe una "deriva negativa", lo que significa que es estadísticamente probable que regrese a una vecindad de la trayectoria sensible si se desvía.

Contribuciones Clave
El artículo realiza cuatro contribuciones principales:

• Nueva Definición de Privacidad y Mecanismo: Los autores introducen una nueva definición de adyacencia para trayectorias de estados de cadenas de Markov basada en distancias de camino más corto y desarrollan el Mecanismo 1, un mecanismo $\epsilon$-diferencialmente privado online adaptado a esta definición.
• Límites de Error: Proporcionan un límite de concentración (Teorema 2) sobre la probabilidad de que la trayectoria privada se desvíe significativamente de la sensible, mostrando que los errores grandes ocurren con una probabilidad que decrece exponencialmente.
• Límites de Tipicidad y Entropía: Los autores acotan la entropía empírica esperada de las trayectorias privadas (Teorema 3) y proporcionan un límite de concentración (Teorema 4) que muestra que las trayectorias privadas se encuentran dentro del conjunto $\eta$-típico de la cadena de Markov subyacente con alta probabilidad. Esto asegura que los datos privatizados retengan las propiedades estadísticas del proceso original.
• Validación Empírica: El mecanismo es probado en tres conjuntos de datos del mundo real: migración crediticia, tráfico de la ciudad (Gainesville, FL) y tráfico de internet (Wikispeedia).

Resultados
Las simulaciones numéricas demuestran que el Mecanismo 1 supera significativamente al mecanismo del estado del arte (Chen et al., 2023b) en términos de utilidad manteniendo el mismo nivel de privacidad:

• Reducción de Entropía: Bajo 3-privacidad diferencial, el Mecanismo 1 exhibe hasta una reducción del 80% en la entropía en comparación con el estado del arte previo. Esto indica que las trayectorias privadas generadas están mucho más cerca de la distribución estadística real de la cadena de Markov.
• Probabilidad de Error: El mecanismo reduce la probabilidad de errores grandes (desviaciones en la distancia de camino más corto) hasta en 4 órdenes de magnitud en comparación con los métodos existentes. Por ejemplo, en el ejemplo de migración crediticia, la probabilidad de un error grande ($v=15$) cayó de 0.003 a $2 \times 10^{-7}$.
• Similitud Estructural: A diferencia de los métodos previos que a menudo derivan en caminatas aleatorias (aumentando la entropía a medida que crece la longitud de la trayectoria), el Mecanismo 1 mantiene un nivel de entropía constante tras cierta longitud de trayectoria, preservando la integridad estructural de los datos.

Significancia
El artículo afirma que su marco aborda el compromiso crítico entre privacidad y utilidad en los datos de cadenas de Markov. Al aprovechar las probabilidades de transición para definir la distancia y la adyacencia, el mecanismo asegura que las trayectorias privatizadas permanezcan "típicas" y estructuralmente similares a los datos sensibles. Esto permite que los sistemas posteriores utilicen los datos privatizados de manera efectiva sin comprometer la privacidad del usuario. Los autores enfatizan que su enfoque no requiere redes neuronales ni funciones de distancia específicas de un contexto, lo que lo hace directamente aplicable a cualquier configuración de cadena de Markov donde se conozcan las probabilidades de transición. El trabajo establece que es posible generar trayectorias privadas online que respeten la dinámica subyacente del sistema, lo que representa una mejora significativa sobre los métodos que tratan los espacios de estados como conjuntos no estructurados.