TL;DR
This paper introduces an unsupervised learning framework that solves the Maximum Clique Problem (MCP) by learning an optimal vertex ordering rather than predicting binary node inclusions. By reordering vertices to concentrate clique edges into the top-left corner of the adjacency matrix using an exponential Chebyshev-distance objective, the model produces a clique-oriented ordering that accelerates classical branch-and-bound (BnB) search algorithms, even when accounting for neural network inference overhead.
What Problem Does This Paper Address?
Finding the maximum clique—the largest complete subgraph where every pair of vertices is connected—is NP-hard and notoriously difficult to approximate. State-of-the-art exact solvers rely on branch-and-bound (BnB) frameworks like MaxCliqueDyn, which depend heavily on initial vertex orderings (typically hand-crafted heuristics like sorting by non-increasing vertex degree) and graph-coloring bounds to prune unpromising branches.
Existing machine learning approaches typically frame MCP as an unsupervised binary classification task (predicting whether each node is in the clique). However, binary classification struggles to capture complex combinatorial correlations among nodes and enforces constraints via penalty terms. The authors address this by reframing MCP as an unsupervised permutation learning task to directly expose dense graph substructures before exact search begins.
Methods
The authors formulate vertex reordering as finding a permutation matrix $P$ that clusters non-edges away from the leading submatrix of the graph complement:
- Geometric Chebyshev Cost Matrix: In the complement graph's adjacency matrix $M(A) = J - I - A$, non-adjacent pairs in the original graph are $1$s, and adjacent pairs (clique edges) are $0$s. The authors define a target cost matrix $D_{\text{Clique}} = (1 + \epsilon)^{(C_n - n/2)}$, where $C_n[i,j] = \max(i, j) - 1$ represents the 2D Chebyshev distance (king moves on a chessboard). Minimizing $\langle P^T (J - I - A) P, D_{\text{Clique}} \rangle$ geometrically forces the $0$s to the top-left corner.
- Theoretical Guarantee: The authors prove that when using the base weighting $(n^2)^{C_n}$, any permutation matrix minimizing the discrete loss function is mathematically guaranteed to place the maximum clique in the first $\omega$ positions.
- GNN + Differentiable Sorting: A 2-layer Scattering Attention Graph Neural Network (SAG) takes node degrees and local clustering coefficients as input features and outputs continuous scores. These scores pass through a Gumbel-Sinkhorn operator to form a differentiable soft permutation matrix $T$ during unsupervised training.
- Hard Assignment & Search Integration: At test time, the Hungarian algorithm converts the continuous logits into a hard permutation matrix $P$. This permutation replaces the initial degree-based ordering in
MaxCliqueDyn.
Datasets
The authors evaluated their model on synthetic Erdős–Rényi (ER) random graphs:
- Graph sizes: $n = 100$ and $n = 200$ vertices across edge probabilities $p \in \{0.1, 0.2, \dots, 0.9\}$.
- Splits: 50,000 training, 10,000 validation, and 10,000 test graphs per $(n, p)$ configuration.
- Generalization benchmark: ER graphs with $n = 190$ and $p = 0.9$, evaluated using zero-padding on a model trained on $n = 200, p = 0.81$.
No real-world graph benchmark datasets (such as DIMACS or BHOSLIB) were evaluated in the paper.
Key Insights and Ideas
- Invariance vs. Equivariance: In the Traveling Salesperson Problem (TSP), a reordering framework requires equivariance (relabeled nodes must consistently relabel the tour heatmap: $\Pi H_0 \Pi^T$). In MCP, the objective $T^T(J - I - A)T$ must be invariant to initial node indexing because the solver always seeks to concentrate clique nodes into the top-left corner regardless of input labelling.
- Synergy with Exact Solvers: Classical BnB solvers explore vertices with the highest color labels first. Placing candidate clique nodes near the top of the matrix causes non-clique vertices to be evaluated earlier, quickly establishing strong candidate cliques that serve as tight lower bounds for subsequent search.
- Diminishing Overhead: Neural inference and Hungarian decoding take roughly constant time ($O(1)$ and $O(n^3)$ respectively). As graph density and size increase, the BnB combinatorial search time explodes exponentially—meaning the learning overhead quickly becomes negligible compared to the thousands of pruned search steps.
Key Results
- Step Reduction: On $n = 200$ graphs, the learned clique-oriented ordering consistently achieved the fewest search steps across all edge probabilities. At $p = 0.9$, it reduced the search steps from $1.435 \times 10^7$ (random) and $1.252 \times 10^7$ (degree-sort) down to $1.209 \times 10^7$ steps (a 3.4% reduction over degree-sort and 15.7% over random).
- Wall-Clock Speedups (including overhead): On dense instances ($n = 200, p = 0.9$) running on an Intel Xeon Gold CPU, total execution time dropped from 33.60 seconds (degree-sort) to 32.74 seconds—a net 2.6% speedup even after including the ~0.04s inference overhead.
- Size Generalization: Using zero-padding on unseen sizes ($n = 190, p = 0.9$), the model completed the search in $5.656 \times 10^6$ steps (14.76s) compared to $5.886 \times 10^6$ steps (15.23s) for degree-sort.
Limitations and Future Work
- Evaluated Only on ER Random Graphs: The evaluation is restricted to Erdős–Rényi graphs. Real-world graphs (e.g., social or biological networks with power-law distributions) and standard competitive benchmarks (like DIMACS) were not tested.
- Capped Graph Sizes: Experiments only scale up to $n = 200$. While inference overhead diminishes as density grows, running the $O(n^3)$ Hungarian algorithm on graphs with thousands of nodes could re-introduce significant latency.
- Static Initialization Only: The learned ordering is used purely as a pre-processing step for the root node; the dynamic variable ordering within subsequent tree levels still relies on traditional heuristics (
ColorSort). - Future Directions: The authors suggest exploring supervised variants learned from optimal orderings, deeper integration of learned ordering throughout intermediate branching steps, and applying the permutation framework to modern SAT-based maximum clique algorithms.
Summary updated