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.