作者：Elior Cohen
编译：ronghuaiyang

导读

图嵌入是图学习的重要手段，今天给大家介绍一个非常经典的方法，node2vec，图嵌入必学方法之一。

原始论文: https://arxiv.org/pdf/1607.00653.pdf

算法实现 — By Elior Cohen：https://github.com/eliorc/node2vec

算法实现 — By the algo author: https://github.com/aditya-grover/node2vec

展示案例代码: https://github.com/eliorc/Medium/blob/master/Nod2Vec-FIFA17-Example.ipynb

动机

嵌入……每个数据科学家现在都听说过这个词，但主要是在NLP上下文中。

那么，我们为什么要费尽心思去嵌入呢？

在我看来，创建高质量的嵌入并将其作为模型的输入，与著名的“Garbage in, garbage out”正好相反。

当你将低质量的数据输入到模型中时，你将整个学习的负担都压在了模型上，因为它将不得不学习从数据中得出的所有必要结论。

相反，当你使用高质量的嵌入时，你已经在数据中放入了一些知识，从而使你的模型更容易地了解问题。

另一个需要考虑的点是信息 vs 领域知识。

例如，让我们考虑词嵌入(word2vec)和词袋表示。

虽然这两种单词表示方式都可以在一个句子中包含某个词的全部信息，但词嵌入还包括词与词之间的关系等领域知识。

在这篇文章中，我将讨论一种称为node2vec的技术，它的目的是为图中的节点创建嵌入(在G(V, E, W)的意义上)。

我将解释它是如何工作的，并用Python 3对它进行了实现，以及一些额外的功能。

嵌入的过程

那么怎么做呢？

嵌入本身的学习方法与word2vec的嵌入学习方法相同 — 使用的是skip-gram模型。

我认为解释node2vec最自然的方式是解释node2vec如何生成“语料库” — 如果我们理解了word2vec，我们就已经知道如何嵌入语料库了。

如何从图中生成语料库呢？这正是node2vec的创新之处，它是用了采样策略的智能方式来做的。

为了从输入图生成语料库，让我们将语料库看作一组有向无环图，最大输出度为1。如果我们想一下，这是一个完美的文本句子的表达，句子中的每个单词都是一个节点，它指向句子中的下一个单词。

用图表示句子

通过这种方式，我们可以看到word2vec已经可以对图进行嵌入，但是是一种非常特殊的图。

然而，大多数图并不是那么简单，它们可以是(非)有向的，(非)加权的，(无)循环的，基本上在结构上比文本复杂得多。

为了解决这个问题，node2vec使用了一个可调整的(通过超参数)抽样策略，对这些有向无环子图进行抽样。这是通过从图的每个节点生成随机游走来实现的。很简单对吧？

在我们深入研究采样策略如何使用超参数生成这些子图之前，让我们先来看看这个过程：

Node2vec嵌入过程

采样策略

现在我们已经有了大致思路，是时候深入挖掘了。

Node2vec的抽样策略，接受4个参数：

行走次数：图中每个节点产生的随机行走次数
行走长度：每次随机行走中有多少个节点
P：返回超参数
Q：输入输出超参数

以及标准的skip-gram参数(上下文窗口大小、迭代次数等)。

前两个超参数非常容易理解。

随机游走生成算法遍历图中的每个节点，生成一定长度<游动长度>的<游走次数>随机游动，。

Q和P，最好用可视化来解释。

假设你正在进行随机游走，并且刚刚在下图中从节点<t>转换到节点<v>。

从<v>转换到他的任何一个邻居的概率是：< 边权重 > <α >(归一化的)，< *α >取决于hyperparameters。

P控制访问<v>后返回<t>的概率。

Q控制探索图中未发现部分的概率。

直观地说，这有点像tSNE中的perplexity参数，它允许你重视图的局部或者全局结构。

不要忘记权重也是要考虑的，所以最终的路径的概率是一个函数:

1、遍历的前一个节点
2、P和Q
3、边的权值

理解这一部分很重要，因为它是node2vec的本质。如果你没有完全理解抽样策略背后的思想，我强烈建议你再读一遍这部分。

使用抽样策略，node2vec将生成用于嵌入的“句子”(有向子图)，就像word2vec中使用文本句子一样。为什么要改变一些事情，如果它是正确的？

代码

现在是时候将node2vec付诸行动了。

你可以在这里找到这个node2vec的完整代码：https://github.com/eliorc/medium/blob/master/nod2vec-fifa17example.ipynb。

我使用node2vec算法的实现作为示例，它增加了对分配节点特定参数(q、p、num_walks和walk length)的支持。

