A Refined Upper Bound and Inprocessing for the Maximum K-plex Problem

Hua Jiang, Fusheng Xu, Zhifei Zheng, Bowen Wang, Wei ZhouIJCAI 2023 · DOI

TL;DR

This paper introduces a novel, more effective upper bound and an incremental graph reduction technique to significantly speed up algorithms for the Maximum k-plex Problem (MKP). Their new branch-and-bound algorithm, DiseMKP, outperforms existing state-of-the-art methods on benchmark datasets, demonstrating substantial improvements in solving more instances and reducing computation time.

What Problem Does This Paper Address?

The Maximum k-plex Problem (MKP) is a fundamental problem in graph theory with applications in areas like social network analysis and community detection. It involves finding the largest induced subgraph where every vertex has at most $k-1$ non-neighbors. While MKP is NP-hard, exact algorithms, particularly those based on branch-and-bound (BnB), have seen significant advancements. These improvements primarily stem from better upper bounds (to prune the search space) and graph reduction rules (to simplify the problem). However, existing methods for calculating upper bounds and performing reductions still leave room for improvement, especially for complex, real-world graphs. This paper aims to address this by proposing a refined upper bound and a more efficient inprocessing strategy to further enhance the performance of BnB algorithms for MKP.

Methods

The paper introduces two core innovations:

  • Refined Upper Bound (DisePUB): The authors propose a new upper bound called "distribution efficiency" (dise). This metric helps in constructing a better partition of candidate vertices for the k-plex. Unlike previous methods that might distribute vertices suboptimally, DisePUB prioritizes partitions that are more "efficient" in contributing to the k-plex, leading to a tighter upper bound. The algorithm, DisePUB, iteratively selects partitions based on this efficiency metric, aiming to minimize the total cost of constructing the k-plex.
  • Inprocessing Strategy (Reduce): Instead of just performing graph reduction once at the beginning, the authors propose an "inprocessing" strategy. This means that graph reduction rules (based on properties of k-plexes and common neighbors) are applied incrementally throughout the BnB search, especially whenever a better lower bound (an updated solution) is found. This allows the algorithm to adapt and simplify the graph as the search progresses, further pruning the search space.

These components are integrated into a new BnB algorithm called DiseMKP.

Datasets

The authors evaluated their algorithm on a comprehensive set of 675 graphs from three distinct sources:

  • DIMACS graphs: A standard benchmark set of 80 graphs, commonly used for evaluating clique and k-plex algorithms.
  • DIMACS10 graphs: A larger dataset with up to $2 \times 10^7$ vertices, designed for testing scalability.
  • Real-world graphs from Network Repository: A diverse collection of 511 graphs from various domains (biological, social, web, etc.), providing a realistic testbed.

Key Insights and Ideas

  • Distribution Efficiency is Key: The core insight is that not all partitions of candidate vertices are equally good for calculating an upper bound. Prioritizing partitions based on a "distribution efficiency" metric leads to tighter bounds and more effective pruning.
  • Inprocessing is Crucial for Performance: Applying graph reduction rules dynamically during the search (inprocessing), rather than just once at the start, significantly boosts performance. This is because the effectiveness of reduction rules depends on the quality of the current lower bound, which improves as the search progresses.
  • Trade-offs in Partitioning: The paper highlights how different partitioning strategies for the same candidate set can lead to vastly different upper bounds, underscoring the importance of the partitioning method.
  • Robustness Across k Values: DiseMKP shows remarkable robustness, maintaining strong performance even as the parameter $k$ increases, which typically makes the MKP much harder.

Key Results

  • State-of-the-Art Performance: DiseMKP significantly outperforms three leading BnB algorithms (BnBK, Maplex, KpLeX) on a broad range of benchmark instances. For $k=8$, DiseMKP solved 11.9% to 38.6% more instances than its competitors.
  • Faster Search: The new upper bound (DisePUB) and the inprocessing strategy lead to substantially smaller search trees and faster computation times. Experiments comparing variants of DiseMKP showed that DisePUB alone reduced search tree sizes by up to 97.9% compared to previous methods.
  • Inprocessing Impact: Disabling the inprocessing feature in DiseMKP-NOIP led to a significant performance drop, solving fewer instances and taking much longer, demonstrating its critical role.
  • Effective Graph Reduction: The inprocessing strategy effectively reduced graph sizes, with some instances shrinking dramatically (e.g., from thousands of vertices to tens) as the search progressed and the lower bound improved.

Limitations and Future Work

  • Time Complexity of DisePUB: The paper notes that the time complexity of the DisePUB algorithm is $O(|S|^2 \times |C|)$, where $|S|$ is the size of the partial solution and $|C|$ is the size of the candidate set. While effective, this complexity might be a bottleneck in certain scenarios.
  • Future Work: The authors suggest that their proposed strategies can be adapted to other graph problems and that further research into more sophisticated reduction rules and upper bounds could yield even greater improvements. The paper also implicitly points to the ongoing challenge of solving MKP on extremely large-scale graphs, where even these advanced techniques might face scalability limits.

Summary updated

BibTeX
@inproceedings{jiang2023refined,
  author = {Hua Jiang and Fusheng Xu and Zhifei Zheng and Bowen Wang and Wei Zhou},
  title = {{A Refined Upper Bound and Inprocessing for the Maximum K-plex Problem}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2023},
  doi = {10.24963/ijcai.2023/623},
}
Figure