Design and Development of Parallel Algorithm for Graph Isomorphism

Authors

  • Vijaya Parag Balpande Associate Professor, Department of Computer Science and Engineering, Priyadarshini College of Engineering, Nagpur, Maharashtra, India.
  • Ujjwala Bal Aher Lecturer, Department of Computer Engineering, Government Polytechnic, Nagpur, Maharashtra, India.
  • Shyam Deshmukh Assistant Professor, Department of Information Technology, Pune Institute of Computer Technology, Pune, India.
  • Rohit Pawar Department of Computer Science and Engineering (Data Science), Shri Ramdeobaba College of Engineering and Management, Nagpur, Maharashtra, India.
  • 5Pramod B. Dhamdhere Assistant Professor, AI&ML, G. H. Raisoni college of engineering & Management, Wagholi Pune India.
  • Nilesh Kulal Assistant Professor, MIT ADT School of Computing, MIT ADT University, Pune, India.

Keywords:

Parallel Algorithm, Recursion, Graph Isomorphism, Sub graph, Large Graph

Abstract

A fundamental issue in mathematics and computer science, the problem of graph isomorphism (GI) has applications in many fields, including chemistry, network analysis, and cryptography. To perform GI, two provided graphs must be examined to see if they are isomorphic, which means they share the same basic structure despite any differences in vertex and edge names. Computational complexity theory has long sought to create effective GI algorithms. Due to the increased accessibility of high-performance parallel computing platforms, there has been an increase in interest in parallel methods for GI in recent years. In order to speed up graph isomorphism testing, parallel methods are created to take advantage of multi-core computers, GPUs, and distributed computing clusters. The goal of this research is to create a parallel GI method that takes advantage of parallel processing to speed up computations for extensive graph comparisons. The algorithm uses a divide-and-conquer tactic, breaking down the input graphs into smaller sub-graphs that are then independently examined for isomorphism. The efficiency of these sub-graph comparisons is greatly increased by running them concurrently across numerous processing units. Load balancing algorithms are incorporated into the algorithm to provide scalability, dividing the workload equally among processing units and reducing communication cost. In order to further improve performance, the algorithm also uses optimisation techniques like graph pruning and canonization. The algorithm's success in lowering the temporal complexity of GI for big graphs is demonstrated by experimental data. This research advances graph isomorphism algorithms by utilising parallelism, which has implications for effectively resolving practical issues and overcoming computational difficulties in a variety of scientific and industrial applications.

Downloads

Download data is not yet available.

References

Lin Chen, "Parallel graph isomorphism detection with identification matrices," Proceedings of the International Symposium on Parallel Architectures, Algorithms and Networks (ISPAN), Kanazawa, Japan, 1994, pp. 105-112, doi: 10.1109/ISPAN.1994.367158.

S. Liu and Y. Wu, "Isomorphism Testing Algorithm Based on Dijkstra Algorithm for Plan Graphs," 2011 International Conference of Information Technology, Computer Engineering and Management Sciences, Nanjing, China, 2011, pp. 309-311, doi: 10.1109/ICM.2011.245.

H. Gazit, "A deterministic parallel algorithm for planar graphs isomorphism," [1991] Proceedings 32nd Annual Symposium of Foundations of Computer Science, San Juan, PR, USA, 1991, pp. 723-732, doi: 10.1109/SFCS.1991.185440.

R. Wang, L. Guo, C. Ai, J. Li, M. Ren and K. Li, "An Efficient Graph Isomorphism Algorithm Based on Canonical Labeling and Its Parallel Implementation on GPU," 2013 IEEE 10th International Conference on High Performance Computing and Communications & 2013 IEEE International Conference on Embedded and Ubiquitous Computing, Zhangjiajie, China, 2013, pp. 1089-1096, doi: 10.1109/HPCC.and.EUC.2013.154.

Lin Chen, "Graph isomorphism and identification matrices: parallel algorithms," in IEEE Transactions on Parallel and Distributed Systems, vol. 7, no. 3, pp. 308-319, March 1996, doi: 10.1109/71.491584.

B. Zhang, Y. Tang, J. Wu and L. Huang, "A Unique Vertex Deleting Algorithm for Graph Isomorphism," 2011 International Symposium on Image and Data Fusion, Tengchong, China, 2011, pp. 1-4, doi: 10.1109/ISIDF.2011.6024200.

J. Jaja and S. R. Kosaraju, "Parallel algorithms for planar graph isomorphism and related problems," in IEEE Transactions on Circuits and Systems, vol. 35, no. 3, pp. 304-311, March 1988, doi: 10.1109/31.1743.

D. S. L. Wei, F. P. Muga and K. Naik, "Isomorphism of degree four Cayley graph and wrapped butterfly and their optimal permutation routing algorithm," in IEEE Transactions on Parallel and Distributed Systems, vol. 10, no. 12, pp. 1290-1298, Dec. 1999, doi: 10.1109/71.819950.

C. -Y. Kuo, C. N. Hang, P. -D. Yu and C. W. Tan, "Parallel Counting of Triangles in Large Graphs: Pruning and Hierarchical Clustering Algorithms," 2018 IEEE High Performance extreme Computing Conference (HPEC), Waltham, MA, USA, 2018, pp. 1-6, doi: 10.1109/HPEC.2018.8547597.

