数据结构第5版上机实验题 已知一个图的连接如下？

来源：蜘蛛抓取(WebSpider) 时间：2023-07-01 05:39 标签： 数据结构第5版上机实验题
一、图的定义关于图的定义，维基百科里给了一个描述性的定义：是用于表示物体与物体之间存在某种关系的结构。具体而言，图是由若干给定的节点以及连接两点的线所构成的一种数据结构。最简单的无向无权图的定义如下：对于给定一个图G，G=（V，E)，其中V表示图中节点的集合，E表示边的集合。下面举例说明图的定义以及保留图结构信息的相关矩阵：图1如图1所示，一张图需要保存两个信息：一个是节点本身的特征信息，由特征矩阵X来表示，每个行向量即每个节点的特征；另一个是图的结构信息，由邻接矩阵A来表示。以图1举例说明，将每个节点进行编号之后，邻接矩阵A是一个6×6的矩阵，其中每个元素Aij的取值取决于节点i和节点j之间是否有连边，有则取1，反之取0。接下来介绍度矩阵和不同形式的拉普拉斯矩阵：图2如图2所示，D是度矩阵，为对角矩阵，矩阵里的每个非零元素表示每个节点的度，也就是与该节点存在连边的节点的数量。D之后是三种拉普拉斯矩阵。第一种是普通的拉普拉斯矩阵；第二种为随机游走的拉普拉斯矩阵，特点是对角元素为1，且每一行的元素之和为0；第三种是对称归一化的拉普拉斯矩阵，其特点是对角元素为1，非对角上非0元素的分母是对应两个节点的度的几何平均数。二、图的分类针对图的节点和边的不同性质，可以将图作不同的区分。1. 简单图与多重图如图的定义一节中所述的图，即为简单图，一对节点之间只能最多只能存在一条边，而一对节点之间可以存在多条边的被称为多重图。2. 有向图与无向图边为有方向的图为有向图，边没有方向的图为无向图。3. 加权图与无权图边为有权重的图为加权图，也叫赋权图，边不含有权重信息的图为无权图。4. 同构图与异构图节点和边的至少有两种或者两种以上类型的图称为异构图，节点和边只有一种类型的图称为同构图。5. 静态图与动态图不含有时间信息的图为静态图，携带有时间信息的图为动态图。三、图的基本任务目前比较常见的图学习的任务主要是以下三个：1. 节点分类节点分类是图神经网络最重要也应用最广泛的任务，即根据已知类别的节点对未知类别的节点分类。2. 链路预测针对两个节点之间是否存在连边进行预测。3. 图分类通过计算节点、边和图的状态综合产生最终输出标签来预测图的类别。三、图神经网络的几种常见模型（一）图卷积神经网络图卷积神经网络的方法顾名思义，受卷积神经网络启发而来，但是卷积神经网络所处理的图像数据为欧几里得数据，而图数据为非欧式数据，即每个节点的邻居的数量并不固定。因此直接把卷积神经网络照搬过来使用是不现实的。根据如何处理这样的问题，图卷积神经网络又主要分为两种模式，一种是空域卷积，一种是谱域卷积。1. 空域卷积空域卷积通过对邻居采样等方式将非欧式结构数据转化为欧式结构数据，再按照普通的卷积神经网络的方式来处理。以下图的PATCHY-SAN模型为例，其核心思路就选择节点序列、遍历邻居节点（只粗略选择一阶二阶）、标准化子图（排序以得到排列整齐的结果）、创建局部感受野（选择邻居节点、裁剪多余节点或使用虚拟节点进行填充）、按照卷积神经网络处理。图32.谱域卷积基于谱域的图卷积神经网络的思路是以图的拉普拉斯矩阵的特征向量为基函数，通过傅里叶变换将卷积核和数据都转换到谱域上进行卷积操作，再通过傅里叶逆变换转回到空域中得到最后的结果，如图4所示：图4其次是针对图卷积的卷积核处理的三种方式，如图5所示：图5如图5所示，GC1是直接将转换到谱域的卷积核初始化为可训练的参数，GC2是将谱域的卷积核的函数使用多项式代替，再以切比雪夫多项式的K阶近似进行截断，GC3是在GC2的基础上将K设置为1得到的。通用的（Graph Convolutional Network）GCN基本上是在GC3的基础上堆叠起来的。因此GCN的传播公式如下：一个两层的GCN的示意图如图6所示：图62. 图注意力机制基于谱域的GCN虽然成为图深度学习的重要方向，但是它还存在着两个明显的问题，其一是对于同一阶邻居的节点“一视同仁”，不能区别对待，忽略了同一阶邻居对于目标节点的影响也不尽相同的情况；其二是GCN是直推式学习，训练时需要将整张图都输入，对于显存需求高，训练耗时长。针对以上两个问题，图注意力机制机制（Graph Attention Network）应运而生。图注意力机制核心思路如图7：图7首先，对所有顶点的应用一个共享权重的线下变换和self-attention来计算attention系数：其次，使用softmax函数进行归一化处理，得到注意力分数：即：最后再使用注意力得分对相应的邻居节点进行加权，并得到每个节点的最终输出：使用多头注意力机制，得到表达式如下：对于最后一层非线性层：3. 动态图神经网络关于动态图，即边有时间信息的图，目前比较常见的处理思路是两种，一种是在时序上对动态网络等时间间隔取快照，从而得到一组离散序列，见图8；另一种是记录边的所有变化，见图9。图8图9目前常见的方法主要集中在第一种在时序上对动态网络取快照的方法，一种常见且核心的思路就是将GCN与循环神经网络结合起来，利用GCN来获取每个静态图上的拓扑结构的信息，再利用循环神经网络来获取时序上的信息。下面介绍相关的两个模型：（1）EvolveGCNEvolveGCN就是一种很好的融合GCN和循环神经网络的方式，如图10所示，它巧妙地避开了先使用GCN分别训练每个时刻的静态图再全部扔进循环神经网络来预测的高复杂度操作，直接使用LSTM或GRU来表示得到GCN的权重参数W，极大地减少了内存和时间的消耗。图10（2）STGCNSTGCN针对交通数据集，提出如图11的一种基于时空图的交通流预测模型，核心就是避开上述的GCN+RNN的思路，而是使用两个时空卷积块加一个输出层来预测，其中时空卷积块是由两个时间门控卷积块夹一个空间图卷积块组成。使用空间图卷积块，即GCN来提取空间的特征，使用时间门控图卷积，即门控循环单元（GLU）来提取时间上的特征，最终的实验结果也证明了方法的有效性。图114.图自编码器及其它按照A Comprehensive Survey on Graph Neural Networks（链接地址：https://arxiv.org/abs/1901.00596）文章的分类，还有图自编码器。相关内容可以参照《图自编码器的起源和应用》这篇文章（https://zhuanlan.zhihu.com/p/114914664）。也可参考图神经网络综述Graph Neural Networks: A Review of Methods and Applications，将图神经网络按照图的类别、训练方法和传播步骤的不同作为划分依据，结果如图12.图12五、图神经网络的学习资料1. 数据集：斯坦福大型网络数据集： https://snap.stanford.edu/data/OGB数据集: https://ogb.stanford.edu/docs/dataset_overview/KONECT数据集：http://konect.cc/2. 文档：PYG文档：https://pytorch-geometric.readthedocs.io/en/latest/index.htmlDGL中文文档：https://docs.dgl.ai/guide_cn/index.html

我要回帖

更多关于 数据结构第5版上机实验题 的文章

 

随机推荐