{"ID":2885619,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2508.04174","arxiv_id":"2508.04174","title":"Cohesive Group Discovery in Interaction Graphs under Explicit Density Constraints","abstract":"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.","short_abstract":"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 u...","url_abs":"https://arxiv.org/abs/2508.04174","url_pdf":"https://arxiv.org/pdf/2508.04174v3","authors":"[\"Yu Zhang\",\"Yilong Luo\",\"Mingyuan Ma\",\"Yao Chen\",\"Enqiang Zhu\",\"Jin Xu\",\"Chanjuan Liu\"]","published":"2025-08-06T07:59:56Z","proceeding":"cs.SI","tasks":"[\"cs.SI\",\"cs.AI\"]","methods":"[\"Diffusion Model\"]","has_code":false}