圖形重新排序透過調整節點的排列方式來提升資料存取效率，但尋找最佳排序方式是一個 NP-困難問題。為了解決此問題，研究人員提出多種啟發式方法，包括能提升效能的 Gorder，以及能降低重新排序開銷的基於度數的 DBG。

本研究以攤銷成本（amortized cost）評估圖形重新排序的實用性，衡量圖形應用需執行多少次，才能攤銷重新排序所帶來的時間成本。過往研究多著重於比較 Gorder 與 RCM 的加速效能，卻忽略了與 BFS Ordering 相關的攤銷成本分析。本研究以 12 個真實世界圖形與 5 種常見圖形應用進行實驗，結果顯示 BFS Ordering 在加速效果與重新排序時間之間達成良好平衡。此外，我們亦透過隨機圖模型，分析不同圖形參數如何影響 BFS Ordering 的表現。

Graph reordering improves data access efficiency by adjusting vertex arrangements, but finding the optimal ordering is NP-hard. To address this, researchers have proposed several heuristic methods. One is Gorder, which boosts performance, and another is degree-based DBG ordering, which minimizes reordering overhead.

This study evaluates the practical applicability of graph reordering using amortized cost. Measures how many times a graph application needs to run to offset the cost of reordering. Previous studies mainly compared acceleration performance with Gorder and RCM but overlooked amortized cost in relation to BFS ordering. We evaluate our approach using 12 real-world graphs and five common graph applications, showing that BFS ordering strikes a good balance between acceleration and reordering time. Additionally, we use random graph models to analyze how various graph parameters affect BFS ordering performance.

