BetweenCut: Private Heavy-Node Classification with Doubly Logarithmic Error in Tree Height

Abstract

Finding heavy nodes in a tree---those whose counts exceed a given threshold---is a building block for analysis and learning over structured data. Achieving record-level differential privacy (DP) without sacrificing accuracy is challenging because each record contributes to counts along an entire root-to-leaf path, allowing privacy costs to accumulate across levels. Existing methods account for the multiple threshold comparisons for each record incur additive error margins of ${\Omega }_{\epsilon ,\delta }(\log h)$ or ${\Omega }_{\epsilon ,\delta }(\sqrt{\log h})$ for tree height $h$. We introduce \textsc{BetweenCut}, an $(\epsilon ,\delta )$-DP algorithm with an additive error margin of $O_{\epsilon ,\delta }(\log \log h)$, improving the existing bounds for deep trees. This error holds simultaneously for all nodes and is independent of the input database size.