CS-ROMF:Efficient Community Search Based on Graph Combinatorial Optimization

ZHANG An-ran; WANG Xing-fen; ZHAO Yu-han; LI Li-bo

doi:10.12263/DZXB.20240767

您当前的位置：

首页 >

文章列表页 >

CS-ROMF:Efficient Community Search Based on Graph Combinatorial Optimization

PAPERS | 更新时间：2025-12-08

- CS-ROMF:Efficient Community Search Based on Graph Combinatorial Optimization
- ACTA ELECTRONICA SINICA Vol. 53, Issue 2, Pages: 440-450(2025)
- 作者机构：
  
  1.北京信息科技大学，北京 102206
  2.香港浸会大学，香港 999077
- 作者简介：
- 基金信息：
- DOI：10.12263/DZXB.20240767
  CLC： TP183;TP301
- Received：19 August 2024，
  
  Revised：2024-12-16，
  
  Published：25 February 2025
- 稿件说明：
移动端阅览
张安冉, 王兴芬, 赵雨涵, 等. 基于图组合优化的高效社区搜索[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 .

Views

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Fusing Large Language Models with Cross-Domain Graphs for Multimodal Emotion Recognition in Dialogue

Joint Optimization of Multipath Routing and Scheduling for Industrial Wireless Deterministic Transmission

LLM-Enhanced Maritime UAV Routing Algorithm Against Gray-Hole Attacks

A Hybrid Quantum-Graph Neural Network for Multimodal Sentiment Analysis

Related Author

ZHAO Yu-han

HUANG Chen

MA Haobo

ZHANG Yan

YANG Chao

SONG Jianhua

CHEN Rongjun

WANG Hongchao

Related Institution

Hong Kong Baptist University

School of Computer Science and Information Engineering, Hubei University

Key Laboratory of Intelligent Sensing System and Security, Ministry of Education

Hubei Key Laboratory of Big Data Intelligent Analysis and Application

Hubei Province Project of Key Research Institute of Humanities and Social Sciences at Universities

⁰