Philosopher Friedrich Nietzsche once said, “invisible threads are the strongest ties.” This notion of “invisible threads” can symbolize the unseen connections among various entities, like homes on a delivery route, transactions within a financial ecosystem, or interactions on social networks.
Computer scientist Julian Shun focuses on these intricate, often hidden connections through graph theory, where objects are depicted as vertices (points) and their relationships as edges (lines).
Recently granted tenure as an associate professor in the Department of Electrical Engineering and Computer Science, Shun devises sophisticated graph algorithms to solve real-world challenges. His work can help pinpoint the most efficient delivery routes for drivers or flag fraudulent activities across financial networks.
As data continues to proliferate, with networks potentially encompassing billions or even trillions of nodes and connections, the quest for efficient solutions becomes increasingly vital. To address this, Shun develops high-performance algorithms that utilize parallel computing, enabling rapid analysis of vast graphs. Given the complexity of parallel programming, he also creates user-friendly frameworks that help others write their own efficient graph algorithms.
“In today’s digital landscape, whether you’re searching for information on a search engine or identifying suspicious financial transactions at a bank, speed is essential. Parallel algorithms can enhance performance by utilizing additional computing resources,” Shun explains. He is also a principal investigator at the Computer Science and Artificial Intelligence Laboratory (CSAIL).
These algorithms have become invaluable in online recommendation systems. For instance, when you search for a product on an e-commerce site, the related items you see are typically generated by graph algorithms that quickly navigate extensive networks of users and products.
The Journey to Graph Theory
Shun’s early exposure to computers was limited to a high school course on website building. Initially, he planned to pursue a major in math or natural sciences upon his acceptance to the University of California, Berkeley. However, a friend’s suggestion to take an introductory computer science course changed the trajectory of his career.
He recalls, “I fell in love with programming and designing algorithms. It was a turning point—I switched to computer science and never reconsidered my decision.” The self-paced structure of the course allowed him to dive deep into the material, fostering a fascination with the logical problem-solving inherent in algorithm development.
After completing his undergraduate studies, Shun gained industry experience before realizing his passion lay in academia, where he could explore questions that intrigued him.
Diving Deep into Graphs
Shun pursued his graduate studies at Carnegie Mellon University, concentrating on applied algorithms and parallel computing. He sought to merge the theoretical with the practical—parallel algorithms perfectly bridged this gap.
“In parallel computing, practical applications are paramount. If an algorithm isn’t fast in the real world, its usefulness is compromised,” he states.
His exposure to graph datasets during his time at Carnegie Mellon intensified his interest; he was captivated by the broad applications and the unique challenges of crafting efficient algorithms to manage them.
After completing his postdoctoral fellowship at Berkeley, Shun eagerly accepted a faculty role at MIT, having already collaborated with several faculty members on parallel computing research.
One of his initial projects involved teaming up with Saman Amarasinghe, a professor at the Department of Electrical Engineering and Computer Science and fellow CSAIL member. Together, they developed a user-friendly programming framework for graph processing known as GraphIt, which outperforming its competitors by executing tasks roughly five times faster.
“That collaboration was incredibly productive. The outcome wouldn’t have been as powerful if I had undertaken it alone,” he notes.
Continuing to expand his research, Shun now explores clustering algorithms, focusing on efficiently grouping related data points—a crucial step for applications like anomaly detection and community detection.
Addressing Dynamic Challenges
Recently, Shun and his team have shifted their focus towards dynamic problems, addressing how graph datasets evolve over time. With multi-billion-point datasets, running entire algorithms for minor adjustments can be computationally taxing. By designing parallel algorithms that manage multiple updates simultaneously, they enhance efficiency while ensuring accuracy.
Yet, this area also presents significant challenges. Dynamic datasets are scarce, often requiring the team to create synthetic data, which may not realistically represent real-world scenarios and could affect their algorithms’ performance.
Ultimately, Shun aims to develop dynamic graph algorithms that efficiently balance practical performance with theoretical guarantees, ensuring their applicability across various contexts.
Looking ahead, he anticipates an increased emphasis on dynamic parallel algorithms. As datasets grow larger and more intricate, researchers will need to create even more efficient algorithms to keep pace with advancements in computing technology and the complexities of modern data.
“That’s the essence of research for me—I thrive on tackling unsolved problems and making meaningful contributions to society,” he concludes.
Photo credit & article inspired by: Massachusetts Institute of Technology
