【图神经网络】图神经网络(GNN)学习笔记：图的基础理论_gcn求最短距离

简介： 近年来，图神经网络(GNN)在社交网络、知识图、推荐系统甚至生命科学等各个领域得到了越来越广泛的应用。 GNN在对图节点之间依赖关系进行建模的强大功能，使得与图分析相关的研究领域取得了突破。本文介绍了图神经网络的基本原理，以及两种高级的算法， DeepWalk和 GraphSage。

1. 图的概述

图（Graph）是一种结构化数据，它由一系列的对象（nodes）和关系类型（edges）组成。作为一种非欧几里得形数据，图分析被应用到节点分类、链路预测和聚类等方向。

在离散数学中，图有顶点(Vertex)以及连接顶点的边Edge构成。Vertex表示研究的对象，Edge表示两个对象之间特定的关系。图G可表示为vertex和edge的集合, 记作G=(V,E),其中V是vertex的集合，E是edge的集合。例如图1所示。其中$V=v1,v2,v3,v4,v5$, $E=(v1,v2),(v1,v3),(v2,v4),(v2,v3),(v3,v4),(v4,v5)$.

2.图的基本类型

2.1 有向图和无向图

如果图中的边存在方向性，则称这样的边为有向边$e_{ij}=<v_i,v_j>$,其中$v_i$是这条有向边的起点，$v_j$是这条有向边的终点，包含有向边的图称为有向图。
无向图中的边为无向，边是对称的，同时包含两个方向：$e_{ij}=<v_i,v_j>=<v_j,v_i>=e_{ji}$。

2.2 非加权图与加权图

如果图里的每条边都有一个实数与之对应，我们称这样的图为加权图。与之相反的是非加权图，我们可认为非加权图各边上的权重是一样的。

2.3 连通图与非连通图

如果图中存在孤立的顶点，没有任何边与之相连，这样的图称为非连通图，反之。

• 对于一个无向图，如果任意的节点i能够通过一些边到达节点j，则称之为连通图。
• 连通分量：无向图G的一个极大连通子图称为G的一个连通分量（或连通分支）。连通图只有一个连通分量，即其自身；非连通图的无向图有多个连通分量。

2.4 二部图

二部图是一类特殊的图。我们将G中的顶点集合V拆分成两个子集A和B，如果对图中的任意一条边$e_{ij}$均有$v_i\in A$,$v_j\in B$或$v_i\in B$,$v_j\in A$,则称$G$为二部图。

2.5 邻居和度

如果存在一条边连接顶点$v_i$和$v_j$，则称$v_j$是$v_i$的邻居，反之亦然。以$v_i$为端点的边的数目称为$v_i$的度（Degree），记为$deg(v_i)$。
在有向图中，我们同时定义出度（outdegree）和入度（indegree），顶点的度数等于该顶点的出度与入度之和。

2.6 子图和路径

子图：图$G^{\prime }$中的顶点集合和边集分别为另一个图$G$的顶点集的子集和边集的子集。
路径：从顶点$v_i$到顶点$v_j$的通过的边
路径的长度：路径中边的数目。
顶点的距离：两个顶点之间的距离由他们的最短路径的长度决定。

2.7 有向图连通性

强连通图：给定有向图$G=(V,E)$，并且给定该图G中的任意两个结点u和v，如果结点u与结点v相互可达，即至少存在一条路径可以由结点u开始，到结点v终止，同时存在至少有一条路径可以由结点v开始，到结点u终止，那么就称该有向图G是强连通图。
弱连通图：若至少有一对结点不满足单向连通，但去掉边的方向后从无向图的观点看是连通图，则该图称为弱连通图。

2.8 最短路径和图直径

图的最短路径：如果从有向图中某一顶点(称为源点)到达另一顶点(称为终点)的路径可能不止一条，如何找到一条路径使得沿此路径上各边上的权值总和达到最小。
图的直径：是指任意两个顶点间距离的最大值。

2.9 度中心性

度中心性（Degree Centrality）是在网络分析中刻画节点中心性（Centrality）的最直接度量指标。 一个节点的节点度越大就意味着这个节点的度中心性越高，该节点在网络中就越重要。

