标题： 图卷积网络在求解顶点$p$-中心问题中的实验 显示英文标题

标题： Experiments with graph convolutional networks for solving the vertex $p$-center problem

摘要： 在过去的几年中，图卷积网络（GCN）已成为机器学习领域中一个流行的研究方向，用于解决定义在图上的NP难组合优化问题（COPs）。 尽管获得的结果通常仍然不如运筹学社区中的特定问题求解方法具有竞争力，但与以往的机器学习方法相比，GCNs在经典的COPs（如旅行商问题（TSP））上通常能带来改进。 在本工作中，我们提出了一个关于使用GCNs解决顶点p-中心问题（PCP）的初步研究，PCP是另一种经典的图上COP。 特别是，我们研究了一个基于端到端训练的TSP成功模型是否可以适应PCP，PCP的输入与通常使用的TSP版本类似，都是二维欧几里得图。 然而，PCP的目标函数具有最小最大化结构，这可能导致许多对称最优，即真实解，以及其它潜在的学习困难。 我们获得的初步结果表明，直接转移网络架构的想法似乎并不太有效。 因此我们认为，PCP可能是一个有趣的新思路和GCN领域新发展的基准问题。 显示英文摘要

摘要： In the last few years, graph convolutional networks (GCN) have become a popular research direction in the machine learning community to tackle NP-hard combinatorial optimization problems (COPs) defined on graphs. While the obtained results are usually still not competitive with problem-specific solution approaches from the operations research community, GCNs often lead to improvements compared to previous machine learning approaches for classical COPs such as the traveling salesperson problem (TSP). In this work we present a preliminary study on using GCNs for solving the vertex p-center problem (PCP), which is another classic COP on graphs. In particular, we investigate whether a successful model based on end-to-end training for the TSP can be adapted to a PCP, which is defined on a similar 2D Euclidean graph input as the usually used version of the TSP. However, the objective of the PCP has a min-max structure which could lead to many symmetric optimal, i.e., ground-truth solutions and other potential difficulties for learning. Our obtained preliminary results show that indeed a direct transfer of network architecture ideas does not seem to work too well. Thus we think that the PCP could be an interesting benchmark problem for new ideas and developments in the area of GCNs.