GNN模型及实现细节

GNN实例.ipynb

# (node, label)集
N = [(“n{}”.format(i), 0) for i in range(1,7)] + \
[(“n{}”.format(i), 1) for i in range(7,13)] + \
[(“n{}”.format(i), 2) for i in range(13,19)]
# 边集
E = [(“n1″,”n2”), (“n1″,”n3”), (“n1″,”n5”),
(“n2″,”n4”),
(“n3″,”n6”), (“n3″,”n9”),
(“n4″,”n5”), (“n4″,”n6”), (“n4″,”n8”),
(“n5″,”n14”),
(“n7″,”n8”), (“n7″,”n9”), (“n7″,”n11”),
(“n8″,”n10”), (“n8″,”n11”), (“n8”, “n12”),
(“n9″,”n10”), (“n9″,”n14”),
(“n10″,”n12”),
(“n11″,”n18”),
(“n13″,”n15”), (“n13″,”n16”), (“n13″,”n18”),
(“n14″,”n16”), (“n14″,”n18”),
(“n15″,”n16”), (“n15″,”n18”),
(“n17″,”n18”)]

本文属于对论文《The Graph Neural Network Model》中GNN模型及实现细节的讲解,模型例子基于论文所述的子图匹配任务,本文讲述输入数据的结构、GNN模型实现细节、模型优化等等。本文任务暂未实现代码,不过模型的Pytorch实现可以参见初探GNN:《The Graph Neural Network Model 》

输入数据

对于子图匹配任务,就是事先给定一个子图作为匹配的对象,然后在其它的图中找到是否包含这样的一个子图。数据示例如下

最左边的 [公式] ​为给定的子图(subgraph),右边的两个图​ [公式] 和 [公式] ​为给定的两个graph数据,节点中的数字用于标识节点,数字相同的节点属于同种类型的节点(可以理解为特征相同的节点),论文子图匹配的任务就是给定子图​ [公式] ,在新的graph上对每个节点进行分类,如果该节点属于子图的一部分,那么为​ [公式] ,否则为 [公式] 。在上方的图示中,右边的两个graph的黑色节点由于属于子图​ [公式] ,所以这些黑色节点的标签为 [公式] ​,其余的白色节点的标签为​ [公式] 。总结如下:

  • 输入(Input):子图 [公式] ​、graph数据 [公式] ​。对于所有graph,节点只有10种,使用数字​0-9进行区分。
  • 标签(Label):对于graph( [公式] ​)来说,对于其中的某一节点 [公式] ​,如果该节点属于子图 [公式] ​,那么节点 [公式] ​的标签为 [公式] ​,否则为​ [公式]
    [公式]
  • 任务(Task):给定一个graph,模型预测该graph中每个节点的标签(​1或-1​),即是否属于子图​。

模型细节

GNN模型与其它模型的区别在于,GNN是对每一个节点单独地进行处理和操作,忽略了graph整体的结构,对于GNN的输出,也是在每个节点单独进行、单独输出,所以,这种模型对于输入graph整体的拓扑结构并不在乎。

GNN的任务可以分为node-focused和graph-focused,对于node-focused任务,可以直接取每个节点的输出,对于graph-focused任务(比如图分类任务),可以对所有节点进行求和取平均或者引出新的节点作为graph的输出。因此,上述中GNN对每个节点进行单独的操作并不影响GNN的任务扩展能力

那么,现在考虑如何对每个节点单独地进行操作,只要定义好这样的一个操作,那么我们只需要对所有的节点分别进行同样的操作即可

变量定义

首先定义一下变量,对于图 [公式] ​,节点集合为 [公式] ​,边集合为​ [公式]

  • [公式] ​:节点 [公式] ​特征向量,维度为​ [公式]
  • [公式] ​:节点​ [公式] 的状态向量,维度为​ [公式]
  • ​ [公式] :边 [公式] ​的特征向量,维度为​ [公式]
  • [公式] ​:节点 [公式] ​邻居节点集合
  • [公式] ​:节点​ [公式] 相连的所有边集合

