GGD证明推导学习

GGD证明推导学习

这篇文章，建议先看相关的论文。这篇是我读证明的感悟，因此，不会论文的主体内容

首先，给出命题：

DGI的sumary向量是一个常数

给定一个图： G = { X ∈ R N × D , A ∈ R N × N } \mathcal{G}=\{\mathbf{X}\in\mathbb{R}^{N\times D},\mathbf{A}\in\mathbb{R}^{N\times N}\} G={X∈RN×D,A∈RN×N}，以及一个GNN编码器 $g$，我们将其嵌入表示为：$\mathbf{H}=\sigma (g(\mathcal{G}))$，$\sigma$是非线性激活函数。通过对summary向量s进行激活函数操作，我们可以得到：ReLU，Prelu，LReLU的值为0.5，sigmoid的值为0.62。及：我们可以得到：

$$s=\mathcal{E}I \tag{1}$$

注：这个是有详细的理论证明的，但是不是我阅读的主要部分。详细证明见论文的A.1

GGD与DGI的联系

既然我们知道dgi的summary向量s为1了，那我们就可以简化整个dgi的流程：

简化DGI

假如设置$\mathbf{s}=ϵ\mathbf{I}=\mathbf{I}$，定义区分器为$\mathcal{D}(\cdot )$，我们就可以重写dgi为：

$$\begin{aligned} \mathcal{L}_{DGI}& =\frac1{2N}(\sum_{i=1}^N\log\mathcal{D}(\mathbf{h}_i,\mathbf{s})+\log(1-\mathcal{D}(\tilde{\mathbf{h}}_i,\mathbf{s}))), \\ &=\frac1{2N}(\sum_{i=1}^N\log(\mathbf{h}_i\cdot\mathbf{s})+\log(1-\tilde{\mathbf{h}_i}\cdot\mathbf{s}))), \\ &=\frac1{2N}(\sum_{i=1}^N\log(sum(\mathbf{h}_i))+\log(1-sum(\tilde{\mathbf{h}}_i))), \end{aligned} \tag{2}$$

其中，区分器是：$\mathcal{D}({\mathbf{h}}_i,\mathbf{s})={\sigma }_{sig}({\mathbf{h}}_i\cdot \mathbf{W}\cdot \mathbf{s})$（这个在代码中，是nn.bilinear（如果代码看到这个，公式就是左侧的区分器）

我们定义${\hat{y}}_i=agg({\mathbf{h}}_i)$，那么，整个公式可以简化为：

