【补充】图神经网络前传——图论

2024-05-01 10:04

本文主要是介绍【补充】图神经网络前传——图论,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

本文作为对图神经网络的补充。主要内容是看书。

仅包含Introduction to Graph Theory前五章以及其他相关书籍的相关内容(如果后续在实践中发现前五章不够,会补上剩余内容)

引入

什么是图?

如上图所示的路线图和电路图都可以使用点和线表示,如下图:

图中的点P,Q,R,S和T被称为顶点(vertices),而图中的线被称为边(edges)。整张图被称为图(graph)。注意PS和QT两条线相交点并不是顶点,参考前面的图,这里的“焦点”并不是路口或者是两条电线教会的地方。

顶点的度(degree),是以该顶点为终点的边的个数,比如图中的顶点Q的度是4(PQ,TQ,SQ,RQ)。

上面这张图也可以表示其他的情况,比如,P,Q,R,S和T表示足球队,边代表队伍之间的比赛,那么队伍P就和Q,S和T三个队伍比赛过,但是没有与队伍R比过赛。这种情况下,度就可以理解为对应队伍参加比赛的数目。

如果我们把PS边扯到矩形PQST外面,得到的图(⬇️)荏苒可以告诉我们P S两个地点之间有一条路/P S之间连了一条电线/P S两个足球队之间进行了比赛。我们丢失的信息可能是路线的长度或者电线是直的。

 因此,图仅仅代表点之间是如何连接的,任何测量得到的属性都不重要。因此虽然PS被扯到外面了,但是与前面的图是同一个图。

类似的,即使⬆️这张图长得完全不像了,但是仍然是同一张图。

现在,我们假设QS、ST道路拥堵,我们需要建造更多的路来缓解交通压力,如下图:

此时,QS、ST之间的边被称为多重边(multiple edges)。

现在,我们有一辆车要在P点停车(感觉这里说做U turn更好理解),此时在P点加一条边,此时这条边被称为自环(loop)

没有loop以及multiple edges的图被称为简单图(simple graphs)

将道路设置为单行道,即为有向图(directed graphs,简写为digraphs),如上图所示。单行道的方向使用箭头表示。

许多图论都包含了各种各样的“移动方式”,即从一个顶点移动到另一个顶点。比如从P点到Q点,我们可以P —> Q —> R,P —> S —> Q —> T —> S —> R,前者走了两步,后者走了五步。如果同一个顶点出现次数不超过一次,则称这种“移动方式”为一条路(path)。

P —> T —> S —> R为一条路

Q —> S —> T —> Q是一个环

这里关于Eulerian和Hamiltonian graph的描述不是很清楚,采用其他材料补充。

在访问每个顶点时沿着每条边正好走一次的回路被称为欧拉回路(Eulerian circuit),这个图被称为欧拉图(Eulerian graph)(死去的记忆开始攻击我了)

如果连通图中存在闭合遍历,则该图称为哈密顿图(Hamiltonian Graph),除了根顶点或起始顶点外,该图的每个顶点都经过一次。哈密顿图的另一个定义是如果有一个连通图,它包含哈密顿电路,那么这个图就被称为哈密顿图。

Certain graph problems deal with finding a path between two vertices such that each edge is traversed exactly once, or finding a path between two vertices while visiting each vertex exactly once. These paths are better known as Euler path and Hamiltonian path respectively.

Mathematics | Euler and Hamiltonian Paths - GeeksforGeeks

有些图有两个或者更多的部分组成->非连通图

任意两个顶点之间都连了一条路径->连通图

如果每一对顶点之间只连了一条边->称为树(tree)

可以看出树是连通图,但是没有环

图的边没有交叉的图称为平面图(planar graph)

(在第6章中介绍的是染色问题,提到了高中的时候用到过的四色定理,考虑有空去看看~)

定义

 如上图,简单图G的顶点集合为V(G),{u, v, w, z},边的集合为E(G),包含:uv, uw, vw, wz

在任何简单图中,最多有一条边连接给定的一对顶点。

简单图的很多结论可以推广到更general的图中(即使加上环和多重边)

图:G = (V, E)

