l1
Modern deep learning toolbox is designed for simple sequences & grids.
挑战：
大小不固定，复杂拓扑结构
没有固定的节点顺序或参考位置
动态/多模态特征
Heterogeneous Graph（异构图）
定义$G=(V,E,R,T)$.
其中，有节点类型的节点$v_i\in V$，有关系类型的边$(v_i,r,v_j)\in E$，节点类型$T(v_i)$，关系类型$r\in R$
节点和边都有属性/特征。
表征是否是独一无二的？
Bipartite graph (二分图)
节点分两个集合（独立的），边都从一类连接另一类，一个集合内的节点间没有连接。
节点/边，社群/子图，图/图迭代。
- prediction：节点（节点周围的子结构）/边/图级别。
图元（graphlets）：小型、连通的非异构子图，用于捕捉图的局部拓扑结构。
l2 节点嵌入
传统ml：输入图–（特征建模：点/边/图级别的特征）–>结构特征–>学习–>（下游预测任务）
图表征学习：不再需要每次进行特征建模。自动学习到特征。
Embedding：将节点映射到向量：特征表征与嵌入。
将嵌入的向量相似性映射图中的节点相似性。编码网络信息。也可能用于下游预测任务。
编码与解码
需要去定义相似性函数的表达，以将原始图中的similarity映射到embedding空间。
浅层编码shallow encode：直接为每个节点学习一个低维向量表示，而不考虑网络的高阶拓扑结构或节点间复杂的交互关系。
$Z$是编码空间，其中每列是对于一个节点u（除了节点处是1,其他全为0）的embedding表示$z_u$。纵向表示维度，横向每列是一个节点。
解码器基于节点相似性
节点对(u,v)相似的情况下，最大化$z^T_vz_u$。
非监督学习embedding：根据节点周围保留的网络结构。
随机游走randomwalk方法
模型根据$z_u$预测：$P(v|z_u)$，从节点u开始走到v的可能性。（使用非线性函数，柔性最大值、sigmoid等）
则$z^T_vz_u$约等于从节点u开始走到v的可能性：两个向量的偏差（夹角） 与 一个点随机游走到另一个点的概率正相关。
优点：
直观：随机游走能表现邻接或高阶相连的节点信息。
高效：不需要考虑所有节点对，只考虑游走过程中出现的。
$\therefore$ ，让邻域重叠最多的节点在嵌入空间靠近。通过最大似然学习。
给定节点u,我们希望通过学习预测其随机游走邻域$N_{(u)}$中节点的特征表示（类似交叉熵），目标是最大化对数似然。$O(|V|^2)$复杂度。
通过负采样优化为两个sigmoid函数的表示（最大化u和正样本v（邻域节点）的相似度+最小化u和k个负样本（随机无关）的相似度）。复杂度降为$O(|v|)$左右。
k更大：引入偏差/估算更准确。一般k取5-20。
或者使用梯度下降优化寻找最大化方法。
随机游走的优化：
- 进行短距离固定长度随机行走（批量梯度下降）。
- 收集节点u的邻域N(u)
- 通过预测节点u的邻域N(u)来优化它的嵌入方法。
DeepWalk作为后续参考。
node2vec
有偏随机行走。
进行BFS和DFS。
- BFS：局部视角，同质性。发现节点的直接邻居。
- DFS：全局视角，结构性。发现远距离节点的功能相似。
使用了两个超参数用来控制游走偏向：
- 返回参数p：回到上一个节点的概率。p越大越鼓励停留在局部（类似BFS），p越小越鼓励向远方走（DFS）。
- 出入参数q：向内或是向外。q越大，倾向于与上个节点接近的节点。q越小，倾向于远离上个节点的节点。
算法总结：
- 计算每边转移可能性。
- 驱动点从节点u走r的长度。
- 使用梯度下降优化。
在线性时间内完成。三步可以并行。
总之：在嵌入空间的距离反映原始网络中角色或潜在关系。
embedding整个图
法1：嵌入所有点，组合起来。
法2：引入虚节点来嵌入子图：将子图所有节点连这上面。
DiffPool作为参考。
矩阵分解MF
与ml中学的相似，节点嵌入矩阵相乘为图的邻接矩阵。使用ml中类似的最小化误差方法（MSE等）进行回归。
DeepWalk与之类似。
局限性
- 传导性限制：无法处理训练集外新图。统一图重复游走可能不便一致。
- 不能捕捉结构相似。
- 不能利用节点/边本身特征。
解决方案：深度表征学习/GNN。
l3/4/5 图神经网络，图卷积网络
GNN
聚合——>更新——>循环
GNN 信息传递框架，输入图，输出图。
不改变图的连接性，改变顶点/边等的属性。
输入：顶点，边，全局的属性向量。
输出：更新后的属性向量。
最后一层：所有节点共享一个全连接层的数据。
汇聚pooling：找到一个点/边相连的点/边加上全局向量。得到代表那个点/边的向量。
信息传递：某节点+邻居节点再进入更新层。（不加权的卷积？）
用图来理解：
每个图经过一次更新层，获得更远一阶的节点信息。信息传递
顶点的信息到边再到顶点。
全局信息？
消息在点/边之间传递很慢。加入master node（虚拟）。与所有节点（也相当于边）相连。汇聚过程中全部汇聚进入。
GCN，graphsuge
GCN可以认为是很多子图，子图代表向前走k步的汇聚（假设有k层）。
卷积：利用周围的特征。
GCN：单纯是聚合环节与GNN有所不同。解决聚合过程中，周围信息（节点/边）的权值问题。
- 平均池叫GCN,最大池叫graphSUGE
公式上：一个点与另一个点的度数 的几何平均的倒数（拉普拉斯矩阵）作为权值，乘到某个点的卷积中，避免信息差很大在卷积过程中使得一个点的更新受很大影响。
（思想：对称归一化。）
GNN不关注ID只关注特征。所以如果特征不是唯一的，GNN不能区别点
颜色：特征——>embedding.
computationalGraph：计算图。用于表示数学计算过程的有向图，它将复杂的计算分解为一系列节点（Nodes）和边（Edges），直观展示数据流动和运算依赖关系。
GNN中，计算图与每个节点周围的有根子树结构相同。如果有根子树结构不同，根节点用不同颜色表示。（单射）
要求GNN每步单射聚合保留节点周围的邻居信息，包括多次聚合后（高阶子树！）
但GCN和graphSUGE不能完美embedding周围节点：如果数量相同，但类别不同，aggregate后结果是一样的。
所以我们需要单射多集函数，保留数量信息。
GIN
最大化表达：GIN。可学习的Sum聚合 + 多层感知机（MLP），保证邻居信息单射性。基于图同构测试。
color-refine（WL测试一维版）来测试是否同构：每个节点初始化为1，每种数字代表一种颜色。每次聚合根据节点和周围颜色hash得到新颜色。一直聚合直到颜色稳定。
迭代完成时，颜色分布一致，可能同构；不一致，不同构。
GIN与WL图核比较。
还有些gnn不能解决的基本图结构，比如环的不同。
limitations & break
好的GNN：
如果两节点有1相同/2不同的邻居结构，则他们应该有相同/不同的embedding.
但是对于1,当两个节点有相同的邻居结构，我们也可能将他们放到不同的embedding：位置信息，在图中的位置不同。
GNN信息传递的谱分解
GNN三种失效：点/边/图级别，计算图（computational）一致（无法区分）。
- WL核保留了图的对称性。但依赖对称性会无法区分某些非同构图。如下。
- 图的对称性也会保留在谱分解中，即可能导致谱信息的模糊。WL核并不能充分利用谱信息的全部信息。
即谱分解的信息是wl着色的信息的超集。
根据GIN的公式：
所以我们可以把更新过程写成矩阵形式
我们就能将图特征分解为特征值/特征向量，它们表达了整张图隐含的信息。
特征值：宏观性质。最大特征值：最大度/连通性。特征值分布：稀疏/稠密。零特征值：连通分量数。
特征向量：第一特征向量：图中心性。高频特征向量：局部震荡模式。
WL算法的颜色更新仅依赖于不正交于1的特征向量（低频平滑）。
而对称图很多特征向量正交于1（高频振荡）。
使用GNN计算子结构
只需要为节点编ID。可以计算图的闭合循环。
包含位置信息的GNN
节点根据它们的位置/结构性特征在图中被打上标签。
传统GNN因为节点计算图相同会失效。
引入锚点：随机选择一个节点。作为坐标帮助图中节点定位。
拓展：锚点集：锚点越多，对于节点位置的表达越精准。
理论支撑：Bourgain 定理。
。失真率logn。