建网站赚钱 知乎,app商城开发网站建设,做英文网站网站犯法吗,简单大气网站文章目录 一、为什么需要图神经网络#xff1f;二、图的定义1.图的定义和种类2.一些关于图的重要概念2.1 子图2.2 连通图2.3 顶点的度、入度和出度2.4 边的权和网2.5 稠密图、稀疏图 3.图的存储结构3.1 邻接矩阵3.2 邻接表3.3 边集数组3.4 邻接多重表3.5 十字链表3.6 链式前向… 文章目录 一、为什么需要图神经网络二、图的定义1.图的定义和种类2.一些关于图的重要概念2.1 子图2.2 连通图2.3 顶点的度、入度和出度2.4 边的权和网2.5 稠密图、稀疏图 3.图的存储结构3.1 邻接矩阵3.2 邻接表3.3 边集数组3.4 邻接多重表3.5 十字链表3.6 链式前向星 三、图神经网络类别 一、为什么需要图神经网络
随着机器学习、深度学习的发展语音、图像、自然语言处理逐渐取得了很大的突破然而语音、图像、文本都是很简单的序列或者网格数据是很结构化的数据深度学习很善于处理该种类型的数据图1。 然而现实世界中并不是所有的事物都可以表示成一个序列或者一个网格例如社交网络、知识图谱、复杂的文件系统等图2也就是说很多事物都是非结构化的。 相比于简单的文本和图像这种网络类型的非结构化的数据非常复杂处理它的难点包括
图的大小是任意的图的拓扑结构复杂没有像图像一样的空间局部性图没有固定的节点顺序或者说没有一个参考节点图经常是动态图而且包含多模态的特征
那么对于这类数据我们该如何建模呢能否将深度学习进行扩展使得能够建模该类数据呢这些问题促使了图神经网络的出现与发展。
二、图的定义
1.图的定义和种类
图可以用 G ( V , E ) G(V, E) G(V,E)来表示 其中 V V V是顶点或节点的集合 E E E是边的集合 e i j ( v i , v j ) ∈ E e_{ij}(v_i, v_j)∈E eij(vi,vj)∈E则表示从 v i v_i vi指向 v j v_j vj的边有向图或仅表示 v i v_i vi和 v j v_j vj之间的边无向图 N ( v ) { u ∈ V ∣ ( v , u ) ∈ E } N(v) \left\{ u∈V|(v,u)∈E \right\} N(v){u∈V∣(v,u)∈E}表示节点 v v v的邻域
图的种类主要包括有向图、无向图再往下细分这两类又包括简单图、多重图、完全图 简单图 ①不存在重复边;②不存在顶点到自身的边 简单有向图图左简单无向图图右 多重图 和简单图相对图G中某两个结点之间的边数多于一条又允许顶点通过同一条边和自己关联即有自环
完全图 任意两个顶点之间都存在边
完全有向图图左完全无向图图右
2.一些关于图的重要概念
2.1 子图
设有两个图G(V, E)和G’(V’, E’)若V’是V的子集 E’是E的子集则称G’为G的子图若满足V(G’)V(G)的子图G’则称其为G的生成子图。
2.2 连通图
指的是一个图中的每对顶点之间都存在至少一条路径即从图中的任意一个顶点出发都可以通过边的连通性到达图中的任何其他顶点。 连通图可以分为以下几种类型
强连通图Strongly Connected Graph在一个有向图中如果对于图中的任意两个顶点 u 和 v 都存在从 u 到 v 和从 v 到 u 的有向路径那么该图是强连通图无向连通图Connected Graph在一个无向图中如果对于图中的任意两个顶点 u 和 v 都存在一条无向路径那么该图是无向连通图弱连通图Weakly Connected Graph在一个有向图中如果将有向边的方向忽略将其视为无向边后得到的无向图是连通图那么该图是弱连通图。生成树Tree生成树是针对无向图的它没有回路环路。连通图的生成树就是包含图中全部顶点的一个极小连通子图。生成森林Forest生成森林是针对非连通图的非连通图可分解为多个连通分量而每个连通分量又各自对应多个生成树。 强连通图无向连通图强连通图弱连通图 有向树一个顶点的入度为0、其余顶点的入度均为1的有向图称为有向树右图 非连通图左图生成森林右图
2.3 顶点的度、入度和出度
图中每个顶点的度定义为以该项点为一个端点的边的数目。
对于无向图顶点v的度是指依附于该顶点的边的条数记为TD(v)对于有向图,顶点v的度分为入度和出度,入度是以顶点v vv为终点的有向边的数目记为ID(v); 而出度是以顶点v为起点的有向边的数目记为OD(v)。顶点v的度等于其入度和出度之和
2.4 边的权和网
在一个图中每条边都可以标上具有某种含义的数值该数值称为该边的权值。这种边上带有权值的图称为带权图也称网
2.5 稠密图、稀疏图
边数很少的图称为稀疏图反之称为稠密图。稀疏和稠密本身是模糊的概念稀疏图和稠密图常常是相对而言的。一般当图G满足 ∣ E ∣ ∣ V ∣ l o g ∣ V ∣ |E| |V|log|V| ∣E∣∣V∣log∣V∣时可以将G视为稀疏图当图G满足 ∣ E ∣ |E| ∣E∣接近 ∣ V 2 ∣ |V^2| ∣V2∣时可以将G视为稠密图
3.图的存储结构
图的表示包括邻接表、邻接矩阵、边集数组、邻接多重表、十字链表、链式前向星等每种图的表示都有不同的用处需要根据实际需求选择。 其中比较标准和常规的表示方法有邻接表、邻接矩阵和边集数组这三种表示法都即可以表示无向图也可以表示有向图。特殊一点的包括邻接多重表、十字链表和链式前向星。
邻接链表通常用来表示稀疏图而邻接矩阵通常用来表示稠密图另外如果需要快速判断任意两个结点之间是否有边相连可能也需要使用邻接矩阵表示法邻接表 存各种图都很适合除非有特殊需求如需要快速查询一条边是否存在且点数较少可以使用邻接矩阵。尤其适用于需要对一个点的所有出边进行排序的场合。邻接表的一个潜在缺陷是无法快速判断一条边(u, v)是否是图中的一条边唯一的办法是在邻接链表Adj[u]中搜索结点v。邻接表还衍生出了一种逆邻接表因为邻接表统计出度的效率较高而入度需要遍历整个表才可以统计出来而逆邻接表不需要遍历直接就可以统计出每个结点的出度这正好和邻接表相反。 邻接矩阵 邻接表的一个缺陷是无法快速判断一条边(u, v)是否是图中的一条边。而邻接矩阵克服了这个缺点但付出的代价是更高的空间复杂度。邻接矩阵只适用于没有重边或重边可以忽略的情况。其最显著的优点是可以 O ( 1 ) O(1) O(1)查询一条边是否存在。由于邻接矩阵在稀疏图上效率很低尤其是在点数较多的图上空间无法承受所以一般只会在稠密图上使用邻接矩阵。空间复杂度高 边集数组 由于直接存边的遍历效率低下一般不用于遍历图。主要见到的就是在最小生成树的 Kruskal 算法中由于需要将边按边权排序需要直接存边。在有时候有可能需要多次建图如建一遍原图建一遍反图此时既可以使用多个其它数据结构来同时存储多张图也可以将边直接存下来需要重新建图时利用直接存下的边来建图。 邻接多重表 邻接多重表用于表示无向图邻接表虽然已经能够很好地表示无向图了但是无向图访问或者删除一条边(Vi,Vj)时需要同时访问两个链表i和j并分别找到对应的边结点这给针对图的边的操作标记或删除带来不便利。邻接多重表因此而演变过来的。当一个无向图需要频繁的修改时邻接表表示法需要修改边两侧的结点对应的信息而多重邻接表可以只修改一次计算量节省了一半。 十字链表 十字链表用来表示有向图十字链表是结合了邻接表和逆邻接表于一体的表示方法用来表示有向图综合了两种表示方法的优点缺点是表示起来更加复杂。 链式前向星 链式前向星是一种静态链表存储用边集数组和邻接表相结合可以快速访问一个顶点的所有邻接点在算法竞赛中广泛使用。
3.1 邻接矩阵
图的邻接矩阵(Adjacency Matrix) 存储方式是用两个数组来表示图。一个一维数组存储图中顶点信息一个二维数组(称为邻接矩阵)存储图中的边或弧的信息 下图是一个无向图和它的邻接矩阵 下图是一个有向图和它的邻接矩阵 下图是一个有向带权图和它的邻接矩阵
3.2 邻接表
邻接表链表表示由一个包含V条链表的数组Adj所构成每个结点都有一条链表存储与其相连的节点 无向图的邻接表的实例如下图所示 有向图的邻接表的实例如下图所示 带权图的邻接表的实例如下图所示
3.3 边集数组
使用一个数组来存边数组中的每个元素都包含一条边的起点与终点带边权的图还包含边权。或者使用多个数组分别存起点终点和边权。
3.4 邻接多重表
邻接多重表中无向图中的每一个顶点分配一个顶点结点所有顶点结点构成一个顶点数组 a d j m u l t i L i s t [ n u m ] adjmultiList[num] adjmultiList[num]。另外每条边也分配一个边节点。 以下是顶点数组的展示 以下是边节点的展示 以下是邻接多重表实例的展示
3.5 十字链表
十字链表是为了便于求得图中顶点的度出度和入度而提出来的。它是综合邻接表和逆邻接表形式的一种链式存储结构。其存储方式和邻接多重表类似。 以下是顶点数组的展示 以下是边节点的展示 3.6 链式前向星
链式前向星是一种静态链表存储用边集数组和邻接表相结合可以快速访问一个顶点的所有邻接点在算法竞赛中广泛使用。
三、图神经网络类别
目前最先进的图神经网络分为四类即递归图神经网络、卷积图神经网络、图自动编码器和时空图神经网络
递归图神经网络Recurrent Graph Neural Networks, RecGNN大多是图神经网络的先驱作品。RecGNN旨在学习具有递归神经结构的节点表示。他们假设图中的一个节点不断地与其邻居交换信息/消息直到达到稳定的平衡RecGNN在概念上很重要并启发了后来对卷积图神经网络的研究。特别是基于空间的卷积图神经网络就继承了消息传递的思想。
卷积图神经网络Convolutional Graph Neural Networks, ConvGNNs将卷积运算从网格数据推广到图数据。主要思想是通过聚合节点 v v v自身的特征 x v x_v xv和邻居的特征 x u x_u xu来生成节点v的表示其中 u ∈ N v u∈Nv u∈Nv。与RecGNN不同ConvGNN堆叠多个图卷积层来提取高级节点表示。ConvGNN在建立许多其他复杂的GNN模型中发挥着核心作用可用于节点分类和图分类如下图所示 右图具有多个图卷积层的ConvGNN。图卷积层通过聚合来自其邻居的特征信息来封装每个节点的隐藏表示。在特征聚合之后将非线性变换应用于结果输出。 通过堆叠多层每个节点的最终隐藏表示从另一个邻域接收消息 左图图卷积层之后是池化层以将图粗化成子图使得粗化图上的节点表示表示表示更高的图级表示。读出层通过取子图的隐藏表示的和/均值来总结最终的图表示
图自动编码器Graph Autoencoders, GAE是一种无监督的学习框架它将节点/图编码到潜在向量空间中并根据编码的信息重建图数据。GAE用于学习网络嵌入和图生成分布。对于网络嵌入GAE通过重构图的结构信息如图的邻接矩阵来学习潜在节点表示。对于图生成一些方法一步一步地生成图的节点和边而另一些方法一次输出图。下图展示了用于网络嵌入的GAE。 编码器使用图卷积层来获得每个节点的网络嵌入。解码器计算给定网络嵌入的成对距离。 在应用非线性激活函数之后解码器重建图邻接矩阵。通过最小化真实邻接矩阵和重构邻接矩阵之间的差异来训练网络
时空图神经网络Spatial-temporal Graph Neural Networks, STGNN旨在从时空图中学习隐藏模式这在交通速度预测、驾驶员机动预期和人类动作识别等各种应用中变得越来越重要。STGNN的关键思想是同时考虑空间依赖性和时间依赖性。当前的许多方法将图卷积与RNN或CNNs集成以捕获空间依赖性从而对时间依赖性进行建模。下图展示了用于时空图预测的STGNN。 用于时空图预测的STGNN。图卷积层之后是1D-CNN层。图卷积层对A和X(t)进行运算以捕获空间相关性而1D-CNN层沿时间轴X滑动以捕获时间相关性。 输出层是线性变换为每个节点生成预测例如其在下一时间步长的未来值。
