Clique-TF-IDF: A New Partitioning Framework Based on Dense Substructures

Natural Language Processing (NLP) techniques are powerful tools for analyzing, understanding, and processing human language with a wide range of applications. In this paper we exploit NLP techniques, combined with Machine Learning clustering algorithms, to find good solutions to a traditional combinatorial problem, namely, the computation of a partition with high modularity of a graph. We introduce a novel framework, dubbed Clique-TF-IDF, for computing a graph partition. Such a framework leverages dense subgraphs of the input graph, modeled as maximal cliques, and characterizes each node in terms of the cliques it belongs to, similarly to a term-document matrix. Our experimental results show that the quality of the partitions produced by algorithm Clique-TF-IDF is comparable with that of the most effective algorithms in the literature. While our focus is on maximal cliques and partitioning algorithms, we believe that this strategy can be generalized to devise AI solutions for a variety of intractable combinatorial problems where some substructures can be efficiently enumerated and exploited.