@TOC

GNN的应用简述

GNN的适用范围非常广泛：

• 显式关联结构的数据：药物分子、电路网络等
• 隐式关联结构的数据：图像、文本等

生物化学领域中：分子指纹识别、药物分子设计、疾病分类等
交通领域中：对交通需求的预测、对道路速度的预测等
计算机图像领域：目标检测、视觉推理等
自然语言处理中：实体关系抽取、关系推理等

GNN的3大优势：
（1）GNN具有强大的图数据拟合能力
（2）GNN具有强大的推理能力。
（3）GNN与知识图谱结合

GNN的应用案例

1. 3D视觉

3D视觉数据的表示方式有多种，如点云（Point Cloud）、网格（Mesh）等。
（1）点云
点云数据是一种有效的三维物体的表示方法，它随着深度感知技术，比如微软的Kinect以及激光探测与测量技术的发展而流行起来。点云数据由一组点组成，每个点都记录有三维坐标(x,y,z)，除此之外，还可以记录采集点的颜色、强度等其他丰富的信息，因此，高精度的点云数据可以很好地还原现实世界。

对点云数据的理解包含几个关键步骤，即点云分类、点云语义分割、点云场景分析。

• 点云分类，即给定一组点云，计算机识别出这组点云到底描绘的是什么物体。
• 点云语义分割要求理解得更细致，比如物体的构成。
• 点云场景分析需要进一步的学习和分析，给定一个场景，识别出包含的不同物体以及空间位置，甚至做出推理。

在GNN被应用到点云数据处理之前，一种解决思路是将点云强制表示为体元（voxel），这样就得到与图像类似的一种三位规则结构，方便卷积和池化操作，缺点是增加了数据量，计算开销大。另一种思路是将点云转换为多视觉图（Multi-view Images），即一组虚拟的二维快照，生成RGB和包含几何特征的合成视图，然后在图像处理完毕后再将其语义分段投影回原始的点云数据，缺点是不能捕捉3D点云的内在结构。

点云数据中的点是离散存在的，点与点间的距离 d d d是确定点彼此之间关系的基础，基于点坐标 ( x , y , z ) (x,y,z) (x,y,z)的欧式空间距离是一种常见的选择；其他非欧氏空间的距离选择如测地(geodesic)距离、形状感知距离等，可以很好地处理非刚性特征，例如PointNet++算法。

有了距离即可确定点与点之间的邻接关系。如何将距离转化为邻接关系？通常需要定义邻域，每个点都与其邻域范围内的点相连，而与邻域外的点无邻接关系。邻域范围可以根据K最近邻法（K nearest neighbor）确定，也可以根据球查询（落在半径范围的球状区域内的所有点）确定。
注意：点之间的邻接关系在每一层的图中并不是固定不变的。PointNet++算法采用了每一层固定邻域点进行卷积操作的策略，而在Edge-Conv的算法中，每一层中的图都可以动态地调整图中节点之间的邻接关系， K K K邻域内的点随着网络的更新发生变化，这样就能自适应地捕捉和更新点云的局部几何特征。在点云分类和分割中取得较好的效果。

邻接关系确定后的另一个关键步骤是基于邻接边的卷积该如何实现。定义 e i j = h Θ ( x i , x j ) e_{ij}=h_\Theta(x_i,x_j) eij​=hΘ​(xi​,xj​)为点 v i v_i vi​和 v j v_j vj​间的边，其中 h Θ h_{\Theta} hΘ​为含有可学习参数 Θ \Theta Θ的非线性函数。

