Two Layer Walk: A Community-Aware Graph Embedding

Community structures play a pivotal role in understanding the mesoscopic organization of networks, bridging local and global patterns. While methods like DeepWalk and node2vec effectively capture node positional and local structural information through random walks, they fail to incorporate critical community information. Other approaches, such as modularized nonnegative matrix factorization and evolutionary algorithm-based methods, preserve community structures but suffer from high computational complexity, making them unsuitable for large-scale networks. To address these limitations, we propose Two Layer Walk (TLWalk), a novel graph embedding algorithm that explicitly incorporates hierarchical community structures. By balancing intra-and inter-community relationships through a community-aware random walk mechanism automatically without using any parameters, TLWalk achieves robust and scalable representation learning that can fully extract local and global topologies, which is proved theoretically by showing TLWalk can overcome locality bias in the walk. We also theoretically prove the relationship between TLWalk and matrix factorization. Extensive experiments on benchmark datasets demonstrate TLWalk's superior performance, with significant accuracy gains--up to 3.2%--over existing methods for the link prediction task. TLWalk's ability to encode both dense local and sparse global structures ensures its adaptability across diverse network types, offering a powerful and efficient solution for network analysis.