《Recognizing Predictive Substructures with Subgraph Information Bottleneck》论文解读

2024-09-12

深度学习 / 图神经网络

字数统计: 1.2k | 阅读时长≈ 4 分钟

论文传送门：click here

论文动机

本文是TPAMI 2024中的一篇工作。

这个论文其实21年就已经发在网上了，24年这个论文和21年的变化基本不大，目测只加了一个图。

这篇论文目的不是靠信息瓶颈找到一个潜在表示，而是抽象出一个子图结构。整体有着较为完整的推导方式，数学公式很多，有着完备的上下界等等。从实现角度来看，整体网络并不难，远远简单于公式。因此或许这种“意义”+实验好的效果就够了。

整个方法采用了两阶段优化，具体来说分为了内部和外部两个阶段来进行优化。

补：这篇论文是前序工作Graph Information Bottleneck for Subgraph Recognition的补充，添加了更多理论支撑。

方法论

这次我想换个方式进行介绍。本文只介绍其整体思想和能够借鉴的部分，具体内容与推导不在这里说明。

论文的理论出发点为：

下面我们从三个Loss入手吧。

$Loss_{MI}$

内层inner optimization是为了考虑原图和子图之间的互信息。使用了DONSKER-VARADHAN representation于KL散度中，从而直接将互信息运算转换为一个互信息估计函数 $f_{\varPhi2}$ 的身上。

那么复杂的问题转换为仅与 $f_{\varPhi2}$ 有关的一个量，这个量就可以通过网络来学了：

具体流程为：分别用共享参数的GNN获得原图和子图的节点特征表示，进而得到图级别的表示，进而拼接以后经过一层MLP得到互信息估计。

we design a statistics network based on modern GNN architectures as shown by Fig. 1: first, we use a GNN to extract embeddings from both $G$ and $G_{sub}$ (parameter shared with the subgraph generator, which will be elaborated in Section 4.3), then concatenate $G$ and $G_{sub}$ embeddings and feed them into a Multi-Layer Perceptron (MLP), which finally produces the real number.

$Loss_{cls}$

这个量衡量的是子图与标签之间的互信息。

文中提到了两个结论，我觉得能够借鉴，同时也降低实现难度：

maximizing $I(Y; G_{sub})$ is achieved by the minimization of the classification loss between $Y$ and $G_{sub}$ as $L_{cls}$。

we can reduce the estimating error with large training sets and simple prediction models; the KL term decreases when the variational approximation approaches $p(Y ;G_{sub})$

整体过程也很好理解，就是GNN后筛选点，而后进行预测。对应绿色的上半部分。

可能有误：选择节点是直接对原始的emb进行选择，原始emb的邻居都在，但是选择后可能原本的邻居不在了，这就导致子图的emb其实并不是真正子图的emb——因为其用到了被删去的点作为邻居信息聚合。

插一嘴，先说子图如何生成

如图所示，经过GNN后过一个MLP，形成一个 $S \in R^{n\times 2}$ 的矩阵，第 $i$ 行的含义为：
$$
[p(V_i\in G_{sub}|V_i), p(V_i\in \overline G_{sub}|V_i)]
$$
用公式来表示的话：

很好理解。

双层优化流程

红色为内层优化，蓝色为外层优化。

$Loss_{con}$

除了IB中的两个Loss，还有一个 $Connectivity\ Loss$——为什么有这个Loss？

the found subgraph is supposed to be compact. Therefore, we propose the following connectivity loss

Loss定义为：
$$
L_{con} = ||\text{Norm}(S^TAS)-I_2||
$$
怎么去理解这个呢，不妨我们把这个 $2\times 2$ 的矩阵按照元素看一看：
$$
a_{11}=\sum_{i,j}A_{ij}p(V_i\in G_{sub}|V_i), p(V_i\in G_{sub}|V_j) \\
a_{12}=\sum_{i,j}A_{ij}p(V_i\in G_{sub}|V_i), p(V_i\in \overline G_{sub}|V_j)
$$
也就是说，有连边的两个点，最好在一个类别里面——要么都在子图要么都不在。

最终模型实际上干的是这些事：