HEA-D: A Hybrid Evolutionary Algorithm for Diversified Top-k Weight Clique Search Problem

Jun Wu, Chu Min Li, Yupeng Zhou, Minghao Yin, Xin Xu, Dangdang NiuIJCAI 2022 · DOI

Abstract

The Diversified Top-$k$ Weight Clique (DTKWC) problem is a critical challenge in graph theory with applications ranging from social network analysis to bioinformatics. This paper introduces HEA-D, a hybrid evolutionary algorithm that combines a specialized clique-based crossover operator with simulated annealing-based local search. HEA-D demonstrates exceptional performance, finding the best-known solutions for all 550 tested instances and establishing new lower bounds for 334 large-scale real-world graphs. Notably, HEA-D often operates one to three orders of magnitude faster than existing state-of-the-art solvers.

Introduction

In graph theory, a clique is a subset of vertices where every vertex is connected to every other vertex. While the Maximum Weight Clique Problem (MWCP) focuses on finding a single optimal clique, many practical applications—such as motif discovery or community detection—require finding multiple high-quality solutions that are sufficiently distinct.

This requirement defines the Diversified Top-$k$ Weight Clique (DTKWC) problem. The objective is to identify $k$ maximal cliques that collectively maximize the total weight of the vertices they cover. Because this problem is NP-hard, exact solvers like CPLEX often struggle as graph size increases. HEA-D addresses these limitations through a robust heuristic framework designed for both solution quality and computational efficiency.

Methodology: The HEA-D Framework

HEA-D is built upon two primary algorithmic pillars designed to balance global exploration with local refinement:

1. Clique-based Crossover and "Private Weight"

Traditional evolutionary algorithms often use generic crossover operators that may disrupt the structural integrity of a solution. HEA-D employs a "clique-aware" crossover. When generating offspring from two parent solutions, the algorithm evaluates cliques based on their private weight—the weight of vertices covered uniquely by a specific clique and no others in the set.

Figure 1: Illustration of clique overlap and the concept of private weight. In (b) and (c), the algorithm must evaluate how much unique weight a new clique $c_3$ adds relative to existing cliques $c_1$ and $c_2$.

This focus on unique coverage ensures that the population evolves toward sets of cliques that are both high-weight and diverse, preventing the algorithm from converging on redundant solutions.

2. Simulated Annealing-based Local Optimization (SALO)

To refine offspring, HEA-D utilizes SALO to explore a restricted neighborhood. Instead of performing vertex-level swaps, SALO attempts to replace entire cliques within the current solution with higher-weight maximal cliques from the graph. The simulated annealing component allows the algorithm to occasionally accept inferior moves, providing a mechanism to escape local optima.

Experimental Evaluation

The algorithm was rigorously tested against 550 instances derived from two major benchmarks:

  • Advertisement Putting Benchmark: Small-scale instances with known optimal solutions.
  • Weighted Real-World Large Graph Benchmark: 102 large-scale graphs where $k$ was varied from 1 to 50.

Key Results and Performance

HEA-D outperformed existing state-of-the-art methods, including TOPKWCLQ and the exact solver CPLEX, across several dimensions:

  • Solution Quality: HEA-D identified the best-known solutions for every single instance. It established 334 new lower bounds for large-scale instances where previous records were surpassed.
  • Computational Efficiency: The algorithm demonstrated significant speed advantages. On many instances, HEA-D was 10 to 1,000 times faster than its closest competitors.
Figure 4: Run time comparison between HEA-D and TOPKWCLQ. Points above the diagonal indicate instances where HEA-D is faster, often by multiple orders of magnitude.
  • Scalability: While CPLEX could only prove optimality for 19 out of 510 real-world instances within the time limit, HEA-D consistently provided superior coverage in a fraction of the time, highlighting its suitability for massive real-world datasets.

Conclusion

HEA-D represents a significant advancement in solving the DTKWC problem. By prioritizing "private weight" during crossover and utilizing high-level clique swaps in local search, the algorithm achieves a superior balance of diversity and weight coverage. Future research may adapt the HEA-D framework to other diversified subgraph problems, such as finding top-$k$ $k$-plexes or $k$-cores in complex networks.

Summary updated

BibTeX
@inproceedings{wu2022hea,
  author = {Jun Wu and Chu Min Li and Yupeng Zhou and Minghao Yin and Xin Xu and Dangdang Niu},
  title = {{HEA-D: A Hybrid Evolutionary Algorithm for Diversified Top-k Weight Clique Search Problem}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2022},
  doi = {10.24963/ijcai.2022/668},
}
Figure