The subgraph matching problem (subgraph isomorphism) is NP-complete. We designed a simple exact subgraph matching (ESM) algorithm for dependency graphs using a backtracking approach. The total worst-case algorithm complexity is O(n² * kⁿ) where n is the number of vertices and k is the vertex degree.

We have demonstrated the successful usage of our algorithm in three biomedical relation and event extraction applications: BioNLP 2011 shared tasks on event extraction, Protein-Residue association detection and Protein-Protein interaction identification.

This Java implementation implements our ESM algorithm. It addition to subgraph isomorphism, it also provides a function to determine graph isomorphism.

If you use our ESM implementation to support academic research, please cite the following paper:

Haibin Liu, Vlado Keselj, and Christian Blouin. Exploring a Subgraph Matching Approach for Extracting Biological Events from Literature. Computational Intelligence, 2013.

Source code and resources pertaining to the ESM 1.0 release are available here
Java API documentation can be found at http://esmalgorithm.sourceforge.net/apidocs/

Version 1.0 of the ESM is available via a Maven repository. If you use Maven as your build tool, you can add the ESM as a dependency by adding the following to your pom.xml file:

<dependency>
  <groupId>edu.ucdenver.ccp</groupId>
  <artifactId>esm</artifactId>
  <version>1.0</version>
</dependency>

<repository>
  <id>bionlp-sourceforge</id>
  <url>http://svn.code.sf.net/p/bionlp/code/repo/</url>
</repository>

Exact Subgraph Matching Algorithm (ESM)