Learning Heuristics for the Maximum Clique Enumeration Problem Using Low Dimensional Representations
This work addresses an NP-hard combinatorial optimization problem for graph analysis, but it is incremental as it builds on existing embedding methods and classification approaches.
The paper tackles the maximum clique enumeration problem by developing a learned heuristic that uses vertex classification with graph embeddings and local features to prune graphs and reduce runtime, showing that Node2Vec and DeepWalk are promising and that combining local features with feature elimination improves accuracy.
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.