# Learning Heuristics for the Maximum Clique Enumeration Problem Using Low Dimensional Representations

arXiv: https://arxiv.org/abs/2210.16963 · HTML: https://mlsanity.com/paper/2210.16963/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 6 of its 26 references that are in the map.
- First posted on arXiv 30 Oct 2022.

## Builds on (most cited first, 6 of 6)

- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [node2vec: Scalable Feature Learning for Networks](https://mlsanity.com/paper/1607.00653/) (2016)
- [DeepWalk: Online Learning of Social Representations](https://mlsanity.com/paper/1403.6652/) (2014)
- [Fine-grained Search Space Classification for Hard Enumeration Variants of Subset Problems](https://mlsanity.com/paper/1902.08455/) (2019)
- [Learning Multi-Stage Sparsification for Maximum Clique Enumeration](https://mlsanity.com/paper/1910.00517/) (2019)
- [Efficiently Counting Vertex Orbits of All 5-vertex Subgraphs, by EVOKE](https://mlsanity.com/paper/1911.10616/) (2019)

## Abstract (arXiv)

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.