{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T01:32:39Z","timestamp":1760059959522,"version":"build-2065373602"},"reference-count":47,"publisher":"MDPI AG","issue":"8","license":[{"start":{"date-parts":[[2025,7,23]],"date-time":"2025-07-23T00:00:00Z","timestamp":1753228800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Symmetry"],"abstract":"<jats:p>Many challenges in solving large graph coloring through parallel strategies remain unresolved. Previous algorithms based on Pregel-like frameworks, such as Apache Giraph, encounter parallelism bottlenecks due to sequential execution and the need for a full graph traversal in certain stages. Additionally, GPU-based algorithms face the dilemma of costly and time-consuming processing when moving complex graph applications to GPU architectures. In this study, we propose Spardex, a novel parallel and distributed graph coloring optimization algorithm designed to overcome and avoid these challenges. We design a symmetry-driven optimization approach wherein the EdgePartition1D strategy in GraphX induces partitioning asymmetry, leading to overlapping locally symmetric regions. This structure is leveraged through asymmetric partitioning and symmetric reassembly to reduce the search space. A two-stage pipeline consisting of partitioned repaint and core conflict detection is developed, enabling the precise correction of conflicts without traversing the entire graph as in previous algorithms. We also integrate symmetry principles from combinatorial optimization into a distributed computing framework, demonstrating that leveraging locally symmetric subproblems can significantly enhance the efficiency of large-scale graph coloring. Combined with Spark-specific optimizations such as AQE skew join optimization, all these techniques contribute to an efficient parallel graph coloring optimization in Spardex. We conducted experiments using the Aliyun Cloud platform. The results demonstrate that Spardex achieves a reduction of 8\u201372% in the number of colors and a speedup of 1.13\u201310.27 times over concurrent algorithms.<\/jats:p>","DOI":"10.3390\/sym17081177","type":"journal-article","created":{"date-parts":[[2025,7,23]],"date-time":"2025-07-23T14:22:44Z","timestamp":1753280564000},"page":"1177","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Scalable Graph Coloring Optimization Based on Spark GraphX Leveraging Partition Asymmetry"],"prefix":"10.3390","volume":"17","author":[{"ORCID":"https:\/\/orcid.org\/0009-0007-0680-632X","authenticated-orcid":false,"given":"Yihang","family":"Shen","sequence":"first","affiliation":[{"name":"School of Computer Science, Nanjing University of Posts and Telecommunications, Nanjing 210023, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xiang","family":"Li","sequence":"additional","affiliation":[{"name":"State Key Laboratory of Millimeter Waves, Southeast University, Nanjing 210096, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tao","family":"Yuan","sequence":"additional","affiliation":[{"name":"School of Medicine, Tongji University, Shanghai 200333, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shanshan","family":"Chen","sequence":"additional","affiliation":[{"name":"School of Computer Science, Nanjing University of Posts and Telecommunications, Nanjing 210023, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2025,7,23]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"654","DOI":"10.1137\/0914041","article-title":"A parallel graph coloring heuristic","volume":"14","author":"Jones","year":"1993","journal-title":"SIAM J. Sci. Comput."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"1036","DOI":"10.1137\/0215074","article-title":"A simple parallel algorithm for the maximal independent set problem","volume":"15","author":"Luby","year":"1986","journal-title":"SIAM J. Comput."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1016\/0020-0190(92)90140-Q","article-title":"Finding good approximate vertex and edge partitions is NP-hard","volume":"42","author":"Bui","year":"1993","journal-title":"Inf. Process. Lett."},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Berman, P., and Karpinski, M. (1999). On some tighter inapproximability results. Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, Prague, Czech Republic, 11\u201315 July 1999, Springer.","DOI":"10.1007\/3-540-48523-6_17"},{"key":"ref_5","unstructured":"Naumov, M., Castonguay, P., and Cohen, J. (2024, May 26). Parallel Graph Coloring with Applications to the Incomplete-LU Factorization on the GPU; Nvidia White Paper; May 2015. Available online: https:\/\/research.nvidia.com\/sites\/default\/files\/pubs\/2015-05_Parallel-Graph-Coloring\/nvr-2015-001.pdf."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1016\/0020-0190(92)90041-S","article-title":"A constructive proof of Vizing\u2019s theorem","volume":"41","author":"Misra","year":"1992","journal-title":"Inf. Process. Lett."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"875","DOI":"10.1007\/s10586-023-03988-x","article-title":"A new distributed graph coloring algorithm for large graphs","volume":"27","author":"Brighen","year":"2024","journal-title":"Clust. Comput."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"043131","DOI":"10.1103\/PhysRevResearch.4.043131","article-title":"Graph coloring with physics-inspired graph neural networks","volume":"4","author":"Schuetz","year":"2022","journal-title":"Phys. Rev. Res."},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Grosset, A.V.P., Zhuand, P., Venkatasubramanian, S., and Hall, M. (2011, January 12\u201316). Evaluating graph coloring on GPUs. Proceedings of the PPoPP\u201911 Proceedings of the 16th ACM Symposium on Principles and Practice of Parallel Programming, San Antonio, TX, USA. ACM SIGPLAN Notices-PPoPP\u201911.","DOI":"10.1145\/1941553.1941597"},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"160","DOI":"10.1109\/TPDS.2020.3014173","article-title":"Feluca: A two-stage graph coloring algorithm with color-centric paradigm on GPU","volume":"32","author":"Zheng","year":"2020","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Che, S., Rodgers, G., Beckmann, B., and Reinhardt, S. (2015, January 25\u201329). Graph coloring on the GPU and some techniques to improve load imbalance. Proceedings of the 2015 IEEE International Parallel and Distributed Processing Symposium Workshop, Hyderabad, India.","DOI":"10.1109\/IPDPSW.2015.74"},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Boman, E.G., Devine, K.D., and Rajamanickam, S. (2013, January 17\u201322). Scalable matrix computations on large scale-free graphs using 2D graph partitioning. Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, Denver, CO, USA.","DOI":"10.1145\/2503210.2503293"},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Gandhi, N.M., and Misra, R. (2015, January 25\u201329). Performance comparison of parallel graph coloring algorithms on bsp model using hadoop. Proceedings of the 2015 International Conference on Computing, Networking and Communications (ICNC), Garden Grove, CA, USA.","DOI":"10.1109\/ICCNC.2015.7069325"},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Sharafeldeen, A., Alrahmawy, M., and Elmougy, S. (2023). Graph partitioning MapReduce-based algorithms for counting triangles in large-scale graphs. Sci. Rep., 13.","DOI":"10.1038\/s41598-022-25243-w"},{"key":"ref_15","unstructured":"Leighton, F.T. (1985). Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes, Elsevier."},{"key":"ref_16","first-page":"347","article-title":"What color is your Jacobian? Graph coloring for computing derivatives","volume":"44","author":"Gebremedhin","year":"2002","journal-title":"SIAM Rev."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"1733","DOI":"10.1137\/S0097539794270248","article-title":"A spectral technique for coloring random 3-colorable graphs","volume":"26","author":"Alon","year":"1997","journal-title":"SIAM J. Comput."},{"key":"ref_18","first-page":"211","article-title":"Algorithms for a maximum clique and a maximum independent set of a circle graph","volume":"2","author":"Gavril","year":"1972","journal-title":"Networks"},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"379","DOI":"10.1023\/A:1009823419804","article-title":"Hybrid Evolutionary Algorithms for Graph Coloring","volume":"3","author":"Galinier","year":"1999","journal-title":"J. Comb. Optim."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1023\/A:1009638304510","article-title":"Graph coloring with adaptive evolutionary algorithms","volume":"4","author":"Eiben","year":"1998","journal-title":"J. Heuristics"},{"key":"ref_21","first-page":"25","article-title":"On an estimate of the chromatic class of a p-graph","volume":"3","author":"Vizing","year":"1964","journal-title":"Diskret. Analiz"},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"15879","DOI":"10.1073\/pnas.252631999","article-title":"The average distances in random graphs with given expected degrees","volume":"99","author":"Chung","year":"2002","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"449","DOI":"10.4153\/CJM-1965-045-4","article-title":"Paths, Trees, and Flowers","volume":"17","author":"Edmonds","year":"1965","journal-title":"Can. J. Math."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"359","DOI":"10.1137\/S1064827595287997","article-title":"A fast and high quality multilevel scheme for partitioning irregular graphs","volume":"20","author":"Karypis","year":"1998","journal-title":"SIAM J. Sci. Comput."},{"key":"ref_25","doi-asserted-by":"crossref","unstructured":"Gibbons, P.B. (1989, January 18\u201321). A more practical PRAM model. Proceedings of the First Annual ACM Symposium on Parallel Algorithms and Architectures, Santa Fe, NM, USA.","DOI":"10.1145\/72935.72953"},{"key":"ref_26","doi-asserted-by":"crossref","unstructured":"Kawarabayashi, K., Khoury, S., Schild, A., and Schwartzman, G. (2019). Improved distributed approximations for maximum independent set. arXiv.","DOI":"10.1145\/3382734.3405728"},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"146","DOI":"10.1137\/0201010","article-title":"Depth-first search and linear graph algorithms","volume":"1","author":"Tarjan","year":"1972","journal-title":"SIAM J. Comput."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"372","DOI":"10.1145\/362248.362272","article-title":"Algorithm 447: Efficient algorithms for graph manipulation","volume":"16","author":"Hopcroft","year":"1973","journal-title":"Commun. ACM"},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"601","DOI":"10.1145\/234533.234534","article-title":"A new approach to the minimum cut problem","volume":"43","author":"Karger","year":"1996","journal-title":"J. ACM"},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1145\/321879.321884","article-title":"Efficiency of a good but not linear set union algorithm","volume":"22","author":"Tarjan","year":"1975","journal-title":"J. ACM"},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"1285","DOI":"10.1007\/s10766-016-0470-1","article-title":"LCS: An Efficient Data Eviction Strategy for Spark","volume":"45","author":"Geng","year":"2017","journal-title":"Int. J. Parallel Prog."},{"key":"ref_32","doi-asserted-by":"crossref","unstructured":"Peters, J.F., Skowron, A., Grzyma\u0142a-Busse, J.W., Kostek, B., \u015awiniarski, R.W., and Szczuka, M.S. (2004). A Partition Model of Granular Computing. Transactions on Rough Sets I. Lecture Notes in Computer Science, Springer.","DOI":"10.1007\/b98175"},{"key":"ref_33","doi-asserted-by":"crossref","unstructured":"Adinew, D.M., Zhou, S., and Liao, Y. (2020, January 20\u201324). Spark performance optimization analysis in memory management with deploy mode in standalone cluster computing. Proceedings of the 2020 IEEE 36th International Conference on Data Engineering (ICDE), Dallas, TX, USA.","DOI":"10.1109\/ICDE48307.2020.00242"},{"key":"ref_34","first-page":"415","article-title":"An Improved Memory Cache Management Study Based on Spark","volume":"56","author":"Wang","year":"2018","journal-title":"Comput. Mater. Contin."},{"key":"ref_35","doi-asserted-by":"crossref","unstructured":"Gannon, D., Jalby, W., and Gallivan, K. (1987). Strategies for cache and local memory management by global program transformation. International Conference on Supercomputing, Springer.","DOI":"10.1007\/3-540-18991-2_14"},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"10","DOI":"10.1016\/j.jpdc.2020.03.010","article-title":"Dynamic memory-aware scheduling in spark computing environment","volume":"141","author":"Tang","year":"2020","journal-title":"J. Parallel Distrib. Comput."},{"key":"ref_37","doi-asserted-by":"crossref","unstructured":"Perez, T.B., Zhou, X., and Cheng, D. (2018, January 13\u201316). Reference-distance eviction and prefetching for cache management in spark. Proceedings of the 47th International Conference on Parallel Processing, Eugene, OR, USA.","DOI":"10.1145\/3225058.3225087"},{"key":"ref_38","doi-asserted-by":"crossref","unstructured":"Zhou, P., Ruan, Z., Fang, Z., Shand, M., Roazen, D., and Cong, J. (2018, January 2\u20134). Doppio: I\/o-aware performance analysis, modeling and optimization for in-memory computing framework. Proceedings of the 2018 IEEE International Symposium on Performance Analysis of Systems and Software (ISPASS), Belfast, UK.","DOI":"10.1109\/ISPASS.2018.00011"},{"key":"ref_39","doi-asserted-by":"crossref","unstructured":"Yang, Z., Jia, D., Ioannidis, S., Mi, N., and Sheng, B. (2018, January 2\u20137). Intermediate data caching optimization for multi-stage and parallel big data frameworks. Proceedings of the 2018 IEEE 11th International Conference on Cloud Computing (CLOUD), San Francisco, CA, USA.","DOI":"10.1109\/CLOUD.2018.00042"},{"key":"ref_40","doi-asserted-by":"crossref","unstructured":"Huang, S., Huang, J., Dai, J., Xie, T., and Huang, B. (2010, January 1\u20136). The HiBench benchmark suite: Characterization of the MapReduce-based data analysis. Proceedings of the 2010 IEEE 26th International Conference on Data Engineering Workshops (ICDEW 2010), Long Beach, CA, USA.","DOI":"10.1109\/ICDEW.2010.5452747"},{"key":"ref_41","doi-asserted-by":"crossref","unstructured":"Bhattacharjee, A. (2013, January 7\u201311). Large-reach memory management unit caches. Proceedings of the 46th Annual IEEE\/ACM International Symposium on Microarchitecture (MICRO-46), Davis, CA, USA.","DOI":"10.1145\/2540708.2540741"},{"key":"ref_42","unstructured":"Leskovec, J., and Krevl, A. (2024, May 26). Snap Datasets: Stanford Large Network Dataset Collection. Available online: http:\/\/snap.stanford.edu\/data."},{"key":"ref_43","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1145\/227234.227246","article-title":"Parallel algorithms","volume":"39","author":"Blelloch","year":"1996","journal-title":"Commun. ACM"},{"key":"ref_44","unstructured":"Alon, N., and Spencer, J.H. (2016). The Probabilistic Method, John Wiley & Sons."},{"key":"ref_45","unstructured":"Papadimitriou, C.H. (2003). Computational complexity. Encyclopedia of Computer Science, John Wiley and Sons Ltd."},{"key":"ref_46","doi-asserted-by":"crossref","first-page":"417","DOI":"10.1145\/2402.322385","article-title":"Smallest-last ordering and clustering and graph coloring algorithms","volume":"30","author":"Matula","year":"1983","journal-title":"J. ACM"},{"key":"ref_47","doi-asserted-by":"crossref","first-page":"70","DOI":"10.1145\/273865.273901","article-title":"Probabilistic checking of proofs: A new characterization of NP","volume":"45","author":"Arora","year":"1998","journal-title":"J. ACM"}],"container-title":["Symmetry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2073-8994\/17\/8\/1177\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,9]],"date-time":"2025-10-09T18:14:43Z","timestamp":1760033683000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2073-8994\/17\/8\/1177"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,7,23]]},"references-count":47,"journal-issue":{"issue":"8","published-online":{"date-parts":[[2025,8]]}},"alternative-id":["sym17081177"],"URL":"https:\/\/doi.org\/10.3390\/sym17081177","relation":{},"ISSN":["2073-8994"],"issn-type":[{"type":"electronic","value":"2073-8994"}],"subject":[],"published":{"date-parts":[[2025,7,23]]}}}