NP-hard problems are common in fields like scheduling, logistics, and circuit design, but are notoriously hard to solve efficiently. This project explores how graph neural networks (GNNs) can learn to solve instances of NP-hard problems and uncover new algorithmic insights. We will train GNNs to run for many steps and analyze how their internal representations evolve over time. By identifying consistent patterns in their behavior, we aim to extract simple, human-readable rules that explain their learned strategies. We hope to use these rules to improve classical heuristics, making them more effective and interpretable. The broader goal is to better understand how deep networks solve hard problems and use that understanding to advance both learning-based and traditional algorithm design.

I am participating in this SuperUROP because my favorite classes at MIT have been in machine learning and algorithms, and this project combines both in a meaningful way. I am excited to explore how deep networks can learn to solve hard problems and potentially uncover new algorithmic insights. My past work with applied AI has prepared me for this, and I look forward to learning more about the research process and hopefully publishing a paper!