Prof. Danai Koutra earns ICDM 10-Year Highest Impact Paper Award for bipartite graph alignment

Associate professor and Associate Director of the Michigan Institute of Data Science Danai Koutra and her co-authors have been recognized with the ICDM2022 10-Year Highest Impact Paper Award. “BIG-ALIGN: Fast Bipartite Graph Alignment” was originally published in 2013 while Koutra was a doctoral candidate at Carnegie Mellon University. The award recognizes the most influential paper among those published at ICDM 2013.

The paper focuses on aligning bipartite graphs, which were previously underrepresented in existing work on graph matching. The authors introduced a new optimization formulation with an effective and fast algorithm to solve it, as well as a practical method that was ten times more accurate in regard to alignment accuracy and running time than baseline approaches. 

Koutra and her co-authors worked in part to demonstrate why bipartite graphs deserve to be studied separately from unipartite graphs, as the former can model bipartite networks and achieve better quality alignments than treating the graph as  unipartite and applying an off-the-shelf algorithm. The paper introduced a powerful primitive with new constraints for the graph matching problem and proposed more efficient algorithms in BIG-ALIGN and UNI-ALIGN.

At the time, during IP filing, this work was recognized as having “extremely high potential business value for IBM”, and led to 7 patents. The paper continues to be cited in new work on network analysis and graph-based research, as well as a broad set of applications spanning from user identity linkage to intrusion detection, to knowledge fusion and semantic matching, to Internet-of-Things applications and efficient hardware systems . The paper was co-authored by Hanghang Tong, now an associate professor at the University of Illinois at Urbana-Champaign, and David Lubensky who was a Distinguished Researcher at IBM. 

In 2020, Koutra was named a Morris Wellman Faculty Development Professor for her outstanding contributions to teaching and research. She has received an NSF CAREER Award and a Rising Star Award from ACM SIGKDD. She has also earned a number of research awards throughout her career, including the 2016 ACM SIGKDD Dissertation Award for her thesis on “Exploring and Making Sense of Large Graphs,” an honorable mention for the SCS Doctoral Dissertation Award (CMU), an ARO Young Investigator Award (2018), an Adobe Data Science Research Faculty Award (2018), an Amazon Research Faculty Award (2019), a WSDM 2019 Outstanding PC Award (2019), and several best paper awards and nominations.