Optimal Algorithms for Fixed-Graph Multi-Attribution Privacy

Traditional differential privacy assumes each training example affects only one user's privacy, but many real-world datasets contain examples attributed to multiple users. We study fixed-graph differential privacy, a framework for learning from such multi-attribution data where the attribution structure is public but example contents are private. We establish fundamental limits and optimal algorithms for this setting. First, we develop approximation algorithms for the NP-hard contribution bounding problem: a sampling-based LP-rounding algorithm achieving $O(|V{|}^{1/(k+1)})$-approximation and a greedy algorithm achieving $O(r)$-approximation, where $r$ is the maximum number of users per example. We prove matching hardness results showing the greedy bound is tight up to $O(\log r)$ factors. Second, we introduce a network density parameter $c$ that measures how concentrated the attribution network is, and establish information-theoretic error lower bounds scaling as $\tilde{\Omega }(c^{2}d/{\epsilon }^2)$ for learning $d$-dimensional models from $n$ examples. We provide matching upper bounds using contribution bounding combined with DP-SGD, demonstrating our algorithms are optimal. We further characterize when contribution bounding introduces selection bias and provide conditions under which bias vanishes. Finally, we extend our analysis to the i.i.d. setting where examples are sampled from a distribution, obtaining improved bounds scaling as $\tilde{O}(\sqrt{c/n})$ for hypothesis testing and providing matching algorithm for clustered networks.