Utilising Reinforcement Learning for the Diversified Top-𝑘� Clique Search Problem

Abstract

The diversified top-𝑘 clique search problem (DTKC) problem is a diversity graph problem in which the goal is to find a clique set of 𝑘 cliques that cover the most nodes in a graph. DTKC is a combinatorial optimisation problem and can be seen as a combination of the maximum clique problem and maximal clique enumeration. In recent years, a new research field arose that research if reinforcement learning can be used for combinatorial optimisation problems. However, no reinforcement learning algorithm exists for DTKC or any other diversity graph problem. Therefore, we propose Deep Clique Comparison Agent (DCCA), which utilises PPO, Graph Isomorphic Networks and the encode-process-decode paradigm to compose an optimal clique set. We tested DCCA for DTKC and the diversified top-𝑘 weighted clique search problem (DTKWC). Our results showed that DCCA could outperform previous methods for DTKC, but only on higher values of 𝑘, such as if 𝑘 = 50. However, we only saw this occur on simpler graphs and DCCA performed significantly worse on the other problem, DTKWC. Due to the novelty of DCCA, we believe that future research can significantly improve our results.