Efficient Maximum k-Plex Computation over Large Sparse Graphs

Summary: kPlexS computes exact maximum k-plexes in large sparse graphs by repeatedly extracting small dense subgraphs and applying branch-and-bound. CTCP reductions and matrix-based BBMatrix exploit vertex/edge and pairwise structure, outperforming prior methods empirically. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: h20c3496ccdcf2760
Venue: VLDB
Year: 2023
Pagerank: 7.5528776e-05
Overall Rank: 3,189 | 78.57%
DOI: 10.14778/3565816.3565817

Incoming Non-self Citations Over Time

Authors

1. Lijun Chang (University of Sydney)
2. Mouyi Xu (University of Sydney)
3. Darren Strash (Hamilton College)

BibTeX Citation

@article{chang_vldb23,
        title = {{Efficient Maximum k-Plex Computation over Large Sparse Graphs}},
        author = {Chang, Lijun and Xu, Mouyi and Strash, Darren},
        journal = {PVLDB},
        series = {{VLDB} '23},
        volume = {16},
        number = {2},
        pages = {127--139},
        doi = {10.14778/3565816.3565817},
        url = {https://doi.org/10.14778/3565816.3565817},
        year = {2023}
}

Incoming Citations (Sorted by Pagerank)

Showing 11 of 11 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
5,552	Theoretically and Practically Efficient Maximum Defective Clique Search	2024	SIGMOD	6.0860432e-05
5,585	Maximum k-Plex Computation: Theory and Practice	2024	SIGMOD	6.0761018e-05
8,671	Enabling Window-Based Monotonic Graph Analytics with Reusable Transitional Results for Pattern-Consistent Queries	2024	VLDB	5.2917782e-05
8,884	Efficient Defective Clique Enumeration and Search with Worst-Case Optimal Search Space	2026	SIGMOD	5.2559789e-05
9,677	Efficient Maximum s-Bundle Search via Local Vertex Connectivity	2025	SIGMOD	5.1435978e-05
9,678	Maximum k-Plex Search: An Alternated Reduction-and-Bound Method	2025	VLDB	5.1435978e-05
10,495	Querying Cohesive Subgraphs in Temporal Graphs	2026	SIGMOD	4.9793485e-05
10,614	Accelerating Triangle-Connected Truss Community Search Across Heterogeneous Hardware	2026	SIGMOD	4.9793485e-05
10,789	CREST: Approximate k-Clique Counting in Real-World Networks via Refinement of Star-Based Sample Space	2026	VLDB	4.9793485e-05
10,797	Revisiting the Maximum Defective Clique Problem: Faster Branching and a Tighter Upper Bound	2026	VLDB	4.9793485e-05
11,296	Maximum k-Plex Finding: Choices of Pruning Techniques Matter!	2025	VLDB	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 3 of 3 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
100	Truss Decomposition in Massive Networks	2012	VLDB	0.00033977856
1,507	Finding the Maximum Clique in Massive Graphs	2017	VLDB	0.00010450256
1,616	Efficient Enumeration of Maximal k-Plexes	2015	SIGMOD	0.00010066712

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	3,412	Scaling Up k-Clique Densest Subgraph Detection	2023	SIGMOD
2	3,610	Efficient k-Clique Listing: An Edge-Oriented Branching Strategy	2024	SIGMOD
3	4,612	Maximum k-Biplex Search on Bipartite Graphs: A Symmetric-BK Branching Approach	2023	SIGMOD
4	5,552	Theoretically and Practically Efficient Maximum Defective Clique Search	2024	SIGMOD
5	10,797	Revisiting the Maximum Defective Clique Problem: Faster Branching and a Tighter Upper Bound	2026	VLDB
6	3,860	Efficient Maximum k-Defective Clique Computation with Improved Time Complexity	2023	SIGMOD
7	11,296	Maximum k-Plex Finding: Choices of Pruning Techniques Matter!	2025	VLDB
8	1,616	Efficient Enumeration of Maximal k-Plexes	2015	SIGMOD
9	9,678	Maximum k-Plex Search: An Alternated Reduction-and-Bound Method	2025	VLDB
10	5,585	Maximum k-Plex Computation: Theory and Practice	2024	SIGMOD