现在以第一张图中的​ [公式] 为例,说明以上变量的含义,如下图

  • 对于节点的状态向量,由于节点初始都没有状态,所以令所有节点的初始状态​ [公式] 为全0,即
    [公式]
    论文中对状态向量的维度设置为5​,所以,每个节点的状态向量如下图,在​t=0时刻,所有节点的状态向量都为0。
  • 对于特征向量,使用节点中的数字表示节点特征,那么,对于节点​ [公式] ,特征向量 [公式] ​可以表示为​ [公式] ,对于节点 [公式] ​,特征向量​可以表示为 [公式] ​,对于节点 [公式] ​,与节点​ [公式] 的特征向量相同,为 [公式] ​,以此类推。
    由此,得到所有节点的特征向量如下,右下角列出所有节点的特征向量

这里同样可以使用one-hot向量来表示节点的特征向量,比如,假设总共有10个特征,那么向量长度为10,节点特征向量就是节点数字对应index为1,其它位置为0的向量,即节点​ [公式] 的特征向量为 [公式] ​。

  • 对于边的特征向量,由于该子图匹配任务不需要边的特征,所以可以忽略边的特征向量或者令边的特征向量为全0。
  • 对于邻居节点,以节点 [公式] ​为例,节点​ [公式] 的邻居节点集合 [公式] ​为 [公式] ​。

节点操作

节点操作涉及到两个方面,一方面,由于刚开始节点的状态初始化全为0,所以需要对节点状态进行更新,通过迭代的方式达到稳定状态,因此,对于节点 [公式] ​需要一个节点状态更新函数 [公式] ​,使得节点的状态由 [公式] ​,由此更新节点状态。

:这里的状态更新函数​和节点有关,不同的节点使用不同的参数​和函数​。

另一方面,对于节点 [公式] ​,最终需要一个输出,因此,需要一个节点输出函数​ [公式] ,用于得到该节点的输出 [公式] ​。

:这里的节点输出函数​ [公式] 同样和节点有关。

  • 考虑节点的状态转化函数​ [公式] ,对于节点​ [公式]
    [公式]
    根据以上公式,可以看出,为了更新 [公式] ​的状态,需要如下变量
    => 该节点 [公式] ​自身的特征向量​ [公式] ,即节点中的数字,对于特定节点,只有一个这样的向量
    => 该节点​ [公式] 相邻边的特征向量 [公式] ​,该任务中为全0或者不考虑,对于特定节点,有co[n]个这样的向量
    => 该节点 [公式] ​相邻节点的特征向量 [公式] ​,即相邻节点中的数字,对于特定节点,有ne[n]个这样的向量。
    => 该节点​ [公式] 相邻节点在​t时刻的状态向量​ [公式] ,即相邻节点的状态,对于特定节点,有ne[n]个这样的向量现在的关键点在于,如何设计转化函数[公式]​,使得该函数与相邻边co[n]的个数以及相邻节点ne[n]的个数无关,最简单的想法是,对其周围的节点分别使用一个函数​ [公式] 进行转换,然后直接进行求和,即
    [公式]
    比如,在​t时刻,更新节点​ [公式] 的状态向量 [公式] ​为​ [公式] ,这个过程的信息流动如下图

其中,黑色带箭头实线表示信息的流动,[公式] ​转换表示节点​ [公式] 的隐藏状态由​ [公式] 转换到了​ [公式] 。可以看出,在使用了这样的求和方式之后,对于任何节点,无论该节点的度(即邻居节点个数)为多少,始终不影响该函数的操作和输出