DGCNN通过构建局部邻居图维持了局部几何结构，然后将类卷积操作应用在节点与其邻居相连的边上。DGCNN每一层固定节点的邻居是变化的，所以每一层的图结构不同，也使得算法具有非局部扩散的性质。
以节点 v i v_i vi​为中心的卷积计算如下：
x i ′ = A g g x j ∈ N ( x i ) h Θ ( x i , x j ) x'_i=Agg_{x_j\in N(x_i)}h_\Theta(x_i,x_j) xi′​=Aggxj​∈N(xi​)​hΘ​(xi​,xj​)
PointNet++和Atzmon等（2018）提出的PCNN方法采用 h Θ ( x i , x j ) = h Θ ( x j ) h_\Theta(x_i,x_j)=h_\Theta(x_j) hΘ​(xi​,xj​)=hΘ​(xj​)的方式，即卷积值通过对邻居进行聚合得到。若以 Θ = ( θ 1 , . . . , θ m ) \Theta=(\theta_1,...,\theta_m) Θ=(θ1​,...,θm​)表示卷积滤波矩阵的权重，以PCNN算法为例，卷积的计算如下所示：
x i m ′ = ∑ h θ i ( x j ) g ( d ( x i , x j ) ) x'_{im}=\sum h_{\theta_i}(x_j)g(d(x_i,x_j)) xim′​=∑hθi​​(xj​)g(d(xi​,xj​))
其中， g g g表示高斯核函数， d ( x i , x j ) d(x_i,x_j) d(xi​,xj​)表示点 v i v_i vi​和 v j v_j vj​之间的距离，与节点的特征相关。而EdgeConv算法基于非对称的边特征计算函数： h Θ ( x i , x j ) = h ‾ Θ ( x i , x j − x i ) h_\Theta(x_i,x_j)=\overline{h}_{\Theta}(x_i, x_j-x_i) hΘ​(xi​,xj​)=hΘ​(xi​,xj​−xi​)。

更具体地，上述公式的m通道计算公式如下：
e i j m ′ = R e L U ( θ m ⋅ ( x j − x i ) + ϕ m ⋅ x i ) e'_{ijm}=ReLU(\theta_m\cdot (x_j-x_i)+\phi_m\cdot x_i) eijm′​=ReLU(θm​⋅(xj​−xi​)+ϕm​⋅xi​)，最后再应用聚合函数，得到节点 i i i的m通道的数值如下：
x i m ′ = max ⁡ j : ( i , j ) ∈ ϵ e i j m ′ x'_{im}=\max_{j:(i,j)\in \epsilon} e'_{ijm} xim′​=j:(i,j)∈ϵmax​eijm′​

关于动态图更新，前面已经多次提到，DGCNN中每层图的结构是根据节点的K近邻动态生成的，表示如下：
G ( l ) = ( ⋎ ( l ) , ϵ ( l ) ) G^{(l)}=(\curlyvee^{(l)},\epsilon^{(l)}) G(l)=(⋎(l),ϵ(l))
节点的K近邻根据 < 节 点 , 邻 居 > <节点,邻居> <节点,邻居>对的embedding距离筛选得到，因此需要维护一个pairwise距离矩阵用以找出每个节点的K近邻。

与DGCNN相关的模型有两类：PointNet、graph CNN。它们与DGCNN有相似的模型范式，具体如下：

通常模型的输入是点云数据的三维坐标值（x,y,z）。

• 对于点云分类，重点是识别整个数据集属于什么类别，输出值是关于类别的标签，属于图层面的输出，侧重学习数据集的全局特征
• 对于点云分割，需要知道每个点云属于哪一部分，假设P物体子部位的数目，因此模型输出为 N × P N\times P N×P维打分矩阵，属于节点层面的输出，除了需要学习全局特征外，还需要结合局部几何特征。

2.2 基于社交网络的推荐系统

在线社区存在显式的用户社交网络信息，如何将这部分信息编码进推荐系统是一个十分关键的问题。
难点1：用户兴趣有短期和长期之分，短期兴趣是动态变化的；
难点2：用户会受到其在线社交圈中的朋友的影响；
难点3：社交网络对用户兴趣的影响并非固定或恒定的，而是根据用户处境（context）动态变化的。

以 D G R E C DGR_{EC} DGREC​模型为例，介绍如何融合社交网络信息从而搭建推荐系统。给方法提出了一种基于动态图注意神经网络的在线社区推荐系统：利用递归神经网络对动态用户行为进行建模；并利用图注意神经网络对dynamic influence进行描述，即根据用户当前的兴趣动态推断影响因素。

