Graph matching is essential in several fields that use structured information, such as biology, chemistry, social networks, knowledge management, document analysis and others. Except for special classes of graphs, graph matching has in the worst-case an exponential complexity; however, there are algorithms that show an acceptable execution time, as long as the graphs are not too large and not too dense. In this paper we introduce a novel subgraph isomorphism algorithm, VF3, particularly efficient in the challenging case of graphs with thousands of nodes and a high edge density. Its performance, both in terms of time and memory, has been assessed on a large dataset of 12,700 random graphs with a size up to 10,000 nodes, made publicly available. VF3 has been compared with four other state-of-the-art algorithms, and the huge experimentation required more than two years of processing time. The results confirm that VF3 definitely outperforms the other algorithms when the graphs become huge and dense, but also has a very good performance on smaller or sparser graphs.
Download full-text PDF |
Source |
|---|---|
| http://dx.doi.org/10.1109/TPAMI.2017.2696940 | DOI Listing |
Publication Analysis
Top Keywords
Similar Publications
GADIFF: a transferable graph attention diffusion model for generating molecular conformations.
Brief Bioinform
November 2024
School of Information Science and Technology, Northeast Normal University, 130117 Changchun, China.
Article Synopsis
- GADIFF is a novel graph attention diffusion model designed for generating molecular conformations, leveraging equivariant networks and self-attention mechanisms to enhance feature representation and noise prediction.
- The model incorporates Graph Isomorphism Networks for capturing local interactions within molecular structures and demonstrates improved performance in generating diverse and accurate molecular conformations compared to existing state-of-the-art methods.
- A derived model, GADIFF-NCI, extends GADIFF's capabilities to noncovalent interaction systems, showing effective conformation generation, indicating its potential for broader applications in studying complex molecular conformations.
Hyper-Zagreb index in fuzzy environment and its application.
Heliyon
August 2024
Department of Applied Mathematics, Vidyasagar University, Midnapore 721102, India.
The Zagreb indices (ZIs) are important graph invariants that are used extensively in many different fields in mathematics and chemistry, such as network theory, spectral graph theory, fuzzy graph theory (FGT) and molecular chemistry, etc. The hyper-ZI is introduced especially for fuzzy graphs (FGs) in this study. The study computes this index's bounds for a variety of FG types, including paths, cycles, stars, complete FGs and partial fuzzy subgraphs.
View Article and Find Full Text PDFRapid Mining of Fast Ion Conductors via Subgraph Isomorphism Matching.
J Am Chem Soc
July 2024
School of Advanced Materials, Peking University, Shenzhen Graduate School, Shenzhen 518055, P. R. China.
The rapidly evolving field of inorganic solid-state electrolytes (ISSEs) has been driven in recent years by advances in data-mining techniques, which facilitates the high-throughput computational screening for candidate materials in the databases. The key to the mining process is the selection of critical features that underline the similarity of a material to an existing ISSE. Unfortunately, this selection is generally subjective and frequently under debate.
View Article and Find Full Text PDFGNNGL-PPI: multi-category prediction of protein-protein interactions using graph neural networks based on global graphs and local subgraphs.
BMC Genomics
May 2024
College of Mathematics and Computer Science, Dali University, 671003, Dali, China.
Most proteins exert their functions by interacting with other proteins, making the identification of protein-protein interactions (PPI) crucial for understanding biological activities, pathological mechanisms, and clinical therapies. Developing effective and reliable computational methods for predicting PPI can significantly reduce the time-consuming and labor-intensive associated traditional biological experiments. However, accurately identifying the specific categories of protein-protein interactions and improving the prediction accuracy of the computational methods remain dual challenges.
View Article and Find Full Text PDFSubgraph Isomorphic Decision Tree to Predict Radical Thermochemistry with Bounded Uncertainty Estimation.
J Phys Chem A
April 2024
Department of Chemical Engineering, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139, United States.
Article Synopsis
- Detailed chemical kinetic models are crucial for understanding industrial processes, and accurate radical thermochemistry estimation is essential for generating reliable kinetic models efficiently.* -
- The subgraph isomorphic decision tree (SIDT) algorithm has been enhanced to estimate hydrogen bond increment (HBI) corrections, improving accuracy and providing better uncertainty estimates compared to traditional methods.* -
- A comprehensive data set of thermochemical parameters for 2210 radicals was created, enabling the SIDT model to offer automatic generation of estimators, enhanced speed, and more precise predictions for radical thermochemistry.*
Want AI Summaries of new PubMed Abstracts delivered to your In-box?
Enter search terms and have AI summaries delivered each week - change queries or unsubscribe any time!