前置知识：CS224W 图机器学习04：GNN 深入理解、CS224W 图机器学习05：GNN 的训练与预测、 CS224W 图机器学习06：GNN 的理论理解
本节主题：如何使得 GNN 的嵌入更具表示力？
1 图神经网络的局限性
一个"完美"的 GNN 应该具备什么特征？
- 能在邻域结构（无论跃点如何）和节点嵌入之间构建一个单射函数
- 如果两个节点具有相同的邻域结构，则它们必须具有相同的嵌入
- 如果两个节点具有不同的邻域结构，则它们必须具有不同的嵌入
问题 1：虽然两个节点具有相同的邻域结构，但是由于两个节点在图中的位置不同，因此有时需要为它们分配不同的嵌入（位置感知任务 position-aware）
问题 2：GNN 的表现力受到 WL 图同构检验的上限约束，因此如果两个节点具有不同的邻域结构，GNN 很难保证它们具有不同的嵌入（以下图为例，由于 RNN 的信息传播机制不考虑周期性，左图中的 $v_1$ 的嵌入和右图中的 $v_2$ 的嵌入是相同的）
改进思路：
- 将位置信息融入到 RNN 的节点嵌入表示中
- 改善信息传播方式，突破 WL 检验的表现力上限
一个最简单的方式就是对每个节点进行 one-hot 编码，这样就能实现任意节点/边/图的区分；但该方式需要的特征维度过大，并且不能灵活泛化到新节点
2 具备位置感知的 GNN
GNN 通常适用于结构感知任务，而不擅长位置感知人物
解决思路：引入锚定节点
- 对于邻结构相同的两个节点 $v_1$ 和 $v_2$，引入锚定节点 $s_1$
- 两个节点 $v_1$ 和 $v_2$ 与锚定节点 $s_1$ 之间的相对距离不同
- 相当于以锚定节点为坐标轴来定位图中的节点（位置感知）
- 可以引入一组锚点集（Archor-sets）来描述节点的位置信息
定义节点与锚点集间的距离：节点与集合内所有锚定节点的最小距离
P-GNN（位置感知 GNN）的模型细节：
- 对 $n$ 个节点进行随机抽样，得到 $k$ 个锚点集 $S={S_1,S_2,S_3}$；其中锚点集的个数 $k=O(log^2n)$ 的确定依赖布尔甘定理（Bourgain theorem ）
- 在计算节点嵌入时，P-GNN 会同时考虑邻域节点信息和锚点集信息；其中锚点集信息是基于 q-hop 最短路径距离计算得到的位置相似度
- 在聚合信息时，P-GNN 会先用函数 $AGG_M$ 聚合不同邻域的信息，再用函数 $AGG_S$ 聚合不同锚点集的信息；多层迭代得到最终的节点嵌入表示
每次迭代时，都会随机抽样得到一批锚点集用于位置信息感知；因此位置编码的维度可以随机排列，而不会改变其含义（置换不变性）
消息计算函数 $F$ 的公式定义： $$F\left(v, u, \mathbf{h}_{v}, \mathbf{h}_{u}\right)=\frac{1}{d_{sp}^q(u,v)+1} \operatorname{CONCAT}\left(\mathbf{h}_{v}, \mathbf{h}_{u}\right)$$
- $F$ 输入包括 $u,v$ 两个节点及其嵌入表示 $\mathbf{h}{v}, \mathbf{h}{u}$
- $d_{sp}^q(u,v)$ 表示基于 q-hop 算法计算 $v,u$ 节点间的最短路径距离
聚合函数 $AGG_M$ 的公式定义： $$ M_v[i]=AGG_M({F\left(v, u, \mathbf{h}_{v}, \mathbf{h}_{u}\right),\forall u\in S_{i}}) $$ 聚合函数 $AGG_S$ 的公式定义： $$ \mathbf{h}_{v}\leftarrow\mathrm{AGG}_{S}({\mathbf{M}_{v}[i],\forall i\in[1,k]}) $$
在 P-GNN 的原始论文中，AAG 聚合多采用 MEAN 函数
3 具备身份感知的 GNN
GNN 失效的三种场景
- 上图分别展示了节点级别、边级别和图级别的 GNN 失效的情况
- 上图中 GNN 的失效表现：输入不同但对应的 GNN 计算图相同
改进思路：对节点进行区分，标记出需要嵌入的节点（异构消息传递）
ID-GNN：将不同的消息/聚合应用于具有不同颜色的节点
ID-GNN 的核心改动：异构消息传递
- 根据节点类型的不同，使用不同的神经网络函数来计算信息并用于聚合
- 实际操作时，会应用不同的神经网络来进行不同类型节点的嵌入表示计算
ID-GNN 能有效解决刚刚提到的 GNN 失效的问题（上图仅展示了节点级别的情况）
ID-GNN 的简化：ID-GNN-Fast
- 相比于 GNN，ID-GNN 的效果提升是由于纳入了给定节点的周期信息
- 因此可考虑将周期计数值（cycle count）作为节点补充特征纳入 GNN
- 该方式不再需要复杂的异构消息传递，是 ID-GNN 的有效简化版本
4 图神经网络的鲁棒性
对抗性示例的存在阻止了深度学习模型在现实世界中的可靠部署：
- 攻击者可能会尝试主动入侵深度学习模型
- 模型落地性能可能会变得比预期的要差得多
定义两种类型的节点：
- 目标节点 $t$，攻击者希望更改目标节点的预测结果
- 可攻击节点 $S$，攻击者可以修改的节点集合
定义两种类型的攻击：
- 直接攻击：目标节点是可攻击节点，比如修改目标节点属性、或为其添加/删除边
- 间接攻击：目标节点不是可攻击节点，只能针对可攻击节点进行属性或边的修改
攻击者的目标：用尽可能少的修改，最大程度地影响到目标节点的预测
攻击实验的设置：
- 实验模型：一个基于 GCN 的半监督节点分类任务
- 实验数据：论文引文网络（2800 个节点，8000 条边）
- 攻击类型：添加或删除边
- 攻击预算：节点 $v$ 的最大攻击次数为 $d_v+2$（$d_v$ 表示节点 $v$ 的度）
- 攻击方式：使用不同的随机种子进行 5 次训练和攻击
攻击实验的结果：
- 对抗性直接攻击的干扰效果最明显，GCN 的性能下降最快
- 随机攻击明显弱于对抗性攻击，间接攻击也对模型有明显挑战
对抗性攻击，以预测概率变化量最大为目标迭代寻找最优的"干扰操作"