0-学习求解具有异质性的组合优化问题（完）

Abstract

图神经网络（GNNs）被广泛应用于解决组合优化问题。然而，许多流行的 GNNs 难以推广到异质性场景，即相邻节点往往具有不同标签或不相似特征的场景，例如图着色问题。此外，大多数现有方法通常是针对特定实例进行优化，缺乏泛化能力。为了解决这些限制，我们提出了一种创新的自监督预训练和微调框架 HOCO，用于解决具有异质性的组合优化问题。该框架采用了一种异质图编码器，通过分离节点及其邻居来捕捉异质性。此外，我们的模型还融入了双层优化策略：在节点层面，对比学习有助于增强相邻节点表示的区分度；在图层面，结构熵优化用于细化全局聚类结构。实验结果表明，我们的模型在图着色和最大 k 割问题上表现出色，与各种基线算法相比，显著提高了准确性、泛化能力和计算效率。

1. Introduction

在现代科学和工程领域，组合优化（CO）问题比比皆是（Brouer, Alvarez, Plum, Pisinger, & Sigurd, 2014；Li, Chu, Feng, Chu and Zhou, 2018；Perboli & Rosano, 2019），这些问题涉及在特定约束和有限资源下寻找最优解。由于图提供了一个自然且强大的工具来表示和处理实体间的关系，许多 CO 问题可以转化为图优化问题。尽管传统算法在某些场景下（Halim & Ismail, 2019；Yu, Liao, & Yang, 2023；Zhao, Di, Cao, & Tang, 2021）十分有效，但对于大规模的 NP-hard CO 问题实例，它们常常面临计算复杂度高和性能不理想等问题。随着深度学习的兴起，特别是神经网络在各种任务中展现的惊人能力，越来越多的人开始关注利用这些技术来解决 NP-hard CO 问题（Kool, Hoof, & Welling, 2018；Lei, Guo, Wang, Wu, & Zhao, 2022；Li, Chen and Koltun, 2018；Liu, Wang, Cao, Liu, & Shen, 2022）。

许多 CO 问题表现出同质性，即相邻节点往往具有相同的标签或相似的特征。例如，平衡图划分问题（BGP）旨在将图划分为大小大致相等的 𝑘 个子图，以最小化不相连子图之间的边总数，这等同于最大化这些子图内部的边数。因此，相邻节点很可能被分到同一个子图中。最近，使用图神经网络（GNNs）解决此类 CO 问题取得了显著进展（Cai, Guo, & Huang, 2024；Liu et al., 2022；Wang, Shen et al., 2022；Wilder, Ewing, Dilkina, & Tambe, 2019），因为同质性与 GNNs 的消息传递机制十分契合。典型的 GNNs 通过聚合和组合节点自身及其邻居的信息来为每个节点生成嵌入向量。这些嵌入向量捕捉了节点间的复杂关系，可用于指导下游任务。因此，GNNs 在解决复杂的同质性 CO 问题上展现出巨大潜力。

相反，有许多 CO 问题表现出异质性，即相邻节点更有可能具有不同的标签或不相似的特征。图着色问题（GCP）是异质性 CO 问题的一个典型例子。其主要目标是为图的节点分配颜色，使得没有两个相邻节点共享相同的颜色。这类问题在实践中有着广泛的应用，并且受到了学术界和工业界的广泛关注。然而，大多数现有的基于同质性假设的 GNNs 在处理异质性 CO 问题时表现不佳。在异质性场景中，相邻节点的标签可能差异很大。因此，通过聚合邻居特征获得的嵌入向量将包含与节点自身标签冲突的信息，导致潜在空间中的特征向量偏离其真实的语义方向。此外，在异质性场景中，高频信号（即相邻节点之间的差异）占主导地位。然而，传统 GNNs 的低通滤波特性本质上会抑制高频成分，从而导致关键的异质性信息丢失。研究表明（Li et al., 2022），常见的 GNNs（如 GCN、GIN、GraphSAGE 和 GAT）在 GCP 上甚至无法超越最简单的贪心算法。作者将这种性能下降归因于以下两个方面：（1）这些在同质性场景下工作的 GNNs 专注于将等效节点映射到相同的嵌入向量，而不是在异质性场景下为相邻节点分配不同的嵌入向量。（2）具有 𝐿 层的 GNNs 无法捕获距离超过 𝐿 的节点的信息。传统 GNNs 的局部性限制使得它们不可能成为最优的方法。

