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.
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: