Fine-Grained Search Space Classification for Hard Enumeration Variants of Subset Problems

Juho Lauri, Sourav DuttaAAAI 2019 · DOI

Introduction

The Maximum Clique Problem (MCP)—identifying the largest complete subgraph within a network—is a cornerstone of combinatorial optimization with applications ranging from social network analysis to bioinformatics. While finding a single maximum clique is a well-known NP-hard problem, the "enumeration" variant, which requires finding all maximum cliques, presents an even greater computational challenge. As real-world datasets scale to millions of vertices, traditional exact solvers often encounter significant bottlenecks in runtime and memory consumption.

Researchers from Nokia Bell Labs have proposed a novel framework that integrates machine learning with exact solvers to address these limitations. By employing fine-grained search space classification, the framework identifies and prunes vertices unlikely to participate in a maximum clique, significantly reducing the workload for downstream solvers without sacrificing solution accuracy.

Methodology: Fine-Grained Pruning

The core innovation of this approach is Fine-Grained Search Space Classification. Unlike previous methods that might attempt to classify entire graphs, this framework operates at the vertex level.

1. Vertex Classification and Probabilistic Pruning

The process begins by training a binary classifier to predict the probability $P(v \in \omega)$ that a vertex $v$ belongs to at least one maximum clique $\omega$. Once probabilities are assigned, a pruning threshold $q$ is applied. Any vertex with a predicted probability below $q$ (e.g., $q = 0.55$) is removed from the graph. This "slimmed down" graph is then processed by a standard exact solver such as cliquer or igraph.

2. Feature Engineering

The effectiveness of the classifier relies on "cheap" features that can be computed rapidly:

  • Graph-Theoretic Features: These include local metrics like vertex degree, local clustering coefficient (LCC), and eigencentrality.
  • Statistical Cues: The authors introduced features based on Pearson’s chi-squared statistics. These measure the deviation of a vertex's local neighborhood density from the expected density in a random graph. Such statistical "surprises" are often strong indicators of hidden clique structures.
Figure 4: Performance metrics on the Planted Clique benchmark, showing (a) vertex classification accuracy, (b) pruning ratio, and (c) final clique accuracy across different graph sizes (n) and clique sizes (k).

Experimental Evaluation

The framework was evaluated using two distinct types of data:

  • Real-World Networks: 239 networks from the Network Repository, including biological, social, and web-crawl data.
  • Synthetic Benchmarks: The "Planted Clique" problem, where a clique of size $k$ is hidden in an Erdős-Rényi random graph $G(n, 1/2)$. This serves as a rigorous test for the algorithm's robustness in the absence of natural community structures.

Key Insights

A significant finding of the study is the scale-invariance of clique motifs. Models trained on small synthetic graphs (e.g., $n=64$) demonstrated remarkable generalization, effectively pruning real-world graphs with millions of vertices. This suggests that the local structural characteristics of maximum cliques are consistent across different scales.

Furthermore, the inclusion of chi-squared statistical features proved vital. While standard graph metrics provide a baseline, detecting statistical anomalies in density allowed the classifier to maintain high accuracy even in dense, noisy environments.

Results and Impact

The framework achieved substantial performance gains across the board:

  • Pruning Efficiency: In real-world networks, the model consistently discarded over 90% of irrelevant vertices.
  • Computational Speedups: By reducing the input size, the cliquer solver experienced speedups of up to 300x. For instance, on the soc-google-plus dataset, runtime was slashed from over 200 seconds to approximately 1 second.
  • Memory Management: The reduction in graph size prevented "Out of Memory" errors that typically plague exact solvers on large-scale instances.
Figure 5: Histograms showing the distribution of classification results for specific (n, k) instances, illustrating the fine-grained nature of the vertex-level predictions.

As shown in Figure 4, the framework maintains high clique accuracy (retaining the true maximum cliques) until the planted clique size $k$ approaches the theoretical limit of detectability. Even in these "hard" regimes, the pruning ratio remains high, demonstrating the efficiency of the vertex-level classification.

Conclusion and Future Work

This research demonstrates that machine learning can serve as a powerful pre-processing layer for NP-hard problems. By shifting the focus from global graph classification to fine-grained vertex classification, the authors have created a scalable, robust heuristic that preserves the exactness of traditional solvers while providing orders-of-magnitude speedups.

Future research directions include extending this "classify-and-prune" paradigm to other subset problems, such as the Maximum Independent Set or the Feedback Vertex Set, and investigating more sophisticated deep learning architectures, such as Graph Neural Networks (GNNs), to further refine vertex classification.

Summary updated

BibTeX
@inproceedings{lauri2019fine,
  author = {Juho Lauri and Sourav Dutta},
  title = {{Fine-Grained Search Space Classification for Hard Enumeration Variants of Subset Problems}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.1609/aaai.v33i01.33012314},
}
Figure