Алгоритм нахождения наибольшего общего подграфа двух ориентированных графов
Аннотация
Проверка графов на изоморфизм имеет важное значение в теории графов и её прикладных областях, особенно по отношению к изоморфизму ориентированных графов, нахождение биекции которого представляет собой NP-трудную задачу.
Задача нахождения наибольшего общего подграфа двух ориентированных графов является сужением задачи изоморфизма предикатных формул, когда в элементарной конъюнкции содержится только один двухместный предикат. Ранее алгоритм был разработан для нахождения наибольшей общей подформулы двух элементарных конъюнкций. В данной работе представлены псевдокоды алгоритмов нахождения наибольшего общего подграфа для ориентированных графов и их пример использования.
Литература
X. Chen, S. Jia, and Y. Xiang, “A review: Knowledge reasoning over knowledge graph,” Expert Systems with Applications, vol. 141, pp. 1–21, 2020; doi:10.1016/j.eswa.2019.112948
G. Bouritsas et al., “Improving graph neural network expressivity via subgraph isomorphism counting,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 45, no. 1, pp. 657–668, 2023; doi:10.1109/TPAMI.2022.3154319
X. Zeng et al., “GNNGL-PPI: multi-category prediction of protein-protein interactions using graph neural networks based on global graphs and local subgraphs,” BMC Genomics, vol. 25, no. 1, pp. 1–13, 2024; doi:10.1186/s12864-024-10299-x
S. Wu et al., “Graph neural networks in recommender systems: a survey,” ACM Computing Surveys, vol. 55, no. 5, pp. 1–37, 2022; doi:10.1145/3535101
D. Cheng et al., “Graph neural network for fraud detection via spatial-temporal attention,” IEEE Transactions on Knowledge and Data Engineering, vol. 34, no. 8, pp. 3800–3813, 2020; doi:10.1109/TKDE.2020.3025588
M. R. Gareу and D. S. Johnson, Computers and intractabilitу: A Guide to the Theory of NP-Completeness, New York:W. H. Freeman and Comp., 1979.
T. M. Kosovskaya and N. N. Kosovskii, “Extraction of common properties of objects for creation of a logic ontology,” Vestnik of Saint Petersburg University. Applied Mathematics. Computer Science. Control Processes, vol. 18, no. 1, pp. 37–51, 2022 (in Russian); doi: 10.21638/11701/spbu10.2022.103
T. M. Kosovskaya and N. N. Kosovskii, “Polynomial equivalence of the problems predicate formulas isomorphism and graph isomorphism,” Vestnik of Saint Petersburg University. Mathematics. Mechanics. Astronomy, vol. 6(64), no. 3, pp. 430–439, 2019 (in Russian); doi:10.21638/11701/spbu01.2019.308
J. Zhou and T. M. Kosovskaya, “Algorithm for extraction common properties of objects described in the predicate calculus language with a single predicate symbol,” Vestnik of Saint Petersburg University. Mathematics. Mechanics. Astronomy, vol. 11(69), no. 4, pp. 733–744, 2024 (in Russian); doi:10.21638/spbu01.2024.409
E. Matthes, Python crash course: A hands-on, project-based introduction to programming, 3rd ed., San Francisco, USA: No starch press, 2023.
Z. Wu et al., “A comprehensive survey on graph neural networks,” IEEE Transactions on Neural Networks and Learning Systems, vol. 32, no. 1, pp. 4–24, 2021; doi:10.1109/tnnls.2020.2978386
K. Xu et al., “How powerful are graph neural networks?,” in Arxiv, 2018. [Online]. Available: https: //arxiv.org/abs/1810.00826
K. Zheng et al., “NASMDR: a framework for miRNA-drug resistance prediction using efficient neural architecture search and graph isomorphism networks,” Briefings in Bioinformatics, vol. 23, no. 5, pp. 1–9, 2022; doi:10.1093/bib/bbac338
J. Su et al., “M2DC: A meta-learning framework for generalizable diagnostic classification of major depressive disorder,” in IEEE Transactions on Medical Imaging, 2024; doi:10.1109/TMI.2024.3461312
Y. Feng et al., “Hypergraph Isomorphism Computation,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 46, no. 5, pp. 3880–3896, 2024; doi:10.1109/TPAMI.2024.3353199
Материал публикуется под лицензией:
