Learning heuristics for the maximum clique enumeration problem using higher-order graph structures Yüksek-derece çizge yapilari ile maksimum klik sayma problemine yönelik buluşsal yöntemleri öǧrenme


TAŞDEMİR A. B., ÖZKAHYA L.

29th IEEE Conference on Signal Processing and Communications Applications, SIU 2021, Virtual, Istanbul, Turkey, 9 - 11 June 2021 identifier identifier

  • Publication Type: Conference Paper / Full Text
  • Doi Number: 10.1109/siu53274.2021.9477866
  • City: Virtual, Istanbul
  • Country: Turkey
  • Keywords: Maximum clique enumeration problem, node classification, machine learning model, graphlet
  • Hacettepe University Affiliated: Yes

Abstract

© 2021 IEEE.Recently, various NP-hard combinatorial optimization problems have been solved by learned heuristics using complex learning models. In particular, node classification in graphs has been a helpful method towards finding the decision boundary to distinguish nodes in an optimal set from the rest. In this work, we investigate the role of local graphlet counts surrounding a node as graph features in the node classification towards solving the maximum clique enumeration problem. Graphlets are small induced subgraphs, whose local and global frequencies have been important features in the analysis of networks. We use a learning framework to identify the nodes that belong to some maximum clique of the network. Consequently, this idea is used in a pruning process to reduce the runtime of the maximum clique enumeration problem. Besides the high accuracy of the results, the performance of this framework is shown to be scalable and robust. The method presented here is applicable to networks from all sizes and can be used in estimating the solution of other graph search problems with high complexity.