RED: Learning the role embedding in networks via Discrete-time quantum walk

摘要

Role embedding aims to embed role-similar nodes into similar representations. Role embedding is significant in graph mining, providing a key bridge between traditional role analysis and machine learning. However, current methods suffer from information loss due to the inherent drawbacks, thus failing to capture role information comprehensively from both global and local perspectives. This paper proposes RED (Role Embedding via Discrete-time quantum walk) to address the above issue via quantum walks, whose characters are naturally applicable to role embedding. Based on the superposition, RED simultaneously learns global role representations by evolving features in a global evolution. Besides, RED uses the quasi-periodicity to capture long-term evolving features within steps. To represent local role information, RED simulates a wave-like diffusion by biased walks, where it learns the closeness from accumulated probabilities for local role representations. To the best of our knowledge, RED is the first to apply quantum walks to the role embedding. Substantial experiments demonstrate that RED significantly outperforms state-of-the-art methods by up to 2300.00% in role detection, 90.93% in equivalency identification, and is overwhelmingly superior in robustness.