《Learning Graph Representation via Graph Entropy Maximization》论文解读

论文传送门：click here

code：GeMax(github)

论文任务与个人想法

本工作来自于2024ICML。

文章的任务是图表示学习，其不仅对每一张图上的每个节点得到编码，更在图整体上得到关于图的编码。本文提出了一种利用正交表示进行图熵最大化的近似方法。

整篇文章读下来，有让我眼前一亮的感觉，是让我觉得蛮有意思的一篇文章。

文章运用了其他文献未运用的，基于独立集表示的熵的表示方法。在计算中，用到了“vertex-packing polytope（$VP(G)$）”概念，但是计算复杂，文章论述了为什么不能用下界进行训练。为了简化问题，文章取了其子集，并在正交表示的条件下给出了一条定理，从而转化为一定条件下的优化问题——规避了复杂的求解独立集的过程。更进一步，将条件转化为优化，使得模型能够学习。

总的来说，我认为论文的亮点如下：

• 如何理解文中最大化交叉熵的目的。

• 找到了正交表示和$VP$之间的一个很妙的关系。

• 规避了求解独立集的过程，使得计算成为可能。

• 将有条件的优化问题转化为无条件的优化问题。

光看这一部分大概率是不了解其具体干了什么，那么先往下看，了解完整体内容再回头看，便能够感受到巧妙之处了。

方法论

图熵，但不能简单优化下界

这里的图熵是基于独立集定义的，独立集就是集合中任意两个点事没有边相连的。下面这个例子能够较好的展示，其一共有十个独立集：

比如 $b_6$ 就代表 $v_1,v_3$ 所组成的独立集（很好理解吧）。

先引入一个概念：vertex-packing polytope
$$
\mathrm{VP}(G):=\{\boldsymbol a\in\mathbb R^{|V|}:\boldsymbol a=\boldsymbol B\boldsymbol{\lambda}, \boldsymbol{\lambda}\geq0, \sum_i\lambda_i=1\}
$$
得到的 $a_i$ 可以理解为其对整个图的独立集所做的贡献。

那么现在就可以引出本文的图熵了：
$$
H_k(G,P):=\min_{\boldsymbol a\in\text{VP}(G)}\sum_{i=1}^{|G|}-P_i\log(a_i)
$$
其中 $P_i$ 代表第 $i$ 个节点的额概率密度。$\sum P_i=1$，但是注意 $\sum a_i\neq1$ 。我们希望最大化图熵 $\max\limits_{F\in\mathcal F} \mathbb E_{G\sim\mathcal D}\begin{bmatrix}H_k\left(G,P_{F(G)}\right)\end{bmatrix}$。

设图表示函数为 $F_g$，图节点函数为 $F_z$：
$$
\mathbf g^\theta=F_g(\boldsymbol A,\boldsymbol X;\theta)\quad \boldsymbol Z^\phi=F_Z(\boldsymbol A,\boldsymbol X;\phi).
$$
那么定义Boltzmann distribution:
$$
P_i(\mathbf g^\theta,\boldsymbol Z^\phi):=\frac{\exp(-||\boldsymbol z_i^\phi-\mathbf g^\theta||^2)}{\sum_{l\in V}\exp(-||\boldsymbol z_l^\phi-\mathbf g^\theta||^2)}, \forall i\in V
$$
从而最终的优化目标为：
$$
\max_{\theta,\phi} \sum_{j=1}^NH_k\left(G_j,P(\boldsymbol A_j,\boldsymbol X_j;\theta,\phi)\right)
$$
或者可以理解为：
$$
\max_{\theta,\phi}\sum_{j=1}^N\min_{\boldsymbol a\in\mathrm{VP}(G_j)}\sum_{i=1}^{n_j}-P_i(\boldsymbol A_j,\boldsymbol X_j;\theta,\phi)\log(a_i)
$$
这个熵是有下界的：
$$
H(P)-\log\alpha(G)\leq H_k(G,P)
$$
其中 $H$ 就是independent number，而 $\alpha(G)$ 是独立数。

根据这个界去优化的话不直接捕获图结构的任何拓扑信息，且效果不好，因此我们需要一种其他方法来对 $H_k$ 进行估计。

pre解决难以优化的问题

图熵的计算是 NP-hard 问题，显然是不可计算的，因此本文提出了一个vertex-packing polytope子集来减少计算量，当然其意义远不止于此，在后续优化中有很大用处。
$$
\mathrm{VP}_\mathrm{Sub}(G) = \{ a\in\mathbb R^{|V|}:\mathbb 1(a)\in \mathrm{VP}(G), 0\leq a_i\leq 1 \}
$$
接下来求解就在这个子集上进行操作了，减少了求解域的大小。

但这个子集仍然需要计算独立的集合指标矩阵 $B$，这仍然是 NP-hard。

正交表示解决求独立集的复杂问题

首先介绍什么是正交表示，简单来说是模长为1，非相邻节点的编码正交形成的编码集合：
$$
\mathcal T(G):={Z\in\mathbb R^{n\times d}: |z_i|_2=1\ \mathrm{for}\ i=1,2,…,n;z_i^{\top}\boldsymbol z_j=0, \forall(i,j)\notin E}.
$$
本文提出Theorem，我认为这是本文最重要的点：

