的学习条件分布及应用解释

论文地址：下载

论文代码：下载

1 简介

使用信息瓶颈的可解释性的图形级表示。

2 符号和预备知识2.1 信息瓶颈

给定输入数据 $X$ 及其标签 $Y$，信息瓶颈的目的是发现一个压缩的潜在表示 $Z$，它在 $Y$ 中提供最大信息。形式上，我们可以通过优化以下优化问题来学习潜在表示 $Z$：

$underset{Z}{max } ;mathcal{L}_{I B}=I(Z ; Y)-beta I(X ; Z)quadquadquad(1)@ >$

其中，$beta$ 表示信息量和压缩量之间的超参数权衡。

互信息 (MI)I(X;Z) 衡量两个随机变量之间的相关性，表示为

$I(X ; Z)= int_{x} int_{z} p(x, z) log frac{p(x, z)}{p(x) p(z)} d x d z $

2.2 GNN 解释

GNN 的解释旨在了解对 GNN 的计算过程至关重要的图的内在信息，从而提供人类可理解的解释。具体来说，给定一个图 $G$ 和一个学习条件分布 $P_{psi}(hat{Z} mid G), mathrm{GNN}$ $psi$) 的 GNN 模型，GNN 解释了目的是学习与GNN的计算结果最相关的解释子图$S$，即：

$underset{S in mathcal{S}}{text{arg max }} operatorname{Score}(S, hat{Z})quadquadquad(2) $

其中，$mathcal{S}$ 表示由图 $G$ 的所有可能子图组成的集合； $operatorname{Score}(S, hat{Z})$ 衡量子图 $ mathcal{S}$ 与 GNN 计算结果 $hat{Z}$ 的相关性。

例如，GNNExcraner[9] 专注于解释有监督的 GNN，并将相关分数 $operatorname{Score}(S, hat{Z})$ 形式化为互信息，即

$S=arg max _{S in mathcal{S}} I(S ; hat{Y})$

其中，随机变量$hat{Y}=hat{Z}$代表分类概率。

3 方法3.1 无监督子图信息瓶颈

在本文中，我们研究了无监督图级表示学习的未探索解释问题。给定由无监督 GNN 提取的图 $G$ 及其对应的表示 $Z$，我们的目标是识别与这些表示最相关的解释性子图 $S$。

根据前面的解释工作[9,10]，我们使用互信息来衡量相关性，所以解释问题被表述为$underset{S}{text{arg max }} I(S ; Z ) 美元。不幸的是，由于 $I(Z ; S) leq I(Z ; G)$ 已经证明存在一个平凡的解 $S=G$（证明见附录 B）。简单的解决方案表明，解释的子图 s 可能包含冗余信息，例如表示 $Z$ 的噪声和不相关信息，受制于成功解释监督网络的 $IB$ 原则 [19]，我们将 $IB$ 原则推广到无监督设置，避免琐碎的解决方案并利用新原理。

定义。 （无监督子图信息瓶颈：USIB）。给定一个图 $G$ 及其表示 $Z$ ，USIB 通过优化问题寻找信息量最大但压缩的解释 $S$

$ underset{S}{text{max } }mathcal{L}_{U S I B}=I(Z ; S)-beta I(G ; S)quadquadquad(3)$

通过优化 USIB 目标，我们可以权衡解释子图的信息量和可压缩性。但是由于USIB目标的优化，互信息涉及到高维数据的整合，难度很大。因此，有必要利用互信息估计方法。

3.2 USIB 优化

我们在 USIB 目标中分别处理 $I(Z ; S)$ 和 $I(G ; S)$ 两个项目。

最大化$I(Z ; S)$

我们采用 Jensen-Shannon MI 估计器 [32,33] 为 $I(Z;S)$ 分配一个近似下界，即

$hat{I}^{J S D}(Z ; S):=sup _{f_{phi}} mathbb{E}_{p(S, Z)}left[-s p左(-f_{phi}(S, Z)right)right]-mathbb{E}_{p(S), p(Z)}left[s pleft(f_{phi}( S, Z)right)right]quadquadquad(4)$

其中$ s p(x)=log left(1+e^{x}right)$是softplus函数；函数 $ f_{phi}: mathcal{S} times mathcal{Z} rightarrow mathbb{R}$ 带有一个可学习的参数 $phi $ 来区分 $S$ 和 $Z$ 的实例是否是从联合分布中采样。由$mathrm{MLP}_{phi_{1}}$和$mathrm{GNN}_{phi_{2}}$的函数组合实现，即：

$f_{phi}left(S^{(k)}, Z^{(k)}right)=operatorname{MLP}_{phi_{1}}left(operatorname{ GNN}_{phi_{2}}left(S^{(k)}right) | Z^{(k)}right)quadquadquad(5)$

其中，$phi=left{phi_{1}，phi_{2}right}$； $|$ 指的是连接运算符。请注意，先前的分布 $p(S, Z)$ 和 $p(Z)$ 在实践中通常是不可达的。结合蒙特卡罗采样逼近先验分布，我们得到一个近似下界$Eq.4$：

$underset{phi}{max} mathcal{L}_{1}(phi, S)=frac{1}{K} sumlimits_{k=1}^{K} -s pleft(-f_{phi}left(S^{(k)}, Z^{(k)}right)right)-frac{1}{K} sumlimits_{k =1, m neq k}^{K} s pleft(f_{phi}left(S^{(k)}, Z^{(m)}right)right)quadquad四边形（6)$

其中，$K$ 是样本数。 $left(S^{(k)}, Z^{(k)}right)$ 从联合分布中采样 $p(S, Z)$, $left(S^{(k)}, Z ^{(m)}right)$ 分别从边际分布 $p(S)$ 和 $p(Z)$ 中独立采样。在实践中，我们通过随机排列对来采样 $left(S^{(k)}，以从联合分布中采样 $left(S^{(k)}, Z^{(k)}right)$ , Z^{(m)}right)$.

