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)

Paper ID: h3c149c6b9b4dc6c1
Venue: SIGMOD
Year: 2010
Pagerank: 6.1772055e-05
Overall Rank: 5,329 | 64.19%
DOI: 10.1145/1807167.1807218

Incoming Non-self Citations Over Time

Authors

1. James Cheng (Nanyang Technological University)
2. Ada Wai-Chee Fu (Chinese University of Hong Kong)
3. Jia Liu (Chinese University of Hong Kong)

BibTeX Citation

@inproceedings{cheng_sigmod10,
        title = {{K-Isomorphism: Privacy Preserving Network Publication against Structural Attacks}},
        author = {Cheng, James and Fu, Ada Wai-Chee and Liu, Jia},
        series = {{SIGMOD} '10},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/1807167.1807218},
        url = {https://dl.acm.org/doi/10.1145/1807167.1807218},
        year = {2010}
}

Incoming Citations (Sorted by Pagerank)

Showing 4 of 4 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
5,021	Privacy Preserving Subgraph Matching on Large Graphs in Cloud	2016	SIGMOD	6.3095725e-05
5,582	Neighborhood-Privacy Protected Shortest Distance Computing in Cloud	2011	SIGMOD	6.0739623e-05
6,428	Privacy-Aware Data Management in Information Networks	2011	SIGMOD	5.7865737e-05
7,489	DPGraph: A Benchmark Platform for Differentially Private Graph Analysis	2021	SIGMOD	5.5102404e-05

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
584	Anatomy: Simple and Effective Privacy Preservation	2006	VLDB	0.00015947172
645	Finding Maximal Cliques in Massive Networks by H*-graph	2010	SIGMOD	0.00015208902
1,008	Towards Identity Anonymization on Graphs	2008	SIGMOD	0.00012545302
1,367	Resisting Structural Re-identification in Anonymized Social Networks	2008	VLDB	0.00010905843
2,486	Anonymizing Bipartite Graph Data using Safe Groupings	2008	VLDB	8.3951524e-05
2,965	K-Automorphism: A General Framework for Privacy Preserving Network Publication	2009	VLDB	7.8023198e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	3,037	Injecting Uncertainty in Graphs for Identity Obfuscation	2012	VLDB
2	6,414	Publishing Attributed Social Graphs with Formal Privacy Guarantees	2016	SIGMOD
3	8,720	Personalized Privacy Protection in Social Networks	2011	VLDB
4	5,021	Privacy Preserving Subgraph Matching on Large Graphs in Cloud	2016	SIGMOD
5	609	Private Analysis of Graph Structure	2011	VLDB
6	4,210	Class-based graph anonymization for social network data	2009	VLDB
7	2,486	Anonymizing Bipartite Graph Data using Safe Groupings	2008	VLDB
8	1,367	Resisting Structural Re-identification in Anonymized Social Networks	2008	VLDB
9	1,008	Towards Identity Anonymization on Graphs	2008	SIGMOD
10	2,965	K-Automorphism: A General Framework for Privacy Preserving Network Publication	2009	VLDB