Diferencijalna privatnost na grafovima povjerenja

Diferencijalna privatnost (DP) je matematički stroga i široko istražena okvir za privatnost koji osigurava da izlaz nasumičnog algoritma ostaje statistički neistraživ čak i ako se podaci jednog korisnika promijene. Ovaj okvir je detaljno istražen u teoriji i praksi, s mnogim primjenama u analizi i strojnom učenju. Dva glavna modela DP-a su centralni model i lokalni model. U centralnom modelu, povjerljivi kurator ima pristup sirovim podacima i odgovoran je za proizvodnju diferencijalno privatnog izlaza. Lokalni model zahtijeva da sve poruke poslane s korisnikovog uređaja budu same diferencijalno privatne, uklanjajući potrebu za povjerljivim kuratorom. Dok je lokalni model privlačan zbog minimalnih zahtjeva za povjerenjem, često dolazi s značajno većom degradacijom korisnosti u odnosu na centralni model.

U stvarnim scenarijima dijeljenja podataka, korisnici često postavljaju različite razine povjerenja u druge, ovisno o njihovim odnosima. Na primjer, netko može biti spremni podijeliti svoje podatke o lokaciji s obitelji ili bliskim prijateljima, ali bi se izdržao da stranci pristupe istim podacima. Ova asimetrija podudara se s filozofskim pogledima na privatnost kao kontrolu nad osobnim informacijama, gdje pojedinci navode s kim su spremni podijeliti svoje podatke. Takve finije preferencije za privatnost ističu potrebu za okvirima koji prelaze binarne pretpostavke povjerenja postojećih diferencijalno privatnih modela, pružajući realističnije dinamike povjerenja u sistemima za očuvanje privatnosti.

U radu “Diferencijalna privatnost na grafovima povjerenja”, objavljenom na Konferenciji o inovacijama u teorijskom računarstvu (ITCS 2025), koristimo graf povjerenja za modeliranje odnosa, gdje čvorovi predstavljaju korisnike, a povezani čvorovi povjeruju jedni drugima. Istražujemo kako primijeniti DP na ove grafe povjerenja, osiguravajući da se jamstvo privatnosti primjenjuje na poruke koje korisnik (ili njihovi povjerljivi susjedi) dijeli s onima kojima ne povjerava. Posebno, distribucija poruka koje svaki korisnik u ili jedan od njihovih susjeda razmjenjuje s bilo kojim drugim korisnikom kome u ne povjerava, trebala bi biti statistički neistraživa ako se unos koji drži u promijeni, što nazivamo diferencijalnom privatnošću na grafovima povjerenja (TGDP).

Primjer grafa povjerenja s dijeljenjem lokacije. Alice dijeli svoju lokaciju s Bobom, koji dijeli svoju lokaciju s Carol i Dave. Carol i Dave dijele svoju lokaciju s Eve. Prema definiciji diferencijalne privatnosti na grafovima povjerenja koju uvodimo, zahtijeva se da Carol, Dave i Eve ne mogu identificirati Aliceove informacije, čak i ako bi spojili sve svoje podatke i one koje su im podijeljene.

Diferencijalna privatnost na grafovima povjerenja (TGDP) prirodno interpolira između centralnog i lokalnog modela. Centralni model je ekvivalentan TGDP-u nad zvjezdanim grafom, s povjerljivim centralnim kuratorom na sredini povezan s svim ostalim korisnicima. Lokalni model, s druge strane, je ekvivalentan TGDP-u nad potpuno nepovezanim grafom, u kojem nijedan korisnik ne povjerava drugom korisniku. Algoritmi koji moraju zadovoljiti centralnu DP mogu biti točniji od algoritama koji moraju zadovoljiti lokalnu DP, jer postoji veća fleksibilnost u dijeljenju podataka pod centralnom DP. S TGDP-om, možemo kvantificirati točnost algoritama pod više generalnim odnosima povjerenja.

Kvantificiramo točnost posebno kroz jednostavan zadatak agregacije, koji je gradivni blok za složenije zadatke strojnog učenja. Pretpostavimo da svaki korisnik ima privatnu vrijednost podataka, x_i, koja je realan broj ograničen u nekom rasponu. Cilj zadatka agregacije je razviti algoritam koji može procijeniti zbroj svih vrijednosti korisnika, Σ_i x_i, s što manjim greškom (mjerenom kao srednja kvadratna greška). U sljedećim sekcijama pružamo i gornje i donje granice greške algoritama za agregaciju koji zadovoljavaju TGDP. Ove granice kvantificiraju granice TGDP algoritama: možemo postići barem toliko dobro kao i gornja granica, a nijedan TGDP algoritam ne može biti bolji od donje granice.

Algoritam na temelju dominirajućeg skupa

Pružamo algoritam za agregaciju koji zadovoljava TGDP. I algoritam i gornja granica oslanjaju se na dominirajući skup grafa povjerenja. Dominirajući skup T je podskup čvorova grafa takav da svaki čvor koji nije u T susjedan je barem jednom čvoru u T. Na primjer, u grafu povjerenja prikazanom desno, {A, C} je dominirajući skup, dok {B, D} nije.

Gornja granica

Gornja granica greške za algoritam agregacije na temelju dominirajućeg skupa može se izraziti kao:

σ^2 / |T| + 2εσ,

gdje je σ^2 varijanca privatnih vrijednosti korisnika, |T| veličina dominirajućeg skupa, a ε parametar diferencijalne privatnosti. Ova granica pokazuje kako varijanca i veličina dominirajućeg skupa utječu na grešku algoritma. Manja varijanca i veći dominirajući skup rezultiraju manjom greškom.

Donja granica

Donja granica greške za algoritam agregacije na temelju dominirajućeg skupa može se izraziti kao:

max(σ^2 / n, εσ),

gdje je n ukupan broj korisnika. Ova granica pokazuje da greška ne može biti manja od maksimalne vrijednosti između σ^2 / n i εσ. To znači da, bez obzira na veličinu dominirajućeg skupa, greška ne može biti manja od ove donje granice.

Primjena

Algoritam na temelju dominirajućeg skupa može se primijeniti u različitim scenarijima, uključujući senzorske mreže, socijalne mreže i distribucijske sisteme. U senzorskoj mreži, svaki čvor predstavlja senzor koji prikuplja podatke o okolini, a dominirajući skup čvorova može biti izabran na temelju njihove pozicije i povezanosti. U socijalnoj mreži, svaki čvor predstavlja korisnika, a dominirajući skup korisnika može biti izabran na temelju njihovih veza i povjerenja. U distribucijskom sistemu, svaki čvor predstavlja poslovni proces, a dominirajući skup procesa može biti izabran na temelju njihove važnosti i interakcija.

Zaključak

Diferencijalna privatnost na grafovima povjerenja pruža fleksibilan i realističan okvir za očuvanje privatnosti u različitim scenarijima. Algoritmi koji zadovoljavaju TGDP mogu biti točniji od onih koji zadovoljavaju centralnu ili lokalnu DP, a njihova greška može se kvantificirati na temelju varijance privatnih vrijednosti korisnika i veličine dominirajućeg skupa. Budući da TGDP prirodno interpolira između centralnog i lokalnog modela, može se primijeniti u različitim aplikacijama i scenarijima, pružajući realističnije dinamike povjerenja u sistemima za očuvanje privatnosti.

Česta pitanja

Što je diferencijalna privatnost?

Diferencijalna privatnost (DP) je okvir za privatnost koji osigurava da izlaz nasumičnog algoritma ostaje statistički neistraživ čak i ako se podaci jednog korisnika promijene. Ovaj okvir je široko istraživan u teoriji i praksi, s mnogim primjenama u analizi i strojnom učenju.

Koja je razlika između centralnog i lokalnog modela diferencijalne privatnosti?

Centralni model zahtijeva povjerljivog kuratora koji ima pristup sirovim podacima i odgovoran je za proizvodnju diferencijalno privatnog izlaza. Lokalni model zahtijeva da sve poruke poslane s korisnikovog uređaja budu same diferencijalno privatne, uklanjajući potrebu za povjerljivim kuratorom. Lokalni model je privlačan zbog minimalnih zahtjeva za povjerenjem, ali dolazi s većom degradacijom korisnosti.

Kako se diferencijalna privatnost primjenjuje na grafove povjerenja?

Diferencijalna privatnost na grafovima povjerenja (TGDP) koristi graf povjerenja za modeliranje odnosa, gdje čvorovi predstavljaju korisnike, a povezani čvorovi povjeruju jedni drugima. TGDP osigurava da se jamstvo privatnosti primjenjuje na poruke koje korisnik (ili njihovi povjerljivi susjedi) dijeli s onima kojima ne povjerava.

Koji algoritmi zadovoljavaju diferencijalnu privatnost na grafovima povjerenja?

Algoritmi koji zadovoljavaju diferencijalnu privatnost na grafovima povjerenja mogu biti točniji od onih koji zadovoljavaju centralnu ili lokalnu DP, a njihova greška može se kvantificirati na temelju varijance privatnih vrijednosti korisnika i veličine dominirajućeg skupa. Primjer algoritma na temelju dominirajućeg skupa pruža gornju i donju granicu greške.

Kako se diferencijalna privatnost na grafovima povjerenja može primijeniti u stvarnim scenarijima?

Diferencijalna privatnost na grafovima povjerenja može se primijeniti u različitim scenarijima, uključujući senzorske mreže, socijalne mreže i distribucijske sisteme. U senzorskoj mreži, svaki čvor predstavlja senzor koji prikuplja podatke o okolini, a dominirajući skup čvorova može biti izabran na temelju njihove pozicije i povezanosti. U socijalnoj mreži, svaki čvor predstavlja korisnika, a dominirajući skup korisnika može biti izabran na temelju njihovih veza i povjerenja. U distribucijskom sistemu, svaki čvor predstavlja poslovni proces, a dominirajući skup procesa može biti izabran na temelju njihove važnosti i interakcija.