为了解决这些问题，已经做出了一些努力，包括使图神经网络尽可能深（Li et al., 2022），选择注入式聚合和组合函数（Li et al., 2022），设计负消息传递策略（Wang, Yan, & Jin, 2024），以及在损失函数中引入正则化项（Wang et al., 2024）。我们认为需要更多的创新，特别是设计适合异质性的神经网络和优化方法。首先，优秀的异质性神经网络应创新消息传递机制，以更好地捕捉相邻节点之间的差异。其次，除了损失函数外，模型还应具备更巧妙的优化策略以增强其判别能力。特别是应采用一些全局方法来克服图神经网络的局部性限制。此外，大多数现有方法直接针对每个测试实例进行优化，导致效率低下且泛化能力不足。一个设计良好的预训练模型可以学习异质性特征，显著减少下游任务所需的时间和资源，并提高在未见实例上的性能。

在本文中，我们提出了一种名为 HOCO（用于组合优化问题的异质性优化网络）的新型自监督预训练和微调框架，以解决相邻节点倾向于具有不同标签的异质性组合优化问题。在预训练阶段，网络架构和优化方法专门设计用于捕捉和利用相邻节点之间的差异。具体来说，在异质性图编码器的设计方面，我们通过将自身节点与其邻居分离来改进传统消息传递机制。这允许相邻节点的表示在多个传播轮次中独立演化而不变得过于相似。此外，我们的模型纳入了双层优化策略。在节点层面，我们采用对比学习，将自身节点的所有邻居作为其负样本。这进一步增加了相邻节点表示之间的区分度，这对于异质性至关重要。在图层面，受结构熵理论的启发，我们构建了2跳邻居图的编码树。通过最小化结构熵，模型被鼓励从全局角度寻找更清晰、更有序的聚类结构。在测试阶段，我们用预训练参数初始化模型，并进行简单的微调，以在不同大小和分布的实例上实现卓越性能。我们的模型HOCO克服了传统图神经网络方法的局限性，提供了一种途径来解决CO问题的异质性。

总结而言，我们的贡献主要有以下三点：

• 我们提出了一种新颖的自监督预训练和微调框架 HOCO，用于解决具有异质性的组合优化（CO）问题。该框架利用预训练模型有效提取异质性特征，从而增强了各种下游优化任务的效率和泛化能力。
• HOCO 采用了为异质性量身定制的网络架构和双层优化策略。我们的异质性图编码器通过将一个节点的嵌入与其邻居的嵌入分离，改进了传统的消息传递机制。节点层面的对比学习增强了相邻节点表示之间的区分度，而图层面的结构熵优化了全局聚类结构，显著提升了模型的性能。
• 在图着色问题（GCP）和最大 k 割问题（Max-k-Cut）上进行的大量实验验证了我们的模型相较于各种基线算法，实现了更优越的性能、更高的计算效率和更强的泛化能力。

2. Related work

异质性组合优化问题

传统算法和神经网络方法都在不断发展，以应对这些具有挑战性的问题。在此，我们仅介绍一些与图着色和最大切割（Max-Cut）相关的研究工作。解决异质性组合优化（CO）问题的传统方法通常包括贪心算法、禁忌搜索和半定规划（SDP）方法。禁忌搜索算法Tabucol（Hertz & Werra, 1987）是一种用于图着色问题（GCP）的算法，它通过维护一个禁忌列表来避免循环，并迭代地重新着色节点。Choi和Ye（2000）使用了基于对偶缩放的SDP求解器（DSDP），并结合了Goemans和Williamson（1995）提出的简化方法，以优化GCP中的颜色分配或Max-Cut中的切割。这些方法在小规模问题上表现良好，但在处理更大或更复杂的图时常常遇到困难（Moalic & Gondran, 2018）。

近年来，利用深度学习方法解决异质性CO问题的算法不断涌现。RUNCSP（Toenshoff, Ritzert, Wolf, & Grohe, 2021）通过约束满足方法来解决各种CO问题。它将每个CO问题表示为一个特定的图，并使用递归神经网络（RNN）迭代更新节点状态。GNN-GCP（Lemos, Prates, Avelar, & Lamb, 2019）首次尝试将图神经网络应用于GCP。它通过最小化模型预测与真实标签之间的二元交叉熵损失，训练一个用于GCP决策版本的二元分类器。由于标签稀缺，研究人员开始探索无监督学习方法。PIGNN（Schuetz, Brubaker和Katzgraber, 2022）将一些CO问题（例如Max-Cut）表述为二次无约束二进制优化（QUBO）形式，利用GNN进行无监督训练，并通过松弛和投影策略获得最优解。GNN-NU（Wang et al., 2024）引入了一个包含负消息传递的图神经网络，并通过引入均匀性最大化项增强了无监督损失函数，从而进一步提高了在GCP上的性能。最近，一个名为Hypop（Heydaribeni, Zhan, Zhang, Eliassi-Rad, & Koushanfar, 2024）的通用框架被构建出来，通过采用超图神经网络以及新的分布式和并行训练架构来解决具有高阶约束的CO问题。在许多CO问题（包括超图最大切割）上，该框架显示出了显著的进步。

此外，一些研究采用了强化学习范式。ECO-DQN（Barrett, Clements, Foerster, & Lvovsky, 2020）通过引入探索性搜索策略，成功提高了强化学习在最大切割问题上的性能。对于GCP问题，ReLCol（Watkins, Montana, & Branke, 2023）是一种基于深度强化学习和图神经网络的自动化图着色启发式算法，旨在学习贪心构造启发式方法。

异质图神经网络

大多数传统的图神经网络（GNNs）是基于同质性假设的，在异质性场景下性能会下降。为了解决这个问题，一些更适合处理异质图的 GNNs 应运而生。Zhu 等人提出了 H2GCN 模型（Zhu 等, 2020），该模型采用了三种关键设计以适应同质性和异质性图结构，包括：分离节点自身的嵌入和邻居节点的嵌入，聚合更高阶邻居信息，以及组合中间表示。LRD-GNN（Yang 等, 2023）和 GPR-GNN（Chien, Peng, Li, & Milenkovic, 2020）模型从不同的角度优化了节点特征提取和拓扑信息表示。具体来说，LRD-GNN 基于低秩矩阵分解，而 GPR-GNN 则采用自适应学习方法推广了 PageRank（GPR）权重。这些设计使得模型能够同时适用于同质性和异质性图。Bo 等人分析了 GNNs 中的频率成分，并提出了一个名为 FAGCN（Bo, Wang, Shi, & Shen, 2021）的模型，该模型引入了一种自门控机制。这种机制使模型能够在不需要了解图类型（同质性或异质性）的情况下，自适应地调整低频和高频信号的融合比例。Rossi 等人分析了图的方向性，并得出结论：在异质性场景中，将图视为有向图有助于更有效地提取图中的同质性信息。基于这一发现，他们提出了有向图神经网络（DIR-GNN）（Rossi 等, 2024）。实验结果表明，DIR-GNN 在异质性数据集上实现了显著的性能提升。此外，一些研究（Wang, Jin, Wang, He 和 Huang, 2022；Yang 等, 2021）提出了多种消息传递机制，以克服传统 GNNs 中统一消息传递框架的局限性。在这样的背景下，我们的工作从同质性和异质性角度研究了组合优化（CO）问题，并提出了一个针对异质性 CO 问题的自监督预训练和微调框架。该模型采用专为异质性设计的图编码器，并结合了节点层面和图层面的优化策略，在下游异质性 CO 问题上实现了卓越的性能。

3. Preliminary

3.1.问题定义

在这篇论文中，我们主要研究了两类具有异质性的典型组合优化（CO）问题，即图着色问题（GCP）和最大 k 割问题（Max-k-Cut）。这两类问题在统计物理、电路布局设计以及统计披露控制等领域有着广泛的应用。并且，它们都已被证明是 NP 难解的问题，也就是说，除非 P 等于 NP（Lewis, 1983），否则不可能在多项式时间内求解。

GCP（图着色问题）。 考虑一个无向图 $G=(V,E)$，其中 $V$ 是节点集合，$E$ 是边集合。给定一个颜色集合 $C$ 和一个着色函数 $f:V\to C$，如果对于每条边 $(u,v)\in E$，都有 $f(u)\ne f(v)$，则称 $f$ 为一个合法着色。GCP 的目标是找到在合法着色下所需的最小颜色数。这个最小值被称为 $G$ 的色数，记作 $\chi (G)$（Kubale, 2004）。

Max-k-Cut（最大 k 割问题）。 给定一个无向图 $G=(V,E)$ 和一个固定的整数 $k$，Max-k-Cut 的目标是将所有节点划分到 $k$ 个不相交的子集中，以最大化跨越子集边的总数（Frieze & Jerrum, 1997）。特别是当 $k=2$ 时，这就是著名的 Max-Cut 问题。

3.2.结构熵理论

结构熵（Li & Pan, 2016）用于衡量图的结构多样性和不确定性，而编码树（Zou et al., 2023）则表示将图划分为层次子集的多粒度划分工具。需要注意的是，编码树的结构熵越低，表示原始图的层次结构越清晰。通过最小化结构熵，我们可以消除图中存在的不确定性和噪声，从而自适应地学习图的主要结构特征，进而实现更优越的节点表示。

编码树

编码树 $\mathcal{T}(G)$ 是一种表示图 $G=(V,E)$ 层次结构的工具。编码树 $\mathcal{T}(G)$ 的根节点 $\lambda$ 包含所有节点 $V$，而编码树 $\mathcal{T}(G)$ 中的每个非根节点 $\alpha$ 对应 $V$ 的一个子集 $T_{\alpha }$。特别地，如果 $\alpha$ 是叶节点，那么 $T_{\alpha }$ 仅包含 $V$ 中的一个节点。并且，$T_{\alpha }$ 是 $\alpha$ 的所有子节点 $\beta$ 的 $T_{\beta }$ 的并集。对于编码树 $\mathcal{T}(G)$ 中的任意节点 $\alpha ，{\alpha }^{-}$ 和 $h(\alpha )$ 分别表示其父节点和高度，其中根节点 $\lambda$ 的高度 $h(\lambda )=0$。当叶节点的高度被限制为 $K$ 时，该树被称为 $K$ 层编码树。

K 维结构熵

在构建了 K 层编码树之后，K 维结构熵 $H^K(G)$ 表示为：

H K ( G ) = min ⁡ ∀ T : height ( T ) ≤ K { H τ ( G ) } H^K(G) = \min_{\forall T: \text{height}(T) \leq K} \{ H^\tau(G) \} HK(G)=min∀T:height(T)≤K​{Hτ(G)}

其中，$H^{\tau }(G)$ 定义为：

$H^{\tau }(G)=-{\sum }_{\alpha \in T,\alpha \ne \lambda }\frac{g_{\alpha }}{\text{vol}(G)}{\log }_2\frac{V_{\alpha }}{V_{{\alpha }^{-}}}$

这里，$\text{vol}(G)$ 是图 $G$ 中所有节点的度数之和，$V_{\alpha }$（分别 $V_{{\alpha }^{-}}$）表示 $T_{\alpha }$（分别 $T_{{\alpha }^{-}}$）中所有节点的度数之和，而 $g_{\alpha }$ 是连接 $T_{\alpha }$ 中节点与 $V\setminus T_{\alpha }$ 中节点的所有边的权重之和。$H^{\tau }(G)$ 是树 $\mathcal{T}(G)$ 的结构熵，而 $H^K(G)$ 则表示与最优 K 层编码树相关的 K 维结构熵。

在这篇论文中，我们基于2跳邻居图构建了编码树。在具有异质性的组合优化（CO）问题中（如图着色问题（GCP）和最大k割问题（Max-k-Cut）），一个节点通常与其1跳邻居表现出异质性，但预计与其2跳邻居表现出更强的同质性。受之前研究（Wang et al., 2024）的启发，我们提供了以下理论分析：考虑一个d-正则图上的着色问题，该图有χ种颜色。设c(v)为节点v的颜色。对于v的每个1跳邻居u，颜色相同的概率为P(c(u)=i|c(v)=i)=0，而颜色不同的概率为P(c(u)=j|c(v)=i)=1/(χ−1)（j≠i）。这表明在1跳邻域内存在异质性。对于v的每个2跳邻居w，颜色相同的概率为P(c(w)=i|c(v)=i)=1/(χ−1)，颜色不同的概率为P(c(w)=j|c(v)=i)=(χ−2)/(χ−1)^2（j≠i）。由于1/(χ−1) > (χ−2)/(χ−1)^2，节点与其2跳邻居更可能具有相同颜色，显示出更强的同质性。由于图的结构熵反映了基于同质性的划分，优化2跳邻域图有助于细化全局图结构。

