Can Graph Reordering Speed Up Graph Neural Network Training? An Experimental Study

Summary: Empirical evaluation of 12 graph-reordering strategies in PyTorch Geometric and DGL for CPU/GPU GNN training. Reordering often reduces training time, with gains shaped by model hyperparameters, hardware, metrics, and amortizable preprocessing cost. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: h8183355fd6f8d96a
Venue: VLDB
Year: 2025
Pagerank: 5.2032182e-05
Overall Rank: 9,243 | 37.88%
DOI: 10.14778/3705829.3705846
PDF: Download (CC BY-NC-ND 4.0)

Incoming Non-self Citations Over Time

Authors

1. Nikolai Merkel (Technical University of Munich)
2. Pierre Toussing (Technical University of Munich)
3. Ruben Mayer (University of Bayreuth)
4. Hans-Arno Jacobsen (University of Toronto)

BibTeX Citation

@article{merkel_vldb25,
        title = {{Can Graph Reordering Speed Up Graph Neural Network Training? An Experimental Study}},
        author = {Merkel, Nikolai and Toussing, Pierre and Mayer, Ruben and Jacobsen, Hans-Arno},
        journal = {PVLDB},
        series = {{VLDB} '25},
        volume = {18},
        number = {2},
        pages = {293--307},
        doi = {10.14778/3705829.3705846},
        url = {https://doi.org/10.14778/3705829.3705846},
        year = {2025}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
10,828	ThunderGNN: Unlocking Tensor Cores for Graph Neural Networks	2026	VLDB	4.9769913e-05

Outgoing Citations (Sorted by Pagerank)

Showing 12 of 12 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
211	AliGraph: A Comprehensive Graph Neural Network Platform	2019	VLDB	0.00024805216
1,134	SANCUS: Staleness-Aware Communication-Avoiding Full-Graph Decentralized Training in Large-Scale Graph Neural Networks	2022	VLDB	0.0001188789
1,438	Speedup Graph Processing by Graph Ordering	2016	SIGMOD	0.00010647473
1,772	ByteGNN: Efficient Graph Neural Network Training at Large Scale	2022	VLDB	9.6746467e-05
1,908	An Experimental Comparison of Partitioning Strategies in Distributed Graph Processing	2017	VLDB	9.3935543e-05
2,250	Streaming Graph Partitioning: An Experimental Study	2018	VLDB	8.7533947e-05
3,390	Experimental Analysis of Streaming Algorithms for Graph Partitioning	2019	SIGMOD	7.3484517e-05
3,753	G3: When Graph Neural Networks Meet Parallel Graph Processing Systems on GPUs	2020	VLDB	7.0483642e-05
4,899	Comprehensive Evaluation of GNN Training Systems: A Data Management Perspective	2024	VLDB	6.3628105e-05
5,731	Hybrid Edge Partitioner: Partitioning Large Power-Law Graphs under Memory Constraints	2021	SIGMOD	6.0126206e-05
6,530	DiskGNN: Bridging I/O Efficiency and Model Accuracy for Out-of-Core GNN Training	2025	SIGMOD	5.7526398e-05
7,481	A Study of Partitioning Policies for Graph Analytics on Large-scale Distributed Platforms	2019	VLDB	5.5135111e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	3,753	G3: When Graph Neural Networks Meet Parallel Graph Processing Systems on GPUs	2020	VLDB
2	1,772	ByteGNN: Efficient Graph Neural Network Training at Large Scale	2022	VLDB
3	11,465	Towards Ideal Temporal Graph Neural Networks: Evaluations and Conclusions after 10,000 GPU Hours	2025	VLDB
4	2,598	Scalable and Efficient Full-Graph GNN Training for Large Graphs	2023	SIGMOD
5	4,855	NeutronOrch: Rethinking Sample-based GNN Training under CPU-GPU Heterogeneous Environments	2024	VLDB
6	10,716	Efficient GNN Training on Giant Graphs with Collective Batching and Scheduling	2026	VLDB
7	6,831	SIMPLE: Efficient Temporal Graph Neural Network Training at Scale with Dynamic Data Placement	2024	SIGMOD
8	4,828	Accelerating Sampling and Aggregation Operations in GNN Frameworks with GPU Initiated Direct Storage Accesses	2024	VLDB
9	6,673	Efficient Training of Graph Neural Networks on Large Graphs	2024	VLDB
10	4,899	Comprehensive Evaluation of GNN Training Systems: A Data Management Perspective	2024	VLDB