Dagstuhl Seminar 18241
High-Performance Graph Algorithms
( Jun 10 – Jun 15, 2018 )
- Henning Meyerhenke (HU Berlin, DE)
- Richard Peng (Georgia Institute of Technology - Atlanta, US)
- Ali Pinar (Sandia Nat. Labs - Livermore, US)
- Ilya Safro (Clemson University, US)
- Andreas Dolzmann (for scientific matters)
- Annette Beyer (for administrative matters)
Graphs (or networks) are a powerful abstraction of various phenomena that can be expressed as relations between entities. As such graph algorithms have been the subject of many research efforts. Recently, however, we see a qualitative change how graph algorithms are used in practice. This change is due to (i) the complex structures and the sizes of graphs in emerging applications and (ii) the computer systems on which graph problems are solved. Application areas driving this change are diverse. To name a few, consider microblogging services in social media, bioinformatics, routing in traffic networks, technology diffusion and decentralized trade in economics, and combinatorial scientific computing. These application areas have in common that the associated problem instances show massive scale and irregular or skewed distributions of structural and semantic properties of entities and their interactions.
We need novel algorithms to cope with the ever growing problem sizes. A major challenge in designing and implementing graph algorithms is the large gap between theoretical computational models and observed performances. Computer architectures are becoming increasingly parallel and heterogeneous. Yet, many design and analysis techniques focus on the sequential case, and many striking theoretical results do not transfer to efficient computational tools. To fully exploit emerging architectures, it is important to develop parallel algorithms and tools with the specific hardware in mind.
This Dagstuhl Seminar aims at narrowing the gap between theoretical and practical graph algorithms. To this end, we would like to bring together (i) theoretical computer scientists whose works have strong practical context, (ii) researchers from graph-focused high performance computing, and (iii) algorithm engineers whose work falls in between the two previous areas. The invited practitioners in graph algorithms will also represent the domain expertise in applications and high-performance tools that address real-life graph problems. Two areas of high-performance graph algorithms that we plan to focus on are algorithmic network analysis and combinatorial scientific computing.
We would like to discuss and achieve some of the synergies that become possible from bringing the aforementioned fields closer together. One open research question covered will be how to transfer provably efficient theoretical methods into code that runs efficiently on modern parallel hardware. By bringing together experts from different fields, we hope to develop the next-generation tools of the trade for large graphs. These tools ideally are significantly faster and more feature-rich than the current state of the art, more closely connected with recent theoretical breakthroughs, and have more simplified development processes. This, in turn, will allow domain scientists to process larger data sets more effectively, and allow them to tackle problems previously out of reach.
Some topics for which we expect joint interest include (but are not limited to): solvers for graph-induced (non)linear systems of equations, I/O and communication efficiency of graph algorithms, fast analysis of massive complex networks, worst-case complexity vs empirical running time of graph algorithms, combinatorial scientific computing, and accelerating numerical methods for graphs.
Many presentations in this Dagstuhl seminar emphasized recent trends regarding typical inputs and their effect on graph algorithm development. From a high-level perspective, one can divide the presentations into two categories: either more focused on algorithm theory or more focused on practical algorithmic results. Many talks considered both theoretical and practical aspects. Furthermore, attention was given to intermix talks with theoretical and practically motivated starting points in order to encourage discussions among attendees. We were happy to see such discussions, as well as synergy of both aspects, carrying over to working groups on open problems.
Theory-focused talks were given by Sachdeva, Nanongkai, Jacob, Mouatadid, Kyng, Tsourakakis, and Litvak. They considered numerous topics such as Laplacian solvers and related optimization techniques, dynamic graph algorithms, external-memory graph algorithms, graph decompositions, and generative models.
The talks with emphasis on practical performance can be further subdivided into three subclasses: (i) graph mining, network analysis and optimization, (ii) parallel, distributed and streaming graph algorithms and (iii) graph generation. The talks given by Koutra, Ahmed, Klymko, Angriman, Gleich and Schulz fall into the first subclass, with a wide variation of algorithmic problems under consideration. Likewise, it was interesting to see the variety in computing platforms and tools (for example shared memory, message passing, distributed systems, streaming from databases, GraphBLAS) used in the eight talks of subclass two, presented by Besta, Shun, Predari, Ramachandran, Pothen, Bader, Finocchi and Davis. Finally, the talks by Phillips, Sanders and Penschuck as well as Crescenzi dealt with generating very large graphs with properties also found in real-world graphs - which is important, among others, for convincing scaling studies in algorithm engineering.
- Nesreen Ahmed (Intel Labs - Santa Clara, US) [dblp]
- Eugenio Angriman (Universität Köln, DE) [dblp]
- David A. Bader (Georgia Institute of Technology - Atlanta, US) [dblp]
- Maciej Besta (ETH Zürich, CH) [dblp]
- Rob Bisseling (Utrecht University, NL) [dblp]
- Timothy Chu (Carnegie Mellon University - Pittsburgh, US) [dblp]
- Pierluigi Crescenzi (University of Florence, IT) [dblp]
- Timothy Alden Davis (Texas A&M University - College Station, US) [dblp]
- Irene Finocchi (Sapienza University of Rome, IT) [dblp]
- John Gilbert (University of California - Santa Barbara, US) [dblp]
- David F. Gleich (Purdue University - West Lafayette, US) [dblp]
- Riko Jacob (IT University of Copenhagen, DK) [dblp]
- George Karypis (University of Minnesota - Minneapolis, US) [dblp]
- Michel A. Kinsy (Boston University, US) [dblp]
- Marsha Kleinbauer (TU Kaiserslautern, DE)
- Christine Klymko (LLNL - Livermore, US) [dblp]
- Yiannis Koutis (NJIT - Newark, US) [dblp]
- Danai Koutra (University of Michigan - Ann Arbor, US) [dblp]
- Rasmus Kyng (Harvard University - Cambridge, US) [dblp]
- Nelly Litvak (University of Twente, NL) [dblp]
- Fredrik Manne (University of Bergen, NO) [dblp]
- Henning Meyerhenke (HU Berlin, DE) [dblp]
- Marco Minutoli (Pacific Northwest National Lab. - Richland, US) [dblp]
- Lalla Mouatadid (University of Toronto, CA) [dblp]
- Danupon Nanongkai (KTH Royal Institute of Technology - Stockholm, SE) [dblp]
- Lorenzo Orecchia (Boston University, US) [dblp]
- Richard Peng (Georgia Institute of Technology - Atlanta, US) [dblp]
- Manuel Penschuck (Goethe-Universität - Frankfurt a. M., DE) [dblp]
- Cynthia A. Phillips (Sandia National Labs - Albuquerque, US) [dblp]
- Alex Pothen (Purdue University - West Lafayette, US) [dblp]
- Maria Predari (Universität Köln, DE) [dblp]
- Vijaya Ramachandran (University of Texas - Austin, US) [dblp]
- Sushant Sachdeva (University of Toronto, CA) [dblp]
- Ilya Safro (Clemson University, US) [dblp]
- Peter Sanders (KIT - Karlsruher Institut für Technologie, DE) [dblp]
- Christian Schulz (Universität Wien, AT) [dblp]
- Julian Shun (MIT - Cambridge, US) [dblp]
- Blair D. Sullivan (North Carolina State University - Raleigh, US) [dblp]
- Charalampos E. Tsourakakis (Harvard University - Cambridge, US) [dblp]
- data structures / algorithms / complexity
- optimization / scheduling
- graph algorithms
- algorithm engineering
- high-performance computing
- combinatorial scientific computing
- theoretical computer science