在这篇论文中，我们基于2跳邻居图构建了编码树。在具有异质性的组合优化（CO）问题中（如图着色问题（GCP）和最大k割问题（Max-k-Cut）），一个节点通常与其1跳邻居表现出异质性，但预计与其2跳邻居表现出更强的同质性。受之前研究（Wang et al., 2024）的启发，我们提供了以下理论分析：考虑一个d-正则图上的着色问题，该图有 $\chi$ 种颜色。设 $c(v)$ 为节点 $v$ 的颜色。对于 $v$ 的每个1跳邻居 $u$，颜色相同的概率为 $P(c(u)=i|c(v)=i)=0$，而颜色不同的概率为 $P(c(u)=j|c(v)=i)=\frac{1}{\chi -1}（j\ne i)$。这表明在1跳邻域内存在异质性。对于 $v$ 的每个2跳邻居 $w$，颜色相同的概率为 $P(c(w)=i|c(v)=i)=\frac{1}{\chi -1}$，颜色不同的概率为 $P(c(w)=j|c(v)=i)=\frac{\chi -2}{(\chi -1{)}^2}（j\ne i）$。由于 $\frac{1}{\chi -1}>\frac{\chi -2}{(\chi -1{)}^2}$，节点与其2跳邻居更可能具有相同颜色，显示出更强的同质性。由于图的结构熵反映了基于同质性的划分，优化2跳邻域图有助于细化全局图结构。

3.3 传统的图神经网络

图神经网络（GNNs）是专门为处理图结构数据而设计的神经网络模型（Scarselli, Gori, Tsoi, Hagenbuchner, & Monfardini, 2008）。传统的 GNNs 使用消息传递机制，通过节点之间的连接逐层聚合和传播节点特征。具体来说，在第 $(k+1)$层，每个节点 $v_i$ 通过结合其自身的特征和从其邻居节点 $N(i)$ 收集到的特征来更新其表示，表示如下：

$h_i^{(k+1)}={\text{COMB}}^{(k)}\left(h_i^{(k)},{\text{AGGR}}^{(k)}\left(\left\{h_j^{(k)}:j\in N_i\right\}\right)\right)$

其中，${\text{COMB}}^{(k)}$ 和 ${\text{AGGR}}^{(k)}$ 分别是第 $k$ 层的组合函数和聚合函数。学习到的节点表示可以用于下游任务，例如分类和聚类。

4. Method

我们的模型采用自监督预训练框架。图1展示了整个流程。预训练阶段，专门设计的异质图编码器在随机图上训练，利用节点和图层面优化策略。微调阶段，测试样本经预训练编码器处理并通过简单线性层微调。最后，进行舍入处理以获得下游任务的可行解。为在预训练中有效提取异质性，我们实施了三大关键设计：异质图编码器，基于对比学习的节点级优化，以及基于结构熵的图级优化。

4.1.预训练

异质图编码器

在异质性场景中，一个节点的特征通常与其邻居节点的特征不同。然而，传统的图神经网络（GNNs）通过求平均（Kipf & Welling, 2016）或加权平均（Veličković et al., 2018）邻居嵌入来更新节点的表示，这导致相邻节点之间的相似性较高（Rossi et al., 2020），尤其是在聚类内部。受异质性模型（如H2GCN（Zhu et al., 2020））的启发，我们采用了一种创新的异质图编码器。一方面，我们将每个节点 $v$ 的表示与其邻居的表示分离，而不是将它们融合在一起。这使得节点自身的表示和邻居的表示可以在多个传播步骤中独立演化，而不变得过于相似。另一方面，在某些异质性组合优化（CO）问题中，1跳邻居通常表现出强异质性，而多跳邻居（尤其是2跳邻居）往往表现出一定的同质性。因此，我们通过两层GNN获取1跳、2跳、3跳和4跳邻居的特征，然后将它们拼接起来以更新节点的表示。

