Bridging privacy-preserving approaches: a formal comparison of k-automorphism, k-isomorphism, and k-symmetry

Abstract

Anonymization of graph data is fundamental to preserving users’ privacy while publishing social network datasets. The strongest privacy guarantees against any structural attacks provide three well-known methods: k-automorphism, k-isomorphism and k-symmetry. These methods have been proposed independently and are often considered distinct, although certain relationships between them have been noted. This paper presents a comprehensive theoretical analysis of the relationships between these methods. A refined definition of k-automorphism is introduced, formalizing conditions implicitly assumed in practical algorithms. Using this enhanced definition, it is formally proved that k-symmetry and k-automorphism are equivalent. Additionally, the relationship between these two methods and k-isomorphism is analyzed. A novel proof demonstrates that a k-automorphic graph necessarily contains k isomorphic subgraphs. The practical relevance of the provided theoretical results is shown by comparing existing anonymization algorithms. This work contributes to a deeper mathematical understanding of privacy guarantees in graph-structured data, supporting the design of anonymization methods in network security.