Graph Algorithms

Graph algorithms are the basis underlying many of the network analysis performed on big data to identify relationships between entities and/or events.

Software

Many of the linear-algebra based algorithms are included in the LAGraph library

Graph Kernel Collection (GKC) Public Release of CMU-SPEED's implementations of GAP benchmark suite. The 6 graph algorithms in the GAP Benchmark Suite are represented here (BFS, Betweeness Centrality, Connected Components, Pagerank, SSSP, and Triangle Counting).

Publications

Delayed Asynchronous Iterative Graph Algorithms
Mark Blanco, Scott McMillan, Tze Meng Low
High Performance Extreme Computing (HPEC)
2021
Towards an Objective Metric for the Performance of Exact Triangle Count
Mark Blanco, Scott McMillan, Tze Meng Low
High Performance Extreme Computing (HPEC)
2020
Evaluation of Graph Analytics Frameworks Using the GAP Benchmark Suite
Ariful Azad, Mohsen Mahmoudi Aznaveh, Scott Beamer, Mark Blanco, Jinhao Chen, Luke D’Alessandro, Roshan Dathathri, Tim Davis, Kevin Deweese, Jesun Firoz, Henry A Gabb, Gurbinder Gill, Balint Hegyi, Scott Kolodziej, Tze Meng Low, Andrew Lumsdaine, Tugsbayasgalan Manlaibaatar, Timothy G Mattson, Scott McMillan, Ramesh Peri, Keshav Pingali, Upasana Sridhar, Gabor Szarnyas, Yunming Zhang , Yongzhe Zhang
IEEE International Symposium on Workload Characterization
2020
Linear Algebraic Louvain Method in Python
Versions
  Accepted
  Published-DOI: 10.1109/IPDPSW50202.2020.00050
Tze Meng Low, Daniele G. Spaminato, Scott McMillan, Michel Pelletier
Workshop on Graphs, Architectures, Programming, and Learning (GrAPL)
2020
Load Balancing Eager K-truss on GPU and CPU via Fine-Grained Parallelism
Graph Challenge Champion
Mark Blanco, Tze Meng Low, Kyungjoo Kim
High Performance Extreme Computing (HPEC)
2019
Delta-Stepping SSSP: From Vertices and Edges to GraphBLAS Implementations
Upasana Sridhar, Mark Blanco, Rahul Mayuranath, Daniele G. Spaminato, Scott McMillan, Tze Meng Low
Workshop on Graphs, Architectures, Programming, and Learning (GrAPL)
2019
Linear Algebraic Depth-First Search
Daniele G. Spaminato, Upasana Sridhar, Tze Meng Low
6th ACM SIGPLAN International Workshop on Libraries, Languages, and Compilers for Array Programming
2019
Linear Algebraic Formulation of Edge-centric K-truss Algorithms with Adjacency Matrices
Graph Challenge Finalist
Tze Meng Low, Anurag Kutuluru, Upasana Sridhar, Franz Franchetti, Scott McMillan
High Performance Extreme Computing Conference(HPEC)
2018
A Family of Provably Correct Algorithms for Exact Triangle Counting
Versions
  Published
Matthew Lee, Tze Meng Low
1st International Workshop on Software Correctness for HPC Applications
2017
First look: Linear algebra-based triangle counting without matrix multiplication
Graph Challenge Honorable Mention
Tze Meng Low, Varun Nagaraj Rao, Matthew Lee, Doru Popovici, Franz Franchetti, Scott McMillan
High Performance Extreme Computing Conference (HPEC)
2017