最小化 $boldsymbol{I}(boldsymbol{G} ; boldsymbol{S})$

注意解释子图 $H(S)=mathbb{E}_{p(S)}[-log p(S)]$ 的熵提供了 $I(G ; S)$ 一个上因为不等式 $I(G ; S)=H(S)-H(S mid G) leq H(S)$ 成立。然而，由于$S$的先验分布在实践中是未知的，因此很难计算熵。为了解决这个问题，我们考虑放宽，并假设解释图是吉尔伯特随机图[34]，其中边有条件地相互独立。具体来说，令 $(i, j) in mathcal{E}$ 表示图 $G$, $e_{i, j} sim operatorname{Bernoulli}left(mu_{i, j }right)$ 是一个二进制变量，指示是否为子图 $S$ 选择边 $(i, j)$。因此，子图的概率分解为$p(S)=prodlimits _{(i, j) in mathcal{E}} pleft(e_{i, j}right)$，其中$ pleft(e_{i, j}right)=mu_{i, j}^{e_{i, j}}left(1-mu_{i, j}right)^{1- e_ {i, j}}$。这样，我们就可以利用蒙特卡洛抽样得到$I(G ; S)$的一个近似上界，记为

$mathcal{L}_{2}(S)=-frac{1}{K} sumlimits_{k=1}^{K} sumlimits_{(i, j) 在 mathcal{E}} e_{i, j}^{(k)} log mu_{i, j}^{(k)}+left(1-e_{i, j}^{(k) )}right) log left(1-mu_{i, j}^{(k)}right)quadquadquad(1)0@>$

重新参数化技巧

由于不可微采样过程和子图结构的离散性，基于梯度的优化方法可能无法优化 $text{Eq.6}$ 和 $text{Eq.7}$。因此，我们遵循 Gumbel-Softmax 重新参数化技巧 [35, 36] 并将二进制变量 $e_{i, j}$ 放松为连续边权重变量 $hat{e}_{i, j}=sigma( (log epsilon-log (1-epsilon)+ left.left.w_{i, j}right) / tauright) in[0,1]$，其中 $sigma( cdot)$ 是 sigmoid 函数； $epsilon sim operatorname{Uniform}(0,1)@>$; $tau$ 是温度超参数，有 $lim _{tau rightarrow 0} pleft(hat{e} _{i, j}=1right)=sigmaleft(w_{i, j}right)$; $w_{i, j}$ 由网络基于先前计算的神经潜在变量确定工作：

$w_{i, j}^{(k)}=operatorname{MLP}_{theta_{1}}left(mathbf{z}_{i}^{(k)} | mathbf{z}_{j}^{(k)}right) text { with } mathbf{z}_{i}^{(k)}=operatorname{GNN}_{theta_{2 }}left(G^{(k)}, iright), i=1,2, cdotsquadquadquad(1)2@>$

其中，$mathbf{z}_{i}^{(k)}$ 表示节点 $i$ 的节点表示。为了更好的表示，我们表示 $theta= left{theta_{1}, theta_{2}right}$，并通过 $hat{S}^{(k)}=g_{ theta }left(G^{(k)}right)^{3}$ 生成一个松弛子图 $hat{S}$。令 $mu_{i, j}^{(k)}=sigmaleft(w_{i, j}^{(k)}right)$, $text{Eq.7} 在方程 $可以改写为

$mathcal{L}_{2}left(g_{theta}left(G^{(k)}right)right)=-frac{1}{K} sum limits_{k=1}^{K} sumlimits_{(i, j) in mathcal{E}} hat{e}_{i, j}^{(k)} log sigma左(w_{i, j}^{(k)}right)+left(1-hat{e}_{i, j}^{(k)}right) log left(1- sigmaleft(w_{i, j}^{(k)}right)right)quadquadquad(1)3@>$

综上，我们将USIB优化问题$text{Eq.3}$改写为：

$underset{phi, theta}{text{max }} mathcal{L}_{U S I B}(phi, theta, G)=mathcal{L}_{1}left (phi, g_{theta}left(G^{(k)}right)right)-beta * mathcal{L}_{2}left(g_{theta}left(G ^{(k)}right)right)quadquadquad(11)4@>$

我们的方法的概述如图 2 所示。解释子图首先由神经网络生成，然后利用另一个网络来估计解释子图和图表示之间的互信息。最后，子图生成器和互信息估计器被共同优化。最终的解释子图可以通过选择具有前 n 个边权重 $left(hat{e}_{i, j}^{(k)}right)$ 的边来实现。具体算法见附录。

1)5@>

3 个实验

在本节中，我们通过回答以下问题来实证评估我们提出的方法的有效性和优越性。

3.1USIB的有效性

1)7@>

1)8@>

3.2表征的表达性和鲁棒性的影响

3.3 定性分析

4 结论

我们调查一个未探索的解释问题：无监督图表示学习的解释。我们提出了 IB 原则来解决解释问题，从而产生了一种新的解释方法，即 USIB。此外，我们从理论上分析了标签空间上表示和解释子图之间的联系，结果表明表达性和鲁棒性有利于解释子图的保真度。四个数据集和三个目标模型的广泛结果证明了我们方法的优越性和理论分析的有效性。作为未来的研究方向，我们考虑对无监督表示学习的反事实解释[42]，并探索解释和对抗性示例之间是否存在联系[43,44,45]。

修改历史

2022-06-21 创建文章

论文解读目录

参考文献

图论 – 随机图和随机点积图

[22]通过相关游走对图神经网络的高阶解释