卷积神经网络在图中的应用

1 .卷积神经网络在“图”中的应用 —— CNN for Graphs 董思佳 硕士 研究生 Beijing Forest Studio 北京理工大学信息系统及安全对抗实验中心 1 2018 年 8 月 5 日

2 .内容提要 背景简介 基本概念 算法原理 应用总结 参考 文献 2

3 .3 背景简介 CNN for Graphs

4 .背景介绍 深度学习的优势 传统方法 深度学习 深度学习减少了手工提取特征或规则的步骤，从原始数据中自动学习特征（端对端 /end-to-end ）。深度学习框架包括 CNN 、 DBN 、 RNN 等算法， 对于不同问题 ( 图像 、 语音 、 文本 ) ，需要选用不同网络模型才能达到更好效果。 4 手动提取特征 输出 分类器 深度神经网络 输出

5 .背景介绍 CNN 的特点 处理 的图像或者视频数据中像素点（ pixel ）是排列 成很 整齐的 矩阵，即欧几里得结构数据（ Euclidean Structure data ）。 Euclidean data 最显著的特征 就是 具 有 规则的空间结构 ，比如图片是规则的正方形栅 格 （ grid ） ， 语音信号 是 规则的一维序列 。 5

6 .背景介绍 CNN 的局限性 不能有效处理非欧几里得结构数据（ Non Euclidean Structure data ） 。传统的离散卷积在这类数据上无法保持平移不变 性。 Non Euclidean data 最显著的特征就是 不具备 规则的空间结构 。 比如社交多媒体网络（ Social Network ）数据，化学成分（ Chemical Compound ）结构数据，生物基因蛋白（ Protein ）数据，知识图谱（ Knowledge Graphs ）数据等， 这类数据属于图结构的数据（ Graph-structured Data ） 。 6

7 .背景介绍 CNN 处理图结构数据的两种方式： 空间域（ spatial domain ）卷积 即 让图中的节点在空间域中相连、达成层级结构，进而进行 卷积。 谱（ spectral domain ）卷积 即将 卷积网络的滤波器与图信号同时搬移到傅里叶域以后进行处理。 7 《 Semi-supervised classification with graph convolutional networks》 《 Learning Convolutional Neural Networks for Graphs》

8 .8 基本概念 CNN for Graphs

9 .基本概念 什么是图？ 图（ Graph ）是表示对象与对象之间关系的方法。 对象又称节点（ Node ）、顶点（ Vertex ）、实体（ Entity ），它描述的是具体的一件事物。 关系又称边（ edge ）它描述的对象之间的关系。 图分为无向图和有向图。 9

10 .基本概念 无向图 特点：每条边都没有方向 表示方法 1 ： G =(V, E), V 表示节点的集合， E 表示边 集合。 无序 对 (vi ， vj) 和 (vj ， vi) 表示同一条边。 表示 方法 2 ：邻接矩阵（ Adjacent matrix ） 10 V={V0,V1,V2,V3} 、 E={(V0,V1),(V0,V2),(V1,V2),(V1,V3)} V0 V1 V3 V2 V0 V1 V0 V2 V1 V3 V3 V2 0 1 1 0 1 0 0 1 0 1 1 0 1 0 1 0 A ：邻接矩阵

11 .基本概念 有向图 特点： 每条边都有方向 表示方法 1 ： G=(V, E), V 表示节点的集合， E 表示边集合。 < vi ， vj> 表示一条有向边， vi 是边 的起点， vj 是边的终点 。 < vi ， vj> 和 <vj ， vi> 是两条不同的有向边。 表示 方法 2 ：邻接矩阵（ Adjacent matrix ） 11 V={V0,V1,V2,V3} 、 E={<V0,V1>,<V1,V0>,<V2,V0>,<V2,V1>,<V3,V1>} A ：邻接矩阵 V0 V1 V3 V2 V0 V1 V0 V2 V1 V3 V3 V2 0 1 1 0 1 0 1 1 0 0 0 0 0 0 1 0

12 .基本概念 现实场景下的图 在实际研究中，节点与边都有特定的类型，比如连接“用户”与“商品”节点的边，很可能就是“购买”的类型关系。像这样，在构建一个具体业务场景的图时，标识上节点类型与边的类型，这样的图我们称之为图的结构表示（ Graph Schema ），它反应出来的是一种业务上的逻辑抽取。 12

13 .基本概念 现实场景下的图 例：社交网络 13 1 、推荐用户可能感兴趣的 人 2 、推荐用户可能感兴趣的帖子或者 内容 3 、社群发现（通过用户社交关系网络挖掘群体结构 ） 4 、用户画像（地点、兴趣、关系网络 ） ……

