注:本节大部分内容(包括图片)来源于"Chapter 2 - Foundations of Graphs, Deep Learning on Graphs",我们做了翻译与重新排版,并增加了一些细节内容。
定义一(图):
定义二(图的邻接矩阵):
给定一个图$\mathcal{G}={\mathcal{V}, \mathcal{E}}$,其对应的邻接矩阵被记为$\mathbf{A} \in{0,1}^{N \times N}$。$\mathbf{A}_{i, j}=1$表示存在从节点$v_i$到$v_j$的边,反之表示不存在从节点$v_i$到$v_j$的边。
在无向图中,从节点$v_i$到$v_j$的边存在,意味着从节点$v_j$到$v_i$的边也存在。因而无向图的邻接矩阵是对称的。
在无权图中,各条边的权重被认为是等价的,即认为各条边的权重为$1$。
对于有权图,其对应的邻接矩阵通常被记为$\mathbf{W} \in \mathbb{R}^{N \times N}$,其中$\mathbf{W}{i, j}=w{ij}$表示从节点$v_i$到$v_j$的边的权重。若边不存在时,边的权重为$0$。
一个无向无权图的例子:
其邻接矩阵为:
$$
\mathbf{A}=\left(\begin{array}{lllll}
0 & 1 & 0 & 1 & 1 \
1 & 0 & 1 & 0 & 0 \
0 & 1 & 0 & 0 & 1 \
1 & 0 & 0 & 0 & 1 \
1 & 0 & 1 & 1 & 0
\end{array}\right)
$$
定义三(节点的度,degree):
定义四(邻接节点,neighbors):
定义五(行走,walk):
定理六:
定义七(路径,path):
定义八(子图,subgraph):
定义九(连通分量,connected component):
给定图$\mathcal{G}^{\prime}={\mathcal{V}^{\prime}, \mathcal{E}^{\prime}}$是图$\mathcal{G}={\mathcal{V}, \mathcal{E}}$的子图。记属于图$\mathcal{G}$但不属于$\mathcal{G}^{\prime}$图的节点集合记为$\mathcal{V}/\mathcal{V}^{\prime}$ 。如果属于$\mathcal{V}^{\prime}$的任意节点对之间存在至少一条路径,但不存在一条边连接属于$\mathcal{V}^{\prime}$的节点与属于$\mathcal{V}/\mathcal{V}^{\prime}$的节点,那么图$\mathcal{G}^{\prime}$是图$\mathcal{G}$的连通分量。
左右两边子图都是整图的连通分量。
定义十(连通图,connected graph):
定义十一(最短路径,shortest path):
定义十二(直径,diameter):
$$
\operatorname{diameter}(\mathcal{G})=\max {v{s}, v_{t} \in \mathcal{V}} \min {p \in \mathcal{P}{s t}}|p|
$$
定义十三(拉普拉斯矩阵,Laplacian Matrix):
定义十四(对称归一化的拉普拉斯矩阵,Symmetric normalized Laplacian):
$$
\mathbf{L=D^{-\frac{1}{2}}(D-A)D^{-\frac{1}{2}}=I-D^{-\frac{1}{2}}AD^{-\frac{1}{2}}}
$$
在学习了简单的图论知识,我们再来回顾应用神经网络于图面临的挑战。
过去的深度学习应用中,我们主要接触的数据形式主要是这四种:矩阵、张量、序列(sequence)和时间序列(time series),它们都是规则的结构化的数据。然而图数据是非规则的非结构化的,它具有以下的特点:
以往的深度学习技术是为规则且结构化的数据设计的,无法直接用于图数据。应用于图数据的神经网络,要求
在此篇文章中,我们学习了简单的图论知识。对于学习此次组队学习后续的内容,掌握这些图论知识已经足够。如果有小伙伴希望掌握更多的图论知识可以参阅参考文献“Chapter 2 - Foundations of Graphs, Deep Learning on Graphs”。
Dear OpenI User
Thank you for your continuous support to the Openl Qizhi Community AI Collaboration Platform. In order to protect your usage rights and ensure network security, we updated the Openl Qizhi Community AI Collaboration Platform Usage Agreement in January 2024. The updated agreement specifies that users are prohibited from using intranet penetration tools. After you click "Agree and continue", you can continue to use our services. Thank you for your cooperation and understanding.
For more agreement content, please refer to the《Openl Qizhi Community AI Collaboration Platform Usage Agreement》