# Recursive Mechanism: Towards Node Differential Privacy and Unrestricted Joins [Full Version, Draft 0.1]

arXiv: https://arxiv.org/abs/1304.4795 · HTML: https://mlsanity.com/paper/1304.4795/

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Apr 2013.

## Built on by (most cited first, 13 of 13)

- [LPGNet: Link Private Graph Networks for Node Classification](https://mlsanity.com/paper/2205.03105/) (2022)
- [SoK: Differential Privacy on Graph-Structured Data](https://mlsanity.com/paper/2203.09205/) (2022)
- [On User-Level Private Convex Optimization](https://mlsanity.com/paper/2305.04912/) (2023)
- [Differentially Private Densest Subgraph Detection](https://mlsanity.com/paper/2105.13287/) (2021)
- [Instance-Optimal Differentially Private Estimation](https://mlsanity.com/paper/2210.15819/) (2022)
- [Differentially Private Synthetic Graphs Preserving Triangle-Motif Cuts](https://mlsanity.com/paper/2507.14835/) (2025)
- [On Privacy and Confidentiality of Communications in Organizational Graphs](https://mlsanity.com/paper/2105.13418/) (2021)
- [Instance-Specific Asymmetric Sensitivity in Differential Privacy](https://mlsanity.com/paper/2311.14681/) (2023)
- [It's My Data Too: Private ML for Datasets with Multi-User Training Examples](https://mlsanity.com/paper/2503.03622/) (2025)
- [Differentially Private Modeling of Disease Transmission within Human Contact Networks](https://mlsanity.com/paper/2604.07493/) (2026)
- [Differentially Private Motif-Preserving Multi-modal Hashing](https://mlsanity.com/paper/2605.15460/) (2026)
- [Robust Statistical Estimators with Bounded Empirical Sensitivity](https://mlsanity.com/paper/2605.21860/) (2026)
- [Differentially Private Range Subgraph Counting](https://mlsanity.com/paper/2606.08179/) (2026)

## Abstract (arXiv)

Existing studies on differential privacy mainly consider aggregation on data sets where each entry corresponds to a particular participant to be protected. In many situations, a user may pose a relational algebra query on a sensitive database, and desires differentially private aggregation on the result of the query. However, no known work is capable to release this kind of aggregation when the query contains unrestricted join operations. This severely limits the applications of existing differential privacy techniques because many data analysis tasks require unrestricted joins. One example is subgraph counting on a graph. Existing methods for differentially private subgraph counting address only edge differential privacy and are subject to very simple subgraphs. Before this work, whether any nontrivial graph statistics can be released with reasonable accuracy under node differential privacy is still an open problem. In this paper, we propose a novel differentially private mechanism to release an approximation to a linear statistic of the result of some positive relational algebra calculation over a sensitive database. Unrestricted joins are supported in our mechanism. The error bound of the approximate answer is roughly proportional to the empirical sensitivity of the query --- a new notion that measures the maximum possible change to the query answer when a participant withdraws its data from the sensitive database. For subgraph counting, our mechanism provides the first solution to achieve node differential privacy, for any kind of subgraphs.