  In a wide spectrum of real-world applications, it is very important to
analyze and mine graph data such as social networks, communication networks,
citation networks, and so on. However, the release of such graph data often
raises privacy issue, and the graph privacy preservation has recently drawn
much attention from the database community. While prior works on graph privacy
preservation mainly focused on protecting the privacy of either the graph
structure only or vertex attributes only, in this paper, we propose a novel
mechanism for graph privacy preservation by considering attacks from both graph
structures and vertex attributes, which transforms the original graph to a
so-called kt-safe graph, via k-anonymity and t-closeness. We prove that the
generation of a kt-safe graph is NP-hard, therefore, we propose a feasible
framework for effectively and efficiently anonymizing a graph with low
anonymization cost. In particular, we design a cost-model-based graph
partitioning approach to enable our proposed divide-and-conquer strategy for
the graph anonymization, and propose effective optimization techniques such as
pruning method and a tree synopsis to improve the anonymization efficiency over
large-scale graphs. Extensive experiments have been conducted to verify the
efficiency and effectiveness of our proposed kt-safe graph generation approach
on both real and synthetic data sets.
