# Cohesive Group Discovery in Interaction Graphs under Explicit Density Constraints

arXiv: https://arxiv.org/abs/2508.04174 · HTML: https://mlsanity.com/paper/2508.04174/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 4 of its 39 references that are in the map.
- First posted on arXiv 6 Aug 2025.

## Builds on (most cited first, 4 of 4)

- [Heat kernel based community detection](https://mlsanity.com/paper/1403.3148/) (2014)
- [Farsighted Probabilistic Sampling: A General Strategy for Boosting Local Search MaxSAT Solvers](https://mlsanity.com/paper/2108.09988/) (2021)
- [Maximum Degree-Based Quasi-Clique Search via an Iterative Framework](https://mlsanity.com/paper/2505.15118/) (2025)
- [HyColor: An Efficient Heuristic Algorithm for Graph Coloring](https://mlsanity.com/paper/2506.07373/) (2025)

## Abstract (arXiv)

Discovering cohesive groups is a fundamental primitive in graph-based recommender systems, underpinning tasks such as social recommendation, bundle discovery, and community-aware modeling. In interaction graphs, cohesion is often modeled as the γ-quasi-clique, an induced subgraph whose internal edge density meets a user-defined threshold γ. This formulation provides explicit control over within-group connectivity while accommodating the sparsity inherent in real-world data. This paper presents EDQC, an effective framework for cohesive group discovery under explicit density constraints. EDQC leverages a lightweight energy diffusion process to rank vertices for localizing promising candidate regions. Guided by this ranking, the framework extracts and refines a candidate subgraph to ensure the output strictly satisfies the target density requirement. Extensive experiments on 75 real-world graphs across varying density thresholds demonstrate that EDQC identifies the largest mean γ-quasi-cliques in the vast majority of cases, achieving lower variance than the state-of-the-art methods while maintaining competitive runtime. Furthermore, statistical analysis confirms that EDQC significantly outperforms the baselines, underscoring its robustness and practical utility for cohesive group discovery in graph-based recommender systems.