《Structural Entropy Based Graph Structure Learning for Node Classification》论文解读

2024-07-18

深度学习 / 图神经网络

字数统计: 2.1k | 阅读时长≈ 8 分钟

论文传送门：click here

可参考资料：$CoGSL$

论文动机

本篇论文是2024AAAI上的论文。

由于GNN的性能高度依赖于输入图结构的质量，因此如今学者已经提出了各种**图结构学习(GSL)**技术来增强图结构。

大多数现有的GSL方法都专注于融合从图中提取的不同结构特征（基本视图），但很少包含图语义，例如层次社区。因此，在处理包含来自现实世界复杂系统的噪声的图时，它们可能还不够。

本文结合了信息瓶颈、最大化互信息等理论，通过图增强、编码树、图混合等技术完成了图结构学习，并形成节点的embedding。

小梳理

本篇论文通读下来感觉信息量还是蛮大的，所以在介绍之前我先简单做一个梳理。

本篇论文我理解为是在 $CoGSL$ 后续所做的工作，其最大的贡献是将图视角与编码树视角相结合，不仅最大化图之间、编码与标签之间的互信息，同时还要优化图与编码树之间的互信息，因此本文有很多的篇章来描述编码树如何构造以及损失函数如何定义。

整个流程下图描述的很清晰，再读文章的时候与这张图对照能够更好的了解具体流程。

简单来说，首先对两个得到的图基础视图进行增强，并根据这两张图生成融合后的图。分别对每张图构造编码树，并根据图上的编码得到编码树上每个节点的编码。接下来优化图与图之间、树与树之间、图与数之间、编码与标签之间的互信息即可。

本篇论文我个人感觉就是在不同视角下不断切换，提供更多的互信息优化依据，以得到更好的模型效果。

方法论

前置知识

图的一维结构熵：
$$
H^1(G)=-\sum_{v\in V}\frac{d_v}{vol(G)}\log_2\frac{d_v}{vol(G)}
$$
其中 $d_v$ 代表 $v$ 节点所连边的权重和，$vol(G)=\sum_v d_v$

编码树的 $K$ 维结构熵：
$$
H^{K}(G)=\min_{\mathcal{T}}\sum_{\alpha\in\mathcal{T},\alpha\neq\lambda}H^{\mathcal{T}}(G;\alpha),\quad\quad H^{\mathcal{T}}(G;\alpha)=-\frac{g_\alpha}{vol(G)}\log_{2}\frac{\mathcal V_\alpha}{\mathcal V_{\alpha^-}}
$$
$\alpha$ 为树上结点，$\lambda$ 为根节点，其中包含图上的所有node。$g_\alpha$ 是从点 $\alpha$ 连向外部的边权之和，$\mathcal V_a$ 是$\alpha$ 内图节点所连边权的和 $\mathcal V_\alpha=\sum_{v\in T_\alpha} d_v$，$\alpha^-$是 $\alpha$ 节点的父节点。

理论优化思想

图结构学习能够用以下公式刻画：
$$
\mathcal L_{gsl}=\mathcal L_{cls}(Z^\star,Y_L)+\mu\mathcal L_{reg}(A^\star,Z^\star,A)
$$
前者是编码与标签的关系，后者是重建的图结构与原始图结构、标签之间的约束。

在本文总，采用信息瓶颈理论进行建模：
$$
GIB(G,Y;Z^\star)=\max_{\boldsymbol{Z}}\left[I(\boldsymbol{Z};Y)-\beta I(\boldsymbol{Z};G)\right]
$$
旨在最大化编码与标签的关系，同时希望从图 $G$ 中提取较少的信息即可。但是 $I(Z,G)$ 的计算是困难的，因此转化问题（感觉可以借鉴）：
$$
\min_{G_{s}}\max_{\boldsymbol{Z}}I(\boldsymbol{Z};Y_{L})+\beta I(\boldsymbol{Z};G_{s}) \ s.t.,H^{1}(G)>H^{1}(G_{s}),I(G;Y_{L})=I(G_{s};Y_{L})
$$
其中 $G_s$ 为 $G$ 的采样子图。也就是说提取较少有用信息这个限制通过 $G_s$ 来进行限制，换句话来说，其保证了捕获节点分类的最小和充分信息。

但是方法中具体而言并不是直接优化这个式子，而是采用不同损失来实现这个思想。

理论方法

首先根据 $CoGSL$ 方法，生成两个基础视图的图结构 $G^1,G^2$。

图增强

接下来对图进行增强，使用 GCN 网络得到每个节点的编码 $z_i$，根据余弦相似度计算出节点对之间的相似度。进一步，根据这些相似度，构造 $kNN$ graph，而 $k$ 的选择需要满足图结构熵的最小：
$$
H^1(G^1_{k-1}) \geq H^1(G^1_{k}) \leq H^1(G^1_{k+1})
$$
最终增强后的图为 $G_{en}^1=G^1+\xi G_k^{1}$，$G^2_{en}$ 同理。

编码树的构建

