【新智元指南】图形神经网络(GNN )在各个领域越来越受欢迎。本文介绍了图形神经网络的基本知识和两种更高级的算法： DeepWalk和GraphSage。

最近，图形神经网络(GNN )在社交网络、知识地图、推荐系统、甚至生命科学等各个领域受到欢迎。

GNN对图形中节点之间的依赖关系进行建模的能力很高，有关图形分析的研究领域取得了划时代的进展。本文旨在介绍图形神经网络的基本知识和两种更高级的算法： DeepWalk和GraphSage。

在讨论

图 (Graph)

GNN之前，让我们先来了解一下什么是图表(Graph )。在计算机科学中，图是由两个零件组成的数据结构：“顶点”和“边”。图表g可以用它所包含的顶点v和边e的集合来记述。

边可以是定向的，也可以是定向的，这取决于顶点之间是否存在方向依赖关系。

定向图(维基) )。

顶点也称为常规节点。在这篇文章中，这两个术语是可以交换的。

图神经网络

图神经网络是直接在图的结构上工作的神经网络。 GNN的典型应用之一是节点分类。本质上，图中的每个节点与标签相关联，其目的是预测没有ground-truth的节点的标签。

本节就thegraphneuralnetworkmodel (scars elli，f .et al .2009 ) [1]这篇论文中的算法进行说明。因为这是第一次提交GNN的论文，所以通常被认为是原始的GNN。

在节点分类问题的设定中，各节点v的特征x_v与一个ground-truth标签t_v相关联。指定使用已标记节点的一部分的graph G，以预测未标记节点的标签。学习用包含邻近信息的d维向量h_v表示各个节点。也就是说：

其中，x_co[v]表示与v相连的边的特征，h_ne[v]表示与v相邻的节点的嵌入，x_ne[v]表示与v相邻的节点的特征。函数f是将这些输入映射到d维空间的转换函数。为了寻找h_v的唯一解，可以应用Banach不动点定理将上述方程式改写为迭代更新过程。

通过将状态h_v和特性x_v传递给输出函数g，计算GNN的输出。

这里的f和g都可以解释为前馈全连接神经网络。 L1 loss可以直接表现如下。

可以通过坡度下降进行优化。

l-align-justify”>然而，原始 GNN 存在三个主要局限性：

如果放宽 “不动点” (fixed point)的假设，那么可以利用多层感知器学习更稳定的表示，并删除迭代更新过程。这是因为，在原始论文中，不同的迭代使用转换函数 f 的相同参数，而 MLP 的不同层中的不同参数允许分层特征提取。它不能处理边缘信息 (例如，知识图中的不同边缘可能表示节点之间的不同关系)不动点会阻碍节点分布的多样性，不适合学习表示节点。

为了解决上述问题，研究人员已经提出了几个 GNN 的变体。不过，它们不是本文的重点。

DeepWalk：第一个无监督学习节点嵌入的算法

DeepWalk [2] 是第一个提出以无监督的方式学习节点嵌入的算法。

它在训练过程中非常类似于词汇嵌入。其动机是 graph 中节点和语料库中单词的分布都遵循幂律，如下图所示：

该算法包含两个步骤：

在 graph 中的节点上执行 random walks，以生成节点序列运行 skip-gram，根据步骤 1 中生成的节点序列，学习每个节点的嵌入

在 random walks 的每个时间步骤中，下一个节点从上一个节点的邻节点均匀采样。然后将每个序列截断为长度为 2|w| + 1 的子序列，其中 w 表示 skip-gram 中的窗口大小。

本文采用 hierarchical softmax 来解决由于节点数量庞大而导致的 softmax 计算成本高昂的问题。为了计算每个单独输出元素的 softmax 值 , 我们必须计算元素 k 的所有 e ^ xk。

Softmax 的定义

因此，原始 softmax 的计算时间为 O(|V|)，其中 V 表示图中顶点的集合。

分层 softmax 利用二叉树来处理这个问题。在这个二叉树中，所有的叶子 (下图中的 v1, v2，…v8) 都表示 graph 中的顶点。在每个内部节点中，都有一个二元分类器来决定选择哪条路径。要计算给定顶点 v_k 的概率，只需计算从根节点到叶节点 v_k 路径上每一个子路径的概率。由于每个节点的子节点的概率之和为 1，所以所有顶点的概率之和为 1的特性在分层 softmax 中仍然保持不变。由于二叉树的最长路径是 O(log(n))，其中 n表示叶节点的数量，因此一个元素的计算时间现在减少到 O(log|V|)。