1 图神经网络（原始版本）

图神经网络现在的威力和用途也再慢慢加强 我从我看过的最原始和现在慢慢最新的论文不断写上我的看法和见解 本人出身数学 所以更喜欢数学推导 第一篇就介绍图神经网络想法的开端 之后的图神经网络模型 都是基于此慢慢改进。

2 能处理的领域

image

针对常见的旅行者问题 社交网络 分子结构 等等常见的非结构化数据皆能进行处理 不同点在于你g（x） 即输出函数如何设计，图神经模型的贡献在于如何去学习一个非结构数据并将其表征

3 模型

3.1 简介

首先 针对图而言 信息有两大类 一个为图节点信息 一个为图边的信息 图的节点包含了一个节点的“状态”，我们用x（i）来表示i节点的“状态” 这是模型经过学习之后 学到的关于图信息的表征 我们可以很直观的假设 一个点的“状态”与周围节点的状态 周围节点与本节点的边（可以认为是二者的距离） 周围节点的标签 然后我们用一个函数f 去学习 于是我们可以得到以下的

image

我们要做的工作就是去学习到整个图 每个节点的“状态” ，但是我们会发现一个问题 那就是 i节点的“状态‘’ x（i）依赖于j节点的状态x（j） 同理j点也是 二者不断地相互依赖 形成一个循环。模型的假设就是我们可以通过循环迭代 去求解全图的“状态”

3.2

我们引入我们的输出函数g（x，l）即一个节点的输出会与此点的“状态”以及相连的边有关

image

由此我们得到了我们整体模型的两个函数 一个去求解图的状态 一个去输出（根据实际任务）

我们要解决的关键是f函数 如何去求解整个图的状态 数学上存在一个理论 即f对x的导数小于1时，我们可以保证 收敛

image

迭代过程简单而言就是 用t轮的状态 去更新t+1轮的状态 ，最终得到全图收敛的状态。

3.3

image 因此 现在我们可以将求解过程按轮次展开 其中的g与f都为神经网络 结构 你可以自己设计 我们将整个求解过程展开成如下形式 其中前面都是不断迭代求解图的状态过程 image

3.4

前面介绍了图神经模型的大体思路 接下来 我将介绍梯度下降及求导过程 因为图神经网络在求解过程中 需要保证状态收敛 才可以进行下一步 所以求导迭代过程有所不同

首先我们介绍一下一个隐函数的存在性

image

此函数反映了我们真实需要的状态x与我们现在所求t轮的x（t）之间的距离 理论上可以证明 存在能让我们求解到完美x的参数w，继而将参数w与x联系起来。

3.5

然后在引入我们的损失函数e 此函数如何定义损失与你的输出函数g有密切相关 需要你自己设计 再次不在累述。根据模型展开结构 ，我们得到了如下的求导公式 image

这个为通过时间的求导法则 很接近传统rnn 我也不再累述。 根据我们的假设 当迭代一定次数后 z（t）等于z（t+1）

image

根据（8）得到（9） 我们再根据我们之前证明存在的隐函数，以及根据隐函数求导法则得到（10）， （11）为另一个方向求解导数 不根据我们模型的展开，直接根据偏导定义直接求得结果 将（9）（10）（11）带入得到了以下的求导法则

image 再次求导公式中 全部转化为对参数w的求导 接下来为z（T）的一个迭代过程 类似于一个数列的求和 image

至此我们得到了我们全部的求导法则

image

3.6 模型算法

在求导过程中 我们是假设收敛到一个值时 我们才能采用我们推导的公式进行求导 因此 算法方面我们需要增加两个步骤 去验证收敛 然后才能继续求导 整体算法框图如下

image

4 总结

整体模型的贡献就是解决了如何去学一个非结构数据的特征，采用迭代到收敛值的方法去学习，可能大家也发现了 针对两个点之间的联系 边 此模型并没有怎么重点关注 现在的图神经思想类似 不过加入了边的学习。

