论文标题
使用低维表示，学习最大集团枚举问题的启发式方法
Learning Heuristics for the Maximum Clique Enumeration Problem Using Low Dimensional Representations
论文作者
论文摘要
使用复杂的学习模型学习了启发式方法，已经发现了各种NP-HARD组合优化问题的近似解决方案。特别是，图中的顶点（节点）分类是找到决策边界的有用方法，以区分最佳集合中的顶点与其余部分。通过遵循这种方法，我们将学习框架用于输入图的修剪过程，以减少最大集团枚举问题的运行时。我们广泛研究了使用嵌入算法（例如Node2VEC和DeepSwalk）的图形嵌入算法以及使用包括局部子学计数的较高级图特征的表示形式的图形嵌入算法的作用。我们的结果表明，Node2VEC和DeepWalk是在表示分类目的的节点时有希望的嵌入方法。我们观察到，在分类过程中使用本地图特征与功能消除过程结合使用会产生更准确的结果。最后，我们在随机图上提供测试，以显示我们方法的鲁棒性和可扩展性。
Approximate solutions to various NP-hard combinatorial optimization problems have been found by learned heuristics using complex learning models. In particular, vertex (node) classification in graphs has been a helpful method towards finding the decision boundary to distinguish vertices in an optimal set from the rest. By following this approach, we use a learning framework for a pruning process of the input graph towards reducing the runtime of the maximum clique enumeration problem. We extensively study the role of using different vertex representations on the performance of this heuristic method, using graph embedding algorithms, such as Node2vec and DeepWalk, and representations using higher-order graph features comprising local subgraph counts. Our results show that Node2Vec and DeepWalk are promising embedding methods in representing nodes towards classification purposes. We observe that using local graph features in the classification process produce more accurate results when combined with a feature elimination process. Finally, we provide tests on random graphs to show the robustness and scalability of our method.
