Enumerating Maximal k-Plexes with Worst-Case Time Guarantee

Yi Zhou, Jingwei Xu, Zhenyu Guo, Mingyu Xiao, Yan JinAAAI 2020 · DOI

In graph theory and network analysis, identifying cohesive subgroups is a fundamental task. While the concept of a clique—a subgraph where every vertex is connected to every other vertex—is mathematically elegant, it is often too restrictive for real-world data. Social networks, biological systems, and recommendation engines typically exhibit "clique-like" structures that are dense but not perfectly complete. This has led to the study of the $k$-plex, a more flexible model where each vertex is allowed to miss connections to at most $k-1$ other members of the group.

Despite their utility, enumerating all maximal $k$-plexes is a computationally daunting task. Most existing algorithms are adaptations of the Bron-Kerbosch method, which, while efficient for cliques ($k=1$), often degrades to a brute-force complexity of $O(n^2 2^n)$ for $k > 1$. A recent paper presented at AAAI-20 by researchers from the University of Electronic Science and Technology of China and Huazhong University of Science and Technology introduces FaPlexen and CommuPlex, providing the first-ever worst-case time guarantees for this problem.

The FaPlexen Algorithm and Pivot Heuristic

The core theoretical contribution of the work is FaPlexen, the first algorithm to enumerate maximal $k$-plexes with a provable worst-case time complexity better than $O(2^n)$. Specifically, it achieves a bound of $O(n^2 \gamma^n)$, where $\gamma < 2$ is the largest real root of $x^{k+2} - 2x^{k+1} + 1 = 0$. For $k=2$, this results in a complexity of approximately $O(n^2 1.839^n)$.

This breakthrough is achieved through a novel pivot heuristic. In traditional clique finding, a pivot vertex is used to prune branches of the search tree that cannot lead to a maximal clique. FaPlexen extends this logic to $k$-plexes by identifying a "minimum degree" vertex in the candidate set. By branching on the non-neighbors of this pivot, the algorithm can mathematically bound the search space and avoid redundant computations.

Branching logic and pivot vertex selection in FaPlexen illustrating the sets P, Cand, and Doing.

Scaling to Massive Networks with CommuPlex

While FaPlexen provides theoretical bounds, the researchers also developed CommuPlex for practical application on massive real-world graphs containing millions of nodes. CommuPlex incorporates several advanced pruning strategies:

  1. Degeneracy Ordering: Vertices are processed in an order that prioritizes sparse areas of the graph, reducing the overhead in early stages of the search.
  2. Diameter-Based Pruning: The authors leverage a critical property: any $k$-plex with a size $\ge 2k-2$ must have a diameter of at most 2. This allows the algorithm to immediately ignore any vertex that is more than two hops away from the current candidate set, drastically reducing the search tree's breadth in large networks.

Experimental Results

The algorithms were evaluated against synthetic random graphs, DIMACS benchmarks, and massive real-world datasets like soc-pokec (1.6M nodes) and Amazon0505.

Performance comparison of FaPlexen against state-of-the-art algorithms GP and LP for various k values, showing running time vs. solved instances.

As shown in the performance plots, FaPlexen consistently outperforms existing state-of-the-art algorithms (GP and LP) by 2 to 10 orders of magnitude. On real-world community detection tasks, CommuPlex successfully processed graphs where previous champions, such as the D2K algorithm, either timed out or exceeded memory limits. For instance, on the soc-Epinions1 graph with $k=4$, CommuPlex completed the task in approximately 53,000 seconds, while competing methods failed to finish.

Conclusion

By breaking the $O(2^n)$ "exponential wall" for $k$-plex enumeration, this research provides both a solid theoretical foundation and a highly efficient practical tool for network analysis. While the problem remains NP-hard, the reduction of the exponential base and the introduction of diameter-based pruning represent significant steps forward. Future work may involve extending these guarantees to dynamic or temporal graphs where edge relationships evolve over time.

Summary updated

BibTeX
@inproceedings{zhou2020enumerating,
  author = {Yi Zhou and Jingwei Xu and Zhenyu Guo and Mingyu Xiao and Yan Jin},
  title = {{Enumerating Maximal k-Plexes with Worst-Case Time Guarantee}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2020},
  doi = {10.1609/aaai.v34i03.5625},
}
Figure