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

作者在图运算中尝试用卷积神经网络来解决图的特征可视化问题,便于了解图的结构特征。其原理用w个固定大小(size=k)的子图来表示输入的图,再将这w个子图规范化后,生成一个w*k维的向量,作为传统CNN的输入进行学习。其实就是做了一个从图到向量的映射的一个预处理过程。其中的图结构即可以是有向图,也可以是无向图。而且图的顶点或边的特征,可以同时有离散和连续的特征。
展开查看详情

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