其中V表示顶点的集合,E是未排序的顶点对的集合,E中的元素即为边。

相邻(adjacent):假设u v是图G = (V, E)的两个顶点,若有\{u, v\}\in E,则称u v是相邻的,即\{u, v\}是图G中的一条边,称u为v的邻居(neighbour)。

关联(incident):若顶点v和边e的关系为v\in e,则称顶点v和边e关联。

自环(loop):(v,v), v\in V
这里的(v,v)表示边连接的两个顶点是同一个

多重边(multiple edge):当一条边e = (u,v)在边的集合E中出现多次,称为多重边

简单图:没有环&多重边

同构(Isomorphism)

G_1 G_2之间的顶点有一一对应关系,且G_1中连接任意两个顶点的边的个数与G_2中对应相等,则称G_1 G_2同构。

推论:G_1与G_2同构,则G_2与G_1同构(可逆)

G_1与G_2同构,G_2与G_3同构,则G_1与G_3同构(传递)

labelled graph和unlabelled graph(直接看图,上面的是labelled,下面是unlabelled)

连通(connectedness)

我们可以把两个图合并在一起,得到一个更大的图,假设现在有两个图G_1 = (V(G_1), E(G_1))以及图G_2 = (V(G_2), E(G_2))并且两个图的顶点的集合(V(G_1)V(G_2))是不相连的,则图的unionG_1\cup G_2即为顶点集合和边集合的unionV(G_1)\cup V(G_2)E(G_1)\cup E(G_2)

之前讨论的大部分图都是连通的(不能被表述为两个图的union),如果可以拆成两个图,那么就是非连通图

任何非连通图G都可以表示成连通图的union,这里的连通图被称为连通块/连通分量(connected component)

相邻

当图G的顶点v和w之间有一条边vw,我们称顶点v和w是相邻(adjacent)的,且与边相关(incident)。类似的,如果两条边e和f有一个公共的顶点,则称这两条边相邻。

邻接矩阵&关联矩阵

adjacency and incidence matrices

假设有n个顶点,邻接矩阵定义为一个nxn的矩阵,若顶点i和顶点j之间有一条边,则位置(i,j)为1,否则为0。任何邻接矩阵为实矩阵且为对称阵

假设有n个顶点,m条边,关联矩阵为一个nxm的矩阵,若顶点与边相关(这条边有一段连着这个顶点)则为1,否则为0。

如果顶点v的度为0,则称该顶点为孤立点(isolated)

如上图所示的图的度序列为(1,3,6,8)(可以看到环会带来两个度)

handshaking lemma:任何图的所有顶点的度的和是偶数。

说明如果几个人握手,总的握手数目一定是偶数

子图

图G的子图是一个顶点都在V(G)内,边都在E(G)内的图。

