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

张安冉; 王兴芬; 赵雨涵; 李立博

doi:10.12263/DZXB.20240767

您当前的位置：

首页 >

文章列表页 >

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

学术论文 | 更新时间：2025-12-08

- 基于图组合优化的高效社区搜索
- CS-ROMF:Efficient Community Search Based on Graph Combinatorial Optimization
- 电子学报 2025年53卷第2期页码：440-450
- 作者机构：
  
  1.北京信息科技大学，北京 102206
  2.香港浸会大学，香港 999077
- 作者简介：
  
  [ "张安冉女，1999年1月出生.现为北京信息科技大学网络空间安全专业硕士研究生.主要研究方向为数据挖掘与复杂网络. E-mail: 2022020934@bistu.edu.cn" ]
  [ "王兴芬女，1968年9月出生.2005年毕业于哈尔滨工业大学管理学院.现任北京信息科技大学党委常委、副校长、教授、博士生导师.主要研究方向为大数据及商务分析、信息管理与智能决策等. E-mail: xfwang@bistu.edu.cn" ]
  [ "赵雨涵男，1999年10月出生.现为香港浸会大学博士研究生.主要研究方向为数据挖掘与推荐系统. E-mail: csyhzhao@comp.hkbu.edu.hk" ]
  [ "李立博男，1999年3月出生.现为北京信息科技大学管理科学与工程专业硕士研究生.主要研究方向为大数据挖掘与分析、时间序列预测. E-mail: 2022020958@bistu.edu.cn" ]
- 基金信息：
- DOI：10.12263/DZXB.20240767
  中图分类号： TP183;TP301
- 收稿：2024-08-19，
  
  修回：2024-12-16，
  
  纸质出版：2025-02-25
- 稿件说明：
移动端阅览
张安冉, 王兴芬, 赵雨涵, 等. 基于图组合优化的高效社区搜索[J]. 电子学报, 2025, 53(02): 440-450.

ZHANG An-ran, WANG Xing-fen, ZHAO Yu-han, et al. CS-ROMF:Efficient Community Search Based on Graph Combinatorial Optimization[J]. Acta Electronica Sinica, 2025, 53(02): 440-450.
张安冉, 王兴芬, 赵雨涵, 等. 基于图组合优化的高效社区搜索[J]. 电子学报, 2025, 53(02): 440-450. DOI：10.12263/DZXB.20240767

ZHANG An-ran, WANG Xing-fen, ZHAO Yu-han, et al. CS-ROMF:Efficient Community Search Based on Graph Combinatorial Optimization[J]. Acta Electronica Sinica, 2025, 53(02): 440-450. DOI：10.12263/DZXB.20240767

摘要

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

值、Jaccard值以及NMI上分别最高提升14.99%、20.67%和21.37%，表明CS-ROMF减轻了“搭便车”效应.同时，CS-ROMF能够显著提升搜索效率，其运行速度比基于GNN的基线模型最多快10倍.

Abstract

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

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.

关键词

Keywords

references

杜明 , 宋嘉祎 , 周军锋 . 规模受限的影响力社区搜索 [J ] . 电子学报 , 2023 , 51 ( 5 ): 1207 - 1214 .

DU M , SONG J Y , ZHOU J F . Size-constrained influential community search [J ] . Acta Electronica Sinica , 2023 , 51 ( 5 ): 1207 - 1214 . (in Chinese)

HU A L , CHAN K C C . Utilizing both topological and attribute information for protein complex identification in PPI networks [J ] . IEEE/ACM Transactions on Computational Biology and Bioinformatics , 2013 , 10 ( 3 ): 780 - 792 .

LIU Y F , LIU Z , FENG X D , et al . Robust attributed network embedding preserving community information [C ] // 2022 IEEE 38th International Conference on Data Engineering (ICDE) . Piscataway : IEEE , 2022 : 1874 - 1886 .

SU X , XUE S , LIU F Z , et al . A comprehensive survey on community detection with deep learning [J ] . IEEE Transactions on Neural Networks and Learning Systems , 2024 , 35 ( 4 ): 4682 - 4702 .

SOZIO M , GIONIS A . The community-search problem and how to plan a successful cocktail party [C ] // Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining . New York : ACM , 2010 : 939 - 948 .

TANG J B , YANG Y H , WEI W , et al . HiGPT: Heterogeneous graph language model [C ] // Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining . New York : ACM , 2024 : 2842 - 2853 .

FETTAL C , LABIOD L , NADIF M . Scalable attributed-graph subspace clustering [J ] . Proceedings of the AAAI Conference on Artificial Intelligence , 2023 , 37 ( 6 ): 7559 - 7567 .

ZHAO Y H , CHEN R , LAI R W , et al . Augmented negative sampling for collaborative filtering [C ] // Proceedings of the 17th ACM Conference on Recommender Systems . New York : ACM , 2023 : 256 - 266 .

SHAN D B , DU X H , WANG W J , et al . KPI-HGNN: Key provenance identification based on a heterogeneous graph neural network for big data access control [J ] . Information Sciences , 2024 , 659 : 120059 .

CHEN J Z , GAO J . VICS-GNN: A visual interactive system for community search via graph neural network [C ] // 2022 IEEE 38th International Conference on Data Engineering (ICDE) . Piscataway : IEEE , 2022 : 3150 - 3153 .

CHEN J Z , GAO J , CUI B . ICS-GNN~+: Lightweight interactive community search via graph neural network [J ] . The VLDB Journal , 2023 , 32 ( 2 ): 447 - 467 .

