GRASP: Accelerating Shortest Path Attacks via Graph Attention
This work addresses the problem of accelerating combinatorial optimization for adversaries in graph-based systems, though it is incremental as it builds on existing solvers with ML enhancements.
The authors tackled the APX-hard problem of attacking shortest paths in a graph by removing the minimum number of edges, proposing the GRASP algorithm which uses a graph attention network to accelerate existing solvers, achieving run times up to 10x faster while maintaining solution quality.
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.