【GCN】图卷积网络初探——基于图(Graph)的傅里叶变换和卷积

【GCN】图卷积网络初探——基于图(Graph)的傅里叶变换和卷积

2018年11月29日 11:50:38 夏至夏至520 阅读数 5980更多

分类专栏: # MachineLearning

版权声明:本文为博主原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接和本声明。

本文链接:https://blog.csdn.net/qq_41727666/article/details/84622965


一、CNN(卷积神经网络)中的离散卷积

推荐阅读:如何通俗易懂地解释卷积?

1、CNN中的离散卷积:共享参数的过滤器

2、CNN中的卷积操作:通过计算中心像素点以及相邻像素点的【加权和】构成【feature map】;
加权系数=卷积核的权重系数

【实例】下式是一个隐藏神经元的输出计算公式,b为偏置,w为5×5的权重向量,a为上一层的激活值,σ()为激活函数。
可以看出,将上一层的5×5=25的神经元(a)加权(w)求和

3、CNN中的卷积目的:空间特征的提取

4、确定卷积核的系数:随机化初值,训练中根据误差函数loss,通过反向传播+梯度下降进行迭代优化。

二、GCN基本概念介绍

(一)图Graph

定义:顶点和边建立的关系拓扑图

(二)研究GCN的原因

1、CNN的【平移不变性】在【非矩阵结构】数据上不适用

2、希望在【拓扑图】上提取空间特征来进行机器学习

3、GCN主要工作:引入可以优化的【卷积参数】

(三)提取【拓扑图】空间特征的两种方式

1、vertex domain(spatial domain):顶点域(空间域)

操作:把每个顶点相邻的neighbors找出来

缺点:每个顶点的neighbors不同,计算处理必须针对每个节点

2、spectral domain:谱域

过程:

(1)定义graph上的Fourier Transformation傅里叶变换

(利用Spectral graph theory,借助图的拉普拉斯矩阵的特征值和特征向量研究图的性质)

(2)定义graph上的convolution卷积

三、图的拉普拉斯矩阵

(一)定义:拉普拉斯矩阵L

L=D−AL=D-AL=D−A
其中,L为Laplacian矩阵;
      D是顶点的度矩阵(对角矩阵),对角线上的元素依次为各个顶点的度(与该顶点相连的边的条数);
      A是图的邻接矩阵。

计算方法实例:

(二)拉普拉斯矩阵L的良好性质

1、是对称矩阵,可以进行谱分解(特征分解),与GCN的spectral domain对应

2、只在【中心节点】和【一阶相连的顶点】这两种位置上有非0元素,其余位置都是0
注:一阶相连就是通过一条边直接相连,如上图中与顶点1一阶相连的顶点为5和2;
二阶相连就是通过两条边相连,如上图中与顶点1二阶相连的顶点为4(1-5-4)、2(1-5-2)、5(1-2-5)、3(1-2-3)

3、可以通过拉普拉斯算子与拉普拉斯矩阵进行类比

(三)拉普拉斯矩阵L的谱分解(特征分解)

1、矩阵L的特征分解定义:将矩阵L分解为由特征值λ和特征向量u表示的矩阵之积

(1)求特征值和特征向量:λ为特征值,u为特征向量,则满足下式:
Lu=λuLu=\lambda uLu=λu

(2)求特征分解:

令 L是一个 N×N 的方阵,且有 N 个线性无关的特征向量 。
这样, L可以被分解为:
L=UΛU−1=U???λ1...λ3???U−1L=U\Lambda U^{-1} =U\begin{pmatrix}\lambda_1& & \\ &...& \\ & & \lambda_3 \end{pmatrix} U^{-1}L=UΛU−1=U???λ1??...?λ3?????U−1
其中,U是N×N方阵,且其第i列为L的特征向量ui,ui为列向量;
U=(u1? ,u2? ,...,un? )U=(\vec{u_1},\vec{u_2},...,\vec{u_n})U=(u1??,u2??,...,un??)
      Λ是对角矩阵,其对角线上的元素为对应的特征值。

