2020/03/18 by Siddharth Samsi, Jeremy Kepner, Vijay Gadepally +9 · 1 citation
Computer Science · Physics and Astronomy · #Advanced Graph Neural Networks #Butterfly graph #Complement graph #Complex Network Analysis Techniques #Graph #Graph Theory and Algorithms #Line graph #Null graph #Power graph analysis #Strength of a graph #Voltage graph #cs.DC #cs.PF
paper · pdf · doi:10.1109/hpec43674.2020.9286166
10 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
arxiv created 2020/03/18 · openalex created_date 2020/03/27 · openalex publication_date 2020/09/22 · arxiv updated 2020/12/24 · openalex updated_date 2026/08/06
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, Ttri, is a strong function of the number of edges in the graph, Ne, which improved significantly from 2017 (Ttri≈ (Ne/108)4/3) to 2018 (Ttri≈ Ne/109) 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.