Overview
The maximum clique problem recast as continuous optimization over the simplex, and solved with projected gradient descent and three variants of Frank-Wolfe. Built for the Optimization for Data Science course in Padova.
- execution time on the DIMACS graphs
- −30%
- found the largest cliques on average
- PGD + L0
- moved the least when the step size changed
- FW, AFW
The problem
Finding the largest fully connected subgraph is NP-hard. The Motzkin-Straus formulation turns the search into a quadratic program over the simplex, and a regularization term makes its local maxima match real cliques.
The approach
- 01Maximized xᵀAx + Φ(x) over the simplex, with two regularizers for Φ: an L2 penalty and a smooth approximation of L0.
- 02Implemented projected gradient descent, Frank-Wolfe, pairwise Frank-Wolfe and away-step Frank-Wolfe, each with exact line search, Armijo and fixed step sizes.
- 03Ran every combination on benchmark graphs from the DIMACS challenge.
The result
Projected gradient descent with the L0 regularizer and a fixed step found the largest cliques on average. Fixed steps were also the fastest, and execution time on DIMACS dropped by 30%. Frank-Wolfe and away-step Frank-Wolfe were the steadiest: the choice of step size moved their results the least.
Stack
- Python
- NumPy
- SciPy
- Frank-Wolfe
- Projected Gradient Descent
- DIMACS
Next project
Pokémon detection, three ways