:这里更新节点状态的时候并没有使用到节点当前时刻的状态。

  • 考虑节点的输出函数​ [公式] ,由于是对每个节点单独使用、单独输出,所以直接使用多层神经网络(全连接)就可以直接输出,即
    [公式]
    值得注意的是,这里的输入仅仅是节点 [公式] ​自己的向量,输出的值为节点 [公式] ​的输出,所以该函数的操作与图的拓扑结构和其它节点均无关

总结一下节点操作,首先,函数 [公式] ​和​ [公式] 通过上述设计后,状态转换操作和输出操作与输入的graph的整体拓扑结构以及每一个节点周围的结构都无关,对于 [公式] ​,使用求和的方式消除节点邻居数量的多样性,对于​ [公式] ,本身就与周围节点以及graph整体结构无关.

其次,函数​ [公式]  [公式] ​的参数 [公式] ​都与操作的节点对象有关,比如,对于节点 [公式] ​,函数的参数为 [公式] ​,在该任务中,可以直接设置参数共享,即对于所有的节点,函数 [公式] ​的 [公式] ​参数共享,可以写成 [公式] ​,函数​ [公式] 的​ [公式] 参数共享,可以写成​ [公式] 。

Forward过程

首先,假设现在输入一个graph数据(在实现的时候输入的是节点集合​ [公式] 以及邻接矩阵 [公式] ​),以及对应每个节点的特征向量初始化状态向量,如下图

然后,对图中的每一个节点,使用公式

[公式]

一直迭代T​次,这里的T​是一个超参数,需要预先设置,按照迭代时刻展开,变量的变化过程如下

图中标出了​t=0时刻到​t=1时刻节点 [公式] ​的隐藏状态由 [公式] 转化为 [公式] ​的信息流动方向,其它节点类似。每一个大方框表示在对应时刻的各个节点变量的值,可以看到,节点的特征向量 [公式] 在迭代过程中始终是不变的,而状态向量​ [公式] 是一直变化的,在迭代 [公式] ​次之后,状态向量会接近于函数的不动点

在迭代​次后,得到了第T​时刻每个节点的状态向量,然后对每个节点应用函数​ [公式] ,得到每个节点的输出 [公式] ​,该过程如下图

可以看出,每一个节点的输出,就是将​T时刻对应节点的特征向量 [公式] 和状态向量 [公式] 使用函数​ [公式] 变换后的输出

得到了节点的真实输出​ [公式] 之后,按照之前的节点标签 [公式] ​,使用回归的思想求得最终的loss

[公式]

总结一下,forward过程输入了一个graph数据,以及对应节点特征和状态,然后使用迭代的方式分别对所有的节点单独应用 [公式] ​函数,在这个过程中,节点特征向量不变,状态向量在迭代过程中不断更新;迭代​T次后,取T​时刻的节点状态,对所有的节点分别单独应用 [公式] ​函数,每个节点都会得到一个输出,然后与节点标签比较求得最终的loss。

Backward过程

在forward过程中求得loss之后,按照反向传播的步骤可以求得参数的梯度,然后使用梯度下降法进行优化,值得注意的是,在所有涉及到的参数中,哪些变量需要求出对应梯度

  • ​ [公式] 不需要梯度,因为对于输入特定的graph和节点,节点特征已经固定
  • ​ [公式] 不需要梯度,同样边的特征也固定
  • 函数 [公式] ​的参数 [公式] ​需要梯度,函数​ [公式] 的参数 [公式] ​需要梯度
  • [公式]​不需要梯度,[公式]需要梯度

关键在于最后一个,首先 [公式] ​不需要梯度是因为最初的​ [公式] 可以任意赋值,而且,迭代到T​时刻的不动点与 [公式] ​的初值无关,因此,完全不需要对初值进行优化,而对于 [公式] ​,forward的迭代过程如下

[公式]

可以看出,由于参数​ [公式] 需要梯度,所以在迭代过程中的 [公式] ​也需要梯度,这些梯度是用来求​ [公式] 的梯度服务的。

编辑于 2019-08-13

发表评论

电子邮件地址不会被公开。 必填项已用*标注