# Mitigating Cascading Effects in Large Adversarial Graph Environments

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 9 of its 33 references that are in the map.
- First posted on arXiv 12 Apr 2024.

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

- [Dota 2 with Large Scale Deep Reinforcement Learning](https://mlsanity.com/paper/1912.06680/) (2019)
- [Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithm](https://mlsanity.com/paper/1712.01815/) (2017)
- [Deep Reinforcement Learning from Self-Play in Imperfect-Information Games](https://mlsanity.com/paper/1603.01121/) (2016)
- [Labeling Trick: A Theory of Using Graph Neural Networks for Multi-Node Representation Learning](https://mlsanity.com/paper/2010.16103/) (2020)
- [Counterfactual Data Augmentation using Locally Factored Dynamics](https://mlsanity.com/paper/2007.02863/) (2020)
- [Woulda, Coulda, Shoulda: Counterfactually-Guided Policy Search](https://mlsanity.com/paper/1811.06272/) (2018)
- [Graph Contrastive Learning for Anomaly Detection](https://mlsanity.com/paper/2108.07516/) (2021)
- [Distribution Knowledge Embedding for Graph Pooling](https://mlsanity.com/paper/2109.14333/) (2021)
- [Enhancing Factorization Machines with Generalized Metric Learning](https://mlsanity.com/paper/2006.11600/) (2020)

## Abstract (arXiv)

A significant amount of society's infrastructure can be modeled using graph structures, from electric and communication grids, to traffic networks, to social networks. Each of these domains are also susceptible to the cascading spread of negative impacts, whether this be overloaded devices in the power grid or the reach of a social media post containing misinformation. The potential harm of a cascade is compounded when considering a malicious attack by an adversary that is intended to maximize the cascading impact. However, by exploiting knowledge of the cascading dynamics, targets with the largest cascading impact can be preemptively prioritized for defense, and the damage an adversary can inflict can be mitigated. While game theory provides tools for finding an optimal preemptive defense strategy, existing methods struggle to scale to the context of large graph environments because of the combinatorial explosion of possible actions that occurs when the attacker and defender can each choose multiple targets in the graph simultaneously. The proposed method enables a data-driven deep learning approach that uses multi-node representation learning and counterfactual data augmentation to generalize to the full combinatorial action space by training on a variety of small restricted subsets of the action space. We demonstrate through experiments that the proposed method is capable of identifying defense strategies that are less exploitable than SOTA methods for large graphs, while still being able to produce strategies near the Nash equilibrium for small-scale scenarios for which it can be computed. Moreover, the proposed method demonstrates superior prediction accuracy on a validation set of unseen cascades compared to other deep learning approaches.