图（graph）中的随机游走（random walk）到底怎么应用，其具体原理是什么？

Question

如题所述

Answer 1

探索图中的随机游走：原理与应用

在机器学习的大世界中，图与数据的融合是一种关键的步骤，这就是图嵌入的魔术。面对海量节点的社交网络，如何将这些节点嵌入到向量空间以避免维度灾难，这就需要DeepWalk这位神奇的助手登场。它源于Google的创新算法Word2Vec，后者曾以单词向量的生成而闻名。

Word2Vec以前，词向量通常是通过独热编码实现的，每个词对应一个全零向量，只有特定位置为1，但这种编码方法效率低且缺乏语义联系。Word2Vec的突破在于将单词映射到一个向量空间，让相似的词在空间中紧密相连，如"国王-男人+女人≈女王"，这就是通过skip-gram模型训练，预测上下文单词来捕捉词的语义特征。

接着，DeepWalk在2014年带来了图嵌入的新视角。Bryan Perozzi巧妙地将Word2Vec的思想应用于图，通过随机游走模拟节点的"醉汉漫步"。随机游走生成的节点序列，就像一个自然的语言句子，被输入Word2Vec模型，以此学习节点的上下文特征，从而得到每个节点的嵌入向量，应用于各种下游任务，如链接预测和节点分类。

Node2Vec是对DeepWalk的进一步优化，它引入了有偏二阶随机游走，允许节点在游走过程中更灵活地选择路径。通过调整参数p和q，Node2Vec在保持局部信息的同时，探索更深层次的结构。然而，随机游走方法的局限在于无法适应新节点的加入，且对地理位置信息的依赖可能限制了全局特征的捕捉。

为了克服这些问题，全图嵌入的方法尝试整合所有节点的信息，通过虚拟节点或匿名随机游走来捕捉图的全局特性。匿名随机游走不仅考虑了节点间的连接，还引入了图元核方法，通过概率统计序列出现的频率，构建图的特征向量。而自监督学习则通过预测随机游走序列，让神经网络学习到图的内在结构特征。

总的来说，随机游走在图嵌入中的应用，不仅展示了数据结构与机器学习的巧妙结合，更展示了在处理大规模复杂网络时的创新思维。每一步优化都在挑战传统的理解，推动着我们更深入地挖掘图数据的潜在价值。