我们要做的是，利用欧洲足球队的队形，嵌入7个不同俱乐部的球队、球员和位置。

我将使用的数据取自Kaggle上的FIFA 17数据集。

在国际足联(通过EASports)中，每支球队都可以用图表示，如下图所示。

来自FIFA17的例子，很容易理解为一个图

正如我们所看到的，每个位置都与其他位置相连，在比赛中每个位置都被分配给一个球员。

有几十种不同的阵型，它们之间的连接也不同。也有一些位置在某些阵型中存在，但在其他阵型中不存在，例如“LM”位置在其他阵型中不存在。

我们这样做：

1、节点是球员、球队名称和位置

2、对于每个球队，创建一个单独的图，其中每个球员节点连接到他的球队名称节点、连接到他的队友节点并连接到他的队友位置节点。

3、对生成的图应用node2vec

注意：为了为球队内部和不同球队之间的每个位置创建单独的节点，我向类似的节点添加了后缀，并在生成walk之后删除了它们。这是一个技术问题，为了更好地理解，请检查代码中的repo

输入数据的第一行是这样的(经过一些排列)：

从输入数据中采样行

然后，我们利用FIFA17构造图。

使用我的node2vec包，图必须是networkx.Graph的一个实例。

在此之后检查图的边，我们将得到以下结果：

for edge in graph.edges:
 print(edge)
>>> ('james_rodriguez', 'real_madrid')
>>> ('james_rodriguez', 'cm_1_real_madrid')
>>> ('james_rodriguez', 'toni_kroos')
>>> ('james_rodriguez', 'cm_2_real_madrid')
>>> ('james_rodriguez', 'luka_modric')
>>> ('lw_real_madrid', 'cm_1_real_madrid')
>>> ('lw_real_madrid', 'lb_real_madrid')
>>> ('lw_real_madrid', 'toni_kroos')
>>> ('lw_real_madrid', 'marcelo')
...

正如我们所看到的，每个球员都和他的球队，位置和队友联系在一起。

所有附加到位置的后缀将在步长计算后返回到它们原来的字符串(lw_real_madrid→ lw)。

现在我们有了图，我们执行node2vec。

# pip install node2vec
from node2vec import Node2Vec
# Generate walks
node2vec = Node2Vec(graph, dimensions=20, walk_length=16, num_walks=100)
# Reformat position nodes
fix_formatted_positions = lambda x: x.split('_')[0] if x in formatted_positions else x
reformatted_walks = [list(map(fix_formatted_positions, walk)) for walk in node2vec.walks]
node2vec.walks = reformatted_walks
# Learn embeddings
model = node2vec.fit(window=10, min_count=1)

我们给 node2vec.Node2Vec一个networkx.Graph实例。在使用 .fit()之后，我们得到一个gensim.models.Word2Vec的实例。

首先，我们将检查不同节点之间的相似性。

我们期望一个球队节点最相似的节点是它的球员：

for node, _ in model.most_similar('real_madrid'):
 print(node)
>>> james_rodriguez
>>> luka_modric
>>> marcelo
>>> karim_benzema
>>> cristiano_ronaldo
>>> pepe
>>> gareth_bale
>>> sergio_ramos
>>> carvajal
>>> toni_kroos

这些都是真正的皇马球员！

接下来，我们检查与特定位置的相似性。我们希望球员在那个位置上或者差一点的情况下接近那个位置。

# Right Wingers
for node, _ in model.most_similar('rw'):
 # Show only players
 if len(node) > 3:
 print(node)
>>> pedro
>>> jose_callejon
>>> raheem_sterling
>>> henrikh_mkhitaryan
>>> gareth_bale
>>> dries_mertens
# Goal keepers
for node, _ in model.most_similar('gk'):
 # Show only players
 if len(node) > 3:
 print(node)
>>> thibaut_courtois
>>> gianluigi_buffon
>>> keylor_navas
>>> azpilicueta
>>> manuel_neuer

在第一次尝试中(右翼)我们确实从不同的俱乐部得到了不同的右翼，这又是一场完美的匹配。

在第二次尝试中，我们得到了除了Azpilicueta之外的所有守门员，Azpilicueta实际上是一名后卫。

效果很好，对吧？在我们结束之前，让我们使用tSNE来降维和可视化球员节点。

球员节点可视化

看看，我们得到了基于不同俱乐部的漂亮的聚类。

英文原文： https://towardsdatascience.com/node2vec-embeddings-for-graph-data-32a866340fef

请长按或扫描二维码关注本公众号