Active Graph Reachability Reduction for Network Security and Software Engineering
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.
Cite
Text
Zheng et al. "Active Graph Reachability Reduction for Network Security and Software Engineering." International Joint Conference on Artificial Intelligence, 2011. doi:10.5591/978-1-57735-516-8/IJCAI11-293Markdown
[Zheng et al. "Active Graph Reachability Reduction for Network Security and Software Engineering." International Joint Conference on Artificial Intelligence, 2011.](https://mlanthology.org/ijcai/2011/zheng2011ijcai-active/) doi:10.5591/978-1-57735-516-8/IJCAI11-293BibTeX
@inproceedings{zheng2011ijcai-active,
title = {{Active Graph Reachability Reduction for Network Security and Software Engineering}},
author = {Zheng, Alice X. and Dunagan, John and Kapoor, Ashish},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {2011},
pages = {1750-1756},
doi = {10.5591/978-1-57735-516-8/IJCAI11-293},
url = {https://mlanthology.org/ijcai/2011/zheng2011ijcai-active/}
}