Алгоритм нахождения наибольшего общего подграфа двух ориентированных графов
Аннотация
Проверка графов на изоморфизм имеет важное значение в теории графов и её прикладных областях, особенно по отношению к изоморфизму ориентированных графов, нахождение биекции которого представляет собой NP-трудную задачу.
Задача нахождения наибольшего общего подграфа двух ориентированных графов является сужением задачи изоморфизма предикатных формул, когда в элементарной конъюнкции содержится только один двухместный предикат. Ранее алгоритм был разработан для нахождения наибольшей общей подформулы двух элементарных конъюнкций. В данной работе представлены псевдокоды алгоритмов нахождения наибольшего общего подграфа для ориентированных графов и их пример использования.
Литература
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
Материал публикуется под лицензией:
