POSTER

Many modern communication systems generate graph data, for example social networks and email networks. Such graph data can be used for recommender systems and data mining. However, because graph data contains sensitive information about individuals, sharing or publishing graph data may pose privacy risks. To protect graph privacy, data anonymization has been proposed to prevent individual users in a graph from being identified by adversaries. The effectiveness of both anonymization and de-anonymization techniques is usually evaluated using the adversary's success rate. However, the success rate does not measure privacy for individual users in a graph because it is an aggregate per-graph metric. In addition, it is unclear whether the success rate is monotonic, i.e. whether it indicates higher privacy for weaker adversaries, and lower privacy for stronger adversaries. To address these gaps, we propose a methodology to systematically evaluate the monotonicity of graph privacy metrics, and present preliminary results for the monotonicity of 25 graph privacy metrics.