A (sub)graph isomorphism algorithm for matching large graphs

By Luigi Pietro Cordella, Pasquale Foggia, Carlo Sansone, Mario Vento. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2004

1,585 citations recorded by the source corpus.

Subfields: Computer Networks and Communications, Computer Vision and Pattern Recognition, Signal Processing

View Paper: https://www.semanticscholar.org/paper/87507a498558ed6ed23115a42f42376c0884f7f2

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Networks and Communications

In Computer Vision and Pattern Recognition

In Signal Processing

Citations in the corpus

DockRMSD: an open-source tool for atom mapping and RMSD calculation of symmetric molecules through graph isomorphism (2019, methodology): “Finally, OpenBabel [15] contains a C++ open source tool, obrms, that considers symmetry correction as a graph isomorphism problem, solved by the VF2 algorithm [16], but also currently requires that the user install the entirety of OpenBabel to use this tool.”
Turboiso: towards ultrafast and robust subgraph isomorphism search in large graph databases (2013, background): “Due to good matching order and the C OMB/PER M strategy, TurboISO outperthe NASA dataset contains only trees, VF2, QuickSI, and GADDI show exponential behaviors at the sizes of query sets 8, 12, and 8, respectively.”
Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting (2020, background): “rithm [53], and its recently improved version, the VF3 [54]”
The Index-Based Subgraph Matching Algorithm (ISMA): Fast Subgraph Enumeration in Large Networks Using Optimized Search Trees (2013, methodology): “To demonstrate the strength of the ISMA algorithm, we compared it to the naive recursive subgraph matching algorithm (RSMA) as well as the algorithm of Ullmann [9], the VF algorithm [10,11] and the VF2 algorithm [12,13], which are state-of-the-art subgraph matching algorithms.”
Ligand placement based on prior structures: the guided ligand-replacement method (2013, methodology): “The subgraph isomorphism algorithm (Cordella et al., 2004) was modified to the application of almost planar graphs.”
Gromov-Wasserstein Learning for Graph Matching and Node Embedding (2019, background): “, 2008), linking accounts in different social networks (Zhang & Philip, 2015), and feature matching in computer vision (Cordella et al., 2004; Zanfir & Sminchisescu, 2018).”
Efficient Subgraph Matching by Postponing Cartesian Products (2016, methodology): “Request permissions from permissions@acm.org. ing paradigms to conduct subgraph matching [4, 8, 14, 15, 22].”
Attack of the Clones: Detecting Cloned Applications on Android Markets (2012, methodology): “We use the VF2 algorithm to compute subgraph isomorphisms, which is a backtracking algorithm geared towards matching large graphs [26].”
Efficient Subgraph Matching on Billion Node Graphs (2012, methodology): “For example, Ullmann [26] and Cordella et al [11] proposed global pruning strategy to accelerate query processing.”
GADDI: distance index based subgraph matching in biological networks (2009, methodology): “Graphs can be used to model complex data objects in a number of applications, e.g., network intrusion detection [33, 26], the semantic web [2], behavioral modeling [43, 34], VLSI reverse engineering [49], link analysis [22, 25, 36], and chemical compound classi.cation [9, 30, 15, 10].”
Generic Strategies for Chemical Space Exploration (2013, methodology): “The current implementation uses VF2[5] to ﬁnd subgraph isomorphisms, and as a fall-back algorithm for isomorphism check for general graphs.”
You Are What You Do: Hunting Stealthy Malware via Data Provenance Analysis (2020, background): “, n-gram [23] or sub-graph matching [24]) would incur huge computation and storage pressure, making it infeasible for any realistic deployment.”
Reaction Mechanism Generator: Automatic construction of chemical kinetic mechanisms (2016, methodology): “The VF2 algorithm [19] for graph and subgraph isomorphisms is currently implemented in RMG.”
TrGraph: Cross-Network Transfer Learning via Common Signature Subgraphs (2015, neutral): “In the node classification problem setting, it is assumed that a small set of nodes are required to be labeled through a manual annotation process.”