.png){kind=icon}
Return
Diversifying Graph Augmentation for Learning to Solve Graph Optimization Problems
.png){kind=icon}
PRE
AI
DOI：10.1109/TKDE.2025.3611663.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Recently, many machine learning-based approaches that effectively solve graph optimization problems have been proposed. The graph optimization problem is the problem that aims to optimize (maximize or minimize) a quantity that is associated with a graph, such as the Minimum Vertex Cover (MVC) and Maximum Independent Set (MIS) problems. These approaches are usually trained on graphs randomly generated with graph generators or sampled from existing datasets. However, we observe that such training graphs lead to poor testing performance if the testing graphs are not generated analogously, i.e., the generalizability of the models trained on those randomly generated training graphs is very limited. To address this critical issue, in this paper, we propose a new framework, named Learning with Iterative Graph Diversification (LIGD), and formulate a new research problem, named Diverse Graph Modification Problem (DGMP), that iteratively generate diversified training graphs and train the models that solve graph optimization problems to improve their performance significantly. We propose three approaches to solve DGMP by considering both the performance of the machine learning approaches and the structural properties of the training graphs. In addition, we study a practical case of DGMP, named Diverse Graph Modification Problem with XOR Diversity (DGMP-XDiv), which considers an XOR-based diversity function. We propose a polynomial-time algorithm named Structure Diversifying Modification on Edge Score (DMES) to obtain the optimal solution. We also propose DMES with Efficiency-Boosting Strategies (DMES-EB) to enhance the efficiency of DMES significantly. Experimental results on well-known problems show that our proposed approaches significantly boost the performance of both supervised and reinforcement learning approaches. They produce near-optimal results and significantly outperform the baseline approaches, such as graph augmentation and diffusion-based approaches.
Keywords:
Graph augmentation
graph optimization
machine learning
Journal
IF:
10.4
Papers:
6.8K
Citations:
3.2W
Organization
View more organizations
Cited Papers
No cited papers available