$$degree=\frac{N_{degree}}{n-1}$$
其中n表示图中结点的个数。

2.10 特征向量中心性（Eigenvector Centrality）

特征向量中心性的基本思想是，一个节点的中心性是相邻节点中心性的函数。也就是说，与你连接的人越重要，你也就越重要。

特征向量中心性和点度中心性不同，一个点度中心性高即拥有很多连接的节点，但特征向量中心性不一定高，因为所有的连接者有可能特征向量中心性很低。同理，特征向量中心性高并不意味着它的点度中心性高，它拥有很少但很重要的连接者也可以拥有高特征向量中心性。

如下图所示：

用邻接矩阵A表示该图：

假设存在一个矩阵x，是一个5x1的向量，向量的值对应图中的每个点。在这种情况下，我们计算的是每个点的点度中心性（degree centrality），即以点的连接数来衡量中心性的高低。矩阵A乘以这个向量的结果是一个5x1的向量：

结果向量的第一个元素是用矩阵A的第一行去“获取”每一个与第一个点有连接的点的值（连接数，点度中心性），也就是第2个、第3个和第4个点的值，然后将它们加起来。

换句话说，邻接矩阵做的事情是将相邻节点的求和值重新分配给每个点。这样做的结果就是“扩散了”点度中心性。你的朋友的朋友越多，你的特征向量中心性就越高。

我们继续用矩阵A乘以结果向量。如何理解呢？

实际上，我们允许这一中心性数值再次沿着图的边界“扩散”。我们会观察到两个方向上的扩散（点既给予也收获相邻节点）。我们猜测，这一过程最后会达到一个平衡，特定点收获的数量会和它给予相邻节点的数量取得平衡。既然我们仅仅是累加，数值会越来越大，但我们最终会到达一个点，各个节点在整体中的比例会保持稳定。

我们认为，图中的点存在一个数值集合，对于它，用矩阵A去乘不会改变向量各个数值的相对大小。也就是说，它的数值会变大，但乘以的是同一个因子。用数学符号表示就是：

满足这一属性的向量就是矩阵M的特征向量。特征向量的元素就是图中每个点的特征向量中心性。
记$x_i$是$v_i$的特征向量中心性度量，则：
$$EC(i)=x_i=c\sum _{j=i}^n{a}_{ij}{x}_j$$
其中$c$是一个比例常数，记$x=[x_1,x_2,...,x_n{]}^T$，经过多次迭代达到稳态时，可写成如下形式：
$$x=cAx$$
其中是一个比例常数，$a_{ij}$当且仅当i与j相连，否则为0。
这里的x是矩阵A的特征值$c^{-1}$对应的特征向量，也可以表示成如下形式：
$$Ax=\lambda x$$

2.11 中介中心性（Betweeness Centrality）

中介中心性用于衡量一个顶点出现在其他任意两个顶点对之间的最短路径的次数，也就是说，如果一个顶点出现在任意两个顶点间最短路径的次数越多，那么该顶点的中介中心性就越大。该中心性经常用于反欺诈场景里中介实体的识别。
该算法的第一步要找出任意两个顶点之间的最短路径（通常使用广度优先算法，深度大于1度），然后统计出所有最短路径中，每个中间顶点出现的次数。

$$Betweenness=\frac{经过该结点的最短路径}{其余两两结点的最短路径}$$

2.12 接近中心性（Closeness centrality）

接近中心性主要用于计算每个顶点到其他所有顶点的最短距离之和。然后将得到的和反过来确定该节点的接近中心性得分。原生的接近中心性计算方式如下：
$$centrality(i)=\frac{1}{{\sum }_{n=1}^{N}distanc{e}_i^n}$$
其中N表示图顶点的个数，$distanc{e}_i^n$表示顶点i和顶点n的最短距离。更常见的做法是将此分数标准化，使其表示最短路径的平均长度，而不是他们的和。标准化的接近中心性计算公式如下：
$$centrality(i)=\frac{N-1}{{\sum }_{n=1}^{N}distanc{e}_i^n}$$
其中N表示图顶点的个数，$distanc{e}_i^n$表示顶点i到顶点n的最短距离。

