登录注册写文章

图神经网络

墨染青clothing

图神经网络

推荐使用网址：https://www.dgl.ai/

介绍

图神经网络【图 + 神经网络】
- 神经网络：https://www.jianshu.com/p/1bad4546f341
  - 输入层
  - 隐含层
  - 输出层
  神经网络

图：同数据结构中的图
- 节点
- 边
  
  image.png

最终目的：
尝试将图作为输入，插入到神经网络中
为什么需要GNN
因为我们生活中许多数据并不是欧式距离（图片，文本），而是非欧式距离（分子结构图）
- 检测分子是否会突变
- 生成我们所需要的分子（适用于解决新型冠状病毒药物的分子）
需要解决的问题
- 如何充分利用结构和关系去帮助我们的模型？
- 图太大的情况下，怎么办？
- 没有所有数据的标签应该怎么办？
案例

一种图
- 带标注的节点远远小于无标签节点的个数
  - 选取一个未知标签的点
  - 随机选取 n 个邻接节点
  - 根据邻接节点的种类对无标签样本进行分类
两种解决方法：
- 将卷积的概念扩展到图上 --> 空间卷积
- 使用信号处理的卷积方式 --> 谱卷积

路程图

路程图

路程图

任务，数据集以及基准

任务：
- 半监督节点分类
- 回归
- 图分类
- 图表示学习
- 链接预测
数据集：
- CORA：引用网络，2.7k nodes + 5.4k links
- TU-MUTAG: 平均节点为18个的188个分子
基准：

实验结果1

实验结果2

实验结果3

实验结果4

实验结果5

实验结果6

实验结果7

基于空间的 GCN

卷积：

欧式卷积
图卷积：

图卷积
- 聚合：用邻居特征更新下一层的 hidden state｛使用0， 2， 4节点更新3｝
- 集合：把所有节点的特征集合起来代表整个图
方法1：NN4G
- NN4G 聚合图以及解释
NN4G的聚合
- 首先对输入层的各个节点做类似与 Embedding 的处理，得到 Hidden layer 0
- 然后使用如图方式对节点进行更新得到下一层
NN4G 集合图以及解释

NN4G的集合
- 得到每一层的节点的均值
- 对每层的均值再次进行加权处理得到最终结果
方法2：DCNN(Diffusion-Convolution Neural Network)
- DCNN 聚合图以及解释
  
  DCNN 聚合图
  - 以最下面的图为基准
  - 对于 Hidden state 0，计算出与所选节点距离为1的特征的和的平均，得到各个节点的特征 $H^0$ [ $H^0$ 是由Hidden state 0所有节点组成的矩阵]{对于节点3，距离为1的节点有0， 2， 4}
  - 对于 Hidden sate 1，计算出与所选节点距离为2的特征的和的平均，得到各个节点的特征 $H^1$ [ $H^1$ 是由Hidden state 1所有节点组成的矩阵]｛对于节点3，距离为2的节点有1， 3｝
  - 以此类推，可以得到多个上述的矩阵
  - 将得到的矩阵按照如图形式表示
- DCNN 集合图以及解释

DCNN集合图

- 根据聚合得到的结果，将其表示出来
- 对各个特征进行加权得到最终结果【图中显示的是得到第一个节点的feature】

方法3：DGC（Diffusion Graph Convolution）
- 聚合方式与 DCNN 类似
- DGC 集合图以及解释
  
  DGC集合图
  - 处理方式与 DCNN 不同，其将得到的结果进行累加
  - 然后对其进行加权，得到最终结果
方法4：MoNET（Mixture Model Networks）
- 方式
  - 定义一个节点距离的度量
  - 使用权值相加(平均)代替简单的相加(平均)
    
    MoNET
  - u 是距离度量 $u(x, y)$ 指的是邻接点与自身节点组成的值
  - 根据 u 的值得到各个节点的权值
方法5：GraphSAGE
- 方式
  - 取样并且聚合
  - 可以使用转导设置与引导设置进行工作
  - 从邻居学习嵌入节点特征
- 算法:
  
  GraphSAGE 算法
- 过程：
  
  过程
方法6：GAT
- 步骤：
  
  步骤
- 聚合
  
  聚合
  - 学习一个 f 计算所有节点的重要性
  - 使用图中公式更新所有的节点
方法7：GIN(Graph Isomorphism Netwrk)

GIN 可解释模型
- 公式如图
- 使用求和
- 使用MLP代替第一层

图信号处理以及基于谱的 GCN