导出子图(induced subgraph):是子图,但是摘出来所有完整的边(如果某个点有多条边,只选取边的另一边连着的顶点也在选取的顶点集合中的边。

生成子图(spanning subgraph):是子图,但是顶点全都选出来了

特殊的图

null graphs:边的集合为空的图。注意null graph的每个顶点都是isolated的。

complete graphs:每一对不同的顶点是邻接的简单图。如果有n个顶点,那么边的数目为n(n-1)/2(见下图)

regular graphs:图的每个顶点都有相同的度(见下图)。如果图的每个顶点的度为r,则称图为regular of degree r或r-regular(r阶正则图)。

下图同样称为Petersen graph,是cubic graphs的一个例子,cubic graphs指的是3阶正则图

cycle graphs:二阶正则图。

path graphs:cycle graphs去掉一条边

wheel:给cycle graphs中的每个点都另外一起连到一个新的顶点

如下图:

platonic graphs:属于正则图

bipartite graphs(二部图/二分图):如果图G的顶点集合可以被分为两个不相交的集合A和B,使得图G的每条边都分别连接A中的顶点和B中的顶点。

cubes:正则二部图

路径和循环

连通性

给定一个图G。G中的一条线路(walk)是一个有限的边的序列,可以表示成:

v_0v_1,v_1v_2,......,v_{m-1}v_m

或者

v_0 \rightarrow v_1\rightarrow v_2 \rightarrow \cdot \cdot \cdot \rightarrow v_m

任意两条连续的边是邻接的或者是相同的(有一个自环)。我们称v_0为线路的初始顶点(initial vertex),v_m为线路的最终顶点(final vertex),并且称这个过程为从v_0到v_m的线路(a walk from v_0 to v_m)。线路中经过的边的条数称为线路的长度(length)

但是线路的概念往往太过于笼统了->引入轨迹(trail)的概念。轨迹指的是所有的边都是distinct的线路,如果同时能保证顶点也是distinct,就称为途径(path)。

如果轨迹或途径是封闭(closed)的(即初始顶点=最终顶点,v_0 = v_m)。至少包含一条边的封闭的途径称为环(cycle),请注意,任何的自环以及多重边都是环。

若G为二部图,则G的每个环的长度都是偶数

连通图:任何一对顶点时图中一条途径的两端

非连通图:⬆️不满足

Eulerian graphs

如果一个连通图G存在一条封闭的轨迹包含G中所有的边,则称这条轨迹为Eulerian trail。注意要求每条边都要遍历且只能走一次(一笔画)

如果一个非欧拉图存在一条轨迹可以包含所有的边,称为semi-Eulerian。上图由左到右依次为欧拉图,半欧拉图,非欧拉图。

七桥问题:

引理:若G的每个顶点的度都至少为2,那么G包含一个环

定理:当且仅当连通图G的每个顶点的度都是偶数,这个图才是Eulerian

(题外话,这不就是一笔画问题咩)

Hamiltonian graphs

哈密顿图

是否包含一条封闭的轨迹通过且只通过一次图G中的所有顶点。

一些算法

详见https://www.maths.ed.ac.uk/~v1ranick/papers/wilsongraph.pdf47页

本章暂时跳过

平面性

平面图

平面图(planar graph)指的是图可以被画在一个平面上并且避免交叉(即:没有任何两条边在除了顶点意外的地方在几何上相交)

把左图的一条边扯到外边(中间的图)就得到了一个平面图

同胚的 (homeomorphic):若两个图都可以通过向同一个图的边加入新的度为2的顶点,称两个图同胚

 

对偶图

图论(十三)——平面图和对偶图-CSDN博客

在G的每个面中选择点v*作为G*的顶点,对应G的边e画边e*穿过e,但是不穿过G的其他边,并将与e相邻的面的顶点v*连接起来,这些线就是G*的边

参考:

https://www2.math.ethz.ch/education/bachelor/lectures/fs2016/math/graph_theory/graph_theory_notes.pdf

https://sitn.hms.harvard.edu/flash/2021/graph-theory-101/

https://cseweb.ucsd.edu/~dakane/Math154/154-textbook.pdf

https://www.maths.ed.ac.uk/~v1ranick/papers/wilsongraph.pdf

这篇关于【补充】图神经网络前传——图论的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/951398

相关文章

图神经网络模型介绍(1)

我们将图神经网络分为基于谱域的模型和基于空域的模型,并按照发展顺序详解每个类别中的重要模型。 1.1基于谱域的图神经网络         谱域上的图卷积在图学习迈向深度学习的发展历程中起到了关键的作用。本节主要介绍三个具有代表性的谱域图神经网络:谱图卷积网络、切比雪夫网络和图卷积网络。 (1)谱图卷积网络 卷积定理:函数卷积的傅里叶变换是函数傅里叶变换的乘积,即F{f*g}

【多系统萎缩患者必看】✨维生素补充全攻略,守护你的健康每一天!

亲爱的朋友们,今天我们要聊一个既重要又容易被忽视的话题——‌多系统萎缩患者如何科学补充维生素‌!🌟 在这个快节奏的生活中,健康成为了我们最宝贵的财富,而对于多系统萎缩(MSA)的患者来说,合理的营养补充更是维护身体机能、提升生活质量的关键一步。👇 🌈 为什么多系统萎缩患者需要特别关注维生素? 多系统萎缩是一种罕见且复杂的神经系统疾病,它影响身体的多个系统,包括自主神经、锥体外系、小脑及锥

机器学习之监督学习(三)神经网络

机器学习之监督学习(三)神经网络基础 0. 文章传送1. 深度学习 Deep Learning深度学习的关键特点深度学习VS传统机器学习 2. 生物神经网络 Biological Neural Network3. 神经网络模型基本结构模块一:TensorFlow搭建神经网络 4. 反向传播梯度下降 Back Propagation Gradient Descent模块二:激活函数 activ

Vue2电商项目(二) Home模块的开发;(还需要补充js节流和防抖的回顾链接)

文章目录 一、Home模块拆分1. 三级联动组件TypeNav2. 其余组件 二、发送请求的准备工作1. axios的二次封装2. 统一管理接口API----跨域3. nprogress进度条 三、 vuex模块开发四、TypeNav三级联动组件开发1. 动态展示三级联动数据2. 三级联动 动态背景(1)、方式一:CSS样式(2)、方式二:JS 3. 控制二三级数据隐藏与显示--绑定styl

图神经网络框架DGL实现Graph Attention Network (GAT)笔记

参考列表: [1]深入理解图注意力机制 [2]DGL官方学习教程一 ——基础操作&消息传递 [3]Cora数据集介绍+python读取 一、DGL实现GAT分类机器学习论文 程序摘自[1],该程序实现了利用图神经网络框架——DGL,实现图注意网络(GAT)。应用demo为对机器学习论文数据集——Cora,对论文所属类别进行分类。(下图摘自[3]) 1. 程序 Ubuntu:18.04

基于深度学习 卷积神经网络resnext50的中医舌苔分类系统

项目概述 本项目旨在通过深度学习技术,特别是利用卷积神经网络(Convolutional Neural Networks, CNNs)中的ResNeXt50架构,实现对中医舌象图像的自动分类。该系统不仅能够识别不同的舌苔类型,还能够在PyQt5框架下提供一个直观的图形用户界面(GUI),使得医生或患者能够方便地上传舌象照片并获取分析结果。 技术栈 深度学习框架:采用PyTorch或其他

图神经网络(2)预备知识

1. 图的基本概念         对于接触过数据结构和算法的读者来说,图并不是一个陌生的概念。一个图由一些顶点也称为节点和连接这些顶点的边组成。给定一个图G=(V,E),  其 中V={V1,V2,…,Vn}  是一个具有 n 个顶点的集合。 1.1邻接矩阵         我们用邻接矩阵A∈Rn×n表示顶点之间的连接关系。 如果顶点 vi和vj之间有连接,就表示(vi,vj)  组成了

自然语言处理系列六十三》神经网络算法》LSTM长短期记忆神经网络算法

注:此文章内容均节选自充电了么创始人,CEO兼CTO陈敬雷老师的新书《自然语言处理原理与实战》(人工智能科学与技术丛书)【陈敬雷编著】【清华大学出版社】 文章目录 自然语言处理系列六十三神经网络算法》LSTM长短期记忆神经网络算法Seq2Seq端到端神经网络算法 总结 自然语言处理系列六十三 神经网络算法》LSTM长短期记忆神经网络算法 长短期记忆网络(LSTM,Long S

神经网络训练不起来怎么办(零)| General Guidance

摘要:模型性能不理想时,如何判断 Model Bias, Optimization, Overfitting 等问题,并以此着手优化模型。在这个分析过程中,我们可以对Function Set,模型弹性有直观的理解。关键词:模型性能,Model Bias, Optimization, Overfitting。 零,领域背景 如果我们的模型表现较差,那么我们往往需要根据 Training l

如何将卷积神经网络(CNN)应用于医学图像分析:从分类到分割和检测的实用指南

引言 在现代医疗领域,医学图像已经成为疾病诊断和治疗规划的重要工具。医学图像的类型繁多,包括但不限于X射线、CT(计算机断层扫描)、MRI(磁共振成像)和超声图像。这些图像提供了对身体内部结构的详细视图,有助于医生在进行准确诊断和制定个性化治疗方案时获取关键的信息。 1. 医学图像分析的挑战 医学图像分析面临诸多挑战,其中包括: 图像数据的复杂性:医学图像通常具有高维度和复杂的结构