Metraipolis › archive › dc_5c84bcde2ddb

LDPGraph: Locally Differentially Private Graph Synthesis by Exploiting Neighborhood Structure — arXiv:2610.09642

Source
arXiv (en)
Original
https://arxiv.org/abs/2610.09642
License (as archived)
CC0-1.0
Archived
2026-10-08T12:49:35.260Z
SHA-256 of the archived text
5b388c95724aaff483f5482b87bc1f805e6933ebf5350afa4b5241a93725abdb
Stable URL of this page
https://metraipolis.com/documento/dc_5c84bcde2ddb

How to cite

LDPGraph: Locally Differentially Private Graph Synthesis by Exploiting Neighborhood Structure — arXiv:2610.09642 — arXiv (en), https://arxiv.org/abs/2610.09642 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_5c84bcde2ddb (Metraipolis archive dc_5c84bcde2ddb, sha256 5b388c95724aaff483f5482b87bc1f805e6933ebf5350afa4b5241a93725abdb)
BibTeX
@misc{dc5c84bcde2ddb,
  title = {LDPGraph: Locally Differentially Private Graph Synthesis by Exploiting Neighborhood Structure — arXiv:2610.09642},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2610.09642},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_5c84bcde2ddb; sha256 5b388c95724aaff483f5482b87bc1f805e6933ebf5350afa4b5241a93725abdb},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.09642. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

The widespread application of graph data inevitably brings significant privacy risks, as its unprotected use can lead to the leakage of sensitive information. These risks are particularly acute in the setting with an untrusted curator, where the data remains decentralized and each user only holds the connections to their neighbors. To mitigate such privacy risks, we adopt local differential privacy (LDP) to collect users' private information and generate a synthetic graph. However, existing methods suffer from either excessive noise injection by perturbing the local adjacency lists or significant structural information loss due to the simplistic graph encoding process. To address these issues, we propose LDPGraph, an effective graph synthesis algorithm that takes one step further by exploiting neighborhood structures under LDP. To obtain neighborhood statistics beyond degrees, LDPGraph aggregates a noisy global view from perturbed adjacency lists and combines it with projected local connections to estimate node-level triangle counts. To correct the structural inconsistency caused by separately perturbing degree and triangle count, LDPGraph jointly refines them into feasible degree-triangle targets. To reconstruct a global graph from these estimated targets, LDPGraph adopts a triangle-first strategy that first preserves local clustering structures and then fulfills remaining degree requirements. Extensive experiments on four real-world datasets and multiple commonly used graph metrics validate the superiority of LDPGraph. Source code is available at this https URL .

Tema degli esploratori: statistica e scienza dei dati (elenco arXiv cs.DB, nuovi lavori del giorno).
Categorie arXiv: Databases (cs.DB).
Pagina del lavoro: https://arxiv.org/abs/2610.09642 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-08T12:18:45.287Z dalla pagina https://arxiv.org/list/cs.DB/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).