When Degree Anonymity Is Not Enough: Assessing Structural Re-identification Risk in Social Graphs

• Christiano J. P. de Brito UFPR
• André L. Vignatti UFPR
• Sidgley C. de Andrade UTFPR

DOI: https://doi.org/10.5753/kdmile.2026.31012

Resumo

Removing identifiers and equalizing node degrees do not guarantee graph privacy, as network topology acts as a structural quasi-identifier. Evaluating rather than assuming privacy, this article frames structural re-identification risk assessment as a reproducible evaluation problem and presents a configuration-driven pipeline that anonymizes graphs, validates anonymity, and reports privacy-utility metrics. We adopt the structural k-anonymity paradigm as our core design choice, evaluating it on Facebook Ego-Nets and Email-Enron across k ∈ {2, 5, 10, 20}. Under a 1-hop subgraph adversary (d = 1), effective protection reduces to degree-based anonymity: the 1-hop re-identification rate exceeds the degree-based rate by approximately 6× on Facebook and 38× on Enron at k = 2, indicating that neighborhoods can remain structurally distinguishable. We position this assessment relative to differential privacy (a difference of premises: publishing the whole graph versus releasing queries) and to stronger learned de-anonymization adversaries. Furthermore, increasing k does not improve privacy monotonically, as aggressive anonymization distorts degree distributions and shifts vulnerability patterns. Since our scenarios model basic adversaries, these risk rates represent lower bounds, indicating that graphs anonymized by degree-based protection should undergo structural risk assessment before publication.

Palavras-chave: data privacy, graph mining, k-anonymity, re-identification risk, social networks, structural anonymization

Referências

Backstrom, L., Dwork, C., and Kleinberg, J. Wherefore art thou r3579x? anonymized social networks, hidden patterns, and structural steganography. In Proc. of the 16th Int. Conf. on World Wide Web. ACM, pp. 181–190, 2007.

Brito, F. T. and Machado, J. C. Differentially private release of count-weighted graphs. In Anais Estendidos do XXXIX Simpósio Brasileiro de Bancos de Dados (SBBD 2024). SBC, Porto Alegre, pp. 183–189, 2024.

Cordella, L. P., Foggia, P., Sansone, C., and Vento, M. A (sub)graph isomorphism algorithm for matching large graphs. IEEE Transactions on Pattern Analysis and Machine Intelligence 26 (10): 1367–1372, 2004.

Hao, Y., Li, L., Chang, L., and Gu, T. MLDA: A multi-level k-degree anonymity scheme on directed social network graphs. Frontiers of Computer Science 18 (2): 182814, 2024.

He, X., Vaidya, J., Shafiq, B., Adam, N., and Atluri, V. Preserving privacy in social networks: A structure-aware approach. In Proceedings of the IEEE/WIC/ACM International Joint Conference on Web Intelligence and Intelligent Agent Technology (WI-IAT 2009). IEEE, pp. 647–654, 2009.

Karypis, G. and Kumar, V. A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM Journal on Scientific Computing 20 (1): 359–392, 1998.

Leskovec, J. and McAuley, J. J. Learning to discover social circles in ego networks. In Advances in Neural Information Processing Systems (NIPS 2012). Curran Associates, pp. 539–547, 2012.

Liu, K. and Terzi, E. Towards identity anonymization on graphs. In Proceedings of the 2008 ACM SIGMOD International Conference on Management of Data (SIGMOD 2008). ACM, New York, NY, USA, pp. 93–106, 2008.

Mendonça, A. L. C., Brito, F. T., and Machado, J. C. Privacy-preserving techniques for social network analysis. In Anais Estendidos do XXXVIII Simpósio Brasileiro de Bancos de Dados (SBBD 2023). SBC, Porto Alegre, pp. 174–178, 2023.

Mueller, T. T., Usynin, D., Paetzold, J. C., Rueckert, D., and Kaissis, G. SoK: Differential privacy on graph-structured data. arXiv preprint arXiv:2203.09205, 2022.

Narayanan, A. and Shmatikov, V. Robust de-anonymization of large sparse datasets. In Proceedings of the 2008 IEEE Symposium on Security and Privacy (S&P 2008). IEEE, pp. 111–125, 2008.

Narayanan, A. and Shmatikov, V. De-anonymizing social networks. In Proceedings of the 2009 30th IEEE Symposium on Security and Privacy (S&P 2009). IEEE, pp. 173–187, 2009.

Nettleton, D. F. and Salas, J. A data driven anonymization system for information rich online social network graphs. Expert Systems with Applications vol. 55, pp. 87–105, 2016.

Shervashidze, N., Schweitzer, P., van Leeuwen, E. J., Mehlhorn, K., and Borgwardt, K. M. Weisfeilerlehman graph kernels. Journal of Machine Learning Research vol. 12, pp. 2539–2561, 2011.

Sweeney, L. k-anonymity: A model for protecting privacy. International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems 10 (5): 557–570, 2002.

Wang, H., Yang, W., Man, D., Wang, W., and Lv, J. Anchor link prediction for privacy leakage via deanonymization in multiple social networks. IEEE Transactions on Dependable and Secure Computing 20 (6): 5197–5213, 2023.

Yuan, Q., Zhang, Z., Du, L., Chen, M., Cheng, P., and Sun, M. PrivGraph: Differentially private graph data publication by exploiting community information. In Proceedings of the 32nd USENIX Security Symposium (USENIX Security 2023). USENIX Association, pp. 3241–3258, 2023.

Zhou, B. and Pei, J. Preserving privacy in social networks against neighborhood attacks. In Proceedings of the 2008 IEEE 24th International Conference on Data Engineering (ICDE 2008). IEEE, pp. 506–515, 2008.

Zhou, B., Pei, J., and Luk, W. A brief survey on anonymization techniques for privacy preserving publishing of social network data. SIGKDD Explor. Newsl. 10 (2): 12–22, 2008.