共计 4938 个字符,预计需要花费 13 分钟才能阅读完成。
介绍
在这篇文章中,咱们将应用古代的图机器学习技术在 Wikispeedia navigation paths 门路数据集进行我的项目实际
West & Leskovec 之前在没有应用图神经网络 [1] 的状况下解决了相似的问题。Cordonnier & Loukas 还应用 Wikispeedia 图[2] 上的非回溯随机游走的图卷积网络解决了这个问题。咱们的技术与这两篇论文都不同并且也获得了很好的成果。
在文章的最初还会提供 GitHub 和 Colab 的残缺代码。
数据 + 问题形容
咱们的数据来自斯坦福网络分析我的项目 (SNAP) 的数据集汇合。该数据集获取了由 Wikispeedia 的玩家收集的 Wikipedia 超链接网络上的导航门路数据。Wikispeedia 是一个更多的被称为 Wikiracing 的益智小游戏,目标是机器主动学习常识常识。游戏规则很简略——玩家在较量中抉择两个不同的维基百科文章,指标是在只点击第一篇文章提供的链接的状况下达到第二篇文章并且越快越好。
那么咱们的工作是什么?鉴于成千上万的用户在玩 Wikispeedia 创立的 Wikipedia 页面门路,如果咱们晓得用户到目前为止拜访的页面程序,咱们是否能够预测玩家的指标文章?咱们能够应用图神经网络提供的表达能力来做到这一点吗?
数据预处理
筹备用于图机器学习的数据集须要大量的预处理。第一个指标是将数据表示为一个有向图,其中维基百科文章作为节点,连贯文章的超链接作为边。这一步能够应用 NetworkX,一个 Python 网络分析库,以及 Cordonnier & Loukas [2] 之前的工作。因为 Cordonnier & Loukas 曾经在应用图形建模语言 (GML) 解决并编码了了来自 SNAP 数据集的超链接图构造文件,咱们能够轻松地将其导入 NetworkX。
下一个指标是解决来自 Cordonnier & Loukas 和原始 SNAP 数据集的数据,这样能够为 NetworkX 图中的每篇文章增加节点级属性。对于每个节点,咱们心愿蕴含页面的入度和出度以及文章内容,所以这里应用了文章中每个单词对应的 FastText 预训练词嵌入的平均值示意。Cordonnier & Loukas 解决并编码了每个页面的度和文本文件中相应的内容嵌入。此外,咱们还将每篇文章进行了档次分类的(例如,“猫”页面分类在迷信 > 生物学 > 哺乳动物下)并增加到其相应的节点,所以在解决时应用 Pandas 以解析制表符分隔并为每篇文章生成一个多分类的变量来示意该文章属于哪些类别。而后再通过应用 set_node_attributes 办法,新的文章属性增加到 NetworkX 图中的每个相应节点。
import networkx as nx
# read our graph from file
our_graph = nx.read_gml('graph.gml')
# define our new node attributes
attrs = {"Cat": { "in_degree": 31}, "New_York_City": {"in_degree": 317} }
# add our new attributes to the graph
nx.set_node_attributes(our_graph, attrs)
NetworkX 图表曾经筹备结束能够加载并筹备运行了! 然而,还须要解决和定义输出数据和标签——即导航门路和指标文章。与后面相似,应用 Pandas 解析 SNAP 数据集中已实现的导航门路的制表符分隔值,而后解决每个导航门路以删除返回的点击(由 Wikispeedia 玩家创立的导航从以后页面返回到之前间接拜访的页面),并删除每个门路中的最初一篇文章(咱们的指标文章)。为了荡涤数据,还删除了超过 32 个超链接点击长度的导航门路,并将每个导航门路填充为 32 个长度。
这样失去了超过 50000 条导航门路连贯在 4000 多篇不同的维基百科文章的曾经通过解决的数据集。
WikiNet 模型架构
咱们的新办法试图将递归神经网络 (RNN) 捕捉序列常识的能力与图神经网络 (GNN) 表白图网络结构的能力相结合。以上就是 WikiNet——一种 RNN-GNN 混合体。
import torch
import torch.nn as nn
from torch_geometric.nn import GCN # import any GNN -- we'll use GCN in this example
from torch_geometric.utils import from_networkx
# convert our networkx graph into a PyTorch Geometric (PyG) graph
pyg_graph = from_networkx(networkx_graph, group_node_attrs=NODE_ATTRIBUTE_NAMES)
# define our PyTorch model class
class Model(torch.nn.Module):
def __init__(self, pyg_graph):
super().__init__()
self.graphX = pyg_graph.x
self.graphEdgeIndex = pyg_graph.edge_index
self.gnn = GCN(in_channels=NODE_FEATURE_SIZE,
hidden_channels=GNN_HIDDEN_SIZE,
num_layers=NUM_GNN_LAYERS,
out_channels=NODE_EMBED_SIZE)
self.batch_norm_lstm = nn.BatchNorm1d(SEQUENCE_PATH_LENGTH)
self.batch_norm_linear = nn.BatchNorm1d(LSTM_HIDDEN_SIZE)
self.lstm = nn.LSTM(input_size=NODE_EMBED_SIZE,
hidden_size=LSTM_HIDDEN_SIZE,
batch_first=True)
self.pred_head = nn.Linear(LSTM_HIDDEN_SIZE, NUM_GRAPH_NODES)
def forward(self, indices):
node_emb = self.gnn(self.graphX, self.graphEdgeIndex)
node_emb_with_padding = torch.cat([node_emb, torch.zeros((1, NODE_EMBED_SIZE))])
paths = node_emb_with_padding[indices]
paths = self.batch_norm_lstm(paths)
_, (h_n, _) = self.lstm(paths)
h_n = self.batch_norm_linear(torch.squeeze(h_n))
predictions = self.pred_head(h_n)
return F.log_softmax(predictions, dim=1)
作为模型输出,WikiNet 接管一批页面导航门路。这示意为一系列节点索引。每个导航门路都被填充到 32 的长度——用索引 -1 的序列开始填充短序列。而后应用图神经网络获取现有的节点属性并为超链接图中的每个 Wikipedia 页面生成大小为 64 的节点嵌入。应用 0 的张量作为缺失节点的节点嵌入(例如:那些由索引 -1 示意的填充“节点”)。
在调用节点嵌入序列之后将此张量输出 BN 层以稳固训练。而后将张量输出 RNN——在咱们的例子中是 LSTM 模型。在将张量发送到最终线性层之前,还会有一个 BN 层利用于 RNN 的输入。最初的线性层将 RNN 输入投影到 4064 个类中的一个——最终目标的 wiki 页面。最初就是对输入利用 log softmax 函数生成概率。
WikiNet 图神经网络变体
WikiNet 试验中用于生成节点嵌入有三种图神经网络格调——图卷积网络、图注意力网络和 GraphSAGE。
首先讨论一下图神经网络的个别性能,在图神经网络中,要害思维是依据每个节点的部分邻域为每个节点生成节点嵌入。也就是说,咱们能够将信息从其相邻节点流传到每个节点。
上图示意输出图的计算图。x_u 示意给定节点 u 的特色。这是一个有 2 层的简略示例,只管 GNN 计算图能够是任意深度。咱们将节点 u 在第 n 层的输入称为节点 u 的“第 n 层嵌入”。
在第 0 层,每个节点的嵌入由它们的初始节点特色 x 给出。在高层上,通过聚合来自每个节点的街坊集的第 k 层嵌入,从第(k-1)层嵌入生成第 k 层嵌入。这激发了每个 GNN 层的两步过程:
- 音讯计算
- 聚合
在音讯计算中,通过“音讯函数”传递节点的第 k 层嵌入。在聚合中应用“聚合函数”聚合来自节点街坊以及节点自身的音讯。更具体地说:
图卷积神经网络 (GCN)
一种简略直观的音讯计算方法是应用神经网络。对于聚合能够简略地取街坊节点音讯的平均值。在 GCN 中还将应用偏置项来聚合来自前一层的节点自身的嵌入。最初通过激活函数(例如 ReLU)传递这个输入。因而,方程看起来像这样:
能够训练参数矩阵 W_k 和 B_k 作为机器学习管道的一部分。[3]
GraphSAGE
GraphSAGE 与 GCN 在几个方面有所不同。在这个模型中,音讯是在聚合函数中计算的,聚合函数由两个阶段组成。首先在节点的街坊上进行聚合——在本例中应用均匀聚合。而后通过连贯节点的前一层嵌入对节点自身进行聚合。这个连贯乘以一个权重矩阵 W_k,而后通过一个激活函数来取得输入 [4]。计算层 -(k+1) 嵌入的总体方程如下:
图留神网络(GAT)
GAT 呈现的实践根底是并非所有街坊节点都具备等同的重要性。GAT 相似于 GCN,但不是简略的均匀聚合,而是应用注意力权值 [5] 对节点进行加权。也就是说,更新规定如下:
能够看到 GCN 的更新规定和 GAT 的更新规定是一样的,其中:
与权值矩阵不同留神权值不是每一层惟一的。为了计算这些注意力权重,首先要计算注意力系数。对于每个节点 v 和街坊 u,其系数计算如下:
而后应用 softmax 函数来计算最终的注意力权重,确保权重之和为 1:
这样就能够通过权值矩阵来训练注意力权重。
训练参数
为了训练咱们的模型,咱们依据 90/5/5% 的宰割随机地将咱们的数据集分成训练、验证和测试数据集。应用 Adam 算法作为训练优化器,负对数似然作为咱们的损失函数。咱们应用了以下超参数:
试验后果
咱们评估了 WikiNet 的三个 GNN 变量对指标文章预测精度的影响。这相似于 Cordonnier & Loukas[2]应用的 precision@1 度量。每个 GNN-RNN 混合模型在指标文章预测上的相对精度都比在节点特色上运行的纯 LSTM 基线高出 3% 至 10%。应用 GraphSAGE 作为模型的 GNN 变体的最高准确率为 36.7%。图神经网络捕捉和编码维基百科页面的部分邻域构造信息的能力仿佛比独自的导航门路序列在指标文章预测方面有更大的性能。
援用
[1] West, R. & Leskovec, J. Human Wayfinding in Information Networks (2012), WWW 2012 — Session: Web User Behavioral Analysis and Modeling
[2] Cordonnier, J.B. & Loukas, A. Extrapolating paths with graph neural networks (2019).
[3] Kipf, T.N. & Welling, M. Semi-Supervised Classification with Graph Convolutional Networks (2017).
[4] Hamilton, W.L. & Ying, R. & Leskovec, J. Inductive Representation Learning on Large Graphs (2018).
[5] Veličković, P. et al. Graph Attention Networks (2018).
本文代码:
https://www.overfit.cn/post/8bdf984e46a54ef9a4076d7b82dc6268
作者:Alexander Hurtado