Acyclic Graph Pattern Counting under Local Differential Privacy

1. Problema y Contexto

El conteo de patrones en grafos es fundamental para el análisis de redes (detección de fraudes, detección de comunidades, etc.). Sin embargo, liberar estos resultados conlleva riesgos de privacidad. La Privacidad Diferencial Local (LDP) es el estándar de oro para proteger datos en entornos descentralizados, donde cada nodo privatiza sus datos antes de enviarlos a un analista.

A pesar de su importancia, los enfoques existentes de LDP para grafos son limitados:

• Se centran casi exclusivamente en estructuras simples y localizadas como estrellas y triángulos.
• No existe una solución general para contar patrones acíclicos arbitrarios (como caminos, árboles o subgrafos sin ciclos de cualquier tamaño).
• Los métodos actuales basados en Respuesta Aleatorizada (RR) para grafos generales sufren de una utilidad muy pobre (error alto) y costos de comunicación prohibitivos, ya que requieren reconstruir un grafo global ruidoso.

El desafío principal: ¿Es posible diseñar un mecanismo general para contar patrones acíclicos arbitrarios bajo LDP que logre un error de $\tilde{O}(\sqrt{N} \cdot d(G)^k)$ (donde $N$ es el número de nodos, $d(G)$ el grado máximo y $k$ el número de aristas del patrón) y reduzca drásticamente los costos de comunicación?

2. Metodología Propuesta

Los autores proponen el primer marco general para contar patrones acíclicos bajo LDP, abordando dos desafíos fundamentales: la construcción generalizada de patrones y la eliminación de duplicación de nodos.

A. Conteo de Caminatas (Walks) como Base

El primer paso es resolver el conteo de $k$-caminatas (secuencias de nodos conectados que pueden repetir nodos).

• Enfoque: En lugar de publicar listas de vecinos ruidosas (como RR), utilizan una agregación recursiva multi-redonda.
• Mecanismo:
  1. Inicializan cada nodo con un contador de 1 (caminata de longitud 0).
  2. En cada ronda $\ell$, los nodos agregan los contadores de sus vecinos de la ronda anterior.
  3. Se añade ruido de Laplace proporcional a la sensibilidad global (basada en el máximo de contadores) para garantizar LDP.
  4. Se optimiza reduciendo las rondas de $k$ a $k-1$ y moviendo el cálculo del máximo global al analista, reduciendo la complejidad computacional por nodo de $O(N)$ a $O(d(G))$.
• Resultado: Error $\tilde{O}(\sqrt{N} d(G)^{k-1})$ y costo de comunicación $O(M+N)$.

B. Eliminación de Duplicación: Marcado Aleatorio (Random Marking)

Para contar caminos (donde los nodos no pueden repetirse) y patrones acíclicos generales, es crucial evitar ciclos o nodos repetidos.

• Inspiración: Técnica de color-coding (codificación por colores) usada en algoritmos no privados.
• Estrategia:
  1. Cada nodo $v_i$ asigna aleatoriamente una "marca" $r_i$ uniforme en $\{0, 1, \dots, k\}$.
  2. Se impone la restricción estricta: un nodo solo puede participar en la posición $r_i$ del patrón.
  3. Esto transforma el problema de "detectar repetición" (difícil en LDP) en un problema de "filtrado por posición" (fácil de implementar localmente).
• Corrección de Sesgo: Dado que un patrón válido solo se cuenta si todos sus nodos reciben las marcas correctas (probabilidad $(k+1)^{-(k+1)}$), el analista escala el resultado final multiplicando por $(k+1)^{k+1}$. Esto introduce un error de muestreo, pero mantiene el estimador insesgado.

C. Generalización a Patrones Acíclicos Arbitrarios

Para patrones que no son simples caminos (ej. árboles con ramificaciones):

• Transformación a Árbol: Cualquier patrón acíclico se modela como un árbol con una raíz y un orden de visita (post-orden o similar).
• Conteo Recursivo: Se adapta el mecanismo de caminatas para realizar un conteo recursivo de subárboles. Los nodos agregan resultados de sus hijos en el árbol del patrón según el orden definido.
• Integración: Se combina la agregación recursiva con el marcado aleatorio para garantizar que ningún nodo aparezca más de una vez en una instancia del patrón.

3. Contribuciones Clave

1. Primera Solución General: Presentan el primer mecanismo LDP capaz de contar cualquier patrón acíclico de $k$ aristas, superando la limitación de métodos anteriores restringidos a estrellas o triángulos.
2. Mejora Teórica de Utilidad: Logran un error aditivo de $\tilde{O}(\sqrt{N} d(G)^k)$. Esto es una mejora exponencial sobre los métodos basados en RR, que tienen un error de $O(N^k)$.
3. Eficiencia en Comunicación y Computación:
   • Reducen el costo de comunicación de $O(N^2)$ (típico en RR) a $O(M + N)$.
   • Reducen la complejidad computacional por nodo de $O(N)$ a $O(d(G))$.
   • El analista tiene una complejidad de $O(N)$.
4. Mecanismos Específicos:
   • $M_{k-wk}$: Para caminatas ($k$-line walks).
   • $M_{k-pt}$: Para caminos ($k$-line paths).
   • $M_T$: Para patrones acíclicos generales.
   • $M_{k★}$: Una versión optimizada de una sola ronda para conteo de estrellas.

4. Resultados Experimentales

Los autores evaluaron sus mecanismos en 6 conjuntos de datos reales (AstroPh, Enron, Twitter, etc.) comparándolos con el estado del arte (métodos RR y otros basados en clipping).

• Utilidad (Error Relativo):
  • Para conteo de caminatas, lograron un error relativo < 8% en todos los conjuntos de datos.
  • Comparado con los métodos base, mostraron mejoras en la utilidad de 46x a 2600x (reducción del error).
  • El error se mantiene bajo incluso para patrones de mayor tamaño ($k=6$).
• Costo de Comunicación:
  • Reducción de costos de 300x a 650x en comparación con los métodos RR.
  • El costo se mantiene estable independientemente del tamaño del patrón $k$, gracias a la optimización de rondas.
• Análisis de Error:
  • Se demostró que el error total está dominado por el error de muestreo (debido al marcado aleatorio) más que por el ruido de privacidad, aunque ambos son manejables.
  • Se propuso una estrategia de promediar múltiples ejecuciones ($n_{rep}$) para equilibrar el error de muestreo y el ruido DP, mejorando aún más la precisión.

5. Significado e Impacto

Este trabajo cierra una brecha significativa en la literatura de privacidad de grafos.

• Viabilidad Práctica: Demuestra que el conteo de patrones complejos en entornos descentralizados es viable sin sacrificar la privacidad ni la utilidad.
• Escalabilidad: Al reducir la complejidad de $O(N^2)$ a $O(M+N)$, hace posible aplicar LDP a grafos del mundo real que antes eran inmanejables debido al costo de comunicación.
• Marco General: Proporciona una plantilla para futuros trabajos en privacidad de grafos, mostrando cómo combinar técnicas de agregación recursiva con restricciones estructurales (marcado aleatorio) para resolver problemas NP-difíciles en el contexto de privacidad.

En resumen, el paper presenta un avance fundamental al transformar el conteo de patrones acíclicos bajo LDP de un problema con soluciones ad-hoc y de baja utilidad a una solución general, eficiente y teóricamente sólida.