基于图组合优化的高效社区搜索

针对大多数基于图神经网络（Graph Neural Network，GNN）的社区搜索方法中存在的时间开销巨大和“搭便车”效应问题，本文提出一种基于图组合优化的高效社区搜索模型（Efficient Community Search Based on Graph Combinatorial Optimization，CS-ROMF）。该模型设计基于GNN的社区定位器来快速定位查询节点的潜在社区，减少时间开销。在此基础上设计基于强化学习（Reinforcement Learning，RL）的社区优化器调整候选社区的结构，减轻“搭便车”效应。在5个具有真实社区的数据集上进行大量实验，结果表明CS-ROMF在所有评估指标上均优于基线模型。其中，相比结果最好的基线模型，CS-ROMF在F 1值、Jaccard值以及NMI上分别最高提升14.99%、20.67%和21.37%，表明CS-ROMF减轻了“搭便车”效应。同时，CS-ROMF能够显著提升搜索效率，其运行速度比基于GNN的基线模型最多快10倍。

To address the significant time overhead and free-rider effect in most GNN-based community search methods, this paper proposes an efficient community search based on graph combinatorial optimization (CS-ROMF). CS-ROMF designs a GNN-based community locator to quickly pinpoint potential communities of the query nodes, thereby reducing time overhead. On this basis, CS-ROMF further designs an RL-based community optimizer to adjust the structure of candidate communities, mitigating the free-rider effect. Experiments conducted on five real-world datasets with true communities demonstrate that CS-ROMF outperforms advanced community search methods across all evaluation metrics. Specifically, compared to the best baseline model, CS-ROMF achieves maximum improvements of 14.99%, 20.67%, and 21.37% in F1 score, Jaccard score, and NMI, respectively. Additionally, CS-ROMF can significantly improve search efficiency, running up to 10 times faster than the baseline model based on GNN.