资料：

课程网址
斯坦福CS224W图机器学习、图神经网络、知识图谱【同济子豪兄】
斯坦福大学CS224W图机器学习公开课-同济子豪兄中文精讲
cs224w（图机器学习）2021冬季课程学习笔记集合

序言

到图神经网络GCN为止的内容参考了斯坦福CS224W图机器学习、图神经网络、知识图谱【同济子豪兄】，后面的内容根据课程网址的ppt课件学习整理。

图的基本表示

图是描述各种关联现象的通用语言。与传统数据分析中的样本服从独立同分布假设不一样，图数据自带关联结构，数据和数据，样本和样本之间有联系。

图神经网络是端到端的表示学习，无需人工特征工程，可以自动学习特征(类似CNN)。

图神经网络的目标是实现图嵌入，即将一个节点映射成d维向量，同时保证网络中相似的节点有相近的向量表示。这个d维向量应该包含节点在原图中的结构信息，语意信息，以方便后续的数据挖掘。

在这里插入图片描述

节点、连接、子图、全图都可以带有特征

不同的任务

在节点、连接、子图、全图层面，都可以进行图数据挖掘

节点层面的案例：如信用卡欺诈
连接层面的案例：如推荐可能认识的人
子图层面的案例：如用户聚类
全图层面的案例：全图层面的预测，如分子是否有毒；全图层面的生成，如生成新的分子结构

图的本体设计

图(network/graph)由节点(nodes/vertices)和连接(links/edges)组成。

节点的集合用N表示，连接的集合用E表示，整个图用G(N,E)表示。

本体图

图的设计牵涉到一个概念，本体图(Ontology)。本体图应该显示节点可能的类型，以及各类型节点(包括节点类型到其自身)之间可能存在的关系。如下图，是一个医疗领域的知识图谱的本体图。

如何设计本体图，取决于要解决的问题。如下图，例如要解决的问题是，什么疾病可以吃什么，那么疾病和食物就需要设计成节点。可以吃，不可以吃， 不推荐吃就应该设计成节点之间的关系

在这里插入图片描述

有时本体图是唯一、无歧义的，如社交网络
有时本体图不唯一，取决于你要研究的问题，如考虑红楼梦的家族，地点，事件等

图的种类（有向、无向、异质、二分、连接带权重）

图可以分为无向图、有向图、异质图(heterogeneous graph)、二分图。

无向图：对称的、双向的图。如合作关系，facebook上的好友关系
有向图：单向的图。如电话，Twitter上的关注
异质图：节点和连接可能有不同的类型，是很多论文研究的重点
二分图(Bipartite Graph)：节点种类是2的异质图被称为二分图。如论文作者和论文的关系、用户和商品之间的关系

二分图可以展开，如下图，在节点集U中，如果两个节点都连接到V中的同一个节点，则在图Projection U中添加一条连接。
这样就可以将二分图转化为两张各自只有一类节点的图。

节点的度(Node degree)

对于无向图
- 第i个节点的度：记为 $k_i$ ，表示与第i个节点邻接的边的数量
- 图的平均度： $\bar{k}=\langle k\rangle=\frac{1}{N} \sum_{i=1}^N k_i=\frac{2 E}{N}$
对于有向图
- 入度：从别的节点指向当前节点的边的总数
- 出度：从当前节点指向别的节点的边的总数
- 节点的度=入度+出度
- 图的平均度： $\bar{k}=\frac{E}{N}$
  
  平均入度=平均出度，因为一个出度对应的边必然对应一个入度对应的边
  入度为0的节点称为Source，出度为0的节点称为Sink

节点的度可以一定程度上反应节点的重要程度

图的基本表示-邻接矩阵

无向图
如果第i个节点和第j个节点之间存在边，则邻接矩阵A的 $A_{ij}$ 和 $A_{ji}$ 对应的值为1

无向图对应的邻接矩阵是对称阵
如果没有自身到自身的环，则主对角线全为0

有向图
如果第i个节点存在指向第j个节点之间的边，则邻接矩阵A的 $A_{ij}$ 对应的值为1

有向图对应的邻接矩阵是非对称阵