如图中所示，首先把behaviors看作a sequence of actions (e.g., item clicks) ,为了捕获用户的动态兴趣，我们将他们的actions分割成子序列，表示为sessions，所以我们关注的就是in session-based recommendations。那么在session（a）部分，用户Alice最近关注了sports，然后他的朋友bob和eva是sports fans（看作lont-term intersets），他们最近关注的sports items 就是 short-term interests，那么很有可能给Alice推荐羽毛球。在session（b）部分。用户Alice最近关注了乐器，但是他的朋友们最近都没有关注这些，但是David是乐器的long-term interests，所以这种情况david对Alice来说就是有意义的，那么David看过的书就可能被推荐。所以用户的current interests 是受他不同朋友的lont-term and short-term interests影响的。

在经典推荐模型(例如，矩阵分解[26])中，用户消费项目的顺序被忽略。然而，在在线社区中，用户偏好变化很快，为了模拟用户的动态兴趣，必须考虑用户偏好行为的顺序。在实践中，由于用户的整个历史记录可能非常长(例如，某些在线社区已经存在多年)，并且用户的兴趣快速切换，所以一种常见的方法是将用户偏好行为分割成不同的会话(例如，使用时间戳并将每个用户在一周内的行为视为一个会话)，并在会话级别提供推荐。

用户受他的current perference和他的朋友的short-/long- interests影响，所以提出了一种动态图注意力网络。DGRec由四个模块组成(图2)。

（1）首先是一个递归神经网络(RNN)——用来建模用户的动态兴趣偏好。动态兴趣偏好可以从用户在当前会话（session）中已消费（comsumed）的项目（item）序列中获取。比如当用户在一次绘画中接连购买了靴子、外套等商品，那么明显用户此时的购物偏好为衣物类型，这种动态的兴趣偏好会极大影响用户下一次的消费行为。
（2）用户朋友的兴趣偏好通过其长期兴趣偏好于短期兴趣偏好组合而成。其中长期兴趣偏好反映了一个用户稳定的兴趣所在，可以用一个学习过的individual embedding 进行编码，而短期偏好反映了一个用户在近期（即最近一次会话中）的兴趣漂移，也可以使用RNN编码。
（3）一个图注意力网络GAT——用来建模用户的动态兴趣偏好与朋友的兴趣偏好的交互模式，这是该方法最关键的一部分。自适应地学习出社交网络对用户消费行为的影响的表示向量，也就是学会根据用户当前的兴趣来权衡每个朋友的影响。
（4）用户下一步的消费行为由用户动态兴趣偏好于社交网络影响两部分信息综合决定。该模型通过将用户当前的偏好与他(依赖于环境的)社会影响即他朋友们的influence相结合来产生推荐。

1. 第一步：利用RNN对用户的动态兴趣进行编码表示：
   将近期会话内项目作为序列输入，通过RNN进行编码，最后输出即作为该用户的兴趣表示；
2. 第二步：通过结合friend的short-and-long term interests生成friend的兴趣表示：
   对于短期兴趣，则同上利用RNN进行编码。针对目标用户，他朋友的短期兴趣通过选取current session之前的对话内的项目来表示。对于每个friend k 来说，将它以往会话内的项目作为RNN的序列输入，这里根据经验只选择单个对话（即T时间戳），输出就是friend的短期偏好表示；对于朋友的长期兴趣反映了他的平均兴趣，不分时间所以我们使用单个向量进行表示，即一个用户的嵌入表示；最后将friend的短期偏好和长期偏好串联进行一个非线性转换就得到了最终的friend的偏好表示（结合了其短期和长期偏好的一个表示）
3. 第三步：context dependent social influence 结合目标用户兴趣和他朋友们的兴趣得到一个上下文相关的社会环境影响表示：
   首先构造一个friendship network用来表示用户及其朋友的联系。利用上述的用户和朋友的兴趣编码表示作为特征，通过图内的edge传播实现特征的信息传递，然后对于不同边通过一个注意力网络赋予不同的权重来度量该朋友对目标用户的影响力，最后进行固定迭代次数后就得到了基于目标用户的节点上所产生的特征组合表示，也就是针对目标用户，结合他朋友们的兴趣作为一个上下文相关的社会环境影响表示。
   那么这里首先定义动态的特征图，也就是friendship图。之所以是动态因为对于图中节点的表示构造都是基于上述动态兴趣的表示。 注意力机制就是计算节点与其邻居的相似性，这里使用一个相似性函数，然后再加上节点自身的表示就得到了节点在该层上的特征表示，送入一个非线性函数，输出为下一层特征表示，最后我们堆叠L层这样的特征表示即为每个节点的final representation。
