Differentiell privat analys av grafer

Differentiell privat analys av grafer studerar algoritmer för att beräkna korrekt grafstatistik samtidigt som differentiell integritet bevaras . Sådana algoritmer används för data som representeras i form av en graf där noder motsvarar individer och kanter motsvarar relationer mellan dem. Kanter kan till exempel motsvara vänskap, sexuella relationer eller kommunikationsmönster. En part som samlat in känslig grafdata kan bearbeta den med en differentiellt privat algoritm och publicera utdata från algoritmen. Målet med differentiellt privat analys av grafer är att designa algoritmer som beräknar korrekt global information om grafer samtidigt som privatlivet bevaras för individer vars data lagras i grafen.

Varianter

Differentiell integritet innebär en begränsning av algoritmen. Intuitivt kräver det att algoritmen har ungefär samma utdatafördelning på närliggande ingångar. Om ingången är en graf, finns det två naturliga föreställningar om angränsande ingångar, kantgrannar och nodgrannar, vilket ger två naturliga varianter av differentiell integritet för grafdata.

Låt ε vara ett positivt reellt tal och ${\mathcal {A}}$ vara en randomiserad algoritm som tar en graf som indata och returnerar en utdata från en mängd ${\mathcal {O}}$ . Algoritmen ${\mathcal {A}}$ är $\epsilon$ -differentiellt privat om, för alla angränsande grafer $G_{1}$ och $G_{2 }$ och alla delmängder $S$ av ${\mathcal {O}}$ ,

$\Pr[{\mathcal {A}}(G_{1})\in S]\leq e^{\epsilon }\times \Pr[{\mathcal {A}}(G_{2})\in S],$

där sannolikheten tas över den slumpmässighet som används av algoritmen.

Edge differentiell integritet

Två grafer är kantgrannar om de skiljer sig åt i en kant. En algoritm är $\epsilon$ -edge-differentiellt privat om, i definitionen ovan, begreppet kantgrannar används. Intuitivt har en kant differentiellt privat algoritm liknande utmatningsfördelningar på alla par av grafer som skiljer sig åt i en kant, vilket skyddar förändringar av grafkanter.

Nod differentiell integritet

Två grafer är nodgrannar om den ena kan erhållas från den andra genom att ta bort en nod och dess intilliggande kanter. En algoritm är $\epsilon$ -nod-differentiellt privat om, i definitionen ovan, begreppet nodgrannar används. Intuitivt har en nod differentiellt privat algoritm liknande utmatningsfördelningar på valfritt par av grafer som skiljer sig åt i en nod och kanter intill den, vilket skyddar information som hänför sig till varje individ. Nod differentiell integritet ger ett starkare integritetsskydd än edge differentiell integritet.

Forskningshistoria

Den första edge differentiellt privata algoritmen designades av Nissim, Raskhodnikova och Smith. Skillnaden mellan kant- och noddifferentiell integritet diskuterades först av Hay, Miklau och Jensen. Det tog dock flera år innan första nod-differentiellt privata algoritmer publicerades i Blocki et al., Kasiviswanathan et al., och Chen och Zhou. I alla tre tidningarna är algoritmerna för att släppa en enda statistik, som en triangelräkning eller antal andra subgrafer. Raskhodnikova och Smith gav den första noden differentiellt privat algoritm för att frigöra en vektor, närmare bestämt gradräkningen och gradfördelningen.