2023年图神经网络GNN基本知识.docx

图神经网络GNN根本知识 掌握图神经网络GNN根本，看这篇文章就够了 3 图 (Graph) 3 图神经网络 3 DeepWalk：第一个无监督学习节点嵌入的算法 4 GraphSage：学习每个节点的嵌入 6 总结 7 使用图神经网络(GNN)寻找最短路径 8 引言 8 人工智能中“图神经网络GNN〞如何理解？（附斯坦福综述） 19 DeepMind、谷歌大脑、MIT等机构联合提出“图网络〞（GNN），将端到端学习与归纳推理相结合，有望解决深度学习无法进行关系推理的问题。 19 掌握图神经网络GNN根本，看这篇文章就够了 【新智元导读】图神经网络(GNN)在各个领域越来越受欢迎，本文介绍了图神经网络的根本知识，以及两种更高级的算法：DeepWalk和GraphSage。 最近，图神经网络 (GNN) 在各个领域越来越受到欢迎，包括社交网络、知识图谱、推荐系统，甚至生命科学。 GNN 在对图形中节点间的依赖关系进行建模方面能力强大，使得图分析相关的研究领域取得了突破性进展。本文旨在介绍图神经网络的根本知识，以及两种更高级的算法：DeepWalk和 GraphSage。 图 (Graph) 在讨论 GNN 之前，让我们先了解一下什么是图 (Graph)。在计算机科学中，图是由两个部件组成的一种数据结构：顶点 (vertices) 和边 (edges)。一个图 G 可以用它包含的顶点 V 和边 E 的集合来描述。 边可以是有向的或无向的，这取决于顶点之间是否存在方向依赖关系。 一个有向的图 (wiki) 顶点通常也被称为节点 (nodes)。在本文中，这两个术语是可以互换的。 图神经网络 图神经网络是一种直接在图结构上运行的神经网络。GNN 的一个典型应用是节点分类。本质上，图中的每个节点都与一个标签相关联，我们的目的是预测没有 ground-truth 的节点的标签。 本节将描述 The graph neural network model (Scarselli, F., et al., 2022) [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 可以直接表述为： 可以通过梯度下降进行优化。 然而，原始 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|)。 Hierarchical Softmax 在训练完 DeepWalk GNN 之后，模型已经学习了每个节点的良好表示，如以下图所示。不同的颜色表示输入图中的不同标签。我们可以看到，在输出图 (2 维嵌入) 中，具有相同标签的节点被聚集在一起，而具有不同标签的大多数节点都被正确地分开了。 然而，DeepWalk 的主要问题是缺乏泛化能力。每当一个新节点出现时，它必须重新训练模型以表示这个节点。因此，这种 GNN 不适用于图中节点不断变化的动态图。 GraphSage：学习每个节点的嵌入 GraphSage 提供了解决上述问题的方法，以一种归纳的方式学习每个节点的嵌入。 具体地说，GraphSage 每个节点由其邻域的聚合 (aggregation) 表示。因此，即使图中出现了在训练过程中没有看到的新节点，它仍然可以用它的邻近节点来恰当地表示。 下面是 GraphSage算法： 外层循环表示更新迭代的数量，而 h ^ k_v 表示更新迭代 k 时节点 v 的潜在向量。在每次更新迭代时，h ^ k_v 的更新基于一个聚合函数、前一次迭代中 v 和 v 的邻域的潜在向量，以及权重矩阵 W ^ k。 论文中提出了三种聚合函数： 1. Mean aggregator： mean aggregator 取一个节点及其所有邻域的潜在向量的平均值。 与原始方程相比，它删除了上面伪代码中第 5 行中的连接运算。这种运算可以看作是一种 “skip-connection〞，在论文后面的局部中，证明了这在很大程度上可以提高模型的性能。 2. LSTM aggregator： 由于图中的节点没有任何顺序，因此它们通过对这些节点进行排列来随机分配顺序。 3. Pooling aggregator： 这个运算符在相邻集上执行一个 element-wise 的 pooling 函数。下面是一个 max-pooling 的例如： 论文使用 max-pooling 作为默认的聚合函数。 损失函数定义如下： 其中 u 和 v 在固定长度的 random walk 中共存，而 v_n 是不与 u 共存的负样本。这种损失函数鼓励距离较近的节点具有相似的嵌入，而距离较远的节点那么在投影空间中被别离。通过这种方法，节点将获得越来越多的关于其邻域的信息。 GraphSage 通过聚合其附近的节点，可以为看不见的节点生成可表示的嵌入。它允许将节点嵌入应用到涉及动态图的域，其中图的结构是不断变化的。例如，Pinterest 采用了GraphSage 的扩展版本 PinSage 作为其内容发现系统的核心。 总结 本文中，我们学习了图神经网络、DeepWalk 和 GraphSage 的根底知识。GNN 在复杂图结构建模方面的强大功能确实令人惊叹。鉴于其有效性，我相信在不久的将来，GNN将在 AI 的开展中发挥重要作用。 使用图神经网络(GNN)寻找最短路径 在本文中，我们将展示具有关注读写功能的图形网络如何执行最短路径计算。经过最少的培训后，该网络可以100％的准确率执行此任务。 引言 在Octavian，我们相信图是表示复杂知识的强大媒介（例如BenevolentAI使用它们来代表药物研究和知识)。 神经网络是一种创造人类无法表达的函数的方法。人们使用大型数据集对网络进行训练。对于神经网络可以处理的模型,我门使用例如的方法训练神经网络拟合输入和输出的关系. 我门需要能够从图结构中进行学习的神经网络,这些神经网络学习有效的归纳偏置用以可靠的学习处理图中的函数.在这个根底上,我门建立了一个强大的神经图系统. 在这里我门提出了一个’面向读写的图网络’,一个可以有效处理最短路径的简单的网络.它是如何组合不同神经网络组件以使系统易于学习经典图算法的一个例子。 这个网络本身是一个新的运算系统，但更重要的是,网络是进一步研究神经图计算的根底。 代码在这里 s://github /Octavian-ai/shortest-path 问题陈述 考虑一个问题“站A和B之间最短路径的长度是多少？ 如果考虑一个图中任意两点的最短路径呢 我们想要通过训练神经网络返回整数的答案. 相关工作 机器学习图表是一个年轻但不断开展的领域。 详细的请参见综述文章Graph Neural Networks: A Review of Methods and Applications or our introduction 用于计算最短路径的经典算法是A-star，Dijkstra和Bellman Ford算法。 这些方法有效并且可以广泛的被应用。 Dijkstra与我们的用例最相似，即在没有路径本钱启发的情况下找到两个特定节点之间的最短路径。 最早的基于神经的最短路径解决方案的工作是通过通信和分组路由来驱动的，这样的近似算法比经典算法速度更快。 这些操作与当今的神经网络完全不同，它们使用迭代反向传播来解决特定图形上的最短路径。 该领域的工作例如包括 Neural networks for routing communication traffic (1988), A Neural Network for Shortest Path Computation (2000) 和 Neural Network for Optimization of Routing in Communication Networks (2022). 本工作建立了一个可以在未知结构图中工作的模型,与前文提到的只能解决某个图中问题的方法形成鲜明的比照.另外,我门寻求为从输入输出对中寻找解决复杂图问题运算提供根底. 最近一个突破性的解决方法在 Differentiable neural computers, 它通过将图形作为连接元组序列并使用读写存储器学习逐步算法来实现这一点。训练的过程以一个学习方案的形式提供,逐步的提高图和问题的规模. 相比之下，我们的解决方案在更大的路径（长度9对4）上表现更好（100％对55.3％），不需要方案学习，不需要训练LSTM控制器，参数更少，网络更简单组件更少。虽然我们还没有找到任何其他公布的解决方案来解决这个问题，但是有很多类似技术被用于不同的问题。几个相关的例子： • Commonsense Knowledge Aware Conversation Generation with Graph Attention 使用注意力来读出知识