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
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
This work is licensed under a Creative Commons Attribution 4.0 International License.
