Дифференциально частный анализ графиков

Дифференциально частный анализ графиков ^[1] изучает алгоритмы вычисления точной статистики графов при сохранении дифференциальной конфиденциальности . Такие алгоритмы используются для данных, представленных в виде графа, где узлы соответствуют отдельным лицам, а ребра соответствуют отношениям между ними. Например, края могут соответствовать дружбе, сексуальным отношениям или моделям общения. Сторона, которая собрала конфиденциальные данные графа, может обработать их с использованием дифференциально-частного алгоритма и опубликовать выходные данные алгоритма. Целью дифференциально-частного анализа графов является разработка алгоритмов, которые вычисляют точную глобальную информацию о графах, сохраняя при этом конфиденциальность лиц, чьи данные хранятся в графе.

Варианты

Дифференциальная конфиденциальность накладывает ограничения на алгоритм. Интуитивно понятно, что для этого требуется, чтобы алгоритм имел примерно одинаковое распределение выходных данных на соседних входах. Если входные данные представляют собой граф, существуют два естественных понятия соседних входных данных: соседи по ребрам и соседи по узлам, которые дают два естественных варианта дифференциальной конфиденциальности для данных графа.

Пусть ε — положительное действительное число и ${\mathcal {A}}$ быть рандомизированным алгоритмом , который принимает граф в качестве входных данных и возвращает выходные данные из набора ${\mathcal {O}}$ .Алгоритм ${\mathcal {A}}$ является $\epsilon$ - дифференциально-частное if для всех соседних графов $G_{1}$ и $G_{2}$ и все подмножества $S$ из ${\mathcal {O}}$ ,

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

где вероятность берется за случайность, используемую алгоритмом.

Дифференциальная конфиденциальность по краям

Два графа являются соседями по ребру, если они различаются по одному ребру. Алгоритм $\epsilon$ -edge-дифференциально частный, если в приведенном выше определении используется понятие краевых соседей. Интуитивно понятно, что дифференциально-частный алгоритм по ребрам имеет одинаковые выходные распределения на любой паре графов, которые отличаются одним ребром, тем самым защищая изменения в ребрах графа.

Дифференциальная конфиденциальность узлов

Два графа являются соседями узла, если один можно получить из другого, удалив узел и прилегающие к нему ребра. Алгоритм $\epsilon$ -node-дифференциально частный, если в приведенном выше определении используется понятие соседей узла. Интуитивно понятно, что алгоритм дифференциально-приватного узла имеет аналогичные распределения выходных данных на любой паре графов, которые различаются узлами и смежными с ним ребрами, тем самым защищая информацию, относящуюся к каждому человеку. Дифференциальная конфиденциальность узлов обеспечивает более надежную защиту конфиденциальности, чем дифференциальная конфиденциальность на границах.

История исследований

Первый дифференциально-частный алгоритм по краям был разработан Ниссимом, Расходниковой и Смитом. ^[2] Различие между дифференциальной конфиденциальностью границ и узлов впервые обсуждалось Хэем, Миклау и Йенсеном. ^[3] Однако прошло несколько лет, прежде чем в Blocki et al. были опубликованы первые дифференциально-частные алгоритмы узла. ^[4] Касивисванатан и др., ^[5] и Чен и Чжоу. ^[6] Во всех трех статьях алгоритмы предназначены для выдачи одной статистики, такой как количество треугольников или количество других подграфов. Расходникова и Смит предложили первый узел дифференциально-частного алгоритма освобождения вектора, в частности, счетчика степеней и распределения степеней. ^[7]

Ссылки

^ Софья Расходникова ; Адам Смит (2015). «Дифференциально частный анализ графов». Као М.И. (Ред.) Энциклопедия алгоритмов. Шпрингер, Берлин, Гейдельберг . дои : 10.1007/978-3-642-27848-8_549-1 .
^ Ниссим, Кобби; Расходникова, Софья ; Смит, Адам (2007). «Плавная чувствительность и выборка при анализе частных данных». Материалы тридцать девятого ежегодного симпозиума ACM по теории вычислений . Нью-Йорк, Нью-Йорк, США: ACM Press. стр. 75–84. дои : 10.1145/1250790.1250803 . ISBN 9781595936318 . S2CID 5642529 .
^ Привет, Майкл; Ли, Чао; Миклау, Жером; Дженсен, Дэвид (2009). «Точная оценка степени распределения частных сетей». 2009 Девятая международная конференция IEEE по интеллектуальному анализу данных . IEEE. стр. 169–178. дои : 10.1109/icdm.2009.11 . ISBN 9781424452422 . S2CID 2572996 .
^ Блоки, Иеремия; Блюм, Аврим; Датта, Анупам; Шеффет, Ор (2012). «Преобразование Джонсона-Линденштрауса само по себе сохраняет дифференциальную конфиденциальность». 2012 53-й ежегодный симпозиум IEEE по основам информатики . стр. 410–419. arXiv : 1204.2136 . Бибкод : 2012arXiv1204.2136B . дои : 10.1109/focs.2012.67 . ISBN 978-0-7695-4874-6 . S2CID 349368 .
^ Касивишванатан, Шива Прасад; Ниссим, Кобби; Расходникова, Софья ; Смит, Адам (2013), «Анализ графов с дифференциальной конфиденциальностью узлов», Теория криптографии , Springer Berlin Heidelberg, стр. 457–476, doi : 10.1007/978-3-642-36594-2_26 , ISBN 9783642365935
^ Чен, Шиси; Чжоу, Шуйгэн (2013). «Рекурсивный механизм». Материалы Международной конференции ACM SIGMOD по управлению данными 2013 г. Нью-Йорк, Нью-Йорк, США: ACM Press. стр. 653–664. дои : 10.1145/2463676.2465304 . ISBN 9781450320375 . S2CID 16257197 .
^ Расходникова, Софья ; Смит, Адам (2016). «Липшицевы расширения для статистики частных графов узлов и обобщенного экспоненциального механизма». 57-й ежегодный симпозиум IEEE по основам информатики (FOCS) , 2016 г. IEEE. стр. 495–504. дои : 10.1109/focs.2016.60 . ISBN 9781509039333 . S2CID 7310416 .

[1] Софья Расходникова ; Адам Смит (2015). «Дифференциально частный анализ графов». Као М.И. (Ред.) Энциклопедия алгоритмов. Шпрингер, Берлин, Гейдельберг . дои : 10.1007/978-3-642-27848-8_549-1 .

[2] Ниссим, Кобби; Расходникова, Софья ; Смит, Адам (2007). «Плавная чувствительность и выборка при анализе частных данных». Материалы тридцать девятого ежегодного симпозиума ACM по теории вычислений . Нью-Йорк, Нью-Йорк, США: ACM Press. стр. 75–84. дои : 10.1145/1250790.1250803 . ISBN 9781595936318 . S2CID 5642529 .

[3] Привет, Майкл; Ли, Чао; Миклау, Жером; Дженсен, Дэвид (2009). «Точная оценка степени распределения частных сетей». 2009 Девятая международная конференция IEEE по интеллектуальному анализу данных . IEEE. стр. 169–178. дои : 10.1109/icdm.2009.11 . ISBN 9781424452422 . S2CID 2572996 .

[4] Блоки, Иеремия; Блюм, Аврим; Датта, Анупам; Шеффет, Ор (2012). «Преобразование Джонсона-Линденштрауса само по себе сохраняет дифференциальную конфиденциальность». 2012 53-й ежегодный симпозиум IEEE по основам информатики . стр. 410–419. arXiv : 1204.2136 . Бибкод : 2012arXiv1204.2136B . дои : 10.1109/focs.2012.67 . ISBN 978-0-7695-4874-6 . S2CID 349368 .

[5] Касивишванатан, Шива Прасад; Ниссим, Кобби; Расходникова, Софья ; Смит, Адам (2013), «Анализ графов с дифференциальной конфиденциальностью узлов», Теория криптографии , Springer Berlin Heidelberg, стр. 457–476, doi : 10.1007/978-3-642-36594-2_26 , ISBN 9783642365935

[6] Чен, Шиси; Чжоу, Шуйгэн (2013). «Рекурсивный механизм». Материалы Международной конференции ACM SIGMOD по управлению данными 2013 г. Нью-Йорк, Нью-Йорк, США: ACM Press. стр. 653–664. дои : 10.1145/2463676.2465304 . ISBN 9781450320375 . S2CID 16257197 .

[7] Расходникова, Софья ; Смит, Адам (2016). «Липшицевы расширения для статистики частных графов узлов и обобщенного экспоненциального механизма». 57-й ежегодный симпозиум IEEE по основам информатики (FOCS) , 2016 г. IEEE. стр. 495–504. дои : 10.1109/focs.2016.60 . ISBN 9781509039333 . S2CID 7310416 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]