二、图论基础

2.1 图的简介

图（Graph）描述了实体之间的两两关系，是诸多领域中真实数据的基本表示方法。

2.2 图的表示

【图】 一个图可表示为 G = { V , E } G=\{V,E\} G={V,E}，其中 V = { v 1 , v 2 , ⋯   , v N } V=\{v_1,v_2,\cdots,v_N\} V={v1​,v2​,⋯,vN​}是大小为N的节点集合， E = { e 1 , e 2 , ⋯   , e M } E=\{e_1,e_2,\cdots,e_M\} E={e1​,e2​,⋯,eM​}是大小为M的边集合。

【相邻】 两个节点相邻当且仅当它们之间存在一条边

• 连接两个节点的边与这两个节点相关联

【邻接矩阵】 给定一个图 G = { V , E } G=\{V,E\} G={V,E}，对应的邻接矩阵可表示为 A ∈ { 0 , 1 } N × N A \in \{0,1\}^{N\times N} A∈{0,1}N×N。邻接矩阵A的第i行第j列元素$A_{i,j}$表示节点$v_i$与$v_j$的连接关系。如果$v_i$与$v_j$相邻，则$A_{i,j}=1$，否则为0。

• 无向图的邻接矩阵一定是对称的

2.3 图的性质

2.3.1 度

【度】 在图 G = { V , E } G=\{V,E\} G={V,E}中，节点$v_i\in V$的度$d(v_i)$为图G中与节点$v_i$相关联的边的数目

• 节点的度可由邻接矩阵计算：$d(v_i)={\sum }_{j=1}^N{A}_{i,j}$
• 图中所有节点的度之和是图中边的数量的二倍
• 无向图邻接矩阵的非零元素的个数是边的数量的二倍

【邻域】 在图 G = { V , E } G=\{V,E\} G={V,E}中，节点$v_i$的邻域$N(v_i)$是所有与其相邻的节点的集合。

• 一个节点的邻域的元素个数等于节点的度

2.3.2 连通度

【途径】 图的途径是节点和边的交替序列，以一个节点开始，以一个节点结束，其中每条边与紧邻的节点相关联

• 节点u起到节点v的途径表示为$u-v$途径
• 途径的长度为途径中包含边的数量
• u-v途径不是唯一的

【迹】 迹是边各不相同的途径

【路】 路是节点各不相同的途径

• 对于图 G = { V , E } G=\{V,E\} G={V,E}及其邻接矩阵A，$A^n$的第i行第j个元素等于长度为n的$v_i-v_j$途径的个数。

【子图】 子图由图的节点集子集和边集子集组成，且节点集子集必须包括边集自己的所有节点

【连通分量】 给定图 G = { V , E } G=\{V,E\} G={V,E}，如果一个子图中任意一对节点之间都至少存在一条路，且子图的节点集不与节点集补集有联系，则该子图为一个连通分量。

【连通图】 如果图中只有一个连通分量，则图为连通图

【最短路】 $p_{st}^{sp}=\underset{p\in P_{st}}{\mathrm{argmin}}|p|$

• 任意给定的节点对之间可能有多条最短路

【直径】 $diameter(G)={\max }_{v_s,v_t\in V}{\min }_{p\in P_{st}}|p|$

2.3.3 中心性

在图中，节点的中心性同于衡量节点在图中的重要性。

【度中心性】 $c_d(v_i)=d(v_i)={\sum }_{j=1}^N{A}_{i,j}$

【特征向量中心性】 $c_e(v_i)=\frac{1}{\lambda }{\sum }_{j=1}^N{A}_{i,j}\cdot c_e(v_j)$

• 矩阵表示为$c_e=\frac{1}{\lambda }A\cdot c_e$
• 一个元素全为正的实方阵具有唯一的最大特征值，其对应的特征向量的元素全为正

【Katz中心性】 $c_k(v_i)=\alpha {\sum }_{j=1}^N{A}_{i,j}{c}_k(v_j)+\beta$

• 矩阵表示为$c_k=\alpha A\cdot c_k+\beta$
• 特征向量中心性的变体，不仅考虑了邻居的中心性，而且包含了一个常数考虑中心节点本身

【介数中心性】 $c_b(v_i)={\sum }_{v_s\ne v_i\ne v_t}\frac{{\sigma }_{st}(v_i)}{{\sigma }_{st}}$。其中${\sigma }_{st}$为所有从节点$v_s$到节点$v_t$最短路的数目，${\sigma }_{st}$表示这些路中经过节点$v_i$的数目

• 归一化：$c_{nb}(v_i)=\frac{2\times {\sum }_{v_s\ne v_i\ne v_t}\frac{{\sigma }_{st}(v_i)}{{\sigma }_{st}}}{(N-1)(N-2)}$

2.4 谱图论

谱图论通过分析图的拉普拉斯矩阵的特征值和特征向量研究图的性质。

2.4.1 拉普拉斯矩阵

【拉普拉斯矩阵】 对于图 G = { V , E } G=\{V,E\} G={V,E}及其邻接矩阵$A$，拉普拉斯矩阵定义为$L=D-A$。式中$D$为对角矩阵，$D=diag(d(v_1).d(v_2),\cdots ,d(v_N))$

