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

arXiv: https://arxiv.org/abs/2511.18958 · HTML: https://mlsanity.com/paper/2511.18958/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 14 of its 33 references that are in the map.
- First posted on arXiv 24 Nov 2025.

## Builds on (most cited first, 14 of 14)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Learning without Forgetting](https://mlsanity.com/paper/1606.09282/) (2016)
- [Deep Gaussian Embedding of Graphs: Unsupervised Inductive Learning via Ranking](https://mlsanity.com/paper/1707.03815/) (2017)
- [Gate-Variants of Gated Recurrent Unit (GRU) Neural Networks](https://mlsanity.com/paper/1701.05923/) (2017)
- [A Unified Lottery Ticket Hypothesis for Graph Neural Networks](https://mlsanity.com/paper/2102.06790/) (2021)
- [The physics of higher-order interactions in complex systems](https://mlsanity.com/paper/2110.06023/) (2021)
- [Self-Supervised Online Reward Shaping in Sparse-Reward Environments](https://mlsanity.com/paper/2103.04529/) (2021)
- [Graph Vulnerability and Robustness: A Survey](https://mlsanity.com/paper/2105.00419/) (2021)
- [Survey and Taxonomy of Lossless Graph Compression and Space-Efficient Graph Representations](https://mlsanity.com/paper/1806.01799/) (2018)
- [Learning to Shape Rewards using a Game of Two Partners](https://mlsanity.com/paper/2103.09159/) (2021)
- [Learning Transferable Domain Priors for Safe Exploration in Reinforcement Learning](https://mlsanity.com/paper/1909.04307/) (2019)
- [Graph Sparsification with Generative Adversarial Network](https://mlsanity.com/paper/2009.11736/) (2020)
- [Preserving Minority Structures in Graph Sampling](https://mlsanity.com/paper/2009.02498/) (2020)
- [Dismantling Complex Networks by a Neural Model Trained from Tiny Networks](https://mlsanity.com/paper/2208.07792/) (2022)

## Abstract (arXiv)

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.