Graph Sparsifications using Neural Network Assisted Monte Carlo Tree Search.
CoRR(2023)
摘要
Graph neural networks have been successful for machine learning, as well as
for combinatorial and graph problems such as the Subgraph Isomorphism Problem
and the Traveling Salesman Problem. We describe an approach for computing graph
sparsifiers by combining a graph neural network and Monte Carlo Tree Search. We
first train a graph neural network that takes as input a partial solution and
proposes a new node to be added as output. This neural network is then used in
a Monte Carlo search to compute a sparsifier. The proposed method consistently
outperforms several standard approximation algorithms on different types of
graphs and often finds the optimal solution.
更多查看译文
AI 理解论文
溯源树
样例
生成溯源树,研究论文发展脉络
Chat Paper
正在生成论文摘要