The LDBC Graphalytics Benchmark

Alexandru Iosup, Ahmed Musaafir, Alexandru Uta, Arnau Prat-Pérez, Gábor Szárnyas, Hassan Chafi, Ilie Gabriel Tanase, Lifeng Nai, Michael J. Anderson, Mihai Capota, Narayanan Sundaram, Peter A. Boncz, Siegfried Depner, Stijn Heldens, Thomas Manhardt, Tim Hegeman, Wing Lung Ngai, Yinglong Xia

Abstract

In this document, we describe LDBC Graphalytics, an industrial-grade benchmark for graph analysis platforms. The main goal of Graphalytics is to enable the fair and objective comparison of graph analysis platforms. Due to the diversity of bottlenecks and performance issues such platforms need to address, Graphalytics consists of a set of selected deterministic algorithms for full-graph analysis, standard graph datasets, synthetic dataset generators, and reference output for validation purposes. Its test harness produces deep metrics that quantify multiple kinds of systems scalability, weak and strong, and robustness, such as failures and performance variability. The benchmark also balances comprehensiveness with runtime necessary to obtain the deep metrics. The benchmark comes with open-source software for generating performance data, for validating algorithm results, for monitoring and sharing performance data, and for obtaining the final benchmark result as a standard performance report.

Introduction: The Challenge of Graph Benchmarking

Graph processing has become a cornerstone of modern data science, critical for applications ranging from social network analysis to scientific modeling. This importance has led to a proliferation of platforms such as Apache Giraph, GraphLab, and Spark. However, comparing these systems objectively is notoriously difficult. Performance in graph analytics is "irregular"; a platform that excels at a simple search on a small graph might fail significantly when faced with complex clustering algorithms or massive, skewed datasets.

The LDBC Graphalytics Benchmark: The graph & RDF benchmark reference.

Existing benchmarks often focus too narrowly on a single metric, such as the BFS-only Graph500. There is a clear need for a benchmark that captures the complex interaction between algorithm logic and graph structure while remaining portable across different architectures—including multi-core, GPUs, and distributed systems—and remaining "future-proof" as hardware continues to advance.

Methodology

The LDBC Graphalytics Benchmark is managed by the Linked Data Benchmark Council (LDBC) and utilizes a formal benchmarking process. Key methodological highlights include:

  • The Six Kernels: The benchmark selects six representative algorithms (kernels) that cover various computational patterns: Breadth-First Search (BFS), PageRank (PR), Weakly Connected Components (WCC), Community Detection (CDLP), Local Clustering Coefficient (LCC), and Single-Source Shortest Paths (SSSP).
  • Standardized Data Format: Graphs use the "Edge/Vertex-List with Properties" (EVLP) format, ensuring a common starting point for all systems.
  • Execution Phases: The benchmark distinguishes between Loading (pre-processing/ingesting data) and Running (executing the algorithm). This allows researchers to measure "cold-start" performance (Makespan) versus "warmed-up" performance (Processing Time).
  • Rigorous Validation: To ensure results are correct, the benchmark uses three validation methods: Exact match (for BFS/CDLP), Equivalence match (for WCC labels), and Epsilon match (to allow for floating-point rounding errors in PR/LCC/SSSP).
  • Renewal Process: A unique mechanism to update the workload and scale definitions periodically ensures the benchmark remains relevant as systems evolve.

Datasets and Scaling

Graphalytics uses a mix of real-world and synthetic data, categorized by "Scale" (a logarithmic measure of vertices + edges) and labeled with intuitive "T-shirt sizes" (2XS to 3XL).

  • Real-world Data: Includes datasets like wiki-talk, cit-patents, com-friendster, and twitter_mpi, covering domains from knowledge graphs to social networks.
  • Synthetic Data: Utilizes the Graph500 generator for power-law distributions and the LDBC Datagen for realistic social network structures.
  • Scaling Formula: The paper introduces a formal way to quantify graph size: $Scale(n, m) = \lfloor 10 \log_{10}(n + m) \rfloor / 10$. The reference "Large" (L) scale is defined as the largest graph a state-of-the-art platform can process within one hour on a single commodity machine.

Key Insights and Metrics

The core philosophy of Graphalytics is that a single "speed" number is misleading. The benchmark forces systems to handle different bottlenecks—some algorithms are memory-bandwidth bound, while others are latency-sensitive or compute-heavy. Beyond raw speed, the benchmark tracks robustness, including failures (time-outs, crashes, data corruption) and performance variability.

For competition-level benchmarking, the framework establishes several key metrics:

  • Workload: A standard run involves 90 graph-processing jobs (6 algorithms across 5 datasets with 3 repetitions each).
  • Throughput: It utilizes "Edges and Vertices Per Second" (EVPS), which better accounts for vertex-dominated algorithms than traditional "Edges Per Second" (EPS).
  • Cost: It incorporates "Price-per-performance" (PPP) based on a three-year Total Cost of Ownership (TCO), aligning with standard TPC pricing models.

Limitations and Future Work

Currently, the benchmark focuses on "full-graph analysis" (batch processing) and does not yet cover fine-grained updates, point queries, or streaming graph data. While the data format supports complex vertex/edge properties, the current core algorithms primarily use weights or simple identifiers. Furthermore, some computationally expensive algorithms, like Betweenness Centrality, were omitted due to the difficulty of validation at scale without approximation.

Future work includes releasing a "Full Disclosure Report" template to facilitate vendor publication and verification of official results, as well as expanding the workload to include more complex property usage and dynamic graph updates.

Summary updated

Abstract

In this document, we describe LDBC Graphalytics, an industrial-grade benchmark for graph analysis platforms. The main goal of Graphalytics is to enable the fair and objective comparison of graph analysis platforms. Due to the diversity of bottlenecks and performance issues such platforms need to address, Graphalytics consists of a set of selected deterministic algorithms for full-graph analysis, standard graph datasets, synthetic dataset generators, and reference output for validation purposes. Its test harness produces deep metrics that quantify multiple kinds of systems scalability, weak and strong, and robustness, such as failures and performance variability. The benchmark also balances comprehensiveness with runtime necessary to obtain the deep metrics. The benchmark comes with open-source software for generating performance data, for validating algorithm results, for monitoring and sharing performance data, and for obtaining the final benchmark result as a standard performance report.
BibTeX
@misc{iosup2020ldbc,
  author = {Alexandru Iosup and Ahmed Musaafir and Alexandru Uta and Arnau Prat-Pérez and Gábor Szárnyas and Hassan Chafi and Ilie Gabriel Tanase and Lifeng Nai and Michael J. Anderson and Mihai Capota and Narayanan Sundaram and Peter A. Boncz and Siegfried Depner and Stijn Heldens and Thomas Manhardt and Tim Hegeman and Wing Lung Ngai and Yinglong Xia},
  title = {{The LDBC Graphalytics Benchmark}},
  year = {2020},
  eprint = {2011.15028},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2011.15028},
}
Figure