基本思想：

基本思想
- 图解：
  - 首先将图空间中的原始图与 Filte 都进行傅里叶转换，将其转换到傅里叶空间上
  - 然后对转换的结果进行相乘处理，得到傅里叶空间中的结果
  - 最后将得到的结果进行反傅里叶转换，将傅里叶空间中的结果转换到图空间中
谱图理论：
- 图： $G = (V, E), N = |V|$ ，其中V指的是节点，E指的是边，N为节点的个数
- 邻接矩阵（权值矩阵）： $A \in R^{N \times N}$ , $A_{i,j }= \begin{cases} 0 & 如果 e_{i,j} \notin E \\ w(i,j)& 其他 \\ \end{cases}$
- 本部分只考虑无向图 $\rightarrow$ 邻接矩阵 $A$ 是对称的
- 度矩阵： $D \in R^{N \times N}$ , 下面d(i)指的是邻接矩阵中第i行的和， $D_{i,j }= \begin{cases} d(i) & 如果 i = j \\ 0 & 其他 \\ \end{cases}$
- 信号函数： $f:C \rightarrow R^N$ , 比如 $f(i)$ 表示节点 $i$ 的信号
  
  节点信号图
图拉普拉斯定理
- 图拉普拉斯 $L = D - A, L \geq 0 \rightarrow$ 半正定
- $L$ 是对称的（对于无向图）
- $L = U \Lambda U^T$ （谱合成）
  
  L的表示
- $\Lambda = diag(\lambda_0, ..., \lambda_{N-1}) \in R^{N \times N}$
  - $U = [u_0, ..., u_{N-1}] \in R^{N \times N} \rightarrow$ 正交化
- $\lambda_l$ 是频率, $u_l$ 是对应于 $\lambda_l$ 的基

对于图拉普拉斯定理的一个图表示：

图例

符号解释
- D 为度数矩阵
- A 为邻接矩阵
- L = D - A
- 根据得到的L计算出特征值与特征向量，即 $\Lambda$ 与 $U$
图信号表示结果：

图信号表示
离散状态下的图理论：

离散时间傅里叶基
解释：【为什么 $\Lambda$ 是频率 $u$ 是基？】
- 节点频率
  
  频率解释
能量差推导
- 特例
  
  特例
  - $\lambda$ 越大，说明某节点左右的信号之差越大

图的计算

时域到频域的转换

时域到频域
频域到时域的转换

频域到时域

Filter 的计算

时域到频域的转换

时域到频域

频域到时域的转换

频域到时域

反傅里叶转换

过程1

过程2

- 即需要学习一个函数

g_\theta(*)

,函数不同得到的复杂度不同

存在的两个问题

复杂度太大
不是局部化

谱模型

ChebNet 【切比雪夫】

ChebNet
- 存在的问题：时间复杂度太大： $O(N^2)$
- 解决方法：
  
  解决时间复杂度
  
  对上述参数进行更换
  
  更换结果
  
  在黄色箭头后对函数进行变换的目的是方便计算

最终计算方式：

公式推导1

公式推导2

GCN：
公式推导：

公式推导1

公式推导2

解决GCN中性能较低的方法：使用DropEdge

总结

学习一个Filter的参数，即 $g_\theta(*)$ 中的 $\theta$ ，可以选择多个Filter（类似于卷积中的多个 channel）

图生成

基于VAE的模型：一步生成一整个图

基于VAE的模型
基于GAN的模型：一步生成一整个图

基于GAN的模型

基于自回归的模型：一步生成节点和边

自回归

用于 NLP 的 GNN

Semanic Roles Labeling

图解1

图解2

事件检测
文档时间戳
命名实体识别
关系提取
知识图谱

总结

总结图

最后编辑于：2020.10.29 09:09:25

©著作权归作者所有,转载或内容合作请联系作者

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 212,294评论 6赞 493
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 90,493评论 3赞 385
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 157,790评论 0赞 348
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 56,595评论 1赞 284
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 65,718评论 6赞 386
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 49,906评论 1赞 290
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 39,053评论 3赞 410
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 37,797评论 0赞 268
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 44,250评论 1赞 303
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 36,570评论 2赞 327
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 38,711评论 1赞 341
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 34,388评论 4赞 332
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 40,018评论 3赞 316
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 30,796评论 0赞 21
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 32,023评论 1赞 266
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 46,461评论 2赞 360
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 43,595评论 2赞 350

赞1赞

赞赏

手机看全文