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.2056825e-05
Overall Rank: 9,233 | 37.93%
DOI: 10.14778/3705829.3705846

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,818	ThunderGNN: Unlocking Tensor Cores for Graph Neural Networks	2026	VLDB	4.9793485e-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.00024816965
1,134	SANCUS: Staleness-Aware Communication-Avoiding Full-Graph Decentralized Training in Large-Scale Graph Neural Networks	2022	VLDB	0.00011893521
1,440	Speedup Graph Processing by Graph Ordering	2016	SIGMOD	0.00010641888
1,772	ByteGNN: Efficient Graph Neural Network Training at Large Scale	2022	VLDB	9.6792287e-05
1,907	An Experimental Comparison of Partitioning Strategies in Distributed Graph Processing	2017	VLDB	9.397856e-05
2,248	Streaming Graph Partitioning: An Experimental Study	2018	VLDB	8.756531e-05
3,390	Experimental Analysis of Streaming Algorithms for Graph Partitioning	2019	SIGMOD	7.3509644e-05
3,752	G3: When Graph Neural Networks Meet Parallel Graph Processing Systems on GPUs	2020	VLDB	7.0517024e-05
4,898	Comprehensive Evaluation of GNN Training Systems: A Data Management Perspective	2024	VLDB	6.365824e-05
5,730	Hybrid Edge Partitioner: Partitioning Large Power-Law Graphs under Memory Constraints	2021	SIGMOD	6.0154682e-05
6,528	DiskGNN: Bridging I/O Efficiency and Model Accuracy for Out-of-Core GNN Training	2025	SIGMOD	5.7553643e-05
7,476	A Study of Partitioning Policies for Graph Analytics on Large-scale Distributed Platforms	2019	VLDB	5.5161224e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	3,752	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,459	Towards Ideal Temporal Graph Neural Networks: Evaluations and Conclusions after 10,000 GPU Hours	2025	VLDB
4	2,596	Scalable and Efficient Full-Graph GNN Training for Large Graphs	2023	SIGMOD
5	4,853	NeutronOrch: Rethinking Sample-based GNN Training under CPU-GPU Heterogeneous Environments	2024	VLDB
6	10,706	Efficient GNN Training on Giant Graphs with Collective Batching and Scheduling	2026	VLDB
7	6,826	SIMPLE: Efficient Temporal Graph Neural Network Training at Scale with Dynamic Data Placement	2024	SIGMOD
8	4,826	Accelerating Sampling and Aggregation Operations in GNN Frameworks with GPU Initiated Direct Storage Accesses	2024	VLDB
9	4,898	Comprehensive Evaluation of GNN Training Systems: A Data Management Perspective	2024	VLDB
10	6,669	Efficient Training of Graph Neural Networks on Large Graphs	2024	VLDB