[1] M. Valiyev, “Graph storage: How good is csr really?,” dated Dec, vol. 10, p. 8, 2017.
[2] E. Cuthill and J. McKee, “Reducing the bandwidth of sparse symmetric matrices,” in Proceedings of the 1969 24th national conference, pp. 157–172, 1969.
[3] A. George and J. W. Liu, Computer solution of large sparse positive definite. Prentice Hall Professional Technical Reference, 1981.
[4] H. Wei, J. X. Yu, C. Lu, and X. Lin, “Speedup graph processing by graph ordering,” in Proceedings of the 2016 International Conference on Management of Data, pp. 1813–1828, 2016.
[5] V. Balaji and B. Lucia, “When is graph reordering an optimization? Studying the effect of lightweight graph reordering across applications and input graphs,” in 2018 IEEE International Symposium on Workload Characterization (IISWC), pp. 203–214, IEEE, 2018.
[6] Y. Zhang, V. Kiriansky, C. Mendis, M. Zaharia, and S. Amarasinghe, “Optimizing cache performance for graph analytics,” arXiv preprint arXiv:1608.01362, 2016.
[7] P. Faldu, J. Diamond, and B. Grot, “A closer look at lightweight graph reordering,” in 2019 IEEE International Symposium on Workload Characterization (IISWC), pp. 1–13, IEEE, 2019.
[8] J. Kunegis, “KONECT – The Koblenz Network Collection,” in Proc. Int. Conf. on World Wide Web Companion, pp. 1343–1350, 2013.
[9] J. Shun and G. E. Blelloch, “Ligra: A lightweight graph processing framework for shared memory,” in Proceedings of the 18th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, pp. 135–146, 2013.
[10] D. J. Watts and S. H. Strogatz, “Collective dynamics of ‘small-world’ networks,” Nature, vol. 393, no. 6684, pp. 440–442, 1998.
[11] A.-L. Barabási and R. Albert, “Emergence of scaling in random networks,” Science, vol. 286, no. 5439, pp. 509–512, 1999.
[12] P. Holme and B. J. Kim, “Growing scale-free networks with tunable clustering,” Physical Review E, vol. 65, no. 2, p. 026107, 2002.
[13] P. Erdős and A. Rényi, “On random graphs I,” Publ. Math. Debrecen, vol. 6, pp. 290–297, 1959.
[14] E. N. Gilbert, “Random graphs,” The Annals of Mathematical Statistics, vol. 30, no. 4, pp. 1141–1144, 1959.
[15] R. Albert and A.-L. Barabási, “Statistical mechanics of complex networks,” Reviews of Modern Physics, vol. 74, no. 1, p. 47, 2002.
[16] NetworkX, "https://networkx.org", 2025.
[17] M. Kulkarni, K. Pingali, B. Walter, G. Ramanarayanan, K. Bala, and L. P. Chew, “Optimistic parallelism requires abstractions,” in Proceedings of the 28th ACM SIGPLAN Conference on Programming Language Design and Implementation, pp. 211–222, 2007.
[18] Y. Zhang, V. Kiriansky, C. Mendis, S. Amarasinghe, and M. Zaharia, “Making caches work for graph analytics,” in 2017 IEEE International Conference on Big Data (Big Data), pp. 293–302, IEEE, 2017.
[19] Y. Low, J. Gonzalez, A. Kyrola, D. Bickson, C. Guestrin, and J. M. Hellerstein, “GraphLab: A new parallel framework for machine learning,” in Conference on Uncertainty in Artificial Intelligence (UAI), vol. 20, 2010.
[20] J. E. Gonzalez, Y. Low, H. Gu, D. Bickson, and C. Guestrin, “PowerGraph: Distributed Graph-Parallel computation on natural graphs,” in 10th USENIX Symposium on Operating Systems Design and Implementation (OSDI 12), pp. 17–30, 2012.
[21] A. Kyrola, G. Blelloch, and C. Guestrin, “GraphChi: Large-Scale graph computation on just a PC,” in 10th USENIX Symposium on Operating Systems Design and Implementation (OSDI 12), pp. 31–46, 2012.
[22] D. Nguyen, A. Lenharth, and K. Pingali, “A lightweight infrastructure for graph analytics,” in Proceedings of the 24th ACM Symposium on Operating Systems Principles, pp. 456–471, 2013.
[23] N. Sundaram, N. R. Satish, M. M. A. Patwary, S. R. Dulloor, S. G. Vadlamudi, D. Das, and P. Dubey, “GraphMat: High performance graph analytics made productive,” arXiv preprint arXiv:1503.07241, 2015.
[24] G. Karypis and V. Kumar, “Multilevel k-way partitioning scheme for irregular graphs,” Journal of Parallel and Distributed Computing, vol. 48, no. 1, pp. 96–129, 1998.
[25] I. Stanton and G. Kliot, “Streaming graph partitioning for large distributed graphs,” in Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 1222–1230, 2012.
[26] G. Karypis and V. Kumar, “Multilevel graph partitioning schemes,” in ICPP (3), pp. 113–122, 1995.
[27] J. Banerjee, W. Kim, S.-J. Kim, and J. F. Garza, “Clustering a DAG for CAD databases,” IEEE Transactions on Software Engineering, vol. 14, no. 11, pp. 1684–1699, 1988.
[28] Y. Lim, U. Kang, and C. Faloutsos, “SlashBurn: Graph compression and mining beyond caveman communities,” IEEE Transactions on Knowledge and Data Engineering, vol. 26, no. 12, pp. 3077–3089, 2014.
[29] K. I. Karantasis, A. Lenharth, D. Nguyen, M. J. Garzaran, and K. Pingali, “Parallelization of reordering algorithms for bandwidth and wavefront reduction,” in SC’14: Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, pp. 921–932, IEEE, 2014.
[30] J. Arai, H. Shiokawa, T. Yamamuro, M. Onizuka, and S. Iwamura, “Rabbit Order: Just-in-time parallel reordering for fast graph analysis,” in 2016 IEEE International Parallel and Distributed Processing Symposium (IPDPS), pp. 22–31, IEEE, 2016.
[31] K. Lakhotia, S. Singapura, R. Kannan, and V. Prasanna, “RECALL: Reordered cache-aware locality-based graph processing,” in 2017 IEEE 24th International Conference on High Performance Computing (HiPC), pp. 273–282, IEEE, 2017.
[32] Q. Lyu, M. Sha, B. Gong, and K. Lyu, “Accelerating depth-first traversal by graph ordering,” in Proceedings of the 33rd International Conference on Scientific and Statistical Database Management, pp. 13–24, 2021.
[33] M. Drescher, M. A. Awad, S. D. Porumbescu, and J. D. Owens, “BOBA: A parallel lightweight graph reordering algorithm with heavyweight implications,” arXiv preprint arXiv:2306.10410, 2023.
[34] K. Wang, X. Lin, L. Qin, W. Zhang, and Y. Zhang, “Vertex priority based butterfly counting for large-scale bipartite networks,” PVLDB, 2019.
[35] E. Lee, J. Kim, K. Lim, S. H. Noh, and J. Seo, “Pre-Select static caching and neighborhood ordering for BFS-like algorithms on disk-based graph engines,” in 2019 USENIX Annual Technical Conference (USENIX ATC 19), pp. 459–474, 2019.
[36] B. Coleman, S. Segarra, A. J. Smola, and A. Shrivastava, “Graph reordering for cache-efficient near neighbor search,” Advances in Neural Information Processing Systems, vol. 35, pp. 38488–38500, 2022.
[37] O. Green, “Inverse-deletion BFS: Revisiting static graph BFS traversals with dynamic graph operations,” in 2021 IEEE High Performance Extreme Computing Conference (HPEC), pp. 1–7, 2021.
[38] F. Ziche, N. Bombieri, F. Busato, and R. Giugno, “GPU-accelerated BFS for dynamic networks,” in European Conference on Parallel Processing, pp. 74–87, Springer, 2024.