[ICLR'20]Graph Information Bottleneck for Subgraph Recognition

## [ICLR'20]Graph Information Bottleneck for Subgraph Recognition

Paper: [OpenReview](https://openreview.net/forum?id=bM4Iqfg8M2k) 
Code: [GitHub](https://github.com/Samyu0304/graph-information-bottleneck-for-Subgraph-Recognition)

### 1. 问题定义

给定图 $G$ 及其标签或性质 $Y$，从 $G$ 中选择一个经过压缩但仍然具有预测能力的子图 $G_{\mathrm{sub}}$。

$$
I(G;G_{\mathrm{sub}})
$$

尽可能小，即子图尽量不保留完整图中的冗余信息。

同时要求子图仍然包含足够的标签信息：

$$
I(Y;G_{\mathrm{sub}})
$$

尽可能大。

### 2. 符号

- $G=(V,E,A,X)$：输入图
- $A\in\{0,1\}^{n\times n}$：邻接矩阵
- $X\in\mathbb R^{n\times d_{\mathrm{in}}}$：节点特征矩阵
- $Y$：图标签或连续性质
- $G_{\mathrm{sub}}$：从 $G$ 中选择的子图
- $H=X^l\in\mathbb R^{n\times d_h}$：GNN 输出的节点表示
- $S\in\mathbb R^{n\times2}$：节点属于子图或补图的软分配矩阵
- $h_G\in\mathbb R^{d_h}$：完整图的向量表示
- $h_{\mathrm{sub}}\in\mathbb R^{d_h}$：子图的向量表示
- $q_{\phi_1}(Y\mid G_{\mathrm{sub}})$：标签预测器
- $f_{\phi_2}(G,G_{\mathrm{sub}})$：互信息 statistics network
- $\theta$：GNN 和子图生成器的参数

经典信息瓶颈中的压缩变量为 $Z$。在本文的子图识别问题中：

$$
Z=G_{\mathrm{sub}}
$$

实际代码计算互信息时，使用的是对应的向量表示：

$$
h_G,\quad h_{\mathrm{sub}}
$$

### 3. 主要目标

论文使用最大化形式：

$$
\max_{G_{\mathrm{sub}}\subseteq G}
I(Y;G_{\mathrm{sub}})
-
\beta I(G;G_{\mathrm{sub}})
$$

等价的最小化形式为：

$$
\min_{G_{\mathrm{sub}}\subseteq G}
-I(Y;G_{\mathrm{sub}})
+
\beta I(G;G_{\mathrm{sub}})
$$

其中：

- $-I(Y;G_{\mathrm{sub}})$：要求子图保留预测 $Y$ 所需的信息；
- $I(G;G_{\mathrm{sub}})$：要求子图删除完整图中的冗余信息；
- $\beta$：控制预测能力与压缩程度之间的权衡。

实际训练还加入 connectivity loss：

$$
\min_{\theta,\phi_1}
\mathcal L_{\mathrm{cls}}
+
\beta\mathcal L_{\mathrm{MI}}
+
\alpha\mathcal L_{\mathrm{con}}
$$

### 4. 主网络：Outer Part

#### 4.1 节点编码

采用赋值式表示：

$$
H
\leftarrow
\operatorname{GNN}_{\theta}(G)
=
\operatorname{GNN}_{\theta}(A,X)
$$

其中：

$$
H\in\mathbb R^{n\times d_h}
$$

每一行 $h_i$ 是节点 $i$ 的上下文表示。

#### 4.2 产生节点分配矩阵

先计算节点分组 logits：

$$
L_S
\leftarrow
\operatorname{MLP}_{\theta}(H)
$$

再计算节点软分配：

$$
S
\leftarrow
\operatorname{Softmax}(L_S)
$$

合并写为：

$$
S
\leftarrow
\operatorname{Softmax}
\left(
\operatorname{MLP}_{\theta}(H)
\right)
$$

其中：

$$
S_{i0}=P(v_i\in G_{\mathrm{sub}}\mid G)
$$

$$
S_{i1}=P(v_i\in\overline{G}_{\mathrm{sub}}\mid G)
$$

#### 4.3 完整图表示

对全部节点表示取平均：

$$
h_G
\leftarrow
\operatorname{MeanPool}(H)
=
\frac{1}{n}\sum_{i=1}^{n}h_i
$$

#### 4.4 子图表示

首先计算软分组表示：

$$
H_{\mathrm{group}}
\leftarrow
S^\top H,
\qquad
H_{\mathrm{group}}\in\mathbb R^{2\times d_h}
$$

其中第一行对应子图：

$$
h_{\mathrm{sub}}
\leftarrow
(H_{\mathrm{group}})_{0,:}
=
(S^\top H)_{0,:}
=
\sum_{i=1}^{n}S_{i0}h_i
$$

第二行对应补图表示，但标签预测主要使用第一行。

因此，主网络的关键赋值关系为：

$$
H
\leftarrow
\operatorname{GNN}_{\theta}(G)
$$

$$
S
\leftarrow
\operatorname{Softmax}
\left(
\operatorname{MLP}_{\theta}(H)
\right)
$$

$$
h_G
\leftarrow
\operatorname{MeanPool}(H)
$$

$$
h_{\mathrm{sub}}
\leftarrow
(S^\top H)_{0,:}
$$

#### 4.5 标签预测

$$
\widehat Y
\leftarrow
q_{\phi_1}(h_{\mathrm{sub}})
$$

分类任务使用：

$$
\mathcal L_{\mathrm{cls}}
\leftarrow
\operatorname{CE}(\widehat Y,Y)
$$

回归任务使用：

$$
\mathcal L_{\mathrm{cls}}
\leftarrow
\operatorname{MSE}(\widehat Y,Y)
$$

它近似实现：

$$
\max I(Y;G_{\mathrm{sub}})
$$

因为：

$$
I(Y;G_{\mathrm{sub}})
=
H(Y)-H(Y\mid G_{\mathrm{sub}})
$$

而 $H(Y)$ 对训练数据而言是常数，所以最小化分类损失近似于最小化：

$$
H(Y\mid G_{\mathrm{sub}})
$$

### 5. 互信息估计器：Inner Part

真实互信息为：

$$
I(G;G_{\mathrm{sub}})
=
D_{\mathrm{KL}}
\left(
p(G,G_{\mathrm{sub}})
\Vert
p(G)p(G_{\mathrm{sub}})
\right)
$$

代码中实际近似的是：

$$
I(h_G;h_{\mathrm{sub}})
$$

由于不知道这些概率分布，作者使用 statistics network：

$$
t
\leftarrow
f_{\phi_2}(h_G,h_{\mathrm{sub}})
$$

并构造 DV 目标：

$$
J(\phi_2;\theta)
=
\mathbb E_{p(h_G,h_{\mathrm{sub}})}
[f_{\phi_2}(h_G,h_{\mathrm{sub}})]
-
\log
\mathbb E_{p(h_G)p(h_{\mathrm{sub}})}
[e^{f_{\phi_2}(h_G,h_{\mathrm{sub}})}]
$$

对于一个 batch，正确配对为：

$$
(h_{G_i},h_{\mathrm{sub},i})
$$

打乱配对为：

$$
(h_{G_{\pi(i)}},h_{\mathrm{sub},i})
$$

batch 互信息下界估计为：

$$
\widehat J
\leftarrow
\frac1B\sum_i
f_{\phi_2}(h_{G_i},h_{\mathrm{sub},i})
-
\log
\left[
\frac1B\sum_i
e^{f_{\phi_2}(h_{G_{\pi(i)}},h_{\mathrm{sub},i})}
\right]
$$

理论上：

$$
J(f_{\phi_2})
\leq
I(h_G;h_{\mathrm{sub}})
$$

并且：

$$
I(h_G;h_{\mathrm{sub}})
=
\sup_f J(f)
\approx
\max_{\phi_2}J(\phi_2)
$$

#### 5.1 内层优化

固定 GNN 和子图生成器，即固定 $h_G,h_{\mathrm{sub}}$，优化：

$$
\phi_2^*
\leftarrow
\arg\max_{\phi_2}
J(\phi_2;\theta)
$$

代码使用梯度下降，因此最小化：

$$
\mathcal L_{\mathrm{inner}}
\leftarrow
-J(\phi_2;\theta)
$$

内层只更新互信息估计器参数 $\phi_2$，不更新 GNN 和 $S$ 生成器。

#### 5.2 外层中的互信息压缩

Outer 会训练主网络。它使用当前训练好的 $f_{\phi_2^*}$ 作为互信息测量器。

$$
(\theta^*,\phi_1^*)
\leftarrow
\arg\min_{\theta,\phi_1}
\left[
\mathcal L_{\mathrm{cls}}
+
\beta J(\phi_2^*;\theta)
+
\alpha\mathcal L_{\mathrm{con}}
\right]
$$

互信息项的梯度路径为：

$$
\frac{\partial J}{\partial h_G},
\frac{\partial J}{\partial h_{\mathrm{sub}}}
\neq 0
$$

其中：

$$
h_G=h_G(\theta),
\qquad
h_{\mathrm{sub}}=h_{\mathrm{sub}}(S(\theta),H(\theta))
$$

因此，梯度会通过 $h_G,h_{\mathrm{sub}}$ 继续影响 $S,H$，最后更新主网络参数 $\theta$。这近似实现：

$$
\min I(G;G_{\mathrm{sub}})
$$

需要区分：$h_G,h_{\mathrm{sub}}$ 是中间张量，不是 optimizer 直接保存的参数。它们具有反向传播梯度路径，但真正被 optimizer 更新的是产生它们的 GNN、selector 和标签预测器参数。

在理论上，Outer 把 $\phi_2^*$ 视为固定；官方代码在 Outer 的 `backward()` 中也会计算互信息网络参数的梯度，但主网络 optimizer 不包含 $\phi_2$，所以该步骤不会更新 $\phi_2$。

因此：

- 内层最大化 $J$：使互信息估计尽可能准确；
- 外层最小化完整损失，其中 $J$ 项使子图尽量删除完整图中的冗余信息；
- Inner 中的 $h_G,h_{\mathrm{sub}}$ 没有通向主网络的梯度，Outer 中则有。

### 6. Connectivity Regularization

先计算软分组邻接矩阵：

$$
A_{\mathrm{group}}
\leftarrow
S^\top AS
$$

其中：

$$
A_{\mathrm{group}}
=
\begin{bmatrix}
\text{子图内部边} & \text{子图到补图的边}\\
\text{补图到子图的边} & \text{补图内部边}
\end{bmatrix}
$$

$S^\top AS$ 本身不是损失，而是一个 $2\times2$ 的软分组邻接矩阵。

论文定义：

$$
\mathcal L_{\mathrm{con}}
\leftarrow
\left\|
\operatorname{Norm}(A_{\mathrm{group}})-I_2
\right\|_F
$$

也就是：

$$
\mathcal L_{\mathrm{con}}
\leftarrow
\left\|
\operatorname{Norm}(S^\top AS)-I_2
\right\|_F
$$

其目标是：

- 增加组内边比例；
- 减少子图与补图之间的跨组边；
- 使节点分配更加明确；
- 鼓励选出的子图在拓扑上更紧凑。

它不严格保证子图连通或全连接。

官方代码使用一个近似实现：

$$
M
\leftarrow
\operatorname{Norm}(S^\top AS)
$$

$$
\mathcal L_{\mathrm{con}}
\leftarrow
\operatorname{MSE}
\left(
\operatorname{diag}(M),
[1,1]
\right)
$$

该损失通过 $S$ 反向传播，主要更新：

- 子图选择 MLP；
- GNN。

它不直接更新互信息估计器。

### 7. 完整训练过程

对于每个 batch，先执行主网络前向计算：

$$
H
\leftarrow
\operatorname{GNN}_{\theta}(G)
$$

$$
S
\leftarrow
\operatorname{Softmax}
\left(
\operatorname{MLP}_{\theta}(H)
\right)
$$

$$
h_G
\leftarrow
\operatorname{MeanPool}(H)
$$

$$
h_{\mathrm{sub}}
\leftarrow
(S^\top H)_{0,:}
$$

$$
\widehat Y
\leftarrow
q_{\phi_1}(h_{\mathrm{sub}})
$$

$$
\mathcal L_{\mathrm{cls}}
\leftarrow
\operatorname{Loss}(\widehat Y,Y)
$$

$$
\mathcal L_{\mathrm{con}}
\leftarrow
\left\|
\operatorname{Norm}(S^\top AS)-I_2
\right\|_F
$$

然后交替优化。

#### Inner optimization

固定 $\theta,\phi_1$ 以及当前 $h_G,h_{\mathrm{sub}}$：

$$
\phi_2^*
\leftarrow
\arg\max_{\phi_2}
J(\phi_2;\theta)
$$

#### Outer optimization

使用当前 $\phi_2^*$，更新 GNN、selector 和标签预测器：

$$
(\theta^*,\phi_1^*)
\leftarrow
\arg\min_{\theta,\phi_1}
\left[
\mathcal L_{\mathrm{cls}}
+
\beta J(\phi_2^*;\theta)
+
\alpha\mathcal L_{\mathrm{con}}
\right]
$$

三个损失分别负责：

- $\mathcal L_{\mathrm{cls}}$：保证子图能够预测 $Y$；
- $J$：删除子图中关于完整图的冗余信息；
- $\mathcal L_{\mathrm{con}}$：使节点选择在拓扑上更紧凑。

最终希望获得：

$$
G_{\mathrm{sub}}^*
\leftarrow
g(G;\theta^*)
$$

它是关于 $G$ 的近似最小充分子图：

- 尽量少保留完整图中的冗余信息；
- 仍然足以预测标签或性质 $Y$；
- 在图结构上相对紧凑。

[ICLR'20]Graph Information Bottleneck for Subgraph Recognition

Paper: OpenReview
Code: GitHub

1. 问题定义

给定图 $G$ 及其标签或性质 $Y$，从 $G$ 中选择一个经过压缩但仍然具有预测能力的子图 $G_{\mathrm{sub}}$。

$$ I(G;G_{\mathrm{sub}}) $$

尽可能小，即子图尽量不保留完整图中的冗余信息。

同时要求子图仍然包含足够的标签信息：

$$ I(Y;G_{\mathrm{sub}}) $$

尽可能大。

2. 符号

$G=(V,E,A,X)$：输入图
$A\in\{0,1\}^{n\times n}$：邻接矩阵
$X\in\mathbb R^{n\times d_{\mathrm{in}}}$：节点特征矩阵
$Y$：图标签或连续性质
$G_{\mathrm{sub}}$：从 $G$ 中选择的子图
$H=X^l\in\mathbb R^{n\times d_h}$：GNN 输出的节点表示
$S\in\mathbb R^{n\times2}$：节点属于子图或补图的软分配矩阵
$h_G\in\mathbb R^{d_h}$：完整图的向量表示
$h_{\mathrm{sub}}\in\mathbb R^{d_h}$：子图的向量表示
$q_{\phi_1}(Y\mid G_{\mathrm{sub}})$：标签预测器
$f_{\phi_2}(G,G_{\mathrm{sub}})$：互信息 statistics network
$\theta$：GNN 和子图生成器的参数

经典信息瓶颈中的压缩变量为 $Z$。在本文的子图识别问题中：

$$ Z=G_{\mathrm{sub}} $$

实际代码计算互信息时，使用的是对应的向量表示：

$$ h_G,\quad h_{\mathrm{sub}} $$

3. 主要目标

论文使用最大化形式：

$$ \max_{G_{\mathrm{sub}}\subseteq G} I(Y;G_{\mathrm{sub}}) - \beta I(G;G_{\mathrm{sub}}) $$

等价的最小化形式为：

$$ \min_{G_{\mathrm{sub}}\subseteq G} -I(Y;G_{\mathrm{sub}}) + \beta I(G;G_{\mathrm{sub}}) $$

其中：

$-I(Y;G_{\mathrm{sub}})$：要求子图保留预测 $Y$ 所需的信息；
$I(G;G_{\mathrm{sub}})$：要求子图删除完整图中的冗余信息；
$\beta$：控制预测能力与压缩程度之间的权衡。

实际训练还加入 connectivity loss：

$$ \min_{\theta,\phi_1} \mathcal L_{\mathrm{cls}} + \beta\mathcal L_{\mathrm{MI}} + \alpha\mathcal L_{\mathrm{con}} $$

4. 主网络：Outer Part

4.1 节点编码

采用赋值式表示：

$$ H \leftarrow \operatorname{GNN}_{\theta}(G) = \operatorname{GNN}_{\theta}(A,X) $$

其中：

$$ H\in\mathbb R^{n\times d_h} $$

每一行 $h_i$ 是节点 $i$ 的上下文表示。

4.2 产生节点分配矩阵

先计算节点分组 logits：

$$ L_S \leftarrow \operatorname{MLP}_{\theta}(H) $$

再计算节点软分配：

$$ S \leftarrow \operatorname{Softmax}(L_S) $$

合并写为：

$$ S \leftarrow \operatorname{Softmax} \left( \operatorname{MLP}_{\theta}(H) \right) $$

其中：

$$ S_{i0}=P(v_i\in G_{\mathrm{sub}}\mid G) $$

$$ S_{i1}=P(v_i\in\overline{G}_{\mathrm{sub}}\mid G) $$

4.3 完整图表示

对全部节点表示取平均：

$$ h_G \leftarrow \operatorname{MeanPool}(H) = \frac{1}{n}\sum_{i=1}^{n}h_i $$

4.4 子图表示

首先计算软分组表示：

$$ H_{\mathrm{group}} \leftarrow S^\top H, \qquad H_{\mathrm{group}}\in\mathbb R^{2\times d_h} $$

其中第一行对应子图：

$$ h_{\mathrm{sub}} \leftarrow (H_{\mathrm{group}})_{0,:} = (S^\top H)_{0,:} = \sum_{i=1}^{n}S_{i0}h_i $$

第二行对应补图表示，但标签预测主要使用第一行。

因此，主网络的关键赋值关系为：

$$ H \leftarrow \operatorname{GNN}_{\theta}(G) $$

$$ S \leftarrow \operatorname{Softmax} \left( \operatorname{MLP}_{\theta}(H) \right) $$

$$ h_G \leftarrow \operatorname{MeanPool}(H) $$

$$ h_{\mathrm{sub}} \leftarrow (S^\top H)_{0,:} $$

4.5 标签预测

$$ \widehat Y \leftarrow q_{\phi_1}(h_{\mathrm{sub}}) $$

分类任务使用：

$$ \mathcal L_{\mathrm{cls}} \leftarrow \operatorname{CE}(\widehat Y,Y) $$

回归任务使用：

$$ \mathcal L_{\mathrm{cls}} \leftarrow \operatorname{MSE}(\widehat Y,Y) $$

它近似实现：

$$ \max I(Y;G_{\mathrm{sub}}) $$

因为：

$$ I(Y;G_{\mathrm{sub}}) = H(Y)-H(Y\mid G_{\mathrm{sub}}) $$

而 $H(Y)$ 对训练数据而言是常数，所以最小化分类损失近似于最小化：

$$ H(Y\mid G_{\mathrm{sub}}) $$

5. 互信息估计器：Inner Part

真实互信息为：

$$ I(G;G_{\mathrm{sub}}) = D_{\mathrm{KL}} \left( p(G,G_{\mathrm{sub}}) \Vert p(G)p(G_{\mathrm{sub}}) \right) $$

代码中实际近似的是：

$$ I(h_G;h_{\mathrm{sub}}) $$

由于不知道这些概率分布，作者使用 statistics network：

$$ t \leftarrow f_{\phi_2}(h_G,h_{\mathrm{sub}}) $$

并构造 DV 目标：

$$ J(\phi_2;\theta) = \mathbb E_{p(h_G,h_{\mathrm{sub}})} [f_{\phi_2}(h_G,h_{\mathrm{sub}})] - \log \mathbb E_{p(h_G)p(h_{\mathrm{sub}})} [e^{f_{\phi_2}(h_G,h_{\mathrm{sub}})}] $$

对于一个 batch，正确配对为：

$$ (h_{G_i},h_{\mathrm{sub},i}) $$

打乱配对为：

$$ (h_{G_{\pi(i)}},h_{\mathrm{sub},i}) $$

batch 互信息下界估计为：

$$ \widehat J \leftarrow \frac1B\sum_i f_{\phi_2}(h_{G_i},h_{\mathrm{sub},i}) - \log \left[ \frac1B\sum_i e^{f_{\phi_2}(h_{G_{\pi(i)}},h_{\mathrm{sub},i})} \right] $$

理论上：

$$ J(f_{\phi_2}) \leq I(h_G;h_{\mathrm{sub}}) $$

并且：

$$ I(h_G;h_{\mathrm{sub}}) = \sup_f J(f) \approx \max_{\phi_2}J(\phi_2) $$

5.1 内层优化

固定 GNN 和子图生成器，即固定 $h_G,h_{\mathrm{sub}}$，优化：

$$ \phi_2^* \leftarrow \arg\max_{\phi_2} J(\phi_2;\theta) $$

代码使用梯度下降，因此最小化：

$$ \mathcal L_{\mathrm{inner}} \leftarrow -J(\phi_2;\theta) $$

内层只更新互信息估计器参数 $\phi_2$，不更新 GNN 和 $S$ 生成器。

5.2 外层中的互信息压缩

Outer 会训练主网络。它使用当前训练好的 $f_{\phi_2^*}$ 作为互信息测量器。

$$ (\theta^*,\phi_1^*) \leftarrow \arg\min_{\theta,\phi_1} \left[ \mathcal L_{\mathrm{cls}} + \beta J(\phi_2^*;\theta) + \alpha\mathcal L_{\mathrm{con}} \right] $$

互信息项的梯度路径为：

$$ \frac{\partial J}{\partial h_G}, \frac{\partial J}{\partial h_{\mathrm{sub}}} \neq 0 $$

其中：

$$ h_G=h_G(\theta), \qquad h_{\mathrm{sub}}=h_{\mathrm{sub}}(S(\theta),H(\theta)) $$

因此，梯度会通过 $h_G,h_{\mathrm{sub}}$ 继续影响 $S,H$，最后更新主网络参数 $\theta$。这近似实现：

$$ \min I(G;G_{\mathrm{sub}}) $$

在理论上，Outer 把 $\phi_2^*$ 视为固定；官方代码在 Outer 的 backward() 中也会计算互信息网络参数的梯度，但主网络 optimizer 不包含 $\phi_2$，所以该步骤不会更新 $\phi_2$。

因此：

内层最大化 $J$：使互信息估计尽可能准确；
外层最小化完整损失，其中 $J$ 项使子图尽量删除完整图中的冗余信息；
Inner 中的 $h_G,h_{\mathrm{sub}}$ 没有通向主网络的梯度，Outer 中则有。

6. Connectivity Regularization

先计算软分组邻接矩阵：

$$ A_{\mathrm{group}} \leftarrow S^\top AS $$

其中：

$$ A_{\mathrm{group}} = \begin{bmatrix} \text{子图内部边} & \text{子图到补图的边}\\ \text{补图到子图的边} & \text{补图内部边} \end{bmatrix} $$

$S^\top AS$ 本身不是损失，而是一个 $2\times2$ 的软分组邻接矩阵。

论文定义：

$$ \mathcal L_{\mathrm{con}} \leftarrow \left\| \operatorname{Norm}(A_{\mathrm{group}})-I_2 \right\|_F $$

也就是：

$$ \mathcal L_{\mathrm{con}} \leftarrow \left\| \operatorname{Norm}(S^\top AS)-I_2 \right\|_F $$

其目标是：

增加组内边比例；
减少子图与补图之间的跨组边；
使节点分配更加明确；
鼓励选出的子图在拓扑上更紧凑。

它不严格保证子图连通或全连接。

官方代码使用一个近似实现：

$$ M \leftarrow \operatorname{Norm}(S^\top AS) $$

$$ \mathcal L_{\mathrm{con}} \leftarrow \operatorname{MSE} \left( \operatorname{diag}(M), [1,1] \right) $$

该损失通过 $S$ 反向传播，主要更新：

子图选择 MLP；
GNN。

它不直接更新互信息估计器。

7. 完整训练过程

对于每个 batch，先执行主网络前向计算：

$$ H \leftarrow \operatorname{GNN}_{\theta}(G) $$

$$ S \leftarrow \operatorname{Softmax} \left( \operatorname{MLP}_{\theta}(H) \right) $$

$$ h_G \leftarrow \operatorname{MeanPool}(H) $$

$$ h_{\mathrm{sub}} \leftarrow (S^\top H)_{0,:} $$

$$ \widehat Y \leftarrow q_{\phi_1}(h_{\mathrm{sub}}) $$

$$ \mathcal L_{\mathrm{cls}} \leftarrow \operatorname{Loss}(\widehat Y,Y) $$

$$ \mathcal L_{\mathrm{con}} \leftarrow \left\| \operatorname{Norm}(S^\top AS)-I_2 \right\|_F $$

然后交替优化。

Inner optimization

固定 $\theta,\phi_1$ 以及当前 $h_G,h_{\mathrm{sub}}$：

$$ \phi_2^* \leftarrow \arg\max_{\phi_2} J(\phi_2;\theta) $$

Outer optimization

使用当前 $\phi_2^*$，更新 GNN、selector 和标签预测器：

$$ (\theta^*,\phi_1^*) \leftarrow \arg\min_{\theta,\phi_1} \left[ \mathcal L_{\mathrm{cls}} + \beta J(\phi_2^*;\theta) + \alpha\mathcal L_{\mathrm{con}} \right] $$

三个损失分别负责：

$\mathcal L_{\mathrm{cls}}$：保证子图能够预测 $Y$；
$J$：删除子图中关于完整图的冗余信息；
$\mathcal L_{\mathrm{con}}$：使节点选择在拓扑上更紧凑。

最终希望获得：

$$ G_{\mathrm{sub}}^* \leftarrow g(G;\theta^*) $$

它是关于 $G$ 的近似最小充分子图：

尽量少保留完整图中的冗余信息；
仍然足以预测标签或性质 $Y$；
在图结构上相对紧凑。

富婆饿饿饭饭

[ICLR'20]Graph Information Bottleneck for Subgraph Recognition