# Learning Multi-Stage Sparsification for Maximum Clique Enumeration

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Sep 2019.

## Built on by (most cited first, 6 of 6)

- [Learning to Sparsify Travelling Salesman Problem Instances](https://mlsanity.com/paper/2104.09345/) (2021)
- [wsGAT: Weighted and Signed Graph Attention Networks for Link Prediction](https://mlsanity.com/paper/2109.11519/) (2021)
- [LeNSE: Learning To Navigate Subgraph Embeddings for Large-Scale Combinatorial Optimisation](https://mlsanity.com/paper/2205.10106/) (2022)
- [COMBHelper: A Neural Approach to Reduce Search Space for Graph Combinatorial Problems](https://mlsanity.com/paper/2312.09086/) (2023)
- [Learning Heuristics for the Maximum Clique Enumeration Problem Using Low Dimensional Representations](https://mlsanity.com/paper/2210.16963/) (2022)
- [Imitation Learning for Combinatorial Optimisation under Uncertainty](https://mlsanity.com/paper/2601.05383/) (2026)

## Abstract (arXiv)

We propose a multi-stage learning approach for pruning the search space of maximum clique enumeration, a fundamental computationally difficult problem arising in various network analysis tasks. In each stage, our approach learns the characteristics of vertices in terms of various neighborhood features and leverage them to prune the set of vertices that are likely not contained in any maximum clique. Furthermore, we demonstrate that our approach is domain independent -- the same small set of features works well on graph instances from different domain. Compared to the state-of-the-art heuristics and preprocessing strategies, the advantages of our approach are that (i) it does not require any estimate on the maximum clique size at runtime and (ii) we demonstrate it to be effective also for dense graphs. In particular, for dense graphs, we typically prune around 30 % of the vertices resulting in speedups of up to 53 times for state-of-the-art solvers while generally preserving the size of the maximum clique (though some maximum cliques may be lost). For large real-world sparse graphs, we routinely prune over 99 % of the vertices resulting in several tenfold speedups at best, typically with no impact on solution quality.