---
title: "Active Graph Reachability Reduction for Network Security and Software Engineering"
authors:
  - "Alice X. Zheng"
  - "John Dunagan"
  - "Ashish Kapoor"
doi: "10.5591/978-1-57735-516-8/IJCAI11-293"
url: "https://ijcai.org/proceedings/2011/293"
pdf: "https://ijcai.org/proceedings/2011/0293.pdf"
venue: "Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence"
year: 2011
pages: "1750-1755"
track: ""
keywords:
---

# Active Graph Reachability Reduction for Network Security and Software Engineering

Alice X. Zheng, John Dunagan, Ashish Kapoor

*Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence*, pages 1750-1755. DOI: [10.5591/978-1-57735-516-8/IJCAI11-293](https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-293)

## Abstract

Motivated by applications from computer network security and software engineering, we study the problem of reducing reachability on a graph with unknown edge costs. When the costs are known, reachability reduction can be solved using a linear relaxation of sparsest cut. Problems arise, however, when edge costs are unknown. In this case, blindly applying sparsest cut with incorrect edge costs can result in suboptimal or infeasible solutions. Instead, we propose to solve the problem via edge classification using feedback on individual edges. We show that this approach outperforms competing approaches in accuracy and efficiency on our target applications.