2、拉普拉斯矩阵:【半正定】【对称】矩阵
性质:
(1)有n个线性无关的特征向量
(2)特征值非负
(3)特征向量相互正交,即Q为正交矩阵
设拉普拉斯矩阵L中,λi为特征值,ui为特征向量,U为特征向量ui作为列向量组成的方阵,那么拉普拉斯矩阵的谱分解形式为:

四、Graph上的傅里叶变换与卷积

(一)核心工作

把拉普拉斯算子的【特征函数】
变为
Graph对应的拉普拉斯矩阵的【特征向量】

(二)Graph上的傅里叶变换

1、传统傅里叶变换:

2、Graph上的傅里叶变换

  • 拉普拉斯矩阵=离散拉普拉斯算子
  • 拉普拉斯矩阵的【特征向量U】=拉普拉斯算子的【特征函数exp(-iwt)】

仿照上面传统傅里叶定义,得到Graph上的傅里叶变换:

  • i为第i个顶点
  • λl为第l个特征值;ul为第l个特征向量
  • f为待变换函数,f尖为其对应的傅里叶变换,f和f尖与顶点i一一对应

3、Graph上的傅里叶逆变换:

(三)Graph上的卷积

1、传统卷积定理:

  • f为待卷积函数,h为卷积核(根据需要设计)
  • f*h为卷积结果

2、Graph上的卷积:仿照上面定义

  • f为待卷积函数,h为卷积核(根据需要设计)
  • f*h为卷积结果

3、由式(1)可以看出,U为特征向量,f为待卷积函数,重点在于设计含有【可训练】【共享参数】的【卷积核h】
卷积参数就是diag(hˆ(λl))卷积参数就是diag(\hat{h}(\lambda_l))卷积参数就是diag(h^(λl?))

五、深度学习中的GCN

1、第一代GCN:

  • 卷积核:
    diag(hˆ(λl)):diag(θl)diag(\hat{h}(\lambda_l)): diag(\theta_l)diag(h^(λl?)):diag(θl?)
  • output公式:

  • 缺点:有n个参数θn,计算量大

2、第二代GCN:

  • 卷积核:
    hˆ(λl):∑Kj=0αjλjl\hat{h}(\lambda_l):\sum_{j=0}^K \alpha_j\lambda_l^jh^(λl?):j=0∑K?αj?λlj?
  • output公式:

注意到下式:

进而可以导出下式:

  • 经过矩阵变换,简化后的output公式:

3、实例

  • K=1时,对于顶点i,将顶点i以及顶点i的一阶相连顶点(j,k,m,n)的feature值(f函数值)做加权求和,权重就是参数αj,最终输出新的feature值(g函数),为提取得到的空间特征
  • K=2时,对于顶点i,将顶点i以及顶点i的一阶相连顶点、二阶相连顶点的feature值加权求和,输出新的feature值

原文地址:https://www.cnblogs.com/think90/p/11508851.html

时间: 09-08

【GCN】图卷积网络初探——基于图(Graph)的傅里叶变换和卷积的相关文章

CVPR2020论文解读:手绘草图卷积网络语义分割

Sketch GCN: Semantic Sketch Segmentation with Graph Convolutional Networks 论文链接:https://arxiv.org/pdf/2003.00678.pdf 摘要 介绍了一种用于手绘草图语义分割和标注的图形卷积神经网络SketchGCN.我们将输入草图视为二维点集,并将笔划结构信息编码为图形节点/边缘表示.为了预测每个点的标签,我们的SketchGCN使用图卷积和全局分支网络结构来提取笔划内和笔划间的特征.SketchG

卷积网络训练太慢?Yann LeCun:已解决CIFAR-10,目标 ImageNet

卷积网络训练太慢?Yann LeCun:已解决CIFAR-10,目标 ImageNet Kaggle近期举办了一场 关于CIFAR-10数据集的竞赛,该数据集包含有6万个32*32的彩色图像,共分为10种类型,由 Alex Krizhevsky, Vinod Nair和 Geoffrey Hinton收集而来. 很多竞赛选手使用了卷积网络来完成这场竞赛,其中一些在该分类任务中靠着超乎人类能力的表现而得分.在本系列的博客中,我们将会分别采访三位选手和卷积网络之父.Facebook人工智能实验室主任

TCN时间卷积网络——解决LSTM的并发问题

TCN是指时间卷积网络,一种新型的可以用来解决时间序列预测的算法.在这一两年中已有多篇论文提出,但是普遍认为下篇论文是TCN的开端. 论文名称: An Empirical Evaluation of Generic Convolutional and Recurrent Networks for Sequence Modeling 作者:Shaojie Bai 1 J. Zico Kolter 2 Vladlen Koltun 3 自从TCN提出后引起了巨大反响,有人认为 时间卷积网络(TCN)

TensorFlow 中的卷积网络

TensorFlow 中的卷积网络 是时候看一下 TensorFlow 中的卷积神经网络的例子了. 网络的结构跟经典的 CNNs 结构一样,是卷积层,最大池化层和全链接层的混合. 这里你看到的代码与你在 TensorFlow 深度神经网络的代码类似,我们按 CNN 重新组织了结构. 如那一节一样,这里你将会学习如何分解一行一行的代码.你还可以下载代码自己运行. 感谢 Aymeric Damien 提供了这节课的原始 TensorFlow 模型. 现在开看下! 数据集 你从之前的课程中见过这节课的

基于图卷积网络的图深度学习

基于图卷积网络的图深度学习 先简单回顾一下,深度学习到底干成功了哪些事情! 深度学习近些年在语音识别,图片识别,自然语音处理等领域可谓是屡建奇功.ImageNet:是一个计算机视觉系统识别项目, 是目前世界上图像识别最大的数据库,并且被业界熟知. 我们先回顾一下,没有大数据支撑的欧式深度学习技术.对于一个字母"Z"的识别,我们通常是建立一个2D网格(点阵),如果将其中的点连接起来,定义这样的连接方式所形成的就是"Z".然后是用其他字母来测试,这个模型的正确性. 传统

R-FCN:基于区域的全卷积网络来检测物体

http://blog.csdn.net/shadow_guo/article/details/51767036 原文标题为"R-FCN: Object Detection via Region-based Fully Convolutional Networks ",作者代季峰 1,14年毕业的清华博士到微软亚洲研究院的视觉计算组,CVPR 16 两篇一作的会议主持人~ ╰(°▽°)╯ 同时公布了源码~ 2 后面主要内容为原文随便的翻译或概括.必有不紧贴原文原意之处,曲解请指出,否则

[转]基于图的机器学习技术:谷歌众多产品和服务背后的智能

近来机器学习领域实现了很多重大的进展,这些进展让计算机系统具备了解决复杂的真实世界问题的能力.其中,谷歌的机器学习又是怎样的 ? 近来机器学习领域实现了很多重大的进展,这些进展让计算机系统具备了解决复杂的真实世界问题的能力.其中之一是谷歌的大规模的.基于图(graph-based)的机器学习平台,该平台由Google Research的Expander团队打造. 基于图的机器学习支持着你可能每天都在使用的谷歌产品和功能,这项技术是一种强大的工具,可以被用于驱动Inbox的提醒功能和Allo的智能

基于图的关键词抽取

项目研究背景: 在关键词抽取研究中,最常用的一种方法就是通过计算一篇文档中词语的TF-IDF值(term frequency-inverse document frequency),并对它们进行排序选取TopK个作为关键词,这是一种无监督的方法.另外一种方法是通过有监督的方法,通过训练学习一个分类器,将关键词抽取问题转化为对每个词语的二分类问题,从而选择出合适的关键词. 无监督和有监督各有各的优势和缺点:无监督学习,不需要人工标注,训练集合的过程,因此更加方便和快捷:然而监督学习的方法,在进行了

开源、易扩展、方便集成的在线绘图(微服务架构图、网络拓扑图、流程图)工具

一个基于typescript + canvas 实现的开源在线绘图的引擎Topology.采用引擎 + 图形库中间件的思路能够方便.快速的扩展.集成到前端项目.目前暂时实现了基本图形.流程图图形库,能够满足微服务架构图.网络拓扑图和流程图的绘制.后面计划陆续实现活动图/时序图/类图等UML图. 在线体验(因为操作方便问题,暂时没有适配移动端)       产品介绍 为什么重复造轮子 笔者工作中遇到比较多的微服务架构.云资源运维.部署与运维可视化方面的需求 开源.满足自己需求的不多 typescr