基于深度强化学习的图约简方法

陈根鑫; 亓晋; 刘娅利; 高钰; 董振江; 孙雁飞

doi:10.11959/j.issn.2096-3750.2026.00406

您当前的位置：

首页 >

文章列表页 >

基于深度强化学习的图约简方法

理论与技术 | 更新时间：2026-04-16

- 基于深度强化学习的图约简方法
- Graph reducing method based on deep reinforcement learning
- 物联网学报 2026年10卷第1期页码：150-160
- 作者机构：
  
  1.南京邮电大学自动化学院，江苏南京 210023
  2.南京邮电大学物联网学院，江苏南京 210003
  3.南京市大数据安全技术有限公司，江苏南京 210001
  4.南京邮电大学计算机学院，江苏南京 210023
- 作者简介：
  
  [ "陈根鑫（1997‒ ），男，南京邮电大学自动化学院博士生，主要研究方向为图算法、深度强化学习和云计算。" ]
  [ "亓晋（1983‒ ），男，博士，南京邮电大学物联网学院教授、博士生导师，主要研究方向为工业互联网、大数据智能处理和区块链。" ]
  [ "刘娅利（1998‒ ），女，南京市大数据安全技术有限公司工程师，主要研究方向为网络空间安全、人工智能和漏洞检测。" ]
  [ "高钰（1996‒ ），男，南京邮电大学自动化学院博士生，主要研究方向为工业互联网、数据挖掘和知识推理。" ]
  [ "董振江（1970‒ ），男，南京邮电大学计算机学院教授、博士生导师，主要研究方向为人工智能大模型、区块链、车联网、计算机视觉和信息安全。" ]
  [ "孙雁飞（1976‒ ），男，南京邮电大学物联网学院研究员、博士生导师，主要研究方向为工业互联网、工业智能、大数据管理与分析和高性能计算。" ]
- 基金信息：
  
  国家自然科学基金面上项目(62172235);江苏省重点研发计划项目(BE2023025);江苏省高等学校基础科学（自然科学）研究项目(22KJB520028;22KJB520026)
- DOI：10.11959/j.issn.2096-3750.2026.00406
  中图分类号： TP183;O157.5
- 收稿：2024-06-12，
  
  修回：2025-07-25，
  
  纸质出版：2026-03-30
- 稿件说明：
移动端阅览
陈根鑫,亓晋,刘娅利等.基于深度强化学习的图约简方法[J].物联网学报,2026,10(01):150-160.

Chen Genxin,Qi Jin,Liu Yali,et al.Graph reducing method based on deep reinforcement learning[J].Chinese Journal on Internet of Things,2026,10(01):150-160.
陈根鑫,亓晋,刘娅利等.基于深度强化学习的图约简方法[J].物联网学报,2026,10(01):150-160. DOI： 10.11959/j.issn.2096-3750.2026.00406.

Chen Genxin,Qi Jin,Liu Yali,et al.Graph reducing method based on deep reinforcement learning[J].Chinese Journal on Internet of Things,2026,10(01):150-160. DOI： 10.11959/j.issn.2096-3750.2026.00406.

摘要

通用人工智能的发展浪潮驱动着海量数据的生成与处理，大规模、异构的图数据网络成为数字世界的重要基础。然而，持续增长的数据规模不仅增加了图数据处理的难度，也催生了降低图规模并最大化图信息量的需求。现有方法难以协同控制图规模并优化图信息量，从而限制了图数据分析处理的效果。为响应图数据规模与信息量的均衡调控需求，提出以规模调控为约束、信息量最大化为目标的图约简问题。具体而言，设计图融合算法与基于深度强化学习的图约简算法对问题进行求解，包括节点融合、复合映射等图约简操作与相似度量方法。实验结果验证了约简算法的均衡调控能力，与4种算法在特征相似度、图相似度、边信息损失3个评估指标上的对比显示，该图约简方法可分别取得最低为20.7%、19.9%及26.3%的性能提升。

Abstract

The development wave of general artificial intelligence drives the generation and processing of massive data

and large-scale and heterogeneous graph data networks constitute an important foundation of the digital world. However

the continuously growing scale of data not only increases the difficulty of graph data processing

but also creates the need to reduce graph size and maximize the amount of graph information. Existing methods make it difficult to synergistically control the graph size and optimize the amount of graph information

which limits the effectiveness of graph data analysis and processing. In response to the need for balanced control of graph data scale and information content

the graph reducing problem with scale regulation as the constraint and information maximization as the goal was proposed. Specifically

a graph fusion algorithm and a deep reinforcement learning-based graph reducing algorithm were designed to solve the problem

including graph reducing operations such as node fusion

composite mapping

and methods used for similarity metrics. Experiments verified the balanced regulation ability of the reducing algorithm

and comparisons with four algorithms across three evaluation metrics—feature similarity

graph similarity

and edge information loss—showed that the proposed graph reduction method could achieve performance improvements of at least 20.7%

19.9%

and 26.3%

respectively.

关键词

Keywords

references

Tang C , Zheng X , Zhang W , et al . Unsupervised feature selection via multiple graph fusion and feature weight learning [J ] . Science China Information Sciences , 2023 , 66 ( 5 ): 152101 .

Nie W Z , Bao Y R , Zhao Y , et al . Long dialogue emotion detection based on commonsense knowledge graph guidance [J ] . IEEE Transactions on Multimedia , 2024 , 26 : 514 - 528 .

Wang D J , Zhang X , Yin Y Y , et al . Multi-view enhanced graph attention network for session-based music recommendation [J ] . ACM Transactions on Information Systems , 2023 , 42 ( 1 ): 1 - 30 .

Marchand-Maillet S , Chávez E . HubHSP graph: capturing local geometrical and statistical data properties via spanning graphs [J ] . Information Systems , 2024 , 121 : 102341 .

Liu R , Xing P W , Deng Z C , et al . Federated graph neural networks: overview, techniques, and challenges [J ] . IEEE Transactions on Neural Networks and Learning Systems , 2025 , 36 ( 3 ): 4279 - 4295 .

Yang M J , Wang H Z , Wei Z W , et al . Efficient algorithms for personalized PageRank computation: a survey [J ] . IEEE Transactions on Knowledge and Data Engineering , 2024 , 36 ( 9 ): 4582 - 4602 .

陈子俊 , 马德龙 , 王一舒 , 等 . GPPR: 跨域分布式个性化PageRank算法 [J ] . 软件学报 , 2024 , 35 ( 3 ): 1090 - 1106 .

Chen Z J , Ma D L , Wang Y S , et al . GPPR: cross-geo-distributed personalized PageRank algorithm [J ] . Journal of Software , 2024 , 35 ( 3 ): 1090 - 1106 .

Cong S , Zhou Y . A review of convolutional neural network architectures and their optimizations [J ] . Artificial Intelligence Review , 2023 , 56 ( 3 ): 1905 - 1969 .

Feng J , Yang L T , Ren B C , et al . Tensor recurrent neural network with differential privacy [J ] . IEEE Transactions on Computers , 2024 , 73 ( 3 ): 683 - 693 .

Lin W Y , Zhang Y F , Dai W R , et al . Scene graph lossless compression with adaptive prediction for objects and relations [J ] . ACM Transactions on Multimedia Computing, Communications, and Applications , 2024 , 20 ( 7 ): 1 - 23 .

Gao M S , Yu J , Yang Z F , et al . A physics-guided graph convolution neural network for optimal power flow [J ] . IEEE Transactions on Power Systems , 2024 , 39 ( 1 ): 380 - 390 .

王继禾 , 吴颖 , 迟恒喆 , 等 . 基于Transformer结构增强的神经网络架构搜索性能预测器 [J ] . 计算机学报 , 2024 , 47 ( 7 ): 1469 - 1484 .

Wang J H , Wu Y , Chi H Z , et al . An architecture-enhanced performance predictor for transformer-based NAS [J ] . Chinese Journal of Computers , 2024 , 47 ( 7 ): 1469 - 1484 .

Verma T , Le Dinh L , Tan N , et al . RLPeri: accelerating visual perimetry test with reinforcement learning and convolutional feature extraction [J ] . Proceedings of the AAAI Conference on Artificial Intelligence , 2024 , 38 ( 20 ): 22401 - 22409 .

Chen Y P , Dai X Y , Liu M C , et al . Dynamic convolution: attention over convolution kernels [C ] // Proceedings of the 2020 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR) . Piscataway : IEEE Press , 2020 : 11027 - 11036 .

Li H J , Feng Y H , Xia C Y , et al . Overlapping graph clustering in attributed networks via generalized cluster potential game [J ] . ACM Transactions on Knowledge Discovery from Data , 2023 , 18 ( 1 ): 1 - 26 .

Yang B , Zhang X T , Wu J H , et al . Fast multiview anchor-graph clustering [J ] . IEEE Transactions on Neural Networks and Learning Systems , 2025 , 36 ( 3 ): 4947 - 4958 .

Zhao H , Yang X , Deng C . Parameter-agnostic deep graph clustering [J ] . ACM Transactions on Knowledge Discovery from Data , 2024 , 18 ( 3 ): 1 - 20 .

吕佳 , 邱小龙 . 基于K-means聚类和特征空间增强的噪声标签深度学习算法 [J ] . 智能系统学报 , 2024 , 19 ( 2 ): 267 - 277 .

Lyu J , Qiu X L . A noisy label deep learning algorithm based on K-means clustering and feature space augmentation [J ] . CAAI Transactions on Intelligent Systems , 2024 , 19 ( 2 ): 267 - 277 .

Li G H , Wang Z K , Zhang Q F , et al . Offline and online objective reduction via Gaussian mixture model clustering [J ] . IEEE Transactions on Evolutionary Computation , 2023 , 27 ( 2 ): 341 - 354 .

金秋 , 林馥 , 裴斐 . 基于层次聚类的敏感信息安全过滤模型研究 [J ] . 计算机仿真 , 2023 , 40 ( 10 ): 296 - 299, 320 .

Jin Q , Lin F , Pei F . Research on security filtering model of sensitive information based on hierarchical clustering [J ] . Computer Simulation , 2023 , 40 ( 10 ): 296 - 299, 320 .

Karypis G , Kumar V . A fast and high quality multilevel scheme for partitioning irregular graphs [J ] . SIAM Journal on Scientific Computing , 1998 , 20 ( 1 ): 359 - 392 .

Xie C , Yan L , Li W J , et al . Distributed power-law graph computing: theoretical and empirical analysis [C ] // Proceedings of the 28th International Conference on Neural Information Processing Systems . Cambridge, MA : MIT Press , 2014 : 1673 - 1681 .

Newman M E J . Fast algorithm for detecting community structure in networks [J ] . Physical Review E , 2004 , 69 ( 6 ): 066133 .

Blondel V D , Guillaume J L , Lambiotte R , et al . Fast unfolding of communities in large networks [J ] . Journal of Statistical Mechanics: Theory and Experiment , 2008 , 2008 ( 10 ): P10008 .

Fortunato S . Community detection in graphs [J ] . Physics Reports , 2010 , 486 ( 3-5 ): 75 - 174 .

王扬 , 陈智斌 , 杨笑笑 , 等 . 深度强化学习结合图注意力模型求解TSP问题 [J ] . 南京大学学报(自然科学) , 2022 , 58 ( 3 ): 420 - 429 .

Wang Y , Chen Z B , Yang X X , et al . Deep reinforcement learning combined with graph attention model to solve TSP [J ] . Journal of Nanjing University (Natural Science) , 2022 , 58 ( 3 ): 420 - 429 .

He Q , Wang Y , Wang X W , et al . Routing optimization with deep reinforcement learning in knowledge defined networking [J ] . IEEE Transactions on Mobile Computing , 2024 , 23 ( 2 ): 1444 - 1455 .

Zhang J D , He Z X , Chan W H , et al . DeepMAG: deep reinforcement learning with multi-agent graphs for flexible job shop scheduling [J ] . Knowledge-Based Systems , 2023 , 259 : 110083 .

Wang H , Li S Y , Pan R , et al . Incorporating graph attention mechanism into knowledge graph reasoning based on deep reinforcement learning [C ] // Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP) . Stroudsburg, PA, USA : ACL , 2019 : 2623 - 2631 .

Chen G X , Qi J , Gao Y , et al . DGTRL: deep graph transfer reinforcement learning method based on fusion of knowledge and data [J ] . Information Sciences , 2024 , 658 : 120019 .

Zhou F , De la Torre F . Factorized graph matching [J ] . IEEE Transactions on Pattern Analysis and Machine Intelligence , 2016 , 38 ( 9 ): 1774 - 1789 .

浏览量

下载量

CSCD

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

提交

工具集

关联资源

意图驱动的物联网双时间尺度资源分配方法

基于深度扩散确定性策略梯度的Wi-Fi网络性能优化

车联网中基于迁移强化学习的跨域充电站推荐算法