5 问题与自己想法

首先1） 此模型在计算过程中 要保证f对x的导数小于1 这点会让模型无法加深 层数一高 必然出现梯度消失之类问题

   2） 没有有效去学习边的信息

---

论文引介 |Learning Convolutional Neural Networks for Graphs

原创： 涂存超 [智能立方](javascript:void(0);) 2016-06-10

文章原名：Learning Convolutional Neural Networks for Graphs

作者：Mathias Niepert, Mohamed Ahmed, Konstantion Kutzkov

单位：NEC Labs Europe, Heidelberg, Germany

译者：涂存超

链接：http://arxiv.org/abs/1605.05273

【导读】

这篇文章提出了对任意的图（网络）学习卷积神经网络的框架。这些图可以是有向的或者无向的，节点和边的属性也可以是离散的或者连续的。对于图像来说，卷积神经网络对输入图像的局部关联的区域进行操作，和此类似，本文提出了一种通用的方法，也抽取图中局部关联的区域进行相应的操作。在标准数据集上的实验结果显示，本文提出的方法学习到的特征表示和目前最先进的graph kernel的方法可比，并且计算效率非常高。

【模型】

为了能够对任意结构的图进行卷积操作，这篇文章提出了PATCHY-SAN (Select-Assemble-Normalize)的方法，通过三个步骤构建卷积分片：1. 从图中选择一个固定长度的节点序列；2. 对序列中的每个节点，收集固定大小的邻居集合；3. 对由当前节点及其对应的邻居构成的子图进行规范化，作为卷积结构的输入。通过上述三个步骤构建出所有的卷积片之后，利用卷积结构分别对每个分片进行操作。具体示意图如下图所示。

image

下面具体介绍一下构建卷积分片的步骤以及最后的卷积结构。

1. 节点序列选择：为了对图中所有的节点进行标号排序，本文引入了图标号函数，将图中的节点集合根据向心性（节点的度、中心度等）映射为有序的节点序列。从该序列中根据一定的间隔s隔段选取w个节点构成最终的节点序列。

2. 邻居节点收集：对于上一步获得的节点序列中的每一个节点，利用广度优化搜索扩展邻居节点，和源节点一起构成一个k大小的邻域集合。

3. 子图规范化：对于一个邻域集合的规划化过程如下图所示。对邻域集合中的个节点按照标号函数k进行排序，得到接受域。那么，对于节点的属性，k个节点属性值构成了一个输入通道，对于边的属性，k^{2个属性值也构成了一个输入通道。我们可以分别用一维的卷积层来处理这两种输入通道（对于节点属性卷积层长度为k，对于边属性卷积层长度为k}2）。

image

【贡献】

这篇文章提出了一种通用高效的对任意的图进行表示学习的框架。同图像中的卷积神经网络类似，本文也是通过构建图中局部相连的邻域，然后对这些邻域进行卷积等操作。

其主要贡献在于，首先，将图像领域的卷积神经网络的概念扩展到网络图上。其次，本文提出的PATCHY-SAN模型与现有的方法相比十分高效，而且适用于大规模网络图。同时，PATCHY-SAN也支持对于学习到的图的特征的可视化，能够对图的结构属性有更深层的了解。下图就是对四种不同类型的图的特征可视化及抽取的邻域的可视化。

image

在实验部分，如下图所示，本文还证明了提出的针对图的CNN与目前最先进的graph kernel方法相比是有效的。

image

在理论上，这篇工作的主要贡献还包括：1. 定义了的图及其复杂度的规范化问题；2. 推导并提出了一种比较图集合中不同标号函数的对比方法。
智能立方 论文引介 |Learning Convolutional Neural Networks for Graphs
https://mp.weixin.qq.com/s?__biz=MzIxNzE2MTM4OA==&mid=2665642794&idx=1&sn=b11ec8699218d43bb7b404a4980bf82e&scene=25