14 .基本概念 基本概念 感受野 （ receptive field ）：是 指卷积神经网络每一层输出的特征图（ feature map ）上的像素点在原始图像上映射的区域大小。 步长（ stride ）：表示卷积核在水平方向 和垂直方向每次 的 移动 长度。 14 例 ： 7*7 的 图像，卷积操作的感受野为 3*3 ，步长 为 1 ，卷积核为 3*3 。

15 .基本概念 CNN 在 图像（ Image ） 中的应用 CNN 中的卷积本质上就是利用一个共享参数的过滤器（ kernel ），通过计算中心像素点以及相邻像素点的加权和来 构成特征图（ feature map ）实现 空间特征的 提取。 15

16 .基本概念 CNN 在 图像（ Image ） 中的 应用 例： 4*4 的 图像，卷积操作的感受野为 3*3 ，步长为 1 ，卷积核为 3*3 。 16

17 .17 算法原理 CNN for Graphs

18 .算法原理 PATCHY-SAN (Select-Assemble-Normalize ) 思路 1 . 选出合适 的 节点 ； 2 . 为每一 个 节点 建立 一个邻域 ； 3. 建立 图 表示到 向量 表示的单一映射，保证具有相似的结构特征的 节点 可以被映射到 向量 当中相近的位置。 18 总体 上讲，就是用 w 个 固定大小（ size=k ）的 子图来表示输入 的图，再 将这 w 个 子图规范化后，生成 一个 w*k 维 的向量，作为 传统 CNN 的输入进行 学习。其实就是做了一个 从图到 向量的映射的一个预处理过程 。 其中 的图结构即可以是有向图，也可以是无向图。而且图的顶点或边的特征，可以同时有离散和连续的特征 。

19 .算法原理 步骤 1. 图当中顶点的选择 Node Sequence Selection 2. 找到 节点 的领域 Neighborhood Assembly 3. 图规范化过程 Graph Normalization 4. 卷积网络结构 Convolutional Architecture 19

20 .1 ） Node Sequence Selection 顶点 选择 输入图 G ，定义宽度 w 。 w ：节点个数 / 卷积操作的个数 / 感受野的个数 那么 具体如何 进行节点的选择？ 20

21 .1 ） Node Sequence Selection 那么具体如何进行 nodes 的选择 ？ 根据 图 当中的 节点 的排序标号进行选择 ，主要采取中心性 度量 方法（ centrality ），包括点 度中心性（ Degree Centrality ）、接近中 心性（ Closeness Centrality ） 、中介中 心性 (Between Centrality ) 等。 举例：接近中心性 （ Closeness Centrality ） ，即其余节点到该节点 最短总距离的 倒数 。 21 假设 相邻的两个 node 之间的距离都是 1 。 A ： 4+2*3+3*3+4*1=23 B ： 3+2*4+3*2+4*2=25 A B

22 .2 ） Neighborhood Assembly 22 接下来 对选出来的每一 个 节点 确定 一个 感 受 野以便 进行卷积操作。 但是在 这之前，首先找到每一 个 节点 的邻域 ， 然后 再从当中确定 感 受 野 当中 的 节点 。 假设 感受野 的 大小为 k （ k 即 为 感受野节点 的 个数），那么对于每 一 个节点 可能 存在几 种 情况： 邻域 节点数等于或小于或大于 k 。 选择邻域的方法： 1 、 找直接相邻的节点； 2 、 若不够再增加间接相邻的节点； 3 、 选择后先 全部放在 候选集（ candidate set ）当中 ，在 下一步骤通过 规范化来做最终的选择 。

23 .3 ） Graph Normalization 规范化目的： 假设 步骤 2 中一个 节点 得到一个 包含有 N 个节点的邻 域。那么 N 可能和 k 不相等。因此， 规范化 的过程就是要对 节点 打上排序标签进行选择，并且按照该顺序映射到向量当中 。 23

24 .3 ） Graph Normalization 24 如何打排序标签？ 例：从这 7 个节点中选出 4 个节点会形成一个含有 4 个节点的图的集合。 思路：在 某种标签下，随机从集合当中选择两个图， 计算在 vector 空间的图的距离和在 graph 空间的图的距离的差异的期望，如果这个期望越小那么就表明这个标签越 好。

25 .3 ） Graph Normalization 目标节点的个数为 w ，感受野中节点的个数为 k 节点 的通道数 为 ， 每个通道是一个一维的有序 向量， k 个节点属性值构成了一个输入 通道 边的通道数 （边特征的 个数）， 每个通道是一个二维的 矩阵， k 2 个属性值构成了一个输入通道   25

26 .4 ） Convolutional Architecture 卷积网络结构： 例：使用一个 2 层的卷积神经网络 26

27 .4 ） Convolutional Architecture 卷积网络结构： 例：使用一个 2 层的卷积神经网络 27

28 .4 ） Convolutional Architecture 卷积网络结构： 例：使用一个 2 层的卷积神经网络 28

29 .4 ） Convolutional Architecture 卷积网络结构： 例：使用一个 2 层的卷积神经网络 29