邻接矩阵是稀疏的，如社交网络

图的基本表示-连接列表和邻接列表

如上面所示，用邻接矩阵来表示图，存在稀疏性问题，造成存储空间的浪费。

连接列表：只记录存在连接的边和节点
邻接列表：对于一个给定节点，只记录他指向的节点和对应的边

上述图是无权图，在邻接矩阵中的值非1即0，如果是带权图，则可以在邻接矩阵中将1改成权重。

图的连通性

无向图中
连通图(Connected graph)：任意两个点都有一条路径可达，则称为连通图。
不连通图虽然本身不连通，但是可以划分得到多个连通分支(connected components)。

最大的连通分支被称为Giant Component
孤立的节点称为Isolated node。
不连通矩阵的邻接矩阵呈现出分块对角的形式
如果存在一个节点将不连通图的两个连通分支连接上了，那么它会打破分块对角形式
有向图中
强连通的有向图：如果任意两个节点存在有向路径可达，则称为强连通的有向图。
弱连通的有向图：如果忽略边的方向，即将它看成无向图，此时如果图是连通的，那么这个有向图称为弱连通的。

对于有向图，可能整体不是强连通的，但其中的某个子图是强连通的，称为强连通分支(Strongly connected components(SCC))
E和G指向SCC，称为In-componet、D和F是由SCC出发的，称为Out-component。

传统图机器学习的特征工程-节点

总的思路
本节用传统机器学习方法，做特征工程，人工设计一些特征，把节点，边，全图特征编码成d维向量，再用该向量进行后续机器学习预测。
1.特征工程
抽取d个特征，编码为d维向量。本节只考虑连接特征，不考虑属性特征。

节点自己的特征，称为属性特征(Attributes)
节点和图中其他节点的连接关系，称为连接特征。
2.训练一个机器学习模型
利用RF、SVM、NN等进行训练。
3.应用模型
给定一个新的节点/链接/图，获得图她的特征并做预测。

本节主要聚焦无向图，并针对节点、边、图层面做特征工程。

节点层面的特征工程

目标：区分节点在图中的结构和位置，可考虑的(连接)特征有：节点的度(Node degree)、节点的重要度(Node centrality)、聚类系数(Clustering coefficient)、子图模式(Graphlets)

聚合系数是指，与当前节点邻接的节点是否有联系。

Node degree

Node degree只考虑了邻接节点的数量，不能反应节点的质量

Node centrality

Node centrality考虑了节点在图中的重要度。有不同的方式来对此进行建模：

特征向量重要度(Eigenvector centrality)
思想：如果一个节点的邻接节点很重要，那么这个节点也很重要
建模：
$c_v=\frac{1}{\lambda}\sum_{u \in N(v)} c_u$

$\lambda$ 是归一化系数，往往是A的最大特征值

实现：这是一个递归问题，如何解决？
上面公式等价于求解 $\lambda \boldsymbol{c}=\boldsymbol{A c}$

