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.