Learning to Compress Graphs via Dual Agents for Consistent Topological Robustness Evaluation
This work addresses the scalability problem for researchers and practitioners dealing with large graph-structured data in adversarial robustness evaluation, though it is incremental as it builds on existing compression and reinforcement learning methods.
The paper tackles the computational expense of evaluating graph robustness under adversarial attacks by proposing Cutter, a dual-agent reinforcement learning framework that compresses graphs into compact representations while preserving topological structure and robustness profiles, achieving significant improvements in evaluation efficiency with consistent robustness degradation trends.
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.