4. 第四步：结合用户自身行为和社会环境影响进行推荐

2.3 视觉推理

推理是人类具有的高阶能力。这里以一个融合了空间信息和语义信息的迭代式视觉推理系统为例。该迭代式的视觉推理架构可以解决一些目标检测的难题。这些目标检测的难题可能是由于数据集标定难度引起，也可能是由于检测框架因此。本推理框架主要由两个部分构成，分别是local module和global graph-reasoning module。其中local module是在卷积网络的基础上引入了记忆机制的局部推理模块，global graph-reasoning module是融合了空间和语义信息的全局推理模块。
推理框架结构图：

图2：推理框架概览。除做预测的普通ConvNets外，框架有两个模块进行推理：一个局部模块（Sec. 3.1），用空间记忆Si，并用另一个ConvNet C推理；一个全局模块（Sec. 3.2），将区域和类作为图中的结点，通过传递结点间信息进行推理。两个模块接收高层和中层的整合信息，交叉互递认知来迭代地工作。最后的预测通过注意力机制整合所有预测结果来生成。

这里的local module是通过使用spatial memory来进行卷积推理的，即局部推理模块以记忆模块 S S S作为输入进行预测，其中记忆模块 S S S用来存储通过卷积网络提取的目标区域的位置特征和图像特征。
为了进行spatial reasoning，借助memory来实现，memory中及保存有high level的类别与位置等特征，又保存有mid level特征。memory的尺寸为 W × H × D W×H×D W×H×D，其中 W W W和 H H H为原图大小的16分之一， D D D取512。推理网络 C C C使用3层3×3的conv和两层4096的fc，同时memory S作为输入，输出特征 f 和注意力 a。memory S这种结构非常有利于spatial reasoning。

给定图像区域 r 的memory更新流程如下，在conv5上进行roi pooling到7×7的尺寸，同时在memory上也进行roi pooling操作到7×7的尺寸，然后memory的更新使用GRU的方式，公式如下。更新完成后resize到W×H的尺寸，更新原始的memory S。

其中 u u u是update gate, z z z是reset gate， σ \sigma σ是激活函数。

global graph-reasoning module主要基于空间特征和语义特征进行推理。空间指的是建立位置上下相邻区域的联系；语义指的是利用外部的知识库建立类别与类别之间的联系。为了综合这两方面信息，采用GNN作为推理模块。图的构成使用两种类型的节点：一种是由所有的区域组成的区域节点，另一种是以所有区域对应的实体作为节点。节点和节点之间的边通过如下3种关系建立：

1. 区域与区域之间通过它们的距离关系建立关联，边的权重由像素距离的核函数归一化值决定；对于有重叠的区域，通过IoU值建立它们之间的关系。
2. 区域与实体之间的关系，根据对区域预测的概率分布（softmax输出），建立与实体之间的关系，边的权重为对应的概率值。
3. 实体与实体之间的关系，来自外部的知识图谱，可以将多种实体关系考虑进来，比如类别从属关系、单复数关系、对称关系等。

相关研究中，实现推理的方案主要分为三种，分别是visual knowledge base、context modeling和relational reasoning。

• visual knowledge base
  该方法往往通过构建视觉图谱的数据集，通过deep learning去结构化学习，并不是真正通过已有知识来进行推理，而是结构化预测。
• context modeling
  该方法类似本文local module，通过图像context来进行卷积推理。
• relational reasoning
  该方法往往利用graph structured data结合神经网络来约束网络关系预测，简单理解可以认为是将概率图模型和神经网络结合。

global graph-reasoning module由三个graph组成，分别是knowledge graph、region graph、assignment graph。

• knowledge graph是通过语义模态构建以类为节点，以关联关系为边的图。
• region graph是通过空间视觉相关性构建以region为节点，以region关系为边的图。
• assignment graph表示region和class之间的映射的图。

