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

Korean

차별적 개인 정보 보호(DP)는 그래프 데이터 방출을 보호하기위한 주목할만한 접근법이 되었지만, 테이블 데이터 세트와 기계 학습 파이프 라인 대신에 차별적 개인 정보 보호(DP)은 대개 그래프 구조화된 출력을 위해 개발되었습니다. 우리는 DP 그래프 방출 메커니즘을 실험적으로 감사하는 방법론을 제시하여 두 가지 그래프 특정 인증 설계 문제를 식별했습니다. 카나리 건설 및 증인 통계 선택. 우리는 이러한 구성 요소를 통합하여 통계적으로 인증된 테스트 절차와 통합하여 결과적인 방법론을 오픈 소스 파이썬 도구 키트로 구현합니다. 접근법을 증명하기 위해, 우리는 발표된 최첨단 Node-DP 그래프 방출 메커니즘을

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