W erze danych grafowych – takich jak sieci społecznościowe, grafy powiązań biznesowych czy mapy wiedzy – coraz częściej pojawia się potrzeba ich publikacji w celach badawczych lub inżynierskich. Ale co jeśli struktura takiego grafu sama w sobie zawiera dane wrażliwe? Nawet bez ujawniania treści, sam fakt istnienia krawędzi (np. relacji między użytkownikami) może prowadzić do naruszenia prywatności.

Tradycyjne podejścia do różnicowej prywatności (DP, ang. Differential Privacy) koncentrują się na ochronie danych podczas uczenia modeli. W tej publikacji autorzy idą o krok dalej — chronią prywatność podczas publikacji danych grafowych. Proponują eleganckie podejście oparte na Gaussian Differential Privacy (GDP), które pozwala na uczenie struktury grafu w sposób zapewniający gwarancje prywatności.

Problem i założenia

Problem:

Jak opublikować graf (np. sieć społecznościową), który można później analizować czy trenować modele, a jednocześnie nie ujawniać prywatnych informacji o jego strukturze (np. o tym, kto z kim jest połączony)?

Założenia:

  • Mamy zbiór rzeczywistych danych grafowych $G$, którego nie chcemy udostępniać w oryginalnej postaci.
  • Chcemy wygenerować syntetyczny graf $\tilde{G}$, który:
    • zachowuje własności statystyczne $G$,
    • pozwala trenować modele tak, jakby były trenowane na $G$,
    • spełnia różnicową prywatność względem $G$.

Podejście matematyczne

Różnicowa prywatność

$$ \text{Mechanizm } M \text{ spełnia } (\varepsilon, \delta)\text{-DP, jeśli dla dowolnych } D, D’ \text{ różniących się jednym elementem:} \ \Pr[M(D) \in S] \leq e^{\varepsilon} \Pr[M(D’) \in S] + \delta $$

Gaussian Differential Privacy (GDP)

$$ \mu = \text{privacy parameter}, \quad GDP \approx \mathcal{N}(\mu, 1) $$

Estymacja parametrów

$$ \ell(\theta; G) = \sum_{(i,j)} y_{ij} \log \sigma(\theta_{ij}) + (1 - y_{ij}) \log(1 - \sigma(\theta_{ij})) $$

Algorytm (skrótowo)

  1. Dane wejściowe: graf $G$
  2. Modelowanie: struktura probabilistyczna
  3. Estymacja parametrów $\theta$ z szumem Gaussa
  4. Generacja grafu $\tilde{G} \sim P_\theta$
  5. Publikacja $\tilde{G}$

Wyniki

Na zbiorach danych (Cora, Citeseer):

  • Zachowanie statystyk
  • Skuteczność modeli trenowanych na $\tilde{G}$
  • Zachowanie prywatności przy niskim $\mu$

Podsumowanie

Metoda oparta na GDP pozwala:

  • zachować prywatność relacji między węzłami,
  • generować realistyczne grafy do dalszej analizy,
  • trenować skuteczne modele.

To ważny krok w stronę bezpiecznego udostępniania danych grafowych.

📎 Linki