通过local module和global graph-reasoning module之间的输出cross-feed来进行迭代推理。

全局推理主要包含两部分，分别是spatial和semantic的reasoning，两部分的推理都通过构建 G = ( N , E ) G=(N, E) G=(N,E)来实现，其中N和E分布表示节点集合与边集合。定义两种类型节点：区域节点 N r N_r Nr​和类别节点 N c N_c Nc​。对于每条边，有三种类型的edge。
首先，针对区域节点 N r N_r Nr​的spatial graph用来编码空间relationships ϵ r − > r \epsilon_{r->r} ϵr−>r​，即节点之间的edge，设计多种类型的边来表征相对位置。我们从诸如“左/右”、“上/下”之类的基本关系开始，并且通过测量两者之间的像素级距离来定义边缘权重。需要说明的是，我们并不是直接使用原始距离x，而是通过距离函数计算得到 k ( x ) = e x p ( − x / Δ ) k(x)=exp(-x/Δ) k(x)=exp(−x/Δ)(其中 Δ = 50 \Delta=50 Δ=50表示带宽)，将其归一化为[0,1]。这样可以使得越接近的区域相关程度越高。然后直接在图的邻接矩阵中使用边缘权重。此外，为了能够有效的解决区域重叠时的分类问题，我们也把用于编码覆盖模式的边( 例如IoU intersection over union, )包含在了其中。
第二，针对 N c N_c Nc​和 N r N_r Nr​的对齐edge，即边是位于区域和类之间的集合，即决定一个区域是否属于某一类。有区域到类别的 ξ r − > c ξ_{r->c} ξr−>c​，也有类别到区域的 ξ c − > r ξ_{c->r} ξc−>r​，也都定义为邻接矩阵，采用soft-max值p来定义连接到所有类别的边缘权重，而不是仅仅计算连接到可能性最高的那一类。这样做是希望它能提供更多的信息，并且提高对错误分类的鲁棒性。
最后，针对 N c N_c Nc​的semantic relationships，使用知识库中的语义关系构造类间关系的集合。即类别到类别的 ξ c − > c ξ_{c->c} ξc−>c​，定义为邻接矩阵。同样，这里可以包括多种类型的边。经典的例子有“is-kind-of”( 例如 “蛋糕”和“食物”)、“is-part-of”(例如“车轮”和“汽车”)、“相似性”( 例如“豹”和“猎豹”)，其中许多都是普遍正确的，因此可以被认为是常识。矩阵的值可以通过commonsense或者自动collected两种方式来定义，上述论述如下图所示。

图3：用多种边在图中直接传递信息的示意图。这里，四个结点连接两个类型的边，每个结点表示一个输入特征向量 m i m_i mi​（整合为 M M M）。权值矩阵 W j W_j Wj​学习为边类型 j j j 以转换输入量。之后邻接矩阵 A j A_j Aj​用来向关联节点传递信息。最后，通过累计所有的边类型并使用激活函数生成输出 G G G。

也就是说，使用GNN来进行推理，区域节点的特征来自卷积网络，实体节点的特征来自预训练的词向量。GNN推理是为了融合空间信息和语义信息对区域进行推理，因此有两条推理路径。一条是区域——区域，它聚合多个区域的特征以得到空间特征；另一条是区域——实体——实体，分为两步，先将区域的特征聚合到实体节点并与实体节点特征融合，然后对不同类型的实体关系进行聚合得到实体的特征，这对应着语义关系。为了得到区域的最终特征，通过实体——区域的关系，将实体携带的语义特征聚合到区域节点上，并与第一条推理路径中得到的空间特征进行融合。整个过程如下：

