Geometric Deep Learning Graph Pruning to Speed-Up the Run-Time of Maximum Clique Enumerarion Algorithms

Abstract

In this paper we propose a method to reduce the running time to solve the Maximum Clique Enumeration (MCE) problem. Specifically, given a network we employ geometric deep learning in order to find a simpler network on which running the algorithm to derive the MCE. Our approach is based on finding a strategy to remove from the network nodes that are not functional to the solution. In doing so, the resulting network will have a reduced size and, as a result, search times of the MCE is reduced. We show that our approach is able to obtain a solver speed-up up to 42 times, while keeping all the maximum cliques.

Publication
Complex Networks and Their Applications XI: Proceedings of The Eleventh International Conference on Complex Networks and Their Applications: COMPLEX NETWORKS 2022—Volume 1

Related