需要注意的是，结合每一层的输出（如拼接或LSTM注意力机制）已被证明可以增强GNNs的表达能力（Xu et al., 2018）。直观上看，这种做法可以提取不同层次的局部信息——早期的传播轮次捕获更局部的信息，而后期的轮次则捕获越来越全局的信息。从谱系角度（Zhu et al., 2020）也可以对这一好处进行理论解释：在异质性场景中，标签分布在高频部分包含的信息比低频部分更多。将不同层的中间输出结合起来，可以在最终表示中提取低频和高频成分，这对异质性场景至关重要。

图2展示了异质图编码器的具体结构。该编码器以包含 $N$ 个节点的图 $G=(V,E)$ 作为输入，特征矩阵 $X$ 初始时用邻接矩阵 $A$ 进行填充。首先，每个节点 $v$ 使用独立于图的线性层来初始化其隐藏状态 $h_v^0$，公式如下：
$h_v^0=\sigma (x_v{W}_0)$
其中，$h_v^0\in {\mathbb{R}}^d$，$x_v\in {\mathbb{R}}^N$ 是特征矩阵 $X$ 中对应节点 $v$的行向量，$W_0\in {\mathbb{R}}^{N\times d}$ 是一个可学习的权重矩阵，而 $\sigma$ 代表非线性激活函数。

接下来，使用两层图神经网络（GNN）分别聚合节点的1跳、2跳、3跳和4跳邻居的信息。这里，${\tilde{N}}_1(v)$ 和 ${\tilde{N}}_2(v)$ 分别表示节点 $v$ 的1跳和2跳邻居集合（不包含自环）。聚合过程如下：

• 聚合1跳邻居的信息：
  $h_{{\tilde{N}}_1(v)}^{1,1}=\text{AGGR}(h_u^0:u\in {\tilde{N}}_1(v))$

• 聚合2跳邻居的信息：
  $h_{{\tilde{N}}_2(v)}^{1,2}=\text{AGGR}(h_u^0:u\in {\tilde{N}}_2(v))$

• 聚合经过1跳邻居传递后的2跳邻居的信息：
  $h_{{\tilde{N}}_1(v)}^{2,1}=\text{AGGR}(h_{{\tilde{N}}_2(u)}^{1,2}:u\in {\tilde{N}}_1(v))$

• 聚合经过2跳邻居传递后的2跳邻居的信息：
  $h_{{\tilde{N}}_2(v)}^{2,2}=\text{AGGR}(h_{{\tilde{N}}_2(u)}^{1,2}:u\in {\tilde{N}}_2(v))$

最后，将每一层的输出与节点自身的嵌入进行拼接，得到节点 $v$ 的最终嵌入 $h_v$：
$h_v=(h_v^0\Vert h_{{\tilde{N}}_1(v)}^{1,1}\Vert h_{{\tilde{N}}_2(v)}^{1,2}\Vert h_{{\tilde{N}}_1(v)}^{2,1}\Vert h_{{\tilde{N}}_2(v)}^{2,2})$
其中，$||$ 表示向量的拼接操作。

节点级优化

在节点级优化中，我们采用对比学习方法，通过优化正负样本之间的对比损失函数，将正样本在特征空间中拉近，负样本推远。在我们的模型中，每个节点以其自身为正样本，并随机选取 $L$ 个一跳邻居作为负样本。若一跳邻居数量不足 $L$，则从非邻接节点中随机补充负样本。我们使用以下 InfoNCE 损失函数作为对比损失：

${\mathcal{L}}_{NL}=-\log \frac{\exp (\text{sim}(h_u,h_u)/\tau )}{\exp (\text{sim}(h_u,h_u)/\tau )+{\sum }_{i=1}^L\exp (\text{sim}(h_u,h_i)/\tau )}$

其中，$h_u$ 和 $h_i$ 分别表示查询节点和第 $i$ 个负样本经过图编码器后的表示。相似度函数 $\text{sim}$ 为节点对的点积。温度超参数 $\tau$ 设为 0.07。通过最小化该损失，模型学会在特征空间中区分相邻节点的嵌入，从而实现异质性场景下的节点级优化。

图级优化