证明在附录中给出了。

正是因为这个原因，将 $\mathrm{VP}_\mathrm{Sub}(G)$ 条件转化为 $D_a(ZZ^{\top})D_a=D_a^2$。从而优化问题转换为：

那么 ‘s.t.’ 如何在模型中作出限制呢？

从有限制优化到非限制优化

对于上面的第一个约束，采用优化如下目标得到：
$$
\mathcal L_{\mathrm{orth}}(\mathcal G;\phi):=\sum_{j=1}^N\left|M_j\odot\left(\boldsymbol Z_j^\phi(\boldsymbol Z_j^\phi)^\top-\boldsymbol I_n\right)\right|F^2
$$
其中 $M_j=1_{n_j\times n_j}-A_j$ ，脚标代表第 $j$ 个图。事实上就是一个mask矩阵。

对于上面的第二个约束：
$$
\mathcal L_{\mathrm{s-vp}}(\mathcal G;\theta,\phi,\mathcal A):=\sum_{j=1}^N\left|D_{a_j}\left(\boldsymbol Z_j^{\phi}(\boldsymbol Z_j^{\phi})^{\top}\right)\boldsymbol D_{a_j}-\boldsymbol D_{a_j}^2\right|^2
$$

$$
\mathrm{s.t.} 0\leq a_{ij}\leq1, \forall i\in[n_j], \boldsymbol{a}_j\in\mathcal A
$$

这样就大大降低了约束条件。

接下来就是对Loss的优化，因为需要$\max\min$，因此采用交替优化如下两个过程：

• 优化图编码器参数：
  $$
  \theta^{(t+1)},\phi^{(t+1)}=\operatorname*{argmax}_{\theta,\phi}\mathcal J_1(\mathcal G;\theta,\phi,\mathcal A^{(t)})
  $$

  $$
  \mathcal J_1(\mathcal G;\theta,\phi,\mathcal A):=\mathcal L_{H_k}(\mathcal G;\theta,\phi,\mathcal A)-\mu\cdot\mathcal L_{\mathrm{orth}}(\mathcal G;\phi)-\gamma\cdot\mathcal L_{\mathrm{s-vp}}(\mathcal G;\theta,\phi,\mathcal A)
  $$

• 优化 $a$：
  $$
  \mathcal A^{(t+1)}=\underset{\mathcal A\in\mathcal C}{\operatorname*{argmin}}\mathcal J_2(\mathcal G;\theta^{(t+1)},\phi^{(t+1)},\mathcal A )
  $$

  $$
  \mathcal J_2(\mathcal G;\theta,\phi,\mathcal A):=\mathcal L_{H_k}(\mathcal G;\theta,\phi,\mathcal A)+\gamma\cdot\mathcal L_{\mathrm{s-vp}}(\mathcal G;\theta,\phi,\mathcal A)
  $$

特别的，在 $a$ 更新时，用函数将其限制在 $[0,1]$：
$$
\operatorname{Proj}_{[0,1]}\left(\bar a\right)=\begin{cases}0,&\text{if}\ \bar a\leq0,\\1,&\text{if}\ \bar a\geq1,\\ \bar a,&\text{otherwise}.\end{cases}
$$
至此，大功告成！

实验设置与结果

本文实验进行了很多，除了下面的还有很多，都在最终的附录中。

不同原则之间的比较

• InfoMax：最大化图级和节点级表示之间的互信息
  $$
  \phi^*,\theta^*,\varphi^*=\arg\max_{\phi,\theta,\varphi}\sum_{j=1}^{|\mathcal G|}\frac1{|V_j|}\sum_{i\in V_j}I_\varphi(\boldsymbol g_j^\theta,\boldsymbol z_{ij}^\phi),
  $$

• Lovasz Principle：其中$\ell_\text{orth}$是正交正则化（orthonormal regularization）
  $$
  \phi^*,\theta^*=\arg\min_{\phi,\theta}\sum_{j=1}^{|\mathcal G|}\max_{i\in V_j}\frac1{\left((z_i^\phi)^\top g_j^\theta\right)^2}+\eta\ell_\text{orth}(\mathcal G;\theta,\phi),
  $$

具体方法可在附录中找到。文章探究了在如上原则与本文提出的最大化图熵的实验效果：

在非监督学习中：

在半监督学习中：

最大化不同熵计算方法之间的比较

• Shannon entropy：
  $$
  J_\mathrm{Sh}(\mathcal G;\theta,\phi)=\sum_j^{|\mathcal G|}\sum_{i\in V_j}-P_i(\mathbf g^\theta,\boldsymbol Z^\phi)\log(P_i(\mathbf g^\theta,\boldsymbol Z^\phi))
  $$

• Renyi entropy：
  $$
  J_\text{Renyi}(\mathcal G;\theta,\phi)=\sum_j^{|\mathcal G|}\frac1{1-\alpha}\log\left(\sum_{i\in V_j}(P_i(\mathbf g^\theta,\boldsymbol Z^\phi))^\alpha\right)
  $$

当然还包括本文中的结构熵，来进行比较。

在非监督学习中：

在半监督学习中：

消融实验、灵敏度分析、本文熵在不同模型上的效果

见附录。