可以发现， $\boldsymbol{c}$ 向量就是 $\boldsymbol{A}$ 的最大特征值对应的特征向量
根据perron-frobenius定理，最大特征值 $\lambda_{max}$ 一定为正且唯一
Betweenness centrality
思想：如果在任意两个节点间的最短路径中，有一个节点频繁出现，那么这个节点可以被认为是重要的
建模：
$c_v=\sum_{s \neq v \neq t} \frac{\#(\text { shortest paths betwen } s \text { and } t \text { that contain } v)}{\#(\text { shortest paths between } s \text { and } t)}$
Closeness centrality
思想：如果一个节点到其他所有节点的路径都很短，那么这个节点可以被认为是重要的
建模：
$c_v=\frac{1}{\sum_{u \neq v} \text { shortest path length between } u \text { and } v}$

Clustering Coefficient

聚类系数(Clustering Coefficient)，衡量一个节点的邻接节点的连接有多紧密。
建模：
$e_v=\frac{\#(\text{edges among neighboring nodes})}{\binom{k_v}{2}}\in [0, 1]$

v节点相邻节点两两组成的节点对计入分母
如果节点对中的两个节点相邻，那么这对节点对计入分子

Graphlets

一个节点的自我网络(ego-network)是指以一个节点为中心，只包含他和他邻接节点，以及这些节点之间的边的图。
可以发现，节点v的聚类系数本质上就是计数了节点v的自我网络中以v为顶点的三角形的个数。
这个三角形可以理解为我们预先定义的一类子图。
那么如果修改这个预定义的子图类型，就可以得到新的计数特征，这个预定义的子图类型，就是我们下面要提到的graphlets。

先看看子图、生成子图、导出子图的概念：
在这里插入图片描述

可以看到，从原图中取一些节点，并取这些节点所有出现的边可以构成导出子图。

下面给出Graphlets的精确定义，即有根连通导出异构子图(Rooted connected induced non-isomorphic subgraphs)
在这里插入图片描述

上图分别展示了2节点、3节点、4节点和5节点的graphlets，共有73种。
2个节点构成的子图中，可以定义1种类型的graphlet
3个节点构成的子图中，可以定义3种类型的graphlets
…
在右上角的例子中，节点u对应的graphlets类型有0、1、2、3、5、10、11、…
聚类系数中的三角形其实就是G2对应的graphlet。

下面引入Graphlets相关的特征向量：Graphlets Degree Vector(GDV)，它一个基于给定节点，以它为根的各类graphlets的实例个数组成向量，如下面的例子。
在这里插入图片描述

注意，原图中没有以c为根结点的导出子图。
GDV描述了节点局部领域的拓扑结构信息，用一些已经定义好的子图模式去匹配，并计数每种模式下的数量。
比较两个节点的GDV向量，可以计算距离和相似度。
在NetworkX中，子图模式Graphlets被称为Atlas

总结

介绍的结构特征可以分为：

基于重要度的特征(描述节点中心度/重要度)：

节点的度
不同节点的重要度度量

可用于预测有影响力的节点

基于结构的特征(描述节点的邻域拓扑连接结构)：

节点的度
聚类系数
GDV

可用于预测节点在图中的功能，桥接、枢纽、中心

传统图机器学习的特征工程-连接

连接层面的预测任务：基于已知连接去预测(补全)未知连接。
在模型训练阶段，节点对被排序，top K节点对被预测。
关键是如何设计节点对的特征。

思路1：直接提取link的特征，变成d维向量。
思路2：把link两端的d维向量拼在一起，但是这会丢失link本身连接结构信息。

link prediction task有两种情况：

随机丢失连接：
对于客观静态图，如蛋白质，分子，我们可以通过随机移除一些连接，并尝试预测它们
随时间变化的连接：
对于如论文引用、社交网络、微信好友、学术合作等图，给定一段时间 $t_0, t_0^{'}]$ 的图，预测下一个时间段 $t_1, t_1^{'}]$ 的一个关于边的ranked list L。
评估的方式：先计算得到 $t_1, t_1^{'}]$ 内真实出现的边的数量，记为 $n=|E_{new}|$ ，然后从上面预测的列表中选出top n条边，然后计算预测的n个连接的准确率。
$\frac{预测的top\ n个连接中正确的数量}{n}$

连接层面的特征

连接的特征可以分为三类：基于距离的特征、基于两节点局部邻域信息的特征、基于两节点全局领域信息的特征

两节点的最短路径长度

在这里插入图片描述

但仅考虑最短路径长度，会忽略连接的质量。如同样最短路径长度是2，A和B只有一条通路，而B和H有两条。

基于两节点局部邻域的信息

考虑两个节点v1和v2的邻接节点。

Common neighbors：
思路：记录共同好友个数
公式：
$\left|N\left(v_1\right) \cap N\left(v_2\right)\right|$
Jaccard’s coefficient：
思路：共同好友个数/两节点邻接节点的并集
公式：
$\frac{\left|N\left(v_1\right) \cap N\left(v_2\right)\right|}{\left|N\left(v_1\right) \cup N\left(v_2\right)\right|}$
Adamic-Adar index：
思路：共同好友是不是社牛，如果v1和v2的共同好友是社牛，那么v1和v2的联系就很廉价。
公式：
$\sum_{u \in N\left(v_1\right) \cap N\left(v_2\right)} \frac{1}{\log \left(k_u\right)}$

基于两节点的局部邻域信息的特征的缺点是：对于没有共同好友的两节点，他们的上述度量都是0。
但事实上，他们在未来可能会有连接。
而全局领域的信息度量可以解决这个缺陷。

基于两节点全局领域的信息

Katz index：
思路：计数节点u和v之间所有长度路径的加权和

可以使用图邻接矩阵的幂可以结算长度为k的路径个数
结合下图，利用数学归纳法，可以推导出 $A_{u v}^l$ 表示节点u和v之间长度为l的路径个数。

公式：
$S_{v_1 v_2}=\sum_{l=1}^{\infty} \beta^{l} A_{v_1 v_2}^l$

其中， $0<\beta<1$ 表示折减系数
它的等价矩阵形式是(类比等比数列求和，并求无穷级数可得)：
$(\boldsymbol{I}-\beta \boldsymbol{A})^{-1}-\boldsymbol{I}$
一般可以将最大特征值的倒数作为折减系数 $\beta$

传统图机器学习的特征工程-全图

目标：将全图 $G$ 的结构特点表示为一个d维特征向量 $\phi(G)$ 。
在这里插入图片描述

Bag-of-*

思路：类比NLP中的Bag-of-Words，

Bag-of-nodes.

在这里插入图片描述

Bag-of-node degrees

在这里插入图片描述

Bag-of-graphlets

注意，这里是从全图的视角去分析，所以这里的graphlets和前面在节点特征工程中提到的graphlets有两点不同：
可以存在孤立节点的graphlets
graphlets不区分根，如下图，g2对应一个graphlets，而不是两个(如果考虑根，是两个)

在这里插入图片描述
Graphlet Count Vector：给定一个图G，和graphlets列表 $G_k=(g_1,g_2, ... g_{n_k})$ ，Graphlet Count Vector可以定义为（向量的第i个分量可以定义为第i个graphlet在全图中的个数）：
$\left(f_G\right)_i=\#\left(g_i \subseteq G\right) \text { for } i=1,2, \ldots, n_k$
例子：
在这里插入图片描述
给定两个图， $G$ 和 $G^{'}$ ，且有了它们对应的GCV，进一步，可以计算Graphlet Kernel：
$K\left(G, G^{\prime}\right)=\boldsymbol{f}_G^{\mathrm{T}} \boldsymbol{f}_{G^{\prime}}$
它可以反应这两张图的关系。

如果两个GCV的数量级悬殊，那么则需要先对这两个特征向量作归一化： $\boldsymbol{h}_G=\frac{\boldsymbol{f}_G}{\operatorname{Sum}\left(\boldsymbol{f}_G\right)}$ ，再计算Graphlet Kernel： $K\left(G, G^{\prime}\right)=\boldsymbol{h}_G{ }^{\mathrm{T}} \boldsymbol{h}_{G^{\prime}}$
获取GCV在算力上是很昂贵的，在大小为n的图上对大小为k的graphlet作子图匹配，需要的时间复杂度是多项式复杂度： $O(n^k)$ 。
即使图节点的度被限制为 $d$ ，复杂度也仍有 $O(nd^{k-1})$

Weisfeiler-Lehman Kernel

由于Graphlets Kernel不够高效，下面引入更高效的Weisfeiler-Lehman Kernel。
目标：设计一个更高效的特征编码。
思路：使用邻域结构迭代式地丰富节点词库
算法实现：颜色微调
主要的步骤是：

1.初始化颜色
2.聚合邻域的颜色+对聚合后的颜色进行哈希映射：
$c^{(k+1)}(v)=\operatorname{HASH}\left(\left\{c^{(k)}(v),\left\{c^{(k)}(u)\right\}_{u \in N(v)}\right\}\right)$

哈希表由两张图共同贡献
3.重复执行k次2的操作，获得 $c^{(K)}(v)$ ，根据所有出现过的颜色，统计次数，得到 $\phi(G)$

$c^{(K)}(v)$ 中包含了K跳邻域的信息。
4.计算WL Kernel： $\phi(G)^T\phi(G)$

总体而言，WL Kernel的时间复杂度是O(#(edges))。

kernel methods

核方法是传统技巧学习在图层面的预测的常用方法。它的核心是如何设计Kernel而非特征向量。

Kernel $K (G, G^{'})$ 是标量，描述了数据间的相似度
核矩阵 $\boldsymbol{K}=\left(K\left(G, G^{\prime}\right)\right)_{G, G^{\prime}}$ 永远半正定，即有正的特征值。
存在特征表示 $\phi(\cdot)$ 使得 $K\left(G, G^{\prime}\right)=\phi(G)^{\mathrm{T}} \phi\left(G^{\prime}\right)$
一定kernel确定了，现成的机器学习模型，如Kernel SVM就可以用来预测。

Node Embeddings-图嵌入表示学习

图表示学习减轻了做特征工程的工作。
映射得到的向量具有低维(向量维度远小于节点数)、连续(每个元素都是实数)、稠密(每个元素都不为0)的特点。

图嵌入-基本框架：编码器-解码器

假设：G是图，V是节点集，A是无权图，本节仍仅考虑连接信息，不考虑节点信息。
目标是：节点编码后，两节点在嵌入空间中的向量的(余弦)相似度可以反应(近似)两节点在图中的相似度。即
$similarity(u,v)\approx \mathbf{z}_v^{\mathrm{T}} \mathbf{z}_u$
在这里插入图片描述
关键：如何定义节点的相似度。
步骤：

编码器：节点-》d维向量
定义节点在图中的相似度函数： $s imi l a r i t y (u, v)$
解码器：计算两个节点向量的相似度：如 $\mathbf{z}_v^{\mathrm{T}} \mathbf{z}_u$
迭代优化编码器的参数使得图中相似节点的向量数量积大，不相似节点向量数量积小： $similarity(u,v)\approx \mathbf{z}_v^{\mathrm{T}} \mathbf{z}_u$

node embeddings方法是无监督/自监督的，且与下游任务无关。

浅编码器

最简单的编码器-查表
只需要直接优化Z矩阵
对应方法有：DeepWalk，node2vec
在这里插入图片描述

基于随机游走的方法

图机器学习的很多概念可以类比NLP的很多概念

Node Embeddings

包括deepwalk和node2vec

Link Analysis：PageRank

半监督节点分类：标签传播和消息传递(Label Propagation for Node Classification)

在这里插入图片描述

transductive直推式学习：整个过程没有新的节点进入，可以利用所有已有节点的信息，并且预测标签未知节点的标签
inductive归纳式学习：要对新的节点进行预测

任务

在这里插入图片描述

本节考虑属性特征向量 $f_v$

概览

在这里插入图片描述

LP(Label Propagation)，ICA(Iterative classification)往往是用于被图神经网络做对比的模型。

在这里插入图片描述

网络中存在Correlations

上面的模型主要基于图的基本假设：在网络中，homophily是大量存在的，即相近的节点相似。
关于为什么网络中的节点行为是correlated的两种解释：

具有相似属性特征的节点，更可能相连且具有相同类别
社群会影响节点的类别

如何利用这种correlation进行分类？
节点的类别依赖于(1)节点的特征(2)节点邻域的标签(3)节点邻域的特征

算法1-标签传播(Label Propagation)

初始化
已知正类标记为1，已知负类标记为0，未知类别标记为0.5
第一次迭代更新
按照顺序(自己定的)，利用节点周围节点标签的平均值更新当前节点的标签
一直迭代，直到收敛(或者到某次之后停止)

挑战：不保证收敛；仅用到网络连接信息，没有用到节点的属性特征

算法2-Iterative Classification(ICA)

LP/Relational classification没有用到节点的属性特征。
下面提到的ICA则既会用到属性特征 $f_v$ ，又会用到连接信息 $z_v$ 。

方法

训练两个分类器

$\phi_1\left(f_v\right)$ ：仅使用属性特征预测节点标签，被称为“base classifer”
$\phi_2\left(f_v, z_v\right)$ ：即使用节点属性特征，也使用网络连接特征，被称为“relational classifier”

$z_v$ 的计算方法有：考虑领域节点标签数量的直方图；考虑领域节点最多的标签类、考虑领域节点不同标签的数量等

步骤

1.在已经标注好的训练集上，训练两个分类器。
2.迭代直到递归：

在测试集上，对任意节点 $v$ ，使用 $\phi_1\left(f_v\right)$ 预测 $Y_v$ ，再用 $Y_v$ 计算 $z_v$ ，最后用 $\phi_2\left(f_v, z_v\right)$ 预测所有节点的类别 $Y_v$ 。
对每个节点v重复以下操作：
- 利用新预测的 $Y_v$ 更新 $z_v$
- 重新用 $\phi_2\left(f_v, z_v\right)$ 预测 $Y_v$
  3.迭代直到类别稳定或者最大迭代次数达到。

这个算法不能保证收敛

算法的总结

ICA算法可以被抽象为Collective Classification。它基于马尔科夫假设：一个节点是什么类别，取决于它的邻居节点的类别。
Collective Classification包含三步：

构造Local Classifier，初始化所有节点的类别，如训练 $\phi_1$
捕获节点间的相关关系来构造Relational Classifier，如训练 $\phi_2$
Collective Inference：通过网络来传递关系

算法3-Correct&Smooth

可以被视为一种后处理的技巧。在很多榜单中有很好的表现。

步骤

1.在训练集上训练基分类器，无论什么模型，如线性模型，MLP
2.用该基分类器预测所有节点的soft标签(标签向量，值表示概率，不是非0即1的值)
3.使用图结构来Post-process(后处理)2中的预测结果，以获得最终的预测结果。(该步骤分为Correct和Smooth)
- 3.1 Correct step
  核心假设是：在节点 $u$ 上的错误会增加 $u$ 的领域有相似错误的可能性。
  因此，需要分散图上的这种“不确定性”
  步骤：
  1.仅计算有标注节点的error向量，对于没有标注的节点，error向量为0向量。

将1中的error向量拼接得到error矩阵。我们的目标是使该矩阵的值尽可能分散。
下一时刻的errror是由上一时刻的error和上一时刻传播过来的error决定的

Normailized diffusion matrix $\widetilde{A} \equiv D^{-1 / 2} A D^{-1 / 2}$ 具有很好的性质：所有特征值在[-1,1]；特征值为1的特征向量为 $D^{1/2}\bold{1}$ ( $\bold{1}$ 是全1的向量)； $\widetilde{\boldsymbol{A}}^K$ 的特征值也都是[-1,1]，且最大特诊值一定是1

在这里插入图片描述

s是超参数，最后再执行归一化

- 3.2 Smooth step

类似Correct step，不过矩阵换成了Z矩阵，它是表示标签的矩阵。
注意有标注的训练集的标签向量要修改成真实标签向量

在这里插入图片描述

C&S可以和GNN结合

算法4-Loopy Belief Propagation

定义

label-label potential matrix $\psi$ ：反映了节点和它的邻居之间的依赖关系。矩阵的元素 $\boldsymbol{\psi}\left(Y_i, Y_j\right)$ 表示当邻居节点 $i$ 为类别 $Y_i$ 时，节点 $j$ 为类别 $Y_j$ 的概率。
Prior belief $\phi$ ： $\phi\left(Y_i\right)$ 是 $i$ 为类别 $Y_i$ 的概率。
$m_{i \rightarrow j}\left(Y_j\right)$ ：表示节点 $i$ 认为节点 $j$ 是类别 $Y_j$ 的概率。
$\mathcal{L}$ ：所有类/标签的集合

在这里插入图片描述

如果图中又换，会导致消息反复传递

在实际情况下，环的影响还是比较弱的，所以还是可以用的。

优缺点

优点：易编程和并行；potential matrix可以设置成更高阶，如 $\boldsymbol{\psi}\left(Y_i, Y_j, Y_k, Y_v \ldots\right)$
挑战：不保证收敛，尤其是有环的时候
potential functions的参数需要通过训练得到。

算法5-Masked Label Prediction

自监督的方法，受到NLP的Bert的启发。
在这里插入图片描述

总结

在这里插入图片描述

深度学习基础

在这里插入图片描述

图神经网络综述和学习路径

在这里插入图片描述

图和节点的嵌入表示应该与节点的编号顺序无关。(置换不变性)
编号不一样，但本质上是同一个节点的两个节点，得到的图嵌入向量应该是一样的。

通过消息传递的框架设计具有置换不变性的图神经网络。

图卷积神经网络-构建计算图

核心思想：基于局部邻域构建产生节点的嵌入
在这里插入图片描述

每个节点分别构建自己的计算图
每个计算图就是一个单独的样本
所有黑色盒子公用一套权重，所有白色盒子也公用一套权重
图神经网络的层数是指计算图的层数，而不是神经网络的层数，如上图是两层的图神经网络
k层图神经网络其实就是k hops的节点，如2层，就是看邻居的邻居。
图神经网络不能太深，如果太深，所有节点都会很类似，会产生过拟合。所以一般2-3层就够了

图卷积神经网络GCN

图卷积神经网络-计算图

在这里插入图片描述

图卷积神经网络-数学形式

第0层的嵌入就是节点的属性特征

如果没有属性特征，可以设置全1向量，或者按照标签设置成one-hot向量

转化为矩阵形式

row normalized matrix的最大特征值为1

row normalized matrix在考虑归一化的时候，只除了自己的度，即只考虑了自己的度，没有考虑对方的度。
优化row normalized matrix，提出Naively Symmetric Normalized Matrix：它是对称矩阵，即考虑了自己的度，也考虑了对方的度
再优化，得到Symmetric Normalized Matrix：它是对称矩阵，最大特征值为1

如果节点 $i$ 和节点 $j$ 是相连的，则权重为 $\frac{1}{\sqrt{d_i} \sqrt{d_j}}$
这个矩阵也被称为Normalized diffusion matrix（Normalized Adjacency Matrix/Symmetric Normalized Matrix）： $\widetilde{\boldsymbol{A}} \equiv D^{-1 / 2} \boldsymbol{A} D^{-1 / 2}$

图卷积神经网络-计算图-改进

在图中为节点添加到节点自身的环，并改进计算图。
在这里插入图片描述
还可以继续改进，对来自领域节点用一套权重，对来自环的自己的节点用另一套权重

如何训练图神经网络？

需要定义一个损失函数：
在这里插入图片描述

监督学习训练

在这里插入图片描述

无监督学习训练

在这里插入图片描述

GCN属于一种直推式(transductive)的学习，要求在一个确定的图中去学习顶点的embedding，无法直接泛化到在训练过程没有出现过的顶点。
GCN由于卷积的训练过程涉及到邻接矩阵、度矩阵（可理解为拉普拉斯矩阵），节点一旦变化，拉普拉斯矩阵随之变化，也就是你说的需要“重新计算前面的归一化矩阵”，然后重新训练模型，不能“活学活用”，所以是Transductive的。

图神经网络-相比传统方法的优点

通过矩阵分解或者随机游走获得节点嵌入的方法的缺点是：

不能获得新加入节点的嵌入。要获得的话，必须重新计算所有的节点的嵌入
不能捕获很远的两个节点的结构相似性：
没有利用节点，边，图的属性信息

图神经网络的优点：
可以给出新节点的embeddings，冷启动，随来随用。
甚至可以在全图层面泛化
训练时间随着图的规模增大线性增加
可学习参数个数与节点个数无关

GNN vs CNN

在这里插入图片描述

CNN的公式可以改写成类似GNN的形式
CNN：

CNN的领域是固定的
CNN的卷积核权重需要学习获得
CNN不满足置换不变性
GCN：
GCN的领域可以是任意的
GCN的卷积核权重由 $\tilde{A}$ 预定义
GCN满足置换不变性

GNN vs transformer

transformer的核心概念是自注意力，使得每两个单词/节点间都可以互相影响，都可以有注意力权重。
在这里插入图片描述
transformer可以看成是一个全连接词图上的GNN

5.GNN02

节点的邻域决定了计算图。
在计算图上传递和传播信息。

GNN的通用框架

在这里插入图片描述

单一的GNN层框架

GNN层=消息+聚合
目的是为了以一些向量为输入，得到一个向量

消息计算

每个节点产生一个消息，用于后续传递到其他节点。
消息函数： $\mathbf{m}_u^{(l)}=\mathrm{MSG}^{(l)}\left(\mathbf{h}_u^{(l-1)}\right)$
举例：线性消息函数： $\mathbf{m}_u^{(l)}=\mathbf{W}^{(l)} \mathbf{h}_u^{(l-1)}$
在这里插入图片描述

聚合

每个节点会聚合来自其他节点的消息
聚合函数： $\mathbf{h}_v^{(l)}=\mathrm{AGG}^{(l)}\left(\left\{\mathbf{m}_u^{(l)}, u \in N(v)\right\}\right)$
举例：AGG可以是 $\operatorname{Sum}(\cdot), \operatorname{Mean}(\cdot)$ or $\operatorname{Max}(\cdot)$ 聚合器中的任意一种
在这里插入图片描述
聚合的问题是忽略了 $v$ 节点自身的信息。解决办法是计算 $\mathbf{h}_v^{(l)}$ 时，考虑 $\mathbf{h}_v^{(l-1)}$ 。此时消息和聚合应改为：
消息： $\mathbf{m}_u^{(l)}=\mathbf{W}^{(l)} \mathbf{h}_u^{(l-1)} \quad \mathbf{m}_v^{(l)}=\mathbf{B}^{(l)} \mathbf{h}_v^{(l-1)}$
聚合：先利用AGG函数聚合领域的消息，再拼接聚合 $v$ 节点的消息
$\mathbf{h}_v^{(l)}=\operatorname{CONCAT}\left(\operatorname{AGG}\left(\left\{\mathbf{m}_u^{(l)}, u \in N(v)\right\}\right), \mathbf{m}_v^{(l)}\right)$

汇总

在这里插入图片描述

经典的GNN层：GCN

在这里插入图片描述

GCN论文中的经过改进后的消息函数其实是：
$\mathbf{m}_u^{(l)}=\frac{1}{\sqrt{|N(v)|}\sqrt{|N(u)|}} \mathbf{W}^{(l)} \mathbf{h}_u^{(l-1)}$

经典的GNN层：GraphSAGE

GraphSAGE的公式： $\mathbf{h}_v^{(l)}=\sigma\left(\mathbf{W}^{(l)} \cdot \operatorname{CONCAT}\left(\mathbf{h}_v^{(l-1)}, \operatorname{AGG}\left(\left\{\mathbf{h}_u^{(l-1)}, \forall u \in N(v)\right\}\right)\right)\right)$

AGG函数内既包含了消息计算，又包含了一部分聚合
具体地，AGG函数可以是下面的几种：Mean、Pool、LSTM

经典的GNN层：Graph Attention Networks(GAT)

GAT的公式： $\mathbf{h}_v^{(l)}=\sigma\left(\sum_{u \in N(v)} \alpha_{v u} \mathbf{W}^{(l)} \mathbf{h}_u^{(l-1)}\right)$
其中 $\alpha_{v u}$ 是attention weights

Attention机制

为了使不同的邻居节点有不同的重要度，引入attention机制。
注意力权重的计算公式(基于节点的消息)：
$e_{v u}=a\left(\mathbf{W}^{(l)} \mathbf{h}_u^{(l-1)}, \mathbf{W}^{(l)} \boldsymbol{h}_v^{(l-1)}\right) \\ \alpha_{v u}=\frac{\exp \left(e_{v u}\right)}{\sum_{k \in N(v)} \exp \left(e_{v k}\right)}$
函数 $a$ 可以是单层神经网络，并和GAT的其他网络共同训练。
$\begin{aligned} & e_{A B}=a\left(\mathbf{W}^{(l)} \mathbf{h}_A^{(l-1)}, \mathbf{W}^{(l)} \mathbf{h}_B^{(l-1)}\right) \\ & =\operatorname{Linear}\left(\operatorname{Concat}\left(\mathbf{W}^{(l)} \mathbf{h}_A^{(l-1)}, \mathbf{W}^{(l)} \mathbf{h}_B^{(l-1)}\right)\right)\end{aligned}$