An Algorithm for Identifying the Maximal Common Subgraph in Oriented Graphs
Abstract
Graph isomorphism checking is highly significant within both graph theory and its applications, particularly regarding oriented graph isomorphism, where identifying a bijection is an NP-hard problem.
The problem of finding the maximal common subgraph between two oriented graphs represents a specific instance of predicate formula isomorphism, occurring when an elementary conjunction includes only a single binary predicate. Initially, the algorithm was developed to determine the maximal common subformula of two elementary conjunctions. This paper provides pseudocode for algorithms that extract the maximal common subgraph in oriented graphs, accompanied by an illustrative application example.
References
Chen X., Jia S., Xiang Y. A review: Knowledge reasoning over knowledge graph // Expert Systems with Applications, 2020. Т. 141. C. 1–21. doi:10.1016/j.eswa.2019.112948
Bouritsas G. et al. Improving graph neural network expressivity via subgraph isomorphism counting // IEEE Transactions on Pattern Analysis and Machine Intelligence, 2023. Т. 45. № 1. С. 657–668. doi: 10.1109/TPAMI.2022.3154319
Zeng X. et al. GNNGL-PPI: multi-category prediction of protein-protein interactions using graph neural networks based on global graphs and local subgraphs // BMC Genomics, 2024. Т. 25. № 1. С. 1–13. doi: 10.1186/s12864-024-10299-x
Wu S. et al. Graph neural networks in recommender systems: a survey // ACM Computing Surveys, 2022. Т. 55. № 5. С. 1–37. doi: 10.1145/3535101
Cheng D. et al. Graph neural network for fraud detection via spatial-temporal attention // IEEE Transactions on Knowledge and Data Engineering, 2020. Т. 34. № 8. С. 3800–3813. doi:10.1109/TKDE.2020.3025588
Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи / пер. с англ. Левнера Е. В. , Фрумкина М. А. М.: Мир, 1982. (Garey M. R., Johnson D. S. Computers and Intractability: A Guide to the Theory of NP-Completeness.)
Косовская Т. М., Косовский Н. Н. Выделение общих свойств объектов для создания логических онтологий // Вестник Санкт-Петербургского университета. Прикладная математика. Информатика. Процессы управления, 2022. Т. 18. № 1. С. 37–51. doi: 10.21638/11701/spbu10.2022.103
Косовская Т. М., Косовский Н. Н. Полиномиальная эквивалентность задач изоморфизм предикатных формул и изоморфизм графов // Вестник Санкт-Петербургского университета. Математика. Механика. Астрономия, 2019. Т. 6 (64). № 3. С. 430–439. doi: 10.21638/11701/spbu01.2019.308
Чжоу Ц., Косовская Т. М. Алгоритм выделения общих свойств объектов, описанных на языке исчисления предикатов с одним предикатным символом // Вестник Санкт-Петербургского университета. Математика. Механика. Астрономия, 2024. Т. 11(69). № 4. С. 733–744. doi:10.21638/spbu01.2024.409
Matthes E. Python crash course: A hands-on, project-based introduction to programming, 3rd Edition. San Francisco: no starch press, 2023.
Wu Z. et al. A comprehensive survey on graph neural networks // IEEE Transactions on Neural Networks and Learning Systems, 2021. Т. 32. № 1. С. 4–24. doi:10.1109/tnnls.2020.2978386
Xu K. et al. How powerful are graph neural networks? // arxiv:1810.00826, 2018.
Zheng K. et al. NASMDR: a framework for miRNA-drug resistance prediction using efficient neural architecture search and graph isomorphism networks // Briefings in Bioinformatics, 2022. Т. 23. № 5. С. 1–9. doi: 10.1093/bib/bbac338
Su J. et al. M2DC: A meta-learning framework for generalizable diagnostic classification of major depressive disorder // IEEE Transactions on Medical Imaging. 2024. doi: 10.1109/TMI.2024.3461312
Feng Y. et al. Hypergraph isomorphism computation // IEEE Transactions on Pattern Analysis and Machine Intelligence, 2024. Т. 46. № 5. C. 3880–3896. 2024; doi: 10.1109/TPAMI.2024.3353199
This work is licensed under a Creative Commons Attribution 4.0 International License.
