Diversifying Graph Augmentation for Learning to Solve Graph Optimization Problems

doi:10.1109/TKDE.2025.3611663

Diversifying Graph Augmentation for Learning to Solve Graph Optimization Problems

2025-09-18

0

PRE

AI

DOI：10.1109/TKDE.2025.3611663

原文链接

原文求助

摘要

En 中文

近年来，许多基于机器学习的方法被提出以有效解决图优化问题。图优化问题是指旨在优化（最大化或最小化）与图相关的某个量的一个问题，例如最小顶点覆盖（MVC）和最大独立集（MIS）问题。这些方法通常是在使用图生成器随机生成的图或从现有数据集中采样的图上进行训练的。然而，我们观察到，如果测试图不是以类似方式生成的，则这样的训练图会导致较差的测试性能，即，在那些随机生成的训练图上训练的模型的可泛化性非常有限。为了解决这一关键问题，本文提出了一种新的框架，名为Learning with Iterative Graph Diversification（LIGD），并提出了一个新的研究问题，名为Diverse Graph Modification Problem（DGMP），该问题通过迭代生成多样化的训练图并训练解决图优化问题的模型来显著提高其性能。我们提出了三种解决DGMP的方法，考虑了机器学习方法的表现和训练图的结构属性。此外，我们研究了DGMP的一个实际案例，名为Diverse Graph Modification Problem with XOR Diversity（DGMP-XDiv），该问题考虑了一种基于XOR的多样性函数。我们提出了一种名为Structure Diversifying Modification on Edge Score（DMES）的多项式时间算法来获得最优解。我们还提出了DMES with Efficiency-Boosting Strategies（DMES-EB）以显著提高DMES的效率。在知名问题上的实验结果表明，我们提出的方法显著提升了监督学习和强化学习方法的性能。它们产生了近最优的结果，并显著优于图增强和基于扩散的方法等基线方法。

Keyword:

Graph augmentation

graph optimization

machine learning

Diversifying Graph Augmentation for Learning to Solve Graph Optimization Problems

摘要

期刊

机构

引用论文