A New Upper Bound Based on Vertex Partitioning for the Maximum K-plex Problem

Hua Jiang, Dongming Zhu, Zhichao Xie, Shaowen Yao, Zhang-Hua FuIJCAI 2021 · DOI

TL;DR

This paper introduces a novel "Partitioning-based Upper Bound" (PUB) for the Maximum k-plex Problem (MKP), a computationally challenging task of finding the largest cohesive subgroup in a network. By leveraging the structure of partially built solutions, their new upper bound significantly prunes the search space, leading to a more efficient exact algorithm (KpLeX) that outperforms state-of-the-art methods on various large-scale real-world and synthetic network datasets.

What Problem Does This Paper Address?

Identifying cohesive subgroups within large networks is crucial for understanding social dynamics, community structures, and information diffusion. The Maximum k-plex Problem (MKP) is a formalization of this, aiming to find the largest subset of vertices where each vertex is connected to at least all but k-1 other vertices within that subset. While related to the well-studied Maximum Clique Problem (k=1), MKP is more flexible and applicable to real-world networks where perfect connectivity isn't always required.

Existing exact algorithms for MKP often rely on branch-and-bound (BnB) techniques. However, their effectiveness is heavily dependent on the quality of "upper bounds" used to prune the search space. Previous upper bounds for MKP have struggled to be both tight and computationally efficient, especially compared to those developed for the Maximum Clique Problem. This paper addresses the need for a more effective upper bound that can significantly accelerate MKP solvers, particularly for the massive graphs encountered in modern data analysis.

Methods

The core contribution of this paper is the Partitioning-based Upper Bound (PUB). This new bound is derived by considering a "growing" k-plex (a partial solution) and the set of candidate vertices that could potentially extend it. The key idea is to partition the candidate set based on its relationship to the vertices already in the growing k-plex.

Specifically, for a growing k-plex $S$ and a candidate set $P$, they define a partition $\Pi = \{\pi_0, \pi_1, \dots, \pi_q\}$ of $P$, where $q = |S|$.

  • $\pi_0$ contains vertices in $P$ adjacent to all vertices in $S$.
  • $\pi_i$ (for $i > 0$) contains vertices in $P$ that are not adjacent to the $i$-th vertex in $S$.

Using this partition and an array $\Delta$ that quantifies the number of non-neighbors for each vertex in $S$, they derive Lemma 1, which provides the upper bound: $|S| + |\pi_0| + \sum_{i=1}^{q} \min\{k - 1 - \delta_i, |\pi_i|\}$. This bound is "tight" because it directly considers the constraints imposed by the current partial solution $S$ on the candidate vertices.

They integrate this PUB into a new branch-and-bound algorithm called KpLeX. KpLeX includes a preprocessing step to find an initial solution and reduce the graph, followed by a recursive BnB search that utilizes the PUB for pruning. A specific pruning technique, "Pro3-based pruning," is also employed at shallower levels of the search tree for dense graphs.

Datasets

The paper evaluates KpLeX on four types of datasets:

  • 2nd DIMACS graphs: 80 graphs with up to 4000 vertices and varying densities.
  • Real-world massive graphs: 139 sparse graphs from the Network Data Repository.
  • 10th DIMACS graphs: 82 graphs with up to $2 \times 10^7$ vertices.
  • Random generated graphs: 120 graphs of 1000 vertices with six different densities.

Key Insights and Ideas

  • Exploiting Partial Solutions: The most significant insight is that the structure of a partially built k-plex is highly informative for bounding future extensions. Unlike previous methods that might partition the entire graph or candidate set independently of the current solution, PUB directly leverages the relationship between the growing solution and the candidate pool.
  • Tightness and Efficiency Trade-off: The PUB is designed to be both tight (leading to better pruning) and computationally efficient. The partitioning step's complexity is $O(|S| \times |P|)$, which is manageable within the BnB framework.
  • Synergy with Other Pruning: The paper shows that while PUB is crucial, other pruning strategies like Pro3-based pruning can further enhance performance, especially for specific graph structures or search tree depths.
  • MKP's Intractability: The paper highlights that MKP is generally more difficult than MCP, as the relaxed adjacency constraint in k-plexes (for $k>1$) makes it harder to apply existing clique-finding bounds directly.

Key Results

  • Superior Performance: KpLeX, using the PUB, significantly outperforms three state-of-the-art exact algorithms (BS, BnBK, and Maplex) across all tested datasets and for $k$ values from 2 to 6. For instance, on the 2nd DIMACS graphs at $k=2$, KpLeX solved 27 instances, which was 1.2 to 1.8 times more than the other algorithms.
  • Scalability: KpLeX demonstrates strong performance on massive graphs, including those with millions of vertices.
  • Effectiveness of PUB: Experiments with variants of KpLeX show that disabling the PUB (KpLeX\PUB) leads to a dramatic increase in search tree size and running time, underscoring its critical role. Disabling Pro3-based pruning (KpLeX\Pro3) had a less severe impact, suggesting PUB is the primary driver of efficiency.
  • Graph Reduction: The preprocessing step in KpLeX effectively reduces the graph size, often removing over 99% of vertices, with initial solution quality comparable to other methods.

Limitations and Future Work

  • Growing Solution Dependency: The paper notes that the pruning ability of PUB is limited when the growing solution $S$ is small. This is why Pro3-based pruning is used at shallower search tree levels.
  • Computational Cost of Pro3-Pruning: The Pro3-based pruning step is computationally expensive ($O(|V|^2)$) and is restricted to shallower search tree levels to maintain efficiency, especially on dense graphs.
  • Future Work: The authors suggest that further research could explore more sophisticated ordering strategies for constructing the partition to potentially achieve even better pruning. They also imply that the effectiveness of PUB could be further explored in conjunction with other advanced bounding techniques.

Summary updated

BibTeX
@inproceedings{jiang2021new,
  author = {Hua Jiang and Dongming Zhu and Zhichao Xie and Shaowen Yao and Zhang-Hua Fu},
  title = {{A New Upper Bound Based on Vertex Partitioning for the Maximum K-plex Problem}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.24963/ijcai.2021/233},
}
Figure