如果节点到图中其它节点的最短距离都很小，那么我们认为该节点的Closeness Centrality高。这个定义其实比Degree Centrality从几何上更符合中心度的概念，因为到其它节点的平均最短距离最小，意味着这个节点从几何角度看是出于图的中心位置。

2.13 图的存储与遍历

2.13.1 邻接矩阵与关联矩阵

邻接矩阵（Adjacency matrix）：邻接矩阵A描述图中顶点之间的关联,$A\in R^{N\ast N}$，其定义为：

关联矩阵：关联矩阵$B\in R^{N\ast M}$来描述结点与边之间的关联，定义如下：


如上图，其邻接矩阵与关联矩阵可表示为：
1)图的邻接矩阵

2)图的关联矩阵

• 一般情况下邻接矩阵中会有大量0元素，所以邻接矩阵的存储通常是通过稀疏矩阵来存的，空间复杂度能在O(M)。
• 关联矩阵就用的比较少了，是通过记录顶点和边的关系建立的。每列代表一条边，如果节点是边的顶点则为1，否则为0。在存储的时候需要两个一维数组表示顶点集合和边集合，再用一个二维数组来存储关联矩阵。因为每行只有2个非0值，所以关联矩阵一般也用稀疏矩阵存储。

2.13.2 图的遍历

图的遍历是指从图中的某一顶点出发，按照某种搜索算法沿着图中的边对图中的所有顶点访问一次且仅访问一次，图的遍历算法主要有两种算法：

• 深度优先搜索（DFS,Depth-First-Search）
• 广度优先搜索（BFS,Breadth-First-Search）。

3. 图数据的应用场景

图数据是一类比较复杂的数据类型，存在非常多的类别，这里介绍最重要的4类：同构图（Homogeneous Graph）、异构图（Heterogeneous Graph）、属性图（Property Graph）和非显式图（Graph Constructed from Non-relational Data）.
1）同构图：图中的节点类型和关系类型都仅有一种。如由超链接关系所构成的万维网。
2）异构图：图的节点类型和关系类型有多种。
3）属性图：相较于异构图，属性图给图数据增加了额外的属性信息，如节点的标签（Label），关系的属性（Property）
4）非显式图：指数据之间没有显示的定义出关系，需要依据某种规则或计算方式将数据的关系表达出来，进而将数据当做一种图数据进行研究。比较抽象，一个例子是点云，本来不是图，但可以将每个点和其他点的距离计算出来转化为关系，可以将点云转化为图

4. 图数据深度学习

一些图学习的理论：

• 谱图理论（Spectral Graph Theory）：图论与线性代数结合，发展出谱聚类相关算法，可以用来解决图的分割或者节点的聚类
  图数据相关任务的一种分类：
• 统计关系学习（Statistical Relation Learning）：关系表述与似然表示结合
• 异构信息网络（Heterogeneous Information Network）
• 图嵌入（Network Embedding）：原书翻译的是网络表示学习

图数据相关的一些任务分类：

1. 节点层面（Node Level）的任务
   节点层面的任务主要包括分类任务和回归任务。这类任务虽然是对节点层面的性质进行预测，但是显然不应该将模型建立在一个个单独的节点上，节点的关系也需要考虑。节点层面的任务有很多。包括学术上使用较多的对论文引用网络中论文节点进行分类，工业界在线社交网络中用户标签的分类、恶意账户检测等。
2. 边层面（Link Level)的任务
   边层面的任务主要包括边的分类和预测任务。边的分类是指对边的某种性质进行预测；边预测是指给定的两个节点之间是否会构成边。常见的应用场景比如在社交网络中，将用户作为节点，用户之间的关注关系建模为边，通过对边预测实现社交用户的推荐。目前，边层面的任务主要集中在推荐业务中。
3. 图层面（Graph Level）的任务
   图层面的任务不依赖于某个节点或者某条边的属性，而是从图的整体结构出发，实现分类、表示和生成等任务。目前，图层面的任务主要应用在自然科学研究领域，比如对药物分子的分类、酶的分类等。

参考资料

1. https://developer.aliyun.com/article/694432
2. 《深入浅出图神经网络：GNN原理解析》
3. https://blog.csdn.net/weixin_45884316/article/details/115751272
4. https://blog.csdn.net/vincent_duan/article/details/119872349