图4. 在我们的全局推理模块 R R R中使用的两个推理路径。以区域和类输入 M r M_r Mr​和 M c M_c Mc​为例，空间路径(spatial path)直接传递具有区域到区域边缘 ϵ r → r \epsilon_{r→r} ϵr→r​ 的区域图中的信息，而语义路径(semantic path)首先将区域分配给具有 ϵ r → c \epsilon_{r→c} ϵr→c​ 的类，然后将信息传递给具有类-类的边 ϵ c → c \epsilon_{c→c} ϵc→c​ 的其他类，然后传播回来。组合最终输出以生成输出区域特征 G r G_r Gr​
首先，计算spatial path，如下公式
G r s p a t i a l p a t h = ∑ e ∈ ϵ r → r A e M r W e G_r^{spatial path}=\sum_{e\in \epsilon_{r\rightarrow r}}A_eM_rW_e Grspatialpath​=e∈ϵr→r​∑​Ae​Mr​We​
然后，计算semantic path，如下公式
G c s e m a n t i c p a t h = ∑ e ∈ ϵ c → c A e σ ( A e r → c M r W e r → c + M c W c ) W e G_c^{semantic path} = \sum_{e\in \epsilon_{c\rightarrow c}}A_e\sigma(A_{e_{r\rightarrow c}}M_rW_{e_{r\rightarrow c}}+M_cW_c)W_e Gcsemanticpath​=e∈ϵc→c​∑​Ae​σ(Aer→c​​Mr​Wer→c​​+Mc​Wc​)We​
最后，计算合并输出，如下公式：
G r = σ ( G r s p a t i a l + σ ( A e c → r G c s e m a n t i c W e c → r ) ) G_r=\sigma(G_r^{spatial}+\sigma(A_{e_{c\rightarrow r}}G_c^{semantic}W_{e_{c\rightarrow r}})) Gr​=σ(Grspatial​+σ(Aec→r​​Gcsemantic​Wec→r​​))

推理不是一步到位的，需要迭代式的。推理的关键是通过迭代方式来估计，为了实现迭代的信息传递，论文中使用显式memory来实现，局部推理和全局推理使用不同的记忆模块S和M，memory存储之前迭代结果（这和跟踪的template相似，这样说来跟踪就是通过memory来进行推理适应目标变化）。local module使用空间memory S，通过卷积推理模块C来生成特征f，而global graph-reasoning module使用没有空间结构特征的memory M，通过推理模块R来生成特征 f。使用新产生的 f 来分别更新S和M。

为了使两个模块推理相互补充，强制使用cross-feed方式合并两个模块特征来进行迭代推理，推理之后memory使用GRU方式进行更新。

另外模型引入了注意力机制，以便融合当前预测值与来自其他迭代过程产生的预测值。可以修改local module和global graph-reasoning module的预测输出，使其生成attention的预测a，相当于两种module分别预测特征 f 和注意力a。对各个迭代阶段的特征进行融合，一共有N=2I+1个特征，分别来自plain ConvNet、local和global模块，公式如下:

对于Loss而言，整个推理框架是端到端的，loss分为四个部分，分别是plain ConvNet loss、local module loss、global module loss以及最终预测的attention loss。为了使训练能够针对困难样本学习，使用re-weight方法来增加困难样本权重，因此针对local和global的loss，如下式所示:
L o s s i r = max ⁡ ( 1. − p i − 1 ( r ) , β ) ∑ r ′ max ⁡ ( 1. − p i − 1 ( r ′ ) , β ) log ⁡ ( p i ( r ) ) Loss_{i}r=\frac{\max{(1.-p_{i-1}(r),\beta)}}{\sum_{r'} \max{(1.-p_{i-1}(r'),\beta)}} \log{(p_i(r))} Lossi​r=∑r′​max(1.−pi−1​(r′),β)max(1.−pi−1​(r),β)​log(pi​(r))
其中， r r r表示对应region， p 0 ( r ) p_0(r) p0​(r)表示plain ConvNet， β = 1 β=1 β=1，权重分为均匀分布， β = 0 β=0 β=0，权重分为熵最小分布。

GNN的未来展望

1. 充分适应复杂多变的图数据
2. 在更多推理任务上的应用与学习机制的研究改进
3. 对超大规模图建模的支持

参考资料

1. 《深入浅出图神经网络：GNN原理解析》
2. 动态图边卷积网络DGCNN(EdgeConv)
3. DGRec: 基于会话的基于动态图注意网络的社会推荐
4. 【论文笔记】Iterative Visual Reasoning Beyond Convolutions
5. Iterative Visual Reasoning Beyond Convolutions