Abstract
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.
Introduction
The Maximum Clique Problem (MCP) is a fundamental challenge in combinatorial optimization, seeking the largest subset of vertices in a graph where every pair is connected. As an NP-hard problem, MCP has critical applications in fields such as bioinformatics, social network analysis, and computer vision. While exact solvers typically employ a Branch-and-Bound (BnB) framework, their performance is highly sensitive to vertex ordering heuristics. Traditional heuristics, such as sorting by vertex degree, often fail to capture the complex global structural relationships necessary for optimal pruning.
Recent efforts to apply Machine Learning (ML) to MCP have largely focused on binary classification—predicting whether a specific node belongs to the maximum clique. However, this "local" approach ignores the collective structural properties of cliques. This paper introduces a novel unsupervised learning framework that treats vertex ordering as a global permutation problem, effectively "revealing" the graph's hidden clique structures to the solver.
Methodology
Permutation-Based Framework
The core of our approach is a shift from node-level classification to graph-level permutation. We aim to find a vertex ordering that clusters potential clique members at the beginning of the sequence. This is achieved through an unsupervised pipeline that processes graph features through a Graph Neural Network (GNN) to produce a differentiable permutation matrix.
The pipeline consists of four main stages:
- Input Features: Node-level features are extracted from the graph.
- Graph Neural Network: A GNN processes these features to capture structural dependencies.
- Permutation Formulation: A Gumbel-Sinkhorn operator is used to generate a "soft" (differentiable) permutation matrix during training.
- Output & Search: For inference, the Hungarian algorithm extracts a discrete ordering, which is then used to initialize the search process in an exact solver.
The Geometric Trick: Chebyshev Distance
To guide the unsupervised learning process, we transform combinatorial constraints into geometric relationships. We define a target cost matrix based on the Chebyshev distance, analogous to the movement of a King on a chessboard.
The cost matrix $C$ assigns high weights to the top-left corner of the adjacency matrix. By minimizing the "clash" between the graph's non-edges and these high-weight regions, the model is incentivized to push adjacent pairs (potential clique members) into the top-left. This "gravitational pull" effectively front-loads the search sequence with vertices most likely to form large cliques.
Experimental Results
We evaluated our framework on Erdős-Rényi (ER) random graphs, a standard benchmark for average-case complexity. We tested graphs with $n=100$ and $n=200$ vertices across a wide range of edge densities ($p \in [0.1, 0.9]$).
Search Efficiency and Speedup
On dense graphs ($n=100, p=0.9$), our learned ordering reduced the number of search steps by 16.4% compared to random ordering. Crucially, it consistently outperformed traditional degree-based heuristics. Even when accounting for the computational overhead of the GNN inference, the method achieved a net speedup in total execution time for the majority of density scenarios on larger $n=200$ graphs.
Generalization
A key strength of this unsupervised approach is its ability to generalize. Models trained on $n=200$ nodes demonstrated "zero-shot" effectiveness when applied to graphs of slightly different sizes (e.g., $n=190$) via simple zero-padding. This suggests that the model learns fundamental structural patterns rather than just memorizing specific graph sizes.
Conclusion
By framing vertex ordering as an unsupervised permutation task, we have demonstrated a significant improvement in the efficiency of exact MCP solvers. Our geometric cost function successfully aligns vertex sequences with clique structures, enabling more aggressive pruning in Branch-and-Bound search. Future work will explore deeper integration where the GNN dynamically guides the search at every branch and extends the framework to real-world graphs with non-uniform structural properties.
Summary updated