Maximum k-Plex Search: An Alternated Reduction-and-Bound Method

Summary: Introduces AltRB, an alternating reduction/bounding strategy for branch-and-bound maximum k-plex search, replacing sequential RB with partitioned iterative pruning. Combined with new rules and preprocessing, kPEX scales up to 100× faster across 664 graphs. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: h5c505faa8df39867
Venue: VLDB
Year: 2025
Pagerank: 5.124163e-05
Overall Rank: 9,714 | 34.89%
DOI: 10.14778/3705829.3705851
PDF: Download (CC BY-NC-ND 4.0)

Incoming Non-self Citations Over Time

Authors

1. Shuohao Gao (Harbin Engineering University)
2. Kaiqiang Yu (Nanyang Technological University)
3. Shengxin Liu (Harbin Engineering University)
4. Cheng Long (Nanyang Technological University)

BibTeX Citation

@article{gao_vldb25,
        title = {{Maximum k-Plex Search: An Alternated Reduction-and-Bound Method}},
        author = {Gao, Shuohao and Yu, Kaiqiang and Liu, Shengxin and Long, Cheng},
        journal = {PVLDB},
        series = {{VLDB} '25},
        volume = {18},
        number = {2},
        pages = {363--376},
        doi = {10.14778/3705829.3705851},
        url = {https://doi.org/10.14778/3705829.3705851},
        year = {2025}
}

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
8,913	Efficient Defective Clique Enumeration and Search with Worst-Case Optimal Search Space	2026	SIGMOD	5.2361195e-05
10,395	Efficient Querying of Maximum Connectivity-Based Quasi-Cliques in Large Graphs	2027	SIGMOD	4.9605343e-05
10,868	Revisiting the Maximum Defective Clique Problem: Faster Branching and a Tighter Upper Bound	2026	VLDB	4.9605343e-05

Outgoing Citations (Sorted by Pagerank)

Showing 15 of 15 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
96	Truss Decomposition in Massive Networks	2012	VLDB	0.00034261728
182	Querying K-Truss Community in Large and Dynamic Graphs	2014	SIGMOD	0.00026383593
1,591	Efficient Enumeration of Maximal k-Plexes	2015	SIGMOD	0.00010107236
1,802	Efficient Exact Algorithms for Maximum Balanced Biclique Search in Bipartite Graphs	2021	SIGMOD	9.598858e-05
2,314	Efficient Algorithms for Maximal k-Biplex Enumeration	2022	SIGMOD	8.6412801e-05
3,000	Efficient Maximum k-Plex Computation over Large Sparse Graphs	2023	VLDB	7.7498183e-05
3,591	Efficient Maximum k-Defective Clique Computation with Improved Time Complexity	2023	SIGMOD	7.1655231e-05
3,881	Cohesive Subgraph Search over Big Heterogeneous Information Networks: Applications, Challenges, and Solutions	2021	SIGMOD	6.9309694e-05
4,155	Maximal Defective Clique Enumeration	2023	SIGMOD	6.7613076e-05
4,606	Maximum k-Biplex Search on Bipartite Graphs: A Symmetric-BK Branching Approach	2023	SIGMOD	6.4898086e-05
4,753	Fast Maximal Clique Enumeration on Uncertain Graphs: A Pivot-based Approach	2022	SIGMOD	6.4218566e-05
4,779	Scalable Mining of Maximal Quasi-Cliques: An Algorithm-System Codesign Approach	2021	VLDB	6.4069971e-05
5,066	Maximum k-Plex Computation: Theory and Practice	2024	SIGMOD	6.2786224e-05
5,500	Hereditary Cohesive Subgraphs Enumeration on Bipartite Graphs: The Power of Pivot-based Approaches	2023	SIGMOD	6.0910824e-05
7,017	Fast Maximal Quasi-clique Enumeration: A Pruning and Branching Co-Design Approach	2023	SIGMOD	5.6041834e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	3,597	Efficient k-Clique Listing: An Edge-Oriented Branching Strategy	2024	SIGMOD
2	10,868	Revisiting the Maximum Defective Clique Problem: Faster Branching and a Tighter Upper Bound	2026	VLDB
3	8,913	Efficient Defective Clique Enumeration and Search with Worst-Case Optimal Search Space	2026	SIGMOD
4	3,591	Efficient Maximum k-Defective Clique Computation with Improved Time Complexity	2023	SIGMOD
5	5,569	Theoretically and Practically Efficient Maximum Defective Clique Search	2024	SIGMOD
6	4,606	Maximum k-Biplex Search on Bipartite Graphs: A Symmetric-BK Branching Approach	2023	SIGMOD
7	11,359	Maximum k-Plex Finding: Choices of Pruning Techniques Matter!	2025	VLDB
8	1,591	Efficient Enumeration of Maximal k-Plexes	2015	SIGMOD
9	5,066	Maximum k-Plex Computation: Theory and Practice	2024	SIGMOD
10	3,000	Efficient Maximum k-Plex Computation over Large Sparse Graphs	2023	VLDB