Efficient Computation of Maximum Flexi-Clique in Networks

Song Kim, Hyewon Kim, Kaiqiang Yu, Taejoon Han, Junghoon Kim, Susik Yoon, Jungeun Kim

Abstract

Discovering large cohesive subgraphs is a key task for graph mining. Existing models, such as clique, k-plex, and γ-quasi-clique, use fixed density thresholds that overlook the natural decay of connectivity as the subgraph size increases. The Flexi-clique model overcomes this limitation by imposing a degree constraint that grows sub-linearly with subgraph size. We provide the algorithmic study of Flexi-clique, proving its NP-hardness and analysing its non-hereditary properties. To address its computational challenge, we propose the Flexi-Prune Algorithm FPA, a fast heuristic using core-based seeding and connectivity-aware pruning, and the Efficient Branch-and-Bound Algorithm EBA, an exact framework enhanced with multiple pruning rules. Experiments on large real-world and synthetic networks demonstrate that FPA achieves near-optimal quality at much lower cost, while EBA efficiently computes exact solutions. Flexi-clique thus provides a practical and scalable model for discovering large, meaningful subgraphs in complex networks.

Introduction

Finding cohesive subgraphs—tightly knit communities—is a fundamental task in graph mining. Traditional models like cliques, $k$-plexes, and $\gamma$-quasi-cliques enforce strict, size-invariant density thresholds. For example, a clique requires every node to be connected to every other node, regardless of whether the group has 5 members or 5,000.

However, empirical data shows that as real-world communities grow, their internal connectivity naturally decays in a sub-linear fashion. The Flexi-clique model addresses this by imposing a degree constraint that scales sub-linearly with the subgraph's size (specifically, each node must have at least $\lfloor |H|^\tau \rfloor$ neighbors, where $\tau < 1$).

Comparison of degree thresholds across different subgraph models.

The Flexi-clique Model and its Challenges

While the Flexi-clique model is highly realistic, it is computationally brutal. The authors prove it is NP-hard and inapproximable within a constant factor. A significant hurdle is that it lacks the hereditary property. In traditional models, any subset of a clique is also a clique. In the Flexi-clique model, a valid subgraph might become invalid if you remove just one node because the required density threshold tightens as the group shrinks.

Illustration of Flexi-clique and the non-hereditary property.

This non-heredity is actually a feature that captures real-world group dynamics: a large community might only be viable because of its size. However, it renders standard exact algorithms for subgraph search, which rely on hereditary properties to prune search trees, ineffective.

Algorithmic Framework

To tackle this computationally hostile model, the authors propose two algorithms:

  1. Flexi-Prune Algorithm (FPA): A fast heuristic that finds a high-quality solution quickly. It uses $k$-core decomposition to find a dense "seed" region and then iteratively prunes the lowest-degree nodes. To ensure the subgraph doesn't fracture, FPA uses a dynamic spanning forest data structure (link-cut trees) to check connectivity in logarithmic time.
  2. Efficient Branch-and-Bound Algorithm (EBA): An exact algorithm that guarantees finding the maximum Flexi-clique. It uses FPA's output as a strong initial lower bound. To handle non-heredity, EBA introduces Connectivity-Preserving Branching (CP-Branching) and employs six aggressive pruning rules based on degree bounds, graph diameter, and cascading "follower" exclusions.

Experimental Evaluation

The authors evaluated their algorithms on 9 real-world networks from the KONECT repository (e.g., Amazon, DBLP) and synthetic LFR benchmark graphs.

  • Effectiveness: FPA achieves >90% of the optimal solution size on most datasets.
  • Efficiency: FPA is incredibly fast, finishing the 317k-node DBLP graph in ~10.5 seconds. EBA solved the same graph in just ~19.8 seconds, significantly outperforming previous baseline heuristics.
  • Real-world Alignment: In a temporal case study on the Eu-mail network, Flexi-cliques closely tracked the actual evolution of ground-truth communities, whereas cliques and $k$-plexes failed to capture the natural density decay of growing groups.

Conclusion

The Flexi-clique model offers a more nuanced approach to community detection by allowing connectivity requirements to relax naturally as groups grow. By introducing efficient heuristic and exact algorithms, the authors make size-adaptive community detection practical for large-scale graphs. Future work includes extending the model to dynamic and attributed graphs and tackling the enumeration of all maximal Flexi-cliques.

Summary updated

Abstract

Discovering large cohesive subgraphs is a key task for graph mining. Existing models, such as clique, k-plex, and γ-quasi-clique, use fixed density thresholds that overlook the natural decay of connectivity as the subgraph size increases. The Flexi-clique model overcomes this limitation by imposing a degree constraint that grows sub-linearly with subgraph size. We provide the algorithmic study of Flexi-clique, proving its NP-hardness and analysing its non-hereditary properties. To address its computational challenge, we propose the Flexi-Prune Algorithm FPA, a fast heuristic using core-based seeding and connectivity-aware pruning, and the Efficient Branch-and-Bound Algorithm EBA, an exact framework enhanced with multiple pruning rules. Experiments on large real-world and synthetic networks demonstrate that FPA achieves near-optimal quality at much lower cost, while EBA efficiently computes exact solutions. Flexi-clique thus provides a practical and scalable model for discovering large, meaningful subgraphs in complex networks.
BibTeX
@misc{kim2026efficient,
  author = {Song Kim and Hyewon Kim and Kaiqiang Yu and Taejoon Han and Junghoon Kim and Susik Yoon and Jungeun Kim},
  title = {{Efficient Computation of Maximum Flexi-Clique in Networks}},
  year = {2026},
  eprint = {2602.10459},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2602.10459},
}
Figure