G. Li, G. Rong, L. Kenli and L. Renfa, "Fast Parallel Molecular Algorithms for DNA-Based Computation: Graph Isomorphism Problem," 2009 2nd International Conference on Biomedical Engineering and Informatics, Tianjin, China, 2009, pp. 1-5, doi: 10.1109/BMEI.2009.5302914.

H. Wu, "An Invariant of the Graph Isomorphism," 2008 IEEE Pacific-Asia Workshop on Computational Intelligence and Industrial Application, Wuhan, China, 2008, pp. 307-310, doi: 10.1109/PACIIA.2008.413.

L. Cappelletti, T. Fontana, J. Reese and D. A. Bader, "Billion-scale Detection of Isomorphic Nodes," 2023 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW), St. Petersburg, FL, USA, 2023, pp. 230-233, doi: 10.1109/IPDPSW59300.2023.00046.

R. -I. Gheorghica, "An Algorithm for Concurrent Use of Quantum Simulators and Computers in the Context of Subgraph Isomorphism," 2023 IEEE 17th International Symposium on Applied Computational Intelligence and Informatics (SACI), Timisoara, Romania, 2023, pp. 000721-000726, doi: 10.1109/SACI58269.2023.10158547.

K. Date, K. Feng, R. Nagi, J. Xiong, N. S. Kim and W. -M. Hwu, "Collaborative (CPU + GPU) algorithms for triangle counting and truss decomposition on the Minsky architecture: Static graph challenge: Subgraph isomorphism," 2017 IEEE High Performance Extreme Computing Conference (HPEC), Waltham, MA, USA, 2017, pp. 1-7, doi: 10.1109/HPEC.2017.8091042.

P. Ribeiro, P. Paredes, M. Silva, D. Aparício and F. Silva, A Survey on Subgraph Counting: Concepts Algorithms and Applications to Network Motifs and Graphlets, 2019

J. R. Ullmann, An Algorithm for Subgraph Isomorphism, New York, NY, USA:Association for Computing Machinery, 1976, [online] Available: https://doi.org/10.1145/321921.321925.

V. Bonnici, R. Giugno, A. Pulvirenti, D. Shasha and A. Ferro, "A subgraph isomorphism algorithm and its application to biochemical data", BMC Bioinformatics, vol. 14, no. 7, pp. S13, 2013, [online] Available: https://doi.org/10.1186/1471-2105-14-S7-S13.

C. Solnon, "AllDifferent-based filtering for subgraph isomorphism", Artificial Intelligence, vol. 174, no. 12, pp. 850-864, [online] Available: https://doi.org/10.1016/j.artint.2010.05.002.

C. McCreesh and P. Prosser, "A Parallel Backjumping Subgraph Isomorphism Algorithm Using Supplemental Graphs", Principles and Practice of Constraint Programming, pp. 295-312, 2015.

O. Green, P. Yalamanchili and L.-M. Munguia, "Fast triangle counting on the GPU", Proceedings of the 4th Workshop on Irregular Applications: Architectures and Algorithms, pp. 1-8, 2014.

T. G. Kolda, A. Pinar, T. Plantenga, C. Seshadhri and C. Task, "Counting triangles in massive graphs with MapReduce", SIAM Journal on Scientific Computing, vol. 36, no. 5, pp. S48-S77, 2014.

A. Azad, A. Buluç and J. Gilbert, "Parallel triangle counting and enumeration using matrix algebra", Parallel and Distributed Processing Symposium Workshop (IPDPSW) 2015 IEEE International, pp. 804-811, 2015.

L. Wang, Y. Wang, C. Yang and J. D. Owens, "A comparative study on exact triangle counting algorithms on the GPU", Proceedings of the ACM Workshop on High Performance Graph Processing, pp. 1-8, 2016.

Y. Shao, L. Chen and B. Cui, "Efficient cohesive subgraphs detection in parallel", Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data, pp. 613-624, 2014.

Downloads

Published

07.01.2024

How to Cite

Balpande, V. P. ., Aher, U. B. ., Deshmukh, S. ., Pawar, R. ., Dhamdhere, 5Pramod B. ., & Kulal, N. . (2024). Design and Development of Parallel Algorithm for Graph Isomorphism. International Journal of Intelligent Systems and Applications in Engineering, 12(10s), 434–447. Retrieved from https://ijisae.org/index.php/IJISAE/article/view/4392

Issue

Vol. 12 No. 10s (2024)

Section

Research Article

License

Creative Commons License

This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

All papers should be submitted electronically. All submitted manuscripts must be original work that is not under submission at another journal or under consideration for publication in another form, such as a monograph or chapter of a book. Authors of submitted papers are obligated not to submit their paper for publication elsewhere until an editorial decision is rendered on their submission. Further, authors of accepted papers are prohibited from publishing the results in other publications that appear before the paper is published in the Journal unless they receive approval for doing so from the Editor-In-Chief.

IJISAE open access articles are licensed under a Creative Commons Attribution-ShareAlike 4.0 International License. This license lets the audience to give appropriate credit, provide a link to the license, and indicate if changes were made and if they remix, transform, or build upon the material, they must distribute contributions under the same license as the original.