Cohesive Group Discovery in Interaction Graphs under Explicit Density Constraints
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915745427881984 |
|---|---|
| author | Zhang, Yu Luo, Yilong Ma, Mingyuan Chen, Yao Zhu, Enqiang Xu, Jin Liu, Chanjuan |
| author_facet | Zhang, Yu Luo, Yilong Ma, Mingyuan Chen, Yao Zhu, Enqiang Xu, Jin Liu, Chanjuan |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_04174 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Cohesive Group Discovery in Interaction Graphs under Explicit Density Constraints Zhang, Yu Luo, Yilong Ma, Mingyuan Chen, Yao Zhu, Enqiang Xu, Jin Liu, Chanjuan Social and Information Networks Artificial Intelligence 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. |
| title | Cohesive Group Discovery in Interaction Graphs under Explicit Density Constraints |
| topic | Social and Information Networks Artificial Intelligence |
| url | https://arxiv.org/abs/2508.04174 |