Communication-Efficient Publication of Sparse Vectors under Differential Privacy via Poisson Private Representation
Open Access
- 4 June 2026
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 1786-1798
Abstract
We present a method for privately publishing sparse vectors with communication and computation costs that scale linearly with the number of nonzero elements. The Poisson Private Representation (PPR) framework was introduced to compress any differentially private mechanism to achieve a communication cost of O(ϵ), where ϵ is the privacy budget. However, PPR and its variant, Chunk PPR, are not well suited for publishing sparse vectors under metric differential privacy: PPR incurs exponential computation cost, while Chunk PPR requires both execution and communication costs linear in the vector dimension. As a result, their guarantees are no stronger than those of non-compressed randomized response, which for a matrix with N users, n columns, and m nonzero elements, requires Ω(nN) communication—rendering it impractical for large-scale data. Our PPR-based algorithm overcomes these limitations, reducing communication to O (ϵm). Remarkably, this is even lower than the non-private baseline, which needs Ω(m log n) bits. Furthermore, as the privacy budget decreases, communication cost is further reduced, enabling stronger privacy with greater efficiency We provide theoretical guarantees showing that our method yields results equivalent to randomized response, and experimental evaluations confirm its advantages in accuracy, communication efficiency, and computational complexity. Finally, we demonstrate its applicability across domains such as social-network adjacency matrices, user-item interaction matrices in recommender systems, and single-nucleotide polymorphism (SNP) profiles in genomic data.Keywords
Funding Information
- KAKENHI (20H05965)
- JST SPRING (JPMJSP2108)
- Villum Foundation (54451)
- JST NEXUS (Y2024L0906031)
- KAKENHI (JP25K00369)
- KAKENHI (20H05967)
- KAKENHI (21H05052)
- KAKENHI (23H03345)
This publication has 19 references indexed in Scilit:
- PGB: Benchmarking Differentially Private Synthetic Graph Generation Algorithms2025
- Locally Differentially Private Sparse Vector Aggregation2022
- Latest trends of security and privacy in recommender systems: A comprehensive review and future perspectivesComputers & Security, 2022
- Strong Functional Representation Lemma and Applications to Coding TheoremsIEEE Transactions on Information Theory, 2018
- Parallel random numbers2011
- What Can We Learn Privately?SIAM Journal on Computing, 2011
- Signed networks in social media2010
- Privacy integrated queries2009
- Probability Inequalities for Sums of Bounded Random VariablesJournal of the American Statistical Association, 1963
- A Method for the Construction of Minimum-Redundancy CodesProceedings of the IRE, 1952