《Graph Information Bottleneck》论文解读

论文传送门：click here

Code：GIB(github.com)

论文动机

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

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

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

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

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

前置理论

图上的信息瓶颈理论

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

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

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

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

所以优化目标函数：
$$
\min_{\mathbb{P}(Z_X^{(L)}|\mathcal{D})\in\Omega}\mathrm{GIB}_\beta(\mathcal{D},Y;Z_X^{(L)})\triangleq\left[-I(Y;Z_X^{(L)})+\beta I(\mathcal{D};Z_X^{(L)})\right]
$$
实际上就是在优化两个分布：$\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_X^{(L)})$ 的下界：

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

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

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

方法论

算法过程

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

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

此外：

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

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

训练目标

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

  

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

  

至此便有：$I(\mathcal D;Z_X^{(L)})\to\sum_{l\in S_A}\widehat{\mathrm{AIB}}^{(l)}+\sum_{l\in S_X}\widehat{\mathrm{XIB}}^{(l)}$。

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

  

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

实验设置与结果

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

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

  

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

  

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

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

  

可能深入方向

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