Restart and Random Walk in Local Search for Maximum Vertex Weight Cliques with Evaluations in Clustering Aggregation

Yi Fan, Nan Li, Chengqian Li, Zongjie Ma, Longin Jan Latecki, Kaile SuIJCAI 2017 · DOI

TL;DR

This paper introduces RRWL, a novel local search algorithm for the NP-hard Maximum Vertex Weight Clique (MVWC) problem. By incorporating a smart restart strategy and a random walk mechanism, RRWL significantly improves upon existing methods, achieving state-of-the-art results on various benchmarks and demonstrating its effectiveness in a practical clustering aggregation application.

What Problem Does This Paper Address?

The Maximum Vertex Weight Clique (MVWC) problem, a fundamental problem in graph theory with applications in areas like clustering and bioinformatics, is known to be NP-hard. While exact algorithms exist, they can be computationally expensive. Incomplete algorithms, particularly those based on local search, offer a more practical approach but often struggle with two key issues: cycling (getting stuck in repetitive search patterns) and the inability to explore the search space exhaustively. Existing local search methods for MVWC, like MN/TS and LSCC, rely on fixed parameters for restarting or deterministic moves, which can be suboptimal. This paper aims to address these limitations by developing a more robust and efficient local search solver for MVWC.

Methods

The core innovation of RRWL lies in its two primary strategies:

  • Revisiting-based Restart Strategy: Instead of relying on fixed restart intervals, RRWL restarts the search when it detects a situation that strongly suggests the search is trapped in a cycle. This is determined by checking if a previously visited solution is encountered again, specifically during the "growing" phase of the search (when the clique is being expanded). This heuristic aims to restart at a more opportune moment, leading to better exploration.
  • Random Walk for Dropping Vertices: When the local search has no other option but to drop vertices to maintain the clique property, RRWL employs a random walk strategy. This contrasts with deterministic greedy approaches that might repeatedly make the same suboptimal choices. By randomly selecting a vertex to drop, RRWL introduces variability, helping to escape local optima and explore different parts of the search space.

Additionally, the paper utilizes a fast approximate hash table to efficiently detect revisiting solutions, which is crucial for the restart strategy. The Strong Configuration Checking (SCC) strategy, a more restrictive version of configuration checking, is also incorporated to reduce cycling.

Datasets

The paper evaluates RRWL on several benchmark datasets:

  • DIMACS: A standard benchmark for clique problems.
  • BHOSLIB: Another benchmark for clique problems.
  • Large Crafted Graphs: These are large, sparse graphs from networkrepository.com.
  • Winner Determination Problem (WDP) Graphs: Graphs derived from the winner determination problem, which can be naturally formulated as MVWC.
  • Real Data Sets for Clustering Aggregation: Datasets from the UCI machine learning repository (Iris, Zoo, Semeion, Pen Digits, Vowel, ISOLET, Letter) were used after being transformed into graphs representing cluster relationships.

Key Insights and Ideas

  • Smart Restarts are Crucial: Fixed restart intervals are less effective than dynamic, heuristic-driven restarts that trigger when the search shows signs of being trapped.
  • Randomness in Dropping is Beneficial: Deterministic vertex dropping can lead to repetitive cycles. Introducing randomness here helps explore alternative clique structures.
  • The "Growing" Phase is Key for Restart Detection: Revisiting a solution is more indicative of a cycle when the search is in an extending phase, as tabu constraints are more actively enforced during additions/swaps.
  • MVWC Formulation for Clustering: The paper demonstrates that MVWC is a powerful framework for tackling the complex problem of clustering aggregation, leading to improved results.
  • Robustness Across Graph Types: RRWL shows strong performance across a wide range of graph densities and sizes, from dense DIMACS graphs to sparse large crafted graphs.

Key Results

  • State-of-the-Art Performance: RRWL outperforms existing state-of-the-art solvers (LSCC, FastWClq, WLMC) on DIMACS, BHOSLIB, and large crafted graphs in terms of solution quality.
  • New Best-Known Solution: RRWL found a new best-known solution on the MANN_a81.clq instance.
  • Competitive on WDP: RRWL and RSL found optimal solutions on WDP graphs, often in shorter times than WLMC.
  • Effective in Clustering Aggregation: When applied to clustering aggregation, RRWL-based methods significantly improved the quality of aggregated clusterings, as measured by Normalized Mutual Information (NMI).
  • Scalability: RRWL demonstrates good scalability, particularly on larger and sparser graphs.

Limitations and Future Work

  • Limitations: The paper acknowledges that while the restart strategy is more intelligent than fixed intervals, it might still be too cautious in some scenarios, potentially spending too much time in non-promising areas. The effectiveness of random walk on very sparse graphs was less pronounced, as the restart strategy was more dominant.
  • Future Work: The authors suggest exploring variants of the restart strategy and applying these techniques to solve other related problems. Further investigation into the interplay between restart and random walk strategies across different graph structures is also a promising avenue.

Summary updated

BibTeX
@inproceedings{fan2017restart,
  author = {Yi Fan and Nan Li and Chengqian Li and Zongjie Ma and Longin Jan Latecki and Kaile Su},
  title = {{Restart and Random Walk in Local Search for Maximum Vertex Weight Cliques with Evaluations in Clustering Aggregation}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2017},
  doi = {10.24963/ijcai.2017/87},
}
Figure