Shortest paths in complex networks play key roles in many applications.
Examples include routing packets in a computer network, routing traffic on a
transportation network, and inferring semantic distances between concepts on
the World Wide Web. An adversary with the capability to perturb the graph might
make the shortest path between two nodes route traffic through advantageous
portions of the graph (e.g., a toll road he owns). In this paper, we introduce
the Force Path Cut problem, in which there is a specific route the adversary
wants to promote by removing a minimum number of edges in the graph. We show
that Force Path Cut is NP-complete, but also that it can be recast as an
instance of the Weighted Set Cover problem, enabling the use of approximation
algorithms. The size of the universe for the set cover problem is potentially
factorial in the number of nodes. To overcome this hurdle, we propose the
PATHATTACK algorithm, which via constraint generation considers only a small
subset of paths -- at most 5% of the number of edges in 99% of our experiments.
Across a diverse set of synthetic and real networks, the linear programming
formulation of Weighted Set Cover yields the optimal solution in over 98% of
cases. We also demonstrate a time/cost tradeoff using two approximation
algorithms and greedy baseline methods. This work provides a foundation for
addressing similar problems and expands the area of adversarial graph mining
beyond recent work on node classification and embedding.
