Дифференциально-приватный анализ графов

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

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

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

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

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

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