《Graph Information Bottleneck》论文解读

论文传送门：click here

Code：GIB(github.com)

论文动机

本篇论文是2020Neurips上的论文。

这篇论文将信息瓶颈理论创新性地应用于图神经网络中，具体来说，文章核心围绕着信息瓶颈理论的——minimal sufficient 特点展开的，从理论推导、实例化、实验证明等方面证明了这种方法的重要性。

信息瓶颈理论的最小-充足特点，能够在保证特征表达的同时很好地提高模型的鲁棒性。但其若直接应用在图上，会有两个较大的问题：

• IB 的模型假设数据集中的训练示例是独立的和同分布的（i.i.d$i.i.d$）。对于图结构数据，这个假设不再成立。
• 结构信息对于表示图结构数据是必不可少的。

因此如何建模这个问题至关重要。如何将IB理论迁移到图中，让我们正式开始了解这篇论文的内容。

---

前置理论

图上的信息瓶颈理论

图信息瓶颈的核心公式如上图所示，旨在增加潜在表示 Z$Z$ 与目标 Y$Y$ 之间的互信息，同时减少潜在表示 Z$Z$ 与原始特征 X$X$ 之间的互信息。这也就是所谓的“最小 - 充足”原则。

针对之前提到的两个问题，文中使用local-dependence assumption来限制 P(Z|D)$P(Z|D)$ 的搜索域，同时运用Markov chain来逐层对feature和structure进行提取，使IB原则迁移到图中。

local-dependence assumption

local-dependence assumption：点 v$v$ 只与他 k$k$ 跳邻居有关，与其他节点是独立的。

Markov chain

Markov chain：第 l$l$ 层图结构信息只与原始图结构 A$A$ 和第 l−1$l-1$ 层特征信息有关，第 l$l$ 层特征信息只与第 l$l$ 层图结构信息和第 l−1$l-1$ 层特征信息有关。

所以优化目标函数：

实际上就是在优化两个分布：P(Z(l)X|Z(l−1)X,Z(l)A), P(Z(l)A|Z(l−1)X,A)$\mathbb{P}(Z_X^{(l)}|Z_X^{(l-1)},Z_A^{(l)}),\mathbb{P}(Z_A^{(l)}|Z_X^{(l-1)},A)$。

GIB的变分界

具体证明可在appendix中找到。

(1) I(Y;Z(L)X)$I(Y;Z_X^{(L)})$ 的下界：

为什么我看附录感觉第二个加号应该是减号

(2) I(D;Z(L)X)$I(\mathcal{D};Z_X^{(L)})$ 的上界：

所以模型中优化函数实际上优化的是GBI的上界。

---

方法论

算法过程

本文给出了两个GIB使用方法：GIB-Cat（基于categorical distributions）和GIB-Bern（基于Bernoulli distribution）。

第三步的邻居采样应用了图注意力机制网络（GAT）来计算目标节点邻居的注意力。

此外：

• GIB-Cat将注意力值作为分类分布的参数，从多跳邻居中采样 k$k$ 个节点构成 Z(l+1)A,v$Z_{A,v}^{(l+1)}$（Algorithm 2）
• GIB-Bern则是将注意力值（softmax替换为sigmoid）作为对邻居分别独立采样的伯努利分布的参数（Algorithm 3）

第3、7步使用了重参数化技巧。

训练目标

• AIBˆ$\widehat{AIB}$的估计：对于两种分布

  

• XIBˆ$\widehat{XIB}$的估计：假设 Q(Z(l)X)$\mathbb{Q}(Z_X^{(l)})$ 服从混合的高斯分布，具体而言，每一个点的分布服从于若干高斯分布的加权求和，其中权重、均值、方差是可学习的。

  

至此便有：I(D;Z(L)X)→∑l∈SAAIBˆ(l)+∑l∈SXXIBˆ(l)$I(\mathcal{D};Z_X^{(L)})\to \sum _{l\in S_A}{\widehat{\mathrm{A}\mathrm{I}\mathrm{B}}}^{(l)}+\sum _{l\in S_X}{\widehat{\mathrm{X}\mathrm{I}\mathrm{B}}}^{(l)}$。

• I(Y,Z(L)X)$I(Y,Z_X^{(L)})$的估计：通过忽略常量，得

  

至此完成了理论到实际的转换。

---

实验设置与结果

本文针对性的对鲁棒性进行了验证。

• 鲁棒性检验，使用Nettack方式，两种测试模式：模型训练后攻击（Evasive）和模型训练前攻击（Poisoning）。

  

• 消融实验，使用不停地训练目标

  

  只使用AIB或XIB，那岂不是没有了特征与目标之间的训练？？？

• 对节点特征的噪声攻击：

  

---

可能深入方向

本文图的结构服务于特征 Z$Z$ 的生成，并没有显式的计算结构熵，或许可以将结构熵加入，进一步简化图本身的复杂度，来更好的对信息进行抽取。