K-Isomorphism: Privacy Preserving Network Publication against Structural Attacks
Summary: Proposes k-isomorphism as the necessary-and-sufficient privacy model against structural attacks on graphs (NodeInfo/LinkInfo). NP-hard; develops efficiency techniques and a compound vertex ID for multi-release privacy; validated on HEP-TH, EUemail, LiveJournal, showing symmetry aids anonymization while preserving utility. (summarized by gpt-5-nano on Feb 09 2026)
Incoming Non-self Citations Over Time
Authors
- 1. James Cheng
- 2. Ada Wai-Chee Fu
- 3. Jia Liu
Incoming Citations (Sorted by Pagerank)
Showing 4 of 4 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 4,942 | Privacy Preserving Subgraph Matching on Large Graphs in Cloud | 2016 | SIGMOD | 5.8124358e-05 |
| 5,494 | Neighborhood-Privacy Protected Shortest Distance Computing in Cloud | 2011 | SIGMOD | 5.4770961e-05 |
| 6,190 | Privacy-Aware Data Management in Information Networks | 2011 | SIGMOD | 5.1604866e-05 |
| 7,943 | DPGraph: A Benchmark Platform for Differentially Private Graph Analysis | 2021 | SIGMOD | 4.6089395e-05 |
Previous
Page 1 / 1
Next
Outgoing Citations (Sorted by Pagerank)
Showing 6 of 6 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
| Rank | Cited Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 654 | Anatomy: Simple and Effective Privacy Preservation | 2006 | VLDB | 0.00018594644 |
| 682 | Finding Maximal Cliques in Massive Networks by H*-graph | 2010 | SIGMOD | 0.0001816451 |
| 800 | Towards Identity Anonymization on Graphs | 2008 | SIGMOD | 0.00016463554 |
| 1,571 | Resisting Structural Re-identification in Anonymized Social Networks | 2008 | VLDB | 0.000113084 |
| 2,721 | Anonymizing Bipartite Graph Data using Safe Groupings | 2008 | VLDB | 8.2331032e-05 |
| 3,169 | K-Automorphism: A General Framework for Privacy Preserving Network Publication | 2009 | VLDB | 7.4545379e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 6,406 | Publishing Attributed Social Graphs with Formal Privacy Guarantees | 2016 | SIGMOD | 5.0704962e-05 |
| 3,106 | Injecting Uncertainty in Graphs for Identity Obfuscation | 2012 | VLDB | 7.5550946e-05 |
| 8,303 | Personalized Privacy Protection in Social Networks | 2011 | VLDB | 4.5392079e-05 |
| 4,942 | Privacy Preserving Subgraph Matching on Large Graphs in Cloud | 2016 | SIGMOD | 5.8124358e-05 |
| 642 | Private Analysis of Graph Structure | 2011 | VLDB | 0.00018757732 |
| 4,346 | Class-based graph anonymization for social network data | 2009 | VLDB | 6.2588738e-05 |
| 2,721 | Anonymizing Bipartite Graph Data using Safe Groupings | 2008 | VLDB | 8.2331032e-05 |
| 1,571 | Resisting Structural Re-identification in Anonymized Social Networks | 2008 | VLDB | 0.000113084 |
| 800 | Towards Identity Anonymization on Graphs | 2008 | SIGMOD | 0.00016463554 |
| 3,169 | K-Automorphism: A General Framework for Privacy Preserving Network Publication | 2009 | VLDB | 7.4545379e-05 |