$$\mathcal{L}_{BCE}=-\frac{1}{2N}(\sum_{i=1}^{2N}y_{i}\log\hat{y}_{i}+(1-y_{i})\log(1-\hat{y}_{i})\tag{3}$$

DGI中的引理：定义 { H g } g = 1 ∣ H ∣ \{\mathbf{H}^{g}\}_{g=1}^{|\mathbf{H}|} {Hg}g=1∣H∣​是一系列从图形中提取到的一系列节点的嵌入，$p(\mathbf{H})$，$\left|\mathbf{H}\right|$是有限数量的元素。$p({\mathbf{H}}^g)=p({\mathbf{H}}^{g\prime })$。$R$是readout函数，其将$H^g$作为输入，summary向量作为输出，${\mathbf{s}}^g$.${\mathbf{s}}^g$遵循边缘分布$p(\mathbf{s})$。我们可以得到：联合分布$p(\mathbf{H},\mathbf{s})$与边缘分布$p(\mathbf{H})\overline{p(\mathbf{s})}$之间最佳分类器错误率的上界是：$E{r}^{\ast }=\frac{1}{2}{\sum }_{g=1}^{|\mathbf{H}|}p({\mathbf{s}}^g{)}^2$

有公式1我们可以得到s是一个常量summary vector $\mathcal{E}I$,$\mathcal{E}$是一个常量。我们可以假设$\mathcal{E}$独立于$p(H)$（实际上，在本文先前的证明中，我们已经证明$\mathcal{E}$是常数。其肯定独立于$p(H)$）。这样，我们就可以退出lemma2：

lemma2 我们假设s是一个summary vector $\mathcal{E}I$,$\mathcal{E}$独立于$p(H)$，我们可以得到最优分类器的错误率是：$E{r}^{\ast }=\frac{1}{2}$

其实，很容易理解：现在$\mathcal{E}$独立于$p(H)$，那自然而然，$p(\mathbf{s})$独立于$p(\mathbf{H})$。这样，预测正确和预测错误都应该为1/2

Theorem 2：给定最佳summary vector $s^{\ast }$，其为联合分布和边缘分布的最佳分类器。${\mathbf{s}}^{\ast }=arqma{x}_{\mathbf{s}}MI(\mathbf{H};\mathbf{s})$

根据理论2，DGI生成最小化分类器D的分类误差可以被使用于最大化MI在输入和readout函数之间的损失。然而，在上述假设下，错误率是一个常数，最小化分类误差是不切实际的。除此之外，由于s是一个常数vector，因此：$MI(\mathbf{H};\mathbf{s})=0$

这样，DGI的推理是有问题的。区分器的作用不是最大化$MI(\mathbf{H};\mathbf{s})$，而是：最大化正嵌入和恒定只要s的相似性和最小化负嵌入和s的相似性。这相当于最大化正嵌入和府前路分布之间的JS偏差。我们给出一个定理来证明这一点：

Theorem 3：假设s是一个常数向量，s独立于$p(H)$，给定图$\mathcal{G}$和扰乱图$\hat{\mathcal{G}}$.$g_{\theta }(\cdot )$是GNN编码器。我们考虑正样本嵌入$g_{\theta }(\mathcal{G})$为$P_{pos}^{\mathbf{h}}$，$g_{\theta }(\tilde{\mathcal{G}})as{P}_{neg}^{\mathbf{h}}$，优化DGI实质上是优化$P_{pos}^{\hat{\mathbf{h}}}和P_{neg}^{\hat{\mathbf{h}}}$JS散度，其中$\hat{h}$是现行变换后的向量。

证明：首先，我们对DGI进行变换

$$\begin{aligned} \text{L}& =\mathbb{E}_{\mathbf{h}\sim P_{pos}^{\mathbf{h}}}log\mathcal{D}(\mathbf{h},\mathbf{s})+\mathbb{E}_{\mathbf{h}\sim P_{neg}^{\mathbf{h}}}log(1-\mathcal{D}(\mathbf{h},\mathbf{s})), \\ &=\mathbb{E}_{\mathbf{h}\sim P_{pos}^{\mathbf{h}}}log(\mathbf{h}\cdot\mathbf{W}\cdot\mathbf{s})+\mathbb{E}_{\mathbf{h}\sim P_{neg}^{\mathbf{h}}}log(1-\mathbf{h}\cdot\mathbf{W}\cdot\mathbf{s}), \\ &=\mathbb{E}_{\mathbf{h}\sim P_{\infty}^{\mathbf{h}}}log(\mathbf{h}\cdot\mathbf{W}\cdot\epsilon)+\mathbb{E}_{\mathbf{h}\sim P_{\infty}^{\mathbf{h}}}log(1-\mathbf{h}\cdot\mathbf{W}\cdot\epsilon), \end{aligned}$$

h是节点嵌入，W是可学习的权重。在这里，我们将$\mathbf{h}\cdot \mathbf{W}$视为$\hat{h}$。正样本采样为$P^{{\hat{\mathbf{h}}}_{pos}}$,负样本采样为：$p^{{\hat{\mathbf{h}}}_{pos}}$。这样，公式就可以重写为：

$$\mathcal{L}=\mathbb{E}_{\hat{\mathbf{h}}\sim P_{pos}^{\hat{\mathbf{h}}}}log(sum(\epsilon\hat{\mathbf{h}}))+\mathbb{E}_{\hat{\mathbf{h}}\sim P_{neg}^{\hat{\mathbf{h}}}}log(1-sum(\epsilon\hat{\mathbf{h}})),\\=\mathbb{E}_{\hat{\mathbf{h}}\sim P_{pos}^{\hat{\mathbf{h}}}}log(\epsilon\cdot agg(\hat{\mathbf{h}}))+\mathbb{E}_{\hat{\mathbf{h}}\sim P_{neg}^{\hat{\mathbf{h}}}}log(1-\epsilon\cdot agg(\hat{\mathbf{h}})),$$

$agg(\cdot )$是sum函数

Theorem 3的详细证明：

（理论推导受到了gan的启发）

$$\begin{aligned}\mathcal{L}&=\mathbb{E}_{\mathbf{h}\thicksim P_{pos}}log(agg(\mathbf{h}))+\mathbb{E}_{\mathbf{h}\thicksim P_{neg}}log(1-agg(\mathbf{h})),\\&=\int_\mathbf{h}P_{pos}(\mathbf{h})log(agg(\mathbf{h}))d\mathbf{h}+\int_\mathbf{h}P_{neg}(\mathbf{h})log(1-agg(\mathbf{h}))d\mathbf{h},\end{aligned}$$

agg是aggregation函数。$P_{pos}$是正样本的分布，$P_{neg}$是负样本的分布。优化损失函数，我们可以得到$agg(h)$的最优解为：$\frac{P_{pos}(\mathbf{h})}{P_{pos}(\mathbf{h})+P_{neg}(\mathbf{h})}$。这是因为$alog(x)+blog(1-x)$在$x=\frac{a}{a+b}$处得到最优解。通过取代$agg(\mathbf{h})$为：$\frac{P_{pos}(\mathbf{h})}{P_{pos}(\mathbf{h})+P_{neg}(\mathbf{h})}$，上述公式可以转换为：

$$\mathcal{L}=\mathbb{E}_{\mathbf{h}\thicksim P_{pos}}log(\frac{P_{pos}(\mathbf{h})}{P_{pos}(\mathbf{h})+P_{neg}(\mathbf{h})})+\mathbb{E}_{\mathbf{h}\thicksim P_{neg}}log(1-\frac{P_{pos}(\mathbf{h})}{P_{pos}(\mathbf{h})+P_{neg}(\mathbf{h})}),\\=\mathbb{E}_{\mathbf{h}\thicksim P_{pos}}log(\frac{P_{pos}(\mathbf{h})}{P_{pos}(\mathbf{h})+P_{neg}(\mathbf{h})})+\mathbb{E}_{\mathbf{h}\thicksim P_{neg}}log(\frac{P_{neg}(\mathbf{h})}{P_{pos}(\mathbf{h})+P_{neg}(\mathbf{h})}).$$

我们发现，其和JS散度很相似：

$$JS(P_1\parallel P_2)=\frac12\mathbb{E}_{\mathbf{h}\thicksim P_1}log(\frac{\frac{P_1}{P_1+P_2}}2)+\frac12\mathbb{E}_{\mathbf{h}\thicksim P_2}log(\frac{\frac{P_2}{P_1+P_2}}2).$$

这样，我们可以重写公式为：

$$\begin{aligned}\mathcal{L}&=\mathbb{E}_{\mathbf{h}\sim P_{pos}}log(\frac{\frac{P_{pos}(\mathbf{h})}{P_{pos}(\mathbf{h})+P_{neg}(\mathbf{h})}}2)+\mathbb{E}_{\mathbf{h}\sim P_{neg}}log(\frac{\frac{P_{neg}(\mathbf{h})}{P_{pos}(\mathbf{h})+P_{neg}(\mathbf{h})}}2)-2log2,\\&=2JS(P_{pos}\parallel P_{neg})-2log2,\end{aligned}$$

因此，最优化L相当于优化JS散度$JS(P_{pos}\parallel P_{neg})$

‍