GraphChallenge.org Triangle Counting Performance

Abstract

The rise of graph analytic systems has created a need for new ways to measure and compare the capabilities of graph processing systems. The MIT/Amazon/IEEE Graph Challenge has been developed to provide a well-defined community venue for stimulating research and highlighting innovations in graph analysis software, hardware, algorithms, and systems. GraphChallenge.org provides a wide range of pre-parsed graph data sets, graph generators, mathematically defined graph algorithms, example serial implementations in a variety of languages, and specific metrics for measuring performance. The triangle counting component of GraphChallenge.org tests the performance of graph processing systems to count all the triangles in a graph and exercises key graph operations found in many graph algorithms. In 2017, 2018, and 2019 many triangle counting submissions were received from a wide range of authors and organizations. This paper presents a performance analysis of the best performers of these submissions. These submissions show that their state-of-the-art triangle counting execution time, $T_{\mathrm{tri}}$, is a strong function of the number of edges in the graph, $N_e$, which improved significantly from 2017 ($T_{\mathrm{tri}}\approx (N_e/10^8{)}^{4/3}$) to 2018 ($T_{\mathrm{tri}}\approx N_e/10^9$) and remained comparable from 2018 to 2019. Graph Challenge provides a clear picture of current graph analysis systems and underscores the need for new innovations to achieve high performance on very large graphs.

arXiv comment10 pages, 8 figures, 121 references, to be submitted to IEEE HPEC 2020. This work reports new updated results on prior work reported in arXiv:1805.09675 & arXiv:1708.06866

References in corpus (28)

• Spectrum of Controlling and Observing Complex Networks
• Community structure and scale-free collections of Erdös-Rényi graphs
• Mathematical Foundations of the GraphBLAS
• Percolation of localized attack on complex networks
• Static Graph Challenge: Subgraph Isomorphism
• Standards for Graph Algorithm Primitives
• Streaming Graph Challenge: Stochastic Block Partition
• Graphs, Matrices, and the GraphBLAS: Seven Good Reasons
• A Comparative Study on Exact Triangle Counting Algorithms on the GPU
• Sparse Deep Neural Network Graph Challenge
• Enabling Massive Deep Neural Networks with the GraphBLAS
• RadiX-Net: Structured Sparse Matrices for Deep Neural Networks
• RedisGraph GraphBLAS Enabled Graph Database
• Using a Power Law Distribution to describe Big Data
• Design and Implementation of Knowledge Base for Runtime Management of Software Defined Hardware
• Novel Graph Processor Architecture, Prototype System, and Results
• Hypersparse Neural Network Analysis of Large-Scale Internet Traffic
• Exploration of Fine-Grained Parallelism for Load Balancing Eager K-truss on GPU and CPU
• PageRank Pipeline Benchmark: Proposal for a Holistic System Benchmark for Big-Data Platforms
• Preconditioned Spectral Clustering for Stochastic Block Partition Streaming Graph Challenge
• Streaming 1.9 Billion Hypersparse Network Updates per Second with D4M
• Genetic Sequence Matching Using D4M Big Data Approaches
• Design, Generation, and Validation of Extreme Scale Power-Law Graphs
• Training Behavior of Sparse Neural Network Topologies
• On Large-Scale Graph Generation with Validation of Diverse Triangle Statistics at Edges and Vertices
• Distributed Triangle Counting in the Graphulo Matrix Math Library
• Rapid Sequence Identification of Potential Pathogens Using Techniques from Sparse Linear Algebra
• Database Operations in D4M.jl

Cited by in corpus (1)

• Anonymized Network Sensing Graph Challenge