Neural-based inexact graph de-anonymization

Abstract

Graph de-anonymization is a technique used to reveal connections between entities in anonymized graphs, which is crucial in detecting malicious activities, network analysis, social network analysis, and more. Despite its paramount importance, conventional methods often grapple with inefficiencies and challenges tied to obtaining accurate query graph data. This paper introduces a neural-based inexact graph de-anonymization, which comprises an embedding phase, a comparison phase, and a matching procedure. The embedding phase uses a graph convolutional network to generate embedding vectors for both the query and anonymized graphs. The comparison phase uses a neural tensor network to ascertain node resemblances. The matching procedure employs a refined greedy algorithm to discern optimal node pairings. Additionally, we comprehensively evaluate its performance via well-conducted experiments on various real datasets. The results demonstrate the effectiveness of our proposed approach in enhancing the efficiency and performance of graph de-anonymization through the use of graph embedding vectors.

Keywords

Graph de-anonymization / Graph convolutional network / Neural tensor network

Declaration of competing interest

The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper.

Acknowledgments

This work is partly supported by the National Science Foundation of U.S. (2011845, 2315596 and 2244219).

References

[1] Z. Cai, Z. He, X. Guan, Y. Li, Collective data-sanitization for preventing sensitive information inference attacks in social networks, IEEE Trans. Dependable Secure Comput. 15 (4) (2016) 577-590.

[2] M.E. Shaw, Communication networks, in: Advances in Experimental Social Psychology, Vol. 1, Elsevier, 1964, pp. 111-147.

[3] X. Zheng, Z. Cai, Privacy-preserved data sharing towards multiple parties in industrial IoTs, IEEE J. Sel. Areas Commun. 38 (5) (2020) 968-979.

[4] E. Alm, A.P. Arkin, Biological networks, Curr. Opin. Struct. Biol. 13 (2) (2003) 193-202.

[5] K. Li, G. Luo, Y. Ye, W. Li, S. Ji, Z. Cai, Adversarial privacy-preserving graph embedding against inference attack, IEEE Internet Things J. 8 (8) (2020) 6904-6915.

[6] Z. Cai, Z. He, Trading private range counting over big IoT data, in: 2019 IEEE 39th International Conference on Distributed Computing Systems, ICDCS, IEEE, 2019, pp. 144-153.

[7] Z. Cai, X. Zheng, J. Wang, Z. He, Private data trading towards range counting queries in internet of things, IEEE Trans. Mob. Comput. (2022).

[8] Z. Cai, X. Zheng, A private and efficient mechanism for data uploading in smart cyber-physical systems, IEEE Trans. Netw. Sci. Eng. 7 (2) (2018) 766-775.

[9] A. Narayanan, V. Shmatikov, De-anonymizing social networks, in: 2009 30th IEEE Symposium on Security and Privacy, IEEE, 2009, pp. 173-187.

[10] N. Korula, S. Lattanzi, An efficient reconciliation algorithm for social networks, 2013, arXiv preprint arXiv:1307.1690.

[11] S. Ji, W. Li, M. Srivatsa, J.S. He, R. Beyah, General graph data de-anonymization: From mobility traces to social networks, ACM Trans. Inf. Syst. Secur. 18 (4) (2016) 1-29.

[12] P. Pedarsani, D.R. Figueiredo, M. Grossglauser, A bayesian method for matching two similar graphs without seeds, in: 2013 51st Annual Allerton Conference on Communication, Control, and Computing, Allerton, IEEE, 2013, pp. 1598-1607.

[13] S. Ji, W. Li, M. Srivatsa, R. Beyah, Structural data de-anonymization: Quantification, practice, and implications, in:Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security, 2014, pp. 1040-1053.

[14] S. Ji, W. Li, M. Srivatsa, R. Beyah, Structural data de-anonymization: Theory and practice, IEEE/ACM Trans. Netw. 24 (6) (2016) 3523-3536.

[15] K. Li, G. Lu, G. Luo, Z. Cai, Seed-free graph de-anonymiztiation with adversarial learning, in:Proceedings of the 29th ACM International Conference on Information & Knowledge Management, 2020, pp. 745-754.

[16] Z. Lou, J. You, C. Wen, A. Canedo, J. Leskovec, et al., Neural subgraph matching, 2020, arXiv preprint arXiv:2007.03092.

[17] T.K. Tu, J.D. Moorman, D. Yang, Q. Chen, A.L. Bertozzi, Inexact attributed subgraph matching, in: 2020 IEEE International Conference on Big Data, Big Data, IEEE, 2020, pp. 2575-2582.

[18] J. Shen, J. Zhou, Y. Xie, S. Yu, Q. Xuan, Identity inference on blockchain using graph neural network, in: Blockchain and Trustworthy Systems: Third International Conference, BlockSys 2021, Guangzhou, China, August 5-6, 2021, Revised Selected Papers 3, Springer, 2021, pp. 3-17.

[19] J. Zhou, C. Hu, J. Chi, J. Wu, M. Shen, Q. Xuan, Behavior-aware account de-anonymization on ethereum interaction graph, IEEE Trans. Inf. Forensics Secur. 17 (2022) 3433-3448.

[20] W. Hamilton, Z. Ying, J. Leskovec, Inductive representation learning on large graphs, Adv. Neural Inf. Process. Syst. 30 (2017).

[21] R. Socher, D. Chen, C.D. Manning, A. Ng, Reasoning with neural tensor networks for knowledge base completion, Adv. Neural Inf. Process. Syst. 26 (2013).

[22] J. Leskovec, R. Sosič, Snap: A general-purpose network analysis and graph-mining library, ACM Trans. Intell. Syst. Technol. 8 (1) (2016) 1-20.

[23] S. Angioni, A. Salatino, F. Osborne, D.R. Recupero, E. Motta, AIDA: A knowledge graph about research dynamics in academia and industry, Quant. Sci. Stud. 2 (4) (2021) 1356-1398.