提出一种兼顾社区结构与局部关系的高效图嵌入方法
Two Layer Walk: A Community-Aware Graph Embedding
- 通过双层随机游走捕捉社区内紧密连接和社区间稀疏连接
- 在链接预测任务中最高提升3.2%准确率，优于现有方法
- 无需额外参数，适合大规模网络分析，计算高效
社区结构对理解网络的介观组织至关重要，连接局部与全局模式。尽管DeepWalk和node2vec等方法通过随机游走捕捉局部位置信息，但无法保留社区结构；而模块化非负矩阵分解与进化算法虽能弥补此缺陷，却计算开销大，不适用于大规模网络。为此，我们提出双层随机游走（TLWalk）——一种新型图嵌入算法，显式建模分层社区结构。该方法通过社区感知的随机游走机制，在不引入额外参数的情况下平衡社区内与社区间关系。理论分析表明，TLWalk有效缓解了局部性偏差。在基准数据集上的实验显示，其在链接预测任务中性能超越现有最优方法，最高达3.2%的准确率提升。通过编码密集局部与稀疏全局结构，TLWalk展现出鲁棒性与可扩展性，为网络分析提供了一种高效解决方案。
原文摘要 · Abstract (English)
Community structures are critical for understanding the mesoscopic organization of networks, bridging local and global patterns. While methods such as DeepWalk and node2vec capture local positional information through random walks, they fail to preserve community structures. Other approaches like modularized nonnegative matrix factorization and evolutionary algorithms address this gap but are computationally expensive and unsuitable for large-scale networks. To overcome these limitations, we propose Two Layer Walk (TLWalk), a novel graph embedding algorithm that incorporates hierarchical community structures. TLWalk balances intra- and inter-community relationships through a community-aware random walk mechanism without requiring additional parameters. Theoretical analysis demonstrates that TLWalk effectively mitigates locality bias. Experiments on benchmark datasets show that TLWalk outperforms state-of-the-art methods, achieving up to 3.2% accuracy gains for link prediction tasks. By encoding dense local and sparse global structures, TLWalk proves robust and scalable across diverse networks, offering an efficient solution for network analysis.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。