  Social graphs are widely used in research (e.g., epidemiology) and business
(e.g., recommender systems). However, sharing these graphs poses privacy risks
because they contain sensitive information about individuals. Graph
anonymization techniques aim to protect individual users in a graph, while
graph de-anonymization aims to re-identify users. The effectiveness of
anonymization and de-anonymization algorithms is usually evaluated with privacy
metrics. However, it is unclear how strong existing privacy metrics are when
they are used in graph privacy. In this paper, we study 26 privacy metrics for
graph anonymization and de-anonymization and evaluate their strength in terms
of three criteria: monotonicity indicates whether the metric indicates lower
privacy for stronger adversaries; for within-scenario comparisons, evenness
indicates whether metric values are spread evenly; and for between-scenario
comparisons, shared value range indicates whether metrics use a consistent
value range across scenarios. Our extensive experiments indicate that no single
metric fulfills all three criteria perfectly. We therefore use methods from
multi-criteria decision analysis to aggregate multiple metrics in a metrics
suite, and we show that these metrics suites improve monotonicity compared to
the best individual metric. This important result enables more monotonic, and
thus more accurate, evaluations of new graph anonymization and de-anonymization
algorithms.
