Unsupervised Ordering for Maximum Clique
This work addresses a combinatorial optimization problem for graph theory and AI applications, presenting an incremental improvement in search methods.
The paper tackles the maximum clique problem by learning vertex orderings through an unsupervised permutation-based framework, which improves search efficiency and reduces computational steps when integrated into branch-and-bound search.
We propose an unsupervised approach for learning vertex orderings for the maximum clique problem by framing it within a permutation-based framework. We transform the combinatorial constraints into geometric relationships such that the ordering of vertices aligns with the clique structures. By integrating this clique-oriented ordering into branch-and-bound search, we improve search efficiency and reduce the number of computational steps. Our results demonstrate how unsupervised learning of vertex ordering can enhance search efficiency across diverse graph instances. We further study the generalization across different sizes.