arXiv:2511.18958cs.LGcs.AI2025-11AAAI

用双智能体强化学习压缩图结构,高效评估对抗攻击下的鲁棒性。

Learning to Compress Graphs via Dual Agents for Consistent Topological Robustness Evaluation

  • 双代理协同识别关键与冗余节点,指导图压缩。
  • 压缩后图在多种攻击下鲁棒性下降趋势与原图高度一致。
  • 适合大规模图数据的鲁棒性评估,提升效率且不损失精度。

随着图结构数据规模不断增大,评估其在对抗攻击下的鲁棒性变得计算成本高昂且难以扩展。为此,我们提出将图压缩为保留拓扑结构和鲁棒性特征的紧凑表示,以实现高效可靠的评估。本文提出Cutter框架,包含关键节点检测代理(VDA)与冗余节点检测代理(RDA),二者协同识别用于引导压缩的结构关键与冗余节点。Cutter引入三种策略提升学习效率与压缩质量:轨迹级奖励塑形,将稀疏回报转化为密集、等价的学习信号;基于原型的塑形,利用高/低回报轨迹的行为模式引导决策;跨代理模仿,实现更安全、可迁移的探索。在多个真实世界图数据集上的实验表明,Cutter生成的压缩图保留了关键静态拓扑属性,并在多种攻击场景下表现出与原始图高度一致的鲁棒性退化趋势,显著提升了评估效率而不牺牲评估保真度。

原文摘要 · Abstract (English)

As graph-structured data grow increasingly large, evaluating their robustness under adversarial attacks becomes computationally expensive and difficult to scale. To address this challenge, we propose to compress graphs into compact representations that preserve both topological structure and robustness profile, enabling efficient and reliable evaluation. We propose Cutter, a dual-agent reinforcement learning framework composed of a Vital Detection Agent (VDA) and a Redundancy Detection Agent (RDA), which collaboratively identify structurally vital and redundant nodes for guided compression. Cutter incorporates three key strategies to enhance learning efficiency and compression quality: trajectory-level reward shaping to transform sparse trajectory returns into dense, policy-equivalent learning signals; prototype-based shaping to guide decisions using behavioral patterns from both high- and low-return trajectories; and cross-agent imitation to enable safer and more transferable exploration. Experiments on multiple real-world graphs demonstrate that Cutter generates compressed graphs that retain essential static topological properties and exhibit robustness degradation trends highly consistent with the original graphs under various attack scenarios, thereby significantly improving evaluation efficiency without compromising assessment fidelity.

图压缩强化学习鲁棒性评估

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