Combinatorial Optimization with Graph Convolutional Networks and Guided Tree Search
图上常见np问题
Abstract
estimate the likelihood, for each vertex in a graph, of whether this vertex is part of the optimal solution.
设计network 综合各种方案
Introduction
GCN学习每个点的likelihood, 但由于解不唯一, 所以允许网络综合各种解决方案，这使网络能够明确消除解决方案空间中的不同模式。 该训练有素的GCN用于指导并行化树搜索过程， used to guide a parallelized tree search procedure .该过程快速生成大量候选解，在随后的优化后选择其中一个。
Method
basic network architecture for f. --within a greedy procedure.
a network f would take the graph G as input,and the output f(G) would be a binary labelling of the nodes.
直接选择 [0,1]^N that indicates how likely each vertex is to belong to the MIS 作为输出无效, 问题在于将概率图f（G）转换为离散分配通常会产生无效解。所以use a network f within a tree search procedure.
推导
treat the prediction f(Gi;θ) as a likelihood map over vertices and use the trained network within a greedy growing procedure that makes sure that the constraints are satisfied.
按p降序排列,最大的标1, neighbor标0, 递归........直到新递归到的已经被标为0了就停止.
去掉这些点,小一些的图fai'重复训练,标记,排列寻找这个过程
synthesize multiple diverse probability maps -- powerful tree search procedure.
修改为M个解的output:
Given the input graph G, the revised network f generates M probability maps
这使网络可以分散其赌注，并生成多种多样的解决方案，每一种解决方案都可以更加精确。
This is akin to breadth-first search, rather than depth-first search(类似于bfs而不是dfs.每一次选M个备用解added to queue, get higher diversity)
树上并行计算:to run multiple threads that choose different incomplete solutions from the queue and expand them.
supplementary material
Word & Phrase
canonical 典型的
performs on par with.....表现一样好
减 reduce, cut, decrease, subtract, lower, diminish
a diverse set of 各种各样的
intractable unmanageable uncontrollable difficult awkward troublesome
表明 show, indicate, demonstrate, clear, reveal, evidence
generates a probability map over the input graph
violate the independence constraints 违反独立性约束
highlights a limitation of 强调了...的局限性
provides the best balance of performance and efficiency.
