Towards identity disclosure control in private hypergraph publishing

Yidong Li, Hong Shen

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review


Identity disclosure control (IDC) on complex data has attracted increasing interest in security and database communities. Most existing work focuses on preventing identity disclosure in graphs that describes pairwise relations between data entities. Many data analysis applications need information about multi-relations among entities, which can be well represented with hypergraphs. However, the IDC problem has been little studied in publishing hypergraphs due to the diversity of hypergraph information which may expose to many types of background knowledge attacks. In this paper, we introduce a novel attack model with the properties of hyperedge rank as background knowledge, and formalize the rank-based hypergraph anonymization (RHA) problem. We propose an algorithm running in near-quadratic time on hypergraph size for rank anonymization which we show to be NP-hard, and in the meanwhile, maintaining data utility for community detection. We also show how to construct the hypergraph under the anonymized properties to protect a hypergraph from rank-based attacks. The performances of the methods have been validated by extensive experiments on real-world datasets. Our rank-based attack model and algorithms for rank anonymization and hypergraph construction are, to our best knowledge, the first systematic study for private hypergraph publishing.

Original languageEnglish
Title of host publicationAdvances in Knowledge Discovery and Data Mining - 16th Pacific-Asia Conference, PAKDD 2012, Proceedings
Number of pages12
EditionPART 2
Publication statusPublished - 2012
Externally publishedYes
Event16th Pacific-Asia Conference on Advances in Knowledge Discovery and Data Mining, PAKDD 2012 - Kuala Lumpur, Malaysia
Duration: 29 May 20121 Jun 2012

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
NumberPART 2
Volume7301 LNAI
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference16th Pacific-Asia Conference on Advances in Knowledge Discovery and Data Mining, PAKDD 2012
CityKuala Lumpur


  • Anonymization
  • Community detection
  • Identity disclosure control
  • Private hypergraph publishing


Dive into the research topics of 'Towards identity disclosure control in private hypergraph publishing'. Together they form a unique fingerprint.

Cite this