# GRASP: Accelerating Shortest Path Attacks via Graph Attention

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 15 references that are in the map.
- First posted on arXiv 12 Oct 2023.

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

- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Deep Graph Infomax](https://mlsanity.com/paper/1809.10341/) (2018)
- [Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizon](https://mlsanity.com/paper/1811.06128/) (2018)
- [Learning Combinatorial Optimization Algorithms over Graphs](https://mlsanity.com/paper/1704.01665/) (2017)
- [Exact Combinatorial Optimization with Graph Convolutional Neural Networks](https://mlsanity.com/paper/1906.01629/) (2019)
- [Combinatorial Optimization with Graph Convolutional Networks and Guided Tree Search](https://mlsanity.com/paper/1810.10659/) (2018)
- [The CLRS Algorithmic Reasoning Benchmark](https://mlsanity.com/paper/2205.15659/) (2022)
- [Neural Algorithmic Reasoning](https://mlsanity.com/paper/2105.02761/) (2021)
- [Stacking Models for Nearly Optimal Link Prediction in Complex Networks](https://mlsanity.com/paper/1909.07578/) (2019)
- [Dual Algorithmic Reasoning](https://mlsanity.com/paper/2302.04496/) (2023)
- [Attacking Shortest Paths by Cutting Edges](https://mlsanity.com/paper/2211.11141/) (2022)

## Built on by (most cited first, 1 of 1)

- [SPEAR: Security Posture Evaluation using AI Planner-Reasoning on Attack-Connectivity Hypergraphs](https://mlsanity.com/paper/2506.01227/) (2025)

## Abstract (arXiv)

Recent advances in machine learning (ML) have shown promise in aiding and accelerating classical combinatorial optimization algorithms. ML-based speed ups that aim to learn in an end to end manner (i.e., directly output the solution) tend to trade off run time with solution quality. Therefore, solutions that are able to accelerate existing solvers while maintaining their performance guarantees, are of great interest. We consider an APX-hard problem, where an adversary aims to attack shortest paths in a graph by removing the minimum number of edges. We propose the GRASP algorithm: Graph Attention Accelerated Shortest Path Attack, an ML aided optimization algorithm that achieves run times up to 10x faster, while maintaining the quality of solution generated. GRASP uses a graph attention network to identify a smaller subgraph containing the combinatorial solution, thus effectively reducing the input problem size. Additionally, we demonstrate how careful representation of the input graph, including node features that correlate well with the optimization task, can highlight important structure in the optimization solution.