Decentralized Privacy Preservation for Critical Connections in Graphs

Li, C; Ni, W; Ding, M; Qu, Y; Chen, J; Smith, D; Zhang, W; Rakotoarivelo, T

Decentralized Privacy Preservation for Critical Connections in Graphs

Li, C

Ni, W Ding, M Qu, Y Chen, J Smith, D Zhang, W Rakotoarivelo, T

Permalink

Publisher:: Institute of Electrical and Electronics Engineers (IEEE)
Publication Type:: Journal Article
Citation:: IEEE Transactions on Knowledge and Data Engineering, 2024, PP, (99), pp. 1-14
Issue Date:: 2024-01-01

Recently Added

	Filename	Description	Size
	1732760.pdf	Published version	8.97 MB	Adobe PDF	View/Open

Copyright Clearance Process

Recently Added
In Progress
Open Access

This item is new to OPUS and is not currently available.

Full metadata record

Field	Value	Language
dc.contributor.author	Li, C https://orcid.org/0000-0002-6164-2643
dc.contributor.author	Ni, W
dc.contributor.author	Ding, M
dc.contributor.author	Qu, Y
dc.contributor.author	Chen, J
dc.contributor.author	Smith, D
dc.contributor.author	Zhang, W
dc.contributor.author	Rakotoarivelo, T
dc.date.accessioned	2024-08-07T05:47:45Z
dc.date.available	2024-08-07T05:47:45Z
dc.date.issued	2024-01-01
dc.identifier.citation	IEEE Transactions on Knowledge and Data Engineering, 2024, PP, (99), pp. 1-14
dc.identifier.issn	1041-4347
dc.identifier.issn	1558-2191
dc.identifier.uri	http://hdl.handle.net/10453/180354
dc.description.abstract	Many real-world interconnections among entities can be characterized as graphs. Collecting local graph information with balanced privacy and data utility has garnered notable interest recently. This paper delves into the problem of identifying and protecting critical information of entity connections for individual participants in a graph based on cohesive subgraph searches. This problem has not been addressed in the literature. To address the problem, we propose to extract the critical connections of a queried vertex using a fortress-like cohesive subgraph model known as <inline-formula><tex-math notation="LaTeX">$p$</tex-math></inline-formula>-cohesion. A user's connections within a fortress are obfuscated when being released, to protect critical information about the user. Novel merit and penalty score functions are designed to measure each participant's critical connections in the minimal <inline-formula><tex-math notation="LaTeX">$p$</tex-math></inline-formula>-cohesion., facilitating effective identification of the connections. We further propose to preserve the privacy of a vertex enquired by only protecting its critical connections when responding to queries raised by data collectors. We prove that, under the decentralized differential privacy (DDP) mechanism, one's response satisfies <inline-formula><tex-math notation="LaTeX">$(\varepsilon , \delta )$</tex-math></inline-formula>-DDP when its critical connections are protected while the rest remains unperturbed. The effectiveness of our proposed method is demonstrated through extensive experiments on real-life graph datasets.
dc.language	en
dc.publisher	Institute of Electrical and Electronics Engineers (IEEE)
dc.relation.ispartof	IEEE Transactions on Knowledge and Data Engineering
dc.relation.isbasedon	10.1109/TKDE.2024.3406641
dc.rights	info:eu-repo/semantics/restrictedAccess
dc.subject	08 Information and Computing Sciences
dc.subject.classification	Information Systems
dc.subject.classification	46 Information and computing sciences
dc.title	Decentralized Privacy Preservation for Critical Connections in Graphs
dc.type	Journal Article
utslib.citation.volume	PP
utslib.for	08 Information and Computing Sciences
pubs.organisational-group	University of Technology Sydney
pubs.organisational-group	University of Technology Sydney/Faculty of Engineering and Information Technology
utslib.copyright.status	recently_added	*
dc.date.updated	2024-08-07T05:47:33Z
pubs.issue	99
pubs.publication-status	Published
pubs.volume	PP
utslib.citation.issue	99

Abstract:

Many real-world interconnections among entities can be characterized as graphs. Collecting local graph information with balanced privacy and data utility has garnered notable interest recently. This paper delves into the problem of identifying and protecting critical information of entity connections for individual participants in a graph based on cohesive subgraph searches. This problem has not been addressed in the literature. To address the problem, we propose to extract the critical connections of a queried vertex using a fortress-like cohesive subgraph model known as

$p$

-cohesion. A user's connections within a fortress are obfuscated when being released, to protect critical information about the user. Novel merit and penalty score functions are designed to measure each participant's critical connections in the minimal

$p$

-cohesion., facilitating effective identification of the connections. We further propose to preserve the privacy of a vertex enquired by only protecting its critical connections when responding to queries raised by data collectors. We prove that, under the decentralized differential privacy (DDP) mechanism, one's response satisfies

$(\varepsilon , \delta )$

-DDP when its critical connections are protected while the rest remains unperturbed. The effectiveness of our proposed method is demonstrated through extensive experiments on real-life graph datasets.

Please use this identifier to cite or link to this item:

http://hdl.handle.net/10453/180354