构建目标依旧用到了熵思想：
$$
\mathcal{T}^{\star}=\underset{\forall\mathcal{T}:height(\mathcal{T})\leq K}{\arg\min}(H^{\mathcal{T}}(G))
$$
为了构建一个树，有三种操作：

合并：对于两个community $P_i,P_j$，合并操作 $op_m(P_i,P_j)$ 后剩下的community集合为 $\mathcal{P}=\{P_{1},…,P_{i-1},P_{i+1},…,P_{j-1},P_{j+1},…,P_{c},P_{x}\}$

另外文中给出了合并后的结构熵变化，我理解与决策树中的信息增益类似。选择信息增益最大的一对进行合并。
压缩：$op_c(\mathcal P)$ 即将 $\mathcal P$ 内的所有community分别压缩成一个点，边权为之前若干边权的和。
更新：$op_u(\mathcal T,\mathcal P)$ ，将 $\mathcal P$ 内部所有的community作为 $\mathcal T$ 的叶子结点。

算法过程为：

感觉跟决策树、霍夫曼编码思想相似。

最终合并图结构的构建

合并的适合考虑了community之间的关系，也就是说考虑了编码树。定义叶子结点的社区影响：
$$
\varepsilon_{\alpha}=\frac{H^{\mathcal T}(G;\alpha)}{\sum_{\delta\in\mathcal T}H^{\mathcal T}(G;\delta)}
$$
其中 $\delta$ 是从树根 $\lambda$ 到 $\alpha$ 路径上的点。

接下来获得系数 $a$，以 $G^1$ 为例：
$$
a_i^1=\frac{\sigma(\pi_i^1)\cdot\pi_i^1+\sigma(\varepsilon_i^1)\cdot\varepsilon_i^1}{\sigma(\pi_i^1)+\sigma(\varepsilon_i^1)}
$$
其中 $\sigma(·)$ 是激活函数，$\pi_i^1$ 是 $v_i$ 对 $G^1$ 的预测置信度（方法与$CoGSL$）一致。

进一步获得权重：
$$
w_i^1=a_i^1/(a_i^1+a_i^2),\quad w_i^2=a_i^2/(a_i^1+a_i^2)
$$
然后便能得到融合后的图了：
$$
G_i^\star=w_i^1\cdot G_{en,i}^1+w_i^2\cdot G_{en,i}^2
$$

双目标优化损失

第一个损失当然是预测准确率的交叉熵：
$$
\mathcal L_{cls}=\sum_{i=1}^2\mathcal L_{cross}(\Pi^i,Y_L)+\mathcal L_{cross}(\Pi^\star,Y_L)
$$
第二个就略有复杂了。

我们先定义编码树上除去叶节点的编码方式（因为叶节点每个节点代表图上一个点，他的编码就是GCN得到的）：
$$
h_\alpha=\sum_{i=1}^m\left[\frac{h^{\mathcal{T}}(G;\alpha^{\langle i\rangle})}{\sum_{j=1}^mh^{\mathcal{T}}(G;\alpha^{\langle j\rangle})}h_{\alpha\langle i\rangle}\right]
$$
其中 $m$ 代表的是 $\alpha$ 的子节点。

这样我们就能够刻画节点与树之间的信息关系了：
$$
\mathcal L_{hc}(\boldsymbol Z;\mathcal{T})=-\sum_{l=2}^K\theta_l\log_2\sum_{i=1}^n\frac{sim(\boldsymbol z_i,\boldsymbol h_{(i,l)})}{\sum_{j=1,j\neq i}^nsim(\boldsymbol z_j,\boldsymbol h_{(j,l)})},\quad \theta_l=\gamma(1-\gamma)^l
$$
$h_{(i,l)}$ 是节点 $v_i$ 的第 $l$ 层community在 $\mathcal T$ 中的嵌入。这样每一组图和编码树之间的损失定义为：
$$
\mathcal L_{mmp}^1=\mathcal L_{cross}^1(\Pi^1,Y_L)+\mathcal L_{hc}(Z^1;\mathcal{T}^1)
$$
因为共有三组（$G^1,G^2,G^\star$），因此 $\mathcal L_{mmp}=\mathcal L_{mmp}^{1}+\mathcal L_{mmp}^{2}+\mathcal L_{mmp}^{\star}$

除此之外，还要最大化不同组之间的互信息：
$$
\mathcal L_{miet}(\mathcal{T}^1,\mathcal{T}^2)=\frac{1}{2}\left[\mathcal L_{hc}(Z^1;\mathcal{T}^2)+\mathcal L_{hc}(Z^2;\mathcal{T}^1)\right]
$$
最终才能得到第二个损失优化目标（太复杂了）：
$$
\mathcal L_{ve}=\mathcal L_{mmp}+(\mathcal L_{miet}(\mathcal T^{1},\mathcal T^{2})+\mathcal L_{miet}(\mathcal T^{1},\mathcal T^{\star}) +\mathcal L_{miet}(\mathcal T^{2},\mathcal T^{\star}))
$$