• 归一化拉普拉斯矩阵：$L^{\prime }=D^{-\frac{1}{2}}(D-A)D^{-\frac{1}{2}}=I-D^{-\frac{1}{2}}A{D}^{-\frac{1}{2}}$
• 拉普拉斯矩阵是半正定、对称矩阵

2.4.2 拉普拉斯矩阵的特征值与特征向量

【定理】 图的拉普拉斯矩阵的特征值非负

【定理】 图的拉普拉斯矩阵中特征值为0的数量等于图中连通分量的数量

2.5 图信号处理

图信号，即图数据结构中存在的与节点相关联的特征或属性，它捕获结构信息（或节点之间的连接）和数据（或节点上的属性）。

图信号由图 G = { V , E } G=\{V,E\} G={V,E}和在节点域上定义的将节点映射为实数值的映射函数$f:V\to {\mathrm{R}}^{N\times d}$构成，其中$d$为节点属性向量的维数。如果图中相邻节点的属性值相似，则称这个图是平滑的，即平滑的图信号是低频的。图信号$f$的平滑度/频率可由拉普拉斯矩阵二次型$f^{T}Lf$测量。

【图的傅里叶变换】 $\hat{f}[l]=<f,u_l>={\sum }_{i=1}^{N}f[i]u_l[i]$，其中$u_l$代表拉普拉斯矩阵的第$l$个特征向量，对应的特征值${\lambda }_l$表示$u_l$的频率（平滑度）。

• 矩阵表示：$\hat{f}=U^{T}f$，其中矩阵$U$的第$l$列为$u_l$
• 特征值度量对应特征向量的平滑度 -> 特征值小，则对应的特征向量平滑

【图的傅里叶逆变换】 $f[l]={\sum }_{i=1}^N\hat{f}[i]u_l[i]$

• 矩阵表示：$f=U\hat{f}$

2.6 复杂图

【异质图】（Heterogeneous Graph） 异质图$G$由节点集合 V = { v 1 , ⋯   , v N } V=\{v_1,\cdots,v_N\} V={v1​,⋯,vN​}和边集合 E = { e 1 , ⋯   , e M } E=\{e_1,\cdots,e_M\} E={e1​,⋯,eM​}组成，其中每个节点和每条边都对应一种类型。$T_n$表示节点类型的集合，$T_e$表示边类型的集合。异质图有两个映射函数：${\varphi }_n:V\to T_n$和${\varphi }_e:E\to T_e$。

【二分图】（Bipartite Graph） 图 G = { V , E } G=\{V,E\} G={V,E}是二分图当且仅当：$V=V_1\bigcup V_2$，$V_1\bigcap V_2=\varnothing$，对于所有边$e=(v_e^1,v_e^2)\in E$，都有$v_e^1\in V_1$和$v_e^2\in V_2$

【多维图】（Multi-dimensional Graph） 多维图由一个节点集合 V = { v 1 , ⋯   , v N } V=\{v_1,\cdots,v_N\} V={v1​,⋯,vN​}和$D$个边集合 { E 1 , ⋯   , E D } \{E_1,\cdots,E_D\} {E1​,⋯,ED​}组成。每个边集合描述了节点之间的一种关系，$D$个边集合可表示为$D$个邻接矩阵$A^{(d)}$

【符号图】（Signed Graph） 符号图表示为 G = { V , E + , E − } G=\{V,E^+,E^-\} G={V,E+,E−}，$E^{+}\subset V\times V$和$E^{-}\subset V\times V$分别为正边集合和负边集合，同时保证$E^{+}\bigcap E^{-}=\varnothing$。在符号图的邻接矩阵中，元素取值为$\pm 1,0$。

【超图】（HyperGraph）超图可表示为 G = { V , E , W } G=\{V,E,W\} G={V,E,W}，其中$V$为节点集合，$E$为超边集合，$W\in {\mathrm{R}}^{|E|\times |E|}$，其中$W_{j,j}$表示超边$e_j$的权重。超图也可利用关联矩阵$H\in R^{|V|\times |E|}$表示，其中$H_{i,j}=1$表示$v_i$与$e_j$关联，节点的度为$d(v_i)={\sum }_{i=1}^{|V|}{H}_{i,j}$。此外，$D_e$和$D_v$分别表示边和节点的度矩阵，且二者均为对角矩阵。

【动态图】（Dynamic Graph） 动态图的每个节点和边都与其产生的时间戳相关联，即存在两个映射函数分别将节点和边映射到它们的时间戳。

• 离散动态图 离散动态图由T个快照 { G 0 , ⋯   , G T } \{G_0,\cdots,G_T\} {G0​,⋯,GT​}构成，每个快照是在图形成过程中观察到的

2.7 图的计算任务

图的计算任务通常分为两大类：侧重于节点的任务、侧重于图的任务。前者将整个数据表示为一个图，节点作为数据样本；后者将数据看作一组图，每个数据样本是一个图。

2.7.1 侧重于节点的任务

【节点分类】 节点分类的目标是利用图和标签节点的信息，学习一个映射使之能够预测无标签节点的分类

【链接预测】 链接预测的目标是预测最可能存在的链接。待预测的每条边被赋予一个分数值用来表示存在这条边的可能性

2.7.2 侧重于图的任务

【图分类】 图分类的目标为在图数据集上学习一个映射函数，用来预测未标记图的标签