Learning Combinatorial Optimization Algorithms over Graphs（强化学习+图神经网络）

基于图神经网络和强化学习的文章

Turning-

520人浏览 · 2023-10-18 20:42:55

Turning- · 2023-10-18 20:42:55 发布

Learning Combinatorial Optimization Algorithms over Graphs（部分精读）

背景

精确算法：不适用于大型数据集；

近似算法：无法确保最优解，目标是在多项式时间内尽可能地接近最优值。近似算法可能会受到弱最优性保证或经验影响，甚至是不可近似问题；

启发式算法：具体问题需具体分析，需要算法设计者进行大量针对特定问题的研究和反复试验。

全文所需定义

基本定义

$G(V,E,ω)G(V,E,\omega)$ ： $V$ 是 $v ec t e x (节点)$ ， $E$ 是 $e d g e (边)$ ， $ω\omega$ 表示边的权重

$μv\mu_v$ ： $v$ 节点的嵌入向量表示

$N (v)$ ： $G$ 中 $v$ 节点的邻居集

$S$ ：表示已经得到的可行解，候选解为 $S‾=V−S\overline{S}=V-S$

$x$ ：为二元决策向量，每一个维度 $x_v$ 表示，如果 $v$ 节点在 $S$ 中，就是1，否则为0

$S^\widehat{S}$ ：强化学习模块中，表示最终状态，即状态的末态

函数定义

$h (S)$ ：将 $S$ 映射到满足问题的特定约束的组合结构

$c (h (S), G)$ ：决定已经得到的可行解质量如何

$Q (h (S), v)$ ：评价函数，即对 $S$ ，加入一个新的节点 $v$ ，该节点可以让 $Q (h (S), v)$ 取到最大值，如下：
$\begin{aligned}S&:=(S,v^*), \mathrm{~where~}v^*:=\text{argmax}_{v\in\overline{S}}Q(h(S),v)\end{aligned}$

$Q^(h(S),v;Θ)\widehat Q(h(S),v;\Theta)$ ：评价函数，较上面更加一般化，具有一个深度学习参数 $Θ\Theta$ ，避免 $Q (h (S), v)$ 在设计上较难的问题（图上的深度学习架构）

$Q^*$ ：表示强化学习问题中的最优 $Q$ 函数

图嵌入

Structure2Vec

structure2vec 根据输入图结构 G 递归地定义网络架构，节点特定的标签或特征 $x_v$ 根据 G 的图拓扑递归聚合，经过几步递归后，网络将为每个节点生成一个新的嵌入，同时考虑到图特征和这些节点特征之间的远程交互。

每一个节点的初始化embedding为0，对于所有v ∈ V ，在第t次迭代同步更新embedding：
$\mu_{v}^{(t+1)}\leftarrow F\left(x_{v},\{\mu_{u}^{(t)}\}_{u\in\mathcal{N}(v)},\{w(v,u)\}_{u\in\mathcal{N}(v)};\Theta\right)$
只有在前一轮所有节点的嵌入更新完成后，才会开始新一轮的遍历节点的嵌入。不难看出，更新还定义了一个过程，其中节点特征 $x_v$ 通过非线性传播函数 F 传播到其他节点。此外，执行的更新迭代越多，节点特征将传播得越远，并在远处节点处非线性聚合。最后，如果一个节点在 T 次迭代后终止，则每个embedding： $μv(T)\mu_{v}^{(T)}$ 的节点将包含有关其 T -hop邻域的信息，这也是GNN的精髓所在。

大量实验表明，GNN不适合层数过深，因此本文的迭代总次数T设定为4.

Parameterizing： $Q^\widehat{Q}$

针对上面提到的式子，可以将非线性变换F具象出来，变为如下式子：
$\mu_{v}^{(t+1)}\leftarrow\mathrm{relu}\big(\theta_{1}x_{v}+\theta_{2}\sum_{u\in\mathcal{N}(v)}\mu_{u}^{(t)}+\theta_{3}\sum_{u\in\mathcal{N}(v)}\mathrm{relu}(\theta_{4}w(v,u))\big)$
其中： $θ4∈Rp\theta_{1}\in\mathbb{R}^{p},\theta_{2},\theta_{3}\in\mathbb{R}^{p\times p}\mathrm{~and~}\theta_{4}\in\mathbb{R}^{p}$ ，这些都是模型参数

针对上面公式：

邻居上的求和是聚合邻居信息的一种方式，该邻居信息对邻居上的排列是不变的
为了使非线性变换更强大，可以在汇集相邻嵌入 $μv\mu_v$ 之前添加更多的relu层

因此到此处，已经求出来了各个节点对应的嵌入向量表达，接着用这些嵌入向量来进一步表示 $Q^(h(S),v;Θ)\widehat Q(h(S),v;\Theta)$ ：
$Q^(h(S),v;Θ)=θ5⊤relu⁡([θ6∑u∈Vμu(T),θ7μv(T)]) \widehat Q(h(S),v;\Theta)=\theta_5^\top\operatorname{relu}([\theta_6\sum_{u\in V}\mu_u^{(T)},\theta_7\mu_v^{(T)}])$
其中： $θ5∈R2p,θ6,θ7∈Rp×p,[⋅,⋅]\theta_{5}\in\mathbb{R}^{2p},\theta_{6},\theta_{7}\in\mathbb{R}^{p\times p},[· , ·]$ 表示连接运算符

