Loading...
Organizing Committee
University of Utah
Abstract
Researchers working on graph algorithms use a broad range of different criteria for deciding what makes an algorithm efficient. While in theory the dominant benchmark is the asymptotic running time, in practice the story is more nuanced: an algorithm needs to be simple enough to be implementable, fast on graphs of bounded size, space efficient, cache-friendly, and easy to test. While many of these requirements motivate interesting algorithmic questions that are highly relevant in practice, they are often overlooked by the theory community. The goal of the workshop is to foster the exchange of ideas between researchers working on graph algorithms, which have high practical relevance. The workshop will include overview talks on the various perspectives, research talks, an open problem session, and structured time for collaboration.
Topics of this workshop include fundamental data science graph algorithms (e.g., clustering, partitioning, graph embedding), graph neural networks, and modeling data using networks (e.g. approximate nearest neighbor search). Additionally, the workshop program incorporates problems and approaches necessitated by scaling graph algorithms to large datasets (e.g. parallel, distributed, dynamic and external memory models, as well as algorithm engineering).
Topics of this workshop include fundamental data science graph algorithms (e.g., clustering, partitioning, graph embedding), graph neural networks, and modeling data using networks (e.g. approximate nearest neighbor search). Additionally, the workshop program incorporates problems and approaches necessitated by scaling graph algorithms to large datasets (e.g. parallel, distributed, dynamic and external memory models, as well as algorithm engineering).
Loading...
Loading participant list in background...
Workshop Schedule
Thursday, February 20, 2025
8:30 - 8:50 AM EST
Check In
11th Floor Collaborative Space
8:50 - 9:00 AM EST
Welcome
11th Floor Lecture Hall
Brendan Hassett, ICERM/Brown University
9:00 - 9:40 AM EST
Streaming (Hyper)Graph Partitioning Algorithms
11th Floor Lecture Hall
Speaker
Christian Schulz, Universität Heidelberg
Session Chair
Alex Pothen, Purdue University
Abstract
Processing large-scale (hyper)graphs with billions of entities and trillions of edges is crucial in fields such as bioinformatics, high-performance computing, as well as navigation and planning problems. Efficient (hyper)graph partitioning, which divides a (hyper)graph into sub-graphs while minimizing inter-block edges, is vital for optimizing parallel computing and enhancing data locality. Traditional in-memory partitioners like METIS and KaHIP deliver high-quality partitions but are often impractical for massive graphs due to their substantial memory requirements. Streaming partitioners address this challenge by reducing memory usage to O(n), where n is the number of nodes, by loading vertices sequentially and assigning them to blocks on-the-fly.
This talk first presents an overview of our recent work on scalable (hyper)graph algorithms, and then focuses on our recent advances in streaming (hyper)graph partitioning. We introduce higher quality streaming partitioning algorithms and present lightning-fast algorithms that reduce computational complexity from O(nk+m) to O(n+m). Additionally, we propose memory-efficient schemes that eliminate the need to store all block IDs for all vertices plainly in an array. Ultimately, we present streaming algorithms capable of partitioning trillion-edge graphs on edge devices.
9:50 - 10:20 AM EST
Coffee Break
11th Floor Collaborative Space
10:20 - 10:25 AM EST
Edge Colored Clustering in Hypergraphs Beyond Minimizing Dissatisfied Edges
Lightning Talks - 11th Floor Lecture Hall
Speaker
Thomas Stanley, Texas A&M University
Session Chair
Jakub Lacki, Google
10:26 - 10:31 AM EST
Faster Approximation Algorithms for Parameterized Graph Clustering and Edge Labeling
Lightning Talks - 11th Floor Lecture Hall
Speaker
Vedangi Vivek Bengali, Texas A&M University
Session Chair
Jakub Lacki, Google
10:32 - 10:37 AM EST
Theoretical Bounds on the Network Community Profile from Low-rank Semi-definite Programming
Lightning Talks - 11th Floor Lecture Hall
Speaker
Yufan Huang, Purdue University
Session Chair
Jakub Lacki, Google
10:38 - 10:43 AM EST
Modeling and Decomposition of Optimization Problems using Graph Theory
Lightning Talks - 11th Floor Lecture Hall
Speaker
David Cole, University of Wisconsin-Madison
Session Chair
Jakub Lacki, Google
10:44 - 10:49 AM EST
Covering maximal cliques in real-world graphs with dense subgraphs
Lightning Talks - 11th Floor Lecture Hall
Speaker
Shweta Jain, University of Utah
Session Chair
Jakub Lacki, Google
10:50 - 10:55 AM EST
NetworKit - An overview into implementing dynamic algorithms
Lightning Talks - 11th Floor Lecture Hall
Speaker
Fabian Brandt-Tumescheit, Humboldt-Universität zu Berlin
Session Chair
Jakub Lacki, Google
10:56 - 11:01 AM EST
ZombieHT: Reanimating Tombstones in a Graveyard
Lightning Talks - 11th Floor Lecture Hall
Speaker
Yuvaraj Chesetti, Northeastern University
Session Chair
Jakub Lacki, Google
11:02 - 11:07 AM EST
QJL: 1-Bit Quantized JL Transform for KV Cache Quantization with Zero Overhead
Lightning Talks - 11th Floor Lecture Hall
Speaker
Majid Daliri, New York University
Session Chair
Jakub Lacki, Google