如 Li et al. (2022) 所述，传统 GNNs 的局部性限制了它们在异质性组合优化（CO）问题中的应用。为克服这一局限，图级优化采用全局视角。受结构熵理论（Li & Pan, 2016；Li, Yin et al., 2018）启发，我们构建了2跳邻居图的2层编码树，并以结构熵为损失函数。2跳邻居图 $G^2$ 由图 $G$ 生成，即删除 $G$ 的边并添加 $G$ 中节点与其2跳邻居间的边。结构熵反映层次划分后的无序程度，值越低表明划分越清晰。因此，通过最小化结构熵，可优化异质性图编码器，使其学习到更全局的结构特征。根据 Zou et al. (2023)，节点 $v_i$ 和 $v_j$ 间边的权重由对应嵌入 $h_i$ 和 $h_j$ 的皮尔逊相关系数（PCC）定义：

其中，${\bar{h}}_i$ 和 ${\sigma }_i$ 分别表示 $h_i$ 的均值和标准差。

我们基于 Zou et al. (2023) 中提出的贪心算法构建编码树（见算法 1）。首先，将所有节点插入根节点。接着，贪心地选择并合并根节点的两个子节点，形成新的分区。这一过程不断迭代，直至结构熵不再下降。为满足高度限制，我们通过将子树提升到更高层次来压缩编码树。重复此操作，直到编码树高度小于 ( K ) 且结构熵无法进一步降低。最终，我们得到一棵高度为 $K$ 且结构熵最小的编码树。

预训练流程

在预训练阶段，我们以随机图作为输入。对于每个图，首先进行 $N$ 次节点级优化迭代，以增强相邻节点表示的区分度；然后进行 $M$ 次图级优化迭代，以捕获全局结构特征。这种交替优化方法提升了局部表示的判别能力，优化了全局图结构，从而强化了异质图编码器的信息量。该编码器提取了异质性组合优化问题的共性特征，在嵌入空间中确保相邻节点表示的区分性。结合微调时的任务特定损失函数，这一预训练的嵌入空间能够有效适应多种约束类型和不同的下游任务。预训练过程如算法 2 所示。

4.2 微调

由于我们在预训练阶段已经获得了一个专为异质性设计的强大图编码器，因此微调网络非常简单。具体来说，对于一个测试实例，我们首先使用预训练的异质图编码器生成初始嵌入 $H_{\text{emb}}$。然后，通过两个线性层后接一个 softmax 操作来生成分配矩阵 $C$。

$H^1=\text{RELU}(H_{\text{emb}}{W}_1+b_1)$

$H^2=H^1{W}_2+b_2$

$C=\text{softmax}(H^2)$

其中，$W_1,W_2,b_1,b_2$ 是可学习的参数。矩阵 $C\in {\mathbb{R}}^{N\times k}$ 的元素 $c_{ij}$ 表示将节点 $v_i$ 分配到第 $j$ 类的概率。

受 Potts 模型（Schuetz, Brubaker, Zhu and Katzgraber, 2022）的启发，我们采用一种无监督的基于效用的目标函数，定义如下：

${\mathcal{L}}_1={\sum }_{(u,v)\in E}{c}_v^T\cdot c_u$ （15）

公式（15）使用内积来衡量两个相邻节点之间的相似性。通过最小化该值，我们可以降低相邻节点对的相似性，从而有效地捕捉异质性。这种方法不依赖任何先验知识，适用于各种异质性组合优化问题。

此外，按照 Wang 等（2024）的方法，我们使用信息熵作为基于均匀性的目标函数，如下所示：

${\mathcal{L}}_2=-{\sum }_{i=1}^N{c}_i^T\cdot \log c_i(16)$

核心思想是：若节点被分配到某一类的概率接近 1，则该节点的类别转移将非常困难，可能导致陷入局部最优。通过最大化信息熵，我们可以增加节点类别分配的不确定性和均匀性，从而提高解的质量和泛化能力。

结合公式（15）和（16），我们得到目标损失函数如下：

${\mathcal{L}}_{\text{Target}}={\mathcal{L}}_1-\lambda {\mathcal{L}}_2(17)$

其中，$\lambda >0$ 是超参数。在测试阶段，冻结预训练的异质图编码器，仅通过对线性层进行微调来最小化目标损失函数。这种统一的预训练模型显著减少了从头处理不同异质组合优化问题和数据集所需的时间和资源。

微调之后，我们为每个节点 $v$ 确定类别标签 $p_v$，使得节点 $v$ 被分配到 $p_v$ 的概率最大化，即 $p_v=\arg \max (c_v)$。至此，我们的模型为下游的组合优化问题提供了一个更优的可行解。