分析公式，其本质是：

将节点 $v$ 的嵌入 $μv\mu_v$ 作为节点 $v$ 的代替代
将整张图的池化嵌入 $∑u∈Vμu(T)\sum_{u\in V}\mu_u^{(T)}$ 作为 $h (S)$ 的替代
由于 $Q^\widehat Q$ 的计算用到了 $μv\mu_v$ ，因此其本质上由7个参数来控制： $Θ={θi}i=17\Theta=\{\theta_i\}_{i=1}^7$

图嵌入小结

以前，graph embedding方法需要为每个输入图 $G$ 提供一个真实标签，以便训练 Structure2vec 架构。在那种情况下，嵌入的输出与 softmax 层相关联，因此可以通过最小化交叉熵损失来端到端地训练参数。

由于本例中缺乏训练标签，这种方法不适用于我们的案例。相反，我们使用强化学习对这些参数进行端到端的训练。

训练：Q-learning

强化学习基本元素构成

要训练的函数： $Q^\widehat{Q}$ ，也就是强化学习中的状态-价值函数
State：一个 $p$ 维的向量，表征图G的一系列节点node，即： $∑v∈Vμv\sum_{v\in V}\mu_v$

值得注意的是，针对该论文，状态的末态表示为： $S^\widehat{S}$
Transition：将最新选取的节点，其标签 $x_v$ 的值，置为1即可
Action：节点的选择，选择一个节点 $v$ 放入 $S$ 中
Reward：函数表达为： $r (S, v)$ ，表示采取动作后到达的新状态和原本状态的“解质量”的差值，具体如下：
$\begin{aligned}r(S,v)&=c(h(S'),G)-c(h(S),G)\end{aligned}$
其中 $S′:=(S,v)S^{\prime}:=(S,v)$ ，此时需要注意的是，对于初态： $c(h(∅),G)=0c(h(\emptyset),G)=0$

通过该初值的限制，就可以实现如下等式：
$R(S^)=∑i=1∣S^∣r(Si,vi)=c(h(S^),G) \begin{aligned}R(\widehat{S})=\sum_{i=1}^{|\widehat{S}|}r(S_i,v_i)\end{aligned} =c(h(\widehat{S}),G)$

Policy：基于学习到的 $Q^\widehat{Q}$ 来确定，是一个确定性的贪心策略：
$\begin{aligned}\pi(v|S)&:=\operatorname{argmax}_{v'\in\overline{S}}Q(h(S),v')\end{aligned}$

学习算法

Loss-function：
$(y−Q^(h(St),vt;Θ))2 \begin{aligned}(y-\widehat{Q}(h(S_t),v_t;\Theta))^2\end{aligned}$
其中对于非终态的 $1 - s t e p$ 而言，
$y=γmax⁡v′Q^(h(St+1),v′;Θ)+r(St,vt) \begin{aligned}y=\gamma\max_{v'}\widehat{Q}(h(S_{t+1}),v';\Theta)+r(S_{t},v_{t})\end{aligned}$

有意思的是，对于 $n - s t e p$ 更新来说，这种结构更适合延时奖励的获取，即 $1 - s t e p$ 可能过于短视， $n - s t e p$ 可以对未来奖励的估计更加准确。但是对于 $n - s t e p$ 而言，其和 $1 - s t e p$ 的差异并不体现在 $l oss - f u n c t i o n$ 上，而是体现在目标上，此时 $y$ 的取值变为如下：
$y=∑i=0n−1r(St+i,vt+i)+γmax⁡v′Q^(h(St+n),v′;Θ) y=\sum_{i=0}^{n-1}r(S_{t+i},v_{t+i})+\gamma\operatorname*{max}_{v^{\prime}}\widehat{Q}(h(S_{t+n}),v^{\prime};\Theta)$
对于学习过程，可以生成一批样本之后再进行批量的学习，即从经验回放池中读取一批数据集 $E$ 来进行 $Q^\widehat{Q}$ 函数的更新学习，数据集的形式如下：
$(S_t,a_t,R_{t,t+n},S_{t+n}) \\ R_{t,t+n}=\sum_{i=0}^{n-1}r(S_{t+i},a_{t+i})$
即从经验回放池中，随机抽取 $E$ ，再进行随机梯度更新！

此处的Q- learning(DQN)是一个off-policy方法。众所周知，诸如 Q-learning 之类的强化学习算法比其策略梯度算法的样本效率（sample-efficient）更高。主要是由于策略梯度方法需要在function approximator（函数逼近器）的每次参数更新后获得新策略的策略样本。

伪代码

在这里插入图片描述

评估

(没有仔细去总结！)

1：预训练

2：时间因素

3：精度因素

总结

本文提出了一个端到端的机器学习框架，用于为图上的NP-Hard组合优化问题自动设计贪婪启发式算法。该方法的核心是将deep graph embedding与RL相结合。通过广泛的实验评估，我们证明了与手动设计的贪心算法相比，所提出的框架在学习贪心启发式算法方面的有效性。学习启发式算法的出色性能在多个不同的问题、图类型和图大小上是一致的，这表明该框架是一种很有前途的新工具，用于设计图问题的算法。