---
_id: '12012'
abstract:
- lang: eng
  text: This paper is eligible for the Jack Keil Wolf ISIT Student Paper Award. We
    generalize a previous framework for designing utility-optimal differentially private
    (DP) mechanisms via graphs, where datasets are vertices in the graph and edges
    represent dataset neighborhood. The boundary set contains datasets where an individual’s
    response changes the binary-valued query compared to its neighbors. Previous work
    was limited to the homogeneous case where the privacy parameter ε across all datasets
    was the same and the mechanism at boundary datasets was identical. In our work,
    the mechanism can take different distributions at the boundary and the privacy
    parameter ε is a function of neighboring datasets, which recovers an earlier definition
    of personalized DP as special case. The problem is how to extend the mechanism,
    which is only defined at the boundary set, to other datasets in the graph in a
    computationally efficient and utility optimal manner. Using the concept of strongest
    induced DP condition we solve this problem efficiently in polynomial time (in
    the size of the graph).
article_processing_charge: No
arxiv: 1
author:
- first_name: Sahel
  full_name: Torkamani, Sahel
  id: 0503e7f8-2d05-11ed-aa17-db0640c720fc
  last_name: Torkamani
- first_name: Javad B.
  full_name: Ebrahimi, Javad B.
  last_name: Ebrahimi
- first_name: Parastoo
  full_name: Sadeghi, Parastoo
  last_name: Sadeghi
- first_name: Rafael G.L.
  full_name: D'Oliveira, Rafael G.L.
  last_name: D'Oliveira
- first_name: Muriel
  full_name: Médard, Muriel
  last_name: Médard
citation:
  ama: 'Torkamani S, Ebrahimi JB, Sadeghi P, D’Oliveira RGL, Médard M. Heterogeneous
    differential privacy via graphs. In: <i>2022 IEEE International Symposium on Information
    Theory</i>. Vol 2022. IEEE; 2022:1623-1628. doi:<a href="https://doi.org/10.1109/ISIT50566.2022.9834711">10.1109/ISIT50566.2022.9834711</a>'
  apa: 'Torkamani, S., Ebrahimi, J. B., Sadeghi, P., D’Oliveira, R. G. L., &#38; Médard,
    M. (2022). Heterogeneous differential privacy via graphs. In <i>2022 IEEE International
    Symposium on Information Theory</i> (Vol. 2022, pp. 1623–1628). Espoo, Finland:
    IEEE. <a href="https://doi.org/10.1109/ISIT50566.2022.9834711">https://doi.org/10.1109/ISIT50566.2022.9834711</a>'
  chicago: Torkamani, Sahel, Javad B. Ebrahimi, Parastoo Sadeghi, Rafael G.L. D’Oliveira,
    and Muriel Médard. “Heterogeneous Differential Privacy via Graphs.” In <i>2022
    IEEE International Symposium on Information Theory</i>, 2022:1623–28. IEEE, 2022.
    <a href="https://doi.org/10.1109/ISIT50566.2022.9834711">https://doi.org/10.1109/ISIT50566.2022.9834711</a>.
  ieee: S. Torkamani, J. B. Ebrahimi, P. Sadeghi, R. G. L. D’Oliveira, and M. Médard,
    “Heterogeneous differential privacy via graphs,” in <i>2022 IEEE International
    Symposium on Information Theory</i>, Espoo, Finland, 2022, vol. 2022, pp. 1623–1628.
  ista: 'Torkamani S, Ebrahimi JB, Sadeghi P, D’Oliveira RGL, Médard M. 2022. Heterogeneous
    differential privacy via graphs. 2022 IEEE International Symposium on Information
    Theory. ISIT: International Symposium on Information Theory vol. 2022, 1623–1628.'
  mla: Torkamani, Sahel, et al. “Heterogeneous Differential Privacy via Graphs.” <i>2022
    IEEE International Symposium on Information Theory</i>, vol. 2022, IEEE, 2022,
    pp. 1623–28, doi:<a href="https://doi.org/10.1109/ISIT50566.2022.9834711">10.1109/ISIT50566.2022.9834711</a>.
  short: S. Torkamani, J.B. Ebrahimi, P. Sadeghi, R.G.L. D’Oliveira, M. Médard, in:,
    2022 IEEE International Symposium on Information Theory, IEEE, 2022, pp. 1623–1628.
conference:
  end_date: 2022-07-01
  location: Espoo, Finland
  name: 'ISIT: International Symposium on Information Theory'
  start_date: 2022-06-26
date_created: 2022-09-04T22:02:04Z
date_published: 2022-08-03T00:00:00Z
date_updated: 2025-09-10T09:42:41Z
day: '03'
department:
- _id: MaMo
doi: 10.1109/ISIT50566.2022.9834711
external_id:
  arxiv:
  - '2203.15429'
  isi:
  - '001254261901131'
intvolume: '      2022'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://doi.org/10.48550/arXiv.2203.15429
month: '08'
oa: 1
oa_version: Preprint
page: 1623-1628
publication: 2022 IEEE International Symposium on Information Theory
publication_identifier:
  isbn:
  - '9781665421591'
  issn:
  - 2157-8095
publication_status: published
publisher: IEEE
quality_controlled: '1'
scopus_import: '1'
status: public
title: Heterogeneous differential privacy via graphs
type: conference
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 2022
year: '2022'
...