Abstract
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.
Abstract (translated)
大量社会的设施可以使用图结构进行建模，从电力和通信网络，到交通网络，到社会网络。每个领域也容易受到级联负面影响的传播，无论是电网中的过载设备，还是包含不准确信息的社交媒体帖子，其影响范围。当考虑恶意攻击方旨在最大化级联影响时，级联潜在危害的叠加效果会变得更加严重。然而，通过利用级联动态的知识，可以预先优先考虑具有最大级联影响的目标进行防御，并减轻攻击者可能造成的损害。虽然游戏理论提供了找到最优先发防御策略的工具，但现有方法在大型图环境中因为攻击者和防御者可以同时选择 graph 上多个目标而出现组合爆炸问题而难以扩展。所提出的方法采用数据驱动的深度学习方法，利用多节点表示学习和反事实数据增强来泛化到完整的组合动作空间，通过在各种小限制子集的action space上训练，实现对动作空间的泛化。我们通过实验证明，与现有的对于大型图的SOTA（最高水平）方法相比，所提出的方法能够识别出更难以被利用的防御策略，同时，对于可以计算的小规模场景，该方法仍然可以生成接近纳什均衡的战略。此外，与其它深度学习方法相比，所提出的方法在验证集中对未见过的级联的预测准确性具有优势。
URL
https://arxiv.org/abs/2404.14418
