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: 14120
Venue: VLDB
Year: 2025
Pagerank: 5.093636e-05
Overall Rank: 10,899 | 25.23%
DOI: 10.14778/3705829.3705846

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

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 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

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
223	AliGraph: A Comprehensive Graph Neural Network Platform	2019	VLDB	0.00024182473
1,132	SANCUS: Staleness-Aware Communication-Avoiding Full-Graph Decentralized Training in Large-Scale Graph Neural Networks	2022	VLDB	0.00012041292
1,511	Speedup Graph Processing by Graph Ordering	2016	SIGMOD	0.00010538011
1,863	ByteGNN: Efficient Graph Neural Network Training at Large Scale	2022	VLDB	9.5950349e-05
1,865	An Experimental Comparison of Partitioning Strategies in Distributed Graph Processing	2017	VLDB	9.5915721e-05
2,221	Streaming Graph Partitioning: An Experimental Study	2018	VLDB	8.9260308e-05
3,362	Experimental Analysis of Streaming Algorithms for Graph Partitioning	2019	SIGMOD	7.4833791e-05
3,751	G3: When Graph Neural Networks Meet Parallel Graph Processing Systems on GPUs	2020	VLDB	7.1531889e-05
5,316	Comprehensive Evaluation of GNN Training Systems: A Data Management Perspective	2024	VLDB	6.2687017e-05
5,610	Hybrid Edge Partitioner: Partitioning Large Power-Law Graphs under Memory Constraints	2021	SIGMOD	6.1508076e-05
6,440	DiskGNN: Bridging I/O Efficiency and Model Accuracy for Out-of-Core GNN Training	2025	SIGMOD	5.8782861e-05
7,362	A Study of Partitioning Policies for Graph Analytics on Large-scale Distributed Platforms	2019	VLDB	5.6338252e-05

Semantically Similar Papers

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