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,940 | Privacy Preserving Subgraph Matching on Large Graphs in Cloud | 2016 | SIGMOD | 5.8180285e-05 |
| 5,485 | Neighborhood-Privacy Protected Shortest Distance Computing in Cloud | 2011 | SIGMOD | 5.4813218e-05 |
| 6,185 | Privacy-Aware Data Management in Information Networks | 2011 | SIGMOD | 5.1666285e-05 |
| 7,940 | DPGraph: A Benchmark Platform for Differentially Private Graph Analysis | 2021 | SIGMOD | 4.613363e-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.00018613167 |
| 686 | Finding Maximal Cliques in Massive Networks by H*-graph | 2010 | SIGMOD | 0.00018178029 |
| 803 | Towards Identity Anonymization on Graphs | 2008 | SIGMOD | 0.00016478924 |
| 1,571 | Resisting Structural Re-identification in Anonymized Social Networks | 2008 | VLDB | 0.00011318916 |
| 2,718 | Anonymizing Bipartite Graph Data using Safe Groupings | 2008 | VLDB | 8.2409647e-05 |
| 3,161 | K-Automorphism: A General Framework for Privacy Preserving Network Publication | 2009 | VLDB | 7.4613905e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 6,410 | Publishing Attributed Social Graphs with Formal Privacy Guarantees | 2016 | SIGMOD | 5.0753667e-05 |
| 3,101 | Injecting Uncertainty in Graphs for Identity Obfuscation | 2012 | VLDB | 7.5598015e-05 |
| 8,309 | Personalized Privacy Protection in Social Networks | 2011 | VLDB | 4.5435639e-05 |
| 4,940 | Privacy Preserving Subgraph Matching on Large Graphs in Cloud | 2016 | SIGMOD | 5.8180285e-05 |
| 642 | Private Analysis of Graph Structure | 2011 | VLDB | 0.00018755196 |
| 4,349 | Class-based graph anonymization for social network data | 2009 | VLDB | 6.2647606e-05 |
| 2,718 | Anonymizing Bipartite Graph Data using Safe Groupings | 2008 | VLDB | 8.2409647e-05 |
| 1,571 | Resisting Structural Re-identification in Anonymized Social Networks | 2008 | VLDB | 0.00011318916 |
| 803 | Towards Identity Anonymization on Graphs | 2008 | SIGMOD | 0.00016478924 |
| 3,161 | K-Automorphism: A General Framework for Privacy Preserving Network Publication | 2009 | VLDB | 7.4613905e-05 |