秒懂算法 | 基于图神经网络的推荐算法
图神经网络(Graph Neural Networks,GNN)是近几年兴起的学科,用来作推荐算法自然效果也相当好,但是要学会基于图神经网络的推荐算法之前,需要对图神经网络自身有个了解。
图卷积网络(Graph Convolutional Networks,GCN)提出于2017年。GCN 的出现标志着图神经网络的出现。深度学习最常用的网络结构是CNN 和RNN。GCN 与CNN 不仅名字相似,其实理解起来也很类似,都是特征提取器。不同的是,CNN 提取的是张量数据特征,而GCN 提出的是图结构数据特征。
01、计算过程
其实GCN 的公式本身非常简单,初期研究者为了从数学上严谨地推导该公式是有效的,所以涉及诸如傅里叶变换,以及拉普拉斯算子等知识。其实对于使用者而言,可以绕开那些知识并且毫无影响地理解GCN。
以下是GCN 网络层的基础公式,具体如下:
其中,
指第1层的输入特征,自然是指输出特征。指线性变换矩阵。是非线性激活函数,如ReLU 和Sigmoid等,所以重点是那些A 和D是什么。
首先说
,通常邻接矩阵用A 表示,在A 上加个波浪线的叫作“有自连的邻接矩阵”,以下简称自连邻接矩阵。定义如下:
其中,I 是单位矩阵(单位矩阵的对角线为1,其余均为0),A 是邻接矩阵。因为对于邻接矩阵的定义是矩阵中的值为对应位置节点与节点之间的关系,而矩阵中对角线的位置是节点与自身的关系,但是节点与自身并无边相连,所以邻接矩阵中的对角线自然都为0,但是如果接受这一设定进行下游计算,则无法在邻接矩阵中区分“自身节点”与“无连接节点”,所以将A 加上一个单位矩阵I 得到A~,便能使对角线为1,就好比添加了自连的设定,如图1所示。
■ 图1 GCN无向无权图示意图
是自连矩阵的度矩阵,定义如下:
如果仍然用上述图例中的数据:
则
所以:
是在自连度矩阵的基础上开平方根取逆。求矩阵的平方根和逆的过程其实很复杂,好在只是一个对角矩阵,所以此处直接可以通过给每个元素开平方根取倒数的方式得到。在无向无权图中,度矩阵描述的是节点度的数量; 若是有向图,则是出度的数量; 若是有权图,则是目标节点与每个邻居连接边的权重和,而对于自连度矩阵,是在度矩阵的基础上加一个单位矩阵,即每个节点度的数量加1。
GCN公式中的
其实都是从邻接矩阵计算而来的,所以甚至可以把这些看作一个常量。模型需要学习的仅仅是这个权重矩阵。
正如之前所讲,GCN 神经网络层的计算过程很简单,如果懂了那个公式,则只需构建一张图,统计出邻接矩阵,直接代入公式即可实现GCN 网络。
02、公式的物理原理
下面来理解一下GCN 公式的物理原理。首先来看
这一计算的意义,如图2所示。
■ 图2 运行Git检查工具
相信大家了解矩阵间点乘的运算规则,即线性变化的计算过程。在自连邻接矩阵满足图2的数据场景时,下一层第1个节点的向量表示是当前层节点h1、h2、h3、h5 这些节点向量表示的和。这一过程的可视化意义如图3所示。
■ 图3 GCN计算过程图解(2)
这一操作就像在卷积神经网络中进行卷积操作,然后进行一个求和池化(Sum Pooling)。这其实是一条消息传递的过程,Sum Pooling是一种消息聚合的操作,当然也可以采取平均、Max等池化操作。总之经消息传递的操作后,下一层的节点1就聚集了它一阶邻居与自身的信息,这就很有效地保留了图结构承载的信息。
接下来看度矩阵D 在这里起到的作用。节点的度代表着它一阶邻居的数量,所以乘以度矩阵的逆会稀释掉度很大的节点的重要度。这其实很好理解,例如保险经理张三的好友有2000个,当然你也是其中的一个,而你幼时的青梅竹马小红加上你仅有的10个好友,则张三与小红对于定义你的权重自然就不该一样。
这一计算的可视化意义如下:
没错,这是一个加权求和操作,度越大权重就越低。图4中每条边权重分母左边的数字4是节点1自身度的逆平方根。
■ 图4 GCN计算过程图解(3)
上述内容可简单地理解GCN 公式的计算意义,当然也可结合具体业务场景自定义消息传递的计算方式。
图神经网络之所以有效,是因为它很好地利用了图结构的信息。它的起点是别人的终点。本身无监督统计图数据信息已经可以给预测带来很高的准确率。此时只需一点少量的标注数据进行有监督的训练就可以媲美大数据训练的神经网络模型。
- 点赞
- 收藏
- 关注作者
评论(0)