arXiv:2508.04174cs.SIcs.AI2025-08

提出EDQC框架,高效发现满足密度要求的紧密群体。

Cohesive Group Discovery in Interaction Graphs under Explicit Density Constraints

  • 用轻量级能量扩散排序顶点,定位潜在高密度区域
  • 在75个真实图上平均找到最大γ-准团,方差更小
  • 适合社交推荐、商品组合等需要紧密群体的任务

发现紧密群体是基于图的推荐系统中的基础任务,支撑社交推荐、商品组合发现和社区感知建模等应用。在交互图中,紧密性常以γ-准团(γ-quasi-clique)建模,即内部边密度达到用户定义阈值γ的导出子图。该形式可显式控制组内连接度,同时适应真实数据的稀疏性。本文提出EDQC框架,在显式密度约束下实现高效的紧密群体发现。该框架利用轻量级能量扩散过程对顶点排序,以定位有潜力的候选区域;再基于此排序提取并优化候选子图,确保输出严格满足目标密度要求。在75个不同密度阈值的真实图上进行的大量实验表明,EDQC在绝大多数情况下识别出最大的平均γ-准团,且方差低于现有最先进方法,同时保持了具有竞争力的运行时间。统计分析进一步证实,EDQC显著优于基线方法,凸显其在图推荐系统中发现紧密群体的鲁棒性与实用性。

原文摘要 · Abstract (English)

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.

图挖掘群体发现密度约束

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。