介绍
在这篇文章中，我们将使用现代的图机器学习技术在 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://github.com/alexanderjhurtado/cs224w_wikinet
https://colab.research.google.com/drive/1geXYFIopoh7W4bLFrICqdkh1HuVySLQn?usp=sharing
作者：Alexander Hurtado