RECORD
SoK: The Faults in our Graph Benchmarks
Databases · Submitted 31 Mar 2024
abstract compiled · 2026-09-23 · no language-model review
The authors' main claim Finally, we suggest best practices to account for these issues when evaluating graph systems.
The compiled record
The paper's own sentences, arranged. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.
Open the compiled record
The abstract, sentence by sentence
Graph-structured data is prevalent in domains such as social networks, financial transactions, brain networks, and protein interactions. As a result, the research community has produced new databases and analytics engines to process such data. Unfortunately, there is not yet widespread benchmark standardization in graph processing, and the heterogeneity of evaluations found in the literature can lead researchers astray. Evaluations frequently ignore datasets' statistical idiosyncrasies, which significantly affect system performance. Scalability studies often use datasets that fit easily in memory on a modest desktop. Some studies rely on synthetic graph generators, but these generators produce graphs with unnatural characteristics that also affect performance, producing misleading results. Currently, the community has no consistent and principled manner with which to compare systems and provide guidance to developers who wish to select the system most suited to their application. We provide three different systematizations of benchmarking practices. First, we present a 12-year literary review of graph processing benchmarking, including a summary of the prevalence of specific datasets and benchmarks used in these papers. Second, we demonstrate the impact of two statistical properties of datasets that drastically affect benchmark performance. We show how different assignments of IDs to vertices, called vertex orderings, dramatically alter benchmark performance due to the caching behavior they induce. We also show the impact of zero-degree vertices on the runtime of benchmarks such as breadth-first search and single-source shortest path. We show that these issues can cause performance to change by as much as 38% on several popular graph processing systems. Finally, we suggest best practices to account for these issues when evaluating graph systems.
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | Graph-structured data is prevalent in domains such as social networks, financial transactions, brain networks, and protein interactions. | background 1.00 | 0.04 | 0.01 | asserted 1.00 |
| s1 | As a result, the research community has produced new databases and analytics engines to process such data. | background 1.00 | 0.04 | 0.02 | asserted 1.00 |
| s2 | Unfortunately, there is not yet widespread benchmark standardization in graph processing, and the heterogeneity of evaluations found in the literature can lead researchers astray. | gap 0.74 | 0.06 | 0.09 | asserted 0.78 |
| s3 | Evaluations frequently ignore datasets' statistical idiosyncrasies, which significantly affect system performance. | background 0.64 | 0.11 | 0.05 | asserted 1.00 |
| s4 | Scalability studies often use datasets that fit easily in memory on a modest desktop. | background 0.60 | 0.06 | 0.02 | asserted 0.99 |
| s5 | Some studies rely on synthetic graph generators, but these generators produce graphs with unnatural characteristics that also affect performance, producing misleading results. | background 0.87 | 0.09 | 0.05 | asserted 0.99 |
| s6 | Currently, the community has no consistent and principled manner with which to compare systems and provide guidance to developers who wish to select the system most suited to their application. | gap 0.96 | 0.04 | 0.12 | asserted 1.00 |
| s7 | We provide three different systematizations of benchmarking practices. | contribution 1.00 | 0.93 | 0.10 | asserted 0.99 |
| s8 | First, we present a 12-year literary review of graph processing benchmarking, including a summary of the prevalence of specific datasets and benchmarks used in these papers. | contribution 0.84 | 0.91 | 0.04 | asserted 1.00 |
| s9 | Second, we demonstrate the impact of two statistical properties of datasets that drastically affect benchmark performance. | contribution 0.98 | 0.93 | 0.07 | asserted 1.00 |
| s10 | We show how different assignments of IDs to vertices, called vertex orderings, dramatically alter benchmark performance due to the caching behavior they induce. | result 0.53 | 0.94 | 0.10 | asserted 1.00 |
| s11 | We also show the impact of zero-degree vertices on the runtime of benchmarks such as breadth-first search and single-source shortest path. | contribution 0.74 | 0.92 | 0.07 | asserted 1.00 |
| s12 | We show that these issues can cause performance to change by as much as 38% on several popular graph processing systems. | result 1.00 | 0.91 | 0.23 | asserted 0.93 |
| s13 | Finally, we suggest best practices to account for these issues when evaluating graph systems. | contribution 0.72 | 0.55 | 0.40 | hedged possibility 0.78 |
What was examined, and what was not
- arXiv listing abstract v1
- full text
- figures and tables
- references and citing sentences
- relations to other papers
- P abstract
- S sections
- T body sentences
- C citations
- R cross-paper relations
The paper
Original abstract
Graph-structured data is prevalent in domains such as social networks, financial transactions, brain networks, and protein interactions. As a result, the research community has produced new databases and analytics engines to process such data. Unfortunately, there is not yet widespread benchmark standardization in graph processing, and the heterogeneity of evaluations found in the literature can lead researchers astray. Evaluations frequently ignore datasets' statistical idiosyncrasies, which significantly affect system performance. Scalability studies often use datasets that fit easily in memory on a modest desktop. Some studies rely on synthetic graph generators, but these generators produce graphs with unnatural characteristics that also affect performance, producing misleading results. Currently, the community has no consistent and principled manner with which to compare systems and provide guidance to developers who wish to select the system most suited to their application. We provide three different systematizations of benchmarking practices. First, we present a 12-year literary review of graph processing benchmarking, including a summary of the prevalence of specific datasets and benchmarks used in these papers. Second, we demonstrate the impact of two statistical properties of datasets that drastically affect benchmark performance. We show how different assignments of IDs to vertices, called vertex orderings, dramatically alter benchmark performance due to the caching behavior they induce. We also show the impact of zero-degree vertices on the runtime of benchmarks such as breadth-first search and single-source shortest path. We show that these issues can cause performance to change by as much as 38% on several popular graph processing systems. Finally, we suggest best practices to account for these issues when evaluating graph systems.
Human review
How the literature uses it
What this paper does with the arXiv papers it cites
What it cites · 3 sentences without a confident label
Cites as support 1 paper
-
Most importantly, as Beamer et al. note, “using a standard high-quality reference implementation could help discourage using low-performance baselines” [ref] .
The GAP Benchmark Suite · Benchmark Suites: Standardization of Graph Benchmarking · 1.00
Cites as background 1 paper
-
The most recent and relevant benchmarking suites that we focus on in the remainder of this section are GAP-BS [ref] , Graphalytics [ref] , and GraphMineSuite [ref]
The GAP Benchmark Suite · Benchmark Suites: Standardization of Graph Benchmarking · 0.86
Discussion
Know something about this paper? Leave a comment, or highlight any passage above to comment on it.