Streaming Graph Challenge: Stochastic Block Partition

Abstract

An important objective for analyzing real-world graphs is to achieve scalable performance on large, streaming graphs. A challenging and relevant example is the graph partition problem. As a combinatorial problem, graph partition is NP-hard, but existing relaxation methods provide reasonable approximate solutions that can be scaled for large graphs. Competitive benchmarks and challenges have proven to be an effective means to advance state-of-the-art performance and foster community collaboration. This paper describes a graph partition challenge with a baseline partition algorithm of sub-quadratic complexity. The algorithm employs rigorous Bayesian inferential methods based on a statistical model that captures characteristics of the real-world graphs. This strong foundation enables the algorithm to address limitations of well-known graph partition approaches such as modularity maximization. This paper describes various aspects of the challenge including: (1) the data sets and streaming graph generator, (2) the baseline partition algorithm with pseudocode, (3) an argument for the correctness of parallelizing the Bayesian inference, (4) different parallel computation strategies such as node-based parallelism and matrix-based parallelism, (5) evaluation metrics for partition correctness and computational requirements, (6) preliminary timing of a Python-based demonstration code and the open source C++ code, and (7) considerations for partitioning the graph in streaming fashion. Data sets and source code for the algorithm as well as metrics, with detailed documentation are available at GraphChallenge.org.

To be published in 2017 IEEE High Performance Extreme Computing Conference (HPEC)

References in corpus (22)

• Modularity and community structure in networks
• Community detection in graphs
• Natural Scales in Geographical Patterns
• Finding community structure in networks using the eigenvectors of matrices
• Community Structure in Time-Dependent, Multiscale, and Multiplex Networks
• Stochastic blockmodels and community structure in networks
• The performance of modularity maximization in practical contexts
• Mixed membership stochastic blockmodels
• Limits of modularity maximization in community detection
• An efficient and principled method for detecting communities in networks
• Parsimonious module inference in large networks
• Efficient Monte Carlo and greedy heuristic for the inference of stochastic block models
• Entropy of stochastic blockmodel ensembles
• Static Graph Challenge: Subgraph Isomorphism
• Network Sampling: From Static to Streaming Graphs
• Asynchronous Gibbs Sampling
• A High Performance Implementation of Spectral Clustering on CPU-GPU Platforms
• Ensuring Rapid Mixing and Low Bias for Asynchronous Gibbs Sampling
• PageRank Pipeline Benchmark: Proposal for a Holistic System Benchmark for Big-Data Platforms
• Network Detection Theory and Performance
• Bayesian Discovery of Threat Networks
• An incremental local-first community detection method for dynamic graphs

Cited by in corpus (14)

• Sparse Deep Neural Network Graph Challenge
• RedisGraph GraphBLAS Enabled Graph Database
• GraphChallenge.org: Raising the Bar on Graph Analytic Performance
• Design and Implementation of Knowledge Base for Runtime Management of Software Defined Hardware
• Preconditioned Spectral Clustering for Stochastic Block Partition Streaming Graph Challenge
• Streaming 1.9 Billion Hypersparse Network Updates per Second with D4M
• 75,000,000,000 Streaming Inserts/Second Using Hierarchical Hypersparse GraphBLAS Matrices
• GraphChallenge.org Sparse Deep Neural Network Performance
• Design, Generation, and Validation of Extreme Scale Power-Law Graphs
• GraphChallenge.org Triangle Counting Performance
• Anonymized Network Sensing Graph Challenge
• Maneuver Identification Challenge
• Performance Measurements of Supercomputing and Cloud Storage Solutions
• Vertical, Temporal, and Horizontal Scaling of Hierarchical Hypersparse GraphBLAS Matrices