"Where Graph Topology Matters" Wins Best Paper at SDM 2015


Leman Akoglu, Assistant Professor of Computer Science at Stony Book University—along with two of her PhD students— received the Best Research Paper award from the Society for Industrial and Applied Mathematics (SIAM) at the 2015 SIAM International Conference on Data Mining.

Akoglu, and the two PhD candidates in Computer Science, Hau Chan and Shuchu Han, were selected on behalf of their paper, Where Graph Topology Matters: The Robust Subgraph Problem. Akoglu and Chan participated in the 2015 conference which was held April 30-May 2 in Vancouver, British Columbia.

According to the abstract, their paper focuses on robustness as a critical measure of resilience of large networked systems. “In this work, we pose the following question: given a large complex graph, how can we find its most robust local subgraph? Our formulation concerns not only with density but also with the placement of edges, i.e., the subgraph topology,” Akoglu said. Akoglu said she and her PhD students took a risk in formulating a new problem in the area of network robustness.

“[We] studied the properties of this new problem, related to existing problems, and proposed fast algorithms for the problem,” she said. “We are happy to receive this award, which illustrates that the data mining community received it well and showcased interest toward novel problems and solutions in the area of graph mining.” Akoglu said that she and her PhD students will continue to work on measuring, modeling, manipulating, and mining graph robustness.

“There are various open problems in this area. One future direction is to characterize the properties of good robustness measures, such as the one we used in our work, and analyze the existing measures with respect to these properties in a more systematic way,” she said. “Another direction of our research aims to modify the structure of a graph under the knowledge of probabilistic failures in the nodes and/or the edges, which we call the risk-aware manipulation, to obtain robust graphs in expectation.”