Improving Maximum k-plex Solver via Second-Order Reduction and Graph Color Bounding

Yi Zhou, Shan Hu, Mingyu Xiao, Zhang-Hua FuAAAI 2021 · DOI

Introduction

In network analysis and community detection, identifying cohesive subgroups is a fundamental task. While the clique—a subgraph where every pair of vertices is connected—is the gold standard for cohesiveness, it is often too restrictive for real-world data. Social networks, biological systems, and collaboration graphs frequently contain "near-cliques" where a few expected links are missing. To address this, researchers use the $k$-plex: a relaxed clique where each vertex is allowed to miss at most $k$ connections to other members of the set.

Finding the Maximum $k$-Plex (MPLEX) is an NP-hard problem. As modern graphs scale to millions of nodes and edges, exact solvers often face exponential time complexity. This paper introduces Maplex, an exact solver that leverages second-order graph reduction and generalized graph coloring to significantly improve performance on massive real-world networks.

Methodology: The Maplex Framework

The Maplex solver operates in three distinct phases designed to prune the search space as early as possible.

1. Heuristic Initialization

The process begins with a fast greedy search to establish a high-quality lower bound ($lb$). This initial solution provides a target size that the subsequent exact search must exceed, allowing for more aggressive pruning.

2. Second-Order Graph Reduction

Standard preprocessing techniques typically rely on "first-order" rules, such as removing vertices with degrees too low to participate in a $k$-plex of size $lb+1$. Maplex introduces a more powerful second-order reduction rule. By examining pairs of vertices $(u, v)$ and their common neighbors, the solver can identify edges or vertices that cannot coexist in an optimal solution. This rule is implemented using an efficient triangle-listing algorithm, making it significantly faster than previous strong inference methods while achieving superior graph reduction.

3. Branch-and-Bound with Graph Color Bounding

The core search phase utilizes a branch-and-bound approach. A key innovation in Maplex is the generalization of graph coloring for $k$-plexes. In traditional clique solvers, an independent set (a set of vertices with no mutual edges) can contribute at most one vertex to a clique. The authors prove that for a $k$-plex, an independent set $I_i$ can contribute at most $\min(|I_i|, k)$ vertices.

Pseudocode for the Branch-and-Bound search with graph color bounding.

As shown in the algorithm above, this property is used to compute a tight upper bound ($ub$) and a "lookahead" bound ($ub_u$) to prune branches of the search tree that cannot yield a better solution than the current $lb$.

Experimental Evaluation

The authors evaluated Maplex against 139 real-world graphs from the Network Repository and various artificial benchmarks. The suite included social, biological, and infrastructure networks of varying densities.

Key Results

Maplex demonstrated clear superiority over existing state-of-the-art solvers like BnBk, BS, and RDS.

  • Graph Reduction: On the socfb-A-anon network, which contains nearly 400,000 vertices, Maplex's second-order reduction shrunk the problem to just 2,155 vertices for $k=2$, a reduction of over 99%.
  • Solving Efficiency: Maplex solved 17 more instances than the previous best solver (BnBk) within a 30-minute time limit.
  • Performance across $k$: The solver maintained its lead as $k$ increased from 2 to 5.
Comparison of Maplex against state-of-the-art solvers across different values of k.

As illustrated in the performance plots, Maplex (blue line) consistently solves more instances in less time than its competitors across all tested values of $k$. Its advantage is particularly pronounced in the early stages of the search, often solving problems in seconds that other methods struggle with for minutes.

Conclusion and Future Work

Maplex advances the state-of-the-art in exact $k$-plex solving by combining efficient second-order preprocessing with a novel bounding technique derived from graph coloring. While it excels on large, sparse real-world networks, performance still degrades for very large $k$ or extremely dense artificial graphs. Future research may explore integrating Boolean satisfiability (SAT) reasoning to further tighten bounds, potentially overcoming current limitations in dense graph environments.

Summary updated

BibTeX
@inproceedings{zhou2021improving,
  author = {Yi Zhou and Shan Hu and Mingyu Xiao and Zhang-Hua Fu},
  title = {{Improving Maximum k-plex Solver via Second-Order Reduction and Graph Color Bounding}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.1609/aaai.v35i14.17477},
}
Figure