KIM J , LUO S Q , CONG G , et al . DMCS: Density modularity based community search [C ] // Proceedings of the 2022 International Conference on Management of Data . New York : ACM , 2022 : 889 - 903 .

FANG Y X , HUANG X , QIN L , et al . A survey of community search over big graphs [J ] . The VLDB Journal , 2020 , 29 ( 1 ): 353 - 392 .

张琦 , 程苗苗 , 李荣华 , 等 . 基于邻域k-核的社区模型与查询算法 [J ] . 软件学报 , 2024 , 35 ( 3 ): 1051 - 1073 .

ZHANG Q , CHENG M M , LI R H , et al . Community model and query algorithm based on neighborhood k-core [J ] . Journal of Software , 2024 , 35 ( 3 ): 1051 - 1073 . (in Chinese)

LIAO X K , LIU Q , HUANG X , et al . Truss-based community search over streaming directed graphs [J ] . Proceedings of the VLDB Endowment , 2024 , 17 ( 8 ): 1816 - 1829 .

LIU F Z , XUE S , WU J , et al . Deep learning for community detection: Progress, challenges and opportunities [EB/OL ] . ( 2020-05-17 )[ 2024-08-19 ] . https://arxiv.org/abs/2005.08225v2 https://arxiv.org/abs/2005.08225v2 .

JIANG Y L , RONG Y , CHENG H , et al . Query driven-graph neural networks for community search: From non-attributed, attributed, to interactive attributed [EB/OL ] . ( 2021-04-08 )[ 2024-08-19 ] . https://arxiv.org/abs/2104.03583v2 https://arxiv.org/abs/2104.03583v2 .

LI Y , CHEN X X , ZHAO Y H , et al . Self-training GNN-based community search in large attributed heterogeneous information networks [C ] // 2024 IEEE 40th International Conference on Data Engineering (ICDE) . Piscataway : IEEE , 2024 : 2765 - 2778 .

HASHEMI F , BEHROUZ A , REZAEI HAJIDEHI M . CS-TGN: Community search via temporal graph neural networks [C ] // Companion Proceedings of the ACM Web Conference 2023 . New York : ACM , 2023 : 1196 - 1203 .

LI Y J , GU C J , DULLIEN T , et al . Graph matching networks for learning the similarity of graph structured objects [EB/OL ] . ( 2019-04-29 )[ 2024-08-19 ] . https://arxiv.org/abs/1904.12787v2 https://arxiv.org/abs/1904.12787v2 .

BAI Y S , DING H , BIAN S , et al . SimGNN: A neural network approach to fast graph similarity computation [C ] // Proceedings of the Twelfth ACM International Conference on Web Search and Data Mining . New York : ACM , 2019 : 384 - 392 .

WU X X , XIONG Y , ZHANG Y , et al . CLARE: A semi-supervised community detection algorithm [C ] // Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining . New York : ACM , 2022 : 2059 - 2069 .

ZHANG H L . Temporal subgraph matching method for multi-connected temporal graph [J ] . Information Sciences , 2025 , 686 : 121320 .

NGUYEN D Q , TOAN NGUYEN T , JO J , et al . Explainable neural subgraph matching with learnable multi-hop attention [J ] . IEEE Access , 2024 , 12 : 130474 - 130492 .

SHAN C H , SHEN Y F , ZHANG Y , et al . Reinforcement learning enhanced explainer for graph neural networks [J ] . Advances in Neural Information Processing Systems , 2021 , 34 : 22523 - 22533 .

DUCHI J , TARLOW D , ELIDAN G , et al . Using combinatorial optimization within max-product belief propagation [M ] // Advances in Neural Information Processing Systems 19 . Cambridge, MA : The MIT Press , 2007 : 369 - 376 .

ZHANG Y , XIONG Y , YE Y , et al . SEAL: Learning heuristics for community detection with generative adversarial networks [C ] // Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining . New York : ACM , 2020 : 1103 - 1113 .

RIZVEE R A , HASSAN R , KHAN M M . A graph neural network-based QUBO-formulated Hamiltonian-inspired loss function for combinatorial optimization using reinforcement learning [EB/OL ] . ( 2023-11-27 )[ 2024-08-19 ] . https://arxiv.org/abs/2311.16277v1 https://arxiv.org/abs/2311.16277v1 .

WANG Q , LAI K H , TANG C L . Solving combinatorial optimization problems over graphs with BERT-Based Deep Reinforcement Learning [J ] . Information Sciences , 2023 , 619 : 930 - 946 .

CHEN J Z , XIA Y K , GAO J . CommunityAF: An example-based community search method via autoregressive flow [J ] . Proceedings of the VLDB Endowment , 2023 , 16 ( 10 ): 2565 - 2577 .

NIU Y D , LI Y C , KARRAS P , et al . Discovering personalized characteristic communities in attributed graphs [C ] // 2024 IEEE 40th International Conference on Data Engineering (ICDE) . Piscataway : IEEE , 2024 : 2834 - 2847 .

YU J K , WANG H C , WANG X Y , et al . Group-based fraud detection network on e-commerce platforms [C ] // Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining . New York : ACM , 2023 : 5463 - 5475 .

浏览量

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

融合大语言模型与跨域图结构的多模态对话情感识别方法

面向工业无线确定性传输的多路径路由与调度联合优化

大语言模型增强的抗灰洞攻击海域无人机路由算法

混合量子与图神经网络的多模态情感分析方法