Newest papers

Practical Auditing of Differentially Private Graph Release Mechanisms: Methodology, Toolkit, and Case Study

Nicholas D'Silva, Surya Nepal, Salil S. Kanhere · 2026 · arXiv (Cornell University)

DOI: 10.48550/arxiv.2610.31294 · cited by 0 works (OpenAlex) · open-access PDF

Russian

Дифференциальная конфиденциальность (DP) стала выдающимся подходом к защите графических выпусков данных, однако эмпирические методологии аудита были в значительной степени разработаны для табличных наборов данных и трубопроводов машинного обучения, а не графически структурированных выходов. Мы представляем методологию эмпирического аудита механизмов выпуска графиков DP, определяя две графически специфические проблемы дизайна аудита: строительство каналов и статистический отбор свидетелей. Мы объединяем эти компоненты с установленной статистически сертифицированной процедурой тестирования и внедряем полученную методологию в качестве инструментария Python с открытым исходным кодом. Чтобы продемонстрировать подход, мы проверяем опубликованный state-of-the-art механизм выпуска графиков Node-

Machine translation (Meta M2M100); the English original follows.

Abstract

Differential Privacy (DP) has become a prominent approach for protecting graph data releases, yet empirical auditing methodologies have largely been developed for tabular datasets and machine learning pipelines rather than graph-structured outputs. We present a methodology for empirically auditing DP graph release mechanisms, identifying two graph-specific audit design problems: canary construction and witness statistic selection. We combine these components with an established statistically certified testing procedure and implement the resulting methodology as an open-source Python toolkit. To demonstrate the approach, we audit a published state-of-the-art Node-DP graph release mechanism. Across a series of synthetic and real-world canary pairs, we obtain certified lower bounds on the privacy parameter {\varepsilon} that exceed the claimed value, yielding counterexamples sufficient to falsify the claimed guarantee for the audited implementation. The violations persist under progressively stronger restrictions on the input domain, including non-empty and connected graphs. We also show that witness selection can materially affect whether a violation is detected, highlighting the importance of evaluating a diverse battery of statistics when auditing DP graph release mechanisms.

Read in: English · Spanish · Chinese · Hindi · Arabic · Portuguese · French · German · Japanese · Russian · Korean · Indonesian · Vietnamese

Topics: Audit, Computer science, Certification, Witness, Graph, Counterexample

Sources: OpenAlex (CC0), arXiv, Crossref. Agent Exchange