An Efficient Hybridization of Graph Representation Learning and Metaheuristics for the Constrained Incremental Graph Drawing Problem

📄 arXiv: 2508.15949v1 📥 PDF

作者: Bruna C. B. Charytitsch, María C. V. Nascimento

分类: cs.LG, math.OC

发布日期: 2025-08-21

备注: The paper has been accepted for publication in the European Journal of Operational Research. Supplementary material will be available on the journal website or upon request

💡 一句话要点

提出GL-GRASP算法，融合图表示学习与元启发式算法，高效解决约束增量图绘制问题。

🎯 匹配领域: 支柱二：RL算法与架构 (RL & Architecture)

关键词: 图表示学习 元启发式算法 约束增量图绘制 GRASP算法 图可视化 节点嵌入 混合算法

📋 核心要点

  1. 现有方法在混合机器学习与元启发式算法时，常因监督或强化学习计算成本高昂而效率低下。
  2. 论文提出GL-GRASP算法，将图表示学习融入GRASP的构造阶段，以低成本提取图的潜在结构。
  3. 实验表明，GL-GRASP在约束增量图绘制问题上优于现有GRASP启发式算法，并具有良好的可扩展性。

📝 摘要（中文）

近年来，机器学习技术与元启发式算法的混合引起了广泛关注。许多研究尝试利用监督学习或强化学习来辅助启发式方法的决策。然而，在某些情况下，这些技术被认为过于耗时，且与手工设计的启发式算法相比不具竞争力。本文提出了一种元启发式算法与计算成本较低的学习策略（即图表示学习，GRL）的混合方法，以提取图的潜在结构。针对约束增量图绘制问题（C-IGDP），一种分层图可视化问题，展开研究。针对该问题的文献有限，而贪婪随机自适应搜索过程（GRASP）启发式算法已显示出良好的效果。因此，本文研究了将GRL融入GRASP构造阶段的收益，称之为图学习GRASP（GL-GRASP）。在计算实验中，我们首先分析了考虑不同节点嵌入技术所取得的结果，其中基于深度学习的策略表现突出。评估考虑了原始积分度量，该度量根据所需时间评估解决方案的质量。根据该度量，最佳的GL-GRASP启发式算法表现出优于现有文献中针对该问题的GRASP启发式算法的性能。在固定时限下对新生成的更密集实例进行的扩展性测试进一步证实了GL-GRASP启发式算法的鲁棒性。

🔬 方法详解

问题定义：论文旨在解决约束增量图绘制问题（C-IGDP），这是一个分层图可视化问题。现有方法，特别是基于监督学习或强化学习的混合方法，在计算成本上存在瓶颈，导致效率不高，难以与手工设计的启发式算法竞争。因此，需要一种更高效的方法来提取图的潜在结构，从而改进图绘制的质量和效率。

核心思路：论文的核心思路是将图表示学习（GRL）融入到贪婪随机自适应搜索过程（GRASP）的构造阶段。GRL能够以较低的计算成本提取图的潜在结构，为GRASP的构造阶段提供更有价值的信息，从而引导搜索过程，提高解的质量。这种混合方法旨在克服传统机器学习方法计算成本高的问题，同时利用GRL的优势来提升启发式算法的性能。

技术框架：GL-GRASP算法的整体框架如下： 1. 图表示学习（GRL）阶段：使用不同的节点嵌入技术（包括基于深度学习的策略）来学习图中节点的表示。 2. GRASP构造阶段：利用GRL学习到的节点表示，指导GRASP的构造过程，选择更有希望的节点加入到解中。 3. GRASP局部搜索阶段：对构造阶段生成的解进行局部搜索，进一步优化解的质量。 4. 迭代：重复构造和局部搜索阶段，直到满足停止条件。

关键创新：论文的关键创新在于将图表示学习（GRL）与元启发式算法GRASP相结合，提出了一种新的混合算法GL-GRASP。这种混合方法利用GRL的低计算成本和有效提取图结构的能力，克服了传统机器学习方法在混合算法中计算成本高的问题，同时提升了GRASP算法的性能。这是将GRL应用于约束增量图绘制问题的一个新尝试。

关键设计：论文的关键设计包括： 1. 节点嵌入技术的选择：实验中分析了不同的节点嵌入技术，包括基于深度学习的策略，以选择最适合C-IGDP问题的节点表示方法。 2. GRL与GRASP的集成方式：具体如何利用GRL学习到的节点表示来指导GRASP的构造过程，例如，可以使用节点嵌入向量来计算节点之间的相似度，从而选择与当前解更相关的节点。 3. 原始积分度量（Primal Integral）：使用原始积分度量来评估算法的性能，该度量综合考虑了解的质量和求解时间。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

实验结果表明，GL-GRASP算法在约束增量图绘制问题上优于现有的GRASP启发式算法。特别是，基于深度学习的节点嵌入技术表现突出。根据原始积分度量，最佳的GL-GRASP启发式算法在解的质量和求解时间上都优于现有方法。此外，扩展性测试表明，GL-GRASP算法在处理更密集的图实例时也具有良好的鲁棒性。

🎯 应用场景

该研究成果可应用于各种需要进行分层图可视化的领域，例如软件工程中的依赖关系可视化、生物信息学中的基因网络可视化、社交网络分析等。通过提高图绘制的效率和质量，可以帮助用户更好地理解复杂系统，从而做出更明智的决策，具有重要的实际应用价值和潜力。

📄 摘要（原文）

Hybridizing machine learning techniques with metaheuristics has attracted significant attention in recent years. Many attempts employ supervised or reinforcement learning to support the decision-making of heuristic methods. However, in some cases, these techniques are deemed too time-consuming and not competitive with hand-crafted heuristics. This paper proposes a hybridization between metaheuristics and a less expensive learning strategy to extract the latent structure of graphs, known as Graph Representation Learning (GRL). For such, we approach the Constrained Incremental Graph Drawing Problem (C-IGDP), a hierarchical graph visualization problem. There is limited literature on methods for this problem, for which Greedy Randomized Search Procedures (GRASP) heuristics have shown promising results. In line with this, this paper investigates the gains of incorporating GRL into the construction phase of GRASP, which we refer to as Graph Learning GRASP (GL-GRASP). In computational experiments, we first analyze the results achieved considering different node embedding techniques, where deep learning-based strategies stood out. The evaluation considered the primal integral measure that assesses the quality of the solutions according to the required time for such. According to this measure, the best GL-GRASP heuristics demonstrated superior performance than state-of-the-art literature GRASP heuristics for the problem. A scalability test on newly generated denser instances under a fixed time limit further confirmed the robustness of the GL-GRASP heuristics.